Perbaikan Kualitas Citra

Bab 7

Perbaikan Kualitas Citra

erbaikan kualitas citra (image enhancement) merupakan salah satu proses awal dalam pengolahan citra (image preprocessing). Perbaikan kualitas diperlukan karena seringkali citra yang dijadikan objek pembahasan mempunyai kualitas yang buruk, misalnya citra mengalami derau (noise) pada saat pengiriman melalui saluran transmisi, citra terlalu terang/gelap, citra kurang tajam, kabur, dan sebagainya. Melalui operasi pemrosesan awal inilah kualitas citra diperbaiki sehingga citra dapat digunakan untuk aplikasi lebih lanjut, misalnya untuk aplikasi pengenalan (recognition) objek di dalam citra

P

7.1 Lingkup Proses Perbaikan Kualitas Citra Yang dimaksud dengan perbaikan kualitas citra adalah proses mendapatkan citra yang lebih mudah diinterpretasikan oleh mata manusia. Pada proses ini, ciri-ciri tertentu yang terdapat di dalam citra lebih diperjelas kemunculannya [DUL97]. Secara matematis, image enhancement dapat diartikan sebagai proses mengubah citra f(x, y) menjadi f ’(x, y) sehingga ciri-ciri yang dilihat pada f(x, y) lebih ditonjolkan. Proses-proses yang termasuk ke dalam perbaikan kualitas citra [DUL97]: 1. Pengubahan kecerahan gambar (image brightness) 2. Peregangan kontras (contrast stretching) 3. Pengubahan histogram citra. 4. Pelembutan citra (image smoothing) 5. Penajaman (sharpening) tepi (edge). 6. Pewarnaan semu (pseudocolouring) 7. Pengubahan geometrik

Bab 7_Perbaikan Kualitas Citra

91

Beberapa operasi image enhancemnent (4 dan 5) dapat dipandang sebagai operasi penapisan untuk memperoleh citra yang lebih baik. Operasi penapisan adalah adalah operasi konvolusi citra f(x, y) dengan penapis h(x, y): f ‘(x, y) = h(x, y) * f(x, y)

(7.1)

atau dalam ranah frekuensi: F ’(u, v) = H(u, v)F(u, v)

(7.2)

Pada umumnya, f(x,y) sudah diketahui sehingga persoalannya adalah memilih h(x,y) sedemikian rupa sehingga f ’(x, y) merupakan citra yang menonjolkan ciri tertentu dari f(x, y).

7.2 Pengubahan Kecerahan Gambar (Image Brightness) Untuk membuat citra lebih terang atau lebih gelap, kita melakukan pengubahan kecerahan gambar. Kecerahan/kecemerlangan gambar dapat diperbaiki dengan menambahkan (atau mengurangkan) sebuah konstanta kepada (atau dari) setiap pixel di dalam citra. Akibat dari operasi ini, histogram citra mengalami pergeseran. Secara matematis operasi ini ditulis sebagai f(x, y)’ = f(x, y) + b

(7.3)

Jika b positif, kecerahan gambar bertambah, sebaliknya jika b negatif kecerahan gambar berkurang. Algoritma pengubahan kecerahan gambar ditunjukkan pada Algoritma 7.1. Citra masukan mempunyai 256 derajat keabuan yang nilai-nilainya dari 0 sampai 255. Intensitas pixel disimpan di dalam Image[0..N-1,0..M-1], sedangkan hasil pengubahan tetap disimpan di dalam citra Image. void ImageBrightness(citra Image, int N, int M, int b) /* Mengubah kecerahan citar Image yang berukuran N × M dengan penambahan intensitas setiap pixel sebesar b. */ { int i, j, n; for(i=0;i<=N-1;i++) for(j=0;j<=M-1;j++) Image[i][j]+=b; } Algoritma 7.1. Perhitungan histogram citra

92

Pengolahan Citra Digital

Nilai pixel hasil pengubahan mungkin ≤ derajat keabuan minimum (0) atau ≥ derajat keabuan maksimum (255). Karena itu, pixel tersebut perlu dilakukan clipping ke nilai keabuan minimum atau ke nilai keabuan maksimum. Sebagai contoh, Gambar 7.1(a) adalah citra Zelda (beserta histogramnya) yang tampak gelap, sedangkan Gambar 7.1(b) adalah citra Zelda (beserta histogramnya) yang lebih terang (nilai b = 80). Perhatikan histogramnya. Sebelum operasi penambahan kecerahan, histogramnya menumpuk di bagian kiri. Setelah penambahan kecerahan, histogramnya bergeser ke bagian kanan.

(b) Histogram citra Zelda (orisinil)

(a) Citra Zelda (orisinil)

(d) Histogram citra Zelda setelah penambahan kecerahan (c) Citra Zelda setelah penambahan kecerahan dengan b = 80 Gambar 7.1. Citra Zelda; Atas: sebelum operasi penambahan kecerahan terlihat agak gelap; Bawah: Zelda setelah operasi penambahan kecerahan dengan b = 80.


93

7.3 Peregangan Kontras Kontras menyatakan sebaran terang (lightness) dan gelap (darkness) di dalam sebuah gambar. Citra dapat dikelompokkan ke dalam tiga kategori kontras: citra kontras-rendah (low contrast), citra kontras-bagus (good contrast atau normal contrast), dan citra kontras-tinggi (high contrast). Ketiga kategori ini umumnya dibedakan secara intuitif. Citra kontras-rendah dicirikan dengan sebagian besar komposisi citranya adalah terang atau sebagian besar gelap. Dari histogramnya terlihat sebagian besar derajat keabuannya terkelompok (clustered) bersama atau hanya menempati sebagian kecil dari rentang nilai-nilai keabuan yang mungkin. Jika pengelompokan nilai-nilai pixel berada di bagian kiri (yang berisi nilai keabuan yang rendah), citranya cenderung gelap. Jika pengelompokan nilai-nilai pixel berada di bagian kanan (yang berisi nilai keabuan yang tinggi), citranya cenderung terang. Tetapi, mungkin saja suatu citra tergolong kontras-rendah meskipun tidak terlalu terang atau tidak terlalu gelap bila semua pengelompokan nilai keabuan berada di tengah histogram. Citra kontras-bagus memperlihatkan jangkauan nilai keabuan yang lebar tanpa ada suatu nilai keabuan yang mendominasi. Histogram citranya memperlihatkan sebaran nilai keabuan yang relatif seragam. Citra kontras-tinggi, seperti halnya citra kontras bagus, memiliki jangkauan nilai keabuan yang lebar, tetapi terdapat area yang lebar yang didominasi oleh warna gelap dan area yang lebar yang didominasi oleh warna terang. Gambar dengan langit terang denganlatar depan yang gelap adalah contoh citra kontras-tinggi. Pada histogramnya terlihat dua puncak, satu pada area nilai keabuan yang rendah dan satu lagi pada area nilai keabuan yang tinggi. Citra dengan kontras-rendah dapat diperbaiki kualitasnya dengan operasi peregangan kontras. Melalui operasi ini, nilai-nilai keabuan pixel akan merentang dari 0 sampai 255 (pada citra 8-bit), dengan kata lain seluruh nilai keabuan pixel terpakai secara merata. Gambar 7.2 memperlihatkan tiga buah citra Lena yang masing-masing memiliki kontras-rendah, kontras-tinggi, dan kontras-bagus. Ketiga histogram ini dihasilkan dengan program Adobe Photoshop.

94


(a) Citra Lena yang terlalu gelap (kontras rendah)

(b) Citra Lena yang terlalu terang (kontras tinggi)

(c) Citra Lena yang bagus (normal)

Histogram

Histogram

Histogram

(kontras bagus) Gambar 7. 2. Tiga buah citra Lena dengan tiga macam kontras.


95

Algoritma peregangan kontras adalah sebagai berikut: 1. Cari batas bawah pengelompokan pixel dengan cara memindai (scan) histogram dari nilai keabuan terkecil ke nilai keabuan terbesar (0 sampai 255) untuk menemukan pixel pertama yang melebihi nilai ambang pertama yang telah dispesifikasikan. 2. Cari batas atas pengelompokan pixel dengan cara memindai histogram dari nilai keabuan tertinggi ke nilai keabuan terendah (255 sampai 0) untuk menemukan pixel pertama yang lebih kecil dari nilai ambang kedua yang dispesifikasikan. 3. Pixel-pixel yang berada di bawah nilai ambang pertama di-set sama dengan 0, sedangkan pixel-pixel yang berada di atas nilai ambang kedua di-set sama dengan 255. 4. Pixel-pixel yang berada di antara nilai ambang pertama dan nilai ambang kedua dipetakan (diskalakan) untuk memenuhi rentang nilai-nilai keabuan yang lengkap (0 sampai 255) dengan persamaan:

s=

r − rmax × 255 rmin − rmax

(7.4)

yang dalam hal ini, r adalah nilai keabuan dalam citra semula, s adalah nilai keabuan yang baru, rmin adalah nilai keabuan terendah dari kelompok pixel, dan rmax adalah nilai keabuan tertinggi dari kelompok pixel (Gambar 7.3).

r rmax

s

0 Gambar 7. 3 Peregangan kontras

96


7.4 Pengubahan Histogram Citra Untuk memperoleh histogram citra sesuai dengan keinginan kita, maka penyebaran nilai-nilai intensitas pada citra harus diubah. Terdapat dua metode pengubahan citra berdasarkan histogram: 1. Perataan historam (histogram equalization) Nilai-nilai intensitas di dalam citra diubah sehingga penyebarannya seragam (uniform). 2. Spesifikasi histogram (histogram spesification) Nilai-nilai intensitas di dalam citra diubah agar diperoleh histogram dengan bentuk yang dispesifikasikan oleh pengguna. Kedua macam pengubahan histogram citra ini dibahas lebih rinci di dalam upabab 7.5 dan 7.6 di bawah ini.

7.5 Perataan Histogram Sebagaimana telah dijelaskan pada pembahasan terdahulu, histogram citra memberikan informasi tentang penyebaran intensitas pixel-pixel di dalam citra. Misalnya, citra yang terlalu terang atau terlalu gelap memiliki histogram yang sempit. Agar kita memperoleh citra yang baik, maka penyebaran nilai intensitas harus diubah. Teknik yang lazim dipakai adalah perataan histogram (histogram equalization). Tujuan dari perataan histogram adalah untuk memperoleh penyebaran histogram yang merata, sedemikian sehingga setiap derajat keabuan memiliki jumlah pixel yang relatif sama. Karena histogram menyatakan peluang pixel dengan derajat keabuan tertentu, maka rumus menghitung histogram ditulis kembali sebagai fungsi peluang

Pr ( rk ) =

nk n

(7.5)

yang dalam hal ini,

rk =

k L −1

,0≤k ≤L–1

(7.6)

yang artinya, derajat keabuan (k) dinormalkan terhadap derajat keabuan terbesar (L – 1). Nilai rk = 0 menyatakan hitam, dan rk = 1 menyatakan putih dalam skala keabuan yang didefinisikan.


97

Contohnya, jika L = 8, maka nilai-nilai rk dinyatakan di dalam tabel 7.1. Tabel 7.1 Nilai-nilai rk jika L = 8 k

rk

0 1 2 3 4 5 6 7

0/7 = 0 1/7 2/7 3/7 4/7 5/7 6/7 7/7 = 1

Yang dimaksud dengan perataan histogram adalah mengubah derajat keabuan suatu pixel (r) dengan derajat keabuan yang baru (s) dengan suatu fungsi transformasi T, yang dalam hal ini s = T(r). Gambar 7.4 memperlihatkan transformasi r menjadi s. Dua sifat yang dipertahankan pada transformasi ini: 1. Nilai s merupakan pemetaan 1 ke 1 dari r. Ini untuk menjamin representasi intensitas yang tetap. Ini berarti r dapat diperoleh kembali dari r dengan transformasi invers:

r = T −1 ( s )

, 0 ≤s≤1

(7.7)

2. Untuk 0 ≤ r i ≤ 1, maka 0 ≤ T(r) ≤ 1. Ini untuk menjamin pemetaan T konsisten pada rentang nilai yang diperbolehkan. s 1

sk = T(rk)

r 0

rk

1

Gambar 7. 4 Fungsi transformasi

98


Untuk fungsi histogram yang menerus, r

∫

s = T ( r ) = Pr ( w) dw

, 0 ≤r≤1

(7.8)

0

yang dalam hal ini w adalah peubah bantu. Dalam bentuk diskrit, nilai-nilai s diperoleh dengan persamaan berikut:

s k = T ( rk ) =

k

nj

k

∑ n ∑ P (r ) j =0

=

r

(7.9)

j

j =0

yang dalam hal ini, 0 ≤ rk ≤ 1, k = 0, 1, 2, …, L – 1 Contoh 7.1. [GON77] Misalkan terdapat citra yang berukuran 64 × 64 dengan jumlah derajat keabuan (L) = 8 dan jumlah seluruh pixel (n) = 64 × 64 = 4096: k 0 1 2 3 4 5 6 7

rk 0/7 = 0.00 1/7 = 0.14 2/7 = 0.29 3/7 = 0.43 4/7 = 0.57 5/7 = 0.71 6/7 = 0.86 7/7 = 1.00

nk 790 1023 850 656 329 245 122 81

Pr(rk ) = nk /n 0.19 0.25 0.21 0.16 0.08 0.06 0.03 0.02

Gambar 7.5 adalah histogram citra semula sebelum perataan. Pr(rk) 0.30 0.25 0.20 0.15 0.10 0.05 0 1/7

3/7

5/7

1

rk

Gambar 7. 5. Histogram citra sebelum perataan


99

Perhitungan perataan histogram adalah sbb: 0

∑ P (r ) = P (r ) = 0.19

s 0 = T ( r0 ) =

r

r

j

0

j= 0

s1 = T ( r1 ) =

1

∑ P (r ) = P (r ) + P (r ) = 0.19 + 0.25 = 0.44 r

r

j

0

r

1

j =0

s 2 = T ( r2 ) =

2

∑ P (r ) = P (r ) + P (r ) + P (r ) = 0.19 + 0.25 + 0.21 = 0.65 r

j

r

0

r

1

r

2

j =0

dan seterusnya, diperoleh: s3 = 0.81 s4 = 0.89 s5 = 0.95

s6 = 0.98 s7 = 1.00

Karena pada citra ini hanya ada 8 nilai intensitas, maka nilai-nilai sk harus dibulatkan ke nilai-nilai r yang terdekat: s0 = 0.19 lebih dekat ke nilai 1/7 ( = 0.14), maka s0 = 1/7 s1 = 0.44 lebih dekat ke nilai 3/7 ( = 0.43), maka s1 = 3/7 s2 = 0.65 lebih dekat ke nilai 5/7 ( = 0.71), maka s2 = 5/7 s3 = 0.81 lebih dekat ke nilai 6/7 ( = 0.86), maka s3 = 6/7 s4 = 0.89 lebih dekat ke nilai 6/7 ( = 0.86), maka s4 = 6/7 s5 = 0.95 lebih dekat ke nilai 7/7 ( = 1.00), maka s5 = 7/7 s6 = 0.98 lebih dekat ke nilai 7/7 ( = 1.00), maka s6 = 7/7 s7 = 1.00 lebih dekat ke nilai 7/7 ( = 1.00), maka s7 = 7/7 Hasil transformasinya : k

rk

sk

0 1 2 3 4 5 6 7

0 1/7 2/7 3/7 4/7 5/7 6/7 1

1/7 3/7 5/7 6/7 6/7 1 1 1

Terlihat dari contoh di atas hanya lima nilai intensitas yang terisi (1/7, 3/7, 5/7, 6/7, dan 1).

100


Notasi untuk tiap hasil transformasi didefinisi ulang menjadi: s0 = 1/7, s1 = 3/7, s2 = 5/7, s3 = 6/7, s4 = 1 Karena r0 = 0 dipetakan ke s0 = 1/7, terdapat 790 pixel hasil transformasi yang memiliki nilai intensitas 1/7. Selanjutnya, s1 = 3/7 memiliki 1023 pixel, s2 =5/7 memiliki 850 pixel. Juga, karena r3 dan r4 dipetakan ke nilai yang sama, s3 = 6/7, maka jumlah pixel yang bernilai 6/7 adalah 656 + 329 = 985. Jumlah pixel hasil transformasi diringkas pada tabel di bawah ini: sk

nk

Ps(sk) = nk/n

1/7 3/7 5/7 6/7 7/7

790 1023 850 656 + 329 = 958 245 + 122 + 81 = 448

0.19 0.25 0.21 0.23 0.11

¾

Gambar 7.5 adalah histogram citra hasil perataan. Ps(sk ) 0.30 0.25 0.20 0.15 0.10 0.05 0 1/7

3/7

5/7

1

sk

Gambar 7.5. Histogram citra hasil perataan

Gambar 7.6 memperlihatkan perataan histogram pada citra anjing collie. Pada mulanya citra collie terlihat terlalu gelap. Histogramnya menumpuk pada daerah derajat keabuan bagian kiri. Dengan teknik perataan histogram, citra anjing collie terlihat lebih bagus. Hal ini dapat dilihat juga pada histogramnya yang tersebar merata di seluruh daerah derajat keabuan.


101

Meskipun perataan histogram bertujuan menyebarkan secara merata nilai-nilai derajat keabuan, tetapi seringkali histogram hasil perataan tidak benar-benar tersebar secara merata (misalnya pada contoh di atas). Alasannya adalah : 1. Derajat keabuan terbatas jumlahnya. Nilai intensitas baru hasil perataan merupakan pembulatan ke derajat keabuan terdekat. 2. Jumlah pixel yang digunakan sangat terbatas. Agar hasil perataan benar-benar seragam sebarannya, maka citra yang diolah haruslah dalam bentuk malar (continue), yang dalam praktek ini jelas tidak mungkin.

(a) Kiri: citra anjing collie yang terlalu gelap; Kanan: histogramnya

(b) Kiri: citra anjing collie setelah perataan histogram; kanan: histogramnya Gambar 7. 6. Contoh perataan histogram pada citra anjing collie

102


Algoritma perataan histogram ditunjukkan pada Algoritma 7.2 [HEN95]. Citra masukan mempunyai 256 derajat keabuan yang nilai-nilainya dari 0 sampai 255. Intensitas pixel disimpan di dalam Image[0..N-1][0..M-1]. Histogram citra semula disimpan di dalam tabel Hist[0..255] yang bertipe riil. Histogram hasil perataan disimpan di dalam HistEq[0..255] yang bertipe integer. void PerataanHistogram(citra Image, int N, int M) /* Mengubah citra Image yang berukuran N × M dengan melakukan perataan histogram (histogram equalization). */ { int i, j; float sum, float Hist[256]; int HistEq[256]; /* histogram hasil perataan */ histogram(Image,N,M,Hist); /* hitung histogram citra */ for(i=0;i<256;i++) { sum=0.0; for (j=0;j<=i;j++) sum=sum+Hist[j]; HistEq[i]=floor(255*sum); } /* update citra sesuai histogram hasil perataan */ for(i=0;i<=N-1;i++) for(j=0;j<=M-1;j++) Image[i][j]=HistEq[Image[i][j]]; Algoritma 7.2 Perataan histogram citra

7.6 Spesifikasi Histogram Perataan histogram memetakan histogram citra semula menjadi histogram yang seragam. Bila histogram yang diinginkan tidak seragam, maka cara ini tidak dapat digunakan. Metode spesifikasi histogram (histogram spesification) memberikan cara menghasilkan histogram yang ditentukan oleh pengguna. Cara pembentukan histogramnya memanfaatkan sifat pada perataan histogram. Bila fungsi transformasi pada perataan histogram menghasilkan histogram semula menjadi histogram yang seragam, maka fungsi balikannya (inverse) memetakan histogram yang seragam menjadi histogram semula. Sifat ini dapat dimanfaatkan untuk mengubah histogram citra menjadi histogram lain yang tidak seragam. Dasar teorinya adalah sebagai berikut: misalkan Pr(r) dan Pz(z) masing-masing adalah histogram citra semula dan histogram yang diinginkan. Fungsi transformasi T mula-mula memetakan intensitas citra semula menjadi histogram yang seragam dengan cara perataan histogram,


103

r

∫

s = T ( r ) = Pr ( w) dw 0

Jika histogram yang diinginkan sudah dispesifikasikan, kita dapat melakukan perataan histogram pula dengan fungsi transformasi G: z

∫

v = G ( z ) = Pz ( w) dw

(7.10)

0

Balikan (invers) dari fungsi G,

z = G −1 ( v )

(7.11)

akan menghasilkan histogram yang diinginkan kembali. Dengan mengganti v dengan s pada persamaan yang terakhir,

z ≈ G −1 ( s )

(7.12)

maka kita dapat memperoleh nilai intensitas yang diinginkan. Hasil yang diperoleh merupakan hampiran karena kita mencoba menemukan nilai s yang transformasinya mendekati nilai z. Algoritma spesifikasi histogram adalah sebagai berikut: 1. Misalkan Pr(r) adalah histogram citra semula. Lakukan perataan histogram terhadap citra semula dengan fungsi transformasi T, r

∫

s = T ( r ) = Pr ( w) dw 0

Dalam bentuk diskrit, nilai-nilai s diperoleh dengan persamaan berikut:

s k = T ( rk ) =

k

nj

k

∑ n ∑ P (r ) =

j =0

r

j

j =0

2. Tentukan histogram yang diinginkan, misalkan Pz(z) adalah histogram yang diinginkan. Lakukan perataan histogram dengan fungsi transformasi G, z

∫

v = G ( z ) = Pz ( w) dw 0

104


Dalam bentuk diskrit, nilai-nilai v diperoleh dengan persamaan berikut:

v k = G ( zk ) =

k

nj

k

∑ n ∑ P (z ) =

j =0

z

j

j =0

3. Terapkan fungsi transformasi balikan, z = G-1(s) terhadap histogram hasil langkah 1. Caranya adalah dengan mencari nilai-nilai s yang memberi nilai z terdekat.

Dengan kata lain, histogram nilai-nilai intensitas pada citra semula dipetakan menjadi intensitas z pada citra yang diinginkan dengan fungsi z = G-1[T(r)] Ketiga langkah di dalam algoritma spesifikasi histogram di atas digambarkan dalam bagan pada Gambar 7.7. G-1 (s)

T(r) Pr(r)

Histogram Seragam

Pz(z)

Gambar 7. 7 Langkah-langkah metode spesifikasi histogram

Contoh 7.2. [GON77] Tinjau kembali citra yang berukuran 64 × 64 dengan jumlah derajat keabuan (L) = 8 dan jumlah seluruh pixel (n) = 64 × 64 = 4096. Tabel histogram citra semula dan tabel histogram yang diinginkan adalah sebagai berikut: Tabel histogram citra semula

Tabel histogram yang diinginkan

rk

nk

Pr(rk) = nk/n

zk

Pz(zk)

0/7 = 0.00 1/7 = 0.14 2/7 = 0.29 3/7 = 0.43 4/7 = 0.57 5/7 = 0.71 6/7 = 0.86 7/7 = 1.00

790 1023 850 656 329 245 122 81

0.19 0.25 0.21 0.16 0.08 0.06 0.03 0.02

0/7 = 0.00 1/7 = 0.14 2/7 = 0.29 3/7 = 0.43 4/7 = 0.57 5/7 = 0.71 6/7 = 0.86 7/7 = 1.00

0.00 0.00 0.00 0.15 0.20 0.30 0.20 0.15


105

Histogram citra semula dan histogram yang diinginkan diperlihatkan secara grafis pada Gambar 7.8. Pz(zk)

Pr(rk )

0.30

0.30

0.25

0.25

0.20

0.20

0.15

0.15

0.10

0.10

0.05

0.05

0 1/7

3/7

5/7

rk

1

0 1/7

Histogram citra semula:

3/7

5/7

1

zk

Histogram yang diinginkan

Gambar 7. 8 Histogram citra semula dan histogram yang diinginkan

Langkah-langkah pembentukan histogram adalah sebagai berikut: Langkah 1: Hasil perataan histogram terhadap citra semula,

s k = T ( rk ) =

k

nj

k

∑ n ∑ P (r ) j =0

=

r

j

j =0

telah dilakukan (lihat Contoh 7.1), dan ini hasilnya: rj → sk

nk

Ps(sk) = nk/n

r0 → s0 = 1/7 r1 → s1 = 3/7 r2 → s2 = 5/7 r3, r4 → s3 = 6/7 r5, r6, r7 → s4 = 7/7

790 1023 850 656 + 329 = 958 245 + 122 + 81 = 448

0.19 0.25 0.21 0.23 0.11

Langkah 2: Lakukan perataan terhadap histogram yang diinginkan, Pz(z), dengan persamaan

v k = G ( zk ) =

k

k

z

j =0

106

nj

∑ n = ∑ P (z ) j

j =0


Hasilnya adalah sbb: v0 = G(z0) = 0.00 v1 = G(z1) = 0.00 v2 = G(z2) = 0.00 v3 = G(z3) = 0.15

v4 = G(z4) = 0.35 v5 = G(z5) = 0.65 v6 = G(z6) = 0.85 v7 = G(z7) = 1.00

Langkah 3: Gunakan transformasi z = G-1(s) untuk memperoleh nilai z dari nilai s hasil perataan histogram. s0 = 1/7 ≈ 0.14 paling dekat dengan 0.15 = s1 = 3/7 ≈ 0.43 paling dekat dengan 0.35 = s2 = 5/7 ≈ 0.71 paling dekat dengan 0.65 = s3 = 6/7 ≈ 0.86 paling dekat dengan 0.85 = s4 = 1 ≈ 1.00 paling dekat dengan 1.00 =

G(z3), G(z4), G(z5), G(z6), G(z7),

jadi jadi jadi jadi jadi

G-1(0.14) = G-1(0.43) = G-1(0.71) = G-1(0.86) = G-1(1.00) =

z3 =1/7 z4 =4/7 z5 =5/7 z6 =6/7 z7 =1

Diperoleh pemetaan langsung sebagai berikut: r0 = 0 → z3 = 3/7 r1 = 1/7 → z4 = 4/7 r2 = 2/7 → z5 = 5/7 r3 = 3/7 → z6 = 6/7

r4 = 4/7 → z6 = 6/7 r5 = 5/7 → z7 = 1 r6 = 6/7 → z7 = 1 r7 = 1 → z7 = 1

Penyebaran pixel: Karena r0 = 0 dipetakan ke z3 = 3/7, maka terdapat 790 pixel hasil transformasi yang memiliki nilai intensitas 3/7. Karena r1 = 1/7 dipetakan ke z4 = 4/7, maka terdapat 1023 pixel hasil transformasi yang memiliki nilai intensitas 4/7. Karena r2 = 2/7 dipetakan ke z5 = 5/7, maka terdapat 850 pixel hasil transformasi yang memiliki nilai intensitas 5/7. Karena r3 = 3/7 dan r4 = 4/7 dipetakan ke z6 = 6/7, terdapat 245 + 122 + 81 = 448 pixel hasil transformasi yang memiliki nilai intensitas 1. Selanjutnya, tidak ada pixel yang mempunyai intensitas z0 = 0, z1 = 1/7, dan z2 = 2/7, karena tidak ada rk yang dipetakan ke nilai-nilai z tersebut. zk

nk

Pz(zk) = nk/n

0 1/7 2/7 3/7 4/7 5/7 6/7 1

0 0 0 790 1023 850 985 448

0.00 0.00 0.00 0.19 0.25 0.21 0.24 0.11


107

Histogram yang terbentuk: Pz(zk) 0.30 0.25 0.20 0.15 0.10 0.05 0 1/7

3/7

5/7

1

zk

Seperti yang sudah disebutkan sebelum ini, histogram yang diperoleh merupakan hampiran dari histogram yang dispesifikasikan karena kita mencoba menemukan nilai s yang transformasinya mendekati nilai z. Dalam praktek, mungkin terdapat ambiguitas pada nilai transformasi balikan, G1 (s). Dengan kata lain, nilai transformasi balikan dari s ke z tidak tunggal. Hal ini terjadi karena: (i) proses pembulatan G-1(s) ke nilai intensitas terdekat, atau (ii) terdapat nilai intensitas yang tidak terisi di dalam histogram spesifikasi. Solusi termudah untuk masalah ini adalah memilih nilai z yang terdekat dengan histogram yang dispesifikasikan. Algoritma Spesifikasi Histogram ditunjukkan pada Algoritma 7.3. Citra masukan mempunyai 256 derajat keabuan yang nilai-nilainya dari 0 sampai 255. Intensitas pixel disimpan di dalam Image[0..N-1][0..M-1]. Hasil perataan histogram dari citra semula disimpan kembali di dalam matriks Image[0..N1][0..M-1]. Histogram yang dispesifikasikan disimpan di dalam Spec[0..255]. Histogram hasil perataan dari Spec disimpan di dalam tabel SpecEq[0..255]. Histogram hasil transformasi balikan disimpan di dalam tabel InvHist[0..255] . void SpesifikasiHistogram(citra Image, int N, int M, float Spec[256]) /* Mengubah citra Image yang berukuran N × M berdasarkan histogram yang dispesifikasikan oleh pengguna (Spec). */ { float sum, Hist[256]; int i, j, minj, minval, HistEq[256], SpecEq[256], InvHist[256]; /* lakukan perataan histogram terhadap citra semula */ histogram(Image,N,M,Hist); /* hitung histogram citra */ for(i=0;i<256;i++) { sum=0.0;

108


for (j=0;j<=i;j++) sum=sum+Hist[j]; HistEq[i]=floor(255*sum); } /* lakukan perataan histogram terhadap citra Spec */ for(i=0;i<=255;i++) { sum=0.0; for (j=0;j<=i;j++) sum=sum+Spec[j]; SpecEq[i]=floor(255*sum); } /* lakukan transformasi balikan */ for(i=0;i<=N-1;i++) { minval=abs(HistEq[i] – SpecEq[0]); minj=0; for(j=0;j<=255;j++) if (abs(HistEq[i] – SpecEq[j]) < minval) { minval = abs(HistEq[i] – SpecEq[j]); minj=j; } InvHist[i]=minj; } /* update citra setelah pembentukan histogram */ for(i=0;i<=N-1;i++) for(j=0;j<=M-1;j++) Image[i][j]]=InvHist[Image[i][j]]; Algoritma 7.3 Pengubahan citra berdasarkan histogram yang dispesifikasikan

7.7 Pelembutan Citra (Image Smoothing) Pelembutan citra (image smoothing) bertujuan untuk menekan gangguan (noise) pada citra. Gangguan tersebut biasanya muncul sebagai akibat dari hasil penerokan yang tidak bagus (sensor noise, photographic grain noise) atau akibat saluran transmisi (pada pengiriman data). Gangguan pada citra umumnya berupa variasi intensitas suatu pixel yang tidak berkorelasi dengan pixel-pixel tetangganya. Secara visual, gangguan mudah dilihat oleh mata karena tampak berbeda dengan pixel tetangganya. Gambar 7.9 adalah citra Lena yang mengalami gangguan berupa spike atau speckle yang tampil pada gambar dalam bentuk bercak putih atau hitam seperti beras. Pixel yang mengalami gangguan umumnya memiliki frekuensi tinggi (berdasarkan analisis frekuensi dengan transformasi Fourier). Komponen citra yang berfrekuensi rendah umumnya mempunyai nilai pixel konstan atah berubah sangat lambat. Operasi pelembutan citra dilakukan untuk menekan komponen yang berfrekuensi tinggi dan meloloskan komponen yang berfrekuensi rendah.


109

Gambar 7.9. Citra Lena yang mengalami gangguan berupa spike

Operasi pelembutan dapat dilakukan pada ranah spsial maupun pada ranah frekuensi. Pada ranah spasial, operasi pelembutan dilakukan dengan mengganti intensitas suatu pixel dengan rata-rata dari nilai pixel tersebut dengan nilai pixelpixel tetangganya. Jadi, diberikan citra f(x,y) yang berukuran N × M. Citra hasil pelembutan, g(x,y), didefinisikan sebagai berikut:

1 g( x, y ) = d

m2

n2

∑∑ f (x + r, y + s)

(7.13)

r = m1 s = n1

yang dalam hal ini d adalah jumlah pixel yang terlibat dalam perhitungan ratarata. Gambar 7.10 memperlihatkan dua buah skema perata-rataan [GON77]. Pada skema pertama, tetangga sebuah pixel adalah pixel-pixel yang berjarak ∆x, sedangkan pada skema kedua tetangga sebuah pixel adalah pixel-pixel yang berjarak paling jauh √2 ∆x. Operasi perata-rataan di atas dapat dipandang sebagai konvolusi antara citra f(x,y) dengan penapis h(x,y): g(x,y) = f(x,y) ∗ h(x,y)

(7.14)

Penapis h disebut penapis rerata (mean filter). Dalam ranah frekuensi, operasi konvolusi tersebut adalah G(u,v) = F(u,v)H(u,v)

110

(7.15)


Tetangga pixel +

+

+

radius = ∆x

(a)

Tetangga pixel +

+

+

radius = √2 ∆x (b) Gambar 7. 10. Skema perata-rataan

Contoh penapis rerata yang berukuran 3 × 3 dan 2 × 2 adalah seperti di bawah ini (elemen yang bertanda • menyatakan posisi (0, 0) dari pixel yan dikonvolusi)):

