余 樑 王廣偉

（浙江海洋學(xué)院數(shù)理信息學(xué)院 浙江 舟山 316000）

0 引言

在圖像處理領(lǐng)域，處理大量的圖像信息之前，往往需要對圖像進(jìn)行預(yù)處理，以便于后面的圖像分析、圖形理解和圖形特征提取等。圖像細(xì)化就是對于圖像預(yù)處理方法的一種，特別在文字識別、指紋識別與圖像理解中，對圖像進(jìn)行細(xì)化有效的提高了處理效率，減少數(shù)據(jù)冗余。

1 像的細(xì)化分析

圖像的細(xì)化主要是針對二值圖而言，對圖像的細(xì)化過程實際上是求該圖像骨架的過程。所謂的骨架，可以理解為圖像的中軸：長方形的骨架，是長方向的中線；圓形的骨架，是圓心這一點。

常用的細(xì)化算法有查表細(xì)化和逐層剝?nèi)〖?xì)化。

查表細(xì)化是建立一個公認(rèn)合理的索引表。規(guī)定黑色值1，白色值0；從上到下，從左到右依次逐個判斷每一個點，碰到當(dāng)前點為黑色，然后通過公式（圖 1），計算出當(dāng)前點的值，所得的值對照索引表（圖2）中值，若deletemark=0，該點刪除，deletemark=1，該點保留為黑色。反復(fù)掃描直到不再變化。

圖1 公式規(guī)則

常用的逐層剝?nèi)〖?xì)化算法有Hilditch，該算法通過判斷圖像中屬于邊界點而不是連通點，就可以去掉此點，這是一種反復(fù)掃描的過程。如果對于一個矩形區(qū)域（圖3），從左上角開始到右下角，每次掃描可以講矩形最外面一層剔去，層層剝離后，最終剩下最中間的一條線（圖4）。

圖2 索引表

圖3 細(xì)化前圖

圖4 灰色即剝?nèi)↑c

綜合以上分析，上述算法處理圖像時都需要反復(fù)對圖像進(jìn)行掃描，刪除可剔除點。若圖像較粗，掃描次數(shù)大量增加，因此效率低下，適合于小圖或者少量圖像處理。

2 細(xì)化算法

本算法基于逐層剝?nèi)±砟?，快速?xì)化算法改進(jìn)了反復(fù)掃描的過程，順序、逆序搜索兩次，確定每個點的層數(shù)，通過層數(shù)可判斷該點屬于邊界點還是骨架，因而優(yōu)化算法的效率，大量減少程序運算時間。

以下是對于算法的詳細(xì)步驟（規(guī)定黑色值1白色值0）：

第一步，從上到下，從左到右依次掃描每一個點，若當(dāng)前點（x，y）為黑點時，需判斷其右上、上、左上和左四點的情況（圖 5）。 （x-1，y+1） （x-1，y） （x-1，y-1） （x，y-1） 這四點可以理解為當(dāng)前點是被該四點包圍，該點層數(shù)即四點層數(shù)最小值多一層；如果當(dāng)前點（x，y）為白色，層數(shù)值賦為0。

圖5 上至下左至右F值

圖6 下至上右至左G值

第二步，自下而上，自右而左，與第一步相似的判斷每個點的狀態(tài)，若當(dāng)前點是黑點，于是判斷其左下、下、右下和右四點的情況（圖6）。 （x+1，y-1） （x+1，y） （x+1，y+1） （x，y+1）四點包圍了當(dāng)前點，同樣取這四點層數(shù)的最小值加1作為該點層數(shù)值；如果當(dāng)前點（x，y）為白色，層數(shù)值賦為0。

與此同時，既然已經(jīng)求得每一個點上包圍層數(shù)值和下包圍層數(shù)值，每個點的實際層數(shù)其實就是兩種層數(shù)值中最小值（圖 7）。

圖7 取點的層數(shù)值M值

第三步，從上到下，從左到右依次掃描每一個點，此時需要判斷該點8方向（圖7）范圍內(nèi)所有點層數(shù)的情況。如果當(dāng)前點的層數(shù)值是周圍相鄰點中最大，該點即保留；如果當(dāng)前點的層數(shù)值并非最大，該點即可刪去。

綜上步驟，即完成了該圖像細(xì)化的全部過程，算法只需遍歷3次，就能將一幅圖像進(jìn)行快速細(xì)化。

3 結(jié)果分析

圖8-0 原圖

圖8-1 快速細(xì)化算法

圖8-2 索引表算法圖

圖8-3 Hilditch細(xì)化算法

圖9-0 原圖

圖9-1 快速細(xì)化算法

圖9-2 索引表算法

圖9-3 Hilditch算法

從圖像上（圖8-0圖9-0）可以看出，上述3種算法都能有效細(xì)化圖像，得到圖像骨架；在索引表細(xì)化及Hilditch細(xì)化中保持了圖像的連通性，但出現(xiàn)大量毛刺；快速細(xì)化算法則出現(xiàn)部分?jǐn)嗔?，但較高描述圖像形態(tài)。

表1

從表1也可發(fā)現(xiàn)，在線條較細(xì)的圖像中（圖8-0），三種算法運行時間幾乎相同；而在線條較粗的圖像中（圖9-0），快速細(xì)化算法運算時間明顯優(yōu)于其余兩種，再將圖像（圖9-0）等比例放大一倍后，快速細(xì)化算法運算時間約原圖像的3倍，而其余兩種算法則需6-7倍，從而看出快速細(xì)化算法的優(yōu)勢。

［1］田剛，馬琨.數(shù)字圖像處理在等差條紋骨架線提取中的應(yīng)用[J].

［2］韓九強.機器視覺技術(shù)及應(yīng)用[M].高等教育出版社，2009.

［3］Rafael C.Gonzalez Richard E.Woods.岡薩雷斯數(shù)字圖像處理[M].電子工業(yè)出版社，2003.

［4］卞維新，徐德琴，王俊書.基于兩極復(fù)合式指紋圖像細(xì)化算法的研究[J].貴州工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2005，34（3）：80-84.

［5］王家隆，郭成安.一種改進(jìn)的圖像模板細(xì)化算法[J].中國圖象圖形學(xué)報，2004，9（3）：297-301.

［6］梅園，孫懷江，夏德深.一種基于改進(jìn)后模板的圖像快速細(xì)化算法[J].中國圖象圖形學(xué)報，2006，11（9）：1306-1311.

［7］王業(yè)琳，寧新寶，尹義龍.指紋圖像細(xì)化算法的研究[J].南京大學(xué)學(xué)報：自然科學(xué)，2003，39（4）：468-475.