title: How to convolve an image with different gabor filters adjusted according to the local orientation and density using FFT?
body: <p>I'm currently working on a library to generate synthetic fingerprints using the <strong>SFinGe</strong> method (by Maltoni, Maio and Cappelli) link :<a href="http://biolab.csr.unibo.it/research.asp?organize=Activities&amp;select=&amp;selObj=12&amp;pathSubj=111%7C%7C12&amp;" rel="nofollow noreferrer">http://biolab.csr.unibo.it/research.asp?organize=Activities&amp;select=&amp;selObj=12&amp;pathSubj=111%7C%7C12&amp;</a></p>
  <p>One of the steps requires me to apply different gabor filters to an image, each pixel in the image have an orientation and a frequency associated, so the convolution is not done with one kernel over the entire image but the filter must change during the process depending on those attributes of the pixels, that way each pixel on the image is altered in a different way.</p>
  <p>If you apply the filters this way, and convolve the image several times(you also have to binarize the image after each convolution) you obtain this:</p>
  <p><img src="https://i.stack.imgur.com/GbXHs.png" alt="enter image description here" /></p>
  <p>A master fingerprint,  this image took about 20 seconds to be generated (which is way too slow, this is why I want to do it with FFT), since I had to perform 5 times the convolution to complete it (you start from a few random black points).</p>
  <p>My filters are 30x30, and the image is 275x400. There are a total of 36000 filters, one for each degree and density (density goes from 0 to 100). I'm planing on reducing the number of filters from 36000 to 9000 since I can cover all the angles with those. Also all the filters are pre-calculated and stored in a filter bank.</p>
  <p>This is the source code in C# of the gabor convolution implementation:</p>
  <p><strong>This two methods execute the convolution:</strong></p>
  <pre class="lang-cs prettyprint-override"><code>    /// &lt;summary&gt;
      /// Convolve the image with the different filters depending on the orientation and density of the pixel.
      /// &lt;/summary&gt;
      /// &lt;param name=&quot;image&quot;&gt;The image to be filtered.&lt;/param&gt;
      /// &lt;param name=&quot;directionalMap&quot;&gt;The directional map.&lt;/param&gt;
      /// &lt;param name=&quot;densityMap&quot;&gt;The density map.&lt;/param&gt;
      /// &lt;returns&gt;&lt;/returns&gt;
      public double[,] Filter(double[,] image, double[,] directionalMap, double[,] densityMap)
      {
          int       midX                          = FILTER_SIZE / 2;
          int       midY                          = FILTER_SIZE / 2;
          double[,] filteredImage                 = new double[image.GetLength(0), image.GetLength(1)];
          double[,] filteredImageWithValuesScaled = new double[image.GetLength(0), image.GetLength(1)];
          double[,] finalImage                    = new double[image.GetLength(0), image.GetLength(1)];
  
          for (int i = 0; i &lt; image.GetLength(0); i++)
              for (int j = 0; j &lt; image.GetLength(1); j++)
              {
  
                  double pixelValue = GetPixelConvolutionValue(image, this.filterBank[(int)Math.Floor((directionalMap[i, j] * 180 / Math.PI))][Math.Round(densityMap[i, j], 2)], i - midX, j - midY);
  
                  filteredImage[i, j] = pixelValue;
              }
  
          filteredImageWithValuesScaled = this.RescaleValues(filteredImage, 0.0, 255.0);
  
          return filteredImageWithValuesScaled;
      }
  </code></pre>
  <pre class="lang-cs prettyprint-override"><code>    /// &lt;summary&gt;
      /// Gets the pixel convolution value.
      /// &lt;/summary&gt;
      /// &lt;param name=&quot;image&quot;&gt;The image.&lt;/param&gt;
      /// &lt;param name=&quot;filter&quot;&gt;The filter.&lt;/param&gt;
      /// &lt;param name=&quot;sourceX&quot;&gt;The source X.&lt;/param&gt;
      /// &lt;param name=&quot;sourceY&quot;&gt;The source Y.&lt;/param&gt;
      /// &lt;returns&gt;&lt;/returns&gt;
      private double GetPixelConvolutionValue(double[,] image, double[,] filter, int sourceX, int sourceY)
      {
          double result      = 0.0;
          int    totalPixels = 0;
  
          for (int i = 0; i &lt; filter.GetLength(0); i++)
          {
              if(i + sourceX &lt; 0 || i + sourceX &gt;= image.GetLength(0))
                  continue;
  
              for (int j = 0; j &lt; filter.GetLength(1); j++)
              {
                  if(j + sourceY &lt; 0 || j + sourceY &gt;= image.GetLength(1))
                      continue;
  
                  double deltaResult = image[sourceX + i,sourceY + j] * filter[i, j];
                  result += deltaResult;
  
                  ++totalPixels;
              }
          }
  
          double filteredValue = result / totalPixels;
          return filteredValue;
      }
  </code></pre>
  <p><strong>This two methods generate the different gabor filters for the filter bank:</strong></p>
  <pre class="lang-cs prettyprint-override"><code>    /// &lt;summary&gt;
      /// Creates the gabor filter.
      /// &lt;/summary&gt;
      /// &lt;param name=&quot;size&quot;&gt;The size.&lt;/param&gt;
      /// &lt;param name=&quot;angle&quot;&gt;The angle.&lt;/param&gt;
      /// &lt;param name=&quot;wavelength&quot;&gt;The wavelength.&lt;/param&gt;
      /// &lt;param name=&quot;sigma&quot;&gt;The sigma.&lt;/param&gt;
      /// &lt;returns&gt;&lt;/returns&gt;
      public double[,] CreateGaborFilter(int size, double angle, double wavelength, double sigma)
      {
          double[,] filter    = new double[size, size];
          double    frequency = 7 + (100 - (wavelength * 100)) * 0.03;
  
          int windowSize = FILTER_SIZE/2;
  
          for (int y = 0; y &lt; size; ++y)
          {
              for (int x = 0; x &lt; size; ++x)
              {
                  int dy = -windowSize + y;
                  int dx = -windowSize + x;
  
                  filter[x, y] = GaborFilterValue(dy, dx, frequency, angle, 0, sigma, 0.80);
              }
          }
  
          return filter;
      }
  </code></pre>
  <pre class="lang-cs prettyprint-override"><code>    /// &lt;summary&gt;
      /// Gabor filter values generation.
      /// &lt;/summary&gt;
      /// &lt;param name=&quot;x&quot;&gt;The x.&lt;/param&gt;
      /// &lt;param name=&quot;y&quot;&gt;The y.&lt;/param&gt;
      /// &lt;param name=&quot;lambda&quot;&gt;The wavelength.&lt;/param&gt;
      /// &lt;param name=&quot;theta&quot;&gt;The orientation.&lt;/param&gt;
      /// &lt;param name=&quot;phi&quot;&gt;The phaseoffset.&lt;/param&gt;
      /// &lt;param name=&quot;sigma&quot;&gt;The gaussvar.&lt;/param&gt;
      /// &lt;param name=&quot;gamma&quot;&gt;The aspectratio.&lt;/param&gt;
      /// &lt;returns&gt;&lt;/returns&gt;
      double GaborFilterValue(int x, int y, double lambda, double theta, double phi, double sigma, double gamma)
      {
          double xx = x * Math.Cos(theta) + y * Math.Sin(theta);
          double yy = -x * Math.Sin(theta) + y * Math.Cos(theta);
  
          double envelopeVal = Math.Exp(-((xx * xx + gamma * gamma * yy * yy) / (2.0f * sigma * sigma)));
  
          double carrierVal = Math.Cos(2.0f * (float)Math.PI * xx / lambda + phi);
  
          double g = envelopeVal * carrierVal;
  
          return g;
      }
  </code></pre>
  <p>My goal is to reduce this time to under 1 second (There are several programs that do the exactly same thing in such time). So since the direct convolution approach is not working for me I decide to implement the Fast Fourier Transform Convolution, but the problem with this is that FFT applies the same kernel to the entire image at once, and I need to change the kernel per pixel, because each pixel must be altered depending on his attributes (density and orientation). In this post <a href="https://stackoverflow.com/questions/9003147/how-to-apply-gabor-wavelets-to-an-image">How to apply Gabor wavelets to an image?</a> <strong>reve-etrange</strong> explains how to apply different gabor filters to an image, but the thing is that the way he does it, is applying the different filters to the whole image and then sum the responses , and what I need is the responses from different pixels to the different filters.</p>
  <p>This is whats happening when I convolve one filter with the image (using FFT):</p>
  <p><img src="https://i.stack.imgur.com/qPSJ3.png" alt="enter image description here" /></p>
  <p>This was the filter used:</p>
  <p><img src="https://i.stack.imgur.com/OJ3TF.png" alt="enter image description here" /></p>
  <p>And this was the image it was convolved with:</p>
  <p><img src="https://i.stack.imgur.com/QeUuC.png" alt="enter image description here" /></p>
  <p><strong>This is the algorithm in C# of the FFT implementation:</strong></p>
  <pre class="lang-cs prettyprint-override"><code>    /// &lt;summary&gt;
      /// Convolve the image using FFT.
      /// &lt;/summary&gt;
      /// &lt;param name=&quot;image&quot;&gt;The image to be filtered.&lt;/param&gt;
      /// &lt;param name=&quot;directionalMap&quot;&gt;The directional map.&lt;/param&gt;
      /// &lt;param name=&quot;densityMap&quot;&gt;The density map.&lt;/param&gt;
      /// &lt;param name=&quot;FFT&quot;&gt;if set to &lt;c&gt;true&lt;/c&gt; [FFT].&lt;/param&gt;
      /// &lt;returns&gt;&lt;/returns&gt;
      public double[,] Filter(double[,] image, double[,] directionalMap, double[,] densityMap, bool FFT)
      {
          double[,] filter        = null;
          double[,] paddedFilter  = null;
          double[,] paddedImage   = null;
          double[,] croppedImage  = null;
          double[,] filteredImage = new double[image.GetLength(0), image.GetLength(1)];
          double[,] filteredImageWithValuesScaled = new double[image.GetLength(0), image.GetLength(1)];
          double[,] finalImage = new double[image.GetLength(0), image.GetLength(1)];
  
          filter = this.filterBank[70][0];
          paddedFilter = PadImage(filter, 512, 512, 0, 0); // Pad the filter to have a potency of 2 dimensions.
          paddedImage = PadImage(image, 512, 512, 0, 0);   // Pad the image to have a potency of 2 dimensions.
  
          FFT fftOne = new FFT(paddedImage);
          FFT fftTwo = new FFT(paddedFilter);
  
          fftOne.ForwardFFT();
          fftTwo.ForwardFFT();
  
          FFT result = fftOne * fftTwo;
  
          result.InverseFFT();
  
          filteredImage = result.GreyImage;
  
          filteredImageWithValuesScaled = this.RescaleValues(filteredImage, 0.0, 255.0);
  
          croppedImage = CropImage(filteredImageWithValuesScaled, image.GetLength(0), image.GetLength(1));
  
          return croppedImage;
      }
  </code></pre>
  <p>So what I'm asking is, how do you get the response from different pixels to different kernels with FFT? If this is not possible, is there a way to improve my direct convolution to make it at least 20 times faster?</p>
  <p>Also would it be possible to make one kernel using all the filters, so I can apply those to the whole image?</p>