Movendo Média Fft

O cientista e os coordenadores guia para processamento de sinal digital Por Steven W. Smith, Ph. D. Embora a transformada de Fourier seja lenta, ela ainda é a maneira mais rápida de converter uma imagem com um kernel de filtro grande. Por exemplo, a convolução de uma imagem 512 x 512 com uma PSF de 50 x 50 é cerca de 20 vezes mais rápida utilizando a FFT em comparação com a convolução convencional. O Capítulo 18 discute como a convolução FFT funciona para sinais unidimensionais. A versão bidimensional é uma extensão simples. Vamos demonstrar a convolução FFT com um exemplo, um algoritmo para localizar um padrão predeterminado em uma imagem. Suponha que construamos um sistema para inspecionar contas de um dólar, como pode ser usado para impressão de controle de qualidade, detecção de falsificação ou verificação de pagamento em uma máquina de venda automática. Conforme ilustrado na Fig. 24-11, uma imagem 100x100 pixel é adquirida da conta, centrada no retrato de George Washington. O objetivo é pesquisar esta imagem para um padrão conhecido, neste exemplo, a 29 x 29 pixels imagem do rosto. O problema é este: dado uma imagem adquirida e um padrão conhecido, qual é a maneira mais eficaz de localizar onde (ou se) o padrão aparece na imagem Se você prestou atenção no Capítulo 6, você sabe que a solução para este problema é Correlação (um filtro correspondente) e que pode ser implementado usando convolução. Antes de realizar a convolução real, há duas modificações que precisam ser feitas para transformar a imagem alvo em um PSF. Estes estão ilustrados na Fig. 24-12. A figura (a) mostra o sinal alvo, o padrão que estamos tentando detectar. Em (b), a imagem foi girada em 180deg, o mesmo que sendo virado para a esquerda para a direita e, em seguida, virado de cima para baixo. Como discutido no Capítulo 7, ao executar a correlação usando a convolução. O sinal alvo precisa ser revertido para neutralizar a reversão que ocorre durante a convolução. Retornaremos a esta edição em breve. A segunda modificação é um truque para melhorar a eficácia do algoritmo. Ao invés de tentar detectar o rosto na imagem original, é mais eficaz para detectar as bordas da face nas bordas da imagem original. Isso ocorre porque as arestas são mais nítidas do que as características originais, fazendo com que a correlação tenha um pico mais nítido. Esta etapa não é necessária, mas torna os resultados significativamente melhores. Na forma mais simples, é aplicado um filtro de detecção de borda 3x3 tanto à imagem original como ao sinal de destino antes da correlação ser realizada. A partir da propriedade associativa de convolução, isto é o mesmo que aplicar o filtro de detecção de borda ao sinal alvo duas vezes. E deixando a imagem original sozinha. Na prática real, a aplicação do núcleo de detecção de borda 3 x 3 apenas uma vez é geralmente suficiente. Isto é como (b) é transformado em (c) na Fig. 24-12. Isto torna (c) o PSF a ser utilizado na convolução. A Figura 24-13 ilustra os detalhes da convolução de FFT. Neste exemplo, convolveremos a imagem (a) com a imagem (b) para produzir a imagem (c). O fato de que essas imagens foram escolhidas e pré-processadas para implementar a correlação é irrelevante este é um diagrama de fluxo de convolução. O primeiro passo é colocar os dois sinais sendo convolvidos com zeros suficientes para torná-los um poder de dois em tamanho, e grande o suficiente para manter a imagem final. Ou seja, quando imagens de 100 x 100 e 29 x 29 pixels são convolvidas, a imagem resultante será 128 x 128 pixels. Portanto, zeros suficientes devem ser adicionados a (a) e (b) para torná-los cada 128 x 128 pixels de tamanho. Se isso não for feito, ocorre uma convolução circular e a imagem final será distorcida. Se você estiver tendo problemas para entender esses conceitos, volte e analise o Capítulo 18, onde o caso unidimensional é discutido com mais detalhes. O algoritmo FFT é usado para transformar (a) e (b) no domínio da freqüência. Isso resulta em quatro arrays 128 x 128, sendo as partes real e imaginária das duas imagens sendo convolvidas. Multiplicando as partes real e imaginária de (a) com as partes real e imaginária de (b), gera as partes real e imaginária de (c). (Se você precisar ser lembrado como isso é feito, veja a Eq. 9-1). Tomando a FFT Inversa completa o algoritmo produzindo a imagem final convolvida. O valor de cada pixel em uma imagem de correlação é uma medida de quão bem a imagem de destino corresponde à imagem pesquisada nesse ponto. Neste exemplo particular, a imagem de correlação em (c) é composta por ruído mais um único pico brilhante, indicando uma boa correspondência ao sinal alvo. Simplesmente localizar o pixel mais brilhante nesta imagem especificaria as coordenadas detectadas da face. Se não tivéssemos usado a modificação de detecção de borda no sinal alvo, o pico ainda estaria presente, mas muito menos distinto. Embora a correlação seja uma ferramenta poderosa no processamento de imagem, ela sofre de uma limitação significativa: a imagem de destino deve ter exatamente o mesmo tamanho e orientação rotacional que a área correspondente na imagem pesquisada. Ruído e outras variações na amplitude de cada pixel são relativamente sem importância, mas uma correspondência espacial exata é crítica. Por exemplo, isso torna o método quase inútil para encontrar tanques inimigos em fotos de reconhecimento militar, tumores em imagens médicas e revólveres em varreduras de bagagens nos aeroportos. Uma abordagem consiste em correlacionar a imagem várias vezes com uma variedade de formas e rotações da imagem alvo. Isso funciona em princípio, mas o tempo de execução vai fazer você perder interesse em uma pressa. O cientista e engenheiros guia para processamento de sinal digital Por Steven W. Smith, Ph. D. Como a FFT funciona A FFT é um algoritmo complicado, e seus detalhes são geralmente deixados para aqueles que se especializam em tais coisas. Esta seção descreve o funcionamento geral da FFT, mas contorna uma questão-chave: o uso de números complexos. Se você tem um fundo em matemática complexa, você pode ler entre as linhas para entender a verdadeira natureza do algoritmo. Não se preocupe se os detalhes elude você poucos cientistas e engenheiros que usam a FFT poderia escrever o programa a partir do zero. Na notação complexa, os domínios tempo e frequência contêm cada um sinal composto por N pontos complexos. Cada um desses pontos complexos é composto de dois números, a parte real ea parte imaginária. Por exemplo, quando falamos da amostra complexa X 42, ela se refere à combinação de ReX 42 e ImX 42. Em outras palavras, cada variável complexa contém dois números. Quando duas variáveis ​​complexas são multiplicadas, os quatro componentes individuais devem ser combinados para formar os dois componentes do produto (como na Eq. 9-1). A discussão a seguir sobre Como a FFT funciona usa esse jargão de notação complexa. Ou seja, os termos singulares: sinal, ponto, amostra. E valor. Referem-se à combinação da parte real e da parte imaginária. A FFT opera por decomposição de um sinal de domínio de tempo de N pontos em N sinais de domínio de tempo cada composto por um único ponto. O segundo passo é calcular os N espectros de frequência correspondentes a estes N sinais de domínio de tempo. Por fim, os espectros de N são sintetizados num único espectro de frequência. A Figura 12-2 mostra um exemplo da decomposição no domínio do tempo usada na FFT. Neste exemplo, um sinal de 16 pontos é decomposto através de quatro fases separadas. A primeira etapa quebra o sinal de 16 pontos em dois sinais cada um consistindo de 8 pontos. A segunda etapa decompõe os dados em quatro sinais de 4 pontos. Este padrão continua até haver N sinais compostos por um único ponto. Uma decomposição entrelaçada é usada cada vez que um sinal é quebrado em dois, isto é, o sinal é separado em suas amostras pares e ímpares. A melhor maneira de entender isto é inspecionando a Fig. 12-2 até entender o padrão. Para esta decomposição são necessários dois estágios Log 2, isto é, um sinal de 16 pontos (2 4) requer 4 estágios, um sinal de 512 pontos (2 7) requer 7 estágios, um sinal de 4096 pontos (12) requer 12 estágios, etc. Lembre-se deste valor, Log 2 N será referenciado muitas vezes neste capítulo. Agora que você compreende a estrutura da decomposição, ela pode ser bastante simplificada. A decomposição não é mais do que uma reordenação das amostras no sinal. A Figura 12-3 mostra o padrão de rearranjo necessário. À esquerda, os números de amostra do sinal original são listados junto com seus equivalentes binários. À direita, os números de amostra rearranjados são listados, também junto com seus equivalentes binários. A idéia importante é que os números binários são as reversões uns dos outros. Por exemplo, a amostra 3 (0011) é trocada com o número de amostra 12 (1100). Da mesma forma, a amostra número 14 (1110) é trocada com o número de amostra 7 (0111), e assim por diante. A decomposição do domínio tempo FFT é geralmente realizada por um algoritmo de triagem de reversão de bits. Isso envolve reorganizar a ordem das N amostras de domínio de tempo contando em binário com os bits invertidos para a esquerda para a direita (como na coluna da extrema direita na Figura 12-3). O próximo passo no algoritmo FFT é encontrar os espectros de freqüência dos sinais de domínio de 1 ponto. Nada poderia ser mais fácil o espectro de freqüência de um sinal de 1 ponto é igual a si mesmo. Isso significa que nada é necessário para fazer essa etapa. Embora não haja trabalho envolvido, não se esqueça que cada um dos sinais de 1 ponto é agora um espectro de freqüência, e não um sinal de domínio do tempo. O último passo na FFT é combinar os espectros de freqüência N na ordem inversa exata que a decomposição do domínio do tempo ocorreu. Este é o lugar onde o algoritmo fica confuso. Infelizmente, o atalho de reversão de bits não é aplicável, e devemos voltar uma etapa de cada vez. Na primeira fase, 16 espectros de frequência (1 ponto cada) são sintetizados em 8 espectros de frequência (2 pontos cada). Na segunda fase, os 8 espectros de freqüência (2 pontos cada) são sintetizados em 4 espectros de freqüência (4 pontos cada), e assim por diante. A última etapa resulta na saída da FFT, um espectro de freqüência de 16 pontos. A Figura 12-4 mostra como dois espectros de freqüência, cada um composto de 4 pontos, são combinados em um único espectro de freqüência de 8 pontos. Esta síntese deve desfazer a decomposição entrelaçada feita no domínio do tempo. Por outras palavras, a operação do domínio da frequência deve corresponder ao procedimento do domínio do tempo de combinar dois sinais de 4 pontos por entrelaçamento. Considere dois sinais de domínio de tempo, abcd e efgh. Um sinal de domínio temporal de 8 pontos pode ser formado por dois passos: diluir cada sinal de 4 pontos com zeros para torná-lo um sinal de 8 pontos e, em seguida, adicionar os sinais em conjunto. Ou seja, abcd torna-se a0b0c0d0. E efgh se torna 0e0f0g0h. Adicionando estes dois sinais de 8 pontos produz aebfggdh. Conforme ilustrado na Fig. 12-4, a diluição do domínio do tempo com zeros corresponde a uma duplicação do espectro de frequência. Portanto, os espectros de freqüência são combinados na FFT duplicando-os e, em seguida, adicionando os espectros duplicados juntos. Para se igualar quando adicionado, os dois sinais de domínio de tempo são diluídos com zeros de uma maneira ligeiramente diferente. Em um sinal, os pontos ímpares são zero, enquanto que no outro sinal, os pontos pares são zero. Em outras palavras, um dos sinais de domínio de tempo (0e0f0g0h na Fig. 12-4) é deslocado para a direita por uma amostra. Esta mudança no domínio do tempo corresponde à multiplicação do espectro por uma sinusoide. Para ver isso, lembre-se que uma mudança no domínio do tempo é equivalente a convolver o sinal com uma função delta deslocada. Isto multiplica o espectro de sinais com o espectro da função delta deslocada. O espectro de uma função delta deslocada é uma sinusóide (ver Fig 11-2). A Figura 12-5 mostra um diagrama de fluxo para combinar dois espectros de 4 pontos em um único espectro de 8 pontos. Para reduzir ainda mais a situação, observe que a Fig. 12-5 é formado a partir do padrão básico na Fig. 12-6 repetido uma e outra vez. Este diagrama de fluxo simples é chamado de borboleta devido à sua aparência alada. A borboleta é o elemento computacional básico da FFT, transformando dois pontos complexos em dois outros pontos complexos. A Figura 12-7 mostra a estrutura de toda a FFT. A decomposição do domínio do tempo é realizada com um algoritmo de ordenação de reversão de bits. Transformar os dados decompostos no domínio da frequência não envolve nada e, portanto, não aparece na figura. A síntese do domínio da frequência requer três ciclos. O circuito externo passa através dos estádios Log 2 N (isto é, cada nível na Fig. 12-2, partindo do fundo e movendo-se para cima). O laço médio move-se através de cada um dos espectros de frequência individuais no estádio em que é trabalhado (isto é, cada uma das caixas num qualquer nível na Fig. 12-2). O loop mais interno utiliza a borboleta para calcular os pontos em cada espectro de frequência (isto é, fazendo um loop através das amostras dentro de qualquer caixa na Fig. 12-2). As caixas de sobrecarga na Fig. 12-7 determinar os índices de início e término para os loops, bem como calcular os sinusóides necessários nas borboletas. Agora chegamos ao coração deste capítulo, os programas FFT reais. Tenho um sinal de trinta segundos de voz que foi amostrado em 44,1 kHz. Agora, eu gostaria de mostrar quais freqüências o discurso tem. No entanto, não tenho certeza qual seria a melhor maneira de fazer isso. Parece que às vezes se calcula o valor absoluto de uma transformada de Fourier, e às vezes a densidade espectral de potência. Se eu entendo corretamente, este último funciona para que eu dividir o meu sinal em partes, fazer FFT part-by-part e de alguma forma sum estes. As funções de janela estão de alguma forma envolvidas. Você pode esclarecer isso um pouco para mim Im novo para DSP. Pediu Jul 25 13 at 16:30 Agora, eu gostaria de mostrar quais as freqüências do discurso tem. No entanto, não tenho certeza qual seria a melhor maneira de fazer isso. Parece que às vezes se calcula o valor absoluto de uma transformada de Fourier, e às vezes a densidade espectral de potência. Se você quiser anexar o significado físico à sua análise, então vá com a densidade espectral de potência, (PSD). Isso ocorre porque isso simplesmente lhe dará o poder de seu sinal, em cada banda de freqüência. Por outro lado, se você não quer se preocupar com um significado físico, mas quer saber como as amplitudes fourier de cada banda variam em relação um ao outro, você pode manter a magnitude absoluta. Na prática, você pode calcular o PSD como simplesmente a magnitude absoluta da transformada fourier ao quadrado. Por exemplo, se seu sinal é xn, e seu DFT for X (f), então a magnitude absoluta do DFT é X (f), enquanto que o PSD é X (f) 2. Se eu entendo corretamente, este último funciona para que eu dividir o meu sinal em partes, fazer FFT part-by-part e de alguma forma sum estes. As funções de janela estão de alguma forma envolvidas. Você pode esclarecer isso um pouco para mim Im novo para DSP. Não, isto não é verdade. O que você está falando aqui refere-se à Transformada de Fourier de Tempo Curto. (STFT). Isto é simplesmente cortar o seu sinal de domínio do tempo, widowing-lo e, em seguida, tendo o forno trnasform. No final do dia, porém, você ainda terá uma matriz complexa. Se você escolher tomar sua magnitude absoluta, você terá uma matriz de transformada de fourier de magnitude absoluta. Se você tomar sua magnitude absoluta ao quadrado, você terá uma matriz de densidade espectral de potência. Respondeu Jul 25 13 at 17:28