基于鄰域幾何特征約束的植株三維形態配準方法研究

馬福峰　耿　楠　張志毅

(西北農林科技大學信息工程學院　陜西 楊凌 712100)

?

基于鄰域幾何特征約束的植株三維形態配準方法研究

馬福峰耿楠*張志毅

(西北農林科技大學信息工程學院陜西 楊凌 712100)

為提高不同角度多次測量得到的植株點云配準速度和精度，提出一種基于植株點云鄰域幾何特征約束改進的三維形態配準方法。首先，針對點云量大并缺少拓撲信息，選取關鍵點集并估計其中每個點的支撐鄰域來擬合出支撐曲面，進一步計算出鄰域幾何特征。其次,采用特征相似度的方法實現點云的初始配準。最后，在初始配準的基礎上，加入兩個新的夾角幾何特征約束匹配點對改進ICP算法進行配準優化。利用bunny、兵馬俑模型點云對算法的精度和通用性進行測試，并在實際應用中驗證了配準效果和算法魯棒性。結果表明，與傳統的特征配準方法相比，該方法配準速度提高約10%以上，精確配準誤差約為傳統算法誤差的1%。

三維形態配準幾何特征特征相似度迭代最近點算法

0　引　言

虛擬植株研究、植株的三維形態重構以及植株三維形態可視化是當前國內外農業生成信息化研究的重點領域。為了能夠獲得植株完整的三維形態的點云模型，三維形態的配準也成為了熱門的研究領域。近年來，由于物體的表面特征在配準過程中表現出的優勢，基于特征的配準方法越來越受到重視。在特征配準中主要是搜索有效的匹配特征點對，當前用于相應匹配點尋找問題的方法旨在減少用來尋找匹配點的點對數量：(1) 通過在數據點集中采樣；(2) 使用特征提取方法[1,2]。準確快速獲取特征點對成為基于特征三維形態配準算法研究的重點。

三維形態配準一般包括初始配準和精確配準。針對初始配準算法，研究者利用不同的幾何特征做了大量的研究。Zhang等[3]利用點云中心提出中心重合法。羅先波[4]和吳敏[5]等通過在模型表面添加標簽來突出其特征，提出標簽法。戴靜蘭等[6]利用每片點云三維形態坐標在空間中擬合曲面的法向量作為點云的主方向，并根據該幾何特征構造坐標系，提出主方向貼合方法。Diez[8]等分別利用點云的曲率和法向提出基于輪廓線法和利用分層的法向空間采樣的方法實現點云初始配準。Dai等[9]也提出基于局部幾何特征來完成初始配準。綜上，現有的初始配準主要采用基于幾何特征的配準，主要包括以下步驟：(1) 提取待配準點集的幾何特征；(2) 根據幾何特征相似性確立匹配點對；(3) 根據建立的對應關系計算坐標變換參數，并進行初始配準。

常用的精確配準方法是由Besl等[10]和Chen等[11]提出的迭代最近點ICP(Iterative Closest Point)算法，但是經典的ICP算法計算效率低，并且其配準過程是一個迭代收斂的過程，算法的效率受點云初始位姿的約束，也容易陷入局部最優[12,13]。由于它的突出優點，ICP算法又非常具有吸引力，因此國內外研究者在ICP算法基礎上，通過引入幾何特征來改進算法，并做了大量工作。Chen和Mediomni等[14]提出了用點云的切平面來逼近點云，該方法選取了點到匹配點處的切平面的距離來代替點到點的距離，但是該算法速度較慢，并且物體表面變化明顯時會影響收斂。Du等[15]首先通過ICA(Independent Component Analysis)獲得點云初始位置，并把放射變換和原始ICP相結合提出放射ICP(Affine ICP)算法。Zhu等[16]提出一個基于雙向距離場的配準算法。Jiang等[17]提出了一種基于夾角的點云配準方法，它通過選擇點云中的任意點與其鄰近點法向之間的夾角作為配準的幾何信息，但是，選取特征不明顯的點估計法向時可能受到噪聲的干擾。Du[18]提出了一種新的局部幾何特征描述子“放射形狀分布”來表達每個點和它的鄰域的隨機空間劃分，該方法在點集中存在較大的離異值和丟失點的情況下能夠檢測到對應點對，并求得潛在的點云間坐標變換。但是，該方法對位姿抖動敏感。當然也有很多研究者從不同的最優策略出發，在試探性的變換下應用一個目標函數測量待拼接點云的不同。Myronenko[19]提出了相關點漂移算法(CPD)，該方法使用一個點集來表達高斯混合模型，并且把點云配準問題轉換為擬合模型到點集的問題。類似的，魯棒的點云配準方法(RPM-GMM)[20]使用高斯混合模型來最小化兩個點集之間的距離。盡管這些方法在許多應用中很成功，但是，如果在點集中離異值和噪聲點占得比例過大，這些方法的性能將會嚴重退化[21]。以上算法主要應用于工業和醫學領域，并且都是在盡量減少配準過程中的迭代次數。

