Traitement d’images – examen de rattrapage (mercredi, 18 juin 2008)

Question 1. Numérisation de l’image

Pour numériser une image analogique, deux étapes sont nécessaires : l’échantillonnage et la quantification. Expliquez la différence entre ces deux étapes et l’influence de chacune sur la résolution

L’échantillonnage est la discrétisation spatiale (en x et y) du signal obtenu par le capteur image. Le résultat est un découpage discret du signal en une matrice de pixels de taille Largeur x Hauteur.

La quantification est la discrétisation du niveau de gris (ou de la couleur) de chaque pixel selon une échelle définie sur n bits. Le résultat est un découpage des valeurs de niveaux de gris (ou de couleurs) selon une échelle discrète de n bits (8, 16, 24 ou 32 le plus souvent)

L’échantillonnage influence la résolution spatiale de l’image finale, c’est-à-dire le nombre de pixels (en x et y) que contiendra cette image et le plus petit détail qui sera discernable sur cette image.

La quantification influence la résolution des tons de gris (ou de couleurs), c’est-à-dire le plus petit changement de gris (ou de couleur) qui sera discernable pour un pixel de l’image finale.

Question 2. Transformée de Fourier et filtrage

Soit l’image A ci-dessous qui est bruitée. Vous voulez “nettoyer” cette image, c’est-à-dire enlever le bruit et obtenir l’image B.

a) Quel type de bruit affect l’image A ?

Il s’agit d’un bruit de type sinusoïdal

b) Parmi les choix suivants, quel est celui ressemble le plus à la transformée de Fourier de l’image A ?

La figure 3.

c) Comment allez-vous procéder pour nettoyer ce bruit ?

Pour nettoyer ce bruit, il faut obligatoirement passer dans l’espace fréquentiel (transformée de Fourier). Sur l’image de la transformée, on identifie le sinus causant le bruit par deux points symétriques se trouvant en dehors du centre. Il suffit alors de mettre ces deux point à zéro dans la transformée et de faire la transformée inverse pour obtenir l’image B.

Question 3. Convolution

Soit l’image (10×10) et le filtre de convolution (3×3) suivants :

a) Calculer ci-dessous l’image convoluée par ce filtre (Notes : image 8 bits non-signés)

Note: En appliquant ce filtre, il faut prendre la valeur absolue du résultat et puis diviser ce résultat par 15 (somme des coefficients positifs – ou négatifs – du filtre)

b) A quoi sert ce filtre de convolution

Il s’agit d’un filtre pour détecter les contours verticaux

Note : Pour information supplémentaire (ne comptant pas pour l’examen), il s’agit d’un masque de Kirsch.

Question 4. Vrai ou Faux

Répondez par V(vrai) ou F(faux) aux affirmations suivantes:

a) La transformée de Hough standard sert à détecter des lignes dans une image. V

b) Deux pixels qui ont le même niveau de gris dans une image ont aussi le même niveau de gris dans l’image après l’égalisation de l’histogramme V

c) Une érosion suivie par une dilatation donne comme résultat l’image de départ. F

d) Augmenter la taille d’une masque de convolution linéaire augmente la complexité de calcul. V

e) L’algorithme des k-moyennes permet toujours de trouver les régions connexes homogènes d’une image. F

f) Il est possible de calculer la luminance d’une image avec seulement l’histogramme de cette image. V

g) L’algorithme de division0-fusion permet de segmenter une image de façon automatique sans seuil ni critère. F

h) Pour éviter de rendre l’image floue lorsqu’on veut enlever le bruit, il vaut mieux utiliser le filtre gaussien plutôt que le filtre médian F

Question 5. Opération sur les images

Soit les deux images suivantes :

où les couleurs représentent le fond de l’image et un objet : blanc pour Fond(0) et noir pour Objet(1)

a) Quelle est la chaine d’opérations permettant de passer de l”image A à l’image B en se servant uniquement des opérations globales suivantes sur les images

  • Opérations binaires : et(˄), ou(˅), non(!)
  • Opérations mathématiques : addition(+), soustraction(-)
  • Opérations ensemblistes : union(ᴗ), intersection (ᴖ)
  • Opérations morphologiques : érosion(ϴ), dilatation(Θ)

Note : Chaque opération ne prend que des images ou des masques (éléments structurants) en arguments, pas de nombres

Soit C un élément structurant (3×3, connexité 4 ou 8), alors

B = A – (A ϴ C)

Note : D’autres solutions sont possibles, mais ne valent pas forcément tous les points

b) Que représente l’image B par rapport à A.

Il s’agit du contour (intérieur) de l’objet. En le calculant avec l’opérateur d’érosion, on l’appelle le gradient morphologie interne.

Advertisements

Traitement d’images – Cours 2010 (IFI – P15)

Programme du cours

  • Introduction
  • Qu’est-ce qu’une image ?
  • Acquisition d’une image
  • Traitements de base d’une image
  • Convolution numérique
  • Traitements fréquentiels
  • Détection des contours
  • Segmentation
  • Opérations sur les images binaires
  • Chaine complète de traitements d’images

Introduction d’images (cours 1)

Acquisition des images : Monde -> Caméra -> Numériseur -> Image numérique

Image numérique :

  • Les valeurs de f(x,y) sont la réponse du capteur au phénomène observé
  • Les valeurs de f(x,y) sont des valeurs de “voltage” continu
  • Les valeurs de f(x,y) doivent être converties vers le domaine numérique : conversion Analogique/Numérique (A/N)
  • Deux procédés sont impliqués pour numériser une image : Numérisation = Échantillonnage + Quantification
    • L’échantillonnage est limité par la capacité du capteur, donc le nombre de pixels disponibles (ou autre limite imposée)
    • La quantification est limité par la quantité de tons (de gris) définie dans l’intervalle

Résolutions des images

  • Résolution spatiale : le plus petit détail discernable => Échantillonnage
  • Résolution tonale (de tons de gris) : le plus petit changement discernable => Quantification
  • Une image a donc une résolution spatiale de MxN pixel et une résolution de tons de gris de K bits ou de L  niveaux ou tons

Formats sans compression

  • Les formats les plus simple sont les images sans compression : les pixels sont codés directement, les uns à la suite des autres
  • PGM : images en niveaux de gris 8 bits
  • PPM : images en couleurs Rouge-Vert-Bleu 24 bits

Formats avec compression

  • Les pixels sont compressés pour que le fichier soit plus petit sur le disque
    • Compression sans perte : fichier compressé sans modification de la valeur des pixels (comme PNG)
    • Compression avec perte : valeurs des pixels modifiées pour prendre encore moins de place après la compression (comme JPEG)
    • JPEG est très bien pour visualiser les images (vision humaine) mais très mauvais pour le traitement d’images, car on perd beaucoup d’informations
      • Images d’entrée peuvent être en JPEG
      • Eviter autant que possible de sauvegarder des résultats en JPEG

TIFF : format multi-usage avec/sans compression

BMP : format couleurs 24 bits sans compression

GIF : format couleurs 8 bits avec compression

Profil d’intensité d’une image

Traitements de base (cours 2 – 03/08/2010)

Histogramme d’une image

Dynamique d’une valeur = [valeur_min, valeur_max]

La luminance (ou brillance) est définie comme la moyenne de tous les pixels de l’image.

Le contraste peut être défini de plusieurs façons

  • Écart-type des variations des niveaux de gris
  • Variation entre niveaux de gris min et max : C = (max[f(x,y)] – min[f(x,y)]) / (max[f(x,y)] + min[f(x,y)])

Amélioration du contraste

  • Transformation linéaire : I(i,j) appartient [min, max] => I'(i,j) appartient [0, 255]
  • Transformation linéaire avec saturation : utiliser Smin, Smax en remplaçant min, max
  • Transformation linéaire par morceau : utiliser plusieurs points avec des min, max local
  • Transformation non-linéaire
  • Égalisation de l’histogramme : pour améliorer le contraste, on cherche à aplanir l’histogramme (L’égalisation d’histogramme peut améliorer une image là où la correction de dynamique de l’histogramme est inefficace)
    • Étape 1 : Calcul de l’histogramme => h[i] avec i appartient [0, 255]
    • Étape 2 : Normalisation de l’histogramme => hn[i] = h[i] / Nbp (Nbp : Nombre de pixels de l’image)
    • Étape 3 : Densité de probabilité normalisé => C[i] = Xichma(0,j) hn[j]
    • Étape 4 : Transformation des niveaux de gris de l’image => f'(x,y) = C(f(x,y)) x 255

Dans le cas où l’histogramme initial occupe toute la plage de dynamique, aucun changement n’est visible

Si on prend la même image avec des contrastes différents, l’égalisation d’histogramme donne le même résultat pour toutes les images

L’égalisation locale de l’histogramme est faite en prenant une fenêtre de 7×7 autour de chaque pixel

L’addition d’images peut permettre

  • De diminuer le bruit d’une vue dans une série d’images
  • D’augmenter la luminance en additionnant une image avec elle-même

La soustraction d’images peut permettre

  • Détection de défauts
  • Détection de mouvements

La multiplication d’images peut permettre d’améliorer le contraste ou la luminosité

Interpolation d’images : changement d’échelle

  • Interpolation du plus proche voisin : par copie des pixels
  • Interpolation bilinéaire : Zoom
  • Interpolation bicubique

Convolution (cours 3 – 05/08/2010)

Modification des valeurs d’une image

  • Pour l’instant, nous avons vu surtout des transformations ponctuelles des pixels d’une image : lire la valeur d’un pixel et puis la remplacer par une autre.
  • Il existe aussi des transformations locales : lire la valeur de quelques pixels voisins et puis calculer une nouvelle valeur pour un pixel
  • Il existe aussi des transformations globales : lire la valeur de tous les pixels de l’image et puis calculer une nouvelle valeur pour un seul pixel

La convolution discrète est un outil permettant l’utilisation de filtres linéaires ou de filtres de déplacements invariants

g(x) = f(x) * h(x)

  • f(x) : la fonction d’origine
  • h(x) : masque de convolution, noyau de convolution, filtre, fenêtre, kernel …
  • g(x) : la fonction convoluée

Convolution numérique : problème -> que faire avec les bords de l’image ?

  • Mettre à zéro
  • Convolution partielle : sur une portion du noyau
  • Miroir de l’image : f(-x,y) = f(x,y)

Masque de convolution. On divisera le résultat de la convolution par la somme des coefficients du masque

  • Pour éviter de modifier la luminance global de l’image, la somme des coefficients doit être égale à 1
  • Filtres passe-bas : atténue le bruit et les détails (basses fréquences) ->lissage
  • Filtres passe-haut : accentue des détails et les contours (hautes fréquences) -> accentuation

Le filtre moyenne

  • Permet de lisser l’image (smoothing)
  • Remplacer chaque pixel par la valeur moyenne de ces voisins
  • Réduit le bruit
  • Réduit les détails non-important
  • Brouille ou rend floue l’image (blur edges)

Filtre dont tous les coefficients sont égaux

Plus le filtre grossit, plus le lissage devient important et plus le flou s’accentue

Le filtre Gaussien

Le filtre gaussien donnera un meilleure lissage et une meilleure réduction du bruit que le filtre moyenne

Filtres non-linéaires

  • Filtre médian : pour nettoyer le bruit dans une image, le filtre médian est meilleur que le filtre moyenne ou le filtre gaussien
    • On remplace la valeur d’un pixel par la valeur médiane dans son voisinage NxN

Traitements fréquentiels (cours 4 – 05/08/2010)

Notions de fréquences dans un signal

  • Signal haute fréquence
  • Signal basse fréquence

Les fréquences dans l’image

  • Fréquence = changement d’intensité
  • Basses fréquence = régions homogènes, flou
  • Hautes fréquence = contours, changement brusque d’intensité, bruit
  • La plus grande partie de l’énergie d’une image se situe dans les basses fréquences

Analyse spectrale d’une image

  • Une image est avant tout un signal (visuel)
  • On peut analyser les fréquences de ce signal. On parle de fréquences spatiales (image) au lieu de fréquences temporelles (audio)
  • Pour cela, on crée un nouvel histogramme (graphique) qui va représenter les fréquences de l’image. L’outil de base pour cela est la Transformé de Fourier
  • On parle de domaine fréquentiel, par opposition au domaine spatial (de l’image)

Interprétation de la Transformée 2D

  • Hautes fréquences : loin du centre de la TF
  • Basses fréquences : proche du centre de la TF
  • Composante continue : centre de l’image. fréquence zéro = moyenne de l’image

Transformée en nombres complexes :

  • La Transformée de Fourier d’une fonction réelle donne une fonction complexe
    • Entrée : une image
    • Sortie : image (partie réelle) + image (partie imaginaire)
  • Nombre complexe : z = x + i*y avec i=root(-1)
  • On utilise beaucoup la norme de la Transformée : Norme = |F(u,v)| = root(Réel^2 + Img^2)

Codage de la transformée de Fourier

  • L’algorithme FFT = Fast Fourier Transform

Dans le domaine spatial, le filtrage se fait par convolution : Image initiale ->(filtrage spatial – convolution) ->Image filtrée

Dans le domaine spectral (ou fréquentiel), il se fait par multiplication (ou masquage de l’image)

  1. Image initiale ->(TF)-> Image transformée
  2. Image transformée ->(Filtrage spectral – multiplication)-> Image transformée filtrée
  3. Image transformée filtrée ->(TF^-1) -> Image filtrée

Dans le cas des filtres dans le domaine fréquentiel non-multiplicatif, on ne peut pas obtenir le même résultat par convolution dans le domaine spatial

Détection de contours (cours 5 – 11/08/2010)

Un contours est une variation brusque d’intensité

Par définition, un contour est la frontière qui sépare deux objets dans une image => une discontinué de l’image.

Dans notre cas, nous détecterons toutes les lignes marquant des changements d’intensité

  • Pas seulement les contours
  • Abus de langage sur la notion de contours
  • Des discontinués comme : d’orientation de surface, de profondeur, de réflectance, d’illumination

Différents types de contours

  • Marche d’escalier
  • Rampe
  • Toit

Dérivée d’une image

La première dérivée de l’image est l’opérateur de base pour mesurer les contours dans l’image. |-delta- f| = (δf/δx)^2 + (δf/δy)^2

Pixels contours : |f(x)’| > Seuil

Dérivée discrète : Approximation simple de la dérivée discrète

-1 1         -1/1

ou encore : -1 0 1                         -1/0/1

Filtre de Roberts : Le calcul se fait avec 2 masques de convolution pour les 2 directions de la dérivée

0  1  : Gx       1  0 : Gy

-1 0                0 -1

Plusieurs autres filtres existent pour la détection des contours dans l’image.

On fait lissage de l’image + dérivée de l’image (sauf Roberts)

Filtre de Prewitt : Moyenneur + Dérivé

Filtre de Sobel : Gaussienne + Dérivé

=> Détection des contours moins sensible au bruit.

Gradient de l’image : En 2 dimensions, nous parlons de gradient de l’image : dérivée en X + dérivée en Y => vecteur avec une norme et une direction.

  • Norme : intensité du gradient en chaque pixel (mesure la plus utilisé). |G| = root(Gx^2 + Gy^2) == |Gx| + |Gy|
  • Direction : direction du gradient le plus fort en chaque pixel. θ = arctan (Gy/Gx)

Deuxième dérivée de l’image : Laplacien

Une autre approche pour trouver les contours de l’image est d’utiliser la seconde dérivée de l’image

Pour cela, on utilise le Laplacien comme opérateur : -delta-^2I = δI/δx^2 + δI/δy^2

Les contours correspondent :

  • Aux maxima de la première dérivée
  • Aux passages par zéros de la deuxième dérivée

Laplacien par convolution

  • Plusieurs approximations discrètes du Laplacien existent
  • Une seule matrice de convolution
  • Symétrique en rotation.

En pratique, on obtient des contours incomplets :

  • il y a des pixels superflus
  • il y a des manques
  • il y a des erreurs de position et d’orientation des pixels contours

Approche globale pour les contours : Transformée de Hough

  • On ne cherche pas seulement des pixels contours
  • On cherche le contour au complet
  • On cherche plusieurs pixels correspondant à un contour.

Transformée de Hough

  • Pour détecter des contours continus du plan x-y au plan paramétrique a-b
  • Plan x-y
    • yi = a*xi + b
    • Une infinité de lignes passent par (xi, yi)
    • Une seule ligne par la paire (a, b)
  • Plan paramétrique a-b
    • b = -xi*a + yi
    • Une seule ligne pour la paire (xi, yi)
    • Une infinité de lignes passent par (a, b)

Droites et Points : Tous les points (x,y) sur une ligne du plan x-y passent par un seul point (a’, b’) dans le plan paramétrique a-b

Principe de la transformée de Hough

  • Cellules d’accumulation – matrice (a,b)
  • On construit une image des votes : chaque point permet de voter pour une droite particulière
  • Les droites recevant le plus de votes sont conservées

Calcul de la transformée de Hough

  • On calcule le gradient de l’image origine : Sobel, Prewitt, Canny ….
  • Pour chaque point du gradient, on calcule une droite (a, b) : on obtient une droite dans le plan a-b pour chaque pixel (x,y)
  • Les pics maximum dans le plan paramétrique a-b indiquent les droites avec le maximum de points du plan x-y : les points de croisement des droites dans le plan a-b indiquent les vraies droites existantes dans le plan x-y

Problème avec un espace (a,b) : pour une droite verticale b=infini => représentation sous forme polaire (ρ,ϴ) : ρ = x*cosϴ  +  y*sinϴ

Segmentation (Cours 6 – 13/08/2010)

La segmentation vise à diviser l’image en morceaux. Ces morceaux correspondent aux objets dans l’image.

La segmentation est liée à la reconnaissance.

But de la segmentation:

  • Extraire (séparer) les entités d’une image.
  • Dans la pratique : construire une image de masques
  • Chaque masque est une composante connexe

La segmentation est normalement basée sur :

  • les discontinuités : contours – les changements abruptes, frontières entre régions, ….
  • les zones homogènes : régions – mêmes couleurs, textures, intensités, …

La segmentation est le découpage d’une image en différentes régions et/ou contours.

Un contours fermé est équivalent à une région.

Segmentation régions/contours

  • Approches régions : rechercher les zones dans l’image sur un critère d’homogénéité
  • Approches contours : rechercher les discontinuités entre régions
  • Approches duales : régions et contours.

Seuillage

  • Le seuillage est une méthode simple et très populaire pour le traitement des images numériques.
  • Ce n’est pas une méthode de segmentation en régions (approche pixel, pas région ni contour)
  • Le seuillage peut-être
    • Global : un seuil pour toute l’image
    • Local : un seuil pour une portion de l’image.
    • Adaptatif : un seuil s’ajustant selon les parties de l’image.

Comment définir le seuil ? Comment trouver le bon seuil (T) ?

  • Une valeur obtenue par tests
  • La valeur moyenne des tons de gris
  • La valeur médiane entre le ton maximum et le ton minimum
  • Une valeur qui balance deux sections de l’histogramme

Choix des seuils (optimaux)

  • Deux surfaces (arrière-plan et objet) dans une image
  • On suppose des modèles mathématiques pour les distributions (gaussiennes, …)
  • On peut déterminer la probabilité d’erreur de classification dans les classe 1 et 2 (surfaces E1 et E2 ci-dessous)
  • On cherche alors un seuil T qui causera une erreur minimale.

Il existe plusieurs méthodes globales automatiques qui permettent de trouver un seuil à partir d’un histogramme : Otsu, Kittler ….

Exemple : Algorithme de Otsu

  • On balaie toutes les valeurs de seuil possible T
  • Pour chaque seuil T
    • On calcule les moyennes et les variances de chaque classe
    • On s’intéresse à la variance intra-classes
  • Basé sur le fait que les classes sont bien définies et regroupées

Seuillage global – problème d’éclairage

  • Problème : le seuillage global ne peut pas traiter ce cas
  • Solution : seuillage local adaptatif

Exemple de seuillage adaptatif

  • Nous avons besoin de séparer l’image en sous images, et de traiter chacune avec son propre seuil
  • Le choix de la dimension des sous-images est important.
  • Avant de traiter chaque sous-image, nous vérifions la variance des tons de gris pour décider s’il existe un besoin de segmentation. Exemple : pas besoin si variance < 100

Algorithme des K-moyennes (K-means)

  • On veut diviser les points en k groupes (clusters)
    • k est donné à l’avance (un paramètre de l’algorithme)
    • on définit le centre d’un groupe comme la moyenne  des éléments (pixels) du groupe
  • L’algorithme est composé de 4 étapes :
    1. Partitionnement des données en k sous-ensembles (non vides)
    2. Calcul des centres des groupes de la partition courante
    3. Les données sont affectées au groupe dont le centre leur est le plus proche
    4. Retour à l’étape 2
    5. Arrêt lorsque les groupes sont constants
  • K-moyennes basé sur l’intensité (gris) ou sur la couleur

Segmentation en pixels/régions

  • Le seuillage est une opération sur les pixels : ne produit pas forcément des régions connexes.
  • On peut utiliser le seuillage pour les régions, mais il faut nettoyer le résultat obtenu : éliminer les pixels seuls, conserver les régions
  • Il existe des méthodes de segmentation en régions : conservent la connexité entre les régions

Segmentation en régions : Division-fusion (Split-and-Merge)

  • Étape de division (split)
    • Diviser récursivement tout bloc non-homogène selon un prédicat défini : variance, max-min …
    • La division d’un bloc donne 4 sous-blocs
    • Les attributs de chaque sous-bloc sont recalculés
  • Étape de fusion (merge)
    • Regrouper les blocs adjacents représentant des régions homogènes selon un prédicat défini

Segmentation en régions : Croissance de régions (Region growing)

  • On débute avec un pixel, et on ajoute les pixels voisins qui répondent à un critère d’appartenance
    • Variance faible
    • Niveau de gris répondant un seuil
    • ……
  • Les pixels initiaux sont appelés “germes (seeds)“, “amorces” ou “semences“. Choix des pixels initiaux automatiques ou semi-automatiques
  • La région “grandit” à partir de son germe. Besoin d’une critère (ou prédicat) pour choisir les pixels à ajouter.

Segmentation en régions : Ligne de partage des eaux (Watershed)

  • On considère la visualisation de l’image en 3D, en utilisant le ton de gris comme troisième dimension.
  • Ensuite on complément les valeurs pour créer des zones inondables
  • Enfin, on infiltre les cavités des zones inondables

Approche Gestalt

  • Une autre approche de la segmentation/groupement s’inspire de la psychologie et de l’observation de l’humain et de son environnement
  • Cette approche est basée sur les travaux de Gestalt sur la vision humaine.
  • Importance du contexte dans cette approche.
    • Proximité : objets proches sont regroupés
    • Similarité : objets semblables sont regroupés
    • Tendance commune : objets avec un mouvement cohérent semblable sont regroupés
    • Région commune : objets à l’intérieur d’une même région sont regroupés
    • Parallélisme : courbes ou objets parallèles sont regroupés
    • Fermeture : courbes ou objets qui peuvent former des objets fermés sont regroupés
    • Symétrie
    • Continuité
    • Configuration familière

Images binaires (Cours 7 – 14/08/2010)

Plusieurs techniques particulières permettent de manipuler les images binaires (0:1)

Utile, par exemple, pour traiter les résultats de segmentation.

Connexité des pixels

  • Connexité-4
  • Connexité-8

Distance discrète entre pixels

  • Distance de Manhattan
  • Distance de l’échiquier

Codage de Freeman

  • Pour coder les directions dans une image, on utilise le codage de Freeman
  • On peut ainsi coder les contours en partant d’un pixel (en haut à gauche) et en tournant dans le sens des aiguilles d’une montre

Étiquetages de composantes connexes

  • Composante connexe = ensemble de pixels connexes (voisins) appartenant à une même entité
  • Une image segmentée n’est qu’une succession de pixels
  • On désire donner une valeur commune pour les pixels d’une région ou d’un contour
  • On désire avoir une valeur différente pour chaque région/contour
  • Utiliser en post-segmentation

Étiquetages de composantes connexes (2)

  • Nous allons effectuer un parcours de l’image pour affecter un numéro unique (étiquette) pour chaque région
  • Tous les pixels d’une même région doivent avoir le même numéro (étiquette)
  • Premier parcours de l’image
    • Pour chaque pixel d’une région, on lui affecte
      • Soit la plus petite étiquette parmi ses voisins haut et gauche
      • Soit une nouvelle étiquette
  • Deuxième parcours de l’image.
    • Pour chaque pixel d’une région, on lui affecte
      • La plus petite étiquette parmi la sienne et celles ses voisins bas de droite
  • Parfois, il faut plus de deux parcours, exemple : région en spirale.
    • On continue les parcours, dans un sens puis l’autre, jusqu’à ce qu’il n’y ait plus de changement d’étiquettes

Étiquetages de contours

  • Pour étiqueter des contours, on peut utiliser le même algorithme
  • On procède de la même façon, sauf qu’on utilise la 8-connexité. On regarde 4 voisins au lieu de 2.
  • A faire attention : normalement l’épaisseur d’un contour doit être d’un seul pixel.

Fermeture des contours

  • Du gradient aux contours
    • Les méthodes de gradient vus en classe ne donnent pas forcément des contours fermés
    • Il y a des trous et plusieurs morceaux isolés
  • On doit alors “fermer les contours” pour avoir une segmentation avec les contours équivalentes  aux régions
  • Si le contour est trop épais, où si le contour présente plusieurs chemins, on doit conserver les pixels de gradient le plus fort.
  • Calcul et suivi du meilleur chemin dans le gradient. Au bout des contours, on cherche le chemin permettant de rejoindre une autre extrémité de contour.
  • Seuillage par hystérésis
    • Définir deux seuils
      • Seuil bas : minimum pour être contour.
      • Seuil haut : minimum pour être contour d’un objet.
    • (1) Seuiller avec le seuil haut
    • (2) Ajouter les contours connectés supérieur au seuil bas.

Opérateurs morphologiques

  • Très utilisés sur les images binaires (images de masques). Mais aussi sur les images en niveaux de gris.
  • Permettent de modifier la morphologie des objets
    • Pour nettoyer le résultat de la segmentation. Remplir les trous, éliminer le bruit.
    • Pour lisser le résultat de la segmentation.
  • Utilisé en post-segmentation
  • Caractérisés par
    • Un élément structurant
    • Des transformations
      • érosion, dilatation
      • ouverture (érosion & dilatation), fermeture (dilatation & érosion)
  • Soit une image binaire avec fond = 0 et objet = 1
  • L’élément structurant glisse sur les bords (intérieurs, extérieurs) des objets et transforme sur son passage
    • Des pixels d’objet en pixels de fond (érosion)
    • Des pixels de fond en pixels d’objet (dilatation)
  • Exemple d’éléments structurants : Connexité-4, Connexité-8 etc.

Opérateurs morphologiques (2)

  • Érosion : Si un des pixels du masque est fond (valeur 0) alors le pixel central devient fond
  • Dilatation : Si un des pixels du masque fait partie de l’objet (valeur >0) alors le pixel central devient objet
  • Ouverture : érosion puis dilatation
  • Fermeture : dilatation puis érosion

Gradient interne, externe

  • Image originaire – Image érodée = Contour intérieur
  • Image dilatée – Image originaire = Contour extérieur
  • Image dilatée – Image érodée = Gradient morphologique

Chaine complète de traitement d’images (Cours 8 – 15/08/2010)

Etape d’un système complet

  1. Acquisition des images
  2. Pré-traitement des images
  3. Segmentation des images
  4. Post-traitement des résultats
  5. Analyse/sortie des résultats

1. Acquisition des images

Un grand nombre de difficultés peuvent être résolues au niveau du système de saisie

  • Choix du type de caméra (couleur ?)
  • Positionnement de la caméra (fixe ?)
  • Choix de l’arrière-plan (homogène et contrastant ?)
  • L’éclairage de la scène (arrière ou devant ?)

2. Pré-traitement des images

  • Enlever le bruit des images : filtres moyenne, médian, …
  • Contraste des images : égalisation de l’histogramme, correction de la dynamique de l’image, …
  • Image couleur vers niveaux de gris (si nécessaire …) ou changement d’espace couleur (TSV, Lab, …)
  • Modifier la résolution (taille) de l’image : pas forcément besoin d’une grande image, vitesse d’exécution et précision voulue, reflets de l’image, autres défauts d’acquisition, ….

3. Segmentation des images

  • Etape très difficile
  • Chaque algorithme de segmentation est très différent
    • Entrées différentes
    • Sorties différentes
    • Paramètres différentes
  • Le but est de trouver un algo+paramétrage unique : même traitements pour toutes les images
  • Un algorithme de segmentation seul n’est pas forcément efficace : combinaison de plusieurs techniques.

4. Post-traitement

  • Après la segmentation, besoin de corriger les résultats
    • Morphologie mathématique
    • Éliminer/corriger les erreurs de segmentation
    • Étiquetage des régions (objets)
    • Création de masques pour les objets voulus
    • ……

5. Analyse/sortie des résultats

  • Selon l’application
    • Besoin d’afficher l’image résultat pour un opérateur humain
    • Reconnaissance des formes
    • Indexation et recherche d’images
    • Détection d’obstacles pour un robot
    • …..
  • D’autres algorithmes et traitements peuvent être nécessaires.

————————————————————

atténuer (v): rendre moins forts, moins intenses, moins graves une sensation, un sentiment, etc.

accentuer (v): rendre plus forts, plus intenses une sensation, un état, une action, etc. ; accroître, augmenter

lissage (m) : smooth

coefficient (m): facteur appliqué à une grandeur quelconque ; pourcentage : Coefficient d’erreur.

Traitement d’images – examen final (jeudi, 19 janvier 2006)

Question 1 – Convolution

Voici un extrait d’une image. Cette image est représentée sur 9 bits par pixel (valeur de chaque pixel en -255 et 255)

(a) Calculer les convolutions sur la ligne centrale de l’image (6 valeurs centrales seulement à calculer) avec les quatre filtres suivants “

(b) Quel est l’effet de chacun de ces quatre filtres sur l’image ? À quoi servent-ils ?

Question 2 – Seuillage

Une méthode de segmentation très facile à programmer et à utiliser est le seuillage. Il suffit de donner un paramètre (le seuil T) et l’algorithme est le suivant :

g(x,y) = 1 si f(x,y) > T ou 0 si f(x,y) <= T

Cet algorithme permet d’isoler facilement un objet du fond de l’image.

(a) Comment peut-on trouver un seuil manuellement en utilisant l’histogramme global de l’image ? Dessinez un exemple pour aider vos explications.

(b) Parfois, un seuillage global d’une image donne de mauvais résultats. Plusieurs solutions sont possibles pour améliorer l’algorithme de base. Donnez un exemple comment améliorer l’algorithme de seuillage.

Question 3 – Segmentation en régions

Expliquez les algorithmes de segmentation de

+ Croissance de régions

+ Division-Fusion

Expliquez le fonctionnement général de ces deux algorithmes (pas besoin de l’algorithme complet mais une  bonne explication) et surtout dites quels sont les paramètres importants de ces deux algorithmes

Question 4 – Comptage d’objets séparés et bruités

On vous demande de concevoir un système qui compte le nombre d’objets avec trous et le nombre d’objets sans trou dans une image. Le système d’acquisition d’images produit des images binaires (0-noir et 1-blanc). Ce système d’acquisition est de très mauvais qualité et les images sont corrompues par un bruit de type poivre et sel. Les objets  ne se touchent pas et ne se recouvrent pas. Ils peuvent être de différentes formes et de différentes tailles. Dans l’image exemple ci-contre, le résultat du système est : 2 objets sans trou et 3 objets avec trous.

Décrivez votre système pour réussir ce travail. Vous pouvez expliquer ou écrire un algorithme en pseudo-code, ou faire des schémas. Donnez toutes les hypothèses nécessaires pour que votre système fonctionne. Vous pouvez utiliser certains algorithmes vus en cours directement sans devoir les décrire entièrement, mais spécifiez les entrées/sorties de ces algorithmes que vous utilisez ainsi que la raison pour les utiliser. Si vous souhaitez modifier un algorithme existant, justifiez pourquoi ainsi que les changements que vous souhaitez faire. Donnez toutes les explications nécessaires pour démontrer le fonctionnement de votre système.

Question 5 – Comptage d’objets se touchant

Dans les applications en microscopie, un problème fréquent est de compter le nombre de particules (d’objets) dans une image, comme dans l’image ci-contre. Il s’agit d’une image binaire (0-noir et 1-blanc) comme  dans la question précédente. Par contre, les différences sont que tous les objets de l’image sont ronds et sont de même taille (tous les objets sont identiques), mais ils se touchent dans l’image, sans toutefois se recouvrir. Il n’y a pas de bruit dans l’image cette fois-ci

Décrivez votre système pour réussir ce travail. Vous pouvez expliquer ou écrire un algorithme en pseudo-code, ou faire des schéma. Donnez toutes les hypothèses nécessaires pour que votre système fonctionne. Vous pouvez utiliser certains ….

Traitement d’images – examen final (mercredi, 5 janvier 2005)

Question 1 – Numérisation de l’image

Pour numériser une image analogique, deux étapes sont nécessaires : l’échantillonnage et la quantification. Expliquez la différence entre deux étapes et l’influence de chacune sur la résolution finale de l’image.

L’échantillonnage est la discrétisation spatiale (en x et y) du signal obtenu par le capteur image. Le résultat est un découpage discret du signal en une matrice de pixels de taille Largeur x Hauteur.

La quantification est la discrétisation du niveau de gris (ou de la couleur) de chaque pixel selon une échelle définie sur n bits. Le résultat est un découpage des valeurs de niveaux de gris (ou de couleurs) selon une échelle discrète de n bits (8, 16, 24 ou 32 le plus souvent).

L’échantillonnage influence la résolution spatiale de l’image finale, c’est-à-dire le nombre de pixels (en x et y) que contiendra cette image et le plus petit détail qui sera discernable sur cette image.

La quantification influence la résolution des tons de gris (ou de couleurs), c’est-à-dire le plus petit changement de gris (ou de couleur) qui sera discernable pour un pixel de l’image finale.

Question 2 – Filtrage spatial et fréquentiel

Vous voulez réaliser le filtre moyenne 5×5, sans faire de convolution mais en utilisant la transformée de Fourier (FFT). Expliquez comment cela peut être fait en donnant toutes les étapes nécessaires, mais sans faire les calculs (5-10 lignes). Les paramètres exacts du filtre ne sont pas demandés, mais seulement la forme finale du filtre (dessin)

Une convolution dans le domaine spatial équivaut à une multiplication dans le domaine fréquentiel. Les étapes nécessaires sont :

  • Calcul de la transformée de Fourier, avec la FFT, sur l’image originaire
  • Multiplication de l’image transformée par le filtre (parcours en x et y avec multiplication du pixel(x,y) de l’image transformée par le pixel(x,y) du filtre)
  • Calcul de la transformée de Fourier inverse, out FFT^-1 sur l’image filtré

Le filtre moyenne est un filtre passe-bas. Il équivaut à mettre à zéro toutes les fréquences à l’intérieur d’un cercle de rayon r dans l’espace  fréquentiel. Le calcul de r détermine la fréquence de coupure, mais ceci n’est pas dans le contenu de ce cours. La forme du filtre est la suivante : (- dessiner le figure -)

Question 3 – Acquisition d’images

Pour réduire le bruit dans une image, une méthode consiste à faire l’acquisition  de plusieurs images identiques et de les additionner. Expliquez pourquoi cette méthode permet d’obtenir une image plus nette.

L’hypothèse (vérifiée) est que le bruit ajouté à la valeur d’un pixel lors de l’acquisition de l’image est aléatoire. En prenant plusieurs images successives de la même scène sans bouger la scène ni la caméra, les images sont normalement identiques, sauf qu’un bruit différent a pu être ajouté à la valeur de chaque pixel de chaque image. En additionnant chaque image, on fait l’équivalent d’un filtre moyenne. Pour chaque pixel, on fait une moyenne des différentes valeurs obtenues afin de diminuer l’influence du bruit dans l’image

Question 4 – Espaces couleurs

Décrivez la différence entre les espaces couleurs Rouge-Vert-Bleu (RVB) et Teinte-Saturation-Valeur (TSV) et donnez les avantages/désavantages de chaque espace couleur

Chaque espace couleur code les pixels par des triplets de valeur représentant la couleur perçue en un endroit de l’espace.

Cependant, dans l’espace RVB, les trois valeurs sont fortement corrélées, dans le sens ou une légère modification d’un seul paramètre de l’éclairage abiment affectera les trois valeurs R,V,B.

Le but de l’espace TSV (et d’autres espaces couleurs existants) est de séparer la signification de chacune de ces valeurs. On code séparément l’intensité perçue pour un pixel (V) et la couleur de ce même pixel (T,S). On a besoin de deux valeurs pour coder cette couleur, exprimant le teinte et la saturation de la valeur.

L’avantage de l’espace RVB est pour obtenir un affichage rapide d’une image, car ce codage est compatible avec les dispositifs d’affichages des écrans. Par contre, l’avantage de TSV est de pouvoir faire des traitements d’images couleurs plus précis et plus efficace.

Cependant, on utilise souvent RVB pour faire le traitement d’images surtout pour des raisons de facilité (pas de conversion à faire). Mais les résultats de ces traitements seront moins robuste aux variations de luminosité dans la scène

Question 5 – Images binaires

Dans les applications en microscopie, un problème fréquent est de compter le nombre de particules (d’objets) dans une image. Un exemple d’image obtenue par la segmentation est représentée ci-contre, sous la forme d’une image binaire (0 pour le fond ou 1 pour les objets). Nous présumons que tous les objets sont bien séparés et ronds et qu’il y a dans cette image des objets d’au maximum trois tailles différentes. Définissez un algorithme pour compter le nombre de particules de chaque taille. Votre algorithme prend en entrée une image binaire résultant de la segmentation et en sortie il fournit un tableau du nombre de particules de chaque taille (3 tailles différentes). Donnez toutes les explications nécessaires pour démontrer le fonctionnement  de votre algorithme.

Un exemple d’algorithme est le suivant :

  • Étiquetage des régions
  • Comptage de Nb = le nombre d’objets dans l’image.
  • Initialisation d’un tableau des tailles petite, moyenne et grande : TabTaille[3] = {0, 0, 0} et d’une variable TailleCourante = 0
  • Tant que (Nb > 0) ou (TailleCourante > 3), faire :
    • Érosion de l’image
    • Étiquetage des régions
    • Comptage de Nb_Courant = le nombre d’objets courant dans l’image
    • Si (Nb_Courant < Nb), alors
      • TabTaille[TailleCourante] = Nb – Nb_Courant
      • TailleCourante ++
      • Nb = Nb_Courant

L’étiquetage des régions  est obligatoire pour connaitre le nombre de régions dans l’image tandis que l’érosion permet de faire disparaitre en premier les petits objets, puis les moyens et enfin les grands objets. Le deuxième étiquetage des régions pourrait être optionnel selon comment on fait les calculs de l’érosion, mais il est donné ici afin de bien mettre en évidence la nécessité de cet étiquetage pour compter les objets. Cet algorithme est facilement généralisable pour un nombre variable de tailles d’objets

Question 6 – Traitement d’images

La figure à la page suivante représente une image et une série de traitement que l’on peut faire sur cette image. Trouver la bonne correspondance entre les numéros de chaque traitement et les noms pour chaque traitement ci-dessous. L’image originaire et au centre et chaque flèche représente un seul traitement  qui a été fait sur une seule image

Traitement d’images – examen de rattrapage (septembre 2007)

Question 1 – Détection de contours

Soit l’images 1D suivante (à gauche) et le filtre de Robert 1D pour détecter les contours (à droite) :

38 46 61 80 97 108 114 115                                                            1 -1

(a) Calculez le résultat de la convolution en négligeant les effets de bords

8 15 19 17 11 6 1

(b) Combien de contours trouvez-vous dans cette image et où sont-ils ? Expliquez

On repère un seul contour en cherchant les maximums locaux du gradient. Le contour correspond à la valeur 19 du gradient, entre les pixels de valeurs 61 et 80

(c) Soit le filtre suivant qui approxime une gaussienne : 1/A [1 4 6 4 1] Quelle est la valeur de A et pourquoi ?

A = 1+4+6+4+1 = 16, car il faut normaliser le filtre pour éviter de rajouter de l’entropie (augmenter les valeurs) dans l’image

Question 2 – Histogramme de l’image

Soit l’image 8×8 représentée par la matrice ci-contre. Chaque pixel est codé sur 4 bits en niveau de gris.

(a). Calculer et dessiner l’histogramme représentant cette image.

4 bits => 16 valeurs

(b). Vous souhaitez améliorer le contraste dans cette image en modifiant l’histogramme, soit par correction de dynamique ou soit par égalisation d’histogramme. Quelle méthode (ou les deux) pouvez-vous choisir et pourquoi ? Expliquez et comparez les effets des deux méthodes sur cette image. Sans faire les calculs, dessinez la forme approximative de l’histogramme en sortie de chacun de ces deux traitements dans le cas de cette image.

La dynamique de cette image est maximale [0,15], ce qui signifie que la correction de dynamique ne changera rien à l’histogramme de cette image. La seul méthode applicable est donc l’égalisation d’histogramme. Le but (théorique) de cette image est d’obtenir un histogramme réparti également sur toutes les valeurs.

Question 3 – Filtrage spatial et fréquentiel

Vous voulez réaliser le filtre moyenne 5×5, sans faire de convolution mais en utilisant la transformée de Fourrier (FFT). Expliquez comment cela peut être fait en donnant toutes les étapes nécessaires, mais sans faire les calculs. Les paramètres exacts du filtre ne sont pas demandés, mais seulement la forme finale du filtre (dessin)

Une convolution dans le domaine spatial équivaut à une multiplication dans le domaine fréquentiel. Les étapes nécessaires sont :

  • Calcul de la transformée de Fourier, avec la FFT, sur l’image originaire
  • Multiplication de l’image transformée par le filtre (parcours en x et y avec multiplication du pixel(x,y) de l’image transformée par le pixel (x,y) du filtre)
  • Calcul de la transformée de Fourier inverse, ou FFT^-1 sur l’image filtrée

Le filtre moyenne est un filtre passe-bas. Il équivaut à mettre à zéro toutes les fréquences à l’intérieur d’un cercle de rayon r dans l’espace fréquentiel. Le calcul de r détermine la fréquence de coupure, mais ceci n’est pas dans le contenu de ce cours. La forme du filtre est la suivante :

Question 4 – Acquisition d’images

Pour réduire le bruit dans une image, une méthode consiste à faire l’acquisition de plusieurs images identiques et de les additionner. Expliquer pourquoi cette méthode permet d’obtenir une image nette.

L’hypothèse (vérifiée) est que le bruit ajouté à la valeur d’un pixel lors de l’acquisition de l’image est aléatoire. En prenant plusieurs images successives de la même scène sans bouger la scène ni la caméra, les images sont normalement identiques, sauf qu’un bruit différent a pu être ajouté à la valeur de chaque pixel de chaque image. En additionnant chaque image, on fait l’équivalent d’un filtre moyenne. Pour chaque pixel, on fait une moyenne des différentes valeurs obtenues afin  de diminuer l’influence du bruit dans l’image.

Question 5 – Morphologie mathématique sur image binaire

Soit l’image suivante (14×14) et l’élément structurant (3×3) donné :

Calculer le résultat après avoir faire les opérations demandées sur l’image originaire.

a) Érosion

b) Dilatation

c) Ouverture (Érosion + Dilatation)

Question 6 – Traitement d’images

La figure à la page suivante représente une image et une série de traitements que l’on peut faire sur cette image. Trouver la bonne correspondance entre les numéros de chaque traitement et les noms pour chaque traitement ci-dessous

A. Bruit poivre et sel – 9

B. Décalage de l’histogramme vers la gauche (-60 pour chaque valeur) – 8

C. Décalage de l’histogramme vers la droite (+60 pour chaque valeur) – 11

D. Égalisation d’histogramme – 7

E. Filtre moyenne – 5/14

F. Filtre moyenne -14/5

G. Filtre médian – 13

H. Gradient Robert – 1

I. Gradient Sobel – 2

J. Laplacien – 6

K. Seuillage – 3

L. Segmentation par division-fusion – 10

M. Érosion (sur niveaux de gris) – 4

N. Dilatation (sur niveaux de gris) – 12

Traitement d’images – examen final (jeudi, 6 juin 2007)

Question 1. Détection de contours

Soit l’image 1D suivante (à gauche) et le filtre de Roberts 1D pour détecter les contours (à droite)

L’image 1D : 56, 64, 79, 98, 115, 126, 132, 133

Le filtre de Roberts : 1, -1

(a) Calculez le résultat de la convolution en négligeant les effets de bords (7 valeurs seulement)

Le résultat : 8 15 19 17 11 6 1

N.B. On calcule la valeur absolue pour le gradient (-0.25 sinon)

(b) Combien de contours trouvez-vous dans cette image et où sont-ils ? Expliquez

On repère un seul contour en cherchant les maximum locaux du gradient. Le contour correspond à la valeur 19 du gradient, entre les pixels de valeurs 79 et 98

(c) En pratique, lorsqu’on utilise un détecteur de contour, on détecte beaucoup d’autres lignes qui ne sont pas des “contours d’objets“. Pourquoi ? Quels autres types de lignes détecte-t-on (donnez 3 exemples)

Ce qu’on appelle un “détecteur de contour” est en fait un détecteur de variation (gradient) dans l’image. Toute variation entre pixels peut ainsi être détectée, et pas seulement les contours. De plus, il faut seuiller le résultat obtenu, ce qui est une autre source d’erreur (paramètre de seuil à fixer)

Par exemple, on peut détecter aussi du bruit dans l’image, mais aussi d’autres types de lignes comme les lignes d’un objet (dues à la texture de l’objet),les lignes de changement  de luminance (éclairage, ombres) ou de réflectance (matériaux composant un objet), les lignes de changement d’orientation de surface d’un objet ou de changement de profondeur dans un objet en 3D, …

Question 2. Filtrage

Quelle est la différence entre le filtre médian et le filtre moyenne …

(a)… pour ce qui est de l’algorithme de calcul utilisé ?

Le filtre moyenne est un filtre linéaire qui se calcule à l’aide d’une convolution (avec une matrice uniforme comme filtre). Le filtre médian est un filtre non-linéaire qui se calcule sans utiliser de convolution ni de matrice de filtre, mais plutôt en triant et calculant la médiane entre un pixel et ses voisins

(b)… pour ce qui est de résultat obtenus ?

Les deux filtres sont utilisés pour diminuer le bruit dans une image. Le filtre moyenne marche assez bien pour tous les types de bruit, mais il rend toute l’image floue (filtre passe-bas ou lissage des contours), tandis que le filtre médian est spécialisé surtout pour le bruit de type “poivre et sel”, mais sans rendre l’image aussi floue qu’avec le premier filtre.

Cependant, il est impossible de dire quel filtre est le meilleur car cela dépend de l’objectif visé (réduire le bruit ou lisser l’image)

Question 3. Évaluation de la segmentation

Pendant le semestre, vous avez fait deux travaux pratiques où il fallait comparer la segmentation (région ou contours) fait par des algorithmes automatiques et celle faite par des humains (références). Comment comparez-vous la segmentation humaine et la segmentation automatique …

N.B. Question mal posée et ambiguë : 2 interprétation sont possibles avec cette question, surtout pour la partie (a). En conséquences, deux réponses sont possibles en (a) et les deux sont acceptées. Pour (b), la réponse est la même pour les deux interprétations.

(a)… pour ce qui est des critères utilisés ?

Première réponse possible :

La segmentation automatique (par la machine) se base surtout sur les informations provenant des pixels (niveaux de gris, couleurs, gradient, etc.). La segmentation humaine se base plutôt sur le contenu sémantique de l’image (objets réels) et la signification de ces objets de l’image (utilisé) et pas seulement les informations “chiffrées” sur les pixels

Deuxième réponse  possible

Pour comparer une segmentation automatique avec une segmentation manuelle, on utilise le principe des cartes de références. Une carte de référence représente la segmentation manuelle faite par un expert humain. Pour les contours, la comparaison est plus simple, car on veut simplement savoir si un pixel contour a été détecté ou non. Il suffit alors de calculer trois grandeurs (nb_automatique, nd_reference et nb_commun – voir énoncé de tp4 pour définitions). A partir de ces grandeurs, on calcule la précision et le rappel qui nous donnent des indications sur les pixels contours détectés et ceux qui sont manqués.

Pour comparer les régions, c’est plus difficile car tous les pixels de l’image sont étiquettes “régions” et pas seulement quelques-uns comme pour les contours. Donc il faut comparer si les pixels segmentés appartiennent à la même région dans les deux images de segmentation. De plus, le nombre et la taille des régions peuvent varier beaucoup entre les deux segmentations. L’algorithme de comparaison doit être plus élaboré ou sinon on compare seulement les plus grandes régions de l’image

(b)… pour ce qui est du résultat obtenu ?

La segmentation automatique classe les pixels en catégories ou divise l’image en régions ou en contours, mais sans du tout tenir compte de la signification de ces catégories, régions ou contours.

La segmentation humaine a plutôt tendance à diviser l’image en objets. Ces objets ont un sens pour humain (on parle de sémantique). Tous les contours ou toutes les régions ne sont pas trouvés, mais seulement ceux qui servent à décrire les objets de l’image.

En résumé, on a une segmentation symbolique (ou numérique) par la machine et une segmentation sémantique par l’humain.

N.B. Il ne suffit pas de dire que la segmentation humaine est meilleure,, mais il faut dire pourquoi

Question 4. Modification du contraste d’une image

Voici une image et son histogramme

[Image originaire] [Histogramme de l’image originaire]

Vous avez ensuite trois fonctions de modification de contraste possibles que nous pouvons appliquer sur cette image et trois histogrammes résultats (après modification de contraste). Pour chaque fonction de modification de contraste, trouvez l’histogramme résultat (pour l’image donnée). Expliquez (en quelques mots) les raisons de vos choix.

Question 5. Morphologie mathématique sur image binaire

Soit l’image suivante (14×14) et l’élément structurant (3×3) donné

Calculer le résultat après avoir fait les opérations demandées sur l’image originaire

(a) Érosion

(b) Dilatation

(c) Ouverture (Érosion + Dilatation)
Question 6. Système complet de segmentation d’images

Une expédition scientifique en Afrique fait une découverte extraordinaire. On découvre des dizaines des boites remplies de messages datant de plus de 3000 ans. Les messages sont chiffrés dans un mystérieux langage impossible à comprendre. Pour aider le décodage de ces textes, on vous demande de concevoir un programme pour faire l’acquisition des images de ces messages et pour extraire le texte automatiquement de ces messages.

Voici un exemple de message à analyser

Quels sont les critères à faire attention dans la conception de votre système et quels algorithmes pouvez-vous utiliser pour cela ? Expliquer les raisons qui motivent chacun de vos choix. Décrivez votre système selon les quatre points suivants :

(a) Acquisition des images

Pour l’acquisition de l’image, l’importance est d’avoir les mêmes conditions d’acquisitions pour toutes les images. Cela veut dire de bien contrôler l’illumination (la lumière) pour chaque prise de vue. Un bon éclairage qui réduit les reflets et les ombrages est requis. Ensuite, il faut penser à avoir une résolution (taille en pixels) d’image suffisante pour avoir tous les détails des chiffres

(b) Pré-segmentation des images

Dans cette étape, il faut réduire le plus possible le bruit présent dans les images (du aux conditions d’acquisition). Un filtre médian (par exemple, mais autres choix possibles) aidera à enlever le bruit. Ensuite, une égalisation d’histogramme permettra d’optimiser le contraste dans les images.

(c) Segmentation des images

Ici encore, il faut faire attention à avoir la même méthode pour toute les images. Étant donné que le contenu des images est surtout des images noirs sur fond blanc, un simple seuillage devrait suffire. Pour le choix du seuil, soit on fixe manuellement un seuil autour de 128 qui devrait être bon, ou sinon on utilise une méthode automatique de seuillage (basée sur l’histogramme)

D’autres méthodes de segmentation sont également possibles, régions ou contours. Quelque soit la méthode choisie, elle devrait normalement être testé sur de vraies images pour être certain.

(d) Post-segmentation des images

Afin d’être certain d’avoir les symboles en entier et bien clair, quelques opérateurs morphologiques peuvent être nécessaires. Les opérateurs exactes (érosion, dilatation, ouverture et/ou fermeture) devront être fixées après quelques tests en fonction des résultats de segmentation de l’étape précédente

Modèle multi-agent d’attraction/répulsion pour la recherche d’images par le contenu

