一種基于像素標(biāo)記的二值圖像區(qū)域圍線(xiàn)追蹤方法

陳兆學(xué)， 張 奎

（上海理工大學(xué) 醫(yī)療器械與食品學(xué)院，上海 200093）

在圖像處理、計(jì)算機(jī)視覺(jué)以及模式識(shí)別等研究領(lǐng)域中，通常需要對(duì)目標(biāo)區(qū)域的邊界信息進(jìn)行分析，如邊界曲率、邊界長(zhǎng)度、鏈碼及凹凸度等參數(shù)，圍線(xiàn)追蹤就是用來(lái)獲得目標(biāo)區(qū)域的這些特征信息的有效方法[1-3]。在激光平面雕刻中，圖像目標(biāo)區(qū)域的圍線(xiàn)追蹤同樣十分必要。為了解決傳統(tǒng)的直線(xiàn)式掃描帶來(lái)的一系列缺點(diǎn)，如雕刻邊緣易出現(xiàn)鋸齒現(xiàn)象、頻繁關(guān)斷造成激光頭壽命受影響等，以圖像區(qū)域圍線(xiàn)追蹤為基礎(chǔ)的螺旋掃描技術(shù)顯得十分有必要。如果激光頭始終沿著圖像邊緣行進(jìn)，那么，連續(xù)的光刻槽形成的包絡(luò)將消除圖像邊緣處的鋸齒[4]。這些沿著圖像邊緣行進(jìn)所形成的軌跡即認(rèn)為是圖像當(dāng)前區(qū)域的圍線(xiàn)，組合起來(lái)可認(rèn)為近似構(gòu)成螺旋形結(jié)構(gòu)。

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

1 二值圖像區(qū)域圍線(xiàn)追蹤算法

1.1 二值圖像“尾巴點(diǎn)”的定義

定義 如圖1所示，不參與形成封閉輪廓的且與構(gòu)成輪廓像素發(fā)生黏連關(guān)系的一類(lèi)像素，將其定義為“尾巴點(diǎn)”。若采用現(xiàn)有的圍線(xiàn)追蹤方法[4]追蹤到該類(lèi)點(diǎn)時(shí)，由于無(wú)跳出尾巴點(diǎn)的有效措施，導(dǎo)致提前終止追蹤。本文所設(shè)計(jì)的像素點(diǎn)追蹤算法將設(shè)法有效跳出“尾巴點(diǎn)”，最終追蹤出完整的圍線(xiàn)。

圖 1 “尾巴點(diǎn)”示意Fig.1 Diagram of tail points

1.2 基于像素標(biāo)記的二值圖像區(qū)域圍線(xiàn)追蹤

基于像素點(diǎn)的二值圖像區(qū)域圍線(xiàn)追蹤實(shí)際上是從目標(biāo)區(qū)域某一邊緣像素點(diǎn)出發(fā)，按照逆時(shí)針或順時(shí)針?lè)较虿粩嗨褜ず罄m(xù)邊緣點(diǎn)，從而形成一條完整圍線(xiàn)的過(guò)程。文獻(xiàn)[4]中提出的圍線(xiàn)追蹤方法是基于某點(diǎn)P周?chē)?個(gè)方向的優(yōu)先順序（如圖2所示）來(lái)判斷后續(xù)追蹤點(diǎn)的選擇。該方法能夠很好地將簡(jiǎn)單區(qū)域的邊緣輪廓按照逆時(shí)針的方向追蹤出來(lái)，但是，對(duì)于較為復(fù)雜的圖像忽略了一些容易出現(xiàn)的特殊情況（如“尾巴點(diǎn)”的存在），直接造成追蹤陷入無(wú)限循環(huán)或追蹤提前終止，抗邊緣噪聲能力較低。針對(duì)該算法的不足之處，本文給出了改進(jìn)后的完整算法。

圖 2 后續(xù)點(diǎn)方向選擇優(yōu)先級(jí)示意Fig.2 Diagram of the prioritization of subsequent points direction

算法步驟：

步驟1 對(duì)二值圖像進(jìn)行掃描，掃描到的第一個(gè)目標(biāo)點(diǎn)設(shè)為當(dāng)前點(diǎn)[10]，記錄坐標(biāo)值并將標(biāo)記值設(shè)為，定義方向因子d=0，像素值轉(zhuǎn)換因子s=0，算法結(jié)束標(biāo)志t=0。

步 驟 2 令 方 向 因 子 d=mod （d+5，8），mod（a，b）表示求a除以b的余數(shù)，判斷該方向上的點(diǎn)是否為目標(biāo)點(diǎn)且未被標(biāo)記，若是，則記錄坐標(biāo)值且標(biāo)記值設(shè)為，該點(diǎn)設(shè)為當(dāng)前點(diǎn)，重復(fù)步驟2，否則，令s=1，進(jìn)行下一步。

步驟3 令方向因子d=mod （d+5，8 ），判斷該方向上的點(diǎn)是否為目標(biāo)點(diǎn)且未被標(biāo)記，若是，則記錄坐標(biāo)值且標(biāo)記值設(shè)為，該點(diǎn)設(shè)為當(dāng)前點(diǎn)，轉(zhuǎn)步驟2，否則，s=s+1，若s=8，令t=0，且將當(dāng)前點(diǎn)標(biāo)記值轉(zhuǎn)換為，并進(jìn)行下一步，否則，重復(fù)步驟3。

