Prof. Shai Avidan Tel Aviv University, School of Electrical Engineering
Haze limits visibility and reduces image contrast in outdoor images. The degradation is different for every pixel and depends on the distance of the scene point from the camera. This dependency is expressed in the transmission coefficients, that control the scene attenuation and amount of haze in every pixel. Previous methods solve the single image dehazing problem using various patch-based priors.
We propose an algorithm based on a new, non-local prior.
Our method is based on the observation that the number of distinct colours in an image is orders of magnitude smaller than the number of pixels.
The observation regarding a small number of distinct colours holds for haze-free images. In the presence of haze, object points that belong to the same colour cluster end up with different acquired colours, since they are in disparate image areas and thus have different distances from the camera. This prior suggests that pixels clustered together in a haze-free image form a line in RGB space in a hazy image.
This prior is demonstrated in Fig 1: Non-Local Prior. A haze-free image is clustered using K-means to 500 clusters. The pixels belonging to four of these clusters are marked by different colour markers in (a) and their RGB coordinates are plotted in (b), demonstrating tight clusters. Note that the clusters include pixels distributed over the entire image that come from objects with different distances from the camera.
A synthetic hazy image (c) was generated from the clear image. The same pixels as in (a) are marked. However, now, colours of pixels that belonged to the same colour cluster are no longer similar. This is depicted in RGB space in (d), where the colour coordinates of these pixels are distributed along a haze-line spanned by the original colour and the air light. The pixels marked by purple circles (originating from the sand patch) are in similar distances, so their distribution along the haze-line is rather tight. However, the pixels marked by orange triangles (grassy areas) are found at different locations in the real world, so they are distributed along the haze-line.

Pictures below describe the before and after processing of hazy images by our non-local prior algorithm:

In contrast to previous methods our non-local algorithm is pixel based and not patch-based. This makes our algorithm faster, more robust, and less prone to issues such as the choice of patch size, patch tiling, and patches with non-uniform content. Our method was tested and found to work well on many real-world images.