基于邊界保留的k-means聚類點云精簡算法研究

常俊飛，趙利民，王瀚斌

(1.遼寧工程技術大學 測繪與地理科學學院，遼寧 阜新 123000;2.廣東省核工業地質局二九二大隊，廣東 河源 517001;3.中國電建集團北京勘測設計研究院有限公司, 北京 100024)

由于測量技術的不斷發展，對物體表面的測量精度和效率也越來越高，測量得到的數據量非常大，存在著大量的冗余數據，增加了后續建模等工作的難度。因此如何提取點云數據中反映曲面特征的點，去除冗余數據，即對測量數據進行精簡有助于提高建模效率和建模質量，是逆向工程中的一項關鍵技術。數據精簡的最佳效果是使精簡后的數據點云具有較少的數據量，同時又能保證不丟失物體表面的細節特征，且速度越快越好。已有研究人員和科學工作者提出了多種方法，但均存在不完善之處[1-12]。因此，本文針對傳統的柵格法與曲率法對數據模型進行精簡時很容易剔除特征點，具有較高的誤判率，導致精簡后的數據不能較好地突出點云數據的特征，使重構后的實體模型精度下降等問題，提出基于邊界保留的k-means聚類算法對點云進行自適應精簡。

1 K-means聚類算法的基本思想

1967年，MacQueen J提出了k-means聚類算法，用來處理數據聚類的問題[13]，該算法由于其算法簡便，又較早提出，因此在科學和工業領域的應用極為廣泛。該算法解決的是將含有n個數據點(實體)的集合劃分為k個類簇Cj的問題(j=1，2，…，k)。算法首先隨機選取k個數據點作為k個類簇的初始簇質心，集合中每個數據點被劃分到與其距離最近的簇質心所在的類簇之中，形成k個聚類的初始分布。對分配完的每一個類簇計算新的簇質心，然后繼續進行數據分配過程，這樣迭代若干次后，若簇質心不再發生變化，則說明數據對象全部分配到自己所在的類簇中，聚類準則函數收斂，否則繼續進行迭代過程，直至收斂。這里的聚類準則函數一般采用聚類誤差平方和準則函數。該算法的一個特點即是在每一次的迭代過程中都要對全體數據點的分配進行調整，然后重新計算簇質心，進入下一次的迭代過程，若在某一次迭代過程中，所有數據點的位置沒有變化，相應的簇質心也沒有變化，此時標志著聚類準則函數已經收斂，算法結束。然而，k均值聚類算法對初始質心的依賴性較強，不同集群的初始化會產生不同的結果，為了避免初始化質心帶來聚類不穩定的問題，使用k-d樹來進行質心的初始化，并且可以保證質心均勻分布。

2 算法的基本流程

目前，K-means聚類多應用于數據挖掘、模式識別、決策支持、機器學習及圖像分割等領域。2016年張帆等利用K-means聚類算法進行了DEM的簡化，效果較好。因此，本文提出基于邊界保留的k-means聚類算法對點云進行精簡，算法包括3個步驟：初始化、點云模型邊界提取及劃分和簇細分。

2.1 初始化

1)在三維空間中，使用輸入的點數N建立一個k-d樹；

2)fori=1 toN；

3)if不是標定點，那么以固定半徑對的鄰域進行搜索；

4)標記固定半徑的鄰域；

5)end if；

6)end for；

7)選擇非標記點作為初始聚類質心。

圖1為k均值聚類的一個例子。

圖1 初始化示意圖

2.2 點云模型邊界提取和劃分

三維點云不僅包含物體的平面信息，還包含物體的高程信息，但是根據人們的習慣，X，Y組成的二維平面攜帶的細節信息相對較多，因此為了在保留點云邊界的同時不影響算法效率，僅獲取X-Y兩個方向的邊界，Z軸信息不會缺失[14]。所以只需將模型的X，Y兩個方向的邊界點云提取即可，具體步驟如下：

1)根據所有點云數據的X坐標大小進行升序排列，排序完成后，將點云數據按照從小到大的順序進行分組，并將每組的個數閾值設為T(T是根據點云的疏密情況來選擇不同的值)；

2)對每組中的點云數據進行Y坐標值的比較，記錄下最大值和最小值點，并保留；

3)同理，根據所有點云數據的Y坐標大小進行升序排列，排序完成后，將點云數據按照從小到大的順序進行分組，并將每組的個數閾值設為T;

