ABSTRACT

Image shape feature’s extraction is an important research content in content-based image retrieval, and an image shape feature extraction method by using complex network model is proposed in this paper. First, SIFT keypoints of an image are extracted, and then the image is divided into blocks such that the initial complex network model can be built in each block respectively. After that, minimum span ning tree decomposition method is used for the network’s dynamic evolution, and the network features at different moments in different blocks are extracted as the image’s shape features. Furthermore, the shape features are combined with the color and texture features and a kind of fusion feature is obtained. By experiment results comparison, it shows that the fusion feature does have advantages in CBIR.

Keywords:Content-Based Image Retrieval, Complex Network, SIFT Keypoints, Topological Structure, Multi-Feature Fusion

基于复杂网络的图像特征提取及多特征融合方案探究

高剂斌^1,2，李裕梅^1*，张慧娜¹

¹北京工商大学理学院数学系，北京

²桂林理工大学理学院，广西 桂林

Email: ^*liwjyumei@163.com

收稿日期：2015年10月3日；录用日期：2015年10月16日；发布日期：2015年10月21日

摘 要

图像形状特征的提取是图像检索中重要的研究内容，本文提出一种基于复杂网络模型的图像形状特征提取方法。提取图像的SIFT关键点，在此基础上进行分块处理并逐一在每个子图上面构建复杂网络初始模型，利用最小生成树分解的方法对网络进行动态演化，提取不同子图不同时刻下的网络特征作为形状特征。本文将形状特征与颜色特征、纹理特征进行融合，通过实验比较，说明此融合方案在CBIR应用中确实具有优势。

关键词 :基于内容的图像检索，复杂网络，关键点，拓扑结构，多特征融合

1. 概述

目前，复杂网络在图像特征提取中的应用受到了越来越多研究者的关注 [1] 。Goncalves等人通过对人脸图像建立复杂网络模型，实现了人脸图像的特征提取与识别 [2] 。Backes等人利用复杂网络模型对文理图像进行建模，然后利用复杂网络的常用统计量进行描述并分类 [3] 。该方法提取到丰富的纹理图像特征，对纹理图像具有较高的分类精度。Tang等人通过对图像的结构进行分析，建立了复杂网络模型，实现了不同结构图的识别及分类 [4] 。Backs等人利用复杂网络的方法进行形状边界分析 [5] ，进一步又提出了将复杂网络与多尺度的分形维数相结合来进行形状分类 [6] 。该方法中的复杂网络模型表示都是基于形状边缘点之间的欧式距离。但研究表明，上述方法往往受一些非刚性变形的影响较大、稳定性较差、抗噪声能力较弱，因此图像形状特征的提取在基于内容的图像检索中具有了重要的研究意义 [7] [8] 。对于形状特征的提取主要可以基于轮廓形状 [9] [10] 、基于区域形状以及基于关键点 [11] [12] 。基于关键点的形状特征提取，一般是先对图像提取一些关键点，如Harris角点、SIFT关键点等，然后根据关键点建立加权网络，其中图中的顶点表示每个关键点，而图的表示图像关键点之间的空间距离关系，边的权值表示所连接顶点之间的欧式距离。由于任意两点之间存在边相连接，所以该网络是一个完全图，然而这种完全图并不具有明显的拓扑结构特征，因此，很难实现对多幅不同图像的特征提取。本文为了解决这一问题，对该网络进行基于边的权值动态演化，可以得到一系列子图，联合这些子图的拓扑特征，将最大度、平均度、平均联合度、平均最短路径长度、平均聚类系数作为特征，来实现图像的形状特征提取。由于基于复杂网络的形状特征提取是根据统计特征得以实现的，因此这种形状特征具有稳定性好、抗噪声能力强等优点。

本文在上述形状特征提取的基础上，实现形状、颜色、纹理多特征融合。其中颜色特征选取HSV颜色直方图并结合动态金字塔技术，从原图像以及不断进行动态变换后得到的图中共同提取HSV颜色直方图进行统计作为本文实验的颜色特征，纹理特征选取HOG描述器并结合3D-LBP技术，首先将图像进行3D-LBP处理可以得到三幅新的图像，再利用HOG描述器从原图像以及衍生出三幅图像中提取特征作为纹理特征。实验过程中，还涉及到主成分因子分析PCA降维等技术的运用。实验选用大家公认的图像检索测试图片库Corel 1000 database为平台(共10个类，每类100幅图片)，通过检索性能来评价本方案的特征融合的优劣。

2. 基于复杂网络的图像特征提取

2.1. 特征描述与动态演化

复杂网络存在大量的特征描述，本文选取了最大度、平均度、平均联合密度、平均最短路径长和平均聚类系数这些特征来度量复杂网络的重要属性。

