On Sequential thinning in pygame

31Mei10

Yeah, beberapa waktu lalu lagi iseng bikin kode untuk thinning di pygame. Bukan karena bosan pake delphi seperti biasanya tapi kode di delphi udah terlalu penuh dan agak males untuk bikin satu program kecil cuma buat ngetes2 jadinya bermain-main di pygame aja. Thinning yang dilakukan disini sifatnya sekuensial, jadi untuk menghapusnya dijalankan tiap kali ketemu titik yang bisa dihapus (bukan disimpan dulu ke list dan kalo udah dicek semuanya baru dihapuskan). Cara kerjanya secara umum adalah memeriksa ujung di setiap scanline dalam beberapa arah sumbu (untuk citra 2d ada dua sumbu yaitu vertikal dan horizontal, untuk citra volum ada 3). Namun dibandingkan teknik lain yang memeriksa tiap arah di tiap sumbu secara terpisah, algoritma yang dipakai di sini memeriksa kedua ujung di tiap sumbu secara bersamaan. Tujuan akhirnya adalah membentuk citra biner yang tiap pikselnya memiliki ketebalan 1 yang saling terhubung dalam ketetanggaan 4. Dengan kata lain, mencari tulang dengan cara menggerus tepinya (menipiskan) sampai ketebalan yang diinginkan.

Secara umum prosesnya cukup cepat karena pemeriksaan piksel yang akan dihapus hanya dilakukan untuk piksel ‘ujung’ (yang punya tetangga putih). Sebetulnya untuk penipisan 2D yang paralel, algoritma semacam Zhang-suen pun bisa dipercepat melalui ‘hashing’ seluruh kemungkinan ketetanggaan 8 (menjadi tabel 256 elemen boolean) sehingga pemeriksaan hapus-tidaknya hanya melibatkan lookup ke tabel tersebut.

Kembali ke topik awal tentang penipisan sekuensial, algoritmanya dibagi menjadi tiga bagian yaitu :

• penentuan hapus-jangan piksel
• pemrosesan scanline tiap sumbu
• iterasi

Bagian pertama adalah penentuan apakah suatu piksel yang diduga jika dihapus maka tidak akan mengubah topologi dari objek keseluruhan.

nn = [(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1),(-1,0)]

def test(ab,x,y):
	cn = 0
	cc = 0
	global nn
	for n in xrange(len(nn)):
		if ab[y+nn[n][1]][x+nn[n][0]]:
			cn += 1
			if not ab[y+nn[n-1][1]][x+nn[n-1][0]]:
				cc += 1
	if cc == 1 and cn != 1:
		ab[y][x] = False
		return 1
	return 0

kode diatas menghitung dua variabel yang dijadikan dasar pengambilan keputusan yaitu cn dan cc. cn menyatakan banyaknya piksel objek yang ada di sekitar piksel yang sedang diperiksa sedangkan cc menyatakan banyaknya kelompok piksel objek (connected component) yang terhubung. Suatu piksel boleh dihapus jika piksel tersebut hanya memiliki satu kelompok piksel dan piksel tetangga tersebut lebih dari satu. Dengan kata lain, piksel yang sedang diperiksa merupakan piksel luar yang ketidakhadirannya tidak mengganggu topologi citra. jadi boleh dihapus.

def thinh(ab,w,h):
	ret = 0
	for y in xrange(h):
		x = 0
		while x<w-1:
			while (x<w-1) and not ab[y][x]:
				x += 1
			if x==w-1:
				break
			start = x
			while (x<w-1) and ab[y][x]:
				x += 1
			stop = x-1
			if stop-start>0:
				ret += test(ab, start, y)
				ret += test(ab, stop, y)
			if x==w-1:
				break
	return ret
		
def thinv(ab,w,h):
	ret = 0
	for x in xrange(w):
		y = 0
		while y<h-1:
			while (y<h-1) and not ab[y][x]:
				y += 1
			if y==h-1:
				break
			start = y
			while (y<h-1) and ab[y][x]:
				y += 1
			stop = y-1
			if stop-start>0:
				ret += test(ab, x, start)
				ret += test(ab, x, stop)
			if y==h-1:
				break
	return ret

Kode di atas menguraikan citra menjadi ‘baris-baris’ dan mengirimkan tiap ujung dari ‘baris’ tersebut ke pengujian penghapusan piksel. Kode di atas analog dengan algoritma yang dipelajari mahasiswa tingkat 2 IF di kuliah algoritma pemrograman bagian mesin kata. Pada kasus thinning di sini, piksel yang dihapus adalah ‘huruf’ yang berada di awal dan akhir ‘kata’.

def thin(ab,w,h):
	step = 0
	while True:
		r = 0
		r += thinv(ab,w,h)
		r += thinh(ab,w,h)
		if r == 0:
			break
		step += 1
	return step

Bagian terakhir adalah bagian yang melakukan iterasi dari proses di atas. Pada tiap tahapan pengulangan, banyaknya piksel yang dihapus dicatat dan akan digunakan sebagai kondisi berhenti pengulangan (berhenti jika tak ada lagi piksel yang dihapus). Pada kode di atas proses penipisan dilakukan terhadap sumbu vertikal terlebih dahulu dibanding horizontal. Hal ini disebabkan objek yang akan ditipiskan (alfabet/angka) pada umumnya memang lebih panjang di sumbu vertikal dibandingkan horizontal.

Kode sisanya merupakan kode untuk visualisasi dan pembacaan citra ke dalam array 2 dimensi boolean.

from pygame import *
import os, sys

def thinning(img):
	buf = []
	for y in xrange(img.get_height()):
		l = []
		for x in xrange(img.get_width()):
			l += [img.get_at((x,y))[0]==0]
		buf += [l]
	#thin
	r = thin(buf, img.get_width(), img.get_height())
	#update back
	for y in xrange(img.get_height()):
		for x in xrange(img.get_width()):
			c = 255
			if buf[y][x]:
				c = 0
			tmp = (c,c,c,255)
			img.set_at((x,y), tmp)
	return r

init()
display.init()
im = None
if len(sys.argv)>1:
	im = image.load(sys.argv[1])
else:
	im = image.load('/data/HWR/12.bmp')
imo = im.copy()
print imo == im
scl = 8
im2x = transform.scale(im, (im.get_width()*scl, im.get_height()*scl))
scr = display.set_mode((im2x.get_width(),im2x.get_height()), HWSURFACE|DOUBLEBUF)

r = True
while r:
	scr.fill((0,0,0))
	scr.blit(im2x, (0,0))
	display.flip()
	for e in event.get():
		if e.type == QUIT or e.type==KEYDOWN and e.key==K_ESCAPE:
			r = False
			break
		if e.type==KEYDOWN:
			if e.key == K_r:
				im.blit(imo, (0,0))
				transform.scale(im, (im.get_width()*scl, im.get_height()*scl), im2x)
			elif e.key == K_t:
				thinning(im)
				transform.scale(im, (im.get_width()*scl, im.get_height()*scl), im2x)

Filed under: image processing, programming   |  3 Komentar
Tag:pygame, python, sequential, skeletonizing, thinning