Wednesday, October 22, 2014

Progress Skripsi: Metode Thresholding Sauvola

Di *UHUK* skripsi yang saya buat, saya perlu memproses gambar untuk dipisah menjadi foreground dan background. Dalam kasus saya yang perlu diproses adalah gambar dokumen form. Foregroundnya adalah tulisan dan backgroundnya adalah warna putih dari kertas. Metode ini disebut sebagai thresholding. Ternyata thresholdingnya sendiri banyak metode-metodenya loh! Salah satu metode yang bikin saya kagum namanya metode Sauvola.

Keabuan

Mari kita ngebahas keabuan dulu.

Umumnya gambar punya warna-warna yang banyak. Dalam image processing warna-warna ini biasanya dipisah dalam channel-channel yang berbeda. Contohnya yang paling sering saya pakai gambar dipisah jadi 3 channel yaitu RGB( Red, Green, dan Blue).

Di channel-channel ini terdapat nilai keabuan masing-masing. Nilai keabuan ini memiliki rentang dari 0-255. Representasinya bisa dibentuk jadi matriks yang punya masing-masing nilai keabuan di tiap elemen. Kalau pakai RGB jadinya satu piksel ada 3 nilai keabuan. Secara umum matriksnya bisa direpresentasikan berdimensi mxnxo.

Gambar dengan nilai RGB ini juga bisa dikonversi jadi gambar abu-abu saja (yang sering kita kenal sebagai grayscale) dengan aturan gini:

pixel_abu = pixel_r*0.299 + pixel_g*0.587 + pixel_b*0.114

Thresholding

Nah, kalau konversi grayscale mengubah dari gambar RGB jadi nilai keabuan saja, thresholding membuatnya lebih sederhana lagi. Metode thresholding membuat gambar dengan nilai keabuan menjadi gambar biner, yakni hitam dan putih saja.

Metode thresholding dibagi dua berdasarkan cakupan nilai thresholdnya. Global threshold dan local threshold. Kalau global threshold menggunakan nilai threshold untuk semua gambar, local threshold memiliki nilai threshold yang berbeda-beda di bagian-bagian gambarnya.

Nah, coba kita lihat perbedaannya masing-masing ya.

Metode Otsu

Salah satu metode global threshold yang umum dipakai adalah metode Otsu. Ide dasar dari thresholding ini adalah terdapat dua kelompok nilai keabuan. Nah, metode Otsu memberikan nilai threshold untuk memisahkan nilai tersebut.

Yang mau tahu lebih detilnya metode Otsu bisa lihat di wikipedia

Kelebihan dan Kekurangan Metode Otsu

Kalau cahayanya cukup merata, metode Otsu ini cukup baik loh untuk dipakai.


Sayangnya cahaya yang ada di citra tidak semulus paha Cherry Belle *halah*. Uh... maksudnya cahaya yang ada di kertas berbeda-beda intensitasnya. Misalnya kita punya gambar yang kayak gini

Kalau dilihat sekilas sih bagus-bagus aja ya, tapi itu intensitasnya berbeda-beda. Bagian kertas yang dekat dengan cahaya lebih terang dibandingkan dengan bawah. Nah, inilah kelemahan dari metode Otsu.
bagian yang dithreshold menjadi hitam seperti ini karena sebaran cahaya yang tidak merata

Metode... Uh... Galau...

Hal ini membuat saya galau berhari-hari. Saya bingung. Saya lelah. Saya hina. Aah. Aah.

Awalnya saya mencoba agar cahaya yang didapatkan merata. Caranya saya membuat instrumen sebuah kotak dilapisi kertas putih agar cahaya membias dan disinari dengan lampu emergency. Tapi ternyata bahkan dengan instrumen seperti ini mendapatkan gambar dengan cahaya yang merata tetap susah. Lampu yang saya gunakan tetap saja memberikan cahaya yang lebih terang di bagian depan. Kalau lampunya diletakkan di atas (misalnya digantung) nanti pas pakai kamera handphone cahayanya kehalangan handphone dong? Hmmm...

