Boundary tracing

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

Types

• Pixel-Following: walks through cells and records them. Typically only traces an outer boundary and require post-processing when changing the size of the space. Easiest to implement
• Vertex-Following Method: walks through edges, recording edges and corners. Typically only traces the outer boundary. Sequential edges can be removed to simplify the data
• Run-Data-Based: processes all cells in the space. Traces all boundaries in the image. Less efficient than other types for small single boundaries since all cells have to be processed. More efficient for large, complex images since the steps per individual cell are usually less than other types ^[3]

Examples

Algorithms used for boundary tracing: ^[4]

• Square tracing algorithm. ^[5] Can only be used for 4-connected (non-diagonal) patterns and requires the stopping criteria to be entering the starting cell in the same direction as the beginning.
• Moore-neighbor tracing algorithm is similar to the Square tracing algorithm with similar weaknesses but works with 8-connected (diagonal) patterns
• Radial sweep ^[6]
• Theo Pavlidis’ algorithm ^[7] tests three cells in front but the check can be short-circuited. Might fail on some patterns.
• A generic approach using vector algebra for tracing of a boundary can be found at ^[8]
• An extension of boundary tracing for segmentation of traced boundary into open and closed sub-section is described at ^[9]

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

Square tracing algorithm

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:

• If you are in a white cell, go left.
• If you are in a black cell, go right.

Keep in mind that it matters how you entered the current cell, so that left and right can be defined.

publicvoidGetBoundary(byte[,]image){for(intj=0;j<image.GetLength(1);j++)for(inti=0;i<image.GetLength(0);i++)if(image[i,j]==255)// Found first white pixelSquareTrace(newPoint(i,j));}publicvoidSquareTrace(Pointstart){HashSet<Point>boundaryPoints=newHashSet<Point>();// Use a HashSet to prevent double occurrences// We found at least one pixelboundaryPoints.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)PointnextStep=GoLeft(newPoint(1,0));Pointnext=start+nextStep;while(next!=start){// We found a black cell, so we go right and don't add this cell to our HashSetif(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 HashSetelse{boundaryPoints.Add(next);nextStep=GoLeft(nextStep);next=next+nextStep;}}}privatePointGoLeft(Pointp)=>newPoint(p.y,-p.x);privatePointGoRight(Pointp)=>newPoint(-p.y,p.x);

Radial sweep

The Radial Sweep algorithm, often discussed in literature alongside its more commonly known counterpart, Moore-Neighbor Tracing, presents a seemingly straightforward approach to contour tracing in image processing. While the algorithm's nomenclature may evoke a sense of complexity, its underlying principle aligns closely with the familiar Moore-Neighbor Tracing technique.

Moore-Neighbor Tracing, a prevalent method for delineating boundaries within digital images, navigates the Moore neighborhood of a designated boundary pixel in a predetermined direction, typically clockwise. Upon encountering a black pixel, it designates this pixel as the new boundary point and proceeds iteratively.

However, the Radial Sweep algorithm, while functionally equivalent to Moore-Neighbor Tracing, introduces a novel perspective on identifying the next black pixel within the Moore neighborhood of a given boundary point.

The algorithm's innovation lies in its approach to pinpointing the subsequent boundary pixel. Upon identifying a new boundary pixel, denoted as P, the algorithm establishes it as the current point of interest. It then constructs an imaginary line segment connecting point P to the preceding boundary pixel. Subsequently, the algorithm systematically rotates this segment about point P in a clockwise direction until it intersects with a black pixel within P's Moore neighborhood. ^[10] Effectively, this rotational movement mirrors the process of inspecting each pixel surrounding point P in the Moore neighborhood.

By employing this method, the Radial Sweep algorithm offers a distinctive strategy for traversing boundary pixels within digital images. While fundamentally akin to Moore-Neighbor Tracing, its emphasis on rotational exploration introduces an intriguing perspective on contour tracing techniques in image analysis and computer vision applications.

Theo Pavlidis' Algorithm

Theo Pavlidis' Algorithm is a well-known method for contour tracing in binary images proposed, designed to methodically detect and follow the boundaries of related components. The technique starts by locating an initial boundary pixel, which is usually the first black pixel seen while scanning the image from top to bottom and left to right. It begins by examining the vicinity of the current pixel to locate the next boundary pixel, often going in a clockwise orientation to find the next black pixel that makes up the boundary. ^[10]

The program traces the contour by moving from one border pixel to the next, ensuring that each boundary pixel is only visited once. This systematic technique promotes computing efficiency. The tracing process continues until the algorithm returns to the first border pixel, completing the contour of the item. The approach is reasonably simple to implement, making it a popular choice for a variety of applications such as object detection, shape analysis, and pattern recognition in computer vision and image processing tasks.

Theo Pavlidis' algorithm is renowned for its simplicity, efficiency, and resilience. It can handle a wide range of object shapes and sizes within binary images, making it useful for a variety of image processing applications.

See also

• Pathfinding
• Curve sketching
• Chain code
• Pixel connectivity
• Optimization problem

References

1. Kovalevsky, V., Image Processing with Cellular Topology, Springer 2021, ISBN 978-981-16-5771-9
2. http://www.kovalevsky.de, Lecture "Tracing Boundaries in 2D Images"
3. Seo, Jonghoon; Chae, Seungho; Shim, Jinwook; Kim, Dongchul; Cheong, Cheolho; Han, Tack-Don (March 2016). "Fast Contour-Tracing Algorithm Based on a Pixel-Following Method for Image Sensors". Sensors. 16 (3): 353. Bibcode:2016Senso..16..353S. doi: 10.3390/s16030353 . PMC   4813928 . PMID   27005632.
4. Contour Tracing Algorithms
5. Abeer George Ghuneim: square tracing algorithm
6. Abeer George Ghuneim: The Radial Sweep algorithm
7. Abeer George Ghuneim: Theo Pavlidis' Algorithm
8. Vector Algebra Based Tracing of External and Internal Boundary of an Object in Binary Images, Journal of Advances in Engineering Science Volume 3 Issue 1, January–June 2010, PP 57–70
9. Graph theory based segmentation of traced boundary into open and closed sub-sections, Computer Vision and Image Understanding, Volume 115, Issue 11, November 2011, pages 1552–1558
10. 1 2 Reddy, P.Rajashekar; V., Amarnadh; Mekala, Bhaskar (January 2012). "Evaluation of Stopping Criterion in Contour Tracing Algorithms". International Journal of Computer Science and Information Technologies. 3 (3): 3888–3894. ISSN   0975-9646.