基于轮廓矢量化形状匹配快速算法

等:基于轮廓矢量化的形状匹配快速算 结果规范化用相对长度差来描述尺寸的差异度其定义可 tl12

|

L2

(

n(L，L1θ12l12反映了两条线段的总体差异程度。由此可见线段(向量)的匹配过程比较简便。如何将这一特性应用于形状

3思路 根据尺寸因素匹配。设lili'分别为轮廓S和矢量化后各自对应的第i条向量的模则li与li' l(

本文算法的思想是通过对轮廓

线点集的离散化采样部分点依次相连构成向量群

lili

lili ＜条线段去近轮廓曲线从而使其线性化最后结合11节

=(=

( ( i i

(的线段匹配计算出相似度。于是问题就转换为如何确

lili0 >0 (离散点之间的采样间隔。文献［6］根据匹配轮廓之间的相对长度(相对弧长)来获取与源图特征点相对应的目标图的期望点;但是源图中的特征点必须是圆弧过度到线段或者线段过度到线段的顶点因此该算法只适用于由线段和弧构成的简单图形。

其中:δ为最大长度差它用来扩大局部轮廓的不相似性。下文中的Δ也是相同作用。本文取δ03。2根据角度因素匹配。θisisi+1titi+1i1，23，n1的夹角，θnsns1tnt1的夹角从相对性上考虑θi0时认为两向量完全相似θiΔ时则完全不同本文方法是如图2所示从区域A中心点O出发以 因此S与T中对应向量的相似度值θ(i)可以由式(6)计算0，逆时针箭头所示方向每隔一个固定角度γ

发出射线射线与轮廓的交点作为特征点集ppp，…

θ(i)= ( 相邻两点连成向量组成沿逆时针方向的严格近轮廓的向量群即{12p2334…}。采样角γ的大小决定了向量的个数n(n=2π/γ)也决定了向量群最终近轮廓的精度，而本文会在实验部分对其大小的确定作进一步地分析。

θ＞其中:Δ为最大角度本文取Δ=5°ρ两种思路均有一定的可行性为使最后的匹配结果能综合尺寸和角度两方面因素轮廓S与T的相似度 可由上述ρS种相似度求和所得1 ∑［τθ(i)+(1τ)l(i) (S ni

!b

a

其中:τ为角度权重因子。通过实验发现轮廓曲线的轨迹与角度因素关系较大本文取τ06。图1线段的匹 图2轮廓离散关于中心点O的确定提出了模板累加法将模板为3×3的方阵对原始数据作卷积运算。当累加次数达到一定时会在图形中间某处出现最大值该点作为中心点;但是该算法需要多次对图形内部的像素点进行累加速度不够快。本文将区域A的重心作为中心点(x0y0)计算如下:

所谓的平移尺度和旋转不变性是指以源图为匹配模板，当目标图像发生任意的平移缩放和旋转变化时匹配的结果不受影响。显然不变性对于算法的合理性提出了更高的要求。中的形状上下文法考量的是目标边缘点的相互位置关系不涉及点的绝对位置所以对平移具有不变性。］利用模板累加法确定边界匹配起始点从而保证旋转x=1∑q 不变性;文献［7］提出了类似的方法 SqA i ( y=

∑q(

本身的锐化程度有关。总体来说现有文献中提到的关于域A的面积。与求轮廓点重心的方法相比式(4)算得的中心根据12节假设源图的轮廓S矢量化后得到的n个向量矢量化后得到的向量群为t1t2，t2t3，t3t4，…，tnt1图3显示出了经矢量化后的轮廓S和轮廓T模型为表述方便每种轮廓

本文基于轮廓矢量化的算法利用了向量的平移不变性使得整体轮廓无论怎样平移都对匹配结果不产生影响。为了消除图形的尺寸大小对于匹配结果的影响算法在匹配之前采用对形状归一化的方法:以最小包络圆圆心为基点将图形进行缩放使得缩放后图形的最小包络圆为一个单位圆。 计算机应用研 第31本文的匹配算法主要用于挠性印刷电路板(flexibleprincircuitFPC)定序列排列排序中形状发生偏转的0和0偏转)可在匹配之前将源图以中心点O为旋转中心转至相应

余匹配值大多在0%以下这说明本文的算法对于检测两种不同批次的焊盘形状有较强的区分性。 xi→ocosαsin x→ 6 = × (yi→o'sinαcos yi→o 表1不同批次焊盘的匹配结 其中xi→o'，yi→oxi→o，yi→o分别表示轮廓上的任意点pi相对于中心点旋转后和旋转前的坐标，α表示偏转角。最后根据为验证文中算法的有效性选取某型号FPC板上的焊盘图像预处理先提取表面再得到轮廓以此作为实验对象。图4为某焊盘金面到轮廓的过程示意图。4本文的1.2节中提到采样角γ的大小决定了近轮廓的向量个数n，从而反映了矢量化的精度而这个精度势必会影响

44. 51. 49. 47. 39. 30. 41. 44. 50. 49. 58. 47. 41. 48. 51. 50. 56. 54. 34. 30. 51. 49. 49. 56. 45. 51. 31. 54. 47. 58. 54. 45. 38. 41. 42. 39. 47. 34. 51. 38. 31. 39. 30. 41. 30. 31. 41. 31. 41. 48. 51. 54. 42. 39. 30. 33为了验证文中算法对形状匹配的综合性能本实验选择实验1中的两组轮廓作为实验对象结合.2节中的方法选取轮廓上的一定量特征点分别使用简化后的极坐标法平均f距离(MD)法形状上下文法以及本文方法进行匹配运算考虑到极坐标法和形状上下文法对各自的特征点数量较敏感均选取4个特征点其余方法选用2个特征点匹配结果和各自所耗时间如表2所示2或选择两组种类不同的相似焊盘为实验对象(第一组命名为1和2，第二组命名为轮廓3和4每组中均有一个缺陷焊盘。采用陆续增大n的方法计算对应的相似度。图5为轮廓示意图和所得的实验数据曲线。从图5(a)(b)

匹配结果ρρρ12396.80.84.ρρρ12396.80.84.0.0.0.———0.0.0.94.89.90.4.4.4.61.59.55.0.0.0.1 3 1

1!""0&01!""0&0!""0&)*)*(a)轮廓1和2的匹配结 (b)轮廓3和4的匹配结5理论上向量个数n越大所得的匹配结果越精确。但这会导致两个问题:a)运算速度变慢;b)匹配结果出错。应该说运算复杂度与向量个数呈线性增长关系这是第一个问题产生的原因;而对于第二个问题当n过大时由于原始轮廓像素点个数有限无法提供足够精细的离散点使之每一个与中心点的连线夹角都等于γ。鉴于此在实用中一般先通过实验对同一批次的焊盘确定出使其相似度值稳定的向量个数范围如图5(a)中的2～0再计算它们对应相似度的算术平均值ρ将其与不同向量个数算得的相似度值进行比较最接近该值的对应向量个数作为最后确定的n。为了验证本文算法的有效性选用八种不同批次的正常焊盘各自进行匹配。焊盘样例编号如图6所示匹配的结果如表1所示。观察表1可知除了自匹配(相似度为0%)以外其

从表2中可以看出似度数值都比较大这是因为C上的焊盘本身形状都很相似;从人眼上判断一般认为轮廓1和2比轮廓3和4相似即ρ12＞34而轮廓1和3属于不同种类的焊盘其相似度值13理应更小显然上述两种方法都没有很好地给予区分。匹配速度方面按照文献介绍的极坐标法实际上需要选取焊盘表面上的所有像素点作为特征点其数量大约为本实验的0～5倍因此其匹配速度已经没有优势;而形状上下文法在本实验中耗时最多;至于MD法其最大的缺点在于无法用百分比定量地评价相似度。综合以上实验结果可知文中焊盘形状匹配算法的综合性能较好平均匹配耗时小于.6s可实际用于焊盘金面的形状匹配但该算法不能应用于凹痕非常剧烈的形状中，这会导致轮廓线性化异常;另外需通过实验确定近向量的个数也比较麻烦这两方面仍然需要提高。在现有的形状匹配算法基础上提出了一种基于轮廓矢量化的算法。对待匹配图像进行预处理先提取轮廓上的特征点将其连成向量再进行匹配运算。通过焊盘的实例运算结果表明文中算法对相似度的计算有一定的可靠性且匹配速度快具有一定的推广性。 (下转第1251页)李等:一种融合多模式单演特征的人脸识别方 充分利用了方向和幅值的分类能力。在Ｒ和SEL人脸库上的实验证明本文MMP和MP能够有效捕获图像中有利于分类的特征同时融合两种模式的方法能够有效地增强特征的判别能力。由于采用分块子模式策略该方法在处理过程中有效避免了同一时间处理高维特征带来的小样本问题。［1］WANGDaran，LIUHuingANGAnzhi，etal．Pefoance．y6［2］BEＲPN，HESPANHAJPKＲIEGMANDJ．s．fisherfaces:recognitionusingclassspecificlinear．Ine，1997，19(7):7110［3］OJALATEM，MAENPAATuiresolutiongraytern．Enegence，2002，24(7):9717．［4］GUOZhenhua，ZHANGLeiZHANGDAcpletedodeingoflocalbinarypatternoperatorfortextureclassification［J．EETransonageProcessing201，19(6):16573［5］TANoyangTＲIGGSBEnhancedlocaltexturefeaturesetsforconditionEonageProcessing201，19(6):16350ieSANChutDagedescripto．ETransonPaenysisandMaeInligence201032(10):17050．［7］GONGDayi，LIShuaoXANGn．Facerecognitionusing

weberlocaldescripto//Procofthe1stAanConferenceonPatternnn．2011:5892［8］LUChengunECSLEＲ．Gaborfeaturebasedclassificationusingtheenhancedfisherlineardciinatedlforfacerecognitio．Enegence，2002，11(4):4676．nWenetbinarypatternhitgamsequence(S):anovelnonstatisticaldlforfacerepresentationandrecognition［C］//Procofthe5thInternationalConferenceonCpurn．2005:7861［10］ZHANGLinZHANGLeiGUOZhenhua，etal．MonogenicPanewapproachforrotationinvarianttextureclassification［C］//Procofthe10thInternationalConferenceonageProcessing．2010:26770．oyngZENGimingetotepoallocalmonogenicbinarypatternsforfacialexpressionrecognitio．ESglProcessingLetters，2012，19(5):2436［12］EBEGM，SEＲGThemonogenicsignal［J．ETransonSgnalProcessing200，49(12):31364［13］杨海燕刘国栋MBLBP算子和urPCA算法的人．47354739．与．6［15］TAKEDAHFAＲSIUSMILANFAＲ．nlregressionforageprocessingandreconstructio．ETransonIaeProcessing，2007，16(2):3466．［16］张宝昌．人脸特征提取和非线性识别方法的研究D．哈尔滨:哈尔滨工业大学，2006．1238页［1］周瑜刘俊涛白翔．形状匹配方法研究与展望J．自动化学报2012，38(6):8890gskeleton．puterVsnandIagesg20080(3):3265［3］XEJun，HENGPAMUBAＲAKSShapehngandodelingcontext．necognton20084117567XiangYANGweiLONGINnofcontourpartsbasedonshapeiilaityJ．Pattencn，2008，41(7):21899［5］HUNGMH，HSIEHCH，KUOC．Styretrievalofshapeesbasedondatabaseclassificatio．JlofslComnesn20067(5J．华南理工大学学报自然科学版，2006，342)771［7］张国敏殷建平祝恩等基于极坐标区间运算的2D．0．［8］XUGang，YANGnn．Fastshapehingusingahybridmode//ProcofInternationalConferenceonCpur

ringandhny．2009:2471［9