Inter-frame Prediction with Fast Weighted Low-rank Matrix Approximation

Zhi-Long Huang, Hsu-Feng Hsiao


In the field of video coding, inter-frame prediction plays an important role in improving compression efficiency. The improved efficiency is achieved by finding predictors for video blocks such that the residual data can be close to zero as much as possible. For recent video coding standards, motion vectors are required for a decoder to locate the predictors during video reconstruction. Block matching algorithms are usually utilized in the stage of motion estimation to find such motion vectors. For decoder-side motion derivation, proper templates are defined and template matching algorithms are used to produce a predictor for each block such that the overhead of embedding coded motion vectors in bit-stream can be avoided. However, the conventional criteria of either block matching or template matching algorithms may lead to the generation of worse predictors. To enhance coding efficiency, a fast weighted low-rank matrix approximation approach to deriving decoder-side motion vectors for inter frame video coding is proposed in this paper. The proposed method first finds the dominating block candidates and their corresponding importance factors. Then, finding a predictor for each block is treated as a weighted low-rank matrix approximation problem, which is solved by the proposed column-repetition approach. Together with mode decision, the coder can switch to a better mode between the motion compensation by using either block matching or the proposed template matching scheme.

Full Text:



J. Ostermann, J. Bormans, P. List, D. Marpe, M. Narroschke, F. Pereira, T. Stockhammer, and T. Wedi, “Video coding with H.264/AVC: tools, performance, and complexity,” IEEE Circuits and Systems Magazine, pp. 7–28, 2004, First Quarter. 16 Z.-L. HUANG, H.-F. HSIAO

G. J. Han, J. Gary, J. R. Ohm, W. J. Han, and T. Wiegand, “Overview of the High Efficiency Video Coding (HEVC) Standard,” in IEEE Transactions on Circuits and Systems for Video Technology, September 2012, p. 1.

K. Sugimoto, M. Kobayashi, Y. Suzuki, S. Kato, and S. B. Choong, “Inter frame coding with template matching spatio-temporal prediction,” in IEEE International Conference on Image Processing, October 2004, pp. 24–27.

Y. Suzuki, C. S. Boon, and T. K. Tan, “Inter frame coding with template matching averaging,” in IEEE International Conference on Image Processing, 16 September – 19 October 2007.

M. Turkan and C. Guillemot, “Sparse approximation with adaptive dictionary for image prediction,” in IEEE International Conference on Image Processing, Cairo, Egypt, November 2009, pp. 25–28.

J. Wang, Y. Shi, W. Ding, and B. Yin, “A low-rank matrix completion based intra prediction for h.264/AVC,” in Multimedia Signal Processing (MMSP), 2011 IEEE 13th International Workshop, 17–19 October 2011.

Y. Suzuki, C. S. Boon, and S. Kato, “Block-based reduced resolution inter frame coding with template matching prediction,” in IEEE International Conference on Image Processing, 8-11 October 2006, pp. 1701–1704.

K. H. Ng, L. M. Po, K. W. Cheung, X. Y. Xu, and K. M. Wong, “A new motion compensation method using superimposed inter-frame signals,” in IEEE International Conference on Speech and Signal Processing (ICASSP), 25-30 March 2012, pp. 1213–1216.

S. Milani, “Segmentation-based motion compensation for enhanced video coding,” in IEEE International Conference on Image Processing (ICIP), 11-14 September 2011, pp. 1649–1652.

J. Bennett and S. Lanning, “The netflix prize,” in Proceedings of KDD Cup and Workshop, 2007.

S. Ma, D. Goldfarb, and L. Chen, “Robust principal component analysis?: Recovering low-rank matrices from sparse errors,” in IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM), October 2010, pp. 201–204.

H. Ji, C. Liu, Z. Shen, and Y. Xu, “Robust video denoising using low rank matrix completion,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2010, pp. 1791–1798.

Z. Lin, M. Chen, L. Wu, and Y. Ma, “The augmented lagrange multiplier method for exact recovery of a corrupted low-rank matrix,” University of Illinois at Urbana-Champaign, Tech. Rep. #UILU-ENG-09-2215, October 2009.

Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, “Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition,” in Proceedings of The 27th Annual Asilomar Conference on Signals, Systems and Computers, 1–3 November 1993, pp. 40–44.

E. J. Cand`es and B. Recht, “Exact matrix completion via convex optimization,”In Magazine Communications of the ACM CACM Homepage, vol. 55, no. 6, pp. 111–119, June 2012.

D. Bertsekas, Constrained optimization and lagrange multiplier method. Academic Press, 1982.

D. Zonoobi, A. A. Kassim, and Y. V. Venkatesh, “Gini index as sparsity measure for signal reconstruction from compressive Samples, ”IEEE Journal on Selected Topics in Signal Processing, pp. 927–932, September 2011.


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933