采用行程跟蹤的二值圖像去毛刺算法

鐘倫超， 何 川

(1.黃山學(xué)院 教務(wù)處，安徽 黃山 245041；2.黃山學(xué)院 信息工程學(xué)院，安徽 黃山 245041)

自1967年Blum提出骨架的概念以來，曲線骨架提取成為多領(lǐng)域研究的熱點(diǎn)。例如指紋識別方法通常是在對原始圖像進(jìn)行一系列預(yù)處理之后，利用細(xì)化處理得到圖像骨架，然后進(jìn)一步運(yùn)用其中的細(xì)節(jié)特征點(diǎn)（起點(diǎn)、終點(diǎn)、結(jié)合點(diǎn)和分叉點(diǎn)）進(jìn)行指紋鑒別。二值圖像細(xì)線化技術(shù)在圖像分析與形狀描述中是一個(gè)非常重要的變換，骨架是圖像幾何形態(tài)的重要拓?fù)涿枋?，是進(jìn)行圖像目標(biāo)的特征提取[1]、模式識別[2]等應(yīng)用的前提，在很多研究領(lǐng)域及生產(chǎn)生活中應(yīng)用廣泛，主要用于字符識別[3]、指紋識別[4]、工程零件骨架結(jié)構(gòu)識別提取[5]等，通過圖像的細(xì)化處理將圖像中的需要識別的部分進(jìn)行細(xì)化，可以很清晰地得到需要的圖像“骨架”，提取出所需目標(biāo)物的單像素輪廓。但是，圖像細(xì)線化帶來的問題是處理后的圖像在此“骨架”的線段分段處產(chǎn)生多余的點(diǎn)和線段，我們把這些多余的點(diǎn)和線稱為“毛刺”[6-8]。

毛刺在圖像中是多余的，并且會(huì)影響圖像主要部分的使用。針對去毛刺過程可能存在去除圖像結(jié)構(gòu)主體部分的缺陷，寧亞輝等人提出改進(jìn)的基于模板去除骨架毛刺方法[9]。該方法首先對目標(biāo)點(diǎn)周圍像素進(jìn)行統(tǒng)計(jì)，找到對應(yīng)像素符合的類型，再結(jié)合傳統(tǒng)去毛刺方法中的毛刺長度設(shè)定，對毛刺進(jìn)行去除。郭斯羽等人提出一種植物葉片圖像骨架提取的去毛刺方法[10]，通過設(shè)定的兩個(gè)指標(biāo)對骨架上的毛刺進(jìn)行判斷和去除。安世全等人提出一種基于Zhang并行細(xì)化算法進(jìn)行細(xì)化，在其基礎(chǔ)上通過改進(jìn)的毛刺消除算法滿足保留較長分支為骨架主體信息的原則，最大程度地保持裂縫骨架主體信息[11]。實(shí)驗(yàn)結(jié)果表明上述文獻(xiàn)提出的方法都可以減少圖像噪聲和毛刺，但是無法保證圖像的有效部分的完整性。通過大量的實(shí)驗(yàn)程序編寫及測試，提出去毛刺算法，針對毛刺的存在問題，利用細(xì)化圖像中的交叉點(diǎn)和端點(diǎn)來確定毛刺的位置，通過端點(diǎn)對交叉點(diǎn)進(jìn)行搜索，存儲搜索路徑，記錄該跟蹤路徑的方向鏈碼，通過設(shè)定毛刺長度門限值對毛刺部分進(jìn)行去除，得到效果滿意的細(xì)化圖像。

1 去毛刺算法描述

基于行程跟蹤的去毛刺算法，實(shí)質(zhì)上就是對目標(biāo)像素的鄰近像素進(jìn)行掃描，以目標(biāo)像素為起始點(diǎn)對毛刺部分進(jìn)行追蹤，通過事先設(shè)定好的長度門限，定義毛刺的長度，判斷毛刺位置，從而進(jìn)行有效去除。通過對毛刺的特性進(jìn)行分析，可以得出毛刺介于交叉點(diǎn)和端點(diǎn)之間，掃描毛刺的方式有兩種：（1）以端點(diǎn)作為起始點(diǎn)，通過行程跟蹤在其設(shè)定長度門限范圍內(nèi)尋找交叉點(diǎn)，定義毛刺長度，從而找出毛刺所在；（2）以交叉點(diǎn)為起始點(diǎn)，對其連通域內(nèi)的8-鄰域像素進(jìn)行像素值判斷，并通過路徑跟蹤以及毛刺長度，判斷出毛刺位置。本文僅詳細(xì)介紹以端點(diǎn)為起始點(diǎn)尋找其連通域內(nèi)的交叉點(diǎn)，進(jìn)行毛刺的檢測和標(biāo)記存儲并有效去除。

