O presente projeto consistiu no estudo e aplicação do algoritmo FDK (Feldkamp-Davis-Kress) para a reconstrução de imagens tomográficas utilizando a geometria de feixe cônico, resultando na implementação de um sistema adaptado de tomografia computadorizada multicortes (TCMC). Para a aquisição das projeções, utilizou-se uma plataforma giratória com goniômetro acoplado, um equipamento de raios X e um detector digital, tipo CCD. Para processar a reconstrução das imagens, foi utilizado um PC, no qual foi implementado o algoritmo FDK. Inicialmente foi aplicado o algoritmo FDK original, no qual se assume o caso físico ideal no processo de medições. Em seguida, foram incorporadas ao algoritmo, algumas correções de artefatos relacionados ao processo de medição das projeções. Para testar o funcionamento do algoritmo implementado, foram feitas reconstruções a partir de projeções simuladas computacionalmente. Foram montados e testados três sistemas de aquisição de projeções, nos quais foram usados diferentes equipamentos de raios X, detectores, metodologias e técnicas radiográficas, a fim de garantir que fossem coletados os melhores conjuntos possíveis de projeções. Realizou-se a calibração do sistema de TCMC implementado. Para isso, utilizou-se um objeto com uma distribuição de coeficientes de atenuação linear conhecida, que foi projetado e fabricado especificamente para isto. Por fim, o sistema de TCMC implementado foi utilizado na reconstrução tomográfica de um objeto não homogêneo, cuja distribuição volumétrica do coeficiente de atenuação linear é desconhecida. As imagens reconstruídas foram analisadas a fim de avaliar o desempenho do sistema de TCMC implementado. / This work consisted on the study and application of the FDK (Feldkamp-Davis-Kress) algorithm for tomographic image reconstruction using cone-beam geometry, resulting on the implementation of an adapted multi-slice computed tomography (MSCT) system. For the acquisition of the projections, a rotating platform coupled to a goniometer, an x-ray equipment and a CCD type digital detector were used. The FDK algorithm was implemented on a PC which was used for the reconstruction process. Initially, the original FDK algorithm was applied considering only the ideal physical conditions in the measurement process. Then some artifacts corrections related to the projections measurement process were incorporated. Computational simulations were performed to test the functioning of the implemented algorithm. Three projections acquisition systems, which used different x-ray equipments, detectors, methodologies and radiographic techniques, were assembled and tested in order to ensure that the best possible set of data was collected. The implemented MSCT system was calibrated. A specially designed and manufactured object with a known linear attenuation coefficient distribution was used for this purpose. Finally, the implemented MSCT system was used for multi-slice tomographic reconstruction of an inhomogeneous object, whose attenuation coefficient distribution was unknown. The reconstructed images were analyzed to assess the performance of the TCMC system that was implemented.

O Homem tem desde o passado, tentado controlar a natureza. Um dos meios utilizados para isto, é sua observação do mundo. Através desta observação, tenta entender os fenômenos da natureza para fazer teorias e modelos. Charles Darwin, em seu trabalho Teoria da Evolução das Espécies, nos dá informações para o conhecimento de uma das mais importantes leis da natureza : sobrevive para a próxima geração o individuo mais forte. O Algoritmo Genético, pesquisado neste trabalho, é o exemplo disso. John Holland fez um Algoritmo Genético baseado na teoria de Darwin, que procura pelas melhores soluções para resolver um problema específico. Nada mais do que a simulação da teoria de Darwin. Nós pretendemos neste trabalho, estudar o Algoritmo Genético de Holland e através dele, analisar uma estrutura para encontrar seus parâmetros elásticos. / The men has since the past, tryed to control the nature. One of the way utilized for this, is his observation of the world. Through his observation, tries to understand the nature\'s fenomena, to making theories and models. Charles Darwin, in his work Theories of Species Evolution, gives us informations for the knowledges of one of the most important nature\'s laws: survives to the next generation the strongest individual . The Genetic Algorithm, the search in this work, is the example of this. John Holland, did a Genetic Algorithm. based in Darwin\'s Theories, that looks for the best solutions to solve a specific problem. Nothing else, of the simulation of the Darwin\'s theories . We intend in this work, to study the Holland\'s Genetic Algorithms and through it, to analyses a structure for find its elastic parameters.

