A novel idea for perception of object surfaces is presented by so called "shape descriptors". Such idea is as an abstract level to represent the object surface by some real numbers. It has the similar idea like as the Fourier coefficients of mapping a function f(x) to frequency domain by Fourier transform. The main goal of this thesis is to define some of the key issues in understanding of an object shape and also to find a modeling methodology to create the "shape descriptors". The modeling methodology is designed based on a variational interpolation technique. Such technique is used to generate a group of variational implicit functions with help of radial basis functions. In our modeling methodology, we randomly choose some reference points on a set of related concentric spheres around a 3D point cloud data as known values in variational implicit functions. The "shape descriptors" are found from these implicit functions implementing LU decomposition. We show that the "shape descriptors" are invariant to size and positioning (rotation and translation) changes of a shape and they are also effective tools for matching of two similar objects surfaces.

A Recuperação de Imagens Baseada em Conteúdo (Content-Based Image Retrieval - CBIR) visa recuperar, em uma base de imagens, as ocorrências mais similares a uma imagem fornecida como modelo, a partir de características extraídas desses objetos. O uso dos conceitos de CBIR, embora bem explorado para recuperação de imagens bidimensionais, ainda é pouco explorado no domínio de objetos tridimensionais. A partir da identificação de lacunas na literatura a respeito da abordagem eficiente para recuperação destes objetos, o objetivo deste estudo foi definir, implementar e validar técnicas de recuperação destes objetos médicos tridimensionais com base no seu conteúdo considerando buscas globais e regionalizadas da estrutura tridimensional. Para atingir tal objetivo foram realizadas as seguintes atividades: revisão bibliográfica, definição da base de dados, implementação de descritores e métodos de comparação por similaridade, construção de um protótipo de sistema de recuperação, realização de testes com objetos médicos tridimensionais e análise dos resultados. Os resultados obtidos com os métodos desenvolvidos foram positivos, alcançando 90% de média de precisão no retorno da busca. Verificou-se que os descritores baseados em Harmônicos Esféricos podem ser adaptados para serem utilizados como descritores locais. Adicionalmente, verificou-se que a abordagem utilizando grafos bipartidos em conjunto com o cálculo de similaridade por meio de uma rede de fluxo, produziu resultados melhores do que os métodos que utilizaram abordagens clássicas de comparação. Em relação ao estudo de caso analisado, as Cardiomiopatias, foi possível constatar que as informações de idade e gênero contribuem para melhorar a precisão da recuperação, uma vez que essas informações podem influenciar diretamente a estrutura do ventrículo esquerdo. Além disso, em uma avaliação com usuários finais da área de Cardiologia, constatou-se que efetivamente esta abordagem pode auxiliar na composição de diagnósticos. Estes resultados confirmaram o potencial que a recuperação por conteúdo possui no contexto médico, além de contribuir com a área de Computação no sentido de ter desenvolvido técnicas para recuperação por conteúdo no domínio de objetos tridimensionais. / Content-Based Image Retrieval - CBIR aims to retrieval, in an image database, the most similar occurrences to an image provided as a query, from extracted characteristics of these objects. The use of CBIR concept, although exploited for recovery of twodimensional images, is still under explored in the three-dimensional objects knowledge field. Based on the identification of the current literature gaps regarding efficient approaches to retrieval these objects, the objective of this study was to define, implement and validate retrieval techniques of three-dimensional medical objects based on their content considering global and regionalized searches of the three-dimensional structure. In order to achieve this objective, the following activities were carried out: literature review, database definition, implementation of descriptors and methods of comparison by similarity, construction of a retrieval system prototype, tests with three-dimensional medical objects and results analysis. The results obtained with the methods developed were positive, reaching 90% of mean precision in the return of the search. It has been found that the descriptors based on Spherical Harmonics can be adapted to be used as local descriptors. Additionally, it was identified that the approach using bipartite graphs in conjunction with the similarity computation through network flow, produced better results than the methods that used classic approaches of comparison. Regarding the case study analyzed, the Cardiomyopathies, it was possible to verify that the information of age and gender contribute to improve the accuracy of the retrieval, since this information can directly influence the structure of the left ventricle. In addition, in an evaluation with end users of Cardiology area, it was verified that this approach can effectively aid in the diagnoses. These results confirmed the potential that content-based retrieval has in the medical context, as well as contribute to the Computing area in the sense of developing techniques for content-based in three-dimensional retrieval.

