|[J19] Rasterized Planar Face Complex|
Damiand G., Rossignac J.
Computer-Aided Design (CAD), to appear 2017
Abstract: We consider a Planar Face Complex (PFC). It is defined by the immersion of a planar and connected graph G, which comprises a set of vertices joined by curved edges. G decomposes the plane into faces that need not be manifold or open-regularized and may be bounded by a single loop edge. The PFC may, for example, be used to represent the complex street network of a city, the decomposition of a continent into countries, or the inhomogeneous structure made of a large set of regions of different materials possibly with internal cracks. The rasterized Planar Face Complex (rPFC) proposed here provides a compact representation of an approximation of a PFC, where the precise location of each vertex is quantized to the pixel that contains it and where the precise geometry of each curved edge is approximated by the ordered list (with possible repetitions) of the pixels traversed by (a chosen polygonal approximation of) the edge. We claim three key contributions: (1) The geometric error between a PFC and its rPFC is bounded by the pixel half-diagonal. (2) In spite of such a drastic discretization of the geometry, the rPFC captures the exact topology of the original PFC (provided that no street lies entirely inside a single pixel) and supports standard graph traversal operators that permit to walk the loop of sidewalks along the streets that bound a face, to cross a street to the opposite sidewalk, or to cross streets in order while walking around their common junction. (3) The local connectivity and order information needed to provide the above functionality is stored at each pixel using only about 4 bits per crossing. We discuss the details of this representation, our implementation of its exact construction, four possible embodiments that offer different space/time efficiency compromises, experimental results, relations between rPFC and prior solutions.
|[J18] Homology of Cellular Structures allowing Multi-Incidence|
Alayrangues S., Damiand G., Lienhardt P., Peltier S.
Discrete & Computational Geometry (DCG), Volume 54, Number 1, pages 42-77, July 2015
Abstract: This paper focuses on homology computation over ‘cellular’ structures that allow multi-incidence between cells. We deal here with combinatorial maps, more precisely chains of maps and subclasses such as maps and generalized maps. Homology computation on such structures is usually achieved by computing simplicial homology on a simplicial analog. But such an approach is computationally expensive because it requires computing this simplicial analog and performing the homology computation on a structure containing many more cells (simplices) than the initial one. Our work aims at providing a way to compute homologies directly on a cellular structure. This is done through the computation of incidence numbers. Roughly speaking, if two cells are incident, then their incidence number characterizes how they are attached. Having these numbers naturally leads to the definition of a boundary operator, which induces a homology. Hence, we propose a boundary operator for chains of maps and provide optimization for maps and generalized maps. It is proved that, under specific conditions, the homology of a combinatorial map as defined in the paper is equivalent to the homology of its simplicial analogue.
|[J17] On the complexity of Submap Isomorphism and Maximum Common Submap Problems|
Solnon C., Damiand G., de la Higuera C., Janodet J.-C.
Pattern Recognition (PR), Volume 48, Number 2, pages 302-316, February 2015
Abstract: Generalized maps describe the subdivision of objects in cells and are widely used to model 2D and 3D images. In this context, several pattern recognition tasks involve solving submap isomorphism problems (to decide if a map is included in another map) or, more generally, computing maximum common submaps (to measure the distance between two maps). Recently, we have described a polynomial-time algorithm for solving the submap isomorphism problem when the pattern map is connected. In this paper, we show that submap isomorphism is NP-complete when the pattern map is not connected. Then, we characterize the inherent difficulty of submap isomorphism with respect to the number of connected components. We show that it is Fixed-Parameter Tractable (FPT) and we give an FPT algorithm for submap isomorphism. We experimentally compare this algorithm with a state-of-the-art subgraph isomorphism algorithm for searching for patterns in an image and we show that it is both more accurate and more efficient. Finally, we study the complexity of the maximum common submap problem, and we show that it is NP-hard even though we restrict the problem to the search of common connected submaps.
|[J16] Polynomial Algorithms for Open Plane Graph and Subgraph Isomorphisms|
de la Higuera C., Janodet J.-C., Samuel E., Damiand G., Solnon C.
Theoretical Computer Science (TCS), Volume 498, pages 76-99, August 2013
Abstract: Graphs are used as models in a variety of situations. In some cases, e.g. to model images or maps, the graphs will be drawn in the plane, and this feature can be used to obtain new algorithmic results. In this work, we introduce a special class of graphs, called open plane graphs, which can be used to represent images or maps for robots: they are planar graphs embedded in the plane, in which certain faces can be removed, are absent or unreachable. We give a normal form for such graphs and prove that one can check in polynomial time if two normalised graphs are isomorphic, or if two open plane graphs are equivalent (their normal forms are isomorphic). Then we consider a new kind of subgraphs, built from subsets of faces and called patterns. We show that searching for a pattern in an open plane graph is tractable if and only if the faces are contiguous, that is, we prove that the problem is NP-complete otherwise.
|[J15] From Maximum Common Submaps to Edit Distances of Generalized Maps|
Combier C., Damiand G., Solnon C.
Pattern Recognition Letters (PRL), Volume 33, Number 15, pages 2020-2028, November 2012
Abstract: Generalized maps are widely used to model the topology of nD objects (such as images) by means of incidence and adjacency relationships between cells (vertices, edges, faces, volumes, ...). In this paper, we introduce distance measures for comparing generalized maps, which is an important issue for image processing and analysis. We introduce a first distance measure which is defined by means of the size of a largest common submap. This distance is generic: it is parameterized by a submap relation (which may either be induced or partial), and by weights to balance the importance of darts with respect to seams. We show that this distance measure is a metric. We also introduce a map edit distance, which is defined by means of a minimum cost sequence of edit operations that should be performed to transform a map into another map. We relate maximum common submaps with the map edit distance by introducing special edit cost functions for which they are equivalent. We experimentally evaluate these distance measures and show that they may be used to classify meshes.
|[J13] Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps|
Damiand G., Solnon C., de la Higuera C., Janodet J.-C., Samuel E.
Computer Vision and Image Understanding (CVIU), Volume 115, Number 7, pages 996-1010, July 2011
Abstract: Combinatorial maps describe the subdivision of objects in cells, and incidence and adjacency relations between cells, and they are widely used to model 2D and 3D images. However, there is no algorithm for comparing combinatorial maps, which is an important issue for image processing and analysis. In this paper, we address two basic comparison problems, i.e., map isomorphism, which involves deciding if two maps are equivalent, and submap isomorphism, which involves deciding if a copy of a pattern map may be found in a target map. We formally define these two problems for nD open combinatorial maps, we give polynomial time algorithms for solving them, and we illustrate their interest and feasibility for searching patterns in 2D and 3D images, as any child would aim to do when he searches Wally in Martin Handford's books.
|[J10] Tiled top-down combinatorial pyramids for large images representation|
Goffe R., Brun L., Damiand G.
International Journal of Imaging Systems and Technology (IJIST), Volume 21, Number 1, pages 28-36, March 2011
Abstract: The uprising number of applications that involve very large images with resolutions greater than 30000*30000 raises major memory management issues. Firstly, the amount of data usually prevents such images from being processed globally and therefore, designing a global image partition raises several issues. Secondly, a multi-resolution approach is necessary since an analysis only based on the highest resolution may miss global features revealed at lower resolutions. This paper introduces the tiled top-down pyramidal framework which addresses these two main constraints. Our model provides a full representation of multi-resolution images with both geometrical and topological relationships. The advantage of a top-down construction scheme is twofold: the focus of attention only refines regions of interest which results in a reduction of the amount of required memory and in a refinement process that may take into account hierarchical features from previous segmentations. Moreover, the top-down model is combined with a decomposition in tiles to provide an accurate memory bounding while allowing global analysis of large images.
|[J8] Directly Computing the Generators of Image Homology using Graph Pyramids|
Peltier S., Ion A., Kropatsch W.g., Damiand G., Haxhimusa Y.
Image and Vision Computing (IMAVIS), Volume 27, Number 7, pages 846-853, June 2009
Abstract: We introduce a method for computing homology groups and their generators of a 2D image, using a hierarchical structure i.e. irregular graph pyramid. Starting from an image, a hierarchy of the image is built, by two operations that preserve homology of each region. Instead of computing homology generators in the base where the number of entities (cells) is large, we first reduce the number of cells by a graph pyramid. Then homology generators are computed efficiently on the top level of the pyramid, since the number of cells is small, and a top down process is then used to deduce homology generators in any level of the pyramid, including the base level i.e. the initial image. The produced generators fit on the object boundaries. A unique set of generators, called the minimal set, is defined and its computation is discussed. We show that the new method produces valid homology generators and present some experimental results.
|[J7] Consistency Constraints and 3D Building Reconstruction|
Horna S., Meneveaux D., Damiand G., Bertrand Y.
Computer-Aided Design (CAD), Volume 41, Number 1, pages 13-27, January 2009
Abstract: Virtual architectural (indoor) scenes are often modeled in 3D for various types of simulation systems. For instance, some authors propose methods dedicated to lighting, heat transfer, acoustic or radio-wave propagation simulations. These methods rely in most cases on a volumetric representation of the environment, with adjacency and incidence relationships. Unfortunately, many buildings data are only given by 2D plans and the 3D needs varies from one application to another. To face these problems, we propose a formal representation of consistency constraints dedicated to building interiors and associated with a topological model. We show that such a representation can be used for: (i) reconstructing 3D models from 2D architectural plans (ii) detecting automatically geometrical, topological and semantical inconsistencies (iii) designing automatic and semi-automatic operations to correct and enrich a 2D plan. All our constraints are homogeneously defined in 2D and 3D, implemented with generalized maps and used in modeling operations. We explain how this model can be successfully used for lighting and radio-wave propagation simulations.
|[J6] Topological Model for 3D Image Representation: Definition and Incremental Extraction Algorithm|
Computer Vision and Image Understanding (CVIU), Volume 109, Number 3, pages 260-289, March 2008
Abstract: In this paper, we define the three-dimensional topological map, a model which represents both the topological and geometrical information of a three-dimensional labeled image. Since this model describes the image's topology in a minimal way, we can use it to define efficient image processing algorithms. The topological map is the last level of map hierarchy. Each level represents the region boundaries of the image and is defined from the previous level in the hierarchy, thus giving a simple constructive definition. This model is an extension of the similar model defined for 2D images. Progressive definition based on successive map levels allows us to extend this model to higher dimension. Moreover, with progressive definition, we can study each level separately. This simplifies the study of disconnection cases and the proofs of topological map properties. Finally, we provide an incremental extraction algorithm which extracts any map of the hierarchy in a single image scan. Moreover, we show that this algorithm is very efficient by giving the results of our experiments made on artificial images.
|[J3] Topological Model for Two-Dimensional Image Representation: Definition and Optimal Extraction Algorithm|
Damiand G., Bertrand Y., Fiorio C.
Computer Vision and Image Understanding (CVIU), Volume 93, Number 2, pages 111-154, February 2004
Abstract: In this paper, we define the two-dimensional topological map, a model which represents both topological and geometrical information of a two-dimensional labeled image. Since this model is minimal, complete, and unique, we can use it to define efficient image processing algorithms. The topological map is the last level of a map hierarchy. Each level represents the region boundaries of the image and is defined from the previous one in the hierarchy, thus giving a simple constructive definition. This model is similar to two existing structures but the main innovation of our approach is the progressive definition based on the successive map levels. These different maps can easily be extended in order to define the topological map in any dimension. Furthermore we provide an optimal extraction algorithm which extracts the different maps of the hierarchy in a single image scan. This algorithm is based on local configurations called precodes. Due to our constructive definition, different configurations are factorized which simplifies the implementation.
|[C55] An automatic comparison approach to detect errors on 3D city models|
Gorszczyk B., Damiand G., Servigne S., Diakité A. A., Gesquière G.
Proc. of 4th Eurographics Workshop on Urban Data Modelling and Visualisation (UDMV), pages 25-30, July 2016, Liège, Belgium
Abstract: 3D building models are needed in several professional domains. To provide better results, these models must be errors-free and that is why it is required to have a way to detect and to correct errors. These errors can be geometric, topological or semantic. By using a topological structure called EBM-LCC that allows to model buildings, we create a new tool that allows to detect these three type of errors in 3D city models. The solution we propose is an algorithm that compares two EBM-LCC. This algorithm can be used to compare two different models, for example acquired with two different processes, or resulting from two different acquisition campaigns. It is also an interesting tool to compare and validate algorithms. In this work, we compare an EBM-LCC loaded directly from a CityGML model with an EBM-LCC reconstructed from a soup of polygons only. Then we can use the result of this comparison to outline possible differences or to correct one of the two models by using the information of the other one. This algorithm allowed to automatically detect and correct semantic errors on several models that are currently used by professionals. This shows the interest of EBM-LCC for the city modeling domain as it helps to reach an error-free model.
|[C54] New Mass Spring System formulation to model the behavior of soft tissues|
Golec K., Zara F., Nicolle S., Palierne J.-F., Damiand G.
Proc. of 22nd European Society of Biomechanics Congress (ESB), July 2016, Lyon, France
Abstract: Computer-based medicine has been largely developed in recent years for helping surgery, diagnosis and treatment. Unfortunately, from a mechanical standpoint, modeling complex materials such as soft tissues is still a challenge requiring accuracy and possibility of user interaction. Among computational models (such as Finite Element Method, or Position Based Dynamics), we chose the Mass-Spring System (MSS) as model. It offers several advantages, like adaptability and fast computation, while allowing topological modifications (like cutting or piercing) without pre-computations. In this paper we present a new MSS formulation for soft tissue simulations. The validation of the mechanical response of the model is based on work of Nicolle et al. which reported the shear behavior of three vital internal organs (kidney, liver and spleen). Our method is based on a topological-physical model called TopoSim which allows to easily implement different physical models and performs fast and accurate modeling of different kinds of tissues. Thanks to this model, we are able to easily adapt the simulation to desired requirements and to perform topological modifications during simulations if necessary.
|[C53] Parallel Homology Computation of Meshes|
Damiand G., Gonzalez-Diaz R.
Proc. of 6th International Workshop on Computational Topology in Image Context (CTIC), Lecture Notes in Computer Science 9667, pages 53-64, June 2016, Marseille, France
Abstract: In this paper, we propose a method to compute, in parallel, the homology groups of closed meshes (i.e., orientable 2D manifolds without boundary) represented by combinatorial maps. Our experiments illustrate the interest of our approach which is really fast on big meshes and which obtains good speed-up when increasing the number of threads.
|[C52] Combining Geometry, Topology and Semantics for Generic Building Description and Simulations|
Horna S., Damiand G., Diakité A. A., Meneveaux D.
Proc. of 3rd Eurographics Workshop on Urban Data Modelling and Visualisation (UDMV), Eurographics Digital Library, pages 13-18, November 2015, Delft, the Netherlands
Abstract: 2D and 3D virtual architectural models are the common ground of many studies, including environmental protection, energy saving, or human well-being. Building or urban environment simulations concern for instance heat transfer, lighting, and acoustics, each of them requiring physical parameters additionally to the geometric representation. Furthermore, geometry does not generally comply straightforwardly with physical parameters and users are forced to manually adapt the models before simulation. This paper proposes an overview of modeling and simulation studies that make use of topological representations, and discusses the advantages of a topological representation for various types of applications. Such a representation can be used not only to maintain the 3D model global coherence, but also to automatically retrieve walls, doors, or room volumes for instance. Based on the existing model of generalized maps, this paper also illustrates some examples of structure traversal that can be used for providing the users with adequate simulation data.
|[C50] Improvement of a Topological-Physical Model to manage different physical simulations|
Golec K., Coquet M., Zara F., Damiand G.
Proc. of 23rd International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), WSCG Full papers proceedings, pages 25-34, June 2015, Plzen, Czech Republic
Abstract: We present an improvement of a unified topological-physical model which permits topological modifications during physical simulation of soft tissues. Our improvement makes the model more generic, efficient and simpler to update. The main principle of our improvement is to associate information to elements of the model, depending on the underlying physical model. Our modification of the architecture enables to easily integrate different physical models. Moreover, topological operations and physical simulations can be factorized between the different physical models. Our solution is more efficient as it leads to simpler modification algorithms after topological alterations with less changes to apply. In this paper, we present our new solution and illustrate its new properties thanks to several experiments performed on two well-known physical models: Mass-Spring System and Tensor-Mass model. The results present a comparison of our solution with the previous one for the cutting topological operation. Moreover, as our model permits to easily compare several physical models, we performed some simulations to reproduce experiments made on real tissues.
|[C49] Automatic Semantic Labelling of 3D Buildings Based on Geometric and Topological Information|
Diakité A. A., Damiand G., Gesquière G.
Proc. of 9th International 3DGeoInfo Conference (3DGeoInfo), 3DGeoInfo conference proceedings series, pages 49-63, November 2014, Dubai, United Arab Emirates
Abstract: The lack of suitable information in 3D models of buildings and cities is still a strong limitation for the increasing number of applications requiring the 3D data. The latter are often obtained from acquisition or modeling processes during which the geometry is well preserved, but the topological and semantic information are lost. We present a new approach to enrich a purely geometric model with topological information. The reconstructed topology combined to the geometry is helpful to several operations like guided building simplification, model correction, etc. In this work we recover the semantic information based on a propagation approach guided by heuristic rules. All the process is automatic and designed such that any user can bring and customize as many rules as needed to supervise the semantic labelling. As example we propose few rules applied to both Building Information Models (BIM) and 3D Geometric Information Systems (GIS) data.
|[C48] A Generic Implementation of dD Combinatorial Maps in CGAL|
Damiand G., Teillaud M.
Proc. of 23rd International Meshing Roundtable (IMR), Procedia Engineering 82, pages 46-58, October 2014, London, United Kingdom
Abstract: We present a generic implementation of dD combinatorial maps and linear cell complexes in Cgal, the Computational Geometry Algorithms Library. A combinatorial map describes an object subdivided into cells; a linear cell complex describes the linear geometry embedding of such a subdivision. In this paper, we show how generic programming and new techniques recently introduced in the C++11 standard allow a fully generic and customizable implementation of these two data structures, while maintaining optimal memory footprint and direct access to all information. We compare our implementation with existing 2D and 3D libraries implementing cellular structures, and illustrate its usage by two applications. To the best of our knowledge, the Cgal software package presented here offers the only available generic implementation of combinatorial maps in any dimension.
|[C47] A Unified Topological-Physical Model for Adaptive Refinement|
Fléchon E., Zara F., Damiand G., Jaillet F.
Proc. of 11th Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS), Eurographics Digital Library, pages 39-48, September 2014, Bremen, Germany
Abstract: In Computer Graphics, physically-based simulation of deformable objects is a current challenge, and many efficient models have been developed to reach real-time performance. However, these models are often limited when complex interactions involving topological modifications are required. To overcome this, the key issue is to manage concurrently, and at minimal cost, both the topology and physical properties. Thus, this paper presents a unified topological-physical model for soft body simulation. The complete embedding of physical and topological models will facilitate operations like piercing, fracture or cutting, as well as adaptive refinement. Indeed, the difficulty is to treat topological changes during the simulation, requiring combined geometric and physics considerations. Rigorous topological operations guarantee the validity of the mesh, while direct access to the adjacent and incident relations will ease the update of physical properties of new elements created during these operations. These features are illustrated on an embedded mass-spring system undergoing topological modifications performed during simulation. Different levels of subdivision are also presented.
|[C44] Topological Reconstruction of Complex 3D Buildings and Automatic Extraction of Levels of Detail|
Diakité A. A., Damiand G., Van Maercke D.
Proc. of 2nd Eurographics Workshop on Urban Data Modelling and Visualisation (UDMV), Eurographics Digital Library, pages 25-30, April 2014, Strasbourg, France
Abstract: This paper describes a new method allowing to retrieve the indoor and outdoor topology of a detailed 3D building model from its geometry and to extract different levels of detail (LoD) from the ersulting topological description. No prior information about the initial model, except its geometric information is needed as input, and using the combinatorial maps data structure, the method recovers the topological information of the identified parts of the building. The topology is needed for most of the applications using 3D building models after the architects design it. While classical models available are mainly furnished in a Boundary Representation (B-Rep) format, we discuss how to recover the components that allow to distinguish the several parts of the building (defined as volumes) then the spatial relationships linking them.
|[C43] Constructing an n-dimensional cell complex from a soup of (n-1)-dimensional faces|
Arroyo Ohori K., Damiand G., Ledoux H.
Proc. of 1st International Conference on Applied Algorithms (ICAA), Lecture Notes in Computer Science 8321, pages 37-48, January 2014, Kolkata, India
Abstract: There is substantial value in the use of higher-dimensional (>3D) digital objects in GIS that are built from complex real-world data. This use is however hampered by the difficulty of constructing such objects. In this paper, we present a dimension independent algorithm to build an n-dimensional cellular complex with linear geometries from its isolated (n-1)-dimensional faces represented as combinatorial maps. It does so by efficiently finding the common (n-2)-cells (ridges) along which they need to be linked. This process can then be iteratively applied in increasing dimension to construct objects of any dimension. We briefly describe combinatorial maps, present our algorithm using them as a base, and show an example using 2D, 3D and 4D objects which was verified to be correct, both manually and using automated methods.
|[C42] A generic topological framework for physical simulation|
Fléchon E., Zara F., Damiand G., Jaillet F.
Proc. of 21th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), WSCG Full papers proceedings, pages 104-113, June 2013, Plzen, Czech Republic
Abstract: This paper presents the use of a topological model to simulate a soft body deformation based on a Mass-Spring System. We provide a generic framework which can integrate any kind of geometrical meshes (hexahedral or tetrahedral elements), using several numerical integration schemes (Euler semi-implicit or implicit). This framework naturally allows topological changes in the simulated object during the animation. Our model is based on the 3D Linear Cell Complex topological model (itself based on a 3D combinatorial map), adding the extra information required for simulation purposes. Moreover, we present some adaptations performed on this data structure to fit our simulation requirements, and to allow efficient cutting or piercing in a 3D object.
|[C41] Map Edit Distance vs Graph Edit Distance for Matching Images|
Combier C., Damiand G., Solnon C.
Proc. of 9th Workshop on Graph-Based Representation in Pattern Recognition (GBR), Lecture Notes in Computer Science 7877, pages 152-161, May 2013, Vienna, Austria
Abstract: Generalized maps are widely used to model the topology of nD objects (such as 2D or 3D images) by means of incidence and adjacency relationships between cells (0D vertices, 1D edges, 2D faces, 3D volumes, ...). Recently, we have introduced a map edit distance. This distance compares maps by means of a minimum cost sequence of edit operations that should be performed to transform a map into another map. In this paper, we introduce labelled maps and we show how the map edit distance may be extended to compare labeled maps. We experimentally compare our map edit distance to the graph edit distance for matching regions of different segmentations of a same image.
|[C40] On the complexity of Submap Isomorphism|
Solnon C., Damiand G., De La Higuera C., Janodet J.-C.
Proc. of 9th Workshop on Graph-Based Representation in Pattern Recognition (GBR), Lecture Notes in Computer Science 7877, pages 21-30, May 2013, Vienna, Austria
Abstract: Generalized maps describe the subdivision of objects in cells, and incidence and adjacency relations between cells, and they are widely used to model 2D and 3D images. Recently, we have defined submap isomorphism, which involves deciding if a copy of a pattern map may be found in a target map, and we have described a polynomial time algorithm for solving this problem when the pattern map is connected. In this paper, we show that submap isomorphism becomes NP-complete when the pattern map is not connected, by reducing the NP-complete problem Planar-4 3-SAT to it.
|[C38] Frequent Submap Discovery|
Gosselin S., Damiand G., Solnon C.
Proc. of 22nd Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science 6661, pages 429-440, June 2011, Palermo, Italy
Abstract: Combinatorial maps are nice data structures for modeling the topology of nD objects subdivided in cells (e.g., vertices, edges, faces, volumes, ...) by means of incidence and adjacency relationships between these cells. In particular, they can be used to model the topology of plane graphs. In this paper, we describe an algorithm, called mSpan, for extracting patterns which occur frequently in a database of maps. We experimentally compare mSpan with gSpan on a synthetic database of randomly generated 2D and 3D maps. We show that gSpan does not extract the same patterns, as it only considers adjacency relationships between cells. We also show that mSpan exhibits nicer scale-up properties when increasing map sizes or when decreasing frequency.
|[C37] Combining Topological Maps, Multi-Label Simple Points, and Minimum-Length Polygons for Efficient Digital Partition Model|
Damiand G., Dupas A., Lachaud J.-O.
Proc. of 14th International Workshop on Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science 6636, pages 56-69, May 2011, Madrid, Spain
Abstract: Deformable models have shown great potential for image segmentation. They include discrete models whose combinatorial formulation leads to efficient and sometimes optimal minimization algorithms. In this paper, we propose a new discrete framework to deform any partition while preserving its topology. We show how to
combine the use of multi-label simple points, topological maps and minimum-length polygons in order to implement an efficient digital deformable partition model. Our experimental results illustrate the
potential of our framework for segmenting images, since it allows the mixing of region-based, contour-based and regularization energies, while keeping the overall image structure.
|[C36] Measuring the Distance of Generalized Maps|
Combier C., Damiand G., Solnon C.
Proc. of 8th Workshop on Graph-Based Representation in Pattern Recognition (GBR), Lecture Notes in Computer Science 6658, pages 82-91, May 2011, Münster, Germany
Abstract: Generalized maps are widely used to model the topology of nD objects (such as images) by means of incidence and adjacency relationships between cells (vertices, edges, faces, volumes, ...). In this paper, we define a first error-tolerant distance measure for comparing generalized maps, which is an important issue for image processing and analysis. This distance measure is defined by means of the size of a largest common submap, in a similar way as a graph distance measure may be defined by means of the size of a largest common subgraph. We show that this distance measure is a metric, and we introduce a greedy randomized algorithm which allows us to efficiently compute an upper bound of it.
|[C35] Tiled Top-Down Pyramids and Segmentation of Large Histological Images|
Goffe R., Brun L., Damiand G.
Proc. of 8th Workshop on Graph-Based Representation in Pattern Recognition (GBR), Lecture Notes in Computer Science 6658, pages 255-264, May 2011, Münster, Germany
Abstract: Recent microscopic imaging systems such as whole slide scanners provide very large (up to 18GB) high resolution images. Such amounts of memory raise major issues that prevent usual image representation models from being used. Moreover, using such high resolution images, global image features, such as tissues, does not clearly appear at full resolution. Such images contain thus different hierarchical information at different resolutions. This paper presents the model of tiled top-down pyramids which provides a framework to handle such images. This model encodes a hierarchy of partitions of large images defined at different resolutions. We also propose a generic construction scheme of such pyramids whose validity is evaluated on an histological image application.
|[C34] A Causal Extraction Scheme in Top-Down Pyramids for Large Images Segmentation|
Goffe R., Damiand G., Brun L.
Proc. of 13th International Workshop on Structural and Syntactic Pattern Recognition (SSPR), Lecture Notes in Computer Science 6218, pages 264-274, August 2010, Cesme, Izmir, Turkey
Abstract: Applicative fields based on the analysis of large images must deal with two important problems. First, the size in memory of such images usually forbids a global image analysis hereby inducing numerous problems for the design of a global image partition. Second, due to the high resolution of such images, global features only appear at low resolutions and a single resolution analysis may loose important information. The tiled top-down pyramidal model has been designed to solve this two major challenges. This model provides a hierarchical encoding of the image at single or multiple resolutions using a top-down construction scheme. Moreover, the use of tiles bounds the amount of memory required by the model while allowing global image analysis. The main limitation of this model is the splitting step used to build one additional partition from the above level. Indeed, this step requires to temporary refine the split region up to the pixel level which entails high memory requirements and processing time. In this paper, we propose a new splitting step within the tiled top-down pyramidal framework which overcomes the previously mentioned limitations.
|[C32] Extraction of tiled top-down irregular pyramids from large images|
Goffe R., Damiand G., Brun L.
Proc. of 13th International Workshop on Combinatorial Image Analysis (IWCIA), Research Publishing Services, pages 123-137, November 2009, Cancun, Mexico
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.
|[C30] Border Operator for Generalized Maps|
Alayrangues S., Peltier S., Damiand G., Lienhardt P.
Proc. of 15th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 5810, pages 300-312, September 2009, Montréal, Canada
Abstract: In this paper, we define a border operator for the generalized maps, a data structure for representing cellular quasi-manifolds. The interest of this work lies in the optimization of homology computation, by using a model with less cells than models in which cells are regular ones as tetrahedra and cubes. For instance, generalized maps have been used for representing segmented images. We first define a face operator to retrieve the faces of any cell, then deduce the border operator and prove that it satisfies the required property : border of border is void. At last, we study the links between the cellular homology defined from our border operator and the classical simplicial homology.
|[C29] Homology Computation on Cellular Structures in Image Context|
Alayrangues S., Damiand G., Fuchs L., Lienhardt P., Peltier S.
Proc. of 2nd International Workshop on Computational Topology in Image Context (CTIC), pages 19-28, August 2009, St. Kathrein/Offenegg, Austria
Abstract: During the previous decade, many works have shown that topological properties are of interest in an image context. Among all topological invariants (Euler characteristic, Betti numbers, orientability...), homology groups are known to be powerful (in term of topological characterization) and computable in the same way in any dimension. In this paper, we recall briefly the cellular structures used in topology-based geometric modeling and image analysis, and propose different approaches for computing homology on such structures. These approaches are adaptations of classical methods from algebraic topology that had essentially been developed for simplicial or cubical complexes. We present two works in progress dealing with two different methods for computing homology information on structures derived from combinatorial maps: a method relying on the definition of a cellular border operator, the other following a constructive approach based on the works about effective homology.
|[C27] Polynomial Algorithm for Submap Isomorphism: Application to Searching Patterns in Images|
Damiand G., De La Higuera C., Janodet J.-C., Samuel E., Solnon C.
Proc. of 7th Workshop on Graph-Based Representation in Pattern Recognition (GBR), Lecture Notes in Computer Science 5534, pages 102-112, May 2009, Venice, Italy
Abstract: In this paper, we address the problem of searching for a pattern in a plane graph, i.e., a planar drawing of a planar graph. To do that, we propose to model plane graphs with 2-dimensional combinatorial maps, which provide nice data structures for modelling the topology of a subdivision of a plane into nodes, edges and faces. We define submap isomorphism, we give a polynomial algorithm for this problem, and we show how this problem may be used to search for a pattern in a plane graph. First experimental results show the validity of this approach to efficiently search for patterns in images.
|[C20] Insertion and Expansion Operations for n -Dimensional Generalized Maps|
Baba-Ali M., Damiand G., Skapin X., Marcheix D.
Proc. of 14th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 4992, pages 141-152, April 2008, Lyon, France
Abstract: Hierarchical representations, as irregular pyramids, are the bases of several applications in the field of discrete imagery. So, n-dimensional "bottom-up" irregular pyramids can be defined as stacks of successively reduced n-dimensional generalized maps (n-G-maps) , each n-G-map being defined from the previous level by using removal and contraction operations defined in . Our goal is to build a theoretical framework for the definition and handling of n-dimensional "top-down" irregular pyramids. To do that, we propose in this paper to study the definition of insertion and expansion operations that allows to conceive this kind of pyramids.
|[C19] Computing Homology Generators for Volumes using Minimal Generalized Maps|
Damiand G., Peltier S., Fuchs L.
Proc. of 12th International Workshop on Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science 4958, pages 63-74, April 2008, Buffalo, NY, USA
Abstract: In this paper, we present an algorithm for computing efficiently homology generators of 3D subdivided orientable objects which can contain tunnels and cavities. Starting with an initial subdivision, represented with a generalized map where every cell is a topological ball, the number of cells is reduced using simplification operations (removal of cells), while preserving homology. We obtain a minimal representation which is homologous to the initial object. A set of homology generators is then directly deduced on the simplified 3D object.
|[C17] A New Contour Filling Algorithm Based on 2D Topological Map|
Damiand G., Arrivault D.
Proc. of 6th Workshop on Graph-Based Representations in Pattern Recognition (GBR), Lecture Notes in Computer Science 4538, pages 319-329, June 2007, Alicante, Spain
Abstract: In this paper, we present a topological algorithm which allows to fill contours images. The filling problem has been widely treated and it recently appeared that it can always be split into two different process : a generic topological process and a dedicated geometrical post-processing which depends on the application. Our algorithm, based on a 2D topological map description of the image, addresses the first step of processing. It is fast, generic and robust. Moreover, the complete topological description allows to easily integrate geometrical constrains and makes our approach an interesting basis for every filling process.
|[C16] Computing Homology Group Generators of Images Using Irregular Graph Pyramids|
Peltier S., Ion A., Haxhimusa Y., Kropatsch W.g., Damiand G.
Proc. of 6th Workshop on Graph-Based Representations in Pattern Recognition (GBR), Lecture Notes in Computer Science 4538, pages 283-294, June 2007, Alicante, Spain
Abstract: We introduce a method for computing homology groups and their generators of a 2D image, using a hierarchical structure i.e. irregular graph pyramid. Starting from an image, a hierarchy of the image is built, by two operations that preserve homology of each region. Instead of computing homology generators in the base where the number of entities (cells) is large, we first reduce the number of cells by a graph pyramid. Then homology generators are computed efficiently on the top level of the pyramid, since the number of cells is small, and a top down process is then used to deduce homology generators in any level of the pyramid, including the base level i.e. the initial image. We show that the new method produces valid homology generators and present some experimental results.
|[C15] Building 3D Indoor Scenes Topology from 2D Architectural Plans|
Horna S., Damiand G., Meneveaux D., Bertrand Y.
Proc. of 2nd International Conference on Computer Graphics Theory and Applications (GRAPP), pages 37-44, March 2007, Barcelona, Spain
Abstract: This paper presents a new method for reconstructing geometry and topology of 3D buildings from 2D architectural plans. A complete topological model expresses incidence and adjacency relations between all the elements. It is necessary for both recovering accurately 2D information and constructing a coherent 3D building. Based on an existing topological kernel, several high-level operations have been developped in 2D for creating walls, portals, stairs, etc. Semantic information is associated with all volumes for specifying openings, walls, rooms, stairs, facade, etc. The resulting 2D model is extruded for generating a 3D environment, taking the semantic information into account since doors are not processed as walls for instance. Floors are superimposed using volumes corresponding to upper and lower ceilings linked according to stairways. The resulting models are suitable for various application such as walkthrough, lighting/wave propoagation/thermal simulation.
|[C14] Computing Homology for Surfaces with Generalized Maps: Application to 3D Images|
Damiand G., Peltier S., Fuchs L.
Proc. of 2nd International Symposium on Visual Computing (ISVC), Lecture Notes in Computer Science 4292, pages 235-244, November 2006, Lake Tahoe, Nevada, USA
Abstract: In this paper, we present an algorithm which allows to compute efficiently generators of the first homology group of a closed surface, orientable or not. Starting with an initial subdivision of a surface, we simplify it to its minimal form (minimal refers to the number of cells), while preserving its homology. Homology generators can thus be directly deduced from the minimal representation of the initial surface. Finally, we show how this algorithm can be used in a 3D labelled image in order to compute homology of each region described by its boundary.
|[C13] Generalized Map Pyramid for Multi-level 3D Image Segmentation|
Simon C., Damiand G.
Proc. of 13th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 4245, pages 530-541, October 2006, Szeged, Hungary
Abstract: Graph pyramids are often used to represent an image with various levels of details. Generalized pyramids have been recently defined in order to deal with images in any dimension. In this work, we show how to use generalized pyramids to represent 3D multi-level segmented images. We show how to construct such a pyramid, by alternating segmentation and simplification steps. We present how cells to be removed are marked: by using an homogeneous criterion to mark faces and the cell degree to mark other cells. When the pyramid is constructed, the main problem consists in retrieving information on regions. In this work, we show how to retrieve two types of information. The first one is the low level cells that are merged into a unique high level cell. The second one is the inter-voxel cells that compose a given region.
|[C12] Topological Map: An Efficient Tool to Compute Incrementally Topological Features on 3D Images|
Damiand G., Peltier P., Fuchs L., Lienhardt P.
Proc. of 11th International Workshop on Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science 4040, pages 1-15, June 2006, Berlin, Germany
Abstract: In this paper, we show how to use the three dimensional topological map in order to compute efficiently topological features on objects contained in a 3D image. These features are useful for example in image processing to control operations or in computer vision to characterize objects. Topological map is a combinatorial model which represents both topological and geometrical information of a three dimensional labeled image. This model can be computed incrementally by using only two basic operations: the removal and the fictive edge shifting. In this work, we show that Euler characteristic can be computed incrementally during the topological map construction. This involves an efficient algorithm and open interesting perspectives for other features.
|[C11] Receptive Fields for Generalized Map Pyramids: The Notion of Generalized Orbit|
Simon C., Damiand G., Lienhardt P.
Proc. of 12th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 3429, pages 56-67, April 2005, Poitiers, France
Abstract: A pyramid of n-dimensional generalized maps is a hierarchical data structure. It can be used, for instance, in order to represent an irregular pyramid of n-dimensional images. A pyramid of generalized maps can be built by successively removing and/or contracting cells of any dimension. In this paper, we define generalized orbits, which extend the classical notion of receptive fields. Generalized orbits allow to establish the correspondence between a cell of a pyramid level and the set of cells of previous levels, the removal or contraction of which have led to the creation of this cell. In order to define generalized orbits, we extend, for generalized map pyramids, the notion of connecting walk defined by Brun and Kropatsch.
|[C9] Using 2D Topological Map Information in a Markovian Image Segmentation|
Damiand G., Alata O., Bihoreau C.
Proc. of 11th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 2886, pages 288-297, November 2003, Naples, Italy
Abstract: Topological map is a mathematical model of labeled image representation which contains both topological and geometrical information. In this work, we use this model to improve a Markovian segmentation algorithm. Image segmentation methods based on Markovian assumption consist in optimizing a Gibbs energy function. This energy function can be given by a sum of potentials which could be based on the shape or the size of a region, the number of adjacencies,... and can be computed by using topological map. In this work we propose the integration of a new potential: the global linearity of the boundaries, and show how this potential can be extracted from the topological map. Moreover, to decrease the complexity of our algorithm, we propose a local modification of the topological map in order to avoid the reconstruction of the entire structure.
|[C6] Geometrical and Topological Informations for Image Segmentation with Monte Carlo Markov Chain Implementation|
Bourdon P., Alata O., Damiand G., Olivier C., Bertrand Y.
Proc. of 15th International Conference on Vision Interface (VI), pages 413-420, May 2002, Calgary, Alberta, Canada
Abstract: Image segmentation methods based on Markovian assumption consist in optimizing a Gibbs energy function which depends on the observation field and the segmented field. This energy function can be represented as a sum of potentials defined on cliques which are subsets of the grid of sites. The Potts model is the most commonly used to represent the segmented field. However, this model only expresses a potential on classes for nearest neighbor pixels. In this paper, we propose the integration of global informations, like the size of a region, in the local potentials of the Gibbs energy. To extract these informations, we use a representation model well known in geometric modeling: the topological map. Results on synthetic and natural images are provided, showing improvements in the obtained segmented fields.
|[C5] Topological Map Based Algorithms for 3D Image Segmentation|
Damiand G., Resch P.
Proc. of 10th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 2301, pages 220-231, April 2002, Bordeaux, France
Abstract: One of the most commonly used approach to segment a 2D image is the split and merge approach. In this paper, we are defining these two operations in 3D within the topological maps framework. This mathematic model of regions segmented image representation allows us to define these algorithms in a local and generic way. Moreover, we are defining a new operation, the corefining, which allows to treat big images. They are cut into small units, treated separately, then the result of each of them are combined to reconstruct the final representation. These three operations let us view efficient 3D segmentation algorithms, which is a difficult problem due to the size of data to treat.
|[C2] Latest Developments and Results in Automatic SCF Counting. Part II: Improved Image Acquisition and Results Obtained|
Gourlot J.P, Héquet E., Giner M., Ahronovitz E., Hugon M., Damiand G.
Proc. of Beltwide Cotton Conferences (BCC), pages 1522-1524, January 1998, San Diego, CA, USA
Abstract: The Trashcam project developed a rapid, automated method used to evaluate the seed coat fragment (SCF) potential of fibers from new cotton plant lines. A camera is used to acquire an image of the fiber web and this is then analyzed by image processing. The latest version of the product, has improved image quality by using a scanner for image acquisition. We compare the automated counts obtained with counts made by an 'expert' in 166 cotton web images. Thanks to the new image acquisition technique and an algorithm whose parameters may be adjusted, the results obtained show that the square root of the automated counts are proportional to the square root of the visual counts. The relationship between the two counts obtained in the context of varietal improvement Bars was: square root of automated count = 1.00 square root of the visual count (r=0.965).
|[C1] Latest Developments and Results in Automatic SCF Counting|
Giner M., Gourlot J.P., Bachelier B., Ahronovitz E., Hugon M., Damiand G.
Proc. of Beltwide Cotton Conferences (BCC), pages 1633-1637, January 1997, New-Orleans, Louisiana, USA
Abstract: Different image-processing methods were used to count seed coat fragments (SCF) in cotton fiber webs. The results obtained showed that, similar to SCF detection on yarn, it is possible to use this technique to prdict the 'SCF potential' of lines during varietal improvement programs. The last method was tested on 440 images derived from carded cottons of various geographic origins. Counts obtained automatically by the analysis of images acquired by a camera were similar to SCF counts made visually by an 'expert'; the relationship between the two counts being: square root of the automated count = 0.867* square root of the visual count + 0.393 (r=0.957).
|[T3] Contributions aux Cartes Combinatoires et Cartes Généralisées :
Simplification, Modèles, Invariants Topologiques et Applications|
Habilitation à Diriger des Recherches, Lyon 1 University, 23 September 2010
Abstract: Ce mémoire résume nos principales contributions aux cartes combinatoires et cartes généralisées, deux modèles combinatoires représentant des subdivisions d'objets en cellules (sommets, arêtes, faces, volumes, ...). Ces modèles possèdent plusieurs avantages qui justifient leurs utilisations dans plusieurs domaines comme la modélisation géométrique et l'analyse d'images : ils sont définis en dimension quelconque à partir d'un seul type d'élément ; ils décrivent les cellules de la subdivision ainsi que toutes les relations d'adjacence et d'incidence entre ces cellules ; des contraintes de cohérence permettent de tester la validité des objets manipulés ; ils autorisent la mise en oeuvre d'algorithmes locaux, qui sont simples et efficaces en complexité. Nos travaux portent sur l'étude de ces modèles et sur la définition d'algorithmes. Nous avons tout d'abord défini quatre opérations de base : la suppression, la contraction, l'insertion et l'éclatement. Ces opérations sont les briques de base permettant de modifier un objet et peuvent être vues comme une généralisation des opérateurs d'Euler. Elles sont définies de manière générale en dimension quelconque. Il est ensuite possible d'ajouter des contraintes supplémentaires selon les applications et selon les propriétés spécifiques à conserver. Ces opérations sont au coeur de nos travaux. Nous les avons utilisées pour définir la carte topologique 2D et 3D, un modèle décrivant la partition d'une image en régions, puis pour définir des opérations de fusion et de découpe sur les cartes topologiques. Nous avons également défini les pyramides généralisées qui peuvent être vues comme des piles de cartes, chacune étant obtenue par simplification de la carte précédente. Enfin, nous avons proposé des algorithmes de calcul d'invariants topologiques : la caractéristique d'Euler-Poincaré, le schéma polygonal canonique, les nombres de Betti et les groupes d'homologies. Dans ces quatre cas, nous avons à nouveau utilisé les opérations de base afin de proposer des méthodes de mise à jour locales, ou pour simplifier la carte dans l'objectif d'accélérer les calculs du fait de la diminution du nombre de cellules. Nous avons utilisé ces travaux théoriques dans différentes applications. En modélisation géométrique, nous présentons le modeleur Moka qui est un modeleur géométrique à base topologique. Différentes applications se sont basées sur ce modeleur et nous présentons plus en détail une méthode de reconstruction automatique de bâtiments 3D à partir de plans numériques 2D. En traitement d'images, nous avons utilisé les cartes topologiques afin de proposer des algorithmes de segmentation d'images 2D et 3D pouvant intégrer un contrôle topologique.
|[T2] Définition et étude d'un modèle topologique minimal de représentation d'images 2d et 3d|
PhD Thesis, Montpellier II University, 14 December 2001
Abstract: Dans cette thèse, nous définissons et étudions un modèle topologique de représentation d'images segmentées en 2 et 3 dimensions : la carte topologique. La définition d'un tel modèle est primordiale afin de définir des algorithmes de segmentation efficaces. Ce problème a été beaucoup étudié en dimension 2, mais les solutions proposées sont difficilement extensibles en dimension 3.
Pour répondre à ce problème, nous définissons d'abord la carte topologique en dimension 2 en ayant comme préoccupation principale son extension en dimension supérieure. Nous introduisons une notion de niveau de simplification qui permet une définition progressive, chaque niveau s'obtenant simplement à partir du niveau précédent par application d'un type particulier de fusion. Cette notion permet de simplifier la définition de la carte topologique qui correspond au dernier niveau. Ces niveaux de simplification s'étendent sans difficulté majeure en dimension 3, et en dimension n. Ils facilitent également l'étude de la carte topologique et la preuve de ses propriétés. Ce modèle est en effet minimal, complet, invariant par rotation, translation et homothétie, et unique.
Nous présentons des algorithmes d'extraction permettant de construire ce modèle à partir d'images segmentées. Un premier algorithme << naïf >> effectue plusieurs passes sur l'image et n'est pas linéaire en dimension 3. Nous étudions ensuite un algorithme optimal d'extraction, basé sur la notion de précode, effectuant un seul balayage de l'image et un nombre minimal d'opérations. Les niveaux de simplification permettent de regrouper les nombreux cas à traiter, en étudiant pour chaque niveau les cas supplémentaires par rapport au niveau précédent.