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.
Algorithms
Algorithms used for boundary tracing:[1]
- Square tracing algorithm[2]
- Moore-neighbor tracing algorithm
- Radial sweep [3]
- Theo Pavlidis’ algorithm [4]
- A generic approach using vector algebra for tracing of a boundary can be found at.[5]
- An extension of boundary tracing for segmentation of traced boundary into open and closed sub-section is described at.[6]
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.
public void GetBoundary(byte[,] image)
{
for (int j = 0; j < image.GetLength(1); j++)
for (int i = 0; int 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.
// 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);
gollark: Or the contest page.
gollark: You can't arbitrarily change the number, but you can send stupid amounts of increment or decrement requests.
gollark: It's not very secure, honestly.
gollark: incdec game idea: write a program to constantly emulate clicking +.
gollark: There are at least three bots for it around.
References
- Contour Tracing Algorithms
- Abeer George Ghuneim: square tracing algorithm
- Abeer George Ghuneim: The Radial Sweep algorithm
- Abeer George Ghuneim: Theo Pavlidis' Algorithm
- 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
- 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.