一種基于Kinect的點(diǎn)云配準(zhǔn)算法

摘要：三維點(diǎn)云配準(zhǔn)是三維重建和增強(qiáng)現(xiàn)實(shí)中的關(guān)鍵技術(shù)，也是計(jì)算機(jī)視覺(jué)領(lǐng)域的重要研究方向。最近點(diǎn)迭代法(ICP Iterative Closest Point)是當(dāng)前應(yīng)用最廣泛的三維點(diǎn)云配準(zhǔn)算法之一。本文將分支與定界算法(Branch-and-Bound, BnB)引入三維點(diǎn)云配準(zhǔn)，在解空間中，采用BnB算法做全局搜索，從根本上解決局部搜索的缺陷，與此同時(shí)，我們?cè)诙ń缰腥诤狭?a class="contentlabel" href="http://2s4d.com/news/listbylabel/label/抽樣一致初始配準(zhǔn)">抽樣一致初始配準(zhǔn)算法(SAC-IA)，從而加快了算法的運(yùn)算速度。實(shí)驗(yàn)表明，本算法在配準(zhǔn)中取得了很好的效果。

引言

　　對(duì)真實(shí)世界場(chǎng)景進(jìn)行三維感知與建模是計(jì)算機(jī)視覺(jué)和機(jī)器人領(lǐng)域的一項(xiàng)重要任務(wù)。國(guó)內(nèi)外的研究者針對(duì)三維重建進(jìn)行了廣泛的研究。近年來(lái)，隨著Kinect(如圖1)的問(wèn)世和不斷發(fā)展，基于深度攝像機(jī)的諸多算法被越來(lái)越廣泛地應(yīng)用于三維重建、實(shí)時(shí)定位與繪圖和機(jī)器人等領(lǐng)域。尤其是在三維重建中，RGB-D攝像機(jī)因其同步獲取場(chǎng)景RGB圖像和深度圖的特點(diǎn)，使其很快成為三維重建的主要感知設(shè)備，極大推動(dòng)了三維重建技術(shù)的進(jìn)步。在實(shí)際重建過(guò)程中，往往因?yàn)閭鞲衅鞯挠行綔y(cè)距離限制和場(chǎng)景遮擋的存在，需要將多幀采集的圖像序列融合到一個(gè)統(tǒng)一坐標(biāo)系下的模型中，實(shí)現(xiàn)這樣目標(biāo)的關(guān)鍵技術(shù)就是3D配準(zhǔn)。

　　正因?yàn)?D配準(zhǔn)在計(jì)算機(jī)視覺(jué)領(lǐng)域的應(yīng)用中常常作為一個(gè)關(guān)鍵環(huán)節(jié)，研究者們已經(jīng)針對(duì)這個(gè)問(wèn)題提出了許多算法，其中最近點(diǎn)迭代法(ICP)是著名的配準(zhǔn)算法。上個(gè)世紀(jì)90年代，ICP首次由Chen和McKay等人提出^[1-2]，在隨后的二十多年中ICP不斷得到改進(jìn)，衍生出了許多改進(jìn)版本，以至于后來(lái)的研究者很難能夠完全列舉出所有基于ICP的配準(zhǔn)算法，不過(guò)，最近發(fā)表的一篇綜述^[3]已經(jīng)列舉出了一些具有代表性的ICP版本。

　　盡管最近點(diǎn)迭代算法ICP具有思路簡(jiǎn)單直觀、效果理想的優(yōu)點(diǎn)，成為三維重建中應(yīng)用最廣泛的配準(zhǔn)算法，并成功引用于計(jì)算機(jī)視覺(jué)領(lǐng)域。但是有一個(gè)難點(diǎn)，在應(yīng)用ICP進(jìn)行配準(zhǔn)之前，需要給出待配準(zhǔn)數(shù)據(jù)的初始估值，如果初始估值不恰當(dāng)?shù)脑?，將使ICP收斂過(guò)程步入歧途，導(dǎo)致配準(zhǔn)陷入局部最優(yōu)化。

　　為了克服陷入局部最優(yōu)化，有一類針對(duì)ICP的改進(jìn)將重點(diǎn)放在了能量函數(shù)。這類方法是用更具魯棒性的范數(shù)來(lái)代替原算法中的范數(shù)，如^[4]中的LI和^[5]中的LP。這兩種方法顯著提高了大量噪聲和局外點(diǎn)魯棒性，一定程度上克服了解空間陷入局部最優(yōu)的缺陷。但是在取得了上述進(jìn)步的同時(shí)，也引入了解空間非凸非平滑的問(wèn)題。

