You get a bonus - 1 coin for daily activity. Now you have 1 coin

11.3. Convolution using FFT

Lecture



As already noted, for the convolution operator of finite arrays or the discretized convolution operator, the equivalent output vector can be found by choosing certain elements of the extended output cyclic convolution vector 11.3.  Convolution using FFT or its corresponding matrix 11.3.  Convolution using FFT . This situation in combination with equality (11.2.13) leads to a very efficient procedure for calculating convolution, consisting of the following steps:

1. Write the impulse response matrix in the upper left corner of the zero matrix. 11.3.  Convolution using FFT th order, and 11.3.  Convolution using FFT for the case of convolution of finite arrays and 11.3.  Convolution using FFT for discretized convolution. Perform a two-dimensional Fourier transform of the extended impulse response matrix.

11.3.  Convolution using FFT . (11.3.1)

2. Write the matrix of the original image in the upper left corner of the zero matrix 11.3.  Convolution using FFT -th order and perform a two-dimensional Fourier transform of the augmented matrix of the original image

11.3.  Convolution using FFT . (11.3.2)

3. Perform scalar multiplication

11.3.  Convolution using FFT , (11.3.3)

Where 11.3.  Convolution using FFT and 11.3.  Convolution using FFT .

4. Perform inverse Fourier transform

11.3.  Convolution using FFT . (11.3.4)

5. After selecting the desired elements to form the desired output matrix

11.3.  Convolution using FFT (11.3.5a)

or

11.3.  Convolution using FFT . (11.3.5b)

It is important that order 11.3.  Convolution using FFT extended matrices 11.3.  Convolution using FFT and 11.3.  Convolution using FFT satisfied the corresponding inequalities. With 11.3.  Convolution using FFT on the left and top edges of the output matrix there will be bands of erroneous elements having a width of 11.3.  Convolution using FFT the countdown (fig. 11.3.1, a, b). They are formed as a result of the so-called cyclic error associated with the incorrect application of the FFT method to calculate convolution. In addition, when performing convolution of finite arrays ( 11.3.  Convolution using FFT -convolution) will be lost elements of the output array, arranged by stripes in the right and lower parts of it. If we put 11.3.  Convolution using FFT then at 11.3.  Convolution using FFT - The output matrix will be completely filled with the correct readings. To calculate 11.3.  Convolution using FFT -convolution with 11.3.  Convolution using FFT , it is necessary to cut off the right and bottom edges of the original matrix. However, the result is that the elements of the output array, located on the top and on the left, will be erroneous.

11.3.  Convolution using FFT

Fig. 11.3.1. Cyclic errors. (Bottom and right sides of the matrix 11.3.  Convolution using FFT cut off.)

a - type filtering 11.3.  Convolution using FFT ; 11.3.  Convolution using FFT .

b - type filtering 11.3.  Convolution using FFT ; 11.3.  Convolution using FFT .

c - type filtering 11.3.  Convolution using FFT ; 11.3.  Convolution using FFT .

g - type filtering 11.3.  Convolution using FFT ; 11.3.  Convolution using FFT .

In signal processing, in many cases, it turns out that different input arrays are affected by operators with the same impulse response and, consequently, the first stage of the algorithm (calculation 11.3.  Convolution using FFT ) enough to run only once. When using the FFT algorithm for the cases of direct and inverse transformations, it is required to perform approximately 11.3.  Convolution using FFT arithmetic operations. Scalar multiplication is done for 11.3.  Convolution using FFT operations, i.e., everything is required 11.3.  Convolution using FFT operations. If the input matrix contains 11.3.  Convolution using FFT items, output 11.3.  Convolution using FFT and impulse response matrix 11.3.  Convolution using FFT elements, then to calculate the final convolution is required 11.3.  Convolution using FFT operations, and for discretized convolution 11.3.  Convolution using FFT operations. If size 11.3.  Convolution using FFT impulse response matrices are large enough compared to the size 11.3.  Convolution using FFT the original matrix, the convolution with the transformation turns out to be more efficient than the direct convolution, and the number of operations can be reduced ten times or more. In fig. 11.3.2 shows the graph of dependence 11.3.  Convolution using FFT from 11.3.  Convolution using FFT for the case when both methods for calculating the convolution of finite arrays (direct and with Fourier transform) have the same efficiency. The jaggedness of the graphics is due to the fact that with increasing 11.3.  Convolution using FFT parameter 11.3.  Convolution using FFT changes in steps, taking values ​​64, 128, 256, etc.

11.3.  Convolution using FFT

Fig. 11.3.2. Comparison of the effectiveness of two methods of obtaining the final convolution: direct and with the Fourier transform.

The calculation of the convolution with the Fourier transform requires a smaller number of operations than in the case of its direct calculation, if the length of the impulse response is large enough. However, if the processed image is also large, the relative efficiency of the method using the Fourier transform decreases. In addition, when calculating the Fourier transform of large matrices, difficulties arise in ensuring the accuracy of the calculations. Both problems can be resolved by resorting to block-based image filtering, when a large matrix is ​​subdivided into a series of overlapping blocks processed alternately [2, 7–9].

In fig. 11.3.3, and it is shown how the block containing the 11.3.  Convolution using FFT items. After convolving it with an impulse response consisting of 11.3.  Convolution using FFT elements, it turns out a block of size 11.3.  Convolution using FFT elements, which are placed in the upper left corner of the output matrix (Fig. 11.3.3, a). Next, from the processed matrix extract the next block size 11.3.  Convolution using FFT elements and from it receive the second block of the processed size image 11.3.  Convolution using FFT adjacent to the first. As shown in fig. 11.3.3, b, the second block of the original image must overlap with the first block in the strip width 11.3.  Convolution using FFT element. Then the processed blocks will dock without a gap. This process continues until all blocks adjacent to the top row of the matrix are processed. If the last block in this block line is incomplete, add zero elements to it. Next, remove the block located at the beginning of the second row and overlapping with the blocks of the first row in the strip width 11.3.  Convolution using FFT element. The process continues until all elements of the processed image have been determined.

11.3.  Convolution using FFT

Fig. 11.3.3. Placing blocks with block image filtering.

a - the first block; b - the second blocks in the row and column of blocks.

To obtain convolution with the Fourier transform is required

11.3.  Convolution using FFT (11.3.6)

operations. When block processing, when the block size is 11.3.  Convolution using FFT necessary

11.3.  Convolution using FFT (11.3.7)

operations where the number of blocks 11.3.  Convolution using FFT - fraction value rounded up 11.3.  Convolution using FFT . Hunt [9] determined how the optimal block size depends on the size of the matrices of the original image and the impulse response.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Digital image processing

Terms: Digital image processing