Image patch matching using probabilistic sampling based on an oracle

In a digital medium environment for performing one or more of digital image modifications or digital image object recognition, a computer-implemented method of image patch matching comprising:

• selecting proposal image patches;
• determining approximate similarity scores for the selected proposal image patches;
• accepting image patches from the selected proposal image patches to further evaluate based on a probability inversely proportional to the approximate similarity scores;
• determining similarity scores for the accepted image patches;
• and
• identifying, based on the determined similarity scores, an image patch that matches a target image patch.

A system for performing one or more of digital image modifications or digital image object recognition comprising:

• a memory comprising:
• a similarity heuristic that allows for a determination of whether image patches match;
• and
• an approximate similarity heuristic that is less computationally intensive than the similarity heuristic;
• and
• a server device comprising instructions thereon that, when executed by at least one processor, cause the server device to:
• identify proposal image patches;
• determine approximate similarity scores for the proposal image patches using the approximate similarity heuristic;
• accept proposal image patches to further evaluate based on an acceptance probability that is inversely proportional to the approximate similarity scores;
• determine, using the similarity heuristic, similarity scores for the accepted proposal image patches that meet the acceptance probability;
• and
• identify one or more image patches that match a target image patch based on the determined similarity scores.