Compute-unified device architecture implementation of a block-matching algorithm for multiple graphical processing unit cards

摘要

We describe and evaluate a fast implementation of a classi-ncal block-matching motion estimation algorithm for multiple graphicalnprocessing units (GPUs) using the compute unified device architec-nture computing engine. The implemented block-matching algorithmnuses summed absolute difference error criterion and full grid searchn(FS) for finding optimal block displacement. In this evaluation, wencompared the execution time of a GPU and CPU implementationnfor images of various sizes, using integer and noninteger searchngrids. The results show that use of a GPU card can shorten com-nputation time by a factor of 200 times for integer and 1000 timesnfor a noninteger search grid. The additional speedup for a noninte-nger search grid comes from the fact that GPU has built-in hardwarenfor image interpolation. Further, when using multiple GPU cards,nthe presented evaluation shows the importance of the data split-nting method across multiple cards, but an almost linear speedupnwith a number of cards is achievable. In addition, we compared thenexecution time of the proposed FS GPU implementation with twonexisting, highly optimized nonfull grid search CPU-based motion es-ntimations methods, namely implementation of the Pyramidal LucasnKanade Optical flow algorithm in OpenCV and simplified unsymmet-nrical multi-hexagon search in H.264/AVC standard. In these com-nparisons, FS GPU implementation still showed modest improvementneven though the computational complexity of FS GPU implementa-ntion is substantially higher than non-FS CPU implementation. Wenalso demonstrated that for an image sequence of 720 × 480 pixels innresolution commonly used in video surveillance, the proposed GPUnimplementation is sufficiently fast for real-time motion estimation atn30 frames-per-second using two NVIDIA C1060 Tesla GPU cards.