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

(北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京 100191)

二維點(diǎn)輪廓與矢量輪廓配準(zhǔn)研究

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

(北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京 100191)

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

二維矢量圖形；二維點(diǎn)云；粗配準(zhǔn)；精配準(zhǔn)；最近點(diǎn)迭代算法

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

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

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

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

已有算法是針對(duì)三維模型的配準(zhǔn)，為了解決二維點(diǎn)輪廓與矢量輪廓的配準(zhǔn)問題，本文提出一種二維粗配準(zhǔn)算法以及一種二維快速 ICP算法。在粗配準(zhǔn)階段，根據(jù)點(diǎn)云和矢量圖形內(nèi)部相似的距離信息提出一種基于中心的角度距離圖的粗配準(zhǔn)算法，將幾何形狀映射為連續(xù)的周期函數(shù)，實(shí)現(xiàn)精度較高的粗配準(zhǔn)。在精配準(zhǔn)階段，以點(diǎn)到曲線的距離為特征度量，以點(diǎn)與點(diǎn)到曲線的距離最近點(diǎn)為特征點(diǎn)對(duì)，以平移向量和旋轉(zhuǎn)角度為目標(biāo)，給出了一種解析求解方法，實(shí)現(xiàn)了二維ICP算法。其算法因?yàn)樘卣鞫攘康倪x取以及目標(biāo)參數(shù)的直接求解，在保證配準(zhǔn)精度的基礎(chǔ)上配準(zhǔn)速度得到了極大提高。本文研究算法兼顧速度和精度，可應(yīng)用在實(shí)際的平面零件檢測中。

1 粗配準(zhǔn)

針對(duì)二維配準(zhǔn)的待配準(zhǔn)元素做一些介紹，二維矢量圖形是一個(gè)二維CAD圖形，二維點(diǎn)云是根據(jù)二維矢量圖形加工出來的平面零件經(jīng)過成像以及輪廓提取之后得到的點(diǎn)輪廓。可稱CAD圖形的最外一環(huán)為二維矢量圖形的外輪廓，其余部分稱之為內(nèi)輪廓，相應(yīng)的點(diǎn)云中的最外一圈叫二維點(diǎn)云的外輪廓，其余部分稱之為內(nèi)輪廓。在粗配準(zhǔn)時(shí)主要使用外輪廓的信息。

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

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

圖1 輪廓曲線1

圖2 角度距離圖(一周)

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

圖3 輪廓曲線2

圖4 角度距離圖(兩周)

圖5 相位角

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

圖6 角度距離圖法流程圖

當(dāng)二維矢量圖形的外輪廓為非圓的旋轉(zhuǎn)對(duì)稱圖形時(shí)，使用角度距離圖法求得旋轉(zhuǎn)角度之后旋轉(zhuǎn)測量點(diǎn)云，外輪廓雖對(duì)齊，但內(nèi)輪廓可能沒有對(duì)齊，如圖7所示。

圖7 特殊情況

所以需要做進(jìn)一步判斷與處理。當(dāng)二維矢量圖形的外輪廓為非圓的旋轉(zhuǎn)對(duì)稱圖形時(shí)，求出各旋轉(zhuǎn)角，在使用角度距離圖法粗配準(zhǔn)的基礎(chǔ)上，再比較以各旋轉(zhuǎn)角做旋轉(zhuǎn)變換的內(nèi)部輪廓的對(duì)齊效果，選擇最佳的旋轉(zhuǎn)角度。

對(duì)齊效果的判斷標(biāo)準(zhǔn)：稱二維矢量圖形外輪廓內(nèi)部的封閉輪廓為矢量圖形的內(nèi)輪廓，稱測量點(diǎn)云外輪廓內(nèi)部的任一圈點(diǎn)云為測量點(diǎn)云的內(nèi)輪廓，每一個(gè)內(nèi)輪廓與外輪廓中心點(diǎn)的求法一致。求矢量圖形每一個(gè)內(nèi)輪廓中心點(diǎn)到所有測量點(diǎn)云內(nèi)輪廓中心點(diǎn)中最近的中心點(diǎn)的距離，將所有距離加起來，得到一個(gè)距離值，距離值最小的情況即為最佳的對(duì)齊效果。

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

2 精配準(zhǔn)

傳統(tǒng) ICP算法實(shí)現(xiàn)點(diǎn)云配準(zhǔn)的基本思路是：假設(shè)兩個(gè)點(diǎn)云P和M近似對(duì)齊，對(duì)于P中任一點(diǎn)，稱M中的距離最近點(diǎn)為其對(duì)應(yīng)點(diǎn)。在M中搜索P中任一點(diǎn)的對(duì)應(yīng)點(diǎn)，得到點(diǎn)云X，計(jì)算P到X的剛體變換。進(jìn)行迭代，直到滿足要求或者達(dá)到最大迭代次數(shù)。假設(shè)P中點(diǎn)數(shù)目為Nc，pi為P中的點(diǎn)，mi為M中的點(diǎn)，所求的旋轉(zhuǎn)變換為，所求平移變換為，則傳統(tǒng)ICP算法的目標(biāo)函數(shù)為

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

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

二維ICP算法步驟如下：

步驟1. 設(shè)定參考數(shù)據(jù)集和目標(biāo)數(shù)據(jù)集；

步驟2. 對(duì)目標(biāo)數(shù)據(jù)集中的每個(gè)點(diǎn)，在參考數(shù)據(jù)集中尋找一個(gè)與之對(duì)應(yīng)的最短距離的點(diǎn)；

