[ansgri]

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 you have to limit your feature space in a way that would have consistent behavior across transformed versions of the image.

[pippy360]

>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 on it and hopefully find solutions).

[bobosha]

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

[pippy360]

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.

[alkoumpa]

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

[pippy360]

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

[JepZ]

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