A Modified Spiral Search Algorithm and Its Embedded System Architecture Design

Authors: Nikolaos Kroupis, Minas Dasygenis, Dimitrios Soudris, Antonios Thanailakis

Abstract:

One of the most growing areas in the embedded community is multimedia devices. Multimedia devices incorporate a number of complicated functions for their operation, like motion estimation. A multitude of different implementations have been proposed to reduce motion estimation complexity, such as spiral search. We have studied the implementations of spiral search and identified areas of improvement. We propose a modified spiral search algorithm, with lower computational complexity compared to the original spiral search. We have implemented our algorithm on an embedded ARM based architecture, with custom memory hierarchy. The resulting system yields energy consumption reduction up to 64% and performance increase up to 77%, with a small penalty of 2.3 dB, in average, of video quality compared with the original spiral search algorithm.

Keywords: Spiral Search, Motion Estimation, Embedded Systems, Low Power

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078448

References:

[1] D. Soudris, C. Piguet, C. Goutis, Designing CMOS Circuits for Low-Power, Kluwer Academic Publisher Press, (2002)
[2] Christian Piguet, Low-Power Electronics Design, CRC Press, (2004)
[3] Thomas Wiegand, Gary J. Sullivan, Gisle Bjontegaard, and Ajay Luthra, "Overview of the H.264 / AVCVideo Coding Standard", in IEEE Transaction on Circuits and Systems for Video Technology, Vol. 13, Issue 7, pp. 560- 576 (2003)
[4] André Kaup and Hubert Mooshofer, "Performance and Complexity Analysis of Rate Constrained Motion Estimation in MPEG-4", Proc. Multimedia Systems and Applications II, Boston, Mass., (1999) 20-22 September, SPIE Vol. 3845, pp. 202-211
[5] Karl Guttag, Robert J. Gove, and Jerry R. Van Aken, "A single-chip multiprocessor for multimedia: The MVP", IEEE Computer Graphics and Applications, Vol. 12, No. 6, pp. 53-64 (1992)
[6] Chok-Kwan Cheung and Lai-Man Po, "Normalized Partial Distortion Search Algorithm for Block Motion Estimation", IEEE Transaction on Circuits and Systems for Video Technology, Vol. 10, No. 3, pp. 417-422 (2000)
[7] Xiaoan Lu, Thierry Fernaine, Yao Wang, "Modeling Power Consumption of a H.263 Video Encoder", Proceedings of the International Symposium on Circuits and Systems, ISCAS ÔÇÿ04, (2004) 23-26 May, pp. 77- 80
[8] D. Soudris, N. Zervas, A. Argyriou, M. Dasygenis, K. Tatas, C. Goutis and A. Thanailakis, "Data-reuse and parallel embedded architectures for lowpower, real-time multimedia applications", Proceedings of 10th Int. Workshop PATMOS, Gottigen, Germany, (2000) September, pp. 243-254
[9] M. Dasygenis, N. Kroupis, K. Tatas, A. Argyriou, D. Soudris and A.Thanailakis, Power and Performance Exploration of Embedded Systems Executing Multimedia Kernels, IEE Proc.-Comput. Digit. Tech., Issues "Low-power system-on-chip", Vol 149, No 4, pp.164-172, (2002)
[10] P. Kuhn, G. Diebel, S. Herrmann, A. Kaup, A. Keil, R. Mayer, H. Mooshofer, W. Stechele, "Complexity and PSNR-Comparison of several Fast Motion Estimation Algorithms for MPEG-4", vol. SPIE 3460 Applications of Digital Image Processing XXI, San Diego, July, (1998)
[11] F. Catthoor, K. Danckaert, K. Kulkarni, E. Brockmeyer, P.G Kjeldsberg, T. van Achteren and T. Omnes, Data Access and Storage Management for Embedded Programmable Processors, Kluwer Academic Publishers, Boston, (2002)
[12] Kwon Moon Nam, Joon-Seek Kim, Rae-Hong Park, Young Serk Shim, "A fast hierarchical motion vector estimation algorithm using mean pyramid", IEEE Transactions on Circuits and Systems on Video Technology, Vol.5, No.4, pp 344-351, (1995)
[13] Bhaskaran and K. Kostantinides, Image and Video Compression Standards, Kluwer Academic Publishers, (1998)
[14] Th. Zahariadis, D. Kalivas, "A Spiral Search Algorithm For Fast Estimation Of Block Motion Vectors", Proceedings of the EUSIPCO 96, Eighth European Signal Processing Conference, Trieste, Italy, (1996), September, pp 1079-82.
[15] Francky Catthoor, Frank Franssen, Sven Wuytack, Lode Nachtergaele, and Hugo De Man, "Global communication and memory optimizing transformations for low power signal processing systems", Proceedings IEEE/ACM Int. Workshop on Low Power Design, Napa Valley, CA, Apr. (1994), pp. 203-208
[16] Ilya Issenin, Erik Brockmeyer, Miguel Miranda and Nikil Dutt, "Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies", Proc. of Design, Automation and Test in Europe, DATE 2004, CNIT La Defese, Paris, France, (2004), 16-20 February, Vol. 1,pp. 202-207.
[17] N. D. Zervas, K. Masselos, C.E. Goutis, "Data-reuse exploration for low-power realization of multimedia applications on embedded cores", Proceedings of 9th International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS-99), (1999), October, pp. 71-80
[18] ARM Software Development Toolkit, ARM L.T.D., Version 2.50, Nov (1998)
[19] P. Shivakumar and N. Jouppi, CACTI 3.0: An Integrated Cache Timing, Power, and Area Model, WRL Research Report 2001/2, Aug. (2001).
[20] Prashant J. Shenoy, Harrick M. Vin, "Efficient support for scan operations in video servers", International Multimedia Conference, San Francisco, California, United States, (1995), pp. 131-140