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

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

基于自適應(yīng)權(quán)值的點(diǎn)云三維物體重建算法研究

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

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

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

Levenberg-Marquart；M-Estimator；自適應(yīng)權(quán)值；點(diǎn)云；重建

基于三維掃描點(diǎn)云數(shù)據(jù)的三維物體重建已經(jīng)廣泛地應(yīng)用于計(jì)算機(jī)視覺領(lǐng)域，如計(jì)算機(jī)動(dòng)畫、醫(yī)學(xué)圖像處理、科學(xué)計(jì)算和虛擬現(xiàn)實(shí)等。在這方面存在很多優(yōu)秀的算法，比如基于最小二乘法(Levenberg-Marquart, LM)算法，基于極大似然估計(jì)的M-Estimator算法和DirectFitting算法[1]。

前面兩種算法都是基于迭代求解的，而最后一種算法是基于算術(shù)求解的，通過數(shù)學(xué)推導(dǎo)直接算出最后的結(jié)果。故在點(diǎn)的數(shù)量較少且沒有噪聲時(shí)后一種算法無論是在速度還是在準(zhǔn)確性上都要優(yōu)于迭代算法。但是一旦點(diǎn)的數(shù)量增加或者點(diǎn)云中夾雜著噪聲時(shí)基于迭代求解的算法優(yōu)勢又體現(xiàn)出來了，在結(jié)果的精準(zhǔn)性上要明顯高于直接求解的算法。本文算法主要基于迭代求解，故這里重點(diǎn)關(guān)注前面兩種算法。

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

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

(1) 自適應(yīng)權(quán)重函數(shù)能和LM算法結(jié)合的更好，算法有更快的收斂速度。

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

(3) 結(jié)合本文權(quán)重函數(shù)，LM算法對噪聲表現(xiàn)出更強(qiáng)的魯棒性。

1　自適應(yīng)權(quán)重函數(shù)算法

1.1問題定義

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

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

1.2自適應(yīng)權(quán)值函數(shù)

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

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

現(xiàn)將式(2)用式(4)表示：

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

相應(yīng)的影響函數(shù)ψ(x)為：

權(quán)重函數(shù)w(x)為：

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

設(shè)ri的絕對值為所有點(diǎn)的誤差集合，則誤差絕對值的集合可表示為：

該權(quán)重函數(shù)有以下2個(gè)優(yōu)點(diǎn)：

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

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

將權(quán)重函數(shù)和LM算法結(jié)合就可得到如式(11)所示的計(jì)算迭代方向的表達(dá)式：

圖1　算法衍生圖

下面給出算法在球體和圓柱體上的實(shí)驗(yàn)結(jié)果，并將其結(jié)果和LM算法與M-Estimator算法進(jìn)行比較。

2　實(shí)驗(yàn)結(jié)果

為了方便實(shí)驗(yàn)結(jié)果的對比，將給出圓柱體和球體2種情況的實(shí)驗(yàn)結(jié)果，較一般的情況同樣也可以用本文算法得出較好的結(jié)果?？蓮膸讉€(gè)方面進(jìn)行對比。①從點(diǎn)的數(shù)量上進(jìn)行對比，每組實(shí)驗(yàn)均在兩組點(diǎn)上進(jìn)行，一組點(diǎn)數(shù)較多，一組點(diǎn)數(shù)較少。②在不同的噪聲等級上比較，具體來說在沒有噪聲和噪聲等級分別為 0.2，0.5，1.0，1.5上進(jìn)行比較，數(shù)值越大噪聲比例越大。③因?yàn)閰?shù)較多，而且不是每個(gè)參數(shù)在各個(gè)算法中都會產(chǎn)生劇烈的變化，所以只對明顯有不同的參數(shù)進(jìn)行比較。在球體的實(shí)驗(yàn)中，幾種算法產(chǎn)生的結(jié)果主要區(qū)別在球體的半徑和球心坐標(biāo)的Z軸上，其他的幾個(gè)參數(shù)都沒有明顯的不同，所以不做比較；在圓柱體的實(shí)驗(yàn)中，實(shí)驗(yàn)結(jié)果的主要區(qū)別是在圓柱體的半徑上，圓柱軸線方向向量沒有明顯區(qū)別，因此只對半徑進(jìn)行比較。

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

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

圓柱體的半徑實(shí)驗(yàn)結(jié)果對比圖如圖4所示。在圓柱體的實(shí)驗(yàn)中其圓柱體的半徑標(biāo)準(zhǔn)值為15，LM算法在噪聲等級高于0.2后半徑就開始出現(xiàn)了較大的偏差，M-Estimator相對于LM算法要好，相對于本文算法要差。

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

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

圖2　球體半徑實(shí)驗(yàn)結(jié)果對比圖

圖3　球體Z軸實(shí)驗(yàn)結(jié)果對比圖

圖4　圓柱體半徑實(shí)驗(yàn)結(jié)果對比圖

圖5　球體上的實(shí)驗(yàn)結(jié)果對比

圖6　圓柱體上的實(shí)驗(yàn)結(jié)果對比

3　總　結(jié)

三維點(diǎn)云的重建在計(jì)算機(jī)視覺領(lǐng)域有很多的應(yīng)用，如計(jì)算機(jī)動(dòng)畫、醫(yī)學(xué)圖像處理等。從有噪聲的數(shù)據(jù)中重建出原始物體的模型是項(xiàng)艱巨的任務(wù)，雖然有很多算法，但是這些算法對噪聲的魯棒性不是很好，基于此提出了自適應(yīng)權(quán)值算法。將自適應(yīng)權(quán)值函數(shù)和LM算法結(jié)合起來能對有噪聲的點(diǎn)云進(jìn)行很好地重建。權(quán)重函數(shù)在每次迭代時(shí)能動(dòng)態(tài)地調(diào)整自己對每個(gè)點(diǎn)的權(quán)重值，從而調(diào)整每個(gè)點(diǎn)對迭代結(jié)果的影響權(quán)重，達(dá)到自適應(yīng)調(diào)整的目的。通過這樣的自適應(yīng)調(diào)節(jié)能更好地排除或減小噪聲的影響，從而達(dá)到較好的迭代結(jié)果。

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

[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] 李勝男, 林曉, 陳言, 等. 基于點(diǎn)云的球面三維逆向建模[J]. 圖學(xué)學(xué)報(bào), 2013, 34(3): 49-52.

[10] 劉進(jìn). 自適應(yīng)的基于點(diǎn)云的 CAD模型重建方法[J].計(jì)算機(jī)應(yīng)用, 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

國家自然科學(xué)基金項(xiàng)目(U1304616, 61502220)

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

李魯群(1967–)，男，山東泰安人，教授，博士。主要研究方向?yàn)橐苿?dòng)GIS、數(shù)字媒體等。E-mail：liluqun@gmail.com