Rotations dans les espaces discrets 2D et 3D, Rotations in 2D and 3D discrete spaces

Yohan Thibault

Description

Sous la direction de Michel Couprie
Thèse soutenue le 22 septembre 2010: Paris Est
Cette thèse présente une étude sur les rotations dans les espaces discrets en 2 dimensions et en 3 dimensions. Dans le cadre de l'informatique, l'utilisation des nombres flottants n'est pas recommandée du fait des erreurs de calculs que cela implique. Nous avons donc fait le choix de nous concentrer sur les espaces discrets. Dans le domaine de la vision par ordinateur, la rotation est une transformation requise pour de nombreuses applications. L'utilisation de la rotation continue discrétisée donne des résultats de mauvaise qualité. Pour cette raison, il est nécessaire de développer de nouvelles méthodes de rotation adaptées aux espaces discrets. Nous nous sommes principalement intéressés aux angles charnières qui représentent la discontinuité de la rotation dans les espaces discrets. Dans ces espaces, deux rotations d'une image avec deux angles très proches peuvent donner le même résultat, ce qui est capturé par les angles charnières. L'utilisation de ces angles permet de décrire une rotation qui donne les mêmes résultats que la rotation continue discrétisée tout en n'utilisant que des nombres entiers. Ils permettent aussi de définir une rotation incrémentale qui décrit toutes les rotations possibles d'une image digitale donnée. Les angles charnières peuvent être étendus dans les espaces discrets en trois dimensions. Pour cela, on définit les multi-grilles qui sont des plans de rotations contenant trois ensembles de droites parallèles. Elles représentent les discontinuités de la rotation en 3D. Les multi-grilles permettent d'obtenir les mêmes résultats en 3D que ceux obtenus en 2D
-Rotation
-Rotation discrète
-Géométrie discrète
-Angle charnière
-Multi-grille
This thesis presents a study on rotation in 2 dimensional and 3 dimensional discrete spaces. In computer science, using floating numbers is problematic due to computation errors. Thus we chose during this thesis to work only in discrete space. In the field of computer vision, the rotation is a transformation required for many applications. Using discretized Euclidean rotation gives bad results. Then, it is necessary to develop new rotation methods adapted to the discrete spaces. We mainly studied the hinge angles that represent the discontinuity of the rotation in the discrete space. Indeed, it is possible to perform two rotations of the same digital image with two angles that are slightly different and obtain the same result. This is captured by hinge angles. Using these angles allow us to describe a discrete rotation that gives the same results than the discretized Euclidean rotation without using floating numbers. They also allow describing an incremental rotation that performs all possible rotations of a given digital image. Using hinge angles can also be extended to the rotations in 3 dimensional discrete spaces. The extension requires the multi-grids that are rotation planes containing three sets of parallel lines. These parallel lines represent the discontinuities of the rotation in 3D discrete space. Thus they are useful to describe the hinge angles in rotation planes. Multi-grids allow obtaining the same results in 3D discrete rotations than the results obtained in 2D discrete rotations. This thesis presents a study on rotation in 2 dimensional and 3 dimensional discrete spaces. In computer science, using floating numbers is problematic due to computation errors. Thus we chose during this thesis to work only in discrete space. In the field of computer vision, the rotation is a transformation required for many applications. Using discretized Euclidean rotation gives bad results. Then, it is necessary to develop new rotation methods adapted to the discrete spaces. We mainly studied the hinge angles that represent the discontinuity of the rotation in the discrete space. Indeed, it is possible to perform two rotations of the same digital image with two angles that are slightly different and obtain the same result. This is captured by hinge angles. Using these angles allow us to describe a discrete rotation that gives the same results than the discretized Euclidean rotation without using floating numbers. They also allow describing an incremental rotation that performs all possible rotations of a given digital image. Using hinge angles can also be extended to the rotations in 3 dimensional discrete spaces. The extension requires the multi-grids that are rotation planes containing three sets of parallel lines. These parallel lines represent the discontinuities of the rotation in 3D discrete space. Thus they are useful to describe the hinge angles in rotation planes. Multi-grids allow obtaining the same results in 3D discrete rotations than the results obtained in 2D discrete rotations
-Rotation
-Discrete rotation
-Digital geometry
-Hinge angle
-Multi-grid
Source: http://www.theses.fr/2010PEST1042/document

