Purpose: Ultrasound is prevalent in image-guided therapy as a safe, inexpensive, and widely available imaging modality. However, extensive training in interpreting ultrasound images is essential for successful procedures. An open-source ultrasound image simulator was developed to facilitate the training of ultrasound-guided spinal intervention procedures, thereby eliminating the need for an ultrasound machine from the phantom-based training environment. Methods: Anatomical structures and surgical tools are converted to surface meshes for data compression. Anatomical data is converted from segmented volumetric images, while the geometry of surgical tools is available as a surface mesh. The pose of the objects are either constants or live measurements from a pose tracking device. Intersection points between the surface models and the ultrasound scan lines are determined with a binary space partitioning tree. The scan lines are divided into segments and filled with grey values determined by an intensity calculation accounting for material properties, reflection, and attenuation parameters defined in a configuration file. The scan lines are then converted to a regular brightness-mode ultrasound image. Results: The simulator was tested in a tracked ultrasound imaging system, with a mock transducer tracked by an Ascension TrakStar electromagnetic tracker, on a spine phantom. A mesh model of the spine was created from CT. The simulated ultrasound images were generated at a speed of 50 frames per second, and a resolution of 820 x 616 pixels on a PC with a 3.4 GHz processor. A human subject trial was conducted to compare the learning performance of novice trainees with real and simulated ultrasound in the localization of the facet joints of a spine phantom. With 22 participants split into two equal groups and each participant localizing 6 facet joints, there was no statistical difference in the performance of the two groups, indicating that simulated ultrasound could indeed replace the real ultrasound in phantom-based ultrasonography training for spinal interventions. Conclusion: The ultrasound simulator was implemented and integrated into the open-source Public Library for Ultrasound (www.plustoolkit.org) and SlicerIGT (www.SlicerIGT.org) toolkits / Thesis (Master, Computing) -- Queen's University, 2013-07-24 12:28:57.201

The creation of 3D models of bone from CT images has become popular for surgical planning, the design of implants, and educational purposes. Software is available to convert CT images into 3D models of bone, however, these can be expensive and technically taxing. The goal of this project was to create an open-source and easy-to-use methodology to create 3D models of bone and allow the user to interact with the model to extract desired regions. The method was first created in MATLAB and ported to Python. The CT images were imported into Python and the images were then binarized using a desired threshold determined by the user and based on Hounsfield Units (HU). A Canny edge detector was applied to the binarized images, this extracted the inner and outer surfaces of the bone. Edge points were assigned x, y, and z coordinates based on their pixel location, and the location of the slice in the stack of CT images to create a 3D point cloud. The application of a Delaunay tetrahedralization created a mesh object, the surface was extracted and saved as an STL file. An add-on in Blender was created to allow the user to select the CT images to import, set a threshold, create a 3D mesh model, draw an ROI on the model, and extract that region based on the desired thickness and create a new 3D object. The method was fully open-sourced so was inexpensive and was able to create models of a skull and allow the segmentation of portions of that mesh to create new objects. Future work needs to be conducted to improve the quality of the mesh, implement sampling to reduce the time to create the mesh, and add features that would benefit the end-user. / Thesis / Master of Applied Science (MASc) / The creation of 3D models of bone from CT images has become popular for education, surgical planning, and the design of implants. Software is available to convert CT images into 3D models but can be expensive and technically taxing. The purpose of this project was to develop a process to allow surgeons to create and interact with models from imaging data. This project applied a threshold to binarize a set of CT images, extracted the edges using a Canny Edge detector, and used the edge pixels to create a 3D point cloud. The 3D point cloud was then converted to a mesh object. A user interface was implemented that allowed the selection of portions of the model and a new 3D model to be created from the selection. The process can be improved by improving the quality of the mesh output and adding features to the user interface.

Surface mesh generation is a critical component of the mesh generation process. The objective of the described effort was to determine if a combination of constrained Delaunay triangulation (for triangles), advancing front method (for quadrilaterals), curvature-based refinement, smoothing, and reconnection is a viable approach for discretizing a NURBS patch holding the boundary nodes fixed. The approach is significant when coupled with recently developed geometry specification that explicitly identifies common edges. This thesis describes the various techniques used to achieve the above objectives. Application of this approach to several representative geometries demonstrates that it is an effective alternative to traditional approaches.

