Multilevel block truncation coding using a minimax error criterion for high-fidelity compression of digital images

An encoding technique called multilevel block truncation coding that preserves the spatial details in digital images while achieving a reasonable compression ratio is described. An adaptive quantizer-level allocation scheme which minimizes the maximum quantization error in each block and substantially reduces the computational complexity in the allocation of optimal quantization levels is introduced. A 3.2:1 compression can be achieved by the multilevel block truncation coding itself. The truncated, or requantized, data are further compressed in a second pass using combined predictive coding, entropy coding, and vector quantization. The second pass compression can be lossless or lossy. The total compression ratios are about 4.1:1 for lossless second-pass compression, and 6.2:1 for lossy second-pass compression. The subjective results of the coding algorithm are quite satisfactory, with no perceived visual degradation