La géométrie des pixels

La géométrie des pixels

Conférence APMEP Octobre 2008

Pr. Eric ANDRESLaboratoire XLIM-SIC - Université de Poitiers

Que dire de la géométrie euclidienne classique ?

Selon Euclide, la géométrie est la science mathématique des figures du plan et des volumes de l’espace. Descartes et Fermat ont fondé la géométrie analytique avec les coordonnées et des équations.

Cela a été fondamental pour le développement du Calcul (en particulier en physique).

De nos jours nous avons de nombreuses géométries comme les géométries algébriques, différentielles, non-euclidiennes, …

Géométrie des Pixels

Et la géométrie « discrète » ?

Pour avoir une géométrie discrète, dans Zn, nous avons besoin d’objets (figures, volumes mais aussi transformations et opérations).

Similairement à ce qu’a fait Descartes, il est possible de décrire la géométrie discrète par des (in)équations : d’où le nom de

« Géométrie Analytique Discrète »

Nous nous intéressons en particulier aux calculs (en informatique avec applications en physique).

Les géométries discrètes algébrique, différentielles, non-Euclidienne, … ne sont pas définies.

Géométrie des Pixels

Pourquoi étudie-t-on la géométrie discrète ?

• Données obtenues pas acquisition

• Utile pour manipuler des images

• Accélération dans divers algorithmes en infographie

• Modélisation

• Volumes

• Phénomènes physiques

• Écoulement du temps Physique

discrète

Fondements théoriques :

Analyse non standard, théorie des nombres, informatique effective, modélisation…

Domaines d’applications :

Informatique graphique, modélisation, analyse d’image et reconnaissance de formes

Applications :

Géologie, imagerie médicale, débruitage d’image et de vidéo, outil de simulation de propagation d’ondes, …

Géométrie Analytique Discrète

Le discret : un monde bien étrange

Deux droites orthogonales sans intersection

Deux droites parallèles et non égales avec une infinité de points d’intersections

Le discret : un monde bien étrange

Regardons à présent cette droite

Le discret : un monde bien étrange

Intersectée avec une deuxième droite

Le discret : un monde bien étrange

Une intersection non connexe et dans le cas général l’intersection peut avoir un nombre

arbitraire de points

Le discret : un monde bien étrange

Relations Continu - Discret

Il existe une relation « paramétrable » entre les deux

Relations Continu - Discret

Taille des voxels diminue plus vite que l’épaisseur de la droite n’augmente

Relations Continu - Discret

A la limite on obtient une droite continue

Relations Continu - Discret

Continu•

•

•

•

•

•

•

•

Discret

Objet A avec propriété 1,2,3, …

Objet A1

Avec prop 1,3,15, …

Objet Ak

Avec prop k1, k2, k3, …

Bases de topologie discrète

4-voisinage 8-voisinage

6-voisinage 18-voisinage 26-voisinage

Bases de topologie discrète

8-tunnel

4-tunnel

26-tunnel

18-tunnel

6

Bases de topologie discrète

Chemins 4 et 8 connexes fermés de « Jordan »

Intérieur et extérieur non 4-connexes

Pas d’intérieur

Chemin 4-connexe fermé Chemin 8-connexe fermé

Bases de topologie discrète

Une solution : voisinage

différent pour la courbe et le

complémentaire

Courbe 4-connexe intérieur / extérieur 8-connexe

Courbe 8-connexe intérieur / extérieur 4-connexe

Bases de topologie discrète

Autre solution : Topologie de Khalimski-Kovalesky

Partition du pixel

SurfelLignel

Pointel

Bases de topologie discrète

Droite analytique discrète

Equation analytique :

Représentation en compréhension

a,b entiers, a/b pente de la droite, épaisseur arithmétique, c constante de translation.

J.-P. Reveillès (1991)

Propriétés

0 1 2 3 4 5 6 7

1

0

2

3

4

5

0 5x – 7y < 123456

< sup(|a|,|b|)

droite non connexedes 1-tunnels

7

= sup(|a|,|b|) = 7

droite 8-connexedes 0-tunnels

891011

= |a|+|b| = 12

droite 4-connexePlus de tunnels

12

0 5 10 15 20 25 30 35

-7 -2 3 8 13 18 23 28