1 / 9 1 / 9 1 / 9  (i) 1 / 9 • 1 / 9 1 / 9 1 / 9 1 / 9 1 / 9

• 1 / 4 1 / 4 (ii)    1 / 4 1 / 4

Algoritma pelembutan citra dengan penapis 3 × 3 ditunjukkan pada Algoritma 7.4. void PerataanCitra(citra Image, citra ImageResult, int N, int M) /* Melembutkan citra Image yang berukuran N × M dengan melakukan konvolusi citra Image dengan penapis rerata yang berukuran 3 × 3. Hasil pelembutna disimpan di dalam ImageResult. */ { int i, j; for (i=1; i<=N-1; i++)


111

for(j=1; j<=M-1; j++) { ImageResult[i][j]= Image[i-1][j-1] + Image[i-1][j] + Image[i-1,j+1]+ Image[i][j-1] + Image[i][j] + Image[i,j+1] + Image[i+1][j-1] + Image[i+1][j] + Image[i+1,j+1]; ImageResult[i][j]=ImageResult[i][j]/9; } }

Algoritma 7.4. Operasi pelembutan citra dengan penapis rerata 3 × 3.

Operasi penapisan ini mempunyai efek pemerataan derajat keabuan, sehingga gambar yang diperoleh tampak lebih kabur kontrasnya. Efek pengaburan ini disebut efek blurring. Gambar 7.11 adalah hasil pelembutan citra Lena dari Gambar 7.9 dengan penapis rata-rata 3 × 3. Efek pengaburan yang dihasilkan dari penapis rata-rata dapat dikurangi dengan prosedur pengambangan berikut:

 1  g( x, y ) =  d  f ( x, y ), 

m2 n2

1 m2 n2 f ( x + r, y + s ) jika f ( x, y ) − f ( x + r, y + s ) >T d r=m1 s=n1 r =m1 s= n1 lainnya (7.16)

∑∑

∑∑

dengan T adalah nilai ambang yang dispesifikasikan.

Gambar 7. 11. Citra Lena yang sudah dilembutkan dengan penapis rerata 3 × 3

112


Penapis h(x,y) pada operasi pelembutan citra disebut juga penapis lolos-rendah (low-pass filter), karena penapis tersebut menekan komponen yang berfrekuensi tinggi (misalnya pixel gangguan, pixel tepi) dan meloloskan komponen yang berfrekuensi rendah.

Penapis Lolos-Rendah Penapis rata-rata adalah salah satu penapis lolos-rendah yang paling sederhana. Aturan untuk penapis lolos-rendah adalah [GAL95]: 1. Semua koefisien penapis harus positif 2. Jumlah semua koefisien harus sama dengan 1 Jika jumlah semua koefisien lebih besar dari 1, maka konvolusi menghasilkan penguatan (tidak diinginkan). Jika jumlah semua koefisien kurang dari 1, maka yang dihasilkan adalah penurunan, dan nilai mutlak setiap pixel di seluruh bagian citra berkurang. Akibatnya, citra hasil pelembutan tampak lebih gelap. Ilustrasi konvolusi dengan penapis rata-rata 3 × 3 terhadap citra yang mengandung pixel derau diperlihatkan di bawah ini. Pixel yang mengalami gangguan dimisalkan bernilai 17, sedangkan nilai pixel tetangganya (yang tidak mengalami gangguan) bernila i rendah, misalkan 8. Efek dari penapis lolos-rendah adalah sbb: pixel-pixel tetangga tidak mengalami perubahan (kecuali bila terdapat perbedaan nilai atau gradien antara pixel-pixel yang bertetangga), sedangkan pixel derau nilainya turun menjadi 9:

8 8 8 8 8 17 8 8   8 8 8 8 (i) sebelum konvolusi

8 8 8 8 8 9 9 8   8 8 8 8 (ii) setelah konvolusi

Nilai 9 ini diperoleh dari hasil perhitungan konvolusi: f ’(1,1) = (8 + 8 + 8 + 8 + 17 + 8 + 8 + 8 + 8)/9 = 81/9 = 9 Selain dengan penapis rata-rata, penapis lolos-rendah lain yang dapat digunakan pada operasi pelembutan adalah:

1 / 16 1 / 8 1 / 16  (i)  1 / 8 1 / 4 1 / 8  1 / 16 1 / 8 1 / 16 


1 / 10 1 / 10 1 / 10 (ii) 1 / 10 1 / 5 1 / 10 1 / 10 1 / 10 1 / 10

1 / 16 1 / 8 1 / 16  (iii)  1 / 8 1 / 4 1 / 8  1 / 16 1 / 8 1 / 16 

113

Jika citra hasil penapisan lolos-rendah dikurangi dari citra semula (yang mengandung derau), maka yang dihasilkan adalah peningkatan relatif komponen citra yang berfrekuensi tinggi tanpa peningkatan komponen derau. Akibatnya, citra hasil pengurangan muncul lebih tajam dari citra semula. Ini dapat digunakan untuk menonjolkan bagian citra yang tidak jelas, misalnya tertutup oleh kabut atau awan. Aplikasi ini dapat diterapkan untuk mendapatkan citra kota Jakarta yang lebih bagus daripada citra kota Jakarta yang tertutup oleh kabut. Penapis lolos-rendah yang disebutkan di atas merupakan penapis lanjar (linear). Operasi pelembutan dapat juga dilakukan dengan menggunakan penapis nirlanjar, yaitu: a. Penapis minimum (min filter) b. Penapis maksimum (max filter) c. Penapis median (median filter) Penapis nirlanjar sebenarnya tidak termasuk kategori operasi konvolusi yang lazim. Cara kerja penapis tersebut berbeda dari penapis lanjar. Operasi dengan penapis nirlanjar dihitung dengan mengurutkan nilai intensitas sekelompok pixel, lalu mengganti nilai pixel yang sedang diproses dengan nilai tertentu dari kelompok tersebut (misalnya nilai median dari kelompok pixel, nilai maksimum atau nilai minimum dari kelompok pixel)

Penapis Median Penapis nirlanjar yang akan dijelaskan adalah penapis median. Penapis ini dikembangkan oleh Tukey. Pada penapis median, suatu “jendela” (window) memuat sejumlah pixel (ganjil). Jendela digeser titik demi titik pada seluruh daerah citra. Pada setiap pergeseran dibuat jendela baru. Titik tengah dari jendela ini diubah dengan nilai median dari jendela tersebut. Sebagai contoh, tinjau jendela berupa kelompok pixel (berbentuk kotak diarsir) pada sebuah citra pada Gambar 7.12(a). Pixel yang sedang diproses adalah yang mempunyai intensitas 35. Urutkan pixel-pixel tersebut: 9

10

10

10

10

10

11

12

35

Median dari kelompok tersebut adalah 10 (dicetak tebal). Titik tengah dari jendela (35) sekarang diganti dengan nilai median (10). Hasil dari penapis median diperlihatkan pada Gambar 7.12(b). Jadi, penapis median menghilangkan nilai pixel yang sangat berbeda dengan pixel tetangganya.

114


13

10

15

14

18

13

10

15

14

18

12

10

10

10

15

12

10

10

10

15

11

11

35

10

10

11

11

10

10

10

13

9

12

10

12

13

9

12

10

12

13

12

9

8

10

13

12

9

8

10

(a) Pixel bernilai 35 terkena derau

(b) 35 diganti dengan median dari

kelompok 3 × 3 pixel Gambar 7. 12. Penghilangan derau dengan penapis median 3 × 3.

Selain berbentuk kotak, jendela pada penapis median dapat bermacam-macam bentuknya, seperti palang (cross), lajur vertikal (vertical strip), atau lajur horizontal (horizontal strip). Gambar 7.13 adalah hasil pelembutan citra dari Gambar 7.9 dengan penapis median 3 × 3. Dari kedua contoh penapis (penapis rerata dan penapis median), dapat dilihat bahwa penapis median memberikan hasil yang lebih baik dibandingkan penapis rerata untuk citra yang mengalami gangguan dalam bentuk spike berupa bercakbercak putih.

Gambar 7. 13. Citra Lena yang dilembutkan dengan penapis median.


115

Cara lain yang dapat dilakukan pada pelembutan citra adalah merata-ratakan derajat keabuan setiap pixel dari citra yang sama yang diambil berkali-kali. Misalnya untuk gambar yang sama direkam dua kali, lalu dihitung intensitas ratarata untuk setiap pixel: 1 f ‘(x,y) = { f1(x, y) + f2(x, y) } (7.16) 2

7.8 Penajaman Citra (Image Sharpening) Operasi penajaman citra bertujuan memperjelas tepi pada objek di dalam citra. Penajaman citra merupakan kebalikan dari operasi pelembutan citra karena operasi ini menghilangkan bagian citra yang lembut. Operasi penajaman dilakukan dengan melewatkan citra pada penapis lolos-tinggi (high-pass filter). Penapis lolos-tinggi akan meloloskan (atau memperkuat) komponen yang berfrekuensi tinggi (misalnya tepi atau pinggiran objek) dan akan menurunkan komponen berfrekuensi rendah. Akibatnya, pinggiran objek telihat lebih tajam dibandingkan sekitarnya. Karena penajaman citra lebih berpengaruh pada tepi (edge) objek, maka penajaman citra sering disebut juga penajaman tepi (edge sharpening) atau peningkatan kualitas tepi (edge enhancement). Gambar 7.14 adalah citra Lena setelah ditajamkan gambarnya.

(a)

(b)

Gambar 7.14 (a) Citra Lena semula, (b) Citra Lena setelah penajaman

116


Selain untuk mempertajam gambar, penapis lolos-tinggi juga digunakan untuk mendeteksi keberadaan tepi (edge detection). Dalam hal ini, pixel-pixel tepi ditampilkan lebih terang (highlight) sedangkan pixel-pixel bukan tepi dibuat gelap (hitam). Masalah pendeteksian tepi akan dibahas dalam pokok bahasan tersendiri. Penapis Lolos-Tinggi Aturan penapis lolos-tinggi [GAL95]: 1. koefisien penapis boleh positif, negatif, atau nol 2. jumlah semua koefisien adalah 0 atau 1 Jika jumlah koefisien = 0, maka komponen berfrekuensi rendah akan turun nilainya, sedangkan jika jumlah koefisien sama dengan 1, maka komponen berfrekuensi rendah akan tetap sama dengan nilai semula. Contoh-contoh penapis lolos-tinggi:

 − 1 − 1 − 1   (i)  − 1 8 − 1  − 1 − 1 − 1 ∑= 0

 − 1 − 1 − 1   (ii)  − 1 9 − 1  − 1 − 1 − 1 ∑=1

 1 −2 1    (iv)  − 2 5 − 2   1 − 2 1  ∑= 1

 1 −2 1    (v)  − 2 4 − 2   1 − 2 1  ∑=0

 0 −1 0    (iii)  − 1 5 − 1  0 − 1 0  ∑=1  0 1 0   (vi) 1 − 4 1   0 1 0 ∑=0

Nilai koefisien yang besar di titik pusat penapis memainkan peranan kunci dalam proses konvolusi. Pada komponen citra dengan frekuensi tinggi (yang berarti perubahan yang besar pada nilai intensitasnya), nilai tengah ini dikalikan dengan nilai pixel yang dihitung. Koefisien negatif yang lebih kecil di sekitar titik tengah penapis bekerja untuk mengurangi faktor pembobotan yang besar. Efek nettonya adalah, pixel-pixel yang bernilai besar diperkuat, sedangkan area citra dengan intensitas pixel konstan tidak berubah nilanya. Gambar 7.15 mempelihatkan konvolusi dengan penapis lolos-tinggi, gambar (a) adalah citra yang tidak mempunyai pixel tepi, dan gambar (b) adalah citra yang mempunyai pixel tepi. Penapis lolos-tinggi yang digunakan adalah penapis (i) dan (ii). Karena koefisien penapis mengandung nilai negatif, maka konvolusi mungkin saja menghasilkan pixel bernilai negatif. Meskipun intensitas bernilai negatif menarik, tetapi kita tidak dapat menampilkannya. Untuk alasan terakhir ini, implementasi konvolusi men-set nilai negatif menjadi nilai 0. Cara lainnya adalah dengan mengambil nilai mutlaknya atau menskalakan semua nilai-nilai pixel secara menaik sehingga nilai yang paling negatif menjadi 0. Bab 7_Perbaikan Kualitas Citra

117

Citra semula:

4 4  4  4  4

Citra semula:

4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4  4 4 4 4 4 4 4 4 4 4 4 4

4 4  4  4  4

Kurva yang merepresentasikan citra:

4 4 8 8 8 8 4 4 8 8 8 8 4 4 8 8 8 8  4 4 8 8 8 8 4 4 8 8 8 8

Kurva yang merepresentasikan citra:

f(x,y)

f(x,y)

8

8

4

4

x

0

x

0

Hasil konvolusi dengan penapis (i):  x x x x x x x  x 0 0 0 0 0 x    x 0 0 0 0 0 x    x 0 0 0 0 0 x  x x x x x x x 

Hasil konvolusi dengan penapis (i): x x x x x x x  x 0 − 12 + 12 0 0 x     x 0 − 12 + 12 0 0 x     x 0 − 12 + 12 0 0 x   x x x x x x x 

Hasil konvolusi dengan penapis (ii) :

Hasil konvolusi dengan penapis (ii):

x x x x x x x 4 4 4 4 4  x 4 4 4 4 4  x 4 4 4 4 4  x x x x x x (a)

x x  x  x x 

x x x x x x  x 4 − 8 + 20 8 8   x 4 − 8 + 20 8 8   x 4 − 8 + 20 8 8  x x x x x x

x x  x  x x 

(b)

Gambar 7. 15 Hasil konvolusi dengan penapis lolos-tinggi: (a) citra yang tidak memiliki pixel tepi, (b) citra yang mengandung pixel-pixel tepi

118


Gambar 7.16 adalah contoh lain penajaman gambar terhadap citra girl, masingmasing dengan penapis (ii), (iii), dan (iv).

(a)

(b)

(c)

(d)

Gambar 7. 16 (a) citra girl sebelum penajaman; (b), (c), dan (d) masing-masing adalah hasil penajaman dengan penapis lolos-tinggi (ii), (iii), dan (iv)


119

7.9 Pewarnaan Semu Pewarnaan semu adalah proses memberi warna tertentu pada nilai-nilai pixel suatu citra skala-abu pada suatu citra berdasarkan kriteria tertentu, misalnya suatu warna tertentu untuk suatu interval derajat keabuan tertentu. Hal ini dilakukan karena mata manusia mudah membedakan banyak jenis warna.

7.10 Koreksi Geometrik Koreksi geometrik dilakukan pada citra yang memiliki gangguan yang terjadi pada waktu proses perekaman citra, misalnya pergeseran koordinat citra (translasi), perubahan ukuran citra, dan perubahan orientasi koordinat citra (skew). Proses koreksi geometri untuk meningkatkan kualitas citra tersebut disebut juga koreksi geometri. Koreksi geometri yang sederhana adalah dengan operasi geometri sederhana seperti rotasi, translasi, dan penskalaan citra. Gambar 7.17 kiri adalah citra kota San Fransisco yang condong (skew) ke kanan. Rotasi sejauh 6° berlawanan arah jarum jam menghasilkan perbaikan yang ditunjukkan pada Gambar 8.11 kanan.

(a)

(b)

Gambar 7. 17 (a) Citra San Fransisco yang condong ke kanan; (b) Hasil rotasi sejauh 6° berlawanan arah jarum jam.

120


Bab 8

Pendeteksian Tepi (Edge Detection)

eningkatan kualitas citra (image enhancement) bertujuan menghasilkan citra dengan kualitas yang lebih baik dibandingkan dengan citra semula. Langkah selanjutnya dalam pengolahan citra adalah analisis citra (image analysis). Analisis citra bertujuan mengidentifikasi parameter-parameter yang diasosiasikan dengan ciri (feature) dari objek di dalam citra, untuk selanjutnya parameter tersebut digunakan dalam menginterpretasi citra. Analisis citra pada dasarnya terdiri dari tiga tahapan: ekstrakasi ciri (feature extraction), segmentasi, dan klasifikasi.

P

Faktor kunci dalam mengekstraksi ciri adalah kemampuan mendeteksi keberadaan tepi (edge) dari objek di dalam citra. Setelah tepi objek diketahui, langkah selanjutnya dalam analisis citra adalah segmentasi, yaitu mereduksi citra menjadi objek atau region, misalnya memisahkan objek-objek yang berbeda dengan mengekstraksi batas-batas objek (boundary). Langkah terakhir dari analisis citra adalah klasifikasi, yaitu memetakan segmen-segmen yang berbeda ke dalam kelas objek yang berbeda pula.

8.1 Definisi Tepi Yang dimaksud dengan tepi (edge) adalah perubahan nilai intensitas derajat keabuan yang mendadak (besar) dalam jarak yang singkat (Gambar 8.1). Perbedaan intensitas inilah yang menampakkan rincian pada gambar. Tepi biasanya terdapat pada batas antara dua daerah berbeda pada suatu citra. Tepi dapat diorientasikan dengan suatu arah, dan arah ini berbeda-beda pada bergantung pada perubahan intensitas.

Bab 8_Pendeteksian Tepi (Edge Detection)

121

jarak perubahan intensitas

α = arah tepi

α

Gambar 8.1 Model tepi satu-matra

Perhatikan Gambar 8.2. Ada tiga macam tepi yang terdapat di dalam citra digital. Ketiganya adalah: 1. Tepi curam Tepi dengan perubahan intensitas yang tajam. Arah tepi berkisar 90°. 2. Tepi landai Disebut juga tepi lebar, yaitu tepi dengan sudut arah yang kecil. Tepi landai dapat dianggap terdiri dari sejumlah tepi-tepi lokal yang lokasinya berdekatan. 3. Tepi yang mengandung derau (noise) Umumnya tepi yang terdapat pada aplikasi computer vision mengandung derau. Operasi peningkatan kualitas citra (image enhancement) dapat dilakukan terlebih dahulu sebelum pendeteksian tepi. derajat keabuan

x

0

x

0

derajat keabuan

derajat keabuan

(b) tepi l andai

derajat keabuan

(a) Tepi curam

x

(d) break down tepi landai

4 4 4 4 4 4  4 4 4  4 4 4 4 4 4 (e) citra curam

0

x

(c) tepi curam dengan derau

8 8 8 8 8 4 4 5 6 7 8 8 8 8 8 8 8 8 4 4 5 6 7 8 8 8    8 8 8 8 8 4 4 5 6 7 8 8 8    8 8 8 8 8 4 4 5 6 7 8 8 8 8 8 8 8 8 4 4 5 6 7 8 8 8 dengan tepi (f) citra dengan tepi landai

Gambar 8. 2 Jenis-jenis tepi

122


8.2 Tujuan Pendeteksian Tepi Pendeteksian tepi merupakan langkah pertama untuk melingkupi informasi di dalam citra. Tepi mencirikan batas-batas objek dan karena itu tepi berguna untuk proses segmentasi dan identifikasi objek di dalam citra. Tujuan operasi pendeteksian tepi adalah untuk meningkatkan penampakan garis batas suatu daerah atau objek di dalam citra. Karena tepi termasuk ke dalam komponen berfrekuensi tinggi, maka pendeteksian tepi dapat dilakukan dengan penapis lolos-tinggi. Terdapat beberapa teknik yang digunakan untuk mendeteksi tepi, antara lain: 1. Operator gradien pertama (differential gradient) 2. Operator turunan kedua (Laplacian) 3. Operator kompas (compass operator)

8.3 Pendeteksian Tepi dengan Operator Gradien Pertama Perubahan intensitas yang besar dalam jarak yang singkat dipandang sebagai fungsi yang memiliki kemiringan yang besar. Kemiringan fungsi biasanya dilakukan dengan menghitung turunan pertama (gradient). Karena citra f(x,y) adalah fungsi dwimatra dalam bentuk diskrit, maka turunan pertamanya adalah secara parsial, masing-masing dalam arah-x dan dalam arah-y, sebagai berikut:

 ∂f    G x  ∇f =  ∂∂fx  =     G y   ∂y 

(8.1)

yang dalam hal ini,

Gx =

∂f ( x, y ) f ( x + ∆x, y ) − f ( x, y ) = ∂x ∆x

(8.2)

Gy =

∂f ( x , y ) f ( x , y + ∆y ) − f ( x, y ) = ∂y ∆y

(8.3)

Biasanya ∆x = ∆y = 1 , sehingga persamaan turunan pertama menjadi:

∂f ( x, y ) = f ( x + 1, y ) − f ( x , y ) ∂x ∂f ( x , y ) Gy = = f ( x, y + 1) − f ( x, y ) ∂y Gx =


(8.4) (8.5)

123

Titik-titik yang terlibat dalam perhitungan turunan pertama diperlihatkan pada Gambar 8.3. y (x-1,y+1)

(x ,y+ 1) (x+ 1,y+ 1)

(x-1,y)

(x,y)

(x+ 1,y)

(x-1,y-1) (x,y-1)

(x+ 1,y-1) x

Gambar 8.3 Titik -titik yang dilibatkan dalam perhitungan gradien

Kedua turunan tersebut dapat dipandang sebagai dua buah mask konvolusi sebagai berikut:

G1 ( x ) = [− 1 1]

1 G1 ( y ) =    − 1

dan

Contoh 8.1. [LOW91] Misalkan terdapat sebuah 5 × 5 citra dengan dua derajat keabuan sebagai berikut:

1 1  1  1 1

1 1 1 1 1 1 1 1 1 1 0 0  1 0 0 0 1 0 0 0

Hasil perhitungan gradien setiap pixel di dalam citra adalah sebagai berikut: Citra 1 1  1  1 1

124

1 1 1 1 1 1 1 1  1 1 0 0  1 0 0 0 1 0 0 0 

Gradien-x 0

0

0

0 *

0

0 0

0 0

0 0 * −1 0 *

0 0

0 −1

0

0 *

0

0 −1

0

0 *

*

Gradien-y 0 0 0 0 0 1 0 1 0 0 0 0 * * *

0 1 0 0 *

Arah gradien * * * * * * * * b b * * * * * ↔ * * * * ↔ * * * ¾ Pengolahan Citra Digital

Berdasarkan konvolusi dengan kedua mask tersebut, kita menghitung kekuatan tepi, G[f(x,y)], yang merupakan magnitudo dari gradien, dan arah tepi, α(x,y), untuk setiap pixel: G[f(x,y)]=

Gx + G y

α(x,y) = tan-1

2

2

Gy Gx

(8.6) (8.7)

Karena menghitung akar adalah persoalan rumit dan menghasilkan nilai riil, maka dalam praktek kekuatan tepi biasanya disederhanakan perhitungannya dengan menggunakan salah satu dari alternatif rumus berikut [DUL97]: (i) G[f(x,y)] = G x 2 + G y 2 , atau (ii) G[f(x,y)] = G x + G y , atau (iii) G[f(x,y)] = max{ G x 2 , G y 2 } , atau (iv) G[f(x,y)] = max{ G x , G y } . Dalam praktek, persamaan (ii) dan (iv) biasanya lebih disukai dan lebih mudah dikerjakan karena mengandung jumlah operasi aritmetika yang lebih sedikit. Hasil pendeteksian tepi adalah citra tepi (edges image) g(x,y), yang nilai setiap pixel-nya menyatakan kekuatan tepi:

