A scalable massively parallel motion and disparity estimation scheme for multiview video coding

Multiview video coding (MVC) has recently received considerable attention. It is proposed as an extension of H.264/Advanced Video Coding (AVC) standard for multiple video source compression. To resolve the extremely high computational complexity of MVC (and in fact other AVC techniques), suitable parallel algorithms need to be developed that are amenable to implementation on low-cost massively parallel architecture, platforms that have found a common place due to recent advances in the parallel computer architecture. The high complexity of MVC is due to its prediction structure, where motion estimation (ME) between the frames and disparity estimation (DE) between the views contribute to more than 99% of overall complexity of the coder. This paper presents the development and implementation of a scalable massively parallel fast search algorithm to significantly reduce the computational cost of ME/DE over the current best available full block matching, and suboptimal fast search algorithms. The proposed massively parallel fast search algorithm (DZfast), when evaluated over eight views, outperforms the existing full search and fast search MVC algorithms by a factor of up to 245.8 and 8.4, respectively. This speedup comes at no or minute loss in rate-distortion performance