由于存在樹枝之間的交叉和遮擋的影響，不同角度獲得的植株點云結構比較復雜。本文通過對目前三維形態配準方法的分析，并結合植株點云的特征對ICP算法做了以下改進研究：

首先，在初始配準過程中，在選取點云中關鍵點集的基礎上，擬合關鍵點集的點的鄰域曲面計算出幾何特征，提出了一種新的幾何特征相似度度量函數。根據特征的相似度建立特征匹配點對，并計算變換矩陣實現點云的初始配準，能夠快速縮小平移旋轉錯位。

其次，在精確配準的過程中，通過加入兩個相鄰匹配點與初始配準后坐標系原點組成的矢量之間的夾角，以及匹配點法向之間的夾角兩個幾何特征來改進ICP算法，以提高配準的速度和精度。本文方法不需要在測體表面做標記信息，僅通過估計點云自身隱含的幾何特征就能夠實現點云的精確配準，并且對點云初始位置沒有要求。

1　基于幾何特征植株三維形態配準方法

三維掃描儀在不同的視角獲得物體點云的過程中存在著旋轉和平移錯位，因此不同視角下的點云在兩套坐標系下點坐標的測量值間存在誤差。使用最小二乘方法對誤差進行求解建模，能夠計算出誤差最優解[6,10]。基于鄰域幾何特征約束的植株三維形態配準方法是由鄰域幾何特征的估計和提取、初始配準和精確配準組成。在初始配準過程中通過特征相似度建立匹配點之間的對應關系。

1.1特征點集提取和特征估計

根據獲得的點云鄰域，為了方便提取空間中的三維點云數據的幾何特征[1]，由于在不同局部坐標系下獲得物體的點云中特征點之間的相互位置和拓撲關系并沒有改變，利用這種空間特征的拓撲不變性就可以找到匹配的特征點對。

點云的鄰域特征主要包括鄰域點數量、鄰域質心、點位于鄰域的法向和曲率。其前三個特征是比較明顯的，且較容易計算。法向和曲率在消除錯誤匹配點對和搜索最佳匹配對中發揮重要作用。對于散亂的點云數據，使用最小二乘擬合方法求解法向量和曲率的速度快，且抗干擾性強。本文使用擬合曲面來獲得法向量[22,23]。為了適應不同曲面的局部形狀要求，根據文獻[24,25]利用最小二乘擬合曲面求解曲率，用二次曲面來表征局部區域，用式(1)-式(4)來計算每個點處的主曲率k1、k2、平均曲率H及高斯曲率K：

(1)

(2)

(3)

(4)

此方法計算得到的曲面法矢量的方向具有不一致性，法向方向的不一致影響到曲率計算和消除錯誤匹配對，因此需要對不協調的法向進行調整。本文使用了Hoppe等[26]提出的“法向傳播思想”處理法向方向不一致問題。然后，進一步計算得到曲面的第一和第二基本量L=fxxn，N=fyyn，M=fxyn，E=fxfx，F=fxfy，G=fyfy，代入式(1)-式(3)，其中：fx、fy、fxx、fyy、fxy是曲面的偏微分。

1.2基于特征相似度的匹配點對確立以及加權采樣

1.2.1加權采樣

首先對于曲面不規則的模型都有凸起的區域，這部分區域更有利于特征的提取。本文為了方便提取點云數據特征，對曲面的凸點和凹點加以定義，并去除影響配準精度的凹點，如圖1所示。

圖1　p是鄰域內的點，q是鄰域重心，n為點處的法向

1.2.2特征相似度定義

(5)

本文利用距離函數對每個配準點對進行特征相似度的度量。利用該點的支撐鄰域構造該點的特征空間來做兩點之間的相似性的判定，該空間是包含所有特征點的高斯曲率均值、平均曲率均值、兩個主曲率的均值、法向量夾角的均值的5維空間。

(6)

1.3初始配準

改進初始配準算法步驟如算法1所示。

算法1改進的三維點云數據初始配準算法

輸入：

P={pi∈R3}:目標點云數據集。

Q={qi∈R3}: 參考點云數據集。

