CN1290061C - 一种利用显著边缘进行图像检索的方法 - Google Patents

Abstract

本发明涉及一种利用显著边缘进行图像检索的方法，适用于边缘比较清晰的图像。基本思想是对描述图像特征的边缘有所选择，采用显著边缘。其特征在于：首先对查询图像进行边缘检测和细化，获取边缘图；其次，使用独立边缘自增强方法，通过对边缘点反复地随即启发式搜索及增强，挑选出图像中的显著边缘；然后，对于每一条显著边缘使用三个典型特征，叉点率、转动频率和角点率来描述，进而生成图像的特征矢量；接着，在匹配时采用综合显著边缘匹配的方法度量图像间的相似程度；最后，根据相似度排序，输出相似图像集合。本方法相对于其它方法检索准确率较高；由于使用了显著边缘和“多对多”的匹配策略，因此具有较高的检索准确率。

Description

一种利用显著边缘进行图像检索的方法

所属技术领域：本发明涉及一种利用显著边缘进行图像检索的方法，属于计算机视觉、图像理解以及模式识别等领域。适用于边缘比较清晰的图像，检索边缘容易获取的图像设计的。

背景技术：自90年代以来，随着计算机技术、多媒体技术以及网络技术的飞速发展，越来越多的图像出现在人们的日常生活中。图像数据的爆炸性增长使得对图像的管理和检索成为关键。目前，许多图像检索方法都使用形状来描述图像的特征。形状是表征物体的本质特征之一，在很多情况下，人们往往单凭物体的形状信息就能识别物体，这是形状区别于其它视觉特征如颜色、纹理等的关键所在。目前应用于图像检索中的形状描述方法大致可以分为两类：基于图像边缘和基于区域。基于图像边缘的方法使用物体的边缘信息描述和查询图像，这类方法适用于图像边缘较为清晰，较为容易获取的图像。基于区域的方法主要依靠区域内象素的颜色分布信息来描述图像，这类方法对于区域能够较为准确的分割出来、区域内颜色分布较为均一的图像较为合适。

研究人员和技术人员提出了多种基于图像边缘的图像检索方法，但仍存在很多问题。方法1：首先提取边缘信息，每一条边缘都用一个多边形来近似，近似多边形的顶点来代表图像的形状信息。此方法的缺点在于：它要求边缘曲线闭合，而对于一般图像来说此要求很难达到。方法2：一种形状弹性匹配算法来进行图像检索，首先由人工指定感兴趣区域，在这些区域中采用爬山优化算法获取图像边缘，使用这些感兴趣区域内的边缘代表物体形状。这种方法的优点是对边缘进行了筛选，缺点是需要人工干预，在图像检索中这往往不太现实。方法3：使用草图进行图像检索，在他们的工作中，图像首先经过一系列的处理如尺度规格化、边缘检测、细化，然后简单地将获取的边缘图像和用户的草图根据模板进行匹配。方法4：采用边缘上的拐角点描述形状，其一、在拐点的基础上进行仿射变换，利用仿射不变特征来代表形状。其二、采用边缘点的相位直方图来刻化图像形状特征。其三、提出一种曲率尺度空间方法来描述形状，它对于每一条边缘曲线进行不同尺度下的高斯平滑，在每一尺度下提取曲率较大的点，选取在多尺度下生存时间最长的点来描述边缘曲线。上述的几种方法的共同缺点是：仅考虑了特殊的边缘点的信息，而这些边缘点并不能很好地刻画物体的形状。方法5：一种基于边缘的结构特征来描述形状，它使用“灌水_i±(Water-Filling)算法抽取边缘曲线，每一条边缘曲线用一些结构特征如：灌水时间、叉点个数、叉点直方图等来表示，而整幅图像的形状特征用几个“特殊”边缘曲线如：叉点最多边缘、灌水时间最长曲线等来刻化。这种方法的优点是：利用了边缘曲线的结构信息而非单个边缘点信息来表示形状，其缺点是：仅仅使用个别的边缘曲线，这些边缘曲线往往因为噪声或提取边缘过程的误差而不准确，这将会降低检索的准确率。方法6：一种基于傅立叶分析的方法，该方法首先获得一个能够描述形状的特征函数，如基于曲率的特征函数或基于半径的特征函数。然后对此特征函数作离散傅立叶变换，使用变换后的傅立叶系数作为形状特征来检索图像。这种方法对边缘点位置的微小变化和噪声相当敏感，因此，在实际检索中并不能取得很好的效果。方法7：三角形划分，首先选取图像边缘上的角点作为特征点，然后使用Delaunay三角形进行划分，可以记录三角形的形状特征来描述图像的形状特征。这种方法由于也基于边缘上的一些特殊点，所以也对于噪声和点位置的变化较为敏感。

