基于混合遺傳算法和點面距離測度的深度像配準

摘要：提出一種利用改進的遺傳算法和點面距離作為誤差測度的深度像精確配準算法。與現有ICP框架下的迭代算法不同，將深度像配準視為高維空間的一個優化問題，通過在遺傳算法中加入退火選擇、爬山法以及參數空間的動態退化來加速尋找最優的位置轉換關系。同時，采用一種新的基于點面距離的適應函數來計算配準誤差，使得算法具有更強的魯棒性。實驗結果表明，該算法不需要初始的運動參數估計，具有較高的配準精度，收斂速度快且抗噪聲能力強。

關鍵詞：遺傳算法; 點面距離; 誤差測度; 深度像配準

中圖分類號：TP391.72文獻標志碼：A

文章編號：1001-3695(2007)12-0354-03

0引言

隨著三維數字化技術的不斷發展，真實世界物體的三維建模已經成為計算機視覺、計算機輔助幾何設計和非接觸測量等多學科交叉領域的一個研究熱點。由于掃描設備的視野限制以及物體自身復雜的幾何形狀，實際物體的全部深度信息不可能在一個視點位置獲得。為了得到被測物體完整的數據模型，就需要從不同視角對物體進行多次重復掃描。這樣，多視場深度數據的精確配準就成為三維建模中的一個關鍵步驟^[1]。

對于深度像的兩兩配準來說，根據輸入和配準精度的不同，現有算法可以分為粗配準和精確配準兩類。粗配準通常是在沒有任何先驗知識的情況下，找到一組近似的運動參數，將兩個視場的深度像統一到同一個坐標系下。此類方法基本上都是通過尋找深度像重疊區域的特征對應來完成的，所用到的特征^[2]包括曲面的曲率、雙切線、曲面的標志以及平面和特征線等。一般來說，粗配準的精度不高，而精確配準卻可以提供很高的匹配精度。這類方法以兩幅深度像和一個初始的空間位置變換作為輸入，通過定義一個誤差函數來反映深度像重疊區域的匹配程度。目前應用最廣泛的精配準算法就是由Besl等人^[3]以及Chen等人^[4]提出的迭代最近點(iterative closest point，ICP)算法及其各種變形^[5]。

深度像精確配準的另一個解決方案就是采用一種有效的搜索算法直接在幾何變換的參數空間中尋找最佳的剛體變換。該方法期望在允許的時間內，在包含六個變量的參數空間中找到一個足夠精確的剛體變換。此類方法中，最有效的應用就是基于遺傳算法^{[1， 2]}或者模擬退火的深度像配準^[6]。2002年，Robertson等人^[7]利用一種并行的硬件實現方式，將對應點對距離的均方誤差作為適應函數，利用遺傳算法解決了自由曲面的精確配準問題。Chow等人^[1]提出了另一種基于遺傳算法的深度像配準算法。在該算法中，Chow利用點對距離的中值作為誤差度量，使得算法的魯棒性大為提高。深度像配準的另外一個重要貢獻是Silva等人^[2]提出的曲面交叉測度。結合點對距離的均方誤差，該方法可以獲得較高的配準精度。然而，現有基于遺傳算法的深度像配準，在誤差測度的選擇上，都是以對應點對之間的距離作為誤差測度來指導深度像的配準。Silva等人^[2]曾經指出：以對應點對的距離作為誤差測度，即使是某些錯誤的轉換關系也同樣可以得到較小的配準誤差。因此，本文采用一種新的誤差度量，將點到對應切平面的距離作為適應函數，并結合一個混合遺傳算法完成了深度像的精確配準。在混合遺傳算法中，退火選擇、爬山法以及參數空間的動態退化均有利于加快算法的收斂和提高最終的配準精度。實驗結果表明，該算法具有較強的魯棒性和較高的配準精度，收斂速度快、運行穩定。

1基于點面距離的誤差測度

Gelfand等人^[8]指出，基于點到對應切平面距離的誤差測度要比基于點對對應的誤差測度更加魯棒。當兩個深度像足夠接近時，點到對應切平面的距離更能反映出兩個曲面之間的真正距離。由于受偏離點的影響，基于點對對應的誤差測度在配準時往往會陷入局部最優而無法得到正確的配準結果。本文采用點到對應切平面的距離作為誤差測度來指導深度像的配準。

4結束語

本文提出了一種利用遺傳算法和點到對應切平面的距離作為誤差測度的深度像精確配準算法。與現有基于點對對應的配準算法相比，基于點到對應切平面距離的誤差測度具有更強的魯棒性，對噪聲不敏感，更能反映出深度像重疊區域的匹配程度。另外，在遺傳算法中加入的退火選擇、爬山法以及參數空間的動態退化等技術，有效地提高了算法的局部搜索能力，加快了算法的收斂速度。大量的實驗結果表明，本文算法不需要初始的變換估計，抗噪聲能力強、運行穩定，而且具有較快的收斂速度和較高的配準精度。

致謝感謝俄亥俄州立大學SAMPL實驗室提供的真實采樣數據。

參考文獻：

[1]CHOW C K， TSUI H T， LEE T. Surface registration using a dynamic genetic algorithm[J]. Pattern Recognition， 2004，37(1):105－117.

[2]SILVA L，BELLON O R P，BOYER K L.Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005，27(5):762-776.

[3]BESL P J， McKAY N D. A method for registration of 3D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1992，14(2):239-256.

[4]CHEN Y， MEDIONI G. Object modeling by registration of multiple range images[C]//Proc of IEEE International Conference on Robotics and Automation. Sacramento:[s.n.]， 1991:2724-2729.

[5]RUSINKIEWICZ S， LEVOY M. Efficient variants of the ICP algorithm[C]//Proc ofthe 3rd International Conference on 3D Digital Imaging and Modeling. Quebec: IEEE， 2001:145－152.

[6]BLAIS G， LEVINE M. Registering multi－view range data to create 3D computer objects[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1995，17(8):820-824.

[7]ROBERTSON C， FISHER R B. Parallel evolutionary registration of range data[J]. Computer Vision and Image Understanding， 2002，87(1):39-50.

[8]GELFAND N， IKEMOTO L， RUSINKIEWICZ S， et al. Geometrically stable sampling for the ICP algorithm[C]//Proc of the 4th International Conference on 3D Digital Imaging and Modeling. Banff:[s.n.]， 2003:260-267.

[9]PULLI K. Multi－view registration for large data sets[C]//Proc of the 2nd International Conference on 3D Digital Imaging and Modeling. Ottawa: IEEE， 1999:160－168.

[10]李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用[M].北京:科學出版社，2002.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”