Thinning

THINNING

Makalah Disusun Guna Melengkapi dan Memenuhi Tugas

Mata Kuliah Pengenalan Pola

Dosen Pengampu: Aris Sugiharto, S.Si, M.Kom

Disusun oleh:

Kelompok 4

1. Dwi Kusrianto Putro        (J2F008098)
2. Khabib Mustofa               (J2F008112)

PROGRAM STUDI TEKNIK INFORMATIKA

JURUSAN MATEMATIKA FAKULTAS MIPA

UNIVERSITAS DIPONEGORO

SEMARANG

2011

A.     Pendahuluan

Thinning adalah sebuah langkah awal memproses untuk berbagai macam operasi analisa image seperti optical character recognition, fingerprint recognition dan document proscessing. Thinning melibatkan perpindahan titik atau lapisan dari suatu pola sampai semua garis menjadi singel pixel.. hasil dari set garis disebut skeleton dari suatu objek. tidak ada definisi matematika dari skleleton;menampilkan berbagai macam metode thinning dalam suatu pola menuju ke berbagai macam hasil pula. cara yang umum untuk mengekstrak skeleton mengandung memindahkan/menghapus, disetiap iterasi, semua edge pixels kecuali pixel yang menjadi skeleton tersebut.  edge pixels  menunjukkan batas yang ada di sebuah patern.

Thinning termasuk langkah penting dalam operasi analisis citra seperti pada pengenalan karakter, pengenaan sidik jari, dan pemrosesan dokumen. Proses thinning mengidentifikasi piksel-piksel dari suatu objek yang dianggap mewakili bentuk objek tersebut, dan digunakan untuk mengekstrak fitur dari suatu objek pada sebuah citra. Pada pengenalan pola, thinning digunakan untuk mereduksi pola biner ke representasi skeletal. Operasi thinning digunakan untuk mengambil rangka setebal satu piksel dari citra, dengan cara membuang titik-titik atau layer terluar dari citra sampai semua garis atau kurva hanya setebal satu piksel.

Kerangka yang dihasilkan disebut sebagai skeleton, yang dianggap merepresentasikan bentuk objek. Pada image berbentuk garis, skeleton menunjukkan semua informasi dari objek aslinya. Komponen-komponen dari skeleton, yaitu posisi, orientasi, dan panjang segmen-segmen garis skeleton mewakili garis-garis yang memberntuk image. Komponen-komponen ini mempermudah karakterisasi komponen-komponen dari image tersebut. Misalnya panjang dari suatu bentuk dapat diperkirakan dengan memperhitungkan ujung-ujung dan titik terjauh pada skeleton.

Ada berbagai macam metode atau algoritma thinning, dan masing-masing memberikan hasil yang berbeda. Kebanyakan algoritma thinning bersifat iteratif. Pada sebuah iterasi, piksel-piksel edge dievaluasi berdasarkan kriteria-kriteria tertentu untuk menentukan apakah harus dibuang atau tidak. Ada juga beberapa algoritma pada komputer-komputer yang bekerja secara sekuensial dan paralel. Pada algoritma sekuensial, untuk memproses suatu piksel pada suatu tahap digunakan hasil pemrosesan pada iterasi sebelumnya dan hasil iterasi pada tahap yang sedang berjalan. Sedangkan pada algoritma paralel, keputusan untuk membuang suatu piksel hanya bergantung pada hasil dari iterasi sebelumnya.

Selain thinning dikenal juga skeletonizing. Thinning sering diasumsikan sama dengan skeletonizing. Tetapi thinning berbeda dengan skeletonizing. Misalnya pada citra persegi panjang yang terisi penuh, thinning menghasilkan satu garis, sedangkan skeletonizing menghasilkan satu garis dengan cabang-cabang pada ujung-ujungnya yang mengarah ke ujung-ujung persegi panjang.

Sebagian dari thinning algoritma adalah iterative, di sebuah iteraksi, edge pixels diperiksa oleh berbagai kriteria untuk memutuskan apakah edge pixels harus dipindahkan atau tidak. Ada berbagai macam algoritma thining di sekunsial dan paralel komputer. Algoritma sekuensial menggunakan hasil dari iterasi sebelumnya dan hasil didapat dari sejauh mana iterasi berlanjut di (dalam) iterasi yang sekarang untuk memproses pixel yang sekarang.  Dengan begitu pada titik manapun  di (dalam) suatu iterasi sejumlah pixel telah diproses. Hasil tersebut bisa digunakan untuk langsung memproses pixel berikutnya. Dengan algoritma pararel, hanya hasil dari iterasi sebelumnya yang mempengaruhi untuk memindahkan sebuah titik yang sedang diiterasi, membuat hal ini sesuai untuk memproses dengan hardware yang pararel seperti array prosesor. Sebagian pengguna menggunakan salah satu dari strategi ini untuk menipiskan berbagai bentuk. Salah satu algoritma bisa menggenenerate skeleton yang bagus untuk bentuk tertentu tetapi bisa saja menghasilkan skeleton yang buruk dengan bentuk yang lain. Sangat sulit untuk mengembangkan sebuah thinning algoritma secara umum yang bisa digunakan untuk berbagai macam bentuk.

