Método mais rápido para calcular a convolução

Question

Eu tenho que aplicar um filtro de convolução em cada linha de muitas imagens. O clássico são 360 imagens de 1024x1024 pixels. No meu caso de uso, são 720 imagens 560x600 pixels.

O problema é que meu código é muito mais lento do que o anunciado nos artigos.

Eu implementei a ingênua convolução e leva 2m 30s. Em seguida, mudei para FFT usando FFTW. Usei o complexo complexo 2, filtrando duas linhas em cada transformação. Agora tenho cerca de 20 anos.

O fato é que os artigos anunciam cerca de 10s e menos ainda para a condição clássica. Então, eu gostaria de perguntar aos especialistas aqui se poderia haver uma maneira mais rápida de calcular a convolução.

Receitas numéricas sugerem evitar a classificação feita na DFT e adaptar a função do filtro de domínio de frequência de acordo. Mas não há um exemplo de código como isso pode ser feito.

Talvez eu perca tempo na cópia de dados. Com o REAL 2 Real Transform, eu não precisaria copiar os dados nos valores complexos. Mas eu tenho que fazer com que 0 de qualquer maneira.

EDIT: Veja minha própria resposta abaixo para obter feedback do progresso e mais informações sobre como resolver esse problema.

Pergunta (reformulação precisa):

Estou procurando um algoritmo ou peça de código para aplicar uma convolução muito rápida a uma função não periódica discreta (512 a 2048 valores). Aparentemente, a transformação discreta de Fourier é o caminho a percorrer. No entanto, gostaria de evitar a cópia e a conversão de dados para o complexo e evitar a reordenação da borboleta.

Answer 1

A FFT é a técnica mais rápida conhecida por convidar sinais, e a FFTW é a biblioteca gratuita mais rápida disponível para calcular a FFT.

A chave para você obter o máximo desempenho (fora do hardware ... A GPU é uma boa sugestão) será preencher seus sinais com um poder de dois. Ao usar o FFTW, use a configuração do 'paciente' ao criar seu plano para obter o melhor desempenho. É altamente improvável que você role manualmente uma implementação mais rápida do que o que o FFTW fornece (esqueça o NR). Também use a versão real da FFT 1D e não a versão complexa; e use apenas precisão única (ponto flutuante), se puder.

Se a FFTW não estiver cortando isso para você, eu olharia para a biblioteca IPP da Intel (muito acessível). Os processadores de FFTs ajustados à mão para Intel que foram otimizados para imagens com várias profundidades de bits.

Paulo
Centerspace Programas

Answer 2

Você pode querer adicionar processamento de imagem como uma tag.

Porém, este artigo pode ser de interesse, especialmente com a suposição de que a imagem é uma potência ou 2. Você também pode ver onde eles otimizam a FFT. Espero que os artigos que você esteja analisando fizessem algumas suposições e depois otimizassem as equações para elas.

http://www.gamasutra.com/view/feature/3993/sponsored_feature_implementation_.php

Se você quiser ir mais rápido, pode usar a GPU para realmente fazer o trabalho.

Este livro pode ser útil para você, se você for com a GPU:http://www.springerlink.com/content/kd6qm361pq8mmlx2/

Answer 3

Esta resposta é para coletar feedback do Relatório de Progresso sobre esse problema.

Editar 11 de outubro:

O tempo de execução que medi não reflete o tempo efetivo da FFT. Percebi que, quando meu programa termina, a CPU ainda está ocupada no tempo do sistema até 42% por 10s. Quando espero até que a CPU esteja de volta a 0%, antes de reiniciar meu programa, recebo o tempo de execução de 15.35s que vem do processamento da GPU. Recebo o mesmo tempo se comentar a filtragem da FFT.

Portanto, a FFT é de fato atualmente mais rápida que a GPU e foi simplesmente prejudicada por uma tarefa do sistema concorrente. Ainda não sei qual é essa tarefa do sistema. Suspeito que isso resulta da alocação de um enorme bloco de heap, onde copio o resultado do processamento antes de gravá -lo no disco. Para os dados de entrada, uso um mapa de memória.

Agora vou alterar meu código para obter uma medição precisa do tempo de processamento da FFT. Torná -lo mais rápido ainda é uma realidade, porque há espaço para otimizar o processamento da GPU, como, por exemplo, pintando a transferência de dados para o processo.