Convolution Math: 1D

The 1D convolution of an input signal x and a response signal g is defined as follows:

where y represents the output signal. The notation x ∗ g is commonly used to denote the convolution of signals (or functions) x and g.

In computer software, an array of sampled data points is frequently employed to represent the input, response, and output signals. A 1D discrete convolution can be calculated using the following equation:

where i = 0, 1, ⋯, N − 1 and M = floor(N_g/2). In the preceding equations, N denotes the number of elements in the input and output signals, and N_g symbolizes the number of elements in the response array. The ensuing discussions and source code examples in this chapter assume that N_g is an odd integer greater than or equal to three. If you examine the 1D discrete convolution equation carefully, you will notice that each element of the output signal array y is computed using a straightforward sum-of-products calculation that encompasses the input signal x and the response signal g. These types of calculations are easy to implement using FMA arithmetic as you have already seen.

In digital signal processing, many applications use smoothing operators to reduce the amount of noise present in a raw data signal. For example, the top plot of Figure 6-1 shows a raw data signal that contains a fair amount of noise. The bottom plot of Figure 6-1 shows the same signal following the application of a smoothing operator. In this example, the smoothing operator convolved the original raw signal with a set of discrete coefficients that approximate a low-pass (or Gaussian) filter. These coefficients correspond to the response signal array g that is included in the discrete 1D convolution equation. The response signal array is often called a convolution kernel or convolution mask. This book uses the term convolution kernel to avoid any potential confusion with SIMD masks.

The 1D discrete convolution equation can be implemented in source code using a couple of nested for-loops. During each outer loop iteration, the convolution kernel center point g[0] is superimposed over the current input signal array element x[i]. The inner for-loop calculates the intermediate products as shown in Figure 6-2. These intermediate products are then summed and saved to output signal array element y[i].

Convolution Math: 2D

The 2D convolution of input signal x, response signal g, and output signal y is defined as follows:

A 2D discrete convolution with a square dimensioned response signal can be calculated using the following equation:

where i = 0, 1, ⋯, N_rows − 1, j = 0, 1, ⋯, N_cols − 1, and M = floor(N_g/2). In the preceding equations, N_g symbolizes the height and width of the response signal (or convolution kernel) and is assumed to be an odd integer greater than or equal to three. A matrix of sampled data points is often utilized to represent the input, response, and output signals of a 2D discrete convolution. Figure 6-3 shows two images: the left image is the original grayscale image, while the right image was generated using a 2D discrete convolution kernel that performs low-pass filtering.

The 2D discrete convolution equation can be implemented in source code using four nested for-loops. During each iteration of the inner-most for-loop, the convolution kernel center point g[0][0] is superimposed over the current input signal array element x[i][j] as shown in Figure 6-4. This figure also shows the equations need to calculate y[i][j].

Direct implementation of the 2D discrete convolution equation is computationally expensive, even when using SIMD arithmetic. One reason for this is that the number of required arithmetic operations increases exponentially as the size of input signal gets larger. The computational costs of a 2D discrete convolution can be significantly reduced if the 2D convolution kernel is separable as shown in Figure 6-5. In this case, a 2D discrete convolution can be carried out using two independent 1D discrete convolutions.

When using a separable 2D convolution kernel, the original 2D discrete convolution equation transforms into the following:

Rearranging these terms yields the following equation:

Nonseparable Kernel

Listing 6-3 opens with the file Ch06_03.h. Near the top of this file is the definition of a structure named CD_2D . This structure holds the input image, output image, and convolution kernel matrices, which are implemented using the C++ STL class std::vector<float>. Structure CD_2D also includes image and kernel size information. Following the definition of structure CD_2D is an enum named KERNEL_ID. The function Init2D() in Ch06_03_misc.cpp employs a KERNEL_ID argument to select a low-pass filter kernel for the convolution functions. In file Ch06_03.cpp, there is a function named Convolve2D_F32() . This function initializes the CD_2D structures, invokes the convolution calculating functions, and saves the final images.

The file Ch06_03_fcpp.cpp begins with the definition of function Convolve2D_F32_Cpp(). This non-SIMD function uses standard C++ statements to perform a 2D discrete convolution using the specified source image and convolution kernel. Note that function Convolve2D_F32_Cpp() employs four nested for-loops to implement the 2D discrete convolution equation that was defined earlier in this chapter.

The SIMD counterpart of function Convolve2D_F32_Cpp() is named Convolve2D_F32_Iavx2(). The code layout of this function is somewhat analogous to the 1D discrete convolution functions you saw earlier in this chapter. In function Convolve2D_F32_Iavx2() , the index variable i in the outer-most for-loop specifies the current image row, and the index variable j in the second-level while-loop specifies the current image column. The first if statement in the while-loop verifies that there are num_simd_elements or more columns remaining in the current row. If true, the two inner for-loops calculate im_des[i][j:j+7] using the appropriate elements from the source image im_src and the convolution kernel im_ker. Note that these C++ code variables correspond to the symbols y, x, and g in the 2D discrete convolution equation.

The explicit equations required to calculate each im_des[i][j] are unwieldy to write out, especially for large convolution kernels. As an alternative, Figure 6-7 shows a table of input signal and convolution kernel (size 3 × 3) elements that are required to calculate each output signal element when using an __m256 C++ SIMD type and SIMD arithmetic. This figure uses the variable names of the 2D discrete convolution equation. To calculate y[i][j], for example, each input signal element in its row must be multiplied by the convolution kernel element that is shown at the top of each table column. These products are then summed to generate the final y[i][j]. Note that each column in the table contains consecutive input signal elements. This allows input signal element loading using the C++ SIMD intrinsic function _mm256_loadu_ps(). The function _mm256_set1_ps() broadcasts single elements from the convolution kernel, while _mm256_fmadd_ps() performs the required FMA SIMD arithmetic.

Separable Kernel

In Listing 6-4, the header file Ch06_04.h begins with the definition of a structure named CD_1Dx2 . This structure holds the data that is used by the convolution calculating functions. There are two noteworthy differences between the structure CD_1Dx2 and the structure CD_2D that was used in the previous example. First, structure CD_1Dx2 includes a third image buffer named m_ImTmp. This temporary buffer holds the result of the first 1D discrete convolution. The second notable change is that structure CD_1Dx2 contains two 1D convolution kernels, m_Kernel1Dx and m_Kernel1Dy, instead of a single 2D discrete convolution kernel. Not shown in Listing 6-4 are files Ch06_04_misc.cpp and Ch06_04.cpp. These files contain the functions that perform data structure initialization, image loading and saving, etc., and are very similar to the ones used in example Ch06_03. They are, of course, included in the software download package.

The first function in file Ch06_04_fcpp.cpp, Convolve1Dx2_F32_Cpp() , implements the dual 1D discrete convolution using standard C++ statements. Note that Convolve1Dx2_F32_Cpp() performs its convolutions using two separate code blocks. The first code block contains three nested for-loops that execute a 1D convolution using the x-axis of source image buffer im_src. The results of this convolution are saved to the temporary image buffer im_tmp. The second code block in function Convolve1Dx2_F32_Cpp() performs a 1D convolution using the y-axis of im_tmp. The result of this 1D convolution is saved to the output image buffer im_des.

In source code file Ch06_05.cpp, changing max_d = 1 to max_d = 0 yields only a small number of pixel value discrepancies.