Title: Real-time motion detection using block matching algorithms on multicore processors

Authors: Durgaprasad Gangodkar, Praveen Kumar, Padam Kumar, Ankush Mittal

Addresses: Department of Electronics and Computer Engineering, Indian Institute of Technology Roorkee, Roorkee – 247667, Uttarakhand, India. ' Department of Computer Science, Gokaraju Rangaraju Engineering College, Bachupally, Nizampet Road, Kukatpally, Hyderabad – 500 090, Andhra Pradesh, India. ' Department of Electronics and Computer Engineering, Indian Institute of Technology Roorkee, Roorkee – 247667, Uttarakhand, India. ' Department of Computer Science and Engineering, College of Engineering Roorkee, Roorkee – 247667, Uttarakhand, India

Abstract: Block matching algorithms (BMAs) like sum of absolute difference (SAD) and normalised cross correlation (NCC) form the basic building block in many computer vision applications. Full search (FS) BMAs take into account every pixel in a block, and are therefore very effective for wide motion search using different blocks. However, FS is computationally very expensive and unsuitable for real-time applications. We present efficient strategies for extracting data parallelism in FS SAD and NCC algorithms with fine-grained optimisation techniques for fully exploiting the computational capacity of the NVIDIA|s multicore graphic processing units (GPUs). We demonstrate that proposed parallel implementation achieves a speedup of around 34× for SAD and 59× for NCC on GPU GTX 280, compared to sequential implementation on dual socket quad core Xeon processor with 2.50 GHz and 16 GB DRAM. Since GPUs are quite cheap and popular, our algorithm can form the base for many real-time video systems.

Keywords: parallel processing; sum of absolute difference; SAD; normalised cross correlation; NCC; graphic processing unit; GPU; multicore processors; compute unified device architecture; CUDA; motion detection; block matching; real-time video.

DOI: 10.1504/IJICT.2011.041744

International Journal of Information and Communication Technology, 2011 Vol.3 No.2, pp.131 - 147

Published online: 20 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article