Ⅰ. INTRODUCTION

POOR visibility becomes a major problem for most outdoor vision applications.Bad weather,such as fog and haze,can significantly 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,efficient,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 difficult 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 significant 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 satisfied. He et al.^[6] propose dark channel prior to estimation of the transmission map and use soft matting to refine 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 filter^[7]. Tarel et al.^[8] use the median filtering 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 filter 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 fields of unknown variables: scene albedo and depth,which has high complexity. Based on planar road constraint,^[11] introduces another efficient MRF approach to improve the restoration of the road area,assuming an approximately flat 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 significantly increase the visibility of the scene.

The article is structured as follows. Section Ⅱ describes the atmospheric scattering model and atmospheric veil. In Section Ⅲ, 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.

Ⅱ. 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 luminance I(x,y) of an object located at distance d(x,y) to the luminance R(x,y) measured close to this object:

$\begin{align} I\left( {x,y} \right) = R\left( {x,y} \right){{\rm e}^{ - \beta d\left( {x,y} \right)}} + A\left( {1 - {{\rm e}^{ - \beta d\left( {x,y} \right)}}} \right), \end{align}$

(1)

where d(x,y) is the distance of the object at pixel (x,y),A is called skylight and represents the luminance of the sky,$\beta$ is the scattering coefficient 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 solve R(x,y). The atmospheric scattering model assumes that the atmosphere is homogeneous and does not consider wavelength's influence on atmospheric scattering coefficient,so $\beta$ is considered to be a constant. The difficulty is that single image defogging is an ill-posed problem. Indeed,from (1),defogging requires to estimate A,$\beta$ and d at every pixel,only knowing the input image I.

In the atmospheric scattering model,the calculation of scene depth and atmospheric scattering coefficient generally requires additional information such as the vanishing points from the infinite plane. The location confirmation 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 difficult to be accurately estimated,which may cause the bad image visibility restoration. As a consequence,we introduce the atmospheric veil to avoid solving $d$ and $\beta$, which can be expressed by

$\begin{align} V(x,y) = A(1 - t(x,y)), \end{align}$

(2)

where V is defined as the atmospheric veil,t is the transmission map which can be expressed as $t(x,y) = {{\rm e}^{ - \beta d(x,y)}}$. V denotes the effect of ambient light^[1], $t$ reflects 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 of t needs to rely on solution of skylight and a constant parameter setting^[6],however,estimation of V can avoid being directly influenced 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.

Ⅲ. 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 Skylight A is typically assumed to be a global constant.We estimate A through the method based on the dark channel prior^[6].The dark channel of input image can be defined as

$\begin{align} {I_{dark}}(x,y) = \mathop {\min }\limits_{(x,y) \in \psi } (\mathop {\rm \min }\limits_{c \in \{ R,G,B\} } {I_c}(x,y)), \end{align}$

(3)

where ${I_c}(x,y)$ is a color channel of I(x,y) and $\psi$ is a local patch. In order to solve A,we choose the 0.1% brightest pixels of the dark channel as their preferred region and define these pixels as ${I_{0.1\% }}$. Then,the average value of ${I_{0.1\% }}$ in the input foggy image is selected as the initial skylight,i.e., ${A_{\rm mean}} = \text{mean}({I_{0.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

$\begin{align} A = \frac{A_{\rm mean}^c}{\mathop {\max }\limits_{c \in R,G,B} (A_{\rm mean}^c)}, \end{align}$

(4)

where A is the ideal skylight estimation result. Equation(4) means setting $A_{\rm mean}$ to be (1,1,1). Then,we can obtain the corrected image I' after white balance,which can be inferred as

$\begin{align} I'(x,y) = \frac {I(x,y)}{A}. \end{align}$

(5)

B. Coarse Estimation of Atmospheric Veil

From (1) and (2),we can find the atmospheric veil estimation becomes the key step to calculate the restored image R. Due to its physical properties,the atmospheric veil is subject to two constraints: i) $0 \le V\left( {x,y} \right) \le 1$,and ii) $V(x,y)$ is not higher than the minimal component of $I'(x,y)$. We thus take the min operation among three color channels and acquire a rough estimation of the atmospheric veil:

$\begin{align} \tilde V\left( {x,y} \right) = \mathop {\min }\limits_{c \in \{ R,G,B\} } (I{'_c}(x,y)), \end{align}$

(6)

where $\tilde V$ is the coarse estimation matrix of atmospheric veil. For the gray image,it is expressed as $\tilde V\left( {x,y} \right) = I'(x,y)$. Atmospheric veil coarse estimation is equivalent to the minimum filtering,but a single minimum filtering usually causes obvious halo or block artifacts. In order to obtain more accurate result,we need reasonable constraint manipulation to further refine $\tilde V$.

subsection{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 refinement 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 refinement.

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 fine-scale detail regardless of contrast^[13]. However,single mean layer is not sufficient 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) identification of local extrema of $\tilde V$; 2) inference of extremal envelopes; 3) visibility enhancement of the result by multi-scale tone manipulation algorithm.

First,we locate the extrema in $\tilde V$. Pixel $p$ is considered as a maxima if at most $k-1$ elements in the $k \times k$ neighborhood around $p$ are greater than the value at pixel $p$. In the same way we can locate the minima. Image details whose extrema are detected by using a $k \times k$ kernel have wavelengths of at least $k/2$ pixels. We choose $k=5$ as the size of the extrema-location 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 resp ectively. Let $S$ be the pixel set of local extrema,we compute an extremal envelope $E$ using an interpolation technique proposed by Levin et al.^{[12, 13, 14]} for image colorization. It assumes that the $E$ is a linear function of the $\tilde V$,and seeks an interpolant $E$ such that neighboring pixels $E(r)$ and $E(s)$ have similar values if $\tilde V(r)$ and $\tilde V(s)$ are similar. The calculation of extremal envelope is to minimize the energy function:

$\begin{align} {\sum\limits_r {\left( {E(r) - \sum\limits_{s \in N(r)} {{w_{rs}}E(s)} } \right)} ^2}, \end{align}$

(7)

which subject to the constraint

$\begin{align} \forall p \in S,\qquad E(p) \in \tilde V(p). \end{align}$

(8)

Equation (7) is designed to minimize the distance between the $E(r)$ at pixel $r$ and the weighted average of the $E(s)$ at neighboring pixels $N(r)$. $N(r)$ denotes the neighbors of $r$, and weights

$\begin{align} {w_{rs}} \propto \exp \left( { - \frac{{{{(\tilde V(r) - \tilde V(s))}^2})}}{{2\sigma _r^2}}} \right), \end{align}$

