Many Content-based Image Retrieval (CBIR) systems and image analysis tools employ color, shape and texture (in a combined fashion or not) as attributes, or signatures, to retrieve images from databases or to perform image analysis in general. Among these attributes, texture has turned out to be the most relevant, as it allows the identification of a larger number of images of a different nature. This paper introduces a novel signature which can be used for image analysis and retrieval. It combines texture with complexity extracted from objects within the images. The approach consists of a texture segmentation step, modeled as a Markov Random Field process, followed by the estimation of the complexity of each computed region. The complexity is given by a Multi-scale Fractal Dimension. Experiments have been conducted using an MRI database in both pattern recognition and image retrieval contexts. The results show the accuracy of the proposed method in comparison with other traditional texture descriptors and also indicate how the performance changes as the level of complexity is altered. ; CNPq (National Council for Scientific and Technological Development, Brazil) (Grant #308449/2010-0, Grant #484312/2013-8, and Grant #301558/2012-4) ; FAPESP (The State of Sao Paulo Research Foundation) (Grant # 11/01523-1)