# Pattern recognition using 2D fft in matlab

I have a dataset with two columns (width and length, both in milimeter). When I make a scatter plot (please refer to the first figure), I see location of defects in a plane. I want to find if the location of the defect has some kind of pattern or it is just a noise. For that I was suggested to use 2D fft to recognize pattern. I don't have any background in 2D fft but I read some articles and used matlab function fft2. I get a plot (please refer to the second figure) which I dont I understand so much at this moment. Can any one has hint to get me going? A nice article could also be of help. I read the following article as well.

http://www.qsimaging.com/ccd_noise_interpret_ffts.html

-

## migrated from stackoverflow.comNov 8 '12 at 19:24

This question came from our site for professional and enthusiast programmers.

What are the two graphs you have provided, is the first the data you are analysing, and the second the 2d FFT output? –  trumpetlicks Nov 8 '12 at 13:28
Also, how does does result are you expecting look like for a given dataset? Is it a simple "yes" or "no" ("yes" meaning there is a pattern to the defect)? –  EitanT Nov 8 '12 at 13:29
@Chris When you realize you posted in the wrong stackexchange site, you DO NOT cross-post. You can flag your own post, and write in the comment "I think this should be posted on DSP.SE, sorry". Our lovely moderators will take care of it for you... What you did just now, cross posting, requires somebody to again flag your question, say "cross-posted", and the mods have to take care of it again. Which is ... okay... if the question has no answers yet, but if answers happened on one or both sites, it would be very hard to impossible to merge them. –  penelope Nov 8 '12 at 16:02
Heh, I actually think this question is more appropriate for stats.se! You have a set of points in a plane, and want a test for whether or not they are "randomly" distributed (what ever that would mean in this particular case). Sounds like a statistics problem! Anyway ... I admit to not understanding your fft plot. What are the axes, and what are you plotting? I would think you want to plot something like the magnitude of the fft over the u-v plane, and hope to see some big spikes in the data. Maybe look for points that are much larger than the median value? –  Dan Becker Nov 8 '12 at 17:59
You really need to explain more about what you're doing. What are you measuring? What is a "defect" and where do they appear in your first image? Why do you think an FFT will help? –  endolith Nov 8 '12 at 18:01

DFT is a great tool to find periodic patterns in signals. However, you should understand what kind of period you want to find. If you want to find a series of points that lie on a regular grid (with even spacing), or more mathematically speaking, a subset of points $(x_i,y_i)$, such that there exists $(dx,dy)$ for which the following equations hold:

$x_i = x_1 + dx*i$
$y_i =y_1 + dy*j$

(The patterns can also be rotated, and DFT will still find them).

You should compute a 2D histogram of your data, with large number of bins, and run DFT on it. Afterwards, you should look for a peak in any location expect the DC. An ideal noise should have no patters, thus the contrast of the frequencies responses should be very low.

-

I think you need some kind of "resolution" in the data. Think you have to convert it to a regular grid. I would say: "no periodicity analysis without data, that has a periodic grid". Correct me if I'm wrong, but I think the fft needs a lower boundary, which is the resolution and a higher boundary, which is the total colums and rows. If you work with points on a 2d plane, whose positions are set by floating point numbers, the fft would have to search for infinitesimal small frequencys. But follow this question about fft of irregular shaped data. Maybe someone comes up with an idea.

For example you could do a 2d histogram with bins that are so small that they hold only one or two values. This way you get a rectangular grid.

I did 2D fft on a rectangular grid with data that is distributed in a similar way as yours and got a very fuzzy 2D spectrograph like posted in my question here with still some peaks that standout a bit more. I think your spectrograph should also show many frequencys distributed all over the 2D plane, so I think your method to derive it is not quite right. Unfortunately I can't help you with matlab.

-