2018年01月13日 | 图像处理算法有哪些_图像处理十大经典算法

随着现代社会的发展，信息的形式和数量正在迅猛增长。其中很大一部分是图像，图像可以把事物生动地呈现在我们面前，让我们更直观地接受信息。同时，计算机已经作为一种人们普遍使用的工具为人们的生产生活服务。

图像处理概况

图像处理，是对图像进行分析、加工、和处理，使其满足视觉、心理以及其他要求的技术。图像处理是信号处理在图像域上的一个应用。目前大多数的图像是以数字形式存储，因而图像处理很多情况下指数字图像处理。本文接下来将简单粗略介绍下数字图像处理领域中的经典算法。

图算法领域10大经典算法

基本遍历

一、深度优先搜索

深度优先搜索算法思想

深度优先遍历图的方法（一种递归的定义）是，假定给定图G的初始状态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作：

1）访问搜索到的未被访问的邻接点；

2）将此顶点标记为已访问节点；

3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。

深度优先搜索算法实现：

1. 使用栈来实现。相关算法实现总结为：

1） 将初始节点压栈。

2） While（栈非空） {

3） 取出栈顶点，暂时存储这个节点node_t信息。

4） 访问该节点，并且标示已访问。

5） 将栈顶元素出站。

6） For（遍历node_t的相邻的未访问过的节点）{

7） 将其入栈。

}

}

注意事项：一定要先将该访问节点出栈后，再将其邻接的未访问的节点入栈。切记不要，之前我的经历，如果没有邻接点就出栈，否则就不出站，但是标记了该节点为访问节点的。

2. 使用递归来实现。相关算法实现总结为：

1） DFS（初始节点）

2） FuncTIon DFS（一个节点） {

3） 访问该节点，并且标示已访问。

4） For（遍历该节点的相邻的未访问过的节点） {

5） DFS（这个邻接节点）。

}

}

二、广度优先搜索

此图遍历中最基本的俩种算法，BFS，DFS，入选本图算法十大算法，自是无可争议。

因为，这俩种搜索算法，应用实为广泛而重要。

三、A*搜索算法

DFS和BFS在展开子结点时均属于盲目型搜索，也就是说，

它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。

在运气不好的情形中，均需要试探完整个解集空间， 显然，只能适用于问题规模不大的搜索问题中。

A*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。

而A*算法最为核心的部分，就在于它的一个估值函数的设计上：

f（n）=g（n）+h（n）

其中f（n）是每个可能试探点的估值，它有两部分组成：

一部分，为g（n），它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。

一部分，即h（n），它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。

更多，请参考：

经典算法研究系列：一、A*搜索算法

附：

Flood Fill

LeeMaRS、wtzyb4446：

图形学中Flood Fill是满水法填充，是用来填充区域的。

就好比在一个地方一直到水，水会往四周满延开，直到高地阻挡。

Flood Fill就是从一个点开始往四周寻找相同的点填充，直到有不同的点为止。

我们用的Flood Fill和这个差不多原理，就是BFS的一种形式。

假设在（i，j）滴好大一滴红墨水，然后水开始漫开，向它的上下左右染色，也就是（i-1，j），（i+1，j），（i，j-1），（i，j+1）这四个点。然后在分别再从这四个点开始向周围染色。。。直到碰到某种边界为止。

把这个转化为BFS的思想，就是队列中初始元素是（i，j），然后把（i，j）扩展状态，得到（i-1，j），（i+1，j），（i，j-1），（i，j+1）这四个状态，加入队列。把（i，j）出列，继续扩展下一个结点。如此
 

最短路径算法

四、Dijkstra

Dijkstra 算法，又叫迪科斯彻算法（Dijkstra），

算法解决的是有向图中单个源点到其他顶点的最短路径问题。

五、Bellman-Ford

Bellman-Ford：

求单源最短路，可以判断有无负权回路（若有，则不存在最短路），

时效性较好，时间复杂度O（VE）。

是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k《《V）。

六、Floyd-Warshall

Floyd-Warshall：求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O（V^3）。此算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。

附：Kneser图

Kneser图是与图的分数染色有关的算法。

给定正整数a，b，a≥2b，Kneser图Ka:b是以如下方式定义的一个图：

其顶点是从给定的a个元素的集合中选出的b个元素构成的子集，两顶点间有边当且仅当这两个顶点为不交的集合。

最小生成树

七、Prim

八、Kruskal

此最小（权值）生成树的俩种算法，日后，会在本BLOG内 具体而深入阐述。

图匹配

九、匈牙利算法

匈牙利算法是众多用于解决线性任务分配问题的算法之一，是用来解决二分图最大匹配问题的经典算法，可以在多项式时间内解决问题，由匈牙利数学家Jack Edmonds于1965年提出。

这个算法，比较生疏，下面，稍微阐述下：

I、匈牙利算法应用问题的描述：

设G=（V，E）是一个无向图。如顶点集V可分区为两个互不相交的子集V1，V2之并，并且图中每条边依附的两个顶点都分属于这两个不同的子集。则称图G为二分图。二分图也可记为G=（V1，V2，E）。

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 选择这样的子集中边数最大的子集称为图的最大匹配问题（maximal matching problem）

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备，完美匹配。

II、算法描述

求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。

下面介绍用增广路求最大匹配的方法（称作匈牙利算法，匈牙利数学家Edmonds于1965年提出）。

增广路的定义（也称增广轨或交错轨）：

若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边（即已匹配和待匹配的边）在P上交替出现，则称P为相对于M的一条增广路径。

由增广路的定义可以推出下述三个结论：

1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。

2－将M和P进行异或操作（去同存异）可以得到一个更大的匹配M’。

3－M为G的最大匹配当且仅当不存在M的增广路径。

算法轮廓：

1）置M为空

2）找出一条增广路径P，通过异或操作获得更大的匹配M’代替M

3）重复（2）操作直到找不出增广路径为止

III、时间复杂度与空间复杂度

时间复杂度

邻接矩阵：最坏为O（n^3） 邻接表：O（mn）

空间复杂度：

邻接矩阵：O（n^2） 邻接表：O（m+n）

附：

Edmonds‘s matching

强连通分支算法与网络流

十、Ford-Fulkerson

最大流量算法（Ford-Fulkerson Algorithm），

也叫做贝尔曼-福特算法，被用于作为一个距离向量路由协议例如RIP， BGP， ISO IDRP， NOVELL IPX的算法。

附：Edmonds-Karp、Dinic、Push-relabel、maximum flow

强连通分支算法：

Kosaraju、 Gabow、 Tarjan。

此类算法，日后阐述。

完。