FRAMEWORK FOR PARALLELIZATION OF BLOCK MATCHING FOR MOTION ESTIMATION AND STEREO MATCHING

Abstract

SAD based block matching algorithms form the backbone of various image and video processing applications such as video encoding, 3D vision, video surveillance, robotics, image registration and contour mapping. Exploiting thread-level parallelism is a promising way to improve the performance of such algorithms for running on multi-core general-purpose processors and GPUs. This thesis describes efficient strategies for implementation of block matching based algorithm for motion estimation and stereo vision on Intel multi-core architectures. A simple yet elegant GPU implementation of motion estimation has also been performed. A multi-pass method to unroll and rearrange the multiple nested loops of the block matching has been exploited for parallelization using the OpenMP shared memory programming model to improve the performance of motion estimation on general-purpose multi-core processors. The results have shown good speedups of 7.0lx over the sequential code performance on Intel Xeon Dual socket Quad-core processor and 1.69x on Intel Core2Duo processor. The GPU based parallel implementation using CUDA has also showed speedups up to 9.7x times. A simple yet effective strategy has also been developed for parallelization of Stereo vision. The method determines the disparity between pixels in two images using a block matching technique and has been implemented on multi-core processors showing decent speedups of around 5x times. This work also illustrates that by exploiting the capabilities of OpenMP and CUDA, a variety of exemplary tasks could be efficiently parallelized and the presently available general purpose multiprocessors and consumer level graphics cards can be more efficiently utilized. This should give software developers a compelling reason to multi-thread their applications.