Apprentissage a contrario et architecture efficace pour la détection d’évènements visuels significatifs

La détection a contrario

 La prise de décision dans un algorithme de détection d’objets (au sens large) peut être vue comme un problème de test statistique d’hypothèses : étant donné un candidat ou une observation w dans l’image, il faut décider s’il est le résultat de l’hypothèse H0 où aucun objet n’est présent, ou bien s’il est le résultat de l’hypothèse H1 de présence d’un objet. La méthode optimale qui minimise le risque d’erreur est connue, il s’agit de la classification bayésienne [DHS01]. Cette méthode conclut qu’un objet est présent si la probabilité a posteriori de H1 est supérieure à un certain seuil : P(H1|w) > δ. Le seuil δ détermine le compromis entre le taux de fausses alarmes toléré et le taux de détection. On distingue généralement deux catégories de méthodes pour estimer cette probabilité a posteriori : les méthodes discriminantes et les méthodes génératives. Les méthodes discriminantes tentent d’estimer directement P(H1|w), on y trouve essentiellement les techniques d’apprentissage statistique telles que les réseaux de neurones, les machines à vecteur support ou les approches à base de boosting (adaboost, etc.) [DHS01]. La principale limitation de ces approches est la difficulté à constituer des ensembles d’apprentissage pertinents : les exemples doivent être indépendants et distribués selon la probabilité a priori P(w). De plus, un grand nombre d’exemples est généralement requis pour obtenir une bonne estimation. Les méthodes génératives s’appuient quant à elles sur la règle de Bayes pour estimer P(H1|w) : P(H1|w) > δ ⇔ P(w|H1)P(H1) P(w) > δ ⇔ P(w|H1)P(H1) P(w|H1)P(H1) + P(w|H0)P(H0) > δ ⇔ 1 + P(w|H0)P(H0) P(w|H1)P(H1) < 1 δ ⇔ P(w|H0) P(w|H1) < ( 1 δ − 1)P(H1) P(H0) ⇔ P(w|H0) P(w|H1) < δ0 ⇔ PH0 (w) PH1 (w) < δ0 Ce calcul classique montre que décider en fonction de P(H1|w) est équivalent à décider en fonction du ratio des vraisemblances de H0 et H1 pour l’observation w. Les méthodes génératives fournissent des modèles pour H0 et H1 permettant de calculer PH0 (w) et PH1 (w), c’est-à-dire d’expliquer comment les observations sont statistiquement générées sous chacune des deux hypothèses. Dans les deux cas, il est nécessaire de spécifier explicitement et quantitativement l’apparence des objets à détecter dans une image, par des exemples pour les méthodes discriminantes, ou bien par un modèle pour les méthodes génératives. Cette tâche est souvent très difficile en vision par ordinateur, car les images naturelles sont très variables et les changements d’illumination ou d’environnement peuvent radicalement modifier l’apparence des objets. Les modèles ou les exemples proposés sont alors uniquement pertinents pour certains types d’images, et des paramètres ont souvent besoin d’être ajustés d’une image à l’autre. Pour obtenir des algorithmes de détection génériques adaptés à tous les types d’images, Agnès Desolneux, Lionel Moisan et Jean-Michel Morel ont proposé la méthodologie a contrario [DMM00b], qui ne cherche pas à estimer explicitement l’apparence des objets dans l’image. L’objectif initial était de donner une formalisation mathématique à la théorie de la Gestalt [Des00], et les premiers travaux se sont attachés à détecter des groupements géométriques correspondants à des gestalts partielles, comme des alignements ou des contours. Cette méthodologie se base sur un principe énoncé par Helmholtz, selon lequel plus une structure a une probabilité faible d’être le résultat du hasard, plus elle est perceptible par notre système visuel. Les gestalts que nous percevons seraient alors des groupements non accidentels dans une image, comme l’illustre la figure 1.1. FIG. 1.1 – Images de bruit où les pixels sont indépendants et identiquement distribués. Dans chaque image, des pixels noirs ont été ajoutés dans une zone rectangulaire de 6 × 4 pixels à la même position. Plus la proportion globale de pixels noirs PN est faible, plus la probabilité d’obtenir une forte concentration locale de pixels noirs par hasard est faible, et plus le rectangle devient perceptuellement significatif. On peut calculer combien on s’attend à trouver de rectangles avec une densité de pixels noirs aussi forte par hasard dans chaque cas. Mathématiquement, il s’agit de l’espérance d’une variable aléatoire, appelée NFA (voir section 1.2). Plus cette espérance est faible, et plus le rectangle est significatif. Cette formulation permet de quantifier de façon intuitive le caractère significatif du rectangle. Outre ces motivations phénoménologiques, le raisonnement a contrario s’est montré utile par la suite pour des applications dépassant le cadre initial de la théorie de la Gestalt (voir la section 1.3). Appliquée à la détection d’objets au sens large, la méthodologie consiste tout d’abord à identifier une ou plusieurs mesures discriminantes dont on suppose a priori que plus leurs valeurs sont grandes, plus il y a de chances qu’un objet soit présent. L’information perceptuelle portée par les mesures est ensuite quantifiée par le principe de Helmholtz en calculant la probabilité d’obtenir des valeurs aussi grandes par hasard. Plus cette probabilité est faible, et plus l’objet est perceptuellement saillant. Les objets peuvent alors être détectés en recherchant les candidats dont les mesures sont statistiquement trop élevées pour être accidentelles. Ainsi, seul un modèle du hasard également appelé modèle a contrario est nécessaire pour quantifier statistiquement la confiance dans la présence d’un objet. Nous continuons ce chapitre par une formalisation mathématique plus précise de la méthodologie a contrario, qui reprend les concepts de l’ouvrage de référence [DMM08], mais avec une formulation parfois différente. Nous ferons ensuite un tour d’horizon des travaux a contrario existants, qui sont tous basés sur le cadre purement analytique établit par [DMM00b]. Nous montrerons cependant que les calculs purement analytiques permettent difficilement de combiner plusieurs mesures discriminantes ou d’utiliser des heuristiques de recherche de candidats dirigées par les données. Ces limitations motiveront le développement d’approches mixtes combinant calculs analytiques et apprentissage dans les chapitres suivants. 