Orientadores: Jose Mario Martinez, Roberto Andreani / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-04T03:19:42Z (GMT). No. of bitstreams: 1 SalvatierraJunior_Mario_D.pdf: 1492550 bytes, checksum: eb4d3783eea3e4aec959a4828e4d6260 (MD5) Previous issue date: 2005 / Resumo: Neste trabalho é definido um método novo de otimização global combinando idéias determinísticas e estocásticas. Para isto, usamos uma estratégia para escapar de mínimos locais baseada em seguir a trajetória da curva de Lissajous, uma curva densa e suave numa caixa limitada O. O algoritmo global é aplicado num problema geofísico, conhecido como o problema da Superfície de Reflexão Comum (CRS), e no problema de encontrar padrões ocultos. Também apresentamos um método quase-Newton para o problema OVO que generaliza o método local de Cauchy (aqui utilizado como método local para encontrar padrões ocultos), e provamos sua convergência superlinear e quadrática. Este novo método é aplicado à uma variação Brasileira do Sistema Bancário Ideal de Stiglitz / Abstract: In this work a new global optimization method is defined combining deterministic and stochastic ideas. For this, we use a strategy to escape of local minimums established in following the trajectory of the Lissajous curve, a dense and smooth curve in an limited box O. The global algorithm is applied in a geophysical problem, known as the Common Reflection Surface (CRS) problem, and in the problem to find hidden patterns. Also we present a quasi-Newton method for the OVO problem that generalizes the Cauchy local method (used here as local method to find hidden patterns), and prove its superlinear and quadratic convergence. This new method is applied to a Brazilian variation of the Stiglitz¿s Ideal Banking System / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

