RU2540781C1 - Method of direct and inverse fast two-dimensional wavelet-transform - Google Patents

Abstract

FIELD: physics, computer technology.

SUBSTANCE: invention relates to image processing systems. The method of direct and inverse fast two-dimensional wavelet transform is offered. At direct transform the input sequences of values, at processing of both lines and columns, are divided into two parts with identical length. Each second of such parts is processed by an additional pair of high-frequency and low-frequency filters, in which the coefficients used for forming of set of filters, are selected in the inverse order in comparison with such coefficients for the filters, processing the first part of sequences. Then incomplete sampling for all additional groups of obtained values is performed. In inverse transform the additional groups of coefficients, uniquely determined by direct transform, are processed by condensing sampling, further convolution with filters, those of which processing the second parts of sequences, are formed on the basis of the set of coefficients selected in the inverse order in comparison with such coefficients for filters, processing the first parts of sequences. After summation the integrated sequences, with high precision coinciding with such sequences separated at direct transform, are formed, and it is performed for processing of both lines and columns.

EFFECT: improvement of quality of recovered data.

4 dwg

Description

The invention relates to the processing of two-dimensional signals, namely, to the field of performing discrete wavelet transform and can be used in image processing systems, their compression, technical vision.

Currently, wavelet transform is widely used in signal and image processing algorithms, which translates the input data into a form that is more convenient for a number of processing algorithms.

When performing the wavelet transform, the signal is decomposed into a number of frequency bands, for which a set of low- and high-frequency filters is set to perform signal decomposition. After performing the required actions on the coefficients of the converted data, the signal can be restored with varying degrees of accuracy. When performing a quick conversion, incomplete thinning and thickening samples are used [1, 2]. For images and two-dimensional signals, “separable convolution” can be used, which are the basis of separable filters that allow processing a multidimensional signal based on sequential one-dimensional filtering [1, 2].

The prior art method and device for wavelet transform (see patent for invention US 6,591,017 B, published July 8, 2003) and a data compression method that uses wavelet transform (see patent application US 2010/0232723 A1).

The disadvantage in them is that after the wavelet transform and subsequent rotation, the image cannot be restored according to the original algorithm without reverse rotation, i.e. these solutions have low resistance to rotation of the converted image.

The closest in technical essence to the claimed invention is a direct and inverse fast two-dimensional wavelet transform. A method for performing direct and inverse fast two-dimensional wavelet transform, based on convolution of input data on rows with low-frequency and high-frequency filters, the outputs of which are incompletely sampled, resulting in low-frequency and high-frequency values of one-dimensional transformation, then convolution with low-pass and high-pass filters, followed by incomplete sampling, and the described sequence can be applied to low-frequency coefficients l actions to perform the next level of direct conversion, and the inverse wavelet transform is performed in columns based on a thickening sample applied to the low-frequency and high-frequency components obtained as a result of the direct wavelet transform, followed by convolution with low-pass and high-pass filters and summation, then line processing based on a thickening sample applied to the obtained low-frequency and high-frequency components, followed by convolution from low-frequency high-frequency filters and summation, while the result can be used with the corresponding high-frequency components to perform the next level of the inverse wavelet transform (see Malla S. Wavelets in signal processing / S. Mala; Per. from English - M .: Mir, 2005. - S.332-336), taken as a prototype.

The disadvantage of this method is that there is no invariance to the rotation of the wavelet transform, which leads to a significant decrease in the quality of image recovery when the matrix is rotated, the obtained coefficients after performing the direct wavelet transform. This is because four frequency ranges are used here when performing the wavelet transform, and the low-frequency range of the coefficients is located in one of the angles of the resulting signal decomposition.

The problem to which the claimed invention is directed, is to ensure invariance to the rotation of the wavelet transform.

The technical result achieved by the implementation of the claimed invention consists in increasing the stability of the wavelet transform to rotation and, accordingly, improving the quality of image recovery after rotation at fixed angles.

Other technical results provided by the invention are two additional technical results. The first additional technical result provided by the given set of features is to increase the stability of the wavelet transform to mirror the image relative to the vertical and horizontal axes, and, consequently, to improve the quality of image recovery after performing direct fast wavelet transform with subsequent mirror reflections.

