A transformada esparsa de Fourier e sua aplicação na extraçao de características de imagens

Abstract

Resumo: Separar uma função complexa em uma série de funções mais simples simplificou o estudo de muitas área na ciência e na engenharia. Este processo ficou conhecido como transformada de Fourier, ou transformada discreta de Fourier. A transformada discreta de Fourier é computada, na forma mais direta, em O(N2) operações, onde N é o tamanho do sinal. Entretanto, desde a descoberta da transformada rápida de Fourier, um algoritmo que computa a transformada discreta de Fourier em O(N log N) operações, muitas aplicações surgiram e foi considerado um dos algoritmos mais importantes do século. A transformada rápida de Fourier é amplamente utilizada para processamento e análise de sinais digitais. Observou-se na prática que muitos sinais possuem um espectro com poucos coeficientes significativos. Estudos recentes apresentam algoritmos que fazem proveito dessa característica que sinais do mundo físico possuem para gerar um algoritmo de aproximação da tranformada de Fourier com complexidade de tempo sublinear ao tamanho do sinal. Estes algoritmos são chamados de transformada esparsa de Fourier. Este trabalho apresenta uma revisão de algoritmos dessa classe e, com mais detalhes, o primeiro algoritmo que superou, na prática, o tempo de execução da transformada rápida de Fourier para alguns sinais exatamente esparsos. Além disso, o trabalho também apresenta resultados de experimentos para determinar quão esparso o espectro de imagens são utilizando a definição de energia dada pelo Teorema de Parseval. Finalmente, o algoritmo da transformada esparsa é utilizado para recuperar os maiores coeficientes daquelas imagens diretamente. Palavras-chave: transformada discreta de Fourier, transformada rápida de Fourier, transformada esparsa de Fourier, processamento de sinais digitais, sinais esparsos.

Abstract: Separating a complex function into a series of simpler functions has improved studies in most areas in science and in engineering. This process became known as the Fourier transform, or discrete Fourier transform. The discrete Fourier transform can be computed, in the most direct way, with O(N2) operations, where N is the signal size. However, since the discovery of the fast Fourier transform, an algorithm that computes the discrete Fourier transform in O(N log N) operations, many applications became possible and the algorithm has been considered one of the most important algorithm of the century. The fast Fourier transform is widely used in digital signal processing and analysis. It was observed that signals in the physical world had spectra that only a few coefficients are significants. Recent studies presents algorithms that explores this characteristic of signals computes an approximation of the Fourier transform of these signal in a sublinear time complexity in the signals size. These algorithms are called sparse Fourier transform. This document presents an overview of algorithms of this class and with futher details, the first algorithm that outperforms the FFT in experimental results for some exactly sparse signals. Also, this work presents experiments for determining how sparse image spectra are by using the Parsevel's Theorem. Finaly, the sparse Fourier transform algorithm is used to recover the greatest coefficients of image spectra directly. Keywords: discrete Fourier transform, fast Fourier transform, sparse Fourier transform, digital signal processing.