Version française


Guillaume Damiand

oHome page

oResearches

oPublications

oTeaching

oSupervised Thesis

oCV

oContacts

oLinks

CNRS 

Publications

 
LIRIS
Books
    [B1] Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing
          Damiand G., Lienhardt P.
          A K Peters/CRC Press, September 2014
      
    Abstract: A Versatile Framework for Handling Subdivided Geometric Objects. Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing gathers important ideas related to combinatorial maps and explains how the maps are applied in geometric modeling and image processing. It focuses on two subclasses of combinatorial maps: n-Gmaps and n-maps. Suitable for researchers and graduate students in geometric modeling, computational and discrete geometry, computer graphics, and image processing and analysis, the book presents the data structures, operations, and algorithms that are useful in handling subdivided geometric objects. It shows how to study data structures for the explicit representation of subdivided geometric objects and describes operations for handling the structures. The book also illustrates results of the design of data structures and operations.

     link
     link

International Journals
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [J14] A Generic and Parallel Algorithm for 2D Digital Curve Polygonal Approximation
          Damiand G., Coeurjolly D.
          Journal of Real-Time Image Processing (JRTIP), Volume 6, Number 3, pages 145-157, September 2011
      
    Abstract: In this paper, we present a generic topological and geometrical framework which allows to define and control several parallel algorithms for 2D digital curve approximation. The proposed technique is based on combinatorial map simplifications guided by geometrical criteria. We illustrate the genericity of the framework by defining three contour simplification methods: a polygonal approximation one based an area deviation computation; a digital straight segments reconstruction one which guaranties to obtain a loss-less representation; and a moment preserving simplification one which simplifies the contours while preserving geometrical moments of the image regions. Thanks to a complete experimental evaluation, we demonstrate that the proposed methods can be efficiently implemented in a multi-thread environment to simplify labeled image contours.

     link
     link
     link
    [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.

     link
     link
     link
    [J12] Fully Deformable 3D Digital Partition Model with Topological Control
          Damiand G., Dupas A., Lachaud. J.-O.
          Pattern Recognition Letters (PRL), Volume 32, Number 9, pages 1374-1383, July 2011
      
    Abstract: We propose a purely discrete deformable partition model for segmenting 3D images. Its main ability is to maintain the topology of the partition during the minimization process. To do so, our main contribution is a new definition of multi-label simple points (ML simple point) that is easily computable. An ML simple point can be relabeled without modifying the overall topology of the partition. The definition is based on intervoxel properties, and uses the notion of collapse on cubical complexes. This work is an extension of a former restricted definition [DupasAl09] that prohibits the move of intersections of boundary surfaces. A deformation process is carried out with a greedy energy minimization algorithm. A discrete area estimator is used to approach at best standard regularizers classically used in continuous energy minimizing methods. We illustrate the potential of our approach with the segmentation of 3D medical images with known expected topology.

     link
     link
     link
    [J11] Efficient Search of Combinatorial Maps using Signatures
          Gosselin S., Damiand G., Solnon C.
          Theoretical Computer Science (TCS), Volume 412, Number 15, pages 1392-1405, March 2011
      
    Abstract: In this paper, we address the problem of computing canonical representations of n-dimensional combinatorial maps and of using them for efficiently searching for a map in a database. We define two combinatorial map signatures: the first one has a quadratic space complexity and may be used to decide of isomorphism with a new map in linear time whereas the second one has a linear space complexity and may be used to decide of isomorphism in quadratic time. We show that these signatures can be used to efficiently search for a map in a database.

     link
     link
     link
    [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.

     link
     link
     link
    [J9] Region Merging with Topological Control
          Dupas A., Damiand G.
          Discrete Applied Mathematics (DAM), Volume 157, Number 16, pages 3435-3446, August 2009
      
    Abstract: This paper presents a region merging process controlled by topological features on regions in 3D images. Betti numbers, a well-known topological invariant, are used as criteria. Classical and incremental algorithms to compute Betti numbers using information represented by the topological map of an image are provided. The region merging algorithm, which allows the merge of any number of connected components of regions together, is explained and its complexity is studied. A topological control of the merging process is implemented using Betti numbers to control the topology of an evolving 3D image partition. The interest of incremental approaches of Betti numbers computation is established by providing processing times comparison. A visual example showing the result of the algorithm and the impact of topological control is also given.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
    [J6] Topological Model for 3D Image Representation: Definition and Incremental Extraction Algorithm
          Damiand G.
          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.

     link
     link
     link
    [J5] nD Generalized Map Pyramids: Definition, Representations and Basic Operations
          Simon C., Damiand G., Lienhardt P.
          Pattern Recognition (PR), Volume 39, Number 4, pages 527-538, April 2006
      
    Abstract: Graph pyramids are often used for representing irregular image pyramids. For the 2D case, combinatorial pyramids have been recently defined in order to explicitly represent more topological information than graph pyramids. The main contribution of this work is the definition of pyramids of n-dimensional generalized maps. This extends the previous works to any dimension, and generalizes them in order to represent any type of pyramid built by using any removal and/or contraction operations. We give basic algorithms that allow to build an n-dimensional generalized pyramid that describes a multi-level segmented image. A pyramid of n-dimensional generalized maps can be implemented in several ways. We propose three possible representations and give conversion algorithms.

     link
     link
     link
    [J4] Removal and Contraction Operations to Define Combinatorial Pyramids: Application to the Design of a Spatial Modeler
          Damiand G., Dexet-Guiard M., Lienhardt P., Andres E.
          Image and Vision Computing (IMAVIS), Volume 23, Number 2, pages 259-269, February 2005
      
    Abstract: Removal and contraction are basic operations for several methods conceived in order to handle irregular image pyramids, for multi-level image analysis for instance. We give the definitions of removal and contraction operations in the generalized maps framework. We propose a first experimentation of irregular pyramid as a basis for a discrete geometrical modeler that can handle both discrete and continuous representations of geometrical objects. This modeler is based on a pyramidal kernel with four coexisting levels between the discrete and the Euclidean representations. We describe how this pyramid can be constructed and updated.

     link
     link
     link
    [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.

     link
     link
     link
    [J2] Split and Merge Algorithms Defined on Topological Maps for 3D Image Segmentation
          Damiand G., Resch P.
          Graphical Models (GM), Volume 65, Number 1-3, pages 149-167, May 2003
      
    Abstract: Split-and-merge algorithms define a class of image segmentation methods. Topological maps are a mathematical model that represents image subdivisions in 2D and 3D. This paper discusses a split-and-merge method for 3D image data based on the topological map model. This model allows representations of states of segmentations and of merge and split operations. Indeed, it can be used as data structure for dynamic changes of segmentation. The paper details such an algorithmic approach and analyzes its time complexity. A general introduction into combinatorial and topological maps is given to support the understanding of the proposed algorithms.

     link
     link
     link
    [J1] A Simple Paradigm for Graph Recognition: Application to Cographs and Distance Hereditary Graphs
          Damiand G., Habib M., Paul C.
          Theoretical Computer Science (TCS), Volume 263, Number 1-2, pages 99-111, July 2001
      
    Abstract: An easy way for graphs recognition algorithms is to use a two-steps process. First compute a characteristic feature as if the graph belong to that class. Secondly check whether the computed feature really defines the input graphs. Although in some cases the two steps can be merged. But separating them may yield to new and much more easily understood algorithms. In this paper we apply that paradigm to the cographs and distance hereditary graphs recognition problem.

     link
     link
     link

International Conferences
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [C51] Incremental Updating of 3D Topological Maps to Describe Videos
          Damiand G., Brandel S., Conte D.
          Proc. of 17th International Workshop on Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science 9448, pages 299-310, November 2015, Kolkata, India
      
    Abstract: A topological map is an efficient mathematical model for representing an image subdivision where all cells and adjacency relations between elements are represented. It has been proved to be a very good tool for video processing when video is seen as a 3D image. However the construction of a topological map for representing a video needs the availability of the complete image sequence. In this paper we propose a procedure for online updating a topological map in order to build it as the video is produced, allowing to use it in real time.

     link
     link
     link
    [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.

     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [C46] 2D Topological Map Isomorphism for Multi-label Simple Transformation Definition
          Damiand G., Roussillon T., Solnon C.
          Proc. of 18th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 8668, pages 39-50, September 2014, Siena, Italy
      
    Abstract: A 2D topological map allows one to fully describe the topology of a labeled image. In this paper we define 2D topological map isomorphism. We show that isomorphic topological maps correspond to homeomorphic embeddings in the plane and we give a polynomial-time algorithm for deciding of topological map isomorphism. Then we use this notion to give a generic definition of multi-label simple transformation as a set of transformations of labels of pixels which does not modify the topology of the labeled image. We illustrate the interest of multi-label simple transformation by generating look-up tables of any pair of adjacent pixel transformation preserving the topology.

     link
     link
     link
    [C45] Remove Noise in Video with 3D Topological Maps
          Conte D., Damiand G.
          Proc. of 15th International Workshop on Structural and Syntactic Pattern Recognition (SSPR), Lecture Notes in Computer Science 8621, pages 213-222, August 2014, Joensuu, Finland
      
    Abstract: In this paper we present a new method for foreground masks denoising in videos. Our main idea is to consider videos as 3D images and to deal with regions in these images. Denoising is thus simply achieved by merging foreground regions corresponding to noise with background regions. In this framework, the main question is the definition of a criterion allowing to decide if a region corresponds to noise or not. Thanks to our complete cellular description of 3D images, we can propose an advanced criterion based on Betti numbers, a topological invariant. Our results show the interest of our approach which gives better results than previous methods.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [C39] Removal Operations in nD Generalized Maps for Efficient Homology Computation
          Damiand G., Gonzalez-Diaz R., Peltier S.
          Proc. of 4th International Workshop on Computational Topology in Image Context (CTIC), Lecture Notes in Computer Science 7309, pages 20-29, May 2012, Bertinoro, Italy
      
    Abstract: In this paper, we present an efficient way for computing homology generators of nD generalized maps. The algorithm proceeds in two steps: (1) cell removals reduces the number of cells while preserving homology; (2) homology generator computation is performed on the reduced object by reducing incidence matrices into their Smith-Agoston normal form. In this paper, we provide a definition of cells that can be removed while preserving homology. Some results on 2D and 3D homology generators computation are presented.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [C33] Signatures of Combinatorial Maps
          Gosselin S., Damiand G., Solnon C.
          Proc. of 13th International Workshop on Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science 5852, pages 370-382, November 2009, Cancun, Mexico
      
    Abstract: In this paper, we address the problem of computing a canonical representation of an n-dimensional combinatorial map. For that, we define two combinatorial map signatures: the first one has a quadratic space complexity and may be used to decide of isomorphism with a new map in linear time whereas the second one has a linear space complexity and may be used to decide of isomorphism in quadratic time. Experimental results show that these signatures can be used to recognize images very efficiently.

     link
     link
     link
    [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.

     link
     link
    [C31] Multi-Label Simple Points Definition for 3D Images Digital Deformable Model
          Dupas A., Damiand G., Lachaud J.-O.
          Proc. of 15th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 5810, pages 156-167, September 2009, Montréal, Canada
      
    Abstract: We present a new deformable partition model, with a natural application to image segmentation. Our approach is purely digital: the partition geometry is the set of intervoxel elements that are between regions and is thus a set of digital surfaces. We define the new notion of I-Simple points to ensure that the partition topology remains unchanged during deformations. This definition is based on simple intervoxel properties and is easy to implement. The deformation is carried out with a greedy energy minimization algorithm. A discrete area estimator is used to approach at best standard regularizers classically used in continuous energy minimizing methods. The effectiveness of our approach is shown on several 3D image segmentations.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
    [C28] A Polynomial Algorithm for Subisomorphism of Holey Plane Graphs
          Damiand G., De La Higuera C., Janodet J.-C., Samuel E., Solnon C.
          Proc. of 7th International Workshop on Mining and Learning with Graphs (MLG), July 2009, Leuven, Belgium
      
    Abstract: We address the problem of searching for a pattern in a plane graph, that is, a planar drawing of a planar graph. We define plane subgraph isomorphism and give a polynomial algorithm for this problem. We show that this algorithm may be used even when the pattern graph has holes.

     link
     link
     link
    [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.

     link
     link
     link
    [C26] 3D Topological Map Extraction from Oriented Boundary Graph
          Baldacci F., Braquelaire A., Damiand G.
          Proc. of 7th Workshop on Graph-Based Representations in Pattern Recognition (GBR), Lecture Notes in Computer Science 5534, pages 283-292, May 2009, Venice, Italy
      
    Abstract: The extraction of a 3D topological map from an Oriented Boundary Graph can be needed to refine a 3D Split and Merge segmentation using topological information such as the Euler characteristic of regions. A presegmentation could thus be efficiently obtained using a light structuring model, before proceeding to the extraction of more information on some regions of interest. In this paper, we present the topological map extraction algorithm which allows to reconstruct locally a set of regions from the Oriented Boundary Graph. A comparison of the two models is also presented.

     link
     link
     link
    [C25] A Top-Down Construction Scheme for Irregular Pyramids
          Goffe R., Brun L., Damiand G.
          Proc. of 4th International Conference On Computer Vision Theory And Applications (VISAPP), pages 163-170, February 2009, Lisboa, Portugal
      
    Abstract: Hierarchical data structures such as irregular pyramids are used by many applications related to image processing and segmentation. The construction scheme of such pyramids is bottom-up. Such a scheme forbids the definition of a level according to more global information defined at upper levels in the hierarchy. Moreover, the base of the pyramid has to encode any single pixel of the initial image in order to allow the definition of regions of any shape at higher levels. This last constraint raises major issues of memory usage and processing costs when irregular pyramids are applied to large images. The objective of this paper is to define a top-down construction scheme for irregular pyramids. Each level of such a pyramid is encoded by a combinatorial map associated to an explicit encoding of the geometry and the inclusion relationships of the corresponding partition. The resulting structure is a stack of finer and finer partitions obtained by successive splitting operations and is called a top-down pyramid.

     link
     link
     link
    [C24] A Generic and Parallel Algorithm for 2D Image Discrete Contour Reconstruction
          Damiand G., Coeurjolly D.
          Proc. of 4th International Symposium on Visual Computing (ISVC), Lecture Notes in Computer Science 5359, pages 792-801, December 2008, Las vegas, Nevada, USA
      
    Abstract: In this paper, we present a generic topological and geometrical framework for the digital reconstruction of complex contours from labeled images. The proposed technique is based on combinatorial map simplifications guided by digital straight segments. We illustrate the genericity of the framework with a parallel contour reconstruction algorithm.

     link
     link
     link
    [C23] Computing Canonical Polygonal Schemata with Generalized Maps
          Damiand G., Alayrangues S.
          Proc. of International Conference on Topological & Geometric Graph Theory (TGGT), Electronic Notes in Discrete Mathematics 31, pages 287-292, August 2008, Paris, France
      
    Abstract: The comparison of two topological surfaces is a frequent question that may be solved by using accurate topological invariants. Such invariants already exist and the main difficulty is to achieve their computation efficiently. In [VegYap90], authors propose an algorithm which allows to compute the canonical polygonal schema of a given surface by using particular transformation rules. This paper shows that these transformations can be defined on a 2-dimensional generalized map which encodes a surface. The algorithm proposed in [VegYap90] to compute canonical polygonal schema can now be transfered onto generalized maps. Moreover, all transformations can be achieved in O(1) with generalized maps, which can help optimizing existing algorithms.

     link
     link
     link
    [C22] Topologically Constrained Segmentation with Topological Maps
          Dupas A., Damiand G.
          Proc. of 1st International Workshop on Computational Topology in Image Context (CTIC), June 2008, Poitiers, France
      
    Abstract: This paper presents incremental algorithms used to compute Betti numbers with topological maps. Their implementation, as topological criterion for an existing bottom-up segmentation, is explained and results on artificial images are shown to illustrate the process.

     link
     link
    [C21] First Results for 3D Image Segmentation with Topological Map
          Dupas A., Damiand G.
          Proc. of 14th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 4992, pages 507-518, April 2008, Lyon, France
      
    Abstract: This paper presents the first segmentation operation defined within the 3D topological map framework. Firstly we show how a traditional segmentation algorithm, found in the literature, can be transposed on a 3D image represented by a topological map. We show the consistency of the results despite of the modifications made to the segmentation algorithm in order to handle topological maps. We study the complexity of the operation. Lastly, we present some experimental results mainly for 3D medical images. These results show the process duration of our method and validate the interest to use 3D topological map in the context of image processing.

     link
     link
     link
    [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) [13], each n-G-map being defined from the previous level by using removal and contraction operations defined in [18]. 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.

     link
     link
     link
    [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.

     link
     link
     link
    [C18] Comparison of Local and Global Region Merging in the Topological Map
          Dupas A., Damiand G.
          Proc. of 12th International Workshop on Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science 4958, pages 420-431, April 2008, Buffalo, NY, USA
      
    Abstract: Topological maps are a model which represents 2D or 3D image subdivisions. The aim of this structure is to provide an image representation which allows topological and geometrical features to be used by image processing operations. Algorithm of region merging is an useful tool in image segmentation and image processing. This paper presents two algorithms of region merging in 3D topological maps: one local which modifies locally the map around merged regions, and another one global which runs through all the elements of the map. We study their complexities and present experimental results to compare both approaches.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [C10] Pyramids of n-Dimensional Generalized Maps
          Simon C., Damiand G., Lienhardt P.
          Proc. of 5th Workshop on Graph-Based Representations in Pattern Recognition (GBR), Lecture Notes in Computer Science 3434, pages 142-152, April 2005, Poitiers, France
      
    Abstract: Graph pyramids are often used for representing irregular pyramids. Combinatorial pyramids have been recently defined for this purpose. We define here pyramids of n-dimensional generalized maps. This is the main contribution of this work: a generic definition in any dimension which extend and generalize the previous works. Moreover, such pyramids explicitly represent more topological information than graph pyramids. A pyramid can be implemented in several ways, and three representations are discussed in this paper.

     link
     link
     link
    [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.

     link
     link
     link
    [C8] Removal and Contraction for N-Dimensional Generalized Maps
          Damiand G., Lienhardt P.
          Proc. of 11th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 2886, pages 408-419, November 2003, Naples, Italy
      
    Abstract: Removal and contraction are basic operations for several methods conceived in order to handle irregular image pyramids, for multi-level image analysis for instance. Such methods are often based upon graph-like representations which do not maintain all topological information, even for 2-dimensional images. We study the definitions of removal and contraction operations in the generalized maps framework. These combinatorial structures enable us to unambiguously represent the topology of a well-known class of subdivisions of n-dimensional (discrete) spaces. The results of this study make a basis for a further work about irregular pyramids of n-dimensional images.

     link
     link
     link
    [C7] Comparison and Convergence of Two Topological Models for 3D Image Segmentation
          Braquelaire A., Damiand G., Domenger J.-P., Vidil F.
          Proc. of 4th Workshop on Graph-Based Representations in Pattern Recognition (GBR), Lecture Notes in Computer Science 2726, pages 59-70, July 2003, York, England
      
    Abstract: In this paper we compare two topological models of 3D segmented images representation. These models are based on a collaboration between a topological representation and a geometrical representation of the regions of the segmented image. In both models the description of the topology lays on topological maps with a combinatorial representation. A geometrical embedding of maps is used to describe the geometry of regions. Both models differ in the way of defining this embedding. The aim of this paper is to compare these two models from the point of view of their interest for image segmentation, and to explore the possibility and the interest of making both these models converge

     link
     link
     link
    [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.

     link
     link
     link
    [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.

     link
     link
     link
    [C4] Topological Map: Minimal Encoding of 3d Segmented Images
          Bertrand Y., Damiand G., Fiorio C.
          Proc. of 3rd Workshop on Graph-Based Representation in Pattern Recognition (GBR), pages 64-73, May 2001, Ischia, Italy
      
    Abstract: In this paper we define formally and completely the 3d topological map introduced in BertrandAl00: a model which encodes totally and minimally all the topological information of a 3d image. In particular, we focus on the problem of disconnections induced by the constructive definition based on several levels of maps. This multilevel representation is more or less a graph pyramid in sense that each level can be compute from the previous one in term of merge operations. Furthermore, algorithms extracting these maps from a segmented image have been given in BertrandAl00 and have been implemented and tested in practical applications.

     link
     link
    [C3] Topological Encoding of 3d Segmented Images
          Bertrand Y., Damiand G., Fiorio C.
          Proc. of 9th International Conference on Discrete Geometry for Computer Imagery (DGCI), Lecture Notes in Computer Science 1953, pages 311-324, December 2000, Uppsala, Sweden
      
    Abstract: In this paper we define the 3d topological map and give an optimal algorithm which computes it from a segmented image. This data structure encodes totally all the information given by the segmentation. More, it allows to continue segmentation either algorithmically or interactively. We propose an original approach which uses several levels of maps. This allows us to propose a reasonable and implementable solution where other approaches don't allow suitable solutions. Moreover our solution has been implemented and the theoretical results translate very well in practical applications.

     link
     link
     link
    [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).

     link
    [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).

     link

Book Chapters
    [BC2] Combinatorial Maps for 2D and 3D Image Segmentation
          Damiand G., Dupas A.
          Digital Geometry Algorithms: Theoretical Foundations and Applications to Computational Imaging, Lecture Notes in Computational Vision and Biomechanics 2, pages 359-393, May 2012
      
    Abstract: This chapter shows how combinatorial maps can be used for 2D or 3D image segmentation. We start by introducing combinatorial maps and we show how they can be used to describe image partitions. Then, we present a generic segmentation algorithm that uses and modifies the image partition represented by a combinatorial map. One advantage of this algorithm is that one can mix different criteria and use different image features which can be associated with the cells of the partition. In particular, it is interesting that the topological properties of the image partition can be controlled through this approach. This property is illustrated by the computation of classical topological invariants, known as Betti numbers, which are then used to control the number of cavities or the number of tunnels of regions in the image partition. Finally, we present some experimental results of 2D and 3D image segmentation using different criteria detailed in this chapter.

     link
     link
     link
    [BC1] Cartes combinatoires pour l'analyse d'images
          Damiand G., Brun L.
          Géométrie discrète et images numériques, Traité IC2, Signal et Image, pages 103-120, Août 2007
      
    Abstract: Les cartes combinatoires permettent de représenter totalement la topologie d'une subdivision cellulaire d'un objet graphique. Pour cette raison, elles s'avèrent être un bon outil pour représenter et modifier un découpage d'une image 2D ou 3D en régions. Dans ce chapitre nous montrons comment utiliser ces cartes combinatoires en analyse d'images. Nous montrons comment définir la carte, l'extraire à partir d'une image et quelles opérations il est possible d'utiliser pour modifier la partition.

     link
     link
     link

Thesis
    [T3] Contributions aux Cartes Combinatoires et Cartes Généralisées : Simplification, Modèles, Invariants Topologiques et Applications
          Guillaume Damiand
          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.

     link
     link
     link
    [T2] Définition et étude d'un modèle topologique minimal de représentation d'images 2d et 3d
          Guillaume Damiand
          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.

     link
     link
     link
    [T1] Quelques propriétés des graphes distances héréditaires
          Guillaume Damiand
          Master Thesis, Montpellier II University, June 1997, Sibil: 1144509
     link

Editors


o [Back]