SOMBRA, Tiago Guimarães. Geração adaptativa de malhas de superfícies paramétricas em paralelo com controle de curvatura. 2016. 71 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T19:12:42Z No. of bitstreams: 1 2016_dis_tgsombra.pdf: 7997002 bytes, checksum: 8e8712a9b19d272a16ac263f62596436 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T16:43:38Z (GMT) No. of bitstreams: 1 2016_dis_tgsombra.pdf: 7997002 bytes, checksum: 8e8712a9b19d272a16ac263f62596436 (MD5) / Made available in DSpace on 2016-07-22T16:43:38Z (GMT). No. of bitstreams: 1 2016_dis_tgsombra.pdf: 7997002 bytes, checksum: 8e8712a9b19d272a16ac263f62596436 (MD5) Previous issue date: 2016 / This work describes a technique for generating parametric surfaces meshes using parallel computing, with distributed memory processors. The input for the algorithm is a set of parametric patches that model the surface of a given object. A structure for spatial partitioning is proposed to decompose the domain in as many subdomains as processes in the parallel system. Each subdomain consists of a set of patches and the division of its load is guided following an estimate. This decomposition attempts to balance the amount of work in all the subdomains. The amount of work, known as load, of any mesh generator is usually given as a function of its output size, i.e., the size of the generated mesh. Therefore, a technique to estimate the size of this mesh, the total load of the domain, is needed beforehand. This work makes use of an analytical average curvature calculated for each patch, which in turn is input data to estimate this load and the decomposition is made from this analytical mean curvature. Once the domain is decomposed, each process generates the mesh on that subdomain or set of patches by a quad tree technique for inner regions, advancing front technique for border regions and is finally applied an improvement to mesh generated. This technique presented good speed-up results, keeping the quality of the mesh comparable to the quality of the serially generated mesh. / Este trabalho descreve uma técnica para gerar malhas de superfícies paramétricas utilizando computação paralela, com processadores de memória compartilhada. A entrada para o algoritmo é um conjunto de patches paramétricos que modela a superfície de um determinado objeto. Uma estrutura de partição espacial é proposta para decompor o domínio em tantos subdomínios quantos forem os processos no sistema paralelo. Cada subdomínio é formado por um conjunto de patches e a divisão de sua carga é guiada seguindo uma estimativa de carga. Esta decomposição tenta equilibrar a quantidade de trabalho em todos os subdomínios. A quantidade de trabalho, conhecida como carga, de qualquer gerador de malha é geralmente dada em função do tamanho da saída do algoritmo, ou seja, do tamanho da malha gerada. Assim, faz-se necessária uma técnica para estimar previamente o tamanho dessa malha, que é a carga total do domínio. Este trabalho utiliza-se de um cálculo de curvatura analítica média para cada patch, que por sua vez, é dado de entrada para estimar esta carga e a decomposição é feita a partir dessa curvatura analítica média. Uma vez decomposto o domínio, cada processo gera a malha em seu subdomínio ou conjunto de patches pela técnica de quadtree para regiões internas, avanço de fronteira para regiões de fronteira e por fim é aplicado um melhoramento na malha gerada. Esta técnica apresentou bons resultados de speed-up, mantendo a qualidade da malha comparável à qualidade da malha gerada de forma sequencial.

