基于自適應權值的點云三維物體重建算法研究

林　曉， 王燕玲， 朱恒亮， 胡甘樂， 馬利莊， 李魯群

(1. 上海師范大學信息與機電工程學院，上海 200234；2. 洛陽師范學院信息技術學院，河南 洛陽 471022；3. 上海交通大學電子信息與電氣工程學院，上海 200240)

基于自適應權值的點云三維物體重建算法研究

林曉1, 2， 王燕玲2， 朱恒亮3， 胡甘樂3， 馬利莊3， 李魯群1

(1. 上海師范大學信息與機電工程學院，上海 200234；2. 洛陽師范學院信息技術學院，河南 洛陽 471022；3. 上海交通大學電子信息與電氣工程學院，上海 200240)

基于三維掃描點云數據的三維物體重建是計算機圖形學中非常重要的課題，在計算機動畫、醫學圖像處理等多方面都有應用。其中基于最小二乘問題的 Levenberg-Marquart算法和基于極大似然估計的 M-Estimator算法都是不錯的方案。但是當點的數量過多過少或者點云中有噪聲時，這些方案產生的結果都會有較大的誤差，影響重建的效果。為了解決這兩個問題，結合 Levenberg-Marquart算法和 M-Estimator算法，提出了一種新的算法。該算法結合Levenberg-Marquart算法較快的收斂性和M-Estimator算法的抗噪性，能很好地解決點數量較多和噪聲點影響結果的問題。通過在 M-Estimator的權重函數上進行改進，提出自適應的權值函數，用靈活變動和自適應的值代替原來的固定值，使算法在噪聲等級較高時也能表現良好。最后將算法應用在球體和圓柱上，并和最新的研究成果進行對比，數據說明算法無論是在點云數量較多還是在噪聲等級較高的情況下都明顯優于其他已知算法。

Levenberg-Marquart；M-Estimator；自適應權值；點云；重建

基于三維掃描點云數據的三維物體重建已經廣泛地應用于計算機視覺領域，如計算機動畫、醫學圖像處理、科學計算和虛擬現實等。在這方面存在很多優秀的算法，比如基于最小二乘法(Levenberg-Marquart, LM)算法，基于極大似然估計的M-Estimator算法和DirectFitting算法[1]。

前面兩種算法都是基于迭代求解的，而最后一種算法是基于算術求解的，通過數學推導直接算出最后的結果。故在點的數量較少且沒有噪聲時后一種算法無論是在速度還是在準確性上都要優于迭代算法。但是一旦點的數量增加或者點云中夾雜著噪聲時基于迭代求解的算法優勢又體現出來了，在結果的精準性上要明顯高于直接求解的算法。本文算法主要基于迭代求解，故這里重點關注前面兩種算法。

一般通過迭代來解決最小二乘問題，而迭代方法中又有3種是最常用的：①最速下降法。利用方程的一階導數逼近信息，該方法能保證迭代結果的正確性，但是不能保證迭代的速度。尤其在點的數量較多時，迭代收斂的速度非常慢。②高斯牛頓算法。其利用方程的二階導數信息，比最速下降法有了更快的收斂速度，但是降低了迭代結果的正確性。③為了能同時解決迭代速度和結果準確性的問題，研究者們提出了LM算法[2-3]。LM算法結合了前兩種算法的迭代公式，并在算法中根據前一次的迭代結果動態地決定后面的迭代是用最速下降法還是高斯牛頓法。當迭代速度變慢時，會自適應地調用高斯牛頓法來調整迭代的速度；當后一次的迭代誤差比前一次還要大時，說明已經有可能偏離了正確的迭代方向，這時該算法又會自適應地調用最速下降法來調整迭代方向。這樣的自適應調整不僅能保證迭代不會偏離正確的迭代方向，又能保證迭代結果的正確性。但該算法還不是最好的，因為實際應用中三維掃描得到的點云數據一般都有噪聲，因為掃描設備的不同和掃描環境的不同，其結果中的噪聲等級也不相同。噪聲會嚴重影響LM算法的收斂速度和迭代結果的準確性。因此有必要對這些算法做必要的改進使得能夠在處理實際數據時產生較好的結果。基于極大似然估計的M-Estimator[4-8]算子就是為了解決噪聲問題提出的算法，該算法在LM算法的迭代公式中增加一個算子。在每一步迭代中該算子都會對每個迭代點產生一個權值，這個權值將決定這個點對最后的迭代結果產生多大的影響，權值越大說明對結果的影響越大，反之則越小。因為點云中有噪聲點，所以如果能在迭代的過程中將噪聲點的影響消除或減小，噪聲就不會對迭代結果產生太大的影響。該算法在一定程度上解決了這一問題，但是在噪聲等級較大或點的數量太大或太小時還是有較大的誤差。經過仔細研究M-Estimator的算子發現該算子加權在每個點上的值是一個常量值，不會隨著迭代的進行而動態的進行調整，因此不具有靈活性和自適應性。所以才會在噪聲點較多的時候表現的不好。一些研究者也對這些問題進行了研究，李勝男等[9]提出了運用點云的球面三維逆向建模；劉進[10]運用了自適應方法進行CAD模型重建；Liu和Wu[11]通過點云進行了自適應的原始形狀抽取。

