Multiwavelet Packets - A New Multiwavelet Technology for Image Processing and Coding

Abstract

A method and algorithms for constructing two-dimensional (2D) discrete fractal step multiwavelets and multiwavelet packets, as well as discrete multiwavelet transforms with specified sizes of multiwavelet packets for different decomposition levels, have been developed. These algorithms allow for the construction of multiwavelets without performing convolution and downsampling operations, unlike the classical method. Additionally, low complexity algorithms for fast 2D multiwavelet transforms (2D MWT) with specified sizes of multiwavelet packets for different decomposition levels have been developed. A methods and algorithms for processing and coding image based on 2D MWT have been proposed as a new multiwavelet technology. A three-level 2D MWT-based image coding method has been proposed, which exhibits a 78.8 times lower multiplicative complexity and requires 22.5 times fewer additions compared to the well-known classical Mallat algorithm. fractal step multiwavelets; wavelet packets; multiwavelet packets; discrete multiwavelet

-

transforms; fast algorithms; fast multiwavelet transforms; multiplicative complexity; multiwavelet technology.

1. Introduction

The systematic theory of constructing orthonormal wavelet bases was developed by Meyer and Mallat [ 1,2 ] through the construction of short-scale approximations of signals [ 3 ]. This theory was based on original ideas developed in computer visualization by Bart and Adelson [ 4 ] for analyzing signals at multiple levels of decomposition. The complete elimination of redundant information is equivalent to constructing a basis in the signal space. While wavelet bases were the first to emerge, they were quickly followed by other families of bases such as wavelet packets [ 5 ], multiwavelets [ 6 ], and local cosine bases [ 2 ]. Multiwavelets (MW) are designed for the decomposition of "multichannel" signals that have more than one component. Their attractiveness lies in the fact that, like regular wavelets, they generate short-scale approximations of the signal that are more localized in space and provide a fast wavelet transform algorithm (Mallat`s algorithm) [ 2,7 ]. Constructing multiwavelets allows for great flexibility in construction by introducing multiple scaling functions and wavelets. A better compromise can be achieved between the supports of the MW and their zero moments [ 6 ]. However, constructing MW proved to be more challenging than regular wavelets. The issue is that the scaling (or dilation) equations have matrix coefficients that do not commute with each other. Therefore, finding a suitable set of coefficients that gives a solution to the inverse equation is quite complex. The first example of orthogonal continuous MW was obtained by Geronimo, Hardin, Massopust (GHM) [ 6 ]. The scaling functions and wavelets obtained, known as GHM, were piecewise-like, and the construction was based on methods from the theory of integral functional systems that generate fractal functions. In [ 8 ], MW and multiwavelet packets (MWP) were defined and orthogonal and biorthogonal MW were constructed. However, multiwavelet packets increase computational complexity due to the process of basis selection. Multiwavelets with the SPIHT algorithm are applied for image compression

2023 Copyright for this paper by its authors. [ 9 ]. Sumalatha and Subramanyam [ 10 ] compared the efficiency of different multiwavelets in compressing medical images and showed that the SA4 multiwavelet demonstrates the best efficiency compared to GHM and CL multiwavelets. It is noted that multiwavelets better detect and represent contours compared to wavelets. In [ 11 ], the use of SA4 multiwavelet with the SPEC algorithm for image compression was proposed, resulting in a 3 dB improvement in PSNR compared to scalar wavelets. In [ 12 ], multiwavelets with the SPIHT algorithm are used for fingerprint compression. Rema et al. [ 13, 14, 15 ] applied SA4 multiwavelets and the SPIHT algorithm using a genetic algorithm for optimizing the coefficients of the pre-filter for fingerprint compression. The improvement in average PSNR for FVC 2000 DB1 and 2002 DB3 databases was 4.23 dB and 2.52 dB, respectively, for bit rates ranging from 0.01 to 1, at compression ratios of 80:1 and 100:1. As noted in [ 15 ], the existing methods in the literature currently achieve 100% recognition only up to a compression ratio of 180:1. In [ 15 ], 100% identification accuracy was achieved for images from the NIST-4, NITGEN, FVC2002DB3_B, FVC2004DB2_B, and FVC2004DB1_B databases at compression ratios of 520:1, 210:1, 445:1, 545:1, and 1995:1, respectively. In [ 16 ], a contour detection method using multiwavelets and the Canny algorithm was proposed. The algorithm's performance is compared using the False Correct Ratio (FCR), which measures the ratio of falsely detected edges to correctly detected edges, and demonstrates an order of magnitude better efficiency for various classes of images compared to scalar wavelets. In [ 17 ], a new human face recognition system utilizing a combination of multiwavelet transform and neural network was proposed. Perfect recognition of thousands of human face images was achieved. In [ 18 ], it was shown that multiwavelets improve SNR by 29,7% compared to wavelets in the analysis of noisy electrocardiograms.

2. Fractal step functions, fractal multiwavelets and multiwavelet packets

In [ 19 ], a new class of normalized fractal step functions (FSF) is introduced, and based on them, a method is developed to construct a complete family of orthonormal basis systems of a new class of fractal multilevel wavelets with different shapes and linear and nonlinear value changes. The key properties of FSF are their recurrence, self-similarity at different scales, and fractal dimension, hence the name "fractal". In [ 20 ], a new class of fractal step multiwavelets (FSMW) is constructed based on FSF with linear and nonlinear value changes, and their transformations with fast algorithms of linear computational complexity are developed. FSMW are symmetric and orthogonal, and they possess high frequency localization, which enhances the representation of high-frequency signals. They exhibit excellent short-scale approximating properties for smooth functions, allowing for more accurate representation of images with complex textures.

In [ 21 ], orthonormal bases of fractal step multilwavelets and multiwavelet packets are described, and based on them, a method and algorithm for fast multiwavelet transform with low computational complexity are developed. The proposed algorithm achieves a 70-fold reduction in computational complexity compared to the well-known classical Mallat algorithm [ 2,7 ] in terms of multiplicative complexity and a 20-fold reduction in terms of additive complexity. The obtained results present a new multilwavelet technology for signal and image processing. 2.1.

The discrete multiwavelet transform

For a function f t  represented by a sequence of numbers, the discrete multiwavelet transform (DMWT) is defined by a pair of discrete wavelet transforms [ 21 ]

W  j0,i0   1 N 1

 f t   j0,i0  t , j  j0 ,

N t0 W k  j,i   i 1 N 1

 f t  jk,i t , i  1, N 1 ,

N t0 where N - number of multiwavelet functions of rank k that represent a multiwavelet packet of size N  N , N  2 p , p  2 ,  jk,i t  - i-th function of a fractal step multiwavelet of rank k [ 20 ], (1) (2) k  0,1,... p  2 for j-th level of decomposition, j  0,1, 2,...m ;  j0 ,i0 t  - Haar scaling function j0  0 and i0  0 ,  0,0 t   1 .

In this case, addition is performed for the values of t, i, and j.

 n  For function f  x , x  0, 2n1, m    .

 p 

2.1.1. Fast multiwavelet transform

In [ 21 ] a fast multiwavelet transform (FMWT) is proposed, which is an efficient method for computing the DMWT. It utilizes the interdependencies between the coefficients of the DMWT at neighboring levels of decomposition. Approximation coefficients W  j  1,i0  and detail coefficients  W k  j 1,i  level j  1 can be calculated through approximation coefficients W  j,i0  level j. 

Theorem [21]

W  j  1,i0   ni0 nW  j, n , n  0,1,...N 1 , W k  j,i   1 N1 f t  jk,i t , , i  1,...N 1 , k  0,1,... p  2 .

i N t0

Expressions (3) and (4) represent the algorithm of fast multiwavelet transform, which can be computed using only scalar product operations without convolution (equivalent to filtering) and downsampling by a factor of 2, as required by the well-known Mallat algorithm for fast wavelet transform (FWT) [ 2,22 ].

In fig. 1 (a), for example, a block diagram of a three-level fast multiwavelet transform with multiwavelet packets of size 4x4 is presented. For example, the space VJ ( function f t  ) can be expressed in the form of

VJ  VJ 3 WJ 3,3 WJ 3,2 WJ 3,1 WJ 2,3 WJ 2,2 WJ 2,1 WJ 1,3 WJ 1,2 WJ 1,1 representing a two-level tree with 10 different layouts. As a result, we will get a tree of subspaces of the analysis (Fig. 1 (b)) and a tree of coefficients (Fig. 1 (c)) for the three-level FMWT of the analysis block in Fig. 1. (a).

At the same time, the well-known classical three-scale fast wavelet transform assumes the presence of three possible schedules, the analysis tree of the wavelet package leads to 26 different layouts. In the general case, P-scale transforms based on classical wavelet packets (and their corresponding analysis tree consisting of P+1 level) make it possible to obtain different distributions in the number of

D  P  1  D  P 2  1 where D 1  1 . With such a large number of admissible decompositions, transformations based on the application of packets allow for better control of the process of splitting the spectrum, which is subject to decomposition of the function into parts. Of course, this leads to an increase in computational complexity.

2.1.2. A method for constructing a discrete multiwavelet transform based on a 4x4 multiwavelet packet

Let's construct a discrete multiwavelet transform matrix of order 4, in which the zeroth row represents a scale rectangular function  h t  , which is a Haar function of zero index  h 0, t   1/ 4 . The first line represents the function  h t  , the mother FSMW of rank zero (k=0) of type 1 with (3) (4) decreasing values at an interval equal to its period, and in a form that approaches the first cos-function of type II. (b) (c)

Figure 1. Block diagram of a three-level FMWT with one multiwavelet packet of size 4x4, (a) is a block diagram, (b) is a tree of analysis subspaces, and (c) is a tree of coefficients.

The second line represents the function of the mother FSMW of type 2, which is the function of the mother modified Haar wavelet (MHW) [ 23 ] of rectangular shape, which approaches the second cosfunction of type II [ 19,20,21 ]. The MHW function can be represented by Haar wavelets of the following scale: where  1,k t  

 2 t   h t   h (2t)  h (2t 1), 2 h 2t  k  are the Haar wavelet functions at a given scale with index j  1.

The third row represents the function  3(0) t  of the zero-rank (k=0) of mother FSMW of type 3 with decreasing values on the half-intervals of the unit interval 0,1 and saw-like form, that approaches the third cos-function of type II. Let's consider the DMWT matrix, which represents a 4x4 multiwavelet packet (MWP) with permuted rows based on bit reversal permutations (BRP) [26] SWT4*  P4SWT4 , SWT4*  B4S4*, (5) 0 where P4 is a BRP 4x4 matrix, P4  diag[1, I2,1], I2   1 1. 0

S4* is a MWP 4x4 matrix with permuted rows.

B4 is a diagonal matrix 4x4 of the normalization coefficients, B4  diag[1/ 2,1/ 2, b1, b3], Matrix S4* can be constructed based on the recurrent method: where H 2 is a 2х2 Hadamard matrix, H 4 is a factor-matrix 4x4 with non-zero elements  1 . At the same time

S4*  R4H4diag[H2, H2 ],

1 1 1   H2  1 1 , H4  1   1 1 1 1

 1 ,   1   r0 R4  diag  I2 , R20  , R0   1 2 s20 s0  1  , r0  2 

R4 is a 4x4 diagonal matrix that contains a 2x2 identity matrix I2 and a 2x2 size matrix R20 , a zero-rank k  0 «rotate-compression/stretch» operator [ 21 ] with constants of r10 , r20 , s10 and s20 of rank k  0 , which satisfy the condition of the "rotation-compression" operator r10  s10  1 & r0 2  s0 2  1 and the "rotation-stretch" operator r20  s20  1, r0 2  s0 2  1 . 1 1 2 2 (6) (7) (8) (9) The S4 MWP matrix of size 4х4 looks like 1 1 1 s S4   1 1 1 q 1 s 1 q 1  1 . 1 

 1

For example, the elements s and q of the matrix S4 for functions  10 t  and  30 t  with nonlinear FSF [ 21 ] acquire the following values: s  2 / 3 and q  3/ 2 . At the same time, the constants of the operator matrix R0 take the following values: r1,0H  5 / 6 , r2,0H  5 / 4 , s1,0H  1/ 6 , s20,H  1/ 4 .

2

2.1.3. A method for constructing a discrete multiwavelet transform based on a 8x8 multiwavelet packet

Let's construct the 8-order DMWT matrix, in which the zeroth row represents a scaled rectangular function  h t  , which is a Haar function of zero index  h 0, t   1/ 8 . The first row represents the function  1 t  of the first-rank k  1 of mother FSMW of type 1 with decreasing values at an 1 interval, which is equal to its period, and in a form that approaches the first cos-function of type II. The second row represents the function  20 t  of the zero-rank k  0 of mother FSMW of type 2 with decreasing values on the first half-interval and rising values on the second half-interval, which is close in form to the second cos-function of type II and can be represented by a wavelet function  101, j 2t  of the zero-rank k  0 of type 1 [ 19,20,21 ]

 20 t   1,00 2t   1,01 2t  1 .

The third row represents the function  31 t  of the first-rank k  1 of mother FSMW of type 3 with decreasing values on the half-intervals of the unit interval 0,1 and saw-like form that approaches the cos-function of type II [ 19,20,21 ]. Fourth and fifth rows represent zeroth and first MHW functions, which can be obtained by scaling at a given scale with an index of i  1 , j  0,1;  h1, j 2t  

2 h 2t  j  . The sixth and seventh lines represent the zero and first functions FSMW zero rank k  0 type 3  301, j 2t  

2 30 2t  j  , which are obtained by scaling at a given scale i  1 , j  0,1. Consider the matrix SWT8* DMWT, which represents MWT order 8х8 with rearranged lines on the base BRP [26] where P8 - matrix 8х8 BRP, P8 0,7  0, 4, 2,6,1,5,3,7 .

Matrix SWT8* order 8х8 DMWT with permuted rows can be written through a matrix MWT SWT8*  P8SWT8 ,

SWT8*  B S* , 8 8 where S8* - matrix 8х8 MWT with permuted rows, B8 - diagonal 8x8 matrix of normalization coefficients.

Matrix S8* can be built based on the recursive method:

S8*  B8R8H8diag S4*, S4*  , where H8 - factor matrix 8x8 with nonzero elements 1 ,

H8  diag I4, 1, I3  antidiag I4, I2  I20  ,

1 I40  diag I20, I20  , I20  diag[ 1,0 ] , I20   0 0 0  ,

I40 - a 4x4 diagonal matrix that contains matrices  I20 order 2х2, I2 , I3 , I4 - unit matrices of size 2х2, 3х3 і 4х4,  - sign of Kronecker multiplication of two matrices, B8 - diagonal matrix with elements 1 і 2 , B8  diag B2  , B2  diag 1, 2  , R8 - diagonal matrix 8х8, that contains unit matrix   I 4 order 4х4, matrix R31 order 3х3 first rank rotation-compression/extension operator k  1 and a unit,

R8  diag I4 , R31,1 .

 Matrix R1 contains non-zero elements, a unit and constants r11 , r21 , s11 і s21 first rank k  1 3 , which satisfy the condition of the operator R31 : (10) ( 11) (12) (13) (14) 1  1  1  1  .

For example, elements si , qi , i  1,4 , matrix S8 for functions  11 t  ,  31 t ,  20 t  ,  3(01, j) 2t  j  , j  0,1 with non-linear FSF [ 19,20,21 ] acquire such values: s1  7 / 8 , s2  3/ 8 , s3  1/ 4 s4  2 / 3 , q1  7 /17 , q2  33/17 , q3  43/17 , q4  3/ 2 . At the same time, the constants of the matrix R31 take the following values: r1,1H  5 / 8 , r2,1H  30 /17 , s1,1H  3/ 8 і s21,H  13 /17 .

In [ 20 ] a recurrent matrix method for constructing a size N  N multiwavelet package is proposed.

Algorithm for fast calculation of 8-point DMWT

Based on the recurrent matrix representation of the multiwavelet packet size N  N in [ 20 ] the factorized representation of the matrix as a product 2 log2 N  1 matrix is obtained. This makes it possible to build a fast calculation algorithm (FA) DMWT. Thus, the matrix SWT8* can be represented as a product of five factor matrices:

SWT8*  B8S8,5S8,4S8,3S8,2S8,1 , where S8,k - k -i, k  1,5 , factor-matrix 8x8 of the algorithm proposed in [ 20 ] for fast calculation of 8-point DMWT, B8 - diagonal 8x8 matrix of normalization coefficients: (16) (22) (23) (24) (25) S8,1  I4  H2 , S8,2  diag H4, H4  ,

S8,3  diag I2, R20, I2, R20  , S8,4  H8 , S8,5  R8  diag I4, R31,1 , 

B8  23/2 diag 1, 2,b2,b4,b1, 2,b3,b4  .

b1  8 2 / 63, b2  3 2 /13, b3  17 / 819, b4  4 / 13 .

Algorithm for fast calculation of 8-point inverse DMWT

Matrix SWT81 the inverse DMWT of order 8 can be obtained by transposition:

SWT81  SWT8*T .

SWT81  S8,1S8T,2S8T,3S8T,4S8T,5B8 ,

Matrix SWT81 on the basis of (12)-(14) taking into account the symmetry of the matrix  H2T  H2  can be represented as a product of five transposed factor matrices:

T where S8,k - k -i, k  2,5 , transposed 8x8 factor matrices of the proposed algorithm for fast calculation of the 8-point inverse DMWT:

S8T,2  diag H4T , H4T  , S8T,3  diag I2, R20T , I2, R20T  ,  (26) S8T,4  H8T , S8T,5  R8T  diag I4, R31T ,1 ,



H8T  diag I4, 1, I3  antidiag I2  I20, I40  .

R1T   3

Computational complexity

In [ 20 ] the FA calculation of DMWT with a multi-wavelet packet of size NxN, which requires M N  3N / 2  4 multiplication operations, and addition AN  17N / 4  6 for functions with linear changes and AN  19N / 4  6 – with non-linear changes was developed, that is, it has a linear computational complexity.

Computational complexity of FA computing the DMWT for an input sequence that represents a signal N=8 makes up: M 8  8 of multiplications, а A8  28 additions for functions with linear changes and A8  32 addition - with non-linear changes. For a three-level scheduling scheme using the FA multiwavelet transform based on an 8x8 multiwavelet packet, it is necessary M N ,8  M8 3 N / 8i  M873N  73N multiplication and AN ,8  A8 3 N / 8i  A873N  511N i1 512 64 i1 512 128 73N /16 73 functions with non-linear changes.

The well-known Mallat algorithm [ 2,22 ] of fast classical wavelet transform for filters with K nonzero coefficients of the wavelet packet of the whole tree with depth log2N needs K N log2N of multiplications and additions, which at K=8 makes 8N log2N operations.

Proposed FA [ 21 ] calculation of the multiwavelet transform compared to the well-known classical Mallat algorithm for filters with 8 non-zero coefficients requires KM  8N log2 N  512log2 N times

2.1.4. Two-dimensional discrete multiwavelet transform

Let's define DMWT functions f  x, y  sizes M  N as follows:

W  j0, m, n  1 M 1 N 1 MN x0 y0 f  x, y j0  x, y , (27) Wi  j,m,n  i 1 M1 N1 f  x, y ii, j,m,n  x, y, i  1, N 1, i  H ,V , D .

MN x0 y0

As in the one-dimensional case, j0 - the initial level of the schedule, and coefficients W  j0, m, n  determine the approximation of the function f  x, y  at level j0 . Coefficients Wii  j, m, n define horizontal, vertical and diagonal details for levels j  j0 . We consider j0 =1 and choose numbers N and M so that they are a power of two. N  M  2J  , J   2 , m, n  0,1, 2,...2 j 1 . With, p J  0,1, 2, ...r , r   j/ p , N1  2 , p  2 . Input function f  x, y  can be restored by given coefficients W and Wii in (27) and (28) using the inverse DMWT: (28) (29) f  x, y  1

 W  j0, m, n j0,m,n  x, y  

MN m n  1 N11 r

   Wii  j, m, n i, j,m,n  x, y .

MN iH ,V ,D i1 j1 m n

Like one-dimensional DMWT, two-dimensional DMWT can be implemented using only scalar product operations without convolution operations (equivalent to filtering) and sparse sampling with a factor of 2, which requires the well-known classical method of two-dimensional fast wavelet transform [ 2,22 ]. Since the used scale and multiwavelet functions are separable, first one-dimensional FMWT is calculated along the lines of the function f (x, y) , and then one-dimensional column-wise FMWT is calculated from the obtained result. Note that, as in the case of its one-dimensional counterpart, for obtaining approximation coefficients and details for the level of decomposition j 1 two-dimensional FMWT operates with approximation coefficients of the decomposition level J.

A single-level block of multiwavelet packets can be reused (for which the approximation coefficients at the output of this block of multiwavelets must be applied to the input of the same next block of multiwavelets), resulting in a p-level transform j  j 1, j  2, ..., j  p . As in the one-dimensional case, the image f (x, y) is used as coefficients W ( j,m,n) at the entrance. By multiplying n columns of the image on the sequence  (n) і  k (n) , k 1,2,3, we will get four parts of the image with a four times less of resolution in the vertical direction. High-frequency or detailed parts characterize the highfrequency components of the image in the vertical direction. Low-frequency or approximation contains information about low frequencies in the vertical direction. A similar for m rows procedure is then applied to the four parts of the image. This gives an output of sixteen images (16 parts of the original image), which can be represented by four groups of images, one, three and six images per group: W ,  WH1 , WH2 , WH3  , WV , WV2 , WV3  , WV1H,2 , W VH , W VH , W VH , W VH , W VH  і WD1 , WD2 , WD3  .

1 1,3 2,1 2,3 3,1 3,2

In fig. 2. a block diagram of a one-level two-dimensional fast multiwavelet transform (FMWT) with one multiwavelet packet of size 4x4 is presented. In fig. 3. the images are shown, which are the result of the scalar product of the image f (x, y) and two-dimensional scaling functions and multi-wavelet functions for one level of decomposition. In fig. 4 presents the corresponding one-level sixteen-base analysis tree of the FMWT (for one level of the schedule).

Note that the frequency plane is divided into five constituent parts of different areas. The lowfrequency part of the range in the center corresponds to the conversion coefficients W ( j  1,m,n) and large-scale space Vj1 . This is fully consistent with the one-dimensional case. In the two-dimensional case, we have four (instead of three) multiwavelet subspaces. They are denoted as WjH1,i  , WjV1,i  , WjD1,i , WjVH1,i, j  and correspond to the coefficients WH ( j 1,m,n) , WV ( j 1,m,n) , i i WD ( j 1,m,n) і WViH,j ( j 1,m,n).

i

The analysis tree for two-dimensional P-scale classical well-known wavelet packets makes it possible to construct various expansions in the number [ 22 ] 4

D  P  1  D  P   1 , where D 1  1 . Thus, the total number of different decompositions that can be obtained from a three-scale tree is 83522. With such a large number of decompositions, two-dimensional transforms based on the application of packets allow better control over the process of dividing the twodimensional spectrum subject to image decomposition into parts. However, this leads to a significant increase in computational complexity.

A method of image coding based on multiwavelets and multiwavelet packets using 2D FMWT

In [ 20 ], a new multi-wavelet technology and image coding method based on 2D DMWT based on fractal steps using fast algorithms is proposed. A method of image coding based on a two-level schedule using 2D fast DMWT with multi-wavelet packets for the first level of size 4x4 and for the second level of size 32x32 was developed. As shown by the experimental results, the proposed method of multiwavelet coding in comparison with the well-known block method based on the integer cosine transformation (ICT) of order 32, which is used in the H.265 video coding standard [ 24 ] according to the characteristic of quantitative assessment of PSNR distortions (dB) for seven of test images of classes A, B, C with a resolution of 2560x1536, 2048x1280, 1280x768 reduces the average value by 0.43-1.06 dB at average values of the compression ratio from 4 to 58, and at high values - the average PSNR reduction is 0.62 dB At the same time, better quality is provided visually than H.265, since there are no block distortions, which are amplified at high degrees of compression for H.265. The computational complexity of the method proposed in [ 20 ] in comparison with the well-known [ 2 ] classical wavelet method at the filter length L = 8 based on a 10-level (m = log2N, N = 1024) 2D FWT (Mallats algorithm) by multiplication operations is reduced by 80 times, and in comparison with the block coding method based on ICT (H.265) [ 24 ] – by 11 times.

Justification of the number of schedule levels

An important factor that affects the computational complexity and error rate of multiwavelet coding recovery is the number of levels of the transform schedule. Since the p-level fast multiwavelet transform requires r iterations of the transform, the number of operations when calculating the direct and inverse increases with the increase in the number of expansion levels. However, the quantization of the coefficients of the higher level of the decomposition spreads over the entire large area of the reconstructed image. In many applications, such as searching an image database or transferring images for incremental recovery (progressive transfer), the number of conversion levels is determined by the resolution of the stored or transferred images, and the scale of the smallest copy used. Note that the main compression occurs at the initial schedules. As shown in [ 22 ], when the number of expansion levels is increased to more than three, the number of coefficients that are set to zero changes little.

Computational complexity of the image coding method based on the 8-point 2D FMWT for three levels of schedule.

For a three-level schedule scheme when encoding an image of size NxN based on an 8-point 2D 3 M8 4161N 2 FMWT with an 8x8 multiwavelet packet, it is necessary M N ,8  M8 2N 2 / 82i1  of i1 16384 multiplications that at M 8 =8 makes up multiplications, or by one pixel is required 7  4161N 2 M8/ p  2,03 multiplication by pixel, and AN ,8  A8 2N 2 / 82i1  A8 4161N 2 additions that at A8 =28 3 i1 16384 makes up

4096 functions with linear changes. For functions with non-linear changes - A8 =32 is required additions, by one pixel is required A8/ p  7,11 additions by one pixel for

 7,88log2 N times fewer multiplications that for N=210 makes up 78,8 times and in

 2, 25log2 N times less additions, which is 22.5 times less for functions with linear changes in values. For functions with non-linear changes in values K A  8,13 less additions, which is 19.7 times less. The paper proposes a multi-wavelet method of image coding based on a three-level two-dimensional FMWT with a multi-wavelet packet of size 8x8. The proposed method of image coding based on a three-level 8-point two-dimensional FMWT compared to the wellknown classical Mallat algorithm [ 2 ] FWT for filters with 8 non-zero coefficients has 7,88 log2N times the lower multiplicative complexity, which for N=210 is 78.8 times and needs in 2,25log2 N times less additions, which is 22.5 times less for functions with linear changes.

 1,97 log2 N times 16log2 N

3. Conclusions

The construction methods and algorithms of two-dimensional (2D) discrete fractal step multiwavelets and multiwavelet packets, 2D discrete multiwavelet transforms with multiwavelet packets of given sizes for different levels of the schedule without performing convolution and sample thinning operations, unlike the classical Mallat method, have been developed. Algorithms of 2D fast multiwavelet transforms have been developed based on fast algorithms for calculating discrete multiwavelet transforms with multiwavelet packets of given sizes of linear computational complexity for different levels of the decomposition of low computational complexity for more accurate and faster image analysis and coding. A method and algorithms for image coding based on 2D FMWP are proposed as a new multi-wavelet technology for image coding, which, based on a three-level 8-point 2D FMWP, compared to the classic Mallat algorithm, 2D FVT for filters with 8 non-zero coefficients has 78.8 times lower multiplicative complexity and 22.5 times lower additive complexity.

4. References

References

[1] Meyer, Y. Wavelets Algorithms and Applications. 1993 . 133 p.

[2] S. Mallat . A Wavelet Tour of Signal Processing . 1998 , 577 p.

[3] Mallat S. Multiresolution Approximations and Wavelet Orthonormal Bases of L2(R) . Transactions of the American Mathematical Society . 1989 , Vol. 315 , No. 1 , pp. 69 - 87 .

[4] Burt , P. and Adelson , E. The Laplacian Pyramid as a Compact Image Code . IEEE Transactions on Communications , 1983 , Vol. 31 , №4, pp. 532 - 540 .

[5] Coifman R R , Meyer Y., Wickerhauser V . Wavelet analysis and signal processing , in: Wavelets and Their Applications , Boston, 1992 . pp. 157 - 178 .

[6] Jeffrey S. Geronimo; Douglas P. Hardin; Peter R. Massopust . Fractal Functions and Wavelet Expansions Based on Several Scaling Functions . Journal of Approximation Theory , 1994 , Vol. 78 , №3, pp. 373 - 401 .

[7] Mallat S A Theory for Multiresolution Signal Decomposition: The Wavelet Representation . IEEE Trans. Pattern Anal. Machine Intell . 1989 , Vol. 11 ,№7, pp. 674 - 693 .

[8] Martin M.B. , Bell A.E. New image compression techniques using multiwavelets and multiwavelet packets . IEEE Trans Image Process . 2001 , Vol. 10 , №4, pp. 500 - 510 .

[9] U.S. Ragupathy , D. Baskar and A. Tamilarasi , “ New Method of Image Compression using Multiwavelets and Set Partitioning Algorithm” , Proceedings of 10th IEEE International Conference on Industrial and Information Systems , 2008 , pp. 1 - 6 .

[10] R. Sumalatha , M.V. Subramanyam , Medical Image Compression Using Multiwavelets for Telemedicine Applications . International Journal of Scientific & Engineering Research . 2011 , Vol. 2 , № 9, pp. 1 - 4 .

[11] M Ashok and T.B. Reddy , “ Image Compression Techniques Using Modified high quality Multi wavelets ” International Journal of Advanced Computer Science and Applications (IJACSA) , 2011 , Vol. 2 , №7, pp. 153 - 158 .

[12] S. Radhakrishnan and J. Subramaniam , “ Fingerprint Compression using Multiwavelets” , International Journal of Signal Processing , 2006 , Vol. 2 , № 2, pp. 78 - 87 .

[13] Rema N.R , Shanavaz K.T and Mythili P. Better fingerprint image compression at lower bit-rates: an approach using multiwavelets with optimised prefilter coefficients/ ICTACT Journal on Image and Video Processing . 2017 . Vol. 8 ,№ 1, pp. 1588 - 1595 .

[14] N.R. Rema and P. Mythili , Improved fingerprint compression technique with decimated multiwavelet coefficients for low bit rates . ICTACT journal on image and video processing , 2018 , Vol. 9 , № 1, pp. 1801 - 1806 .

[15] N. R. Rema and P. Mythili , Extremely High Compression and Identification of Fingerprint Images Using SA4 Multiwavelet Transform . International Journal of Image and Graphics 2021 ,Vol. 21 , No. 3 , 2150037 , https://doi.org/10.1142/S0219467821500376.

[16] N. M. Mary Sindhuja , T. Prathiba , S. Nisha Rani . Edge Detection of Synthetic Image Using GHM Multiwavelet Transform / International Journal of Computer Applications in Engineering Sciences. 2012 , Vol II , № IV , December, pp. 399 - 403 .

[17] W. A. Mahmoud , Majed E. Alneby , W. Zayer 2D -Multiwavelet Transform 2D-Two Activation Function Wavelet Network Based Face Recognition . Journal of Applied Sciences Research , 2010 , Vol. 6 , №8, pp. 1019 - 1028 .

[18] B. Subramanian , A. Ramasamy and K. Rangasamy . Performance Comparison of Wavelet and Multiwavelet Denoising Methods for an Electrocardiogram Signal . Advances in Mathematical Methods for Image and Signal Processing . 2014 , Article ID 241540. https://doi.org/10.1155/ 2014 /241540.

[19] Hnativ L.O. The method of constructing a family of orthonormal basis systems of fractal multiwavelets based on step functions . Pr. International sh. "Issues of optimization of calculations (POO-HLII) , Kyiv: Institute of Cybernetics National Academy of Sciences , 2015 , P. 37 - 38 .

[20] Hnativ L.O. Fractal step multiwavelets are a new wavelet technology for signal processing and image coding. Theses add . International of science conf. "Modern informatics: problems, achievements and ..." , Ukraine, Kyiv, December 13-15 , 2017 . P. 195 - 197 .

[21] Hnativ L.O. Orthonormal bases of fractal stepped multiwavelets - a new multiwavelet technology for signal and image processing . Physical and mathematical modeling and information technologies . 2021 . No. 32. P. 91 - 95 .

[22] Gonzalez D. , Woods R . Digital Image Processing. 2-nd Edition . 2002 . 793 p.

[23] B.M. Shevchuk , V.K. Zadiraka , L.O. Hnativ , S.V. Fryer Technology of multifunctional processing and transmission of information in monitoring networks . Kyiv. Naukova Dumka . 2010 . 375 p.

[24] ITU-T Rec . H.265|ISO/IEC 23008-2: 2013 . Information technology - High efficiency coding and media delivery in heterogeneous environments - Part 2: High efficiency video coding , 2013 .