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

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

1 引言

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

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

問題1 二像素寬度斜線細化出現(xiàn)結(jié)構(gòu)全丟失。

問題2 2×2正方形結(jié)構(gòu)細化后拓撲結(jié)構(gòu)全丟失。

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

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

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

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

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

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

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

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

2 細化算法基本原理

2.1 基本定義

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

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

2.2 細化約束條件

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

若S為偶數(shù)，公式（3）、（4）變?yōu)椋?/p>

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

2.3 平滑像素點的判定條件

迭代次數(shù)較多的二值圖像通常存在不光滑的輪廓，由于目標各處由表面到內(nèi)部的細化速度是均勻的，最終在各不平滑輪廓的突起處將會形成不同長度的分支?？梢酝葡耄敶毣瘓D像擁有平滑程度更高的輪廓，將會得到更少分支的細化結(jié)果。

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

圖2 光滑像素點1～4

2.4 保留與刪除模板

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

圖3 4×4子域

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

3 骨架提取改進算法

3.1 改進算法整體描述

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

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

圖4 保留模板

圖5 刪除模板

3.2 算法細節(jié)描述

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

圖6 改進算法整體框圖

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

3.3 改進算法流程

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

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

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

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

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

圖7 改進算法流程圖

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

4 改進算法效果及性能

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

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

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

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

圖9 正方形細化效果對比

圖10 人體結(jié)構(gòu)細化效果對比

圖11 字母結(jié)構(gòu)細化效果對比

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

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

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

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

表1 各算法細化率對比

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

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

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

5 結(jié)論

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

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