基于改進(jìn)自適應(yīng)k 均值聚類的三維點(diǎn)云骨架提取的研究

魯 斌 范曉明

隨著三維掃描技術(shù)和建模技術(shù)的不斷發(fā)展,點(diǎn)云模型已經(jīng)被廣泛地應(yīng)用于實(shí)際的生產(chǎn)生活和科學(xué)研究[1],相關(guān)的模型處理技術(shù)也在不斷地深入.骨架模型[2]作為三維模型的概括型表現(xiàn)形式,直觀地顯示了模型的拓?fù)溥B接性和幾何結(jié)構(gòu),目前已有很多三維處理技術(shù)如三維重建[3]、模型分割[4-5]、點(diǎn)云配準(zhǔn)[6-7]和模型形狀檢索[8-10]等以此為基礎(chǔ)實(shí)現(xiàn).因此,三維點(diǎn)云技術(shù)的飛速發(fā)展及模型種類的不斷增多對(duì)骨架提取算法的準(zhǔn)確性提出了更高的要求.L1-中值骨架提取算法[11]因其快速高效的特點(diǎn),被廣泛地應(yīng)用于點(diǎn)云模型骨架提取中.該算法基于全局中值的思想,提出應(yīng)用局部中值對(duì)點(diǎn)云提取初始骨架,通過不斷擴(kuò)大鄰域半徑達(dá)到針對(duì)不同區(qū)域?qū)崿F(xiàn)不同程度收縮的目的;同時(shí),根據(jù)點(diǎn)分布情況引入了引力約束和斥力約束來實(shí)現(xiàn)規(guī)整化,可以快速計(jì)算出較好的一維骨架.但該算法也存在隨機(jī)采樣造成的可重復(fù)性差,密度不均勻情況下采樣很容易丟失細(xì)節(jié),以及基于閾值的骨架伸長(zhǎng)導(dǎo)致的錯(cuò)誤骨架連接等問題.

本文針對(duì)以上缺點(diǎn),提出了一種基于改進(jìn)的自適應(yīng)k均值(k-means)聚類引導(dǎo)的L1-中值骨架提取算法,主要的流程圖如圖1 所示.給定一個(gè)三維點(diǎn)云模型,首先采用八叉樹對(duì)散亂點(diǎn)云進(jìn)行組織,每個(gè)體素基于當(dāng)前密度包含的點(diǎn)數(shù)不一;在此結(jié)構(gòu)下完成中值采樣,并利用采樣點(diǎn)集自適應(yīng)確定初始聚類中心實(shí)現(xiàn)k均值區(qū)域劃分,應(yīng)用局部中值迭代收縮得到各區(qū)域內(nèi)的骨架分支;最后通過對(duì)L1局部分支擬合曲線完成骨架平滑及連接.本算法將密度因素及野點(diǎn)的影響考慮到采樣問題中,保證模型的細(xì)節(jié)不會(huì)丟失,同時(shí)減少了后續(xù)骨架提取的迭代次數(shù);區(qū)域劃分約束下提取骨架,解決了跨區(qū)域連接錯(cuò)誤的問題.實(shí)驗(yàn)結(jié)果表明,本文算法與L1-中值骨架提取算法相比,有效地提升了點(diǎn)云骨架的準(zhǔn)確性與可重復(fù)性,可以達(dá)到更好的提取效果.

圖1 本文算法流程圖Fig.1 Flow chart of our proposed algorithm

1 國(guó)內(nèi)外研究現(xiàn)狀

最經(jīng)典的骨架提取技術(shù)是Blum[12]在1967 年提出的中軸變換,該方法能夠快速地提取二維形狀內(nèi)部的一維骨架(中軸線),但對(duì)形狀表面的噪聲十分敏感.Dey 等[13]首先定義了模型中軸面的子集為三維模型的一維曲線骨架.Cornea 等[14]對(duì)現(xiàn)有的一維曲線骨架提取技術(shù)做了很好的綜述,提出了理想骨架應(yīng)該具有的屬性.雖然骨架并沒有一個(gè)完全統(tǒng)一、標(biāo)準(zhǔn)的定義,但大多數(shù)骨架提取的方法都運(yùn)用了中軸的概念,滿足中心性;同時(shí),骨架又不同于中軸,中軸能夠感知到模型的邊界上比較微弱的擾亂,而曲線骨架必須要具備較少的對(duì)模型邊界上的聲音的感知能力,具有魯棒性.

