Fast Fourier Transform (FFT)
adalah sebuah algoritma komputasi untuk mengurangi komputasi apabila
menggunakan transformasi Fourier yang biasa. FFT digunakan untuk
mentransformasikan time domain ke dalam bentuk frequency
domain. Fungsi FFT lazim digunakan pada signal processing. Image processing merupakan fungsi spasial yang bisa dikonversi
menjadi domain frequensi. Untuk citra dua dimensi, citra memiliki
informasi spasial (dua dimensi) yang terkandung di dalam setiap elemen
pikselnya. Dalam tahap perkembangannya, FFT memiliki teknik algortima yang
bervariasi, contohnya adalah pada aplikasi Image-J.
Jika
dilihat dari perspektif frekuensi, citra bisa dibedakan menjadi 2 (high
frequency dan low frequency). Sinyal high frequency biasanya adalah
“the real signal of an object” atau “signal of interest“. Dengan kata lain,
sinyal inilah yang biasanya akan dianalisis. Sedangkan sinyal frekuensi rendah
biasanya adalah sinyal background dari sebuah citra. Dalam domain spasial,
kedua sinyal ini terkadang sangat sulit dipisahkan. Untuk itu diperlukan teknik
FFT untuk memisahkan/mengeliminasi salah satu sinyal yang diinginkan dengan
sangat mudah.
Berikut
ini adalah contoh penggunaan fungsi FFT pada image processing:
Gambar di
atas menunjukkan sebuah citra yang memiliki struktur periodic yang unik. Dalam
contoh kasus ini, kita ingin menghilangkan background dari citra ini dengan
menggunakan operasi FFT. Untuk itu kita akan menggunakan fungsi FFT dari
Image-J yang sudah tersedia. Untuk melakukan Fourier transformation dengan
menggunakan Image-J, kita harus menggubah citra ke dalam bentuk format 8-bit
grayscale:
Kemudian
dengan memilih opsi FFT pada aplikasi Image-J akan dihasilkan:
Sinyal
yang terletak ditengah adalah sinyal low frequency atau sinyal
dari background yang ingin kita eliminasi. Cara untuk mengeliminasi frekuensi
rendah ini adalah dengan memblok area dari hasil transformasi fourier citra
seperti tergambar pada gambar berikut:
Arti
dari pemblokan low frequency ini adalah mengalikan semua nilai
piksel frekuensi rendah dengan piksel hitam yang bernilai keabuan 0. Dengan
melakukan ini, kita sudah mengaplikasikan high pass filter pada
citra kita. Untuk melihat hasil dari high pass filter ini,
kita harus melakukan operasi inverse FFT. Hasil dari inverse FFT
bisa kita lihat pada gambar berikut:
Dengan
melakukan inverse FFT, maka filtering berbasis frekuensi, dalam contoh kasus
ini high pass filter telah berhasil dilakukan.
Contoh-contoh
penggunaan FFT lainnya adalah:
1. Untuk
data compression, contoh: mp3.
2.
Analisis spektral dari sebuah sinyal.
3.
Mencari respons frekuensi dari sebuah system.
Untuk jumlah sample yang
sedikit mungkin perbedaan kompleksitastidak begitu terasa, namun lain ceritanya
bila kita mengambil jumlah sample yang sedikit lebih banyak.
Misalnya kita hanya mengambil 2 sample, dengan menggunakan
DFT, tingkat kompleksitas transformasi kita adalah 4, sementara dengan
menggunakan FFT kompleksitasnya sebesar 0,602. Perbedaan yang semakin mencolok
tampak bila kita mengambil jumlah sample yang lebih banyak
lagi, misalnya kita ingin meninjau 64 titiksample, maka kompleksitas
dengan menggunakan DFT adalah sebesar 4096, sementara dengan menggunakan FFT
kompleksitasnya menjadi 115,6. Perbedaan yang sangat mencolok melihat
perbandingan yang mencapai hampir 40 kali lipatnya. Kompleksitas transformasi
ini terutama menjadi vital saat diimplementasikan pada perangkat riil.
Perbandingan kompleksitas DFT dan FFT dapat dilihat pada gambar berikut:
Komentar
Posting Komentar