算法步驟：首先判斷給定的圖像是否為二值圖像，如果不是，對原圖像進(jìn)行二值化處理，此時(shí)的圖像可能存在很多噪聲點(diǎn)，對圖像進(jìn)行去噪及一系列形態(tài)學(xué)預(yù)處理，然后對給定進(jìn)行細(xì)線化操作，得到初步的圖像目標(biāo)物骨架，細(xì)線化處理的圖像會(huì)產(chǎn)生很明顯的毛刺現(xiàn)象。通過行程跟蹤對毛刺像素進(jìn)行檢測和標(biāo)記存儲，再對其進(jìn)行有效去除，得到輪廓光滑且目標(biāo)物結(jié)構(gòu)不變的新圖像。

（1）對原圖進(jìn)行去噪等預(yù)處理，采用MATLAB軟件自帶的二值化函數(shù)對給定圖像進(jìn)行二值化處理，得到二值圖像；

（2）對得到的二值圖像進(jìn)行細(xì)線化處理，得到像素寬度為1的目標(biāo)物輪廓圖，從而提取出圖像目標(biāo)物特征骨架；

（3）通過掃描，尋找到圖像中所有的端點(diǎn)和交叉點(diǎn)，對端點(diǎn)和交叉點(diǎn)進(jìn)行標(biāo)記并存儲，設(shè)定毛刺長度門限值L，以端點(diǎn)為起始點(diǎn)在其連通域內(nèi)進(jìn)行目標(biāo)物行程跟蹤，直到尋找到交叉點(diǎn)，終止運(yùn)算，存儲行程中的每一個(gè)像素點(diǎn)。如果跟蹤的步數(shù)M小于設(shè)定的毛刺門限值L，則該段路徑為毛刺；反之，跟蹤步數(shù)大于設(shè)定的毛刺長度L，則默認(rèn)該段路徑為圖像的有效結(jié)構(gòu)；

（4）通過步驟（3）確定毛刺后，根據(jù)行程跟蹤過程中存儲起來的像素點(diǎn)，將符合毛刺定義的端點(diǎn)和其對應(yīng)的交叉點(diǎn)之間的像素去除；

（5）得到清晰的圖像骨架，結(jié)束運(yùn)算。

算法流程如圖1所示。

圖1 去毛刺算法流程圖Fig.1 Flow chart of deburring algorithm

2 二值圖像轉(zhuǎn)換及圖像骨架的提取

采用MATLAB R2015a軟件DIP工具箱函數(shù)im2bw使用閾值變換法把灰度圖像轉(zhuǎn)換成二值圖像：

式中：I為原圖像；J為轉(zhuǎn)化后的二值圖像。

隨即采用bwmorph函數(shù)對原二值圖像進(jìn)行細(xì)線化處理，提取圖像中目標(biāo)物的骨架：

式中：J為二值圖像；運(yùn)算次數(shù)n為12；H為骨架圖像。

3 毛刺的定義

3.1 端點(diǎn)、交叉點(diǎn)及毛刺模型

為了確定細(xì)線化所引起的毛刺的位置所在，需要先找到產(chǎn)生毛刺的根源，即交叉點(diǎn)和端點(diǎn)。不難發(fā)現(xiàn)，毛刺一定是始于交叉點(diǎn)且止于端點(diǎn)，存在于端點(diǎn)和交叉點(diǎn)之間。如圖2所示，對端點(diǎn)、交叉點(diǎn)和毛刺作形象說明。

圖2 端點(diǎn)、交叉點(diǎn)和毛刺示意圖Fig.2 Diagram of endpoints,intersections and burrs

圖中，可以看到A點(diǎn)和B點(diǎn)處在交叉位置，則定義A點(diǎn)和B點(diǎn)為交叉點(diǎn)，C、D、E3點(diǎn)為端點(diǎn)，從圖中可以看出，毛刺存在于端點(diǎn)和交叉點(diǎn)之間，則a、b、c3段都有可能是毛刺，但是考慮到有些毛刺可能是圖像的有效部分，不可去除，例如c段。因此，我們需要設(shè)置毛刺的長度，合理地對毛刺進(jìn)行去除，保留圖像的有效部分。

3.2 端點(diǎn)、交叉點(diǎn)標(biāo)記及存儲

3.2.1 端點(diǎn)

