Sunday, September 14, 2008

Detecting similar entropy zones in image

As I thought about information entropy one idea came to me - to write application which looks similar entropy zones in image. So after some time, I came with this algorithm (pseudo code):

1. Split image into 5x5 pixel image blocks
2. Calculate information entropy of these blocks (actually sum of entropy in 3 color channels)
3. Find similar entropy blocks.
4. [...] filter out small groups of blocks (seems like noise, huh ? ). Blah, blah...
5. Picture these similar entropy blocks on top of original image as red color layer.

Now real part (as you know already) - Python code which does the job [you need PIL module to run this]:

from PIL import Image
from math import *

def entropysum(pixels):
Calculating information entropy for image
region and returning entropy sum for
all 3 color channels
cr = [r for (r,g,b) in pixels]
cg = [g for (r,g,b) in pixels]
cb = [b for (r,g,b) in pixels]

er = 0.0
eg = 0.0
eb = 0.0

for r in set(cr):
p = float(cr.count(r))/len(cr)
if p > 0.0: er += -p * log(p,2)

for g in set(cg):
p = float(cg.count(g))/len(cg)
if p > 0.0: eg += -p * log(p,2)

for b in set(cb):
p = float(cb.count(b))/len(cb)
if p > 0.0: eb += -p * log(p,2)

return er + eg + eb

def decompose(image, block_len):
Decomposing given image into some number of
smaller images of size block_len*block_len
parts = []
w, h = image.size

for x in range(0, w, block_len):
for y in range(0, h, block_len):
locim = image.crop((x,y,x+block_len,y+block_len))
acc = entropysum(list(locim.getdata()))


return parts

def similarparts(imagparts):
Detecting similar image blocks by comparing
entropy of given images. Two images considered
being equal if entropy difference is not big.
dupl = []

for i in range(len(imagparts)-1):
acc1, x1, y1, im1 = imagparts[i]
acc2, x2, y2, im2 = imagparts[i+1]

if acc1 == acc2 == 0:
gain = 0.0
gain = 100.0 * (1.0 - acc1 / acc2)

if 0.01 < gain < 0.1 :
if imagparts[i] not in dupl:
if imagparts[i+1] not in dupl:

return dupl

def clusterparts(parts):
Grouping nearest images into groups.
This is done, because we need to
filter out very small groups. We
want to know only big differences.

filtparts = []
clust = {}
belongs = {}
w,h = parts[0][3].size

# assign all parts to clusters
for i in range(len(parts)):
acc, x, y, im = parts[i]
sides = []

# detect side already in cluster
fc = None
for s in sides:
if belongs.has_key(s):
fc = belongs[s]

# if this is new cluster
if fc == None:
fc = len(clust) + 1
clust[fc] = 1
clust[fc] += 1

# set cluster for rectangle sides
for s in sides:
if not belongs.has_key(s):
belongs[s] = fc

# filter out small clusters
for i in range(len(parts)):
acc, x, y, im = parts[i]
side = str(x)+str(y)+str(x+w)+str(y)
cl = belongs[side]
if clust[cl] > 2:

return filtparts

def marksimilar(image, dparts):
Mark found similar image blocks on
original image, by applying red layer
on similar parts of image.
if dparts:
colormask ='RGB', dparts[0][3].size,(255,0,0))
for (acc,x,y,im) in dparts:
im = Image.blend(im, colormask, 0.4)

return image

if __name__ == '__main__':
im ="1.jpg")
ls = decompose(im, 5)
dparts = similarparts(ls)
cparts = clusterparts(dparts)
im = marksimilar(im, cparts)

So these are the results after running this script on several images:


So this algorithm is an interesting tool for exploration of information entropy in image. Maybe in some cases it could be a tool for analyzing very similar texture zones. BTW information entropy may be used for hashing image. Hashing image is useful, because it lets us to search similar images in database (for example) by its hash.

Have fun !

No comments:

Post a Comment

Comment will be posted after comment moderation.
Thank you for your appreciation.