Single image dehazing can benefit many computer vision applications hence has attracted much more attention in recent years. However, it still remains a challenging task due to its double uncertainty of scene transmission and scene radiance. The existing image dehazing methods usually impair edges in the estimated transmission which leads to halo effects in the dehazing results. Besides, most existing methods suffer from noise and artifacts amplification in dense haze region after dehazing. To address these challenges, we propose a transmission adaptive regularized image recovery method for high quality single image dehazing. An initial transmission map is first obtained by a boundary constraint on the haze model. Then it is refined by applying a non-local total variation (NLTV) regularization to keep depth structures while smoothing excessive details. Noticing that the artifacts amplification effect depends on scene transmission, a transmission adaptive regularized recovery method based on NLTV is proposed to simultaneously suppress visual artifacts and preserve image details in the final dehazing result. An efficient alternating optimization algorithm is also proposed to solve the regularization model. Thorough experimental results demonstrate that the proposed method can effectively suppress visual artifacts for degraded hazy images, and yields high-quality results comparative to the state-of-the-art dehazing methods both quantitatively and qualitatively.