（计算机应用技术专业论文）基于聚类和距离变换的数字图像彩色化技术.pdf

摘要 数字图像彩色化是近年来出现的一种将计算机作为辅助工具，给单色的静态图像或 视频序列添加色彩信息的技术。目前已被运用到黑白老照片、数字娱乐、教育、遥感、 医学及数字文化保护和修复等领域，具有广阔的应用前景和潜在价值。本文在对彩色化 研究现状进行分析的基础上，以静态灰度图像的彩色化为研究内容，相关工作及主要贡 献如下： 1 基于局部颜色线索扩展的彩色化 基于“像素空间距离越近，颜色越接近；像素的局部灰度统计特性与某种颜色线条 覆盖像素的局部灰度统计特性越接近，则该像素颜色越接近于对应线条的颜色”的假设， 本文提出了一种基于距离变换和初始模糊聚类的着色方法。事先由用户在输入灰度图像 中勾勒一些典型的颜色线条，然后是：各种颜色线条的提取、距离变换与空间权值估计、 初始模糊聚类、基于各种颜色线索的混合加权。基于上述局部颜色线索在整幅输入图像 的扩展，最终得到一幅彩色化的图像。 2 基于颜色传递思想的彩色化 基于分裂式分级聚类技术的高效颜色传递 针对w e l s h 算法穷尽式搜索的邻域选择以及耗时的颜色传递过程等问题，本文给出 了一种新的彩色化算法：借助分裂式分级聚类技术构建亮度特征空间的二叉树结构；基 于二叉树的最近邻搜索，实现参考彩色图像向输入灰度图像的高效颜色传递。 基于高斯金字塔的多层颜色传递和梯度修正 为了进一步提升算法的彩色化效果，本文引入多级颜色传递策略。首先，借助于高 斯金字塔，将输入的灰度图像和参考的彩色图像表示成多分辨率形式；然后，由低分辨 率向高分辨率逐层进行颜色传递；最后，基于纹理结构一致性的假设，进行颜色修正。 基于上述策略，可以得到一幅视觉效果满意的彩色输出图像。 关键词：彩色化距离变换高斯金字塔分裂式分级聚类直方图均衡化 i i i a b s t r a c t d i g i t a li m a g ec o l o r i z a t i o n , e m e r g i n gi nr e c e n ty e a r s ，i sac o m p u t e r - a i d e dt e c h n o l o g yo f a d d i n gc o l o rt om o n o c h r o m es t a t i ci m a g e so rv i d e os e q u e n c e s s of a r , i th a sb e e nw i d e l y a p p l i e di nm a n yf i e l d s ，s u c h 嬲o l db l a c k - a n d w h i t ep h o t o s ，d i g i t a le n t e r t a i n m e n t ，e d u c a t i o n , r e m o t es e n s i n g ，m e d i c a ld i a g n o s i s ，d i g i t a lp r e s e r v a t i o na n dr e s t o r a t i o n , e t c t h e r e f o r e ，i m a g e c o l o r i z a t i o nh o l d st h ec h a r a c t e r i s t i c so fp r o m i s i n ga p p l i c a t i o np r o s p e c t sa n dp o t e n t i a lv a l u e s t a r t i n gw i t hab r i e fo v e r v i e wo fe x i s t i n gc o l o r i z a t i o nt e c h n i q u e s ，w ef o c u so nt h es t u d yo f c o l o r i z a t i o nf o rs t a t i c g r a y s c a l ei m a g e s t h er e l a t e dw o r ka n dm a i nc o n t r i b u t i o n sa r e s u m m a r i z e da sf o l l o w s ： 1 c o l o r i z a t i o nb a s e do nl o c a lc o l o r - h i n tp r o p a g a t i o n u n d e rt h ea s s u m p t i o nt h a t t h es h o r t e rs p a t i a ld i s t a n c ea n dt h em o r es i m i l a rl o c a lg r a y s t a t i s t i c a lc h a r a c t e r i s t i c st h ep i x e lh o l d st oag i v e nc o l o rs c r i b b l e , t h em o r ec o l o rc o n t r i b u t i o n s f r o mt h eg i v e ns c r i b b l et h ep i x e lg e t s ”，t h i st h e s i sg i v e sae o l o r i z a t i o nm e t h o d t h i sp r o p o s e d a l g o r i t h mi sb a s e do nd i s t a n c et r a n s f o r m a t i o na n df u z z yc l u s t e r i n g g i v e ns o m et y p i c a lc o l o r s c r i b b l e so nt h ei n p u tg r a y s c a l ei m a g e ，t h ec o l o r i z a t i o np r o c e s sc o n s i s t so ft h ef o l l o w i n gs t e p s ： c o l o rs c r i b b l ee x t r a c t i o n , d i s t a n c et r a n s f o r m a t i o na n ds p a t i a lw e i g h t i n ge s t i m a t i o n , f u z z y c l u s t e r i n g , a n dw e i g h t e dc o l o rb l e n d i n g b yp r o p a g a t i n gt h el o c a lc o l o r h i n t sf r o mt h eg i v e n s c r i b b l e st ot h ew h o l ei n p u ti m a g e ，t h ef i n a lc o l o ri m a g ec a nb ep r o d u c e d 2 c o l o r i z a t i o nb ym e a n so fc o l o rt r a n s f e r e f f i c i e n tc o l o rt r a n s f e rb a s e do nd i v i s i v eh i e r a r c h i c a lc l u s t e r i n g c o n s i d e r i n gt h ep r o b l e mo fn e i g h b o rs e l e c t i o nb ye x h a u s t i v es e a r c h i n ga n dt h e t i m e - c o n s u m i n gt r a n s f e r r i n gp r o c e d u r ei nw e l s h sm e t h o d ，w ei n t r o d u c ean e wc o l o r i z a t i o n a l g o r i t h m ，i nw h i c hd i v i s i v eh i e r a r c h i c a lc l u s t e r i n gi su s e dt ob u i l dt h eb i n a r y - t r e es t r u c t u r e f o rt h er e f e r e n c ec o l o ri m a g el u m i n a n c ef e a t u r es p a c e b a s e do n t h en e a r e s tn e i g h b o rr u l e ， t h ec o l o rc o m p o n e n tf r o mt h er e f e r e n c e dc o l o ri m a g ec a nb ee f f i c i e n t l yt r a n s f e r r e dt ot h e i n p u tg r a y s c a l ei m a g e i v m u l t i - l e v e lc o l o rt r a n s f e ra n dg r a d i e n tc o r r e c t i o nb a s e do ng a u s s i a np y r a m i d i no r d e rt oi m p r o v et h ev i s u a le f f e c ta b o u tt h ec o l o r i z a t i o nr e s u l t ，t h i st h e s i si n t r o d u c e sa m u l t i - l e v e lc o l o rt r a n s f e r r i n gs t r a t e g y b yg a u s s i a np y r a m i d ，am u l t i r e s o l u t i o nf o r mf o rb o t h i n p u ti m a g ea n dt h er e f e r e n c ec o l o ri m a g ei sg e n e r a t e dr e s p e c t i v e l y t h e nt h em u l t i l e v e l c o l o rt r a n s f e ri sc a r r i e do 呔f r o ml o wr e s o l u t i o nt oh i g hr e s o l u t i o ni no r d e rt op r o d u c e d i f f e r e n tr e s o l u t i o nc o l o r i z a t i o nr e s u l t s f i n a l l y , a c c o r d i n gt ot h ea s s u m p t i o no ft e x t u r e c o n s i s t e n c y , c o l o rc o r r e c t i o np r o c e s si ss u p p l i e d t h e r e f o r et h eo u t p u tc o l o ri m a g ew i t h p l e a s a n tv i s u a le f f e c t si sp r o d u c e d k e y w o r d s ：i m a g ec o l o r i z a t i o n ，d i s t a n c et r a n s f o r m ，g a u s s i a np y r a m i d ，d i v i s i v eh i e r a r c h i c a l c l u s t e r i n g ，h i s t o g r a me q u a l i z a t i o n v 学位论文原创性声明 本人所提交的学位论文基于聚类和距离变换的数字图像彩色化技术，是在导师 的指导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要 贡献的个人和集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：崔会砷 劲。吁年6 月吁e l 指导教师确认( 签名) ：嬲 ? 伪夕年多月夕日 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 论文作者( 签名) ：崔食聊 2 d 口c 年6 月9 e l 指导教师( 签名) ：嬲 2 彬年多月歹日 1 1 1绪论 1 1 选题背景及意义 图像是记录客观世界的一种有效形式。早期关于客观世界的图像记录过程中，由于 成像手段的落后，不可避免地出现颜色缺失的现象，因此出现了大量没有颜色的黑白照 片、电影；此外，由于成像机理的关系，一些成像系统如x 光透视成像、雷达成像等， 只能记录得到灰度图像。人眼关于灰度图像的分辨能力只能达到几十个灰度级，若灰度 图像中包含丰富的信息，但相邻像素的灰度差别不大，则无法从图像中辨别或提取相应 信息；相对于灰度图像，人眼对彩色信号的分辨能力更强，可以辨别几千种颜色色调和 亮度，而且颜色能使图像内容更丰富、细节更清晰，视觉效果也更为生动、逼真。 彩色图像的优势引发了人们对灰度图像进行颜色处理的兴趣，于是给灰度图像上色 的技术应运而生，这就是图像的彩色化( i m a g ee o l o r i z a t i o n ) 。目前，“彩色化 这个术语 定义为：将计算机作为辅助工具，为单色的静态图像或视频序列添加色彩信息的各种技 术，即数字图像的彩色化。数字图像彩色化是近十年来出现的一个研究方向，已经成为 图像处理和图像编辑理论中的一项重要研究内容。 将计算机作为辅助工具来完成着色这项工作，最初出现于w i l s o nm a x k l e 和b r i a n h u n t 在1 9 7 0 年提出的彩色化这个概念中，当时他将计算机辅助彩色化方法应用于处理 黑白老照片和黑白电影【1 】，例如“阿波罗 登月获取的月球影像。h a lr o a c h 工作室的主 席g l i c k 在1 9 8 4 年就曾有过这样的论断，彩色化经典的黑白作品所创造出的经济价值远 远超过新创造的黑白作品【2 1 。因此，在社会价值上，我们可以看到图像彩色化技术的经 济利益。 由于彩色化过程中，要对图像中表示亮度的各像素的灰度值取代以三维颜色空间的 矢量，而从灰度值到表征色彩的颜色分量的映射却并不是唯一确定的，即不同的颜色可 能具有相同的亮度值，却具有不同的色调和饱和度。因此，彩色化从根本上讲是一个“病 态 的过程。为了降低这种映射的不确定性，少量的人工干预常起很重要的作用。基于 上述原因，现有的彩色化过程必须具备两个要素：一是参考的颜色信息；另一个是基于 这些颜色信息的着色策略。另一方面，到目前为止，还缺乏评价彩色化效果的客观标准， 还没有一种“正确”的解决方案。 因此，随着数字技术的广泛应用和产业化技术越来越得到人们的关注，数字图像彩 色化技术作为其中的重要部分之一，仍是一个富有挑战性的研究课题。 1 2 国内外研究现状 自2 0 0 1 年以来，随着计算机科学和多媒体技术的发展，数字图像彩色化的研究得 到了国内外的密切关注。但到目前为止，还没有一种通用的方法，能完全自动地对任意 类型的图像或视频序列着色。目前的彩色化技术按照处理对象的不同，主要归纳为三类： 静态图像的彩色化、常规视频序列的彩色化、黑白卡通片的彩色化。 1 2 1 静态图像的彩色化 现有的彩色化方法大都是针对静态图像而言的，按照彩色化的策略不同，又可分成 以下几种： 基于类比学习思想的彩色化 图像类比( i m a g ea n a l o g i e s ) 是借助机器学习的过程，从输入图像彳，么学习其相关 性，再应用于输入的源图像曰以得到与已知图像彳风格相似的目标图像曰的一种技术。 h e r t z m 觚n 【3 】将该思想应用到w e l s h 【2 】的灰度图像彩色化中，取得了较好的效果。 基于颜色传递思想的彩色化 r u d e r m a n 【4 】提出的鄙颜色空间，奠定了彩色化发展的基础。r e i n h a r d 【5 】的彩色图 像间颜色传递算法的提出引起了人们的广泛关注，在此基础上，w e l s h 【2 】根据像素灰度 及邻域统计特征的相似性，将颜色传递扩展到灰度图像，为灰度图像的彩色化开了先河。 同时，对于图像基调不唯一的情况，w e l s h 及之后的张引等人【6 1 使用分块思想予以处理。 随后，c h e r tr 7 】将a l p h a 分布和梯度引入到贝叶斯抠图中，结合w e l s h 的着色环节分别上 色，并进行a l p h a 合成。针对场景复杂的灰度图像，x i a n g t 8 】【9 】参考多幅不同的源图像， 实现了由多幅源图像向一幅目标图像的颜色传递。尽管这类方法给出了一些效果不错的 彩色化实例，但却不能保证处理后的颜色在空间上的连续性；同时，由于着色结果强烈 依赖于所采用的参考图像，这使得参考图像的选择成为一个难题。 基于局部颜色线索的颜色扩展彩色化 这类方法不需要额外的彩色图像作为参考，首先由用户提供局部颜色线索，再设法 将局部的颜色信息扩展到整幅图像。因颜色线索的提供或颜色信息的扩展策略不同，陆 续有不同的算法出现。如l e v i n 【l o 】利用草涂的颜色条作为约束条件来构建最小平方优化 问题；l i 【l i 】、l a g o d z i n s k i l 【1 2 】及y a t z i 4 1 4 1 提出基于距离加权的彩色化；贾云涛t l s 贝0 把图切分这种最优分割思想用到彩色化中，随后r o t h e r 1 6 1 提出了改进的g r a b c u t 分割算 2 法；h o r i u c h i 【1 7 】【1 8 】【1 9 1 2 0 采用了由种子像素开始、在保证邻域像素颜色差异最小的前提下， 使着色向外逐点扩张的方法；赵国英等人【2 1 】提出多分辨率脸部图像上色思想；胡国飞等 人【捌提出基于统计学的自适应颜色传递技术：i r o n y 2 3 】提出监督分类的着色方案。 1 2 2 常规视频序列的彩色化 前面的一些图像彩色化方法可以扩展到视频序列处理中，如l e v i n t l o 】利用运动估计 确定相邻帧像素间的时空邻域关系，根据时空邻域内颜色差异最小的原则将邻近帧的着 色方法应用于当前帧。但视频序列彩色化不宜简单照搬图像彩色化的方法，这主要是因 为视频序列帧数众多，如果每一帧都分别用现有的着色方法进行处理，工作量太大，势 必会影响其实用性。 y a h 等人f 2 4 】基于颜色传递技术，实现了一种彩色化红外线视频的方法，首先将红外 视频转换成灰度视频，然后为提取的关键帧设定彩色参考图像，根据参考图像与关键帧 的灰度对应关系建立调色板，利用调色板彩色化关键帧及其邻近帧。考虑到同一场景下 相邻帧之间的图像内容差异较小，p a n 等人【2 5 】提出了一种以颜色传递和运动跟踪为基础 的视频彩色化方案，做法是对关键帧采用w e l s h 的着色方案，与关键帧相邻帧的处理是 为每一像素在关键帧上寻找邻近的灰度匹配点，将匹配点的颜色作为该像素的着色结 果。w a n g 等人幽根据用户输入的一幅目标图像和三幅源图像，指定图像序列的n 值和 颜色变量曲线，利用插值的方法计算出一个颜色相关的视频序列。 1 2 3 黑白卡通片的彩色化 一般来说，卡通的构图相对简单，只有前景和背景两层，且轮廓清晰，易于进行分 割；另一方面，由于缺乏必要的纹理信息，其彩色化无法利用颜色传递技术。与普通视 频的彩色化处理相对应， s y k o r a 等人【2 7 】【2 8 】【2 9 1 研究了卡通视频的彩色化问题框架，以人 工着色的单帧卡通图像为参考，针对卡通序列帧间跳跃过大的特点，重点解决了后续帧 的颜色跟踪问题，尤其适用于数字化传统的赛璐璐电影。该方法的前提是前景物体具有 明显的轮廓，由此可以较准确地选取出与每一帧形状相似的前景区域。但该算法只能对 特定的结构性卡通片有效，还非常耗时。同时，s y k o r a 等人【3 0 】还利用了基于块的采样和 概率松弛法的着色方法，该方法仅对前景物体进行彩色化，适用于背景是静态、前景是 动态的手绘卡通片，同时要求目标与源图像有相似的形状。 1 3 典型应用 数字图像彩色化目前已经成为数字图像处理的主要研究内容，其研究成果不仅可以 3 为彩色图像合成、图像编辑、图像增强等提供有效参考途径，具有重要的学术价值，图 像彩色化技术还具有广阔的应用前景。以下是近年来彩色化技术的一些典型应用。 1 ) 黑白老照片和电影胶片着色【3 1 1 。很多经典的老照片和电影大都是灰度图像，进 一步挖掘这些影片的艺术和商业价值，给其添加上适当的颜色，能使其更具观赏性，而 这正是黑白电影难以实现的。 2 ) 电影特技【3 2 】。电影特技指的是利用特殊的拍摄制作技巧完成特殊效果的电影画 面。将彩色化技术应用到电影特技的制作和处理过程，既提高了影视制作的效率，也降 低了成本，增强场景的真实感，是一个比较有挑战性的研究方向。 3 ) 遥感图像【3 3 1 。对黑白航空图像或全色卫星图像，借助真彩色航空图像或多光谱 卫星图像的颜色信息进行彩色化，一方面改善视觉效果，再现或模拟场景的真实颜色； 另一方面，突出图像中感兴趣的内容，检测到黑白图像中检测不到的信息，利于对图像 细节内容的判读与识别。 4 ) 医学图像。由于成像机理的限制，一些医学成像设备如c t 、m r i 、p e t 、s p e c t 、 d s a 、u s 等只能得到灰度图像。利用彩色化技术对这些图像进行着色，可以增强其可 视化效果，更有利于观察人员做出正确的诊断。此技术在图像重建体绘制和仿真、虚拟 活检、虚拟手术、临床影像诊断参照等领域都有广泛的应用前景。 5 ) 夜视图俐3 4 1 。夜视图像通常都是灰度图像，尤其是在低照度情况下，图像提供 的细节信息比较有限，而适当的彩色化处理方法，可以将蕴藏在原始信道图像灰度中的 细节信息突显出来，更利于目标识别、方位判断和场景记忆识别，其在军事、公安、航 天、航海、卫星监测等领域的应用前景，已经引起越来越多人的重视。 6 ) 黑白卡通片。现代化流水线的制作，卡通里的人物与背景都是由电脑剪辑而来， 清晰地分开了前景与背景( 通常背景是静态的) 。将彩色化技术应用于黑白卡通片，只需 对轮廓清晰的动态变化的前景层进行相应的处理即可。 7 ) 褪色或变色的文物。经历漫长的历史更迭和变迁，我国的一些建筑彩绘或现存 的古建筑遗址也已遭到不同程度的破坏。如何采取有效的保护和修复措施已经显得非常 迫切与重要。作为数字文化保护及修复手段之一的基于计算机辅助的彩色化技术，已经 引起各国政府、学术界及文物考古界的高度关注。 另外，色彩信息往往还添加到一些科学图片上，加强生动性和教育性；同时，根据 所选的目标图像的不同，不仅能产生不同的视觉效果，而且也提高了技术处理的多样性 和艺术性。 4 1 4 本文的主要工作 本文针对静态图像的彩色化技术进行研究，工作主要包括以下几个部分： 1 ) 对国内外现有的图像彩色化技术进行了分类总结，对彩色化技术的研究现状进 行了分析； 2 ) 针对基于局部颜色线索扩展的彩色化，本文提出了一种基于距离变换和初始模 糊聚类的彩色化算法，这是一种用户指导下的交互式图像彩色化方法，并对实验结果进 行了详细的分析、比较和讨论； 3 ) 针对基于颜色传递思想的彩色化，本文借助分裂式分级聚类实现了高效的颜色 传递；借助于高斯金字塔技术和分层颜色传递，获取额外辅助颜色信息，基于结构一致 性原则实现颜色修正，得到了视觉效果较为满意的彩色化输出图像。 1 5 本文的结构安排 本文共分为四章，各章的内容安排如下： 第一章介绍了本文的选题背景和意义、国内外研究现状、典型应用、主要工作及组 织结构； 第二章基于局部颜色线索扩展的彩色化技术，在一定的用户交互前提下，给出了一 种基于距离变换和初始模糊聚类的彩色化算法，并对实验结果进行了讨论； 第三章是基于颜色传递思想的、分裂式分级聚类的彩色化算法，对实验结果进行了 分析和讨论； 第四章对本文的研究工作进行了总结，并对进一步的研究方向和任务进行了展望。 5 2 基于距离变换和初始模糊聚类的数字图像彩色化 2 1引言 静态图像彩色化的一类方法就是：首先由用户在输入的灰度图像上勾勒局部的颜色 线条，以此作为参考的颜色信息；在此基础上，结合图像的自身特征设定颜色扩展策略， 进行整幅图像的彩色化。本质上，这是一种基于局部颜色线索扩展的彩色化过程。针对 这类着色思想，本章提出了一种基于空间距离变换和初始模糊聚类的彩色化算法。 文中认为，用户通过人机交互勾勒出的线条颜色就是输出图像在线条覆盖处的颜 色；其它位置处的颜色是用户提供颜色的加权组合。由此，我们做出如下假设：输入 、二 图像中像素关于某颜色线条的空间距离越近，彩色化过程中这种颜色线条对该像素着色 的影响程度就越大；输入图像中像素的局部灰度统计特性越接近于某线条覆盖处像素 的局部灰度统计特性，则在输出图像中该像素的颜色与该线条的颜色就越接近。换言之， 输出图像中各像素的颜色是上述两种因素共同作用的结果。 基于以上考虑，本章将距离变换和初始模糊聚类的思想引入到数字图像彩色化中。 利用距离变换来快速度量输入图像中像素关于各颜色线条的空间距离，进而得到与空间 距离有关的颜色权重；利用初始模糊聚类度量输入图像中像素关于各参考颜色线条处灰 度局部统计特性的相似程度。 本章首先介绍彩色化算法中的两个关键部分一距离变换和模糊聚类，然后给出完 整的着色算法步骤与实现。 2 2 距离变换 本文中将用“距离变换来快速估计灰度图像中任意像素关于各给定颜色线条的最 近距离，最终得到一系列的距离图像。 2 2 1 相关概念 距离变换( d i s t a n c et r a n s f o r m ，d t ) 是针对二值图像的一种变换，也是计算机图像处 理中基本的操作技术，已被广泛地应用于图像分析、计算机视觉、模式识别等领域。 构成距离变换的关键在于距离的设定，不同的距离定义对应不同的距离变换。数字 图像中常用的距离有欧氏距离、街区距离( 函，如图2 1 ( a ) ) 、棋盘距离( 魂，如图2 1 ( b ) ) 、 八边形距离( 如图2 1 ( c ) ) 等。其中八边形距离是函与函的混合距离，街区距离和棋盘距 6 离是欧氏距离的近似。在图像处理和分析中，距离常常是以某种特征出现，近似欧式距 离由于计算方便、结果均为整数，常被采用。 22 2 2 2 2 21221ll2 21ol22lo12 2l22l112 22 222 2 ( a ) 街区距离( b ) 棋盘距离 3 3 3 3 2 2 2 3 3 2 2l2 2 3 3 21o12 3 32 2l2 23 3 2 2 2 3 3 3 3 ( c ) 八边形距离 图2 1 , 4 、a s 及八边形距离的特征圆 点到点集的距离 点p 到一个点集s 的距离定义为：p 到s 中所有点的距离中的最短距离，即p 到s 中最近点的距离。 距离图像 距离变换是一种特殊的变换，它将输入的二值图像变换为输出的灰度图像。灰度图 像中各像素的值，反映了该像素与其最近目标点的距离。 严格定义如下：给定点集尸、一个子集b 和满足测度条件的距离函数攻，) ，在对p 的距离变换中赋予点p e p 的距离值为： d t ( p ) 2 曾 d ( p ，g ) ) ( 2 - 1 ) 计算距离的理想情况就是使用欧氏距离；但为了计算简便，常用的距离测度大多为 使用整数算术运算的距离函数。通过距离变换，一幅二值图像就可以转换成相应的灰度 图像，其中每个像素的灰度级代表了该像素与距其最近的特征像素间距离；这样，原来 7 的二值图像就变换成距离图像。 2 2 2 相关研究与计算原理 自r o s e n f e l d 和p f a l t z 于1 9 6 6 年首次提出距离变换这一概念【3 5 】并给出函m e t r i c 快速 算法以来，相继出现了一系列并行和串行算法【3 6 】【3 7 】【3 8 】【3 9 1 , 1 0 1 。距离变换被成功地应用到 图像分析、模式识别、计算机视觉等领域的研究中，如目标细化、骨架抽取4 1 】【4 2 1 、粘连 物体分离【4 3 】、机器人碰撞检测、最短路径检测、数据压缩、变形【4 4 】【4 5 】、o f f s e t 曲线的计 算m 、切片匹配插值【4 7 1 、印刷文本分割【4 8 】。 目前，距离变换的计算通常有两种方法：一种是基于模板的近似方法，另一种是基 于欧氏距离的精确方法。前者复杂度低、效率高，但计算的结果存在误差；后者计算结 果精确，但复杂度较高。从理论上讲，要计算一个像素到背景像素的最短距离，往往需 要对图像进行全局的运算，即计算此像素与所有背景像素的距离，然后取最小值。然而， 这种全局操作的计算量是非常大的。为了解决这个问题，一种办法是在并行机上使用并 行算法，另一种途径则是采用将全局操作分解为局部操作的策略，用串行扫描算法实现 距离变换，进而在扫描过程中传递最短距离信息。 实践中常用倒角( c h 锄f 砷算法【4 9 】进行距离变换，只需对图像进行两次扫描即可，并 且计算出的距离合理逼近于真实的欧氏距离。以二维图像为例，倒角算法给出了一个类 似于卷积核的模板如图2 2 ，它以一种类似于卷积的操作在整幅图像中移动。其具体算 法是先把二值图像中背景灰度设为0 ，目标灰度设为1 ，然后对图像做前后两次扫描( 模 板分别对应图2 2 的深灰色和浅灰色区域) ，一旦模板的中心( 图2 2 黑色部分) 移动到某 一目标位置时，模板中的每个元素就与其对应位置处的图像像素值相加，从而得到一个 两项和的集合，位于模板中心的图像像素值就用这些和中的最小值来代替。 只要图2 2 中纵b 、c 的取值满足l b a 2 ，1 c b 相似度定义：定义如何表示数据的相似度。一般使用的是基于距离的表示法。 聚类技术：通过各种聚类算法将数据对象分成多个簇，常用的聚类算法如硬c - 均值聚类和模糊c 均值聚类。 其他可选任务阶段：如对聚类结果的数据抽象、评估聚类等。 图2 6 聚类技术的阶段图 从隶属度的取值形式来看，现有的聚类分析算法主要有硬聚类方法和模糊聚类方 法。硬聚类算法要求每个样本经过聚类后，只能划分到唯一的一个类别中，样本对各类 的隶属度只能取0 和1 两种值，取值为0 表示该样本不属于这一类，取值为1 表示该样 本属于这一类。模糊聚类方法则顾及到了样本之间的联系，认为每个样本与各聚类中心 都有一个隶属关系，将隶属度扩展到区间 o ，1 】，类别划分具有“亦此亦彼 的性质。 2 3 2 硬c - 均值聚类 硬c - 均值聚类算法是应用最多的硬聚类算法之一，是一种在无类标号数据中发现簇 和簇中心的方法【5 l 】，能够对呈椭球状的数据进行分类。基本思想是：给定一个包含n 个 数据对象的数据库和要生成簇的数目c ，随机选取c 个对象作为初始聚类中心；然后计 算剩余样本到各聚类中心的距离，把该样本归到离它最近的那个聚类中心所在的类，并 对调整后的新类计算平均值作为新的聚类中心；如果相邻两次的聚类中心没有任何变 化，说明样本调整结束。 2 3 3 模糊c - 均值聚类 实际应用中的样本对象，其性态和类属方面存在着中介性，适合进行软化分。z a d e h 1 2 提出的模糊集理论为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理 聚类问题，称之为模糊聚类分析【5 2 1 。其应用范围涉及到通讯系统中的信道均衡、矢量量 化编码中的码书设计、时间序列的预测、神经网络的训练、非线性系统辨识、参数估计、 图像处理、数据挖掘、决策支持、医学诊断、天气预报、食品分类、水质分析等领域【5 3 1 ， 并取得了满意的效果。 模糊聚类算法的典型代表是由d u n n 提出并由b e z d e k 加以推广的模糊c 均值( f u z z y c m e a n s ，f c m ) 算法，也是一种比较有效的、利用迭代最优化目标函数对数据聚类的算 法。该类算法实际上是将聚类问题转化为经典数学中的多元非线性规划来求解，设计简 单、解决问题的范围广，且易于计算机实现。 设胙 x l ，规，而) c 矿是数据集，乃是数据集的元素个数，c 是聚类中心数( 1 c 刀) ， 妒矿巧i i 是样本点墨和聚类中心巧的欧式距离，巧c 萨( 1 删，u i 是样本却关于第j 类的隶属度，泸 ” 是一个n x c 矩阵，降【n ，v 2 ，z c 是一个$ x c 矩阵。模糊c 均值聚 类问题可以表示成下面的数学规划问题： 构造目标函数： a ( u ，矿) = m 口驴2 ( 2 4 ) i = 1j = l 最小化j ( u ，v ) ，使得： r c u 0 = 1 ，l f 刀 l 户1 1 ( 6 ) 蹦扩( o ，1 ) ，l i n ，l j c ，( 2 5 ) j ( c ) o 输入图像中颜色线条覆盖处各像素模糊隶属度的计算。 对于位于颜色线条上的各像素，我们规定：该像素关于所在线条颜色的模糊隶属度 为l ，而关于其它线条的模糊隶属度为0 。 这样，初始模糊聚类算法就完成了，算法的结果得到的是图像上各像素与所有已知 颜色的相近程度，即模糊隶属度矩阵玑 s t e p4 ：模糊隶属度的归一化。为了便于计算，文中将模糊隶属度矩阵进行归一化， 以满足条件：g ，= 1 ，0 _ 在s t e p1 得到颜色线条数目的基础上，定义一个颜色数目计数器c o l o rh u m ，初 始化为0 ；同时构造一个长度与线条数目相等的颜色数组，每个数组元素包含三个成员， 分别与颜色的r 、g 、b 三个分量相对应，均初始化为0 ； 遍历各颜色线条：第一个线条颜色是最先出现的颜色，将其填充到第一元素中， 2 1 同时颜色数目计数器c o l o rn u m 加1 ；对于其它线条，读取其颜色，并且分别与现有的 c o l o rl i t l m 个颜色进行比较。如果不存在一致的颜色，则颜色计数器c o l o rh u m 加l ，同 时数组元素下移一个，填入新的颜色；如果存在一致的颜色，例如 o b j e c t i c o l o r = o b j e c t 1 c o l o r o o ，则需做如下处n - 将线条o b j e c t j 的标记值m a r k 修改为与线条o b y e c f f 】的标记值相同： 将标记图像上o b j e c t j 所覆盖的位置处的标记改为o b j e c t i 的标记值； 将线条o b j e c t 1 之后的所有线条的标记值减l ； 将线条o b j e c t i 与o b j e c t j 覆盖的所有像素合并到一起，保存到线条o b j e c t i 的 数组s c r i b b m a t 中。 这样，就将具有相同颜色信息的线条归为了一类。 s t e p3 ：提取具有不同颜色的线条，并各自保存为一幅线条图像。根据颜色种类数 c o l o rh u m 的大小，从o b j e c t 数组中取出前c o l o rh u m 个元素，就可以得到所有不同颜 色的线条图像，如图2 1 3 ( d ) 所示。 经过上述三个步骤的改进操作，就将颜色相同的线条放到了同一幅图像中，从而使 得聚类的数目c l u s t e rn 和线条颜色数目c o l o rl i u m 一致，这在后续的距离变换和模糊聚 类中将大大减少运算量，提高运算的速度，其它操作与情况王一样。 ( 2 ) 模块二：距离变换及距离权重的估计 在得到了不同颜色的线条图像之后，可以利用本章2 2 3 节的c h a m f e r3 - 4 距离变换 对各颜色线条图像进行距离变换，从而得到相应的距离图像，而距离图像中各像素的值 即为输入的灰度图像中该像素到这种颜色线条的最近空间距离。这种距离是该像素关于 不同颜色线条的空间接近程度的一种定量描述。 按照关于本算法的一些假设条件，我们可以这样认为：在对输入图像中任意像素上 色时，某颜色的线条关于该像素的最近空间距离越小，则该像素关于这种颜色的空间接 近程度就越大；相应地，在对该像素上色时，这种颜色线条对该像素着色的影响程度就 越大。 基于上述考虑，我们引入“距离权重( d i s t a n c ew e i g h t ) 来定量描述这种具有不同空 间接近程度的颜色线条对像素着色的影响程度。并且，像素关于某种颜色线条的空间距 离越小，相应地，对该像素进行上色时，线条颜色对该像素颜色的影响权重就越大。 若输入图像总的像素数目为d a t a 行，用户勾勒线条的颜色种数为c l u s t e r 尼，输入图 像中第f 个像素到第j 种颜色线条的距离权重为暇力，则可根据第i 个像素到第，种颜 2 2 色线条的最近距离吠t 力来估计权重职t 力。 我们可以定义不同形式的距离权重。这里给出如下两种形式： 高斯型： 一r 垡! ! ! ! 、2 w ( i ，j ) = e 。艿+ s i g m a ( j ) ( 2 1 0 ) 其中：职t 力代表第f 个像素到第_ ，个颜色线条的距离权重； 吠t d 表示第f 个像素到第，个颜色线条的最近空