（计算机应用技术专业论文）一种基于迭代分割抠图算法的研究与改进.pdf

摘要 数字图像抠图技术是指把任意形状的前景物体从图像中分割出来的一种技术，如今 它己经成为影视特效等多媒体制作中不可或缺的关键技术，因此该技术具有巨大的商业 价值。但是，现有的抠图技术难以同时满足人们在数字图像抠图的速度和效果两个方面 的需求，同时，它又难以对自然界存在的大量的颜色变化比较剧烈的复杂图像进行抠图 处理。本文针对现有的数字图像抠图技术存在的问题，就如何提高分割速度和改善最终 抠图效果两方面进行了研究。 首先，本文针对g r a bc u t 算法中所使用的数学模型和数学公式进行研究，对其中一 部分不利于实现，或者计算量较大的部分，在不影响最终效果的前提下，采用其它公式 或模型对其进行替代，在此基础上对原算法进行实现。在高斯混合模型的初始化聚类方 面，引入了二叉树颜色量化算法进行聚类，相较其他算法取得了更好的迭代分割结果。 在迭代计算方面，本文针对高斯混合模型组件在迭代过程被吸收的现象提出并实现 了迭代过程中的重新聚类与混合聚类的方法。相比原算法的迭代过程，这种方式一方面 加速了迭代过程中的收敛速度，另一方面迭代后的结果与前相比更佳符合分割的要求。 最后，针对g r a bc u t 算法中，对于平滑项的处理是局部收敛的，每次进行计算只 是针对每个正在处理的像素点以及与其相邻的几个像素点进行处理的，因此整个迭代最 小化是局部收敛的，因此，在本文中，利用互异点对对最小化迭代进行全局上的约束。 关键词：交互式分割图分割图像编辑前景提取a l p h a 计算初始化高斯混合模 型 a b s t r a c t d i g i t a li m a g em a t t i n gi st oe x t r a c tt h ef o r e g r o u n do b j e c t sw i t ha r b i t r a r ys h a p e sf r o ma l l i m a g e i ti sa ne s s e n t i a lt e c h n i q u e t om a k es p e c i a le f f e c t si nf i l ma n dv i d e op r o d u c t i o na n d h a se n o r m o u sp o t e n t i a lc o m m e r c i a la p p l i c a t i o n s t h ee x i s t i n gi m a g em a t t i n gt e c h n i q u e s c a l l t s a t i s f yt h ei n c r e a s i n gn e e d sf o rs p e e da n de f f e c t so fm a t t i n gs i m u l t a n e o u s l y t h i sp a p e r p r o p o s e so p t i m a la n dd e v e l o p e da l g o r i t h m sf o rg r a bc u ta l g o r i t h m s 。 f i r s t ，r e s e a r c ht h em o d a la n df o r m u l ao ft h eg r a bc u ta l g o r i t h m w i t hn o ti n f l u e n c i n gt h e r e s u l to ft h eo r i g i n a la l g o r i t h m ，i m p r o v e dap a r to ft h em o d a la n df o r m u l ao ft h eo r i g i n a l a l g o r i t h m a n dw eq u o t et h ec l u s t e r i n ga l g o r i t h mo fc o l o rq u a n t i z a t i o no fi m a g e st od e a lw i t h t h ei n i t i a l i z a t i o no fg m m c o m p a r i n gt ot h eo t h e ra l g o r i t h m ，w ew i l lg e tab e t t e rr e s u l t s e c o n d ，i nt h ep r o c e d u r eo fi t e r a t e dc o m p u t i n g , t h i sp a p e rp r o p o s e st h er e i n i t i a l i z i n go f g m ma n dt h em i xi n i t i a l i z i n go fg m mi nt h ep r o c e d u r eo fi t e r a t e dc o m p u t i n gt od e a lw i t h t h et h i n gt h a tt h ec o m p o n e n to fg m md i s a p p e a ri nt h ep r o c e d u r eo fi t e r a t e dc o m p u t i n g c o m p a r i n gt ot h eo r i g i n a la l g o r i t h m ，t h i sm o d ew i l li m p r o v et h es p e e do fc o n v e r g e n c ea n d t h el a s tr e s u l to fs e g m e n t a t i o n t h i r d ，i no r d e rt od e a lw i t ht h ep r o b l e mt h a tt h em i n i m i z a t i o na l g o r i t h mp r e s e n t e di ng r a b c u tp a p e rw h i c h o n l yd e a lap i x e la n dt h ep i x e l sa r o u n di ti ne a c hc o m p u t i n g , o n l yg u a r a n t e e s c o n v e r g e n c et oal o c a lm i n i m u m ，w ep r e s e n tam e t h o dt or e s t r a i nt h eg l o b a lm i n i m u mb y u s i n gi n t e r - d i f f e rp a i ro fd o t k e yw o r d s ：i n t e r a c t i v ei m a g es e g m e n t a t i o n ，g r a p hc u t s ，i m a g ee d i t i n g ，f o r e g r o u n d e x t r a c t i o n ，a l p h am a t t i n gi n i t i a l i z a t i o no fg m m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得 墨盗墨墨盘堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名： 枷甩 签字日期：2 确月扩日 学位论文版权使用授权书 本学位论文作者完全了解 叁盗墨墨盘堂有关保留、使用学位论文 的规定。特授权叁盗墨墨盘堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 孙毛 导师签名： 致晔 签字日期：翮7 月驴日签字日期：6 p 占年1 月l 扩日 第一章绪论 第一章绪论 本章结合今年来娱乐界和影视界的发展情况给出了数字图像抠图( d i g i t a li m a g e m a t t i n g ) 和图像合成的基本概念。接着对这两种技术近年来的研究与发展情况进行了 简要的介绍。如何在复杂背景下( 例如自然图像) ，高效、快速地进行图像的抠图操作， 已经成为当前计算机图像和视觉研究领域的一个热点和难点。在本章的最后一部分，对 本文的研究工作以及文章的组织结构进行了阐述。 i i 引言 随着人类社会的发展和进步，人类日常生活的各个角落充满着各种各样的信息。由 于计算机硬件飞速发展、数学以及计算机理论的不断取得突破，数字图像处理和计算机 视觉技术也得到了前所未有的快速发展。借助于这些技术，人们可以制作出五花八门， 绚丽多彩的多媒体特殊效果来达到宣传、娱乐以及艺术创作的目的。其中图像分割是图 像处理的主要问题，也是计算机视觉领域低层次视觉中的主要问题。传统的图像分割是 把图像划分成若干互不交叠区域的集合。这些区域要么对当前的任务有意义，要么有助 于说明他们与实际物体或物体的某些部分之间的对应关系 1 。图像分割的应用十分广 泛，几乎出现在有关图像处理的所有领域，并涉及各种类型的图像。例如在医学中讲核 磁共振图像中特定的器官分割出来，用于疾病的诊断；在遥感图像中将农田分割出来用 于估计农产品的产量等等。数字图像抠图作为图像分割中的一种，近年来得到了广泛深 入的研究。从它的发展历史来看，这门技术能够得到持续发展的最主要的原因在于电影 特效制作以及照片特效制作的需要。利用这些技术，电影导演可以在真实场景中无缝隙 地插入需要的物体，还可以把演员送到计算机生成的虚拟场景。几乎所有的现代电影制 作都用到了数字图像抠图和图像合成技术，最有名的例子包括“星球大战”，“侏罗纪公 园”，“黑客帝国，“魔戒三部曲”以及“哈里波特历险记”等等。图像精细分割与图像 合成技术的重要性已经完全由这些影片令人惊讶的上座率体现出来了。根据网站“t h e i n t e r n e tm o v i ed a t a b a s e 的统计数据，截止20 04 年4 月，最卖座的1o 部电影 中有6 部获得了“最佳视觉效果奖 。可以说，这些电影之所以取得成功，很大程度上 依赖于它们那令人惊叹的视觉效果，而这些效果的制作，应该归功于数字图像抠图与图 像合成技术的有效运用。因此，数字图像抠图和图像合成技术都具有巨大的商业价值。 另外数字图像抠图与图像合成也广泛应用于现在的媒体制作当中，包括杂志，二维艺术 与图形，电视，广告，视频以及多媒体标题制作等等。 尽管数字图像抠图与图像合成技术拥有如此巨大的商业价值，它的出现和发展也由 第一章绪论 来已久但直到今天，这项技术依然还有很多地方值得研究。最近几年不少的研究人员 对数字图像抠图技术进行了深入的分析与研究，提出了各种各样行之有效的数字自然抠 圈算法。有的算法处理速度快可以满足及时性、实时性方面的要求，但是由于算法自 身的限制这些方法往往只能在相对简单的背景条件下执行，并且所得到的结果有一定 的局限性。有的算法效果方面可以令人满意，可以满足一些背景部分相对比较复杂的图 像的精确分割的要求，但依然由于算法的限制，算法的处理速度往往不能令人满意。因 此，如何在复杂背景下( 例如自然罔像条件下) 高效、高速地对图像进行处理仍然是 当前计算机图像和视觉研究领域的一个热点和难点。 1 2 课题研究的意义 一幅图像中的自然景物如树叶和毛发，其所占的位置通常会比一个像素的大小还笺 细小如图i1 所示。这样便使离散的数字图像在图像中的前景与背景的交界处上的大 量像素点所获得的颜色值并不一定足由单一物体所反射的光线所获得的。另外，一些包 含半透明物体的图像中的半透明物体，例如：云彩，玻璃杯等等，即使是在前景物体( 云 彩、玻璃杯) 的内部，但这时候，在这些前景物体的像素点所包含的像素的颜色值也 不仅仅是受前景物体所左右，也就是说这些像素的颜色值同时包含了前景物体以及背 景中的色彩。对于这些景物的分离，传统的图像分割则会变得无从下手。这个时候，这 些问题便需要基于透明度( 同时也称作a 1 p h a 值) 的数字抠圈技术( m a t t l n g ) 来对其 进行相应的处理，这些方法可以对某个确定像素点，对同时对它颜色值产生影响的前景 色彩与背景色彩的颜色值进行分离。山于这些方法的特性，这些方法被广泛地应用于电 影特殊处理以及照片艺术处理等各个领域。 ( a ) 毛发( b ) 毛皮 嘲1 1 通常的幽像升割方法无法对例如毛发的细小部分进行精确的分割 简单柬说，数字罔像抠图技术指的足把任意形状的前景物体从图像中的背景部分的包嘲 巾抽取m 束的种技术，而蚓像的合成，则蛙指把抽取出术的罔像的前景物体部分与另 第一章绪论 一幅只包含背景部分的图像相结合，将其合成为一幅新的图像。从卜面的捕述我们可以 看出，数字图像抠图技术与图像合成技术是一对互逆的圈像处理操作，如图1 2 所示 这些技术的发展是基于电影产业的繁荣而发展起来的。1 9 8 4 午p o r t e r 和d u f f 2 1 首 先将a l p h a 通道的概念引入了数字图像之中柬并提出了著名的台成公式： cz a f + ( 1 一n ) 占 其中，对于r 、g 、b 某一个通道束说，c 表不该通道上某一像素的颜色值，f 表示 这像素在设通道上的前景物体的颜色值，b 表示这像素在该通道上的背景值，o 表 示质疑像素在设通道上的a 1 p h a 值。通过该公式我们可以得知，图像中的每一个像素点 的颜色值都是山它的前景颜色、背景颜色以及a l p h a 值三者所共同决定的。 a 的大小取值在 0 ，1 之间。通过公式11 我们可以知道，当图像巾的某一像素点 的at p h a 值a = 10 的时候，则表明陵像素点处于完全不透明的状态，即此时该像素点的 颜色是前景颜色；当像素点的a l p h a 值a = o0 的时候，则表明该像素点处于完全透明的 状态，即此时该像素点的颜色是背景颜色；当像素点的a l p h a 值。在0 和l 之间且不等 于0 和l 的一个小数的时候，表示该点处于半透明的状态，此时该像素点的颜色由日口景 颜色f 和背景颜色b 按照上面所提到的合成公式按a 1 p h a 值n 混合计算而成。 a ) 处理前的原图 ( b ) 提取小前景后重新和成的削片 酗1 2 数字幽像拒田与图像合成 1 3 数字抠图方法的研究现状 数字抠图技术大致经历了光学图像处理和数字图像处理两大发展阶段。，随着数字 科技技术的发展，光学场景分割与合成技术已经在很大程度上被数字图像抠图技术与数 字圈像合成技术所替代。在计算机和并种专用软件的帮助下，数字图像报| 璺| 技术与数字 图像合成技术已经可以完全完成光学场景分割与合成的绝大部分丁作，它使图像分割与 图像合成的工作变得更加简单、可靠和高效。 数字图像抠图技术的发展历史其历史可以大致分为两个阶段 单一背景的数字图像抠图技术( 蓝屏抠图或绿屏抠图) 复杂背景的数字图像抠图技术( 自然图像抠图) 函垴 a ) 单一背景图片( b ) 复杂背景图片 图1 3 两种数字削像抠圈l 勺输入幽片 1 31 单一背景的数字图像抠图技术( 蓝屏抠图或绿屏抠图) 根据数字图像抠图技术的定义，当图像的背景部分的颜色值b 为给定的固定值的时 候，那么这种数字图像技术就属于单一背景的数字图像抠图技术( 蓝屏抠圈或绿屏抠 圈) 。之所以单一背景的图像抠图技术义被称为蓝屏抠图( 或称为绿屏抠图) ，其原因在 于早期的抠图方法通常将需要提取的图像的前景部分放到一个同定的蓝色( 或绿色) 的 屏幕的背景当中去，然后通过固定的背景颜色值，分别在r 、g 、b 三个颜色通道上对 前景部分的颜色值进行估计，然而这些分量值的估计通常需要人工的相关操作，来肘估 计的过程进行相应的干预。当然，由_ f 这种固定背景颜色值的方法以其简单、实用以及 它的高教性，被厂泛地应用于早期的电影叶1 活动物体以及图像中1 j 景部分的图像抠罔技 图像台成。 a ) 蓝辟抠幽输入图片( b ) 台成结果幽片 幽l 4 监屏抠幽的输入与输出 靛辟图像抵图技术的具体进行步骤如下述内容所描进，首先，将所需要们作为前量 的运五i j 物体胃十蓝屏( 或者绿群) 订址j - ：抽下组连续的影片。然后埘影”巾的符一 第一章绪论 幅图片进行单一背景图像抠图的图像处理，由于是置于固定的蓝色( 或绿色) 背景中， 所以背景颜色的颜色值便为已知了，所以通过已知的背景颜色将活动物体的前景颜色的 颜色值和它的透明度a l p h a 值提取出来，从而达到图像抠图的目的。然后再将得到的活 动物体部分与所需要背景部分进行图像合成处理，得到一些列新的图片，从而达到使活 动物体置于目的背景中的目的。例如早期的西游记、星球大战以及最近的影片功 夫等都用到了这种技术。 单一背景抠图( 或称为蓝色抠图或绿屏抠图) 是把所需要提取的前景物体放置在已 经固定了的已知颜色的背景前面进行摄影，根据r g b 的三个颜色通道，根据公式 l 2 口，+ u 一口户分别列出合成公式，建立方程组，对前景物体的颜色进行求解，在未 固定背景颜色的时候，在三个通道上分别列出的三个方程所组成的方程组，共有7 个未 知数组成，分别为a l p h a 值，前景颜色分别在r 、g 、b 三个通道上的分量值，以及背景 颜色分别在r 、g 、b 三个通道上的分量值。现在将背景颜色值固定，则已把未知量的个 数缩减为4 个，分别为前景颜色值在r 、g 、b 三个通道上的分量值，以及a l p h a 值。尽 管如此，缩减后的未知数的个数仍然大于所列出的方程组中的方程个数，因此在这个方 程组的基础上仍然不能对目标求取确切的解。因此为了得到一个可行的解，我们还需要 对蓝屏抠图问题进行进一步的约束限制。作为这个领域的先行者，v l a h o s 2 2 ，2 3 3 等人 提出了一个比较简单的约束条件，并且在该条件下使得无定解的目标方程组，在约束下 得到一个可行解。另外，s m i t h 和b 1i n n 的论文 2 4 中，对利用上述方程组进行蓝屏抠 图的各种可能的界的情况进行了详细的分析。在v l a h o s 的蓝屏抠图方案中，在假设前 景颜色在红、绿、蓝各个颜色通道上的颜色值的分量大小的相对比例是已知的条件下， 并且满足下列约束 0 5 s a 2s 瓦s a 2 ( 1 - 2 ) 通过上述约束推出每一点的a l p h a 值的计算公式为 口= 1 一口( q 一口：q ) ( 1 - 3 ) 其中，g 和c ，分别是所要处理的输入图像在蓝色通道和绿色通道上的颜色值的分 量值，而a ，和a ，则是由用户控制输入的参数。在原来的由三个方程组成的方程组的基础 上，加上方程( 卜3 ) ，则方程组中方程的个数变为4 个，因此可以通过新的方程组，即 增加用户添加的约束方程后的方程组，解除目标方程组的唯一解。当然，因为控制约束 方程的两个参数a ，和a ：是由认为自行输入的，因此无法保证输入一次参数便能得到令人 满意的抠图结果，因此，用户需要通过不断调节输入参数a ，和a ，的大小，来对抠图结果 进行调整，直到获得一个能够令人满意的抠图结果为止。这种通过参数调整的方法虽然 构造简单，并且易于实现，但是需要一个有经验的专家来进行参数的调节，因此需要很 第一章绪论 高的调试技巧才能在能够令人忍受的时间范围内得到令人满意的结果。并且，该算法的 鲁棒性较差因此利用该算法可能无法将一些简单的物体从单一的背景中提取出来，再 有，这种方法无法从数学上得到该算法有效性和可行性的理论基础。 m i s h l 哪 2 5 提出了一种基于代表性的前景和背景颜色样本的蓝屏分割的改进方 法。首先，该方法首先把图像分割成为前景区域，背景区域和未知区域三个部分。被划 分为这样三个区域的图像我们称之为二分图( t r i m a p ) 。由用户指定其中背景区域和前 景区域中的部分样本点作为代表前景部分和背景部分的特征样本：其次在颜色空日j 中， 构造两个相似多面体，其中一个多面体尽可能小f 目能够包含全部的背景点，另个多而 体则尽可能人但包含全部的背景点和未知区域的点，计算出所有背景点的颤色平均值b ： 接着。对于未知区域中的点c 过c 点和背景均值点b 做直线，分别交两个多面体于b ， f 点，线段8 c 占b f 的长度比例就是c 点的“值，如图15 所示。该方法需要用户指定 前景和背景样本点，但它对背景的要求相对较少。 a ) 图片中的像素划分 ( b ) 拒图方法示意图 酗1 jm i s h i m a 监屏抠图方法 1 32 早期的复杂背景下的数字图像抠图技术( 自然图像抠图) 鉴于单一背景的局限性和依赖性，需要固定背景颜色值对预处理图片有较高要求。 人们迓渐对复杂背景下的精细分割越来越感兴趣。当身边缺少特制的背景幕时我们可 能就需要从一张具有任意背景的图像中获取它的n 值，此时自然图像抠图问题的束知数 达到了7 个。这种数字抠图技术就叫做复杂背景下的数字图像抠图。复杂背景的数字图 像抠圈是一种更加困难的分割技术。 r o t o s c o pj n g 是一种普遍使用的复杂背景下的数字图像抠图技术，但是这种技术过 分依赖操作人员的经验，同时丁作量相当大，但最终所得到的抠图效果却不够好。 m i t s u n a g a 等人提m 了种a u t o k e y 的数字抠目方法，这种办法被用束改进r o t o s c o p i n g 过程。在陵方法中通过r o t o s c o p in g 过程可以得到每帧中前景物体的边缘曲线，为 了能够得到卫加精确的| 冬| 像，需要进行少鞫 业于工 作束校证每帧的边缘曲线。 荡 第一章绪论 以往的方法只是简单使用羽化操作来获得半透明的a 图像，a u t o k e y 方法采用了一种自 适应的羽化方案。假设图像中的前景颜色f 与背景颜色b 的变化很小，可以推导出a 图 像中前景物体边缘的透明度变化程度和该处的图像梯度的大小有关。但该方法对前景和 背景的颜色做了很强的限制，使得a u t o k e y 比较适用于前景物体的边缘比较“硬 的情 况，而不适用毛刺比较多的复杂边缘。 随着对复杂背景下数字图像抠图算法研究的不断深入，最近几年又出现了许多不同 的复杂背景的数字图像抠图方法，主要有k n o c k o u t 方法 2 7 ，2 8 ，r u z o n 方法 2 9 ， h i l l m a n 方法 3 0 ，b a y e s i a n 方法 3 1 j ，p o i s s o n 方法 3 2 ，f l a s hm a t t i n g 3 3 方法以 及在这篇文章中我们所研究的g r a b c u t 方法。在复杂背景的数字图像抠图方法中，由于 大部分方法是基于三分图而发展出来的，所以适量的手工交互是必要的。基于三分图的 复杂背景的数字图像抠图基本上可以分为区域划分、颜色估计与a l p h a 估计这三个步骤。 以上的几种方法中，大部分方法都是基于三分图的方法，因此事先都需要把图像分割成 三个部分，即首先需要创建三分图( t r i m a p ) ：前景区域、背景区域和未知区域，然后求 未知区域中各点的前景色成分和a l p h a 值。前景区域，背景区域和未知区域之间的分界 线称为前景轮廓线和背景轮廓线。作为这些数字图像抠图方法当中重要的唯一的手工操 作，轮廓线在图像中的具体位置，由于人工操作的局限性，无法对轮廓线在图像中的具 体位置做到一个量化的限制，即每次的轮廓线划分无法完全保证所有轮廓线的一致性， 也就是对于三分图( t r i m a p ) 的构筑，会形成不同的结果，这无疑对数字图像抠图的效 果有着很大的影响，因此区域划分时必须十分仔细，保证前景轮廓线内的点全部为前景 点，背景轮廓线外的点全部为背景点，不能有交叉，在此基础上，未知区域应尽量小。 下面将分别介绍一下这几种分割方法。 首先，我们对k n o c k o u t 方法，r u z o n 方法，h ill m a n 方法以及b a y e si a n 方法这些 相对较早期出现的方法进行一下大体的介绍。 ( 1 ) k n o c k o u t 方法 区域分割完毕以后，对未知区域中的任一像素点c ，k n o c k o u t 方法 2 7 ，2 8 利用和 c 邻近的前景轮廓线上的像素点的颜色的均值作为它的前景色分量，类似的，可以得到 背景色分量；接着修正背景色，然后根据得到的前景色和背景色分量以及像素点c 的颜 色值来推断该点的a l p h a 值。其步骤如下：首先，找到距离c 点最近的背景轮廓线上的 点，设这个最近距离为d ，然后找到轮廓线上所有距离不大于2 d 的点；给这些点赋权值， 距离为d 的点的权值为1 ，等于2 d 的点的权值为o ，处于二者之间的各点的权值依次按 照线性比例减小；算出这些轮廓线上的像素点的颜色值的加权平均值b ，前景轮廓线上 的点的处理与之类似，同理得到前景边界点的加权均值f ，如图2 6 ：在r g b 颜色空间中， 过b 点做平面使该平面垂直于线段f b ；过c 点做垂线垂直于平面，并交平面子b 点， 第一章绪论 则b 点就是所求的拶点的修正值；求得b 点以后，再分别把线段f b 和b c 投射到颜色空 间中的三个轴上，假设b c 的投射线段占f b 的投射线段的长度在三个轴上的比值分别为 乱，4 s 和。并分s l i 以f b 的投射线段的长度作为他们的权值，算出4 4 。和4 。的加权 均值就得到c 的a l p h a 值。我们称k n o c k o u t 方法的这种a i p h a 估方法为通道加权 法。如图16 所示。从k n o c k o u t 方法的颜色估汁方案可以看出，该方法只适用与光滑 图像的抠图。当图像比较复杂时，它估计出来的前景和背景颜色成分误差很大，不能进 一步用来估计，这是该方法明显的缺点；但是由于算法简单，所以运算速度很快。 张 5 0 0 x 5 0 0 的图像在不到1 秒的时间内就可以处理完毕。 ( 2 ) i t u z o n 方法 a ) 图片中的像素划分( b ) 抠图方法示意圈 幽1 6 i c m o c k o u t 拒图方注脚例 r u z o n 的方法则是采用了统计学的方法柬估计a l p h a 值f 2 9 。它的丰要处理步骤如下所 不： 首先，把未知区域划分为一系列子区域，对每个予区域作一个矩形刚好包围该子区 域，矩形内的前景和背景点作为统计样本，如图l7 所示 其次，对矩形内的前景样本和背景样本点按照文献 3 3 的方法进行颜色聚娄，假设 分别为m 个和n 个类，前景样本的m 个类和背景样本的、个类再进行两两配对，合计共 有有m x n 个配对，而每个类中的像素点的颜色值在颜色空b j 中服从无向高斯分布 ( u n o r i e n t e dg a u s s i a n sd j s t r i b u t i 0 1 3 ) ； 再次，在这些配对当中，剔除掉产生“相交冲突”( i n t e r s e c t i o ng o n f l i c t ) 和“角 度冲突”( a n g l ec o n y l i c t ) 的配对。所旧“相交冲突”就是指两个配对( 两条线段) 在颜 色空间中的距离小于某个阀值，而“角度冲完”即指拥有共同端点的两个配对的兆角小 于l o 度： 蛙席埘r 每个配对，它的时最羊背景类服从的丹朽的中心点分别为对应类的颤 第一章绪论 色加权平均值f 和b 。在这个配对中，像素点c 的颜色值服从的分布为前景类和背景类 像桑点颜色值的线性插值，也就是| 兑，它的巾心点c 在线段耶卜移动，当c 的概率为 最大时，也即c 为c 在线段上的投影时，c b 与线段f 口的比值就是这个配对取得的a l p h a 值。我们称这种a l p h a 估计方法为投影法。每个配对都以一定的概率对应着一个a l p h a 值。对于待估计的像素点c ，它的所有这些配对中取到最大概率的a l p h a 值就足它的最 终所取a 1 p h a 值。 此外，在每个配对当巾，算出其a l p h a 的概率，咀哗作为权值，计算出每个配 对的f 和日的加权平均值作为像素点c 最终的f 和口。如图17 所示。 从上述步骤可以看出。r u z o n 方法的颜色估计和a l p h a 估计的计算量相当大，这导致它 的处理速度非常慢。 ( a ) 幽片中的像素划分( b ) 抠图方法示意图 目17 r u z o n 抠削方法幽例 ( 3 ) h i l l m a n 方法 2 0 0 1 年，f i l 】1 i 】a n 等人提出了个基丁主成分分析的数字图像抠图方法 3 0 。他们观察 到，对前景和背景区域细分的锥个类，他们在颜色空问中的分布为类似于雪茄形状的 长条形，这种形状使样本的协方差矩阵的非零元素乇要分辅在对角线附近，适用于主成 分分析。这可能是因为在一张图像巾，局部区域中的点只有亮度有较太差别，而色度则 基本孝目同，或者足阿种色度之间的过渡变化，( 如斟l8 所示，其中和：为前景簇在 颜色空问中的长条形的两个端点，q 和。z 则是背景簇的两个端点，c 是未知区域中的 一点) 。h i l l m a n 方法分别找出自u 景( 线段：) 和背景( 线段。- 。：) 卜离点c 最近的点f 和占，线b i c b 在线段f b 上的投影c b 占线段f 日的比例就是所求的a 1 p h a 值。把向 量c c 加到f 上，得到的点f 就是所求的前景点。当前景或者背景l l 存在某些不_ f 常的 点离各自主轴的距离比点c 离卡轴的距离较远时，这种方沾就不适用了。钊对这种情况， h i l l m a n 对算法进行了修f ，对这些不正常的点，把它们作为c 服从的分布的样本来考 虑。i i l m u n 算法的汁算量出很大，从它a l p h a 计算步骤可以看出，它使用的也足投尝 法。 爹一每 h i l l r n a n c 与 a ) 削片中的像素划分( b ) 抠幽方法示意酗 削1 8 h i l l m a n 抠蚓方法目例 ( 4 ) b a y e s i a n 方法 同样是2 0 0 1 年，c h u a n g 等人提出了一个基于贝叶斯框架的数字图像抠图方法 3 1 。 与以前的方法利用光栅扫描顺序来逐个处理每个像素不同，该方法率先利用处理过 的点的结果来估计当前点，处理的顺序是先处理未知区域外部的轮廓线线附近的点， 然后像剥洋葱似的逐圈向内处理未知区域内部其他的点如图1 9 所示。和文献 2 9 的方法有点类似，其处理步骤简单描述如下： 取样窗口为滑动的圆窗口，而不是文献 2 9 的矩形窗口，大小可变，以保证圆 内包含一定的前景和背景的样本点，处理过的点所得到的结果被应用到后面尚未 处理的点的估计中去； 在建立样本分布时，它利用了己经处理过的点的结果，认为样本点的分布为 有向高斯分布( o r i e n t e dg a u s s i a n s ) ，而不是采用r u z o n 的无向高斯分布和 h i l l m a n 的p e a 分析； 在利用r a p 法则求产生虽大概率的f 和日时，利用偏微分推导概率密度函数 的极值，而后通过解一个六元线性方程组求得极值的条件，即可求得，和b ； 利用求得的f 和四用投影法求得a 。为了使线性方程组可解，b a y e s 方法 以圆邻域内的己知点( 包括处理过的点) 的8 的加权平均值作为初始值赋给系数 矩阵中的n 。 第一章绪论 b a v e s i a n a ) 幽片巾的像素划分( b ) 抠目方法示意阿 圉l 9b a y 幅h n 抠图方法图例 c h u a n g 3 1 定义了对数概率工( c l ，b ，口) ，( ，) 和l ( 日) ，但没有定义工( 口) ，而是 简单地假定其为常数。当前景和背景的颜色比较接近时，这种假设就会出现问题。因为 没有了d 的先验知识，当f 和b 比较接近时，用投影法求。将带来极大的误差。c h u a n g 在文献 3 4 中介绍了对这个问题的进一步研究提出了一种基于马尔可夫场的l t a ) 定 义方法，在一定程度上弥补了这个缺陷。c h e n 3 5 也介绍了忙，的一种定义方法然 后用b a y e s i a n 方法专门束解决灰度图像的精细分割问韪。s h u m 3 6 也探讨了婶j 的定 义问题，提出了一种相关性数字图像抠图( ( c o h e r e n c em a t t in g ) 的方法。他们在一种叫 弹出式光场( p o p u pl i g h tf i e l d ) 的基于图像的绘制系统中用这种方法来构建相关性图 层。 从图19 可以看出，b a y e s i a n 分割方法实际上是要在r g b 空间中求得c 点到线段邝 的欧式距离正，f 点到f 点的马氏距离4 2 ( m a h a l a n o b i sd i s t a n c e ) ，b 点到口点的马 氏距离4 ，的平方和的最小值。k a r h a nt a n 对b a y e s i a n 数字图像抠图方法作了一些改 进，提出了一种快速数字图像抠图算法 3 7 。他假设线段，口经过c 点，这4 - 。”，把 b a y e s 抠图的框架简化为求4 ：+ q 的晟小值，并提出了一个快速求解晟小值的近似方法。 凌方法通过分别做r g b 颜色空间到前景和背景协方差权重空间的映射，假设映射后的 线段c f 和c b 与映射前的线段耶共面，可以求出4 z + 4 ，的最小值。线段f b 在很多情 况下并不经过c 点从其推导过程可以看出，在求4z + 如最小值时所做的假设也不合理。 因此，这种快速图像分割方法尽管可以在数秒内得 u 一张图像的精细分割结果，但其效 果并不理想。 上面所讲的这四个方法都是在三分图的基础上构建出柬的，即这些方法都是在得到 三分图之后，再对两条轮廓线中间所包围的未知区域中的像素点进行数字图像抠囤处理 的，因此这些方法不但需要较大的人工交互工作，而且在得到三分图后，对三分图中的 未知区域进行处理的时候，需要对整幅图像中的像素点，根据三分图划分操作中所标示 的两条轮廓线进行点在多边形内外的处理，因此，在抠图方法中所使用的点在多边形内 外的判断算法的效率对这个算法的效率会产牛很人的影响。 篓 第一章绪论 1 3 3 点在多边形内外算法简介 多边形在计算机图形学中的应用，一般要求他们具有以下性质：( 1 ) 封闭性：任何 一条边有且只有两个端点，每个端点都是两条边的交点；( 2 ) 不自交：任何两条边只有 在相邻的情况下才相交，并且交点就是边的端点；( 3 ) 有向性：任何一条边都有方向， 并且边的方向一致。 在点在多边形内外的判定算法中会用到多边形的一些基本概念，下面我们将这些概 念进行一个简单的介绍： 定义1多边形：多边形式一个首尾相连的多边线，它可以用点序列昂只罡”z 表示， 昂置，号昱，只一只，昂称为多边形的边，昂，皇，昱，c 称为多边形的定点。 定义2 简单多边形：如果一个多边形具有以下性质： a ) 对于任意f ，层一弓，即所有的定点均不相同； b ) 任何一个顶点都属于一条边5 c ) 任何两条非相邻边都不相交， 这样的多边形，则称之为简单多边形。 在计算机图形学中应用的多边形一般为间断多边形，并且规定多边形沿逆时针方向 时方向为正，沿顺时针方向时方向为负。 形方向的判断方法进行以下介绍，给定多边形尸l 咒皇昱”以，如图1 1 0 所示，多边形 方向的判断方法的步骤如下面所示： i 遍历多边形p ，找到p 沿x ，y 方向的最大值、最小值点分别为1 t ， i l p 7 ： ppp i i 定义矢量z - ( o ，0 ，1 ) 。将只，弓，置，号的下标从小到大排序得到- | ，k ，对于下标 相同的电，不计重复的下标，只保留一个，如果只剩下两个点，转到步骤4 ，如果只剩 下三个点，则转到步骤5 ； i i i 连接弓，最：弓，弓，得到一个四边形p 。2 弓卑曰号，其中 昂2 弓，墨= 置，a 弓，只= 号，转至步骤6 ； i v 设剩下的两点为只，弓，则如果( 只一- 只鼻号+ - ) z o ，则p 的方向为正；如果 ( 只一- 皇号+ t ) 。z 0 ，则尸的方向为正，如果( 砭只e ) 。z 0 ，则p 的方向 为囟。 第章绪论 图1 加多边形及其同构凸多边形 在非退化情况下p 可以看成是将举行的包围盒去掉4 个角得到的，也就是说p 的每 个内角都t j , - 于1 8 0 。，因而是严格凸的。凸多边形的方向可以由任意两个相邻便矢量的叉 积确定。同时，根据拓扑学的知识可知，p 的方向与多边形p 的方向相同。 实际应用中的多变性是形状各异的，对上述的多变性方向判断方法而言，最具代表 性的两种特殊情况如图1 1 1 所示： 图1 1 1 两种退化情况 对于左图的情况，假设f o ，那么j p ) 就会大于，( 含) ，但通常来说，我们希望i ，p ) 是越大越 孥，因些最直观的方法是直接求得使q ( 臼) 取得最大值时的口值，那么， ) 每次迭代的 增量便会越大，如图3 2 所示。 由于q p ) 是秒的函数，我们可以把和口不相关的部分并入常数项中去，如下式表示： 2 荟n 荟3 岛妙矿b 丽1e x p ( 一盟学玛卅q k 嘲取辩h ：，一喀返乞 v 舢叫；吾翌娄塑型 想要求最佳的口，值，需要引入拉格朗日乘数( l a g r a n 毒em u l t i p l i e r ) ： ( 1 ，- - q + a ( a l + 口2 + 口3 1 ) 2 著n 荟3 岛 ) 【l n a j - d l n c r j 一垒掣】+ a + a 2 + a 3 - 1 ) 分别对口微分求导，可以得到 v q q - - o 净口，a i 一善a “) 第二章g r a b c u t 自然抠图方法的理论基础 v 一：l o 号口：a = 一善殷瓴) v - ，l o 辛口，ai 一善尾 ) 将上面三式相加，可以得到： ( 口+ 口z + 口s m 一一善【展“) + 成“) + 岛瓴) 】 a 。一v 1 。一万 智 因此，可以得到 旷孝善岛“) ，j 都，3 因此我们最后的结果可以整理如下： 岛 k 岛( 薯) 口；! 薹竺兰! 竖二竺三二竖二竺! 宝色“)一 。 驴言善岛“ 其中岛( t ) 的计算，是根据刍来进行的。因此由上述推导方法得到的结果，何前面 一部分的结果是完全一致的。由关于，p ) 一，p ) 苫q p ) 这部分的图解如下图所示： ，( 0 令、 | ( e ) 纱。 孓9 卜o 夕j ( p ) - 西 睁 图2 2 关于j p ) 一，p ) q p ) 的图解 第三章g r a b c u t 自然抠图方法的分析与初步实现 第三章g r a b c u t 自然抠图方法的分析与初步实现 图像分割是图像处理与机器视觉的基本问题之一，其要点是：把图像划分成若干互不 交迭的区域的集合，这些区域要么对当前的任务有意义，要么有助于说明它们与实际 物体或物体的某些部分之间的对应关系。自然抠图算法便是图像分割的一个特例，自然 图像抠图的目的在于将一幅图像中的前景部分与图像中的背景部分分离开来，并得到图 像中每个像素的前景值，背景值，以及图像的透明度a l p h a 值。g r a bc u t 方法正是在图 像分割的基础上，将所分割出来的前景部分与背景部分的交界处自动形成一个未知区 域，然后再在这个未知区域上对前景部分的边界进行细化以达到抠图这个最终目的的数 字图像抠图方法。本章主要对g r a bc u t 方法中的分割部分进行实现与研究。根据 r o t h e r 5 3 的方法，对g r a b c u t 方法进行实现，并在实现过程中，对原文中没有详细介 绍的实现部分给出实现过程中所用到的公式