Bagaimana pengalihan gambar subpixel menggunakan DFT benar-benar berfungsi?

12

Saya mencoba untuk menilai kualitas beberapa metode interpolasi gambar untuk aplikasi yang melibatkan menghasilkan gambar yang dialihkan subpiksel. Saya pikir saya bisa membandingkan hasil pergeseran subpixel menggunakan semua varian interpolasi ini dengan beberapa gambar yang bergeser sempurna, tetapi mungkin tidak mungkin untuk mendapatkannya (apa yang akan dibutuhkan untuk interpolasi kemudian?).

Saya sedang berpikir tentang menggunakan pergeseran DFT + dalam domain frekuensi, dan saya tidak yakin bagaimana cara kerjanya dibandingkan dengan secara eksplisit menginterpolasi gambar (menggunakan bilinear, bicubic, dll ...). Saya yakin itu tidak mungkin menghasilkan gambar yang bergeser sempurna , tapi saya tidak bisa meletakkan jari saya di atasnya. Apakah perpindahan subpiksel dengan DFT setara dengan penerapan interpolasi dan jika demikian, yang mana? Apa bias dari nilai piksel dalam gambar yang diperoleh menggunakan metode ini? Terima kasih!

EDIT: Setelah memikirkan masalah ini, saya pikir karena FFT adalah perkiraan (bahkan lebih DFT) dari fungsi asli dalam hal harmonik (fungsi sinus), bahwa itu akan menjadi semacam interpolasi trigonometri. Saya ingat formula "Fourier series interpolasi" untuk data diskrit yang merupakan interpolasi trigonometri, tetapi tidak yakin apakah itu terhubung.

image-processing dft interpolation neuviemeporte
sumber
Transformasi Fourier cepat (FFT) adalah algoritma untuk transformasi Fourier diskrit. DFT bukan merupakan perkiraan dari fungsi asli dalam hal harmonik, melainkan proyeksi dari sinyal ke basis ortogonal eksponensial yang kompleks.
Bryan
Oke, tetapi sinyal itu sendiri adalah perkiraan sampel dan terkuantisasi dari beberapa distribusi intensitas, dan DFT terbatas sehubungan dengan konten harmonik dibandingkan dengan distribusi teoritis. Anda bisa mendapatkan sinyal yang tepat kembali dari IDFT, tetapi akan ada beberapa bias jika Anda melakukan hal-hal (seperti bergeser) sebelum IDFTing kembali. Atau apakah saya melewatkan sesuatu?
neuviemeporte
DFT memang mengambil input yang diskrit, tetapi tidak terbatas pada input yang dikuantifikasi. Apa sinyal itu tidak masalah. Seperti yang telah Anda tunjukkan, Anda bisa mendapatkan sinyal yang tepat kembali. Namun, saya tidak yakin apa yang Anda maksud dengan "bergeser". Properti pergeseran dalam domain frekuensi sudah terkenal (terjemahan frekuensi kompleks dalam domain waktu). Jika keinginan Anda adalah untuk bergeser dalam domain "waktu", maka Anda perlu memikirkan tentang DFT ganda dari itu.
Bryan
1
Maksud saya, jika saya melakukan beberapa operasi pada DFT sinyal (seperti dalam kasus saya - pergeseran subpiksel gambar dalam "domain piksel" menggunakan teorema pergeseran Fourier), bahwa IDFT akan mengembalikan hasil yang diinterpolasi seperti dijelaskan oleh @ hotpaw2's menjawab. Interpolasi ini tidak sempurna karena sinyalnya tidak terbatas dan DFT itu sendiri dihitung dari sejumlah terbatas sampel terkuantisasi (0-255).
neuviemeporte

Jawaban:

4

DFT / FFT, ditambah menambahkan zero-padding dalam domain frekuensi, kemudian IDFT / IFFT yang lebih panjang, mengembalikan poin yang diinterpolasi. Poin-poin ini akan diinterpolasi menggunakan kernel Sinc periodik, yang merupakan interpolasi sempurna untuk data asli yang terbatas pada band di bawah setengah dari laju sampel asli. Namun, data akan ditindaklanjuti seolah-olah dibungkus melingkar, yang dapat menghasilkan hasil aneh di tepi beberapa gambar. Jadi, Anda mungkin ingin mengisi tepi sumber asli dengan pengisi warna yang bagus atau warna sebelum interpolasi.

Jika Anda melakukan upample dengan 2X (nol-pad FFT untuk menggandakan panjang sebelum IFFT), maka Anda dapat melakukan pergeseran setengah-pixel menggunakan titik interpolasi. 3X untuk pergeseran piksel ketiga, dll. Untuk pemindahan, Anda dapat membuang poin asli ditambah kelebihan titik interpolasi untuk mendapatkan ukuran yang diinginkan.

