TINJAUAN PUSTAKA Citra Digital

TINJAUAN PUSTAKA Citra Digital Secara umum citra merupakan gambar pada bidang dua dimensi. Ditinjau dari sudut pandang matematis, citra merupakan sebuah fungsi kontinu dari intensitas radiasi pada bidang dua dimensi. Sumber radiasi mengeluarkan radiasi yang kemudian mengenai objek, objek memantulkan kembali sebagian dari radiasi tersebut, pantulan radiasi ini ditangkap oleh sensor pada alat-alat optik seperti mata, kamera, pemindai (scanner) dan sebagainya. Akhirnya bayangan objek tersebut direkam dalam suatu media tertentu. Citra semacam ini disebut juga sebagai citra pantulan. Jika objek menghasilkan radiasi sendiri, maka citra yang tertangkap oleh sensor disebut sebagai citra emisi. Sedangkan jika objek bersifat transparan, sehingga citra yang dihasilkannya merupakan representasi dari radiasi yang berhasil diserap oleh partikel-partikel dari objek tersebut, maka citra tersebut adalah citra absorpsi. Untuk pembahasan selanjutnya pada seluruh bagian dari riset ini, yang disebut sebagai citra adalah citra pantulan yang ditangkap oleh sensor pada kamera. Analisis terhadap sebuah citra dapat dilakukan dengan menggunakan bantuan komputer melalui sebuah sistem visual buatan yang biasa disebut dengan computer vision. Secara umum, tujuan dari sistem visual adalah untuk membuat model nyata dari sebuah citra. Untuk itu citra yang ditangkap oleh sensor yang masih dalam bentuk fungsi kontinu (analog) harus dirubah terlebih dahulu menjadi fungsi diskret (digital) yang dapat dibaca oleh komputer. Proses ini disebut sebagai digitasi, terdiri dari dua sub proses yaitu sampling dan kuantifikasi. Sampling merupakan proses untuk mengubah sebuah sinyal dalam ruang kontinu menjadi sinyal dalam ruang diskret, hasil dari proses ini adalah citra yang terdiri dari piksel-piksel yang tersusun dalam kolom dan baris. Setiap piksel merupakan hasil penggabungan dari beberapa sinyal yang saling berdekatan. Sekali sebuah citra mengalami proses sampling, tidak dimungkinkan untuk mengembalikannya kedalam bentuk kontinu. Setiap piksel biasanya akan memuat nilai intensitas yang pada awalnya mempunyai range kontinu, artinya sangat banyak kemungkinan nilai yang dapat dimuat oleh setiap piksel. 7

Sehubungan dengan keterbatasan kemampuan komputer untuk memproses pengkodean nilai-nilai tersebut, dibutuhkan sebuah metode untuk membatasinya. Kuantifikasi merupakan proses untuk mengubah range nilai intensitas yang semula kontinu menjadi range nilai yang diskret sedemikian sehingga dapat diakomodasi oleh sistem pengkodean biner pada komputer. Akhirnya, sebuah citra yang telah melalui proses digitasi disebut sebagai citra digital. Representasi Citra Digital Citra digital biasa direpresentasikan sebagai sebuah fungsi dua dimensi f(x,y), x dan y adalah koordinat spasial yang menunjukkan lokasi dari sebuah piksel didalam sebuah citra dan amplitudo dari f pada setiap pasangan koordinat (x,y) adalah intensitas dari citra pada piksel tersebut [Gonzales, 2004]. Untuk kebutuhan pengolahan dan analisis, representasi tersebut ditampilkan dalam bentuk matriks sebagai berikut :

…......................... (1)

