二維點輪廓與矢量輪廓配準研究

黃 方， 寧 濤， 陳志同， 沈云超

(北京航空航天大學機械工程及自動化學院，北京 100191)

二維點輪廓與矢量輪廓配準研究

黃 方， 寧 濤， 陳志同， 沈云超

(北京航空航天大學機械工程及自動化學院，北京 100191)

在平面類零件的光學測量中，二維點輪廓與矢量輪廓的配準是關鍵算法，配準精度直接影響測量精度。針對平面類零件的配準問題，提出了基于形狀特征函數的粗配準算法和二維矢量最近點迭代(ICP)精配準算法。利用角度距離圖法將矢量圖形的幾何信息轉化為獨立于坐標系的連續函數，進而實現粗配準算法?；谄矫嫔宵c與曲線的最近距離算法計算配準目標函數，給出了不同于傳統的ICP算法的直接求解目標函數的解析方法，有效提高了算法效率。利用實例驗證分析了該算法的高效性和可靠性。

二維矢量圖形；二維點云；粗配準；精配準；最近點迭代算法

平面類零件的制造過程中存在誤差，如何快速測量零件的尺寸，并與加工的數據進行對比，得到加工誤差，對判斷加工的正確性以及提高加工效率至關重要。受測量工具和測量者的影響，傳統的人工測量方法效率低，而且可能對零件造成損傷。三坐標測量儀的效率會隨著測量點數的增加而下降，點數多的情況下耗時也多。使用光學測量的方式能夠很快獲取零件的輪廓圖，進而實現快速的尺寸測量與對比。英國Inspect Vision公司的Planar視覺檢測系統就使用了這種測量手段，

采用超高分辨率的成像系統，瞬間獲取零件的測量數據，通過計算機處理，生成零件的實際點輪廓圖，與零件的CAD圖形進行對齊，顯示各部位的尺寸偏差，從而獲取零件的加工精度。在尺寸的測量和對比過程中，需要實現零件的點輪廓圖和加工CAD圖的對齊，這個處理叫做配準。配準是一個帶有約束條件的最優化問題，是在平移和旋轉組成的剛體變換的約束下達到最佳對齊。元素可以是曲面、點云以及二維矢量圖形。配準分為粗配準和精配準兩步。通過粗配準使得待配準元素近似對齊，為精配準提供一個良好的初始位置，精配準在粗配準基礎上通過迭代，逐步逼近最佳對齊。

現階段常用的粗配準方法有：三點對齊法、力矩主軸法、遺傳算法、最小包圍盒法以及標簽法等。張學昌等[1]提出了三點對齊法進行粗配準，簡單直觀快速。力矩主軸法也被用來解決粗配準問題[2]。嚴慶光等[3]使用了遺傳算法實現粗配準。劉斌等[4]使用了最小包圍盒算法。標簽法則是在測量時提前設置一些特征點，然后在配準時使用這些特征點[5]。

Besl和 Mckay[6]提出的最近點迭代(iterated closest point，ICP)算法被廣泛應用于解決精配準問題。傳統的 ICP算法有配準精度上的保證，但其效率不高，所以出現了很多改進的 ICP算法。改進的 ICP算法主要有以下幾方面：點對的選取，距離度量的選取和搜索策略的選取[7]。傳統的ICP算法每次迭代計算使用全部的點。為了減少每次迭代中用于計算的點，需要對配準元素進行采樣，Turk和Levoy[8]使用了一致采樣方法，Masuda等[9]使用的是隨機采樣方法。傳統的 ICP算法把點到點的歐氏距離當作特征度量。Chen和 Medioni[10]利用的是測量點集中的點的法線與模型點集合的交點來確定對應點，得到對應點后，目標函數則采用的是點到面的距離。在對應點的選取，也就是構造各對應點的過程中，需要進行大量的搜索，時間復雜度為O(NcNx)，其中Nc為測量點集中點數目，Nx為模型點集中點數目。這是傳統ICP算法在配準效率上的瓶頸。Zhang[11]采用了多維二元搜索樹(K-D Tree)，使得時間復雜度降為O(NclogNx)。Jost和Hügli[12]提出了鄰域搜索策略，時間復雜度為O(Nc)。蔣睿嵩等[13]根據配準模型中不同區域的重要性不同，引入權值約束，實現模型的高精度配準。王森等[14]通過引入稀疏度對模型進行配準優化，避免了局部對齊，提高了算法的穩定性和精確度。

