基于直线基元的实时定位与匹配方法

周晴，白瑞林，李新

1.江南大学轻工过程先进控制教育部重点实验室，信息与控制实验教学中心，江苏无锡 214122

2.无锡信捷电气股份有限公司，江苏无锡 214072

基于直线基元的实时定位与匹配方法

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

1.江南大学轻工过程先进控制教育部重点实验室，信息与控制实验教学中心，江苏无锡 214122

2.无锡信捷电气股份有限公司，江苏无锡 214072

1 引言

流水线是自动化生产的一个重要环节，在流水线上实现工件相对位置的实时定位，能降低生产成本并进一步提高自动化生产效率。机器视觉定位技术[1]具有速度快、稳定性好、精度高，抗干扰能力强等突出优点，应用于目标的实时定位与匹配，取得了一系列的研究成果。王斌、舒华忠等[2]提出了一种基于轮廓线的形状描述与匹配方法，使用三个欧氏距离计算形状之间的相似度。Chen等[3]提出了一种将模板物体与搜索图像中的轮廓线分割为线段，利用线段间的几何关系实现匹配定位。以上方法均未能达到实际生产要求。

几何哈希法[4]是IBM Watson研究中心的HAIMJ. W.OLSFSON提出的一种图像匹配算法，该算法将坐标的几何特征与哈希表结合使用，基于结构信息进行模板匹配。AlbertT[5]将图像的角点作为稳定特征，将特征点用两个基点来坐标表示，采用几何哈希法来实现匹配定位，但该方法在建立几何哈希表时占用了大量的内存空间。黄嘉辛、陆军[6]等通过减少模板库的采集样本数来提高几何哈希法匹配定位的效率，提供了改善几何哈希法的效率的思路。此外，还有以形状上下文[7-9]的方法来实现匹配定位，但不能满足实时性要求。Chum O等提出了一种基于几何哈希法的局部图像匹配算法，将图像的局部特征用其邻域内的相对位置信息构成，利用几何哈希法完成目标的定位与匹配[10]。Chum O在研究利用几何基元信息构建可重复的几何哈希表时，改进了匹配算法，改善了目标定位与匹配算法在重复匹配与错误率的问题[11]。

基于以上述分析，本文提出一种基于直线基元的几何哈希法实时定位与匹配方法。通过离线训练学习模板，将模板中的直线基元用坐标表示，选择直线基元构建基底，量化剩余基元并建立几何哈希表；在线实测图像中，选择一组直线基元构成基底，量化剩余基元，通过坐标在几何哈希表中查询对应的基底并投票，来实现实时定位与匹配。本算法通过几何基元之间的关系匹配定位模板实例，避免了以全部边缘轮廓特征点作为特征匹配的计算复杂性。经过实验分析，算法实时性好、准确性高。

2 系统方案

一种基于直线基元的几何哈希法实时定位与匹配方法的整体流程如图1所示。离线过程，建立几何哈希表，提取直线基元作为特征，将直线基元向量化，选择其中两个基元作为基底，坐标表示剩余基元，以坐标构建哈希表的查询地址，基底信息作为哈希表的内容；在线过程中，提取在线实测图像中的直线基元信息，选择主直线作为基底坐标表示其余直线基元，查询哈希表，并投票确定基底组合，以此方法来实现实时定位与匹配。

图1 算法流程图

3 离线过程

离线过程是建立几何哈希表的过程，提取的特征是直线基元，通过智能相机捕获到的图像需要进行预处理操作，去除噪声的干扰；为得到模板目标，采用最小Tsallis交叉熵阈值图像分割[12]将目标和背景分割出来，并采用一种快速跟踪边缘轮廓轮的方法[13]得到目标工件的轮廓，通过多边形近似，直线拟合等步骤得到直线基元；将基元向量表示，选择其中两个基元作为基底，坐标表示剩余基元，以坐标构建哈希表的地址，基底信息作为哈希表的内容。

3.1 多边形近似

多边形近似是图像轮廓的一种描述方法，格拉斯-普克法[14]采用了一种计算点到直线的最大距离，来寻找轮廓分段点的方法。算法步骤如图2所示。

图2 多边形近似算法

由上述方法实现轮廓的多边形描述，提出的基于直线基元的几何哈希法实时匹配与定位方法，需要提取直线基元作为特征，为去除可能构成圆弧的部分，减少算法的复杂性和计算量，将多边形中小于某阈值（一般为10个像素）的边长去除，不进行下一步的处理。

3.2 直线拟合

式（1）、（2）计算得到了线段基元的参数k、b。

通过直线基元的几何参数k、b，检验相邻的两个直线基元是否属于一条直线，判断斜率k、b在某阈值（斜率之差小于0.3）范围内，则认为属于同一条直线基元，将它们合并，并采用最小二乘直线拟合法计算几何参数。

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)。

根据拟合得到的斜率信息k，在直角坐标系中，基元的起点p1(x1,y1)、终点p2(x2,y2)，则基元向量的坐标为λ(1,k)，其中λ=|x1-x2|。

本课题的案例库框架建设，经过反复对比建设的资金、难度和适应性后，课程组决定采用网页型框架，使用Dreamweaver软件编辑网页构架。

将直线基元用不同的基底表示，如图4所示，以此来描述基元之间的相对位置关系。选择两个不共线的基元作为基底，构建坐标系，将其余基元在此基底下坐标表示(α,β)，向量表示：c=αa+βb。

图3 向量表示示意图

图4 向量线性表示图

几何哈希法需要计算所有可能的基底组合，并记录所有的坐标。

3.4 构建几何哈希表

