（计算机科学与技术专业论文）图像—视频抠像技术的研究.pdf

摘要 随着数字获取技术的发展，家用数字产品的普及，数字传媒业的兴起，影视业的火 爆，虚拟、增强现实技术在工业领域的深入应用，图形学与人们日常生活的联 系是越来越紧密、越来越密切。图形学的根本任务是真实地表示客观世界，表现真实、 操作方便、响应快捷是表示的基本要求。但真实地表示复杂物体，例如毛发、阴影、树 木等，目前还是图形学的研究难点和热点之一。数字抠像技术用于抽取图像、视频的感 兴趣物体，并将抽取物体合成到新场景，这种基于图像的2 d 操作方式一定条件下能够实 现对复杂几何物体的表示和操作，本文主要研究复杂物体的数字抠像技术及关键问题。 本文研究了提示驱动的图像抠像、基于视频时空体的视频抠像、单张室外图像的阴 影抠像和光照一致图像合成四个问题。 图像抠像包括软抠像和硬抠像。由于受交互中离群数据的影响，基于g r a p hc u t s 的抠像方法需要对抠像结果进行多次补充修改。提出了一种提示驱动的硬抠像方法，利 用图像保持空间局部性转换后的次小拉普拉斯特征向量将图像划分为连通区域和孤立区 域，用来辅助用户交互，避免了用户交互的盲目性，能够一次完成抠像。泊松抠像方法 假定前景、背景亮度光滑变化，把梯度作为抠像保持特征，易产生模糊细节，需多次局 部操作细化抠像。本文改进了泊松抠像方法，将张量作为保持特征，能够抠取细节保持 的较高质量抠像。 视频时空体同时表现视频的时间特性和空间特性，可用来辅助视频抠像。巨量的图 节点数限制了基于g r a p hc u t s 的视频抠像方法所能处理的视频长度。基于视频时空体， 提出了抠取刚性物体的层次式3 d g r a p h c u t 算法，能够以笔划交互快速地完成抠像。该 算法先在低分辨率视频完成初始抠取，然后逐级投影到高分辨率视频，减少了所处理的 图节点数目，提高了抠像效率。逐帧抠像方式很难产生时空一致的视频抠像，提出了基 于视频时空体的泊松视频抠像方法，将抠像操作作为一个整体进行处理；跟踪关键帧掩 码生成掩码图像序列：用双共轭梯度法求解含有千万个未知数的线性方程组，能够产生 时空一致的视频抠像。 从单张室外无定标图像中抠取复杂物体的阴影属于欠约束问题，它包括三个子问 题：阴影区判断、阴影抽取和阴影区纹理恢复。本文提出了基于物理光照模型的阴影抽 取方法，以近似方式计算照片的光照环境、漫射系数和太阳光遮挡系数。根据室外阴影 的特点光顺阴影抠像，从而能抽取出真实的阴影。相比于已有的阴影抽取方法，本文的 方法能很好地处理软影区，且阴影去除区域能无缝地融合到图像中。 中文摘要 合成不同光照环境中获取的图像会产生不真实的效果。为了将抠像无缝地合成到其 它背景图像，提出了一种保持视觉突出性的光照一致图像合成方法。该方法首先根据亮 度和色度的综合特性计算视觉突出性，再对齐抠像和背景图像的颜色主轴，然后用视觉 突出性约束图像合成，从而能合成出既保持抠像的视觉突出性又光照一致的图像。 关键词：图像抠像；视频抠像；阴影抠像；泊松方程；g r a p h c u t s ；时空一致性； 分割；合成；视觉突出性 a b s t r a c t w i t ht h ed e v e l o p m e n to fd i g i t i z e da c q u i s i t i o nt e c h n o l o g y , t h ep r e v a l e n c eo fc o n t e m - p o r a r yd i g i t i z e da p p l i a n c e , t h er i s eo fm e d i ai n d u s t r y , t h eb l o o m o fm o 、，i ef i e l d a n d t h ee x t e n s i v ea p p l i c a t i o no fv rw m u a lr e a l i t y ) a n da r ( a u g m e n tr e a l i t y ) ，t h et i eb e - t w e e ng r a p h i c sr e s e a r c ha n dl i f ei sb e c o m i n gm o r ea n dm o r et i g h t e ra n dc l o s e r t h e f u n d a m e n t a lg o a lo fg r a p h i c sr e s e a r c hi st or e p r e s e n tt h er e a lw o r l d , a n dt h ep r e l i m i - n a r yr e q u i r e m e n t st or e p r e s e n t a t i o n a r et h ef a i t h f u ln a r r a t i o n , e a s ym a n i p u l a t i o n , q u i c k r e s p o n s e h o w e v t h e r ee x i s t ss u c hc o m p l e xo 惭e c 协a sh a 弛s h a d o wa n dt r e et od i f - f i c u l t yd e p i c t , h o wt or e p r e s e n tt h e ma r et h e c u n - e n th o t d i g i t a lm a t t i n gf o c u s e so n e x t r a c t i n gt h ei n t e r e s t e do b j e c t sf r o mi m a g e v i d e o , a n dc o m p o s et h e mi n t ot h en o v e l c o n t e x t m a t t i n gc o u l dm a n i p u l a t et h ec o m p l e xg e o m e t r yo b j e c te q u i v a l e n t l yw i t l l2 d o p e r a t i o n a lm a n n e r t h et h e s i sc o n c e n t r a t e so n t h em a t t i n ga n di t sk e yi s s u e s t h e d i s s e r t a t i o n i n v e s t i g a t e s f o u r p r o b l e m s c o v e r i n g i m a g e m a t t i n g , v i d e o m a t t i n g , s h a d o we x t r a c t i o na n di m a g ec o m p o s i t i o n h a r dm a t t i n ga n ds o f tm a t t i n ga r et h eg e n e r a l l ys o - c a l l e di m a g e m a t t i n g g r a p h c u t sa n dp o i s s o nm a t t i n ga r et h er e p r e s e n t a t i v em e t h o do fh a r da n ds o f tm a t t i n gs e p - a r a t i v e l y s u b j e c tt ot h ei n f l u e n c eo fo u t l i e ra m o n gu s e fi n t e r a c t i o n s , m a t t i n gb a s e d u p o ng r a p hc u t sr e q u i r e sa d d i t i o n a lm o d i f i c a t i o n s i nt h e s i s ，a c c o r d i n g t ot h es e c o n d s m a l l e s te i g e n v e c t o ra f t e ri m a g ei st r a n s f o r m e dw i t hl o c a l i t yp r e s e r v i n gp r o j e c t i o n s , t h e i m a g ei sp a r t i t i o n e di n t ot h ec o n n e c t e da n di n d e p e n d e n tr e g i o n s d i f f e r e n tt y p e so f r e g i o nr e q u i r ed i f f e r e n ts t r o k e s , h e n c et h e u s e ri n t e r a c t i o ni sg u i d e da n dt h eu s e ri n t e r - a c t i o ni n d e p e n d e n to ft h ef i n a lr e s u l t p o i s s o nm a t t i n ga s s u m e st h a tf o r e g r o u n da n d b a c k g r o u n d a l es m o o t h , a n dt a k et h e g r a d i e n t a st h e m a t t i n gf e a t u r e s ，b u t i tr e q u i r et h e a d d i t i o n a ll o c a lo p e r a t i o n st or e f i n et h er e s u l t a ne x t e n s i o nt op o i s s o nm a t t i n g i sg i v e n , w h i c hm a i n t a i n st h et e n s o ri nt h em a t t e , a n dc o u l da c h i e v et h eh i g h - q u a l i t yr e s e t s p a c e - t i m ev i d e ov o l u m es i m u l t a n e o u s l ye x h i b i t st h es p a t i a la n dt e m p o r a lp r o p - e r t i e s , a n di tc a nb ee x p l o i t e df o ra s s i s t i n gt h ev i d e oe d i t i n g d u et ot h eh u g en u m b e r o fg r a p hn o d e , t h ec o n v e n t i o n a lv i d e oo b j e c te x t r a c t i o nm e t h o db a s e do ng r a p hc u t s s h o w st h el o we f f i c i e n c ya n dh a ss l o wr e s p o n s et ou s e ri n t e r a c t i o n a na p p r o a c ho f h i e r a r c h i c a l3 d g r a p hc u t si sg i v e n , w h i c hi n i t i a l l ye x t r a c t st h eo b j e c ti nt h el o wr e s o - i h i v 英文摘要 l u t i o nv i d e o , t h e np r o j e c t st h ep u l l e do b j e c t st oh i g h e rr e s o l u t i o nv i d e o t h ed i s c u s s e d m e t h o ds i g n i f i c a n t l yr e d u c e st h en u m b e ro fg r a p hn o d e s ，a n dc o u l da c h i e v et h eh i g h - q u a l i t ye x t r a c t i o no n l y w i t hd e p e n d e n c eo nt h eu s e r - s u p p l i e ds t r o k e so nk e y f r a m e t h e h i e r a r c h i c a l3 dg r a p hc u t sc o u l da c c e l e r a t et h ee f f i c i e n c yo f3 dg r a p hc u t f r a m e - b y - f r a m em a t t i n gi sd i f f i c u l tt oa c h i e v et h es p a t i o t e m p o r a l l yc o h e r e n tv i d e om a t t i n g a n a p p r o a c hw h i c hf o r m u l a t i n gt h ev i d e om a t t i n g a ss o l v i n gt h ed i s c r e t ep o i s s o n e q u a t i o n s w i t h i ns p a c e - t i m ev i d e oc u b e t h ef r a m et r i m a pi sp r o d u c e d b yt r a c k i n gt h ek e y f r a m e t r i m a p t h eb i c o n j u g a t eg r a d i e n ti su s e df o rs o l v i n gt h eb a n d e ds p a r s ee q u a t i o n sw i t h m i l l i o n so fl m r l k n o w n s t h ep r o p o s e dm e t h o dc o u l dp r o d u c et h es p a t i o t e m p o r a u yc o n - s i s t e n tv i d e o m a t t i n g e x t r a c t i n gt h e n a t u r a ls h a d o wf r o ma nu n c a l i b r a t e do u t d o o r i m a g e i si n - p o s e d , a n d i tc o v e r st h r e e s u b p r o b l e m s ：s h a d o wd e t e r m i n a t i o n ，s h a d o w e x t r a c t i o na n ds h a d o wr e - m o v a l am e t h o do fs h a d o we x t r a c t i o ni sp u tf o r w a r d , w h i c hi sb a s e do nt h ep h y s i c a l i l l u m i n a t i o nm o d e l o u ra p p r o a c ha p p r o x i m a t e l ye v a l u a t e st h ei l l u m i n a t i o nc o n t e x t , d i f f u s ec o e f f i c i e n ta n di l l u m i n a t i o no c c l u s i o ns c a l a nc o m p a r e dw i t ht h ep r e v i o u sm e t h - o d s ，t h eg i v e na p p r o a c hc o u l de x t r a c tt h er e a l i s t i cs h a d o w , r e m o v et h es h a d o ws i m u l t a - n e o u s l y b a s e do nt h ec h a r a c t e r i s t i c so fn a t u r a ls h a d o w , t h es h a d o wm a t t ei ss m o o t h e d , h e n c ei nt h es h a d o wr e m o v a li m a g et h et e x t u r ea t t r i b u t ei sw e l lm a i n t a i n e da n dt h e s h a d o wr e m o v a lr e g i o ni sa b l et ob es e a m l e s s l y i n c o r p o r a t e di n t ot h ei m a g e t o c o m p o s et h ei m a g e st a k e nf r o m d i f f e r e n ti l l u m i n a t i o n sl e a d st ou n r e a l i s t i cc o r n p o s i t i o n a ni m a g ec o m p o s i t i o nm e t h o dw i m s a l i e n c ep r e s e r v i n gi sp r e s e n t e d , w h i c h f o c u s e so nh o wt oa c h i e v et h ec o n s i s t e n tl u m i n a n c ea m o n g c o m p o s i t i o nc o m p o n e n t s t h eg i v e na p p r o a c hi n c l u d e ss a l i e n c ed e t e r m i n a t i o n , w h i t e p o i n tc o r r e c t i o na n dl u m i - i h g , n c ea d j u s t m e n tw i t ht h ec o n s t r a i n to fs a l i e n c e f i r s t l y , t h es a l i e n c ei se v a l u a t e do n f u l l ye x p l o i t i n gt h e d i f f e r e n c eo fl u m i n a n c ea n dc h r o m i n a n c e , t h e nt h e p r i n c i p l ec o l o r a x e so ft h ee x t r a c t e di m a g ea n db a c k g r o u n di sa l i g n e d , f i n a l l yt h ei m a g ec o m p o s i t i o n i sf o r m u l a t e da san o n l i n e a ro p t i m i z a t i o np r o b l e mw i t ht h es a l i e n c ec o n s t r a i n t t h e d i s c u s s e ds c h e m ac o u l da c h i e v et h el u m i n a n c ec o n s i s t e n ti m a g ec o m p o s i t i o nw i t hp r e - s e r v i n gt h es a l i e n c e k e yw o r d s ：i m a g em a t t i n g , v i d e om a t t i n g , s h a d o wm a t t i n g , g r a p hc u t s ，s p a - t i o t e m p o r a lc o h e r e n c e ，s e g m e n t a t i o n , c o m p o s i t i o n , s a l i e n c e 第一章绪论 随着数字获取技术的发展和消费级数字产品的普及，人们积累了大量记录其生产和 生活过程的媒体文档，对这些文档进行编辑以产生满足其需要的新文档有着重大的现实 意义。图像、视频编辑是对这些媒体文档内容进行编辑和修改的技术。数字抠像技术是 图像、视频编辑的重要操作之一，用于从图像、视频等媒体文档中抠取出用户感兴趣的 物体。从s m i t h 提出蓝屏法抠像【1 】1 到今天，抠像技术一直得到研究者的青睐和r r 业界 的关注。 数字抠像技术在影视制作、远程视频会议、虚拟现实、增强现实、数字及家庭娱乐 等方面有着广泛的应用。它可以将艺术创作与实际拍摄完美地结合起来，可以在影片中 无缝插入物体，从而给观众带来强烈的视觉震撼和身临其境的感受，“星球大战”、 “侏罗纪公园”、“黑客帝国”、“魔戒三部曲”和“哈利波特历险记”等高票房收入 影视大片都无一例外地用到了数字抠像技术。同时，抠像技术与人们的日常生活的联系 也越来越密切，广泛应用于人们的日常生活中，如设计电子卡片、编辑户外活动录像 等。 由于诸多因素的制约，到目前为止，真实地表示一些自然界物体，例如，树木、毛 发等仍存在一些未解决或解决得不够好的技术问题。数字抠像技术能够将实拍物体抠取 出来并合成到所需场景中，以2 d 方式操作3 d 物体，从而无需定标、重建等操作就可表 示自然界物体。数字抠像技术一定程度上为计算机图形学提供了真实表示自然界物体的 辅助手段，在计算机图形学和视觉领域有着很高的学术研究价值。 由于抠像技术的巨大应用潜力和重要的学术研究价值，近年来抠像问题得到计算机 图形学和视觉领域研究人员的广泛关注和深入研究，提出了基于统计学习、基于图表示 和基于泊松偏微分方程的抠像算法。这些算法能够抠取较高质量的图像视频抠像，但 仍然存在着一些需要深入研究的问题和亟待改进的地方。例如，基于统计学习的抠像算 法会给出带有少许颜色沾粘的抠像结果，对细节的保持程度还不够细微；基于图表示的 抠像算法过多地依赖用户交互；基于泊松偏微分方程的抠像算法对前景和背景的要求比 较苛刻。 本文在图像抠像、视频抠像、阴影抠像和图像合成方面进行了研究，提出或改进了 一些抠像算法。与已有方法所不同，本文的图像抠像算法强调保持抠像细节，分析图像 的隐含内容提示，降低抠像算法对用户交互的依赖；视频抠像着重研究如何抠取时空一 致的视频抠像，提出了基于视频时空体的层次式3 d g r a p h c u t 算法和泊松视频抠像算 法，降低了时空同时处理视频的计算代价；阴影抠像重点研究如何在单张室外图像抠取 1 2第一章绪论 阴影，提出了一种单张室外图像的阴影抠取和阴影区纹理恢复方法，该方法能够抽取与 实际阴影一致的阴影抠像，且阴影去除图像能保持纹理结构；图像合成算法致力于合成 光照一致的图像，提出了保持视觉突出性的光照一致图像合成方法。 1 1 数字抠像问题 根据媒体类型的不同，数字抠像包括图像抠像和视频抠像。这两类抠像都假定图 像视频j 是物体( 前景) f 及其背景引拘线性组合，如式( 1 1 ) 。 i = a f + ( 1 一q ) b( 1 1 ) 其中。是物体f 和背景b 的合成系数。 抠像就是要抽取出物体f ，获得其o t 图像。本文出现的“抠像”一词有动词和名词两 种词性，作动词时是指抠像操作，即抠取的意思；作名词时是指物体f 的n 值集合。 抠像问题是病态问题。图像视频是由包括f 和b 在内的场景经过透视变换形成，恢 复f 是一个逆向问题。由于目前的技术所限，恢复复杂物体f 仍存在一些解决得不够好 的技术问题，因而人们可在二维图像空间近似估计口抠像，通过操作抠像以达到等价操 作三维物体f 的目的。 式( 1 1 ) 中含有o t 、f 和b z 个未知量，只有，为已知量。根据已知条件数，抠像问题 可分为欠约束抠像和过约束抠像两类。欠约束抠像有多组解，抠像只是满足约束的一个 解。过约束抠像通过引入多源信息增加约束，抠像结果是满足多约束的最优解。欠约束 抠像面临的挑战是如何在信息不充分时抠取高质量的o t 图像；过约束抠像面临的主要问 题是如何充分、协调地利用多源信息。本文所讨论的抠像都属于欠约束抠像。 目前还没有一个统一的、定量的标准评价抠像质量，大多数人以主观视觉满意程度 作为评价标准，也就是说，n 图像细节清楚、不模糊、且有较强的真实感，即为高质量 的抠像。这里给出一些关于。抠像定性的评价标准，并用于评价文中的抠像质量。 没有颜色沾粘； 细节清楚、不模糊； o t 图像不闪烁； 纵观近年来出现的各种图像视频抠像技术，基本可分为三类：基于统计学习的抠 像方法、基于图论的抠像方法和基于偏微分方程的抠像方法。基于统计学习的抠像方法 利用概率和机器学习原理构建物体及背景模型，在最大可能性原则下抠取物体。基于图 论的抠像方法用图表示抠像环境，利用最大流最小割分割出用户感兴趣的物体。基于偏 微分方程的抠像方法将抠像问题公式化为偏微分方程，在最小能量原则下抠取出物体。 浙江大学博士学位论文 3 以上三类方法各有所长，相互补充，它们共同的目标是抠取的物体尽可能完整，细节尽 可能得到保持。 1 2 图像抠像 根据抠像的n 值和抠像所需的图像数，抠像分为硬抠像、软抠像和环境抠像三种类 型。 i q 【0 ，1 】 环境抠像多张图像 a = o ，1 ) 硬抠像一张图像 i o o 1 】 软抠像一张图像 软抠像与环境抠像的区别在于：软抠像的o t 值反映了物体和背景的合成情况，而环 境抠像的a 值反映了物体对环境的反射、透射和折射情况。另外，软抠像输入单张包含 物体的图像，而环境抠像输入的是多张包含有同一物体的图像。下面对这三类抠像的研 究现状进行阐述。 1 2 1 环境抠像 环境抠像的o t 图像反映了物体与周围环境的反射和折射的光学交互，主要用于抠取 半透明或透明物体。环境抠像所依赖的图像合成方程与式( 1 1 ) 稍有些不同，如式( 1 2 ) 所 示，其中引入了环境光亮度圣。 j = q f + ( 1 一n ) b + 圣 ( 1 2 ) 搭建实验平台是环境抠像必不可少的步骤，用于 获取有关物体的一组图像序列，记录物体与不同背景 的交互信息。图1 1 是【2 ，3 ，4 】所用的实验平台，它包 括计算机、物体、可控相机等硬件。物体放置在计算 机屏幕前，屏幕上播放预先设计好的图像。每播放一 幅不同的图像时，相机拍摄一次。环境抠像就是要从 获取的图像序列抠取物体的n 值。下面对近几年有关 图1 1 环境抠像实验台，引自文献【2 】环境抠像方面的研究 作掌了分析、望孽。 1 半透明物体会发生反射、透射和折射三种光学现 象。从图像中分析出物体的绝对反射、透射和折射系数几乎是不可能，因而，通常的方 法是用一组基近似模拟、表示三种效果的同时发生。z o n g k e r 4 l 将环境抠像问题看作 4第一章绪论 是如何利用系列纹理去表示物体的三种光效果。为了降低计算时间，z o n g k e r 采用先 估计物体覆盖区域，去除非覆盖区域，然后估计物体影响的背景小矩形区域，优化物体 边缘o l 值，估计侧背景对抠像物体的影响等逐步细化方式，取得了如图1 2 所示的效果， 图1 2 ( b ) 、1 2 ( c ) 、1 2 ( d ) 和图1 2 ( e ) 是将抠取的透明杯合成到不同背景的效果。在频域中 分析信号具有一些独特的优势，例如，突出指定频率，受噪音干扰小，不受比例变换影 响等。z h u 等【2 1 利用了上述优势，提出了一种频率环境抠像方法，取得了较好的抠像 效果。z o n g k e r 用单一标量值表示背景区域对物体抠像的贡献，只能表示单一的背景区 域，c h u a n g 等【3 】用有向高斯混合模型表示背景图像，使得环境抠像能反映物体对多处 背景的反射和折射情况，从而能得到更精确的环境抠像。p e e r 5 】用小波( w a v e l e t ) 表示 采样图像，每张图像分解为若干级，选择对抠像贡献较大的小波级，用一组重要的背景 图像分解小波线性表示环境抠像。相比于【3 ，4 】，p e e r 方法产生的抠像既能很好地表示 反射和折射，又能较好地反映物体的漫射特性，克服了【3 】不能精确表示不规则漫射表 面的缺陷。为了准确地表示出物体高光部分对抠像结果的影响，文献1 5 】需要更多的高频 信息，从而导致较慢的收敛速度。 文献【2 ，3 ，4 ，5 】中，采用了和图1 1 相似的实验平台，并变化背景图案模式，以 使西能更全面反映物体的反射、折射和散射情况。 ( a )( c )( d )( e ) 图1 2 7 环境抠像，引自文献【4 】。( a ) 为抠像前的玻璃杯；c o ) 、( c ) 、( d ) 和( e ) 是将抠取的玻璃杯抠像合 成到不同背景中。 ( a )( b )( c )( d ) 图1 3 环环境抠像，引自文献【3 】。( a ) 、( b ) 、( c ) 和( d ) 分别是在同一背景下合成不同时刻的环境抠像。 浙江大学博士学位论文 5 环境抠像能逼真地反映物体与环境的光亮度相互关系，但环境抠像需要大量采样( 拍 摄) ，通常需要采样一千张以上的图像，存贮开销巨大，且文献【2 ，3 ，4 】的方法只适合小 场景。扩大环境抠像的场景范围，降低采样量是环境抠像要解决的主要问题。 1 2 2 硬抠像 硬抠像【6 ，7 】是将物体f 从图像，中分离出来，即将j 划分为前景区f 和非前景区f 。 硬抠像的o t 值，要么是o ，要么是1 ，“0 ”表示背景，“1 ”表示物体，其目的是要从图 像，中完整地抠取出用户感兴趣的物体f 。 硬抠像的代表方法是g r a p hc u t s 6 , 8 ，9 ，1 0 , 1 1 ，1 2 , 1 3 , 1 4 , 1 5 , 1 6 ，1 7 , 1 8 , 1 9 , 2 0 , 2 1 】 方法。g r a p hc u t s 方法用图节点表示图像的基本组成单位( 像素或区域) ，边表示基本单 位间的依赖关系( 区分度) 。g r a p hc u t s 用最大流最小割原理计算物体与背景的分割边 界。b o y k o v 等【6 】在所构造的图中包含源( s o u r c e ) 和汇( s i n k ) 两个特殊节点；图节点 与源或汇的连接边称为t - l i n k ，图节点与图节点的连接边叫n - l i n k 。t - l i n k 表示了图节 点与指定区域的相符程度，n - l i n k 表示图节点之间的相似程度，相似的节点间用较小的 约束边连接，差异大的节点间用较大的约束边连接。 图1 4g r a p hc u t s 抠像，引自文献【7 】。( b ) 是( a ) 的抠像结果 g r e i g 2 2 】是第一个将组合优化理论的中最大流最小割( m a x f l o w - m i nc u t ) 算法用 来到解决最小能量条件下的图像分割问题，g r e i g 的工作开启了图论在图像处理和视觉 领域的应用。遗憾的是，在g r e i g 提出该方法后的十多年时间，基于图的图像处理并没 有引起研究者的注意。b o y k o v 和j o l l y 【6 】是继g r e i g 之后再次将图论应用到图像处理 和视觉领域的研究者，正是由于他的工作，推动了基于图的抠像技术的发展。g r a p h c u t s 所赖以的图实质上反映了图像的能量分布，像素、区域及体素等图像基本处理单元 被表示为图节点，基本处理单元间的能量被表示为区域能量或边界能量。其中，区域能 量表示基本单元与用户交互的吻合程度，即先验能量1 6 】。边界能量描述相邻基本单元 间的相似程度，越相似的基本单元其边界能量越低，反之，差异越明显的单元其边界能 6第一章绪论 量越高。b o y k o v 6 】运用组合优化理论的最大流算法计算具有最小能量时的分割，沿最 小割位置抠取物体，如图1 4 所示。 传统g r a p hc u t s 方法对整幅图像处理，计算效率较低，j u a n 等【1 4 】提出了一种基 于初始轮廓的g r a p h c u t s 方法，通过指定初始位置，人为地去掉了偏离抠取目标很远 的区域，提高了g r a p hc u t s 的执行效率。此外，文献【1 4 1 证明了所提方法得到的最终 结果对初始轮廓的依赖很小。文献 1 4 1 所提方法适合分割物体与周围背景明显不同的图 像，对于复杂背景中的物体抠取，初始轮廓所能提供的有用信息较少，因而对抠取物体 的帮助也不大。 文献【6 】的方法在分割时易于趋向物体的最短边界，物体的完整性被破坏，w a n g 等 1 1 3 】提出了最小平均割g r a p hc u t s 方法。该方法不直接利用边的权，而利用边的平均 权。文献【1 3 】的方法可分割出具有连接边界的物体，勾勒出物体轮廓，但相比于s n a k e 和智能剪刀【2 3 ，2 4 】的交互式分割结果，w a n g 方法产生的轮廓过于零碎。 g r a p h c u t s 方法对海量数据进行分割时内存开销巨大、运算时间也无法忍受，例 如，用g r a p hc u t s 对5 1 2x5 1 2 5 1 2 的三维c t 数据进行分割时需要8 g b y t e 的运行内存 开销，且需4 6 小时处理时间。为此，l o m b a e r t 1 7 】提出了层次式带状g r a p h c u t s ， 用于减少g r a p hc u t s 在分割海量数据时的内存开销和处理时间。l o m b a e r t 首先对原始 图像进行下采样【2 5 】得到较低分辨率图像，用g r a p hc u t s 对低分辨率图像进行分割， 并将分割结果投影到较高分辨率的带状区域中，逐级在较高分辨率图像的带状区域中进 行分割，直至得到原分辨率图像的分割结果。l o m b a e r t 的实验结果表明4 或8 的下采样 率既能取得明显地降低内存开销，又能显著地减少运算时间，该采样率几乎可以达到实 时处理。 x u 等【1 2 】将g r a p hc u t s 和主动轮廓方法( a c t i v ec o n t o u r ) 相结合，用g r a p hc u t s 的分割结果控制轮廓的演化。由于g r a p hc u t s 具有全局寻优能力，因而两者结合使轮 廓演化可以避开局部极小值，且能产生光顺的演化轮廓。 i j i 等 2 6 1 将2 dg r a p hc u t s 扩展为3 dg r a p hc u t ，并用来分割视频物体。当图表 示图像时，节点间只是平面类型连接，即相连的节点位于同一平面内，而当图表示视频 时，节点间连接包括帧内和帧间两种类型。节点的先验能量和连接能量的构造方法与文 献1 6 1 相似。文献【2 6 】为了减少节点数量，对每帧图像用水坝法( w a t e r s h e d ) 2 5 ，2 7 , 2 8 】 进行预分割，且将视频分割为2 5 3 0 帧的视频剪辑。由于g r a p hc u t s 方法的固有缺 陷，利用3 dg r a p hc u t 进行视频分割后需进行多次局部细化操作，3 dg r a p hc u t 方法 最致命的问题是其处理时间过长，导致分割结果不能实时地反馈给用户，针对该问题， 本文提出了一种层次式3 dg r a p hc u t 方法。 浙江大学博士学位论文 7 b o y k o v 和k o l m o g o r o v 1 1 】最近又将g r a p hc u t s 和曲面演化相结合，从而把图论 与偏微分方程p d e ( p a r t i a l d i f f e r e n t i a l e q u a t i o n ) 结合起来。在以往的研究中，几乎没 有人将图论和偏微分方程相结合，他们的工作无疑开创了g r a p hc u t s 的又一个新的研 究热点。 理论上讲，g r a p hc u t s 的时间复杂度为o ( 舻) 为图节点数) ，但在将抠像( 分 割) 问题表示为基于图表示的最大流最小割问题求解，g r a p hc u t s 在多项式时间内 可完成【1 0 】。文献【1 0 】中比较了d i n i c 算法、高优先级p u s h - r e l a b e l 算法和先进先出 p u s h - r e l a b e l 算法在图像分割、图像恢复和立体重建方面的应用。 1 2 3 硬抠像与图像分割的关系 硬抠像和图像分割既有联系，又有区别。硬抠像是要从图像中尽可能完整地提取用 户感兴趣的物体，而图像分割是在明显可区分位置把物体与周围环境分离开。 图像中包含着大量的有用信息，图像分割技术可以帮助人们提取这些信息。代 表性的交互式图像分割方法有智能剪刀( i n t e l h g e n ts c i s s o r ) 【2 3 ，2 4 】、主动轮廓法 ( a c t i v ec o n t o u r ) 2 9 , 3 0 】、水平集法( l e v e ls e t ) 3 1 ，3 2 , 3 3 , 3 4 、均值漂移法( m e a n s h i f t ) j 3 5 ，3 6 , 3 7 , 3 8 1 ，n o r m a l i z e dc u t 3 9 , 4 0 】等。下面对这几类方法进行讨论。 【a )( b ) 图1 6 智能剪刀。( a ) 、图中的白色轮廓线是智能剪刀的分割结果，白色空心小圆圈是种子点。 由于边缘点多为二阶导数零交叉点，其能量比相邻点的能量小，因而在局部窗口中 各点到种子点的最小能量图呈现“总线”结构，其中边缘为代表低能量的“总线”， 从而在交互过程中自动勾勒出边缘。基于上述思想，m o r t e n s e n 2 3 ，2 4 】提出了一种交 互式图像分割方法一智能剪刀。该方法定义p 、g 两相邻象素点的能量e ( p ，q ) 为q 点的梯 度，g ( 口) 、p g 的梯度方向，d ，g ) 、及口点二阶导数零交叉值丘( q ) 三项的加权和，如式 ( 1 3 ) 。用动态规划法确定从种子点到交互位置的边界，如图1 6 所示。 e ( 鼽g ) = w g 尼( g ) + w d 如0 ，q ) + “如五( 口)( 1 3 ) 8第一章绪论 其中w g 、w d 、w z 为相应项的权值。 活动轮廓法【2 9 , 3 0 】也是一类典型的交互式分割方法，预先在物体位置附近指定初 始轮廓，使初始轮廓沿能量降低方向演化，直至接近物体边界。活动轮廓法所依赖的能 量包括变形能量( 内部能量) 和约束能量( 外部能量) 。变形能量使边界尽可能光滑，约束 能量使轮廓尽可能靠近物体边界，如式( 1 4 ) 所示。式( 1 4 ) 的能量函数用c ( p ) ( 参数曲 线) 表示活动轮廓，区间【o ，1 】表示整个轮廓。 ，1，l，1 e ( c ) = o i o ) 1 2 却+ 卢i c ”o ) 1 2 却+ a i g ( v l c ( p ) d d p ( 1 4 ) j oj 0j 0 其中n 、卢、，y 是调节系数。式( 1 4 ) 的前两项是变形能量，第三项是约束能量；g 为边界 检测函数，通常取g ( 8 ) = 南。 水平集法【3 4 ，4 1 ，4 2 】用高维隐式函数表示曲线曲面，是一种基于水平集从初始 轮廓向内或向外进化的交互式图像分割方法。水平集法在分割时需要给定初始轮廓， 如图1 7 ( a ) 所示，然后沿水平集法线方向进化，如图1 7 ( b ，c ) 所示，直至达到稳定状态 为止，如图1 7 ( d ) 。水平集方法的分割结果与初始轮廓有关，且容易受到局部极值的影 响，如图1 7 ( d ) 中右上角部分，另外，水平集法适合分割一些细节较少，物体相对突出 的图像。 (a)(b)( c )( d ) 图1 7 水平集法分割腿部切片。( a ) 、( b ) 、( c ) 、( d ) 是四个不同时刻的分割结果。 均值漂移法( m e a ns h i f t ) 3 5 ，3 6 , 3 7 , 3 8 , 4 3 】是一种非参数式分类技术，在核空间根 据密度对数据进行分类。它可以处理高维复杂数据，不需要人为干预分类过程，具有良 好的聚类能力，因而被应用在图像和视频分割问题。 均值漂移法使用各向同性的核密度描述聚类，核的大小( 带宽) 在分类操作前事先 设定，由于不同的类具有不同的局部特性，等大小的核不能很好地表示不同的聚类。 w a n g 等【3 5 】提出了一种各向异性的核密度表示方法，它能够自适应地调整核密度大 小、比例和方向，优于各向同性核的聚类能力。均值漂移法在处理图像和视频分割问题 时需定义数据间的距离( 通常是基于内积定义) 和核带宽。数据间的度量距离须考虑图像 浙江大学博士学位论文