g ( x , y ) = G [ f ( x , y )] Keputusan apakah suatu pixel merupakan tepi atau bukan tepi dinyatakan dengan operasi pengambangan berikut:

1, jika G [ f ( x , y )] ≥ T g( x, y) =  lainnya 0,

(8.8)

yang dalam hal ini T adalah nilai ambang, pixel tepi dinyatakan putih sedangkan pixel bukan tepi dinyatakan hitam. Gambar 8.4 adalah contoh hasil deteksi semua tepi citra Lena, citra Camera, dan citra botol.


125

Gambar 8.4 Deteksi semua tepi citra Lena, camera, dan botol

126


Selain operator gradien yang sudah disebutkan di atas, masih ada beberapa operator gradien pertama yang lain yang dapat digunakan untuk mendeteksi tepi di dalam citra, yaitu: (a) Operator gradien selisih-terpusat (center-difference):

Dx ( x, y ) =

∂f ( x , y ) f ( x + 1, y ) − f ( x − 1, y ) = ∂x 2

(8.9)

Dy ( x, y ) =

∂f ( x, y ) f ( x, y + 1) − f ( x, y − 1) = ∂y 2

(8.10)

yang ekivalen dengan mask berikut:

D2 ( x ) = [− 1 0 1]

dan

1 D2 ( y ) =  0  − 1

(b) Operator Sobel Tinjau pengaturan pixel di sekitar pixel (x,y):

a1 a2  a0 a ( x, y) a  3  7  a 6 a5 a4  Operator Sobel adalah magnitudo dari gradien yang dihitung dengan M=

s 2x + s 2y

yang dalam hal ini, turunan parsial dihitung dengan

s x = ( a2 + ca3 + a 4 ) − (a 0 + ca 7 + a 6 )

(8.11)

s y = ( a 0 + ca1 + a 22 ) − ( a 6 + ca5 + a4 )

(8.12)

dengan konstanta c = 2. Dalam bentuk mask, sx dan sy dapat dinyatakan sebagai

 − 1 0 1 S x =  − 2 0 2  − 1 0 1

dan


2 1 1  Sy =  0 0 0  − 1 − 2 − 1 127

Arah tepi dihitung dengan persamaan

S α(x,y) = tan-1  y  Sx

  

(8.13)

Contoh 8.2. Contoh berikut ini memeperlihatkan pendeteksian tepi dengan operator Sobel. Konvolusi pertama dilakukan terhadap pixel yang bernilai 1 (di titik pusat mask):

3 2  3  4  2

4 2 5 1 1 6 4 2 5 7 1 3  2 5 7 1 5 1 3 2

* * * * *  * 18          

(i) citra semula

(ii) hasil konvolusi

Nilai 18 pada citra hasil konvolusi diperoleh dengan perhitungan berikut: Sx = (3)(-1) + (2)(-2) + (3)(-1) + (2)(1) + (6)(2) + (7)(1) = 11 Sy = (3)(1) + (4)(2) + (2)(1) + (3)(-1) + (5)(-2) + (7)(-1) = -7 M=

s 2x + s 2y =

Pada contoh ini, nilai M =

112 + ( −7 ) 2 ≅ S x + S y = 11 + − 7 = 18 s 2x + s 2y dihampiri dengan menghitung

M ≅ Sx + S y .

¾

Contoh 8.3. Di bawah ini contoh lain pendeteksian tepi dengan operator Sobel, dimana hasil konvolusi diambangkan dengan T = 12. Citra: 0 0  0  0 0  0

0 0 0 0 0 2 0 3 3 0 0 1 0 0 0 2 4 3  0 2 0 2 4 3 3 2 3  0 1 3 3 4 3 3 3 3 1 0 4 3 3 2 4 3 2  0 1 2 3 3 4 4 4 3

128

gradien - x + gradien - y :

* *  *  * *  *

* * * * * * 10 14 12 14 4 *  6 8 10 20 16 12 6 0 *  4 10 14 10 2 4 2 4 * 2 12 12 2 2 4 6 8 *  * * * * * * * * * * 4

* 6

* 4


Hasil pengambangan dengan T = 12:

* *  *  * *  *

* * * * * * 10 14 12 14 4 *  6 8 10 20 16 12 6 0 *  4 10 14 10 2 4 2 4 * 2 12 12 2 2 4 6 8 *  * * * * * * * * * * 4

* 6

* 4

¾

(c) Operator Prewitt Persamaan gradien pada operator Prewitt sama seperti operator Sobel, tetapi menggunakan nilai c = 1:

 − 1 0 1 Px =  − 1 0 1  − 1 0 1

dan

1 1 1  Py =  0 0 0  − 1 − 1 − 1

(d) Operator Roberts Operator Roberts sering disebut juga operator silang (gambar 8.5). Gradien Roberts dalam arah-x dan arah-y dihitung dengan rumus:

R+ ( x , y ) = f ( x + 1, y + 1) − f ( x , y )

(8.14)

R− ( x , y ) = f ( x, y + 1) − f ( x + 1, y )

(8.15)

f(x, y+1)

f(x, y)

f(x + 1, y+1)

f(x + 1, y)

x Gambar 8. 5 Operator silang


129

Operator R+ adalah hampiran turunan berarah dalam arah 45°, sedangkan Radalah hampiran turunan berarah dalam arah 135°. Dalam bentuk mask konvolusi, operator Roberts adalah:

1 0   0 1 R+ =  dan R− =    0 − 1  − 1 0

Khusus untuk operator Roberts, arah tepi dihitung dengan rumus

α ( x, y ) =

π R + tan −1 ( − ) 4 R+

(8.17)

Sedangkan kekuatan tepi umumnya dihitung dengan rumus G[f(x,y)] = R+ + R−

Contoh 8.4. Contoh berikut ini memeperlihatkan pendeteksian tepi dengan operator Roberts.

3 2  3  4  2

4 2 5 1 1 6 4 2 5 7 1 3  2 5 7 1 5 1 3 2

(i) citra semula

4 5  2  1  *

3 3 6 * 7 8 2 * 5 4 4 *  1 8 7 * * * * *

(ii) hasil konvolusi

Nilai 4 pada pojok kiri atas pada citra hasil konvolusi diperoleh dengan perhitungan sebagai berikut: f ’[0,0] = ¦ 3 – 1 ¦ + ¦ 4 – 2 ¦ = 4

8.4 Pendeteksian Tepi dengan Operator Turunan Kedua Operator turunan kedua disebut juga operator Laplace. Operator Laplace mendeteksi lokasi tepi lebih akurat khususnya pada tepi yang curam. Pada tepi yang curam, turunan keduanya mempunyai persilangan nol (zero-crossing), yaitu titik di mana terdapat pergantian tanda nilai turunan kedua (Gambar 8.6),

130


sedangkan pada tepi yang landai tidak terdapat persilangan nol. Persilangan nol merupakan lokasi tepi yang akurat. Turunan kedua fungsi dengan dua peubah adalah:

∂2 f ∂2 f + ∂x 2 ∂y 2

∇2 f =

(8.18)

f(x)

∂f /∂x

∂ 2f /∂x2

•

(a) Tepi landai

(b) Tepi curam

Gambar 8. 6 Deteksi tepi dengan operator turunan kedua

Dengan menggunakan definisi hampiran selisih-mundur (backward difference approximation):

G3 ( x) =

∂f ( x, y ) f ( x , y ) − f ( x − ∆x, y ) = ∂x ∆x

(8.19)

G3 ( y) =

∂f ( x, y ) f ( x , y ) − f ( x , y − ∆y ) = ∂y ∆y

(8.20)


131

maka

∇2 f =

∂2 f ∂2 f + ∂x 2 ∂y 2

= G1 (G3 ( x )) + G1 (G3 ( y )) 1 1 = G1 ( f ( x , y )) − G1 ( f ( x − ∆x , y )) + G1 ( f ( x , y )) − G1 ( f ( x , y − ∆y )) ∆x ∆y 1 f ( x + ∆x , y ) − f ( x , y ) − f ( x, y ) + f ( x − ∆ x, y ) { } ∆x ∆x 1 f ( x , y + ∆y ) − f ( x , y ) − f ( x , y ) + f ( x, y − ∆y ) + { } ∆y ∆y =

=

f ( x + ∆x , y ) − 2 f ( x, y ) + f ( x − ∆ x, y ) ( ∆x ) 2

+

f ( x , y + ∆y ) − 2 f ( x , y ) + f ( x, y − ∆ y ) ( ∆y )2

Dengan mengasumsikan ∆x = ∆y = 1, maka diperoleh:

∇2 f ( x , y ) = f ( x + 1, y ) − 2 f ( x , y ) + f ( x − 1, y ) + f ( x , y + 1) − 2 f ( x, y ) + f ( x, y − 1) = f ( x , y − 1) + f ( x − 1, y ) − 4 f ( x, y ) + f ( x + 1, y ) + f ( x, y + 1) (8.21) atau dapat dinyatakan sebagai mask:  0 1 0 1 − 4 1     0 1 0 Selain mask di atas, masih ada dua hampiran operator Laplace yang lain, yaitu

 − 1 − 1 − 1  1 −2 1   − 1 8 − 1 dan  − 2 4 − 2       1 − 2 1   − 1 − 1 − 1

132


Kadang-kadang diinginkan memberi bobot yang lebih pada pixel tengah di antara pixel tetangganya. Operator Laplace yang digunakan untuk tujuan ini adalah

4 1 1  4 − 20 4    4 1   1 Operator Laplace termasuk ke dalam penapis lolos-tinggi sebab jumlah seluruh koefisiennya nol dan koefisiennya mengandung nilai negatif maupun positif.

Contoh 8.5. [GAL90] Contoh berikut ini memperlihatkan pendeteksian tepi vertikal dengan operator Laplace:

4 4  4  4 4

4 4 8 8 8 8 4 4 8 8 8 8  4 4 8 8 8 8  4 4 8 8 8 8 4 4 8 8 8 8

* *  *  * *

* * * * * * 0 + 4 − 4 0 0 *  0 + 4 − 4 0 0 *  0 + 4 − 4 0 0 * * * * * * * (ii) Hasil konvolusi

(i) Citra semula 8

+4

4

0

0

-4

Satu baris dari hasil pendeteksian tepi: 0 +4

–4 0 0

Pada contoh di atas, persilangan nol bersesuaian dengan tepi pada citra semula, yang terdapat pada titik tengah antara dua buah pixel yang bersesuaian. Pixel tepi seharusnya ditandai secara konsisten, apakah pixel di sebelah kiri atau di sebelah kanan garis “|”. ¾


133

Contoh 8.6. [GAL90] Pendeteksian tepi diagonal (miring) dengan operator Laplace: 4 4  4  4 4

4 8 8 8 8 8 8 4 4 8 8 8 8 8  4 4 4 8 8 8 8  4 4 4 4 8 8 8 4 4 4 4 4 8 8

* *  *  * *

* 0 0 0 *

* * +8 − 4 0 0 0 *  0 + 8 − 4 0 0 *  0 0 + 8 − 4 0 * * * * * * * *

*

*

*

(ii) Hasil konvolusi

(i) Citra semula

¾

Contoh 8.7. Pendeteksian tepi landai dengan operator Laplace:

2 2  2  2  2

2 2 5 8 8 8 8 2 2 5 8 8 8 8 2 2 5 8 8 8 8  2 2 5 8 8 8 8 2 2 5 8 8 8 8 (i) Citra semula

* *  *  * *

* * * 0 + 3 0 − 3 0 0 * 0 + 3 0 − 3 0 0 *  0 + 3 0 − 3 0 0 * * * * * * * * *

*

*

*

(ii) Hasil konvolusi

Satu baris dari hasil pendeteksian tepi: 0 +3 0 –3 0 Pada contoh di atas tidak terdapat persilangan nol; lokasi tepi yang sesungguhnya ditentukan secara interpolasi. ¾

Kadangkala pendeteksian tepi dengan operator Laplace menghasilkan tepi-tepi palsu yang disebabkan oleh gangguan pada gambar [DUL97]. Untuk mengurangi kemunculan tepi palsu, citra disaring dulu dengan fungsi Gaussian (Gambar 8.7).

134


f(x,y)

dihaluskan dengan fungsi Gauss, G(x,y)

h(x,y)

operator Laplace, ∇2

k(x,y) Gambar 8. 7 Skema pendeteksian tepi untuk citra yang mengalami gangguan.

Berdasarkan skema pada Gambar 8.7:

k ( x , y ) = ∇ 2h ( x, y )

(8.22)

h ( x, y ) = f ( x , y ) * G ( x, y )

(8.23)

dan

maka dapat dibuktikan bahwa

∇2 [ f ( x , y ) * G ( x , y )] = f ( x , y ) * ∇ 2G ( x, y )

(8.24)

k ( x , y ) = f ( x , y ) * ∇ 2G ( x, y )

(8.25)

Jadi,

yang dalam hal ini,

 x 2 + y 2 − 2σ 2  −  e ∇ G ( x, y ) =  σ4   2


( x 2 + y2 ) 2σ 2

(8.26)

135

Fungsi ∇2G(x,y) merupakan turunan kedua dari fungsi Gauss, kadang-kadang disebut juga fungsi Laplacian of Gaussian (LoG) atau fungsi topi orang Mexico (Mexican Hat), karena bentuk kurvanya seperti topi Meksiko. Jadi, untuk mendeteksi tepi dari citra yang mengalami gangguan, kita dapat melakukan salah satu dari dua operasi ekivalen di bawah ini: 1.

Konvolusi citra dengan fungsi Gauss G(x,y), kemudian lakukan operasi Laplacian terhadap hasilnya, atau

2.

Konvolusi citra dengan penapis LoG.

Contoh penapis LoG yang berukuran 5 × 5:

0 −1 0 0 0  0 −1 − 2 −1 0     − 1 − 2 16 − 2 − 1    0 −1 − 2 −1 0   0 0 −1 0 0 

Hasil pendeteksian tepi dengan operator Laplace dan Laplacian of Gaussian diperlihatkan pada Gambar 8.8.

(a)

136

(b)


(c)

(d)

Gambar 8. 8 (a) citra botol; (b) Laplace; (c) Laplace dengan bobot lebih; (d) Laplacian of Gaussian (LoG)

8.5 Pendeteksian Tepi dengan Operator Kompas Operator kompas (compass operator) digunakan untuk mendeteksi semua tepi dari berbagai arah di dalam citra. Operator kompas yang dipakai untuk pendeteksian tepi menampilkan tepi dari 8 macam arah mata angin: Utara, Timur Laut, Timur, Tenggara, Selatan, Barat Daya, dan Barat Laut. Pendeteksian tepi dilakukan dengan mengkonvolusikan citra dengan berbagai mask kompas, lalu dicari nilai kekuatan tepi (magnitude) yang terbesar dan arahnya. Jika misalnya digunakan sebanyak p buah mask kompas dan nilai kekuatan tepi pada pixel (x, y) untuk semua mask adalah G1[f(x,y)], G2[f(x,y)], …, Gp[f(x,y)], maka besar kekuatan tepi adalah:

G [ f ( x , y )] = max{Gi [ f ( x , y )] i = 1,2,..., p}

(8.27)

i

Jika mask k adalah mask yang memberikan kekuatan terbesar, maka arah tepi ditentukan dari mask k tersebut. Operator kompas yang dipakai untuk pendeteksian tepi menampilkan tepi dari 8 macam arah mata angin:


137

Utara 1 1 1  1 −2 1     − 1 − 1 − 1

Timur Laut 1 1 1  − 1 − 2 1    − 1 − 1 1

Timur − 1 1 − 1 − 2   − 1 1

1 1 1

Tenggara  − 1 − 1 1  − 1 − 2 1    1 1 1

Selatan  − 1 − 1 − 1  1 −2 1     1 1 1 

Barat Daya 1 − 1 − 1 1 − 2 − 1   1 1 1 

Barat 1 1 − 1 1 − 2 − 1   1 1 − 1

Barat Laut 1 1 1 1 − 2 − 1   1 − 1 − 1

Operator kompas yang tersedia dapat juga digunakan untuk mendeteksi tepi dalam arah tertentu saja. Misalnya diinginkan mendeteksi tepi dalam arah horizontal dan vertikal, seperti hasil pendeteksian tepi citra San Fransisco (Gambar 8.9) dan citra WTC1109.

Tepi horizontal

Tepi vertikal

Gambar 8. 9 Deteksi tepi horizontal dan vertikal dari citra San Fransisco

138


Gambar 8. 10. Citra WTC1109

Tepi vertikal


139

Tepi horizontal Gambar 8.10 (lanjutan).

140


Bab 9

Kontur dan Representasinya

endeteksi tepi menghasilkan citra tepi yang berupa citra biner (pixel tepi berwarna putih, sedangkan pixel bukan-tepi berwarna hitam). Tetapi, tepi belum memberikan informasi yang berguna karena belum ada keterkaitan antara suatu tepi dengan tepi lainnya. Citra tepi ini harus diproses lebih lanjut untuk menghasilkan informasi yang lebih berguna yang dapat digunakan dalam mendeteksi bentuk-bentuk sederhana (misalnya garis lurus, lingkaran, elips, dan sebagainya) pada proses analisis citra.

P

Rangkaian pixel-pixel tepi yang membentuk batas daerah (region boundary) disebut kontur (contour) [JAI95]. Kontur dapat terbuka atau tertutup. Kontur tertutup berkoresponden dengan batas yang mengelililingi suatu daerah lihat Gambar 9.1(a). Pixel-pixel di dalam daerah dapat ditemukan dengan algoritma pengisian (filling algorithm). Batas daerah berguna untuk mendeskripsikan bentuk objek dalam tahap analisis citra (misalnya untuk mengenali objek). Kontur terbuka dapat berupa fragmen garis atau bagian dari batas daerah yang tidak membentuk sirkuit (Gambar 9.1(b)).

(a)

(b) Gambar 9.1 (a) kontur tertutup, (b) kontur terbuka

Bab 9_Kontur dan Representasinya

141

9.1 Representasi Kontur Representasi kontur dapat berupa senarai tepi (edge list) atau berupa kurva. Senarai tepi merupakan himpunan terurut pixel-pixel tepi. Representasi kontur ke dalam kurva merupakan representasi yang kompak dan mangkus untuk analisis citra. Misalnya, rangkaian pixel tepi yang membentuk garis dapat direpresentasikan hanya dengan sebuah persamaan garis lurus. Representasi semacam ini menyederhanakan perhitungan selanjutnya seperti arah dan panjang garis. Kode Rantai Kode rantai (chain code)adalah notasi untuk mengkodekan senarai tepi yang membentuk batas daerah. Kode rantai menspesifikasikan arah setiap pixel tepi di dalam senarai tepi. Arah yang digunakan adalah 8 arah mata angin seperti yang terlihat pada pada Gambar 9.2 (a). 0

7

batas

1

6

2

objek titik awal

5

4

(a)

3

(b)

Gambar 9.2 (a) Kode rantai, (b) representasi batas objek dengan kode rantai.

Dimulai dari sebuah pixel tepi dan searah jarum jam, arah setiap pixel tepi yang membentuk batas objek dikodekan dengan salah satu dari delapan kode rantai. Kode rantai merepresentasikan batas objek dengan koordinat pixel tepi pertama lalu diikuti dengan senarai kode rantai. Karena ada 8 arah, maka cukup 3 bit untuk mengkodekan setiap arah. Gambar 9.3 memperlihatkan contoh pengkodean batas objek dengan kode rantai.

142


Titik awal A

1 0

2

2

2

2

2

2

2

3

0

3

2

7

2 4

7

4 6

6

6

6

6

6

6

6

6

6

4

Kode rantai: (A), 22222332244466666666667700221 Gambar 9.3 Contoh pengkodean batas objek dengan kode rantai.

Pencocokan Kurva Kurva yang merepresentasikan kontur dicari dengan teknik pencocokan kurva (curve fitting). Ada dua macam teknik pencocakan kurva: interpolasi dan penghampiran (approximation). Interpolasi kurva adalah mencari kurva yang melalui semua pixel tepi, sedangkan penghampiran kurva adalah mencari kurva yang paling dekat melalui pixel-pixel tepi, tetapi tidak perlu melalui semua pixel tersebut. Di dalam bab ini kita hanya membahas teknik pencocokan kurva dengan penghampiran. Salah satu metode penghampiran kurva yang populer dalam pengolahan citra adalah transformasi Hough. Transformasi Hough akan dibahas dalam upa-bab 9.3 di bawah ini.

9.2 Transformasi Hough Transformasi Hough menspesifikasikan kurva dalam bentuk parametrik. Kurva dinyatakan sebagai bentuk parametrik (x(u), y(u))


143

