（计算机软件与理论专业论文）基于多特征的相片聚类算法研究与实现.pdf

中山大学硕士论文基于多特征的相片聚类算法研究与实现 论文题目： 专 业： 硕士生： 指导教师： 基于多特征的相片聚类算法研究与实现 计算机软件与理论 邱志豪 李文军教授 摘要 随着数码技术的快速发展和数码相机的广泛使用，用户将不断收集大量的个 人数码相片，如何帮助用户组织和管理这些相片是一个重要的问题。聚类技术是 解决这个问题的主要方法之一，传统的相片聚类算法主要使用时间和内容信息来 对相片集进行聚类，但它们一般都是尝试使用单个特征来聚类，或使用多个特征 进行聚类时总要基于预先设定的阈值。这样做法存在不足之处：1 ) 单个特征不 能处理复杂的相片集；2 ) 预先设定的阈值不能自适应满足用户多样化的相片集。 本文在对现有相片聚类算法进行调研后，将这些相片聚类算法进行分类总 结，并讨论和分析它们的不足。考虑到现有相片聚类算法使用单个特征来聚类只 能满足用户单方面需求的情况，本文提出了一个通用的相片聚类框架，该框架可 以将现有流行的相片聚类算法集成进来，并根据用户具体需求来联合调用多个相 片聚类算法来执行，以达到满足用户多样化需求的目的。考虑到现有相片聚类算 法不能满足画册制作所需要小粒度相片聚类的要求，本文提出了一种基于多特征 的相片聚类算法，该算法联合使用时间、内容和亮度三个特征来对相片集进行聚 类，通过自适应给各个特征分配适当权重来计算出相片之间的相似度，再使用递 归图划分的方法将相片集划分成小粒度聚类，以达到满足画册制作的要求。 本文的主要贡献如下：1 ) 针对当前单个特征不能满足用户多样化需求，设 计一个通用的相片聚类框架；2 ) 在结合时间和相片内容信息的基础上，引进光 学信息来提高相片聚类效果；3 ) 提出一种多特征自适应权值的图划分相片聚类 算法，有效地解决了自动画册制作所需要的小粒度聚类问题。 关键词：相片聚类算法、相片聚类框架、多特征自适应权重、图划分 中山大学硕士论文基于多特征的相片聚类算法研究与实现 t i t l e ：r e s e a r c ha n di m p l e m e n t a t i o no fp h o t oc l u s t e r i n ga l g o r i t h m b a s e do nm u l t i v l ef e a t u r e s m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z h i h a oq i u s u p e r v i s o r ：p r o f w e n j u nl i a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd i g i t a lt e c h n o l o g ya n dt h ee x t e n s i b l eu s eo f d i g i t a lc a m e r a s ，u s e r sw i l la c c u m u l a t eal a r g en u m b e ro fp e r s o n a lp h o t o s ，h o wt oh e l p u s e r so r g a n i z ea n dm a n a g et h e s ep h o t o si sa ni m p o r t a n ti s s u e c l u s t e r i n gt e c h n i q u ei s a ne f f e c t i v em e t h o dt os o l v et h i sp r o b l e m t r a d i t i o n a lp h o t oc l u s t e r i n ga l g o r i t h m s m a i n l ye m p l o yt e m p o r a la n dc o n t e n ti n f o r m a t i o nt oc l u s t e rp h o t o s ，b u tt h e yu s u a l l y t r yt ou s eas i n g l ef e a t u r et oc l u s t e rp h o t o s ，o rt h e yf u s em u l t i p l ef e a t u r e st oc l u s t e r p h o t o sb a s e do np r e d e t e r m i n e dt h r e s h o l d t h ea b o v em e t h o d sh a v ef o l l o w i n g d i s a d v a n t a g e so b v i o u s l y ：1 ) s i n g l e f e a t u r ec a n n o th a n d l et h ec o m p l e xp h o t o c o l l e c t i o n 2 ) p r e d e t e r m i n e dt h r e s h o l dc a n n o tb ea d a p t i v et om e e tv a r i o u sp h o t o c o l l e c t i o n s t h i sp a p e rf i r s t l yi n v e s t i g a t e sa n ds u m m a r i z e st h ee x i s t i n gp h o t oc l u s t e r i n g a l g o r i t h m s , t h e nd i s c u s s e sa n da n a l y z e st h e i rd e f i c i e n c i e s c o n s i d e rt h a te x i s t i n g a l g o r i t h m su s i n gas i n g l ef e a t u r et oc l u s t e rp h o t o sc a no n l ys a t i s f yu s e rr e q u i r e m e n t u n i l a t e r a l l y t h i sp a p e rp r e s e n t sau n i v e r s a lp h o t oc l u s t e r i n g 丘a r n e w o r k ，w h i c hc a n i n t e g r a t ee x i s t i n gp o p u l a rc l u s t e r i n ga l g o r i t h m s ，a n dc o m b i n es e v e r a lc l u s t e r i n g a l g o r i t h m st or u ni na c c o r d a n c ew i t ht h es p e c i f i cn e e d so fu s e r s i no t h e rw o r d s t h i s 蠡a m e 、v o r kc a na c h i e v et h ep u r p o s eo fm e e t i n gt h ed i v e r s en e e d so fu s e r s c o n s i d e r t h a te x i s t i n gp h o t oc l u s t e r i n ga l g o r i t h m sc a n n o tg e n e r a t es m a l lc l u s t e r st h a tc a nb e u s e dt om a k ea p h o t ob o o k ，t h i sp a p e rp r e s e n t sa n o v e lm u l t i - f e a t u r ea d a p t i v e w e i g h t p h o t oc l u s t e r i n ga l g o r i t h m , w h i c ha u t o m a t i c a l l ya s s i g n se a c hf e a t u r eap r o p e rw e i g h t v a l u et o c o m p u t ep h o t os i m i l a r i t ym a t r i x ，t h e n u s e sg r a p hp a r t i t i o nm e t h o dt o i i 中山大学硕士论文 基于多特征的相片聚类算法研究与实现 r e c u r s i v e l yd i v i d ep h o t oc o l l e c t i o n si n t os m a l lc l u s t e r st h a tc a l ls a t i s f yt h e r e q u i r e m e m so fp h o t ob o o k t h em a i nc o n t r i b u t i o n so f t h i sp a p e r sa l ea sf o l l o w s ：1 ) d e s i g nau n i v e r s a lp h o t o c l u s t e r i n gf r a m e w o r k ，w h i c hc a nh e l pu s e r st oo p e r a t et h ep h o t oc o l l e c t i o n se a s i l y ；2 ) b e s i d e st i m ea n dc o n t e n ti n f o r m a t i o n , t h i sp a p e ra d d so p t i c a li n f o r m a t i o nt oc l u s t e r p h o t o s a n d i m p r o v ec l u s t e r i n g r e s u l t ；3 lp r o p o s ean o v e lm u l t i - f e a t u r e a d a p t i v e w e i g h tp h o t oc l u s t e r i n ga l g o r i t h m , w h i c hc a nd e a lw i t ht h er e q u i r e m e n t o fp h o t ob o o ke f f e c t i v e l y k e yw o r d s ：p h o t oc l u s t e r i n ga l g o r i t h m ，p h o t oc l u s t e r i n gf r a m e w o r k , m u l t i f e a t u r e a d a p t i v e w e i g h t ，g r a p hp a r t i t i o n i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：即志各 日期：翌2 釜皇目塑旦 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名： 氍囊 日期：加口? 年，月冯日 中山大学硕士论文基于多特征的相片聚类算法研究与实现 第1 章引言 近年来，伴随电脑技术的普及以及数码相机逐渐融入人们的生活中，人们趋 于收集大量的数码相片。同时互联网上不断兴起很多的相片共享社区和在线打印 相册等应用服务，这些网站都收集了大规模数量的数码相片。无论是面对个人收 集的数码相片还是面对网站收集的数码相片，人们都需要有一种有效的方法来组 织和管理这些相片。 相片聚类技术是解决相片管理问题的主要方法之一。通过使用聚类技术可以 把视觉上相似或主题意义上相同的相片聚集在一起，这样可以便利用户对相片的 操作，以达到用户浏览、批注、检索和分享相片的目的。因此，无论是从市场需 求，还是从研究理论的角度出发，对有效的相片聚类算法进行研究和实现都是具 有极高的社会意义和应用价值的。 i i 研究背景 随着数码技术的飞快发展，数码相机的价格不断降低，人们在日常生活中开 始广泛使用这些摄影设备。由于使用相机拍照很简单易用，又不用考虑相片拍照 的成本，故人们收集了大量的个人数码相片。在传统上，人们在个人电脑中使用 文件夹以树状结构的方式来存储和管理他们的相片集，这种树状结构的组织管理 方式比较低级，只能静态地表达相片之间的关系，对人们进行浏览相片和搜索相 片都极为不便，需要在不同文件夹之间频繁切换操作才能完成任务。因此用树状 文件夹系统不能有效地帮助人们组织和管理数码相片。为了解决这个问题，现有 研究开发了很多相片管理工具，例如e a s y a l b u m 1 、a u t o a l b u m 2 、p h o t o t o c 3 、 f a m i l ya l b u m s 5 和f a m i l yp h o t oa l b u m 7 等。这些相片管理工具通过利用相片 的元数据和内容信息来对相片集进行聚类，从而达到帮助人们组织和管理相片的 目的。 在互联网的作用下，人们有可能想通过网络向他们的朋友或家人分享所拍摄 中山大学硕士论文基于多特征的相片聚类算法研究与实现 相片中含有的事件、经历和回忆，或者想借助网络可以享受在线打印相片等各种 跟相片相关的服务。正是在这些需求的推动下，互联网上不断兴起很多的相片共 享社区和相片应用服务等，例如全球最大的相片共享社区f l i c k r ，其收集的数 码相片数量已经超过2 0 亿张；类似的网站还有p h o t o b u c k e t 、f o t o l o g 、y o f u s 、 w e b s h o t s 和p i c a s a 等，这些网站都利用在线相册功能来收集了大规模数量的数 码相片，因此也需要借助相片聚类技术来组织和管理相片。 此外，借助于在线相册功能，许多服务提供商允许用户把在线相册( a l b u m ) 打印成一本纸质画册( p h o t ob o o k ) 来珍藏。与电子相册不同的是，画册是需要 用户花钱去打e l j 的。因此用户对厕册在页面美观和排版布局方面有很高要求，想 尽可能地把相似或相同意义的相片放在同一个页面，这样不仅可以使得画册整齐 美观，还可以方便浏览查看。众所周知，手工去挑选和组织这些相片来制作一本 画册是一项费时和烦人的任务，需要花费用户很多的精力和时间，因此很希望能 有一种有效的相片聚类算法来帮助用户完成这个任务。 因此，无论是相片管理工具还是相片应用网站，都需要有效的相片聚类算法 来支持，使得可以帮助用户更好地组织和管理这些相片集。 1 2 相片聚类技术主要作用及难点 1 2 1 相片聚类技术主要作用 相片聚类技术是一种有效组织和管理数码相片的技术，其主要作用有： 1 ) 浏览( b r o w s i n g ) 利用聚类技术可以把在视觉上相似或主题意义上相同的相片聚集在一起，这 样以聚类结果的形式来展示相片，更能方便用户浏览和查阅【3 】。例如，根据相 片的拍摄时间信息可以把相片集分割成一系列事件，使得用户通过以事件的形式 来浏览相片等。 h t t p j w w w f l i c k r c o m h t t p j p h o t o b u c k e t c o r n h r p y w w w f o t o l o g c o m h t t p ：w w w y o f u s c o r n h t t p j w w w w c b s h o t s c o m h t t p p i c a s a g o o g l e c o r n 2 中山大学硕士论文基于多特征的相片聚类算法研究与实现 2 ) 检索( r e t r i e v a l ) 利用聚类技术对相片集进行处理得到一系列聚类结果，则可以对这些聚类结 果进行检索 1 2 1 。例如，根据给定相片可以找出它所在的事件聚类，则将该事件 聚类作为检索结果返回。 3 ) 评注( a n n o t a t i o n ) 由于很难直接获取相片的语义信息，用户一般都是通过添加评注的方式来描 述相片的语义。通过利用相片聚类技术对相片集进行聚类，用户则可以直接对聚 类结果进行批量添加评注 1 0 ，1 1 ，这样避免了手工频繁地对单张相片进行添加批 注，不仅大大地减少了工作量，还节省了用户的时间和精力。 4 ) 共享( s h a r i n g ) 利用聚类技术把有相同意义的相片聚集在一起后，用户可以通过网络或其他 存储设备把这些聚类结果来分享给亲人朋友，以达到相片共享的目的。 1 2 2 相片聚类技术难点 由于相片的特殊性，相片聚类技术在对相片集进行处理时存在以下难点： 1 ) 缺少上下文信息 跟视频不一样，由于相片是在离散时间内所拍摄的，相片往往在局部时间内 才可能相似，也就是说，相邻相片之间可以挖掘的关联信息没有视频那么丰富。 并且在拍摄过程中用户总想挑选适合的角度来拍摄相片，可能会造成相机镜头的 角度和缩放频繁地变化，从不同角度对同一个物体拍摄的相片其内容信息也不太 相同，这样给计算相片之间的相似度带来了很大难度。 2 ) 数据集多样化 由于相片与用户行为有密切关系，不同的用户可能会有不同的拍照习惯，即 不同用户所收集的相片集数据分布可能是不一样的。这些多样化的相片集将给聚 类技术带来了很大的挑战，因此很需要一种有效的自适应相片聚类算法。 。h t t p - j w w w i m a g e e v e n t c o a l 3 中山大学硕士论文基于多特征的相片聚类算法研究与实现 1 3 本文的主要工作和贡献 1 3 1 本文的主要工作 本文主要研究内容包括以下几个方面： ( 1 ) 相片聚类算法综述。对现有相片聚类算法进行调查研究，根据它们针对 不同特征来对相片进行聚类的特点，将现有相片聚类算法划分基于e x i f 元数据 和基于内容信息两种类型，并分别对每种类型的相片聚类算法进行总结和归纳， 最后讨论和分析了现有相片聚类算法的不足之处。 ( 2 ) 相片聚类框架设计实现。考虑到现有研究已经提出很多相片聚类算法， 而这些相片聚类算法往往只针对单个特征对相片集进行聚类，这样不能满足用户 多样化的需求。为了解决这个问题，本文设计和实现了一个通用的相片聚类框架， 该框架可以将现有流行的相片聚类算法集成进来，并根据用户具体需求联合调用 多个相片聚类算法来执行，以达到满足用户多样化需求的目的。由于该相片聚类 框架是以中间件的形式存在的，相片管理系统开发人员可以很方便地将其集成到 现有相片管理系统中，使得相片管理系统也拥有相片聚类功能。相片聚类算法研 究人员也可以利用该框架来快捷地设计和实现新的相片聚类算法。因此，本文提 出的相片聚类框架对相片聚类研究领域具有非常重要的意义。 ( 3 ) 相片聚类算法研究与开发。在查阅大量论文、专著及专利的基础上，考 虑到现有相片聚类算法不能满足画册制作所需要小粒度相片聚类的要求，本文提 出了一种基于多特征自适应权重的相片聚类算法，该算法联合使用时间、内容和 亮度三个特征来对相片进行聚类，通过自适应地给各个特征分配适当的权重来计 算出相片之间的相似度，接着根据相似度矩阵使用自适应递归图划分的方法将相 片集划分成小粒度聚类，以达到满足画册制作的要求。 1 3 2 本文的主要贡献 本文的主要贡献如下所述： 。h t t p ：w w w e x i f o r g 4 中山大学硕士论文基于多特征的相片聚类算法研究与实现 ( 1 ) 综述相片聚类算法。通过对现有相片聚类算法进行调研后，根据它们针 对不同特征来对相片进行聚类的特点，将现有相片聚类算法划分基于e x i f 元数 据和基于内容信息两种类型，并分别对每种类型的相片聚类算法进行总结和归 纳，最后讨论和分析了现有相片聚类算法的不足之处。通过本文对相片聚类算法 的综述，可以帮助研究人员加深对相片聚类研究领域的了解。 ( 2 ) 设计和实现一个通用的相片聚类框架。考虑到现有研究已经提出很多相 片聚类算法，且这些相片聚类算法往往只能满足用户单方面需求的情况，本文提 出一个通用的相片聚类框架，它可以将现有流行的相片聚类算法集成进来，通过 联合调用执行多个相片聚类算法来满足用户多样化的需求。该框架是以中间件的 形式存在的，对相片管理系统开发和相片聚类算法研究都具有重大意义。 ( 3 ) 设计和实现一种基于多特征自适应权重的相片聚类算法。考虑到现有的 相片聚类算法不能满足制作画册的要求，本文在相片聚类框架的基础上设计和实 现了一种基于多特征自适应权重的相片聚类算法，该算法通过自适应地给多个特 征分配适当的权重来计算出相片之间的相似度，接着根据相似度矩阵使用自适应 递归图划分的方法来将相片集划分成小粒度聚类，使得满足制作画册的需要。由 于该相片聚类算法是采用白适应的策略来对相片集进行聚类，不需要设置闽值， 因此可以灵活地处理多样化的相片集。 ( 4 ) 联合多特征来聚类。现有的相片聚类研究一般都是使用时间特征和内容 特征来对相片进行聚类，而本文在结合时间特征和内容特征的基础上，又引进亮 度特征来提高相片聚类的效果，这样同时使用多个特征来进行聚类的做法也是本 文的独创之处。 1 4 本文的组织结构 本文共分为六章。 第一章为引言部分，主要介绍了相片聚类技术的研究背景和作用，并简述 本文的主要研究内容、主要贡献和组织结构。 第二章先从e x i f 元数据、事件概念及形式化表示、聚类算法与原理等三 个方面来介绍相片聚类预备知识，接着分别对现有基于e x i f 元数据和基于内容 5 中山大学硕士论文基于多特征的相片聚类算法研究与实现 信息的相片聚类算法进行总结和综述，最后讨论和分析了现有相片聚类算法存在 的不足，以及考虑如何使相片聚类技术满足制作画册的需求。 第三章针对当前相片聚类技术不能满足用户多样化需求的问题，提出了一 种通用的相片聚类框架，并对该框架使用的相片模型、框架结构设计以及各模块 设计都进行了详细的描述，最后阐述了该相片聚类框架的关键技术。 第四章提出一种基于多特征自适应权重的相片聚类方算法来解决制作画册 的问题，详细描述了该算法流程的事件划分和场景聚类两个阶段后，着重讨论了 场景聚类中的多特征自适应权重选择策略和自适应递归图划分方法等。 第五章使用真实用户数据集来测试上述算法，比较不同多特征组合的聚类 效果，并对实验结果进行了讨论和分析。 第六章对整个论文的内容进行总结和展望，指出了设计中存在的问题，并 提出了进一步工作的想法。 6 中山大学硕士论文基于多特征的相片聚类算法研究与实现 第2 章相关研究工作 本章主要介绍现有的相片聚类算法，由于这些聚类算法都是针对相片的不同 特征提出来的，因此本文根据基于的不同特征来对这些聚类算法进行分类和总 结，这样可以从特征的角度更清晰地了解这些相片聚类算法。 一般来说，传统相片聚类算法用到的主要相片特征可以分为两种类型： e x l l 如( e x c h a n g e a b l ei m a g ef i l ef o r m a t ) 元数据和内容信息。其中，e x i f 元数 据是相机在拍摄相片时候自动记录在相片文件里而的，它主要包含了相片拍摄时 间、相片分辨率、相机型号等，还有些光学信息，例如是否闪光、光圈系数、 曝光时间和焦距等。更高级的相机还包含有g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 信息，但是这种相机还没有被普遍使用，现实中大多数相片都没有含有g p s 信 息。在e x i f 信息中相片拍照时间对相片聚类来说是最有用的，根据拍照时间可 以把相片集划分成一系列事件的形式，这里提到的事件这个概念是没有统一定义 的，往往是跟某段时间或某个地点相关的，例如生日晚会、婚礼等等。光学信息 也提供了拍摄相片时非常有用的上下文信息，例如亮度的大幅度变化也意味着场 景的转移，利用光学信息还可以分类出户外和户内的相片。而内容信息也可以分 成两类：低层次内容信息和高层次内容信息。其中低层次内容信息主要包括颜色 ( c o l o r ) 、纹理( t e x t u r e ) 和形状( s h a p e ) 等，这些低层次内容信息从不同方 面来反映出相片的不同视觉特性，通过这些低层次内容信息可以把在视觉上相 似的相片聚集在一起。在现有的相片聚类算法中，颜色直方图是最为常用的特征， 纹理其次，形状特征则很少被使用。而高层次内容信息指的是跟相片语义相关的， 里面研究涉及的技术比较复杂。因此对相片集进行聚类所用到的内容信息主要是 低层次内容信息。 在下面章节中先简单地介绍相片聚类预备知识，再对基于不同特征的相片聚 类算法进行分类综述。 ：h t t p j w w w e x i f i o r g 。h t t p j w w w g p s g o v c h i n e s e h t m l 7 中山大学硕士论文基于多特征的相片聚类算法研究与实现 2 1 相片聚类预备知识 在开始综述相片聚类算法之前，先简单地介绍一下相片聚类预备知识。跟普 通w e b 图像不同，相片跟人的行为是密切相关的，且相片本身也拥有w e b 图像 所没有的e x i f 元数据，所以相片聚类跟w e b 图像聚类的关注点不太一样。一般 来说，w e b 图像聚类只关注于图像内容方面，而相片聚类则不同，除了关注相片 内容相似性外，还考虑时间和其它上下文信息。由于相片在内容特征提取方法跟 w e b 图像类似，且现有基于内容的图像检索技术比较成熟，所以在这里就不再阐 述相片内容特征方面。本节主要从三个方面来介绍相片聚类预备知识，分别是相 片e x i f 元数据、相片聚类事件概念和聚类算法与原理，关于它们的具体描述见 下面章节。 2 1 1e x i f 元数据 本节主要介绍相片中包含的e x i f 元数据，该元数据是相片聚类研究中不同 缺少的信息。这里e x i f ( e x c h a n g e a b l ei m a g ef i l ef o r m a t ) 是可交换图像文件的 缩写，是专门为数码相机的照片设定的，可以记录数字照片的属性信息和拍摄数 据。它最初由日本电子工业发展协会在1 9 9 6 年制定，后来增加了对音频文件的 支持。e x i f 可以附加于j p e g 、t i f f 、r i f f 等文件之中，为其增加有关数码相 机拍摄信息的内容和索引图或图像处理软件的版本信息。 一般说来，在e x i f 标准中定义的元数据标签包括以下几大方面的信息： 1 ) 日期和时间信息( d a t et i m eo r i g i n a l ) 。数码相机将记录当前日期和时间， 并把这些信息记录在元数据标签里。 2 ) 相机设置。这包括静态信息，如相机型号( m o d e l ) 、生产厂商( m a k e r ) ； 还有一些光学信息，例如光圈系数( f n u m b e r ) 、曝光时间( e x p o s u r et i m e ) 、焦 距( f o c a ll e n g t h ) 、i s o 感光速度( i s os p e e dr a t i n g s ) 等。 3 ) 相片拍摄地的空间信息。可以由全球卫星定位系统g p s 接收器连接到数 码相机上，来提供相关全球定位信息。不过仅有极少数数码相机支持这个特性， 现实中大部分相片所包含的e x i f 元数据都没有这个信息。 8 中山大学碗士论文基于多特征的相片聚樊算涪研究与赛现 相片的e x l f 信息如下面图2 1 所示，可以使用鼠标右键点击相片属性，进 入摘要选项面板，点击高级按钮就可以看到该相片的部分e x i f 信息。 图2 - 1 相片e x i f 元数据示意图 总的来说，在* h 相片相关的应用研究中，e x i f 元数据足很重要的一部分信 息，现有的很多相片管理工具都支持该e x i f 元数据。 2 1 2 事件概念及形式化表示 继上一节介绍e x i f 元数据后，本节主要介绍事件概念及其形式化表示。前 面已经提到时州足相片聚类中最有用的信息。因为时间信息有两个很重要的特 点：( 1 ) 时间可以帮助人们回忆，符合人们浏览相片的习惯【1 5 。根据相片拍照 时间的先后顺序来浏览或查看相片，可以让人们在时间层次上更清晰地看清楚柏 片所带来的历史主题意义。( 2 ) 时f f 【| 可以反映出相片之间的关联关系，在相近时 问段内拍摄的相片往往都会有相同或相近的主题意义，即可以把这些连续时间片 段内拍摄的相片看成一个事件，因此可以根据时问信息来将相片集划分成一系列 事件。因此时间是组织和管理相片的不可缺少的因素之一。 对于上面所提到的事件这个概念是没有统一定义的，它往往是跟某段时间或 某个地点相关的例如生日晚会、婚礼等等。也就是说，一个事件可以理解成人 们的某次活动记录，它一般都是集中在某个时间段和某个地方发生的。为了更好 地理解事件这个概念，下面从事件层次和事件形式化表示两方面来描述： 1 ) 事件层次 中山大学硕士论文 基于多特征的相片聚类算法研究与实现 由于研究的关注点不同，现有相片聚类研究对事件层次主要有两种理解；一 种认为事件是平坦结构的，而另外一种认为事件是层次结构的。它们的分歧在于 对事件粒度大小的认识不同，前者认为在时间轴上可以把相片流分割成一系列事 件，且各事件之间是独立的。后者觉得事件之间是有层次结构的，一个事件中还 包含一系列子事件，这里层次结构事件如下图2 2 所示： 子事件 图2 - 2 层次结构事件示意图 从层次结构事件图2 2 中可以看出，公园春游这个事件中包含着爬山和划船 等多个子事件，即事件是不断嵌套在一起的，也就是说事件的粒度可以很小，这 种层次结构比较符合人们的浏览习惯。 2 ) 事件形式化表示 为了更直观地表示事件这个概念，这里以平坦结构的事件形式来描述基于时 间的相片聚类算法原理。对于给定按照拍摄时间先后顺序排列好的相片集，可以 把按时间排列好的相片集称为相片流，此时可以形象地将相片聚类问题看作是相 片流的事件分割问题，而对相片流的事件分割又可以形式化成对事件边界的侦 测，具体原理如下【1 6 】： 假设现在总共有n + l 张相片按照拍照时间先后顺序排好，分别表示如下： p = a ，p 2 ，以+ 1 ) 对应地，上述这+ l 张相片的拍摄时间分别是： t = ，t 2 ，k 1 ) ，其中 _ 4 3 2 0 1 ) 计算所有相邻相片的函数值后，以直方图的形式来统计函数值f ( x ) 的分别 情况，接着使用2 - m e a n 聚类方法把统计直方图划分成两个聚类，将时间差较大 的那个聚类看作是事件的边界。 4 ) 基于棋盘核函数的方法 c o o p e r 1 9 借鉴视频场景边界侦测的思想，提出一种使用棋盘核函数结合相 似度矩阵来计算事件边界分数，通过计算多尺度的事件划分置信分数，从而找出 对相片流最好的事件划分。该基于棋盘核函数的算法流程如下： 算法：基于棋盘核函数的算法 输入：相片集p = p l ，p 2 ，p u + ，其拍照时间为t = 输出：一系歹0 聚类 步骤： 1 首先计算所有相片的时间相似度矩阵s r ( f ，歹) ，计算公式如下： 踯一p ( - 掣) ( 2 - 3 ) 2 利用棋盘核函数g ( 1 ，聊) 来对相似度矩阵s x ( f ，j ) 进行计算事件边界分 数吆( f ) ，计算公式如下： f 吆( d = s x ( i + l ，i + m ) g ( 1 ，m ) ( 2 4 ) ，口，= 一t 3 根据步骤2 中事件边界分数可以检测出事件边界，则通过下面聚类评 价函数c ( 吸) 来评价当前事件划分的置信分数，计算公式如下： c ( 吼) = l 茗1 “引s x ( 一i , q y ) 芦一l b 荟x l - 2 吾b 1 + l ，h 善i + 2 ，瓦_ 币s k ( 瓦i , j 而) ( 2 5 ) 4 对三个不同尺度的k 值，分别执行前面三个步骤，计算得到三个置 1 5 中山大学硕士论文基于多特征的相片聚类算法研究与实现 这里说明一下，关于该算法2 1 所提到公式的具体含义可参考原文献【1 9 】。 5 ) m e a ns h i f t 方法 l i a n g l i a n g 【2 0 】引进了图像分割中经典的m e a ns h i f t 算法对相片集进行事件 划分，该方法的好处在于避免了传统聚类方法对阈值设置的敏感问题，它可以根 据默认的带宽参数来自动计算出聚类数目，该方法对空间信息也兼容。 该m e a ns h i f t 聚类流程描述如下： l 算法：m e a ns h i f t 聚类算法l i 输入：相片集，每张相片均有时问信息，仅有部分相片有g p s 信息i f 输出：一系列聚类l ll i 步骤：l i i 1 使用m e a ns h i f t 算法对所有相片进行时问聚类，得到基本聚类集合c 。l fi | 2 使用m e a ns h i f t 算法对同时含有时问和g p s 信息的部分相片集进行l i 聚类，得到目标聚类集合c 。l l 3 检查是否存在新的聚类gr 属于c ，使得q ，r nc ，：f 2 j ，则把g 7 作为f ii i 一个新聚类加入到c 中。l i4 重复以下步骤直到c 包含所有的相片：i ii l4 1 选择一个样本薯属于c 7n x , 不属于c ，同时选择另外一个样本xl ll l 属于c ，满足矗= a r g m i n d i s t ( x , ，x ) ，这里d i s t ( x t ，x ) 表示计算样本誓和样本x 之i il i 间的时间欧几里德距离。i il 4 2 增加薯到c ，把它放置在跟同一个聚类中。l ll l 5 将c 作为最终的相片聚类结果返回。 l l 算法2 - 2 l 6 ) 基于概率模型的方法 t a om e i 2 1 提出一种基于混合概率的事件划分方法，该方法提出的事件概念 跟通常理解的事件有所不同，它试图将相片集划分成集体活动事件和非集体活动 事件，因此允许不同事件在时间上是有重叠的。 1 6 中山大学硕士论文基于多特征的相片聚类算法研究与实现 该方法融合了多种特征对相片集进行聚类，包括时间、颜色、纹理、光圈、 焦距、曝光时间和人脸数量等，并假设时间、颜色和纹理服从高斯分布，而纹理、 光圈、焦距、曝光时间和人脸数量服从多项式分布，最后使用期望最大化算法求 得聚类结果。 2 2 1 2 基于亮度 现有不少研究使用光学信息来对相片进行场景分类【4 ，2 2 ，即根据亮度等信 息来区分户外与户内的相片。一般来说，在同一场景所拍摄的相片集其亮度值大 体一致，在不同场景所拍摄的相片集其亮度值就可能会有些变化，而户内相片的 亮度值将比户外相片的亮度值低一些。正是基于这点考虑，文献【1 6 】提出了一种 基于亮度的层次聚类算法，该方法首次引入光学信息来对相片进行聚类，认为亮 度的变化也意味着事件的转移。由于使用内容信息来聚类需要很大的计算丌销， 该方法的目的是想尝试用光学信息来代替内容信息对相片进行聚类。该方法所使 用的亮度计算公式 2 3 鱼1 1 下所示： 4 + 瓦= 鼠+ 鼠 ( 2 - 6 ) 这里a ，= l o g ：( ) 、l = 一l 0 9 2 ( e ) 和& = l o g ：( t 3 1 2 5 ) ，其中e 表示光圈 系数，巨表示曝光时间，t 表示i s o 速率。可以通过计算前面三项求得亮度值， 即鼠= 瓯一4 一瓦。该文献考虑到事件的粒度大小难以定义，故使用层次结构算 法来聚类，具体算法流程如下： 1 7 中山大学硕士论文基于多特征的相片聚类算法研究与实现 2 2 1 3 基于空间 空闻信息也是组织和管理相片的重要因素。由于技术和市场等各方面原因， 现在带有g p s 功能的相机还很少，也就是说现有大部分相片还没有包含空扛 j 信 息，相信不久当带有g p s 功能的相机丌始被人们普遍使用时，基于空间信息的 相片聚类技术将会成为一个研究热点。目前也有不少研究尝试使用空问信息来对 相片进行聚类，不过它们的研究都是在假设所有相片均含有空问信息的基础上展 开的。 n a a m a n 2 4 提出一个名为p h o t o c a m p a s 的系统，该系统可以利用相片的空问 信息来自动组织个人相片集，它先将空问信息进行层次聚类，再按照对应的地理 名称来给每个聚类命名，以便用户可以根据地理名称来浏览相片集。 类似地，p i g e a u 2 5 也利用时间和空间信息来对相片集进行层次结构划分。 2 2 2 基于内容的相片聚类算法 前面也已经提到，相片内容信息可以分成两类：低层次内容信息和高层次内 容信息。这里低层次内容信息指颜色、纹理和形状等，它跟象素点有直接关系的； 而高层次内容信息指语义相关的，涉及到图像对象识别等。跟基于内容的图像检 索的研究重点不同，相片聚类研究中内容信息往往起辅助作用。一般来说，在相 邻时间内所拍摄的相片才会出现内容相似，即内容极相似的两张相片其时问相似 度也很高。下面分别对这两个层次内容信息的相片聚类算法进行总结和综述。 2 2 2 1 基于低层次内容 在低层次内容方面，可以根据需求考虑使用局部信息或全局信息来计算相片 之间的相似度进行聚类。现有大多数基于低层次内容的相片聚类算法都是基于阈 值来实现的，使用阈值来控制聚类的结果。 1 ) 基于颜色直方图 a u t o a l b u m 2 使用固定阈值对相片集进行事件划分后，如果得到某事件所包 含相片数量大于给定数量4 8 时，则对该事件继续进行基于内容聚类，使得最终 所有相片聚类含有相片的平均数量是8 。该方法选择颜色直方图作为内容特征， 并假设相片产生符合隐马可夫模型，故执行基于内容聚类时只考虑对相邻相片聚 1 8 中山大学硕士论文基于多特征的相片聚类算法研究与实现 类进行最佳优先合并，具体过程如下图2 5 所示： 口 3 5 口 5 2 口 4 2 口口 6 张相片，6 个聚类 7 9 6 3将最近相令5 聚类合并 口口 6 张相片，5 个聚类 7 96 3将最近相邻聚类合并 口口 6 张相片，4 个聚类 图2 - 5 最佳优先合并示意图1 2 1 在图2 - 5 中相邻聚类之间的数字越小则表示此两个聚类越相似，将优先考虑 将它们合并。类似地，p h o t o t o c 3 对相片集进行事件划分后，如果得到的聚类 粒度太大( 超过2 3 张) ，则考虑使用内容聚类来分裂这些大聚类得到相应的小聚 类，其中小聚类的数量是大聚类中含有相片数量的1 1 2 ( 四舍五入取整) 。 2 ) 基于兴趣区域块 文献【2 6 】提出一种基于兴趣区域块的相片聚类方法，它首先检测出相片中的 人脸，根据人脸位置可以将相片划分成三个兴趣区域块，并将这些兴趣区域块作 为内容特征，最后把时间和内容的相似度乘积作为总相似度对相片集进行聚类， 不过该聚类算法是基于阈值的，即如果两张相片之间的总相似度大于设定阈值， 则将它们合并在一个聚类，反之则放置在不同聚类中。 3 ) 基于方格划分 j a n g 【2