BIBLIOGRAPHIE Image Numérique - …bigbozoid.free.fr/CoursLICENCE3/IMS/COURS_IN/Cours...les pixels noirs sont connexes donc l’image est adaptée à l’impression. Inconvénient

1

Image Numérique

Carole Blanc

22Image NumériqueImage Numérique

BIBLIOGRAPHIE

•J.D. FOLEY, A. VAN DAM, S.K. FEINER, J.F. HUGHES & R.L. PHILIPS, Introduction à l'infographie, Addison Wesley, 1995, 2-87908-058-4

• J.D. FOLEY, A. VAN DAM, S.K. FEINER & J.F. HUGHES, Computer Graphics : Principles and practice, 2nd edition, Addison Wesley, 1996, 0-201-84840-6

• A. S. GLASSNER, Principles of digital image synthesis, Morgan Kaufman, 1994, 1-55860-276-3


Historique : la préhistoire

–50's : 1èresapplications graphiques : visualisation de résultats numériques sous forme de courbes (surfaces)

- pas de matériel spécialisé (télétypes, écrans)

- pas d'interactivité



–50's : 1èresapplications graphiques :

2



–55 : MIT : tube cathodique piloté par un ordinateur

1er écran graphique vectoriel (TX-0)a visualisation "fil de fer"

(wireframe) modèle pendant 15 ans



–55 : MIT : tube cathodique piloté par un ordinateur



–55 : armée EU - projet SAGE : localisation d'avions


Historique : les pionniers

–63 : Ivan Sutherland (PhD MIT) a Sketchpad- système interactif (matériel, logiciel)- création, manipulation et animation de

figures

3


Historique : les pionniers

– 60's : General Motors DAC-11er système de CAO (production de plans)Lockeed, Bell,


Historique : le matériel

–1ersécrans commercialisables65 : DEC 30, IBM 2250 (100 000 $), CDC

–1ersécrans permanents 68 : Computer Designs ART (15 000 $)70 : Tektronix 4010 (5 000 $)

tablette, joystick, boite à boutons

–70's : diminution du coût du hardwareécrans matriciels, couleurs


Historique : la révolution

–75's : apparition des micro-ordinateurs•- Apple, Atari, Amiga, IBM …

•- possibilités graphiques (Apple II : 512 x 192, 16)

• a développement de logiciels (jeux, tableurs, …)

–75's : recherche communication homme-machine (CHM)

�a utilisation du graphisme (menu - souris)Xerox : SmallTalk 80 Mac Intosh


Jeux :

71 : Pong NolanBushnell

77 : Space InvadersSociété Taïto

81 : pacman

4


Jeux :

71 : Pong NolanBushnell

81 : pacman


Historique : l'évolution

–80's : apparition des stations de travail•- Sun, Apollo, Silicon Graphics, ...

•- capacités graphiques (1024 x 1024, 16 M)

•- bibliothèques graphiques (Core, GL, …)

•- CHM : multifenêtrage, menus - souris

•- architectures/processeurs spécialisés


Historique : l'évolution

–90’s : l’explosion •- croissance conjointe

•- capacités matérielles

•- nouvelles utilisations

•- besoins utilisateurs


Secteurs d’activité

–architecture, urbanisme : conception, implantation

– industries de fabrication : conception, contrôle qualité

– transport (avion, train, voiture …) : apprentissage

– loisirs : jeux, cinéma, pub, télévision

–médecine : diagnostic, geste chirurgical, enseignement

–environnement : météo, ressources naturelles

–chimie : conception molécule

–militaire : détection satellitaire, apprentissage

– ...

5


Qu’est-ce qu’une image numérique ?



Dynamique des fluides :contrôle de pression pour un turbo d’avion

Modèle cellulaire(géologie, géophysique)





011111100001000010000100001000010000100001000010000111111000

MémoireEcran

6



N

M

Une matrice de

N*M Pixels

(picture element)



Ecran Mémoire

1 bit / pixel

Bit-map


Qu’est-ce qu’une image numérique ?Bit-map : quelques exemples


Qu’est-ce qu’une image numérique ?Bit-map : quelques exemples

7



Mémoire

1 octet / pixel

256 niveaux de gris256 couleurs avec

LUT(Look Up Table)

8 - plans



Mémoire

3 octets / pixel

16 Millions de Couleurs.

Vraies couleurs

24 - plans

…


