一种度量图像相似性和计算图编辑距离的新方法

A New Algorithm for Image Similarity Measure and Graph Edit Distance

由于在图编辑距离(GED)的计算中合理地为编辑操作定义代价函数相当困难,因此本文提出一种基于图结构的独立于代价函数定义的GED计算方法.它利用边缘方向直方图刻画图的结构,通过计算边缘方向直方图之间的距离来判断图的相异性,从而无需再定义代价函数.Earth Mover’s Distance(EMD)可以准确地计算直方图之间的距离,而且对于图在平面内的旋转所引起的直方图变化具有鲁棒性.为此,本文采用边缘方向直方图之间的EMD计算图编辑距离.将图像用图来表示,利用这种新的图编辑距离度量图像之间的相似性.实验结果表明本文提出的方法可以简单而有效地对图像进行聚类和分类,与基于谱序列计算图编辑距离的方法相比,可以更好地刻画图的结构差异.

For the difficulty of reasonably defining cost functions for edit operations in Graph Edit Distance（GED）,a purely structural method for GED computing is proposed which is thoroughly independent of cost functions.It makes use of Edge Direction Histogram（EDH）to characterize the structure of graphs,and estimates the dissimilarity of graphs by computing the distance of EDHs without defining cost functions.Earth Mover＇s Distance（EMD）examines histograms＇ distance exactly and is robust with respect to the diversification of histograms caused by rotating a graph in the same plane,so GED is measured by the EMD of EDHs in this paper.Images are represented by graphs and this new distance measure is used for examination of image similarity.Experimental results demonstrate that the proposed method is effective for classifying and clustering images.Compared with the GED from spectral seriation,the proposed method can capture the structure difference of graphs better.