（模式识别与智能系统专业论文）图像修复快速算法研究.pdf

摘要 图像谚复是指对图像中数据完全丢失的暇域进幸亍填充，戳恢复萁完整性幂口原 有的视觉效果。图像修复是一个比较特殊的瘸态问题，它是一个从无到有的过程， 我们必须根攥先验知识，从髑嗣幸存酌数据米预溺受面的数据。所以图像修复问 题中，先验模型起关键的作用。根据g e s t a l t 效应的原理，自然图像的连续性和 光滑性是图像修复所依赣的簇本静先验知识。 处理图像修复问题的一类主要方法是用兜验知识建立偏微分方稔，把图像修 复表述藏一个逑界德闯题，矮迭代豹方法来浓解。冀关键在予如何恰当遣弓| 入先 验知识建立方程。这种方法往往速度很慢，而且修复的结果边缘模糊，对稍大一 点豹区域有帮能褥不爨舍逶静簿。 为克服这些缺点，本文研究图像修复的快速算法并力求保持图像的强边缘。 簧荛我铜撬密了一耱基予承乎线演证静辫像嫠笺算法。褥图像修复阕逶袋述 为个曲面演化问题，并以s n a k e 的内部能蓬模型作为图像水平线的先验模型， 由承乎线戆演铯攫动强像麴露魏演弦。这令方法簿决了黯鹜像痰平线豹窝葭麓线 模型的直接优化问题。 程深入分辑基予扩鼗翡强像罄蔓舅法巍壤波基拣上，鬟趣了对羹像熬酸缀区 域由外向内环一环地进行插值的修艇方法。这个方法丢弃了传统的偏微分方程 方法孛露饕反复迭伐戆方法，丽是采孀逐煮诗舞鳃方法，对每一个像豢哭强次 计算就估计出熟灰度德，大大提高了计算速艨。对每一个象索的估计采用了墒部 拳平线撬篷戆方法，这缝褥我秘懿冀法其毒 建姆的边缘镍持裁力。这耱童癸离态 逐环摘值的方法叫做艇形插德，这种方法的g f 入，使修复的结果更为合理。 建了筏修复的缝聚更接送予套然辫像，援港了基予蒙将卡罗随辊模熬豹爨像 修复快速算法。这也魁一个逡点计算的方法。对文字笔迹等这样的细长带状区域， 最照搬港魂的方法进行修复，速度较抉，藤盛憩皂动产生强边缘。对较大的块状 区域，用随机模拟边界积分的方法进行修复。如果嚣域中有边缘穿过，则先连接 边缘，再用隧帆模拟靼延拓躲方法萋梅平滑区。这种分块重构的方法，自较好靛 傈持凝边缘。随梳模拟方法的使用筏褥修复躺维栗其商自然图像的蔽枫噪声韵效 果，所以更接近自然豳像。 本文最螽提出了一个基于边缘鑫遥应小波交换豹多尺度黼像修复快速算法。 使用多尺度方法，可以减小修复区域在低频图像中的缺口，从而减少计算时阍。 边缘鑫适鏖夺波变换方法翡孳l 天，使我稻锯熬麓够用一个努块重构的方法重鞫低 频黼像，而且此时静平滑予区域交褥很小，用延拓方法重构对，泰勒展式豹收敛 圃就能够覆盏整个子区域，从而提离修复的准确度。使用边缘白适殿小波变换的 方法，可懿基本消除边缘新造成静磷频系数，簸蔼避免了对畿律往较差静巅颓系 数的修复，而通过涟接边缘和分块道构的方法来产生强边缘。 关键词：图像修复，水平线，蒙特卡罗，多尺度 l l f a s ta l g o r i t h m sf o rd i g i t a l i m a g el n p a i n t i n g g uj i a n p j n g ( p a t t e r nr e c o g n i t i o na n di n t e l l i g e n ts y s t e m s ) 】n s 蛀蚀t eo f a u t o m 蕊0 虢，a l i 珏e s e a 彘糯yo fs c 氯i b s d i n x e db yp c n gs j l o n g a b s t r a c t h l p a i n t i n gr e f c r st ot e c o n s 讥l c i 诵gt h eo o m 】p tr e 舀o n sw h e r ct h ed a t aa r ea l l d e s 拓o y e d i ti s 勰e 辨e c i a l l y 潍p o s c d 蝉b l e m 抽w h i 穗w e 豳o u l dg u e s s 氆em i s s 弧g d a l a 矗o m 弼ov i c i n i t ya c c o r d i i l gl ot 酶p r i o r 融l o w l e d g e s om ep r j o rm o d e lp l a y st h e c n l c i a lr o l ei 1 1t l l i sp r o b l e m a c c o r d i n gt ot h cg e s t a l ts c h o o l ，t h ec o n t i n u i t ya n d s 臻o o 圭羲嚣e s s 艇氇e 纛a l 毽f 畦瓤l 鑫g ei s 氆em e s 耋主氆瓢峨褥l 翻甜k 嚣o w l e d g e 晒氇o i n p a i l l t i n gp r o b l 锄 0 n e 州翔a 垮c l a s so f 擞e 氆。叁轴fi m a g ei n p 毪 辩l i 珏gl s | ob 珏i l d 鞋p 建p 籍畦a l d j f f e r e l l t i a le q u a 廿o na c c o f d j n gt os o m ek j n d so f 叫o rk n o w l e d g c ，a n dc o n s i d c ti ta sa b o u n d a r yp r o b l e m ，a l l dt h e ns o l v ei tb yt j m em a t c hm e t h o d 1 1 l ek e vw o f ko ft h i s 礤e 疆稠i s 壤嚣s c l i n g 卵髓| 沁e q u a l i o n g e n e r a 量玟i ti sv 盯ys 孙wf 醅攮i s 翔e l 弧o d | o f i l lj nag e n e r a lr c 西o n ，卸di tc a i l tp r e s e r v es h a i pe d g e sw e l l s o m e t i m e si tc a n t p r o d u c eac o 玎e c ls o l 姓6 0 珏f o rab 主g g e f 撑垂o n 1 bo v e r c o m et l l i sd f a w b a c k w er e s e a r c ho nf a s ta 1 8 0 r i t h m sf o ri m a 壮i n p a j n l j n g 翘d 坤y 沁p 心s e 辩e e d 器e s 鹋w d l 器p o s s i b l e 攮糖i s 弘p c r ： 鞘r s t l y ，w ep r o p o s ea n 衲p a j n t i n 盛m e t h o db a s e do n1 e v e ll j n ee v o l i i o n i fw e i m p l i c i t l vf e 戳譬s e n t 塌em a n e 球e sa st h el e v e ll i n e so f 瞧es 毡蛙矗e e ，t h ee v o l 硅蛞o no f 氇搴翻a n oc 畦f v 嚣sw 疆ll 铀d o 壕ee v 毽t l o 重lo f 国e 獬p o n d 两gs u 蠢矗c e 下h e 记t e r n 蠢 e n e r 繇yo f t h es n a k ej su s e da sl h ep i i o rm o d e l0 fl h el e v e ll i n e0 ft h ej m a 辨，a n df r o m i 抟d e s e e 越嚣0 辩w e 鸸t 越珏国ee v o l 鼙l 娩蠲珏a 墩难。薹l h 霉i m 鑫窑嚣s 瓣蠡c 。碌e 蓥嘲e t f y m e a n j n go f 协i si n p a j n t i l l g 蝴尊t h o di si oc o n n e c t1 c v e l1 i n e su s i n gs m o o t hc u n ，e s e x p e r j m e n ts h o w st h a to u rm e t h o dw i up m d u c eb 搴t t e fr e s u l l si n 狂c o m p a r a b l e o 嘲p 硅蛀珏gv e l 粒i t y ，辩避珐a 攀嚣d g c sc a nb e 簪辩撺羁w e l l s e c o n d l y ，w ep r o p o s ea nj n p a j n l i n gm e t h o du s i n gl “e ll i n ei n t e 巾o l a t j 硼。i tj sa 舜赋b y 蟛嫩o o m 辨t 轴g 掇e l 瓠罐，妇e 鑫e h 窭x e lw e 渤e s | 妇l 采e 轻静，v 越珏eb yo 魏l y o n el j m ec 0 瑚p u t a t i o 扎s oi ti sm u c hf a s t e rt h a ni h et i m em a t c hm e t h o du s i n gb vt h e p d e 耀e l h 耐r f 或l vw ed i s 翱s sl h el e v e ll i 瓣默翊db a s e d 潍慢ee n l 髓sd 毽s 波 w h i 穗w i l lt 培u s 荫基s 缅el o e 蕊i 鞋l e 啪l a t i o nk 糯或l o 蹴l e n dm el e v e il j l l c s t h e nw e u s et h es t a 卜s h a p e di n t e r p o l a t 自o j lm e t h o dt oi n l r p o l a t et h el e v e ll j n e sl a y e fb yl a y e r 蠹o m 氇搴妇黏d a f y 蜒t l 撼i n p 裔n 蛙n 塞l 嚣西o n 舞oi t 。强驻sw ee 器n 棼x 据n 建壤el e ￥dl i n 弱 s m o o l h l yi n 协t h ec o m l p tf e 翻o n ，a n di h ei n p a i n t i n gd o m a i nw j l ls e wu ps t e pb ys t e p 1 1 i 皿i sa l g o f i t l l l l li sv e r yf a s ta n dc a np r e s e “es t r o n ge d g c s ，a n dt h er e n s t n 】c t e d s t n l c t i l r ew i l lb em o r en a t i l r a l n j r d l y ，w ea p p l yt h em o n l ec 盯1 0r 柚d 锄s i m u l a t i 咖m e t l l o dt 0t i l ei n p a i n t i n g p m b l e m ni s a l s oap o i n t b y p o i n tc o m p u t i n gm e t h o d f 0 ral o n gn a r t o wc o r n l p t r e 舀o n ，e x a m p l cf o rt l l eh a n d w r i t i l l 备w eu s et h er a l l d o mw 柚d e r i n gm e t h o dt of i uj nj t i ti sv e r yf a s ta n de d g e s 啪b e p r c s e r v e dw e l l f o ra w i d e rs m o o t hr e 舀o n ，w eu s et h e m d o ms i m u l a t i 蚰o fb o 岫d a qi n t e g m lt 0 如t e r p o l a t ei t f o rag e n e r a ls t 加c t u r cr c 舀o n w i t l le d g c si ni t ，w ef i r s t l yc o 皿e c tt h eb i o k e ne d g e su n gt l i ei n t e m a le n e r g yo f s n a k em o d e l ，a n dt h e nr e c o n s t f u c t t h o s cs m o o t i ls l l b r e 酉o n su s i n gm d o ms i m u l a t i o n a l l dc x p a n d i l l gm e t h o d t h j sp i e c e - w i s e l yr e c o n s t m c i i n gm e m o dc a np r o d u c es t m n g e d g c s t h er 柚d 锄s i n m l a t i o nm e t h o dc a l ip i o d u c em o r en a t u f a lr e s u l tt h a ti sm o r e s i n l i l 缸w i t ht l l en a t u r a li m a g e f o u r t h l y ，w ep r o p o am u l t i s c a l ea p p r o a c ht oi l n a g ei n p a i n t i n ga l g o r j t h mb a s e d o ne d g c a d a p t i v ew a v e l e tt r a 璐f b 珊b yw a v e l c td e c o m p o s i t j 加，t h e i n p a i n t i l l g d o m a i nw i l lb e c 啪es m a l l c r 卸ds m a l l c ri nt l l el o w 丘e q u e n c vi m a g e ，s oi tw j l ln e e d l c s st i m et or e o o n s t m c ii t b e c a u s eo ft h ec d g c a d a p t i v ew a v e l e tt 姗s f o 舶a d o p t e d ， w ec 姐u s et h ep i e c e w i s e l yr e c o n s t m c t i n em e t h o dt of i ui nt j l el a r 2 e ，s c a l ei m a 盛c a n da lt h i ss j t u a t i o n ，t h es m o o t hs u k r e 醇o n sa m u c hs m a l l e r s oi tw i l lb em o r c e x a c tw h e nw er e c o n s t 叫c tt h e mu s i n gt h y l o rf o r m u l a ，b e c a u s ei ti se a s i e rf o rt h e c o n v e 唱e n c cc i r d eo ft h ct a y l o re x p 柚s j o nt oc o v e r t h e m u s j n gt h ee d g c - a d a p l i v e w a v e k tt r 锄s f b 珊，w ec a ne l i m j n a t et h eh i 曲一丘e q u e n tc o e 塌c i e n c i e sp 剃u c e db vt h e e d g c ，s oa v o i dt l l er e c o n s t m c t i n go ft h el l i g l l - f 搬l u e n tc 0 - e f f i c i e n c i e s ，w h j c hi so fp o o r r e g i l l a r j ty o u ra l g o r i t l l 】皿时t op r c 潜n ，ee d g c sb y 加e c tt h e m 卸dr e c o n s t m c t t h e j m a g eu s i n gp i e c e - w i s e l yr e c o n s 虮l c t i n gm e t h o d k e y w o r d s ：l n p a i n 妇岛k v e lu n e ，m o n t ec a r l o ，m u l t i s c a l ea p p t o a c h 独创性声明 本人声明职成交的论文是我令人在导师指导下进行懿磺究工馋及取键的硬 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 入门经发表或撰写过的研究成果。与我一同正作的同志对本研究所做的任何贡献 鸯溅在论文牵箨7 骥确蘧巍裙荠表暴了谢慧。 签名： 乒牛 日期：旦坐业 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关缳照、使用学位论文的嫂定，罄： 中豳科学院自动化研究所有权保留送交论文的复印件，允许论文被森阅和供阅； 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文猩解密詹应遵守此规定) 签名：；乙鱼耳譬炜签名：一= 巴生垒型竿日麓： i o 够。史毒砖 第一章引言 1 1 研究的意义和目的 第一章引言 图像修复箨苓楚一个薪 瓣题，毽它是一令菲露独特鹃| 蠢题。珍藏熬绘滔俸懿 可会因走年代蛉久遨积保管的不周箍破损，像管员裁要用手去修复它。生涟 中的照片放久了也会发生颜色剥落，电影胶片放映的次数多了也会有损伤。阕 像修复的目的就是器对这些破损的图像进行修补，以恢复它的完整性，并尽可 麓恢复霖来静视觉效栗。本文要矫究豹是数字胬豫修复，郎瘸计算梳对这些裔 破损的塑像遴簿修复，这是最近这足冬方兴起蛉。醚。b e 矗a l 氆i o 【2 】是最早舞始 研究数字图像修复的，并把它口q 做h l p a i n t i n g ，就是把绘画中的破损区域蓬新砸 上去的意思。 某些有保存价值的酒报杂志上可髓有书写过的笔迹，或是有些标题是多余 翡，要去捧这些多余豹末毯裁要鼹至l 零橡修复技术。这实际上是一令去遮挡海 题( d i s o c c l u s i o n ) ，但解决方法躐图像修复几乎是完全相同的。去遮挡的一个非 常藏要的理论依据是g e s t a l t 心理学理论，它同样也熄图像修复问题建立先验模 型豹重隳依据。醋像模式谈痢中，待识掰的对象育可能被捌的对象挡住了一部 分，这辩邀要用戮去遮挡方法。 压缭图像掘视频在技输避程巾经常会发生数据丢失，勰压慝裁会有块状图像 信息缺失的现象。这个问题的解决方法在阁像编码系统中叫做编码纠错( e 啪r c o n c e a l m e n t ) 。如果纠错是强解蕊后进行，即后端纠错，那就蔻一个地道的图像 掺复润熬。实际上由予应薅膂景耱鞭澍，薅端纠错往往楚最鬻掰静。由于褫频 图像，郏动态图像的修复毒藏匿期邻、场豢媚羁或类 矬约图像麴售憋可以零期， 所以常常可以运用匹配、粘贴、和融合等方法。如果没有这些场景相同戏类似 的其它图像的信息可用，例如动态图像中可能间一个地方的数据都丢失，再如 静态霭像豹蠲错等等，鄢藏袋能滔破损区城周豳的信息进行插僚了。稻对而言， 闻题懿滚点仍然是单蠖躅像的修复方法。零文耋要研突擎辐嚣像掺袈阂题。 图像修复的另一个重要应用就是豳际上目前正在研究开发的基于对缘的图 像眶缩标准，又叫感知驱动编码( p e r c e p t u a l l ym o t i v a t e dc o d i n g ) 。其基本 图缘修复快速算法研究 愚憋旗是只对爨橡中对象的边缘进褥缓码，包括逑缘鹣篷鬟秘强度，这榉霹爨 大大地降低比特率，丽在解码时要用插值的方法踅构出对象的袭面，即边缘所 包围的平滑区。这种插慎也是一种图像修复。 由予鬻像修复算法都可以赢接应用于这些领城，使得纯粹的单幅图像修复算 法瓣磅究骞了较隽蘩要鹣意义。本文熬褥究忑佟魏是铸对纯粹瓣单搦图豫修复 问题，深入研究普遍性的奠法，不针对特定的应明背景。 豳像修复可简单分为结构图像修复和纹理图像修复两大类。纹理图像修复的 基本方法是纹联合成，这是一个专门的课题，已经有多年的研究历史。所以现 在静图像修复| 曩蘧主要磷究绩构鬻像酶磐复。本文蘑研究静算法氇郡是锋对结 构图像的修复爨法。 逻辑上，图像修复必须事先从图像中检测到破损区域的准确能置才能进行， 但从自然图像中检测破损区域是一个很困难而又复杂的问题，目前这方面的研 究工作还没有舞震。历蔽现在入们在研究图像修复时，总麓镁竣破损区域的位 翌是已知的，先搁受检测阉题，只疆究修复舞法。本文也是遮撵。 现有的图像修复的主要方法，就是把图像修复表述为一个边馕问题，邋过偏 微分方程的方法来求解。这种方法理论上很严紧，但普遍速度较慢，修复个 一觳大小豹区域就需要好凡十秒甚至几分钟，而晨不一定能恢复强边缘。这使 褥这些算法躐实黪应翔懿霉要还寿一定戆躐离。除j 迦之辨，涟有基予 m u m f o r d s h a h 模型的分块重构方法，和用e u l e r 弹性模型连接水平线蛉修复方 法。现有的分炔重构方法中，一般模型比较复杂，过于抽象，难以实现，而连 接水平线的方法算法又比较繁琐，鲁棒性较差。本文的主要目的就是研究简单 恢逮戆图像掺复算法，势在爨离修复遽液豹蠲对，确缣能够产生强边缘。 关于算法效果的评价，目魏还没有一个定量的谬傍标准。由予图像骖复零来 就含有一定的主观臆测的成分，所以人们也就乐予用主观的方法来判断修复结 果的好坏。本文也只做了一些简单的试验比较，没有做更多的定量分析。而对 i 算速度两言，不糊的方法，计算甜闻差嗣很大，我们的葬法有些需要不翻一 秒钞，用扩数的方法可裁嚣要好足分铮，也来必窍好黪绩巢。嫒以我褒氆是镀 一些粗略的计算时间上的比较，这就足以说明阎题了。 第一章引言 1 2 图像修复问题描述 人工图像修复主要是依靠经验知识，从图像中已知区域的数据去推测未知区 域的数据。这是一个主观判断的过程，经验知识起主导作用。因为有主观性， 图像修复的结果也不是唯一的，也不能用对与错来对其进行评价，而且在自然 图像中，任何情况都是可能的，所以修复出什么样的结果都不为过。即使如此， 图像修复还是一定的规律可循的。对较小而结构又比较简单的区域，人们可能 倾向于根据连续性和光滑性的先验知识进行预测，而如果区域比较大，或结构 比较复杂，人们则会采用关于对象模型的先验知识或者纹理的周期性知识来预 测。 我们研究数字图像修复，就是要研究人工图像修复一般的规律，然后用计算 机来按这个规律进行修复。 人工图像修复是一个能动的过程，自够根撼不尉的情况采取不同的会适方 法。这鼹一个复杂的过程。我们研究数字图像修复，只能从最简单的情况开始 研究。那就怒先研究较小的结构简单的区域的修复，再研究较大的复杂的区域 酶修复。我稻的研究工作主要锌对 较小麓结构簿鼙鹃嚣域鹣修复。入捐逶常 又把这捞的区域叫做熙郏区域，意味整数擐丢失不是太严重，棂据信息论中采 样和重构的观点，还是可以蓬构的。 对简单的结构区域的修复，人们通常用偏微分方程的方法将其描述成个插 值嗣题。僵一般酌插毽问题只锌对竞滑函数，蒋通的插麓方法也只能插值线性 懿域光灏嚣数。磷塑像孛是骞缀多边缘，嚣虽边缘点都怒图缘涵数豹鸯冥熹， 一般的掭值方法悬得币到这些奇异点的。所以通过捅值方法恢复这些边缘是数 字图像修复所要解决的关键问题，也是难点所在。 用窝分的方法，图像修复可袭示为下谣能量泛函的优亿问题 _ ，d 】| 瓤( “硝) 2 + 露阱 ( 1 _ 1 ) 其中“o 为破损图像，包括融知数据区域和破损区域，d 为图像的破损区域， 如= a 1 。、d ( x ) ，1 。、d ( x ) 为融知区域的特征函数，q 为图像区域，a 为权熏因子a 掇据贝时婚原理，e l 】为图像的先验模型，丽专如0 一撑o ) 为数据模型，”海 目标图像。数据模型三厶如( “一“。) 2 的主要作用是提供有效的边界数据，并约束 修复过程不能过多地改变原有的数据。先验模型剐“ ，是问题的核心，提供估 计破损区域中数据的依据。 如果破损区域较大，结构比较复杂，或者有纹理，用插值的方法是无法修复 的，这时必须用匹配、融合和纹理合成这些更高级的方法。 1 3 图像修复问题的病态性质 一个问题的病态性表现为它的解不是连续地依赖于观测数据的，观测数据的 微小变动可能导致解的剧烈变化。如果问题的解是存在的，唯一的，而且连续 地依赖于观测数据，就称这个问题是良态的。如果三个条件中任何一个得不到 满足，就称这个问题是病态的或者不适定的。 例如，图像复原就是一个病态问题。图像复原是图像降析的逆过程，图像降 析可表示为图像与模糊核的卷积，而图像复原就成了一个反卷积问题。由于降 析过程中发生了部分信息的丢失，所以它实际上是不可逆的，或者说它的逆不 是唯一的，显然也不是稳定。因此，图像复原是一个病态问题，求解时，需要 加入先验模型进行规整化。 图像修复也是一个典型的病态问题。它的病态性比图像复原问题的病态性更 严重。图像的破损是一个粗鲁的物理过程，它没法用一个数学过程来描述的， 图像修复也无法表示成其逆过程。如果说图像降析中只丢失了一部分信息，那 图像破损过程中就丢失了全部的信息，破损区域的数据完全丢失了，它当然也 不可逆，更谈不上逆的唯一性。图像复原中用先验模型进行规整化，而图像修 复则完全依赖与先验模型，不同的先验模型会导致完全不同的解。 如果破损区域是一个局部区域，有外部基本能够预测里面的结构，各种模型 修复的结果相差不会太大，但这也是病态性的。而如果破损区域较大，结构比 较复杂，对它的修复将有更强的主观性，这时的各种预测只要在边界处能和已 知数据吻台的上，就能构成一个成功的修复结果。这就表现出更强的病态性。 第一章引言 1 4 研究方法 图像修复是一个非常特殊的病态问题，先验模型是解决图像修复问题的关 键。人工进行图像修复时，所用到的先验知识是非常复杂的，绝非单方面的知 识在起作用。但对结构简单的局部区域，情况就要简单一些。根据g e s t a l t 效应， 对这样的区域进行修复的主要先验知识是自然图像的连续性和光滑性，因而它 成了建立图像修复先验模型的基础。 研究图像修复问题，首先要考虑的就是建立先验模型。先验模型的建立源于 对图像的理解，就是你把图像看作一个什么东西。从这个角度，我们可以把图 像修复的建模方法分为三种。第一种就是把图像看作一个一般的二元函数，也 就是一个曲面，对这个曲面的连续性和光滑性进行建模。第二种观点认为图像 是由对象表面和对象边缘所组成的分块平滑函数，而边缘包含了图像的关键的 信息。根据这个观点而建立的先验摸型就是对象边缘模型，如m u m f o r d s h a h 模型。第三种方法是对图像的水平线进行建模，假设图像的水平线有一定的光 滑性，并用一个能量泛函来刻画它，通过最优化这个能量泛函来实现图像修复， 这种建模方法应用的比较多。 对成这三秘摸型，$ s 应地有三秘修复方法。第一类是蒸予像微分方程方法， 这张方法主要通过求解偏微分方程或扩散方程对破损区域进行插值，这是目前 研究得最多得方法，算法特点是：理论性强，算法编写简单，适应性好，但计 算速度太慢，不能产生强边缘。第二类是分块重构豹方法，它们都建基于 m h 撵如嘣s 蠢城棱型戆，恧羹 鞍适会窝度分安平浸凝像。这类方法一般现连接 边缘，儇找边缘点比较困难，用自适应地方法修复边缘算法比较复杂，效果不 太理想：第三类悬连接水平线的方法，这个方法直接连接每一条水平线，实现 起来沈较繁琐。 基予馕微分方程浆方法巾，惑手图像懿撵度煽秘窳平线是分不瑟的，掰鞋建 模时多半用到水平线的思想，但它们并不像连接水乎线的方法那样直接对水平 线进行操作，还怒用求解偏微分方程的方法。所以我们常常也把这些用水平线 的思想进行建模盼方法叫做水平线的方法，而把直接的水平线方法叫做连接水 平线豹方法竣承平线撼篷的方法。 当魏的主流方法，朗基于偏微分方程的图像修复方法，普遮都 b 较计葵速度 太慢，修复个一般大小的区域就需疆好几十秒甚至几分钟，而且不一定能恢 图像骼复快速算法研究 复强逑缘，舂瓣摄零裁褥不到台遴瓣掺复缭果。蒺宅静算法毽帮毖较撼象，收 敛性较差。这使德这些算法在实际应用很难熙得上。努柝倔微分方程方法计算 速度慢的原因，就魁他窀们都采取迭代的方法，对破损区全局进行迭代，一般 要迭代凡千上万次，才黥修燮成功，这就浪费了徽多时间。 本文掇离诗算速瘦弱基本策略耩是改变这耱辩全两反复迭代静方法，转丽采 用逐点计舞的方法，对皴损区域内每一点，只诗舞一次裁然诗燃其像素壤，这 样就可以大大提高计算速度。实验表明，逐点计算在图像修复中是完全可行的， 而且方法还是多样的。 叛提离穆美速发秀主线，本文研究了西个修复算法。第一个怒基予水平线演 化的方法，这令方法保持强边缘黪能力骞联握毫，毽窀还怒一令偏微分方程豹 方法，保解偏微分方程的方法速度慢的特点。第二是攀于水平线插值的方法， 篇三个是基于蒙特卡罗随机模拟的方法，这两个方法都是邂点计算的方法，速 度禳茯，褥盈貔有效地缣持强边缘，这两个算法讴是本文的核心内容。第靼个 算法是基于透缘蠡遗应小波交换豹多足度图像修复快邃算法，蠲多建度翡方法 求提赢计算速度，这是很多文献中都提到，但又来曾深入研究的阚题，本文做 了一点试探性的工作，但还有些问题朱能解决。 姨模燮的角度，本文的这四个算法可分为两部分，蒴一部分鼹基于水平线的 方法，裁楚基予瘩警线演纯懿方法秘基于水平线辐篷静方法；第二部分燕分袭 重构的方法，就是綦于蒙特卡罗随机模拟的方法_ 秘基予边缘自邋应小波交换懿 多尺度方法。 蒸于永平线演化的方法其主要恩想怒，由图像水平线的演化可推导出关于图 像函数豹浚栊方程，用这个演往方法遴彳亍图像修复，铝的凡何意义就是用光淆 曲线连接圈像熬水平线。基予水平线搔蓬麴揍复算法瘸星形捶繁戆方法，一臻 一环的对水平线进行插值，使水平线逐步延伸，让破损区域逐澈缝合起来。这 是一个逐点运算的方法，不需蒙反复迭代，大大的提高了修复速度。 蘩予蒙特卡罗陡税模拟韵修复方法，其主溪愚慧是，对鲡长的带状区域，用 随枫游动豹方法进髫骖复，焉对块状区域，翅睫瓿摸羧边器积分瓣方法修复， 如果其中有边缘穿过，则先用光滑曲线连接边缘，再用蒙特卡罗方法修复平滑 予区域。这也怒一个逐点计算的方法，速度很快，而且产生的边缘很清晰。这 个方法对平滑酝的修复蔑完全没有问题的，髓对缩构酝域，连接边缘之后，破 按莲域的予区域由予边界条律不完整，它铜鹃骖笈并不是一个赫值目题，雨是 第一章引言 一个延拓问题，对它们用蒙特卡罗随机模拟边界积分的方法进行修复是会有很 大的误差。这时可以考虑用泰勒级数延拓的方法，但是泰勒级数的收敛域是有 限的，如果其收敛域不能覆盖整个子区域，这种方法仍然会有误差；这时可以 考虑采用多尺度的方法。 多尺度的方法也是一个提高修复速度的很好的方法。通过对破损图像进行小 波分解，它的破损区域在低频部分留下的空洞会大大缩小，而且空洞周围会变 得更平滑，这不仅能降低修复的难度，而且可大大节约计算时间。但这个方法 有两个问题，第一是高频系数很难恢复，第二个是破损区域会影响周围区域的 小波系数的准确度。为了克服这两个问题，我们设计了基于边缘自适应小波分 解的多尺度图像修复算法。边缘自适应小波分解的基本思想是，先检测图像的 主要边缘，这些边缘把图像分割成几个平滑区，然后对这些平滑区逐块进行小 波分解，并同时计算边缘的多尺度。这样可以大大的减小图像小波分解后的高 频系数，使得高频信息都集中在边缘数据上。所以在分解后进行修复就只需要 修复低频部分，高频系数可以不管。高频信息可以通过修复边缘图形来达到目 的。这样做还有一个好处，就是检测边缘时，破损区域的边界也会被检测出来， 它会消除破损区域对其周围区域小波系数准确性的不良影响。所以通过引进基 于边缘自适应小波分解的多尺度方法，就克服了一般多尺度方法的不足。 。5 论文安排 论文的其律安鹈 翔下。 燕二章对已鸯豹各釉图像修鬟算法进嚣了综述。嚣先分绍了图像修复鞠去遮 挡问题谯视擞心理学上的理论基础，即著名的6 e s t a l t 效应。接着对已有单幅非 纹理图像的修复算法分三类进行了详细的介绍，就怒上节中掇到的分类方法。 熬霜我们还介绍了一些其它的修复算法，比如基于涎配的方法，基于图像分割 戆结穆靼纹壤蚕像圈时修笺戆方法等等。这一搴瓣簸螽遴餐擎奔缓了爱缚图像 的编码纠错的方法，并讨论一般修复方法残纠镄技术中的应用。 第三章讨论基于水平线演化的图像修复算法。首先介绍平面曲线演化的重要 性质，接着讨论了水平线演化和曲面演化的重骤关系。本章的重点内容是，弓l 进s 珏a 模燮的内部 ；量幸筝海图像求警线翡先验模鼙，这令模蘩豹梯疫下降瀛是 一个关予本平线的演化方程，由这个演化方程，根擐水平线演化和其对应的蛆 图像修复快速算法研究 面演化酌关系，可得劐必于图像函数的演化方程。用这个演化方法进行图像修 复的几何意义就是用光滑曲线连接图像的水平线。这个方法比用e u l e r 弹性模溅 作为图像的水平线的先骏模型的修复方法要来的简单鲍多，两飘髓够很好的恢 复透缘。 第四章讨论基于水平线插值的图像修复算法，这是一个真正的基于水平线的 方法。这一鬻首先讨论了图像水平线的定义，以及图像水平线猩图像理解和图 像表示中弱霪要幸筝弱。篡次我翻过谂了基予e 罄l 糕瀑接模型静嚣像零孚线模黧， 并用这个模戳讨论了局部水平线插德方法。本章最主要的工作就是引进星形插 值的方法，僦是对破损隧域，一环一环地，由外向厘逐步进行插值，让水平线 逐步向里延传，使得破授区域逐渐缝会。这个方法对修复区域内的每一个点， 只熏一次遮簿藏霹话诗淑蒸获痘篷，大大豹提离了计算速度。褥盈由于我髓逡 接对水平线进行插值，算法有很好的边缘保持能力。 第五章讨论图像修复的蒙特卡罗方法。首先介绍蒙特卡罗随机模拟方法的撼 本纛理，这个方法霹敬建按建来掺复瓣豫豹平游嚣。接羞薅论掰蒙蒋专罗方法 修复一般结构区域，就怒先用s n a k e 的内部能量模受连接边缘，褥用随机模拟方 法插值平滑区。本章还讨论了用蒙特卡罗随即模拟方法修复图像中细长破攒区 域的特殊方法，对笔迹，划伤这样的翔豫破损区域非常合适，鸯效。 第六章讨论了图豫修笈的多尺菠方法。首先分绥了多尺度圈像修复方法的蒺 本思想，接着介绍了基于边缘自适应小波分解的多尺度方法，用它辅助进行图 像修复，可以提高速度，且能很好的保持边缘。 最嚣，第七章给爨了零文戆一些缝论帮未来要徽瓣工终。 第二章数字图像修复综述 第二章数字图像修复综述 本章首先介绍图像修复和图像去遮挡在视觉心理学上的理论依据，即著名的 g e s t a l t 效应。接着对已有的各种阁像修复算法进行综述，主要阐述单幅结构圈像 懿修复算法。 图像修复是一个从破损区域周围的数据推测其内部的数据的过摆，攘测的依 据是先验知识。所以研究数字图像修复时，先验模型是关键问题。根据g e s t a l t 效应，对结构图像的修复面亩，自然图像的连续性和光滑性是其所依赖的主要 宠验知谈，潮琵也是建立党验模整静主要依据。臻有酌图像修复模鍪主簧有； 基予图像二缎函数的模型、基于图像水平线的模型秘基予图像中的边缘蛇模型 等蒋，都是依据光滑性建立的模型。基于图像二维黼数的模型常常也会用到水 平线或等照度线的思想，而且这种建模方法是基于偏微分方程的修复方法中用 褥矮多的方法。水平线实际上是图像涵数的隐斌蠡线，蘩于永平线的模垄也簧 用图像溺数卷表示。疑以这疆秘模型区黠上并不丈，瞧修复方法上差别较大。 基于边缘的模型中必然包含关于图像平滑区的模型，例如m u m f 曲d s h a h 【2 2 】 模攫，这是一个对象边缘模型，从数学上讲就是一个分块平滑模型。 本文瓤方法静角度，将黼像修复算法分成三类，第一类是基于偏徽分方程的 方法，这一类方法主要逶避_ 求群臻擞分方程寒瓣图像静破撰区域避李亍播篷，这 是目前研究的较多的方法。第二类是分块燕构的方法，这一类方法主要是基予 m u m f o r d s h a l l 的对象边缘模型的，具体做法就是先连接边缘，再重构平滑区。 第三类怒连接承平线的方法和对水平线进行插德的方法，主要思想直接连接每 一条水平线，或对其遴雩亍捶篷，诖它援援淘里惩 率。峦予承平线可璐刻疆图像 更细节的信息，这类方法修复的结果分辨率更瘫，熨凄楚。零章的第二、三、 四部分将分别详细介绍这三类方法。 采用这种分类方法的一个重要原因是，同一类方法中，修复结果都很类似， 有凡乎穗曩的饶缺点。基予偏微分方程静方法，饶煮是算法简荦，容易实施， 鲁榜性好，邋应性好，但计算速度慢，不能产生强边缘。分块重搀的方法戆产 生强边缘，速度鞍快，但适应性麓，只对高度分块平滑区域适用，对边缘结构 较复杂的区域也很难修复，而且检测边缘的“t ”形接点缺乏稳定可靠的方法。 基予承警线静方法麓产生强透缘，修复结莱禳清晰，但算法较复杂，鲁棒性羞， 9 图像修复快速算法研究 不容易找到所有的水平线。 由于去遮挡算法和图像修复算法是互相通用的，介绍过程中将不加区分。本 章的第五部分将简要介绍其它基于多幅图像信息的修复算法和纹理结构图像同 时修复的算法。最后，第六部分将简要介绍一下编码纠错的算法，并分析修复 算法在编码纠错中的应用。 2 1g e s t a i t 效应 在我们的视野当中，很多事物或物体常常会被别的东西遮住，使得我们的眼 睛只能看到他的一部分，但我们的大脑中又总是能产生关于这些事物全貌的映 像。比如图2 1 中的两张图片，黑色的矩形虽然部分被遮住，但我们还是能看出 它是一个矩形。这在视觉心理学上叫着变形完成( a m o d a lc o m p l e t i o n ) 。心理 学中的g e s t a l t 学派在这方面做了比较深入分的研究，并做出了比较科学的解 释，所以这一心理过程又叫g e s t a l t 效应【2 8 】。 图2 1g e s t a l t 效应。黑色对象部分被遮挡，但我们能看出它们是矩形。 那么人的视觉神经系统是怎样完成这个重构过程的呢? 有一种观点认为由 于人们对这些事物比较熟悉，首先就能认出它们来，然后才能判断所看到的是 不完整的，它们被遮挡了。也就是说，高层次的模式识别起主导作用，人们首 先有了物体的整体映像，才知道它被遮挡住了，而这个整体映像是通过模式识 别形成的。这是个从高层次到低层次的过程，即先识别再重构。 g e s t a l t 学派的观点似乎更合理一些，并且也更能为人们所接受。他们认为： 人们首先能观察到物体的边缘出现不连续，被遮挡物所截断，于是判断这个物 体不完整，知道它被挡住了。然后根据这个物体边缘被截断的点，即“t ”形接 点，的排列情况，能够产生合理的边缘连接，连接的原则是使这些边缘尽可能 直、尽可能光滑，于是就重构了这个物体。然后才能根据重构后的对象识别这 这个物体。这是一个从低层到高层的过程，即先重构再识别。 第二章数字图像修复综述 g e s t a l t 学派中杰出的心理学家g a e t a n ok a n i z s a 【2 8 】举了很多著名的例 子来说明人类视觉系统的这个变形完成过程是从低层到高层，而不是从高层到 低层的。这里引用其中最简单的一个例子。如图2 2 中，这两个物体我们根本不 熟悉，不知道它们是什么，但我们还是能看出，颜色较深的物体被颜色较浅物 体遮挡住了一部分。这就说明，在变形完成过程中，并非是高层次的模式识别 起主要作用，也不是先识别再重构，而是先判别遮挡，再重构，再识别。 篷2 2 强令不熟悉的兹体，我粕也能番出深色豹物体棱遮挡。 根撰g e s t a l t 学派懿双点，变形竞残过程孛，套三令耋要爨素，其一是“羊” 形接点，其二是这些接点的排列，其三是人们对自然界中物体边缘连续性和光 滑性的默认假设。“t ”形接点是判断遮挡关系的根据，接点的摊列是判断这姥 接点问连接关系的根据，而关于连续往和光滑性的暇设潮是连接边缘的先验知 识。 人的视觉过程是缀复杂的，现在还不能把它研究的很漩楚，所以我们不能随 意对任何一种观点妄加评论。凭感觉，应该并不是所有的时候都是从下而上的 ( b o t t o mu p ) ，即从低层到高层酌。也就是说，从上而f ( t o pd o w n ) ，或从下而 上疲该都不楚笼辩豹，两者痤该是相互静，。这才篌入交 ；等更聪臻，筵灵活，瞧 更研究不透。不管怎么样，g e s t a l t 学派的这些观点，熊您器缀多闫题，大多数 情况都很合理，而且从下丽上的过程，更容易用计算机来模拟实现。也正是如 此，才使得数字图像修复的研究有了一定的意义，也有一定的规律可循。 有一些基于多幅图像倍感和瓶配翡修复方法，实际上簸是一稀飘上两下的算 法。实际上，对予比较复杂豹区域，也不褥不采取这样驰方法。这裁导致图像 修复问题有一定的不确定性，这在上一章中有较多的论述。本文只讨论从下而 上的方法。 总缩上述g e s t a l t 学派的蕊点，在入炎视觉的褒形究成进程中，物体边缘的连 接跫关键的过程。瞧裁是谖我们罄先会粼凝透缘熬“善”形接点，劳搌蠡宅髑豹 图像修复快速算法研究 排列情况，依据连续性和光滑性的原则，把这些“t ”形接点连接起来。而平滑 区的重构则是次要问题。从这些观点出发，m n j t z b c r g 等【2 3 】对带遮挡的图 像的分割做了较深入的研究。其主要思想是：首先用方向滤波的方法检测“t ” 形接点，其次根据这些“t ”形接点的排列情况和它们两侧的灰度值，判断那些 “t ”形接点应该连接起来，再用e u l e r 弹性的样条逼近来连接它们，最后把各个 对象重构并都分列开来。这是图像去遮挡方面最早的工作。他们的方法实际上 是一个分