In this paper, we present an adaptive nonparametric solution to the image parsing task, namely, annotating each image pixel with its corresponding category label. For a given test image, first, a locality-aware retrieval set is extracted from the training data based on superpixel matching similarities, which are augmented with feature extraction for better differentiation of local superpixels. Then, the category of each superpixel is initialized by the majority vote of the k -nearest-neighbor superpixels in the retrieval set. Instead of fixing k as in traditional nonparametric approaches, here, we propose a novel adaptive nonparametric approach that determines the sample-specific k for each test image. In particular, k is adaptively set to be the number of the fewest nearest superpixels that the images in the retrieval set can use to get the best category prediction. Finally, the initial superpixel labels are further refined by contextual smoothing. Extensive experiments on challenging data sets demonstrate the superiority of the new solution over other state-of-the-art nonparametric solutions.