基于直線基元的實時定位與匹配方法

周晴，白瑞林，李新

1.江南大學輕工過程先進控制教育部重點實驗室，信息與控制實驗教學中心，江蘇無錫 214122

2.無錫信捷電氣股份有限公司，江蘇無錫 214072

基于直線基元的實時定位與匹配方法

周晴1，白瑞林1，李新2

1.江南大學輕工過程先進控制教育部重點實驗室，信息與控制實驗教學中心，江蘇無錫 214122

2.無錫信捷電氣股份有限公司，江蘇無錫 214072

1 引言

流水線是自動化生產(chǎn)的一個重要環(huán)節(jié)，在流水線上實現(xiàn)工件相對位置的實時定位，能降低生產(chǎn)成本并進一步提高自動化生產(chǎn)效率。機器視覺定位技術(shù)[1]具有速度快、穩(wěn)定性好、精度高，抗干擾能力強等突出優(yōu)點，應用于目標的實時定位與匹配，取得了一系列的研究成果。王斌、舒華忠等[2]提出了一種基于輪廓線的形狀描述與匹配方法，使用三個歐氏距離計算形狀之間的相似度。Chen等[3]提出了一種將模板物體與搜索圖像中的輪廓線分割為線段，利用線段間的幾何關(guān)系實現(xiàn)匹配定位。以上方法均未能達到實際生產(chǎn)要求。

幾何哈希法[4]是IBM Watson研究中心的HAIMJ. W.OLSFSON提出的一種圖像匹配算法，該算法將坐標的幾何特征與哈希表結(jié)合使用，基于結(jié)構(gòu)信息進行模板匹配。AlbertT[5]將圖像的角點作為穩(wěn)定特征，將特征點用兩個基點來坐標表示，采用幾何哈希法來實現(xiàn)匹配定位，但該方法在建立幾何哈希表時占用了大量的內(nèi)存空間。黃嘉辛、陸軍[6]等通過減少模板庫的采集樣本數(shù)來提高幾何哈希法匹配定位的效率，提供了改善幾何哈希法的效率的思路。此外，還有以形狀上下文[7-9]的方法來實現(xiàn)匹配定位，但不能滿足實時性要求。Chum O等提出了一種基于幾何哈希法的局部圖像匹配算法，將圖像的局部特征用其鄰域內(nèi)的相對位置信息構(gòu)成，利用幾何哈希法完成目標的定位與匹配[10]。Chum O在研究利用幾何基元信息構(gòu)建可重復的幾何哈希表時，改進了匹配算法，改善了目標定位與匹配算法在重復匹配與錯誤率的問題[11]。

基于以上述分析，本文提出一種基于直線基元的幾何哈希法實時定位與匹配方法。通過離線訓練學習模板，將模板中的直線基元用坐標表示，選擇直線基元構(gòu)建基底，量化剩余基元并建立幾何哈希表；在線實測圖像中，選擇一組直線基元構(gòu)成基底，量化剩余基元，通過坐標在幾何哈希表中查詢對應的基底并投票，來實現(xiàn)實時定位與匹配。本算法通過幾何基元之間的關(guān)系匹配定位模板實例，避免了以全部邊緣輪廓特征點作為特征匹配的計算復雜性。經(jīng)過實驗分析，算法實時性好、準確性高。

2 系統(tǒng)方案

一種基于直線基元的幾何哈希法實時定位與匹配方法的整體流程如圖1所示。離線過程，建立幾何哈希表，提取直線基元作為特征，將直線基元向量化，選擇其中兩個基元作為基底，坐標表示剩余基元，以坐標構(gòu)建哈希表的查詢地址，基底信息作為哈希表的內(nèi)容；在線過程中，提取在線實測圖像中的直線基元信息，選擇主直線作為基底坐標表示其余直線基元，查詢哈希表，并投票確定基底組合，以此方法來實現(xiàn)實時定位與匹配。

圖1 算法流程圖

3 離線過程

離線過程是建立幾何哈希表的過程，提取的特征是直線基元，通過智能相機捕獲到的圖像需要進行預處理操作，去除噪聲的干擾；為得到模板目標，采用最小Tsallis交叉熵閾值圖像分割[12]將目標和背景分割出來，并采用一種快速跟蹤邊緣輪廓輪的方法[13]得到目標工件的輪廓，通過多邊形近似，直線擬合等步驟得到直線基元；將基元向量表示，選擇其中兩個基元作為基底，坐標表示剩余基元，以坐標構(gòu)建哈希表的地址，基底信息作為哈希表的內(nèi)容。

