Video Block Motion Estimation Based on Walsh-Hadamard Projection Kernels

Abstract:

In modern video coders, motion is estimated using an algorithm that calculates the distance and direction of motion on a block-by-block basis. In this paper, a new motion estimation scheme is proposed. This scheme uses the sum of absolute difference between the Walsh-Hadamard projections of two blocks as measurement. And integral image is used to perform the scheme. Different from other methodologies using WH projections, the method proposed in this paper does not require iteration over every position to effectively calculate the WH projections of a block at any location. And the complexity of this scheme is regardless of the size (2^N×2^N) of the block. Comparing to the methods (Full Search, Three Step Search and Diamond Search) based on sum of absolute differences (SAD), experiments show that the proposed scheme significantly reduces computational complexity with little increase in the bit-rate.

• Periodical: Advanced Materials Research (Volumes 971-973)
• Pages: 1847-1852
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.971-973.1847
• Online since: June 2014
• Authors: Jia Ge*, Jia Song Wu, Zhi Fang Dong, Hua Zhong Shu
• Keywords: Block Matching (BM), Motion Estimation, Video Coding, Walsh-Hadamard Transform (WHT)

References

[1] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, T. Ishiguro, Motion compensated inter-frame coding for video conferencing, in Proc. Nat. Telecommun. Conf., New Orleans, LA, Nov. 29-Dec. 3 1981, pp. G5. 3. 1-5. 3. 5.

[2] Po L.M. Ma W.C. A novel four-search algorithm for block motion estimation,. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(3): 313-317.

DOI: 10.1109/76.499840

[3] Tham J.Y. Ranganath S. Kassim A.A. A novel unrestricted center-biased diamond search algorithm for block motion estimation,. IEEE Transactions on Circuits and Systems for Video Technology, 1998, 8(4): 369-377.

DOI: 10.1109/76.709403

[4] N. Li, C. M. Mak, and W. K. Cham, Fast block matching algorithm in Walsh–Hadamard domain, in Proc. Asian Conf. Computer. Vis. (ACCV) , Jan. 13 –16, 2006, p.712–721.

DOI: 10.1007/11612704_71

[5] Y. Moshe and H. Hel-Or, A fast block motion estimation algorithm using Gray Code Kernels, inProc. 6th IEEE ISSPIT, Vancouver, BC, Canada, p.185–190. (2006).

DOI: 10.1109/isspit.2006.270794

[6] C. S. Young and C. S. Ik, Hierarchical Motion Estimation in Hadamard Transform Domain, Electronics Letters, vol. 35(25), pp.2187-8, Dec. (1999).

DOI: 10.1049/el:19991502

[7] M. Brünig and B. Mense, A Fast Exhaustive Search Algorithm Using Orthogonal Transforms, Proc. 7th. IWSSIP 2000, pp.111-4, June (2000).

[8] C. M. Mak, C. K. Fong, and W. K. Cham. Fast Motion Estimation forH. 264/AVC in Walsh–Hadamard domain ,. IEEE Transactions on Circuits and Systems for Video Technology, Vol. 18, No. 6, June, 2008, P. 735-745.

DOI: 10.1109/tcsvt.2008.918790

[9] Y. Hel-Or and H. Hel-Or, Real-Time Pattern Matching Using Projection Kernels, 9th IEEE Int. Conf. Computer Vision, pp.1486-93, Oct. (2003).

DOI: 10.1109/iccv.2003.1238666

[10] Y. Moshe and H. Hel-Or, Video block motion estimation based on gray-code kernels, IEEE Trans. Image Process. , vol. 18, no. 10, p.2243–2254, Oct. (2009).

DOI: 10.1109/tip.2009.2025559

[11] H. Kitajima. Energy packing efficiency of the hadamard trans-form., IEEE T-Comm., pages 1256–1258, (1976).

DOI: 10.1109/tcom.1976.1093239

[12] G. Ben-Artzi, H. Hel-Or and Y. Hel-Or, Filtering with Gray Code Kernels, Proc. of the 17th Int. Conf. Pattern Recognition, vol. 1, pp.556-9, Aug. (2004).

DOI: 10.1109/icpr.2004.1334198

[13] G. Ben-Artzi, H. Hel-Or and Y. Hel-Or, The Gray Code Filter Kernels, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 29, no. 3, pp.382-393, Mac. (2007).

DOI: 10.1109/tpami.2007.62

[14] Franklin C. Crow. Summed-area tables for texture mapping ,. Proceedings of the 11th annual conference on Computer graphics and interactive techniques. p.207–212. (1984).

DOI: 10.1145/800031.808600

[15] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, A novel unrestricted center-biased diamond search algorithm for block motion estimation, IEEE Trans. Circuits Syst. Video Technol., vol. 8, no. 4, p.369–377, Apr. (1998).

DOI: 10.1109/76.709403