一種基于二值圖像的形狀分割算法研究*

王琴竹，唐 瑩

(1.運城學院 公共計算機教學部，山西 運城 044000；2.中國建行廣西分行信息技術部，廣西 南寧 530022)

形狀分割屬于圖像的粗分割，一般采用基于數學形態學的分割技術，適用于較為復雜的圖像檢索、識別和變形等的預處理，可以提高后續處理的速度和效率。本文提出一種新的形狀分割算法，先檢測出邊界的凹角點，然后分析圖像骨架分支，根據每個分支兩側最近的凹角點確定分割線來進行分割。

1 基于二值圖像形狀的分割算法

1.1 凹角點檢測

角點提取[1]是圖像處理中的一個重要任務，研究者提出過許多檢測方法，如：利用鏈碼跟蹤到的輪廓點計算曲率來判定角點和運用方向導數來檢測角點[2]等。本文則運用SUSAN特征檢測原則[3]提取剪紙二值圖像中外輪廓的凹角點。

SUSAN角點檢測是一種直接利用圖像灰度信息進行角點檢測的方法，具有方法簡單、定位準確、抗噪能力強的特點。其方法如下：如圖1所示，用圓形模板在圖像上移動，若模板內的像素與模板中心像素(核)灰度的差值小于一定閾值，則認為該點與核具有相同(或相近)的灰度，滿足此條件的像素所組成的區域稱為USAN(Univalue Segment Assimilating Nucleus)，統計 USAN區域面積，最后將USAN區域面積與一個幾何門限比較以判斷是否為角點。在二值圖像中，分別用0和1代表背景像素和目標像素。對于邊界點的USAN，其構成元素均為目標像素，因此可直接統計以邊界點為核的USAN面積，即統計目標像素的個數：

式中，c(r0)是以r0為圓心的模板，c(r，r0)為模板中的目標像素。

圖1 SUSAN原則中模板的位置

設圓形模板的半徑為R，分析圓形模板在邊界線上移動時USAN面積的特點。由圖1可知，當圓形模板在位置d時，USAN面積剛好為圓形模板面積的一半；當模板位于a時，USAN面積小于圓形模板面積的一半；當模板位于e時，USAN面積大于圓形模板面積的一半。圖1中的a和e位于角點位置，其中e的位置即為要檢測的凹角點的位置，而d是位于直線上的點(在局部小范圍內，邊界線可看作直線)。基于上述分析可知，邊界凹角點的USAN面積大于圓形模板面積的一半。檢測凹角點方法如下：設需要檢測邊界曲線上≥β(β>90°，類似圖 1位置 e)的角點，S(R)表示圓形模板的面積(即圓形內像素的總個數)。由扇形和圓的關系可知，其面積比等于角度比，所以USAN面積符合以下條件的邊界點為候選凹角點：

實際中常按α＋β=360對α和β進行取值。通常，由于角點一定發生在USAN面積極值處，角點附近會產生若干個候選角點。因此對S(R)/2的A(r0)，取USAN面積最大值處為真正的角點。

1.2 骨架提取

(1)基本形態變換定義：設有模板 C，F={F1，F2}，F=F1∪F2且 F1∩F2=Φ為給定的結構元素，X是待變換圖像，由此可以對基本形態變換定義如下：

定義1結構元素C對圖像X的膨脹為：

定義2結構元素C對圖像X的腐蝕為：

定義3結構元素F對圖像X的擊中變換為：

定義4結構元素F對圖像X的形態薄化變換為：XdF=X/(X?F)=XI(X?F)d

形態薄化變換就是從圖像X中刪除被F擊中的部分，它使圖像線劃減細，是圖像形態細化算法的基礎。

(2)改進的序貫同倫形態細化過程就是采用多個分別承擔不同方向像素剝離的拓撲同倫結構元素，按細化應遵循的原則，對圖像進行反復的迭代薄化運算，直到迭代收斂為止。其模型為：

式中，SK(X)為圖像 X的骨架；k是圖像細化過程收斂時的總循環次數，取決于圖像目標的大小及粗細；結構元素 Di、Ei、Li分別承擔不同方向像素的剝離，當 i=4時，Di+1=D5=D1，可以證明這種算法模型也是收斂的。其最大優點是對于大規模的圖像矩陣來說，任一個像素的剝落與否可以同時采用4個結構元素進行擊中運算。在每次循環中，迭代次數為4，則總迭代次數為4k，收斂速度大為加快。結構元素D、E、L如圖2所示。

圖2 結構元素 D、E、L

圖中，正中間格“1”表示結構元素的原點；“*”表示取“0”或“1”。式(3)模型的程序實現步驟如下：

①X：?X1，0：?k；

②X1：?X2；

③(X2?D1)U(X2?D2)U(X2?E1)U(X2?L1)：?Y；X2/Y：?X2；

④(X2?D2)U(X2?D3)U(X2?E3)U(X2?L2)：?Y；X2/Y：?X2；

⑤(X2?D3)U(X2?D4)U(X2?E3)U(X2?L3)：?Y；X2/Y：?X2；

