Download Transformations rigides sur les images numériques 2D: analyse combinatoire et topologique PDF

TitleTransformations rigides sur les images numériques 2D: analyse combinatoire et topologique
LanguageEnglish
File Size12.5 MB
Total Pages141
Table of Contents
                            Abstract
Résumé
Remerciements
List of enclosed articles
List of figures
Part I: Discrete rigid transformation
	Introduction
	Rigid transformations on digital images
		Background notions
			2D (digital) image
			2D (digital) rigid transformation
			Transformation models
		Non-bijectivity of digital rigid transformations
		Non-preservation of geometric properties
		Partition of the parameter space
			Discontinuity of digital rigid transformations
			Tipping surfaces and tipping curves
			Digitization of the parameter space of rigid transformations
		Summary
	Combinatorial analysis of discrete rigid transformations
		Graph representation of discrete rigid transformations
		Algorithm for discrete rigid transformation graph construction
			Arrangement problem formalization
			Sweeping algorithm for discrete rigid transformation graph construction
		Discrete rigid transformation graph under constraints
		Space complexity of discrete rigid transformation graphs
		Summary
	Topological image analysis under rigid transformations
		Digital topology: background notions
		Topological issues on the discrete structure of images
		Topological invariance of digital images under rigid transformations
		Topological invariance verification
			Discrete rigid transformation graph as a topological analysis tool
			A local analysis for evaluating topological invariance
		Summary
	Conclusion
		Contributions
		Perspectives
	Publications and communications
	References
Part II: Enclosed articles
	Article 1: Combinatorial structure of rigid transformations in 2D digital images
	Article 2: Topology-preserving conditions for 2D digital images under rigid transformations
	Article 3: On 2D constrained discrete rigid transformations
                        
Document Text Contents
Page 1

HAL Id: tel-01186326
https://pastel.archives-ouvertes.fr/tel-01186326

Submitted on 24 Aug 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L’archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d’enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Transformations rigides sur les images numériques 2D :
analyse combinatoire et topologique

Hoai Diem Phuc Ngo

To cite this version:
Hoai Diem Phuc Ngo. Transformations rigides sur les images numériques 2D : analyse combinatoire et
topologique. Image Processing [eess.IV]. Université Paris-Est, 2013. English. �NNT : 2013PEST1091�.
�tel-01186326�

https://pastel.archives-ouvertes.fr/tel-01186326
https://hal.archives-ouvertes.fr

Page 2

upe_logo.eps


UNIVERSITÉ PARIS-EST
ÉCOLE DOCTORALE MSTIC

T H È S E
pour obtenir le grade de

Docteur en Informatique � Signal, Image, Automatique

de l'Université Paris-Est, Marne-la-Vallée

Présentée par

Hoai Diem Phuc Ngo

RIGID TRANSFORMATIONS ON

2D DIGITAL IMAGES

COMBINATORIAL AND TOPOLOGICAL ANALYSIS

Transformations rigides sur les images numériques 2D

Analyse combinatoire et topologique

Directeur de thèse : Michel Couprie

Encadrants : Yukiko Kenmochi, Nicolas Passat et Hugues Talbot

Soutenue le 18 octobre 2013

Membres du jury :

Rapporteurs : Éric Andrès Professeur, Université de Poitiers
David Coeurjolly Directeur de Recherche, CNRS, Lyon

Examinateurs : Jean-Pierre Reveillès Docteur d'État
Michel Couprie Professeur, ESIEE - Paris
Yukiko Kenmochi Chargée de Recherche, CNRS, Paris
Nicolas Passat Professeur, Université de Reims Champagne-Ardenne
Hugues Talbot Professeur Associé, ESIEE - Paris

Invitée : Fanny Buyens Ingénieur - Chercheur, CEA LIST - DIGITEO Labs

Page 70

REFERENCES 49

[Hundt 2008b] C. Hundt and M. Li±kiewicz. Two-dimensional pattern matching with com-

bined scaling and rotation. In CPM, Proceedings, volume 5029 of Lecture Notes in

Computer Science, pages 5�17. Springer, 2008. (Cited on page 7.)

[Hundt 2009] C. Hundt, M. Li±kiewicz and R. Nevries. A combinatorial geometrical ap-

