Bagaimana seseorang menerapkan FFT dengan benar dalam denoising gambar

Saya sedang menulis program (Qt widgets / c ++) untuk menghilangkan noise dari gambar. Sebagai metode denoising, saya memilih metode non lokal berarti . Metode ini memiliki kualitas luar biasa dari gambar yang dipulihkan (itu sebabnya itu satu-satunya metode denoising di OpenCV), tetapi memiliki biaya perhitungan yang besar , jadi saya membuat banyak varian modifikasi dari metode ini (beberapa dengan multithreading, beberapa algoritmik). Tapi, saya mengalami masalah dengan yang satu, melibatkan FFT

Saya mengikuti semua langkah artikel ini (hanya satu halaman, 1430) dan semua berfungsi dengan baik, kecuali untuk bagian FFT, hanya ada 2 baris tentang hal itu di koran dan saya tidak bisa mengerti, BAGAIMANA harus menggunakan fft

Masalah ini telah mengganggu saya selama berbulan-bulan, bantuan atau wawasan apa pun akan sangat appriciated.

Versi pertanyaan yang singkat: Bagaimana saya bisa mendapatkan perbedaan kuadrat terangkum dari dua array pada gambar (satu di atas dan satu di tengah, nilai adalah warna) dengan cepat? (O (n ^ 2) adalah biaya besar, ada banyak jenis operasi ini, kertas di atas menyatakan, bahwa hal itu dapat dilakukan melalui FFT dengan O (n * log n) (mengatakan bahwa 2 array ini entah bagaimana membentuk lilitan melingkar melingkar) )

Trik di dalam kertas adalah sebagai berikut:

1. Apa yang ingin Anda hitung adalah , di mana adalah gambar, dan dua piksel berisik dan adalah offset 2D digunakan untuk mendefinisikan suatu tambalan.$\sum_{i \in W} |I(x+i)-I(y+i)|^2$$I$$x$$y$$i$
2. Memperluas ekspresi yang dihasilkan: .$\sum_i I^2(x+i) + \sum_i I^2(y+i) - 2 \sum_i I(x+i)I(y+i) = A + B - 2C$
3. $A$ dan dihitung menggunakan gambar integral kuadrat, yaitu, gambar integral dari gambar asli kuadrat.$B$
4. $C$ adalah konvolusi antara dua tambalan yang berpusat pada dan . Dengan demikian, itu dapat dihitung dalam domain Fourier, di mana ia menjadi perkalian. Anda mendapatkan nilai dengan menghitung transformasi Fourier dari tambalan di sekitar , tambalan di sekitar , mengalikan hasil ini secara pointwise dan mengambil transformasi Fourier terbalik dari hasil multplikasi.$x$$y$$C$$x$$y$

Transformasi Fourier jelas merupakan transformasi 2D karena Anda bekerja dengan data 2D. Apa yang Anda peroleh untuk tambalan tertentu adalah array 2D nilai-nilai kompleks.

Catatan tambahan

Menurut pendapat saya, artikel ini bukan strategi speedup NL-means terbaik. Eksperimen yang saya lakukan pada 2007/2008 menunjukkan bahwa pra-pemilihan tambalan lebih baik (baik dari segi kecepatan dan kualitas hasil). Saya sudah mulai menulis blog tentang ini di sini , tetapi sayangnya saya mencari waktu untuk menyelesaikan posting.

Makalah NL-means asli menyebutkan implementasi blockwise yang bisa menarik. Ada 2 cara mendasar dalam mengimplementasikan NL-means:

1. menulis lingkaran denoising untuk setiap piksel dalam gambar
2. menulis lingkaran denoising untuk setiap patch, kemudian memproyeksikan kembali patch untuk membentuk gambar.

Impolementasi pertama adalah pendekatan asli, karena pada tahun 2005 memori dan CPU multicore mahal. Saya memilih di sisi lain nomor 2 pada perangkat keras terbaru dalam 2 tahun terakhir. Itu tergantung pada ukuran gambar khas Anda dan jika Anda ingin dapat menghitung transformasi domain seperti DFT / DCT (seperti dalam makalah yang diusulkan dan dalam BM3D).