Single Image Fog Removal Based on Local Extrema

Hongyu Zhao,Chuangbai Xiao,Jing Yu,and Xiujie Xu

Single Image Fog Removal Based on Local Extrema

Hongyu Zhao,Chuangbai Xiao,Jing Yu,and Xiujie Xu

—Atmospheric conditions induced by suspended particles,such as fog and haze,severely alter the scene appearance. In this paper,we propose a novel defogging method based on the local extrema,aiming at improving the image visibility under foggy or hazy weather condition.The proposed method utilizes atmospheric scattering model to realize the fog removal. It applies the local extrema method to fi gure out three pyramid levels to estimate atmospheric veil,and manipulates the tone and contrast of details at different scales through multi-scale tone manipulation algorithm.The results on the experiments of comparison with traditional methods demonstrate that the proposed method can achieve more accurate restoration for the color and details,resulting in a great improvement in image visibility.

Index Terms—Defog,local extrema,atmospheric scattering model,haze removal.

I.INTRODUCTION

POOR visibility becomes a major problem for most outdoor vision applications.Bad weather,such as fog and haze,can signi fi cantly degrade the visibility of a scene.The low visibility inevitably handicaps visual recognition and comprehension.The goal of defogging methods is to remove the effects of fog and recover details and colors of scene from foggy image.

Most traditional image enhancement methods,such as histogram equalization,Retinex,the wavelet transform,usually cannot obtain ideal defogging result.These methods mainly focus on enhancing low brightness and low contrast features in digital images,and they are simple,ef fi cient,and can be applied to most real-time scenes.However,they do not consider the reason why the image is degraded by fog and cannot compensate effectively.Therefore,these methods are limited to perform the defogging task and even may introduce halo artifacts or distort the color.

Alternatively,another method,which improves image color and contrast through understanding the physical model of image degradation[1],has become a research hotspot that has been widely researched in computer vision and image processing.The atmospheric scattering model is usually used to describe the formation of a foggy or hazy image.These methods based on this physical model are reliable,highly targeted and can produce better quality defogging results. Some of these methods require multiple images of the same scene,taken under different atmospheric conditions[2-3]or combined with near-infrared version.In practice,unfortunately it is usually dif fi cult to satisfy such special conditions,so these methods are restricted if there is not enough additional information to be used.

Recently,several fog removal methods based on single image have made signi fi cant progress.Tan′s work[4]is based on the assumption that the clear-day images have higher contrast compared with the input fog image,which removes the haze by maximizing the local contrast of the restored image.This method generates compelling images with enhanced contrast, but it may also result in a physically-invalid excessive haze removal.Fattal[5]assumes that image albedo is a constant vector in local region and that the transmission is locally statistically uncorrelated.Fattal’s approach can produce impressive results, but it cannot well handle heavy haze images and may fail when the assumption is not satis fi ed.He et al.[6]propose dark channel prior to estimation of the transmission map and use soft matting to re fi ne it.The results are visually compelling, but both the time and space complexity of this method can be quite high.They further improve their method by estimating the transmission map using guided fi lter[7].Tarel et al.[8]use the median fi ltering method to estimate atmospheric veil.This method performs faster than the previous approaches,but its detail restoration is not ideal.Yu et al.[9]use the bilateral fi lter to estimate the atmospheric veil,improving the defogging performance to some cases.An approach based on factorial MRF is proposed in[10]to handle the two types of fi elds of unknown variables:scene albedo and depth,which has high complexity.Based on planar road constraint,[11]introduces another ef fi cient MRF approach to improve the restoration of the road area,assuming an approximately fl at road.

In this paper,we introduce a novel method based on local extrema to remove fog from a single image.We use local extrema method[12]to estimate the atmospheric veil and adopt multi-scale tone manipulation algorithm to regulate the expression of details.Through the fusion of multi-scale information, we can create more visual effects on the restored image.The proposed method is physically valid and can signi fi cantlyincrease the visibility of the scene.

The article is structured as follows.Section II describes the atmospheric scattering model and atmospheric veil.In Section III,we present a detailed description of the proposed method. In Section IV,a comparison is provided with current defogging methods to illustrate the advantage of the proposed method. Finally,concluding remarks are made in Section V.

