Image classification using compression distance

The normalised compression distance measures the mutual compressibility of two signals. We show that this distance can be used for classification on real images. Furthermore, the same compressor can also operate on derived features with no further modification. We consider derived features consisting of trees indicating the containment and relative area of connected sets within the image. It had been previously postulated that such trees might be useful features, but they are too complicated for conventional classifiers. The new classifier operating on these trees produces results that are very similar to those obtained on the raw images thus allowing, for the first time, classification using the full trees