Show HN: Transformation Invariant Reverse Image Search

Hey guys, I&#x27;m the guy who made this. Let me know if anything isn&#x27;t clear or if you have any questions.<p>*I developed this after I saw how poor google (and any other reverse image search engine I tested, like bing&#x2F;tineye) performed on rotated images, for example google doesn&#x27;t match this image [0] to it&#x27;s original [1] (google&#x27;s neural network will find that it is a cat but won&#x27;t match to the original). After playing around with trying to make my algorithm (uniform&#x2F;nonuniform) scale and rotation invariant I found that I was able to make it fully 2D affine invariant (pretty much by luck)<p>I developed all this in my spare time actively for about about a year. I also have a c++ implementation that let&#x27;s you reproduce all this but it&#x27;s just a proof of concept and so it&#x27;s quite slow. You can check that out on my github here [2]. There are loads of ways this can be improved but I wanted to get the idea out quickly.<p>[0] <a href="https:&#x2F;&#x2F;github.com&#x2F;pippy360&#x2F;transformationInvariantImageSearch&#x2F;blob&#x2F;master&#x2F;fullEndToEndDemo&#x2F;inputImages&#x2F;cat2.png" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pippy360&#x2F;transformationInvariantImageSear...</a><p>[1] <a href="https:&#x2F;&#x2F;github.com&#x2F;pippy360&#x2F;transformationInvariantImageSearch&#x2F;blob&#x2F;master&#x2F;fullEndToEndDemo&#x2F;inputImages&#x2F;cat_original.png" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pippy360&#x2F;transformationInvariantImageSear...</a><p>[2] <a href="https:&#x2F;&#x2F;github.com&#x2F;pippy360&#x2F;transformationInvariantImageSearch" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pippy360&#x2F;transformationInvariantImageSear...</a>

Good in its simplicity. Basically, they construct not-quite-but-local hyperfeatures using edge triangles and then compute a descriptor (perceptual hash) for all these hyperfeatures. In this way, you get many features on different scales allowing for retrieving composed images, and, when comparing, use the most informative fragment available.<p>The big problem is, a moderately complex image can yield n³ triangles, so you have to limit your feature space in a way that would have consistent behavior across transformed versions of the image.

Awesome work! Thanks for sharing this!<p>Reminds me of nova.astrometry.net and PixInsight (and others), which are able to determine which stars are in an image, regardless of transforms.<p>Relevant paper (outlines an approach using triangle space): <a href="https:&#x2F;&#x2F;hal.inria.fr&#x2F;inria-00548539&#x2F;document" rel="nofollow">https:&#x2F;&#x2F;hal.inria.fr&#x2F;inria-00548539&#x2F;document</a><p>Relevant section: &quot;Provided the reduced object lists, our next step is to construct all possible triangles. From the list of n objects we can construct n(n − 1)(n − 2)&#x2F;6 triangles. Those will be represented in so called &quot;triangle space&quot;. We need to choose a triangle representation that will let us find similar triangles, that is to find corresponding object triplets being insensitive to translation, rotation, scaling and flipping. A triangle in the triangle space could be represented as a two-dimensional point (x, y) where x = a&#x2F;b, y = b&#x2F;c.<p>a, b and c are the lengths of triangle sides in decreasing order. Similar triangles will be located close to each other in the triangle space.&quot;

This is really impressive. What I particularly like is how the demo demonstrates the usefulness of the algorithm - an article about it would be interesting, but after I cropped, scaled, rotated and moved the dog&#x27;s head, and it was still found, it was just so <i>obviously</i> useful. For example, if someone did the same thing with a photo of a person&#x27;s face you could find the original image it came from.

This is great, I was toying with this kind of image recognition a year or two ago and I am impressed with this.<p>Have you considered doing other common transformations like various Instagram filters and compression loss? If you had those abilities combined with the current algorithm you could have the kernel of a photo copyright protection system . . .

That is really gorgeous, do you have anything quick written up about how your hashes are stored? I spent far too much of a few months optimizing phash to hell (I can do fuzzy lookups in a table of ~17 million images in constant time)and I&#x27;d love to play with your math a little bit

Really cool! I love how more and more mathematical ideas (like translation invariance) are seeping into the programming community. I suspect that this will have a bigger and longer lasting impact on software engineering as a result of the current machine learning hype, than will any particular technology that it may produce.

Very impressive indeed. I was wondering, how did you determine your criteria for matching (i.e. the hash distance at which two triangles are considered different)? Also, could this be extended to colour transformations as well (perhaps by using a wavelet transform to extract phase for comparison, rather than amplitude)?

When you say this is a reverse image search, does it search over multiple images to find the one which matches the closest? In the demo it seems to only search over a single image to find the cropped, stretched or rotated part of the image. Do you also have examples of negative searches where it doesn&#x27;t find the image in question?

This is awesome! Do you have any resources to dive into reverse image search? I am not familiar with the standard methods and I am looking for more than the pyimagesearch&#x27;s tutorial of using histogram matching, I am interested in learning what the standard is and any tutorials&#x2F;implementations

This is pretty neat. I&#x27;ve been using pHash to find duplicate photos across my personal library, but this seems significantly better. I&#x27;d like to wrap it as a Python library - what are the bits that need improving?

I&#x27;m amazed at how simple this is! Making the triangles equilateral is one of those things which seems so simple in hindsight but I doubt it was easy to think of, were you inspired by anything in particular?

Beautifully done! Affine transformations! Gotta love that Jacobian, baby.