1

I want to create a mapping in Python that will use images as keys, but treat similar (but not identical) images as the same key. I have an approach for deciding which images are similar enough: I shrink them, convert them to line art, and then compute the md5 sum. Two images are "similar enough" applying this process to them generates the same result (and as one would hope this relation is transitive).

Computing this checksum is computation-intensive, so I'd prefer to do so fewer times. In order to do so, I think I should write a SmartImage (need better name) wrapper for PIL's images that caches the result of the checksum. From there I can think of two designs:

  1. Subclass collections.MutableMapping and create a dictionary-like class that operates on images and, under the hood, computes my check sum and sticks the results in some other mutable mapping (a shelf, in my case)
  2. Give SmartImage a custom __hash__ method that reports my checksum and then go ahead and use it with whatever collection class is convenient. Perhaps I'd have to supply some other methods (maybe __eq__) as well.

My question is, is option #2 palatable, or is the bar for having the same hash code in Python high enough that even a class that is specially designed to do fuzzy matching should not give the same hash value for non-identical images?

def get_thumbnail(image):
    im2 = image.copy()
    return im2.convert("L")


def image_pixel_hash_code(image):
    pixels = list(image.getdata())
    avg = sum(pixels) / len(pixels)
    bits = bitarray(1 if pixel < avg else 0 for pixel in pixels)
    return b64encode(hashlib.md5(str(bits)).hexdigest())
7
  • Is there a reason you are not using existing "similar image" algorithms? You'll find the hash to be an enormously high bar. "Similar" is a concept that image processing folk have been working at very hard for three or four decades now...
    – Cort Ammon
    Aug 3, 2015 at 1:39
  • @CortAmmon, the hash technique I'm using here has two advantages: 1. it is transitive (if a is similar to b and b is similar to c, then a is similar to c); and 2. I can check in constant time whether a new image matches one that is already in the collection. A few months ago I posted a question looking for alternatives here.
    – kuzzooroo
    Aug 3, 2015 at 1:41
  • Have you generated two similar images? It surprises me that the line art approach generates exactly the same result for two similar images, bit for bit.
    – Cort Ammon
    Aug 3, 2015 at 3:42
  • @CortAmmon: to me it sounds the OP is exactly doing this - using a well-known algorithm for detecting similar images. I do not have any references at hand, but I am pretty sure the idea of comparing image after shrinking/simplifying them is not novel.
    – Doc Brown
    Aug 3, 2015 at 4:36
  • 1
    @kuzzooroo: I do not understand your question. Hash functions never guarantee to deliver different values for for different objects, they only guarantee to return the same value for similar objects. That is why you always must implement a custom equality comparer when you provide a custom hash function - to give the container a chance to test if two objects with same hash are really equal. And this is in no way special to your case, nor special to Python.
    – Doc Brown
    Aug 3, 2015 at 4:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.