劉偉學(xué)

（赤峰學(xué)院 計算機科學(xué)與技術(shù)系，內(nèi)蒙古 赤峰 024000）

圖像輪廓的點坐標(biāo)的提取方法及VC++編程實現(xiàn)

劉偉學(xué)

（赤峰學(xué)院 計算機科學(xué)與技術(shù)系，內(nèi)蒙古 赤峰 024000）

本文介紹了一種基于位圖圖像輪廓提取與跟蹤的算法原理，提出了基于該原理進行提取圖像輪廓的點坐標(biāo)系列的方法，并分析了應(yīng)用該方法可能出現(xiàn)的問題及相應(yīng)的解決辦法，最后給出了該方法的VC++編程實現(xiàn).

輪廓提??；輪廓跟蹤；點坐標(biāo)

1 引言

近年來，學(xué)者們提出了許多光柵圖像（以位圖為例，以下稱位圖）矢量化技術(shù)在CAD/CAM系統(tǒng)中的應(yīng)用.如絎縫圖案畫稿自動生成系統(tǒng)、刺繡畫稿自動生成系統(tǒng)等.位圖矢量化融合了計算機圖形學(xué)、數(shù)字圖像處理、模式識別、軟件設(shè)計等多學(xué)科的技術(shù).在各種基于位圖圖像輪廓的畫稿自動生成系統(tǒng)中，其位圖矢量化的一般處理流程為：除去噪聲，二值化，輪廓提取，矢量輪廓圖形生成.圖像的去噪與二值化方法直接影響后續(xù)處理中的輪廓提取效果的好壞.本文中對此不作討論，并以經(jīng)過去噪且以恰當(dāng)閥值分割后的二值圖像作為圖像輪廓提取處理的輸入，探討在此基礎(chǔ)提取輪廓的點坐標(biāo)系列的方法和VC++的編程實現(xiàn).

2 輪廓提取與跟蹤的基本原理

輪廓提取的算法非常簡單，就是掏空內(nèi)部點.假設(shè)二值圖像中黑色為目標(biāo)，白色為背景，則如果源圖中有一點為黑，且它的8個相鄰點都是黑色時，此點即為內(nèi)部點，應(yīng)將其刪除.因此該算法實際是對圖像的各像素進行掃描，對于這里討論的二值圖像來說則只需考慮黑點.對圖像中的每個圖點，考慮其上、下、左、右的八個鄰點，如果其全為黑，則說明該點為物體的內(nèi)部點，可以去除（變?yōu)楸尘包c：白點），否則保留.如果前面的去噪與二值化處理的效果理想的話，該算法提取圖像目標(biāo)輪廓沒有什么問題，這里不作詳細(xì)討論.下面重點討論在經(jīng)過輪廓提取處理后得到輪廓圖像提取點坐標(biāo)系列的方法.該方法基于邊界跟蹤算法，故下面先對邊界跟蹤算法作一介紹.

在識別圖像中的目標(biāo)時，往往需要對目標(biāo)邊緣作跟蹤處理，也叫輪廓跟蹤.顧名思義，輪廓跟蹤就是通過順序找出邊緣點來跟蹤邊界的.若圖像是二值圖像或圖像中不同區(qū)域具有不同的像素值，但每個區(qū)域內(nèi)的像素值是相同的，則如下算法可完成基于4連通或8連通區(qū)域的輪廓跟蹤.為了敘述問題的方便，假設(shè)待處理圖像為二值輪廓圖像，即背景點為白點，輪廓點為黑點.對于不同區(qū)域具有不同像素值的圖像，其處理方法類似，或者可先將其處理為二值圖像再用如下算法進行處理.

2.1 按從上到下，從左到右的順序掃描位圖圖像像素矩陣，尋找沒有標(biāo)記跟蹤結(jié)束記號的第一個界起始點A0,A0是具有最小行和列值的邊界點.注意：此時的邊界點其實是圖像的最左下角的邊界點.定義一個掃描方向變量dir,該變量用于記錄上一步中沿著前一個邊界點到當(dāng)前邊界點的移動方向，按上述掃描第一個邊界點的順序，其初始化取值為：對4連通區(qū)域取dir=0,如圖 1所示；對 8連通區(qū)域取dir=7,如圖2所示.

