ALGORITMA THRESHOLDING ADAPTIF BERDASARKAN DETEKSI BLOK TERHADAP CITRA DOKUMEN TERDEGRADASI Agus Zainal Arifin, Arya Yudhi Wijaya, Laili Cahyani1 1
Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS), Surabaya, 60111, Indonesia E-mail :
[email protected]
algoritma thresholding telah dikembangkan untuk citra dokumen terdegradasi[1]. Berdasarkan teknik yang ada saat ini, thresholding dapat diklasifikasikan menjadi dua, yaitu thresholding global dan thresholding lokal (adaptif). Metode thresholding global memperkirakan dan menerapkan threshold tunggal untuk seluruh piksel citra. Sahoo dkk.[2] telah melakukan perbandingan dengan menggunakan pengukuran bentuk atau uniformity terhadap efektifitas metode yang diusulkan oleh Otsu[3], Tsai, Johannsen, dan Kapur dalam mendapatkan hasil thresholding yang memadai. Namun demikian, metodemetode ini kurang efektif untuk mendapatkan hasil yang sesuai ketika citra memiliki beragam bentuk background. Maka banyak peneliti berusaha untuk mengatasi masalah ini dengan menggunakan metode lokal. Dalam metode thresholding lokal, nilai threshold ditentukan untuk setiap piksel berdasarkan nilai grayscale sendiri dan nilai grayscale tetangga. Oleh karena itu, pendekatan ini disebut algoritma thresholding adaptif. Beberapa algoritma thresholding adaptif telah dikembangkan, diantaranya adalah metode Niblack [4] pada tahun 1986. Namun, metode Niblack tidak efektif ketika background berisi tekstur berupa cahaya. Pada tahun 2000, Sauvola [5] menyusun metode yang memodifikasi metode Niblack dengan melakukan hipotesis pada nilai keabuan piksel teks dan piksel background. Pada tahun 2004, Sezgin dan Sankur[6] melakukan perbandingan terhadap 40 metode. Hal itu menunjukkan bahwa metode thresholding lokal Sauvola dan metode dari Trier melakukan yang terbaik untuk proses thresholding dokumen. Kemudian Gatos dkk.[7] menemukan metode thresholding lokal lainnya untuk citra dokumen berkualitas rendah. Dengan menggunakan metode Sauvola, metode Gato melakukan deteksi foreground dan melanjutkannya dengan beberapa langkah post-processing untuk meningkatkan hasil akhir. Meskipun menawarkan hasil yang memuaskan untuk dokumen terdegradasi, pendekatan lokal tersebut memiliki biaya komputasi yang tinggi karena harus memperkirakan nilai threshold untuk setiap piksel.
ABSTRAK Saat ini, keberadaan citra dokumen yang mengalami degradasi dapat menjadi masalah tersendiri untuk melakukan suatu penelitian. Banyak metode yang sudah dikembangkan. Namun, kebanyakan metode hanya memperhatikan perbaikan kualitas saja tanpa memperhatikan efisiensi waktu. Tugas akhir ini melakukan implementasi sebuah algoritma thresholding secara adaptif terhadap citra dokumen terdegradasi. Dengan menggabungkan keuntungan metode global dan lokal, algoritma ini membagi citra dokumen menjadi beberapa blok. Kemudian proses thresholding dilakukan pada tiap blok citra untuk mendapatkan hasil berupa citra biner. Kinerja dari aplikasi ini akan diukur menggunakan aplikasi Optical Character Recognition (OCR) dengan menghitung keakuratan pembacaan teks hasil thresholding. Akhirnya, metode ini menghasilkan suatu pemisahan yang baik antara teks dan background. Percobaan juga menunjukkan bahwa metode ini mampu menghasilkan kinerja yang lebih unggul dari metode sebelumnya. Rata-rata keakuratan thresholding dari semua percobaan mencapai 93%. Kata kunci : Degradasi, deteksi ukuran blok, thresholding, binerisasi adaptif. 1
PENDAHULUAN Saat ini beberapa aplikasi memerlukan pengenalan karakter, seperti aplikasi OCR (optical character recognition). Pada proses pemisahan karakter dan background, thresholding citra dokumen melibatkan proses konversi citra grayscale menjadi citra biner[1]. Proses thresholding telah diterima cukup intens selama tiga dekade terakhir. Meskipun banyak algoritma telah diusulkan untuk gambar berintensitas seragam, namun thresholding agak rumit ketika harus memproses gambar dokumen yang mengalami degradasi. Degradasi dapat disebabkan oleh beberapa hal, diantaranya background yang kompleks, intensitas yang tidak seragam, dan bayangan pada citra. Untuk mengatasi hal ini, beberapa
1
melakukan perkiraan periode dari kurva yang dihasilkan oleh proyeksi horisontal H ( y ) berdasarkan langkah-langkah sebagai berikut : 1. R ( y ) merupakan kurva periodik
Oleh karena adanya manfaat dan keterbatasan yang ada pada setiap metode dan kebanyakan hanya memperhatikan perbaikan kualitas tanpa memperhatikan efisiensi waktu, maka Tugas Akhir ini mengimplementasikan algoritma thresholding berdasarkan deteksi blok untuk mengatasi permasalahan tersebut. Deteksi blok dilakukan untuk melakukan thresholding secara adaptif dan thresholding menggunakan metode global digunakan untuk mendapatkan waktu yang efisien. Sehingga proses thresholding citra dokumen terdegradasi dapat menghasilkan keluaran yang baik dalam waktu efisien. 2
τ
, yang dengan periode dirumuskan sebagai berikut
Rτ ( y) = max[H ( y)].[sgn[sin( 2. Varians dari Rτ (y ) didapatkan dengan persamaan berikut:
σ ε2 =
METODE
1 N
dapat
2πy
τ
)] + 1]
(2.3) dan H ( y ) menghitung 2
N
∑ [Rτ ( y ) − H ( y )]
(2.4)
y =1
2.1 Proyeksi Horisontal
dimana N merupakan jumlah kolom
Proyeksi horisontal dilakukan untuk mengenali karakteristik citra masukan yang akan diproses. Sehingga, hal ini dapat memudahkan proses pemisahan antara piksel karakter dan piksel background. Persamaan 2.1 adalah persamaan yang menunjukkan perumusan proyeksi horisontal.
citra.
ε
(2.1)
dimana merupakan intensitas keabuan tiap piksel citra berukuran M×N dan (x,y) merupakan koordinat tiap piksel. Hasil kurva proyeksi horisontal dapat dilihat pada Gambar 3.1. Secara normal nilai piksel karakter harus lebih rendah daripada nilai dari piksel background. Lembah dan puncak dari hasil representasi kurva proyeksi horisontal merupakan akumulasi nilai-nilai dari piksel karakter dan background. Sehingga dapat terlihat bahwa daerah karakter dapat dipisahkan dari daerah background.
2.3 Deteksi Ukuran Blok Beberapa tahapan untuk melakukan deteksi ukuran blok adalah mencari turunan pertama dari kurva Hs ( y ) , mencari titik (3.3) ekstrim dari turunan pertama, mencari nilai dari inflection point, dan mencari ukuran blok. Langkah awal yang dilakukan adalah mencari turunan pertama dari kurva Hs ( y ) . Pencarian turunan pertama dilakukan untuk mendapatkan gradient atau kemiringan kurva. Hal ini dapat menunjukkan karakteristik dari citra sehingga pada proses berikutnya dapat dilakukan pemisahan antara karakter dan background berdasarkan intensitas keabuan citra masukan, baik sebagai wilayah karakter atau background. Turunan pertama dari kurva Hs ( y ) dirumuskan oleh persamaan 2.5, sedangkan kurva hasil turunan pertama dapat dilihat pada Gambar 1.
2.2 Smoothing Filter Smoothing filter dilakukan untuk memperbaiki nilai kontras yang tidak merata sebab adanya noise yang muncul, sehingga dapat menghalangi proses pemisahan antara piksel karakter dan background. Smoothing filter juga dilakukan untuk menjaga informasi penting dari dokumen agar tidak banyak yang hilang selama proses thresholding. Perumusan smoothing filter yang digunakan dapat dilihat pada persamaan 2.2
Hs ( y ) =
m 2
1 ∑ H (k ), m k= y− m
dan
3. Ukuran smoothing window m dapat didefinisikan sebagai nilai yang dihasilkan pada varians minimal σ ε2 yang diperoleh. Hasil keluaran proses smoothing filter sekaligus merupakan keluaran akhir pada preprocessing ini berupa matriks Hsy sebagai representasi dari kurva yang lebih halus (smooth) dibandingkan dengan kurva H ( y ) . Matriks Hsy ini yang akan menjadi masukan untuk proses deteksi ukuran blok.
x =1
y+
ε = 12 τ
N 0<ε < 2
M
H ( y) = ∑ f ( x, y ),
Sedangkan,
(2.2)
H's ( y) =
2
dimana m merupakan ukuran dari smoothing window. Ukuran window ditentukan dengan
dHs(y) Hs(y+1)−Hs(y) = =Hs(y+1)−Hs(y) dy (y+1)−y (2.5)
2
Gambar 1 Ilustrasi Proses Segmentasi Citra.
Citra masukan yang berupa citra grayscale dibagi menjadi beberapa blok berdasarkan jarak yang telah didapatkan pada proses deteksi ukuran blok sebelumnya. Pertama daerah citra masukan dipisahkan ke dalam n – 1 bagian sub-region ( , , ..., ). Tiap bagian sub-region terdiri dari piksel. Tiap bagian sub-region dibagi menjadi kumpulan blok. Tiap blok terdiri dari piksel. Ukuran blok pada tiap bagian sub-region bervariasi sesuai jarak Hasil dari segmentasi citra adalah citra yang terbagi menjadi sub-region citra. Ilustrasi pada Gambar 1 adalah hasil segmentasi citra.
Langkah berikutnya adalah mencari titik ekstrim dari turunan pertama, yaitu titik dimana kurva asal berada pada nilai maksimum atau minimum. Pada Gambar 3.1, titik ekstrim ditunjukkan sebagai deret yang dapat didefinisikan Y = {Y j 0 < j < n } sebagai titik dimana nilai turunan pertamanya adalah nol. Setelah didapatkan deret Y sebagai titik ekstrim, maka langkah selanjutnya yaitu mencari inflection point. Inflection point P = {P j 1 < j < n }didapatkan antara indeks Yj dan Yj+1. Berikut ini adalah perumusan inflection point yang digunakan untuk proses deteksi ukuran blok (2.5) P j = max H s' ,
{ }
Y j < Y < Y j +1
'
dimana H s merupakan nilai turunan pertama yang telah didapatkan pada kurva sebelumnya. Nilai turunan yang maksimal pada kurva turunan menunjukkan bahwa gradient/kemiringan paling besar. Gradient ini didefinisikan sebagai adanya perubahan kontras yang terjadi pada tingkat keabuan dari piksel-piksel citra. Sehingga terdapat batas yang dijadikan pemisah antara region karakter dan region background. Inflection point merupakan titik batas yang digunakan antara wilayah karakter dan background. Sehingga langkah berikutnya adalah menghitung jarak antara tiap inflection point yang didapatkan. Jarak tersebut akan menjadi ukuran blok untuk proses segmentasi citra di tahap berikutnya. Jarak ini juga didefinisikan sebagai tinggi tiap wilayah karakter dan background, serta dijadikan sebagai input paramater pada proses segmentasi. Perumusan jarak yang dilakukan berdasarkan persamaan 2.6. (2.6) D j = Pj +1 − Pj .
Gambar 2 Ilustrasi Proses Segmentasi Citra.
2.5 Thresholding Citra Proses berikutnya dalam pengimplementasian algoritma thresholding adaptif berdasarkan deteksi blok ini adalah proses thresholding citra. Pada proses deteksi blok yang menjadi data masukan adalah hasil citra yang telah tersegmentasi. Proses ini membutuhkan inisialisasi nilai mean dan standar deviasi yang digunakan sebagai threshold. Pertama yang dilakukan terhadap citra yang telah terbagi menjadi beberapa blok tersebut yaitu menghitung nilai local mean dan local standar deviasi. Local mean dan local standar deviasi dihitung untuk tiap blok serta digunakan untuk menentukan apakah suatu blok perlu diproses dengan threshold adaptif
2.4 Segmentasi Citra 3
atau tidak. Kemudian nilai local mean dan local standar deviasi pada tiap blok dibandingkan dengan mean threshold dan standar deviasi threshold. Jika nilai local standar deviasi lebih rendah daripada standar deviasi threshold dan local mean lebih tinggi daripada mean threshold, maka setiap piksel dalam blok tersebut disubtitusikan dengan piksel background(1). Sebaliknya, jika tidak maka untuk tiap blok dilakukan proses binerisasi citra dengan metode global (metode otsu). Metode otsu digunakan karena kecepatannya dalam melakukan proses thresholding secara global.
F=
2 * ( PRC * RCL) ( PRC + RCL)
citra3
citra4
3.1 Uji Coba Parameter Ada dua buah parameter yang cukup penting untuk digunakan dalam implementasi algoritma thresholding adaptif berdasarkan deteksi blok, yaitu. 1. Parameter mean threshold 2. Parameter standar deviasi threshold
UJI COBA DAN EVALUASI Terdapat dua macam uji coba yang dilakukan, yaitu uji coba parameter dan uji coba perbandingan metode. Uji coba parameter dilakukan untuk mendapatkan parameter yang sesuai untuk algoritma thresholding adaptif berdasarkan deteksi blok ini, sedangkan uji coba perbandingan metode dilakukan untuk mengetahui seberapa unggul algoritma thresholding adaptif berdasarkan deteksi blok dibandingkan dengan metode yang dikembangkan sebelumnya, yaitu Otsu, Niblack, dan Sauvola. Sebagai data masukan untuk uji coba parameter, digunakan 4 macam data citra dokumen dengan degradasi yang berbeda seperti ditunjukkan pada Gambar 3. Sedangkan untuk melakukan uji coba perbandingan metode, digunakan 8 macam sampel data citra dokumen terdegradasi. Evaluasi dilakukan dengan menjadikan citra hasil thresholding sebagai masukan pada software OCR untuk mengukur kemampuan aplikasi dalam melakukan pengenalan karakter. Istilah berikut akan menjelaskan kriteria pada tiap tabel uji coba berikutnya. • DB: karakter (huruf, angka, atau tanda baca) yang terdeteksi benar oleh OCR, • DS: karakter yang terdeteksi namun merupakan kesalahan pengenalan oleh OCR, • TT: total karakter keseluruhan, • PRC: pengukuran secara precision, • RCL: pengukuran secara recall, • F: rata-rata harmonis antara precision dan recall. DB , (3.1) PRC = ( DB + DS ) DB , TT
citra2
Gambar 3 Data Citra Uji Coba Parameter
3
RCL =
citra1
3.1.1 Uji Coba dan Evaluasi Parameter Mean Uji coba parameter mean yang dilakukan terhadap citra uji 1 dengan menggunakan 10 nilai mean menghasilkan kinerja seperti ditunjukkan pada Tabel 1. Demikian juga pada data citra uji 2, 3, dan 4 sehingga menghasilkan nilai mean threshold optimal yaitu 40. Tabel 1 Evaluasi Uji Coba Parameter Mean Citra Uji 1 Kriteria meant DB DS TT PRC RCL F 100 346 31 359 91.78 96.38 94.02 90 349 21 359 94.32 97.21 95.75 80 355 21 359 94.41 98.89 96.60 70 355 13 359 96.47 98.89 97.66 60 355 12 359 96.73 98.89 97.80 50 358 5 359 98.62 99.72 99.17 40 356 1 359 99.72 99.16 99.44 30 356 1 359 99.72 99.16 99.44 20 356 1 359 99.72 99.16 99.44 10 356 1 359 99.72 99.16 99.44
3.1.2 Uji Coba dan Evaluasi Parameter Standar deviasi Tabel 2 Evaluasi Uji Coba Parameter Standar deviasi Citra Uji 1 Kriteria stdT DB DS TT PRC RCL F 20 258 10 359 96.29 71.87 82.30 18 268 18 359 93.71 74.65 83.10 16 286 21 359 93.16 79.67 85.89 14 313 14 359 95.72 87.19 91.25 12 330 19 359 94.56 91.92 93.22 10 357 1 359 99.72 99.44 99.58 8 357 2 359 99.44 99.44 99.44 6 358 2 359 99.44 99.72 99.58 4 355 18 359 95.17 98.89 96.99 2 346 23 359 93.77 96.38 95.05
(3.2) (3.3)
4
Uji coba parameter standar deviasi yang dilakukan terhadap citra uji 1 dengan menggunakan 10 nilai standar deviasi menghasilkan kinerja seperti ditunjukkan pada Tabel 2. Demikian juga terhadap data citra uji 2, 3, dan 4 sehingga menghasilkan nilai standar deviasi threshold optimal yaitu 10.
Tabel 3 Evaluasi Uji Coba Perbandingan Metode Adaptif Blok dan Otsu
Terdapat tiga metode yang digunakan sebagai pembanding untuk melakukan uji coba perbandingan metode, yaitu : 1. Metode global Otsu 2. Metode adaptif Niblack 3. Metode adaptif Sauvola
Adaptif Blok
Otsu
Adaptif Blok
Otsu
Citra III
Otsu
3.2 Uji Coba Perbandingan Metode
Citra II
Adaptif Blok
Kriteria Uji Coba
Citra I
DB
219
56
51
49
32
12
DS
0
6
8
9
0
2
TT
219
219
52
52
32
32
PRC RCL
100 100
90.3 25.6
86.4 98.1
84.5 94.2
100 100
85.7 37.5
F
100
39.8
91.9
89.1
100
52.2
Tabel 4 Evaluasi Uji Coba Perbandingan Metode Adaptif Blok dan Niblack
Adaptif Blok
Niblack
Gambar3 Hasil Perbandingan Metode Adaptif Blok dan Otsu
Niblack
Otsu
Adaptif Blok
adaptif blok
Otsu
Citra III
Niblack
citra3
adaptif blok
Citra II
Adaptif Blok
citra1
Kriteria Uji Coba
Citra I
DB
219
114
51
25
80
53
DS
0
59
8
27
0
28
TT
219
219
52
52
86
86
PRC RCL
100 100
65.9 52
86.4 98.1
48.1 48.1
100 93
65.4 61.6
F
100
58.2
91.9
48.1
96.4
63.5
Tabel 5 Evaluasi Uji Coba Perbandingan Metode Adaptif Blok dan Sauvola
Niblack
citra1
citra3
adaptif blok
adaptif blok
Sauvola
DB
Gambar3 Hasil Perbandingan Metode Adaptif Blok dan Niblack
Adaptif Blok
Niblack
Sauvola
adaptif blok
Citra III
Adaptif Blok
citra3
Citra II
Sauvola
Citra I Adaptif Blok
adaptif blok
Kriteria Uji Coba
citra1
219
215
51
51
80
75
DS
0
4
8
1
0
18
TT
219
219
52
52
86
86 80.6
PRC
100
98.2
86.4
981
100
RCL
100
98.2
98.1
98.1
93
87.2
F
100
98.2
91.9
98.1
96.4
83.8
Sauvola Rata-rata F-Measure yang didapatkan dari uji coba perbandingan metode terhadap 8 citra adalah sbb. • Thresholding Adaptif Blok: 92.69% • Thresholding Global Otsu: 62.94% • Thresholding Adaptif Niblack: 34.46% • Thresholding Adaptif Sauvola: 85.79%
Sauvola
Gambar3 Hasil Perbandingan Metode Adaptif Blok dan Sauvola
Evaluasi terhadap uji coba hasil perbandingan metode adaptif blok dan Otsu ditunjukkan oleh Tabel 3. Sedangkan perbandingan dengan metode Niblack dan Sauvola ditunjukkan pada Tabel 4 dan 5.
4
SIMPULAN Dari hasil uji coba yang didapatkan, didapatkan beberapa simpulan sebagai berikut: 1. Aplikasi ini mampu melakukan proses thresholding berdasarkan deteksi blok
5
2.
3.
4.
5.
terhadap citra dokumen terdegradasi dengan baik, sehingga menghasilkan citra biner yang dapat dikenali oleh aplikasi OCR. Aplikasi ini mampu mendeteksi ukuran blok untuk proses segmentasi terhadap citra dokumen terdegradasi. Aplikasi ini mampu melakukan thresholding secara adaptif melalui blok-blok yang telah didapatkan. Algoritma thresholding adaptif berdasarkan deteksi blok memiliki kinerja lebih baik daripada metode Otsu, Niblack, dan Sauvola.
DAFTAR PUSTAKA [1]. Pai Yu-Ting, Yi-Fan Chang and Shanq-Jang Ruan, 2010. Adaptive thresholding algorithm: Efficient computation technique based on intelligent block detection for degraded document images, Elsevier Ltd. [2]. Sahoo, P.K, S. Soltani, and A. K. C. Wong, 2004. Survey over image thresholding techniques and quantitative performance evaluation. Journal of Electronic Imaging [3]. Nobuyuki Otsu, 1979. A Threshold Selection Method From Gray Level Histograms. IEEE Trans. Systems Man Cybernet. [4]. W. Niblack, 1986. An Introduction to Digital Image Processing. Prentice-Hall. [5]. Sauvola, J., M. Pietikainen. 2000. Adaptive Document Image Binarization. Pattern Recognition. [6]. Sezgin, Mehmet, Bulent Sankur. 2004. Survey Over Image Thresholding Techniques and Quantitative Performance Evaluation. Journal of Electronic Imaging. [7]. Gatos, B., I. Pratikakis, S. J. Perantonis. 2005. Adaptive Degraded Document Image Binarization. Elsevier Ltd. [8]. Gonzales, R.C., Woods, R.E., 2002. Digital Image Processing, 2nd ed. Prentice Hall, Upper Saddle River, NJ, pp.
6
