L'algorithme RANSAC (Random Sample Consensus) est l'approche la plus populaire 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 ou 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êmes 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. Afin de concevoir notre approche, nous commençons 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. La partialité des tris, quant à elle, 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 le bénéfice de ces méthodes sur 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. / RANSAC algorithm (Random Sample Consensus) is the most common approach for the problem of robust parameters estimation of a model in computer vision. This is mainly its ability to handle data containing more errors than potentially useful information that made its success in this area where sensors provide a very rich but noisy information. Since its creation thirty years ago, many modifications have been proposed to improve its speed, accuracy and robustness. In this work, we propose to accelerate the resolution of a problem by using RANSAC with more information than traditional approaches. This information, extracted from the data itself or from complementary sources of all types, is used help generating more relevant RANSAC hypotheses. To do this, we propose to distinguish four degrees of quality of a hypothesis: inlier, consistent, coherent or suitable sample. Then we show how an inlier sample is far from being relevant in the general case. Therefore, we strive to design a novel algorithm which, unlike previous methods, focuses on the generation of suitable samples rather than inlier ones. We begin by proposing a probabilistic model unifying all the RANSAC reordered sampling methods. These methods provide a guidance of the random data selection without impairing the search. Then, we propose our own scheduling algorithm, BetaSAC, based on conditional partial sorting. We show that the conditionality of the sort can satisfy consistency constraints, leading to a generation of suitable samples in the first iterations of RANSAC, and thus a rapid resolution of the problem. The use of partial rather than exhaustive sorting ensures rapidity and randomization, essential to this type of methods. In a second step, we propose an optimal version of our method, called OABSAC (for Optimal and Adaptive BetaSAC), involving an offline learning phase. This learning is designed to measure the properties of the specific problem that we want to solve in order to determine automatically the optimal setting of our algorithm. This setting is the one that should lead to a reasonably accurate estimate of the model parameters in a shortest time (in seconds). The two proposed methods are very general solutions that integrate into RANSAC any additional useful information. We show the advantage of these methods to the problem of estimating homographies and epipolar geometry between two photos of the same scene. The speed gain compared to the classical RANSAC algorithm can reach a factor of hundred.

L’objectif de cette thèse est de proposer un algorithme de segmentation et de suivi du myocarde basé sur le formalisme des ensembles de niveaux. Nous modélisons dans un premier temps le myocarde par un modèle géométrique (hyperquadriques) qui permet de représenter des formes asymétriques telles que le myocarde tout en évitant une étape d’apprentissage. Ce modèle est ensuite inclus dans le formalisme des ensembles de niveaux afin de servir de contrainte de forme lors de la segmentation simultanée de l’endocarde et de l’épicarde. Ce terme d’a priori de forme est couplé à un terme local d’attache aux données ainsi qu’à un terme évitant la fusion des deux contours. L’algorithme est validé sur 80 images en fin systole et en fin diastole segmentées par 3 cardiologues. Dans un deuxième temps, nous proposons de segmenter l’ensemble d’une séquence en utilisant l’information de mouvement. Dans ce but, nous faisons l’hypothèse de conservation des niveaux de la fonction implicite associée à l’ensemble de niveaux et l’exprimons comme une énergie dans un formalisme variationnel. Cette énergie est ensuite ajoutée à l’algorithme décrit précédemment pour la segmentation statique du myocarde afin de contraindre temporellement l’évolution du contour. L’algorithme est alors validé sur 20 séquences échocardiographiques (soit environ 1200 images) segmentées par 2 experts. / The aim of this work is to propose an algorithm to segment and track the myocardium using the level-set formalism. The myocardium is first approximated by a geometric model (hyperquadrics) which allows to handle asymetric shapes such as the myocardium while avoiding a learning step. This representation is then embedded into the level-set formalism as a shape prior for the joint segmentation of the endocardial and epicardial borders. This shape prior term is coupled with a local data attachment term and a thickness term that prevents both contours from merging. The algorithm is validated on a dataset of 80 images at end diastolic and end systolic phase with manual references from 3 cardiologists. In a second step, we propose to segment whole sequences using motion information. To this end, we apply a level conservation constraint on the implicit function associated to the level-set and express this contraint as an energy term in a variational framework. This energy is then added to the previously described algorithm in order to constrain the temporal evolution of the contour. Finally the algorithm is validated on 20 echocardiographic sequences with manual references of 2 experts (corresponding to approximately 1200 images).