Extraction de caractéristique en vision par ordinateur

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir extraction de caractéristique (homonymie).

En vision par ordinateur, l'extraction de caractéristiques visuelles (ou visual features extraction en anglais) consiste en des transformations mathématiques calculées sur les pixels d'une image numérique. Les caractéristiques visuelles permettent généralement de mieux rendre compte de certaines propriétés visuelles de l'image, utilisées pour des traitements ultérieurs entrant dans le cadre d'applications telles que la détection d'objets ou la recherche d'images par le contenu.

Localisation des caractéristiques[modifier | modifier le code]

On distingue usuellement[1] les caractéristiques globales qui sont calculées sur toute l'image et les caractéristiques locales qui sont calculées autour de points d'intérêt. On peut aussi parler des caractéristiques semi-locales quand celles-ci sont extraites dans des zones restreintes de l'images, résultant d'une segmentation de l'image en région ou simplement selon une grille arbitraire.

La distinction entre caractéristiques globales et locales a un intérêt taxinomique. Les caractéristiques locales se distinguent par le fait qu'elles sont distinctes, robustes aux occlusions (car il y en a beaucoup dans un image ou une région) et qu'elles ne nécessitent pas de segmentation[2]. Un descripteur local calculé en chaque pixel d'une image ou d'une région obtenue par segmentation, puis accumulé dans un histogramme est donc une description globale de l'image ou de la région.

Caractéristiques globales[modifier | modifier le code]

Couleur[modifier | modifier le code]

Histogramme et dérivés[modifier | modifier le code]

La prise en compte de la couleur des images a été historiquement l'une des premières caractéristiques employées pour la recherche d'images par le contenu et produit encore des résultats parfois spectaculaires sur certaines bases. C'est en 1991 que Swain et Ballard ont proposé d'utiliser un histogramme couleur pour ce genre de tâche[3]. Il représente la distribution globale des couleurs dans l'image. Son calcul consiste en une quantification de l'espace couleur choisi (RVB par exemple) suivie du calcul de l'histogramme des pixels ainsi transformés. Par exemple, si l'on considère une image RVB classique et que l'on quantifie chaque plan couleur sur 4 bins, l'histogramme résultant aura une dimension 4^3=64. Si l'image est originellement codée sur 24 bits (la valeur de chaque plan est dans l'intervalle [0-255]), l'histogramme couleur sur 64 bins pourrait être représenté par un « cube » 4\times 4\times 4:


  Rouge
0-63 64-127 128-191 192-255
Vert Vert Vert Vert
0-63 64-127 128-191 192-255 0-63 64-127 128-191 192-255 0-63 64-127 128-191 192-255 0-63 64-127 128-191 192-255
Bleu 0-63 x x x x x x x x x x x x x x x x
64-127 x x x x x x x x x x x x x x x x
128-191 x x x x x x x x x x x x x x x x
192-255 x x x x x x x x x x x x x x x x

Chaque couleur représentant l'un des 64 bins quantifiés, et x étant alors le nombre de pixels de l'image correspondant à ce bin. En pratique, ce descripteur est généralement représenté par un vecteur mono dimensionnel à 64 dimensions.

De nombreux descripteurs peuvent être dérivés de la représentation par histogramme, dont plusieurs ont été inclus au modèle expérimental de la norme MPEG-7. Il s'agit notamment de:

  • dominant color: rend compte de la couleur dominante d'une image, calculée comme celle du bin ayant la plus grande valeur. L'espace de couleur peut être quelconque en théorie, mais l'utilisation de HSV donne des résultats intéressants[4].
  • scalable colour: il s'agit de la transformée de Haar de l'histogramme couleur dans l'espace HSV, ce qui résulte en un code très compact.
  • coulour structure: il s'agit d'un histogramme couleur «local». Sa construction est identique au principe présenté précédemment (histogramme couleur global), si ce n'est qu'un fenêtre de taille réduite (8x8 pixels) parcourt l'image lors du comptage des couleurs en chaque pixel. Il reflète ainsi un certaine information sur la structure spatiale de la répartition des couleurs.
  • colour layout: la transformée en cosinus discrète de la représentation en histogramme est calculée et seule une partie des coefficients peut être utilisée pour la signature. Cela donne la possibilité d'obtenir un descripteur relativement grossier mais très compact ou bien un descripteur plus fin mais prenant plus de place. Un tel descripteur est intéressant pour des applications nécessitant une certaine scalabilité

Moments de couleur[modifier | modifier le code]