II.BACKGROUND

The attenuation of luminance through the atmosphere was studied by Nayar and Narasimhan[1],who derived a foggy image degradation model called atmospheric scattering model. This model relates the apparent luminanceI(x,y)of an object located at distanced(x,y)to the luminanceR(x,y)measured close to this object:

whered(x,y)is the distance of the object at pixel(x,y),Ais called skylight and represents the luminance of the sky,βis the scattering coef fi cient of the atmosphere,I(x,y)is the intensity of image degraded by fog.R(x,y)is the intensity of clear image without fog.The removal of the fog is actually to solveR(x,y).The atmospheric scattering model assumes that the atmosphere is homogeneous and does not consider wavelength’s in fl uence on atmospheric scattering coef fi cient, soβis considered to be a constant.The dif fi culty is that single image defogging is an ill-posed problem.Indeed,from(1), defogging requires to estimateA,βanddat every pixel,only knowing the input imageI.

In the atmospheric scattering model,the calculation of scene depth and atmospheric scattering coef fi cient generally requires additional information such as the vanishing points from the in fi nite plane.The location con fi rmation of vanishing points relies on the subjective judgment or is realized through the image processing algorithm(e.g.,Hough transform,Curvelet transform).In many cases,vanishing points are dif fi cult to be accurately estimated,which may cause the bad image visibility restoration.As a consequence,we introduce the atmospheric veil to avoid solvingdandβ,which can be expressed by

whereVis de fi ned as the atmospheric veil,tis the transmission map which can be expressed ast(x,y)=e-βd(x,y).Vdenotes the effect of ambient light[1],tre fl ects the ability of light penetration.They both contain the depth information. Estimating the transmission map and atmospheric veil are two main kinds of defogging method based on the physical model. The estimation oftneeds to rely on solution of skylight and a constant parameter setting[6],however,estimation ofVcan avoid being directly in fl uenced by other parameters and can be executed quickly and accurately.Through the subsequent parameter adjustment,estimating atmospheric veil method can achieve good image restoration result.

III.DEFOGGING METHOD

In this paper,we introduce a novel defogging technique based on local extrema method to remove fog or haze from a single image.Our method can be decomposed into three steps:estimating the skylight and correcting color through white balance;estimating the atmospheric veil based on local extrema method and recovering the image visibility by inverting atmospheric scattering model;Controlling the visibility by multi-scale tone manipulation algorithm.

A.Skylight Estimation and White Balance

SkylightAis typically assumed to be a global constant. We estimateAthrough the method based on the dark channel prior[6].The dark channel of input image can be de fi ned as

whereIc(x,y)is a color channel ofI(x,y)andψis a local patch.In order to solveA,we choose the 0.1%brightest pixels of the dark channel as their preferred region and de fi ne these pixels asI0.1%.Then,the average value ofI0.1%in the input foggy image is selected as the initial skylight,i.e.,Amean=mean(I0.1%)

The color of foggy image sometimes suffers from illumination variations.For example,the foggy day is often accompanied by cloudy weather which causes the scene to be prone to partial color.Therefore,to improve the skylight estimation,we will correct fog to to be pure white.The calculation can be performed as

whereAis the ideal skylight estimation result.Equation(4) means settingAmeanto be(1,1,1).Then,we can obtain the corrected imageI′after white balance,which can be inferred as

B.Coarse Estimation of Atmospheric Veil

From(1)and(2),we can fi nd the atmospheric veil estimation becomes the key step to calculate the restored imageR. Due to its physical properties,the atmospheric veil is subject to two constraints:i)0≤V(x,y)≤1,and ii)V(x,y)is not higher than the minimal component ofI′(x,y).We thus take the min operation among three color channels and acquire a rough estimation of the atmospheric veil:

whereis the coarse estimation matrix of atmospheric veil. For the gray image,it is expressed as(x,y)=I′(x,y).Atmospheric veil coarse estimation is equivalent to the minimum fi ltering,but a single minimum fi ltering usually causes obvious halo or block artifacts.In order to obtain more accurate result, we need reasonable constraint manipulation to further re fi ne.

C.Image Restoration by Local Extrema