De nombreux modèles numériques ont été proposés pour mieux comprendre comment le courant électrique est répartit lors d’une stimulation électrique par implant cochléaire. Ceci permet à terme d’optimiser la géométrie des électrodes et les stratégies de stimulation. Les modèles précédemment proposés modélisent les modèles d'interface électrochimique de façon très basique, et ne prennent généralement compte que de l'intensité du courant sur les électrodes. Par conséquent, il leur est difficile de simuler la dynamique temporelle de la stimulation ou de modéliser la répartition du courant en fonction de différents modes de stimulation contrôlés en tension, tels que le mode de de retour commun (Common Ground), ou de retour multiple (Multi-Mode Grounding). Dans cette thèse, nous avons développé un nouveau modèle surfacique de la cochlée. Le modèle géométrique dépend d'un ensemble de paramètres permettant d'ajuster la forme de la cochlée, en utilisant par exemple des données histologiques, des scans CT, ou encore des maillages de surface. Un modèle paramétrique nous a permis de comparer les courants générés par les modèles d'électrodes actuellement disponibles et par un nouveau type d'électrode - faisceau transmodiolaire. Le modèle peut prendre en compte des courants ou des tensions en entrée à chaque électrode, ce qui permet de simuler le mode de retour commun ou multiple. Afin de valider les résultats de simulation et calibrer les paramètres du modèle, nous avons créé un système permettant d'acquérir des mesures in-situ et in-vitro. Les données enregistrées ont permis de valider le modèle combinant le modèle d'interface électrochimique et le modèle tridimensionnel de cochlée. / Computational models have been widely used to improve the knowledge of the current distribution behavior in cochlear implant stimulations, optimizing electrode designs and stimulation strategies. The existing models employed no or simple electrochemical interface models and took current intensity on the electrodes as input. Therefore they have difficulties in making time domain simulations and simulating the stimulation modes that have voltage constraints, such as the Common Ground and the Multi-Mode Grounding modes. In this PhD work, a new parametric surface mesh model of the cochlea has been developed. The shape of the model is controlled by a set of input parameters which can be tuned to fit the cochlear shape acquired from histological images, CT scans or existing cochlear mesh models. The symmetric boundary element method, which was implemented in OpenMEEG, has been applied on the model to simulate the current distribution of the cochlear implant stimulation. Using the parametric model, comparisons on the current field has been made between the existing electrode layouts and a new transmodiolar electrodes. The new model can take either current or voltage as input for each electrode to simulate the common ground and multi-mode grounding modes. By coupling the surface model with lumped capacitor and constant phase element models, time domain simulation of the stimulation waveform has also been achieved. To validate the simulation results and calibrate the parameters of the model, in-situ and in-vitro measurements have been carried out with self-made devices. The recorded data proved the effectiveness of combining lumped components with the surface model.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / This work describes a technique for generating parametric surfaces meshes using parallel computing, with distributed memory processors. The input for the algorithm is a set of parametric patches that model the surface of a given object. A structure for spatial partitioning is proposed to decompose the domain in as many subdomains as processes in the parallel system. Each subdomain consists of a set of patches and the division of its load is guided following an estimate. This decomposition attempts to balance the amount of work in all the subdomains. The amount of work, known as load, of any mesh generator is usually given as a function of its output size, i.e., the size of the generated mesh. Therefore, a technique to estimate the size of this mesh, the total load of the domain, is needed beforehand. This work makes use of an analytical average curvature calculated for each patch, which in turn is input data to estimate this load and the decomposition is made from this analytical mean curvature. Once the domain is decomposed, each process generates the mesh on that subdomain or set of patches by a quad tree technique for inner regions, advancing front technique for border regions and is finally applied an improvement to mesh generated. This technique presented good speed-up results, keeping the quality of the mesh comparable to the quality of the serially generated mesh. / Este trabalho descreve uma tÃcnica para gerar malhas de superfÃcies paramÃtricas utilizando computaÃÃo paralela, com processadores de memÃria compartilhada. A entrada para o algoritmo à um conjunto de patches paramÃtricos que modela a superfÃcie de um determinado objeto. Uma estrutura de partiÃÃo espacial à proposta para decompor o domÃnio em tantos subdomÃnios quantos forem os processos no sistema paralelo. Cada subdomÃnio à formado por um conjunto de patches e a divisÃo de sua carga à guiada seguindo uma estimativa de carga. Esta decomposiÃÃo tenta equilibrar a quantidade de trabalho em todos os subdomÃnios. A quantidade de trabalho, conhecida como carga, de qualquer gerador de malha à geralmente dada em funÃÃo do tamanho da saÃda do algoritmo, ou seja, do tamanho da malha gerada. Assim, faz-se necessÃria uma tÃcnica para estimar previamente o tamanho dessa malha, que à a carga total do domÃnio. Este trabalho utiliza-se de um cÃlculo de curvatura analÃtica mÃdia para cada patch, que por sua vez, à dado de entrada para estimar esta carga e a decomposiÃÃo à feita a partir dessa curvatura analÃtica mÃdia. Uma vez decomposto o domÃnio, cada processo gera a malha em seu subdomÃnio ou conjunto de patches pela tÃcnica de quadtree para regiÃes internas, avanÃo de fronteira para regiÃes de fronteira e por fim à aplicado um melhoramento na malha gerada. Esta tÃcnica apresentou bons resultados de speed-up, mantendo a qualidade da malha comparÃvel à qualidade da malha gerada de forma sequencial.

