Le Filtrage linéaire d’une image

Détection de contours

La détection de contours est une étape préliminaire à de nombreuses applications de l’analyse d’images. En effet les contours constituent des indices riches, au même titre que les points d’intérêts, pour toute interprétation ultérieure de l’image. Les contours dans une image proviennent des :
➤ Discontinuités de la fonction de réflectance (texture, ombre),
➤ Discontinuités de profondeur (bords de l’objet).
et sont caractérisés par des discontinuités de la fonction d’intensité dans les images. Le principe de la détection de contours repose donc sur l’étude des dérivéesde la fonction d’intensité dans l’image : les extrema locaux du gradient de la fonction d’intensité et les passages par zéro du laplacien. La difficulté réside dans la présence de bruit dans les images.

Dérivation par filtrage optimal
Les dérivations présentées consistent à convoluer l’image par des masques de petites dimensions. Ces approches sont donc dépendantes de la taille des objets traités, elles sont aussi très sensible au bruit. Un autre type d’approches plus récentes repose sur la définition de critères d’optimalité de la détection de contours ces critères débouchant sur des filtres de lissage optimaux.

De l’image des dérivées aux contours
Les différents filtres présentés permettent de calculer le gradient ou le laplacien d’une image mais ne donnent pas des points de contours. Un traitement ultérieur est nécessaire, ce traitement étant dépendant du type d’approche choisi.

Les approches de détection de contours

Deux approches sont utilisées:
➤ Approche gradient : détermination des extrema locaux dans la direction du gradient,
➤ Approche laplacien : détermination des passages par zéro du laplacien.
Ces approches reposent sur le fait que les contours correspondent des discontinuités d’ordre 0 de la fonction d’intensité. Le calcul de dérivée nécessite un pré-filtrage des images. Filtrage linéaire pour les bruits de moyenne nulle (par exemple bruit blanc Gaussien, filtre Gaussien). Filtrage non-linéaire pour les bruits impulsionnels (filtre médian par exemple). Les différentes approches existantes se classent ensuite suivant la manière d’estimer les dérivées de la fonction d’intensité :
➤ Différences finies,
➤ Filtrage optimal,
➤ Modélisation de la fonction d’intensité.

Détection de points d’intérêts

La détection de points d’intérêts (ou coins) est, au même titre que la détection de contours, une étape préliminaire à de nombreux processus de vision par ordinateur. Les points d’intérêts, dans une image, correspondent à des doubles discontinuités de la fonction d’intensités. Celles-ci peuvent être provoquées, comme pour les contours, par des discontinuités de la fonction de réflectance ou des discontinuités de profondeur. Ce sont par exemple : les coins, les jonctions en T ou les points de fortes variations de texture.

Les Avantages
Les Avantages des points d’intérêts sont :
➤ Sources d’informations plus fiables que les contours car plus de contraintes sur la fonction d’intensité,
➤ Robuste aux occultations (soit occulté complètement, soit visible),
➤ Pas d’opérations de chainage (=> contours !),
➤ Présents dans une grande majorité d’images (≠ contours !).

Les Différentes approches

De nombreuses méthodes ont été proposées pour détecter des points d’intérêts. Elles peuvent être classées grossièrement suivant trois catégories :
❖ Approches contours : l’idée est de détecter les contours dans une image dans un premier temps. Les points d’intérêts sont ensuite extraits le long des contours en considérants les points de courbures maximales ainsi que les intersections de contours,
❖ Approches intensité : l’idée est cette fois-ci de regarder directement la fonction d’intensité dans les images pour en extraire directement les points de discontinuités,
❖ Approches à base de modèles : les points d’intérêts sont identifiés dans l’image par mise en correspondance de la fonction d’intensité avec un modèle théorique de cette fonction des points d’intérêts considérés. Les approches de la deuxième catégorie sont celles utilisées généralement. Les raisons sont : indépendance vis à vis de la détection de contours (stabilité), indépendance vis à vis du type de points d’intérêts (méthodes plus générales).

La segmentation
La segmentation d’images est un problème important dans le traitement numérique des images. La segmentation est une opération qui a pour objectif la description de l’information contenue dans l’image en donnant une représentation plus condensée et facilement exploitable. Il est difficile de définir d’une manière absolue, une ‘bonne’ segmentation. La segmentation, souvent, n’est pas une fin en soi, sa qualité influe directement sur les résultats obtenus par les traitements situés en aval de l’étape de segmentation.

Les différentes approches de segmentation

La segmentation fait référence aux notions de différence et de similarité perçues par le système visuel humain. Ceci donne naissance à deux approches couramment qualifiés d’approche ‘frontière’ et d’approche ‘région’. L’approche région s’attache à faire apparaître des régions homogènes selon un critère (niveaux de gris ou texture), alors que l’approche frontière tente de trouver des contours ou frontières de régions présentant une variation rapide du même critère. Un algorithme de segmentation s’appuie donc sur :
➤ la recherche de discontinuités afin de mettre en évidence les contours,
➤ la recherche d’homogénéité locale pour définir les régions,
➤ ou encore sur la coopération des deux principes.

Les types de segmentation

Il existe deux types de segmentation à savoir :

Segmentation en contours

La recherche des contours dans une image numérique est un des problèmes les plus étudiés depuis l’origine des travaux sur l’imagerie numérique. Ceci est en grande partie dû à la nature très intuitive du contour qui apparaît très naturellement comme l’indice visuel idéal dans la plus grande partie des situations. Très schématiquement, les contours sont les lieux de variations significatives de l’information niveaux de gris (il n’est pas question ici des travaux sur les contours dans les images couleurs ou multispectrales). Dans cette approche, on suppose que l’image est une mosaïque de régions parfaitement homogènes. C’est à dire que les contours recherchés sont de type créneaux. De plus, la transition étant stricte, un contour doit être une chaîne de pixels d’épaisseur 1. Cette restriction sur la nature du contour a été imposée dans un premier temps pour des raisons de formalisation mathématique. Il est possible de construire des processus capables d’extraire d’autres types de contours comme par exemple des vallées ou des toits. Cependant, il n’existe pas à l’heure actuelle de processus complet et général qui pourrait extraire tous les types de contour. La notion de contour étant reliée à celle de variation, il est évident qu’une telle définition nous amène tout naturellement vers une évaluation de la variation en chaque pixel. Une variation existera si le gradient est localement maximum ou si la dérivée seconde (à définir dans un espace bi-dimensionnel) présente un passage par zéro. Les principaux algorithmes connus (Sobel, Prewitt, Kirsh, Canny, Dériche, …) se focalisent sur ce premier aspect du contour. Il existe moins de travaux sur la formalisation de la deuxième partie consistant à passer d’une mesure locale de variations à des chaines de points d’épaisseur 1. C’est pourtant cette deuxième partie qui fait souvent la différence et la qualité visuelle d’un résultat. Nous allons d’abord présenter les méthodes d’extraction de points de contour, par des techniques de filtrage gradient ou laplacien. Puis nous verons quelques techniques de chaînage de ces points (suivi de contour) et de représentation des contours finaux ainsi obtenus .

Calcul du gradient

Le gradient, en un pixel d’une image numérique, est un vecteur caractérisé par son amplitude et sa direction. L’amplitude est directement liée à la quantité de variation locale des niveaux de gris. La direction du gradient est orthogonale à la frontière qui passe au point considéré. La méthode la plus simple pour estimer un gradient est donc de faire un calcul de variation monodimensionnelle, i.e. en ayant choisi une direction donnée. On a alors le schéma suivant :

Gd(x,y) = (I * Wd)(x,y)

où Wd désigne l’opérateur de dérivation dans la direction d et * le produit de convolution.

Gd(x,y) = Σ i=-m,+m Σ j=-n, +n I(x+i,y+j) . Wd(i,j)