近年來,國(guó)內(nèi)外學(xué)者對(duì)于點(diǎn)云骨架提取問題做了大量的研究工作,可以概括為以下幾類:1)距離變換法:基于幾何三維結(jié)構(gòu)的整體分析,對(duì)節(jié)點(diǎn)進(jìn)行距離變換計(jì)算,形成距離場(chǎng),通過篩選出局部極值點(diǎn)作為骨架點(diǎn)來達(dá)到構(gòu)建整體骨架的目的.此方法在解決整體性比較好、細(xì)節(jié)不多的模型時(shí)效果明顯,對(duì)于模型重構(gòu)也有著很好的借鑒意義,但在離散域中,節(jié)點(diǎn)之間的關(guān)系無法準(zhǔn)確定位,得出的骨架大多不連續(xù),效果較差.2)Laplace 收縮法:由Au 等[15]提出的基于網(wǎng)格的骨架提取代表方法之一,運(yùn)用Laplace 算子的收斂特性,通過反復(fù)平衡牽引將網(wǎng)格收縮到模型的中間位置,可以處理少量點(diǎn)云缺失問題,目前應(yīng)用較為廣泛.因需要反復(fù)調(diào)整Delaunay 三角網(wǎng)格,故時(shí)間復(fù)雜度較高.3)廣義旋轉(zhuǎn)對(duì)稱軸法:利用平滑切割的迭代算法來計(jì)算點(diǎn)云的旋轉(zhuǎn)對(duì)稱軸,然后對(duì)非圓柱形連接區(qū)域進(jìn)行特殊處理以得到一維曲線骨架.該方法利用旋轉(zhuǎn)對(duì)稱性可以實(shí)現(xiàn)有效地缺失彌補(bǔ),但其前提假定模型是圓柱形的,并且過多的預(yù)處理操作極大地增加了時(shí)間復(fù)雜度.4)空間中軸法:Huang 等[11]提出的基于局部中值[16]迭代收縮實(shí)現(xiàn)骨架提取的算法,可以有效抵御野點(diǎn)的影響,避免了傳統(tǒng)骨架提取方法中的預(yù)分割和人工編輯操作,具有較好的應(yīng)用前景.

表1 列舉了這4 類方法最近幾年的代表性文章,并分析了各自的優(yōu)缺點(diǎn)和適用范圍.隨著研究的不斷深入,學(xué)者們也結(jié)合其他方法對(duì)L1-中值算法進(jìn)行了擴(kuò)展,在適用范圍內(nèi)都取得了不錯(cuò)的效果.

表1 三維點(diǎn)云骨架提取方法的比較Table 1 Comparison of three-dimensional point cloud skeleton extraction methods

本文還整理了2011～2019 年點(diǎn)云骨架提取方向的國(guó)內(nèi)外論文共158 篇,基于年度論文發(fā)表數(shù)量及論文數(shù)量累計(jì)和繪制了圖2 所示的柱形-折線圖.總體上說,研究該方向的論文并不是特別多,但隨著骨架提取作為前置工作與三維重建、點(diǎn)云分割、目標(biāo)檢測(cè)等領(lǐng)域技術(shù)的結(jié)合,該方向關(guān)注度呈螺旋式上升的趨勢(shì).

圖2 2011～2019 年點(diǎn)云骨架提取方向論文發(fā)表年度趨勢(shì)圖Fig.2 Annual trend chart of the paper published in the point cloud skeleton extraction field from 2011 to 2019

2 基于八叉樹分割的點(diǎn)云化簡(jiǎn)

2.1 八叉樹分割

將輸入點(diǎn)云體素化,利用八叉樹算法覆蓋輸入點(diǎn)云.選擇基于指針區(qū)域的八叉樹進(jìn)行實(shí)驗(yàn),可以達(dá)到以下3 個(gè)目的:1)把散亂點(diǎn)云數(shù)據(jù)有序組織好,起到索引的作用;2)實(shí)現(xiàn)有計(jì)劃地?cái)?shù)據(jù)簡(jiǎn)化;3)為特征點(diǎn)估計(jì)定義鄰域點(diǎn).

八叉樹分割方法遞歸地將空間上的所有節(jié)點(diǎn)都分解成8 個(gè)一樣的子節(jié)點(diǎn),即在這個(gè)空間上的所有體素的幾何信息是一致的[28].圖3 為八叉樹分割的示意圖,從遞歸結(jié)構(gòu)上可以看出,該方法使用樹遍歷算法來查找節(jié)點(diǎn),并且可以在節(jié)點(diǎn)上遞歸生成新節(jié)點(diǎn),具有良好的拓?fù)浣Y(jié)構(gòu).

圖3 八叉樹分割示意圖Fig.3 Schematic diagram of octree segmentation

本文對(duì)于給定點(diǎn)云模型,首先計(jì)算輸入點(diǎn)云數(shù)據(jù)的一個(gè)包圍框如圖4(a),對(duì)其進(jìn)行八叉樹分割,圖4(b)、圖4(c)給出了分割過程示意圖;若子立方體內(nèi)包含點(diǎn)云數(shù)據(jù)則保留,否則拋棄如圖4(d),重復(fù)上述步驟直至滿足判別條件,分割結(jié)果如圖4(e)所示.基于后續(xù)點(diǎn)云下采樣對(duì)八叉樹的要求,采用固定的最小體素值作為判別條件,此時(shí)均勻排列的體素網(wǎng)格代表著輸入點(diǎn)云的局部表面特征.

圖4 八叉樹分割可視化結(jié)果圖Fig.4 Visualization result diagram of octree segmentation

