algorithm - Recognize recurring images into a larger one

Question

Edit: this is not a duplicate of Determine if an image exists within a larger image, and if so, find it, using Python since I do not know the pattern beforehand

Suppose I have a big image (usually a picture taken with a camera so it might be a bit noisy, but let's assume it's not for now) made up of multiple smaller images all equal among themselves, something like

I need to find the contour of each one of those. The first step is recognizing that there's a recurring image (or unknown pattern) in the 2D image. How can I achieve this first step?

I did read around that I might use a FFT of the original image and search for duplicate frequencies, would that be a feasible approach?

To build a bit on the problem: I do not know the image beforehand, nor its size or how many will there be on the big image. The images can be shot from camera so they might be noisy. The images won't overlap.

Answer 1

You can try to use described keypoints (Sift/SURF/ORB/etc.) to find features in the image and try to detect the same features in the image. You can see such a result in How to find euclidean distance between keypoints of a single image in opencv where 3x the same image is present and features are detected and linked between those subimages automatically.

In your image the result looks like

so you can see that the different occurances of the same pattern is indeed automatically detected and linked.

Next steps would be to group features to objects, so that the "whole" pattern can be extracted. Once you have a candidate for a pattern, you can extract a homography for each occurance of the pattern (with one reference candidate pattern) to verify that it is a pattern. One open problem is how to find such candidates. Maybe it is worth trying to find "parallel features", so keypoint matches that have parallel lines and/or same length lines (see image). Or maybe there is some graph theory approach.

All in all, this whole approach will have some advantages and disadvantes:

Advantages:

• real world applicability - Sift and other keypoints are working quite well even with noise and some perspective effects, so chances are increased to find such patterns.

Disadvantages

• slow
• parametric (define what it means that two features are successfully matched)
• not suitable for all kind of patterns - your pattern must have some extractable keypoints

Those are some thoughts and probably not complete ;)

Unfortunately no full code yet for your concrete task, but I hope the idea is clear.