BAB 2 LANDASAN TEORI
2.1
Definisi Citra, Pengolahan Citra, dan Pengenalan Pola Citra dapat didefinisikan sebagai fungsi dua dimensi dari f(x,y) di mana x dan y adalah koordinat bidang dan amplitudo dari f pada pasangan koordinat apapun adalah intensitas atau tingkat keabu – abuan dari citra pada titik tersebut. Jika x, y, dan nilai intensitas dari f tersebut berhingga, bernilai diskrit, citra tersebut disebut citra digital (Gonzalez and Woods, 2008, p. 1). Pengolahan
citra
(image
processing)
merupakan
bidang
yang
behrubungan dengan proses transformasi citra (image) yang bertujuan untuk mendapatkan kualitas citra yang lebih baik (Fairhurst, 1988, p. 5). Pengenalan pola (pattern recognition) merupakan bidang ilmu yang melakukan proses analisis gambar yang inputnya adalah gambar ataupun citra digital dan menghasilkan output suatu deskripsi dengan tujuan untuk mendapatkan informasi yang disampaikan oleh gambar atau citra, dengan kata lain meniru kemampuan manusia (otak manusia) dalam mengenali suatu objek atau pola terentu (Fairhurst, 1988, p. 5).
9
2.2
Computer Vision Computer vision merupakan ilmu yang mempelajari bagaimana komputer dapat mengenali obyek yang diamati (Fairhurst, 1988, p. 5). Computer vision adalah kombinasi antara pengolahan citra dan pengenalan pola. Computer vision bersama intelegensia semu (artificial intelligence) akan mampu menghasilkan sistem intelegen visual (visual intelligence system).
2.3
Matriks Matriks adalah sebuah cara yang dengan unik merepresentasikan dan bekerja dalam transformasi linear. Dengan kata lain, setiap transformasi linear dapat direpresentasikan dengan matriks, dan setiap matriks berhubungan dengan transformasi linear yang khas. Matriks dan determinan merupakan konsep yang sangat penting dalam aljabar linear, dan pertama kali diformulasikan oleh Sylvester (1851) dan Cayley.
2.3.1
Matriks Ortogonal Sebuah matriks Anxn adalah matriks ortogonal jika AAT = I dimana AT adalah matriks transpose dari A dan I adalah matriks identitas. Dengan kata lain, matriks ortogonal selalu memiliki invers dan A-1 = AT.
10
2.3.2
Matriks Invers Invers dari sebuah matriks bujur sangkar A, disebut juga matriks kebalikan, adalah sebuah matriks A-1 yang memenuhi AA-1 = I di mana I adalah matriks identitas. Sebuah matriks bujur sangkar A memiliki invers jika dan hanya jika determinan ||A|| ≠ 0 (Lipschutz, 1991, p. 45). Matriks yang memiliki invers disebut juga matriks non-singular.
2.3.3
Matriks Singular Matriks singular adalah matriks yang tidak memiliki invers. Sebuah matriks bujur sangkar A adalah matriks singular jika dan hanya jika determinan ||A|| = 0.
2.3.4
Matriks Kovarian Jika terdapat n himpunan yang dinotasikan dengan {X1}, {X2}, …, {Xn}, matriks kovarian orde pertama didefinisikan dengan Vij = cov(xi, xj) ≡ [(xi - µi) (xj - µj)] di mana µi adalah rata – rata (mean). Matriks dengan orde lebih tinggi didefinisikan dengan Vijmn = [(xi - µi)m (xj - µj)n]. Elemen matriks individual Vij = cov(xi, xj) disebut juga kovarian dari xi dan xj.
11
2.3.5
Matriks Identitas Matriks identitas adalah diagonal matriks paling sederhana yang didefinisikan oleh I(X) ≡ X untuk semua vektor X. Matriks identitas dapat dinotasikan dengan 1, I, atau E (singkatan dari istilah dalam Bahasa Jerman “Einheitsmatrix”; Courant dan Hilbert, 1989, p. 7). Matriks identitas juga dikenalan sebagai matriks unit (Akivis dan Goldberg, 1972, p. 71).
2.3.6
Matriks Transpose Matriks transpose A atau AT adalah matriks yang didapat dengan menukar setiap baris pada A menjadi kolom pada matriks AT, (aij = aji), dan memenuhi (AT)-1 = (A-1)T.
2.3.7
Nilai Eigen Nilai eigen adalah himpunan khusus dari skalar yang berhubungan dengan persamaan sistem linear yang dikenal juga dengan nama akar karakteristik (Hoffman dan Kunze, 1971), proper values, atau latent roots (Marcus dan Minc, 1988, p. 144).
12
2.3.8
Vektor Eigen Vektor eigen adalah himpunan khusus dari vektor yang berhubungan dengan persamaan sistem linear yang dikenal juga dengan nama vektor karakteristik, proper vector, atau latent vector (Marcus dan Minc, 1988, p. 144). Vektor eigen dan nilai eigen dalam sebuah sistem sangat berpengaruh pada bidang fisika dan teknik, di mana vektor eigen ekuivalen dengan diagonalisasi matriks dan sering muncul pada aplikasi – aplikasi yang umum seperti analisis stabilitas, fisika rotasi, sistem getaran, dan lainnya. Dekomposisi sebuah matriks bujur sangkar A menjadi nilai eigen dan vektor eigen dikenal dengan dekomposisi eigen, dan adalah fakta bahwa dekomposisi ini selalu mungkin dilakukan selama matriksnya adalah matriks bujur sangkar dikenal dengan Eigen Decomposition Theorem.
2.4
Principal Component Analysis Principal Component Analysis (PCA) merupakan salah satu metode paling sering digunakan dalam pengenalan citra dan kompresi data. Tujuan dari PCA adalah untuk mereduksi dimensi yang besar dari ruang data (observed variables) menjadi dimensi intrinsik yang lebih kecil
dari ruang fitur
(independent variables), yang dibutuhkan untuk mendeskripsikan data lebih sederhana.
13
Pekerjaan yang bisa dilakukan oleh PCA antara lain adalah prediksi, penghapusan redundansi, ekstraksi fitur, kompresi data, dan lainnya. Karena PCA merupakan metode yang bisa bekerja pada wilayah linear, maka aplikasi – aplikasi yang memiliki model linear dapat menggunakan metode ini, seperti pengolahan sinyal, pengolahan citra, komunikasi, dan lainnya. Algoritma dari Principal Component Analysis adalah sebagai berikut: 1.
Prepare the data Kumpulkan seluruh data yang akan diproses dalam sebuah matriks.
2.
Subtract the mean Agar PCA dapat bekerja dengan benar, rata – rata dari data harus dikurangkan dari setiap data yang ada. Rata – rata yang dikurangkan merupakan rata – rata dari setiap dimensi yang ada. Sehingga, setiap nilai x memiliki rata – rata x yang akan dikurangkan dan setiap nilai y memiliki rata – rata y yang akan dikurangkan.
3.
Calculate the covariance matrix Hitung matriks kovarian dari matriks yang telah dikurangkan dengan rata – ratanya.
4.
Calculate the eigenvectors and eigenvalues of the covariance matrix Hitung vektor eigen dan nilai eigen dari matriks kovarian yang sudah didapat sebelumnya. Penghitungan vektor eigen dari matriks kovarian
14
yang dimiliki, memungkinkan untuk mengekstraksi karakteristik dari data. 5.
Choosing components and forming a feature vector Pada umumnya, setelah vektor eigen didapatkan dari matriks kovarian, langkah
selanjutnya
adalah
mengurutkan
vektor
eigen
tersebut
berdasarkan nilai eigennya, dari paling tinggi ke paling rendah. Hal ini membuat vektor eigen tersusun berdasarkan besar pengaruhnya. Vektor eigen yang tidak terlalu berpengaruh (memiliki nilai eigen yang kecil) dapat dihilangkan sehingga dimensi matriks menjadi lebih kecil, namun informasi dari data dapat hilang walaupun sedikit. 6.
Deriving the new data set Langkah terakhir adalah untuk mendapatkan nilai data baru dengan mengalikan matriks dari vektor eigen yang didapat dari langkah sebelumnya dengan data lama yang sudah dikurangi dengan rata – ratanya.
2.5
Orthogonal Locality Preserving Projection Laplacianfaces adalah metode linear yang baru diajukan untuk representasi dan pengenalan wajah. Metode tersebut berdasarkan pada Locality
15
Preserving Projection (LPP) dan dengan tegas memperhitungkan struktur manifold dari wajah. Diberikan sebuah himpunan citra wajah {x1, x2, …, xn} ⊂ Rm, dan X = [x1, x2, …, xn]. S menjadi matriks similaritas yang terdefinisi pada titik – titik data. Laplacianfaces dapat diperoleh dengan menyelesaikan permasalahan minimalisasi berikut: n
n
(
)
a opt = arg min ∑∑ a T x i − a T x j Sij a
2
i =1 j=1
= arg min a T XLX T a a
dengan batasan aTXDXTa = 1, di mana L = D - S adalah graph laplacian dan Dii = ∑jSij. Dii mengukur kepadatan lokal dari xj. Laplacianfaces mengkonstruksikan − xi − xj
matriks similaritas S menjadi Sij = e
t
2
untuk xi dan xj berhubungan dan Sij =
0 untuk xi dan xj tidak berhubungan. Fungsi objektif pada Laplacianfaces mengalami penalti jika titik – titik yang berdekatan, xi dengan xj, dipetakan berjauhan. Karena itu, menyelesaikan permasalahan minimalisasi di atas merupakan usaha untuk memastikan bahwa xi dan xj berdekatan, sehingga yi(=aTxi) dan yj(=aTxj) juga berdekatan. Pada akhirnya, fungsi basis dari Laplacianfaces adalah vektor eigen yang berhubungan dengan nilai eigen terkecil dari masalah eigen XLXTa = λXDXTa. XDXT menjadi tunggal setelah beberapa tahap pemrosesan terhadap X pada Laplacianfaces; jadi, fungsi basis dari Laplacianfaces dapat dianggap sebagai
16
vektor eigen dari matriks (XDXT)-1 XLXT yang berhubungan dengan nilai eigen terkecil. Karena pada umumnya matriks (XDXT)-1 XLXT tidak simetris, fungsi basis dari Laplacianfaces tidak ortogonal. Setelah vektor eigen dihitung, Ak = [a1, a2, …, ak] menjadi matriks transformasi. Sehingga jarak Euclidean antara dua titik data pada ruang tereduksi dapat dihitung sebagai berikut:
dist(y i , y j ) = y i − y j = AT xi − AT x j = A T (x i − x j ) =
(x
− x j ) AA T (x i − x j ) T
i
Jika A adalah matriks ortogonal, maka AAT = I dan struktur metrik tetap terjaga.
2.6
Orthogonal Laplacianfaces
Algoritma dari metode Orthogonal Laplacianfaces untuk representasi dan pengenalan wajah berdasarkan kepada Orthogonal Locality Preserving Projection (OLPP). Pada analisis wajah berdasarkan penampilan, masalah yang
sering ditemukan adalah vektor dari citra wajah jumlahnya lebih besar dibandingkan dengan jumlah citra wajah itu sendiri, sehingga matriks XDXT bersifat tunggal. Untuk mengatasi masalah tersebut, metode PCA dapat diaplikasikan untuk memproyeksikan wajah ke dalam sebuah sub-ruang tanpa harus kehilangan informasi apapun dan matriks XDXT menjadi tidak tunggal.
17
Algoritma dari Orthogonal Locality Preserving Projection adalah sebagai berikut: 1.
PCA projection
Memproyeksikan citra wajah xi ke dalam sub-ruang PCA dengan cara menghilangkan komponen – komponen terkecil yang memiliki nilai eigen menuju nol. Matriks transformasi yang dihasilkan oleh PCA dinotasikan dengan WPCA. Dengan proyeksi PCA, wajah – wajah yang diekstrak tidak berhubungan (berdasarkan statistik) dan rank dari matriks yang baru sama besarnya dengan jumlah dimensi. 2.
Constructing the adjacency graph
G menunjuk pada sebuah graph dengan n titik. Titik ke-i menunjuk kepada citra wajah xi. Sebuah sudut diletakkan antara titik i dan j jika xi dan xj berdekatan, contohnya, xi berada di antara p nearest-neighbors dari xj atau xj berada di antara p nearest-neighbors dari xi. Perlu dicatat, jika informasi kelas tersedia, sudut antara dua titik data dalam satu kelas dapat dengan mudah diletakkan. 3.
Choosing the weights
Jika titik i dan j berhubungan, maka Sij = ed, d = -||xi – xj||2 t-1, t adalah konstanta yang cocok. Sebaliknya, jika titik i dan j tidak berhubungan maka Sij = 0. Matriks bobot S pada graph G memodelkan struktur lokal dari manifold wajah.
18
4.
Computing the orthogonal basis function
D didefinisikan sebagai matriks diagonal yang elemen – elemennya adalah kolom (atau baris, dikarenakan S simetris) penjumlahan dari S, Dii = ∑jSij. Didefinisikan juga L = D - S yang merupakan matriks Laplacian pada teori Spectral Graph. {a1, a2, …, ak} adalah vektor basis ortogonal. Didefinisikan A(k-1) = [a1, a2, …, ak-1] dan B(k-1) = [A(k-1)]T (XDXT)-1 A(k-1). Vektor basis ortogonal {a1, a2, …, ak} dapat dihitung sebagai berikut: -
Hitung a1 sebagai vektor eigen dari (XDXT)-1 XLXT yang berhubungan dengan nilai eigen terkecil.
-
Hitung ak sebagai vektor eigen dari M(k) = {I – (XDXT)-1 A(k-1) [B(k-1)] -1
[A(k-1)]T} (XDXT)-1 XLXT yang berhubungan dengan nilai eigen
terkecil dari M(k). 5.
OLPP embedding
WOLPP = [a1, a2, …, al], embedding-nya adalah sebagai berikut: x → y = WT x, W = WPCA WOLPP, y adalah representasi berdimensi l dari citra wajah x, dan W adalah matriks transformasi.
19
2.7
Nearest-neighbor Classifier Nearest-neighbor Classifier adalah sebuah metode sederhana yang
digunakan untuk mengklasifikasikan sebuah objek baru berdasarkan kesamaan data pada objek yang berada pada training set.
Nilai k yang ada pada
Nearest-neighbor Classifier adalah parameter jumlah nearest-neighbor yang
akan diambil untuk klasifikasi data baru. Algoritma dari Nearest-neighbor Classifier adalah sebagai berikut:
1.
Menentukan nilai k (banyaknya nearest-neighbor).
2.
Hitung jarak antara data – data pada objek baru dengan data – data pada objek yang lama dengan rumus D ( x, y ) =
n
∑ (x i =1
− yi )
2
i
dimana x adalah
objek baru, y adalah objek yang berada pada training set, n adalah jumlah pixel, dan D(x,y) adalah jarak antara objek baru dengan objek pada training set.
3.
Urutkan objek berdasarkan jarak yang didapat dan ambil k objek yang memiliki nilai D(x,y) paling kecil.
4.
Mengumpulkan kategori dari setiap objek yang termasuk nearestneighbor.
5.
Objek baru termasuk dalam kategori yang paling banyak muncul dari objek yang termasuk nearest-neighbor.
20
2.8
Perangkat Lunak
Perangkat lunak adalah (1) instruksi – instruksi (program komputer) yang ketika dieksekusi akan memberikan fungsi dan performa seperti yang diinginkan, (2) struktur data yang memungkinkan program memanipulasi informasi secara proporsional, dan (3) dokumen yang menggambarkan operasi dan penggunaan program (Pressman, 2001, p6) Perangcangan perangkat lunak adalah disiplin perancangan yang berhubungan dengan semua aspek dari produksi perangkat lunak dari tahap awal spesifikasi sistem sampai dengan pemeliharaan setelah sistem dalam tahap berjalan (Sommerville, 2001, p6). Salah satu model perancangan perangkat lunak adalah Waterfall Model atau dikenal juga dengan Linear Sequential Model. Menurut Pressman (2001, p28), Waterfall Model meliputi beberapa aktivitas berikut: -
Problem Definition/Concept Exploration Perangkat lunak selalu menjadi bagian sistem yang lebih besar, sehingga pekerjaan dimulai dari menentukan kebutuhan untuk semua elemen sistem dan kemudian menempatkan beberapa sub-bagian dari kebutuhan pada perangkat lunak. Pengamatan terhadap sistem menjadi penting ketika perangkat lunak harus berinteraksi dengan elemen lainnya seperti perangkat keras, manusia, dan database.
21
-
Requirements Analysis Specification Mengerti jenis program yang akan dibuat, pembuat perangkat lunak harus mengerti domain informasi dari perangkat lunaknya, begitu juga fungsi yang dibutuhkan, tingkah laku, performa, dan antarmuka.
-
Design Prototyping Desain perangkat lunak sebenarnya adalah sebuah proses bertingkat yang terkonsentrasi pada empat buat atribut berbeda dari program, yaitu struktur data, arsitektur perangkat lunak, representasi antar-muka, dan prosedur (algoritma) rinci.
-
Implementation and Unit Testing Desain yang diajukan harus bisa ditranslasikan menjadi bentuk yang bisa dibaca oleh mesin sehingga mampu diimplementasikan. Jika desain dapat dikerjakan secara rinci, unit testing dapat diselesaikan secara mekanis.
-
Integration and System Testing Setelah kode program diselesaikan, percobaan terhadap program dilakukan. Proses percobaan difokuskan pada bagian internal perangkat lunak, memastikan semua pernyataan sudah dicoba, dan juga pada fungsi eksternal; yaitu, melakukan tes untuk menemukan kesalahan dan memastikan bahwa dari input yang diberikan, akan keluar hasil yang diinginkan.
22
-
Release, Operation, and Maintenance Perangkat lunak akan mengalami perubahan setelah diberikan kepada pelanggan. Perubahan akan terjadi karena kesalahan yang ditemukan, karena keperluan untuk beradaptasi dengan perubahan lingkungan, atau karena pelanggan membutuhkan penambahan fungsi atau peningkatan performa.
Gambar 2.1 Waterfall Model.
2.9
C#
Menurut Bradley L. Jones (2001), C# adalah sebuah bahasa pemrograman baru yang dibuat oleh Microsoft dan telah diajukan kepada ECMA untuk standardisasi. Bahasa pemrograman C# dibuat oleh sebuah tim dari Microsoft yang dipimpin oleh Anders Hejlsberg yang sebelumnya telah membuat bahasa pemrograman lain yaitu Turbo Pascal dan Delphi.
23
2.10
Makalah Relevan
Penelitian – penelitian yang pernah dilakukan oleh peneliti lain yang berhubungan dengan penelitian terkait dengan penulisan skripsi ini adalah sebagai berikut: 1.
Orthogonal Laplacianfaces for Face Recognition, 2006, Deng Cai, Xiaofei He, Jiawei Han, Hong-Jiang Zhang. Mengajukan teori Orthogonal Laplacianfaces dan membandingkannya dengan metode Eigenfaces, Fisherfaces, dan Laplacianfaces.
2.
Orthogonal Locality Preserving Indexing, 2005, Deng Cai, Xiaofei He. Memberikan contoh aplikasi lain dari Orthogonal Locality Preserving Projection.
3.
Locality Preserving Projections, 2003, Xiaofei He, Partha Niyogi. Memperkenalkan metode LPP sebagai salah satu metode pengenalan wajah.
