基于均值漂移的暗原色先验图像去雾算法

陆海俊, 汪荣贵, 杨 娟, 薛丽霞, 王 晶

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)



基于均值漂移的暗原色先验图像去雾算法

陆海俊, 汪荣贵, 杨 娟, 薛丽霞, 王 晶

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)

暗原色先验去雾算法在单幅图像去雾方面效果明显,但该算法复杂度高、处理耗时长,针对该算法不足之处,文章对均值漂移算法进行适当改进后,将其引入暗原色先验去雾算法之中,并结合数学形态学的思想,提出一种新的高精度透射率快速计算技术和相应的去雾算法。通过改进的算法,有效解决了块状效应和光晕现象的问题。选取一系列雾天图像进行实验,分别采用主观观察评价和客观数据分析方法,结果表明文中所提出算法快速有效,并较好地恢复了图像细节,减少了色彩失真,同时改进算法处理效果与原算法基本一致,算法效率得到显著提高。

图像去雾;暗原色先验;透射率估计;均值漂移;图像质量;形态学

随着“平安城市”、“智慧城市”的建设,视频系统越来越多地应用在日常生活中，相机在雨雾天气下的成像影响着整个系统的工作，因此利用有效且快速的去雾方法使雾天图像清晰化具有十分重要的意义。

目前雾天图像清晰化方法可分为图像增强和图像复原。雾天图像增强方法不考虑图像质量下降的本质原因,直接通过提高图像的对比度,提高视觉效果,如直方图均衡化[1]、Retinex算法[2-4]等。但是图像信息的损失与目标和相机的距离成指数关系,因为图像增强方法无法对景深跨度大的图像产生很好的效果。图像复原是研究图像质量损失的过程,建立损失模型并对其进行逆向,补偿其损失的内容,从而获得无雾图像。图像复原法与图像增强法相比更具有针对性,处理后的图像更加自然,但处理的关键点在于图像损失模型中参数的设定。

近年来,国内外研究者趋向于从分析恶劣天气条件下,图像降质原因的角度来解决降质图像的清晰化问题，对雾天降质图像形成机理进行深入探讨,挖掘图像降质的具体原因,利用先验知识建立图像降质的物理模型,进行图像复原。在计算机视觉系统中,常用大气散射模型来描述雾霾天气下场景的成像过程,由于该模型包含了3个未知参数,从本质上讲,其求解过程是一病态问题。针对该问题,相关研究提出的图像去雾算法几乎都是基于先验知识或假设条件来构造用于求解场景反射光线强度的约束条件,该类方法的关键问题是获取场景的深度信息。

文献[5-7]提出利用不同天气情况下的2幅或多幅图像求解场景深度的方法,该方法在一些情况下(如实时监控系统), 由于无法提供多幅场景的差异图像而难以应用。文献[8]又提出一种基于深度估计的交互式去雾方法,此方法需要依赖人工干预来获得图像深度信息,不易应用。文献[9]通过假设透射率和表面投影局部不相关,利用独立成分分析估算景物透射率,再利用模型求解清晰图像,此方法建立在过强的假设理论条件下,而且对浓雾图像处理时效果不理想。文献[10]提出大气耗散函数在局部变化平缓同时在可行域中逼近最大值的思想,在此思想上提出了一种快速图像去雾算法,该算法以改进的中值滤波估计大气耗散函数,但是由于中值滤波存在丢失边缘的特性,极易导致光晕效应;此外,由于算法存在过多的参数,不易应用。

针对损失模型参数,文献[11]提出了基于暗原色先验去雾方法(下文简称“He算法”)。He算法基于大量图像统计后得出规律认为,在无雾图像的局部区域中RGB 3个颜色通道中至少有1个通道的数值接近0,通过此先验知识对大气投射率进行估算,再结合软抠图去除图像处理中引起的光晕和块状效应。此算法可以得出很好的去雾效果,但是由于软抠图太过复杂,占用大量内存和时间而难以应用。针对此问题出现了一些改进算法,例如:文献[12]在YCbCr空间中Y分量上应用Retinex理论得到与He算法类似的透射图,但这是一种巧合而不具备理论支持,只是针对一些特定的图片取得了较好的效果,缺乏通用性;文献[13]使用双边滤波来代替软抠图算法,但是双边滤波具有梯度反转的局限性,导致边缘特征被弱化。

上述研究几乎均存在计算复杂、耗时长等问题,并且在参数假设不恰当的情况下存在光晕现象。针对该类问题,本文对传统的均值漂移算法进行改进,将其应用到透射率的快速求精,并结合数学形态学的思想,提出一种新的暗原色先验快速除雾算法。算法结合大气散射模型的构造和求解过程,通过引入形态学思想对雾天图像进行处理来获得较高精度的雾天透射图,并通过改进的均值漂移方法消除透射图计算中出现的块状效应和光晕现象[14],可以对透射图快速有效地求精,解决了高精度透射率的快速计算难题,与文献[12-13]的算法相比,运行速度明显提高,且能够有效地消除光晕现象,在处理效果上取得了较好的效果。

