Este trabalho apresenta uma solução geral para a detecção de alinhamentos de dados em conjuntos multidimensionais não ordenados e ruidosos. Nesta abordagem, o tipo requerido de alinhamento de dados pode ser uma forma geométrica (e.g., linha reta, plano, círculo, esfera, seção cônica, entre outras) ou qualquer estrutura, com dimensionalidade arbitrária, que possa ser caracterizada por um subespaço linear. A detecção é realizada por meio de um procedimento composto por três etapas. Na etapa de inicialização, um espaço de parâmetros com p (n − p) dimensões é definido de modo que cada ponto neste espaço represente uma instância do alinhamento requerido, descrito por um subespaço p-dimensional em um domínio n-dimensional. Em seguida, uma grade de acumuladores é criada como sendo a representação discreta do espaço de parâmetros. Na segunda etapa do procedimento, cada elemento no conjunto de dados de entrada (também um subespaço no domínio n-dimensional) é mapeado para o espaço de parâmetros como os pontos (no espaço de parâmetros) representando os subespaços requeridos que contém ou que estão contidos no elemento de entrada. À medida que os elementos de entrada são mapeados, as células do acumulador relacionadas com o mapeamento são incrementadas pelo valor de importância do elemento mapeado. A etapa final do procedimento recupera os subespaços p-dimensionais que melhor se ajustam aos dados de entrada como sendo os máximos locais na grade de acumuladores. A parametrização proposta é independente das propriedades geométricas dos alinhamentos a serem detectados. Além disso, o procedimento de mapeamento é independente do tipo de dado de entrada e é capaz de se adaptar a elementos com dimensionalidades arbitrárias. Essas características permitem a utilização da técnica (sem a necessidade de modificações) como uma ferramenta para a detecção de padrões em uma grande quantidade de aplicações. Por conta de sua natureza geral, otimizações desenvolvidas para a abordagem proposta beneficiam, de forma imediata, todos os casos de detecção. Neste trabalho eu demonstro uma implementação em software da técnica proposta e mostro que ela pode ser aplicada tanto em casos simples de detecção, quanto na detecção concorrente de tipos diferentes de alinhamentos, com diferentes interpretações geométricas e em conjuntos de dados compostos por vários tipos de elementos. Esta dissertação também apresenta uma extensão do esquema de detecção para dados de entrada com distribuição Gaussiana de incerteza. A extensão proposta produz distribuições de valores mais suaves na grade de acumuladores e faz com que a técnica fique mais robusta à detecção de subespaços espúrios. / This dissertation presents a generalized closed-form framework for detecting data alignments in large unordered noisy multidimensional datasets. In this approach, the intended type of data alignment may be a geometric shape (e.g., straight line, plane, circle, sphere, conic section, among others) or any other structure, with arbitrary dimensionality that can be characterized by a linear subspace. The detection is performed using a three-step process. In the initialization, a p (n − p)-dimensional parameter space is defined in such a way that each point in this space represents an instance of the intended alignment described by a p-dimensional subspace in some n-dimensional domain. In turn, an accumulator array is created as the discrete representation of the parameter space. In the second step each input entry (also a subspace in the n-dimensional domain) is mapped to the parameter space as the set of points representing the intended p-dimensional subspaces that contain or are contained by the entry. As the input entries are mapped, the bins of the accumulator related to such a mapping are incremented by the importance value of the entry. The subsequent and final step retrieves the p-dimensional subspaces that best fit input data as the local maxima in the accumulator array. The proposed parameterization is independent of the geometric properties of the alignments to be detected. Also, the mapping procedure is independent of the type of input data and automatically adapts to entries of arbitrary dimensionality. This allows application of the proposed approach (without changes) in a broad range of applications as a pattern detection tool. Given its general nature, optimizations developed for the proposed framework immediately benefit all the detection cases. I demonstrate a software implementation of the proposed technique and show that it can be applied in simple detection cases as well as in concurrent detection of multiple kinds of alignments with different geometric interpretations, in datasets containing multiple types of data. This dissertation also presents an extension of the general detection scheme to data with Gaussian-distributed uncertainty. The proposed extension produces smoother distributions of values in the accumulator array and makes the framework more robust to the detection of spurious subspaces.