演化是复杂网络的一个重要特征，在动态演化下，复杂网络的特征是一个关于时间的函数，在同一种演化方式下的两个网络具有不同的特征 [8] 。所以，应用网络演化过程中不同时刻的相关度量来进行图像形状特征提取是非常关键的。

2.2. 利用图像关键点构建复杂网络

本文在提取关键点时，采用的是SIFT提取算法。对图像的SIFT关键点建立加权复杂网络模型：，其中代表网络中的定点，表示的是图像中的关键点，代表网络中的边，表示图像关键点之间的空间距离关系，而边的权值为所连顶点之间的欧式距离。由于任意两点之前均存在边相连接，故该复杂网络是一个完全图。这种完全图并不具有明显的拓扑结构特征，所以很难实现对图像的形状特征提取。

2.3. 复杂网络的动态演化实现

为了解决这一问题，文献 [9] 使用了边的权值对上述完全图进行动态演化得到一系列子图，并根据这些子图对完全图进行动态演化得到一系列子图，并根据这些子图实现对完全图的特征提取。但这种方法存在弊端，因为在动态演化过程中很难保证各个子图相联通，进而对子图提取特征常带来一定困难。因此，本文在文献 [9] 的基础上，先将图片进行分块处理，再利用最小生成树分解的方法给出一种全新的动态演化方案，详细步骤如下：

其中，是最小生成树算法，，为初始的完全图，是第次动态演化得到的最小生成树，是第次动态演化得到的子图，为相对于的补图。

图1展示了图像关键点分块到建立复杂网络模型再到进行动态演化的全过程。首先对图片进行SIFT关键点提取，再将提取好的关键点进行分块处理，这样可以使得特征提取效率大大提高，然后逐一对分块子图中的关键点建立复杂网络模型，并根据最小生成树进行动态演化，最后从各个演化网络拓扑结构中提取形状特征。

2.4. 基于复杂网络拓扑结构的特征提取

根据各个分块子图动态演化过程中得到的，分别计算以下特征值：最大度、平均度、

图1. 关键点分块及其复杂网络建模动态演化

平均联合度、平均最短路径长和平均聚类系数。再将不同分块子图的不同动态演化时刻下对应各个网络特征值串联起来，组成特征向量。

如图1分块子图A的形状特征可由特征向量：

(1)

表示，其中分别对应分块子图各动态演化时刻的最大度、平均度、平均联合度、均最短路径长和平均聚类系数。而特征向量则可以表示该图像的形状特征。在本文中，令，故运用上述提取方法，一副图像可获取270维的形状特征。

3. 多特征融合

3.1. 三维局部二值模式(3D-LBP)

本文在进行颜色和纹理特征提取时，选用三维局部二值模式(3D-LBP)，该模式较通常的一维局部二值模式(LBP)有较大改变，一维局部二值模式是通过原始图像的邻域像素值得计算生成一幅灰度图像，再根据灰度图像提取纹理特征。而三维局部二进制模式(3D-LBP)则是通过原始图像的邻域像素计算生成三幅新的彩色图像，再从彩色图像中提取出颜色和纹理特征 [13] - [15] 。

3D-LBP算法描述：对于一幅图像，是任意像素点的邻域，是中间像素点，它的灰度值被用来作为阈值。像素点邻域的其他像素点被定义为，其中是用来标记邻域像素点。中心像素点对应LBP值的计算方法如下：

(2)

其中和分别是像素点及其邻域的灰度值。是一个阈值函数定义如下：

(3)

LBP算法相对容易实现，因为在(2)式中LBP算法只需要中心像素与其相邻像素的灰度值差值来计算。图2左边是一幅灰度图像，右边是它的LBP图像，而在中间有两个的矩阵则是以灰度值为207的中心像素为例，详细介绍了LBP算法。中心像素作为一个阈值的函数，并在右侧的矩阵中揭示了通过中心像素与其相邻像素之间灰度值的差异来进行阈值去噪的过程。通过(2)式和(3)式，可以得到一个阈值为207的符号函数，进而得到LBP的二进制代码为00001111，其对应于的十进制数为15。

