基于改進自適應k 均值聚類的三維點云骨架提取的研究

魯 斌 范曉明

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

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

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

1 國內外研究現狀

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

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

表1 列舉了這4 類方法最近幾年的代表性文章,并分析了各自的優缺點和適用范圍.隨著研究的不斷深入,學者們也結合其他方法對L1-中值算法進行了擴展,在適用范圍內都取得了不錯的效果.

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

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

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

2 基于八叉樹分割的點云化簡

2.1 八叉樹分割

將輸入點云體素化,利用八叉樹算法覆蓋輸入點云.選擇基于指針區域的八叉樹進行實驗,可以達到以下3 個目的:1)把散亂點云數據有序組織好,起到索引的作用;2)實現有計劃地數據簡化;3)為特征點估計定義鄰域點.

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

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

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

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

2.2 八叉樹中值下采樣

基于密度進行下采樣把采樣點收縮為骨架點,從而生成骨架.對于一些點云密度不均勻的數據,隨機采樣會使得密度較高的區域采樣點多,而密度較低的區域采樣點少,收縮得到的骨架容易丟失細節,甚至出現較多的小骨架.

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

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

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

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

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

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

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

3 自適應k 均值聚類的區域劃分

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

3.1 k 均值聚類算法

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

式中,Ci是第i個類簇,p是Ci中的樣本點,mi是Ci當前的聚類中心,k值基于先驗知識設定,即類簇的個數,也是點云區域的個數.SSE 是源點云中所有點的聚類誤差平方和,代表了聚類效果的好壞.

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

3.2 自適應k 值

k均值算法中涉及到類簇個數k的指定,但在實際中k值的選擇即給定點云劃分的區域個數非常難以估計.為降低因人為誤差造成劃分結果的不準確性以及最小化誤差平方和SSE,本文采用肘部法則對SSE 曲線圖進行分析,以自適應得到一個建議的k值.

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

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

由圖7 可以看出,當設定的類簇數不斷接近最佳類簇數時,SSE 呈現快速下降態勢,而當設定類簇數超過最佳類簇數時,SSE 仍會繼續下降,但下降態勢趨于緩慢,因此拐點處的k值已經達到了合適的分類效果,即類簇數量與SSE 之間的一個平衡點.

圖7 飛機模型點云的k-SSE 關系曲線圖Fig.7 k-SSE relation graph of aircraft model point cloud

對于拐點的確定,為避免目測法帶來的人為誤差且結合折線圖的走勢,本文借鑒主成分分析中保留方差百分比的方法,即k 值的選取類似于主成分個數的選取,可通過當前k值對誤差平方和SSE 的降低貢獻率來判斷,計算公式:

在圖7 所示的曲線圖中,拐點k=6 處對SSE的降低貢獻率已經達到了85.81%,拐點后的k值貢獻率增加不大且接近100%,因此選取拐點為滿足條件的最小k值.經實驗證明,μ取0.8 較為合適.

3.3 自適應k 均值聚類中心

k均值算法隨機確定初始聚類中心,很可能會收斂到局部最優.實驗證明,初始聚類中心的好壞,對聚類的效果以及算法的迭代次數都有著很明顯的影響.

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

圖8 初始中心位置導致分類結果不同Fig.8 The initial center position results in different classification results

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

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

圖9 飛機模型點云的初始聚類中心Fig.9 Initial cluster center of aircraft model point cloud

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

3.4 自適應k 均值聚類的算法流程

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

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

步驟1.初始化k值的上下限參數kmax、kmin及貢獻率閾值μ,并輸入源點云及采樣點云.

步驟2.令當前聚類個數為kmin,在采樣點云使用kmeans++算法自適應得到kmin個初始聚類中心.

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

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

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

步驟6.進行類簇染色,使用不同顏色對類簇加以區分.

步驟7.停止算法,輸出點云.

圖11 給出了飛機模型點云完成自適應k均值聚類得到的分類結果.可見,該點云自適應區域個數k為6,箭頭指向的點為最終的聚類中心,數字表示當前類簇的索引值,圖中的線段標注,表示初始聚類中心到最終聚類中心的直線距離,因自適應初始聚類中心確定的好,所以中心位置移動不大,且不存在跨區域移動,大大減少了聚類的迭代次數.

圖11 飛機點云自適應k 均值聚類的分割結果Fig.11 Adaptive k-means segmentation results of aircraft point cloud

