Home | About | Apps | Github | Rss

Zhang-Suen Thinning Algorithm

Fiddling around with ideas on how to break captchas, I realised one of the first steps towards it could be the simplification of the input image, into a simple node graph (after elimination of background artefacts). From the node graph, it should be trivial to classify a particular graph structure into its corresponding ASCII symbols, without delving into neural networks.

To construct node graph, it seemed logical to thin down symbols into simple lines, which is when I came across Zhang-Suen Thinning algorithm (pdf paper).

Before:

After:

After implementing the algorithm I realised that although its quite efficient at simplifying the symbols, it is insufficient. More work needs to be done on this.

Python implementation:

import sys
from PIL import Image
from pprint import pprint as pp

C_BLACK = 0
C_WHITE = 1

####################################################################
#	Helper functions for working with data returned as a single 
#	array by list(img.getdata()) method
####################################################################

# is the pixel black or white
# assuming col represents gray color in (r,g,b) format
def _isbw(col):
	c = 240 
	if col[0] < c and col[1] < c and col[2] < c:
		col = C_BLACK
	else:
		col = C_WHITE

	return col

def _getcoord( size, pos ):
	x,y = pos
	w,h = size
	i = (y * w) + x
	return i

def _getbw( imgdata, size, pos ):
	return imgdata[ _getcoord(size,pos) ]
	
def _setbw( imgdata, size, pos, col ):
	imgdata[ _getcoord(size,pos) ] = col

def _getbwdata( img ):
	d = list(img.getdata())
	for i, c in enumerate(d):
		d[ i ] = _isbw( c )
		# print i, c, d[ i ]
	return d


####################################################################
#	Algorithm implementation
####################################################################

# step1_func = lambda parr: p2 + p4 + p6 > 0 and p4 + p6 + p8 > 0
# step2_func = lambda parr: p2 + p4 + p8 > 0 and p2 + p6 + p8 > 0
step1_func = lambda parr: parr[0] + parr[2] + parr[4] > 0 and parr[2] + parr[4] + parr[6] > 0
step2_func = lambda parr: parr[0] + parr[2] + parr[6] > 0 and parr[0] + parr[4] + parr[6] > 0

def do_step(imgdata, size, func):
	was_modified = False
	for j in range(1,h-1):
		for i in range(1,w-1):
			p1 = _getbw( imgdata, size, ( i,  j   ) )
			p2 = _getbw( imgdata, size, ( i,  j-1 ) )
			p3 = _getbw( imgdata, size, ( i+1,j-1 ) )
			p4 = _getbw( imgdata, size, ( i+1,j   ) )
			p5 = _getbw( imgdata, size, ( i+1,j+1 ) )
			p6 = _getbw( imgdata, size, ( i,  j+1 ) )
			p7 = _getbw( imgdata, size, ( i,  j+1 ) )
			p8 = _getbw( imgdata, size, ( i-1,j   ) )
			p9 = _getbw( imgdata, size, ( i-1,j-1 ) )

			# nimg.putpixel( (i,j),  )
			# nimg.putpixel( (i,j), p1 )
			A_Val  = (p2 == 0 and p3 == 1) + (p3 == 0 and p4 == 1) 
			A_Val += (p4 == 0 and p5 == 1) + (p5 == 0 and p6 == 1) 
			A_Val += (p6 == 0 and p7 == 1) + (p7 == 0 and p8 == 1)
			A_Val += (p8 == 0 and p9 == 1) + (p9 == 0 and p2 == 1)

			B_Val = sum([p2,p3,p4,p5,p6,p7,p8,p9])
			parr = [p2,p3,p4,p5,p6,p7,p8,p9,p2]

			if p1 == C_BLACK:
				if 2 <= B_Val <= 6:
					if A_Val == 1:
						if func(parr):
							_setbw( imgdata, size, (i,j), C_WHITE )
							was_modified = True
							# imgdata.putpixel( (i,j), C_WHITE )
	return (imgdata, was_modified)
								

####################################################################
#	Work on image / main
####################################################################

if __name__ == '__main__':
	imgname = 'abcd.jpg'
	img = Image.open(imgname)
	w, h = img.size

	""" The data is returned as a single array """
	pixels = list(img.getdata())

	# Create black and white pixel bitmap image
	nimg = Image.new('1', img.size, -1 )

	# Convert source image to black and white pixels
	bwdata = _getbwdata( img )

	# Run the algorithm until no further modifications are required
	is_modified = True
	while is_modified:

		bwdata, modified1 = do_step(bwdata,img.size,step1_func)
		bwdata, modified2 = do_step(bwdata,img.size,step2_func)

		is_modified = modified1 | modified2

		print is_modified, modified1, modified2

	# Push the data to image
	nimg.putdata( bwdata )
	nimg.show()

	## And save
	fp = open('.abcd_output.jpg','w')
	nimg.save(fp)
	fp.close()

More posts