Algoritma FFT (Fast Fourier Transform)

Algoritma FFT (Fast Fourier Transform) adalah salah satu algoritma yang dapat digunakan untuk melakukan kompresi sinyal ataupun gambar. Contoh yang dibahas kali ini adalah mengenai pengolahan file gambar.
Algoritma ini adalah variasi dari Algoritma DFT (Discrete Fourier Transform), dimana teknik perhitungan yang dilakukan adalah menggunakan teknik Cooley–Tukey / Radix-2. Teknik ini melakukan metode Divide and Conquer untuk memecahkan data menjadi bagian yang lebih kecil, kemudian melakukan proses perhitungan FFT pada komponen terkecil, sehingga proses perhitungan dapat dilakukan lebih cepat dibandingkan dengan DFT (Discrete Fourier Transform).

Diketahui data awal adalah sebagai berikut. Dalam kasus ini akan digunakan gambar berwarna bertipe jpg dengan ukuran 128 x 128 pixel

Perlu diingat bahwa ukuran lebar dan panjang yang direkomendasikan adalah kelipatan 2, dan ukuran gambar adalah persegi (ukuran lebar = ukuran panjang)
Jika ukuran gambar tidak persegi, maka gambar tersebut harus dikonversi agar menjadi ukuran persegi
Ada 2 cara untuk melakukan hal tersebut

• Gambar tersebut diskala ulang
• Dilakukan penambahan pixel warna hitam disekeliling gambar tersebut

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan penyimpanan semua data warna dalam pixel yang terdapat dalam gambar tersebut
warna dalam sebuah pixel dibedakan menjadi 3 bagian, yaitu komponen merah, hijau, dan biru

For i = 0 To gmb.Width - 1
	For j = 0 To gmb.Height - 1
		inputPixel(i)(j)(0) = gmb.GetPixel(i, j).R
		inputPixel(i)(j)(1) = gmb.GetPixel(i, j).G
		inputPixel(i)(j)(2) = gmb.GetPixel(i, j).B
	Next j
Next i

2. Lakukan inisialisasi variabel yang digunakan oleh metode FFT (Fast Fourier Transform)
karena lebar dan panjang gambar contoh bernilai sama, maka jumlah data yang digunakan dalam perhitungan FFT adalah lebar atau panjang gambar tersebut

Dim fft As New FFT(gmb.Width)

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class FFT untuk menampung semua variabel yang dibutuhkan dalam perhitungan metode FFT (Fast Fourier Transform). Deklarasi Class FFT adalah sebagai berikut:

Public Class FFT
	Public Structure AngkaKompleks
		Public real As Double
		Public imajiner As Double
	End Structure

	Public jumlahData As Integer
	Public nilaiKompleks As AngkaKompleks()
	Public data As AngkaKompleks()
	Public output As Double()

	Public Sub New(jumlahData As Integer)
		Me.jumlahData = jumlahData
		nilaiKompleks = New AngkaKompleks(jumlahData / 2 - 1) {}
		For i As Integer = 0 To (jumlahData / 2) - 1
			nilaiKompleks(i).real = Math.Cos(2 * Math.PI * CDbl(i) / CDbl(jumlahData))
			nilaiKompleks(i).imajiner = Math.Sin(2 * Math.PI * CDbl(i) / CDbl(jumlahData))
		Next

		data = New AngkaKompleks(jumlahData) {}
		output = New Double(jumlahData) {}
	End Sub
	
	. . .
End Class

* Karena gambar contoh adalah gambar berwarna, maka akan terdapat 3 komponen warna dalam gambar tersebut (merah, hijau, biru)
Masing-masing warna akan dilakukan proses perhitungan secara baris dan secara kolom,
Sehingga akan terdapat 6x perhitungan dengan menggunakan metode DFT

3. Lakukan proses perhitungan pada setiap baris dari komponen warna merah
Proses pertama adalah proses perhitungan dengan metode FFT (Fast Fourier Transform)
Proses kedua adalah proses perhitungan inversi FFT
Kemudian catat nilai output sementara yang dihasilkan

For x = 0 To gmb.Width - 1
	For y As Integer = 0 To gmb.Height - 1
		fft.data(y).real = gmb.GetPixel(x, y).R
		fft.data(y).imajiner = 0.0
	Next

	fft.hitungFFT()

	fft.hitungIFFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Height - 1
		tmpOutput(x)(y)(0) = fft.output(y)
		tmpOutput(x)(y)(1) = 0.0
	Next
Next