步驟4 若t=8，則轉(zhuǎn)步驟5，否則，令方向因子 d=mod （d+1，8 ），t=t+1，判斷該方向上像素點(diǎn)的標(biāo)記值，若為，轉(zhuǎn)步驟5；若為，則將標(biāo)記值轉(zhuǎn)換成，并將該點(diǎn)設(shè)為當(dāng)前點(diǎn)，重復(fù)步驟4；若無(wú)標(biāo)記值且為目標(biāo)點(diǎn)，則該點(diǎn)設(shè)為當(dāng)前點(diǎn)，記錄坐標(biāo)值且標(biāo)記值設(shè)為，轉(zhuǎn)步驟2，若不為目標(biāo)點(diǎn)，則重復(fù)步驟4。

步驟5 結(jié)束算法。

值得說(shuō)明的是，像素值轉(zhuǎn)換因子s的值是像素點(diǎn)對(duì)應(yīng)的像素值是否由轉(zhuǎn)換為的標(biāo)志，算法結(jié)束標(biāo)志t為完整圍線(xiàn)追蹤標(biāo)志。在“尾巴點(diǎn)”區(qū)域，像素點(diǎn)像素值會(huì)轉(zhuǎn)換為，以此為標(biāo)志，追蹤過(guò)程會(huì)逐步回溯，直到找到新的未標(biāo)記的目標(biāo)點(diǎn)，從而跳出“尾巴點(diǎn)”。

2 實(shí)驗(yàn)驗(yàn)證與分析

如圖3所示，約定顏色較深區(qū)域?yàn)槟繕?biāo)區(qū)域，每個(gè)小方格代表一個(gè)單位像素，采用本文提出的基于像素多次標(biāo)記的二值圖像區(qū)域圍線(xiàn)追蹤算法對(duì)圖3中的目標(biāo)區(qū)域進(jìn)行模擬實(shí)驗(yàn)，最終的追蹤圍線(xiàn)為如圖4所示的顏色較深的區(qū)域。表1按照追蹤到目標(biāo)像素點(diǎn)的先后順序給出了圖像坐標(biāo)系下構(gòu)成圍線(xiàn)的像素點(diǎn)坐標(biāo)值以及最終標(biāo)記值。圖5展示了追蹤過(guò)程。

圖 3 模擬實(shí)驗(yàn)圖像Fig.3 Simulated experimental image

圖 4 追蹤結(jié)果示意Fig.4 Diagram of tracking results

圖 5 追蹤過(guò)程示意Fig.5 Diagram of tracing process

表 1 圍線(xiàn)追蹤過(guò)程像素坐標(biāo)與標(biāo)記數(shù)據(jù)表Tab.1 Pixels coordinates and labeled data in contour tracing process

由圖4可以看出，構(gòu)成圍線(xiàn)的像素被成功地追蹤出來(lái)，呈現(xiàn)一條完整圍線(xiàn)。被追蹤到的目標(biāo)像素點(diǎn)分別被標(biāo)記為，和。其中，代表追蹤起始點(diǎn)和結(jié)束點(diǎn)，代表追蹤一次的點(diǎn)，代表追蹤二次的點(diǎn)。由圖4和表1可知，“尾巴點(diǎn)”均被標(biāo)記為，也成功地被找出，且未因“尾巴點(diǎn)”的存在而中斷追蹤。

利用本文算法對(duì)圖3進(jìn)行完整的追蹤過(guò)程總搜索判斷像素點(diǎn)262次，追蹤到有效構(gòu)成圍線(xiàn)像素點(diǎn)42個(gè)，利用文獻(xiàn)[4]進(jìn)行圍線(xiàn)追蹤，當(dāng)追蹤到表1中所示的21號(hào)點(diǎn)時(shí)，便無(wú)法繼續(xù)追蹤，充分說(shuō)明本文算法對(duì)文獻(xiàn)[4]所述算法進(jìn)行了有效的改進(jìn)。

3 結(jié) 論

提出了一種基于像素標(biāo)記的二值圖像區(qū)域圍線(xiàn)追蹤方法。該算法在已有圍線(xiàn)追蹤算法的基礎(chǔ)上，通過(guò)定義特定追蹤方向，使得追蹤過(guò)程始終按照逆時(shí)針或順時(shí)針?lè)较蜓刂B通區(qū)域邊緣進(jìn)行。在追蹤過(guò)程中對(duì)像素點(diǎn)進(jìn)行多次標(biāo)記，通過(guò)在按照追蹤方向確定的像素點(diǎn)基礎(chǔ)上判斷像素標(biāo)記值來(lái)確定下一次待追蹤像素點(diǎn)的選取。提出“尾巴點(diǎn)”的概念，并對(duì)“尾巴點(diǎn)”區(qū)段的一次追蹤和二次追蹤進(jìn)行了有效區(qū)分，解決了追蹤過(guò)程中出現(xiàn)的追蹤間斷現(xiàn)象，使得追蹤結(jié)果呈現(xiàn)一條完整圍線(xiàn)。大量實(shí)驗(yàn)表明，方法可行且可靠，能夠很好地實(shí)現(xiàn)二值圖像目標(biāo)區(qū)域的圍線(xiàn)追蹤。