How to measure arithmetic complexity of compression algorithms: a simple solution

Image compression techniques appear to have matured during the past few years. Differences between the compression performance of different algorithms are very small. The key differences are now features such as embedded coding, regions of interest coding, bitstream manipulation or error resilience. However, there is one major difference present but only rarely discussed: algorithmic complexity. It can correspond to the number of arithmetic operations, memory demands and bandwidth or simply the difficulty of implementation. The performance of image compression algorithms are generally presented in terms of PSNR relative to the possible bitrates. It is interesting to consider a similar relationship in terms of complexity. Unfortunately the term complexity itself is not well defined. In this paper a methodology to measure arithmetic complexity (and eventually other types of complexity) of a complete compression algorithm is presented. The model is then applied to the ISO standard JPEG encoder