基于最短路径的图像着色毕业论文设计

PAGE毕业设计题目：基于最短路径的图像着色院：电气信息学院专业：电子信息工程班级：0701学号：200701030119学生姓名：许凤英导师姓名：张可为老师完成日期：2011.06诚信声明本人声明：1、本人所呈交的毕业设计是在老师指导下进行的研究工作及取得的研究成果；2、据查证，除了文中特别加以标注和致谢的地方外，毕业设计中不包含其他人已经公开发表过的研究成果，也不包含为获得其他教育机构的学位而使用过的材料；3、我承诺，本人提交的毕业设计中的所有内容均真实、可信。作者签名：日期：2011毕业设计任务书题目：基于最短路径的图像着色姓名许凤英学院电气与信息学院专业电子信息班级0701学号200701030119指导老师张可为职称讲师教研室主任刘望军陈爱萍基本任务及要求：着色是一种给黑白图像、电影或电视节目加上颜色的计算机辅助处理技术，在影视、医疗、太空探索及其它许多工业及科学领域有着广泛的应用，同时也一直是图像处理中一个活跃的、有挑战性的研究课题。最短路径表示从图像中一点到另一点的灰度变化最平缓的路径，将它作为混色权重可以把着色问题转化为混色问题求解。设计要求：1． 熟悉彩色化以及最短路径理论。2． 用matlab语言编程实现基于最短路径的黑白图像着色算法。3． 完成毕业论文。进度安排及完成时间：1、第1～2周：课题调研、文献检索。2、第3～6周：毕业设计开题报告、文献综述3、第7周：总体设计，完成方案的选择4、第8～9周：确定数据模型，算法实现5、第10～11周：基本算法验证、编程实现6、第12～13周：论文撰写。论文初审，定稿。7、第14周：答辩。目录摘要 1Abstract 2第1章绪论 31.1概述 31.2课题发展现状和前景展望 31.3论文内容 4第2章基于最短路径的图像着色 52.1图像着色的介绍 52.1.1图像着色 52.1.2颜色与色彩空间 72.2最短路径的介绍 102.2.1最短路径 102.2.2最短路径的定义 102.2.3最短路径的基本思路 122.1.4最短路径的基本方法 132.3利用短程线距离进行颜色混合 17第3章最短路径的图像着色在MATLAB中的实现 193.1MATLAB的介绍 193.2MATLAB的特点 203.3基于最短路径的图像着色在MATLAB中的实现 213.4基于最短路径的图像着色的结果 26结束语 30参考文献 31致谢 33基于最短路径的图像着色PAGE33基于最短路径的图像着色摘要：彩色化是一种给黑白图像、电影或电视节目加上颜色的计算机辅助处理技术，在影视、医疗、太空探索及其它许多工业及科学领域有着广泛的应用，同时也一直是图像处理中一个活跃的、有挑战性的研究课题。本论文的研究课题是基于最短路径的图像着色，本文分别介绍了图像着色和最短路径的方法，然后两相结合提出了利用短程线距离进行颜色混合的算法来实现最短路径的图像着色。基于最短路径的图像着色是一种快速的图像着色方法，在对黑白图像进行局部颜色涂抹得到涂抹图像后，运用颜色扩展的方式使整幅图像彩色化。最后编程运用Matlab软件实现。关键词：图像着色，彩色化，灰度图像着色，最短路径ColorImagesBasedontheShortestPathAbstract:Colorizationisacolorprocessingtechnologywithcomputer-aidedtomakecolortoblackandwhiteimage,filmandTVshow.Filmandtelevision,healthcare,spaceexplorationandmanyotherindustrialandscientificfieldshasbeenwidelyused,butalsohasbeenanactiveandchallengingresearchtopicinimageprocessing.Researchofthisthesisisawayofcolorimageswhichbasedontheshortestpath,thethesisintroducedtheimagecoloringandshortestpath,andthencombiningthetwoproposedgeodesicdistanceusingcolormixingtoachievetheshortestpathalgorithmforimagerendering.Colorimagesbasedontheshortestpathisafastimagerenderingmethod,thelocalcolorofblackandwhiteimageafterimageappliedbypainting,usingcolortomakeexpandthewaythewholeimagecolorization.Finally，programanduseMatlabsoftwaretogainresults.Keywords:Imagerendering,Colorization,Grayscalecolor,Shortestpath第1章绪论1.1概述彩色化是一个给黑白图像、电影或电视节目加上颜色的处理过程。一般认为是由WilsonMarkle1970年发明，最初用于处理阿波罗登月计划获取的月球影像。黑白电影的彩色化在上世纪80年代曾经是一个热门话题。一些早期电影通过彩色化处理焕发了新的光彩。尽管人们对老电影彩色化的艺术价值存在争议，但彩色化视频和图像能够增强人们的视觉效果却是不争的事实。而且彩色化技术涉及到图像的分割、聚类、运动估计等很多图像与视频处理中的通用技术，所以当前彩色化技术研究仍然是图像处理学界一个活跃的、有挑战性的课题，而且被更多的应用于图像、视频编辑和图像通信，以及科学、工业和军事等多个领域。短程线距离即最短路径衡量的是连接两点亮度变化最平缓的曲线上的亮度变化总量。虽然像素亮度变化与颜色变化并非严格的一一对应，但二者之间联系紧密：亮度剧烈变化的地方一般对应颜色的巨变，亮度平缓变化或保持恒定的地方通常颜色变化程度也不明显。因此可以认为，像素间的短程线距离越小，期间的颜色就越接近。这是短程线距离能够反映亮度变化、进而可以用来进行颜色扩展的现实基础。也是同Levin颜色扩展方法的操作类似，首先在图像各部分涂上适当颜色的线条作为初始颜色。设有N个互不相连的涂色区域，用表示，每个涂色区域仅对应一种颜色，彩色化的任务就是将现有中的颜色扩展到图像中的其他区域。1.2课题发展现状和前景展望最短路径问题是图论中研究的一个重要课题,它广泛应用于交通、网络寻优等领域。此类问题不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。例如,城市交通中出行者选择出行路径,通信网中的最可靠路、最大容量路问题,统筹方法中关键路线问题等,都可以转化为最短路径问题。最短路径问题要解决的就是求加权图G=<V,E,W>中两给定顶点之间的最短路径，实际上就是根据网络的链路代价计算一对节点之间的最小代价路径。最短路径一般包括以下5种情况：1.从某一节点到其它所有节点之间的最短路径；2.在各对节点之间的最短路径；3.在两个规定节点之间的最短路径；4.在某些规定节点通过某些规定节点之间的最短路径；5.次短或较短路径。其中第一种情况应用最为广泛。与图像处理的其它领域相比，在图像着色方面公开可查的资料较少。从现有方法及本文的研究结果来看，还有许多问题需要解决或改进。图像着色的发展前景主要偏重于以下3方面：(1)提高图像彩色化方法的实用性。实用性包含两个方面，一是操作简便、处理高效，二是要有逼真的处理结果。当前在图像彩色化中还离不开人工参与，如在应用颜色扩展类方法时需要事先在图像上人工设置指示色，而颜色转移类方法则需要选择适配的参考图像。对处理效率和处理效果的要求同各类图像处理的是一致的，即力求以最小的处理代价获得最优的处理结果。(2)增强视频序列彩色化的稳健性。不同于单帧图像彩色化，多帧彩色化的关键是要充分利用相邻帧的处理结果。现有方法的突出问题表现为在后续帧的处理结果中常出现颜色偏差。设计稳健的后续帧彩色化及对颜色偏差的检测纠正方法是下一步工作的努力方向。可能的处理方式是综合利用相邻多帧进行运动估计及颜色传递。(3)拓宽对纹理图像、复杂场景的适用性。现有彩色化方法在应用上还有诸多局限性，如颜色扩展类彩色化方法不适于处理内容复杂的纹理图像，视频序列彩色化方法对于复杂场景的处理能力也有待加强。1.3论文内容本文的内容是利用短程线的方法实现灰度图像的着色。基于短程线距离的颜色混合法处理速度最快。采用高效的短程线距离算法，该方法最接近实际的影像彩色化要求。像素间短程线距离越小，其间的颜色就越相近。这是短程线距离能够反映亮度变化、进而可以用来进行颜色扩展的现实基础。第2章基于最短路径的图像着色基于最短路径的图像着色分为两部分，第一部分是图像着色部分，第二部分是最短路径的实现。并且编程在MATLAB实现最短路径的图像着色。基于最短路径的图像着色的流程框图如图2.1。黑白图像黑白图像添加颜色涂抹添加颜色涂抹涂抹图像涂抹图像RGBRGB空间转换为YUV空间颜色扩展（短程线或不平度）颜色扩展（短程线或不平度）图像整理图像整理图2.1基于最短路径的图像着色的流程框图下面分别介绍图像着色和最短路径。2.1图像着色的介绍2.1.1图像着色彩色图像的合成与分析分别是计算机图像学和计算机视觉研究的主要课题之一。对于静止图像，影响物体表面颜色的主要物理因素是环境光的光谱能量分布和物体表面反射率。图像合成是给定环境光信息(光谱能量分布)及前景与背景信息(物体的几何形状、位置、表面的反射率分布函数)条件下，计算所期望的场景图像的颜色。该过程称为“着色”。相对于黑白图像，颜色使彩色影像内容更丰富、细节更清晰，视觉效果逼真。彩色影像的优点引发人们对黑白影像进行颜色处理的兴趣，彩色化技术应运而生。按照应用目的及处理方式的不同，彩色化可分为伪彩色和假彩色两种类型。伪彩色彩色化最初处理的是间接视觉成像。这类黑白影像由成像机理决定了其记录的内容本身并没有颜色，甚至并非常规意义上的图像，是表示非可见电磁波穿透特性的数据显示。如医学上为检查人体病变采用的x光透视成像，人体各器官及正常器官与病变器官对x光的吸收率不同，经x光透视成像后体现在灰度差异上，从而间接反映体内器官的状况。虽然这类图像本身没有颜色，但为了使图像更便于观察，常根据图像灰度添加不同的颜色以突出细节。这种处理方式称为“伪彩色”(pseudocoloration)。伪彩色处理通过将每个狄度级匹配到彩色空间上的一点，将单色图像映射为一幅彩色图像。这可将按某种规则生成的映射存储在查找表中，从而简单地给每个狄度级赋予一种彩色。如果按某种模式进行伪彩色映射而不是随机地赋值，效果可能令人更满意，一般是将灰度轴匹配到色彩空间中的一条连续的曲线上。伪彩色处理可以是连续的彩色也可以由几种彩色单独构成。假彩色原本彩色的场景由于成像条件所限造成颜色被动丢失，即传统意义上的黑白照片、黑白电影等。对于这类影像的处理要求为其添加自然的、接近真实的颜色，以最大限度地模拟或再现场景的原貌。这类彩色处理方式称为“假彩色”（falsecolofization）。关于假彩色这个术语，学术界对其解释不尽相同。有的文献并不严格区分假彩色和伪彩色，而普拉特提出的假彩色概念是将一幅由三基色描绘的彩色图像或具有同一内容的一套多光谱图像，逐像素映射到由三激励值所确定的色彩空间上。将给黑白照片着色以模拟真实颜色这一类处理方式称作假彩色。假彩色和伪彩色是彩色化处理的两个分支，二者应用背景不同，在处理方法上也存在很大差异。伪彩色的处理对象本没有颜色，而是重在突出细节，要使灰度不同的像素对应不同的颜色，即以颜色差异体现灰度差异，处理过程可看作一种灰度——颜色映射，颜色选择允许一定的随意。假彩色力求体现场景的真实性，对表现细节没有特殊要求，但颜色搭配要自然合理，以最大限度地实现逼真的彩色化效果。2.1.2颜色与色彩空间牛顿认为:“准确地说，光线是没有颜色的，它所拥有的只是引起这样或那样颜色知觉的能量分布。”现代心理学研究表明，颜色是人类认知系统对物体表面光照以及视觉环境的综合反应；缺少了其中的任何一个，都不会有颜色知觉。光对人眼引起的视觉效果可以用色调(hue)、饱和度(saturation)及亮度(brightness)三个参量来表示，称为颜色的三要素。色调色调是颜色的一种最基本的感觉属性，这种属性可以使光谱上的不同部分区别开，即按红、橙、黄、绿、青、蓝、紫等色感觉来区分色谱段。根据有无色调属性，可以将外界引起的色感觉分为两大体系:彩色系(chromaticcolors)与非彩色系(achromaticcolors)，前者同时具有色调、饱和度和亮度三个量度，而非彩色系只有亮度一种度量，饱和度等于零。饱和度饱和度是对有色调属性的视觉在色彩鲜艳程度上做出评判的视觉属性。彩色系的颜色，其鲜艳程度与饱和度成正比，描述饱和度感觉的程度词是浓、淡、深、浅。非彩色系是饱和度为零的状态，比如将彩色显示器的色彩逐渐调淡，最后就变成黑白画面。亮度亮度是区分明暗层次的非彩色觉的视觉属性，这种明暗层次决定于光刺激能量水平的高低。亮度与色调属性无关，是只涉及明暗层次的感觉，正如用黑白全色胶卷拍照只记录明暗层次而不记录色调。根据亮度感觉的强弱，从最明亮到最暗可以分为三个水平:白—高亮度端的非彩色觉；黑—低亮度端的非彩色觉；灰—介于白与黑之间的中间层次亮度感觉。三要素中，色调与饱和度又总称为色度，它既说明颜色的类别，又能表示颜色的浓淡程度。色彩空间，是指定颜色信息的表达方式，是以多维强度值来表示颜色的描述体系。常见色彩空间包括图像处理中广泛采用的RGB空间，应用于视频传输系统的YIQ、YUV或YCbCr空间，彩色印刷业采用的CMYK空间。另外还有一类与颜色的基本要素，亦即人类视觉对颜色的感知密切相关的认知色彩空间，如HSI和HSV空间。RGB色彩空间图像处理中最基础、最常用的色彩空间是RGB空间。三基色原理认为自然界中的绝大多数的彩色光能分解为互相独立的红(red)、绿(green)、蓝(blue)三种基色光；反之用互相独立的红、绿、蓝三种基色以不同的比例混合，可模拟出自然界中绝大多数的颜色。RGB色彩空间即RGB颜色立方体，利用颜色的三基色来描述物体的颜色特征。在计算机图像处理软件和图形处理软件的色彩管理系统中，RGB色彩空间是数字照相机、扫描仪、显示器所使用的颜色系统，是一个与设备相关的颜色空间。也就是说，它们产生的颜色是与具体使用的设备有关，不同的设备可能使用不同的RGB三原色，混合出的效果也不会完全相同。CMYK色彩空间CMYK(eyan青，magenta品红，yellow黄，black黑)是用于印刷的色彩空间标准。和RGB模型不同的是，CMYK用的是减色法。印刷品本身通常不能发光，而是通过反射光线来表现自身的颜色，例如红色的纸，是吸收了照明白光中的青色光线，反射红光到人的眼睛，使人产生红色的色感。这种特性决定了印刷系统采用的CMY基色刚好是RGB系统三原色的补色，另外CMYK把黑色独立出来是为了提供更丰富的灰度级。YIQ类色彩空间YIQ是北美NTSC电视系统中采用的色彩系统，Y是指颜色的亮度，I和Q分别是色调和饱和度。为了有效传输并与黑白电视兼容，YIQ系统中的Y分量提供黑白电视机要求的所有影像信息。RGB到YIQ的变换关系为(2-1)利用人的视觉系统对亮度变化比对色调和饱和度变化更敏感这一特性，YIQ标准中表示Y时分配较大的带宽(指数字颜色所用比特数)，而在表示I、Q时可以采用较小的带宽。另外，它成为普遍应用的标准是因为在图像处理中YIQ模型的主要优点是去掉了亮度和颜色信息之间的紧密联系。亮度是与眼中获得的光的总量成比例的，去除这种联系的重要性在于处理图像的亮度成份时能在不影响色彩成份的情况下进行。与YIQ同属一类，YUV是欧洲PAL电视系统中采用的色彩空间，YUV的含义和YIQ一一对应，只是与RGB之间的转换关系不同。YCbCr是JPEG的缺省色彩系统，它是从YUV色彩系统中衍生出来的，将U和V做少许调整就是Cb和Cr。HIS类色彩空间HSI色彩空间是从人的视觉系统出发，用色调(hue)、饱和度(saturation)和亮度(intensity)来描述颜色。HSI色彩空间可以用一个圆锥空间模型来描述，此圆锥模型比较复杂，但确能把色调、亮度及饱和度的变化情形表现得很清楚。由于人的视觉对亮度的敏感程度远强于对颜色浓淡的敏感程度，采用HSI色彩空间比RGB空间更符合人的视觉特性，也更便于色彩处理和识别。在图像处理和计算机视觉中大量算法都可在HSI色彩空间中方便地使用，它们可以分开处理而且是相互独立的。因此，在HSI色彩空间可以简化图像分析和处理的工作量。HSV空间与HSI类似，区别是亮度分量的计算不同，从而使得亮度和饱和度的分布及动态范围有一定差异。色彩空间在本质上是颜色的描述方式，考虑其对颜色的描述角度，可以用一种更为宽泛的形式对色彩空间进行分类，即分为由颜色分量表示的基本色空间和利用颜色要素表达的色彩属性空间；前者如RGB、CMYK空间，YIQ、YUV、YCbCr及HSI、HSV等空间都归为后者。顾名思义，基本色空间重在说明颜色的构成，如RGB模型明示了颜色三基色分量，CMYK用以说明打印一种颜色需用的颜料配比。颜色属性空间则直接与人眼对颜色的视觉感受，即颜色三要素(亮度、色调、饱和度)密切相关，更加符合人的视觉信息获取过程。颜色属性空间的显著特征就是亮色分离。颜色描述中是否实现亮色分离，是区分宽泛分类色彩空间的主要标志。实现亮色分离就可以对颜色的亮度和色度进行单独处理，这为一些图像处理问题带来极大便利。2.2最短路径的介绍2.2.1最短路径最短路径这一重要问题早在20世纪初就已经得到人们的高度重视，当时也有许多科学家研究这一重要问题的求解方法。但直到1959年荷兰计算机科学家Dijkstra（迪杰斯特拉）才给出这一问题求解的基本思想，并给出了算法。后来这个算法就成了众所周知的Dijkstra算法，也成为了一代经典。当时的Dijkstra提出的这一算法主要解决的问题是从固定的一个点到其他各点的最短路径问题。但是在实际生活中往往要求解决的不只是固定一点到其他点的最短路径，而是要求计算出任意两点之间的最短距离。随着社会的不断进步，最短路径算法在人们的日常生活中显得越来越重要。所谓最短路径就是网络中两点之间距离最短的路径，这里讲的距离可以是实际的距离，也可以引申为其他的度量，比如时间、运费、流量等。因此，从广义上讲，最短路径算法就是从网络中找出两个点之间最小阻抗路径的算法。2.2.2最短路径的定义最短路径即短程线距离的概念：(p)表示连接图像中两点r,s的曲线，Y代表像素的亮度，r,s间的短程线距离义为(2-2)短程线距离对应于连接两点的所有曲线中、沿曲线方向像素亮度值的梯度积分的最小值，即短程线表示从图像中一点到另一点的灰度变化最平缓的路径。最短路径的离散化定义：在数字图像中短程线距离的计算需要采用离散形式，现给出一种更直观的离散定义。用Y表示像索的亮度，则图像中相邻两点r、s间的短程线距离为(2-3)定义图像中8连通的曲线上的曲线距离(2-4)则图像中两点间的短程线距离等于连接这两点的所有曲线中的最短距离(2-5)这种离散定义形式便于进行计算。短程线距离是定义在图像中的某种最短距离，在图论中也有类似的最短距离。给定一个双向图G，它的每条边都有一个非负的长度，路径的长度即为次路径经过的边的长度之和。图2.2.1(a)给出了一个具有五个顶点的有向图，各边上的数即为长度，假设源顶点s为1，从顶点1出发到各顶点的最短路径按长度顺序列在图2.2.1(b)中，每条路径前的数字为路径长度。对于图像而言，如果把每个像素对应图中的顶点，相邻像素间的亮度差看作图中顶点间的边长，那么所谓短程线距离就可等效于图论中的最短距离。884214215542423535143143(a)图023461111111332344502346(b)图最短路径图2.2.1最短路径举例2.2.3最短路径的基本思路为了解决最短路径问题，首先应根据要求选取一种量度标准。然后将n个输入排成这种量度标准要求的顺序，按照这种顺序一次输入一个量。如果这个输入和当前已经构成的在这种量度意义的部分最优解加在一起能产生一个可行解，则把此输入加到这部分最优解中，否则不加入。这种能够在某种量度意义下得到最优解的分级处理方法称为贪心算法。按照上面的思路，可以逐步地构造出这些最短路。使用迄今已经生成的所有路径长度之和作为一种量度，为了使这一量度达到最小，单独的每一条路径都必须具有最小长度。使用这一量度标准，假定已经构造了n条最短路径，则下面要构造的路径应该是下一条最短的最小长度路径。如何根据贪心算法，确定路径上的每个节点而最终求得最短路径，Dijkstra提出了一个按路径长度递增的次序产生到各顶点的最短路径的算法。1)假设用带权的邻接矩阵cost来表示一个带权图，表示弧<，>上的权值。若<，>不存在，则置为（在计算机上可以用允许的最大整数值来表示），S为已找到从点出发的最短路径的集合，它的初态为空集。从到其他结点的路径长度向量为。那么从出发到图上其余顶点可能达到的最短路径长度的初值为（2.2.5）2)选择使得dist[j]=min{dist[j]，{V-S}，就是当前求得的一条从出发的最短路径的终点。令S=S║{}。3)修改从出发到集合V-S上任一顶点可达的最短路径长度。如果则修改为4)重复操作2)，3)共n-1由此求得从到图上其余各个结点的最短路径。这是依据路径长度递增的序列而求得的。2.1.4最短路径的基本方法传统的利用Dijkstra算法来实现图中任意结点之间的最短路径查找，其基本思想就是依次以图中各个结点为起点利用Dijkstra算法计算出最短路径，这样循环n次即可得到图中任意结点之间的最短路，而每步都是一个简单的重复过程。这样虽然能够实现任意两点之间的最短路径查找，但是从效率上分析并不是最优的。实际是可以进行改进，具体方法如下：1)根据Dijkstra算法思想，可以由图中结点的出入度信息来提高各点之间最短路径的查找速度。2)在带权图中利用Dijkstra算法找出部分结点之间的最短路径后，若其他还没有找出最短路径的结点可以利用前面已找出的最短路径信息为自己提供快速的最短路径查找。利用结点入度信息查找根据结点的入度信息来优化查找最短路径的基本思想是：当某结点的入度为0时，图中其他结点到该结点的最短路径都为无穷（不可达）并且其他结点之间的最短路径也不会出现该结点，所以在求图中其他各结点之间的最短路径时，可以将该结点先删除以简化整个图的最短路径的查找。根据上述基本思路，给出优化查找的具体步骤：1)求出图中各结点的入度；2)找到入度为0的结点，记作；3)从点出发开始用Dijkstra算法求到其他各结点的最短路径；4)求完后，若结点入度为0则删除该结点，从而简化了连接图，也简化了查找步骤；5)重复2)，3)步，直到没有入度满足条件的结点。如图2.2.2所示，A的入度为0，当求出了以A点出发到图中其他各点的最短路径后，再求其他结点间的最短路径时，就可以将结点A删除，并把其他结点到A结点的最短路径记为无穷大即可。56879AABCD图2.2.2基于入度优化的实例图将图2.2.2中的结点A删除后的图像如图2.2.3所示，这样使得B，C，D结点之间最短路径的查找更为简便。79BBCD图2.2.3A入度为0，A执行完3),4)步后的图示利用结点出度信息查找基于结点出度信息查找图中各结点间的最短路径的基本思想是：当某结点的出度为0时，从该结点出发到图中任何一个结点都是不可达的。其次，当某个结点的出度为1时，该结点只有唯一的后继结点。并且该结点到其他结点的最短路径必须经过此后继结点。当该结点的这个唯一的后继结点到其他各结点的最短路径已经求出以后，该结点到其他各结点的最短路径也就可以求出了。只需在其唯一后继结点的最短路径求出后再加上其唯一出度边的权值即可。根据上面讨论的基本思想，下面是从出度着手查找的具体步骤：1)首先求出图中所有结点的出度；2)找到出度为0或为1的结点，记作；3)若出度为0，则不必去求从该结点出发的最短路径了，因为从该结点出发是不可能找出到其他结点的最短路径（不可达）；4)若出度为1则也不必去求从该结点出发的最短路径了，只需在其唯一后继结点的最短路径求出后再加上其唯一出度边的权值即可；5)重复2)、3)、4)步，直到没有出度满足条件的结点。不论是从入度还是从出度着手都应该考虑出入度为1的多个结点，并注意其前驱结点的顺序。利用已找出的最短路径快速查找这种优化方法的基本思想是：根据图2.2.4所示，假设从源点A出发到结点C的最短路径已经求出，为A，B，C，D；那么需要求从结点B出发到结点D或到结点C的最短路径时，不用再去按照Dijkstra算法去求，可按照已找出的A→C的最短路径直接得出B→C的最短路径为B，D，C；得出B→D的最短路径为B，D证明如下：当结点A到结点C的最短路径为A，B，C，D；假设结点B到结点D的最短路径不是B，D；而是B…D那么可得出A，B…D，C；这条路径一定比路径A，B，D，C更短，因此与已知A→C的最短路径A，B，D，C矛盾。所以，可知B→D的最短路径必为B，D；同理可以推出B→C的最短路径必为B，D，C。86932451CCDAB图2.2.4利用最短路径信息优化实例图根据上面分析，可以得出图中任意两结点之间的最短路径。参照图2.2.4所示，优化实现的具体步骤如下（按照A，B，C，D为出发点的顺序查找）：从A点出发寻找其他各结点的最短路径步骤：1)A→B的最短路径为A，B∥由Dijkstra得2)A→D的最短路径为A，B，D∥由Dijkstra得3)A→C的最短路径为A，B，D，C∥由Dijkstra得从B点出发寻找其他各结点的最短路径步骤：4)B→D的最短路径为B，D∥2)中已找到5)B→C的最短路径为B，D，C∥3)中已找到6)B→A的最短路径为B，D，C，A∥由Dijkstra得从C点出发寻找其他各结点的最短路径步骤：7)C→A的最短路径为C，A∥6)中已找到8)C→B的最短路径为C，A，B∥由Dijkstra得9)C→D的最短路径为C，A，B，D∥由Dijkstra得从D点出发寻找其他各结点的最短路径步骤：10)D→C的最短路径为D，C∥3)中已找到11)D→A的最短路径为D，C，A∥6)中已找到12)D→B的最短路径为D，C，A，B∥由Dijkstra得2.3利用短程线距离进行颜色混合定义点到区域的短程线距离(2-6)即点到一个区域的短程线距离等于该点与这个区域内所有点之间短程线距离的最小值。对于要彩色化的像素，如图2.3.1中s，根据Yatziv颜色混合的思想，其处理后的颜色为(2-7)其中权值由s到各涂色区域的短程线距离确定W(r)=(2-8)式中b是混合调节参数，一般取1b6。实际处理中对每个像素取3种混合色即可，仅取与之短程线距离最小的三个涂色区域的颜色。图2.3.1颜色混合示例第3章最短路径的图像着色在MATLAB中的实现3.1MATLAB的介绍MATLAB和Mathematica、Maple并称为三大数学软件。MATLAB可以进行矩形运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通信、图像处理、信号检测、金融建模设计与分析等领域。MATLAB是矩阵实验室(MatrixLaboratory)的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB语言已是当今国际上科学界最具影响力、也是最有活力的软件。它起源于矩阵预算，并已经发展成一种高度集成的计算机语言。MATLAB具有强大的数学运算能力、方便使用的绘图功能及语言的高度集成性。MATLAB除具备卓越的数值计算能力外，它还提供了专业水平的符号计算、文字处理、可视化建模仿真和实时控制等功能。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，因此用MATLAB来解决问题要比用C、FORTRAN等语言完成相同的事情简捷得多。MATLAB在数学计算以外的其他科学与工程领域的应用也是越来越广，并且有着更广阔的应用前景和无穷无尽的潜能。它可以将使用者从烦琐、无谓的底层编程中解放出来，把有限的宝贵时间更多地花在解决问题中，这样无疑会提高工作效率。目前，MATLAB已经成为国际上最流行的苦学与工程计算的软件工具，现在的MATLAB已经不仅仅是一个“矩阵实验室”了，它已经成为了一种具有广泛应用前景的计算机高级编程语言了，有人称它为“第四代”计算机语言，它在国内外高校和研究部门正扮演着重要的角色。MATLAB语言的功能也越来越强大，不断使用的要求提出新的解决方法。可以预见，在科学运算、自动控制、科学绘图、通信仿真等领域MATLAB语言将长期保持其独一无二的地位。3.2MATLAB的特点MATLAB之所以能如此迅速的普及，现实出强大的生命力，是由于它有着不同于其他语言的特点。被称作第四代计算机语言的MATLAB，利用其丰富的函数资源，使编程人员从烦琐的程序代码中解放出来。MATLAB最突出的特点就是间接。MATLAB用更直观的、更符合人们思维习惯的代码，代替了C/C++和FORTRAN语言的冗长代码。MATLAB给用户提供的是最直观、最简洁的开发环境。高效方便的矩阵预算MATLAB语言像BASIC、FORTRAN和C语言一样规定了矩阵的算术运算、关系运算符、逻辑运算符、条件运算符以及赋值运算符，而且这些运算符大部分可以照搬到矩阵的运算，有些如算术运算符只要增加“.”就可以用于矩阵间的运算，并且它不需要定义距阵间的维数，并给出矩阵函数、特殊矩阵专门的库函数，使之在数字信号处理、建模、系统识别、自动控制、优化等领域，显得十分简洁、高效，具有其他高级语言不可比拟的优势。直观灵活的语言MATLAB不仅仅是一套打包好的函数库，同事也是一种高级的、面向对象的编程语言，使用MATLAB可事半功倍的开发自己的程序。MATLAB自身的许多函数，实际上也包括所有的工具箱函数，都是用M文件实现的。先进的可视化工具MATLAB提供功能强大的、交互式的二维和三维绘图功能，可创建富有表现力的彩色图形。可视化工具包括：曲面渲染（SurfaceRendering）、线框图，伪彩图、光源，三维等高线图、图像显示、动画、体积可视化等。开放性、可扩展性强M文件是可见的MATLAB程序，所以可以查看源代码。开放的系统设计使我们能够检查算法的准确性，修改已存在的函数，或者加入自己的新部件。用户使用方便MATLAB语言灵活、方便，其调试程序手段丰富，调试速度快。不仅可以作为解释性语言使用，也可以以.m格式的文件作为编译型的语言使用。现将MATLAB中进行编写程序和调试程序的步骤说明如下：(1)编辑：程序从键盘上输入后要修改输入的错误。在输入过程中可以利用块操作、光标操作、文件输入等，加快正确输入程序的速度。(2)编译：陈旭输入后，要把这种高级语言翻译成二进制编码。翻译过程中要纠正程序中不符合该高级语言所规定的格式或语法错误，知道其确无上述错误为止。(3)连接：将翻译后的二进制的程序装入具体的计算机环境中，将其和操作系统及其他应用软件连接起来，以解决不同时刻、不同条件下新装入程序和其他软件的不同连接关系。(4)执行和调试：连接后要执行，执行的目的是检验用户编写程序是否存在语意上的错误。如果执行结果正确，说明程序已经调试完毕；如果不符合用原来的语意，就需要进行调试，从而修改原来的程序。功能强大的工具箱MATLAB工具箱包括两个部分：核心工具箱（核心部分中有数百个核心内部函数）和各种可选的工具箱。其核心工具箱又可分为两大类：功能性工具箱主要用来扩充其符号计算功能、图示建模仿真功能、文字处理功能以及与硬件实时交互功能。功能性工具箱可用于多种学科，而学科性工具箱专业性比较强，如ControlSystem、SignalProcessing、NonlinearControl、Optimization等。这些工具箱都是由该领域内的高水平专家编写的，用户可以使用它们直接进行较高的烟具工作。3.3基于最短路径的图像着色在MATLAB中的实现图像是各种观测系统观测客观世界获得的且可以直接或间接作用于人眼而产生视觉的实体。在信息传递和交换中，图像是重要的传播媒体。颜色和灰度是决定一幅图像表现力的关键因素，在人类视觉系统中，颜色是重要的因素。由于人眼对灰度的敏感度远不如颜色，对于一些灰度图像如：红外照片、科学图片、磁共振成像等，我们希望把灰度图像变成彩色图像以增强视觉效果。这就要用到图像的彩色化处理。图像彩色化是进行影像彩色化处理的基础。早期对黑白照片和黑白电影进行着色一般采用“人工绘制”的方式，现阶段流行的处理方式是以计算机处理为主、人工参与为辅，具体的处理方法又分为借助颜色转移和局部颜色扩展两类。基于不平度的颜色混合图像彩色化方法Yatzif提出的颜色扩展方法简易可行、速度很快且效果颇佳，该方法提出先收工部分着色，再利用类似侧地距离的概念为两个距离定义了短程线距离，并以此为颜色传递的依据。这种处理方式对图像彩色化的实际操作颇有启发意义。不平度的概念：像素s和它的8领域中的像素t之间的不平度(s,t)定义为：(s,t)=abs(Y(s)-Y(t))(3-1)Y为像素灰度值。对于连通关系定义的曲线C={,,…,}，它的不平度定义为：(C)=max{(,),…,(,),…,(,)}i=1…m-1(3-2)对于任意两个像素s和t，它们的不平度定义为：=min(QUOTE(C(s,t)))(3-3)其中C(s,t)是所有以s为起点t为终点的曲线。根据上面的这些公式，像素s到已经着色区域的不平度公式(3-4)。QUOTE(s,)=min(QUOTE(C(s,t)))(3-4)基于不平度的颜色混合图像彩色化原理本方法依据Yatzif同样的假设：当没有剧烈灰度变化时相邻像素的颜色也不会又剧烈变化。初始情况下，通过手工的方式给部分区域着色，目标就是利用这些初始条件给未着色的像素赋予合理的颜色，根据假设可知，未着色的像素的颜色应该和到该像素灰度变化最平缓的已着色像素的颜色一致。假设A和B是已经着色的像素，C是待着色的像素。设A到C的路径集合为X，B到C的路径集合为Y。通过一定的定义，把路径的灰度变化程度进行量化描述。从集合X中挑选出一条路径，使其满足该路径灰度变化最小，同理从集合Y中也挑选出一条这样的路径。通过比较得出到达C像素灰度变化最小的路径，像素C的颜色就取灰度变化最小的路径另一端的像素颜色。当所有未着色像素都进行了这样的彩色化过程后，整副图像的彩色化就完成了。上述方法的关键就是如何定量描述一条路径的灰度变化程度，“不平度”正是为此而定义的。对于两个像素之间的任意一条路径，求出每两个相邻像素之间的灰度差，然后找到其中最大的那一个，来表示该路径的灰度变化程度，称之为该路径的不平度。连接两个像素所有路径的不平度的最小值定义为这两个像素之间的不平度，它表示的是两个像素之间的灰度变化的程度，这正是假设中进行颜色传递的约束机制。灰度变化越大说明这两个像素之间颜色的一致性越小，反之则说明两个像素之间的颜色一致性越大，而且不平度的大小与路径的长短无关，由此可见不平度很适合作为颜色扩展的约束机制。为了使边界附近的结果更加平滑，我们也采用了颜色混合的方法。所谓颜色混合就是对于未着色像素，把到达该像素的不平度最小的3个着色区域颜色辅以一个关于不平度的函数进行加权求和，从而得到最终的颜色。对于加权函数的选取需要符合如下条件：(3-5)(3-6)其中d表示不平度。根据这两个条件，我们选择了函数。基于不平度的颜色混合彩色化算法的实现在图像彩色化中要计算每个未涂色像素与涂色区域的不平度，该过程可以利用迭代动态规划算法(interactivedynamicprogrammingalgorithm)来实现。迭代动态规划算法就是利用迭代方式来求解动态规划递归方程。动态规划(principleofoptimality)是采用最优原则来建立用于计算最优解的递归式。所谓最优原则，即不管前面的策略如何，此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。在得到最优解的递归式之后，需要执行回(traceback）以构造最优解。如果不能有效地避免重复计算，递归程序的复杂性将非常可观。如果可以在递归程序设计中解决重复计算问题，那么计算的复杂性将急剧下降。动态规划递归方程如果用迭代方式来求解，能够很自然地避免重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不要附加的递归栈空间，因此比避免重复计算的递归程序更快。迭代动态规划算法首先设定一个活性像素集合APS(ActivePixelSet)表示要向外进行颜色扩展的像素集合，其初始元素即涂色区域QUOTE(n=1,2,…,N)的边界。APS中的像素t向其8邻域的像素扩展，把它的不平度与他们之间的灰度差比较之后传递给相邻像素，若与其相邻的像素所对应的最小的3个不平度发生了变化，就把添加到APS中；当根据t处理完相邻像素的不平度之后，将t从APS中删除，循环往复直至APS为空。算法的流程图如图3.3.1原始图像部分着色图像原始图像部分着色图像初始化初始化APS空？APS空？传递不平度（短程线）传递不平度（短程线）将被传递像素加入APS被传递像素的不平度（短程线）改变？将被传递像素加入APS被传递像素的不平度（短程线）改变？将原像素从ASP中去除将原像素从ASP中去除颜色混合颜色混合输出彩色图像输出彩色图像图3.3.1算法流程图基于不平度的颜色彩色化快速方法的实现本方法在算法实现方面还是采用了迭代动态规划算法。设定一个活性像素集合APS(ActivePixelSet)表示要向外进行颜色扩展的像素集合，其初始元素即涂色区域QUOTE(n=l,2,…,N)的边界。APS中的像素t向其8邻域的像素扩展，把它的不平度与它们间的灰度差比较之后把其中小的值传递给相邻像素，作为该像素的不平度。若与其相邻的像素所对应不平度发生了变化，就把添加到APS中；当根据t处理完相邻像素的不平度之后，将t从APS中删除。此循环往复，直至APS为空。之后在对颜色信息进行区域适应性的平滑，消除图像边缘处的着色误差之后就能得到最后的彩色结果。图3.3.2为彩色化程序流程图。部分着色图像原始图像部分着色图像原始图像初始化初始化是APS是APS空？否否传递不平度（短程线）传递不平度（短程线）被传递像素的不平度（短程线）改变？被传递像素的不平度（短程线）改变？将被传递像素加入APS将被传递像素加入APS是是否否将元像素从APS中去除将元像素从APS中去除边缘处理边缘处理输出彩色图像输出彩色图像图3.3.2彩色化程序流程图3.4基于最短路径的图像着色的结果图像着色的目的使处理后图像的某些内容更加醒目,利用最短路径的方法给黑白图像着色是为了可以更快的得到着色后的图像。下图是两幅黑白图像在利用本文所介绍的基于最短路径的图像着色方法在MATLAB中实现的着色图像。图3.4.1和图3.4.4分别是两幅黑白图像，图3.4.2和图3.4.5分别是对两幅黑白图像进行局部颜色涂抹，图3.4.3和图3.4.6分贝是对两幅黑白图像经过着色后的彩色图像。图3.4.1黑白图像Lilies图3.4.2对Lilies进行局部颜色涂抹图3.4.3对Lilies着色后的彩图图3.4.1是一幅Lilies的黑白图像，为了使图像可以醒目的呈现在大家眼前，对Lilies进行着色，首先这幅图需要着色的部分有花朵和叶片，然后对它们进行局部颜色涂抹得到图3.4.2，然后根据灰度值的不同，每种颜色向其相同或相近的灰度值扩展，最终得到彩色图像3.4.3。图3.4.4黑白图像Arch图3.4.5对Arch进行局部颜色涂抹图3.4.6对Arch着色后的彩图Arch与Lilies采用的一样的方式最后得到彩色图像3.4.6。经过着色后的图像不仅看起来漂亮而且醒目。而且可以得到从黑白图像中得不到的信息。结束语转眼间这次的毕业设计已经接近尾声，作为一个本科生的毕业设计，由于经验的匮乏，难免有许多考虑不周全的地方，如果没有导师的督促指导，想要完成这个设计是很有难度的。在这半年的时间里我感受很深。从这次的毕业设计中我学到了很多东西。最短路径在现实生活中越来越重要，所谓最短路径就是网络中两点之间距离最短的路径，这里讲的距离可以是实际的距离，也可以引申为其它的度量，如时间、运费、流量等。因此，最短路径就是为了能快速、高效的实现各种需要的