針對上述存在的各種問題，本文提出了一種自適應的權值算法。M-Estimator算子在迭代的最初幾步，如果給定的初始值和正確值偏離得比較遠，會使得大部分的數據點都不參與計算，能參與計算的小部分點很有可能是噪聲點，這樣會讓迭代方向出錯，使程序迭代次數增加，迭代的結果也有可能出錯。因此本文提出一種更加靈活的權重函數，無論是在迭代的最初幾步，還是在迭代將要收斂的時候都能讓足夠多的正確點影響最后的迭代結果，并且排除噪聲點或減小噪聲點對最后迭代結果的影響。利用上一次的迭代中每個點產生的誤差信息來動態的決定下一次迭代中每個點的權值，也就是說每個點的前一次迭代誤差會影響到下一次的權重值。通過不停的動態調整，將噪聲點的影響降到最低，從而得到較好的迭代結果。綜上所述，在自適應權值算法中主要有3個創新點：

(1) 自適應權重函數能和LM算法結合的更好，算法有更快的收斂速度。

(2) 不會對給定算法的初始迭代值有很強的依賴性。

(3) 結合本文權重函數，LM算法對噪聲表現出更強的魯棒性。

1　自適應權重函數算法

1.1問題定義

在實際應用中經常需要得到一個物體的幾何表達式，但又不能通過測量的方法，唯一能得到的數據就是通過三維掃描得到該物體的點云數據，并根據這些點云數據重建出物體的幾何表達式。由于掃描設備的問題和環境因素的干擾，導致掃描出來的數據經常有很多噪聲，在重建時還需排除這些噪聲的影響，否則重建的結果將會產生很大的誤差。下面對這個問題給出一個比較嚴格的數據定義。

i程參數。如果f表示的是一個球體，可通過某種方法求出這個球體的球心坐標和球體半徑；如果f表示的是一個圓柱體，需求出圓柱體的半徑和軸線的方向向量。這里f所表示的物體類型是已知的。

1.2自適應權值函數

其中，ρ是一個對稱正定且在原點有唯一最小值的函數。不直接解這個問題，而是將其轉換為一個迭代加權最小二乘問題。設為將要計算的未知數，也就是如下線性方程組的解：

這里的偏導數ψ(x)=dρ(x)/d x稱為影響函數。式(3)定義了權重函數：

現將式(2)用式(4)表示：

式(4)正是求解最小二乘問題的線性方程組：

相應的影響函數ψ(x)為：

權重函數w(x)為：

傳統的算子使得最小二乘問題對噪聲具有更強的魯棒性，但因k值是一個常數使得權重函數式(8)不夠靈活。在迭代的最初幾步，如果給定的初始值和正確值偏離得比較遠，因為k值很小使得大部分的數據點均不參與計算。在噪聲點較多時，能參與計算的小部分點也很有可能是噪聲點，這樣會讓迭代方向出錯，還會使程序收斂的速度下降，并使迭代結果產生較大的誤差。讓k更加靈活，在剛開始迭代時讓更多的正確點能參與計算，或者增大正確點對迭代結果的影響。

設ri的絕對值為所有點的誤差集合，則誤差絕對值的集合可表示為：

該權重函數有以下2個優點：

