(論文)本科設(shè)計論文(2013年優(yōu)秀畢業(yè)設(shè)計論文)

畢畢 業(yè)業(yè) 設(shè)設(shè) 計（論計（論 文）文） 空間相似變換在點云配準中的應用 專業(yè)年級專業(yè)年級 06 級測繪工程 學學 號號 06044235 姓姓 名名 郭建明 指導教師指導教師 陳建華 評評 閱閱 人人 鄭德華 二一年六月二一年六月 中國中國 南京南京 河海大學學士學位論文 空間相似變換在點云配準中的應用 1 河 海 大 學 本科畢業(yè)設(shè)計（論文）任務(wù)書 、畢業(yè)設(shè)計（論文）題目： 空間相似變換在點云配準中的應用 、畢業(yè)設(shè)計（論文）工作內(nèi)容（從綜合運用知識、研究方案的設(shè)計、研究方法 和手段的運用、 應用文獻資料、 數(shù)據(jù)分析處理、 圖紙質(zhì)量、 技術(shù)或觀點創(chuàng)新等方面詳細說明）： 三維激光掃描技術(shù)能夠快速、精確、無接觸地獲取復雜物體表面的三維信 息(點云),進而完成三維實體重建。 不同視點所獲點云坐標由于誤差積累等原因， 往往不能很好匹配，需要后期配準。傳統(tǒng)上使用 ICP 點云配準算法。由空間相似 變換進行不同視點的點云配準， 其參數(shù)幾何意義明確， 也便于可靠性及誤差分析。 本課題的研究，要求學生針對具體問題制定研究計劃、總結(jié)研究成果，在研究過 程中，學會用科學的方法分析問題、解決問題。 要求： 1、了解 ICP 點云配準算法 2、Trimble 三維激光掃描儀的應用 3、熟悉空間相似變換及間接平差理論 4、熟練掌握 VB/VC 程序設(shè)計 5、通過實驗檢測應用空間相似變換進行點云配準的效果，并進行可靠 性分析 河海大學學士學位論文 空間相似變換在點云配準中的應用 2 、進度安排： 1.收集閱讀參考資料 1 周 2.熟悉 Trimble 三維激光掃描儀 1-2 周 3.空間相似變換及間接平差理論分析 2-3 周 4.空間相似變換在點云配準中的應用 2-3 周 5.撰寫畢業(yè)論文及答辯 2-3 周 、主要參考資料： 1 工程測量學 水利水電出版社 2相關(guān)論文 指導教師： 陳建華 ， 2010 年 6 月 1 日 學生姓名： 郭建明 ，專業(yè)年級：06 級測繪工程 河海大學學士學位論文 空間相似變換在點云配準中的應用 3 摘要摘要 近幾十年來，計算機圖形學得到了迅速發(fā)展。隨著計算機圖形學的發(fā)展，一 些相關(guān)技術(shù)也相繼出現(xiàn)或在原有基礎(chǔ)上有了長足的進步。虛擬現(xiàn)實、數(shù)字城市、 數(shù)字博物館、逆向工程等新名詞相繼出現(xiàn)并開始進入應用階段。這些技術(shù)都不可 或缺的需要進行三維幾何建模，而傳統(tǒng)的 AutoCAD、3D Max、MAYA 等建模工具已 經(jīng)逐漸不能勝任人們對復雜曲面物體的建模需要， 由此三維激光掃描技術(shù)應運而 生。 為了得到物體真實的三維模型，人們需要獲得三維物體表面的真實數(shù)據(jù)。但 是，由于受到測量設(shè)備和環(huán)境的限制，物體表面完整測量數(shù)據(jù)的獲得往往需要通 過多次測量完成。因此，在得到點云數(shù)據(jù)之后，為了得到三維模型的原始曲面， 必須要將不同角度， 不同位置掃描得到的大容量三維空間數(shù)據(jù)點集轉(zhuǎn)換到一個統(tǒng) 一的坐標系中，該技術(shù)稱之為數(shù)據(jù)縫合，即三維點云數(shù)據(jù)的配準。 點云配準實際上相當于數(shù)學上的映射問題， 即找到相鄰兩個點云數(shù)據(jù)的一一 對應關(guān)系，或者說要找到一個合適的變換關(guān)系，將一個坐標系統(tǒng)下的點云轉(zhuǎn)換到 另外一個坐標系統(tǒng)中。 本文在總結(jié)國內(nèi)外學者研究成果的基礎(chǔ)上， 著重研究了三維激光掃描數(shù)據(jù)的 空間配準問題， 地面三維激光數(shù)據(jù)配準方法大致分為基于特征的數(shù)據(jù)配準和迭代 法數(shù)據(jù)配準：ICP(Iterative Closest Point)算法是點云配準的常用算法，他同 視角點云中的對應點對的映射關(guān)系，采用最小二乘坐標轉(zhuǎn)換矩陣，迭代求解直到 滿足精度要求。一般來說，這種方法精度比較高但是對應的速度也較慢。本文提 出了一種新的利用空間相似變換進行不同視點的點云配準，其參數(shù)幾何意義明 確，也便于可靠性及誤差分析?？臻g相似變換是近來剛剛發(fā)展并得到應用的點云 配準的方法， 利用空間相似變換可以確定立體模型在地面坐標系中的正確方位和 比例尺歸化因子。本文主要涉及三維激光掃描數(shù)據(jù)點云的配準，并重點介紹空間 相似變換在點云配準中的應用。 關(guān)鍵詞：三維激光掃描；關(guān)鍵詞：三維激光掃描；ICPICP配準；空間相似變換配準；空間相似變換；點云配準；點云配準 河海大學學士學位論文 空間相似變換在點云配準中的應用 4 Abstract In recent decades, computer graphics have developed rapidly. With the development of computer graphics, some related technologies have emerged, or has made substantial progress based on the original. Virtual reality, digital city, digital museum, reverse engineering and other new terms have emerged and begun to enter the application stage. These technologies are essential to the needs of three-dimensional geometric modeling, but traditional AutoCAD, 3D Max, MAYA and other modeling tools have been increasingly incompetent people need for complex surface modeling of objects, thus three-dimensional laser scanning technology came into being. In order to obtain the real three-dimensional model of the objects, people need to get the real data on the surface of three-dimensional. However, due to measurement equipment and environmental constraints, the full surface measurement data obtained through multiple measurements are completed. Therefore, in the point cloud data obtained after the three-dimensional model in order to get the original surface, must be to different angles and different positions scanned by the large-capacity three-dimensional data points converted to a common coordinate system, the technology known as data suture, or three-dimensional point cloud data registration. Point cloud registration in fact equivalent to the mapping of mathematical problems, that two adjacent point cloud data to find the corresponding relationship, or to find a suitable transformation between a coordinate system conversion to another point cloud a coordinate system. This review describes the basis of academic research, and focused on the spatial three-dimensional laser scan data registration problems, ground-dimensional laser data registration method can be divided into feature-based iterative method of data registration and data registration: ICP (Iterative Closest Point) algorithm is commonly used point cloud registration 河海大學學士學位論文 空間相似變換在點云配準中的應用 5 algorithm, his view point cloud with the corresponding point on the mapping, using the least square coordinate transformation matrix, iterative solution until you meet the required precision. In general, this approach corresponds to high precision and speed, but slower. This paper presents a new similarity transformation space for different point of view of point cloud registration, a clear geometric meaning of its parameters, but also easy to reliability and error analysis. Space similarity transformation is just recently developed and applied to point cloud registration method, the use of space can determine the three-dimensional model similar transformation on the ground coordinate system in the correct orientation and scale factor naturalization. This article mainly deals with three-dimensional laser scan data point cloud registration, and highlights the similar transformation in the point cloud space registration application. KeyKey words: 3D lawords: 3D laser scanning; ICP Registrationser scanning; ICP Registration; ;s space pace s similarity imilarity t traransformationnsformation ; ; p point oint c cloud loud R Registrationegistration 目錄目錄 第一章 緒論 1 1.1 三維激光掃描技術(shù)及其應用 1 1.2 三維激光掃描技術(shù)特點 2 1.3 點云數(shù)據(jù)配準的意義 4 1.4 點云數(shù)據(jù)配準算法的研究進展 6 第二章 研究現(xiàn)狀及原理 9 2.1 ICP 算法在點云配準中的應用 . 9 2.2 空間相似變換在點云配準中的應用 . 13 2.2.1 基于矩陣論的空間相似變換 . 13 2.2.2 基于空間向量的空間相似變換 . 15 第三章 應用與實驗. 21 3.1 數(shù)據(jù)的獲取 . 21 3.2 間接平差原理 . 22 3.3 利用已知對應同名點求轉(zhuǎn)換參數(shù) . 24 3.4 點云的配準 . 29 第四章 總結(jié)與展望. 31 4.1 實驗后的結(jié)論 31 4.2 展望 31 參考文獻. 32 致 謝 34 附錄一 英文翻譯. 35 附錄二. 47 河海大學學士學位論文 空間相似變換在點云配準中的應用 1 第一章 緒論 1.1 三維激光掃描技術(shù)及其應用 長久以來，由于受到科學技術(shù)發(fā)展的限制，人們所能夠得到并對之進行處理 的絕大多數(shù)是二維的數(shù)據(jù)。然而，隨著現(xiàn)代信息技術(shù)的飛速發(fā)展以及圖形應用領(lǐng) 域的不斷擴大， 如何將現(xiàn)實世界的立體信息快速的轉(zhuǎn)換為計算機可以處理的數(shù)據(jù) 稱為人類追求的目標。1965年，L.Robert在其論文“三維物體的機器感知”中指 出利用計算機視覺技術(shù)獲取物體三維信息的可能性， 這標志著三維信息獲取技術(shù) 新紀元的到 9 來。之后，科研人員相繼提出了立體視覺、結(jié)構(gòu)光等方法，并得到 了實際應用。隨著電子技術(shù)的飛速發(fā)展，三維激光掃描儀的出現(xiàn)為三維空間信息 獲取提供了更便捷的手段。 在現(xiàn)有的數(shù)據(jù)采集技術(shù)中,三維激光掃描(LiDAR)技術(shù)以其獨特的優(yōu)勢,向人 們展示了復雜曲面三維信息獲取、三維重建、逆向工程、虛擬地理環(huán)境等方面廣 闊的應用場景。通過三維激光掃描，可快速、方便地將真實世界的立體信號轉(zhuǎn)化 為計算機上可直接處理的數(shù)字信號， 為真實世界的數(shù)字化提供了一種以往其他任 何技術(shù)無法比擬的手段。 三維掃描儀是針對三維信息領(lǐng)域的發(fā)展而開發(fā)的計算機輸入信息的前端設(shè) 備。利用該設(shè)備只需要對任意實際物體進行掃描，即可在電腦上得到實物的三維 圖像和物體的真實色彩。Cyberware公司研制出了世界上最早的三維掃描儀并將 其商品化，投入使用，進入90年代后，三維掃描技術(shù)已體現(xiàn)出廣闊的應用前景和 強大的生命力。目前，國外有幾十家高科技公司開展了對三維掃描技術(shù)的研究并 形成了自己的產(chǎn)品。 這些設(shè)備使用與各種不同大小的物體， 根據(jù)應用背景的不同， 精度、速度也有很大的區(qū)別。其掃描原理也有很多種，基本上可以分為接觸式和 非接觸式兩大類。接觸式的掃描對于被掃描物體本身可能造成損害，也不適用于 柔軟物體的測量，因此現(xiàn)在的主流掃描設(shè)備都是非接觸式的。 三維掃描技術(shù)能獲得物體表面點的三維坐標信息，屬于一種立體測量技術(shù)。 與傳統(tǒng)測量技術(shù)相比，該技術(shù)能完成對復雜物體的測量，而且精度高、速度快、 河海大學學士學位論文 空間相似變換在點云配準中的應用 2 能大幅節(jié)約時間和成本，因而在下述領(lǐng)域的應用中體現(xiàn)出重要價值： (1)(1)文化遺產(chǎn)的精密數(shù)字化保護與重建 中國是歷史文明古國，在歷經(jīng)上下五千年的人類文明歷史后，留下了無數(shù)的 文化遺產(chǎn)?，F(xiàn)在這些文化遺產(chǎn)隨著時間流逝和國家現(xiàn)代化的過程，正瀕臨消失。 因此近些年來全國文物保護的呼聲越來越響，國內(nèi)也有很多文化遺產(chǎn)如故宮、長 城、布達拉宮等被列為世界文化遺產(chǎn)。文物保護一般有兩個方面：一方面是文物 現(xiàn)狀的資料保存；另一方面是文物的修繕或者重建，這些修繕或重建應該在保持 文物原有風格的基礎(chǔ)上進行，這就要求必須詳細記錄文物現(xiàn)狀。利用激光掃描技 術(shù)可以詳細記錄文物的外形和表面紋理信 12 息。 （2 2）重要工程的竣工驗收與精密數(shù)字化 對于大型且結(jié)構(gòu)復雜的建筑結(jié)構(gòu)，通常需要對建筑構(gòu)件進行安裝定位，對結(jié) 構(gòu)的整體變形或局部施工質(zhì)量作檢驗，確定實際建筑是否與設(shè)計要求吻合。三維 激光掃描技術(shù)能夠完成這些工作， 同時還能記錄建筑物的三維信息作為建筑物的 歷史資料 （3 3）建筑物的精密變形監(jiān)測 傳統(tǒng)的變形監(jiān)測多是基于測量儀器的逐點監(jiān)測。利用三維激光掃描技術(shù)，可 以將監(jiān)測對象的整體模型構(gòu)建出來， 通過定期對比模型的方法來全方位的反映監(jiān) 測對象各處的形變。 1.2 三維激光掃描技術(shù)特點 三維激光掃描技術(shù)是近年來剛剛發(fā)展起來并正在逐步走向成熟的一項三維 數(shù)據(jù)獲取技術(shù)。 通過該技術(shù)可真正實現(xiàn)直接從實物進行快速的逆向三維數(shù)據(jù)采集 及模型重構(gòu)。它的出現(xiàn)和發(fā)展為空間三維信息的獲取提供了全新的技術(shù)手段，為 信息數(shù)字化發(fā)展提供了必要的生存條件。激光測量技術(shù)出現(xiàn)于上世紀80年代，由 于激光具有單色性、方向性、相干性和高亮度等優(yōu)異性能，使其在精度、速度、 易操作性等方面表現(xiàn)出巨大的優(yōu)勢，引發(fā)了現(xiàn)代測量技術(shù)的一場革命。該技術(shù)具 有如下一些特 13 點： （1）數(shù)據(jù)獲取速度快，實時性強：激光掃描測量能夠快速獲取大面積目標 河海大學學士學位論文 空間相似變換在點云配準中的應用 3 空間信息。常用的地面三維激光掃描儀的掃描點采集速度可達每秒數(shù)千點以上， 某些型號的掃描儀采集速度高達每秒數(shù)十萬點?？蓪崟r的測定尸體表面立體信 息。 （2）非接觸性：采用完全非接觸的方式進行掃描測量，不需要反射棱鏡， 無需對掃描目標物體進行任何表面處理便可采集物體表面的矢量化三維坐標數(shù) 據(jù)，快速實現(xiàn)原型重構(gòu)，并能色彩還原。可以用于解決危險復雜目標、環(huán)境及工 作人員難以到達的情況，且在光線昏暗甚至黑夜是均可作業(yè)。具有傳統(tǒng)測量方式 難以完成的技術(shù)優(yōu)勢 9。 （3）主動性強，能全天候工作：地面三維激光掃描技術(shù)采用主動發(fā)射激光， 通過探測器自身發(fā)射的激光脈沖回射信號來描述目標信息， 從而實現(xiàn)不受掃描環(huán) 境的時間及空間的約束。 （4）高密度、高精度：激光掃描能夠快速、高精度的獲取海量點云數(shù)據(jù)， 實現(xiàn)對掃描目標的高精度三維數(shù)據(jù)采集，從而達到高分辨率的目的。 （5）全數(shù)字化特征、兼容性好：系統(tǒng)掃描獲取的數(shù)字距離信號具有全數(shù)字 化特征，易于自動化顯示輸出，可靠性好。用戶界面有好的后處理軟件具有很好 的點云處理、建模處理能力，能夠達到與其他軟件相兼容、共享和互操作。 （6）與數(shù)碼相機、GPS系統(tǒng)集成使用：新型掃描系統(tǒng)繼承了GPS接收機和數(shù) 碼相機等高精度定位裝置，系統(tǒng)外置（或內(nèi)置）的數(shù)碼相機的使用增強了彩色信 息的采集，對信息的獲取更加全面。GPS定位系統(tǒng)的使用，進一步提高了測量數(shù) 據(jù)的準確性。 （7）適應性強：一般常用的激光掃描設(shè)備對于目標環(huán)境及工作環(huán)境的依賴 性都很小，且其體積小、防水、防輻射、防震動、防潮等特性，有利于進行各種 場景或野外環(huán)境的操作。 但該技術(shù)仍有很多不足之處，簡單歸納如下： （1） 掃描儀是個黑箱系統(tǒng)，難以檢校；以其昂貴，市場定位為高檔設(shè)備。 （2） 掃描數(shù)據(jù)后處理時間可達數(shù)據(jù)采集所需時間的10倍，掃描易，處理難。 （3） 掃描數(shù)據(jù)拼接軟件不完善， 各廠家自成一體， 互不兼容； 缺乏標準化思考， 缺乏實用而價格相對便宜的軟件；考古學家、文物保護人員、建筑學家較 難進一步使用三維建模成果開展專業(yè)研究工作。 河海大學學士學位論文 空間相似變換在點云配準中的應用 4 （4） 三維建模有一定的主觀性，非專業(yè)人士常受到虛擬動畫的視覺迷惑，忽視 了三維模型的可測量和科學性。 1.3 點云數(shù)據(jù)配準的意義 在計算機中對客觀環(huán)境進行真實的三維重建，一直以來都是計算機視覺、機 器人學以及計算機圖形學所研究的熱門領(lǐng)域之一。近年來，隨著激光掃描技術(shù)的 發(fā)展以及其成本的逐漸降低， 快速高效地獲取真實場景的高精度三維數(shù)據(jù)成為可 能。利用這些數(shù)據(jù)，可以重建出具有準確幾何信息、甚至照片級真實感的三維模 型。利用三維激光掃描技術(shù)進行三維重建，主要需解決如下幾個問題： （1 1）數(shù)據(jù)獲?。褐笇鼍暗娜S數(shù)據(jù)的獲取，這一步主要由激光掃描儀來 完成。為了高效而高質(zhì)量的獲取一個大型場景的完整的三維數(shù)據(jù)，在數(shù)據(jù)獲取方 面還存在很多問題，比如掃描試點的規(guī)劃、掃描儀和掃描分辨率的選擇、掃描數(shù) 據(jù)的格式及表示等等。 （2 2）點云數(shù)據(jù)的配準：這是數(shù)據(jù)獲取后所要做的第一項工作，是后續(xù)工作 的基礎(chǔ)和前提，因此是非常重要的一個環(huán)節(jié)。 （3 3）點云數(shù)據(jù)的融合與表面重建：當多視點點云數(shù)據(jù)配準到同一坐標系后， 其重合的部分必然會有兩層數(shù)據(jù)， 造成數(shù)據(jù)的冗余和不一致， 需要進行數(shù)據(jù)融合。 另外， 由激光掃描得到的點云數(shù)據(jù)一般都是離散的三維點， 數(shù)據(jù)量大、 存在冗余， 與實際應用的要求仍有一定差距。 常用的解決方法是對點云進行三角剖分以重建 表面，三角剖分得到的三角網(wǎng)模型可以很好的逼近實物 9。 (4) (4) 紋理映射：經(jīng)過前述過程對實體進行了數(shù)字化，并獲得了精確的數(shù)字 幾何模型。但為了體現(xiàn)模型表面的屬性及特征，需要將拍到的實體的一系列彩色 照片準確映射到幾何模型上，即模型的無變形紋理映射。 因此， 基于三維激光掃描技術(shù)進行實體空間數(shù)據(jù)獲取和三維重建一般應該采 用如下流程： 河海大學學士學位論文 空間相似變換在點云配準中的應用 5 從上述流程可以看出，作為利用點云數(shù)據(jù)場景三維重建系統(tǒng)的一部分，研究 點云配準的重要性和意義主要體現(xiàn)在以下幾個方面： （1）三維激光掃描系統(tǒng)雖然具有精度高、作業(yè)速度快等數(shù)據(jù)獲取的能力， 使空間目標的采集不再困難，但其數(shù)據(jù)處理卻成為它廣泛應用的瓶頸，大力發(fā)展 三維激光掃描的數(shù)據(jù)處理技術(shù)是三維建模的關(guān)鍵問題。 （2）為了得到物體真實的三維模型，人們需要獲得三維物體表面的真實數(shù) 據(jù)。但是，由于受到測量設(shè)備和環(huán)境的限制，物體表面完整測量數(shù)據(jù)的獲得往往 需要通過多次測量完成。 點云(三維數(shù)據(jù))就是使用各種三維數(shù)據(jù)采集儀采集得到 的密集數(shù)據(jù)，它記錄了有限體表面在離散點上的各種物理參量。三維曲面的重建 圖 1.1 三維激光掃描數(shù)據(jù)的處理流程圖 三維建模 （3D Modeling） 其它應用 （Other Application） 格網(wǎng)建立 （Mesh Establishing ） 曲面擬合 （Surface Fitting） 數(shù)據(jù)縮減 （Data Reduction） 數(shù)據(jù)分割 （Data Segmentation） 數(shù)據(jù)配準 （Data Registration） 原始三維激光掃描數(shù)據(jù) （3D Point Could） 融合后的點云數(shù)據(jù) （Integrated Point Could） 點云數(shù)據(jù)平滑處理 （Data Noise Removal） 河海大學學士學位論文 空間相似變換在點云配準中的應用 6 就是依據(jù)這種密集的點云數(shù)據(jù)來恢復原始曲面， 進而實現(xiàn)三維模型的真實重現(xiàn)的 目的 （3）通常的三維激光掃描系統(tǒng)一次只能得到物體的一個側(cè)面的點云數(shù)據(jù)， 要得到地物完整的形狀信息，須采用多測站多視角掃描。由于不同位置進行掃描 時坐標系不同，需要將 多測站下的掃描的三維數(shù)據(jù)進行拼合，將其轉(zhuǎn)換到同一 坐標系下并進行數(shù)據(jù)融合，才能獲得物體表面的完整的形狀信息。這種三維坐標 系的統(tǒng)一和點云融合過程就是數(shù)據(jù)配準。 點云配準是點云數(shù)據(jù)獲取后的第一步處 理，也是所有后續(xù)處理的基礎(chǔ)。因此，配準的精度將直接關(guān)系到建模精度。 1.4 點云數(shù)據(jù)配準算法的研究進展 1.4.1 國內(nèi)外研究進展 數(shù)據(jù)的配準是一個寬泛的概念，早期主要應用在圖像處理中。據(jù)文獻記載， 國外在六十年代就在圖像配準領(lǐng)域進行了相關(guān)的研究， 但是直到八十年代后才開 始引起廣泛的關(guān)注（劉松濤，2007） 常見的圖像配準方法有機遇圖像灰度的方法（王小睿，1997：A.Averbuch， 2002）和基于圖像特征（鈕永勝，1999；周鵬，2002；李秀秀等，2008）的方法。 基于圖像灰度的配準方法，通常直接利用整幅圖像的灰度信息，建立兩幅圖像之 間的相似性度量， 然后采用某種搜索方法尋找使相似性度量值最大或最小的變換 模型的參數(shù)值。這種方法能提高估計的精度，但計算量很大，速度較慢。而基于 圖像特征的配準方法是目前采用最多的，它主要的優(yōu)點是提取了圖像的顯著特 征，大大壓縮了圖像的信息量，計算量小，但這種方法對特征提取和特征匹配的 錯誤更敏感?；趫D像特征的配準方法包括特征提取、特征匹配、選取變換模型 及求取參數(shù)、坐標變換與插值四個組成部分（倪國強，2004）?，F(xiàn)在圖像配準已 廣泛應用于遙感圖像處理、醫(yī)學圖像分析、目標變化監(jiān)測、目標識別等領(lǐng)域中。 二十世紀八十年代中期，由于三維激光掃描系統(tǒng)的應用，國外很多學者開始 對三維激光掃描數(shù)據(jù)的空間配準進行了研究。 1986年，F(xiàn)augeras和Hebert用四元 素概念進行了配準方法的研究，提出了點集與點集間的匹配方法（Faugeras， 1986）。1987年，Horn和Arun等人同樣用四元素法提出了點集對點集配準的方法 PSTPS(Point Set to Point Set Registration)，這種點集與點集坐標系匹配算 河海大學學士學位論文 空間相似變換在點云配準中的應用 7 法通過實踐證明是一個解決復雜配準問題的關(guān)鍵方 10 法。1992年，計算機視覺 研究者Bes1和Mckay介紹了一種高層次的基于自由形態(tài)曲面的配準方法，也就是 迭代最近點法。 上述數(shù)據(jù)配準的算法多是只包括兩個站點間坐標系的統(tǒng)一， 主要應用在工業(yè) 產(chǎn)品的模具和制造產(chǎn)業(yè)中。隨著長距離三維激光掃描系統(tǒng)的發(fā)展成熟，為城市建 模提供了更先進的數(shù)據(jù)采集手段。這是針對地理場景的數(shù)據(jù)配準有了新的特點， 本文根據(jù)三維激光掃描數(shù)據(jù)的特點，把點云數(shù)據(jù)的空間配準分為兩個階段，分別 是三維坐標系的統(tǒng)一和數(shù)據(jù)融合。 多站掃描結(jié)果之間點云的配準， 實際上是將兩個或兩個以上坐標系中的海量 三維空間數(shù)據(jù)點集轉(zhuǎn)換到同一坐標系統(tǒng)的數(shù)學計算過程。 一般這種變換關(guān)系可以 用一個3*3的旋轉(zhuǎn)矩陣R和一個三維平移向量T來描述，數(shù)據(jù)配準的任務(wù)就是求出 （R,T） Vorady（1997）介紹了一種轉(zhuǎn)臺定位法：將測量物體放在旋轉(zhuǎn)臺上，通過測 量物體和轉(zhuǎn)臺同步旋轉(zhuǎn)，調(diào)整物體的測量位置，設(shè)法測得各個不同角度的數(shù)據(jù)， 然后可以從轉(zhuǎn)臺上讀取相應旋轉(zhuǎn)角來求得旋轉(zhuǎn)矩陣， 這種情況沒有平移量： 此外， 還可固定測量物體， 通過關(guān)節(jié)是掃描系統(tǒng)機械臂的空間運動來記錄測量的空間位 置變換。這兩種方法都需要讀取測量設(shè)備的刻度進行坐標變換，對測量人員和測 量設(shè)備的要求較高，而且定位精度不易保證（吳敏等，2003）。顯然，這兩種方 法都不適合于長距離激光掃描儀獲得的地理場景數(shù)據(jù)的空間配準。 一般而言，為了求出R和T，需要在多測站點云中找出若干組對應的特征或同 名點。就算法而言，對于數(shù)據(jù)配準問題，一直以來存在兩種策略。一種是上世紀 就是年代初提出的著名的迭代最近點（Iterative Closest Point，ICP）算法， 另一列方法是利用離散的特征進行匹配的方法。 兩者的主要區(qū)別在于用于配準的 點云數(shù)量級的不同，ICP算法可看做是把某一點集中的所有點當做同名點進行計 算。 針對上述各種形式的點云數(shù)據(jù)，在20世紀80年代中期，很多學者對其配準 進行了大量研究。 1987年， Horn、 Arun等人用四元素法提出點集對點集配準方法。 這種點集與點集坐標系匹配算法通過實踐證明是一個解決復雜配準問題的關(guān)鍵 方法。1992年，計算計視覺研究者Besl和Mckay介紹了一種高層次的基于自由形 河海大學學士學位論文 空間相似變換在點云配準中的應用 8 態(tài)曲面的配準方法，也稱為迭代最近點法ICP（Iterative Closest Point），并 在此基礎(chǔ)上產(chǎn)生了許多的變種算法。ICP主要用于解決基于自由形態(tài)曲面的配準 問題。但ICP 算法對兩個點云相對的初始位置要求比較高，點云之間初始位置不 能相差太大，并且要求兩個匹配點集中的一個點集是另外一個點集的子集。當條 件不滿足，或相差太大時，會影響ICP的收斂方向，這將導致算法的精確度和收 斂速度受到影響，甚至還有可能陷入局部最優(yōu)解，因而配準結(jié)果也是不可靠的。 1.4.2 當前研究中的缺陷與不足 綜上所述，三維數(shù)據(jù)空間配準方法已經(jīng)有了很大的發(fā)展，然而由于掃描物體 的復雜性，大多數(shù)的配準方法都有其自身的局限性，主要表現(xiàn)在： （1） 傳統(tǒng)逆向工程單個物體上用到的配準方法在地理場景配準應用上具有較 大的限制， 無論是轉(zhuǎn)臺定位法還是回轉(zhuǎn)配準法都無法直接應用在地理場景 掃描中； （2） 采用平面或其他特征作為數(shù)據(jù)配準的方法還不成熟，主要表現(xiàn)在：不同視 圖中的特征往往不一致， 甚至同一個特征在其它視圖中被分割程序多特征 或者消失，同時該方法帶來的集合圖形之間的布爾運算將涉及到許多CAD 種目前尚未解決的或解決不甚圓滿的難題，如曲面的拼接、求交、延拓和 過渡等； （3） 各種ICP及改進算法的最大問題在于其算法的復雜性，兩個測站的配準就 會需要極大的計算量， 不適合以大量測站為特征的地理場景的三維激光掃 描數(shù)據(jù)的快速配準； （4） 現(xiàn)有的研究多集中在兩站測量數(shù)據(jù)的坐標系統(tǒng)一過程中， 對于多測站的數(shù) 據(jù)配準和數(shù)據(jù)融合的研究比較缺乏。 因此，針對中場距離掃描系統(tǒng)采集到的地理場景數(shù)據(jù)的空間配準，有必要采取更 加合理的方法進行配準研究，解決三維建模過程中數(shù)據(jù)統(tǒng)一的問題。 河海大學學士學位論文 空間相似變換在點云配準中的應用 9 第二章 研究現(xiàn)狀及原理 在無法預知點云數(shù)據(jù)間的相互關(guān)系式，迭代算法的有效性得到了質(zhì)疑，這是 基于幾何特征的配準算法就顯示了明顯的優(yōu)勢， 這種算法根據(jù)點云或者曲面的特 征來尋找特征相似區(qū)域，在此基礎(chǔ)上，通過最小化目標函數(shù)的方法來提高配準的 精確性， 這種方法配準效率較高， 并且對于如局部重疊的點云數(shù)據(jù)， 適用性較好。 基于特征的配準能有效地計算出點云間的對應性， 而迭代算法能夠得到精確 地配準效果，因此，在實際應用中，配準算法往往以基于幾何特征的配準作為預 配準，以迭代配準作為精確配準。這樣，既解決了迭代算法收斂的不確定性，又 減少了迭代過程的配準時間。 本文作者在深入學習了江剛武、 潘國榮等人的文獻中提出的基于矩陣論的空 間相似變換以及基于空間向量的空間相似變換的基礎(chǔ)上， 利用matlab實現(xiàn)了旋轉(zhuǎn) 矩陣和平移參數(shù)的計算，并且編程實現(xiàn)了空間三維坐標轉(zhuǎn)換，針對乒乓球的點云 數(shù)據(jù)進行了數(shù)據(jù)配準的試驗，取得了較好的配準效果。下面介紹一下這種空間相 似變換模型，并簡要的介紹一下目前應用最為廣泛的ICP點云配準算法的原理。 2.1 ICP 算法在點云配準中的應用 點云配準有手動配準、依賴儀器的配準和自動配準。通常我們所說的點云配 準技術(shù)即是指最后一種。點云自動配準技術(shù)是通過一定的算法或者統(tǒng)計學規(guī)律, 利用計算機計算兩片點云之間的錯位,從而達到把兩片點云自動配準的效果。目 前采用的自動配準技術(shù)一般分為初始配準和精確配準兩步,初始配準是為了縮小 點云之間的旋轉(zhuǎn)和平移錯位以提高精確配準的效率和趨向,精確配準則是為了使 兩個點云之間的配準誤差達到最 8 小。 精確配準一般采用ICP（iterative closest point）算法。但傳統(tǒng)的ICP算 法計算效率不高，因此國內(nèi)外許多研究者都為改進ICP算法做出了努力。下面介 紹幾種常見的ICP配準的方法： 2.1.1點云初始配準 河海大學學士學位論文 空間相似變換在點云配準中的應用 10 為了縮小點云之間的旋轉(zhuǎn)和平移錯位，使得精確配準不致趨向錯誤的方向， 需要進行點云初始配準。本文采用點云主方向貼合法實現(xiàn)自動初始配準，具有方 便快捷精確的效果。 每個點云都存在一個空間上的主方向， 這個主方向可由計算點云中所有點的 特征向量得到，根據(jù)特征向量還可以得到與主方向垂直的兩個此方向。由此可建 立一個以點云重心為原點，點云主方向以及次方向為坐標軸的一個參考坐標系。 這樣，對于相似度大的兩個點云，只要把兩個參考坐標系調(diào)整到一致，即可以實 現(xiàn)點云配準。對于差異較大的點云，通過這種方式，也可以達到縮小點云之間錯 位的目的。 由于主方向具有正反兩個方向,因此可能出現(xiàn)配準后兩個點云正好相差 180的情況,所以配準后還需測試是否出現(xiàn)這種情況。 本文通過計算兩個點云的 包圍盒來測試兩點云是否重合。設(shè) R V（下角R代表reference）為參考點云包圍 的體積， T V（下角T代表target）為目標點云包圍的體積， i V為參考點云和目標 點云包圍相交得到的包圍的體積。則包圍和重合系數(shù)為：(*)/(*) iiRT fVVVV (1) 如果fT,T為設(shè)定閾值,則兩點云大致重合。否則兩點云不重合,反轉(zhuǎn)參考坐 標系的X軸或Y軸再次測試。如果4種可能性都測試過，并且沒有任何一個f大于T, 則說明兩點云差異較大，去f最大的那種即可。 算法流程說明如下: (1) 讀取參考點云和目標點云; (2) 分別粗略選取兩片點云可以重疊部分; (3) 分別用雅克比法計算選取區(qū)域的特征向量 和特征值,按特征值從大到小排列特征向量為EV0 , EV1 , EV2 ; (4) 分別計算點云重心C,以C為原點,以EV0 為X軸, EV1 為Y軸, EV0 EV1 為Z 軸, 建立參考 坐標系; (5) 由兩個坐標系計算得到坐標變換矩陣; 河海大學學士學位論文 空間相似變換在點云配準中的應用 11 (6) 根據(jù)坐標變換矩陣變換目標點云坐標; (7) 測試變換后點云和參考點云是否大致重合 合,不重合則反轉(zhuǎn)目標點云X 軸或Y 軸, 跳到步驟5; (8) 點云重合,結(jié)束。 2.1.2 點云精確配準 為了盡可能配準兩個點云使它們之間的誤差最小,還需在初始配準的基礎(chǔ)上 進行自動精確配準。 本文采用基于特征點的ICP算法進行精確配準,該算法可以有 效提高計算速度,對于海量數(shù)據(jù)點云效果十分顯著,可以有效縮短原ICP算法的計 算時間。 在研究ICP算法之前,必須先了解其中所使用的一個關(guān)鍵算法, 即對應點 集配準算法(corresponding point set registration)。 對應點集配準的單位四元數(shù)法 對應點集配準算法的目標在于尋找最小二乘逼近的坐標變換矩陣,對于互相 對應的兩個點集,可以采用單位四元數(shù)法 1 得到。 若目標點集P對應于參考點集X, 對應點集應滿足以下條件: (1) P中點的個數(shù)NP 和X中點的個數(shù)NX 相等,即NP =NX ; (2) 對于P中每一個點pi 都應該對應于X中具有相同下標i的xi ,即pi = xi。 設(shè)旋轉(zhuǎn)變換向量為單位四元數(shù) 0123 , T R qq q q q，其中 0 q0，并且 2222 0123 1qqqq， 可得3*3旋轉(zhuǎn)矩陣() R R q。 設(shè)平移變換向量為 T q= 456 , T q q q， 可得完全坐標變換向量 T RT qq q 。則求對應點集間的最佳坐標變換向量問題 可轉(zhuǎn)化為求q使得函數(shù)： ( )f q= 1 P N 2 1 () P N iRiT i xR qpq （3-1-1） 最小化的問題。 算法流程如下： (1) 得到對應點集P和X; (2) 計算目標點集P 的重心和參考點集X的重心: 11 11 , p X N N piXi ii PX uP uX NN (3-1-2) (3) 由點集P和X構(gòu)造協(xié)方差矩陣: 河海大學學士學位論文 空間相似變換在點云配準中的應用 12 , 1 1 ()() P N T iPix P X i P puxu N 1 1 P N TT iipx i P p xu u N （3-1-3） (4) 由協(xié)方差矩陣構(gòu)造4 4對稱矩陣: , 3 P,X, () Q()=() T P X T P XP XP X tr trI （3-3-4） 其中， 3 I是33的單位矩陣， , () P X tr是矩陣 ,P X 的跡， 233112 , T AAA , , i j A , , () T i j P XP X ； （5）計算Q , () P X 的特征值和特征向量，其最大特征值對應的特征向量即為最 佳旋轉(zhuǎn)向量 R q= 0123 T q q q q； （6）計算最佳平移向量 () TXRp quR q u （3-1-5） ，其中： () R R q 2222 012312031302 2222 120301232301 2222 130223010123 2()2() 2()2() 2()2() qqqqq qq qq qq q q qq qqqqqq qq q q qq qq qq qqqqq （3-1-6） （7）得到完全坐標變換向量 T RT qq q = 0123456 T q q q q q q q,求得最小均方誤差 ms d=( )f q； （8）結(jié)束 把這種對應點集配準算法記為( , ) ms q d =( ,)Q P X.并用( )q P表示P根據(jù)坐標變換 向量q變換后的點云。 2.1.3 改進的ICP算法 ICP算法是當前應用最廣的點云配準算法。 ICP算法雖然基本能夠滿足點云配 準在精度上的要求,但算法本身計算效率不高,花費時間太多,特別是對于實際測 量中的海量數(shù)據(jù)無法直接使用。因此需要對其進行改進,提高計算效率。 ICP算法的時間代價是() PX O N N。在實際測量中,當數(shù)據(jù)量很大時(例如幾十 河海大學學士學位論文 空間相似變換在點云配準中的應用 13 萬甚至幾百萬個點) ,所花費的時間將是驚人的。如果能夠減少時間代價到 () P O N ,并且同時保證配準精度的話,就能應用于實際測量的模型之中。 由于ICP 算法中主要是求最近點集的算法花費時間比較多,如果能夠把這個步驟的時間代 價減少到() P O N ,即可達到目的。 (1) 得到目標點云P (含有 P N個點)和參考云X(含有 X N個點); (2) 根據(jù)點的曲率特征,在P 中尋找n個特征點( n為常數(shù),例如n = 1 000) ,得到 特征點集F; (3) 初始化: 0 FF, T 0 q1,0,0,0,0,0,0, k=0； (4) 利用k-d tree尋找F在X中的最近點Y: kk YC(FX)， (5) 計算坐標變換向量和誤差: kk qd（ ， ）= 0k Q(FY，） (6) 特征點集坐標變換: k 1k0 FqF ) （; (7) 判斷誤差是否收斂,如果 kk 1 dd ，為設(shè)定值且0,則收斂，否則跳到 步驟4； (8) 誤差收斂于 , 目標點云坐標變換: P= ( ) k qP ; (9)結(jié)束。 2.2 空間相似變換在點云配準中的應用 在攝影測量學里,為了確定立體模型在地面坐標系中的正確方位和比例尺歸 化因子,一般采用空間相似變換的方法。正確求解空間相似變換中的各項參數(shù), 需要一定數(shù)量的控制點，這里至少需要三個點才能求出轉(zhuǎn)換參數(shù)，下面介紹兩種 利用空間相似變換求取轉(zhuǎn)換參數(shù)的原理和方 2 法： 2.2.1 基于矩陣論的空間相似變換 設(shè)有兩個空間直角坐標系分別為O-XYZ和O-XYZ,其坐標系原點不一致, 存在三個平移參數(shù)XYZ、；它們間的坐標軸也相互不平行，存在三個旋 轉(zhuǎn)參數(shù)XY、Z。 同一點A在兩個坐標系中的坐標分別為(X,Y,Z)和(X,Y,Z)。 河海大學學士學位論文 空間相似變換在點云配準中的應用 14 顯然，這兩個坐標系通過坐標軸的平移和旋轉(zhuǎn)可取的已知，坐標系的轉(zhuǎn)換關(guān) 系如下，3D 空間下,設(shè)兩個不同坐標系間的對應點坐標分別為X,Y,Z和X,Y,Z， 則兩者的轉(zhuǎn)換可用公式表示 3 為: X XX YYR Y ZZ Z （3-2-1） 其中, X,Y 和Z 均為平移參數(shù); 為比例因子；R為正交旋轉(zhuǎn)矩陣: 111213 212223 313233 rrr Rrrr rrr 111213 2122 2331 r = cos () cos () r = - cos () sin () , r = - sin, r = cos() sin() - sin() sincos() , r = cos () cos () + sin ()sin sin() , r = - sin () cos () , r = s YZYZY XZXYZXZXYZ XY 且， 3233 in () sin () + cos ()sincos() , r = sin () cos () - cos () sin sin (), r = cos ()cos() XZXYZ XZXYZ