Dès 1995, il a été proposé d'utiliser les moments calculés dans un espace de couleur donné pour caractériser les images[5]. On se restreint généralement aux deux ou trois premiers moments (moyenne, variance, asymétrie voire le moment d'ordre 4 appelé kurtosis) mais ils sont calculés dans chacun des trois plans de l'espace couleur choisi. Un rafinement possible consiste à diviser l'image selon une grille et à calculer ces moments dans chaque cellule.

Autocorrélogramme de couleur[modifier | modifier le code]

La couleur d'un pixel p=(x,y) \in I étant notée I(p), définissons l'ensemble I_c \triangleq \{ p|I(p)=c\}. Ainsi p\in I_c signifie que le pixel p de l'image I a une couleur c. Considérons une valeur de distance entre pixels d\in [\![ 1  \dots n ]\!] fixée a priori. La distance utilisée est par exemple L_\infty définie pour deux pixels p_1=(x_1,y_1) et p_2=(x_2,y_2) par L_\infty(p_1,p_2) \triangleq \max\{ |x_1-x_2|,|y_1-y_2|\}. Le corrélogramme pour i,j\in [\![ 1  \dots m ]\!] et k\in [\![ 1  \dots d ]\!]est alors défini par:

 \gamma^{k}_{c_i,c_j}(I) \triangleq  \overset{Pr}{p_1 \in I_{c_i}, p_2\in I_{c_j}}[p_2\in I_{c_j} | L_\infty(p_1-p_2)=k]

Cela reflète la probabilité qu'un pixel à une distance k du pixel considéré soit de couleur c_j. La taille du corrélogramme est O(m^2d).

L'autocorrélogramme est défini par:

\alpha^{(k)}_c(I)\triangleq \gamma^{k}_{c,c}(I)

Il nécessite un espace d'ordre O(md).

Forme[modifier | modifier le code]

Décrire les formes nécessite une identification préalable de régions. Cela peut résulter d'une segmentation de l'image ou de la détection de leurs contours. On peut alors caractériser les régions au moyen de divers indices telle leur orientation principale (par exemple leur premier axe propre), leur symétrie ou encore leurs moments de Zernike.

Une méthode de description particulièrement utilisée est celle proposée par Mokhtarian, appelée Curvature Scale Space[6]. Elle consiste à décrire une région en fonction des variations de courbure de son contour. Pour une courbe plane en coordonnées paramétriques dans un repère orthonormé \scriptstyle{ r(t) = (x(t),y(t))}, la courbure s'exprime par:

\gamma(t) = \frac{x'y''-y'x''}{(x'^2+y'^2)^{3/2}}.

Cette description est invariante en rotation et translation. Concernant le zoom, il faut a minima normaliser par la longueur du contour. Plus important, le descripteur est généralement calculé à différentes échelles, chacune correspondant à la convolution par un noyau gaussien.

Texture[modifier | modifier le code]

A une certaine échelle, une foule peut être vue comme une texture.

La définition de la texture n'est pas évidente et dépend de l'échelle[7],[8] . On distingue trois approches pour définir la notion de texture. Dans la veine des travaux pioniers de Haralick[9], une première approche considère une texture comme résultant d'un processus stochastique et cherche à les décrire en termes de propriétés statistiques des valeurs et positions relatives des pixels[10],[11].

La seconde approche suppose l'existence de primitives fondamentales permettant de décrire les textures, tels les Textons définis par Julesz[12]. Par suite, une texture donnée est décrite comme une combinaison complexe de ces primitives, exprimée par exemple avec des graphes.

Une approche plus récente s'inspire plutôt de la perception visuelle et tend à rendre compte du processus de formation des textures du point de vue humain[13].

Approche stochastique[modifier | modifier le code]

Une texture peut être décrite statistiquement, en rendant compte de la manière dont les niveaux de gris de l'image s'organisent les uns par rapport aux autres. On considère un opérateur de position p permettant de définir une matrice P_{ij} qui compte le nombre de fois qu'un pixel de niveau de gris i est présent à la posiiton p d'un pixel de niveau j. Si la matrice est normalisée entre 0 et 1, on parle de matrice de cooccurrence de niveau de gris[14]. La position relative de deux pixels peut aussi être définie par un angle \theta et une distance d. Par exemple, si on considère trois niveaux de gris possibles et l'image I définie par:

I=\begin{pmatrix}
0 &1 & 2 & 2\\
0 & 0 & 1 & 2\\
0 & 0 & 1& 2\\
0 & 0 & 0& 1\\
0 & 0 & 1& 1\\
\end{pmatrix}

Et l'opérateur est à droite de (également défini par un angle \theta=0 et une distance d=1 pixel), alors la matrice de cooccurrence (non normalisée) est:

C=\begin{pmatrix}
5 & 5 & 0 \\
0 & 1 & 3 \\
0 & 0 & 1\\
\end{pmatrix}

Le 3 de la matrice C signifiant que l'on trouve trois fois un pixel de valeur 2 (donc en troisième colonne) à la droite d'un pixel de valeur 1 (donc en seconde ligne).

À partir de cette matrice de cooccurrence, il est possible de définir maints descripteurs, tels que ceux répertoriés dans cette table:

Opérateur Formulation
Maximum \max_{ij}(C_{ij})
Différence d'ordre k \sum_{i}\sum_{j}{c_{ij}\,(i-j)^k }
Entropie \sum_i\sum_j{ c_{ij}\,log(c_{ij})}
Uniformité \sum_i{\sum_j{c_{ij}^2}}

Une autre approche statistique largement utilisée est le modèle MSAR (Multiresolution Simultaneous Autoregressive Models[15]) utilisé, au delà de la reconnaissance de texture, pour reconnaître des scènes naturelles[16].

Approche structurelle[modifier | modifier le code]

Cette approche suppose l'existence de primitives fondamentales permettant de décrire les textures. L'un des premiers exemple de tels primitives a été les Textons proposés par Julesz[12]. Une texture donnée est décrite comme une combinaison complexe de ces primitives, exprimée par exemple avec des graphes. Ces graphes peuvent alors servir de descripteurs de la texture.

Approche spectrale[modifier | modifier le code]

L'expression des périodicités et autres régularités dans une image ou dans un signal se fait naturellement dans le cadre de l'analyse spectrale. Ainsi une transformée de Fourier discrète de l'image peut être une base pour fabriquer des descripteurs. Néanmoins, il est plus courant d'utiliser un ensemble de filtres de Gabor disposés à plusieurs échelles et orientations. Cela permet notamment d'identifier des « traits perceptifs majeurs » [17]. Des travaux ont montré qu'un descripteur basé sur une telle description spectrale pouvait rendre compte de la structure spatiale dominante d'une scène naturelle[18].

Une alternative à la transformée de Fourier est de calculer la transformée en cosinus discrète (DCT). En pratique des descripteurs basés sur les coefficients DCT ont permis de discriminer des images d'intérieur et d'exterieur[19], des images de paysages urbains contre des paysages naturels[20] et, combinés à d'autres descripteurs, plusieurs catégories de scènes naturelles simultanément[16].

Caractéristiques locales[modifier | modifier le code]

La caractérisation d'une image peut être calculée en un nombre restreint de pixel. Il faut pour cela d'abord détecter les zones d'intérêt de l'image puis calculer en chacune de ces zones un vecteur caractéristiques. Ces zones d'intérêt sont par exemple les arêtes ou les points saillants de l'image (zones de fort contraste). Il peut aussi s'agir de points pris aléatoirement ou régulièrement dans l'image (échantillonnage dit dense).

Le vecteur caractéristique contient parfois des données provenant de la détection, telles que l'orientation de l'arête ou la magnitude du gradient dans la zone d'intérêt. Généralement, le vecteur caractéristique en un pixel est calculé sur un voisinage de ce pixel, c'est-à-dire à partir d'une imagette centrée sur ce pixel. Il peut être calculé à différentes échelles de manière à s'affranchir du facteur de zoom. Parmi les caractéristiques locales couramment calculées, on retrouve des motifs préalablement utilisés globalement, tels que des histogrammes de couleur ou des vecteurs rendant compte de l'orientation des gradients des niveaux de gris.

Trois exemples de voisinages utilisés pour définir une texture et calculer un motif binaire local (LBP)

Certaines méthodes telles SIFT ou SURF incluent à la fois la détection de zone d'intérêt et le calcul d'un vecteur caractéristique en chacune de ces zones. Concernant le vecteur caractéristique, les SIFT sont grossièrement un histogramme des orientations du gradient et les SURF consistent en le calcul d' approximation d'ondelettes de Haar. Dans une veine similaire, les motifs binaires locaux sont un calcul de cooccurrence des niveaux de gris locaux d'une image et les HOG des histogrammes de gradients orientés, assez similaires aux SIFT, calculés selon un échantillonnage dense.

Agrégation[modifier | modifier le code]

La description d'une images au moyen de caractéristique locale a généralement une dimension variable, dépendant du nombre de points d'intérêt extraits (en fait, ce nombre fois la dimension du descripteur local). Une telle représentation n'est donc pas adaptée à nourrir des algorithmes d'apprentissage classiquement utilisés (SVM, boosting...). Pour se ramener à une représentation dans un espace vectoriel de dimension fixe, il est fait appel à des technique d'agrégation de descripteurs telle celle des sac de mots (bag of visterms)[21]. Le résultat d'une telle accumulation est donc une caractéristique globale d'une image ou d'une partie d'image (région).

