文档章节

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

abcijkxyz
 abcijkxyz
发布于 2016/11/22 16:40
字数 2921
阅读 6
收藏 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
粉丝 63
博文 6196
码字总数 1876
作品 0
深圳
项目经理
SSE图像算法优化系列二十:一种快速简单而又有效的低照度图像恢复算法。

 又有很久没有动笔了,主要是最近没研究什么东西,而且现在主流的趋势都是研究深度学习去了,但自己没这方面的需求,同时也就很少有动力再去看传统算法,今天一个人在加,还是抽空分享一个简...

Imageshop
08/11
0
0
高斯模糊算法的 C++ 实现

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

hoodlum1980
2015/05/25
0
0
28个不得不看的经典编程算法

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

xjhznick
2014/11/06
0
0
数据结构基本概念 - 学习笔记

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

wqli
2012/09/22
0
0
【万能搜索】万能DFS之全排列(一)——普通算法

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

qq_37656398
2017/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

活动推荐|互联网3.0与区块链新时代论坛(北京)

1 时间地点 **时间:**9月22日 14:00 - 18:00 地点:(北京海淀)西大街70号 3w咖啡 二层 2 活动详情 Harmony创始人Stephen及团队将介绍他们的区块链分片扩容技术。Stephen曾任Apple地图服务...

HiBlock
42分钟前
1
0
如何优雅的删除Redis的大key

关于Redis大键(Key),我们从[空间复杂性]和访问它的[时间复杂度]两个方面来定义大键。前者主要表示Redis键的占用内存大小;后者表示Redis集合数据类型(set/hash/list/sorted set)键,所含有的...

IT--小哥
52分钟前
1
0
spring cloud学习笔记

工具 eclipse 4.9 gradle 4.10.2 spring cloud Finchley.SR1 spring boot 2.0.4 build.gradle buildscript {ext {springBootVersion = '2.0.4.RELEASE'}repositories {jcenter()......

bobby2006
54分钟前
1
0
Tcl命令操作实验-----(5)

Vivado% proc myproc {arg} {puts $arg}Vivado% myproc mynamemynameVivado% if {2>1} {puts 2>1} else {puts 2<1}2>1...

whoisliang
今天
1
0
比特币钱包RPC的PHP调用方法

当我们希望在Php开发的网站中加入比特币支付功能时,需要解决的第一个 问题,就是如何在Php程序代码中调用比特币钱包的RPC API开发接口来实现 我们期望的功能,例如比特币的支付与接收。 例如...

汇智网教程
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部