Fast Matching Pursuit Video Coding by Combining Dictionary Approximation and Atom Extraction

Abstract—In this paper, we propose a systematic approach that approximates a target dictionary to reduce the complexity of a matching pursuit encoder. We combine calculation of the inner products and maximum atom extraction of a matching pursuit video coding scheme based on eigendictionary approximation and tree-based vector quantization. The approach makes the codec design and optimization cleaner and more systematic than previous dictionary approximation methods. We vary the quality of approximation to demonstrate the tradeoff between computa-tional complexity and coding efficiency. The experiment results show that our codec achieves speed-up factors of up to 100 with a performance loss of less than 0.1 dB. We use double-stimulus impairment scale scores to evaluate the perceptual quality of our approach for different levels of complexity. Index Terms—Fast algorithm, matching pursuit (MP), tree-based vector quantization (VQ), video coding. I