1、摘 要碩士學位論文 光學三維快速檢測系統中的點云融合技術研究與應用Point Cloud Integration in 3D Fast Measuring System學科專業：機械制造及其自動化2009年01月論文題目：光學三維快速檢測系統中的點云融合技術研究與應用學科專業：機械制造及其自動化摘 要針對現有點云融合方法融合數據速度慢、占用內存大、不能適用于光學三維快速檢測的問題，在深入研究國內外已有點云融合理論的基礎上，結合面結構光掃描技術的特點以及快速檢測的工程實際需求，本文對光學三維快速檢測中的點云融合技術進行深入研究。主要內容和成果如下： (1)設計并實現了針對光學三維快速檢測系統的點

2、云融合方案，即首先對點云進行預處理：去除孤立點、計算法向量、計算點云權值、減小邊界點權值、精簡數據等。然后融合多層點云數據，獲得單層完整的點云數據，用于比對檢測或逆向設計。(2)設計并實現了單面法融合點云數據的方法。首先確定基準點云，然后根據給定的誤差帶確定并去除非基準點云中的重疊點，最后將不包含重疊點的多幅點云合并為單層的一幅點云。該方法的優點是效率高，可以很好的應用于快速檢測中，但該方法融合后的表面光滑度不好，不能很好的應用于逆向設計中。(3)設計并實現了中點法融合點云數據的方法。首先去除每幅點云中的孤立點，其次搜索兩幅點云中的對應點對，為了加快搜索速度，本文采用KD-Tree空間鄰域搜索

3、策略。最后用點對的中值代替點對中的兩個點，從而實現去除冗余點。該方法相對于單面法表面光滑度有所改善，但融合效率比單面法慢。(4)實現了聚類法融合點云數據的方法，并對該方法進行了改進：首先提出了結構光掃描技術中點云權值計算的理論，實現了結構光掃描技術中點云權值的計算；其次對KD_Tree空間鄰域搜索方法進行了改進，實現了一種高效的空間近鄰點云搜索策略，有效提高了點云數據融合的速度；最后提出按包圍盒等間距分割點云數據的方法，分塊多次融合點云，解決了融合海量點云數據時內存不足的問題。該方法融合效率比單面法低但比中點法高，融合后表面光滑，可以很好的應用于快速檢測和逆向設計中。經過試驗、分析及工程應用，

4、結果表明：本文提出的方法在保證點云數據融合精度的同時，提高了點云融合的效率，滿足了三維快速檢測的工程實際需求，效果良好。關 鍵 詞：光學三維快速檢測；點云融合；單面法；中點法；改進的聚類法；論文類型：應用研究61ABSTRACTTitle: Point Cloud Integration in 3D Fast Measuring System The research is funded by National 863 Plan（2007AA04Z124）& Jiangsu Province Technology Supporting Planned Project(BE2008058).Sp

5、eciality: Mechanical EngineeringApplicant: Baoquan ShiSupervisor: Vice-Prof. Liang JinABSTRACTThe point cloud integration technique of 3D optical rapid detection is in-depth studied in the paper,based on the theory of point cloud integration at home and abroad have been researched in-depth,for the e

6、xisting point cloud integration methods with slow efficiency, take much memory ,can not be applied to 3D optical rapid detection. The surface structure optical scan technique and the needs of rapid detection project are combinated to considered. The main contents and achievements are listed as follo

7、ws:(1) The point cloud integration program for 3d optical rapid detection system is designed and implemented.That is, at first,execute the point cloud pre-processing, remove the isolation, calculate the vector and value of points, decrease the weight of the border, sampling the data, and then integr

8、ate point cloud data, remove redundant points. At last contrast the point cloud data and CAD model. (2) The method of hold one layer among multi-overlap layers is realized. Find the base point cloud firstly;Then according to the error band,delete the overlap points in non-base point cloud;At last Al

9、l point clouds are Merged together to be one single layer point cloud.This method have a high integration speed,however the integrated surface is rough.(3) The method of interpolation between two layers is realized. First of all, remove each isolated point, search the corresponding points in two poi