(9)

are computed using the local variance $\sigma _r^2$ of the intensities around $r$. ${w_{rs}}$ is 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 significant speedups. If the number of pixels of an input image is $N$,the computational time of single envelope can reach ${\rm 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 veil $V_i$,$i=1,2,3$. After calculating the skylight A through Section Ⅲ-A,we can directly recover the scene information in the ideal weather conditions:

$\begin{equation} {R_i}(x,y) = \frac{{I(x,y) - q{V_i}(x,y)}}{{1 - {V_i}(x,y)}}\times A \end{equation}$

(10)

where the parameter $q(0{\text{ }}\& lt;{\text{ }}q{\text{ }}\& lt;{\text{ }}1)$ is simply fixed 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 find that not all the processes of three scales are suitable to refine 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 significant 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 refinement; 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 images ${R_1}$ ,${R_2}$ ,${R_3}$ obtained from minimal envelope,maximal envelope,mean layer,respectively. We first construct a three-level decomposition of the CIELAB lightness channel,which includes coarse base level $b$ from ${R_1}$,two detail levels ${d^1}$ and ${d^2}$(${d^1} = {R_1} - {R_2}$,${d^2} = {R_2} - {R_3}$). The result of the manipulation R at each pixel $p$ is then given by

$\begin{align} {R_p} = \mu + C({\delta _0},\eta {b_p} - \mu ) + C({\delta _1},d_p^1) + C({\delta _2},d_p^2), \end{align}$

(11)

where $\mu $ is the mean of the lightness range,and function $C$ is 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 that would otherwise occur when the detail layers are significantly boosted. $\eta $ is the exposure parameter,${\delta _0}$, ${\delta _1}$ and ${\delta _2}$ are boosting factors. The solution procedure of (11) is non-iterative and can be performed in real time.

Fig. 2 is a tone adjustment example,which is obtained with the parameters ${\delta _0}={\delta _1}={\delta _2}=1,\mu =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 find that three levels are sufficient for detail display. Using more scales will enable finer control,but will consume more time.

Ⅳ. 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 filter^[7]. Tarel et al. introduced a complete inference of atmospheric veil in ^[8]. He et al first 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 $\times$ 315,460 $\times$ 380, 600 $\times$ 400 and 600 $\times$ 450,and the four groups of experimental images are expressed as Fig. 3(a) $\sim$ (d).

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 indicators $e$,$\bar r$ to assess the performances of a contrast restoration method through comparing two gray level images: the input image and the restored image. The value of $e$ evaluates 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 $\bar r$ expresses 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 as $h$. 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) $s$ to 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 indicators $e$,$\bar r$,$h$ and $s$ are evaluated for the comparison experiments on four images of Fig. 3,see Tables Ⅰ-Ⅳ.

As can be observed from Tables Ⅰ and Ⅱ,our method is able to achieve fog removal while restoring more visible edges. Table Ⅲ 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 Ⅳ 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 error ${E_{avg}}$ between 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 find 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.

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 significantly improve image contrast and clarity. Its main advantage is the more accurate and effective detail restoration.

Ⅴ. DISCUSSION AND CONCLUSIONS

In this paper,we propose a novel defogging method based on local extrema,which relies only on the assumption that the 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 multi-scale 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 efficient for practical application in real fog fields.

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 efficiency.