Multidimensional discrete convolution: Difference between revisions

Revision as of 12:17, 1 September 2022

Revision as of 00:23, 19 April 2023

Line 141:

Thus, the resulting convolution can be effectively calculated by first performing the convolution operation on all of the rows of <math>x(n_1,n_2)</math>, and then on all of its columns. This approach can be further optimized by taking into account how memory is accessed within a computer processor.

A processor will load in the signal data needed for the given operation. For modern processors, data will be loaded from memory into the processors cache, which has faster access times than memory. The cache itself is partitioned into lines. When a cache line is loaded from memory, multiple data operands are loaded at once. Consider the optimized case where a row of signal data can fit entirely within the processor's cache. This particular processor would be able to access the data row-wise efficiently, but not column-wise since different data operands in the same column would lie on different cache lines.<ref>{{cite web|title=Introduction to Caches|url=http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/introCache.html|website=Computer Science University of Maryland|access-date=10 November 2015}}</ref> In order to take advantage of the way in which memory is accessed, it is more efficient to transpose the data set and then axisaccess it row-wise rather than attempt to access it column-wise. The algorithm then becomes:

# Separate the separable two-dimensional signal <math>h(n_1,n_2)</math> into two one-dimensional signals <math>h_1(n_1)</math> and <math>h_2(n_2)</math>

# Perform row-wise convolution on the horizontal components of the signal <math>x(n_1,n_2)</math> using <math>h_1(n_1)</math> to obtain <math>g(n_1,n_2)</math>