2.2 八叉樹中值下采樣

基于密度進(jìn)行下采樣把采樣點(diǎn)收縮為骨架點(diǎn),從而生成骨架.對(duì)于一些點(diǎn)云密度不均勻的數(shù)據(jù),隨機(jī)采樣會(huì)使得密度較高的區(qū)域采樣點(diǎn)多,而密度較低的區(qū)域采樣點(diǎn)少,收縮得到的骨架容易丟失細(xì)節(jié),甚至出現(xiàn)較多的小骨架.

針對(duì)這種現(xiàn)象,本文提出基于八叉樹的中值下采樣方法,即取每個(gè)體素中包含的所有點(diǎn)的中值點(diǎn)作為采樣點(diǎn).在此,中值點(diǎn)是基于體素中心進(jìn)行求解的,計(jì)算公式:

式中,ωj=1/‖CJ－qj‖.當(dāng)前體素的點(diǎn)集為 {qj}j∈J,CJ是該體素中心,即點(diǎn)集的均值中心,ωj表示點(diǎn)qj的權(quán)重,與該點(diǎn)到體素中心的距離成反比.由式(1)可知,距離越遠(yuǎn)的點(diǎn)權(quán)重越小,對(duì)中值點(diǎn)的貢獻(xiàn)率也就越小,因此中值點(diǎn)更能抵御野點(diǎn)的影響.

具體實(shí)現(xiàn)如下:首先通過八叉樹進(jìn)行點(diǎn)云數(shù)據(jù)組織并得到體素中心集合(如圖5(a)中心位置的點(diǎn)所示),然后計(jì)算每個(gè)體素內(nèi)的點(diǎn)到中心點(diǎn)的距離以賦予權(quán)重,接著根據(jù)式(1)求得體素中值點(diǎn),最后作為采樣點(diǎn)輸出(如圖5(b)所示).

圖5 均值中心與中值中心對(duì)比圖Fig.5 The mean center versus the median center

圖6 為植物模型點(diǎn)云中值下采樣的過程及結(jié)果.圖6(a)為源點(diǎn)云;圖6(b)表示八叉樹分割點(diǎn)云的可視化過程,可以看出,由于第2.1 節(jié)中八叉樹拆分的終止條件,最終得到的體素大小都是一樣的,故可實(shí)現(xiàn)在點(diǎn)密集的區(qū)域和點(diǎn)稀疏的區(qū)域采樣平衡,達(dá)到消除質(zhì)量差異的目的;圖6(c)中將基于體素中心的均值采樣結(jié)果與本文采用的基于體素中值點(diǎn)的中值采樣結(jié)果進(jìn)行了對(duì)比,左圖均值采樣得到的采樣點(diǎn)排列規(guī)整,在保持源點(diǎn)云結(jié)構(gòu)和尺度的基礎(chǔ)上進(jìn)行了簡(jiǎn)化,右圖中本文采樣方法得到的采樣點(diǎn)保留原有結(jié)構(gòu)的同時(shí)對(duì)分支進(jìn)行了細(xì)化,如枝干部位,這是因?yàn)槿≈兄迭c(diǎn)作為采樣點(diǎn),很好地利用了中值濾波,起到弱化噪聲點(diǎn)和離群點(diǎn)的作用.

圖6 植物模型點(diǎn)云中值下采樣Fig.6 Median down-sampling of plant model point cloud

因此,基于八叉樹的中值下采樣方法,不僅實(shí)現(xiàn)了基于密度的采樣平衡,而且基于中值思想得到的采樣點(diǎn)集收斂于真實(shí)骨架,大大減少了后續(xù)骨架提取的迭代次數(shù).

3 自適應(yīng)k 均值聚類的區(qū)域劃分

本文提出一種基于八叉樹采樣的自適應(yīng)k均值聚類算法對(duì)點(diǎn)云模型進(jìn)行劃分,主要考慮到以下三點(diǎn):1)八叉樹組織點(diǎn)云數(shù)據(jù)可以減少后續(xù)聚類的工作量;2)自適應(yīng)聚類中心和類簇個(gè)數(shù)k可明顯減少迭代次數(shù),同時(shí)降低人為誤差;3)提前劃分區(qū)域可有效降低骨架錯(cuò)誤連接的發(fā)生.

3.1 k 均值聚類算法

k均值聚類算法[29]的主要特征是隨機(jī)確定k個(gè)初始聚類中心,基于距離比較對(duì)源點(diǎn)進(jìn)行歸類劃分并計(jì)算得到新的聚類中心,進(jìn)行下一輪迭代,中心位置不變時(shí)結(jié)束歸類.歸類的過程實(shí)際上也是最小化誤差的過程,k均值最小化,是要最小化所有點(diǎn)與其關(guān)聯(lián)的聚類中心點(diǎn)之間的距離之和,即評(píng)估指標(biāo)(Sum of squared errors,SSE),計(jì)算公式為:

式中,Ci是第i個(gè)類簇,p是Ci中的樣本點(diǎn),mi是Ci當(dāng)前的聚類中心,k值基于先驗(yàn)知識(shí)設(shè)定,即類簇的個(gè)數(shù),也是點(diǎn)云區(qū)域的個(gè)數(shù).SSE 是源點(diǎn)云中所有點(diǎn)的聚類誤差平方和,代表了聚類效果的好壞.

k均值算法中,選擇最近的聚類中心歸類,是為了減小p引起的誤差,而重新定位聚類中心則是用于減小mi引起的誤差,所以每一次迭代都會(huì)將誤差最小化.

3.2 自適應(yīng)k 值

k均值算法中涉及到類簇個(gè)數(shù)k的指定,但在實(shí)際中k值的選擇即給定點(diǎn)云劃分的區(qū)域個(gè)數(shù)非常難以估計(jì).為降低因人為誤差造成劃分結(jié)果的不準(zhǔn)確性以及最小化誤差平方和SSE,本文采用肘部法則對(duì)SSE 曲線圖進(jìn)行分析,以自適應(yīng)得到一個(gè)建議的k值.

肘部法則使用SSE 作為性能度量,SSE 值越小則說明各個(gè)類簇越收斂.但并不是SSE 越小越好,考慮極端情況下將采樣點(diǎn)集內(nèi)的每個(gè)點(diǎn)都視為一個(gè)類簇,那么SSE 的值降為0,顯然達(dá)不到分類的效果.肘部法則為本文提供的是在類簇?cái)?shù)量與SSE 之間尋求一個(gè)平衡點(diǎn)的方法.

應(yīng)用肘部法則計(jì)算得到自適應(yīng)k值的步驟如下:1)確定k值的上限kmax和下限kmin,即可能的最大類簇?cái)?shù)和最小類簇?cái)?shù).由于本文實(shí)驗(yàn)數(shù)據(jù)集均為結(jié)構(gòu)清晰的實(shí)物點(diǎn)云模型,且考慮到骨架提取對(duì)區(qū)域個(gè)數(shù)的約束,本文設(shè)定kmax=10,kmin=2;2)從kmin遞增至kmax,計(jì)算出不同k 值下的SSE,并繪制曲線圖;3)曲線圖下降途中的拐點(diǎn)所對(duì)應(yīng)的k 值,則是相對(duì)最佳的類簇?cái)?shù)量值.此處以從Fast-Scan 三維掃描儀采集的飛機(jī)模型為例,得到如下k-SSE 曲線圖:

由圖7 可以看出,當(dāng)設(shè)定的類簇?cái)?shù)不斷接近最佳類簇?cái)?shù)時(shí),SSE 呈現(xiàn)快速下降態(tài)勢(shì),而當(dāng)設(shè)定類簇?cái)?shù)超過最佳類簇?cái)?shù)時(shí),SSE 仍會(huì)繼續(xù)下降,但下降態(tài)勢(shì)趨于緩慢,因此拐點(diǎn)處的k值已經(jīng)達(dá)到了合適的分類效果,即類簇?cái)?shù)量與SSE 之間的一個(gè)平衡點(diǎn).

圖7 飛機(jī)模型點(diǎn)云的k-SSE 關(guān)系曲線圖Fig.7 k-SSE relation graph of aircraft model point cloud

對(duì)于拐點(diǎn)的確定,為避免目測(cè)法帶來的人為誤差且結(jié)合折線圖的走勢(shì),本文借鑒主成分分析中保留方差百分比的方法,即k 值的選取類似于主成分個(gè)數(shù)的選取,可通過當(dāng)前k值對(duì)誤差平方和SSE 的降低貢獻(xiàn)率來判斷,計(jì)算公式:

在圖7 所示的曲線圖中,拐點(diǎn)k=6 處對(duì)SSE的降低貢獻(xiàn)率已經(jīng)達(dá)到了85.81%,拐點(diǎn)后的k值貢獻(xiàn)率增加不大且接近100%,因此選取拐點(diǎn)為滿足條件的最小k值.經(jīng)實(shí)驗(yàn)證明,μ取0.8 較為合適.

3.3 自適應(yīng)k 均值聚類中心

k均值算法隨機(jī)確定初始聚類中心,很可能會(huì)收斂到局部最優(yōu).實(shí)驗(yàn)證明,初始聚類中心的好壞,對(duì)聚類的效果以及算法的迭代次數(shù)都有著很明顯的影響.

最壞的情況如圖8(b)所示,兩個(gè)初始點(diǎn)選在了同一個(gè)類簇中,很有可能導(dǎo)致原本屬于一個(gè)類簇的點(diǎn)被分成了兩類.另外,初始中心最好選擇數(shù)據(jù)中的點(diǎn),若中心在點(diǎn)云數(shù)據(jù)之外,其移動(dòng)到最終位置勢(shì)必會(huì)增加迭代次數(shù).

圖8 初始中心位置導(dǎo)致分類結(jié)果不同F(xiàn)ig.8 The initial center position results in different classification results

