BAB II DASAR TEORI
2.1
Definisi Gambar Digital Gambar dapat direpresentasikan ke dalam dua macam bentuk yaitu bentuk
kontinu dan bentuk digital. Dengan menggunakan definisi gambar dalam representasikan digital yang akan melibatkan karakteristik gambar dalam pengolahan lebih lanjut. Dalam bentuk kontinu, gambar didefinisikan dalam suatu fungsi kontinu dari intensitas cahaya dalam bidang dua dimensi f ( x , y ) dimana x dan y menyatakan koordinat gambar dan nilai f pada koordinat ( x , y ) menunjukkan kecerahan atau informasi warna gambar yang secara otomatis dinyatakan sebagai berikut :
o < f ( x, y ) < 255 o < ( x, y ) < ~ Definisi digital dijelaskan bahwa gambar berupa array 2 dimensi dengan nilai f(x,y)-nya telah dikonversi ke dalam bentuk diskrit baik pada koordinat maupun kecerahannya. secara umum dapat didefinisikan sebagai pemrosesan sebuah gambar 2 dimensi oleh komputer, atau dapat juga diartikan pengolahan data 2 dimensi secara digital.
2.2
Definisi dan Hubungan Dasar pada Gambar Digital
2.2.1
Piksel
Piksel merupakan suatu unit terkecil pada gambar. Setiap piksel memiliki informasi warna yang membentuk suatu gambar. Informasi warna yang ditampilkan oleh
5
piksel tergantung pada jumlah bit yang menyusun piksel tersebut. Pada gambar biner, 1 piksel terdiri atas 1 bit dan dapat menampilkan maksimal 2 warna, Pada gambar dengan 256 warna 1 pikselnya terdiri atas 8 bit, jadi semakin besar bit yang dimiliki oleh piksel maka warna yang terkandung dalam piksel semakin beragam. 2.2.2
Tetangga Piksel
Sebuah piksel pada koordinat (x.y) memiliki 4 tetangga piksel yang bersinggungan langsung secara horizontal dan vertikal dengan titik - titik sebagai berikut: (x+1,y) , (x-1,y) , (x,y+1) , (x,y-1) disebut N4(p) dan 4 tetangga piksel yang bersinggungan secara diagonal yaitu : (x+1,y+1), (x-1,y-1), (x-1,y+1) , (x+1,y-1). sehingga sebuah piksel mempunyai piksel tetangga maksimum 8 buah. 2.2.3
Deteksi Sudut
Pengertian sudut adalah daerah yang dibentuk dari 2 buah pertemuan area yang berbeda di mana pada daerah yang bertemu tersebut mempunyai perbedaan intensitas yang tinggi dan minimal merupakan pertemuan 2 buah sisi. Ada beberapa metode deteksi sudut. Metode yang digunakan adalah metode Harris Stephen.
Gambar Awal
Gambar yang telah dideteksi sudutnya
Gambar 2.1 Gambar yang menunjukkan deteksi sudut
6
2.2.3.1 Deteksi Sudut dengan Metode Harris Stephen
Misalkan b(x,y) menyatakan brightness dari sebuah piksel. Deteksi sudut dengan Metode Harris Stephen menghitung turunan bx , by dengan menggunakan matriks n x n turunan pertama. Dengan menggunakan Gaussian G(x,y) dengan standar deviasi α algoritma lalu menghitung [ b2x] , [ b2y ] dan [bx b
y
]. Misalkan f(x,y) adalah sebuah
fungsi. Nilai dari { f(x,y) } adalah sebagai berikut :
{ b(x,y)} = b(x,y)* G(x,y)
G(x,y) =
1 2μa
exp ( −
x2 + y2 ) 2σ 2
Untuk setiap piksel ( x , y ) digunakan matriks sebagai berikut :
bxb y ⎤ ⎥ b y2 ⎥⎦
⎡ ( b 2x ) A=⎢ ⎢⎣ b x b y
Metode Harris Stephen menghitung respon sudut dengan rumus :
Chs = Det A – k Trace2 A
7
Di mana k ditetapkan 0.04 dan k Trace2 A
digunakan mendiskriminasikan fungsi
tangga yang terdapat pada sisi. Untuk menentukan apakah suatu piksel merupakan sudut atau bukan, digunakan threshold di mana jika threshold < Chs maka koordinat piksel tersebut merupakan sudut. 2.2.3.2 Syarat – syarat Deteksi Sudut
Deteksi Sudut adalah pencarian nilai – nilai piksel yang memiliki perbedaan yang signifikan dengan piksel tetangganya. Suatu deteksi sudut dianggap baik apabila memenuhi syarat – syarat berikut : a.
Hanya terdapat sedikit kesalahan sudut yang terdeteksi dan sudut yang tidak terdeteksi.
b.
Penempatan yang akurat. Penempatan sudut harus sedekat mungkin dengan lokasi sudut yang sebenarnya.
c.
Hanya bereaksi pada sebuah sudut. Tidak terjadi sudut terdeteksi ulang.
d.
Waktu yang dibutuhkan cepat. Algoritma harus cepat untuk dapat dilakukan proses selanjutnya.
e.
Stabil yaitu apabila gambar berubah letak karena ada translasi ataupu rotasi posisi sudut yang terdeteksi tetap sama.
2.3
Transformasi Geometri
Transformasi Geometri merupakan suatu fungsi yang memetakan piksel dari gambar asal menuju gambar tujuan. Misalkan (x,y) adalah koordinat gambar asal dan (x’,y’) merupakan koordinat gambar tujuan maka transformasi geometri memerlukan 2
8
buah fungsi pemetaan yaitu fungsi pemetaan maju dan fungsi pemetaan mundur, sebagai berikut: Fungsi pemetaan maju : x’ = x’ (x,y) dan y’ = y’(x,y) Fungsi pemetaan mundur : x = x (x,y) dan y = y (x,y)
2.3.1
Jenis Operasi Transformasi Geometri
2.3.1.1 Pergeseran / Translasi
Translasi matriks gambar P(x,y) dengan menggunakan Koordinat Kartesius yang menghasilkan P’(x’ , y’) melibatkan proses komputasi pengalamatan relatif dari kedua gambar yang bersangkutan. Translasi alamat tersebut berhubungan dengan : x’ = x + tx y’ = y + ty z’ = z = 1 ; karena sifat gambar yang dua dimensi Di mana tx dan ty merupakan konstanta offset translasi. Dalam bentuk matriks dapat dituliskan ⎡ x'⎤ ⎡1 0 tx ⎤ ⎡ x ⎤ ⎢ y '⎥ = ⎢0 1 ty ⎥ ⎢ y ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢⎣ z ' ⎥⎦ ⎢⎣0 0 1 ⎥⎦ ⎢⎣ 1 ⎥⎦
Maka P’ = T * P Di mana T menunjukkan translasi
9
Translasi Gambar 2.3 Transformasi Geometri ( Translation )
2.3.1.2 Penskalaan
Penskalaan spasial dapat diperoleh dengan melakukan modifikasi koordinat kartesian dari gambar input berdasarkan hubungan : x’ = sxx y’ = syy z’ = z = 1 ; karena sifat gambar yang dua dimensi Di mana sx dan sy merupakan nilai posisi konstanta penskalaan tapi tidak harus merupakan nilai integer. Dalam bentuk matriks, penskalaan dapat dituliskan sebagai berikut :
10
⎡ x'⎤ ⎡ sx 0 0⎤ ⎡ x ⎤ ⎢ y '⎥ = ⎢ 0 sy 0⎥ ⎢ y ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢⎣ z ' ⎥⎦ ⎢⎣ 0 0 1⎥⎦ ⎢⎣ 1 ⎥⎦
Maka P’ = S * P Di mana S menunjukkan matriks penskalaan.
x’
x y’
y
Skala Gambar 2.2 Transformasi Geometri ( Scaling )
2.3.1.3 Rotasi
Operasi rotasi pada sebuah gambar berdasarkan titik asal Koordinat Kartesius dapat dilakukan dengan komputasi pengalamatan sebagai berikut : x’ = x cos θ – y sin θ y’ = x sin θ + y cos θ z’ = z = 1 ; karena sifat gambar yang dua dimensi
11
Di mana θ merupakan sudut rotasi dengan arah berlawanan arah jarum jam berdasarkan sumbu horizontal dari gambar inputan. Dalam bentuk matriks rotasi dapat dituliskan sebagai berikut :
⎡ x'⎤ ⎡cos θ ⎢ y '⎥ = ⎢ sin θ ⎢ ⎥ ⎢ ⎢⎣ z ' ⎥⎦ ⎢⎣ 0
− sin θ cos θ 0
0⎤ ⎡ x ⎤ 0⎥⎥ ⎢⎢ y ⎥⎥ 1⎥⎦ ⎢⎣ 1 ⎥⎦
Maka P’ = R * P Di mana R menunjukkan matriks rotasi.
Rotasi Gambar 2.4 Transformasi Geometri ( Rotating )
2.3.1.4 Warping Gambar
Warping gambar pada dasarnya merupakan suatu transformasi yang mengubah konfigurasi spatial sebuah gambar. Setelah mempelajari jenis – jenis transformasi maka dapat ditentukan transformasi yang merupakan gabungan dari proses penskalaan, rotasi 12
dan pergeseran. Misalkan P = [ x y 1 ] menotasikan posisi yang berhubungan pada gambar yang di-warp. Maka dapat ditulis transformasi sederhana sebagai berikut : P’ = H * P H=T*S*R Di mana H menotasikan matriks transformasi. Misalkan transformasi yang dilakukan terlebih dahulu adalah rotasi dikuti oleh penskalaan dan pergeseran maka matriks H dapat diganti : P’ = T * S * R * P Persamaan diatas dapat dituliskan : ⎡ x'⎤ ⎡ Sx * cos θ ⎢ y '⎥ = ⎢ Sx * sin θ ⎢ ⎥ ⎢ ⎢⎣ z ' ⎥⎦ ⎢⎣ 0
2.3.2
− Sy * sin θ Sy * cos θ 0
tx ⎤ ⎡ x ⎤ ty ⎥⎥ ⎢⎢ y ⎥⎥ 1 ⎥⎦ ⎢⎣ 1 ⎥⎦
Jenis Transformasi Geometri
Ada 3 macam transformasi geometri yaitu : a.
Transformasi Rigid Transformasi yang hanya melibatkan operasi perpindahan dan rotasi.
b.
Transformasi Affine Transformasi yang melibatkan operasi perpindahan, rotasi dan penskalaan.
c.
Transformasi Perspektif Transformasi yang dibatasi oleh 4 buah titik sudut atau 4 buah garis. Merupakan transformasi yang bersifat umum. Matriks transformasinya adalah sebagai berikut :
13
⎡ x'⎤ ⎡ h11 ⎢ y '⎥ = ⎢h ⎢ ⎥ ⎢ 21 ⎢⎣ z ' ⎥⎦ ⎢⎣ h31
h12 h22 h32
h13 ⎤ ⎡ x ⎤ h2 3 ⎥⎥ x ⎢⎢ y ⎥⎥ h3 3⎥⎦ ⎢⎣ 1 ⎥⎦
Gambar 2.5 Jenis transformasi Rigid , Affine , Perspektif
2.4
Mosaic
2.4.1
Pengertian Mosaic
Mosaic adalah serangkaian tindakan terhadap kumpulan gambar yang overlapping dan menyediakan serangkaian transformasi untuk menggabungkannya ke dalam gambar. Tiga masalah utama dari Mosaic adalah : a.
Image alignment Menentukan transformasi yang mengatur lebih dari 1 buah gambar untuk digabungkan kedalam sebuah mosaic.
b.
Image cut and paste Image mosaicing melibatkan kombinasi gambar yang saling melengkapi daerahnya . proses cut and paste melibatkan daerah yang dipilih dalam mosaic.
c.
Image blending Teknik yang digunakan untuk mengatasi perbedaan intensitas antara gambar yang digabungkan.
14
2.4.2
Mosaic berdasarkan Sudut
Metode berdasarkan sudut ini berlaku jika gambar yang akan digabungkan mempunyai daerah yang saling berpotongan minimal sebesar 50%. Metode ini dibatasi hanya terjadi pada transformasi affine. 2.4.2.3 Metode Geometric Hashing
Untuk menetukan image alignment maka diperlukan M sudut pada gambar 1 dipasangkan dengan N sudut pada gambar 2. Transformasi 2 dimensi memerlukan K sudut ( K = 3 untuk transformasi affine ). Kita dapat membentuk K pasang sudut pada ⎛M ⎞ sebuah gambar sebanyak K! ⎜⎜ ⎟⎟ cara. Sehingga untuk pencarian pasangan sudut akan ⎝K⎠ ⎛ M ⎞⎛ N ⎞ memakan waktu sebanyak K! ⎜⎜ ⎟⎟⎜⎜ ⎟⎟ * waktu pencarian matriks transformasi. Hal ini ⎝ K ⎠⎝ K ⎠ akan memakan waktu yang lama. Untuk memperkecil perhitungan matriks transformasi , maka salah satu cara menggunakan Geometric Hashing. Adapun algoritmanya sebagai berikut : a.
Lakukan deteksi sudut pada gambar 1 sebanyak M dan sudut pada gambar 2 sebanyak N.
b.
Misalkan transformasi yang dilakukan adalah affine maka dibutuhkan 3 pasang sudut. untuk setiap 3 pasang sudut bentuk sebuah segitiga hitung 2 buah vector, sudut serta panjang l antar 2 buah sudut yang terdapat pada ujung segitiga dan ⎛M ⎞ simpan sebagai table hash. Sehingga didapatkan ⎜⎜ ⎟⎟ segitiga dengan parameter ⎝K⎠ θ dan l.
15
b
b’
lj
li
θi a
θj
c
c’
a’
Gambar 2.6 Geometri Hashing c.
⎛N⎞ Lakukan hal yang sama kepada gambar 2 sehingga didapatkan ⎜⎜ ⎟⎟ dengan ⎝K⎠ parameter θ dan l sebagai table pembanding.
d.
Hitung selisih sudut antar kedua table hash tersebut
∂i,j = | θMi – θNj |
Lakukan hal yang sama pada panjang l.
∂li,j = | lMi - lNj |
Dengan menggunakan threshold sudut ∆θ dan panjang ∆l maka dapat dikurangi pasangan segitiga yang tidak sesuai. Pasangan segitiga dengan selisih sudut dan selisih panjang yang bernilai lebih minimum dianggap pasangan yang bersesuaian.
16
Untuk mendapatkan matriks transformasi maka digunakan koordinat sudut. Misal L merupakan koordinat sudut pada gambar l dan R merupakan koordinat sudut pada gambar 2. untuk 3 pasang sudut maka dapat digunakan rumus :
⎛ xi' ⎞ ⎜ ⎟ Ri = ⎜ y i' ⎟ = HLi = ⎜ z' ⎟ ⎝ i⎠
⎡ h11 ⎢h ⎢ 21 ⎢⎣ h31
h12 h22 h32
h13 ⎤ ⎡ x ⎤ h23 ⎥⎥ ⎢⎢ y ⎥⎥ h33 ⎥⎦ ⎢⎣ 1 ⎥⎦
H = RL-1
2.4.2.4 Metode Random Adaptive
Misalkan I1 dan I2 adalah gambar yang diambil dari kamera yang sama. Awalnya dideteksi ciri – ciri geometri pada gambar yaitu sudut. Atru S1 = { L1,…,Ln} ( nl = |S1| ) dan S2 = { R1,…,Rn} ( n2 = |S2| ). Misalnya sudut yang dicari dengan menggunakan deteksi sudut degan metode Harris Stephen. Daerah yang sama pada I1 dan I2 didefinisikan oleh pasangan sudut ( titik sudut ) yaitu Li ↔ Ri dengan 4 buah titik sudut {Li}i dari S1 dengan 4 titik sudut lainya {Ri}i dari S2 . misalkan H adalah sebuah matriks transformasi dan Li dan Ri adalah sudut pada gambar I1 dan I2 adalah yang merupakan titik proyeksi. Maka dengan menggunakan koordinat 2 dimensi dari Li dan Ri didapatkan: ⎛ xi' ⎞ ⎜ ⎟ Ri = ⎜ y i' ⎟ = HLi = ⎜ z' ⎟ ⎝ i⎠
⎡ h11 h12 h13 ⎤ ⎡ x ⎤ ⎢h 21 h22 h 23⎥ ⎢ y ⎥ ⎢ ⎥⎢ ⎥ ⎢⎣ h31 h32 h33⎥⎦ ⎢⎣ 1 ⎥⎦
17
⎛x Dengan Li = ⎜⎜ i ⎝ zi
(
dan R = R1T
R2T
yi zi
⎞ ⎟⎟ dan Ri = ⎠
R3T
⎛ xi' ⎜ ' ⎜z ⎝ i
y i' z i'
⎞ ⎟ .misalkan L = LT1 ⎟ ⎠
(
LT2
LT3
LT4
)
)
R4T adalah matriks 3 x 4. maka didapatkan :
H = RLT(LLT)-1
Pemilihan sampel pada Random Adaptive menggunakan Random Uniform, hal ini disebabkan sudut yang terdeteksi pada gambar letaknya menyebar pada bidang gambar. sehingga setiap sudut memiliki kemungkinan untuk memiliki pasangan, oleh karena itu digunakan pemilihan secara uniform. Dengan menggunakan ciri – ciri geometri (sudut) maka didapat transformasi yang ⎛ n ⎞⎛ n ⎞ memungkinkan sebanyak 4! ⎜ 1 ⎟⎜ 2 ⎟ . misalkan n1 = n2 = 40 maka didapat 200 milliar ⎝ 4 ⎠⎝ 4 ⎠
transformasi yang memungkinkan. Untuk memperkecil peluang yang ada maka dilakukan dengan algoritma random adaptive. Adapun algoritmanya sebagai berikut : •
Ekstrasi ciri dari gambar (sudut).
•
Diberikan T kumpulan dari daerah yang sama dan cocokkan paling tidak pada pecahan dari kumpulan titik sudut.
•
Berikan nilai pada setiap daerah yang sama dan pilih salah satu dengan kualitas yang terbaik.
Setelah itu lakukan : •
Lakukan subpiksel analisis pada sudut.
18
•
Lakukan optimasi lokal dengan cara menghitung koefisien matriks pada daerah yang sama.
•
Lakukan warping gambar.
2.5
UML (Unified Modelling Language)
UML adalah suatu bahasa standar untuk menulis cetak biru (rancangan) piranti lunak. UML dapat digunakan untuk memvisualisasi (visualizing), menspesifikasikan (specifying), membentuk (constructing), dan mendokumentasikan (documenting) sistem piranti lunak. Booch, Jacobson dan Rumbaugh menyatakan ada tiga tujuan dibentuknya UML, yaitu: a.
Untuk memodelkan sistem, dari konsep menjadi suatu objek yang dapat dijalankan dengan menggunakan teknik berorientasi objek.
b.
Untuk menempatkan masalah yang sifatnya skalar ke dalam sistem yang rumit dan bertujuan kritis.
c.
Untuk membuat sebuah bahasa pemodelan yang bisa digunakan oleh manusia dan mesin. Berikut adalah beberapa diagram-diagram dalam UML:
a.
Class Diagram Class diagram mengambarkan kumpulan class, interfaces dan collaboration serta relationships ketiganya.
Beberapa komponen class diagram antara lain:
19
•
Class
Sebuah class adalah kumpulan objek yang mempunyai attributes, operations,
relationships dan semantics yang sama. Class dapat merepresentasikan hal fisik (seperti pelanggan, produk, buku), hal konseptual (seperti pesanan, pinjaman, pemesanan) atau hal organisasi (seperti perusahaan atau departemen).
Class digambarkan dengan sebuah kotak persegi panjang. Notasi class terdiri dari 3 bagian yaitu nama class, attribute dan operation.
Gambar 2.4 Notasi class •
Relationships i.
Generalization Menggambarkan hubungan class yang umum dengan class yang khusus yang dikenal dengan hubungan subclass/superclass atau child/parent.
ii.
Association Menggambarkan hubungan struktural antara class. Pada association, terdapat multiplicity dan aggregation.
Multiplicity menggambarkan berapa banyak objek yang mungkin terhubung dari suatu hubungan association. Multiplicity dinotasikan dengan 1 atau 1..1,
20
* atau 0..*, 0..1, 1..* atau bilangan tertentu di masing-masing ujung garis
association. Misalkan:
Gambar 2.5 Contoh multiplicity
Aggregation adalah association yang mempunyai hubungan “bagian dari”. Misalkan:
Gambar 2.6 Contoh aggregation b. Use Case Diagram
Use case diagram menggambarkan sekumpulan use case dan actor serta hubungan antara keduanya. Beberapa komponen dari use case diagram: •
Actor Actor mewakili peran pengguna dalam hubungannya dengan use case. Actor dapat saja berupa seorang manusia, alat perangkat keras atau sistem lain.
21
Gambar 2.7 Notasi actor •
Use Case Use case menjelaskan sekumpulan urutan, di mana masing-masing urutan mewakili interaksi “benda” di luar sistem (actor) dengan sistem itu sendiri. Sebuah use case mewakili sebuah functional requirement dari sistem secara keseluruhan. Use case menggambarkan apa yang dilakukan oleh sistem, bukan bagaimana sistem melakukannya.
Gambar 2.8 Notasi use case •
Flow of Events Flow of events menggambarkan perilaku sistem dengan kalimat yang jelas sehingga bisa dimengerti dengan mudah oleh orang di luar sistem.
•
Include Include relationship di antara use case-use case berarti sebuah use case dasar memasukkan perilaku dari use case lain secara eksplisit. Include relationship digunakan untuk menggambarkan use case yang berulang.
22
Gambar 2.9 Contoh include relationship •
Extend Extend relationship di antara use case-use case berarti use case dasar memasukkan perilaku dari use case lain secara tidak langsung. Extend
relationship digunakan untuk menggambarkan variasi dari tingkah laku normal.
Gambar 2.10 Contoh extend relationship c. Activity Diagram
Activity Diagram menggambarkan flow (aliran) dari sebuah aktivitas ke aktivitas lainnya dalam sistem.
Komponen
Keterangan
Initial state, yaitu menyertakan awal dimulainya suatu aktivitas.
Final state, yaitu menyatakan berakhirnya suatu aktivitas. State, menggambarkan aktivitas yang merepresentasikan kinerja dari suatu operasi
23
Pada transition dapat dituliskan ekspresi sebagai guard (kondisi yang menentukan aliran kontrol, ditandai dengan tanda “[ ]”).
Decision, menggambarkan kontrol dari aliran yang bersifat kondisional.
Forking dan joining dipergunakan untuk menggambarkan aliran kontrol yang berjalan secara paralel atau bersamaan. Tabel 2.1 Tabel notasi activity diagram
d. Statechart Diagram
Statechart Diagram menggambarkan sebuah state machine, yang terdiri dari state, transition, event dan aktivitas. Statechart diagram hampir sama dengan activity diagram. Keduanya sama-sama menggambarkan flow of control. Bedanya activity diagram menggambarkan flow of control dari suatu aktivitas ke aktivitas, sedangkan statechart diagram menggambarkan flow of control dari suatu state ke state lainnya.
24