周晴，白瑞林，李新

1.江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，信息與控制實(shí)驗(yàn)教學(xué)中心，江蘇無錫 214122

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

基于直線基元的實(shí)時(shí)定位與匹配方法

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

1.江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，信息與控制實(shí)驗(yàn)教學(xué)中心，江蘇無錫 214122

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

1 引言

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

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

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

2 系統(tǒng)方案

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

圖1 算法流程圖

3 離線過程

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

3.1 多邊形近似

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

圖2 多邊形近似算法

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

3.2 直線擬合

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

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

3.3 坐標(biāo)化基元

在如圖3所示的直角坐標(biāo)系中，向量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，在直角坐標(biāo)系中，基元的起點(diǎn)p1(x1,y1)、終點(diǎn)p2(x2,y2)，則基元向量的坐標(biāo)為λ(1,k)，其中λ=|x1-x2|。

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

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

圖3 向量表示示意圖

圖4 向量線性表示圖

幾何哈希法需要計(jì)算所有可能的基底組合，并記錄所有的坐標(biāo)。

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

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

圖5 哈希表存儲(chǔ)示意圖

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

4 在線檢測(cè)

在線過程，對(duì)相機(jī)獲取的在線實(shí)測(cè)圖像，進(jìn)行離線過程相同的操作，預(yù)處理圖像，提取圖像的邊緣輪廓，多邊形近似以得到直線基元。

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

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

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

4.2 基地組合投票

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

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

5 實(shí)驗(yàn)結(jié)果與分析

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

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

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

圖7 模板圖像

圖8 待檢測(cè)圖像

圖9 匹配結(jié)果

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

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

6 結(jié)論

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

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

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

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

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

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

[2]王斌，舒華忠，施朝健，等.一種基于輪廓線的形狀描述與匹配方法[J].電子與信息學(xué)報(bào)，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目標(biāo)分類方法[J].系統(tǒng)仿真學(xué)報(bào)，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ìn)[J].東華大學(xué)學(xué)報(bào)：自然科學(xué)版，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].儀器儀表學(xué)報(bào)，2008，29（9）：1868-1872.

[13]劉相濱，鄒北冀，孫家廣.基于邊界跟蹤的快速歐式距離變換算法[J].計(jì)算機(jī)學(xué)報(bào)，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].計(jì)算機(jī)工程與應(yīng)用，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

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

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

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)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目（No.PAPD）；江蘇省產(chǎn)學(xué)研前瞻性聯(lián)合研究項(xiàng)目（No.BY2012056）。

周晴（1988—），男，碩士研究生，研究領(lǐng)域?yàn)榍度胧綑C(jī)器視覺理論與應(yīng)用；白瑞林（1955—），男，教授，博導(dǎo)，研究領(lǐng)域?yàn)闄C(jī)器視覺與智能系統(tǒng)等；李新（1970—），男，工程師，研究領(lǐng)域?yàn)楣I(yè)自動(dòng)化系統(tǒng)與裝備。E-mail：marschina1@gmail.com

2014-02-28

2014-05-23

1002-8331（2014）22-0228-05

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