Sebenarnya thinning adalah sebuah tugas yang mudah untuk manusia. Diantaranya  bisa mengthin suatu patern dengan variasi patern bentuk tanpa kesulitan. itu nampak bahwa dpertama kali dia memahami bentuk secara global, kemudian mengaplikasikan berbagai macam bentuk algpritma untuk mengthin bentuk yang berbeda dari bagian yang berbeda dalam patern yang sama. Sebagai hasilnya, Skeleton yang dibuat manusia biasanya dijadikan referensi dari suatu skeleton. Fakta ini bisa sangat  menolong  untuk proses thinning.

Salah   satu  cacat yang umum dari suatu algoritma thinning adalah kelainan bentuk skeleton yang digenerate di ujung dan daerah silang seperti yang ditunjukan di gambar 1. masalah ini timbul ketika menggenerate skeleton dua pixels p1 dan p2 menjadi berhubungan seperti gambar 

2(a)  dan tidak seperti gambar di 2(b). cacat yang lain adalah generasi dua pixels skeleton;rangka lebar/luas untuk daerah [yang] dibengkokkan. Masalah inti timbul diakibatkan pixel yang ditunjukan pada gambar  2(a) berhubungan seperti gambar 2(b). hal tersebut bisa dilihat sebagai dua masalah yang saling kontradiksi dan oleh karena itu harus ada kompromi diantara keduanya.

Problem konektivitas dan thick skelelon sering dialami oleh banyak algoritma  ketika hasil bagian luar lapisan pixel dari suatu obyek dipindahkan/dihilangkan dan mengakibatkan struktur dari hasilnya tidak diketahui sejauh iterasi tersebut berjalan. Di kasus tersebut, batasan dikenalkan untuk memastikan conectivity sehingga sedemikian rupa kejadian doubly thick skleleton terjadi. Untuk kasus pararel algoritma, solusi telah dibagi menjadi beberapa sub iterasi untuk mendapatkan informasi tentang tetangga pixel.

B.    Karekteristik Skeleton

Pada bagian ini akan membahas tentang karakteristik yang umum dari skeleton dan  beberapa istilah yang berkaitan dengan skeleton. Suatu image biner yang menguraikan suatu 2D array pixels (gambar 4). Yang obyeknya membentuk foreground Q¹ image ini diwakili oleh satu set dark point sedang background Q^’ sesuai dengan satu set white point .

 

Untuk pixel yang telah ditentukan yaitu p ada delapan neighbours n₀,n1,..,n₇, dengan subcript yang menandakan arah tetangga dari p, berkenaan dengan x-axis(Gambar 5). Untuk n_i, arahnya adalah  i*45°. Neighbours dengan subcript dikenal sebagai D-neigbours, yang dapat diakses p dengan pindah ke suatu arah vertikal atau horisontal. Neighbours lainnya disebut I-Neighbours, yang dapat diakses dari p dengan 45°. Jika p adalah dark point dan salah satu dari 8 neighbours n_i adalah dark juga, p dan n_i disebut 8-connected.

Jika  p adalah dark dan salah satu dari empat  D-neighbours n_2i adalah juga dark, p dan n_2i dikatakan 4-connected.

Jika p₀ dan p_m adalah dua poin dark pada obyek yang sama, ada suatu alur, yang dapat menjelaskan suatu rantai tentang dark points p₀, p₁,.., p_m, dengan masing-masing pasangan pixel yang berurutan, p_i dan p_i+2 menjadi neghbours dari yang lain. Jika semua tetangga masing-masing dipertimbangkan, p₀ dan p_m disebut 8-connected. Jika hanya D-neighbours yang dipertimbangkan, p₀ dan p_m maka disebut 4-connected.

Suatu obyek disebut 8-connected jika semua pasangan point berada dalam obyek 8-connected dan disebut 4-connected jika semua pasangan point berada dalam obyek 4-connected. Berikut merupakan essensial karakteristik skeleton:

1. Konektifitas harus dipelihara. Jika objek terhubung, skeleton hasilnya juga harus terhubung. Umumnya, 8-connectivity harus dijaga untuk foreground, dan  4-connectivity harus dijaga untuk background.
2. Erosi yang berlebihan harus dicegah. Titik ujung dari skeleton harus ditemukan secepat mungkin, sehingga panjang skeleton tidak memendek, sehingga benar-benar merepresentasikan citra aslinya.
3. Skeleton tidak boleh dipengaruhi noise. Noise adalah gangguan-gangguan kecil yang bukan merupakan bagian dari skeleton, dan akan sering dihasilkan berupa ekor/cabang dari thinning. Panjang ekor ini harus diminimalkan.
4. Penggunaan 8-connectivity untuk foreground sangat penting, karena jika menggunakan   4-connectivity, skeleton akan memiliki ketebalan 2 piksel, sehingga tidak sesuai dengan skeleton yang dihasilkan. Tetapi penggunaan 8-connectivity juga memiliki efek samping, yaitu skeleton yang dihasilkan pada sudut atau persimpangan akan terdistorsi (terjadi eror), terutama jika citra aslinya sangat tebal.