規(guī)定目標(biāo)像素為黑色，像素值為1，背景色像素值為0。設(shè)N8(P0)為P0的8個(gè)鄰域中數(shù)值為1的像素個(gè)數(shù)。當(dāng)P0=1，N8(P0)=1，即目標(biāo)像素為黑色，它的8個(gè)鄰域中僅有1個(gè)點(diǎn)為黑色，則P0為端點(diǎn)，如圖3所示，P0為掃描到的目標(biāo)像素。當(dāng)P0的3×3鄰域滿足(a)～(h)8種情形中的任意一種時(shí)，則P0為端點(diǎn)。此時(shí)我們對P0點(diǎn)進(jìn)行標(biāo)記并存儲。

圖3 滿足端點(diǎn)性質(zhì)的P0鄰域像素分布Fig.3 The P0 Neighborhood pixel distribution satisfying the endpoint property

3.2.2 交叉點(diǎn)

如果當(dāng)前掃描到的目標(biāo)像素P0，像素值為1，我們定義，當(dāng)P0=1，3＜N8(P0)時(shí)，該點(diǎn)為交叉點(diǎn)。我們可以從圖5看出，如果P0點(diǎn)的8-鄰域中僅有兩個(gè)點(diǎn)像素值為1，則該點(diǎn)為線段中一點(diǎn)，不能視為交叉點(diǎn)。當(dāng)P0點(diǎn)的8-鄰域中有三個(gè)或超過三個(gè)點(diǎn)像素值為1，則該點(diǎn)為交叉點(diǎn)，即為毛刺產(chǎn)生點(diǎn)。如圖4為文字識別細(xì)線化的圖像，可以看出，該圖中有6處交叉點(diǎn)。標(biāo)記所有的交叉點(diǎn)，并進(jìn)行存儲。

圖4 交叉點(diǎn)示意圖Fig.4 Cross point diagram

3.3 毛刺定義

通過大量研究可知，毛刺必然存在于端點(diǎn)和交叉點(diǎn)之間，因此，對端點(diǎn)和交叉點(diǎn)進(jìn)行標(biāo)記和存儲，并對每個(gè)端點(diǎn)和對應(yīng)的交叉點(diǎn)進(jìn)行編號，使得從某一端點(diǎn)進(jìn)行行程跟蹤后，對其連通域內(nèi)尋找到的交叉點(diǎn)進(jìn)行對應(yīng)，確定毛刺的位置，但是并不是所有的端點(diǎn)和交叉點(diǎn)之間的線段都是毛刺，我們通過限制毛刺長度門限來定義毛刺，確保圖像有效部分不被剔除。

4 基于行程跟蹤的毛刺去除

4.1 行程跟蹤

掃描全圖，以掃描到的端點(diǎn)P0為起始點(diǎn)，跟蹤P0的8-鄰域，如果掃描到黑色點(diǎn)，則將該黑點(diǎn)存儲起來，再以該黑點(diǎn)為起始點(diǎn)進(jìn)行掃描，則繼續(xù)掃描如圖5所示，圖(b)為圖(a)的部分像素分布圖。

圖5 毛刺像素分布示意圖Fig.5 Schematic of burr pixel distribution

圖為8×8的區(qū)域，0代表黑色像素點(diǎn)，1代表白色像素點(diǎn)，跟蹤示意圖如框圖6所示。（1）從端點(diǎn)（2,2）開始搜索，根據(jù)交叉點(diǎn)定義，（4,4）點(diǎn)為交叉點(diǎn)，結(jié)束運(yùn)算，該段路徑可能為毛刺；（2）從端點(diǎn)（2,7）開始搜索，直到交叉點(diǎn)（4,5）結(jié)束搜索，該段路徑也可能為毛刺。（3）存儲兩段路徑的所有有效點(diǎn)。

圖6 毛刺跟蹤流程圖Fig.6 Flow chart of burr tracking

4.2 毛刺去除

設(shè)定毛刺長度門限值L，標(biāo)記存儲細(xì)線化圖像的所有端點(diǎn)及交叉點(diǎn)，其次判斷P0點(diǎn)的8-鄰域像素值為1的個(gè)數(shù)：如果N8(P0)=0，則該點(diǎn)為孤立點(diǎn)，結(jié)束運(yùn)算；如果N8(P0)=1，則P0為端點(diǎn)，進(jìn)行跟蹤，此時(shí)步數(shù)M=1，M=M+1，再以P0的8-鄰域內(nèi)的點(diǎn)作為起始點(diǎn)，進(jìn)行跟蹤，直至尋找到起始點(diǎn)連通域內(nèi)的交叉點(diǎn)，結(jié)束運(yùn)算。若M＞L,即搜索路徑長度大于毛刺長度門限值，停止運(yùn)算；若M＜L，直至找到最近的交叉點(diǎn)。此時(shí)將存儲的起始點(diǎn)與尋找到的交叉點(diǎn)一一配對；如果搜索步數(shù)小于L，則該段路徑為毛刺，去除端點(diǎn)和對應(yīng)的交叉點(diǎn)之間的像素；反之，該段路徑為圖像有效結(jié)構(gòu)，不做處理。

