一種基于累積誤差優(yōu)化分配的多視角拼接方法

湯明輝，程筱勝，崔海華，戴 寧

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

一種基于累積誤差優(yōu)化分配的多視角拼接方法

湯明輝，程筱勝，崔海華，戴 寧

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

多視角三維拼接是三維測量的重要組成部分，為了提高多視角拼接的精度，提出了一種基于累積誤差優(yōu)化分配的多視角拼接方法。根據(jù)多視角點(diǎn)云數(shù)據(jù)的空間位置信息，構(gòu)建環(huán)形拼接生成樹，利用設(shè)計(jì)的環(huán)形結(jié)構(gòu)將拼接產(chǎn)生的累積誤差分散到各個(gè)視角，從而逐步提高整體拼接精度。實(shí)驗(yàn)表明，該方法能獲得令人滿意的拼接精度。

多視角拼接；生成樹；誤差分配；累積誤差

非接觸式測量是由光學(xué)設(shè)備獲取物體表面圖像，進(jìn)行處理后獲得物體表面的三維數(shù)據(jù)。計(jì)算機(jī)技術(shù)以及光電技術(shù)的結(jié)合促進(jìn)了非接觸式測量技術(shù)的發(fā)展和應(yīng)用。然而受限于光學(xué)設(shè)備的視場，在實(shí)際測量過程中，單視角的測量并不能獲取物體完整的表面信息，因此需要將多視角測量的數(shù)據(jù)進(jìn)行拼接。尋找點(diǎn)云或者網(wǎng)格數(shù)據(jù)之間的位置變換關(guān)系，將多片點(diǎn)云或者網(wǎng)格數(shù)據(jù)統(tǒng)一到唯一的全局坐標(biāo)系下，稱為三維點(diǎn)云配準(zhǔn)，在不同場合也被稱為重定位或者三維點(diǎn)云拼接。

多視角拼接中最基礎(chǔ)、最簡單的情況是兩視角的點(diǎn)云拼接，對(duì)兩視角的點(diǎn)云或網(wǎng)格數(shù)據(jù)拼接，國內(nèi)外研究成果眾多。無點(diǎn)云初始位置信息的拼接，稱為粗拼接，需建立三維特征進(jìn)行匹配，從而獲取點(diǎn)云中配對(duì)的點(diǎn)對(duì)，通過計(jì)算獲得點(diǎn)云片間的初始位置?？衫玫娜S特征一般有點(diǎn)簽名[1]、Spin圖像[2]等?；谌S特征的無初始位置拼接往往不能獲得精確位置，仍然需要調(diào)整點(diǎn)云的相對(duì)位置。對(duì)于點(diǎn)云的初始位置已知的兩視角點(diǎn)云拼接，稱為精拼接。迭代最近點(diǎn)[3]算法及其相關(guān)改進(jìn)算法[4]是目前應(yīng)用最廣泛的無特征精拼接方法。迭代最近點(diǎn)算法是將另一片點(diǎn)云中最近的點(diǎn)作為一個(gè)匹配點(diǎn)，獲得大量的匹配點(diǎn)后計(jì)算點(diǎn)云的位置，然后再選擇最近點(diǎn)，如此反復(fù)循環(huán)迭代直至滿足算法結(jié)束的條件(最近點(diǎn)距離小于一定閾值或者迭代達(dá)到一定次數(shù))。

