基于四叉树结构的形状特征检索*

陈 慧 黄 堃 林 雯 林旭云

(福建江夏学院 福建福州 350001)

由于海量化的各种图像数据的迅速扩张，如何快速、有效地检索所需要的图像是当前图像应用领域的一个重要挑战，基于内容的图像检索是通过提取图像内容的特征作为索引来实现更高层次的图像检索[1]。在图像的诸多内容特征中，形状特征具备了不受目标颜色、纹理及背景变化影响的特点，在查询与目标图像具有类似形状为主要目的图像检索中，显示出了颜色和纹理特征所无以伦比的优势。基于形状特征的图像检索已经被广泛应用于许多专业领域，比如对医学图像、商标和徽标图像、陶瓷工艺图像和指纹图像检索等。目前这些特征提取大多是基于全局匹配的特征提取，强调整体图像的特点，忽略局部特征及局部图像间的空间关系，利用空间的局部信息来增强全局的形状特征的图像检索算法，不仅可以实现特征间的优势互补，还可以将多种视觉特征有效地整合到图像检索系统中，提高图像检索的质量和性能。

1形状特征表示方法

在二维的图像空间中，形状被认为是一个区域，由一条封闭的轮廓曲线组成。形状特征的提取必须满足独特性、完整性、几何变形后的不变性、灵敏度以及抽象性等特点，以下是几种典型的形状特征：

1.1 Hu不变矩

矩是一种数学表示，可以包含目标区域而不必先分离目标。由于低阶对量化误差和噪声不敏感，它为描述形状区域提供了虽不完全却有用的整体表示[2]。图像的矩特征是用一个全局量描述描述了整体对象的特点，具有很好的旋转，尺度缩放，平移不变性，是检索相似的图片的特征依据之一。设F(x，y)是一幅数字图像，其(p+q)阶矩定义为：

(1)

f(x ,y)的(p+q)阶中心矩定义为：

(2)

用图像的2阶和3阶规格化中心矩导出的由7个不变矩组成的不变矩组，称为Hu不变矩[2]。Hu不变矩具有的良好不变性，已被广泛应用于图像的识别和检索中。

1.2信息熵

在数字图像中，不同亮度的象素点在空间占据不同的区域，使得图像表现出不同的形状，用信息熵来描述图像形状。给定F(x,y)=0表示单元图像中背景空白的像素点，F(x,y)=1表示图像的实际像素点，图像子块的信息熵可定义为：

H(p0,p1)=-p0logp0-p1logp1

(3)

p1=∑∑F(xi,yj)/Size(i,j)；p0=1-p1

(4)

p1和p0是从单元图像中像素点的几何分布导出的。

对图像的每个子块计算其单元熵后，整幅图像的信息熵特征就可以用一个P×Q维的一维单元熵矢量来表示。

1.3偏心率

偏心率又称伸长度。偏心率Ec是指轴向的最大和最小的比率，描述图像区域的致密性。计算公式如下：

(5)

1.4圆形度

圆形度是定义边界点的特征量，测量的振幅反映边界的复杂性。该值越大，则形状越复杂。圆度特性不受地域的平移，旋转和缩放变化。子块的圆形度特征用ci=ui/σi来表示，ui表示子块重心至边界点的平均距离，σi表示重心至边界点的距离的均方差。

1.5相对位置

相对位置即分块重心到整幅图像重心的距离，表示如下：

(6)

2图像形状特征的四叉树表示方法

上述的图像检索方法是基于全局匹配检索，强调的是全局图像的特点，忽略图像的局部特征及局部图像间的空间关系。描述的图像局部特征与空间关系有两种方法：一种是自动分割图像形成区域，并根据这些区域建立索引，另一种是将图像均匀划分成若干规则块，然后对每个子块索引的图像特征提取法。

为了避免图像进行准确地自动分割的困难，同时又要结合图像的空间信息，一种折中的方法是将图像划分成多个子块，然后提取每个子块的各种特征。常用的方法有四叉树分块法，将整幅图像看成一个四叉树的结构，逐层进行图像分块，分别对每个子块图像采用相应适合的特征描述[3]。图像形状特征的四叉树方法体现为以下3部分：

2.1确定形状主方向

形状主方向取决于图像的形状特征，由图像的主轴方向与水平方向的夹角(记为β)决定[2]。主轴方向是指图像目标区域的最佳椭圆的长轴方向[2]，β是最大的特征值的向量方向，根据夹角β和三阶中心矩确定形状主方向，比较形状x>0与x<0两部分的能量，选择能量小的部分作为图像的形状主方向[3]。

2.2提取目标区域

将图像的主方向旋转到水平向右(即x轴的正方向)，以重心为原点，以形状方向为坐标系的x轴，与之垂直的方向为y轴建立坐标系，以坐标(xmin,ymin)为左上角，坐标(xmin,ymin)为右下角，构成一个最小外接矩形，该最小外接矩形为图像的目标区域。

2.3 四叉树分解

以图像的重心为中心，以水平方向和垂直方向为轴，将图像分解为4个一级子块B1～B4[3]，接着用4个分块图像的特征对图像的局部形状进行描述[4]。另外，以相同的方式对每个子块进行分解，进而得到16个二级子块B5～B20。经过两次这样的分解，可以得到总共20个子块[2]。以此类推，对每个二级子块进行分解，得到64个三级分块。将原图视为第0级子块，把0～3级子块加起来，图像共被分为85个子块[2]。因此，四叉树分解法使用的是由粗到细的逐层分解方式，利用空间局部信息增强全局形状特征描述，从而可以充分描述图像的空间分布信息。通过选择子块分割的层次，可以实现对子块数量的控制，以及对子块的图像内容描述的精确性的控制[3]。

