OBJECTIVE: We introduce descriptor-based segmentation that extends existing patch-based methods by combining intensities, features, and location information. Since it is unclear which image features are best suited for patch selection, we perform a broad empirical study on a multitude of different features. METHODS: We extend nonlocal means segmentation by including image features and location information. We search larger windows with an efficient nearest neighbor search based on kd-trees. We compare a large number of image features. RESULTS: The best results were obtained for entropy image features, which have not yet been used for patch-based segmentation. We further show that searching larger image regions with an approximate nearest neighbor search and location information yields a significant improvement over the bounded nearest neighbor search traditionally employed in patch-based segmentation methods. CONCLUSION: Features and location information significantly increase the segmentation accuracy. The best features highlight boundaries in the image. SIGNIFICANCE: Our detailed analysis of several aspects of nonlocal means-based segmentation yields new insights about patch and neighborhood sizes together with the inclusion of location information. The presented approach advances the state-of-the-art in the segmentation of parotid glands for radiation therapy planning.