引入平滑迭代的骨架提取改進算法

袁良友，周 航，韓 丹，許國梁

北京交通大學 電子信息工程學院，北京100044

1 引言

作為計算機視覺領域提取目標特征的處理步驟之一，細化已經廣泛應用于指紋識別、字符處理、運動人體分析、測繪信息提取[1-4]等各種應用場景。細化是指在不影響原圖像拓撲連接關系的條件下，保持其目標骨架或中軸線，將圖像的線條由多像素寬度減少至單位像素寬度，極大消除圖像冗余信息的過程，也稱骨架化。具有良好效果的細化算法須具有以下特點：迭代收斂、骨架可連通、拓撲結構不變、細節特征可保持、無冗余像素、骨架中心化、實時性好等。細化算法作為一個活躍的研究領域，目前已有一些經典的成果。整體而言細化算法可分為迭代以及非迭代兩類，迭代算法分為串行[5]、并行以及串并行混合算法，而非迭代算法基于距離變換或其他原理，處理后的骨架通常缺乏整體連通性。在此背景下，速度快、條件簡單的并行算法得到了更廣泛應用，代表之一便是Zhang和Suen在文獻[6]中提出的ZS細化算法。

ZS算法對拐角、T型交叉點以及直線的結構細化效果較好，能保持其整體連通性以及較快的細化速度。但是大量的實驗表明，ZS 算法普遍存在三種處理不當的問題[7]：

問題1 二像素寬度斜線細化出現結構全丟失。

問題2 2×2正方形結構細化后拓撲結構全丟失。

問題3 細化后大量存在二像素寬度的冗余像素。

細化過程中局部信息的丟失將導致可提取特征點的減少，冗余信息會混淆和誤導特征點提取的結果，微小結構的丟失則嚴重影響某些微型結構場景下的細化效果。如何同時處理結構丟失、像素冗余的細化問題顯得尤為重要。

因此，產生了各種ZS算法的改進形式，Lu和Wang[8]提出LW 細化算法，去除了B(P0)=2 的刪除判定條件，使得二像素斜線結構得到保留，但細化結果出現大量冗余分叉。牟少敏等人[9]通過制作像素周圍8鄰域的十進制模板，增加了特定模板刪除條件，一定程度上解決了冗余像素問題。包建軍等人[10]提出EPTA 的魯棒算法，增加了是否結束第一階段掃描的判斷條件并增加一個二階段掃描過程，有效改善了局部信息丟失和冗余像素等問題，但其依然存在斜線細化畸變以及冗余消除不完全的問題。趙丹丹等人[11]提出IEPTA 算法，在EPTA 算法的基礎上增加了兩個對稱的映像迭代過程，獲得了更加接近中心線的骨架圖像，但并沒有實現完全對稱的細化效果。文獻[12]提出了MZS算法，能夠完整保留2×2正方形結構，但像素的坐標索引值的奇偶性會對細化結果有直接影響。

好的細化算法應能改善圖像線條紋路信息，而不僅僅是消極地進行數據壓縮。對于線狀圖形信息豐富的圖像，細化之后除了骨架的大小、形狀與原圖像保持一致，一般也會存在原圖像的表面噪聲信息。文獻[13]指出，在足夠多的迭代次數下，不平滑的表面輪廓會使得細化結果存在第四種問題：

問題4 圖像出現較多受噪聲影響的輪廓分叉。

文獻[14]通過改進刪除規則，提出了一種基于輪廓篩檢的骨架細化算法，并應用于交通指揮動作骨架提取過程中，但其刪除規則的制定依據于人體骨架而不具普遍性。文獻[15]提出了一種基于筆劃連續性檢測的并行細化算法，可以控制筆劃交叉或交叉處的大變形，免受表面噪聲干擾，但其適用范圍局限于字符圖像。對于不同類型的二值圖像，細化時若能夠在刪除冗余像素和保留特定結構的前提下減少其表面噪聲信息，將大大提高后期特征提取的效果和精度。

為了解決細化過程出現的以上問題，本文在細化過程中加入保留模板和消除模板以處理冗余與結構丟失現象；同時在進行全局的細化迭代前引入一定次數的輪廓平滑迭代過程，有效抑制了實際二值圖像的表面噪聲帶來的分支效應。

引入通用的并行計算平臺和編程模型可以加快算法的運算速度[16]。目前，各個并行細化算法的CUDA并行編程模型正在成為研究熱點，其算法的并行版本平均可比傳統的CPU順序版本快幾十倍以上。

2 細化算法基本原理

2.1 基本定義

規定二值圖像的前景點像素為1，背景點像素為0。對某一像素點P0，其8 鄰域與24 鄰域的像素點集合如圖1 所示，P0為掃描點像素，P1～P8為其8 鄰域像素，在周圍擴展一層像素集合P9～P24得到其24 鄰域像素。在細化的迭代過程中，每次迭代的次序記為N，子迭代次序記為S。像素P0的交叉數A(P0)定義為沿其八鄰域順時針環繞一周像素由1變為0的次數，P0的連接數B(P0)定義為其八鄰域中像素為1的總數。