si kotak bercahaya
Dari kesimpulan saya, Otsu benar-benar memisahkan gambar menjadi dua kelas relatif berdasarkan gambar. Jadi walaupun gambarnya terlihat cukup terang bagian gambar yang lebih gelap akan dinyatakan sebagai background *hiks*. Nah lucunya kalau gambarnya tidak terlalu terang dan tidak terlalu gelap metode Otsu sukses untuk memisahkannya menjadi dua bagian.

Gambar yang cukup abu-abu ternyata bisa di threshold. Wah.
Akhirnya saya googling lagi dan ketemu dengan beragam keyword, antara lain threshold, local thresholding, dan adaptive thresholding.

Local Thresholding

Ternyata permasalahan dengan cahaya yang tidak merata adalah hal yang umum di thresholding. Banyak penelitian yang mengulas hal ini. Sub topik bidang ini dinamakan sebagai local thresholding. Kenapa local? Karena nilai threshold berbeda-beda di seluruh bagian gambar.
Ada teknik-teknik keren seperti Chow-Kaneko yang memotong-motong gambar dan diberikan thresholding dengan Otsu method pada masing-masing gambar, ada juga yang nyari rata-rata kebuan di sekeliling tiap-tiap pixel. Salah satu penelitian yang hasilnya menurut saya cukup bagus untuk digunakan di skripsi saya adalah metode Sauvola.

Metode Sauvola

Metode Sauvola sebenarnya pengembangan dari metode Niblack. Katanya Sauvola, metode Niblack itu dirumuskan gini:

T = m + k*s

dimana T itu nilai thresholdnya, m itu rata-rata keabuan, k konstanta, dan s itu standar deviasi.

Alamak, ternyata saya banyak ketemu statistika di image processing.

Eh, balik lagi. Jadi kata Sauvola nilai metode Niblack kurang memuaskan kalau gambar yang di threshold memiliki tekstur yang terang. Sauvola kemudian memodifikasi metode Niblack menjadi seperti ini:

T(x,y) = m(x,y) * (1+( k*( (s(x,y)/R)-1) ) );

dimana R adalah "dynamic range standard deviation". Di penelitiannya Sauvola nilai R itu paling bagus 128 dan k-nya 0.5;

Algoritma Sauvola

Heh, itu semua cuma rumus geje woy. Cara pakainya gimana?

Jadi algortima metode Sauvola tuh gini

  1. Untuk masing-masing piksel (Loop i dan j) telusuri sejauh n window, kita sebut piksel ini sebagai P_threshold. Hal ini dlakukan agar beban komputasi kecil. Besar n bebas. Semakin kecil n nya maka gambar yang memiliki keabuan merata akan dibuat menjadi background.
  2. Cari m dari sekeliling P_threshold.
  3. Cari s dari sekeliling P_threshold.
  4. Tentukan besar T dan simpan di matriks_threshold.
  5. end for (i dan j)!
  6. Untuk masing-masing piksel (Loop i dan j) telusuri lagi sejauh n window, kita sebut piksel ini sebagai P_abu.
  7. Untuk masing-masing piksel (Loop ii dan jj) dari i hingga n dan j hingga n (kita sebut piksel ini sebagai P_window).
  8. Cek apakah indeks i dan j tidak memiliki sisa bagi dengan n. Jika ada berarti merupakan piksel acuan. Tentukan keabuannya dari indeks di matriks_threshold. Tentukan nilai piksel berdasarkan T.
  9. Jika bukan merupakan piksel acuan kita cari rata-rata thresholdnya dengan rumus ini:
    T = (matriks_threshold[i][j]+ //titik kiri atas
    matriks_threshold[i][j+n]+ //titik kanan atas
    matriks_threshold[i+n][j]+ //titik kiri bawah
    matriks_threshold[i+n][j+n] //titik kanan bawah
    )/4;
    Tentukan nilai piksel berdasarkan T.


  10. end for (i dan j)!
  11. end for (ii dan jj)!