Este trabalho apresenta uma solução geral para a detecção de alinhamentos de dados em conjuntos multidimensionais não ordenados e ruidosos. Nesta abordagem, o tipo requerido de alinhamento de dados pode ser uma forma geométrica (e.g., linha reta, plano, círculo, esfera, seção cônica, entre outras) ou qualquer estrutura, com dimensionalidade arbitrária, que possa ser caracterizada por um subespaço linear. A detecção é realizada por meio de um procedimento composto por três etapas. Na etapa de inicialização, um espaço de parâmetros com p (n − p) dimensões é definido de modo que cada ponto neste espaço represente uma instância do alinhamento requerido, descrito por um subespaço p-dimensional em um domínio n-dimensional. Em seguida, uma grade de acumuladores é criada como sendo a representação discreta do espaço de parâmetros. Na segunda etapa do procedimento, cada elemento no conjunto de dados de entrada (também um subespaço no domínio n-dimensional) é mapeado para o espaço de parâmetros como os pontos (no espaço de parâmetros) representando os subespaços requeridos que contém ou que estão contidos no elemento de entrada. À medida que os elementos de entrada são mapeados, as células do acumulador relacionadas com o mapeamento são incrementadas pelo valor de importância do elemento mapeado. A etapa final do procedimento recupera os subespaços p-dimensionais que melhor se ajustam aos dados de entrada como sendo os máximos locais na grade de acumuladores. A parametrização proposta é independente das propriedades geométricas dos alinhamentos a serem detectados. Além disso, o procedimento de mapeamento é independente do tipo de dado de entrada e é capaz de se adaptar a elementos com dimensionalidades arbitrárias. Essas características permitem a utilização da técnica (sem a necessidade de modificações) como uma ferramenta para a detecção de padrões em uma grande quantidade de aplicações. Por conta de sua natureza geral, otimizações desenvolvidas para a abordagem proposta beneficiam, de forma imediata, todos os casos de detecção. Neste trabalho eu demonstro uma implementação em software da técnica proposta e mostro que ela pode ser aplicada tanto em casos simples de detecção, quanto na detecção concorrente de tipos diferentes de alinhamentos, com diferentes interpretações geométricas e em conjuntos de dados compostos por vários tipos de elementos. Esta dissertação também apresenta uma extensão do esquema de detecção para dados de entrada com distribuição Gaussiana de incerteza. A extensão proposta produz distribuições de valores mais suaves na grade de acumuladores e faz com que a técnica fique mais robusta à detecção de subespaços espúrios. / This dissertation presents a generalized closed-form framework for detecting data alignments in large unordered noisy multidimensional datasets. In this approach, the intended type of data alignment may be a geometric shape (e.g., straight line, plane, circle, sphere, conic section, among others) or any other structure, with arbitrary dimensionality that can be characterized by a linear subspace. The detection is performed using a three-step process. In the initialization, a p (n − p)-dimensional parameter space is defined in such a way that each point in this space represents an instance of the intended alignment described by a p-dimensional subspace in some n-dimensional domain. In turn, an accumulator array is created as the discrete representation of the parameter space. In the second step each input entry (also a subspace in the n-dimensional domain) is mapped to the parameter space as the set of points representing the intended p-dimensional subspaces that contain or are contained by the entry. As the input entries are mapped, the bins of the accumulator related to such a mapping are incremented by the importance value of the entry. The subsequent and final step retrieves the p-dimensional subspaces that best fit input data as the local maxima in the accumulator array. The proposed parameterization is independent of the geometric properties of the alignments to be detected. Also, the mapping procedure is independent of the type of input data and automatically adapts to entries of arbitrary dimensionality. This allows application of the proposed approach (without changes) in a broad range of applications as a pattern detection tool. Given its general nature, optimizations developed for the proposed framework immediately benefit all the detection cases. I demonstrate a software implementation of the proposed technique and show that it can be applied in simple detection cases as well as in concurrent detection of multiple kinds of alignments with different geometric interpretations, in datasets containing multiple types of data. This dissertation also presents an extension of the general detection scheme to data with Gaussian-distributed uncertainty. The proposed extension produces smoother distributions of values in the accumulator array and makes the framework more robust to the detection of spurious subspaces.