hotpaw2
sumber
5
@ hotpaw2: kernel interpolasi untuk DFT bukan sinc () dari batas tak terbatas, pada kenyataannya DFT adalah diskrit, transformasi terbatas. Interpolasi oleh DFT setara dengan konvolusi dengan kernel Dirichlet, juga disebut periodic sinc () oleh beberapa penulis: en.wikipedia.org/wiki/Dirichlet_kernel
Arrigo
@ Arrigo: Setuju. Jawaban yang diedit untuk diperbaiki.
hotpaw2
@ hotpaw2: ketika saya mengisi FFT dua kali ukuran, IFFT akan menghasilkan rekonstruksi dua kali ukuran. Tidak yakin apa yang harus dilakukan dengan surplus? Terima kasih
neuviemeporte
Buang kelebihan poin yang tidak Anda butuhkan. Dalam 2X upample, setiap yang lain digeser, bergantian dengan poin asli yang direkonstruksi. Dalam 3X upample, Anda mendapatkan 2 poin bergeser (1/3 dan 2/3) bergantian dengan aslinya. Dll. Semakin Anda upsample, semakin banyak Anda membuang.
hotpaw2
7

Ada beberapa wawasan utama yang Anda butuhkan untuk memahami bagaimana DFT memungkinkan Anda untuk menggeser gambar.

Pertama, teorema Fourier: Mungkin lebih mudah untuk melihat kasus kontinu (yaitu analog) terlebih dahulu. Bayangkan Anda memiliki beberapa fungsi, sebut saja g (t). Untuk kesederhanaan, katakanlah g (t) adalah rekaman audio analog, jadi ini adalah fungsi satu dimensi, yang kontinu, dan mewakili tekanan sesaat sebagai fungsi waktu.

Sekarang, g (t) adalah salah satu cara kita dapat mewakili rekaman audio kita. Lainnya adalah G (f). G (f) adalah transformasi Fourier dari g (t). Jadi, G (f) == FT (g (t)). G (f) memiliki semua informasi yang sama dengan g (t), tetapi mewakili informasi itu dalam domain frekuensi alih-alih domain waktu. Ada beberapa detail pemilih tentang Fourier Transforms, yang tidak akan saya sebutkan.

Anda dapat menganggap G (f) sebagai "distribusi frekuensi" yang terkandung dalam g (t). Jadi, jika g (t) adalah gelombang sinus (yaitu, nada murni), maka G (f) akan nol di mana-mana, kecuali pada frekuensi nada itu. Ini mungkin poin yang baik untuk menyebutkan bahwa G (f) secara umum adalah fungsi yang kompleks - yaitu mengatakan bahwa ia mengembalikan bilangan kompleks, yang dapat dianggap memiliki komponen nyata dan imajiner atau besaran dan fase.

δ(w)δ

Ok, jadi sekarang kita punya FT kontinu di bawah ikat pinggang kita.

Inilah wawasan kedua: Transformasi Fourier Diskrit adalah Transformasi Fourier sebagai sinyal sampel ke sinyal analog. Dalam hal ini, "diskrit" mengacu pada kuantisasi domain fungsi (waktu atau frekuensi), bukan jangkauannya. (Sinyal digital sampel yang Anda dapatkan dari kartu suara Anda diukur dalam domain dan rentang.)

Digital byte-stream yang Anda dapatkan dari kartu suara Anda berisi "sampel" dari sinyal kontinyu (analog) asli dari mikrofon. Jika kita mengambil DFT dari sampel g (t) kita, kita masih mendapatkan G (f). G (f), ingat, hanyalah cara berbeda untuk merepresentasikan informasi yang terkandung dalam g (t). Jika kita mematuhi teorema Nyquist , sinyal sampel g (t) berisi semua "kecerdasan" dari sinyal kontinu asli, sehingga diskrit G (f) kita harus berisi semua informasi dari sinyal kontinyu asli kita. Secara parentetis, G (f) masih merupakan fungsi yang kompleks.

Di sinilah keajaiban pergeseran sub-pixel masuk, tetapi dalam kasus ini saya akan menulis tentang menggeser sinyal audio dalam waktu kurang dari sampel, karena itu adalah hal yang sama.

eiπ2

Itu berarti kita dapat menggeser rekaman audio kita dalam waktu (dengan jumlah berapa pun yang kita pilih, termasuk sebagian kecil dari waktu sampel) hanya dengan memodifikasi fase G (t). Sebenarnya, pernyataan itu mungkin agak terlalu santai. Untuk sinyal sampel yang tidak dikuantisasi, fase dapat disesuaikan secara sewenang-wenang (ini adalah bagian dari alasan saya membuat perbedaan antara kuantisasi domain dan rentang sebelumnya). Namun, untuk sinyal sampel terkuantisasi (byte-stream audio kami, misalnya) ukuran langkah kuantisasi (yaitu, jumlah bit) menentukan resolusi yang dengannya kami dapat menyesuaikan fase. Ketika kita Inverse Fourier Transform G (f) (atau DIFT itu, untuk sinyal sampel ini), set sampel baru g '(t) = DIFT (G (F)) semua akan digeser dalam waktu dengan jumlah yang kita pilih.

Menerapkan ini ke piksel Anda berarti menggunakan FT 2 dimensi, bukan FT 1 dimensi yang dibahas di sini.

nick g
sumber