Faster graph-theoretic image processing via small-world and quadtree topologies

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.