Plan de la présentation :

  1. Introduction
    1. Contexte : Recherche d’images par le contenu (CBIR)
    2. Problématique : Similarité des images, Visualisation et interaction (Google Image Swirl)
    3. État de l’art : OSCAR (Outil de Simulation Comportementale par Attraction/Répulsion) et LEA (Learning Email Agent), Espace 2D, Mots clés, Similarité, Regroupement, Forces
      • Mutil-agents
      • Modèle d’agents réactifs à base de phéromones attractives/répulsives
      • Modèle d’agents réactifs à base de champs de potentiels attractifs/répulsifs
      • Implémentions de comportements organisationnels sous GAMA
      • Recherche d’images par le contenu
      • Requête image et textuelle (Google Similar Images / Swirl)
      • Requête image (Tineye / Google Goggles)
      • Avec retour de pertinence (Pixolu)
      • Utilisation d’une distance de similarité globale
    4. Objectif : Proposer un modèle muli-agents d’attraction/répulsion pour la recherche d’images par le contenu
      • Support de caractéristiques hétérogènes (visuelles, textuelles, temporelles)
      • Utilisation de forces attractives/répulsives
      • Possibilité de faire une ou plusieurs requêtes de type image
      • Interface graphique avec interaction utilisateur
  2. Caractérisation des images
    1. Caractéristiques visuelles
      • Signature couleur (Histobin) : Division des histogrammes R,G et B en 5 parties. Vecteur de caractéristiques
      • Signature de texture : impression visuelle, méthode des matrices de co-occurences (energie, entropie, inertie, moment differentiel inverse)
    2. Caractéristiques textuelles
      • Mots clés associés aux images
  3. Système multi-agents
    1. Une nouvelle approche
      • Méthode traditionnelle : fonction de similarité globale, calcul des distances entre les vecteurs caractéristiques, tri en fonction du taux de similarité => Résultat : une liste ordonnée d’images similaire à une requête
      • Approche multi-agents : 1 image = 1 agent, agents réactifs se déplaçant dans un espace 2D, forces d’attraction / répulsion => Résultat : disposition spatiale
    2. Choix d’implémentation
      • Travaux sur GAMA
      • Implémentation d’une nouvelle plateforme en C++
    3. Forces d’attraction/répulsion
      • Comment les forces sont elles assignées ?
      • Système itératif
      • Tout les agents ne réagissent pas avec tout le monde en même temps
      • L’inertie de mouvement permet de garder une trace des forces appliquées aux itérations précédentes
      • Forces calculées à partir de couples d’agents
        • Principe de base, exemple  avec 3 caractéristiques R, V, B
        • Modèle auto-organisationnel
        • Modèle avec requêtes
        • Le cumul de certains types de force fait émerger des comportements intéressants
    4. Stabilité du système
      • Système dynamique en mouvement perpétuel
      • Le système n’atteint jamais un état fixe
      • On juge le système “stable” lorsque le mouvement des images est limité
      • Parfois, l’état stable n’est jamais atteint. On peut fixer un nombre d’itérations maximum
  4. Résultats expérimentaux
    1. Évaluation de la performance du système
      • Résultats semblables à une approche traditionnelle globale
    2. Résultats préalables
    3. Démonstration
  5. Conclusion et perspectives
    1. Conclusion
      • Méthode de CBIR innovante
      • Traitement et visualisation simultané et en temps réel
      • Système de coordonnées polaire
      • Résultats expérimentaux proches des méthodes traditionnels
      • Mélange de caractéristiques hétérogènes
      • Le grand nombre d’itérations compense les arrondis sur les calculs
      • Parallèle avec les cartes de Kohonen
    2. Perspectives
      • Aspect visualisation améliorable
      • Étendre la capacité du système. Demande de l’optimisation
      • Possibilités illimitées en terme de caractérisation d’images (visuelles, textuelle, temporelle, retour de pertinence …)
      • Système extensive à d’autre domaines (classification d’email, recherche de personnes sur des réseaux sociaux …)

Chaine complète de traitement d’images

Étapes d’un système complet : Exemple avec un système de segmentation

  1. Acquisition des images : un grand nombre de difficultés peuvent être résolues au niveau du système de saisie
    1. Choix du type de caméra (couleur ?)
    2. Positionnement de la caméra (fixe ?)
    3. Choix de l’arrière-plan (homogène et contrastant ?)
    4. L’éclairage de la scène (arrière ou devant ?)
  2. Pré-traitement des images
    1. Enlever le bruit des images : filtres moyenne, médian, …
    2. Contraste des images : Égalisation de l’histogramme, Correction de la dynamique de l’image …
    3. Image couleur ver niveaux de gris (si nécessaire) : Ou changement d’espace couleur (TSV, Lab,…)
    4. Modifier la résolution (taille) de l’image : pas forcément besoin d’une grande image, vitesse d’exécution et précision voulue, reflets de l’image, autre défauts d’acquisition, …
  3. Segmentation des images
    1. Étape très difficile
    2. Chaque algorithme de segmentation est très différent
    3. Le but est de trouver un algo+paramétrage unique. Mêmes traitements pour toutes les images
    4. Un algorithme de segmentation seul n’est pas forcément efficace. Combinaison de plusieurs techniques
  4. Post-traitement des résultats
    1. Après la segmentation, besoin de corriger les résultats
    2. Morphologie mathématique
    3. Éliminer/corriger les erreurs de segmentation
    4. Étiquetage des régions (objets)
    5. Création de masques pour les objets voulus
  5. Analyse / sortie des résultats
    1. Besoin d’afficher l’image résultat pour un opérateur humain
    2. Reconnaissance des formes
    3. Indexation et recherche d’images
    4. Détection d’obstacles pour un robot

Images binaires

Connexité des pixels

  • Connexité-4
  • Connexité-8

Connexités différentes pour les contours et régions

  • Connexité-4 pour les régions et connexité-8 pour les contours
  • Connexité-8 pour les régions et connexité-4 pour les contours

Codage de Freeman : pour coder les directions dans une image, on utilise le codage de Freeman.

On peut ainsi coder les contours en partant d’un pixel (en haut à gauche) et en tournant dans le sens des aiguilles d’une montre

Étiquetages de composantes connexes

Fermeture des contours

Épaisseur des contours :

  • Condition importante : un contour doit avoir une épaisseur de 1 pixel partout
  • Si le contour est trop épais, où si le contour présente plusieurs chemins, on doit conserver les pixels de gradient le plus fort

Calcul et suivi du meilleur chemin dans le gradient

  • Au bout des contours, on cherche le chemin permettant de rejoindre une autre extrémité de contour : Suivi du chemin de gradient  le plus fort
  • On peut voir plusieurs chemins possibles

Seuillage par hystérésis

  • Définir deux seuils :
    • Seuil bas : minimum pour être contour
    • Seuil haut : minimum pour être contour d’un objet
  • (1) Seuiller avec le seuil haut
  • (2) Ajouter les contours connectés supérieur au seuil bas

Opérateurs morphologiques => Utilisé en post-segmentation

  • Très utilisés sur les images binaires (images de masques). Mais aussi sur les images en niveaux de gris.
  • Permettent de modifier la morphologie des objets
    • Pour nettoyer le résultat de la segmentation. Remplir les trous, éliminer le bruit
    • Pour lisser le résultat de la segmentation
  • Caractérisés par
    • un élément structurant
    • des transformations : érosion, dilatations, ouverture (érosion & dilatation), fermeture (dilatation & érosion)
  • Soit une image binaire avec fond = 0 et objet = 1
  • L’élément structurant “glisse” sur les bords (intérieurs, extérieurs) des objets et transforme sur son passage
    • des pixels d’objet en pixels de fond (érosion)
    • des pixels de fond en pixels d’objet (dilatation)
  • Érosion : Si un des pixels du masque est fond (valeur 0), alors le pixel central devient fond
  • Dilatation : Si un des pixels du masque fait partie de l’objet (valeur > 0), alors le pixel central devient objet
  • Ouverture : Érosion puis dilatation
  • Fermeture : Dilatation puis érosion