圖1 像素8鄰域與像素24鄰域

2.2 細化約束條件

對于ZS 細化算法，子迭代次數S的奇偶性決定了不同的判斷條件。若S為奇數，當每次判斷像素點P0滿足下列4 個條件，標記為待刪除點，并在該子迭代結束時統一刪除。

若S為偶數，公式（3）、（4）變為：

當某次迭代中不存在滿足刪除條件集合的像素，算法結束。

2.3 平滑像素點的判定條件

迭代次數較多的二值圖像通常存在不光滑的輪廓，由于目標各處由表面到內部的細化速度是均勻的，最終在各不平滑輪廓的突起處將會形成不同長度的分支。可以推想，當待細化圖像擁有平滑程度更高的輪廓，將會得到更少分支的細化結果。

滿足公式（1）的目標輪廓像素點可分為平滑像素點與非平滑像素點。如圖2，像素點1～4 依次代表了斜方向與水平方向上的平滑像素點，它們滿足公式（2）和（7）。

圖2 光滑像素點1～4

2.4 保留與刪除模板

24鄰域可以劃分出4個不同方向上的4×4子域，如圖3 中的M1～M4 所示，它們適合用來區分不同方向上的特定結構。

圖3 4×4子域

為處理細化過程中的結構丟失與冗余像素問題，分別設計了24 鄰域子域下的保留模板以及8 鄰域下的刪除模板[17]，如圖4、圖5。模板中的像素點Px可為1也可為0。

3 骨架提取改進算法

3.1 改進算法整體描述

引言中論述的四種問題在不同的細化場景下其處理的優先級是不同的。目標像素總數與迭代次數較少時，問題1～3所代表的拓撲結構丟失與像素冗余問題應當被優先考慮。而當像素總數與整體迭代次數較多時，問題4 中不光滑輪廓引起分支問題的解決對于目標特征提取更加關鍵。

因此，在進行全局迭代前，本文引入一定次數的平滑迭代過程，用以解決不同場景下的細化問題。在平滑迭代過程中對平滑像素點進行保留，抑制了平滑輪廓出像素點集合的細化速度。同時，為了解決結構和冗余問題，在前期的迭代過程中引入保留模板，而在后續的二階段掃描過程中引入刪除模板。

圖4 保留模板

圖5 刪除模板

3.2 算法細節描述

如圖6所示，改進算法將整個細化過程分成三種迭代流程：平滑迭代、全局迭代以及二階段掃描。針對問題1 和2，在平滑迭代與全局迭代中加入保留模板的判定條件，保留所有既有刪除標記又滿足保留模板的像素點，從而避免了一些拓撲結構的刪除。其中，圖4（a）～（h）用來保持二像素寬度斜線，圖4（i）用于保持2×2 正方形結構。針對問題3，在二階段掃描中加入刪除模板（圖5）的判定條件，挑選出那些不滿足刪除條件但滿足刪除模板的像素點進行單獨刪除，可避免細化結構出現冗余點。不同于全局迭代中添加刪除標記的處理過程，直接刪除滿足刪除模板判定條件的像素點，能有效避免拓撲結構的斷裂情況出現。對于問題4，引入的K次平滑迭代可以很好地抑制輪廓噪聲。在每次迭代過程中，滿足公式（1）、（2）的像素點集合代表了所有的目標邊緣像素，滿足公式（7）的像素點集合代表了輪廓上的所有平滑像素。僅標記所有的不平滑像素點，意味著直接對輪廓噪聲進行過濾，使得目標圖像在后續的全局迭代過程中能得到更整體化的細化結構。

圖6 改進算法整體框圖

此外，過多的或者不合適的平滑迭代次數會導致提取的骨架出現結構變形。K值的選取應由實際圖像的輪廓平滑程度以及前景像素點總數決定。輪廓平滑程度較高，對平滑迭代的要求降低；前景像素點總數較少，對判定條件的敏感度提高，兩種情況下K值均應該取較小。

3.3 改進算法流程

修改后的細化算法方案流程如下：

步驟1 根據待細化圖像的像素總數和輪廓平滑情況選定平滑迭代次數K，初始化N=0,S=0。

步驟2N＜K時，進行平滑迭代。首先對同時滿足公式（1）、（2）的像素點進行刪除點標記，再在這些像素集合中除去滿足公式（7）以及滿足保留模板圖4（a）～（i）之一的像素點。每次迭代結束時刪除掉有刪除標記的像素，N=N+1。

步驟3N≥K時，進行全局迭代。奇數次子迭代對同時滿足公式（1）～（4）的像素點進行刪除點標記，偶數次子迭代對同時滿足公式（1）、（2）、（5）、（6）的像素點進行刪除點標記，然后在這些像素集合中除去滿足保留模板圖4（a）～（i）之一的像素點，每次迭代結束時刪除掉所有刪除標記的像素，N=N+1,S=S+1。當某次迭代后無刪除標記像素時，進入步驟4。

步驟4 進行一次全局迭代的二階段掃描。掃描過程中直接刪除滿足刪除模板（圖5 后兩個）的像素點。當迭代后無刪除標記像素時，細化結束。

