基于最短路径的图像着色毕业论文.docx

毕 业 论 文题 目： 基于最短路径的图像着色 毕业论文（设计）原创性声明本人所呈交的毕业论文（设计）是我在导师的指导下进行的研究工作及取得的研究成果。据我所知，除文中已经注明引用的内容外，本论文（设计）不包含其他个人已经发表或撰写过的研究成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名： 日期： 毕业论文（设计）授权使用说明本论文（设计）作者完全了解*学院有关保留、使用毕业论文（设计）的规定，学校有权保留论文（设计）并向相关部门送交论文（设计）的电子版和纸质版。有权将论文（设计）用于非赢利目的的少量复制并允许论文（设计）进入学校图书馆被查阅。学校可以公布论文（设计）的全部或部分内容。保密的论文（设计）在解密后适用本规定。 作者签名： 指导教师签名： 日期： 日期： 注 意 事 项1.设计（论文）的内容包括：1）封面（按教务处制定的标准封面格式制作）2）原创性声明3）中文摘要（300字左右）、关键词4）外文摘要、关键词 5）目次页（附件不统一编入）6）论文主体部分：引言（或绪论）、正文、结论7）参考文献8）致谢9）附录（对论文支持必要时）2.论文字数要求：理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。3.附件包括：任务书、开题报告、外文译文、译文原文（复印件）。4.文字、图表要求：1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程字书写，不准用徒手画3）毕业论文须用A4单面打印，论文50页以上的双面打印4）图表应绘制于无格子的页面上5）软件工程类课题应有程序清单，并提供电子文档5.装订顺序1）设计（论文）2）附件：按照任务书、开题报告、外文译文、译文原文（复印件）次序装订3）其它毕业设计（论文）任务书 题目： 基于最短路径的图像着色 姓名 许凤英 学院 电气与信息学院 专业 电子信息 班级 0701 学号 200701030119 指导老师 张可为 职称 讲师 教研室主任 刘望军 陈爱萍 一、 基本任务及要求：着色是一种给黑白图像、电影或电视节目加上颜色的计算机辅助处理技术，在影视、医疗、太空探索及其它许多工业及科学领域有着广泛的应用，同时也一直是图像处理中一个活跃的、有挑战性的研究课题。最短路径表示从图像中一点到另一点的灰度变化最平缓的路径，将它作为混色权重可以把着色问题转化为混色问题求解。设计要求： 1熟悉彩色化以及最短路径理论。2用matlab语言编程实现基于基于最短路径离的黑白图像着色算法。3完成毕业论文。二、 进度安排及完成时间：1、第12周：课题调研、文献检索。2、第36周：毕业设计开题报告、文献综述3、第7周：总体设计，完成方案的选择4、第89周：确定数据模型，算法实现5、第1011周：基本算法验证、编程实现6、第1213周：论文撰写。论文初审，定稿。7、第14周：答辩。 目 录摘要3Abstract3第1章 绪论31.1 概述31.2 课题发展现状和前景展望31.3 论文内容3第2章 基于最短路径的图像着色32.1图像着色的介绍32.1.1图像着色32.1.2颜色与色彩空间32.2最短路径的介绍32.2.1最短路径32.2.2最短路径的定义32.2.3最短路径的基本思路32.1.4最短路径的基本方法32.3利用短程线距离进行颜色混合3第3章 最短路径的图像着色在MATLAB中的实现33.1 MATLAB的介绍33.2 MATLAB的特点33.3 基于最短路径的图像着色在MATLAB中的实现33.4 基于最短路径的图像着色的结果3结束语3参考文献3致谢3基于最短路径的图像着色基于最短路径的图像着色摘要：彩色化是一种给黑白图像、电影或电视节目加上颜色的计算机辅助处理技术，在影视、医疗、太空探索及其它许多工业及科学领域有着广泛的应用，同时也一直是图像处理中一个活跃的、有挑战性的研究课题。本论文的研究课题是基于最短路径的图像着色，本文分别介绍了图像着色和最短路径的方法，然后两相结合提出了利用短程线距离进行颜色混合的算法来实现最短路径的图像着色。基于最短路径的图像着色是一种快速的图像着色方法，在对黑白图像进行局部颜色涂抹得到涂抹图像后，运用颜色扩展的方式使整幅图像彩色化。最后编程运用Matlab软件实现。关键词：图像着色，彩色化，灰度图像着色，最短路径Color images based on the shortest pathAbstract: Colorization is a color processing technology with computer-aided to make color to black and white image, film and TV show. Film and television, health care, space exploration and many other industrial and scientific fields has been widely used, but also has been an active and challenging research topic in image processing. Research of this thesis is a way of color images which based on the shortest path, the thesis introduced the image coloring and shortest path, and then combining the two proposed geodesic distance using color mixing to achieve the shortest path algorithm for image rendering. Color images based on the shortest path is a fast image rendering method, the local color of black and white image after image applied by painting, using color to make expand the way the whole image colorization. Finally，program and use Matlab software to gain results.Keywords: Image rendering, Colorization, Grayscale color, Shortest path第1章 绪论1.1 概述彩色化是一个给黑白图像、电影或电视节目加上颜色的处理过程。一般认为是有Wilson Markle 1970年发明，最初用于处理阿波罗登月计划获取的月球影像。黑白电影的彩色化在上世纪80年代曾经是一个热门话题。一些早期电影通过彩色化处理焕发了新的光彩。尽管人们对老电影彩色化的艺术价值存在争议，但彩色化视频和图像能够增强人们的视觉效果却是不争的事实。而且彩色化技术涉及到图像的分割、聚类、运动估计等很多图像与视频处理中的通用技术，所以当前彩色化技术研究仍然是图像处理学界一个活跃的、有挑战性的课题，而且被更多的应用于图像、视频编辑和图像通信，以及科学、工业和军事等多个领域。短程线距离即最短路径衡量的是连接两点亮度变化最平缓的曲线上的亮度变化总量。虽然像素亮度变化与颜色变化并非严格的一一对应，但二者之间联系紧密：亮度剧烈变化的地方一般对应颜色的巨变，亮度平缓变化货保持恒定通常颜色变化程度也不明显。因此可以认为，像素间的短程线距离越小，期间的颜色就越接近。这是短程线距离能够放映亮度变化、进而可以用来进行颜色扩展的现实基础。也是同Levin颜色扩展方法的操作类似，首先在图像各部分涂上适当颜色的线条作为初始颜色。设有N个互不相连的涂色区域，用表示，每个涂色区域仅对应一种颜色，彩色化地任务就是将现有中的颜色扩展到图像中的其他区域。1.2 课题发展现状和前景展望最短路径问题是图论中研究的一个重要课题,它广泛应用于交通、网络寻优等领域。此类问题不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。例如,城市交通中出行者选择出行路径,通信网中的最可靠路、最大容量路问题,统筹方法中关键路线问题等,都可以转化为最短路径问题。最短路径问题要解决的就是求加权图G=中两给定顶点之间的最短路径，实际上就是根据网络的链路代价计算一对节点之间的最小代价路径。最短路径一般包括以下5种情况：1.从某一节点到其它所有节点之间的最短路径；2.在各对节点之间的最短路径；3.在两个规定节点之间的最短路径；4.在某些规定节点通过某些规定节点之间的最短路径；5.次短或较短路径。其中第一种情况应用最为广泛。与图像处理的其它领域相比，在图像着色方面公开可查的资料较少。从现有方法及本文的研究结果来看，还有许多问题需要解决或改进。图像着色的发展前景主要偏重于以下3方面：(1)提高图像彩色化方法的实用性。实用性包含两个方面，一是操作简便、处理高效，二是要有逼真的处理结果。当前在图像彩色化中还离不开人工参与，如在应用颜色扩展类方法时需要事先在图像上人工设置指示色，而颜色转移类方法则需要选择适配的参考图像。对处理效率和处理效果的要求同各类图像处理的是一致的，即力求以最小的处理代价获得最优的处理结果。(2)增强视频序列彩色化的稳健性。不同于单帧图像彩色化，多帧彩色化的关键是要充分利用相邻帧的处理结果。现有方法的突出问题表现为在后续帧的处理结果中常出现颜色偏差。设计稳健的后续帧彩色化及对颜色偏差的检测纠正方法是下一步工作的努力方向。可能的处理方式是综合利用相邻多帧进行运动估计及颜色传递。(3)拓宽对纹理图像、复杂场景的适用性。现有彩色化方法在应用上还有诸多局限性，如颜色扩展类彩色化方法不适于处理内容复杂的纹理图像，视频序列彩色化方法对于复杂场景的处理能力也有待加强。1.3 论文内容本文的内容是利用短程线的方法实现灰度图像的着色。基于短程线距离的颜色混合法处理速度最快，采用高效的短程线距离算法，该方法最接近实际的影像彩色化要求。像素间短程线距离越小，其间的颜色就越相近。这是短程线距离能够反映亮度变化、进而可以用来进行颜色扩展的现实基础。第2章 基于最短路径的图像着色基于最短路径的图像着色分为两部分，第一部分是最短路径的实现，第二部分是图像着色部分。并且编程在MATLAB实现最短路径的图像着色。基于最短路径的图像着色的流程框图如图2.1。黑白图像添加颜色涂抹涂抹图像颜色扩展（短程线或不平度）图像整理图2.1 基于最短路径的图像着色的流程框图下面分别介绍图像着色和最短路径。2.1图像着色的介绍2.1.1图像着色彩色图像的合成与分析分别是计算机图像学和计算机视觉研究的主要课题之一。对于静止图像，影响物体表面颜色的主要物理因素是环境光的光谱能量分布和物体表面反射率。图像台成是给定环境光信息(光谱能量分布)及前景与背景信息(物体的几何形状、位置、表面的反射率分布函数)条件下，计算所期望的场景图像的颜色。该过程称为“着色”。相对于黑白图像，颜色使彩色影像内容更丰富、细节更清晰，视觉效果逼真。彩色影像的优点引发人们对黑白影像进行颜色处理的兴趣，彩色化技术应运而生。按照应用目的及处理方式的不同，彩色化可分为伪彩色和假彩色两种类型。1) 伪彩色彩色化最初处理的是间接视觉成像。这类黑白影像由成像机理决定了其记录的内容本身并没有颜色，甚至并非常规意义上的图像，是表示非可见电磁波穿透特性的数据显示。如医学上为检查人体病变采用的x光透视成像，人体各器官及正常器官与病变器官对x光的吸收率不同，经x光透视成像后体现在灰度差异上，从而间接反映体内器官的状况。虽然这类图像本身没有颜色，但为了使图像更便于观察，常根据图像灰度添加不同的颜色以突出细节。这种处理方式称为“伪彩色”(pseudo coloration)。伪彩色处理通过将每个狄度级匹配到彩色空间上的一点，将单色图像映射为一幅彩色图像。这可将按某种规则生成的映射存储在查找表中，从而简单地给每个狄度级赋予一种彩色。如果按某种模式进行伪彩色映射而不是随机地赋值，效果可能令人更满意，一般是将灰度轴匹配到色彩空间中的一条连续的曲线上。伪彩色处理可以是连续也可以由几种彩色单独构成。2) 假彩色原本彩色的场景由于成像条件所限造成颜色被动丢失，即传统意义上的黑白照片、黑白电影等。对于这类影像的处理要求为其添加自然的、接近真实的颜色，以最大限度地模拟货再现场景的原貌。这类彩色处理方式称为“假彩色”（false colofization）.关于假彩色这个术语，学术界对其解释不尽相同。有的文献并不严格区分假彩色和伪彩色，而普拉特提出的假彩色概念是将一幅由三基色描绘的彩色图像或具有同一内容的一套多光谱图像，逐像素映射到由三激励值所确定的色彩空间上。将给黑白照片着色以模拟真实颜色这一类处理方式称作假彩色。假彩色和伪彩色是彩色化处理的两个分支，二者应用背景不同，在处理方法上也存在很大差异。伪彩色的处理对象本没有颜色，而是重在突出细节，要使灰度不同的像素对应不同的颜色，即以颜色差异体现灰度差异，处理过程可看作一种灰度颜色映射，颜色选择允许一定的随意。假彩色力求体现场景的真实性，对表现细节没有特殊要求，但颜色搭配要自然合理，以最大限度地实现逼真的彩色化效果。2.1.2颜色与色彩空间牛顿认为:“准确地说，光线是没有颜色的，它所拥有的只是引起这样或那样颜色知觉的能量分布。”现代心理学研究表明，颜色是人类认知系统对物体表面光照以及视觉环境的综合反应；缺少了其中的任何一个，都不会有颜色知觉。光对人眼引起的视觉效果可以用色调(hue)、饱和度(saturation)及亮度(brightness)三个参量来表示，称为颜色的三要素。1) 色调色调是颜色的一种最基本的感觉属性，这种属性可以使光谱上的不同部分区别开，即按红、橙、黄、绿、青、蓝、紫等色感觉来区分色谱段。根据有无色调属性，可以将外界引起的色感觉分为两大体系:彩色系(chromatic colors)与非彩色系(achromatic colors)，前者同时具有色调、饱和度和亮度三个量度，而非彩色系只有亮度一种度量，饱和度等于零。2) 饱和度饱和度是对有色调属性的视觉在色彩鲜艳程度上做出评判的视觉属性。彩色系的颜色，其鲜艳程度与饱和度成正比，描述饱和度感觉的程度词是浓、淡、深、浅。非彩色系是饱和度为零的状态，比如将彩色显示器的色彩逐渐调淡，最后就变成黑白画面。3) 亮度亮度是区分明暗层次的非彩色觉的视觉属性，这种明暗层次决定于光刺激能量水平的高低。亮度与色调属性无关，是只涉及明暗层次的感觉，正如用黑白全色胶卷拍照只记录明暗层次而不记录色调。根据亮度感觉的强弱，从最明亮到最暗可以分为三个水平:白高亮度端的非彩色觉；黑低亮度端的非彩色觉；灰介于白与黑之间的中间层次亮度感觉。三要素中，色调与饱和度又总称为色度，它既说明颜色的类别，又能表示颜色的浓淡程度。色彩空间，是指定颜色信息的表达方式，是以多维强度值来表示颜色的描述体系。常见色彩空间包括图像处理中广泛采用的RGB空间，应用于视频传输系统的YIQ、YUV或YCbCr空间，彩色印刷业采用的CMYK空间。另外还有一类与颜色的基本要素，亦即人类视觉对颜色的感知密切相关的认知色彩空间，如HSI和HSV空间。1) RGB色彩空间图像处理中最基础、最常用的色彩空间是RGB空间。三基色原理认为自然界中的绝大多数的彩色光能分解为互相独立的红(red)、绿(green)、蓝(blue)三种基色光；反之用互相独立的红、绿、蓝三种基色以不同的比例混合，可模拟出自然界中绝大多数的颜色。RGB色彩空间即RGB颜色立方体，利用颜色的三基色来描述物体的颜色特征。在计算机图像处理软件和图形处理软件的色彩管理系统中，RGB色彩空间是数字照相机、扫描仪、显示器所使用的颜色系统，是一个与设备相关的颜色空间。也就是说，它们产生的颜色是与具体使用的设备有关的，不同的设备可能使用不同的RGB三原色，混合出的效果也不会完全相同。2) CMYK色彩空间CMYK(eyan青，magenta品红，yellow黄，black黑)是用于印刷的色彩空间标准。和RGB模型不同的是，CMYK用的是减色法。印刷品本身通常不能发光，而是通过反射光线来表现自身的颜色，例如红色的纸，是吸收了照明白光中的青色光线，反射红光到人的眼睛，使人产生红色的色感。这种特性决定了印刷系统采用的CMY基色刚好是RGB系统三原色的补色，另外CMYK把黑色独立出来是为了提供更丰富的灰度级。3) YIQ类色彩空间YIQ是北美NTSC电视系统中采用的色彩系统，Y是指颜色的亮度，I和Q分别是色调和饱和度。为了有效传输并与黑白电视兼容，YIQ系统中的Y分量提供黑白电视机要求的所有影像信息。RGB到YIQ的变换关系为 （2.1.1）利用人的视觉系统对亮度变化比对色调和饱和度变化更敏感这一特性，YIQ标准中表示Y时分配较大的带宽(指数字颜色所用比特数)，而在表示I、Q时可以采用较小的带宽。另外，它成为普遍应用的标准是因为在图像处理中YIQ模型的主要优点是去掉了亮度和颜色信息之间的紧密联系。亮度是与眼中获得的光的总量成比例的，去除这种联系的重要性在于处理图像的亮度成份时能在不影响色彩成份的情况下进行。与YIQ同属一类，YUV是欧洲PAL电视系统中采用的色彩空间，YUV的含义和YIQ一一对应，只是与RGB之间的转换关系不同。YCbCr是JPEG的缺省色彩系统，它是从YUV色彩系统中衍生出来的，将U和V做少许调整就是Cb和Cr。4) 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.1)短程线距离对应于连接两点的所有曲线中、沿曲线方向像素亮度值的梯度积分的最小值，即短程线表示从图像中一点到另一点的灰度变化最平缓的路径。最短路径的离散化定义：在数字图像中短程线距离的计算需要采用离散形式，现给出一种更直观的离散定义。用Y表示像索的亮度，则图像中相邻两点r、s间的短程线距离为 (2.2.2)定义图像中8连通的曲线上的曲线距离 (2.2.3)则图像中两点间的短程线距离等于连接这两点的所有曲线中的最短距离 (2.2.4)这种离散定义形式便于进行计算。短程线距离是定义在图像中的某种最短距离，在图论中也有类似的最短距离。给定一个双向图G，它的每条边都有一个非负的长度，路径的长度即为次路径经过的边的长度之和。图2.2.1(a)给出了一个具有五个顶点的有向图，各边上的数即为长度，假设源顶点s为1，从顶点1出发到各顶点的最短路径按长度顺序列在图2.2.1(b)中，每条路径前的数字为路径长度。对于图像而言，如果把每个像素对应图中的顶点，相邻像素间的亮度差看作图中顶点间的边长，那么所谓短程线距离就可等效于图论中的最短距离。842154235143(a)图0234611111332344502346(b)图最短路径图2.2.1最短路径举例2.2.3最短路径的基本思路为了解决最短路径问题，首先应根据要求选取一种量度标准。然后将n个输入排成这种量度标准要求的顺序，按照这种顺序一次输入一个量。如果这个输入和当前已经构成的在这种量度意义的部分最优解加在一起能产生一个可行解，则把此输入加到这部分最优解中，否则不加入。这种能够在某种量度意义下得到最优解的分级处理方法称为贪心算法。按照上面的思路，可以逐步地构造出这些最短路。使用迄今已经生成的所有路径长度之和作为一种量度，为了使这一量度达到最小，单独的每一条路径都必须具有最小长度。使用这一量度标准，假定已经构造了n条最短路径，则下面要构造的路径应该是下一条最短的最小长度路径。如何根据贪心算法，确定路径上的每个节点而最终求得最短路径，Dijkstra提出了一个按路径长度递增的次序产生到各顶点的最短路径的算法。1)假设用带权的邻接矩阵cost来表示一个带权图，表示弧上的权值。若不存在，则置为（在计算机上可以用允许的最大整数值来表示），S为已找到从点出发的最短路径的集合，它的初态为空集。从到其他结点的路径长度向量为。那么从出发到图上其余顶点可能达到的最短路径长度的初值为 （2.2.5）2)选择使得distj=mindistj，V-S，就是当前求得的一条从出发的最短路径的终点。令S=S。3)修改从出发到集合V-S上任一顶点可达的最短路径长度。如果则修改为4)重复操作2)，3)共n-1由此求得从到图上其余各个结点的最短路径。这是依据路径长度递增的序列而求得的。2.1.4最短路径的基本方法传统的利用Dijkstra算法来实现图中任意结点之间的最短路径查找，其基本思想就是依次以图中各个结点为起点利用Dijkstra算法计算出最短路径，这样循环n次即可得到图中任意结点之间的最短路，而每步都是一个简单的重复过程。这样虽然能够实现任意两点之间的最短路径查找，但是从效率上分析并不是最优的。实际是可以进行改进，具体方法如下： 1）根据Dijkstra算法思想，可以由图中结点的出入度信息来提高各点之间最短路径的查找速度。 2）在带权图中利用Dijkstra算法找出部分结点之间的最短路径后，若其他还没有找出最短路径的结点可以利用前面已找出的最短路径信息为自己提供快速的最短路径查找。1. 利用结点入度信息查找根据结点的入度信息来优化查找最短路径的基本思想是：当某结点的入度为0时，图中其他结点到该结点的最短路径都为无穷（不可达）并且其他结点之间的最短路径也不会出现该结点，所以在求图中其他各结点之间的最短路径时，可以将该结点先删除以简化整个图的最短路径的查找。根据上述基本思路，给出优化查找的具体步骤：1)求出图中各结点的入度；2)找到入度为0的结点，记作；3)从点出发开始用Dijkstra算法求到其他各结点的最短路径；4)求完后，若结点入度为0则删除该结点，从而简化了连接图，也简化了查找步骤；5)重复2)，3)步，直到没有入度满足条件的结点。如图2.2.2所示，A的入度为0，当求出了以A点出发到图中其他各点的最短路径后，再求其他结点间的最短路径时，就可以将结点A删除，并把其他结点到A结点的最短路径记为无穷大即可。56 8 79ABCD图2.2.2基于入度优化的实例图将图2.2.2中的结点A删除后的图像如图2.2.3所示，这样使得B，C，D结点之间最短路径的查找更为简便。 79BCD如2.2.3 A入度为0，A执行完3）,4）步后的图示2. 利用结点出度信息查找基于结点出度信息查找图中各结点间的最短路径的基本思想是：当某结点的出度为0时，从该结点出发到图中任何一个结点都是不可达的。其次，当某个结点的出度为1时，该结点只有唯一的后继结点。并且该结点到其他结点的最短路径必须经过此后继结点。当该结点的这个唯一的后继结点到其他各结点的最短路径已经求出以后，该结点到其他各结点的最短路径也就可以求出了。只需在其唯一后继结点的最短路径求出后再加上其唯一出度边的权值即可。根据上面讨论的基本思想，下面是从出度着手查找的具体步骤：1)首先求出图中所有结点的出度；2)找到出度为0或为1的结点，记作；3)若出度为0，则不必去求从该结点出发的最短路径了，因为从该结点出发是不可能找出到其他结点的最短路径（不可达）；4)若出度为1则也不必去求从该结点出发的最短路径了，只需在其唯一后继结点的最短路径求出后再加上其唯一出度边的权值即可；5)重复2)、3)、4)步，直到没有出度满足条件的结点。不论是从入度还是从出度着手都应该考虑出入度为1的多个结点，并注意其前驱结点的顺序。3. 利用已找出的最短路径快速查找这种优化方法的基本思想是：根据图2.2.4所示，假设从源点A出发到结点C的最短路径已经求出，为A，B，C，D；那么需要求从结点B出发到结点D或到结点C的最短路径时，不用再去按照Dijkstra算法去求，可按照已找出的AC的最短路径直接得出BC的最短路径为B，D，C；得出BD的最短路径为B，D证明如下：当结点A到结点C的最短路径为A，B，C，D；假设结点B到结点D的最短路径不是B，D；而是BD那么可得出A，BD，C；这条路径一定比路径A，B，D，C更短，因此与已知AC的最短路径A，B，D，C矛盾。所以，可知BD的最短路径必为B，D；同理可以推出BC的最短路径必为B，D，C。86 93 24 51CDAB图2.2.4利用最短路径信息优化实例图根据上面分析，可以得出图中任意两结点之间的最短路径。参照图2.2.4所示，优化实现的具体步骤如下（按照A，B，C，D为出发点的顺序查找）：从A点出发寻找其他各结点的最短路径步骤：1) AB的最短路径为A，B由Dijkstra得2) AD的最短路径为A，B，D由Dijkstra得3) AC的最短路径为A，B，D，C由Dijkstra得从B点出发寻找其他各结点的最短路径步骤：4) BD的最短路径为B，D2)中已找到5) BC的最短路径为B，D，C3)中已找到6)BA的最短路径为B，D，C，A由Dijkstra得从C点出发寻找其他各结点的最短路径步骤：7)CA的最短路径为C，A6)中已找到8)CB的最短路径为C，A，B由Dijkstra得9)CD的最短路径为C，A，B，D由Dijkstra得从D点出发寻找其他各结点的最短路径步骤：10)DC的最短路径为D，C3)中已找到11)DA的最短路径为D，C，A6)中已找到12)DB的最短路径为D，C，A，B由Dijkstra得2.3利用短程线距离进行颜色混合定义点到区域的短程线距离 (2.3.1)即点到一个区域的短程线距离等于该点与这个区域内所有点之间短程线距离的最小值。对于要彩色化的像素，如图2.3.1中s，根据Yatziv颜色混合的思想，其处理后的颜色为 (2.3.2)其中权值由s到各涂色区域的短程线距离确定W(r)= (2.3.3)式中b是混合调节参数，一般取1b6。实际处理中对每个像素取3种混合色即可，仅取与之短程线距离最小的三个涂色区域的颜色。图2.3.1 颜色混合示例第3章 最短路径的图像着色在MATLAB中的实现3.1 MATLAB的介绍MATLAB和Mathematica、Maple并称为三大数学软件。MATLAB可以进行矩形运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于恭喜横计算、控制设计、信号处理与通信、图像处理、信号检测、金融建模设计与分析等领域。MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB语言已是当今国际上科学界最具影响力、也是最有活力的软件。它起源于矩阵预算，并已经发展成一种高度集成的计算机语言。MATLAB具有强大的数学运算能力、方便使用的绘图功能及语言的高度集成性。MATLAB除具备卓越的数值计算能力外，它还提供了专业水平的符号计算、文字处理、可视化建模仿真和实时控制等功能。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，因此用MATLAB来解决问题要比用C、FORTRAN等语言完成相同的事情简捷得多。MATLAB在数学计算以外的其他科学与工程领域的应用也是越来越广，并且有着更广阔的应用前景和无穷无尽的潜能。它可以将使用者从烦琐、无谓的底层编程中解放出来，把有限的宝贵时间更多地花在解决问题中，这样无疑会提高工作效率。目前，MATLAB已经成为国际上最流行的苦学与工程计算的软件工具，现在的MATLAB已经不仅仅是一个“矩阵实验室”了，它已经成为了一种具有广泛应用前景的计算机高级编程语言了，有人称它为“第四代”计算机语言，它在国内外高校和研究部门正扮演着重要的角色。MATLAB语言的功能也越来越强大，不断使用的要求提出新的解决方法。可以预见，在科学运算、自动控制、科学绘图、通信仿真等领域MATLAB语言将长期保持其独一无二的地位。3.2 MATLAB的特点MATLAB之所以能如此迅速的普及，现实出强大的生命力，是由于它有着不同于其他语言的特点。被称作第四代计算机语言的MATLAB，利用其丰富的函数资源，使编程人员从烦琐的程序代码中解放出来。MATLAB最突出的特点就是间接。MATLAB用更直观的、更符合人们思维习惯的代码，代替了C/C+和FORTRAN语言的冗长代码。MATLAB给用户提供的是最直观、最简洁的开发环境。1) 高效方便的矩阵预算MATLAB语言像BASIC、FORTRAN和C语言一样规定了矩阵的算术运算、关系运算符、逻辑运算符、条件运算符以及赋值运算符，而且这些运算符大部分可以照搬到矩阵的运算，有些如算术运算符只要增加“.”就可以用于矩阵间的运算，并且它不需要定义距阵间的维数，并给出矩阵函数、特殊矩阵专门的库函数，使之在数字信号处理、建模、系统识别、自动控制、优化等领域，显得十分简洁、高效，具有其他高级语言不可比拟的优势。2) 直观灵活的语言MATLAB不仅仅是一套打包好的函数库，同事也是一种高级的、面向对象的编程语言，使用MATLAB可事半功倍的开发自己的程序。MATLAB自身的许多函数，实际上也包括所有的工具箱函数，都是用M文件实现的。3) 先进的可视化工具MATLAB提供功能强大的、交互式的二维和三维绘图功能，可创建富有表现力的彩色图形。可视化工具包括：曲面渲染（Surface Rendering）、线框图，伪彩图、光源