k-means++算法[30]的基本思想是,初始聚類中心之間的相互距離要盡可能遠(yuǎn).結(jié)合以上分析,并考慮到算法中距離計(jì)算的工作量,本文在八叉樹采樣點(diǎn)集中使用k-means++算法來確定初始聚類中心.首先從采樣點(diǎn)集中隨機(jī)選擇一個(gè)點(diǎn)作為第1 個(gè)聚類中心,之后對(duì)于每個(gè)采樣點(diǎn)計(jì)算到最近的聚類中心的距離D(x),輪盤賭法選出下一個(gè)點(diǎn)作為新的聚類中心,直到得到k個(gè)中心點(diǎn).輪盤賭法中每個(gè)點(diǎn)被選擇的概率與D(x)成正比,D(x)越大,被選取作為聚類中心的概率也就越大.

圖9 給出了飛機(jī)模型點(diǎn)云自適應(yīng)得到的k個(gè)初始聚類中心.如圖中圓點(diǎn)標(biāo)注的位置,初始聚類中心正好分散在最終得到的類簇中,避免了因初始中心聚集而導(dǎo)致的迭代次數(shù)的大幅增加.箭頭上的數(shù)字表示自適應(yīng)得到k個(gè)中心的先后順序,驗(yàn)證了kmeans++算法中相互距離盡可能的遠(yuǎn)的取點(diǎn)原則.

圖9 飛機(jī)模型點(diǎn)云的初始聚類中心Fig.9 Initial cluster center of aircraft model point cloud

該方法可以實(shí)現(xiàn)初始聚類中心的分散選取,從而減少聚類迭代次數(shù),大大改善了k均值算法的有效性.算法流程如圖10 所示.

3.4 自適應(yīng)k 均值聚類的算法流程

基于八叉樹采樣的自適應(yīng)k均值聚類算法流程如圖10 所示,具體步驟如下:

圖10 自適應(yīng)k 均值聚類算法流程圖Fig.10 Flowchart of adaptive k-means clustering algorithm

步驟1.初始化k值的上下限參數(shù)kmax、kmin及貢獻(xiàn)率閾值μ,并輸入源點(diǎn)云及采樣點(diǎn)云.

步驟2.令當(dāng)前聚類個(gè)數(shù)為kmin,在采樣點(diǎn)云使用kmeans++算法自適應(yīng)得到kmin個(gè)初始聚類中心.

步驟3.基于初始聚類中心進(jìn)行k均值聚類,計(jì)算源點(diǎn)云所有點(diǎn)到每個(gè)聚類中心的距離,選擇最近的中心進(jìn)行歸類.

步驟4.更新k個(gè)聚類中心的位置,取當(dāng)前簇內(nèi)所有點(diǎn)的平均值作為新的聚類中心.計(jì)算先后中心的距離,若存在中心點(diǎn)移動(dòng),則返回步驟3;否則保存當(dāng)前分類結(jié)果及誤差平方和SSE,k的值加1,若k大于kmax,進(jìn)行下一步,否則利用新k值返回步驟2.

步驟5.在所有分類情況均完成后,利用式(3)得到滿足條件的最小k值,即自適應(yīng)類簇個(gè)數(shù).該k值下的分類結(jié)果即為所求.

步驟6.進(jìn)行類簇染色,使用不同顏色對(duì)類簇加以區(qū)分.

步驟7.停止算法,輸出點(diǎn)云.

圖11 給出了飛機(jī)模型點(diǎn)云完成自適應(yīng)k均值聚類得到的分類結(jié)果.可見,該點(diǎn)云自適應(yīng)區(qū)域個(gè)數(shù)k為6,箭頭指向的點(diǎn)為最終的聚類中心,數(shù)字表示當(dāng)前類簇的索引值,圖中的線段標(biāo)注,表示初始聚類中心到最終聚類中心的直線距離,因自適應(yīng)初始聚類中心確定的好,所以中心位置移動(dòng)不大,且不存在跨區(qū)域移動(dòng),大大減少了聚類的迭代次數(shù).

圖11 飛機(jī)點(diǎn)云自適應(yīng)k 均值聚類的分割結(jié)果Fig.11 Adaptive k-means segmentation results of aircraft point cloud

圖12 分別給出了含羞草模型點(diǎn)云和瑜伽動(dòng)作模型點(diǎn)云完成自適應(yīng)k均值聚類得到的分類結(jié)果.其中,含羞草模型點(diǎn)云自適應(yīng)區(qū)域個(gè)數(shù)k為7,瑜伽模型點(diǎn)云自適應(yīng)區(qū)域個(gè)數(shù)k為6.

圖12 自適應(yīng)k 均值聚類的分割結(jié)果Fig.12 Adaptive segmentation results of k-means clustering

4 骨架提取

4.1 骨架分支的生成

