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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:
    Grady, L. (author) / Schwartz, E.L. (author)


    Publication date :

    2004-01-01


    Size :

    728500 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



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

    Grady, L. / Schwartz, E. / IEEE Computer Society | British Library Conference Proceedings | 2004


    Faster fractal image compression using quadtree recomposition

    Jackson, D. J. / Mahmoud, W. / Stapleton, W. A. et al. | British Library Online Contents | 1997


    Complementary quadtree

    Kim, Y.-M. / Park, S.-B. | British Library Online Contents | 1993


    Image search based on quadtree Zernike decomposition

    Neri, A. / Carli, M. / Palma, V. et al. | British Library Online Contents | 2010