Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing

Ioannis Koutis, Gary L. Miller, David Tolliver

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

Abstract

Linear systems and eigen-calculations on symmetric diagonally dominant matrices (SDDs) occur ubiquitously in computer vision, computer graphics, and machine learning. In the past decade a multitude of specialized solvers have been developed to tackle restricted instances of SDD systems for a diverse collection of problems including segmentation, gradient inpainting and total variation. In this paper we explain and apply the support theory of graphs, a set of of techniques developed by the computer science theory community, to construct SDD solvers with provable properties. To demonstrate the power of these techniques, we describe an efficient multigrid-like solver which is based on support theory principles. The solver tackles problems in fairly general and arbitrarily weighted topologies not supported by prior solvers. It achieves state of the art empirical results while providing robust guarantees on the speed of convergence. The method is evaluated on a variety of vision applications.

Original languageEnglish (US)
Title of host publicationAdvances in Visual Computing - 5th International Symposium, ISVC 2009, Proceedings
Pages1067-1078
Number of pages12
EditionPART 1
DOIs
StatePublished - 2009
Externally publishedYes
Event5th International Symposium on Advances in Visual Computing, ISVC 2009 - Las Vegas, NV, United States
Duration: Nov 30 2009Dec 2 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5875 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Symposium on Advances in Visual Computing, ISVC 2009
Country/TerritoryUnited States
CityLas Vegas, NV
Period11/30/0912/2/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing'. Together they form a unique fingerprint.

Cite this