圖12 分別給出了含羞草模型點云和瑜伽動作模型點云完成自適應k均值聚類得到的分類結果.其中,含羞草模型點云自適應區域個數k為7,瑜伽模型點云自適應區域個數k為6.

圖12 自適應k 均值聚類的分割結果Fig.12 Adaptive segmentation results of k-means clustering

4 骨架提取

4.1 骨架分支的生成

通過八叉樹分割得到一系列采樣點后利用L1-中值骨架算法進行區域內骨架收縮提取.骨架收縮提取的基本思想是通過選取采樣點鄰域內的中值而不是平均值進行收縮,產生新的骨架點,不停地迭代并重新將其分配至所在區域的源點的中心.直接應用L1-中值算法往往會產生稀疏分布,造成結果中的一些中心點過度收縮產生一團點簇.為此使用了一個調整函數在局部空間中軸形成一種排斥力,完成規整排布.

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

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

實際情況中,對于形狀不規則的模型,區域點集粗細不一,給定一個鄰域半徑難免出現過收縮和欠收縮的情況.為減少迭代次數,本文提出一種基于區域劃分的自適應半徑骨架提取的算法,針對不同區域設定不同的初始鄰域半徑,避免由于初始半徑設定的太小導致迭代次數增加;以相同的增長率擴大半徑,尋找新的分支并進行骨架連接,對于已經收縮到位的分支進行固定.

基于區域大小以及包含的源點數計算不同的鄰域半徑h0,實驗發現,對于點數小于五萬的點云收縮成骨架的最大鄰域半徑為 3h0,默認值h0=,dbb是指該區域點云包圍盒對角線長度,J指該區域內源點云集合的點數目.

4.2 基于區域的骨架連接

使用上述公式計算收縮得到的粗骨架,在連續性和平滑性這兩點上還存在不足,甚至會影響到骨架的準確性,所以本文在原有最優化公式上添加了一個正則項,用于局部分支的曲線擬合,以形成密切聯系的骨架.定義以下平滑函數:

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

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

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

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

5 實驗與分析

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

表2 不同模型的實驗結果對比Table 2 Comparison table of experimental results of different models

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

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

圖16 是在瑜伽動作的點云模型上做骨架提取的結果,該模型屬于四肢型動作模型的一種,身軀和四肢在區域大小、點數和形狀上存在差異,且骨架提取在扁平區域很容易出現過度收縮的現象.實驗表明,在采樣點和區域分割約束下,提取的骨架具有較高的準確度,保留了骨架的連續性.

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

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

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

為進一步說明本文算法的優越性,將其與2 種最先進的骨架提取算法L1-中值算法[11]和基于距離場引導的L1-中值算法[18]進行了比較.以下是分別在鹿模型、珊瑚模型和較復雜的樹木模型上進行骨架提取的實驗結果.

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

圖18 鹿模型的點云骨架提取對比結果Fig.18 Comparison results of point cloud skeleton extraction of deer model

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

圖19 珊瑚模型的點云骨架提取對比結果Fig.19 Comparison results of point cloud skeleton extraction of coral model

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

圖20 樹木模型的點云骨架提取對比結果Fig.20 Comparison results of point cloud skeleton extraction of tree model

由以上對比實驗可以看出,該算法提取的骨架比其他方法更準確,可有效地識別更多的分支.同時,實驗部分所涉及模型的形狀和拓撲結構各異,點云的密度也不盡相同,本文算法仍能得到很好地骨架提取結果,具有較好的適應性,未來可更好地應用于其他相關領域,具有較強的學習擴展能力.

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

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

圖22 動作模型的點云骨架提取Fig.22 Point cloud skeleton extraction of movement model

6 結束語

本文針對傳統骨架提取算法中提取結果可重復性差、易丟失細節及連接錯誤等問題,提出了一種基于改進的自適應k均值區域劃分的骨架提取算法,對骨架提取和連接進行約束.該算法利用八叉樹中值采樣,起到抵御野點和平衡點云分布密度的作用;基于采樣點進行自適應k均值區域劃分,實現保留局部細節;基于區域自適應半徑進行L1-中值骨架收縮,有效地減少了工作量.實驗結果表明,該算法大大減少了迭代次數,有效避免了細節的丟失及錯誤骨架的連接,具有強魯棒性、高準確率等優點.

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