摘 要:針對三維激光點(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è)條件分別是: