Algoritma DFT (Discrete Fourier Transform)

Algoritma DFT (Discrete 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 sangat mirip dengan DCT (Discrete Cosine Transform), dimana jika pada algoritma ini, dibutuhkan 2 buah fungsi (sinus dan kosinus) untuk menghitung angka kompleks, sedangkan pada Algoritma DCT (Discrete Fourier Transform), hanya fungsi kosinus yang digunakan dalam perhitungan angka kompleks. Tetapi pada intinya kedua algoritma ini melakukan konversi data dari bentuk spasial menjadi bentuk frekuensi, kemudian melakukan pengolahan data frekuensi, dan dikonversi menjadi bentuk spasial menggunakan inversi metode yang bersangkutan.

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 DFT (Discrete Fourier Transform)
karena lebar dan panjang gambar contoh bernilai sama, maka jumlah data yang digunakan dalam perhitungan DFT adalah lebar atau panjang gambar tersebut

Dim dft As New DFT(gmb.Width)

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

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

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

	Public Sub New(jumlahData As Integer)
		Me.jumlahData = jumlahData
		nilaiKompleks = New AngkaKompleks(jumlahData) {}
		nilaiKompleks(0).real = 1.0    'cos(0) bernilai 1
		nilaiKompleks(0).imajiner = 0  'sin(0) bernilai 0
		For k As Integer = 1 To jumlahData - 1
			nilaiKompleks(k).real = Math.Cos((2.0 * Math.PI * CDbl(k) / CDbl(jumlahData)))
			nilaiKompleks(k).imajiner = -Math.Sin((2.0 * Math.PI * CDbl(k) / CDbl(jumlahData)))
		Next

		data = New AngkaKompleks(jumlahData) {}
		komponenFourier = 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 DFT (Discrete Fourier Transform)
Proses kedua adalah proses perhitungan inversi DFT
Kemudian catat nilai output sementara yang dihasilkan

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

	dft.hitungDFT()

	dft.hitungIDFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Height - 1
		tmpOutput(x)(y)(0) = dft.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
		dft.data(y).real = tmpOutput(x)(y)(0)
		dft.data(y).imajiner = tmpOutput(x)(y)(1)
	Next

	dft.hitungDFT()

	dft.hitungIDFT(gmb.Width / 2)

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

* Gunakan fungsi ini untuk melakukan proses perhitungan dengan metode DFT (Discrete Fourier Transform)
Proses ini membutuhkan parameter data dan nilai kompleks,
dan akan mengembalikan komponen fourier yang memiliki nilai real dan nilai imajiner

Public Sub hitungDFT()
	If jumlahData > 0 Then
		For k As Integer = 0 To jumlahData - 1
			komponenFourier(k).real = 0
			komponenFourier(k).imajiner = 0

			For l As Integer = 0 To (jumlahData - 1) - 1
				komponenFourier(k) = hitungPenjumlahanKompleks(komponenFourier(k), hitungPerkalianKompleks(nilaiKompleks((k * l) Mod jumlahData), data(l)))
			Next

			komponenFourier(k).real = komponenFourier(k).real / jumlahData * 2
			komponenFourier(k).imajiner = -komponenFourier(k).imajiner / jumlahData * 2
		Next

		komponenFourier(0).real = komponenFourier(0).real / 2
		komponenFourier(0).imajiner = komponenFourier(0).imajiner / 2
	End If
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 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

* Gunakan fungsi ini untuk melakukan proses perhitungan dengan metode inversi DFT
Proses ini membutuhkan parameter komponen fourier,
dan akan mengembalikan nilai output real

Public Sub hitungIDFT(ByVal jumlahKomponen As Integer)
	For k As Integer = 0 To jumlahData - 1
		output(k) = 0

		For l As Integer = 0 To (jumlahKomponen - 1)
			output(k) = output(k) + komponenFourier(l).real * Math.Cos(2.0 * Math.PI * CDbl(l * k) / CDbl(jumlahData)) _
								  + komponenFourier(l).imajiner * Math.Sin(2.0 * Math.PI * CDbl(l * k) / CDbl(jumlahData))
		Next
	Next
End Sub

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
		dft.data(y).real = gmb.GetPixel(x, y).G
		dft.data(y).imajiner = 0.0
	Next

	dft.hitungDFT()

	dft.hitungIDFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Height - 1
		tmpOutput(x)(y)(0) = dft.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
		dft.data(y).real = tmpOutput(x)(y)(0)
		dft.data(y).imajiner = tmpOutput(x)(y)(1)
	Next

	dft.hitungDFT()

	dft.hitungIDFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Width - 1
		tmpOutput(x)(y)(0) = dft.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
		dft.data(y).real = gmb.GetPixel(x, y).B
		dft.data(y).imajiner = 0.0
	Next

	dft.hitungDFT()

	dft.hitungIDFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Height - 1
		tmpOutput(x)(y)(0) = dft.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
		dft.data(y).real = tmpOutput(x)(y)(0)
		dft.data(y).imajiner = tmpOutput(x)(y)(1)
	Next

	dft.hitungDFT()

	dft.hitungIDFT(gmb.Width / 2)

	For y As Integer = 0 To gmb.Width - 1
		tmpOutput(x)(y)(0) = dft.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.

Tinggalkan sebuah komentar Batalkan balasan

2 pemikiran di “Algoritma DFT (Discrete Fourier Transform)”

Balas ↓
MACHNUN ARIF 5 Juni 2022 pada 5:27 pm
Salam kenal, apakah contoh diatas ada yg menggunakan software MATLAB?
- Balas ↓
  pip Penulis 6 Juni 2022 pada 3:00 pm
  Referensi yang saya gunakan sebenarnya benar didapatkan dari bahasa matlab. Tetapi saat ini saya sudah tidak memiliki referensi tersebut.

Langkah-langkah penggunaan algoritma ini adalah

Hasil akhir adalah: (klik untuk perbesar gambar)

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

Bagikan ini:

Tinggalkan sebuah komentar Batalkan balasan

2 pemikiran di “Algoritma DFT (Discrete Fourier Transform)”