title: Distance between N images: incrementally! (same crop, but re-compressed/adjusted)
body: <p><strong>I'm trying to figure out a geo-hashing method for images</strong>.  It is hard because the space of possible images is of much higher dimensionality than lat/lng.  (geo-hashing converts a location to a string where the string progressively refines the location)</p>
  
  <p>So, what I need is something that:</p>
  
  <ul>
  <li>INPUT: A list of JPG or PNG images on disk</li>
  <li>OUTPUT: For each image a string WHERE <strong>the longer the string prefix in common between any two images, the higher chance that the two images are the same.</strong></li>
  </ul>
  
  <p>It doesn't need to be perfect, and it doesn't need to handle extreme cases, like cropped images or heavily adjusted images.  It is intended for multiple copies of the same image at different resolutions and compression levels.</p>
  
  <p>I can't use:</p>
  
  <ul>
  <li>File or image-data hashing, because even a teeny change between two images makes a completely different hash and you don't get any proximity</li>
  <li>Image subtraction, because it won't be a N-to-N comparison.</li>
  </ul>
  
  <p>I've read in other answers to try wavelet compression or a laplacian/gaussian pyramid, but I'm not sure how to implement in Java or Python.  However, I have made progress!  </p>
  
  <ol>
  <li>Resize to 32x32 using <a href="http://today.java.net/pub/a/today/2007/04/03/perils-of-image-getscaledinstance.html" rel="nofollow">http://today.java.net/pub/a/today/2007/04/03/perils-of-image-getscaledinstance.html</a> to not discard data.  Ok that everything gets turned into a square.</li>
  <li>Create a pyramid of successively smaller thumbnails all the way down to 2x2.</li>
  <li>In the 2x2, encode up a string of "<strong>is the next pixel brighter than the current?  If so, 1, else 0</strong>"  (This throws away all hue and saturation, I may want to use hue somehow)</li>
  <li>Encode successive binary numbers from the 8x8 and 32x32 pyramids</li>
  <li>Convert the big binary number to some higher radix representation, like Base62.</li>
  </ol>
  
  <p>This seems to work well!  Minor differences from compression or color balancing aren't enough to change a "is the left side of this area brighter than the right side".  However, I think I'm re-inventing the wheel, some sort of progressive encoding might be better?  SIFT and other feature-detection is overkill, I don't need to be able to handle cropping or rotation.</p>