Parallel algorithms to a parallel hardware: Designing vision algorithms for a GPU

Junsik Kim, Myung Hwangbo, and Takeo Kanade
Workshop on Embedded Computer Vision (ECV), 2009 (held in conjunction with ICCV)., October, 2009.


Download
  • Adobe portable document format (pdf) (1MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
A GPU becomes an affordable solution for accelerating a slow process on a commercial system. The most of achievements using it for non-rendering problems are the exact re-implementation of existing algorithms designed for a serial CPU. We study about conditions of a good parallel algorithm, and show that it is possible to design an algorithm targeted to a parallel hardware, though it may be useless on a CPU. The optical flow estimation problem is investigated to show the possibility. In some time-critical applications, it is more important to get results in a limited time than to improve the results. We focus on designing optical flow approximation algorithms tailored for a GPU to get a reasonable result as fast as possible by reformulating the problem as change detection with hypothesis generation using features tracked in advance. Two parallel algorithms are proposed: direct interpolation and testing multiple hypotheses. We discuss implementation issues in the CUDA framework. Both methods are running on a GPU in a near video rate providing reasonable results for the time-critical applications. These GPU-tailored algorithms become useful by running about 240 times faster than the equivalent serial implementations which are too slow to be useful in practice.

Notes

Text Reference
Junsik Kim, Myung Hwangbo, and Takeo Kanade, "Parallel algorithms to a parallel hardware: Designing vision algorithms for a GPU," Workshop on Embedded Computer Vision (ECV), 2009 (held in conjunction with ICCV)., October, 2009.

BibTeX Reference
@inproceedings{Kim_2009_6536,
   author = "Junsik Kim and Myung Hwangbo and Takeo Kanade",
   title = "Parallel algorithms to a parallel hardware: Designing vision algorithms for a GPU",
   booktitle = "Workshop on Embedded Computer Vision (ECV), 2009 (held in conjunction with ICCV).",
   month = "October",
   year = "2009",
}