Finding repeating patterns/images in images

EthernetCable picture EthernetCable · Feb 15, 2011 · Viewed 10.7k times · Source

I've been looking around for some papers (or info) on this topic.

To avoid a misunderstanding: I'm not talking about finding a supplied pattern in multiple locations.

Repeating patterns can also be understood to mean repeating images. The definition of pattern here isn't abstract. Imagine, for instance, a brick wall. The wall is composed of individual bricks. A picture of the wall is composed of the repeating image of a brick.

The solution must preferably find the largest repeating pattern. Large in this context can be defined two ways: pixel area or number of repetitions.

In the above example, you can cut the bricks in half. In order to make a brick, you can rotate a segment and attach the halves. While the complete brick is the largest repeating image in terms of pixel area, there are 2x more repetitions of half blocks.

Any thoughts?

Answer

datenwolf picture datenwolf · Feb 16, 2011

A number of methods come to mind:

  • Fourier Transformation of the image
  • Wavelet Analysis
  • Autocorrelation

I'd start with fourier analysis: Any shape repeating in a regular pattern in the image creates a very distinct spatial frequency spectrum: One major frequency and some harmonics.