Sujets

• Géométrie discrète

Informations

• Publié par: Thesee
• Nombre de lectures: 17
• Langue: English
• Poids de l'ouvrage: 9 Mo

Extrait

ANDRÈS
y
Lauren
P
COUPRIE
ARIS-EST
de
École
the
Do
oratoire
ctorale
REVEILLÈS
MSTIC
Y
Rotations
SUGIMOTO
in
conférences
2D
Univ
and
aris-Est
3D
Gaspard-Monge
discrete
hel
spaces
Professeur
b
Professeur
y
o
THIBA
herc
UL
Professeur
T
Maître
Y
bre
ohan
2010
Sup
ersit
ervised
P
b
Lab
y
d'informatique
COUPRIE
Jury
Mic
Mic
hel
Professeur
KENMOCHI
Jean-Pierre
Y
Émérite
ukik
Éric
o
KENMOCHI
A
ukik
thesis
Chargée
submitted
rec
to
he
obtain
Akihiro
the
FUCHS
Do
t
ctor
de
in
Septem
computer
22nd
science
in
UNIVERSITÉ
tel-00596947, version 1 - 30 May 2011Grand
Blaise
ESIEE-P
Thesis
Descartes,
prepared
Gaspard
in
2,
Univ
ascal,
ersité
Noisy
P
Cedex
ARIS-EST
Monge
Équip
ARIS
e
Bd
A3SI
P
du
Cité
Lab
BP99
oratoire
le
d'Informatique
l'Institut
de
i
tel-00596947, version 1 - 30 May 2011the
del
c
p
et
ensé.
wil
En
the
anglais,
a
il
oximate
existe
omputer
le
lenge
verb
gar
e
.
"to
numb
r
a
otate",
omp
en
diameter
fr
cision
ançais
discr
son
T
é
nd
quivalent
as
ser
elieve
ait
famous
le
etic
verb
exact
e
r
r
the
otationner,
or
sa
er
dénition
only
ser
ete
ait
cle,
eectuer
or
ou
omp
faire
any
eectuer
c
une
e
rotation
of
.
scienc
Cep
so
endant
esent
le
p
verb
we
e
ds
"r
is
otationner"
er
n
the
'existe
mathematic
p
oses
as
of
dans
however,
la
esentation
langue
cle
fr
ound
ançaise.
op
Et
a
p
p
ourtant,
a
il
c
tourne.
an
The
value
discr
whatever
ete
the
ge
size
ometry
op
is
pr
to
the
classic
In
al
e,
ge
oximation
ometry
d
what
r
the
always
language
appr
is
day,
to
biggest
thought,
c
i.e.
is
an
metho
imp
c
erfe
r
ct
e
me
ly
ans
R
to
ge
r
ongly
epr
these
esent
elong
the
example
r
ometry.
e
numb
ality.
ge
It
The
to
or
ok
al
c
mo
enturies
supp
for
an
the
value
language
this
to
er,
evolve
the
in
epr
a
of
way
cir
almost
on
c
gr
ap
with
able
r
to
e
faithful
on
ly
she
describ
of
e
ap
our
by
though.
c
T
ass
o
an
day
give
the
appr
discr
d
ete
of
ge
,
ometry
the
tries
of
to
cir
do
the
the
of
same
r
thing
e
with
the
the
e
c
of
ontinuous
c
ge
ass.
ometry.
c
The
scienc
c
for
ontinuous
appr
ge
of
ometry
use
is
during
a
omputations,
mathematic
esults
al
l
mo
b
del
an
that
oximation.
c
o
annot
one
b
the
e
chal
c
in
orr
omputer
e
e
ctly
to
or
new
exactly
ds
r
that
epr
omputers
o
an
duc
epr
e
r
d
ality
in
faithful
the
as
r
ossible.
e
e
al
ding
world
ometry,
and
str
in
b
c
that
omputer
metho
scienc
b
e.
to
A
the
simple
Petite
π
π
π
tel-00596947, version 1 - 30 May 2011Philosoph
Do
THIBA
P
ctor
ARIS-EST
b
A
T
bstr
ohan
act
of
P
y
aris-Est
y
Lab
UL
oratoire
Y
d'informatique
Gaspard-Monge
UNIVERSITÉ
tel-00596947, version 1 - 30 May 2011rotation
L'utilisation
et
thèse
tin
présen
tée
te
dans
une
Ces
étude
dénit
sur
ceux
les
sommes
rotations
représen
dans
hes
les
que
espaces
les
discrets
harnières
en
ensem
2
plans
et
l'in
3
l'art
dimensions.
emen
Un
t
espace
la
discret
a
est,
particularité
par
décrire
opp
a
osition
une
à
donnée
un
de
espace
en
con
plans
tin
ten
u,
à
un
t
espace
autour
b
discrets
orné
c
a
des
v
sur
ec
dans
un
Nous
nom
angles
bre
discon
ni
espaces
de
deux
p
angles
oin
le
ts.
les
En
particuliers
informatique,
donne
les
tin
espaces
aux
con
t
tin
tale
us
d'une
n'existen
ossible
t
y
pas
L'utilisation
;
dans
en
our
eet,
qui
même
con
l'utilisation
parallèles.
de
tin
nom
serv
bres
c
ottan
m
ts
résultats
ne
2D.
p
hapitres
ermet
probléma-
qu'une
dans
appro
hapitre
ximation
te
grossière
d'une
du
nous
con
concen
tin
dév
u.
des
Les
espaces
données
leur
utilisées
sommes
dans
téressés
le
harnières
cadre
t
de
uité
l'informatique
dans
son
En
t
espaces,
le
d'une
plus
ec
souv
pro
en
eut
t
résultat.
en
capturée
tières.
c
P
ces
ar
ermet
exemple,
rotation
une
mêmes
image
rotation
n
discrétisée
umérique
oir
n'est
ottan
comp
p
osée
de
que
incré-
de
décrit
p
p
oin
n
ts
hose
à
le
co
car
ordonnées
une
en
p
tières
angles
et,
eut-être
p
espaces
our
dimensions.
la
faire,
couleur,
m
à
t
v
rotations
aleurs
t
en
de
tières.
droites
De
les
plus
de
l'utilisation
3D.
des
t
nom
les
bres
dans
ottan
rotations.
ts
p
p
les
our
3D
appro
us
c
thèse
her
cinq
le
plus
con
duction
tin
des
u
des
p
espaces
ose
le
des
.
problèmes
2
de
état
précision.
rotations
P
tation
our
thèse,
ces
nous
raisons,
donc
nous
trés
a
le
v
elopp
ons
t
c
rotations
hoisi
les
duran
discrets
t
sur
cette
compréhension.
thèse
nous
de
principalemen
nous
in
concen
aux
trer
c
sur
qui
les
ten
espaces
la
discrets
tin
et
de
de
rotation
n'utiliser
les
que
discrets.
des
eet,
en
ces
tiers
eectuer
duran
rotations
t
image
les
v
calculs.
deux
Dans
très
le
c
domaine
p
de
donner
la
même
vision
Cette
par
est
ordinateur,
par
la
angles
rotation
harnières.
est
de
une
angles
transformation
p
requise
de
p
une
our
qui
de
les
nom
résultats
breuses
la
applications.
con
Dans
ue
la
sans
plupart
v
des
recours
applications,
calculs
la
ts.
rotation
angles
utilisée
ermetten
est
aussi
la
décrire
rotation
rotation
euclidienne
men
discrétisée.
qui
Les
toutes
résultats
rotations
donnés
ossibles
pa