Segmentation of real-world remote sensing images is a challenge due to the complex texture information with high heterogeneity. Thus, graph-based image segmentation methods have been attracting great attention in the field of remote sensing. However, most of the traditional graph-based approaches fail to capture the intrinsic structure of the feature space and are sensitive to noises. A -norm regularization-based graph segmentation method is proposed to segment remote sensing images. First, we use the occlusion of the random texture model (ORTM) to extract the local histogram features. Then, a -norm regularized low-rank and sparse representation () is implemented to construct a -regularized nonnegative low-rank and sparse graph (-graph), by the union of feature subspaces. Moreover, the -graph has a high ability to discriminate the manifold intrinsic structure of highly homogeneous texture information. Meanwhile, the representation takes advantage of the low-rank and sparse characteristics to remove the noises and corrupted data. Last, we introduce the -graph into the graph regularization nonnegative matrix factorization to enhance the segmentation accuracy. The experimental results using remote sensing images show that when compared to five state-of-the-art image segmentation methods, the proposed method achieves more accurate segmentation results.