Tipe-Tipe Citra Digital Tiga tipe citra digital yang sering digunakan adalah citra intensitas, citra biner, dan citra RGB. Citra intensitas dan citra biner merupakan citra monokrom (lebih dikenal dengan citra hitam putih) sedangkan citra RGB merupakan citra berwarna. a. Citra Intensitas, merupakan sebuah matriks dua dimensi berukuran mxn yang setiap selnya berisi nilai intensitas antara 0 sampai dengan 255. Intensitas 0 ditangkap sebagai warna hitam pekat, sedangkan intensitas 255 ditangkap sebagai warna putih terang oleh mata manusia. Nilai intensitas yang ada diantaranya merupakan gradasi dari warna hitam ke putih, atau lebih sering disebut warna keabuan (grayscale). b. Citra biner, merupakan sebuh matriks dua dimensi berukuran mxn yang setiap selnya berisi kode 0 atau 1 yang merupakan representasi dari nilai logical "benar" 8

atau "salah", disebut juga tipe data boolean. Nilai 0 sering diasosiasikan dengan warna putih terang (setara dengan nilai 255 pada citra intensitas) sedangkan nilai 1 sering diasosiasikan dengan warna hitam (setara dengan nilai 0 pada citra intensitas). Namun bagaimanapun, asosiasi tersebut bisa berubah-ubah tergantung dari asumsi yang digunakan oleh pengguna. Tidak ada kesepakatan baku yang mengatur bagaimana nilai 0 dan 1 dihubungkan dengan warna hitam dan putih. Umumnya, citra biner terbentuk dari citra intensitas yang mengalami proses tresholding. Proses ini sangat sederhana, pertama-tama tetapkan sebuah nilai T yang terletak diantara range nilai intensitas. Ubah nilai intensitas dari setiap piksel dengan mengikuti aturan berikut: 0, jika f(n)≥T g(n) =

….................................................. (2)

1, jika f(n)
linear dari

R

m

ke

R

n

dimana n <<< m dengan memaksimumkan variansi

data. Misalkan input vector adalah

x∈R

m

y

dengan E[x]=0 (zero mean) dan

adalah vektor berdimensi n, maka transformasi linear dari

R

m

ke

R

n

dapat

dinyatakan sebagai :

[ ] [] [] ⋯aT1 ⋯ ⋯aT2 ⋯ ⋮ ⋯aTn ⋯

x1 x2 ⋮ xm

=

y1 y2 ⋮ yn

…............................... (3)

dengan :

[] [] []

a11 a 1= a12 ⋮ a 1m

a 21 a , a 2= 22 ⋮ a2m

a n1 a … a n= n2 ⋮ anm

Secara umum transformasi dapat dinyatakan sebagai : y i=aTi x

; i = 1,2,...,n

var  y i 

= var a Ti x 

var  y i 

