一種基于像素標記的二值圖像區域圍線追蹤方法

陳兆學， 張 奎

（上海理工大學 醫療器械與食品學院，上海 200093）

在圖像處理、計算機視覺以及模式識別等研究領域中，通常需要對目標區域的邊界信息進行分析，如邊界曲率、邊界長度、鏈碼及凹凸度等參數，圍線追蹤就是用來獲得目標區域的這些特征信息的有效方法[1-3]。在激光平面雕刻中，圖像目標區域的圍線追蹤同樣十分必要。為了解決傳統的直線式掃描帶來的一系列缺點，如雕刻邊緣易出現鋸齒現象、頻繁關斷造成激光頭壽命受影響等，以圖像區域圍線追蹤為基礎的螺旋掃描技術顯得十分有必要。如果激光頭始終沿著圖像邊緣行進，那么，連續的光刻槽形成的包絡將消除圖像邊緣處的鋸齒[4]。這些沿著圖像邊緣行進所形成的軌跡即認為是圖像當前區域的圍線，組合起來可認為近似構成螺旋形結構。

在現有的圍線追蹤算法中，很多算法在追蹤某些形狀的區域圍線時往往會出現錯誤[1,5]。文獻[4]雖然給出了一種用于生成螺旋掃描線的圍線追蹤方法，但該方法只能處理結構較為簡單的圖像，也沒有考慮追蹤過程中易出現的特殊問題，抗噪性能較差，不能直接用于工業生產中。文獻[6]提出了一種基于邊過程的圖像區域圍線追蹤算法，雖然計算復雜度是線性的，但時間復雜度相對較高。在一些基于像素的圍線追蹤算法中，一般采用邊界像素來表示圍線，例如，Square Tracing，Moore-Neighbor Tracing，Radial Sweep和Theo Pavlidis算法。但由于某些特定區域存在單像素寬度的情形，導致這些圍線追蹤算法在這些區域的特定區段追蹤時容易產生遺漏或提前終止的情況[6]。本文在文獻[4]的算法基礎上提出了一種改進的基于像素點多次標記[7]的二值圖像區域圍線追蹤方法。通過定義特定追蹤方向，使得追蹤過程始終按照逆時針或順時針方向沿著連通區域邊緣行進[8]。在追蹤過程中對像素點進行多次標記，通過在按照追蹤方向確定的像素點基礎上判斷像素標記值來確定下一次追蹤像素點的選取。由于對像素點進行多次標記，有效區分了一次追蹤像素點和二次追蹤像素點，解決了追蹤過程中出現的追蹤間斷現象[9]，使得追蹤結果呈現一條完整圍線。實驗結果表明，本文方法可以快速有效地完成二值圖像連通區域的圍線追蹤和提取。

1 二值圖像區域圍線追蹤算法

1.1 二值圖像“尾巴點”的定義

定義 如圖1所示，不參與形成封閉輪廓的且與構成輪廓像素發生黏連關系的一類像素，將其定義為“尾巴點”。若采用現有的圍線追蹤方法[4]追蹤到該類點時，由于無跳出尾巴點的有效措施，導致提前終止追蹤。本文所設計的像素點追蹤算法將設法有效跳出“尾巴點”，最終追蹤出完整的圍線。

圖 1 “尾巴點”示意Fig.1 Diagram of tail points

1.2 基于像素標記的二值圖像區域圍線追蹤

基于像素點的二值圖像區域圍線追蹤實際上是從目標區域某一邊緣像素點出發，按照逆時針或順時針方向不斷搜尋后續邊緣點，從而形成一條完整圍線的過程。文獻[4]中提出的圍線追蹤方法是基于某點P周圍8個方向的優先順序（如圖2所示）來判斷后續追蹤點的選擇。該方法能夠很好地將簡單區域的邊緣輪廓按照逆時針的方向追蹤出來，但是，對于較為復雜的圖像忽略了一些容易出現的特殊情況（如“尾巴點”的存在），直接造成追蹤陷入無限循環或追蹤提前終止，抗邊緣噪聲能力較低。針對該算法的不足之處，本文給出了改進后的完整算法。