4)對每組中的點云數據進行X坐標值的比較，記錄下最大值和最小值點，并保留；以此操作，可以提取模型邊界。

對邊界點提取后，要判定該邊界點所在的簇是否遠離了簇質心，如若遠離，需要對該簇進行分解，關于距離 “遠近”的判定，文獻[15]給出相應的判定準則，具體如下：

1)計算該質心與鄰近質心的距離，并求其均值，記為DC；

2)計算邊界點所在簇的所有點的平均距離，最大值記為MaxDM；

3)如果MaxDM大于DC，邊界簇的質心遠離邊界；

4)該邊界簇將被細分為兩個新的子簇，一個質心位于原始的質心點，另一個位于簇中所有元素平均距離最大的地方；

5)使用k均值聚類算法重新對點云進行聚類，直至滿足要求。

2.3 簇細分

一般來說，在低曲率區域，簇成員在彼此的空間域和功能域是非常相似的，因此簇質心可以代表整個簇。而在高曲率區域，簇成員可能存在更細致的特征而在彼此的空間域和功能域是不相似的。如果用簇質心來代替整個簇，那么有些特征將會消失。為了準確，初始簇被遞歸分解為小的子簇直到成員在彼此的空間域和功能域是相似的。Pauly 等引入層次聚類方法，采用從上到下的方式把點云分為小的子集。如果簇單元的大小超過用戶指定的大小或者變化閾值的上限，那么它將會被分解，然后，分解過程將從原始的輸入數據開始，很明顯點云作為一個大的集群將會消耗很多時間[5]。Lee 等采用基于八叉樹的空間分解方法，把三維網格立方體遞歸劃分為8個叉，并把該點的法向量的標準偏差作為細分的標準。由于每一次每個立方體分為8個叉，所以將會有很多點留在高曲率區域[4]。在本節中，應用點的曲率偏差來評價特征區域中的相似性。其優點是不僅可以確定簇成員是否相似，也可以找到存在偏差的位置。具體步驟如下：

1)對簇中每個點進行估計曲率計算，分別記為ki，并將最大曲率值和最小曲率值記為kmax和kmin；

2)設置曲率偏差閾值Kth，若簇中kmax-kmin

3)若簇中kmax-kmin>Kth，那么說明簇中的點處在曲率變化比較大的地方，需要對該簇進行分解為兩個新的子簇，其中曲率最大值和曲率最小值的點分別為新的簇質心；

4)使用標準k均值聚類步驟把簇中的其他成員分配為兩個新的質心，然后生成兩個子簇；

5)重復以上步驟，直到新生成的簇滿足終止條件。終止條件是當法向量偏差的最大值小于給定的限差Kth，或者簇中只有一個點。

通過以上算法可以得出，低曲率區域的點云由于曲率變化小，可以由簇質心代替。高曲率區域的點云曲率差較大，會不斷分解為多個簇，特征不會消失。

2.4 點云精簡誤差評定

為了評定精簡后點云的準確性，計算原始點集S和簡化后點集S′間的最大誤差和平均誤差。

(1)

(2)

3 實驗與分析

為了驗證本文算法的優越性，分別使用柵格法、曲率法和本文提出的算法對葉片模型、兔子模型、Dragon模型和Horse模型進行精簡(所使用模型已經進行去噪處理)。

葉片模型的精簡結果如圖2所示，3種方法基本上都能保持模型的基本形狀。圖2(a)為原始點云數據，點數為113 432個。其中圖2(b)使用的是柵格法，該方法精簡后點數為68 592個，由于網格的大小一定，針對性不強，某些高曲率區域精簡點數較多，特征不明顯，精簡效果不好。圖2(c)使用的是曲率法，精簡后點云數為68 614個，該方法雖然突出了模型曲率較高的地方，但是在曲率較高的地方保留的點太多，而在曲率較低的地方保留的點數又太少，模型特征消失，達不到重構目的，而且某些邊緣信息也已丟失，精簡效果不好。圖2(d)使用本文提出的新方法k均值聚類精簡算法，精簡后點數為68 579個，該方法在低曲率區域保留了均勻分布的點，而在高曲率區域則保留了必要密度的較多的點，而且邊緣特征也得到保留，效果比柵格法和曲率法好。

