Single image dehazing with its ill-posted characteristics has been a popular challenge in low-level vision. In this paper, an alternative approach of solving a single hazy image is presented. Initially, we propose a new haze model in consideration of multiple scattering during light propagation. Compared with the traditional dichromatic atmospheric scattering model, our new model requires fewer restrictive assumptions. Also, considering a hazy image as the distorted and blurred version of a fine image, we adopt a sparse coding technology that presents every patch with dedicate-prepared over-complete dictionaries and trace back to the image which is haze-free. Extensive experimental results on a variety of hazy images demonstrate that the proposed method delivers higher performance in image restoration producing an output with faithful colors and fine details.