(1) 在迭代的最初幾步確保大部分的點都能參與計算，不會產生像Huber一樣的問題，這樣算法就不會對初始值的設定產生很大的依賴性。

(2) 在保證大部分點都參與計算的情況下還能保證噪聲點不對迭代結果產生很大的影響，由此確保結果的可信度。

將權重函數和LM算法結合就可得到如式(11)所示的計算迭代方向的表達式：

圖1　算法衍生圖

下面給出算法在球體和圓柱體上的實驗結果，并將其結果和LM算法與M-Estimator算法進行比較。

2　實驗結果

為了方便實驗結果的對比，將給出圓柱體和球體2種情況的實驗結果，較一般的情況同樣也可以用本文算法得出較好的結果。可從幾個方面進行對比。①從點的數量上進行對比，每組實驗均在兩組點上進行，一組點數較多，一組點數較少。②在不同的噪聲等級上比較，具體來說在沒有噪聲和噪聲等級分別為 0.2，0.5，1.0，1.5上進行比較，數值越大噪聲比例越大。③因為參數較多，而且不是每個參數在各個算法中都會產生劇烈的變化，所以只對明顯有不同的參數進行比較。在球體的實驗中，幾種算法產生的結果主要區別在球體的半徑和球心坐標的Z軸上，其他的幾個參數都沒有明顯的不同，所以不做比較；在圓柱體的實驗中，實驗結果的主要區別是在圓柱體的半徑上，圓柱軸線方向向量沒有明顯區別，因此只對半徑進行比較。

圖2中給了兩組球體半徑實驗結果對比，分別為點數采樣比例為1和采樣比例為4，前者點數較多。在兩組圖中給出了球體的標準值為15，如圖中的水平線所示。從圖中可以看出自適應權值算法在5個噪聲等級上明顯要好于LM算法。在點的采樣比例為1噪聲等級達到1.5時，LM算法得出的球體半徑已經和標準值偏離了3個單位，而本文算法只和標準值差1。在噪聲等級為0.2時M-Estimator的半徑值和標準值達到3的差距。在兩個點采樣比例下，當噪聲比例達到1.5時，M-Estimator算出的半徑比本文算法好，這是以其他參數的大誤差為代價的。從下面的球體Z軸的對比結果可以看出這點，如圖3所示。

在圖3中用水平線標出了5個噪聲等級下的Z軸標準值都為0。LM算法和M-Estimator算法在噪聲等級達到0.2后就會出現較大的誤差，最大的誤差達到10，而且變化劇烈，其在實際應用中是不能接受的。雖然本文算法也會有誤差，但相對于另外兩種算法的總體誤差要小，而且變化相對較平緩，從而體現了自適應權值的效果。

圓柱體的半徑實驗結果對比圖如圖4所示。在圓柱體的實驗中其圓柱體的半徑標準值為15，LM算法在噪聲等級高于0.2后半徑就開始出現了較大的偏差，M-Estimator相對于LM算法要好，相對于本文算法要差。

圖5和圖6給出了更直觀的比較。圖5為球體標準圖和3種算法計算出來的圖，其噪聲等級為1.0 和 0.5；標準圖形球心為(0,0,0)，半徑為 15。從兩個圖的分離程度可看出算法的誤差，其中本文算法與標準圖吻合最好。

圖6為圓柱體標準圖和3種算法實驗結果圖，其噪聲等級為1.0和0.5；標準圖形軸向均為(0.866, 0.499, 0)，軸線過(0, 0, 0)，半徑為15。從兩個圖的分離程度可以看出本文算法的精度好于LM算法和Huber算法。

圖2　球體半徑實驗結果對比圖

圖3　球體Z軸實驗結果對比圖

圖4　圓柱體半徑實驗結果對比圖

圖5　球體上的實驗結果對比

圖6　圓柱體上的實驗結果對比

3　總　結

三維點云的重建在計算機視覺領域有很多的應用，如計算機動畫、醫學圖像處理等。從有噪聲的數據中重建出原始物體的模型是項艱巨的任務，雖然有很多算法，但是這些算法對噪聲的魯棒性不是很好，基于此提出了自適應權值算法。將自適應權值函數和LM算法結合起來能對有噪聲的點云進行很好地重建。權重函數在每次迭代時能動態地調整自己對每個點的權重值，從而調整每個點對迭代結果的影響權重，達到自適應調整的目的。通過這樣的自適應調節能更好地排除或減小噪聲的影響，從而達到較好的迭代結果。

