保拓?fù)浣Y(jié)構(gòu)的三維細(xì)化算法及三維非接觸測(cè)量

洪漢玉+馬爾威+黃麗坤

【摘要】 針對(duì)現(xiàn)有的三維細(xì)化算法會(huì)出現(xiàn)斷裂、不連續(xù)以及破壞物體原有的拓?fù)浣Y(jié)構(gòu)等問題，提出了一種基于保拓?fù)浣Y(jié)構(gòu)和具有旋轉(zhuǎn)不變性的新的三維細(xì)化算法。實(shí)驗(yàn)結(jié)果表明，新的細(xì)化算法具有連通性保持不變，幾何及拓?fù)湫再|(zhì)保持不變，及旋轉(zhuǎn)后細(xì)化結(jié)果保持不變的性質(zhì)。

【關(guān)鍵詞】 三維細(xì)化 刪除模板 拓?fù)浣Y(jié)構(gòu) 旋轉(zhuǎn)不變性 三維非接觸測(cè)量

一、引言

圖像細(xì)化廣泛應(yīng)用在各個(gè)領(lǐng)域，如醫(yī)學(xué)圖像分析，模式識(shí)別等。三維圖像細(xì)化是圖像處理和視覺分析的主要研究方向，細(xì)化提取的骨架是后續(xù)圖像分析和特征提取的重要基礎(chǔ)。從三維細(xì)化的結(jié)果中可提取基本尺寸和基準(zhǔn)線、基準(zhǔn)面等特征，包括物體的軸線基準(zhǔn)、軸線長度，形狀結(jié)構(gòu)及聯(lián)接關(guān)系。通過這一系列參數(shù)和特征準(zhǔn)確表述和確定目標(biāo)的當(dāng)前狀態(tài)，從而實(shí)現(xiàn)對(duì)三維目標(biāo)的全方位的非接觸測(cè)量。

三維細(xì)化算法主要包括提取中心線和提取中心面兩類，本文重點(diǎn)研究中心線的提取。在一個(gè)三維二值圖像中黑點(diǎn)和白點(diǎn)分別代表目標(biāo)點(diǎn)和背景點(diǎn)，細(xì)化就是將逐層將黑點(diǎn)移除（黑點(diǎn)改為白點(diǎn)）直到僅剩一個(gè)像素寬的骨架。連通性及拓?fù)浣Y(jié)構(gòu)的保持是三維細(xì)化過程中考慮的主要問題，概括為三個(gè)方面：（1）輸入圖像中的任何物體不能被拆分或完全消除；（2）任何空腔不能與背景或另一個(gè)空腔合并；（3）不能消除或新增任何的空腔和孔洞。連通性的保持是拓?fù)湫再|(zhì)的保持的基礎(chǔ)，例如形如“o” 的物體細(xì)化后不能形如 “c”，細(xì)化后提取的骨架應(yīng)位于物體的中軸，并且看起來相似于原物體；同時(shí)細(xì)化算法在物體平移、比例變化及旋轉(zhuǎn)前后提取的骨架應(yīng)基本保持一致。

提取中心線的三維細(xì)化算法多是基于模板的并行細(xì)化算法。并行細(xì)化算法有子迭代并行細(xì)化算法，區(qū)域并行細(xì)化算法[10，11]和完全并行細(xì)化算法三類。完整的基于模板的完全并行三維細(xì)化算法由Ma和Sonka提出，這一算法不能很好的保護(hù)三維物體的拓?fù)浣Y(jié)構(gòu)，后續(xù)研究者發(fā)現(xiàn)這一問題，Wang和Basu通過擴(kuò)充刪除模板解決了某些情況下細(xì)化結(jié)果出現(xiàn)斷裂的情況，但仍存在一些問題，且由于刪除模板擴(kuò)充后有方向性，不能保證三維物體旋轉(zhuǎn)后的細(xì)化結(jié)果保持不變。

針對(duì)上述問題，提出一種新的細(xì)化算法，從基礎(chǔ)模板在各個(gè)方向上旋轉(zhuǎn)得到具有各向同性的刪除模板，保證了模板的對(duì)稱性，使物體旋轉(zhuǎn)之后細(xì)化結(jié)果和旋轉(zhuǎn)前細(xì)化結(jié)果保持一致；給出了真?zhèn)蝿h除點(diǎn)的定義，并證明了提出的算法滿足連續(xù)性保持的條件，解決了點(diǎn)同時(shí)刪除造成不連續(xù)的問題。

