Boundary tracing, also known as contour tracing, of a binary digital region can be thought of as a segmentation technique that identifies the boundary pixels of the digital region. Boundary tracing is an important first step in the analysis of that region. Boundary is a topological notion. However, a digital image is no topological space. Therefore, it is impossible to define the notion of a boundary in a digital image mathematically exactly. Most publications about tracing the boundary of a subset S of a digital image I describe algorithms which find a set of pixels belonging to S and having in their direct neighborhood pixels belonging both to S and to its complement I - S. According to this definition the boundary of a subset S is different from the boundary of the complement I – S which is a topological paradox.
To define the boundary correctly it is necessary to introduce a topological space corresponding to the given digital image. Such space can be a two-dimensional abstract cell complex. It contains cells of three dimensions: the two-dimensional cells corresponding to pixels of the digital image, the one-dimensional cells or “cracks” representing short lines lying between two adjacent pixels, and the zero-dimensional cells or “points” corresponding to the corners of pixels. The boundary of a subset S is then a sequence of cracks and points while the neighborhoods of these cracks and points intersect both the subset S and its complement I – S.
The boundary defined in this way corresponds exactly to the topological definition and corresponds also to our intuitive imagination of a boundary because the boundary of S should contain neither elements of S nor those of its complement. It should contain only elements lying between S and the complement. This are exactly the cracks and points of the complex.
This method of tracing boundaries is described in the book of Vladimir A. Kovalevsky[1] and in the web site.[2]
Algorithms used for boundary tracing:[4]
Marching squares extracts contours by checking all corners of all cells in a two-dimensional field. It does not use an initial position and does not generate the contour as an ordered sequence so it does not 'trace' the contour. Has to check each cell corner for all four neighbors but since the checks are independent performance can be easily improved with parallel processing
The square tracing algorithm is simple, yet effective. Its behavior is completely based on whether one is on a black, or a white cell (assuming white cells are part of the shape). First, scan from the upper left to right and row by row. Upon entering your first white cell, the core of the algorithm starts. It consists mainly of two rules:
Keep in mind that it matters how you entered the current cell, so that left and right can be defined.
public void GetBoundary(byte[,] image)
{
for (int j = 0; j < image.GetLength(1); j++)
for (int i = 0; i < image.GetLength(0); i++)
if (image[i, j] == 255) // Found first white pixel
SquareTrace(new Point(i, j));
}
public void SquareTrace(Point start)
{
HashSet<Point> boundaryPoints = new HashSet<Point>(); // Use a HashSet to prevent double occurrences
// We found at least one pixel
boundaryPoints.Add(start);
// The first pixel you encounter is a white one by definition, so we go left.
// In this example the Point constructor arguments are y,x unlike convention
// Our initial direction was going from left to right, hence (1, 0)
Point nextStep = GoLeft(new Point(1, 0));
Point next = start + nextStep;
while (next != start)
{
// We found a black cell, so we go right and don't add this cell to our HashSet
if (image[next.x, next.y] == 0)
{
next = next - nextStep;
nextStep = GoRight(nextStep);
next = next + nextStep;
}
// Alternatively we found a white cell, we do add this to our HashSet
else
{
boundaryPoints.Add(next);
nextStep = GoLeft(nextStep);
next = next + nextStep;
}
}
}
private Point GoLeft(Point p) => new Point(p.y, -p.x);
private Point GoRight(Point p) => new Point(-p.y, p.x);