随着现代社会的发展,信息的形式和数量正在迅猛增长。其中很大一部分是图像,图像可以把事物生动地呈现在我们面前,让我们更直观地接受信息。同时,计算机已经作为一种人们普遍使用的工具为人们的生产生活服务。
图像处理概况图像处理,是对图像进行分析、加工、和处理,使其满足视觉、心理以及其他要求的技术。图像处理是信号处理在图像域上的一个应用。目前大多数的图像是以数字形式存储,因而图像处理很多情况下指数字图像处理。本文接下来将简单粗略介绍下数字图像处理领域中的经典算法。
图算法领域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,入选本图算法十大算法,自是无可争议。
因为,这俩种搜索算法,应用实为广泛而重要。
关于此BFS、DFS算法,更多,请参考:
http://blog.csdn.net/v_JULY_v/archive/2011/01/01/6111353.aspx
三、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)出列,继续扩展下一个结点。如此
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)