Kode / Nama Rumpun Ilmu : 458/ Teknik Informatika Komputer Informatika ktro ELEKTRO
LAPORAN AKHIR 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 NOPEMBER 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. 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 5
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 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 6
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. c. Dikembangkannya sebuah sistem untuk video obyek tagging mengenali / pelabelan obyek dalam sistem video surveillance.
1.5
Keterkaitan Penelitian dengan Penyelesaian Disertasi 7
untuk
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. . 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 9
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 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, 10
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
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
11
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 ni
(2.2)
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 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. 12
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
(2.8)
i 1 j 1
merupakan representasi dari keanggotaan dari pixel xi di dalam j th cluster, c j adalah j th pusat cluster. uij
c
u
1,1 j n
ij
(2.9)
i 1
uij 0,1 i c,1 j n
(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 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
13
.
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)
MSE X , Y
1 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: 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. 14
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 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 15
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 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.
16
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.
SE
A
E
SE=structures
E = citra hasil erosi
elements 𝐸(𝐴, 𝑆𝐸) = 𝐴 ⊗ 𝑆𝐸
A = citra biner
Gambar 3. Operasi Erosi 1.2.4.1 Opening 17
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 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. 18
(𝐴 ⊝ 𝑆𝐸) ⊕ 𝑆𝐸
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 :
dan dapat digambarkan sebagai berikut:
19
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.
-
Setelah mendapatkan ciri Gabor maka dapat dilakukan ekstraksi ciri. Salah satu ciri yang dapat dipilih adalah ciri energi, yang didefinisikan sebagai: 21
-
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. 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: 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. 25
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.
33
BAB V . HASIL DAN PEMBAHASAN
5.1 Target Penelitian Realisasi No
Jenis Kegiatan
Output Capaian
1.
Pengumpulan data 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%
Melakukan proses normalisasi data yang dipakai dalam percobaan
-
85%
Melakukan Ekstraksi data menggunakan yang akan digunakan untuk percobaan kmeans, filter gabor dan fitur gabor
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.
-
Pengolahan Data Awal Melakukan proses pemilihan pada Data yang dipakai dalam percobaan
3.
Keterangan
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
34
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. 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
35
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.
(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
36
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.
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 24. 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 25. 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
5.2.1 Peningkatan Kualitas segmentasi dengan Filter Gabor dan Distance Pada bagian ini akan dideskripsikan proses dari segmentasi object bergerak dengan penerapan clustering dengan peningkatan kualitas menggunakan filter Gabor dan Analisis distance metric. Untuk metode yang diusulkan pada metode ini sebagai berikut : 38
Foreground Detection
Video Sequence
Foreground Enhancement
Clustering Object
Objects Segmented
Distance Measure
Noise Removal
Measurement
Gambar 26. Metode diusulkan untuk Enhancement Pada metode yang kami usulkan, pertama diterapkan metode background subtraction, untuk mendapatkan objek yang bergerak pada video frame. Dengan menerapkan tiga pengurangan image sequence pada eksperiman akan dihasilkan kualitas objek yang lebih baik disbanding dua frame. fbi ke
fbi 1 dan fbi 1 ke fbi .
Adapun persamaan metode tersebut
dapat dituliskan sebagai berikut :
fbi 1 fbi fbi 1
(1)
fbi 1 fbi 1 fbi
(2)
(a) (b) (c Gambar 27 Model subtraction frame (a) background (b) Foreground (c) Objek terdeteksi
Desaian Gabor Filter Langkah utama pada segmentasi citra video pada resolusi rendah dengan menerapakan Gabor filter untuk membuang noise pada image. Fungsi yang universal pada bentuki 2D Gabor filter dapat dilihat pada persamaan dibawah ini, merujuk pada space domain pada fungsi g(x,y) dan berhubungan dengan 2-D Fourier transform G(x,z) :
39
g ( p, q ) exp( (
2 2 p q 2 pq
)) cos(2 (u0 p v0 q)
(3)
2 2 2 (e e0 ) (e e0 ) 1 (c c0 ) 1 (c c0 ) G (c, e) A {exp( ( )) exp( ( ))} (4) 2 2 2 ce2 2 ce 2 ce ce
Dimana , (c0 , e0 ) merupakan partikel frekuensi 2-D , sedangkan u dan v dimana skala filter parameter yang akan membedakan hasil dari proses tersebut :
(a)
(b)
(c)
Gambar 28 Hasil proses gabor filter pada frame (c)
Proses klastering dengan fuzzy C-means Diberikan nilai 𝑋 = {𝑥𝑖: 𝑖 = 1, 2, 𝑁} menjadi nilai observasi pada citra, dimana 𝑖 menjadi respon dari index piksel dengan nilai, 𝑥𝑖 = (𝑥𝑖1, 𝑥𝑖2, 𝑥𝑖𝑑) 𝑉 merupakan vektor fitur piksel dimana r, 𝑖, 𝑑 menjadi dimensi piksel, dan 𝑁 merupakan angka dari piksel dalam gambar citra 𝑋. Fungsi objektif dari algorithm FCM diformulasikan sebagai berikut : N
c
J FCM uijm dij
(10)
i 1 j 1
Dimana nilai c adalah jumlah angka klaster, dan j merupakan indeks cluster, sehingga nilai
U [uij ]N c
merupakan matrik terhubung untuk fuzzy segmentasi,
merepresentasikan tingkat koneksi m dimana dan menyakinkan nilai of
uij
ij 1 uij
1
xi
uij
merupakan keanggotaan pada klaster jth
. Pada factor fuzzy telah di berikan sebagai exponent
dan menggambarkan algortima dari nilai tingkat fuzziness.
dij xi j
2
merepresentasikan dari distance Euclidean yang akan menjadi ukuran kemiripan dari
40
vekstor piksel 𝑥𝑖 dan d merupakan rata-rata vector dari 𝑗𝑡ℎ cluster
j ( j1 , j 2 ... jn )T
.
Nilai distance akan diimplementasi secara variatif untuk mendapatkan nilai yang terbaik dari segmentasi berbasis klastering diantaranya SAD, Minkowski dan lainnya. Penerapan jarak pada klastering Konsep dasar dari analisis klaster merupakan konsep penerapan analisis jarak pada pengukuran model kemiripan pada hasil segmentasi citra. Jarak dalam klastering memisahkan antar objek. Ukuran jarak [18] yang diterapkan untuk memisahkan antara kemiripan dan ketidakmiripan antara dua objek. Jarak menjadi peran yang sangat krusial dalam klastering data objek. Adapun analisis jarak yang dilakukan dalam eksperimen ini sebagai berikut : 5.4.1 Euclidean distance Euclidean distance merupakan yang terbanyak diterapkan dalam area visi computer, disamping pada pembelajaran terbimbing dan tak terbimbing pada algoritma mesin. Persamaan ini dapat dimodelkan sebagai berikut Eq. (8). :
d xi, z j 5.4.2
2 d xi,k z j ,k (11) k 1
City Block Distance
Distance ini juga diberikan nama Manhattan distance. Pengukuran pada city block distance lebih handal terhadap outliers. Distan ini di modelkan sebagai jumlah dari perbedaan antara fitur vector pada citra dan di estimasikan sebagai berikut by Eq. (9).
d d xi , z j xi,k z j ,k k 1
5.4.3
(12)
Canberra distance
Pengukuran pada city block distan menunjukkan pada data berukuran besar terhadap dua objek gambar menurut ketidakmiripannya. Untuk itu proses normalisasi pada tiap pasangan fitur yang berbeda dibagi dengan penjumlahan antara pasangan fitur. Pengukuran ini telah diterapkan utnuk jarak pada data numerik antara kueri dan database fitur vector yang di tunujukkan pada persamaan dengan Eq. (13). 41
|𝑥 −𝑧 |
𝑑(𝑥𝑖, , 𝑧𝑗 ) = ∑𝑛𝑘=1 |𝑥 𝑖𝑘|+|𝑧𝑖𝑘 | 𝑖𝑘
(13)
𝑖𝑘
5.4.4 Chebyshev distance Distance jarak ini juga dipangil dengan nama maximum value distance, yang banyak diterapkan dalam menyediakan data nilai terbesar dengan persamaann Eq. (11).
d xi , z j
5.4.5
max x z j ,k i 1,2,..n i ,k
(14)
Minkowski distance
Bentuk umum dari jarak didefinisikan sebagai berikut :
p d d xi , z j p xi,k z j ,k (15) k 1
Jika 𝑝 merupakan nilai integer positif. Jka diberikan nilai distance metrics untuk positif value dari p, sebagai contoh p =1 ditampilkan pada city block dan p= 2 maka Euclidean distance. Kami juga memeberikan nilai p =3 sebagai Minkowski distance pada komparasi pengukuran distance .
5.4.6 Bray Curtis Distance
Jarak Bray Curtis Distance merupakan sebuah jarak yang mirip dengan Manhattan distance. Rumus dari persamaan didefinisikan sebegai nilai bsolute difference dibagi dengan penjumlahan seperti tampak dibawah Eq. (16). ∑𝑛 |𝑥 −𝑧 |
𝑖𝑘 𝑖𝑘 𝑑(𝑥𝑖, , 𝑧𝑗 ) = ∑𝑛 𝑖=1 (|𝑥 |+|𝑧 |) 𝑖=1
𝑖𝑘
(16)
𝑖𝑘
42
5.4.7 Jensen Shannon Divergence
Jensen Shannon Divergence (JSD) merupakan metode popular untuk mengukur kemiripan antara dua kemungkinan distribusi. Jarak ini berdasarkan pada Kullback–Leibler divergence. JSD didefiiskan sebagai berikut :
1
𝐽𝑆𝐷(𝑥, 𝑦) = (∑𝑁 𝑥𝑖 𝑙𝑛𝑥𝑖 + ∑𝑁 𝑖 𝑖 𝑦𝑖 𝑙𝑛𝑦𝑖 ) − 2
𝑥𝑖 +𝑦𝑖 2
𝑥𝑖 +𝑦𝑖
𝑙𝑛 (
2
)
Ketika operasi background subtraction telah dilakukan proses dengan menggunakan metode pengurangan frame pada image sequence, sebagai hasil pengurangan didapatkan objek bergerak sebagai foreground . Dalam operasi morpologi opening dan closing dilakukan untuk mengurangi noise pada latar belakang agar meningkatkan performa. Pada bagian ini , operasi morpologi dilakukan dengan melakukan modifikasi pada atribut citra berdasar kan tampak luar. Terdapat beberapa operasi yang dilakukan seperti erosi, dilasi, opening and closing. Pada penggunaan dari opening untuk membuang piksel yang tidak dikehendaki, sehingga dapat memperbaiki dan menyederhanakan citra terhadap objek yang tersegmentasi.
(a) Frame Original
(b) Segmented Objek
(c) Morphologi Operasi
Gambar 29. Operasi Morphologi pada Frame Hasil eksperimen Pada percobaan ini digunakan urutan gambar video dari data set Weizsman1 dataset terdiri dari
50 frame dengan resolusi rendah (180x144) pada kecepatan 25 fps. Sebagai
pembanding eskperimen digunakan segmentasi dengan 2 metode yaitu FCM dengan distance dan FCM dengan Filter Gabor dan Distance. Kami melakukan evaluasi untuk mengukur performance dengan menggunakan Mean 1
http://www.ecse.rpi.edu/~cvrl/database/Activity_Datasets.htm
43
Square Error (MSE) untuk metode clustering [21]. MSE Hasil menunjukkan bahwa MSE FCM dengan gabor filter lebih baik disbanding FCM dengan distance. Performance of MSE diformulasikan sebagai berikut :
1 MSE G, F VY
V
Y
G(u, t ) F (u, t ) u 1 t 1
(a)
(b)
(d)
(f)
(c)
(g)
Not Segemented
(h)
(i)
(j)
Fig.30 Segmented moving object on 11th frame using FCM+Gabor and variance distance. (a) Frame original (b) Ground truth (c) Euclidean (d) City Block (e) Canberra (f) Chebyshev (g) Minkowski (h) Bray Curtis (i) Jensen Shannon
Hasil evaluasi performa dari Gabor filter telah dideskripsikan pada gambar 30 yang dibandingkan dengan metode FCM. Disamping itu kami juga melakukan perbandingan dengan menggunakan distance. Hasil menunjukkan bahwa Gabor filter yang ditambahkan ke FCM memiliki performa lebih baik dan dengan minkowski distance mengahsilkan MSE lebih rendah disbanding yang lain.
44
SAD
Uclidean
Chebyshev
Minkowski
Canberra
Bray Curtis
Jansen shanon
20,000.00 15,000.00 10,000.00 5,000.00 1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
Gambar 31. Hasil MSE FCM + distance SAD
Uclidean
Chebyshev
Canberra
Bray Curtis
Jansen shanon
Minkowski
15,000.00 10,000.00 5,000.00 1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
Gambar 32. Hasil MSE FCM dan Gabor filter + Distance
45
33
35
37
39
BAB VI KESIMPULAN Pada penelitian ini, kami membangun sebuah model Automatis untuk melakukan segmentasi pada video sequence khususnya pada video dengan kualitas rendah, dimana pada metode yang dilakukan dengan melakukan peningkatan kualitas hasil dengan gabor filter dan distance. Metode FCM dengan standar distance Euclidean memunculkan nosie dalam segmentasi. Untuk itu dilakukan peningkatan dalam hal kualitas segmentasi. Dengan mengganti distance standar dengan beberapa distance menunjukkan bahwa kualitas hasil segmentasi dapat dipengaruhi oleh distanc yang ada. Pada hasil eksperimen menunjukkan bahwa terjadi peningkatan kualitas MSE yang dihasilkan pada penambahan filter gabor pada frame yang dilakukan segmentasi. Dari keseluruhan tujuh distance menunjukkan bahwa minkowski distance memiliki peningkatan MSE yang signifikan.
46
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.
47
[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 48
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. [40] C. Shao-Yi, C. W. Kai, T. Y. Hsiang and H.-Y. Chen, "Video object segmentation and tracking framework with improved threshold decision and diffusion distance," IEEE Trans. On Circuits and Systems For Video Technology, vol. 23, no. 6, pp. 921-934, 2013. [41] N. Benaichouche, H. Oulhadj and P. Siarry, "Improved spatial fuzzy c-means clustering for image segmentation using PSO initialization, Mahalanobis distance and post-segmentation correction," Elsevier, Digit. Signal Process. 23 (2013) 1390–1400, vol. 23, pp. 1390-1400, 2013.
49
50
