1

PENYEMBUNYIAN DATA REVERSIBLE CITRA MENGUNAKAN QUAD-TREE SEGMENTATION DAN HISTOGRAM

SHIFTING DUA POIN

Ananta Yudica Email: nta040689@gmail.com

Rojali

Afan Galih Salman

ABSTRAK

Skripsi ini berisi tentang mengaplikasikan teknik penyembunyian data secara reversibel ke dalam Android dengan menggunakan algoritma Histogram Shifting dan Quad-tree Segmentation. Pada algoritma Histogram Shifting ditambahkan titik maksimum dan minimum poin yang bertujuan untuk: menyembunyikan data berkapasitas tinggi, citra yang sudah diekstrak dapat dipakai kembali karena algoritma Histogram Shifting bersifat reversibel, dan distorsi yang dihasilkan relatip rendah setelah penyisipan (embedding) pesan rahasia. Kemudian digabungkan dengan skema (bagan) Segmentasi secara hirarki (Quad-tree Segmentation) yang dapat mempartisi secara hiraki citra input ke dalam beberapa ukuran blok berdasarkan piksel yang bervariasi dibawah nilai kriteria kapasitas maksimal (maximal capacity criterion) untuk setiap blok yang dipartisi. Blok-blok ini diorganisasikan menjadi sebuah struktur pohon (tree structure) untuk setiap yang direpresentasikan. Pesan rahasia dan informasi pohon (tree) partisi kemudian disisipkan kedalam blok-blok dari citra tersebut, dimana tiap-tiap blok tidak saling berhimpitan. dengan metode-metode tersebut yang akan diimplentasikan kedalam citra berwarna, diharapkan meningkatkan kapasitas penyisipan data secara signifikan. Kata kunci : histogram shifting, reversible data hiding, segmentasi quad-tree, Keamanan citra, android

ABSTRACT

Thesis is about applying techniques reversible data hiding into Android by using Histogram Shifting and Quad-tree Segmentation algorithms. In the algorithm Histogram Shifting added point maximum and minimum points are aimed at: a high-capacity data hiding, image has been extracted can be reused as Histogram Shifting reversible algorithm, and the resulting relatively low distortion after insertion (embedding) secret message. Then combined with the scheme in a hierarchical segmentation (Quad-tree Segmentation) which can partition the input image into a hierarchy multiple block sizes vary based on pixel values below the maximum capacity criterion (maximum capacity criterion) for each block of the partitioned. The blocks are organized into a tree structure (tree structure) for each represented. Secret message and information tree and then inserted into partition blocks of the image, where each block not coincide. by methods which will be implemented by the image into color, insertion of data is expected to increase the capacity significantly. Keywords : histogram shifting, reversible hiding the data, quad-tree segmentation, image security, android.

2

1. Pendahuluan (Lin & Li, 2011) Sebuah konten digital sangat mudah disebarluaskan di internet,

dibutuhkan sebuah cara untuk melindungi konten tersebut dari tindak ilegal atau keamanan konten itu sendiri. Beberapa para ahli telah menyajikan beberapa cara teknik penyembunyian data untuk menyisipkan data rahasia.

Namun pada beberapa skema penyembunyian data, medium (cover object) yang ingin memproteksi atau mengirim dari data tersimpan yang dirahasiakan, kemungkinan akan mengalami beberapa distorsi dan juga tidak dapat mentransformasikan kembali kepada format asli pada tahapan ekstraksi. Pada penggunaan citra yang sensitip, seperti halnya pada citra medis, citra pengindraan jarak jauh militer (remote sensing images), dan karya seni adalah sangat penting agar dapat menjamin bahwa konten media tersebut dapat dikembalikan kepada bentuk semula pada tahapan ekstraksi. 2. Metode Penelitian

2.1 Steganografi

