Gaspard Jankowiak Arbres de decision pour la classification d'images resultats

De Ensiwiki
Aller à : navigation, rechercher


Arbres de décision pour la classification d'images

Labo Laboratoire Jean Kuntzmann
Equipe LEAR
Encadrants Roger.Mohr_(at)_imag.fr Jakob.Verbeek_(at)_inrialpes.fr, Roger.Mohr_(at)_imag.fr

Etudiant

Gaspard Jankowiak

Introduction

On s'intéresse ici au problème général de la catégorisation des images, c'est-à-dire l'association d'une ou plusieurs étiquettes sémantiques aux images dont on dispose. Ces étiquettes peuvent être très générales : maison, personne, et dans notre cas d'application, les vélos. C'est un problème d'une importance capitale aujourd'hui puisque de plus en plus d'appareils sont capables de prendre des photos, ce qui génère un grand nombre d'images. Dans la plupart des cas, nous n'avons aucune information sur le contenu réel de celles-ci, d'où l'importance de leur attacher des étiquettes "sémantiques". Par ailleurs, comme le nombre d'images à traiter est important, il est capital d'avoir une complexité d'utilisation la plus petite possible. Enfin, cette tâche présente un certain nombre de difficultés :

  • Les objets peuvent être partiellement cachés (occlusion).
  • Les angles de prise de vue sont très variables.
  • La luminosité varie aussi de manière importante (photos de jour / de nuit)
  • Certains objets se ressemblent mais n'appartiennent pas à la même catégorie (vélos / motos par exemple)


Eléments de pré-requis

Une approche efficace de ce problème est inspirée du modèle "bag-of-words" de l'analyse de texte. Les mots du textes sont considérés comme des occurrences non ordonnées et équiprobables dans le texte. Dans le monde de l'image, le concept devient "bag-of-visual-words", et les mots deviennent des "régions" de l'image (points selles par exemple), codées en un vecteur de grande taille (dim ~ 100). L'idée très schématique est "d'entrainer" l'ordinateur à reconnaître les bons et les mauvais vecteurs à l'aide d'un échantillon d'images. Une fois ces "mots visuels" obtenus, on les sépare en clusters, on obtient ainsi des histogrammes qui représentent la distribution des mots dans les clusters. On peut alors associer à chaque groupe un poids, ce qui permet d'obtenir un score pour l'image en sommant sur tous les patchs (régions), et ensuite de classer l'image.

Deux algorithmes utilisent cette idée générale :

  • k-means clustering : cette méthode donne de bons résultats, mais elle est assez lente, et très générique pour les problèmes de clustering. Elle ne tient en particulier pas compte d'un étiquetage a priori des images d'apprentissage.
  • les arbres de décision aléatoires : bien plus rapide, l'idée de cette méthode est d'associer à chaque patch l'étiquette de l'image dont il provient. Ensuite, on divise l'espace récursivement en utilisant un critère de seuil : pour chaque région de l'espace, on tire au hasard T coordonnées et seuils et on garde la "meilleure" combinaison sur toutes les régions. La région correspondante est coupée en 2 sous-régions, et on continue. Le problème ici est que la mesure de "meilleure" ne tient pas compte du lien entre les images et les patchs. On optimise donc la probabilité de prédire l'étiquette correcte des patchs, ce qui n'est pas forcément la même chose que prédire l'étiquette des images.

Illustration de la clusterisation

Travail réalisé

Modélisation

Mon travail a consisté en l'amélioration du modèle précédent, en prenant en compte le lien images - patchs. Le nouveau modèle est inspiré de celui des arbres de décision, il est assez simple à formaliser. Il est admet une unique solution, mais contrairement au modèle précédent, il n'admet plus de solution analytique. Il a donc fallu trouver une méthode itérative efficace pour la résolution, et l'algorithme E.M. s'est montré approprié. L'évaluation de chaque combinaison (composante + seuil) est cependant très coûteuse et cela induit un temps de calcul bien supérieur au modèle précédent. Pour cela, j'ai développé des variantes -approximatives- dans le calcul de l'évaluation pour réduire ce coût, qui reste cependant important pour l'apprentissage.

Expérimentation

J'ai comparé le nouveau modèle à la méthode k-means et aux arbres de décision aléatoires avec une implémentation MATLAB. Pour cela, j'ai utilisé la base de données GRAZ, avec 600 images au total, la moitié pour l'apprentissage, l'autre moitié pour évaluer la performance (précision). Celle-ci est mesurée avec une méthode répandue dans l'apprentissage machine, la Précision Moyenne (Average Precision).

J'ai aussi utilisé plusieurs arbres en parallèle, c'est une bonne méthode pour améliorer la performance avec une augmentation de coût linéaire.

Résultats

Les deux modèles existants affichent des résultats similaires, avec une forte croissance de la précision pour un petit nombre de feuilles. Cependant, une asymptote apparaît vers 85%.

Résultats pour les arbres classiques
Précision Moyenne pour les arbres de décision classiques.

Avec le modèle que j'ai proposé, les résultats sont intéressants :

  • pour la version de base, on n'a pas de gain particulier en précision, on est toujours dans la même zone que les arbres de décision classiques (représentés avec les courbes plus fines).
  • la version approchée par contre nous donne un gain en précision de 5% pour 5 et 10 arbres, ce qui est assez intéressant. De plus, on dépasse le plateau des 85% pour atteindre 90%.
Résultats pour les arbres améliorés
Précision Moyenne pour les arbres de décision avec le nouveau modèle.

Conclusion

Les résultats sont étonnants (version approchée plus précise que la version de base), et montrent toujours une certaine variabilité, d'autres tests seraient nécessaires. Mais on voit déjà que le nouveau modèle se comporte bien et apporte un réel gain de précision. Certes, ceci se fait au détriment du temps de calcul, mais seulement lors de l'apprentissage, qui ne se fait que sur un groupe restreint d'images. Lors de l'utilisation réelle (classification de milliers d'images), la structure est la même que précédemment, et le coût en calcul reste le même (voire diminue un peu puisqu'on a la même précision avec moins de clusters).

Pour des études futures, il pourrait être intéressant de regarder un autre modèle pour la prise en compte du lien images - patchs, qui ne dégrade pas autant les performances.

Références

Rapides (Wikipedia)

Approfondies

  • Algorithme EM et arbres de décision :

C. Bishop. Pattern Recognition and Machine Learning. Springer, October 2007.

  • Plus d'informations sur l'extraction des patchs, descripteur SIFT, démo dispo :

D. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Com- puter Vision, 60(2):91–110, 2004.

F. Moosmann, B. Triggs, and F. Jurie. Fast discriminative visual codebooks using randomized clustering forests. In Advances in Neural Information Processing Systems, 2007.

Documents additionnels