Algoritma DST (Discrete Sine Transform) [Eksperimen]

Algoritma DST (Discrete Sine Transform) adalah salah satu algoritma yang dapat digunakan untuk melakukan kompresi sinyal ataupun gambar. Contoh yang dibahas kali ini adalah mengenai pengolahan file gambar.
Pada intinya algoritma ini adalah Algoritma DFT (Discrete Fourier Transform) yang hanya menggunakan fungsi sinus nya saja. Tetapi sebenarnya algoritma ini bukan ditujukan untuk perhitungan secara multidimensi, melainkan hanya digunakan untuk menyelesaikan permasalahan persamaan fungsi parsial yang berbeda. Tetapi dalam kasus ini saya “paksakan” untuk menyelesaikan permasalahan multidimensi, dan hasilnya memang tidak sempurna.

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 DST (Discrete Sine Transform) pada blok pixel terpilih
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2b1 – 2b10)

Call hitungDST(0, x, y)

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

Public Sub hitungDST(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.Sin(((2 * (i - posX) + 1) * ((k - posX) + 1) * Math.PI) / (2 * lebarBlokPixel)) * _
						Math.Sin(((2 * (j - posY) + 1) * ((l - posY) + 1) * Math.PI) / (2 * panjangBlokPixel))
				Next j
			Next i

			koefisienDST(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 DST

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 DST pada blok pixel terpilih
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2d1 – 2d10)

Call hitungIDST(0, x, y)

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

Public Sub hitungIDST(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 + (koefisienDST(idx, k - posX, l - posY) * alpha(k - posX) * alpha(l - posY)) * _
						Math.Sin(((2 * (i - posX) + 1) * ((k - posX) + 1) * Math.PI) / (2 * lebarBlokPixel)) * _
						Math.Sin(((2 * (j - posY) + 1) * ((l - posY) + 1) * 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 DST 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 DST
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)

Seharusnya hasil perhitungan akan mengembalikan gambar yang sama seperti aslinya. Sesuai pernyataan pada bagian awal pos ini, memang terbukti bahwa algoritma ini tidak bisa digunakan untuk menyelesaikan permasalahan multidimensi, sehingga hasilnya tidak sempurna. Tetapi hendaknya hasil eksperimen ini menjadi contoh awal dalam pengembangan ke dalam kasus-kasus berikutnya.

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.