算法

1: for p∈{pi}do

2: Nk=operaNear(p)and ci=center(Nk)

3: 對每個支撐域擬合曲面，計算主曲率k1、k2、高斯曲率K、平均曲率H、法向n。

4: end for

10: end for

11: 根據特征相似度進一步確立特征匹配點，

12: 進一步使用四元數法計算坐標變換矩陣R和T。

13：將坐標變換矩陣R和T代入三維目標數據點集，完成初始配準。

輸出：

1.4精確配準

算法2改進后精確配準ICP算法

輸入：

Z=[3,9,12,16,50,100,180]

V=φ

算法：

1:for zi∈Zdo

2:while ((dk-dk+1)<γ)

3:for p∈FirPfdo

5:end for

7:if((sinφ<τ1)&&(sinθ<τ2)&&(|cosφ-cosθ|<τ3))

8:if(V.num

10:end if

11:end if

12:if FirPf和FirQf配準誤差太大

13:估算變換Tran(R,T)=[QR|QT]T，使得誤差趨于最優：

14:應用變換：FirQf(l+1)=Tran(R,T)·FirQf(l)，

15:else

16:stop

17:end if

18:對目標點集應用變換，完成精確配準。

圖2　初始配準后兩個幾何特征

19:end while

20:end for

輸出：配準后的點云。

本文通過加入φ和θ這兩個特征來改進ICP迭代的過程，根據判斷這兩個特征來進一步優化匹配點對，提高ICP算法的效率。將該方法稱為改進的ICP算法，如圖2所示。

2　實驗分析

本實驗使用斯坦福大學[27]計算機圖形實驗室提供的bunny的標準三維點云以及自制設備[28]實際測量兵馬俑模型和植株獲得的點云。圖3是不同視角下獲得的點云，其中圖3(a)中點云有40 225個三維點，圖3(b)中點云有40 096個三維點，圖3(c)中點云有90 678個三維點，圖3(d)中點云有104 748個三維點，圖3(e)、(f)為從不同側面獲得植株模型點云，包含116 386個三維點。實驗環境為：系統為Win7，CPU為Intel(R)Core(TM)2.67 GHz，內存為4.00 GB，軟件：Microsoft Visual Studio 2010+OpenGL，語言：C++。實驗的閾值設定。本文所選取的閾值為：τ1=0.1,τ2=0.2,τ3=0.005，α的值為0.6，考慮到實際點云難以完全滿足該約束條件，閾值的選取可以根據實際情況做相應的微調。

圖3　不同角度獲得的點云

2.1算法對比試驗

本實驗結合四種算法進行對比實驗:1) 采用傳統的初始配準算法[6]；2) 經典的ICP算法配準[10,11]；3) 傳統初始配準+經典ICP算法[6]；4) 本文提出的算法。為了進行對比，同一組點云被用來作為輸入。配準結果如圖4所示，配準誤差和效率如表1所示。

圖4　不同算法點云配準效果比較

算法配準誤差d/mm運行時間/s傳統初始配準算法6．0132489．43經典ICP算法3．40153258．57初始配準+經典ICP算法1．2036542．14改進初始配準+改進ICP算法0．0124838．46

可以看出：經典ICP算法沒有優化點云的初始位置，出現了局部最優的狀況，導致配準的精度較低，配準的速度也較慢。本文算法由于在配準之前提取了關鍵點，并且對點集進行了加權抽樣和配準對的優化，減少了配準的數量，即使增加了計算量，計算的時間復雜度也大大降低，同時精度也得到了提高。

2.2不同匹配點對的對比試驗

據本文算法設置Z=[3,9,12,16,50,100,180]，得到相應的匹配點對，并根據不同的匹配點對計算變換進行配準。經過對Stanford大學提供的點云數據進行試驗，驗證了該算法在不同特征點對下的配準效果，如圖5所示。由表2分析可以看出，只要有三個正確的匹配點就足以計算出最優變換，隨著點對的增加，其配準誤差變化不大，但是其配準耗時卻隨著點對的增加不斷增加。

圖5　bunny不同匹配點對下配準效果對比圖

匹配點對數配準誤差d/min運行時間/s30．0134736．2390．0124838．46120．0124240．01160．0114342．56500．0104167．311000．0091370．181800．0091190．54

