Show HN: Transformation Invariant Reverse Image Search • Hacker News Board

Re: Show HN: Transformation Invariant Reverse Image Search

#21

Post by pippy360 » Thu, Aug 10, 2017, 1:41 PM UTC

ansgri wrote: post #7

tw1010 wrote: post #2

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.

These invariants are standard practice in computer vision. In fact, you won't go anywhere without translation and brightness invariance, more often you need also scale (uniform) and rotation invariance, and limited projective transform tolerance. There are various ways to deal with this in ML (not really an expert in ML), but AFAIU in most cases you get candidate transforms via model-based methods, and then make the…

I think for handling truly/non-affine arbitrary transformations we will have to resort to ML. Then we could have matching very similar to how humans do it (where we really don't care if the transformation is affine/non-affine we just care if it's a huge transformation the makes the image unrecognisable). But I really don't know much about ML.

Okcupid talked about this in an article about image hashing [0] and they have a nice quote:

"The end-to-end approach of training a Convolutional Net to embed images such that the positive / negative case distances separate nicely is probably the cool new hypebeast way forward. This would have the added advantage of being able to handle whatever transformations you can think of at training time."

[0]https://tech.okcupid.com/evaluating-perceptual-image-hashes-...

Re: Show HN: Transformation Invariant Reverse Image Search

#22

Post by activatedgeek » Thu, Aug 10, 2017, 2:10 PM UTC

pippy360 wrote: post #18

activatedgeek wrote: post #15

Earlier quoted context omitted.

Hey Tom, Great work there! One question - Why are we transforming the triangles to equilateral triangles? Just throwing out a few ideas and wanted to discuss what potential flaws could they have. 1. For keypoint detection, what if you use ASIFT (Affine SIFT) which is Affine transformation friendly. In that case, you'd probably save time doing the rotations. Given the huge number of proposals we get, we might still ne…

>Why are we transforming the triangles to equilateral triangles? This is so that the extracted image fragments/triangles are always very similar and so have an extremely similar hash. If I didn't transform the triangles then, for example, a fragment of a query image might be stretched compared with the matching fragment in the database. Intuitively it makes sense that it would be easier to match image fragments if th…

Your observation regarding the triangulation makes sense. Might end up failing under most cases.

Re: Show HN: Transformation Invariant Reverse Image Search

#23

Post by ansgri » Thu, Aug 10, 2017, 2:50 PM UTC

activatedgeek wrote: post #13

lscharen wrote: post #12

Earlier quoted context omitted.

I've been out of the Machine Vision space for a while, so my knowledge is somewhat out of date. What research is out there on general Affine invariant vision algorithms and techniques? For context, my practical experience ended in the mid 2000's when "jittering" was a bit of thing along with some occasional closed form estimators based on basic linearization approximations.

ASIFT or Affine SIFT is one of the Affine invariant versions of SIFT. Take a look here - http://www.cmap.polytechnique.fr/~yu/research/ASIFT/demo.htm... .

It's actually perspective transform invariant, which is a more general class. The name is misleading.

SIFT and its multiple descendants, yes, and also things like Random Ferns, google "Boosted Random Ferns for Object Detection" (it's damn difficult to get a clean link to pdf from google...)

Re: Show HN: Transformation Invariant Reverse Image Search

#24

Post by deevnull » Thu, Aug 10, 2017, 4:14 PM UTC

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'd love to play with your math a little bit

Re: Show HN: Transformation Invariant Reverse Image Search

#25

Post by jboggan » Thu, Aug 10, 2017, 4:24 PM UTC

This is great, I was toying with this kind of image recognition a year or two ago and I am impressed with this.

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 . . .

Re: Show HN: Transformation Invariant Reverse Image Search

#26

Post by zfedoran » Thu, Aug 10, 2017, 4:39 PM UTC

Awesome work! Thanks for sharing this!

Reminds me of nova.astrometry.net and PixInsight (and others), which are able to determine which stars are in an image, regardless of transforms.

Relevant paper (outlines an approach using triangle space): https://hal.inria.fr/inria-00548539/document

Relevant section: "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)/6 triangles. Those will be represented in so called "triangle space". 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/b, y = b/c.

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."

Re: Show HN: Transformation Invariant Reverse Image Search

#27

Post by mendeza » Thu, Aug 10, 2017, 4:43 PM UTC

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's tutorial of using histogram matching, I am interested in learning what the standard is and any tutorials/implementations

Re: Show HN: Transformation Invariant Reverse Image Search

#28

Post by Sean1708 » Thu, Aug 10, 2017, 4:45 PM UTC

I'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?

Re: Show HN: Transformation Invariant Reverse Image Search

#29

Post by JepZ » Thu, Aug 10, 2017, 5:42 PM UTC

pippy360 wrote: post #20

alkoumpa wrote: post #14

Earlier quoted context omitted.

I wonder if only using non-overlapped triangles would reduce accuracy. Otherwise, it should limit the number of triangles.

It would be great if I could remove overlapping triangles then I would have near linear growth of triangles for larger images. But it's very hard to come up with a technique which removes the same overlapping triangles (and leaves the same one) and is invariant to 2D affine transformations. For example if you have 50 overlapping triangles you have to decide which 49 to remove and you have to remove the same 49 on the…

Maybe removing triangles which have one very narrow angle could help. After normalization those trinagles do not hold a lot information anyway ;-)

Re: Show HN: Transformation Invariant Reverse Image Search

#30

Post by rosenbus » Thu, Aug 10, 2017, 11:07 PM UTC

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't find the image in question?