目前已有的依靠边缘信息描述图像形状进而检索图像的方法具有以下两个主要的缺陷：其一、在利用边缘提取形状信息之前对边缘不进行分析和选择，大多数算法使用了图像中的所有边缘。图像检索的目的是为了搜索出相似的图像，而在实际处理中，由于边缘提取的不准确性和噪声的影响，并不是所有的边缘都会对描述图像形状和图像匹配产生积极作用；其二、在度量图像间的相似性时，采用了简单的“一对一”匹配策略。这种匹配策略计算相当简单，但是由于噪声的影响和边缘提取的不准确往往会使得抽取出的最长灌水时间边缘和最多叉点边缘不准确，直接导致误匹配的出现，从而影响检索的准确率。

发明内容：为避免现有技术的缺陷，本发明在系统地研究了基于边缘的形状特征的描述方法，及形状特征在图像检索中的应用，提出了一种基于显著边缘的图像检索方法。与其它的方法不同，我们认为最能够代表形状应当是的图像中的显著边缘，并且设计了一个独立边界自增强的算法来提取图像中的显著边缘。然后，我们使用三个特征来描述每一条显著边缘，进而形成图像的特征矢量。在度量图像间的相似度时，我们没有采用传统的“一对一”匹配准则，而是用了一种“多对多”的匹配准则，其目的是为了减少因为图像边缘提取不准对检索造成的不良影响。大量的实验证明，本发明所提出的方法相对于其它方法，具有优良的性能：1、由于使用了显著边缘，剔除短小的边缘，去掉了一个影响检索准确率的不利因素。同时也减小计算量，提高检索速度；2、采用“多对多”的匹配策略，能够从一定程度上减小边缘不准确的影响。

本发明的基本思想是对描述图像特征的边缘有所选择，采用显著边缘。它们对于尺度缩放、噪声、边缘提取不准确等都有一定的鲁棒性。显著边缘是指图像中视觉强度较大且长度较长的的边缘，其特征在于：首先对查询图像进行边缘检测和细化，获取边缘图；其次，使用独立边缘自增强方法，通过对边缘点反复地随即启发式搜索及增强，挑选出图像中的显著边缘；然后，对于每一条显著边缘使用三个典型特征，叉点率、转动频率和角点率来描述，进而生成图像的特征矢量；接着，在匹配时采用综合显著边缘匹配的方法度量图像间的相似程度；最后，根据相似度排序，输出相似图像集合。

独立边缘自增强是将独立的边缘点连接成边缘曲线，并对获取的边缘曲线进行适当的处理，为后续的显著边缘选择提供便利。该方法是：以边缘的强度信息作为引导度量，通过反复的随机启发式搜索获得各种可能的图像边缘，然后利用积累器对每一条独立边缘进行自增强，这样就使图像中的显著边缘得到了很大的增强，最后利用增强后的结果就很容易的选择到显著边缘。独立边界自增强方法的最大优点是：边缘增强的幅度与自身的显著程度成正比，因此，增强后的结果更有利于显著边缘的选择。此外，由于多次的随机启发式搜索使得提取边缘的过程受噪声影响较小。

由于Canny算子具有良好的定位和细化性能，所以本发明中的边缘检测采用Canny算子。边缘检测后的图像称之为边缘图(Edge map)，图中每一点的亮度代表了其边缘强度，亮度越大意味着边缘强度越大，可以发现灰度在局部发生突变的象素点。

图像特征矢量的生成：对于每一条显著边缘，采用三个典型特征，叉点率、转动频率和角点率来描述。

叉点率：边缘曲线的分叉点数目可以很好地衡量边缘的结构复杂程度。将每一条显著边缘对应到原始的边缘图中，沿着显著边缘的端点，进行“灌水”，定义分叉点数为当水流沿着边缘流动时分叉的总次数。则该条显著边缘的叉点率为：分叉的总次数//显著边缘的长度。对于显著边缘来说，它的叉点率越高说明它的结构越复杂。