⑥(X2?D4)U(X2?D1)U(X2?E4)U(X2?L4)：?Y；X2/Y：?X2；

⑦若 X2≠X1；則k+1：?k；X2：?X1轉②；

⑧X2：?SK(X)，輸出 SK(X)，結束。其中，：?為值賦予或圖像賦予。

1.3 生成所有分割線

生成所有分割線具體步驟：

(1)按最近原則分別檢測骨架線所有分支兩側的凹角點，并將兩側離分支最近的的凹角點相連，得到分割線集合 θ1。

(2)分別計算集合θ1內所有分割線與骨架線的交點個數。

(3)根據交點個數判斷，找出與骨架分支有且只有一個交點的凹角點連線，得到分割線集合 θ2，θ2即是包含初步生成的所有的分割線結果。

(4)集合θ2中的每條分割線的首尾端點之間的圖像邊界的控制點即為一個分割子區域的邊界控制點。

由以上步驟生成圖像的所有分割線如圖3所示，圖中淺色直線即是生成的分割線。

圖3 生成所有分割線結果

1.4 優化分割線

優化一：清除邊界的局部形變或局部噪聲造成的影響。局部形變或局部噪聲會對區域骨架的結構產生較大的影響，雖然采用改進的骨架對這些影響進行了一定的抑制，但有些局部形變或局部噪聲還是會形成一些不合適的分割線，如圖3中a處的分割線是由局部噪聲影響生成的分割線。

優化二：去除較短長度的分支兩側凹角點形成的分割線，這類分割線分割出來的子區域比較小，對后期的工作貢獻不大。如圖3中b處的分割線屬于分割后的子區域對形狀分析貢獻不大的細小區域。

優化方法：清除這兩類的分割線可通過在骨架提取過程中修剪產生的骨架短枝，但在刪除過程中，不能破壞骨架的完整和連通性。采用以下模型進行骨架短枝的刪除：

式中，l為骨架短枝的長度(像素個數)；結構元素Ki如圖4所示。

圖4 結構元素K

2 實驗計算

為驗證本文算法效率，從二值圖像的形狀分割算法中選取具有代表性的Limbs算法[4]與本文算法進行用時對比實驗，實驗在 PⅢ處理器(930 MHz)、256 MB內存的微機上進行。在實驗中，對30幅各種類型的二值剪紙圖像進行了多組試驗，結果表明，本文算法所得到的分割結果均達到了一般形狀分割的要求，為圖像的后續處理(如圖像識別以及本文接下來的剪紙圖像變形工作)提供了便利，而且處理的圖像數據越大，本文算法的時間優勢就越明顯。表1是兩種算法的時間比較。

表1 兩種形狀分割算法的性能比較

用本文算法的剪紙圖像分割結果如圖5所示，骨架短枝的修剪長短可由用戶根據分割需要以及圖像邊界噪聲的影響程度控制。圖5(a)是設置骨架短枝修剪長度為10，將牛的尾巴和蹄子上對后續分析無用的小區域分割線刪掉所得優化分割線后的分割結果；圖5(b)是設置骨架短枝修剪長度為15，將鳥背上的邊界噪聲以及爪子的小區域分割線刪掉后的分割結果。

用Limbs算法的剪紙圖像分割結果如圖6所示。由于Limbs算法是按照最小內切圓原則來連接邊界點得到分割子區域，對剪紙圖像中的牛蹄和鳥的頸部都沒有完整分割出來，在后續的剪紙變形處理將會帶來一定的影響。因此，本文算法在剪紙圖像的形狀分割的應用上比Limbs算法可為后續變形處理提供更好的分割結果。

圖5 本文算法優化后的分割線

圖6 Limbs算法分割結果

本文提出了一種二值圖像形狀分割算法，該算法將形狀分割的兩大類型方法結合起來，先檢測出邊界的凹角點，然后分析圖像骨架，將每個分支兩側最近的凹角點相連得出形狀分割后的子區域。該算法避免了大量的計算，同時通過對修剪骨架短枝減少了邊界噪聲的影響，并刪除了對形狀分析貢獻不大的子區域分割，從而降低了在進行骨架提取時對骨架提取算法好壞的依賴程度，提高了形狀分割的速度和效率，更適合后續的圖像分析處理。

[1]張坤華，王敬儒，張啟衡.多特征復合的角點提取方法[J].中國圖像圖形學報，2002，7(4)：319-324.

[2]FREEMAN H，DAVIS L S.A corner finding algorithm for chain code curves[J].IEEE Transactions.on Computers，1997， 26： 297-303.

[3]SMITH S M，BRADY J M.SUSAN-a new approach to low levelimageprocessing[R].InternalTechnicalReportTR95SMS1，Defence Research Agency， Chobham Lane， Chertsey， Surry，UK，1995.

[4]KALEEM S， KIMIA B B.Parts of visual form： computational aspects [J].IEEE Transactions on Pattern Analys and Machine Intelligence， 1995，17(3)： 239-251.