dari parameter u. Bentuk parametrik tersebut menspesifikasikan titik-titik sepanjang kurva dari titik awal kurva p1 = (x(u1), y(u1) ke titik akhir p2 = (x(u2), y(u1). Panjang kurva adalah u2

L=

∫

u1

2

2

 dx   dy    +   du  du   du 

(9.1)

Transformasi Hough menggunakan mekanisme voting untuk mengestimasi nilai parameter. Setiap titik di kurva menyumbang suara untuk beberapa kombinasi parameter. Parameter yang memperoleh suara terbanyak terpilih sebagai pemenang. Pada awalnya, Transformasi Hough digunakan untuk mendeteksi garis lurus. Namun, ia juga dapat digunakan untuk mendeteksi kurva sederhana lainnya seperti lingkaran dana elips. Pembahasan dimulai dengan transformasi Hough untuk mendeteksi keberadaan garis lurus di dalam citra tepi.

Mendeteksi Garis Lurus Misalkan citra tepi berukuran n = N × M pixel. Cara yang paling sederhana mendeteksi garis lurus adalah menemukan semua garis yang ditentukan oleh dua buah pixel dan memeriksa apakah sebagian dari pixel tepi termasuk ke dalam garis tersebut (cara exhaustive search). Jumlah maksimum garis yang dideteksi adalah n (n – 1)/2. Karena setiap pixel harus diperiksa apakah ia termasuk ke dalam suatu garis, maka kompleksitas algoritma pendeteksian garis lurus untuk kasus terburuk adalah O(n3). Untuk aplikasi praktis, jelas metode pendeteksian dengan cara ini tidak mangkus. Transformasi Hough mengurangi kompleksitas komputasi dengan menggunakan bentuk parametrik dan menggunakan mekanisme pemungutan suara terbanyak (voting) untuk menentukan nilai parameter yang tepat. Tinjau persamaan garis lurus: y = mx + c

(9.2)

Dalam bentuk parametrik, setiap garis dinyatakan sebagai (m’, c’) di dalam ruang parameter m-c. Persamaan 9.2 dapat ditulis menjadi c = y – mx

(9.3)

Sembarang titik (x,y) pada bidang planar X-Y berkoresponden dengan sebuah garis lurus pada ruang parameter m–c.

144


Tinjau 3 buah titik pada sebuah garis lurus pada Gambar 9.4(a). Sembarang garis yang melalui titik (x1,y1) berkoresponden dengan garis c = y1 – mx1 pada ruang parameter m-c. Begitu juga, sembarang garis lurus yang melalui (x2,y2) berkoresponden dengan garis c = y2 – mx2 dan sembarang garis lurus yang melalui (x3,y3) berkoresponden dengan garis c = y3 – mx3 pada ruang m-c. Perpotongan (m’,c’) dari ketiga garis pada ruang m-c tersebut menentukan garis unik yang melalui (xi,yi), i = 1, 2, 3, di bidang X-Y. Dengan cara ini, maka setiap pixel pada garis lurus di bidang citra berkoresponden dengan sejumlah garis lurus yang melalui satu ititik tertentu di ruang parameter m-c. Sifat ini dimanfaatkan untuk mendeteksi garis lurus. Jika setiap pixel tepi melakukan “pemungutan suara” pada ruang parameter, maka keberadaan garis lurus pada citra ditandai dengan penumpukan suara pada tempat-tempat tertentu di ruang parameter. y

c

c = y - mx 1

c = y - mx 3

(x1,y1) (x2,y2) (x3,y3)

c = y - mx 2 x

(a)

m

(b)

Gambar 9. 4 (a) Garis lurus pada ruang X-Y; (b) representasinya dalam ruang parameter m-c.

Karena itu, prosedur mendeteksi garis lurus adalah sebaga i berikut: 1. Ruang parameter didiskritkan sebagai matriks P(m, c), yang dalam hal ini m1 ≤ m ≤ mK dan c1 ≤ c ≤ cL. 2. Tiap elemen pada ruang parameter diasumsikan sebagai akumulator. Inisialisasi setiap elemen P(m, c) dengan 0. 3. Untuk setiap pixel tepi (xi, yi) –pixel tepi dicirikan mempunyai nilai intensitas putih (1) dalam skala 0 - 1)– hitung nilai c = yi – mxi. Untuk setiap nilai parameter m, m1 ≤ m ≤ mK, yang berkoresponden dengan nilai c, maka elemen matriks P(m, c) yang bersesesuaian dinaikkan satu: P(m, c) = P(m, c) + 1

(9.4)

Dengan kata lain, tambahkan satu suara pada ruang parameter m-c.


145

4. Ulangi langkah 3 sampai seluruh pixel di dalam citra tepi ditelusuri. 5. Pada akhir prosedur, tiap elemen matriks P(m, c) menyatakan jumlah pixel tepi yang memenuhi persamaan (1). Tentukan elemen matriks yang memiliki penumpukan suara cukup besar (yang nilainya di atas nilai ambang tertentu). Misalkan tempat-tempat itu adalah {(m1, c1), (m2, c2), …, {(mk, ck ), Hal ini berarti terdapat k garis lurus yang terdeteksi pada citra.

Tingkat ketelitian dari Transformasi Hough bergantung pada ukuran matriks P(m, c), yaitu K × L. Kompleksitas komputasi Transformasi Hough pada kasus terburuk adalah O(Kn), yang dalam hal ini K adalah jumlah pembagian parameter m, dan n adalah jumlah pixel di dalam citra tepi. Karena O(Kn) < O(n3), maka pendeteksian garis lurus dengan Transformasi Hough lebih cepat daripada metode exhaustive search. Model parametrik pada persamaan 9.2 tidak dapat digunakan untuk mendeteksi garis vertikal atau hampir vertikal karena gradiennya (m) menuju nilai takberhingga. Karena itu, garis dinyatakan dalam representasi polar: r = x cos θ + y sin θ

(9.4)

yang dalam hal ini r adalah jarak garis ke titik asal (Gambar 9.5). θ

y

( r, θ ) r

θ x

r

Gambar 9.5 Representasi polar dari garis lurus

Sembarang garis yang melalui (x1,y1) pada ruang x–y berkoresponden dengan kurva sinusoida r = x1 cos θ + y1 sin θ pada ruang r–θ. Pixel-pixel yang terletak segaris pada citra tepi berkoresponden dengan titik potong seluruh kurva sinusoidanya pada ruang parameter r–θ.

146


Prosedur yang sama untuk mendeteksi garis lurus dapat digunakan kembali dengan mengganti ruang parameter m–c menjadi ruang parameter r–θ, yang dalam hal ini,

− N2 + M 2 ≤ r ≤ N2 + M 2 -π/2 ≤ θ ≤ π/2 Algoritma Transformasi Hough diperlihatkan pada Algoritma 9.1 [PIT93]. Algoritma tersebut mengasumsikan citra tepi (citra hasil pendeteksian tepi) disimpan di dalam matriks Edge[0..N-1,0..M-1]. Ruang parameter r–θ dinyatakan sebagai matriks P yang berukuran n × m. Nilai cosinus dan sinus disimpan di dalam lookup table COS[0..p-1] dan SIN[0..p-1] yang dibentuk dengan Algoritma 9.2. void Hough(citra Edge, int N, int M, imatriks P, int n, int m, float *COS, float *SIN) /* prosedur yang melakukan Transformasi Hough. Masukan: citra tepi Edge yang berukuran N x M. Keluaran: matriks parameter P yang berukuran n x m */ { int k, l, i, j, kk, ll; float r, b; float SQRTD =sqrt((float)N*(float)N + (float)M*(float)M); /* inisialisasi P[0..p-1, 0,,q-1] dengan 0 */ for(kk=0;kk<=p-1;kk++) for(ll=0;ll<=q-1;ll++) P[kk][ll]=0; /*telusuri citra tepi. Jika pixel merupakan tepi, lakukan pemungutan suara pada elemen matriks P yang bersesuaian. tetha dari –pi/2 sampai pi/2. r dari –sqrt(N*N+M*M) sampai sqrt(N*N+M*M). */ for (k=0;k<=N-1;k++) for (l=0;l<=M-1;l++) { if (Edge[k][l]==1) { for (i=0;i<=p-1;i++) { r = k*COS[i] + l*SIN[i]; b = SQRTD; r+=b; r/=(SQRTD*2.0); r*=(m-1); r+=0.5; j=floor(r); P[i][j]++; } } } }

Algoritma 9.1 Transformasi Hough


147

void LookUpTable(float *COS, *SIN, int m) /* Membuat tabel cosinus dan sinus untuk fungsi COS dan SIN. Masukan: m adalah jumlah baris tabel Keluaran: tabel COS dan tabel SIN */ { int i; float th, R_TO_D = 0.017453 for(i=0;i<=p-1;i++) { th = (float)i * 180.0/(m-1)-90.0; th = th * R_TO_D; COS[i] = (double) cos((double)th); SIN[i] = (double) sin((double)th); }

Algoritma 9.2 Transformasi Hough

Setelah Transformasi Hough selesai dilakukan, langkah berikutnya adalah melakukan operasi pengambangan (thresholding) untuk menentukan tempattempat pada ruang paramater r–θ yang mempunyai penumpukan suara lebih besar dari nilai ambang T. Elemen matriks P yang nilainya di atas nilai ambang tersebut menyatakan parameter garis lurus. Misalkan tempat-tempat itu adalah {(m1, c1), (m2, c2), …, {(mk , ck ), hal ini berarti terdapat k garis lurus yang terdeteksi pada citra. Algoritma pengambangan ditunjukkan pada Algoritma 9.3. void threshold(imatriks P, int n, in m, int T) /* Melakukan pengambangan pada matriks parameter P. Setiap elemen matriks P yang nilainya di atas T menyatakan parameter garis lurus. Masukan: matriks parameter P yang berukuran n x m. Keluaran: matriks parameter P yang sudah di-threshold. */ { int i, j; for(i=0;iT) P[i][j]=1; else P[i][j=0; }

Algoritma 9.3 Pengambangan hasil transformasi Hough

Pixel-pixel tepi yang termasuk di dalam garis lurus hasil deteksi Transformasi Hough dapat dihasilkan dengan algoritma Transformasi Hough Balikan (inverse Hough Transform). Untuk setiap elemen matriks Par yang bernilai 1,

148


garis lurus yang bersesuaian (yang intensitasnya 1) digambarkan pada matriks keluaran Out. Operasi and dengan citra tepi dilakukan untuk mengklarifikasi keberadaan pixel tepi. Algoritma Transformasi Hough Balikan diperlihatkan pada Algoritma 9.4 [PIT93]. Algoritma tersebut mengasumsikan citra tepi (citra hasil pendeteksian tepi) disimpan di dalam matriks Edge[0..N-1,0..M-1]. Ruang parameter r–θ dinyatakan sebagai matriks P yang berukuran n × n. Citra keluaran yang berisi pixel-pixel tepi pembentuk garis lurus disimpan di dalam matriks Out[0..N-1,0..M-1]. void InverseHough(citra Edge, citra Out, int N, int M, imatriks P, int n, int m, float *COS, float *SIN) /* prosedur yang melakukan Transformasi Hough Balikan Masukan: 1. citra tepi Edge yang berukuran N x M. 2. matriks parameter P yang berukuran n x m Keluaran: citra Out yang berisi pixel-pixel pembentuk garis lurus. */ { int k, l, i, j; float r, y; float SQRTD =sqrt((float)N*(float)N + (float)M*(float)M); /* inisialisasi citra keluaran dengan 0 */ for(kk=0;kk<=p-1;kk++) for(ll=0;ll<=q-1;ll++) Out[p][q]=0; /* Matriks parameter P telah dilakukan operasi thresholding. Untuk setiap elemen P yang bernilai 1, garis lurus yang bersesuaian digambarkan ke dalam matriks Out. Operasi and dengan citra tepi dikerjakan. for (k=0;k<=p-1;k++) for (l=0;l<=q-1;l++) { y=(float)0.0; if (P[k][l]==1) /* atau P[k][l]== 255 */ { for (i=0;i<=N-1;i++) { r = (float)l * 2.0 * SQRTD/(m-1) – SQRTD; if (SIN[k]==(float)0.0) y++; else y=(r – (float)i * COS[k])/SIN[k]; y+=0.5; j=floor(y); if (j >=0 && j < M) if (Edge[i][j]==1) Out[i][j]++; } } } }

Algoritma 9.4 Transformasi Hough Balikan


149

Mendeteksi Lingkaran Transformasi Hough dapat juga digunakan untuk mendeteksi bentuk lingkaran di dalam citra tepi. Persamaan lingkaran yang berpusat di titik (a, b) dengan jari-jari r adalah

( x − a)2 + ( y − b)2 = r 2

(9.5)

Jadi, ruang parameter untuk lingkaran adalah r–a–b , sehingga matriks trimatra P(r, a, b) dibutuhkan untuk menyimpan perhitungan suara. Persamaan polar untuk setiap titik (x, y) di lingkaran: x = a + r cos θ y = b + r sin θ

(9.6) (9.7)

Persamaan (9.6) dan (9.7) dapat ditulis menjadi persamaan a = x – r cos θ b = y – r sin θ

(9.8) (9.9)

Pada operasi deteksi tepi, selain magnitudo pixel tepi, juga dihasilkan arah tepi, θ. Karena itu, cos θ dan sin θ dapat dihitung. Misalkan (x i, yi) adalah pixel tepi dan θ adalah arah tepi . Ada dua kasus yang akan ditinjau: (i) jika jari-jari lingkaran diketahui, (ii) jika jari-jari lingkaran tidak diketahui.

Kasus 1: Jari-jari lingkaran diketahui Jika jari-jari jari-jari lingkaran diketahui r = R, maka ruang parametrik trimatra, P(r,a,b), dapat direduksi menjadi ruang dwimatra, P(a,b).

(a,b)

R

(x i,yi)

Gambar 9. 5 Proses penumpukan suara untuk mendeteksi lingkaran

150


Titik pusat lingkaran, (a,b), yang mempunyai jari-jari r = R dan melalui titik (x i, yi) dapat dihitung dengan persamaan a = xi – R cos θ b = yi – R sin θ

(9.10) (9.11)

seperti yang ditunjukkan pada Gambar 9.5, lalu tambahkan elemen P(a, b) yang bersesuaian dengan satu. Proses ini diulangi untuk pixel-pixel tepi yang lain. Elemen matriks P(a, b) yang memiliki jumlah suara di atas nilai ambang tertentu menyatakan lingkaran yang terdapat di dalam citra tepi.

Kasus 2: Jari-jari lingkaran tidak diketahui Jika jari-jari lingkaran tidak diketahui, maka penumpukan suara dilakukan untuk semua nilai r, 0 < r ≤ r max, nilai a dan b untuk pixel tepi (xi, yi) dihitung dengan persamaan a = xi – r cos θ b = yi – r sin θ

(9.12) (9.13)

dan elemen P(r, a, b) yang bersesuaian dinaikkan satu. Proses ini diulangi untuk pixel-pixel tepi yang lain. Elemen matriks P(r, a, b) yang memiliki jumlah suara di atas nilai ambang tertentu menyatakan lingkaran yang terdapat di dalam citra tepi. Persamaan (9.12) dan (9.13) dapat dimanipulasi dengan mengeliminasi r dari kedua persamaan: (x − a) a = x – r cos θ → r = cos θ ( x − a) b = y – r sin θ → b = y − sin θ = y − ( x − a ) tan θ cos θ b = a tan θ – x tan θ + y

(9.14)

Dengan demikian, maka ruang parametrik trimatra, P(r,a,b), dapat direduksi menjadi ruang dwimatra, P(a,b). Untuk untuk semua nilai r, yang dalam hal ini a1 < a ≤ aK, nilai ordinat b dari titik pusat lingkaran (a,b) yang melalui titik (xi, yi) dapat dihitung dengan persamaan (11), lalu tambahkan elemen P(a, b) yang bersesuaian dengan satu. Proses ini diulangi untuk pixel-pixel tepi yang lain. Elemen matriks P(a, b) yang memiliki jumlah suara di atas nilai ambang tertentu menyatakan lingkaran yang terdapat di dalam citra tepi. Gambar 9.6 memperlihatkan hasil transformasi Hough untuk mendeteksi lingkaran dari citra slope dengan menggunakan nilai ambang T = 30. Bab 9_Kontur dan Representasinya

151

(a)

(b)

Gambar 9. 6 (a) Citra slope, (b) hasil deteksi lingkaran dengan Transformasi Hough (Terima kasih kepada Danu Pranantha atas izin menggunakan output program tugasnya)

Transformasi Hough untuk Mendeteksi Bentuk Sembarang Transformasi Hough dapat dirampatkan untuk mendeteksi sembarang kurva yang berbentuk f(x, a) = 0, yang dalam hal ini x adalah vektor peubah dan a adalah vektor parameter. Memori yang dibutuhkan untuk matriks parametrik P(a) meningkat menjadi Kq, yang dalam hal ini q adalah jumlah parameter. Tahapan yang dilakukan adalah [DUL97]: 1. tentukan lokasi pusat penumpukan suara; 2. tentukan fungsi jarak dari setiap pixel tepi ke pusat pemungutan suara. Jika kurva berbentuk lingkaran, maka lokasi pusat penumpukan suara adalah titik pusat lingkaran, sedangkan fungsi jarak dari setiap pixel tepi ke titik pusat lingkaran adalah fungsi konstan (yaitu akar pangkat dua dari persamaan (4) ). Sebagai contoh, pada Gambar 9.7 titik (a, b) adalah lokasi pusat penumpukan suara. Fungsi jarak r dari setiap titik (x, y) dan nilai α merupakan fungsi dari arah vektor normal N. Untuk setiap pixel tepi (x,y) dengan sudut arah tepi θ, lokasi pusat penumpukan suara dihitung dengan rumus N

a = x − r(θ ) cos(α (θ )) b = y − r (θ ) sin( α (θ ))

(9.15) (9.16)

(x,y)

α

r

(a,b) Gambar 9. 7 Pendeteksian bentuk kurva sembarang dengan Transformasi Hough rampatan

152


Bab 10

Pemampatan Citra

ada umumnya, representasi citra digital membutuhkan memori yang besar. Sebagai contoh, citra Lena dalam format bitmap yang berukuran 512 × 512 pixel membutuhkan memori sebesar 32 KB (1 pixel = 1 byte) untuk representasinya. Semakin besar ukuran citra tentu semakin besar pula memori yang dibutuhkannya. Pada sisi lain, kebanyakan citra mengandung duplikasi data. Duplikasi data pada citra dapat berarti dua hal. Pertama, besar kemungkinan suatu pixel dengan pixel tetanggganya memiliki initensitas yang sama, sehingga penyimpanan setiap pixel memboroskan tempat. Kedua, citra banyak mengandung bagian (region) yang sama, sehingga bagian yang sama ini tidak perlu dikodekan berulang kali karena mubazir atau redundan.

P

Saat ini, kebanyakan aplikasi menginginkan representasi citra dengan kebutuhan memori yang sesedikit mungkin. Pemampatan citra atau kompresi citra (image compression) bertujuan meminimalkan kebutuhan memori untuk merepresentasikan citra digital. Prinsip umum yang digunakan pada proses pemampatan citra adalah mengurangi duplikasi data di dalam citra sehingga memori yang dibutuhkan untuk merepresentasikan citra menjadi lebih sedikit daripada representasi citra semula.

10.1 Pemampatan Citra versus Pengkodean Citra Pemampatan citra kadang-kadang disalahmengertikan dengan pengkodean citra (image encoding), yaitu persoalan bagaimana pixel-pixel di dalam citra dikodekan dengan representasi tertentu. Pengkodean citra tidak selalu menghasilkan representasi memori yang minimal. Pengkodean citra yang menghasilkan Bab 10_Pemampatan Citra

153

representasi memori yang lebih sedikit daripada representasi aslinya itulah yang dinamakan pemampatan citra. Ada dua proses utama dalam persoalan pemampatan citra: 1.

Pemampatan citra (image compression). Pada proses ini, citra dalam representasi tidak mampat dikodekan dengan representasi yang meminimumkan kebutuhan memori. Citra dengan format bitmap pada umumnya tidak dalam bentuk mampat. Citra yang sudah dimampatkan disimpan ke dalam arsip dengan format tertentu. Kita mengenal format JPG dan GIF sebagai format citra yang sudah dimampatkan.

2.

Penirmampatkan citra (image decompression). Pada proses ini, citra yang sudah dimampatkan harus dapat dikembalikan lagi (decoding) menjadi representasi yang tidak mampat. Proses ini diperlukan jika citra tersebut ditampilkan ke layar atau disimpan ke dalam arsip dengan format tidak mampat. Dengan kata lain, penirmampatan citra mengembalikan citra yang termampatkan menjadi data bitmap.

10.2 Aplikasi Pemampatan Citra Pemampatan citra memberikan sumbangsih manfaat yang besar dalam industri multimedia saat ini. Pemampatan citra bermanfaat untuk aplikasi yang melakukan: 1. Pengiriman data (data transmission) pada saluran komunikasi data Citra yang telah dimampatkan membutuhkan waktu pengiriman yang lebih singkat dibandingkan dengan citra yang tidak dimampatkan. Contohnya aplikasi pengiriman gambar lewat fax, videoconferencing, pengiriman data medis, pengiriman gambar dari satelit luar angkasa, pengiriman gambar via telepon genggam. download gambar dari internet, dan sebagainya. 2. Penyimpanan data (data storing) di dalam media sekunder (storage) Citra yang telah dimampatkan membutuhkan ruang memori di dalam media storage yang lebih sedikit dibandingkan dengan citra yang tidak dimampatkan. Contoh aplikasi nya antara lain aplikasi basisdata gambar, office automation, video storage (seperti Video Compact Disc), dll.

10.3 Kriteria Pemampatan Citra Saat ini sudah banyak ditemukan metode-metode pemampatan citra. Kriteria yang digunakan dalam mengukur metode pemampatan citra adalah [LOW91]:

154


1. Waktu pemampatan dan penirmampatan (decompression). Waktu pemampatan citra dan penirmampatannya sebaiknya cepat. Ada metode pemampatan yang waktu pemampatannya lama, namun waktu penirmampatannya cepat. Ada pula metode yang waktu pemampatannya cepat tetapi waktu penirmampatannya lambat. Tetapi ada pula metode yang waktu pemampatan dan penirmampatannya cepat atau keduanya lambat. 2. Kebutuhan memori. Memori yang dibutuhkan untuk merepresentasikan citra seharusnya berkurang secara berarti. Ada metode yang berhasil memampatkan dengan persentase yang besar, ada pula yang kecil. Pada beberapa metode, ukuran memori hasil pemampatan bergantung pada citra itu sendiri. Cira yang mengandung banyak elemen duplikasi (misalnya citra langit cerah tanpa awan, citra lantai keramik) umumnya berhasil dimampatkan dengan memori yang lebih sedikit dibandingkan dengan memampatkan citra yang mengandung banyak objek (misalnya citra pemandangan alam). 3. Kualitas pemampatan (fidelity) Informasi yang hilang akibat pemampatan seharusnya seminimal mungkin sehingga kualitas hasil pemampatan tetap dipertahankan. Kualitas pemampatan dengan kebutuhan memori biasanya berbanding terbalik. Kualitas pemampatan yang bagus umumnya dicapai pada proses pemampatan yang menghasilkan pengurangan memori yang tidak begitu besar, demikian pula sebaiknya. Dengan kata lain, ada timbal balik (trade off) antara kualitas citra dengan ukuran hasil pemampatan. Kualitas sebuah citra bersifat subyektif dan relatif, bergantung pada pengamatan orang yang menilainya. Seseorang dapat saja mengatakan kualitas suatu citra bagus, tetapi orang lain mungkin mengatakan kurang bagus, jelek, dan sebagainya. Kita dapat membuat ukuran kualitas hasil pemampatan citra menjadi ukuran kuantitatif dengan menggunakan besaran PSNR (peak signal-to-noise ratio). PSNR dihitung untuk mengukur perbedaan antara citra semula dengan citra hasil pemampatan (tentu saja citra hasil pemampatan harus dinirmampatkan terlebih dahulu) dengan citra semula, dengan rumus:

 b  PSNR = 20 × log 10    rms 

(10.1)

dengan b adalah nilai sinyal terbesar (pada citra hitam-putih, b = 255) dan rms adalah akar pangkat dua dari selisih antara citra semula dengan citra hasil pemampatan. Nila rms dihitung dengan rumus:

Bab 10_Pemampatan Citra

155

rms =

1 Lebar × Tinggi

N

M

∑∑ ( f

ij

− f ' ij ) 2

(10.2)

i =1 j =1

yang dalam hal ini, f dan f ' masing-masing menyatakan nilai pixel citra semula dan nilai pixel citra hasil pemampatan. PSNR memiliki satuan decibel (dB). Persamaan (10.2) menyatakan bahwa PSNR hanya dapa dihitung setelah proses pernirmapatan citra. Dari persamaan (10.2) terlihat abhwa PSNR berbanding terbalik dengan rms. Nilai rms yang rendah yang menyiratkan bahwa citra hasil pemampatan tidak jauh berbeda dengan citra semula akan menghasilkan PSNR yang tinggi, yang berarti kualitas pemampatannya bagus. Semakin besar nilai PSNR, semakin bagus kualitas pemampatannya. Seberapa besar nilai PSNR yang bagus tidak dapat dinyatakan secara eksplisit, bergantung pada citra yang dimampatkan. Namun kita dapat mengetahui hal ini jika kita melakukan pengujian dengan mencoba berbagai kombinasi parameter pemampatan yang digunakan. Jika nilai PSNR semakin membesar, itu berarti parameter pemampatan yang digunakan sudah menuju nilai yang baik. Parameter pemampatan citra bergantung pada metode pemamapatan yang digunakan. 4. Format keluaran Format citra hasil pemampatan sebaiknya cocok untuk pengiriman dan penyimpanan data. Pembacaan citra bergantung pada bagaimana citra tersebut direpresentasikan (atau disimpan).

Pemilihan kriteria yang tepat bergantung pada pengguna dan aplikasi. Misalnya, apakah pengguna menginginkan pemampatan yang menghasilkan kualitas yang bagus, namun pengurangan memori yang dibutuhkan tidak terlalu besar, atau sebaliknya. Atau jika waktu pemampatan dapat diabaikan dari pertimbangan (dengan asumsi bahwa pemampatan hanya sekali saja dilakukan, namun pernirmampatan dapat berkali-kali), maka metode yang menghasilkan waktu penirmampatan yang cepat yang perlu dipertimbangkan.

10.4 Jenis Pemampatan Citra Ada empat pendekatan yang digunakan dalam pemampatan citra [LOW91]: 1. Pendekatan statistik. Pemampatan citra didasarkan pada frekuensi kemunculan derajat keabuan pixel di dalam seluruh bagian gambar. Contoh metode: Huffman Coding.

156


2. Pendekatan ruang Pemampatan citra didasarkan pada hubungan spasial antara pixel-pixel di dalam suatu kelompok yang memiliki derajat keabuan yang sama di dalam suatu daerah di dalam gambar. Contoh metode: Run-Length Encoding. 3. Pendekatan kuantisasi Pemampatan citra dilakukan dengan mengurangi jumlah derajat keabuan yang tersedia. Contoh metode: metode pemampatan kuantisasi. 4. Pendekatan fraktal Pemampatan citra didasarkan pada kenyataan bahwa kemiripan bagianbagian di dalam citra dapat dieksploitasi dengan suatu matriks transformasi. Contoh metode: Fractal Image Compression.

10.5 Klasifikasi Metode Pemampatan Metode pemampatan citra dapat diklasifiksikan ke dalam dua kelompok besar: 1. Metode lossless Metode lossless selalu menghasilkan citra hasil penirmampatan yang tepat sama dengan citra semula, pixel per pixel. Tidak ada informasi yang hilang akibat pemampatan. Sayangnya nisbah (ratio) pemampatan citra metode lossless sangat rendah. Contoh metode lossless adalah metode Huffman. Nisbah pemampatan citra dihitung dengan rumus Nisbah = 100 % − (

ukuran citra hasil pempatatan × 100%) ukuran citra semula

(10.3)

Metode lossless cocok untuk memampatkan citra yang mengandung informasi penting yang tidak boleh rusak akibat pemampatan. Misalnya memampatkan gambar hasil diagnosa medis. 2. Metode lossy Metode lossy menghasilkan citra hasil pemampatan yang hampir sama dengan citra semula. Ada informasi yang hilang akibat pemampatan, tetapi dapat ditolerir oleh persepsi mata. Mata tidak dapat membedakan perubahan kecil pada gambar. Metode pemampatan lossy menghasilkan nisbah pemampatan yang tinggi daripada metode lossless. Gambar 10.1 adalah citra sebelum dimampatkan, dan Gambar 10.2 adalah hasil pemampatan citra kapal dengan metode lossy. Contoh metode lossy adalah metode JPEG dan metode fraktal.


157

Gambar 10.1 Citra kapal sebelum dimampatkan

Gambar 10.2 Citra kapal setelah dimampatkan dengan sebuah metode lossy

158


10.6 Metode Pemampatan Huffman Metode pemampatan Huffman menggunakan prinsip bahwa nilai (atau derajat) keabuan yang sering muncul di dalam citra akan dikodekan dengan jumlah bit yang lebih sedikit sedangkan nilai keabuan yang frekuensi kemunculannya sedikit dikodekan dengan jumlah bit yang lebih panjang. Algoritma metode Huffman: 1. Urutkan secara menaik (ascending order) nilai-nilai keabuan berdasarkan frekuensi kemunculannya (atau berdasarkan peluang kemunculan, pk , yaitu frekuensi kemunculan (nk ) dibagi dengan jumlah pixel di dalam gambar (n)). Setiap nilai keabuan dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dengan frekuensi kemunculan nilai keabuan tersebut. 2. Gabung dua buah pohon yang mempunyai frekuensi kemunculan paling kecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon penyusunnya. 3. Ulangi langkah 2 sampai tersisa hanya satu buah pohon biner. Agar pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka semua pohon yang ada selalu terurut menaik berdasarkan frekuensi. 4. Beri label setiap sisi pada pohon biner. Sisi kiri dilabeli dengan 0 dan sisi kanan dilabeli dengan 1. Simpul-simpul daun pada pohon biner menyatakan nilai keabuan yang terdapat di dalam citra semula. Untuk mengkodekan setiap pixel di dalam di dalam citra, lakukan langkah kelima berikut: 5. Telusuri pohon biner dari akar ke daun. Barisan la bel-label sisi dari akar ke daun menyatakan kode Huffman untuk derajat keabuan yang bersesuaian. Setiap kode Huffman merupakan kode prefiks, yang artinya tidak ada kode biner suatu nilai keabuan yang merupakan awalan bagi kode biner derajat keabuan yang lain. Dengan cara ini, tidak ada ambiguitas pada proses penirmampatan citra.


159

Contoh 10.1. Misalkan terdapat citra yang berukuran 64 × 64 dengan 8 derajat keabuan (k) dan jumlah seluruh pixel (n) = 64 × 64 = 4096 k

nk

p(k) = nk/n

0 1 2 3 4 5 6 7

790 1023 850 656 329 245 122 81

0.19 0.25 0.21 0.16 0.08 0.06 0.03 0.02

Proses pembentukan pohon Huffman yang terbentuk dapat dilihat pada Gambar 10.3. Setiap simpul di dalam pohon berisi pasangan nilai a:b, yang dalam hal ini a menyatakan nilai keabuan dan b menyatakan peluang kemunculan nilai keabuan tersebut di dalam citra. Dari pohon Huffman tersebut kita memperoleh kode untuk setiap derajat keabuan sebagai berikut: 0 = 00 2 = 01 4 = 1110 6 = 111101 1 = 10 3 = 110 5 = 11111 7 = 111100 Ukuran citra sebelum pemampatan (1 derajat keabuan = 3 bit) adalah 4096 × 3 bit = 12288 bit, sedangkan Ukuran citra setelah pemampatan: (790 × 2 bit) + (1023 × 2 bit) + (850 × 2 bit) + (656 × 3 bit) + (329 × 4 bit) + (245 × 5 bit) + (122 × 6 bit) + (81 × 6 bit) = 11053 bit Jadi, kebutuhan memori telah dikurangi dari 12288 bit menjadi 11053 bit. Jelas ini tidak banyak menghemat, tetapi jika 256 nilai keabuan yang digunakan (dibanding dengan 8 derajat keabuan deperti pada contoh di atas) , penghematan memori dapat bertambah besar. 11053 Nisbah pemampatan = (100% − × 100 %) = 10% , yang artinya 10% dari 12288 citra semula telah dimampatkan. ¾

160


1.

7:0.02

2.

6:0.03

76:0.05

7:0.02

3.

5:0.06

5:0.06

4:0.08

4:0.08

765:0.11

7:0.02

0:0.19

2:0.21

1:0.25

3:0.16

0:0.19

2:0.21

1:0.25

3:0.16

0:0.19

2:0.21

1:0.25

3:0.16

0:0.19

2:0.21

1:0.25

5:0.06

6:0.03

4765:0.19

4.

4:0.08

765:0.11

5:0.06

76:0.05

7:0.02

0:0.19

3:0.16

6:0.03

76:0.05

5.

4:0.08

2:0.21

6:0.03

1:0.25

34765:0.35

4765:0.19

3:0.16

4:0.08

765:0.11

5:0.06

76:0.05

7:0.02

6:0.03

Gambar 10.3 Tahapan pembentukan pohon Huffman untuk Contoh 10.1 di atas


161

1:0.25

6.

34765:0.35

02:0.40

4765:0.19

3:0.16

4:0.08

0:0.19

765:0.11

5:0.06

76:0.05

7:0.02 7.

02:0.40

0:0.19

2:0.21

6:0.03

134765:0.60

2:0.21

1:0.25

34765:0.35

3:0.16

4765:0.19

765:0.11

4:0.08

76:0.05

7:0.02

5:0.06

6:0.03

02134765: 1.00

8.

02:0.40

0:0.19

134765:0.60

2:0.21

1:0.25

34765:0.35

4765:0.19

3:0.16

4:0.08

765:0.11

76:0.05

7:0.02

5:0.06

6:0.03

Gambar 10.3 (lanjutan)

162


10.7 Metode Pemampatan Run-Length Encoding (RLE) Metode RLE cocok digunakan untuk memampatkan citra yang memiliki kelompok-kelompok pixel berderajat keabuan sama. Pemampatan citra dengan metode RLE dilakukan dengan membuat rangkaian pasangan nilai (p, q) untuk setiap baris pixel, nilai pertama (p) menyatakan derajat keabuan, sedangkan nilai kedua (q) menyatakan jumlah pixel berurutan yang memiliki derajat keabuan tersebut (dinamakan run length). Contoh 10.2. [LOW91] Tinjau citra 10 × 10 pixel dengan 8 derajat keabuan yang dinyatakan sebagai matriks derajat keabuan sebagai berikut 0 0 1 4 3 2 3 0 1 3

0 0 1 4 3 2 3 0 1 3

0 0 1 4 3 6 4 0 1 3

0 1 1 4 5 0 4 0 1 2

0 1 1 3 5 0 3 0 0 2

2 1 1 3 7 0 2 0 0 2

2 1 1 3 7 0 2 0 0 1

2 2 1 3 7 1 2 0 2 1

2 2 1 2 7 1 1 1 2 1

2 2 1 2 6 0 1 1 2 1

semuanya ada 100 buah nilai. Pasangan nilai untuk setiap baris run yang dihasilkan dengan metode pemampatan RLE: (0, 5), (2, 5) (0, 3), (1, 4), (2, 3) (1, 10) (4, 4), (3, 4), (2 2) (3, 3), (5, 2), (7, 4), (6, 1) (2, 2), (6, 1), (0, 4), (1, 2), (0, 1) (3, 2), (4, 2), (3, 1), (2, 2), (1, 2) (0, 8), (1, 2) (1, 4), (0, 3), (2, 3) (3, 3), (2, 3), (1, 4) semuanya ada 31 pasangan nilai atau 31 × 2 = 62 nilai. Ukuran citra sebelum pemampatan (1 derajat keabuan = 3 bit) adalah 100 × 3 bit = 300 bit, sedangkan ukuran citra setelah pemampatan (derajatk keabuan = 3 bit, run length = = 4 bit): (31 × 3) + (31 × 4) bit = 217 bit Bab 10_Pemampatan Citra

163

217 × 100%) = 27 .67% , yang artinya 27.67% 300 dari citra semula telah dimampatkan. ¾ Nisbah pemampatan = (100% −

Versi lain dari metode RLE adalah dengan menyatakan seluruh baris citra menjadi sebuah baris run, lalu menghitung run-length untuk setiap derajat keabuan yang berurutan. Sebaga i contoh, tinjau sebuah citra sebagai berikut: 1 1 1 1

2 3 1 1

1 4 3 1

1 4 3 1

1 4 3 3

1 4 5 3

Nyatakan sebagai barisan nilai derajat keabuan: 1 2 1 1 1 1 3 4 4 4 4 1 1 3 3 3 5 1 1 1 1 3 3 semuanya ada 24 nilai. Pasangan nilai dari run yang dihasilkan dengan metode pemampatan RLE: (1, 1) (2, 1) (1, 5) (3, 1) (4, 4) (1, 2) (3, 3) (5, 1) (1, 4) (3, 2) Hasil pengkodean: 1 1 2

1 1

5

3

1

4

4

1

2

3 3 5 1

1 4 3

2

semuanya ada 20 nilai. Jadi, kita sudah menghemat 4 buah nilai. Metode RLE dapat dikombinasikan dengan metode Huffman untuk mengkodekan nilai-nilai hasil pemampatan RLE guna meningkatkan nisbah pemampatan. Mulamula lakukan pemampatan RLE, lalu hasilnya dimampatkan lagi dengan metode Huffman.

10.8 Metode Pemampatan Kuantisasi (Quantizing Compression) Metode ini mengurangi jumlah derajat keabuan, misalnya dari 256 menjadi 16, yang tentu saja mengurangi jumlah bit yang dibutuhkan untuk merepresentasikan citra. Misalkan P adalah jumlah pixel di dalam citra semula, akan dimampatkan menjadi n derajat keabuan. Algoritmanya adalah sebagai berikut: Algoritma metode kuantisasi: 1. Buat histogram citra semula (citra yang akan dimampatkan). 2. Identifikasi n buah kelompok di dalam histogram sedemikian sehingga setiap kelompok mempunyai kira-kira P/n buah pixel. 164


3. Nyatakan setiap kelompok dengan derajat keabuan 0 sampai n –1. Setiap pixel di dalam kelompok dikodekan kembali dengan nilai derajat keabuan yang baru. Contoh 10.3. [LOW91] Tinjau citra yang berukuran 5 × 13 pixel: 2 3 3 3 2

9 8 8 9 0

6 5 4 4 4

4 4 7 7 3

8 7 4 2 8

2 6 9 7 9

6 3 2 6 5

3 8 3 2 4

8 2 8 1 7

5 8 2 6 1

9 4 7 5 2

3 7 4 3 8

7 3 9 0 3

yang akan dimampatkan menjadi citra dengan 4 derajat keabuan (0 s/d 3), jadi setiap derajat keabuan direpresentasikan dengan 2 bit. Histogram citra semula: 0 1 2 3 4 5 6 7 8 9

** ** ********* *********** ********* **** ***** ******** ********* ******

Ada 65 pixel, dikelompokkan menjadi 4 kelompok derajat keabuan. Tiap kelompok ada sebanyak rata-rata 65/4 = 16.25 pixel per kelompok: -----------------------------------------------------0 ** 13 1 ** 0 2 ********* -----------------------------------------------------20 3 *********** 4 ********* 1 ----------------------------------------------------5 **** 17 6 ***** 2 7 ******** ----------------------------------------------------15 8 ********* 3 9 ****** -----------------------------------------------------


165

Citra setelah dimampatkan menjadi: 0 1 1 1 0

3 3 3 3 0

2 2 1 1 1

1 1 2 2 1

3 2 1 0 3

0 2 3 2 3

2 1 0 2 2

1 3 1 0 1

3 0 3 0 2

2 3 0 2 0

3 1 2 2 0

1 2 1 1 3

2 1 3 0 0

Ukuran citra sebelum pemampatan (1 derajat keabuan = 4 bit): 65 × 4 bit = 260 bit Ukuran citra setelah pemampatan (1 derajat keabuan = 2 bit): 65 × 2 bit = 130 bit Nisbah pemampatan = (100% − semula telah dimampatkan.

130 × 100%) = 50% , yang artinya 50% dari citra 260 ¾

Kelemahan metode pemampatan kuantisasi adalah banyaknya informasi yang hilang, tapi kehilangan informasi ini dapat diminimalkan dengan menjamin bahwa tiap kelompok mempunyai jumlah pixel yang hampir sama.

10.9 Metode Pemampatan Fraktal Metode pemampatan fraktal adalah metode yang relatif baru. Prinsipnya adalah mencari bagian di dalam citra yang memiliki kemiripan dengan bagian lainya namun ukurannya lebih besar (self similarity). Kemudian dicari matriks yang mentransformasikan bagian yang lebih besar tersebut dengan bagian yang lebih kecil. Kita cukup hanya menyimpan elemen-elemen dari sekumpulan matriks transformasi tersebut (yang disebut matriks transformasi affine). Pada proses penirmampatan, matriks ransformasi affine di-iterasi sejumlah kali terhadap sembarang citra awal. Hasil iterasi akan konvergen ke citra semula. Metode ini menghasilkan nisbah pemampatan yang tinggi namun waktu pemampatannya relatif lama, sedangkan waktu penirmamoatannya berlangsung cepat. Metode pemampatan fraktal akan dijelaskan secara panjang lebar di dalam Bab tersendiri (Bab 14).

166


Bab 11

Citra Biner

itra biner (binary image) adalah citra yang hanya mempunyai dua nilai derajat keabuan: hitam dan putih. Meskipun saat ini citra berwarna lebih disukai karena memberi kesan yang lebih kaya daripada citra biner, namun tidak membuat citra biner mati. Pada beberapa aplikasi citra biner masih tetap dibutuhkan, misalnya citra logo instansi (yang hanya terdiri atas warna hitam dan putih), citra kode batang (bar code) yang tertera pada label barang, citra hasil pemindaian dokumen teks, dan sebagainya. Bab 10 ini akan memaparkan beberapa konsep dan teknik pengolahan citra biner.

C

11.1 Pendahuluan Seperti yang sudah disebutkan di awal Bab, citra biner hanya mempunyai dua nilai derajat keabuan: hitam dan putih. Pixel-pixel objek bernilai 1 dan pixel-pixel latar belakang bernilai 0. Pada waktu menampilkan gambar, 0 adalah putih dan 1 adalah hitam. Jadi, pada citra biner, latar belakang berwarna putih sedangkan objek berwarna hitam. Gambar 11.1 memperlihatkan beberapa contoh citra biner, sedangkan Gambar 11.2 adalah contoh pengkodean citra biner.

(a) Citra logo

Bab 11_Citra Biner

(b) Citra lukisan mobil

167

23942

0

(c) Citra teks (hasil pemindaian dokumen)

41480

3

(d) Citra kode batang (bar code)

Gambar 11.1 Beberapa contoh citra biner

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

1

1

0

0

0

1

0

0

0

0

1

1

1

1

1

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

1

1

0

0

0

0

1

0

0

0

1

1

0

0

0

0

1

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

Gambar 11.2 Huruf “B” dan representasi biner dari derajat keabuannya.

Meskipun komputer saat ini dapat memproses citra hitam-putih (greyscale) maupun citra berwarna, namun citra biner masih tetap dipertahankan keberadaannya. Alasan penggunaan citra biner adalah karena ia memiliki sejumlah keuntungan sebagai berikut: 1. Kebutuhan memori kecil karena nilai derajat keabuan hanya membutuhkan representasi 1 bit. Kebutuhan memori untuk citra biner masih dapat berkurang secara berarti dengan metode pemampatan run-length encoding (RLE). Metode RLE akan dijelaskan kemudian. 2. Waktu pemrosesan lebih cepat dibandingkan dengan citra hitam-putih karena banyak operasi pada citra biner yang dilakukan sebagai operasi logika (AND, OR, NOT, dll) ketimbang operasi aritmetika bilangan bulat.

168


Aplikasi yang menggunakan citra biner sebagai masukan untuk pemrosesan pengenalan objek, misalnya pengenalan karakter secara optik, analisis kromosom, pengenalan sparepart komponen industri, dan sebagainya.

11.2 Konversi Citra hitam-putih ke Citra Biner Pengkonversian citra hitam-putih (greyscale) menjadi citra biner dilakukan untuk alasan-alasan sebagai berikut: 1. Untuk mengidentifikasi keberadaan objek, yang direpresentasikan sebagai daerah (region) di dalam citra. Misalnya kita ingin memisahkan (segmentasi) objek dari gambar latar belakangnya. Pixel-pixel objek dinyatakan dengan nilai 1 sedangkan pixel lainnya dengan 0. Objek ditampilkan seperti gambar siluet. Untuk memperoleh siluet yang bagus, objek harus dapat dip isahkan dengan mudah dari gambar latar belakangnya. 2. Untuk lebih memfokuskan pada analisis bentuk morfologi, yang dalam hal ini intensitas pixel tidak terlalu penting dibandingkan bentuknya. Setelah objek dipisahkan dari latar belakangnya, properti geometri dan morfologi/ topologi objek dapat dihitung dari citra biner. Hal ini berguna untuk pengambilan keputusan. 3. Untuk menampilkan citra pada piranti keluaran yang hanya mempunyai resolusi intensitas satu bit, yaitu piranti penampil dua-aras atau biner seperti pencetak (printer). 4. Mengkonversi citra yang telah ditingkatkan kualitas tepinya (edge enhancement) ke penggambaran garis-garis tepi. Ini perlu untuk membedakan tepi yang kuat yang berkoresponden dengan batas-batas objek dengan tepi lemah yang berkoresponden dengan perubahan illumination, bayangan, dll.

Pengambangan Konversi dari citra hitam-putih ke citra biner dilakukan dengan operasi pengambangan (thresholding). Operasi pengambangan mengelompokkan nilai derajat keabuan setiap pixel ke dalam 2 kelas, hitam dan putih. Dua pendekatan yang digunakan dalam operasi pengambangan adalah pengambangan secara global dan pengambangan secara lokal. a. Pengambangan secara global (global image thresholding) Setiap pixel di dalam citra dipetakan ke dua nilai, 1 atau 0 dengan fungsi pengambangan:

1, f B (i , j ) =  0,

Bab 11_Citra Biner

f g ( i, j ) ≤ T lainnya

(11.1)

169

yang dalam hal ini, fg(i, j) adalah citra hitam-putih, fB(i, j) adalah citra biner, dan T adalah nilai ambang yang dispesifikasikan. Dengan operasi pengambangan tersebut, objek dibuat berwarna gelap (1 atau hitam) sedangkan latar belakang berwarna terang (0 atau putih). Nilai ambang T dipilih sedemikian sehingga galat yang diperoleh sekecil mungkin. Cara yang umum menentukan nilai T adalah dengan membuat histogram citra. Jika citra mengandung satu buah objek dan latar belakang mempunyai nilai intensitas yang homogen, maka citra tersebut umumnya mempunyai histogram bimodal (mempunyai dua puncak atau dua buah maksimum lokal) seperti yang ditunjukkan pada Gambar 11.3. Nilai T dipilih pada nila i minimum lokal yang terdapat di antara dua puncak. Dengan cara seperti ini, kita tidak hanya mengkonversi citra hitam-putih ke citra biner, tetapi sekaligus melakukan segmentasi objek dari latar belakangnya. Gambar 11.4 memperlihatkan segmentasi objek (botol dan apel) dari latar belakangnya dengan cara mengkonversikan citra hitam-putihnya menjadi citra biner dengan menggunakan nilai ambang T = 90 dan T = 100. Gambar 11.5 memperlihatkan konversi citra Lena menjadi citra biner dengan T = 128 dan T = 150. P(r)

kelas 0

T

kelas 1

r Gambar 11.3 Penentuan nilai ambang T

.

(a) 170

(b) Pengolahan Citra Digital

(c)

(d)

Gambar 11.4 (a) Citra botol, (b) histogram, (c) T = 90, dan (d) T = 100

(a) Citra Lena

(c) T = 128

(b) Histogram citra Lena

(d) T = 150

Gambar 11.5 Operasi pengambangan pada citra Lena

Bab 11_Citra Biner

171

Jika nilai intensitas objek diketahui dalam selang [T1, T2], maka kita dapat menggunakan fungsi pengambangan:

1, T1 ≤ f g ( i, j ) ≤ T2 f B ( i, j ) =  lainnya 0,

(11.2)

b. Pengambangan secara lokal adaptif (locally adaptive image thresholding) Pengambangan secara global tidak selalu tepat untuk seluruh macam gambar. Beberapa informasi penting di dalam gambar mungkin hilang karena pengambangan global ini. Lagipula, tidak ada harga nilai ambang yang berlaku secara global untuk seluruh daerah citra (misalnya pada citra kedokteran, citra pemandangan alam, dsb). Pengambangan secara lokal dilakukan terhadap daerah-daerah di dalam citra. Dalam hal ini citra dipecah menjadi bagian-bagian kecil, kemudian proses pengambangan dilakukan secara lokal. Nilai ambang untuk setiap bagian belum tentu sama dengan bagian lain. Sebagai contoh, pengambangan dilakukan terhadap daerah citra yang berukuran 3 × 3 atau 5 × 5 pixel. Nilai ambangnya ditentukan sebagai fungsi rata-rata derajat keabuan di dalam dearah citra tersebut. Intensitas pixel yang berbeda secara signifikan dari nilai rata-rata tersebut dianggap mengandung informasi kontras dan ini harus dipertahankan di dalam citra biner. Dengan pengambangan secara lokal adaptif, secara subjektif citra biner yang dihasilkan terlihat lebih menyenangkan dan sedikit informasi yang hilang.

11.3 Penapis Luas Proses pengambangan menghasilkan citra biner. Seringkali citra biner yang dihasilkan mengandung beberapa daerah yang dianggap sebagai gangguan. Biasanya daerah gangguan itu berukuran kecil. Penapis luas dapat digunakan untuk menghilangan daerah gangguan tersebut [JAI95]. Misalkan objek yang dianalisis diketahui mempunyai luas yang lebih besar dari T. Maka, pixel-pixel dari daerah yang luasnya di bawah T dinyatakan dengan 0. Dengan cara ini, daerah yang berupa gangguan dapat dihilangkan (Gambar 11.6 dan 11.7).

172


Gambar 11.6 Kiri: gangguan pada citra biner yang mengandung huruf “i”; Kanan: citra yang dihasilkan setelah dilakukan penapisan (T = 10) [JAI95].

Gambar 11.7 Kesalahan yang diperoleh dari pengambilan nilai T0 yang tidak tepat (T = 25). Perhatikan bahwa “titik” di atas huruf “i” hilang karena luasnya, sehingga huruf “i” terlihat seperti angka “1” [JAI95].

11.4 Pengkodean Citra Biner Citra biner umumnya dikodekan dengan metode run-length encoding (RLE). Metode pengkodean ini menghasilkan representasi citra yang mampat. Dua pendekatan yang digunakan dalam penerapan RLE pada citra biner: a. Posisi awal kelompok nilai 1 dan panjangnya (length of runs) b. Panjang run, dimulai dengan panjang run 1.

Bab 11_Citra Biner

173

Contoh 11.1. Misalkan citra binernya adalah sebagai berikut 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1

Hasil pengkodean dengan metode RLE: (i) pendekatan pertama: (1, 3) (7, 2) (12, 4) (17, 2) (20, 3) (5, 13) (19, 4) (1, 3) (17, 6) (ii) pendekatan kedua 3, 3, 2, 3, 4, 1, 2, 1, 3 0, 4, 13, 1, 4 3, 13, 6

¾

11.5 Segmentasi Citra Biner Proses awal yang dilakukan dalam menganalisis objek di dalam citra biner adalah segmentasi objek. Proses segmentasi bertujuan mengelompokkan pixel-pixel objek menjadi wilayah (region) yang merepresentasikan objek. Ada dua pendekatan yang digunakan dalam segmentasi objek: 1. Segmentasi berdasarkan batas wilayah (tepi dari objek). Pixel-pixel tepi ditelusuri sehingga rangkaian pixel yang menjadi batas (boundary) antara objek dengan latar belakang dapat diketahui secara keseluruhan (algoritma boundary following). 2. Segmentasi ke bentuk-bentuk dasar (misalnya segmentasi huruf menjadi garis-garis vertikal dan horizontal, segmentasi objek menjadi bentuk lingkaran, elips, dan sebagainya). Kita hanya akan membahas pendekatan pertama.

174


Segmentasi berdasarkan batas wilayah. Pada citra biner, batas antara objek dengan latar belakang terlihat jelas. Pixel objek berwarna hitam sedangkan pixel latar belakang berwarna putih. Pertemuan antara pixel hitam dan putih dimodelkan sebagai segmen garis. Penelusuran batas wilayah dianggap sebagai pembuatan rangkaian keputusan untuk bergerak lurus, belok kiri, atau belok kanan seperti yang diperlihatkan pada Gambar 11.8.

Gambar 11.8 Proses penelusuran batas wilayah dalam citra biner [DUL97].

Pixel yang bertanda • menyatakan pixel yang sedang ditelaah. Penelusur harus menentukan arah pixel tepi berikutnya bergantung pada pixel-pixel sekitarnya. Algoritma menentukan arah berikutnya: if DepanTidakSama(arah,x,y) then Belok kanan (arah,x,y) else if SilangSama(arah,x,y) then Belok kiri (arah,x,y) else Lurus (arah,x,y) endif endif

Metode pendeteksian batas wilayah yang lain adalah pendeteksian secara topologi. Pada metode topologi, setiap kelompok 4-pixel bertetangga diperiksa, dan bila kelompok tersebut sama dengan salah satu bentuk pada Gambar 11.9, maka pada titik tengah dari kelompok pixel tersebut terdapat tepi.

Bab 11_Citra Biner

175

Gambar 11.9 Bentuk -bentuk yang menghasilkan titik tepi [MEN89].

Titik tepi yang dideteksi selanjutnya dihubungkan oleh garis-garis penghubung. Arah garis penghubung dikodekan dengan kode rantai (chain code).

11.6 Representasi Wilayah Wilayah (region) di dalam citra biner dapat direpresentasikan dalam beberapa cara. Salah satu cara yang populer adalah representasi wilayah dengan pohonempatan (quadtree). Setiap simpul di dalam pohon-empatan merupakan salah satu dari tiga ketagori: putih, hitam, dan abu-abu. Pohon-empatan diperoleh dengan membagi citra secara rekursif. Wilayah di dalam citra dibagi menjadi empat buah upa-wilayah yang berukuran sama. Untuk setiap upa-wilayah, bila pixel-pixel di dalam wilayah tersebut semuanya hitam atau semuanya putih, maka proses pembagian dihentikan. Sebaliknya, bila pixel-pixel di dalam upa-wilayah mengandung baik pixel hitam mapupun pixel putih (kategori abu-abu), maka upawilayah tersebut dibagi lagi mejadi empat bagian. Demikian seterusnya sampai diperoleh upa-wilayah yang semua pixel-nya hitam atau semua pixel-nya putih. Proses pembagian tersebut digambarkan dengan pohon-empatan. Dinamakan pohon-empatan karena setiap simpul mempunyai tepat empat anak, kecuali simpul daun. Gambar 10.10 memperlihatkan contoh representasi wilayah dengan pohon empatan.

176


B

C

E

D

A

G

A

F

H B

C

D

E

G

H

M

F I

J

L

K

M I

J

K

L

Kode: gwgwbbwbgwwgwwgwwbbb Di-decode sebagai: g(wg(wbbw)bg(wwg(wwbb)b)) Keterangan: b = black , w = white, g = gray

(a) Citra biner

(b) Pohon-empatan

Gambar 11.10 Representasi wilayah dengan pohon-empatan

11.7 Properti Geometri Setelah proses segmentasi objek selesai dilakukan, maka proses berikutnya adalah menganalisis objek untuk mengenali objek tersebut. Analisis objek didasarkan pada ciri khas (feature) geometri pada objek tersebut. Kita asumsikan di dalam citra biner hanya terdapat 1 buah objek. Ada dua kelompok ciri khas pada objek [JAI95]: a. Global feature, yaitu ciri khas keseluruhan objek. b. Local feature, yaitu ciri khas bagian tertentu dari objek. Besaran yang termasuk global feature: (i) Luas atau ukuran objek (A)

A=

n

m

∑∑ f (i, j )

(11.3)

i=1 j=1

Catatan: f(i, j) = 1 jika (i, j) adalah pixel objek

Bab 11_Citra Biner

177

(ii) Pusat massa Berguna untuk menentukan posisi objek. n

x=

m

∑∑ j. f (i , j ) i =1 j =1

n

y=

(11.4)

A m

∑∑i. f (i , j ) i =1 j =1

(11.5)

A

(iii) Momen inersia (M) n

m

∑∑ j . f (i , j ) 2

Mx =

i =1 j =1

A n

(11.6)

m

∑∑i . f (i , j ) 2

My =

i = 1 j =1

A

(11.7)

(iv) Keliling objek (K) Menghitung panjang batas wilayah. Pixel dalam batas wilayah horizontal atau vertikal dianggap satu satuan panjang, sedangkan pixel pada arah diagonal panjangnya √2 satuan.

(v) Tinggi (T) Dihitung dari jarak vertik al dari pixel tertinggi dan terendah dari objek. Jarak antara pixel (i 1, j1) dan pixel (i 2, j2) dapat dihitung dengan bermacam-macam rumus: - Euclidean

d Euclidean = (i1 − i2 )2 + ( j1 − j2 ) 2 -

City-block

d city = i1 − i2 + j1 − j2

178

(11.8)

(11.9)


-

Chessboard

d chess = max ( i1 − i2 , j1 − j2 )

(11.10)

(vi) Lebar (L) Dihitung dari jarak horizontal dari pixel tertinggi dan terendah dari objek. (vii) Diameter Dihitung dari jarak paling jauh dari dua titik pada objek. (viii) Kompleksitas bentuk Menyatakan seberapa rumitnya suatu bentuk. Didefinisikan sebagai K2/A, yang dalam hal ini K = keliling, A = luas. (ix) Proyeksi Menyatakan bentuk yang diperoleh dari hasil proyeksi objek terhadap garis sumbu. Proyeksi citra biner terhadap garis horizontal dan garis vertikal dihitung dengan rumus:

H (i) =

m

∑ f (i , j )

(11.11)

j=1

V (i ) =

n

∑ f (i, j)

(11.12)

i =1

Sedangkan besaran yang termasuk local feature antara lain: (i) Arah dan panjang segmen garis lurus Arah garis dinyatakan dengan kode Freeman, sedangkan panjang garis dihitung sebagai jarak antara ujung-ujung garis. (ii) Sudut antar garis Menyatakan besar sudut antara dua garis lurus yang berpotongan. (iii) Jarak relatif Dihitung sebagai jarak antara dua titik. (iv) Object signature Menyatakan jarak dari pusat massa ke tepi suatu objek pada arah 0 sampai 360 derajat.

Bab 11_Citra Biner

179

11.8 Penipisan Pola Pada aplikasi pencocokan pola, banyak bentuk terutama bentuk yang mengulur/memanjang yang dapat dinyatakan dalam versi yang lebih tipis. Bentuk yang lebih tipis terdiri dari garis-garis terhubung yang disebut rangka (skeleton) atau tulang atau garis inti. Idealnya, rangka tersebut membentang sepanjang garis sumbu objek. Penipisan (thinning) adalah operasi pemrosesan citra biner yang dalam hal ini objek (region) direduksi menjadi rangka yang menghampiri garis sumbu objek. Tujuan penipisan adalah mengurangi bagian yang tidak perlu (redundant) sehingga hanya dihasilkan informasi yang esensial saja. Pola hasil penipisan harus tetap mempunyai bentuk yang menyerupai pola asalnya. Sebagai contoh, Gambar 11.11 adalah huruf “R” dan hasil penipisan polanya menjadi rangka “R”.

(a) Huruf “R”

(b) Hasil penipisan huruf “R

Gambar 11.11 Penpisan pola huruf “R”

Penipisan pola merupakan proses yang iteratif yang menghilangkan pixel-pixel hitam (mengubahnya menjadi pixel putih) pada tepi-tepi pola. Jadi, algoritma penipisan mengelupas pixel-pixel pinggir objek, yaitu pixel-pixel yang terdapat pada peralihan 0→1. Algoritma penipisan pola harus memenuhi persyaratan sebagai berikut [PIT93]: 1. Mempertahankan keterhubungan pixel-pixel objek pada setiap lelaran. Dengan kata lain, tidak menyebabkan bentuk objek menjadi terputus (Gambar 11.12(a)). 2. Tidak memperpendek ujung lengan dari bentuk yang ditipiskan (Gambar 11.12(b)).

180


(a)

(b)

p8

p1

p2

p7

p0

p3

p6

p5

p4

(c)

Gambar 11.12 (a) Penghapusan pixel pinggir menyebabkan ketidakterhubungan, (b) penghapusan pixel pinggir memperpendek lengan objek, (c) notasi pixel yang digunakan untuk memeriksa keterhubungan.

Algoritma penipisan yang umum adalah memeriksa pixel-pixel di dalam jendela yang berukuran 3 × 3 pixel dan mengelupas satu pixel pada pinggiran (batas) objek pada setiap lelaran, sampai objek berkurang menjadi garis tipis. Notasi pixel di dalam jendela 3 × 3 diperlihatkan pada Gambar 11.12(c). Algoritma bekerja secara iteratif, pada setiap lelaran dilakukan premrosesan pada jendela yang berukuran 3 × 3 pixel. Algoritmanya adalah sebagai berikut [PIT93]: 1. Mula-mula diperiksa jumlah pixel objek (yang bernilai 1), N, di dalam jendela 3 × 3 pixel. 2. Jika N kurang atau sama dengan 2, tidak ada aksi yang dilakukan karena di dalam jendela terdapat ujung lengan objek. 3. Jika N lebih besar dari 7, tidak ada aksi yang dilakukan karena dapat menyebabkan pengikisan (erosion) objek. 4. Jika N lebih besar dari 2, periksa apakah penghilangan pixel tengah menyebabkan objek tidak terhubung. Ini dilakukan dengan membentuk barisan p1p2p3…p8p1. Jika jumlah peralihan 0 → 1 di dalam barisan tersebut sama dengan 1, berarti hanya terdapat satu komponen terhubung di dalam jendela 3 × 3. Pada kasus ini, dibolehkan menghapus pixel tengah yang bernilai 1 karena penghapusan tersebut tidak mempengaruhi keterhubungan.

Algoritma penipisan pola dalam bahasa C diperlihatkan pada Algoritma 11.1. void penipisan(citra f, int N1, int M1, int N2, int M2) /* Prosedur yang mengimplementasikan penipisan pola Masukan : f : citra biner N1, M1 : koordinat awal (sudut kiri atas) N2, M2 : koordinat akhir (sudut kanan bawah) Keluaran: citra bienrf */ { int k, l, i, j, count=0, y[9], trans=0, m, OK=1

Bab 11_Citra Biner

181

do { OK=1; for(k=N1+1;k2)&&(count<8)) { /* hitung jumlah peralihan 0->1 */ y[0]=f[k-1][l-11]; y[1]=f[k-1][l];y[2]=f[k-1][l+1]; y[3]=f[k][l+1]; y[4]=f[k+1]l+1];y[5]=f[k+1][l]; y[6]=f[k+1][l-1]; y[7]=f[k][l-1];y[8]=f[k-1][l-1]; trans=0; for(m=0;m<=7;m++) if (y[m]==0 && y[m+1]==1) trans++; /* jika jumlah peralihan sama dengan 1, hapus pixel yang sedang diacu (current) */ if (trans==1) {f[k][l]=0; OK=0;} } } } while (OK=0); }

Algoritma 11.1 Penipisan pola.

182


Bab 12

Warna

ersepsi visual citra berwarna (color images) umumnya lebih kaya dibandingkan dengan citra hitam putih (greyscale), karena itu citra berwarna lebih disenangi daripada citra hitam putih. Citra berwarna menampilkan warna objek seperti warna aslinya (meskipun tidak selalu tepat demikian). Bab ini akan menguraikan konsep warna, model warna, dan transformasi warna dari satu model ke model lainnya.

P

12.1 Dasar-dasar Warna Warna yang diterima oleh mata dari sebuah objek ditentukan oleh warna sinar yang dipantulkan oleh objek tersebut. Sebagai contoh, suatu objek berwarna hijau karena objek tersebut memantulkan sinar biru dengan panjang gelombang 450 sampai 490 nanometer (nm). Warna sinar yang direspon oleh mata adalah sinar tampak (visible spectrum) dengan panjang gelombang berkisar dari 400 (biru) sampai 700 nm (merah). Lihat Gambar 12.1.

10-5

10-1

Bab 12_Warna

1

10

400

700

2500 nm

1000 m 183

sinar sinar sinar kosmik gamma X

ultra violet

ultra violet

Infra merah

micro TV radio wave wave wave

sinar tampak

400 nm

electr. power

infra merah

700 nm

Gambar 12.1 Spektrum cahaya

Warna-warna yang diterima oleh mata manusia merupakan hasil kombinasi cahaya dengan panjang gelombang berbeda. Penelitian memperlihatkan bahwa kombinasi warna yang memberikan rentang warna yang paling lebar adalah red (R), green (G), dan blue (B). Ketiga warna tersebut dinamakan warna pokok (primaries), dan sering disingkat sebagai warna dasar RGB. Warna-warna lain dapat diperoleh dengan mencampurkan ketiga warna pokok tersebut dengan perbandingan tertentu (meskipun tidak sepenuhnya benar, karena tidak semua kemungkinan warna dapat dihasilkan dengan kombinasi RGB saja), sesuai dengan teori Young (1802) yang menyatakan bahwa sembarang warna dapat dihasilkan dari percampuran warna-warna pokok C1, C2, dan C3 dengan persentase tertentu [PIT93]: C = a C1 + b C2 + c C3

(12.1)

Bila citra warna didigitasi, maka tiga buah filter digunakan untuk mengekstraksi intensitas warna merah, hijau, dan biru, dan bila ketiganya dikombinasikan kita memperoleh persepsi warna.

12.2 Atribut Warna Selain RGB, warna juga dapat dimodelkan berdasarkan atribut warnanya. Setiap warna memiliki 3 buah atribut, yaitu intensity (I), hue (H), dan saturation (S). a. Intensity/brigthness/luminance Atribut yang menyatakan banyaknya cahaya yang diterima oleh mata tanpa mempedulikan warna. Kisaran nilainya adalah antara gelap (hitam) dan terang (putih).

184


b. Hue Menyatakan warna sebenarnya, seperti merah, violet, dan kuning. Hue digunakan untuk membedakan warna-warna dan menentukan kemerahan (redness), kehijauan (greenness), dsb, dari cahaya. Hue berasosiasi dengan panjang gelombang cahaya, dan bila kita menyebut warna merah, violet, atau kuning, kita sebenarnya menspesifikasikan hue-nya. c. Saturation Menyatakan tingkat kemurnian warna cahaya, yaitu mengindikasikan seberapa banyak warna putih diberikan pada warna. Sebagai contoh, warna merah adalah 100% warna jenuh (saturated color), sedangkan warna pink adalah warna merah dengan tingkat kejenuhan sangat rendah (karena ada warna putih di dalamnya). Jadi, jika hue menyatakan warna sebenarnya, maka saturation menyatakan seberapa dalam warna tersebut. Dalam praktek, hue dikuantisasi dengan nilai dari 0 sampai 255; 0 menyatakan merah, lalu memutar nilai-nilai spektrum tersebut kembali lagi ke 0 untuk menyatakan merah lagi. Ini dapat dipandang sebagai sudut dari 0° sampai 360°. Jika suatu warna mempunyai saturation = 0, maka warna tersebut tanpa hue, yaitu dibuat dari warna putih saja. Jika saturation = 255, maka tidak ada warna putih yang ditambahkan pada warna tersebut. Saturation dapat digambarkan sebagai panjang garis dari titik pusat lingkaran ke titik warna. Intensity nilainya dari gelap sampai terang (dalam praktek, gelap = 0, terang = 255). Intensity dapat digambarkan sebagai garis vertikal yang menembus pusat lingkaran. Ketiga atribut warna (I, H, dan S) digambarkan dalam model IHS (ada juga yang menyebutnya model HSV, dengan V = Value = I) yang diperlihatkan pada Gambar 12.2. Terang Biru

I

Titik warna n ratio Satu

θ = hue

S H Merah

Hijau

Gelap Gambar 12.2 Model IHS

Bab 12_Warna

185

12.3 Sistem Koordinat Warna CIE (Commission International de l’Eclairage) atau International Lighting Committee adalah lembaga yang membakukan warna pada tahun 1931. CIE mula-mula menstandarkan panjang gelombang warna-warna pokok sebagai berikut [MEN89]: R G B

: 700 nm : 546.1 nm : 435.8 nm

Warna-warna lain dapat dihasilkan dengan mengkombinasikan ketiga warna pokok tersebut. Model warna yang digunakan sebagai acuan dinamakan model RGB. RGB bukan satu-satunya warna pokok yang dapat digunakan untuk menghasilkan kombinasi warna. Warna lain dapat juga digunakan sebagai warna pokok (misalnya C = Cyan, M = Magenta, dan Y = Yellow). Karena itu CIE mendefinisikan model warna dengan menggunakan warna-warna fiktif (yaitu, warna yang secara fisik tidak dapat direalisasikan), yang dilambangkan dengan X, Y, dan Z. Model warna tersebut dinamakan model XYZ. Warna-warna dispesifikasikan dengan jumlah relatif warna pokok fiktif. Keuntungan utama dari model ini adalah luminance atau brigntness sinyal disediakan langsung oleh Y. Jadi, nilai Y memberikan citra greyscale dari citra berwarnanya. Kromatisitas (chromaticity of color) masing-masing warna pokok, menunjukkan persentase relatif suatu warna pokok di antara warna pokok lainnya pada warna yang diberikan, yang definisikan sebagai

x=

X X +Y + Z

(12.2)

y=

Y X +Y + Z

(12.3)

z=

Z X +Y + Z

(12.4)

Warna putih acuan dinyatakan dengan X = Y = Z = 1. Jumlah seluruh nilai kromatisitas warna adalah satu: x+y+z=1

186

(12.5)


atau z = 1 – (x + y)

(12.6)

Jelas hanya dua nilai x dan y yang dibutuhkan untuk menspesifikasikan kromatisitas warna, karena jika x dan y diketahui, z dapat dihitung dengan persamaan 12.6. Warna lebih tepat dinyatakan dengan kromatisitas x dan y dan luminansi Y. Koordinat kromatisitas (12.2 dan 12.3) digunakan untuk menggambarkan diagram kromatisitas pada Gambar 12.3. Titik yang ditandai “green” pada diagram Gambar 12.3 memiliki kira-kira 62% green dan 25% red. Ini sesuai dengan persamaan 12.6 bahwa kompisisi blue kirakira 13%. Posisi bermacam-macam spektrum warna, dari violet 380 nm sampai red 780 nm dinyatakan pada sisi (boundary) diagram yang berbentuk setengah elips. Ini adalah warna-warna “pure”. Titik yang tidak terletak pada sisi tetapi masih di dalam diagram menyatakan campuran spektrum warna. Titik energi setara (equal energy) berkoresponden dengan nilai fraksi yang sama dari ketiga warna pokok X, Y, Z. Titik energi setara menyatakan bakuan CIE untuk cahaya putih. Sembarang titik yang terletak pada sisi diagram dikatakan jenuh (saturated). Semakin jauh titik-titik itu meninggalkan sisi dan mendekati titik energi setara, itu berarti semakin banyak cahaya putih ditambahkan pada warna dan ia menjadi kurang jenuh (less saturated). Kejenuhan titik energi setara adalah nol. Garis lurus yang menghubungkan dua titik di dalam diagram mendefinisikan semua variasi warna berbeda yang dapat diperoleh dengan mengkombinasikan dua warna ini. Sebagai contoh, garis lurus dari red ke green. Jika lebih banyak cahaya red daripada green, maka titik warna baru terletak pada segmen garis, tetapi ia akan lebih dekat ke red daripada ke green.

Bab 12_Warna

187

y 520

Spectral energy locus (wavelength in nanometers)

0.9 540

0.8 510

0.7

green

560

0.6 gold 500

0.5

warm white

600

cool white

0.4

pink daylight

0.3

620 red 780

490 deep blue

0.2 480

0.1

blue Point of equal energy

470 380

x 0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

Gambar 12.3 Diagram kromatisitas CIE

Hue dari warna tertentu diperoleh dengan menarik garis dari putih ke sisi elips melalui warna tersebut. Misalkan digambar garis dari posisi W (putih) melalui warna tertentu, P, ke sisi elips pada posisi H. Nilai hue adalah H, dan saturation adalah panjang WP relatif terhadap WH. Warna P dapat dipandang sebagai campuran warna putih dan hue: P = SH + (1 – S) W

(12.7)

yang dalam hal ini S mengendalikan perbandingan relatif warna putih dan hue.

188


12.4 Transformasi Sistem Koordinat Warna Transformasi warna dari basis CIE RGB ke CIE XYZ dapat dilakukan sebagai berikut: Diberikan triplet RGB (Ri, Gi, Bi) untuk pixel i, maka triplet XYZ (Xi, Yi, Zi) dihitung dengan

 X i  0 .490 0 .310 0.200   Y  = 0.177 0.813 0.011   i   Z i  0 .000 0 .010 0.99 

 Ri  G   i  Bi 

(12.8)

Transformasi sebaliknya dari CIE XYZ ke CIE RGB dapat dilakukan dengan persamaan

 Ri   2.365 − 0.3896 − 0.468 G  =  − 0.515 1 .425 0.088   i   Bi   0.005 − 0.014 1.009 

Xi  Y   i  Z i 

(12.9)

Algoritma transformasi citra dari model warna CIE RGB ke model warna CIE XYZ diperlihatkan pada Algoritma 12.1, sedangkan algoritma transformasi balikan dari model warna CIE XYZ ke model warna CIE RGB diperlihatkan pada Algoritma 12.2 [PIT93]. Kedua algoritma tersebut mengasumsikan bahwa komponen RGB disimpan masing-masing di dalam matriks r, g, dan b. Hasil transformasi masing-masing disimpan di dalam matriks x, y, dan z. Ukuran citra adalah N × M. int cieRGB_toXYZ(citra r, citra g, citra b, citra x, citra y, citra z, int N, int M) /* Transformasi citra dari model warna CIE RGB ke model CIE XYZ Masukan: citra dengan kompoenen RGB masing-masing disimpan di dalam matriks r, g, dan b. Ketga mtariks ini berukuran N × M. Keluaran: citra dengan komponen XYZ masing-masing disimpan di dalam matriks x, y, dan z. */ { int i, j; double R, G, B; double X, Y, Z; for (i=0; i<=N-1; i++) for (j=0; j<=M-1; j++) { R = (double)r[i][j]; G=(double)g[i][j]; B=(double)b[i][j]; X = 0.490*R+0.310*G+0.200*B; Y = 0.177*R+0.813*G+0.011*B; Z = 0.010*G+0.990*B; if (X > 255.0) x[i][j]=255; else x[i][j]=(unsigned char)X; if (Y > 255.0) y[i][j]=255; else y[i][j]=(unsigned char)Y; if (Z > 255.0) z[i][j]=255; else z[i][j]=(unsigned char)ZX; } }

Algoritma 12.1 Transformasi citra dari model warna CIE RGB ke model CIE XYZ

Bab 12_Warna

189

int XYZ_to_cieRGB(citra x, citra y, citra z, citra r, citra g, citra b, int N, int M) /* Transformasi citra dari model warna CIE XYZ ke model CIE RGB Masukan: citra dengan komponen XYZ masing-masing disimpan di dalam matriks x, y, dan z. Ketga mtariks ini berukuran N × M. Keluaran: citra dengan komponen RGB masing-masing disimpan di dalam matriks r, g, dan b. */ { int i, j; double R, G, B; double X, Y, Z; for (i=0; i<=N-1; i++) for (j=0; j<=M-1; j++) { X = (double)x[i][j]; Y =(double)y[i][j]; Z =(double)z[i][j]; R = 2.365*X-0.896*Y-0.468*Z; G = -0.515*X+1.425*Y+0.088*Z; B = 0.005*X-0.014*Y+1.009*Z; if (R > 255.0) r[i][j]=255; else if (R<0.0) r[i][j]=0; else r[i][j]=(unsigned char)R; if (G > 255.0) g[i][j]=255; else if (G<0.0) g[i][j]=0; else g[i][j]=(unsigned char)G; if (B > 255.0) b[i][j]=255; else if (B<0.0) b[i][j]=0; else b[i][j]=(unsigned char)B; }

Algoritma 12.2 Transformasi citra dari model warna CIE XYZ ke model CIE RGB

Model warna RGB dan XYZ yang dikemukakan di atas adalah bakuan dari CIE. Ada juga model warna yang diusulkan untuk platform perangkat keras tertentu untuk menampilkan gambar. Misalnya National Television Systems Committee (NTSC) menggunakan model warna RGB khusus untuk menampilkan citra berwarna pada layar CRT. Format NTSC digunakan pada televisi di Amerika Serikat. Salah satu keuntungan utama dari format ini adalah data greyscale dipisahkan dari data warnanya, sehingga sinyal yang sama dapat digunakan baik untuk layar berwarna maupun layar hitam putih. Pada format NTSC, data citra terdiri atas tiga komponen, yaitu luminance (Y), hue (I), dan saturation (Q). Komponen pertama, yaitu Y menyatakan data greyscale, sedangkan dua komponen terakhir membentuk chrominance. Jika dib erikan triplet NTSC RGB (Ri, Gi, Bi) untuk pixel i, maka nilai YIQ untuk pixel yang bersangkutan dihitung dengan

0 .114   Yi  0.299 0.857  I  = 0.596 − 0.274 − 0.322   i   Qi   0.211 − 0.523 0 .312 

190

 Ri  G   i  Bi 

(12.10)


Nilai NTSC RGB semula dapat dihitung dengan menggunakan transformasi balikan:

0.621   Ri  1.000 0 .956 G  = 1.000 − 0 .273 − 0.647    i   Bi  1.000 − 1 .104 1.701 

 Yi  I   i Qi 

(12.11)

Transformasi dari NTSC RGB ke CIE RGB dihitung dengan persamaan:

 Ri   1.167 − 0.146 − 0 .151 G  =  0.114 0.753 0.159   i   Bi   − 0.001 0.059 1.128 

 R _ NTSCi  G _ NTSC  i   B _ NTSCi 

(12.12)

Sistem NTSC RGB dapat ditransformasikan ke sistem CIE XYZ dengan persamaan:

 X i  0 .607 0.174 0.201  Y  = 0 .299 0.587 0.114   i    Z i   0.000 0.066 1.117 

 R _ NTSCi  G _ NTSC  i   B _ NTSCi 

(12.13)

sedangkan transformasi dari CIE XYZ ke NTSC RGB dihitung dengan persamaan:

 R _ NTSCi   1 .910 − 0.533 − 0.288 G _ NTSC  =  − 0.985 2.000 − 0.028 i     B _ NTSCi   0.058 − 0.118 0.896 

X i  Y   i  Z i 

(12.14)

12.5 Model Warna CMY dan CMYK Warna cyan (C) , magenta (M), dan yellow (Y) adalah warna komplementer terhadap red, green, dan blue. Dua buah warna disebut komplementer jika dicampur dengan perbandingan yang tepat menghasilkan warna putih. Misalnya, magenta jika dicampur dengan perbandingan yang tepat dengan green menghasilkan putih, karena itu magenta adalah komplemen dari dari green. Model CMY dapat diperoleh dari model RGB dengan perhitungan berikut: C=1–R M=1–G Y=1–B

(12.15) (12.16) (12.17)

Model CMY dapat digunakan untuk mencetak citra berwarna, tetapi karena ketidaksempurnaan tinta, model CMY tidak dapat menghasilkan warna hitam

Bab 12_Warna

191

dengan baik. Karena itu, model CMY disempurnakan menjadi model CMYK, yang dalam hal ini K menyatakan warna keempat, dengan perhitungan sebagai berikut [PIT93]: K = min(C, M, Y) C=C–K M=M–K Y=Y–K

(12.18) (12.19) (12.20) (12.21)

Algoritma transformasi citra dari model RGB ke model CMYK ditunjukkan pada Algoritma 12.3, sedangkan algoritma transformasi balikan dari model CMYK ke model RGB ditunjukkan pada Algoritma 12.4 [PIT93]. Kedua algoritma tersebut mengasumsikan komponen RGB disimpan masing-masing di dalam matriks r, g, dan b. Hasil transformasi masing-masing disimpan di dalam matriks c, m, y dan k. Ukuran citra adalah N × M. int RGB_toCMYK(citra r, citra g, citra b, citra c, citra m, citra y, citra k, int N, int M) /* Transformasi citra dari model warna RGB ke model CMYK. Masukan: citra dengan komponen RGB masing-masing disimpan di dalam matriks r, g, dan b. Ketga mtariks ini berukuran N × M. Keluaran: citra dengan komponen CMYK masing-masing disimpan di dalam matriks c, y, m, dan k. */ { int i, j; for (i=0; i<=N-1; i++) for (j=0; j<=M-1; j++) { c[i][j]=(unsigned char)255 – r[i][j]; m[i][j]=(unsigned char)255 – g[i][j]; y[i][j]=(unsigned char)255 – b[i][j]; k[i][j]=c[i][j]; if (m[i][j]
Algoritma 12.3 Transformasi citra dari model warna RGB ke model CMYK.

192


int CMYKtoRGB(citra c, citra y, citra m, citra k, citra r, citra g, citra b, int N, int M) /* Transformasi citra dari model warna CMYK ke model RGB. Masukan: citra dengan komponen CMYK masing-masing disimpan di dalam matriks c, y, m, dan k. Ketga mtariks ini berukuran N × M. Keluaran: citra dengan komponen RGB masing-masing disimpan di dalam matriks r, g, dan b. */ { int i, j; for (i=0; i<=N-1; i++) for (j=0; j<=M-1; j++) { c[i][j]=c[i][j]+k[i][j]; m[i][j]=m[i][j]+k[i][j]; y[i][j]=y[i][j]+k[i][j]; k[i][j]=c[i][j]; r[i][j]=(unsigned char)255 – c[i][j]; g[i][j]=(unsigned char)255 – m[i][j]; b[i][j]=(unsigned char)255 – y[i][j]; } }

Algoritma 12.4 Transformasi citra dari model warna CMYK ke model RGB

17.6 Transformasi Warna RGB ke IHS Meskipun basis RGB bagus untuk menampilkan informasi warna, tetapi ia tidak cocok untuk beberapa aplikasi pemrosesan citra. Pada aplikasi pengenalan objek, lebih mudah mengidentifikasi objek dengan perbedaan hue-nya dengan cara memberikan nilai ambang pada rentang nilai-nilai hue (panjang helombang spektrum) yang melingkupi objek. Masalahnya, bagaimana melakukan pengambangan pada ruang warna RGB dan apa rumus untuk mengaplikasikannya? Masalah ini lebih mudah dipecahkan bila nilai RGB dikonversi ke nilai intensity (I), hue (H), dan saturation (S). Aplikasi yang lain misalnya dalam pemampatan citra. Melakukan pemampatan secara terpisah pada setiap nilai R, G, dan B tidak disarankan, karena data yang dimampatkan 3 kali lebih banyak dan waktu pemampatannya 3 kali lebih lama daripada waktu pemampatan citra skala-abunya. Pemampatan citra berwarna lebih relevan bila warna RGB-nya dikonversikan ke IHS karena algoritma pemampatan pada citra skala-abu dilakukan pada komponen I, sedangkan nilai H dan S dikodekan dengan cara yang lain dengan sedikit atau sama sekali tidak ada degradasi.

Bab 12_Warna

193

Model warna IHS merepresentasikan warna dalam terminologi intensity, hue, dan saturation. Dari diagram kromatisitas, buatlah segitiga yang menghubungkan tiga warna pokok red, green, blue (Gambar 12.4). Titik-titik pada segitiga menyatakan warna yang dihasilkan dari pencampuran warna titik sudut, sedangkan titik-titik di dalam segitiga menyatakan warna yang dapat dihasilkan dengan mengkombinasikan tiga warna titik sudut. Titik tengah segitiga menyatakan warna putih, yaitu pencampuran warna pokok dengan fraksi yang sama.

B

H S R

G Gambar 12.4 Segitiga HIS

Komponen RGB dari citra berwarna dapat dikonversikan ke model warna IHS. Dengan mengasumsikan komponen RGB telah dinormalisasikan ke 1, maka I dihitung dengan rumus:

1 I = (R + G + B) 3

(12.22)

Persamaan 12.22 di atas sering digunakan untuk mengubah citra berwarna menjadi citra skala -abu. H dihitung dengan rumus:

H = cos − 1

194

2R − G − B 2 ( R − G ) 2 + ( R − B )(G − B )

(12.23)


Nilai S dihitung dengan rumus:

S = 1−

3 min( R, G , B ) R+G+ B

(12.24)

Alternatif lain mengubah model RGB ke model IHS adalah sebagai berikut. Konversi dari model RGB ke model IHS dilakukan dalam dua tahap. Tahap pertama adalah merotasikan koordinat RGB ke sistem koordinat (I, V1, V2) dengan transformasi:

3 /3  I   3/3 V  =  0 1/ 2  1  V2   2 / 6 − 1 / 6

3 /3   − 1/ 2  − 1 / 6 

R G     B 

(12.25)

Langkah kedua adalah menghitung H dan S dari koordinat (V1, V2): H = tan-1(V2/V1)

(12.26)

S = (V12 + V22)1/2

(12.27)

Nilai H adalah dalam selang [0,2π] atau setara dengan [0, 360°]. Transformasi dari model IHS ke model RGB dapat dilakukan dengan prosedur balikan: V1 = S cos(H)

(12.28)

V2 = S sin(H)

(12.29)

0 R  3 / 3 G  =     3 / 3 1/ 2  B   3 / 3 − 1 / 2 

2/ 6   I     − 1 / 6  V1  − 1 / 6  V2 

(12.30)

Dengan transformasi RGB ke IHS, maka algoritma pemrosesan citra yang semula untuk citra skala-abu dapat diterapkan pada komponen intensity, sedangkan algoritma segmentasi citra dapat dilakukan pada komponen H.

Bab 12_Warna

195

Transformasi citra dari basis RGB ke basis IHS dilakukan sebelum pemrosesan citra. Citra yang sudah diproses dapat dikonversikan kembali ke basis RGB untuk tujuan display. National Television Systems Committee (NTSC) menggunakan model YIQ untuk mentransformasikan model RGB ke IHS, yang dalam hal ini Y menyatakan intensity, I menyatakan hue, dan Q menyatakan saturation [PIT93].

196


Bab 13

Steganografi dan Watermarking pada Citra Digital

teganografi (steganography) adalah teknik menyembunyikan data rahasia di dalam wadah (media) digital sehingga keberadaan data rahasia tersebut tidak diketahui oleh orang. Steganografi membutuhkan dua properti: wadah penampung dan data rahasia yang akan disembunyikan. Steganografi digital menggunakan media digital sebagai wadah penampung, misalnya citra, suara (audio), teks, dan video. Data rahasia yang disembunyikan juga dapat berupa citra, suara, teks, atau video.

S

Penggunaan steganografi antara lain bertujuan untuk menyamarkan eksistensi (keberadaan) data rahasia sehingga sulit dideteksi, dan melindungi hak cipta suatu produk. Steganografi dapat dipandang sebagai kelanjutan kriptografi. Jika pada kriptografi, data yang telah disandikan (ciphertext) tetap tersedia, maka dengan steganografi cipherteks dapat disembunyikan sehingga pihak ketiga tidak mengetahui keberadaannya. Data rahasia yang disembunyikan dapat diekstraksi kembali persis sama seperti keadaan aslinya. Bab ini akan memaparkan steganografi dan watermarking pada citra digital. Watermarking adalah aplikasi dari steganografi, di mana citra digital diberi suatu penanda yang menunjukkan label kepemilikan citra tersebut. Sebagian besar dari materi bab ini dikutip dari [POL98].

Bab 13_Steganografi dan Watermarking pada Citra Digital

197

13.1 Sejarah Steganografi Steganografi sudah dikenal oleh bangsa Yunani. Penguasa Yunani dalam mengirimkan pesan rahasia menggunakan kepala budak atau prajurit sebagai media. Dalam hal ini, rambut budak dibotaki, lalu pesan rahasia ditulis pada kulit kepala budak. Ketika rambut budak tumbuh, budak tersebut diutus untuk membawa pesan rahasia di kepalanya. Bangsa Romawi mengenal steganografi dengan menggunakan tinta tak-tampak (invisible ink) untuk menuliskan pesan. Tinta tersebut dibuat dari campuran sari buah, susu, dan cuka. Jika tinta digunakan untuk menulis maka tulisannya tidak tampak. Tulisan di atas kertas dapat dibaca dengan cara memanaskan kertas tersebut. Sebagai contoh ilustrasi, Gambar 13.1.a adalah citra lada (peppers.bmp) yang akan digunakan untuk menyembunyikan sebuah dokumen teks (Gambar 13.1.b) yang berukuran 20 KB). Perhatikanlah citra lada sebelum penyembuan data (13.1.a) dan citra setelah disisipi data teks (13.1.c). Citra lada tetap kelihatan mulus, seolah-olah tidak pernah disisipi data sebelumnya. Sebenarnya tidaklah demikian, gambar lada tersebut mengalami sedikit perubahan akibat steganografi, namun mata manusia mempunyai sifat kurang peka terhadap perubahan kecil ini, sehingga manusia sukar membedakan mana gambar yang asli dan mana gambar yang sudah disisipi data.

198


LETTER OF RECOMMENDATION To Whom It May Concern, Herewith I highly recommend Mr. R. Hendro Wicaksono continue his postgraduate study at your university. My recommendation is based on my experience as his lecturer in several courses for the past four years. He has shown me his excellent attitude and personality. He is a hard working person and he has a lot of creative ideas. He is also a very intelligent student and he cooperates very well with his peers whenever they had to work together. During his study, he showed diligence and eagerness to achieve his goal. He sets very high standard for himself and organizes himself very well to achieve the standard. I am confident that if he can maintain his goal work, he should be able to complete the postgraduate program well within the stipulated time.

(a) Citra peppers asli

I am sure that his abilities and his personal qualities along with his academic capabilities will help his to obtain his Master’s degree at your university, which will be very useful for our country. Bandung, November 15, 2002 Yours Sincerely, Ir. Rinaldi Munir, M.Sc. Senior Lecturer Informatics Engineering Department, Institute Technology of Bandung (ITB) Jl. Ganesha No. 10, Bandung 40132 Email : [email protected] Phone +62-22-2508135 Indonesia

(b) Dokumen hendro.doc yang akan disembunyikan ke daalm citra lada

(c) Citra peppers setelah “diisi” dengan data teks hendro.doc Gambar 13.1 Contoh penyembunyian data di dalam citra digital


199

13.2 Kriteria Steganografi yang Bagus Seperti sudah disebutkan pada bagian awal bab, data yang disembunyikan tidak hanya berupa teks, tetapi juga berupa citra, audio, atau video. Selain citra digita, media penampung data rahasia juga bisa berupa teks, audio, atau video. Namun di sini kita membatasi media penampung hanya citra digital saja. Penyembunyian data rahasia ke dalam citra digital akan mengubah kualitas citra tersebut. Kriteria yang harus diperhatikan dalam penyembunyian data adalah: 1. Fidelity. Mutu citra penampung tidak jauh berubah. Setelah penambahan data rahasia, citra hasil steganografi masih terlihat dengan baik. Pengamat tidak mengetahui kalau di dalam citra tersebut terdapat data rahasia. 2. Robustness. Data yang disembunyikan harus tahan (robust) terhadap berbagai operasi manipulasi yang dilakukan pada citra penampung, seperti pengubahan kontras, penajaman, pemampatan, rotasi, perbesaran gambar, pemotongan (cropping), enkripsi, dan sebagainya. Bila pada citra penampung dilakukan operasi-operasi pengolahan citra tersebut, maka data yang disembunyikan seharusnya tidak rusak (tetap valid jika diekstraksi kembali) 3. Recovery. Data yang disembunyikan harus dapat diungkapkan kembali (reveal). Karena tujuan steganografi adalah data hiding, maka sewaktu-waktu data rahasia di dalam citra penampung harus dapat diambil kembali untuk digunakan lebih lanjut.

13.3 Teknik Penyembunyian Data Penyembunyian data dilakukan dengan mengganti bit-bit data di dalam segmen citra dengan bit-bit data rahasia. Hingga saat ini sudah banyak dikemukakan oleh para ilmuwan metode-metode penyembunyian data. Metode yang paling sederhana adalah metode modifikasi LSB (Least Significant Bit Modification). Pada susunan bit di dalam sebuah byte (1 byte = 8 bit), ada bit yang paling berarti (most significant bit atau MSB) dan bit yang paling kurang berarti (least significant bit atau LSB). Sebagai ilustrasi, di bawah ini dijelaskan metode modifikasi LSB untuk menyisipkan watermark pada citra (gambar) digital. Misalnya pada byte 11010010, bit 1 yang pertama (digarisbawahi) adalah bit MSB dan bit 0 yang terakhir (digarisbawahi) adalah bit LSB. Bit yang cocok untuk diganti adalah bit LSB, sebab penggantian hanya mengubah nilai byte tersebut satu lebih tinggi atau satu lebih rendah dari nilai sebelumnya. Misalkan byte tersebut di dalam gambar menyatakan warna tertentu, maka perubahan satu bit LSB tidak mengubah warna tersebut secara berarti. Lagi pula, dan ini keuntungan yang dimanfaatkan, mata manusia tidak dapat membedakan perubahan yang kecil.

200


Misalkan segmen pixel-pixel citra sebelum penambahan bit-bit watermark adalah 00110011

10100010

11100010

01101111

Misalkan data rahasia (yang telah dikonversi ke sistem biner) adalah 0111. Setiap bit dari watermark menggantikan posisi LSB dari segmen data citra menjadi: 00110010

10100011

11100011

01101111

Untuk memperkuat penyembunyian data, bit-bit data tidak digunakan mengganti byte-byte yang berurutan, namun dipilih susunan byte secara Misalnya jika terdapat 50 byte dan 6 bit data yang akan disembunyikan, byte yang diganti bit LSB-nya dipilih secara acak, misalkan byte nomor 36, 10, 18, 49.

untuk acak. maka 5, 21,

Bilangan acak dibangkitkan dengan pseudo-random-number-generator (PRNG). PRNG menggunakan kunci rahasia untuk membangkitkan posisi pixel yang akan digunakan untuk menyembunyikan bit-bit. PRNG dibagun dalams ejumlah cara, salah satunya dengan menggunakan algoritma kriptografi DES (Data Encryption Standard), algoritma hash MD5, dan mode kriptografi CFB (Chiper-Feedback Mode). Tujuan dari enkripsi adalah menghasilkan sekumpulan bilangan acak yang sama untuk setiap kunci enkripsi yang sama. Bilangan acak dihasilkan dengan cara memilih bit-bit dari sebuah blok data hasil enkripsi. Teknik penyembunyian data untuk citra 8-bit berbeda dengan citra 24-bit. Seperti sudah dijelaskan di dalam Bab 3, berkas citra bitmap terdiri atas bagian header, palet RGB, dan data bitmap. Pada citra 8-bit, setiap elemen data bitmap menyatakan indeks dari peta warnanya di palet RGB. Pada citra 24-bit, tidak terdapat palet RGB, karena nilai RGB langsung diuraikan dalam data bitmap. Setiap elemen data bitmap panjangnya 3 byte, masing-masing byte menyatakan komponen R, G, dan B.

Teknik Penggantian Bit pada Citra bukan 24-bit. Sebelum melakukan penggantian bit LSB, semua data citra yang bukan tipe 24-bit diubah menjadi format 24-bit. Jadi, setiap data pixel sudah mengandung komponen RGB. Setiap byte di dalam data bitmap diganti satu bit LSB-nya dengan bit data yang akan disembunyikan. Jika byte tersebut merupakan komponen hijau (G), maka penggantian 1 bit LSB-nya hanya mengubah sedikit kadar warna hijau, dan perubahan ini tidak terdeteksi oleh mata manusia.


201

Teknik Penggantian Bit pada Citra 24-bit. Karena data bitmap pada citra 24-bit sudah tersusun atas komponen RGB, maka tidak perlu dilakukan perubahan format. Setiap byte di dalam data bitmap diganti satu bit LSB-nya dengan bit data yang akan disembunyikan.

Perubahan Jumlah Warna Pada citra 8-bit, jumlah warna terbatas, hanya 256 warna. Pengubahan format citra 8-bit menjadi 24-bit akan menghasilkan warna baru (yang semula tidak terdapat di dalam palet RGB). Setiap elemen RGB pada tabel palet berpotensi menjadi 8 warna berbeda setekah proses penggantian bit LSB. Hal ini karena setiap data bitmap terdiri atas 3 byte, maka tersedia 3 bit LSB untuk penggantian. Penggantian 3 bit LSB menghasilkan 23 = 8 kombinasi warna. Dengan demikian, steganografi pada citra 256 warna berpotensi menghasilkan 256 × 8 = 2048 warna. Untuk menghindari kelebihan warna dari 256, maka sebelum proses penyembunyian data, warna citra 8-bit diturunkan terlebih dahulu menjadi 32 warna (jika jumlah warnanya kurang dari 32, tidak perlu dilakukan penurunan warna). Dengan demikian, jika setiap warna menghasilkan 8 warna baru, jumlah warna seluruhnya maksimum 32 × 8 = 256 warna. Penurunan jumlah warna dilakukan dengan cara kuantisasi warna (color quantization). Penurunan jumlah warna harus tetap menghasilkan citra yang tampak persis seperti citra semula. Algoritma kuantisasi warna ada beberapa buah, antara lain algoritma diversity. Prinsip algoritma diversity adalah memaksimumkan perbedaan warna. Algoritma Diversity: 1. Buat histogram citra. Warna yang frekuensi kemunculannya 0 dibuang karena tidak akan digunakan. 2. Pilih warna dengan frekuensi kemunculan tertinggi sebagai warna patokan. Masukkan warna ini ke dalam senarai warna terpilih. 3. Cari warna yang mempunyai perbedaan terjauh dengan warna patokan. Masukkan warna tersebut ke dalam senarai warna terpilih. Perbedaan dua buah warna dihitung dengan rumus jarak Euclidean: d = { (r1 – r2)2 + (g1 – g2)2 + (b1 – b2)2 }1/2 yang dalam hal ini, r1, g1, dan b1 adalah komponen RGB dari warna pertama, dan r2, g2, dan b2 adalah komponen RGB dari warna kedua. 4. Untuk setiap warna yang tersisa di dalam list, hitung jaraknya dari masingmasing warna di dalam senarai warna terpilih. Ambil warna yang paling jauh berbeda dengan warna yang sudah dipilih. Lakukan langkah 4 ini berulang kali sampai k warna sudah terpilih. 202


13.4 Ukuran Data Yang Disembunyikan Ukuran data yang akan disembunyikan bergantung pada ukuran citra penampung. Pada citra 8-bit yang berukuran 256 × 256 pixel terdapat 65536 pixel, setiap pixel berukuran 1 byte. Setelah diubah menajdi citra 24-bit, ukuran data bitmap menjadi 65536 × 3 = 196608 byte. Karena setiap byte hanya bisa menyembunyikan satu bit di LSB-nya, maka ukuran data yang akan disembunyikan di dalam citra maksimum 196608/8 = 24576 byte. Ukuran data ini harus dikurangi dengan panjang nama berkas, karena penyembunyian data rahasia tidak hanya menyembunyikan isi data tersebut, tetapi juga nama berkasnya. Semakin besar data disembunyikan di dalam citra, semakin besar pula kemungkinan data tersebut rusak akibat manipulasi pada citra penampung.

13.5 Teknik Pengungkapan Data Data yang disembunyikan di dalam citra dapat dibaca kembali dengan cara pengungkapan (reveal atau extraction). Posisi byte yang menyimpan bit data dapat diketahui dari bilangan acak yang dibangkitkan oleh PRNG. Karena algoritma kriptografi yang digunakan menggunakan kunci pada proses enkripsi, maka kunci yang sama digunakan untuk membangkitkan bilangan acak. Bilangan acak yang dihasilkan sama dengan bilangan acak yang dipakai pada waktu penyembunyian data. Dengan demikian, bit-bit data rahasia yang bertaburan di dalam citra dapat dikumpulkan kembali. Di bawah ini ditampilkan contoh steganografi yang diambil dari program Tugas Akhir Lazarus Poli [POL98] yang diberi nama DATAhide. Untuk setiap contoh, digunakan kunci yang sama: informatika. Tampilan awal program diperlihatkan pada Gambar 13.2. Upa-menu yang ada pada menu Operasi adalah Penyembunyian data dan Pengungkapan data.


203

Gambar 13.2 Tampilan awal program DATAhide [POL98].

Contoh-contoh Hasil Steganografi 1. Citra penampung: citra 24 bit (berwarna) Data yang disembunyikan: citra berwarna (a) Penampung: citra peppers.bmp (512 × 512 pixel, 769 KB)

204

(b) Data yang disembunyikan: citra handshak.bmp (44 KB)


(c) Hasil penyembunyian data (peppers.bmp + handshak.bmp):

(d) Berkas handshak-stega.bmp (44 KB) hasil pengungkapan:

Gambar 13.4 Penyembunyian citra handshaking ke dalam citra berwarna 24 bit (peppers.bmp)

2. Citra penampung: citra 24 bit (berwarna) Data yang disembunyikan: teks (a) Penampung: citra peppers.bmp (512 × 512 pixel, 769 KB)

(b) Data yang disembunyikan: hendro.doc (20 KB) LETTER OF RECOMMENDATION To Whom It May Concern, Herewith I highly recommend Mr. R. Hendro Wicaksono continue his postgraduate study at your university. My recommendation is based on my experience as his lecturer in several courses for the past four years. He has shown me his excellent attitude and personality. He is a hard working person and he has a lot of creative ideas. He is also a very intelligent student and he cooperates very well with his peers whenever they had to work together. During his study, he showed diligence and eagerness to achieve his goal. He sets very high standard for himself and organizes himself very well to achieve the standard. I am confident that if he can maintain his goal work, he should be able to complete the postgraduate program well within the stipulated time. I am sure that his abilities and his personal qualities along with his academic capabilities will help his to obtain his Master’s degree at your university, which will be very useful for our country.


205

Bandung, November 15, 2002 Yours Sincerely, Ir. Rinaldi Munir, M.Sc. Senior Lecturer Informatics Engineering Department, Institute Technology of Bandung (ITB) Jl. Ganesha No. 10, Bandung 40132 Email : [email protected] Phone +62-22-2508135 Indonesia

(c) Hasil penyembunyian data (peppers.bmp + hendro.doc):

(d) Hasil pengungkapan data (hendro-stega.doc, 20 KB): LETTER OF RECOMMENDATION To Whom It May Concern, Herewith I highly recommend Mr. R. Hendro Wicaksono continue his postgraduate study at your university. My recommendation is based on my experience as his lecturer in several courses for the past four years. He has shown me his excellent attitude and personality. He is a hard working person and he has a lot of creative ideas. He is also a very intelligent student and he cooperates very well with his peers whenever they had to work together. During his study, he showed diligence and eagerness to achieve his goal. He sets very high standard for himself and organizes himself very well to achieve the standard. I am confident that if he can maintain his goal work, he should be able to complete the postgraduate program well within the stipulated time. I am sure that his abilities and his personal qualities along with his academic capabilities will help his to obtain his Master’s degree at your university, which will be very useful for our country. Bandung, November 15, 2002 Yours Sincerely, Ir. Rinaldi Munir, M.Sc. Senior Lecturer Informatics Engineering Department, Institute Technology of Bandung (ITB) Jl. Ganesha No. 10, Bandung 40132 Email : [email protected] Phone +62-22-2508135 Indonesia

Gambar 13.5 Penyembunyian dokumen teks ke dalam citra berwarna 24 bit (peppers.bmp)

206


2. Citra penampung: citra 8 bit (greyscale) Data yang disembunyikan: audio (a) Penampung: citra barbara.bmp (512 × 512 pixel, 258 KB)

(b) Data yang disembunyikan: chord.wav (95 KB), yaitu berkas musik dari Windows.

(dimainkan dengan media player)

(c) Hasil penyembunyian data (barbara.bmp + chord.wav)

(d) Berkas chord-stega.wav (95 KB) hasil pengungkapan:

(dimainkan dengan media player)

Pada kasus ini, terjadi penurunan kualitas gambar karena pengaruh penurunan jumlah warna (color quantization)!

Gambar 13.6 Penyembunyian data audio ke dalam citra greyscale 8-bit


207

13.6 Watermarking Salah satu karya intelektual yang dilindungi adalah barang dalam bentuk digital, seperti software dan produk multimedia seperti teks, musik (dalam format MP3 atau WAV), gambar/citra (image), dan video digital (VCD). Selama ini penggandaan atas produk digital tersebut dilakukan secara bebas dan leluasa. Hasil penggandaan persis sama dengan aslinya. Pemegang hak cipta atas produk digital tersebut tentu dirugikan karena ia tidak mendapat royalti dari usaha penggandaan tersebut. Sebenarnya masalah penyalahgunaan hak cipta pada bidang multimedia tidak hanya mengenai penggandaan dan pendistribusiannya saja, tetapi juga mengenai label kepemilikan. Kebanyakan produk digital tersebut tidak mencantumkan siapa pemegang hak ciptanya. Kalaupun bukti kepemilikan itu ada, biasanya informasi kepemilikan disertakan pada sampul pembungkus yang menerangkan bahwa produk multimedia tersebut adalah milik pembuatnya. Masalahnya, distribusi produk multimedia saat ini tidak hanya secara offline, tetapi juga dapat dilakukan lewat internet. Jika anda masuk ke situs-situs web di internet, anda dapat menemukan informasi berupa teks, gambar, suara, dan video. Semua produk digital tersebut dapat anda download dengan mudah. Anda pun juga dapat mempertukarkan data digital dengan layanan internet seperti e-mail. Masalahnya, hampir semua data digital yang bertebaran di dunia internet tidak mencantumkan informasi pemiliknya. Seseorang yang telah mendapatkan produk digital dapat mengklaim bahwa produk tersebut adalah hasil karyanya. Berhubung tidak ada bukti kepemilikan sebelumnya, maka klaim tersebut mungkin saja dipercaya. Salah satu cara untuk melindungi hak cipta multimedia adalah dengan menyisipkan informasi ke dalam data multimedia tersebut dengan teknik watermarking. Informasi yang disisipkan ke dalam data multimedia disebut watermark, dan watermark dapat dianggap sebagai sidik digital (digital signature) dari pemilik yang sah atas produk multimedia tersebut. Dengan kata lain, watermark yang disisipkan menjadi label hak cipta dari pemiliknya. Pemberian signature dengan teknik watermarking ini dilakukan sedemikian sehingga informasi yang disisipkan tidak merusak data digital yang dilindungi. Sehingga, seseorang yang membuka produk multimedia yang sudah disisipi watermark tidak menyadari kalau di dalam data multimedia tersebut terkandung label kepemilikan pembuatnya. Jika ada orang lain yang mengklaim bahwa produk multimedia yang didapatkannya adalah miliknya, maka pemegang hak cipta atas karya multimedia tersebut dapat membantahnya dengan mengekstraksi watermark dari dalam data multimedia yang disengketakan. Watermark yang diekstraksi dibandingkan dengan watermark pemegang hak cipta. Jika sama, berarti memang dialah pemegang hak cipta produk multimedia tersebut.

208


Pada dasarnya, teknik watermarking adalah proses menambahkan kode identifikasi secara permanen ke dalam data digital. Kode identifikasi tersebut dapat berupa teks, gambar, suara, atau video. Selain tidak merusak data digital produk yang akan dilindungi, kode yang disisipkan seharusnya memiliki ketahanan (robustness) dari berbagai pemrosesan lanjutan seperti pengubahan, transformasi geometri, kompresi, enkripsi, dan sebagainya. Sifat robustness berarti data watermark tidak terhapus akibat pemrosesan lanjutan tersebut.

Sejarah Watermarking Watermarking sudah ada sejak 700 tahun yang lalu. Pada akhir abad 13, pabrik kertas di Fabriano, Italia, membuat kertas yang diberi watermark atau tanda-air dengan cara menekan bentuk cetakan gambar atau tulisan pada kertas yang baru setengah jadi. Ketika kertas dikeringkan terbentuklah suatu kertas yang berwatermark. Kertas ini biasanya digunakan oleh seniman atau sastrawan untuk menulis karya mereka. Kertas yang sudah dibubuhi tanda-air tersebut sekalius dijadikan identifikasi bahwa karya seni di atasnya adalah milik mereka [HEN03]. Ide watermarking pada data digital (sehingga disebut digital watermarking) dikembangkan di Jepang tahun 1990 dan di Swiss tahun 1993. Digital watermarking semakin berkembang seiring dengan semakin meluasnya penggunaan internet, objek digital seperti video, citra, dan suara yang dapat dengan mudah digandakan dan disebarluaskan.

Perbedaan Steganografi dengan Watermarking Watermarking merupakan aplikasi dari steganografi, namun ada perbedaan antara keduanya. Jika pada steganografi informasi rahasia disembunyikan di dalam media digital dimana media penampung tidak berarti apa-apa, maka pada watermarking justru media digital tersebut yang akan dilindungi kepemilikannya dengan pemberian label hak cipta (watermark). Meskipun steganografi dan watermarking tidak sama, namun secara prinsip proses penyisipan informasi ke dalam data digital tidak jauh berbeda. Beberapa metode yang sudah ditemukan untuk penyisipan watermark adalah metdoe LSB (seperti pada penjelasan steganografi di atas), metode adaptif, metode spread spectrum, dan sebagainya.


209

Data watermark yang lazim disisipkan ke dalam data digital adalah teks, citra, atau suara. Watermark berupa teks mengandung kelemahan karena kesalahan satu bit akan menghasilkan hasil teks yang berbeda pada waktu verifikasi (ektraksi). Watermark berupa suara atau citra lebih disukai karena kesalahan pada beberapa bit watermark tidak menghasilkan perubahan yang berarti pada waktu verifikasi. Hasil ekstraksi watermark yang mengandung kesalahan tersebut masih dapat dipersepsi secara visual (atau secara pendengaran jika watermark-nya berupa suara). Citra yang sering digunakan sebagai watermark biasanya logo atau lambang.

Penyisipan Watermark Di sini kita hanya meninjau watermarking pada citra digital. Proses penyisipan watermark ke dalam citra disebut encoding dan ditunjukkan Gambar 13.7. Encoding dapat disertai dengan pemasukan kunci atau tidak memerlukan kunci. Kunci diperlukan agar watermark hanya dapat diekstraksi oleh pihak yang sah. Kunci juga dimaksudkan untuk mencegah watermark dihapus oleh pihak yang tidak berhak. kunci

Citra

Encoding

Citra berwatermark

Watermark Gambar 13.7 Proses penyisipan watermark pada citra digital

Gambar 13.8 memperlihatkan sebuah gambar (image) paprika yang disisipi dengan watermark berupa gambar hitam putih yang menyatakan identifikasi pemiliknya (Shanty) [HEN03]. Perhatikanlah bahwa setelah disisipi watermark, gambar paprika tetap kelihatan mulus, seolah-olah tidak pernah disisipi watermark sebelumnya. Sebenarnya tidaklah demikian, gambar paprika tersebut mengalami sedikit perubahan akibat watermarking, namun mata manusia mempunyai sifat kurang peka terhadap perubahan kecil ini, sehingga manusia sukar membedakan mana gambar yang asli dan mana gambar yang sudah disisipi watermark.

210


+

=

Watermark

Citra asli

Citra ter-watermark

Gambar 13.8 Memberi watermark pada citra peppers

Verifikasi Watermark Verifikasi watermark dilakukan untuk membuktikan status kepemilikan citra digital yang disengketakan. Verifikasi watermark terdiri atas dua sub-proses, yaitu ekstraksi watermark dan pembandingan. Sub-proses ekstraksi watermark disebut juga decoding, bertujuan mengungkap watermark dari dalam citra. Decoding dapat mengikutsertakan citra asal (yang belum diberi watermark) atau tidak sama sekali, karena beberapa skema watermarking memang menggunakan citra asal dalam proses decoding untuk meningkatkan unjuk kerja yang lebih baik [HEN03]. Sub-proses pembandingan bertujuan membandingkan watermark yang diungkap dengan watermark asli dan memberi keputusan tentang watermark tersebut. Proses verifikasi watermark ditunjukkan pada Gambar 13.9. kunci

Citra yang diuji

Citra asal

Decoding

watermark yang terekstraksi

Pembandingan

keputusan

watermark asli Gambar 13.9 Proses verifikasi watermark pada citra digital


211

Selain untuk tujuan pelabelan hak cipta (copyright labelling), watermarking juga dimanfaatkan untuk tujuan-tujuan lain sebagai berikut [SUP00]: 1. Tamper-proofing. Watermarking digunakan sebagai alat untuk mengidentifikasi atau menunjukkan bahwa data digital telah mengalami perubahan dari aslinya. 2. Feature location. Watermarking digunakan untuk mengidentifikasi isi dari data digital pada lokai-lokasi tertentu. 3. Annotation/caption. Watermarking digunakan hanya sebagai keterangan tentang data digital itu sendiri.

212


Bab 14

Pemampatan Citra Fraktal

etode pemampatan cira fraktal (fractal image compression) adalah metode lossy compression yang relatif baru. Metode ini mengeksploitasi kemiripan bagian-bagian di dalam citra dan menghitung transformasi yang memetakan bagian-bagian caitra yang memiliki kemiripan tersebut. Pembahasan di dalam Bab 14 ini dimulai dari teori mengenai fraktal, kemudian konsep pemampatan fraktal, lalu aplikasi pemampatan fraktal untuk memampatkan sembarang citra.

M

14.1 Definisi Fraktal Sejarah fraktal dapat dirunut dari buku Benoit Mandelbrot yang berjudul The Fractal Geometry of Nature. Jika geometri Euclidean digunakan untuk merepresentasikan bentuk-bentuk yang dibuat oleh manusia (bujursangkar, lingkaran, bloa, dsb), maka geometri fraktal merupakan cara yang alami untuk merepresentasikan bentuk-bentuk objek di alam. Fraktal dapat didefinisikan dari dua buah properti [MUN99]: 1) self similarity, dan 2) matra (dimension). 1. Fraktal adalah obyek yang memiliki kemiripan dirinya-sendiri (self-similarity) namun dalam skala yang berbeda. Ini artinya, bagian-bagian dari obyek akan tampak sama dengan obyek itu sendiri bila dilihat secara keseluruhan. Gambar 14.1 memperlihatkan tiga buah contoh fraktal, yaitu segitiga Sierpinski, daun pakis Barnsley, dan pohon fraktal. 2. Fraktal adalah objek yang memiliki matra bilangan riil atau pecahan (fractional). Kata terakhir inilah yang menurunkan kata fraktal.

Bab 14_Pemampatan Citra Faktral

213

Gambar 14.1 Segitiga Sierpinski, daun pakis Barsnsley, dan pohon fractal

14.2 Iterated Function System (IFS) Michael Barnsley (1988) merepresentasikan fraktal ke dalam model matematika yang dinamakan IFS (Iterated Function System), melalui buku, Fractals Everywhere. IFS dimetaforakan sebagai sebuah mesin foto copy yang disebut Multiple Reduction Copy Machine (MRCM). MRCM memiliki banyak lensa dan setiap lensa melakukan pengecilan gambar dalam jumlah yang banyak. Gambar dihasilkan dari mesin copy dioperasikan kembali sebagai masukan untuk membuat salinan berikutnya (Gambar 14.2).

Salinan ke-1 Gambar masukan Mesin copy

...

Salinan ke-2

Gambar 14.2 Multiple Reduction Copy Machine (MRCM)

Hal yang menarik dari MRCM adalah, apapun gambar awal yang digunakan, MRCM selalu konvergen ke gambar akhir yang sama. Gambar 14.3 memperlihatkan hasil salinan setelah beberapa kali lelaran dari MRCM yang

214


disusun oleh tiga buah lensa, setiap lensa memiliki faktor pengecilan setiap lensa adalah ½. Gambar akhir yang dihasilkan selalu segitiga Sierpinski.

Gambar awal

Salinan 1

Salinan 2

Salinan 3

Salinan 20

Gambar 14.3 Apapun gambar awalnya, MRCM selalu menghasilkan segitiga Sierpienski .

Secara matematis, sistem lensa pada MRCM dapat dinyatakan dengan sekumpulan transformasi affine w1, w2, …, wn. Setiap transformasi wi melakukan pencondongan, pemutaran, pengecilan, dan penggeseran terhadap salinan (copy) citra masukan. Setiap transformasi affine dinyatakan sebagai matriks dengan enam buah elemen:

a b w= c d

e f 

(14.1)

Sembarang titik (x,y) pada gambar masukan ditansformasikan oleh w menjadi

 x'   x  a b   x   e   y ' = w  y  =  c d   y  +  f  = Ax + t          

(14.2)

Setiap transformasi affine wi menghasilkan salinan citra yang lebih kecil; yaitu, untuk sembarang citra awal A yang diberikan, dihasilkan salinan affine, w1(A), w2(A), …, wn(A). Gabungan dari seluruh salinan tersebut adalah W(A), yang merupakan keluaran dari mesin, W(A) = w1(A) + w2(A) + … + wn(A)


(14.3)

215

W, yang dinamakan operator Hutchinson, adalah gabungan (collage) dari sejumlah transformasi individual wi, yaitu

W = w1 U w2 U ... U wn =

n

Uw

(14.4)

i

i =1

Setiap transformasi affine wi bersifat kontraktif, yaitu wi memetakan dua buah titik menjadi lebih dekat. Ini berlaku untuk semua titik di bidang citra. Akibatnya, MRCM selalu menghasilkan salinan gambar yang ukurannya lebih kecil daripada ukuran gambar semula. Sifat kontraktif saja tidak begitu penting. Sifat ini menjadi penting bila MRCM dijalankan dengan skema kalang umpan-balik terhadap gambar awal. Yaitu, diberikan citra awal A0, diperoleh n

A1 = W(A0) =

Uw (A ) i

0

i =1

A2 = W(A1) = W(W(A0)) = W2(A0) A3 = W(A2) = W(W(A1)) = W(W(W(A0))) = W3(A0) M An = Wn(A0) Jika W seluruhnya kontraktif, maka untuk n → ∞ lelarannya konvergen ke sebuah citra yang unik, A∞. Citra A∞ disebut titik-tetap (fixed-point) atau invariant dari proses lelaran, dan attractor dari W. Titik-tetap adalah citra A∞ sedemikian sehingga A∞ = W(A∞)

(14.5)

Jadi, jika A∞ dipilih sebagai citra awal, maka tidak ada perubahan pada hasil transformasinya. Sedangkan attractor dari W adalah citra A∞ sedemikian sehingga A∞ = lim Wn(A0 ) untuk sembarang citra awal A0 . n →∞

(14.6)

Persamaan yang terakhir ini menyatakan bahwa tidak peduli apa pun citra awal yang digunakan, limit lelarannya selalu menghasilkan citra akhir yang sama. Dengan kata lain, citra attractor adalah unik. Tansformasi affine yang menghasilkan citra titik-tetap segitiga Sierpinski adalah

 0.5 0.0 0.0   0.5 0.0 0.5 w1 =  w2 =     0.0 0.5 0.0   0.0 0.5 0.0 

216

 0.5 0 .0 0.25 w3 =    0.0 0.5 0.5 


Skema pembentukan segitiga Sierspinski dengan ketiga transformasi w1, w2, dan w3 ditunjukkan pada Gambar 14.4.

w3 w1 w2 Gambar 14.4. Cetak biru MRCM untuk membentuk segitiga Sierpinski.

Jika jumlah transformasi affine meningkat menjadi empat dengan setiap w i adalah sebagai berikut:

 0.85 0.04 0.0 w1 =    − 0.04 0.85 1.6 

 0.20 − 0.26 0 .0  w2 =    0.23 0 .22 1.6 

 − 0.15 0.28 0.0  w3 =    0 .26 0.52 0.44

 0.0 0.0 0.0  w4 =    0.0 0.16 0.0 

maka MRCM konvergen ke citra fraktal yang terkenal, yang dinamakan tanaman pakis Barnsley (Barnsley’s fern) – Gambar 14.5. Di sini, w1 mengendalikan keseluruhan bentuk, w2 membangkitkan daun kiri, w3 membangkitkan daun kanan, dan w4 menghasilkan batang.

w1

w2 w3

w4 Gambar 14.5 Pakis Barnsley dan empat buah transformasi affine-nya


217

14.3 Pengkodean Citra dengan IFS Menyimpan citra sebagai kumpulan pixel membutuhkan memori yang besar, namun bila yang disimpan adalah transformasi affine-nya, maka memori yang dibutuhkan jauh lebih sedikit. Cara ini melahirkan gagasan pengkodean citra dengan nisbah pemampatan yang tinggi. Pakis Barnsley misalnya, dibangkitkan dengan empat buah transformasi affine, masing-masingnya terdiri atas enam buah bilangan riil (4 byte), sehingga dibutuhkan 4 × 6 × 4 byte = 96 byte untuk menyimpan keempat transformasi itu. Bandingkan bila citra pakis Barnsley disimpan dengan representasi pixel hitam putih (1 pixel = 1 byte) berukuran 550 × 480 membutuhkan memori sebesar 264.000 byte. Maka, nisbah pemampatan citra pakis adalah 264.000 : 96 = 2750 : 1, suatu nisbah yang sangat tinggi. Kesulitan utama pemampatan dengan IFS adalah menemukan bagian citra yang mirip dengan keseluruhan citra. Intervensi manusia diperlukan untuk memandu menemukan bagian citra yang mirip dengan citra secara keseluruhan. Selain itu, pemampatan citra dengan IFS yang telah dikemukakan di atas hanya dapat diterapkan untuk citra yang memiliki self-similarity saja. Citra alami, disamping mempunyai warna, hampir tidak pernah self-similar secara keseluruhan. Karena itu, pemampatan sembarang citra (baik citra berwarna maupun citra greyscale) dengan IFS tidak dapat dilakukan. Terobosan penting dibuat oleh Arnaud D. Jacquin, mahasiwa Barnsley. Melalui tulisan monumentalnya pada tahun 1992, Jacquin meyajikan skema otomatis pengkodean citra yang dikenal dengan nama Partitoned Iterated Function System (PIFS). PIFS dapat digunakan untuk memampatkan sembarang citra, baik citra skala-abu maupun citra berwarna, dan tidak terbatas untuk citra fraktal saja.

14.4 Partitioned Iterated Function System (PIFS) Citra alami (natural image) umumnya hampir tidak pernah self-similar secara keseluruhan. Karena itu, citra alami pada umumnya tidak mempunyai transformasi affine terhadap dirinya sendiri. Tetapi, untunglah citra alami seringkali memiliki self-similarity lokal, yaitu memiliki bagian citra yang mirip dengan bagian lainnya, misalnya citra berskala-abu (greyscale) Lena pada Gambar 14.6 (bagian yang mirip ditandai di dalam kotak putih. Sebagai contoh, bagian topi Lena mirip dengan bagian topi di dalam bayangan cermin, bagian bahu mirip dengan bagian bahu yang lebih besar, dan sebagainya). Kemiripan lokal yang banyak terdapat pada citra alami bersifat selftransformability, yaitu bagian citra yang lebih kecil dapat diperoleh dengan

218


mentransformasikan bagian citra yang lebih besar namun mirip dengan bagian citra yang lebih kecil itu [FIS94]. Setiap transformasi itu disebut IFS lokal. Gabungan dari seluruh hasil transformasi itu adalah citra fraktal yang menyerupai (atau menghampiri) citra semula.

Gambar 14.6 Kemiripan lokal pada citra Lena

Langkah pertama yang dilakukan dalam proses pemampatan adalah membagi citra atas sejumlah blok yang berukuran sama dan tidak saling berir isan, yang disebut blok jelajah (range). Untuk menyederhanakan masalah, blok jelajah diambil berbentuk bujursangkar. Untuk setiap blok jelajah, dicari bagian citra yang berukuran lebih besar dari blok jelajah –yang disebut blok ranah (domain)dan paling mirip (cocok) dengan blok jelajah tersebut (Gambar 14.7), kemudian turunkan transformasi affine (IFS lokal) wi yang memetakan blok ranah ke blok jelajah. Hasil dari semua pemasangan ini adalah Partitioned Iterated Function System (PIFS). Kemiripan antara dua buah (blok) citra diukur dengan metrik jarak. Metrik jarak yang banyak digunakan dalam praktek adalah metrik rms (root mean square):

d rms =

1 n

n

n

∑∑ ( z'

ij

− z ij ) 2

(14.7)

i =1 j =1

dengan z dan z’ adalah nilai intensitas pixel dari dua buah citra, dan n adalah jumlah pixel di dalam citra.


219

Blok ranah

Blok jelajah

Gambar 14.7 Pemetaan dari blok ranah ke blok jelajah

Seperti yang sudah dijelaskan, blok ranah dan blok jelajah keduanya berbentuk bujursangkar, tetapi ukuran blok ranah diambil dua kali blok jelajah. Untuk blok jelajah berukuran 8×8 pixel dan blok ranah berukuran 16×16 pixel, citra 256×256 misalnya, dapat dibagi menjadi 1024 buah blok jelajah yang tidak saling beririsan dan (256 – 16 + 1)2 = 58.081 buah blok ranah berbeda (yang beririsan). Himpunan blok ranah yang digunakan dalam proses pencarian kemiripan dimasukkan ke dalam pul ranah (domain pool). Pul ranah yang besar menghasilkan kualitas pemampatan yang lebih baik, tetapi membutuhkan waktu pencocokan yang lebih lama. Sebelum proses pencarian kemiripan dimulai, setiap blok ranah diskalakan sehingga ukurannya sama dengan ukuran blok jelajah. Penskalaan ini dimaksudkan agar jarak antara blok jelajah dan blok ranah mudah dihitung dengan persamaan 14.7. Penskalaan dilakukan dengan menjadikan 2×2 buah pixel menjadi satu buah pixel. Nilai satu buah pixel tersebut adalah rata-rata nilai keempat pixel. Transformasi affine wi untuk citra berskala-abu disusun oleh bagian spasial yang memetakan posisi pixel di blok ranah Di ke posisi pixel di blok jelajah Ri, dan bagian intensitas yang mengubah nilai intensitas pixel. Titik (x,y) dengan intensitas z yang termasuk di dalam blok ranah dipetakan oleh w i menjadi:

 x'   x   ai  y' = w  y =  c i      i  z   0  z ' 

bi di 0

0 0  si 

 x   ei   y +  f     i  z   oi 

(14.8)

Dengan pemetaan wi di atas, intensitas tiap pixel juga diskalakan dan digeser, yaitu z’ = si z + oi

220

(14.9)


Parameter si menyatakan faktor kontras pixel (seperti tombol kontras di TV). Bila si bernilai 0, maka pixel menjadi gelap, bila si sama dengan 1 kontrasnya tidak berubah; antara 0 dan 1 pixel berkurang kontrasnya, di atas 1 kontrasnya bertambah. Parameter o i menyatakan ofset kecerahan (brightness) pixel (seperti tombol kecerahan di TV. Nilai oi positif mencerahkan gambar dan nilai oi negatif menjadikannya gelap. Kedua parameter tersebut dapat memetakan secara akurat blok jelajah berskala abu ke blok jelajah berskala abu. Untuk menjamin efek kontraktif dalam arah spasial, maka blok ranah harus berukuran lebih besar daripada blok jelajah. Untuk alasan praktis, ukuran blok ranah diambil dua kali ukuran blok jelajah (perbandingannya 2:1). Jadi, jika ukuran blok jelajah adalah B×B pixel, maka ukuran blok ranah adalah 2B×2B pixel. Perbandingan ini membuat transformasi affine menjadi lebih sederhana, yaitu

 x'   y' = w i    z ' 

 x   0.5 0 0   y  =  0 0.5 0      0 si   z   0

 x   ei   y +  f     i  z   oi 

(14.10)

Parameter ei dan fi mudah dihitung karena keduanya menyatakan pergeseran sudut kiri blok ranah ke sudut kiri blok jelajah yang bersesuaian. Sedangkan si dan oi dihitung dengan menggunakan rumus regresi berikut [FIS94]: Diberikan dua buah blok citra yang mengandung n buah pixel dengan intensitas d1, d2, …, dn (dari blok ranah D i) dan r1, r2, …, rn (dari R i). Nilai s dan o diperoleh dengan meminimumkan total kuadrat selisih antara intensitas pixel blok Di yang diskalakan dengan s lalu digeser sejauh o dan intensitas pixel blok R i : n

E=

∑ (d '

i

− ri ) 2 =

i =1

n

∑ (s ⋅ d

i

+ o − ri )2

(14.11)

i=1

Nilai minimum E terjadi bila turunan parsialnya terhadap s dan o adalah nol, yang terjadi bila turunan pertama E sama dengan 0, atau E’=0 yang dipenuhi oleh n  s= 

∑ d r −∑ d ∑ n  ∑ d − (∑ d ) n

n

i i

i =1

n

n

2 i =1 i

r i =1 i

i

i =1

n

i =1

i

2

 

(14.12)



dan

o=

n  1 n r − s di   i n  i =1 i =1 

∑

∑


(14.13)

221

∑

∑

∑

1 n ri . Dengan nilai s dan n i =1 o yang telah diperoleh, maka kuadrat galat antara blok jelajah dan blok ranah adalah Jika n

n

d2 −( i =1 i

E=

n

d ) 2 = 0 maka s = 0 dan o = i =1 i

n n n  n  n    1 r 2i + s s d i2 − 2 d i ri + 2o d i  + o no − 2 ri      n i =1 i =1 i =1   i =1    i =1

∑

∑

∑

∑

∑

(14.14)

Metriks rms, drms , tidak lain adalah drms =

E /n

(14.15)

Selanjutnya, transformasi affine wi diuji terhadap blok ranah D i untuk menghasilkan blok uji Ti = wi (Di) (Gambar 14.8). Jarak antara T dan Ri dihitung dengan persamaan 14.15. Transformasi affine yang terbaik ialah transformasi w yang meminimumkan jarak antara Ri dan T. Runtunan pencarian dilanjutkan untuk blok jelajah berikutnya sampai seluruh blok jelajah sudah dipasangkan dengan blok ranah. Hasil dari proses pemampatan adalah sejumlah IFS lokal yang disebut PIFS. Seluruh parameter PIFS di-pak dan disimpan di dalam berkas eksternal. Parameter PIFS yang perlu disimpan hanya ei, fi, si, oi, dan jenis operasi simetri untuk setiap blok jelajah. Dalam praktek, parameter ei dan fi diganti dengan posisi blok ranah yang dipetakan ke blok jelajah. Parameter ai, bi, ci, dan di tidak perlu disimpan karena nilainya sudah tetap, yaitu ½ untuk ai dan di, dan 0 untuk bi dan ci. Algoritma pencocokan blok yang dijelaskan di atas adalah algoritma brute force, karena untuk setiap blok jelajah pencocokan dilakukan dengan seluruh blok ranah di dalam pul untuk memperoleh pencocokan terbaik.

1

2

Pul ranah

3

Blok ranah

Blok jelajah

1

1 2

E

5

T 3 w

2 6

3

4

7

8

9

10

11

12

13

15

14

16

Gambar 14.8. Blok jelajah 5 dibandingkan dengan blok ranah 3 di dalam pul ranah. Transformasi w ditentukan, lalu blok ranah 3 ditransformasikan dengan w menghasilkan T. Jarak antara T dengan blok jelajah 5 diukur.

222


14.5 Rekonstruksi Citra Rekonstruksi (decoding) citra dilakukan dengan melelarkan PIFS dari citra awal sembarang. Karena setiap IFS lokal kontraktif, baik kontraktif dalam matra intensitas maupun kontraktif dalam matra spasial maka lelarannya akan konvergen ke citra titik-tetap PIFS. Kontraktif intensitas penting untuk menjamin konvergensi ke citra semula, sedangkan kontaktif spasial berguna untuk membuat rincian pada citra untuk setiap skala. Jika PIFS yang ditemukan selama proses pemampatan bagus, yaitu gabungan dari transformasi seluruh blok ranah dekat dengan citra semula (diukur dengan persamaan 14.7), maka titik-tetap PIFS juga dekat dengan citra semula tersebut. Selama proses pemulihan, setiap IFS lokal mentransformasikan sekumpulan blok ranah menjadi sekumpulan blok jelajah. Karena blok jelajah tidak saling beririsan dan mencakup keseluruhan pixel citra, maka gabungan seluruh blok jelajah menghasilkan citra titik -tetap yang menyerupai citra semula. Gambar 14.8 memperlihatkan hasil rekonstruksi citra Lena setelah 1, 2, dan 6 lelaran [MUN99]. Citra awal yang digunakan adalah citra adalah citra dengan nilai pixel yang dibangkitkan secara acak. Konvergensi ke citra titik-tetap berlangsung cepat. Konvergensi umumnya dapat diperoleh dalam 8 sampai 10 kali lelaran [MUN99]. Karena transformasi affine kontraktif dalam arah spasial, maka semakin banyak rincian citra yang dibuat pada setiap lelaran

(a) Citra awal


(b) Lelaran ke-1

223

(c) Lelaran ke-2

(d) Lelaran ke-6

Gambar 14.8 Rekonstruksi citra Lena [MUN99].

Contoh-contoh hasil pemampatan citra fraktal [MUN99]:

Citra asli (256 × 256 pixel) Lena.bmp (66 KB)

224

Citra hasil pemampatan fraktal Lena.fra (7 KB)


Citra asli (256 × 256 pixel) Collie.bmp (66 KB)

Citra hasil pemampatan fraktal Collie.fra (9 KB)

Citra asli (512 × 512 pixel) Kapal.bmp (258 KB) Bab 14_Pemampatan Citra Faktral

225

Citra hasil pemampatan fraktal Kapal.fra (9 KB)

226


Citra asli (316 × 404 pixel) Potret.bmp (126 KB)

Citra hasil pemampatan fraktal Potret.fra (17 KB)

Tabel 14.1 Perbandingan ukuran berkas citra sebelum dan sesudah dimampatkan No.

Ukuran (byte) 263.222

Citra FRA (byte) KAPAL512.FRA

Ukuran

1

Citra BMP (byte) Kapal.bmp

8.956

Nisbah (%) 96,6

2

Lena.bmp

66.614

LENA256.FRA

8.137

87,6

3

Collie.bmp

66.614

COLLI256.FRA

9.150

86,3

4

Potret.bmp

128.782

17.437

86,5

POTRET.FRA

Tabel 14.2 Perbandingan ukuran citra berformat BMP, JPG, GIF, dan fraktal (FRA) Nama Citra Kapal.bmp

Format BMP (byte) 263.222

Format JPG (byte) 24.367

Format GIF (byte) 242.452

Format FRA (byte) 8.956

Lena.bmp

66.614

7.126

70.292

8.137

Collie.bmp

66.614

7.021

69.965

9.150

Potret.bmp

128.782

16.377

136.377

17.437


227

14.6 Pemampatan Citra Berwarna Penelitian yang dilakukan tentang pemampatan citra fraktal kebanyakan ditujukan pada citra hitam-putih (greyscale). Karena citra berwarna terdiri atas 3 komponen (RGB), maka pemampatan fraktal dilakukan secara terpisah untuk masing-masing komponen. Tetapi, cara ini tidak dianjurkan karena membuat waktu pemampatan tiga kali lebih lama daripada cira skala-abunya, begitu pula ukuran berkas hasil pemampatannya tiga kali lebih besar. Teknik yang mangkus adalah dengan mentransformasi model RGB ke model YIQ, XYZ, atau IHS. Pemampatan fraktal cukup dilakukan terhadap komponen luminansinya (Y pada model YIQ, Y pada model XYZ, atau I pada model IHS) [FIS94]. Dua komponen sisanya dimampatkan dengan metode berbeda (misalnya dengan metode Huffman). Pada proses rekonstruksi citra, model YIQ, XYZ, atau IHS ditransformasikan kembali ke model RGB.

228


Bab 15

Pengenalan Pola

eskipun materi pengenalan pola (pattern recognition) tidak termasuk ke dalam pokok bahasan buku ini, namun sebagai bab penutup Penulis akan menjelaskan secara singkat mengenai pengenalan pola.

M

15.1 Pengertian Pola dan Ciri Pola adalah entitas yang terdefinisi dan dapat diidentifikasi melalui ciri-cirinya (features) [HEN95]. Ciri-ciri tersebut digunakan untuk membedakan suatu pola dengan pola lainnya. Ciri yang bagus adalah ciri yang memiliki daya pembeda yang tinggi, sehingga pengelompokan pola berdasarkan ciri yang dimiliki dapat dilakukan dengan keakuratan yang tinggi. Sebagai contoh, Pola

Ciri

huruf

tinggi, tebal, titik sudut, lengkungan garis, dll

suara

amplitudo, frekuensi, nada, intonasi, warna, dll

tanda tangan

panjang, kerumitan, tekanan, dll

sidik jari

lengkungan, jumlah garis, dll

Bab 15_Pengenalan Pola

229

Ciri pada suatu pola diperoleh dari hasil pengukuran terhadap objek uji. Khusus pada pola yang terdapat di dalam citra, ciri-ciri yang dapat diperoleh berasal dari informasi: a. Spasial: intensitas pixel, histogram, … b. Tepi: arah, kekuatan, … c. Kontur: garis, elips, lingkaran, … d. Wilayah/bentuk: keliling, luas, pusat massa, … e. Hasil transformasi Fourier: frekuensi, …

15.2 Sistem Pengenalan Pola Pengenalan pola bertujuan menentukan kelompok atau kategori pola berdasarkan ciri-ciri yang dimiliki oleh pola tersebut. Dengan kata lain, pengenalan pola membedakan suatu objek dengan objek lain. Terdapat dua pendekatan yang dilakukan dalam pengenalan pola: pendekatan secara statistik dan pendekatan secara sintaktik atau struktural [HEN95]. (a) Pengenalan Pola secara Statistik Pendekatan ini menggunakan teori-teori ilmu peluang dan statistik. Ciri-ciri yang dimiliki oleh suatu pola ditentukan distribusi statistiknya. Pola yang berbeda memiliki distribusi yang berbeda pula. Dengan menggunakan teori keputusan di dalam statistik, kita menggunakan distribusi ciri untuk mengklasifikasikan pola. Contoh teori keputusan: Misalkan ada N pola yang dikenali, yaitu w1, w2, …, wN dan fungsi peluang atau kerapatan dari ciri-ciri pada pola diketahui. Jika x merupakan hasil pengukuran ciri-ciri, maka

p ( x wi )

, i = 1, 2, …, N

dapat dihitung. Sebagai contoh, misalkan diketahui fungsi kerapatan dari diameter buah jeruk dan apel yang diperlihatkan pada Gambar 15.1.

230


peluang 1 p(diameter | jeruk) p(diameter | apel)

a

0

b

diameter

Gambar 15.1. Grafik fungsi kerapatan dari ciri diameter jeruk dan apel.

Jika sebuah objek diukur dan diperoleh diameternya adalah a cm, maka kita mengklasifikasikan objek tersebut sebagai “jeruk”, karena p(a | jeruk) > p(a | apel) dan jika hasil pengukuran diameter adalah b cm, kita mengklasifikasikan objek tersebut sebagai “apel”, karena p(b | jeruk) < p(b | apel) Sistem pengenalan pola dengan pendekatan statistik ditunjukkkan oleh diagram pada Gambar 15.2. Pola

Preprocessing

Feature Extraction

Classification

Feature Selection

Learning

Pengenalan ( recognition) Pelatihan ( training) Pola terokan

Gambar 15.2. Sistem pengenalan pola dengan pendekatan statistik.


231

Ada dua fase dalam sistem pengenalan pola: (i) fase pelatihan dan (ii) fase pengenalan. Pada fase pelatihan, beberapa contoh citra dipelajari untuk menentukan ciri yang akan digunakan dalam proses pengenalan serta prosedur klasifikasinya. Pada fase pengenalan, citra diambil cirinya kemudian ditentukan kelas kelompoknya. Preprocessing Proses awal yang dilakukan untuk memperbaiki kualitas citra (edge enhancement) dengan menggunakan teknik-teknik pengolahan citra yang sudah diejelaskan pada bab-bab sebelum ini.

Feature Extraction Proses mengambil ciri-ciri yang terdapat pada objek di dalam citra. Pada proses ini objek di dalam citra mungkin perlu dideteksi seluruh tepinya, lalu menghitung properti-properti objek yang berkaitan sebagai ciri. Beberapa proses ekstraksi ciri mungkin perlu mengubah citra masukan sebagai citra biner, melakukan penipisan pola, dan sebagainya.

Classification Proses mengelompokkan objek ke dalam kelas yang sesuai.

Feature Selection Proses memilih ciri pada suatu objek agar diperoleh ciri yang optimum, yaitu ciri yang dapat digunakan untuk membedakan suatu objek dengan objek lainnya.

Learning Proses belajar membuat aturan klasifikasi sehingga jumlah kelas yang tumpang tindih dibuat sekecil mungkin. Kumpulan ciri dari suatu pola dinyatakan sebagai vektor ciri dalam ruang bahumatra (multi dimensi). Jadi, setiap pola dinyatakan sebagai sebuah titik dalam ruang bahumatra. Ruang bahumatra dibagi menjadi sejumlah uparuang (sub-ruang). Tiap uparuang dibentuk berdasarkan pola-pola yang sudah dikenali kategori dan ciri-cirinya (melalui fase pelatihan). Lihat Gambar 15.3.

232


3 kelas

2 kelas yang beririsan

ciri 2

ciri 2

batas kelas batas keputusan ciri 1

ciri 1

Gambar 15.3. Contoh pembagian kelas pola

(b) Pengenalan Pola secara Sintaktik Pendekatan ini menggunakan teori bahasa formal. Ciri-ciri yang terdapat pada suatu pola ditentukan primitif dan hubungan struktural antara primitif kemudian menyusun tata bahasanya. Dari aturan produksi pada tata bahasa tersebut kita dapat menentukan kelompok pola. Gambar 15.4 memperlihatkan sistem pengenalan pola dengan pendekatan sintaktik. Pengenalan pola secara sintaktik lebih dekat ke strategi pengenalan pola yang dilakukan manusia, namun secara praktek penerapannya relatif sulit dibandingkan pengenalan pola secara statistik.

Pola

Preprocessing

Primitive Extraction

Classification

Primitive Selection

Learning

Pengenalan (recognition) Pelatihan (training) Pola terokan

Gambar 15.4. Sistem pengenalan pola dengan pendekatan sintaktik.


233

Pendekatan yang digunakan dalam membentuk tata bahasa untuk mengenali pola adalah mengikuti kontur (tepi batas) objek dengan sejumlah segmen garis terhubung satu sama lain, lalu mengkodekan setiap garis tersebut (misalnya dengan kode rantai). Setiap segmen garis merepresentasikan primitif pembentuk objek.

Contoh 15.1. [GON77] Pembentukan tata bahasa (grammar) untuk mengenali kromosom (lihat Gambar 15.5) yang diusulkan oleh Ledley (1964, 1965). Tata bahasa untuk mengenali kromosom adalah G = (N, ∑, P, S), yang dalam hal ini ∑ = {a, b, c, d, e} N = {S, T, A, B, C, D, E, F} S = { S, T} dan himpunan aturan produksi P: 1) 2) 3) 4) 5) 6) 7) 8) 9)