The study of particle morphology plays an important role in understanding the micromechanical behavior of cohesionless soil. Shear strength and liquefaction characteristics of granular soil depend on various morphological characteristics of soil grains such as their particle size, shape and surface texture. Therefore, accurate characterization and quantification of particle shape is necessary to study the effect of grain shape on mechanical behavior of granular assembly. However, the theoretical and practical developments of quantification of particle morphology and its influence on the mechanical response of granular assemblies has been very limited due to the lack of quantitative information about particle geometries, the experimental and numerical difficulties in characterizing and modeling irregular particle morphology. Motivated by the practical relevance of these challenges, this research presents a comprehensive approach to model irregular particle shape accurately both in two and three dimensions. To facilitate the research goal, a variety of natural and processed sand samples is collected from various locations around the world. A series of experimental and analytical studies are performed following the sample collection effort to characterize and quantify particle shapes of various sand samples by using Fourier shape descriptors. As part of the particle shape quantification and modeling, a methodology is developed to determine an optimum sample size for each sand sample used in the analysis. Recently, Discrete Element Method (DEM) has gained attention to model irregular particle morphology in two and three dimensions. In order to generate and reconstruct particle assemblies of highly irregular geometric shapes of a particular sand sample in the DEM environment, the relationship between grain size and shape is explored and no relationship is found between grain size and shape for the sand samples analyzed. A skeletonization algorithm is developed in this study in order to automate the Overlapping Discrete Element Cluster (ODEC) technique for modeling irregular particle shape in two and three dimensions. Finally, the two-dimensional and three-dimensional particle shapes are implemented within discrete element modeling software, PFC2D and PFC3D, to evaluate the influence of grain shape on shear strength behavior of granular soil by using discrete simulation of direct shear test.

In order to meet the needs of people with hearing loss today hearing aids are custom designed. Increasingly accurate 3-D scanning technology has contributed to the transition from conventional production scenarios to software based processes. Nonetheless, there is a tremendous amount of manual work involved to transform an input 3-D surface mesh of the outer ear into a final hearing aid shape. This manual work is often cumbersome and requires lots of experience which is why automatic solutions are of high practical relevance. This work is concerned with the recognition of 3-D surface meshes of ear implants. In particular we present a semantic part-labeling framework which significantly outperforms existing approaches for this task. We make at least three contributions which may also be found useful for other classes of 3-D meshes. Firstly, we validate the discriminative performance of several local descriptors and show that the majority of them performs poorly on our data except for 3-D shape contexts. The reason for this is that many local descriptor schemas are not rich enough to capture subtle variations in form of bends which is typical for organic shapes. Secondly, based on the observation that the left and the right outer ear of an individual look very similar we raised the question how similar the ear shapes among arbitrary individuals are? In this work, we define a notion of distance between ear shapes as building block of a non-parametric shape model of the ear to better handle the anatomical variability in ear implant labeling. Thirdly, we introduce a conditional random field model with a variety of label priors to facilitate the semantic part-labeling of 3-D meshes of ear implants. In particular we introduce the concept of a global parametric transition prior to enforce transition boundaries between adjacent object parts with an a priori known parametric form. In this way we were able to overcome the issue of inadequate geometric cues (e.g., ridges, bumps, concavities) as natural indicators for the presence of part boundaries. The last part of this work offers an outlook to possible extensions of our methods, in particular the development of 3-D descriptors that are fast to compute whilst at the same time rich enough to capture the characteristic differences between objects residing in the same class.

