As one of the most simple and effective single image dehazing methods, the dark channel prior (DCP) algorithm has been widely applied. However, the algorithm does not work for pixels similar to airlight ( e.g., snowy ground or a white wall), resulting in underestimation of the transmittance of some local scenes. To address that problem, we propose an image dehazing method by incorporating Markov random field (MRF) with the DCP. The DCP explicitly represents the input image observation in the MRF model obtained by the transmittance map. The key idea is that the sparsely distributed wrongly estimated transmittance can be corrected by properly characterizing the spatial dependencies between the neighboring pixels of the transmittances that are well estimated and those that are wrongly estimated. To that purpose, the energy function of the MRF model is designed. The estimation of the initial transmittance map is pixel-based using the DCP, and the segmentation on the transmittance map is employed to separate the foreground and background, thereby avoiding the block effect and artifacts at the depth discontinuity. Given the limited number of labels obtained by clustering, the smoothing term in the MRF model can properly smooth the transmittance map without an extra refinement filter. Experimental results obtained by using terrestrial and underwater images are given.