title: Replicate MATLAB's `conv2()` Using Fourier Domain Convolution
body: <p>I would like to take two images and convolve them together in Matlab using the 2D FFT without recourse to the <code>conv2</code> function. However, I am uncertain with respect to how the matrices should be properly padded and prepared for the convolution.  </p>
  
  <p>The mathematical operation is the following:</p>
  
  <p><strong>A</strong> * <strong>B</strong> = <strong>C</strong> </p>
  
  <p>In the above, * is the convolution operator (<a href="http://en.wikipedia.org/wiki/Convolution" rel="nofollow noreferrer">Wikipedia link</a>).</p>
  
  <p>The following Matlab program shows the difference between padding and not padding the matrices.  I suspect that not padding the matrices results in a circular convolution, <em>but I would like to perform a linear convolution without aliasing</em>.</p>
  
  <p>If I do pad the two matrices, then how do I truncate the output of the convolution so that <strong>C</strong> is the same size as <strong>A</strong> and <strong>B</strong>?</p>
  
  <pre><code>A = rgb2gray(im2double(imread('1.png'))); % input A
  B = rgb2gray(im2double(imread('2.png'))); % kernel B
  
  figure;
  imagesc(A); colormap gray;
  title ('A')
  
  figure;
  imagesc(B); colormap gray;
  title ('B')
  
  [m,n] = size(A);
  mm = 2*m - 1;
  nn = 2*n - 1;
  
  C = (ifft2(fft2(A,mm,nn).* fft2(B,mm,nn)));
  
  figure;
  imagesc(C); colormap gray;
  title ('C with padding')
  
  C0 = (ifft2(fft2(A).* fft2(B)));
  
  figure;
  imagesc(C0); colormap gray;
  title ('C without padding')
  </code></pre>
  
  <p>Here is the output of the program:</p>
  
  <p><img src="https://i.stack.imgur.com/Z5hZu.png" alt="A">
  <img src="https://i.stack.imgur.com/5PZlG.png" alt="B">
  <img src="https://i.stack.imgur.com/HQcbX.png" alt="C">
  <img src="https://i.stack.imgur.com/Eb9dZ.png" alt="C0"></p>