A hierarchical fast encoding algorithm for vector quantization with PSNR equivalent to full search

In order to encode an image using VQ fast, it is most important to eliminate unnecessary distance computation as much as possible while searching for winner code. Sum and partial sum are used as features in this paper to roughly measure the difference between an input image block and a code to check whether current code could be a promising candidate winner code or not. A 3-step hierarchical fast search algorithm is proposed by narrowing search scope, skipping redundant distance computation and lastly simplifying must-do distance computation. For 10 standard gray-level images of size 512×512 with very different details, computational complexity can be reduced to below 5% ultimately for a codebook of size 1024 or 2048 meanwhile keeping the PSNR not as degraded as that of full search.