通過實驗對比，發現本文算法無論是對較簡單的物體還是復雜的物體都能較好地重建。無論是在速度、還是在精度上都比其他兩種算法要好。但是本文算法在性能上的提升不是很明顯，未來的工作將專注于性能的提升和改進。

[1] Shah T R. Automatic Reconstruction of Industrial installations using point clouds and images [D]. Shanghai: Shanghai Jiao tong University, 2006.

[2] Shakarji C M. Least-squares fitting algorithms of the nist algorithm testing system [J]. Journal of Research of the National Institute of Standards and Technology, 1998, 103(6): 633-641.

[3] Ranganathan A. The levenberg-marquardt algorithm [J]. Tutoral on LM Algorithm, 2004, 11(1): 101-110.

[4] Zhang Z Y. Parameter estimation techniques: a tutorial with application to conic fitting [J]. Image and Vision Computing Journal, 1997, 15(1): 59-76.

[5] Bustos O H, Lucini1 M M, Frery A C. M-Estimators of roughness and scale for-modelled SAR imagery [J]. EURASIP Journal on Applied Signal Processing, 2002, 1: 105-114.

[6] Tyler D E. A distribution-free M-Estimator of multivariate scatter [J]. The Annals of Statistics, 1987, 15(1): 234-251.

[7] Smolic A, Ohm J R. Robust global motion estimation using a simplified M-Estimator approach [J]. Image Processing, 2000, 1: 868-871.

[8] Clark D I, Osborne M R. Finite algorithms for Huber’s M-Estimator [J]. Society of Industrial and Applied Mathematics, 1986, 7(1): 72-85.

[9] 李勝男, 林曉, 陳言, 等. 基于點云的球面三維逆向建模[J]. 圖學學報, 2013, 34(3): 49-52.

[10] 劉進. 自適應的基于點云的 CAD模型重建方法[J].計算機應用, 2013, 33(9): 2617-2622.

[11] Liu J, Wu Z K. An adaptive approach for primitive shape extraction from point clouds [J]. Optik-International Journal for Light and Electron Optics, 2014, 125(9): 2000-2008.

Point-Cloud 3D Object Reconstruction by Using Adaptive Weighting Function

Lin Xiao1,2,Wang Yanling2,Zhu Hengliang3,Hu Ganle3,Ma Lizhuang3,Li Luqun1

(1. The College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai 200234, China; 2. Academy of Information Technology, Luoyang Normal University, Luoyang Henan 471022, China; 3. School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)

3D object reconstruction based on point clouds is an important field in computer graphics which have been used in computer animation, medical image processing and so on. Many good algorithms have been developed to solve this problem such as Levenberg-Marquart algorithm based on least squares and M-Estimator based on maximum likelihood estimation. But all of these algorithms are sensitive to noise and the data number of too lager or too little. And the result of these algorithms would have a larger error, which can influence the effect of reconstruction. In order to solve these problems, we propose a new algorithm which is based on Levenberg-Marquart algorithm and M-Estimator. Our algorithm takes advantage of high convergence of Levenberg-Marquart algorithm and noise proof of M-Estimator, so it can solve two problems mentioned above. And we improved the weighting function of M-Estimator which replaces the constant value with the flexible and adaptive value. This way makes our algorithm to behave very well in large number of points andhigh level of noise. We apply our algorithm on ball and cylinder and compare with the latest research results. From the experimental data we can see that our algorithm behaves much well than the others.

Levenberg-Marquart; M-Estimato; adaptive weighting function; point cloud; reconstruction

TP 391

10.11996/JG.j.2095-302X.2016020143

A

2095-302X(2016)02-0143-06

2015-09-24；定稿日期：2015-10-22

國家自然科學基金項目(U1304616, 61502220)

林曉(1978–)，女，河南南陽人，副教授，博士。主要研究方向為圖形圖像、數字媒體與數據重建。E-mail：lin6008@126.com

李魯群(1967–)，男，山東泰安人，教授，博士。主要研究方向為移動GIS、數字媒體等。E-mail：liluqun@gmail.com