Submitted by Eduarda Figueiredo (eduarda.ffigueiredo@ufpe.br) on 2015-03-06T15:05:20Z No. of bitstreams: 2 teseTCAgilson2012digital.pdf: 1787853 bytes, checksum: 4942f4072dad835d860eb3e2ccfdcecf (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-06T15:05:20Z (GMT). No. of bitstreams: 2 teseTCAgilson2012digital.pdf: 1787853 bytes, checksum: 4942f4072dad835d860eb3e2ccfdcecf (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-04-27 / Encontrar a forma mais e ciente de resolver um problema aritmético e desenvolver algoritmos cada vez melhores é uma grande preocupação dos cientistas, matemáticos e engenheiros projetistas. Economizar operações aritméticas signi ca diminuir o tamanho do hardware, reduzir o consumo de energia e baixar custos de produção. Um algoritmo otimizado minimiza essas três variáveis destacadas. Nesta tese é introduzida a teoria para se obter algoritmos otimizados para qualquer transformada linear. Uma aplicação direta dessa teoria resulta na construção da transformada rápida de Fourier otimizada, a qual atinge o número mínimo possível de multiplicações, sendo mais e ciente do que qualquer algoritmo conhecido na literatura, para computar a transformada discreta de Fourier.

Submitted by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-04-17T14:22:33Z No. of bitstreams: 2 TESE Raimundo Corrêa de Oliveira.pdf: 4679493 bytes, checksum: 92c147d723d5ebefcda7c913e4f62516 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-04-17T14:22:33Z (GMT). No. of bitstreams: 2 TESE Raimundo Corrêa de Oliveira.pdf: 4679493 bytes, checksum: 92c147d723d5ebefcda7c913e4f62516 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2013-04-17 / Esta tese apresenta novos algoritmos rápidos para computação das transformadas discretas de Fourier (DFT) e de Hartley (DHT), denominados FFT e FHT, respectivamente. Os algoritmos FFT são baseados em uma expansão em série matricial de Laurent da matriz de transformação da DFT de comprimento N ≡ 4(mod 8). A complexidade multiplicativa destes apresenta um ganho em relação aos algoritmos Cooley-Tukey base-2 e base-4. Os algoritmos FHT são baseados na expansão da matriz de transformação da DHT de comprimento N ≡ 0(mod 4). Estes algoritmos rápidos apresentaram um melhor desempenho que algoritmos conhecidos para computação da DHT. Além disso, são apresentados algoritmos ótimos, ou seja, de complexidade multiplicativa mínima, para esta transformada, para os comprimentos N = 8, 12, 16 e 24. Uma implementação em FPGA de um dispositivo que calcula as duas transformadas é apresentado; o dispositivo utilizado para implementar o projeto foi um Xilinx Spartan 3E.

Imageamento acústico é um problema computacionalmente caro e mal-condicionado, que envolve estimar distribuições de fontes com grandes arranjos de microfones. O método clássico para imageamento acústico utiliza beamforming, e produz a distribuição de fontes de interesse convoluída com a função de espalhamento do arranjo. Esta convolução borra a imagem ideal, significativamente diminuindo sua resolução. Convoluções podem ser evitadas com técnicas de ajuste de covariância, que produzem estimativas de alta resolução. Porém, estas têm sido evitadas devido ao seu alto custo computacional. Nesta tese, admitimos um arranjo bidimensional com geometria separável, e desenvolvemos transformadas rápidas para acelerar imagens acústicas em várias ordens de grandeza. Estas transformadas são genéricas, e podem ser aplicadas para acelerar beamforming, algoritmos de deconvolução e métodos de mínimos quadrados regularizados. Assim, obtemos imagens de alta resolução com algoritmos estado-da-arte, mantendo baixo custo computacional. Mostramos que arranjos separáveis produzem estimativas competitivas com as de geometrias espirais logaritmicas, mas com enormes vantagens computacionais. Finalmente, mostramos como estender este método para incorporar calibração, um modelo para propagação em campo próximo e superfícies focais arbitrárias, abrindo novas possibilidades para imagens acústicas. / Acoustic imaging is a computationally intensive and ill-conditioned inverse problem, which involves estimating high resolution source distributions with large microphone arrays. The classical method for acoustic imaging consists of beamforming, and produces the source distribution of interest convolved with the array point spread function. This convolution smears the image of interest, significantly reducing its effective resolution. Convolutions can be avoided with covariance fitting methods, which have been known to produce robust high-resolution estimates. However, these have been avoided due to prohibitive computational costs. In this thesis, we assume a 2D separable array geometry, and develop fast transforms to accelerate acoustic imaging by several orders of magnitude with respect to previous methods. These transforms are very generic, and can be applied to accelerate beamforming, deconvolution algorithms and regularized least-squares solvers. Thus, one can obtain high-resolution images with state-of-the-art algorithms, while maintaining low computational cost. We show that separable arrays deliver accuracy competitive with multi-arm spiral geometries, while producing huge computational benefits. Finally, we show how to extend this approach with array calibration, a near-field propagation model and arbitrary focal surfaces, opening new and exciting possibilities for acoustic imaging.

Imageamento acústico é um problema computacionalmente caro e mal-condicionado, que envolve estimar distribuições de fontes com grandes arranjos de microfones. O método clássico para imageamento acústico utiliza beamforming, e produz a distribuição de fontes de interesse convoluída com a função de espalhamento do arranjo. Esta convolução borra a imagem ideal, significativamente diminuindo sua resolução. Convoluções podem ser evitadas com técnicas de ajuste de covariância, que produzem estimativas de alta resolução. Porém, estas têm sido evitadas devido ao seu alto custo computacional. Nesta tese, admitimos um arranjo bidimensional com geometria separável, e desenvolvemos transformadas rápidas para acelerar imagens acústicas em várias ordens de grandeza. Estas transformadas são genéricas, e podem ser aplicadas para acelerar beamforming, algoritmos de deconvolução e métodos de mínimos quadrados regularizados. Assim, obtemos imagens de alta resolução com algoritmos estado-da-arte, mantendo baixo custo computacional. Mostramos que arranjos separáveis produzem estimativas competitivas com as de geometrias espirais logaritmicas, mas com enormes vantagens computacionais. Finalmente, mostramos como estender este método para incorporar calibração, um modelo para propagação em campo próximo e superfícies focais arbitrárias, abrindo novas possibilidades para imagens acústicas. / Acoustic imaging is a computationally intensive and ill-conditioned inverse problem, which involves estimating high resolution source distributions with large microphone arrays. The classical method for acoustic imaging consists of beamforming, and produces the source distribution of interest convolved with the array point spread function. This convolution smears the image of interest, significantly reducing its effective resolution. Convolutions can be avoided with covariance fitting methods, which have been known to produce robust high-resolution estimates. However, these have been avoided due to prohibitive computational costs. In this thesis, we assume a 2D separable array geometry, and develop fast transforms to accelerate acoustic imaging by several orders of magnitude with respect to previous methods. These transforms are very generic, and can be applied to accelerate beamforming, deconvolution algorithms and regularized least-squares solvers. Thus, one can obtain high-resolution images with state-of-the-art algorithms, while maintaining low computational cost. We show that separable arrays deliver accuracy competitive with multi-arm spiral geometries, while producing huge computational benefits. Finally, we show how to extend this approach with array calibration, a near-field propagation model and arbitrary focal surfaces, opening new and exciting possibilities for acoustic imaging.