9
BAB 2 LANDASAN TEORI
2.1 2.1.1
Tabu search Latar Belakang Tabu search Tabu search merupakan suatu pendekatan meta-heuristik yang mendasari prosedur pencarian heuristic lokal yang digunakan untuk mencari kemungkinan ditemukannya solusi lain di luar tingkat optimalitas lokal atau untuk mencari solusi yang optimal atau mendekati optimal. Tabu search secara dramatis telah mengubah kemampuan kita untuk menyelesaikan sains terapan, bisnis dan engineering. Metode untuk mencari solusi dengan Tabu search telah menjadi fokus yang dominan selama 3 dekade belakangan ini (dan masih menjadi fokus). Meta-heuristik sendiri berarti suatu master strategi yang mendasari dan memodifikasi heuristik lainnya untuk menghasilkan solusi / kesimpulan, selain dari yang biasanya diterapkan pada penelitian untuk mendapatkan tingkat optimalitas. (Glover dan Laguna , 1997, p17) Tabu search didasarkan pada kesimpulan bahwa penyelesaian masalah, untuk memenuhi kualitas sebagai metode yang mempunyai kecerdasan, harus menggabungkan adaptive memory dan responsive exploration. Kemampuan adaptive memory pada Tabu search memungkinkan untuk mengimplementasikan prosedur yang mampu untuk mencari lingkup solusi secara efisien dan ekonomis.
10 Pentingnya penggunaan responsive exploration pada Tabu search, baik yang di-implementasikan secara determinan atau probabilitas, diperoleh dari pengandaian bahwa pemilihan strategi yang buruk dapat menghasilkan lebih banyak informasi daripada sebuah pilihan baik yang diperoleh secara acak. Dalam sistem yang menggunakan memori, sebuah pilihan buruk yang diambil berdasarkan strategi dapat menyediakan kesimpulan yang berguna tentang bagaimana strategi dapat diubah untuk menjadi lebih baik. Responsive exploration menggabungkan prinsip dasar dari pencarian cerdas seperti selalu berusaha mencari solusi terbaik selama mencari semua kemungkinan yang ada. Tabu search selalu berusaha mencari cara yang baru dan lebih efisien dalam mengambil keuntungan dari penggabungan mekanisme adaptive memory dan mekanisme responsive exploration. 2.1.2
Kegunaan Memori Struktur memori dalam Tabu search bekerja dengan merajuk pada empat prinsip dasar, yang terdiri dari recently, frequency, quality, dan influence. Recency-based dan frequency-based saling melengkapi satu sama lain dan mempunyai karakteristik penting. Quality merujuk pada kemampuan untuk membedakan kualitas dari solusi yang ditemui selama proses pencarian. Dalam konteks ini memori dapat digunakan untuk mengidentifikasikan elemen yang umum untuk mencari solusi terbaik atau jalur yang menuju solusi yang baik. Dalam kerjanya, quality menjadi dasar dari pembelajaran incentive-based di mana dorongan diberikan untuk menguatkan aksi yang dapat mencari solusi yang baik. Dan penalti diberikan untuk melemahkan aksi yang dapat menyebabkan solusi yang tidak baik.
11 Dan yang keempat, influence, didasarkan pada akibat dari pemilihan yang dibuat selama proses pencarian, tidak hanya pada kualitas tetapi juga pada strukturnya.
sumber : Tabu search
Gambar 2.1 Empat Prinsip Dasar Memory Dalam Tabu search
Penggunaan memori pada Tabu search adalah secara ekplisit dan atribut. Eksplisit memori menyimpan solusi secara lengkap, termasuk solusi yang baik yang diketahui selama proses. Sedangkan attribut memori digunakan untuk mengarahkan tujuan. Tipe memori ini menyimpan informasi tentang atribut dari solusi yang berubah selama pergerakan dari satu solusi ke solusi yang lain. Sebagai contoh, dalam graph atau jaringan, atribut dapat berupa kumpulan node yang ditambah, dikurangi, atau dipindahkan selama mekanisme pergerakan. 2.1.3
Intensifikasi dan Diversifikasi Dua komponen yang sangat penting dalam Tabu search adalah strategi intensifikasi dan strategi diversifikasi.
12 1. Strategi Intensifikasi Strategi ini berdasarkan pada modifikasi aturan pemilihan untuk mendorong atau menguatkan kombinasi pergerakan dan solusi yang mempunyai histori yang baik. Strategi ini juga dapat memberikan suatu nilai kepada daerah yang potensial untuk diproses lebih mendalam. Strategi ini mencari “neighbors” dengan menggabungkan semua komponen dari solusi yang baik atau dengan menggunakan evaluasi dari strategi yang telah dimodifikasi menjadi sebuah solusi yang dapat berkembang. 2. Strategi Diversifikasi Strategi ini didasarkan atas suatu proses pencarian yang digunakan untuk menguji daerah yang tidak pernah dikunjungi / dibahas sebelumnya untuk menghasilkan suatu solusi yang berbeda dari alternatif-alternatif solusi yang pernah ada. Atau dapat juga dikatakan bahwa pengukuran diversifikasi berhubungan
dengan
banyaknya
perpindahan
yang
dibutuhkan
untuk
memindahkan satu solusi ke solusi yang lain. Strategi ini mendorong proses pencarian untuk mencoba daerah yang belum pernah dikunjungi dan untuk menghasilkan solusi yang berbeda dalam banyak hal dengan solusi yang pernah diketahui sebelumnya. 2.1.4
Prinsip Tabu search dan Memori Jangka Pendek Tabu search dapat diaplikasikan langsung ke statement verbal maupun simbolik dari berbagai macam masalah pengambilan keputusan tanpa perlu untuk mengubahnya menjadi bentuk rumus matematisnya. Meskipun begitu, ada gunanya juga untuk menggunakan notasi matematika untuk menggambarkan lingkup yang lebih besar dari masalah sebagai dasar untuk menjelaskan beberapa
13 hal di dalam Tabu search. Tabu search mengkarakteristikkan bagian dari masalah dengan tujuan mengoptimalkan (minimum atau maksimum) dari fungsi
f (x) dengan x ∈ X, di mana f (x) dapat berupa linear maupun non-linear dan X ringkasan yang mengandung nilai keputusan variabel x. Tabu search mulai dengan cara yang sama seperti ordinary local atau neighborhood search, memulai proses iterasi dari satu titik (solusi) ke solusi lain sampai kriteria/ syarat iterasi berhenti tercapai. Setiap x ∈ X berasosiasi dengan neigborhood N(x)⊂X dan setiap solusi x'∈ N(x) diperoleh dari x dari operasi yang dinamakan move. Sebagai langkah awal, Tabu search dapat dilakukan dengan metode descent yang sederhana di mana tujuannya adalah untuk meminimumkan f (x) (atau sebaliknya metode ascent yang goalnya adalah memaksimalkan f (x) ). Metode seperti ini hanya mengijinkan move menuju solusi neighbor yang membuat hasil/goal lebih minimum/ lebih baik dan berhenti jika tidak dapat ditemukan solusi yang lebih baik. Hasil x akhir yang diperoleh dari metode descent dinamakan local optimum , karena hasilnya itu setidaknya lebih baik dari sebagian maupun seluruh solusinya yang terdapat dalam neighborhood. Akibat dari cara singkat yang diperoleh dari metode descent adalah sebuah lokal optimum yang dalam banyak kasus bukan merupakan optimum dari keseluruhannya, artinya biasanya hasil yang diperoleh bukan merupakan f (x) minimum dari semua x ∈ X .
14 Pseudocode dari metode descent adalah seperti berikut 1. Pilih x ∈ X untuk memulai proses. 2. Cari x'∈ N(x) di mana f ( x' ) < f ( x) . 3. Jika tidak ada x’ lagi yang dapat ditemukan maka x adalah local optimum dan metode berhenti. 4. Selain itu, set x’ menjadi x yang baru dan kembali ke langkah ke 2 Versi lain dari metode descent adalah steepest descent yang mencari seluruh neighborhood dari x dalam proses pencarian dari neighbor solusi x’ yang memberikan nilai fungsi f (x' ) dari seluruh x'∈ N(x). Tetapi steepest descent kadang-kadang tidak bisa diterapkan karena secara komputasi proses tersebut terlalu berat, di mana N(x) mengandung banyak element atau setiap element terlalu berat/memakan resource ketika ingin dikirim atau dievaluasi. Tetapi kadang masih cukup bernilai untuk memilih x’ untuk setiap iterasi di mana masih “baik” meskipun bukan nilai f (x' ) terbaik/terkecil. 2.1.5 Memori dan Klasifikasi Tabu Salah satu pembedaan yang penting di dalam Tabu search adalah pembedaan antara short-term memory dengan long-term memory. Setiap tipe memori ini memiliki kelebihan masing-masing dalam hal strateginya. Bagaimanapun juga, efek dari kedua memori ini adalah modifikasi terhadap neigborhood N(x) dari solusi x yang sedang diproses. Neighborhood yang telah dimodifikasi, yang dinotasikan sebagai N*(x), adalah hasil dari pemilihan history dari state yang timbul selama pencarian.
15 Dalam strategi Tabu search yang menggunakan short-term memory N*(x) secara karakteristik adalah bagian dari N(x), dan klasifikasi tabu dilakukan untuk mencari elemen dari N(x) yang tidak terdapat dalam N*(x). Dalam strategi Tabu search yang menggunakan longer-term memory, N*(x) dapat dikembangkan dengan memasukkan solusi yang tidak umum yang tidak terdapat dalam N(x). Secara karakteristik, dalam Tabu search cara ini dapat dipandang sebagai dynamic neighborhood method, yang artinya adalah neighborhood dari x bukan suatu kumpulan yang tetap, melainkan sebuah kumpulan yang jumlahnya dapat berubah tergantung dari history selama proses. 2.1.6 Recency-based Memory Recency-based memory menyimpan arah/jalur dari setiap solusi yang berubah selama proses. Untuk memperlihatkan penggunaan memori, setiap attribut yang muncul dalam solusi yang baru saja dikunjungi diberi label tabuactive dan pemilihan solusi yang mengandung elemen tabu-active atau kombinasi dari attributnya, solusi tersebut menjadi tabu. Hal ini mencegah solusi tertentu yang telah ada sebelumnya menjadi N*(x) dan mencegah agar tidak dikunjungi berkali-kali. 2.1.7 Komponen-komponen Tabu search •
Solusi Awal : Objek pattern P diletakkan pada posisi paling pojok bidang
(sekitar daerah koordinat 0,0) •
Move : Menggerakkan pattern melalui jalur-jalur yang ditentukan oleh
kriteria-kriteria tertentu. Untuk setiap move dapat dilakukan beberapa proses yang diperlukan seperti mengupdate boundary dari bidang, pengecekan jika terjadi tabrakan dan lain-lain yang diperlukan.
16 •
Basic Neighborhood N(π) : Neighborhood dari π terdiri dari solusi-solusi
yang diperoleh melalui suatu gerakan (move) dari solusi saat ini π. •
Tabu List : Tabu list didefinisikan sebagai set T = { T1, T2, …, Ts}. Tj adalah
elemen ke-j dari T yang berisi nilai objektif yang berkaitan. Apabila s bervariasi dengan cara yang asiklis, maka looping akan dapat dihindari. •
Tabu tenure : Tabu tenure s di-set secara dinamis.
•
Stopping rules : aturan/syarat untuk stop perhitungan, bisa dipilih dengan
infinite artinya proses mencoba segala yang mungkin, atau bisa dengan kriteria bila solusi yang diperoleh tidak mengalami peningkatan setelah mengalami iterasi berulang sebanyak tf. Atau bisa dengan aturan-aturan yang lain yang lain 2.1.8 Algoritma Tabu search •
Langkah 1 : t ← 1 sebagai nomor iterasi. s ← ∼ sebagai nilai tabu tenure.
Set tabu list awal Tj = 0; j = 1,2,…,s. tn ← 0. •
Langkah 2 : Set π sebagai solusi awal. π* ← π dan πbest ← π.
•
Langkah 3 : lakukan langkah-langkah untuk mendapatkan Candidate list
CL(π*). Tentukan Z(πl) = min { Z (πi); πi ∈ CL(π*)}. •
Langkah 4 : Jika Z(πl) < Z(πbest) maka πbest ← πl dan tn ← 0.
•
Langkah 5 : Masukkan ke tabu list ke kanan dan set T1 ← Z(πl) dan Tj ← Tj1,
j= 2,..., s.
•
Langkah 6 : Bila Z(πl) ≥ Z(π*), maka Ts+1 ← 0. π* ← πl
•
Langkah 7 : Bila t = tf, πbest diambil sebagai solusi suboptimal dan stop
perhitungan.
17 •
Langkah 8 : t ← t + 1
•
Langkah 9 : Bila semua move telah dicoba maka stop perhitungan jika tidak
kembali ke langkah 3
2.2
Computer Graphics
Menurut Xiang (2001, p1), computer graphics (CG) mempelajari tentang dasar- dasar penerapan ilmu penggambaran dalam sebuah komputer. Image Processing adalah salah satu bagian dari computer graphics yang berusaha untuk memanipulasi suatu gambar, atau bentuk hasil dari computer graphics untuk menghasilkan suatu gambar yang diinginkan oleh pemakai, gambar yang dihasilkan dapat bersifat realistis, abstrak, maupun virtual (Xiang, 2001, p4). 2.2.1 Bentuk Dasar a. Titik Piksel Piksel merupakan satuan pemetaan terkecil yang kita lihat dalam suatu layar monitor dan setiap titik dalam CG dapat diwakili oleh satu atau lebih piksel yang digambarkan ke bidang layar monitor (Xiang, 2001, p6). Jadi dalam keadaan ideal satu titik adalah satu piksel pada layar. b. Garis Garis merupakan kumpulan titik yang berurutan atau acak (tergantung dari resolusi layar yang digunakan), sehingga terlihat gambar sebuah garis pada layar (Xiang, 2001, p26).
18 c. Poligon Poligon merupakan kumpulan dari garis yang berurutan membentuk suatu bentuk tertutup. Bentuk poligon yang paling mudah adalah segitiga, lalu berkembang menjadi segiempat dan seterusnya. 2.2.2 Resolusi a. Resolusi Layar Monitor Resolusi layar monitor yang berbeda-beda memiliki arti tertentu dan mempengaruhi tampilan gambar yang dihasilkan dengan resolusi yang berbeda dengan resolusi layar monitor (Xiang, 2001, p9). Untuk resolusi 800 x 600 piksel, artinya satu piksel pada lebar layar adalah lebar layar monitor dibagi 800, sedangkan satu piksel pada tinggi layar adalah tinggi layar monitor dibagi 600. Demikian seterusnya untuk resolusi layar monitor yang lainnya. Jadi bentuk atau ukuran gambar yang ditampilkan pada resolusi yang berbeda-beda akan berbedabeda juga. b. Resolusi Gambar Semakin besar resolusi suatu gambar maka semakin tinggi kerapatan tiap piksel dan biasanya semakin bagus juga gambar yang dihasilkan (Xiang, 2001, p9-10)Tapi dengan resolusi yang sangat tinggi suatu gambar akan diharuskan menyimpan banyak juga warna atau atribut lainnya dalam gambar tersebut sehingga semakin besar pula ukuran dari gambar tersebut. Walupun resolusi layar berbeda-beda tetapi ukuran gambarnya tidak akan berubah, hanya ukuran tampilannya saja yang berubah sesuai dengan resolusi monitor.
19 c. Resolusi Printer & Scanner Printer dan scanner sebagai salah satu alat keluaran dan masukan yang berfungsi untuk mencetak dan merekam gambar dari dan ke dalam computer melalui medium lain (kertas, plastik, dll) juga memiliki satuan resolusi sendiri untuk memetakan piksel pada CG ke dalam medium atau komputer. Perbedaan resolusi atau kesalahan proses mapping akan mengakibatkan pergeseran kualitas gambar yang akan dicetak atau direkam (Xiang, 2001, p11). 2.2.3 Teknik Manipulasi Image Processing Berikut ini adalah sebagian teknik yang dapat digunakan untuk memanipulasi suatu citra/gambar dalam image processing, yaitu (Erhardt, 2000) : a. Lighting & Ray Tracing Proses Lightning adalah proses yang memberikan efek pencahayaan pada gambar, jadi proses ini hanya mengubah besarnya pencahayaan pada suatu citra/gambar (Xiang, 2001, p230). Proses ray-tracing dapat memanipulasi gambar berdasarkan arah cahaya jadi kita dapat mengendalikan dari mana cahaya berasal dan bagaimana akibatnya pada suatu gambar atau bentuk objek dalam gambar itu (Xiang, 2001, p251). b. Blur Memberikan efek pemudaran penglihatan, atau membuat gambar nampak lebih buram dari gambar aslinya, dengan pemakaian efek yang baik akan memberikan hasil efek fokus pada mata manusia.
20 c. Shadow Memberikan efek bayangan pada suatu gambar. Dengan teknik ray-tracing akan dapat menghasilkan bayangan yang bagus pada gambar atau objek di dalam gambar. d. Negative Menciptakan bentuk negatif atau sebuah klise foto, yaitu semua warna yang dominan dan kurang dominan akan dipetakan dalam bentuk hitam, abu-abu dan putih. e. Noise Pada proses ini pemetaan yang dilakukan adalah memasukkan piksel acak ke dalam suatu image dalam bentuk berbagai warna yang terlihat memberikan efek acak ke dalam gambar. f. Halftoning & Dithering (Black & White) Proses halftoning melakukan manipulasi jumlah piksel yang akan mewakili suatu piksel untuk memberikan kesan pewarnaan hitam, abu-abu sampai putih dengan hanya menggunakan dua warna saja yaitu hitam dan putih dengan tujuan untuk lebih merepresentasikan sejumlah atau satu piksel menjadi satu titik pada umumnya alat keluaran (printer dsb) (Xiang, 2001, pll-12). Proses Image Dithering sekarang tidak hanya berlaku pada bentuk hitam putih saja tapi juga sampai pada pewarnaan (Xiang, 2001, pI2-13). Proses ini mengkalkulasi kerja printer agar dapat mencetak warna yang ada agar tidak berubah atau hilang (halftoning) sehingga memberikan hasil yang bagus.
21 2.2.4 Manajemen Warna Warna yang kita lihat pada monitor/TV dihasilkan dengan bantuan kartu grafis Untuk dapat membedakan warna-warna yang berbeda. Sistem yang berfungsi untuk merepresentasikan warna-warna tersebut kita sebut dengan Color Management (System Manajemen Warna). Terdapat beberapa model sistem manajemen warna, antara lain adalah RGB dan CMYK. Model RGB digunakan kebanyakan sebagai representasi warna sepenuhnya hasil dari pemetaan sinar merah, hijau dan biru pada monitor. Sedangkan CMYK menghasilkan warna yang selayaknya akan dicetak pada alat keluaran dan menampilkan warna tersebut pada monitor berbasiskan RGB. Selain ke dua model sistem manajemen warna di atas, ada hal yang mempengaruhi kondisi warna baik yang dihasilkan pada sistem RGB maupun system CMYK yaitu intensitas putih (terang) dan hitam (gelap) dari warna tersebut, sehingga lahir model HSL. Jadi dapat dikatakan ke tiga jenis sistem manajemen warna ini akan menghasilkan warna yang sama pada perwakilan nilai intensitas yang berbeda. 2.2.5 Warna RGB(Red, Green & Blue), CMYK (Cyan, Magenta, Yellow, Black), dan HSL (Hue, Saturation, Luminosity) Menurut teori Tristimulus Warna, disebutkan bahwa retina manusia mempunyai tiga jenis sensor warna (cores) dengan sensitivitas puncak (peak) pada cahaya merah, hijau dan biru. (Rogers, 1985, p385) Konsep dasar RGB adalah warna putih dari cahaya (Boumphrey, 2000-2003). Warna putih dari cahaya dikatakan berasal dari kombinasi warna pelangi, dan
22 warna merah, hijau serta biru dapat dicampur menjadi berbagai warna tersebut sesuai dengan besarnya intensitas warna tersebut. RGB adalah salah satu representasi warna pada monitor. Karena pada dasarnya tabung katoda pada monitor menggunakan representasi warna dasar cahaya (Red), Hijau (Green) dan Biru (Blue) atau biasa dikenal dengan RGB screen. RGB dikenal juga dengan sistem pewarnaan additif, yaitu warna dihasilkan dengan menggabungkan intensitas warna dasar. Sebagai contoh yang ekstrim: warna hitam pada monitor dihasilkan oleh pencampuran intensitas minimum semua warna dan warna putih adalah pencampuran maksimum intensitas seluruh warna dasar RGB. Tapi pada kenyataannya kebanyakan alat keluaran selain monitor menggunakan pilihan warna yang lebih substraktif yaitu dengan model system pewarnaan CMYK. Warna-warna pada CMYK pada dasarnya adalah warna substraksi kebalikan dari sistem warna RGB. [C, M, Y] = 1 - [R, G, B] Sebagai contoh ekstrim: warna hitam yang akan ditampilkan ke dalam kertas dengan printer adalah campuran maksimum dari cyan, magenta dan yellow, sedangkan warna putih pada kertas adalah pengurangan ke tiga campuran warna tersebut, atau dengan tidak mencetaknya sama sekali (pada kertas berwarna putih).
23
sumber : www.techcolor.com
Gambar 2.2 Warna dalam RGB dan CMY HSL (Hue, Saturation, Luminosity) model ini ada berdasar jumlah efek abuabu/ grey (shadyness) yang dihasilkan kombinasi warna RGB maupun CMYK. HSL memiliki intensitas nilai dari 0-240 di mana nilai 240 adalah nilai di mana sekali tidak ada unsur abu-abu dalam warna (warna tersaturasi penuh).
sumber : www.hypermedic.com
Gambar 2.3 HSL Color Wheel 2.2.6 Manajemen Warna RGB Manajemen warna RGB dibuat dengan klasifikasi besar intensitas warna nyata (true color) yang disimbolkan dengan nilai 0-255 atau 8 bit untuk tiap warna dasar, jadi untuk true color ada 24 bit warna yang dapat digunakan. Dalam pengembangan dasarnya hanya diperlukan sekitar 200 level warna untuk dapat menghasilkan gradasi warna saja untuk dapat dibedakan oleh mata
24 manusia, dibuat 256 level warna disebabkan oleh 2 (dua) hal (Fraser et al., 2003, p61): Headroom (ruang lebih warna), ini digunakan untuk menanggulangi warna yang hilang/berubah akibat berbagai proses yang dilalui oleh suatu warna (setelah dicetak, scan, dll). Bits, representasi dengan bit sangat tanggung bila untuk 200 level saja, di mana 7 bit atau 27 mengasilkan 128 level dan 8 bit atau 28 menghasilkan 256 level intensitas. Jadi dengan representasi 256 x 256 x 256 warna sistem RGB dapat menghasilkan 16,8 juta jenis warna. Tentu sangat banyak kombinasi dibandingkan dengan representasi warna yang diwakilkan kurang dari 24 bit atau true color. Dengan perkembangan teknologi hardware, sekarang graphic card sudah dapat memberikan efek warna 32 bit. Di mana 8 bit selebihnya diperuntukkan besarnya intensitas terang dari warna, dilambangkan dengan α. Dengan besar intensitas warna 8 bit atau 256 maka model warna RGB juga dapat direpresentasikan dalam heksa-desimal 2 digit, mulai dari level terkecil 00 sampai dengan yang tertinggi FF (255). Jadi semisal warna hitam, karena tidak ada campuran dari satupun sinar maka diwakilkan dengan heksa 000000, sebaliknya putih merupakan campuran dari ke tiga sinar maksimum diwakilkan dengan heksa FFFFFF. 2.2.7 Dokumen Bitmap (.bmp) Dokumen bitmap .bmp ini merupakan salah satu format gambar/citra. Pada suatu dokumen .bmp dapat tersimpan gambar mulai dari 1 bit warna (hitam/putih) hingga 24 bit warna (true color).
25 a. Struktur Dokumen Bitmap
Header identification as windows bitmap files
Header
40 bytes in length information of the bitmap type
Info header Optional palette
Optional palette use as replacement of undefine color in a non true color bitmap type
Image data
The image color, position mapping code for the bitmap sumber : http://astronomy.swin.edu.au
Gambar 2.4 Struktur Dokumen Bitmap
Menurut Bourke (1998), struktur format dokumen ini seperti terlihat pada gambar 2.6 memiliki 4 bagian: header, info header, optional palette dan image data. Bagian header bitmap berisikan 14 bytes data yang berisikan informasi yang menyatakan identifikasi sebagai suatu dokumen bitmap, besar atau ukuran data pada dokumen ini, beserta informasi awal pembacaan dokumen bitmap. Bagian info header sepanjang 40 bytes berisikan infonnasi tinggi dan lebar citra, jumlah bit/piksel, resolusi, besarnya dokumen, jenis kompresi (bila ada) serta definisi yang berhubungan dengan warna yang dipakai. Kompresi yang digunakan pada dokumen bitmap masih sangat sederhana, untuk bitmap berukuan kecil masih dapat memperlihatkan kompesi yang berarti, namun semakin besar ukuran dokumen, semakin lemah
26 juga hasil kompresi yang didapatkan. Tabel 2.4 memperlihatkan tipe kompresi bitmap. Tabel 2.1 Jenis kompresi pada dokumen bitmap Nilai Kompresi 0 1 2 3
Bagian
optional
Jenis Kompresi Tidak ada kompresi Kompresi 8 bit Kompresi 4 bit RGB dengan masking
palette
mencatat
warna-warna
yang
dipaksakan/penting untuk dipakai dalam bitmap yang kurang dari 24 bit (true color bitmap). Jadi bagian ini bisa ada ataupun tidak. Pada true color bitmap tidak ada optional palette. Bagian image data, berisikan data-data yang akan dikonversi sebagai warna tampilan gambar/citra yang akan terlihat di monitor. b. Keunggulan dan Kekurangan Dokumen Bitmap Menurut O'Reilly (1996), keunggulan dokumen bitmap adalah sangat mudah untuk dibuat, dapat mengambil data tiap piksel data dengan sistem koordinat, manipulasi tiap piksel dapat dengan mudah dilakukan sesuai dengan kapasitas warna dapat disimpan. Menurut O'Reilly (1996), kekurangan dokumen bitmap adalah besarnya ukuran dokumen bahkan dengan adanya teknik kompresi, untuk dokumen berukuran sangat besar kompresi tidak mampu untuk memperkecil lebih dari ukuran dokumen. Selain itu dokumen bitmap sulit untuk diubah skala
27 resolusinya, kadang-kadang akan mengakibatkan perubahan kepadatan warna dan sebagainya.
2.3
Transformasi Dua Dimensi.
Dasar dari semua sistem grafik komputer adalah kemampuan untuk mensimulasikan hasil dari manipulasi objek dalam ruang (Xiang, 2001, p68). Fungsi dari transformasi ini perlu jika ada beberapa objek, yang masing masing mempunyai koordinat sistem, perlu untuk diletakkan bersama-sama dalam suatu master koordinat sistem. Ada dua poin penting dalam mendeskripsikan transformasi objek. Pertama adalah objek tersebut ditransformasikan relatif terhadap koordinat sistem yang tetap. Notasi matematika dalam hal ini disebut transformasi geometri yang diaplikasikan pada tiap titik dari objek. Yang kedua adalah objek itu tetap tetapi koordinat sistemnya ditranformasi menjadi relatif terhadap objek itu. Hal ini dapat diperoleh dengan menggunakan tranformasi koordinat. Sebuah contoh untuk menggambarkan perbedaan keduanya adalah dengan melihat pergerakan sebuah mobil terhadap lingkungan sekitarnya. Kita dapat mensimulasikan kejadian tersebut dengan menggerakan mobil sementara lingkungannya tetap (transformasi geometri) Atau kita dapat membuat mobil itu diam dengan menggerakkan lingkungan sekitarnya (transformasi koordinat) Sebuah titik dapat direpresentasikan pada bidang dua dimensi melalui koordinatnya. Nilai dari koordinat ini dapat lebih spesifik sebagai elemen yang terdiri dari satu baris dan dua kolom matriks [x,y] atau dua baris dan satu kolom ⎡ x⎤ ⎢ y ⎥ . Suatu rangkaian dari titik dalam komputer sebagai suatu matriks angka. ⎣ ⎦
28 Posisi ini dapat dikontrol dengan memanipulasi matriks dari titik-titik tersebut. (Rogers, 1979, p24) 2.3.1 Sistem Koordinat Kartesian Dua Dimensi Gambar pada umumnya merupakan bentuk dari sistem 2 dimensi, oleh karena itu konsep dari matematika dapat diterapkan untuk mengolahnya. (Anil K. Jain,p11). Dalam bidang dua dimensi, kita dapat menunjuk satu titik dan menyebutnya sebagai origin. Melalui titik origin itu kita dapat membuat dua garis tegak lurus yang dinamakan sumbu. Sumbu ini biasanya diberi nama sumbu x dan sumbu y. Arah dari bidang tersebut dapat ditentukan dari posisi positif dari sumbu x dan sumbu y. Jika rotasi sebersar 90 derajat berlawanan arah jarum jam dari daerah positif x dan positif y, maka koordinat sistem tersebut dinamakan right-handed sebaliknya jika rotasi searah jarum jam maka koordinat sistem tersebut dinamakan left-handed. Garis garis yang tegak lurus terhadap sumbu x dan tegak lurus terhadap sumbu y membentuk grid bujursangkar dalam bidang dua dimensi. Setiap titik P dalam bidang ini terdapat pada perpotongan tepat satu garis tegak lurus sumbu x dan garis tegak lurus sumbu y. Pasangan angka ini (x,y) yang diasosiasikan dengan titik P dinamakan koordinat Kartesian dari P. Dengan cara ini setiap titik dalam bidang diwakilkan oleh sepasang koordinat. 2.3.2 Matriks Matriks adalah sebuah tabel yang terdiri dari kolom dan baris. Notasi dari aij digunakan untuk menunjuk posisi matriks yang berada pada perpotongan baris i dan kolom j.
29 Matriks 2 dimensi sering digunakan untuk merepresentasikan gambar dalam matriks.. Representasi matriks gambar diperoleh dengan merotasi 900 searah jarum jam matriks koordinat Kartesian 2 dimensi . n
X(m,n) =
n ⎡2 − 1 − 3⎤ ⎢4 0 5 ⎥⎥ ⎢ ⎢⎣1 2 3 ⎥⎦
⇒X =
m
m
⎡1 4 2 ⎤ ⎢ 2 0 − 1⎥ ⎢ ⎥ ⎣⎢3 5 − 3⎦⎥
Ukuran atau dimensi dari matriks dinotasikan dalam m × n dimana m merupakan jumlah baris dari matriks dan n merupakan jumlah kolom dari matriks. Matriks dapat digunakan untuk merepresentasikan transformasi geometri dalam grafik komputer. ⎡ a(1,1) a(1,2) ⎢ a(2,1) ... a(m, n) = ⎢ ⎢ ... ... ⎢ ⎣a(m,1) a(m,2)
... a(1, n) ⎤ ... ... ⎥⎥ ... ... ⎥ ⎥ ... a(m, n)⎦
Beberapa perhitungan dalam matriks: a. Perkalian skalar Matriks kA adalah suatu matriks yang diperoleh dari mengkalikan seluruh elemen dalam matriks A dengan nilai K. b. Penambahan matriks Dua buah matriks A dan B dengan besar m × n dapat ditambahkan sehingga membentuk sebuah matriks C dengan besar m × n yang baru dengan cara menjumlahkan seluruh elemen dari matriks A dan B yang mempunyai i, j yang sama.
30 cij = aij + bij c. Perkalian matriks Sebuah matriks A dengan besar m × p dapat dikalikan dengan matriks B dengan besar p × n untuk membentuk sebuah matriks C dengan besar m × n. Elemen cij diperoleh dengan melakukan perkalian dot product dari baris i matriks A dengan kolom j dari matriks B. Perkalian matriks tidak bersifat komutatif, jadi AB ≠ BA.
cij = (baris i) . (kolom j) = ai1 + b1j + ai2 + b2j + .... + aim + bmj 2.3.3 Boundary Boundary adalah jalur-jalur/edges yang saling berhubungan yang membentuk karakteristik dari suatu objek. Boundary merupakan serangkaian pixel yang membentuk tepian dari suatu objek, tetapi bukan bagian dari kontur object itu sendiri. Boundary sangat berguna dalam perhitungan geometry seperti menghitung luas maupun arahnya. Secara konsep, boundary dapat dibentuk dengan mengikuti jalur-jalur yang saling berhubungan. Representasi dari boundary yang tepat sangat penting dalam menganalisis maupun membentuk pola. Analisis bentuk biasanya dibutuhkan untuk deteksi dan pengenalan dari objek pada suatu hal/ tugas. Pembentukan objek sangat berguna dalam computer-aided design (CAD), simulasi gambar seperti video games, film kartun, modelling lingkungan dari landasan pesawat terbang dan pelatihannya, dan masalah-masalah dalam komputer grafik lainnya.
31 2.3.4 Tranformasi Geometri Jika ada sebuah bidang dengan sistem koordinat. Sebuah objek Obj yang merupakan kumpulan dari titik-titik yang dipetakan ke bidang. Setiap titik mempunyai koordinat (x,y) , sehingga objek Obj merupakan jumlah dari semua titik-titik tersebut. Jika sebuah objek digerakkan ke posisi yang baru, maka dapat disebut sebagai objek Obj’, yang mana semua titik koordinatnya P’ diperoleh dari titik koordinat asalnya yaitu P dengan menggunakan perhitungan transformasi geometri (Xiang,2001, p69) a. Translasi Dalam translasi, sebuah objek ingin dipindahkan terhadap suatu jarak dan arah tertentu dari posisi awalnya. Jika perpindahan tersebut diberikan dalam vektor v = txI + tyJ, objek baru pada titik P’(x’,y’) dapat dihitung dengan menggunakan rumus transformasi Tv pada titik P(x,y) P’ = Tv(P) Dimana x’ = x + tx dan y’ = y + ty b. Rotasi Terhadap Titik Pusat Dalam rotasi, sebuah objek dirotasikan sebesar θ terhadap titik pusat. Yang perlu diperhatikan adalah arah rotasi berlawanan arah jarum jam jika θ bernilai positif dan searah jarum jam jika θ berlawanan arah jarum jam. Rumus dari rotasi Rθ adalah P’ = Rθ (P) Dimana x’ = x cos (θ) – y sin (θ) dan y’ = x sin (θ) + y cos (θ)
32 Kunci untuk mengerti bagaimana objek geometri dapat dideskripsikan dan dimanipulasi di dalam grafik sistem sebuah komputer adalah mengerti bagaimana cara bermain dalam geometri dan angka (Xiang, 2001, p271). Kita telah memiliki dasar dasar geometri seperti bagaimana mendeskripsikan sebuah garis, sudut, dan bentuk dan mendeskripsikan sifat dari objek tersebut seperti rotasi, translasi, distorsi, dan lain-lain, kita juga telah mengenal komputer yang mampu untuk mengolah angka secara cepat. Masalahnya adalah bagaimana mendeskripsikan ide-ide geometri kita ke dalam angkaangka sehingga komputer dapat mengerti dan mengerjakan tugas kita. 2.4
Bubble Sort
Bubble sort atau exchange sort adalah algoritma pengurutan yang sederhana. Proses pengurutannya adalah dengan membandingkan setiap objek dalam daftar dengan objek berikutnya dan menukarnya jika perlu. Proses ini dilakukan berulang-ulang sampai terjadi keadaan di mana proses melalui seluruh daftar tanpa perlu untuk melakukan perulangan sama sekali (yang berarti bahwa semua objek telah terurut). Hal ini seperti keadaan nilai yang lebih besar “bubble” ke bawah daftar sedangkan nilai yang lebih kecil naik ke atas daftar. Pseudocode dari algoritma bubble adalah : function bubblesort (A : list[1..n]) { var int i, j; for i from n downto 1 { for j from 1 to i-1 { if (A[j] > A[j+1]) swap(A[j], A[j+1]) } } }
33 Hal yang menguntungkan dari bubble sort adalah algoritma ini sederhana dan mudah untuk diimplementasikan sedangkan kerugiannya adalah algoritma ini tidak efisien. Keadaan ini menyebabkan algoritma ini cocok untuk mengurutkan daftar dengan objek yang sedikit (misal kurang dari seratus) karena mempunyai tingkat efisien yang hampir sama dengan algoritma yang lebih canggih dan rumit. Tapi untuk objek yang banyak maka algoritma ini tidak cocok untuk diimplementasikan karena akan berakibat lambatnya proses sorting.
sumber : MichaelLamont
Gambar 2.5 Grafik Efisiensi Bubble Sort 2.5
Microsoft C#.NET
C# adalah bahasa pemrograman yang baru yang diadaptasi dari bahasabahasa pemrograman sebelumnya untuk mengambil kelebihan-kelebihannya seperti C (performa yang tinggi), C++ (object-oriented structure), Java (garbage collector, high security) dan Visual Basic (pengembangan yang cepat) (Liberty, 2002, p1). Tujuan dari C# ini adalah untuk menyediakan bahasa pemrograman yang simpel, aman, modern, object-oriented, Internet-centric, performa tinggi dalam lingkungan pengembangan .NET.