Atmospheric veil depends solely on the depth of the objects and has nothing to do with scene albedo[10].The scene depth is changing smoothly across small neighboring areas except at the edges.Therefore,the re fi nement of atmospheric veil can be considered a smoothing problem.In this paper,in order to generate an ideal estimation of the atmospheric veil,we apply an edge-preserving smoothing approach based on the local extrema for re fi nement.

Our method based local extrema is inspired from Subr[12]’s technique,which uses edge-aware interpolation to compute envelopes.A smoothed mean layer is obtained by averaging the envelopes.The method can extract fi ne-scale detail regardless of contrast[13].However,single mean layer is not suf fi cient to well approximate atmospheric veil,and it is solved by iterative calculation,which is time-consuming.

Our non-iterative method consists of three steps:1)identi fi cation of local extrema of;2)inference of extremal envelopes;3)visibility enhancement of the result by multiscale tone manipulation algorithm.

First,we locate the extrema in.Pixelpis considered as a maxima if at mostk-1 elements in thek×kneighborhood aroundpare greater than the value at pixelp.In the same way we can locate the minima.Image details whose extrema are detected by using ak×kkernel have wavelengths of at leastk/2 pixels.We choosek=5 as the size of the extremalocation kernel in this paper.

As for the next step,we will employ the interpolation of the local minima and maxima to compute minimal and maximal extremal envelopes respectively.LetSbe the pixel set of local extrema,we compute an extremal envelopeEusing an interpolation technique proposed by Levin et al.[12,14]for image colorization.It assumes that theEis a linear function of the,and seeks an interpolantEsuch that neighboring pixelsE(r)andE(s)have similar values if(r)and(s)are similar.The calculation of extremal envelope is to minimize the energy function:

which subject to the constraint

Equation(7)is designed to minimize the distance between theE(r)at pixelrand the weighted average of theE(s)at neighboring pixelsN(r).N(r)denotes the neighbors ofr, and weights

are computed using the local varianceof the intensities aroundr.wrsis a weighting function so that the functions for all sum to one.The extremal envelope calculation needs to solve a large,sparse system of linear equations.We adopt the approach of[14]and minimize the quadratic functional using their weighted least squares formulation,which can achieve even more signi fi cant speedups.If the number of pixels of an input image isN,the computational time of single envelope can reach O(N).

After obtaining the minimal envelope,maximal envelope and the mean layer computed by these two envelopes,we can obtain the three-scale atmospheric veilVi,i=1,2,3. After calculating the skylightAthrough Section III-A,we can directly recover the scene information in the ideal weather conditions:

where the parameterq(0＜q＜1)is simply fi xed to 0.95, which is used for regulating the degree of defogging.This means that 95%of the amount of atmospheric veil is removed. In practice,remaining a small amount of mist can make image layer clearer.

By observation and experimentation,we fi nd that not all the processes of three scales are suitable to re fi ne atmospheric veil. From Fig.1,we can see that all the smoothing operations of three scales are effective in preserving high-gradient edges,so the smoothed results will contain few halo artifacts along depth discontinuities.The difference is that the detail-preserving, the maximal envelope can extract detail more accurately in bright regions than in dark regions;the minimal envelope can effectively smooth detail even with large amplitude variation. Especially,it can preserve the signi fi cant edges in dark regions better than the other two scales;the mean layer has the compromise effect between the other two envelopes,it can strictly preserves edges without blurring detail.Atmospheric veil is locally smooth except at edges,which has higher intensity in regions with denser haze.Therefore,minimal envelope is most suitable for atmospheric veil re fi nement;the maximal envelope and mean layer can be used to highlight the detail in the input image.

With three-scale restored results,we adopt the multi-scale tone manipulation algorithm of Farbman et al.[15]to improve the visual effect.According to the above analysis,we will manipulate tone and contrast of details at three scales,which include including restored imagesR1,R2,R3obtained from minimal envelope,maximal envelope,mean layer,respectively. We fi rst construct a three-level decomposition of the CIELAB lightness channel,which includes coarse base levelbfromR1, two detail levelsd1andd2(d1=R1-R2,d2=R2-R3). The result of the manipulationRat each pixelpis then given by