但是，由于LBP算法是在灰度图上进行的，并未携带颜色特征，所以在对于某些对象和场景的图像检索中性能较差 [16] - [18] 。而三维LBP的算法则与传统的LBP算法不同，该算法是在彩色图像上进行的，因此携带了颜色的特征。对于一幅彩色图像，3D-LBP算法可以理解为通过三个立体的LBP算法生成三幅彩色图像。图3展示出一幅彩色图像，进行三维LBP算法的方法及过程，最终生成了三幅彩色图像。3D-LBP中第一个LBP算法，适用的邻域为的矩阵，算法依据图3第一行中间图片所示，首先将彩色图像的分为R、G、B三个分量进行LBP计算，然后再将三个运算后的分量进行组合，形成一个新的彩色图像，如图3中第一行最后一幅所示，该图像与原始彩色图像相比，缺少了最外面一圈像素点的灰度值。第二个LBP算法，适用的邻域为的矩阵，算法依据图3第二行中间图片所示，将R、G、B的三个分量的像素点依次按行进行组合并进行LBP计算，将三个运算后的分量进行组合后得到新的彩色图像，如图3中第二行最后一幅所示，该图像与原始图像相比，缺少了首列和尾列两列像素点的灰度值。第三个LBP算法，同样适用的邻域为的矩阵，算法依据图最后一行中间图片所示，将R、G、B的三个分量的像素点依次按列进行组合并进行LBP计算，将三个运算后的分量进行组合后得到新的彩色图像，如图3中最后一行第三幅图片所示，该图像与原始图像相比，缺少了首行和尾行两行像素点的灰度值。

通常情况下，一幅彩色图像由RGB三个平面构成，在执行3D-LBP算法时，需要将三个平面扩充到五个，只需要复制R、B两个平面即可，使一幅彩色图片由BRGBR五个平面构成，对BRG运用算法，可以得到新的R平面，同理分别对RGB、GBR运用3D-LBP算法得到新的G和B平面，再将新平面组合最终成为图3中最后一列的三幅图像，以便于进而提取图片的特征。3D-LBP与传统LBP算法相比，增强了图像垂直和水平方向的局部特征。

3.2. Harr小波变换

当通过3D-LBP得到三幅彩色图像后，完成了特征提取的第一步，下面还需要继续图像进行预处理，主要会用到Harr小波变换的方法。Harr小波变换 [19] ，通过提高彩色图像各分量的局部对比度，以达到提取局部信息的目的。Harr小波转换 [20] 是于1909年由Alfréd Haar所提出，是小波转换(Wavelet transform)中最简单的一种转换，也是最早提出的小波转换，它是Daubechies小波变换的N = 2的特例。Harr小波变换相对于其他小波变换有算法简单、计算效率高等优点。

通过Haar小波变换可以将一幅灰度图像分解成低通低通(LL)、高通低通(HL)、低通高通(LH)和高通高通(HH)四部分。如图4所示，首先将一幅彩色图像分离成R、G、B三幅灰度图，运用Harr小波变换将灰度图像分别分解成LL、HL、LH、HH四幅图片，再分别将由R、G、B灰度图分解后得到的四幅图片进行组合，最后得到的图片如图4中最后一列所示。通过观察可以发现，该图像LL为彩色图像，用于后续的颜色特征提取，LH、HL、HH均为黑白图像，其中LH、HL纹理特征明显、形状清晰，用于后续纹理特征的提取，由于HH图像内容较为模糊，故在后续实验中不做考虑内容。

3.3. 颜色特征提取

颜色直方图是提取颜色特征最常用的方法之一，其核心思想是在一定的颜色空间中对图像中各种颜

图2. 以阈值为207的点为例,展示灰度图像成为其LBP图像的过程

图3. 3D-LBP图像的描述

图4. Harr小波变换示意图

色出现的频数进行统计。计算颜色直方图需要将颜色空间划分为若干个小的颜色区间，每个区间成为直方图的一个柄，这个过程称为颜色量化。按照人的视觉分辨能力，把色调H分成8份，饱和度S分成4份，亮度V分成2份，并根据色彩的不同范围进行非等间隔量化，量化后的色调、饱和度和亮度值分别为，将HSV空间划分成了个区间。这样对H、S、V进行量化，可以得到下列计算式：

(4)

在运算过程中，对 三维特征矢量取不同的权值，进而组合成一维特征矢量便于计算。在这三个矢量中，人眼对于颜色的划分主要是根据色调，其次是饱和度，最后是亮度，故加权后得到一维矢量：

(5)

其中，和分别是S和V的量化级数。若取，上式可表示为：

(6)

L的取值为，计算L可以得到64柄的一维直方图，而H、S、V三个分量也通过L在一维矢量上分布开来。色调H取的权重取为8，饱和度S的权重取为2，亮度V的权重取为1，这就大大减轻了图像亮度V对检索结果的影响，而且也削弱了饱和度S对检索结果的影响，却能够对颜色分布不同的图像得到较好的检索结果。

LL的颜色特征提取还需要运用到动态金字塔理论。首先，将LL图像压缩成方阵，进行HSV空间颜色特征提取，得到64维特征。再将压缩后的方阵进行减半处理，行列分别交叉进行选取。本文将LL图像缩减3次，分别在HSV空间提取颜色特征，得到192维特征，加上原始LL图像的64维颜色特征，共256维。

