Image Pyramids

In this demonstration we give an introduction and examples to:

An image pyramid is a stack of successively smaller descriptions of an image. Data structures for describing an image range from arrays to graphs, dual graphs, combinatorial maps, and generalized maps. They can be divided in fixed (arrays) and variable structure (graphs, maps), and, depending on this and the reduction method, image pyramids can be regular (predefined, regular structure) and irregular (adaptable, irregular structure).

Construction of Irregular Pyramids

Irregular pyramids are constructed sequentially in a bottom-up manner using only local operations. These operations create vertical relations between the levels of the pyramid. The receptive field [BK02b, BK03b] of any vertex is the connected set of bottom level vertices that can be reached from it using the vertical relations. The higher in the pyramid, the larger the receptive field of the vertices, and thus the higher the areas on which the operations apply. This results in a gradual shift from local to global processing. Regions [BK02a] have been formally defined to associate vertices from higher levels to connected sets of vertices in the bottom level.

Bottom-up construction of irregular pyramids has been studied on dual graphs and on combinatorial maps:

Dual-graphs were used to create hierarchies relating topology and geometry [KHL06,KH04c], and study abstraction on discrete representations [Kro02]. Their structure is adapted to the processed data and they correctly encode the topology in 2D.

Combinatorial maps have been used to create combinatorial pyramids [BK03a]. We have studied the properties of their construction [BK03b], and created efficient ways of representing them (e.g. implicit encoding [BK03c]). Contraction kernels have been fitted to the combinatorial map structure and rooted kernels have been defined [MBK04]. The notion of receptive fields has been extended to combinatorial pyramids [BK03b] and the reduction of 3D complexes has been studied [IIHK06a, IIHK06b].

Properties of Pyramids

The height of a pyramid influences the length of the paths traversed along the vertical relations, and should be as short as possible - preferably logarithmic with respect to the number of vertices in the base level [HGS+02a, KS02c]. Methods like MIES and MIDES [HGS+02b, HK03b] guarantee the desired height/reduction relation. They break big contraction kernels into many small ones which can be contracted in parallel.

Height characteristics of irregular pyramids have also increased their acceptance as a model for the human visual system and as a representation suited for algorithms mimicking human performance. A study of irregular pyramids in this context has been presented in [KHPL05]. It shows the advantages of models based on irregular pyramids over the ones based on regular pyramids.

Contains and Inside Relationships within Combinatorial Pyramids [BK05, BK06] help discriminate between configurations where a simple analysis of the adjacency relations would not be enough. Orientation explicitly encoded by combinatorial maps is used to determine inside and outside of loops with only local computations.

Segmentation with Pyramids

Graphs, maps and irregular pyramids are very well suited for representing image and object segmentation. Concepts like the redundancy pyramid, applied to images [HMK04] (Figure 3) or videos [MKH04], rely on these structures.

Together with the concepts of internal and external contrast, and an algorithm for finding the Minimum Spanning Tree, a new method for image segmentation was introduced. The method was defined and studied in the framework of dual-graph pyramids [HK03d, HK04, KH04a, HK03c] and (dual-) combinatorial map pyramids [IHKB05, HIKB05] (see Figure 4). A theoretical study of its properties has been made [IKH06] which shows in a transformed space its similarity with the watershed transform. Different decimation strategies have been tried [HIK06c], and benchmarking with respect to human segmentation [HIK06a], the normalized cut [HIK06b] and other minimum spanning tree based methods [HIKI05] has been done.

Segmentation is bound to connected regions. There are many cases where broken (non-connected) elements 'belong together', e.g. dotted or dashed lines. Grouping such elements in the irregular pyramid has also been used to 'bridge the representational gap between image and model features' [KH05, KH04b].


0 (160 000)	21 (2387)	27 (321)	37 (41)	42 (9)

