Many applications in computer graphics and related fields can benefit fromautomatic simplification of complex polygonal surface models. Applications areoften confronted with either very densely over-sampled surfaces or models toocomplex for the limited available hardware capacity. An effective algorithmfor rapidly producing high-quality approximations of the original model is avaluable tool for managing data complexity. In this dissertation, I present my simplification algorithm, based on iterativevertex pair contraction. This technique provides an effective compromisebetween the fastest algorithms, which often produce poor quality results, andthe highest-quality algorithms, which are generally very slow. For example, a1000 face approximation of a 100,000 face model can be produced in about 10seconds on a PentiumPro 200. The algorithm can simplify both the geometryand topology of manifold as well as non-manifold surfaces. In addition toproducing single approximations, my algorithm can also be used to generatemultiresolution representations such as progressive meshes and vertex hierarchiesfor view-dependent refinement. The foundation of my simplification algorithm, is the quadric error metricwhich I have developed. It provides a useful and economical characterization oflocal surface shape, and I have proven a direct mathematical connection betweenthe quadric metric and surface curvature. A generalized form of this metric canaccommodate surfaces with material properties, such as RGB color or texturecoordinates. I have also developed a closely related technique for constructing a hierarchyof well-defined surface regions composed of disjoint sets of faces. This algorithminvolves applying a dual form of my simplification algorithm to the dual graphof the input surface. The resulting structure is a hierarchy of face clusters whichis an effective multiresolution representation for applications such as radiosity.

An efficient numerical method for solving Schr&ouml / dinger&#039 / s and Poisson&#039 / s equations using a basis set of cubic B-splines is investigated. The method is applied to find both the wave functions and the corresponding eigenenergies of low-dimensional semiconductor structures. The computational efficiency of the method is explicitly shown by the multiresolution analysis, non-uniform grid construction and imposed boundary conditions by applying it to well-known single electron potentials. The method compares well with the results of analytical solutions and of the finite difference method.

RNA is amazing. We found that without changing the backbone connectivity, RNA can maintain structural conservation in 3D via topology switches, at a single residue level. I developed a method of representing RNA structure in multiresolution, called the PBR approach (P stands for Phosphate; B stands for Base; R stands for Ribose). In this method, structural data is viewed through a series of resolutions from finest to coarsest. At a single nucleotide resolution (fine resolution), RNA is abstruse and elaborate with structural insertions/deletions, strand clips, and 3,2-switches. The compilation of structural deviations of RNA, called DevLS (Deviations of Local Structure), provides a new descriptive language of RNA structure, allowing one to systematize and investigate RNA structure. Using PBR analysis, a total of 103 tetraloops within the crystal structures of the 23s rRNA of H. marismortui and the 70s rRNA of T. thermophilus are found and classified. Combining them, I constructed a 'tetraloop family tree', using a tree formalism, to unify and re-define the tetraloop motif and to represent relationships between tetraloops, as grouped by DevLS. To date, structural alignment of very large RNAs remains challenge due to the large size, intricate backbone choreography, and tertiary interactions. To overcome these obstacles, I developed a concept of structural anchors along with a 'Divide and Conquer' strategy for performing superimposition of 23s rRNAs. The successful alignment and superimpositions of the 23s rRNAs of T. thermophilus and H. marismortui gives an overall RMSD of atomic positions of 1.2 Å, as utilized 73% of RNA backbone atoms (~ 2129 residues). By using principles of inorganic chemistry along with structural alignment technique as described above, a recurrent magnesium-binding motif in large RNAs is revealed. These magnesium-binding motifs play a critical role in the framework of the ribosomal PTC by their locations, topologies, and coordination geometries. Common features of Mg2+-mc's include direct phosphate chelation of two magnesium ions in the form of Mg2+(i)-(O1P-P-O2P)-Mg2+(j), phosphate groups of adjacent RNA residues as ligands of a given Mg2+, and undulated RNA surfaces with unpaired and unstacked bases.

