图像处理算法有哪些_图像处理十大经典算法

2018-01-13 18:47:17编辑:王磊 关键字:图像处理算法  图像处理

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


图像处理概况


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

图算法领域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。


此类算法,日后阐述。


完。

关键字:图像处理算法  图像处理

来源: 互联网 引用地址:http://www.eeworld.com.cn/szds/article_2018011312970.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:ISP图像处理芯片
下一篇:Google对YouTube 视频进行严格审查 动用人工智能和机器学习进

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利

推荐阅读

基于视觉传感的焊缝跟踪技术简介

6 mm/ s.   1. 2 图像采集与处理   1. 2. 1 开小窗口分析法   采用“小窗口”获取焊缝特征信息, 在焊缝区域开了一个100 帧x120 帧的小窗口, 仅对此窗口内的图像进行处理。 该窗口包含了进行焊缝跟踪所需要的特征信息, 又削减了大量不必要的图像信息。 CCD 摄像机和送丝嘴都固定在焊枪上, 也就是焊枪、钨极、送丝嘴在图像平面投影的相对位置是不变的, 同时在试验前已经将CCD 摄像机的轴心、焊枪轴心以及焊缝调节到了同一个平面上, 如此, 焊枪的轴线在图像平面上的投影为一条水平线, 为后续的跟踪提供了便利条件。   1. 2. 2 图像处理算法   在试验中, 首先提取到焊缝的上下边缘, 经过去除伪点
发表于 2013-12-30 16:13:12
基于视觉传感的焊缝跟踪技术简介

美图宣布将自研图像处理芯片

6月27号晚,“美图T9×颐和园寻美之夜”在北京举行,正式发布了美图T9标准版。此次的美图T9除了常规的硬件、功能升级外,还着重加入了众多拍照和摄影的黑科技功能,不仅能美颜,还能“瘦身”。同时,美图宣布将进军芯片领域,推出自研的MT-AI图片处理芯片。别人家的图像处理器已经无法满足美图美图表示,公司当前在手机影像处理技术上的探索,遇到了硬件的性能掣肘。现有的手机硬件无法及时地支持某些需要庞大的计算量的尖端影像技术,比如夜景相机的降噪处理。为此,美图在云处理的软件解决方案之外,积极寻求硬件上的突破。在美图的规划中,自研的MT-AI芯片能够加快图片美化的速度,提升研发团队的效率,实现很多之前无法实现的畅想,并最终使手机超越单反相机
发表于 2018-06-29 19:27:50
美图宣布将自研图像处理芯片

ISP图像处理芯片

1、FH8510ISP处理芯片简介FH8510是一款针对CIS(CMOSImageSensor)的图像信号处理芯片,它内置强大图像处理引擎,CMOS图像传感器接口,TV编码器,D/A转换器,提供NTSC/PAL的输出,同时也提供ITU.BT65610Bit的输出,主要应用于中低端标清模拟CCTV摄像机、车载后视摄像机及楼宇对讲摄像机。FH8510可以支持多种CMOS图像传感器,具有功耗低、分辨率高、配置灵活、定制化程度高等特点。FH8510的缺省配置可以支持OV7740、OV7725,通过外接EEPROM还可以配置更多的CMOS图像传感器。FH8510的OSD采用硬件图像数据解压缩技术,全部的OSD数据可放置在EEPROM
发表于 2018-01-20 20:02:41
ISP图像处理芯片

图像处理技术是什么_图像处理技术现状和发展前景

数字图像处理概要  数字图像处理是将图像信号转换成数字信号并利用计算机对其进行处理。起源于20世纪20年代,20世纪60年—70年随着计算机技术与数字电视技术的普及和发展而迅速发展。在80年代——90年代才形成独立的科学体系。早期数字图像处理的目的是改善图像的质量,它以人为对象,以改善人的视觉效果为目的。目前该技术已广泛用于科学研究、工农业生产、生物医学工程、航空航天、军事、工业、机器人产业、政府职能机关文化文艺等多领域。并在其中发挥着越来越大的作用,已成为一门引人注目、前景广阔的新型学科。  图像是指物体的描述信息,数字图像是一个物体的数字表示,图像处理则是对图像信息进行加工以满足人的视觉心理和应用需求的行为。数字图像处理是指
发表于 2018-01-20 19:57:00
图像处理技术是什么_图像处理技术现状和发展前景

视频图像处理技术应用探析_图像处理技术在视频监视中的应用

摘 要随着科技的发展和时代的不断进步,视频和图像数据处理技术逐渐成熟起来,对人们的生活和工作起着重要的作用。视频和图像是现代生活中必备的元素,被广泛的运用在各个领域,在电影电视、视频监控、医学检查等方面具有至关重要的作用。但视频和图像处理技术属于先进的科技领域,其中涵盖了较为先进的技术和理论的应用,再加上高新设备的使用等,给图像和视频处理带来了一定的困难。所以要想提高处理技术的水平和质量就需要加大对该技术的研究和探讨。文章主要针对视频和图像处理技术的应用和发展问题进行研究和探讨,并根据存在的问题提出合理化的建议。随着经济的发展和人们生活水平的提高,视频和图像处理技术在生活中应用的范围越来越广,所以人们对新形势下图像和视频处理技术
发表于 2018-01-20 19:51:50
视频图像处理技术应用探析_图像处理技术在视频监视中的应用

AI 时代,为什么需要 eyemore 成像芯片?

面向 AI 视觉来开发成像芯片,眼擎科技想要让机器变得更智能。由于算法的演进、大量数据的涌入以及算力的提升,人工智能迎来了最好的时代。同时,从智能手机,到自动驾驶,再到安防,AI 图像视觉技术也正在被应用到越来越多的行业。但目前落地应用过程中所面临的现实的情况是,受深度学习驱动,云端视觉图像处理技术飞速发展的同时,前端视觉成像技术却依旧裹足不前,无法与之相匹配,成为了限制 AI 视觉发展的严重瓶颈。比如,2016 年的时候,一辆特斯拉 MODEL S 在自动驾驶时发生车祸,导致驾驶员死亡。究其原因,正是由于在逆光以及反光的情况下,其所配备的摄像头无法识别前方车辆,才酿成了那起事故。当算法以及超强的计算能力赋予了机器逻辑思维能力之后
发表于 2018-01-16 10:38:04

小广播

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: 电视相关 白色家电 数字家庭 PC互联网 数码影像 维修拆解 综合资讯 其他技术 技术产品 应用设计 论坛

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved