Traitement des Images Click to edit Master title style · Réalité Augmentée Vision Robotique -opération Véhicules autonomes Vision Industrielle Inspection Montage Fabrication

Click to edit Master title style

MasterPro IICI - Option GTI - 2014/2015

Traitement des Images

Jean-Marc Vezien

[email protected]

2


Plan du cours

1. Introduction et notions fondamentales

2. Filtrage

3. Morphologie mathématique

4. Le système visuel

TDs: ImageJ (java)

Traitement GPU (GLSL)

3


Traitement des Images et Vision par Machine

1- Introduction

Jean-Marc Vezien

[email protected]

4


Introduction

• L’image a pris un rôle énorme dans les sociétés

humaine moderne depuis le Xxème siècle

L’image est un signifiant:

OU: détection, reconstruction,

analyse

Quoi: classification

Qui: Biométrie

5


Applications

Imagerie Imagerie Satellite

Imagerie Médicale

Multimédia Cinéma

Photo

Indexation web

Réalité Augmentée

Vision

Robotique Télé-opération

Véhicules autonomes

Vision

Industrielle Inspection

Montage

Fabrication

6


• Première images par ordinateur:

Sutherland, fin 60s.

• Première caméras électroniques (Vidicon):

60s.

• Premier capteur CCD (Bell): 1969.

• Premières applications: reconnaissance

de caractères, imagerie satellitaire.

Historique

E. Zajac, 1963

Hypothèse : Le monde se réduit à un ensemble de

caractéristiques « binaires » que l’on peut détecter:

problème d’intelligence artificielle.

R. A. Kirsch, 1957

7


Des pixels aux prédicats ?

Historique (2)

• Pas si simple ! Le monde n’est pas

binaire !

• Les pixels sont une représentation

« pauvre » du monde.

• Preuve: illusions d’optique

• La perception humaine se forme à

plusieurs échelles : groupements

perceptuels

8


D. Marr (1980): compare les systèmes de

vision au système visuel humain:

Approche «Bottom-up» : on construit des

représentations de haut-niveau à partir

d’indices locaux

points contours objects 3D

Perception 3d = Reconstruction 3d

Historique (3)

Cette approche est encore implicite dans de nombreux

travaux

9


• Approche moderne plus modeste: le contexte et

l’apprentissage sont essentiels

Les machines ne peuvent analyser toutes les situations

• Résoudre des taches concrètes dans des cadres

spécifiques.

• Utilisation d’information a priori (modèles 3d, modèles

statistiques …)

• Augmenter la complexité graduellement.

Historique (4)

10


Trois catégories de transformations:

Le traitement des images: image image

«image processing»

L’analyse d’images: image mesures

«image analysis»

L’analyse sémantique:

image description de haut niveau

«image understanding»

Taxonomie

11


Concepts fondamentaux du traitement d’images Images 2D (généralisation possible)

Image = fonction I(x,y)

I = amplitude = intensité (ou vecteur)

position (x,y) dans le plan cartésien.

Ex:

une photographie aérienne

un profil d'élévation d'un terrain

une carte topographique

= trois images différentes d'un même objet

Objet du cours

12


Image digitale I[m,n] =

Description dans un espace discret de R2 d’une

image continue I(x,y)

Amplitudes =

Réels (voire complexes) ou

Entiers = quantification des valeurs sur un ensemble

discret (ex: 24 bits)

Définitions

13


Définitions (2)

= longueur d’onde couleur (canal)

L=2B , B = nombre de bits

B=1 : image binaire

N lignes

M colonnes X

Z

Y

Valeur L(x,y,z, , t)

14


Traitement local notion de voisinage, généralement

rectangulaire

Traitement: types d’opération

Complexité de calcul croissante

=

15


Formats des images

• Résolution / Aspect ratio: Resolution/

Aspect Ratio

4:3 16:9 16:10 3:2 5:3 5:4

CGA 320 x 200

QVGA 320 x 240

VGA 640 x 480

NTSC 720 x 480

WVGA 854 x 450

WVGA 800 x 480

PAL 768 x 576

SVGA 800 x 600

XGA 1024 x 768

N/A 1152 x 768

HD 720 1280 x 720

WXGA 1280 x 800

WXGA 1280 x 768

SXGA 1280 x 1024

N/A 1366 x 768

N/A 1440 x 960

SXGA+ 1400 x 1050

WSXGA 1680 x 1050

UXGA (2MP) 1600 x 1200

HD1080 1920 x 1080

WUXGA 1920 x 1200

QXGA (3MP) 2048 x 1536

WQXGA 2560 x 1600

QSXGA (5MP) 2560 x 2048

3840 × 2160 4K (8.8 MP)

16


Formats 16:9 (ou 16/10) plus adaptés à la télévision.

Fréquence: 50/60Hz

HD ready: 1280 x 720 (mais peut afficher le Full HD)

720i: entrelacé, 2:1

720p : pas d’entrelacement

FULL HD : 1920 x 1080

1080p: pas d’entrelacement, 1:1

1080i: entrelacée, 2:1

(Rappel: SD = 720 x 576 en 2:1)

Formats des images (2)

17


SD

HDReady

Full HD

TP = total pixels (horizontal x vertical)

Vt = Rafraichissement image (Hz)

BPS = bits per sample (16 in general)

SD (entrelacé) : 99 MHz

HDReady (720p): 442 MHz

Full HD (1080p) : 995 MHz

http://www.hdtvexpert.com

Multibust (ref)

720p observé

Formats des images (3)

Bande passante: BW = (TP x Vt) * BPS (MHz)

18


ObjetSystème de prise

de vues

Numérisation :

échantillonnage

et quantification

Sources

d'éclairement

Energie

rayonnante

Image

analogiqueImage

numérique

Formation des images

19


P(x0,y0,z0) o

p(x,y)

f

z

x

point focal

plan focal