Texture analysis is an important problem in machine vision, with applications in many fields including medical imaging, remote sensing (SAR), automated flaw detection in various products, and document analysis to name but a few. Over the last four decades many techniques for the analysis of textured images have been proposed in the literature for the purposes of classification, segmentation, synthesis and compression. Such approaches include analysis the properties of individual texture elements, using statistical features obtained from the grey-level values of the image itself, random field models, and multichannel filtering. The wavelet transform, a unified framework for the multiresolution decomposition of signals, falls into this final category, and allows a texture to be examined in a number of resolutions whilst maintaining spatial resolution. This thesis explores the use of the wavelet transform to the specific task of texture classification and proposes a number of improvements to existing techniques, both in the area of feature extraction and classifier design. By applying a nonlinear transform to the wavelet coefficients, a better characterisation can be obtained for many natural textures, leading to increased classification performance when using first and second order statistics of these coefficients as features. In the area of classifier design, a combination of an optimal discriminate function and a non-parametric Gaussian mixture model classifier is shown to experimentally outperform other classifier configurations. By modelling the relationships between neighbouring bands of the wavelet trans- form, more information regarding a texture can be obtained. Using such a representation, an efficient algorithm for the searching and retrieval of textured images from a database is proposed, as well as a novel set of features for texture classification. These features are experimentally shown to outperform features proposed in the literature, as well as provide increased robustness to small changes in scale. Determining the script and language of a printed document is an important task in the field of document processing. In the final part of this thesis, the use of texture analysis techniques to accomplish these tasks is investigated. Using maximum a posterior (MAP) adaptation, prior information regarding the nature of script images can be used to increase the accuracy of these methods. Novel techniques for estimating the skew of such documents, normalising text block prior to extraction of texture features and accurately classifying multiple fonts are also presented.

[pt] Reconstruir a informação 3D de uma cena é uma tarefa bastante comum em Visão Computacional. Uma das técnicas mais utilizadas para realizar esta tarefa é a correspondência por estéreo, que consiste basicamente em, dadas duas imagens referentes a uma mesma cena vista de pontos diferentes, determinar os pontos correspondentes entre essas duas imagens e armazenar essa informação em um mapa de disparidades. Até hoje diversos métodos foram propostos para resolver o problema de estéreo com esforço computacional viável e mantendo a qualidade dos resultados. Essa, entretanto, é uma tarefa bastante árdua e que difícilmente alcança resultados precisos com pouco esforço computacional. Nesse âmbito, uma técnica que tem sido muito estudada são os Cortes de Grafo (Graph Cuts), que almeja resolver o problema de minimização de energia em tempo polinomial. Nesse caso o problema de estéreo é mapeado como um problema de minimização de energia e desta forma solucionado utilizando cortes de grafo. Neste trabalho estudamos as técnicas de cortes de grafo mais recentes e eficientes e propomos um método para a determinação de correspondências entre duas imagens num contexto de multi-resolução, no qual uma pirâmide Gaussiana para as imagens é construída e a técnica de cortes de grafo é aplicada em níveis menores, otimizando a performance e obtendo resultados mais precisos através da utilização do algoritmo de expansão-alfa. São revisadas as técnicas de cortes de grafo e de multi-resolução e os resultados obtidos são apresentados e avaliados em relação a métodos semelhantes. / [en] Reconstructing the 3D information of a scene is a common task in Computer Vision. Stereo matching is one of the most investigated techniques used to perform this task, which basically consists of, given two images of a scene seen from different view points, determining corresponding pixels in these two images and store this information in a disparity map. Several methods have been proposed to solve the stereo problem keeping good performance and giving good quality results. This is however a very arduos task which hardly achieves precise results with low computational power. In this context, the Graph Cuts method has been very much considered, which aims to solve the energy minimization problem in polinomial time. In this case the stereo problem can be modelled as an energy minimization problem and, thus solved using the Graph Cuts technique. In this work we investigate the most recent and efficient Graph Cuts methods and propose a method for establishing the correspondences between two images in the context of multi-resolution, in which a Gaussian pyramid for the input images is built and the Graph Cuts methods is applied in coarser levels, optimizing the performance and getting more precise results through the use of the alfa-expansion algorithm. The Graph Cuts and multi-resolution techniques are reviewed and the results of the proposed method are presented and evaluated compared to similar methods.