Contoh: 

C.     Jenis-Jenis Thinning Algorithm

 

1.      Sequential and Parallel Thinning Algorithm

Algoritma thinning telah dipelajari secara ekstensif di dalam pengenalan pola dan pemrosesan citra. Macam-macam urutan dan paralel dari algoritma thinning sudah tersedia di dalam literatur. Semuanya mempunyai kelebihan dan kelemahannya tersendiri.

Sequential thinning method terdiri dari iterasi penghapusan titik gelap sepanjang tepi pola sampai pola itu menipis menjadi satu piksel garis tergambar. Titik tepi dari pola diidentifikasikan dengan tes pada 8 tetangga. Titik tepi terhapus dengan cara penghapusannya:

1. Jangan menghapus titik akhir
2. Jangan memutuskan sambungan pola
3. Jangan menyebabkan erosi yang merusak

Pada algoritma yang berbeda, test ini disajikan dengan cara yang berbeda.

Sequential algorithms memerlukan sedikit memori. Sequential algorithms menjelajah ke setiap piksel pada bitmap untuk memisahkan foreground dari background. Dapat dikatakan waktu kompleksitasnya tergantung pada ukuran bitmap. Kompleksitas juga tergantung pada operasi yang diperlukan untuk perkiraan titik tepi. Operasi ini tampil di setiap iterasi sampai pola benar-benar tipis. Waktu kompleksitas dapat berkurang jika objek memiliki titik-titik luar.

Pada teknik penelusuran permukaan, permukaan mengggambarkan tepi sebuah objek yang telah ditelusuri di setiap iterasi. Setelah permukaan selesai ditelusuri dan perkiraan urutan piksel ditemukan berupa sketsa piksel atau bukan, permukaan dihapus. Pada iterasi berikutnya, permukaan yang baru ditelusuri dan operasi dilakukan berulang-ulang sampai semua titik yang tidak aman terhapus.

Sama persis seperti sequential algorithms, parallel algorithms juga memakai cara mengunjungi semua titik piksel pada bitmap untuk menemukan titik gelap. Lalu titik-titik gelap diklasifikasikan ke dalam titik-titik tepi dan titik-titik yang lainnya. Hanya titik-titik tepi yang dibutuhkan. Tes bisa mempengaruhi beberapa titik tepi dari 8 tetangga untuk memperkirakan apakah mereka titik pemisah, titik akhir, atau titik tidak aman. (titik pemisah – penghapusan titik ini akan memisahkan hubungan, titik akhir – titik pada akhir permukaan, titik tidak aman – penghapusan titik initidak akan mempengaruhi sketsa). Titik tidak aman akan dihapus pada akhir proses. Titik-titik akhir dan titik-titik pemisah diambil sebagai titik aman dan seharusnya tidak dihapus.

Seperti sequential algorithm, waktu kompleks dari parallel algorithm terdiri dari 3 komponen:

1. Setiap lewat dan setiap subiterasi, setiap piksel pada bitmap telah ditelusuri satu kali untuk mengidentifikasikan titik-titik gelap. Jumlah operasi akan sesuai dengan luas area bitmap.
2. Setiap titik gelap telah ditemukan titik-titik tepinya. Jumlah operasi akan sesuai dengan luas area objek setiap melewati telusuran,
3. Jumlah yang telusuran berhubungan dengan ketebalan objek

Tetapi pada penggunakan cara paralel, waktu yang dibutuhkan lebih sedikit daripada sequential algoritms.

Meskipun parallel algorithms lebih cepat, ada beberapa masalah pada algoritma itu seperti kasus pada arsitektur proses parallel algoritms. Pada beberapa parallel algorithms, piksel dengan lebar 2 akan dihapus pada awal penelusuran, titik-titik pada kedua sisi garis tidak akan memisahkan hubungan pola bila titik-titik itu ditelusuri terpisah. Bila kedua sisi ditelusuri dengan cara paralel menggunakan hasil dari proses sebelumnya, titik-titik itu akan dihapus secara berurutan karena hasil dari penghapusan satu pihak tidak diketahui oleh pihak yang lain pada saat yang bersamaan. Di sinilah masalah dimana beberapa proses paralel berbagi memori yang sama. Pada algoritma thinning, ketika proses menjelajah piksel yang pasti, seharusnya menggunakan piksel dan 8 tetangganya secara eksklusif, Pada proses paralel thinning, ini bukan masalah.