-14 -9 -4 1 6 11 16 21

-21 -16 -11 -6 -1 4 9 14

-28 -23 -18 -13 -8 -3 2 7

-35 -30 -25 -20 -15 -10 -5 0

Propriétés de la droiteOn a la relation

Et donc si on se limite aux droites naïves on voit assez facilement que

On suppose ici 0 < a < b et pgcd(a,b)=1.

On a

Où est le reste de la division.

Propriétés de la droite

Prenons a/b = 5/17 et la suite y(xi) = {axi / b}

xi0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

y(xi) 0 0 0 0 1 1 1 2 2 2 2 3 3 3 4 4 4

{axi / b} 0 5 10 15 3 8 13 1 6 11 16 4 9 14 2 7 12

0

0

4

16

Propriétés de la droite

c c c d c c d c c c d c c d c c dA tout rationnel a/b Christoffel associe les lettres L1…Lb à la suite r(i)={ai/b} avec i=1,…,b où une lettre Li vaut “c” si r(i)<r(i+1) et “d” sinon.

Comme les deux dernières lettres valent tjs “dc” on appelle le mot de Christoffel le mot Ch(a/b) = L1… Lb-2

On retrouve bien sur les paliers de la droite discrète.

5 / 17

Propriétés de la droite

Il existe un rapport entre le mot de Christoffel et le développement en fraction continue de = a/b avec 0<<1.

Soit = [s,s1, …, sn] le développement en fraction continue de a/b. Le mot de Christoffel Ch(a) est construit avec les suites de mots n, Cn, dn

Propriétés de la droite

Avec

On a donc

s=3, s1=2, s2=2 et n=2.

Le mot de Christoffel est donc Ch(5/17)=c1 2 1

avec =c2, c1=c2d, d1=c3d

1=c1=c2d, c2=c1d1=c2dc3d, d2=c12d1=c2dc2dc3d

2=c2=c2dc3d.

Propriétés de la droiteLe mot de Christoffel est donc Ch(5/17) = c1 2 1

avec =c2, c1=c2d, 1=c2d, 2=c2=c2dc3d.

Soit au final Ch(5/17) = c2d.c2dc3d.c2d.c2

Si on code dans c.Ch(5/17).d = cccdccdcccdccdccd le mot c3d par L et c2d par C

On retrouve un condensé du mot et surtout :

L C L C C

5 / 17

Propriétés de la droite

Propriétés de la droite

Applications Quasi-Affines

[Reveilles 1991]

Definition :

En général

Avec la matrice et le vecteur

Applications Quasi-Affines

Definition : application contractante

Une application affine est dite contractante pour une constante de Lipschitz s<1 pour tout vecteur x,y nous avons

||f(x)-f(y)|| <s||x-y|| avec ||.|| la norme Euclidienne.

Théorème: une application affine f qui est contractante a un unique point fixe tel que f()=

Applications Quasi-Affines

Propriété : AQA contractante

Si l’application affine associée à une AQA F est strictement contractante alors F est aussi contractante en-dehors de la boule de rayon

Dynamique

Trajectoire du point (10,0)

La dynamique de l’AQA est définie par la suite Xn = F(Xn-1)

Dynamique

Bassin attracteur : un bassin attracteur d’un cycle limite est la réunion de tous les arbres attachés au cycle.

Z2 est décomposée en bassin d’attracteur

Dynamique

• a 1 unique point fixe : (0,0)

Pas d’autres cycle limite.

• a 2 points fixes : (0,0) et (0,-1)

• Pas d’autres cycles limites.

•

a 5 points fixes :

(0,0);(-1,-1);(0,-1);(1,-1);(0,-2)

Dynamique

•

a 32768 points fixes.

• a 1043 3-cycles et l’origine comme

point fixe

Dynamique

Dynamique

Autour de l’origine il y a un 3-cycle, 5-cycle, 7-cycle, 11 –cycle, 15-cycle, …

Dynamique

Seulement 1 seul bassin attracteur infini. La couleur représente la distance à l’origine qui est l’unique point fixe.

Dynamique

Quatre bassins attracteurs infinis

Dynamique

La couleur donne la distance au point fixe

Application Quasi-Affine

Di

D'j T (i,j)-1