Kata steganografi (steganography) berasal dari bahasa Yunani yaitu steganos yang artinya tersembunyi atau terselubung dan graphein, yang artinya menulis, sehingga kurang lebih artinya adalah “menulis tulisan yang tersembunyi atau terselubung” (Sellars, 1996).

Steganografi (steganography) adalah ilmu dan seni menyembunyikan pesan rahasia (hiding message) sedemikian sehingga keberadaan (eksistensi) pesan tidak terdeteksi oleh indera manusia (Munir, 2004)

Steganografi adalah tindakan komunikasi rahasia, yang berarti bahwa hanya pengirim, Alice, dan penerima, Bob, menyadari komunikasi rahasia. Untuk mencapai hal ini, pesan rahasia yang tersembunyi dalam media komunikasi dikenal sebagai covertexts atau coverwork. Untuk seorang Eve, jelas bahwa Alice dan Bob berkomunikasi, tetapi covertext gabungan dan tersembunyi pesan, disebut sebagai stegotext atau stegowork, tampaknya tidak berbahaya (misalnya, Eve tidak menyadari bahwa konten menyembunyikan pesan). (Cox, Miller, Bloom, Fridrich, & Kalker, 2008)

Properti Steganografi: • Embedded message (hidden-text): Pesan yang disembunyikan. • Cover-object(cover-text): Media yang digunakan untuk menyembunyikan pesan. • Stego-object (stego-text): Media yang sudah berisi pesan. • Stego-key: Kunci yang digunakan untuk menyisipan pesan dan mengekstraksi

pesan dari stegotext.

3

2.2 Metode Histrogram Shifting

Teknik Histogram Shifting yang dikemukakan (Ni, Shi, Ansari, & Su, 2006) adalah menyisipkan data dengan menggeser rangkaian histogram. Secara garis besarnya adalah sebagai berikut :

Langkah pertama : Merekonstruksi histogram citra dari citra pembungkus cover image untuk mendapatkan pasangan titik puncak (peak point) dan titik nol (zero point).

Langkah kedua : Data disisipkan dengan meng-shifting rangkaian histogram. Karena kesederhanaan teknik ini, sehingga menjadi satu teknik yang paling populer dalam bidang penyembunyian data reversibel (reversible data hiding).

Sedangkan untuk algoritma penyisipan dengan dua poin sebagai berikut: Input : Original-image (8-bit grayscale) dengan , dan pesan rahasia .

Output : Stego-image , titik maksimum

Step 1 : Membuat Histrogram

Step 2 : Didalam Histrogram : mencari titik maksimum ,

, dan mencari titik minimum

, dari citra awal .

Step 3 : Jika titik minimum atau , maka simpan koordinat

dari piksel atau , dan nilai sebagai informasi pembukuan di

overhead kemudian set .

Proses Embedding

Proses Extracting

Pengirim(A) Penerima(B)

Stego-object Cover Cover*

Message Message

Key Key

Gambar 1 Sistem Stegonografi

4

Step 4: Tanpa kehilangan generalitas, kita asumsikan , pindahkan semua bagian

dari Histrogram dengan , ke kanan 1 unit, dan ,

pindahkan semua bagian dari Histrogram dengan , ke kiri 1

unit.

Step 5 : Memindai citra, setelah memenuhi piksel grayscale yang nilai adalah dan ,

memeriksa bit yang akan disisipkan. Jika bit yang akan disisipkan adalah 1, maka nilai piksel grayscale diubah ke atau . jika bit adalah

0,maka nilai piksel tetap .

(a)

(b)

5

(c)

Gambar 2 Alur dari Metode Shifting Dengan Dua Poin, (a) Awal Citra, (b) Histogram Shifting, (c) Penyisipan bit

Sedangkan untuk algoritma mengeskrak dengan dua poin sebagai berikut:

Input : Stego-image , titik maksimum

Output : Original-image Step 1: Memindai citra yang ditandai dalam urutan yang sama seperti yang digunakan

dalam prosedur Embedding. jika nilai piksel grayscale atau

