文档章节

一种可实时处理 O(1)复杂度图像去雾算法的实现。

abcijkxyz
 abcijkxyz
发布于 2016/11/22 16:40
字数 2921
阅读 4
收藏 0
点赞 0
评论 0

  在我博文的一系列的文章,有不少算法都于去雾有关,比如限制对比度自适应直方图均衡化算法原理、实现及效果局部自适应自动色阶/对比度算法在图像增强上的应用这两个增强算法都有一定的去雾能力,而最直接的就是《Single Image Haze Removal Using Dark Channel Prior》一文中图像去雾算法的原理、实现、效果及其他 一文,描述了暗通道去雾这一state-of-the-art algorithms的过程和实现,虽几经优化,对于常用的视频1024*768大小的图片,算法处理部分还是需要70MS的时间(I3 笔记本CPU),因此,这一算法用于实时要求时还有一定的难度,并且优化后的算法基本无法并行,而可并行的算法重复计算大,由于不熟悉GPU方面的理念,不晓得使用不优化的算法靠GPU是否能有多大速度的提升。

     为此,我一直在找寻相关的论文,这种找寻的踪迹一般就是看到一篇好论文--》看其参考文献--》再看参考文献的参考文献,这样循环下去。 然后有某种机会或巧合,又看到一篇好论文,重复前面的过程,你就会发现很多交集,慢慢的就会有一些好运向你招手。 话说我原本只看英文的文献,所以一直忽略了国内的文章,前几日,一个QQ朋友推荐了一篇清华大学的论文,下载后稍微看了下,觉得其描述的结果还是比较吸引人的,于是就实现了下,实时的效果应该说很不错,这里就简单的介绍并推荐给大家。

      原始论文下载:基于单幅图像的快速去雾.pdf  ,作者刘倩,陈茂银,周东华,感谢他们(她们)。

      算法原理没有什么复杂的地方,其实说原理,还不如说经验或实验,因为论文中可以用理论来推导的公式确实不多。不过这也没关系,有用的东西就应该拿来用。

      算法的执行流程直接贴用原图的文字来说明吧:

     

     先挑点小瑕疵,比如步骤5中的L有个下标,而其他涉及到L的地方去没有,这叫前后不一致。论文中也还有一些其他的地方有些小错误,所以看啊,即使是清华的文章,在编辑审核这一块还是相当的不严谨。

     我们先来看看算法,1、2、3、4步都没有什么说的,第五步是求大气透射率的过程,这里ρ是一个用来调节的参数,当ρ值越大时,结果图像整体越暗,去雾的效果更明显,ρ较小时,图像偏白,有明显的雾气。第六步求全局大气光A值,用了很简单的方式,即求原始图像的RGB所有像素分量的最大值(这个估计99%都为255了)何暗通道的最大值的平均值,并且注意到RGB三个通道用的A值都为同一个数字。这个和我在何凯明的文章的分析也有相似的地方。 第七步用了标准的去雾模型来求结果值。

     在来看看算法的效率问题, 从算法的初步分析来看,算法的效率取决于第3步和第7步,第三步中,使用了均值模糊,目前已经存在大量的O(1)均值模糊算法,可是O(1)只能表示算法的执行速度和参数的大小无关系,并不表示算法就很快。比如基于积分图的模糊算法是广为认知的O(1)算法,但是他也存在很多问题,最严重的就是数据的溢出,当图像较大和偏白时,对图像积分图的累加和存在超出int.Maxvalue所能表达的范围的问题,解决办法就是积分图内的数据全部使用long类型表示,这将导致程序多占用Width*Height*4字节的大小的内存,且在32位系统还流行的情况进一步降低程序的速度(32位系统64位整数的计算速度要比32位整数慢)。积分图的另外一个问题就是计算积分图的过程难以并行化,因为一个像素的积分值是依赖于其前面一系列像素的相关结果值的。另外一种优化方式就是先计算行方向的平均值,然后再计算列方向的值。这种方式在同一行(列)内,算法依旧必行顺序执行,这也是因为前后影响的原因。但是不同行(列)之间的计算是没有任何关系,因此非常适合GPU这种可大规模并行计算的场合,但不适于CPU这种重量级的线程并发(反而会慢)。这种算法如果为了精度会需要一个和原图一样大小,占用字节Width*Height*4字节大小的的中转区用来保存中间计算的结。在彩色图像高速模糊之懒惰算法一文中,我采用了另外一种处理方法,利用列直方图相关的技术,只需对每个循环的起始位置处的像素做特殊处理,其他位置的利用简单的一加一简即可获得累加和,从而快速的实现模糊,我实际的编码表明,这种方式比其他的方式都要快。但是有一个缺点,不适合于并行计算,不过在CPU上这个很有优势。

      再观察下第七步。第七步存在两个需要优化的地方,第一,存在除法;第二,有浮点运算。如果直接编码必然会带来性能损失,但是,观察下在第七步的公式中,只有两个自变量,H(X)和L(X),并且自变量的取值都为[0,255]之间的整数,因此,如果事先建议一个查找表,由于这个查找表的计算量只有 256*256次,要远远的小于直接计算的次数,必然能提高程序的速度。256这个数字还有个好处,就是可以用移位来辅助计算查表表的下标,部分参考代码如下所示:

unsigned char * Table = (unsigned char  *) malloc (256*256*sizeof(unsigned char));
for (Y = 0; Y < 256; Y++)
{
    Index=Y<<8;
    for (X = 0; X < 256; X++)
    {
        Value = (Y-X) /(1-X*InvA);
        if (Value > 255)
            Value = 255;
        else if (Value < 0)
            Value = 0;
        Table[Index++]= Value;
    }
}

  其中InvA = 1 / A;A为全局大气光值。 Value需为double类型的变量。

     当我们需要计算F(x)时,查表的方式为 F(X)=Table[(H[X]<<8 )+ L[X]];

     实际的效果表明,这样的方式对于1024*768的图,可以提速10ms。

     那么对于其他步骤也有很多优化的注意事项,比如计算M(X)中所有元素的平均值Mav这一块,完全没有必要在开一个循环,而是可以在进行步骤3的时候同步进行,大家知道,循环楚了要计算循环体内部的东西外,还要有个循环计数器的更新的,何必浪费这个时间呢。

for (Y = 0, DarkPt = DarkChannel; Y < Height; Y++)
{
    ImgPt = Src + Y * Stride;
    for (X = 0; X < Width; X++)
    {
        Min = *ImgPt;
        if (Min > *(ImgPt + 1)) Min = *(ImgPt + 1);
        if (Min > *(ImgPt + 2)) Min = *(ImgPt + 2);
        *DarkPt = Min;                                        //    三通道的最小值
        Sum    +=    Min;                                        //  累积以方便后面求平均值
        ImgPt += 3;
        DarkPt++;
    }
}
Mean =(double)Sum /(Width*Height*255);

    还有比如第6步中,分别求原图RGB三像素最大值以及安通道中的最大值的过程,传统的过程如下代码:

int Max1 =0 ;
for (Y = 0; Y < Height; Y++)
{
    ImgPt = Src + Y * Stride;
    for (X = 0; X < Width; X++)
    {
        if (Max1 < *(ImgPt)) Max1 = *(ImgPt);
        if (Max1 < *(ImgPt + 1)) Max1 = *(ImgPt + 1);
        if (Max1 < *(ImgPt + 2)) Max1 = *(ImgPt + 2);
        ImgPt += 3;
    }
}

  特别是对于求原图的最大值,实际上很多情况下这个值都为255,因此如果Max1变量已经是255,则循环完全没有必要进行下去了,因此,如果改为下述代码,必然可以减少计算量:

for (Y = 0; Y < Height; Y++)
{
    ImgPt = Src + Y * Stride;
    for (X = 0; X < Width; X++)
    {
        if (Max1 < *(ImgPt)) Max1 = *(ImgPt);
        if (Max1 < *(ImgPt + 1)) Max1 = *(ImgPt + 1);
        if (Max1 < *(ImgPt + 2)) Max1 = *(ImgPt + 2);
        ImgPt += 3;
    }
    if (Max1==255) break;
}

      注意,这个break语句必须放在Y循环中,如果放在X循环中,虽然提前退出循环的可能性会增加,但是判断的工作量带来的损失更多。
      综合上述优化,我用C++写了个DLL,对于1024*768的图像在我的I3的机器上平均能达到18ms每副图像的计算速度,相当于56fps,只占用了单核的资源,考虑解码、显示等等其他过程所占用的时间,应该是能够靠CPU实现20fps的实时速度的。

      在内存占用上,约需要> 3*Width*Height+256*256字节的空间(不包括图像本身的),如果用在连续的视频处理上,这部分内存就不需要频繁的分配和释放,可能也对速度的保证有好处。

     程序下载地址: http://files.cnblogs.com/Imageshop/FastHazeRemovalTest.rar

  

 参数的选取:

    为了获得好的效果,该算法需要选择恰当的参数,我们为此做了一些测试。对于半径参数,我的个人建议是取值不要小于50或图像宽度和高度最大值的的1/20,比如对下面的图像(原图大小不是下图中的大小,这里是为了方便浏览缩小显示的),ρ取1.28时(对于上图中的去雾程序选择为128),半径取不同参数时的效果:

   

             原图                               r=16                          r=50

   注意上面中间的图,一群飞鸟的周边明显有格格不入的白色雾气,而在右侧的图中,飞鸟则自然的融入了背景图像中。

   另外,当半径足够大时,半径的大小对输出的结果的影响不大。

   ρ参数的大小控制了图像去雾能力的大小,越大,雾气越少,图像越显得暗,越小,图像偏白,雾气越浓,下面给出了在半径R=50,取不同ρ值的效果。

   

   

   

              原图                               ρ=0.75                          ρ=1.3

     ρ值如何取才能获得最佳效果,这个没有理论依据,需要根据具体图像进行测试,不过一般在1.2到1.5之间的效果能综合去雾和保持图像清晰的能力。

     从更多的测试图看,该去雾算法的效果都是较为理想的,而且对于填充部位出现瑕疵的情况也出现的很少,速度上更是没的说,因此,作为一种实时去雾工业化也应该是可行的。

     试过将过程中的均值模糊更改为高斯模糊,在速度上会稍有下降,也能达到实时要求,但去雾的效果似乎还没有均值好。

    

 

*****************************基本上我不提供源代码,但是我会尽量用文字把对应的算法描述清楚或提供参考文档*********************

*************************************因为靠自己的努力和实践写出来的效果才真正是自己的东西,人一定要靠自己****************************

*********************************作者: laviewpbt   时间: 2013.11.4   联系QQ:  33184777  转载请保留本行信息************************

本文转载自:http://www.cnblogs.com/Imageshop/p/3410279.html

共有 人打赏支持
abcijkxyz
粉丝 61
博文 6195
码字总数 1876
作品 0
深圳
项目经理
高斯模糊算法的 C++ 实现

  2008 年在一个 PS 讨论群里,有网友不解 Photoshop 的高斯模糊中的半径是什么含义,因此当时我写了这篇文章:   对Photoshop高斯模糊滤镜的算法总结;   在那篇文章中,主要讲解了高...

hoodlum1980 ⋅ 2015/05/25 ⋅ 0

28个不得不看的经典编程算法

转载自:28个不得不看的经典编程算法 第一名:Union-find 严格地说,并查集是一种数据结构,它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构,使得编程复杂度降低到了令人...

xjhznick ⋅ 2014/11/06 ⋅ 0

数据结构基本概念 - 学习笔记

数据结构基本概念 1 数据:数据是用来描述现实世界的数字、字符、图像、声音,以及能够输入到计算机中并能被计算机处理的符号集合 2 数据元素:数据元素是数据的基本单位,在计算机中通常作为...

wqli ⋅ 2012/09/22 ⋅ 0

[发布] Photoshop 油画效果滤镜

    【原创性声明】本滤镜是我采用 PS SDK 开发而成,而滤镜的算法具体是由谁提出的可能不详,我是参考了 FilterExplorer 的源码(VC 6),本算法的主要参考来源是该项目中的 Filters.cp...

hoodlum1980 ⋅ 2011/01/15 ⋅ 0

【万能搜索】万能DFS之全排列(一)——普通算法

DFS相信大家都很熟悉,下面就给出一种用DFS实现的算法。 全排列 大家对于全排列是很熟悉的,比如123的全排列就有: 123 132 213 231 312 321 这六种。 现在,我们来设计一个算法,来求出所有...

qq_37656398 ⋅ 2017/12/03 ⋅ 0

用机器学习构建O(N)复杂度的排序算法,可在GPU和TPU上加速计算

  选自arXiv   作者:Hanqing Zhao等   机器之心编译   参与:刘晓坤、李亚洲      排序一直是计算机科学中最为基础的算法之一,从简单的冒泡排序到高效的桶排序,我们已经开发了...

