ML Anthology

Faster Graph-Theoretic Image Processing via Small-World and Quadtree Topologies

Leo J. Grady, Eric L. Schwartz
CVPR 2004 pp. 360-365
doi:10.1109/CVPR.2004.107 /cvpr/2004/grady2004cvpr-faster/

Abstract

Numerical methods associated with graph-theoretic image processing algorithms often reduce to the solution of a large linear system. We show here that choosing a topology that yields a small graph diameter can greatly speed up the numerical solution. As a proof of concept, we examine two image graphs that preserve local connectivity of the nodes (pixels) while drastically reducing the graph diameter. The first is based on a "small-world" modification of a standard 4-connected lattice. The second is based on a quadtree graph. Using a recently described graph- theoretic image processing algorithm we show that large speed-up is achieved with a minimal perturbation of the solution when these graph topologies are utilized. We suggest that a variety of similar algorithms may also benefit from this approach.

CVPR Semantic Scholar

Cite

Text

Grady and Schwartz. "Faster Graph-Theoretic Image Processing via Small-World and Quadtree Topologies." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2004. doi:10.1109/CVPR.2004.107

Markdown

[Grady and Schwartz. "Faster Graph-Theoretic Image Processing via Small-World and Quadtree Topologies." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2004.](https://mlanthology.org/cvpr/2004/grady2004cvpr-faster/) doi:10.1109/CVPR.2004.107

BibTeX

@inproceedings{grady2004cvpr-faster,
  title     = {{Faster Graph-Theoretic Image Processing via Small-World and Quadtree Topologies}},
  author    = {Grady, Leo J. and Schwartz, Eric L.},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {2004},
  pages     = {360-365},
  doi       = {10.1109/CVPR.2004.107},
  url       = {https://mlanthology.org/cvpr/2004/grady2004cvpr-faster/}
}