Applications[modifier | modifier le code]

Les caractéristiques d'images extraites selon les modalités expliquées ci-dessus sont utilisées dans de nombreux domaines de la vision par ordinateur.

Associés à des images annotées, ils peuvent servir d'entrée à un algorithme d'apprentissage supervisé en vue de leur classification. Cela peut notamment servir à détecter leur contenu et en particulier les objets présents dans l'image. Dans la même veine mais dans des domaines plus spécifiques, ils peuvent servir à détecter des visages ou des personnes.

Pouvant servir de signature d'image, ces descripteurs sont aussi utilisés dans la recherche d'images par le contenu.

D'une manière générale, ce sont des technologies de base servant dans de nombreux domaines où la vision par ordinateur intervient: robotique, vidéo-surveillance, vision industrielle, reconnaissance optique de caractères, etc...

Notes et références[modifier | modifier le code]

  1. Présentation sur la description des images, transparents 22 à 36.
  2. Mikolajczyk, K.; Schmid, C., "A performance evaluation of local descriptors," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.27, no.10, pp.1615,1630, Oct. 2005 (section 1, ligne 4-5)
  3. MJ Swain, DH Ballard: Color Indexing, International Journal of Computer Vision, 1991
  4. Y. Liu, D.S. Zhang, G. Lu and W.-Y Ma. Region-based image retrieval with perceptual colors. Proc. Pacific-Rim Multimedia Conference, pp 931-938, décembre 2004.
  5. M. Stricker and M. Orengo. Similarity of color images. In In SPIE Conference on Storage and Retrieval for Image and Video Databases III, volume 2420, pages 381­­392, Feb. 1995.
  6. Mokhtarian, F., and Mackworth, A.K., Scale Based Description and Recognition of Planar Curves and Two-Dimensional Shapes, PAMI(8), No. 1, January, 1986, pp. 34-43.
  7. Th. Gevers and A.W.M. Smeulders, Content-based Image Retrieval: An Overview, from the book Emerging Topics in Computer Vision, G. Medioni and S. B. Kang (Eds.), Prentice Hall, 2004
  8. John R. Smith and Shih-fu Chang, An Image and Video Search Engine for the World-Wide Web, In Proc. SPIE Storage and Retrieval for Image and Video Databases, 1997
  9. Haralick R., Shanmugam K. & Dinstein I. (1973) Textural features for image classification. IEEE Transactions on Systems, Man, and Cybernetics 3(6): 610–621.
  10. Weszka J, Dyer C & Rosenfeld A (1976) A comparative study of texture measures for terrain classification. IEEE Transactions on Systems, Man, and Cybernetics 6: 269–285.
  11. Unser M (1986) Sum and difference histograms for texture classification. PAMI 8(1): 118–125.
  12. a et b Julesz B (1981) Textons, the elements of texture perception, and their interactions. Nature 290: 91–97.
  13. Chellappa R & Manjunath B (2001) Texture classification and segmentation: tribulations, triumphs and tributes. In: Davis L (ed) Foundations of Image Understanding,pp 219–240. Kluwer.
  14. R.M. Haralick, Texture feature for image classification, IEEE Transactions on Systems, Man, and Cybernetics 3 (1973) (1), pp. 610–621
  15. J. Mao and A. K. Jain, “Texture classification and segmentation using multiresolution simultaneous autoregressive models,” Pattern Recognit.,vol. 25, pp. 173–188, Feb. 1992.
  16. a et b A. Vailaya,M.A.T Figeiredo A. Jain and H.J. Zhang. Image classification for content-based indexing. IEEE transaction on image processing, vol 10, N°1, 2001
  17. H. Tamura, S. Mori, and T. Yamawaki. Texture features corresponding to visual perception. IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-8, no. 6, 1978, 460 - 473
  18. Aude Oliva, Antonio Torralba.Modeling the shape of the scene: a holistic representation of the spatial envelope. International Journal of Computer Vision, Vol. 42(3): 145-175, 2001
  19. M. Szummer and R.W. Picard. Indoor-outdoor image classification. IEEE international workshop on content-based access of images and video databases. Bombay, India, 1998
  20. A. Vailaya, A. Jain and H.J. Zhang. On image classification: city vs landscape. Pattern Recognition, vol 31, N° 12, pp 1921-1935, 1998
  21. J. Sivic and Andrew Zisserman. Video Google : A text retrieval approach to object matching in videos. In Proceedings of the International Conference on Computer Vision, pages 1470–1477, 2003.