@inproceedings{ion-2005, author={A. Ion, Y.; Haxhimusa, W. Kropatsch, L. Brun}, title={Hierarchical Image partitioning using Combinatorial Maps}, year={2005}, month={February}, address={Zell an der Pram, Austria}, booktitle={CVWW 2005}, theme = {hierarchical}, abstract ="We present a hierarchical partitioning of images using a pairwise similarity function on a combinatorial map based representation. We used the idea of minimal spanning tree to find region borders quickly and effortlessly in a bottom-up way, based on local differences in a color space. The result is a hierarchy of partitions with multiple resolutions suitable for further goal driven analysis. The algorithm can handle large variation and gradient intensity in images. Dual graph pyramid representations lack the explicit encoding of edge orientation around vertices i.e they lack an explicit encoding of the orientation of planes, existing in combinatorial maps. Moreover with combinatorial maps, the dual must not be explicitly represented because one map is enough to fully characterize the partition.", url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/cvww2005.pdf} } @InProceedings{CI-BRUN-2008, author = {Brun, L. and Pruvot, J.H.}, title = {Hierarchical Matching Using Combinatorial Pyramid Framework}, booktitle = {ICISP 2008}, pages = {346-355} , year = 2008, volume = 5099, address = {Cherbourg}, theme = {hierarchical}, } @INPROCEEDINGS{barchadier-04, AUTHOR = {Marchadier, Jocelyn and {B}run, Luc and {{K}ropatsch}, Walter G.}, TITLE = {Rooted kernels and Labeled Combinatorial Pyramids}, BOOKTITLE = {Computer Vision - CVWW'04, Proceedings of the Computer Vision Winter Workshop}, EDITOR = {{Leonardis}, Ale{v s} and {Solina}, Franc (eds.)}, PUBLISHER = {IEEE Slovenia Section}, ADDRESS = {Ljubljana}, YEAR = {2004}, theme = {hierarchical} abstract = "An irregular pyramid consists of a stack of successively reduced graphs. Each smaller graph is deduced from the preceding one using contraction or removal kernels. A contraction (resp. removal) kernel defines a forest of the initial (resp. dual ) graph, each tree of this forest being reduced to a single vertex (resp. dual vertex) in the reduced graph. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. We present in this article a new definition of contraction and removal kernels which allows to encode the different values attached to a given vertex, dual vertex or edge along the pyramid.", url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/cvww2004.pdf}, } @InProceedings{CI-Pruvot-2007, author = {Pruvot, Jean Hugues and Luc Brun}, title = {Scale Set representation for image segmentation}, booktitle = {Graph based Representation in Pattern Recognition'2007}, pages = {126-137}, year = 2007, editor = {Francisco Escolano and Mario Vento}, number = 4538, address = {Alicante}, month = {June}, organization = {IAPR TC15}, publisher = {LNCS}, abstract= "Segmentation algorithms based on an energy minimisation framework often depend on a scale parameter which balances a fit to data and a regularising term. Irregular pyramids are defined as a stack of graphs successively reduced. Within this framework, the scale is often defined implicitly as the height in the pyramid. However, each level of an irregular pyramid can not usually be readily associated to the global optimum of an energy or a global criterion on the base level graph. This last drawback is addressed by the scale set framework designed by Guigues. The methods designed by this author allow to build a hierarchy and to design cuts within this hierarchy which globally minimise an energy. This paper studies the influence of the construction scheme of the initial hierarchy on the resulting optimal cuts. We propose one sequential and one parallel method with two variations within both. Our sequential methods provide partitions near the global optima while parallel methods require less execution times than the sequential method of Guigues even on sequential machines.", url="article(ps):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/gbr2007.ps, slides(pdf):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/slides_gbr2007.pdf, video:=http://videolectures.net/gbr07_pruvot_hcs/", theme = {hierarchical}, } @InProceedings{CN-Brun-2006, author = {Luc Brun}, title = {Segmentation, Graphes et structures hi{'e}rarchiques}, booktitle = {ORASIS 2007}, year = 2007 address = {Obernai, France}, month = {June}, theme = {hierarchical}, url = {slide(pdf):=http://wwww.greyc.ensicaen.fr/~luc/ARTICLES/orasis2007.pdf} } @article{brun-06-1, author = {Luc Brun and Walter Kropatsch}, title = {Contains and Inside relationships within combinatorial Pyramids}, journal = {Pattern Recognition}, year = 2006, volume = 39, number = 4, pages = {515-526}, month = {April}, abstract= "Irregular pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids are used within the segmentation framework to encode a hierarchy of partitions. The different graph models used within the irregular pyramid framework encode different types of relationships between regions. This paper compares different graph models used within the irregular pyramid framework according to a set of relationships between regions. We also define a new algorithm based on a pyramid of combinatorial maps which allows to determine if one region contains the other using only local calculus.", theme = {hierarchical} } @InProceedings{brun-05, author = {Luc Brun and Myriam Mokhtari and Fernand Meyer}, title = {Hierarchical watersheds within the Combinatorial Pyramid framework}, booktitle = {Proc. of DGCI 2005}, year = 2005, organization = {IAPR-TC18}, publisher = {LNCS}, theme = {hierarchical}, url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/dgci2005.ps, slides:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/slides_dgci2005.pdf}, abstract= "Watershed is the latest tool used in mathematical morphology. The algorithms which implement the watershed transform generally produce an over segmentation which includes the right image's boundaries. Based on this last assumption, the segmentation problem turns out to be equivalent to a proper valuation of the saliency of each contour. Using such a measure, hierarchical watershed algorithms use the edge's saliency conjointly with statistical tests to decimate the initial partition. On the other hand, Irregular Pyramids encode a stack of successively reduced partitions. Combinatorial Pyramids consitute the latest model of this family. Within this framework, each partition is encoded by a combinatorial map which encodes all topological relationships between regions such as multiple boundaries and inclusion relationships. Moreover, the combinatorial pyramid framework provides a direct access to the embedding of the image's boundaries. We present in this paper a hierarchical watershed algorithm based on combinatorial pyramids. Our method overcomes the problems connected to the presence of noise both within the basins and along the watershed contours." } @InProceedings{brun-05-2, author = {Luc Brun and Walter Kropatsch}, title = {Inside and Outside within Combinatorial Pyramids}, booktitle = {5th IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition}, year = 2005, editor = {Luc Brun and Mario Vento}, series = {Lecture Notes in Computer Science}, address = {Poitiers (France)}, month = {April}, organization = {IAPR-TC15}, publisher = {Springer, Berlin Heidelberg, New York}, theme= {hierarchical}, note = {ISBN: 3-540-25270-3}, url= {springerLink:=http://www.springerlink.com/index/V6UYD78EF8CLHQQ2} abstract= "Irregular pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids are often used within the segmentation and the connected component analysis frameworks to detect meaningful objects together with their spatial and topological relationships. The graphs reduced in the pyramid may be region adjacency graphs, dual graphs or combinatorial maps. Using any of these graphs each vertex of a reduced graph encodes a region of the image. Using simple graphs one edge between two vertices encodes the existence of a common boundary between two regions. Using dual graphs and combinatorial maps, each connected boundary segment between two regions is associated to one edge. Moreover, special edges called loops may be used to differentiate a special type of adjacency where one region surrounds the other. We show in this article that the loop information does not allow to distinguish inside and outside of the loop by local computations. We provide a method based on the combinatorial pyramid framework which uses the orientation explicitly encoded by combinatorial maps to determine inside and outside with local calculus." } @InProceedings{brun-04, author = {Luc Brun and Philippe Vautrot and Fernand Meyer}, title = {Hierarchical Watersheds with Inter-pixel Boundaries}, booktitle = { Image Analysis and Recognition: International Conference ICIAR 2004, Part I}, year = 2004, pages= {840-847}, address = {Proto (Portugal)}, publisher = {Springer Verlag Heidelberg (LNCS)}, theme = {hierarchical}, abstract = "Watersheds are the latest segmentation tool developed in mathematical morphology. These algorithms produce a segmentation of an image into a set of basins separated by watershed pixels. The over segmentation produced by these algorithms is reduced by removing all contours with a low saliency. This contour's saliency is generally defined from the minimal height of the watershed pixels along the contour. However, such a definition does not allow to define a contour's saliency in case of thick watersheds. Moreover, the set of basins which corresponds to the intuitive notion of regions does not define an image partition. In this paper we propose a method which allows to aggregate the watershed pixels to the basins while preserving the notion of contour and the associated saliency. The model used to encode the image partition is then decimated according to the contour saliency to obtain a hierarchy of partitions.", url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/iciar2004.ps} } @Article{brun-02-6, author = {Luc Brun and Walter Kropatsch}, title = {Receptive Fields within the Combinatorial Pyramid Framework}, journal = {Graphical Models}, year = 2003, pages= {23-42}, volume= 65, abstract = "A hierarchical structure is a stack of successively reduced image representations. Each basic element of a hierarchical structure is the father of a set of elements in the level below. The transitive closure of this father-child relationship associates to each element of the hierarchy a set of basic elements in the base level image representation. Such a set, called a receptive field, defines the embedding of one element on the original image. Combinatorial pyramids are defined as a stack of successively reduced combinatorial maps, each combinatorial map being defined by two permutations acting on a set of half edges named darts. The basic element of a combinatorial pyramid is thus the dart. This paper defines the receptive field of each dart within a combinatorial pyramid and study the main properties of these sets.", url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/recep_field.pdf}, theme = {hierarchical} } @Article{brun-02-7, author = {Luc {B}run and Walter {K}ropatsch}, title = {Contraction Kernels and Combinatorial Maps}, journal = {Pattern Recognition Letters}, volume = {24}, number = 8, pages= {1051-1057}, year = 2003, month = {April}, abstract= "Graph pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids overcome the main limitations of their regular ancestors. The graphs used in the pyramid may be region adjacency graphs, dual graphs or combinatorial maps. Compared to usual graph data structures, combinatorial maps offer an explicit encoding of the orientation of edges around vertices. Each combinatorial map in the pyramid is generated from the one below by a set of edges to be contracted. This contraction process is controlled by kernels that can be combined in many ways. This paper shows that kernels producing a slow reduction rate can be combined to speed up reduction. Conversely, kernels decompose into smaller kernels that generate a more gradual reduction. We also propose one sequential and one parallel algorithm to compute the contracted combinatorial maps.", url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/cont_kernel_combi_maps.pdf}, theme = {hierarchical} } @InProceedings{brun-03, author = {Luc Brun and Walter Kropatsch}, title = {Implicit encoding of combinatorial Pyramids}, booktitle = {Proceedings of the Computer Vision Winter Workshop}, pages = {49-54}, year = 2003, editor = {Ondrej Drbohlav}, address = {Valtice, Czech Reublic}, month = {February}, url = { article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/cvww2003.pdf}, abstract = " An irregular pyramid consists of a stack of successively reduced graphs. Each smaller graph is deduced from the preceding one by the contraction or the removal of a set of edges. Using a fixed decimation ratio we need approximately O(log(image size)) graphs to encode the whole pyramid. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. We present in this article an encoding of a combinatorial pyramid which allows to fold the whole pyramid in the base level layer and provides at the same time a measure of the importance of every pixel. Any reduced combinatorial maps of the pyramid maybe directly retrieved from this encoding if needed.", theme = {hierarchical} } @InProceedings{brun-03-2, author = {Luc Brun and Walter Kropatsch}, title = {Construction of Combinatorial Pyramids}, booktitle = {Graph based Representations in Pattern Recognition}, pages = {1-12}, year = 2003, editor = {Edwin Hancock and Mario Vento}, volume = 2726, series = {LNCS}, address = {York, UK}, month = {June}, organization = {IAPR-TC15}, url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/gbr2003.pdf,slides:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/slides_gbr2003.pdf}, abstract = "Irregular pyramids are made of a stack of successively reduced graphs embedded in the plane. Each vertex of a reduced graph corresponds to a connected set of vertices in the level below. One connected set of vertices reduced into a single vertex at the above level is called the reduction window of this vertex. In the same way, a connected set of vertices in the base level graph reduced to a single vertex at a given level is called the receptive field of this vertex. The graphs used in the pyramid may be region adjacency graphs, dual graphs or combinatorial maps. This last type of pyramids are called Combinatorial Pyramids. Compared to usual graph data structures, combinatorial maps encode one graph and its dual within a same formalism and offer an explicit encoding of the orientation of edges around vertices. This paper describes the construction scheme of a Combinatorial Pyramid. We also provide a constructive definition of the notions of reduction windows and receptive fields within the Combinatorial Pyramid framework.", theme = {hierarchical} } @InProceedings{brun-03-1, author = {Luc Brun and Walter Kropatsch}, title = {Combinatorial Pyramids}, booktitle = {IEEE International conference on Image Processing (ICIP)}, pages = {33-37}, year = 2003, editor = {Suvisoft}, volume = {II}, address = {Barcelona}, month = {September}, organization = {IEEE}, url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/icip2003.pdf, slides:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/slides_icip2003.pdf}, abstract = "An irregular pyramid consists of a stack of successively reduced graphs. Each smaller graph is deduced from the preceding one by the contraction or the removal of a set of edges. Using a fixed decimation ratio we need approximately O(log(image size)) graphs to encode the whole pyramid. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. We present in this article an encoding of a combinatorial pyramid which allows to fold the whole pyramid in the base level layer and provides at the same time a measure of the relevance of every pixel. This encoding is used to retreive any reduced combinatorial map of the pyramid from its base and to compute the borders of the partition encoded by the combinatorial maps.", theme = {hierarchical} } @TechReport{brun-02-4, author = "Luc {B}run and Walter Kropatsch", institution ="PRIP, TU Wien", number = "PRIP-TR-yy", title = "Labeled Pyramids with Combinatorial Maps", year = 2002, theme = {hierarchical}, price = "20,-", url = {article:=ftp://www.prip.tuwien.ac.at/pub/publications/trs/tr57.ps.gz}, abstract = " Combinatorial Pyramids are defined as a stack of successively reduced combinatorial maps. The Pyramid construction plan defined in TR-63~cite{brun-00-1} allows to describe a pyramid by two functions $level$ and $state$ defined respectively on the set of darts of the initial combinatorial map and the set of levels of the pyramid. These two functions encode respectively the maximum level on which a dart survives and the type of each reduction operation. Based on these functions any combinatorial map of the pyramid may be build from the base by a one pass algorithm scanning all the darts of the initial combinatorial map~cite{brun-00-1}. In this technical report we show that algorithms with a same sequential and parallel complexity may be designed in order to build all the reduced combinatorial maps of the Pyramid." } @PhdThesis{brun-02-9, author = {Luc Brun}, title = {Traitement d'images couleur et pyramides combinatoires}, school = {Universit{'e} de Reims}, year = 2002, theme = {topologie,hierarchical,couleur,quantification,inversion}, type = {Habilitation {`a} diriger des recherches}, abstract = "We describe in this thesis three key steps of image processing algorithms. We first study the reflexion models which describe the image formation process. These models are used to obtain a segmentation of the image into materials and to reconstruct the surface of some of the regions previously segmented. The materials studded for the reconstruction stage are metallic ones. We also study quantization and inverse colormap operations. These operations are used to display an image onto low cost terminals. Such processes may also be applied into the image compression or image segmentation framework. We finally describe a new hierarchical model based on a topological representation of an image partition. The model named Combinatorial Pyramid is the only hierarchical model currently developed which allows to encode all the topological information.", url= {pdf:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/hdr.pdf,ps.gz:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/hdr.ps.gz} } @INPROCEEDINGS{brun-02-2, AUTHOR = {Luc Brun and Walter Kropatsch}, TITLE = {Receptive Fields within the Combinatorial Pyramid Framework}, BOOKTITLE = {Discrete Geometry for Computer Imagery}, PAGES = {92-101}, YEAR = 2002, EDITOR = {Achille Braquelaire and Lachaud, Jacques-Olivier and Anne Vialard}, VOLUME = 2301, SERIES = {LNCS}, ADDRESS = {Bordeaux}, theme = {hierarchical}, MONTH = {April}, PUBLISHER = {Springer-Verlag}, NOTE = {ISBN 3-540-43380-5, ISSN 0302-9743}, ABSTRACT = {A hierarchical structure is a stack of successively reduced image representations. Each basic element of a hierarchical structure is the father of a set of elements in the level below. The transitive closure of this father-child relationship associates to each element of the hierarchy a set of basic elements in the base level image representation. Such a set, called a receptive field, defines the embedding of one element of the hierarchy on the original image. Using the father-child relationship, global properties of a receptive field may be computed in $O(log(m))$ parallel processing steps where $m$ is the diameter of the receptive field. Combinatorial pyramids are defined as a stack of successively reduced combinatorial maps, each combinatorial map being defined by two permutations acting on a set of half edges named darts. The basic element of a combinatorial pyramid is thus the dart. This paper defines the receptive field of each dart within a combinatorial pyramid and studies the main properties of these sets.}, url = {article:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/dgci2002.pdf}, } @InProceedings{brun-02-3, author = {Luc Brun and Walter Kropatsch}, title = {Defining regions within the Combinatorial Pyramid framework}, booktitle = {Proceedings of the Computer Vision Winter Workshop}, pages = {198-207}, year = 2002, theme = {hierarchical}, abstract = "Irregular Pyramids are defined as a stack of successively reduced graphs. Each vertex of a reduced graph is associated to a set of vertices in the base level graph named its receptive field. If the initial graph is deduced from a planar sampling grid its reduced versions are planar and each receptive field is a region of the initial grid. Combinatorial Pyramids are defined as a stack of successively reduced combinatorial maps. Combinatorial maps are based on half edges named darts and the receptive field of a dart is a sequence of darts in the base level combinatorial map. We present in this paper preliminary results showing how to define regions from the receptive fields of the darts.", url = {article(pdf):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/cvww2002.pdf}, editor = {Horst Wildenauer and Walter Kropatsch}, address = {Bad Ausse Austria}, month = {February} } @INCOLLECTION{brun-02-1, AUTHOR = {Luc {B}run and Walter {K}ropatsch}, TITLE = {Introduction to Combinatorial Pyramids}, BOOKTITLE = {Digital and Image Geometry}, PAGES = {108-127}, PUBLISHER = {Springer Verlag}, YEAR = 2001, EDITOR = {G. Bertrand, A. Imiya, R. Klette}, VOLUME = 2243, SERIES = {LNCS}, abstract= "A pyramid is a stack of image representations with decreasing resolution. Many image processing algorithms run on this hierarchical structure in O(log(n)) parallel processing steps where n is the diameter of the input image. Graph pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids overcome the main limitations of their regular ancestors. The graphs used in the pyramid may be region adjacency graphs or dual graphs. This paper reviews the different hierarchical data structures and introduces a new representation named combinatorial pyramid.", url = {slides (ppt):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/dgi.ppt, article (pdf):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/dgi.pdf}, theme = {hierarchical} } @InProceedings{brun-01, author = {Luc {B}run and Walter {K}ropatsch}, title = {Contraction Kernels and Combinatorial Maps}, booktitle = {$3^{rd}$ IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition}, pages = {12-21}, year = 2001, editor = {{J}olion, Jean Michel and Walter Kropatsch and Mario Vento}, address = {Ischia Italy}, month = {May}, organization = {IAPR-TC15}, publisher = {CUEN}, theme = {hierarchical}, url = {slides:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/slides_gbr2001_1.ppt}, abstract = "Graph pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids overcome the main limitations of their regular ancestors. The graphs used in the pyramid may be region adjacency graphs, dual graphs or combinatorial maps. Compared to the usual graph data structures, combinatorial maps offer an explicit encoding of the orientation of edges around vertices. Each combinatorial map in the pyramid is generated from the one below by a set of edges to be contracted. This contraction process is controlled by kernels that can be combined in many ways. We show in this paper, that kernels producing a slow reduction rate can be combined to speed up reduction. Or, conversely, kernels decompose into smaller kernels that generate a more gradual reduction. We also propose one sequential and one parallel algorithm to compute the contracted combinatorial maps defined by kernels." } @TechReport{brun-00-1, author = {L. {B}run and Walter {K}ropatsch}, title = {The Construction of Pyramids with Combinatorial Maps}, institution = {Institute of Computer Aided Design}, year = 2000, number = 63, url = {article:=ftp://www.prip.tuwien.ac.at/pub/publications/trs/tr63.ps.gz}, address = {Vienna University of Technology, lstr. 3/1832,A-1040 Vienna AUSTRIA}, month = {June}, url = {http://www.prip.tuwien.ac.at/}, abstract = " This paper presents a new formalism for irregular pyramids based on combinatorial maps. This technical report continues the work begun with the TR-54 and TR-57 reports (see ~cite{brun-99-1} and~cite{brun-99-3}).We provide in this technical report algorithms allowing efficient parallel or sequential implementation of combinatorial pyramids", theme={hierarchical} } @inproceedings{brun-00, AUTHOR = {L. {B}run and {{K}ropatsch},Walter }, TITLE = {Irregular Pyramids with Combinatorial Maps}, BOOKTITLE = {Advances in Pattern Recognition, Joint IAPR International Workshops SSPR'2000 and SPR'2000}, EDITOR = {{Amin}, Adnan and {Ferri}, Francesc J. and {Pudil}, Pavel and {I~{n}esta}, Francesc J.}, PUBLISHER = {Springer, Berlin Heidelberg, New York}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {Vol.~1451}, ADDRESS = {Alicante, Spain}, YEAR = {2000}, MONTH = {August}, PAGES = {256-265}, abstract = "This paper presents a new formalism for irregular pyramids based on combinatorial maps. Such pyramid consists of a stack of successively reduced graph. Each smaller graph is deduced from the preceding one by a set of edges which have to be contracted or removed. In order to perform parallel contractions or removals, the set of edges to be contracted or removed has to verify some properties. Such a set of edges is called a Decimation Parameter. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. Combining the useful properties of both combinatorial maps and irregular pyramids offers a potential alternative for representing structures at multiple levels of abstraction.", theme={hierarchical} } @TechReport{brun-99-1, author = {Luc {B}run and Walter Kropatsch}, title = {Dual Contractions of Combinatorial Maps}, institution = {Institute of Computer Aided Design}, year = 1999, number = 54, url = {article:=ftp://www.prip.tuwien.ac.at/pub/publications/trs/tr54.ps.gz}, theme = {hierarchical}, address = {Vienna University of Technology, lstr. 3/1832,A-1040 Vienna AUSTRIA}, month = {January}, url = { http://www.prip.tuwien.ac.at/}, abstract = " This paper presents a new formalism for irregular pyramids based on combinatorial maps. The combinatorial map formalism allows us to encode a planar graph thanks to two permutations encoding the edges and the vertices of the graph.The combinatorial map formalism encode explicitly the orientation of the planar graph. This last property is useful to describe the partitions of an image which may be considered as a subset of the oriented plane $IR^2$. This new constraint allows us to design interesting properties for irregular pyramids. Finally the combinatorial formalism allows us to encode efficiently the graph transformations used in irregular pyramids." } @TechReport{brun-99-3, author = "Luc {B}run and Walter Kropatsch", institution ="PRIP, TU Wien", number = "PRIP-TR-057", title = "Pyramids with Combinatorial Maps", year = 1999, price = "20,-", theme = {hierarchical}, url = {article:=ftp://www.prip.tuwien.ac.at/pub/publications/trs/tr57.ps.gz}, abstract = "This paper presents a new formalism for irregular pyramids based on combinatorial maps. This technical report continue the work began with the TR-54 report. Definition and properties of Contraction kernels are generalized and completed. The definition and properties of Equivalent contraction kernels are also given. ", } @inproceedings{brun-99-2, AUTHOR = {L. {B}run and {K}ropatsch, Walter}, TITLE = {Dual Contraction of Combinatorial Maps}, BOOKTITLE = {$2^{nd}$ IAPR-TC-15 Workshop on Graph-based Representations}, EDITOR = {{Kropatsch},Walter and {{J}olion}, J.-M.}, PUBLISHER = {{"O}sterreichische Computer Gesellschaft}, VOLUME = {126}, ADDRESS = {Haindorf, Austria}, YEAR = {1999}, MONTH = {May}, PAGES = {145-154}, theme = {hierarchical}, url = {slides:=http://www.greyc.ensicaen.fr/~luc/ARTICLES/slides_cvww1999.ps}, abstract = "This paper presents a new formalism for irregular graph pyramids based on combinatorial maps. Such pyramids consist of a stack of successively reduced graphs. Each smaller graph is derived from the larger one in the stack by a graph transformation called dual graph contraction. The basic operations of this transformation are contraction and removal of edges. In this paper these two basic operations are translated into the formalism of combinatorial maps and should enable the construction of combinatorial pyramids. A combinatorial map encodes a planar graph by two permutations encoding the edges and their orientation around the vertices. Combining the useful properties of irregular pyramids offers a potential alternative for representing structures at multiple levels of abstraction." } @InProceedings{kropatsch-00, author = {Walter G. {K}ropatsch and Luc {B}run}, title = {Hierarchies of Combinatorial Maps}, booktitle = {CPRW'00 Proceedings}, year = 2000, editor = {Thom{'a}s Svoboda}, address = {Persl{'a}k}, month = {February}, organization = {Czech Pattern Recognition Society} , abstract = "Hierarchies of graphs can be generated by dual graph contraction. The goal is to reduce the data structure by a constant reduction factor while preserving certain image properties like connectivity. Since these graphs are typically samplings of the plane they are by definition plane. The particular embedding can be represented in different ways, e.g. a pair of dual graphs relating points and faces through boundary segments. Combinatorial maps determine the embedding by explicitely recording the orientation of edges around vertices. We summarize the formal framework which has been set up to perform dual graph contraction with combinatorial maps. Contraction is controlled by kernels that can be combined in many ways. We have shown that kernels producing a slow reduction rate can be combined to speed up reduction. Or, conversely, kernels decompose into smaller kernels that generate a more gradual reduction.", theme = {hierarchical}, url = {article(ps):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/cprw00.ps} } @InProceedings{CI-BRUN-2009, author = {Romain Goffe and Guillaume Damiand and Luc Brun}, title = {A top down construction scheme for irregular pyramids}, booktitle = {V.I.S.A.P.P.'2009}, year = 2009, series = {LNCS}, month = {February}, publisher = {Springer}, theme = {hierarchical}, note = {To be published} } @InProceedings{CI-Goffe-2009, author = {Romain {Goffe} and Guillaume {Damiand} and Luc {Brun}}, title = {Extraction of tiled top-down irregular pyramids from large images.}, booktitle = {13th International Workshop on Combinatorial Image Analysis (IWCIA'09)}, series = {Research Publishing Services}, publisher = {RPS, Singapore}, pages = {123-137}, month = {November}, year = {2009}, editor = {Petra {Wiederhold} and Reneta P. {Barneva}}, theme="hierarchical", keywords = {Irregular pyramid; Topological model; Tiled data structure; Combinatorial map;}, url = {paper(pdf):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/GoffeAl09b.pdf, slides(pdf):=http://www.greyc.ensicaen.fr/~luc/ARTICLES/slidesIWCIARomain.pdf}, abstract = {Processing large images is a common issue in the computer vision framework with applications such as satellite or microscopic images. The major problem comes from the size of those images that prevents them from being loaded globally into memory. Moreover, such images contain different information at different levels of resolution. For example, global features, such as the delimitation of a tissue, appear at low resolution whereas finer details, such as cells, can only be distinguished at full resolution. Thus, the objective of this paper is the definition of a suitable hierarchical data structure that would provide full access to all the properties of the image by representing topological information. The idea consists in transposing the notion of tile for top-down topological pyramids to control accurately the amount of memory required by the construction of our model. As a result, this paper defines the topological model of tiled top-down pyramid and proposes a construction scheme that would not depend on the system memory limitations. } } @InProceedings{yll-05, author = {Yll Haxhimusa and Adrian Ion and Kropatsch, Walter G. and Luc Brun}, title = {Hierarchical Image Partitioning using Combinatorial Maps}, booktitle = {Joint Hungarian-Austrian Conference on Image Processing and Pattern Recognition}, pages = {179--186}, year = 2005, editor = {D. Chetverikov and L. Czuni and M. Vincze}, address = {Hungary}, month = {May}, theme = {hierarchical} } @PhdThesis{TH-PRUVOT-2008, author = {Jean Hugues Pruvot}, title = {Segmentation et appariement hiÃ©rarchiques basÃ©s sur les pyramides combinatoires }, school = {UniversitÃ© de Caen Basse Normandie - ED SIMEM }, year = 2008, address= {France}, theme = {hierarchical}, url = {Phd:=http://wwww.greyc.ensicaen.fr/~luc/ARTICLES/pruvotPhd.pdf} }