Most of the existing single image dehazing algorithms are on the basis of local priors, and there is block effect in dehazing results. The image artifacts are augmented at heavy haze regions, if there is no special treatment. For example, the noise and color overlap which are almost invisible in the original haze image are enhanced after dehazing, and affect the quality of the dehazing images. In order to eliminate these disadvantages, a novel image dehazing algorithm is proposed. Firstly, the non-local prior is adopted to estimate the initial transmission. Then, a regularized method is used to optimize it, the L1/2 norm of gradient difference of original image and dehazing image is used as regularization term to suppress the noise interference. The results show that the proposed algorithm can recover the details and color effectively, and has better robustness than the local prior methods.