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

11.2. SUPERPOSITION WITH TRANSFORMATION

Lecture



The superposition operation described in ch. 9, it is often possible to perform more efficiently if, instead of direct processing, processing is carried out using conversion. In fig. 11.2.1, a, b are diagrams for direct execution of the final superposition and discretized superposition. In fig. 11.2.1, g, d are presented the schemes of the superposition operation when the vector 11.2.  SUPERPOSITION WITH TRANSFORMATION subjected to unitary transformation, the result of which is multiplied by the matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION (for the operator of superposition of finite arrays) or matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION (for discretized superposition operator). The inverse transform gives the processed vector. According to fig. 11.2.1, a, d, in the case of applying the operator of superposition of finite arrays, the original and processed vectors are related by the following relations:

11.2.  SUPERPOSITION WITH TRANSFORMATION (11.2.1а)

and

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.1b)

Therefore, the matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION can be represented as a work

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.2а)

Similarly

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.2b)

To directly perform a superposition of finite arrays, it takes about 11.2.  SUPERPOSITION WITH TRANSFORMATION operations (here 11.2.  SUPERPOSITION WITH TRANSFORMATION - the order of the impulse response matrix). In this case, the fill factor of the matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION equals

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.3a)

A superposition of discretized arrays requires about 11.2.  SUPERPOSITION WITH TRANSFORMATION operations, and the fill factor of the matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION equals

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.3b)

In fig. 11.2.1, e shows a block diagram of cyclic superposition with transformation. In this case, the input vector 11.2.  SUPERPOSITION WITH TRANSFORMATION serves as the so-called extended input vector, obtained by placing the matrix of the original image 11.2.  SUPERPOSITION WITH TRANSFORMATION in the left corner of the square zero matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION th order and scan the resulting matrix in columns. Repeating the above reasoning, it can be shown that

11.2.  SUPERPOSITION WITH TRANSFORMATION (11.2.4a)

and therefore

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.4b)

11.2.  SUPERPOSITION WITH TRANSFORMATION

Fig. 11.2.1. Different types of superposition.

a is the final superposition; b - discretized integral superposition; c is a cyclic superposition; g is the final superposition with transformation; e - discretized integral superposition with transformation; e is a cyclic superposition with a transformation.

As noted in ch. 9, for a superposition of finite or discretized arrays, the equivalent output vector can be formed from 11.2.  SUPERPOSITION WITH TRANSFORMATION by choosing specific components of the latter. For superposition of finite arrays

11.2.  SUPERPOSITION WITH TRANSFORMATION , (11.2.5а)

and for superposition of discretized arrays

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.5b)

With the superposition of finite arrays, the matrix of the processed image is associated with the expanded image matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION in the following way:

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.6a)

When superposing discretized arrays, the matrix of the processed image is equal to

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.6b)

The number of arithmetic operations required to calculate the vector 11.2.  SUPERPOSITION WITH TRANSFORMATION by transformation processing, it can be found from the above formulas, if we put 11.2.  SUPERPOSITION WITH TRANSFORMATION :

Direct conversion: 11.2.  SUPERPOSITION WITH TRANSFORMATION .

Fast conversion: 11.2.  SUPERPOSITION WITH TRANSFORMATION .

If the matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION sparse then many of 11.2.  SUPERPOSITION WITH TRANSFORMATION multiplications required for filtering operations will not be performed.

From the foregoing, it is easy to conclude that in order to carry out a superposition efficiently, one should choose a transformation that meets two requirements: first, a fast algorithm must exist for it, and, second, the filter matrix of the transformed arrays must be sparse. As an example, we consider the convolution of finite arrays obtained using the Fourier transform [2, 3]. In accordance with Fig. 11.2.1 we set

11.2.  SUPERPOSITION WITH TRANSFORMATION , (11.2.7)

Where

11.2.  SUPERPOSITION WITH TRANSFORMATION

at 11.2.  SUPERPOSITION WITH TRANSFORMATION . Also, assume that the vector 11.2.  SUPERPOSITION WITH TRANSFORMATION size 11.2.  SUPERPOSITION WITH TRANSFORMATION represents the extended matrix of the spatially invariant impulse response described by formulas (9.3.2) with 11.2.  SUPERPOSITION WITH TRANSFORMATION . Fourier transform from 11.2.  SUPERPOSITION WITH TRANSFORMATION denote by

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.8)

The resulting transformation counts are placed on the main diagonal of the size matrix. 11.2.  SUPERPOSITION WITH TRANSFORMATION

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.9)

Using very cumbersome calculations, it can be shown that in the spectral space of the matrix, the convolution operator of finite arrays and the discretized convolution operator can be represented in the following form [4]:

11.2.  SUPERPOSITION WITH TRANSFORMATION (11.2.10)

at 11.2.  SUPERPOSITION WITH TRANSFORMATION and

11.2.  SUPERPOSITION WITH TRANSFORMATION (11.2.11)

at 11.2.  SUPERPOSITION WITH TRANSFORMATION where

11.2.  SUPERPOSITION WITH TRANSFORMATION , (11.2.12а)

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.12b)

Thus, both convolution operators in the spectral space contain a matrix of scalar weight factors 11.2.  SUPERPOSITION WITH TRANSFORMATION and interpolation matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION that allows you to associate an input size vector 11.2.  SUPERPOSITION WITH TRANSFORMATION with output size vector 11.2.  SUPERPOSITION WITH TRANSFORMATION . As a rule, the interpolation matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION contains a lot of zero elements, and therefore convolution using the transformation is performed very effectively.

We now consider cyclic convolution performed with the transition to the spectral space. Using arguments similar to the above, it was shown [4] that the filter operator in this case reduces to a scalar operator

11.2.  SUPERPOSITION WITH TRANSFORMATION . (11.2.13)

Thus, as can be seen from equalities (11.2.12) and (11.2.13), when convolving in the space of Fourier spectra, the filter matrix can be expressed in a compact closed form. For other unitary transformations, no such expressions were found.

The efficiency of the convolution calculation using the Fourier transform is determined by the fact that the convolution operator 11.2.  SUPERPOSITION WITH TRANSFORMATION has a cyclic matrix, and the corresponding filter matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION is diagonal. As can be seen from relations (11.1.6), the basic vectors of the Fourier transform are actually the eigenvectors of the matrix 11.2.  SUPERPOSITION WITH TRANSFORMATION [five]. This is not so for a general superposition operation, as well as for a convolution operation using other unitary transformations. However, in many cases the filter matrices 11.2.  SUPERPOSITION WITH TRANSFORMATION and 11.2.  SUPERPOSITION WITH TRANSFORMATION contain relatively few non-zero elements, and conversion processing reduces the amount of computation.

In fig. 11.2.2 shows the form of spectra matrices for the three types of the convolution operator for a one-dimensional input vector with a Gaussian impulse response using Fourier and Hadamard transforms [6]. As expected, the transformation coefficient matrices turned out to be significantly more sparse than the original matrices. In addition, it is easy to see that for cyclic convolution with the Fourier transform, the filter matrix is ​​diagonal. In fig. 11.2.3 shows the structure of the matrices of the three convolution operators of two-dimensional signals [4].

11.2.  SUPERPOSITION WITH TRANSFORMATION

Fig. 11.2.2. Matrices of convolution operators of one-dimensional signals using Fourier and Hadamard transforms.

a is the final convolution; b - discretized convolution; c is a cyclic convolution.

11.2.  SUPERPOSITION WITH TRANSFORMATION

Fig. 11.2.3. Matrices of convolution operators for two-dimensional signals using Fourier transform.

Final convolution: a - directly executed; b - with conversion. Discretized integral convolution: c - directly executed; d - with conversion.

Cyclic convolution: d - directly executed; e - with conversion.


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