足部模型點(diǎn)云配準(zhǔn)方法研究

馬天嬌，葉方堅(jiān)，韓廣良，劉培勛※

（1.中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，長(zhǎng)春 130033；2.公安部物證鑒定中心痕跡科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100038）

0 引言

痕跡檢驗(yàn)技術(shù)是公安部在進(jìn)行刑事案件及其他各類(lèi)案件中應(yīng)用最廣泛的一門(mén)技術(shù)。足部點(diǎn)云配準(zhǔn)與三維重建是刑事科學(xué)技術(shù)研究中的一項(xiàng)重要研究課題，由于受設(shè)備傳感器的限制，三維掃描測(cè)量設(shè)備在進(jìn)行掃描物體時(shí)每次只能掃到被測(cè)物體的部分點(diǎn)云數(shù)據(jù)，若想獲得被測(cè)物體的全部點(diǎn)云數(shù)據(jù)，需對(duì)被測(cè)物體的不同視角進(jìn)行多次掃描，并對(duì)每個(gè)視角的點(diǎn)云數(shù)據(jù)進(jìn)行融合拼接。然而每個(gè)視角下的點(diǎn)云都具有獨(dú)立的坐標(biāo)系，無(wú)法實(shí)現(xiàn)直接對(duì)其拼接。因此需要對(duì)所有視角下獲取到的點(diǎn)云進(jìn)行坐標(biāo)變換統(tǒng)一到同一坐標(biāo)系下，對(duì)相鄰視角的點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)融合，拼接出被測(cè)物體完整的點(diǎn)云數(shù)據(jù)。

目前國(guó)內(nèi)外研究學(xué)者對(duì)點(diǎn)云配準(zhǔn)都進(jìn)行了深入的研究，也取得了豐碩的研究成果。常見(jiàn)的點(diǎn)云配準(zhǔn)拼接方法主要分為兩大類(lèi)。

一類(lèi)是無(wú)輔助的自動(dòng)拼接，其中以迭代最近點(diǎn)法（ICP）及其改進(jìn)算法[1-4]和基于幾何特征匹配法[5]為代表的算法目前應(yīng)用最為廣泛。如MavridisP等[6]提出了一種基于混合優(yōu)化系統(tǒng)的稀疏ICP算法，來(lái)改善配算算法的速度和精度問(wèn)題；Dus等[7]提出了尺度ICP算法，解決了含尺度因素的點(diǎn)云配準(zhǔn)問(wèn)題；趙夫群等[8]提出了基于旋轉(zhuǎn)角約束來(lái)解決由于旋轉(zhuǎn)角度過(guò)大而引起的配準(zhǔn)效果不佳的問(wèn)題，然而用迭代最近法（ICP）進(jìn)行點(diǎn)云配準(zhǔn)時(shí)往往容易陷入局部最優(yōu)解，且該方法要求待配準(zhǔn)的兩個(gè)點(diǎn)云位置相差不大，因此直接采用迭代最近法（ICP）進(jìn)行點(diǎn)云配準(zhǔn)往往無(wú)法達(dá)到理想的配準(zhǔn)效果。用特征點(diǎn)匹配就是通過(guò)分析被測(cè)物體的局部幾何特征來(lái)尋找特征點(diǎn)并實(shí)現(xiàn)匹配。如Liao等[9]提出了一種基于局部特征的配準(zhǔn)方法，通過(guò)計(jì)算兩個(gè)點(diǎn)集的幾何特征，建立對(duì)應(yīng)特征點(diǎn)對(duì)并計(jì)算其剛體變換矩陣來(lái)實(shí)現(xiàn)點(diǎn)云配準(zhǔn)問(wèn)題。但該算法特征點(diǎn)往往包含的幾何信息較少，因此穩(wěn)定性有待提高。

另一類(lèi)點(diǎn)云配準(zhǔn)拼接方法就是人工輔助標(biāo)志點(diǎn)配準(zhǔn)方法[10-11]，該方法常用于沒(méi)有明顯特征點(diǎn)的物體，當(dāng)傳感器從不同視角無(wú)法對(duì)同一點(diǎn)獲取的點(diǎn)云數(shù)據(jù)進(jìn)行有效識(shí)別定位，此時(shí)就需要人為在被測(cè)物體上添加標(biāo)志點(diǎn)，進(jìn)行測(cè)量。

傳統(tǒng)點(diǎn)云配準(zhǔn)方法對(duì)于采集到的點(diǎn)云數(shù)據(jù)要求較高，需滿(mǎn)足待配準(zhǔn)的兩點(diǎn)云具有較高重疊度的條件，否則就會(huì)導(dǎo)致配準(zhǔn)不準(zhǔn)確。由于人體足部特征信息較少，且足部外表幾何形狀結(jié)構(gòu)不規(guī)則，當(dāng)足部模型點(diǎn)云采集工作受三維測(cè)量設(shè)備成像距離與角度的限制時(shí)，會(huì)導(dǎo)致從腳趾和腳跟方向采集到的點(diǎn)云數(shù)據(jù)與從足部側(cè)面采集到的點(diǎn)云數(shù)據(jù)重疊度較低，從而給點(diǎn)云配準(zhǔn)工作帶來(lái)很大難度。本文針對(duì)這一難題提出了一種先粗配準(zhǔn)再細(xì)配準(zhǔn)的配準(zhǔn)策略。首先采用具有規(guī)則幾何形狀的底座作輔助，并結(jié)合包圍盒的配準(zhǔn)方法對(duì)足部模型點(diǎn)云進(jìn)行粗配準(zhǔn)，然后再采用ICP最近點(diǎn)迭代算法進(jìn)行足部模型點(diǎn)云精配準(zhǔn)，最終實(shí)現(xiàn)足部模型完整點(diǎn)云的獲取。實(shí)驗(yàn)結(jié)果證明，該方法不但可以得到足部模型的完整點(diǎn)云，且與傳統(tǒng)的點(diǎn)云配準(zhǔn)方法相比，大大減少了計(jì)算量，縮短了計(jì)算時(shí)間。

1 點(diǎn)云配準(zhǔn)理論及方法

由于人體足部整體結(jié)構(gòu)呈長(zhǎng)條形，腳趾外表面呈不規(guī)則幾何形狀，使得三維掃描設(shè)備在對(duì)足部模型進(jìn)行點(diǎn)云數(shù)據(jù)采集時(shí)，會(huì)出現(xiàn)從腳趾和腳跟方向采集到的點(diǎn)云數(shù)據(jù)與從足部側(cè)面采集到的點(diǎn)云數(shù)據(jù)重疊度較低的情況，因此本文在對(duì)足部模型點(diǎn)云配準(zhǔn)時(shí)，在足部模型下方增加一個(gè)具有規(guī)則幾何形狀的立方體底座，利用立方體底座法向量均勻規(guī)則的特性來(lái)輔助足部模型點(diǎn)云粗配準(zhǔn)工作。具體配準(zhǔn)方法是：在進(jìn)行點(diǎn)云數(shù)據(jù)采集時(shí)，針對(duì)相鄰的兩片點(diǎn)云進(jìn)行配準(zhǔn)，先采用基于旋轉(zhuǎn)角約束的AABB包圍盒法對(duì)點(diǎn)云進(jìn)行粗配準(zhǔn)，待粗配準(zhǔn)工作結(jié)束后，采用點(diǎn)云分割方法去掉足部模型下方立方體底座，最后進(jìn)行足部模型點(diǎn)云細(xì)配準(zhǔn)。

1.1 基于旋轉(zhuǎn)約束的AABB包圍盒粗配準(zhǔn)

1.1.1 AABB包圍盒

AABB包圍盒是包含被測(cè)模型，且邊平行于坐標(biāo)軸的最小六面體。描述一個(gè)AABB包圍盒僅需要6個(gè)參數(shù)，即沿3個(gè)坐標(biāo)軸方向的最小坐標(biāo)值和最大坐標(biāo)值。如圖1所示，ABCD-A′B′C′D′為包含源點(diǎn)云的包圍盒，EFGH-E′F′G′H′包含目標(biāo)點(diǎn)云的包圍盒，記xmin, ymin, zmin和xmax, ymax, zmax為源點(diǎn)云AABB包圍盒沿3個(gè)坐標(biāo)軸方向的最小坐標(biāo)值和最大坐標(biāo)值，和為目標(biāo)點(diǎn)云AABB包圍盒沿3個(gè)坐標(biāo)軸方向的最小值和最大值，Cp為包圍盒ABCD-A′B′C′D′的質(zhì)心， Cq為包圍盒EFGH-E′F′G′H′的質(zhì)心，p為坐標(biāo)原點(diǎn)O到Cp之間的向量，q為坐標(biāo)原點(diǎn)O到Cq之間的向量，根據(jù)源點(diǎn)云與目標(biāo)點(diǎn)云包圍盒質(zhì)心可計(jì)算ABCD-A′B′C′D′到EFGH-E′F′G′H′剛體變換的初始旋轉(zhuǎn)平移矩陣q0=[R0,t0]T。

圖1 包含源點(diǎn)云與目標(biāo)點(diǎn)云的AABB包圍盒

1.1.2 旋轉(zhuǎn)約束

旋轉(zhuǎn)約束是針對(duì)AABB包圍盒進(jìn)行剛性變換時(shí)設(shè)置的幾何約束。其目的是給粗配準(zhǔn)過(guò)程中的剛性變換加入收斂條件，當(dāng)變換后滿(mǎn)足旋轉(zhuǎn)約束的收斂條件時(shí)，則粗配準(zhǔn)工作完成。

假設(shè)P、Q為相鄰的兩組原始點(diǎn)云數(shù)據(jù)集。本文采用K-d tree的方法在兩組點(diǎn)云數(shù)據(jù)集中的立方體底座上找到具有對(duì)應(yīng)關(guān)系的點(diǎn)對(duì)，如圖2所示，分別記為源點(diǎn)云p與目標(biāo)點(diǎn)云q，記pi=(xi, yi, zi)為源點(diǎn)云中的點(diǎn)，qi=(xi, yi, zi)為目標(biāo)點(diǎn)云中的點(diǎn)，nis為 pi對(duì)應(yīng)的法線(xiàn)，nit為qi對(duì)應(yīng)的法線(xiàn)，定義nis與nit之間的偏差為θ：

圖2 源點(diǎn)云中的點(diǎn)與目標(biāo)點(diǎn)云中點(diǎn)的法向量偏差

1.2 ICP最近點(diǎn)迭代

ICP（Iterative Closest Point）最近點(diǎn)迭代法的的本質(zhì)基于最小二乘的最優(yōu)配準(zhǔn)法。其基本思想是：從源點(diǎn)云和目標(biāo)點(diǎn)云中選擇具有對(duì)應(yīng)關(guān)系的點(diǎn)對(duì)，計(jì)算源點(diǎn)云到目標(biāo)點(diǎn)云的剛體變換矩陣，將源點(diǎn)云剛體變換后的結(jié)果作為新的源點(diǎn)云，重復(fù)進(jìn)行上述操作，使源點(diǎn)云越來(lái)越靠近目標(biāo)點(diǎn)云，直到兩組點(diǎn)云數(shù)據(jù)之間滿(mǎn)足距離度量準(zhǔn)則下的最優(yōu)匹配。點(diǎn)云配準(zhǔn)的目的是找到從源點(diǎn)云到目標(biāo)點(diǎn)云的變換矩陣，使得誤差E最小，記：

式中：n為源點(diǎn)云與目標(biāo)點(diǎn)云中對(duì)應(yīng)點(diǎn)數(shù)目； pi=(xi, yi, zi)，為代表源點(diǎn)云中的點(diǎn)；qi=(xi, yi, zi)，為目標(biāo)點(diǎn)云中的點(diǎn)；pi∈p，qi∈q，p?P，q?Q。

記源點(diǎn)云與目標(biāo)點(diǎn)云的質(zhì)心分別為：

由源點(diǎn)云到目標(biāo)點(diǎn)云的變換關(guān)系知:

對(duì)H進(jìn)行奇異值分解：H=U∑VT，可得最優(yōu)解R*=VUT，其中需滿(mǎn)足H為滿(mǎn)秩，且det(R*)=1的條件。從而可進(jìn)一步得到最優(yōu)解T*：

1.3 點(diǎn)云配準(zhǔn)方法

結(jié)合基于AABB包圍盒的粗配準(zhǔn)和ICP細(xì)配準(zhǔn)算法后，足部模型點(diǎn)云配準(zhǔn)實(shí)現(xiàn)步驟如下。

（1）計(jì)算包含立方體底座在內(nèi)的源點(diǎn)云與目標(biāo)點(diǎn)云AABB包圍盒及其質(zhì)心，計(jì)算包圍盒之間剛體變換初始變換矩陣q0=[R0,t0]T。

（2）提取目標(biāo)點(diǎn)云立方體底座左右兩側(cè)的點(diǎn)，并定義其朝向左右兩側(cè)的法向量分別為left（-1，0，0），right（1，0，0），計(jì)算源點(diǎn)云初始剛體變換后朝向左右兩側(cè)的法向量與與left（-1，0，0），right（1，0，0）之間的夾角 θ，并設(shè)定一個(gè)閾值θ′。若θ＞θ′，則重復(fù)步驟（1）工作，直至夾角小于設(shè)定閾值，則足部模型點(diǎn)云粗配準(zhǔn)工作結(jié)束。

（3）采用點(diǎn)云分割方法去掉立方體底座，ICP最近點(diǎn)迭代方法，對(duì)待配準(zhǔn)點(diǎn)云進(jìn)行配準(zhǔn)，利用SVD奇異值分解方法，計(jì)算源點(diǎn)云與目標(biāo)點(diǎn)云之間的旋轉(zhuǎn)平移矩陣：qs=[Rs,ts]T。

計(jì)算均方根誤差RMS：

設(shè)定均方根誤差閾值ε，若RMS＜ε，則重復(fù)步驟（3），直至滿(mǎn)足收斂條件RMS＜ε。

圖3 鞋子點(diǎn)云預(yù)處理及ROI提取結(jié)果

2 實(shí)驗(yàn)結(jié)果及誤差分析與討論

為驗(yàn)證本文算法的有效性，本文使用旋轉(zhuǎn)機(jī)構(gòu)搭載結(jié)構(gòu)光相機(jī)先后對(duì)鞋子和足部模型進(jìn)行掃描來(lái)采集點(diǎn)云數(shù)據(jù)，通過(guò)對(duì)兩種模型配準(zhǔn)結(jié)果進(jìn)行評(píng)估來(lái)驗(yàn)證本文提出的算法的有效性。圖3所示為依據(jù)本文點(diǎn)云配準(zhǔn)方法對(duì)鞋子采集到的初始點(diǎn)云數(shù)據(jù)，并進(jìn)行預(yù)處理與感興趣區(qū)域（ROI）提取的結(jié)果，圖4所示為提取特征后的法向量計(jì)算結(jié)果，圖5所示為采用本文點(diǎn)云配準(zhǔn)方法，得到的鞋子點(diǎn)云配準(zhǔn)拼接結(jié)果。圖6所示為采用本文點(diǎn)云配準(zhǔn)方法對(duì)足部模型點(diǎn)云配準(zhǔn)拼接后得到的結(jié)果。表1所示為傳統(tǒng)ICP配準(zhǔn)方法和本文方法圍繞足部模型采集的6幅點(diǎn)云數(shù)據(jù)配準(zhǔn)結(jié)果的平均統(tǒng)計(jì)值。

圖4 鞋子點(diǎn)云法向量計(jì)算結(jié)果

圖5 鞋子點(diǎn)云配準(zhǔn)拼接結(jié)果

圖6 足部模型點(diǎn)云配準(zhǔn)拼接結(jié)果

表1 配準(zhǔn)結(jié)果

從圖5、圖6可以看出，本文對(duì)鞋子和足部模型點(diǎn)云有較好的配準(zhǔn)效果。從表1中可以看出，與傳統(tǒng)ICP配準(zhǔn)方法相比，本文算法在配準(zhǔn)精度和配準(zhǔn)速度上均有提高：在配準(zhǔn)精度上提高了54%，在配準(zhǔn)速度上提高了42%，由此可見(jiàn)本文算法對(duì)足部模型點(diǎn)云配準(zhǔn)的有效性。

3 結(jié)束語(yǔ)

足部點(diǎn)云配準(zhǔn)是公安痕跡科學(xué)研究重點(diǎn)研究?jī)?nèi)容之一，其配準(zhǔn)結(jié)果的準(zhǔn)確度會(huì)直接影響后續(xù)模型重建的精度。本文提出了一種先用基于包圍盒進(jìn)行粗配準(zhǔn)再用ICP進(jìn)行細(xì)配準(zhǔn)的配準(zhǔn)方法，并在鞋子和足部模型點(diǎn)云數(shù)據(jù)上進(jìn)行了配準(zhǔn)實(shí)驗(yàn)。與傳統(tǒng)的ICP點(diǎn)云配準(zhǔn)算法相比，本文的算法在配準(zhǔn)速度和精度均有較大的改善，其中對(duì)鞋子點(diǎn)云的配準(zhǔn)速度提高了54%，精度提高了42%，實(shí)現(xiàn)了鞋子和足部模型點(diǎn)云數(shù)據(jù)快速、準(zhǔn)確地配準(zhǔn)。