Geologists and planetary scientists will benefit from methods for accurate segmentation of rocks in natural scenes. However, rocks are poorly suited for current visual segmentation techniques - they exhibit diverse morphologies and have no uniform property to distinguish them from background soil. We address this challenge with a novel detection and segmentation method incorporating features from multiple scales. These features include local attributes such as texture, object attributes such as shading and two-dimensional shape, and scene attributes such as the direction of illumination. Our method uses a superpixel segmentation followed by region-merging to search for the most probable groups of superpixels. A learned model of rock appearances identifies whole rocks by scoring candidate superpixel groupings. We evaluate our method's performance on representative images from the Mars Exploration Rover catalog.