　　另一類對(duì)于ICP的改進(jìn)是基于統(tǒng)計(jì)學(xué)的方法。Jian等人^[6]提出的改進(jìn)是基于高斯混合模型。Billings等人^[7]提出的IMLP也屬于基于統(tǒng)計(jì)學(xué)方法的ICP改進(jìn)。盡管這類方法一定程度上克服了局部最優(yōu)化的缺陷，并且算法思路很具有說(shuō)服性，但是它們的優(yōu)化方法仍然是采用局部搜索的方式。

　　還有一類ICP的改進(jìn)算法應(yīng)用了三維點(diǎn)云的特征點(diǎn)提取與匹配^[8-11]。通常，這類方法的算法框架可以歸納為兩部分。首先，采用一種特征點(diǎn)提取算法分別在待配準(zhǔn)點(diǎn)云中提取出特征點(diǎn)子集，并且在子集中利用特征描述符建立對(duì)應(yīng)點(diǎn)對(duì)的匹配關(guān)系;然后，ICP算法利用這些已經(jīng)匹配點(diǎn)對(duì)建立剛體轉(zhuǎn)換關(guān)系，從而最終獲得全集的配準(zhǔn)結(jié)果。有些算法還會(huì)在配準(zhǔn)后應(yīng)用閉環(huán)檢測(cè)和全局優(yōu)化算法對(duì)結(jié)果進(jìn)行校正。雖然這類方法克服了對(duì)精確配準(zhǔn)初值的依賴，但是它們并沒(méi)有做到全局最優(yōu)化。而且高效魯棒的三維特征點(diǎn)提取與匹配算法本身也是一個(gè)具有挑戰(zhàn)性的研究課題。

　　分支定界(BnB)是一個(gè)最近在計(jì)算機(jī)視覺(jué)領(lǐng)域得到越來(lái)越多應(yīng)用的全局最優(yōu)化通用框架^[12-14]。在三維配準(zhǔn)中，Hartley等人^[12]提出的旋轉(zhuǎn)空間搜索方法能夠在僅有旋轉(zhuǎn)運(yùn)動(dòng)的情況下獲得全局最優(yōu)的配準(zhǔn)結(jié)果。本文算法將這種BnB框架擴(kuò)展到平移空間，從而獲得通常情況下全局最優(yōu)的配準(zhǔn)結(jié)果，為了提高算法的效率，我們會(huì)將抽樣一致初始配準(zhǔn)(SAC-IA)嵌套在分支定界框架中來(lái)加速算法。

1 三維點(diǎn)云配準(zhǔn)與ICP算法

　　我們定義待配準(zhǔn)點(diǎn)云中，當(dāng)前點(diǎn)云記為，其中;目標(biāo)點(diǎn)云記為，其中，p_i和q_j分別表示當(dāng)前點(diǎn)云和目標(biāo)點(diǎn)云中的一個(gè)任意點(diǎn)，即。ICP算法將在以下兩個(gè)步驟間迭代：

　　1)在P_s和P_t間計(jì)算匹配的最鄰近點(diǎn)對(duì)：

(1)

　　2)通過(guò)最小化下列L₂范數(shù)形式的誤差目標(biāo)函數(shù)E，計(jì)算最鄰近匹配點(diǎn)對(duì)的剛體運(yùn)動(dòng)：

(2)

　　最鄰近迭代法ICP的具體描述如下：

2 本文提出的算法

2.1 分支定界框架

　　分支定界是一個(gè)用途廣泛的算法，其基本思想是對(duì)有約束條件的最優(yōu)化問(wèn)題的完全可行解空間進(jìn)行搜索。該算法在執(zhí)行過(guò)程中，將全部可行解空間不斷分割為越來(lái)越小的子集(分支)，并為每個(gè)子集計(jì)算一個(gè)上界或下界(定界)，凡是超過(guò)已知界限的子空間將被舍棄，從而縮小搜索范圍，直到求得最優(yōu)解。以下是通用BnB框架的具體描述：

2.2 三維配準(zhǔn)中可行解空間的參數(shù)化

　　將分支定界算法應(yīng)用于三維點(diǎn)云配準(zhǔn)問(wèn)題的一個(gè)重要前提是可行解空間的參數(shù)化，只有實(shí)現(xiàn)了解空間的參數(shù)化，才可以將連續(xù)的優(yōu)化轉(zhuǎn)換成離散問(wèn)題。下面將分別介紹本文采用的參數(shù)化模型。

