基于小波变换的图像检索_徐淑平

文章编号:1006-2475(2005)11-0012-04

计算机与现代化

JISUANJI YU XIANDAIHUA

总第123期

基于小波变换的图像检索

徐淑平,洪 亲

1

2

(1.清华大学计算机科学与技术系,北京 100084;2.福建师范大学物理与光电信息科技学院,福建福州 350007)摘要:随着多媒体和因特网技术的迅速发展,图像数据在不断增加,为了对这些图像进行更有效的管理和分析,帮助用户快速准确地找到所需内容的图像,基于内容的图像检索(CBIR)正成为当今多媒体技术研究的热点。本文采用基于小波变换的技术来提取图像的纹理特征,并使用支持向量机学习技术从图像数据库中检索出符合要求的图像,实验结果证明了所提出方法的有效性。

关键词:基于内容的图像检索;小波变换;特征提取;SVM中图分类号:TP391.41 文献标识码:A

ImageRetrievalBasedonWaveletTransform

XUShu-ping1,HONGQing2

(1.DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing 100084,China;2.SchoolofPhysicsandOptoElectronicsTechnology,FujianNormalUniversity,Fuzhou 350007,China)

Abstract:WiththeadvancesofthemultimediaandInternettechnologies,therehasbeenanexplosionintheamountofdigitalimages,inordertomanageandanalyzetheseimageseffectivelyandhelpuserretrievetheirwantedimagesefficiently,theconten-tbasedimagere-trieval(CBIR)isbecomingmoreandmoreactiveinmultimediaresearchfield.Thispaperextractsimage.sfeaturesbasedonwavelettransformandusessupportvectormachine(SVM)toretrieveimagesfromimagedatabases.Theexperimentresultsillustratethisap-proachisveryeffective.

Keywords:CBIR;wavelettransform;featureextraction;SVM

0 引 言

在70年代,图像检索技术是基于文件系统的图像管理,到了80年代流行基于文本的图像检索方式是首先使用文本标注图像的内容,然后通过关系数据

库系统进行图像检索,其优点是可以利用关系数据管理系统的成熟技术于图像管理当中。而进入90年代,随着图像数据的来源不断增加,数据量不断增大,人工标注的问题使得图像检索很难有所突破,制约了图像检索技术的发展。为了解决这个问题,人们提出了基于内容的图像检索技术CBIR,其主要特点是基于图像特征从大型数据库中检索出用户所需要图像的过程。这些图像特征可以是低层的视觉特征(如:

颜色、纹理、形状、空间结构等),或是更高层的图像语义特征,而这些特征提取的主要过程必须是计算机自动完成的。

本文在第1部分对基于图像的底层特征进行了概括,其中包括图像的颜色、纹理、结构和空间特征,在第2部分介绍了基于小波变换的图像纹理特征的提取的详细过程,在第3部分对实验过程及结果进行概述。

1 图像的底层特征

图像底层特征[1]是指图像的原始特性或属性。其中有些是视觉直接感受到的自然特征,如区域的亮度、边缘的轮廓、纹理或颜色等;有些是需要通过变

收稿日期:2005-01-21

基金项目:国家自然科学基金资助项目(60321002),国家重点基础研究(973)项目(2004CB318108)作者简介:徐淑平(1972-),男,江西南昌人,清华大学计算机科学与技术系硕士研究生,研究方向:多媒体技术,人工智能;洪亲(1964-),女,福建南安人,福建师范大学高级工程师,研究方向:数据库,多媒体技术。

2005年第11期徐淑平等:基于小波变换的图像检索

13

换、测量或计算才能得到的人为特征,如图像的直方图、矩等。1.1 颜色特征

颜色是图像的一个重要属性,它对图像的大小、方向和旋转都不敏感,具有一定的稳定性。颜色特征值一般用颜色直方图来描述,直方图的横轴表示颜色的等级划分,而纵轴表示在某一个颜色等级上具有该颜色的像素在整幅图像中所占的比例数,其值越大表示该颜色在图像中占据的面积越大。

另外,由于彩色空间的选取对图像检索的性能也有比较大的影响。而常用的颜色空间主要有以下几种:RGB(红绿蓝),HSV(色调、饱和度和亮度),PAL彩色电视用的YUV和NTSC彩色电视用的YIQ颜色空间。其中RGB虽然是一种被广泛采用的颜色模型,但在RGB空间中的向量同时反映了颜色和亮度,而亮度变化对图像检测的效果会造成很大影响。大量的试验表明,采用HSV颜色空间更适合于基于内容的图像检索。1.2 图像形状

形状特征是刻画图像中目标的主要特征之一,传统的方法是用Freeman链码、曲线、Fourier描述子、二次曲线及B样条曲线等来描述平面曲线。基于形状的检索主要是要寻找那些对平移、缩放、旋转都不变的几何特征。其主要问题是图像中的对象一般很难从背景中准确分割出来,从而无法得到其精确的形状信息;另外,物体的形状受视角及物体姿势的影响,使得其检索越加困难。1.3 纹理特征