whereµis the mean of the lightness range,and functionCis used to control the exposure and contrast of three-level details. It is a sigmoid curve,i.e.,C(a,u)=1/(1+exp(-au)). The goal of this sigmoid is to avoid the hard clipping thatwould otherwise occur when the detail layers are signi fi cantly boosted.ηis the exposure parameter,δ0,δ1andδ2are boosting factors.The solution procedure of(11)is non-iterative and can be performed in real time.

Fig.1.Image smoothing effect in three scales.(a)The input image signal(b)The smoothed results by the minimal envelope(dash line), maximal envelope(dot-dash line)and the mean layer(continuous curve)computed by these two envelopes.

Fig.2 is a tone adjustment example,which is obtained with the parametersδ0=δ1=δ2=1,µ=1.As we can see, using the multi-scale tone manipulation algorithm,our method can correct brightness and enhance image details effectively. Through further experiments we fi nd that three levels are suf fi cient for detail display.Using more scales will enable fi ner control,but will consume more time.

IV.COMPARISON EXPERIMENTS

In order to verify the effectiveness of the defogging method, we will evaluate the proposed method on the real scene and the virtual scene.The experiments will be conducted on the matlab platform and mainly deal with low resolution images for better detail comparison.Firstly,in the aspect of restoring real world foggy images,our method will compare with two classical methods:Tarel′s noblack-pixel constraint(NBPC)[8]and He′s method based on guided fi lter[7].Tarel et al.introduced a complete inference of atmospheric veil in[8].He et al fi rst proposed dark channel prior to initialize transmission estimation in[6].However,the matting Laplacian regularization might lead to an overall reduction of contrast at the distant regions and had high time and space complexity.Reference [7]was their improved method free from these problems. Both methods are known for their robustness and can produce visually pleasing restored results.The time consumption of [7-8]is mainly associated with the estimation of transmission map or atmospheric veil.Both of their calculations can reach O(N).From top to bottom,the dimensions of images provided in Fig.3 are 315×315,460×380,600×400 and 600×450, and the four groups of experimental images are expressed as Fig.3(a)～(d).

Fig.2.Tone adjustment.(a)is the input foggy image,(b)-(d)are the three-scale defogging results,(e)is our result.

Fig.3.Fog removal results of real world image.From left to right:the input foggy images,Tarel′s results,He′s results,and our results.

As seen from Fig.3,three methods have strong defogging ability.Some objects which were barely visible in foggy image appear clearly in enhanced images.However,Tarel′s results have lower contrast and prone to be saturated;He′s method has a good ability of fog removal,but its detail enhancement ability is limited.Compared with the two methods,our method can better restore image and achieve much greater color consistency.Experimental results also show that proposed method has a obvious superiority in preserving detail and can avoid the halo effect.

In order to objectively assess these methods,we use the assessment method dedicated for visibility restoration proposed in[16].This method computes two indicatorse,¯rto assess the performances of a contrast restoration method through comparing two gray level images:the input image and the restored image.The value ofeevaluates the ability of the method to restore edges which were not visible in the input image but are in the restored image.The value of¯rexpresses the average visibility effect enhanced by the restoration method.

Furthermore,a good image restoration method should also make the restored image look natural and real,therefore, color retention degree is an important index for evaluating the defogging methods,which is denoted ash.We evaluate the color retention ability by histogram comparison.The more similar the histogram shapes,the stronger color retention ability is.We use the color histogram intersection method to calculate the histogram similarity between original image and the restored image,which is expressed as a percentage.

We use the edge preserved index(EPI)sto measure the edge-preserving ability,which is obtained by calculating the ratio value of gradient-sum of pixels in the original image and restored image.

These indicatorse,¯r,handsare evaluated for the com-parison experiments on four images of Fig.3,see Tables I-IV.

TABLE I COMPARISON OF THEeVALUES

TABLE II COMPARISON OF THE¯rVALUES

TABLE III _COMPARISON OF THEhVALUES

TABLE IV COMPARISON OF THEsVALUES