10、nt clouds, using KD-Tree space neighborhood search strategy to speed up the search efficiency, take the median of corresponding points instead of them to remove points redundancy. Compared with the method of hold one layer among multi-overlap layers,this method is smoother in integration surface,but

11、 lower in integration speed .(4) The clustering integration method is realized and improved. At first, the theory of the ringhts of points in structure optical scan technique is put forward,and calculate the ringhts of points. then the KD_Tree search method is improved and achieve a highly efficient

12、 space neighbors search strategies to increase the speed of point cloud integration. Finally, divide point cloud data equidistance by boxes, repeatedly integrate point clouds in subblock to overcome the problem of memory lack in massive integration point cloud.this method have the most smooth integr

13、ation surface and the integrating speed lies between the anterior two methods.After testing and analyzing, combined its application in the 3D optical rapid detection system, the result shows that the approachs in this paper insure the accuracy of point cloud integration ,increase the efficiency of t

14、he point cloud integration, meet the demand of 3D rapid detection project, and prove a good performance in application.目 錄緒論目 錄1 緒論11.1 引言11.2 研究背景及國內外發展狀況11.2.1 研究背景11.2.2 國內外發展現狀11.2.3 國內外研究現狀總結41.3 課題來源與研究意義41.3.1 課題來源41.3.2 研究意義41.4 研究內容和技術路線51.4.1 研究內容51.4.2 技術路線52 點云融合方案72.1 引言72.2 XJTUOM系統72.

15、2.1 基本原理72.2.2 系統組成72.2.3 應用領域92.3 點云融合所處環節92.4 點云融合方案的確定102.4.1 點云融合系統設計原則102.4.2 針對光學三維測量系統的點云融合方案102.4.3 點云融合目標制定112.5 本章小結113 單面法123.1 引言123.2 單面法理論基礎123.3 單面法技術路線123.4 單面法關鍵技術133.4.1 三維空間鄰域搜索技術133.4.2 去除非基準點云中的重疊點153.5 采用的數據結構及軟件的基本框架163.5.1 本文采用的數據結構163.5.2 軟件的基本框架173.6 本章小結184 中點法204.1 引言204.

16、2 中點法理論基礎204.3 中點法技術路線214.4 中點法關鍵技術224.4.1 去除孤立點224.4.2 去除非基準點云中的無對應點的重疊點244.4.3 去除密集點254.5 軟件基本框架264.6 本章小結265 聚類法285.1 引言285.2 聚類法理論基礎285.2.1 層次聚類法295.2.2 類間聚類法(最簡單的聚類方法)295.2.3 最大距離樣本法305.2.4 k-means聚類305.2.5 迭代自組織（ISODATA）聚類法315.2.6 本文采用的聚類算法335.3 聚類法技術路線335.4 Ply文件格式345.5 聚類法關鍵技術365.5.1 快速三角化36

17、5.5.2 半邊(HalfEdge)數據結構375.5.3 法向量計算385.5.4 點云權值395.5.5 減小點云邊界權值405.5.6 根據點云的包圍盒分割點415.5.7 新的空間鄰域搜索策略415.5.8 融合第k塊點云425.6 軟件框架435.7 本章小結436 點云融合系統的實驗分析及應用446.1 點云融合的效果446.2 點云融合速率分析496.3 在檢測中的應用實例516.4 本章小結547 結論與展望557.1 結論557.2 展望56致 謝57參考文獻58聲明CONTENTS緒論CONTENTS1 Preface11.1 Foreword11.2 Research B

18、ackground&Recent Development at Home and Abroad11.2.1 Research Background11.2.2 Recent Development at Home and Abroad11.2.3 Brief Summary4 1.3 Subject Source and Research Significance41.3.1 Subject Source41.3.2 Research Significance41.4 Research Content and Technology Route51.4.1 Research Content51.

19、4.2 Technology Route52 Scheme of 3d Point Cloud Integration72.1 Foreword72.2 XJTUOM System7 2.2.1 Theory72.2.2 Compose of XJTUOM System72.2.3 Application Domain92.3 Step of Point Cloud Integration92.4 Point Cloud Integration System Design Scheme102.4.1 Design Principles of Point Cloud Integration Sy