　　1)旋轉(zhuǎn)空間

　　因?yàn)榕錅?zhǔn)的數(shù)學(xué)化目標(biāo)是公式(2)中誤差目標(biāo)函數(shù)的最小化。所以本文采用圖2所示的角軸表示來(lái)參數(shù)化旋轉(zhuǎn)空間。

　　對(duì)于任意一個(gè)旋轉(zhuǎn)在圖2中用向量表示，的模表示繞旋轉(zhuǎn)軸旋轉(zhuǎn)的角度，所以g可以用表示。

　　2)平移空間

　　對(duì)于平移空間的參數(shù)化，本文采用圖3所示的一個(gè)邊界值為的正方體來(lái)表示。設(shè)定為能夠使得待匹配點(diǎn)云產(chǎn)生重疊的最小值，立方體內(nèi)的任意一點(diǎn)的坐標(biāo)(x,y,z)即表示一個(gè)空間中的平移運(yùn)動(dòng)。

2.3 嵌套的BnB

　　在解決了三維配準(zhǔn)中可行解空間的參數(shù)化問(wèn)題的前提下，在應(yīng)用分支定界算法前還要解決的一個(gè)問(wèn)題是上下界的確定。

　　假設(shè)對(duì)于一個(gè)旋轉(zhuǎn)空間的子集C_r，其空間半邊長(zhǎng)記為，空間的中心對(duì)應(yīng)一個(gè)旋轉(zhuǎn)記為r_o，P為點(diǎn)云中一個(gè)點(diǎn)，易得到如下結(jié)論：

(3)

表示空間C_r對(duì)應(yīng)的旋轉(zhuǎn)漂移半徑。

　　假設(shè)對(duì)于一個(gè)平移空間的子集C_t，其空間半邊長(zhǎng)記為，空間的中心對(duì)應(yīng)一個(gè)平移記為t_o，P為點(diǎn)云中一個(gè)點(diǎn)，我們有如下結(jié)論：

(4)

　　r_t是C_t對(duì)應(yīng)的平移漂移半徑。

　　將上述結(jié)論應(yīng)用到一般的三維場(chǎng)景中，即同時(shí)存在一個(gè)旋轉(zhuǎn)子集C_r和平移子集C_t，對(duì)于空間中任意一點(diǎn)p_i，公式(2)中的殘差函數(shù)與公式(3)(4)結(jié)合可以得到如下結(jié)論：

(5)

　　因此本文定義殘差函數(shù)上界如下式：

　(6)

　　由公式(5)得到殘差函數(shù)下界如下式：

(7)

　　將點(diǎn)云中每個(gè)點(diǎn)的上下界做黎曼和即為本文分支定界算法的上下界函數(shù)，即：

　(8)

　(9)

2.4 集成SAC-IA

　　當(dāng)本文的分支定界執(zhí)行到第9行時(shí)，算法找到了一個(gè)更加接近最優(yōu)解的子集，此時(shí)利用SAC-IA求得相比于子集中心更加精確的運(yùn)動(dòng)估計(jì)來(lái)更新目前為止的上界閾值。以這種形式集成SAC-IA可以加快分支定界的搜索，忽略不必要的多余空間。

3 實(shí)驗(yàn)與分析

　　為驗(yàn)證本文提出的算法，我們采用目前國(guó)際上應(yīng)用廣泛的配準(zhǔn)素材進(jìn)行對(duì)比實(shí)驗(yàn)(Stanford models)。我們使用的實(shí)驗(yàn)環(huán)境是一臺(tái)Windows 7系統(tǒng)的工作站，配備Intel Xeon 2.0GHz CPU和16G內(nèi)存。對(duì)比的算法包括Standard ICP、Point-to-Point ICP、Point-to-Plane ICP和近年來(lái)提出的GICP。借助于庫(kù)PCL，我們可以很方便地實(shí)現(xiàn)上述對(duì)比算法。在衡量算法精度時(shí)，本文分別計(jì)算配準(zhǔn)后最鄰近點(diǎn)對(duì)間歐氏距離的最小值、最大值以及均方根誤差RMSE。在驗(yàn)證算法效率時(shí)，本文記錄各算法配準(zhǔn)過(guò)程所消耗的物理時(shí)間，實(shí)驗(yàn)結(jié)果如表1所示。圖4所示為本文算法的直觀結(jié)果。