Le coeur de cette thèse porte sur la modélisation géométrique et introduit une méthode robuste d'extraction de formes tubulaires à partir de nuages de points. Nous avons choisi de tester nos méthodes dans le contexte applicatif de la foresterie pour mettre en valeur la robustesse de nos algorithmes.Nos méthodes intègrent les normales aux points, il est donc nécessaire de les pré-calculer. Notre premier développement a alors consisté à présenter une méthode rapide d'estimation de normales. Pour ce faire nous avons approximé localement la géométrie du nuage de points en utilisant des "patchs" lisses dont la taille s'adapte à la complexité locale des nuages de points.Nos travaux se sont ensuite concentrés sur l’extraction robuste de formes tubulaires dans des nuages de points occlus, bruités et de densité inhomogène. Nous avons développé une variante de la transformée de Hough que nous avons couplé à une proposition de contours actifs indépendants de leur paramétrisation. Notre méthode a été validée en environnement forestier pour reconstruire des troncs d'arbre afin d'en relever les qualités par comparaison à des méthodes existantes.La reconstruction de troncs d'arbre ouvre d'autres questions dont la segmentation des arbres d'une placette forestière. Nous proposons également une méthode de segmentation pour isoler les différents objets d'un jeu de données.Durant nos travaux nous avons utilisé des approches de modélisation pour répondre à des questions géométriques, et nous les avons appliqué à des problématiques forestières. Il en résulte un pipeline de traitements cohérent qui, bien qu'illustré sur des données forestières, est applicable dans des contextes variés. / The core of this thesis concerns geometric modelling and introduces a fast and robust method for the extraction of tubular shapes from point clouds. We chose to test our method in the difficult applicative context of forestry in order to highlight the robustness of our algorithms.Our methods integrate normal vectors, thus they have to be pre-computed. Our first development consisted in the development of a fast normal estimation method on point cloud. To do so, we locally approximated the point cloud geometry using smooth "patches" of points which size adapts to the local complexity of the point cloud geometry.We then focused our work on the robust extraction of tubular shapes from dense, occluded, noisy point clouds suffering from non-homogeneous sampling density. We developed a variant of the Hough transform and combined this research with a new definition of parametrisation-invariant active contours. We validated our method in complex forest environments with the reconstruction of tree stems to emphasize its advantages and compare it to existing methods.Tree stem reconstruction also opens new perspectives halfway in between forestry and geometry such as the segmentation of trees from a forest plot. Therefore we propose a segmentation approach capable of isolating objects inside a point cloud.During our work we used modelling approaches to answer geometric questions and we applied our methods to forestry problems. Therefore, our studies result in a processing pipeline adapted to forest point cloud analyses, but the general geometric algorithms we propose can also be applied in various contexts.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-10T13:03:01Z No. of bitstreams: 1 DissIJRF.pdf: 11147756 bytes, checksum: c2f35d4805dd8c9a93b43189bacf2899 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:38:57Z (GMT) No. of bitstreams: 1 DissIJRF.pdf: 11147756 bytes, checksum: c2f35d4805dd8c9a93b43189bacf2899 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:39:03Z (GMT) No. of bitstreams: 1 DissIJRF.pdf: 11147756 bytes, checksum: c2f35d4805dd8c9a93b43189bacf2899 (MD5) / Made available in DSpace on 2016-10-20T19:39:09Z (GMT). No. of bitstreams: 1 DissIJRF.pdf: 11147756 bytes, checksum: c2f35d4805dd8c9a93b43189bacf2899 (MD5) Previous issue date: 2016-05-20 / Não recebi financiamento / The computational analysis of human mobility can aid in treatment and rehabilitation of people who have some kind of physical disability. Physiotherapeutic studies, called kinematics, aims to correct body’s dysfunction, caused by genetic malformations, degenerative diseases or posture problems. A computer system can be used to precisely describe motion, anatomical position and angular terms during gait. Therefore, the movements need to be captured and represented in three-dimensional space to be evaluated. This work is a study, development and evaluation of a system for capturing human movement based on recorded videos, using low cost computing resources and adapted to the reality of gait analysis. The automation of computing movements capture, as well as aid in neurological, motor or orthopedic rehabilitation will expand its application to community. In this context, a study was conducted about computing methods of human movements capture by passive markers, and defined the four main steps: calibration and synchronization of the cameras, detection and three-dimensional reconstruction. Computer experiments were made to facilitate the theoretical understanding of this work. Kinematic analyzes data were used as a study case for the implementati / A análise computacional de movimentos humanos pode auxiliar no tratamento e reabilitação de pessoas que possuem algum tipo de deficiência motora. Estudos na fisioterapia, chamado de avaliação cinemática, tem por objetivo direcionar tratamentos para corrigir as disfunções do corpo, causadas pela má formação genética, doenças degenerativas ou problemas de postura. Um sistema computacional pode ser utilizado para descrever precisamente os movimentos, posição anatômica e termos angulares durante o período da marcha. Para tanto, os movimentos precisam ser capturados e reconstruídos no espaço tridimensional para posteriormente serem avaliados. Este trabalho consiste no estudo, desenvolvimento e avaliação de um sistema para captura de movimentos humanos baseado em registros de vídeos, utilizando recursos computacionais de baixo custo e adaptado a realidade da análise de marcha. A automatização da captura computacional destes movimentos, além de auxiliar na reabilitação motora neurológica e ou ortopédica de pessoas que possuem alguma deficiência do gênero, ampliará sua aplicação na comunidade. Nesse contexto, foi realizado o levantamento bibliográfico das principais técnicas de captura computacional de movimentos, e no caso dos sistemas ópticos com marcadores passivos, e definido quatro etapas principais: calibração, sincronização das câmeras, detecção e reconstrução tridimensional. Ainda, experimentos computacionais foram realizados para o entendimento prático e teórico do trabalho. Registros de marcha de crianças foram utilizados como estudo de caso para a implementação das etapas de calibração, detecção dos marcadores e reconstrução tridimensional.