As can be observed from Tables I and II,our method is able to achieve fog removal while restoring more visible edges. Table III that the histogram results of restored images obtained by our method are very close to the histogram results of the original images,which means our method can accurately retains the color of the objects.From Table IV we can deduce that our method can preserve edge characteristics effectively. In conclusion,our method clearly outperforms other methods. The color is more homogeneous and small details are better restored.

In the next experiments,we employ the database named FRIDA2[17]for the evaluation of the proposed method under the ideal condition.FRIDA2 is available for research purpose and in particular to allow other researchers to rate their own visibility enhancement methods.This database provides 66 images of the same virtual scene with and without fog.The proposed method will be compared with 5 other methods[17]: multi-scale retinex(MSR),adaptive histogram equalization (CLAHE),free space segmentation(FSS),noblack-pixel constraint(NBPC)[8]and dark channel prior(DCP)[6].

To quantitatively assess those methods,we use the method of computing the average absolute errorEavgbetween the image without fog and the enhanced image.Table V shows the comparative results of 6 defogging methods using 66 virtual images with uniform fog.The subjective comparison results of one typical example are presented in Fig.4.Table 5 shows that our result is the second closest to the clear day image only inferior to FSS.From the subjective observation in Fig.4,we fi nd that MSR and CLAHE are not suitable for foggy images, that vertical objects appears too dark with FSS,far away objects are more foggy with DCP or NBPC.By comparison, the details in our result appear much cleaner,and the visibility of distant objects is also improved obviously.Experimental results also demonstrate that our method can maintain the dominant color styles of the original image in the restored image.

Fig.4.Fog removal results of virtual image.

Fig.5.Comparison with Caraffa′s work.From left to right:the input foggy images,Caraffa′s results,and our results.

Fig.6.Comparison with Li′s work.From left to right:the input foggy images,Li′s results,and our results.

TABLE V COMPARISON OF THEEavgVALUES

Finally,we will show a comparison of our proposed method with two state-of-art methods by Caraffa[11]and Li[18].As shown in Fig.5,Caraffa′s method can remove fog robustly and the restored results show higher contrast in remote areas. However,many latent image details in Caraffa′s results are lost.From Fig.6,we can see that Li’s method can improve the visibility and achieve more natural recovery.Compared with the two methods,our method can signi fi cantly improve image contrast and clarity.Its main advantage is the more accurate and effective detail restoration.

V.DISCUSSION AND CONCLUSIONS

In this paper,we propose a novel defogging method based on local extrema,which relies only on the assumption thatthe depth map tends to be smooth everywhere except at edges.Inspired by techniques in empirical data analysis and morphological image analysis,we use the method based local extrema to estimate atmospheric veil.After obtaining multiscale restoration results,then we improve the visual effects through multi-scale tone manipulation algorithm,which is very effective for controlling the amount of local contrast at different scales.Compared with other defogging methods, the experiment results demonstrate our method can achieve more ideal defogging results without requiring any additional information(e.g.,depth information)or any user interactions. This method can be ef fi cient for practical application in real fog fi elds.

On the other hand,our work shares the common limitation of most image defogging methods,that is,does not always obtain equally good results on heavy haze scenes.Our work may result in poor effect when failing to identify the local minima and local maxima accurately.Therefore,the parameter settings under different weather conditions are very important.

In future work,we are going to investigate more optimal schemes for determining the parameters of multi-scale tone manipulation algorithm and the calculation of extremal envelope in order to further improve the visual effects and the operational ef fi ciency.

REFERENCES

[1]Nayar S K,Narasimhan S G.Vision in bad weather.In:Proceedings of the 7th International Conference on Computer Vision 1999.Kcrkyra: IEEE Computer Vision,1999.820-827

[2]Narasimhan S G,Nayar S K.Contrast restoration of weather degraded images.IEEE Transactionson PatternAnalysisand MachineIntelligence, 2003,25(6):713-724

[3]Shwartz S,Namer E,Schechner Y Y.Blind haze separation.In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.New York,USA:IEEE Press,2006.1984-1991

[4]Tan R T.Visibility in bad weather from a single image.In:Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition.Anchorage:IEEE Computer Society,2008.1-8

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

[6]He K M,Sun J,Tang X O.Single image haze removal using dark channel prior.In:Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition.Miami,USA:IEEE Press,2009. 1956-1963