F(x,y) =

Pavages

Le pavé P0,0 est égal à l’intersection entre D0 et D’0

A(2,2) appartient à l’intersection de D0 et D’1.

L’image de A par l’AQA est par conséquent (0,1).

Def. Pavé

Pi,j = Di D’j = F-1(i,j)

Cas plus général : Nombre de pavés

Si = ad-bc Alors tous les pavés sont identiques et contiennent points.

Le nombre de pavés different à l’ordre 1 est égal à

Avec = ad-bc.

Exemples

= 15+6 = 21

Soit ’= 21 / gcd(14,21) = 3

Exemples

= 5+6 = 11

Soit ’= 11 / gcd(11,11) = 1

Applications Quasi-Affines

Definition : Un pavé d’ordre 2 est l’ensemble des points dont l’image par l’AQA appartient au pavé d’ordre 1 pour l’indice i,j

Il y a ’2 pavés distincts à l’ordre 2

Exemples

= 1+1 = 2

Soit ’= 2 / gcd(2,3) = 2 4 paves à l’ordre 2

Exemples

= 1+1 = 2

Soit ’= 2 / gcd(2,3) = 28 pavés différents à l’ordre 3

Exemples

Ordre 1 Ordre 2

Ordre 3 Ordre 4

Ordre 5Ordre 7

Plans discrets

Equation analytique :

Représentation en compréhension

Epaisseur arithmétique : = B - A Reveillès (1991)

Propriétés

0 2x+5y+9z < 1

0 2x+5y+9z < 2

Propriétés

0 2x+5y+9z < 3

Propriétés

0 2x+5y+9z < 4

Propriétés

0 2x+5y+9z < 5

Propriétés

0 2x+5y+9z < 6

Propriétés

0 2x+5y+9z < 7

Propriétés

0 2x+5y+9z < 8

Propriétés

0 2x+5y+9z < 9

Propriétés

0 2x+5y+9z < 10

Propriétés

0 2x+5y+9z < 11

Propriétés

0 2x+5y+9z < 12

Propriétés

0 2x+5y+9z < 13

Propriétés

0 2x+5y+9z < 14

Propriétés

0 2x+5y+9z < 15

Propriétés

0 2x+5y+9z < 16

Propriétés

0 2x+5y+9z < 16

Propriétés

Cercles Analytiques Discrets

Cercle discret de Bresenham (1977)

résultat d'un algorithme d'approximation d'un cercle euclidien

Problèmes :

• rayon uniquement entier

• épaisseur entière = 1

• points n'appartenant à aucun cercle concentrique

• centre uniquement entier

0 1 2 3 4 5

Définition des hypersphères analytiques discrètes

Équation analytique :

Représentation en compréhension

[Andres 89,97]

Hypersphères analytiques discrètes

Propriétés

0 1 2 3 4 5

• Centre, rayon, épaisseur, quelconque

• définit en dimension n

• Pavage de l'espace par hypersphères concentriques

• Algorithme simple 2D suffit

• Une hypersphère d'épaisseur est k-séparatrice et

au moins (n-k)-connexe (pour n 3)

• Un cercle d'épaisseur 1 est au moins 0-connexe

ExempleSphères de centre (0.1,0.3,0.5) et de rayon k+0.8

• Projet transverse

Géométrie discrète Propagation d’ondes

• But : présenter la propagation d’ondes d’une manière pédagogique d’une manière « graphique »

Exemple d’application :Propagation d’ondes discrètes

Modélisation géométrique

Droite analytique discrète Cercle analytique

discret

Polygone + Front d’onde

Algorithme de propagation

Source E Point d’observation P

Energie totale

onde n°1

onde n°2

onde n°3

Pointeur d’onde

Type d’interaction

Coeff de divergeance

Valeur de la fonction d’onde

Valeur du champ électrique

Liste des points d’interactions Liste des points d’interactions Liste des points d’interactions

Q1Q2

Q3

E E Q1 Q3Q2E

Point P

Résultats

Hypersphères

Hypersphères analytiques discrètes

Hypersphères

Hypersphères analytiques discrètes

Hypersphères

Hypersphères analytiques discrètes

Approche classique

Approche Analytique discrète

Projet à très long terme

« Unifier » les géométries