proach to two-dimensional robust pattern matching with scaling and rotation. Theo-

retical Computer Science, vol. 410, no. 51, pages 5317�5333, 2009. (Cited on pages vi,

4, 7, 17 and 29.)

[Hundt 2010] C. Hundt. A�ne image matching is uniform TC0-complete. In CPM, Pro-

ceedings, volume 6129 of Lecture Notes in Computer Science, pages 13�25. Springer,

2010. (Cited on pages 4 and 7.)

[Jacob 1995] M.-A. Jacob and E. Andres. On discrete rotations. In DGCI, Proceedings,

pages 161�174, 1995. (Cited on page 11.)

[Jyoti 2012] J. Jyoti and S. G. Shirish. Area based image matching methods � A survey.

Emerging Technology and Advanced Engineering, vol. 2, no. 1, pages 130�136, 2012.

(Cited on page 25.)

[Khalimsky 1987] E. Khalimsky. Topological structures in computer science. Journal of

Applied Mathematics and Simulation, vol. 1, no. 1, pages 25�40, 1987. (Cited on

pages 32 and 34.)

[Kong 1989] T. Y. Kong and A. Rosenfeld. Digital topology: Introduction and survey. Com-

puter Vision Graphics & Image Processing, vol. 48, no. 3, pages 357�393, 1989.

(Cited on pages 13, 32, 34 and 38.)

[Kovalevsky 1989] V. A. Kovalevsky. Finite topology as applied to image analysis. Computer

Vision, Graphics & Image Processing, vol. 46, no. 2, pages 141�161, 1989. (Cited on

pages 13, 32 and 34.)

[Lam 1992] L. Lam, S.-W. Lee and C. Y. Suen. Thinning methodologies � A comprehensive

survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14,

no. 9, pages 869�885, 1992. (Cited on pages 31 and 40.)

[Latecki 1995] L. J. Latecki, U. Eckhardt and A. Rosenfeld. Well-composed sets. Com-

puter Vision and Image Understanding, vol. 61, no. 1, pages 70�83, 1995. (Cited on

page 39.)

[Latecki 1998] L. J. Latecki, C. Conrad and A. Gross. Preserving topology by a digitization

process. Journal of Mathematical Imaging and Vision, vol. 8, no. 2, pages 131�159,

1998. (Cited on pages 40 and 43.)

Page 71

50 REFERENCES

[Mazo 2012a] L. Mazo, N. Passat, M. Couprie and C. Ronse. Digital imaging: A uni�ed

topological framework. Journal of Mathematical Imaging and Vision, vol. 44, no. 1,

pages 19�37, 2012. (Cited on page 32.)

[Mazo 2012b] L. Mazo, N. Passat, M. Couprie and C. Ronse. Topology on digital label

images. Journal of Mathematical Imaging and Vision, vol. 44, no. 3, pages 254�281,

2012. (Cited on page 39.)

[Nouvel 2005] B. Nouvel and E. Rémila. Con�gurations induced by discrete rotations: Pe-

riodicity and quasi-periodicity properties. Discrete Applied Mathematics, vol. 147,

no. 2�3, pages 325�343, 2005. (Cited on pages vi, 4 and 11.)

[Nouvel 2006a] B. Nouvel. Rotations discrètes et automates cellulaires. PhD thesis, École

Normale Supérieure de Lyon, 2006. (Cited on pages 4 and 11.)

[Nouvel 2006b] B. Nouvel and E. Rémila. Incremental and transitive discrete rotations.

In IWCIA, Proceedings, volume 4040 of Lecture Notes in Computer Science, pages

199�213. Springer, 2006. (Cited on pages vi and 4.)

[Pennec 2000] X. Pennec, N. Ayache and J.-P. Thirion. Landmark-based registration using

features identi�ed through di�erential geometry. In I. N. Bankman, editeur, Hand-

book of Medical Imaging, chapitre 31, pages 499�513. Academic Press, 2000. (Cited

on pages vii, 25, 29, 41 and 42.)

[Pham 2001] D. L. Pham. Spatial models for fuzzy clustering. Computer Vision and Image

Understanding, vol. 84, no. 2, pages 285�297, 2001. (Cited on pages 31 and 40.)

