Como a mudança de imagem de subpixel usando DFT realmente funciona?

12

Estou tentando avaliar a qualidade de vários métodos de interpolação de imagem para um aplicativo que envolve a geração de imagens deslocadas por subpixel. Eu pensei que poderia comparar os resultados de uma mudança de subpixel usando todas essas variantes de interpolação com alguma imagem perfeitamente alterada, mas provavelmente não é possível obtê-la (qual seria a necessidade de interpolação?).

Eu estava pensando em usar o deslocamento DFT + no domínio da frequência e não tenho certeza de como ele realmente funciona em comparação com a interpolação explícita da imagem (usando bilinear, bicúbico, etc.). Tenho certeza de que não é possível gerar uma imagem perfeitamente alterada , mas não posso colocar o dedo nela. O deslocamento de subpixel com DFT é equivalente à aplicação de interpolação e, em caso afirmativo, qual? Qual é o viés dos valores de pixel nas imagens obtidas usando esse método? Obrigado!

EDIT: Depois de refletir sobre o assunto, percebi que, como a FFT é uma aproximação (ainda mais a DFT) da função original em termos de harmônicos (funções senoidais), isso equivaleria a algum tipo de interpolação trigonométrica. Lembro-me de uma fórmula de "interpolação em série de Fourier" para dados discretos, que era uma interpolação trigonométrica, mas não tenho certeza se está conectada.

neuviemeporte
fonte
A transformada rápida de Fourier (FFT) é um algoritmo para a transformação discreta de Fourier. O DFT não é uma aproximação da função original em termos de harmônicos, mas uma projeção de um sinal em uma base ortogonal exponencial complexa.
21713 Bryan
Tudo bem, mas o sinal em si é uma aproximação amostrada e quantizada de alguma distribuição de intensidade, e o DFT é limitado em relação ao conteúdo harmônico em comparação com essa distribuição teórica. Você pode obter o sinal exato de volta da IDFT, mas haverá algum viés se você fizer alguma coisa (como mudar) antes de fazer a IDFT de volta. Ou eu estou esquecendo de alguma coisa?
Neuviemeporte 21/02
O DFT de fato recebe entradas discretizadas, mas não se limita a entradas quantizadas. Qual é o sinal não importa. Como você apontou, você pode receber o sinal exato de volta. No entanto, não tenho certeza do que você quer dizer com "mudança". As propriedades da mudança no domínio da frequência são bem conhecidas (tradução de frequência complexa no domínio do tempo). Se seu desejo é mudar no domínio do "tempo", é necessário pensar no dual DFT disso.
21713 Bryan
1
Quero dizer que, se eu executar alguma operação no DFT de um sinal (como no meu caso - deslocamento de subpixel de uma imagem no "domínio de pixel" usando o teorema do deslocamento de Fourier), o IDFT retornará resultados interpolados, conforme explicado por @ hotpaw2's responda. Essa interpolação é imperfeita porque o sinal não é ilimitado por banda e o próprio DFT foi calculado a partir de um conjunto finito de amostras quantizadas (0-255).
neuviemeporte

Respostas:

4

Um DFT / FFT, mais o preenchimento zero adicionado no domínio da frequência, depois um IDFT / IFFT mais longo, retorna pontos interpolados. Esses pontos serão interpolados usando um kernel Sinc periódico, que é uma interpolação perfeita para dados originais estritamente limitada à banda abaixo da metade da taxa de amostragem original. No entanto, os dados serão acionados como se fossem circularmente, o que pode produzir resultados estranhos nas bordas de algumas imagens. Portanto, convém preencher as bordas da fonte original com um bom preenchimento ou cor de estrutura antes da interpolação.

Se você aumentar o tamanho em 2X (zere o FFT para dobrar o comprimento antes do IFFT), poderá fazer uma troca de meio pixel usando os pontos interpolados. 3X para um terceiro deslocamento de pixel, etc. Para o deslocamento, você pode jogar fora os pontos originais e quaisquer pontos interpolados em excesso para obter o tamanho desejado.

