2

I am looking for algorithms or models for detecting and identifying repeated patterns in a single image. For example, an arbitrary smaller image might be pasted at random locations in the image. In the situation at hand, no prior information is known about the appearance of the object or pattern.

Do any algorithms/models for this exist?

interoception
  • 123
  • 4
  • 1
    See https://stackoverflow.com/q/5008040 – jon_simon Nov 04 '21 at 02:58
  • 1
    Those answers are about a decade dated, and I believe there may have been progress on this problem since then. – interoception Nov 05 '21 at 17:52
  • Fourier transforms are good for detecting generic repeating sequences of pixels. I'm sure there are better methods using convolutional networks, but those depend more on the details of your problem. – jon_simon Nov 05 '21 at 20:11
  • For example is there a single repeating image patch that you're looking for, or multiple? Does this patch appear with different sizes, or different rotations? Do you know what this patch looks like in advance and you're simply trying to localize it within in the image, or are you trying to find any such image patch that may be present? All of these details will change the approach – jon_simon Nov 05 '21 at 20:14
  • I'm not sure how a FT would help me identify the pattern, but I can see how it would help me identify the period. The patch is not rotated or scaled, just possibly differing by some amount of noise. Not known in advance. More than one class of patches, but we can assume only one for now. – interoception Nov 07 '21 at 16:13
  • In that case you could just do something brute-force like extract all possible image patches and convolve them with the image, and see where you get big big spikes in the output value. Those will correspond to one patch landing on top of its (near) duplicate. – jon_simon Nov 10 '21 at 03:02
  • Thanks for the suggestion. The problem with that approach is that it's prohibitively expensive. For an $m\times n$ image, it's at least $\mathcal O(m^2 n^2)$. – interoception Nov 14 '21 at 15:26
  • Another thing you could do that would be more computationally efficient, is to convolve the entire image over itself. In that case, any large-ish repeating patterns in the image will produce spikes in the output value, albeit noisy ones. That will at least narrow down the locations in the image that you need to take a closer look at. – jon_simon Nov 15 '21 at 20:37
  • Another "more modern" approach https://www.researchgate.net/publication/316948619_Repeated_Pattern_Detection_Using_CNN_Activations – jon_simon Nov 15 '21 at 20:42
  • Yes, convolving the image over itself is actually the same idea I had. I'm finding that it's nontrivial to pick the right "spikes", however. – interoception Nov 17 '21 at 02:20

0 Answers0