3.1 多邊形近似

多邊形近似是圖像輪廓的一種描述方法，格拉斯-普克法[14]采用了一種計算點到直線的最大距離，來尋找輪廓分段點的方法。算法步驟如圖2所示。

圖2 多邊形近似算法

由上述方法實現(xiàn)輪廓的多邊形描述，提出的基于直線基元的幾何哈希法實時匹配與定位方法，需要提取直線基元作為特征，為去除可能構(gòu)成圓弧的部分，減少算法的復雜性和計算量，將多邊形中小于某閾值（一般為10個像素）的邊長去除，不進行下一步的處理。

3.2 直線擬合

式（1）、（2）計算得到了線段基元的參數(shù)k、b。

通過直線基元的幾何參數(shù)k、b，檢驗相鄰的兩個直線基元是否屬于一條直線，判斷斜率k、b在某閾值（斜率之差小于0.3）范圍內(nèi)，則認為屬于同一條直線基元，將它們合并，并采用最小二乘直線擬合法計算幾何參數(shù)。

3.3 坐標化基元

在如圖3所示的直角坐標系中，向量AB的表示為：AB=OB-OA，其中A(x1,y1)、B(x2,y2)，則：AB=(x3,y3)= OB-OA=(x2,y2)-(x1,y1)=(x2-x1,y2-y1)。

根據(jù)擬合得到的斜率信息k，在直角坐標系中，基元的起點p1(x1,y1)、終點p2(x2,y2)，則基元向量的坐標為λ(1,k)，其中λ=|x1-x2|。

本課題的案例庫框架建設，經(jīng)過反復對比建設的資金、難度和適應性后，課程組決定采用網(wǎng)頁型框架，使用Dreamweaver軟件編輯網(wǎng)頁構(gòu)架。

將直線基元用不同的基底表示，如圖4所示，以此來描述基元之間的相對位置關(guān)系。選擇兩個不共線的基元作為基底，構(gòu)建坐標系，將其余基元在此基底下坐標表示(α,β)，向量表示：c=αa+βb。

圖3 向量表示示意圖

圖4 向量線性表示圖

幾何哈希法需要計算所有可能的基底組合，并記錄所有的坐標。

3.4 構(gòu)建幾何哈希表

對所有的向量坐標(α,β)，即關(guān)鍵碼，建立一個映射地址index，并在地址index中存入相應坐標的基底信息，如圖5所示，本文提出了一種映射地址的計算方法，即將坐標(α,β)的第一坐標α作為映射地址的整數(shù)部分，第二坐標β作為映射地址的小數(shù)部分，即index=α.β。

圖5 哈希表存儲示意圖

為查詢地址方便，在構(gòu)建哈希表時，將哈希表內(nèi)容（即坐標，映射地址，基底組合）按index的大小順序排列。

4 在線檢測

在線過程，對相機獲取的在線實測圖像，進行離線過程相同的操作，預處理圖像，提取圖像的邊緣輪廓，多邊形近似以得到直線基元。

首先，選擇兩個主直線基元（即直線基元長大于一定的閾值，一般取20個像素）作為所有直線基元的基底，按向量坐標表示法坐標表示剩余直線基元，然后，查詢離線建立的幾何哈希表，對基底組合投票以確定匹配的對象。算法流程如圖6所示。

圖6 在線定位與匹配算法流程圖

計算得到的各基元坐標(μ,σ)，計算映射地址index=μ.σ，本文在離線構(gòu)建幾何哈希表時，將哈希表內(nèi)容（即坐標、映射地址、基底組合）按index的數(shù)值大小排序，因此在搜索哈希表(α,β)時，通過數(shù)值的大小可以迅速查詢到目標位置。考慮坐標的計算誤差，滿足地址即為搜到地址，通過搜索地址，得到基底組合信息。

4.2 基地組合投票

得到映射地址，查詢到對應基底信息(basic_x,basic_y)，并給對應的基底組合投票。若一個映射地址對應多個基底組合，則將對每個基底組合投票。

