Methods, apparatus, and computer-readable storage media for object retrieval and localization that employ a spatially-constrained similarity model. A spatially-constrained similarity measure may be evaluated by a voting-based scoring technique. Object retrieval and localization may thus be achieved without post-processing. The spatially-constrained similarity measure may handle object rotation, scaling and view point change. The similarity measure can be efficiently calculated by the voting-based method and integrated with inverted files. The voting-based scoring technique may simultaneously retrieve and localize a query object in a collection of images such as an image database. The object retrieval and localization technique may, for example, be implemented with a k-nearest neighbor (k-NN) re-ranking method in or as a retrieval method, system or module. The k-NN re-ranking method may be applied to improve query results of the object retrieval and localization technique.