# 2d dft of a scattered signal

I want to take the DFT of the data shown in the image. Note: my data consists of $(x,y,z)$ values for which I have shown $(x,y)$ in the image (i.e. their location). '$z$' is the amplitude of the data points which I haven't shown. I have some questions:

1. Is 2d DFT for this data the same as taking multiple 1d DFT for all the rows? (Should I venture into the world of 2d Fourier to analyze this data of mine or is 1d analysis sufficient?)

2. As it can be seen ,my data is highly scattered, do I need to interpolate it before applying DFT? If yes, which interpolation would you suggest ? Or, can I use a non uniform DFT ?

I am a newbie to DSP and I understand my questions are elementary. So if you feel it does not need to be answered here, you may direct me to a web-page or a link to a question-answer/discussion which addresses this issue.

Also no data does not exist between the blue dots i.e the blue dots represents the points where I have the height (amplitude) value and the in between 'white' points I do not have the height (amplitude).

• I am trying to model the surface of a material (building material to be precise, I am a civil engineer). About the data, the $z$ here represents 'height of the material's surface from an assumed datum' at any given $(x,y)$. I want to study(infer) the shape of the surface of the material. Why do I want to use DFT, by using DFT on two different surfaces (the above image is of one particular surface) and obtaining the spectrum I want to study how their surface shapes are different. No data does not exist between the points. Dec 30, 2016 at 5:19
• @Laurent I have added these details to the question. Right now I am in a preliminary stage , so there may be many errors in my approach. Right now I just want to understand what pre processing of my data needs to be done so that I can apply dft to it? And what kind of dft sjould be applied - 2d or 1d ? Interploate the data or use non uniform dft? These are some questions that I am struggling with. Dec 30, 2016 at 6:07
• Your question has beeen answered. Do not hesitate to vote for the useful ones and accept the most suitable Feb 9, 2017 at 17:26

Without knowing what you want to get, I will assume you are interested in periodicities of the elevated dot patterns. They can give you access to roughness measures, texture attributes.

Visually, 2D periodicities are apparent from your data point $(x,y)$ locations. At different scales though: beside a potential periodic base pattern, little streaks of 5 to 10 dots, closely spaced, can be observed.

The situation will depend on how to want to treat the data. If you treat it as an image, putting white values (or whatever) between dots, you are already doing interpolation. In that case, a true 2D DFT would take a separable 1D DFT on both rows AND columns. So, you definitely need to venture into 2D, unless you will only see horizontal frequencies; look at the last line of your image: there are 8 or 9 periods only, you are missing out the small slope.

I cannot propose data interpolation without knowledge of the underlying process, and the $z$ value. My take is that you ought to try with true 2D non-uniform DFT first. Interpolation causes smearing.

In recent question (what is $1/f$ property of the visual world?), Frequency Synthesis of Landscapes was evoked, and a parametric spectrum modeling (eg decay in $1/f^p$) can provide you with parameters to compare different surfaces. For some spectral shapes, this can be naturally done in a Fourier domain. There should be related techniques under the field of "Surface roughness analysis".

My basic thinking for a procedure is the following: your different scans of surfaces may have different $(x,y)$ locations, and sizes. So it is not easy to compare their properties directly in the space domain, unless you regrid, interpolate, etc. which can cause harm. Non regular Fourier transforms can regularize the outcomes: from any two scattered grids, you can cast Fourier coefficients to the same 2D regular frequency grid, and infer global parameters from them: peaks, moments, parametric fits, etc.

So you can check NUFFT (NFFT, USFFT) Software and the related keywords:

algorithms have been developed to overcome this limitation - generally referred to as non-uniform FFTs (NUFFT), non-equispaced FFTs (NFFT) or unequally-spaced FFTs (USFFT)

with a related paper: Accelerating the Nonuniform Fast Fourier Transform, by Leslie Greengard and June-Yub Lee. Apparently there are Matlab versions too: NUFFT, NFFT, USFFT.

If this is not enough, you can try (lifting) wavelet transforms on 2D irregular grids, to catch the proper scale and local details. You could mesh it with MeshLab. And then use lifting wavelets for a multiresolution vision.