纹理同颜色一样,是图像中的一个重要特征,虽然图像在局部区内可能呈现出不规则性,但从整体上看还是表现出某种规律性。根据图像的纹理对图像进行检索的方法主要有两种方法,分别是统计的方法和结构的方法[2]。而本文提出了基于小波变换的图像纹理特征,即先对图像进行小波变换,然后计算其系数的均值和方差作为对应图像的特征值,其具体方法及步骤在第2部分有详细的介绍。1.4 空间特征

空间关系表达了图像内部各部分之间的联系。空间关系主要包括朝向和拓扑两种结构关系,具体表达这些关系时,可采用四叉树网格、2-D串等方式来进行。它的优点是图像空间特征比颜色、纹理、形状等能更完整地表达图像各部分的信息,并能比较方便地进行无示例或用自然语言进行图像的查询,因此也广泛地应用于基于内容的图像检索系统中。2 基于小波变换的纹理特征提取

20世纪70年代,当时在法国石油公司工作的年轻的地球物理学家JeanMorlet提出了小波变换WT(wavelettransform)的概念。

小波变换的主要算法则是由法国的科学家StephaneMallat在1988年提出。他在构造正交小波基时提出了多分辨率的概念,从空间上形象地说明了小波的多分辨率的特性,提出了正交小波的构造方法和快速算法,叫做Mallat算法。该算法统一了在此之前构造正交小波基的方法,它的地位相当于快速傅立叶变换在经典傅立叶分析中的地位。

2.1 小波的定义[3]

小波是定义在有限间隔而且其平均值为零的一种函数,它的某些波形如图1所示。在数学上,小波定义为对给定函数局部化的函数,小波可由一个定义在有限区间的函数7(x)来构造,7(x)称为母小波(motherwavelet)或者叫做基本小波。一组小波基函数{7a,b(x)},可通过缩放和平移基本小波7(x)来生

x-b成,7a,b(x)=|a|-1/27()

a

其中,a为进行缩放的缩放参数,反映特定基函数的宽度(或者叫做尺度);b为进行平移的平移参数,指定沿x轴平移的位置。函数f(x)以小波7(x)为基的连续小波变换定义为函数f(x)和7a,b(x)的内积。

Wf(a,b)=a,b>=Qf(x)

-]+]

1x-b7()dx

aa2.2 小波变换与分析

图像分析一般是为了获得时间和频率域之间的相互关系。傅立叶变换提供了有关频率域的信息,但

14

计 算 机 与 现 代 化2005年第11期

2时间方面的局部化信息却基本丢失。与傅立叶变换不同,小波变换通过平移母小波(motherwavelet)可获得信号的时间信息,而通过缩放小波的宽度(或者叫做尺度)可获得信号的频率特性。对母小波的缩放和平移操作是为了计算小波的系数,这些系数代表小波和局部信号之间的相互关系。

如果对图像的高频分量不再分解,而对低频分量连续进行分解,就得到许多分辨率较低的低频分量,形成的树形结构就叫做小波分解树。而对低频分解级数的多少则取决于要被分析的数据和用户的需要。图2给出了三级小波分解的示意图。

LL3HL3LH3HH3LH2

HL2

HL1(水平分量)

HH2

n,对应的方差:R(x)=E(xi-Lj(x))/n(其中n为图像特征的维数),图3为基于小波变换的图像纹理特征提取流程图,第二步中的小波变换一般可采用三层小波变换即可。对图像库中的所有图像进行特征提取后可放在一个图像特征文件中,以使数据具有可重用性,为以后程序的再次开发创造条件。

3 实验进行及结果

在图像检索的匹配部分,我们选择支持向量机SVM作为学习机器[4],这是因为SVM不仅有统计学习理论作为其推广性的保证,而且在很多实际问题中获得了优于其他方法的结果。SVM是基于统计学习理论中的结构风险最小化原则发展而来的,所谓结构风险最小化,就是在确定的置信范围内,寻找最小经验风险。随着函数子集复杂度的增加,置信范围会增大,而经验风险会减小。选择最小经验风险与置信范

LH1(垂直分量)

HH1(对角分量)

图2 三级小波分解示意图

小波分解树表示只对信号的低频分量进行连续分解。如果不仅对信号的低频分量连续进行分解,而且对高频分量也进行连续分解,这样不仅可得到许多分辨率较低的低频分量,而且也可得到许多分辨率较低的高频分量。这样分解得到的树叫做小波包分解树。

图4 篮球比赛图像检索结果

围之和最小的函数子集,就可以达到期望风险的最小,这个函数子集中使经验风险最小的函数就是要求的最优函数。如果样本点是线性可分的,则直接对样

2.3 基于小波变换的图像特征提取

图像小波变换后的低频成分对应于图像的轮廓,高频成分对应于图像的细节部分,所以一般采用小波分解树方式对图像进行小波分解,然后提取其系数对应的均值和方差即可。在数学上,一幅图像数据是一个二维的数据阵列,进行小波变换时可以先对阵列的每一行进行变换,然后在行变换之后对阵列的每一列进行变换,最后对经过变换之后的图像数据阵列进行小波系数的均值及方差的计算。对于阵列中的某一行(或列),小波变换后的系数平均值为Lj(x)=i=r0xi/

