Local appearance-based approaches for planar object recognition do not support efficient means for indexing of object models. The size of the feature set which needs to be stored and processed is also large. To reduce database size, we propose an optimal feature extraction technique that selects only the salient features of an object. Since in typical local appearance-based systems, the actual feature information is not isolated from the background, scene clutter causes error in recognition. We propose a mechanism whereby this shortcoming can be alleviated. Further, by indexing onto this space, we propose to improve the performance in terms of computation time and suppression of false positives. This indexing mechanism based on the color histogram and the geometry of the feature, exploits the fact that features tend to form clusters in the feature space based on their similarity of appearances. We have implemented the proposed system and verified its validity through extensive testing. © 2002 Published by Elsevier Science B.V.