Efficient dark channel based image dehazing using quadtrees

Using dark channel prior—a kind of statistics of the haze-free outdoor images—to remove haze from a single image input is simple and effective. However, due to the use of soft matting algorithm, the method suffers from massive consumption of both memory and time, which largely limits its scalability for large images. In this paper, we present a hierarchical approach to accelerate dark channel based image dehazing. The core of our approach is a novel, efficient scheme for solving the soft matting problem involved in image dehazing, using adaptively subdivided quadtrees built in image space. Acceleration is achieved by transforming the problem of solving a N-variable linear system required in soft matting, to a problem of solving a much smaller m-variable linear system, where N is the number of pixels and m is the number of the corners in the quadtree. Our approach significantly reduces both space and time cost while still maintains visual fidelity, and largely extends the practicability of dark channel based image dehazing to handle large images.