MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


GPU point list generation through histogram pyramids

Ziegler, Gernot and Tevs, Art and Theobalt, Christian and Seidel, Hans-Peter

June 2006, 13 pages.

Status: available - back from printing

Image Pyramids are frequently used in porting non-local algorithms to graphics hardware. A Histogram pyramid (short: HistoPyramid), a special version of image pyramid, sums up the number of active entries in a 2D image hierarchically. We show how a HistoPyramid can be utilized as an implicit indexing data structure, allowing us to convert a sparse matrix into a coordinate list of active cell entries (a point list) on graphics hardware . The algorithm reduces a highly sparse matrix with N elements to a list of its M active entries in O(N) + M (log N) steps, despite the restricted graphics hardware architecture. Applications are numerous, including feature detection, pixel classification and binning, conversion of 3D volumes to particle clouds and sparse matrix compression.

  • MPI-I-2006-4-002.pdf
  • Attachement: MPI-I-2006-4-002.pdf (1333 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Ziegler, Gernot and Tevs, Art and Theobalt, Christian and Seidel, Hans-Peter},
  TITLE = {GPU point list generation through histogram pyramids},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2006-4-002},
  MONTH = {June},
  YEAR = {2006},
  ISSN = {0946-011X},