Andhika Putro: Algoritma Thinning

Algoritma Thinning dan Penjelasannya

Thinning merupakan metode yang digunakan untuk skeletonizing yang salah satu penggunaanya adalah dalam aplikasi pattern recognition. Terdapat cukup banyak algoritma untuk image thinning dengan tingkat kompleksitas, efisiensi dan akurasi yang berbeda-beda. Kami hanya akan membahas beberapa algoritma yang tersedia. Citra yang digunakan adalah citra biner, jika citra itu merupakan suatu citra grayscale, biasanya dilakukan thresholding terlebih dahulu sedemikian rupa sehingga citra tersebut menjadi citra biner. Citra biner adalah citra yang hanya memiliki 2 kemungkinan nilai pada setiap piksel-pikselnya, yaitu 0 atau 1. Nilai 0 adalah background points, biasanya bukan merupakan bagian dari citra sesungguhnya. Sedangkan nilai 1 adalah region points, yaitu bagian dari citra sebenarnya (bukan latar belakang). Citra hasil dari algoritma thinning biasanya disebut dengan skeleton.

Umumnya suatu algoritma thinning yang dilakukan terhadap citra biner seharusnya memenuhi kriteria-kriteria sebagai berikut:

Skeleton dari citra kira-kira berada di bagian tengah dari citra awal sebelum dilakukan thinning.
Citra hasil dari algoritma thinning harus tetap menjaga struktur keterhubungan yang sama dengan citra awal.
Suatu skeleton seharusnya memiliki bentuk yang hampir mirip dengan citra awal.
Suatu skeleton seharusnya mengandung jumlah pixel yang seminimal mungkin namun tetap memenuhi kriteria-kriteria sebelumnya.

Algoritma Zhang-Suen

Algoritma ini adalah salah satu algoritma thinning yang cukup populer dan telah digunakan sebagai suatu basis perbandingan untuk thinning. Algoritma ini cepat dan mudah diimplementasikan.

Setiap iterasi dari metode ini terdiri dari dua sub-iterasi yang berurutan yang dilakukan terhadap contour points dari wilayah citra. Contour point adalah setiap pixel dengan nilai 1 dan memiliki setidaknya satu 8-neighbor yang memiliki nilai 0.

Dengan informasi ini, langkah pertama adalah menandai contour point p untuk dihapus jika semua kondisi ini dipenuhi:

(a) 2 ≤ N(p₁) ≤ 6;

(b) S(p₁) = 1;

(d) p₄ . p₆ . p₈ = 0;

dimana N(p₁) adalah jumlah tetangga dari p₁ yang tidak 0; yaitu,

N(p₁) = p₂ + p₃ + ... + p₈ + p₉

p₉	p₂	p₃
p₈	p₁	p₄
p₇	p₆	p₅

dan S(p₁) adalah jumlah dari transisi 0-1 pada urutan p₂, p₃, ..., p₈, p₉.

Dan pada langkah kedua, kondisi (a) dan (b) sama dengan langkah pertama, sedangkan kondisi (c) dan (d) diubah menjadi:

(c’) p₂ . p₄ . p₈ = 0;

(d’) p₂ . p₆ . p₈ = 0;

Langkah pertama dilakukan terhadap semua border pixel di citra. Jika salah satu dari keempat kondisi di atas tidak dipenuhi atau dilanggar maka nilai piksel yang bersangkutan tidak diubah. Sebaliknya jika semua kondisi tersebut dipenuhi maka piksel tersebut ditandai untuk penghapusan.

Piksel yang telah ditandai tidak akan dihapus sebelum semua border points selesai diproses. Hal ini berguna untuk mencegah perubahan struktur data. Setelah langkah 1 selesai dilakukan untuk semua border points maka dilakukan penghapusan untuk titik yang telah ditandai (diubah menjadi 0). Setelah itu dilakukan langkah 2 pada data hasil dari langkah 1 dengan cara yang sama dengan langkah 1 sehingga, dalam satu kali iterasi urutan algoritmanya terdiri dari:

(1) Menjalankan langkah 1 untuk menandai border points yang akan dihapus,

(2) hapus titik-titik yang ditandai dengan menggantinya menjadi angka 0,

(3) menjalankan langkah 2 pada sisa border points yang pada langkah 1 belum dihapus lalu yang sesuai dengan semua kondisi yang seharusnya dipenuhi pada langkah 2 kemudian ditandai untuk dihapus,

(4) hapus titik-titik yang ditandai dengan menggantinya menjadi angka 0.

Prosedur ini dilakukan secara iteratif sampai tidak ada lagi titik yang dapat dihapus, pada saat algoritma ini selesai maka akan dihasilkan skeleton dari citra awal.

Algoritma Stentiford

Metode ini adalah algoritma thinning dengan menggunakan teknik template-based mark-and-delete. Metode ini cukup terkenal karena reliable dan kefektifannya. Metode thinning jenis ini menggunakan template untuk dicocokkan dengan citra yang akan di-thinning. Algoritma ini bersifat iteratif yang berguna untuk mengikis lapisan pixel terluar sampai tidak ada lapisan lagi yang dapat dihilangkan.

Template yang dipakai adalah 4 buah template 3 x 3 yaitu,

Berikut ini akan dijelaskan langkah–langkah algoritma Stentiford :

Cari pixel pada lokasi (i,j) dimana pixel-pixel pada image cocok dengan template T₁. Dengan template ini, maka semua pixel di bagian atas dari image akan dihilangkan (remove). Pencocokkan template ini bergerak dari kiri ke kanan dan dari atas ke bawah.
Bila pixel tengah bukan merupakan endpoint dan mempunyai jumlah konektivitas (connectivity number) 1, maka tandai pixel tersebut untuk kemudian dihilangkan (remove).

Endpoint pixel : pixel yang merupakan batas akhir dan hanya terhubung dengan 1 pixel saja. Contoh : suatu pixel hitam hanya mempunyai satu tetangga saja yang hitam juga dari kemungkinan delapan tetangga.

Connectivity number : merupakan suatu ukuran berapa banyak obyek yang terhubung dengan pixel tertentu (dihitung berdasarkan rumus di bawah).

N_k merupakan nilai dari 8 tetangga di sekitar pixel yang akan dianalisa (central pixel) dan nilai S = {1,3,5,7}. N₀ adalah nilai dari pixel tengah (central pixel). N₁ adalah nilai dari pixel pada sebelah kanan central pixel dan sisanya diberi nomor berurutan dengan arah berlawanan jarum jam.