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

引言

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

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

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

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

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

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

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

1 三維點云配準與ICP算法

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

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

(1)

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

(2)

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

2 本文提出的算法

2.1 分支定界框架

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

2.2 三維配準中可行解空間的參數化

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

　　1)旋轉空間

　　因為配準的數學化目標是公式(2)中誤差目標函數的最小化。所以本文采用圖2所示的角軸表示來參數化旋轉空間。

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

　　2)平移空間

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

2.3 嵌套的BnB

　　在解決了三維配準中可行解空間的參數化問題的前提下，在應用分支定界算法前還要解決的一個問題是上下界的確定。

　　假設對于一個旋轉空間的子集C_r，其空間半邊長記為，空間的中心對應一個旋轉記為r_o，P為點云中一個點，易得到如下結論：

(3)

表示空間C_r對應的旋轉漂移半徑。

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

(4)

　　r_t是C_t對應的平移漂移半徑。

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

(5)

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

　(6)

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

(7)

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

　(8)

　(9)

2.4 集成SAC-IA

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

3 實驗與分析

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

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

4 結論

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

參考文獻：

　　[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

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