圖5(a)所示為原始點云的位姿，圖5(b)為使用3對匹配點對情況下配準后的位姿，可以看出，雖然有一定的效果，但是存在偏差，兩片點云沒有完全重合。圖5(c)、(d)是分別在9和12對匹配點下進行的實驗，達到了良好的配準效果。圖5(e)、(f)、(g)是分別在50、100和180對匹配點下進行的配準，與(c)、(d)相比配準效果相差不大，不過增加匹配點數在一定程度上增加了配準的魯棒性。圖5(h)是在沒有提取特征點情況下的配準效果圖，與其相比可以反映出本文所提出的算法的性能。

2.3在噪聲環境下不同匹配點對的對比試驗

為說明該算法的抗噪性能，本實驗仍然設置Z=[3,9,12,16,50,100,180]，并在相同的實驗環境下對含有噪聲的兵馬俑模型的點云數據進行配準，如圖6所示。配準耗時和配準誤差如表3所示。

圖6　兵馬俑模型的含噪聲點云數據不同匹配點對下配準效果對比圖

匹配點對數配準誤差d/mm運行時間/s30．0544840．3190．0513246．23120．0504249．05160．0494353．41500．0404183．211000．0401391．231800．04001113．53

結合圖5和圖6(b)，分析表2和表3可知，特征點對的增加可以提高該算法的抗噪性，但是隨著特征點的增加，配準偏差逐漸趨于平穩，表明算法具有抗噪性。噪聲對配準誤差變化趨勢和收斂時間影響如圖7所示。

圖7　不同匹配點對下配準耗時和誤差變化趨勢圖

2.4在植株點云模型中的應用

為進一步說明該算法在模型配準中的應用，本文選取由自制設備獲得的植物模型點云數據和由昆士蘭大學提供的樹的點云模型進行配準測試。圖8(a)、(b)、(c)、(d)、(e)、(f)為自制設備獲得點云配準效果圖，圖8(g)、(h)為昆士蘭大學提供的點云進行配準實驗的效果圖。通過對兩組模型的配準分析，驗證了該算法對大多數點云模型配準的有效性和通用性。

圖8　植株點云模型配準效果

3　結　語

本文提出的特征相似度度量函數方法實現的初始配準和基于夾角幾何特征的改進ICP算法的精確配準相結合，能夠快速消除三維形態之間的惡旋轉和平移錯位。本文首先使用標準點云模型測試了算法的效率和精度，最后實際應用到植株的點云模型中。實驗結果表明，該算法能夠對植株三維形態進行很好的配準。對于含有約4萬個數據點的兩片點云進行配準，該算法與傳統初始配準方法相比速度提高了約50%，與經典ICP算法相比多次測量平均速度約提高了80%，以及與其他改進的ICP方法相比速度約提高了11.95%，配準誤差近似。因此該方法在配準的精度和速度上都有了提高，具有實際的應用價值。

[1] Basdogan C,Oztireli A C.A new feature-based method for robust and efficient rigid-body registration of overlapping point clouds[J].The Visual Computer,2008,24(7):679-688.

[2] Yang H J,He D J.A simplified and accurate registration for splat-based fruit scans[J].ICIC Express Letters,Part B:Applications,2012,3(4):733-741.

[3] Zhang X C,Xi J T,Yan J Q.Research on digital measurement technology based on point cloud data of complex surfaces[J].Computer Integrated Manufacturing Systems,2005,11 (5):727-731,737.

[4] 羅先波,鐘約先,李仁舉,等.三維掃描系統中的數據配準技術[J].清華大學學報:自然科學版,2004,44(8):1104-1106.

[5] 吳敏,周來水.測量點云數據的多視拼合技術研究[J].南京航空航天大學學報,2003,35(5):552-557.

[6] 戴靜蘭,陳志楊,葉修梓,等.ICP算法在點云配準中的應用[J].中國圖象圖形學報,2007,12(3):517-521.

[7] Wang Z,Geng N,Zhang Z.Surface mesh reconstruction based on contours[C]//proceedings of the 2009 International Conference on Computational Intelligence and Software Engineering.CiSE 2009,December 11,2009-December 13,2009,Wuhan,China,F,2009,IEEE Computer Society.

[8] Diez Y,Marti J,Salvi J.Hierarchical normal space sampling to speed up point cloud coarse matching[J].Pattern Recognition Letters,2012,33(16):2127-2133.

[9] Dai J J,Yang J.A novel two-stage algorithm for accurate registration of 3D point clouds[C]//International Conference on Multimedia Technology,2011:6187-6191.

[10] Besl P J,Mckay N D.A method for registration of 3d shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256.

[11] Chen Y,Medioni G.Object modeling by registration of multiple range images[J].Image and Vision Computing,1992,10(3):145-155.

