一種新型稀疏標(biāo)志點(diǎn)的特征描述算法

石誠(chéng)，程筱勝，崔海華，方舟，張逸，胡廣露

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

0 引言

近年來(lái)，隨著航空航天、汽車船舶、機(jī)電重工等大型裝備制造業(yè)蓬勃發(fā)展，攝影測(cè)量技術(shù)因其便攜、快速和高精度的優(yōu)點(diǎn)，正得到越來(lái)越多的應(yīng)用[1]。為將攝影測(cè)量應(yīng)用于大型裝備制造裝配變形分析，提出一種稀疏標(biāo)志點(diǎn)數(shù)據(jù)的特征描述算法，用以匹配變形前后的標(biāo)志點(diǎn)數(shù)據(jù)。

目前關(guān)于點(diǎn)云數(shù)據(jù)匹配的研究[2-3]大多針對(duì)點(diǎn)云密度較高的數(shù)據(jù)，一般分為粗配準(zhǔn)和精配準(zhǔn)[4]，通常采用“先粗后精”的思路。粗配準(zhǔn)主要分為基于RANSAC[5]和基于特征的配準(zhǔn)方法，其中基于特征匹配的方式，更具有效率和魯棒性[6]。RUSU R B等提出了視點(diǎn)特征直方圖[7](viewpoint feature histogram，VFH)特征量和快速點(diǎn)云直方圖[8](fast point feature histograms，F(xiàn)PFH)特征量作為描述子；劉劍等[9]將三角剖分與FPFH特征描述相結(jié)合，黃源等[10]利用局部幾何特征作為描述子，進(jìn)行數(shù)據(jù)的匹配。這些描述特征點(diǎn)的思路被借鑒，用以解決稀疏標(biāo)志點(diǎn)數(shù)據(jù)的匹配問(wèn)題，翁金平等[11]使用能量法描述稀疏標(biāo)志點(diǎn)，實(shí)現(xiàn)了標(biāo)志點(diǎn)的特征匹配，但能量法局限于標(biāo)志點(diǎn)數(shù)據(jù)不發(fā)生形變的情況，適用性不夠廣泛。

本文受點(diǎn)特征直方圖[12](point feature histograms，PFH)描述算法啟發(fā)，利用稀疏標(biāo)志點(diǎn)數(shù)據(jù)鄰域的拓?fù)湫畔?，進(jìn)行稀疏標(biāo)志點(diǎn)數(shù)據(jù)的匹配。

1 特征描述算法

假設(shè)攝影測(cè)量在初始狀態(tài)獲取的標(biāo)志點(diǎn)數(shù)據(jù)集合為點(diǎn)集P，產(chǎn)生局部形變后獲取的數(shù)據(jù)集合為點(diǎn)集Q。P和Q在不同測(cè)量坐標(biāo)系下且包含未發(fā)生形變的點(diǎn)對(duì)，稀疏標(biāo)志點(diǎn)的描述算法根據(jù)點(diǎn)鄰域的拓?fù)湫畔?，?duì)P和Q中每個(gè)點(diǎn)做唯一描述，描述結(jié)果稱為描述子。通過(guò)描述子確定P和Q的對(duì)應(yīng)點(diǎn)對(duì)，并篩選出其中幾乎未發(fā)生形變的點(diǎn)對(duì)，以完成稀疏標(biāo)志點(diǎn)數(shù)據(jù)的匹配。

1.1 描述子的建立

任選稀疏數(shù)據(jù)中一點(diǎn)Po，簡(jiǎn)述描述子的建立過(guò)程：

1)利用KD樹(shù)檢索，查找距離Po最近的k個(gè)點(diǎn)，依據(jù)這些點(diǎn)與Po的歐氏距離di(i=1,2,…,k)：

(1)

將這k個(gè)點(diǎn)由近及遠(yuǎn)，構(gòu)成k鄰域點(diǎn)集Pk(圖1)。取k=3，展示了k鄰域點(diǎn)集Pk的建立思路。

圖1 建立k鄰域點(diǎn)集Pk

2)對(duì)于點(diǎn)集Pk內(nèi)一點(diǎn)Pi，在Po處建立圖2所示的局部坐標(biāo)系(u,v,w) (U,V,W)，其中no為點(diǎn)Po的法矢，建立過(guò)程如下：

U=no

(2)

(3)

W=U×V

(4)

圖2 定義局部坐標(biāo)系

其中:坐標(biāo)軸u、v、w的方向分別對(duì)應(yīng)矢量U、V、W的方向。

