一種基于特征提取和匹配的點(diǎn)云自動配準(zhǔn)算法

摘 要：針對三維激光點(diǎn)云數(shù)據(jù)配準(zhǔn)問題，提出一種基于特征提取和匹配的點(diǎn)云自動配準(zhǔn)算法。算法依據(jù)點(diǎn)云中每個(gè)點(diǎn)的鄰域點(diǎn)集到該點(diǎn)切平面的平均距離信息來提取特征點(diǎn)。利用點(diǎn)云中四種基本幾何特征形成特征描述算子，根據(jù)特征描述算子的相似性初步搜索匹配點(diǎn)對，然后采用距離約束條件得到精確的匹配點(diǎn)對集合，運(yùn)用四元數(shù)算法計(jì)算初始配準(zhǔn)參數(shù)，最后通過改進(jìn)的迭代最近點(diǎn)（ICP）算法對點(diǎn)云進(jìn)行精確配準(zhǔn)。實(shí)驗(yàn)結(jié)果證明了該算法的有效性和可行性。

關(guān)鍵詞：點(diǎn)云配準(zhǔn)；距離約束；特征提?。蛔罱c(diǎn)迭代

三維激光掃描技術(shù)作為一種目前新興的空間信息獲取技術(shù)，已經(jīng)廣泛應(yīng)用于文物古跡保護(hù)、建筑、數(shù)字城市、土木工程、礦山監(jiān)測等領(lǐng)域，通過對三維激光掃描儀所獲得的多個(gè)視角掃描得到的點(diǎn)云數(shù)據(jù)進(jìn)行坐標(biāo)轉(zhuǎn)換，最終拼接到同一個(gè)坐標(biāo)系里[1-2]，這即是點(diǎn)云的配準(zhǔn)問題。目前，很多國內(nèi)外專家學(xué)者提出了多種點(diǎn)云配準(zhǔn)方法，其中最為常見并且應(yīng)用最為普遍的是迭代最近點(diǎn)（ICP）算法。但I(xiàn)CP算法有其自身的缺陷：首先兩片點(diǎn)云之間必須是包含與被包含的關(guān)系，其次兩片點(diǎn)云必須具有良好的初始位置，否則可能會陷入局部最優(yōu)，得到錯(cuò)誤的配準(zhǔn)結(jié)果。針對ICP算法的局限性，國內(nèi)外很多學(xué)者提出采用兩階段配準(zhǔn)方法，首先對點(diǎn)云進(jìn)行初始配準(zhǔn)獲得良好的初值，然后再采用改進(jìn)的迭代最近點(diǎn)算法[3-4]進(jìn)行精確配準(zhǔn)。文獻(xiàn)[5]通過計(jì)算點(diǎn)云中各點(diǎn)的法向量和曲率，利用幾何哈希方法找出匹配點(diǎn)對進(jìn)行初始配準(zhǔn)；盧章平等[6]提出了一種基于共面4點(diǎn)集的RANSAC初始配準(zhǔn)算法； 利用點(diǎn)的法向量與其鄰近點(diǎn)的法向量的點(diǎn)積來描述點(diǎn)的特征并形成特征描述算子，進(jìn)行初始配準(zhǔn)。

1 算法介紹

文章利用點(diǎn)云法向量幾何信息研究點(diǎn)云自動配準(zhǔn)算法。計(jì)算點(diǎn)云法向量并進(jìn)行方向一致化。根據(jù)各點(diǎn)的法向量獲得每個(gè)點(diǎn)的切平面，利用每個(gè)點(diǎn)的鄰域點(diǎn)集到切平面的距離來判斷該點(diǎn)是否為特征點(diǎn)，得到特征點(diǎn)集，然后對特征點(diǎn)集中的每個(gè)點(diǎn)基于四種幾何特征的點(diǎn)云描述算子，根據(jù)點(diǎn)云描述算子的相似性，得到初始匹配點(diǎn)對，然后再采用距離約束條件得到精確匹配點(diǎn)對，采用四元數(shù)方法計(jì)算初始配準(zhǔn)參數(shù)，精確配準(zhǔn)方面，采用改進(jìn)的ICP算法提高了算法配準(zhǔn)精度。實(shí)驗(yàn)采用經(jīng)典兔子數(shù)據(jù)，得到了比較理想的效果。

2 初始配準(zhǔn)

2.1 提取特征點(diǎn)

對于待配準(zhǔn)的兩片點(diǎn)云，如果對整個(gè)點(diǎn)云搜索匹配點(diǎn)對，將會消耗大量的時(shí)間，同時(shí)也會出現(xiàn)大量錯(cuò)誤匹配點(diǎn)對，為了快速精確的配準(zhǔn)，需要對點(diǎn)云進(jìn)行預(yù)處理，獲得特征點(diǎn)集。通過對點(diǎn)的切平面觀察很容易發(fā)現(xiàn)，如果點(diǎn)云局部區(qū)域鄰域點(diǎn)集到切平面的距離較小時(shí)，說明該區(qū)域比較平坦，特征性不明顯；相反，如果鄰域點(diǎn)集到切平面的距離較大則表明該區(qū)域起伏變化較大，特征性較為明顯。