通過八叉樹分割得到一系列采樣點(diǎn)后利用L1-中值骨架算法進(jìn)行區(qū)域內(nèi)骨架收縮提取.骨架收縮提取的基本思想是通過選取采樣點(diǎn)鄰域內(nèi)的中值而不是平均值進(jìn)行收縮,產(chǎn)生新的骨架點(diǎn),不停地迭代并重新將其分配至所在區(qū)域的源點(diǎn)的中心.直接應(yīng)用L1-中值算法往往會(huì)產(chǎn)生稀疏分布,造成結(jié)果中的一些中心點(diǎn)過度收縮產(chǎn)生一團(tuán)點(diǎn)簇.為此使用了一個(gè)調(diào)整函數(shù)在局部空間中軸形成一種排斥力,完成規(guī)整排布.

給定散亂采樣點(diǎn)Q={qj},j∈J?Ω3,以及對(duì)應(yīng)鄰域點(diǎn)X={xi},i∈I?Ω3,利用最優(yōu)化式(4)可得到一系列骨架點(diǎn):

式(4)中第1 項(xiàng)確定局部L1-中值收縮骨架點(diǎn),基于采樣點(diǎn)在輸入點(diǎn)集中的鄰域點(diǎn)的引力作用向局部中值移動(dòng);第2 項(xiàng)規(guī)整項(xiàng),基于采樣點(diǎn)集內(nèi)的鄰域點(diǎn)形成斥力,避免收縮過近,根據(jù)點(diǎn)分布情況[31]見式(5),其中γi是平衡引力和斥力的參數(shù).θ(r)是高斯權(quán)重函數(shù),由式(6)可知,固定鄰域半徑下,距離采樣點(diǎn)越遠(yuǎn),所貢獻(xiàn)權(quán)重也就越小,從而起到了中值濾波的作用.把式(5)代入L1-中值求解項(xiàng)中得出:

實(shí)際情況中,對(duì)于形狀不規(guī)則的模型,區(qū)域點(diǎn)集粗細(xì)不一,給定一個(gè)鄰域半徑難免出現(xiàn)過收縮和欠收縮的情況.為減少迭代次數(shù),本文提出一種基于區(qū)域劃分的自適應(yīng)半徑骨架提取的算法,針對(duì)不同區(qū)域設(shè)定不同的初始鄰域半徑,避免由于初始半徑設(shè)定的太小導(dǎo)致迭代次數(shù)增加;以相同的增長(zhǎng)率擴(kuò)大半徑,尋找新的分支并進(jìn)行骨架連接,對(duì)于已經(jīng)收縮到位的分支進(jìn)行固定.

基于區(qū)域大小以及包含的源點(diǎn)數(shù)計(jì)算不同的鄰域半徑h0,實(shí)驗(yàn)發(fā)現(xiàn),對(duì)于點(diǎn)數(shù)小于五萬的點(diǎn)云收縮成骨架的最大鄰域半徑為 3h0,默認(rèn)值h0=,dbb是指該區(qū)域點(diǎn)云包圍盒對(duì)角線長(zhǎng)度,J指該區(qū)域內(nèi)源點(diǎn)云集合的點(diǎn)數(shù)目.

4.2 基于區(qū)域的骨架連接

使用上述公式計(jì)算收縮得到的粗骨架,在連續(xù)性和平滑性這兩點(diǎn)上還存在不足,甚至?xí)绊懙焦羌艿臏?zhǔn)確性,所以本文在原有最優(yōu)化公式上添加了一個(gè)正則項(xiàng),用于局部分支的曲線擬合,以形成密切聯(lián)系的骨架.定義以下平滑函數(shù):

N(xi)是該點(diǎn)的鄰域點(diǎn)集,v(xi)是鄰域中點(diǎn)的個(gè)數(shù).平滑函數(shù)P(X)通過將鄰域點(diǎn)的距離最小化,來優(yōu)化骨架點(diǎn)的位置,得到局部擬合的曲線骨架.圖13(a)中第3 個(gè)點(diǎn)與它的相鄰點(diǎn)不呈曲線分布,從數(shù)學(xué)角度來講,即在空間坐標(biāo)軸主方向貢獻(xiàn)了方差.應(yīng)用式(8)的平滑函數(shù)最小化方差,則得到了圖13(b)中骨架點(diǎn)的平滑分布.

圖13 局部曲線擬合示意圖Fig.13 Schematic diagram of local curve fitting

基于區(qū)域劃分的骨架連接,由于本身是一個(gè)整體,每個(gè)區(qū)域一般都會(huì)存在跨區(qū)域連接.基于骨架分支擬合曲線,分支兩個(gè)端點(diǎn)沿伸長(zhǎng)方向加值延長(zhǎng)至當(dāng)前鄰域半徑的2 倍,若與其他區(qū)域骨架點(diǎn)相交,則以相交點(diǎn)為端點(diǎn)固定該伸長(zhǎng)分支,并進(jìn)行標(biāo)記,否則偏轉(zhuǎn)角度進(jìn)行連接;若與本區(qū)域內(nèi)骨架點(diǎn)相交,則遍歷該區(qū)域所有骨架是否已存在跨區(qū)域連接,若不存在,待本區(qū)域分支均連接完畢后,再伸長(zhǎng)一個(gè)半徑長(zhǎng)度的活動(dòng)段進(jìn)行尋找,找到則連接,否則結(jié)束骨架連接,示意圖見圖14.最后采用四邊形細(xì)分的方法[32]對(duì)骨架平滑化和橢圓擬合方法[33]進(jìn)行骨架中心化.