For x = 0 To gmb.Height - 1
	For y As Integer = 0 To gmb.Width - 1
		fft.data(y).real = tmpOutput(x)(y)(0)
		fft.data(y).imajiner = tmpOutput(x)(y)(1)
	Next

	fft.hitungFFT()

	fft.hitungIFFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Width - 1
		tmpOutput(x)(y)(0) = fft.output(y)
		tmpOutput(x)(y)(1) = 0.0
	Next
Next

* Gunakan fungsi ini untuk melakukan proses perhitungan dengan metode FFT (Fast Fourier Transform)
Lakukan proses perhitungan untuk melakukan penukaran susunan data
Kemudian lakukan proses perhitungan untuk melakukan proses perhitungan dengan metode FFT (Fast Fourier Transform) pada sub data
Setelah proses tersebut, bagi semua elemen data dengan 2N, kecuali elemen data pertama yang harus dibagi dengan 4N

Public Sub hitungFFT()
	TukarIndeksData(data, jumlahData)
	hitungSubFFT(data, jumlahData)

	For i As Integer = 0 To jumlahData - 1
		data(i).imajiner = data(i).imajiner / CDbl(jumlahData) * 2.0
		data(i).real = data(i).real / CDbl(jumlahData) * 2.0
	Next
	data(0).imajiner = data(0).imajiner / 2.0
	data(0).real = data(0).real / 2.0
End Sub

* Gunakan fungsi ini untuk melakukan penukaran susunan data
Data akan dibagi 2 menjadi 2 sub data, kemudian indeks data terhitung akan ditukar dengan indeks pada sub data kedua,
Jika penjumlahan data berikutnya melebihi jumlah data, maka masing-masing sub data akan kembali dibagi dengan 2 (menjadi 4 sub data),
dan akan dilakukan proses penukaran indeks data yang sama sampai sub data terakhir hanya berisi 1 pasang data.

Public Sub TukarIndeksData(data As AngkaKompleks(), jumlahData As Integer)
	Dim jarak As Integer = jumlahData / 2
	Dim k As Integer
	Dim idxTukar As Integer = 0

	'Lakukan perhitungan dimulai dari indeks kedua sampai terakhir
	For i As Integer = 1 To jumlahData - 1
		k = i
		jarak = jumlahData / 2
		idxTukar = 0

		'Cari indeks data berikutnya sampai indeks yang ditemukan bukan indeks pertama
		While k > 0
			If (k Mod 2) > 0 Then
				idxTukar = idxTukar + jarak
			End If
			k = Math.Truncate(k / 2)
			jarak = jarak / 2
		End While

		'Lakukan penukaran data pada indeks terpiilh dan indeks yang telah dihitung sebelumnya
		If i < idxTukar Then
			Dim tmp As AngkaKompleks = data(idxTukar)
			data(idxTukar) = data(i)
			data(i) = tmp
		End If
	Next
End Sub

* Gunakan fungsi ini untuk melakukan proses perhitungan dengan metode FFT (Fast Fourier Transform) pada sub data
Setelah mengalami penukaran indeks, lakukan perhitungan FFT pada indeks data genap dan ganjil
Setelah semua data terhitung, masing-masing data indeks genap dan ganjil akan membentuk pasangan grup,
dan kemudian lakukan perhitungan FFT pada grup data antara indeks genap dan ganjil
Lakukan proses tersebut sampai semua data sudah tergabung menjadi satu grup

Public Sub hitungSubFFT(data As AngkaKompleks(), jumlahData As Integer)
	Dim k As Integer, m As Integer
	Dim nilai As AngkaKompleks
	Dim tmp As AngkaKompleks
	Dim tmpDataI As AngkaKompleks

	k = 1
	While k <= jumlahData / 2
		m = 0
		While m <= (jumlahData - 2 * k)
			For i As Integer = m To m + (k - 1)
				nilai.real = nilaiKompleks(((i - m) * jumlahData / k / 2)).real
				nilai.imajiner = nilaiKompleks(((i - m) * jumlahData / k / 2)).imajiner

				tmp = hitungPerkalianKompleks(data(i + k), nilai)
				tmpDataI = data(i)
				data(i) = hitungPenjumlahanKompleks(data(i), tmp)
				data(i + k) = hitungPenguranganKompleks(tmpDataI, tmp)
			Next
			m = m + 2 * k
		End While
		k = k * 2
	End While
End Sub

* Gunakan fungsi ini untuk menghitung penjumlahan antara 2 angka kompleks

Public Function hitungPenjumlahanKompleks(a As AngkaKompleks, b As AngkaKompleks) As AngkaKompleks
	Dim output As AngkaKompleks
	output.real = a.real + b.real
	output.imajiner = a.imajiner + b.imajiner
	Return (output)
End Function