Cette thèse porte sur l’appariement des formes, et la recherche par forme clef. Elle décrit quatrecontributions à ce domaine. La première contribution est une amélioration de la méthode des nuéesdynamiques pour partitionner au mieux les voxels à l’intérieur d’une forme donnée ; les partitionsobtenues permettent d’apparier les objets par un couplage optimal dans un graphe biparti. Laseconde contribution est la fusion de deux descripteurs, l’un local, l’autre global, par la règle duproduit. La troisième contribution considère le graphe complet, dont les sommets sont les formes dela base ou la requête, et les arêtes sont étiquetées par plusieurs distances, une par descripteur ;ensuite cette méthode calcule par programmation linéaire la combinaison convexe des distancesqui maximise soit la somme des longueurs des plus courts chemins entre la requête et les objetsde la base de données, soit la longueur du plus court chemin entre la requête et l’objet comparé àla requête. La quatrième contribution consiste à perturber la requête avec un algorithme génétiquepour la rapprocher des formes de la base de données, pour un ou des descripteur(s) donné(s) ; cetteméthode est massivement parallèle, et une architecture multi-agent est proposée. Ces méthodes sontcomparées aux méthodes classiques, et ont de meilleures performances, en terme de précision. / This thesis concerns shape matching and shape retrieval. It describes four contributions to thisdomain. The first is an improvement of the k-means method, in order to find the best partition ofvoxels inside a given shape ; these best partitions permit to match shapes using an optimal matchingin a bipartite graph. The second contribution is the fusion of two descriptors, one local, the otherglobal, with the product rule. The third contribution considers the complete graph, the vertices ofwhich are the shapes in the database and the query. Edges are labelled with several distances,one per descriptor. Then the method computes, with linear programming, the convex combinationof distances which maximizes either the sum of the lengths of all shortest paths from the query toall shapes of the database, or the length of the shortest path in the graph from query to the currentshape compared to query. The fourth contribution consists in perturbing the shape query, to make itcloser to shapes in the database, for any given descriptors. This method is massively parallel and amulti-agent architecture is proposed. These methods are compared to classical methods in the field,they achieve better retrieval performances.

In order to meet the needs of people with hearing loss today hearing aids are custom designed. Increasingly accurate 3-D scanning technology has contributed to the transition from conventional production scenarios to software based processes. Nonetheless, there is a tremendous amount of manual work involved to transform an input 3-D surface mesh of the outer ear into a final hearing aid shape. This manual work is often cumbersome and requires lots of experience which is why automatic solutions are of high practical relevance. This work is concerned with the recognition of 3-D surface meshes of ear implants. In particular we present a semantic part-labeling framework which significantly outperforms existing approaches for this task. We make at least three contributions which may also be found useful for other classes of 3-D meshes. Firstly, we validate the discriminative performance of several local descriptors and show that the majority of them performs poorly on our data except for 3-D shape contexts. The reason for this is that many local descriptor schemas are not rich enough to capture subtle variations in form of bends which is typical for organic shapes. Secondly, based on the observation that the left and the right outer ear of an individual look very similar we raised the question how similar the ear shapes among arbitrary individuals are? In this work, we define a notion of distance between ear shapes as building block of a non-parametric shape model of the ear to better handle the anatomical variability in ear implant labeling. Thirdly, we introduce a conditional random field model with a variety of label priors to facilitate the semantic part-labeling of 3-D meshes of ear implants. In particular we introduce the concept of a global parametric transition prior to enforce transition boundaries between adjacent object parts with an a priori known parametric form. In this way we were able to overcome the issue of inadequate geometric cues (e.g., ridges, bumps, concavities) as natural indicators for the presence of part boundaries. The last part of this work offers an outlook to possible extensions of our methods, in particular the development of 3-D descriptors that are fast to compute whilst at the same time rich enough to capture the characteristic differences between objects residing in the same class.

