BAB 2 KAJIAN PUSTAKA
2.1.
Image Processing Data atau informasi tidak hanya disajikan dalam bentuk teks, tetapi juga dapat berupa gambar, audio (bunyi, suara, musik), dan video. Keempat macam data atau informasi ini sering disebut multimedia. Era teknologi informasi saat ini tidak dapat dipisahkan dari multimedia. Situs web (website) di Internet dibuat semenarik mungkin dengan menyertakan visualisasi berupa gambar atau video yang dapat diputar. Beberapa waktu lalu istilah SMS begitu populer diantara pengguna telepon genggam (handphone). Tetapi, saat ini orang tidak hanya dapat mengirim pesan dalam bentuk teks tapi juga dalam bentuk gambar maupun video yang dikenal dalam layanan MMS (Multimedia Message Service). Gambar (image) adalah istilah lain untuk gambar sebagai salah satu komponen multimedia memegang peranan sangat penting sebagai bentuk informasi visual. Gambar mempunyai karakteristik yang tidak dimiliki oleh data teks, yaitu gambar kaya dengan informasi. Maksudnya sebuah gambar dapat memberikan informasi lebih banyak daripada informasi tersebut disajikan dalam bentuk tekstual. Pengolahan gambar digital atau Digital Image Processing adalah bidang yang berkembang sangat pesat sejalan dengan kemajuan teknologi pada industri saat ini. Fungsi utama dari Digital Image Processing adalah untuk memperbaiki kualitas dari gambar sehingga gambar dapat dilihat lebih jelas tanpa ada 5
ketegangan pada mata, karena informasi penting diekstrak dari gambar yang dihasilkan harus jelas sehingga didapatkan hasil yang terbaik. Selain itu DIP digunakan untuk memproses data yang diperoleh dalam persepsi mesin, yaitu prosedur–prosedur yang digunakan untuk mengekstraksi informasi dari gambar informasi dalam bentuk yang cocok untuk proses komputer. Proses pengolahan gambar digital dengan menggunakan computer digital terlebih dahulu mentransformasikan gambar ke dalam bentuk besaran-besaran diskrit dari nilai tingkat keabuan pada titik-titik elemen gambar. Bentuk gambar ini disebut gambar digital. Elemen-elemen gambar digital apabila ditampilkan dalam layar monitor akan menempati sebuah ruang yang disebut dengan pixel (picture
elemen/pixel).
Teknik
dan
proses
untuk
mengurangi
atau
menghilangkan efek degradasi pada gambar digital meliputi perbaikan gambar (image enhancement), restorasi gambar (image restoration), dan transformasi spasial (spatial transformation). Subyek lain dari pengolahan gambar digital diantaranya adalah pengkodean gambar (image coding), segmentasi gambar (image segmentation), representasi dan diskripsi gambar (image representation and description ). Pengolahan gambar digital memiliki banyak aplikasi seperti pada bidang penginderaan jarak jauh, robotik, pemetaan, biomedis, dan sebagainya. Perlengkapan pengolahan gambar digital minimal terdiri atas alat pemasukan data gambar berupa digitizer atau scanner, computer digital, alat penyimpanan data dengan kapasitas yang besar. Beberapa aplikasi image processing dapat iimplementasikan dalam kehidupan sehari‐hari, seperti dalam wujud : 6
•
Pengolahan informasi data planet yang diterima dari pesawat ruang angkasa
Voyager,
diproses
untuk
meningkatkan
kontras
dan
seperti
implementasi
CAT
Scan
kejernihannya. •
Dalam
dunia
kesehatan,
(Computer‐Assisted Tomography), untuk memindai seluruh tubuh manusia secara visual. •
Image processing juga digunakan pada model system radar dan sonar.
2.1.1. Citra Secara harafiah, citra (image) adalah gambar pada bidang dwimatra (dua dimensi). Gambar 2.1 adalah citra seorang gadis model yang bernama Lena, dan gambar di sebelah kanannya adalah citra kapal di sebuah pelabuhan. Ditinjau dari sudut pandang matematis, citra merupakan fungsi menerus (continue) dari intensitas cahaya pada bidang dwimatra. Sumber cahaya menerangi objek, objek memantulkan kembali sebagian dari berkas cahaya tersebut. Pantulan cahaya ini ditangkap oleh oleh alat-alat optik, misalnya mata pada manusia, kamera, pemindai (scanner), dan sebagainya, sehingga bayangan objek yang disebut citra tersebut terekam. Citra sebagai keluaran dari suatu sistem perekaman data dapat bersifat : 1. optik berupa foto, 2. analog berupa sinyal video seperti gambar pada monitor televisi, 3. digital yang dapat langsung disimpan pada suatu pita magnetik.
7
Citra yang dimaksudkan di sini adalah “citra diam” (still images). Citra diam adalah citra tunggal yang tidak bergerak. Gambar 2.1 adalah dua buah citra diam. Untuk selanjutnya, citra diam kita sebut citra saja.
(a) Lena
(b) Kapal
Gambar 2.1 Citra Lena dan citra kapal
Citra bergerak (moving images) adalah rangkaian citra diam yang ditampilkan secara beruntun (sekuensial) sehingga memberi kesan pada mata kita sebagai gambar yang bergerak. Setiap citra di dalam rangkaian itu disebut frame. Gambar-gambar yang tampak pada film layar lebar atau televisi pada hakikatnya terdiri atas ratusan sampai ribuan frame.
2.1.2. Definisi Pengolahan Citra Meskipun sebuah citra kaya informasi, namun seringkali citra yang kita miliki mengalami penurunan mutu (degradasi), misalnya mengandung cacat atau derau (noise), warnanya terlalu kontras, kurang tajam, kabur (blurring), dan
8
sebagainya.Tentu saja citra semacam ini menjadi lebih sulit diinterpretasi karena informasi yang disampaikan oleh citra tersebut menjadi berkurang. Agar citra yang mengalami gangguan mudah diinterpretasi (baik oleh manusia maupun mesin), maka citra tersebut perlu dimanipulasi menjadi citra lain yang kualitasnya lebih baik. Bidang studi yang menyangkut hal ini adalah pengolahan citra (image processing). Pengolahan
citra
adalah
pemrosesan
citra,
khususnya
dengan
menggunakan komputer, menjadi citra yang kualitasnya lebih baik. Sebagai contoh, citra burung nuri pada Gambar 2.2 (a) tampak agak gelap, lalu dengan operasi pengolahan citra kontrasnya diperbaiki sehingga menjadi lebih terang dan tajam (b). Umumnya, operasi-operasi pada pengolahan citra diterapkan pada citra bila : 1.
perbaikan atau memodifikasi citra perlu dilakukan untuk meningkatkan kualitas penampakan atau untuk menonjolkan beberapa aspek informasi yang terkandung di dalam citra,
2.
elemen di dalam citra perlu dikelompokkan, dicocokkan, atau diukur,
3.
sebagian citra perlu digabung dengan bagian citra yang lain.
9
(a)
(b)
Gambar 2.2. (a) Citra burung nuri yang agak gelap, (b) Citra burung yang telah diperbaiki kontrasnya sehingga terlihat jelas dan tajam
Di dalam bidang komputer, sebenarnya ada tiga bidang studi yang berkaitan dengan data citra, namun tujuan ketiganya berbeda, yaitu: 1. Grafika Komputer (computer graphics). 2. Pengolahan Citra (image processing). 3. Pengenalan Pola (pattern recognition/image interpretation). Hubungan antara ketiga bidang (grafika komputer, pengolahan citra, pengenalan pola) ditunjukkan pada Gambar 2.3.
10
citra
Pengolahan Citra
citra Pengenalan Pola
Grafika Komputer deskripsi
deskripsi
Gambar 2. 3. Tiga bidang studi yang berkaitan dengan citra
Grafika Komputer bertujuan menghasilkan citra (lebih tepat disebut grafik atau picture) dengan primitif-primitif geometri seperti garis, lingkaran, dan sebagainya. Primitif-primitif geometri tersebut memerlukan data deskriptif untuk melukis elemen-elemen gambar. Contoh data deskriptif adalah koordinat titik, panjang garis, jari-jari lingkaran, tebal garis, warna, dan sebagainya. Grafika komputer memainkan peranan penting dalam visualisasi dan virtual reality.
Grafika
data deskriptif
Komputer
citra
Gambar 2. 4. Struktur Grafika Komputer
Contoh grafika komputer misalnya menggambar sebuah ‘rumah’ yang dibentuk oleh garis-garis lurus, dengan data masukan berupa koordinat awal dan koordinat ujung garis (Gambar 2.5).
11
Gambar 2. 5. (a) Program Grafika Komputer untuk membuat gambar ‘rumah (b)
Pengolahan Citra bertujuan memperbaiki kualitas citra agar mudah diinterpretasi oleh manusia atau mesin (dalam hal ini komputer). Teknik-teknik pengolahan citra mentransformasikan citra menjadi citra lain. Jadi, masukannya adalah citra dan keluarannya juga citra, namun citra keluaran mempunyai kualitas lebih baik daripada citra masukan. Termasuk ke dalam bidang ini juga adalah pemampatan citra (image compression).
citra
Pengolahan
citra
Citra
Gambar 2. 6. Struktur Pengolahan Citra
Pengubahan kontras citra seperti pada Gambar 2.2 adalah contoh operasi pengolahan citra. Contoh operasi pengolahan citra lainnya adalah penghilangan derau (noise) pada citra Lena (Gambar 2.7). Citra Lena yang di sebelah kiri mengandung derau berupa bintik-bintik putih (derau). Dengan operasi penapisan
12
(filtering), derau pada citra masukan ini dapat dikurangi sehingga dihasilkan citra Lena yang kualitasnya lebih baik.
(a)
(b)
Gambar 2.7. (a) Citra Lena yang mengandung derau, (b) hasil dari operasi penapisan derau.
Pengenalan Pola mengelompokkan data numerik dan simbolik (termasuk citra) secara otomatis oleh mesin (dalam hal ini komputer). Tujuan pengelompokan adalah untuk mengenali suatu objek di dalam citra. Manusia bisa mengenali objek yang dilihatnya karena otak manusia telah belajar mengklasifikasi objek-objek di alam sehingga mampu membedakan suatu objek dengan objek lainnya. Kemampuan sistem visual manusia inilah yang dicoba ditiru oleh mesin. Komputer menerima masukan berupa citra objek yang akan diidentifikasi, memproses citra tersebut, dan memberikan keluaran berupa deskripsi objek di dalam citra.
13
Pengenalan
citra
Pola
Deskripsi objek
Gambar 2.8. struktur Pengenalan Pola
Contoh pengenalan pola misalnya citra pada Gambar 2.9 adalah tulisan tangan yang digunakan sebagai data masukan untuk mengenali karakter ‘A’. Dengan menggunakan suatu algoritma pengenalan pola, diharapkan komputer dapat mengenali bahwa karakter tersebut adalah ‘A’.
Gambar 2.9. Citra karakter ‘A’ yang digunakan sebagai masukan untuk pengenalan huruf
Pengolahan citra mempunyai aplikasi yang sangat luas dalam berbagai bidang kehidupan kita antar lain : 1. Bidang Militer a. Mengenali sasaran peluru kendali melalui sensor visual. b. Mengidentifikasi pesawat musuh melalui radar. c. Teropong malam hari (night vision) 14
2. Bidang Medis / Kedokteran a. Mendeteksi retak/patah tulang dengan CT Scan. b. Rekonstuksi foto janin (USG). c. Mendeteksi kanker (kanker otak) 3. Bidang Biologi Pengenalan jenis kromosom melalui gambar mikroskopis 4. Bidang Pendidikan Pengolahan pendaftaran mahasiswa menggunakan scanner. 5. Bidang Geografi dan Geologi a. Pemetaan batas wilayah melalui foto udara / Landsat. b. Mengenali jenis dan bentuk lapisan batuan bawah permukaan bumi melalui rekonstruksi hasil seismic. 6. Bidang Kepolisian / Hukum a. Pengelan pola sidik jari (finger print). b. Rekonstruksi wajah pelaku kejahatan. c. Pengenalan pola hasil uji balistik. 7. Bidang Perdagangan a. Pembacaan barcode pada barang di swalayan. b. Mengenali huruf / angka pada suatu formulir secara otomatis. 8. Bidang Hiburan Pemampatan video (MPEG). 9. Komunikasi data Pemampatan citra yang ditransmisi (Internet).
15
2.1.3. Histogram Salah satu cara untuk memperbaiki suatu citra digital adalah dengan mengatur level dari brightness dan contrast-nya. Pertama-tama, kami akan menggambarkan
variasi-sebuah
brightness
pada
suatu
citra
dengan
menggunakan histogram citra tersebut dan bagaimana suatu citra dapat dimanipulasi dengan merubah histogram citra tersebut. Histogram akan menempatkan beberapa piksel dengan brightness level mereka yang sesuai. Untuk piksel dengan ukuran level brightness sebesar 8-bit maka brightness akan memiliki grey level yang berkisar antara nol (hitam) sampai 255 (putih). Sehingga histogram yang memiliki nilai brightness yang lebih kecil akan terlihat lebih gelap dibandingkan dengan yang memiliki nilai lebih besar. Gambar dibawah menunjukkan gambar sebuah ban mobil dengan histogramnya. Histogram pada gambar tersebut menunjukkan bahwa tidak semua grey level yang ada dalam histogram terpakai. Dapat kita lihat bahwa histogram yang memiliki grey level dibawah 120 memiliki tingkat kegelapan yang lebih gelap, dimana warna gelap tersebut dimiliki oleh ban mobil dan bagian bawah mobil, serta bayangan mobil yang memiliki warna cenderung hitam. Di sini juga terlihat bahwa apabila suatu gambar memiliki warna yang cenderung gelap maka secara keseluruhan histogram akan berkonsentrasi kearah kiri (hitam). Bandingkanlah gambar tersebut dengan gambar di bawahnya yang mana gambar tersebut adalah gambar yang sama, tetapi telah dinaikkan nilai
16
brightness-nya. Sekarang histogram cenderung merata dan agak sedikit terkonsentrasi ke arah kanan (putih).
Gambar 2.10. Gambar sebuah ban mobil dan histogramnya
Gambar 2.11. Gambar ban mobil dan histogramnya setelah dinaikkan nilai brightness-nya.
Disini kita dapat melihat bahwa kita belum memakai seluruh dari grey level yang tersedia. Kita dapat menarik histogram citra tersebut sehingga semua grey level yang tersedia sepenuhnya terpakai, dan teknik itu akan menghasilkan citra yang lebih jelas. Histogram ini juga dapat memperlihatkan kejanggalan bila didalam citra tersebut terdapat noise apabila histogram yang ideal telah kita ketahui. Sehingga kami dapat menghilangkan noise tersebut. Proses ini tidak hanya semata-mata
17
kami lakukan untuk mendapatkan citra yang lebih baik, tetapi juga untuk lebih memudahkan
tugas-tugas
kami dalam teknik-teknik pemprosesan citra
selanjutnya. 2.1.4. Operasi Pengolahan Citra Operasi-operasi yang dilakukan di dalam pengolahan citra banyak ragamnya.
Namun,
secara
umum,
operasi
pengolahan
citra
dapat
diklasifikasikan dalam beberapa jenis sebagai berikut: 1.
Perbaikan kualitas citra (image enhancement). Jenis operasi ini bertujuan untuk memperbaiki kualitas citra dengan cara
memanipulasi parameter-parameter citra. Dengan operasi ini, ciri-ciri khusus yang terdapat di dalam citra lebih ditonjolkan. Contoh-contoh operasi perbaikan citra: a. perbaikan kontras gelap/terang b. perbaikan tepian objek (edge enhancement) c. penajaman (sharpening) d. pembrian warna semu (pseudocoloring) e. penapisan derau (noise filtering) Gambar 2.12 adalah contoh operasi penajaman. Operasi ini menerima masukan sebuah citra yang gambarnya hendak dibuat tampak lebih tajam. Bagian citra yang ditajamkan adalah tepi-tepi objek.
18
(a)
(b)
Gambar 2.12. (a) Citra Lena asli, (b) Citra Lena setelah ditajamkan
2.
Pemugaran citra (image restoration). Operasi ini bertujuan menghilangkan/meminimumkan cacat pada citra.
Tujuan pemugaran citra hampir sama dengan operasi perbaikan citra. Bedanya, pada pemugaran citra penyebab degradasi gambar diketahui. Contoh-contoh operasi pemugaran citra: a. penghilangan kesamaran (deblurring). b. penghilangan derau (noise) Gambar 2.13 adalah contoh operasi penghilangan kesamaran. Citra masukan adalah citra yang tampak kabur (blur). Kekaburan gambar mungkin disebabkan pengaturan fokus lensa yang tidak tepat atau kamera bergoyang pada pengambilan gambar. Melalui operasi deblurring, kualitas citra masukan dapat diperbaiki sehingga tampak lebih baik.
19
(a)
(b)
Gambar 2.13. Kiri: Citra Lena yang kabur (blur), kanan: citra Lena setelah deblurring
3.
Pemampatan citra (image compression). Jenis operasi ini dilakukan agar citra dapat direpresentasikan dalam
bentuk yang lebih kompak sehingga memerlukan memori yang lebih sedikit. Hal penting yang harus diperhatikan dalam pemampatan adalah citra yang telah dimampatkan harus tetap mempunyai kualitas gambar yang bagus. Contoh metode pemampatan citra adalah metode JPEG. Perhatikan Gambar 2.14. Gambar sebelah kiri adalah citra kapal yang berukuran 258 KB. Hasil pemampatan citra dengan metode JPEG dapat mereduksi ukuran citra semula sehingga menjadi 49 KB saja.
20
(a)
(b)
Gambar 2.14. (a) Citra boat.bmp (258 KB) sebelum dimampatkan, (b) citra boat.jpg (49 KB) sesudah dimampatkan.
4.
Segmentasi citra (image segmentation). Jenis operasi ini bertujuan untuk memecah suatu citra ke dalam beberapa
segmen dengan suatu kriteria tertentu. Jenis operasi ini berkaitan erat dengan pengenalan pola. 5.
Pengorakan citra (image analysis) Jenis operasi ini bertujuan menghitung besaran kuantitif dari citra untuk
menghasilkan deskripsinya. Teknik pengorakan citra mengekstraksi ciri-ciri tertentu yang membantu dalam identifikasi objek. Proses segmentasi kadangkala diperlukan untuk melokalisasi objek yang diinginkan dari sekelilingnya. Contoh-contoh operasi pengorakan citra: a. Pendeteksian tepi objek (edge detection) b. Ekstraksi batas (boundary) c. Representasi daerah (region)
21
Gambar 2.15 adalah contoh operasi pendeteksian tepi pada citra Camera. Operasi ini menghasilkan semua tepi (edge) di dalam citra.
(a)
(b)
Gambar 2. 15. (a) Citra camera, (b) citra hasil pendeteksian seluruh tepi
6.
Rekonstruksi citra (image reconstruction) Jenis operasi ini bertujuan untuk membentuk ulang objek dari beberapa
citra hasil proyeksi. Operasi rekonstruksi citra banyak digunakan dalam bidang medis. Misalnya beberapa foto rontgen dengan sinar X digunakan untuk membentuk ulang gambar organ tubuh. 2.2.
Computer Vision Terminologi lain yang berkaitan erat dengan pengolahan citra adalah computer vision atau machine vision. Pada hakikatnya, computer vision mencoba meniru cara kerja sistem visual manusia (human vision). Human vision sesungguhnya sangat kompleks. Manusia melihat objek dengan indera penglihatan (mata), lalu citra objek diteruskan ke otak untuk diinterpretasi sehingga manusia mengerti objek apa yang tampak dalam pandangan matanya.
22
Hasil interpretasi ini mungkin digunakan untuk pengambilan keputusan (misalnya menghindar kalau melihat mobil melaju di depan). Computer vision merupakan proses otomatis yang mengintegrasikan sejumlah besar proses untuk persepsi visual, seperti akuisisi citra, pengolahan citra, klasifikasi, pengenalan (recognition), dan membuat keputusan. Computer vision terdiri dari teknik-teknik untuk mengestimasi ciri-ciri objek di dalam citra, pengukuran ciri yang berkaitan dengan geometri objek, dan menginterpretasi informasi geometri tersebut. Mungkin berguna bagi anda untuk mengingat persamaan berikut: Vision = Geometry + Measurement + Interpretation Proses-proses di dalam computer vision dapat dibagi menjadi tiga aktivitas: 1. Memperoleh atau mengakuisisi citra digital. 2. Melakukan teknik komputasi untuk memperoses atau memodifikasi data citra (operasi-operasi pengolahan citra). 3. Menganalisis dan menginterpretasi citra dan menggunakan hasil pemrosesan untuk tujuan tertentu, misalnya memandu robot, mengontrol peralatan, memantau proses manufaktur, dan lain-lain. mengklasifikasikan proses-proses di dalam computer vision dalam hirarkhi sebagai berikut :
23
Gambar 2. 16. (a) Citra camera, (b) citra hasil pendeteksian seluruh tepi
Dari penjelasan di atas, dapat kita lihat bahwa pengolahan citra dan pengenalan pola merupakan bagian dari computer vision. Pengolahan citra merupakan proses awal (preprocessing) pada computer vision, sedangkan pengenalan pola merupakan proses untuk menginterpretasi citra. Teknik-teknik di dalam pengenalan pola memainkan peranan penting dalam computer vision untuk mengenali objek. Jika dihubungkan dengan grafika komputer, maka computer vision merupakan kebalikannya. Grafika komputer membentuk (sintesis) citra, sedangkan computer vision mengoraknya (analisis). Pada masa awal kedua bidang ini, tidak ada hubungan antara keduanya, tetapi beberapa tahun belakangan kedua bidang tersebut berkembang semakin dekat. Computer vision
24
menggunakan representasi kurva dan permukaan dan beberapa teknik lain dari grafika komputer, sedangkan grafika komputer menggunakan teknik -teknik di dalam computer vision untuk memuat citra realistik (virtual reality). 2.3.
Retrival Citra Berbasis Konten RCBK adalah salah satu metodologi untuk pemanggilan kembali data gambar berdasarkan content sebuah gambar. Teknik RCBK yang banyak digunakan adalah teknik warna, teknik tekstur, dan teknik bentuk. Gambar 2.17 memperlihatkan bentuk umum system Retrival Citra Berbasis Konten (RCBK).
Image Database
Query Image
Pre-processing Pre-processing
Feature Extraction
Feature Extraction Indexing
Feature Database
Similarity Comparison
Retrival Result
Gambar 2.17. Langkah Retrival Citra Berbasis Konten
25
Indexing, retrieval, dan database merupakan tiga hal yang tidak dapat dipisahkan pada data dan informasi. Indexing yang baik akan sangat menentukan kecepatan dan ketepatan retrieval data yang secara phisik sangat ditentukan oleh model database yang digunakan. Gambar 2.17. menampilkan hubungan antar data, struktur index dan retrieval. Retrival Citra Berbasis Konten merupakan proses pengindeksan dan pengambilan (melalui proses pencarian) gambar berdasarkan isi (fitur) dari gambar. Jadi berbeda dengan teknik pengindeksan yang saat ini umum digunakan, yaitu dengan pemberian tag atau deskripsi singkat secara manual oleh manusia, yang mana selain sangat terbatas pada bahasa yang digunakan bisa saja sebuah tag ataupun deskripsi singkat yang diberikan bersifat ambigu atau memiliki makna yang berbeda, belum lagi jika memperhatikan adanya faktor kesalahan manusia. Namun jika “tag” yang digunakan adalah fitur dari gambar, yang mana seluruh proses pengambilan fitur tersebut dilakukan secara otomatis, maka tentu akan mengatasi batasan-batasan seperti yang telah disebutkan di atas yang terdapat pada sistem yang telah ada seperti saat ini pada umumnya. Sebuah gambar dapat direpresentasikan dengan berbagai macam cara, diantaranya: ‐
Warna Model warna RGB (red, green, blue) mendeskripsikan warna sebagai kombinasi positif dari 3 warna, yaitu merah, hijau, dan biru. Ciri warna suatu gambar dapat dinyatakan dalam bentuk histogram dari gambar tersebut. Histogram menghitung jumlah 26
piksel pada masing-masing jenis warna dengan membaca masingmasing piksel citra hanya sekali dan menambah jumlahnya pada tempat penyimpan yang tepat di histogram. ‐
Bentuk Ciri bentuk suatu gambar dapat ditentukan oleh tepi (sketsa), atau besaran moment dari suatu gambar. Pemakaian besaran moment pada ciri bentuk ini banyak digunakan dengan memanfaatkan nilai-nilai transformasi fourier dari gambar. Proses yang dapat digunakan untuk menentukan ciri bentuk adalah deteksi tepi, threshold, segmentasi dan perhitungan moment seperti (mean, median dan standard deviasi dari setiap lokal gambar).
‐
Tekstur Tekstur adalah properti bawaan pada semua citra permukaan, seperti hutan, perkebunan, kain dan lainnya. Tekstur berisi informasi penting tentang aransement struktur dari permukaan dan hubungannya terhadap lingkungan sekitarnya. Walau mudah bagi manusia untuk membedakannya, namun sangat sulit bagi komputer digital untuk mendefinisikannya.
Ekstraksi fitur (feature extraction) adalah salah satu tahapan dalam system RCBK yang berguna untuk mendapatkan karakteristik visual citra. Segmentasi adalah bagian dari proses ekstraksi ciri. Segmentasi bertujuan untuk mendapatkan segmen citra digital yang tegas antara layar belakang obyek pada citra digital. 27
Dari ketiga fitur tersebut, yang menjadi pusat perhatian adalah warna. Maka selanjutnya akan dibahas lebih lanjut tentang apa dan bagaimana fitur tersebut diekstrak. 2.3.1. Ekstraksi Fitur Warna Ada
beberapa
metoda
untuk
mengekstrak
fitur
visual
menggunakan vitur warna, yaitu: •
Histogram warna Merupakan fitur warna yang paling banyak digunakan. Histogram warna sangat efektif mengkarakterisasikan distribusi global dari warna dalam sebuah image.
•
Moment warna Ini merupakan representasi yang padat dari fitur warna dalam mengkarakterisasikan warna citra.
•
Tag bahasa warna Penggunaan distribusi warna secara global terkadang tidak
menguntungkan
karena
adanya
keterbatasan
kemampuan penglihatan manusia. Oleh karena itu diperkenalkanlah tag bahasa warna. Ini merupakan cara untuk mengindentifikasi citra dengan menyebut nama dari warna. Fitur yang diekstrak adalah warna, sehingga digunakanlah histogram HSV (Hue Saturation Value). Untuk mendapatkan nilai hue dari tiap pixel, digunakan perhitungan sebagai berikut:
28
Dimisalkan r, g, dan b masing-masing mewakili tingkat warna merah, hijau, dan biru dari sebuah pixel, dimana masing-masing nilai r, g, dan b memiliki nilai terendah 0 dan nilai tertinggi 255. Selain itu kita juga punya max yang mana isinya adalah max(r, g, b) dan min yang mana isinya adalah min(r, g, b). Sehingga digunakan rumus untuk mendapatkan nilai h (Hue) sebagai berikut:
0,
jika max = min
g-b + 360o) mod 360o, jika max = r max-min b-r 60o x + 120o, jika max = g max-min r-g 60o x max-min + 240o, jika max = g (60o x
h=
Sehingga h memiliki nilai minimum 0 dan nilai maksimum 360 (0° - 360°). Setelah itu untuk menghitung nilai saturation digunakanlah rumus:
S=
0,
jika max = 0
max-min min =1, max max
selain itu
Sedangkan untuk menghitung v (value) dari gambar berdasarkan rumus sebagai berikut: V = max Sebenarnya ada beberapa rumus lain untuk mendapatkan nilai Hue, tetapi rumus di atas dipilih karena rumus tersebut setidaknya 29
digunakan
di
dua
halaman
web
yang
ditemukan,
yaitu
http://en.wikipedia.org/wiki/HSV_color_space#Conversion_from_RGB_ to_HSL_or_HSV
(ensiklopedia
online)
dan
http://en.literateprograms.org/RGB_to_HSV_color_space_conversion_( C)#Efficient_integer_version (ensiklopedia online yang berfokus pada bidang pemrograman).
2.4.
Information Retrieval
Information Retrieval merupakan bagian dari computer science yang berhubungan dengan pengambilan informasi dari dokumen-dokumen yang didasarkan pada isi dan konteks dari dokumen-dokumen itu sendiri. Berdasarkan referensi dijelaskan bahwa Information Retrieval merupakan suatu pencarian informasi
(biasanya
berupa
dokumen)
yang
didasarkan
pada
suatu query (inputan user) yang diharapkan dapat memenuhi keinginan user dari kumpulan dokumen yang ada. Sedangkan, definisi query dalam Information Retrieval menurut referensi merupakan sebuah formula yang digunakan untuk mencari informasi yang dibutuhkan oleh user, dalam bentuk yang paling sederhana, sebuah query merupakan suatu keywords (kata kunci) dan dokumen yang mengandung keywords merupakan dokumen yang dicari dalam IRS. Model yang terdapat dalam Information Retrieval terbagi dalam 3 model besar, yaitu: 1. Set-theoretic models, model merepresentasikan dokumen sebagai himpunan kata atau frase. Contoh model ini ialah standard Boolean model dan extended Boolean model. 30
2.
Algebratic
model,
model
merepresentasikan
dokumen
dan
query sebagai vektor atau matriks similarity antara vektor dokumen dan vektor query yang direpresentasikan sebagai sebuah nilai skalar. Contoh model ini ialah vector space model dan latent semantic indexing (LSI). 3. Probabilistic model, model memperlakukan proses pengembalian dokumen sebagai sebuah probabilistic inference. Contoh model ini ialah penerapan teorema bayes dalam model probabilistik. Proses dalam Information Retrieval dapat digambarkan sebagai sebuah proses untuk mendapatkan relevant documents dari collection documents yang ada melalui pencarian query yang diinputkan user.
Gambar 2.18. Proses Information Retrieval
Sistem Information Retrieval berupaya untuk mengoptimalkan proses pencarian dan akses pada dokumen yang telah disimpan dalam bentuk elektronik secara cepat dan akurat. Dewasa ini teknik Information Retrieval telah berkembang luas dengan dikembangkannya banyak model. Dari sekian banyak model IR system yang dikembangkan, hampir sebagian besar dari model-model 31
tersebut membandingkan isi dari dokumen terhadap query hanya berdasarkan set term index yang tersedia saja. Hal ini dapat mengakibatkan performa IR system yang kurang baik dikarenakan dua faktor. Yang pertama, akan banyak dokumen yang tidak berkaitan dengan konsep atau ide yang diharapkan dihasilkan oleh IR system hanya dikarenakan dokumen tersebut mengandung term index yang dimasukkan dalam query. Yang kedua, banyak dokumen relevan yang tidak dihasilkan oleh IR system, dikarenakan dokumen tersebut tidak mengandung term yang diindex oleh query. Model Latent Semantic Indexing (LSI) merupakan salah satu model sistem Information Retrieval yang menerapkan prinsip Vector Space Model (VSM) yang keistimewaannya adalah memecahkan masalah semantic dalam term sehingga dokumen yang tidak mengandung term yang diminta pun dapat ditemukan karena memiliki hubungan dengan term yang diminta. Gambar arsitektur dari LSI dapat dilihat pada gambar 2.19.
Gambar 2.19. Arsitektur LSI
32
Dari ilustrasi pada gambar 2.19, dapat dilihat bahwa input dari LSI terdiri dari 2 jenis yaitu koleksi data asal yang akan menjadi topik dari pencarian yang dilakukan LSI dan input yang kedua adalah berupa set query yang merupakan kata kunci dari data yang ingin dicari oleh user. Koleksi data sebelum dapat digunakan dalam proses query akan memerlukan beberapa proses persiapan sebelumnya yang terdiri dari proses Lexical Analysis untuk mengidentifikasi tiap kata yang memiliki potensi menjadi term index. Kemudian langkah selanjutnya adalah dengan membentuk Term Data Matrix sebagai inverted file dari LSI. Langkah terakhir dalam persiapan data adalah proses dekomposisi matrix, yaitu memecah Term Data Matrix menjadi 3 matrix baru yang nilai dari elemen 3 matrix tersebut dapat mengungkap hubungan keterkaitan antar term dari tiap data. Metode yang digunakan untuk dekomposisi matrix ada 2 cara yaitu Singular Value Decomposition atau disingkat SVD dan Semi Discrete Matrix Decomposition atau disingkat SDD. SDD sebenarnya merupakan pengembangan lebih lanjut dari SVD dengan penyempurnaan pada masalah ruang penyimpanan matrix. Namun SDD dibanding dengan SVD terdapat penurunan pada tingkat akurasi dokumen yang dihasilkan sebagai jawaban untuk set query yang diminta. Perbandingan dan perbedaan dari kedua metode matrix dekomposisi tersebut dapat diamati pada tabel 2.1.
33
Tabel 2.1. Perbandingan SVD dengan SDD
2.5.
SVD Matrix SVD
SDD Matrix SDD
Matrix U dan V pada SVD menggunakan bilangan real untuk elemen matrixnya
Matrix X dan Y pada SDD menggunakan kombinasi angka -1, 0, atau 1 untuk elemen matrixnya
Ruang Penyimpanan
Ruang Penyimpanan
SVD membutuhkan ruang penyimpanan sebesar k (m+n+1) untuk matrixnya
SDD hanya membutuhkan ruang sebesar k (m+n) untuk menyimpan matrixnya
Perhitungan SVD
Perhitungan SDD
Nilai matrix SVD dicari berdasarkan nilai eigen dan vector eigen
Nilai matrix SDD didapatkan dari hasil iterasi matrix
Latent Semantic Indexing Latent Semantic Indexing (LSI) adalah sebuah metode indexing dan retrieval yang menggunakan sebuah teknik matematika yang disebut Singular Value Decomposition (SVD) untuk mengidentifikasi pola-pola dalam hubunganhubungan antara kondisi-kondisi dan konsep-konsep yang terdapat dalam sebuah koleksi teks tak berstruktur. 2.5.1. Sejarah Latent Semantic Indexing Istilah LSI (Latent Semantic Indexing) mulai muncul pada tahun 2003 ketika Google membeli sebuah perusahaan bernama Applied Semantics, dimana teknologi piranti lunak dikembangkan untuk dapat mengekstrak dan mengorganisasikan informasi dari situs-situs web layaknya manusia yang mengerjakan. Tujuan dari Google membeli teknologi tersebut adalah untuk mencocokan iklan Adsense (milik Google) dengan halaman web yang sesuai sehingga iklan yang relevan akan muncul pada halaman yang tepat. Sebelumnya Adsense hanya 34
mencocokan kata kunci pada suatu halaman dengan kata kunci pada iklan Adsense tersebut. Namun masalah segera muncul ketika jutaan halaman dibuat hanya untuk berisi kata-kata kunci agar menarik (menjebak) pengunjung untuk mengklik iklan. Latent semantic indexing memberikan langkah penting bagi proses pengindeksan dokumen. Selain mencatat kata-kata kunci di dalam sebuah dokumen, ia juga mempelajari dokumen tersebut secara keseluruhan. Walaupun demikian, algoritma LSI sebenarnya tidak bisa untuk memahami arti dari kata-kata, ia hanya memperhatikan pola-pola yang ada sehingga membuat algoritma ini seolah cerdas. 2.5.2. Singular Value Decomposition SVD (Singular Value Decomposition) adalah salah satu teknik untuk mengolah matriks dari cabang ilmu aljabar linear yang diperkenalkan oleh Beltrami pada tahun 1873. SVD merupakan salah satu alat matematis yang digunakan untuk merepresentasikan sebuah matriks dan mampu melakukan berbagai analisis dan komputasi matriks. Dalam aljabar linier, SVD adalah sebuah faktorisasi penting dari sebuah matriks persegi bilangan real atau pun kompleks, dengan banyak pengaplikasiannya di bidang signal processing dan statistic. Dimisalkan A adalah sebuah matriks m kali n dimana entrientrinya diperoleh dari K (sekumpulan bilangan real atau pun kompleks). Sehingga kemudian bentuk faktorisasinya adalah A = USVT dimana U adalah sebuah matriks unitary m kali m dari K, sedangkan matriks S 35
adalah matriks diagonal m kali n dengan bilangan real non negative pada diagonalnya, dan VT merupakan transpose konjugasi dari V (sebuah matriks unitary n kali n dari K). Faktorisasi semacam ini disebut SVD dari A. Umumnya entri-entri diagonal Si,i disusun sedemikian rupa sehingga bergaya non-increasing. Dalam kasus semacam ini, matriks diagonal S ditentukan secara unik oleh A (walaupun matriks U dan V tidak). Entri-entri diagonal dari S adalah singular values dari A. Pada A = USVT , kolom-kolom dari V membentuk sebuah set arah vektor berbasis “input” orthonormal untuk A (ini merupakan eigenvector dari [AT][A]). Kolom-kolom dari U membentuk sebuah set arah vektor berbasis “output” orthonormal untuk A (ini merupakan eigenvector dari [A][AT]). Nilai-nilai dari diagonal matriks S adalah singular values, yang mana bisa disebut sebagai “gain controls” scalar yang mana setiap input yang bersangkutan dikali agar memberikan output yang bersangkutan (ini merupakan akar kuadrat dari eigenvalue yang bersangkutan dengan kolom-kolom yang sama pada U dan V). 2.5.3. K-means
Setelah proses SVD dilakukan, maka kumpulan feature vector seolah membentuk kumpulan titik-titik koordinat di bidang dua dimensi. Selanjutnya, dari titik-titik tersebut akan dibentuk kelonpok-kelompok dengan menggunakan metode K-means clustering.
36
K-means clustering adalah sebuah metode analisa cluster yang mana bertujuan untuk membagi n observasi ke dalam k cluster yang mana tiap observasi merupakan anggota dari cluster berdasarkan titik tengah terdekatnya. Pada K-Means clustering, pengelompokan data dilakukan berdasarkan jarak data ke titik pusat kelompok. Jumlah kelompok yang ingin dibentuk ditentukan terlebih dahulu dan kemudian akan dicari posisi titik pusat setiap kelompok dan data apa saja yang termasuk ke dalam kelompok tersebut. Algoritma yang harus dilakukan adalah: -
Tentukan jumlah kelompok yang akan dibentuk.
-
Tentukan posisi setiap pusat kelompok. Tidak ada aturan pasti untuk menentukan posisi awal pusat kelompok. Cara yang biasa digunakan adalah secara random atau dengan memilih beberapa data sebagai pusat kelompok.
-
Periksa jarak setiap data ke setiap pusat kelompok. Data tersebut akan dimasukkan ke dalam kelompok yang terdekat dengannya.
-
Hitung kembali posisi setiap pusat kelompok dengan cara menambahkan jarak tiap data ke pusat kelompok, kemudian dibagi dengan banyaknya data kelompok tersebut.
-
Periksa kembali setiap data untuk menentukan keanggotaan data dengan menggunakan pusat kelompok yang baru. Bila ternyata terjadi perubahan, maka pusat setiap kelompok harus
37
dihitung kembali. Proses ini dilakukan terus menerus hingga tidak ada perubahan lagi pada keanggotaan data. Metode ini merupakan salah satu metode yang paling mudah diimplementasikan. Namun bila metode ini dilakukan berulang kali untuk himpunan data yang sama, hasilnya belum tentu sama. Hasil metode ini akan sangat tergantung pada penempatan pertama posisi pusat kelompok yang biasanya dilakukan secara random.
Jika diberikan sekumpulan observasi (x1, x2, …, xn) dimana tiap observasi merupakan sebuah vektor bilangan real pada sebuah ruang D dimensi, kemudian k-means clustering membagi sekumpulan observasi tersebut dinyatakan sebagai (k < n) S={S1,S2,…,Sk}.
Proses k-means clustering:
Gambar 2.20. k-means clustering
38
1. Dari sekumpulan data yang kita miliki ditentukan berapa jumlah cluster yang mau dibentuk, misalnya k = 5.
Gambar 2.21. tampilan data pada k-means clustering
2. Lalu ditentukan 5 titik pusat bagi masing-masing cluster secara random.
Gambar 2.22. tampilan hasil titik pusat yang telah dilakukan secara rando
39
3. Lalu semua titik dibandingkan jaraknya dengan kelima titik pusat tersebut, titik pusat yang terdekat menjadi cluster bagi masingmasing titik tersebut.
Gambar 2.23. tampilan titik pusat yang telah dibentuk pada masing-masing cluster
4. Dari masing-masing cluster yang terbentuk tersebut dibentuk lagi titik pusatnya masing-masing.
Gambar 2.24. tampilan titik pusat pada masing-masing cluster yang telah dibentuk kembali
40
5. Kemudian langkah 3 sampai seterusnya diulang sampai terjadi konvergensi. 2.5.4. Metode LSI lebih lanjut Dimisalkan A adalah sebuah matriks berukuran m kali n dimana tiap baris m adalah sebuah fitur yang diekstrak dari gambar dan tiap kolom n adalah sebuah gambar.
A=
G1
G2
G…
…
Gn
…
…
…
…
…
F1
…
…
…
…
…
F2
…
…
…
…
…
F…
…
…
…
…
…
…
…
…
…
…
…
Fm
Jadi sebuah kolom adalah sebuah feature vector dari sebuah gambar. Lalu dari sebuah matriks tersebut dipecah menjadi A = USVT. Misal, ada 3 buah gambar yang memiliki kesamaan dan mau dibentuk kelas/kategori sendiri, masing-masing gambar diambil 11 fitur:
41
A=
1
1
1
0
1
1
1
0
0
0
1
0
1
0
0
1
0
1
1
1
1
1
1
1
1
0
1
0
2
0
0
1
1
Sehingga setelah dilakukan proses dekomposisi diperolehlah matriks-matriks sebagai berikut:
42
-0.4201 0.0748 -0.0460 -0.2995 -0.2001 0.4078 -0.1206 0.2749 -0.4538 -0.1576 -0.3046 -0.2006 -0.1206 0.2749 -0.4538 U=
4.0989
0.0000
0.0000
0.1547
S = 0.0000
2.3616
0.0000
-0.4201 0.0748 -0.0460
0.0000
0.0000
1.2737
-0.2626 0.3794
-0.4201 0.0748 -0.0460 -0.2626 0.3794
0.1547
-0.3151 -0.6093 -0.4013 -0.2995 -0.2001 0.4078
-0.4945 0.6492 -0.5780 V=
-0.6458 -0.7194 -0.2556 -0.5817 0.2469
0.7750
-0.4945 -0.6458 -0.5817 VT =
0.6492 -0.7194 0.2469 -0.5780 -0.2556 0.7750
Lalu selanjutnya dimensi bagi setiap feature vector direduksi menjadi 2 dimensi, sehingga kita ambil Rank 2 Approximation (k = 2) seperti terlihat pada gambar berikut:
43
-0.4201 0.0748
k=2
-0.2995 -0.2001
-0.1206 0.2749
-0.1576 -0.3046
-0.1206 0.2749 U ≈ Uk =
-0.2626 0.3794
-0.4201 0.0748
S ≈ Sk =
4.0989
0.0000
0.0000
2.3616
-0.4201 0.0748
-0.2626 0.3794
-0.3151 -0.6093
-0.2995 -0.2001
-0.4945 0.6492 V ≈ Vk = -0.6458 -0.7194
VT ≈ VTk = -0.4945 -0.6458 -0.5817
-0.5817 0.2469
0.6492 -0.7194 0.2469
44
Jadi, “koordinat” bagi tiap gambar bisa didapat dari matriks V, yaitu: •
G1 = (-0.4945, 0.6492)
•
G2 = (-0.6458, -0.7194)
•
G3 = (-0.5817, 0.2469)
Langkah pertama adalah merepresentasikan teks sebagai matriks yang setiap barisnya mewakili kata yang unik dan setiap kolom mewakili kalimat. Setiap sel berisikan frekuensi kemunculan kata di setiap kolom. Selanjutnya, isi dari sel merupakan transformasi preliminary yang detilnya akan dideskripsikan kemudian, yang masing–masing frekuensi sel diberi bobot oleh sebuah fungsi yang menghasilkan keutamaan kata dalam sebuah kalimat.
Selanjutnya, metode ini mengaplikasikan SVD (Singular Value Decomposition) ke dalam matriks. Dalam SVD, matriks persegi didekomposisi
menjadi
tiga
matriks
lainnya.
Matriks
pertama
mendeskripsikan baris asli sebagai vector turunan nilai factor orthogonal. Satu matriks lagi mendeskripsikan kolom seperti sebelumnya. Matriks ketiga adalah matriks diagonal yang memuat nilai skala jika ketiga komponen matriks dikalikan.
Dari matriks-matriks yang telah dibuat, akan ditemukan kata yang berhubungan dengan kata kunci yang dicari. Kemudian, dari katakata tersebut, dicarilah halaman-halaman web yang sesuai dari daftar alamat web yang terdapat pada basis data. 45
2.6.
Supervised Learning
Supervised learning adalah teknik pembelajaran mesin dengan membuat suatu fungsi dari data latihan. Data latihan terdiri dari pasangan nilai input (biasanya dalam bentuk vektor), dan output yang diharapkan untuk input yang bersangkutan. Tugas dari mesin supervised learning adalah memprediksi nilai fungsi untuk semua nilai input yang mungkin, setelah mengalami sejumlah data latihan.
Untuk mencapai tujuan ini, mesin harus dapat melakukan proses generalisasi dari data latihan yang diberikan, untuk memprediksikan nilai output dari input yang belum pernah diberikan sebelumnya dengan dara yang masuk akal.
46
