摘  要： 用三維光學測量系統進行測量時，由于周圍環境、人、設備等各方面的影響，測量數據中常常會摻入噪聲。針對體外飛點和離群成簇噪聲分別采取基于K_近鄰搜索的平均距離去噪算法和改進的基于近鄰點距傳播的去噪算法進行處理，取得了較好的去噪效果。針對直接測量或者多次測量拼接獲取的點云存在“粗糙毛刺”和點云多層重疊的狀況，采用基于MLS的擬合平面投影光順算法進行光滑處理，去除“粗糙毛刺”和打薄重疊區域。該光順去噪預處理算法已經成功運用到三維測量系統的點云處理模塊中。
關鍵詞： 去噪；光順；MLS；點云數據；K_近鄰

    逆向工程是將現有實物產品利用數據采集設備獲取物體外表面三維信息，再將數據進行處理及分析，最后實現產品的三維信息數字化，重建三維模型，對產品模型進行二次設計、修改及優化。物體三維數據采集設備從采集方式上可以分為兩種類型：接觸式和非接觸式。其中，基于結構光的非接觸式測量是當前及今后優先發展的重點，它具有快速、全面獲取物體三維外形數據且對物體無損傷、對自然環境無污染的優點。但是由于測量環境、人、設備等因素的影響，采集到的點云中往往含有大量的噪聲，難以被直接應用于物體三維模型的重建。為了使點云數據能夠運用到后期的處理過程，滿足曲面擬合及造型設計等對數據高質量的要求，必須先對原始數據進行去噪、光順方面的預處理。逆向工程與三維測量技術的迅速發展也推動了去噪光順研究的進展，國內外許多研究學者在這方面做了深入的研究，如基于局部曲面擬合的MLS方法[1]，基于Scale-Space理論的拉普拉斯方法[2]等。近年來，傳統的網格模型去噪和光順算法得到了長足的發展。其中很多網格模型的去噪和光順算法可以直接擴展到點模型上，比較經典的有Fleishman的雙邊濾波去噪算法[3]。
    本文針對點云數據所含噪聲以及點云特點進行分析，然后采用不同的算法進行去噪和光順處理。
1 去噪光順算法
    三維測量系統獲取的點云數據中混雜的噪聲大致可以分為3種：(1)體外飛點，偏離實測數據較遠，懸浮在主體點云外圍的孤立、稀疏點；(2)離群成簇噪聲，偏離主體點云較遠，小而密集的噪聲簇；(3)混雜噪點，噪聲點和真實點混雜在一起，該種點云的形態與實體中心點云成分層狀，直觀表現為點云表面很多“粗糙毛刺”。
1.1 體外飛點去除算法
    針對體外飛點無序、散亂的特性，本文采用空間單元柵格法[4]建立點云數據點之間的空間拓撲關系進而搜索每個點的K_近鄰。首先讀入測量數據點，將三維坐標點存入一個一維數組Array[]，同時得到其X、Y、Z坐標的最大、最小值，這樣可以做一個與各個坐標軸平行的大長方體柵格，包圍所有的三維點。根據數據點的密度將長方體柵格劃分為多個小立方體柵格，并判斷每個數據點所在的小立方體柵格，將數據點的序號追加到該立方體柵格對應的線性鏈表中。

    確定好當前點所在小立方體柵格的索引號后，對其所在小立方體及相鄰的上、下、左、右、前、后共27個小立方體柵格中查找K個最近鄰的點，求取pi的K_近鄰。實驗時K取20。
    建立好散亂點之間的拓撲關系，搜索到每個點的K_近鄰之后，采用平均距離法進行噪聲點去除。算法如下：
    (1)讀入三維散亂點云數據P；
    (2)利用空間單元柵格法建立點云拓撲關系；
    (3)搜索點云中任意一點pi∈P的K_鄰域NB(pi)；
    (4)計算當前pi與其K_鄰域內K個點之間的距離，取其平均值M(pi)；
    (5)判斷該平均距離M(pi)是否超過設定的閾值M?滓，若超過，則認為該點是離群噪聲點，將其刪除；
    (6)重復步驟(3)~步驟(5)，直到處理完整體點云中所有的數據點。