Cette thèse présente une méthodologie appliquée à la caractérisation de la dynamique de structures déformables sur des séquences temporelles (2D+t). Des indicateurs sont proposés pour estimer la mobilité de formes non-rigides, à partir de leurs contours. Deux approches complémentaires sont développées: En premier lieu, les descripteurs de forme sont utilisés pour quantifier les déformations globales des formes, et pour estimer des repères géométriques spécifiques. La deuxième approche repose sur l'appariement difféomorphique pour déterminer une paramétrisation unifiée des formes, afin de décrire les déformations. Une évaluation permet d'apprécier la qualité des indicateurs en termes de coût algorithmique, de robustesse face aux données altérées, et de capacité à différencier deux séquences.Cette approche de caractérisation est appliquée à des séquences IRM dynamiques de la cavité pelvienne, où les principaux organes pelviens (vessie, utérus-vagin, rectum) ont une grande variabilité morphologique, ils se déplacent et se déforment. Cette caractérisation est validée dans le cadre de deux applications. L'analyse statistique effectuée sur un ensemble de séquences permet de mettre en évidence des comportements caractéristiques des organes, d'identifier des références anatomiquement significatives, et d'aider à l'interprétation des diagnostics des organes. Aussi, dans le contexte de la réalisation d'une modélisation de la dynamique pelvienne patiente-spécifique, la caractérisation vise à évaluer quantitativement la précision de la modélisation, en utilisant l'IRM dynamique comme vérité-terrain. Ainsi, elle apporte des indications sur la correction des paramètres du modèle. / This thesis presents a methodology for the characterization of the dynamics of deformable structures on time-series data (2D+t). Some indicators are proposed in order to estimate non-rigid shape variations from their contours. Two complementary approaches are developed : First, shape descriptors are used to quantify the global deformations of the shapes, and to estimate specific geometric references. The second approach relies on the diffeomorphic mapping to determinate a unified parametrization of the shapes. Then, features are used to describe the deformations locally. Furthermore, the methodology has an evaluation step which consists in the assessment of the quality of the indicators in the algorithmic complexity, in the stability against data with a small variability, and in the ability to differentiate two sequences.The characterization is applied to dynamic MRI sequences of the pelvic cavity, where the main pelvic organs (bladder, uterus-vagina, rectum) have a high morphological variability, they undergo displacements and deformations. The characterization is validated within the context of two applications. Firslty, a statistical analysis is carried out on a set of sequences. It allows to highlight some properties of the organ behaviors, and to identify meaningful anatomical landmarks. The analysis helps also for the automatic interpretation of the organ diagnoses. Secondly, within the context of the development of a patient-specific pelvic dynamics modeling system, the characterization aims at assessing quantitatively the modeling precision. It uses the dynamic MRI as a ground truth. Thereby, it brings some clues about the correction of the model parameters.

Proteins and the formation of large protein complexes are essential parts of living organisms. Proteins are present in all aspects of life processes, performing a multitude of various functions ranging from being structural components of cells, to facilitating the passage of certain molecules between various regions of cells. The 'protein docking problem' refers to the computational method of predicting the appropriate matching pair of a protein (receptor) with respect to another protein (ligand), when attempting to bind to one another to form a stable complex. Research shows that matching the three-dimensional (3D) geometric structures of candidate proteins plays a key role in determining a so-called docking pair, which is one of the key aspects of the Computer Aided Drug Design process. However, the active sites which are responsible for binding do not always present a rigid-body shape matching problem. Rather, they may undergo sufficient deformation when docking occurs, which complicates the problem of finding a match. To address this issue, we present an isometry-invariant and topologically robust partial shape matching method for finding complementary protein binding sites, which we call the ProtoDock algorithm. The ProtoDock algorithm comes in two variations. The first version performs a partial shape complementarity matching by initially segmenting the underlying protein object mesh into smaller portions using a spectral mesh segmentation approach. The Heat Kernel Signature (HKS), the underlying basis of our shape descriptor, is subsequently computed for the obtained segments. A final descriptor vector is constructed from the Heat Kernel Signatures and used as the basis for the segment matching. The three different descriptor methods employed are, the accepted Bag of Features (BoF) technique, and our two novel approaches, Closest Medoid Set (CMS) and Medoid Set Average (MSA). The second variation of our ProtoDock algorithm aims to perform the partial matching by utilizing the pointwise HKS descriptors. The use of the pointwise HKS is mainly motivated by the suggestion that, at adequate times, the Heat Kernel Signature of a point on a surface sufficiently describes its neighbourhood. Hence, the HKS of a point may serve as the representative descriptor of its given region of which it forms a part. We propose three (3) sampling methods---Uniform, Random, and Segment-based Random sampling---for selecting these points for the partial matching. Random and Segment-based Random sampling both prove superior to the Uniform sampling method. Our experimental results, run against the Protein-Protein Benchmark 4.0, demonstrate the viability of our approach, in that, it successfully returns known binding segments for known pairing proteins. Furthermore, our ProtoDock-1 algorithm still still yields good results for low resolution protein meshes. This results in even faster processing and matching times with sufficiently reduced computational requirements when obtaining the HKS.

