Constant‐Time Filtering by Singular Value Decomposition

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We present a technique implementing space‐variant filtering of an image, with kernels belonging to a given family, in time independent of the size and shape of the filter kernel support. The essence of our method is efficient approximation of these kernels, belonging to an infinite family governed by a small number of parameters, as a linear combination of a small number k of “basis” kernels. The accuracy of this approximation increases with k, and requires O(k) storage space. Any kernel in the family may be applied to the image in O(k) time using precomputed results of the application of the basis kernels. Performing linear combinations of these values with appropriate coefficients yields the desired result. A trade off between algorithm efficiency and approximation quality is obtained by adjusting k. The basis kernels are computed using singular value decomposition, distinguishing this from previous techniques designed to achieve a similar effect. We illustrate by applying our methods to the family of elliptic Gaussian kernels, a popular choice for filtering warped images.

Original languageEnglish (US)
Pages (from-to)153-163
Number of pages11
JournalComputer Graphics Forum
Volume13
Issue number2
DOIs
StatePublished - May 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design

Keywords

  • Filtering
  • Texture mapping
  • Warping

Fingerprint

Dive into the research topics of 'Constant‐Time Filtering by Singular Value Decomposition'. Together they form a unique fingerprint.

Cite this