Dans cette thèse, nous nous sommes intéressés au problème de l'extraction d'une surface à partir de la représentation volumique d'un objet. Dans ce but, nous nous sommes concentrés sur les méthodes de division spatiale. Ces approches divisent le volume afin de construire une approximation par morceaux de la surface de l'objet. L'idée générale consiste à faire des approximations surfaciques locales qui seront ensuite combinées pour extraire une surface unique représentant l'objet. Les approches basées sur l'algorithme " Marching Cubes " (MC) présentent des défaut par rapport à la qualité et l'adaptativité de la surface produite. Même si une considérable quantité d'améliorations ont été apportées à la méthode originale, la plus grande partie des algorithmes fournissent la solution à un ou deux défauts mais n'arrivent pas à surmonter toutes ses limitations.Les méthodes duales sont plus adaptées pour utiliser un échantillonnage adaptatif sur le volume d'intérêt. Ces méthodes reposent sur la génération de surfaces duales à celles construites par MC ou se basent sur des grilles duales. Elles construisent des maillages moins denses et en même temps capables de mieux approcher les détails de l'objet. De plus, des améliorations récentes garantissent que les maillages extraits ont de bonnes propriétés topologiques et géométriques.Nous avons étudié les caractéristiques spécifiques des objets volumiques par rapport à leur géométrie et à leur topologie. Nous avons exploré l'état de l'art sur les approches de division spatiale afin d'identifier leurs avantages et leurs inconvénients ainsi que les implications de leur utilisation sur des objets volumiques. Nous avons conclu qu'une approche duale était la mieux adaptée pour obtenir un bon compromis entre qualité du maillage et qualité de l'approximation. Dans un second temps, nous avons proposé et développé un pipeline de génération de surfaces basé sur une combinaison d'une approche duale et de la recherche de composantes connexes n-dimensionnels pour mieux reproduire la topologie et la géométrie des objets originels. Dans un troisième temps, nous avons présenté une extension "out-of-core" de notre chaîne de traitements pour l'extraction des surfaces à partir de grands volumes. Le volume est divisé pour générer des morceaux de surface de manière indépendante et garde l'information nécessaire pour les connecter afin de produire une surface unique topologiquement correcte.L'approche utilisée permet de paralléliser le traitement pour accélérer l'obtention de la surface. Les tests réalisés ont permis de valider la méthode sur des données volumiques massives. / In this document, we have been interested in the surface extraction from the volumetric representation of an object. With this objective in mind, we have studied the spatial subdivision surface extraction algorithms. This approaches divide the volume in order to build a piecewise approximation of the surface. The general idea is to combine local and simple approximations to extract a complete representation of the object's surface.The methods based on the Marching Cubes (MC) algorithm have problems to produce good quality and to handle adaptive surfaces. Even if a lot of improvements to MC have been proposed, these approaches solved one or two problems but they don't offer a complete solution to all the MC drawbacks. Dual methods are more adapted to use adaptive sampling over volumes. These methods generate surfaces that are dual to those generated by the Marching Cubes algorithm or dual grids in order to use MC methods. These solutions build adaptive meshes that represent well the features of the object. In addition, recent improvements guarantee that the produced meshes have good geometrical and topological properties.In this dissertation, we have studied the main topological and geometrical properties of volumetric objects. In a first stage, we have explored the state of the art on spatial subdivision surface extraction methods in order to identify theirs advantages, theirs drawbacks and the implications of theirs application on volumetric objects. We have concluded that a dual approach is the best option to obtain a good compromise between mesh quality and geometrical approximation. In a second stage, we have developed a general pipeline for surface extraction based on a combination of dual methods and connected components extraction to better capture the topology and geometry of the original object. In a third stage, we have presented an out-of-core extension of our surface extraction pipeline in order to extract adaptive meshes from huge volumes. Volumes are divided in smaller sub-volumes that are processed independently to produce surface patches that are later combined in an unique and topologically correct surface. This approach can be implemented in parallel to speed up its performance. Test realized in a vast set of volumes have confirmed our results and the features of our solution.