圖14 骨架連接示意圖Fig.14 Skeleton connection diagram

5 實(shí)驗(yàn)與分析

為驗(yàn)證算法的提取效果,本文選用點(diǎn)云由FastScan 三維掃描儀采集,是沒有經(jīng)過任何預(yù)處理、包含噪聲或離群點(diǎn)的非均勻密度的點(diǎn)云數(shù)據(jù).該數(shù)據(jù)集[11]包括植物、動(dòng)物、靜物和人體動(dòng)作等15 類三維模型,部分采用本文算法的骨架提取結(jié)果數(shù)據(jù)如表2 所示.

表2 不同模型的實(shí)驗(yàn)結(jié)果對(duì)比Table 2 Comparison table of experimental results of different models

圖15 是在情侶雕塑的點(diǎn)云模型上做骨架提取的結(jié)果,該模型由自適應(yīng)k均值聚類算法大體對(duì)稱地分為了7 個(gè)區(qū)域,涉及多處跨區(qū)域環(huán)狀連接.實(shí)驗(yàn)結(jié)果表明,本文算法可以很好地處理對(duì)稱環(huán)狀連接問題,得到平滑骨架.同時(shí),點(diǎn)云模型中含有部分噪聲和離群點(diǎn),并且掃描出的點(diǎn)云密度并不均勻,在這種情況下,能夠提取出較為理想的骨架,顯示了算法的強(qiáng)魯棒性.

圖15 情侶模型的點(diǎn)云骨架提取Fig.15 Point cloud skeleton extraction of couple model

圖16 是在瑜伽動(dòng)作的點(diǎn)云模型上做骨架提取的結(jié)果,該模型屬于四肢型動(dòng)作模型的一種,身軀和四肢在區(qū)域大小、點(diǎn)數(shù)和形狀上存在差異,且骨架提取在扁平區(qū)域很容易出現(xiàn)過度收縮的現(xiàn)象.實(shí)驗(yàn)表明,在采樣點(diǎn)和區(qū)域分割約束下,提取的骨架具有較高的準(zhǔn)確度,保留了骨架的連續(xù)性.

圖16 瑜伽模型的點(diǎn)云骨架提取Fig.16 Point cloud skeleton extraction of yoga model

圖17(a)含羞草模型中存在葉子點(diǎn)云密度不均勻及數(shù)據(jù)缺失的現(xiàn)象.提取的骨架結(jié)果表明,本文算法對(duì)原始點(diǎn)云的質(zhì)量并沒有嚴(yán)格的先驗(yàn)要求,仍可以提取出較為準(zhǔn)確的骨架線,具有強(qiáng)魯棒性.

圖17 含羞草模型的點(diǎn)云骨架提取Fig.17 Point cloud skeleton extraction of mimosa model

為進(jìn)一步說明本文算法的優(yōu)越性,將其與2 種最先進(jìn)的骨架提取算法L1-中值算法[11]和基于距離場(chǎng)引導(dǎo)的L1-中值算法[18]進(jìn)行了比較.以下是分別在鹿模型、珊瑚模型和較復(fù)雜的樹木模型上進(jìn)行骨架提取的實(shí)驗(yàn)結(jié)果.

圖18 是鹿雕塑的點(diǎn)云模型做骨架提取的結(jié)果,該模型上半部分包含細(xì)小分叉,同時(shí)底部較分支部分尺度和點(diǎn)數(shù)都相差較大;在圖18(b)展示的L1-中值骨架提取結(jié)果中,丟失了很多骨架分支,且存在多處骨架連接錯(cuò)誤,造成這些現(xiàn)象的原因主要有2 個(gè):1)L1-中值算法采用隨機(jī)下采樣使得原本點(diǎn)稀疏的分支點(diǎn)數(shù)減少以致無法形成骨架;2)骨架分支距離過近導(dǎo)致錯(cuò)誤連接;圖18(d)方法[18]的結(jié)果除以上問題外,還出現(xiàn)了錯(cuò)誤的骨架閉環(huán),且該算法本身易受點(diǎn)云缺失的影響,導(dǎo)致模型底部的骨架連續(xù)性較差;然而這些在圖18(c)本文算法得到的結(jié)果中有相當(dāng)明顯的改善,本文通過八叉樹中值采樣保證分支的密度平衡,以減少骨架的丟失,另外區(qū)域劃分對(duì)骨架連接進(jìn)行了約束,提高了骨架準(zhǔn)確率.

圖18 鹿模型的點(diǎn)云骨架提取對(duì)比結(jié)果Fig.18 Comparison results of point cloud skeleton extraction of deer model