已有算法是針對三維模型的配準，為了解決二維點輪廓與矢量輪廓的配準問題，本文提出一種二維粗配準算法以及一種二維快速 ICP算法。在粗配準階段，根據點云和矢量圖形內部相似的距離信息提出一種基于中心的角度距離圖的粗配準算法，將幾何形狀映射為連續的周期函數，實現精度較高的粗配準。在精配準階段，以點到曲線的距離為特征度量，以點與點到曲線的距離最近點為特征點對，以平移向量和旋轉角度為目標，給出了一種解析求解方法，實現了二維ICP算法。其算法因為特征度量的選取以及目標參數的直接求解，在保證配準精度的基礎上配準速度得到了極大提高。本文研究算法兼顧速度和精度，可應用在實際的平面零件檢測中。

1 粗配準

針對二維配準的待配準元素做一些介紹，二維矢量圖形是一個二維CAD圖形，二維點云是根據二維矢量圖形加工出來的平面零件經過成像以及輪廓提取之后得到的點輪廓?？煞QCAD圖形的最外一環為二維矢量圖形的外輪廓，其余部分稱之為內輪廓，相應的點云中的最外一圈叫二維點云的外輪廓，其余部分稱之為內輪廓。在粗配準時主要使用外輪廓的信息。

粗配準需要找二維點云和二維矢量圖形的平移變換和旋轉變換。先確定二維點云中心以及二維矢量圖形中心的概念：以二維點云外輪廓所有點坐標的平均值為二維點云中心的坐標值；依據二維點云外輪廓點的數目對二維矢量圖形外輪廓進行均勻離散處理，得到矢量圖形外輪廓的點云，以矢量圖形外輪廓的點云中所有點坐標的平均值為二維矢量圖形中心的坐標值。對于平移變換，可以通過平移使得二維點云和二維矢量圖形的中心重合來求取平移矢量。對于旋轉變換，可以使用二維點云和二維矢量圖形外輪廓的幾何信息。二維矢量圖形的旋轉只與一個角度有關，因此可以考慮通過計算旋轉角度來確定旋轉矩陣。本文引入一個角度距離圖的概念：對于一個圖形，求得圖形中心，計算圖形外輪廓上任一點與方向向右的水平線的夾角，計算該點與點云中

心的距離，逆時針掃一周，以角度為自變量，以兩點距離為因變量(如果同一個角度存在多個點，則取最遠點計算距離)，得到一個角度距離圖。如圖1、2所示。

圖1 輪廓曲線1

圖2 角度距離圖(一周)

對于兩個只需做旋轉變換的圖形，旋轉角度就是兩個角度距離圖的相位角。在外輪廓為非旋轉對稱圖形時兩個角度距離圖曲線只相差一個相位角，而這個相位角就是旋轉角度。在計算相位角時，采用最小二乘法，設置角度 θ，計算 θ在[0°,360°]變化時兩個角度距離圖對應角度的距離差的平方和。平方和最小的情況下，兩個點云的角度距離圖最佳對齊，得到的θ為所求得相位角。如圖3~5所示。

圖3 輪廓曲線2

圖4 角度距離圖(兩周)

圖5 相位角

在二維矢量圖形的外輪廓為非旋轉對稱圖形的情況下，稱二維點云外輪廓部分為待配準點云，二維矢量圖形外輪廓經過離散后得到的點云為模型點云。在實際求取角度距離圖時的操作為：模型點云的角度計算范圍是[0°,360°]，待配準點云的角度計算范圍是[0°,720°]。計算相位角時待配準點云與模型點云對應點的角度差為上文提及的θ。角度距離圖法的流程圖如圖6所示。