3)基于局部坐標(biāo)系(u,v,w)，根據(jù)PFH特征值的計(jì)算方法，計(jì)算圖2中一組角度，來(lái)表示點(diǎn)Po法矢no和點(diǎn)Pi法矢ni的偏差：

α=V·ni

(5)

(6)

θ=arctan(W·ni,U·ni)

(7)

4)按照步驟2)、步驟3)，分別計(jì)算Po與點(diǎn)集合Pk中各點(diǎn)的特征值α、φ、θ，則每對(duì)點(diǎn)Po和Pi可得到如下四維描述向量，記為Di：

Di=(di,αi,φi,θi)

(8)

5)按照k鄰域點(diǎn)集Pk中的順序，建立點(diǎn)Po的k×4描述矩陣D，D即為點(diǎn)Po的描述子：

D=(D1,D2,…,Dk)T

(9)

6)將描述矩陣D進(jìn)一步變形為如下形式，則β為k維的向量，由各鄰域點(diǎn)到點(diǎn)Po的歐氏距離構(gòu)成，B為k×3的矩陣，由各鄰域點(diǎn)到點(diǎn)Po的角度特征構(gòu)成：

D=(βT,B)

(10)

將描述子D拆分，是因?yàn)棣履軌蚋鼫?zhǔn)確地判斷前后點(diǎn)之間的對(duì)應(yīng)關(guān)系，而矩陣B更好地折射出形變大小。下文稱β為距離向量，稱B為角度矩陣。

1.2 描述子相似度的衡量

利用上述算法計(jì)算出稀疏數(shù)據(jù)中每個(gè)點(diǎn)的描述子，點(diǎn)集P中所有點(diǎn)的描述子構(gòu)成集合FP={Dpi|1≤i≤nP，i∈N}, 點(diǎn)集Q中所有點(diǎn)的描述子構(gòu)成集合FQ={Dqj|1≤j≤nQ，j∈N}。其中nP和nQ分別為點(diǎn)集P和Q中點(diǎn)的總個(gè)數(shù)，Dpi和Dqj分別為點(diǎn)集P中第i個(gè)點(diǎn)和點(diǎn)集Q中第j個(gè)點(diǎn)的描述子。

(11)

利用最近鄰匹配法(nearest neighbor)[13]和閾值法分析距離向量，初步獲取點(diǎn)集P和Q的對(duì)應(yīng)點(diǎn)對(duì)。最近鄰匹配法即對(duì)P中一點(diǎn)Ps，取其對(duì)應(yīng)的距離向量βps，然后搜索出點(diǎn)集Q中距離最近的向量βqt，將點(diǎn)Ps和點(diǎn)Qt視作一對(duì)對(duì)應(yīng)點(diǎn)。為了防止誤匹配，再使用閾值法，設(shè)置閾值h1，若ρ(βpi,βqj)≤h1，則將這對(duì)點(diǎn)作為初步匹配結(jié)果。

初步獲取對(duì)應(yīng)點(diǎn)對(duì)后，需篩選出其中幾乎沒(méi)有發(fā)生形變的點(diǎn)對(duì)，這就要利用角度矩陣。角度矩陣主要描述了查詢點(diǎn)與其周圍k個(gè)鄰域點(diǎn)之間的相對(duì)位置關(guān)系，因此假如該查詢點(diǎn)與其k個(gè)鄰域點(diǎn)的位置較為恒定，角度矩陣并沒(méi)有太大的變化；反之，角度矩陣則會(huì)有明顯變化。據(jù)此，利用F-范數(shù)來(lái)衡量角度矩陣的變化大小。以對(duì)應(yīng)點(diǎn)對(duì)Ps和Qt為例：

BE=Bps-Bqt

(12)

2 實(shí)驗(yàn)結(jié)果及分析

2.1 實(shí)驗(yàn)過(guò)程及評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)利用加拿大某公司的攝影測(cè)量設(shè)備獲取標(biāo)志點(diǎn)，圖3(a)為初始狀態(tài)的標(biāo)志點(diǎn)排布情況，圖3(b)模擬了局部形變和位移后，標(biāo)志點(diǎn)的排布，圖中黑色圓內(nèi)的靶標(biāo)是基準(zhǔn)點(diǎn)，用于變形前后數(shù)據(jù)匹配，以驗(yàn)證算法精度。實(shí)驗(yàn)過(guò)程具體步驟如下：

1) 布設(shè)標(biāo)志點(diǎn)，獲取標(biāo)志點(diǎn)點(diǎn)集P；

2) 模擬局部位移和形變，變換測(cè)量坐標(biāo)系，獲取標(biāo)志點(diǎn)點(diǎn)集Q；