O presente trabalho visa a utilização da transformada Wavelet no monitoramento do sistema elétrico no que diz respeito a problemas de qualidade da energia com o intuito de detectar, localizar e classificar os mesmos. A transformada Wavelet tem surgido na literatura como uma nova ferramenta para análise de sinais, utilizando funções chamadas Wavelet mãe para mapear sinais em seu domínio, fornecendo informações simultâneas nos domínios tempo e freqüência. A transformada Wavelet é realizada através de filtros decompondo-se um dado sinal em análise multiresolução. Por esta, obtém-se a detecção e a localização de distúrbios relacionados com a qualidade da energia decompondo-se o sinal em dois outros que representam uma versão de detalhes (correspondente as altas freqüências do sinal) e uma versão de aproximação (correspondente as baixas freqüências do sinal). A versão de aproximação é novamente decomposta obtendo-se novos sinais de detalhes e aproximações e assim sucessivamente. Sendo assim, os distúrbios podem ser detectados e localizados no tempo em função do seu conteúdo de freqüência. Estas informações fornecem também características únicas pertinentes a cada distúrbio, permitindo classificá-los. Desta forma, propõe-se neste trabalho o desenvolvimento de um algoritmo classificador automático de distúrbios relacionados com a qualidade da energia baseado unicamente nas decomposições obtidas da análise multiresolução. / The aim of the present dissertation is to apply the Wavelet transform to analyze power quality problems, detecting, localizing and classifying them. The topic Wavelet transform, has appeared in the literature as a new tool for the analysis of signals, using functions called mother Wavelet to map signals in its domain, supplying information in the time and frequency domain, simultaneously. Wavelet transform is accomplished through filters decomposing a provided signal in multiresolution analysis. The detection and localization of disturbances are obtained by decomposing a signal into two other signals that represent, a detailed version (high frequency signals) and a smoothed version (low frequency signals). The smoothed version is decomposed again, and new detailed and smoothed signals are obtained. This process is repeated as many times as necessary and the disturbances can be detected and localized in the time as a function of its level frequency. This information also supplies characteristics to each disturbance, allowing classifying them. Thus, this research presents a way to develop an automatic classifying algorithm of power quality disturbances, based only on multiresolution analysis.

Image inpainting is the process of recovering missing or deteriorated data within the digital images and videos in a plausible way. It has become an important topic in the area of image processing, which leads to the understanding of the textural and structural information within the images. Image inpainting has many different applications, such as image/video restoration, text/object removal, texture synthesis, and transmission error concealment. In recent years, many algorithms have been developed to solve the image inpainting problem, which can be roughly grouped into four categories, partial differential equation-based inpainting, exemplar-based inpainting, transform domain inpainting, and hybrid image inpainting. However, the existing algorithms do not work well when the missing region to be inpainted is large, and when there are textural and structural information needed to be recovered. To address this inpainting problem, we propose multiple algorithms, 1) perceptually aware image inpainting based on the perceptual-fidelity aware mean squared error metric, 2) image inpainting using nonlocal texture matching and nonlinear filtering, and 3) multiresolution exemplar-based image inpainting. The experimental results show that our proposed algorithms outperform other existing algorithms with respect to both qualitative analysis and observer studies when inpainting the missing regions of images.

The Wavelet Finite Element Method (WFEM) involves combining the versatile wavelet analysis with the classical Finite Element Method (FEM) by utilizing the wavelet scaling functions as interpolating functions; providing an alternative to the conventional polynomial interpolation functions used in classical FEM. Wavelet analysis as a tool applied in WFEM has grown in popularity over the past decade and a half and the WFEM has demonstrated potential prowess to overcome some difficulties and limitations of FEM. This is particular for problems with regions of the solution domain where the gradient of the field variables are expected to vary fast or suddenly, leading to higher computational costs and/or inaccurate results. The properties of some of the various wavelet families such as compact support, multiresolution analysis (MRA), vanishing moments and the “two-scale” relations, make the use of wavelets in WFEM advantageous, particularly in the analysis of problems with strong nonlinearities, singularities and material property variations present. The wavelet based finite elements (WFEs) presented in this study, conceptually based on previous works, are constructed using the Daubechies and B-spline wavelet on the interval (BSWI) wavelet families. These two wavelet families possess the desired properties of multiresolution, compact support, the “two scale” relations and vanishing moments. The rod, beam and planar bar WFEs are used to study structural static and dynamic problems (moving load) via numerical examples. The dynamic analysis of functionally graded materials (FGMs) is further carried out through a new modified wavelet based finite element formulation using the Daubechies and BSWI wavelets, tailored for such classes of composite materials that have their properties varying spatially. Consequently, a modified algorithm of the multiscale Daubechies connection coefficients used in the formulation of the FGM elemental matrices and load vectors in wavelet space is presented and implemented in the formulation of the WFEs. The approach allows for the computation of the integral of the products of the Daubechies functions, and/or their derivatives, for different Daubechies function orders. The effects of varying the material distribution of a functionally graded (FG) beam on the natural frequency and dynamic response when subjected to a moving load for different velocity profiles are analysed. The dynamic responses of a FG beam resting on a viscoelastic foundation are also analysed for different material distributions, velocity and viscous damping profiles. The approximate solutions of the WFEM converge to the exact solution when the order and/or multiresolution scale of the WFE are increased. The results demonstrate that the Daubechies and B-spline based WFE solutions are highly accurate and require less number of elements than FEM due to the multiresolution property of WFEM. Furthermore, the applied moving load velocities and viscous damping influence the effects of varying the material distribution of FG beams on the dynamic response. Additional aspects of WFEM such as, the effect of altering the layout of the WFE and selection of the order of wavelet families to analyse static problems, are also presented in this study.

Wavelets are functions used to approximate data and can be traced back to several different areas, including seismic geology and quantum mechanics. Wavelets are applicable in many areas, including fingerprint and data compression, earthquake prediction, speech discrimination, and human vision. In this paper, we first give a brief history on the origins of wavelet theory. We will then discuss the work of Daubechies, whose construction of continuous, compactly supported scaling functions resulted in an explosion in the study of wavelets in the 1990's. These scaling functions allow for the construction of Daubechies' wavelets. Next, we shall use the algorithm to construct the Daubechies D4 scaling filters associated with the D4 scaling function. We then explore the Cascade Algorithm, which is a process that uses approximations to get possible representations for the D2N scaling function of Daubechies. Lastly, we will use the Cascade Algorithm to get a visual representation of the D4 scaling function.

Cette thèse introduit un cadre d’analyse multirésolution pour les données de classements. Initiée au 18e siècle dans le contexte d’élections, l’analyse des données de classements a attiré un intérêt majeur dans de nombreux domaines de la littérature scientifique : psychométrie, statistiques, économie, recherche opérationnelle, apprentissage automatique ou choix social computationel entre autres. Elle a de plus été revitalisée par des applications modernes comme les systèmes de recommandation, où le but est d’inférer les préférences des utilisateurs pour leur proposer les meilleures suggestions personnalisées. Dans ces contextes, les utilisateurs expriment leurs préférences seulement sur des petits sous-ensembles d’objets variant au sein d’un large catalogue. L’analyse de tels classements incomplets pose cependant un défi important, tant du point de vue statistique que computationnel, poussant les acteurs industriels à utiliser des méthodes qui n’exploitent qu’une partie de l’information disponible. Cette thèse introduit une nouvelle représentation pour les données, qui surmonte par construction ce double défi. Bien qu’elle repose sur des résultats de combinatoire et de topologie algébrique, ses nombreuses analogies avec l’analyse multirésolution en font un cadre naturel et efficace pour l’analyse des classements incomplets. Ne faisant aucune hypothèse sur les données, elle mène déjà à des estimateurs au-delà de l’état-de-l’art pour des petits catalogues d’objets et peut être combinée avec de nombreuses procédures de régularisation pour des larges catalogues. Pour toutes ces raisons, nous croyons que cette représentation multirésolution ouvre la voie à de nombreux développements et applications futurs. / This thesis introduces a multiresolution analysis framework for ranking data. Initiated in the 18th century in the context of elections, the analysis of ranking data has attracted a major interest in many fields of the scientific literature : psychometry, statistics, economics, operations research, machine learning or computational social choice among others. It has been even more revitalized by modern applications such as recommender systems, where the goal is to infer users preferences in order to make them the best personalized suggestions. In these settings, users express their preferences only on small and varying subsets of a large catalog of items. The analysis of such incomplete rankings poses however both a great statistical and computational challenge, leading industrial actors to use methods that only exploit a fraction of available information. This thesis introduces a new representation for the data, which by construction overcomes the two aforementioned challenges. Though it relies on results from combinatorics and algebraic topology, it shares several analogies with multiresolution analysis, offering a natural and efficient framework for the analysis of incomplete rankings. As it does not involve any assumption on the data, it already leads to overperforming estimators in small-scale settings and can be combined with many regularization procedures for large-scale settings. For all those reasons, we believe that this multiresolution representation paves the way for a wide range of future developments and applications