20、stem102.4.2 Point Cloud Integration Scheme for XJTUOM System102.4.3 Point Cloud Integration Objective 11 2.5 Brief Summary113 Method of hold one layer among multi-overlap layers123.1 Foreword123.2 Theoretical Basis123.3 Technology Route123.4 Key Technologies Analysis133.4.1 Search Technology of Near

21、est Neighbors In 3D Space133.4.2 Removal of Overlaping Points in Non-Base Point Cloud153.5 Data Structure & Framework of Integration Software163.5.1 Data Structure Used in Integration Software163.5.2 Framework of Integration Software173.6 Brief Summary184 Method of Interpolation between Two Layers20

22、4.1 Foreword204.2 Theoretical Basis204.3 Technology Route214.4 Key Technologies Analysis224.4.1 Removal of Isolated Points224.4.2 Removal of Non-Grouped Overlaping Points in Non-Base Point Cloud244.4.3 Removal of Extremely Closing Points254.5 Framework of Integration Software264.6 Brief Summary265 M

23、ethod of Clustering285.1 Foreword285.2 Theoretical Basis285.2.1 Hierarchical Clustering Method295.2.2 Siplest Clustering Method295.2.3 Max Distance Clustring Method305.2.4 K-means Clustering Method305.2.5 Iterative Self-Organizing Data Analysis Technology Algorithm315.2.6 Clustering Method Used in I

24、ntegrationg Software335.3 Technology Route335.4 Ply Format345.5 Key Technologies Analysis365.5.1 Fast Triangulation of Point Cloud365.5.2 HalfEdge Data Structure375.5.3 Normal Vector and Weight Calculation of Point385.5.4 Weight of Point Cloud395.5.5 Decrease Weight of Edge Points405.5.6 Patiton of

25、Point Clouds Based on Boundary Box415.5.7 New Search Technology of Nearest Neighbors In 3D Space415.5.8 Integration of The Kth Point Cloud Block425.6 Framework of Integration Software435.7 Brief Summary436 Test-analysis and Application of Point Cloud Integration System446.1 Effects of Point Cloud In

26、tegration446.2 Speed of Point Cloud Integration496.3 Application of Point Cloud Integration System516.4 Brief Summary547 Conclusions and Suggestions557.1 Conclusions557.2 Suggestions56Acknowledgements57References58Declaration7 結論與展望1 緒論1.1 引言隨著現代工業制造水平的發展，產品零件大量采用不規則復雜曲面，其設計、生產、檢測、試驗等環節需要進行大量的三維曲面實體

27、數字化和三維快速檢測。其中三維快速檢測技術主要包括以下幾個步驟：數據采集、數據精確對齊、數據融合及點云與CAD數模比對分析。數據融合是指去除多幅點云重疊區域的冗余數據，獲得單層精確的點云模型。數據融合是三維快速檢測技術的一個難點。本章首先介紹了點云融合技術的研究背景、國內外研究狀況，然后闡述了本課題的來源和研究意義，最后說明了本文的主要研究內容和技術路線。1.2 研究背景及國內外發展狀況1.2.1 研究背景隨著計算機圖形學的發展，傳統的AutoCAD、3DMax、MAYA等建模工具已經逐漸不能勝任人們對復雜曲面物體的建模需要。非接觸式測量方法1-4應運而生。不同于傳統的檢測手段，光學三維快速檢

28、測系統5-7采用非接觸的測量方法，直接得到真實物體表面的采樣點，即點云數據。然后用點云數據和CAD模型進行比對8-10。這種方法不受曲面復雜度影響，表面采樣密度大，可以達到很高的檢測精度，因此光學三維快速檢測系統近年來得到迅速的發展。光學三維測量儀器單次掃描的幅面大小有限，而大型復雜型面如大型泡沫件、大型鑄件、大型水輪機葉片、大型模具、大型工件等的尺寸較大，單次測量只能得到物體一個側面的點云，必須進行多方位的尺寸測量。多次掃描得到的點云存在大量重疊區域，并不能直接用于和CAD模型進行比對。因此，需要對獲得的點云數據進行融合，從而得到單層的、精確的點云模型。1.2.2 國內外發展現狀點云融合技術