= E [( aTi x  x T a i 

var  y i 

= a Ti E  xx T  ai

var  y i 

= ai

…..................... (4)

sehingga :

dimana

T

∑ ai

…................................. (5)

Σ adalah matriks covarian.

Selanjutnya harus ditentukan maksimum dengan kondisi batas

a i yang dapat membuat

∥a∥=1 atau

var  y i  menjadi

T a i a i=1 atau

T

a i a i−1=0

karena a i adalah sebuah unit vektor. Salah satu teknik memecahkan permasalah optimisasi seperti ini adalah menggunakan teknik pengganda lagrange. Penentuan a i dihitung sebagai berikut : Masalah optimisasi : Maksimumkan

: var  y i  = a Ti ∑ ai

Kendala

:

T

a i a i−1=0

Melalui pengganda lagrange, fungsi yang dimaksimumkan adalah :

10

f a i 

= a Ti ∑ ai - λ( a Ti a i−1 )

∂F =0 ∂ ai

= 2Σ a i - 2 λ a i = 0

Σ

ai

=λ

ai

….............................................. (6)

Dari persamaan 6 terlihat bahwa λ adalah nilai-nilai eigen dari matriks

Σ, sedang

a i adalah vektor eigen yang bersesuaian dengan masing-masing λ. Jika ruas kiri dan kanan persamaan tersebut dikalikan dengan a Ti maka akan diperoleh : a Ti ∑ ai

=

a Ti λ a i

kerena a Ti a i=1 , maka : T

ai

∑ ai = λ

var  y i  = λ …..................................................... (7)

Dari persamaan (7) tersebut dapat dilihat bahwa nilai eigen dari matriks covarian

Σ

adalah

var  y i  . Sehingga agar diperoleh varian maksimum maka a i

adalah vetor-vektor eigen yang bersesuaian dengan nilai-nilai eigen terbesar dari matriks

Σ.

Principal Components Analisys 2 Dimensi (Yang J. et al, 2004) Pada teknik pengenalan wajah berbasis 1D PCA, citra wajah 2D akan dirubah terlebih dahulu menjadi vektor citra 1D. Akibatnya ruang vektor citra yang terbentuk akan memiliki dimensi sangat besar. Hal ini menyebabkan perhitungan matriks kovarian secara akurat serta perhitungan nilai eigen dan vektor eigen dari matriks kovarian tersebut menjadi relatif sulit. Berbeda dengan 1D PCA, pada 2D PCA citra wajah tetap direpresentasikan dengan matriks. Hal ini menyebabkan matriks kovarian yang terbentuk menjadi jauh lebih kecil. Dampak dari fakta tersebut, 2D PCA memiliki dua kelebihan dibandingkan dengan 1D PCA, yaitu : 1. Evaluasi terhadap matriks kovarian lebih akurat. 2. Waktu yang diperlukan untuk menghitung nilai eigen dan vektor eigen lebih cepat 11

Formulasi 2D PCA Misalkan X adalah vektor kolom satuan berdimensi n. PCA 2D melakukan poreksi sebuah matriks acak dari citra A berukuran m x n kepada X dengan transformasi linear . Y=AX Sehingga akan diperoleh vektor Y berdimensi m, dinamakan vektor feature dari A. Permasalahannya adalah menetukan vektor X yang memaksimumkan total scatter dari proyeksi data. Secara matematis dapat dinyatakan sebagai : J(X) = tr (Sx) …......................................................................... (8) dimana Sx menyatakan matriks kovarian dari vektor feature data-data training, dan tr (Sx) adalah trace dari Sx. Selanjutnya matriks kovarian Sx dapat dinyatakan sebagai : Sx

= E Y −EY Y −EY T =E [ AX −E  AX ][ AX −E  AX ]T = E [ A−EA X ][ A− EA X ]T , sehingga :

tr  S x = X T [ E [ A− EAT  A−EA]] X .......................................... (9) Kemudian didefinisikan sebuah matriks T G t =E [ A−EA  A−EA] …........................................... (10)

Matriks

Gt dinamakan matriks kovarian(scatter) citra yang berukuran n x n.

Matriks ini dapat dihitung langsung dari M buah citra-citra training A j  j=1,2,... , M  1 Gt = M

M

∑  A j − A T  A j− A

…....................................... (11)

j=1

Maka kriteria pada persamaan (8) dapat dinyatakan sebagai : T

J  X = X G t X …..............................................................(12)

Kolom vektor satuan X yang memaksimisasi J(X) disebut sumbu proyeksi yang optimal. Ini berarti total scatter (varians) dari data yang telah diproyeksikan pada X menjadi maksimum. Sumbu tersebut adalah vektor-vektor eigen dari matriks Gt yang bersesuaian dengan nilai-nilai eigen terbesar.

12

Linear Support Vector Machine (SVM) Konsep SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah class pada input space. Gambar berikut memperlihatkan beberapa pattern yang merupakan anggota dari dua buah kelas : +1 dan –1. Pola yang tergabung pada class –1 disimbolkan dengan segitiga, sedangkan pola pada class +1, disimbolkan dengan lingkaran. Problem klasifikasi dapat diterjemahkan dengan usaha menemukan garis (hyperplane) yang memisahkan antara kedua kelompok tersebut.

Gambar 2 : Support vector, hyperplane dan margin Hyperplane pemisah dapat dinyatakan dengan persamaan

T w xb=0 dimana

w  adalah vektor normal dari hyperplane dan b merupakan intercept hyperplane. Misalkan himpunan n buah data training adalah D={  x , y  }, anggotanya adalah pasangan xi dan label kelasnya y i untuk i=1,2,...,n, dimana dalam SVM label kelas dinyatakan sebagai +1 dan -1. Selanjutnya linear classifier dapat dinyatakan sebagai T f  x i =signw xi b ….................................................. (13)

Permasalahan selanjutnya adalah mencari set parameter T f  x i =w x ib= y i untuk semua i.

w  , b sehingga

SVM berusaha mencari fungsi

pemisah/hyperplane optimum diantara fungsi yang tidak terbatas jumlahnya yang memisahkan dua kelas objek. Optimal hyperplane kemudian ditentukan terhadap support vector dengan memaksimumkan margin (ρ). Support vectors adalah data training yang terletak paling dekat ke hyperplane. Data-data ini merupakan data yang paling sulit untuk diklasifikasikan. Hyperplane yang optimal diperoleh pada 13

saat jarak support vector negatif ke hyperplane sama dengan jarak support vector positif ke hyperplane ( ρ/2). Jarak terpendek setiap vektor data xi ke hyperplane adalah jarak tegak lurus terhadap hyperplane (proyeksi) sehingga paralel dengan vektor normal w  . Unit vektor normal hyperplane adalah

terhadap hyperplane adalah

w  sehingga jarak proyeksi ∥w∥

w r  . Misalkan proyeksi ∥w∥

xi

x terhadap

hyperplane adalah x ' maka w  x '=x − yr …................................................................ (14) ∥w∥ dimana perkalian dengan y adalah untuk merubah tanda sesuai dengan kelas positif dan negatif. x w 

w r  ∥w ∥

T

w xb=0

x ' Gambar 3 : Proyeksi x terhadap hyperplane Karena x ' terletak pada hyperplane maka w T  wT  x' b=0 sehingga : w  x − yr ∥w∥ b=0 . Setelah persamaan tersebut diatur ulang akan diperoleh : r=y

wT xb ∥w∥

atau jarak absolut antar xi a dengan hyperplane adalah

∣

r=

w T xi b ∥w∥

∣

…................................................................ (15)

Jika normal vektor w  yang digunakan adalah unit vektor, maka ∥w  ∥=1 dan jarak xi ke hyperplane adalah 14

∣wT x ib∣

. Agar persamaan

menjadi unik, diambil

∣wT x ib∣=1

untuk setiap support vector xi (vektor

terdekat ke hyperplane). Sehingga jarak support vector xi terhadap hyperplane adalah

∣

∣

2 w T x i b 1 dan margin ρ = . = ∥w ∥ ∥w∥ ∥w ∥

Permasalahan kemudian menjadi bagaimana memilih w  dan b agar 2 maksimum dengan kondisi batas : ∥w ∥

∣wT x ib∣≥1

jika xi kelas positif dan

∣wT x ib∣≤1

jika

xi kelas negatif.

Permasalah ini dapat dirubah menjadi formulasi standar SVM sebagai permasalahan minimisasi : Minimumkan fungsi

1 2  = ∥w ∥ : J w 2

Kondisi batas

T : gi w  , b=1− y i w xi b

untuk i = 1, 2 … n Permasalahan ini merupakan permasalahan optimisasi fungsi kuadrat dengan kendala linear. Karena

J w   adalah sebuah fungsi kuadrat, maka akan ada satu

global minimum. Salah satu teknik pemecahannya adalah dengan metoda Pengganda Lagrange dan Teorema Karush-Kuhn-Tucker. (Smith, 2004), (Kecman, 2001). Dengan metoda tersebut permasalahan menjadi n

n

n

maksimumkan

1 T : L D  λ=∑ λ i− ∑ ∑ λ i λ j y i y j x i x j …... (16) 2 i=1 j=1 i=1

kendala

: λ i≥0 dan

n

∑ λ i y i=0

…........................... (17)

i=1

dimana λ = { λ 1 ,... λ n } adalah pengganda lagrange (variabel baru) untuk masing-masing data. Persamaan (16 ) dapat ditulis menggunakan notasi matriks : T

[] []

λ1 1 λ1 L D  λ=∑ λ i− ⋮ H ⋮ 2 i=1 λn λn n

….................. (18)

dimana H merupakan matiks berukuran n x n, dengan nilai pada baris ke-i dan kolom ke-j dari matriks H adalah

T

H ij = y i y j x i x j

15

L D  λ dapat dioptimasi menggunakan Quadratic Programming.

Selanjutnya

Berdasarkan pada λ = { λ 1 ,... λ n } optimal yang diperoleh : λ i=0 maka data ke-i adalah bukan support vector

•

jika

•

jika λ i≠0 dan

T

yi  w  x ib−1=0 maka data ke-i adalah

support

vector. Kemudian w  dihitung menggunakan persamaan n

w  =∑ λi y i x i …....................................... (19) i=1

b dapat dihitung menggunakan sembarang λ i0 melalui persamaan b=

1 −w T xi …....................................... (20) yi

Persamaan hyperplane optimal yang diperoleh adalah : f x =

T

 ∑ λi y i x i  x i∈ S

x ib ….................... (21)

dimana S adalah himpunan support vector S={ xi |

λ i≠0 }

Metoda Kernel Jika suatu kasus klasifikasi memperlihatkan ketidaklinieran, algorithma linear SVM tidak bisa melakukan klasifikasi dengan baik. Metoda kernel adalah salah satu teknik untuk mengatasi hal ini. Dengan metoda kernel suatu data xi di input space dimapping ke feature space F dengan dimensi yang lebih tinggi melalui map φ sebagai berikut φ : x → φ(x). Karena itu data x di input space menjadi φ(x) di feature space. Dari persamaan (16) terlihat bahwa optimisai fungsi pada data xi melalui perkalian titik

xTi x j . Jika

L D a hanya bergantung xi dibawa ke dimensi yang

lebih tinggi oleh φ(x) maka harus dihitung hasil kali titik pada dimensi yang lebih tinggi tersebut φ xTi φ  x j  . Fungsi yang akan dimaksimasi menjadi

16

n

n

n

1 L D a=∑ ai− ∑ ∑ ai a j y i y j φ  x Ti  φ x j  …...................................... (22) 2 i=1 j =1 i=1 Sering kali fungsi φ (x) tidak tersedia atau tidak bisa dihitung, tetapi dot product dari dua vektor dapat dihitung baik di dalam input space maupun di feature space. Dot product ini dinamakan kernel dan dinotasikan sebagai K  xi , x j 

Sehingga persamaan (19) menjadi : n

n

n

1 L D a=∑ ai− ∑ ∑ ai a j y i y j K  x i , x j  …........................................ (23) 2 i=1 j =1 i=1 Diharapkan pada dimensi yang lebih tinggi data dapat dipisahkan secara linear.

Gambar 4 : Suatu kernel map mengubah problem yang tidak linier menjadi linier dalam space baru Gambar 4 mendeskrisikan suatu contoh feature mapping dari ruang dua dimensi ke feature space tiga dimensi. Dalam input space, data tidak bisa dipisahkan secara linier, tetapi bisa dipisahkan di feature space. • • •

Beberapa fungsi kernel yang umum digunakan adalah : Linear T K  x i , x j = x i x j Polinamial T p K  x i , x j = x i x j1 Radial Basis Function (data dibawa ke dimensi tak hingga) −1 K  x i , x j =exp ∥x i −x j∥2 2 2σ





17