當全部直線基元在基底下得到的坐標，其坐標對應的基底組合全部投票完畢。本文選擇投票數(shù)最多的一組基底。將模板中選中的基底對應的坐標表示形式與實測圖像對應比較，將相同的部分在實測圖像中表示出來，并且計算目標工件的相對旋轉(zhuǎn)角，通過對應的直線基底的相對角度得到。

5 實驗結(jié)果與分析

系統(tǒng)構(gòu)建采用自主研發(fā)SV4-30M CMOS智能相機、25 mm定焦鏡頭以及背光光源，采集圖像并在Matlab R2012a平臺做算法仿真實驗，系統(tǒng)配置CPU為Pentium?E6700 3.2 GHz，內(nèi)存（RAM）2.00 GB。

針對各種類型工件圖像進行仿真實驗，算法滿足工業(yè)現(xiàn)場實時、準確的要求。下面以一組圖像為例。

算法使用的兩組模板圖像如圖7所示，對應的2組待檢測的圖像如圖8所示，并給出了對應的2組檢測檢測結(jié)果如圖9所示。

圖7 模板圖像

圖8 待檢測圖像

圖9 匹配結(jié)果

采用了2組工件來做實驗驗證算法，如圖7所示，它們作為模板圖像，經(jīng)過處理建立基于直線基元的幾何哈希表。其中圖8（a）、圖8（c），具有單個目標，且目標背景復雜，有干擾物體，如圖9（a）、圖9（c）顯示，算法在選擇一組基底（圖中紅色部分所示的直線基元）的情況下，匹配到了模板中的剩余直線基元（圖中藍色部分所示的直線基元）并計算工件的相對旋轉(zhuǎn)角度；如圖8（b）、8（d）所示，具有多個目標，且目標的部分被遮擋，還具有無關(guān)物體的干擾等外界影響，算法能夠準確地定位出實測圖像中的2個目標，如圖9（b）、圖9（d）所示，其中圖9（d）的目標被部分遮擋，算法在選擇一組基底（圖中紅色部分所示的直線基元）的情況下，匹配到了模板中的剩余直線基元（圖中藍色部分所示的直線基元）并計算工件的相對旋轉(zhuǎn)角度。算法測試的結(jié)果如表1所示，并與文獻[15]提出的方法進行比較，匹配過程所用時間沒有包括邊緣跟蹤耗時。

表1 算法檢測結(jié)果

6 結(jié)論

針對工業(yè)流水線工件的定位與匹配，提出一種基于直線基元的幾何哈希法實時定位與匹配方法，有如下特點：

（1）離線過程，用輪廓的多邊形描述來提取直線基元，采用向量方式表示直線基元，并構(gòu)造直線基元的基底，量化剩余基元。本文用這種方法描述了直線基元之間的相互關(guān)系。

（2）構(gòu)建幾何哈希表，以直線基元為特征構(gòu)造的哈希表，數(shù)據(jù)量小，提高了算法的速度。

（3）構(gòu)建基底信息的投票方法，以特殊的映射地址，快速得到基底組合信息，能實時定位工件的位置并得到相對旋轉(zhuǎn)角度。

實驗表明，算法在背景復雜，存在遮擋的工業(yè)環(huán)境下，利用幾何基元之間的相互關(guān)系，提出了一種基于直線基元的幾何哈希法實時定位與匹配算法。該算法采用直線基元特征建立幾何哈希表，極大減少了內(nèi)存空間，提高了算法的效率，并滿足工業(yè)現(xiàn)場實時性與準確性的要求。

[1]Steger C，Ulrich M，Wiedemann C.機器視覺算法與應用[M].楊少榮，吳迪靖，段德山，譯.北京：清華大學出版社，2008：238-345.

[2]王斌，舒華忠，施朝健，等.一種基于輪廓線的形狀描述與匹配方法[J].電子與信息學報，2008，30（4）：949-952.

[3]Chen J M，Ventura J A.Segmentation of planar curves into circular arcs and line segments[J].Image and Vision Computing，1996，14（1）：71-83.