圖3為兔子模型精簡示意圖。圖3(a)表示的是原始點云數據，共有33 791個點。圖3(b)表示的是使用柵格法精簡后點云模型，點云個數為16 966個。由圖可知，雖然該方法達到了精簡的目的，但它只是根據距離進行精簡，并沒有考慮模型本身的曲率及特征，精簡效果不好。圖3(c)表示使用曲率法精簡后的點云模型，點云個數為16 869個。由圖可知，曲率法雖考慮了模型本身的曲率高低，但該方法過于突出曲率，致使高曲率區域保留的點太多以致冗雜，低曲率區域的點太少而致某些特征模糊或者消失，精簡效果一般。圖3(d)使用的是本文提出的算法， 精簡后點數為16 912個。由圖可知，在高曲率區域，相對于曲率法而言，本文方法在保留曲率特征的情況下保留點數較少，在低曲率區域保留相對均勻的點來突出模型的特征，并且保留了某些邊緣特征(如兔子后肢的下面部分)。

圖2 葉片模型精簡圖

圖4為Dragon模型的點云精簡示意圖。其中圖4(a)為原始點云數據，點數為29 959個，圖4(b)使用柵格法，該方法精簡后點數為18 012個，由于網格的大小一定，針對性不強，在曲率突變處精簡效果不好，如龍的觸角和尾巴等處，特征已經消失，重構精度低。圖4(c)使用的是曲率法，精簡后點云數為17 975個，該方法雖然突出考慮了模型的曲率，但是在曲率較高的地方保留的點太多(如龍的身體上邊界和龍尾邊界部位)，在曲率較低的地方保留的點數又太少。而且該方法未考慮邊界，使得邊界平坦區域的某些點云(如圖中圓圈部分)消失，精簡效果一般。圖4(d)使用的是本文提出的新方法，精簡后點數為17 983個，由于該方法考慮了邊界，所以邊界點云保留完整，而且在低曲率區域保留了均勻分布的點，在高曲率區域則保留了必要密度的較多的點，特征保持較好，效果優于柵格法和曲率法。

圖4 Dragon模型精簡示意圖

圖5為Horse模型的點云精簡示意圖。圖5(a)為原始點云數據，點數為48 484個。圖5(b)使用的是柵格法，該方法精簡后點數為19 390個，由于網格的大小一定，有些網格包含的點云數量較多則精簡的也越多，相反，網格內包含的點數少則精簡的少，該方法不考慮模型的曲率高低，精簡后模型特征不突出，精簡效果一般。圖5(c)使用的是曲率法，精簡后點云數為19 394個，該方法雖然考慮了模型的曲率，但是在曲率低的地方保留的點數太少(如馬的身體部位)，在頭部和腿部等曲率高的部位保留的點數太多，而且該方法未考慮邊界，使得某些邊緣特征丟失(如圖中馬的耳朵和后蹄部位)，精簡效果一般。圖5(d)使用的是本文提出的新方法，精簡后點數為19 411個，邊界特征保留較好，而且在低曲率區域保留了均勻分布的點，在高曲率區域則保留了必要密度的較多的點，精簡效果較好。

圖5 Horse模型精簡示意圖

為了更加直觀地顯示不同方法精簡后的效果，把結果用表格的形式呈現出來，并且計算原始點集S和簡化后點集S′間的最大誤差、平均誤差和運行時間，結果如表1所示。

由表1可知，通過3種方法對葉片模型、兔子模型、Dragon模型和Horse模型的精簡率基本相同，但是從原始點集S和簡化后點集S′間的最大誤差和平均誤差可知，本文提出的算法使得精簡后的數據與原點云數據的差別較小，更好的保留了物體特征。但由于本文算法進行了聚類和曲率計算，所以運行時間要稍高于傳統的柵格法和曲率法，這也是后續所要研究的內容。

表1 簡化結果對比圖

續表1

4 結 論

針對傳統的柵格法與曲率法對數據模型進行精簡時很容易剔除特征點，具有較高的誤判率，導致精簡后的數據不能較好的突出點云數據的特征，使重構后的實體模型精度下降的問題，本文提出基于邊界保留的K-means聚類算法對點云進行精簡。該方法在精簡過程中不僅考慮了模型邊界，還考慮了模型的曲率高低。從而在精簡過程中不僅在曲率較低處保留一些均勻分布的點，在曲率較高的地方保留必要的密集點，而且保持邊界的完整性，精簡效果優于傳統的柵格法和曲率法。但該算法的時間消耗要稍稍高于柵格法和曲率法，這也是下一步所需要改進的地方。