This report evaluates possibilities to combine volumetric ultrasound (us) data together with the recent work published on advanced skin rendering techniques. We focus mainly on how to filter us data and localize surfaces within us data. We also evaluate recent skin rendering techniques in order to have a good understanding of what is needed from the us for rendering realistic skin. us data is acquired using sonography and have a low signal-to-noise ratio by nature, this makes it harder to extract surfaces compared to other medical data acquisition methods such as ct and mr. This report present an algorithm which implements a variational classification technique to emphasize surfaces within us and using a rbf network to fit an implicit function to these surfaces. Using this approach presented we have successfully extract smooth meshes from the noisy us data.

Dans le contexte des sciences archéologiques, des images tridimensionnelles issues de scanners tomodensitométriques sont segmentées en régions d’intérêt afin d’en faire une analyse. Ces objets virtuels sont souvent utilisés dans le but d’effectuer des mesures précises. Une partie de ces analyses nécessite d’extraire la surface des régions d’intérêt. Cette thèse se place dans ce cadre et vise à améliorer la précision de l’extraction de surface. Nous présentons dans ce document nos contributions : tout d’abord, l’algorithme du HMH pondéré dont l’objectif est de positionner précisément un point à l’interface entre deux matériaux. Appliquée à une extraction de surface, cette méthode pose des problèmes de topologie sur la surface résultante. Nous avons donc proposé deux autres méthodes : la méthode du HMH discret qui permet de raffiner la segmentation d’objet 3D, et la méthode du HMH surfacique qui permet une extraction de surface contrainte garantissant l’obtention d’une surface topologiquement correcte. Il est possible d’enchainer ces deux méthodes sur une image 3D pré-segmentée afin d’obtenir une extraction de surface précise des objets d’intérêt. Ces méthodes ont été évaluées sur des acquisitions simulées d’objets synthétiques et des acquisitions réelles d’artéfacts archéologiques. / In the context of archaeological sciences, 3D images produced by Computer Tomography scanners are segmented into regions of interest corresponding to virtual objects in order to make some scientific analysis. These virtual objects are often used for the purpose of performing accurate measurements. Some of these analysis require extracting the surface of the regions of interest. This PhD falls within this framework and aims to improve the accuracy of surface extraction. We present in this document our contributions : first of all, the weighted HMH algorithm whose objective is to position precisely a point at the interface between two materials. But, applied to surface extraction, this method often leads to topology problems on the resulting surface. So we proposed two other methods : The discrete HMH method which allows to refine the 3D object segmentation, and the surface HMH method which allows a constrained surface extraction ensuring a topologically correct surface. It is possible to link these two methods on a pre-segmented 3D image in order to obtain a precise surface extraction of the objects of interest These methods were evaluated on simulated CT-scan acquisitions of synthetic objects and real acquisitions of archaeological artefacts.

Extracting surfaces, representing boundaries of objects of interest, from volumetric images, has important applications in various scientific domains, from medicine to geology. In this thesis, I introduce novel mathematical, computational, and algorithmic machinery for extraction of sheet-like surfaces (with boundary), whose boundary is unknown a-priori, a particularly important case in applications that has no convenient methods. This case of a surface with boundaries has applications in extracting faults (among other geological structures) from seismic images in geological applications. Another application domain is in the extraction of structures in the lung from computed tomography (CT) images. Although many methods have been developed in computer vision for extraction of surfaces, including level sets, convex optimization approaches, and graph cut methods, none of these methods appear to be applicable to the case of surfaces with boundary. The novel methods for surface extraction, derived in this thesis, are built on the theory of Minimal Paths, which has been used primarily to extract curves in noisy or corrupted images and have had wide applicability in 2D computer vision. This thesis extends such methods to surfaces, and it is based on novel observations that surfaces can be determined by extracting topological structures from the solution of the eikonal partial differential equation (PDE), which is the basis of Minimal Path theory. Although topological structures are known to be difficult to extract from images, which are both noisy and discrete, this thesis builds robust methods based on Morse theory and computational topology to address such issues. The algorithms have run-time complexity O(NlogN), less complex than existing approaches. The thesis details the algorithms, theory, and shows an extensive experimental evaluation on seismic images and medical images. Experiments show out-performance in accuracy, computational speed, and user convenience compared with related state-of-the-art methods. Lastly, the thesis shows the methodology developed for the particular case of surfaces with boundary extends to surfaces without boundary and also surfaces with different topologies, such as cylindrical surfaces, both important cases for many applications in medical image analysis.