Ce travail de thèse concerne l'analyse structurelle des maillages triangulaires surfaciques, ainsi que leur traitement en vue de l'amélioration de leur qualité (remaillage) ou de leur simplification. Dans la littérature, le repositionnement des sommets d'un maillage est soit traité de manière locale, soit de manière globale mais sans un contrôle local de l'erreur géométrique introduite, i.e. les solutions actuelles ne sont pas globales ou introduisent de l'erreur géométrique non-contrôlée. Les techniques d'approximation de maillage les plus prometteuses se basent sur une décomposition en primitives géométriques simples (plans, cylindres, sphères etc.), mais elles n'arrivent généralement pas à trouver la décomposition optimale, celle qui optimise à la fois l'erreur géométrique de l'approximation par les primitives choisies, et le nombre et le type de ces primitives simples. Pour traiter les défauts des approches de remaillage existantes, nous proposons une méthode basée sur un modèle global, à savoir une modélisation graphique probabiliste, intégrant des contraintes souples basées sur la géométrie (l'erreur de l'approximation), la qualité du maillage et le nombre de sommets du maillage. De même, pour améliorer la décomposition en primitives simples, une modélisation graphique probabiliste a été choisie. Les modèles graphiques de cette thèse sont des champs aléatoires de Markov, ces derniers permettant de trouver une configuration optimale à l'aide de la minimisation globale d'une fonction objectif. Nous avons proposé trois contributions dans cette thèse autour des maillages triangulaires 2-variétés : (i) une méthode d'extraction statistiquement robuste des arêtes caractéristiques applicable aux objets mécaniques, (ii) un algorithme de segmentation en régions approximables par des primitives géométriques simples qui est robuste à la présence de données aberrantes et au bruit dans la position des sommets, (iii) et finalement un algorithme d'optimisation de maillages qui cherche le meilleur compromis entre l'amélioration de la qualité des triangles, la qualité de la valence des sommets, le nombre de sommets et la fidélité géométrique à la surface initiale. / The work in this thesis concerns structural analysis of 2-manifold triangular meshes, and their processing towards quality enhancement (remeshing) or simplification. In existing work, the repositioning of mesh vertices necessary for remeshing is either done locally or globally, but in the latter case without local control on the introduced geometrical error. Therefore, current results are either not globally optimal or introduce unwanted geometrical error. Other promising remeshing and approximation techniques are based on a decomposition into simple geometrical primitives (planes, cylinders, spheres etc.), but they generally fail to find the best decomposition, i.e. the one which jointly optimizes the residual geometrical error as well as the number and type of selected simple primitives. To tackle the weaknesses of existing remeshing approaches, we propose a method based on a global model, namely a probabilistic graphical model integrating soft constraints based on geometry (approximation error), mesh quality and the number of mesh vertices. In the same manner, for segmentation purposes and in order to improve algorithms delivering decompositions into simple primitives, a probabilistic graphical modeling has been chosen. The graphical models used in this work are Markov Random Fields, which allow to find an optimal configuration by a global minimization of an objective function. We have proposed three contributions in this thesis about 2-manifold triangular meshes : (i) a statistically robust method for feature edge extraction for mechanical objects, (ii) an algorithm for the segmentation into regions which are approximated by simple primitives, which is robust to outliers and to the presence of noise in the vertex positions, (iii) and lastly an algorithm for mesh optimization which jointly optimizes triangle quality, the quality of vertex valences, the number of vertices, as well as the geometrical fidelity to the initial surface.

