Algoritma DCT (Discrete Cosine Transform)

Algoritma DCT (Discrete Cosine Transform) adalah salah satu algoritma yang dapat digunakan untuk melakukan kompresi sinyal ataupun gambar. Contoh yang dibahas kali ini adalah mengenai kompresi gambar yang biasanya dilakukan oleh file bertipe JPEG.
Algoritma ini sangat mirip dengan Algoritma DFT (Discrete Fourier Transform), dimana jika pada algoritma ini, hanya fungsi kosinus yang digunakan dalam perhitungan angka kompleks, sedangkan pada Algoritma DFT (Discrete Fourier Transform), dibutuhkan 2 buah fungsi (sinus dan kosinus) untuk menghitung 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

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan lebar dan panjang dalam perhitungan blok pixel
Nantinya dalam sekali perulangan akan dilakukan perhitungan pixel sesuai dengan ukuran blok pixel ini
Direkomendasikan nilainya adalah kelipatan 2, dan ukuran blok pixel adalah persegi (ukuran lebar = ukuran panjang)
Diasumsikan dalam kasus ini, lebar dan panjang blok pixel adalah 16

Const lebarBlokPixel As Integer = 16
Const panjangBlokPixel As Integer = 16

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 perhitungan pada masing-masing pixel gambar tersebut (poin 2a – 2f)

For x = 0 To gmb.Width - 1 Step lebarBlokPixel
	For y = 0 To gmb.Height - 1 Step panjangBlokPixel
	. . .

* Perlu diingat bahw dalam sekali perulangan akan dilakukan perhitungan blok pixel dengan ukuran sesuai dengan parameter lebar dan panjang blok pixel

2a. Lakukan perhitungan untuk mencari komponen Y, U, V dari blok pixel terpilih

Call hitungYUVPixel(x, y)

* Gunakan fungsi ini untuk menghitung nilai komponen Y, U, V pada masing-masing pixel

Public Sub hitungYUVPixel(ByVal posX As Integer, ByVal posY As Integer)
	Dim x As Integer
	Dim y As Integer

	For x = posX To posX + lebarBlokPixel - 1
		For y = posY To posY + panjangBlokPixel - 1
			nilaiYPixel(x - posX, y - posY) = hitungYPixel(gmb.GetPixel(x, y))
			nilaiUPixel(x - posX, y - posY) = hitungUPixel(gmb.GetPixel(x, y))
			nilaiVPixel(x - posX, y - posY) = hitungVPixel(gmb.GetPixel(x, y))
		Next y
	Next x
End Sub

Public Function hitungYPixel(color As Color) As Integer
	hitungYPixel = (0.299 * color.R) + (0.587 * color.G) + (0.114 * color.B)
End Function

Public Function hitungUPixel(color As Color) As Integer
	hitungUPixel = (-0.147 * color.R) - (0.289 * color.G) + (0.436 * color.B)
End Function

Public Function hitungVPixel(color As Color) As Integer
	hitungVPixel = (0.615 * Color.R) - (0.515 * Color.G) - (0.1 * Color.B)
End Function

2b. Lakukan proses perhitungan dengan menggunakan metode DCT (Discrete Cosine Transform) pada blok pixel terpilih
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2b1 – 2b10)

Call hitungDCT(0, x, y)

* Gunakan fungsi ini untuk melakukan proses perhitungan dengan metode DCT (Discrete Cosine Transform)
Nilai koefisien dalam masing-masing pixel dihitung dengan rumus:
Y(k,l) = (2/root(N*M)) * alpha(k) * alpha(l) * Y(i,j) * cos(pi * (2i+1) * k / (2N)) * cos(pi * (2j+1) * l / (2M))

Public Sub hitungDCT(idx As Integer, ByVal posX As Integer, ByVal posY As Integer)
	Dim k As Integer
	Dim l As Integer
	Dim i As Long
	Dim j As Long
	Dim tmpKoefisien As Double

	For k = posX To posX + lebarBlokPixel - 1
		For l = posY To posY + panjangBlokPixel - 1

			tmpKoefisien = 0
			For i = posX To posX + lebarBlokPixel - 1
				For j = posY To posY + panjangBlokPixel - 1
					tmpKoefisien = tmpKoefisien + (nilaiYPixel(i - posX, j - posY)) * _
						Math.Cos(((2 * (i - posX) + 1) * (k - posX) * Math.PI) / (2 * lebarBlokPixel)) * _
						Math.Cos(((2 * (j - posY) + 1) * (l - posY) * Math.PI) / (2 * panjangBlokPixel))
				Next j
			Next i

			koefisienDCT(idx, k - posX, l - posY) = alpha(k - posX) * alpha(l - posY) * tmpKoefisien * (2 / Math.Sqrt(lebarBlokPixel * panjangBlokPixel))
		Next l
	Next k
End Sub

* Gunakan fungsi ini untuk menghitung nilai alpha untuk digunakan dalam perhitungan koefisien DCT

