Count Characters In Image - Using Space Efficient CCL Algorithm With Dilation and Erosion

count-characters.py

__author__ = 'Saurabh'
from PIL import Image

IMAGE_NAME = 'RandomText.gif'

inputImage = Image.open(IMAGE_NAME)
inputImageMatrix = inputImage.load()

BLACK = 0
WHITE = 255

OBJECT_PIXEL = WHITE
BACKGROUND = BLACK

def copyMatrix(fromMatrix, toMatrix, width, height):
	for y in range(height):
		for x in range(width):
			toMatrix[x, y] = fromMatrix[x, y]

def negate(imageMatrix, width, height):
	for y in range(height):
		for x in range(width):
			if imageMatrix[x, y]==0:
				imageMatrix[x, y] = 255
			else:
				imageMatrix[x, y] = 0

def dilate(imageMatrix, width, height):
	outputImage = Image.new('L', (width, height), "black")
	outputImageMatrix = outputImage.load()
	for y in range(height):
		for x in range(width):
			if imageMatrix[x, y]!=BACKGROUND:
				outputImageMatrix[x, y] = OBJECT_PIXEL
				if x+1<width:
					outputImageMatrix[x+1, y] = OBJECT_PIXEL
				if y+1<height:
					outputImageMatrix[x, y+1] = OBJECT_PIXEL
				if x-1>=0:
					outputImageMatrix[x-1, y] = OBJECT_PIXEL
				if y-1>=0:
					outputImageMatrix[x, y-1] = OBJECT_PIXEL
	copyMatrix(outputImageMatrix, imageMatrix, width, height)

def erode(imageMatrix, width, height):
	outputImage = Image.new('L', (width, height), "black")
	outputImageMatrix = outputImage.load()
	for y in range(height):
		for x in range(width):
			isConnected = True
			if x+1<width and imageMatrix[x+1, y] != OBJECT_PIXEL:
				isConnected = False
			if y+1<height and imageMatrix[x, y+1] != OBJECT_PIXEL:
				isConnected = False
			if x-1>=0 and imageMatrix[x-1, y] != OBJECT_PIXEL:
				isConnected = False
			if y-1>=0 and imageMatrix[x, y-1] != OBJECT_PIXEL:
				isConnected = False
			if isConnected:
				outputImageMatrix[x, y] = OBJECT_PIXEL
			else:
				outputImageMatrix[x, y] = BACKGROUND
	copyMatrix(outputImageMatrix, imageMatrix, width, height)

def getTopAndLeftLabels(x, y, labelMatrix, width, height):
	top = 0
	left = 0
	if x-1>=0  and labelMatrix[(x-1,y)] != 0:
		top = labelMatrix[(x-1,y)]
	if y-1>=0 and labelMatrix[(x,y-1)] != 0:
		left = labelMatrix[(x,y-1)]
	return [top, left]

def getBottomAndRightLabels(x, y, labelMatrix, width, height):
	bottom = 0
	right = 0
	if x+1<width  and labelMatrix[(x+1,y)] != 0:
		right = labelMatrix[(x+1,y)]
	if y+1<height and labelMatrix[(x,y+1)] != 0:
		bottom = labelMatrix[(x,y+1)]
	return [bottom, right]

import sys
def debug(matrix):
	import sys
	for y in range(20):
		for x in range(20):
			sys.stdout.write(str(matrix[(x,y)]))
		print ''

def applyCCL3(imageMatrix, width, height):
	labelMatrix = {}
	for y in range(height):
		for x in range(width):
			labelMatrix[(x,y)] = 0

	labelCount = 1
	for y in range(height):
		equivalenceClassList = []
		for x in range(width):
			if imageMatrix[x, y]!=BACKGROUND:
				compareList = filter(lambda value: value!=0, getTopAndLeftLabels(x, y, labelMatrix, width, height))
				compareList = list(set(compareList))
				try:
					labelMatrix[(x,y)] = min(compareList)

					isEquivalenceClassPresent = False
					for equivalenceClass in equivalenceClassList:
						if any(value in compareList for value in equivalenceClass):
							isEquivalenceClassPresent = True
							equivalenceClass.extend(compareList)

					if not isEquivalenceClassPresent:
						equivalenceClassList.append(compareList)
				except ValueError:
					labelMatrix[(x,y)] = labelCount
					labelCount = labelCount+1
		for x in range(width):
			if labelMatrix[(x,y)] != 0:
				for equivalenceClass in equivalenceClassList:
					if labelMatrix[(x,y)] in equivalenceClass:
						labelMatrix[(x,y)] = min(equivalenceClass)
	
	for y in range(height-1,-1,-1):
		for x in range(width-1,-1,-1):
			if imageMatrix[x, y]!=BACKGROUND:
				compareList = filter(lambda value: value!=0, getBottomAndRightLabels(x, y, labelMatrix, width, height))
				compareList = list(set(compareList))
				try:
					labelMatrix[(x,y)] = min(compareList)
				except ValueError:
					pass
	debug(labelMatrix)
	return labelMatrix


negate(inputImageMatrix, inputImage.size[0], inputImage.size[1])
dilate(inputImageMatrix, inputImage.size[0], inputImage.size[1])
erode(inputImageMatrix, inputImage.size[0], inputImage.size[1])
labelMatrix = applyCCL3(inputImageMatrix, inputImage.size[0], inputImage.size[1])
negate(inputImageMatrix, inputImage.size[0], inputImage.size[1])

RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)

resultImage = Image.new('RGB', (inputImage.size[0], inputImage.size[1]), "white")
resultImageMatrix = resultImage.load()
labelCount = {}
for y in range(inputImage.size[1]):
    for x in range(inputImage.size[0]):
    	if labelMatrix[(x,y)] == 0:
    		resultImageMatrix[x, y] = (255,255,255)
    		continue
        labelCount[labelMatrix[(x,y)]] = ''
        if labelMatrix[(x,y)]%3==0:
            resultImageMatrix[x, y] = RED
        if labelMatrix[(x,y)]%3==1:
            resultImageMatrix[x, y] = GREEN
        if labelMatrix[(x,y)]%3==2:
            resultImageMatrix[x, y] = BLUE
resultImage.save(IMAGE_NAME.split('.')[0]+'_output.'+IMAGE_NAME.split('.')[1])

print 'Total label components are==>'+str(len(labelCount))