hotpaw2
fonte
5
@ hotpaw2: o núcleo de interpolação para o DFT não é um sinc () de extensão infinita; na verdade, o DFT é uma transformação finita e discreta. A interpolação pela DFT é equivalente à convolução com o kernel do Dirichlet, também chamado de periódico sinc () por alguns autores: en.wikipedia.org/wiki/Dirichlet_kernel
Arrigo
@Arrigo: Concordo. Resposta editada para corrigir.
hotpaw2
@ hotpaw2: quando eu forço o FFT com o dobro do tamanho, o IFFT produzirá uma reconstrução com o dobro do tamanho. Não sabe o que fazer com o excedente? Obrigado
neuviemeporte
Jogue fora os pontos excedentes que você não precisa. Em uma amostra 2X, todas as outras são trocadas, alternando com os pontos originais reconstruídos. Em uma amostra 3X, você obtém 2 pontos alterados (1/3 e 2/3) alternando com os originais. Etc. Quanto mais você exemplo, mais você joga fora.
hotpaw2
7

Existem várias informações importantes que você precisa para entender como a DFT permite que você mude uma imagem.

Primeiro, o teorema de Fourier: provavelmente é mais fácil olhar primeiro para o caso contínuo (isto é, analógico). Imagine que você tem alguma função, chame de g (t). Por uma questão de simplicidade, digamos que g (t) é uma gravação de áudio analógica; portanto, é uma função unidimensional, que é contínua e representa a pressão instantânea em função do tempo.

Agora, g (t) é uma maneira de representar nossa gravação de áudio. Outro é G (f). G (f) é a transformada de Fourier de g (t). Então, G (f) == FT (g (t)). G (f) tem todas as mesmas informações que g (t), mas representa essas informações no domínio da frequência em vez do domínio do tempo. Existem alguns detalhes minuciosos sobre transformadas de Fourier, que não mencionarei.

Você pode pensar em G (f) como a "distribuição de frequências" contida em g (t). Portanto, se g (t) é uma onda senoidal (ou seja, um tom puro), então G (f) será zero em todos os lugares, exceto na frequência desse tom. Este é provavelmente um bom ponto para mencionar que G (f) é em geral uma função complexa - ou seja, retorna números complexos, que podem ser pensados ​​como tendo um componente real e imaginário ou uma magnitude e fase.

δ(W)δ

Ok, agora temos FTs contínuos.

Aqui está o segundo insight: uma transformação discreta de Fourier é uma transformação de Fourier, como um sinal amostrado é um sinal analógico. Nesse caso, o "discreto" refere-se à quantização do domínio da função (tempo ou frequência), não ao alcance. (O sinal digital amostrado que você recebe da placa de som é quantizado no domínio e no alcance.)

O fluxo de bytes digital obtido da placa de som contém "amostras" do sinal contínuo (analógico) original do microfone. Se tomarmos a DFT do nosso g (t) amostrado, ainda obteremos um G (f). G (f), lembre-se, é apenas uma maneira diferente de representar a informação contida em g (t). Se obedecemos ao teorema de Nyquist , o sinal amostrado g (t) contém toda a "inteligência" do sinal contínuo original, portanto nosso G (f) discreto deve conter todas as informações de nosso sinal contínuo original. Entre parênteses, G (f) ainda é uma função complexa.

É aqui que entra a mágica da mudança de sub-pixel, mas, neste caso, vou escrever sobre a mudança do sinal de áudio no tempo em menos de uma amostra, pois é a mesma coisa.

eEuπ2

Isso significa que podemos mudar nossa gravação de áudio no tempo (em qualquer quantidade que escolhermos, incluindo uma fração do tempo de amostra) simplesmente modificando a fase de G (t). Na verdade, essa afirmação é talvez um pouco casual demais. Para um sinal amostrado não quantizado, a fase pode ser ajustada arbitrariamente (isso é parte da razão pela qual fiz a distinção entre quantização de domínio e faixa anteriormente). No entanto, para um sinal amostrado quantizado (nosso fluxo de bytes de áudio, por exemplo), o tamanho da etapa de quantização (ou seja, número de bits) determina a resolução com a qual podemos ajustar a fase. Quando inversamente transformamos a transformada de Fourier G (f) (ou a DIFT para este sinal amostrado), o novo conjunto de amostras g '(t) = DIFT (G (F)) será alterado no tempo pela quantidade que escolhermos.

Aplicar isso aos pixels significa simplesmente usar um FT bidimensional em vez do FT unidimensional discutido aqui.

nick g
fonte