Projection perspective:

),(),(0

0

0

0

fz

yd

fz

xdpyxp

f = distance focale

Formation des images (2)

20


Imperfections des sytèmes (lentilles réelles):

Largeur de trou: défocalisation (flou)

Diffraction: aberrations chromatiques

Epaisseur de plaque: vignettage

Astigmatisme (irisations)

Formation des images (3)

21


Linéarité:

Sensibilité:

absolue : nombre minimum de photoélectrons détectables

relative S: nombre minimum de photoélectrons nécessaire pour passer d’un niveau de gris au suivant

30offsetgain

ac

gain

1S

Paramètres des capteurs

22


Bruit photonique :

T = temps d’observation

ρ = densité de photons par unité de temps.

Le bruit thermique

courant en l’absence de lumière = courant d’obscurité.

Refroidir le capteur.

dBTRSB )(log10 10photo

Bruits

4°C 25°C

23


Le bruit de lecture

dépend de la fréquence de lecture sur le

CCD. Pour des signaux faibles et des

fréquences de lecture importantes.

Le bruit d’amplification

bruit gaussien généré par les différents

étages d’amplification. Presque négligeable

désormais.

Bruits (2)

24


Le bruit de quantification

généré lors de la numérisation du signal en 2 B

niveaux discrets.

Pour B = 8 bits, RSB=59 dB (très grand)

dBBRSBquant 116

Bruits (3)

25


Dans la pratique, c’est le bruit

photonique qui produit le RSB le plus

faible, et est donc prépondérant.

Bruits: conclusion

26


Perte de luminosité non homogène (optique)

ijijjiajic ),(),(

Coefficients et estimés par calibration

Vignettage

27


Zone non sensible

Zone sensible

Format du pixel

%100oo

aa

YX

YXFrFacteur de remplissage:

Compromis entre efficacité et risque de "bavure"

http://www.photo-lovers.org/sensor.shtml.fr

28


Parfois X0/Y0 ≠ 1 (pixel non carré)

La forme du pixel peut conduire à des altérations

lors de la capture:

Estimation à l’aide de mires géométriques

Format du pixel (2)

29


CCD sensible aux IR (filtre)

Sensibilité spectrale

30


• 5 mégapixels = 2 592 x 1 944

• Zoom numérique jusqu'à 10x

Focale: 2.8-5,6/34 mm, ce qui

correspond à la focale de 35 mm

d'un 24 x 36

• vitesse d’obturation 1/1000s

• Taille d’une image ≈ 500 Ko.

• Séquences vidéo MPEG-4 de

résolution VGA (jusqu'à 30

images/sec), 60 s. max NOKIA N95 (2007) 120g, 8 Go,

Écran 240 x 320 pixels

Exemple (2007)

31


• 5 mégapixels = 2 584 x 1 938

• 2 appareils photos !

• Zoom numérique jusqu'à 14 x

Focale: 2.8 / 5.4 == 34mm

vitesse d’obturation ?

• Taille d’une image ≈ 500 Ko.


résolution VGA (jusqu'à 30

images/sec), 90 minute max,

avec flash.

NOKIA N97 (2011) 138g, 32 Go,

Écran 640 x 480 pixels

Exemple (2011)

32


• 8 mégapixels = 2 448 x 3264

• Front camera: 1.2 MPx

• Zoom numérique jusqu'à 14 x Focale: 2.8 / 5.4 == 33mm

Taille d’une image ≈ 800 Ko.


résolution HD (30 images/sec),

avec flash, zoom X3. Iphone 5s (2013) 112g, 64 Go,

Écran 1 136 x 640 pixels

Exemple (2013)

33


• 8 mégapixels = 2 448 x 3264

• Front camera: 1.2 MPx

• Zoom numérique = ?

Focale: 2.2 / 4.15 == 28mm

Taille d’une image ≈ 800 Ko.

• Séquences vidéo MPEG-4

1080p@60fps

720p@240fps

Avec flash, zoom X3.

Iphone 6 (2014) 129g, 128 Go,

Écran 1 334 x 750 pixels

Exemple (2014)

34


• Résolution : permet le zoom numérique

• Bande passante

UMTS 3G: 384 Kbps . Pratique: 64 à 128 kbps en émission et

128 à 384 kbps en réception

HSDPA (3G+): 7.2 Mbps (normalement).

4G : LTE-advanced = 100 Mbps. En pratique autour de 20 Mb/s

(5 à 10 en upload).

• Emettre une image, si 128 kbps -> 16ko/s -> 500/16 s = 30s !

• En 4G: 1/5 sec.

• Flash xenon Flash led (moins gourmand)

• Vidéo HD possible !

Evolutions

35


Image continue → image discrète

IMAGE CONTINUE fc(x,y) continue

x,y continus

IMAGE DISCRETE fd(xi,yi) continue

xi,yi entiers

Reconstruction spatiale

Echantillonnage spatial

Echantillonnage

Réciproque: reconstruction spatiale

36


Echantillonnage

37


Peigne de Dirac:

S(x , y) d(x i j

i

x , y j y )

S(x,y)

x

x

y

yvet

xuavec

vjvuiudvuSi j

22

),(),(

Distribution de Dirac

d(0)=1

d(n) = 0 pour n ≠ 0

1)( nnd

d

n

fd(x,y) = fc(x,y) S(x,y)

38


)()( uFxffF

)()(1

xfuFfF

dxexfuF uxi2)()(

F est une transformée bijective et unitaire (elle conserve la norme).

dueuFxf uxi2)()(

Transformée de Fourier continue

C’est une projection sur un espace de fonction

39


dxπuxxfidxπuxxfuF )2sin()()2cos()()( F(u) = F(u)ei (u )

Fourier de spectre)( uF spectredu complexe phase)( u

Transformation bidimensionnelle:

dydxeyxfvuF vyuxi )(2),(),(

dvduevuFyxf vyuxi )(2),(),(

Transformée de Fourier continue

40


d

clair

sombre

T 2d

fmax 1

2d

Soit fmax fréquence maximale:

F(nu,0) = f(x,y) • (n=5 ici)

Si f ne contient pas cette harmonique, les deux signaux sont décorrélés

et F(nu,0) ≈ 0

F(nu,mv) = f(x,y) •

Fourier : interprétation en image

(n=5 et m=10 ici)

41


1

0

1

0

)(2

),(1

),(M N

N

vy

M

uxi

eyxfNM

vuF

1

0

1

0

)(2

),(),(M N

N

vy

M

uxi

evuFyxf

Complexité = M2.N2

Si M=2K1 et N=2K2 FFT (Fast Fourier Transform)

M.N.log(M.N)

u

v

x

y

Transformée de Fourier discrète

42


M

vyi

N M

Muxi eeyxf

MNvuF 2

1

0

1

0

2),(11),(

F(u,y)

Successivement deux algorithmes de FFT monodimensionnels, l'un sur les

lignes, et l'autre sur les colonnes.

f(x,y)

1D

horiz.

1D

vert.

F(u,y)

F(u,v)

Fourier discrète : implémentation

43


N N2 Nlog2N Gain

64 4096 384 10.67

128 16384 896 18.29

256 65536 2048 32

512 262144 4608 56.89

1024 1e6 10240 102.40

Gain de la FFT

44


dvduvyuxgvufyxgyxf ),(),(),(),(

Filtrage d’une image f par un filtre g:

f(x,y) g(x,y) F(u,v) . G(u,v)

f(x,y).g(x,y) F(u,v) G(u,v)

Fourier et filtrage

f(x,y)

g(x,y)

f(x,y) * g(x,y) *

f(x,y)

g(x,y)

f(x,y) * g(x,y)

fF

fF

• fF-1

45


fd(x,y) = fc(x,y) S(x,y)

Transformée de Fourier: Fd(u,v) = Fc(u,v) * S(u,v)

u

v

Fc(u,v)

Spectre de la bande principale

Convolution duplication du spectre continu

Echantillonnage: Fourier

yvet

xuavec

vjvuiudvuSi j

22

),(),(

46


Fréquence de coupure:

u

v

umax u

Fc(u,v ) = 0 si u umax et v vmax

22maxmax

vvet

uu

yvet

xu

maxmax

Repliement du spectre

u

v

Fc(u,v)

Spectre de la bande principale

47


Soit l la demi-période de transition la plus « rapide »

observée dans l’image:

c

cT

f2

lf

xc

l= Tc /2

Période de la demi-sinusoïde

• Δ x ≤ l : les spectres s’écartent, pas de recouvrement

• Δ x > l : recouvrement de spectre, information perdue

Fréquence de coupure

48


Image discrète → image continue ?

Filtrer la partie fondamentale du spectre.

Passe-bas idéal:

u

v

1

0

Reconstruction spatiale

sinon0),(

vetusi1),(

vuH

yxvuH

49


F(u,v ) = Fd (u,v ).H(u, v)

),(),(),( yxhyxfyxf d

)(sinc)(sinc),(),( 1

y

y

x

xvuHFyxh

sinc(x)=sin(x) / x

Reconstruction spatiale (2)

50


fd(x)

x

Fonction image discrète

h(x)

x

Fonction d'interpolation idéale (sinc(x))

0

fd(x) * h(x)

x

Fonction image reconstruite

Reconstruction spatiale (3)

51


Problème: sinc a un support infini.

Interpolation avec des fonctions plus simples:

Ordre 0:

constant par palier (défaut)

h0(x)

x

1

2

x

2

x

H0(u)

u

Perte de résolution Repliement en

fréquence

-2/x 2/x

x

Interpolateur réel

52


Parasites: moiré, hautes fréquences

Hautes fréquences mal

représentées (moiré)

Basses fréquences mal

représentées

Reconstruction d’ordre 0

53


h1(x) = h0(x) h0(x)

x

1

x / 2 - x / 2

H1(u) = H0(u) . H0(u)

u

Perte de résolution Repliement en fréquence

x

π2 x

π2

x

Reconstruction d’ordre 1

Interpolation linéaire

entre les points

Fonction

d’interpolation =

triangle

Espace de Fourier =

Sinc 2

54


a b

c d

AB

C

D

x

y

A B

C

D

x

y

x0

y0

U

V

(x0,y0)

fc(x0,y0)

Filtres interpolateurs

Interpolation

bidimensionnelle:

Interpolation bilinéaire:

55


a b

c d

e f

Filtre bilinéaire : exemple

56


( =

3x

8, x = y)

( =

4x

8, x = y)

( =

5x

8, x =y)

FONCTION % d’erreur de résolution % d’erreur de

repliement

Sinc (idéal) 0 0

Carré (ordre 0) 26.9 15.7

Triangle (ordre 1) 44.0 3.7

gaussienne 38.6 10.3

54.6 2.0

66.7 0.3

Reconstruction: récapitulatif

57


Valeur continue fc(xi,yi) → discrète fd(xi,yi)

d0 d1 d2 d3 d4

EntréecontinueFc(xi,yi)

QuantificationFd(xi,yi)

4 niveaux

r0

r1

r2

r3

00

01

10

11Codes

di = niveaux de décisionri = niveaux de reconstruction spatiale

Quantification

58


a b

c d

e f

g

Quantification: exemple

8 bits 7 bits

6 bits 5 bits

2 bits

3 bits 4 bits

59


Erreur de discrétisation:

1

0

221

)()(M

i

d

d

i

i

i

dffPRfe

P(f) = probabilité qu’un pixel ait une intensité f.

0

0

2

2

i

i

R

e

d

e

Ri et di sont liés !

1

1

1

)(

)()(

)(2

i

i

i

i

ii

d

d

d

d

i

RR

i

dffP

dfffPRii

di

Quantification optimale

60


f

P(f) Surfaces égales

d0 d1 d2 d3 d4 d5 d6 d7

Cas général : solution obtenue de manière récursive.

Cas particulier (histogramme plat):

Quantification optimale (M grand)

Solution empirique:

P(f)

f d0=0 dn =2B-1

1/n di= i/n * dn

Ri = di

61


f Transformation T

Transformation inverse T-1

T(f) T = égalisation d’histogramme

^

f

)(^

fT

Quantification linéaire

T : inversible et produire

un histogramme plat pour

appliquer la quantification

linéaire

T existe = égalisation

d’histogramme

Appliquée aussi bien aux

niveaux de décision que

de reconstruction.

Quantification par transformation

T-1: sur l’image transformée

1

1 0 i

j T(i)

T-1

(j)

62


• Suppression des bits non-

significatifs:

On décompose l’image suivant

les bits de poids décroissant et

on met les bits non significatifs

(LSB) à 0.

Ex: 3 bits / 8 = économie de 37.5% de

stockage.

Exemple d’utilisation

a b

c d

e f

g h

63


F(i,j) → G(i,j)

n niveaux de gris → 2 niveaux

Plusieurs techniques possibles:

• seuillage fixe

• seuillage aléatoire

• seuillage ordonné

• seuillage par diffusion d’erreur

Particulièrement utile pour la reproduction des couleurs sur un

support de qualité limitée: imprimante, affiche…

Cas particulier: binarisation

64


Si F(i,j) < M alors G(i,j) = 0

Si F(i,j) > M alors G(i,j) = 1

• Avantage: ultra-rapide

• Inconvénient: flexibilité réduite, seuil choisi sur toute l’image

Seuillage fixe

65


• But: tempérer les effets « violents » du seuillage simple en laissant aux pixels sombres « une chance » d’apparaître dans le résultat.

• Implémentation:

Choix d’une loi de probabilité

Tirage de la loi sur chaque pixel = image aléatoire

Comparaison pixel à pixel

Ex: Loi gaussienne autour du seuil moyen (127 pour une image 8 bits)

On peut régler le seuil avec l’image (histogramme)

Seuillage aléatoire

66


(µ = 127, = 4)

Seuillage aléatoire

Seuillage aléatoire par gaussienne

67


Technique visant à représenter des niveaux de gris en

distribuant des intensités binaires sur un voisinage: compromis

résolution/niveaux de gris

Ex: Ordered Clustered Dot dithering

• On définit dans un voisinage N x N une matrice, qui se répète sur toute l’image.

Seuillage ordonné

68


• Dans cette matrice, on définit en

chaque point une valeur de seuillage.

• En seuillant chaque pixel de l’image

originale suivant les valeurs de la

matrice, on réduit le nombre de niveau

de gris apparent à NxN.

Seuillage ordonné

69


SEUILLAGE PAR DIFFUSION D’ERREUR:

Diffusion d’erreur: on seuille un pixel, on regarde l’erreur, que l’on distribue sur les pixels adjacents:

Floyd-Steinberg:

... et on itère.

X 7/16

3/16 5/16 1/16

Seuillage par diffusion

70


Algorithme + lent, mais

supérieur en qualité

• D’autres filtres sont disponibles

• Extension en couleur possible.

for (x=0;x < width; x++) {

for (y=0;y < height;y++) {

test = (I(x,y) < seuil ? 0 :1);

e=I(x,y) - 255*test;

I(x,y) = (test > 0 ? 255 : 0);

I(x,y+1) += α*e;

I(x+1,y-1) += β*e;

I(x+1,y) += γ*e;

I(x+1,y+1) += δ*e;

}

}

Seuillage par diffusion

71


Il faut calculer:

• Ri = le centre d'inertie du

domaine Di

• Densité de probabilité de Di =

probabilité d'avoir la couleur (RVB)

du domaine

Problème complexe → solutions sous-optimales

Quantification des couleurs

Généralisation : définir dans l'espace RVB, des

domaines de décision Di (volumes) et des

niveaux de reconstruction Ri (vecteurs couleur)

approximant toutes les couleurs tombant dans

le domaine des décisions Di.

Ex: median cut

http://www.micro.magnet.fsu.edu/primer/ja

va/digitalimaging/processing/colorreduction

/index.html

72


Quantification des couleurs

Original 64 couleurs 16 couleurs

73


THE END !

Documents

Traitement des Images Click to edit Master title style · Réalité Augmentée Vision Robotique -opération Véhicules autonomes Vision Industrielle Inspection Montage Fabrication