圖 2 后續點方向選擇優先級示意Fig.2 Diagram of the prioritization of subsequent points direction

算法步驟：

步驟1 對二值圖像進行掃描，掃描到的第一個目標點設為當前點[10]，記錄坐標值并將標記值設為，定義方向因子d=0，像素值轉換因子s=0，算法結束標志t=0。

步 驟 2 令 方 向 因 子 d=mod （d+5，8），mod（a，b）表示求a除以b的余數，判斷該方向上的點是否為目標點且未被標記，若是，則記錄坐標值且標記值設為，該點設為當前點，重復步驟2，否則，令s=1，進行下一步。

步驟3 令方向因子d=mod （d+5，8 ），判斷該方向上的點是否為目標點且未被標記，若是，則記錄坐標值且標記值設為，該點設為當前點，轉步驟2，否則，s=s+1，若s=8，令t=0，且將當前點標記值轉換為，并進行下一步，否則，重復步驟3。

步驟4 若t=8，則轉步驟5，否則，令方向因子 d=mod （d+1，8 ），t=t+1，判斷該方向上像素點的標記值，若為，轉步驟5；若為，則將標記值轉換成，并將該點設為當前點，重復步驟4；若無標記值且為目標點，則該點設為當前點，記錄坐標值且標記值設為，轉步驟2，若不為目標點，則重復步驟4。

步驟5 結束算法。

值得說明的是，像素值轉換因子s的值是像素點對應的像素值是否由轉換為的標志，算法結束標志t為完整圍線追蹤標志。在“尾巴點”區域，像素點像素值會轉換為，以此為標志，追蹤過程會逐步回溯，直到找到新的未標記的目標點，從而跳出“尾巴點”。

2 實驗驗證與分析

如圖3所示，約定顏色較深區域為目標區域，每個小方格代表一個單位像素，采用本文提出的基于像素多次標記的二值圖像區域圍線追蹤算法對圖3中的目標區域進行模擬實驗，最終的追蹤圍線為如圖4所示的顏色較深的區域。表1按照追蹤到目標像素點的先后順序給出了圖像坐標系下構成圍線的像素點坐標值以及最終標記值。圖5展示了追蹤過程。

圖 3 模擬實驗圖像Fig.3 Simulated experimental image

圖 4 追蹤結果示意Fig.4 Diagram of tracking results

圖 5 追蹤過程示意Fig.5 Diagram of tracing process

表 1 圍線追蹤過程像素坐標與標記數據表Tab.1 Pixels coordinates and labeled data in contour tracing process

由圖4可以看出，構成圍線的像素被成功地追蹤出來，呈現一條完整圍線。被追蹤到的目標像素點分別被標記為，和。其中，代表追蹤起始點和結束點，代表追蹤一次的點，代表追蹤二次的點。由圖4和表1可知，“尾巴點”均被標記為，也成功地被找出，且未因“尾巴點”的存在而中斷追蹤。

利用本文算法對圖3進行完整的追蹤過程總搜索判斷像素點262次，追蹤到有效構成圍線像素點42個，利用文獻[4]進行圍線追蹤，當追蹤到表1中所示的21號點時，便無法繼續追蹤，充分說明本文算法對文獻[4]所述算法進行了有效的改進。

3 結 論

提出了一種基于像素標記的二值圖像區域圍線追蹤方法。該算法在已有圍線追蹤算法的基礎上，通過定義特定追蹤方向，使得追蹤過程始終按照逆時針或順時針方向沿著連通區域邊緣進行。在追蹤過程中對像素點進行多次標記，通過在按照追蹤方向確定的像素點基礎上判斷像素標記值來確定下一次待追蹤像素點的選取。提出“尾巴點”的概念，并對“尾巴點”區段的一次追蹤和二次追蹤進行了有效區分，解決了追蹤過程中出現的追蹤間斷現象，使得追蹤結果呈現一條完整圍線。大量實驗表明，方法可行且可靠，能夠很好地實現二值圖像目標區域的圍線追蹤。