Problématiques liées aux pixels :=((

• représentation des détails : anti-aliasing


Problématiques liées aux pixels :=((

• représentation des univers continus :�tracé de droites ou de courbes crénelage

� discrétisation des méthodes de traitement etd’analyse (mathématiques discrètes)

8


Autres problèmes :

• L’œil humain …• Exigence des utilisateurs …


Modèles numériques

Images numériques (pixmap)

Objets réels, virtuels

Modélisation

Traitement

SynthèseAnalyse

InterprétationNumérisation O

péra

teur

Ord

inat

eur

Imagescodées

Codage

Décodage


Modèles numériques

Images numériques (pixmap)

Objets réels, virtuels

Modélisation

Traitement

SynthèseAnalyse

InterprétationNumérisation O

péra

teur

Ord

inat

eur

Imagescodées

Codage

Décodage


La couleur

• Codage des couleurs :

� Monochrome (Noir et Blanc) ou bitmapPréparation des impressions.

� 8-plans : 256 niveaux de gris ou couleurs� LUT : Table de clés pour choisir 256 couleurs

parmi 16 Millions

• Quantification des couleurs : ou comment réduire intelligemment le nombre de couleurs dans un image.

• Modèles de couleurs : RGB, HSV,…

9


Quantification des couleurs : NG vs NB

Point de départ : une image en NG(256 possibles)

Point d’arrivée : une image NB


Quantification des couleurs :NG vs NB

Point de départ : une image en NG(256 possibles)

Point d’arrivée : une image NB



1ère idée: représenter les NG par des motifs en noir et blanc

Clustering

Motif = matrice de pixels NB de petite taille.Plus il y a de pixels blancs plus les niveaux de gris représentés sont clairs. Et vice et versa.

Question : Dans quel ordre doit-on allumer les pixels pour former les différents motifs ?



1ère idée: clustering

Simulation du procédé offset de l’imprimerie : les motifs représentent des taches d’encre de plus en plus grosses en quinconces.

N

n=N/2

10





N

n=N/2





N

n=N/2





N

n=N/2





N

n=N/2

11



1ère ideé: Clustering


N

n=N/2





N

n=N/2





N

n=N/2





N

n=N/2

12





N

n=N/2n = 3 donne 19 motifs

Dans le cas général :

12

2

+Nmotifs



1ère idée: Clustering

Simulation du procédé offset de l’imprimerie : l’algorithme

�Définir les différents motifs

�Partager l’image à traiter en morceaux de taille N*N pixels

�Calculer pour chaque morceaux le NG moyen.

�Choisir le motif correspondant à ce NG.

�Remplacer le morceau de l’image par le motif.



1ère idée: Clustering

Simulation du procédé offset de l’imprimerie : exemple



1ère idée: représenter les NG par des motifs en noir et blanc

Simulation du procédé offset de l’imprimerie :

Avantage : les pixels noirs sont connexes donc l’image est adaptée à l’impression.

Inconvénient :Peu de motifs réalisables par rapport à la taille de la matrice

13




On oublie la contrainte de l’offset. On allume les pixels un par un pour définir les motifs.Une matrice carrée de taille N donne N*N+1 motifs possibles définis avec la matrice de Dither (tremblé ordonné) :

=

=

++++

=

11

11

13

20

1434

2404

2

2

L

MOM

L

n

nnnn

nnnnn

UD

UDUD

UDUDD





=

513715

91113

614412

10280

4D







2ème idée: dithering

Algorithme : Pour un morceau de n*n pixels de l’image, on change le NG de chaque pixel en ajoutant un pseudo-bruitcalculé avec la matrice de Dither.On seuille chaque NG modifié à 0.5

5.02

2/1),(

),(

−+n

jiDjiNG n

14



2ème idée: dithering



Inconvénients :Clustering et Dithering génèrent des motifs réguliers

Autre idée : …



Diffusion de l’erreur : Floyd et Steinberg

Algorithme : �Balayage de l’image pixel par pixel

�Pourchaque pixel :Si NG < 0.5

alors noir (0)sinon blanc (1)

�Evaluation de l’erreur commise lors du seuillage.�Répartition de cette erreur sur les pixels voisins

non encore traités




Algorithme : �Balayage de l’image pixel par pixel

ligne par ligne de gauche à droite et de haut en bas.

ligne par ligne de gauche à droite puis de droite à gauche et de haut en bas (zigzag).

Hilbert, …

15




Algorithme : �Répartition de cette erreur sur les pixels voisins

non encore traités

3/165/163/16

5/16




Algorithme : �Répartition de cette erreur sur les pixels voisins

non encore traités

1/165/163/16

7/16



Diffusion de l’erreur : Floyd et SteinbergExemple :



16




Inconvénient : On ne peut pas traiter une partie de l’image

Idée : avoir des méthodes locales …


Quantification des couleurs : 8 vs 24 plans

Hypothèse : on travaille avec la repésentation RGB des couleurs

• R = red (rouge) sur un octet.• G = green (vert) sur un octet.• B = blue (bleu) sur un octet.

La couleur de chaque pixel est représentée par 3 octets : image en 24 plans.



Axe de gris

(0 ,0 ,0)Rouge(255,0,0)

Bleu(0,0,255)

Vert(0,255,0)

Jaune(255,255,0)

Cyan(0,255,255)

Magenta(255,0,255)

Blanc(255,255,255)

Noir



1ère idée : seuillage brut

• Pour chaque composante (RGB) d’une couleur faire un seuillage à 6 niveaux :

0 255

51

204

153

102

255

reste 216 couleurs différentes au final

17



2ème idée : seuillage amélioré

• Même principe en tenant compte des caractéristiques de l’œil humain : seuillage à 8 niveaux pour le rouge et le vert, à 4 niveaux pour le bleu: 256 couleurs au final

0 255

170

85

255

0 255

36

182

109

73

255

146

219



3ème idée: tenir compte des caractéristiques de l’image

• seuillage à 32 niveaux par couleur R G B reste 32768 couleurs possibles (R’,G’,B’)

• établir l’histogramme des 32768 couleurs possibles

n

H ''*32'*1024 BGRn ++=H[n] = H[n] + 1

�Pour chaque pixel de l’image

�Choisir les 256 couleurs Finales. Comment ?




Choix des 256 couleurs sur l’histogramme :

• Popularité: 256 plus fréquentes

• Diversité:

1. la plus populaire

2. la plus distante de 1


…

256. La plus distante de 255




Choix des 256 couleurs sur l’histogramme :

• Bradley :

1. la plus populaire


3. retour à 1

18


Quantification des couleurs : 8 vs 24 plans4ème idée: Median Cut ( Heckbert 82)

• seuillage à 32 niveaux + histogramme

• partage du cube RGB en deux selon l’axe des rouge en 2 régions contenant le même nombre de pixels. Pareil selon l’axe des verts et bleus. On a 8 « sous-cubes » contenant chacun le mêmenombre de pixels.

• On répète cette subdivision jusqu’à avoir 256 sous-cubes.

• Pour chaque sous-cube on fait la moyenne des couleurs présentent et on donne cette couleur à tous les pixels du sous-cube.



14984couleurs

65 couleurs

252couleurs


Quantification des couleurs : RGB vs NGris

NGris = 0.2999*R +0.587*G + 0.114*B

•Les coefficients sont issus de la sensibilité de l’œil humain

•Les niveaux de gris (NGris) sont invariants par cette transformation.Exemple :

Si R = G = B = x dans [0, 255]alors

NGris = (0.2999 + 0.587 + 0.114)x = x


Modèles de couleur :

• domaine complexe : –physique, physiologie, psychologie, culture, etc.

• couleur d'un objet dépend

– de l'objet (couleur, matière, réflexion/diffusion)– de la source qui l'éclaire

– de la couleur ambiante

– du système de perception humain

19


Modèles de couleur :

•Perception visuelle humaine :– vue et/ou perception : œil et/ou cerveau

– œil : nombre fini de récepteurs réagissant aux longueurs d'onde entre 380 et 770 nm

– perception

� dépend de la longueur d'onde (rouge, vert, bleu)

� plus sensible aux contrastes qu'aux différences absolues.

� dépend de la luminosité

� dépend du sujet (culture, âge, condition)


Modèles de couleur

Notions fondamentales–Physique:intensité, luminance, longueur d’ondes,…

–Psychologie de la perception : luminosité

–Chromatique :•teinte (hue) : (rouge, bleu …)

•saturation: mesure la différence entre une couleur et un NGris de même intensité

•clarté(lightness) : intensité lumineuse réfléchie

•luminosité(brightness) : intensité lumineuse émise


Modèles de couleur

• Quelques traductions : – colorimétrie :

•teinte : longueur d'onde dominante•saturation : pureté de la couleur•clarté ou luminosité : luminance

–lumière : énergie électromagnétique dont le spectre est compris entre 400 et 700 nm (violet -> rouge)


Modèles de couleur

• Cadre de travail:la rétine possède 3 sortes de cellules détectrices de couleurs :

•une pour le rouge (570 nm), appelés erythrolabes•une pour le vert (535 nm), appelés chlorolabes•une pour le bleu (445 nm), appelés cyanolabes

Que nous indique les courbes ci-dessus ?

20


Modèles de couleur

• Standardisation:La perception des couleurs diffère selon :

� Les individus

�Les périphériques d’affichage

En 1931 La Commission Internationale de l'Eclairage (CIE) propose une représentation standard indépendante des périphériques utilisés. Les critères sont basés sur la perception de la couleur par l'oeil humain


Modèles de couleur

•Standardisation:le système colorimétrique xyY représentant les couleurs selon leur chromaticité (axes x et y) et leur luminance (axe Y).


Modèles de couleur

•Standardisation:le système colorimétrique xyY représentant les couleurs selon leur chromaticité (axes x et y) et leur luminance (axe Y).

Spectres A : couleurs visiblesB : film couleurC : moniteurD : imprimante


Modèles de couleur

•RGB:

(0 ,0 ,0)Rouge(255,0,0)

Bleu(0,0,255)

Vert(0,255,0)

Jaune(255,255,0)

Cyan(0,255,255)

Magenta(255,0,255)

Blanc(255,255,255)

Noir

21


Modèles de couleur

•RGB: – modèle additif

– mélange d’ondes lumineuse

– adapté aux affichagesgraphiques

– certaines couleurs ne sont représentables.


Modèles de couleur

•CMY: Cyan - Magenta - Yellow

Rouge

Bleu

VertJaune

Cyan

Magenta Blanc(0,0,0)

Noir


Modèles de couleur

•CMY: – modèles soustractif

– mélange de pigments

– utilisé en imprimerie(CMYK).

Pourquoi K ?

– certaines couleurs ne sont pas représentables.


Modèles de couleur Modèles de couleur

Munsell, peintre américain (1858 - 1918), publie en 1915 son " atlas of the Munsell color system ".

Il présentait les couleurs sous forme d'un" arbre des couleurs" autour d'un axe vertical allant du blanc au noir

22


Modèles de couleur • HSL :Après la mort de Munsel, la Munsell color Cy continue ses travaux et publie, en 1929, le " Munsell book of colors " classification en 3 dimensions :

�teinte, Saturation

�Luminosité : R+V+BCette classification est, encore actuellement, très utilisée, enparticulier en géologie et en archéologie.


Modèles de couleur

• HSL :


•HSV: – Hue

–Saturation

–Value max(R, V, B)

S

V

H

Modèles de couleur


• YUV, YIQ :TV : YUV (PAL), YIQ (NTSC)

3 primaires : luminance et 2 chrominance

Modèles de couleur

23


Traitement d’image


Transformation géométrique

Exemple :



Exemple :



Question :Comment fait–on cette transformation ?

NONf

Pourquoi ?

24



f -1

Pour chaque pixel dans l’image finale on cherche quel est le pixel de l’image initiale qui lui correspond. Il faut définir f -1



Même principe pour une rotation

f -1

f -1 est la rotation inverse

Image finale Image originale



Transformation optique 1 pour 1 :

La couleur de chaque pixel de l’image est recalculée en fonction de sa valeur d’origine

Exemple : en niveaux de gris

0 255

255

NG

Inversion vidéo


Transformation optique




0 255

255

NG

Eclaircissement

25






0 255

255

NG

Correction gamma

γ/1)( ttf =1>γ



Transformation optique n pour 1 :

La couleur de chaque pixel de l’image est recalculée en fonction des valeurs des pixels voisins dans l’image d’origine.

Pixel Pij

Fenêtre de convolution

C9C8C7

C6C5C4

C3C2C1Masque des Coefficients :





Exemple :Si Nij et le niveau de gris du pixel Pij on fait un calcul du type suivant

ij

ij

ijijij NcN ∑

=

=

=9

1

'





Exemple : détection de contour

On doit extraire une grandeur qui représente les variations de NG.Quelle est cette grandeur ?

26





h

xfhxfxf

)()()('

−+≈

Dans un espace discret on fera :

),()1,(

),(),1(

yxNGyxNGV

yxNGyxNGV

y

x

−+=−+=





Masque de Sobel

10-1

10-1

10-1

111

000

-1-1-1

Vx Vy





Masque de Prewitt

10-1

20-2

10-1

121

000

-1-2-1

Vx Vy





27




Exemple : Filtre passe-bas (blur)

1/91/91/9

1/91/91/9

1/91/91/9




Exemple : filtre passe-bas (blur)



Transformation optique n pour n :

Principe ?


Synthèse 2D

28


Synthèse 2D• Tracé :

• Découpage :

• Remplissage :


Synthèse 2D : problème



Exemple: tracé une droite en vectoriel

%!PS-Adobe-2.0 EPSF-2.0%%BoundingBox: 0 0 400 400

%% Version encapsulee (PostScript 2)

newpath0 0 moveto400 200 lineto

strokeshowpage



Exemple: tracé une droite sur une matrice de pixels

29



Exemple: tracé une droite sur une matrice de pixels

Algorithmes adaptés à la définition matricielle.


Synthèse 2D : tracés

� primitives de base : points, segments, cercles etc.

� usage massif � forte optimisation

� choix des pixels à allumer � approximation


Synthèse 2D : tracés de droite

Cas triviaux

�Segments horizontaux ou verticauxpour x = xD à xF faire :

afficher (x , yD)

�Segments diagonauxi = 0pour x = xD à xF faire :

afficher (x , yD + i)i = i + 1



Cas général :

Méthode directe : utilise l'équation de la droite :

y = a x + b

Algorithme : a=(y F - y D)/(x F - x D)b=y D-a*x D

pour x = x D à x F fairey = a * x + bafficher (x , y)

30



Cas général :

•Inconvénients méthode directe :

– opération couteuses (*, /)

– arrondis

– trous : si |a| > 1

• Exemple :D (1 , 1) F (3 , 6)

a = ( 6 - 1) / (3 - 1) = 5/2

b = 1 - 5/2 * 1 = - 3/2

( x1 , y1 )= (1,1) ( x2 , y2 )= (2, 7/2)

( x3 ,y3 ) = (3, 6)



Cas général :

Améliorations

� si |a| > 1 on parcourir les y et calculer les x

� remplacer les * et / par des + et –� calculs incrémentaux



Méthode incrémentale : Principe

Calculer l’étape i en fonction de l'étape i-1autrement dit calculer Pi+1 en fonction de Pi

Exemple: dans le 1er octantx i+1 = x i + 1y i+1 = a x i+1 + b

= a (x i + 1) + b = y i + a

généralisable à tous les octants par symétrie

123

4

56 7

8



Méthode incrémentale : 1èreversion

a = (yF-yD)/(xF-xD)y = yDpour x = xD à xF faire :

afficher (x,y)y = y+a

Inconvénients : additions de réels, arrondis

31



Méthode incrémentale : 2èmeversion Bresenham(65)

Principe : minimiser la distance entre le segment réel et le segment tracé

Exemple: 1er octant

si |a| < 1/2 alors choisir

Pi+1 (xi + 1, yi)

si |a| > 1/2 alors choisir

Pi+1 (xi + 1, yi + 1)

en pratique, on testera le signe d'une erreur (a-1/2)

Pi Pi+1 ?

Pi+1 ? a=1/2



•Algorithme de Bresenham: versionβ octant 1

e = -1/2a = (y F - y D) / (x F - x D)y = y D

pour x = x D à x Ffaire

si e > 0 alors

y = y + 1e = e - 1 + a

sinon

e = e + aafficher (x , y)



•Algorithme de Bresenham: versionβ octant 1

•Exemple :• D (1 , 1) F (4 , 3)

• a = 2/3

• e = -1/2

• y = 1

•Problème : division pour calculer « a » + opérations réelles sur l'erreur

•Idée : comme on ne teste que le signe de « e »multiplier « e » par une constante positive 2 * (xD - xF)

3

4

1/6

4

221yi

321xi

3/6-1/61/6e

321i



•Algorithme de Bresenham: 1er octant

Dx = xF - xDDy = yF - yDe = - Dxy = yDpour x = xD à xF faire :

si e > 0 alors

y = y+1e = e+2*(Dy-Dx)

sinon

e = e+2*Dyafficher (x , y)

Rq : Coût optimisé

32


Synthèse 2D : Découpage (clipping)

• Objectifvérifier qu'un affichage reste à l'intérieur de l'écran

• Motivationséconomiser des opérations inutiles

• Extensionen 3D : éliminer les calculs en dehors de l'espace visible



•Méthodes :–Points : on teste point par point l'appartenance à l'écran

–Segments : il existe 4 familles de droite

1: segment visible

1 2 : segment invisible23 : segmentpartiellement visible

3 4 : segmentpartiellement visible

4

Idée : tester les extrémités du segment



•Méthode: Cohen-SutherlandBasée sur une décomposition du plan en 9 régions repérée par un code binaire.

•la première valeur = 1 si x < xmin,

•la deuxième valeur = 1 si x > xmax,

•la troisième valeur = 1 si y < ymin,

•la quatrième valeur = 1 si y > ymax.



•Méthode: Cohen-Sutherland

Simple pour 3 cas :

C(D) = C(F)= 0000[DF] est visible cas 1

C(D) ou C(F) est 0000[DF] en partie visible cas 2

C(D)&&C(F) ≠ 0000[DF] est invisible cas 3

33



•Méthode: Cohen-Sutherland

Dernier cas : incertain.

• On calcule l’intersection Idu segment [DF] avec une droite qui formentla fenêtre de clipping.

• On traite le segment [DI]ou [IF] obtenu

I



Cas des polygones:

• si l'on veut simplement afficher le contour, un découpage coté par coté suffit.

• si l'on veut ensuite traiter le polygone (le remplir), il faut s'assurer de conserver la connexité



Cas des polygones: Sutherland - Hodgman

Idée : découpe du polygone par chacun des cotés de la fenêtre.Mise en œuvre : parcours de la liste des cotés,construction d'une liste intermédiaire.

4 cas possibles :

Si

Sj

(1)

Si

Sj

Sk

(2)

Si

Sj

(3)

Sj

Si

Sk

(4)



Cas des polygones: Sutherland – HodgmanAlgorithme : L = liste ordonnée des sommets du polygonepour chaque coté de la fenêtre faire :

NL = {}pour chaque sommet Si de L faire :

si (2) alors NL = NL U {Sk , Sj}si (3) alors NL = NL U {Sj}si (4) alors NL = NL U {Sk}

L = NL

Si

Sj

(1)

Si

Sj

Sk

(2)

Si

Sj

(3)

Sj

Si

Sk

(4)

34



Cas des polygones: Sutherland – Hodgman

Exemple

S1

S2

S3

S4

S5


Synthèse 2D : Remplissage

Introduction• 1èresimages : silhouettes en fil de fer (technologie vectorielle) � pas de remplissage

• évolution technologie : matriciel � évolution algorithmique

� images "remplies"

• 2 familles d'algorithmes�contours affichés sur l'écran

�contours représentés en mémoire(liste de sommets, courbe paramétrique, etc)



Contours affichés

� Point à point1. parcours de la fenêtre ligne par ligne de haut en

bas (scan-line).

2. test de l'appartenance d'un point à la surface.

3. si on détecte un point allumé alors tous ses voisins (dans le sens du balayage) sont à allumer jusqu'au prochain point déjà allumé



35



Contours affichés

•Améliorations :� traçage de segments plutôt que de listes de points

� rectangle englobant pour minimiser le parcours

� détection des concavités, triangulation



Contours affichés:

� Inondation

• on part d'un point interne au polygone (germe)

• on essaie de colorer ses voisins

• on itère le procédé (récursion)



Contours affichés:

� Inondation variante :1. tracer des segments dans les 4 directions

2. empiler les voisins non traités

3. si frontière alors redémarrer d'un point dépilé



Contours affichés:

� Attention à la connexité du contour :Contour 8-connexe � remplissage 4-connexe

Contour 4-connexe � remplissage 8-connexe

Sinon trou ou fuite.

Contour et remplissage4-connexe : trou

Contour et remplissage 8-connexe : fuite

36



Contours stockés: Principe

– calculer et stocker les extrémités des segments

– principe : remplir par une série de segments horizontaux

142142

143143Image Numérique : Modélisation géométriqueImage Numérique : Modélisation géométrique

DéfinitionsDéfinitions

Modélisation géométrique:

Création d'une description numérique des caractéristiques géométriques d'un objet 3D sous la forme d'un fichier informatique.

Modeleur :Logiciel permettant de réaliser la modélisation géométrique et optique d'une scène ou d'un objet 3D.

Exemple: Maya, SoftImage, Rhyno, etc


HistoriqueHistorique

Années 60 :Premiers travaux issus du monde industriel

Débuts simultanés dans quatre entreprises :

• Constructeur Boeing (USA) John Ferguson

• Constructeur Ford (USA) Steven Coons

• Constructeur Citroën (France)Paul de Casteljau

• Constructeur Renault (France) Pierre Bézier

1974 :Première conférence universitaire

• University of Utah R. Barnilh & R. Riesenfeld

37



Premiers travaux :

• Formes simples

• Visualisation en fil de fer



Aujourd'hui :

• Formes complexes

• Visualisation réaliste

© Pixar 1998


Domaines d'applicationDomaines d'application

Architecture Cinéma Mécanique

Médecine Jeux vidéo Sculpture virtuelle

Urbanisme ...


Domaines d'applicationDomaines d'application

• Architecture

• Mécanique

• Médecine

• Urbanisme

• Cinéma

• Jeux vidéo

• Sculpture virtuelle

avec sans

Contraintes physiques

38


ClassificationClassification

Il existe 4 familles de modèles :

• Volumique continu

• Volumique discret

• Surfacique continu

• Surfacique discret


Volumique continuVolumique continu

On définit un volume V avec une fonction F dite d'intérieur/extérieur :

( ) ( ){ }0,,/R,, 3 ≤∈= zyxFzyxPV

On dit que V est défini de manière implicite, pourquoi ?


Volumique continu : ExemplesVolumique continu : Exemples

Sphère :rayon r centre (a,b,c)

Ellipsoïde :rayons (p,q,r) centre (a,b,c)

( ) ( ) ( ) ( ) 2222,, rczbyaxzyxF −−+−+−=

( ) ( ) ( ) ( )2

2

2

2

2

2

,,r

cz

q

by

p

axzyxF

−+−+−=



Equipotentielles :

• Sources de potentiel :

• Seuil : T

• Loi de décroissance :

( )iiii zyxP ,,

( )zyxf i ,,

( ) ( ) TzzyyxxfzyxFN

iiiii −−−−=∑

=1

,,,,

39



Equipotentielles :

• Sources de potentiel :

• Seuil : T

• Loi de décroissance :

( )iiii zyxP ,,

( )zyxf i ,,



Equipotentielles :


Volumique continuVolumique continu

Inconvénients:

• Pas de calcul simple d'un point sur la surface.Conséquences ?

• Pas de paramétrisation.Conséquences ?

Avantages :

• Stockage compact.• Bonne gestion des contacts entre volumes.• Bonne adaptation aux opérations booléennes.


Volumique discretVolumique discret

On échantillonne un volume V en une liste de N volumes

élémentaires: vi

vi : Souvent parallelépipédiques et alignés le long des axes.

UN

iiv

1=

=V

Quel nom portent ces volumes élémentaires ?

40



Décomposition uniforme

Volumes de taille fixe

Grille 3D qui s'appuie sur le volume englobant de l'objet



Décomposition adaptative

Subdivision récursivedu volume englobant

Arbre octal



Arbre octal :

IntérieurExtérieurMixte, à subdiviser


Volumique discretVolumique discretInconvénient:

• Coût de stockage.

• Difficulté d'édition.

• Définition approximative.

Avantage:

• Applicable à n'importe quel objet.

• Facilité de calcul des propriétés.

• Facilité de réalisation des opérations booléennes.

Utilisation :

• Imagerie médicale.

• Géologie, météorologie,...

41


Surfacique continuSurfacique continu

On définit une surface S avec une équation explicite S(u,v)dépendant de 2 paramètres compris dans [0,1]

( ) ( ) [ ] ( ) ( ){ }zyxvuSvuRzyxP ,,,,1,0,/,, 23 =∈∃∈=S

On dit que S est définie de manière explicite, pourquoi ?


Surfacique continu : ExemplesSurfacique continu : Exemples

Sphère :rayon r centre (a,b,c)

Ellipsoïde :rayons (p,q,r) centre (a,b,c)

( )( ) ( )( ) ( )( )

+++

=vrc

uvrb

uvra

vuS

πππππ

cos

2sinsin

2cossin

,

( )( ) ( )( ) ( )( )

+++

=vrc

uvqb

uvpa

vuS

πππππ

cos

2sinsin

2cossin

,



Courbes B-spline:

• Points de contrôle : Pk

• Fonctions de base de degré p-1 : )(, tN pk

( ) ( ) k

n

kpk PtNtC ∑

=

=0

,



Courbes B-spline :

P0

P6

P4

P3

P2P1

P5

42



Autres fonctions de base �� Courbes cardinale spline :

P1

P0

P5P4

P3

P2

P6



Surfaces B-splines :

• Points de contrôle : Pij

• Fonctions de base :

p-1 et q-1 sont les degrés des fonctions de base

( ) ( )vNuN qjpi ,, et

( ) ( ) ( ) ji

k

i

l

jqjpi PvNuNvuS ,

1 1,,, ∑∑

= =

=







43








Surfacique continu Surfacique continu

Inconvénients:• Stockage peu compact.

• Mal adapté aux opérations booléennes.

• Problème de continuité lors des raccordements

de surfaces.

Avantages :

• Définition explicite.

• Grande variété de formes.

• Visualisation interactive (Z-buffer).


Surfacique discretSurfacique discret

On échantillonne une surface S en une liste de N

facettes si.

Le plus souvent si est triangulaire. Pourquoi ?

∑=

=N

iis

1

S

44



Décomposition uniforme

Echantillonnage du domaine de variation du paramètre

dans le cas de surfaces paramétriques



Décomposition adaptative

Echantillonnage selon des critères géométriques :

courbure,...



Inconvénients:• Stockage peu compact.

• Mal adapté aux opérations booléennes.

• Définition approximative

• Surface C0

Avantages :

• Définition explicite.

• Applicable à n’importe quel objet.

• Visualisation interactive (Z-buffer).

176176

45

177177Image Numérique : construction 3DImage Numérique : construction 3D

Surfacique : Extrusion

• Extrusion simple :

Axe : Courbe « gauche »

Section: cercle

=)(

)(

)(

)(

vz

vy

vx

vA


Surfacique extrusion

• Extrusion simple :

Axe : Courbe « gauche »

Section: cercle



• Etape 1: on définit les parallèles sur l’axe par une suite v0 , v1 , … vp

A(v0 )

A(vk)

A(vp)



• Etape 2: pour chaque point A(vk) on cherche le plan orthogonal à l’axe pour placer la section (repère de Frenet local).

A(vk)

)()(

)()(

εε

+

+=kk

kkk

vAvA

vAvATr

� Vecteur tangent :

46



• Etape 2: pour chaque point A(vk) on cherche le plan orthogonal à l’axe pour placer la section (repère de Frenet local).

)( ε−kvA

)( ε+kvA

)( kvA

−kTr

+kTr

kN'r

� Vecteur quasi-normal :

−+

−+

−−=

kk

kkk

TT

TTN rr

rrr'

(Tk et N’k ne sont pas colinéaires )



• Etape 2: pour chaque point A(vk) on cherche le plan orthogonal à l’axe pour placer la section (repère de Frenetlocal).

kkk TBNrrr

∧=

�Vecteur binormal:

�Vecteur normal:

kkk NTB 'rrr

∧=

),,),(( kkkk BNTvArrr

Repère de Frenet :


Surfacique : Extrusion• Etape 2: pour chaque point A(vk) on cherche le plan

orthogonal à l’axe pour placer la section (repère de Frenet local).

A(vk)

kT

kN

kB

),,),(( kkkk BNTvArrr

Repère de Frenet :



• Etape 3: on trace la section échantillonnée dans ce plan.

kTr

kBr

kNr

)( kvA0u

1u

2u

3u

quM i

Dans le planles coordonnées d’un point M du cercle section sont données par :

),( kk BNrr

kkk BNvAMrr

.sin.cos)( θθ ++=

Avec : on calcule Mi

ii u.πθ =

θi

47



• Etape 4: on génère les facettes.


Cylindres Généralisés : extension

))(),(( ubuau a

Section de forme variable :

Exemple : jusqu’ici la section était circulaire :

==

uub

uua

ππ

sin)(

cos)(



))(),(( ubuau a

Section de forme variable :

klklk BubNuavAMrr

).().()( ++=

Calcul du point M :


Volumique: CSG

CSG : Géométrie Constructive des Solides

Principe : construire des solides de forme complexe en combinant des solides de forme simple (primitives) grâce à des opérations booléennes (union, intersection, différence)

Le solide est représenté par l’historique de sa construction sous la forme d’un arbre binaire dont les feuilles sont lesprimitives et les nœuds les opérations booléennes.

48


Volumique: CSG

Exemple: construction d’une bobine

Primitives :• 3 cylindres• 2 cones


Volumique: CSG



Volumique: CSG


http://www.limsi.fr/

192192

49

193193DéformationsDéformations

Déformation :

But : Enrichir la gamme des formes possibles.

Principe : Elaborer des formes complexes par transformations successives de formes simples.

194194Image Numérique : déformationImage Numérique : déformation

Déformations axiales : Barr 84

Exemples :

Original Taper Twist Bend


Déformations axiales : Barr 84

Exemples :

Original Taper Twist Bend


FFD : Sederberg & Parry 86

FFD = FreeForm Deformation

Principe et Analogie: • On plonge l’objet à déformer dans un bloc

de « plastique » flexible de forme parallélépipédique.

• On déforme le bloc de « plastique », l’objet inclus est également déformé.

Utilisation : Dans des soft de haut niveau (Maya, SoftImage, …)

Domaine d ’application: Tous les modèles

50

197197Image numérique : déformation ?Image numérique : déformation ? 198198Image numérique : déformation ?Image numérique : déformation ?

Bump mapping

Principe : Perturbation de la normale à la surface. [Blinn 78].La géométrie de l’objet n’est pas modifiée.

199199Image numérique : déformation ?Image numérique : déformation ?

Displacement mapping :

Principe : Perturbation de la surface le long de la normale [Cook 84].

La géométrie de l’objet n’est pas modifiée !

Documents

BIBLIOGRAPHIE Image Numérique - …bigbozoid.free.fr/CoursLICENCE3/IMS/COURS_IN/Cours...les pixels noirs sont connexes donc l’image est adaptée à l’impression. Inconvénient