[12] Xie Z X,Xu S,Li X Y.A high-accuracy method for fine registration of overlapping point clouds[J].Image and Vision Computing,2010,28(4):563-570.

[13] Liu Y H.Constraints for closest point finding[J].Pattern Recognition Letters,2008,29(7):841-851.

[14] Chen Y,Medioni G.Object modeling by registration of multiple range images[C]//Robotics and Automation,1991 IEEE International Conference on.IEEE,1991:2724-2729.

[15] Du S Y,Zheng N N,Ying S H,et al.Affine iterative closest point algorithm for point set registration[J].Pattern Recognition Letters,2010,31(9):791-799.

[16] Zhu J,Du S,Yuan Z,et al.Robust affine iterative closest point algorithm with bidirectional distance[J].IET Computer Vision,2012,6(3):252-261.

[17] Jiang J,Cheng J,Chen X L.Registration for 3-Dpoint clouds using angular-invariant feature[J].Neuro Computing,2009,72(16-18):3839-3844.

[18] Du J,Xiong W,Chen W,et al.Multi-view Point Cloud Registration Using Affine Shape Distributions[M]//Computer Vision--ACCV 2014.Springer International Publishing,2014:147-161.

[19] Myronenko A,Song X.Point set registration:Coherent point drift[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2010,32(12):2262-2275.

[20] Jian B,Vemuri B C.Robust point set registration using gaussian mixture models[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2011,33(8):1633-1645.

[21] Lian W,Zhang L.Robust point matching revisited:a concave optimization approach[M]//Computer Vision-ECCV 2012.Springer Berlin Heidelberg,2012:259-272.

[22] Joel Daniells,Tilo Ochotta,Linh K,et al.Spline-based feature curves from point-sampled geometry[J].The Visual Computer,2008,24(6):449-462.

[23] Guan Y L,Cheng X J.A robust method for fitting a plane to point clouds[J].Joural of Tongji University:Natural Science,2008,36(7):982.

[24] Chen Z Q,Wang Y Z,Li B,et al.A survey of methods for moving least squares surfaces[C].Symposium on Point-Based Graphics 2008.Los Angeles:EG&VGTC,2008:9-23.

[25] 朱延娟,周來水,張麗艷.散亂點云數據配準算法[J].計算機輔助設計與圖形學學報,2006,18(4):475-481.

[26] Hoppe H,DeRose T,Duchamp T,et al.Surface reconstruction from unorganized points[J].ACM Siggraph Computer Graphics,1992,26(2):71-78.

[27] The Stanford 3D Scanning Repository[EB/OL].Stanford University Computer Graphics Laboratory.[2003-04-01].http://www.graphics.stanford.edu/data/3Dscanrep/.

[28] Zhang Z Y,Yuan L.Build A 3D Scanner System Based on Monocular Vision[J].APPLIED OPTICS,2012,51(11):1638-1644.

ON 3D PLANT MORPHOLOGY REGISTRATION METHOD BASED ON GEOMETRICAL FEATURE CONSTRAINT OF NEIGHBOURHOOD

Ma FufengGeng Nan*Zhang Zhiyi

(College of Information Engineering,Northwest Agricultural and Forest University,Yangling 712100,Shaanxi,China)

In order to improve the registration speed and precision of plant point cloud derived from multiple measurements in various angles, this paper proposes an improved 3D morphological registration method which is based on the geometrical feature constraint of neighbourhood of plant point clouds. First, aiming at the large amount of point clouds and lack of topological information, the method estimates the support neighbourhood of each point by selecting key point set to fit the support surface and then to further compute the geometrical feature of neighbourhood. Secondly, it employs the feature similarity method to implement the initial registration of point clouds. Finally, based on initial registration it adds two matching pairs of angle’s geometric feature constraints to improve the iterative closest point (ICP) algorithm and to optimise the registration. We tested the accuracy and universality of the algorithm with the point clouds of bunny and Terracotta Army models, and verified in practical application the effect of registration and the robustness of the algorithm. Results showed that compared with traditional feature-based registration method, the proposed method increased the registration speed about over 11.9%, and the error of precise registration was about 1% of that of the traditional feature-based algorithm.

3D morphology registrationGeometrical featureFeature similarityICP algorithm

2015-05-21。國家高技術研究發展計劃項目(2013AA 102304)；基本科技創新一般項目(QN2013056)；科技創新一般項目(2014YB067)。馬福峰，碩士，主研領域：計算機虛擬技術與圖形學。耿楠，教授。張志毅，副教授。

TP391.41

A

10.3969/j.issn.1000-386x.2016.09.044