4.3 實(shí)驗(yàn)過程分析

如圖7(a)為一張簡單的線段圖，通過此圖像的操作來體現(xiàn)文中算法的處理結(jié)果。利用細(xì)線化技術(shù)對其進(jìn)行骨架圖像提取，圖7(b)為細(xì)線化帶有毛刺的圖像，此時(shí)，標(biāo)記存儲圖(b)中所有的交叉點(diǎn)和端點(diǎn)，如圖(c)(d)分別為提取的交叉點(diǎn)和端點(diǎn)，通過以端點(diǎn)為起始點(diǎn)搜尋其連通域內(nèi)的交叉點(diǎn)，并存儲搜索路徑中所有的白色像素，通過路徑步長M和定義的毛刺長度L進(jìn)行比較，去除符合毛刺定義的路徑內(nèi)的所有像素即可，毛刺處理效果如圖7(e)所示。

圖7 行程跟蹤去毛刺算法處理效果Fig.7 Processing effect of stroke tracking deburring Algorithm

5 實(shí)驗(yàn)結(jié)果仿真與分析

為了更好地驗(yàn)證基于行程跟蹤的去毛刺算法在實(shí)際應(yīng)用中的效果，以車牌骨架提取和文字骨架提取為例，對處理前后的圖像進(jìn)行對比，分析去毛刺算法的特點(diǎn)和優(yōu)勢。

圖8(a)為車牌的原始彩色圖像；圖8(b)為車牌二值化并取反的圖像；圖8(c)為二值圖像的細(xì)線化處理圖像，可以清晰的看出，圖像中出現(xiàn)了很多影響圖像美觀的毛刺，這些毛刺有的存在于線段中部，有的存在于線段尾部，這兩種情況的毛刺都是產(chǎn)生于交叉點(diǎn)，結(jié)束于端點(diǎn)；圖8(d)為本文算法處理的結(jié)果，通過與圖(c)進(jìn)行比較，我們可以得出，本文基于行程跟蹤的去毛刺算法對處理細(xì)化圖像中的毛刺有著明顯的效果。

圖8 車牌骨架提取去毛刺效果圖Fig.8 The deburring effect diagram of license plate skeleton extraction

圖9為文字骨架提取過程中毛刺去除過程。圖9(a)為漢字“中國”二值化后的圖像；圖9(b)為車牌細(xì)線化處理圖像，處理結(jié)果帶來了很多毛刺；圖9(c)為本文算法處理的結(jié)果，毛刺被有效去除。通過實(shí)驗(yàn)結(jié)果可以看出，“國”字右下角延伸出來的“橫”并沒有被當(dāng)成毛刺去除，可見本文算法有效保證了圖像的骨架完整性。

圖9 文字骨架提取去毛刺效果圖Fig.9 Image of text skeleton extraction deburring

圖8(d)和圖9(c)的實(shí)驗(yàn)結(jié)果是在Intel(R)Pentium(R)CPU G2030(3.00 GHz)、內(nèi)存4G的微機(jī)上采用MATLAB R2016b軟件編程實(shí)現(xiàn)的，算法運(yùn)行時(shí)間分別為643和596 ms，完全滿足圖像處理在實(shí)際應(yīng)用中的時(shí)間要求。

6 結(jié)束語

二值圖像細(xì)線化算法應(yīng)用廣泛，其運(yùn)算結(jié)果不可避免會(huì)產(chǎn)生影響圖像質(zhì)量的毛刺。本文提出基于毛刺行程跟蹤的去毛刺算法，通過分析毛刺的規(guī)律、特點(diǎn)、性質(zhì)，運(yùn)用交叉點(diǎn)和端點(diǎn)定位毛刺，對細(xì)線化圖像中毛刺的有效去除。該算法能夠在不改變圖像連通性條件下，保持圖像有效部分的基本骨架，同時(shí)有效去除二值圖像細(xì)線化處理帶來的毛刺，改善了圖像視覺質(zhì)量。