The authors describe a novel approach to image matching which utilizes the minimal representation criterion as a means to obtain robust matching performance, even when image data are extremely noisy. They describe the application of this approach to the problem of matching noisy gray-level images to attributed models. Using the minimum representation criterion, the match between gray-level image features and an attributed graph model incorporates a representation size measure for the modeled points, the data residuals, and the unmodeled points. This structural representation identifies correspondence between a subset of data points and a subset of model points in a manner which minimizes the complexity of the resulting model. The proposed minimum representation matching algorithm is polynomial in complexity, and exhibits robust matching performance on examples where less than 30% of the features are reliable. The minimum representation principle is extensible to related problems using three-dimensional models and multisensor data matching.>