Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Transformation Invariant Reverse Image Search

pippy360.github.io

Post reply on HN
Print view View original

11–20 of 31 posts

Re: Show HN: Transformation Invariant Reverse Image Search

#11

Post by pippy360 »

rcarmo wrote: post #4

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

Unfortunately it needs a huge amount of work to be production ready. I'd love to see it wrapped up in python though and I'll be continuing to work on it. The main issue you will run into is that the number of triangles computed from the keypoints is n^3 (where n is the number of keypoints), So currently it will take far too long to match large images. I have a few ideas on how to solve this but none of them have lead to quick and easy solutions...yet

I'm currently working on an improved method for getting 2D affine invariant keypoints because the current one just barely works. After that I will be working on handling the scaling issue.

Re: Show HN: Transformation Invariant Reverse Image Search

#12

Post by lscharen »

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

Re: Show HN: Transformation Invariant Reverse Image Search

#13

Post by activatedgeek »

lscharen wrote: post #12
ansgri wrote: post #7

Earlier quoted context omitted.

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

Re: Show HN: Transformation Invariant Reverse Image Search

#14

Post by alkoumpa »

ansgri wrote: post #6

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. The big problem is, a moderately complex image can yield n³ triangles, so yo…

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

Re: Show HN: Transformation Invariant Reverse Image Search

#15

Post by activatedgeek »

pippy360 wrote: post #8

Hey guys, I'm the guy who made this. Let me know if anything isn't clear or if you have any questions. *I developed this after I saw how poor google (and any other reverse image search engine I tested, like bing/tineye) performed on rotated images, for example google doesn't match this image [0] to it's original [1] (google's neural network will find that it is a cat but won't match to the original). After playing ar…

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 need to filter out some keypoint proposals from this may be using a metric like if too many keypoints are within some 2D window, then choose the one which is farthest from all edges of the 2D window (very rough, don't know if there are other ways)

2. With the final set of keypoints, I propose that let us do Delaunay Triangulation in the hope of getting a collection of triangles which cover the complete surface area of the image making it a spatially equidistant breakdown of the image pixels.

3. Hash those triangles (maybe? how?)

4. Now given a query image, perform steps 1-3, and find the triangles which match the triangles from a database image. If the fraction of matches are above a given threshold, then this is a potential candidate for the search result.

Re: Show HN: Transformation Invariant Reverse Image Search

#16

Post by bobosha »

pippy360 wrote: post #10
ansgri wrote: post #6

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. The big problem is, a moderately complex image can yield n³ triangles, so yo…

>The big problem is, a moderately complex image can yield n³ triangles This is a big problem I have been facing. You will notice that all the images I use in my c++ demos are small for this reason. I'm trying to solve this scaling issue but I wasn't able to get a solution quickly so I decided to release this and continue to work on it and hopefully release an improved version at some point (or let other people work o…

Could you not use feature hashing to reduce to something manageable?

Re: Show HN: Transformation Invariant Reverse Image Search

#17

Post by aidos »

rcarmo wrote: post #4

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

Duplicate photos is something you can do reasonably well without resorting to the more advanced techniques, depending on how "different" the duplicates are. In general though, I'd only consider an image to be a duplicate if it's a scaled version of the original (and maybe rotated).

When I've done it in the past I've created a 5x5 greyscale thumbnail of each and then you done bitwise comparisons. You can do more complex stuff like normalisation of brightness. Really the main thing to focus on is the vectorisation so you can quickly compare truckloads of images.

If I was to do it now I'd probably use width:height ratio to reduce the search space and then quickly check the 4 rotations of my sample hash against all known hashes of the same ratio. And I'd probably start but finding all images that were under a certain size, assume they were thumbnails, and try to find matching originals so I could remove them from the data set.

It depends on what exactly has happened to your library in the first place but I'd be surprised if you had lots of images that had undergone arbitrary transformations. Though obviously, only you know what that data looks like to start with! :-)

Re: Show HN: Transformation Invariant Reverse Image Search

#18

Post by pippy360 »

activatedgeek wrote: post #15
pippy360 wrote: post #8

Hey guys, I'm the guy who made this. Let me know if anything isn't clear or if you have any questions. *I developed this after I saw how poor google (and any other reverse image search engine I tested, like bing/tineye) performed on rotated images, for example google doesn't match this image [0] to it's original [1] (google's neural network will find that it is a cat but won't match to the original). After playing ar…

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 they have the same scale/aren't stretched versions of each other. The transformation to equilateral triangles is what makes the algorithm 2D affine-invariant.

>what if you use ASIFT (Affine SIFT) which is Affine transformation friendly

I only discovered ASIFT while reading this thread, it looks very interesting and useful but I'll need to look into it more. I did test out SIFT as a keypoint finder and it performed really poorly for what I wanted to do but I didn't do a lot of testing. My current method of finding keypoints is a load of crap that I threw together for this demo, a better one would seriously improve the accuracy and speed.

>like if too many keypoints are within some 2D window/I propose that let us do Delaunay Triangulation

I looked into both Delaunay Triangulation and a 2D window as a way to decrease the number of proposals/triangles generated, but had problems with both. I will still try later to implement a 2D window. As for Delaunay Triangulation, if you play around with it on paper you can see that it's not 2D affine invariant, it might still work well for small transformations but there are affine transformations where it fails. Still I think it would be worth looking into more.

Re: Show HN: Transformation Invariant Reverse Image Search

#19

Post by pippy360 »

bobosha wrote: post #16
pippy360 wrote: post #10

Earlier quoted context omitted.

>The big problem is, a moderately complex image can yield n³ triangles This is a big problem I have been facing. You will notice that all the images I use in my c++ demos are small for this reason. I'm trying to solve this scaling issue but I wasn't able to get a solution quickly so I decided to release this and continue to work on it and hopefully release an improved version at some point (or let other people work o…

Could you not use feature hashing to reduce to something manageable?

possibly, I'm not sure what implementation you have in mind?

I find it's the combination of a poor keypoint finder, noise and needing to be able to match partial images is the problem. If I could guarantee that 99% of the keypoints in the query image would be in the matching image and that the extracted hashes wouldn't be affected (hugely) by noise and that most of the query image was present in the matching image then I could simply discard a huge amount of the triangles and only query for a manageable number of them. Obviously that's a lot to ask but the better I can make each part the more options I will have for culling the hashes. For the moment I need to query as many fragments as possible to have a good chance of finding the matching image.

Re: Show HN: Transformation Invariant Reverse Image Search

#20

Post by pippy360 »

alkoumpa wrote: post #14
ansgri wrote: post #6

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. The big problem is, a moderately complex image can yield n³ triangles, so yo…

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 query image and the matching image. But because we want to be able to do our searches in sublinear time we can't compare the two images and decided on which triangles should stay/be removed, you have to do all that in preprocessing before inserting into the database/querying. delaunay triangulation looks almost perfect but isn't invariant to 2D affine transformations

Post reply on HN