二、三維細(xì)化旋轉(zhuǎn)不變性理論分析

Wang和Basu針對(duì)Ma和Sonka的算法中不能保持連通性的情況對(duì)D類模板添加更多更細(xì)致的限制，擴(kuò)充了最終的刪除模板。Ma算法中D類刪除模板是12個(gè)，Wang對(duì)模板中的一些點(diǎn)增加了限制，把D類模板擴(kuò)充為36個(gè)。Ma算法中d7如圖2所示，Wang擴(kuò)充后的d7如圖3所示。

圖3 Wang算法中刪除模板d7-1，d7-2，d7-3算法主要步驟：

1）檢測(cè)邊界點(diǎn)（26鄰域內(nèi)至少有一個(gè)是背景點(diǎn)）。

2）并行刪除滿足任一刪除模板的非尾點(diǎn)。

3）返回1）直到無任何點(diǎn)可以被刪除。

完全并行細(xì)化算法，從各個(gè)方向同時(shí)逐層刪除三維物體中的點(diǎn)，這保證了最終結(jié)果位于原物體的中軸上，且相似于原物體。但并行細(xì)化算法的細(xì)化結(jié)果有出現(xiàn)斷裂的可能，每一層的點(diǎn)在進(jìn)行刪除模板的匹配及其他刪除條件的判斷時(shí)，若點(diǎn)與點(diǎn)之間相互為滿足刪除條件的必要點(diǎn)，同時(shí)刪除所有滿足條件的點(diǎn)得到的細(xì)化結(jié)果就可能出現(xiàn)斷裂，不能保持原物體的拓?fù)浣Y(jié)構(gòu)。

其他情況下仍仍然會(huì)出現(xiàn)斷裂，使最終細(xì)化結(jié)果無法保持原物體拓?fù)浣Y(jié)構(gòu)。同時(shí)因?yàn)橹桓淖兞四承┓较蛏系哪０?，最終的刪除模板不再是完全對(duì)稱，使得細(xì)化算法不具旋轉(zhuǎn)不變性。

三、基于保拓?fù)浣Y(jié)構(gòu)和旋轉(zhuǎn)不變性的細(xì)化算法

針對(duì)上述分析提出一種新的基于保拓?fù)浣Y(jié)構(gòu)和旋轉(zhuǎn)不變的三維細(xì)化算法。首先給出旋轉(zhuǎn)不變性的定義，其次設(shè)計(jì)了各向同性的刪除模板，最后根據(jù)需要定義了真?zhèn)蝿h除點(diǎn)，并論述了提出的算法滿足連續(xù)性保持的條件。通過假設(shè)驗(yàn)證法，檢測(cè)候選刪除點(diǎn)刪除前后26鄰域內(nèi)目標(biāo)體和背景組的數(shù)目變化，確認(rèn)刪除點(diǎn)的真?zhèn)?，保持了原有的拓?fù)浣Y(jié)構(gòu)，進(jìn)而確保物體旋轉(zhuǎn)后細(xì)化結(jié)果的連續(xù)性不變。

關(guān)于旋轉(zhuǎn)不變性做如下定義：

定義1（旋轉(zhuǎn)不變性）：當(dāng)物體相對(duì)之前位置旋轉(zhuǎn)后，通過細(xì)化提取的骨架與旋轉(zhuǎn)前提取的骨架形態(tài)及結(jié)構(gòu)保持一致，簡稱該細(xì)化算法具有旋轉(zhuǎn)不變性。

為使旋轉(zhuǎn)后結(jié)果與旋轉(zhuǎn)前結(jié)果保持一致，本文構(gòu)造了具有各向同性的刪除模板。如圖4所示，新算法中具有各向同性的D類刪除模板是12個(gè)，且模板中限制點(diǎn)比Ma算法中少。改進(jìn)刪除模板是基于圖2中四類基本模板，通過繞三個(gè)中軸旋轉(zhuǎn)獲得，在結(jié)構(gòu)上是完全對(duì)稱的，從而保證在各個(gè)方向模板是同性的，使新算法具有旋轉(zhuǎn)不變性。

為準(zhǔn)確表達(dá)該算法，做如下定義：