[Rosen 1992] K. H. Rosen. Elementary Number Theory and its Applications. Addison-

Wesley, 3rd édition, 1992. (Cited on page 24.)

[Rosenfeld 1966] A. Rosenfeld and J. L. Pfaltz. Sequential operations in digial picture pro-

cessing. Journal of the Association for Computing Machinery, vol. 13, no. 4, pages

471�494, 1966. (Cited on page 32.)

[Rosenfeld 1970] A. Rosenfeld. Connectivity in digital pictures. Journal of the Association

for Computing Machinery, vol. 17, no. 1, pages 146�160, 1970. (Cited on pages 31

and 33.)

[Serra 1983] J. Serra. Image Analysis and Mathematical Morphology. Academic Press, Inc.,

1983. (Cited on pages 40 and 43.)

[Sharir 1999] M. Sharir. Recent developments in the theory of arrangements of surfaces. In

FSTTCS, Proceedings, volume 1738 of Lecture Notes in Computer Science, pages

1�21. Springer, 1999. (Cited on pages 20 and 22.)

Page 140

On 2D Constrained Discrete Rigid Transformations 33

Procedure 1: Modification of the graph associated to a cut with respect to a
boundary event point of either type (a) or (b).

Input: A graph G
a = (V
a , E
a) associated to a cut γa = (φ1, φ2, . . . , φn−1, φn)
and a boundary event point q = {φu, φv}.

Output: The modified graph of G
a at q.
1 if (φu = φ1 and φv 6= φ2) or (φv = φ1 and φu 6= φ2) then
2 e1 ← ε(φ1) ; e2 ← ε(φ2)
3 {w} ← ϑ(e1) ∩ ϑ(e2)
4 {φ′} ← {φu, φv} \ {φ1} // φ′ = {either φu or φv} is a new upper boundary
5 E



a ← {(w0, w, φ1)} // {w0} = ϑ(e1) \ {w} is a top vertex

6 E
+

a ← {(w0, w, φ′)}

7 if (φu = φn and φv 6= φn−1) or (φv = φn and φu 6= φn−1) then
8 e1 ← ε(φn) ; e2 ← ε(φn−1)
9 {w} ← ϑ(e1) ∩ ϑ(e2)

10 {φ′} ← {φu, φv} \ {φn} // φ′ = {either φu or φv} is a new lower boundary
11 E−a ← {(w,wn, φn)} // {wn} = ϑ(e1) \ {w} is a bottom vertex
12 E

+

a ← {(w,wn, φ′)}

13 E
a ← E
a \ E−
a ∪E
+

a // No new vertex is generated at q

Procedure 2: Modification of the graph associated to a cut with respect to a
boundary event point of either type (c) or (d).

Input: A graph G
a = (V
a , E
a) associated to a cut γa = (φ1, φ2, . . . , φn−1, φn)
and a boundary event point q = {φu, φv}.

Output: The modified graph of G
a at q.
1 if φu = φ1 then
2 if φv 6= φ2 then
3 eu ← ε(φu)
4 {w} ← ϑ(eu) \ {w0} // w0 is a top vertex
5 E



a ← {(w0, w, φu)}

6 V
+


a ← {w′} // w′ is a new vertex
7 E+
a ← {(w0, w′, φu), (w′, w, φv)}
8 if φv = φ2 then
9 eu ← ε(φu) ; ev ← ε(φv)

10 {w} ← ϑ(eu) ∩ ϑ(ev)
11 {w′} ← ϑ(ev) \ {w} // w′ is an adjacent vertex of w
12 V −
a ← {w} // w is a removed vertex
13 E



a ← {(w0, w, φu), (w,w′, φv)}

14 E
+

a ← {(w0, w′, φu)}

15 V
a ← V
a \ V −
a ∪ V
+


a

16 E
a ← E
a \ E−
a ∪E
+

a

– ε(φ) returns the edge corresponding to the tipping curve φ in δE
a .

Similarly, we have in Procedure 2 the algorithm for modifying the graph G
a at a

boundary event point q = {φu, φv} which has φv goes in and out by crossing the upper
boundary φu, i.e., type (c) and (d).

Similer Documents