1
$\begingroup$

I am doing an experiment, where I am trying to get the same results from correlating two matrices in the fourier domain and then scaling the data by some constant.

Method_1: Do FFT, Correlate the data, Do IFFT, Scale data

Method_2: Scale data, Do FFT, Correlate the data, Do IFFT

In other words, I am expecting that if I scale the data before I do correlation I should get the same results if I do correlation first, and then scale the data afterwards(provided that the scaling factor is the same). What's different in my case is that I am doing the correlation in the fourier domain instead of the time domain.

Below illustrates an example of scaling data before or after fft, which will yield the same results

data_1=[1,2,3,6;4,5,9,10;7,8,9,4;10,14,13,12];
%scaling constant
h=magic(4);

%METHOD_1

    %go to fourier domain
    method1_data1_fourier=fft2(data_1,8,8);             %zero padding

    %do ifft
    result1=ifft2(method1_data1_fourier,8,8);

    %scale
    result1=result1(1:4,1:4)./h;

%METHOD_2

    method2_data1 = data_1;

    %scale
    method2_data1 = method2_data1./h;

    %go to fourier domain
    method2_data1_fourier=fft2(method2_data1,8,8);              %zero padding

    %do ifft
    result2=ifft2(method2_data1_fourier,8,8);
    %result2=result2(1:4,1:4);

Below is a matlab example of what I am trying to do in C++ with 32 bit floating point precsion and fft length of 47x47 (padded with zeros to 94x94 before transform)

%correlating data_1 against data_2
data_1=[1,2,3,6;4,5,9,10;7,8,9,4;10,14,13,12];
data_2=[7,2;9,8;3,1];
%scaling constant
h=magic(4);

%METHOD_1

    %go to fourier domain
    method1_data1_fourier=fft2(data_1,8,8);             %zero padding
    method1_data2_fourier=fft2(data_2,8,8);

    %do correlation
    result1 = method1_data1_fourier.*conj(method1_data2_fourier);

    %do ifft
    result1=ifft2(result1,8,8);

    %scale
    result1(1:4,1:4)=result1(1:4,1:4)./h;

%METHOD_2

    method2_data1 = data_1;
    method2_data2 = data_2;

    %scale
    method2_data1 = method2_data1./h;


    %go to fourier domain
    method2_data1_fourier=fft2(method2_data1,8,8);              %zero padding
    method2_data2_fourier=fft2(method2_data2,8,8);

    %do correlation
    result2 = method2_data1_fourier.*conj(method2_data2_fourier);

    %do ifft
    result2=ifft2(result2,8,8);

Unfortunately I am not getting the results I expected to get, as in result1 and result2 do not match at all. Can anyone tell me what is wrong with the above method I am using? I believe it has something to do with the result be being shifted after the correlation in the fourier domain because indice (3,3) of result1 and result2 are the same, and the first matlab example works fine.

$\endgroup$
  • $\begingroup$ Why do you expect the results to match? Though you say $h$ is a constant, it is in fact another matrix (another signal). $\endgroup$ – Oliver Aug 13 '15 at 0:23
  • $\begingroup$ becase I am scaling both results in the time domain with the same signal; I see what you are saying, I had a typo see my edit $\endgroup$ – DSP_Student Aug 13 '15 at 0:40
  • $\begingroup$ The result should be the same if your computation has an infinite accuracy (double precision for not too long FFT). Since you give a "meaning less" program for me - I know DSP, not Matlab - It could help to know: Length of FFT, accuracy of data in (# of bits), accuracy of coefficients, accuracy of data out. What did you expected to get? $\endgroup$ – Moti Aug 13 '15 at 2:03
  • $\begingroup$ The actual code in C++ is using 32 bit precision for all the data (images in this case), and the fft size is 47x47 but it gets padded with zeros to 94x94 before the transformation. What I expected is that both methods would yield exactly the same or close to the same numbers within the time domain when looking at the upper left quadrant (the actual data, not where the artificial zeros were placed) $\endgroup$ – DSP_Student Aug 13 '15 at 2:28
  • $\begingroup$ It is not clear to me how you implement FFT (I assume 2D FFT) for 97 points. What is the scaling you use? Is it down or up? 32 bit precision is not good enough. Suggest to try it first with double precision and than move to integer scaling only after the scaling works with the double precision. $\endgroup$ – Moti Aug 14 '15 at 6:21
1
$\begingroup$

I figured out the problem. But there is one constraint

(1) The scaling factor for the entire matrix has to be the same number to do the process efficiently

So the way correlation is done, is multiplication and accumulation of two matrices, take for example the image matrix below correlated with the signal, and the result is from the valid part of the correlation, as in no zero padding is done

image        signal    scaling constant = 3
1  2  3      9 4
4  5  6      3 4

result[1] = (1*9+2*4+4*3+5*4)/3 = 16.3333
result[2] = (2*9+3*4+5*3+6*4)/3 = 23

If I want to scale before the correlation, I would have to scale the whole correlation window, like so

image              signal    scaling constant = 3
1/3  2/3  3/3      9 4
4/3  5/3  6/3      3 4

result[1] = ( (1/3)*9+(2/3)*4+(4/3)*3+(5/3)*4 ) / 3 = 16.3333
result[2] = ( (2/3)*9+(3/3)*4+(5/3)*3+(6/3)*4 ) / 3 = 23

After scaling like above, I could alternatively go to fourier domain with the image and the signal and do correlation there, do ifft, and I still get the same results.

image              signal    scaling constant = 3
1/3  2/3  3/3      9 4
4/3  5/3  6/3      3 4

image_fourier=fft2(image,4,6);   zero padding
signal_fourier=fft2(signal,4,6);   
result=ifft2(image_fourier.*conj(signal_fourier));

NOTE: above is matlab syntax

result[1] = 16.3333
result[2] = 23;

But this will not work if the scaling factor is different for result[1] and result[2].

$\endgroup$

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.