29、一直是點云預處理技術中的難點，對于這方面的研究，國外最早由一些著名的大學開始于上世紀八十年代末，九十年代初。目前比較典型的方法有：基于網格縫合的方法（Zippered Polygon Meshes from Range Images）、增量式網格化方法（Incremental Approaches）、基于空間容積的方法（Volumetric Approaches）、基于聚類的方法（Accurate integration of multi-viewrange images using k-means clustering）等。(1)基于網格縫合的方法G Turk&M Levoy11于1994年

30、提出Zippered Polygon Meshes from Range Images方法。該方法的主要思想為：首先把每幅點云三角化，然后把這些單幅的點云網格通過局部縫合的方法融合成為一幅點云。其算法組織如下：一首先網格化單幅點云：對于有柵格線信息的點云文件（*.ply）采用快速三角化的方法，即簡單的連接相鄰網格線上的頂點。對于沒有柵格信息的點云文件（*.asc），采用常規的德勞內三角化12-15的方法進行三角化（要比快速三角化的方法慢很多）。如圖 11 (a)所示。二.裁剪網格A中落在網格B邊界線內的部分，如圖 11 (b)所示，裁剪網格A中落入網格B的紅色邊界線內的部分。三.接下來連接網格

31、A中和網格B中在裁剪邊界線上相交的點，如圖 11 ( c)所示。四.對網格進行調整、優化，去除網格中的狹長三角形和小三角形, 如圖 11(d)所示。 (a)兩幅點云網格化 (b)裁剪網格A中落入B中紅色邊界線內的部分 (c)連接裁剪邊界線上的交點 (d) 網格經過調整優化圖 11網格縫合步驟(2)增量式網格化方法這種方法的特點是：通過網格化的過程去除多幅點云中的冗余點，把網格化的過程和去除冗余點的過程結合在一起，效率高。該方法中最典型的是滾球法（Ball-Pivoting）,由F Bernardini,J Mittleman, H Rushmeier,et al16提出。滾球法原理如圖 12所

32、示。該方法的算法組織如下：首先確定滾動球的半徑，并選定一個基準的三角形或邊界邊，如圖 12所示。其次滾動球沿邊界邊滾動，如果有三個點（其中包括滾動球所在邊上的兩個端點）落入滾動球內，那么把這三個點連接成一個新三角形。接著檢查這三個點的法向量是否一致，如果三個點之間的法向量的夾角均小于180度，那么認為他們是一致的，可以構成三角形，否則這三個點不可以構成三角行，應該去掉。最后一步是，更新邊界邊鏈表，讓滾動球沿著新邊繼續前面的步驟，直至所有的點被處理完成為止。圖 12滾球法基本原理圖(3)基于空間容積的方法該方法是由斯坦福大學的B Curless&M Levoy 17提出，該方法的算法思想很簡單：

33、給輸入的點云建立一個距離函數f(),該函數的返回值有正負兩種情況。其次用遍歷空間立體網格March Cubes18-20的方法抽取f=0的節點，最后用這些點構建點云曲面。March Cubes 方法的基本思想如下圖 13所示：主要分三步：首先建立空間網格；接著根據距離函數f確定所有點的符號，內部點定義為+1，外部點定義為-1；最后假設零值點位于內部點和外部點的交界線上，連接這些交界點，構成最終的曲面。(a)建立空間網格 (b)根據f確定內外點 (c)抽取f=0的點圖 13 March Cubes原理(4)聚類法該方法由YH Liu&H Zhou21提出。在其論文”Accurate integr

34、ation of multi-viewrange images using k-means clustering”中詳細論述了該方法的基本思想。主要步驟為：首先搜索兩幅點云的重疊區域。其次初始化聚類核中心，初始聚類核中心的確定是整個融合過程的關鍵，這一步處理好，那么點云融合時的收斂速度就會加快。最后就是迭代更新聚類核直到聚類核中心穩定下來，那么用穩定的聚類核中心代替重疊區域的點云。如下圖 14 (a)所示，兩幅點云，其中一幅為紅色的點云，另外一幅為藍色的點云，經聚類法融合以后形成黑色的穩定的初始聚類核中心，然后如圖 14 (b)所示，通過迭代更新聚類核中心，用最終形成穩定的黑色聚類核中心代替兩

35、幅點云中的重疊點（即紅點和藍點）。(a) 初始聚類核中心確定的過程(黑色點為聚類核中心)(b)聚類核中心的迭代過程(中間一層為最終穩定的聚類核中心)圖 14聚類融合原理1.2.3 國內外研究現狀總結目前已有的各種融合方法，應用于逆向設計均可取得良好的效果。但是應用于光學三維快速檢測中卻存在不少問題。首先，基于網格縫合的方法融合后表面相對于其它幾種方法比較粗糙，其次滾球法融合后對細節特征模糊的比較厲害，最后這幾種方法融合的速度都比較慢，對內存的消耗嚴重，不能滿足快速檢測的需求，為此本文對點云融合技術進行深入的研究。1.3 課題來源與研究意義1.3.1 課題來源(1) 本技術得到國家863項目 “

36、大型復雜曲面產品的反求和三維快速檢測系統研究”支持。(2) 江蘇省工業扶持項目“三維光學快速質量檢測系統”支持。(3) 對企業進行了深入的調研和需求分析，陜汽集團、西飛集團、四川德陽二重、河南奔馬集團、天津汽車模具有限公司等都對泡沫模型、模具、鑄件、工件等的高精度檢測有著極大的需求。(4) 本課題組和天津汽車模具有限公司是長期合作伙伴，本課題的研究成果應用于天津汽車模具有限公司泡沫實型的檢測、模具的表面檢測和制件的檢測，并由天津汽車模具有限公司反饋本技術存在的不足之處，及企業的實際需求，對該技術進行改進和完善。1.3.2 研究意義隨著現代工業制造水平的發展，產品零件大量采用不規則復雜曲面，其設

37、計、生產、檢測、試驗等環節需要進行大量的三維曲面實體數字化和三維測量，迫切需要快速、高效、準確、移動式的三維測量技術和反求逆向設計技術22-23。本文研究是針對光學三維檢測系統而提出的，對之進行研究具有重要意義：(1)目前，歐洲、美國、加拿大、澳大利亞、日本等國的幾十家高技術公司開展了對三維掃描技術的研究開發，已經形成了較大規模的產業。其產品在精度、速度、易操作性等方面都達到了較高的水平。反觀國內三維掃描技術的研究和應用情況不容樂觀。(2)本課題研究內容為國家863項目“大型復雜曲面產品的反求和三維快速檢測系統研究”組成部分。(3)本課題研究內容是江蘇省工業扶持項目“三維光學快速質量檢測系統”

38、的組成部分。(4)三維點云融合技術是光學三維快速檢測系統中不可或缺的一部分，如果沒有自動高效的三維點云融合技術，光學儀器獲得的點云將無法應用于快速檢測中。(5)三維點云融合技術極大地減少逆向設計中手動刪除重疊面的工作量，提高逆向設計的效率。1.4 研究內容和技術路線1.4.1 研究內容作者針對XJTUOM 三維光學快速檢測系統的點云融合技術，進行了大量的工作研究和實驗，主要內容如下：(1)總結當前已有點云融合技術，提出針對研究所自主研發的XJTUOM 三維光學快速檢測系統點云融合方案。(2)設計并實現了單面法融合點云數據的方法。實現了手動刪除點云重疊面進行點云數據融合的方法以及自動刪除多幅點云