Este trabalho discute a determinação de padrões respiratórios em sequências temporais de imagens obtidas por Ressonância Magnética (RM) e o seu uso no registro temporal de imagens coronais e sagitais. O registro é feito sem o uso de qualquer informação de sincronismo e qualquer gás especial para reforçar o contraste. As sequências temporais de imagens são adquiridas em respiração livre. O movimento real do pulmão nunca foi diretamente visto, pois é totalmente dependente dos músculos que o rodeiam. A visualização do pulmão em movimento é um tema atual de pesquisa na medicina. O movimento do pulmão não possui intervalos regulares e é suscetível a variações na respiração. Comparado à Tomografia Computadorizada (TC), a RM necessita de um maior tempo de aquisição e é preferível porque não envolve radiação. Como as sequências de imagens coronais e sagitais são ortogonais entre si, a sua intersecção corresponde a um segmento de reta no espaço tridimensional. O registro se baseia na análise deste segmento interseccional. A variação deste segmento de interseção no tempo pode ser enfileirada, definindo uma imagem espaço-temporal em duas dimensões (2DST). Supõe-se que o movimento diafragmático é o movimento principal de todas as estruturas do pulmão se movem quase que totalmente sincronicamente. A sincronização deste movimento é feita através de um padrão chamado função respiração. Este padrão é obtido através do processamento de uma imagem 2DST. Um algoritmo da transformada de Hough intervalar procura movimentos sincronizados na função respiração. O algoritmo de contornos ativos ajusta pequenas discrepâncias originadas por movimentos assíncronos nos padrões respiratórios . A saída é um conjunto de padrões respiratórios. Finalmente, a composição de imagens coronal e sagital que estão na mesma fase respiratória é realizada através da comparação de padrões respiratórios provenientes das superfícies de contorno superior e diafragmática. Quando disponíveis, os padrões respiratórios associados às estruturas internas do pulmão também são usados. Vários resultados e conclusões são apresentados. / This work addresses the determination of the breathing patterns in time sequence of images obtained from Magnetic Resonance (MR) and their use in the temporal registration of coronal and sagital images. The registration is done without the use of any triggering information and any special gas to enhance the contrast. The temporal sequences of images are acquired in free breathing. The real movement of the lung has never been seen directly, as it is totally dependent on its surrounding muscles and collapses without them. The visualization of the lung in motion is an actual topic of research in medicine. The lung movement is not periodic and it is susceptible to variations in the degree of respiration. Compared to Computerized Tomography (CT), MR imaging involves longer acquisition times and it is preferable because it does not involve radiation. As coronal and sagittal sequences of images are orthogonal to each other, their intersection corresponds to a segment in the three dimensional space. The registration is based on the analysis of this intersection segment. A time sequence of this intersection segment can be stacked, defining a two-dimension spatio-temporal (2DST) image. It is assumed that the diaphragmatic movement is the principal movement and all the lung structures move almost synchronously. The synchronization of this motion is performed through a pattern named respiratory function. This pattern is obtained by processing a 2DST image. An interval Hough transform algorithm searches for synchronized movements with the respiratory function. A greedy searches for synchronized movements with the respiratory function. A greedy active contour algorithm adjusts small discrepancies originated by asynchronous movements in the respiratory patterns. The output is a set of respiratory patterns. Finally, the composition of coronal and sagittal images that are in the same breathing phase is realized by comparing of respiratory patterns originated from diaphragmatic and upper boundary surfaces. When available, the respire tory patterns associated to lung internal structures are also used. Several results and conclusions are shown.