234

S → CC T → AC C → BC C → CB C → FD C → EF E → Fc D → cF A → bA

10) A → Ab 11) A → e 12) B → bB 13) B → Bb 14) B → b 15) B → d 16) F → bF 17) F → Fb 18) F → a


a

b

c

d

e

(a)

a b

a b

e

b b

c

c b

d

d

b

b b

a

a

c b

b

b

b

ebabcbab

a a abcbabdbabcbabdb (b)

Gambar 15.5 (a) Primitif grammar kromosom, (b) pengkodean kromosom.

Contoh 15.2. [GON77] Pembentukan grammar dengan Picture Description Language (PDL) yang diusulkan oleh Shaw (1970). Lihat Gambar 15.6. Tata bahasa untuk mengenali bentuk “rumah” adalah G = (N, ∑, P, S), yang dalam hal ini

∑ ={a

,b

,c

,d

}

N = {S, A1, A2, A3, A4, A5} S = { S} dan himpunan aturan produksi P: S → d + A1 A1 → c + A2 A2 → ~d*A2 A3 → a + A4 A4 → b*A5 A5 → c Bab 15_Pengenalan Pola

235

t

t

h

h

t h d

c + (~d)

d + (c+(~d))

(a)

(b)

(c)

t

h

t

h

h t