1 暗原色先验去雾模型

相机在雨雾环境下成像时,由于空气中悬浮的各种微粒对光的折射或漫射使相机的成像质量下降,可见距离大大缩短,严重影响了相机的正常工作。大气的散射模型[15]的表达式为:

(1)

其中,J为原始图像,即为无雾图像;t(x)为大气投射率;A为环境光;I为当前图像,即为需要处理的图像。其中t(x)与A为此模型中要求的参数。

在He算法的暗原色模型的先验思想中,在无雾的环境中,图像的区域RGB 3个颜色通道中至少有1个通道的数值接近0。其方程为:

(2)

其中,Jc为图像J的3种通道中某一通道;Ω(x)为图像中以像素x为几何中心的一块区域; Jdark为暗原色,是2个最小化滤波操作的结果。

假设暗原色先验规律正确,最小通道亮度为0,则对(1)式进行2次求最小可得:

(3)

由(3)式可得到初步的t(x),但是通过实验发现,即使在无雾环境下,由于大气闪烁的原因,视场的远处依旧有层雾蒙蒙的现象,所以在(3)式中,引入一个常量ω,以保留少量的雾信息,使图像看起来真实,ω通常取0.95。

(4)

对于大气光A的估值,本文选择暗原色图像中亮度较高的像素,这些像素的数量占总像素的0.1%,这些像素对应的有雾图像I中最高的亮度值被定为大气光A的取值。同时为了防止当t(x)为0时,处理后的图像出现噪声,对t(x)限定一个下限t0。最后处理后的图像为:

(5)

2 均值漂移算法

均值漂移(mean shift)[16]这个概念最早是由Fukunaga等人于1975年提出的,其最初的含义就是偏移的均值向量。但随着mean shift理论的发展,如今mean shift算法一般是指一个迭代的步骤,以1点为例:先算出该点的偏移均值量,将该点按其偏移均值移动到一个新的点,再以此为起始点,继续计算移动,直到满足设定的结束条件为止,停止移动。

假定d维空间Rd中总体X的n个样本点 xi,i=1,…,n,在x点的均值漂移向量定义为:

(6)

其中,Sh为一个半径为h的高维球区域;k为落入Sh区域中的样本点数。(6)式中均值漂移向量Mh(x)为对偏移向量求和再平均。

若样本点是从一个概率密度函数中采样得到的,当概率不为0时,其概率密度梯度方向指向为最大增加方向,所以Sh区域内的样本点更多沿着概率密度梯度的方向上分布,因此得到的均值漂移向量也指向概率密度梯度的方向。

文献[17]对基本的mean shift算法在以下2个方面做了推广:① 定义了1族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同;② 设定了1个权重系数,使得不同的样本点重要性不一样。推广后的形式为:

(7)

其中,w(xi)为赋给每个采样点xi的权重;G为单位核函数；均值漂移向量Mh(x)为采样点的加权平均。

空间中一个点x若用1个列向量表示,x的模为‖x‖2=xTx。R表示实数域。定义核函数K:Rd→R,存在一个剖面函数k:[0,∞]→R,即

(8)

概率密度函数f(x)的核函数密度估计为:

(9)

f(x)的梯度估计为:

(10)

定义g(x)=-k′(x),G(x)=g(‖x‖2),(10)式可重写为：

(11)

(11)式第2个等号后的第2个括号内的部分就是(7)式定义的均值漂移向量。

文献[18-19]将mean shift算法成功地运用在特征空间的分析中,证明了mean shift算法在满足一定条件下,一定可以收敛到最近的一个概率密度函数的稳态点,因此mean shift算法可以用来检测概率密度函数中存在的模态。

3 基于改进算法的暗原色先验

3.1 透射图的形态学优化

对灰度图像的形态学处理就是将运算对象由集合换成函数图像。 由于暗原色先验的处理结果在其边缘的区域相对原图要宽,容易形成边缘效应,因此需要对其进一步处理。

腐蚀是一种消除独立点及将区域边界往内缩小的算法。由于透射图是灰度图像,其腐蚀的过程就是一次取大的过程,即

(12)

其中,t(y)为原始透射图;Ω(x)为图像中以像素x为几何中心的一块区域。

Ω(x)的大小直接影响腐蚀的边缘大小是否符合原色图像,根据腐蚀算法原理以及实验得出,这里腐蚀区域的大小取投射图像模版尺寸的1/2。

3.2 透射率的快速求精

形态学处理只能缩小边缘效应的区域,但无法解决光晕问题。本文对透射图进一步求精。