Este trabalho apresenta uma solução geral para a detecção de alinhamentos de dados em conjuntos multidimensionais não ordenados e ruidosos. Nesta abordagem, o tipo requerido de alinhamento de dados pode ser uma forma geométrica (e.g., linha reta, plano, círculo, esfera, seção cônica, entre outras) ou qualquer estrutura, com dimensionalidade arbitrária, que possa ser caracterizada por um subespaço linear. A detecção é realizada por meio de um procedimento composto por três etapas. Na etapa de inicialização, um espaço de parâmetros com p (n − p) dimensões é definido de modo que cada ponto neste espaço represente uma instância do alinhamento requerido, descrito por um subespaço p-dimensional em um domínio n-dimensional. Em seguida, uma grade de acumuladores é criada como sendo a representação discreta do espaço de parâmetros. Na segunda etapa do procedimento, cada elemento no conjunto de dados de entrada (também um subespaço no domínio n-dimensional) é mapeado para o espaço de parâmetros como os pontos (no espaço de parâmetros) representando os subespaços requeridos que contém ou que estão contidos no elemento de entrada. À medida que os elementos de entrada são mapeados, as células do acumulador relacionadas com o mapeamento são incrementadas pelo valor de importância do elemento mapeado. A etapa final do procedimento recupera os subespaços p-dimensionais que melhor se ajustam aos dados de entrada como sendo os máximos locais na grade de acumuladores. A parametrização proposta é independente das propriedades geométricas dos alinhamentos a serem detectados. Além disso, o procedimento de mapeamento é independente do tipo de dado de entrada e é capaz de se adaptar a elementos com dimensionalidades arbitrárias. Essas características permitem a utilização da técnica (sem a necessidade de modificações) como uma ferramenta para a detecção de padrões em uma grande quantidade de aplicações. Por conta de sua natureza geral, otimizações desenvolvidas para a abordagem proposta beneficiam, de forma imediata, todos os casos de detecção. Neste trabalho eu demonstro uma implementação em software da técnica proposta e mostro que ela pode ser aplicada tanto em casos simples de detecção, quanto na detecção concorrente de tipos diferentes de alinhamentos, com diferentes interpretações geométricas e em conjuntos de dados compostos por vários tipos de elementos. Esta dissertação também apresenta uma extensão do esquema de detecção para dados de entrada com distribuição Gaussiana de incerteza. A extensão proposta produz distribuições de valores mais suaves na grade de acumuladores e faz com que a técnica fique mais robusta à detecção de subespaços espúrios. / This dissertation presents a generalized closed-form framework for detecting data alignments in large unordered noisy multidimensional datasets. In this approach, the intended type of data alignment may be a geometric shape (e.g., straight line, plane, circle, sphere, conic section, among others) or any other structure, with arbitrary dimensionality that can be characterized by a linear subspace. The detection is performed using a three-step process. In the initialization, a p (n − p)-dimensional parameter space is defined in such a way that each point in this space represents an instance of the intended alignment described by a p-dimensional subspace in some n-dimensional domain. In turn, an accumulator array is created as the discrete representation of the parameter space. In the second step each input entry (also a subspace in the n-dimensional domain) is mapped to the parameter space as the set of points representing the intended p-dimensional subspaces that contain or are contained by the entry. As the input entries are mapped, the bins of the accumulator related to such a mapping are incremented by the importance value of the entry. The subsequent and final step retrieves the p-dimensional subspaces that best fit input data as the local maxima in the accumulator array. The proposed parameterization is independent of the geometric properties of the alignments to be detected. Also, the mapping procedure is independent of the type of input data and automatically adapts to entries of arbitrary dimensionality. This allows application of the proposed approach (without changes) in a broad range of applications as a pattern detection tool. Given its general nature, optimizations developed for the proposed framework immediately benefit all the detection cases. I demonstrate a software implementation of the proposed technique and show that it can be applied in simple detection cases as well as in concurrent detection of multiple kinds of alignments with different geometric interpretations, in datasets containing multiple types of data. This dissertation also presents an extension of the general detection scheme to data with Gaussian-distributed uncertainty. The proposed extension produces smoother distributions of values in the accumulator array and makes the framework more robust to the detection of spurious subspaces.

