Antoine Meler - BetaSAC et OABSAC, deux nouveaux échantillonnages conditionnels pour RANSAC

L’algorithme RANSAC est l’approche la plus commune pour l’estimation robuste des paramètres d’un modèle en vision par ordinateur. C’est principalement sa capacité à traiter des données contenant potentiellement plus d’erreurs que d’information utile qui fait son succès dans ce domaine où les capteurs fournissent une information très riche mais très difficilement exploitable. Depuis sa création, il y a trente ans, de nombreuses modifications ont été proposées pour améliorer sa vitesse, sa précision ou sa robustesse. Dans ce travail, nous proposons d’accélérer la résolution d’un problème par RANSAC en utilisant plus d’information que les approches habituelles. Cette information, calculée à partir des données elles-même ou provenant de sources complémentaires de tous types, nous permet d’aider RANSAC à générer des hypothèses plus pertinentes. Pour ce faire, nous proposons de distinguer quatre degrés de qualité d’une hypothèse : la "non contamination", la "cohésion", la "cohérence" et enfin la "pertinence". Puis nous montrons à quel point une hypothèse non contaminée par des données erronées est loin d’être pertinente dans le cas général. Dès lors, nous nous attachons à concevoir un algorithme original qui, contrairement aux méthodes de l’état de l’art, se focalise sur la génération d’échantillons "pertinents" plutôt que simplement "non contaminés". Notre approche consiste à commencer par proposer un modèle probabiliste unifiant l’ensemble des méthodes de réordonnancement de l’échantillonnage de RANSAC. Ces méthodes assurent un guidage du tirage aléatoire des données tout en se prémunissant d’une mise en échec de RANSAC. Puis, nous proposons notre propre algorithme d’ordonnancement, BetaSAC, basé sur des tris conditionnels partiels. Nous montrons que la conditionnalité du tri permet de satisfaire des contraintes de cohérence des échantillons formés, menant à une génération d’échantillons pertinents dans les premières itérations de RANSAC, et donc à une résolution rapide du problème. L’utilisation de tris partiels plutôt qu’exhaustifs, quant à lui, assure la rapidité et la randomisation, indispensable à ce type de méthodes. Dans un second temps, nous proposons une version optimale de notre méthode, que l’on appelle OABSAC (pour Optimal and Adaptative BetaSAC), faisant intervenir une phase d’apprentissage hors ligne. Cet apprentissage a pour but de mesurer les propriétés caractéristiques du problème spécifique que l’on souhaite résoudre, de façon à établir automatiquement le paramétrage optimal de notre algorithme. Ce paramétrage est celui qui doit mener à une estimation suffisamment précise des paramètres du modèle recherché en un temps (en secondes) le plus court. Les deux méthodes proposées sont des solutions très générales qui permettent d’intégrer dans RANSAC tout type d’information complémentaire utile à la résolution du problème. Nous montrons l’avantage de ces méthodes pour le problème de l’estimation d’homographies et de géométries épipolaires entre deux photographies d’une même scène. Les gains en vitesse de résolution du problème peuvent atteindre un facteur cent par rapport à l’algorithme RANSAC classique.