Convolution

A two-dimensional discrete convolution is defined as

$\left(I*K\right)\left(x,y\right)=\sum_{-\infty}^{+\infty}\sum_{-\infty}^{+% \infty}I\left(u,v\right)K\left(x-u,y-v\right)\,,$

(1)

where is an image of size $m\times n$ , and is a convolution kernel of arbitrary size. Values outside the domains of and are set to zero.

Convolution can be a time demanding operation when implemented according to the definition in Equation (1). To speed up the algorithms, we use a method known as convolution with separable kernels. This allows one to calculate the convolution of the image with the kernel as

$F=I*K=\left(I*\boldsymbol{k}\right)*\boldsymbol{k}^{\top}$

(2)

if the kernel can be written as $K=\boldsymbol{k}\boldsymbol{k}^{\top}$ . Here the kernel is an $l\times l$ matrix and $\boldsymbol{k}=\left[k_{1},k_{2},\ldots,k_{l}\right]^{\top}$ . Using the method of separable kernels reduces the time complexity of the convolution from $O\left(mnl^{2}\right)$ to $O\left(mnl\right)$ .

Convolution

See also