3) 通過(guò)基準(zhǔn)靶標(biāo)，利用奇異值分解[14](SVD)算法，匹配點(diǎn)集P和Q；

4) 輸出對(duì)應(yīng)點(diǎn)的編號(hào)，并計(jì)算各點(diǎn)變形大??；

5) 利用本文提出的算法，篩選出幾乎不形變的對(duì)應(yīng)點(diǎn)對(duì)，據(jù)此匹配點(diǎn)集P和Q；

6) 輸出對(duì)應(yīng)點(diǎn)的編號(hào)，計(jì)算各點(diǎn)變形大小。

圖3 標(biāo)志點(diǎn)排布情況

步驟4)所得結(jié)果作為本次實(shí)驗(yàn)的標(biāo)準(zhǔn)值，將步驟6)結(jié)果與標(biāo)準(zhǔn)值對(duì)比，驗(yàn)證本文算法的準(zhǔn)確性和匹配精度。

2.2 實(shí)驗(yàn)數(shù)據(jù)分析

兩次測(cè)量所獲取的點(diǎn)集分別為P和Q，它們的標(biāo)志點(diǎn)編號(hào)分別如圖4(a)、圖4(b)所示。

圖4 標(biāo)志點(diǎn)編號(hào)

使用本文的算法，得到對(duì)應(yīng)點(diǎn)對(duì)的初步匹配關(guān)系如圖5所示，在獲取了初步對(duì)應(yīng)點(diǎn)對(duì)匹配結(jié)果之后，繼續(xù)使用本文的算法，篩選出幾乎不發(fā)生形變的對(duì)應(yīng)點(diǎn)對(duì)，這些點(diǎn)對(duì)記錄在表1。

圖5 對(duì)應(yīng)點(diǎn)匹配結(jié)果

表1 用于匹配的對(duì)應(yīng)點(diǎn)對(duì)

利用表1中的對(duì)應(yīng)點(diǎn)對(duì)，計(jì)算轉(zhuǎn)換矩陣，匹配點(diǎn)集P和Q，并計(jì)算各點(diǎn)變形前后的誤差。利用基準(zhǔn)點(diǎn)匹配所得的誤差如圖6所示，將作為誤差評(píng)判的標(biāo)準(zhǔn)。利用本文算法匹配所計(jì)算出的誤差如圖7。將本文算法和標(biāo)準(zhǔn)結(jié)果對(duì)比，偏差結(jié)果如圖8所示，最大偏差為-0.098mm，最小偏差為-0.017mm，絕對(duì)偏差的平均值為0.029mm。

圖6 各點(diǎn)標(biāo)準(zhǔn)誤差

圖7 本文算法所得各點(diǎn)誤差

圖8 本文算法與標(biāo)準(zhǔn)結(jié)果對(duì)比

在進(jìn)行了大量實(shí)驗(yàn)統(tǒng)計(jì)后，對(duì)應(yīng)點(diǎn)對(duì)匹配的成功率接近100%，絕對(duì)平均誤差為平均值為0.029mm，最低僅為0.008mm。

3 結(jié)語(yǔ)

為解決稀疏標(biāo)志點(diǎn)的匹配問(wèn)題，本文借助PFH的描述思想，提出了稀疏標(biāo)志點(diǎn)的特征描述算法，并以此對(duì)各標(biāo)志點(diǎn)進(jìn)行唯一性描述。實(shí)驗(yàn)證明，該算法具有極高的準(zhǔn)確性，能夠精準(zhǔn)地分析出基本不發(fā)生形變的對(duì)應(yīng)點(diǎn)對(duì)。利

用這些點(diǎn)對(duì)求解轉(zhuǎn)換矩陣并完成匹配，平均偏差為0.029mm，足以滿足裝配周期較長(zhǎng)的大尺寸裝配攝影測(cè)量變形檢測(cè)的需求。同時(shí)，本文的算法也能應(yīng)用于其他需要標(biāo)志點(diǎn)匹配的情形，例如基于標(biāo)志點(diǎn)匹配的點(diǎn)云拼接。為保證匹配結(jié)果的準(zhǔn)確性，本文對(duì)未發(fā)生形變的點(diǎn)對(duì)篩選過(guò)于嚴(yán)格，被篩選出的點(diǎn)在鄰域內(nèi)幾乎不發(fā)生形變，今后將進(jìn)一步改進(jìn)，以適應(yīng)更多稀疏標(biāo)志點(diǎn)匹配的應(yīng)用場(chǎng)景。