馬天嬌，葉方堅，韓廣良，劉培勛※

（1.中國科學院長春光學精密機械與物理研究所，長春 130033；2.公安部物證鑒定中心痕跡科學與技術重點實驗室，北京 100038）

0 引言

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

目前國內外研究學者對點云配準都進行了深入的研究，也取得了豐碩的研究成果。常見的點云配準拼接方法主要分為兩大類。

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

另一類點云配準拼接方法就是人工輔助標志點配準方法[10-11]，該方法常用于沒有明顯特征點的物體，當傳感器從不同視角無法對同一點獲取的點云數(shù)據(jù)進行有效識別定位，此時就需要人為在被測物體上添加標志點，進行測量。

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

1 點云配準理論及方法

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

1.1 基于旋轉約束的AABB包圍盒粗配準

1.1.1 AABB包圍盒

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

圖1 包含源點云與目標點云的AABB包圍盒

1.1.2 旋轉約束

旋轉約束是針對AABB包圍盒進行剛性變換時設置的幾何約束。其目的是給粗配準過程中的剛性變換加入收斂條件，當變換后滿足旋轉約束的收斂條件時，則粗配準工作完成。

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

圖2 源點云中的點與目標點云中點的法向量偏差

1.2 ICP最近點迭代

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

式中：n為源點云與目標點云中對應點數(shù)目； pi=(xi, yi, zi)，為代表源點云中的點；qi=(xi, yi, zi)，為目標點云中的點；pi∈p，qi∈q，p?P，q?Q。

記源點云與目標點云的質心分別為：

由源點云到目標點云的變換關系知:

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

1.3 點云配準方法

結合基于AABB包圍盒的粗配準和ICP細配準算法后，足部模型點云配準實現(xiàn)步驟如下。

（1）計算包含立方體底座在內的源點云與目標點云AABB包圍盒及其質心，計算包圍盒之間剛體變換初始變換矩陣q0=[R0,t0]T。

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

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

計算均方根誤差RMS：

設定均方根誤差閾值ε，若RMS＜ε，則重復步驟（3），直至滿足收斂條件RMS＜ε。

圖3 鞋子點云預處理及ROI提取結果

2 實驗結果及誤差分析與討論

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

圖4 鞋子點云法向量計算結果

圖5 鞋子點云配準拼接結果

圖6 足部模型點云配準拼接結果

表1 配準結果

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

3 結束語

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