　　從配準(zhǔn)的統(tǒng)計(jì)和直觀結(jié)果可以清晰看出，本文提出的算法在精度和效率上都超過(guò)了對(duì)比算法，同時(shí)直觀配準(zhǔn)結(jié)果也顯示了本文算法取得了良好的配準(zhǔn)結(jié)果。

4 結(jié)論

　　本文提出了一種基于分支定界的三維點(diǎn)云配準(zhǔn)算法。該算法一方面利用分支定界的框架，在配準(zhǔn)問(wèn)題的完全可行域中搜索最優(yōu)解，克服了傳統(tǒng)配準(zhǔn)算法容易陷入局部最優(yōu)化的缺陷;另一方面通過(guò)集成SAC-IA算法，加速分支定界的過(guò)程，忽略不必要的可行域子集，克服了傳統(tǒng)分支定界時(shí)間效率低的缺陷，同時(shí)保持了配準(zhǔn)算法的高效性。對(duì)比實(shí)驗(yàn)結(jié)果表明，本文算法達(dá)到了有效克服局部最優(yōu)化的目的，精度更高，速度更快，取得了理想的配準(zhǔn)效果。

參考文獻(xiàn)：

　　[1]Y. Chen and G. Medioni, “Object modeling by registration of multiple range images,” in Robotics and Automation, 1991. Proceedings., 1991 IEEE International Conference on. IEEE, 1991, pp. 2724–2729

　　[2]P. J. Besl and N. D. McKay, “Method for registration of 3-d shapes,” in Robotics-DL tentative. International Society for Optics and Photonics, 1992, pp. 586–606

　　[3]F. Pomerleau, F. Colas, R. Siegwart, and S. Magnenat, “Comparing icp variants on real-world data sets,” Autonomous Robots, vol. 34, no. 3, pp. 133–148, 2013

　　[4]A. W. Fitzgibbon, “Robust registration of 2d and 3d point sets,” Image and Vision Computing, vol. 21, no. 13, pp. 1145–1153, 2003

　　[5]S. Bouaziz, A. Tagliasacchi, and M. Pauly, “Sparse iterative closest point,” in Computer graphics forum, vol. 32, no. 5. Wiley Online Library, 2013, pp. 113–123

　　[6]B. Jian and B. C. Vemuri, “A robust algorithm for point set registration using mixture of gaussians,” in Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, vol. 2. IEEE, 2005, pp. 1246–1251

　　[7]S. D. Billings, E. M. Boctor, and R. H. Taylor, “Iterative most-likely point registration (imlp): a robust algorithm for computing optimal shape alignment,” PloS one, vol. 10, no. 3, 2015

　　[8]A. S. Huang, A. Bachrach, P. Henry, M. Krainin, D. Maturana, D. Fox, and N. Roy, “Visual odometry and mapping for autonomous flight using an rgb-d camera,” in International Symposium on Robotics Research (ISRR), 2011, pp. 1–16

　　[9]J. Xie, Y.-F. Hsu, R. S. Feris, and M.-T. Sun, “Fine registration of 3d point clouds with iterative closest point using an rgb-d camera,” in Circuits and Systems (ISCAS), 2013 IEEE International Symposium on. IEEE, 2013, pp. 2904–2907

　　[10]X. Li, W. Li, H. Jiang, and H. Zhao, “Automatic evaluation of machining allowance of precision castings based on plane features from 3d point cloud,” Computers in Industry, vol. 64, no. 9, pp. 1129–1137, 2013

　　[11]M. Salem, H. Ramadan, M. I. Roushdy et al., “Comparison of 3d feature registration techniques for indoor mapping,” in Computer Engineering & Systems (ICCES), 2013 8th International Conference on. IEEE, 2013, pp. 239–244

　　[12]R. I. Hartley and F. Kahl, “Global optimization through rotation space search,” International Journal of Computer Vision, vol. 82, no. 1, pp. 64–79, 2009

　　[13]M. Sun, M. Telaprolu, H. Lee, and S. Savarese, “An efficient branchand-bound algorithm for optimal human pose estimation,” in Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on.IEEE, 2012, pp. 1616–1623

　　[14]C. Yu, Y. Seo, and S. W. Lee, “Global optimization for estimating a brdf with multiple specular lobes,” in Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010, pp. 319–326

本文來(lái)源于中國(guó)科技期刊《電子產(chǎn)品世界》2016年第4期第31頁(yè)，歡迎您寫論文時(shí)引用，并注明出處。