[4]Grimson W E L，Lozano-Perez T.Localizing overlapping parts by searching the interpretation tree[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1987（4）：469-482.

[5]Albert T S Au.Affine invariant recognition of 2D occluded objects using Geometric Hashing and Distance Transformation[J].IEEE TENCON-Digital Signal Processing Applications，1996：64-67.

[6]黃嘉辛，陸軍，趙凌君，等.一種基于仿真圖像模板的SAR目標分類方法[J].系統(tǒng)仿真學報，2013，25（6）：1359-1363.

[7]Hu Yuanyuan，Niu Xiamu，Zhang Hui.A novel perceptual image hashing method via geometric features and distance invariant[C]//2ndInternationalCongressonImageand Signal Processing.[S.l.]：IEEE，2009.

[8]Jayaraman U，Gupta A K，Prakash S，et al.An enhanced geometric hashing[C]//2011 IEEE International Conference on Communications（ICC）.[S.l.]：IEEE，2011：1-5.

[9]夏小玲，柴望.基于Shape Context的形狀匹配方法的改進[J].東華大學學報：自然科學版，2009，35（1）：79-83.

[10]Chum O，Matas J.Geometric hashing with local affine frames[C]//Computer Society Conference on Computer VisionandPatternRecognition，New York，2006，1：879-884.

[11]Chum O，Perdoch M，Matas J.Geometric min-hashing：Finding a（thick）needle in a haystack[C]//Computer Vision and Pattern Recognition（CVPR），New York，2009：17-24.

[12]唐英干，邸秋艷，關(guān)新平，等.基于最小Tsallis交叉熵閾值圖像分割方法[J].儀器儀表學報，2008，29（9）：1868-1872.

[13]劉相濱，鄒北冀，孫家廣.基于邊界跟蹤的快速歐式距離變換算法[J].計算機學報，2006，29（2）：317-323.

[14]Douglas D H，Peucker T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].The Canadian Cartographer，1973，10（2）：112-122.

[15]倪健，白瑞林，李英，等.采用輪廓向量特征的嵌入式圖像匹配方法[J].計算機工程與應用，2014，50（13）：168-172.

ZHOU Qing1,BAI Ruilin1,LI Xin2

1.Key Laboratory of Advanced Process Control for Light Industry（Ministry of Education）,Information and Control Experiment Teaching Center,Jiangnan University,Wuxi,Jiangsu 214122,China
2.Xinje Electronic Co.,Ltd.,Wuxi,Jiangsu 214072,China

In order to achieve real-time positioning of the workpiece in the industrial processes,a real-time location and matching method based on linear geometric hashing primitive is proposed.In the offline process,linear primitives are extracted from the image,one of the two linear primitives is selected to construct basement,quantify the remaining primitives and establish the geometric Hashing table;In the online process,a set of linear primitives is selected to be basement,quantify the remaining primitives,for the coordinates in the geometric Hashing table query corresponding substrate and vote them,in this way real-time locating and matching are achieved.Through the experimental analysis,the method for the positioning and matching of the workpiece,is good real-time,high accuracy.

machine vision;geometric primitives;geometric hashing;positioning and matching

為實現(xiàn)工業(yè)過程中對工件的實時定位，提出一種基于直線基元的幾何哈希法實時定位與匹配方法。離線學習模板過程，提取圖像中的直線基元，選擇其中兩個直線基元構(gòu)建基底，量化剩余基元并建立幾何哈希表；在線實測圖像中，選擇一組直線基元構(gòu)成基底，量化剩余基元，通過坐標在幾何哈希表中查詢對應的基底并投票，來實現(xiàn)實時定位與匹配。實驗證明，該方法對于工件的定位與匹配，實時性好、準確性高。

機器視覺；幾何基元；幾何哈希法；匹配定位

A

TP391.4

10.3778/j.issn.1002-8331.1402-0378

ZHOU Qing,BAI Ruilin,LI Xin.Real-time location and matching method based on line geometric primitives with geometric hashing.Computer Engineering and Applications,2014,50（22）：228-232.

江蘇高校優(yōu)勢學科建設工程資助項目（No.PAPD）；江蘇省產(chǎn)學研前瞻性聯(lián)合研究項目（No.BY2012056）。

周晴（1988—），男，碩士研究生，研究領(lǐng)域為嵌入式機器視覺理論與應用；白瑞林（1955—），男，教授，博導，研究領(lǐng)域為機器視覺與智能系統(tǒng)等；李新（1970—），男，工程師，研究領(lǐng)域為工業(yè)自動化系統(tǒng)與裝備。E-mail：marschina1@gmail.com

2014-02-28

2014-05-23

1002-8331（2014）22-0228-05

CNKI網(wǎng)絡優(yōu)先出版：2014-06-24,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0378.html