This paper presents an image haze removal algorithm for a single image. The conventional Dark Channel Prior (DCP) algorithm estimates the transmission map using the dark information in an image. The haze regions are then detected using a matting algorithm. However, the resulting transmission map invariably includes some block artifacts as the DCP algorithm is based on block-based processing. Therefore, to solve this problem, an algorithm for a modified transmission map is proposed using a Hidden Markov Random Field (HMRF) algorithm. Experimental results confirm that the proposed algorithm is superior to conventional algorithms in image haze removal.