Nyatanya, kebutuhan dari subiteraksi yang berbarengan pada parallel algorithm dan kemungkinan dari kesalahan penelusuran dua piksel yang bersebelahan pada pola dapat menyebabkan kesalahan fatal. Pada parallel algorithm, sebuah piksel diproses pada basis penelusuran sebelumnya, maka ketika piksel diperhitungkan dalam paralel, semua piksel akan dihapus.

Ketika masalah terlihat dari lain pihak, satu yang bisa terlihat pada penjelajahan pola dan teknik paralel, piksel dihapus dari pola tanpa tahu apa yang akan terjadi pada objek yang tersisa. Hasilnya, semua piksel akan terhapus atau kurva tebal akan tetap tebal setelan iterasi terakhir.

Solusinya adalah harus memikirkan hasil-hasil lebih jauh lagi pada pemrosesan piksel saat ini. Jika piksel mau dihapus, pola baru yang akan tampilkan menjadi background dapat diperhitungkan. Kapan pola diproses, sebuah bagian dari pola baru diolah agar setiap piksel pada pola dikunjungi. Bagian itu dicari titik-titik pemisah dan informasi ini tersedia ketika sub-urutan piksel pada urutan atau urutan berikutnya telah dikunjungi. Pada akhir iterasi, pola baru akan tersedia untuk iterasi berikutnya tanpa menghapus pola yang lama. Setiap saat, algoritma ini akan menyelesaikan pengetahuan dari apa saja yang tersisa dari sebuah objek ketika pola itu dihapus. 

2.     The Medial Axis Thinning Algorithm

Salah satu algoritma yang biasa digunakan untuk melakukan proses thinning adalah algoritma Medial Axis. Algoritma ini merupakan algoritma yang paling awal digunakan untuk melakukan proses thinning. Transformasi Medial Axis dari suatu himpunan S adalah himpunan titik tengah dan radius dari lingkaran terbesar yang terdapat di S, atau dengan kata lain himpunan titik pada S yang memiliki jarak terjauh dari S’. Dari hal tersebut terlihat bahwa sebenarnya algoritma ini berusaha untuk mencari jalan tengah di antara batas-batas S yang berlawanan dibentuk oleh sudut bisector dari batas-batas S. Akan tetapi, titik-titik yang dibentuk dengan cara ini belum tentu merupakan titik-titik yang 8-connected. Sehingga keterhubungan antar titik harus diperhatikan dengan melihat apakah piksel yang dipilih di baris tertentu dengan baris sebelumnya apakah mereka 8-connected, jika tidak maka harus dibuat lintasan 8-connected yang menghubungkan kedua titik tersebut.

Walaupun metode ini tidak memakan banyak waktu, secara umum hasil dari metode ini tidaklah begitu baik dibandingkan dengan algoritma-algoritma  thinning yang lain. Algoritma ini dapat bekerja dengan baik apabila daerah yang diproses merupakan daerah yang lurus dan tidak terdapat banyak noise, hal ini dikarenakan metode Medial Axis ini sangat sensitif terhadap noise.

3.        Algoritma Thinning Binary Region

Algoritma ini adalah algoritma untuk citra biner, dimana piksel background citra bernilai 0, dan piksel foreground (region) bernilai 1. Algoritma ini cocok digunakan untuk bentuk yang diperpanjang (elongated) dan dalam aplikasi OCR (Optical Character Recognition). Algoritma ini terdiri dari beberapa iterasi, dimana setiap iterasinya terdiri dari 2 langkah dasar yang diaplikasikan terhadap titik contour (titik batas) region. Titik contour  ini dapat didefinisikan sebagai sembarang titik yang pikselnya  bernilai 1, dan memiliki paling sedikit 1 piksel dari 8-tetangganya yang bernilai 0. Gambar berikut ini mengilustrasikan titik contour p₁ dan 8-tetangganya:

Langkah pertama dari sebuah iterasi adalah menandai semua titik contour untuk dihapus, jika titik contour  tersebut memenuhi syarat-syarat berikut:

1. 2 < N(p₁) < 6
2. S (p₁) = 1
3. p_{2 ·}  p_{4 ·}  p₆  = 0
4. p_{4 ·}  p_{6 ·}  p₈  = 0

dimana N(p₁) adalah jumlah dari tetangga titik contour  p_1, yang pikselnya bernilai 1, yaitu:

dan S (p₁) adalah banyaknya transisi 0-1 dari nilai piksel  p_2, p_{3, ...}  p_8, p₉ secara berurutan. Misalnya, untuk nilai  p_2, p_{3, ...}  p_8, p₉  seperti di bawah ini:

Maka nilai N(p₁) = 4 dan S (p₁) = 3.