3基于四叉树结构的形状特征检索算法思想及步骤

3.1四叉树结构的形状特征检索算法的基本思想

四叉树结构的形状特征检索算法的基本思想是：对图像进行分块，在进行子块分解时采用的是四叉树分解的方法，每个分块图像特征能够反映图像的局部特征，而多个子块的图像特征反映局部特征之间的空间关系的有序组合，从而反映图像的整体特性[4]。

3.2 算法设计[4]

①计算图像的形状主方向，根据其形状主方向对图像进行旋转, 去除图像旋转带来的变化。②提取图像目标区域，并对目标区域进行分块操作。四叉树结构的方法中定义的目标区域为目标像素的水平方向上图像的最小外接矩形，实现相对简单。③对图像分块，图像分块时采用由粗到细的分层次四叉树结构，实现多层次的描述。④分别提取分块图像的相应特征，定义原始图像为第0块子块图像，对第0块子块图像提取信息熵、偏心率、圆形度和Hu不变矩四个形状特征，接着对除了第0块子块图像外的其他的子块图像分别提取相对位置、信息熵、偏心率和圆形度四个形状特征。⑤根据提取的图像特征，采用欧氏距离[5]计算子块间的相似度，再通过加权法计算出总的相似度。设定待检图像T(a)和查询图像T(q)，计算两幅图像之间的相似程度为：

(7)

其中第k个子块图像形状特征的权值表示为wk，当两幅图像相同时，它们的相似性为1。因此两幅图像之间的特征距离越大，则图像的相似度越小。

4实验结果及分析

为了测试提出的四叉树分块图像检索方法的有效性，基于Window平台上的VisualC++开发实现该算法。图像库的建立分3个步骤完成，首先图像库由从网络搜索的各种图像共600幅组成。其次，为了提高图像检索效率，需要对图像进行一些预处理，如转换格式，噪声过滤等。转换格式的软件可以将图像库中的图像转换成统一的格式，如bmp位图格式的图像源，而噪声滤波则采用一些有效的滤波算法。最后，确定图像数据库的存储位置，所有图像统一置于操作系统一个共同的文件夹内。实验分为3部分，即几何变形实验，尺度和旋转不变性实验，以及视觉一致性实验。实验系统实现本文提出的基于四叉树分块的图像特征检索算法，并在实验中采用了多种性能评价方法以验证实验的有效性，如体现检索精度P和检索回召率R的PVR指数、用户参与评价等。

4.1几何变形实验

为了研究基于分块图像特征的检索方法对于几何变形图像的检索能力，对原始图像做多种变形，随机从图像数据库中选择10个目标图像作为查询图像进行检索[5]，图像编号1～10，分别为设置图像旋转100%、图像旋转-100% ，波纹效果20%、波纹效果-20%、图像缩放30%、图像缩放-30%、图像球形化效果40%、图像球形化效果-40%、图像缩放50%、图像缩放-50% 。检索结果的PVR指数如表1所示。

表1 几何变形实验的图像检索PVR指数(%)

显然，对于变形图像的检索能力，四叉树分块图像特征的方法相对于Hu不变矩较令人满意，平均PVR指数达到91.46%，高于Hu不变矩的平均PVR指数83.30% 。

4.2尺度和旋转不变性实验

随机从图像数据库中选择10个目标图像，并对每幅目标图像进行多比例图像缩放和多角度旋转。分别采用基于Hu不变矩的图像检索法和基于四叉树分块的图像特征检索法，在每次检索时，将目标图像及其相应的缩放和旋转图像都添加到图像数据库，共同参与图像检索[4]。检索结果显示基于Hu不变矩检索法的平均PVR指数为98.03%，低于基于四叉树检索法的平均PVR指数99.62%。

4.3视觉一致性实验

图像的视觉一致性实验，是用来验证图像的检索结果是否符合人的视觉感知，采用用户参与评价法，即人眼所看到的检索结果图像与要查询的图像是否相似。每次从建立的图像库中任意选择一幅图像作为样本，检索结果将返回前14 幅与样本图像相似度最大的图像，返回的第一幅图像就是样本图像。

图1给出了五角形图像的检索结果。图1(a)为基于Hu不变矩的检索结果，其中第1, 13和14幅与目标图像相似，图1(b)为基于四叉

树分块的检索结果，其中仅第12，13，14幅图像与目标图像差距明显，而其它图像都与目标图像有着不同程度的相似。

4.4结论

实验结果表明，基于四叉树的分块检索方法在以上3个方面的表现都优于HU不变矩，可以全面准确而且多层次的描述图像的形状信息和空间分布的信息，可以同时体现图像的整体形状和局部形状，检索结果更符合人类视觉感知[4]。

基于四叉树分块图像特征的图像检索方法通过利用全局和局部特征，可以更好地描述图像的内容[4]。另外，子块由粗到细的分层结构，可用于描述若干层次的图像的特征的形状，以提高图像检索的性能[2]。因此，该方法对于形状较明显的图像比较适用，对于形状特征不明显的图像，则检索精度不高。

参考文献：

[1]黄赛平.基于文本和内容的商标图像检索[D].南京：南京理工大学，2008.11.

[2]杨青燕.基于内容的商标图像检索研究与实现[D].济南：山东科技大学，2009.13.

[3]张玲.商标图像检索研究与系统实现[D].长沙：湖南大学，2006.6.

[4]郭丽.基于内容的商标图像检索研究南京：南京理工大学，2003.2.

[5]褚菁菁.基于内容的二值商标图像检索技术研究[D].郑州：河南大学，2011.5.