转动频率：曲线的转动频率是用来描述边缘的弯曲程度。每一条显著边缘的转动频率为：该边缘发生转动的总次数//显著边缘的长度。转动频率越高表示此边缘曲线弯曲程度越大。

角点率：拐角点频率用来衡量边缘曲线的平滑程度。拐角点是边缘曲线上的一类重要的特殊点，拐角点越多说明边缘走向在局部变化越剧烈，边缘在整体上越不平滑。每一条显著边缘的角点率为：拐角点数目//显著边缘的长度。

规定在小范围的曲线段中，只能存在一个拐角点，小范围的像素点的数目取为5。

确定了每一条显著边缘的原始特征后，就得到一个图像的显著边缘集合，也就得到图像特征矢量。

由于采用叉点率、转动频率和角点率作为描述图像的原始特征，从曲线的结构复杂程度、弯曲程度和平滑程度三方面刻画了曲线特征，计算相当简单。这三个原始特征对于平移和旋转都不敏感，即满足平移和旋转不变性。至于尺度不变性，这对于用来进行图像检索的特征矢量来说是相当难满足的，由于我们的三个原始特征均使用了比率，所以能够满足形状描述子应当刻画图像特征准确、算法简单、易操作，还应当对旋转、平移、尺度缩放具有不变性这一性质。

在图像匹配时，图像之间的相似度一般由对应特征矢量之间的距离来度量，最终，距离最小的图像集合认为是相似图像。本发明关于图像匹配提出的综合显著边缘匹配方法没有采用传统的“一对一”匹配，而是放松了对于匹配的严格要求，它采用了一种“多对多”的匹配方案，一幅图像的一条显著边缘允许同另一幅图像的多条显著边缘相匹配，具体的匹配策略依靠两个准则来约束，即：重要度满足准则：和最相似最先匹配准则。图像间最终的相似度由所有有效匹配来决定。此方法的突出优点是：减小了因边缘提取不准确造成的误匹配，能够一定程度地提高检索准确率。

附图说明：

图1：本发明方法的基本流程图

图2：用系统进行举例查询的例子

图3：用系统进行举例查询的例子

(a)一幅用户手绘的草图

(b)根据用户手绘草图检索的结果

具体实施方式：

现结合附图对本发明作进一步描述：

根据本发明提出的基于显著边缘的图像检索方法，我们用C++语言实现了一个图像检索的原型系统。目前，我们的图像数据库中共有4500幅图像，这些图像包括：建筑物、风景、商标、图标、人脸等。图像的来源有：网上下载、Corel stock photo library抽取、数码照相机拍摄和Yale research Lab face database。我们图像数据库中的图像均为灰度图像且边缘都较为清晰。

假设一个待查询图像Q，在图像数据库中检索与Q相似的图像I，即：D(X_Q，X_I)≤t。上式中D是特征矢量的距离函数，t是由用户设立的阈值，X_Q是图像Q的特征矢量，X_I是图像I的特征矢量。两幅图像Q和I的相似程度可以用它们的特征矢量X_Q和X_I的距离来表示，距离越小表示两个图像越相似。查询的结果随着阈值而变化，始终满足与待查询图像的距离小于或等于阈值。用户可也以直接要求系统输出与待查询图像最类似的图像集合，如输出与待查询图像距离最近的20幅图像。

首先对图像Q进行边缘检测和细化，获取边缘图。然后用独立边缘自增强方法：即通过对边缘点反复地随即启发式搜索及增强，挑选出图像中的显著边缘。计算每一条显著边缘的叉点率、转动频率和角点率。假设一条显著边缘C_i，它的长度为l_i，由“灌水”算法计算出的分叉点数目为f_ci。则C_i的叉点率fr_i＝f_ci/l_i；转动频率rf_C＝rn_T/l_i，其中rn_T为边缘显著边缘C_i发生转动的总次数；当它的拐角点数目为cn_i时，则拐点率cf_i＝cn_i/l_i。

确定了每一条显著边缘的原始特征后，我们就可以得到图像的特征矢量。根据图像Q的显著边缘集合C＝{c₁，c₂，...，c_i，...，c_v，}，用f₁，f₂，...，f_i...，f_v分别表示显著边缘c₁，c₂，...，c_i，...，c_v的特征，则有：