Το αντικείμενο της μελέτης αυτής είναι η οργάνωση (ταξινόμηση, αναγνώριση, ανάκτηση κλπ.) βάσεων που περιλαμβάνουν εικόνες (φωτογραφίες) φύλλων δένδρων. Η οργάνωση βασίζεται στο σχήμα των φύλλων και περιλαμβάνει διάφορα στάδια. Το πρώτο στάδιο είναι η εξαγωγή του περιγράμματος και γίνεται με διαδικασίες επεξεργασίας εικόνας που περιλαμβάνουν τεχνικές ομαδοποίησης και κατάτμησης. Από το περίγραμμα του φύλλου εξάγονται χαρακτηριστικά που δίνουν την δυνατότητα αξιόπιστης περιγραφής κάθε φύλλου. Μελετήθηκαν στη διατριβή αυτή οι παρακάτω γνωστές μέθοδοι: Centroid Contour Distance, Angle code (histogram), Chain Code Fourier Descriptors. Προτάθηκαν επίσης και καινούριες μέθοδοι: Pecstrum (pattern spectrum), Multidimension Sequence Similarity Measure (MSSM). Οι παραπάνω μέθοδοι υλοποιήθηκαν. Παράχθηκε κατάλληλο λογισμικό και εφαρμόσθηκαν σε μία βάση εικόνων φύλλων επιλεγμένη από το διαδίκτυο. Η αξιολόγηση των μεθόδων έγινε μέσα από έλεγχο της συνολικής ακρίβειας κατηγοριοποίησης (με τον confusion matrix). H μέθοδος MSSM έδωσε τα καλύτερα αποτελέσματα. Μία οπτική αξιολόγηση έγινε σε αναπαράσταση 2 διαστάσεων (biplot) μέσα απο διαδικασία Multidimensional Scaling. / The objective of this thesis is the leaf images data base organization (i.e classification, recognition, retrieval etc.). The database organization is based on the leaf shape and is accomplished in a few stages. The contour recognition and recording consist the first stage and is performed with image processing operations namely clustering and segmentation. From the leaf contour several features are extracted appropriate for a reliable description of each leaf type. The following well known techniques were studied in this thesis: Centroid Contour Distance, Angle code (histogram), Chain Code, Fourier Descriptors. Two new metods were also proposed: Pecstrum (pattern spectrum), Multidimension Sequence Similarity Measure. In the experimental study appropriate software was produced to realize all the above methods which was applied to the leaf data base downloaded from internet. The overall evaluation of the methods was done by means of the classification in precision and using the confusion matrix. Best results were produced by the MSSM method.

Proteins and the formation of large protein complexes are essential parts of living organisms. Proteins are present in all aspects of life processes, performing a multitude of various functions ranging from being structural components of cells, to facilitating the passage of certain molecules between various regions of cells. The 'protein docking problem' refers to the computational method of predicting the appropriate matching pair of a protein (receptor) with respect to another protein (ligand), when attempting to bind to one another to form a stable complex. Research shows that matching the three-dimensional (3D) geometric structures of candidate proteins plays a key role in determining a so-called docking pair, which is one of the key aspects of the Computer Aided Drug Design process. However, the active sites which are responsible for binding do not always present a rigid-body shape matching problem. Rather, they may undergo sufficient deformation when docking occurs, which complicates the problem of finding a match. To address this issue, we present an isometry-invariant and topologically robust partial shape matching method for finding complementary protein binding sites, which we call the ProtoDock algorithm. The ProtoDock algorithm comes in two variations. The first version performs a partial shape complementarity matching by initially segmenting the underlying protein object mesh into smaller portions using a spectral mesh segmentation approach. The Heat Kernel Signature (HKS), the underlying basis of our shape descriptor, is subsequently computed for the obtained segments. A final descriptor vector is constructed from the Heat Kernel Signatures and used as the basis for the segment matching. The three different descriptor methods employed are, the accepted Bag of Features (BoF) technique, and our two novel approaches, Closest Medoid Set (CMS) and Medoid Set Average (MSA). The second variation of our ProtoDock algorithm aims to perform the partial matching by utilizing the pointwise HKS descriptors. The use of the pointwise HKS is mainly motivated by the suggestion that, at adequate times, the Heat Kernel Signature of a point on a surface sufficiently describes its neighbourhood. Hence, the HKS of a point may serve as the representative descriptor of its given region of which it forms a part. We propose three (3) sampling methods---Uniform, Random, and Segment-based Random sampling---for selecting these points for the partial matching. Random and Segment-based Random sampling both prove superior to the Uniform sampling method. Our experimental results, run against the Protein-Protein Benchmark 4.0, demonstrate the viability of our approach, in that, it successfully returns known binding segments for known pairing proteins. Furthermore, our ProtoDock-1 algorithm still still yields good results for low resolution protein meshes. This results in even faster processing and matching times with sufficiently reduced computational requirements when obtaining the HKS.