二值圖像的快速細化算法

余 樑 王廣偉

（浙江海洋學院數理信息學院 浙江 舟山 316000）

0 引言

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

1 像的細化分析

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

常用的細化算法有查表細化和逐層剝取細化。

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

圖1 公式規則

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

圖2 索引表

圖3 細化前圖

圖4 灰色即剝取點

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

2 細化算法

本算法基于逐層剝取理念，快速細化算法改進了反復掃描的過程，順序、逆序搜索兩次，確定每個點的層數，通過層數可判斷該點屬于邊界點還是骨架，因而優化算法的效率，大量減少程序運算時間。

以下是對于算法的詳細步驟（規定黑色值1白色值0）：

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

圖5 上至下左至右F值

圖6 下至上右至左G值

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

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

圖7 取點的層數值M值

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

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

3 結果分析

圖8-0 原圖

圖8-1 快速細化算法

圖8-2 索引表算法圖

圖8-3 Hilditch細化算法

圖9-0 原圖

圖9-1 快速細化算法

圖9-2 索引表算法

圖9-3 Hilditch算法

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

表1

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

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

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

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

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

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

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

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