Usando o IOS Accelerate Framework para processamento de sinal 2D em imagens sem potência de dois?

Question

//EDITAR...

Estou editando um pouco minha pergunta para abordar a questão de trabalhar especificamente com imagens sem potência de dois.Eu tenho uma estrutura básica que funciona com imagens quadradas em tons de cinza com tamanhos como 256x256 ou 1024x1024, mas não consigo ver como generalizar para imagens de tamanhos arbitrários.As funções fft parecem querer que você inclua o log2 da largura e altura, mas não está claro como descompactar os dados resultantes ou se os dados não estão apenas sendo embaralhados.Suponho que a coisa óbvia a fazer seria centralizar a imagem npot em uma imagem maior, toda preta, e então ignorar quaisquer valores nessas posições ao observar os dados.Mas estou me perguntando se existe uma maneira menos complicada de trabalhar com dados npot.

//...TERMINAR EDIÇÃO

Estou tendo alguns problemas com a documentação do Accelerate Framework.Eu normalmente usaria o FFTW3, mas estou tendo problemas para compilar isso em um dispositivo IOS real (veja isto pergunta).Alguém pode me indicar uma implementação super simples usando Accelerate que faça algo como o seguinte:

1) Transforma os dados da imagem em uma estrutura de dados apropriada que pode ser passada para os métodos FFT do Accelerate.
No FFTW3, na sua forma mais simples, usando uma imagem em tons de cinza, isso envolve colocar os bytes não assinados em um array "fftw_complex", que é simplesmente uma estrutura de dois floats, um contendo o valor real e o outro o imaginário (e onde o imaginário é inicializado em zero para cada pixel).

2) Pega essa estrutura de dados e executa uma FFT nela.

3) Imprime a magnitude e a fase.

4) Executa um IFFT nele.

5) Recria a imagem original a partir dos dados resultantes do IFFT.

Embora este seja um exemplo muito básico, estou tendo problemas para usar a documentação do site da Apple.O então responda por Pi aqui é muito útil, mas ainda estou um pouco confuso sobre como usar o Accelerate para executar essa funcionalidade básica usando uma imagem 2D em escala de cinza (ou colorida).

De qualquer forma, qualquer indicação ou especialmente algum código simples de trabalho que processe uma imagem 2D seria extremamente útil!

\\\ EDITAR \\\

Ok, depois de dedicar algum tempo para mergulhar na documentação e em alguns códigos muito úteis no SO e também no repositório github do pkmital, tenho um código funcional que pensei em postar porque 1) demorei um pouco para descobrir e 2) porque ainda tenho algumas perguntas restantes...

Inicialize o "plano" FFT.Assumindo uma imagem quadrada de potência de dois:

#include <Accelerate/Accelerate.h>
...
UInt32 N = log2(length*length);
UInt32 log2nr = N / 2; 
UInt32 log2nc = N / 2;
UInt32 numElements = 1 << ( log2nr + log2nc );
float SCALE = 1.0/numElements;
SInt32 rowStride = 1; 
SInt32 columnStride = 0;
FFTSetup setup = create_fftsetup(MAX(log2nr, log2nc), FFT_RADIX2);

Passe uma matriz de bytes para uma imagem quadrada em escala de cinza com potência de dois e transforme-a em COMPLEX_SPLIT:

COMPLEX_SPLIT in_fft;
in_fft.realp = ( float* ) malloc ( numElements * sizeof ( float ) );
in_fft.imagp = ( float* ) malloc ( numElements * sizeof ( float ) );

for ( UInt32 i = 0; i < numElements; i++ ) {
    if (i < t->width * t->height) {
      in_fft.realp[i] = t->data[i] / 255.0;
      in_fft.imagp[i] = 0.0;
    }
}

Execute a FFT nos dados da imagem transformada e, em seguida, obtenha a magnitude e a fase:

COMPLEX_SPLIT out_fft;
out_fft.realp = ( float* ) malloc ( numElements * sizeof ( float ) );
out_fft.imagp = ( float* ) malloc ( numElements * sizeof ( float ) );

fft2d_zop ( setup, &in_fft, rowStride, columnStride, &out_fft, rowStride, columnStride, log2nc, log2nr, FFT_FORWARD );

magnitude = (float *) malloc(numElements * sizeof(float));
phase = (float *) malloc(numElements * sizeof(float));

