This paper proposes an efficient method to locate a three-dimensional object in cluttered environment. Model of the object is represented in a reference scale by the local features extracted from several reference images. A PCA-based hashing technique is introduced for accessing the database of reference features efficiently. Localization is performed in an estimated relative scale. Firstly, a pair of stereo images is captured simultaneously by calibrated cameras. Then the object is identified in both images by extracting features and matching them with reference features, clustering the matched features with generalized Hough transformation, and verifying clusters with spatial relations between the features. After the identification process, knowledge-based correspondences of features belonging to the object present in the stereo images are used for the estimation of the 3D position. The localization method is robust to different kinds of geometric and photometric transformations in addition to cluttering, partial occlusions and background changes. As both the model representation and localization are single-scale processes, the method is efficient in memory usage and computing time. The proposed relative scale method has been implemented and experiments have been carried out on a set of objects. The method results very good accuracy and takes only a few seconds for object localization by our primary implementation. An application of the relative scale method for exploration of an object in cluttered environment is demonstrated. The proposed method could be useful for many other practical applications. © 2007 Elsevier B.V. All rights reserved.