一种图像相似度匹配的算法

2012年第17期SCIENCE &TECHNOLOGY INFORMATION

○高校讲坛○科技信息

一种图像相似度匹配的算法

潘

(1.武汉理工大学自动化学院湖北武汉

李佩2

430082；2. 武汉大学电子信息学院

岱1

湖北武汉430070)

【摘要】提出了一种在matlab 中计算图形相似度的度量方法。首先，我们得到某种未知图形和已知图形的某些特征组成的行向量，由这些行向量得到该特征行向量的协方差矩阵。然后，由已知图形和未知图形的协方差方程的行向量中采用一维DP 匹配方法，产生一个代替未知图形的协方差矩阵的相似行向量。最后，根据一维DP 匹配计算相似行向量与未知图形协方差矩阵标准行向量之间的匹配距离，度量出两个未知图形与已知图形的相似度。此方法适用于matlab 图像中对于图形的形状分类等，实验证明，此方法效果良好。

【关键词】图像处理；图像匹配；协方差矩阵；DP 距离；Dijkstra 算法

0引言

在图像处理中，相似度的计算是一个十分关键的问题。因为在图像匹配中，很难精确的描述两种相似图形的特征。如果能够将未知图形的模块和已知图形模块的视觉特征用矩阵来表示，单纯的转化为矩阵之间相似性的比较，那么，这种匹配就变得相对简单，也更有理论依据[1]。

表达图像特征相似度的时候，通常采用的方法就是距离法。欧氏距离是测量两个特征矩阵的简单方法，即通过对应位置元素的差来计算特征矩阵的相似度。在人的观察有限的情况下，欧氏距离描述的相似度更加的准确。

d 矩阵即为匹配距离矩阵，将d 矩阵看成是加权有向图，以d(1,1)为加权图的起点，d(i,j)看成是终点，寻找起点到终点的最短距离，即d (1,1)到d(i,j)的路径上权值之和最小的路径距离。矩阵中元素间权值与元素距离d 有关，假设d(i,j)为终点，分别从d(i-1，j-1) 、d(i-1,j)和d(i,j-1) 连接一条有向边，这三条边的权值为ω1、ω2、ω3，此时ω1=2d（i ，j ）、ω2=2（i ，j ）、ω3=d（i ，j ）。具体示意图如下：

1协方差矩阵的计算

图2

元素间权值设置

区域协方差矩阵就是用一个d 维的协方差矩阵来描述区域的特征，它表述了d 维特征中每个分量自身的方差以及分量之间的相关关系，在本文中即指相关图像的d 个特征。为方便说明，设I 为相关的图像，W 和H 分别表示图形的宽度和高度，则该图像宽度和高度的特征向量就可写成(W,H)。

假设已知图形的特征向量为α=（α1，α2，α3，…，αn ），则该区域协方差矩阵C R 的表达式为：

Dijkstra 算法是图论中计算加权有向图任意两个节点最短路径的经典算法[5]，利用该算法可以得到起点d(1,1)到终点d(i,j)的最短路径长度，据此对得到的距离矩阵进行归一化处理，公式为：

C R =

≠

d DP （I ，Q ）＝

D （αi ，αj ）

i ≠j （i ，j =1，2，3…n ）i =j （i ，j =1，2，3…n ）

1（d （1，1）+P ）

min

2n -1

（3）

COV （αi ，αj ）

（1）

对DP 距离归一化之后，保证了DP 匹配距离值与向量元素的数目无关，更有参考性。至此，我们就求出了I 1和Q 1的DP 匹配距离

其中D （αi ，αj ）为αi 和αj 组成的行向量的方差，COV （αi ，αj ）为αi

和αj 组成的行向量的协方差，这样我们就得到一个n ×n 维的协方差矩阵C R 。

d11DP 。

同理取出C R 1的第一行和C R 2的第二行，设为I 1和Q 2，得到d12DP 。DP 距离共有n ×n 个，组成DP 距离矩阵。

2DP 距离的计算[2]

DP(DynamicProgramming) 匹配是一种用来计算两个一维向量匹

配距离的方法，不同于经典的欧几里得范数，它给人整合窗的概念，允许特征向量中的一个元素可以在给定的整合窗内选择对应特征向量中具有最小元素距离的元素作为其匹配对象，而不仅仅限定在对应位置元素。其具体的操作方法在下文中有详细介绍[3]。

Shiiyama 把一维向量的DP 匹配扩展到二维向量。利用这点，就可以对得到的协方差进行匹配[4]。

根据上面的内容已经可以将图形的特征转化为数字形式存放在C R 矩阵中，要计算已知图形和未知图形的匹配度的话，只要计算出已知图形的C R 1和未知图形的C R 2，并求取两个矩阵之间的匹配度即可。DP 距离针对的是一维向量，所以，我们先分别取出C R 1和C R 2的第一行，设为I 1和Q 1。这里，先求出这两个行向量的元素距离矩阵d ，该距离的定义如下：

图3

计算d DP 所有行的最小距离并将与之比较的C R 2的行数记住并存放在一个行矩阵S1中，若某行比较之后的最好距离超过一定的阈值，将该距离对应的行数记为零。设S2=(1,2,3,…,n), 再用之前的公式（3）计算d DP （S1，S2）, 最后得到两个图形的相似度s=1-dDP （S1，S2），当s 为1时，两个图形十分相似。若S1中零值的个数超过了n/2个，则s 直接定义为零，即两个图形不相似。

d （I 1，Q 1）=I 1-Q 1

I 1+Q 1

则，d 矩阵的构成如下图1所示：

（2）

3结束语

将图像特征转化为矩阵从而求取已知图形和未知图形的相似性，在选取图形相关特征是就要考虑到该特征是否有大小和旋转的不变性。同时，相关特征的个数越多，相似度s 的值就越能准确的反应出图像的相似性。

但是也必须注意到，n 越大，DP 匹配算法的时间复杂度就越高，算法的执行时间就会越长。科

●

【参考文献】

（下转第278页）

张磊, 等. 基于神经网络自学习的图像检索方法[J].软件学报，2001,12(10):［1］

图1

1479-1485.

2012年第17期SCIENCE &TECHNOLOGY INFORMATION

○职校论坛○科技信息

学。其中，课堂实践教学方便学生参与；校园实践教学容易调动学生的积极性；社会实践教学则能够锻炼学生运用理论分析问题、解决问题的能力。一是课堂实践教学形式要丰富多彩，使学生能够更加广泛的参与其中。例如在教师讲授理论的同时，可以尝试组织学生进行随堂讨论、辩论等有效形式，趁热打铁的进行理论联系实际的讲授，以期取得最佳教学效果。二是积极组织、引导校园实践教学的开展。教师全程参与学生活动选拔、指导，让学生即学到了书本上的理论知识，又通过活动培养了学生发现问题、运用理论分析问题、解决问题的能力，进而促使理论进入学生的头脑，内化为学生的世界观和方法论，从而实现思想政治理论课实践教学的目的。三是放宽社会实践教学参与的准入门槛，能够让更广泛学生参与。改变以往以点代面、以偏概全的做法，改变以少数学生干部代表大多数普通学生的做法，真正让学生通过社会实践教学的形式，了解社会实际，用理论来解决实际问题。例如，组织社会实践活动中，教师可以利用QQ 群、飞信群、手机短信等现代通讯手段时刻与学生保持联系，随时解决学生遇到的问题，并且在假期结束后，教师要严格审批学生递交的社会实践报告，了解实践中学生关注的社会问题，产生的疑惑及由此产生的思想问题，从而有针对性地调整教学计划，使社会实践与课堂教学有机地联系起来。

（3）增强教师指导实践教学的经验和构建实践教学考评机制。实践教学不但是—种教学活动，而且比理论教学更难。它不仅要求教师具有良好的思想政治素质、扎实的理论功底和理论联系实际的意识，而且还要具备较强的组织、协调能力。因此，高校有关部门应有针对性地组织思想政治理论课教师进行开展实践教学技能的培训，不断探索思想政治理论课实践教学的新方法和新途径。例如利用暑假专门集中

开展校际之间的教师实践教学交流会；通过实地观摩去感受实践教学的流程与方法。只有思想政治理论课教师多交流、多接触，多学习，才能在以后的教学过程中更好的组织各种实践教学活动。另外，要探索构建有效的实践教学考评机制。这是实现思想政治理论课教学目标的重要保证。为了保证考评标准的统一性、一致性和体现灵活性以及地区差异性。建议由教育部统一制定考评标准原则，各省制定适合本省实际情况的实践教学考评标准，至于考评细则，则由相关高校根据自身开展的实践教学情况具体制定。既要体现教师指导学生的用心程度、选题内容、活动开展质量等方面，又要体现学生在实践教学活动中的参与热情度、活动完成质量高低、创新精神等。科

