Image similarity using the normalized compression distance based on finite context models

A compression-based similarity measure assesses the similarity between two objects using the number of bits needed to describe one of them when a description of the other is available. Theoretically, compression-based similarity depends on the concept of Kolmogorov complexity but implementations require suitable (normal) compression algorithms. We argue that the approach is of interest for challenging image applications but we identify one obstacle: standard high-performance image compression methods are not normal, and normal methods such as Lempel-Ziv type algorithms might not perform well for images. To demonstrate the potential of compression-based similarity measures we propose an algorithm that is based on finite-context models and works directly on the intensity domain of the image. The proposed algorithm is compared with several other methods.