[7]He K M,Sun J,Tang X O.Guided image fi ltering.In:Proceedings of the 2010 European Conference on Computer Vision(ECCV).Berlin, Germany:Springer-Verlag,2010.1-14

[8]Tarel J P,Hauti N.Fast visibility restoration from a single color or gray level image.In:Proceedings of the 12th International Conference on Computer Vision.Kyoto,Japan:IEEE,2009.20-28

[9]Yu J,Li D P,Liao Q M.Physics-based fast single image fog removal.Acta Automatica Sinica,2011,37(2):143-149

[10]Nishino K,Kratz L,Lombardi S.Bayesian defogging.International Journal of Computer Vision,2012,98(3):263-278

[11]Caraffa L,Tarel J P.Markov random fi eld model for single image defogging.In:Proceedings of the 2013 Intelligent Vehicles Symposium. Gold Coast,QLD:IEEE,2013.994-999

[12]Subr K,Soler C,Durand F.Edge-preserving multiscale image decomposition based on local extrema.ACM Transactions on Graphics,2009, 28(5):Article No.147

[13]Xu L,Lu C W,Xu Y,Jia J Y.Image smoothing via L0 gradient Minimization.ACM Transactions on Graphics,2011,30(5):Article No. 174

[14]Levin A,Lischinski D,Weiss Y.Colorization using optimization.ACM Transactions on Graphics,2004,23(3):1-6

[15]Farbman Z,Fattal R,Lischinski D,Szeliski R.Edge-preserving decompositions for multi-scale tone and detail manipulation.ACM Transactions on Graphics,2008,27(3),Article No.67.

[16]Hautiere N,Tarel J P,Aubert D,Dumont´E.Blind contrast enhancement assessment by gradient ratioing at visible edges.Image Analysis and Stereology,2008,27(2):87-95

[17]Hautire N,Tarel J P,Halmaoui H,Br´emond R,Aubert D.Enhanced fog detection and free space segmentation for car navigation.Machine Vision and Applications,2014,25(3):667-679

[18]Li P,Xiao C B,Yu J.Single image fog removal based on dark channel prior and local extrema.American Journal of Engineering and Technology Research,2012,12(2):96-104

Hongyu ZhaoPh.D.candidate at the College of Computer Science and Technology,Beijing University of Technology.He received the master degree from Computer Application Technology,Inner Mongolia Agricultural University in 2011.His research interests includes image processing and computer vision.Corresponding author of this paper.

Jing Yureceived the Ph.D.degree from the Department of Electronic Engineering,Tsinghua University in 2011.Her research interests include pattern recognition and image processing.

Xiujie XuPh.D.candidate at the College of Computer Science and Technology,Beijing University of Technology.She received the master degree from Computer Application Technology,Beijing University of Chemical Technology in 2004.Her research interests include internet of things(IoT)and cloud computing.

Xiao

the Ph.D.degree in pattern recognition and intelligent information systems,Tsinghua University in 1995.He is professor and assistant dean of the Department of Computer Science and Technology in Beijing University of Technology.His research interests include digital signal processing,audio and video signal processing, and network communication.

Manuscript received March 11,2014;accepted September 27,2014.This work was supported by Beijing Municipal Education Commission Science and Technology Development Plan key project(KZ201210005007)and the Beijing Municipal Education Commission Science and Technology Development Plan project(KM201010005011,KM201310005020).Recommended by Associate Editor Qianghai Dai.

:Hongyu Zhao,Chuangbai Xiao,Jing Yu,Xiujie Xu.Single image fog removal based on local extrema.IEEE/CAA Journal of Automatica Sinica, 2015,2(2):158-165

Hongyu Zhao and Chuangbai Xiao are with the College of Computer Science and Technology,Beijing University of Technology,Beijing 100124, China(e-mail:asas.014@163.com;cbxiao@bjut.edu.cn).

Jing Yu is with the Department of Electronic Engineering,Tsinghua University,Beijing 100084,China(e-mail:yujing@tsinghua.edu.cn).

Xiujie Xu is with the College of Computer Science and Technology Beijing University of Technology,Beijing 100124,China(e-mail:xiu-@163.com)).