#!/usr/bin/python # image_hash.py # --copyright-- Copyright 2014 (C) Tranzoa, Co. All rights reserved. Warranty: You're free and on your own here. This code is not necessarily up-to-date or of public quality. # --url-- http://www.tranzoa.net/tzpython/ # --email-- pycode is the name to send to. tranzoa.com is the place to send to. # --bodstamps-- # November 2, 2014 bar # November 3, 2014 bar try to handle 0xffff... and 0 hashes # November 8, 2014 bar put the file in file name order # --show_diffs # November 9, 2014 bar phash # November 12, 2014 bar ahash() and mhash() # November 14, 2014 bar ahash and mhash return numpy uint64's # May 25, 2015 bar use tzlib's bit_count # January 21, 2017 bar allow outsiders to pass numpy arrays to the image hash rtns # --eodstamps-- ## \file # \namespace tzpython.image_hash # # # Hash image files or look for an image in a list of hashes. # # The current logic for handling too-simple hashs only looks for 2 bits off 0 or 0xffff... # That 2 bits could be something else. # How to measure an acceptable, sufficiently complex hash? # # Space filling curve makes for not many (almost no) 0xffff.... or 0 hashes. # So, "sufficiently complex" sensor would be good. # # Are the always-zero high bits of phash's right? # # One bit is extra in phash to replace the DC component that's skipped. # Is this phash logic even correct? # It could be something about the global picture. # More than half the coefficients greater than average?. # # Handle pattern images - filled with a pattern. They tend to be 0xfffffffff... or 0. # ahash - subtract each pixel from the average pixel? # hash the center quarter of the image, zooming in until the hash is suffiently complex? # split image up in to 9 sections or 4 sections 123 -> 12 23 45 56 # 456 45 56 78 89 # 789 # and hash each? # # Two images same but with different light level? # # ahash - average or median for reference? # # Different textures _img_7532.jpg and _img_0609.jpg # # Or: # 12x5 space filling curve for dhash: # 5 5 # 4 5 # 3 5 # 2 5 # 1 5 # 1 4 # 2 4 # 3 4 # 3 3 # 2 3 # 1 3 # 1 2 # 1 1 # 2 1 # 2 2 # 3 2 # 3 1 # 4 1 # 4 2 # 5 2 # 5 1 # 6 1 # 6 2 # 7 2 # 7 1 # 8 1 # 9 1 # 9 2 # 8 2 # 8 3 # 9 3 # 10 3 # 11 3 # 11 2 # 10 2 # 10 1 # 11 1 # 12 1 # 12 2 # 12 3 # 12 4 # 12 5 # 11 5 # 11 4 # 10 4 # 10 5 # 9 5 # 9 4 # 8 4 # 8 5 # 7 5 # 6 5 # 6 4 # 7 4 # 7 3 # 6 3 # 5 3 # 4 3 # 4 4 # 5 4 # # import math import sys import os from PIL import Image, ImageOps import numpy import tzlib import tgcmsg VANILLA_CUTOFF = 2 # if the hash is this close or closer to 0xffff... or 0, then rotate the image 90 degrees to start it out def bad_pop_count(h) : """ Return False if this hash is too vanilla to be used. All black or white or gray image, for instance. """ if (tzlib.bit_count(h ^ 0xffffFFFFffffFFFF) <= VANILLA_CUTOFF) or (tzlib.bit_count(h) <= VANILLA_CUTOFF) : return(True) h = (h ^ (h >> 32)) & 0xffffFFFF if (tzlib.bit_count(h ^ 0x00000000ffffFFFF) <= VANILLA_CUTOFF) or (tzlib.bit_count(h) <= VANILLA_CUTOFF) : return(True) return(False) # # http://www.janeriksolem.net/2009/06/histogram-equalization-with-python-and.html # def histeq(img, nbr_bins=256) : """ Histogram equalize a gray scale image. """ im = numpy.array() hist, bins = numpy.histogram(im.flatten(), nbr_bins, normed = True) # get image histogram cdf = hist.cumsum() # cumulative distribution function cdf = 255 * cdf / cdf[-1] # normalize im2 = numpy.interp(im.flatten(), bins[:-1], cdf) # use linear interpolation of cdf to find new pixel values return(im2.reshape(im.shape), cdf) def equalize_image(img) : """ Histogram equalize an image after forcing it to grayscale. """ return(ImageOps.equalize(ImageOps.grayscale(img))) hilbert_curve = None if True : hilbert_curve = [ [ 4, 8, ], [ 4, 7, ], [ 3, 7, ], [ 3, 8, ], ] hilbert_curve += [ [ y - 6, x + 4, ] for x, y in hilbert_curve ] hilbert_curve += [ [ x, 13 - y, ] for x, y in hilbert_curve[::-1] ] hilbert_curve += [ [ x, 9 - y, ] for x, y in hilbert_curve[::-1] ] hilbert_curve += [ [ 9 - x, 9 - y, ] for x, y in hilbert_curve ] hilbert_curve = [ [ x - 1, y - 1, ] for x, y in hilbert_curve ] hilbert_curve.append(hilbert_curve[0]) hilbert_curve = [ (y * 8) + x for x, y in hilbert_curve ] # print hilbert_curve # sys.exit(1) # # This blog entry that started this all: # # http://www.hackerfactor.com/blog/?/archives/529-Kind-of-Like-That.html # def dhash(img) : """ Return a 64-bit difference hash of the image. """ if tzlib.is_numpy_array(img) : img = Image.fromarray(img) img = ImageOps.grayscale(img) # for outsiders who may not remember to do this img = img.resize(( (hilbert_curve and 8) or 9, 8 ), Image.ANTIALIAS) dat = img.getdata() h = 0 one = 1 if hilbert_curve : for hi, ii in enumerate(hilbert_curve[:-1]) : if dat[hilbert_curve[hi + 1]] >= dat[ii] : h |= one << hi pass pass else : ii = 0 pi = 0 for r in xrange(img.size[1]) : for c in xrange(img.size[0] - 1) : if dat[ii + one] >= dat[ii] : h |= one << pi # print "@@@@", ii, int(ii / 9), int(ii % 9) pi += one ii += one ii += one pass return(numpy.uint64(long(h))) def _amhash(img, rtn) : """ Return a 64-bit something hash of the image. """ if tzlib.is_numpy_array(img) : img = Image.fromarray(img) img = ImageOps.grayscale(img) # for outsiders who may not remember to do this img = img.resize(( 8, 8 ), Image.ANTIALIAS) dat = numpy.asarray(img).flatten() avg = rtn(dat) # print "@@@@ avg", avg, dat, [ ord(c) for c in img.tostring() ] h = 0 for pi, p in enumerate(dat) : if p >= avg : h |= (1 << pi) pass return(numpy.uint64(long(h))) def ahash(img) : """ Return a 64-bit average hash of the image. """ return(_amhash(img, numpy.mean)) def mhash(img) : """ Return a 64-bit median hash of the image. """ return(_amhash(img, numpy.median)) PHASH_IMAGE_SIZE = 32 PHASH_NUM_DCT_COEF = 8 DCT = numpy.matrix([ [ math.sqrt(2.0 / PHASH_IMAGE_SIZE) * math.cos((math.pi / 2 / PHASH_IMAGE_SIZE) * y * (2 * x + 1)) for x in xrange(PHASH_IMAGE_SIZE) ] for y in xrange(1, PHASH_NUM_DCT_COEF) ]) DCT_T = numpy.transpose(DCT) def phash(img) : """ Return a 64-bit DCT hash of the image. """ if tzlib.is_numpy_array(img) : img = Image.fromarray(img) img = ImageOps.grayscale(img) # for outsiders who may not remember to do this img = img.resize(( PHASH_IMAGE_SIZE, PHASH_IMAGE_SIZE ), Image.ANTIALIAS) ca = numpy.array((DCT * numpy.array(img.getdata(), numpy.float).reshape(PHASH_IMAGE_SIZE, PHASH_IMAGE_SIZE) * DCT_T)).flatten() m = numpy.median(ca) # print "@@@@", len(ca), ca, m return(sum((1 << i) for i, c in enumerate(ca) if c > m)) def prep_img(img, equalize = False, wide = False) : """ Return the image changed according to the command line options. Equalize and/or rotate the image. """ if equalize : # img.putdata(histeq(img)[0]) img = ImageOps.equalize(img) if wide : if img.size[0] < img.size[1] : img = img.transpose(Image.ROTATE_270) pass return(img) def _fix_dhash_img(img, equalize, wide) : """ Return the image changed according to the command line options and the dhash. Rotate the image if we must. """ img = prep_img(img, equalize, wide) dh = dhash(img) if bad_pop_count(dh) : timg = img.transpose(Image.ROTATE_90) tdh = dhash(timg) if not bad_pop_count(tdh) : if verbose > 4 : print "Black or white: Rotate" img = timg dh = tdh pass return(img, dh) def print_dupes(dh, fn, ofn) : """ Print duplicates. """ print "Duplicate 0x%016x" % long(dh), os.path.basename( fn), os.path.dirname( fn) print " ", os.path.basename(ofn), os.path.dirname(ofn) class an_image(object) : def __init__(me, fn, h) : me.fn = fn me.h = h me.k = 0 # an_image def dist_cmp_rtn(me, om) : return(int(tzlib.bit_count(me.h ^ om.h))) def center_rtn(img_a) : h = numpy.uint64(0) l2 = (len(img_a) + 1) / 2 one = numpy.uint64(1) for b in xrange(64) : m = one << b if sum([ 1 for i in img_a if i.h & m ]) >= l2 : h |= m pass return(an_image("", h)) def show_clusters(hashs, K) : """ K-means cluster the given images and print the results. """ a = [ an_image(hashs[k], k) for k in hashs.keys() ] kma = tzlib.kmeans_cluster(a, K, distance_rtn = dist_cmp_rtn, make_center_rtn = center_rtn) for i, img in enumerate(a) : img.k = kma[i] a.sort(lambda a, b : cmp(a.k, b.k) or cmp(a.fn.lower(), b.fn.lower()) or cmp(a.h, b.h)) pk = -1 for img in a : if img.k != pk : print pk = img.k print "K %2u %016x %s" % ( img.k, long(img.h), img.fn, ) pass help_str = """ %s (options) ambiguous_file_name... Hashes the given images or finds the given images in a hash-output file. Options: --dhash output_hash_file_name Output the dHashes of the input image files to the given file. --find_in hash_file_name Find the input image files by matching hashes in given hash file. --equalize Equalize the images. --wide Only compare images in wider-than-high orientation. --sub_dirs Find input files in sub-directories. --show_diffs Print hash differences between sorted files. --kmeans K Print images by K-means groups. --verbose Increase the verbosity level. This program computes hashes of the input image files and puts them along with the file name in an output (tgcmsg/AMP) text file. And this program finds matches of given input images in such a text file containing hashes and image file names. If an input file name is a non-existent .dhash file, this program computes the hashes of the other input files and outputs them to the file. If the .dhash file exists, this program finds them in the .dhash file. """ if __name__ == '__main__' : import TZCommandLineAtFile program_name = sys.argv.pop(0) TZCommandLineAtFile.expand_at_sign_command_line_files(sys.argv) dhash_file = None phash_file = None find_files = [] equalize = False show_diffs = False K = 0 wide = False sub_dirs = False verbose = 0 while True : oi = tzlib.array_find(sys.argv, [ "--help", "-h", "-?", "/h", "/H", "/?" ] ) if oi < 0 : break del sys.argv[oi] print help_str % ( os.path.basename(program_name), ) sys.exit(254) while True : oi = tzlib.array_find(sys.argv, [ "--verbose", "-v", ] ) if oi < 0 : break del sys.argv[oi] verbose += 1 while True : oi = tzlib.array_find(sys.argv, [ "--sub_dirs", "--sub-dirs", "--subdirs", "--sub_dir", "--sub-dir", "--subdir", "-s", "--recurs", "--recursive", "-r", ] ) if oi < 0 : break del sys.argv[oi] sub_dirs = True while True : oi = tzlib.array_find(sys.argv, [ "--equalize", "--histogram_equalize", "--histogram-equalize", "--histogramequalize", "--he", "-e", ] ) if oi < 0 : break del sys.argv[oi] equalize = True while True : oi = tzlib.array_find(sys.argv, [ "--wide", "--orient", "-w", ] ) if oi < 0 : break del sys.argv[oi] wide = True while True : oi = tzlib.array_find(sys.argv, [ "--dhash", "--dHash", "--dh", ] ) if oi < 0 : break del sys.argv[oi] if dhash_file : print >>sys.stderr, "Only one dHash output file per customer, please!" sys.exit(101) dhash_file = sys.argv.pop(oi) while True : oi = tzlib.array_find(sys.argv, [ "--phash", "--dHash", "--ph", ] ) if oi < 0 : break del sys.argv[oi] if phash_file : print >>sys.stderr, "Only one dHash output file per customer, please!" sys.exit(101) phash_file = sys.argv.pop(oi) while True : oi = tzlib.array_find(sys.argv, [ "--find", "--find_in", "--find-in", "--findin", "-f", ] ) if oi < 0 : break del sys.argv[oi] find_files.append(sys.argv.pop(oi)) while True : oi = tzlib.array_find(sys.argv, [ "--show_diffs", "--show-diffs", "--showdiffs", "--show_diff", "--show-diff", "--showdiff", ] ) if oi < 0 : break del sys.argv[oi] show_diffs = True while True : oi = tzlib.array_find(sys.argv, [ "--k_means", "--k-means", "--kmeans", "-K", "-k", ] ) if oi < 0 : break del sys.argv[oi] K = int(sys.argv.pop(oi)) fns = {} while len(sys.argv) : fn = sys.argv.pop(0) fa = tzlib.ambiguous_file_list(fn, do_sub_dirs = sub_dirs) if not len(fa) : fns[fn] = True else : fns.update(tzlib.make_dictionary(fa)) pass if not len(fns) : print >>sys.stderr, "Tell me files to hash or find" sys.exit(101) fns = fns.keys() if (not dhash_file) and (not phash_file) and (not len(find_files)) : for fi, fn in enumerate(fns) : ext = os.path.splitext(fn)[1].lower() if ext in [ '.dhash', '.phash', ] : if os.path.exists(fn) : find_files.append(fn) elif ext == '.dhash' : dhash_file = fn else : phash_file = fn break pass pass if (dhash_file or phash_file) and len(find_files) : print >>sys.stderr, "I cannot both create a .dhash/.phash file and look up images in it!" sys.exit(102) if (not dhash_file) and (not phash_file) and (not len(find_files)) : print >>sys.stderr, "Tell me a .dhash/.phash file to output or to compare images against!" sys.exit(102) fns.sort(lambda a, b : cmp(a.lower(), b.lower())) if verbose > 2 : for fn in fns : print fn pass dhashs = {} phashs = {} for fn in find_files : msgs = tgcmsg.amp_messages_from_file(fn) if (msgs is None) or (not len(msgs)) : print >>sys.stderr, "No hashes in %s!" % fn sys.exit(103) for m in [ m for m in msgs if m[0] == 'dhash' ] : dhashs[int(m[1], 16)] = m[2] for m in [ m for m in msgs if m[0] == 'phash' ] : phashs[int(m[1], 16)] = m[2] pass if verbose : if len(find_files) : print len(dhashs), "known image file dhashes", print len(phashs), "known image file phashes", print len([ fn for fn in fns if os.path.splitext(fn)[1].lower() not in [ '.dhash', '.phash', ] ]), "images to find." dupes = [] for fn in fns : if os.path.splitext(fn)[1].lower() not in [ '.dhash', '.phash', ] : cmg = Image.open(fn) # rbg = cmg.split() # rbg[2].save('xyzzb.png') img, dh = _fix_dhash_img(ImageOps.grayscale(cmg), equalize, wide) if bad_pop_count(dh) : smg = cmg.split() if verbose > 4 : print "Black or white: Red" try : img, dh = _fix_dhash_img(smg[0], equalize, wide) # try just the red color except IndexError : pass pass if bad_pop_count(dh) : if verbose > 4 : print "Black or white: Green" try : img, dh = _fix_dhash_img(smg[1], equalize, wide) # try just the green color except IndexError : pass pass if bad_pop_count(dh) : if verbose > 4 : print "Black or white: Blue" try : img, dh = _fix_dhash_img(smg[2], equalize, wide) # try just the blue color except IndexError : pass pass if bad_pop_count(dh) : if verbose > 4 : print "Black or white: Hopeless." img, dh = _fix_dhash_img(ImageOps.grayscale(cmg), equalize, wide) # punt ph = phash(prep_img(cmg, equalize, wide)) if len(find_files) : dhs = [] dhs.append(ph) dhs.append(dh) img = img.transpose(Image.FLIP_TOP_BOTTOM) dhs.append(dhash(img)) img = img.transpose(Image.FLIP_LEFT_RIGHT) dhs.append(dhash(img)) img = img.transpose(Image.FLIP_TOP_BOTTOM) dhs.append(dhash(img)) if (not wide) or (img.size[0] == img.size[1]) : img = img.transpose(Image.ROTATE_90) dhs.append(dhash(img)) img = img.transpose(Image.FLIP_TOP_BOTTOM) dhs.append(dhash(img)) img = img.transpose(Image.FLIP_LEFT_RIGHT) dhs.append(dhash(img)) img = img.transpose(Image.FLIP_TOP_BOTTOM) dhs.append(dhash(img)) bh = -1 bi = -1 br = 65 obr = br for hi, h in enumerate(dhs) : for fh in dhashs.keys() + phashs.keys() : r = tzlib.bit_count(h ^ fh) if br > r : obr = br br = r bh = fh bi = hi elif (br == r) and (bh != fh) : obr = br br = r bh = fh bi = hi elif obr > r : obr = r pass pass print 'Orientation:%u Diff:%2u %2u 2nd best:%2u for "%s" - found "%s"' % ( bi, obr - br, br, obr, os.path.basename(fn), dhashs.get(bh, phashs.get(bh, None)), ) if verbose > 1 : print " ", "Un-transformed: dhash %016x - phash %016x" % ( long(dh), long(ph), ), [ "%016x" % long(h) for h in dhs ], pass elif dh in dhashs : print_dupes( dh, fn, dhashs[dh]) dupes.append([ dh, fn, dhashs[dh], ]) elif ph in phashs : print_dupes( ph, fn, phashs[ph]) dupes.append([ ph, fn, phashs[ph], ]) else : if verbose : print fn, "dhash:0x%016x phash:0x%016x" % ( long(dh), long(ph), ) dhashs[dh] = fn phashs[ph] = fn pass pass if dhash_file : ha = dhashs.keys() ha.sort(lambda a, b : cmp(dhashs[a].lower(), dhashs[b].lower()) or cmp(a, b)) tgcmsg.amp_messages_to_file(dhash_file, [ [ 'dhash', "0x%016x" % long(h), dhashs[h], ] for h in ha ]) if phash_file : ha = phashs.keys() ha.sort(lambda a, b : cmp(phashs[a].lower(), phashs[b].lower()) or cmp(a, b)) tgcmsg.amp_messages_to_file(dhash_file, [ [ 'phash', "0x%016x" % long(h), phashs[h], ] for h in ha ]) hashs = dhashs if phash_file : hashs = phashs if len(dupes) : print "Duplicates" for h, fn, ofn in dupes : print_dupes(h, fn, ofn) pass if show_diffs and (dhash_file or phash_file) : ha = hashs.keys() ha.sort(lambda a, b : cmp(hashs[a].lower(), hashs[b].lower()) or cmp(a, b)) ph = [ [ tzlib.bit_count(h ^ ha[(hi + 1) % len(ha)]), h, ] for hi, h in enumerate(ha) ] ph.sort() for d, h in ph : print "diff %2u %s" % ( int(d), hashs[h], ) pass if 0 < K <= len(hashs) : show_clusters(hashs, K) pass # # # eof