3.4. 纹理特征选取

本文选取的纹理特征为Histogram of oriented gradients (HOG)。HOG描述器最重要的思想是：在一幅图像中，局部目标的表象和形状能够被梯度或边缘的方向密度分布很好地描述。具体的实现方法是：首先将图像分成小的连通区域，我们把它叫细胞单元。然后采集细胞单元中各像素点的梯度的或边缘的方向直方图。最后把这些直方图组合起来就可以构成特征描述器。为了提高性能，还可以把这些局部直方图在图像的更大的范围内进行对比度归一化，所采用的方法是：先计算各直方图在这个区间中的密度，然后根据这个密度对区间中的各个细胞单元做归一化。通过这个归一化后，能对光照变化和阴影获得更好的效果。

在本文实验中，将灰度图像分割共9个区域，每个区域的直方图梯度等级分为9级，这样每幅图像的形状特征为81维。针对前面叙述的Harr小波波变换理论，如图5所示，将LL彩色图像分离成R、G、B三个灰度图像，分别用HOG描述器提取形状特征，可得到维特征，将LH、HL彩色图像直接转化成灰度图像，再用同样方法提取形状特征各得到81维特征。

图5. Harr小波变换后通过HOG描述器提取形状特征示意图

3.5. 多特征融合

一幅彩色图像通过关键点复杂网络建模及动态演化可得到270维形状特征，经过SIFT关键点经过3D-LBP算法可得到三幅彩色图像，而每幅彩色图像经过Harr小波变换后，能提取出256维的颜色特征以及405维的纹理特征。综上所述，一幅彩色图像原图加上通过3D-LBP得到的三幅图像，共能提取出2914维特征。再通过利用PCA对2914维特征数据进行降维，最终得到165维特征，此时特征贡献率可达到85%以上。

4. 实验

实验图像数据库：采用Corel数据库，该数据库包含1000幅图像，图像大小为或。图像共分为10类，每类100张，按语义可分为：非洲(Africa)、海滩(Beach)、城堡(Buildings)、公交车(Buses)、恐龙(Dinosaurs)、大象(Elephants)、花(Flowers)、马(Horses)、山(Mountains)和食物(Food)。

本文相似性度量使用的是Euclidean距离。先将各个向量进行归一化，后通过计算特征数据之间的Euclidean距离，根据距离数值从小到大将各个图像进行排列，若距离越小，则可以认为两幅图像越相似。

检索性能参数选用查全率、查准率。查准率指的是检索结果中相关图像数与检索结果集合中的所有图像数(包括相关图像和不相关图像)的比值。在CBIR系统返回的检索结果中，相关图像数越多，则查准率就越高。查全率指的是系统返回的检索结果结合中，相关图像数与图像库中所有相关图像数的比值。查全率和查准率越高，则该CBIR系统检索性能就越好。

图6展示的是本文方案查准率与查全率变化曲线。通过比较图6与文献 [21] ，本文方案优于文献 [21] 中方案。本文特征不仅基于复杂网络提取了图片的形状特征，而且还通过3D-LBP及Harr小波变换分别提取了颜色特征和纹理特征，因此检索效果较好。

图6. Precision-Recall曲线

5. 结论

本文给出了一种基于复杂网络模型的图像形状特征提取方法。提取图像的SIFT关键点，在此基础上进行分块处理并逐一在每个子图上面构建复杂网络初始模型，利用最小生成树分解的方法对网络进行动态演化，提取不同子图不同时刻下的网络特征作为形状特征。除此之外，本文还实现了形状特征与颜色特征、纹理特征进行多特征融合。颜色特征选取HSV颜色直方图并结合动态金字塔技术，从原图像以及不断进行动态变换后得到的图中共同提取HSV颜色直方图进行统计作为本文实验的颜色特征，纹理特征选取HOG描述器并结合3D-LBP技术，首先将图像进行3D-LBP处理可以得到三幅新的图像，再利用HOG描述器从原图像以及衍生出三幅图像中提取特征作为纹理特征。实验表明，利用融合后的方案进行图像检索，与现有传统特征相比，本文方案检索效果更好，充分说明多特征融合在CBIR应用中确实具有优势。

基金项目

国家自然科学基金(11101012)，北京工商大学学科建设与研究生教育专项(2015XWYJS018)。

文章引用

高剂斌,李裕梅,张慧娜. 基于复杂网络的图像特征提取及多特征融合方案探究
Image Feature Extraction Based on Complex Network and Multi-Feature Fusion Schemes Exploration in CBIR[J]. 图像与信号处理, 2015, 04(04): 101-110. http://dx.doi.org/10.12677/JISP.2015.44012

参考文献 (References)