Le but de ce travail était la mise en place d’une chaîne méthodologique de planification virtuelle d’une ostéotomie sagittale des branches mandibulaires (OSBM) et son transfert au bloc opératoire. Dans la première partie, les méthodes classiques de planification et de transfert sont exposées. Habituellement réalisées à partir de modèles en plâtre sur articulateur, la planification et la production de guides occlusaux chirurgicaux souffrent d’une imprécision potentiellement à l’origine de troubles fonctionnels temporo-­‐mandibulaires. Le contrôle per-­‐opératoire du condyle mandibulaire lors de l’OSBM est un élément de stabilité squelettique dont dépend la qualité du résultat fonctionnel. Une évaluation des pratiques professionnelles des chirurgiens maxillo-­‐faciaux a été réalisée sur ce point. Une méthode de positionnement condylien utilisant un dispositif, moins fréquemment utilisée que la méthode empirique, est proposée comme présentant le meilleur rapport bénéfice/risque. Cette méthode a été reproduite virtuellement à travers les différents maillons de la chaîne méthodologique. Des techniques innovantes informatisées d’acquisition, de conception et modélisation, et d’impression en 3 dimensions ont été utilisées. Dans la seconde partie, la méthodologie de chacun des maillons de la chaîne a été présentée et évaluée, soit sur sujets cadavériques, soit sur patients. L’objectif était de démontrer la faisabilité de la chaîne. Le maillon « acquisition et extraction de surface » a mis en exergue le problème des artéfacts dus aux matériaux métalliques dentaires ou orthodontiques. Dans 90% des cas le maillage obtenu était satisfaisant, permettant de s’affranchir des modèles en plâtre. Le maillon « planification chirurgicale virtuelle » a montré une valorisation par rapport à la technique classique en terme de prévention des interférences des pièces osseuses déplacées. Le maillon « modélisation et impression du guide chirurgical » a décrit les étapes d’invention d’un guide de positionnement occlusal et condylien (OCPD : occlusal and condylar positionning device). Ses caractéristiques techniques, ses modalités de production par impression 3D ainsi que son utilisation peropératoire, ont été précisées. Enfin le maillon « évaluation de l’OCPD » a permis de montrer la faisabilité de la méthode et l’équivalence clinique, technique et biologique de ce dispositif médical sur mesure par rapport à ceux utilisés dans la méthode classique. Enfin le positionnement condylien obtenu grâce à ce dispositif a été évalué de manière préliminaire et comparé aux données de la littérature. Grâce à l’OCPD, nous avons montré la possibilité de transférer au bloc opératoire la planification virtuelle d’une OSBM contrôlant la position des condyles / The purpose of this work was the implementation of a methodological chain for bilateral sagittal split osteotomy (BSSO) virtual planning and its transfer in the operating room. In the first part of the work, usual methods for planning BSSO are exposed. Usually realized from plaster models on articulator, the planning and the occlusal surgical guides production are at risk of temporo-­‐mandibular functional disorders. The quality of the functional result depends on the correct positioning of the mandibular condyle, considered as a skeletal stability element. An assessment of the maxillofacial surgeons practices was realized regarding intra-­‐operative condyle positioning. Using a condylar positioning device (CPD),less frequently employed than the empirical method, meets an acceptable benefit/risk balance. This method was virtually reproduced through various steps of the methodological chain described. Computerized innovative techniques for three-­‐dimensional acquisition, design and manufacturing were used. In the second part of the work, the methodology of each step of the chain was presented and estimated, either on cadaveric subjects, or on patients. The aim was to demonstrate the feasibility of the whole chain. The “acquisition and surface extraction” step pointed the issue of artefacts due to dental or orthodontic metallic devices. Ninety % of the obtained meshes were satisfactory, allowing not to use plaster models. The “virtual surgical planning” step allowed reproducing the usual method and showed great interest in bone interferences prevention. The “modelling and printing of the surgical guide” step described the stages of occlusal and condylar positioning device (OCPD) invention. Its technical characteristics, its methods of manufacturing by 3D printing, and its intraoperative use were specified. The step “OCPD evaluation” showed the method feasibility and the clinical, technical and biological equivalence of this custom-­‐made medical device as compared to those used in the usual method. Finally the condylar position obtained with this device was estimated in a preliminary clinical study and compared with the literature. Thanks to the OCPD, we showed the possibility of transferring in the operating room an OSBM virtual planning controlling condyles position.