We introduce a texture descriptor based on fractal analysis. This descriptor, called the Multi Fractal Spectrum (MFS), provides an efficient framework for coding with very low dimension the essential structure of textures. The MFS has the property of being mathematically proven invariant under the bi-Lipschitz map, which means under any smooth transformation, including changes in viewpoint, non-rigid deformations of the textured surface as well as locally linear changes in illumination. Experiments demonstrate that in practical computations the MFS is very robust to these transformations. Intuitively, one may view the MFS as a variation of the "histogram", which captures some geometric information encoded in the texture and is very robust to environmental changes.