對(duì)多視角點(diǎn)云，若將點(diǎn)云依照兩兩拼接的方式進(jìn)行拼接，微小的誤差會(huì)逐漸累積，累積誤差會(huì)使點(diǎn)云位置錯(cuò)位。相對(duì)于兩視角點(diǎn)云拼接，如何將多視角拼接的累積誤差合理地分配到各視角點(diǎn)云數(shù)據(jù)上，是一個(gè)亟需解決的問題。Kari[5]將計(jì)算點(diǎn)云間重疊區(qū)域所得的百分比，確定為點(diǎn)云之間拼接的可靠性系數(shù)，重疊區(qū)域大的，確定為優(yōu)先拼接的對(duì)象，逐步將所有的點(diǎn)云拼接到一處，從而分配累積誤差。YangChen[6]等人則將拼接完成的點(diǎn)云進(jìn)行融合，未拼接的點(diǎn)云依次拼接到融合完成的點(diǎn)云上，再次融合，如此反復(fù)，直至拼接完成，該方法分配累積誤差的方法并不均勻。Sharp[7]等人則將累積的誤差均勻分配到各點(diǎn)云中，并未考慮不同點(diǎn)云間大小不同的重疊區(qū)域?qū)φ`差分配的影響。也有一些學(xué)者另辟蹊徑，如Takeshi Masuda[8]利用空間中的采樣點(diǎn)建立有向距離場(Signed Distnce Field， SDF)來調(diào)整各點(diǎn)云之間的相對(duì)位置，在采樣點(diǎn)足夠密集，而且點(diǎn)云的起伏變化并不劇烈時(shí)，該方法可以獲得良好的拼接效果，該方法的另一優(yōu)勢(shì)在于可以同時(shí)調(diào)整所有視角的點(diǎn)云姿態(tài)。

本文提出了一種多視角點(diǎn)云數(shù)據(jù)拼接的新方法，拼接構(gòu)成的累積誤差根據(jù)點(diǎn)云間的重疊區(qū)域的大小來分配，相較于均勻分配的方式，該方法更為可靠合理。該方法采用生成樹來表示點(diǎn)云之間的拓?fù)潢P(guān)系，從而避免了窮舉所有的點(diǎn)云組合關(guān)系來進(jìn)行拼接，大大減少所需計(jì)算的組合數(shù)量，減少了計(jì)算量，提高了計(jì)算效率。

1 多視角拼接方法

1.1生成樹的構(gòu)建

傳統(tǒng)的方法有將任意兩片點(diǎn)云進(jìn)行拼接的方法，此方法需要遍歷所有的兩兩點(diǎn)云組合，計(jì)算量甚大，盲目性過大，如圖1所示，對(duì)于有N個(gè)視角的點(diǎn)云數(shù)據(jù)需要進(jìn)行N×(N-1)次計(jì)算，同時(shí)該方法也存在不合理的地方，單純只考慮了兩片點(diǎn)云間的關(guān)系，沒有考慮到多視角點(diǎn)云間復(fù)雜的相互關(guān)系，故所得的拼接結(jié)果精度有限。

圖1 兩兩拼接多視角拼接組合示意圖

對(duì)一個(gè)完整的物體進(jìn)行掃描，多視角點(diǎn)云數(shù)據(jù)會(huì)構(gòu)成一個(gè)封閉的整體，這些不同視角的點(diǎn)云數(shù)據(jù)可以拆分成最基本的環(huán)形結(jié)構(gòu)，即多片點(diǎn)云構(gòu)成一個(gè)首尾相接的環(huán)形。無論多復(fù)雜的點(diǎn)云關(guān)系，都可以拆分成一系列的環(huán)形結(jié)構(gòu)，如圖2所示，其中連接不同視角的直線表示這兩個(gè)視角之間存在重疊區(qū)域。

圖2 多視角點(diǎn)云相互關(guān)系示意圖

在對(duì)多視角點(diǎn)云進(jìn)行拼接之前，首先需要確定各視角點(diǎn)云之間的關(guān)系，比較簡單的方法是檢測各點(diǎn)云的包圍盒是否相交，從而快速判斷不同視角點(diǎn)云之間是否存在相交區(qū)域。另一種較為精確的方法是對(duì)點(diǎn)云進(jìn)行降采樣后，利用kd樹[9]等搜索在另一片點(diǎn)云上是否存在距離小于指定閾值的點(diǎn)，若存在則認(rèn)為有重疊，該方法的優(yōu)勢(shì)在于當(dāng)采樣點(diǎn)足夠多時(shí)可以將有匹配點(diǎn)的采樣點(diǎn)數(shù)量除以總的采樣點(diǎn)數(shù)量，大致估算出兩片點(diǎn)云的重疊區(qū)域大小。

構(gòu)成環(huán)形的視角數(shù)量并不恒定，因此需要有合適的方法將所有的環(huán)形結(jié)構(gòu)篩選出來，此處引入圖論中生成樹的概念，基于之前對(duì)于點(diǎn)云是否存在相交區(qū)域的判斷結(jié)果，構(gòu)建生成樹(Spanning Tree)[10]。下面以5個(gè)視角的點(diǎn)云數(shù)據(jù)為例介紹生成樹的一些特性，5個(gè)視角的點(diǎn)云數(shù)據(jù)抽象為5個(gè)點(diǎn)，用線連接的2個(gè)點(diǎn)表示這2個(gè)視角的點(diǎn)云數(shù)據(jù)存在重疊部分，如圖3所示。

圖3 5點(diǎn)構(gòu)成的生成樹

生成樹的一個(gè)特點(diǎn)在于將樹上的任意兩個(gè)端點(diǎn)連接起來即可構(gòu)成一個(gè)環(huán)形結(jié)構(gòu)，如圖3所示，將a,c相連，a-e-c-a構(gòu)成一個(gè)環(huán)形；將a,d相連，a-e-d-a構(gòu)成一個(gè)環(huán)形，依此類推，可以窮舉多視角點(diǎn)云數(shù)據(jù)構(gòu)成的環(huán)形結(jié)構(gòu)。在實(shí)際應(yīng)用中，并不是所有的點(diǎn)云之間都存在相交區(qū)域，可以根據(jù)這些關(guān)系來去除部分不存在的環(huán)形結(jié)構(gòu)，減少計(jì)算量。

1.2環(huán)形結(jié)構(gòu)多視角點(diǎn)云拼接

1.2.1環(huán)形結(jié)構(gòu)拼接問題

由1.1節(jié)可以知道，利用生成樹可以將多視角點(diǎn)云數(shù)據(jù)劃分為基礎(chǔ)的環(huán)形結(jié)構(gòu)，本節(jié)將討論環(huán)形結(jié)構(gòu)的多視角點(diǎn)云數(shù)據(jù)拼接。如圖4所示，對(duì)環(huán)形結(jié)構(gòu)的存儲(chǔ)罐模型采集點(diǎn)云數(shù)據(jù)，利用迭代最近點(diǎn)算法將點(diǎn)云兩兩拼接，可以明顯發(fā)現(xiàn)：由于累積誤差的存在，最后一片數(shù)據(jù)和第一片數(shù)據(jù)之間的重疊區(qū)域偏差距離遠(yuǎn)大于0.145mm(圖4(b)中橢圓框選區(qū)域)，而且拼接效果良好的區(qū)域可以觀察到兩片點(diǎn)云相互交錯(cuò)，圖4中并沒有觀察到該現(xiàn)象。

點(diǎn)云間重疊區(qū)域更大的兩片點(diǎn)云拼接結(jié)果相較于重疊區(qū)域較小的兩片點(diǎn)云，其拼接結(jié)果更為可靠，因此考慮到不同視角點(diǎn)云的重疊部分不同，將累積誤差平均分配給環(huán)形結(jié)構(gòu)中各視角點(diǎn)云是不合適的——被移動(dòng)的點(diǎn)云應(yīng)該更靠近重疊部分較大的作為參照基準(zhǔn)的另一部分點(diǎn)云。運(yùn)用迭代最近點(diǎn)算法進(jìn)行拼接時(shí)，為了提高運(yùn)算效率，對(duì)點(diǎn)云進(jìn)行隨機(jī)采樣后搜索匹配點(diǎn)，重疊區(qū)域更大的點(diǎn)云之間，匹配點(diǎn)的數(shù)量更多，點(diǎn)云會(huì)被“拉近”重疊區(qū)域更多的點(diǎn)云，利用這一特性，可以將累積誤差分配到構(gòu)成環(huán)形結(jié)構(gòu)的各視角的點(diǎn)云數(shù)據(jù)中去。

圖4 6視角點(diǎn)云數(shù)據(jù)兩兩視角拼接累積誤差示意圖

實(shí)際測量過程中獲得的多視角點(diǎn)云數(shù)據(jù)的拓?fù)湫畔⑼容^復(fù)雜，如圖5所示，V1和V2，V2和V3進(jìn)行拼接，由于進(jìn)行的是兩兩拼接，V1視角和V3視角存在的重疊部分對(duì)拼接結(jié)果并沒有影響，因此更容易造成誤差的累積。

圖5 3視角點(diǎn)云示意圖

1.2.2用于環(huán)形結(jié)構(gòu)拼接的金字塔模型

考慮到上述問題的存在，本文基于迭代最近點(diǎn)算法提出了一種新的誤差分配方法，稱為金字塔模型，根據(jù)點(diǎn)云間的重疊率來分配多視角環(huán)形結(jié)構(gòu)拼接產(chǎn)生的累積誤差。

下面以4個(gè)視角點(diǎn)云數(shù)據(jù)的環(huán)形結(jié)構(gòu)拼接為例，詳細(xì)說明使用金字塔模型進(jìn)行拼接的方法。4個(gè)視角采用V1，V2，V3和V4表示，4視角之間存在的重疊區(qū)域如圖6所示，圖中的連接線表示兩視角之間存在重疊區(qū)域，為簡化模型，假設(shè)每個(gè)視角只與其相鄰的視角存在重疊區(qū)域。

圖6 4視角環(huán)形結(jié)構(gòu)

如圖7所示，將視角V1算作兩個(gè)視角，打開環(huán)形結(jié)構(gòu)的鏈條，構(gòu)建金字塔模型的第1層。

圖7 4視角環(huán)形結(jié)構(gòu)的打開

利用迭代最近點(diǎn)算法，調(diào)整相鄰兩視角的位置，即以V1為基準(zhǔn)，將V2拼接到V1上去，拼接完成后，將V3拼接到V2上去，依此類推，最后將另一片V1拼接到V4上，自此完成金字塔模型第2層的構(gòu)建，如圖8所示。

圖8 金字塔模型第二層的構(gòu)建

仿照金字塔模型第2層的構(gòu)建，構(gòu)建第3層的視角V1″，V2″和V3″，再構(gòu)建第4層的視角V1?和V2?，最終生成拼接參考模型V。金字塔模型各層各視角間關(guān)系如圖9所示。

將視角V1視作兩個(gè)視角打斷環(huán)形結(jié)構(gòu)之后，可以發(fā)現(xiàn)倒數(shù)第2層的兩個(gè)視角V1?和V2?中均含有視角V1的點(diǎn)云數(shù)據(jù)，其中V1?包含視角V1，V2，V3和V4的數(shù)據(jù)，而V2?則包含V2，V3，V4和V1的數(shù)據(jù)，視角V1的數(shù)據(jù)會(huì)將兩個(gè)視角V1?和V2?相互拉近，兩個(gè)視角V1?和V2?中包含的視角V2，V3和V4的數(shù)據(jù)相互分開，從而將累積的誤差分配到各點(diǎn)云中去，以生成的金字塔模型為基準(zhǔn)，將V1，V2，V3和V4拼接到金字塔模型V上去，完成環(huán)形結(jié)構(gòu)多視角點(diǎn)云數(shù)據(jù)的拼接。

圖9 金字塔模型示意圖

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

為減少數(shù)據(jù)量，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行采樣后選取匹配點(diǎn)進(jìn)行拼接(不建議直接對(duì)點(diǎn)云進(jìn)行降采樣后使用降采樣的點(diǎn)云進(jìn)行拼接，這樣雖然減少了數(shù)據(jù)量，但是大量原先處于相同位置點(diǎn)的存在會(huì)導(dǎo)致點(diǎn)云的“鎖死”，難以獲得良好的結(jié)果，因此本文在進(jìn)行實(shí)驗(yàn)時(shí)存儲(chǔ)各視角點(diǎn)云數(shù)據(jù)的旋轉(zhuǎn)平移關(guān)系，即4×4的旋轉(zhuǎn)平移矩陣)。金字塔模型中每片點(diǎn)云生成時(shí)，都進(jìn)行隨機(jī)采樣，獲得不同的點(diǎn)構(gòu)成新的點(diǎn)云數(shù)據(jù)，而采樣后獲得的點(diǎn)在尋找匹配點(diǎn)時(shí)，可以根據(jù)存儲(chǔ)的旋轉(zhuǎn)平移矩陣轉(zhuǎn)換到匹配點(diǎn)所在視角的坐標(biāo)系下，獲得盡可能可靠的匹配點(diǎn)，從而提高點(diǎn)云拼接的精度。由于拼接時(shí)點(diǎn)云受到的“拉力”取決于點(diǎn)的數(shù)量，故為了將累積誤差合理分配，需保持視角V1采樣的數(shù)據(jù)量與剩余視角的總數(shù)據(jù)量相同。對(duì)石膏制存儲(chǔ)罐模型進(jìn)行掃描重建，獲得6個(gè)不同視角下的三維點(diǎn)云數(shù)據(jù)，6視角的數(shù)據(jù)為環(huán)形結(jié)構(gòu)，多視角點(diǎn)云依靠掃描儀的機(jī)械轉(zhuǎn)臺(tái)進(jìn)行粗定位。多視角點(diǎn)云數(shù)據(jù)拼接前后的位置以及精度分析如圖10所示。

從圖10可以看到，各視角點(diǎn)云數(shù)據(jù)在拼接之后重疊部分有良好的交錯(cuò)區(qū)域，利用Gemagic Studio 12軟件分析可發(fā)現(xiàn)重疊部分的平均距離在0.028mm以下。

圖10 儲(chǔ)蓄罐6視角點(diǎn)云拼接

對(duì)石膏牙模采集數(shù)據(jù)，依照本文方法進(jìn)行拼接，數(shù)據(jù)分析結(jié)果如圖11所示。

圖11 石膏牙模多視角點(diǎn)云拼接

由圖11可以看到各視角點(diǎn)云重疊部分的平均距離由拼接前的0.126mm下降到0.035mm，Gemagic全局注冊(cè)功能拼接結(jié)果則為0.033mm。

對(duì)石膏儲(chǔ)蓄罐模型和石膏牙齒模型測量后進(jìn)行拼接，部分實(shí)驗(yàn)數(shù)據(jù)見表1。

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

3 結(jié)束語

本文提出了一種新的多視角拼接方法，利用多視角點(diǎn)云之間的位置關(guān)系，基于生成樹構(gòu)建環(huán)形結(jié)構(gòu)，合理有效地分配了環(huán)形結(jié)構(gòu)中由拼接造成的累積誤差。實(shí)驗(yàn)表明，該方法能獲得令人滿意的拼接結(jié)果，相較于以往的拼接方法，誤差分配更平均合理。然而在視角數(shù)量較多時(shí)，由于生成了大量的環(huán)形結(jié)構(gòu)，會(huì)導(dǎo)致算法運(yùn)行需要較多的時(shí)間，如何提高算法效率是后續(xù)研究需要解決的問題。

[1] Chua C S, Jarvis R. Point signatures:a new representation for 3d object recognition[J]. International Journal of Computer Vision, 1997, 25(1): 63-85.

[2] Johnson A E, Hebert M. Using spin images for efficient object recognition in cluttered 3D scenes[J].Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1999, 21(5): 433-449.

[3] Besl P J, McKay N D. Method for registration of 3-D shapes[C]//Robotics-DL tentative. International Society for Optics and Photonics, 1992: 586-606.

[4] Rusinkiewicz S, Levoy M. Efficient variants of the ICP algorithm[C]//3-D Digital Imaging and Modeling, 2001. Proceedings. Third International Conference on. IEEE, 2001: 145-152.

[5] Pulli K. Multiview registration for large data sets[C]//3-D Digital Imaging and Modeling, 1999. Proceedings. Second International Conference on. IEEE, 1999: 160-168.

[6] Chen Y, Medioni G. Object modelling by registration of multiple range images[J]. Image and Vision Computing, 1992, 10(3): 145-155.

[7] Sharp G C, Lee S W, Wehe D K. Multiview registration of 3D scenes by minimizing error between coordinate frames[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2004, 26(8): 1037-1050.

[8] Masuda T. Registration and integration of multiple range images by matching signed distance fields for object shape modeling[J]. Computer Vision and Image Understanding, 2002, 87(1): 51-65.

[9] Liu T, Moore A W, Yang K, et al. An investigation of practical approximate nearest neighbor algorithms[C]//Advances in Neural Information Processing Systems,2004: 825-832.

[10] Rosen R. The theory of graphs and its applications[J]. Bulletin of Mathematical Biology, 1962, 24(4): 441-443.

Multi-viewRegistrationof3DScenesBasedonAllocatingCumulativeErrors

TANG Minghui, CHEN Xiaosheng, CUI Haihua, DAI Ning

(Nanjing University of Aeronautics & Astronautics, Jiangsu Nanjing, 210016, China)

Multi-view three-dimensional registration is an important part of three-dimensional measurements. In order to improve the accuracies of multi-view registration, it proposes a method based on optimal allocation of cumulative errors. According to the spatial position information of multi-view point cloud data, this method constructs a ring based on spanning tree, distributes the accumulated errors to each perspective. This can gradually improve the overall accuracies. Experiments show that the method can obtain satisfactory registration precision almost reached with the same effect of those commercial softwares.

Multi-view Registration; Spanning Tree; Error Allocation; Cumulative Errors

10.3969/j.issn.2095-509X.2014.09.005

2014-08-19

國家863計(jì)劃資助項(xiàng)目(SS2013AA040802)；國家自然科學(xué)基金資助項(xiàng)目(51305201)；江蘇省精密與微細(xì)制造技術(shù)重點(diǎn)實(shí)驗(yàn)開放基金；南京市產(chǎn)學(xué)研項(xiàng)目(201306007)

湯明輝(1990—)，男，江蘇南京人，南京航空航天大學(xué)碩士研究生，主要研究方向?yàn)閳D像處理、非接觸三維幾何測量、三維拼接。

TP399

A

2095-509X(2014)09-0018-05