a+d

(a + b) *c

(d + (c + (~d)))*((a+b)*c)

(d)

(e)

(f)

Gambar 15.6 Langkah-langkah pembentukan struktur PDL

236


Daftar Pustaka

[BAL82]

Ballard, Dana H., Computer Vision, Prentice-Hall, 1982.

[DAV90]

Davies, E. R., Machine Vision: Theory, Algorithms, Practicalities, Academic Press, 1990.

[DUL97]

Dulimarta, Hans S., Diktat Kuliah Pengolahan Citra, Jurusan Teknik Informatika ITB, 1997.

[FIS94]

Fisher, Yuval, Fractal Image Compression: Theory & Application, Springer-Verlag, 1994.

[GAL90]

Galbiati, Louis J., Machine Vision and Digital Image Processing Fundamentals, Prentice Hall, 1990.

[GON77]

Gonzalez, Rafael C., Digital Image Processing, Addison-Wesley Publishing, 1977.

[HEN95]

Hendradjaya, Bayu, Catatan Kuliah Pengolahan Citra, 1995.

[HEN03]

Hendrawan, Shanty Meliani, Robust and Non Blind Watermarking pada Citra Dijital dengan Teknik Spread Spectrum, Tugas Akhir Departemen Teknik Informatika, 2003.