Doenças vasculares são um problema mundial, que representa 28% das mortes no mundo e 66% do total de doenças que acometem os brasileiros. Dessa forma, há um grande interesse em pesquisar formas de prevenção e tratamento dessas doenças. Algumas medidas são relevantes no auxílio de diagnóstico, tal como: tamanho médio dos ramos, diâmetro médio das seções transversais dos vasos e padrões de divisão de ramos. Calcular essas medidas de forma manual é uma tarefa demorada e trabalhosa. Assim, esta Tese tem como objetivo, propor um método computacional de rastreamento e extração de atributos em redes vasculares a partir de imagens 3D de angiografia por ressonância magnética e por tomografia computadorizada. Trata-se de uma abordagem de rastreamento e identificação de bifurcações que difere das técnicas anteriores, utilizando a Transformada de Hough para identificar o diâmetro do vaso em cortes transversais num dado ponto ao longo de um vaso sanguíneo. Mais detalhadamente, essa abordagem utiliza um campo vetorial advindo do cálculo de uma matriz formada por derivadas parciais de segunda ordem, obtida da intensidade luminosa da imagem, para identificar a direção de um ramo de vaso. Além disso, durante o processo de rastreamento de um ramo de vaso, são calculados vários descritores de forma com o objetivo de classificar regiões como pertencentes a uma bifurcação ou não. Em adição a estes descritores, desenvolvemos uma nova medida chamada de variância do raio que permite distinguir, bifurcações, não-bifurcações e segmentos de vaso com stents (aparelho metálico usado para aumentar o diâmetro dos vasos). Para a classificação de bifurcações, criamos a medida de bifurcação, que trata-se de uma combinação linear de todos os descritores de forma apresentados neste trabalho. Testes foram realizados para atestar a eficácia da abordagem proposta, utilizando tanto imagens sintéticas quantoimagens reais. Os resultados mostraram que o método é capaz de rastrear 91% de uma rede vascular sintética variando o ponto de inicialização e 76% variando o nível de ruído. Também foi observado por meio de testes que o método proposto consegue rastrear vasos e identificar bifurcações em imagens reais sem avaliação numérica. Essa abordagem permite a extração da relação hierárquica entre os ramos em uma rede vascular e a extração do padrão de divisão dos vasos, o que contribui sobremaneira para o estudo do comportamento do fenômeno da angiogênese e no auxílio no diagnóstico de anomalias vasculares. / Vascular diseases are a main health problem, representing 28% of deaths worldwide and 66% of all diseases affecting the Brazilian population. Thus, it is important that researches in prevention and treatment of this type of disease increase. Moreover, there are several demands, such as computational tools capable of analyzing and extracting attributes from non-invasive images. The scope of this work is the analysis and extraction of data from magnetic resonance angiography and computed tomography angiography images by highlighting blood vessels. In this context, this thesis aims the development of a novel computational tracking and feature extraction method for vascular networks from 3D images. Our approach presents the following steps: First, identify the vessel cross-sections along it using the Hough transform. Then, compute a matrix composed of second order partial derivatives of image intensity to identify the direction of the vessel. Perform a feature analysis of the vessel contour to classify the bifurcation point, and finally, identify the direction of the new branch in a bifurcation point. The main contribution of this Thesis is the two new measures developed, called radius ratio and bifurcation measure, the radius ratio is capable to distinguish between a region with bifurcation, stents or without both of them. The bifurcation measure is a linear combination that allows to classify a region as bifurcation or not. Tests were performed in order to verify the proposed approach effectiveness, using both synthetic images and real images. The results showed the method is capable to track 91% of synthetic vascular networks varying the seed point and 76% varying the level of noise. Also, we performed tests in real images and by visual evaluation, we could observed that the proposed method was able to track vessels and identify bifurcations from different parts of the body. This approach allows to calculate, in the future, the density of bifurcations in a vascular network, the distance between them, the stenosis and aneurysms grading and characterize specific vessels. In addition, the vascular networks extraction allows the study of the angiogenesis phenomena and vascular anomalies.

