邊界跟蹤

二值圖像的邊界跟蹤Boundary tracing,也稱 輪廓跟蹤contour tracing)可以被認為是一種識別數字區域邊界像素的圖像分割技術。邊界跟蹤是分析區域的第一步操作。

算法

邊界跟蹤的算法有:[1]

  • Square跟蹤算法[2]
  • Moore鄰域跟蹤算法
  • 徑向掃描 (radical sweep)[3]
  • Theo Pavlidis算法 [4]
  • 一種使用向量幾何的泛化的算法:[5]
  • 一種分割區域為開、閉子區域的算法:[6]

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

參見

參考資料

  1. ^ Contour Tracing Algorithms. [2021-12-28]. (原始內容存檔於2022-07-04). 
  2. ^ Abeer George Ghuneim: square tracing algorithm. [2021-12-28]. (原始內容存檔於2022-03-25). 
  3. ^ Abeer George Ghuneim: The Radial Sweep algorithm. [2021-12-28]. (原始內容存檔於2021-12-28). 
  4. ^ Abeer George Ghuneim: Theo Pavlidis' Algorithm. [2021-12-28]. (原始內容存檔於2021-12-28). 
  5. ^ 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]頁面存檔備份,存於網際網路檔案館
  6. ^ 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]頁面存檔備份,存於網際網路檔案館