Entropy based cropping of images

cropentro.py

import math
from optparse import OptionParser
from PIL import Image

def entropy(img):
    hist = img.histogram()
    total_prob = sum(hist)
    probs = [float(x) / total_prob for x in hist]
    return -sum([p * math.log(p) for p in probs if p != 0])

def rows(img):
    width, height = img.size
    for x in xrange(height):
        yield img.crop((0, x, width, x+1))

def columns(img):
    width, height = img.size
    for y in xrange(width):
        yield img.crop((y, 0, y+1, height))

def normalize(values):
    lo = min(values)
    rng = max(values) - lo
    return [(x - lo) / rng for x in values]

def subtract_constant(values, constant):
    return [x - constant for x in values]

def max_sum_subsequence(values):
    global_max = current_max = 0
    global_start = global_end = None
    current_start = 0
    for current_end, v in enumerate(values):
        current_max += v
        if current_max > global_max:
            global_max = current_max
            global_start = current_start
            global_end = current_end
        if current_max < 0:
            current_max = 0
            current_start = current_end + 1
    if global_start is not None and global_end is not None:
        return (global_max, global_start, global_end)
    return None

def crop(input_path, output_path, treshold):
    img_in = Image.open(input_path)

    row_entropy = normalize([entropy(r) for r in rows(img_in)])
    column_entropy = normalize([entropy(c) for c in columns(img_in)])

    row_range = \
        max_sum_subsequence(subtract_constant(row_entropy, treshold))
    column_range = \
        max_sum_subsequence(subtract_constant(column_entropy, treshold))

    if row_range is None or column_range is None:
        return False

    img_out = img_in.crop(
        (column_range[1], row_range[1], column_range[2], row_range[2]))
    img_out.save(output_path, img_in.format)
    return True

def parse_options():
    option_parser = OptionParser(
        usage='usage: %prog [options] input_file output_file')
    option_parser.add_option('-t', '--threshold', dest='treshold',
        type='float', default=0.1,
        help='entropy threshold (0.0 - 1.0) for cropping')
    return option_parser.parse_args()

if __name__ == '__main__':
    options, args = parse_options()

    if len(args) >= 2:
        crop(args[0], args[1], options.treshold)
    else:
        print "Not enough arguments (run with '-h' for help)"