基于最短路径的图像着色毕业论文(编辑修改稿)

基于最短路径的图像着色毕业论文(编辑修改稿)内容摘要：

以用一个圆锥空间模型来描述，此圆锥模型 比较复杂，但确能把色调、亮度及饱和度的变化情形表现得很清楚。 由于人的视觉对亮度的敏感程度远强于对颜色浓淡的敏感程度，采用 HSI色彩空间比 RGB 空间更符合人的视觉特性，也更便于色彩处理和识别。 在图像处理和计算机视觉中大量算法都可在 HSI 色彩空间中方便地使用，它们可以分开处理而且是相互独立的。 因此，在 HSI 色彩空间可以简化图像分析和处理的工作量。 HSV空间与 HSI 类似，区别是亮度分量的计算不同，从而使得亮度和饱和度的分布及动态范围有一定差异。 色彩空间在本质上是颜色的描述方式，考虑其对颜色的描述角度，可以用一种更为宽泛的形式对色彩空间进行分类，即分为由颜色分量表示的基本色空间和利用颜色要素表达的色彩属性空间 ； 前者如 RGB、 CMYK 空间， YIQ、 YUV、YCbCr 及 HSI、 HSV等空间都归为后者。 顾名思义，基本色空间重在说明颜色的构成，如 RGB 模型明示了颜色三基色分量， CMYK 用以说明打印一种颜色需用的颜料配比。 颜色属性空间则直接与人眼对颜色的视觉感受，即颜色三要素 (亮度、色调、饱和度 )密切相关，更加符合人的视觉信息获取过程。 颜色属性空间的显著特征就是亮色分离。 基于最短路径的图像着色 10 颜色描述中是否实现亮色分离，是区分宽泛分类色彩空间的主要标志。 实现亮色分离就可以对颜色的亮度和色度进行单独处理，这为一些图像处理问题带来极大便利。 的介绍 最短路径 最短路径这一重要问题早在 20 世纪初就已经得到人们的高度重视，当时也有许多科学家研究这一重要问题的求解方法。 但直到 1959 年荷兰计算机科学家Dijkstra（迪杰斯特拉）才给出这一问题求解的基本思想，并给出了算法。 后来这个算法就成了众所周知的 Dijkstra 算法，也成为了一代经典。 当时的 Dijkstra提出的这一算法主要解决的问题是从固定的一个点到其他各点的最短路径问题。 但是在实际生活中往往要求解决的不只是固定一点到其他点的最短路径，而是要求计算出任意两点之间的最短距离。 随着社会的不断进步，最短路径算法在人们的日常生活中显得越来越重要。 所谓最短路径就是网络中两点之间距离最短的路径，这里讲的距离可以是实际的距离，也可以引申为其他的度量，比如时间、运费、流量等。 因此，从广义上讲，最短路径算法就是从网络中找出两个点之间最小阻抗路径的算法。 最短路径的定义 最短路径的概念：短程线距离的概念： tsc, (p)表示连接图像中两点 r , s 的曲线， Y 代表像素的亮度， r , s 间的短程线距离义为 ptsc dpCYtsd ts   )(m in),( , () 短程线距离对应于连接两点的所有曲线中、沿曲线方向像素亮度值的梯度积分的最小值，即短程线表示从图像中一点到另一点的灰度变化最平缓的路径。 最短路径 的离散化定义：在数字图像中短程线距离的计算需要采用离散形式，现给出一种更直观的离散定义。 用 Y 表示像索的亮度，则图像中相邻两点 r、基于最短路径的图像着色 11 s 间的短程线距离为 )()(),( tYsYtsd  () 定义图像中 8连通的曲线 },...,{ 21 mpppC  上的曲线距离 ),()( 1111  imi ippc ppdcd m () 则图像中两点间的短程线距离等于连接这两点的所有曲线中的最短距离 )(min),( stc cdtsd  () 这种离散定义形式便于进行计算。 短程线距离是定义在图像中的某种最短距离，在图论中也有类似的最短距离。 给定一个双向图 G，它的每条边都有一个非负的长度，路径的长度即为次路径经过的边的长度之和。 图 (a)给出了一个具有五个顶点的有向图，各边上的数即为长度，假设源顶点 s为 1，从顶点 1出发到各顶点的最短路径按长度顺序列在图 (b)中，每条路径前的数字为路径长度。 对于图像而言，如果把每个像素对应图中的顶点，相邻像素间的亮度差看作图中顶点间的边长，那么所谓短程线距离就可等效于图论中的 最短距离。 (a)图 1 4 3 2 5 2 4 8 5 3 4 1 基于最短路径的图像着色 12 0 2 3 4 6 (b)图最短路径 图 最短路径的基本思路 为了解决最短路径问题，首先应根据要求选取一种量度标准。 然后将 n 个输入排成这种量度标准要求的顺序，按照这种顺序一次输入一个量。 如果这个输入和当前已经构成的在这种量度意义的部分最优解加在一起能产生一个可行解，则把此输入加到这部分最优解中，否则不加入。 这种能够在某种量度意义下得到最优解的分级处理方法称为贪心算法。 按照上面的思路，可以逐步地构造出这些最短路。 使用迄今已经生成的所有路径长度之和作为一种量度，为了使这一量度达到最小，单独的每一条路径都必须具有最小长度。 使用这一量度标准，假定已经构造了 n 条最短路径，则下面要构造的路径应该是下一条最短的最小长度路径。 如何根据贪心算法，确定路径上的每个节点而最终求得最短路径， Dijkstra提出了一个按路径长度递增的次序产生到各顶点的最短路径的算法。 1)假设用带权的邻接矩阵 cost 来表示一个带权图， ],[cos jit 表示弧 iV ， jV 上的权值。 若 iV ， jV 不存在，则置 ],[cos jit 为  （ 在计算机上可以用允许的最大整数值来表示）， S 为已找到从 oV 点出发的最短路径的集合，它的初态为空集。 0 2 3 4 6 1 1 1 1 1 3 3 2 3 4 4 5 基于最短路径的图像着色 13 从 oV 到其他结点的路径长度向量为 ][ndist。 那么从 oV 出发到图上其余顶点 iV 可能达到的最短路径长度的初值为 VViVtid ist io  ],[c o s][ （ ） 2)选择 jV 使得 dist[j]=min{dist[j]， iV VS}， jV 就是当前求得的一条从 oV 出发的最短路径的终点。 令 S=S║ { jV }。 3)修改从 oV 出发到集合 VS上任一顶点 kV 可达的最短路径长度。 如果 ][],[c os][ kdi sstkjtjdi st  则修改 ][kdist 为 ],[c os][][ kjtjdi stkdi st  4)重复操作 2)， 3)共 n1 由此求得从 oV 到图上其余各个结点的最短路径。 这是依据路径长度递增的序列而求得的。 最短路径的基本方法 传统的利用 Dijkstra 算法来实现图中任意结点之间的最短路径查找 ， 其基本思想就是依次以图中各个结点为起点利用 Dijkstra 算法计算出最短路径 ， 这样循环 n 次即可得到图中任意结点之间的最短路 ，而每 步都是一个简单的重复过程。 这样虽然能够实现任意两点之间的最短路径查找 ， 但是从效率上分析并不是最优的。 实际是可以进行改进 ， 具体方法如下 ： 1） 根据 Dijkstra 算法思想 ， 可以由图中结点的出入度信息来提高各点之间最短路径的查找速度。 2） 在带权图中利用 Dijkstra 算法找出部分结点之间的最短路径后 ， 若其他还没有找出最短路径的结点可以利用前面已找出的最短路径信息为自己提供快速的最短路径查找。 1. 利用结点入度信息查找 根据结点的入度信息来优化查找最短路径的基本思想是 ： 当某结点的入度为0时 ， 图中其他结点到该结点的最短路径都为无穷 （ 不可达 ） 并且其他结点之间的最短路径也不会出现该结点 ， 所以在求图中其他各结点之间的最短路径时 ， 可以将该结点先删除以简化整个 图的最短路径的查找。 根据上述基本思路 ， 给出优化查找的具体步骤 ： 基于最短路径的图像着色 14 1)求出图中各结点的入度 ； 2)找到入度为 0的结点 ， 记作 1V ； 3)从 1V 点出发开始用 Dijkstra 算法求 1V 到其他各结点的最短路径 ； 4)求完后 ， 若结点 1V 入度为 0 则删除该结点 ， 从而简化了连接图 ， 也简化了查找步骤 ； 5)重复 2)， 3)步 ， 直到没有入度满足条件的结点。 如图 所示 ， A 的入度为 0， 当求出了以 A 点出发到图中其他各点的最短路径后 ， 再求其他结点间的最短路径时 ， 就可以将结点 A 删除 ， 并把其他结点到 A 结点的最短路径记为无穷大即可。 5 6 8 7 9 图 将图 A 删除后的图像如图 所示 ， 这样使得 B， C， D结点之间最短路径的查找更 为简便。 7 9 如 A 入度为 0， A 执行完 3） ,4） 步后的图示 B C D A B C D 基于最短路径的图像着色 15 2. 利用结点出度信息查找 基于结点出度信息查找图中各结点间的最短路径的基本思想是 ： 当某结点的出度为 0时 ， 从该结点出发到图中任何一个结点都是不可达的。 其次 ， 当某个结点的出度为 1时 ， 该结点只有唯一的后继结点。 并且该结点到其他结点的最短路径必须经过此后继结点。 当该结点的这个唯一的后继结点到其他各结点的最短路径已经求出以后 ， 该结点到其他各结点的最短路径也就可以求出了。 只需在其唯一后继结点的最短路径求出后再加上其唯一出度边的权值即可。 根据上面讨论的基本思想 ， 下面是从出度着手查找的具体步骤 ： 1)首先求出图中所有结点的出度 ； 2)找到出度为 0或为 1的结点 ， 记作 mV ； 3)若出度为 0， 则不必去求从该结点出发的最短路径了 ， 因为从该结点出发是不可能找出到其他结点的最短路径 （不可 达 ）； 4)若出度为 1则也不必去求从该结点出发的最短路径了 ， 只需在其唯一后继结点的最短路径求出后再加上其唯一出度边的权值即可 ； 5)重复 2)、 3)、 4)步 ， 直到没有出度满足条件的结点。 不论是从入度还是从出度着手都应该考虑出入度为 1 的多个结点 ， 并注意其前驱结点的顺序。 3. 利用已找出的最短路径快速查找 这种优化方法的基本思想是 ： 根据图 所示 ， 假设从源点 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。