Public Function alpha(value As Integer) As Double
	If value = 0 Then
		alpha = 1 / Math.Sqrt(2)
	Else
		alpha = 1
	End If
End Function

2c. Kosongkan semua nilai komponen Y dari blok pixel terpilih untuk digunakan pada perhitungan berikutnya

For x1 = 0 To lebarBlokPixel - 1
	For y1 = 0 To panjangBlokPixel - 1
		nilaiYPixel(x1, y1) = 0
	Next y1
Next x1

2d. Lakukan proses perhitungan dengan menggunakan metode inversi DCT pada blok pixel terpilih
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2d1 – 2d10)

Call hitungIDCT(0, x, y)

* Gunakan fungsi ini untuk melakukan proses perhitungan dengan metode inversi DCT
Nilai komponen Y dalam masing-masing pixel dihitung dengan rumus:
Y(i,j) = (2/root(N*M)) * Y(k,l) * alpha(k) * alpha(l) * cos(pi * (2i+1) * k / (2N)) * cos(pi * (2j+1) * l / (2M))

Public Sub hitungIDCT(idx As Integer, ByVal posX As Integer, ByVal posY As Integer)
	Dim k As Integer
	Dim l As Integer
	Dim i As Long
	Dim j As Long
	Dim tmpKoefisien As Double

	For i = posX To posX + lebarBlokPixel - 1
		For j = posY To posY + panjangBlokPixel - 1

			tmpKoefisien = 0
			For k = posX To posX + lebarBlokPixel - 1
				For l = posY To posY + panjangBlokPixel - 1
					tmpKoefisien = tmpKoefisien + (koefisienDCT(idx, k - posX, l - posY) * alpha(k - posX) * alpha(l - posY)) * _
						Math.Cos(((2 * (i - posX) + 1) * (k - posX) * Math.PI) / (2 * lebarBlokPixel)) * _
						Math.Cos(((2 * (j - posY) + 1) * (l - posY) * Math.PI) / (2 * panjangBlokPixel))
				Next l
			Next k

			nilaiYPixel(i - posX, j - posY) = tmpKoefisien * (2 / Math.Sqrt(lebarBlokPixel * panjangBlokPixel))
		Next j
	Next i
End Sub

2e. Lakukan proses perhitungan untuk menghitung nilai output pixel setelah melalui proses inversi DCT pada blok pixel terpilih
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2e1 – 2e10)

Dim tmpOutputPixel()()() As Byte = hitungOutputPixel(x, y)

* Gunakan fungsi ini untuk menghitung nilai output pixel setelah melalui proses inversi DCT
Setiap komponen Y, U, V dari masing-masing pixel akan dikonversi kembali menjadi komponen merah, hijau, biru

Public Function hitungOutputPixel(ByVal posX As Integer, ByVal posY As Integer) As Byte()()()
	Dim x As Integer
	Dim y As Integer

	Dim outputPixel(lebarBlokPixel - 1)()() As Byte
	For i = 0 To outputPixel.Length - 1
		outputPixel(i) = New Byte(panjangBlokPixel - 1)() {}

		For j = 0 To outputPixel(i).Length - 1
			outputPixel(i)(j) = New Byte(2) {}
		Next
	Next i

	For x = posX To posX + lebarBlokPixel - 1
		For y = posY To posY + panjangBlokPixel - 1
			outputPixel(x - posX)(y - posY)(0) = YUV2R(nilaiYPixel(x - posX, y - posY), nilaiVPixel(x - posX, y - posY))
			outputPixel(x - posX)(y - posY)(1) = YUV2G(nilaiYPixel(x - posX, y - posY), nilaiUPixel(x - posX, y - posY), nilaiVPixel(x - posX, y - posY))
			outputPixel(x - posX)(y - posY)(2) = YUV2B(nilaiYPixel(x - posX, y - posY), nilaiUPixel(x - posX, y - posY))
		Next y
	Next x

	Return outputPixel
End Function

Public Function YUV2R(y As Double, v As Double) As Integer
	YUV2R = y + (1.14 * v)
	If YUV2R < 0 Then YUV2R = 0
	If YUV2R > 255 Then YUV2R = 255
End Function

Public Function YUV2G(y As Double, u As Double, v As Double) As Integer
	YUV2G = y - (0.395 * u) - (0.581 * v)
	If YUV2G < 0 Then YUV2G = 0
	If YUV2G > 255 Then YUV2G = 255
End Function

Public Function YUV2B(y As Double, u As Double) As Integer
	YUV2B = y + (2.032 * u)
	If YUV2B < 0 Then YUV2B = 0
	If YUV2B > 255 Then YUV2B = 255
End Function

2f. Masukkan kembali blok pixel yang telah dihitung ke dalam matriks output

For x1 = x To x + lebarBlokPixel - 1
	For y1 = y To y + panjangBlokPixel - 1
		outputPixel(x1)(y1) = tmpOutputPixel(x1 - x)(y1 - y)
	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.