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

11.1. PROCESSING USING THE TRANSFORMATION

Lecture



Two-dimensional linear transformations can be defined as a series as

  11.1.  PROCESSING USING THE TRANSFORMATION . (11.1.1)

This ratio in vector form is

  11.1.  PROCESSING USING THE TRANSFORMATION . (11.1.2)

It will be shown below that such linear transformations can often be performed more efficiently if, instead of direct calculations using formulas (11.1.1) or (11.1.2), we use indirect methods using two-dimensional unitary transformations.

In fig. 11.1.1 the block diagram of the indirect method of calculation, called generalized linear filtering [1], is given. Array   11.1.  PROCESSING USING THE TRANSFORMATION describing the original image, is subjected here to a two-dimensional unitary transformation, which results in an array of transformation coefficients   11.1.  PROCESSING USING THE TRANSFORMATION . Then a linear combination of these coefficients is compiled, which is generally described by the formula

  11.1.  PROCESSING USING THE TRANSFORMATION , (11.1.3)

Where   11.1.  PROCESSING USING THE TRANSFORMATION - the core of the linear filtering transformation. Finally, an inverse unitary transformation is performed to obtain the processed image.   11.1.  PROCESSING USING THE TRANSFORMATION .

  11.1.  PROCESSING USING THE TRANSFORMATION

Fig. 11.1.1. The structure of the algorithms for direct processing (a) and generalized linear filtering (b).

Such a calculation method will be more efficient than direct calculation using formula (11.1.1) if there are fast unitary transformation algorithms, and the core   11.1.  PROCESSING USING THE TRANSFORMATION contains a large number of zero elements.

  11.1.  PROCESSING USING THE TRANSFORMATION

Fig. 11.1.2. The structure of the algorithms for direct processing (a) and generalized linear filtering (b) in the vector representation of images.

The process of generalized linear filtering can also be represented in a vector form (Fig. 11.1.2). To simplify the notation, we assume that   11.1.  PROCESSING USING THE TRANSFORMATION , but   11.1.  PROCESSING USING THE TRANSFORMATION . Then the generalized linear filtering can be described by the relations

  11.1.  PROCESSING USING THE TRANSFORMATION , (11.1.4a)

  11.1.  PROCESSING USING THE TRANSFORMATION , (11.1.4b)

  11.1.  PROCESSING USING THE TRANSFORMATION , (11.1.4b)

Where   11.1.  PROCESSING USING THE TRANSFORMATION - matrix of unitary size conversion   11.1.  PROCESSING USING THE TRANSFORMATION ,   11.1.  PROCESSING USING THE TRANSFORMATION - matrix operator linear size filtering   11.1.  PROCESSING USING THE TRANSFORMATION , but   11.1.  PROCESSING USING THE TRANSFORMATION - matrix inverse unitary size conversion   11.1.  PROCESSING USING THE TRANSFORMATION . As follows from relations (11.1.4), the vectors of the original and processed images are related by the equality

  11.1.  PROCESSING USING THE TRANSFORMATION . (11.1.5)

Equating the relations (11.1.2) and (11.1.5), we find the connection between the matrices   11.1.  PROCESSING USING THE TRANSFORMATION and   11.1.  PROCESSING USING THE TRANSFORMATION :

  11.1.  PROCESSING USING THE TRANSFORMATION , (11.1.6a)

  11.1.  PROCESSING USING THE TRANSFORMATION . (11.1.6b)

For direct processing to perform calculations using the formula (11.1.2), it is necessary to carry out   11.1.  PROCESSING USING THE TRANSFORMATION arithmetic action where   11.1.  PROCESSING USING THE TRANSFORMATION   11.1.  PROCESSING USING THE TRANSFORMATION characterizes the degree of filling the matrix   11.1.  PROCESSING USING THE TRANSFORMATION nonzero elements. With generalized linear filtering, the total number of arithmetic operations is:

Direct conversion:

  11.1.  PROCESSING USING THE TRANSFORMATION - with direct calculation;

  11.1.  PROCESSING USING THE TRANSFORMATION - when using fast conversion.

Linear filtering:

  11.1.  PROCESSING USING THE TRANSFORMATION multiplications.

Inverse transform:

  11.1.  PROCESSING USING THE TRANSFORMATION - with direct calculation;

  11.1.  PROCESSING USING THE TRANSFORMATION - when using fast conversion.

Here   11.1.  PROCESSING USING THE TRANSFORMATION   11.1.  PROCESSING USING THE TRANSFORMATION - matrix fill factor   11.1.  PROCESSING USING THE TRANSFORMATION nonzero elements. If a   11.1.  PROCESSING USING THE TRANSFORMATION and a direct computation of the unitary transformation is performed, it is obvious that generalized linear filtering is not as effective as direct processing. However, if fast algorithms are used, like the Fast Fourier Transform (FFT), generalized linear filtering will be more efficient than direct processing if the fill factor of the matrix is   11.1.  PROCESSING USING THE TRANSFORMATION satisfies inequality

  11.1.  PROCESSING USING THE TRANSFORMATION . (11.1.7)

In many cases, the matrix   11.1.  PROCESSING USING THE TRANSFORMATION it is sparse and inequality (11.1.7) holds. Generally speaking, unitary transformations often lead to decorrelation of matrix elements.   11.1.  PROCESSING USING THE TRANSFORMATION and matrix   11.1.  PROCESSING USING THE TRANSFORMATION turns out to be sparse. In addition, the matrix   11.1.  PROCESSING USING THE TRANSFORMATION It is often possible to destroy without introducing large errors if we replace its elements with small values ​​by zeros [1].

In the following sections, the structure of linear superposition, convolution, and pseudo-inversion operators is considered in order to determine the possibility of applying the method of generalized linear filtering to perform these operations.


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