圖6 角度距離圖法流程圖

當二維矢量圖形的外輪廓為非圓的旋轉對稱圖形時，使用角度距離圖法求得旋轉角度之后旋轉測量點云，外輪廓雖對齊，但內輪廓可能沒有對齊，如圖7所示。

圖7 特殊情況

所以需要做進一步判斷與處理。當二維矢量圖形的外輪廓為非圓的旋轉對稱圖形時，求出各旋轉角，在使用角度距離圖法粗配準的基礎上，再比較以各旋轉角做旋轉變換的內部輪廓的對齊效果，選擇最佳的旋轉角度。

對齊效果的判斷標準：稱二維矢量圖形外輪廓內部的封閉輪廓為矢量圖形的內輪廓，稱測量點云外輪廓內部的任一圈點云為測量點云的內輪廓，每一個內輪廓與外輪廓中心點的求法一致。求矢量圖形每一個內輪廓中心點到所有測量點云內輪廓中心點中最近的中心點的距離，將所有距離加起來，得到一個距離值，距離值最小的情況即為最佳的對齊效果。

如果二維矢量圖形的外輪廓為圓，內輪廓與外輪廓的對齊沒有關系，所以角度距離圖法失效?？梢酝ㄟ^比較，0°~360°每一個角度逐步旋轉時內部輪廓的對齊效果，選擇最佳的旋轉角度。

2 精配準

傳統 ICP算法實現點云配準的基本思路是：假設兩個點云P和M近似對齊，對于P中任一點，稱M中的距離最近點為其對應點。在M中搜索P中任一點的對應點，得到點云X，計算P到X的剛體變換。進行迭代，直到滿足要求或者達到最大迭代次數。假設P中點數目為Nc，pi為P中的點，mi為M中的點，所求的旋轉變換為，所求平移變換為，則傳統ICP算法的目標函數為

目標函數的求解主要有兩種：①需要求解矩陣的特征值和特征向量，稱之為為四元數方法；②需要進行矩陣奇異值分解，稱之為SVD分解法。

本文的二維 ICP算法針對二維點云與二維矢量輪廓圖。通過求取點到曲線的最近距離點來確定對應點對，本文處理二維的幾何元素，在算法上做了一些簡化，以平移矢量和旋轉角度 3個變量為求解參數建立目標函數，可以使用解析方法直接求解方程。

二維ICP算法步驟如下：

步驟1. 設定參考數據集和目標數據集；

步驟2. 對目標數據集中的每個點，在參考數據集中尋找一個與之對應的最短距離的點；

步驟3. 建立匹配目標函數，對目標函數進行優化，求出目標函數最優解，得到新的目標數據集；

步驟4. 進行誤差分析，若滿足誤差條件或達到最大迭代次數則轉至步驟 5，否則，轉至步驟2；

步驟5. 配準結束。

在求解變換這一步，先建立匹配目標函數，再對目標函數進行優化，求出目標函數最優解，從而得到新的目標數據集。以下是建立目標函數的過程：

其中，θ、b1、b2為待定系數；為旋轉矩陣；為平移向量。

求解待定系數θ、b1、b2，使得f最小。

下面為目標函數的求解過程

對這3個方程進行求解，由式(1)可得

由式(2)可得

由式(3)可得

從而可得

將式(9)代入式(5)、式(6)可求b1、b2，得到θ、b1、b2的值，代入到方程

中可以得到新的目標數據點。

3 算法分析和實例驗證

粗配準階段的角度距離圖法幾何依據明確，主要使用外輪廓信息，對數據信息的部分缺失不敏感；計算簡單直接，在保證配準的正確性的基礎上耗時少，若測量點云數目為 Nc，則角度距離圖法的時間復雜度為O(Nc)；同時配準精度可以自主控制和調整，可以達到 1°甚至更精確。角度距離圖法有兩個缺點：①在矢量圖形外輪廓為圓時失效；②在矢量圖形外輪廓為旋轉對稱圖形時，角度距離圖法不能給出最終的結果，還要做后續的比較才能得到最終的結果。

