图像处理十大经典算法

图像处理，是对图像进行分析、加工、和处理，使其满足视觉、心理以及其他要求的技术。图像处理是信号处理在图像域上的一个应用，目前大多数的图像是以数字形式存储，因而图像处理很多情况下指数字图像处理。

随着现代社会的发展，信息的形式和数量正在迅猛增长。其中很大一部分是图像，图像可以把事物生动地呈现在我们面前，让我们更直观地接受信息。下面简单介绍下数字图像处理领域中的经典算法。

一、深度优先搜索

深度优先遍历图的算法是，假定给定图G的初始状态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用步骤：

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

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

3、搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索，反复进行直到所有节点都被访问为止。

二、广度优先搜索

广度优先搜索算法，又称为”宽度优先搜索”，简称BFS。它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。

如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。也就是说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。

三、A*搜索算法

A*算法（A-Star），作为启发式搜索算法中的一种，是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法，被广泛应用在最优路径求解和一些策略设计的问题中。

A*算法操作：首先将起始结点S放入OPEN表，CLOSE表置空，算法描述：

1、如果OPEN表不为空，从表头取一个结点n，如果为空算法失败。

2、n是目标解吗？是，找到一个解（继续寻找，或终止算法）。

3、将n的所有后继结点展开，就是从n可以直接关联的子结点，如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1。

四、Dijkstra算法

又叫迪科斯彻算法，是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法采用的是一种贪心的策略，基本算法思想：

1、通过Dijkstra计算图G中的最短路径时，需要指定起点s。

2、引进两个集合S和U。S的作用是记录已求出最短路径的顶点，而U则是记录还未求出最短路径的顶点。

3、初始时，S中只有起点s，U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

五、Bellman-Ford算法

Bellman – ford算法是求含负权图的单源最短路径的一种算法，其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

Bellman-Ford算法能在更普遍的情况下解决单源点最短路径问题，算法描述：

1、初始化：将除源点外的所有顶点的最短距离估计值。

2、迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离。

3、检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解。否则算法返回true，并且从源点可达的顶点v的最短距离保存在集合dist[v]中。

六、Floyd-Warshall算法

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。

算法思想：

1、创建源顶点 v 到图中所有顶点的距离的集合S，为图中的所有顶点指定一个距离值，初始均为I，源顶点距离为0。

2、计算最短路径，执行 V – 1 次遍历。

3、对于图中的每条边：如果起点u的距离d 加上边的权值w小于终点v的距离d，则更新终点v的距离值d。

4.检测图中是否有负权边形成了环，遍历图中的所有边，计算u至v的距离，如果对于v存在更小的距离，则说明存在环。

七、Prim算法

图论的一种算法，可在加权连通图里搜索最小生成树。由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

Prim算法在找当前最近顶点时使用到了贪婪算法，算法描述：

1、 在一个加权连通图中，顶点集合V，边集合为E。

2、任意选出一个点作为初始顶点,标记为visit,计算所有与之相连接的点的距离，选择距离最短的，标记visit。

3、在剩下的点，计算与已标记visit点距离最小的点，标记visit,证明加入了最小生成树，重复操作，直到所有点都被标记为visit。

八、Kruskal算法

Kruskal算法是一种用来寻找最小生成树的算法,在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

Kruskal算法就是基于并查集的贪心算法,算法描述：

1、将图G看做一个森林，每个顶点为一棵独立的树。

2、将所有的边加入集合S，即一开始S = E 。

3、从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E’。

4、重复3直到所有点属于同一棵树，边集E’就是一棵最小生成树。

九、匈牙利算法

匈牙利算法是用于解决线性任务分配问题的算法之一，该算法的核心就是寻找增广路径，是用来解决二分图最大匹配问题的经典算法，可以在多项式时间内解决问题。

算法轮廓：

1、置M为空

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

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

十、Ford-Fulkerson算法

也称最大流量算法，常用于作为一个距离向量路由协议例如RIP， BGP， ISO IDRP， NOVELL IPX的算法。

Ford-Fulkerson 算法是一种迭代方法。开始时，对所有 u, v ∈ V 有 f(u, v) = 0，即初始状态时流的值为 0。在每次迭代中，可通过寻找一条增广路径来增加流值。增广路径可以看做是从源点 s 到汇点 t 之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直至增广路径都被找出为止。