定義2（真?zhèn)蝿h 除點(diǎn)）：在每次迭代中，通過與刪除模板的匹配，簡單點(diǎn)、非尾點(diǎn)的判斷選出候選點(diǎn)，假設(shè)所有候選點(diǎn)被刪除，再逐個(gè)檢驗(yàn)候選點(diǎn)被同時(shí)刪除后26鄰域內(nèi)目標(biāo)體的數(shù)目和背景組的數(shù)目有沒有改變，若改變稱為偽刪除點(diǎn)，若未發(fā)生變化稱為真刪除點(diǎn)。

每次迭代中對(duì)符合刪除模板且滿足其他刪除條件的目標(biāo)點(diǎn)做標(biāo)記，假設(shè)標(biāo)記點(diǎn)已全部被刪除（值為0），逐個(gè)對(duì)標(biāo)記點(diǎn)位置進(jìn)行檢測(cè)，檢測(cè)標(biāo)記點(diǎn)位置26鄰域中目標(biāo)點(diǎn)（黑點(diǎn)）的連通性，和18鄰域中背景點(diǎn)的連通性，若連通性發(fā)生改變則把標(biāo)記點(diǎn)重置為1，若未改變確定刪除。因?yàn)樵谝淮蔚腥魏吸c(diǎn)的刪除不應(yīng)該改變其26鄰域中目標(biāo)點(diǎn)的連通性和18鄰域中背景點(diǎn)的連通性。這就有效防止同時(shí)刪除一系列點(diǎn)造成細(xì)化結(jié)果出現(xiàn)斷裂破壞拓?fù)浣Y(jié)構(gòu)的可能。

連通性證明：本文算法按照簡單點(diǎn)的定義選候刪除點(diǎn)，為保證被刪除的點(diǎn)是簡單點(diǎn)，在刪除前做如下判斷：判斷當(dāng)前點(diǎn)26鄰域內(nèi)的目標(biāo)點(diǎn)是否連通；判斷當(dāng)前點(diǎn)18鄰域內(nèi)的背景點(diǎn)是否連通且至少有一個(gè)點(diǎn)與當(dāng)前點(diǎn)是6鄰接，所以被刪除的點(diǎn)都是簡單點(diǎn)，滿足條件①。通過刪除點(diǎn)的真?zhèn)悟?yàn)證表明對(duì)每一個(gè)刪除點(diǎn)來說，在其他點(diǎn)被刪除后，26鄰域內(nèi)仍然只有一個(gè)目標(biāo)體，18鄰域內(nèi)只有一個(gè)背景組，即還是簡單點(diǎn)，所以每次迭代中同時(shí)刪除的所有點(diǎn)的集合是一個(gè)簡單點(diǎn)集合。那么屬于一個(gè)單位正方形上的兩個(gè)，三個(gè)或四個(gè)不同點(diǎn)被同時(shí)刪除時(shí)，它們也是簡單點(diǎn)集合，表明本文算法滿足條件②、③、④。假設(shè)存在一個(gè)包含在單位立方體內(nèi)的目標(biāo)體被完全刪除，那么單位立方體內(nèi)八個(gè)點(diǎn)只能是可被刪除的點(diǎn)或者背景點(diǎn)，可被刪除的點(diǎn)必須滿足某一刪除模板，根據(jù)根據(jù)本文算法設(shè)計(jì)的刪除模板特點(diǎn)，八個(gè)點(diǎn)中總有一個(gè)面上的四個(gè)點(diǎn)必須同時(shí)是背景點(diǎn)，因此包含在一個(gè)單位立方體內(nèi)能被完全刪除的目標(biāo)體不存在，即滿足條件⑤。因此本文算法滿足三維細(xì)化算法保持連通性的條件。

基于保拓?fù)浣Y(jié)構(gòu)具有旋轉(zhuǎn)不變性的三維細(xì)化算法主要步驟：

1）檢測(cè)邊界點(diǎn)（26鄰域內(nèi)至少有一個(gè)是背景點(diǎn)）；

2）檢測(cè)滿足任一刪除模板同時(shí)屬于非尾點(diǎn)和簡單點(diǎn)的點(diǎn)，并標(biāo)記為候刪除點(diǎn)；

3）根據(jù)定義2判斷2）中標(biāo)記的候刪除點(diǎn)的真?zhèn)?，若為真，則確認(rèn)刪除，否則不刪除；

4）返回1）直到無任何點(diǎn)可以被刪除。

四、 物體的尺寸提取與非接觸測(cè)量