圖19 是珊瑚雕塑的點(diǎn)云模型做骨架提取的結(jié)果,該模型形狀可看似骨骼明顯的樹形結(jié)構(gòu),在圖19(b)展示的L1-中值骨架提取結(jié)果中,多處出現(xiàn)骨架不連續(xù),提取效果較差;圖19(d)方法[18]相較于L1-中值算法,雖然在連續(xù)性上有所改善,但仍然丟失了大量的骨架分支;而圖19(c)本文算法通過區(qū)域約束使得提取結(jié)果很好地保持了同一區(qū)域內(nèi)骨架的連通,且盡可能多的保留細(xì)節(jié),極少丟失骨架.

圖19 珊瑚模型的點(diǎn)云骨架提取對(duì)比結(jié)果Fig.19 Comparison results of point cloud skeleton extraction of coral model

圖20 是樹木點(diǎn)云模型做骨架提取的結(jié)果,樹木模型相對(duì)復(fù)雜,含有較多錯(cuò)綜連接的樹杈及細(xì)小無形的枝葉,且較為集中.圖20(b)展示的L1-中值骨架提取結(jié)果中,樹木丟失了接近一半的骨架,且枝葉部分幾乎無骨架分支形成;圖20(d)方法[18]的結(jié)果中不僅丟失了較多關(guān)鍵骨架,而且提取出的骨架離散不連通,效果較差;圖20(c)中本文算法通過區(qū)域劃分首先將枝葉和樹干分類隔開,分別提取骨架再進(jìn)行連接,避免發(fā)生枝葉分離或提取不出骨架的情況,很好地保持了樹干的拓?fù)浣Y(jié)構(gòu),并且具有很好的連通性.

圖20 樹木模型的點(diǎn)云骨架提取對(duì)比結(jié)果Fig.20 Comparison results of point cloud skeleton extraction of tree model

由以上對(duì)比實(shí)驗(yàn)可以看出,該算法提取的骨架比其他方法更準(zhǔn)確,可有效地識(shí)別更多的分支.同時(shí),實(shí)驗(yàn)部分所涉及模型的形狀和拓?fù)浣Y(jié)構(gòu)各異,點(diǎn)云的密度也不盡相同,本文算法仍能得到很好地骨架提取結(jié)果,具有較好的適應(yīng)性,未來可更好地應(yīng)用于其他相關(guān)領(lǐng)域,具有較強(qiáng)的學(xué)習(xí)擴(kuò)展能力.

但同時(shí)該算法也存在著一些缺陷,均勻子空間采樣在保留細(xì)節(jié)的同時(shí)偶爾會(huì)導(dǎo)致產(chǎn)生多余的小骨架,如圖21(b)標(biāo)注,因恐龍腳部點(diǎn)云呈平面分布且離散而收縮成了兩個(gè)骨架分支;另外,局部點(diǎn)云內(nèi)部缺失嚴(yán)重時(shí),易形成局部骨架閉環(huán),如圖22(b).

圖21 恐龍模型的點(diǎn)云骨架提取Fig.21 Point cloud skeleton extraction of dinosaur model

圖22 動(dòng)作模型的點(diǎn)云骨架提取Fig.22 Point cloud skeleton extraction of movement model

6 結(jié)束語

本文針對(duì)傳統(tǒng)骨架提取算法中提取結(jié)果可重復(fù)性差、易丟失細(xì)節(jié)及連接錯(cuò)誤等問題,提出了一種基于改進(jìn)的自適應(yīng)k均值區(qū)域劃分的骨架提取算法,對(duì)骨架提取和連接進(jìn)行約束.該算法利用八叉樹中值采樣,起到抵御野點(diǎn)和平衡點(diǎn)云分布密度的作用;基于采樣點(diǎn)進(jìn)行自適應(yīng)k均值區(qū)域劃分,實(shí)現(xiàn)保留局部細(xì)節(jié);基于區(qū)域自適應(yīng)半徑進(jìn)行L1-中值骨架收縮,有效地減少了工作量.實(shí)驗(yàn)結(jié)果表明,該算法大大減少了迭代次數(shù),有效避免了細(xì)節(jié)的丟失及錯(cuò)誤骨架的連接,具有強(qiáng)魯棒性、高準(zhǔn)確率等優(yōu)點(diǎn).

需要注意的是,本文算法盡管在k均值聚類時(shí)實(shí)現(xiàn)了自適應(yīng)確定參數(shù),可客觀地進(jìn)行合理的區(qū)域劃分,但在L1-中值算法中的參數(shù)仍使用了實(shí)驗(yàn)觀察法,這些參數(shù)對(duì)骨架提取結(jié)果有著一定的影響;同時(shí)提取的骨架結(jié)果保留細(xì)節(jié)的同時(shí)偶爾會(huì)有多余的小骨架產(chǎn)生,且在局部點(diǎn)云內(nèi)部缺失嚴(yán)重時(shí)易形成局部骨架閉環(huán),因此如何更加便捷準(zhǔn)確地確定參數(shù)及完善骨架,這將是下一步重點(diǎn)解決的問題.