公共點(diǎn)自動(dòng)匹配算法研究

鄭應(yīng)新，岳建平，甄宗坤

(河海大學(xué)地球科學(xué)與工程學(xué)院，江蘇南京210098)

一、引 言

三維激光掃描技術(shù)以其無(wú)接觸、掃描速度快、獲取信息量大、精度高、實(shí)時(shí)性強(qiáng)、全自動(dòng)化、復(fù)雜環(huán)境測(cè)量等優(yōu)點(diǎn)被廣泛應(yīng)用于測(cè)繪、逆向工程及珍貴文物保護(hù)等領(lǐng)域，隨著應(yīng)用的深入，提高點(diǎn)云數(shù)據(jù)處理的速度和精度的重要性也日漸突出。而點(diǎn)云拼接是點(diǎn)云數(shù)據(jù)處理的基礎(chǔ)，也是最關(guān)鍵的一步，它的效率直接影響點(diǎn)云數(shù)據(jù)后續(xù)處理，因此，實(shí)現(xiàn)點(diǎn)云拼接的自動(dòng)化具有重要的意義。目前點(diǎn)云拼接的方法主要有：公共點(diǎn)法、絕對(duì)定位法和ICP法。其中，公共點(diǎn)法由于其精度高、可靠性好而被廣泛采用。但目前軟件中自帶的公共點(diǎn)的拼接方法多是手動(dòng)或半自動(dòng)的，這無(wú)疑降低了工作效率。針對(duì)這一問(wèn)題，本文利用歐氏距離不變的特性提出基于重心化歐氏距離的公共點(diǎn)自動(dòng)匹配方法，并針對(duì)該方法中可能出現(xiàn)的危險(xiǎn)球問(wèn)題，提出散亂點(diǎn)有序化自動(dòng)匹配方法，以期實(shí)現(xiàn)拼接過(guò)程的自動(dòng)化、高效化。

二、散亂點(diǎn)的重心化歐氏距離自動(dòng)匹配

基于公共點(diǎn)的點(diǎn)云匹配方法至少需要3個(gè)公共點(diǎn)，在一組公共點(diǎn)中任意一點(diǎn)到該公共點(diǎn)組重心的距離保持不變。因此，不同測(cè)站的公共點(diǎn)重心認(rèn)為是同名點(diǎn)，利用該性質(zhì)可進(jìn)行各公共點(diǎn)的匹配。

現(xiàn)有目標(biāo)點(diǎn)集P、參考點(diǎn)集Q，兩點(diǎn)集重心的坐標(biāo)計(jì)算為

式中，n為公共點(diǎn)的個(gè)數(shù)。

P、Q點(diǎn)集中任意一點(diǎn)到該點(diǎn)集重心的距離為

若|D1(i)－ D2(j)|＜ ε，i、j=(1，2，…，n)，則認(rèn)為P中第i點(diǎn)與Q中第j點(diǎn)為對(duì)應(yīng)點(diǎn)，據(jù)此判斷其他對(duì)應(yīng)點(diǎn)。閾值ε可根據(jù)測(cè)量精度及經(jīng)驗(yàn)選取。

三、散亂點(diǎn)集有序化的自動(dòng)匹配

上述方法雖然簡(jiǎn)便高效，但若有兩個(gè)以上的重心化距離十分接近，將引起判斷錯(cuò)誤。為解決此問(wèn)題，提出點(diǎn)集有序化的方法。該方法的基本思路是：計(jì)算所有公共點(diǎn)到重心的距離，然后選取與其他距離不相等的距離，通過(guò)不相等的距離匹配得到對(duì)應(yīng)點(diǎn)。若不存在唯一距離，則通過(guò)角度來(lái)找穩(wěn)健對(duì)應(yīng)點(diǎn)，再計(jì)算該對(duì)穩(wěn)健對(duì)應(yīng)點(diǎn)與其他公共點(diǎn)的距離，并將距離排序，根據(jù)排序后的點(diǎn)名匹配對(duì)應(yīng)點(diǎn)。數(shù)學(xué)模型描述如下：

重心坐標(biāo)按式(1)計(jì)算，重心與公共點(diǎn)的距離按式(2)計(jì)算，并根據(jù)計(jì)算的距離進(jìn)行判斷。判斷原則：若點(diǎn)集P中D1(i)與P中其他公共點(diǎn)到重心的距離的差值最大，則認(rèn)為D1(i)是唯一的，在點(diǎn)集Q中也一定存在某段距離與其他公共點(diǎn)到重心的距離的差值最大，設(shè) Q中此段距離為D2(m)，若|D1(i)－D2(m)|＜ε，則認(rèn)為P中i點(diǎn)與Q中m點(diǎn)為穩(wěn)健對(duì)應(yīng)點(diǎn)。計(jì)算P中i點(diǎn)到其他公共點(diǎn)的距離，以及Q中m點(diǎn)到其他公共點(diǎn)的距離。公共點(diǎn)之間的距離為

式中，i、j=1，2，…，n;k 為點(diǎn)集號(hào)，取值 1、2。

