In this paper, we present a new fractal-based indexing scheme that can handle different variations and disturbances of the query image. Our approach is a “query-by-example” approach based on the convergence speed of the decompression process. It consists in one application of the stored image IFS to the query one. Two questions can then be answered. The first one is the existence of the query: if it exists in the database, we find it immediately. The second concerns the retrieval similar images, which are given in order of similarity to the query. The dissimilarity measure is expressed in terms of mean and variance of the image. Other measures are under study. Experimental results, using images from Vistex databases of MIT, to demonstrate the validity of the approach, shows the robustness and tolerance of the method to different kind of disturbance.