Udah deeeh. Itu algoritma umumnya. Kalau saya nambahin dikit algoritmanya untuk ngehandle kalau piksel P_abu ternyata mentok, kalau mentok berarti P_abu di sekelilingnya kurang dari 4.


Untuk penelitian saya menggunakan n = 30, R = 128, dan k = 0.3. Hasilnya cukup memuaskan loh

gambar yang sebelumnya jelek kalau di threshold dengan metode Otsu ternyata dengan metode Sauvola menghasilkan hasil yang bagus
Bahkan yang cukup ekstrim, yaitu gambar yang diambil menggunakan lampu blitz. Permasalahan di gambar ini adalah cahaya berada di tengah dan intensitasnya berubah menjadi gelap semakin ke arah luar.

Form yang diambil dengan lampu blitz

menggunakan metode Sauvola

menggunakan metode Otsu

Keep fighting! 


Yaay. Nah sekarang udahan buat image processingnya. Sekarang mari kita ulik lebih lanjut di Neural Networknya. Yuhu!

p.s: Kalau mau kasih semangat boleh loh komen-komen disini, huehue.

9 comments:

  1. Hmmm dari sudut pandang dsp, sebenernya kamu nyari high frequency seh...

    Sebenernya ada cara yang lebih gampang untuk ngerjain hal di atas
    High frequency = original frequency - low frequency...

    Untuk cari Low frequency tinggal di blur aja seh... *sebenernya kamu juga ngeblurin di algo kamu kan? Tapi gak make semua sample, maen skip n langkah :v... Kamu lebih pake downsampling seh menurut aku :v...

    Untuk lebih gampang ngertinya...
    Buka gambar itu di photoshop, duplikat layer, blur layer yang di atas *radiusnya itu kayak parameter n di algo kamu... Trus invert, ubah blending mode jadi add...
    Harusnya sama aja :v

    ReplyDelete
    Replies
    1. Iya juga ya, dia kan ngambil nilai dari piksel-piksel di sekelilingnya, kayak blur juga :p

      Delete
  2. Yups :v... It's basically blur...
    Ada banyak cara seh buat ngeblur... Cara yang paling aku suka pake algo ini...
    Jadi dibedain jadi 2 phase, blur horizontal sama blur vertikal...
    Untuk tiap phase...
    Kamu punya satu variable namain warna...
    Untuk tiap looping dari kiri ke kanan
    warna = warna * c + value
    c itu konstanta, dari 0 sampe 1, semakin gede, radius blurnya makin gede juga...
    Value itu warna pixel sekarang
    Dan warna itu warna blur untuk pixel sekarang
    Trus lakukan hal yang sama untuk vertikal

    ReplyDelete
  3. artikelnya menarik ga,,,
    boleh minta contoh programnya ga gan,,,
    ane belum terlalu paham nih sama alur kerja algoritmanya,,help gan buat tugas soalnya,,hehehhe,, kalau bisa kirim ke eganghukz@yahoo.co.id ya,,
    tank's banget nih gan,,,

    ReplyDelete
    Replies
    1. Whoops, maaf Egan saya belum bisa kasih.

      Kamu bisa mulai coba-coba dulu dari metode thresholding yang sederhana (misalnya otsu) terus bertahap yang agak rumit kayak Sauvola ini.

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. bang, algoritma thresholding ini bisa gak dipakai buat identifikasi penyakit kanker usus besar, citra yang digunakan dari sel jaringan yang diteliti menggunakan mikroskopik bg? terimakasih :)

    ReplyDelete
    Replies
    1. waduh, bisa mungkin, haha. dia gunanya untuk bikin citra jadi dua warna aja kok, bebas implementasinya mau gimana

      Delete
  6. mas bisakah minta email untuk penjelasan lebih lanjut ?

    ReplyDelete

Comment is caring :)