一种改进的AEI算法中初始匹配码字的快速查找方法

An Improved Fast Search Method of Initial Matching Codeword for AEI Algorithm

矢量量化(VQ)是一种高效的有损压缩技术。快速码字搜索算法是矢量量化的核心问题之一,其性能决定了编码时间。快速码字搜索算法中,绝对误差不等式删除算法(AEI)是一种典型的3步算法,其第1步查找输入矢量的初始匹配码字的方法采用了Minimax法,是整个AEI算法中计算量最大的步骤,严重影响了算法的效率。针对这个问题,提出了一种新的查找初始匹配码字的方法——PartialMinimax法。该方法在保证所找到的初始匹配码字与原始AEI算法相同并且重建图像的PSNR(峰值信噪比)值不变的前提下,可显著减小这一步骤的计算量和查找时间,从而有效地提高了算法的总体编码速度。

Vector quantization （VQ） is an efficient approach of lossy data compression. The performance of the fast codeword search algorithm in VQ determines its encoding time. Absolute error inequality（AEI） algorithm is a standard fast codeword search algorithm, in which the initial matching codeword search is based on Minimax method. However, the computation cost that is required at this step in AEI algorithm is too much. Aimed at solving this problem, we propose an improved method for searching the initial matching codeword that is named as Partial Minimax Method. The proposed method guarantees the found initial matching codeword is the same as the standard AEt method and the PSNR performance of AEI method has no degradation. Because it can significantly reduce the computational cost for searching the initial matching codeword, the proposed method can speed up the standard AEI method effectively.