This paper proposes a novel technique for single image dehazing using adaptive nearest neighbor regularization to obtain a haze-free transmission map and then approximating the additional airlight component present in the hazy image. The proposed method relies on the intensity distribution in the small image patches of the image, exhibited from the Y channel of the YCbCr representation of the image, in order to preserve the texture information of the image. We substitute the commonly used soft matting technique in assessing the refined transmission map for haze removal, by adaptive nearest neighbor classifier. We assume that the actual color of the haze-free pixels in the image is approximated by a set of discrete colors. We discover the haze-free pixels using the Nearest-Neighbor (NN) regularization. Finally, unlike the state-of-the-art methods, we approximate the additional airlight present in the image patch and eliminate that to clear the haze, instead of estimating the transmission of the medium. The proposed nearest neighbor regularization technique automatically changes the patch size, which helps in dealing with the high depth region (e.g., sky region) of the image. We experimented on standard synthetic and real hazy image datasets and observed that, the proposed method outperforms the state-of-the-art, especially for images with sky regions. © 2020 Elsevier B.V.