由于透射图是灰度图像,所以只需考虑图像的位置和亮度信息,可以用Y=(Sx,Sy,B)三维向量表示。其中，Sx、Sy为图像的坐标；B为图像亮度信息。

基于坐标和亮度信息之间的相互独立性以及运算的合理性,本文把核函数分解为K(S)和K(B) 2个独立的核函数的积,即

(13)

其中,K(S)为位置信息核函数;K(B)为亮度信息核函数。

为了适应人类眼睛的特性,获得好的视觉感,核函数选用高斯核函数,即

(14)

将(7)式的x提到求和号的外面,可得到(15)式:

(15)

提取(15)式中等号右边第1项得到均值漂移算法的迭代公式如下:

(16)

迭代算法结束的条件是小于容许误差ε,ε控制着均值漂移的程度。给定核函数K(x)和容许误差ε,对透射图中每个像素点i做如下运算:

(1) 选择带宽为h的初始搜索区域Sh。h为空间范围带宽hs和亮度范围带宽hr的总称。

(2) 求出mh(i)。

(3) 计算Mh(i)。

(4) 如果‖Mh(i)‖<ε,迭代算法结束,否则将mh(i)赋给i,执行步骤(2)。

按上述步骤运算后发现,经过上述方式处理后会减弱投射图原始边缘强度,这是由于均值漂移的局限引起的。为了克服此问题,本文对均值漂移进行改进,通过引入一个边缘权重图E(x),对边缘进行加权处理。E(x)为当前点边缘强度与整幅图片边缘强度均值的一个比值。则改进的迭代公式为:

(17)

均值偏移量得到的点的密度大于x处的密度,因此均值漂移向量总是指向密度梯度增加的方向,均值漂移收敛点为局部密度极大值点。此外，通过引入边缘权重图提高了均值漂移方法的边缘保留能力。

透射效果图如图1所示。

图1 透射效果图

4 结果与分析

本文实验平台为CPU双核2.60 GHz,内存4 G,软件为Matlab R2009a,Windows 7操作系统。为了验证算法的效果,取多组户外雾天图像进行处理,并与带色彩恢复的多尺度视网膜增强(multi-scale retinex with color restoration,MSRCR)算法、He算法比较,通过主观观察和客观分析验证本文算法的优越性。

4.1 主观评价

roof(第1行)、building(第2行)以及lotus(第3行)的实验结果如图2所示。

图2表明MSRCR算法有一定的去雾效果,提升了图像的可识别性,但是依旧有很大的局限性,例如roof 上部出现色斑、building效果亮度不够、lotus出现颜色失真等情况;He算法在lotus上出现过爆的现象；本文算法结果克服了上述缺点,主观观察上优于前2种算法。

图2 去雾结果主观对比效果图

4.2 客观对比

4.2.1 时间复杂度

算法的时间复杂度表示执行算法所需的计算工作量,能反映出一个算法的优劣。时间复杂度越低,意味着算法的执行效率越高。

设一幅图像的大小为Sx×Sy,He算法所用的SoftMatting算法是一个大规模稀疏线性方程组求解的过程,具有很高的时间复杂度和空间复杂度,其时间复杂度为O(9M2m2),其中M为拉普拉斯矩阵的大小,M=Sx×Sy,m为计算拉普拉斯矩阵中像素值的模板大小。该算法的时间复杂度非常高,执行效率极低。

4.2.2 客观评价估计标准

大部分对于雾天降质图像复原的质量评价体系中,都需要一幅无雾图像作为参考,但实际应用中很难满足这一要求。本文为了更加准确地表现出算法的效果,将处理时间、熵、平均梯度、边缘强度作为客观的评价标准。

tree(第1行)、Tiananmen(第2行)以及people(第3行)的实验结果如图3所示。3种场景客观评价对比结果见表1～表3所列。

图3 客观对比效果图

项 目t/s熵平均梯度边缘强度原图2.0324.85647.461MSRCR算法0.5102.18910.449102.813He算法12.0342.24814.459141.063本文算法4.9272.25114.522142.575

表2 Tiananmen图对比结果

表3 people图对比结果

从表1～表3可以看出,本文算法在时间上不如MSRCR算法快速,但与He算法相比用时更少;在熵、平均梯度、边缘强度3个方面,本文算法都优于MSRCR算法,甚至优于He算法。

5 结 论

本文对传统的均值漂移算法进行改进,将其应用到透射率的快速求精,并结合数学形态学的思想,提出一种新的暗原色先验快速除雾算法,有效地解决了快速高效去雾的难题。多组实验结果表明了本文算法能够有效地去除图像中的雾霭,再现了场景的对比度和颜色,消除了光晕现象,提高了图像质量。此外,通过实验发现,本文算法虽然整体性能高于其他算法,但是要达到实时去雾的程度还需要进一步研究改善的方法。

