Saya bekerja dengan korelasi 2d untuk teknik pemrosesan gambar (pengenalan pola dll ...). Saya bertanya-tanya apakah ada pendekatan teoritis tentang cara mengetahui kapan harus menggunakan perkalian dalam ruang frekuensi lebih dari korelasi dalam ruang waktu. Untuk ukuran 2 x ruang frekuensi jelas lebih cepat tetapi bagaimana dengan ukuran kecil, prima seperti misalnya 11?
Saya akan menganggap ini sedang dilakukan pada CPU konvensional, satu inti, menjalankan satu utas sederhana, tidak ada perangkat keras mewah. Jika ada lebih dari itu terjadi, itu mungkin dapat dipertanggungjawabkan dengan penyesuaian dengan alasan untuk sistem yang lebih sederhana. Tidak banyak lagi yang bisa dikatakan tanpa sistem khusus untuk didiskusikan, atau seluruh buku teks atau makalah penelitian untuk mencakup berbagai kemungkinan.
Saya tidak akan khawatir tentang kekuatan dua ukuran. Itu tidak masalah. Algoritma FFT dengan unit kupu-kupu dan semua yang ada untuk faktor 3, atau jumlah kecil, tidak hanya 2. Ada algoritma pintar untuk seri data berukuran prima juga. Saya tidak suka mengutip Wikipedia tentang ini karena sifatnya yang tidak kekal, tetapi bagaimanapun:
ada FFT dengan kompleksitas O (N log N) untuk semua N, bahkan untuk prime N
Implementasi FFT untuk N sewenang-wenang dapat ditemukan di FFTW perpustakaan GPL .
Satu-satunya cara yang dapat dipercaya dalam hal teknik serius adalah membangun dan mengukur, tetapi kita tentu bisa mendapatkan ide dari teori, untuk melihat hubungan antar variabel. Kami membutuhkan perkiraan berapa banyak operasi aritmatika yang terlibat untuk setiap metode.
Mengalikan masih lebih lambat daripada penambahan pada sebagian besar CPU, bahkan jika perbedaannya telah menyusut sangat banyak selama bertahun-tahun, jadi mari kita menghitung perkalian. Akuntansi juga membutuhkan sedikit lebih banyak pemikiran dan melacak hal-hal.
Konvolusi langsung, sebenarnya mengalikan dan menambahkan menggunakan kernel konvolusi, mengulangi untuk setiap piksel keluaran, membutuhkan perkalian W² · K², di mana W adalah jumlah piksel di sepanjang satu sisi gambar (dengan asumsi kuadrat untuk kesederhanaan), dan K adalah ukurannya kernel konvolusi, sebagai piksel di satu sisi. Dibutuhkan penggandaan K² untuk menghitung satu piksel keluaran menggunakan kernel dan bagian berukuran sama dari gambar input. Ulangi untuk semua piksel keluaran, yang jumlahnya sama dengan pada gambar input.
(N mult ) langsung = W² · K²
Untuk melakukan pekerjaan di ruang Fourier, kita harus Fourier mengubah gambar. Ini dilakukan dengan menerapkan FFT ke setiap kolom secara terpisah, dan kemudian ke setiap baris. Poin data FFT untuk N membutuhkan sekitar 2N · log (N) perkalian; kami ingin N menjadi W, panjang satu kolom atau baris. Semua logaritma di sini adalah basis dua.
Ada baris W dan kolom W, jadi setelah semua FFT selesai, kami telah melakukan perkalian 2W · (2W · log (W)). Gandakan itu, karena setelah kita mengalikan dengan transformasi Fourier dari kernel, kita harus membalik-Fourier data untuk kembali ke gambar yang masuk akal. Itu 8W² · log (W). Tentu saja, mengalikan dengan transformasi Fourier dari kernel harus dilakukan, perkalian W² lainnya. (Dilakukan sekali, tidak sekali per piksel keluaran, per baris atau apa pun.) Ini adalah perkalian yang kompleks, jadi itulah perkalian nyata 4W².
Jadi, kecuali saya melakukan kesalahan (dan mungkin saya lakukan) yang kita miliki
(N mult ) Fourier = 4W² · (2 · log (W) + 1)
Kapan kita ingin melakukan sesuatu dengan cara langsung? Ketika K cukup kecil untuk membuat W² · K² lebih kecil dari 4W² · (2 · log (W) + 1). Faktor umum W² mudah difaktorkan. Kami mungkin dapat menghapus "+1" karena kami sedang berhadapan dengan perkiraan yang diidealkan. +1 kemungkinan hilang karena kesalahan relatif terhadap implementasi aktual, dari tidak menghitung penambahan, overhead loop dan sebagainya. Itu meninggalkan:
K² < 8·log(W)
Ini adalah kondisi perkiraan untuk memilih pendekatan langsung daripada pendekatan ruang frekuensi.
Perhatikan bahwa korelasi dari dua gambar dengan ukuran yang sama seperti penggabungan dengan kernel berukuran K = W. Ruang Fourier selalu merupakan cara untuk melakukannya.
Ini dapat disempurnakan dan diperdebatkan untuk memperhitungkan overhead, pipelining opcode, float vs fixed-point, dan dibuang keluar jendela dengan GPGPU dan perangkat keras khusus.