摘要:分析目前MPEG.�7标准下对纹理特征提取的研究，在边缘直方图描述符的基础上，借鉴马尔可夫链的思想，提出了马尔可夫边缘描述符。该描述符使用马尔可夫链的初始分布表征同种类型边缘之间的空间分布信息，采用马尔可夫链的极限分布来表征不同类型边缘之间的空间分布信息。实验表明，马尔可夫边缘描述符在具有直方图描述符优点的基础上，可以很好地捕获图像边缘的空间信息，对同种或不同种边缘类型间的空间分布都有较好的检索效果，检索效果优于边缘直方图描述符。
关键词:基于内容的图像检索；特征提取；MPEG.�7；马尔可夫链；边缘描述符�
中图分类号: TP312；TP391.41文献标志码:A
�
Markov edge descriptor for feature extraction algorithms of image
�
CUI Ning.hai��*, LIU Li.ping
College of Information Science and Engineering, Shenyang Ligong University, Shenyang Liaoning 110159, China
Abstract:
After analyzing the texture feature extraction on MPEG.�7 standard, a new Markov Edge Descriptor (MED) was proposed base on Edge Histogram Descriptor (EHD), which was in virtue of the Markov chain. It adopted initial distribution of Markov chain model to represent the spatial information between the same kind of edges. And it adopted stationary distribution of Markov chain model to represent the spatial information between the different of edges. Experimental results show that MEDhas the merits of EHD, and MED can describe the spatial information between the image edges. It has corking retrieval performance for the same or different kind of edges. Its retrieval performance is better than EHD.
After analyzing the texture feature extraction on MPEG.�7 standard, a new Markov Edge Descriptor (MED) was proposed based on Edge Histogram Descriptor (EHD), which was in virtue of the Markov chain. It adopted initial distribution of Markov chain model to represent the spatial information between the same kinds of edges. And it adopted stationary distribution of Markov chain model to represent the spatial information between different edges. The experimental results show that MED has the merits of EHD, and MED can describe the spatial information between the image edges. It has corking retrieval performance for the same or different kinds of edges. Its retrieval performance is better than EHD.
�Key words:
content.based image retrieval; feature extraction; MPEG.�7; Markov chain; edge descriptor
�
0 引言�
目前，在MPEG.7�［1］多媒体内容描述接口(Multimedia Content Description Interface，MCDI)标准下，对图像颜色和纹理特征提取的研究取得了很大的进展。对于边缘直方图描述符的提取方法，文献［2］提出了全域和半全域边缘直方图的概念，将边缘直方图的维数扩展到了150维。文献［3］在边缘直方图描述符的5种边缘类型基础上，将边缘类型分为6种，然后构造局部和全局边缘直方图描述符。文献［4］结合边缘信息与彩色直方图提出一种基于边缘彩色直方图的图像检索算法。文献［5］在边缘直方图描述符基础上，提出了一种游程编码直方图方法。文献［6］提出了一种边缘能量描述符。在文献［7］中，边缘直方图描述符与�K�.近邻算法相结合，实现了对矿物图像的分类。在文献［8］中提出了一种基于内外边缘颜色特征的图像检索算法。虽然以上几种边缘特征提取方法使检索精度得到一定的提高，但实际上它们仍然基于边缘直方图的思想，无法全面地获得边缘的空间分布信息，只能以累加个数的方式获得图像中边缘的信息。Pianpian等�［9］提出了一种用共生矩阵方法表示边缘信息的方法。该方法虽然能够获得边缘空间分布信息，但它占用存储空间大，抗干扰性差。根据以上分析，研究出一种包含边缘分布信息、存储空间小、抗干扰性强的边缘特征提取方法具有重要意义。本文在分析边缘直方图描述符的基础上，提出了马尔可夫边缘描述符(Markov Edge Descriptor,MED)，它使用马尔可夫链的初始分布和极限分布来表征图像中边缘的空间分布信息。�
1 边缘直方图描述符�
边缘直方图描述符(Edge Histogram Descriptor，EHD)是MPEG.�7标准推荐的一种纹理描述符，采用直方图的方法累加不同类型的边缘出现的次数，用以表征图像的纹理特征。�
边缘直方图描述符中定义了5种类型的边缘，分别为0°，45°，90°，135°边缘和无方向边缘�［10］，边缘直方图描述符对图像中的5种边缘进行累加，生成边缘直方图，用以表征一幅图像的边缘分布特征。纹理空间选择是将RGB彩色图像空间转化到灰度空间。灰度是指黑白图像中点的颜色深度，灰度图像中的每个像素都有一个0(黑色)到255(白色)之间的亮度值。彩色图像可以方便地通过RGB空间到灰度空间的转换，变成灰度图像�［11］。�
虽然直方图方法具有计算快速、空间利用率高、抗干扰性强等优点，但由于它不能捕获任何空间信息，在使用中有很大的局限。如图1所示，两幅图像都具有2种类型的边缘，每种类型的边缘个数也相等，但在空间分布上有较大差异。图像中A区域表示135°边缘的分布区域，B区域表示45°边缘的分布区域，对这两个图像累加得到的边缘直方图相同，但图像中的内容是有很大差异的。边缘直方图描述符无法获得同种边缘的空间分布信息，导致了图像匹配过程中出现误差。�
图2中A区域表示135°边缘的分布区域，B区域表示45°边缘的分布区域，C区域表示垂直边缘的分布区域。对两个图像进行边缘直方图累加，得到相同的结果，但实际上45°边缘和垂直边缘在空间分布上是有差异的。这种误差是由于边缘直方图缺乏对不同类型边缘之间的空间分布信息所导致的。�
图2 需要不同边缘的空间信息来区分的两幅图像�
根据以上的分析，本文在马尔可夫链(Markov chain)的基础上提出一种新的纹理描述符――马尔可夫边缘描述符(Markov Edge Descriptor, MED)。�
2 马尔可夫边缘描述符�
2.1 边缘类型共生矩阵�
共生矩阵是图像的纹理分析中十分重要的概念，它使用两个位置的像素的联合概率密度来定义。任何图像表面都可以看成三维空间中的一个曲面，在三维空间中，相隔某一距离的两个像素，它们具有相同的灰度级，或者具有不同的灰度级，若能找出这样两个像素间的联合分布的统计形式，对于图像的纹理分析是很有意义的。�
本文基于共生矩阵的思想，提出边缘类型共生矩阵的概念。对于边缘直方图描述符中定义的5种边界类型，使用5个数字对其表示，0表示垂直边缘，1表示水平边缘，2表示45°边缘，3表示135°边缘，4表示无方向边缘。�
边缘类型共生矩阵包含了丰富的边缘空间分布信息，如果直接使用它进行图像匹配需要巨大的空间代价，而且它对图像的噪声非常敏感，最关键的是，它不能解决图2中所示的问题，即不能获得不同边缘之间的空间分布信息。�
�对于边缘类型共生矩阵E�ij，可以从统计学的角度进行分析。当边缘E�i和E�j的共生值较大的时候，说明边缘类型从E�i转化到E�j的概率比较大。�根据以上分析，本文使用马尔可夫链来表征边缘之间的空间分布关系，将5种类型的边缘看做是马尔可夫链模型中的5种状态，由边缘类型共生矩阵获得5种状态的转换概率。这样，比较两幅图像的边缘就转换成了比较对应的马尔可夫链。�
2.2 马尔可夫链�
在物理学中，很多确定性现象遵从如下演变原则：�过程(或系统)在时刻t�0所处的状态为已知的条件下，过程在时刻t>t�0所处状态的条件分布与过程在时刻t�0之前所处的状态无关，这种情况称为马尔可夫性或无后效性。时间和状态都是离散的马尔可夫过程称为马尔可夫链，简称马氏链。�
本文中边缘类型共有5种，定义状态空间为E={e�0,e�1,…,e�4}。从边缘e�i直接转化到边缘e�j的概率为p�ij=P(X�1=c�i|X�2=c�j)，马尔可夫一步转移矩阵为P=(p�ij)�5×5。�根据上文的分析，可以由边缘类型共生矩阵得到一步马尔可夫转移矩阵，计算公式如下：