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

摘要：三維點云配準(zhǔn)是三維重建和增強現(xiàn)實中的關(guān)鍵技術(shù)，也是計算機視覺領(lǐng)域的重要研究方向。最近點迭代法(ICP Iterative Closest Point)是當(dāng)前應(yīng)用最廣泛的三維點云配準(zhǔn)算法之一。本文將分支與定界算法(Branch-and-Bound, BnB)引入三維點云配準(zhǔn)，在解空間中，采用BnB算法做全局搜索，從根本上解決局部搜索的缺陷，與此同時，我們在定界中融合了抽樣一致初始配準(zhǔn)算法(SAC-IA)，從而加快了算法的運算速度。實驗表明，本算法在配準(zhǔn)中取得了很好的效果。

引言

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

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

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

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

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

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

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

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

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

　　1)在P_s和P_t間計算匹配的最鄰近點對：

(1)

　　2)通過最小化下列L₂范數(shù)形式的誤差目標(biāo)函數(shù)E，計算最鄰近匹配點對的剛體運動：

(2)

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

2 本文提出的算法

2.1 分支定界框架

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

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

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

　　1)旋轉(zhuǎn)空間

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

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

　　2)平移空間

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

2.3 嵌套的BnB

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

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

(3)

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

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

(4)

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

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

(5)

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

　(6)

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

(7)

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

　(8)

　(9)

2.4 集成SAC-IA

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

3 實驗與分析

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

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

4 結(jié)論

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

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