ditemui, bit 1 diekstrak. nilai piksel grayscale atau ditemui, bit 0

diekstrak. Kemudian didapat dan .

Step 2: Memindai citra lagi, untuk setiap nilai piksel yang grayscale , nilai

piksel dikurangi 1.

6

Step 3: Jika di overhead ada informasi pembukuan ( ) atau ( yang

ditemukan pada saat data diekstrak, set nilai piksel grayscale koordinat

sebagai nilai atau . Dengan metode ini, citra dapat dipulihkan tanpa distorsi

apa pun.

Gambar 3 Flowchart Proses Menyisipkan Histogram Shifting.

7

Gambar 4 Flowchart Proses Mengesktrak Histogram Shifting.

2.3 Quad-tree segmentation

Quad-tree segmentation adalah teknik yang membagi blok sebuah citra menjadi 4 bagian yang tidak tumpang tindih dan setiap 4 sub-blok dapat dibagi lagi hingga seterusnya sesuai dengan aturan struktur tree (atau hirarki) pendekatan segmentasi atau pembagian blok.

Tujuan algoritma ini agar saat Histogram Shifting didapat blok yang kontrasnya lebih rendah. Karena sifat teknik Histrogram Shifting blok kontras yang lebih rendah dapat menampung lebih banyak bit data rahasia, sementara blok kontras yang lebih tinggi menampung relatif lebih sedikit bit data rahasia. Oleh karena itu, blok kontras yang lebih tinggi perlu untuk dipartisi atau dibagi menjadi sub-blok yang lebih kecil dan menyediakan kapasitas yang lebih besar bit data rahasia.

8

(a)

(b)

(c)

Gambar 5 Contoh Quad-tree segmentation sederhana. (a)Citra yang sudah di Segmentation, (b)Struktur Quad-tree Segmentation pada citra, (c) Quad-tree segmentation

9

Penjelasan definisi simbol yang digunakan pada algorima ini: • Citra yang input dilambangkan dengan atau

• : Struktur Quad-tree yang digunakan untuk mewakili proses blok

• : Variabel biner yang menunjukan apakah telah dibagi atau

tidak. Set , jika memutuskan untuk dibagi, jika

tidak set .

• :Fungi membuat Histrogram yang dihitung menurut blok .

• : Fungsi menghitung kapasitas penyisipan dari .

• : Tingkatan(level) pada Quad-tree.

• : Posisi blok pada level

Pada pengimplementasian metode ini, penulis menggunakan media citra yang berwarna. Maka setiap kanal warna(RGB) pada citra yang sudah di-Histogram Shifting. Kapasitas penyembunyian data (pure payload) yang akan dihasilkan pada satu blok. Kapasitas dihitung sebagai berikut:

Pada awalnya asumsikan bahwa citra adalah 8-bit matriks dua dimensi

bilangan bulat berukuran oleh .

Input : Citra (8-bit grayscale) dengan .

Output : Struktur Quad-tree segmentation dan Citra (8-bit grayscale) dengan .

Step 1 : Jika , maka bagi menjadi 4 blok

yaitu . Set , kirim ke step 2.

Step 2 : Jika kirim ke step 3. dan jika

kirim ke step 4.

10

Step 3 : Bagi menjadi 4 blok , set Set ,

dan krim ke Step 2.

Step 4 : Set , jika sisa 0 maka kirim ke step 5. jika

sisa bukan 0 maka kirim ke Step 2.

Step 5 : Jika , maka kirim ke Step 4. Jika maka algoritma selesai.

Untuk menghubungkan tiap blok data yang tesembunyi pada tiap kanal warna(RGB) dan puncak . Dimana tiap blok yang dihasilkan Quad-tree

segmentation, dan Histogram shifting pada seluruh citra ,maka dibutukan informasi yang menghubungkan kesemuanya itu. Hubungan antar blok dan Histogram Shifting untuk data yang disembunyikan, dengan Histogram Shifting untuk bit Quad-Tree Segmentation terlihat pada gambar berikut:

Gambar 6 Hubungan antar Informasi Overhead 2 dengan Overhead 1

11

Gambar 7 Gambar 2.8 Hubungan Informasi antar Blok di Overhead1

Dari gambar diatas besar bit yang dibutuhkan untuk next a, next b, banyak b,dan len bit pesan sebesar 8 bit untuk masing-masing, jadi total 32 bit dan sisanya sesuai dengan kebutuhan yang ada.

Satu blok dapat dihitung besar daya tampung bit data yang tersisipkan ( payload Size) sebagai berikut:

Dan total bit yang dapat ditampung dalam sebuah citra sebagai berikut:

Proses penyisipan dan ekstraksi adalah pengembangan metode Histogram Shifting yang ada, bisa dilihat pada gambar flowchart berikut ini:

12

Gambar 9 Flowchart Proses menyisipkan

13

Gambar 10 Flowchart Proses Mengekstrak

14

3. Hasil Dan Bahasan

(a) Lenna

(b) F-16

\ (c) House

(d) girl3

(e) Peppers

(f) Baboon

Gambar 11 Tes Citra

Untuk pesan yang akan disisipkan pada test citra bisa dilihat sebagai berikut:

Tabel 1 Pesan Input

Tipe input filename Besar bit Pesan - 128 Data test-1.txt 1024+80 Data test-2.gif 13392 +80

Sebelum melakukan proses menyisipkan program melakukan proses Quad-tree Segmentation terhadap citra. Hasil dari proses Quad-tree Segmentation menghasilkan maksimum bit dan struktur bit Quad-tree Segmentation, dan hasil proses Quad-tree Segmentation bisa dilihat pada Error! Reference source not found..

15

Tabel 2 Struktur bit Quad-tree dari Proses Quad-tree Segmentation

Citra Size Perkiraan Maksimum bit

Struktur bit Quad-tree Segmentation

Lenna 474,42 Kb 48040 1110100000001000010000110100000010000010000110000100001000010000110000100001000010000

F-16 419,25 Kb 103864 11100001100000100000100001100000010000110000010000101000010000011001000001010000100000110000010000011000001000010000110000100001100000100000100100000

House 451,97 Kb 92000 11100000110000010000100000110000100010000100001000011100000100001000010000110000100001000010000100001100001001000000101000000

Girl3 326,48 Kb 74360 11110000100001000010000110000100001000010000101000010000100001100001000001000011100001000010000100001100001000010000100001100001000000110000100000011100001000010000010000110000100000010010000011000100001010000010000100100000100010000

Peppers 374,39 Kb 35920 1110000100001000010000110000100001000011000000011000001000010000110000100001000010000

Baboon 498,59 Kb 20832 11000011000010000010000100001100001000000

Setelah Proses Quad-tree Segmentation didapatlah Struktur bit Quad-tree, maka citra yang diinput akan dibagi-bagi atau dipartisi(Segmentation).

Gambar 12 Segmentation pada Citra Lenna

16

Tabel 3 Hasil PSNR dan Waktu Proses dari menyisipkan Pesan

Pesan test-1.txt test-2.gif

Lenna 58,23 dB

(18 detik)

58,22 dB

(18 detik)

53,43 dB

(19 detik)

F-16 58,34 dB

(20 detik)

27,82 dB

(20 detik)

54,54 dB

(20 detik)

House 59,07 dB

(18 detik)

57,81 dB

(18 detik)

55,03 dB

(19 detik)

Girl3 64,36 dB

(21 detik)

63,90 dB

(21 detik)

58,41 dB

(22 detik)

Peppers 57,91 dB

(19 detik)

57,35 dB

(19 detik)

54,42 dB

(22 detik)

Baboon 59,29 dB

(17 detik)

57,23 dB

(17 detik)

50,93 dB

(22 detik)

Gambar 13 Grafik Hasil PSNR dari citra Lenna terhadat banyak bit yang disisipkan

17

4. SIMPULAN DAN SARAN

4.1 Kesimpulan

Beberapa kesimpulan yang diperoleh dari penulisan skripsi ini adalah sebagai berikut:

• Program aplikasi yang dibuat dapat menyisipkan pesan text atau pesan data ke dalam citra bertipe .jpg atau .jpeg.

• Program aplikasi dapat mengekstrak citra warna yang telah disisipkan terlebih dahulu.

• Penambahan titik maksimum dan minimum pada metode Histogram Shifting dapat dilakukan.

• Mengimplentasikan metode Quad-tree Segmentation pada citra berwarna dapat mengoptimalkan besar size Payload.

• Hasil dari stego citra dikatagorikan dengan sangat baik karena hasil rata-rata PSNR dari citra stego dan citra original .

• Citra Stego dapat dikembalikan ke awal sebelum citra disisipkan pesan (reversible).

4.2 Saran

Beberapa saran yang diajukan dengan kemungkinan dilakukan pengembangan lebih lanjut adalah sebagai berikut: • Mengembangkan pada n titik maksimum dan minimum pada metode Histogram

Shifting. • Menyesuaikan kebutuhan size pesan (Payload) dengan Quad-tree segmentation

agar lebih cepat dalam proses.

18

5. REFERENSI

android. (2011, May 16). Sejarah Android OS. Dipetik September 1, 2012, dari Aplikasi

Android: http://aplikasiandroid.com/berita-android-2/sejarah-android-os/ Conzalez, R. C., & Woods, R. E. (2008). Digital Image Processing Third Edition.

Prentice Hall. Cox, I. J., Miller, M. L., Bloom, J. A., Fridrich, J., & Kalker, T. (2008). Digital

Watermarking and Steganography, Second Edition. Morgan Kaufmann. Cummins, J., Diskin, P., Lau, S., & Parlett, R. (2004). Steganography and Digital

Watermarking. H, N. S. (2011). Android. Bandung: Informatika. Hong, W., Chen, T. S., Lin, K. Y., & Chiang, W. C. (2010). A Modified Histrogram

Shifting Based Reversible Data Hiding Scheme for High Quality Images. Information Technology Jurnal, 9, 179-183.

Kumar, A., & Pooja, K. (2010). Steganography- A Data Hiding Technique.

International Journal of Computer Applications, vol. 9, no. 7, 19-23. Lin, Y.-C., & Li, T.-S. (2011). Reversible Image Data Hiding Using Quad-tree

Segmentation and Histogram Shifting. Journal of Multimedia, vol. 6, no. 4, 349-358.

Munir, R. (2004). Steganografi dan Watermarking. Departemen Teknik Informatika

Institut Teknologi Bandung. Ni, Z., Shi, Y.-Q., Ansari, N., & Su, W. (2006). Reversible Data Hiding. IEEE

Transaction on Circuits and Systems for Video Technology, vol. 16, no. 3, 354-362.

The MathWorks, Inc. (1994-2012). Compute peak signal-to-noise ratio (PSNR) between

images. Dipetik September 1, 2012, dari MathWorks: http://www.mathworks.com/help/vision/ref/psnr.html

Tian, J. (2003). Reversible Data Embedding Using a Difference Expansion. IEEE

Transactions on Circuits and Systems for Video Technology, vol. 13, no. 8, 890-897.

Varsaki, E., Fotopoulos, V., & Skodras, N. (2006). A reversible data hiding technique

embedding in the image histogram. Hallenic Open University.

xix

6. RIWAYAT PENULIS Ananta Yudica lahir di Jakarta pada tanggal 4 juni 1989 Penulis menamatkan pendidikan S1 du Universitas Bina Nusantara dalam bidang Matematika dan Teknik Informatika pada tahun 2013.