Kondisi (a) dilanggar jika titik contour  p₁ memiliki hanya satu atau tujuh tetangga dari 8-tetangganya yang pikselnya bernilai 1. Jika titik contour  p₁ hanya memiliki satu tetangga, hal ini mengakibatkan p₁ adalah akhir dari skeleton, sehingga tidak boleh dihapus. Jika p₁  memiliki tujuh tetangga dan jika p_1, maka akan menimbulkan  erosi pada region yang bersangkutan. Kondisi (b) dilanggar jika titik contour merupakan region dengan satu piksel. Sehingga jika titik tersebut dihapus, akan mengakibatkan pemutusan segmen dari skeleton selama operasi thinning.

Kondisi (c) dan (d) akan dipenuhi minimal jika p₄ = 0, atau p₆ = 0, atau (p₂ = 0 dan p₈ = 0). Jika p₄ = 0 menunjukkan titik contour berada pada batas timur region. Jika p₆ = 0 menunjukkan titik contour berada pada batas batas selatan region. Sedangkan jika p₂ = 0 dan p₈ = 0 menunjukkan titik contour berada pada batas utara-barat region. Serupa dengan syarat (c) dan (d) pada langkah I, syarat (c’) dan (d’) pada langkah II dipenuhi minimal jika p₂ = 0, atau p₈ = 0, atau (p₄ = 0 dan  p₆ = 0).

Setelah langkah 1 selesai, langkah 2 diterapkan terhadap titik contour dari hasil langkah 1 sebelumnya, yaitu:

1. 2 < N(p₁) < 6
2. S (p₁) = 1
3. p_{2 ·}  p_{4 ·}  p₈ = 0
4. p_{2 ·}  p_{6 ·}  p₈ = 0

Langkah I diterapkan ke selutuh titik batas pada citra biner.Jika satu atau lebih syarat dari point a, b, c, d tidak dipenuhi, titik tersebut tidak ditandai untuk dihapus. Sebaliknya, jika semua syarat terpenuhi, maka titik tersebut ditandai untuk dihapus. Titik –titik batas tersebut tidak dihapus terleboh dahulu, sampai semua titik batas dievaluasi. Hal ini mencegah perubahan struktur data selama eksekusi algoritma. Setelah langkah I selesai dievaluasi terhadap semua titik batas, titik-titik yang diberi tanda dihapus (misalnya dengan cara mengubah nilai piksel dari 1 ke 0). Kemudian setelah itu, langkah II diterapkan ke citra hasil proses dengan langkah I.

Dari keterangan di atas, dapat diambil kesmpulan bahwa 1 iterasi dalam algoritma thinning ini terdiri dari 4 langkah , yaitu:

1. Menerapkan langkah I untuk menandai titik batas yang akan dihapus
2. Menghapus semua titik batas yang sudah diberi tanda
3. Menerapkan langkah II  untuk menandai titik batas yang akan dihapus pada citra hasil pemrosesan dengan langkah I
4. Menghapus titik batas yang sudah diberi tanda

Langkah I dan II diterapkan berulang-ulang, samapai tidak ada lagi titik yang bisa dihapus. 

Berikut ini adalah contoh hasil dari implementasi algoritma thinning binary region:

4.     A Thinning Algorithm by Contour Generation

Algoritma ini adalah teknik urutan yang lain. Pada metode ini, citra binary yang diberikan representasikan oleh kode berantai. Kode berantai diolah untuk setiap pola tertutup pada objek, dan kelangsungan dari rantai berlawanan arah jarum jam untuk pola luar dari objek dan searah jarum jam untuk pola di dalam lubang. Pola juga diperhitungkan sebagai urutan dari rantai dari titik tepi. Urutan piksel ditampilkan dalam bentuk Freeman code, yang merupakan urutan, penempatan ke piksel berikutnya di dalam bagian. Untuk 8 arah pola, dir(i) di dalam range 0 sampai 7 menampilkan 8 kelangsungan seperti terlihat pada Figure 5. Sebagai algoritma iterasi, Setelah menggambar pola pertama, algoritma melewati beberapa iterasi. Di setiap iterasi, pola yang merupakan tepi dari sebuah objek akan ditelusuri. Iterasi berhenti pada pola kecil-kecil ketika tidak ada lagi titik tidak aman pada pola. Ketika operasi selesai, yang tersisa hanyalah sketsa.

Ini adalah algoritma yang efisien sama seperti metode memeriksa citra hanya sekali untuk menghasilkan sketsa dari objek. Setelah itu, semua iterasi pola baru dihasilkan dari pola yang telah ada dan proses berulang sampai sketsa terakhir muncul. Tetapi masalah utamanya adalah ketajaman dari sketsa berkurang pada sudut dan titik menyilang. Ini sesuai fakta bahwa 8 ketehubungan mengatur piksel objek. Bila citra sudah tipis, ini memberikan kepuasan pada hasil, tetapi sama seperti ketebalan dari citra bertambah, ketebalan sketsa akan berkurang.

