IMPLEMENTASI PENGENALAN KODE PETI KEMAS SECARA OTOMATIS MENGGUNAKAN FITUR EIGEN Mujiono1, Nanik Suciati2, Arya Yudhi Wijaya3 Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Email:
[email protected] ABSTRAK Pengenalan kode peti kemas merupakan salah satu langkah penting dalam manajemen aliran peti kemas. Dewasa ini, pengenalan kode peti kemas masih dilakukan oleh manusia, sehingga rawan terjadi kesalahan dan membutuhkan banyak waktu. Masalah ini menimbulkan ketertarikan untuk melakukan sebuah penelitian yang menghasilkan sistem otomatis berbasis visi komputer yang memungkinkan pengenalan kode peti kemas secara otomatis. Input sistem berupa citra peti kemas yang diproses melalui tahapan konstruksi model dan pengenalan kode peti kemas. Pada tahap konstruksi model dilakukan segmentasi menggunakan metode local thresholding. Selanjutnya, dilakukan ekstraksi area kode peti kemas berdasarkan fitur geometri kode peti kemas. Hasil ekstraksi setiap karakter digunakan untuk menyusun model fitur eigen dari citra training. Pada tahap pengenalan kode, dilakukan pemisahan baris kode peti kemas. Selanjutnya, setiap karakter dibaca dengan menghitung PCA Reconstruction Error terkecil. Hasil uji coba menunjukkan bahwa metode yang diterapkan menghasilkan sistem otomatis dengan tingkat pengenalan kode yang tinggi dan waktu pengenalan kode yang singkat. Secara keseluruhan, sistem ini berpotensi untuk meningkatkan efisiensi terminal peti kemas serta meningkatkan manajemen aliran peti kemas. Kata kunci: pengenalan kode, segmentasi lokal, fitur geometri, model fitur eigen, principal component analysis error atau kesalahan yang dilakukan oleh manusia 1. Pendahuluan dalam mengenali kode peti kemas dan waktu pengenalan dapat dikurangi. Dalam beberapa tahun terakhir, transportasi kapal perindustrian menjadi semakin berkembang di dunia internasional. Hal ini berbanding lurus 2. Tinjauan Pustaka dengan jumlah peti yang diangkut yang juga mengalami peningkatan. Peti Kemas atau yang 2.1 Peti Kemas dalam bahasa Inggris disebut sebagai Container Peti kemas (container) merupakan peti adalah salah satu alat untuk mengemas barang atau kotak yang memenuhi persyaratan teknis sehingga diangkut dengan mudah menggunakan sesuai dengan International Organization for truk, kapal, atau pesawat terbang, terutama untuk Standardization (ISO) sebagai alat atau perangkat lintas pulau atau lintas Negara[1]. pengangkut barang yang bisa digunakan diberbagai Setiap peti kemas memiliki kode yang moda, mulai dari moda jalan dengan truk peti berisi informasi. Informasi yang disimpan dalam kemas, kereta api, dan kapal peti kemas laut seperti kode peti kemas antara lain : id pemilik, kategori, yang terlihat pada Gambar 2.1. nomor seri, cek digit, kode ukuran, dan kode tipe peti kemas [2]. Untuk mengetahui informasi yang disimpan oleh peti kemas harus dilakukan pengenalan terhadap kode tersebut. Pengenalan kode peti kemas merupakan salah satu langkah penting dalam manajemen aliran peti kemas. Dewasa ini, pengenalan kode peti kemas masih dilakukan oleh manusia, sehingga rawan terjadi kesalahan dan membutuhkan banyak waktu dalam penerapannya. Masalah ini menimbulkan ketertarikan untuk melakukan sebuah riset yang menghasilkan sistem otomatis berbasis visi komputer yang Gambar 2.1 Peti Kemas memungkinkan pengenalan kode peti kemas secara Salah satu keunggulan angkutan peti kemas otomatis [1]. Input sistem yang berupa citra peti adalah intermodality dimana peti kemas bisa kemas dan diproses menggunakan metode-metode diangkut dengan truk peti kemas, kereta api, dan dalam pengolahan citra dan visi komputer, kapal peti kemas. Hal ini menyebabkan peralihan sehingga memungkinkan pengenalan kode peti angkutan umum barang menjadi angkutan barang kemas secara otomatis. Dengan sistem ini, human-
1
Tabel 2.1 Ketentuan dan arti kode peti kemas berdasarkan ISO Baris Pertama
dengan peti kemas menonjol dalam beberapa dekade terakhir ini. Hal ini juga terlihat pada pelabuhan-pelabuhan kecil yang sudah menunjukkan trend peralihan ke peti kemas karena alsan keekonomisan terutama dalam kaitannya dengan kecepatan bongkat muat dan biaya yang lebih rendah.
2.2
Kode Peti Kemas
Kode peti kemas merupakan barisan huruf baik itu abjad mapun numerik yang memiliki arti. Arti kode pada peti kemas berdasarkan ISO6346 (BIC) codes dapat dilihat pada Gambar 2.2. Kode peti kemas terdiri dari dua baris kode, baris pertama terdiri dari sebelas karakter, dan baris kedua terdiri dari empat karakter. Sehingga sebuah peti kemas memiliki 15 karakter kode yang terdiri dari huruf dan angka. Pada baris pertama, empat karakter pertama merupakan huruf dan tujuh karakter lainnya merupakan angka. Tiga karakter pertama menujukkan id pemilik dan karakter keempat menun jukkan kategori peti kemas. Karakter terakhir pada baris pertama menujukkan cek digit, dan karakter lainnya menujukan nomer seri peti kemas. Pada baris kedua, dua karakter pertama dan karakter terakhir merupakan angka dan karakter ketiga merupakan huruf. Dua karakter pertama menujukkan kode ukuran peti kemas, karakter ketiga dan terakhir menujukkan kode tipe peti kemas. Contoh kode peti kemas, ketentuan penulisan, dan arti dari masing-masing karakter yang memenuhi ISO, dapat dilihat pada Gambar 2.3 dan Tabel 2.1.
Kode Karakter
Arti
Tipe Karakter
Tiga karakter pertama (YML)
Id Pemilik
Huruf
Karakter keempat (U)
Kategori
Huruf
Karakter terakhir (0)
Cek Digit
Angka
Karakter yang lain (471645)
Nomer Seri
Angka
Kode Karakter
Arti
Tipe Karakter
Dua karakter pertama (42)
Kode Ukuran
Angka
Karakter ketiga (G)
Kode Tipe
Huruf
Karakter terakhir (1)
Kode Tipe
Angka
Baris Kedua
2.3
Computer Vision
Computer Vision merupakan salah satu bidang ilmu yang sedang berkembang dewasa ini. Teknik-teknik yang dibahas dalam ilmu ini merupakan penggabungan dari beberapa bidang ilmu diantaranya Grafika Komputer dan Pengolahan Citra. Teknik-teknik tersebut digunakan untuk mengotomatisasikan dan memudahkan proses persepsi visual yang dilakukan melalui peralatan penangkap citra misalnya scanner dan kamera yang kemudian diinterpretasikan ke dalam informasi-informasi yang representatif [3]. Computer Vision dapat diterapkan pada beberapa permasalahan, antara lain: pengenalan objek (object recognition), analisis gerak (motion analysis), rekonstruksi adegan (scene reconstruction), dan perbaikan citra (image restoration). Computer Vision System menggunakan beberapa metode untuk menyelesaikan permasalahan tertentu. Metodemetode tersebut berupa akusisi citra (image acquisition), pra-pengolahan (pre-processing), ekstraksi fitur (feature extraction), pendeteksian, proses tingkat tinggi, dan penentuan keputusan [4].
Gambar 2.2 ISO6346 (BIC) codes
2.4
Citra grayscale
Citra grayscale, yaitu citra yang nilai pixel-nya merepresentasikan derajat keabuan atau intensitas warna putih. Nilai intensitas paling rendah merepresentasikan warna hitam dan nilai intensitas paling tinggi merepresentasikan warna putih. Pada umumnya citra grayscale memiliki kedalaman pixel 8 bit (256 derajat keabuan), tetapi ada juga citra grayscale yang kedalaman pixel-nya bukan 8 bit, misalnya 16 bit untuk penggunaan yang memerlukan ketelitian tinggi.
Gambar 2.3 Kode peti kemas
2
Citra grayscale merupakan citra satu kanal, dimana citra f(x,y) merupakan fungsi tingkat keabuan dari hitam keputih, x dan y menyatakan variable kolom atau posisi pixel di garis jelajah. Intensitas f dari citra hitam putih pada titik (x,y) disebut derajat keabuan (grey level), yang dalam hal ini derajat keabuannya bergerak dari hitam keputih. Derajat keabuan memiliki rentang nilai dari Imin sampai Imax, atau Imin < f < Imax, selang (Imin, Imax) disebut skala keabuan. Biasanya selang (Imin, Imax) sering digeser untuk alasan-alasan praktis menjadi selang [0,L], yang dalam hal ini nilai intensitas 0 meyatakan hitam, nilai intensitas L meyatakan putih, sedangkan nilai intensitas antara 0 sampai L bergeser dari hitam ke putih. Sebagai contoh citra grayscale dengan 256 level artinya mempunyai skala abu dari 0 sampai 255 atau [0,255], yang dalam hal ini intensitas 0 menyatakan hitam, intensitas 255 menyatakan putih, dan nilai antara 0 sampai 255 menyatakan warna keabuan yang terletak antara hitam dan putih. Citra grayscale dapat dilihat pada Gamabr 2.4(a).
2.5
2.6
Tujuan digunakannya Thresholding adalah untuk mengkonversi dari citra grayscale ke citra biner (hitam-putih). Proses thresholding merupakan pengelompokan nilai derajat keabuan (gray level) dari setiap pixel ke dalam dua kelas yaitu hitam (memiliki nilai intensitas 0) dan putih (memiliki nilai intensitas 1). Oleh karena itu pengelompokan / pemetaaan setiap pixel pada citra ke dalam dua nilai yaitu 0 dan 1 dengan menggunakan fungsi thresholding: (2.1)
Dalam hal ini fg(i,j) adalah citra gray, fB(i,j) adalah citra biner/ hitam-putih, dan T adalah nilai threshold. Dengan operasi thresholding tersebut, objek kode peti kemas dibuat menjadi berwarna gelap (0 atau hitam) sedangkan latar belakang berupa pintu peti kemas menjadi berwarna terang (1 atau putih). Local Thresholding atau adaptif threshold digunakan untuk mengkonversi citra grayscale ke citra biner dengan menggunakan nilai threshold yang berbeda pada region yang berberda pada citra. Metode ini dapat mencegah kekurangan pada metode threshold biasa (global thresholding) dimana perubahan tingkat kecerahan pada citra dapat menyebabkan beberapa bagian menjadi terlalu terang (daerah terang) dan beberapa bagian menjadi terlalu gelap (daerah gelap).
Citra biner
Citra Biner yaitu citra yang hanya terdiri atas dua warna, yaitu hitam dan putih. Oleh karena itu, setiap pixel pada citra biner cukup direpresentasikan dengan 1 bit. Meskipun saat ini citra berwarna lebih disukai karena memberi kesan yang lebih kaya dari citra biner, namun tidak membuat citra biner mati. Pada beberapa aplikasi citra biner masih tetap di butuhkan, misalkan citra logo instansi (yang hanya terdiri dari warna hitam dan putih). Citra biner dapat Gambar 2.4(b) Alasan penggunaan citra biner adalah karena citra biner memiliki sejumlah keuntungan sebagai berikut:
2.6.1
Metode Otsu
Proses binerisasi menghasilkan citra biner dengan memiliki dua nilai tingkat keabuan yaitu hitam dan putih. Permasalahan utama dalam proses binerisasi adalah menentukan nilai ambang (Threshold). Nilai ini digunakan untuk mempartisi citra gray scale kedalam dua nilai yaitu hitam dan putih. Penentuan nilai ambang yang ditetapkan pada suatu nilai tertentu (fixed threshold) sangat berisiko untuk diterapkan karena dapat menghasilkan citra biner yang kurang sempurna sehingga mempersulit proses selanjutnya. Penentuan nilai ambang untuk proses binerisasi menggunakan metode Otsu mampu menghasilkan bentuk citra biner yang lebih konsisten untuk setiap citra yang dimiliki[7]. Tujuan dari metode otsu adalah membagi histogram citra gray level kedalam dua daerah yang berbeda secara otomatis tanpa membutuhkan bantuan user untuk memasukkan nilai ambang. Pendekatan yang dilakukan oleh metode otsu adalah dengan melakukan analisis diskriminan yaitu menentukan suatu variabel yang dapat membedakan antara dua atau lebih kelompok yang muncul secara alami. Analisis Diskriminan akan memaksimumkan variable tersebut agar dapat membagi objek latardepan (foreground) dan
• Kebutuhan memori kecil karena nilai derajat keabuan hanya membutuhkan representasi 1 bit. • Waktu pemrosesan lebih cepat di bandingkan dengan citra hitam putih ataupun warna.
(a)
Local Thresholding
(b)
Gambar 2.4 (a) citra lena grayscale (b) citra lena biner.
3
latarbelakang (background). Nilai Ambang yang akan dicari dari suatu citra gray level dinyatakan dengan k. Nilai k berkisar antara 1 sampai dengan L, dengan nilai L = 255. 2.7
2.7.1
Relasi Dasar antar Piksel (a)
Ketetangaan (neighbors) dari suatu piksel
Gambar 2.6 (a) 4-adjacency, (b) 8-adjacency
Sebuah piksel p pada koordinat (x,y) mempunyai empat tetangga vertikal dan horisontal, dimana koordinat tersebut dinyatakan oleh: (x-1,y), (x+1,y), (x,y-1), (x,y+1).Satuan piksel ini dinamakan 4-neighbors dari p yang dinotasikan dengan N4(p). Sedangkan empat tetangga diagonal p mempunyai koordinat: (x+1,y+1), (x+1,y-1), (x1,y+1), (x-1,y-1). Satuan piksel dinamakan 8neighbors dari p, yang dinotasikan dengan ND(p). Hubungan ketetanggaan antar piksel dapat dilihat pada Gambar 2.5.
-
-
2.7.2
Adjacency, Connectivity, Region, dan Boundary
Dua buah piksel dinyatakan terhubung jika kedua piksel tersebut adalah tetangga dan tingkat keabuannya mencukupi suatu ukuran similarity (tingkat keabuannya sama). - Adjacency V merupakan satuan nilai-nilai gray-level yang digunakan untuk menggambarkan adjacency. Untuk menetapkan V perlu dipertimbangkan tiga jenis adjacency, yaitu: • 4-adjacency, dua piksel p dan q dengan nilai-nilai dari V adalah 4-adjacency jika q adalah bagian di dalam N4(p). Ilustrasi dapat dilihat pada Gambar 2.6 (a). • 8-adjacency, dua piksel p dan q dengan nilai-nilai dari V adalah 8-adjacent jika q adalah bagian di dalam N8(p). Ilustrasi dapat dilihat pada Gambar 2.6 (b).
-
Connectivity Jika S adalah subset dari suatu citra. Dua piksel p dan q dikatakan connected dalam S, jika terdapat path yang menghubungkan p dan q melalui piksel-piksel di dalam S. Untuk sembarang piksel p di dalam S, himpunan piksel yang connected dengan p di dalam S disebut connected component dari S. Jika hanya terdapat satu buah connected component, maka S disebut connected set. Region R merupakan suatu subset piksel di dalam sebuah citra yang dipanggil sebagai suatu region dari citra jika R merupakan suatu connected set. Boundary Boundary dari sebuah region R adalah satuan piksel di dalam region yang mempunyai satu atau lebih tetangga yang tidak termasuk di dalam R.
2.8
Jarak antar Piksel
Setiap piksel pada sebuah citra memiliki jarak (distance) terhadap piksel lain. Terdapat beberapa metode untuk menghitung jarak antar piksel pada citra, antara lain : • Euclidean Distance :
[
Gambar 2.5
(x, y-1) (x, y) (x, y+1)
2
]
1 2 2
De ( p, q ) = ( x − s ) + ( y − t ) •
(x-1, y-1) (x-1, y) (x-1, y+1)
(b)
(2.7)
City-Block Distance :
D4 ( p, q ) = x − s + y − t
(x+1, y-1) (x+1, y) (x+1, y+1)
•
(2.8)
ChessBoard Distance :
D8 ( p, q ) = max( x − s , y − t )
Hubungan Ketetanggaan antar Piksel
2.9
(2.9)
Eigen values dan Eigen vectors
Sebuah matriks bujur sangkar dengan orde n x n misalkan A, dan sebuah vektor kolom X. Vektor X adalah vektor dalam ruang Euclidian yang dihubungkan dengan sebuah persamaan:
AX = λX 4
Rn
(2.10)
dengan menentukan eigenvector dan eigenvalue, maka dimensinya akan berubah menjadi mxm, dimana m<
Dimana adalah suatu skalar dan X adalah vektor yang tidak nol Skalar dinamakan eigenvalue dari matriks A. Eigenvalue adalah nilai karakteristik dari suatu matriks bujur sangkar. Vektor X dalam persamaan (2.10) adalah suatu vektor yang tidak nol yang memenuhi persamaan (2.10) untuk nilai eigen yang sesuai dan disebut dengan vektor eigen. Jadi vektor X mempunyai nilai tertentu untuk nilai eigen tertentu. Sehingga X dapat dikatakan sebagai eigenvector yang berkorespondensi dengan eigenvalue
3. Perancangan Perangkat Lunak 3.1
Sistem secara umum
Perancangan proses dibutuhkan untuk mengetahui alur dalam penerapan metode yang digunakan dalam tahap implementasi. Proses utama yang diterapkan di dalam perangkat lunak dibagi menjadi dua tahap yaitu ekstraksi model dan proses pengenalan kode. Masing – masing proses terdiri atas beberapa tahap didalamnya. Dapat dilihat di Gambar 3.2 Pada Gambar 3.2 terdapat dua tahap yaitu tahap ekstraksi model dan tahap pengenalan kode. Ekstraksi model terdiri atas tiga proses, yaitu segmentasi local thresholding, ekstraksi karakter berdasarkan fitur geometri, dan penyusunan model fitur eigen. Pengenalan kode terdiri atas dua proses, yaitu pemisahan baris kode karakter, perhitungan minimal PCA reconstruction error.
2.10 Principal Component Analysis (PCA) Dalam statistika, analisis komponen utama (principal component analysis / PCA) adalah teknik yang digunakan untuk menyederhanakan suatu data, dengan cara mentransformasi linier sehingga terbentuk sistem koordinat baru dengan varians maksimum. PCA dapat digunakan untuk mereduksi dimensi suatu data tanpa mengurangi karakteristik data tersebut secara signifikan. Analisis komponen utama merupakan suatu teknik statistik untuk mengubah dari sebagian besar variabel asli yang digunakan yang saling berkorelasi satu dengan yang lainnya menjadi satu set variabel baru yang lebih kecil dan saling bebas (tidak berkorelasi lagi). Jadi analisis komponen utama berguna untuk mereduksi data, sehingga lebih mudah untuk menginterpretasikan data-data tersebut [8]. Analisis ini merupakan analisis antara dari suatu proses penelitian yang besar atau suatu awalan dari analisis berikutnya, bukan merupakan suatu analisis yang langsung berakhir. Misalnya komponen utama bisa merupakan masukan untuk regresi berganda atau analisis faktor. Dilihat secara aljabar linier, komponen utama adalah kombinasi linier-kombinasi linier tertentu dari p peubah acak x1,x2,x3,….,xm. Secara geometris kombinasi linier ini merupakan sistem koordinat baru yang didapat dari rotasi sistem semula dengan x1,x2,….,xm sebagai sumbu koordinat. Sumbu baru tersebut merupakan arah dengan variabilitas maksimum dan memberikan kovariansi yang lebih sederhana. Sumber lain merumuskan bahwa PCA merupakan teknik linier untuk memproyeksikan data vektor yang berdimesi tinggi ke vektor yang mempunyai dimensi lebih rendah [9]. PCA lebih banyak digunakan untuk keperluan ekstraksi fitur citra, dimana jumlah dimensi dari citra jauh lebih besar dibandingkan dengan jumlah data sampel yang digunakan, untuk melakukan proyeksi sampel vektor dari citra pelatihan, setiap citra pelatihan disusun dalam bentuk vektor baris. Jika jumlah data pelatihan adalah sebanyak m, maka dimensi vektornya adalah mxn. Apabila vektor citra pelatihan mempunyai dimensi mxn tersebut diortogonalisasi
Gambar 3.1 Dua tahap utama perangkat lunak
3.2 3.2.1
Tahap Ekstraksi Model Segmentasi Local Thersholding
Proses segmentasi pada Tugas Akhir ini memperhatikan tiga properti intensitas pada citra peti kemas. Pertama, karakter-karakter yang mirip satu sama lain. Kedua, besarnya intensitas kontras yang mengelilingi karakter-karakter. Ketiga, kemungkinan pencahayaan yang tidak merata pada citra peti kemas. Berdasarkan tiga observasi ini, metode Segmentasi Local Thresholding dipilih untuk mensegmentasi citra peti kemas. Metode ini dirancang berdasarkan distribusi intensitas ketetanggaan disetiap piksel pada citra. Citra grayscale peti kemas yang telah disebutkan sebelumnya menjadi input dari metode segmentasi lokal thresholding ini. Filter yang telah ditentukan ukurannya digunakan untuk memroses citra, setiap piksel yang dilalui oleh pusat filter dihitung
5
intensitas rata-rata dari piksel yang bertetangga yang masuk pada filter. Piksel tersebut diklasifikasi sebagai foreground, jika intensitasnya lebih kecil dari c persen dari rata-rata intensitas, dan sebaliknya diklasifikasi sebagai background. Piksel yang termasuk foreground disebut sebagai FG. Ukuran filter yang dijalankan pada citra ditentukan sebasar 1/30 dari lebar citra input dan besarnya c adalah 0.08. Kriteria thresholding ini hanya cocok untuk citra peti kemas dengan daerah kode peti kemas lebih gelap dari daerah sekitarnya. Kesalahan segmentasi dapat terjadi karena kesalahan klasifikasi ketika kode peti kemas dibaca sebagai background. Oleh sebab itu, perlu dibuat sebuah strategi pengecekan untuk mencegah hal ini. Pertama kali yang dilakuan yaitu melakukan segmentasi dengan metode Otsu [7] pada citra grayscale peti kemas dan membaginya kedalam dua cluster piksel C1 dan C2. Karena peti kemas melingkupi sebagian besar citra, maka dimasukkan kedalam cluster yang lebih besar (diasumsikan C1). Disamping itu, karakter-karakter kode dimasukkan kedalam cluster C2 karena memiliki perbedaan intensitas kontras dengan sekitarnya. Secara berurutan, dihitung intensitas rata-rata dari citra grayscale untuk C1 dan C2. Error terdeteksi pada segmentasi lokal jika intensitas rata-rata FG dan C1 lebih kecil dari FG atau C2. Sehingga harus mengubah kriteria dan memproses citra lagi. Kriteria dirubah menjadi piksel dengan rata-rata intensitasnya lebih besar dari tetangganya diklasifikasikan sebagai foreground, dan sebaliknya diklasifikasikan menjadi background. Dengan proses pengecekan ini, akan didapatkan hasil segmentasi karakter-karakter kode peti kemas baik hitam maupun putih. Alur segmentasi local thresholding dijelaskan pada Gambar 3.2.
3.2.2
Mulai
Citra Grayscale Peti Kemas, WS = w/30, c
Memfilter Citra dengan Blok Filter
Ubah Kriteria Background dan Foreground
Tidak
Inisialisasi Blok Filter dengan tipe ‘Average’ berukuran WS
Binerisasi Citra Hasil Filter
Luas Daerah Hitam > Luas Daerah Putih
Ya
Citra Biner Peti Kemas
Selesai
Gambar 3.2 Diagram alir segmentasi Local Thresholding
kan properti geometri yang dimiliki oleh karakterkarakter kode peti kemas, seperti lebar, tinggi, keliling, dan luas. Jika nilai dari parameter suatu
daerah diluar rentang yang diperkirakan secara empiris, maka bukan termasuk daerah kode, sebaliknya termasuk daerah kode peti kemas. Untuk mengambil area karakter kode, maka dirancang algoritma grouping berdasarkan jarak (distance-based grouping). Untuk menghitung jarak antar piksel, digunakan jarak Euclidean. Berikut langkah – langkah algoritma distancebased grouping : 1. Beri label FALSE semua region dan set status groupingnya UNGROUP. 2. Set TRUE suatu region yang berlabel FALSE. 3. Jika ada region berlabel FALSE memenuhi aturan sebagai berikut: 4. Jika ada non-zero piksel dalam region yang memiliki jarak Euclidean dengan non-zero piksel lain kurang dari 25 piksel, maka daerah yang diperiksa diberi label sebagai TRUE. 5. Ulangi langkah 3 sampai tidak ada lagi daerah TRUE ditemukan. 6. Kelompokkan region TRUE & UNGROUP, dan set status groupingnya GROUP. 7. Ulangi langkah 2 sampai tidak ada region yang dapat dikelompokkan lagi.
Ekstraksi Karakter Berdasarkan Fitur Geometri
Hasil segmentasi merupakan citra biner berupa daerah hitam (0) dan putih (1) dari citra peti kemas. Daerah hitam inilah yang nantinya akan digunakan untuk menemukan area kode peti kemas. Bagian-bagian peti kemas seperti pintu dan logo pemilik cenderung lebih mendominasi daerah hitam yang bercampur dengan area kode peti kemas. Untuk menentukan daerah hitam tersebut termasuk area kode peti kemas atau tidak berdasar-
Setelah dilakukan proses grouping, maka akan dihasilkan beberapa group, group yang merupakan area kode peti kemas adalah group yang memiliki lebar terbesar diantara group-group yang lain. Alur ekstraksi karakter berdasarkan fitur geometri dijelaskan pada Gambar 3.3. Alur algoritma distance-based grouping dijelaskan pada Gambar 3.4.
6
model, citra biner hasil segmentasi dipisah satu sama lain untuk menghilangkan perbedaan pose. Hasil pemisahan antar karakter berfungsi sebagai sampel training yang berukuran 24x42 piksel, dinotasikan sebagai X = (x1, x2, ... , xi, xm-1, xm) dimana m merupakan jumlah sampel training. Setiap sampel training xi direpresentasikan sebagai vector satu dimensi (x1, x2, ..., xj, ..., xn-1, xn)T, dimana xj merupakan nilai intensitas piksel ke-j pada sampel training dan n meruapakan jumlah piksel. Kemudian m sampel dirata-rata sampel untuk memperoleh nilai mean vector x , selanjutnya menghitung matrik kovarian C yang mengimplikasikan variansi setiap sampel training dengan mean vector. Dengan C diketahui dari persamaan:
Mulai
Citra Biner Peti Kemas
Pelabelan Piksel yang Terhubung
N=1
Pengecekan Fitur Geometri Region Piksel N
N=N+1
67 ≤ luas ≤ 720 5 ≤ lebar ≤ 30 21 ≤ tinggi ≤ 37
Tidak
Filter Out Region Piksel
Tidak
(3.1)
Ya Filter In Region Piksel
N = Total Region ?
Ya
Sehingga akan ditemukan eigenvalues (v1, v2, ... , vi, ... , vn-1, vn ) dan eigenvector (u1, u2, ... , ui, ... , un-1, un) dari matrik kovarian. Kemudian, eigenvalue disusun dengan urutan terbesar sampai terkecil. Akhirnya, akan didapatkan fitur eigen yang dikarakterisasikan dengan meanvector dan eigenvector yang dapat digunakan pada tahap pengenalan kode peti kemas. Pada Tugas Akhir ini set fitur eigen dibedakan antara sampel training untuk karakter huruf dan karakter angka, sehingga terdapat dua set fitur eigen untuk karakter huruf dan karakter angka. Hal ini dilakukan untuk mempermudah pengenalan kode peti kemas yang memiliki ketentuan khusus. Alur penyusunan model fitur eigen dijelaskan pada Gambar 3.5 dan 3.6.
Hasil Ekstraksi Region Piksel yang terdeteksi sebagai Kode Peti Kemas
Selesai
Gambar 3.3 Diagram alir ekstraksi karakter berdasarkan fitur geometri
Mulai
Citra Biner Hasil Ekstraksi Karakter
Untuk Semua Region : Label Region = FALSE, Grouping Status = UNGROUP
Mulai
Set Arbitary FALSE Region = TRUE
Tidak
Cek Region lain yang berlabel FALSE
Jarak Euclidean ≤ 25
UNGROUP = 0
Ya
Area Karakter Kode Peti Kemas
Area Kode = Group dengan Lebar Terbesar
UNGROUP = UNGROUP – 1
Ya
Set Label Region Cek = TRUE
Kelompokkan Region True & Ungroup. Set Groupig Status = GROUP
Pelabelan Karakter Kode
Area Kode Karakter Peti Kemas
Selesai
3.2.3
Set m Sampel Training Karakter Angka (24x42 piksel)
Set m Sampel Training Karakter Huruf (24x42 piksel)
Gambar 3.4 Diagram alir algoritma distance-based grouping
Penyusunan Fitur Eigen X = (x1, x2, ... , xi, xm-1, xm) x = (x1, x2, ..., xj, ..., xn-1, xn)T
Degan menggunakan metode Segmentasi Local Thresholding, area karakter kode peti kemas secara otomatis dapat diekstrak dari citra peti kemas. Untuk setiap karakter huruf dan angka disusun model fitur eigen berdasarkan PCA untuk mengkarakterisasi variasi kemunculannya pada citra training yang berbeda. Pada proses kontruksi
1
Gambar 3.5 Diagram alir penyusunan model fitur eigen (1)
7
1
Mulai Matriks Kovarian Sampel Training Karakter Huruf
Matriks Kovarian Sampel Training Karakter Angka
Eigenvalues dan Eigenvectors Sampel Training Karakter Huruf
Eigenvalues dan Eigenvectors Sampel Training Karakter Angka
Citra Biner Area Kode Peti Kemas
Find Selang Baris Piksel Hitam antara Area Kode ?
Tidak
Rotasi Area kode sebesar α
Ya
Set Fitur Eigen Sampel Traning Karakter Angka (meanvector dan eigenvector)
Set Fitur Eigen Sampel Traning Karakter Huruf (meanvector dan eigenvector)
Selesai
Gambar 3.7 Diagram alir pemisahan baris kode karakter
perpotongan tegak lurus antara koordinat karakter pertama dan karakter terkahir pada baris pertama. Sedangkan merupakan besar sudut rotasi yang dicari. Alur pemisahan baris kode karakter peti kemas dijelaskan pada Gambar 3.7.
Finish
Gambar 3.6 Diagram alir penyusunan model fitur eigen (2)
3.3 3.3.1
Baris 1 = Area Piksel Diatas Selang Baris Piksel Hitam, Baris 2 = Area Piksel Dibawah Selang Baris Piksel Hitam
Jumlah Baris Pengecekan = Jumlah Baris Input
Sort Desc Eigenvalue
Tahap Pengenalan Kode
3.3.2
Pemisahan Baris Kode Karakter
Kode peti kemas memiliki urutan tertentu dalam penyusunannya. Susunan karakter kode peti kemas memiliki arti yang dapat kita ketahui. Pembahasan arti kode peti kemas telah dijelaskan pada Bab 2. Untuk mengenali kode peti kemas, perlu ditekankan bagaimana urutan pengenalan kode peti kemas itu sendiri. Sehingga, digunakan metode pemisahan baris kode peti kemas agar proses pengenalan dapat berjalan sesuai yang diharapkan. Pada koleksi citra peti kemas, kode peti kemas terdiri dari dua baris dimana proses pembacaannya dilakukan dari kiri ke kakanan. Jika pada proses pemisahan baris kode ini terdapat kesalahan, yaitu hanya dapat mendeteksi satu baris saja. Maka, perlu dilakukan strategi rotasi area kode peti kemas. Hal ini perlu dilakukan karena untuk melakukan proses pengenalan diperlukan masukan berupa dua baris kode peti kemas. Kesalahan tersebut dapat terjadi jika perangkat lunak tidak dapat mencari selang pemisah antarabaris pertama dan baris kedua. Strategi rotasi area kode peti kemas dilakukan dengan cara mendeteksi sudut kemiringan antara karakter pertama dan karakter terakhir pada baris pertama menggunakan aturan cosinus. Rotasi dilakukan dengan arah berlawanan arah jarum jam dengan besar sudut rotasi diketahui pada persamaan 3.2.
Pengenalan Karakter Kode dengan Minimal PCA Reconstruction Error
Pada tahap ini, pertama kali yang dilakukan adalah memisahkan karakter-karakter pada area kode peti kemas. Karakter-karakter yang telah dipisah dan tidak diketahui, masing-masing secara berurutan dibandingkan dengan semua fitur eigen, dan dikenali dengan menemukan model terbaik yang cocok dengan Minimal PCA Reconstruction Error. Detail dari algoritma pengenalan kode karakter sebagai berikut : •
Langkah – Langkah – Langkah 1. Input unknown karakter Cunknown dan set fitur eigen. – Langkah 2. Pilih Eigen-feature dan proyeksikan vektor karakter Cunknown
(3.3)
–
Langkah 3. Rekonstruk melalui proses proyeksi
karakter
(3.4)
(3.2)
– Variable a,b, dan c merupakan panjang sisi pada sebuah segitiga yang dibentuk dari tiga titik, yaitu: koordinat karakter pertama, koordinat karakter terakhir pada baris pertama dan koordinat
–
8
Langkah 4. Hitung reconstruction error Langkah 5. Simpan nilai error dan kembali ke langkah 2 sampai semua karakter yang tidak diketahui
dibandingkan dengan semua template training berdasarkan model fitur eigen. – Langkah 6. Pilih karakter dengan reconstruction error minimal sebagai hasil pengenalan Cunknown Pencarian minimal PCA ercontruction error dilakukan pada setiap karakter yang didak diketahui dari input citra peti kemas terhadap semua sampel training beserta fitur eigen yang dibuat pada proses sebelumnya. Proses pengenalan dapat berjalan lebih akurat karena pengecekan terhadap karakter huruf dan angka dilakukan pada sampel training yang berbeda. Alur Pengenalan Karakter Kode dengan Minimal PCA Reconstruction Error dijelaskan pada Gambar 3.8.
Mulai
Baris Kode Peti Kemas, Model Fitur Eigen Karakter Abjad dan Numerik
Baris = 1, Karakter Dikenali = “”
Pelabelan Piksel Baris
Find Karakter Cocok = Minimal PCA Reconstruction Error Tidak
4. Uji Coba dan Analisa 4.1
Karakter Dikenali = Karakter Dikenali + Karakter Cocok
Skenario Uji Coba
Pada bagian ini dijelaskan mengenai skenario uji coba yang akan dilakukan untuk mengetahui kemampuan perangkat lunak dalam mengenali kode peti kemas. Terdapat dua skenario untuk menguji sistem, antara lain: 1. Uji coba konstruksi model citra peti kemas. 2. Uji coba pengenalan kode peti kemas beserta akurasi keberhasilan pengenalan kode perkarakter.
4.1.1
Karakter Unknown = 1
Baris = Baris + 1
End Of Kode Peti Kemas ?
Ya
End Of Baris ?
Tidak
Karakter Unknown = Karakter Unknown + 1
Ya
Set Karakter Dikenali
Selesai
Gambar 4.1 Diagram alir pengenalan karakter kode dengan MinimalPCA Reconstruction Error
Uji Coba Konstruksi Model
hasilkan area yang berupa karakter kode peti kemas.
Uji coba konstruksi model berguna untuk mengetahui tingkat keberhasilan perangkat lunak dalam menghasilkan area kode peti kemas berupa lima baris karakter huruf dan angka. Untuk mendapatkan lima belas karakter tersebut, konstruksi model melalui dua proses utama, yaitu proses segmentasi Local Threshoding dan proses ekstraksi karakter berdasarkan fitur geometri. Pada proses segmentasi local thresholding ditentukan oleh dua parameter utama yang berlaku untuk semua data uji coba[1]. Parameter pertama merupakan ukuran filter yang ditentukan sebesar w/30, w adalah lebar dari citra peti kemas. Parameter kedua merupakan konstanta c yang ditentukan sebasar 0.08. Secara kualitatif dapat diukur tingkat keberhasilan perangkat lunak dalam memperoleh area kode peti kemas. Hasil uji coba konstruksi model dapat dilihat pada Tabel 5.1. Hasil uji coba yang ditampilkan adalah tujuh citra peti kemas dan hasil konstruksi modelnya. Dari hasil uji coba konstruksi model terhadap data uji, secara kualitatif dapat digolongkan pada hasil yang bagus. Hal ini dikarenakan, dari seluruh uji coba semuanya meng-
4.1.2
Uji Coba Pengenalan Kode
Uji coba pengenalan kode bertujuan untuk mengetahui tingkat keberhasilan perangkat lunak dalam membaca karakter kode peti kemas. Secara kuantitatif dapat diukur tingkat akurasi keberhasilan pengenalan kode karakter. Tingkat akurasi keberhasilan diukur dengan Recognition Success Rate (RSR). RSR merupakan prosentase keberhasilan pengenalan kode peti kemas per karakter dari karakter huruf A-Z dan angka 0-9. Misalnya, karakter ‘G’ pada data uji terdapat sebanyak 59 karakter, dan jumlah yang berhasil dikenali adalah sebanyak 58 karakter. Maka, RSR untuk karakter ‘G’ adalah 58/59 atau 98.31%. Salah satu hasil pengenalan kode dapat dilihat pada Gambar 4.1. Keseluruhan hasil pengenalan kode untuk lima puluh empat data uji lainnya dapat dilihat pada Lampiran 2 buku Tugas Akhir. Hasil RSR dari seluruh data uji coba dapat dilihat pada Tabel 4.2. Data RSR pada Tabel 4.2 menunjukkan prosentase akurasi pengenalan kode peti kemas per karakter. Prosentase akurasi pengenalan kode peti
9
kemas untuk masing-masing karakter huruf dan angka diatas 95 %. Nilai rata-rata RSR dari hasil percobaan pengenalan kode adalah 99.78 %. Hal ini menunjukkan bahwa perangkat lunak memiliki akurasi yang tinggi untuk mengenali kode peti kemas.
4.2 4.2.1
2.
Adapun saran yang ingin disampaikan untuk pengembangan lebih lanjut dari Tugas Akhir ini, antara lain: 1. Untuk meningkatkan akurasi, dibutuhkan jumlah karakter training yang semakin beragam untuk setiap karakter huruf dan angka. 2. Penerapan proses pengenalan kode atau karakter dari sebuah citra dapat lebih dikembangkan, baik dari sisi citra yang semakin beraneka ragam maupun fungsi pengenalan kode atau karakter yang semakin luas.
Analisa Uji Coba Analisa Uji Coba Konstruksi Model
Pada uji coba konstruksi model, uji coba dilakukan pada lima puluh lima citra peti kemas. Tujuan uji coba ini untuk memperoleh ekstraksi area kode peti kemas. Dari hasil uji coba, secara kualitatif dapat diukur tingkat keberhasilan perangkat lunak dalam menghasilkan area kode peti kemas melalui proses kontruksi model. Dari lima puluh lima citra input, dapat dihasilkan area kode peti kemas dengan baik berupa citra biner area kode. Tingkat keberhasilan pendeteksi area kode peti kemas ini akan mempertinggi kemungkinan pengenalan kode peti kemas pada proses selanjutnya.
4.2.2
geometri yang diterapkan, maka area kode peti kemas yang diperoleh semakin bagus. Pengenalan kode peti kemas menggunakan model fitur eigen memiliki akurasi yang baik (99.78%).
Tabel 4.1 Hasil uji coba konstruksi model citra peti kemas No Citra Peti Kemas Hasil Konstruksi Model 1
Analisa Uji Coba Pengenalan Kode
Pada uji coba pengenalan kode, proses pengenalan kode dilakukan pada citra biner hasil ekstraksi area kode peti kemas pada tahap konstruksi model. Tujuan uji coba ini untuk mengenali karakter yang merupakan kode peti kemas. Dari hasil uji coba, secara kuantitatif dapat diukur tingkat keberhasilan perangkat lunak dalam mengenali karakter kode peti kemas. Data hasil uji coba disajikan pada Tabel 4.2 berupa Recognition Success Rate (RSR) per karakter huruf A-Z dan angka 0-9. Data RSR menujukkan nilai rata-rata RSR 99.78 %. Data tersebut berarti perangkat lunak memiliki akurasi yang sangat tinggi dalam mengenali karakter kode peti kemas. Kesalahan pengenalan terjadi pada pengenalan karakter huruf ‘G’ yang dikenali sebagai karakter ‘C’, dan karakter angka ‘9’ yang dikenali sebagai karakter ‘8’. Kesalahan pengenalan ini hanya terjadi satu kali dari 59 kali kemunculan karakter huruf ‘G’, dan satu kali dari 32 kali kemunculan karakter angka ‘9’.
2
3
4
5
5. Kesimpulan dan Saran
6
Berdasarkan aplikasi yang telah dibuat beserta uji coba yang telah dilakukan, maka dapat ditarik kesimpulan sebagai berikut. 1. Proses konstruksi model dipengaruhi oleh hasil segmentasi citra, dan nilai-nilai dari fitur geometri yang dimiliki karakter kode pada peti kemas. Semakin baik hasil segmentasi dan semakin spesifik fitur
7
10
Tabel 4.2 Recognition Success Rate (RSR) per Karakter Jumlah
Karakter
Jumlah yang Berhasil
RSR
Kemunculan
Dikenali
A
5
5
100 %
B
3
3
100 %
C
10
10
100 %
D
0
0
-
E
1
1
100 %
F
2
2
100 %
G
59
58
98.31 %
H
3
3
100 %
I
3
3
100 %
J
0
0
-
K
10
10
100 %
L
26
26
100 %
M
24
24
100 %
N
1
1
100 %
O
35
35
100 %
P
0
0
-
Gambar 4.1 Hasil Pengenalan Kode
6. Daftar Pustaka [1]
[2]
Q
0
0
-
R
2
2
100 %
[3]
S
15
15
100 %
[4]
T
4
4
100 %
U
56
56
100 %
V
0
0
-
W
2
2
100 %
X
0
0
-
Y
9
9
100 %
Z
5
5
100 %
0
40
40
100 %
1
103
103
100 %
2
121
121
100 %
3
39
39
100 %
4
68
68
100 %
5
42
42
100 %
6
27
27
100 %
7
42
42
100 %
8
36
36
100 %
9 Ratarata RSR
32
31
96.88 %
[5]
[6]
[7]
[8]
[9]
99.78 %
11
Chen, H.C., Chen, C.K., Hsu, F.Y., Lin, Y.S., Wu, Y.T. Sun, Y.N., “A Computer Vision System for Automated Container Code Recognition”, Directory of Open Journal, vol. 2188, pp. 470-474. 2011. Container Handbook: Cargo loss prevention information from German marine insurers, ch. 3.4. [Online]. Available:http://www.containerhandbuch.de /chb_e/stra/index.html?/chb_e/stra/stra_03_ 04_00.html Linda G. Shapiro and George C. Stockman. Computer Vision. Prentice Hall. 2001. E. Roy Davies. Machine Vision : Theory, Algorithms, Practicalities. Morgan Kaufmann. 2005 Munir Rinaldi. Pengolahan Citra Digital dengan Pendekatan Algoritmik. Informatika Bandung. 2004. Rafael C. Gonzalez and Richard E. Woods. Digital Image Processing. 2nd ed. Prentice Hall. 2002. Nobuyuki Otsu. A threshold selection method from gray-level histograms. IEEE Trans. Sys., Man., Cyber. 9: 62–66. 1979. Johnson R. A & Wichern D. W, Apllied Multivariate Statistical Analysis, Prentice Hall Inc, New York, 1982 M. Turk and A. Pentland, “Face recognition using eigenfaces” Proc. IEEE Conference on Computer Vision and Pattern Recognition, Maui, Hawaii, 1991.