[pt] Este trabalho está dividido em duas partes. A primeira parte trata das relações entre o problema de otimização d.c. (diferença de duas funções convexas) e o problema de otimização d.c. regularizado por inf-convolução, com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. Neste sentido se generaliza a relação de TOLAND (1979): inf { g(x) - h(x) } = inf { h(asterístico (y) - g (asterístico(y) }, H H E a relação de GABAY (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Onde g, h , são funções convexas próprias e semicontínuas inferiormente, g(asterístico), h(asterístico), são conjugadas de g e h, respectivamente, H é um espaço de Hilbert real, e g (lambda), h lambda , são as funções regularizadas respectivas de g e h, por inf-convolução com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. A segunda parte deste trabalho apresenta um algoritmo novo para tratar com o problema de otimização d.c.. Trata-se de um método de descida do tipo proximal, onde se leva em consideração separadamente as propriedades de convexidade das duas funções convexas. / [en] The work is divided in two parts. The first part is concerned with the relationship between the d.c. optimization problem. In this sence we geralize the TOLAND´s relation (1979): inf { g(x) - h(x) } = inf { h(asteristic)(y) - g (asteristic)(y) }, H H And the GABAY´s relation (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Where g, h, are l.s.c. convex functions, g(asteristic) and h(asteristic) are their conjugates, H is a real Hilbert space, and g lambda, h lambda, are the inf-convolution of g and h respectively, with the núcleos 8( . ) = (2 lambda)- 1 l l . l l 2 , lambda > 0. In the second part we present a new algorithm for dealing with d.c. functions. It is a descent method of proximal kind which takes in consideration the convex properties of the two convex functions separately

[pt] Apresenta-se nesta dissertação um novo algoritmo para o cálculo de algumas funções distância entre polígonos convexos, no caso geral em que os polígonos podem se interseptar, cuja complexidade linear de pior caso é melhor do que a dos algoritmos até então conhecidos na literatura. O algoritmo é baseado em um algoritmo de complexidade linear originalmente proposto para determinação da distância de Hausdorff entre polígonos convexos disjuntos e utiliza como sua principal componente um algoritmo linear para o cálculo da interseção entre polígonos convexos. A motivação para o estudo de algoritmos eficientes para este problema de cálculo de distâncias decorre de aplicações em reconhecimento de formas e superposição ótima de contornos. Resultados computacionais também são apresentados. / [en] We present in this dissertation a new algorithm for the computation of some distance functions between convex polygons, in the general case where they can intersect, whose worst case time complexity is better than of the previously known algorithms. The algorthm is based on an algorithm originally proposed for the computation of the Hausdorff distance between disjoint polygons and uses as its main component a linear time algorithm for finding the intersection of convex polygons. The motivation for the study of efficient algorithms for this distance computation problem comes from applications in pattern recognition and contour fitting. Computatioal results are also presented.

[pt] Este trabalho é composto do projeto e implementação de um sistema gráfico para uso em microcomputadores do tipo IBM PC visando aplicações em CDA, animação e processamento de imagens. Com várias configurações programáveis destaca-se a capacidade do uso de altas resoluções e grande número de cores, podendo chegar a 16 milhões. Todo o processamento é feito por um microprocessador RISC, o que se traduz em alto desempenho e grande flexibilidade na execução de rotinas e algoritmos gráficos. / [en] The contents of this work are the Project and implementation of a graphic system for IBM PC microcomputers for use in CAD, animation, and image processing. Among its features stand out the display resolution and up to 16 million colors. All the processing are made by a RISC microprocessor, leading to a high performance and great flexibility in routine and graphics algorithm execution.

The thesis covers construction, application and evaluation of a stemming algorithm for advanced information searching and retrieval in Latvian databases. Its aim is to examine the following two questions: Is it possible to apply for Latvian a suffix removal algorithm originally designed for English? Can stemming in Latvian produce the same or better information retrieval results than manual truncation? In order to achieve these aims, the role and importance of automatic word conflation both for document indexing and information retrieval are characterised. A review of literature, which analyzes and evaluates different types of stemming techniques and retrospective development of stemming algorithms, justifies the necessity to apply this advanced IR method also for Latvian. Comparative analysis of morphological structure both for English and Latvian language determined the selection of Porter's suffix removal algorithm as a basis for the Latvian sternmer. An extensive list of Latvian stopwords including conjunctions, particles and adverbs, was designed and added to the initial sternmer in order to eliminate insignificant words from further processing. A number of specific modifications and changes related to the Latvian language were carried out to the structure and rules of the original stemming algorithm. Analysis of word stemming based on Latvian electronic dictionary and Latvian text fragments confirmed that the suffix removal technique can be successfully applied also to Latvian language. An evaluation study of user search statements revealed that the stemming algorithm to a certain extent can improve effectiveness of information retrieval.

It is a new and open-source benchmark for multiprocessor based embedded system. It comprises a set of parallel implementations for seven classical algorithms that cover different computing features of general-purpose processor. The performance data including tables and figures is provided for guiding the potential users to evaluate the design of multiprocessor based embedded system. The parallel implementations for seven applications that cover four categories are shown according to the category: Automation and Industry Control * Bitcount * SUSAN * BASICMATH Network * Patricia * Dijkstra Office * Stringsearch Security * SHA Among them, Bitcount and Dijkstra involve more than one parallel application implemented for different functions or using different strategies. Bitcount consists three parallel applications, parallel Bitcnt_1, parallel Bitstring and parallel Bitcnts, that implemented bit counting with different strategy. Three parallel applications implemented for Dijkstra. One is for all-pairs shortest paths problem. Another two are for solving single-source shortest paths problem using single queue strategy and multiple queue strategy respectively. Stringsearch consists of Pratt-Boyer-Moore, Case-sensitive Boyer-Moore-Horspool, Case-Insensitive Boyer-Moore-Horspool, and Boyer-Moore-Horspool (Case-insensitive with accented character translation) implementations. Source code of sequential versions of these applications download from Mibench as well as the standard output based on x86-linux. For OpenMPBench, all parallel applications have been implemented in ANCI C language using POSIX threads. All libraries related to implementations are based on GNU standard library. Development environment is in UBUNTU 9.04 with 2.6.28-generic Linux kernel, GCC 4.2.4 compiler, and Emacs 22.1 editor. On the basis of current hardware condition, a workstation with 8 processors, shipped with UBUNTU 4.2.4, is selected for experiment environment. UBUNTU is a free GNU Linux version that offers all GNU standard library and GCC has been installed by default. In conclusion, we consider this experiment environment is available to simulate the multiprocessor based on embedded systems. / Det är en ny och öppen källkod riktmärke för multiprocessor baserade inbyggda system. Det innehåller en rad parallella implementationer i sju klassiska algoritmer som täcker olika datorer funktioner i allmänt bruk processor. Uppgifter om prestanda inklusive tabeller och siffror ges för att styra potentiella användare att utvärdera utformningen av multiprocessor baserade inbyggda system. De parallella implementeringar för sju ansökningar som omfattar fyra kategorier visas beroende på vilken kategori: Automation och industri Control * Bitcount * SUSAN * BASICMATH Nätverk * Patricia * Dijkstra Office * Stringsearch Säkerhet * SHA Bland dem, Bitcount och Dijkstra omfattar mer än en parallell ansökan genomförs för olika funktioner eller med hjälp av olika strategier. Bitcount består tre parallella program, parallell Bitcnt_1, parallell Bitstring och parallella Bitcnts, som genomförs bit räknar med olika strategi. Tre parallella ansökningar genomförs för Dijkstra. Den ena är för all-par kortaste stigar problem. Ytterligare två är för att lösa enda källa kortaste stigar problemet, använder en kö strategi och flera kö strategi respektive. Stringsearch består av Pratt-Boyer-Moore, skiftlägeskänslig Boyer-Moore-Horspool, skiftlägesokänslig Boyer-Moore-Horspool, och Boyer-Moore-Horspool (små bokstäver med accenttecken översättning) implementationer. Källkod sekventiell versioner av dessa program att hämta från Mibench liksom standard produktion baserad på x86-linux. För OpenMPBench har alla parallella ansökningar har genomförts i ANCI C-språk med POSIX trådar. Alla bibliotek i samband med implementationer är baserat på GNU standard bibliotek. Utvecklingsmiljö i Ubuntu 9.04 med 2.6.28-generic Linuxkärnan, GCC 4.2.4 kompilator och Emacs 22,1 redaktör. På grundval av nuvarande hårdvara skick, en arbetsstation med 8 processorer, som levereras med Ubuntu 4.2.4, har valts för experiment miljön. Ubuntu är ett gratis GNU Linux-version som kan erbjuda alla GNU Standard bibliotek och GCC har installerats som standard. Sammanfattningsvis anser vi att detta experiment miljön är tillgänglig för att simulera multiprocessor baserade på inbyggda system. / Yuchen Liang: phone no: 8641182120823 6-3-1, No. 44, Huabei Road Ganduan, Ganjingzi District, Dalian City, 116023, Liaoning Province, P. R. China Syed Muhammad Zeeshan Iqbal: phone no: 92415510275 Muhallah Gurunanak Pura, Street No: 7, House No:211, Faisalabad, Pakistan

La famille de modèles dite des filtres de Kalman permet d'estimer les états d'un système dynamique à partir d'une série de mesures incomplètes ou bruitées. Malgré leur relative simplicité de modélisation, ces filtres sont utilisés dans un large spectre scientifique dont le radar, la vision, et les communications. Ce succès repose, pour l'essentiel, sur l'existence d'algorithmes de filtrage et de lissage exacts et rapides, \ie linéaires au nombre d'observations, qui minimisent l'erreur quadratique moyenne. Dans cette thèse, nous nous sommes intéressés au filtre de Kalman couple. Celui-ci intègre, par rapport au modèle original, de nouvelles possibilités d'interactions entre états cachés et observations, tout en conservant des algorithmes exacts et rapides dans le cas linéaire et gaussien. Nous étudions plus particulièrement le problème de l'estimation non supervisée et robuste des paramètres d'un filtre de Kalman couple à partir d'observations en nombre limité. Le manuscrit décrit ainsi plusieurs algorithmes d'apprentissage par estimation du maximum de vraisemblance selon le principe EM (\textit{Expectation-Maximization}). Ces algorithmes originaux permettent d'intégrer des contraintes a priori sur les paramètres du système étudié, comme expressions de connaissances partielles sur la physique de l'application ou sur le capteur. Ces systèmes contraints réduisent l'ambiguïté liée au problème d'identifiabilité du filtre de Kalman couple lors de l'estimation des paramètres. Ils permettent également de limiter le nombre de maxima locaux de la fonction de vraisemblance en réduisant la dimension de l'espace de recherche, et ainsi évitent parfois le piégeage de l'algorithme EM. Il est important de noter que l'ensemble des algorithmes proposés dans ce manuscrit s'applique directement au filtre de Kalman original, comme cas particulier du filtre de Kalman couple. Tous les algorithmes sont rendus robustes par la propagation systématique de racines-carrés des matrices de covariance au lieu des matrices de covariance elles-mêmes, permettant ainsi d'éviter les difficultés numériques bien connues liées à la perte de positivité et de symétrie de ces matrices. Ces algorithmes robustes sont finalement évalués et comparés dans le cadre d'une application de biométrie de l'iris à partir de vidéos. Le suivi de la pupille est exploitée pour enrôler et identifier en temps-réel une personne grâce à son iris-code. / The family of Kalman filter model allows to estimate the states of a dynamical system from a set of observations. Despite a simple model, these filters are used in a large field of applications: Radar, vision and communications. The success is mainly based on the existence of exact smoothing or filtering algorithms, \ie linear to the number of observations and which minimize the mean square error. In this thesis, we are concerned about the pairwise Kalman filter. This filter adds from the orignal model, new interactions between hidden states and obervations while keeping exact algorithms in the case of linear and Gaussian models. We studied particularly the problem of the unsupervised and robust estimation of a pairwise Kalman filter parameters from a limited set of observations. The manuscript describes several learning algorithms by the estimation of the likelihood maximum according to EM (\textit{Expectation-Maximization}) principle. These original algorithms allow to embed a-priori constraints on studied system parameters, like a knowledge about physical or sensors. These constrained systems reduce the ambiguity, linked to identifiability issue of the pairwise Kalman filter during the parameter estimation. They allow also to limit the number of local maxima of likelihood function with the reduction of the dimension of search space and avoid sometime the trapping of EM algorithm. It is important to note that all proposed algorithm of this manuscrit can be applied to the original Kalman filter, as a particular pairwise Kalman filter. All algorithm are made robust by the propagation of square root matrices instead of the covariance matrices, which allows to limit the numerical issues, linked to the loses of symetry or positivity of these matrices. These algorithm are finally evaluated and compared in the case of an iris biometry application from video sequences. Pupil tracking is used to enroll and recognize in real-time a person thanks to its iris-code.

During the last decade increasing interest in parallel programming can be observed. It is caused by a tendency of developing microprocessors as a multicore units, that can perform instructions simultaneously. Popular and widely used example of such platform is a graphic processing unit (GPU). Its ability to perform calculations simultaneously is being investigated as a way for improving performance of the complex algorithms. Therefore, GPU’s are now having the architectures that allows to use its computional power by programmers and software developers in the same way as CPU. One of these architectures is CUDA platform, developed by nVidia. Aim of this thesis is to implement the parallel CYK algorithm, which is one of the most popular parsing algorithms, for CUDA platform, that will gain a significant speed-up in comparison with the sequential CYK algorithm. The thesis presents review of existing parallelisations of CYK algorithm, descriptions of implemented algorithms (basic version and few modifications), and experimental stage, that includes testing these versions for various inputs in order to justify which version of algorithm is giving the best performance. There are three versions of algorithm presented, from which one was selected as the best (giving about 10 times better performance for the longest instances of inputs). Also, a limited version of algorithm, that gives best performance (even 100 times better in comparison with non-limited sequential version), but requires some conditions to be fulfilled by grammar, is presented. The motivation for the thesis is to use the developed algorithm in GCS.