for (int i = 0; i < numElements; i++) {
   magnitude[i] = sqrt(out_fft.realp[i] * out_fft.realp[i] + out_fft.imagp[i] * out_fft.imagp[i]) ;
   phase[i] = atan2(out_fft.imagp[i],out_fft.realp[i]);
}

Agora você pode executar um IFFT nos dados out_fft para obter a imagem original...

COMPLEX_SPLIT out_ifft;
out_ifft.realp = ( float* ) malloc ( numElements * sizeof ( float ) );
out_ifft.imagp = ( float* ) malloc ( numElements * sizeof ( float ) );
fft2d_zop (setup, &out_fft, rowStride, columnStride, &out_ifft, rowStride, columnStride, log2nc, log2nr, FFT_INVERSE);   

vsmul( out_ifft.realp, 1, SCALE, out_ifft.realp, 1, numElements );
vsmul( out_ifft.imagp, 1, SCALE, out_ifft.imagp, 1, numElements );

Ou você pode executar um IFFT na magnitude para obter uma autocorrelação...

COMPLEX_SPLIT in_ifft;
in_ifft.realp = ( float* ) malloc ( numElements * sizeof ( float ) );
in_ifft.imagp = ( float* ) malloc ( numElements * sizeof ( float ) );
for (int i = 0; i < numElements; i++) {
  in_ifft.realp[i] = (magnitude[i]);
  in_ifft.imagp[i] = 0.0;
}

fft2d_zop ( setup, &in_fft, rowStride, columnStride, &out_ifft, rowStride, columnStride, log2nc, log2nr, FFT_INVERSE );      

vsmul( out_ifft.realp, 1, SCALE, out_ifft.realp, 1, numElements );
vsmul( out_ifft.imagp, 1, SCALE, out_ifft.imagp, 1, numElements );

Finalmente, você pode colocar os resultados do ift de volta em uma matriz de imagens:

for ( UInt32 i = 0; i < numElements; i++ ) {
  t->data[i] = (int) (out_ifft.realp[i] * 255.0);
}     

Ainda não descobri como usar a estrutura Accelerate para lidar com imagens sem potência de dois.Se eu alocar memória suficiente na configuração, poderei fazer uma FFT, seguida de uma IFFT para obter minha imagem original.Mas se tentar fazer uma autocorrelação (com a magnitude da FFT), minha imagem obterá resultados instáveis.Não tenho certeza da melhor maneira de preencher a imagem adequadamente, então espero que alguém tenha uma ideia de como fazer isso.(Ou compartilhe uma versão funcional do método vDSP_conv!)

Answer 1

Eu diria que, para realizar trabalhos em tamanhos de imagem arbitrários, tudo o que você precisa fazer é dimensionar sua matriz de valores de entrada adequadamente para a próxima potência de 2.

A parte difícil é onde colocar os dados da imagem original e com o que preencher.O que você realmente está tentando fazer com a imagem ou com a extração de dados da imagem é crucial.

No PDF vinculado abaixo, preste atenção especial ao parágrafo logo acima de 12.4.2http://www.mathcs.org/java/programs/FFT/FFTInfo/c12-4.pdf

Embora o texto acima fale sobre a manipulação ao longo de 2 eixos, poderíamos potencialmente realizar uma ideia semelhante antes da segunda dimensão e seguindo para a segunda dimensão.Se eu estiver correto, então este exemplo pode ser aplicado (e este ainda não é um algoritmo exato):

digamos que temos uma imagem de 900 por 900:primeiro poderíamos dividir a imagem em faixas verticais de 512, 256, 128 e 4.Processaríamos então 4 FFTs 1D para cada linha, um para os primeiros 512 pixels, o próximo para os 256 pixels seguintes, o próximo para os 128 seguintes e o último para os 4 restantes.Como a saída da FFT é essencialmente a popularidade da frequência, elas poderiam simplesmente ser adicionadas (SOMENTE da perspectiva da frequência, não do deslocamento angular).Poderíamos então levar esta mesma técnica para a 2ª dimensão.Neste ponto, teríamos levado em consideração cada pixel de entrada sem precisar preencher.

Isso é realmente apenas um alimento para reflexão. Eu não tentei isso sozinho e, na verdade, deveria pesquisar isso sozinho.Se você está realmente fazendo esse tipo de trabalho agora, talvez tenha mais tempo do que eu neste momento.