机器之心 ⋅ 05/16 ⋅ 0

二维灰度地形图山脊线自动提取方法整理(MST)

概述 本方法的目标位快速,自动,准确地提取DEM格式图像中山脊线(或山谷线),其在水文地质工程应用方面有着特殊的意义。算法基本处理流程为: 构建基于原始DEM图像的图G; 对G中各边V赋予权...

tbtbtbtbtbtbtb ⋅ 2017/02/13 ⋅ 0

用户画像系统

用户画像分析是当前互联网产品对用户进行数据分析常用的一个手段,比如推荐场景,常见的算法是协同过滤算法,基于用户相似度和基于物品相似度,但是这两种算法适用的场景往往比较有限。 1.基...

满小茂 ⋅ 01/13 ⋅ 0

算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方 ⋅ 2017/12/14 ⋅ 0

游戏排行榜算法设计实现比较

  以前在音乐做过一些实时投票,积分排名;单曲、专辑等排行榜;游戏中也有类似的战斗力排行;SNS的游戏又有好友排行等,对于此类的排行算法在此做个总结。   需求背景:   查看前top...

shezjl ⋅ 2015/10/04 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Greys Java在线问题诊断工具

Greys是一个JVM进程执行过程中的异常诊断工具。 在不中断程序执行的情况下轻松完成JVM相关问题排查工作 目标群体 有时候突然一个问题反馈上来,需要入参才能完成定位,但恰恰没有任何日志。回...

素雷 ⋅ 27分钟前 ⋅ 0

git从远程仓库拉取代码的常用指令

一种(比较麻烦的)拉代码的方法 git clone //克隆代码库,与远程代码库的主干建立连接,如果主干已经在就不用再clone啦,克隆路径为当前路径下的新创建的文件夹 git checkout -b //本地建立...

Helios51 ⋅ 42分钟前 ⋅ 0

005. 深入JVM学习—Java堆内存参数调整

1. JVM整体内存调整图解(调优关键) 实际上每一块子内存区域都会存在一部分可变伸缩区域,其基本流程:如果内存空间不足,则在可变的范围之内扩大内存空间,当一段时间之后,内存空间不紧张...

影狼 ⋅ 47分钟前 ⋅ 0

内存障碍: 软件黑客的硬件视图

此文为笔者近日有幸看到的一则关于计算机底层内存障碍的学术论文,并翻译(机译)而来[自认为翻译的还行],若读者想要英文原版的论文话,给我留言,我发给你。 内存障碍: 软件黑客的硬件视图...

Romane ⋅ 今天 ⋅ 0

SpringCloud 微服务 (七) 服务通信 Feign

壹 继续第(六)篇RestTemplate篇 做到现在,本机上已经有注册中心: eureka, 服务:client、order、product 继续在order中实现通信向product服务,使用Feign方式 下面记录学习和遇到的问题 贰 or...

___大侠 ⋅ 今天 ⋅ 0

gitee、github上issue标签方案

目录 [TOC] issue生命周期 st=>start: 开始e=>end: 结束op0=>operation: 新建issueop1=>operation: 评审issueop2=>operation: 任务负责人执行任务cond1=>condition: 是否通过?op3=>o......

lovewinner ⋅ 今天 ⋅ 0

浅谈mysql的索引设计原则以及常见索引的区别

索引定义:是一个单独的,存储在磁盘上的数据库结构,其包含着对数据表里所有记录的引用指针. 数据库索引的设计原则: 为了使索引的使用效率更高,在创建索引时,必须考虑在哪些字段上创建索...

屌丝男神 ⋅ 今天 ⋅ 0

String,StringBuilder,StringBuffer三者的区别

这三个类之间的区别主要是在两个方面,即运行速度和线程安全这两方面。 首先说运行速度,或者说是, 1.执行速度 在这方面运行速度快慢为:StringBuilder(线程不安全,可变) > StringBuffer...

时刻在奔跑 ⋅ 今天 ⋅ 0

java以太坊开发 - web3j使用钱包进行转账

首先载入钱包,然后利用账户凭证操作受控交易Transfer进行转账: Web3j web3 = Web3j.build(new HttpService()); // defaults to http://localhost:8545/Credentials credentials = Wallet......

以太坊教程 ⋅ 今天 ⋅ 0

Oracle全文检索配置与实践

Oracle全文检索配置与实践

微小宝 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部