39、重疊面融合點云數據的方法。(3)設計并實現了中點法融合點云數據的方法。首先去除每幅點云中的孤立點，其次搜索兩幅點云中的對應點對，為了加快搜索速度，本文采用KD-Tree空間鄰域搜索策略。最后用點對的中值代替點對中的兩個點，從而實現去除冗余點。(4)實現了聚類融合點云數據的方法，并對該方法進行了改進。首先提出了結構光掃描技術中點云權值計算的理論，實現了結構光掃描技術中點云權值的計算。其次對KD_Tree空間鄰域搜索方法進行了改進，實現了一種高效的空間點云搜索策略，有效提高了點云數據融合的速度。最后提出按包圍盒等間距分割點云數據的方法，分塊多次融合點云，解決了融合海量點云數據時內存不足的問題。(5

40、) 對點云融合方案進行試驗和分析。1.4.2 技術路線本文首先對光學三維快速檢測系統在國內的應用前景進行市場調研。深入企業，調查企業的需求。接著，提出了針對自主研發的光學三維面掃描檢測系統的點云融合方案。然后依次實現了單面法、中點法、聚類法點云融合算法，并對其進行了改進。最后進行了實驗和分析。對比了三種方法的優缺點，并將其應用于實際生產中。詳細的研究技術路線如圖 15所示。圖 15研究工作的技術路線圖2 點云融合方案2.1 引言三維光學面掃描系統的一大特點就是數據量龐大，因此三維點云融合方案必須滿足大數據量點云數據快速、準確和高效的融合需求。本文首先簡要介紹了XJTUOM三維光學面掃描系統，進

41、而闡述了針對XJTUOM三維光學面掃描系統的三維點云融合方案，并制定了三維點云融合目標。2.2 XJTUOM系統2.2.1 基本原理三維光學測量系統采用結構光非接觸式照相測量原理，如圖21所示，它結合結構光、相位測量、計算機視覺等技術于一體，通過光柵投影裝置投影數幅特定編碼的結構光到待測物體上，并由成一定夾角的兩個攝像頭同步采集相應圖像，然后對圖像進行解碼和相位計算，并利用匹配技術和三角形測量原理，計算出兩個攝像機公共視區內像素點的三維坐標，從而實現物體的三維信息數字化和測量。所謂照相測量，就是類似于照相機對視野內的物體進行照相，不同的是照相機攝取的是物體的二維圖像，而三維光學測量系統獲得的是

42、物體的三維信息。圖21 三維光學測量系統的基本原理圖2.2.2 系統組成硬件設備組成，如圖 22所示。(1)投影儀一個：采用多媒體投影儀，分辨率為；(2)數碼攝像頭二個：使用工業級數字攝像頭，該攝像頭在分辨率下的最大輸出可以達到7.5幀，而且提供二次開發SDK可以很方便的對其進行編程控制；(3)組合平臺一個：包括投影儀底座，相機萬向頭，連接桿，三腳架等；(4)高性能計算機一臺：通過控制投影儀、數碼攝像頭來完成整個掃描過程，以及對掃描數據進行處理。圖 22 XJTUOM密集點云采集系統軟件系統組成：(1)密集點云采集軟件。軟件界面如圖 23所示。圖 23 XJTUOM密集點云采集系統界面(2)點

43、云預處理軟件。軟件界面如圖 24所示。圖 24 XJTUOM點云預處理軟件界面2.2.3 應用領域產品檢測：生產線產品質量控制和形位尺寸檢測、特別適合復雜曲面的檢測，可以檢測鑄件、鍛件、沖壓件、模具、注塑件、木制品等產品。本文開發的系統已應用與天津汽車模具廠等合作單位。逆向設計：快速獲取零件的表面點云數據，建立三維點云數模，達到快速設計產品的目的。其它應用：文物掃描和牙齒畸形矯正、整容等。2.3 點云融合所處環節應用光學三維快速檢測系統掃描點云時，不可避免的要從多個角度和方位獲取點云數據。獲取得到的點云數據首先需要進行坐標變換，統一在一個世界坐標系下，其次去除融合的重合點云得到單層的、完整的點

44、云模型，最后用這個點云模型進行逆向建模設計或與CAD數模進行檢測比對，點云融合在測量流程中所處環節如圖 25所示。圖 25點云融合在測量流程中所處環節2.4 點云融合方案的確定2.4.1 點云融合系統設計原則該系統面向對象為企業橫向課題和國家863項目部分，具有較強的實際應用需求，在系統設計時應遵循以下原則：(1) 具備處理大數據量的能力：一般情況下，單次掃描獲取得到的點云有上千萬個點，軟件系統需要能同時處理大數據量的點云。(2) 具有快速的處理速度：逆向設計對點云融合的實時性要求較低，但檢測對點云融合的實時性要求較高。(3) 高精度的處理結果：融合后不降低點云數據的精度。(4) 較好的系統穩

