碩士學(xué)位論文光學(xué)三維快速檢測系統(tǒng)中的點云融合技術(shù)研究與應(yīng)用POINTCLOUDINTEGRATIONIN3DFASTMEASURINGSYSTEM學(xué)科專業(yè)機械制造及其自動化2009年01月論文題目光學(xué)三維快速檢測系統(tǒng)中的點云融合技術(shù)研究與應(yīng)用學(xué)科專業(yè)機械制造及其自動化摘要針對現(xiàn)有點云融合方法融合數(shù)據(jù)速度慢、占用內(nèi)存大、不能適用于光學(xué)三維快速檢測的問題，在深入研究國內(nèi)外已有點云融合理論的基礎(chǔ)上，結(jié)合面結(jié)構(gòu)光掃描技術(shù)的特點以及快速檢測的工程實際需求，本文對光學(xué)三維快速檢測中的點云融合技術(shù)進行深入研究。主要內(nèi)容和成果如下1設(shè)計并實現(xiàn)了針對光學(xué)三維快速檢測系統(tǒng)的點云融合方案，即首先對點云進行預(yù)處理去除孤立點、計算法向量、計算點云權(quán)值、減小邊界點權(quán)值、精簡數(shù)據(jù)等。然后融合多層點云數(shù)據(jù)，獲得單層完整的點云數(shù)據(jù)，用于比對檢測或逆向設(shè)計。2設(shè)計并實現(xiàn)了單面法融合點云數(shù)據(jù)的方法。首先確定基準點云，然后根據(jù)給定的誤差帶確定并去除非基準點云中的重疊點，最后將不包含重疊點的多幅點云合并為單層的一幅點云。該方法的優(yōu)點是效率高，可以很好的應(yīng)用于快速檢測中，但該方法融合后的表面光滑度不好，不能很好的應(yīng)用于逆向設(shè)計中。3設(shè)計并實現(xiàn)了中點法融合點云數(shù)據(jù)的方法。首先去除每幅點云中的孤立點，其次搜索兩幅點云中的對應(yīng)點對，為了加快搜索速度，本文采用KDTREE空間鄰域搜索策略。最后用點對的中值代替點對中的兩個點，從而實現(xiàn)去除冗余點。該方法相對于單面法表面光滑度有所改善，但融合效率比單面法慢。4實現(xiàn)了聚類法融合點云數(shù)據(jù)的方法，并對該方法進行了改進首先提出了結(jié)構(gòu)光掃描技術(shù)中點云權(quán)值計算的理論，實現(xiàn)了結(jié)構(gòu)光掃描技術(shù)中點云權(quán)值的計算；其次對KD_TREE空間鄰域搜索方法進行了改進，實現(xiàn)了一種高效的空間近鄰點云搜索策略，有效提高了點云數(shù)據(jù)融合的速度；最后提出按包圍盒等間距分割點云數(shù)據(jù)的方法，分塊多次融合點云，解決了融合海量點云數(shù)據(jù)時內(nèi)存不足的問題。該方法融合效率比單面法低但比中點法高，融合后表面光滑，可以很好的應(yīng)用于快速檢測和逆向設(shè)計中。經(jīng)過試驗、分析及工程應(yīng)用，結(jié)果表明本文提出的方法在保證點云數(shù)據(jù)融合精度的同時，提高了點云融合的效率，滿足了三維快速檢測的工程實際需求，效果良好。關(guān)鍵詞光學(xué)三維快速檢測；點云融合；單面法；中點法；改進的聚類法；論文類型應(yīng)用研究TITLEPOINTCLOUDINTEGRATIONIN3DFASTMEASURINGSYSTEMSPECIALITYMECHANICALENGINEERINGAPPLICANTBAOQUANSHISUPERVISORVICEPROFLIANGJINABSTRACTTHEPOINTCLOUDINTEGRATIONTECHNIQUEOF3DOPTICALRAPIDDETECTIONISINDEPTHSTUDIEDINTHEPAPER,BASEDONTHETHEORYOFPOINTCLOUDINTEGRATIONATHOMEANDABROADHAVEBEENRESEARCHEDINDEPTH,FORTHEEXISTINGPOINTCLOUDINTEGRATIONMETHODSWITHSLOWEFFICIENCY,TAKEMUCHMEMORY,CANNOTBEAPPLIEDTO3DOPTICALRAPIDDETECTIONTHESURFACESTRUCTUREOPTICALSCANTECHNIQUEANDTHENEEDSOFRAPIDDETECTIONPROJECTARECOMBINATEDTOCONSIDEREDTHEMAINCONTENTSANDACHIEVEMENTSARELISTEDASFOLLOWS1THEPOINTCLOUDINTEGRATIONPROGRAMFOR3DOPTICALRAPIDDETECTIONSYSTEMISDESIGNEDANDIMPLEMENTEDTHATIS,ATFIRST,EXECUTETHEPOINTCLOUDPREPROCESSING,REMOVETHEISOLATION,CALCULATETHEVECTORANDVALUEOFPOINTS,DECREASETHEWEIGHTOFTHEBORDER,SAMPLINGTHEDATA,ANDTHENINTEGRATEPOINTCLOUDDATA,REMOVEREDUNDANTPOINTSATLASTCONTRASTTHEPOINTCLOUDDATAANDCADMODEL2THEMETHODOFHOLDONELAYERAMONGMULTIOVERLAPLAYERSISREALIZEDFINDTHEBASEPOINTCLOUDFIRSTLYTHENACCORDINGTOTHEERRORBAND,DELETETHEOVERLAPPOINTSINNONBASEPOINTCLOUDATLASTALLPOINTCLOUDSAREMERGEDTOGETHERTOBEONESINGLELAYERPOINTCLOUDTHISMETHODHAVEAHIGHINTEGRATIONSPEED,HOWEVERTHEINTEGRATEDSURFACEISROUGH3THEMETHODOFINTERPOLATIONBETWEENTWOLAYERSISREALIZEDFIRSTOFALL,REMOVEEACHISOLATEDPOINT,SEARCHTHECORRESPONDINGPOINTSINTWOPOINTCLOUDS,USINGKDTREESPACENEIGHBORHOODSEARCHSTRATEGYTOSPEEDUPTHESEARCHEFFICIENCY,TAKETHEMEDIANOFCORRESPONDINGPOINTSINSTEADOFTHEMTOREMOVEPOINTSREDUNDANCYCOMPAREDWITHTHEMETHODOFHOLDONELAYERAMONGMULTIOVERLAPLAYERS,THISMETHODISSMOOTHERININTEGRATIONSURFACE,BUTLOWERININTEGRATIONSPEED4THECLUSTERINGINTEGRATIONMETHODISREALIZEDANDIMPROVEDATFIRST,THETHEORYOFTHERINGHTSOFPOINTSINSTRUCTUREOPTICALSCANTECHNIQUEISPUTFORWARD,ANDCALCULATETHERINGHTSOFPOINTSTHENTHEKD_TREESEARCHMETHODISIMPROVEDANDACHIEVEAHIGHLYEFFICIENTSPACENEIGHBORSSEARCHSTRATEGIESTOINCREASETHESPEEDOFPOINTCLOUDINTEGRATIONFINALLY,DIVIDETHERESEARCHISFUNDEDBYNATIONAL863PLAN（2007AA04Z124）J1搜索重疊區(qū)域SEARCHOVERLAPAREA（I,J）刪除第J幅點云上的重疊區(qū)域DELETEOVERLAPAREAJ合并兩幅點云至I中MERGEI,JJN1結(jié)束NOYESJ多幅點云N圖32單面法技術(shù)路線圖34單面法關(guān)鍵技術(shù)由圖32中的技術(shù)路線可知，單面法融合點云的關(guān)鍵技術(shù)為搜索重疊區(qū)域和刪除非基準點云中的重疊點。341三維空間鄰域搜索技術(shù)目前常用的空間搜索算法主要有八叉樹2425、空間單元格2627和KD_TREE28法。其中KDTREE是由BENTLEY于1975年提出來并發(fā)展成為一種多維空間樹狀搜索索引結(jié)構(gòu)，它特別適合空間點的搜索，具有快速查找鄰近的特性，其典型應(yīng)用是求點的K個最近點，本文就是采用這種結(jié)構(gòu)來組織三維數(shù)據(jù)點的。下面將詳細介紹KDTREE的生成過程。KDTREE是一個針對K維度空間所設(shè)計的二元搜索樹，其本質(zhì)是一個二叉樹。對于一個K維度的歐氏空間，被一個正交于任意一個K維坐標軸的超平面（K1維）遞歸分割為兩個子空間，直到每個子空間所包含的數(shù)據(jù)個數(shù)不超過給定的值為止，且每個子空間中至少包含一個數(shù)據(jù)。對于一個包含離散點的二維空間來說，如圖33，KDTREE的生成過程就是平面被X軸和Y軸連續(xù)遞歸劃分的過程，平面的劃分深度就是KDTREE的深度，若用D表示，則KDTREE上節(jié)點的總數(shù)為2D或2D1。假設(shè)水平方向為X軸，豎直方向為Y軸，則具體的劃分過程如下首先按X軸尋找分割線，即計算所有點X值的平均值，以此平均值將平面分成兩部分；然后在分成的子平面中按Y值劃分，分割好的子平面再按X值分割，依此類推，直到最后分割的區(qū)域內(nèi)只有一個點。這樣的分割過程就對應(yīng)了一個二叉樹，二叉樹的分支節(jié)點對應(yīng)一條分割線，而每個葉子節(jié)點就對應(yīng)一個數(shù)據(jù)點。AKDTREE法劃分二維平面B離散點的二叉樹存儲圖33KDTREE法劃分二維平面及離散點的二叉樹存儲由上面的介紹，可以得出KDTREE的三個特點第一，每個節(jié)點代表一個矩形區(qū)域；第二，每個節(jié)點對應(yīng)一個坐標軸上的劃分，它的子節(jié)點就對應(yīng)著這個劃分；第三，節(jié)點所對應(yīng)的分割線與深度對應(yīng)。此外，KDTREE還具有點分布均勻的特點，所以搜索的效率比較高。KDTREE的一個典型應(yīng)用就是查詢空間中距離一個輸入點最近的一點29。這里采用一種回溯的算法來搜索最近兩點，對于一個輸入頂點P，首先找到P所在的區(qū)域，然后計算與P所相鄰區(qū)域內(nèi)所有點的最小距離，然后用這個最小距離和P到當前分割線的距離進行比較，如果最小距離小于等于P到分割線的距離則搜索結(jié)束；如果最小距離大于P到分割線的距離，則說明距離P最近的點有可能存在于分割線的另一側(cè)區(qū)域，向分割線的另一側(cè)回溯直到找到的最小距離小于P到當前分割線的距離。在KDTREE建立之后，某點的K鄰域搜索就成了基于KDTREE劃分的二叉樹搜索問題了。通過空間劃分的方法使K鄰近點的搜索都從樹的底層開始，也就是空間的小區(qū)域開始，然后逐漸再向樹的上層大空間區(qū)域搜索，從而達到提高搜索速度的效果。因為大部分最近點的搜索都在樹的底層完成，所以運用KDTREE查找兩片點云之間最近點的時間復(fù)雜度大約是，在大數(shù)據(jù)量的情況下，比原始搜索算法的LOGPQN快的多。因此，運用KDTREE這種數(shù)據(jù)結(jié)構(gòu)可以在很大程度上提高空間搜PQN索效率。下面給出KDTREE的部分C代碼CLASSCKD_TREEPUBLICSTRUCTBOX_RANGEFLOATLO3FLOATHI3CKD_TREEVIRTUALCKD_TREECKD_TREEKDARRAYPA,INTN,INTDD,INTBS10VOIDSEARCHKDCOORDQ,INTK,KDINDXNN_INDX,KDCOORDDD,DOUBLEEPSPRIVATEINTDIMINTN_PTSKDARRAYPTSKDINDXPIDXCKD_NODEROOTBOX_RANGEBND_BOXVOIDINITKD_TREEINTN,INTDD,INTBSVOIDBOXRANGEKDARRAYPA,KDINDXPIDX,INTN,INTDDFLOATMAXDISTANCEKDARRAYPA,KDINDXPIDX,INTN,INTDFLOATBOXDISTANCECONSTKDCOORDP,CONSTBOX_RANGEBND_BOX,INTDIMVOIDGETMINMAXVALKDARRAYPA,KDINDXPIDX,INTN,INTCUT_DIM,FLOATCKD_NODECREATKD_TREEKDARRAYPA,KDINDXPIDX,INTN,INTDIM,INTBSP,BOX_RANGEBND_BOXVOIDGETSPLITNUMKDARRAYPA,KDINDXPIDX,INTN,INTCUT_DIM,FLOATCUT_VAL,INTVOIDSPLITKDARRAYPA,KDINDXPDIX,INTN,INTDIM,INT342去除非基準點云中的重疊點兩幅點云PT1和PT2，我們以其中比較大的一幅點云（點云個數(shù)較多的點云）為基準點云（PT1），另外一幅點云為待融合點云（PT2）。那么通過建立KDTREE樹，進行鄰域搜索確定重疊點BUILD_KDTREEPTS2FOREACHPOINTINPTS11NODEIPTSSEARCHNEARESTPOINTNODEI當獲得基準點云重疊區(qū)域的最近點后，就可以根據(jù)搜索半徑（R）判斷是否是重疊點，如公式（31）所示。31,TRUEIFNARESTDIRNODEILTFLS去除非基準點云中的重疊點的部分代碼如下SEARCH_NEAREST_NEIGHBOR04,4,GPOINTA0,GPOINTA1IFCMPGPOINTA0LEN,GPOINTA1LENFORI0IN1結(jié)束YESJ圖42中點法技術(shù)路線圖44中點法關(guān)鍵技術(shù)由圖43中點法的技術(shù)路線可知，中點法的關(guān)鍵技術(shù)為去除孤立點、搜索重疊區(qū)域、計算中值、去除非基準點云中未被計算的重疊點、去除密集點。搜索重疊區(qū)域的技術(shù)在前面的章節(jié)中討論過了，在此不再論述。中值計算方法也在本章的42節(jié)中論述過，也不再分析。441去除孤立點單幅點云中的孤立點定義為與其最近點的歐氏距離41遠遠大于掃描間隔的那些點。造成孤立點的原因，如圖43，主要是因為被掃描面的法向與掃描方向的夾角較大，造成掃描間距較大。這些點的可信度較低，偏離真實值的程度遠遠大于其它點。（A）掃描方向和側(cè)面法向夾角較大（B）掃描后點云側(cè)面圖43孤立點產(chǎn)生的原因為了剔除孤立點對最終融合效果的影響，在融合前，本文首先去掉點云中的這些孤立點，如圖44所示在點云預(yù)處理軟件中用紅色的圈畫出來的部分是去除孤立點的參數(shù)設(shè)置，給定閥值，判斷出孤立點。去除孤立點的部分代碼VOIDCPOINTSMODELDELETESINGLEPOINT_POINTPT,INTK_NEIGHBOR,FLOATVAL,FLOATKEYVALUEINTISEARCH_NEAREST_NEIGHBORPT,K_NEIGHBOR,VALFORI0ILENIIFPTPOINTNODEIK_NEAREST_DISTANCENULLCONTINUEELSEIFPTPOINTNODEIK_NEAREST_DISTANCE0KEYVALUEPTPOINTNODEISELECTEDTRUE圖44去除孤立點442去除非基準點云中的無對應(yīng)點的重疊點造成無對應(yīng)點的重疊點的原因主要有三個，下面逐一分析。首先使用面結(jié)構(gòu)光掃描儀器掃描點云時，掃描柵格線不均勻，其橫坐標軸的掃描間隔和縱坐標軸的掃描間隔不相同。如圖45，兩幅點云重疊時，柵格線互相交叉，造成第I幅點云上的某幾個點可能同時對應(yīng)于第J幅點云上的同一個點。由圖45可以得出，兩幅點云I和J上的點的對應(yīng)關(guān)系并不是一一對應(yīng)，有可能是一對多，或多對一，這樣造成中值計算的非對應(yīng)性。比如第I幅點云中的點1同時對應(yīng)第J幅點云中的點2和點3，那么在計算中值時只計算點1和其最近的一個點2的中值，而點3則未參與運算。圖45兩幅點云中的最近點對對于上述情況，如果保留點3的話，那么會造成最終的表面更加粗糙，如圖46（A）所示，所以采取直接去除點3的辦法，最后形成圖46（B）所示的結(jié)果。用灰色的點代表新計算得到的點，綠色代表目標點上的非重疊點。圖中只畫了第I幅點云中的第一條掃描線上的點云融合后的情況?？梢钥闯?，如果不去除點3的話，表面會變的像波浪形一樣，不平滑。圖46用中值代替原始點第二種情況，用光學(xué)掃描儀器掃描點云時，有漏掃的點云，從而造成最近點對對應(yīng)錯誤的問題，掃描點云時點云有漏洞的情況如圖47所示點1用紫色的圓圈標記出來，為漏掃的點，從而造成點2，點3屬于重疊點，但不能參與運算。圖47漏掃點云時最近點對匹配錯誤情況最后一種情況，當點云融合一次后，點距就極其不規(guī)則，從而造成最近點對一對多和多對一的情況。443去除密集點密集點產(chǎn)生的原因主要是因為在計算中值的時候有多對一的情況如圖48所示。點1和點2同時對應(yīng)點3，那么融合后的點1和點2就會靠近很多，如圖中的灰色點，這樣經(jīng)過多次融合以后就可能造成兩個點的坐標相同。為此需要去除太靠近的點對。為了避免出現(xiàn)上述情況，我們采用去除密集點的方法。去除密集點的方法有兩種第一種，給定一個較小的閥值KJHXR7）LJHKRJXH（58）KD樹加點云空間包圍盒判斷的搜索方法基本思想如下KD樹的鄰域搜索包括兩個階段第一個階段是建樹即將點云壓入二叉樹結(jié)構(gòu)中，這個過程相比第二個階段，要快的多，一般以MS為單位，所以對第一個階段我們就采用常規(guī)KD建樹的策略；第二個階段是點云搜索階段，這個階段最消耗時間，其時間復(fù)雜度為NLOGN，所以本文對這個階段進行改進。對于兩幅沒有重疊區(qū)域的點云，我們只要判斷其包圍盒是否相交就可以了，如果包圍盒不相交，那么直接返回。對于有部分區(qū)域重疊的兩幅點云，我們以壓入KD樹的點云的包圍盒為基準，那么另一幅點云中未落入該包圍盒的點不參與運算，這樣相當于減少了點云的個數(shù)即減小了N。當掃描的實物比較大的時候，使用該方法可以顯著提高點云的融合速度。KDTREE空間鄰域搜索算法建樹（點云PT1，包含N1個點）所需的時間為N1LOGN1。那么（點云PT2）N2個點搜索鄰近點需要的總時間為N2N1LONGN1。令兩幅點云的包圍盒分別為BBOX1和BBOX2，PT1中的點落在BBOX2內(nèi)的點個數(shù)記為121MINSIDEBBOXPTI，I1,2,N1；PT2中的點落在BBOX1內(nèi)的點個數(shù)記為2J，J1,2,N2；那么在建樹的過程中只把M1個點壓入KD樹，而PT2在搜索的過程中只對M2個點進行搜索，其余的點不參與運算。這時整個搜索算法的時間為M2M1LONGM1，對于兩幅重疊部分較少的點云（M1N1，M2N2,M2M1LONGM1N2N1LONGN1）可以極大的減小搜索時間。而實際的點云數(shù)據(jù)重疊的部分往往比較少，所以該方法能有效提高點云處理的速度。558融合第K塊點云聚類法融合點云數(shù)據(jù)依據(jù)聚類的原理，把三維空間點按照其法向量和空間歐式距離的相似性聚在不同的聚類核內(nèi)，然后迭代聚類核直至穩(wěn)定，最后用穩(wěn)定的聚類核中心代替那些核內(nèi)的點。該算法的目的在于最小化所有的數(shù)據(jù)點與其相關(guān)聚類核之間的差異，最終得到目標函數(shù)公式（59），其中是點與其所歸屬的聚類核2JIJXCJIX中心的距離。這個距離反映了該數(shù)據(jù)點與核中心的相似程度。為了評估融合后的表JC面與原始各幅點云表面之間的非相似性，目標函數(shù)J可以改進為公式（510）的形式，其中，J就代表了在原始各幅點云表面上的N個相關(guān)點與融合面上的對2IJJORNEWP應(yīng)點的非相似性。聚類法的目的就是使目標函數(shù)最小化。（521KNJIJJIJXC9）（521IJKNJORNEWJIJP10）56軟件框架聚類法的實驗平臺建立在單面法和中點法的基礎(chǔ)上，并進行了改進，由于有了法向量，點云中的點可以真彩色顯示。這時點云處理的軟件上升為V62版本，基本界面如圖511所示，軟件具有的功能為全局匹配、聚類法刪除點云重疊面、平滑降噪、去除局外點、測量點距、顯示單個點坐標等功能。圖511點云預(yù)處理軟件V6257本章小結(jié)本章主要介紹了聚類法的基本原理、改進聚類法的技術(shù)路線、改進聚類法的關(guān)鍵技術(shù)。改進的聚類算法解決了面結(jié)構(gòu)光掃描測量中點云權(quán)值計算的問題，提高了點云融合的速度，減小了融合過程中內(nèi)存的占用，具有融合速度快、融合精度高、可處理大數(shù)據(jù)量點云的特點?？梢詽M足逆向設(shè)計及三維快速測量系統(tǒng)的需求。EQUATIONCHAPTERNEXTSECTION16點云融合系統(tǒng)的實驗分析及應(yīng)用本文提出的算法用VC60在西安交通大學(xué)信息機電研究所自主開發(fā)的XJTUOM點云預(yù)處理軟件中實現(xiàn)，并在實際的三維快速測量中得到應(yīng)用，取得良好的效果。本文實驗用計算機處理器配置均為AMD642X4400，2G內(nèi)存。用到的點云均由XJTUOM三維光學(xué)密集點云采集系統(tǒng)掃描獲得。本章從五個方面對三種點云融合方法進行實驗分析融合的效果，融合的效率，融合算法的時間復(fù)雜度，融合算法的空間復(fù)雜度，融合精度。61點云融合的效果圖61圖65為用單面法、中點法、改進的聚類算法融合表61中某人頭模型數(shù)據(jù)、某花瓶數(shù)據(jù)、某航空葉輪數(shù)據(jù)、某車門數(shù)據(jù)和某翼虎點云數(shù)據(jù)的過程。其中每組數(shù)據(jù)中的A、D、G為單面法、中點法、改進聚類法融合后的點云數(shù)據(jù)，改進的聚類法在顯示的時候使用了真彩色顯示。每組數(shù)據(jù)中的B、E、H為融合后的數(shù)據(jù)三角化的結(jié)果，這組數(shù)據(jù)主要是為了比較融合后模型的表面光滑程度。每組數(shù)據(jù)中的C、F、I為局部放大圖，為了更清晰的比較三種方法融合后的表面。由實驗結(jié)果可以得出以下結(jié)論1單面法融合的最終效果很大程度的依賴于點云的匹配精度，如果匹配的精度足夠高，融合后的光滑程度越高，那么單面法可以用于逆向設(shè)計中。如果匹配精度不高，那么在多幅點云的交界處有明顯的棱存在，整個模型不光滑，融合以后的模型不能很好的應(yīng)用于逆向設(shè)計中。2中點法在多幅點云的交界處，對融合結(jié)果有所改進，棱的高度變?yōu)樵瓉淼囊话?。但沒有徹底消除棱。融合后的表面的粗糙度增大，這個主要是因為經(jīng)過運算后，有可能把噪聲疊加在一起，所以在融合表面會出現(xiàn)波浪形的凸起。3改進的聚類算法克服了單面法和中點法的不足，融合后消除了邊界交界處的棱，并且保持融合表面的光滑性?？梢詽M足逆向設(shè)計的要求。A單面法融合后B單面法融合后三角化C左眼局部放大（D）中點法融合后（E）中點法融合后三角化（F）左眼局部放大（G）改進聚類法融合后（H）改進聚類法融合后三角化（I）左眼局部放大圖61某人頭模型用三種方法融合后效果A單面法融合后B單面法融合后三角化C凸緣局部放大（D）中點法融合后（E）中點法融合后三角化（F）凸緣局部放大（G）改進聚類法融合后（H）改進聚類法融合后三角化（I）凸緣局部放大圖62某花瓶模型用三種方法融合后效果A單面法融合后B單面法融合后三角化C凸緣局部放大（D）中點法融合后（E）中點法融合后三角化（F）凸緣局部放大（G）改進聚類法融合后（H）改進聚類法融合后三角化（I）凸緣局部放大圖63某葉輪模型用三種方法融合后效果A單面法融合后B單面法融合后三角化C車窗局部放大（D）中點法融合后（E）中點法融合后三角化（F）凸緣局部放大圖（G）改進聚類法融合后（H）改進聚類法融合后三角化I）車窗局部放大圖64某車門模型用三種方法融合后效果A單面法融合后B單面法融合后三角化C虎身局部放大（D）中點法融合后（E）中點法融合后三角化（F）虎身局部放大（G）改進聚類法融合后（H）改進聚類法融合后三角化（I）虎身局部放大圖65某翼虎模型用三種方法融合后效果62點云融合速率分析對某人頭點云數(shù)據(jù)、某花瓶數(shù)據(jù)、某航空葉輪數(shù)據(jù)、某車門數(shù)據(jù)和某翼虎點云數(shù)據(jù)在相同的計算機配置下進行融合，融合速率如表61及圖66所示。由表61和圖66可以得出，單面法的融合速度遠遠高于中點法及改進的聚類法，一般為它們兩者的35倍，所以單面法為所有點云融合方法中效率最高的，最適用于三維快速檢測。由于增加了孤立點的去除以及密集點的去除，中點法融合的效率低于單面法和改進的聚類算法的效率。表61單面法、中點法和改進聚類法的融合效率圖的編號點云幅數(shù)點云數(shù)目/個單面法融合所需時間/秒中點法融合所需時間/秒改進聚類法所需時間/秒圖615231309283340圖6212635762344231104圖6319139337186135圖6482276392239471圖65817025168653105010015020025013933711702516227639223130926357623點云數(shù)目/個融合所需的時間/秒單面法中點法改進聚類法圖66單面法、中點法及聚類法融合效率表62及圖67為原始聚類算法21和改進的聚類算法在融合效率方面的比對。由表可知，改進的聚類算法的融合效率在數(shù)據(jù)量較大的情況下，遠遠高于原聚類算法的效率。原聚類算法因為融合速率較慢，所以無法應(yīng)用于快速檢測中。表62原始聚類法與改進聚類法融合效率對比實物點云幅數(shù)點云中點個數(shù)/個原聚類法融合需時間/分鐘改進聚類法融合所需時間/分鐘某航空葉輪191393371078058某牙模12225179610095某車門12635762341173某面包車部分3217080308960817某大型葉片4036036228無法處理內(nèi)存耗盡2000204060801001201393371225179663576231708030836036228點云數(shù)目/個融合時間/分鐘改進聚類法原始聚類法圖67原始聚類法與改進聚類算法融合效率63在檢測中的應(yīng)用實例本節(jié)以某花瓶為例說明點云融合技術(shù)在快速檢測中的應(yīng)用過程，如圖68AH所示。A導(dǎo)入初始點云數(shù)據(jù)B融合完成后（融合時間14S）C將融合后的點云數(shù)據(jù)與CAD模型導(dǎo)入GEOMAGICQUALIFY軟件中D將點云數(shù)據(jù)與CAD模型對齊E3DCOMPAREF截線分析G截面形狀顯示H截面偏差分析圖68某花瓶點云數(shù)據(jù)與CAD模型的快速檢測過程64本章小結(jié)本章主要對三種融合算法進行了比對和分析，對比了三種算法的融合效果，融合速率，并且分析了三種融合算法的時間復(fù)雜度，空間復(fù)雜度，以及融合的精度。最后以一個實例說明快速檢測的整個流程。EQUATIONCHAPTERNEXTSECTION17結(jié)論與展望71結(jié)論針對企業(yè)需求、國家863課題需求及現(xiàn)有點云融合方法融合數(shù)據(jù)速度慢、占用內(nèi)存大、不能適用于光學(xué)三維快速檢測的問題，在深入研究國內(nèi)外已有點云融合理論的基礎(chǔ)上，結(jié)合面結(jié)構(gòu)光掃描技術(shù)的特點以及快速檢測的工程實際需求，本文對光學(xué)三維快速檢測中的點云融合技術(shù)進行深入研究。提出了點云融合方案，設(shè)計并實現(xiàn)了單面法、中點法，改進了聚類法。最后進行了實驗和分析，并應(yīng)用于工程實際中，取得了較好的效果。本文得出以下主要結(jié)論1設(shè)計并實現(xiàn)了針對光學(xué)三維快速檢測系統(tǒng)的點云融合方案，即首先對點云進行預(yù)處理去除孤立點、計算法向量、計算點云權(quán)值、減小邊界點權(quán)值、精簡數(shù)據(jù)等。然后融合多層點云數(shù)據(jù)，獲得單層完整的點云數(shù)據(jù)，用于比對檢測或逆向設(shè)計。2設(shè)計并實現(xiàn)了單面法融合點云數(shù)據(jù)的方法。首先確定基準點云，然后根據(jù)給定的誤差帶確定并去除非基準點云中的重疊點，最后將不包含重疊點的多幅點云合并為單層的一幅點云。該方法的優(yōu)點是效率高，可以很好的應(yīng)用于快速檢測中，但該方法融合后的表面光滑度不好，不能很好的應(yīng)用于逆向設(shè)計中。3設(shè)計并實現(xiàn)了中點法融合點云數(shù)據(jù)的方法。首先去除每幅點云中的孤立點，其次搜索并確定兩幅點云中重疊區(qū)域的對應(yīng)點對，為了加快搜索速度，本文采用KDTREE空間鄰域搜索策略，最后用點對的中值代替點對中的兩個點，從而實現(xiàn)冗余點的去除。該方法相對于單面法表面光滑度有所改善，但融合效率比單面法慢。4實現(xiàn)了聚類法融合點云數(shù)據(jù)的方法，并對該方法進行了改進首先提出了結(jié)構(gòu)光掃描技術(shù)中點云權(quán)值計算的理論，實現(xiàn)了結(jié)構(gòu)光掃描技術(shù)中點云權(quán)值的計算；其次對KD_TREE空間鄰域搜索方法進行了改進，實現(xiàn)了一種高效的空間近鄰點云搜索策略，有效提高了點云數(shù)據(jù)融合的速度；最后提出按包圍盒等間距分割點云數(shù)據(jù)的方法，分塊多次融合點云，解決了融合海量點云數(shù)據(jù)時內(nèi)存不足的問題。該方法融合效率比單面法低但比中點法高，融合后表面光滑，可以很好的應(yīng)用于快速檢測和逆向設(shè)計中。5改進的聚類算法解決了面結(jié)構(gòu)光掃描測量中點云權(quán)值計算的問題，提高了點云融合的速度，減小了融合過程中內(nèi)存的占用，具有融合速度快、融合精度高、可處理大數(shù)據(jù)量點云（以千萬為單位）的特點?？梢詽M足逆向設(shè)計及三維快速測量系統(tǒng)的需求，已經(jīng)在實際的塑料泡沫檢測、鑄件檢測、葉片檢測、模具檢測以及工程反求應(yīng)用中取得良好的效果。72展望單面法是所有融合方法中效率最高的，如果能對其融合后的表面的光滑度進行改進，那么單面法能很好的應(yīng)用于檢測與逆向設(shè)計中。而聚類法的融合效率也有進一步改進的空間，如果其融合速率能達到單面法的速率，那么將是一種理想的融合方法。目前的研究主要是針對研究所自主研發(fā)的面掃描系統(tǒng)獲取的點云數(shù)據(jù)。這種點云是按掃描線有序排列的，而用其他一些掃描儀器獲取的點云數(shù)據(jù)并不一定有掃描線信息，因此本文的算法并不是通用的算法。而實際應(yīng)用中點云數(shù)據(jù)的格式往往變化不定，但不論哪種數(shù)據(jù)格式，都會包含最基本的3D坐標即XYZ值。所以點云融合應(yīng)該能處理只包含XYZ信息的點云，這樣算法將可以處理各種掃描儀器獲取得到的點云數(shù)據(jù)。EQUATIONCHAPTERNEXTSECTION1致謝首先，我要感謝我的導(dǎo)師梁晉副教授，正是在他的悉心指導(dǎo)和嚴格要求下本文才得以完成，其中梁老師對論文的總體方向進行了嚴格的把握，就論文的寫作以及本課題的關(guān)鍵技術(shù)、方案設(shè)計等諸多方面進行了細致耐心的指導(dǎo)。三年來，梁老師從學(xué)習、生活和科研工作上給予了作者無私的關(guān)懷和幫助，使作者受益匪淺。梁老師嚴謹求實、謙遜博學(xué)的作風將繼續(xù)鞭策著作者奮發(fā)上進。在此，再次向梁老師致以衷心的感謝另外，感謝信息機電研究所的師兄弟們以及一直關(guān)心我的親朋好友，是他們陪伴我度過碩士的三年珍貴時光。最后，我要特別感謝家人對作者最深切的關(guān)懷和莫大的支持，他們是我堅持不懈地投入學(xué)業(yè)的精神支柱。參考文獻1SAZERNIKOV,AFISCHEREMERGINGNONCONTACT3DMEASUREMENTTECHNOLOGIESFORSHAPERETRIEVALANDPROCESSINGJVIRTUALANDPHYSICALPROTOTYPING,2008,3285912KSAITO,TMIYOSHINONCONTACT3DDIGITIZINGANDMACHININGSYSTEMFORFREEFORMSURFACEJANNALSOFTHECIRP,1991,404834863周倫彬逆向非接觸測量技術(shù)淺析J中國測試技術(shù),2005,31525274邵偉,楊軍良,郭俊杰,方海燕非接觸式測量機器人J儀器儀表學(xué)報,2003,2441711725JMHUNTLEYOPTICALSHAPEMEASUREMENTTECHNOLOGYPAST,PRESENTANDFUTUREAPROCEEDINGSOFSPIEC,2000,407611621736PSHUANGA,SZHANGB3DOPTICALMEASUREMENTUSINGPHASESHIFTINGBASEDMETHODSAPROCEEDINGSOFSPIEC,2005,600012127NDAPUZZOOVERVIEWOF3DSURFACEDIGITIZATIONTECHNOLOGIESINEUROPEAPROCEEDINGSOFSPIEC,2006,605611138YDLI，PHGU，F(xiàn)REEFORMSURFACEINSPECTIONTECHNIQUESSTATEOFTHEARTREVIEWJCOMPUTERAIDEDDESIGN，2004,36139514179SSON，HPARK，KHLEE，AUTOMATEDLASERSCANNINGSYSTEMFORREVERSEENGINEERINGANDINSPECTIONJMACHINETOOLSANDMANUFACTORY，2002,4288989710KWOLF,DROLLER,DSCHAFERANAPPROACHTOCOMPUTERAIDEDQUALITYCONTROLBASEDON3DCOORDINATEMETROLOGYAMATERIALPROCESSINGTECHNOLOGYC,2000,1079611011GTURK,MLEVOYZIPPEREDPOLYGONMESHESFROMRANGIMAGESAPROCEEDINGSOFSIGGRAPHC,1994,31131812MGOPI,SKRISHNAN,CSILVASURFACERECONSTRUCTIONBASEDONLOWERDIMENSIONALLOCALIZEDDELAUNAYTRIANGULATIONAPROCEEDINGSOFEUROGRAPHICSC,2000,19346747813DFWATSONCOMPUTINGTHENDIMENSIONALDELAUNAYTESSELLATIONWITHAPPLICATIONTOVORONOIPOLYTOPESJTHECOMPUTERJOURNAL,1981,24216717214姜壽山,楊海成,候增選用空間形狀優(yōu)化標準完成散亂數(shù)據(jù)的三角剖分J計算機輔助設(shè)計與圖形學(xué)報,1995,7424124915呂震反求工程CAD建模中的特征技術(shù)研究D杭州浙江大學(xué),200316FBERNARDINI,JMITTLEMAN,HRUSHMEIER,ETALTHEBALLPIVOTINGALGORITHMFORSURFACERECONSTRUCTIONJIEEETRANSVISUALCOMPUTGRAPH1999,534935917BCURLESS,MLEVOYAVOLUMETRICMETHODFORBUILDINGCOMPLEXMODELSFROMRANGEIMAGESAPROCEEDINGSOFSIGGRAPHC,1996,43844618CROCCHINI,PCIGNONI,FGANONELLI,ETALTHEMARCHINGINTERSECTIONSALGORITHMFORMERGINGRANGEIMAGESJVISUALCOMPUT,2004,14916419WELORENSEN,HECLINEMARCHINGCUBESAHIGHRESOLUTION3DSURFACECONSTRUCTIONALGORITHMAPROCEEDINGSOFSIGGRAPHC,1987,16316920HHILTON,AJSTODDART,JILLINGWORTHETALMARCHINGTRIANGLESRANGEIMAGEFUSIONFORCOMPLEXOBJECTMODELLINGAPROCEEDINGSOFICIPC,1996,38138421YHLIU,HZHOUACCURATEINTEGRATIONOFMULTIVIEWRANGEIMAGESUSINGKMEANSCLUSTERINGJSCIENCEDIRECT,2008,15217522CXFENGINTERNETBASEDREVERSEENGINEERINGJTHEINTERNATIONALJOURNALOFADVANCEDMANUFACTURINGTECHNOLOGY,2003,21213814423呂國剛,諶永祥,李永橋反求工程測量技術(shù)簡述J機械研究與應(yīng)用,2006,1947824KSUNGADDAOCTREETRAVERSALALGORITHMFORRAYTRACINGAEUROGRAPHICS91PROCEEDINGSOFTHEEUROPEANCOMPUTERGRAPHICSCONFERENCEANDEXHIBITIONC,FHPOSTANDWBARTHEDS,PP7385,NORTHHOLLAND,199125劉春明,方漪尋找三維散亂數(shù)據(jù)點拓撲結(jié)構(gòu)的一種算法J青島大學(xué)學(xué)報,2003,183202426HHOPPEPROGRESSIVEMESHESAPROCEEDINGSOFSIGGRAPHCOMPUTERGRAPHICSC,NEWYORKACM,1996,9910827MECK,TDEROSE,TDUCHAMP,ETALMULTIRESOLUTIONANALYSISOFARBITRARYMESHESAPROCEEDINGSOFSIGGRAPHCOMPUTERGRAPHICSCNEWYORKACM,1995,829028JLBENTLEYMULTIDIMENSIONALBINARYSEARCHTREESUSEDFORASSOCIATIVEDSEARCHINGACOMMUNICATIONSOFTHEACMC,197518950951729WANDREWMOOREANINTRODUCTORYTUTORIALONKDTREESRTECHNICALREPORT,COMPUTERLABORATORY,UNIVERSITYOFCAMBRIDGE,199130RSWRIGHT,BLIPCHAKOPENGLSUPERBIBLE3RDEDITIONMSAMSPUBLISHING,200531YDLI,PHGUFREEFORMSURFACEINSPECTIONTECHNIQUESSTATEOFTHEARTREVIEWJCOMPUTERAIDEDDESIGN2004,361395141732SSON,HPARK,KHLEE,AUTOMATEDLASERSCANNINGSYSTEMFORREVERSEENGINEERINGANDINSPECTIONJMACHINETOOLSANDMANUFACTORY2002,4288989733KWOLF,DROLLER,DSCHAFERANAPPROACHTOCOMPUTERAIDEDQUALITYCONTROLBASEDON3DCOORDINATEMETROLOGYJ,MATERIALPROCESSINGTECHNOLOGY2000,1079611034BJBROWN,RSZYMONNONRIGIDGLOBALALIGNMENTUSINGTHINPLATESPLINESASKESTCHESOFACMSIGGRAPH2005C35MITRANJ,GELFANDN,POTTMANNH,ETALREGISTOFPOINTCLOUDDATAFROMAGEOMETRICOPTPERSPECTIVEAGEOMETRYPROCESSINGC,2004233236RSZYMON,BBROWN,MKAZHAN3DSCANMATCHINGANDREGISTRATIONCICCV2005SHORTCOURSE37TVRADY,RMARTIN,JCOXREVERSEENGINEERINGOFGEOMETRICMODELSANINTRODUCTIONJCOMPUTERAIDEDDESIGN,1997,29425526838錢錦鋒逆向工程中的點云處理D杭州浙江大學(xué)，200539MGOPI,SKRISHNAN,AFASTANDEFFICIENTPROJECTIONBASEDAPPROACHF