Abstract: The dark channel prior is a statistics of the haze-free natural outdoor images. Using dark channel prior to estimate the thickness of the haze, recent research work has made significant progresses in single image dehazing. However, it is difficult to apply existing method for processing high resolution input images because of the heavy computation costs of it. For some kinds of input images, existing method still can not reach enough accuracy which is required by visually-pleasing results. Motivated by this and based on thorough analysis of input image data, a kind of novel image prior, so-called gradient prior of transmission maps, has been proposed in this paper. Combining it with multiple-resolution image processing routine, we develop a powerful and practical single image dehazing method. The experimental results show our gradient prior of transmission maps greatly reduces the computation costs of the previous method. Furthermore, the optimization methods and parameter adjustment for our novel image prior enhance the accuracy of the computation related with transmission map, which results in better image quality under the previous method's ill-situation. Overall, compared with the state of the art, our new single image dehazing method achieves the same, and even better image quality with only around 1/8 computation time and memory cost.