5. Hybrid Algorithm
Adalah penggabungan dari thinning algorithm yang sudah ada, menghasilkan algoritma baru dengan gabungan kelebihan dari algoritma terdahulu. Jenis-jenis hybrid algorithms :

a.     Gabungan Local Thinning Algorithms dengan Non-Local Algorithms

Keuntungan utama dari local thinning algorithms adalah kecepatannya dan simple, tapi kekurangannya adalah pada peninjauan data yang tidak nyata. Pendekatan seperti itu baik pada daerah yang diperpanjang seperti isolated strokes, tapi gagal pada stroke intersections. Non-local algorithms lebih baik pada intersecting strokes atau noisy strokes, tapi dapat juga menjadi rumit dan lambat.

Algoritma ini mempunyai dua keuntungan: Pertama, kemampuan mengidentifikasi dengan cepat area pola yang di-thin dengan baik menggunakan local methods dan yang menimbulkan ambiguitas. Kedua, kemampuan menghasilkan evaluasi yang lebih detil, menggunakan konteks, pada area yang tidak sukses di-thin. Algoritma ini dapat mendeteksi dan mengurangi jumlah kekeliruan, mengurangi sensitivitas thresholding, dan mengurangi sensitivitas local noise.

Algorithm ini menggunakan local methods untuk membuat hasil skeletonisasi awal image. Strokes yang diperpanjang dan mempunyai rentang variasi lambat di-thin dengan benar. Dengan menggunakan strokes yang di-thin kembali ke rentang asli mereka, dengan local process lagi dapat diidentifikasikan daerah yang dapat dihasilkan dari lebih satu stroke, lalu melabelinya sebagai ambigu. Metode non-local lalu digunakan hanya pada daerah ini. Berikut ini komponen algoritmanya: Initial skeletonization; stroke hypothesization, regeneration, and ambiguity detection; and stroke interpretation.

1. Initial Skeletonization. Meng-generate initial skeleton hipotesis; maka, cukup menggunakan salah satu thinning algorithm yang menyediakan dan memperbolehkan rekonstruksi. Tujuannya untuk mengidentifikasikan daerah pada image yang dengan mudah di-thin dengna benar dan menggunakan daerah tsb untuk mendukung sisa bagian dari pola.

2. Stroke Identification. Pada skeletonized image kita membagi skeleton menjadi fragment pada akhir dan junction points (pixel dengan tetangga tiga atau lebih). Kemudian membuat label yang unik pada masing-masing kontur dan mencoba menjabarkan keunikan hipotesa dengan membalik proses local thinning untuk menghasilkan skeleton kepada sebuah aproksimasi pola asli. Digunakan dua metode untuk regenerasi. Jika pengukuran jarak sederhana dari masing-masing kontur piksel ke ujung pola, kita bisa meletakkan tanda pada tiap piksel skeleton dengan jarak yang sesuai. Hasilnya adalah representasi pendekatan dari pola asli. Versi kedua menggunakan rata-rata lebar seluruh segment pada masing-masing piksel pada segmen. Ini membantu mengurangi noise pada atau dekat junctions yang bisa menurunkan akurasi perhitungan jarak.  Selama regenerasi, semua daerah yang dapat dihasilkan oleh lebih dari satu kontur skeleton ditandai pada image (mis :  lebih dari satu hipotesis menghasilkan lebih dari satu tanda). Daerah ini ambigu dan kita tidak dapat mengasumsikan sudah di-thin dengan benar. Kemudian kita memproyeksikan daerah ini kembali ke thinned image hypothesis, dan mencari bagian mana dari hipotesis skeleton awal menghasilkan skeleton fragments yang ambigu.

3. Stroke Interpretation and Reconstruction. Perkiraan orientasi ini dihitung dari rata-rata kecuraman dari k dekat tetangga, dan perkiraan lebar dihitung dari hasil scan image asli pada arah ortogonal. Gambar 1a memperlihatkan image asli dengan skeleton asli saling menimpa dan daerah yang rentan ambigu diberi tanda. 1b memperlihatkan skeleton yang berpotongan digunakan untuk menghitung orientasi dan poin akhir yang digunakan sebagai poin patokan. Gambar 1c memperlihatkan informasi lebar ditimpakan pada skeleton yang saling berpotongan. Tujuannya menciptakan orientasi dan informasi lebar pada anchor points di daerah perpotongan untuk menciptakan koneksi yang halus antara anchor points. Pengukuran tingkat kehalusan tidak dibicarakan disini.

    

   

b.    Gabungan Medial Axis Method dengan Contour Generation Method

Metode ini meminimalisasi masalah penyusunan kembali bentuk skeleton pada corner points. Algoritma ini memiliki lima langkah:

1. Pada langkah pertama, seperti thinning algorithm lain, menghilangkan noise pada input image. Ini membantu untuk menghindari tambahan ujung dan bermacam-macam distorsi. Digunakan algoritma penghalusan yang terdiri dari window 3x3 melalui binary image dan membandingkan posisi piksel tengah dengan 8 tetangganya untuk memutuskan apakah apakah nilai piksel perlu dipertahankan atau dimodifikasi.
2. Kemudian, image disegmentasi menjadi daerah horizontal, vertikal dan kurva berdasarkan panjang tiap langkah (rentangan piksel gelap yang bersambung pada kolom) dan membandingkan mereka dengan rata-rata ketebalan.
3. Setelah segmentasi, bergantung pada tipe daerah, metode yang sesuai diaplikasikan untuk menipiskan daerah. Pada tahap ini skeleton di semua daerah di-generate terpisah.
4. Skeleton kemudian dihubungkan untuk menghasilkan skeleton akhir.
5. Akhirnya perlu ada proses untuk menghilangkan beberapa poin yang tidak penting dan menjaga skeleton sebagai kesatuan lebar unit.

Contoh penggunaan Hybrid Algorithm (hasil Gabungan medial axis method dengan contour generation method):

6.     Susan Binary Post-Processing

Proses thinning yang dihasilkan dari SUSAN binary post-processing mengikuti beberapa aturan sederhana yang membuang edge points palsu atau yang tidak diinginkan, lalu menambahkan edge points yang seharusnya dilaporkan namun tidak ada. Dapat dibagi ke dalam 3 kategori : Membuang edge points palsu atau yang tidak diinginkan, menambahkan edge points baru, dan mengubah edge points ke posisi baru.

Aturannya sekarang diurutkan berdasarkan jumlah edge points tetangga yang dimiliki sebuah edge points (dengan aturan 8-tetangga), contohnya dapat dilihat pada gambar:

Contoh aturan thinning yang berbeda. Edge points yang baru hanya akan dibuat jika diperbolehkan oleh edge response.

a.    0 tetangga.

Membuang edge point.

b.   1 tetangga.

Cari tetangga dengan edge response maksimum (tidak nol), menyambung edge, dan mengisi kekosongan dalam edge. Response yang digunakan adalah yang ditemukan oleh initial stage dari SUSAN edge detector, sebelum penutupan non maksimum. Response ini diberi bobot yang mengacu pada orientasi edge yang sudah ada sehingga edge tersebut akan tersambung dalam suatu garis lurus. Sebuah edge dapat dilanjutkan oleh maksimum 3 piksel.

c.    2 tetangga.

Ada 3 kasus yang mungkin : 

• Kalau poinnya menempel pada sebuah garis lurus, bandingkan edge response-nya dengan edge response poin yang berkorespondensi dalam garis. Kalau poin potensial dalam edge lurus punya edge response lebih besar dari 0.7 dari point's response sekarang, pindahkan poinnya ke dalam edge dalam garis.
• Kalau poinnya tersambung dalam edge diagonal, buang poin tsb.
• Selain di atas, poinnya adalah edge point yang valid.

d.    Lebih dari 2 tetangga.

Jika poinnya bukan penghubung antara beberapa edge maka edge di-thin. Hal ini akan mengikutsertakan pilihan antara poin sekarang dan salah satu tetangganya. Apabila pilihan dibuat dalam cara logis yang konsisten akan dihasilkan thinned edge yang kelihatan bersih.

Aturan ini diterapkan ke semua piksel dalam image secara sekuensial dari kiri ke kanan dan dari atas ke bawah. Apabila perubahan dibuat pada edge image maka pencerian poin sekarang digeser ke belakang lebih dari 2 piksel ke kiri dan ke atas. Berarti alterasi yang iteratif pada image dapat dicapai hanya dengan menggunakan algoritma ini sekali jalan.

7.    Most Prominent Ridge Line (MPRL)

Metode thinning pada binary image tidak dapat diaplikasikan langsung ke image gray-scale, maka image gray-scale sering di-treshold untuk menciptakan bagian binary-nya. Proses ini menyebabkan hilangnya informasi berharga pada intensitas dimensi, ketidakseragaman nilai gray-level pada image gray-scale menyebabkan kontur yang tidak seimbang dalam binary image yang di-treshold, menyebabkan kesulitan pada proses thinning binary image.

Pendekatan pada image thinning berbasis scale-space ini dapat diaplikasikan baik pada binary maupun gray-scale image, dan meringankan efek ketidakseragaman dalam nilai gray-level dari image gray-scale dan kontur yang tidak seimbang pada binary image. Scale-space terdiri atas image asli pada level skala nol (t = 0) bersama dengan image pada skala dimensi kontinu t yang diturunkan filter Gaussian, dimana t > 0 adalah varian. Dalam scale-space semua skala dapat diakses secara simultan, juga mempunyai unsur-unsur pembangun dimana pada scale-space yang lebih besar (coarser structure) dapat dilacak ke struktur skala lebih kecil (finer structure), implikasinya finer structure ditutup saat skala bertambah.

