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.

Dans les examens médicaux et les actes de thérapie, les techniques minimalement invasives sont de plus en plus utilisées. Des instruments comme des aiguilles de biopsie, ou des électrodes sont utilisés pour extraire des échantillons de cellules ou pour effectuer des traitements. Afin de réduire les traumatismes et de faciliter le suivi visuelle de ces interventions, des systèmes d’assistance par imagerie médicale, comme par exemple, par l’échographie 2D, sont utilisés dans la procédure chirurgicale. Nous proposons d’utiliser l’échographie 3D pour faciliter la visualisation de l’aiguille, mais en raison de l’aspect bruité de l’image ultrasonore (US) et la grande quantité de données d’un volume 3D, il est difficile de trouver l’aiguille de biopsie avec précision et de suivre sa position en temps réel. Afin de résoudre les deux principaux problèmes ci-dessus, nous avons proposé une méthode basée sur un algorithme RANSAC et un filtre de Kalman. De même l’étude est limitée à une région d’intérêt (ROI) pour obtenir une localisation robuste et le suivi de la position de l’aiguille de biopsie en temps réel. La méthode ROI-RK se compose de deux étapes: l’étape d’initialisation et l’étape de suivi. Dans la première étape, une stratégie d’initialisation d’une ROI en utilisant le filtrage de ligne à base de matrice de Hesse est mise en œuvre. Cette étape permet de réduire efficacement le bruit de granularité du volume US, et de renforcer les structures linéaires telles que des aiguilles de biopsie. Dans la deuxième étape, après l’initialisation de la ROI, un cycle de suivi commence. L’algorithme RK localise et suit l’aiguille de biopsie dans une situation dynamique. L’algorithme RANSAC est utilisé pour estimer la position des micro-outils et le filtrage de Kalman permet de mettre à jour la région d’intérêt et de corriger la localisation de l’aiguille. Une stratégie d’estimation de mouvement est également appliquée pour estimer la vitesse d’insertion de l’aiguille de biopsie. Des volumes 3D US avec un fond inhomogène ont été simulés pour vérifier les performances de la méthode ROI-RK. La méthode a été testée dans des conditions variables, telles que l’orientation d’insertion de l’aiguille par rapport à l’axe de la sonde et le niveau de contraste (CR). La précision de la localisation est de moins de 1 mm, quelle que soit la direction d’insertion de l’aiguille. Ce n’est que lorsque le CR est très faible que la méthode proposée peut échouer dans le suivi d’une structure incomplète de l’aiguille. Une autre méthode, utilisant l’algorithme RANSAC avec apprentissage automatique a été proposée. Cette méthode vise à classer les voxels en se basant non seulement sur l’intensité, mais aussi sur les caractéristiques de la structure de l’aiguille de biopsie. Les résultats des simulations montrent que l’algorithme RANSAC avec apprentissage automatique peut séparer les voxels de l’aiguille et les voxels de tissu de fond avec un CR faible. / In medical examinations and surgeries, minimally invasive technologies are getting used more and more often. Some specially designed surgical instruments, like biopsy needles, or electrodes are operated by radiologists or robotic systems and inserted in human’s body for extracting cell samples or delivering radiation therapy. To reduce the risk of tissue injury and facilitate the visual tracking, some medical vision assistance systems, as for example, ultrasound (US) systems can be used during the surgical procedure. We have proposed to use the 3D US to facilitate the visualization of the biopsy needle, however, due to the strong speckle noise of US images and the large calculation load involved as soon as 3D data are involved, it is a challenge to locate the biopsy needle accurately and to track its position in real time in 3D US. In order to solve the two main problems above, we propose a method based on the RANSAC algorithm and Kalman filter. In this method, a region of interest (ROI) has been limited to robustly localize and track the position of the biopsy needle in real time. The ROI-RK method consists of two steps: the initialization step and the tracking step. In the first step, a ROI initialization strategy using Hessian based line filter measurement is implemented. This step can efficiently reduce the speckle noise of the ultrasound volume, and enhance line-like structures as biopsy needles. In the second step, after the ROI is initialized, a tracking loop begins. The RK algorithm can robustly localize and track the biopsy needles in a dynamic situation. The RANSAC algorithm is used to estimate the position of the micro-tools and the Kalman filter helps to update the ROI and auto-correct the needle localization result. Because the ROI-RK method is involved in a dynamic situation, a motion estimation strategy is also implemented to estimate the insertion speed of the biopsy needle. 3D US volumes with inhomogeneous background have been simulated to evaluate the performance of the ROI-RK method. The method has been tested under different conditions, such as insertion orientations angles, and contrast ratio (CR). The localization accuracy is within 1 mm no matter what the insertion direction is. Only when the CR is very low, the proposed method could fail to track because of an incomplete ultrasound imaging of the needle. Another methodology, i.e. RANSAC with machine learning (ML) algorithm has been presented. This method aims at classifying the voxels not only depending on their intensities, but also using some structure features of the biopsy needle. The simulation results show that the RANSAC with ML algorithm can separate the needle voxels and background tissue voxels with low CR.