The second additional technical result provided by the given set of features is the preservation of not only absolute values, the results of applying the direct fast wavelet transform for the image rotated by a fixed angle and / or the mirror image, but also the sign of these coefficients, which can reduce the number of operations during processing images using this method, as well as the complexity of the hardware that implements them.

The specified technical result is achieved by the fact that in the method of performing direct and inverse fast two-dimensional wavelet transform, based on the convolution of the input data on the lines with low-frequency and high-frequency filters, the outputs of which are incomplete sampling, resulting in low-frequency and high-frequency values of one-dimensional conversion, then convolution with low-pass and high-pass filters is applied to them in columns, followed by incomplete sampling, and to low-pass coefficients The described sequence of actions can be applied to the participants to perform the next level of direct conversion, and the inverse wavelet transform is performed in columns based on the thickening sample applied to the low-frequency and high-frequency components obtained as a result of the direct wavelet transform, followed by convolution with low-pass and high-pass filters and summing, then row-based processing is performed based on the thickening sample applied to the resulting low-frequency and high-frequency component with subsequent convolution with low-pass and high-pass filters and summation, while the result can be used with the corresponding high-frequency components to perform the next level of the inverse wavelet transform according to the invention for direct conversion of input sequences of values, both when processing rows and columns are divided into two parts of the same length, with each second of these parts being processed by an additional pair of high-frequency and low frequency filters, in which the coefficients used to form the set of filters are selected in the opposite order as compared to those for the filters processing the first parts of the sequences, with further incomplete sampling for all additional groups of obtained values, and in the inverse transformation, additional groups of coefficients are uniquely determined by direct conversion are subjected to a thickening sampling, further convolution with filters, those of which process the second parts afterwards odds are formed on the basis of a combination of coefficients that are selected in the reverse order compared to such coefficients for filters that process the first parts of sequences, and after summing, combined sequences are formed that coincide with high accuracy with such sequences that are separated by direct conversion, and this is done as for processing rows and columns.

The invention is illustrated by drawings, which depict:

figure 1 is a block diagram of a block for performing direct fast wavelet transform;

figure 2 is a structural diagram of a block for performing inverse fast wavelet transform;

figure 3 - the formation of low-frequency and high-frequency groups of coefficients when performing a direct wavelet transform of the image corresponding to different frequency ranges (a - conversion by rows; b - subsequent conversion by columns);

figure 4 - the results of the direct fast wavelet transform of the first level (a - the initial test image; b - the conversion in rows; c - the subsequent transformation in columns; d - the difference between the results obtained by the method described in the prototype, and the proposed way).

The invention consists in the following.

Fast wavelet transform is an efficient method for implementing discrete wavelet transform computations [1]. It can be represented as the product of a block matrix by a column vector [3]:

$$\left[\frac{A_j}{D_j}\right]a_j=\left[\frac{a_{j+\mathrm{one}}}{d_{j+\mathrm{one}}}\right],\left(\mathrm{one}\right)$$

where j is the conversion level;

A _j , D _j - blocks of the transformation matrix;

a _j , a _{j + 1} and d _{j + 1} are column vectors of approximating and detailing transformation coefficients.

и высокочастотного $$\left(\overline{g}\right)$$

фильтров [1, 3].The block transformation matrix is formed using the values of the scaling (φ) and wavelet functions (ψ), which are the basis for the formation of the low-frequency $$\left(\overline{h}\right)$$

and high frequency $$\left(\overline{g}\right)$$

filters [1, 3].

To solve the claimed technical problem, the number of frequency ranges is increased by making the following fundamental changes:

- Input data at each conversion level is divided into two equal parts. The first part contains the first half of the input data values, and the second part contains the second half. Depending on the scaling and wavelet functions used, overlapping by values in the center of the input sequence is possible:

$$a_j=\left[\frac{a{\mathrm{one}}_j}{a{2}_j}\right],\left(2\right)$$

where a1 _j and a2 _j are the first and second parts of the input sequence of the corresponding conversion level.

- To form the transformation matrix, pairs of high-pass and low-pass filters are used, the coefficients of which are related by the following relationships:

$$\begin{array}{l}\overline{h\mathrm{one}}[\mathrm{one}:n]=\overline{\mathrm{<figure-callout\; id="2"\; label="h"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">h</figure-callout>}2}[n:\mathrm{one}]\\ \overline{g\mathrm{one}}[\mathrm{one}:n]=\overline{\mathrm{<figure-callout\; id="2"\; label="g"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">g</figure-callout>}2}[n:\mathrm{one}],\left(3\right)\end{array}$$

, $$\overline{g1}$$

и $$\overline{h2}$$

, $$\overline{g2}$$

- низкочастотный и высокочастотный фильтры для обработки первой и второй частей входных последовательностей соответственно.Where $$\overline{h\mathrm{one}}$$

, $$\overline{g\mathrm{one}}$$

and $$\overline{\mathrm{<figure-callout\; id="2"\; label="h"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">h</figure-callout>}2}$$

, $$\overline{\mathrm{<figure-callout\; id="2"\; label="g"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">g</figure-callout>}2}$$

- low-pass and high-pass filters for processing the first and second parts of the input sequences, respectively.

Expression (3) shows that in the formation of the first and second pairs of filters, coefficients with direct and reverse order are used.

As a result of using these filters, two low-frequency and high-frequency groups of conversion coefficients belonging to different frequency ranges are created, and expression (1) taking into account (2) and (3) takes the following form:

$$\left[\begin{array}{l}\frac{D{\mathrm{one}}_j}{A{\mathrm{one}}_j}\\ \frac{A{2}_j}{D{2}_j}\end{array}\right]\left[\frac{a{\mathrm{one}}_j}{a{2}_j}\right]=\left[\begin{array}{c}\frac{d{\mathrm{one}}_{j+\mathrm{one}}}{a{\mathrm{one}}_{j+\mathrm{one}}}\\ \frac{a{2}_{j+\mathrm{one}}}{d{2}_{j+\mathrm{one}}}\end{array}\right],\left(\mathrm{four}\right)$$

where D1 _j , A1 _j , A2 _j and D2 _j are parts of a block transform matrix, each 2 ^{n / 2} × 2 ⁿ in size;

a1 _{j + 1} , a2 _{j + 1} and d1 _{j + 1} d2 _{j + 1} - approximating and detailing parts of the column vector of the direct transformation, each 2 ^n-2 in length.

In accordance with (2), (4) with the replacement of the input data, data belonging to different frequency ranges can be sequentially processed.

For the inverse wavelet transform, pairs of low-pass and high-pass filters can be used in accordance with the following expression:

$$\begin{array}{l}\text{hl [l: n]}=\text{h2 [n: l]}\\ \text{gl [l: n]}=\text{g2 [n: l]}\text{.}\left(\text{5}\right)\end{array}$$

On their basis, a block matrix of the inverse transformation is formed. Using orthogonal functions [1, 2] when forming filters, the expression can be used:

$$a_j=\left[\frac{a{\mathrm{one}}_j}{a{2}_j}\right]={\left[\begin{array}{l}\frac{D{\mathrm{one}}_j}{A{\mathrm{one}}_j}\\ \frac{A{2}_j}{D{2}_j}\end{array}\right]}^{-\mathrm{one}}\left[\begin{array}{c}\frac{d{\mathrm{one}}_{j+\mathrm{one}}}{a{\mathrm{one}}_{j+\mathrm{one}}}\\ \frac{a{2}_{j+\mathrm{one}}}{d{2}_{j+\mathrm{one}}}\end{array}\right]\left(6\right)$$

With the replacement of the input data in (6), data belonging to different frequency ranges can be sequentially processed.

, $$\overline{g1}$$

и $$\overline{h2}$$

, $$\overline{g2}$$

с реализацией неполной выборки на выходе 12. На выходах 1, 4 и 2, 3 блоков фильтров формируются прореженные высокочастотные и низкочастотные значения обработанных данных соответственно. При этом блок фильтров F1 производит обработку по строкам, а блоки фильтров F2-F5 производят обработку по столбцам.In accordance with the claimed method, direct fast two-dimensional wavelet transform is performed using 5 identical filter blocks F1-F5 (Fig. 1), each of which contains a switch - Sw, which performs the functions of demultiplexing, two pairs of low-pass and high-pass filters - $$\overline{h\mathrm{one}}$$

, $$\overline{g\mathrm{one}}$$

and $$\overline{\mathrm{<figure-callout\; id="2"\; label="h"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">h</figure-callout>}2}$$

, $$\overline{\mathrm{<figure-callout\; id="2"\; label="g"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">g</figure-callout>}2}$$

with the implementation of incomplete sampling at output 12. At outputs 1, 4, and 2, 3 of the filter blocks, thinned high-frequency and low-frequency values of the processed data are formed, respectively. At the same time, filter block F1 performs row-by-row processing, and filter blocks F2-F5 perform column-wise processing.

The input of filter block F1 receives input data a _j in rows.

и $$\overline{g1}$$

. После свертки с данными фильтрами данные прореживаются через один отсчет ↓2 и на выходах 1 и 2 блока фильтров F1 формируются высокочастотная d1_j+1 и низкочастотная a1_j+1 составляющие соответственно.The first part of each line through the output 1 of the switch Sw of the filter block F1 is fed to the low-pass and low-pass filters $$\overline{h\mathrm{one}}$$

and $$\overline{g\mathrm{one}}$$

. After convolution with these filters, the data is thinned through one sample ↓ 2 and at the outputs 1 and 2 of the filter block F1, the high-frequency d1 _{j + 1} and low-frequency a1 _{j + 1} components, respectively, are formed.

и $$\overline{g2}$$

. После свертки с данными фильтрами данные прореживаются через один отсчет ↓2 и на выходах 3 и 4 блока фильтров F1 формируются низкочастотная a2_j+1 и высокочастотная d2_j+1 составляющие соответственно. Распределение по частотам результатов одномерного прямого быстрого вейвлет-преобразования представлено на фиг.3,а.The second part of each line through the output 2 of the switch Sw of the filter block F1 is fed to the low-pass and low-pass filters $$\stackrel{}{h}$$$$\overline{2}$$

and $$\overline{\mathrm{<figure-callout\; id="2"\; label="g"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">g</figure-callout>}2}$$

. After convolution with these filters, the data is thinned out through one sample ↓ 2 and at the outputs 3 and 4 of the filter block F1 low-frequency a2 _{j + 1} and high-frequency d2 _{j + 1} components are formed, respectively. The frequency distribution of the results of a one-dimensional direct fast wavelet transform is presented in figure 3, a.

The first high-frequency component d1 _{j + 1} from the output 1 of the filter block F1 is fed to the input of the filter block F2, which processes the data in columns.

и $$\overline{g1}$$

и после прореживания через один отсчет ↓2 на выходах 1 и 2 данного блока формируются значения $$d{11}_{j+1}^3$$

и $$d{11}_{j+1}^2$$

соответственно.The first part of the input column from the output 1 of the switch Sw of the filter block F2 is collapsed with filters $$\overline{h\mathrm{one}}$$

and $$\overline{g\mathrm{one}}$$

and after thinning through one count ↓ 2 at the outputs 1 and 2 of this block, values are formed $$d{\mathrm{eleven}}_{j+\mathrm{one}}^3$$

and $$d{\mathrm{eleven}}_{j+\mathrm{one}}^2$$

respectively.

, $$\overline{g2}$$

и после прореживания через один отсчет ↓2 на выходах 3 и 4 данного блока формируются значения $$d{11}_{j+1}^2$$

и $$d{12}_{j+1}^3$$

соответственно. Блоки фильтров F3-F5 обрабатывают входные данные аналогично блоку F2. Низкочастотная составляющая a1_j+1 с выхода блока фильтров F1 поступает на вход блока F3, на выходах 1, 2, 3. 4 которого формируются составляющие прямого быстрого вейвлет-преобразования $$d{11}_{j+1}^1$$

, a11_j+1, a12_j+1 и $$d{12}_{j+1}^1$$

соответственно. Низкочастотная составляющая a2_j+1 с выхода блока фильтров F1 поступает на вход блока F4, на выходах 1, 2, 3, 4 которого формируются составляющие прямого быстрого вейвлет-преобразования $$d{21}_{j+1}^1$$

, a21_j+1, a22_j+1 и $$d{22}_{j+1}^1$$

соответственно. Высокочастотная составляющая d2_j+1 с выхода блока фильтров F1 поступает на вход блока F5, на выходах 1, 2, 3, 4 которого формируются составляющие прямого быстрого вейвлет-преобразования $$d{21}_{j+1}^3$$

, $$d{21}_{j+1}^2$$

, $$d{22}_{j+1}^3$$

и $$d{22}_{j+1}^3$$

, соответственно. Распределение по частотам результатов двухмерного прямого быстрого вейвлет-преобразования представлено на фиг.3,б.The second part of the input data column from output 2 of the switch Sw of the filter block F2 is collapsed with filters $$\stackrel{}{h}$$$$\overline{2}$$

, $$\overline{\mathrm{<figure-callout\; id="2"\; label="g"\; filenames="00000043.png,00000045.png"\; state="\{\{state\}\}">g</figure-callout>}2}$$

and after thinning through one count ↓ 2 at the outputs 3 and 4 of this block, values are formed $$d{\mathrm{eleven}}_{j+\mathrm{one}}^2$$

and $$d{12}_{j+\mathrm{one}}^3$$

respectively. Filter blocks F3-F5 process the input data similarly to block F2. The low-frequency component a1 _{j + 1} from the output of the filter block F1 goes to the input of the block F3, at the outputs 1, 2, 3. 4 of which the components of the direct fast wavelet transform are formed $$d{\mathrm{eleven}}_{j+\mathrm{one}}^{\mathrm{one}}$$

, a11 _{j + 1} , a12 _{j + 1} and $$d{12}_{j+\mathrm{one}}^{\mathrm{one}}$$

respectively. The low-frequency component a2 _{j + 1} from the output of the filter block F1 goes to the input of the block F4, at the outputs 1, 2, 3, 4 of which the components of the direct fast wavelet transform are formed $$d{21}_{j+\mathrm{one}}^{\mathrm{one}}$$

, a21 _{j + 1} , a22 _{j + 1} and $$d{22}_{j+\mathrm{one}}^{\mathrm{one}}$$

respectively. The high-frequency component d2 _{j + 1} from the output of the filter block F1 goes to the input of the block F5, at the outputs 1, 2, 3, 4 of which the components of the direct fast wavelet transform are formed $$d{21}_{j+\mathrm{one}}^3$$

, $$d{21}_{j+\mathrm{one}}^2$$

, $$d{22}_{j+\mathrm{one}}^3$$

and $$d{22}_{j+\mathrm{one}}^3$$

, respectively. The frequency distribution of the results of two-dimensional direct fast wavelet transform is presented in figure 3, b.

The set of values of 16 components at all outputs of the filter blocks F2-F4 is the result of a direct fast wavelet transform j + 1 and can be used for subsequent processing based on various algorithms, including rotations at fixed angles. The set of 4 low-frequency components a11 _{j + 1} , a12 _{j + 1} , a21 _{j + 1} and a22 _{j + 1} at the outputs 2, 3 of filter blocks F3 and F4, respectively, can be used to perform direct fast wavelet transform of the next level.

In accordance with the claimed method, the inverse fast two-dimensional wavelet transform is performed using 5 Fb-Fb5 filter blocks of the same type (FIG. 2), each of which has 4 inputs, two pairs of low-pass and high-pass filters h1, g1 and h2, g2 with a thickening implementation ↑ 2 samples at the input of each, 2 adders ⊕ at the output of each pair of filters to form the first and second parts of the output sequence, contains a switch - Sw, which performs multiplexing functions to form one full frequency component.

, $$d{11}_{j+1}^2$$

, $$d{11}_{j+1}^2$$

и $$d{12}_{j+1}^3$$

соответственно. Значения составляющих $$d{11}_{j+1}^3$$

, $$d{11}_{j+1}^2$$

подвергаются сгущающей выборке ↑2, далее осуществляется фильтрация на основе свертки с h1 и g1 и в результате суммирования на ⊕ формируется первая часть столбца d1_j+1. Значения составляющих $$d{12}_{j+1}^2$$

, $$d{12}_{j+1}^3$$

подвергаются сгущающей выборке ↑2, далее осуществляется фильтрация на основе свертки с h2, g2 и в результате суммирования на ⊕ формируется вторая часть столбца d1_j+1.The inputs 1-4 of the filter block Fb1 receive frequency components $$d{\mathrm{eleven}}_{j+\mathrm{one}}^3$$

, $$d{\mathrm{eleven}}_{j+\mathrm{one}}^2$$

, $$d{\mathrm{eleven}}_{j+\mathrm{one}}^2$$

and $$d{12}_{j+\mathrm{one}}^3$$

respectively. Component Values $$d{\mathrm{eleven}}_{j+\mathrm{one}}^3$$

, $$d{\mathrm{eleven}}_{j+\mathrm{one}}^2$$

are subjected to a thickening sample ↑ 2, then filtering is performed on the basis of convolution with h1 and g1, and as a result of summation on ⊕, the first part of the column d1 _{j + 1 is formed} . Component Values $$d{12}_{j+\mathrm{one}}^2$$

, $$d{12}_{j+\mathrm{one}}^3$$

are subjected to a thickening sample ↑ 2, then filtering is performed on the basis of convolution with h2, g2, and as a result of summation on ⊕, the second part of the column d1 _{j + 1 is formed} .

The first and second parts of the column d1 _{j + 1} are fed to the inputs 1, 2 of the switch Sw of the filter block Fb1, the output of which is formed by the full high-frequency component d1 _{j + 1} in columns, fed to the input 1 of the filter block Fb5. Filter blocks Fb2-Fb4 work similarly.

, a11_j+1, a12_j+1 и $$d{12}_{j+1}^1$$

соответственно, и на выходе данного блока формируется полная низкочастотная составляющая a1_j+1 по столбцам, поступающая на вход 2 блока фильтров Fb5. На входы 1-4 блока фильтров Fb3 поступают частотные составляющие $$d{21}_{j+1}^1$$

, a21_j+1, a22_j+1 и $$d{22}_{j+1}^1$$

соответственно, и на выходе данного блока формируется полная низкочастотная составляющая a2_j+1 по столбцам, поступающая на вход 3 блока фильтров Fb5.At the inputs 1-4 of the filter block Fb2 received frequency components $$d{\mathrm{eleven}}_{j+\mathrm{one}}^{\mathrm{one}}$$

, a11 _{j + 1} , a12 _{j + 1} and $$d{12}_{j+\mathrm{one}}^{\mathrm{one}}$$

respectively, and at the output of this block, a complete low-frequency component a1 _{j + 1 is formed} in columns, which is fed to input 2 of the filter block Fb5. At the inputs 1-4 of the filter block Fb3 received frequency components $$d{21}_{j+\mathrm{one}}^{\mathrm{one}}$$

, a21 _{j + 1} , a22 _{j + 1} and $$d{22}_{j+\mathrm{one}}^{\mathrm{one}}$$

respectively, and at the output of this block, the complete low-frequency component a2 _{j + 1 is formed} in columns, which is fed to input 3 of the filter block Fb5.

, $$d{21}_{j+1}^2$$

, $$d{22}_{j+1}^3$$

и $$d{22}_{j+1}^3$$

соответственно, и на выходе данного блока формируется полная высокочастотная составляющая d2j+i по столбцам, поступающая на вход 4 блока фильтров Fb5. Значения составляющих по столбцам d1_j+1 и a1_j+1 подвергаются сгущающей выборке ↑2 по строкам, далее осуществляется фильтрация на основе свертки с h1 и g1 и в результате суммирования на ⊕ формируется первая часть строк a_j. Значения составляющих по столбцам a2_j+1 и d2_j+1 подвергаются сгущающей выборке ↑2 по строкам, далее осуществляется фильтрация на основе свертки с h2, g2 и в результате суммирования на ⊕ формируется вторая часть столбца a_j. Первая и вторая части строк a_j подаются на входы 1, 2 переключателя Sw блока фильтров Fb5, на выходе которого формируется полная составляющая a_j по строкам. Данная низкочастотная составляющая a_j является результатом выполнения обратного быстрого вейвлет-преобразования и может использоваться в реализации алгоритмов обработки изображений или в совокупности с соответствующими высокочастотными составляющими участвовать в вейвлет-преобразовании следующего уровня.At the inputs 1-4 of the filter block Fb4 received frequency components $$d{21}_{j+\mathrm{one}}^3$$

, $$d{21}_{j+\mathrm{one}}^2$$

, $$d{22}_{j+\mathrm{one}}^3$$

and $$d{22}_{j+\mathrm{one}}^3$$

respectively, and at the output of this block, the full high-frequency component d2j + i is formed in columns, fed to the input 4 of the filter block Fb5. The values of the components in columns d1 _{j + 1} and a1 _{j + 1} are subjected to a thickening sample ↑ 2 by rows, then filtering is performed on the basis of convolution with h1 and g1, and as a result of summing on ⊕, the first part of rows a _{j is formed} . The values of the components in columns a2 _{j + 1} and d2 _{j + 1} are subjected to a thickening sample ↑ 2 by rows, then filtering is performed on the basis of convolution with h2, g2, and as a result of summing on ⊕, the second part of column a _{j is formed} . The first and second parts of the lines a _j are fed to the inputs 1, 2 of the Sw switch of the filter block Fb5, at the output of which the total component a _{j is formed} along the lines. This low-frequency component a _j is the result of performing the inverse fast wavelet transform and can be used in the implementation of image processing algorithms or, in combination with the corresponding high-frequency components, to participate in the next level wavelet transform.

Figure 4 presents the simulation results of the forward and reverse fast two-dimensional wavelet transform using the Daubechies basis in accordance with the claimed method. Figure 4, a presents the original test image. Figure 4, b presents the result of direct fast wavelet transform of the first level in rows. Figure 4, c shows the result of direct fast wavelet transform of the first level in rows and columns.

Figure 4, g presents the difference between the result of direct fast wavelet transform of the first level, made in accordance with the prototype and with the claimed method. Here, the frequency ranges were combined and, as can be seen, the values can differ by 3/4 of the area (75%). Matches 1/4 of the values corresponding to the lower right dark quadrant.

As follows from the foregoing, when performing a wavelet transform in accordance with the claimed method of direct and inverse fast two-dimensional wavelet transform, values corresponding to additional frequency ranges are formed, which ensures the fulfillment of the claimed main technical result and two additional technical results in the proposed method.

The proposed invention can find application in various fields of image processing and multidimensional signals, including coding and compression systems, technical vision, etc., as well as in data transmission systems over computer networks.

List of sources used

1. Gonzalez R. Digital image processing / R. Gonzalez, R. Woods. - M .: Technosphere, 2005 .-- 1072 p.

2. Dobeshi I. Ten lectures on wavelets / I. Dobeshi. - Izhevsk: SRC “Regular and chaotic dynamics”, 2001. - 464 p.

3. Welstead S. Fractals and wavelets for image compression in action / S. Welstead. - M .: Triumph, 2003 .-- 320 p.

Claims (1)

A method for performing direct and inverse fast two-dimensional wavelet transform, based on convolution of input data on rows with low-frequency and high-frequency filters, the outputs of which are incompletely sampled, resulting in low-frequency and high-frequency values of one-dimensional transformation, then convolution with low-pass and high-pass filters, followed by incomplete sampling, and the described sequence can be applied to low-frequency coefficients l actions to perform the next level of direct conversion, and the inverse wavelet transform is performed in columns based on a thickening sample applied to the low-frequency and high-frequency components obtained as a result of the direct wavelet transform, followed by convolution with low-pass and high-pass filters and summation, then line processing based on a thickening sample applied to the obtained low-frequency and high-frequency components, followed by convolution with low-frequency high and high-pass filters and summation, while the result can be used with the corresponding high-frequency components to perform the next level of the inverse wavelet transform, characterized in that for direct conversion the input sequences of values, both in the processing of rows and columns, are divided into two parts of the same length, and each second of these parts is processed by an additional pair of high-pass and low-pass filters, in which the coefficients are used f to form a set of filters, they are selected in the opposite order compared to such coefficients for filters that process the first parts of sequences, with further incomplete sampling for all additional groups of obtained values, and in the reverse transformation, additional groups of coefficients uniquely determined by direct transformation are subjected to a thickening sample , further convolution with filters, those of which process the second parts of the sequences, are formed on the basis of a combination of coefficients of agents selected in the reverse order compared to such coefficients of filters processing the first parts of sequences, and after summing, they form combined sequences with high accuracy coinciding with such sequences shared by direct conversion, and this is done both for processing rows and columns .

Images