步驟3. 建立匹配目標(biāo)函數(shù)，對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，求出目標(biāo)函數(shù)最優(yōu)解，得到新的目標(biāo)數(shù)據(jù)集；

步驟4. 進(jìn)行誤差分析，若滿足誤差條件或達(dá)到最大迭代次數(shù)則轉(zhuǎn)至步驟 5，否則，轉(zhuǎn)至步驟2；

步驟5. 配準(zhǔn)結(jié)束。

在求解變換這一步，先建立匹配目標(biāo)函數(shù)，再對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，求出目標(biāo)函數(shù)最優(yōu)解，從而得到新的目標(biāo)數(shù)據(jù)集。以下是建立目標(biāo)函數(shù)的過程：

其中，θ、b1、b2為待定系數(shù)；為旋轉(zhuǎn)矩陣；為平移向量。

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

下面為目標(biāo)函數(shù)的求解過程

對(duì)這3個(gè)方程進(jìn)行求解，由式(1)可得

由式(2)可得

由式(3)可得

從而可得

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

中可以得到新的目標(biāo)數(shù)據(jù)點(diǎn)。

3 算法分析和實(shí)例驗(yàn)證

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

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

下面給出驗(yàn)證實(shí)例，其中根據(jù)矢量圖形的外輪廓對(duì)稱情況分為3類：外輪廓不對(duì)稱、外輪廓為旋轉(zhuǎn)對(duì)稱圖形和外輪廓為圓。配準(zhǔn)誤差是指配準(zhǔn)后點(diǎn)

輪廓上點(diǎn)到矢量輪廓上對(duì)應(yīng)點(diǎn)的距離的平均值。

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

實(shí)例1. 圖形內(nèi)輪廓一樣，外輪廓不一樣。根據(jù)外輪廓分為5種情況。

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

圖8 外輪廓不對(duì)稱之一

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

圖9 外輪廓不對(duì)稱之二

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

圖10 外輪廓旋轉(zhuǎn)對(duì)稱之一

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

圖11 外輪廓旋轉(zhuǎn)對(duì)稱之二

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

圖12 外輪廓為圓

以上5種配準(zhǔn)情況的配準(zhǔn)信息如表1所示。

表1 實(shí)例1配準(zhǔn)信息

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

實(shí)例2. 圖形外輪廓一樣，內(nèi)輪廓不一樣。根據(jù)內(nèi)輪廓數(shù)目，分為3種情況。

情況1. 內(nèi)輪廓數(shù)目為8(圖13)。

情況2. 內(nèi)輪廓數(shù)目為16(圖14)。

情況3. 內(nèi)輪廓數(shù)目為25(圖15)。

以上3種配準(zhǔn)情況的配準(zhǔn)信息如表2所示。

圖13 內(nèi)輪廓數(shù)目為8

圖15 內(nèi)輪廓數(shù)目為25

表2 實(shí)例2配準(zhǔn)信息

由表2數(shù)據(jù)可知，相對(duì)于傳統(tǒng)ICP算法配準(zhǔn)點(diǎn)集耗時(shí)較多，二維 ICP算法可稱為快速精配準(zhǔn)方法。在實(shí)驗(yàn)結(jié)果中精配準(zhǔn)時(shí)間與點(diǎn)云中點(diǎn)數(shù)目的變化情況基本呈現(xiàn)線性的趨勢，驗(yàn)證點(diǎn)云數(shù)目為Nc時(shí)，二維ICP算法的時(shí)間復(fù)雜度為O(Nc)。

4 結(jié) 論

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

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

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

[1] 張學(xué)昌, 習(xí)俊通, 嚴(yán)雋琪. 基于擴(kuò)展高斯球的點(diǎn)云數(shù)據(jù)與CAD模型配準(zhǔn)[J]. 機(jī)械工程學(xué)報(bào), 2007, 43(6): 142-148.

[2] 黃鏡榮, 李熙瑩. 加快尋優(yōu)的醫(yī)學(xué)圖像互信息配準(zhǔn)算法的研究[J]. 中山大學(xué)學(xué)報(bào): 自然科學(xué)版, 2005, 44(S2): 174-177.

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

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

[5] 羅先波, 鐘約先, 李仁舉. 三維掃描系統(tǒng)中的數(shù)據(jù)配準(zhǔn)技術(shù)[J]. 清華大學(xué)學(xué)報(bào): 自然科學(xué)版, 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] 蔣睿嵩, 魏發(fā)遠(yuǎn), 馮大勇, 等. 一種權(quán)值約束的精確配準(zhǔn)算法[J]. 圖學(xué)學(xué)報(bào), 2014, 35(2): 167-172.

[14] 王 森, 王 璐, 洪靖惠, 等. 基于Sparse ICP的三維點(diǎn)云耳廓識(shí)別[J]. 圖學(xué)學(xué)報(bào), 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

國家科技重大專項(xiàng)–高檔數(shù)控機(jī)床與基礎(chǔ)制造裝備科技重大專項(xiàng)課題(2013ZX04011031)

黃 方(1991–)，男，湖南婁底人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)輔助設(shè)計(jì)、CAD技術(shù)。E-mail：hf501x@163.com

寧 濤(1967–)，男，遼寧丹東人，副教授，博士。主要研究方向?yàn)橛?jì)算機(jī)輔助設(shè)計(jì)、CAD/CAM技術(shù)。E-mail：dr.nt@163.com