Project topics and materials
Get Complete Project Material File(s) Now! »
Arrangement problem formalization
In the 2D space, an arrangement is dened as the decomposition of a nite collection C of curves in the plane [Edelsbrunner 1987, Snoeyink 1989, Halperin 2004]; these curves have no selfintersections, and are endless (either closed or bi-nite). Any two curves intersect in a nite number of points. The curves partition the plane into three types of maximally connected regions that are called cells of dimensions 0, 1 and 2: a 0-dimension cell (a vertex ) is the intersection point of two curves of C, a 1-dimension cell (an arc) is a maximally connected portion of a curve that is not intersected by any other curve in C; and a 2-dimension cell (a face) is a maximally connected region of R2 that is not intersected by any other curve in C. An arrangement of C is a set of those cells and their relations, denoted by A(C). An arrangement is simple if there are no three curves that intersect at a same point. An example of curve arrangements is shown in Figure 3.4. Various methods can be used to obtain the arrangement of curves: linear sweep construction [Edelsbrunner 1992], zone theorem [Edelsbrunner 1991b], topological sweep [Edelsbrunner 1991a], etc. A comprehensive discussion on the arrangement can be found in [Halperin 2004, chapter 24].
The problem of arrangement has been extended to the 3D space for the case of surfaces [Sharir 1999, Chan 2005]. Given a nite set S of surfaces, this set S partitions the 3D space into four types of cells: a 3-dimension cell is a maximally connected region that is not divided by any other surfaces in S, while the other 2-, 1-, and 0-dimension cells are dened as above. An example is shown in Figure 3.5. It is shown in [Sharir 1999] that the surface-arrangement algorithm has a complexity of (n4) for general surfaces, where n is the number of surfaces. To compute a DRT graph, we only deal with the tipping surfaces. From Section 2.4.2, we know that tipping surfaces in the 3D parameter space (a; b; ) can be fully described from their two cross-sections on the planes (a; ) and (b; ), respectively. These cross-sections are expressed by two sets of tipping curves. In addition, we are only interested in the information about regions and faces in the arrangement.
Therefore, instead of using the basic algorithm of surface arrangement, we propose a variation of the sweeping method [Edelsbrunner 1991a] for constructing the DRT graph with a better complexity of O(n3), where n is the number of tipping surfaces.
Sweeping algorithm for discrete rigid transformation graph construction
Let us formalize the specic case when the surfaces are tipping surfaces as follows. Given a set of tipping surfaces S, we would like to construct a graph modeling the subdivision of the parameter space (a; b; ) induced by S. Such a graph is called a DRT graph (see Denition 2) and denoted by G. We recall that in G, each vertex is associated to a 3D open cell of the subdivision, and each tippingsurface segment shared by two adjacent 3D open cells, is associated to an edge. When projecting two families of tipping surfaces on the planes (a; ) and (b; ), we obtain the corresponding families of tipping curves (see Figure 2.9(b) in Section 2.4.2). Based on these relations that link tipping surfaces and tipping curves, instead of constructing directly the partition graph in the 3D parameter space (a; b; ), we rst consider the structures of graphs in the 2D planes (namely, the (a; ) and (b; ) planes), and then combine them to build a complete DRT graph in the 3D parameter space (a; b; ).
The main idea of the sweeping method in 2D is that a cut is swept through all tipping curves on the plane, and allows us to construct a graph afterwards. We dene such a cut for a plane either (a; ) or (b; ) denoted by , as a monotonic line intersecting exactly once for each tipping curve in the plane. A cut is then represented by its sequence of intersecting tipping curves and modeled by a directed graph G according to its sequence, as illustrated in Figure 3.6.
Discrete rigid transformation graph under constraints
So far, we know that a DRT graph models the subdivision of the whole parameter space of rigid transformations. In other words, it models all the possible rigid transformations of a given subset of Z2 of size N N. It has been proved in [Ngo 2013a] that the DRT graph has a polynomial complexity O(N9) (see Section 3.4). Due to this high complexity, it is dicult to involve directly a DRT graph in image analysis applications. To tackle this issue, two approaches can be considered. The rst consists of using the DRT graph in a local fashion, thus reducing the space complexity of the research area where it is involved, as proposed in [Ngo 2013e, Ngo 2013b] (see Chapter 4). The second consists of providing spatial constraints in order to guide the transformations. Such constrained search paradigms are often used in image analysis and computer vision, e.g., for matching, registration and warping purposes [Pennec 2000, Zitová 2003, Amintoosi 2011, Xiao 2011, Jyoti 2012]. In general, these constraints introduce prior knowledge on transformations that contribute to reduce the searching space. We now investigate this second approach from a combinatorial point of view. More precisely, we address the eects of geometric constraints, called pixelinvariance constraints.
Table of contents :
Abstract
Résumé
Remerciements
List of enclosed articles
List of gures
1 Introduction
2 Rigid transformations on digital images
2.1 Background notions
2.1.1 2D (digital) image
2.1.2 2D (digital) rigid transformation
2.1.3 Transformation models
2.2 Non-bijectivity of digital rigid transformations
2.3 Non-preservation of geometric properties
2.4 Partition of the parameter space
2.4.1 Discontinuity of digital rigid transformations
2.4.2 Tipping surfaces and tipping curves
2.4.3 Digitization of the parameter space of rigid transformations
2.5 Summary
3 Combinatorial analysis of discrete rigid transformations
3.1 Graph representation of discrete rigid transformations
3.2 Algorithm for discrete rigid transformation graph construction
3.2.1 Arrangement problem formalization
3.2.2 Sweeping algorithm for discrete rigid transformation graph construction
3.3 Discrete rigid transformation graph under constraints
3.4 Space complexity of discrete rigid transformation graphs
3.5 Summary
4 Topological image analysis under rigid transformations
4.1 Digital topology: background notions
4.2 Topological issues on the discrete structure of images
4.3 Topological invariance of digital images under rigid transformations
4.4 Topological invariance verication
4.4.1 Discrete rigid transformation graph as a topological analysis tool
4.4.2 A local analysis for evaluating topological invariance
4.5 Summary
5 Conclusion
5.1 Contributions
5.2 Perspectives
Publications and communications
References