f₁＝(fr₁，r_f，cf₁)，f₂＝(fr₂，rf₂，cf₃)，...，f_i＝(fr_i，rf_i，cf_i)，...，f_L＝(fr_v，rf_v，cf_v)

于是，图像Q的特征矢量 为： ${\stackrel{\‾}{f}}_Q=[f_1,f_2,...f_i,...f_v].$

进行图像匹配，采用综合显著边缘匹配方法，一幅图像的一条显著边缘允许同另一幅图像的多条显著边缘相匹配的“多对多”的匹配方案进行图像匹配。图像Q的特征矢量

为： ${\stackrel{-}{f}}_Q=[f_1,f_2,...f_i,...f_v],$ 那么图像Q’的特征矢量f_Q’为：f_Q’＝[f₁’，f₂’，...，f_j’...，f_v]’。以对应特征矢量之间的距离来度量，最终，距离最小的图像集合认为是相似图像。

本发明所实施的系统支持用户进行两种查询：举例查询(Query by example)和草图查询(Query by sketch)。举例查询是指由用户提供一个待查询图像，由系统自动输出与之相似的若干幅图像，相似图像的数目可以由用户指定，范围在0到100之间。草图查询是指由用户画出一幅草图提交给系统查询，同样地，用户可以指定系统输出若干数目的相似图像。在查询过程中，用户可以通过“双击”系统的输出图像来查看它的尺寸、来源等相关信息，用户也可以以某一幅查询结果图像作为例子图像进行新的查询。

图2给出了本章检索系统进行举例查询结果较好的一个例子，图像左上角的第一幅图像为查询图像，打“√”的表示正确的检索结果，而打“×”的表示错误的检索结果。图3给出了一个本章检索系统进行草图查询结果较好的一个例子，(a)中显示的图像是用户手绘的草图，(b)中的图像是检索的结果。

从实验结果看出：本方法提取的显著边缘比较符合人的主观判断；相对于其它方法检索准确率较高；由于使用了显著边缘和“多对多”的匹配策略，因此具有较高的检索准确率。

Claims (8)

1、一种利用显著边缘进行图像检索的方法，其特征在于：首先对查询图像进行边缘检测和细化，获取边缘图；其次，使用独立边缘自增强方法，通过对边缘点反复地随即启发式搜索及增强，挑选出图像中的显著边缘；然后，对于每一条显著边缘使用三个典型特征，叉点率、转动频率和角点率来描述，进而生成图像的特征矢量；接着，在匹配时采用综合显著边缘匹配的算法度量图像间的相似程度；最后，根据相似度排序，输出相似图像集合。

2、根据权利要求1所述的一种利用显著边缘进行图像检索的方法，其特征在于：独立边缘自增强方法：以边缘的强度信息作为引导度量，通过反复的随机启发式搜索获得各种可能的图像边缘，然后利用积累器对每一条独立边缘进行自增强，最后利用增强后的结果就很容易的选择到显著边缘。

3、根据权利要求1所述的一种利用显著边缘进行图像检索的方法，其特征在于：综合显著边缘匹配方法，采用了一种“多对多”的匹配方案，一幅图像的一条显著边缘允许同另一幅图像的多条边缘相匹配；具体的匹配策略依靠两个准则来约束，即：重要度满足准则和最相似最先匹配准则，图像间最终的相似度由所有有效匹配来决定。

4、根据权利要求1所述的一种利用显著边缘进行图像检索的方法，其特征在于：边缘检测采用Canny算子。

5、根据权利要求1所述的一种利用显著边缘进行图像检索的方法，其特征在于：将每一条显著边缘对应到原始的边缘图中，沿着显著边缘的端点，进行“灌水”，定义分叉点数为当水流沿着边缘流动时分叉的总次数，则该条显著边缘的叉点率为：分叉的总次数/显著边缘的长度。

6、根据权利要求1所述的一种利用显著边缘进行图像检索的方法，其特征在于：每一条显著边缘的转动频率为：该边缘发生转动的总次数/显著边缘的长度，转动频率越高表示此边缘曲线弯曲程度越大。

7、根据权利要求1所述的一种利用显著边缘进行图像检索的方法，其特征在于：每一条显著边缘的角点率为：拐角点数目/显著边缘的长度。

8、根据权利要求7所述的一种利用显著边缘进行图像检索的方法，其特征在于：规定在小范围的曲线段中，只能存在一个拐角点，小范围的像素点的数目取为5。

Images