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.
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
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,
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:
circ: Uses circular convolution for , which implies . This option assumes that and repeat themselves beyond their boundaries.
valid: Keeps only the valid part of the circular convolution’s result, that is a smaller cutout, which we can compute without assumptions regarding the convolved objects’ continuation.
full: Pads and with a zeros-margin and performs circular convolution.
The matrix instance from class
CnvMat provides the following properties and methods:
.dot(g): Computes . The argument must either be -shaped, or a matrix with an -compatible row count.
.sf: Tells , that is the shape of .
.sg: Tells , that is the shape of .
.sh: Tells , that is the shape of .
.shape: Tells the shape of matrix .
.T: Accesses in time, where corresponds to the cross-correlation of and , and the
modeparameter 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
.toarray(): Computes and returns the
ndarrayobject, which represents matrix explicitly.
With , and , the implementation assumes the following definitions for the corresponding matrices and . These definitions, quite similar to those used in , depend on the specified
mode parameter. We write and for the DFT matrix and its inverse, respectively:
- circular convolution:
Matrix pads its right-hand vector to the size of .
- valid convolution:
Matrix crops its right-hand vector to the size .
- full convolution:
Matrices and pad their right-hand vectors and to the size .