3
$\begingroup$

I'm making a small program which gets the DFT of an image to get a general idea of the image's overall orientation. It does this by rotating a line in a radar sweep type pattern, keeping track of which angle has the highest sum of frequency amplitudes. (It actually only does $0-180^\circ$ though because the testing line is symmetrical across the origin)

Anyways, I was wondering, is there a less computationally expensive way to get frequency amplitudes of a 2D image than doing a 2D DFT?

I know that it is separable so can do better than the naive $\mathcal O(N^4)$ operation - I think it becomes $\mathcal O(N^3)$. I also know that the FFT can do a 1D DFT in $\mathcal O(N \log N)$ instead of $\mathcal O(N^2)$. Lastly, I know that it's massively parallelizable so could be (massively) multithreaded on either CPU or GPU.

Those things aside, are there any less computationally expensive ways to get frequency amplitudes of a 2D image than to do a full 2D DFT?

$\endgroup$
  • $\begingroup$ I assume you're referring to a 2D-FFT when asking for a faster candidate? Or do you mean an algorithm (other than DFT) which computes a specific set of frequencies that you need... $\endgroup$ – Fat32 Jul 31 '16 at 20:29
  • $\begingroup$ My usage case is 2d, yeah, but if there is something in 1d that can also be made to work in 2d, and was also faster in 2d vs 2d dft, then yeah, that's be useful too. $\endgroup$ – Alan Wolfe Jul 31 '16 at 20:46
  • $\begingroup$ Clever SleuthEye! Cynically, I think that is likely to be the best answer I get. Want to make it one and I'll accept it if that's true? $\endgroup$ – Alan Wolfe Aug 1 '16 at 1:56
2
$\begingroup$

Note that the computational complexity of a 2D FFT would be $\mathcal O(N^2\log N)$ instead of $\mathcal O(N^4)$ for the naive 2D DFT.

That said, since you mention that you want to obtain spectrum information along beams of a radar-like pattern, it sounds like you are really more interested in computing the 1D FFT of each such beam. In that case, for $M$ beams the computational complexity would be $\mathcal O(MN \log N)$.

As an illustration, lets process the following figure:

input image

from which we shall extract a set of $M$ beams with the following sample matlab code:

% Number of beams to extract
M = 200;

% Convert the input image "img" to polar coordinates
c = size(img)/2+1;
N = max(size(img));
angles = 2*pi*[0:M-1]/M;
radius = [0:floor(N/2)-1];
imgpolar = zeros(length(radius), length(angles));
for ii=1:length(radius)
  xi = min(max(1, floor(c(2)+radius(ii)*cos(angles))), size(img,2));
  yi = min(max(1, floor(c(1)-radius(ii)*sin(angles))), size(img,1));
  imgpolar(ii,:) = img(sub2ind(size(img), yi, xi));
end
% Compute the FFT for each beam angle
ImgFD = fft(imgpolar,[],1);

figure(1);
freqs = [0:size(ImgFD,1)-1]/size(ImgFD,1);
surf(angles, freqs, 10*log10(abs(ImgFD)+1), 'EdgeColor', 'None');
view(2);
colormap("gray");
xlabel('Beam angle (radians)');
ylabel('Normalized frequency');

to yield:

Beam spectrums

which can be collapsed to the sum of amplitudes as a function of the beam angles to give:

SumAmplitudes = sum(abs(ImgFD),1);
figure(2);
hold off; plot(angles, 10*log10(SumAmplitudes+1));
xlabel('beam angle (radians)');
ylabel('Sum of amplitudes (dB)');

Sum of amplitudes as a function of beam angle

As a side note, if you can use sum of squared amplitudes along those beam (instead of sum of amplitudes), then you can do it directly in spatial domain thanks to Parseval's theorem (which would bring the computational complexity down to $\mathcal O(MN)$, dominated by the conversion to polar coordinates). The equivalence (for the sum of squared amplitudes) can be seen using the following code:

% Compare the result of square amplitude summation in the frequency domain vs spatial domain
SumFD = sum(abs(ImgFD).^2,1)/size(ImgFD,1);
SumSD = sum(abs(imgpolar).^2,1);

figure(3);
hold off; plot(angles, 10*log10(SumFD+1), 'b');
hold on;  plot(angles, 10*log10(SumSD+1), 'r:');
xlabel('beam angle (radians)');
ylabel('Sum of squared amplitudes (dB)');
legend('Frequency domain', 'Spatial domain', "location", "southwest");

Notice the overlap of the curves computed in the spatial and frequency domains:

Sum of squared amplitudes as a function of beam angle

Update:

If you are in fact computing beams of a radar-like pattern in a 2D frequency plot as you seem to suggest in this other post, then you best bet comes back to doing a 2D FFT which would be order $\mathcal O(N^2 \log N)$. You could then perform the conversion to polar form for the sum of frequency coefficients which would add a small $\mathcal O(N^2)$, so the result is still dominated by the 2D FFT.

$\endgroup$
  • $\begingroup$ How can you use 2D-Parseval's theorem to obtain a partial sum of the line of magnitude squared frequency coefficients? As it yields the total sum, but you are referring to a line of frequencies ? May be you can provide an example octave/matlab code or a mathematical derivation of the statement ? $\endgroup$ – Fat32 Aug 1 '16 at 9:29
  • 2
    $\begingroup$ @Fat32 You'd use 1D-Parseval's theorem to obtain the total sum on each given spoke, ie. including all frequencies, based on the OP's "keeping track of which angle has the highest sum of frequency amplitudes" (except that to use Parseval's it would have to be "keeping track of which angle has the highest sum of squared frequency amplitudes"). This illustrates that if OP keeps track of a quantity that is essentially independent of frequency, then there is no need for DFT/FFT. $\endgroup$ – SleuthEye Aug 1 '16 at 17:52
  • $\begingroup$ Nice effort! I think I've misunderstood the OP. I thought he's sweeping a line in the 2D DFT coefficients, rather than in spatial image domain samples, (as your example demonstrated). So basicly what you say is to get, for each angle, a sweeping line of spatial samples from the image, and compute its 1D-DFT and compute the total DFT energy (or instead use Parseval to find the total energy directly without a DFT). So this information gives us the image orientation based on the assumption that an image should be dominated by lines parallel to alignment (vertical to sweeping line?) $\endgroup$ – Fat32 Aug 1 '16 at 19:43
  • $\begingroup$ I am sweeping a line in 2D DFT coefficients for what it's worth. If this solution doesn't work for that case, it seems like i could do it in the DFT image instead to get the same desired results, since the DFT loses positional information, but keeps directional frequency information? $\endgroup$ – Alan Wolfe Aug 3 '16 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.