This thesis states that cracks and scars, referred to as Secondary Creases, in fingerprint images can be used as means for aiding and complementing fingerprint recognition, especially in cases where there is not enough clear data to use traditional methods such as minutiae based or correlation techniques. A Gabor filter bank is used to extract areas with linear patterns, where after the Hough Transform is used to identify secondary creases in a r, theta space. The methods proposed for Secondary Crease extraction works well, and provides information about what areas in an image contains usable linear pattern. Methods for comparison is however not as robust, and generates False Rejection Rate at 30% and False Acceptance Rate at 20% on the proposed dataset that consists of bad quality fingerprints. In short, our methods still makes it possible to make use of fingerprint images earlier considered unusable in fingerprint recognition systems.

Les capacités des technologies de télédétection ont augmenté exponentiellement au cours des dernières années : de nouveaux scanners fournissent maintenant une représentation géométrique de leur environnement sous la forme de nuage de points avec une précision jusqu'ici inégalée. Le traitement de nuages de points est donc devenu une discipline à part entière avec ses problématiques propres et de nombreux défis à relever. Le coeur de cette thèse porte sur la modélisation géométrique et introduit une méthode robuste d'extraction de formes tubulaires à partir de nuages de points. Nous avons choisi de tester nos méthodes dans le contexte applicatif difficile de la foresterie pour mettre en valeur la robustesse de nos algorithmes et leur application à des données volumineuses. Nos méthodes intègrent les normales aux points comme information supplémentaire pour atteindre les objectifs de performance nécessaire au traitement de nuages de points volumineux.Cependant, ces normales ne sont généralement pas fournies par les capteurs, il est donc nécessaire de les pré-calculer.Pour préserver la rapidité d'exécution, notre premier développement a donc consisté à présenter une méthode rapide d'estimation de normales. Pour ce faire nous avons approximé localement la géométrie du nuage de points en utilisant des "patchs" lisses dont la taille s'adapte à la complexité locale des nuages de points. Nos travaux se sont ensuite concentrés sur l’extraction robuste de formes tubulaires dans des nuages de points denses, occlus, bruités et de densité inhomogène. Dans cette optique, nous avons développé une variante de la transformée de Hough dont la complexité est réduite grâce aux normales calculées. Nous avons ensuite couplé ces travaux à une proposition de contours actifs indépendants de leur paramétrisation. Cette combinaison assure la cohérence interne des formes reconstruites et s’affranchit ainsi des problèmes liés à l'occlusion, au bruit et aux variations de densité. Notre méthode a été validée en environnement complexe forestier pour reconstruire des troncs d'arbre afin d'en relever les qualités par comparaison à des méthodes existantes. La reconstruction de troncs d'arbre ouvre d'autres questions à mi-chemin entre foresterie et géométrie. La segmentation des arbres d'une placette forestière est l'une d’entre elles. C'est pourquoi nous proposons également une méthode de segmentation conçue pour contourner les défauts des nuages de points forestiers et isoler les différents objets d'un jeu de données. Durant nos travaux nous avons utilisé des approches de modélisation pour répondre à des questions géométriques, et nous les avons appliqué à des problématiques forestières.Il en résulte un pipeline de traitements cohérent qui, bien qu'illustré sur des données forestières, est applicable dans des contextes variés. / Abstract : The potential of remote sensing technologies has recently increased exponentially: new sensors now provide a geometric representation of their environment in the form of point clouds with unrivalled accuracy. Point cloud processing hence became a full discipline, including specific problems and many challenges to face. The core of this thesis concerns geometric modelling and introduces a fast and robust method for the extraction of tubular shapes from point clouds. We hence chose to test our method in the difficult applicative context of forestry in order to highlight the robustness of our algorithms and their application to large data sets. Our methods integrate normal vectors as a supplementary geometric information in order to achieve the performance goal necessary for large point cloud processing. However, remote sensing techniques do not commonly provide normal vectors, thus they have to be computed. Our first development hence consisted in the development of a fast normal estimation method on point cloud in order to reduce the computing time on large point clouds. To do so, we locally approximated the point cloud geometry using smooth ''patches`` of points which size adapts to the local complexity of the point cloud geometry. We then focused our work on the robust extraction of tubular shapes from dense, occluded, noisy point clouds suffering from non-homogeneous sampling density. For this objective, we developed a variant of the Hough transform which complexity is reduced thanks to the computed normal vectors. We then combined this research with a new definition of parametrisation-invariant active contours. This combination ensures the internal coherence of the reconstructed shapes and alleviates issues related to occlusion, noise and variation of sampling density. We validated our method in complex forest environments with the reconstruction of tree stems to emphasize its advantages and compare it to existing methods. Tree stem reconstruction also opens new perspectives halfway in between forestry and geometry. One of them is the segmentation of trees from a forest plot. Therefore we also propose a segmentation approach designed to overcome the defects of forest point clouds and capable of isolating objects inside a point cloud. During our work we used modelling approaches to answer geometric questions and we applied our methods to forestry problems. Therefore, our studies result in a processing pipeline adapted to forest point cloud analyses, but the general geometric algorithms we propose can also be applied in various contexts.

The aim of this thesis is to design an algorithm for an automatic track counting of an image of etched track detector made of CR-39 polymer. Tracks are produced by alpha particles. Chemically etched detector is imaged using a microscope resulting in 64 images of segments on the surface of the detector. Circle shaped tracks in the images have to be detected and counted. This thesis evaluates the utilization of circle hough transform for circle detection. The final software should automate a detector track counting and should also account for defects in the image and contamination of detector surface. The software will produce a measurement report with a total track count in each segment.