[1] 罗颖昕.雾天低对比度图像增强方法的研究[D].天津:天津大学,2005.

[2] 陈雾.基于Retinex理论的图像增强算法研究[D].南京:南京理工大学,2006.

[3] 汪荣贵,朱静,杨万挺,等.基于照度分割的局部多尺度Retinex算法[J].电子学报,2010,38(5):1181-1186.

[4] 汪荣贵,张璇,张新龙,等.一种新型自适应Retinex图像增强方法研究[J].电子学报,2010,38(12):2933-2936.

[5] NARASIMHAN S G,NAYAR S K.Contrast restoration of weather degraded images[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(6):713-724.

[6] NAYAR S K,NARASIMHAN S G.Vision in bad weather[C]//IEEE International Conference on Computer Vision,Vol 2.[S.l.]:IEEE Computer Society,1999:820-827.

[7] SCHECHNER Y Y,NARASIMHAN S G,NAYAR S K.Polarization-based vision through haze[J].Applied Optics,2003,42(3):511-525.

[8] NARASIMHAN S G,NAYAR S K.Interactive (de) weathering of an image using physical models[C]//IEEE Workshop on Color and Photometric Methods in Computer Vision:in Conjunction with ICCV’03.[S.l.:s.n.],2003:1387-1394.

[9] FATTAL R.Single image dehazing[J].ACM Transactions on Graphics,2008,27(3):1-9.

[10] TAREL J P,HAUTIERE N.Fast visibility restoration from a single color or gray level image[C]//Proceedings of the 12th IEEE International Conference on Computer Vision.[S.l.]:IEEE, 2009:2201-2208.

[11] HE Kaiming,SUN Jian,TANG Xiaoou.Single image haze removal using dark channel prior[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. [S.l.]:IEEE, 2009: 1956-1963.

[12] XIE Bin,GUO Fan,CAI Zixing.Improved single image dehazing using dark channel prior and multi-scale retinex[C]//Proceedings of the 2010 International Conference on Intelligent System Design and Engineering Application,Vol 1.[S.l.]:IEEE Computer Society,2010:848-851.

[13] XU Haoran,GUO Jianming,LIU Qing,et al.Fast image dehazing using improved dark channel prior[C]//2012 International Conference on Information Science and Technology (ICIST).[S.l.]:IEEE, 2012:663-667.

[14] 许欣,陈强,王平安,等.消除光晕现象的快速Retinex图像增强[J].计算机辅助设计与图形学学报,2008, 20(10):1325-1331.

[15] MIDDLETON W E K.Vision through the atmosphere[M]//Geophysics Ⅱ.Berlin:Springer, 2009:254-287.

[16] FUKUNAGA K,HOSTETLER L D.The estimation of the gradient of a density function,with applications in pattern recognition[J].IEEE Transactions on Information Theory,1975,21(1):32-40.

[17] CHENG Yizong.Mean shift,mode seeking,and clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence,1995,17(8):790-799.

[18] COMANICIU D,MEER P.Mean shift analysis and applications[C]//Proceedings of the Seventh IEEE International Conference on Computer Vision,Vol 2.[S.l.]: IEEE Computer Society,1999:1197-1203.

[19] COMANICIU D,MEER P.Mean shift:a robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.

(责任编辑 张淑艳)

An image haze removal algorithm using dark channel prior based on mean shift

LU Haijun, WANG Ronggui, YANG Juan, XUE Lixia, WANG Jing

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

The image haze removal algorithm based on the dark channel prior has achieved a good result in removing the haze from foggy images, but it has high computational complexity of transmission and is time consuming. In this paper, the mean shift algorithm is improved properly and introduced into the image haze removal algorithm using the dark channel prior based on the ideas of mathematical morphology. Then a new kind of high precision transmission estimation algorithm is put forward. The block effect and halo effect can be eliminated effectively by using this method. A series of foggy images are tested, and by using the methods of subjective observation and objective data evaluation respectively, the proposed algorithm is proved to be quick and effective, and is better in restoring image details and reducing the color distortion at the same time. The proposed algorithm has almost the same processing effect as the original algorithm and higher efficiency.

image haze removal; dark channel prior; transmission estimation; mean shift; image quality; morphology

2015-06-08；

2015-09-29

国家自然科学基金资助项目(61075032); 中央高校基本科研业务费专项资金资助项目(2012HGCX0001)和合肥工业大学博士学位人员专项基金资助项目(JZ2014HGBZ0059)

陆海俊(1990-),男,安徽滁州人,合肥工业大学硕士生;

汪荣贵(1966-),男,安徽池州人,博士,合肥工业大学教授,博士生导师.

10.3969/j.issn.1003-5060.2016.09.011

TP391.411

A

1003-5060(2016)09-1205-06