Dengan prinsip ini dikembangkan metode topografik untuk image thinning dalam scale-space. Metode topografik memperlakukan image gray-scale sebagai permukaan dengan intensitas yang diinterpretasikan sebagai dimensi spasial ketiga (height). Dalam representasi topografik dari image 2-D, peak dijabarkan sebagai sebuah poin pada permukaan dimana gradiennya sama dengan nol, dan turunan kedua pada semua arah adalah negatif. Poin sisi didefenisikan sebagai poin pada permukaan dimana gradiennya nol, turunan kedua dalam satu arah adalah nol dan negatif dalam arah ortogonal, atau jika gradien tidak sama dengan nol, turunan kedua ortogonal terhadap gradien adalah negatif. Point saddle adalah poin pada permukaan dimana gradiennya nol dan turunan kedua pada satu arah adalah negatif dan positif dalam arah ortogonal. Maximum-intensity ridge line (MPRL) pada intensitas permukaan adalah gabungan poin topografik yang signifikan (peaks, point sisi, dan points saddle) dan diinterpretasikan sebagai representasi yang di-thin dari image asli. Dengan meminimisasi turunan spasial kedua dari masing-masing poin topografik signifikan pada skala dalam scale-space ditempatkan Most Prominent Ridge Line (MPRL). MPRL adalah cara dalam scale-space dimana dimensi skala merepresentasikan kesignifikanan struktur pada image awal. Point sepanjang MPRL mempunyai kontras terbesar dengan poin-poin tetangga, membuat mereka tidak gampang terpengaruh pada ketidakseragaman intensitas. Bersama dengan  penutupan dari struktur yang lebih baik, metode ini tidak terlalu dipengaruhi boundary noise atau ketidakseimbangan.

MPRL diimplementasikan menggunakan struktur data image pyramid untuk meng-approksimasi scale-space dengan image asli pada level dasar. Procedure yang mengikuti sisi kemudian digunakan untuk mengalokasikan MPRL dalam image pyramid. MPRL yang diekstrak digunakan untuk menghasilkan thinned image dalam ruang image 2-D awal. Hal ini dicapai dengan memproyeksikan MPRL dalam scale-space ke level base asli.

D.     Contoh Aplikasi

Salah satu penggunaan thinning dalam aplikasi adalah untuk membantu analisis terhadap pola tertentu. Dalam hal ini, thinning merupakan bagian dari computer vision. Salah satu penerapannya adalah untuk menganalisis pola akar tanaman. Tujuannya adalah untuk mengetahui kebutuhan tanaman akan nutrisi. Aplikasi analisis akar tanaman memiliki prosedur dan metodologi seperti pada gambar berikut:

 

Dalam melakukan analisis terhadap akar tanaman, yang pertama kali harus dilakukan adalah pengambian citra. Citra diambil dengan menggunakan kamera. Kemudian, pada citra yang telah diambil, dilakukan pemrosesan tahap awal (lower processing) sebagai persiapan untuk pemrosesan selanjutnya.

Citra yang telah melalui tahap awal pemrosesan kemudian disegmentasi. Proses segmentasi terdiri dari dua tahapan. Yang pertama adalah image tresholding dan yang kedua adalah image thinning. Image tresholding berguna untuk memisahkan gambar akar dengan background-nya. Kemudian, proses thinning dilakukan. Contoh hasil thinning adalah pada gambar berikut.

 

Setelah thinning dilakukan, barulah dapat dilakukan analisis terhadap citra. Diantaranya adalah mengukur panjang, sudut, ujung akar, dan celah lateral. Sedangkan mengukur permukaan lateral dapat dilakukan setelah proses tresholding.

E.     Daftar Pustaka

Utami, Annisa, dkk, 2003, “Thinning”, diakses dari http://www.google.co.id/search?q=thining+dalam+pengenalan+pola&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a#q=thinning+dalam+pengenalan+pola&hl=id&client=firefox-a&pwst=1&rls=org.mozilla:en-US:official&prmd=ivns&ei=t06iTdC9KIzirAfM9uXuAg&start=0&sa=N&fp=aa9c18a922804eb4, pada tanggal 9 April 2011, pukul 19.56 WIB.

AS, Baihaki, dkk, 2003, “Thinning”, diakses dari http://www.google.co.id/search?q=thining+dalam+pengenalan+pola&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a#q=thinning+dalam+pengenalan+pola&hl=id&client=firefox-a&hs=ggQ&pwst=1&rls=org.mozilla:en-US:official&prmd=ivns&ei=j02iTY7oCMXjrAf8svXxAg&start=10&sa=N&fp=aa9c18a922804eb4, pada tanggal 9 April 2011, pukul 20.14 WIB.