Disclosed are various embodiments labeling objects using multi-scale partitioning, rare class expansion, and/or spatial context techniques. An input image may be partitioned using different scale values to produce a different set of superpixels for each of the different scale values. Potential object labels for superpixels in each different set of superpixels of the input image may be assessed by comparing descriptors of the superpixels in each different set of superpixels of the input image with descriptors of reference superpixels in labeled reference images. An object label may then be assigned for a pixel of the input image based at least in part on the assessing of the potential object labels.