Perancangan dan Implementasi Aplikasi Deteksi Kemiripan Citra Digital Menggunakan Algoritma Shingling dan Redundant Pixel Removal
Artikel Ilmiah
Peneliti: Andry Vegard Sariwating (672010147) Magdalena A. Ineke Pakereng, M.Kom.
Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Satya Wacana Salatiga 2016
Perancangan dan Implementasi Aplikasi Deteksi Kemiripan Citra Digital Menggunakan Algoritma Shingling dan Redundant Pixel Removal Artikel Ilmiah
Diajukan kepada Fakultas Teknologi Informasi untuk memperoleh gelar Sarjana Komputer
Peneliti: Andry Vegard Sariwating (672010147) Magdalena A. Ineke Pakereng, M.Kom.
Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Satya Wacana Salatiga 2016
Perancangan dan Implementasi Aplikasi Deteksi Kemiripan Citra Digital Menggunakan Algoritma Shingling dan Redundant Pixel Removal 1)
Andry Vegard Sariwating, 2) M. A. Ineke Pakereng Fakultas Teknologi Informasi Universitas Kristen Satya Wacana Jl. Diponegoro 52-60, Salatiga 50711, Indonesia 1) Email:
[email protected], 2)
[email protected]
Abstract Detection of digital image similarity is required to avoid the accumulation of information in a database or file system, to detect plagiarism, for grouping pictures, and a variety of other purposes. Shingling algorithm is used for the process of finding nearduplicate document. Redundant pixel removal is a technique to ignore / delete pixels that have the same value, which adjacent, in a digital image, so that the detection process can be minimized. In this study, shingling algorithm is implemented to detect similarities digital image. The test results indicate that the application can detect the similarity image that has been through various manipulations such as scaling (enlarge / reduce), rotation, cropping (cut part), and pixel manipulation. Keywords: Shingling, Near Duplicate Detection, Redundant Pixel Removal
Abstrak Deteksi kemiripan citra digital diperlukan untuk menghindari penumpukan informasi pada suatu database atau file sistem, untuk mendeteksi plagiasi, untuk pengelompokan gambar, dan berbagai keperluan yang lain. Algoritma Shingling merupakan algoritma yang digunakan untuk proses pencarian near-duplicate document. Redundant pixel removal adalah teknik untuk mengabaikan/menghapus piksel-piksel yang memiliki nilai sama, yang terletak bersebelahan, pada suatu citra digital, sehingga proses deteksi dapat diminimalisasi. Pada penelitian ini, algoritma shingling diimplementasikan untuk mendeteksi kemiripan citra digital. Hasil pengujian menunjukkan bahwa aplikasi yang dibuat, dapat mendeteksi kemiripan gambar yang telah melalui berbagai manipulasi yaitu scaling (perbesar/perkecil), rotasi, cropping (potong sebagian), dan manipulasi piksel. Kata Kunci: Shingling, Deteksi Kemiripan, Redundant Pixel Removal 1)
Mahasiswa Program Studi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Kristen Satya Wacana 2) Staf Pengajar Fakultas Teknologi Informasi, Universitas Kristen Satya Wacana.
1.
Pendahuluan
Kemudahan dalam menyalin informasi dari satu informasi ke tempat yang lain merupakan salah satu efek dari kemajuan teknologi informasi. Citra digital, sebagai salah satu bentuk informasi digital, dapat disalin, diubah, diambil sebagian, menjadi satu file yang baru. Deteksi kemiripan citra digital diperlukan untuk menghindari penumpukan informasi pada suatu database atau file sistem, untuk mendeteksi plagiasi, untuk pengelompokan gambar, dan berbagai keperluan yang lain. Algoritma Shingling merupakan algoritma yang ditemukan oleh Andrei Broder [1]. yang digunakan untuk proses pencarian near-duplicate document. Algoritma shingling bekerja dengan cara memotong-motong teks menjadi kumpulan kata, dan membangkitkan suatu nilai unik (fingerprint) untuk tiap kumpulan kata. Algoritma hash dapat digunakan untuk membangkitkan fingerprint [2]. Redundant pixel removal adalah teknik untuk mengabaikan/menghapus piksel-piksel yang memiliki nilai sama, yang terletak bersebelahan, pada suatu citra digital. Cara ini diperlukan ketika membandingkan dua citra digital yang berasal dari satu sumber, namun memiliki ukuran dimensi berbeda, dengan kata lain citra digital yang kedua merupakan hasil scaling (diperbesar/diperkecil) dari citra digital yang pertama. Pada penelitian ini, algoritma shingling diimplementasikan untuk mendeteksi kemiripan citra digital. Shingle yang diproses merupakan potongan dari piksel-piksel pada citra digital. Piksel-piksel yang redundant dihilangkan terlebih dahulu, sehingga dapat mempercepat proses pembandingan. 2.
Tinjauan Pustaka
Penelitian tentang deteksi kemiripFFan yang pernah dilakukan adalah "A Digest and Pattern Matching-Based Intrusion Detection Engine" [3]. Pada penelitian tersebut dipaparkan suatu masalah yaitu intrusion detection/preventation system (IDS/IPS) pada jaringan komputer. IDS/IPS bekerja dengan bergantung pada signature database dan pattern matching (PM). Untuk melakukan pencocokan pola (PM) dengan data yang lewat pada jaringan komputer digunakan algoritma Boyer-Moore. Hasil ekperimen menghasilkan kesimpulan bahwa dengan membangkitkan nilai Fingerprint, proses pencarian menjadi lebih cepat. Pada penelitian tersebut nilai Fingerprint dibangkitkan dengan menggunakan teknik Rabin-Fingerprint Perbedaan antara penelitian tersebut dengan penelitian yang dilakukan ini adalah pada penelitian ini bertujuan untuk mencari kemiripan antara dua dokumen, bukan paket data jaringan komputer, dan algoritma MD5 digunakan untuk membangkitkan nilai Fingerprint. Pada penelitian yang berjudul "Identifying and Filtering Near-Duplicate Documents", dibahas tentang masalah mendeteksi kemiripan halaman web satu dengan web yang lain, pada proses web indexing skala besar yang dilakukan oleh AltaVista search engine [4]. Andrei Broder mengajukan algoritma untuk menyaring near-duplicate documents, dan sudah diimplementasikan selama
1
kurang lebih tiga tahun pada AltaVista. Document yang dibandingkan disederhanakan dalam bentuk set, melalui proses shingling. Pada penelitian tersebut, satu Shingle terdiri dari 4 kata, sehingga disebut 4-shingling. Setiap Shingle dibangkitkan sebuah Fingerprint untuk kemudian dibandingkan dengan nilai Fingerprint dari Shingle pada dokumen kedua.Algoritma yang digunakan untuk membangkitkan nilai Fingerprint adalah Rabin's Fingerprint. Rabin's membangkitkan nilai Fingerprint sebesar 64 bit (8 byte). Berbeda dengan penelitian yang dilakukan ini, nilai Fingerprint diperoleh dengan cara membangkitkan nilai hash dari tiap Shingle. Algoritma yang digunakan adalah MD5. MD5 membangkitkan nilai hash sebesar 128 bit, bukan 64 bit. Nilai yang lebih panjang ini dimaksudkan untuk menghindari nilai hash yang sama dari dua Shingle yang berbeda. Pada penelitian yang berjudul “Implementasi Teknik Steganografi dengan Metode LSB pada Citra Digital”, disebutkan tentang perlunya pengamanan pengiriman pesan melalui jaringan Internet. Pada penelitian tersebut digunakan media gambar sebagai cover. Hasil penelitian tersebut adalah sebuah aplikasi steganografi dengan algoritma LSB Embedding, yang dapat menyembunyikan pesan, sehingga orang lain tidak menyadari keberadaan pesan di dalam media [5]. Berbeda dengan penelitian ini adalah, pada penelitian ini, proses dipilih pada lokasi yang memberikan perubahan paling minimal. Sehingga kerusakan (perubahan) pada cover menjadi tidak semakin mencurigakan, untuk mencapai salah satu tujuan steganografi. Berdasarkan penelitian-penelitian yang telah dilakukan tentang deteksi kemiripan dokumen teks, plagiasi, algoritma pencarian string dan teknik fingerprint, maka dilakukan penelitian yang bertujuan untuk merancang aplikasi deteksi kemiripan citra digital dengan mengimplementasikan algoritma Shingling dan redundant pixel removal. Batasan masalah dalam penelitian ini adalah sebagai berikut: (1) Citra digital yang dibandingkan memiliki format true color image; (2) Algoritma shingling digunakan untuk membandingkan dua citra digital berdasarkan kumpulan piksel (shingle) yang terbentuk dari kedua citra digital; (3) Algoritma redundant pixel removal digunakan untuk menghapus piksel bersebelahan yang mirip pada satu citra digital. Penelitian yang dilakukan membahas tentang near-duplicate dan plagiarism. Plagiarism secara sederhana adalah merepresentasikan ide orang lain, sebagai ide milik sendiri, baik terjadi secara sengaja maupun secara kebetulan [6]. Near-duplicate adalah kondisi ketika dua dokumen memiliki isi yang sama, berbeda pada berberapa kata atau susunan kata [7]. Algoritma Shingling merupakan algoritma yang ditemukan oleh Andrei Broder[4]. Algoritma ini bekerja dengan cara membuat sebuah shingle yang berisi beberapa kata dengan jumlah yang tetap. Angka yang menentukan jumlah kata dalam satu shingle ini disebut gram. Pada tiap shingle dibangkitkan nilai fingerprint. Proses shingling ini akan menghasilkan himpunan yang berisi sejumlah fingerprint. Himpunan ini kemudian dibandingkan dengan himpunan yang dihasilkan dari dokumen kedua. Nilai kemiripan diperoleh dengan cara membagi jumlah fingerprint yang sama (intersection) dari dua dokumen dengan
2
jumlah fingerprint gabungan (union). Proses perhitungan tersebut didefinisikan sebagai berikut[4]: |S S | (1) r A, B = |S S | Persamaan 1 Rumus Nilai Kemiripan [4]
Algoritma Shingling dilakukan melalui beberapa langkah berikut [4]: 1. Hilangkan tanda baca pada dokumen. 2. Dimulai dengan kata pertama, buat satu shingle berisi kata pertama tersebut sampai 3 kata berikutnya. 3. Pindah ke kata kedua, buat shingle berisi kata kedua dan 3 kata berikutnya. 4. Lakukan pembentukan shingle sampai dengan 4 kata terakhir dari dokumen tersebut. 5. Untuk tiap shingle, bangkitkan nilai fingerprint. 6. Lakukan langkah 1 sampai dengan 5 untuk dokumen kedua. 7. Gunakan rumus nilai kemiripan dokumen (Persamaan 1) untuk menghitung nilai kemiripan dokumen. Nilai fingerprint pada penelitian ini dihitung dengan menggunakan algoritma MD5. MD5 (Message-Digest Algorithm 5) ialah fungsi hash kriptografi yang digunakan secara luas dengan hashvalue 128-bit [2]. MD5 telah dimanfaatkan secara bermacam-macam pada aplikasi keamanan, dan MD5 juga umum digunakan untuk melakukan pengujian integritas (fingerprint) sebuah file.MD5 didesain oleh Ronald Rivest pada tahun 1991 untuk menggantikan hashfunction sebelumnya, yaitu MD4. Hashvalue yang dihasilkan oleh MD5 memiliki panjang 128-bit (16 byte), sekalipun input (pesan) yang digunakan memiliki panjang yang bervariasi. Hashvalue berubah signifikan sekalipun perubahan yang terjadi pada input hanya 1 byte. Algoritma Shingling yang ditemukan oleh Broder, menggunakan fingerprint dengan panjang 64 bit. Panjang fingerprint 64 bit untuk tiap shingle memiliki resiko yaitu dihasilkannya fingerprint yang sama untuk shingle yang berbeda. Hal ini disebut dengan collision vulnerabilities [8]. Untuk menghindari kemungkinan collision, maka digunakan fingerprint dengan panjang yang lebih dari 64 bit. Berdasarkan tujuan tersebut maka algoritma MD5 digunakan untuk menghasilkan fingerprint dengan panjang 128 bit. Pada penelitian ini, format file citra digital yang digunakan adalah PNG. PNG merupakan True Color image. Suatu true colour image memiliki komponen red, green dan blue yang terpisah untuk tiap pikselnya. Pada sebagian besar true colour image, tiap komponen diwakilkan dengan satu byte yang terdiri dari 8 bit, sehingga setiap piksel memiliki 24 bit informasi warna. Oleh karena itu, mode ini sering disebut sebagai “24-bit warna”. Pada Gambar 1 ditunjukkan contoh potongan dari file gambar. Potongan ini memiliki dimensi 6 x 6 piksel.Pada tiap piksel terdapat tiga bagian warna yaitu red, green dan blue. Pada lokasi piksel 1,1 terdapat warna red bernilai 96, green bernilai 143, dan blue bernilai 179. Pada lokasi piksel 1,2 terdapat warna red 61, green 125, dan green 198[9].
3
Gambar 1 Komponen RGB pada File Gambar 24 Bit Warna[9]
Microsoft .NET Framework merupakan sebuah perangkat lunak kerangka kerja yang berjalan pada sistem operasi Microsoft Windows. Saat ini .NET Framework umumnya telah terintegrasi dalam distribusi standar Windows (mulai dari Windows Server 2003 dan versi-versi Windows yang lebih baru). Kerangka kerja ini menyediakan sejumlah besar pustaka pemrograman komputer dan mendukung beberapa bahasa pemrograman serta interoperabilitas yang baik sehingga memungkinkan bahasa-bahasa tersebut berfungsi satu dengan lain dalam pengembangan sistem. Berbeda halnya dengan tipikal aplikasi konvensional umumnya, program yang ditulis dengan memanfaatkan .NET Framework berjalan pada lingkungan perangkat lunak melalui Common Language Runtime, dan bukan perangkat keras secara langsung. Hal ini memungkinkan aplikasi yang dibuat di atas .NET secara teoritis dapat berjalan pada perangkat keras apapun yang didukung oleh .NET Framework. Perangkat lunak ini adalah kunci penawaran utama dari Microsoft, dan dimaksudkan untuk digunakan oleh sebagian besar aplikasi-aplikasi baru yang dibuat untuk platform Windows [10]. Pada penelitian ini, .NET Framework digunakan untuk membangun aplikasi deteksi kemiripan. Beberapa pustaka pemrograman yang digunakan adalah pustaka untuk membuat Graphical User Interface (GUI), dan pustaka pemrosesan gambar (Bitmap). 3.
Metode dan Perancangan Sistem
Penelitian yang dilakukan, diselesaikan melalui tahapan penelitian yang terbagi dalam empat tahapan, yaitu: (1) Identifikasi masalah dan literatur, (2) Perancangan sistem, (3) Implementasi sistem yaitu Membangun aplikasi/program, dan (4) Pengujian sistem dan analisis hasil pengujian.
4
Identifikasi Masalah dan Studi Literatur
Perancangan Sistem
Implementasi Sistem
Pengujian Sistem dan Analisis Hasil Pengujian
Gambar 2 Tahapan Penelitian
Tahapan penelitian pada Gambar 2, dapat dijelaskan sebagai berikut. Tahap pertama: identifikasi masalah dan literatur, yaitu keamanan citra digital. Tahap kedua: perancangan sistem yang meliputi perancangan sistem deteksi kemiripan citra digital; Tahap ketiga: implementasi sistem, yaitu membuat aplikasi sesuai perancangan sistem pada tahap kedua; dan Tahap keempat: pengujian sistem dan analisis hasil pengujian, yaitu dilakukan pengujian terhadap proses yang telah dirancang, dan melihat kesesuaian solusi terhadap masalah yang telah teridentifikasi sebelumnya. Gambar A
Hapus Piksel Redundant
Buat Shingle berisi N Piksel Hitung Union dan Intersection
Gambar B
Hapus Piksel Redundant
Hitung Prosentase Kemiripan
Buat Shingle berisi N Piksel Gambar 3 Desain Sistem
Sistem yang dikembangkan, memiliki desain yang ditunjukkan pada Gambar 3. Sistem terdiri dari dua input yaitu file gambar A dan file gambar B. Hasil deteksi kedua file gambar tersebut adalah berupa angka prosentase kemiripan.
5
Mulai
Mulai
Himpunan piksel (K)
Gambar A
Gambar B Nilai gram (q)
Hapus Redundant Piksel
Hapus Redundant Piksel
Proses membentuk Shingle
Proses membentuk Shingle
Perulangan sebanyak K
Hitung nilai intersection True
Hitung nilai union Buat shingle False
Hitung Kemiripan = intersection/union x 100% Hitung fingerprint
Selesai Selesai
Gambar 4 Perhitungan Prosentase Kemiripan File Gambar
Gambar 5 Shingle dan Fingerprint
Proses perhitungan prosentase kemiripan file gambar secara garis besar ditunjukkan pada Gambar 4. Proses pembandingan memerlukan dua input file citra digital. Pada tiap file citra digital, dilakukan proses penghapusan pikselpiksel yang berlebihan (redundant). Piksel redundant adalah piksel yang memiliki nilai yang sama dengan nilai sebelumnya. Tujuan dari proses ini adalah untuk mengurangi shingle yang terbentuk, dan mempercepat proses pembandingan. Jumlah shingle yang terbentuk bergantung pada jumlah piksel yang ada pada suatu citra digital. Semakin sedikit piksel, maka semakin sedikit pula shingle yang dihasilkan. Semakin sedikit shingle yang dihasilkan, maka semakin cepat proses pembandingan. Penghapusan piksel redundant juga bertujuan untuk membandingkan dua file citra digital yang sama, namun berbeda ukuran dimensi karena hasil scaling (citra digital diperbesar/diperkecil). Proses pembentukan shingle dilakukan setelah proses penghapusan piksel redundant. Langkah detail dari pembentukan shingle ditunjukkan pada Gambar 5. Jumlah piksel dalam satu shingle ditentukan oleh nilai gram. Nilai gram ditentukan oleh input user. Pada tiap shingle yang terbentuk, dihitung nilai fingerprint. Pembentukan nilai fingerprint bertujuan untuk memperkecil ukuran byte shingle yang akan dibandingkan. Sebagai contoh jika dalam satu shingle terdapat 20 piksel (variabel gram diberi nilai 20), maka dalam satu shingle terdapat 20 x 3 byte (1 piksel terdapat warna R, G, B) = 60 byte. 60 byte tersebut jika dihitung nilai fingerprint dengan MD5, menghasilkan nilai hash 16 byte (128 bit). 6
Membandingkan dua shingle yang berukuran 16 byte, tentu lebih cepat dari pada membandingkan dua shingle berukuran 60 byte. Proses setelah terbentuk shingle untuk kedua gambar dan nilai fingerprint untuk tiap-tiap shingle, yaitu menghitung jumlah shingle yang sama pada kedua gambar (intersection), dan jumlah gabungan shingle kedua gambar (union). Nilai kemiripan diperoleh dari nilai intersection dibagi dengan nilai union, dikalikan 100 persen. Langkah-langkah pada flowchart di Gambar 4 dan Gambar 5, dapat dijelaskan dengan contoh proses deteksi kemiripan dua citra digital. Terdapat dua citra digital dengan nilai piksel ditunjukkan pada Gambar 6 dan Gambar 7. RGB (200,100,100)
RGB (100,200,120)
RGB (40,40,40)
RGB (40,40,40)
RGB (200,100,100)
RGB (100,200,120)
RGB (40,40,40)
RGB (200,100,100)
RGB (100,200,120)
Gambar 6 Susunan Piksel Citra Digital A RGB (200,100,100)
RGB (200,100,100)
RGB (40,40,40)
RGB (40,40,40)
RGB (100,200,120)
RGB (100,200,120)
RGB (50,50,50)
RGB (50,50,50)
RGB (100,200,120)
RGB (200,100,100)
RGB (200,100,100)
RGB (100,200,120)
RGB (40,40,40)
RGB (40,40,40)
RGB (100,200,120)
RGB (200,100,100)
RGB (200,100,100)
RGB (100,200,120)
Gambar 7 Susunan Piksel Citra Digital B
Piksel pada citra digital A disusun secara berurutan maka terbentuk deretan piksel yang ditunjukkan pada Gambar 8. Piksel pada citra digital B, menghasilkan deretan piksel ditunjukkan pada Gambar 9. Citra Digital A RGB (200,100,100) RGB (100,200,120) RGB (40,40,40) RGB (40,40,40) RGB (200,100,100) RGB (100,200,120) RGB (40,40,40) RGB (200,100,100) RGB (100,200,120)
Citra Digital B RGB (200,100,100) RGB (200,100,100) RGB (40,40,40) RGB (40,40,40) RGB (100,200,120) RGB (100,200,120) RGB (50,50,50) RGB (50,50,50) RGB (100,200,120) RGB (200,100,100) RGB (200,100,100) RGB (100,200,120) RGB (40,40,40) RGB (40,40,40) RGB (100,200,120) RGB (200,100,100) RGB (200,100,100) RGB (100,200,120)
Gambar 8 Susunan Piksel Citra Digital A Disusun Berurutan
Gambar 9 Susunan Piksel Citra Digital B Disusun Berurutan
7
Proses redundant pixel removing kemudian dilakukan pada susunan piksel tiap citra digital tersebut. Hasil dari proses tersebut menghasilkan nilai-nilai piksel ini: Citra Digital A (semula) RGB (200,100,100)
Citra Digital A (sesudah) RGB (200,100,100)
RGB (100,200,120)
RGB (100,200,120)
RGB (40,40,40)
RGB (40,40,40)
RGB (40,40,40)
RGB (200,100,100)
RGB (200,100,100)
RGB (100,200,120)
RGB (100,200,120)
RGB (40,40,40)
RGB (40,40,40)
RGB (200,100,100)
RGB (200,100,100)
RGB (100,200,120)
RGB (100,200,120)
Gambar 10 Susunan Piksel Citra Digital A sebelum proses redundant pixel removing
Gambar 11 Susunan Piksel Citra Digital A Setelah Proses redundant pixel removing
Citra Digital B (semula) RGB (200,100,100) RGB (200,100,100) RGB (40,40,40) RGB (40,40,40) RGB (100,200,120) RGB (100,200,120) RGB (50,50,50) RGB (50,50,50) RGB (100,200,120) RGB (200,100,100) RGB (200,100,100) RGB (100,200,120) RGB (40,40,40) RGB (40,40,40) RGB (100,200,120) RGB (200,100,100) RGB (200,100,100) RGB (100,200,120)
Citra Digital B (sesudah) RGB (200,100,100) RGB (40,40,40) RGB (100,200,120) RGB (50,50,50) RGB (100,200,120) RGB (200,100,100) RGB (100,200,120) RGB (40,40,40) RGB (100,200,120) RGB (200,100,100) RGB (100,200,120)
Gambar 12 Susunan Piksel Citra Digital B sebelum proses redundant pixel removing
Gambar 13 Susunan Piksel Citra Digital B Setelah Proses redundant pixel removing
Shingle-shingle kemudian dibentuk berdasarkan hasil removal pada Gambar 11 dan Gambar 13. Pada contoh ini nilai gram yang digunakan adalah 2, dengan tujuan untuk menyederhanakan contoh. Pada tiap shingle, kemudian dihitung nilai fingerprint dengan menggunakan algoritma MD5.
8
Tabel 1 Hasil Shingle dan Fingerprint pada Contoh Citra Digital A Shingle 1 2 3 4 5 6 7 8
Isi Shingle RGB (200,100,100) RGB (100,200,120) RGB (100,200,120) RGB (40,40,40) RGB (40,40,40) RGB (200,100,100) RGB (200,100,100) RGB (100,200,120) RGB (100,200,120) RGB (40,40,40) RGB (40,40,40) RGB (200,100,100) RGB (200,100,100) RGB (100,200,120) RGB (100,200,120) RGB (200,100,100)
Fingerprint (MD5) 1E371AC53749600F9DCD6519031A62DE 135F34EE36C547F5BB93E1BB5F4BF2A7 78D4EE3D58CCEA81770A469E02E6F2BB 1E371AC53749600F9DCD6519031A62DE 135F34EE36C547F5BB93E1BB5F4BF2A7 78D4EE3D58CCEA81770A469E02E6F2BB 1E371AC53749600F9DCD6519031A62DE 5166A20435CCC3DAECDFC7DE1A2E2C6C
Tabel 2 Hasil Shingle dan Fingerprint pada Contoh Citra Digital B Shingle 1 2 3 4 5 6 7 8 9 10 11
Isi Shingle RGB (200,100,100) RGB (40,40,40) RGB (100,200,120) RGB (50,50,50) RGB (100,200,120) RGB (200,100,100) RGB (100,200,120) RGB (40,40,40) RGB (100,200,120) RGB (200,100,100) RGB (100,200,120)
Fingerprint (MD5) RGB (40,40,40) RGB (100,200,120) RGB (50,50,50) RGB (100,200,120) RGB (200,100,100) RGB (100,200,120) RGB (40,40,40) RGB (100,200,120) RGB (200,100,100) RGB (100,200,120) RGB (200,100,100)
599428928438677F7BABC8A6574AF047 73D2E7A4A52C1C0C74916C22F0FDBD4B 714F15BFCFC1ADCD79525FD7B9FF9947 39EDF78E5049C842DA8B6592D6910B54 5166A20435CCC3DAECDFC7DE1A2E2C6C 1E371AC53749600F9DCD6519031A62DE 135F34EE36C547F5BB93E1BB5F4BF2A7 73D2E7A4A52C1C0C74916C22F0FDBD4B 5166A20435CCC3DAECDFC7DE1A2E2C6C 1E371AC53749600F9DCD6519031A62DE 5166A20435CCC3DAECDFC7DE1A2E2C6C
Perpotongan (intersection), adalah nilai fingerprint yang berada di citra digital A (Tabel 1) dan juga berada di citra digital B dari Tabel 1 dan Tabel 2 (Tabel 2). 1E371AC53749600F9DCD6519031A62DE 5166A20435CCC3DAECDFC7DE1A2E2C6C 135F34EE36C547F5BB93E1BB5F4BF2A7
Gabungan (union) diperoleh dengan cara menggabungkan nilai fingerprint citra digital A dan citra digital B, namun hanya nilai unik saja, sehingga tidak ada nilai fingerprint yang muncul lebih dari satu kali. 1E371AC53749600F9DCD6519031A62DE 5166A20435CCC3DAECDFC7DE1A2E2C6C 135F34EE36C547F5BB93E1BB5F4BF2A7 78D4EE3D58CCEA81770A469E02E6F2BB 599428928438677F7BABC8A6574AF047 73D2E7A4A52C1C0C74916C22F0FDBD4B 714F15BFCFC1ADCD79525FD7B9FF9947 39EDF78E5049C842DA8B6592D6910B54
Nilai kemiripan yaitu jumlah perpotongan dibagi jumlah gabungan dikalikan 100 %. (3 / 8) x 100% = 37.5%. Jadi citra digital A dan citra digital B memiliki nilai kemiripan sebesar 37.5%.
9
4.
Hasil dan Pembahasan
Pengembangan aplikasi dilakukan dengan menggunakan Visual Studio 2012 Express for Desktop. Visual Studio 2012 Express for Desktop merupakan satu dari serangkaian produk Microsoft yang dapat digunakan tanpa harus membayar lisensi. Di dalam Visual Studio sudah termasuk kerangka kerja pemrograman .Net Framework 4.5. Pustaka ini menyediakan pustaka-pustaka yang dapat digunakan untuk mengolah gambar, melakukan enkripsi/dekripsi, dan lain sebagainya.
Gambar 14 Hasil Deteksi Gambar 100% Mirip
Gambar 15 Hasil Deteksi Gambar 88.67% Mirip Hasil Proses Flip Kode Program 1 Perintah untuk membentuk suatu shingle 1. 2. 3. 4. 5. 6. 7. 8. 9.
for (int i = 0; i < jumlahShingle; i++) { byte[] shingle = new byte[gram]; Array.Copy(words, i, shingle, 0, shingle.Length); String hash = GetMd5Hash(md5, string.Join(" ", shingle)); s.Add(hash); }
Kode Program 1 merupakan perintah yang digunakan untuk membentuk suatu shingle. Panjang shingle ditentukan oleh variabel gram. Variabel ini bergantung dari masukan user. Kode Program 2 Perintah untuk Menghitung Fingerprint 1. 2. 3. 4. 5.
public static string GetMd5Hash( MD5 md5Hash, byte[] pixels) { byte[] data = md5Hash.ComputeHash(pixels); StringBuilder sBuilder = new StringBuilder();
10
6. 7. 8. 9. 10. 11. 12. }
for (int i = 0; i < data.Length; i++) { sBuilder.Append( data[i].ToString("x2")); } return sBuilder.ToString();
Pada Kode Program 2, untuk membangkitkan nilai fingerprint dari suatu shingle, digunakan algoritma MD5 (baris 13). Pada .Net Framework, tersedia class MD5, yang berfungsi untuk membangkitkan nilai hash/fingerprint dari inputstring. Class MD5 yang tersedia mengakibatkan proses pengembangan aplikasi menjadi lebih cepat karena tidak perlu menulis kode program sendiri. Selain itu, implementasi MD5 pada .Net Framework memberikan jaminan bahwa library tersebut berjalan optimal dalam sistem operasi Microsoft Windows. Kode Program 3 Perintah untuk Menghitung Nilai Prosentase Kemiripan 1 2 3 4 5 6
var fA = Fingerprints(docA); var fB = Fingerprints(docB); var intersect = fA.Intersect(fB); var union = fA.Union(fB); return (float)intersect.Count()/(float)union.Count();
Untuk menghitung nilai kemiripan dua citra digital sesuai dengan Persamaan 1, digunakan fungsi Intersect (baris 3) dan Union (baris 4). Kedua fungsi tersebut dapat digunakan pada sebuah variabel bertipe array (himpunan). Intersect merupakan fungsi untuk mencari elemen-elemen yang merupakan anggota dua himpunan. Union merupakan fungsi untuk menggabungkan dua himpunan. Menggunakan dua fungsi tersebut, maka dapat diperoleh angka kemiripan, yaitu dengan membagi angka jumlah himpunan hasil dari Intersect, dengan angka jumlah himpunan hasil Union. Beberapa pengujian dilakukan pada aplikasi untuk mengetahui hasil deteksi kemiripan gambar. Pengujian 1 yaitu pengujian gambar yang diskalakan (diperbesar/diperkecil). Hasil pengujian 1 ditunjukkan pada Tabel 3. No
Gambar A
Tabel 3 Hasil Pengujian 1 Gambar B Keterangan
1.
Skala 120%
11
Hasil Deteksi Kemiripan
72%
2.
Skala 150%
3.
70%
Skala 200% 68%
4.
Skala 80%
72%
Skala 50%
70%
Skala 25%
68%
5.
6.
Berdasarkan hasil pengujian 1, aplikasi dapat mendeteksi kemiripan gambar yang diperbesar/diperkecil, sampai dengan 72%. Pengujian 2 yaitu pengujian gambar yang diputar. Pengujian dilakukan terhadap beberapa gambar, yang dilakukan rotasi beberapa kali. Hasil pengujian 2 ditunjukkan pada Tabel 4. Tabel 4 Hasil Pengujian 2
No
Gambar A
Gambar B
1.
Keterangan Rotasi Kanan 90 derajat
12
Hasil Deteksi Kemiripan 56%
2.
Rotasi Kiri 90 derajat
57%
3.
Rotasi 180 derajat
78%
4.
Flip Horisontal
79%
5.
Flip Vertikal
88%
Berdasarkan hasil pengujian 2, aplikasi dapat mendeteksi kemiripan gambar hasil rotasi sampai dengan 88%. Pengujian 3 yaitu pengujian gambar yang dipotong sebagian. Pengujian dilakukan terhadap beberapa gambar, yang dipotong secara bervariasi. Hasil pengujian 3 ditunjukkan pada Tabel 5. Tabel 5 Hasil Pengujian 3
No
Gambar A
Gambar B
Keterangan
Hasil Deteksi Kemiripan 96%
1.
Crop 50x50 piksel
2.
Crop 75x75 piksel
91%
3.
Crop 100x100 piksel
85%
4.
Crop 150x150 piksel
66%
13
Crop 200x200 piksel
5.
39%
Berdasarkan hasil pengujian 3, aplikasi dapat mendeteksi kemiripan gambar yang dipotong, sampai dengan 96%. Nilai kemiripan bergantung pada berapa besar bagian gambar yang hilang karena dipotong. Pengujian 4 yaitu pengujian gambar yang diubah (manipulasi) sebagian. Pengujian dilakukan terhadap beberapa gambar yang dimanipulasi pada posisi yang berbeda-beda. Hasil pengujian 4 ditunjukkan pada Tabel 6. Tabel 6 Hasil Pengujian 4
No
Gambar A
Gambar B
Keterangan
1.
Diberi tulisan
Hasil Deteksi Kemiripan 96%
2.
Dimanipulasi
92%
3.
Dimanipulasi
86%
4.
Overlay
92%
5.
Grayscale
25%
Berdasarkan hasil pengujian 4, aplikasi dapat mendeteksi kemiripan gambar yang diubah nilai pikselnya, sampai dengan 96%. Nilai kemiripan bergantung pada besarnya piksel yang dimanipulasi. 5.
Simpulan
14
Berdasarkan penelitian, pengujian dan analisis terhadap sistem, maka dapat diambil kesimpulan sebagai berikut: (1) Deteksi kemiripan gambar dapat dilakukan dengan membandingkan nilai-nilai piksel gambar tersebut, dengan membentuk shingle-shingle; (2) Untuk memperkecil jumlah piksel dan shingle yang dibandingkan, maka dilakukan penghapusan piksel-piksel yang redundan. Piksel redundan adalah piksel yang bernilai sama dengan piksel sebelumnya; (3) Aplikasi dapat mendeteksi kemiripan gambar yang telah melalui berbagai manipulasi yaitu scaling (perbesar/perkecil), rotasi, cropping (potong sebagian), dan manipulasi piksel. Saran yang dapat diberikan untuk penelitian dan pengembangan lebih lanjut adalah proses pembentukan fingerprint dapat menggunakan algoritma hash yang lain. Tiap algoritma hash seperti CRC, MD5, SHA dan lain-lain memiliki keunggulan masing-masing. Aplikasi yang dihasilkan pada penelitian ini dapat dimanfaatkan untuk deteksi kemiripan foto, sebagai contoh pada bagian imigrasi, pencarian orang hilang, dan lain sebagainya. Proses pembandingan juga dapat mengabaikan bitplane yang rendah, semisal 4 bit paling kiri. Jadi proses pembandingan hanya dilakukan pada 4 bit terdepan, sehingga dapat mengurangi banyaknya data yang dibentuk menjadi shingle, dan juga mempercepat proses deteksi kemiripan. 6.
Daftar Pustaka
Montanari, D. & Puglisi, P. L. 2012. Near duplicate document detection for large information flows. In Multidisciplinary Research and Practice for Information Systems, pp. 203–217. Springer. [2]. Walia, A. G. N. K. 2014. Cryptography Algorithms: A Review. International Journal of Engineering Development and Research [3]. Chen, Z., Zhang, Y. & Delis, a. 2009. A Digest and Pattern MatchingBased Intrusion Detection Engine. The Computer Journal 52, 699–723. (doi:10.1093/comjnl/bxp026) [4]. Broder, A. 2000. Identifying and filtering near-duplicate documents. Combinatorial pattern matching , 1–10. [5]. Alatas, P. 2009. Implementasi Teknik Steganografi dengan Metode LSB pada Citra Digital. Universitas Gunadarma [6]. Fowler, H. R., Aaron, J. E. & others 2007. The little, brown handbook. Pearson Longman. [7]. Stein, B., Koppel, M. & Stamatatos, E. 2007. Plagiarism analysis, authorship identification, and near-duplicate detection PAN’07. In ACM SIGIR Forum, pp. 68–71. [8]. Wang, G. 2011. Collision attack for the hash function extended MD4. In Information and Communications Security, pp. 228–241. Springer. [9]. Parvez, M. T. & Gutub, A. A.-A. 2008. RGB Intensity Based Variable-Bits Image Steganography. IEEE Asia-Pacific Services Computing Conference , 1322–1327. [10]. Microsoft 2015. Overview of the .NET Framework. https://msdn.microsoft.com/id-id/library/zw4w595w(v=vs.110).aspx. [1].
15
Diakses pada 4 November 2015.
16
