|
I've been tinkering a bit with corner detection algorithms, and the question was asked: could the corners found with something like SIFT/FAST be used to determine whether a larger image contains something resembling a smaller image, especially in a manner that is rotation and/or scale invariant. It occurred to me that the 'corner' points could be assembled in a graph (ala graph theory), and if a fast algorithm existed for checking whether the graph for the target image is a sub-graph of the larger image's graph -- then viola, it's a match. Ignoring all the details of how the graphs would be connected, I was suddenly reminded of something from my graph theory class about checking whether one graph is a subgraph of another is NP or NP-hard. So, the question is, essentially: is checking the similarity of a set of corners generated from two images an NP or NP-hard problem? |
|
This, in graphs, is the bipartite matching problem. It is usually polynomial.
This answer is marked "community wiki".
So, you're thinking if I identify all the 'matchings' in a graph, then try to identify some subset of those as being equivalent to the 'matchings' in the smaller image ... or something to that effect?
(Jul 09 '11 at 20:45)
Brian Vandenberg
Build a bipartite graph with all SIFT points in each image as one of the bipartite components, with edged between sift points in different images corresponding to their similarity. A maximum match now pairs each point in the image with less points with a point in the image with more points such that the sum of the chosen edges is maximized. The main flaw in this is that it doesn't respect geometric constraints, but actually considering all constraints on the shape of something that can arise from 3d movements and projections is too much for me, and would probably make it np-complete.
(Jul 10 '11 at 03:53)
Alexandre Passos ♦
I was thinking of it from the perspective of something reminiscent of a max cut min flow problem. I suppose you could do it using a modified SIFT/FAST algorithm that uses the lines found that create the corners to also dictate node/edge relationships -- that would add a geometric constraint but allow you to ignore distances.
(Jul 11 '11 at 01:00)
Brian Vandenberg
Usually these bipartite matching algoritms are solved using max flow techniques (usually it's max flow/min cut, not the opposite, that people talk about, as generally min flow is no flow at all :-) ); you can see more details on the wikipedia page I linked above. Intuitively, you build a graph like I described above and connect an infinite capacity source to all nodes in one image and an infinite capacity sink to all nodes in the other image. After solving a max flow problem it is easy to see that each node in one image is paired with at most one node in the other image (the only exception in the complete bipartite case being if there are more nodes in one image than in the other), and the edges connecting these paired nodes have maximum sum.
(Jul 11 '11 at 03:10)
Alexandre Passos ♦
I can see where it could run into problems, but a less constrained solution could be sought -- eg, some way of ranking it based on similarity as opposed to seeking an exact match.
(Jul 12 '11 at 02:07)
Brian Vandenberg
Brian: using a matching algorithm will give you the best sum of similarities overall, not just the greedy best pair for each single node. If you want you can probably find a way to corrupt that solution and find good alternatives, but I don't think there is a K-best algorithm because in the combinatorial case (with 0/1 edge weights) there can be an exponential number of maximum-value matchings.
(Jul 12 '11 at 03:43)
Alexandre Passos ♦
showing 5 of 6
show all
|
You could certainly make a fast algorithm that does this heuristically, but in general any sort of sub-graph finding is NP-hard. However, you have the neat advantage of planarity, which should put it in P.