Irregular Pyramids (bibtex)

by Walter G. Kropatsch, Annick Montanvert

Abstract:

A pyramid is a stack of images with exponentially decreasing resolutions. Many image processing algorithms run on this hierarchical structure in $O(łog n)$ parallel processing steps where $n$ is a side of the input image. Perturbations in the structure may disturb the originally regular neighborhood relations and also the stability of the results. On the other hand, biological vision is based on piecewise regular patches in the retina, e.g. of a monkey or a human. P. Meer's stochastic pyramid is such an irregular structure. The parallel generation of the structure is governed by two ``decimation rules'' that also characterize a maximal independent set on the neighborhood graph of the image pixels. In general, the number of neighbors in the decimated graph may increase. It is shown that the decimation $G'(V',E')$ of any neighborhood-graph $G(V,E)$ preserves the degrees in the corresponding dual graphs. However the dual of $G'$ is not always a ``good'' decimation of the dual of $G$. Investigating in parallel dual decimations of regular graphs, one finds unique solutions that have interesting properties for image pyramids. Besides the above theoretical motivation for irregular structures, we can find similar strutures in the retinas of monkeys (and also of humans).

Reference:

Irregular Pyramids (Walter G. Kropatsch, Annick Montanvert), Technical report, PRIP, TU Wien, 1992.

Bibtex Entry:

@TechReport{PP-Kropatsch92b, author = "Walter G. Kropatsch and Annick Montanvert", institution = "PRIP, TU Wien", number = "PRIP-TR-005", title = "Irregular {P}yramids", year = "1992", url = "ftp://ftp.prip.tuwien.ac.at/pub/publications/trs/tr5.ps.gz", abstract = "A pyramid is a stack of images with exponentially decreasing resolutions. Many image processing algorithms run on this hierarchical structure in $O(\log n)$ parallel processing steps where $n$ is a side of the input image. Perturbations in the structure may disturb the originally regular neighborhood relations and also the stability of the results. On the other hand, biological vision is based on piecewise regular patches in the retina, e.g. of a monkey or a human. P. Meer's stochastic pyramid is such an irregular structure. The parallel generation of the structure is governed by two ``decimation rules'' that also characterize a maximal independent set on the neighborhood graph of the image pixels. In general, the number of neighbors in the decimated graph may increase. It is shown that the decimation $G'(V',E')$ of any neighborhood-graph $G(V,E)$ preserves the degrees in the corresponding dual graphs. However the dual of $G'$ is not always a ``good'' decimation of the dual of $G$. Investigating in parallel dual decimations of regular graphs, one finds unique solutions that have interesting properties for image pyramids. Besides the above theoretical motivation for irregular structures, we can find similar strutures in the retinas of monkeys (and also of humans).", }

Powered by bibtexbrowser