精配準階段的二維快速 ICP算法在尋找最近點這一步，采用求取點到曲線段的最近距離點來確定對應點對的策略，可以大大降低搜索最近點的時間復雜度，提高效率。測量點云數目為 Nc，矢量圖形曲線段數目為N，時間復雜度為O(Nc)。對于測量點云數目為Nc，模型點云數目為Nx的情況，傳統的 ICP算法搜索最近點的時間復雜度為O(NcNx)。同時原始的ICP算法，不能直接求取旋轉矩陣和平移矩陣，需要使用四元數來表示旋轉矩陣，再根據旋轉矩陣求平移矩陣。目標函數的求解需要本文二維 ICP算法直接以旋轉角度和平移分量為參數建立目標函數，原理清晰，形式簡單，可以使用解析方法求解參數。二維快速 ICP算法適用于處理二維點云與二維矢量圖形的配準，無法處理三維的配準，也不適合二維點云與二維點云的配準。

下面給出驗證實例，其中根據矢量圖形的外輪廓對稱情況分為3類：外輪廓不對稱、外輪廓為旋轉對稱圖形和外輪廓為圓。配準誤差是指配準后點

輪廓上點到矢量輪廓上對應點的距離的平均值。

所用計算機配置：處理器為 Inter Core i3-3240，CPU為3.40 GHz，內存4 GB。例子中黑色部分圖形為平面零件的矢量圖形，紅色部分圖形為點輪廓圖。

實例1. 圖形內輪廓一樣，外輪廓不一樣。根據外輪廓分為5種情況。

情況1. 圖形外輪廓不對稱之一(圖8)。

圖8 外輪廓不對稱之一

情況2. 圖形外輪廓不對稱之二(圖9)。

圖9 外輪廓不對稱之二

情況3. 圖形外輪廓為旋轉對稱之一(圖10)。

圖10 外輪廓旋轉對稱之一

情況 4. 圖形外輪廓為旋轉對稱之二(圖11)。

圖11 外輪廓旋轉對稱之二

情況5. 圖形外輪廓為圓(圖12)。

圖12 外輪廓為圓

以上5種配準情況的配準信息如表1所示。

表1 實例1配準信息

由表1數據可知，當外輪廓為非圓的圖形時，粗配準耗時很少，各情況下相差也極小，外輪廓為圓時，粗配準耗時增加，與之前的情況有接近10倍的差別，由此可確認角度距離圖法的有效性。

實例2. 圖形外輪廓一樣，內輪廓不一樣。根據內輪廓數目，分為3種情況。

情況1. 內輪廓數目為8(圖13)。

情況2. 內輪廓數目為16(圖14)。

情況3. 內輪廓數目為25(圖15)。

以上3種配準情況的配準信息如表2所示。

圖13 內輪廓數目為8

圖15 內輪廓數目為25

表2 實例2配準信息

由表2數據可知，相對于傳統ICP算法配準點集耗時較多，二維 ICP算法可稱為快速精配準方法。在實驗結果中精配準時間與點云中點數目的變化情況基本呈現線性的趨勢，驗證點云數目為Nc時，二維ICP算法的時間復雜度為O(Nc)。

4 結 論

(1) 針對二維點云圖形與矢量圖形的配準問題，論文提出了粗配準和精配準方法。在粗配準階段，本文提出的角度距離圖法將矢量圖形的幾何信息轉化為連續的形狀特征函數，此特征函數不依賴于坐標系，為粗配準提供了明確的配準依據。該方法計算量小、精度較高，易于用算法實現，但不足之處是無法解決外輪廓為圓的粗配準。

(2) 在精配準階段，提出了針對點輪廓與矢量輪廓的二維快速ICP算法。該方法基于點/曲線的最近距離算法，極大提高了最近點的搜索效率，用解析方法直接求解本算法的目標函數，無需復雜的矩陣分解算法，即可得到最佳配準。

現有 ICP算法都是基于一種能量法，沒有考慮到配準對象的局部幾何形狀。由于一般平面類零件中大量存在直角、圓等幾何特征，在后續研究中將圍繞點輪廓中的幾何特征提取，以及幾何特征的模糊匹配與配準展開。

