The operation of convolving two objects and is linear, regardless of those objects’ dimensions. In the design of algorithms, this allows convolution to be written as *matrix-vector-product* (MVP)

(1)

where the matrices and are induced by the vectorial and , respectively. This turns out to be very handy, as it provides meanings for expressions like and similar, but the computation of the potentially large matrices and in explicit representations can be costly.

However, the computation of can be done in just using the *fast Fourier transform* (FFT). So, wouldn’t it be nice, if we were able to implement algorithms in a high-level, MVP-manner, but still exploiting FFT’s computational efficiency?

The Numpy library provides powerful classes for numerical linear algebra in Python. A small module, which adapts the interface of Numpy’s `ndarray`

class, but still evaluates expressions like (1) in just time, emerged as a side-product of my master thesis. In its current version, it supports one- and two-dimensional objects, but can easily be extended to also support 3D images, e.g. CT datasets.

## Capabilities

The core component of the module is the class `CnvMat`

. With and , it is meant to be instantiated in one of the following ways: Either through

- the
`cnvmat(f, sg, mode)`

function, that returns the matrix s.t. , - or through
`cnvmat_tp(f, sh, mode)`

, which returns the matrix .

The returned matrix’ column count must be specified explicitly using the second parameter, `sg`

or `sh`

respectively. The third parameter determines the shape of the convolution’s result, , that corresponds to the returned matrix’ row count. This parameter must be one of the following strings:

Uses`circ`

:*circular convolution*for , which implies . This option assumes that and repeat themselves beyond their boundaries.Keeps only the`valid`

:*valid part*of the circular convolution’s result, that is a smaller cutout, which we can compute without assumptions regarding the convolved objects’ continuation.Pads and with a zeros-margin and performs circular convolution.`full`

:

The matrix instance from class `CnvMat`

provides the following properties and methods:

Computes . The argument must either be -shaped, or a matrix with an -compatible row count.`.dot(g)`

:Tells , that is the shape of .`.sf`

:Tells , that is the shape of .`.sg`

:Tells , that is the shape of .`.sh`

:Tells the shape of matrix .`.shape`

:Accesses in time, where corresponds to the`.T`

:*cross-correlation*of and , and the`mode`

parameter transitions as follows:

mode of **circular convolution:**circular correlation circular correlation (not implemented) **valid convolution:**full correlation valid correlation **full convolution:**valid correlation valid correlation Computes and returns the`.toarray()`

:`ndarray`

object, which represents matrix explicitly.

## Showcase

## Background

With , and , the implementation assumes the following definitions for the corresponding matrices and . These definitions, quite similar to those used in [1], depend on the specified `mode`

parameter. We write and for the DFT matrix and its inverse, respectively:

**circular convolution:**(2)

Matrix pads its right-hand vector to the size of .

**valid convolution:**(3)

Matrix crops its right-hand vector to the size .

**full convolution:**(4)

Matrices and pad their right-hand vectors and to the size .

The padding and cropping matrices and are structured like that:

(5)

## Leave a Reply