L’utilisation des modèles 3D, représentés sous forme de maillage, est sans cesse croissante dans de nombreuses applications. Pour une transmission efficace et pour une adaptation à l’hétérogénéité des ressources de ces modèles, des techniques de compression progressive sont généralement utilisées. Afin de protéger le droit d’auteur de ces modèles pendant la transmission, des techniques de tatouage sont également employées. Dans ces travaux de thèse, nous proposons premièrement deux méthodes de compression progressive pour des maillages avec ou sans information de couleurs et nous présentons finalement un système conjoint de compression progressive et de tatouage. Dans une première partie, nous proposons une méthode d’optimisation du compromis débit-distorsion pour des maillages sans attribut de couleur. Pendant le processus de l’encodage, nous adoptons la précision de quantification au nombre d’éléments et à la complexité géométrique pour chaque niveau de détail. Cette adaptation peut s’effectuer de manière optimale en mesurant la distance par rapport au maillage original, ou de façon quasi-optimale en utilisant un modèle théorique pour une optimisation rapide. Les résultats montrent que notre méthode donne des résultats compétitifs par rapport aux méthodes de l’état de l’art. Dans une deuxième partie, nous nous focalisons sur l’optimisation du compromis débit-distorsion pour des maillages possédant l’information de couleur attachée aux sommets. Après avoir proposé deux méthodes de compression pour ce type de maillage, nous présentons une méthode d’optimisation du débit-distorsion qui repose sur l’adaptation de la précision de quantification de la géométrie et de la couleur pour chaque maillage intermédiaire. Cette adaptation peut être effectuée rapidement selon un modèle théorique qui permet d’évaluer le nombre de bits de quantification nécessaire pour chaque maillage intermédiaire. Une métrique est également proposée pour préserver les éléments caractéristiques durant la phase de simplification. Finalement, nous proposons un schéma conjoint de compression progressive et de tatouage. Afin de protéger tous les niveaux de détails, nous insérons le tatouage dans chaque étape du processus d’encodage. Pour cela, à chaque itération de la simplification, nous séparons les sommets du maillage en deux ensembles et nous calculons un histogramme de distribution de normes pour chacun d’entre eux. Ensuite, nous divisons ces histogrammes en plusieurs classes et nous modifions ces histogrammes en décalant les classes pour insérer un bit. Cette technique de tatouage est réversible et permet de restaurer de manière exacte le maillage original en éliminant la déformation induite par l’insertion du tatouage. Nous proposons également une nouvelle méthode de prédiction de la géométrie afin de réduire le surcoût provoqué par l’insertion du tatouage. Les résultats expérimentaux montrent que notre méthode est robuste à diverses attaques géométriques tout en maintenant un bon taux de compression / The use of 3D models, represented as a mesh, is growing in many applications. For efficient transmission and adaptation of these models to the heterogeneity of client devices, progressive compression techniques are generally used. To protect the copyright during the transmission, watermarking techniques are also used. In this thesis, we first propose two progressive compression methods for meshes with or without color information, and we present a joint system of compression and watermarking. In the first part, we propose a method for optimizing the rate-distortion trade-off for meshes without color attribute. During the encoding process, we adopt the quantization precision to the number of elements and geometric complexity. This adaptation can be performed optimally by measuring the distance regarding the original mesh, or can be carried out using a theoretical model for fast optimization. The results show that our method yields competitive results with the state-of-the-art methods. In the second part, we focus on optimizing the rate-distortion performance for meshes with color information attached to mesh vertices. We propose firstly two methods of compression for this type of mesh and then we present a method for optimizing the rate-distortion trade-off based on the adaptation of the quantification precision of both geometry and color for each intermediate mesh. This adaptation can be performed rapidly by a theoretical model that evaluates the required number of quantization bits for each intermediate mesh. A metric is also proposed in order to preserve the feature elements throughout simplification. Finally, we propose a joint scheme of progressive compression and watermarking. To protect all levels of detail, we insert the watermark within each step of the encoding process. More precisely, at each iteration of simplification, we separate vertices into two sets and compute a histogram of distribution of vertex norms for each set. Then, we divide these histograms into several bins and we modify these histograms by shifting bins to insert a bit. This watermarking technique is reversible and can restore exactly the original mesh by eliminating the distortion caused by the insertion of the watermark. We also propose a new prediction method for geometry encoding to reduce the overhead caused by the insertion of the watermark. Experimental results show that our method is robust to various geometric attacks while maintaining a good compression ratio

One of the common research goals in disciplines such as computer graphics and robotics is to understand the subtleties of human motion and develop tools for recreating natural and meaningful motion. Physical simulation of virtual human characters is a promising approach since it provides a testbed for developing and testing control strategies required to execute various human behaviors. Designing generic control algorithms for simulating a wide range of human activities, which can robustly adapt to varying physical environments, has remained a primary challenge. This dissertation introduces methods for generic and robust control of virtual characters in an interactive physical environment. Our approach is to use the information of the physical contacts between the character and her environment in the control design. We leverage high-level knowledge of the kinematics goals and the interaction with the surroundings to develop active control strategies that robustly adapt to variations in the physical scene. For synthesizing intentional motion requiring long-term planning, we exploit properties of the physical model for creating efficient and robust controllers in an interactive framework. The control design leverages the reference motion capture data and the contact information with the environment for interactive long-term planning. Finally, we propose a compact soft contact model for handling contacts for rigid body virtual characters. This model aims at improving the robustness of existing control methods without adding any complexity to the control design and opens up possibilities for new control algorithms to synthesize agile human motion.