基于提升小波和双树复小波的图像检索新算法

舒彬

(陕西学前师范学院 数学系,陕西 西安 710100)

基于提升小波和双树复小波的图像检索新算法

舒彬

(陕西学前师范学院 数学系,陕西 西安 710100)

由于提升小波的高效性,双树复小波的多方向选择性等特点,所以本文提出了一种新的检索算法:基于提升小波和双树复小波变换的图像检索算法。此算法首先对图像分别进行提升小波和双树复小波变换,得到每层各个方向上的高频子图像;然后将各层上各方向的高频子图像组合,提取它们的纹理特征;最后通过计算特征向量之间的canberra距离,检索出相似度高的图像。实验结果说明,此算法的检索效率高于提升小波和双树复小波的算法。

提升小波; 双树复小波;纹理特征; canberra距离;图像检索

由于计算机技术突飞猛进地发展,海量的图像数据不断地涌现,如何快速准确地检索出用户所需要的图像数据,已成为研究人员的热门课题。纹理是图像明显而稳定的性质,能表达图像中像素的灰度空间的分布现象,方向性为纹理的非常重要的性质,如果能提取到很多的方向信息,将有助于提高纹理识别的效率。迄今为止,已有很多研究者将小波理论应用到图像得特征提取中。因为,小波变换具有很好的时(空)频域性,将小波变换应用到图像处理中,此时,图像信号将由时间域(空间域)转换到小波域表示。可以利用小波变换的正交／双正交的变换特性,将图像的像素间的相关性消除。从而降低了图像信号在空间中的冗余。由于传统的卷积小波(第1代小波)变换过程的复杂,运算的量大,实时性比较差,20世纪90年代,小波提升算法(lifting scheme)或称为自举法[2]由Sweldens提出,完成了空间域上小波的构造完全。提升小波变换又称作第二代小波变换技术,和经典的Mallat算法相比较,它可以实现小波变化的原位计算;且其减少了一半的运算量;整数到整数的小波变换容易实现,会极大地减少计算的时间和空间的复杂度。所以,应用提升小波变换对图像进行分解,将有利于缩短检索的时间,提高准确率。因为传统的小波变换具有有限的方向性,进行纹理特征描述时不够充分,因此一种双树复小波变换(Dual-tree Complex Wavelet Transform,DT-CWT)[3]信号分析方法由Kingsbury[4]提出,它建立在实数小波理论框架的基础上,具有如下优点:良好的多方向选择性,近似的平移不变性,计算量很小,有限的冗余度,因为这些优点,方便了纹理特征的提取。

1 小波变换的提升实现

1.1 db2小波变换的提升理论[5]

基于提升格式的小波变换,在对系统内存需求以及变换实现的复杂度等方面都是一种非常有效的实现形式。有限长双正交小波变换,可以通过有限步的提升和对偶提升操作完成。为得到提升小波变换的形式,令小波滤波器的多相矩阵为:

其中,he( z)、ho( z)、ge(z)、go(z)分别为合成低通滤波器h及高通滤波器g的奇偶分量。对于双正交小波,其分解滤波器与合成滤波器是相同的,因此,对偶多相矩阵p( z)与p( z)相等。对于给定互补滤波器对(h, g),总是存在洛朗多项式si( z)和ti( z),(其中1≤i≤m)以及常数k有:

换句话说,所有有限长冲激响应滤波器小波变换都可以从一个懒小波变换开始,经过m步提升和双提升操作,最后进行尺度变换来完成。

1.2 二维图像的小波变换提升

设F是一个M×N的图像矩阵,第一步:对F的每一行按1.1节所述方法进行一维提升小波变换,低频分量存储在矩阵F每一行的前[N/2]项,高频分量存储在后[N/2]项;再对F的每一列进行一维提升小波变换,方法同行变换。

2 基于双树复小波变换的理论知识[7]

双树复小波变换采用两个实小波可称为树A和树B。其中,变换的实部由上部树A给出,变换的虚部由下部树B给出。两个实小波变换采用不同的两个滤波器集合,每一个集合都满足完美重建条件。将这两组滤波器设计在一起,变换是近似可分析的。

那么可得到以下6个小波:

因为双树复小波变换的二维形式是通过对二维信号(图像)分别对行和列进行一维分解。同时分解行和列,抑制负频率，二维信号频谱的第一象限被保留，方向选择性由高维的复数小波变换提供。6个不同的方向由以上6个实数方向小波成功分离，它们都来自于一对经典的小波，都近似满足ψg（t）=h｛ψh（t）｝［8］。双树复小波的冗余性与分解的尺度数无关。它提供了良好的方向选择性，如：6个方向的纹理特征。而经典的2-D DWT仅能提供3个方向。

3 基于提升小波和双树复小波的图像检索算法

3.1 纹理特征

对图像分别进行K层db2小波提升变换和双树复小波变换，图像纹理主要集中在高频部分，因此，选用高频子图像的均值和标准差来表示其纹理信息。提升小波变换后，得到9K个高频子图像记做ft，t=1，2，⋅⋅⋅，9K。第t个高频子图像的均值Mt和标准差St分别为：

i=1，2，⋅⋅⋅，8k ｛M1，S1，M2，S2，⋅⋅⋅，Mi，Si｝i=1，2，…R， j=1，2，…C其，中，R和C是每一个高频子图像的行数和列数，代表子图像的大小。于是，整幅图像F的纹理特征可表示为1*16k维的向量，记为：，其中：

3.2 相似度的度量