Dans cette version discrète, la taille de cet opérateur est donnée par le couple (m, n). Sauf cas très particulier, on utilise toujours m=n. Il existe de très nombreux opérateurs différents ( Roberts, Sobel, Prewitt, Kirsch, …) qui ont globalement les mêmes propriétés. Le gradient étant un vecteur, l’approche la plus classique pour estimer le gradient consiste à choisir deux directions privilégiées (naturellement celles associées au maillage, i.e. ligne et colonne) orthogonales, sur lesquelles on projette le gradient. A partir de deux calculs identiques à celui présenté ci-dessus, on peut donc obtenir une connaissance parfaite du gradient :

G(x,y) = (GX(x,y),GY(x,y) ) = ((I * WX)(x,y), (I * WY)(x,y))

L’amplitude du gradient s’obtient alors par l’une des formules suivantes :

m(x,y) = (GX(x,y)2 + GY(x,y)2) ½
m(x,y) = |GX(x,y)| + |GY(x,y)|
m(x,y) = Max(|GX(x,y)| + |GY(x,y)|)

Et la direction du gradient est donnée par:

d(x,y) = Arctg( GY(x,y) / GX(x,y))

Cette approche présente comme principal inconvénient le fait que la direction peut prendre n’importe quelle valeur réelle. Ceci n’est pas en accord avec la nature discrète d’une image. Que représente une frontière orientée à 17° sur une grille ? C’est pourquoi on peut adopter un schéma différent adapté à la nature discrète de l’image. Il s’agit alors de calculer le gradient, non plus dans deux directions, mais dans toutes les directions possibles de l’image : 0°, 45°, 90°, 135°. On peut se contenter de ces 4 directions. On a alors :

m(x,y) = Maxd = 0°, 45°, 90°, 135° md(x,y)
d(x,y) = arg Maxd md (x,y)

Là encore, on peut imaginer plusieurs types de masques ( Sobel, Prewitt, Kirsch, …).

Table des matières

INTRODUCTION GENERALE
Chapitre I : Vision par ordinateur
INTRODUCTION
I. Détection de contours
1. Définitions
a. Le Filtrage linéaire d’une image
b. Le gradient d’une image
c. Le laplacien d’une image
d. Les filtres séparables
e. Dérivation par différence finies
f. Dérivation par filtrage optimal
g. De l’image des dérivées aux contours
2. Les approches de détection de contours
II. Détection de points d’intérêts
1. Les Avantages
2. Les Différentes approches
III. La segmentation
1. Définition
2. Les différentes approches de segmentation
3. Les types de segmentation
a. Segmentation en contours
i. Calcul du gradient
ii. Calcul du Laplacien Dérivée seconde et recherche des zero-crossing
iii. Chaînage des points de contour
iv. Détermination des seuils sur l’amplitude
v. Suppression directionnelle des non maxima locaux
vi. Extraction des éléments essentiels
vii. Reconstitution des points par hystérésis
viii. Codage des contours
b. Segmentation en régions
i. Le seuillage
ii. Quelques critères d’homogénéité
IV. Reconnaissance d’objets
Chapitre II : Présentation de l’OpenGL
INTRODUCTION
I. Fonctionnalités d’OpenGL
1. Bibliothèques d’OpenGL
a. OpenGL Library (GL)
b. OpenGL Utility Library (GLU)
c. OpenGL extension to X-Windows (GLX)
d. Auxiliary Library
e. OpenGL Tk Library (GLTk)
f. OpenGL Utility Toolkit (GLUT)
2. Syntaxe de la librairie GL
3. Processus de visualisation en OpenGL
4. Transformations géométriques
a. Transformations d’utilité générale
b. Transformation spécifique à la visualisation (view)
c. Transformations de projection
5. Les listes d’affichage
a. Commandes principales des listes d’affichage
6. Les textures
Chapitre III : CONCEPTION
INTRODUCTION
I. Architecture des classes
1. La classe graph
2. La classe Vertex
3. La classe Edge
II. Structure de données
1. Types de données
2. Fonctions
III. Transformée de Hough
IV. Diagramme de classe
Chapitre IV : REALISATION
I. Présentation de l’application
1. Volet lecture de données leurs traitement et calcul du résultat
2. Volet visualisation
II. Environnement de développement
1. Le Dev-C++
2. GLUT
III. Captures d’écran
CONCLUSION
BIBLIOGRAPHIE

Lire le rapport complet