45、定性。2.4.2 針對光學三維測量系統的點云融合方案為了快速得到高精度、單層的點云模型，本文制定了點云融合的方案：如圖 26所示，首先去除單幅點云中的孤立點，標識點云的邊界點，并計算點云的權值，其次計算點云中每個點的法向量(用于后期的精確融合)，接著用最近鄰域搜索策略判斷出重疊的區域，最后采用點云融合算法融合重疊的區域。圖 26點云融合方案2.4.3 點云融合目標制定(1)首先能快速的初始化點云：包括去除孤立點、計算法向量、計算點云權值等。(2)快速的判斷多幅點云的重疊區域。(3)融合重疊區域。(4)最終獲得高質量的能夠用于檢測和逆向建模設計的點云模型。2.5 本章小結本章主要介紹了XJTUO

46、M三維光學面掃描系統的組成和應用領域，對本文所設計到的點云融合技術的方案進行了分析，并根據點云融合系統的設計原則提出了針對XJTUOM三維光學面掃描系統點云融合方案。3 單面法3.1 引言由于本文針對在線檢測的點云融合問題，前面所討論的已有的各種比較成熟的方法，就都不能適用，最大的瓶頸是處理速度。在線檢測要求在保證精度的前提下，檢測速度非常快，在幾分鐘至多十幾分鐘內處理得到結果，為此本文根據實際情況提出單面法融合點云數據的方法，并將其應用到實際的工程實踐中，下面對單面法的基本原理進行分析。3.2 單面法理論基礎單面法基本原理如下：如果兩幅點云有重疊區域，那么在重疊的區域以其中一幅點云為基準刪除

47、與其重疊的另一幅點云中的重疊點，從而得到單層的點云。判斷另一幅點云中每個點是否為重疊點的方法為：以基準點云中的點為中心，給定上下偏差帶 ，那么另一幅點云中落在偏差帶內的點定義為重疊點。如圖 31所示：以點云1為中心，給定誤差帶寬：，那么點云2處在點云1誤差帶內的點被剔除掉，從而形成單層點云。圖 31單面法的原理圖3.3 單面法技術路線對于需要進行融合處理的多幅點云，首先按點云包圍盒進行排序，使相鄰的兩幅點云有重疊的區域，從而提高融合的效率。其次取其中的第一幅為目標點云，其余各幅依次融合至該幅點云中。如圖 32所示，第j幅點云和第i幅點云融合時，首先搜索兩幅點云的重疊區域，在搜索的過程中，本文使

48、用kd樹鄰域搜索的策略。這個階段也是整個融合過程中最耗時的步驟。接下來進行重疊區域的融合，本文采用保留第i幅點云中的重疊區域，而去除第j幅點云中的重疊區域的辦法。刪除完j幅點云中的重疊點，下一步就是把兩幅點云中的點合并為一幅點云，具體是把點云j合并至點云i中。最后重復上述步驟直至所有點云處理完成為止。圖 32單面法技術路線圖3.4 單面法關鍵技術由圖 32中的技術路線可知，單面法融合點云的關鍵技術為搜索重疊區域和刪除非基準點云中的重疊點。3.4.1 三維空間鄰域搜索技術目前常用的空間搜索算法主要有八叉樹24-25、空間單元格26-27和KD_Tree28法。其中KD-Tree是由Bentley

49、于1975年提出來并發展成為一種多維空間樹狀搜索索引結構，它特別適合空間點的搜索，具有快速查找鄰近的特性，其典型應用是求點的K個最近點，本文就是采用這種結構來組織三維數據點的。下面將詳細介紹KD-Tree的生成過程。KD-Tree是一個針對K維度空間所設計的二元搜索樹，其本質是一個二叉樹。對于一個K維度的歐氏空間，被一個正交于任意一個K維坐標軸的超平面（K-1維）遞歸分割為兩個子空間，直到每個子空間所包含的數據個數不超過給定的值為止，且每個子空間中至少包含一個數據。對于一個包含離散點的二維空間來說，如圖 33，KD-Tree的生成過程就是平面被X軸和Y軸連續遞歸劃分的過程，平面的劃分深度就是K

