?？★w，趙利民，王瀚斌

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

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

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

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

2 算法的基本流程

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

2.1 初始化

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

2)fori=1 toN；

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

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

5)end if；

6)end for；

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

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

圖1 初始化示意圖

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

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

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

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

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

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

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

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

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

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

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

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

2.3 簇細分

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

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

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

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

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

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

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

2.4 點云精簡誤差評定

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

(1)

(2)

3 實驗與分析

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

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

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

圖2 葉片模型精簡圖

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

圖4 Dragon模型精簡示意圖

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

圖5 Horse模型精簡示意圖

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

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

表1 簡化結(jié)果對比圖

續(xù)表1

4 結(jié) 論

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