* Gunakan fungsi ini untuk menghitung pengurangan antara 2 angka kompleks

Public Function hitungPenguranganKompleks(a As AngkaKompleks, b As AngkaKompleks) As AngkaKompleks
	Dim output As AngkaKompleks
	output.real = a.real - b.real
	output.imajiner = a.imajiner - b.imajiner
	Return (output)
End Function

* Gunakan fungsi ini untuk menghitung perkalian antara 2 angka kompleks

Public Function hitungPerkalianKompleks(a As AngkaKompleks, b As AngkaKompleks) As AngkaKompleks
	Dim output As AngkaKompleks
	output.real = a.real * b.real - a.imajiner * b.imajiner
	output.imajiner = a.real * b.imajiner + a.imajiner * b.real
	Return (output)
End Function

4. Masukkan nilai output sementara sebagai nilai output untuk komponen warna merah
Jika nilai output ternyata diluar batas warna yang diperbolehkan,
maka kembalikan nilainya agar masuk dalam batas tersebut

For x = 0 To gmb.Width - 1
	For y = 0 To gmb.Height - 1
		If tmpOutput(x)(y)(0) < 0 Then
			outputPixel(x)(y)(0) = 0
		ElseIf tmpOutput(x)(y)(0) > 255 Then
			outputPixel(x)(y)(0) = 255
		Else
			outputPixel(x)(y)(0) = tmpOutput(x)(y)(0)
		End If
	Next
Next

5. Lakukan proses yang sama (poin 3 dan 4) untuk komponen warna hijau dan biru

For x = 0 To gmb.Width - 1
	For y As Integer = 0 To gmb.Height - 1
		fft.data(y).real = gmb.GetPixel(x, y).G
		fft.data(y).imajiner = 0.0
	Next

	fft.hitungFFT()

	fft.hitungIFFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Height - 1
		tmpOutput(x)(y)(0) = fft.output(y)
		tmpOutput(x)(y)(1) = 0.0
	Next
Next

For x = 0 To gmb.Height - 1
	For y As Integer = 0 To gmb.Width - 1
		fft.data(y).real = tmpOutput(x)(y)(0)
		fft.data(y).imajiner = tmpOutput(x)(y)(1)
	Next

	fft.hitungFFT()

	fft.hitungIFFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Width - 1
		tmpOutput(x)(y)(0) = fft.output(y)
		tmpOutput(x)(y)(1) = 0.0
	Next
Next

For x = 0 To gmb.Width - 1
	For y = 0 To gmb.Height - 1
		If tmpOutput(x)(y)(0) < 0 Then
			outputPixel(x)(y)(1) = 0
		ElseIf tmpOutput(x)(y)(0) > 255 Then
			outputPixel(x)(y)(1) = 255
		Else
			outputPixel(x)(y)(1) = tmpOutput(x)(y)(0)
		End If
	Next
Next

For x = 0 To gmb.Width - 1
	For y As Integer = 0 To gmb.Height - 1
		fft.data(y).real = gmb.GetPixel(x, y).B
		fft.data(y).imajiner = 0.0
	Next

	fft.hitungFFT()

	fft.hitungIFFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Height - 1
		tmpOutput(x)(y)(0) = fft.output(y)
		tmpOutput(x)(y)(1) = 0.0
	Next
Next

For x = 0 To gmb.Height - 1
	For y As Integer = 0 To gmb.Width - 1
		fft.data(y).real = tmpOutput(x)(y)(0)
		fft.data(y).imajiner = tmpOutput(x)(y)(1)
	Next

	fft.hitungFFT()

	fft.hitungIFFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Width - 1
		tmpOutput(x)(y)(0) = fft.output(y)
		tmpOutput(x)(y)(1) = 0.0
	Next
Next

For x = 0 To gmb.Width - 1
	For y = 0 To gmb.Height - 1
		If tmpOutput(x)(y)(0) < 0 Then
			outputPixel(x)(y)(2) = 0
		ElseIf tmpOutput(x)(y)(0) > 255 Then
			outputPixel(x)(y)(2) = 255
		Else
			outputPixel(x)(y)(2) = tmpOutput(x)(y)(0)
		End If
	Next
Next

* Tampilkan pada layar

Dim bitMap As Bitmap = BuatBitmap(outputPixel, 2)
picHasil.Image = bitMap.Clone
bitMap.Dispose()

Hasil akhir adalah: (klik untuk perbesar gambar)

Karena tidak melakukan proses pengolahan data frekuensi apapun, maka hasil akhir perhitungan tersebut akan mengembalikan gambar yang sama seperti awalnya.

Contoh source code lengkap dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.