50、D-Tree的深度，若用d表示，則KD-Tree上節點的總數為2d或2d-1。假設水平方向為X軸，豎直方向為Y軸，則具體的劃分過程如下：首先按X軸尋找分割線，即計算所有點x值的平均值，以此平均值將平面分成兩部分；然后在分成的子平面中按y值劃分，分割好的子平面再按x值分割，依此類推，直到最后分割的區域內只有一個點。這樣的分割過程就對應了一個二叉樹，二叉樹的分支節點對應一條分割線，而每個葉子節點就對應一個數據點。 (a) KD-Tree法劃分二維平面 (b) 離散點的二叉樹存儲圖 33 KD-Tree法劃分二維平面及離散點的二叉樹存儲由上面的介紹，可以得出KD-Tree的三個特點：第一，每個節點代

51、表一個矩形區域；第二，每個節點對應一個坐標軸上的劃分，它的子節點就對應著這個劃分；第三，節點所對應的分割線與深度對應。此外，KD-Tree還具有點分布均勻的特點，所以搜索的效率比較高。KD-Tree的一個典型應用就是查詢空間中距離一個輸入點最近的一點29。這里采用一種回溯的算法來搜索最近兩點，對于一個輸入頂點P，首先找到P所在的區域，然后計算與P所相鄰區域內所有點的最小距離，然后用這個最小距離和P到當前分割線的距離進行比較，如果最小距離小于等于P到分割線的距離則搜索結束；如果最小距離大于P到分割線的距離，則說明距離P最近的點有可能存在于分割線的另一側區域，向分割線的另一側回溯直到找到的最小距離

52、小于P到當前分割線的距離。在KD-Tree建立之后，某點的K鄰域搜索就成了基于KD-Tree劃分的二叉樹搜索問題了。通過空間劃分的方法使K鄰近點的搜索都從樹的底層開始，也就是空間的小區域開始，然后逐漸再向樹的上層大空間區域搜索，從而達到提高搜索速度的效果。因為大部分最近點的搜索都在樹的底層完成，所以運用KD-Tree查找兩片點云之間最近點的時間復雜度大約是，在大數據量的情況下，比原始搜索算法的快的多。因此，運用KD-Tree這種數據結構可以在很大程度上提高空間搜索效率。下面給出KD-Tree的部分c+代碼：class Ckd_tree public:struct Box_Range float

53、 lo3; float hi3;Ckd_tree();virtual Ckd_tree();Ckd_tree(kdarray pa,int n,int dd,int bs=10); void Search(kdcoord q,int k,kdindx nn_indx,kdcoord dd,double eps);private: int dim;int n_pts;kdarray pts; kdindx pidx;Ckd_node *root; Box_Range bnd_box; void Initkd_tree(int n,int dd,int bs);void BoxRange(kdar

54、ray pa,kdindx pidx,int n,int dd);float MaxDistance(kdarray pa,kdindx pidx,int n,int d);float BoxDistance(const kdcoord p,const Box_Range bnd_box,int dim);void GetMinMaxVal(kdarray pa,kdindx pidx, int n,int cut_dim,float &min, float &max);Ckd_node *Creatkd_tree(kdarray pa,kdindx pidx, int n,int dim, int bsp,Box_Range bnd_box);void GetSplitNum(kdarray pa,kdindx pidx,int n,int cut_dim,float cut_val,int &num1,int &num2);void Split(kdarray pa,kdindx pdix,int n,int dim,int &cut_dim,float &cut_val,int &n_lo, Box_Range &bnd_box);3.4.2 去除非基準點云中的重疊點兩幅點云pt1和pt2，我們以其中比較大的一幅點云（點云個數較多的點云）為基準點云（pt1），另外一幅點