# convnFast

## PURPOSE

Fast convolution, replacement for both conv2 and convn.

## SYNOPSIS

function C = convnFast( A, B, shape )

## DESCRIPTION

     Fast convolution, replacement for both conv2 and convn.

     See conv2 or convn for more information on convolution in general.

     This works as a replacement for both conv2 and convn.  Basically,
     performs convolution in either the frequency or spatial domain, depending
     on which it thinks will be faster (see below). In general, if A is much
     bigger then B then spatial convolution will be faster, but if B is of
     similar size to A and both are fairly big (such as in the case of
     correlation), convolution as multiplication in the frequency domain will
     tend to be faster.

     The shape flag can take on 1 additional value which is 'smooth'.  This
     flag is intended for use with smoothing kernels.  The returned matrix C
     is the same size as A with boundary effects handled in a special manner.
     That is instead of A being zero padded before being convolved with B;
     near the boundaries a cropped version of the matrix B is used, and the
     results is scaled by the fraction of the weight found in  the cropped
     version of B.  In this case each dimension of B must be odd, and all
     elements of B must be positive.  There are other restrictions on when
     this flag can be used, and in general it is only useful for smoothing
     kernels.  For 2D filtering it does not have much overhead, for 3D it has
     more and for higher dimensions much much more.

     For optimal performance some timing constants must be set to choose
     between doing convolution in the spatial and frequency domains, for more
     info see timeConv below.

     USAGE
      C = convnFast( A, B, [shape] )

     INPUTS
      A       - d dimensional input matrix
      B       - d dimensional matrix to convolve with A
      shape   - ['full'] 'valid', 'full', 'same', or 'smooth'

     OUTPUTS
      C       - result of convolution

     EXAMPLE

     See also CONV2, CONVN

     Piotr's Image&Video Toolbox      Version 2.0
     Copyright 2008 Piotr Dollar.  [pdollar-at-caltech.edu]
     Please email me if you find bugs, or have suggestions or questions!
     Licensed under the Lesser GPL [see external/lgpl.txt]

## CROSS-REFERENCE INFORMATION

This function calls:

- convnFast Fast convolution, replacement for both conv2 and convn.
- arrayToDims Pads or crops I appropriately so that size(IC)==dims.
- ind2sub2 Improved version of ind2sub.

This function is called by:

- convnFast Fast convolution, replacement for both conv2 and convn.
- gaussSmooth Applies Gaussian smoothing to a (multidimensional) image.
- histcImWin Calculates local histograms at every point in an image I.
- normxcorrn Normalized n-dimensional cross-correlation.
- xcorrn n-dimensional cross-correlation. Generalized version of xcorr2.
- xeucn n-dimensional euclidean distance between each window in A and template T.