（计算机软件与理论专业论文）图象检索中若干距离度量算法研究.pdf

摘要 摘要 高斯混合( g m s ) 函数表示图象内容是一种流行的方法，它比直方图方法能够 更有效地描述图象内容，基于g m s 的距离度量算法的研究已经成为基于内容图 象检索的研究热点。本文主要研究基于g m s 模型的两种距离度量算法，一种是 最优化方法，其代表算法是旅行商距离( e m d ) ，另一种是统计方法，其代表算法 是渐进似然估计( a l a ) 距离，并且分别对它们提出了相应的改进算法本文的主 要内容如下： ( 1 ) y o s s i r u b n e r 提出了基于直方图及e m d 的图象检索算法，由于直方图 不能很好地描述图象的内容。本文在他的基础上提出使用高斯混合的期望最大 ( g m e m ) 算法进行图象描述，为e m d 算法提供更恰当的概率模型。实验结果表 明这种g m e m 聚类加上e m d 距离度量的方法可以有效地提高检索效率。 ( 2 ) 统计方法在图象检索中具有检索精度高的优点，但其代价是计算量很 大。为克服该缺点，n u n ov a s c o n c e l o s 提出了a l a 算法有效地减少了计算复杂 度。然而这种距离度量方式会使高斯混合模型方差较大的数据库图象产生误判。 为此，本文提出了改进的a l a 算法即i a l a ，即利用分层的方法来提高检索精 度。 ( 3 ) 例图混合成分的集中时，用i a l a 算法效果较好；反之，用e m d 可以 收到好的效果，这两种算法是互补的。本文进一步提出了测度选择( m e a s u r e m e n t s e l e c t ( m s ) ) 算法，即根据例子的特征来选择最好的距离度量算法。 ( 4 ) 原始的e m 算法的无法跳出局部最优。本文提出了改进的e m 算法并 将它应用于基于内容的图象检索中本文的i e m 算法在迭代开始时用小方差； 迭代过程中采用分裂操作，及删除操作来得到有意义的混合成分来使得e m 算法 跳出局部最优 关键字：基于内容图象检索；高斯混合函数：旅行商距离；渐进似然估计算法； 期望最大算法 ：奎三些查兰至圭兰堡当三 a b s t r a c t g a u s s i a nm i x t u r e s ( g m s ) m e t h o di sap o p u l a ra p p r o a c ht or e p r e s e n tt h ec o n t e n t o fa ni m a g e i tc a r r i e sm o r ei m f o r m a t i o nt h a nh i s t o g r a mm e t h o d t h e r ea r el o t so f s i m i l a r i t ym e t r i cb a s e do ng m s t o ws i m i l a r i t ym e t r i c e sa r ed e s c u s s e di nt h i s d i s s e r t a t i o n , t h ef i r s to n ei so p t i m i z a t i o nm e t h o d ，t y p i c a l l ye a r t hm o v e r sd i s t a n c e ( 功泪) ) ；t h es e c o n do 粥i sp m b a b i l i s t i ca p p r o a c h , t y p i c a l l ya s y m p t o t i cl i k e l i h o o d a p p r o x i m a t i o n ( a l a ) d i s t a n c e t h i sd i s s e r t a t i o na l s or e s e a r c ho nt h em e t h o d st h a tf i t g m sm o d e lt h em a i nw o “【so f t h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l i o w s f i r s t l y , e m dc o n d u c t sas i m i l a r i t ym e t r i cm e a s u r e m e n tb ym i n i m i z i n gc o s t s , w h i c hp e r f o r m sb e r c rr e t r i e v a lr e s u l tw i t hr e l a t i v e l yl o wc o m p u t a t i o n a lc o m p l e x i t y t h ea c c u r a t em e a s u r e m e mb e n e f i t sf r o mt h ep r o p e r l yf o r m u l a t e dp r o b a b i l i s t i cm o d e l o fa ni m a g e ，w h i l et h em o d e l sb a s e do nh i s t o g r a ma n dv e c t o rq n a n t i z a t i o n ( v q ) e a n n o te 币c i e n t i yd e s c r i b et h ei m a g ei n f o r m a t i o n i nt h i sp a p e r , w ei l s eg a u s s l a n m i x t u r ee m ( g m e m ) a l g o r i t h mt od e s c r i b ea n 自l i l a g ea n df o r mab e t t e rp r o b a b i l i s t i c m o d e lf o re i v l da l g o r i t h m , w h i c hr e s u l t si nt h eg m e m + e m da l g o r i t h m e x p e r i m e m ss h o wt h a tt h ee m dm e a s u r e m e m sb a s e do i lg m e mc l u s t e r i n gc a n i m p r o v et h er e t r i e v a lp e r f o r m a n c ee f f e c t i v e l y w e a l s oc o m f i b m ean e wf e a t u r e r e p r e s e n t a t i o nm e t h o d ，w h i c hi n c r e a s e st h ew e i g h t so fi m a g et e x t u r e s ，r e d u c 韶t h e n u m b e ro f t h es u b b l o c k so f a ni m a g e , a n dt h e r e b ys p e e d sl 巾t h ec o m p u t a t i o n s e c o n d l y , s i m i l a r i t ym e t r i ci sak e ys t e po f c o n t e n tb a s e di m a g er e t r i e v a l ( c b i 鼬 a n di ta l s oo n eo f t h ed i f f i c u l t i e s p r o b a b i l i s t i ca p p r o a c h e sa r cap m m i s i n gs o l u t i o nt o t h ei m a g er e t r i e v a lp r o b l e m , a n da l a a l g o r i t h mi so n eo f t h ee x c e l l e n tm e a s u r e m e n t s o fp r o b a b i l i t ys i m i l a r i t yf u n c t i o n , w h e nt h em i x t u r ec o m p o n e n to ft h eq u e r ys p r e a d a r o u n dt h ee x p e r i m e n tr e s u l t ss h o wt h a tt h ea l aa l g o r i t h mi st h eb e s t b e c a u s eo fi t s e a s yf o rt h i sa l g o r i t h mg e t sb a dp e r f o r m a n c e ；w eu s em u l t i - l a y e ra p p r o a c ht or e d u c e t h ei n f l u e n c eo f t h i ss i t u a t i o n , a n dc a l li ti m p r o v e da l a ( i a l a ) a l g o r i t h m t h i r d l ) ：i ft h em i x t u r ec o m p o n e n to ft h eq u e r yg r o u pt o g e t h e r , t h ea l a a l g o r i t h mp e r f o r m sb a d l y , t h i si st h et i m ew eu s ee m da ss h n i l a r i t ym e t r i ci n s t e a d , a n dw ec a l li tn 弛a s u r e m e n ts e l e c t m g ( m s ) a l g o r i t h m i tu s e st h e p r o b a b i l t yf e a t u r eo f q u e r y sg m s t os e l e c ti a l ao re m da ss i m i l a r i t ym e t r i co f c b i r s y s t e m f i n a l l y , c b i ri sm a i n l yc o n t a i n e do ft o wp h a s e s ：f i r s t ，t or e p r e s e n ta l li m a g e ； s e c o n d , t om e a s u r et h ed i s s i m i l a r i t yb c l m ，咖i m a g e s i nt h i sp a p e r , w ei n t r o d u c ea l l i m p r o v e de x p e c t a t i o n - m a x i m i z a t i o n ( e m ) a l g o f i t h mf o rc l u s t e r i n gg m st or e p r e s e n t a l li m a g e ，i n s t e a do f r e g u l a re m a l g o r i t h m k e yw o r d ：c o n t e n tb a s e di m a g er e t r i e v a l ；g s u u i a nm i x t u r e s ；e m d ；a l a ： e x p e c t a t i o nm a x i m i z a t i o na l g o r i t h m m 独创件j 明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包括其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过得成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的声明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字： 彩嘭眨 论文作者签字：j 乏杨碍囱c 2 0 0 7 5 月落日 第章绪论 1 1 研究背景 第一章绪论 随着多媒体技术和互联网的迅速发展，包括图象、音频和视频等信息的多媒 体数据大量涌现。互联网多媒体的发展极大方便和丰富了人们的生活，同时也给 人们提出了新的课题：即如何管理和组织这些海量的多媒体信息? 在2 0 世纪7 0 年代始人们利用常规关系数据库管理系统来管理多媒体数 据，其典型框架是由人工注解多媒体数据，再利用基于文本的数据库管理系统来 检索图象。这种思路虽然可以利用许多成熟的文本检索技术，但存在着两大困难： 一是人工注解工作量太大，尤其是对于大型的多媒体数据库；二是人工注解的主 观性和不准确性可能导致检索过程中的失配。常言说。一图胜千言”，蕴含在多 媒体数据中的丰富内容有时难以用语言表达，或者不同的人会有不同的表达，这 都为基于人工注解的多媒体检索带来困难。在这样的背景下，基于内容的多媒体 检索应运而生。 基于内容的多媒体检索是指由计算机自动提取媒体对象的内容，如图象的颜 色、纹理、形状，声音中的音调、响度、音色，视频中的镜头、场景、镜头的运 动等，再按照这些客观的特征进行检索。这些特征通过计算机自动提取的方式获 得，可克服传统方法中工作量大、主观性强和难于用语言描述等弊端，适用于大 规模的数据检索。 目前基于内容的文本检索系统已经得到了成功的应用，但是对于图象、视频 和音频等非结构化数据的检索仍然是个非常困难的问题。这是因为描述文本的单 词在某种意义上是一个语义对象，而图象在计算机中存储为二维的像素点阵列， 视频为二维的像素点阵列加上一维的时间序列，这些需要经过计算机处理分析才 有可能得到语义信息，然而，目前的计算机视觉和图象理解的水平远未达到这个 目标 为了方便检索多媒体数据，运动图片专家组m p e g 于1 9 9 6 年开始制定 m p e g - 7 标准m p e g - 7 也称为。多媒体内容描述接口”( m u h i m e d i ac o n t e n t d e s c r i p t i o n i m e 嘀) ，其目标是产生个描述多媒体内容的标准，支持对多媒体 广东工业大学硕士学位论文 信息在不同层面上的解释和理解，从而使其可以根据用户的需要进行传递和存 取。为此，m p e g - 7 标准提出了多媒体内容描述子的概念 1 ，用于描述多媒体 信息的颜色、纹理 2 1 、形状 3 、运动 4 等特征，但是m p e g 7 标准只是对内 容的描述制定标准，而不涉及如何提取和表示这些特征或内容，也未涉及具体的 搜索引擎方法。m p e g - 7 标准回避的正是基于内容信息检索中最困难的问题，因 此，虽然m p e g 7 针对基于内容的多媒体检索制定了标准，仍存在很多问题需 要研究者们继续努力。 图象是一种广泛应用的多媒体数据，本文的研究内容集中于基于内容的图象 检索( 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 a m ) 。c b i r 的应用范围非常广泛，如多 媒体数字图书馆、商标与版权数据库管理、医学图象管理、遥感与地球资源的管 理、艺术馆与博物馆的管理、建筑工程设计、时装设计、地理信息系统、网上购 物、罪犯调查等许多方面。它涉及信息检索，图象处理，计算机视觉，机器学习， 人工智能，数据库等诸多领域，是一个很有发展前途的研究方向，具有重要的研 究意义和巨大的实用价值。 1 2 基于内容图象检索的问题描述 一般来说，一个图象检索系统支持如下一个或多个检索方式： 口随机图象浏览 二基于例图的图象检索 二基于草图的图象检索 二基于关键字的图象检索 二根据定制图象类别进行导航 其中基于例图的查询( q u e r y b y e x a m p l e ，q b e ) 是最常用的查询方式，本文 也将采用这一方式。 从查询的目标看，检索任务主要可分为两大类： ( 1 ) 目标搜索( t a r g e ts e a r c h ) ，即期望的输出是一幅特定的目标； ( 2 ) 类别搜索( c a t e g o r ys e a r c h ) 即期望的输出是一类图象 本文的研究范围限定于基于例图的目标图象俭索 1 第一章绪论 1 3 基于内容图象检索的研究现状 1 3 1 基于区域的图象检索 基于区域的图象检索试图通过图象分割识别出图象中的对象从而得到图象 语义。对于颜色纹理等全局特征而言，对象的特征与背景的特征无法区别，因此 同一对象在不同背景下的图象特征可能相差很远。如果能把对象从背景中分割出 来，则可对其单独提取特征( 形状信息也可以加入) ，减少由于对象在图象中位 置变化、背景变化带来的影响，从而接近语义检索的目标然而，图象分割仍是 目前计算机视觉中的难点问题，仅仅在简单的情况下，才可能得到理想的分割结 果。不精确的分割结果给目标识别及图象匹配带来困难，但仍有许多基于区域的 检索研究取得了较好的效果，典型的系统有： 二v m u a i s e e k 最早基于区域检索的系统是哥伦比亚大学开发的龇a l s e e k 5 ，它主要研 究图象区域的空间关系查询和从压缩域中抽取视觉特性。系统所采用的视觉特性 是颜色集和基于小波变换的纹理特性，为加速检索过程，采用了基于二叉树的索 引算法。v i 啪l s e e k 支持基于视觉特征和它们之间空间关系的查询。 口n e t r a n e t r a 6 是u c s b 大学开发的基于图象分割的检索系统它利用图象区域的 颜色、纹理、形状及空间关系等信息从图象库中检索相似的区域。n e t r a l 系统 与n e t r a 2 系统分别采用了“e d g ef l o w ” 7 与“j s e g ” 8 两种分割方法。 口b l o b w o r l d b l o b w o r l d 是c a l i f o r n i a 大学b e r k e l e y 分校开发的基于图象分割的检索系统 9 该系统的一个重要特点是用户可以清楚地看到图象的表示，提交查询的同 时，可以定性规定所选区域和其它区域的重要程度，以及各区域的各种特征( 颜 色、纹理、形状、位置) 的重要程度，从而使用户能清楚地理解查询结果。 n e t r a 与b l o b w o r k i 较v i s u a l s e e k 更强调图象分割的效果，这两个系统都是 根据单个区域比较图象，但在实际中用户经常难以抉择指定哪块区域检索于是 为了减轻用户的负担，一些基于区域的系统提出了利用图象中所有区域信息对全 图进行比较的距离度量，如w a l r u s i o ，w i n d s u r f ii s i m p l l c i t y 1 2 等， 广东工业大学硕士学位论文 这种方法也可降低由分割不准确性带来的影响。 口s i m p l i c i t y s i m p l i c i t y 中提出了一种综合区域匹配( i n t e g r a t e dr e g i o nm a t c h i n g ，i r m ) 算法来定义图象的相似度。它具有旋转和平移的不变性，允许区域问一对多的匹 配，对不准确的分割比较鲁棒。 1 3 2 基于概率框架的图象检索 近几年来，基于概率框架的图象检索成为c b i r 领域的新热点 1 3 。主要的 代表有m i t 的v a s c o n c e l o s ，n 在文献 1 4 提出用g m s 表示图象，再用a l a 算法 来计算相似性。设查询图q 的特征记为岛，图象库d 中第i 幅图象的特征记为 只在检索过程中需要对d 中每一幅图象计算其与查询图q 在特征上的相似度： d ( 0 = d i s t a n c p oi i 毋。) ( 卜1 ) 前k 幅与q 具有最大相似度的图象被作为目标图象集合丁返回给用户在 这样的检索框架中，视觉特征与相似性度量是研究的重点。图象的低层视觉特征， 主要包括颜色、纹理及形状等。最常用的颜色特征是颜色直方图 1 5 ，它描述的 是像素在各量级颜色值上的分布比例。为在颜色直方图上加入空间位置信息，又 先后提出了颜色连通矢量 1 6 与颜色相关直方图 1 7 等方法。颜色矩 1 8 也是一 种重要的颜色特征，其突出优点是维数低。 1 4 论文各部分的主要内容 从以上综述可以看出，基于溉率图象检索方法具有良好的应用前景。本论文 的内容包括：用精确聚类后的g m s 来表示图象，及聚类后g m s 之间的距离度量 算法的研究。 论文具体的内容组织如下： 第一章是绪论，概述基于内容图象捡索的研究背景与研究现状 第二章介绍g m s 建模及度量算法 第三章提出了g m e m 聚类的e m d 图象检索算法，本章主要工作有：( 1 ) 由 于g m e m 算法初值的选取直接影响它的聚类效果，本章提出从图象本身出发寻 第一章绪论 找有意义的聚类，克服了分裂算法中出现空原子而可能导致得不到有意义混合成 分的问题；( 2 ) 提出了一种新的特征表示方法，该方法比 2 2 中提出的4 ：1 ：l 表 示方法的效果有较大改进。 第四章提出了l a l a 算法。该算法克服了a l a 距离对特征库中大方差图象 产生误判的缺点。 第五章提出了测度选择算法，有效地提高了检索效率。常用的两种算法e m d 和a l a 有各自的优缺点，本章提出用例子混合成分的集中程度来选择距离度量 算法，使得这两种算法达到取长补短的效果。例子的混合成分之间的最大距离可 以大致地看出混合成分的聚合程度，本章使用这个值来选择测度。 第六章e m 算法是一种贪婪算法，这会导致算法无法跳出局部最优。针对 e m 算法的这个缺点提出了i e m 算法，并且和传统聚类方法进行详细比较。 论文的最后一章总结全文工作，并展望进一步的研究方向 s 广东工业大学硕士学位论文 2 1 引言 第二章g m s 建模及度量算法 本文介绍的图象检索算法是属于q b e 查询方式。这种检索算法首先对数据 库图象的特征库，然后将例子特征和特征库中的特征进行距离度量并排序输出。 本文建立特征库和检索过程如下： 第一步，将图象分割成若干个小块并表示为特征向量集合伽，j = l ，2 ，j ； 第二步，对上述数据进行建立一个概率分布函数( p , 0 0 ；第三步，对例子和图库 中的图象都做第一和第二步操作之后，求取二者的p d f 之阃的距离，并排序，就 得到本文的检索结果。 - + 排序 输出 图2 - 1 建立特征库和检索过程 根据上述流程：本章着重介绍数据收集、建模的方法及c b i r 的距离测度。 2 2 小块特征的数据收集 2 2 1 颜色特征 因为一些实际应用的原因，有时候采用和( r ，g ，b ) 三刺激集合不一样的集合 ( r ，g ，) 会带来更大方便 1 9 但是不论哪种空间它和另一种空间是线性相关 的这是因为这个空b j 的任何两个刺激值之和要和另一个空间对应的两个刺激值 之和相对应两个刺激空间之间的变换为： 第二章g m s 建模及度量算法 r 2 q l r + a 2 l g + a 3 l b g 2 q 2 r + a 2 2 g + a 3 2 b ， b = q 3 r + 吩p + 码3 b 两组主激励集合都是线性独立的矩阵a 表示有上式中组成，记为： ( 2 - 1 ) 呜。 1 ( 2 2 ) 吗，j 式( 2 - 2 ) 矩阵的行列式值必不为零，设( r ，g ，印系统和( 置，g 。，b 。) 的激励分别 为，( ，g ，6 ) 和( ，。，g ，b ) ，这时对应激励的变换有： ( 2 - 3 ) 设a 矩阵的逆矩阵为口= 【包。a i ，j = 1 ，2 ，3 ，则( ，g 。，b ) 可以用表示为： ，= 6 l i ，+ 6 1 2 9 + 3 b g = 岛l ，+ 鱼口g + 参b 6 ( 2 4 ) b = 毛i ，+ 6 3 2 9 + k 6 在( r ，g ，曰) 色度空间中，在某些波段中对应的激励中存在负激励。这令人费 解，于是在1 9 3 1 年c i e 通过选取了特定的矩阵b 后，定义了另一种色度空间， 称为( x ，y ，z ) 这种变换后，完全包含了光谱的轨迹和紫线，( x ，y ，z ) 所对应的 激励值永远非负。 在计算色差时，用( 盂，g ，b ) 或者( x ，y ，z ) 是都达不到和人类视觉习惯一致的 效果而当时人们已经收集大量这方面的数据。c i e 通过对这些数据进行建模产 生了c i e l 9 7 6 ( c 甜v ) 空间。其参数如下定义： 其中， 嘶喹) ； 村= 1 3 。r ( 一t ) ； ( 2 5 ) v = 1 3 r ( v 。一v 二) ； 1 ； q q q _。l = a 广东t 业大学硕+ 学位论文 ， ) = 舭丽舻万露瓦；。 ( 2 7 ) 忙x + 1 5 y + 3 z 以2 瓦而知云 这个空间的极白点在r g b 空间中就是( 2 5 5 ，2 5 5 ，2 5 5 ) 。色差公式为： 砭= 【( 应) 2 + ( “) 2 + ( 加) 2 ，”( 2 - 8 ) 在颜色空间中，等式( 2 - 6 ) 定义的颜色空白j 称为c i e l 9 7 6 ( r “v ) 一空间，其色差 由式( 2 9 ) 定义。 2 2 2 纹理特征 纹理是用来刻画物体表面反映其视觉特性的一种属性。许多真实世界的物 体，如云、树、草、砖、水和头发等都以纹理属性作为它们的主要特征。由于自 然纹理的多样性，很难给纹理下一个精确的定义，一般认为图像的纹理指图像像 素灰度级或颜色的某种变化，而且这种变化是空间统计相关的。现在常用的提取 纹理特征的方法包括信号处理的方法和基于模型的方法。本节主要介绍基于小波 变换的纹理特征。 本章这里采用的小波纹理特征。小波变换具有多尺度、良好的空间和频率局 部性等优点，近年来在图像处理和模式识别中得到广泛应用。 闭子空间旷满足： c k c k c c c c ：( 2 9 ) 函数妒e ( 即尺度函数) ，使得 丸，一e z ) 是上的一个规范正交基有 九，玎ez ) 可以构造出另一组基函数规范正交基 ；，k e z 小波变换指将一 个信号分解成一族基函数规范正交基 j ；，七z ) ，其中数吩j o ) ，该基函数由 母小波( 工) 经平移和旋转得到，即蚧j o ) = 2 7 2 v ( 2 一胆x - k ) 。 回 嘟 嘶 专一 m 一 n 一 兰一争# 嘲 吼 第二章g m s 建模及度量算法 对= f i v f ( x ) e l 2 ( r ) ，定义为匕在巧。上的正交补，于是有：巧，= 形。巧 且上u 。) 厂( 其塔式分解可表示为： 尸= z d 谚o ，广= c 。i 九，= c 。l 九， 其中。 c ：= 瓦一，司- - z g - 二- ： tt 因此， ( 2 一1 0 ) ( 2 一1 1 ) 尸= ，+ 拈军幻+ 莩( 2 - 1 2 ) = 。 ( 2 - 1 6 ) 如果随机向量x 服从g m 分布，足= p n g ( x ，以，毛p ) ) 其中的协方差矩阵 第二章g m s 建模及度量算法 e ( s ) = s l ，v n ，i 为单位矩阵，占为小常数那么： 蝌川= 黜篡北叫旷晰f ， c z 一忉 c 并且觋只( 功5 善占。一肛) ，( m ) 2 3 4 直方图模型 特征向量s 的直方图是一个向量p = 锄9 t ，肌) 。这个向量对应的是朋羽个 划分z = 石，舶 的映射。b 就是s 中落入第i 个划分的百分比。这里可以看出 这种模型除了中，b c , 外，其它所有信息都被抛弃了，其表达式为： 雕) = 8 ( x - c , ) p , 1 1 它和v q 算法不同的是，其分块是武断的。 2 3 5 高斯混合模型 ( 2 1 8 ) 对于式( 3 1 ) 混合模型中的 ，( 引幺) ) 二，取p ( x l 只) = g ( 工，以，e ) ，于是得 到高斯混合模型的定义为： 尸( 曲= g ( x , l z ，毛) ， ( 2 - 1 9 ) 其g ( x , l a ，毛) 如式( 2 一1 5 ) 定义。本文对测度的研究建立在g m s 模型的基础上， 下面介绍g m s 建立的方法 2 4 期望最大算法的基本原理 2 4 1 算法简介 研究对已有数据和未知参数集口的一般情形假设参数的先验为p ( 力，则后 广东l 业大学硕+ 学位论文 验概率p ( o l x ) 和p ( x l 口) p ( p ) 成j 下比。现在，如果有了其他数据的话，找目的m a p 估计会更容易 3 2 。其中p ( x ，j i 口) 和p ( xd 可以通过边缘概率联系起来： p ( x l e ) = b ( 弘x l o ) d y 。 ( 2 2 0 ) 期望最大算法是一个可以使边缘后验概率函数p ( a i 收敛到最大值，而不需要 精确地控制边缘似然p ( x 1 0 ) 。 e m 算法是通过交替地应用e - s t e p 和m s t e p 来完成。正式地说，舀在t = 0 。1 2 上继承地进行参数估计。如式( 2 - 1 9 ) 定义的有限高斯混合模型，x 为膨 维随机变量，是高斯混合成分的个数，啦是高斯混合成分的先验概率。 2 4 2 单调性 注意函数占( 口) ：r p 寸r ，其最大值和所要搜寻的口相对应。如果是m a p 标 准的话，可以取l o g p ( 口i 工) ，下面证明占( 口) 是单调增加的。 将迭代定义为： 秒= 孤g 峄忙妒) 一p , a ( o ，蚋 ( 2 - 2 1 ) 其中层是正常数，d ( 只参。) 是惩罚函数，而且满足d p ，参) 2 0 当且仅当秽= 参。 时，等号成立。 由( 2 - 2 1 ) 定义的迭代满足： 占( 参) 一属d ( 伊“，参) 占( 参h ( 2 - 2 2 ) 则 s ( 参) 一占( 伊) 届d ( 伊“，参o ) o ( 2 - 2 3 ) 取“d = l o g ( x i e ) + l o g p ( o ) o c l o g p ( e l x ) ，且： d ( e ，伊) = 仇p ox ，参”) l lp ( ylx ，口) 】 第二章g m s 建模及度量算法 = 如妒g 筹辫砂 斗g 篇坩。 ( 2 2 4 ) 则，根据( 2 - 2 1 ) 得： 伊= a r g m 笋o l o g p ( o i x ) - e i l o g 锚鲁k 砂 ) = a r g o m o m o m o m 铲 l o g p ( o ) + l o g ( p ( 工i 口) + e i l o g p ( y , x l e ) l 工，痧 ) 2 a r g 峄 l o g p ( 力+ e 1 0 9 p ( y ，工l e ) i x , 参。 ( 2 - 2 5 ) e m 得单调性使得它依赖于它的初始化，可能进入局部最大。 2 4 3 收敛到静态点 单调性不是p ( o i 力收敛到最大值的充分条件。证明这种收敛性要求 l o g p ( o x ) 和对d e p ( y i x , j ) i i p ( y i x , o ) 是光滑的。将e m 算法固定在一个点 上，则，寸c o 时，有 参4 = a r g m 字x o l o g p ( o i x ) 一巩【烈j ，i 毛参) i i p ( y l x , e ) ，( 2 - 2 6 ) 因为对口两个表达式都是光滑的，则伊。肯定是静态点即； 8 1 0 9 p ( o l x ) 1 0 0 甜- i _ 亟殴坦型8 0 也业趔b = o 。 ( 2 2 7 ) p 弘l 脚”。 ”。” 2 4 4 高斯混合的方式 设x = 岛，j ；l 2 ，“棚为样本集，其概率密度函数为： 烈毛i 口，口) = p ( 葺i 吃) ， ( 2 2 8 ) n s l j 若其似然函数为：l ( a ，见j ) = l o g 从而i 吃) 则没有闭式答案( c l o s e d f o r m 扣l i l l ， 广东丁业大学硕士学位论文 s o l u t i o n ) 。在混合的e m 算法中，这里为每个样本加上一个标签，毛= 斛彳) 表 示属于那一类，并将z ，看成是丢失的数据，加入似然函数得： j jn l c ( a ，口，x ，z ) = l 0 9 1 - i p ( ，刁i 口，见) = e z , l o g ( a p ( x , i b ) ) ， ( 2 2 9 ) 其中，互是似然函数中是线性的。则： q ( a ，口l 舀”，参) = e l c ( a ，0 ，x ，z ) lx ，五( ”，占( 】 = l c ( a ，o , x ，e i zix ，砂】) ( 2 3 0 ) 由于z 都是二进制的变量，为了减少e s t e p 的计算量，将它精简为，有： w j ，詈( ，ix ，蠢，参n ) = p r ( 彳= llx ，西“，参) ( 2 3 1 ) 这就是属于第s 类的概率，由贝叶斯公式得： ，：掣旦剑塑， 坼j2 可。：2 。 彰p ( 渺) ( 2 - 3 2 ) 注意到式( 2 - 2 9 ) 中的l o g a ，实际上是线性的，的极大似然估计为 = 了i 陲j ， ( 2 - s s ) 而参数0 的更新方式如下： 怠= 鹕警喜w , , , l o g p “， ( 2 - 3 4 ) j 对于具体的概率密度函数p ( t 1 只) ，可以令，l o g p ( x ，j 晓) 对只的导数为零的 到。一般地，式( 2 3 2 ) ，( 2 - 3 3 ) 称为e s t e p ，式( 2 3 4 ) 称为m s t e p 。 2 5 距离度量算法 对每一类产生一个概率密度函数咖l ， l ，2 m ，例子的p 够为尼( d ， 数据库图象的特征集为毋。( n f = l ，m 1 4 第二章g m s 建模及度量算法 2 5 1 常用的距离度量算法 测量中用得最多是两个密度函数之白j 的p 范数，即： d ，( 岛。毛) = a r g 唧n ( j l 岛( x ) 一只，( x ) i d x ) ( 2 - 3 5 ) 这种方式一般用在基于颜色的图象检索中，它是计算颜色直方图之问距离的 标准算法假如直方图被规范化，厶距离的最小值等于直方图交集( h i ) 距离的最 大值，即： d , ( v q i i v , ，) = 8 f g m 奸m i n 【尼( ”) ，只，( w ，) 】 ( 2 3 6 ) 另一种常用的测度是二次距离： m , ( p i ip ) = l 一一旺， ( 2 3 7 ) 其中，丑可以是两个类中的某个协方差，也可以是单位矩阵 2 5 2 期望对数距离 设j 为图象的特征空间，】，为分类指示变量则，相似度函数为： g ：x - - y 2 1 一，柳，( 2 3 8 ) 那么，是分类误差概率p ( g ( x ) y ) 最小的相似度函数是b a y e s 或m a p 相似 函数： g ( x ) = a r g m p ( j ，= f i x ) = a r g m 警乏l o g c ( t ) + l o g p ( y = d ， ( 2 3 9 ) 上式中，我一般假设先验概率p ( r = o 相等，这样m a p 相似度函数也被称 为极大似然( m l ) 函数。 上述说法的推论是m l 相似度函数是趋近于p ( 力在只力下的e l 距离为： g ( 对= a r g 埘警e “p 只) = 踟苫m p o ) l o g v 。( x ) d x k l 散度 3 3 如下定义。 k l ( = p ( 功堍怒凼 格 广东工业大学硕士学位论文 因为尸( x ) 独立于i ，这就是说上述式子的值和使k l 散度最小的值是一样的。 2 5 3 旅行商距离的基本原理 e m d 反映一种概翠分布转换到另一种概率分布时，移动权值所需的最小工 作量。 设z ，是第，个和第，个混合成分之间的不相似度4 ，= 既p ( 一9 一一一0 ) ， f ，表示最优化流，是一个正常数那么最小工作量问题可以描述为： m m d ( q 舻瓷， t z ， 满足：，f 。= 忍，巧，= b ， ( 2 4 3 ) 其中，上述条件极值问题可以由单纯形法求解。 2 6 本章小结 本章主要介绍了基于g m s 的建模方法和基本的距离度量算法。 首先，本章介绍了两种常用的表示方法：颜色和纹理。对给出了这两种特征 的基本原理。其次，本章讨论了数据的收集方法及其建模方法，这是整个系统最 基本的地方，直接影响了系统的检索效果，最后介绍了一些基本的距离度量算法 由于数据量过大，在图象检索的过程中，不能对这些原始的数据进行比对。 在后续的章节中本文将介绍如何通过e m 算法将这些数据建立g m s ，然后用a l a 或者e m d 算法进行距离度量。 第三章雄丁g m e m 聚类的e m d 图象检素 第三章基于g m e m 聚类的e m d 图象检索 3 1 引言 图象距离度量和图象的表示受到广泛的重视。这两类算法是相互影响的，只 有在它们结合得很好时，才能得到较好的检索效果。 e m d 算法首先由y o s s ir u b n c r 等在 2 1 中引入到图象检索中来，是结合纹 理和颜色特征的一种优秀的距离度量( s i m i l a r i t ym e t r i c ) 算法。文 2 1 1 中表示图象 的概率模型是采用直方图算法，该算法的操作过程是对数据的每一维进行量化得 到若干个原子，然后统计落在每个原子的数据数目占整个数据集的比重。可以看 出，原子个数是随数据的维数的增加而迅速增加的。文献 1 4 中提到用v q 算法 聚类的方法，v q 迭代采用分裂( s p l i t t i n g ) 的方式，但它很可能得到有意义的混合。 成分( m i x t u r ec o m p o n e n t ) ，即会产生空原子( e m p t yc e i l ) 。这两种算法都不能为