通过上述特征提取公式可以建立纹理特征数据库。检索性能不仅与提取的特征有关，而且还与相似性的计算方法有关。好的相似性计算方法提高检索效率的同时，还能缩短检索的时间。由于提取的纹理特征用均值和标准差表示，它们具有不同的物理意义，并且量纲不同，如果使用欧式距离进行相似性计算，对不相同物理意义的特征需要归一化处理，从而使计算复杂化，为了使计算量减少，采用Canberra距离，此距离能够解决量纲产生的问题，定义公式，如下：

其中：d（x，y）表示两个特征向量x，y之间的距离，D表示特征向量的维数，xi，yi则表示特征向量x，y的第i个分量。

3.3 图像检索算法

取8K幅高频子图像的均值和标准差作为它们的纹理特征，得到维的特征向量；记为：

｛M1，S1，M2，S2，⋅⋅⋅，Mi，Si｝ i=1，2，⋅⋅⋅，8k 从图库中读入每幅图像，并对图库中的每个图像都重复进行与查询图像同样的步骤（1）-（4）操作。

求取每幅图像的纹理特征数据与查询图像的纹理特征数据的Canberra距离。距离越小，相似程度越高。

4 实验结果和分析

本文实现了一个实验系统。测试使用文献［6］中SIMPLIcity系统测试集，它是从Corel图像库选取的600幅图像，包括10类，每类60张，如恐龙，汽车、花、、海滩、建筑、非洲土著居民等。在下面的实验中，共选取6类图像（恐龙，马、海滩、公共汽车、花、建筑），对每一类图像随机抽取1幅作为查询图像，用基于提升小波变换的纹理特征的图像检索算法和基于双树复小波变换的纹理特征图像检索算法与本文的算法做比较，并选取系统返回的前20幅的图像作为检索结果。限于篇幅，只取一类结果，如图3-图5所示：

图3 基于提升小波变换的图像检索算法

图4 基于双树复小波变换的图像检索算法

图5 本文检索算法

图3到图5中，系统返回20幅图像，其中第一幅图为查询图像。在图3到图5中，可以看到对于纹理清晰的公共汽车类图像，用提升小波变换的纹理特征的检索算法检索出了5幅，基于双树复小波变换的纹理特征检索算法检索出了6幅，本文的算法检索出了16幅。

文中用查全率（recall）［9］及查准率（precision）［10］来评价检索算法的好坏。查全率：返回的图像中，与查询图像相关的数目占图库中相关图像的总数的比例。设w是原始图像，其查全率及查准率可以设为：

其中，N是图库中与原始图像w相类似的图像总数；n是系统检索到的与原始图像相似的图像数目；F是系统自动搜索得到图像的总数目。当查全率及查准率越大时，说明该算法的检索率越高。

下面是三种算法检索出来的结果的比较。

实验：对公共汽车、建筑物、海滩风景图像检索

表1 三种方法的检索性能数据比较

从表1中容易得出，基于提升小波的图像检索算法，虽然对各类图像查询所需的时间比基于双树复小波变换的纹理特征图像检索算法的短，但它的查全率P（%）和查准率R（%），显然低于基于双树复小波变换的纹理特征图像检索算法，而本文检索算法的查全率及查准率不但高于文中的其他两种检索算法，并且检索时间也比其他两种算法的查询时间短。综上所述，本文的检索算法优于文中其他的两种图像检索算法。

5 结束语

本文提出：基于提升小波和双树复小波变换的图像检索算法。第一步：对图像分别进行K层db2小波提升变换和K层双树复小波变换；得到各层的3个方向上的和6个方向上的高频子图像，第二步：将各层上的8K个方向上的高频子图像组合在一起，得到8K幅高频子图像。第三步：取8K幅高频子图像的均值和标准差作为它们的纹理特征，计算图像间的纹理特征数据的Canberra距离，完成检索过程。虽然本文的检索算法，具有纹理特征描述能力，但是缺乏对图像语义的描述，如对食物的检索效果有待提高，对此将在以后进行研究讨论。

［1］赵珊.基于内容的图像检索关键技术研究［博士学位论文］.西安：西安电子科技大学，2007.

［2］SWELDENS W. The lifting scheme： A custom design construction of biorthogona lwavelets， ApplHarmon.Anal，1996，3（2）：186-200.

［3］Nick Kingsbury. The Dual-tree Complex Wavelet Tra nsform： a New Technique for Shift Invariance and Directional Filters［C］//Proc 8 IEEE DSPW orkshop，［S I ：Bryce Canyon ，1998.］

［4］Kingsbury N.Complex wavelets for shift invariant analysis and filtering of signals［J］.Applied and Computational Har-monic Analysis，2001，10（3）：234-253.

［5］赵志杰，林茂六，曹志民，刘增玉.基于db2提升小波的可伸缩视频编码方法.通信学报， 2009，1，30（1）：88-94.

［6］DAUBECHIES I .et al.Factoring wavelet transforms into lifting steps.J Fourier Anal Appl，1998， 4（3）：247-269.

［7］基于多尺度及多方向分析的纹理图像检索算［J］.郑州大学学报，2009，41（1）：27-32.

［8］Haralick R M，Shanmugam K，Dinstein I.Textures features for image classification［J］.IEEE Transactions on Systems，Man and Cybernetics，1973，3（6）：610-621.

［9］刘忠伟，章毓晋.综合利用颜色和纹理特征的图像检索.通信学报，1999，20（5）：36-40.

［10］王华，戴芳.一种基于基元的彩色图像检索方法.计算机系统应用，2011，20（1）：95-99.

TP391

A

1003-5168(2015)11-267-03