[1] 張學昌, 習俊通, 嚴雋琪. 基于擴展高斯球的點云數據與CAD模型配準[J]. 機械工程學報, 2007, 43(6): 142-148.

[2] 黃鏡榮, 李熙瑩. 加快尋優的醫學圖像互信息配準算法的研究[J]. 中山大學學報: 自然科學版, 2005, 44(S2): 174-177.

[3] 嚴慶光, 李明哲, 李東成. 多點成形件檢測中三維數據配準方法的研究[J]. 中國機械工程, 2003, 14(19): 34-37.

[4] 劉 斌, 華順剛, 歐宗瑛, 等. 基于斷骨模型自動配準的完全性骨折鋼板預彎[J]. 光電子·激光, 2009, 20(7): 977-982.

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

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

[7] Rusinkiewicz S, Levoy M. Efficient variants of the ICP algorithm [C]//Proceedings of the Third International Conference on 3D Digital Imaging and Modeling. New York: IEEE Press, 2001: 145-152.

[8] Turk G, Levoy M. Zippered polygon meshes from range images [C]//Conference on Computer Graphics and Interactive Techniques, SIGGRAPH. New York: ACM Press, 1994: 311-318.

[9] Masuda T, Sakaue K, Yokoya N. Registration and integration of multiple range images for 3-D model construction [C]//Proceedings of the 13th International Conference on Pattern Recognition. New York: IEEE Press,1996: 879-883.

[10] Chen Y, Medioni G. Object modeling by registration of multiple range images [C]//Proceedings of IEEE Conference on Robotics and Automations. New York: IEEE Press, 1991: 2724-2729.

[11] Zhang Z Y. Iterative point matching for registration of free-form curves and surfaces [J]. International Journal of Computer Vision, 1994, 13(2): 119-152.

[12] Jost T, Hügli H. Fast ICP algorithms for shape registration [M]. Berlin: Springer, 2002: 91-99.

[13] 蔣睿嵩, 魏發遠, 馮大勇, 等. 一種權值約束的精確配準算法[J]. 圖學學報, 2014, 35(2): 167-172.

[14] 王 森, 王 璐, 洪靖惠, 等. 基于Sparse ICP的三維點云耳廓識別[J]. 圖學學報, 2015, 36(6): 862-867.

Registration of Planar Point Cloud and Vector Graphics

Huang Fang, Ning Tao, Chen Zhitong, Shen Yunchao

(School of Mechanical Engineering and Automation, Beihang University, Beijing 100191, China)

In the optical measuring of planar parts, the registration of 2D point contour and planar vector contour is the key algorithm, the speed and precision of registration has a major impact on the speed and precision of measure result. In order to solve the problem of registration of 2D point cloud, a coarse registration algorithm based on shape feature function and a 2D iterated closest point (ICP) fine registration algorithm are researched. Through the angle-distance graph, geometry information of point contour and planar vector contour is translated to continuous function that is independent of coordinate system. The objective function of registration is calculated on account of nearest distance algorithm on planar point and curve, and analytic method of solving the objective function directly is given, which is different from traditional ICP algorithm. The efficiency of algorithm is improved significantly. Examples are exhibited to analysis the efficiency and reliability of the algorithm.

planar vector graphics; 2D point cloud; coarse registration; fine registration; iterated closest point algorithm

V 260.5; TP 391

10.11996/JG.j.2095-302X.2016050598

A

2095-302X(2016)05-0598-09

2016-03-10；定稿日期：2016-05-03

國家科技重大專項–高檔數控機床與基礎制造裝備科技重大專項課題(2013ZX04011031)

黃 方(1991–)，男，湖南婁底人，碩士研究生。主要研究方向為計算機輔助設計、CAD技術。E-mail：hf501x@163.com

寧 濤(1967–)，男，遼寧丹東人，副教授，博士。主要研究方向為計算機輔助設計、CAD/CAM技術。E-mail：dr.nt@163.com