圖1 四連通區(qū)域方向示意圖

圖2 八連通區(qū)域方向示意圖

2.2 按逆時針方向搜索當(dāng)前像素點的3×3鄰域，如果搜索到邊界點（黑點）時，則將該邊界點作為新的當(dāng)前像素點，且更改搜索方向，其方法為：對4連通區(qū)域取(dir-2)mod 4,對8連通區(qū)域取(dir-2)mod 8；否則以原當(dāng)前像素點為中心逆時針繼續(xù)搜索，由當(dāng)前搜索方向求下一個搜索方向的方法為：對4連通區(qū)域取(dir+1)mod 4,對8連通區(qū)域取(dir+1)mod 8.

2.3 如果搜索的下一個像素點等于第一個邊界點A0或者越界，則停止搜索，結(jié)束跟蹤，否則重復(fù)步驟(2)繼續(xù)搜索.

2.4 由起始邊界點沿著跟蹤路徑再到起始邊界點構(gòu)成的邊界即為要跟蹤的邊界.

其中算法中（1）所采用的準(zhǔn)則稱為“探測準(zhǔn)則”，其作用是找出第一個邊界點；(3)中所采用的準(zhǔn)則稱為“跟蹤準(zhǔn)則”，其作用是找出所有邊界點.

3 圖像輪廓的點坐標(biāo)系列的提取方法

運用該跟蹤算法提取圖像輪廓的點坐標(biāo)系列就是要按邊界跟算法中點搜索的順序?qū)⑦吔琰c的坐標(biāo)系列存儲起來.運用上述邊界跟蹤算法提取點坐標(biāo)系列還需考慮如下問題：

3.1 完成一次跟蹤只能提取一段邊界.對于有若干不連續(xù)的邊界，必須重復(fù)跟蹤，而對于已跟蹤的邊界必須去除.去除的可能辦法有二種：一是邊跟蹤邊去除，二是跟蹤完一段后再一起去除.實驗中發(fā)現(xiàn)第一種方法不可行，其原因是在邊跟蹤邊去除邊界點時，無法滿足上述算法中（3）所述搜索終止條件.故宜采用第二種方法.

3.2 對于跟蹤的邊界點坐標(biāo)須用一點坐標(biāo)數(shù)組存儲起來，點坐標(biāo)系列順序按跟蹤順序保存，這一順序即是將邊界圖像矢量化為矢量圖元的順序.

3.3 邊界點坐標(biāo)的數(shù)據(jù)結(jié)構(gòu).因為邊界圖像可能有若干不連續(xù)邊界，故記錄這些不連續(xù)的邊界點坐標(biāo)通常有兩種方法.一是采用鏈表的形式，鏈中每一結(jié)點兩個字段：一個邊界段的點坐標(biāo)數(shù)組及該邊界段的點數(shù)組成的結(jié)構(gòu)體，指向下一個結(jié)點的指針.二是用線性表的形式，一個點坐標(biāo)數(shù)組存儲所有邊界點的坐標(biāo)，另用一個結(jié)構(gòu)體記錄邊界點總點數(shù)，總段數(shù)及每段的坐標(biāo)點數(shù).對于這兩種數(shù)據(jù)結(jié)構(gòu)的選擇取決于邊界圖像是否為最終目標(biāo)圖像邊界，如是，則采用線性表的形式處理更容易；如不是，即后續(xù)處理中還需對邊界進行修正，則采用鏈表的形式處理更方便.

3.4 對于非常少的點數(shù)的邊界段的處理問題.通常這類邊界往往是噪聲形成的，應(yīng)該在處理中去除.但也不盡然，在細(xì)節(jié)較為豐富的邊界圖像中，可能這些較少點數(shù)的邊界段也是有用信息.故實驗中采取人機交互的辦法.通過對話框讓用戶根據(jù)不同特征的邊界圖像提供一個臨界值來確定多少個點數(shù)組成的邊界為噪聲.

