（计算数学专业论文）降维方法在图像检索中的应用.pdf

中文摘要 随着信息技术的不断发展，图像数据呈现出几何级数的增长趋势。那么如 何从海量的多媒体数据库中按照内容检索到用户真正需要的数据就成为一个热 点问题。目前，基于内容的图像检索( c b i r ) 技术研究正是这一研究领域的 一个研究方向。 本文以基于内容的图像检索技术为基础，重点讨论了图像低层特征的提 取，将p 层四叉树的图像分块策略和非线性降维方法一l l e 方法应用于图像 特征的提取之中，提出了一种新的基于区域的图像特征提取方法。本方法在提 取图像颜色特征的同时还充分考虑了图像的空间信息，并且通过l l e 方法降 维后，新方法所提取的特征向量具有更好的检索性能。具体工作如下： 1 、对图像库中的每幅图像按照p 层四叉树的分块策略进行划分，然后对 每个分块计算其自身的低阶颜色矩和阈值作为分块的图像特征，综合每个分块 的特征从而得到图像的总体特征描述。 2 、针对上述所提取的图像特征维数高的缺点给出了相应的改进方法，新 的方法将l l e 降维方法应用于图像特征的降维之中，有效的降低了数据的存 储空间及运算复杂度。 3 、对新设计的方法做了数值实验。结果表明，本文提出的算法具有较好 的检索性能，与理论研究目标基本保持一致。 关键词 基于内容的图像检索，特征向量，降维 a b s t r a c t ( 英文摘要) w i t ht h ec o n s t a n t l yd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h en u m b e ro f t h ei m a g ed a t ah a sb e e ns h o w i n gag e o m e t r i cp r o g r e s s i o no fg r o w t ht r e n d h o w c a nt h eu s e r ss e a r c hf o rt h em u l t i m e d i ad a t aw h i c ht h e yr e a l l yn e e df r o mt h e v a s tm u l t i m e d i ad a t a b a s eh a sb e c o m eah o tt o p i c c o n t e n t b a s e di m a g er e t r i e v a l ( c b i r ) t e c h n o l o g yi sas t u d yi nt h i sr e s e a r c h f i e l d t h ep a p e rb a s e do nc b i rm a i n l yf o c u s e so nl o w - l e v e li m a g ee x t r a c t i o n ， i nw h i c hpl a y e rq u a d t r e ed e c o m p o s i t i o ns t r a t e g yi su s e d i tp r o p o s e san e w r e g i o n - b a s e df e a t u r ee x t r a c t i o nm e t h o d t h em e t h o dn o to n l ye x t r a c t st h ei m a g e c o l o rf e a t u r eb u ta l s of u l l yt a k e st h es p a t i a li n f o r m a t i o ni n t oa c c o u n t a f t e rt h e d i m e n s i o n a l i t yi sr e d u c e db yl l e ，t h en e wf e a t u r ee x t r a c t i o nm e t h o dh a sa b e t t e rr e t r i e v a lp e r f o r m a n c e t h ew o r km a l i n l ye n g a g e di ni sa sf o l l o w s ： f i r s t ，e v e r yi m a g ei nt h ed a t a b a s ei sd i v i d e da c c o r d i n gt opl a y e rq u a d t r e e d e c o m p o s i t i o ns t r a t e g y , t h e nf o re a c hb l o c k ，w ec a l c u l a t et h el o w - l e v e lc o l o r m o m e n ta n dt h r e s h o l dv a l u ea si t si m a g ef e a t u r e ac o m p r e h e n s i v ef e a t u r eo f e a c hb l o c kt od e s c r i b et h eg e n e r a lc h a r a c t e r i s t i c so ft h ei m a g ei so b t a i n e d s e c o n d ，r e s p o n d i n gt ot h em e t h o do fe x t r a c t e di m a g ef e a t u r e sw h i c hh a s t h ed e f e c t so fh i g hd i m e n s i o n s o m ei m p r o v e m e n t sa r em a d e l l e ak i n do f n o n - l i n e a rd i m e n s i o n a l i t yr e d u c t i o nm e t h o di sa p p l i e d ，t h e ni tw i l lr e d u c eb o t h s p a t i a la n do p e r a t i o nc o m p l e x i t y a tl a s t ，n u m e r a le x p e r i m e n t sa r em a d e r e s u l t ss h o wt h a tt h eq u a l i t yo f i m a g er e t r i e v a li si ng o o da c c o r d a n c ew i t ht h et h e o r yt a r g e t k e yw o r d s c o n t e n t - b a s e di m a g er e t r i e v a l ，f e a t u r ev e c t o r ，d i m e n s i o n a l i t yr e d u c t i o n l l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：丛垡指导教师签名： 小ld 年1 7 月f 。日 年月 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：力寸段 函卜年易月oe t 西北大学硕士学位论文 1 1 研究背景 第一章绪论帚一早 三百比 随着信息社会的发展，大容量存储设备及数字化设备的出现和广泛使用， 多媒体技术和网络技术的迅速普及，图像和视频数据呈现出了一种“爆炸”式 的现象，其数量呈几何级数的增长趋势，大容量的多媒体数据库也随之而出 现。那么如何从浩瀚的图像数据库中根据内容检索到自己所需要的图像成了近 十多年来多媒体领域研究的热点之一m 。 从图像检索技术的发展历程来看，图像检索技术的历史可以追溯到2 0 世 纪7 0 年代，其推动力来源于针对数据库系统和计算机视觉的研究，它们分别 从基于文本和基于内容两个不同的角度展开研究。基于文本的图像检索是将图 像作为数据库的一个存储对象，用文本语言对图像的信息进行手工描述，对图 像进行查询时是根据各种关键字进行精确匹配或模糊匹配，因此这种图像检索 技术的实质是采用成熟的文本检索技术来实现对图像的检索。然而基于文本的 图像检索技术存在很多无法解决的问题例。 第一，它需要人工提前的对图像库中的图像进行归纳和注释，费时又费 力，尤其是当资源的数量多到一定程度时，完全采用人工的方法会遇到难以克 服的困难。 第二，图像检索的结果也完全依赖于人工标注的图像名称、编号、注释等 信息，但是这些信息具有很强的主观性。对于同一幅图像，“公说公有理，婆 说婆有理”，不同的人极有可能存在着不同的看法，那么其标注的信息也可能 会不尽一致。 第三，一幅图像所包含的意义非常丰富，“百闻不如一见”就很好的说明 了这个事实，而人工标注的少量文字很难充分表达一幅图像的内涵，图像的许 多内容都是文字很难以描述的。 1 第一章绪论 第四，由于媒体信息往往是发布在网络环境中，不同国家、不同民族使用 的语言也不同，所以对同一幅图像采用不同的语言种类进行标注，而且不同民 族有着各自独特的文化，对图像语义理解的差异也很大，因此不可能形成一种 统一的检索方法。 针对上述种种无法克服的弊端，一种新的图像检索技术一基于内容的图 像检索技术被提出并迅速发展起来。 基于内容的图像检索指的是查询条件本身就是一幅图像( 或者是对于图像 的内容描述) ，它建立索引的方式是首先提取图像的特征，然后通过计算比较 这些特征和查询条件之间的距离，来决定两幅图的相似程度。为了提高索引性 能，还需要有效地索引技术以满足检索的实时性要求。这种以图找图的查询模 式是对以关键字找图的一大突破。 基于内容的图像检索技术的研究涉及到人工智能、计算机视觉、信号处 理、认知心理学、数据库、人机交互等诸多领域，具有重大的理论意义。同 时，它也是理论和实践相结合的一项研究，其最终目标就是帮助人们更方便， 快捷，准确地找到他们所需要的多媒体资源，因此，该技术具有巨大的应用前 景【2 7 】。 c b i r 的一般框架如图1 1 所示： 图1 1 ：c b i r 框架图 2 西北大学硕士学位论文 基于内容的图像检索技术具有以下几个特点矧： 第一、直接从图像的内容着手，提取图像内容本身的相关特征信息，基于 内容的图像检索突破了早期的基于文本描述的检索手段，它是对图像中颜色、 纹理、空间等性质进行分析和特征提取，最后利用这些特征信息来建立索引。 第二、基于内容的图像检索采取的是相似性匹配手段。在构建图像数据库 时，需要事先采用模式识别的方法对数据库按不同的特征进行索引分类；当图 像进行检索时，通过某种相似性度量手段进行模糊匹配，最后返回查询结果。 在这一点上它与常规的基于精确匹配的数据检索方式有着明显的不同。 第三、通过计算机可以自动实现图像特征提取和索引建立，从而避免了传 统的人工描述方式，大大减少了工作量。 1 2 国内外研究现状 基于内容的图像检索技术始于上世纪九十年代初期，由于该项技术涉及 的领域很多，以及该技术对信息检索领域的重要作用，所以迅速成为研究 的热点问题。各大研究机构、公司、高校如i b m 、m i t 、c o l u m b i a 等都对 该技术进行了深入的研究，并推出了各自的图像检索系统；各大著名杂志 如c o m p u t e rv i s i o na n di m a g eu n d e r s t a n d i n g 、p a t t e r nr e c o g n i t i o n 、p a t t e r n r e c o g n i t i o nl e t t e r s 等也纷纷设立了专刊介绍该领域研究的成果。 在国内，各大重点院校和科研机构都展开了关于基于内容的图像、 视频、音频的检索方法的研究。清华大学结合国家8 6 3 高技术研究发展 项目，开展了“w _ e b 上基于内容的图像检索的研究”，研究目标是开发 能在i n t e r n e t i n t r a n e t 环境下，通过友好的人机界面，利用主颜色、纹 理、颜色分布以及轮廓等图像特征或样本图像检索的方法和工具。中国 科学院计算技术研究所和北京图书馆联合开发了“基于特征的多媒体 信息检索系统m i r e s ”，浙江大学开发了p h o t on a v i g a t o r 、p h o t oe n g i n e 和w e b s c o p e c b r 等系统。总之，目前越来越多的科研机构都加入了研究基于 3 第一章绪论 内容的图像检索技术的行列中来。 目前，c b i r 是一个非常繁荣的研究与应用领域，几乎每天都会有新技术 报道。随着该领域的逐步发展，研究者与开发者所面临的问题也相应的发生了 变化。大部分的前期研究主要关心如何从一个大图像集中利用自动导出的图 像特征检索出图像；目前的研究工作则集中在如何改进c b i r 技术上，以研 制出满足用户实际需求的c b i r 系统，研究的主要问题包括新类型的图像特 征、表示方法以及相似度度量等。显然，c b i r 系统不可能只用传统的文字 查询方式达到目的，但这并不意味着不能将文字查询包含在c b i r 的系统中 去。事实上，已经有一些研究工作将基于文本的检索与c b i r 集成在一起， 即将图像的文字描述与图像的底层特征集成在一个c b i r 系统中。研究人员 已经发现全自动的提取特征似乎是不可能的，而使用者有时也无法明确地描述 其中的一些图像特征。越来越多的研究工作己转向“半自动”的特征提取以及 交互式查询方式，现有的交互式c b i r 系统广泛采用了相关反馈技术以及机 器学习技术。另一方面，一些研究者逐渐意识到”图像相似”是一个与人的视 觉感知有关的概念，然而现有的c b i r 技术无法完整地建立图像的低层特征 与语义信息之间的联系。因此，就提出了“语义图像检索”技术，目前针对该 技术的研究也取得了巨大的成果。通过考察c b i r 技术的发展过程并不难发 现，c b i r 技术的发展已经经历了几个发展阶段，每个阶段均体现了人们对 “图像相似”概念理解的变化，并且均得到了相应技术的支持。 1 3 研究意义 在基于内容的图像检索过程中，为了达到较好的图像查询效果，用于表示 图像的特征向量往往具有高维特性，随着图像特征数据维数的不断提升，数据 将提供关于客观图像更加丰富，更加细致的信息。目前许多现有的c b i r 试 验原型系统仅仅处理几百幅或几千幅图像，因此即使对所有的图像按序排列并 计算相似度也不会带来性能上的显著下降。但是，随着用户需求的提升，图像 4 西北大学硕士学位论文 集的规模会变得越来越大，这时，大量的高维数据会给随后的数据处理工作带 来巨大的困难，这就是所谓的“维数灾难”( c u r s eo fd i m e n s i o n a l i t y ) i x 2 。 对高维数据进行处理本身就比较困难，而且用高维特征向量进行检索时，检索 速度就会成为检索系统中的性能瓶颈。另一方面，随着特征向量维数的增加， 高维空间中的欧氏距离还受到c o n c e n t r a t i o n 现象的影响，就是在空间中，任 意两个向量之间具有高度的相似性。任意两个数据点和之间的欧氏距离，可以 证明：【6 】 恕坐幽m i 糍n i 拶= 。 d o o ( d 【z ，饥) j 这个对特征向量之间的相似性度量会产生很大的影响，从而会进一步影响检索 结果。基于对以上由于高维特征向量所引起的各种问题以及降维技术在模式识 别中的广泛应用，我们一个自然而然的想法就是将降维技术运用到基于内容的 图像检索中来，在对检索结果不会产生很大影响的前提下对图像的高维特征向 量进行降维。这样，不但可以降低数据的存储开销，而且可以提高检索的效 率。 降维技术在图像检索中运用的基本思想是：首先利用各种降维方法将图像 的数据集中的大部分“信息”压缩到低维的特征向量中，然后使用这些低维的 特征向量来索引图像，并据此实现基于内容的图像检索。 1 4 本文主要工作和组织安排 本文立足于基于内容的图像检索技术，首先对图像库中的每幅图像按照p 层四叉树的分块策略进行划分，然后对每个分块计算其自身的低阶颜色矩和阈 值作为分块的图像特征，综合每个分块的特征从而得到图像的总体特征描述。 然后，针对上述所提取的图像特征维数高的缺点给出了相应的改进方法，新的 方法将l l e 降维方法应用于图像特征的降维之中，有效的降低了数据的存储 空间及运算复杂度。最后，对新设计的方法做了数值实验。结果表明，本文提 出的算法具有较好的检索性能，与人们的期望基本保持一致。 5 第一章绪论 本文的组织结构安排如下： 第一章绪论 主要介绍本文的研究背景、研究意义，本文的主要工作和章节安排。 第二章特征提取 将p 层四叉树的分块策略应用于图像空间的划分之中，结合图像的底层 特征提取颜色矩和图像的阈值，提出了一种新的基于区域的图像特征的提取方 法。 第三章数据降维 在第二章提出的图像特征的提取方法的基础上，将l l e 的非线性降维方 法运用到图像特征向量的降维之中，针对性的解决了本文所提出的图像特征提 取方法的缺点。 第四章特征匹配 承接第三章，介绍了各种相似性度量的方法，对降维后的图像特征向量选 取适当的度量方法进行相似性度量。 第五章性能评价 对于图像检索系统性能的优劣进行评价，详细介绍了精确度和检索率两个 评价指标。最后给出了试验结果，通过对实验结果的分析证明了本文所提取算 法的优越性。 6 西北大学硕士学位论文 第二章特征提取 弟一早i 寸哥位淀耿 图像特征的提取与表达是基于内容的图像检索技术的基础。从广义上讲， 图像的特征包括基于文本的特征( 如关键字、注释等) 和基于视觉的特征( 如 色彩、纹理、形状、对象表面等) 两大类，而视觉特征又可以分为通用的视觉 特征和领域相关的视觉特征。前者用于描述所有图像共有的特征，与图像的具 体类型或者是内容无关，主要包括色彩、纹理和形状；后者则建立在对所描述 图像内容的某些先验知识或假设的基础上，与具体的应用紧密相关。 颜色特征是在图像检索中应用最为广泛的视觉特征，也是人识别图像的主 要感知特征，其主要原因在于颜色往往和图像中所包含的物体或场景十分相 关。在自然界中，同一类物体通常有相同或相近的颜色特征，而不同类的物体 则可能表现为不同的颜色特征，所以，颜色经常可以作为区分不同物体种类最 为简单有效的一种手段。与其它的视觉特征相比，颜色特征对图像本身的尺 寸、方向、视觉的依赖性较小，具有较高的鲁棒性。因此，大多数图像检索系 统都将颜色特征作为图像检索的主要检索手段 基于颜色特征的图像检索系统中涉及若干问题。首先，需要选择合适的颜 色空间来描述颜色特征；其次，必须要采用一定的量化方法将颜色特征表达为 向量的形式；再次，以一定的形式来描述颜色特征；最后，还要定义一种相似 性度量准则来衡量特征间的相似性。本章重点介绍前三项内容，并针对现有的 基于区域图像特征的提取方法做以改进，最后一项放在第四章来介绍。 2 1 颜色空间及其量化 从数字图像中提取颜色特征，依赖于对数字图像中颜色的表示和颜色理论 的理解。颜色空间对于相关颜色以数字形式表示是一个很重要的成分，在不同 颜色空间之间的转换以及颜色信息的量化是给定特征提取方法的决定因素。 7 第二章特征提取 2 1 1r g b 颜色空间 r g b 颜色空间是彩色图像最基本、最常用的颜色模型矧，在计算机中 和各种显示设备中，各种彩色图像的显示也是采用r g b 模式的。在图像处 理中的其他颜色空间模型都是以r g b 为基础转换而来的。根据r g b 三色原 理可知，自然界中任何颜色都是由r ( 红) 、g ( 绿) 、b ( 蓝) 三种颜色构成，早 期研究证明，人的眼睛对颜色的感知也是三维的，因此，r g b 被称为人类视 觉的基色。r g b 空间模型就是根据此理论发展的，如图2 1 所示。它是一个 三维坐标系，三个方向的坐标分别代表r 、g 、b 三个分量，图像中的任何一 个像素点都是该坐标系中的一个点，它的像素值由r g b 表示，其中每一颜 色分量的取值范围为【0 ，2 5 5 】。从图中可以看出，原点处代表黑色，其像素值 为( 0 ，0 ，0 ) ，离原点最远处的代表白色，值为( 1 ，l ，1 ) ，其他的顶点分别表示 红、绿、蓝、品红、蓝绿和黄。 r g b 颜色空间具有表达简单、使用方便等优点，有着十分广泛的应用， 但是r g b 颜色空间也有它的缺点，其缺点是： 1 、不直观，从r g b 值中很难看出该值所表示的颜色的认知属性。因 此，r g b 颜色空间不符合人对颜色的感知心理。 2 、r g b 颜色空间是一种不均匀的颜色空间，两种颜色之间的知觉差异不 能采用该颜色空间中的两个颜色点之间的距离来表示。 基于r g b 颜色空间上述两个缺点，我们并不选取它来描述颜色特征，而 是采用h s v 颜色空间。 2 1 2h s v 颜色空间 h s v 模型 9 1 是面向用户的，它是从人类的视觉感知角度出发的，因而更 容易被人们接受。用户使用的调色板和色彩模版中的色彩描述都是基于h s v 颜色模型的，2 1 1 介绍的r g b 颜色空间通常都是从图像采集设备、显示器 等硬件角度出发的，与h s v 模型相比它并不能更好的满足人们的视觉习惯。 8 西北大学硕士学位论文 从心理学和视觉的角度出发，人类对色彩中的色调、饱和度、亮度最为敏感， 它正好与h s v 模型中h 、s 、v 相对应。 其中s 代表色调，它是通过物体反射光线中哪种波长为主来决定的，不 同长度的波长会给人产生不同的颜色感知效果，如红、橙、黄、绿、青、篮、 紫等。色调是色彩图像中最基本的属性，决定了颜色的本质。例如在分辨不同 颜色物体间的区别时，最直观有效的方法就是通过物体的色调特征。 饱和度s 说明了一个物体颜色的鲜艳程度，它代表色彩的纯度，物体颜 色越深，则说明饱和度越高。它反应了色度中含色成分和消色成分的比例。当 色度中白色或灰色越多，则饱和度越低。亮度v 是指人对光的强度感受，它 描述了物体表面反光强弱的物理量，它与物体的反射系数决定，反射系数越 大，则说明物体的亮度越高。 h s v 模型如图2 2 所示，它是一个三维圆锥体形状，圆锥的项面，它的 取值范围为【o ，1 o 】它对应了r g b 模型中r 、g 、b 三个分量等于的面， 色彩h 由和v 轴的夹角决定，例如，红色对应于0 0 ，蓝色对应于2 4 0 0 。 在h s v 中颜色和它的补色相差1 8 0 0 。h 的取值范围为【0 ，1 o 】。圆锥的原 点处代表黑色，其中：v = 0 ，s 和h 无意义，圆锥顶面中心处代表白 色，s = 0 ，v = 1 ，h 无意义。从圆锥的白色点到黑色点说明了亮度渐暗的 灰色。 h s v 颜色空间具有两大特点： 1 、亮度分量与图像的彩色信息无关； 2 、色调和饱和度分量与人感受到颜色的方式是紧密相连的。 这两个特点使h s v 颜色空间非常适合于借助人的视觉系统来感知颜色特 性的图像处理法。h s v 颜色空间直接对应于人眼色彩视觉特征的3 要素，通 道之间各自独立，可以被独立感知各颜色分量的变化，其中色调尤其影响着人 的视觉判断。因此，在基于内容的图像检索中，应用这种彩色空间更适合于用 户的视觉判断。 由于数字图像的显示通常都是r g b 模型，所以在进行图像处理时，需要 9 第二章特征提取 首先将r g b 颜色空间转换到h s v 中，它们之间的转换关系如下： r 令 r2 则有 ，( 1 ，0 ，o ) 图2 1 ：r g b y r， 。1 ，o ) g v = m a x ( r ，g ，b ) v 卢7 弋。 ￥纠盛打 l 纱气l i s s = v - m l a x ( 一r , g , b ) 图2 2 ：h s v ( 2 1 ) ( 2 2 ) v - g v - m i n ( r , g , b ) ，6 ，= v - 上m i n 生( n , g , b ) ，( 2 3 ) 6 。，( 2 3 ) h = 6 0 丰h 7 ( 2 4 ) 由上述叙述可知：日【0 ，3 6 0 。】，s 【0 ，l 】，v 【0 ，1 】。 2 1 3h s v 颜色空间的量化 颜色量化是图像工程中的一项基本而重要的技术【2 8 】，它是进行图像分割 和对象提取的基础。自然界具有无限丰富的颜色，真彩色图像具有2 2 4 种颜 色，而在图像检索的情况下，对颜色的数目有一定的限制。如何选取有代表性 1 0 西北大学硕士学位论文 的若干颜色，并把各种颜色都归到这些代表色上，就是颜色量化需要解决的问 题。 根据颜色量化的方法，可将h s v 的3 个分量根据人类的颜色感知进行非 等间隔量化【3 1 】，分别量化为8 份、3 份、3 份、，总共8 * 3 * 3 = 7 2 份。 h = s = v ： 0i l h 【3 1 6 ，2 0 1 i ，h 【2 1 ，4 0 】 2 i fh 【4 1 ，7 5 】 3 i f 一九 7 6 , 1 5 5 】 ( 2 5 ) 4i f h 【1 5 6 ，1 9 0 】 5i f h 【1 9 1 ，2 7 0 】 6 i ，h 【2 7 1 ，2 9 5 】 7 i lh 【2 9 6 ，3 1 5 】 i fs 【0 ，0 2 】 i fs ( 0 2 ，o 7 】 i f8 ( 0 7 ，1 】 i fv 0 ，0 2 】 i fu ( 0 2 ，o 7 】 i fu ( 0 7 ，1 】 然后，按照以下公式将己量化好的h s v 三个分量合成一维特征： l = h q 。q + s q + v ( 2 6 ) ( 2 7 ) ( 2 8 ) 其中，q 。、q u 分别是s 和y 的量化级数，在这里，仉= q 钉= 3 ， 则l = 9 h + 3 s + t ，。 经过上述非均匀量化后，就将h s v 空间转换为一维颜色空间l ，l 的取 值范围为 0 ，1 ，7 1 】。给定一幅彩色图后，我们就可以计算出其象素的一维 1 1 ，jl-，-，、l 第二章特征提取 颜色值。 2 2 图像的特征 2 2 1 颜色特征 在图像的各类特征中，颜色特征是最显著、最可靠、最稳定的视觉特征， 是人识别图像的主要感知特征它是人们感知和区别不同图像的一个主要特征， 世界上每一类的物体都有它固定不变的颜色表述，例如蓝色的天空、红色的玫 瑰花等，都有其特有的颜色信息，属性相同的同类物体都有相似的颜色特征， 不同类别的物体的颜色往往会有较大的差别，人们在早期的视觉研究中，通常 都比较注重物体的几何特性，反而忽视了颜色特征也是表达物体的一个重要属 性，相对于几何性而言，颜色对图像中对象的平移和方向的旋转变化都不敏 感，具有较强的鲁棒性。同时，颜色又是描述一幅图像最简便而又有效的特 征。 现在已经有很多文献提出了各种基于颜色的内容索引技术俐：s w a i n 首先提出了使用颜色直方图作为图像内容的索引特征，即首先将颜色空间 按照规则划分成若干个子空间b i n ，然后统计每副图像中的像素点在b i n 区间的出现频率，而图像间的相似性度量手段则采用直方图相交法；类似 的，h a f n e r 在q b i c 中采用了直方图的二次距离作为图像的相似性测度；另 外还有s t r i c k e r 等采用了颜色值的3 个统计量，即图像的前三阶矩来表示图像 的内容。f h n t 和f i n l a y s o n 扩展了s w a n 的方法，提出了常量颜色索引的方 法。w a n 等人则提出使用八叉数算法将图像中的像素颜色进行层次聚类，然 后导出它们的平均色、主色等作为图像索引的特征信息。 本文中主要介绍基于颜色矩的颜色特征的提取方法。 2 2 2 颜色矩 颜色矩( c o l o rm o m e n t s ) 【1 0 】是由s t r i c k e r 等人提出的一种简单有效的颜 1 2 西北大学硕士学位论文 色特征提取算法，它的思想来源于图像中任何颜色的分布情况都可通过数学上 的矩来表示，此外，由于颜色信息代表图像的低层特征信息，因此，图像的一 阶矩、二阶矩、三阶矩就可以完全描述出图像中的颜色分布情况。 颜色的三个低阶矩的数学表达式为： 1o 地2 元0 黝 3 = 1 ( 2 9 ) 以= ( 1n 二2 ) 5 埘 岛= ( 去季一胁，3 ) 5 c 2 1 1 ， 式中，p i t 表示点处的颜色值，礼表示灰度级数。 2 3 图像的阈值 众所周知，彼此之间相似的灰度图像其阈值也非常接近。所以，我们可以 将阈值作为一种图像的特征应用到图像检索中来。人们对“阈值选取”的方法 已经进行了相当广泛而深入的研究，并且提出了多种技术和方法。 所有这些阈值化方法，根据使用的是图像的局部信息或者整体信息，可以 分为上下文无关方法( 也叫做基于点的方法) 和上下文相关方法( 也叫做基于 区域的方法) ：根据对全图使用统一阈值或是对不同区域使用不同阈值，可以 分为全局阈值方法和局部阈值方法，也叫做自适应阂值方法；另外，还可以分 为双阂值方法和多阈值方法等等一系列的方法。 在本文中我们主要介绍基于点的全局阈值选取方法中的最大类间方差法。 最大类间方差法f 2 6 】是由o t s u 于1 9 7 8 年提出的一种阈值选取方法，以 其计算简单、稳定有效，一直广为使用。从模式识别的角度看，最佳阈值应当 产生最佳的目标类与背景类的分离性能，此性能我们用类别方差来表征，为此 1 3 第二章特征提取 引入类内方差盯影、类间方差刍和总体方差砟，并定义三个等效的准则测 量： 入= 害k = 杀叼= 骞 仁 a wo 钰。量 出于对计算量的考虑，人们一般通过优化第三个准则获取阈值。但此方法 也有其缺陷，当图像中目标与背景的大小之比很小时方法失效。 在实际运用中，往往使用以下简化计算公式： 盯2 ( 丁) = 厂a ( p 口一p ) 2 + 名( p 6 一p ) 2 ( 2 x 3 ) ( 2 1 4 ) 锄i p i m 一1 肛口= ，舶= 号l ，p = z 。p i ( 2 1 5 )肛口= 广 ，舶= 一 ，p =夕，l z l a j a p i i = 0 i = 0i = 0 其中，仃2 为两类间最大方差，w a 为a 类概率，比为a 类平均灰 度，为b 类概率，为b 类平均灰度，p 为图像总体平均灰度。 即阈值t 将图像分成a ，b 两部分，使得两类总方差盯2 ( t ) 取最大值 的t ，即为最佳分割阈值。 对于彩色图像来说，我们使用2 1 3 颜色空间的“非均匀量化的方法， 已经计算出了图像像素的1 维颜色值。在此基础之上，我们采用上述阂值的 选取方法，计算出图像的阂值。将计算出的阈值作为一种图像的特征将其提取 出来。 2 4 特征提取 由于图像分割技术本身是一个至今尚未解决的难题，本文采用一种类似于 “四叉树分解”的图像，定义为“p 层四叉树分解”，它的优点是：不但可以 1 4 巩 一州 = 纯 。铷 = 峨 西北大学硕士学位论文 抽取结构化区域中的图像特征，而且从一定意义上讲它还保持了图像的空间信 息。所谓p 层四叉树分解就是：事先给定数值p ，首先计算出整幅图像的一个 低阶颜色矩和一种阈值，这就是对图像的第一层分解；然后将图像划分为4 个大小相等且互不重叠的区域( 子图像) ，对于细分出的四个子图像，分别计 算每个子图像的颜色矩和阈值，这是第二层分解；这样一直递归的进行下去， 直至划分到第p 层，整个分解过程结束【1 9 】。 给定一幅图像i ，一个低阶的颜色矩( 可以是一阶、二阶、三阶矩中的任 何一个) 以及一个阈值的选择方法，我们应用上述的p 层四叉树的图像分解 技术就可以将图像i 划分为一个子图像的集合。p 为事先给定的划分的最大 的层数，p 越大，图像被划分的越精细，所反应出来的“空间”信息就越多， 但相应的，图像特征向量的维数也就越高。对于任意的层数i ( 1 i p ) ，又 设a i i 为第i 层所有子图像的集合( 其中n i 为第i 层子图像的总数) ，则图 像i 可以表示为： p a = ( a 毛) ，啦= n ， n i = 4 ， 1 i p( 2 1 6 ) i - - - - l 其中，为划分出的所有子图像的总数。 对于第i 层分解出的每一个子图像马( 1 歹r t i ) ，其中啦为第i 层分 解出的子图像的总数，我们计算出它的特征向量( 乃i ，劣) ，其中巧i 为这个子图 像弓的一阶颜色矩，夕；为它的阈值( 这里采用阈值的最小内方差法) 。这样 就可以得到整个图像i 的高维特征向量： s = ( r 。，磋，磁) ， n i = 4 扣1 ，1 isp( 2 1 7 ) 其中毫为第i 层所有子图像的特征向量所组成的序列，根据子图像在原图像 中的位置，按照自上而下、自左而右的顺序进行排列而得到的，即 砭。= ( 巧，乃i ，、 ，lj = 1 n l ( 2 1 8 ) 我们就用这种p 叉树分解方式提取的图像的特征向量来表示图像，并以此来 实现基于内容的图像检索。 15 第二章特征提取 设s 为使用上述方法导出的图像的特征向量，则 s = ( ( i ，9 ) ，( t ；，夕 ) ，( ；，夕扒( ，蠕) ) ( 2 1 9 ) 为简化起见，我们用两个子特征向量t 和g 来表示s ，即s = ( lg ) 。 这里t 表示图像的一阶颜色矩组成的子特征向量，g 表示图像阈值组成 的子特征向量。我们有： r = ( t l ，t ；，缓，) = ( t l ，t 2 ，) ( 2 2 0 ) g = ( g l ，9 ，虼) = ( g l ，9 2 ，鳊)仇= r t i ( 2 2 1 ) i = 1 我们可以看到，这种方法提取的图像特征的维数会随着事先给定的最大分 解层数p 的增大呈指数型的上升，例如当p = 5 时，特征向量的维数为3 4 1 。 用此高维的特征向量来检索图像，其缺点是显而易见的，不但提高了存储开 销，而且提高了检索的计算复杂度，从而会进一步影响算法的效率。一个自然 的想法就是降维，在保留特征向量大部分“信息”的前提下，尽量降低特征向 量的维数，使用降维后的特征向量来索引图像，并据此实现基于内容的图像检 索。而之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量的 冗余信息，因为有些变量和数据集中的其它变量之间具有很强的相关性( 例如 是其它变量的线性组合或是其他函数依赖关系) 。这些冗余在处理时常常消耗 过多的系统开销，在许多情形下可以一定程度上剔除这些冗余信息，从而获得 更加“经济”的向量表示形式。 1 6 m p 汹 = m 西北大学硕士学位论文 3 1 降维的定义 第三章数据降维弟二早裂j 7 占陴z 隹 定义3 1 对d 维空间上的一个数据集x = x l ，x 2 ，z n ，戤r d ，数 据集y = l ，y 2 ，鲰) ，y i r m ，( m d ) 称映射 f ：x y 甄hy i = f ( x i ) 为从x 到y 的一个降维【3 1 。 3 2 降维的方法 一般情况下，我们把降维方法分为两类，一类是线性降维方法，另一类是 非线性降维方法。 定义3 2 对数据集x = 忙1 ，x 2 ，z n ，x i r d ，通过映射f 。；， z ；， ( 3 1 ) 得到低维空间中的数据集y = 可1 ，y 2 ，) ，y i ，( m d ) 如果f 是 线性函数，称f 为线性降维【1 2 】；反之，则称之为非线性降维 1 4 】。 而非线性降维方法的另一个方向是将原始空间划分为一些局部子空间的集 合，我们把这些小的子空间近似的看作是线性的，在这个小的子空间上我们采 用线性的而方法来降维。但采取这种方式降维会导致每一个小的子空间都有一 个自己的坐标系，这显然会是一件非常麻烦的事情。然而这种用局部来逼近全 局的思想确实十分值得借鉴的f 1 5 j 。 】7 、ll-、 、，、， h 二 毋瑚 确 1 1 1 2 1 n z z z ，j，i，j、 f f ； f ，jj-。一 第二章数据降维 3 3 本征维数 降维的目的是提取数据集在某一方面最本质的信息，以便减少其在分析、 处理时的难度。若我们选取降维空间为d 维欧式空间，那么降维问题就的一 个重要方面就是如何确定数据集的本征维数d 2 4 】。所谓的本征维数，是指一 个数据集所表示的空间对象最本质的维度，而不是其所在空间的维数。从几何 的角度上来看，本征维数是d 维高维空间中的采样点可以近似嵌入的低维流 形的维数d ( d d ) 。值得我们注意的是，本征维数不仅与数据集合的本身 特性有关，而且在很大程度上，它也依赖于具体的问题形式。在实际处理当 中，人们经常是在一定的先验信息之下，来探求数据集合的本征维数。 由此可知，数据集的本征维数的概念也是一个相对模糊的概念。因为不同 的数据在同一个数据集中也很可能呈现出不同的特性，如果把所有的高维数据 均表示在同一个固定的模式下，不可避免的会带来大量的信息的丢失。因此， 为了获取高维数据更为准确的降维结果，我们可以从数据集的单个样本点出 发，将单个样本点的本征维数作为整个数据集本征维数的一个重要参考。这样 一方面达到了对高维数据降维的目的，同时也最大限度的保留了原始数据空间 的整体和局部信息。 3 4 局部线性嵌入( l l e ) 法 l l e 方法【1 7 】是s u a l 和r o w e i s 于2 0 0 0 年提出的一种非线性降维方法， 这个算法的主要思想属于非线性降维的第二个方向。它用局部的线性来逼近整 体的非线性，通过保持局部的拓扑结构不变，互相重叠的局部邻域来提供整体 的信息，进而保持整体的拓扑信息。经过具体实践的检验，l l e 方法被认为 是一种非常有效的降维方法，已经被成功的运用于各种有关模式识别的问题之 中。下面图3 1 所示是一个l l e 方法应用于数据降维的例子。首先，它将三 位空间中的连续数据图a 离散化，见图b ，然后将离散数据映射到二维空间中 ( 见图c ) 。如果将图b 中内外两端的数据看成是分布在三维空间中的两类数 】8 d m * i 据，通过非线性局部嵌入以后，降维以后的数据在二维空间中仍然保持相对独 立的两类数据。 l 蓑 图3 1 ：l l e 降维 给定离散的数据集x x = x l ，x 2 ，：c n ，4 ( 1 l n ) 通 过l l e 算法输出向量，船，蜥 ，n 俨咖! i s ) ，m d 。 l l e 的主导思想是： ( 1 ) 如果两个数据点 毛，q 在高维空间中是不 同的两个点，通过l l e 变换后，它们在低维空间中所对应的两个点协，弛) 也一定是不相同的。( 2 ) 如果 z n z 豳，5 “) 是。的 个近邻点，那 么 驴1 ，y i 2 ，瑚k ) ( 1 曼；兰n ) 也必定为n 的k 个近邻点。 具体算法可以归结为三步： ( 1 ) 寻找相对于丑( 1 蔓z 曼n ) 欧式距离最近的个点规定为q 的k 个近 邻点女是预先设定的值。 ( 2 ) 由每个点z 。，( 11 2sn ) 的月个近邻点计算出该点处的局部重建权值 矩阵。 ( 3 j 由该点处的局部权值矩阵及其近邻点输出该点的低维向量。 热黟 第三章数据降维 图3 2 ：寻找邻居节点 我们可以看到对于点x i 、它的邻点巧和它们的局部线性组 合j 巧= 翰，其权值满足jw i i = 1 u 球健 f 。口。气。母技帽辅繁盘 r ，、 、 ， 巳。，一，7 斑八翻越傍它鹅 图3 3 ：l l e 算法 定义一个误差方程删，= 莩卜手1 2 ，式中啪乩2 ，闱 为鼢的k 个近邻点。为计算出权值w i j ( 1 i 礼，1 歹后) ，我们最小化误 差方程 满足两个条件： e c ，= 莩l 黾一莩伽巧z 巧1 2 c 3 2 ， e ( ) = b 一伽糊l ( 3 2 ) 4 l j i 西北大学硕士学位论文 条件( 1 ) 点x i 只能通过其k 个邻点来构建，如果x i 不是它的邻点之 一，则w i j = 0 条件( 2 ) w i j = 1 j 有上述条件( 1 ) 可知权值矩阵w 是一个对称阵，则对于数据的旋转 变换、尺度变换具有不变性；又由条件( 2 ) w i i = 1 可以得到对于数据 j 的平移变换也是不变的。 为求取局部权值矩阵，构造一个k 宰k 的局部协方差矩阵q q ；m = ( z t z 巧) t ( 翰一x i m ) ( 3 3 ) 采用拉格朗日乘子法，即可求出局部最优化重建权值矩 肾驴巧7 飞- 1 扣嚣) 4 ) 通常情况下，上式中的为奇异矩阵，我们必须将其变为非奇异矩阵， 对q i 进行正贝4 化，引入一个正则化参数r