圖7 改進算法流程圖

圖8 二像素寬度斜線細化效果對比

4 改進算法效果及性能

為了檢驗改進算法對問題1～4的改善效果，本文在Visual Studio 2019 環境下，分別對二像素寬度斜線結構、正方形結構、人體結構以及字母結構進行細化，并將改進算法、經典ZS算法與較新的IEPTA算法、MZS算法細化結果進行比較。考慮到細微結構對平滑迭代的敏感度高，僅在字母結構細化過程中加入平滑迭代。

如圖8 所示，相比ZS 算法無法有效保持二像素寬度結構，IEPTA 算法與MZS 算法均解決了二像素斜線細化畸變的問題，但前者細化后的斜線長度有所減少，后者由于判斷條件的不對稱其結果出現了上下兩部分結構的中心偏移。這兩種情況在改進算法中均有所改善。

如圖9所示，ZS算法和IEPTA算法無法保留左邊的2×2 正方形拓撲結構。而MZS 和改進算法均能克服該缺點，同時也能完整保留圖右邊的兩正方形交叉結構。

如圖10 所示，ZS 算法處理后人體的右腿部出現較多的冗余像素，而IEPTA、MZS 以及改進算法均實現了對冗余像素的去除。其中，IEPTA 算法由于從4 個方向上進行迭代且加入刪除冗余信息的消除模板，處理后的人體骨架較為光滑，但其手部區域也相應地出現了結構丟失。MZS 算法保留的骨架具有較好的連通性，但沒有充分刪除諸如右腳處的分叉像素點，易受表面噪聲的影響。改進算法保持了具有良好連通性的ZS算法細化后的主干結構，同時對噪聲點像素也能合理的去除。

圖9 正方形細化效果對比

圖10 人體結構細化效果對比

圖11 字母結構細化效果對比

圖12 仿真實驗細化圖片示例對比

如圖11 所示，對字母圖片進行細化處理后，ZS 算法、IEPTA 算法、MZS 算法的效果圖均出現端點和邊緣處的較大分叉。受到不平滑輪廓的干擾，未加入平滑迭代的改進算法也出現了邊緣分叉，通過取一定大小的K值，有效去除了上下兩處分叉，同時整體的骨架更加光滑。

以上4組圖片的實驗結果分別展示了改進算法對4類問題的展示效果。為了對各算法的細化程度進行精確的評估，對MPEG7 圖像數據集進行細化仿真實驗，圖12展示了仿真實驗的一個示例。

用于細化的目標圖像應該具有整體的線條化結構，且所細化目標應具有可提取的特征及一定的現實意義。細化性能往往受到圖像大小和圖像內容的影響。因此從全部1 402張二值圖像中選取適合細化的527張圖片作為仿真對象。同時，在細化仿真前，進行必要的濾波和形態學預處理[18]，首先對數據集中的原始圖像進行背景像素點填充，使其符合模板匹配的要求。然后針對圖像中大量存在的邊緣噪聲和孔洞結構進行適當的形態學開操作與閉操作[19]。定義細化率為算法細化過程中刪除掉的前景像素點數占原有前景像素點數的比例，各算法細化率結果和冗余像素情況在表1～表3中給出。

表1 各算法細化率對比

表2 不同K 值下的改進算法細化率對比

表3 各算法冗余像素情況對比

表1 展示了ZS、IEPTA、MZS 以及改進算法(K=0)的細化率仿真情況，其中改進算法的細化程度最高，其細化率比前三種算法分別高出0.23%、0.05%、0.11%，說明改進算法能夠高效濾除圖像中的冗余信息。表2 比較了不同平滑迭代次數下的改進算法的細化率，驗證了增大平滑迭代次數將會進一步提高其細化程度，同時能提高對輪廓噪聲的改善效果。表3 表明改進算法的細化結果無冗余像素，很好處理了像素冗余與結構丟失的矛盾問題。

5 結論

本文針對二像素寬度斜線結構全刪除、正方形結構丟失、大量斜線冗余像素存在以及不平滑輪廓帶來大量分叉四類問題，在原始ZS 細化算法基礎上引入了平滑迭代流程以及后續的掃描過程，并在其中加入保留模板和刪除模板條件的判定。通過針對性地保留和刪除一些特定的拓撲結構，有效保留了二像素寬度斜線結構和正方形結構，并完全刪除了斜線上的冗余像素，引入的平滑迭代能有效減少骨架輪廓的噪聲分叉。仿真實驗數據表明，不引入平滑迭代階段的改進算法的細化率相比ZS、IEPTA、MZS算法提高了0.05%～0.25%不等；而平滑迭代次數的增加，能進一步提高細化程度，減少大量的輪廓分叉，完整保留了目標圖像的骨架信息和拓撲性。

本文解決了現有細化算法在細化過程中的局部結構丟失、冗余像素以及輪廓分叉的問題，但沒有對具體細化背景下合理的平滑迭代次數的選取做出精準估算，同時受到匹配模板及平滑迭代次數的影響其算法的實時性并不穩定。后期將就確定自適應的K值以及提高算法實時穩定性做進一步研究，完善其改進算法性能。