3

I'm looking for a good method to detect whether an image has a repeating pattern of similar shapes or is just noise with no discernible pattern. This is best shown by looking at a couple of images:

  1. The method here would return True, and ideally identify that there are ~35 repeating shapes in the image (I wouldn't expect it necessarily to identify the cropped out shape in the lower right corner.

Returns TRUE

  1. The method here would return FALSE. While there are a lot of distinct shapes in this image, it is clear visually that there is no repeating pattern of similar shapes.

Returns FALSE

A few notes:

  • The images are from patterns on a shirt. The shapes that repeat themselves aren't all exactly the same size, and may not be exactly evenly spaced. There may be anywhere from 10 shapes to several thousand shapes on a single image.
  • I do not know in advance the size or characteristics of the shapes that repeat themselves. I'm taking these images from shirts so you can imagine there are many different types of repeating shapes.
  • I've been using scipy.ndimage.measurements.label to identify all of the individual shapes in an image. I also use dilation to combine nearby shapes and can filter out really small shapes.

I've struggled to come up with a method that is flexible enough to work with the multitude of different patterns I'm dealing with but also rigid enough to reject noise.

Appreciate any help!

eyllanesc
  • 235,170
  • 19
  • 170
  • 241
Dan Kinn
  • 151
  • 2
  • 5
  • fft could work really well, but it wouldnt be able to identify how many patterns are there and it also depends on what other kind of images you intend to use it on. I suggest you give it a shot first. – Zaw Lin Oct 13 '17 at 06:14

2 Answers2

4

Not a complete answer, but hopefully some help and someone else can comment now the spectra are available...

Normally, an FFT spectrum should reveal repeating patterns. I am not the world's best at interpretation of spectra, but here they are for both your images.

I calculated with ImageMagick like this at the command-line:

convert image.jpg -fft +delete -evaluate log 100000 spectrum.png

First the patterned shirt:

enter image description here

Then the splodgy mess:

enter image description here

Yes, I know you want an OpenCV solution, and I used a different tool, but the idea is to collaborate to find a method that works first, then it can be re-formulated in OpenCV.

Mark Setchell
  • 191,897
  • 31
  • 273
  • 432
  • Thanks. This looks like we may be getting somewhere -- is there then a mathematical way to differentiate these images? Numpy in Python has a good package to perform the FFT so that isn't an issue. – Dan Kinn Oct 13 '17 at 17:24
  • Hi, @DanKinn Did you find a way to mathematically differentiate these two FFT images? I have a very similar use case where I have to detect the pattern and then extract it as well. – Spandan Thakur Mar 20 '18 at 11:29
  • @SpandanThakur unfortunately I did not find a mathematically sound way of differentiating. I used machine learning using some of the other aspects of the image as inputs and was able to do an okay job of classifying my images, but not nearly as good as I would have liked. If you find a solution I would be very interested to know your methodology. – Dan Kinn Apr 03 '18 at 18:40
2

If the repeating patterns are arranged on a regular grid so that they are self-similar by translation, this is a job for autocorrelation: if you try different translation vectors, the autocorrelation map will exhibit a strong peak where there is a match.

As the autocorrelation is compute-intensive, you will need to resort to the DFT (and its fast version) to compute it.

  • Hi -- thanks for your input. I've attempted something similar but because the images are from shirts they do not always lie in a perfect grid due to small ripples in how the shirt lies. Perhaps my example image makes it seem like the spacing on the patterns is more perfect than it usually is. I may also be mis-interpreting exactly what you're suggesting so please let me know if your method addresses this imperfect grid problem. – Dan Kinn Oct 13 '17 at 20:47
  • @DanKinn: You should have stated that upfront, it makes it a harder problem, especially with large deformation. Anyway the autocorrelation method will still show peaks, but somewhat eroded. Then you can try to compute the correlation of a window of the image, of size equal to a putative pattern size, with the whole image. Despite deformation, you will get significant peaks where the pattern repeats. –  Oct 14 '17 at 14:45