Kode / Nama Rumpun Ilmu : 458 / Teknik Informatika
LAPORAN KEMAJUAN PENELITIAN DISERTASI DOKTOR
PELACAKAN OBYEK BERGERAK (MOTION TRACKING) PADA VIDEO TAGGING BERBASIS PEMBELAJARAN TIDAK TERBIMBING MENGGUNAKAN METODE KLASTERING
PENGUSUL Moch Arief Soeleman, M.Kom. NIDN: 0628027101
UNIVERSITAS DIAN NUSWANTORO SEMARANG JUNI 2015
1
2
DAFTAR ISI
RINGKASAN................................................................................................
4
BAB I. PENDAHULUAN............................................................................
5
BAB II. TINJAUAN PUSTAKA...............................................................
9
BAB III TUJUAN DAN MANFAAT PENELITIAN ...............................
25
BAB IV METODE PENELITIAN............................................................
26
BAB V HASIL DAN PEMBAHASAN ………………………………
32
BAB VI RENCANA TAHAPAN BERIKUTNYA....................................
36
BAB VII KESIMPULAN............................................................................
37
DAFTAR PUSTAKA................................................................................
38
LAMPIRAN................................................................................................
41
Lampiran 1. Draft Paper
3
ABSTRAKSI Pesatnya pertumbuhan dan perkembangan dari teknologi digital serta ketersediaan pada peralatan berbasis video seperti kamera digital, telepon bergerak dengan kamera, menyebabkan terjadinya peningkatan secara cepat dalam perangkat penyimpanan, jaringan dan teknik kompresi dalam sekala besar. Dampaknya diperlukan teknologi yang dapat menyimpan secara efisien untuk data video. HEVC sebagai teknologi kompresi baru berbasis efisiensi video coding diharapkan menajdi kompresi data video terbaik dari segi efisiensi ukuran penyimpanan. Sebagai pembanding kompresi standar H.264/MPEG-4 AVC pada level kualitas video yang sama. HEVC mendukung 8K UHD dan ukuran resolusi hingga 8192 x 4320 piksel. Video object tagging sebagai riset dalam video pelabelan otomatis untuk video surveilance menjadi bagian dari aplikasi video intelligent system dan interaksi manusia dan komputer. Secara konseptual video object tagging merupakan proses pemberian label pada obyek bergerak khususnya di video yang bertujuan untuk membantu efisiensi dalam pencarian, klasifikasi atau pengenalan objek pada video. Pada riset ini, dikembangkan framework untuk menuju sistem video object tagging khususnya pada motion tracking berbasis unsupervised learning dengan menggunakan metode clustering. Pada tahapan ini akan dilakukan proses tracking, ektraksi objek dan proses pelabelan. Tujuan utama yang akan dicapai pada penelitian ini mendukung terbangunnya model framework proses video object tagging pada video surveilance. Metode yang dilakukan dalam penelitian ini dalam membangun framework video object tagging meliputi proses deteksi, tracking, ekstraksi fitur dan pelabelan. Pendeteksian obyek bergerak yang akan dilakukan dengan background subtraction, selanjutnya proses clustering digunakan untuk melakukan proses segmentasi fitur dengan menggunakan fuzzy c-means clustering. Dengan mencapai keberhasilan tracking dan segmentasi obyek bergerak maka akan didapatkan obyek yang akan diberikan pelabelan secara otomatis untuk pengenalan obyek dalam video surveilance. Penelitian video object tagging diharapkan menjadi penelitian pelopor dalam bidang video object yang semakin berkembang pesat. Keywords: Video tagging, Tracking, clustering, segmentasi.
4
BAB I PENDAHULUAN
1.1
Latar Belakang
Pesatnya pertumbuhan dan perkembangan dari teknologi digital serta ketersediaan pada peralatan berbasis video capture seperti kamera digital, telepon bergerak dengan kamera, menyebabkan terjadinya peningkatan secara cepat dalam perangkat penyimpanan, jaringan dan teknik kompresi dalam sekala besar. Awal pengembangan teknik kompresi video telah didominasi oleh keinginan untuk memaksimalkan kemampuan kompresi. Data video asli yang ukurannya terlalu besar diharapkan dapat disimpan ke dalam ukuran file yang cukup kecil. Selain itu, aspek lain yang perlu dipertimbangkan adalah seberapa besar data yang hilang akibat proses kompresi. Standar kompresi video yang paling sukses dan masih digunakan sampai saat ini yaitu H.262/MPEG-2 Video (1994) dan H.264/MPEG-4 AVC (1999). Keduanya dikembangkan oleh dua lembaga standarisasi internasional (joint project), yaitu ITU-T dan ISO/IEC. Saat ini, standar kompresi video terbaru yang dikenal sebagai High Efficiency Video Coding (HEVC). HEVC mampu menggandakan rasio kompresi data video jika dibandingkan kompresi standar H.264/MPEG-4 AVC pada level kualitas video yang sama. HEVC mendukung 8K UHD dan ukuran resolusi hingga 8192 x 4320 piksel. Beberapa ekstensi HEVC yang masuk dalam daftar pengembangan, meliputi ekstensi jangkauan (mendukung format video yang kualitasnya ditingkatkan), ekstensi coding yang scalable, serta ekstensi video 3D. Dari banyak keunggulan yang dimiliki, HEVC menentukan fase baru dalam hal teknologi kompresi yang ditargetkan
untuk
meningkatkan
pengalaman
pengguna
dalam
efisensi
penyimpanan data. HEVC sangat efisien mengatasi dari rendah ke resolusi sangat tinggi, sehingga dapat mendukung berbagai macam display yang baru. 5
Studi yang mempelajari tentang tagging pada sekumpulan data set besar dari konsep semantic untuk data video merupakan harapan untuk menjembatani gap yang ada [1],[2],[3],[4]. Menurut Hauptmann [1] semantic gap antara low-level fitur dan informasi ke user dimasukkan ke dalam 2 kelompok gap, pertama pemetaan lowlevel fitur ke tingkat menengah konsep semantic, kedua pemetaan konsep tersebut ke dalam kebutuhan user. Annotation atau tagging memastikan langkah untuk menyelesaikan ke pendekatan low-level. Video annotation secara otomatis juga di kenal dengan nama “video concept detection” [5], “video semantic analysis” [6] atau “high level feature extraction” [7]. Umumnya seperti diketahui bahwa metode labeling dalam gambar dapat dilakukan secara otomatis atau semi-otomatis. Terakhir kali, metode-metode dalam membantu untuk proses otomatis menghasilkan sekumpulan dari semantic label berbasis gambar pada konten visual diantaranya [8],[9],[10],[11],[12], metode ini pertama melakukan ekstraksi low-level feature pada citra gambar dan membuat sebuah matematika model untuk menghubungkan low-level isi citra gambar sehingga disebut dengan metode content based image tagging (CBIT) Dari hasil penelitian terdahulu tersebut mendorong peneliti dalam melakukan teknik automatic image annotation yang memfokuskan pada penandaan teks secara otomatis pada citra gambar sehingga citra gambar tersebut menjgap adi kunci pencarian. Tagging secara otomatis dapat dilakukan melalui ekstraksi beberapa feature dari sebuah citra gambar. Dari pemetaan feature tersebut akan dijadikan dalam kunci penulisan teks. Secara umum pemanfaatan fitur dapat dikelompokkan pada warna, texture dan bentuk. Beberapa tahun terakhir, tagging pada video mengalami kemajuan cukup signifikan. Beberapa usulan untuk pendekatan dalam video tagging, diantaranya seperti semi-suppervised learning [14],[15],[16], active learning [17,18], multiinstance learning [19] dan multi-label learning [20], ke semua metode telah berhasil meningkatkan performance dalam area masing-masing. Pada metode supervised, model dari konsep semantic dibangun melalui sekumpulan pelatihan penamaan, dan ketika ada penamaan sampel baru dapat diprediksi melalui model pembelajar. Sedangkan semi-supervised learning dan active learning merupakan dua pendekatan untuk mengatasi kesulitan pada data pelatihan yang tidak mencukupi pada model supervised. Metode Semi-supervised learning mengekploitasi unlabeled data dengan asumsi yang pasti dan memiliki keyakinan untuk 6
membangun model yang lebih akurat dibanding yang sudah dicapai pada model supervised. Problem dari semantic video object tagging berkaitan kuat dengan problem dasar pada visual categorization, seperti klasifikasi dari obyek lebih dari pengenalan sebuah spesifik kelass dari obyek. Dari semua problem tersebut, problem dari semantic video tagging yang belum dilakukan dalam penelitian adalah pembahasan untuk mengenali obyek saat obyek bergerak. Untuk mencapai kondisi yang efektif dari perubahan yang tampak maka fitur-fitur obyek harus dapat dikenali dalam video obyek tagging.
1.2
Permasalahan
Beberapa permasalahan yang akan menjadi fokus penelitian motion tracking pada video object tagging sebagai berikut : a. Bagaimana melakukan tracking pada motion obyek bergerak
berbasis
background subtraction b. Bagaimana melakukan ekstraksi terhadap obyek bergerak dengan menggunakan metode klastering secara otomatis. c. Bagaimana melakukan pengenalan obyek bergerak pada video untuk mendukung proses video tagging berbasis unsupervised untuk menyelesaikan problem video object tagging.
1.3
Tujuan Khusus
Adapun tujuan penelitian sebagai berikut : a. Menyelesaikan problem tracking dengan metode clustering pada obyek bergerak . b. Menyelesaikan problem dalam melakukan ektraksi fitur pada obyek bergerak untuk video object tagging. c. Menyelesaikan problem dalam mengenali semantic video object tagging pada video surveilance
1.4
Keutamaan Penelitian a. Dibentuk sebuah model untuk tracking obyek bergerak dengan metode clustering b. Dikembangkan sebuah sistem untuk ekstraksi obyek bergerak untuk video objek tagging berbasis clustering. 7
c. Dikembangkannya sebuah sistem untuk video obyek tagging
untuk
mengenali / pelabelan obyek dalam sistem video surveillance.
1.5
Keterkaitan Penelitian dengan Penyelesaian Disertasi
Keterkaitan penelitian yang akan dilakukan terhadap penyelesaian disertasi adalah merupakan penelitian orisinalitas dan penemuan baru dalam penggunaan model video object tagging pada video surveilance. Motion tracking pada obyek bergerak pada video yang nantinya dalam penyelesaian disertasi akan digabung menjadi sebuah teknik untuk melakukan pengenalan dari hasil pelacakan obyek bergerak dalam video. Tahapan yang dilakukan dalam penelitian ini ada 2 tahap dari 4 tahap yang akan dilakukan untuk penyelesaian disertasi. Dua tahap yang dilakukan pada penelitian ini merupakan langkah ketiga dan keempat dari penyelesaian disertasi. Hasil akhir tahap ketiga dalam video obyek tagging adalah melakukan ekstraksi obyek bergerak, hasil ekstraksi diharapkan menjadi referensi untuk mengenali dalam proses pelabelan. Hasil akhir tahap keempat adalah proses mengenali dari obyek yang telah diekstraksi untuk pelabelan pada video object tagging. 1.6
Luaran Penelitian
Luaran yang akan ditargetkan pada Penelitian Disertasi Doktor ini adalah: a.
Disertasi (draft disertasi) yang telah disetujui Pembimbing / Promotor dan
Co-promotor. b.
Publikasi ilmiah dalam jurnal bereputasi internasional yang terindek
SCOPUS
1.7
Kontribusi terhadap perkembangan IPTEKS
Penelitian ini berkontribusi terhadap pengembangan Ipteks antara lain : 1.
Dihasilkan metode baru dalam melakukan tracking obyek bergerak dalam
video untuk video surveilance. 2.
Dihasilkan metode yang lebih baik dalam dalam melakukan ekstraksi
terhadap obyek bergerak pada video terkompresi. 3.
Dihasilkan framework / model baru untuk video object tagging berbasis
unsupervised clsutering untuk menyelesaikan problem object tagging 8
BAB II TINJAUAN PUSTAKA
2.1
Video Tagging
Konsep video annotation atau tagging berhubungan dengan istilah pada “video concept detection” [5], “video semantic analysis” [6] atau “high level feature extraction” [7], dapat diselesaikan dengan metode pembelajaran mesin. Video tagging merupakan sebuah pendekatan atau proses dari merubah dari konten visual ke dalam sekumpulan dari kata-kata tekstual untuk mendiskripsikan semantik yang terkandung dalam video untuk memudahkan pencarian pada isi terkandung. Pada umumnya sebuah video tagging memiliki alur berikut, pertama video dilakukan segmentasi ke dalam unit-unit yang pendek seperti shot dan sub-shots. Kemudian low-level fitur dilakukan ektraksi dari tiap-tiap unit untuk dideskripsikan isinya. Video tagging kemudian di tetapkan untuk membelajarkan sekumpulan konsep standar dari setiap unit berdasarkan pada low-level fitur. The National Institute of Standars and Technology (NIST) telah membuktikan dalam “high level feature extraction” dalam sebuah TREC video retrieval evaluation (TRECVID) [6], [7], yang memberikan kontribusi untuk menyediakan dalam evaluasi teknologi video tagging.. 2.2
Digital Video
Digital video adalah representasi diskrit gambar dunia nyata dalam spasial dan domain temporal. Dalam sampel temporal domain biasanya jumlah frame per detik pada tingkat 20, 25, atau 30 frame per detik . Setiap frame video gambar diam terdiri atas piksel dibatasi oleh dimensi ruang . Pada umumnya domain video spasial resolusi berkisar 1280 x 720 ( HD ) atau 1920 x 1080 ( Full HD ) pixel. . 9
Sebuah pixel memiliki satu atau lebih komponen sesuai dengan warna ruang, umumnya ruang warna RGBdan YCrCb. Ruang warna RGB menggambarkan proporsi relatif merah, biru, dan hijau di sebuah pixel. Komponen RGB umumnya diukur dalam kisaran 0-255 , yaitu 8 bit untuk masing-masing komponen dan 24 bit secara total. YCrCb ruang warna dikembangkan dengan sistem visual manusia 2.3.
Supervised Learning
Untuk melakukan proses video tagging, metode yang paling banyak dilakukan dengan menerapkan algoritma pembelajaran terbimbing, dimana yang pertama dilakukan dengan melakukan pelatihan secara di supervisi, kemudian melakukan membangun model untuk konsep yang diberikan selama pelatihan dan memberikan label dari sampel tetap kemudian disimpulkan berdasarkan pada model. Metode pembelajaran terbimbing dapat dikelompokkan ke dalam dua kategori [6], yaitu generative methods dan discriminative methods. Dalam motode generative, kondisi kelas probabilitas distribusi kepadataan
merupakan yang pertama di estimasi
kemudian kelas probabilitas diperoleh menurut aturan bayes. Sedangkan untuk metode diskriminatif, kelas probabilitas dimodelkan secara langsung tanpa mengestimasi probabilitas kepadatan.
2.4 Deteksi Pergerakan Objek Deteksi pergerakan objek dalam urutan video merupakan langkah paling awal untuk dapat melakukan ekstraksi informasi dalam beberapa area visi komputer seperti video pengamatan, monitoring trafik dan tracking manusia serta video tagging. Beberapa tugas dalam video melibatkan deteksi keberadaan dari sebuah objek dalam sebuah urutan gambar dan lokasi untuk pengenalan yang lebih presisi. Beberapa metode telah diusulkan oleh beberapa peneliti untuk deteksi objek dalam video surveillance berbasis [36]. Deteksi objek dapat dibagi sedikitnya dalam 5 pendekatan seperti frame difference [31], background subtraction [35], optical flow [33], ekastraksi warna kulit [38] dan pendekatan berbasis probabilitas [36]. Pada penelitian yang lain (Staufer & Grimson) mengusulkan sebuah metode Gausian mixture model berbasis pada background model untuk mendeteksi objek. Lipton et., al [36] mengusulkan metode frame difference yang digunakan pada pixel-wise differences antara
dua frame gambar untuk mengekstraksi daerah pergerakan.
Penelitian [34] mengusulkan sebuah kombinasi dari background subtraction dan 10
frame difference yang meningkatkan hasil sebelumnya dari background subtraction dan frame difference. Kinerja dari sebuah proses video tagging, sangat tergantung pada kemampuan untuk melakukan deteksi objek bergerak di dalam lingkungan yang diamati. Sebuah tindakan berikutnya, seperti tracking, analisis pergerakan atau identifikasi objek, memerlukan sebuah akurasi ekstraksi dari laman depan objek, menjadikan deteksi objek bergerak bagian yang penting dari sebuah sistem.
2.5. Background Subtraction Background subtraction digunakan untuk mengenali perbedaan intensitas dari citra dan latar belakang citra. Background modeling menggunakan frame baru untuk memperbarui pada background model. Background model dibagi ke dalam rekursif dan non rekursif. Teknik rekursif menggunakan frame masukan untuk memperbarui background model tunggal secara rekursif. Dibanding pada model rekursif, non rekursif menggunakan antar frame untuk memisahkan piksel sebagai background atau foreground. Untuk melakukan threshold
menggunakan metode frame
difference, salah satu dari teknik non rekursif dalam background subtraction. Frame difference merupakan teknik background model yang paling sederhana, di samping rendah dalam kompleksitas komputasinya [34]. 1, if I x, y, t I x, y, t 1 Back / Foreground x, y, t 0, otherwise
(2.1)
Threshold (α) digunakan untuk mengklasifikasi antara foreground dan background yang biasa dilakukan secara manual oleh manusia.
a. Citra Asli
b.
Citra Hasil Background Substraction
Gambar 1. Model Hasil Background Substraction
11
2.6
Otsu Algorithm
Metode Otsu merupakan metode threshold untuk segmentasi yang berdasarkan pada histogram citra, histogram ini menunjukkan nilai instensitas dari tiap piksel pada citra dalam dimensi 1. Sumbu x menyatakan level intensitas yang berbeda, sedangkan sumbu Y menyatakan jumlah piksel yang memiliki nilai intensitas tersebut Threshold dari algoritma Otsu inisialisasi menggunakan t . Nilai bentangan dari t berkisar antara 1 dan L , dimana L 255 , probabilitas dari tiap piksel di dalam level ke- i dapat di jelaskan (2.2).
pi ni / N
(2.2)
ni adalah angka dari pixel di dalam i th level dan N merupakan banyaknya pixel.
Rata-rata gray level dari sebuah citra digunakan persamaan 2.3 :
T
L 1
i p
(2.3)
i
i 1
Untuk threshold tunggal, Otsu membagi pixel ke dalam dua kelas C1 0,1,..., t dan C2 t 1, t 2,..., L 1 . N Probabilitas dari kelas dapat di komputasi dengan (2.4). t
p
2 (t )
i pi 1 (t )
2 (t )
1 (t )
i
t
i 1
p
(2.4.)
i
i 1
i 1
1 (t )
L 1
L 1
i pi
i 1
2
(t )
(2.5)
Nilai dari t dapat di komputasi menggunakan (2.5).
t * max B2 (t )
(2.6)
1 k L
dengan B2 t 1 t 1 t T
2
2 t 2 t T
2
(2.7)
2.7 Clustering Algoritma clustering dapat dipertimbangkan sebagai teknik untuk klasifikasi piksel sebagai foreground dan background. Algoritma clustering dapat dibagi ke dalam clustering keras 12
dan lunak. Clustering keras diartikan sebuah objek keanggotaanya hanya pada satu clustering, sedangkan clustering lunak keanggotaanya dapat berada pada beberapa cluster. Fuzzy C-Means (FCM) merupakan algoritma clustering lunak yang menghasilkan sebuah keanggotaan bebas dari tiap objek ke seluruh cluster. FCM merupakan algoritma clustering tidak terbelajar yang berhasil pada sejumlah problem clustering, seperti segmentasi warna dan clustering citra gambar. FCM menghasilkan sebuah matrik keanggotaan yang berisi keanggotaan bebas dari sebuah pixel ke seluruh cluster. FCM mencoba meminimalkan jumlah kesalahan sum of square error (SSE). Adapun formulanya : N
SSE
2
C
xi c j ,1 m
uijm
i 1 j 1
(2.8)
uij merupakan representasi dari keanggotaan dari pixel xi di dalam j th cluster, c j adalah j th pusat cluster. c
u
1,1 j n
ij
i 1
uij 0,1 i c,1 j n
(2.9) (2.10)
n
u
ij
1,1 i c
(2.11)
i 1
Algoritma FCM dapat di jelaskan dalam langkah sebagai berikut 1. Tentukan data input dari sebuah citra gambar. 2. Pilih angka dari jumlah cluster dan nilai dari ( 0 ). 3. Perhitungkan matrik partisi menggunakan persamaan
1
uik
dik d j 1 jk c
2
(2.12)
m 1
4. Perbaiki pusat cluster dengan menggunakan persamaan
13
n
u
m ik xk
cj
k 1 n
(2.13)
uikm
k 1
5. Ulang langkah 3 sampai 4 dimana
c k c k 1
.
Mean Square Error (MSE) dan Peak Signal to Noise Ratio (PSNR) digunakan untuk mengukur performance dari proses segmentasi obyek bergerak. Nilai MSE yang kecil dan nilai angka PSNR yang besar menunjukkan metode deteksi lebih baik. Adapun persamaan MSE dan PSNR tersebut sebagai berikut :
M
N
X (i, j) Y (i, j)
(2.14)
max 2 PSNR X , Y 10.log10 MSE X , Y
(2.15)
1 MSE X , Y MN
i 1 j 1
2.7.1 Clustering K-Means
Cluster (klaster) adalah kesatuan nilai-nilai dalam jarak tertentu pada kepadatan suatu daerah (relatif besar) dibandingkan dengan kepadatan nilai-nilai daerah sekitarnya. Teknik klasterisasi bermanfaat untuk segmentasi citra dan klasifikasi data yang belum diolah untuk menciptakan kelas-kelas. Warna diwakili dalam vektor 3 dimensi dari nilai titiknya. Masing-Masing komponen warna dihadirkan dalam warna merah, hijau dan biru (RGB). Perlu dicatat bahwa penggunaan penyajian ini, jika dua garis vektor adalah saling berdekatan, warna akan ditampilkan serupa, rata-rata dari dua garis vektor, jika warna yang akan ditampilkan sangat berbeda, maka akan diambil jalan tengah dengan menghadirkan suatu warna secara kasar dari warna aslinya. Acuan ini juga ketika rata-rata berbagai garis vektor RGB. Adapun cara-cara lain yang tidak membatasi untuk menghadirkan suatu warna dengan garis vektor 3 dimensi. Berikut untuk detilnya dari penjelasan di atas, bagaimana pilihan penampilan warna mempengaruhi hasil proses klasterisasi: 14
1.
Langkah yang pertama adalah menetapkan data set dari algoritma yang akan digunakan (KMeans), yaitu dengan melakukan pengambilan nilai acak dari k.
2.
Kemudian, penampilan RGB dari tiap pixel diciptakan, dan menghasilkan dataset dalam 3- vektor.
3.
Algoritma K-Means diterapkan pada dataset, menetapkan klasterisasi pusat k. Algoritma KMeans akan menghadirkan k warna untuk menggambarkan citra tersebut.
4.
Tiap-Tiap piksel citra dikonversi dalam suatu garis vektor RGB, dan ditampilkan menggunakan rata-rata dari kelompok warna yang dihasilkan.
Salah satu metode dalam clustering adalah metode Kmean, metode ini merupakan algoritma clustering yang paling popular dan banyak digunakan dalam dunia industri. Langkah-langkah metode K-means dalam penentuan data cluster sebagai berikut [38]: 1. Tentukan k sebagai jumlah cluster yang di bentuk. Untuk menentukan banyaknya cluster k dilakukan dengan beberapa pertimbangan seperti pertimbangan teoritis dan konseptual yang mungkin diusulkan untuk menentukan berapa banyak cluster. Menentukan jumlah kluster (k), tetapkan pusat kluster sembarang dari objek-objek yang tersedia sebanyak k cluster, kemudian untuk menghitung centroid cluster ke-i berikutnya, digunakan rumus sebagai berikut : 𝑣=
∑𝑛 𝑖=1 𝑥𝑖
(2,16)
𝑛
Dimana 𝑣 = centroid pada cluster 𝑥1 = objek ke-i 𝑛 = banyaknya objek/jumlah objek yang menjadi anggota cluster i= 1,2,3…n 2. Menghitung jarak setiap data ke pusat kluster, contohnya untuk menghitung jarak antara objek dengan centroid menggunakan Euclidian Distance 𝐷(𝑋, 𝑌) = √∑(𝑋𝑖 − 𝑌𝑖 )2
(2.17)
Dimana 𝑋𝑖 = Obyekx ke-I , 𝑌𝑖 = obyek y ke-i 3. Mengelompokan data ke dalam kluster yang dengan jarak yang paling pendek 4. Menghitung pusat kluster yang baru 5. Mengulangi langkah 2 sampai dengan 4 hingga sudah tidak ada lagi data yang berpindah ke kluster yang lain. Pengecekan konvergensi dilakukan dengan 15
membandingkan matriks group assignment pada iterasi sebelumnya dengan matrik group assignment pada iterasi yang sedang berjalan. Jika hasilnya sama maka algoritma k-means cluster analysis sudah konvergen, tetapi jika berbeda maka belum konvergen sehingga perlu dilakukan iterasi berikutnya. Pada langkah-langkah penentuan cluster metode K-means diatas, menghitung penentuan jarak setiap data ke pusat cluster sangatlah penting dimana keakuratan dalam penentuan cluster sangat dipengaruhi oleh penentuan jarak tersebut. Algoritma ini dimulai dengan penyekatan masukan menunjuk ke dalam tetapan k secara acak. Kemudian mengkalkulasi rata-rata titik, atau pusat luasan, dari tiap set. Hal ini mengakibatkan suatu sekat baru dengan menghubungkan masing-masing dengan pusat luasan yang terdekat. Kemudian pusat luasan dihitung kembali untuk klaster yang baru, dan algoritma yang diulangi dua langkah sampai pemusatan, yang mana diperoleh ketika poin-poin tidak lagi berpindah klaster atau sebagai alternative pusat luasan adalah tidak lagi diubah. Walaupun algoritma harus selalu memusat, tidak ada batas pada banyaknya iterasi yang berulangulang sesuai yang diperlukan. Suatu implementasi boleh dipilih untuk menghentikan algoritma itu setelah suatu jumlah iterasi tertentu. Pemusatan tidaklah menjamin untuk menghasilkan suatu hasil yang maksimal secara menyeluruh[38].
2.7.2 Operasi Mophology Morfologi adalah satu cabang dari pengolahan citra yang sangat bermanfaat dalam analisis bentuk dalam citra. Morfologi didasarkan pada bentuk segmen atau region dalam citra. Morfologi atau kadang disebut mathematical morphology adalah alat untuk mengekstrak komponen-komponen citra digital yang berguna dalam representasi dan deskripsi dari suatu gambar [21]. Morfologi dapat diterapkan sebagai langkah awal ataupun akhir dari proses analisis citra digital untuk jenis gambar biner(0 dan 1) atau citra dengan skala keabuan (0-255) atau grayscale [21]. Namun, umumnya morfologi biasanya diterapkan pada citra biner. Perbedaan pada pemrosesan citra secara morfologis adalah suatu citra dipandang sebagi himpunan, yang sebelumnya dipandang sebagai suatu fungsi intensitas terhadap posisi (x,y). Secara umum, pemrosesan citra secara morfologi dilakukan dengan cara mem-passing sebuah structuring element (SE) terhadapa sebuah citra dengan cara yang hampir sama dengan konvolusi. Structuring element dapat diibaratkan dengan mask pada pemrosesan citra. Structuring element dapat berukuran sembarang, namun Matlab menyediakan beberapa bentuk structuring element seperti: line, disk, diamond, arbitary, square, and 16
rectangle. Terdapat dua operasi dasar dalam morfologi yaitu dilasi dan erosi, operasi lainnya dibangun dari kombinasi antara keduanya. 2.7.2.1 Dilasi Dilasi merupakan proses penggabungan titik-titik latar menjadi bagian dari objek berdasarkan structuring element yang digunakan. Dilasi dilakukan dengan meletakkan titik poros SE pada titik A kemudian diberi angka 1 untuk semua titik(x,y) yang terkena/tertimpa oleh structuring element pada posisi tersebut.
SE
A
D
SE=structures
D = citra hasil dilasi
elements
𝑑(𝐴, 𝑆𝐸) = 𝐴⨁𝑆𝐸
A = citra biner
Gambar 2. Model Dilasi 7.2.2.2 Erosi Erosi merupakan proses penghapusan titik-titik objek(1) menjadi bagian dari latar(0), berdasarkan stucturing elements(SE) yang digunakan. Erosi dilakukan dengan meletakkan titik poros SE pada titik A kemudian jika ada bagian dari SE yang berada diluar A, maka titik poros akan dihapus atau dijadikan latar.
17
SE
A
E
SE=structures
E = citra hasil erosi
elements 𝐸(𝐴, 𝑆𝐸) = 𝐴 ⊗ 𝑆𝐸
A = citra biner
Gambar 3. Operasi Erosi 1.2.4.1 Opening Operasi erosion sangat berguna dalam menghilangkan objek-objek kecil yang terdapat dalam gambar, namun operasi ini memiliki kelemahan, yaitu terjadinya penurunan ukuran objek yang lainnya. Untuk mengatasi hal tersebut, dapat dilakukan operasi dilation setelah melakukan operasi erosion dengan menggunakan SE yang sama. Kombinasi dari kedua operasi ini disebut opening[21]. Secara matematis, operasi opening pada gambar biner dapat dituliskan dengan rumus berikut ini 𝐴 ∘ 𝑆𝐸 = (𝐴 ⊝ 𝑆𝐸) ⊕ 𝑆𝐸
(3)
Operasi opening akan mencegah penurunan ukuran objek secara keseluruhan. Gambar II.8 menunjukkan contoh operasi opening menggunakan SE berukuran 3x3. (𝐴 ⊝ 𝑆𝐸)
(𝐴 ⊝ 𝑆𝐸) ⊕ 𝑆𝐸
A SE=structures
SE
elements A = citra biner Gambar 4. Operasi Opening.
2.7.2.4 Closing Sama seperti opening, operasi closing merupakan penggabungan antara operasi erosion dan dilation. Namun, pada closing operasi dilation dilakukan terlebih dulu kemudian baru 18
diikuti dengan operasi erosion. Secara matematis, operasi closing dapat dituliskan dengan rumus. 𝐴 ⋅ 𝑆𝐸 = (𝐴 ⊕ 𝑆𝐸) ⊝ 𝑆𝐸
(4)
Hasil operasi closing hampir mirip seperti hasil operasi dilation, yaitu memperbesar batas luar dari foreground objek dan juga menutup lubang kecil yang terletak di tengah objek. Akan tetapi, hasil operasi closing tidak sebesar operasi dilation. Hasil dari operasi dilation akan menyebabkan pembengkakkan bentuk keseluruhan objek. Efek ini dapat dikurangi dengan menerapkan proses erosion setelah proses dilation.
(𝐴 ⊝ 𝑆𝐸) ⊕ 𝑆𝐸
A (𝐴 ⊕ 𝑆𝐸) SE
SE=structures elements A = citra biner Gambar 5. Operasi Closing.
2.7.2 Filter Gabor Filter Gabor merupakan salah satu filter yang mampu mensimulasikan karakteristik sistem visual manusia dalam mengisolasi frekuensi dan orientasi tertentu dari citra [39]. Karakteristik ini membuat filter Gabor sesuai untuk aplikasi pengenalan tekstur dalam computer vision. Secara spasial, sebuah fungsi Gabor merupakan sinusoida yang dimodulasi oleh fungsi Gauss. Respon impuls sebuah filter Gabor kompleks dua dimensi adalah :
19
dan dapat digambarkan sebagai berikut:
Gambar 6. Respon impuls filter Gabor dua dimensi.
Dalam domain frekuensi spasial, filter Gabor dapat direpresentasikan sebagai berikut:
Dalam domain frekuensi spasial, parameter-parameter filter Gabor dapat digambarkan sebagai:
Gambar 7. Parameter filter Gabor dalam domain frekuensi spasial 20
Tabel 2.2 Enam parameter filter Gabor
Ada enam parameter yang harus ditetapkan dalam implementasi filter Gabor. Keenam parameter tersebut adalah: F, θ, σx, σy, BF, dan Bθ -
Frekuensi (F) dan orientasi (θ) mendefinisikan lokasi pusat filter.
-
BF
dan Bθ menyatakan konstanta lebar pita frekuensi dan jangkauan angular
filter. -
Variabel σx berkaitan dengan respon sebesar -6 dB untuk komponen frekuensi spasial.
-
Variabel σy berkaitan dengan respon sebesar -6dB untuk komponen angular.
-
Posisi (F, θ) dan lebar pita (σx, σy) dari filter Gabor dalam domain frekuensi harus ditetapkan dengan cermat agar dapat menangkap informasi tekstural dengan benar. Frekuensi tengah dari filter kanal harus terletak dekat dengan frekuensi karakteristik tekstur.
21
-
Setelah mendapatkan ciri Gabor maka dapat dilakukan ekstraksi ciri. Salah satu ciri yang dapat dipilih adalah ciri energi, yang didefinisikan sebagai:
-
Dalam modul ini digunakan lebar pita frekuensi (BF), dan jarak frekuensi tengah (SF) sebesar satu oktaf, serta lebar pita angular (Bθ) dan jarak angular (Sθ) sebesar 30° dan 45°. Pemilihan lebar pita angular sebesar 30° dan 45° adalah karena nilai ini dianggap mendekati karakteristik sistem visual manusia.
2.3 Peta Jalan Penelitian Pada Penelitian Disertasi Doktor ini, belum pernah ada penelitian dibidang video object tagging menggunakan metode klastering. Diharapkan penelitian dibidang video object tagging dapat mendorong untuk semakin meningkatkan penelitian di bidang video processing atau visi komputer. Dibawah ini peta jalan penelitian yang akan dilakukan :
Gambar 8. Road Map Penelitian Video Object Tagging
22
Gambar 9. Fishbone Road map Video Object Tagging 2.3.1 Peta jalan Penelitian 1: Deteksi objek bergerak dan threshold. Pada proses ini, untuk melakukan deteksi terhadap obyek bergerak digunakan pendekatan berbasis background subtraction. Pendekatan ini merupakan proses untuk mendeteksi pergerakan atau perbedaan yang signifikan di dalam video frame. Untuk algoritma background subtraction diimplementasikan metode frame difference. Metode frame difference merupakan perbedaan antara dua frame secara berurutan dalam sebuah video dan sebuah reference background frame untuk ektrak daerah bergerak dari sebuah citra yang diciptakan sebuah citra berbeda. Adapun proposed algoritma sebagai berikut : Video Sequence Background Subtraction Adaptive Threshold
Classify Pixels
Morphology
Moving Object Segmented
Gambar 10. Model Alur dari Deteksi dan Threshold Objek Bergerak
23
Gambar 11. Clustering obyek bergerak dengan FCM dan OTSU (Vehicle)
24
Gambar 12. Clustering obyek bergerak dengan FCM dan OTSU (Human)
Peta Jalan Penelitian 2 : Segmentasi objek bergerak . Pada tahap 2 ini proses segmentasi dari objek bergerak yang telah berhasil terdeteksi dengan metode clustering dilakukan proses segmentasi. Dari hasil segmentasi ini yang akan dilakukan prose pembelajaran terhadap data set untuk pelabelan. Adapun hasil segmentasi dapat dilihat pada gambar dibawah ini :
BAB III TUJUAN DAN MANFAAT PENELITIAN
3.1 Tujuan dan Manfaat Pada penelitian ini bertujuan untuk mendapatkan objek pada sebuah video pelacakan yang memiliki karakteristik seperti bentuk non-kaku dan tampilan obyek yang bervariasi, oklusi, perubahan pencahayaan, adegan yang tidak beraturan. 3.2 Kontribusi Penelitian Dengan menggunakan metode clustering, seperti k-means, fuzzy, self organization map didapatkan object yang tepat dan dapat mengurangi jumlah pixel eror sehingga akurasi yang dihasilkan dapat meningkat. Manfaat yang dapat diberikan dalam penelitian ini dengan deteksi dan segmentasi objek bergerak yang akurat dapat membantu proses pelacakan video. Misalkan: Pengawasan otomatis, pengindekan video, anotasi otomatis, pemantauan lalu lintas, navigasi kendaraan. 3.1 Manfaat Penelitian Manfaat dari penelitian ini adalah: 25
3.3.1 Manfaat praktis Manfaat dari penelitian ini yaitu diharapkan agar terciptanya suatu sistem yang efektif dan efisien yang dapat membantu permasalah deteksi objek dalam pelacakan atau pengawasan video otomatis, pengindekan video, pemantauan lalu lintas dan navigasi kendaraan. 3.3.2 Manfaat teoritis Hasil penelitian ini diharapkan dapat memberikan sumbangan pada pengembangan teori yang berhubungan dengan penggunaan algoritma clustering pada teknik pengurangan background untuk mendeteksi objek bergerak dalam pelacakan dan pengawasan berbasis video.
26
BAB IV METODE PENELITIAN
4.1 Bagan Penelitian First Stage Study of Video processing
Study of Frame Processing
Moving Object Detection using Background Subtraction
Study State of The Art
Study about Background Subtraction
Publication
Report
Second Stage Collecting Data
Preprocessing
Adaptive Threshold using FCM
Automatic Detection of Moving Object
Clasify Pixel and Morphology
Moving Object Segmented
Report
Publication
Third and Four Stage Moving Object Extraction
Clasification and Recognition Moving Object
Publication
Video Object Tagging
REPORT
Gambar 13. Skema Penelitian Video Tagging
Gambar 13. menjelaskan bahwa penelitian disertasi doktor terdiri atas 4 tahap 27
Deteksi moving object (1) kemudian adaptive threshold untuk melakukan proses deteksi dan clustering (2) tahap yang berikutnya proses segmentasi objek yang bergerak yang berhasil dilakukan klastering (3) dan yang terakhir adalah proses klasifikasi dan pengenalan serta pelabelan terhadap objek yang sudah dilakukan pembelajaran. Yang dilakukan dalam penelitian PDD ini adalah 2 tahap dari 4 tahap penyelesaian disertasi, yaitu : (1) Segmentasi secara automatik dan pelabelan dari objek yang tersegmentasi setelah dilakukan proses pembelajaran sehingga objek tagging berhasil di lakukan.
4.2 Lokasi Penelitian Lokasi penelitian direncanakan akan dilakukan di : (1) Laboratorium Telematika B-201, Teknik Elektro, FTI-ITS. (3) Laboratorium Riset, Magister Teknik Informatika Universitas Dian Nuswantoro. 4.3 Indikator Capaian Secara Terukur Hasil yang ditargetkan adalah video object tagging yang mampu melakukan proses tracking, segmentasi klasifikasi hingga pengenalan objek.
Tabel 3.1 Indikator Capaian No.
Rincian Kegiatan
Tolak Ukur
1
Target luaran
Terselesaikannya peneltian video object tagging yang dimulai dari deteksi, tracking, segmentasi objek, klasifikasi dan pengenalan label objek
2.
Sasaran sampel data
Data yang akan direkam dan di tagging mahsiswa Universitas Dian Nuswantoro dan Mahasiswa ITS
3.
Waktu dan jumlah sampel model
-
Kegiatan pengambilan data dilakukan selama 4 bulan
-
Pengembangan sistem dan survey selama 4 bulan
-
Penulisan paper dan jurnal dilakukan selama 4 bulan efektif
-
Waktu pelaksanaan bulan januari 2015 sd Desember 2015
-
Jumlah mahasiswa yang direkam 30 sd 40 mahasiswa
28
4.
Indikator Pencapaian
-
Minimal 85 persen penelitian ini membantu penyelesain disertasi doktor
-
Diterima sebagai paper dan jurnal pada publikasi internasional terindex scopus.
Institusi yang terlibat Institut Teknologi Sepuluh Nopember Surabaya
4.5 Metode Metode yang diusulkan untuk penelitian ini menerapkan algorithma clustering pada Background Substraction untuk mengelompokkan pixel pada citra termasuk sebagai background atau foreground. Ditambahkan operasi morfologi dan median filtering dalam rangka meningkatkan performa dari model yang diajukan. Berdasarkan Gambar 14 maka metode yang diusulkan pada penelitian ini dapat dijelaskan antara lain:
29
Gambar 14. Metode yang diusulkan
Tahapan pada usulan penelitian ini: 4.5.1 Input image frame Data image/citra yang telah disiapkan dalam pengolahan data awal. Di-load oleh model. Data yang digunakan adalah data pada folder eksperimen. 4.5.2
Preprosessing
Image frame hasil ekstraksi mempunyai ruang warna RGB. Setiap image frame akan masuk proses inisialisai. Pada proses inisialisasi, dimensi image frame masukan akan di-resize menjadi 240X352. Kemudian image frame masukan diekstrak menjadi 3 bagian image R,image G, dan image B. Sebelum proses inisilaisasi dilakukan, tentukan dulu image yang menjadi model background. Image frame pertama akan digunakan
30
sebagai model background awal. Tahap preprocessing ini dilakukan sebagai persiapan dalam pendeteksian foreground menggunakan Background Subtraction. 4.5.3
Background Substraction
Pada tahap background substraction berisi beberapa proses. Dimulai dengan pencarian Best Matching Unit (BMU) dari model background dengan frame masukan. Proses ini dimulai dengan menghitung jarak kedua citra. Digunakan fungsi jarak.m yang kami buat berdasarkan rumus perhitungan jarak Euclidean Distance. 𝑑(𝑎, 𝑏) = [(𝑎𝑅 − 𝑏𝑅 )2 + (𝑎𝐺 − 𝑏𝐺 )2 + (𝑎𝐵 − 𝑏𝐵 )2 ]1⁄2 Nilai pixel pada citra hasil pengurangan akan dibandingkan dengan nilai threshold yang telah ditetapkan. Pixel akan masuk kategori BMU jika nilainya lebih kecil atau sama dengan nilai threshold. Pixel yang masuk kategori BMU akan ditetapkan sebagai Background dan diberi nilai 0, sedang kondisi lainya akan masuk sebagai foreground diberi nilai 1. Sesuai dengan Algoritma Kmeans image di kluster menjadi background dan foreground menggunakan beberapa perbedaan jaraknya. 4.5.4. Filter Gabor Pada tahap ini frame yang dibaca akan dilakukan proses filtering dengan menggunakan filter gabor. Pada proses filter ini akan diberikan perlakuan parameter yang ada difilter gabor seperti σ, λ, π, dan θ yang bervariatif untuk menguji nilai yang terbaik dari nilai filter tersebut. -
Lambda (λ), merupakan parameter panjang gelombang dari factor sinusoidal. Nilainya ditentukan oleh piksel, dengan nilai bilangan asli yang sama atau lebih besar dari 2. Lambda merupakan invers dari frekuensi gelombang dalam fungsi gabor dengan nilai f = 1/ λ.
-
Tetha (θ) merupakan orientasi normal terhadap garis parallel fungsi Gabor, nilainya ditentukan dalam derajat antara 0 dan 360. Jika jumlah orientasi lebih dari satu dan disimbolkan N>=1, maka N konvolusi akan dihitung sesuai distribusi antara 0 dan 360 derajat. Cara alternative komputasi konvulusi dengan membuat daftar nilai orientasi dipisahkan dengan koma (0,45,135).
-
Phi (θ) merupakan fase offset sebagai factor kosinus dalam fungsi gabor, nilainya dalam derajat antara -180 dan 180. Untuk nilai antara 0 dan 180 sesuai dengan fungsi pusat simetris sedangkan nilai antara -90 dan 90 sesuai dengan fungsi anti
31
simetris. Jika nilai diberikan (0,90) maka konvolusi bertingkat orientasi akan dihitung, satu setiap nilai dari daftar dalam fase offset.. -
Sigma (σ) standar deviasi dari Gaussian factor menentukan ukuran dari fungsi gabor. Nilai ini tidak dapat ditentukan secara langsung tetapi dapat diubah hanya melalui nilai bandwith (b). Nilai tersebut standardnya adalah 1, semakin kecil bandwith, semakin besar σ. 4.5.6. Postprocessing
Tahapan ini diaplikasikan teknik Morfologi dan filtering untuk memperbaiki hasil segmentasi dari Background Substraction. Teknik yang dapat digunakan dalam postprosessing seperti Morfologi (Closing, Opening, Dilation, Erotion), Median filter, Wiener filter, atau teknik peningkatan citra lain. Dalam penelitian ini diplikasikan Closing, Opening, Erotion dan Median Filter. 4.5.7. Object Detection and Marking Tahap terakhir adalah deteksi objek dan penandaan objek (foreground). Diaplikasikan algoritma connected component yang dilanjutkan dengan teknik Bounding Box yang akan memberi batas persegi objek yang terdeteksi pada citra. 4.6
Experimen dan Pengujian Metode
Pada tahapan ini menjelaskan tentang teknik pengujian yang digunakan. Pelacakan objek dilakukan menggunakan dua metode yaitu background Subtraction standard dan bacground substraction berbasis klastering. Proses eksperimen dan pengujian menggunakan dua dataset yang telah disiapkan dari tahap sebelumnya. Tahap ini akan dijalankan deteksi objek menggunakan background subtraction standar dan berbasis som pada setiap dataset. Setiap dataset berisi 100 frame. Hasil daeteksi akan diukur dengan membandingkan dengan citra ground truth. Dilakukan pengaturan parameter unutk mendapatkan performance dan akurasi terbaik. 4.7 3.5 Evaluasi Hasil Pada tahap ini dibahas tentang hasil evaluasi dari eksperimen yang telah dilakukan. Telah disebutkan sebelumnya, evaluasi pada penelitian ini dilakukan dengan mencari nilai MSE dan PSNR. Nilai MSE didapatkan dengan membandingkan citra ground truth dengan citra hasil deteksi dari metode yang diusulkan. Dari dataset yang digunakan akan diperoleh nilai MSE dan PSNR dari deteksi objek menggunakan Background Subtraction standard. Setelah itu dengan dataset yang samaclustering dan tahap post-processing yang diajukan, diapliksaikan dalam proses deteksi objek dengan dataset yang sama. Dari hasil yang 32
diperoleh kemudian dibandingkan untuk mengetahui ada perubahan atau tidak. Diharapkan dalam penelitian ini Algoritma clustering dan tahap post-processing yang diajukan bekerja dengan baik.
BAB V . HASIL DAN PEMBAHASAN
5.1 Target Penelitian Realisasi No
Jenis Kegiatan
Output Capaian
1.
Pengumpulan data
33
Keterangan
Melakukan review terhadap data yang dapat dipakai dalam penelitian
2.
Tempat Pengambilan data
85%
Melakukan review terhadap jurnal yang dapat dipakai dalam penelitian
Data Jurnal
85%
Melakukan review terhadap data yang diambil dan akan dipakai dalam penelitian
Data
90%
Data terproses
85%
Pengolahan Data Awal Melakukan proses pemilihan pada Data yang dipakai dalam percobaan Melakukan proses normalisasi data yang dipakai dalam percobaan Data berupa nilai fitur
85%
Ekperimen Melakukan eksperimen menggunakan Gabor filter dan K-means, motion vector dan ekstraksi fitur
85%
Melakukan penulisan kemajuan Penggunaan Dana penelitian
4.
-
85%
Melakukan Ekstraksi data menggunakan yang akan digunakan untuk percobaan kmeans, filter gabor dan fitur gabor 3.
-
Laporan Penggunaan Dana
70%
Laporan dan Publikasi Melakukan penulisan paper yang berjudul “Modified K-Means from Distance for Clustering Moving Objects Based on Gabor Filter
Paper terlampir Draft
5.2 Hasil Penelitian Bab ini menunjukkan hasil dari algoritma ketika diuji dengan urutan video yang disediakan. Algoritma ini dikembangkan dengan menggunakan Matlab. Urutan video diambil menggunakan kamera saku. Fokus utama di sini adalah untuk mencapai suatu algoritma yang kuat dan cerdas untuk mendeteksi objek bergerak pada berbagai karakteristik yang menyebabkan meningkatnya jumlah pixel error.
34
Hasilnya ditunjukkan langkah-demi-langkah sepanjang proses deteksi dan pada bagian ini menunjukkan hasil akhir dari proses pelacakan dari urutan video yang disertai dengan error disaat algoritma mendeteksi objek tersebut. Error didapatkan dari perbandingan hasil deteksi secara manual dengan hasil deteksi yang dilakukan oleh algoritma dalam proses mendapatkan hasil pelacakan yang akurat. Hasil eksperimen video dengan proses filter gabor dan Background subtraction. Pada hasil dibawah ditunjukkan dengan nilai N = 5, sigma = 0.2
(a) (b) (c) Gambar 16. Frame (a) frame asli (b) frame dengan Filter Gabor (c) frame dengan BG
Pada hasil dibawah menunjukkan hasil objek yang terdeteksi dan terlacak dengan filter gabor
(a)
(b)
Gambar 17. Obyek terlacak dengan posisi saling berdekatan
Pada eksperimen pada dataset dari kamera wall berbeda berikut ini proses klastering obyek bergerak berhasil melakukan identifikasi dan segmentasi terhadap obyek yang terlacak. Masingmasing frame menunjukkan hasil yang berbeda dari hasil percobaan penggunaan metode klastering diantaranya K-means, Fuzzy C-means dan Self Organization Map.
35
(a)
(b) Gambar 18. Klastering dengan K-Means
(a)
(b) Gambar 19. Klastering dengan FCM
(a)
(c)
(c)
(b)
(c)
Gambar 20. Klastering dengan SOM Dari hasil eksperimen diatas, sebagai bahan evaluasi performance masing-masing metode digunakan metode MSE dan PSNR. Proses mendapatkan MSE ini dengan cara melakukan uji ground truth terhadap manual obyek yang disegmentasi. Adapun nilai MSE menunjukkan nilai eror dari kinerja algorithma dalam melakukan klastering dan segmentasi terhadap obyek yang ada. Nilai terkecil dari MSE menunjukkan semakin kecil tingkat kesalahan terhadap sehingga semakin baik hasil capaiannya. TABEL 4 . RATA-RATA MSE UNTUK
K-MEANS, FCM AND SOM
No.
Method
K-Means
FCM
SOM
1 2 3
Kampus1 Pejalan 2 Pejalan 3
9.913 13.827 9.799
9.886 13.170 9.796
9.899 13.973 9.809
Adapun hasil dari keseluruhan eksperimen dari dataset diatas dapat ditunjukkan dalam grafik yang menunjukkan performance masing-masing hasil uji coba metode klastering yang berbeda-beda.
36
30000 25000 20000 M S 15000 E 10000
Kmeans FCM SOM
5000 0 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 Frame
Gambar 20. Grafik MSE K-means, FCM dan SOM
(a) (b) Gambar 22. Dua Obyek terlacak dengan K-means
(a) (b) Gambar 23. Dua Obyek terlacak dengan FCM
(a)
(b)
(c)
(c)
(c)
Gambar 2.4. Dua obyek terlacak dengan SOM 37
Adapun hasil dari PSNR merupakan kebalikan dari nilai MSE, semakin tinggi nilai PSNR maka semakin baik hasil performance kinerja algoritma tersebut. Hasil PSNR dapat dilihat pada table berikut : TABEL 4 . RATA-RATA PSNR UNTUK K-MEANS, FCM AND SOM
No.
Method
K-Means
FCM
SOM
1 2 3
Kampus1 Walk1 Walk2
8,68 6,93 8,66
8,69 7,14 8,67
8,68 6,87 8,66
Adapun grafik PSNR dapat dilihat pada gambar dibawah ini : 30000 25000 M 20000 S 15000 E 10000
Kmeans FCM SOM
5000 0 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 Frame
Gambar 21. Grafik PSNR K-means, FCM, SOM Disamping nilai MSE dan PSNR dari metode klastering, juga didapatkan hasil waktu proses pada hasil yang didapat masing-masing algoritma sebagai berikut Tabel 5. Waktu proses (second) No. 1 2 3
Video Dataset Student Walk1 Walk2
K-Means
FCM
SOM
4.09 6.70 4.65
1.19 2.39 1.46
8.22 9.93 11.8
38
BAB VI RENCANA TAHAPAN BERIKUTNYA
Tahapan kegiatan berikutnya pada Penelitian desertasi doktor merupakan tahap penyelesaian, yang dapat dirinci sebagai berikut: Tabel 6.1 Kegiatan dan Target selanjutnya (Juli – Nopember 2015) No. 1. 2. 3. 4. 5.
Kegiatan Juli – Nopember 2015 Peneyelesain Ekstraksi fitur Penyelesaian Klasifikasi objek Penyelesaian pengenalan obyek Publikasi Ilmiah Pelaporan Kegiatan
Waktu Juli 2015
Target Hasil dan Luaran Fitur Ekstrkasi
Agustus 2015
Obyek terklasifikasi
100%
September 2015
Obyek ter-Rekognisi
100%
September 2015 Nopember 2015
Artikel Ilmiah (Jurnal) Laporan Kegiatan
100% 100%
Capaian 100%
Secara umum seluruh kegiatan penelitian disertasi doktor akan diselesaikan di akhir Nopember 2015
39
BAB VII KESIMPULAN Dalam percobaan yang telah dibahas sebelumnya, pada penelitian ini mampu mendapatkan objek dalam sebuah video pelacakan. Karakteristik seperti bentuk objek yang non kaku tampilan objek yang bervariasi, oklusi, perubahan pencahayaan yang tidak beraturan telah mempengaruhi hasil error yang dihasilkan oleh kmeans, fcm dan SOM. Dengan error kecil yang dihasilkan dari fcm, maka penelitian ini di anggap telah berhasil dalam melacak beberapa objek bergerak.
40
DAFTAR PUSTAKA
[1] A. G. Hauptmann, "Lessons for the future from a decade of informedia video
analysis research," in Proc. ACM Int. Conf. Image and Video Retrieval, Singapore, 2005, pp. 1-10. [2] A. G. Hauptmann, R. Yan, W. H. Lin, M. Christel, and H. Wactlar, "Can high-level
concepts fill the semantic gap in video retrieval? A case study with broadcast news," IEEE Trans. Multimedia, vol. 9, no. 5, pp. 958-966, Aug. 2007. [3] X. Li, D. Wang, J. Li, and B. Zhang, "Video search in concept subspace: A text-
like paradigm," in Proc. ACM Int. Conf. Image and Video Retrieval, Amsterdam, The Netherlands, 2007, pp. 603-610. [4] X. Mu, "Content-based video retrieval: Does video's semantic visual feature
matter?" in Proc. ACM SIGIR Conf. Research and Development Informa. Retrieval, Seattle, WA, 2006, pp. 679-680. [5] M. R. Naphade and J. R. Smith, "On the detection of semantic concepts at
TRECVID," in Proc. ACM Multimedia, New York, NY, 2004, pp. 660-667. [6] C. G. Snoek, M.Worring, and A.W. Smeulders, "Early versus late fusion in
semantic video analysis," in Proc. ACM Multimedia, Singapore, 2005, pp. 399402. [7] W. Kraaij and P. Over. "TRECVED-2005 high-level feature task: Overview," in Proc. TRECVID, Gaithersburg, MD, 2005 [8] D.M. Blei and M.I. Jordan, "Modeling Annotated Data," Proc. ACM SIGIR, pp. 127134, 2003. [9] G. Carneiro, A.B. Chan, P.J. Moreno, and N. Vasconcelos, "Supervised Learning of Semantic Classes for Image Annotation and Retrieval," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 29, no. 3, pp. 394-410, Mar. 2007. [10] A.B. Chan, P.J. Moreno, and N. Vasconcelos, "Using Statistics to Search and Annotate Pictures: An Evaluation of Semantic Image Annotation and Retrieval on Large Databases," Proc. Am. Statistical Assoc., Aug. 2006. [11] P. Duygulu, K. Barnard, J. de Freitas, and D. Forsyth, "Object Recognition as Machine Translation: Learning a Lexicon for a Fixed Image Vocabulary," Proc. Seventh European Conf. Computer Vision, pp. 349-354, 2002. [12] J. Fan, Y. Gao, and H. Luo, "Hierarchical Classification for Automatic Image Annotation," Proc. ACM SIGIR, pp. 111-118, 2007. R. Datta, D. Joshi, J. Li, and J.Z. Wang, "Image Retrieval: Ideas, Influences, and Trends of the New Age," ACM Computing Surveys, vol. 40, no. 2, pp. 1-60, 2008. [13] Meng Wang, Xian-Seng Hua, Yan Song, Xun Yuan, Shipeng Li, Hong Jiang Zang, "Automatic Video Annotation by Semi-Supervised Learning with Kernel Density Estimation", MM 06 October 23, 2006, Santa Barbara, California, USA, 2006 ACM 1- 59593-447-2.
41
[14] Chapelle O, Zien A, Scholkopf B. Semi-Supervised Learning [M], MIT Press,
2006. [15] Zhu X. Semi-supervised learning literature survey [R]. Technical Report,
1530, University of Wisconsin-Madison. [16] Cohen D A, Ghahramani Z, Jordan M I. Active learning with statistical models
[J]. Journal of Artifial Intelligence Research, 1996,4: 129-145. [17] Naphade M, Smith J R. Active learning for simultaneous annotation of
multiple binary semantic concepts [C]. Proceedings of International Conference on Image Processing, 2004. [18] Boutell M, Luo J, Shen X, et al. Learning multi-label scene classication [J].
Pattern Recognition, 2004, 37: 1757-1771. [19] Dietterich T G, Lathrop R H, Lozano-Perez T. Solving the multi- instance
problem with axis-parallel rectangles [J]. Artiflcal Intelligence, 1997, 89 (12): 31[20] Carl Vondrick, Deva Ramanan, "Video Annotation and Tracking with Active
Learning" [21] Meng Wang, Xian Sheng Hua, Member, IEEE, Richang Hong, Jinhui Tang,
Guo Jun Qi,Yan Nong, "Unified Video Annotation via Multigraph Learning", IEEE Transaction On Circuits and Systems For Video Technology, Vol 19, No. 5, May 2009. [22] Tianzhu Zhang, Member, IEEE, Changseng Xu, Senior Member, IEEE,
Guangyu Zhu, Si Liu and Hanqing Lu, Senior Member, IEEE. " A Generic Framework for Video Annotation via Semi-Supervised Learning", IEEE Transactions On Multimedia, Vol. 14, No. 4, August 2012. [23] Carl Vondrick, Donald Patterson, Deva Ramanan, " Efficiently Scaling Up
Crowdsourced Video Annotation ", " A Set of Best Practices for High Quality, Economical Video Labeling", International Journal of Computer Vision 2012 [26] Jeny Yuen, Bryan Russell, Ce Lu, Antonio Toralba, " labelme video : Building
a Video Database with Human Annotations", 2009 IEEE 12th International Conference on Computer Vision (ICCV) [27] Lamberto Balan, Marco Bertini, Alberto Del Bimbo, Lorenzo Seidenari,
Giuseppe Serra, "Event Detection and Recognition for Semantic Annotation of Video", Journal Multimedia Tools and Applications Volume 51 Issue 1, January 2011, Pages 275 - 302 [28] Georgios Th. Papadopoulos, Student Member, IEEE, Alexia Briassouli,
Vasileios Mezaris, Member IEEE, Ioannis Kompatsiaris, Member, IEEE, and Michael G. Strintzis, Fellow, IEEE, "Statistical Motion Information Extraction Representation for Semantic Video Analysis", IEEE Transactios on Circuits and Systems for Video Technology, Vol.19, No. 10, October 2009. [29] Llaria Bartolini, Marco Patella, Corrado Romani, " SHIATSU : Semantic-
Based Hierarchical Automatic Tagging of Videos By Segmentation using 42
Cuts", AIEMPro'10, October 29, 2010, Florence, Italy. 2010 ACM 978-14503-014-0 [30] Yang Li, Yafei Zhang, Jiangjiang Lu, Ran Li, Jiabao Wang, "Video Analysis
and Trajectory Based Video Annotation System", Asia-Pacific Conference on Wearable Computing Systems. 2010. [31] Jui-Hsin Lai and Shao-Yi Chien, " Baseball and Tennis Video Annotation with
Temporal Structure Decomposition", Multi Media Signal Processing Proceeding on IEEE, 2008. [32] Lipton, A; Fujiyoshi, H. & Patil, R., “Moving target classification and tracking
from real-time video”, Proceeding of IEEE Workshop Applications of Computer Vision, pp. 8-14, 1998. [33] Stauffer, C. & Grimson, W., “Adaptive background mixture models for real-
time tracking”, Proceeding of IEEE Conf. on Computer Vision and Pattern Recognition, pp. 246- 252, 1999. [34] Meyer, D.; Denzler, J. & Niemann, H., “Model based extraction of articulated
objects in image sequences for gait analysis”, Proceeding of IEEE Int. Conf Image Proccessing, pp. 78-81, 1998. [35] Desa, S. M. & Salih, Q. A., “Image subtraction for real time moving object
extraction”, Proceeding of Int. Conf. on Computer Graphics, Imaging and Visualization (CGIV'04'), pp. 41-45., 2004. [36] Heikkila, J. & Silven, O., “A real-time system for monitoring of cyclists and
pedestrians", Proceeding of Second IEEE Workshop on Visual Surveillance, pp 74-81, 1999. [37] Collins, R. ; Lipton, A.; Kanade, T.; Fujiyoshi, H.; Duggins, D.; Tsin, Y.;
Tolliver, D.; Enomoto, N. & Hasegawa. “System for video surveillance and monitoring”, Technical Report CMU-RI-TR-00-12, Robotics Institute, Carnegie Mellon University, 2000. [38] D.T Larose, Discovering Knowledge In data ‘An Introduction to Data Mining”, New Jersey, John Willey & Sons, Inc, Publication, 2005. [39] Zehang Sun, George Bebis, Ronald Miller,”On-Road Vehicle Detection Using
Evolutionary Gabor Filter Optimization”, IEEE Transactions on Intelligent Transportation System, Vol. 6, No.2 Juni 2005.
43
Lampiran 1. Draft paper
44
45