根據(jù)以上觀察，定義點(diǎn)云中某一點(diǎn)Pi處其K-鄰域內(nèi)點(diǎn)到該點(diǎn)切平面的平均距離即特征距離gi作為判定Pi點(diǎn)是否為特征點(diǎn)的依據(jù)。計(jì)算公式為：

（1）

式中dij指點(diǎn)Pi鄰域某點(diǎn)到Pi點(diǎn)切平面的距離，gi為點(diǎn)Pi的鄰域點(diǎn)到Pi點(diǎn)切平面的平均距離。

根據(jù)該定義，特征距離越大的點(diǎn)表示該區(qū)域起伏變化大，因此可利用此特征距離來提取點(diǎn)云中的特征點(diǎn)。選擇適當(dāng)?shù)拈撝?？?，去掉點(diǎn)云中較為平坦的點(diǎn)，保留gi>？滓1的點(diǎn)，對于保留的點(diǎn)中任意一個(gè)點(diǎn)Pn，若其滿足

則將Pn作為特征點(diǎn)，其中g(shù)（Pn1），g（Pn2），…，g（Pnk）為點(diǎn)Pn的k-鄰近點(diǎn)的特征距離，假設(shè)兩片點(diǎn)云分別為P和Q，其中P為目標(biāo)點(diǎn)集，Q為參考點(diǎn)集，利用文章提出的點(diǎn)云特征提取方法，分別對兩片點(diǎn)云進(jìn)行特征提取，得到P的特征點(diǎn)集為Pt={Pt1，Pt2，…Ptm'}，Q的特征點(diǎn)集為Qt={qt1，qt2，…qtn'}，其中m'和n'分別為P和Q的特征點(diǎn)個(gè)數(shù)。本實(shí)驗(yàn)采用經(jīng)典的斯坦福大學(xué)兔子點(diǎn)云數(shù)據(jù)，提取的特征點(diǎn)如圖1所示。

2.2 尋找匹配點(diǎn)對

2.2.1 初步獲取匹配點(diǎn)對

文章選擇四種基本幾何特征作為特征描述算子，初步搜索特征點(diǎn)集中的匹配點(diǎn)對。采用多種幾何特征信息不僅可以更加細(xì)致精確的描述鄰域特征信息，同時(shí)也可以避免大量錯(cuò)誤匹配點(diǎn)對的出現(xiàn)，以目標(biāo)點(diǎn)集Pt為例，四種幾何特征描述如下：

（1）根據(jù)點(diǎn)集Pt中的每一個(gè)點(diǎn)Pti，以其K-鄰近點(diǎn)的特征距離作為第一種特征量，公式如下

f1（Pti）=g（Pti） （3）

（2）根據(jù)點(diǎn)集Pt中的每一個(gè)點(diǎn)Pti，計(jì)算該點(diǎn)的k-鄰近點(diǎn)重心O（Pti），以該點(diǎn)與其K鄰近點(diǎn)重心O（Pti）之間的距離值作為第二種特征量，公式入下

f2（Pti）=Pti-O（Pti） （4）

（3）根據(jù)點(diǎn)集Pt中的每一個(gè)點(diǎn)Pti，計(jì)算該點(diǎn)法向量的變化程度即該點(diǎn)法向量與K-鄰近點(diǎn)法向量之間夾角余弦的算術(shù)平均值作為第三種特征量，公式如下

（5）

其中cos（？茲ij）為點(diǎn)Pti的法向量與其鄰近點(diǎn)Pti法向量的夾角的余弦值。

（4）根據(jù)點(diǎn)集Pt中的每一個(gè)點(diǎn)Pti，以該點(diǎn)法向量 ni和該點(diǎn)與其K-鄰近點(diǎn)重心之間連線的夾角余弦值作為該點(diǎn)的第四種特征量，公式如下

（6）

通過以上四種特征量的求解，我們得到Pti和qti的特征向量，最后分別得到Pt和Qt的特征向量點(diǎn)集L1和L2，對于點(diǎn)集Pt中每一個(gè)點(diǎn)，在點(diǎn)集Qt中搜索其匹配點(diǎn)，如果Pti與qti是匹配點(diǎn)對，那么它們會有相同或者相似的幾何特征，特征向量也應(yīng)該是相同或者相似的。特征點(diǎn)的相似性，采用特征向量間的歐氏距離作為比較準(zhǔn)則，對于點(diǎn)集Pt中的Pti點(diǎn)與點(diǎn)集Qt中的一點(diǎn)qti同時(shí)滿足以下四個(gè)條件則認(rèn)為他們是一對匹配點(diǎn)對，四個(gè)條件分別是：