●

【参考文献】

栾谨崇. 高校思想政治理论课实践教学的多维度思考[J].鲁东大学学报:哲学［1］

社会科学版,2008,05:90.

吕健. 对思想政治理论课实践教学的几点思考[J].沈阳航空工业学院学报:［2］

2006,06:148.［3］http://www.gov.cn/ldhd/2008-07/09/content_1040644.htm[OL].

教育部网站：http://www.moe.gov.cn/publicfiles/business/htmlfiles/moe/moe_772/［4］

201001/xxgk_80414[OL].

作者简介：刘京雷（1982—），男，江苏徐州人，硕士研究生，郑州职业技术学院教师，研究方向为高校思想政治教育。

［责任编辑：曹明明］

（上接第151页）3）以上步骤完成后，可以设定Web 服务组合的约束条件逻辑说明和Web 服务组件的逻辑功能说明。这些工作完成后，就可以把各个组件和数据随机打乱，然后再随机的映射到本体域上面。

4）Web 服务的输入和输出参数通常为3-6个，每个Web 服务通常由4-8个原子Web 服务构成；

5）测试环境：CPU 为Intel core I32.4GHz, RAM 为4GB ，OS 为

法发激发序列，该合法序列即为服务组合问题的可行解，根据APN 的推理规则，找出最优解。从执行时间和查准率两方面进行了实验仿真，并与文献中提出的贪心法和近似法进行比较，实验结果表明该方法有较高执行效率和较高的查准率。科

●

【参考文献】

［1］吴迪, 陈钢. 新一代的Web Services 技术[J].计算机应用研究,2004,20(3):4-5,9．［2］柴晓路, 梁宁奇.Web Services 技术、架构和应用[M].北京:电子工业出版社,

Windows7。

仿真实验结果表明，采用基于GA 和APN 的方法，其执行时间明显低于贪心方法及近似方法，且当服务库中的服务个数越多时，效果越明显。由于在采用GA 方法搜索时，充分利用了APN 的性质，使得搜索空间大大降低，许多不符合约束关系以及无关联性和关联性较差的组件服务就不必进行组合，大大节省了执行时间，进而提高了服务匹配的时间性能。

2003．

［3］周明, 孙树栋. 遗传算法原理及应用[M].北京:国防工业出版社,1999,6.

［4］王小平，曹立明，遗传算法：理论、应用与软件实现[M].西安交通大学出版社，2002.

作者简介：罗柯（1982．2—），女，汉族，安徽阜阳人，2009年考入安徽理工大学理学院攻读应用数学专业硕士学位，从事Petri 网理论及应用方面的研究工作。

4结论

利用GA 方法并紧密联系Petri 网的性质，在APN 模型中搜索合

［责任编辑：王静］

刘跃虎, 等. 一种特征矩阵的相似性度量方法及其在图像［2］（上接第134页）

检索中的应用[J].模式识别与人工智能，2006,8(19).

Japan, 1998,27(5):533-539.

代西武.Dijkstra 矩阵算法[J].北京建筑工程学院学报, 2007,6(23).［5］

［3］Siroi. Pattern Understanding. Nagasaki. Japan; Ohm Publishers, 1987.

［4］Shiiyama H, Masaki K. Similar Image Retrieval Using Two Dimensional DP Matching Algorithm. The Journal of the Institute of Image Electronics Engineers of

［责任编辑：曹明明］

（上接第238页）考虑这些策略、交互使用，并结合学校组织的力量与教师个人的力量，才能有助于增进大学英语教师的专业成长，从而更好的服务于教育事业，为我国大学英语教育做贡献。科

2012(6).

［3］侯桂松. 知识管理与创新[M].北京：中国纺织出版社，2002：49-51.

［4］龙君伟. 校本人力资源开发与管理[M].广州：广东高等教育出版社，2006：274-279.

【参考文献】

［1］张璐. 浅谈教师知识管理[J ].科技信息，2011(23).

［2］周大明，周颖. 高中英语教师知识管理的现状调查和对策研究[J ].英语教师，

［责任编辑：王洪泽］