（计算机软件与理论专业论文）动态图片拼接.pdf

浙江大学硕士学位论文 摘要 摘要 如何高效而且令人愉快的浏览大量图片一直是计算机视觉和多媒体邻域中 的一个重大挑战。现有的浏览大规模图片集的技术按照它们对图片的排列方式可 以分为两类：空间排列方法和时间排列方法。空间排列方法利用屏幕空间来生成 图片集的一个二维表示形式。传统的马赛克方法将所有图片在一个简单的网格上 以不重叠的的方式排列好，它的后续工作采用更好的算法来决定图片布局和排列 方式，但是它们都不允许图片之间有重叠。最近出现的图片拼接技术允许图片不 重要的区域可以被其他图片覆盖，因而提高了屏幕的利用率。时间排列方法大部 分采用顺序播放的方式，一次显示一幅图片。最近出现的新算法可以实现无重叠 图片马赛克的顺序播放，它同时考虑了图片在时间和空间上的排列方式，但是丧 失了浏览过程中的连续性。 本文提出的动态图片拼接算法是一种将时间和空间排列方式相结合的高效 大规模图片集浏览技术，在图片浏览过程中同时实现了空间排列上的紧凑性和时 间上的连续性。不同于之前的仅关注如何生成一个图片集的二维排列方式的静态 空间排列方法( t h u m b n a i l s ，图片拼接) ，动态图片拼接技术明确考虑了时间迁 移的因素，从大规模图片集中动态的产生随时间变化的图片拼接结果。为了达到 图片浏览的连续性，动态图片拼接在更新图片拼接结果时，并不像之前的时间排 列方法那样替换屏幕中的所有图片，而只是更新少数图片。它采用一种高效渐增 式的基于局部调整的算法来更新图片布局( 所有图片的中心位置，倾角，层次数) ， 使得屏幕展现的图片可视信息量总和达到最大，因而有效的实现了图片浏览的连 续性。较之前的图片浏览算法，动态图片拼接在保持高效的前提下显著提高了浏 览图片的数量，丰富了用户的视觉感受，最大限度的利用了屏幕空间和用户时间， 达到了理想的图片浏览效果。 关键词：动态图片拼接，可视信息量，时间迁移 浙江大学硕士学位论文 a b s t r a c t a b s tr a c t b r o w s i n gl a r g ep h o t oc o l l e c t i o ni n a ne f f i c i e n ta n dp l e a s i n gw a yi sag r e a t c h a l l e n g e e x i s t i n gt e c h n i q u ef o rb r o w s i n gl a r g ep h o t oc o l l e c t i o n sc a nb ec l a s s i f i e d i n t ot w od i f f e r e n ta p p r o a c h e so nt h ea r r a n g e m e n to fi m a g e s ：s p a t i a la r r a n g e m e n t m e t h o d sa n dt e m p o r a la r r a n g e m e n tm e t h o d s s p a t i a la r r a n g e m e n tm e t h o d sa i mt o c r e a t eas i n g l e2 dr e p r e s e n t a t i o nf o rap h o t oc o l l e c t i o nu t i l i z i n gt h es c r e e ns p a c e t r a d i t i o n a lm o s a i cm e t h o dl i n e su pp h o t o si nas i m p l eg r i di nan o n - o v e r l a p p i n g m a n n e r , l a t e rw o r k su 8 cb e t t e ra l g o r i t h mt od e t e r m i n eag o o dl a y o u ta n dp l a c e m e n to f i m a g e s ，b u ta l lt h e s ew o r k sd o n ta l l o wp h o t oo v e r l a p p i n g r e c e n tt e c h n i q u en a m e d c o l l a g ea l l o w su n i m p o r t a n ta r e ao fap h o t ot ob ec o v e r e db yo t h e rp h o t o s ，8 0i t i m p r o v e st h eu t i l i z a t i o no fs c r e e ns p a c e t e m p o r a la r r a n g e m e n tm e t h o d sm o s t l y d i s p l a yp h o t oc o l l e c t i o ni nas e q u e n t i a lm a n n e rw i t ho n ei m a g ed i s p l a y e da tat i m e s o m en e wt e c h n i q u ea l l o wi m a g em o s a i c st ob es e q u e n t i a l l yd i s p l a y e d ，i tc o n s i d e r a r r a n g e m e n ta n dt e m p o r a la r r a n g e m e n ts i m u l t a n e o u s l y b u tl o s et h e t e m p o r a l c o n t i n u i t yo ft h ep r e s e n t a t i o n d y n a m i cc o l l a g ep r o p o s e di nt h i sp a p e ri sa ne f f i c i e n tt e c h n i q u ef o rb r o w s i n g l a r g ep h o t oc o l l e c t i o nt h a tc o m b i n e ss p a t i a la r r a n g e m e n tm e t h o da n dt e m p o r a l a r r a n g e m e n tm e t h o d ，a c h i e v i n gs p a t i a lc o m p a c t n e s s a n d t e m p o r a lc o n t i n u i t y s i m u l t a n e o u s l y u n l i k ep r e v i o u st e c h n i q u e s t h a tf o c u so n g e n e r a t i n g as t a t i c t w o d i m e n s i o n a la r r a n g e m e n to fp h o t o s ( s u c ha st h u m b n a i l sa n dc o l l a g e ) ，d y n a m i c c o l l a g ee x p l i c i t l yc o n s i d e r st e m p o r a lt r a n s i t i o na n dd y n a m i c a l l yc r e a t eat i m e v a r y i n g c o l l a g ef r o mt h el a r g ep h o t oc o l l e c t i o n i no r d e rt or e t a i nt h et e m p o r a lc o n t i n u i t y , d y n a m i cc o l l a g eo n l yu p d a t e sal i t t l ef e wp h o t o si n s t e a do fu p d a t i n ga l lp h o t o si nt h e s c r e e nl i k ew h a tp r e v i o u st e m p o r a l a r r a n g e m e n tm e t h o d sd o ，u s i n ga ne f f i c i e n t i n c r e m e n t a lo p t i m i z a t i o na l g o r i t h mb a s e do nl o c a l l ya d j u s t m e n tt o u p d a t et h e p l a c e m e n to fa l lp h o t o s ( t h ec e n t e rp o s i t i o n ，t h ea n g l e ，a n dt h el a y e ro fa l lp h o t o s ) a i m i n gt om a x i m i z et h ev i s u a li n f o r m a t i o ns ot h a tt e m p o r a lc o n t i n u i t yo ft h eb r o w s i n g p r o c e s si sp r e s e r v e d c o m p a r e dt op r e v i o u sa l g o r i t h m sf o rb r o w s i n gp h o t oc o l l e c t i o n ， d y n a m i cc o l l a g ed r a m a t i c a l l yi n c r e a s e st h es i z eo ft h ep h o t oc o l l e c t i o n st ob eb r o w s e d , e n r i c h e su s e r s v i s u a le x p e r i e n c e ，b e s tu t i l i z e st h es c r e e ns p a c ea n du s e rt i m e ，a n d a c h i e v e san i c ee x p e r i e n c ef o rb r o w s i n gp h o t oc o l l e c t i o n k e y w o r d s ：d y n a m i cc o l l a g e ，v i s u a li n f o r m a t i o n ，t e m p o r a lt r a n s i t i o n i ! i 浙江大学硕士学位论文图目录 图目录 图2 1 采用了双层表示的家庭照片集6 图2 2d i g i t a lt a p e s t r y 的结果。7 图2 3 滚动播放图片马赛克8 图3 1 动态图片拼接系统流程图1 2 图3 2 单一r o i 模型图片拼接结果1 4 图3 3 信息图模型动态图片拼接结果1 4 图4 1 贝叶斯网络示例2 1 图4 2 双马尔可夫随机场的图模型2 3 图4 3 贝叶斯置信度传递过程2 4 图4 4 包围盒信息图。2 9 图4 5 带有倾角的图片求交转化为包围盒信息图求交。2 9 图4 6 图模型的建立3 0 图4 7 贝叶斯传递算法消息传递伪代码一3 2 图4 8 画布初始状态3 5 图4 9 由初始状态建立图模型3 6 图4 1 0 移除旧图加入新图( 新图用加粗黑框表示) 3 6 图4 1 1 更新图模型3 7 图4 1 2 中心位置优化结果3 7 图4 1 3 采用基于权值的拓扑排序优化层次数伪代码4 0 图5 1 几种不同的图片浏览技术比较。4 3 图5 2 用户研究的实验结果总结。4 5 图5 3 动态图片拼接系统浏览截图( 个人图片集) 。4 7 图5 4 动态图片拼接系统浏览截图( 个人图片集) 。4 7 图5 5 动态图片拼接系统浏览截图( 个人图片集) 4 8 图5 6 动态图片拼接系统浏览截图( 个人图片集) 。4 8 图5 7 动态图片拼接系统浏览截图( 个人图片集) 。4 9 图5 8 动态图片拼接系统浏览截图( 个人图片集) 4 9 图5 9 动态图片拼接系统浏览截图( 中国油画) 5 0 图5 1 0 动态图片拼接系统浏览截图( 中国油画) 5 0 图5 1 1 动态图片拼接系统浏览截图( 中国油画) 5 1 图5 1 2 动态图片拼接系统浏览截图( 中国油画) 5 1 图5 1 3 动态图片拼接系统浏览截图( 中国油画) 5 2 图5 1 4 动态图片拼接系统浏览截图( 中国油画) 5 2 图5 1 5 动态图片拼接系统浏览截图( 蝴蝶) 5 3 图5 1 6 动态图片拼接系统浏览截图( 蝴蝶) 5 3 图5 1 7 动态图片拼接系统浏览截图( 蝴蝶) 5 4 h i 浙江大学硕士学位论文 图目录 图5 1 8 动态图片拼接系统浏览截图( 蝴蝶) 5 4 图5 1 9 动态图片拼接系统浏览截图( 蝴蝶) 5 5 图5 2 0 动态图片拼接系统浏览截图( 蝴蝶) 。5 5 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得澎鎏盘鲎或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签名： 签字日期： 年月日签字日期： 1， 月 审互 多甲阵 ，l|1， 骨夥加 浙江大学硕士学位论文第1 章绪论 1 1 研究背景 第1 章绪论 随着数码照相机和移动电话摄像头的可用性和普及率的提高，数码照片的数 量呈现了爆炸性的增长。现在，在个人电脑上保存成千上万张家庭，旅游照片已 经是十分普遍了；同时具有海量图库的互联网也成为图片的主要来源之一，用户 经常需要浏览从互联网上搜索到的大量图片。因此，设计一种在有限的时间内使 用户能够充分浏览大量图片的技术成为了当今的一个具有挑战性的工作。围绕着 这个问题主要有三个阶段的研究工作：图片管理( 包括标记和分类) ，图片获取 和可视化。我们的工作主要关注第三阶段，也就是大量图片的可视化问题。这直 接关系到用户对大量图片集的直观视觉感受，在很多场合中是最需要解决的问 题，例如浏览家庭照片集合，浏览图片搜索的结果以便于定位需要的图片，等等。 本文提到的图片浏览问题就是图片可视化问题。 设计合理的图片集可视化技术，也就是本文所说的浏览技术，必须注重两点， 即效率和表达的视觉愉悦性。面对成千上万的图片，图片集浏览技术必须在有限 的时间之内，充分利用屏幕空间，展现整个图片集合的全貌。而现有的工作并不 能够很好的处理图片浏览的时空协调问题，在浏览大规模图片集合时，或是关注 如何在有限空间内如何展示图片( 已有的图片拼接工作) ；或是关注时问，让用 户能够顺序浏览图片( 如s 1 i d e s h o w ) ，丧失了图片拼接的紧凑型，对屏幕空间的 高利用率和浏览的连续性。极少数的兼顾时间和空间的算法也存在着浏览连续性 的问题，它们把图片分类之后，按照不同的格局顺序播放图片拼接的结果，并且 在很大程度上不允许图片重叠，增大了有限屏幕空间上的信息冗余度。 综上所述，针对大量图片的浏览技术具有很强的实用性和广阔的应用前景， 并且是现今急需解决的一个问题。同时，大规模图片集的浏览技术必须做到高效 和保证用户的视觉愉悦性，如何合理的安排图片播放形式，协调时间和空间之间 浙江大学硕士学位论文第1 章绪论 的关系，这也是一个不小的挑战。就是在这个背景下，本文提出了一种动态图片 拼接算法，详细阐述了它的目标，运行机制和实验结果。经过实验和一定量的用 户体验测试，较之前的图片拼接和滚动播放( s l i d e s h o w ) ，动态图片拼接能更有 效地浏览图片集，在种高效的算法控制下兼顾了图片浏览时的时空协调，保证 了浏览的连续性。 1 2 研究目标和研究内容 我们研究工作的主要内容是设计一种浏览大规模图片集的技术，它必须高效 而且具备视觉愉悦性。本文在充分借鉴之前的图片拼接算法( p h o t oc o l l a g e ) 工作的基础上，提出了一种新的图片浏览算法，即动态图片拼接( d y n a m i c c o l l a g e ) 。下面，根据高效和视觉愉悦性，我们分别详细阐述相关的研究内容。 1 2 1 图片浏览高效性 本文提出的动态拼接算法的高效包含两个方面的含义：算法效率高，对画布 ( c a n v a s ，图片拼接的载体) 的利用率高。动态图片拼接允许图片之间的相对非 关键区域可以相互重叠，使得有限的画布上尽量只呈现关键区域信息，提高了画 布的利用率。之前的图片拼接工作将所有图片在画布上的排列方式，即它们的中 心位置，角度，层次( 1 a y e r ，决定图片之间遮挡的次序) ，做为一个全局优化问 题来求解，这样，如果把每一个图片的位置( 包含上述三个分量) 作为变量，那 么它的解空间可以是整个画布，这使得优化算法的计算量非常大。而动态图片拼 接把该问题视为一个局部优化问题，每个图片的中心位置的解空间只是初始位置 的一个邻域。于是这个局部优化问题的解空间大大减少了，这就是动态图片拼接 算法高效的关键。对于画布上的每一幅图片来说，优化之后的最终位置处于其初 始位置的某一邻域以内。我们的局部优化算法采用一种渐增( i n c r e m e n t a l ) 的 方式对画布上所有的图片的位置在局部区域内进行调整，在很大程度上保证了优 化前后画布上所有图片布局的连续性。事实上，这也是整个图片浏览过程的连续 性的一个重要保证。在后面章节我们会对算法进行详细阐述，解释这种局部调整 2 浙江大学硕士学位论文第1 章绪论 算法对于浏览图片集问题的合理性。 1 2 2 图片浏览的视觉愉悦性 这是图片浏览算法设计中最具有主观性并且挑战最大的一部分。不同的用户 有不同的需求，所谓众口难调，我们只能基于常识，满足最基本的需求。 由于画布的面积有限，我们无法将大量图片集中显示在画布上，必须考虑在 时间维上的图片分布，这样必然就有一个新旧图片替换的问题：新的图片进入两 布，旧的图片( 或者重要性不高的图片) 离开画布，使得画布空间的利用率维持 在一个合理的水平。 我们结合了人脑认知模型对此进行了具体分析。人脑具有暂时记忆功能，在 浏览图片数据时，先前所看到的在大脑中还能保持一定的印象。为了适应这种记 忆暂存现象，我们希望在更新图片数据时，原有图片的变动不要太大，尽量保持 浏览的过程的连续性。如上一节所述，我们的优化算法是一种局部调整算法，对 于画布内的每一幅图片来说，优化之后的最终位置处于初始位置的某个事先指定 的邻域之内，这样便有效的保证图片布局变动的连续性，而全局优化算法必然会 使画布内图片布局发生不连续的突变。由此可以看到，基于局部调整的动态图片 拼接算法符合人脑的记忆暂存现象，确保了图片浏览的视觉愉悦性。在后面的系 统模块分析中，我们将对图片调度模块进行细致的分析，从而可以达到更好的浏 览效果和更佳的视觉愉悦性。 1 3 本文组织结构 根据上述研究内容和研究目标，文章其余部分内容组织如下： 第二章： 本章介绍了已有的图片浏览技术，并且把现有的浏览技术按照空间排列方法 和时间排列方法进行了分类说明，介绍了它们的研究历史和各自的特点。同时指 出图片拼接算法在浏览大规模图片集时的不足，由此说明了设计新算法来浏览大 量图片的必要性。 3 浙江大学硕士学位论文第1 章绪论 第三章： 本章介绍了动态图片拼接系统的概貌，指出了系统运作的流程。对于系统流 程中的四个主要模块，即图片关键区域计算模块( s a l i e n c yc o m p u t a t i o n ) ，调度模 块( s c h e d u l e ) ，优化模块( o p t i m i z a t i o n ) ，绘制模块( r e n d e d n g ) 进行了有针对 性的详细说明，明确了各个模块的任务职责和工作过程。最后指出了优化模块是 动态图片拼接的核心模块。 第四章： 本章详细介绍了动态图片拼接系统的优化模块，集中阐述了动态图片拼接的 优化过程。本章提出了相应于特定问题背景的优化目标函数，利用分离优化方式， 分别对画布上所有图片的中心位置，倾角，层次数进行了优化。最后本章对整个 优化过程做了总结并且进行了效率分析。 第五章： 本章主要说明了动态图片拼接的实验结果，包括以用户体验的方式对包括动 态图片拼接技术在内的几种图片浏览技术做比较的结果，以及采用动态图片拼接 系统浏览了若干个图片集的效果。本章也根据用户反馈的结果总结了动态图片拼 接在浏览图片时的不足之处并且做出了分析。 第六章： 本章对全文内容进行了总括，回顾了本文的主要研究内容，归纳了本文的主 要贡献以及创新点，并指出进一步可以进行研究的内容，作为下个阶段研究的重 点。 1 4 本章小结 本章介绍了本文研究的主题，二种新的图片浏览方式一动态图片拼接，详细 说明了图片浏览技术产生的背景和现状，指出了现有图片浏览技术的不足之处， 由此引出了本文研究工作的必要性。接着，本章详细介绍了动态图片拼接算法的 研究目标和主要研究内容，提纲挈领的展示了本文的主体内容。 4 浙江大学硕士学位论文第2 章图片浏览研究综述 2 1 引言 第2 章图片浏览研究综述 在绪论的介绍中，我们已经大概介绍了当前图片浏览技术研究的现状。在本 章中，我们会对已有的图片浏览技术做出综述，并且分析它们的优点及不足这 些工作对于本文的工作具有重大的借鉴意义。 前面已经指出，图片浏览技术必须做到高效和保证视觉愉悦性。为了达到高 效的目标，也就是为了充分利用有限的时间和屏幕( 画布) 空间来展示图片，现 有的大规模图片集合的浏览技术根据它们对图片的排列方式可以分为两类：空问 排列方法( s p a t i a la r r a n g e m e n tm e t h o d ) 和时间排列方法( t i m ea r r a n g e m e n t m e t h o d ) 。最近出现了一类新的方法同时考虑了时间和空间上的排列方式，我们 把它放在时间排列方法中加以说明。 2 2 空间排列方法 为了充分利用画布空间，空间排列方法致力于创建一个能展现所有图片的二 维表示。这方面的一个传统方法就是图片马赛克( i m a g em o s a i c i n g ) ，它把所有 的图片用一种不重叠的方式在一个简单的网格内排列好。由于它的简单实用性， 它在很多商业软件中得到了广泛的应用，例如a c d s e e 1 1 ，p i c a s a 1 5 1 ，p i c l e n s l l 6 1 。 如今的图片马赛克技术采用更加成熟的算法来决定画布的版面安排和图片的位 置。b e d e r s o n 等人【2 1 提出了一种使用有序定量树状图的方法来决定画布的布局， 并且成功的把其算法应用到了图片浏览器p h o t o m e s a 之上。k u s t a n o w i t z 和 s h n e i d e r m a n t l l 】把这个方法进行了扩展，他们采用了改进的画布格局算法生成了 一个更高效的两级图片表达形式。在这个新的形式中，最能反映主旨的图片被放 置在画布的中央位置，而画布的其他区域则放置层次稍低的图片。他们的一个效 果如图2 1 所示。 5 浙江大学硕士学位论文 第2 章图片测览研究综述 叠鑫翻兹嚣稍，确蝴辫 ，霹 醐薅霪貉j 憋毪虚纨鲞茂嗡汹擒心 翟 雠困矗。惫“滚磊i 确 潮 避鬻躺您镒缄缄 圈幽函滋豳斌 圜鳓翻圈琵戮 爹麓 图2 1 采用了双层表示的家庭照片集 为了达到更好的图片排列效果，一些工作更关注于照片管理。例如，p l a t t 等 人【川提出了图片自动聚类的方法，而c u i 等人【5 l 则提出了一个有效的图片标柱 模式。但是，本小节提到的所有技术，都是使用图片马赛克的形式在画布上展现 图片，原则上不允许图片重叠，因而在有限的画布空间内增大了信息冗余度，并 没有达到高效利用有限空间的目的。 最近，一种称之为图片拼贴画( c o l l a g e ，本文也称之为图片拼接) 的技术 引起了广泛的注意并且变得流行起来【8 ，坝6 - 1 & 2 。图片拼接技术可以产生一个紧 凑的并且令人赏心悦目的多图片展现形式，它和图片马赛克技术最大的不同之处 在于允许图片之间重叠，这样，通过遮挡图片的非重要区域，在有限的画布空问 内就可以表示更多图片的有用信息，达到了高效利用画布空间的目的。由于本文 提出的动态图片拼接技术是在已有图片拼接技术的基础上直接产生，因而我们将 在2 3 节详细介绍这一种图片拼接技术。 图片拼接的初始工作由g e i g e l 和l o u i i s 完成。他们用一群图片产生一个自 动的图片拼接的结果，但是他们的结果中包含了大量的空自区域，视觉效果不佳。 6 一蹦篇蠛淼嘲一飘a啊然戮强嘲锶皖一潮1锡黔鼬 讶茂蕊曩门馘瞄圜鬣嬲霸裔蔼螨捌娥 一豫骢一魄蛳蹬 霾鹾零嘲鬟竣缴燃豳 啊懑鹏露陇攀强燃弘斌誉涨警斛舳鬻娃豳隗幽囊蜢熬盼蠢峨群鬈陇跚馘瞄 掣蕊隧舅辅t一 娥圈能幽隔一隧盐税獭巍娥磁 戳辫麟藏聪鳓 辫娥程热聪鳓黎圈谜心隧糟秘滓娥燃激鑫 浙江大学硕士学位论文第2 章图片浏览研究综述 r o t h e r 等人【1 9 】提出了一种“数字织锦 ( d i g i t a lt a p e s t r y ) 的方法，从图片集 中自动产生一个稠密的无缝图片拼接效果，可以认为这是图片拼接的真正开端， 如图2 2 所示为一个效果图。 图2 2d i g i t a lt a p e s t r y 的结果 接下来，r o t h e r 等扩展了自己的方法，提高了方法的可量度性和计算效率， 做出了一个a u t o c o l l a g e 的结果【”l 。但是在这个工作中，他们对图片进行了筛选， 并不是所有的图片都能放进拼接图中，因而不能在图片拼接中浏览全部图片。 w a n g 等人1 2 1 】在图片拼接时中不采用无缝连接的方式，而是像大部分商业软件那 样，保持了图片的边框。d i a k o p o u l o s 和e s s a l 6 】提出了一种交互的方法来生成 图片拼接结果，用户可以根据自己的需要来创建图片拼接。 在这里我们需要特别提及视频拼接技术( v i d e oc o l l a g e ) 【4 2 2 1 。c h r i s t e l 等 人【4 l 提出了一种方法可以从新闻视频集合中生成一个视频拼接的结果，在他们的 方法中，所有输入视频的每一帧都被用来产生一个二维图片拼接，由此可以看到 二维图片拼接技术在三维上的应用。w a n g 等人【硐用类似的技术从一个内容更加 7 浙江大学硕士学位论文 第2 章图片浏览研究综述 广泛的视频集中进行视频拼接，该方法采用了更多种类的排列策略。k a n g 等人1 1 0 l 采用了时空蒙太奇的方法从多个输入视频中产生一个视频拼接的结果。 2 3 时间排列方法 除了前面提到的采用空间排列方法来浏览图片之外，另一种方法是按时间排 列方式来浏览图片。滚动播放( s l i d e s h o w ) 是最常见的一种，大部分商业软件1 1 1 5 1 6 l 采用这种方式。滚动播放一次展示一副图片，所有的图片用一种令人愉悦的 方式顺序展现。最近，c h e n 等人【3 】提出了一种滚动播放图片马赛克的方法。这是 一种结合时空排列形式来浏览图片的方法，每一帧图片马赛克中包含一幅反映主 旨的大图片，在它的周围排布着一些衬托主旨的小图片，如图2 3 所示。随着音 乐节拍，不同的图片马赛克被顺序展现出来。 一一 霉! ? 霪纛鬻鍪i 霪嚣絮篱麓 。 奄i i 黧一一l 簪；i o 耄 骶孽 霞澎鬟辫濑 ! 彗誊五越滋澎耄! 凌 ，i 叠缎舞鬟畿浚| | ；期 图2 3 滚动播放图片马赛克 这种方法需要事先对图片集按照不同的主题进行聚类，根据聚类的结果安排 画布，并且由背景音乐的节拍来判断是否需要播放下一个图片马赛克。这种方式 考虑了图片浏览的时间和空间顺序，但是在时间上仅考虑音乐节拍，在空间上不 允许图片之间的重叠，并未达到对时间和空间的充分利用。本文提出的动态图片 拼接技术较此有两个主要不同之处。一，动态图片拼接采用可重叠的拼接形式， 达到了对画布空间的高效利用，可以展现更多的图片信息。二，动态图片拼接 强调浏览的连续性。在更新画布时，只是更新画布上的少数图片，大部分图片仍 然保留，而滚动播放图片马赛克则是对画布的完全刷新，时间上相邻的两个画布 之间内容及图片布局迥异。根据前面的分析，浏览的连续性更可以适应人脑的记 忆暂存现象，因而动态图片拼接较之滚动播放图片马赛克能更充分的利用空间和 时间，获得理想的图片浏览效果。 8 浙江大学硕士学位论文第2 章图片浏览研究综述 2 4 图片拼接 前面已经介绍过，本文的工作借鉴了图片拼接技术的结果，因此，本小节专 门分析图片拼接技术睁1 8 2 1 2 2 1 。，并且指出在浏览大规模图片集时的不足。尽管 之前的工作使用了很多不同的术语，例如，照片拼接( p h o t oc o l l a g e ) i s ，图 片拼接( p i c t u r ec o l l a g e ) 【2 1 1 ，自动拼接( a u t o c o l l a g e ) 1 8 l ，视频拼接l 翊， 它们需要解决的问题都是相似的，那就是它们都需求解在静态的二维画布上图片 ( 关键帧) 的最优排列方式。为了避免因不同术语引起歧义，我们统一使用“图 片拼接”来描述这个问题。 给定一个图片集合，图片拼接的目的是在一个给定大小的画布上求得这些图 片( 或者它的一个子集) 的一个最优排列方式( 这里画布的面积往往比图片的面 积总和要小很多) ，使得画布上所有图片展现的信息量之和达到最大。一般的来 说，这是一个组合优化问题，但是实际的解决方法中大量采用了启发式的方法来 缩小解空间。图片拼接求解可以分为两个阶段，即预计算阶段和优化阶段。 2 4 1 预计算阶段 在这个阶段，图片拼接算法首先需做的是精简输入图片集合，若输入图片集 中含有大量的冗余重复信息( 例如视频中的所有帧) ，则算法首先从输入图片集 中挑选出那些最具有代表性的图片，只有这些经过挑选的图片才能放入最后的拼 接结果中。接下来，对于每一幅被选中的图片，算法采用一个可视信息度量方法 来计算它的最感兴趣区域，也就是视觉上包含信息量最多，最显著的区域。目前 在计算机视觉和多媒体领域中已经发展了多种可视信息度量方法1 9 1 2 3 1 4 1 ，利用 这些方法可以采用对象识别技术在图片中找到重要的对象，例如人脸【2 0 。 2 4 2 优化阶段 在优化阶段，图片拼接算法把经过挑选后的图片排列在画布上，使得画布上 展现的信息量最大。一些已有的工作会去掉图片的边框，实现图片的无缝连接1 1 8 2 2 1 ，这主要是通过a l p h a 通道混合或者p o i s s o n 融合的方式来实现的，以期达到 9 浙江大学硕士学位论文第2 章图片浏览研究综述 更好的视觉效果。由于图片的面积总和要比画布面积大很多，因此只有图片的重 要区域才能被显示在画布上，而不重要的区域则被裁剪【6 1 ，混合【1 8 2 2 1 ，覆盖【2 1 l 。 这是一个组合优化问题。设画布的面积为a ，我们需要排列n 幅图片，那么 就存在a 种可能的图片排列方式。尽管有多种启发式的方法能够缩小解空间， 采用全局优化方法仍然有着很大的计算量。已有的算法或是用简单的启发式方法 来得到一个次优解【2 2 1 ；或是采用固定格局的画稚1 6 1 ，从而得到一个非常小的解 空间；或是并不考虑解空间中所有点，而是在解空间中做一个蒙特卡罗采样l 殂1 。 2 4 3 已有图片拼接算法的不足 由上面的介绍可以看到，尽管已有的图片拼接算法能够有效的从一个小规模 图片集中产生良好的图片拼接效果，然而它的可扩展性受到了画布大小的严重限 制，无法在有限的画布上展示更多的图片。实验表明，如果画布的面积与所有图 片的面积总和之比小于0 6 时，那么图片的任何排列方式都会显得非常拥挤以致 于影响视觉效果【2 。因此，如果想用已有的图片拼接算法来浏览大规模图片集， 只有以下两种方法： 1 ) 创建一个面积足够大的画布，做成一个包含所有图片的大型拼接图。这 种方法的缺点非常明显。首先，根据前面的分析，大的画布会形成巨大的解空间， 导致这种方法计算量非常大，效率很低。其次，浏览画布会变得非常不方便。为 了浏览大小超过用户屏幕分辨率的画布，用户必须前后左右拖动画布，显得非常 不方便。 2 ) 从输入图片集中创建一个小型拼接图的序列，可以设想每一个小的拼接 图包含1 0 到2 0 幅图片，然后用滚动播放的形式播放拼接图序列。这种方法的缺 点在于破坏了图片浏览的连续性，在时间上相邻的两个拼接图之间有很大的区 别。 根据上面的分析可以看到，已有的图片拼接算法尚不适合用于浏览大量图 片，由此本文提出了不破坏浏览连续性的动态图片拼接算法来浏览大规模图片 集。 1 0 浙江大学硕士学位论文第2 章图片浏览研究综述 2 5 本章小结 本章主要介绍了已有的图片浏览技术，并且把现有的浏览技术按照空间排列 方法和时间排列方法进行了分类说明，介绍了它们的研究历史和各自的特点。由 于本文工作主要基于图片拼接算法，因此本章专门介绍了图片拼接算法的研究历 史和现状，它的优化求解的两步过程，以及图片拼接算法在浏览大规模图片集时 的不足，由此说明了设计新算法来浏览大量图片的必要性。 浙江大学硕士学位论文第3 章动态图片拼接算法综述 3 1 引言 第3 章动态图片拼接算法综述 从本章开始我们系统介绍动态图片拼接算法。本章将主要介绍动态图片拼接 系统的概貌，图3 1 是整个动态图片拼接系统的流程图。 p h o t oc o l l e c t i o n s 图3 1 动态图片拼接系统流程图 从图3 1 可以看到，动态图片拼接系统的输入是一个图片集，它的数据来源 可以是本地的图片数据库，也可以是互联网上图片搜索的结果，等等。在系统处 理之前并不需要一次性输入全部图片，因为我们的系统是按一定的顺序处理所有 图片。这样系统在很多场合下就具有更强的可用性，例如，服务器给用户发送图 片查询结果时，一般情况下所有的图片都是依次传送过来，用户端一次只能接收 一幅图片，非常适合动态图片拼接系统采用“去旧迎新 的方式产生动态拼图以 供用户浏览所有的图片。 我们的动态图片拼接系统包含四个模块：图片关键区域计算模块( s a l i e n c y c o m p u t a t i o n ) ，调度模块( s c h e d u l e ) ，优化模块( o p t i m i z a t i o n ) ，绘制模块 浙江大学硕士学位论文第3 章动态图片拼接算法综述 ( r e n d e r i n g ) 。下面四个小节分别介绍这四个模块。 3 2 图片关键区域计算模块 该模块负责计算所有输入图片的视觉关键区域。已有的图片拼接工作往往采 用简单的基于r o i ( r e c t a n g l eo fi n t e r e s t ) 的视觉关注模型，这种模型把图片 的视觉关键区域视为一个矩形，然后在该矩形赋予相同的重要值( i m p o r t a n c e v a l u e ) 。对于采用全局优化方法的图片拼接算法来说，这种简单的模型可以有效 的减少计算量，因而是必要的，但是这种方法的缺陷十分明显。很多情况下图片 往往具有多个r o i ，例如，家庭照片中经常可以看到两个或者更多的人脸，显然 也就具有相应数量的r o i ：而且不同的r o i 的重要值也不必相同。 我们提出了一种更具一般性的视觉关注模型来解决这个问题。首先，我们引 入了“信息图”( i n f o r m a t i o ni m a g e ) 的概念。我们计算每一个输入图片的信息 图，信息图的大小和原图片大小一致，它的每一个像素值就是对应图片在相应像 素上的重要值( i m p o r t a n c ev a l u e ) 。这种一般性的模型不仅解决了多r o i 的问 题( 只需在信息图上指定相应的r o i 即可) ，由于信息图定义在像素级别上，我 们可以在每一个r o i 内部采用不同的重要值分布模型，而非之前的单一值。例如， 在本文的实现中，所有的r o i 内部的重要值分布采用了高斯分布模型，取得了良 好的效果。同时，为了提高这种像素级信息图的查询效率( 计算重叠区域信息损 失时需要查询信息图，累计区域内所有像素的信息值) ，我们引入了“信息积分 图 。对于每一幅信息图，我们可以在线性时间内计算它的积分图【2 0 】并且保存， 此后对信息图的查询可以转移为对积分图的查询，并且时间复杂度仅为d ( 1 ) ，极 大提高了信息图的使用效率。除此之外，我们采用了有效的人脸检测算法【冽， 信息图中对应人脸的区域的重要值设为一个足够大的值，保证人脸永远不被覆 盖。为了说明信息图模型较单一r o i 模型的优势，可以对比图3 2 和图3 3 。我 们用已有的图片拼接算法和单一r o i 模型生成了拼接结果图3 2 ，而采用动态图 片拼接算法和信息图模型，生成的结果如图3 3 所示。 1 3 浙江大学硕士学位论文 第3 章动态图片拼接算法综述 图3 2 单一r o i 模型图片拼接结果 图3 3 信息图模型动态图片拼接结果 注意到标记红圈的图片。图3 2 仅仅标记了图片左部的r o i ，因而右边的人 全被挡住；而图3 3 采用了信息图标记了左右两边的r o i ，并且在两个r o i 内部 采用了高斯分布模型，于是图片左右方的关键部分都不被遮挡，其他相对不重要 的部分可以被覆盖以显示其他图片的重要信息，达到了一个合理的图片拼接效 1 4 浙江大学硕士学位论文第3 章动态图片拼接算法综述 果。 3 3 调度模块 调度模块负责从当前的拼接图中删除图片，或者插入新图片到拼接图中。它 直接影响浏览顺序。系统允许用户自定义调度策略，从而得到多样化的图片拼接 效果。下面我们将论述与调度相关的三个要素，即调度时间，调度顺序，调度之 后的画布布局更新。画布布局更新并不直接影响调度的结果，但是新图片加入画 布后的初始位置对当前动态图片拼接的结果有直接影响，这是因为算法采用一个 局部调整的方式来优化图片在画布上的排列方式。我们认为新画片加入画布后， 它的初始位置的选择也属于调度的范围。 3 3 1 调度时间 系统根据一定的准则，为每一个图片确定了它在画布内的最大停留时间，我 们称之为生命时间( 1 i f et i m e ) 。一旦图片被调度模块选择进入了画布，那么一 个相应的计时器开始计时。当某一图片的生命时间结束时，那么一个“p h o t o r e m o v a l 事件会被触发，系统从画布中移除该图片。当移除若干幅图片之后， 画布面积和画布内所有图片面积总和之比( a k 文之后把这个比值简称为画布稠密 系数) 会升高，当这个比值超过一个给定的阈值时( 例如0 7 5 ) ，那么系统认为 画布容纳的图片数目偏少，于是一个“p h o t oi n s e r t i o n 事件被触发，一张新 图片被插入画布。在所有图片的大小相差不多的情况下，系统总是可以将画布稠 密系数保持在一个适当的合理水平。在我们的实际实现中，画布稠密系数的值稳 定在o 6 5 左右。 这里需要特别关注的是系统指定图片生命时间的准则。一个最简单的方式就 是对所有图片指定一个统一的生命时间，然而这种方法不能反映图片重要性的差 异。在本文中，系统采用用户自定义的生命时间准则，例如图片大小( 大图片拥 有更长的生命时间) ，图片内容的丰富程度( 内容丰富的图片拥有更长的生命时 间) ，等等。 浙江大学硕士学位论文第3 章动态图片拼接算法综述 3 3 2 调度顺序 当“p h o t oi n s e r t i o n 事件被触发之后，调度顺序决定了应该选择哪一幅 图片加入画布。例如，可