n

本空间进行操作即可。若样本点不是线性可分,则首

先通过一个非线性映射<(x)将其投影到一个高维空间(称之为特征空间)使之线性可分,然后在特征空间中对<(x)进行操作。

总之,SVM是利用非线性映射将输入向量映射到一个高维的特征空间中,然后在该空间中构造一个最优超平面来逼近目标函数。最优超平面方法控制学习机实现的函数集的容量,使支持向量机具有更好的推广能力;采用该函数方法则避免了显式的非线性映射,从而克服了高维特征空间带来的计算困难。在图像检索、汉字识别、语音处理、人脸识别等诸多领域应用非常普遍。

2005年第11期徐淑平等:基于小波变换的图像检索

15

本实验在以NIST(美国国家标准与科技协会)提供的TRECVID中的视像关键帧图像为数据源,其中有新闻图片、运动场面、人物专、暴力事件、动植物等共十多万幅图像。对于要检索的图像,先人工标注部分正例和反例,然后采用SVM进行训练,并用最终训练好的算法进行图像检索,最终显示出我们所需要的图像。图4是显示篮球比赛镜头的前九幅图像。

[5]

决。如何更有效地进行图像检索,有许多人提出了基于图像语义的处理方法,还有的提出了在检索中加了人工反馈等多种多样的技术,随着技术的进一步深入,图像检索技术必定会有新的突破。

参考文献:

[1] XiangSeanZhou,ThomasSHuang.CBIR:Fromlow-level

featurestohigh-levelsemantics[A].Proc.SPIEImageandVideoCommunicationandProcessing[C].2000.

[2] 徐杰,施鹏飞.基于内容的图像检索技术[J].中国图象

图形学报,2003,8(9):977~983.

[3] VapnikV.统计学习理论的本质[M].张学工译.北京:

清华大学出版社,2000.

[4] 林福宗.多媒体技术基础(第2版)[M].北京:清华大学

出版社,2002.

4 结束语

由于目前的计算机技术还很难准确提取和描述任意图像的内容特征,而且基于特征的相似度计算与人眼的视觉感知存在一定差异,以及基于少量的反馈

样本很难有效地机器学习等原因,CBIR距离实用阶段还有一段距离,存在许多具有挑战性的问题需要解(上接第11页)这两种测试模型的缺陷越来越明显,很难满足我们的需要。近几年发展起来的面向对象测试模型和前置测试模型汲取了V模型和X模型的精华,弥补了它们的不足,将测试和开发过程密切结合,是行之有效的测试模型。使用这两种模型,可以使软件项目加快速度。有关面向对象测试模型和前置测试模型的知识,不是本文讨论的范围,读者可以参考有关书籍和资料。

测试。测试计划的评审应该有多方人员参与,包括开发人员。

由于测试发现问题,在解决问题后还要重新测试,因此测试的时间可能会比实际更长一些。要正确识别和注意少数重要的方面,而忽略多数次要的方面。

正确的错误定位。错误的定位有时是很难的,要找出必然发生的前因后果,而不至于因为描述错误而误导开发人员。对于错误不能重建的问题,解决办法是在错误报告中给予说明。对错误的描述,应该是准确、完整而简练。因为描述的问题或者不完整的描述会引起开发人员的误解,其后果是可想而知的。最后,测试工作应该覆盖到硬件,甚至非计算机产品的测试。

3 测试方案、计划和方法

测试就像做实验,之前必须有实验的方案、内容和步骤,测试也是同样的。另外,基于测试用例的测试和常见的随机性地测来测去也是完全不同的,尽管习惯于随机性测试的人,如果注意力集中的话,他的头脑里也是有测试用例的。

测试工作需要良好的工作环境。进行测试工作要争取到尽可能好的工作环境,如果可能,应该建立测试实验室,实验室包括必要的装备、工具软件(包括测试工具)和各种操作系统平台,保持实验室的实用、整洁,避免他人干扰甚至破坏测试环境。

制作简单的测试跟踪软件。制作一个简单的测试问题跟踪软件,记录测试的结果,将测试发现的问题分类,并对测试发现的问题和模块、开发人员进行关联,有助于分析问题,并可有效记录测试的结果,形成测试报告,从中找出一些规律性的东西来。测试问题跟踪软件是有价值的。

制定测试计划。在制定测试计划的时候,要充分考虑到测试风险,并抉择要执行哪些测试,放弃哪些

4 结束语

随着计算机技术、数据融合技术、网络技术和通信技术的飞速发展,对软件功能提出的要求也越来越高,如何开发出高质量的软件已成为一个迫切需要解决的课题。加强软件测试管理是保证软件高质量的关键。我们相信,通过建立科学合理的软件测试管理体系,充分考虑到软件的特殊性,借鉴其他学科的相关理论,是可以全面控制软件质量的。

参考文献:

[1] 郑人杰,殷人昆,陶永雷.实用软件工程[M].北京:清华

大学出版社,1997.

[2] 郑人杰.计算机软件测试技术[M].北京:清华大学出版

社,1993.