对所有的向量坐标(α,β)，即关键码，建立一个映射地址index，并在地址index中存入相应坐标的基底信息，如图5所示，本文提出了一种映射地址的计算方法，即将坐标(α,β)的第一坐标α作为映射地址的整数部分，第二坐标β作为映射地址的小数部分，即index=α.β。

图5 哈希表存储示意图

为查询地址方便，在构建哈希表时，将哈希表内容（即坐标，映射地址，基底组合）按index的大小顺序排列。

4 在线检测

在线过程，对相机获取的在线实测图像，进行离线过程相同的操作，预处理图像，提取图像的边缘轮廓，多边形近似以得到直线基元。

首先，选择两个主直线基元（即直线基元长大于一定的阈值，一般取20个像素）作为所有直线基元的基底，按向量坐标表示法坐标表示剩余直线基元，然后，查询离线建立的几何哈希表，对基底组合投票以确定匹配的对象。算法流程如图6所示。

图6 在线定位与匹配算法流程图

计算得到的各基元坐标(μ,σ)，计算映射地址index=μ.σ，本文在离线构建几何哈希表时，将哈希表内容（即坐标、映射地址、基底组合）按index的数值大小排序，因此在搜索哈希表(α,β)时，通过数值的大小可以迅速查询到目标位置。考虑坐标的计算误差，满足地址即为搜到地址，通过搜索地址，得到基底组合信息。

4.2 基地组合投票

得到映射地址，查询到对应基底信息(basic_x,basic_y)，并给对应的基底组合投票。若一个映射地址对应多个基底组合，则将对每个基底组合投票。

当全部直线基元在基底下得到的坐标，其坐标对应的基底组合全部投票完毕。本文选择投票数最多的一组基底。将模板中选中的基底对应的坐标表示形式与实测图像对应比较，将相同的部分在实测图像中表示出来，并且计算目标工件的相对旋转角，通过对应的直线基底的相对角度得到。

5 实验结果与分析

系统构建采用自主研发SV4-30M CMOS智能相机、25 mm定焦镜头以及背光光源，采集图像并在Matlab R2012a平台做算法仿真实验，系统配置CPU为Pentium®E6700 3.2 GHz，内存（RAM）2.00 GB。

针对各种类型工件图像进行仿真实验，算法满足工业现场实时、准确的要求。下面以一组图像为例。

算法使用的两组模板图像如图7所示，对应的2组待检测的图像如图8所示，并给出了对应的2组检测检测结果如图9所示。

图7 模板图像

图8 待检测图像

图9 匹配结果

采用了2组工件来做实验验证算法，如图7所示，它们作为模板图像，经过处理建立基于直线基元的几何哈希表。其中图8（a）、图8（c），具有单个目标，且目标背景复杂，有干扰物体，如图9（a）、图9（c）显示，算法在选择一组基底（图中红色部分所示的直线基元）的情况下，匹配到了模板中的剩余直线基元（图中蓝色部分所示的直线基元）并计算工件的相对旋转角度；如图8（b）、8（d）所示，具有多个目标，且目标的部分被遮挡，还具有无关物体的干扰等外界影响，算法能够准确地定位出实测图像中的2个目标，如图9（b）、图9（d）所示，其中图9（d）的目标被部分遮挡，算法在选择一组基底（图中红色部分所示的直线基元）的情况下，匹配到了模板中的剩余直线基元（图中蓝色部分所示的直线基元）并计算工件的相对旋转角度。算法测试的结果如表1所示，并与文献[15]提出的方法进行比较，匹配过程所用时间没有包括边缘跟踪耗时。

表1 算法检测结果

6 结论

针对工业流水线工件的定位与匹配，提出一种基于直线基元的几何哈希法实时定位与匹配方法，有如下特点：

（1）离线过程，用轮廓的多边形描述来提取直线基元，采用向量方式表示直线基元，并构造直线基元的基底，量化剩余基元。本文用这种方法描述了直线基元之间的相互关系。

（2）构建几何哈希表，以直线基元为特征构造的哈希表，数据量小，提高了算法的速度。

（3）构建基底信息的投票方法，以特殊的映射地址，快速得到基底组合信息，能实时定位工件的位置并得到相对旋转角度。

实验表明，算法在背景复杂，存在遮挡的工业环境下，利用几何基元之间的相互关系，提出了一种基于直线基元的几何哈希法实时定位与匹配算法。该算法采用直线基元特征建立几何哈希表，极大减少了内存空间，提高了算法的效率，并满足工业现场实时性与准确性的要求。

[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].系统仿真学报，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]唐英干，邸秋艳，关新平，等.基于最小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

为实现工业过程中对工件的实时定位，提出一种基于直线基元的几何哈希法实时定位与匹配方法。离线学习模板过程，提取图像中的直线基元，选择其中两个直线基元构建基底，量化剩余基元并建立几何哈希表；在线实测图像中，选择一组直线基元构成基底，量化剩余基元，通过坐标在几何哈希表中查询对应的基底并投票，来实现实时定位与匹配。实验证明，该方法对于工件的定位与匹配，实时性好、准确性高。

机器视觉；几何基元；几何哈希法；匹配定位

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.

江苏高校优势学科建设工程资助项目（No.PAPD）；江苏省产学研前瞻性联合研究项目（No.BY2012056）。

周晴（1988—），男，硕士研究生，研究领域为嵌入式机器视觉理论与应用；白瑞林（1955—），男，教授，博导，研究领域为机器视觉与智能系统等；李新（1970—），男，工程师，研究领域为工业自动化系统与装备。E-mail：marschina1@gmail.com

2014-02-28

2014-05-23

1002-8331（2014）22-0228-05

CNKI网络优先出版：2014-06-24,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0378.html