（应用数学专业论文）基于线裁剪的保特征图像缩放算法.pdf

浙江人学硕i ：学位论文 摘要 摘要 图像缩放技术是数字图像处理领域中一个研究重点。图像的分辨率调整、格式转换 和在p d a 等便携电子设备中在有限的屏幕上显示高分辨率的图像都需要使用图像缩放 技术。 传统的图像缩放技术采用插值算法，往往在缩放时会出现锯齿或者图像细节丢失现 象，并且图像的内容发生了较大的缩放变化近年来，a v i d a n 和s h a m i r 提出了一种基 于线裁剪的保持图像内容的缩放算法，通过增加或者删除视觉重要性最弱的像素线来实 现图像缩放，这样图像中的最重要的视觉信息就能在结果中保留下来。但是，由于没有 考虑图像中的高层视觉信息，算法的结果不能保持图像中重要目标物体轮廓的特征。为 此，本文提出了两种基于线裁剪的图像缩放算法： 第一种方法是基于局部调整的方法来保持图像缩放结果的特征信息。图像特征的扭 曲是由于像素线穿越图像的特征导致的，所以对于扭曲的特征要进行调整来保持特征 为此算法首先求出所有要增加或者删除的像素线，若有像素线穿越图像的特征，则将像 素线与图像特征的交点是连续的聚为一类，聚类后根据特征点的斜率和连通性对每个类 进行局部调整，调整后图像特征得以保持，克服了原算法无法保持图像特征这一问题。 第二种方法是基于一条像素线的增删对于图像特征的影响仅限于它们交点邻域这 一事实，通过引入度量特征点邻域相似性的能量函数，得到保持特征的图像缩放的能量 优化算法。若像素线穿越图像特征时采用动态规划算法找出使得调整后特征点邻域相似 性最大的路径进行局部调整，从而使得图像缩放过程中图像特征不会变形，达到保持图 像的特征的目的 关键词：图像缩放；保图像特征；线裁剪 a b s t r a c t i m a g er e s i z i n gp l a y sa ni m p o r t a n tr o l ei nd i g i t a li m a g ep r o c e s s i n g i ti sw i d e l yu s e di n v a r i o u s a p p l i c a t i o n si n c l u d i n gi m a g e r e s o l u t i o n a d j u s t m e n t , f o r m a tc o n v e r s i o n ，a n d d i s p l a y i n gh i g hr e s o l u t i o ni m a g eo nt h es c r e e no f p d a i n t e r p o l a t i o nt e c h n i q u e sa r eg e n e r a l l yu s e dt or e s i z ei m a g e u n f o r t u n a t e l y ，t h e s et e c h n i q u e s i n t r o d u c em u c hd i s t o r t i o ni nt h er e s u l t e di m a g ea n dt h e r ea l ea r t i f a c t si nt h er e s u l ts u c ha s z i g z a ge f f e c t sa n db l u r r i n gn e a rs h a r pe d g e s r e c e n t l y ，a v i d a na n ds h a m i rp r o p o s ea l l a l g o r i t h m c a l l e ds e a mc a r v i n gi m a g er e s i z i n g i tr e p e a t e d l yr e m o v e so ri n s e r t sh o r i z o n t a la n d v e r t i c a ls e a m st oc h a n g et h es i z eo fi m a g ew i t hp r e s e r v i n gt h ei m p o r t a n tc o n t e n t si nt h ei m a g e h o w e v e r ，i tc a nn o tp r e s e r v et h es h a r pf e a t u r e sa l o n g t h es i l h o u e t t e so fi m p o r t a n to b j e c t si n t h ei m a g eb e c a u s et h eh i g hl e v e lp e r c e p t u a li n f o r m a t i o ni sn o tc o n s i d e r e di nt h ea l g o r i t h m i n o r d e rt op r e s e r v et h ef e a t u r e so ft h ei m a g e ，w ep r o p o s et w oi m a g er e s i z i n ga l g o r i t h m sb a s e d o ns e a mc a r v i n gs c h e m e f i r s t ，w ep r o p o s eal o c a la d j u s t m e n tt e c h n i q u et op r e s e r v et h ei m p o r t a n tf e a t u r e si nt h e r e s i z e di m a g e a st h ed i s t o r t i o ni sc a u s e db yt h es e a m sa c r o s st h es h a r pf e a t u r eo ft h ei m a g e ， t h ea l g o r i t h ma d j u s tt h el o c a ld i s t o r t e dr e g i o no ft h es e a m st or e d u c et h ed i s t o r t i o n w e c o m p u t ea l lt h es e a m st h a tw i l lb er e m o v e do ri n s e r t e d i ft h e r ea r es e a m sc r o s s i n gt h es h a r p f e a t u r e so ft h ei m a g e ，w ec l a s s i f yt h ei n t e r s e c t i n gp o i n t si n t od i f f e r e n tc l u s t e r s f o re a c h c l u s t e rw ea d j u s tt h ei m a g el o c a l l ya c c o r d i n gt ot h es l o p ea n dc o n n e c t i v i t yi n f o r m a t i o nt o p r e s e r v et h ef e a t u r e s w ea l s op r e s e n ta ne n e r g yo p t i m i z a t i o na l g o r i t h mb yi n t r o d u c i n gt h ee n e r g yf u n c t i o nt h a t r e p r e s e n t st h es i m i l a r i t yo ft h ef e a t u r ep o i n t sn e i g h b o u r h o o db a s e d o nt h eo b s e r v a t i o nt h a t o n es e a mo n l yi n f l u e n c e st h en e i g h b o u r h o o do ft h ep o i n to fi n t e r s e c t i o n w h e nas e a mi n t e r s e c t st h ef e a t u r e so ft h ei m a g e ，w ec a nu s ed y n a m i cp r o g r a m m i n g a l g o r i t h mt o f i n dt h eb e s ta d j u s t i n gp a t ht og e tt h em o s ts i m i l a rn e i g h b o u r h o o da f t e r a d j u s t m e n t s ot h ef e a t u r e so ft h ei m a g ew i l l n o ts u f f e rd i s t o r t i o na n dt h er e s i z e di m a g e p r e s e r v e st h ef e a t u r e so ft h eo r i g i ni m a g e k e yw o r d s ：i m a g er e s i z i n g ；f e a t u r ep r e s e r v i n g ；s e a mc a r v i n g m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成 果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得逝江太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 学位论文作者签名：签字日期：年 月 e t 学位论文版权使用授权书 本学位论文作者完全了解浙坚太堂有关保留、使用学位论文的规定特授权 浙塑太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、 缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国家有关部门或机构送 交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名i 签字日期：年月 日 导师签名i 签字日期：年月 致谢 致谢 我很荣幸能够在攻读硕士学位期间师从刘利刚副教授，本文正是在刘老 师的认真指导下完成的。刘老师渊博的知识、严谨的治学态度、为人师表 的品格、孜孜不倦的进取精神和富于创新的科学精神以及对知识和学术执 着的追求精神，一直深深的感染并激励着我，给我留下了深刻的印象。我 的每一点成绩、每一次进步无不渗透着刘老师的心血。籍此论文完成之际， 谨向我的导师致以深深的敬意和衷心的感谢! 在求学期间和论文撰写过程中，浙江大学数学系计算机辅助几何设计与 图形学课题组的汪国昭教授、王国瑾教授和杨勋年副教授在各方面都给予 我极大的支持和帮助，衷心的感谢诸位老师对我的教导和帮助，感谢课题 组的陈仁杰、张磊、张冬梅、计忠平、陈中贵、沈莞蔷、曾兰玲、陆立正、 胡倩倩、陈军、曹娟、周红光、方林聪等师兄师姐师弟师妹们的帮助。 能够顺利完成学业，除了有课题组提供的良好的科研环境外，生活环境 的愉悦也是必不可少的。因此在这里还要感谢室友蔡庆重、加帮平、朱升 峰，感谢好友马昊迪、狄建涛、施红星、张丰伟、林成春、庄成明、孟敏、 冯敬真、刘颖等，陪我度过了许多难忘的时光。 最后特别感谢我的父母和女朋友对我自始至终的爱和支持，正是他们无 私的奉献和支持，才使我得以顺利完成学业。 谨以此文献给所有关心、支持和帮助过我的人们! 邓会鹏 20 0 8 年5 月于求是园欧阳纯美楼 浙江人学硕i j 研究生学位论文 绪论 1 绪论 1 1 引言】 据有关研究表明，人类所获取的全部信息中，有8 0 以上来源于视觉。与文字信息 相比，图像可以包含更多的信息量、更加直观丰富而通常意义上的图像都是连续的图 像，产生的图像也都是模拟信号，由于对模拟信号处理手段及其自身的原因，现在研究 对象从模拟领域延伸到了数字领域，于是产生了数字图像 在2 0 世界6 0 年代早期，在美国加利福尼亚的喷气推进实验室人们对“旅行者7 号” 卫星传送的月球图像进行处理，这是数字图像处理在空间方面比较早的应用在2 0 世 纪6 0 年代末7 0 年代初数字图像处理技术也在医学图像、地球遥感检测等领域有了应用。 在2 0 世纪7 0 年代发明的计算机轴向断层术( 简称c t ) 是图像处理在医学诊断领域最 重要的应用之一从那时起，图像处理得到了蓬勃的发展，除了上述应用外，计算机程 序用于增强对比度或将亮度编码为彩色，以用于生物学等其他领域的图像在考古学领 域，使用图像处理方法已成功复原了模糊的图片，在物理学中计算机技术也可以增强高 能等离子和电子显微镜等领域的实验图像。图像处理技术也成功应用在天文学、国防及 工业领域中。 数字图像处理包含很多个方面，每个方面均有丰富的内容，都可作为独立的领域进 行研究，主要研究内容有以下几个方面： 图像增强和图像复原是为了提高图像的质量图像增强突出图像中所感兴趣的部 分；图像复原技术倾向于以图像退化的数学或者概论模型为基础，再采用某种滤波方法， 恢复或重建原来的图像而图像压缩所涉及的技术是减少图像的存储量，或者在传输图 像时降低频带图像分割则是将一幅图像划分为组成部分或者目标物。图像识别主要内 容是图像经过某些预处理( 增强、复原、压缩) 后，进行图像分割和特征提取，从而进 行判决分类除此之外，数字图像处理还包括形态学处理、图像显示等方面，总而言之， 它是包含多种技术和方法的一门学科 浙江人学顾f ：研究生学位论文绪论 随着互联网的发展和计算机的普及，图像又是人类获取和交换信息的主要来源，因 此数字图像处理的应用领域必然涉及到人类生活和工作的方方面面，数字图像处理也将 有更广阔的前景 1 2 图像缩放技术概述 图像的放大缩小是图像处理的一个基本操作；简称为图像缩放。图像缩放操作本 身是指图像分辨率的改变，在图像的显示，传输，分析以及电影电视等领域均有广泛 的应用比如1 7 英寸的l c d 显示器在1 2 8 0 1 0 2 4 分辨率下全屏显示1 0 2 4 x7 6 8 的 数字图像，就要事先对显示信号进行处理，将其放大为1 2 8 0 x1 0 2 4 的画面再显示出 来。 数字图像是由像素组成的二维矩阵，对图像进行缩放，要利用已知的信息和先验 知识来对未知的像素进行估计图像缩放的方法分为两类，几何变换缩放算法和保持 图像内容缩放算法。 1 2 1 几何变换缩放算法2 几何变换是图像缩放发展早期的缩放算法比较著名的有以下几种： 1 2 1 1 均值法( m e a ni n t e r p o l a t i o n ) d 1 均值法是几何变换算法的基础，原理也比较简单设原始图像为i ，放大后的图像 为a ，设放大的倍数为形( 水平和垂直放大倍数一致) ，对于放大后图像a 每个像素赋 值就可得到放大后的图像。对于放大后图像中的一点p 像素坐标为似y ) ，对应原始图像l 中的坐标为0 w , y w ) 比如将1 0 0 x1 0 0 的图像放大到2 0 0 x2 0 0 ，对于放大后的图像 中的点a ( 2 5 ，2 5 ) 对应原始图像中的i ( 1 2 5 ，1 2 5 ) ，因此i ( 2 5 ，2 5 ) 的像素值就是( a ( 1 2 ，1 2 ) + a ( 1 2 ，1 3 ) + a ( 1 3 ，1 2 ) + a ( 1 3 ，1 3 ) ) 4 均值法的优点是计算简单，易于实现，但是对于图 像细节和边缘等高频信息不能很好的保持，放大后图像变得很模糊。 2 浙江人学颂i ：研究生学位论文 绪论 1 2 1 2 最近邻域法( n e a r e s tn e i g h b o r ) d 1 均值法本质上是对原始图像中的相邻点简单平均，所以起到的是均值滤波的作用。 这样就是保留低频信息而损失了高频信息，图像放大后细节会比较模糊，放大效果不好 为了保持图像的细节，可以采用最近邻域法它的原理如下：设原始图像l 大小为1 0 0 1 0 0 ，放大后的图像为a 为3 0 0 x3 0 0 ，放大后图像中的a ( 1 0 0 ，1 0 0 ) 对应原始图像1 ( 3 3 ， 3 3 ) ，这样就可以比均值法更好的保持图像细节 1 2 1 3 双线性插值法( b i l i n e a ri n t e r p o l a t i o n ) 1 4 - 5 1 最近邻域法在细节保持上虽然有改善，但是放大后的图像方格效应比较明显，因此 要进一步改进。双线性插值法在插值的时候考虑插值点周围像素对插入点的贡献，与前 面两种直接映射到原图像的方法不同，双线性插值法对于空间距离不相同的点，对插入 点像素值的贡献也不同。它的原理如下( 以水平放大为例) ： 原始图像中的一行 1 1d1 2 1 3 q a 夕0 t1 - t 图1 - 1 双线性插值法示意图 对于原始图像l 水平方向进行形倍的放大，得到放大后的图像a ，则a 中的像素点 似y ) 对应于l 中的g 彬力，如上图所示，设“力对应于图中的d 点若像素的间隔为 1 ，则d 点的像素值为n - o f ) 木l l + t 奉1 2 ，用这种方法就可以求得放大后图像a 中的所 有像素值同前面的两种方法相比，双线性插值法保持图像细节的效果更优。 1 2 1 4 双三次插值法( b i c u b i c ) m 双线性插值法只是考虑空间距离上不同对缩放效果的线性影响，没有考虑图像纹理 对缩放的影响，因此放大后的图像在缩放比例比较大的时候仍然会有锯齿效应。双三次 3 浙江人学硕j ：研究生学位论文绪论 内插法就是考虑了图像纹理的影响提出的。仍以水平放大为例，设放大后的图像的像素 点映回到原始图像中的d 点，如下图所示： 原始图像中的一行 l l1 2d1 3 1 4 0 屯夕0 t 1 t 图卜2 双三次插值法示意图 d 点的像素值由与其临近的四个像素点n 到1 4 来决定，设d 的像素值为g c d ) ，n 到 ，4 的像素值分别为n 1 ) ，f ( 2 ) ，f ( 3 ) ，f ( 4 ) ，则双三次内插的公式可以表示为 “叫2 + f ( 1 1 ) ( - s a + 3 + 4 2 s 2 - s ) 2 + + f ( 1 2 ) ( 3 s 3 f ( 1 3 ) ( - ss ) 2f ( 1 4 ) ( s 善) 了y ( 1 1 ) + 4 s 2 + + 一s 2 ) 2 双三次内插法考虑了图像纹理对插值的作用，在上述方法中缩放效果是最好的但 是相对于其他三种方法，计算量也是最大的。 1 2 2 保持图像内容缩放算法 几何变换的图像缩放算法原理简单，计算量小，易于实现但是几何变换的图像 缩放算法对于图像中所有内容进行等比例的放大或者压缩，所以图像的失真比较严重 在最近几年中，保持图像内容的算法得到了比较大的发展，现在介绍如下 1 2 2 1 基于图像裁剪或变形( i m a g ec r o p p i n g w a r p i n g ) 缩放算法 保持像的内容最为重要的是保持住图像中重要区域的特征一个思路就是找出图像 中的特征区域，对特征区域外的部分进行剪裁，这样就可以在保持住图像中重要区域的 特征同时完成图像缩放这样就必须采用一定的方法来检测图像中的重要区域通常采 用的方法有两种：一种是采用v o i l a 和j o n e s l 8 l 提出的人脸探测器( f a c ed e t e c t o r ) 的方法 来寻找图像中的重要区域，另外的一种方法是l t t i l 9 l 等人提出的构建图像特征r e ( s a l i e n c e m a p ) 来实现图像重要区域的探测s u b l l o l 等人利用上面方法来获取图像中的重要区域， 4 浙江人学硕i ：研究生学位论文绪论 提出了一种为大量图像创建缩略图的方法。s a n t c l l a 等人i l l j 则是根据人眼聚焦的位置利 用前面提到的技术能够智能裁剪图像，得到用户想要的裁剪结果。上述方法都是缩小图 像的时候可以使用，对于图像的放大的情况并没有涉及，同时这两种方法要依赖原有的 图像裁剪技术 使用图像变形技术来实现图像缩放是另外一个思路。i j u 和g l e i c h e l l 2 l 时利用s u h 等 人【1 0 】文中的方法找到感兴趣 域( r e g i o n o f - i n t e r e s t ) ，提出了一个非线性的鱼眼变形函数 ( f i s h - e y ev i e ww a r p i n g ) 来保持住感兴趣区域，同时这个函数对图像的其他部分变形程度 也不是十分严重。这样当用户指定缩放后图像的大小时就可以用上述方法实现图像的缩 放。但是图像中感兴趣的区域若是多于一个，算法结果不是很稳定。w o l f 等人1 1 3 l 综合 了v o i l a 和j o n e s l 8 】提出的人脸探测和图像梯度的信息去检测图像中的重要区域，对于重 要区域的变形较小而其余区域的变形较大，通过求解关于像素点变形后的位置的方程来 实现图像的缩放 1 2 2 2 基于线裁剪( a mc a r v i n g ) 的保持图像内容的缩放算法 这是2 0 0 7 年在s i g g r a p h 上由a v i d a n 和s h a m i r l l 4 i 提出的算法，也是本文工作的 基础，所以在本节对该算法进行详细的介绍。所谓线裁剪，指的是通过删除或者插入8 连通的水平或者垂直穿过整幅图像的像素线来达到图像缩放的效果为了保持图像的特 征，删除或者插入的像素线必须是图像中重要性最弱的为了定义像素线的重要性，首 先要定义图像中像素点的重要性。文章中提出用能量函数来定义像素点的重要性，这个 能量函数可以是图像的梯度的一范数，如果设图像为l 则能量函数的定义如下： 州，一驯+ 引 2 ， 上述的能量函数实际上就是图像的梯度，在图像缩小的时候每次都移除能量最小的 像素线来来保持图像的主要特征，而在图像放大的时候则将能量最小的线插入到原始图 像中来放大图像从而达到保持图像内容的目的。下面以对图像缩小为例，详细介绍该算 法。 5 浙江人学硕l ：研究生学位论文 绪论 设原始图像i 的大小为t i x m ，其中刀为列数，m 为行数因为是缩小图像，所以要 删除像素线设删除的垂直像素线为c v ，则可以表示为 c 9 一 c ，) 二。- ( 工( f ) ，i ) ) 王。，j f vf ，l z ( f ) 一z ( f 一1 ) i 手1 ( 1 3 ) 其中x o ) 是映射：x ： 1 ，卅一b ，n 。从上面的公式可以看出，垂直像素线是从图 像的第一行到最后一行的像素组成的8 连通路径，每行有且仅有一个像素被删除。类似 的，设水平像素线为一，则c 6 可以表示为 。c 一 c ；) ：。一 ( ，) ，( ，) ) ) ：。，j f vf ，i y ( ，) 一y ( j 一1 ) l 1 ( 1 4 ) 其中y ( d 是映射：) ，：n ，刀】叫1 ，叫，水平像素线是垂直像素线是从图像的第一列 到最后一列的像素组成的8 连通路径，每列有且仅有一个像素被删除 在删除垂直像素线后只需将该像素线的右侧图像向左移动一个像素就可以填补删 除的像素线，同理，若删除的是水平像素线就将水平像素线下方的图像向上移动一个像 素就填补删除的水平像素线通过像素线的删除我们就实现了图像的缩小。 通过前文的叙述，我们已经知道了删除的像素线的性质，但是如何找出这样的像素 线是关键首先，我们找到的像素线能量是最小的，记像素线c 的能量为e ( c ) ，则能量 最小的垂直像素线可以表示为： e ：- m 。i ne ( c ) - m ? n 霪州( c ，) ( 1 5 ) 其中邮( c ) ) 为像素点c 处的能量。 对于水平删除的像素线，类似的有 el m ，i ne ( c ) - m ? n 芝州( c ，) ) ( 1 6 ) 其中e ( ，孵) ) 为像素点q 处的能量。 能量最小的像素线的寻找采用动态规划算法1 1 5 l 求解。若想找出能量最小的垂直像素 线，对于图像l 中的像素点o ，j ) ，记该点的累积能量为推，d ，则有 m ( i ，j ) = e ( i ，) + m i n ( m ( i 一1 ，j 一1 ) ，m ( i ，j 一1 ) ，m ( f + 1 j 一1 ) 1 ) ( 1 7 ) 6 浙江人学硕i ：研究生学位论文 绪论 为此只需遍历图像l 中的第二行到最后一行计算上述的累计能量。最后一行中累 计能量最小的点就是能量最小的垂直像素线的终点。然后从这点回溯回去，每次都寻找 已找到的累计能量最小点的上一行8 邻域中累计能量最小的像素点，依次进行直至图像 的第一行就找到了能量最小的垂直像素线 对于寻找能量最小的水平像素线，则像素点g ，d 处的累计能量聊，d 为 m ( i ，_ ) = e ( i ，i ) + m i n ( m ( i - 1 , j - 1 ) ，m ( f - 1 , j ) ，肘( f - l , j + 1 ” ( 1 8 ) 对列采用上面对行的策略就可以找出能量最小的像素线，这里不再重复。 如果只是对原始图像高度或者宽度进行缩小，那么每次只需找到图像中能量最小的 水平或者垂直像素线删除就可以了。但是对于图像的高度和宽度都缩小的时候，删除水 平和垂直像素线的顺序需要进行决定，对此文中给出了如下的选择策略。若将n x m 的 原始图像l 缩小为厅耐，其中n ，所以先进行水平像素线的删除。算法首先要检测图像的特征，并用多边形来逼近这 些特征本文采用c a n n y 边缘检测算法1 2 0 l 来检测图像的特征，也可以由用户交互在图像 上选择想保持的特征图像特征获取后采用2 1 2 的方法得到特征的多边形表示。 2 2 2 删除的水平像素线与图像特征相交的交点聚类 因为缩放后图像的宽度为m k ，所以首先用动态规划算法找出欲在图像中删除的k 条累积能量最小的水平像素线，若这七条水平像素线与图像特征均没有相交，那么就不 用做任何处理，再进行图像高度的缩放若这k 条水平像素线与图像特征有交点，对每 个交点单独进行调整来保持特征效果不理想，因为这样做累计误差比较大，对于删除的 特征点是连续的时候这样做误差尤为明显所以在将删除的水平像素线与图像特征的交 点全求出以后，要对这些交点进行聚类若交点是连续分布且斜率相同，将它们聚为一 类，其余的则单独为一类这样可以进行更准确的调整来保持图像的特征。 2 2 3 判断图像特征的改交情况 对于图像的特征的改变情况的判断，主要考虑两个因素：删除行前后特征点的连通 性是否改变和特征点的斜率。 特征点的连通性指的是若特征点在没有被删除前特征是8 连通的，删除后这个点特 征是否还是8 连通下面以图示说明这个问题 浙江人学碗i 目f ，生学位论!性特缸脚像缩欣的局整算法 群辅辣群 ( a ) 原始图像特征 ( b ) 删除特征点 后结果 ( c ) 原始图像特征( d ) 删除特征点 后结果 固2 - 5 田像特征连通性 ( a ) 删除2 0 行( 红线所示)( b ) 删赊2 0 行的结果( c ) 局部调整后结果 圈2 - 6 删除2 0 行的结果对比 氢 h ) 捌睬2 0 行( 红线所示)( 吣局部调整后结果 囤2 - 7 保特征局部调整结果 如上页图2 - 5 ( a ) 所示，红色点表明当前像素点是图像的特征点对于a 点而言，a 点就是特征8 连通的如果删除a 点，则如图2 - 5 蚴所示，a 点的连通性就被改变，所 以要进行删除垂直像素线的局部调整保持来保持特征的连通性 浙江人学硕f ：研究生学位论文保特征图像缩放的局部调整算法 对于图2 - 5 ( c ) 来说，a 、b 、c 、d 均是图像的特征点，若删除的特征点只有a ，那 么可以得到图2 - 5 ( d ) 1 钓结果。删除a 点后特征点d 代替了a ，特征的连通性没有改变 这时就不必进行删除垂直像素线的调整。 斜率对于如何进行保持图像特征的调整是很重要的，对于不同的斜率有不同的处理 方法首先对于斜率是无穷大和斜率是零的情况不进行处理，经过实际例子测试，在这 两种特殊情况下删除行后对图像特征的影响不明显，所以算法中没有对这两种情况进行 考虑。对于斜率是其他取值的时候，按照绝对值的大小，分为大于等于一和小于一两种 情况采周不同的处理策略。 首先，对于斜率绝对值大于等于一的情况，为了更清楚的表明算法的过程，我们考 虑下面图像中斜率为1 5 的直线将这条直线作为图像的特征，对于删除像素线的不同 聚类情况采用不同的处理方式 对于聚类后类中的特征点的数量大于1 的，像上页图2 - 6c o ) 中a 处是连续删除4 条像素行的部分，对于这种情况，记连续删除的水平像素线的数量为，l ，而被删除的特 征点的斜率为kj 则为保持图像特征应删除的的垂直像素线的数量为n k 。若n k 不是 整数，要考虑如何取整。取整的准则是如果删除下取整数量的垂直像素线后可以使该特 征点处是连通的，则删除的数量就是下取整的数量，若不连通就是上取整的数量。对于 本例而言，4 1 5 = 8 3 ，删除2 条垂直像素线就可以保证图像的连通性，所以下取整。对 于单独为一类的特征点，如上页图2 6 ( b ) 中b 处的点，这个时候删除垂直像素线就看被 删除的特征点的连通性是否改变，没有改变就不必删除，反之则删除上图中连通性没 有改变，所以没有删除垂直像素线采用上面的调整方法，得到的结果就是图2 - 6 ( c ) ， 直线特征得到保持 其次对于斜率绝对值小于一的情形，删除垂直像素线的策略与斜率大于一的情况中 聚类后特征点的数量大于一的情况一致这里不再重复，仅以一例说明一下 上页图2 - 7 ( a ) 中黑色直线的斜率为o 7 5 ，红色的粗线是连续四条删除的水平像素线删 除的垂直像素线的数量为4 0 7 5 = 1 6 3 ，实际删除的数量为5 对于删除的单独的水平像 素线与图中黑色直线相交的特征点位置删除的垂直像素线的数量为i 0 7 5 = 4 3 ，实际只 浙江人学硕j ：研究生学位论文保特征图像缩放的局部调整算法 删除1 条垂直像素线。经过上述调整后得到的结果如图2 - 7 ( b ) 所示，直线的特征得到了 保持。 2 2 4 图像宽度修正 由于在2 2 3 节中算法为了保持图像的特征而删除了垂直像素线，而图像缩小后的 宽度为n - ，这样会导致图像宽度未必是甩一，为此要进行图像宽度的修正。对于多删 除的垂直像素线要补回到图像中，反之则要继续删除垂直像素线。 若当前图像的宽度矗大于n 一，则每次删除当前图像中能量最小的垂直像素线直至 图像的宽度为n 一，；若当前图像的宽度n 小于疗一，则要求出当前图像中能量最小的 n - f n 条垂直像素线，然后在这些能量最小的垂直像素线右侧插入像素线，颜色值为能 量最小的像素线与其右侧相邻像素的颜色值的平均值。至于能量最小的像素线的求法， 仍然是采用1 2 2 2 中提到的动态规划算法求解 2 2 5 算法的完整过程 在2 2 1 到2 2 4 小节中，我们分步骤详细叙述了保特征图像缩放的局部调整算法的 每一个步骤，对于各种可能的情况进行了讨论现在对整个算法进行一个总结，算法的 各步骤如下： 1 输入原始图像和缩放后图像的高度和宽度。 2 计算图像高度的改变量和图像宽度的改变量，比较这两个改变量的绝对值大小， 从绝对值大的方向开始图像的缩放 3 使用c a n n y 边缘检测算法检测图像的特征，提取轮廓后用d o u g l a s p e u c k e r 算法 得到特征的多边形表示 4 对于改变量大的方向，采用动态规划算法找到所有欲删除或者增加的像素线，并 对这些像素线与图像的特征的交点进行聚类，斜率相同且位置连续的交点聚为一类若 没有任何交点，不进行任何调整，算法退出 5 对于每一个聚好的类，根据斜率和图像改变后特征点的连通性计算删除或者增加 的像素线数量，然后进行局部调整以保持图像的特征 6 对于改变量小的方向进行修正：若是在步骤5 中多删除了像素线，则在当前的图 像中用动态规划算法找到相应数量的累积能量最小的像素线插入到图像中反之则要删 除这些像素线修正完成后得到缩放后的图像，算法结束 1 6 浙江人学碰i 。w f 究生学位论立保特征削像缩放的月部调整算法 2 3 算法结果比较 我们在v c2 0 0 5 编译环境下，c p u 为2 8 g ，i g r a m 的条件下实现了上述算浩。 下面的富士山图像的太小为3 8 3x 1 0 6 ，图2 1 7 和图2 1 8 结果均是图像的高度减少4 6 ， 图像的宽度没有变化，缩小后图像的大小为3 8 3 x6 0 ( a ) 富士山原始图像( b ) 删除的4 6 条水早像素线( 固中红线 ( c ) a v i d a n 和s h a m ir 的算洁结果 ( d ) 本章算法结果 图2 - 8 富士山图像缩小结果对比 图2 - 8 ( a ) 是富士山原始图像，田28 ( b ) 中的红线是删除的d 6 条水平像素线，图 2 - 8 ( c ) 是a v i d a n 和s h a m i r 的算法1 1 4 l 的结果，图28 ( d ) 是本章算法的结果 对比结果可以看出，a v i d a n 和s h a m i r 的算法l “l 对富士山的特征保持得不好，左面 的山坡被拉长了，没有保持住原始图像中的山坡特征而本章算法的结果没有这个问题， 不仅富士山的主体保持住了，而且山坡的特征也保持 匕较完好。 对于圉像放大的情形，我们将富士山图像的高度增为1 6 0 ，宽度没有改变，仍是1 0 6 ， 得到的结果如下： f 。王 一 一 j 壶0上i k _ ：_ ( a ) a v i d a n 和$ h a m ir 的算法结果( 砷本章算法结果 宙2 - 9 富士山图像放大结果对比 结果对 匕一目了然，图2 - 9 ( a ) 中h v i d a n 和s h a m i r 的算法1 结果完全没有保持住富 士山的两个山坡，山坡错切的比较严重而本章提出的算法得到的结果田2 - 9 ( b ) 明显优 于他们的结果，山坡特征完好保持 浙江人学碗l t 研究生学位论文嘴幽散嘧破的局部调船算法 下面是五角石图像的缩小，图2 1 0 ( a ) 为五角石原始图像，大小为6 0 0 x4 5 0 ，将其 缩小为5 5 0 x2 0 0 ，删除的像素线如图2 1 0 ( b ) 所示 ，嚣7 _ ( a ) 五角石原始田像 r 霹 ：、 - 三。， n ( c ) a v i d a n 和s h a m ir 的算法结果( d ) 本章算法结果 囤2 - 1 0 五角石图像缩小结果对比 对 匕图2 - l o ( c ) a v i d a n 和s h a m i r 的算法1 结果与田21 0 ( d ) 本章算法的结果，可以 看到目2l o c ) 五角石的形状改变较大，且五角石的影子扭曲比较大图21 0 ( d ) 则有 较好的结果，五角石的形状只有左下角的部分变化稍多，而五角石的影子则没有影响 24 本章小结 本章提出了保特征图像缩放的局部调整算法：若像素线的增删影响了图像的特征， 则根据被影响的特征点的斜率和连通性进行局部调整来保持图像的特征，最后再进行图 像大小的修正柬完成图像缩放通过与a v i d a n 和s h a m i r 基于线裁剪的缩放算法”的结 果对比，表明本章提出的算法可以保持住图像的特征，改进了原算法不能有效保持图像 特征的这一问题 ! 。 f 一 浙江 学顾i ， f 究生学位论空雠征创像缩m 能釜优化掉往 3 保特征图像缩放的能量优化算法 在第二章中我们提出了保特征图像缩敲的局部调整算法针对a v i d a n 和s h a m i r 基 于线裁剪的缩放算法l “ 对于图像的特征保持不理想的情况进行了改进。从算法的过程可 以看出，对于如何调整被改变的特征使其与原始图像中特征保持一致是关键。而一条像 素缦的增删对特征的影响是局部的，对这个局部的特征的保持是关键所在。为了说明这 点，我们先看一个目像水平缩小的例子 ( a ) 原始图像特征( b ) 删除承平像素线( 蓝线 ( c ) 删除像素线后的结果( d ) 奉章算法调整后的结果 图3 - 1删除水平像素线翦后对比 围3 - 1 ( a ) 中红色标记的是圈像中某处的特征，图3 - 1 嘞蓝色的线表示欲删除的水平 像素线，删除的像素线经过特征点a 删除水平像素线后，在水平像素线以下的部分向 上秽动一个像素来填补删除的水平像素线，此时这处的图像为固3 - 1 ( c ) 我们可以看出 删除一行水平像素线对图像的特征的影响是局部的，上面例子中只是a 点的处的特征改 变了，其他特征则没有受到影响，所以为了保持a 点处的特征，只需对a 点进行局部 浙江人学硕l j 研究生学位论文 保特钲图像缩放的能量优化算法 处理就可以了，可以删除经过a 的垂直像素线，如图3 q ( 0 所示，这样就可以保持住图 像的特征。 基于一条像素线的增删对特征的影响是局部的这一事实，在本章中我们引入能量函 数来度量图像缩放前后特征的邻域相似性图像缩放前后特征保持得越好，则特征邻域 的相似性越大，能量也就越低本章将给出使得能量最低的调整方法，调整后的图像是 可以保持住图像的特征为此，我们首先给出能量函数的定义。 3 1 能量函数的定义 通过前面的讨论，我们已经知道：删除或者增加一条像素线对图像特征的影响是局 部的所以我们可以用被改变的图像特征点的邻域的相似性来度量特征的改变情况。若 记原始图像为，改变后的图像为i ，被改变的图像特征点为p m ，则特征点p 厅。，的 邻域能量定义为 l i ( p ，。，) 。，苫，i ，( j ，y ) 一j i j ，y ) 1 2 3 1 j ， o 其中。， ，。分别为以p ，f 。，。、图像改变后p 细。的位置为中心的k k 的大 小的作用域( 七为奇数) ，j “力，0 ，y ) 分别代表对应像素点的颜色值对于图像改 变后p 枷的位置如何选取，对于不同的情况也有不同的选择是删除水平像素线，由 于在水平像素线下的像素点均向上移动一个像素位置，所以图像改变后p 柚的位置比 原来也向上移动了一个像素位置；若是删除垂直像素线，则在垂直像素线右侧的像素 点均向左移动一个像素位置，所以图像改变后p 佬。，。的位置比原来也向左移动了一个像 素位置。对于增加像素线的情况与删除像素线的情况刚好相反，增加水平像素线时图像 改变后p 扣。，。的位置比原来向下移动了一个像素位置，而增加垂直像素线后p 知，。的 位置比原来向右移动了一个像素位置对于每一次进行的删除或者增加像素线，只需看 对应上述的哪种情况，就采用相应的方法判断图像改变后p ，。的位置 浙江人学硕l ：研究生学位论文 保特征图像缩放的能量优化算法 由于保持图像特征是最为关键的，所以对于特征点与非特征点能量的权应该不同， 由于我们要保持图像的特征，所以特征点的权应该比较大，而其他非特征点的权重相应 应该比较小所以上面能量函数的定义修改为 e ( p f e a t u r e ) t l ，( x 。，y 。) 一1 ( z 。，y 。) 1 2 j y t e 口t u r e 。，7 f 。4 。7 。 。， ( 3 2 ) “m 磊胁。巩) - ，( 咖2 ) 1 2 l 屯，2 t f e a t u r e 其中f e a t u r e 代表k 七作用域内特征点集合，0 o ，则删除后图像的大小为n - l m k ，以下详细介绍算法的流程 首先，算法仍是检测图像的特征并用多边形逼近图像的特征，这与第二章中的保特 征图像缩放的局部调整算法相同，这里不再赘述其次决定删除像素线的顺序，由于 k l 0 ，所以先从删除水平的像素线开始进行图像缩小若删除的水平像素线与图像的 特征有交点，则要决定是否进行局部调整来保持特征 3 2 1 判断是否进行局部调整保持特征 当删除的水平像素线与图像的特征有交点的时候，是否要进行局部调整来保持图像 的特征有两个因素要考虑：特征点的斜率、特征点被删除后其邻域的能量。 浙太学顿i 目f 究生学位论文 侏特征目像缩破的能i 优化算法 o _ o ( a ) 原始田像特征( b ) 删睬水平像素线( 蓝线)( c ) 删除像素线后的结果 图3 - 2 斜率大干等于1 的时删除水平像素缦的结果 ( a ) 原始图像特征 o ( b ) 删除一条水平像素线( 圉中蓝缦) ( c )