Vol 3, No 3 Desember 2013
ISSN 2088-2130
EKSTRAKSI FITUR MENGGUNAKAN METODE LDA DAN PEMILIHAN EIGEN VALUE PADA CACAT KERTAS DUPLEK Aeri Rachmad Fakultas Teknik – Universitas Trunojoyo Madura
[email protected]
ABSTRAK Industri kertas masih menggunakan proses yang manual dengan menggunakan peralatan yang manual untuk mendeteksi cacat yang terdapat pada kertas.Dalam peneletian ini bertujuan untuk mereduksi cacat pada kertas dengan menggunakan LDA, berbeda dengan penelitian sebelumnya yang menggunakan metode PCA. Linear Discriminant Analysis merupakan salah satu metode untuk melakukan reduksi dan ekstraksi cacat yang ada pada kertas. Metode ini akan mereduksi dimensi yang ada agar lebih kecil serta mencari nilai eigen yang terbesar untuk mempercepat proses pengujian. Dalam pengujian menggunakan euclidian distance terdapat error minimal sebesar 4% dan error maksimal sebesar 12%.
Kata kunci: Linear DiscriminantAnalysis, nilai eigen, euclidian distance
ABSTRACT The paper industry is still using manual processes and manual equipment to detect defects contained in the paper. In this research aims to reduce defects in the paper by using LDA, in contrast to previous studies that use PCA method. Linear Discriminant Analysis is a methods to perform the reduction and extraction of defects that exist on paper. This method will reduce the existing dimensions that are smaller and look for the largest eigenvalues to accelerate the testing process. In testing using the euclidian distance errors are minimum of 4% and maximum error of 12%. Keywords: Linear Discriminant Analysis, eigenvalues, euclidian distance
142
Vol3, No 3Desember 2013
PENDAHULUAN Latar Belakang Pendeteksian kecacatan pada kertas merupakan salah satu bidang penelitian yang penting bagi perusahaan kertas yang karena bias menurunkan tingkat kesalahan kertas sebelum distribusi ke konsumen atau pada distributor. Meskipun tidak banyak mendapatkan perhatian dari para peneliti, sistem pendeteksian kecacatan pada kertas dapat dipergunakan untuk aplikasi pendeteksian dini pada kertas sehingga komplain yang disebabkan karena kecacatan kertas bisa menurun atau bahkan tidak ada. Komputer Vision memegang peranan penting dalam Human Computer Interaction Technology (HCI) yang meliputi deteksi wajah, penjejakan wajah/badan, deteksi aksi (gesture), estimasi umur, etnik dan deteksi cacat pada kertas. Sistem deteksi dan identifikasi kertas dapat dipergunakan dalam banyak hal, seperti yang berhubungan dengan kecacatan kertas Penelitian deteksi kecacatan kertas jarang sekali dilakukan apalagi warna yang dimiliki kertas hanya bewarna kertas adalah putih saja (Homogen). Penenilitian kali ini akan melihat seberapa jauh kemampuan komputer dan algoritma yang digunakan untuk mendeteksi kecacatan kertas serta mengklasifikasikan hasil cetakan kertas berdasarkan tingkat kecacatannya. Sistem deteksi kecacatan pada kertas melalui beberapa tahapan proses, yaitu deteksi kecacatan kertas, ekstraksi ciri / fitur dan tahapan terakhir terakhir adalah pengenalan cacat kertas[1]. Tujuan Tujuan dilakukan penelitian ini adalah mengembangkan dari penelitian sebelumnya sehingga pengenalan terhadap klasifikasi kecacatan kertas duplek menjadi lebih baik dari sebelumnya. untukmengetahui hasil dari pengenalan cacat dari sebuah kertas
143
berdasarkan tingkat kecacatan pada kertas dengan menggunakan metode LDA.
Permasalahan Bagaimana mambandingkan penggunaan ekstraksi fitur LDA dan PCA dalam melakukan pengenalan cacatpada kertas Duplek.
Tinjauan Pustaka Data Kertas Duplex Data citra yang digunakan berasal dari dari data natural kertas dupleks hasil produksi pabrik kertas PT. Pakerin Prambon Mojokerto yang kemudian dipindai dengan parameter pemindai sbb: 1. Scan Mode: Color/Greyscale. 2. Image Quality: 300 dpi Pemilihan Scan Mode menggunakan moda Color/Greyscale adalah karena kedua modetersebutmemberikankemungkinanwarn a yang lebihbanyakdaripadacitrabiner.Pada sistem ini, baik citra color ataupun greyscale akan dikonversi menjadi greyscale. Sedangkan pemilihan Image Quality menggunakan 300 dpi supaya cacat-cacat yang tidak nampak oleh mata, bisa „terlihat„ oleh program pendeteksi cacat. DenganImage Quality 300 dpi, output dari pemindaian kertas berukuran A4 adalah 2430x3483 piksel. Linear Discriminant Analysis (LDA) Ide dasar dari LDA adalah menemukan sebuah transformasi linear sehingga pengklasteran dapat dipisahkan setelah transformasi. Ini dapat diperoleh melalui analisa matriks scatter. LDA lebih bertujuan untuk mengoptimalkan diskriminan sedangkan PCA lebih pada pengoptimalan representasi. Sama dengan proyeksi pada PCA, pada LDA vektor data diproyeksikan ke dalam sub ruang. Demikian pula apabila ada data uji maka
Aeri Rachmad dkk,Ekstraksi Fitur...
akan diproyeksikan ke sub ruang yang sama dengan melakukan perkalian vektor eigen hasil training dengan vektor data uji. LDA mengelompokkan vektor data dari kelas yang sama dan memisahkan kelas yang berbeda. Vektor data diproyeksi dari ruang N-dimensi (dimana N ada jumlah Kertas Duplex yang diproses) ke ruang C-1 dimensi (dimana C adalah jumlah kelas dalam vektor data).
yang orthonormal yang memaksimalkan rasio dari matriks between-class scatter ke matriks within-class scatter dari sample yang telah diproyeksikan, yaitu (3):
Wopt arg max w
wT S B w wT S w w
w1 , w2 ,..., wm
dimana {wi| i=1, 2, ..., m} adalah sekumpulan vektor eigen yang digeneralisasi dari SB dan SW yang bersesuaian dengan m nilai eigen terbesar { i | i=1, 2, ..., m }, yaitu (4):
S B wi i S w wi i = 1, 2, ..., m
METODOLOGI
Gambar 1. Proyeksi data 2 kelas menggunakan metode LDA Metode LDA memilih W dengan cara memaksimalkan rasio antara between-class scatter (SB) (1)dan within-class scatter (SW)(2). Berikut ini definisi dari kedua kelas scatter :
Metodologi penelitian yang digunakanuntukmendukungpenyelesaianper ancangandanpembuatansistemdeteksicacatke rtasadalah : 1. Deteksi dan segmentasi cacat kertas duplek 2. Normalisasi data cacat kertas duplek 3. Perbandingan metode ekstraksi fitur PCA dan LDA 4. Pengenalan cacat kertas duplek menggunakan euclidian distance
HASIL DAN PEMBAHASAN Deteksi dan Segmentasi Cacat
l
S B ni ( (i ) )( (i ) ) T i 1
l ni S w ( x (ji ) (i ) )( x (ji ) (i ) ) T i 1 j 1 dimana adalahvektor rata-rata jumlah
sample, niadalah jumlah sample dalam kelas ke-i, (i)adalah vektor rata-rata kelas ke-i, xj(i)adalah sample ke-j pada kelas ke-i, dan l adalah jumlah kelas. Jika SW tidak singular, proyeksi optimal Wopt dipilih sebagai matriks dengan kolom
Dalam penelitian ini kami melakukan (1) deteksi cacat kertas duplek pada selembar kertas dengan ukuran A4 dengan multi cacat (2) yang terdapat pada kertas duplek tersebut. Proses deteksi cacat kertas duplex terdiri dari: proses greyscale, threshold, edge detection, menyambung pixel yang mempunyai jarak kurang dari sama dengan 6 pixel, mengkrop area cacat dengan ukuran 31 x 31 pixel. Algoritma deteksi cacat dan cropping pada citra adalah sbb[1]:
144
Vol 3, No 3 Desember 2013
Polyline Polygon 250
245
240
235
230 246
247
248
249
250 251 Dimensi pertama
252
253
Gambar 3.Data Testing yang Diplot dalam 2-Dimensi
Normalisasi Data Cacat Kertas
255 Polyline Polygon
250
Normalisasi data cacat kertas tersebut bertujuan agar ukuran dari cacat kertas yang terdeteksi menjadi lebih standart. Ukuran yang telah ditentukan yaitu 31x31 pixel yang didalamnya terdapat hanya satu jenis cacat saja seperti tampak pada gambar 4. Algorithma untuk melakukan normalisasi cacat kertas[1]:
245
Dimensi kedua
255
Dimensi kedua
1. Membaca gambar kertas duplek dengan ukuran yang ditentukan. 2. Melakukan threshold pada kertas duplek sesuai dengan intensitas dari kertas. 3. Mengubah image menjadi hitam dan putih saja. 4. Melakukan edge detection. 5. Menyambung pixel yang mempunyai jarak kurang dari sama dengan 6 pixel. 6. Mengindex area yang mempunyai kemungkinan merupakan cacat kertas Duplek yang berbentuk polygone dan polyline . Pada Gambar 2 menunjukkan nilai sebaran data training dari 80 data masing – masing cacat yang sudah di pilih yang paling jelas cacatnya dan pada Gambar 4 menunjukkan sebaran 20 data testing masing – masing
240 235 230 225 220 215 210
215
220
225
230 235 Dimensi pertama
240
245
250
255
cacat pada Gambar 3. Gambar 2.Data Training yang Diplot dalam 2-Dimensi
145
1. Membaca data cacat yang sudah terdeteksi sebelumnya. 2. Merubah data cacat menjadi hitam dan putih 3. Mendeteksi ukuran image 31 x 31 pixel 4. Melakukan threshold sesuai dengan intensitas cacat kertas yang sudah terdeteksi 5. Mencari keliling dan luasan cacat kertas 6. Mencari cacat poliline dengan membagi luas dibagi dengan keliling
254
255
Aeri Rachmad dkk,Ekstraksi Fitur... 3. Menghitung rata-rata vektor data (1,2, …n) dari masing-masing objek. 4. Mengurangkan data masing-masing kelas dengan rata-ratanya. 5. Mengurangkan masing-masing rata-rata kelas dengan rata-rata keseluruhan. 6. Menghitungbetween-class scatter : l
S B ni ( (i ) )( (i ) ) T i 1
7. Menghitungwithin-class
scatter
:
S w ( x (ji ) (i ) )( x (ji ) (i ) ) T i 1 j 1 l
ni
8. Menghitung proyeksi optimal Wopt : Wopt arg max w
Gambar 4. Normalisasi Cacat Polyline dan Polygone Proses Linier Discriminat Analysis (LDA) Vektor data hasil proses PCA merupakan data yang representasinya telah optimal karenapada proses PCA akan diambil data yang mempunyai varians dominan, namundemikian proses tersebut tidak bertujuan untuk diskriminan data. Untuk mendapatkan sebaran data yang tingkat diskriminannya optimal, maka dilakukan proses analisa diskriminan menggunakan metodeLinier Discriminant Analysis (LDA). Proses LDA akan meningkatkan rasio antara between-class scatter (SB) danwithin-class scatter (SW), jadi semakin besar jarak sebaran data yang berlainan kelas dan semakin dekat jarak sebaran data yang sekelas maka tingkat diskriminan data akan semakin baik. Untuk meningkatkan diskriminan data dapat diproses berdasarkan algoritma LDA berikut: ALGORITMA: LDA(X,Y) 1. Vektor data
w TSB w w TSw w
w1 , w2 ,..., wm Pemilihan W optimal berdasarkanpadanilaieigenterbesar, haltersebutdapatdijelaskanberdasarkanpersa maan:
S BV S wV dimana V adalah vektor eigen dan adalah nilai eigen. Persamaan diatas dapat dituliskan ulang menjadi:
SB V V SW dimana
atau
V V
SB . SW
Vektor eigen dan nilai eigen didapatkan dari matrik kovarian dan pemilihan eigen vektor optimalnya berdasarkan dengan nilai eigen terbesar.
masukan:
X [ x11, x12 ,..., x1n , x21, x22 ,..., x2n, ........ , xm1 , xm2 ,..., xmn ] 2. Menghitung rata-rata vektor data () berdasarkan rata-rata keseluruhanobjekdarimasing-masingcacat.
146
Vol3, No 3Desember 2013
LDA.m
data terakhir untuk testing. 5 kelompok ini kemudian di rotasi tanpa terjadi overlapping sehingga semua kelompok pernah menjadi data testing. Dengan 5 kelompok, berarti 1 kelompok terdiri dari 40 data (20 cacat polyline dan 20 polygone).
Untuk data uji, 1 kelompok terdiri dari 40 data (20 cacat polyline dan 20 polygone). ‘ErrPlgn’adalah errorcacat polygone, yaitu terdeteksinya cacat polygone pada kelompok 10 data cacat polyline. Sebaliknya, ‘ErrPln’ adalah errorpolyline, yaitu terdeteksinya cacat polyline pada kelompok 10 data cacat polygone. ‘ErrM’adalah nilai rata-rata dari ErrPlgn dan ErrPln. ErrPlgn, Errpln dan ErrM ditampilkan dalam jumlah dan persen. Jika dalam persen, maka (misal ErrP) nilai ErrP adalah (ErrP/10)*Gambar5.HasilProyeksi
Pengujian dan Analisa Menggunakan Metode LDA Seperti yang telah dilakukan pada proses PCA mentraining 80 data cacat polyline dan 80 cacat polygon kemudian baru di olah dengan PCA dan LDA seperti yang ditunjukkan pada gambar 5 dan 40 data testing seperti pada gambar 6. Setelah data diolah dengan metode PCA maka dilakukan reduksi dimensidengan LDA menggunakan metode five-fold cross validation (CV).Yaitu data dibagi menjadi 5 kelompok, dengan 4/5 data pertama dijadikan data training dan 1/5
Data Training dengan Diplotdalam 2-dimensi
147
LDA
yang
Aeri Rachmad dkk,Ekstraksi Fitur...
140
Error City Distance
Polyline Polygon
120
14 12 10 8 6 4 2 0
100
Persentase
Dimensi kedua
80 60 40 20 0
ErrorPolylin e ErrorPolyg one
1
-20
2
3
4
5
Jumlah group
-40 -60 -100
0
100
200 300 Dimensi pertama
400
500
Gambar 6.HasilProyeksi Data Testing dengan LDA yang Diplotdalam 2-dimensi
Gambar 8.ErrorCity Distance tiap Group Pada gambar 7 dan 8 menunjukkan error pada euclidian distance dan city distance dimana rata-rata nilai terendah pada nilai 5% yang terjadi pada group 1 dan
Table 1Hasil error City distance dan error Euclidian distance dengan LDA
Error Euclidian Distance 14 Persentase
12 10
ErrorPolyline
8
ErrorPolygone
6
ErrorRata-Rata
4 2 0 1
2
3
4
5
Jumlah Group
SIMPULAN Berdasarkan hasil pengujian dan analisa dari sistem yang telah dilakukan didapatkan beberapa kesimpulan dalam proses pengenalan cacat kertas menggunakan metode LDA yaitu: 1. Deteksi cacat kertas dapat dilakukan lebih baik di bandingkan dengan proses manual. 2. LDA dapat digunakan sebagai ekstraksi dan reduksi dimensi serta pengenalan cacat kertas dengan memilih eigen value yang mempunyai error yang kecil dibandingkan dengan metode PCA
Gambar 7. Error Euclidian Distance tiap Group
148
Vol3, No 3Desember 2013 DAFTAR PUSTAKA [1] Rachmad A, “Pengenalan kecacatan kertas Duplek menggunakan Ekstraksi fitur PCA” [2] HaryantiRivai, MauridhiHery P, Supeno Mardi S N, “ PengenalanCiri – CiriTeksturKain Sutra menggunkanMetode GMRF denganKlasifikasi SOMKOHONEN”, InstitutTeknologiSepuluhNopermber Surabaya, 2005. [3] Hua-Long Bu, Guo-Zheng Li, XueQiangZeng, “Reducing Error of Tumor Classification by Using Dimension Reduction with Feature Selection”, School of Computer Engineering and Science, ShanghaiUniversityShanghai 200072, China, 2007 [4]E.Ramaraj and M.Punithavalli, “Taxonomically Clustering Organisms Based on the Profiles of Gene Sequences Using PCA” 1Department of Computer Science and Engineering, Alagappa University, TN, India,2006 [5] Viola, Paul; Jones, Michael J., “Fast Multi-view Face Detection”, Demo at then IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2003 [6] Meiching Fong, “Dimension Reduction on Hyperspectral Images” , UCLA Department of Mathematics, 2007. [7] Zehang Sun, Xiaojing Yuan, and G.Bebis, Ronald Miller, ”Object detection using feature subset selection” , Department of Computer Science, University of Nevada, Reno 2004
149
