The general segmentation algorithms are mainly dependent on visual features extracted from images, such as intensity, color and texture features. However, the feature extraction from hazy image becomes difficult and unstable. In this paper, a novel feature vector suitable to hazy image segmentation is introduced, and the corresponding feature extraction algorithm is proposed. The feature vector is composed of three components, which are degree of polarization of objects, depth map and color information, respectively. The degree of objects is separated with the degree of airlight using an decorrelation-based method. The depth map is inferred by analyzing the polarization images based on the hazy degradation model. And the color information is obtained from non-polarization image estimated by polarization images. Finally, these features are formed into a vector and fed to a well-known graph-based segmentation algorithm. After comparing the proposed results with those using only color cue on two aspects, it can be concluded that the proposed feature vector is more effective and robust than the usual features for hazy scene segmentation.