穩(wěn)健對(duì)應(yīng)點(diǎn)到其他公共點(diǎn)距離按式(4)計(jì)算完畢后，分別對(duì)兩點(diǎn)集距離排序，即D1(i，j)＜D1(i，k)＜… ＜D1(i，n)，D2(m，h) ＜D2(m，l)＜ … ＜D2(m，n)。該不等式中，j、k表示目標(biāo)點(diǎn)集P中點(diǎn)號(hào)，j、k=1，2，…，n，且 j≠k;h、l表示參考點(diǎn)集 Q 中的點(diǎn)號(hào)，h、l=1，2，…，n，且 h≠l。然后提取排序后的點(diǎn)號(hào)，若|D1(i，j)－D2(m，h)|＜ ε，則提取的點(diǎn)號(hào)自動(dòng)匹配。但若穩(wěn)健點(diǎn)到某兩公共點(diǎn)之間距離相近，則有可能會(huì)出現(xiàn)匹配錯(cuò)誤。

若點(diǎn)集P、Q中重心o到公共點(diǎn)的距離大致相等，則需通過(guò)角度來(lái)尋找最穩(wěn)健的對(duì)應(yīng)點(diǎn)。角度計(jì)算公式為

四、矢量化點(diǎn)集自動(dòng)匹配

按下式計(jì)算以重心o為起點(diǎn)，各公共點(diǎn)為終點(diǎn)的向量為

式中，(xp，yp，zp)為點(diǎn)集 P 的重心坐標(biāo);(xq，yq，zq)為點(diǎn)集 Q 的重心坐標(biāo);i、j=1，2，…，n。

向量之間夾角的計(jì)算公式為

式中，k 為點(diǎn)集號(hào)，k=1，2;i、j=1，2，…，n。

首先判斷各向量之間夾角是否相等，向量夾角的情況分為以下3種：

3)若向量夾角均相等，則在點(diǎn)集Q中尋找與點(diǎn)集P中向量長(zhǎng)度相等的向量，進(jìn)而判斷匹配點(diǎn)。如果出現(xiàn)至少3個(gè)向量的長(zhǎng)度相等，且這3個(gè)向量間夾角相等，則提示錯(cuò)誤。

五、實(shí)例驗(yàn)證

對(duì)上述方法分別用實(shí)測(cè)數(shù)據(jù)進(jìn)行驗(yàn)證，結(jié)果見(jiàn)表1～表3。

表1 散亂點(diǎn)重心化自動(dòng)匹配結(jié)果

表2 散亂點(diǎn)有序化自動(dòng)匹配結(jié)果

表3 矢量化方法自動(dòng)匹配結(jié)果

由試驗(yàn)結(jié)果可以看出，3種方法匹配結(jié)果正確。通過(guò)上述方法，可快速準(zhǔn)確地得到兩站中同一標(biāo)志的對(duì)應(yīng)點(diǎn)，保證了其一一對(duì)應(yīng)的關(guān)系。

六、結(jié)束語(yǔ)

本文研究了基于公共點(diǎn)自動(dòng)匹配問(wèn)題。結(jié)合歐氏距離不變?cè)硖岢錾y點(diǎn)重心化匹配方法，但如果公共點(diǎn)位于危險(xiǎn)球上，上述方法可能失效，為此對(duì)該方法作了進(jìn)一步改進(jìn)，提出散亂點(diǎn)有序化的方法。試驗(yàn)結(jié)果表明，改進(jìn)的方法可有效解決危險(xiǎn)球問(wèn)題。結(jié)合歐氏角度不變?cè)?，提出矢量化匹配方法，并根?jù)矢量化過(guò)程中出現(xiàn)的幾種問(wèn)題提出了相應(yīng)的解決方法。從試驗(yàn)結(jié)果可以看出，該方法簡(jiǎn)便、高效，準(zhǔn)確度高，可有效解決匹配過(guò)程中手動(dòng)及半自動(dòng)方法的問(wèn)題，提高了匹配效率。

［1］王力，李廣云，賀磊，等.點(diǎn)云拼接中標(biāo)志自動(dòng)匹配方法［J］.測(cè)繪科學(xué)，2011，36(2)：144-145.

［2］魏江，熊邦書(shū)，馮燕，等.基于法向量的多視點(diǎn)定標(biāo)球球心算法［J］.計(jì)算機(jī)工程與應(yīng)用，2005，41(19)：15-17.

［3］張東，黃騰，陳建華，等.基于羅德里格矩陣的三維激光掃描點(diǎn)云配準(zhǔn)算法［J］.測(cè)繪科學(xué)，2012，37(1)：159-160.

［4］YANG Shen，QI Yue，SHEN Xukun，et al.Rapid and Automatic Method for 3D Scanned Data Registration［J］.Journal of Software，2010，21(6)：1438-1450.

［5］盧小平，王玉鵬，盧遙，等.齊云塔激光點(diǎn)云三維重建［J］.測(cè)繪通報(bào)，2011(9)：11-14.

［6］HARTLEY R，ZISSERMAN A.Multiple View Geometry in Computer Vision［M］.London：Cambridge University Press，2002.