Some levels of the partitioning of `Tulips': level (number of components).

Matching with Pyramids

A very important step in a classical image processing system, matching, has evolved from one-to-one, to one-to-many, and finally to many-to-many. Many-to-many matching of segmentation hierarchies has been approached in [GPK02, GPK04] and applied to the matching of panoramic images [GPK03]. It is more robust than one-to-one and one-to-many but also more computationally expensive.

An efficient representation for eigenimage representations based on pyramids is shown in [LBK02].

References

[BK02a]	L. Brun and W. G. Kropatsch. Defining regions within the combinatorial pyramid framework. In Computer Vision - CVWW’02, Computer Vision Winter Workshop, pages 198 – 207, Bad Aussee, Österreich, 2002.
[BK02b]	L. Brun and W. G. Kropatsch. Receptive fields within the combinatorial pyramid framework. In Discrete Geometry for Computer Imagery, 10th DGCI, pages 92 – 101, Bordeaux, Frankreich, 2002.
[BK03a]	L. Brun and W. G. Kropatsch. Contraction kernels and combinatorial maps. Pattern Recognition Letters, 24(8):1051 – 1057, 2003.
[BK03b]	L. Brun and W. G. Kropatsch. Construction of combinatorial pyramids. In 4th IAPR-TC15Workshop on Graph-based Representation in Pattern Recognition, pages 1 – 12, 2003.
[BK03c]	L. Brun and W. G. Kropatsch. Implicite encoding of combinatorial pyramids. In Computer Vision Winter Workshop 2003, page 6, 2003.
[BK05]	L. Brun and W. G. Kropatsch. Inside and outside within combinatorial pyramids. In M. vento L. Brun, editor, 5th IAPR-TC15 Workshop on Graph-based Representation in Pattern Recognition, pages 122 – 131, 2005.
[BK06]	L. Brun and W. G. Kropatsch. Contains and inside relationships within combinatorial pyramids. Pattern Recognition, 39(4):515 – 526, 2006.
[GPK02]	R. Glantz, M. Pelillo, and W. G. Kropatsch. Matching hierarchies of segmentations. In Computer Vision - CVWW’02, Computer Vision Winter Workshop, pages 149 – 158, Bad Aussee, ¨ Osterreich, 2002.
[GPK03]	R. Glantz, M. Pelillo, and W. G. Kropatsch. Hierarchical matching of panoramic images. In 12th International Conference on Image Analysis and Processing, pages 328–333, 2003.
[GPK04]	R. Glantz, M. Pellilo, and W. G. Kropatsch. Matching segmentation hierarchies. International Journal of Pattern Recognition and Artificial Intelligence, 18, 2004.
[HGS+02a]	Y. Haxhimusa, R. Glantz, M. Saib, G. Langs, and W. G. Kropatsch. Logarithmic tapering graph pyramid. In Proceedings of 24th DAGM Symposium, pages 117 – 124, Zürich, Schweiz, 2002.
[HGS+02b]	Y. Haxhimusa, R. Glantz, M. Saib, G. Langs, and W. G. Kropatsch. Reduction factors of image pyramid on undirected and directed graph. In Proceedings of the 7th. Computer Vision Winter Workshop, pages 29 – 38, Bad Aussee, 2002.
[HIK06a]	Y. Haxhimusa, A. Ion, and W. G. Kropatsch. Comparing hierarchies of segmentations: Humans, normalized cut, and minimum spanning tree. In Digital Imaging and Pattern Recognition, pages 95 – 103, Obergurgl, 2006.
[HIK06b]	Y. Haxhimusa, A. Ion, and W. G. Kropatsch. Evaluating hierarchical graphbased segmentation. In The 18th International Conference on Pattern Recognition, pages 195 – 198, Hong Kong, 2006.
[HIK06c]	Y. Haxhimusa, A. Ion, and W. G. Kropatsch. Irregular pyramid segmentations with stochastic graph decimation strategies. In Progress in Pattern Recognition, Image Analysis and Applications, pages 277 – 286, Cancun, Mexico, 2006.
[HIKB05]	Y. Haxhimusa, A. Ion, W. G. Kropatsch, and L. Brun. Hierarchical image partitioning using combinatorial maps. In D. Chetverikov, L. Czuni, and M. Vincze, editors, Hierarchical Image Partitioning using Combinatorial Maps, pages 179 – 186, 2005.
[HIKI05]	Y. Haxhimusa, A. Ion, W. G. Kropatsch, and T. Illetschko. Evaluating minimum spanning tree based segmentation algorithms. In A. Gagalowicz and W. Philips, editors, Computer Analysis of Images and Patterns: 11th International Conference, CAIP 2005, pages 579 – 586, 2005.
[HK03b]	Y. Haxhimusa and W. G. Kropatsch. Constructing stochastic pyramids by mides - maximal independent directed set. In 4th IAPR-TC 15 Workshop on Graph based Representation in Pattern Recognition, page 11, 2003.
[HK03c]	Y. Haxhimusa and W. G. Kropatsch. Hierarchical image partitioning with graph pyramids. In Proceedings of the 25th DAGM Symposium, page 8, 2003.
[HK03d]	Y. Haxhimusa and W. G. Kropatsch. Image partitioning with graph pyramids. In Proceedings of 25th AGM Workshop, page 7, 2003.
[HK04]	Y. Haxhimusa and W. G. Kropatsch. Segmentation graph hierarchies. In Proceedings of Joint International Workshops on Structural, Syntactic, and Statistical Pattern Recognition S+SSPR 2004, pages 343 – 351, 2004.
[HMK04]	A. Hanbury, J. Marchadier, and W. G. Kropatsch. The redundancy pyramid and its application to image segmentation. In Digital Imaging in Media and Education, Proc. of the 28th Workshop of the Austrian Association for Pattern Recognition (OAGM/AAPR), pages 157 – 164, 2004.
[IHK05]	A. Ion, Y. Haxhimusa, and W. G. Kropatsch. A graph-based concept for spatiotemporal information in cognitive vision. In M. vento L. Brun, editor, 5th IAPR-TC15 Workshop on Graph-based Representation in Pattern Recognition, pages 223 – 232, 2005.
[IHKB05]	A. Ion, Y. Haxhimusa, W. G. Kropatsch, and L. Brun. Hierarchical image partitioning using combinatorial maps. In H. Bischof A. Hanbury, editor, 10th Computer Vision Winter Workshop - CVWW 2005, pages 43 – 52, 2005.
[IHKH06]	A. Ion, H. Hausegger, W. G. Kropatsch, and Y. Haxhimusa. How humans describe short videos. In Proceedings of the Second International Cognitive Vision Workshop, 2006.
[IlHKH06a]	T. Illetschko, A. Ion, Y. Haxhimusa, and W. G. Kropatsch. Collapsing 3d combinatorial maps. In Digital Imaging and Pattern Recognition, pages 85 – 93, Obergurgl, 2006.
[IlHKH06b]	T. Illetschko, A. Ion, Y. Haxhimusa, and W. G. Kropatsch. Distinguishing the 3 primitive 3d-topological configurations: Simplex, hole, tunnel. In Proceedings of the 11th Computer Vision Winter Workshop, pages 22 – 27, Telc, Czech Republik, 2006.
[IKH06]	A. Ion, W. G. Kropatsch, and Y. Haxhimusa. Considerations regarding the minimum spanning tree pyramid segmentation method. In Structural, Syntactic, and Statistical Pattern Recognition, pages 182 – 190, Hong Kong, 2006.
[KH04a]	W. G. Kropatsch and Y. Haxhimusa. Grouping and segmentation in a hierarchy. In Computational Imaging II, pages 193 – 204, 2004.
[KH04b]	W. G. Kropatsch and Y. Haxhimusa. Hierarchical grouping of non-connected structures. In Digital Imaging in Media and Education, Proc. of the 28th Workshop of the Austrian Association for Pattern Recognition (OAGM/AAPR), pages 165 – 172, 2004.
[KH04c]	W. G. Kropatsch and Y. Haxhimusa. Hierarchies relating topology and geometry. In Cognitive Vision Systems, 2004.
[KH05]	W. G. Kropatsch and Y. Haxhimusa. Grouping of non-connected structures by an irregular graph pyramid. In P. Pina J. Marques, N. de la Blanca, editor, Pattern Recognition and Image Analysis: Second Iberian Conference, IbPRIA 2005, pages 107 – 114, 2005.
[KHL06]	W. G. Kropatsch, Y. Haxhimusa, and P. Lienhardt. Cognitive Vision Systems: Sampling the Spectrum of Approaches, chapter 13. Hiearchies relating Topology and Geometry, pages 199 – 220. Springer LNCS, Berlin - Heidelberg - New York, 2006.
[KHP04]	W. G. Kropatsch, Y. Haxhimusa, and Z. Pizlo. Integral trees: Subtree depth and diameter. In Proceedings of the IWCIA 2004, pages 77 – 87, 2004.
[KHPL05]	W. G. Kropatsch, Y. Haxhimusa, Z. Pizlo, and G. Langs. Vision pyramids that do not grow too high. Pattern Recognition Letters, 26(3):319 – 337, 2005.
[KIHF06]	W. G. Kropatsch, A. Ion, Y. Haxhimusa, and T. Flanitzer. The eccentricity transform (of a digital shape). In Discrete Geometry for Computer Imagery, pages 437 – 448, Szeged, Ungarn, 2006.
[Kro02]	W. G. Kropatsch. Abstraction pyramids on discrete representations. In Discrete Geometry for Computer Imagery, 10th DGCI, pages 1 – 21, Bordeaux, Frankreich, 2002.
[Kro03]	W. G. Kropatsch. Benchmarking graph matching algorithm. Pattern Recognition Letters, 24(8):1051 – 1059, 2003.
[KS02c]	W. G. Kropatsch and M. Saib. The optimal height of a graph pyramid. InVision with Non-Traditional Sensors 26th ¨ OAGM Workshop, pages 87 – 94, Graz, Österreich, 2002.
[LBK02]	G. Langs, H. Bischof, and W. G. Kropatsch. Hierarchical top-down enhancement of robust pca. In Proceedings of IAPR Int. Workshop on Syntactical and Structural Pattern Recognition (SSPR 2002), LNCS 2396, pages 131 – 136, Windsor, Kanada, 2002.
[MBK04]	J. Marchadier, L. Brun, and W. G. Kropatsch. Rooted kernels and labeled combinatorial pyramids. In Computer Vision Winter Workshop - CVWW’04, pages 59 – 68, 2004.
[MK03b]	J. Marchadier and W. G. Kropatsch. Extraction of curve segments and junctions by graph based optimization. In Vision in a Dynamic World 27th ÖAGM Workshop, 2003.
[MKH03]	J. Marchadier, W. G. Kropatsch, and A. Hanbury. Homotopic transformation of combinatorial maps. In Discrete Geometry for Computer Imagery, pages 134 – 143, Neapel, Italy, 2003.
[MKH04]	J. Marchadier, W. G. Kropatsch, and A. Hanbury. The redundancy pyramid and its application to segmentation on an image sequence. In DAGM Symposium 2004, pages 432 – 439, 2004.
[MK03c]	J. Marchadier and W. G. Kropatsch. Functional modeling of structures images. In 4th IAPR-TC15 Workshop on Graph-Based Representation in Pattern Recognition, page 12, 2003.
[OK04]	W. Ölz and W. G. Kropatsch. Graph representation of fingerprint topology. In Computer Vision Winter Workshop- CVWW’04, pages 51 – 58, 2004.
[PSS+06]	Z. Pizlo, E. Stefanov, J. Saalweachter, Y. Haxhimusa, and W. G. Kropatsch. Traveling salesman problem: A foveating pyramid model. The Journal of Problem Solving, 1(1):83 – 101, 2006.

Contact: Mail: webmaster(at)prip.tuwien.ac.at | Tel: +43.1.58801.193301 | Fax : no longer available
2014-2020 PRIP, Impressum / Datenschutzerklärung
This page is maintained by Webmaster ( webmaster(at)prip.tuwien.ac.at ) and was last modified on 20. May 2015 12:17