边界跟踪

二值图像的边界跟踪（Boundary tracing，也称 轮廓跟踪即contour tracing）可以被认为是一种识别数字区域边界像素的图像分割技术。边界跟踪是分析区域的第一步操作。

算法
边界跟踪的算法有：
 Square跟踪算法
 Moore邻域跟踪算法 
 径向扫描 （radical sweep）
 Theo Pavlidis算法 
 一种使用向量几何的泛化的算法：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  

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);

参见
 寻路



 最佳化問題

 参考资料 

Category:数字拓扑学