
Leo Grady and Eric L. Schwartz.
Faster graphtheoretic image processing via smallworld and quadtree
topologies.
In Proceedings of the 2004 IEEE Computer Society Conference on
Computer Vision and Pattern Recognition, volume 2 of Conference on
Computer Vision and Pattern Recognition, pages 360365, Washington DC, June
27  July 2 2004. IEEE Computer Society, IEEE.
Numerical methods associated with graphtheoretic
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 ``smallworld''
modification of a standard 4connected lattice. The
second is based on a quadtree graph. Using a
recently described graphtheoretic image processing
algorithm we show that large speedup 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.