對(duì)細(xì)化后的骨架進(jìn)行像素?cái)?shù)的統(tǒng)計(jì)可以得到三維模型的幾何尺寸信息，這些測(cè)量信息可以精準(zhǔn)地描述三維模型的當(dāng)前狀態(tài)。比如表面即為邊界點(diǎn)的集合，通過判斷是否具備空間26連通可以快速提取邊界點(diǎn)，表面積可以表示為邊界點(diǎn)像素的總和，這種表示方法不僅簡單，而且被證明是物體表面積的無偏和一致的最好估計(jì)。

根據(jù)三維圖像數(shù)據(jù)和尺寸基準(zhǔn)線，可提出和計(jì)算目標(biāo)的厚度、高度、徑向、軸向、位置等幾何尺寸，計(jì)算各組成部分的長度、高度、寬度或直徑、半徑等形狀參數(shù)，計(jì)算表面各部分的幾何距離，有關(guān)結(jié)構(gòu)與重要基準(zhǔn)面、基準(zhǔn)線的距離以及平行度、平面度、圓度、同軸度等形位誤差。用這一系列參數(shù)和特征準(zhǔn)確表達(dá)和確定目標(biāo)的實(shí)際當(dāng)前狀態(tài)，從而實(shí)現(xiàn)對(duì)目標(biāo)的全方位的非接觸測(cè)量。

五、實(shí)驗(yàn)結(jié)果與分析

該部分設(shè)置了四個(gè)實(shí)驗(yàn)。在前兩個(gè)實(shí)驗(yàn)中把新算法分別和Ma的算法，Wang的算法做對(duì)比，表明新算法在保持連通性方面的優(yōu)勢(shì)；在第三個(gè)試驗(yàn)中把新算法與Wang的算法的細(xì)化結(jié)果做對(duì)比，表明新算法具有旋轉(zhuǎn)不變性；第四個(gè)實(shí)驗(yàn)是新算法細(xì)化各類模型得到的精準(zhǔn)的骨架。

新算法與Ma算法的細(xì)化結(jié)果對(duì)比如圖5所示，在圖5.（a）中是一個(gè)連續(xù)的簡單模型，圖5.（b）中是Ma算法的細(xì)化結(jié)果，左右連在一起的兩個(gè)方形在細(xì)化后被分開，破壞了原有的連通性，圖5.（c）中是新算法的細(xì)化結(jié)果。左右兩個(gè)方形細(xì)化后任連在一起，保持了原有的拓?fù)浣Y(jié)構(gòu)。在圖6.（a）中是一個(gè)連續(xù)的簡單模型，圖6.（b）中是Ma算法的細(xì)化結(jié)果，上下連在一起的兩個(gè)方形在細(xì)化后被分開，破壞了原有的連通性，圖6.（c）中是新算法的細(xì)化結(jié)果。上下兩個(gè)方形細(xì)化后任連在一起，保持了原有的拓?fù)浣Y(jié)構(gòu)

六、結(jié)論

完全并行基于模板的細(xì)化算法，會(huì)出現(xiàn)斷裂，導(dǎo)致細(xì)化結(jié)果拓?fù)浣Y(jié)構(gòu)發(fā)生改變，并且不具有旋轉(zhuǎn)不變性，本文通過設(shè)計(jì)各向同性模板，判斷后刪除點(diǎn)的真?zhèn)谓鉀Q了這一問題，并通過實(shí)驗(yàn)進(jìn)行了驗(yàn)證；在三維細(xì)化的基礎(chǔ)上實(shí)現(xiàn)了非接觸測(cè)量，提取三維特征信息，這將進(jìn)一步滿足對(duì)三維模型特征分析的需求。

參 考 文 獻(xiàn)

[1]廖開陽，張學(xué)冬，章明珠.一種新的指紋圖像快速細(xì)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（5）：93-95.

[2]鄧剛，童學(xué)鋒.FPTA快速細(xì)化算法在脫機(jī)手寫體漢子識(shí)別中的應(yīng)用.計(jì)算機(jī)工程與應(yīng)用，2002，01：135-136

[3] Chuang JH， Tsai CH， Ko MC. Skeletonization of three-dimensional object using generalized potential field[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000，22（11）： 1241-1251.

[4]侯培，田慶國，葛寶臻.基于優(yōu)化DRG的三維人體點(diǎn)云骨架提取算法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（18）：182-187.