3.5 對確定為噪聲的邊界段去除辦法.應(yīng)根據(jù)邊界點的數(shù)據(jù)結(jié)構(gòu)作相應(yīng)處理.

4 VC++程序?qū)崿F(xiàn)

輪廓跟蹤提取邊界點坐標(biāo)系列的算法函數(shù)TraceDIB()原型如下：

下面對其作簡要說明.CsplitProc為類名，TraceDIB為該類的成員函數(shù)，函數(shù)輸入為二值圖像的句柄，輸出有：輪廓總點數(shù)，總段數(shù)，輪廓點坐標(biāo)以及各段點數(shù).函數(shù)參數(shù)說明：hDIB為待處理的圖像句柄，由此可訪問到圖像中各像素的灰度值；dwCountPints為圖像輪廓的點數(shù)，為引用型變量，函數(shù)中對此變量的修改即是對所引用的變量的修改；dw-CountSg為圖像的輪廓的段數(shù)（這里把根據(jù)上述輪廓跟蹤算法結(jié)束時得到的輪廓段稱為一段），也采用引用型變量，其含義同上；lpPoints為指向點坐標(biāo)數(shù)組的指針，為指針型變量，函數(shù)中通過該指針即可訪問到存放點坐標(biāo)的數(shù)組；lpSg-Points為指向存放各段點數(shù)的雙字型數(shù)組，函數(shù)中通過該指針可訪問到存放各段點數(shù)的數(shù)組.函數(shù)實現(xiàn)方法簡述如下：按上述輪廓跟蹤算法不斷跟蹤圖像輪廓：每跟蹤到一個點時，記錄該點坐標(biāo)，輪廓點數(shù)增1；每跟蹤完一段后，段數(shù)增1，數(shù)并記錄該段的點數(shù)；直到所有輪廓點跟蹤完畢.為了在輪廓跟蹤過程中對某些少數(shù)點組成的圖段（可能為噪聲）去除，可在處理時提供對話框由用戶設(shè)定噪聲邊界點數(shù)的臨界值，這樣既可去除噪聲，又不至于將有用的細(xì)節(jié)丟失.如圖3所示的源圖像，經(jīng)過該函數(shù)處理后，將其邊界點坐標(biāo)系列信息保存于文件中，將其重新繪制得到的邊界圖形如圖4所示.可見源圖像的噪聲得到了去除，但同時也損失了一些邊界細(xì)節(jié).此時的噪聲邊界點數(shù)臨界值為100，適當(dāng)修改該值，可得到不同的處理效果.

圖3 待處理的含有噪聲的輪廓圖

圖4 提取輪廓點坐標(biāo)后重新繪制圖形

4 結(jié)論與展望

上述運用輪廓跟蹤提取邊界點坐標(biāo)系列的方法通過實驗表明在一定條件下是可行的.對于噪聲與圖像有用邊界很分明的圖像去噪效果很好，但對于圖像細(xì)節(jié)與噪聲難以分辨的圖像去噪與保留細(xì)節(jié)是一對矛盾.對于邊界中無交叉的情況提取點坐標(biāo)系列無重復(fù)邊界點，否則按此邊界搜索算法將會有重復(fù)邊界點.以上問題仍需進一步研究，如采用人工交互的辦法去除噪聲點，對有交叉點的邊界應(yīng)予以特殊處理，去除重復(fù)邊界點等.

〔1〕高守傳.VisualC++實踐與提高－數(shù)字圖像處理與工程應(yīng)用篇[M].中國鐵道出版社,2006.

〔2〕余學(xué)軍，彭立中.二值圖像曲線輪廓提取的新算法[J].中國圖像圖形學(xué)報，2002（3）.

〔3〕孫景榮，許錄平.一種改進的圖形矢量化方法[J].計算機工程及應(yīng)用，2004（1）.

〔4〕劉安心，余躍慶，等.三維機器視覺測量系統(tǒng)圖像邊緣提取算法研究 [J].機械制造與自動化，2006，35(1)：101-103,106.

TP39

A

1673-260X（2011）03-0039-02