METODE REGION BASED QUADTREE UNTUK REPRESENTASI CITRA BERWARNA Soendoro Herlambang1
A
Program Studi Sistem Informasi, Sekolah Tinggi Manajemen Informatika & Teknik Komputer Surabaya (STIKOM), Email:
[email protected]
AY
Abstract: Quadtree one of data spatial structures that represents image. This representation is aimed to reduce image storage file capacity. This research has been tested using black-white and colour image, black-white got the same representation and colours started from 2 colours got storage reduction as may as 62,65 %, 4 colours 53.14%, 8 colours 47.43%and 16 colours 42.67%. Each of colours is encode in 1 character and saved in text file. As shown in the output of representation, the quadtree representation differs for different resolution.
AB
Keywords : Quadtree, Region Based Quadtree, Spatial Data, Colors
R
Region Based Quadtree Method adalah suatu metode untuk merepresentasikan citra ke dalam pembagian empat bidang kwadran yang homogen North-East, North-West, South-East dan South-West secara rekursif. Menurut Samet (1990a, 90b), representasi suatu citra dilakukan dengan mendekomposisi citra menjadi 4 bidang seperti pada gambar 1.
SU
North North West (NW)
North East (NE)
West
East
NW
South East (SE)
M
South West (SW)
NE
SW
SE
Gambar 2. Bentuk Quadtree
South
O
Gambar 1. Pedoman arah pendekomposisian citra
ST
IK
Quadtree merupakan struktur data spasial untuk merepresentasikan suatu bidang. Representasi ini mengubah dari bentuk region ke bentuk tree. Representasi dapat mengurangi besarnya ruang kapasitas penyimpanan. Hasil dari representasi akan mengkodekan citra sesuai dengan warna citra tersebut. Representasi quadtree dibangun dari Morton matrik. Contoh dari Morton matrik ditunjukkan pada Gambar 3. 1 2 5 6 17 18 21 22
1
3
4
7
8
19
20
23
24
9
10
13
14
25
26
29
30
11
12
15
16
27
28
31
32
33
34
37
38
49
50
53
54
35
36
39
40
51
52
55
56
Jurusan Manajemen Informatika STIKOM, Surabaya
41
42
45
46
57
58
61
62
43
44
47
48
59
60
63
64
Gambar 3. Morton Matrik 23 X 23
2
5
6
17
18
AB
1
AY
A
Angka-angka pada gambar di atas, merupakan cara kunjungan terhadap image. ‘Leaf node’ dapat dibentuk jika ada penggabungan dari beberapa node yang mempunyai warna yang sama. Gambar 4 (a) akan direpresentasikan dengan binary image array berukuran 23 X 23 seperti pada gambar 4 (b). Matrik tersebut diberi nama A. Kunjungan ke elemen matrik dimulai dari elemen A[1,1] diikuti A[2,1], A[1,2], A[2,2], A[1,3] dan seterusnya (Samet and Webber, 84). Ternyata pixel 1, 2, 3, 4 mempunyai tipe warna yang sama yaitu BLACK dan pada akhirnya direpresentasi dengan node A sebagai hasil akhirnya. Pixel nomor 5, 6, 7, 8 mempunyai tipe yang tidak sama sehingga tidak dapat digabungkan menjadi satu node (pixel 5,6 berwarna WHITE, pixel 7,8 berwarna BLACK). Hasil akhir dari representasinya dapat terlihat pada
3
4
7
8
19
20
23
24
9
10
13
14
25
26
29
30
11
12
15
16
27
28
31
32
33
34
37
38
49
50
53
54
35
36
39
40
51
52
55
56
41
42
45
46
57
58
61
62
43
44
47
48
59
60
63
64
R SU
22
(b)
IK
O
M
(a)
21
(c)
ST
gambar 4 (c)
Gambar 4. (a) Contoh gambar. (b) Dekomposisi area. (c) Representasi Quadtree
Menentukan kode dengan cara mengunjungi tiap node pada quadtree yang disebut tree traversal. Kunjungan yang digunakan adalah preorder. Cara kerjanya adalah cetak isi node yang dikunjungi, kunjungi cabang kiri, kunjungi cabang kanan. METODE Dalam melakukan penelitian, untuk merepresentasikan quadtree citra berwarna, diperlukan merancang quadtree untuk pengetesan black-white terlebih dahulu. Perancangan algoritma untuk membangun quadtree citra black-white terdapat pada Gambar 5 (Herlambang, 2003).
START
Level = kedalaman
Tidak
AY
Level =0
A
x= EXPN(2,level) y= EXPN(2,level)
level:=level-1; texpn:=EXPN(2,level); tx:=x-texpn; ty:=y-texpn;
Ya
AB
Cek pada RLC
CONSTRUCT(p[1],level,tx,ty); CONSTRUCT(p[2],level,x,ty); CONSTRUCT(p[3],level,tx,y); CONSTRUCT(p[4],level,x,y);
Tidak
R
Inside RLC ?
Ya
Tidak
White
New(q) q^.NW = p[1] q^.N E = p[2] q^.SW = p[3] q^.SE = p[4]
Ya
par = p[1]
M
END
SU
Black
p[1].colour= p[2].colour= p[3].colour= p[4].colour ?
O
Gambar 5. Diagram Alir Pembentukan Quadtree untuk Citra Black-White Secara Rekursif
ST
IK
Rancangan membangun quadtree untuk representasi citra berwarna menggunakan pedoman dari rancangan quadtree black-white. Proses mendapatkan nilai warna piksel dilakukan dengan cara membuka bagian header dan palette dari citra dengan format bitmap. Diagram alir pembentukan quadtree untuk citra berwarna terdapat pada gambar 6 (Herlambang, 2003).
START
Level = kedalaman
Tidak
AY
Level =0
A
x= EXPN(2,level) y= EXPN(2,level)
level:=level-1; texpn:=EXPN(2,level); tx:=x-texpn; ty:=y-texpn;
Ya
AB
Get Color Number
Tidak
SU
Color Number 0 : color:=black 1 : color=blue 2 : color = green 3 : color = cyan 4 : color = red 5 : color = magenta 6 : color = brown 7 : color = lightgray 8 : color = darkgray 9 : color = lightblue 10 : color = lightgreen 11 : color = lightcyan 12 : color = lightred 13 : color = lightmagenta 14 : color = yellow 15 : color = white
R
CONSTRUCT(p[1],level,tx,ty); CONSTRUCT(p[2],level,x,ty); CONSTRUCT(p[3],level,tx,y); CONSTRUCT(p[4],level,x,y);
Ya
par = p[1]
M
New(q) q^.NW = p[1] q^.N E = p[2] q^.SW = p[3] q^.SE = p[4]
p[1].colour= p[2].colour= p[3].colour= p[4].colour ?
O
END
IK
Gambar 6. Diagram Alir Pembentuk Quadtree Untuk Citra Berwarna Secara Rekursif
ST
HASIL DAN PEMBAHASAN 1. Tes Dengan Simulasi Citra Hitam-Putih Simulasi 1 menggunakan citra seperti pada gambar 3. Kemudian simulasi 2 menggunakan citra gambar 6.
A AY
AB
Gambar 7. Gambar Simulasi Hitam-Putih
R
Hasil penelitian menunjukkan bahwa ratio = 1 (object size sama dengan image size) mempunyai hasil yang sama dengan ratio > 1 (object size lebih kecil dari image size), yaitu jumlah node hitam, node putih maupun total jumlah node, besarnya sama atau tidak berubah. Kondisi ini menunjukkan bahwa representasi quadtree yang dihasilkan juga sama dan kapasitas penyimpanan file teks yang dihasilkan mununjukkan total jumlah node. Hasil analisa ini digunakan untuk keperluan tes dengan kasus nyata untuk citra black-white maupun berwarna, yakni citra cukup dianalisa ratio = 1, dimana ratio adalah perbandingan antara image size dan object size. Hasil selengkapnya dilihat pada Tabel 1.
SU
Tabel 1. Hasil Tes Dengan Simulasi Citra Hitam-Putih Ratio 1
Object Size = 8
Simulasi 2
Node Hitam
6
28
Node Putih
7
12
Node ‘(‘
4
13
Jumlah Node
17
53
17
53
O
M
Simulasi 1
IK
Ukuran file(bytes)
ST
Hasil pengkodean untuk simulasi citra pertama adalah : ((B(WWBBWB(WWBWWB Sedangkan hasil pengkodean untuk simulasi citra kedua adalah : ((W(WBBB(WBBBB((BWBBWB(BWBB((BBWBBW(BBWB(B(BBBW(BBBWW 2. Tes Dengan Kasus Nyata Citra Hitam-Putih Untuk mengekstrak citra, peneliti melakukan ploting terhadap peta dari pulau ternate , sehingga diperoleh masing-masing titik sudut koordinat. Berdasarkan hasil simulasi pada citra black-white, maka analisa dilakukan dengan ratio = 1 karena analisa dengan ratio > 1 hasilnya akan sama dengan ratio = 1. Total jumlah node menunjukkan total kapasitas file penyimpanan. Hal ini terlihat pada real test case dengan ratio =1, dimana total jumlah node dan kapasitas file penyimpanan =249 bytes. Hasil selengkapnya dapat dilihat pada tabel 2. Hasil pengkodean dari quadtree yang terbentuk adalah : ((W(WW(W(WWWBW(WBBB(B(WWBBBB(WWW(W(WBWBWB(((WWWBBBBBBB((WW(WWB B(WW(BWBB(WWBWWB(((WWBWW(BWBBWW(B(BWBBBB(WW(BWBWW((W(WB(WWWBB
W((WBWBB(WBWWBB(W(W(WBWBWWWW(BB((WBWWBW(WBWW(BB(BBWBB(B(B((BWB WW(BWBWWB((BWBWWWW(BB(BBB(BBWW(BB(BBWW(BWWW((BBB(BWWWW((BWWWW WWW Tabel 2. Hasil Tes Dengan Kasus Nyata Citra Hitam-Putih Ratio 1
Node Hitam
83
Node Putih
104
Node ‘(‘
62
Jumlah Node
249
Ukuran file(bytes)
249
AY
A
Object Size = 32
M
SU
R
AB
3. Tes Dengan Simulasi Citra Berwarna Citra yang dianalisa mempunyai format Bitmap. Untuk mengekstrak dan memperoleh informasi mengenai nilai warna piksel dari citra, diperlukan teknik khusus yaitu mengekstrak HEADER dan PALETTE. Berikut diperlihatkan beberapa citra untuk keperluan simulasi.
(c)
(b)
(a)
O
Gambar 8. (a) Citra Homogen, (b) Citra Agak Heterogen, (c) Citra Heterogen
ST
IK
Dengan resolusi warna yang berbeda, maka representasi dari quadtree juga berbeda. Jika gambar dianalisa dengan menggunakan resolusi yang rendah (2 warna), maka representasi quadtree akan nampak berbeda dan lebih sederhana dibanding dengan analisa dengan resolusi yang lebih tinggi (16 warna). Resolusi 2 warna hanya menampilkan node berwarna hitam dan putih, node warna yang lain belum nampak. Jika resolusi ditambah menjadi 16 warna, maka akan nampak warna-warna lain sesuai dengan citra aslinya. Kondisi ini juga menunjukkan penambahan jumlah node yang ada, dan secara tidak langsung kapasitas penyimpanan dari hasil pengkodean representasi quadtree akan bertambah sesuai dengan pertambahan jumlah node. Hasil selengkapnya dapat dilihat pada Tabel 3. Tabel 3. Hasil Tes Dengan Simulasi Citra Berwarna Simulasi 1
Object Size = 32 2 warna
Simulasi 2
Simulasi 3
node
Bytes
node
Bytes
node
Bytes
21
21
21
21
61
61
4 warna
21
21
21
21
61
61
8 warna
21
21
21
21
69
69
16 warna
21
21
21
21
81
81
IK
O
M
SU
R
AB
AY
A
4. Tes Dengan Kasus Nyata Citra Berwarna Citra yang dianalisa dengan ratio =1. Seperti pada simulasi, hasil yang diperoleh pada test case bahwa dengan resolusi warna yang berbeda, maka representasi dari quadtree akan berbeda juga. Kondisi ini terjadi juga pada real test case. Jika citra dianalisa dengan resolusi yang rendah (2 warna), maka representasi quadtree akan nampak berbeda dibanding dengan analisa dengan resolusi yang lebih tinggi (16 warna). Semakin tinggi resolusinya, maka akan semakin komplek representasi quadtree yang muncul. Pada representasi 2 warna hanya menampilkan citra berwarna hitam dan putih, tetapi pada resolusi yang lebih tinggi (4, 8 atau 16 warna) akan nampak warna lain. Hal ini terjadi karena pada resolusi 2 warna, warna selain hitam dan putih tidak nampak. Sebagai contoh warna merah, hijau dan biru, pada resolusi 2 warna saja, warna-warna tersebut dianggap hitam semuanya. Sedangkan warna kuning, lightcyan, lightgray, dianggap sebagai warna putih. Dari hasil ini terlihat bahwa untuk memperoleh hasil analisa yang mendekati warna citra sesungguhnya diperlukan resolusi warna yang lebih tinggi. Semakin tinggi resolusi yang digunakan, berdampak semakin besar kapasitas penyimpanan file teks yang dibutuhkan. Gambar 9 merupakan citra yang akan dianalisa.
Gambar 9. Citra Untuk Tes Kasus Nyata
ST
Hasil analisa ditunjukkan pada tabel 4, tabel 5, tabel 6 dan tabel 7.
Tabel 5. Analisa Gambar 9 dengan 4 Warna Object Size = 32 Image Size = 32
Resolusi (color) 4 279 293 93 74 246 985
8 212 261 93 74 84 92 0 13 276 1105
A
Node Putih Node Hitam Node Merah Node Hijau Node Biru Node Magenta Node Yellow Node Lightcyan Node ‘(‘ Jumlah Node
Resolusi (color)
Tabel 7. Analisa Gambar 9 dengan 16 Warna Object Size = 32 Resolusi (color) Image Size = 32 16 Node Putih 154 Node Hitam 248 Node Merah 93 Node Hijau 26 Node Biru 84 Node Magenta 38 Node Yellow 73 Node Cyan 0 Node Brown 0 Node LightGray 0 Node DarkGray 46 LightBlue 0 LightGreen 66 LightCyan 13 LightRed 0 LightMagenta 63 Node ‘(‘ 301 Jumlah Node 1205
ST
IK
O
M
SU
Node Putih Node Hitam Node Merah Node Hijau Node ‘(‘ Jumlah Node
Object Size = 32 Image Size = 32
AY
Resolusi (color) 2 284 305 196 785
AB
Object Size = 32 Image Size = 32 Node Putih Node Hitam Node ‘(‘ Jumlah Node
Tabel 6. Analisa Gambar 9 dengan 8 Warna
R
Tabel 4. Analisa Gambar 9 dengan 2 Warna
Dari hasil analisa untuk resolusi 2 warna, kapasitas file penyimpanannya adalah 785 bytes, sedangkan pada resolusi 16 warna, kapasitas file penyimpanannya menjadi 1,205 bytes. Berdasarkan hasil penelitian, besarnya kapasitas penyimpanan, sama dengan banyaknya node yang muncul. Setiap node besarnya adalah 1 bytes.
AB
AY
A
SIMPULAN Representasi citra berwarna menggunakan metode region based quadtree dapat menghemat kapasitas file penyimpanan dari citra. Besarnya kapasitas file penyimpanan sebanding dengan jumlah node hasil representasi quadtree (1 karakter koding = 1 bytes). Semakin tinggi resolusi yang digunakan, semakin komplek representasi quadtree karena pada resolusi yang tinggi akan muncul warna-warna lain yang tidak muncul pada resolusi warna yang lebih rendah. Reduksi penyimpanan akan semakin berkurang seiring dengan meningkatnya resolusi citra yang digunakan. Pada kondisi worst case untuk - 2 warna diperoleh reduksi penyimpanan sebesar 62,65% - 4 warna diperoleh reduksi penyimpanan sebesar 53,14% - 8 warna diperoleh reduksi penyimpanan sebesar 47,43% - 16 warna diperoleh reduksi penyimpanan sebesar 42,67% Dapat dilakukan penelitian selanjutnya yaitu, proses ektraksi citra black-white pada real test case dibuat dengan perangkat lunak yang berbeda atau dengan bantuan menggunakan program aplikasi yang mendukung Sistem Informasi Geografi, misalnya ArcView dan ArcInfo. Citra ditingkatkan pada format lain seperti GIF dan JPEG. Serta resolusi dapat ditingkatkan menjadi 16 bit dan 24 bit (true color). Membuat suatu prosedur untuk mengekstrak kembali menjadi citra yang asli sesuai dengan warna yang ada dari hasil pengkodean citra yang dikirim. DAFTAR RUJUKAN Herlambang, S. 2003. Representasi Citra Berwarna Menggunakan Metode Region Based Quadtree. Yogyakarta: Magister Ilmu Komputer, Universitas Gadjah Mada.
R
Samet(1), H. 1990. Application of Spatial Data Structures. Canada: Addison – Wesley Publishing Company Inc.
SU
Samet(2), H. 1990. The Design and Analysis of Spatial Data Structures. Canada: Addison – Wesley Publishing Company Inc.
ST
IK
O
M
Samet,(3) H., and Webber, R.E. 1984. On Encoding Boundaries with Quadtrees. IEEE Transactions on Pattern Analysis and Machine Intelegence, vol. PAMI-6, No.3.