1.2 離群成簇噪點的去除
    有些測量數據中會出現一部分離主體點云(即被測物體點云)較遠的小片點云和離散點，它們稱之為“離群點簇”。含有成簇噪聲的點云數據，由于主體點云數據點的數量比離群點的數量大得多，所以計算每一片點云中數據點的數目，認定數目最多的點云為主體點云，其余均為離群點，可以進行刪除處理。
    本文采用改進的近鄰點距離傳播算法去除離群成簇噪聲。近鄰點距離傳播算法[5]主要用來計算每片點云的數量，其主要思想是：設定點與其近鄰點的距離閾值，并假設某一點為種子點，向其K_近鄰中以點與點之間距離小于閾值的約束進行傳播，獲取相對應的K_近鄰的點；接著以傳播得到的點作為新的種子點，再向各自K_近鄰中距離小于設定閾值的點做傳播。注意，每個點只能被傳播一次，傳播的同時記錄點云數據中點的個數。當傳播不能繼續時，說明此片點云數據已經被傳播完畢，且點的數目計算完畢。再次重新尋求未被傳播到的點作為新的種子點，繼續傳播。這樣一直到計算完每片點云點的數目。最后，點數多的即是主體點云，剩余的為離群點，將要被刪除。具體算法流程如下：
    (1)創建一維數組mark[i]=-1，{i=1，2，3，…，N}，記錄含點的柵格屬于哪片點云。其中N為全部點云中點的總個數；
    創建兩個動態存儲容器vec_1、vec_2分別記錄每個數據點對應的序號；
    創建int類型number，并賦初始值為0；
    設定點距離閾值為threshold_dist；
    設定K的取值，建立各點的K_近鄰；
    完成初始化。
    (2)依次檢查并記錄mark[i]，如果mark[i]=-1，則number=number+1，mark[i]=number，然后把對應的i值追加到vec_1并轉到步驟(3)執行；對每個i值遍歷完以后，轉到步驟(4)。
    (3)分別以vec_1中的每個序號對應的數據點作為種子點，順序查看其K_近鄰數據點，如果數據點與種子點的幾何距離dist<threshold_dist，并且該數據點對應的mark[i]=-1，則使mark[j]=number，并把此數據點的序號j追加到vec_2，否則繼續查看K_近鄰的下一個數據點。當vec_1中的序號對應的數據點都做過了種子點后，刪除vec_1中的所有元素。然后，如果vec_2為空，轉到步驟(2)；否則，以vec_2中的每個序號對應的數據點為種子點，順序查看其K_近鄰點，如果數據點與種子點的幾何距離dist<threshold_dist，并且該數據點對應的mark[i]=-1，則使mark[j]=number，并把此數據點的序號j追加到 vec_1，否則繼續查看K_鄰近的下一個數據點。當vec_2中的序號對應的數據點都做過了種子點后，刪除vec_2中的所有元素。如果vec_1為空，轉步驟(2)，否則繼續步驟(4)。

1.3 光順算法
    在三維光學測量過程中，由于人為、環境等因素干擾，會出現“粗糙”點云數據，再者多次測量結果拼接后會出現點云疊層的情況。為了減少“粗糙毛刺”和疊層對測量數據后期處理和造型造成影響，本文采用基于移動最小二乘擬合平面投影法對測量數據中的“粗糙毛刺”和重疊層進行光滑處理。

    隨著逆向工程的廣泛應用和三維測量技術的發展，人們對曲面造型設計的技術要求越來越高，對點云數據預處理效果的要求也越來越高。本文對三維光學測量系統獲取的含噪點云進行分析，對不同的噪聲類型采取不同的去噪光順預處理方法來獲取高質量的點云。實驗結果表明，本文的算法去噪光順速度高、穩健性強，具有較高的實用價值。
參考文獻
[1] ALEXA M，BEHR J，FLEISHMAN S，et al.Point set surfaces[C].Processing of IEEE Visualization 2001，San Diego，California，21-26 October 2001，IEEE，Piscataway，New Jersey，2001：21-28，537.
[2] LANCASTER P，SALKAUSKAS K.Surfaces generated by  moving least squares methods[J].Mathematics of Computation，1981，37(155)：141-159.
[3] FLEISHMAN S，DRORI I，COHEN-Or D.Bilateral mesh denoising[J].ACM Transactions on Graphics(TOG)，2003，22(3)：950-953.
[4] 張毅，劉旭敏，隋穎，等.基于K-近鄰點云去噪算法的研究與改進[J].計算機應用，2009，29(4)：1011-1014.
[5] 王雪英.離群點預處理及檢測算法研究[D].成都：西南交通大學，2009.