[JAI89]

Jain, Anil K, Fundamentals of Digital Image Processing, Prentice-Hall International, 1989.

[JAI95]

Jain, Ramesh, Machine Vision, McGraw-ill, 1995.

[KER88]

Kernighan, Brian W., The C Programming Language 2Th , Prentice Hall, 1988.

[LOW91]

Low, Adrian, Introductory Computer Vision and Image Processing, McGraw-Hill, 1991.

[MEN89]

Mengko, Richard, Workshop On Image Processing & Pattern Recognition, PAU Mikroelektronika ITB, 1989.

[MUN99]

Munir, Rinaldi, Pengelompokan Blok Ranah Berdasarkan Rata-rata dan Variansi Intensitas Pixel pada Pemampatan Citra dengan Transformasi Fraktal, Tesis Magister Informatika ITB, 1999.

[MUR92]

Murni, Aniati, Pengantar Pengolahan Citra, Elex Media Komputindo, 1992.

[PIT93]

Pitas, Ioannis, Digital Image Processing Algorithms, Prentice-Hall International, 1993.

Daftar Pustaka

247

[POL98]

Poli, Lazarus, Penerapan Steganografi dengan Citra Dijital Sebagai File Penampung, Tugas Akhir Jurusan Teknik Informatika, 1998.

[SCH89]

Schalkoff, Robert J., Digital Image Processing and Computer Vision, John Wiley & Sons, 1989.

[SID95]

Sid-Ahmed, A. A, Image Processing, Theory, Algorithms, & Architectures, McGraw-Hill, 1995.

[SUP00]

Supangkat, Suhono H., Watermarking Sebagai Teknik Penyembunyian Label Hak Cipta pada Data Digital, Jurnal Teknik Elektro, Vo. 6, No. 3, 2000.

[WIC01]

Wicaksono, R Hendro dkk, Tugas IF473 Pengolahan Citra, Departemen Teknik Informatika, 2001.

[WOR93]

Works, The Math, Image Processing Toolbox For Use with MATLAB, The Math Works Inc, 1993.

248


Perbaikan Kualitas Citra

Recommend Documents