边界跟踪
二值图像的边界跟踪(Boundary tracing,也称 轮廓跟踪即contour tracing)可以被认为是一种识别数字区域边界像素的图像分割技术。边界跟踪是分析区域的第一步操作。
算法
边界跟踪的算法有:[1]
Square 跟踪算法
Square跟踪算法简单但有效。它的行为完全基于格子是白格还是黑格(假设白格是形状的一部分)。首先,从左上到右上逐行扫描。进入第一个白格后,算法的核心部分就开始了。它主要包括两个规则:
- 如果在白格,左转
- 如果在黑格,右转
需要记录进入当前格的过程,这样才能定义左和右方向。
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.
// 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);
参见
- 寻路
- 曲线描边
- 链码
- 像素联通性
- 最佳化问题
参考资料
- ^ Contour Tracing Algorithms. [2021-12-28]. (原始内容存档于2022-07-04).
- ^ Abeer George Ghuneim: square tracing algorithm. [2021-12-28]. (原始内容存档于2022-03-25).
- ^ Abeer George Ghuneim: The Radial Sweep algorithm. [2021-12-28]. (原始内容存档于2021-12-28).
- ^ Abeer George Ghuneim: Theo Pavlidis' Algorithm. [2021-12-28]. (原始内容存档于2021-12-28).
- ^ 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 [1] (页面存档备份,存于互联网档案馆)
- ^ 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 [2] (页面存档备份,存于互联网档案馆)