Image characterization and classification by physical complexity

Hector Zenil (1, 2) , Cédric Gaucherel (3) , Jean-Paul Delahaye (1, 2)

1 LIFL - Laboratoire d'Informatique Fondamentale de Lille
2 SMAC - Systèmes Multi-Agents et Comportements
3 UMR AMAP - Botanique et Modélisation de l'Architecture des Plantes et des Végétations

We present a method for estimating the complexity of an image based on Bennett's concept of logical depth. Bennett identified logical depth as the appropriate measure of organized complexity, and hence as being better suited to the evaluation of the complexity of objects in the physical world. Its use results in a different, and in some sense a finer characterization than is obtained through the application of the concept of Kolmogorov complexity alone. We use this measure to classify images by their information content. The method provides a means for classifying and evaluating the complexity of objects by way of their visual representations. To the authors' knowledge, the method and application inspired by the concept of logical depth presented herein are being proposed and implemented for the first time

Mots clés: Information content; Bennett's logical depth; Algorithmic complexity; Image classification; Algorithmic randomness

Domaines: Biodiversité et Ecologie; Traitement des images [eess.IV]

Hector Zenil, Cédric Gaucherel, Jean-Paul Delahaye. Image characterization and classification by physical complexity. Complexity, 2012, 17 (1), pp.26-42. ⟨10.1002/cplx.20388⟩. ⟨halsde-00733599⟩