1.2 Formalisation mathématique 

Notion de PFA 

Plusieurs éléments sont nécessaires pour raisonner a contrario : – Un ensemble de mesures discriminantes, représentées par des variables aléatoires. Une variable est dite discriminante si plus elle est grande, plus il y a de chance qu’un objet soit présent. – Éventuellement, un ensemble de mesures non discriminantes, représentées également par des variables aléatoires. Nous les appellerons par la suite variables conditionnantes, car elles vont servir à prendre en compte le contexte pour évaluer le degré de confiance statistique associé aux variables discriminantes. – Un modèle a contrario permettant d’estimer la distribution des variables sous l’hypothèse H0 où leurs valeurs sont le résultat du hasard. Exemple En s’inspirant de la figure 1.1, nous illustrons les concepts de cette section par une application dont le but est de détecter des taches noires rectangulaires dans une image. Pour cet exemple, il est naturel de prendre comme variable discriminante le nombre K de pixels noirs dans un rectangle : plus il est grand, plus il y a de chances pour qu’une tache noire soit présente. La significativité perceptuelle du nombre de pixels noirs d’un rectangle donné dépend de la densité globale PN de pixels noirs sur l’image et de la taille L du rectangle, nous prenons donc ces deux mesures comme variables conditionnantes. Nous considérons enfin comme modèle a contrario un modèle où les pixels sont spatialement indépendants et identiquement distribués. Ainsi, les taches noires seront détectées à partir du moment où la concentration de pixels noirs est trop forte pour être le résultat d’un arrangement spatial accidentel de pixels. Il est supposé a priori que plus les variables discriminantes sont grandes, plus un objet a de chances d’être présent. En s’appuyant sur le principe de Helmholtz, la significativité perceptuelle de l’objet pour une observation candidate w peut alors être estimée en calculant la probabilité que les variables discriminantes soient aussi grandes que celles de w par hasard. Définition 1 (Probabilité de fausse alarme). Soient H0 l’hypothèse de “hasard”, X = {X1, . . . , Xi} un vecteur de variables aléatoires discriminantes, Y = {Y1, . . . , Yj} un vecteur de variables aléatoires conditionnantes et w une observation candidate. On note X ≥ X(w) l’évènement {X1 ≥ X1(w), X2 ≥ X2(w), . . . , Xi ≥ Xi(w)}. La probabilité de fausse alarme associée à l’observation w est définie par : PFA(w) = PH0 (X ≥ X(w) | Y = Y(w)) La probabilité de fausse alarme d’une observation w mesure donc à quel point il est probable d’observer des valeurs discriminantes aussi grandes que celles de w par hasard, étant donné ses variables conditionnantes. Cette probabilité est calculée à l’aide du modèle a contrario de hasard choisi a priori. 1.2. Formalisation mathématique 21 Plus PFA(w) est faible, moins les variables de l’observation w sont susceptibles d’être aussi grandes par hasard, et donc, a contrario, plus elles sont susceptibles d’être associées à un objet à détecter. La probabilité de fausse alarme permet de classer les observations par degré de confiance : on dira qu’une observation w1 est plus significative, et donc plus probablement associée à un objet qu’une observation w2 si PFA(w1) < PFA(w2). Le rôle du modèle a contrario est donc de servir de référence statistique pour évaluer la confiance dans la présence d’un objet pour chacune des observations, en fonction des mesures discriminantes et du contexte. Remarque Par souci de simplicité, ce chapitre se focalise sur des variables discriminantes telles que plus leurs valeurs sont grandes, plus un objet a de chances d’être présent. Il est bien entendu possible de raisonner de façon opposée avec des variables telles que plus leurs valeurs sont petites, plus un objet a de chances d’être présent. Les évènements considérés par la probabilité de fausse alarme seraient alors de type Xi ≤ Xi(w). De tels évènements seront utilisés dans le chapitre 3. Exemple Pour la détection de taches noires, le vecteur discriminant pour un rectangle R contient une seule variable K, le nombre de pixels noirs dans le rectangle. Le vecteur conditionnant contient les deux variables PN et L, respectivement la densité globale de pixels noirs sur l’image et la taille de R. La PFA de R est donc donnée par : PFA(R) = PH0 (K ≥ K(R) | L = L(R), PN ) Le modèle a contrario choisi pour H0 considère que les pixels sont indépendants et identiquement distribués. Chacun des pixels de R peut donc être vu comme une variable de Bernouilli Zi qui vaut 1 (noir) avec une probabilité PN et 0 (blanc) avec une probabilité 1 − PN . Le nombre de pixels noirs K dans le rectangle correspond alors à la somme des L(R) variables Zi , sa loi est donc binomiale, de paramètres L(R) et PN : PH0 (K ≥ K(R) | L = L(R), PN ) = B≥(K(R), L(R), PN ) avec B≥(k, n, p) = Pn i=k 

Télécharger le document complet