劉偉學(xué)
(赤峰學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,內(nèi)蒙古 赤峰 024000)
圖像輪廓的點(diǎn)坐標(biāo)的提取方法及VC++編程實(shí)現(xiàn)
劉偉學(xué)
(赤峰學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,內(nèi)蒙古 赤峰 024000)
本文介紹了一種基于位圖圖像輪廓提取與跟蹤的算法原理,提出了基于該原理進(jìn)行提取圖像輪廓的點(diǎn)坐標(biāo)系列的方法,并分析了應(yīng)用該方法可能出現(xiàn)的問題及相應(yīng)的解決辦法,最后給出了該方法的VC++編程實(shí)現(xiàn).
輪廓提??;輪廓跟蹤;點(diǎn)坐標(biāo)
近年來(lái),學(xué)者們提出了許多光柵圖像(以位圖為例,以下稱位圖)矢量化技術(shù)在CAD/CAM系統(tǒng)中的應(yīng)用.如絎縫圖案畫稿自動(dòng)生成系統(tǒng)、刺繡畫稿自動(dòng)生成系統(tǒng)等.位圖矢量化融合了計(jì)算機(jī)圖形學(xué)、數(shù)字圖像處理、模式識(shí)別、軟件設(shè)計(jì)等多學(xué)科的技術(shù).在各種基于位圖圖像輪廓的畫稿自動(dòng)生成系統(tǒng)中,其位圖矢量化的一般處理流程為:除去噪聲,二值化,輪廓提取,矢量輪廓圖形生成.圖像的去噪與二值化方法直接影響后續(xù)處理中的輪廓提取效果的好壞.本文中對(duì)此不作討論,并以經(jīng)過(guò)去噪且以恰當(dāng)閥值分割后的二值圖像作為圖像輪廓提取處理的輸入,探討在此基礎(chǔ)提取輪廓的點(diǎn)坐標(biāo)系列的方法和VC++的編程實(shí)現(xiàn).
輪廓提取的算法非常簡(jiǎn)單,就是掏空內(nèi)部點(diǎn).假設(shè)二值圖像中黑色為目標(biāo),白色為背景,則如果源圖中有一點(diǎn)為黑,且它的8個(gè)相鄰點(diǎn)都是黑色時(shí),此點(diǎn)即為內(nèi)部點(diǎn),應(yīng)將其刪除.因此該算法實(shí)際是對(duì)圖像的各像素進(jìn)行掃描,對(duì)于這里討論的二值圖像來(lái)說(shuō)則只需考慮黑點(diǎn).對(duì)圖像中的每個(gè)圖點(diǎn),考慮其上、下、左、右的八個(gè)鄰點(diǎn),如果其全為黑,則說(shuō)明該點(diǎn)為物體的內(nèi)部點(diǎn),可以去除(變?yōu)楸尘包c(diǎn):白點(diǎn)),否則保留.如果前面的去噪與二值化處理的效果理想的話,該算法提取圖像目標(biāo)輪廓沒有什么問題,這里不作詳細(xì)討論.下面重點(diǎn)討論在經(jīng)過(guò)輪廓提取處理后得到輪廓圖像提取點(diǎn)坐標(biāo)系列的方法.該方法基于邊界跟蹤算法,故下面先對(duì)邊界跟蹤算法作一介紹.
在識(shí)別圖像中的目標(biāo)時(shí),往往需要對(duì)目標(biāo)邊緣作跟蹤處理,也叫輪廓跟蹤.顧名思義,輪廓跟蹤就是通過(guò)順序找出邊緣點(diǎn)來(lái)跟蹤邊界的.若圖像是二值圖像或圖像中不同區(qū)域具有不同的像素值,但每個(gè)區(qū)域內(nèi)的像素值是相同的,則如下算法可完成基于4連通或8連通區(qū)域的輪廓跟蹤.為了敘述問題的方便,假設(shè)待處理圖像為二值輪廓圖像,即背景點(diǎn)為白點(diǎn),輪廓點(diǎn)為黑點(diǎn).對(duì)于不同區(qū)域具有不同像素值的圖像,其處理方法類似,或者可先將其處理為二值圖像再用如下算法進(jìn)行處理.
2.1 按從上到下,從左到右的順序掃描位圖圖像像素矩陣,尋找沒有標(biāo)記跟蹤結(jié)束記號(hào)的第一個(gè)界起始點(diǎn)A0,A0是具有最小行和列值的邊界點(diǎn).注意:此時(shí)的邊界點(diǎn)其實(shí)是圖像的最左下角的邊界點(diǎn).定義一個(gè)掃描方向變量dir,該變量用于記錄上一步中沿著前一個(gè)邊界點(diǎn)到當(dāng)前邊界點(diǎn)的移動(dòng)方向,按上述掃描第一個(gè)邊界點(diǎn)的順序,其初始化取值為:對(duì)4連通區(qū)域取dir=0,如圖 1所示;對(duì) 8連通區(qū)域取dir=7,如圖2所示.
圖1 四連通區(qū)域方向示意圖
圖2 八連通區(qū)域方向示意圖
2.2 按逆時(shí)針方向搜索當(dāng)前像素點(diǎn)的3×3鄰域,如果搜索到邊界點(diǎn)(黑點(diǎn))時(shí),則將該邊界點(diǎn)作為新的當(dāng)前像素點(diǎn),且更改搜索方向,其方法為:對(duì)4連通區(qū)域取(dir-2)mod 4,對(duì)8連通區(qū)域取(dir-2)mod 8;否則以原當(dāng)前像素點(diǎn)為中心逆時(shí)針繼續(xù)搜索,由當(dāng)前搜索方向求下一個(gè)搜索方向的方法為:對(duì)4連通區(qū)域取(dir+1)mod 4,對(duì)8連通區(qū)域取(dir+1)mod 8.
2.3 如果搜索的下一個(gè)像素點(diǎn)等于第一個(gè)邊界點(diǎn)A0或者越界,則停止搜索,結(jié)束跟蹤,否則重復(fù)步驟(2)繼續(xù)搜索.
2.4 由起始邊界點(diǎn)沿著跟蹤路徑再到起始邊界點(diǎn)構(gòu)成的邊界即為要跟蹤的邊界.
其中算法中(1)所采用的準(zhǔn)則稱為“探測(cè)準(zhǔn)則”,其作用是找出第一個(gè)邊界點(diǎn);(3)中所采用的準(zhǔn)則稱為“跟蹤準(zhǔn)則”,其作用是找出所有邊界點(diǎn).
運(yùn)用該跟蹤算法提取圖像輪廓的點(diǎn)坐標(biāo)系列就是要按邊界跟算法中點(diǎn)搜索的順序?qū)⑦吔琰c(diǎn)的坐標(biāo)系列存儲(chǔ)起來(lái).運(yùn)用上述邊界跟蹤算法提取點(diǎn)坐標(biāo)系列還需考慮如下問題:
3.1 完成一次跟蹤只能提取一段邊界.對(duì)于有若干不連續(xù)的邊界,必須重復(fù)跟蹤,而對(duì)于已跟蹤的邊界必須去除.去除的可能辦法有二種:一是邊跟蹤邊去除,二是跟蹤完一段后再一起去除.實(shí)驗(yàn)中發(fā)現(xiàn)第一種方法不可行,其原因是在邊跟蹤邊去除邊界點(diǎn)時(shí),無(wú)法滿足上述算法中(3)所述搜索終止條件.故宜采用第二種方法.
3.2 對(duì)于跟蹤的邊界點(diǎn)坐標(biāo)須用一點(diǎn)坐標(biāo)數(shù)組存儲(chǔ)起來(lái),點(diǎn)坐標(biāo)系列順序按跟蹤順序保存,這一順序即是將邊界圖像矢量化為矢量圖元的順序.
3.3 邊界點(diǎn)坐標(biāo)的數(shù)據(jù)結(jié)構(gòu).因?yàn)檫吔鐖D像可能有若干不連續(xù)邊界,故記錄這些不連續(xù)的邊界點(diǎn)坐標(biāo)通常有兩種方法.一是采用鏈表的形式,鏈中每一結(jié)點(diǎn)兩個(gè)字段:一個(gè)邊界段的點(diǎn)坐標(biāo)數(shù)組及該邊界段的點(diǎn)數(shù)組成的結(jié)構(gòu)體,指向下一個(gè)結(jié)點(diǎn)的指針.二是用線性表的形式,一個(gè)點(diǎn)坐標(biāo)數(shù)組存儲(chǔ)所有邊界點(diǎn)的坐標(biāo),另用一個(gè)結(jié)構(gòu)體記錄邊界點(diǎn)總點(diǎn)數(shù),總段數(shù)及每段的坐標(biāo)點(diǎn)數(shù).對(duì)于這兩種數(shù)據(jù)結(jié)構(gòu)的選擇取決于邊界圖像是否為最終目標(biāo)圖像邊界,如是,則采用線性表的形式處理更容易;如不是,即后續(xù)處理中還需對(duì)邊界進(jìn)行修正,則采用鏈表的形式處理更方便.
3.4 對(duì)于非常少的點(diǎn)數(shù)的邊界段的處理問題.通常這類邊界往往是噪聲形成的,應(yīng)該在處理中去除.但也不盡然,在細(xì)節(jié)較為豐富的邊界圖像中,可能這些較少點(diǎn)數(shù)的邊界段也是有用信息.故實(shí)驗(yàn)中采取人機(jī)交互的辦法.通過(guò)對(duì)話框讓用戶根據(jù)不同特征的邊界圖像提供一個(gè)臨界值來(lái)確定多少個(gè)點(diǎn)數(shù)組成的邊界為噪聲.
3.5 對(duì)確定為噪聲的邊界段去除辦法.應(yīng)根據(jù)邊界點(diǎn)的數(shù)據(jù)結(jié)構(gòu)作相應(yīng)處理.
輪廓跟蹤提取邊界點(diǎn)坐標(biāo)系列的算法函數(shù)TraceDIB()原型如下:
下面對(duì)其作簡(jiǎn)要說(shuō)明.CsplitProc為類名,TraceDIB為該類的成員函數(shù),函數(shù)輸入為二值圖像的句柄,輸出有:輪廓總點(diǎn)數(shù),總段數(shù),輪廓點(diǎn)坐標(biāo)以及各段點(diǎn)數(shù).函數(shù)參數(shù)說(shuō)明:hDIB為待處理的圖像句柄,由此可訪問到圖像中各像素的灰度值;dwCountPints為圖像輪廓的點(diǎn)數(shù),為引用型變量,函數(shù)中對(duì)此變量的修改即是對(duì)所引用的變量的修改;dw-CountSg為圖像的輪廓的段數(shù)(這里把根據(jù)上述輪廓跟蹤算法結(jié)束時(shí)得到的輪廓段稱為一段),也采用引用型變量,其含義同上;lpPoints為指向點(diǎn)坐標(biāo)數(shù)組的指針,為指針型變量,函數(shù)中通過(guò)該指針即可訪問到存放點(diǎn)坐標(biāo)的數(shù)組;lpSg-Points為指向存放各段點(diǎn)數(shù)的雙字型數(shù)組,函數(shù)中通過(guò)該指針可訪問到存放各段點(diǎn)數(shù)的數(shù)組.函數(shù)實(shí)現(xiàn)方法簡(jiǎn)述如下:按上述輪廓跟蹤算法不斷跟蹤圖像輪廓:每跟蹤到一個(gè)點(diǎn)時(shí),記錄該點(diǎn)坐標(biāo),輪廓點(diǎn)數(shù)增1;每跟蹤完一段后,段數(shù)增1,數(shù)并記錄該段的點(diǎn)數(shù);直到所有輪廓點(diǎn)跟蹤完畢.為了在輪廓跟蹤過(guò)程中對(duì)某些少數(shù)點(diǎn)組成的圖段(可能為噪聲)去除,可在處理時(shí)提供對(duì)話框由用戶設(shè)定噪聲邊界點(diǎn)數(shù)的臨界值,這樣既可去除噪聲,又不至于將有用的細(xì)節(jié)丟失.如圖3所示的源圖像,經(jīng)過(guò)該函數(shù)處理后,將其邊界點(diǎn)坐標(biāo)系列信息保存于文件中,將其重新繪制得到的邊界圖形如圖4所示.可見源圖像的噪聲得到了去除,但同時(shí)也損失了一些邊界細(xì)節(jié).此時(shí)的噪聲邊界點(diǎn)數(shù)臨界值為100,適當(dāng)修改該值,可得到不同的處理效果.
圖3 待處理的含有噪聲的輪廓圖
圖4 提取輪廓點(diǎn)坐標(biāo)后重新繪制圖形
上述運(yùn)用輪廓跟蹤提取邊界點(diǎn)坐標(biāo)系列的方法通過(guò)實(shí)驗(yàn)表明在一定條件下是可行的.對(duì)于噪聲與圖像有用邊界很分明的圖像去噪效果很好,但對(duì)于圖像細(xì)節(jié)與噪聲難以分辨的圖像去噪與保留細(xì)節(jié)是一對(duì)矛盾.對(duì)于邊界中無(wú)交叉的情況提取點(diǎn)坐標(biāo)系列無(wú)重復(fù)邊界點(diǎn),否則按此邊界搜索算法將會(huì)有重復(fù)邊界點(diǎn).以上問題仍需進(jìn)一步研究,如采用人工交互的辦法去除噪聲點(diǎn),對(duì)有交叉點(diǎn)的邊界應(yīng)予以特殊處理,去除重復(fù)邊界點(diǎn)等.
〔1〕高守傳.VisualC++實(shí)踐與提高-數(shù)字圖像處理與工程應(yīng)用篇[M].中國(guó)鐵道出版社,2006.
〔2〕余學(xué)軍,彭立中.二值圖像曲線輪廓提取的新算法[J].中國(guó)圖像圖形學(xué)報(bào),2002(3).
〔3〕孫景榮,許錄平.一種改進(jìn)的圖形矢量化方法[J].計(jì)算機(jī)工程及應(yīng)用,2004(1).
〔4〕劉安心,余躍慶,等.三維機(jī)器視覺測(cè)量系統(tǒng)圖像邊緣提取算法研究 [J].機(jī)械制造與自動(dòng)化,2006,35(1):101-103,106.
TP39
A
1673-260X(2011)03-0039-02