146 Rational Wavelet Transform with Reducible Rational Dilation Factor © Oleg Chertov1[0000-0003-0087-1028] and © Volodymyr Malchykov1[0000-0002-1710-9171] 1 National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine mavr2k@gmail.com Abstract. Wavelet analysis is very effectively used in analysis of different types of data. Mostly often dyadic wavelet transforms are used. But non-dyadic wavelet transforms allow more accurate determination of data features. Com- monly used value of dilation factor for rational wavelet transforms is an irre- ducible fraction. In this paper we will show on an example that for reducible fraction as a dilation factor perfect reconstruction condition is satisfied. Keywords: Wavelet Transform, Non-Dyadic Wavelet, Dilation Factor. 1 Introduction 1.1 Wavelet Transform Wavelet transform (WT) is a very powerful tool for analyzing the data of different nature. Unlike Fourier analysis WT gives as a result time-frequency representation of source signal. Wavelet analysis has shown its efficiency in various areas, such as image and vid- eo processing, data compression and noise reduction, solving of partial differential equations, speech recognition, processing of Electroencephalography (EEG), Elec- tromyography (EMG), Electrocardiography (ECG) signals, etc. [1-4] 1.2 Dyadic and Non-dyadic Wavelet Transform Discrete wavelet transform is characterized by its dilation factor. It was shown [5] that as a value of dilation factor any real number greater than one can be taken. If dilation factor equals 2 the discrete WT is called dyadic, otherwise non-dyadic. Usually dyadic WT is used due to its simple and effective implementation. But in the case when signal singularities will be located in adjoined frequency intervals the re- sults of dyadic WT will not be eligible. Thus, it will be better to select frequency in- tervals in a way that they would cover such singularities. For example, non-dyadic WT are more suitable for flexible decompositions of the data [6], non-dyadic scale ratios [7], non-dyadic frequency divisions [8], or constructing non-tensor-based multi- D wavelets with coset sum method [9]. Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 147 Various approaches to non-dyadic WT were proposed by different authors. Bratteli and Jorgensen [10] proposed a method based on the construction of the set mapping to Kunzh’s algebra representation. In their approach task of non-dyadic WT filters choice reduces to unitary matrix construction. As a dilation factor only a natu- ral number greater than one can be selected. Pollock and Cascio [8] proposed a method for construction of packet WT with a possibility of a dilation factor choice through each level of decomposition. They gen- eralized dyadic WT packet technique, where each frequency range at each step of wavelet decomposition is divided into two intervals. Main idea was to divide range into p intervals, where p is an arbitrary prime number. There can be cases where integer dilation factor is not enough. Auscher [11] gave the formal definition of a rational multiresolution analysis and specified the method of corresponding orthogonal wavelet bases construction. Using his ideas, Baussard, Nicolier and Truchetet [12] developed a fast pyramidal algorithm for WT coefficients construction in a case of a rational dilation factor. Thus, they gave a generalization of the Malla algorithm for dyadic case. Also, there are some works that deal with using of irrational dilation factors. One of the first was Feauveau [13], where the value of dilation factor was √2. 1.3 Rational Wavelet Transform The most general and effective approach for non-dyadic WT is rational multiresolu- tion analysis proposed in [11] and [12]. In this approach dilation factor N is equal to a rational number p/q. At each level of wavelet decomposition, we get one approximation component and (p – q) detail com- ponents. Rational multiresolution analysis filters construction is carried out in the frequency domain. Wavelet decomposition pyramidal algorithm with a rational dila- tion factor is also transferred to the frequency domain. 2 Problem Formulation The main advantage of non-dyadic wavelet transform is that it can provide more pre- cise separation of signal components. Very often the irreducible dilation factor is used for such decomposition. Commonly its value is taken 3/2. The purpose of this work is to show that as value of the dilation factor for rational wavelet transform a reducible fraction 6/4 can be taken and this will allow getting the more precise detection of signal singularities. Also, authors will show that perfect reconstruction condition is satisfied for this case. 148 3 Problem Solution 3.1 Conditions for Building Filters In order to build filters for rational wavelet transform with dilation factor 6/4 we will use the approach described in [5] for case 3/2. We have function 6 𝜑 ∈ 𝑉 𝑉 = 𝑆𝑝𝑎𝑛 𝜑 ∙ −𝑛 4 so, that 𝜑 𝑥 = ∑ ℎ 𝜑 𝑥−𝑛 (1) 6 6 6 6 𝜑 𝑥 − 4𝑙 = ℎ 𝜑 𝑥 − 4𝑙 − 𝑛 = ℎ 𝜑 𝑥 − 6𝑙 − 𝑛 = 4 4 4 4 6 6 = ℎ 𝜑 𝑥−𝑘 4 4 This set of functions has to be orthonormal 𝛿 = 〈𝜑 𝑥 , 𝜑 𝑥 − 4𝑙 〉 = 𝜑 𝑥 ∙ 𝜑 𝑥 − 4𝑙 𝑑𝑥 = ℝ 6 6 6 6 = ℎ 𝜑 𝑥−𝑛 ℎ 𝜑 𝑥−𝑘 𝑑𝑥 4 4 4 4 ℝ 6 6 6 = ℎ ℎ 𝜑 𝑥 − 𝑛 ∙ 𝜑 𝑥 − 𝑘 𝑑𝑥 = ℎ ℎ 4 4 4 ℝ So, orthonormality of the 𝜑 ∙ −4𝑙 implies the condition ℎ ℎ =𝛿 On the other hand, 𝜑 𝑥 − 1 is also in V0, and therefore can also be written as 𝜑 𝑥−1 = ∑ ℎ 𝜑 𝑥−𝑛 (2) 149 6 6 6 6 𝜑 𝑥 − 4𝑙 − 1 = ℎ 𝜑 𝑥 − 4𝑙 − 𝑛 = ℎ 𝜑 𝑥 − 6𝑙 − 𝑛 = 4 4 4 4 6 6 = ℎ 𝜑 𝑥−𝑘 4 4 Set of functions 𝜑 ∙ −1 also has to be orthonormal. 𝛿 = 〈𝜑 𝑥 − 1 , 𝜑 𝑥 − 4𝑙 − 1 〉 = 𝜑 𝑥 − 1 ∙ 𝜑 𝑥 − 4𝑙 − 1 𝑑𝑥 = ℝ 6 6 6 6 = ℎ 𝜑 𝑥−𝑛 ℎ 𝜑 𝑥−𝑘 𝑑𝑥 4 4 4 4 ℝ 6 6 6 = ℎ ℎ 𝜑 𝑥 − 𝑛 ∙ 𝜑 𝑥 − 𝑘 𝑑𝑥 = ℎ ℎ 4 4 4 ℝ Also, it has to be orthogonal to the previous set of functions. 0 = 〈𝜑 𝑥 − 1 , 𝜑 𝑥 − 4𝑙 〉 = 𝜑 𝑥 − 1 ∙ 𝜑 𝑥 − 4𝑙 𝑑𝑥 = ℝ 6 6 6 6 = ℎ 𝜑 𝑥−𝑛 ℎ 𝜑 𝑥−𝑘 𝑑𝑥 4 4 4 4 ℝ 6 6 6 = ℎ ℎ 𝜑 𝑥 − 𝑛 ∙ 𝜑 𝑥 − 𝑘 𝑑𝑥 = ℎ ℎ 4 4 4 ℝ So, orthonormality of the 𝜑 . −4𝑙 − 1 and its orthogonality of the 𝜑 . −4𝑙 − 1 with the respect to 𝜑 . −4𝑙 give us such two conditions ℎ ℎ =𝛿 ℎ ℎ =0 Repeating the similar operations for functions 𝜑 𝑥 − 2 and 𝜑 𝑥 − 3 150 𝜑 𝑥−2 = ∑ ℎ 𝜑 𝑥−𝑛 (3) 𝜑 𝑥−3 = ∑ ℎ 𝜑 𝑥−𝑛 and taking into account orthogonality and orthonormality properties will bring us to the conditions ℎ ℎ =𝛿 ℎ ℎ =0 ℎ ℎ =0 ℎ ℎ =𝛿 ℎ ℎ = ℎ ℎ = ℎ ℎ = Now, we will introduce auxiliary functions. Let’s denote by 𝜑 𝜔 the Fourier trans- form of function 𝜑 𝑥 . Then, applying the Fourier transform to (1), we will get 6 4 4 4 4 𝜑 𝜔 = ℎ 𝜑 𝜔 𝑒 = ℎ 𝑒 ∙𝜑 𝜔 4 6 6 6 6 We can rewrite last expression as 𝜑 𝜔 =𝑚 𝜔 ∙𝜑 𝜔 (4) where 𝑚 𝜔 is defined as 4 𝑚 𝜔 ≡ ℎ 𝑒 6 In the same way we can define the function 𝑚 𝜔 . Applying the Fourier transform to (2) will give us 151 6 4 4 4 4 𝜑 𝜔 𝑒 = ℎ 𝜑 𝜔 𝑒 = ℎ 𝑒 ∙𝜑 𝜔 4 6 6 6 6 𝜑 𝜔 𝑒 =𝑚 𝜔 ∙𝜑 𝜔 (5) where 4 𝑚 𝜔 ≡ ℎ 𝑒 6 After applying the same operations to functions (3) we will get 𝜑 𝜔 𝑒 =𝑚 𝜔 ∙𝜑 𝜔 (6) 𝜑 𝜔 𝑒 =𝑚 𝜔 ∙𝜑 𝜔 (7) where 4 𝑚 𝜔 ≡ ℎ 𝑒 6 4 𝑚 𝜔 ≡ ℎ 𝑒 6 Similar to [5] we can also define two wavelet functions 6 6 𝜓 𝑥 = 𝑔 𝜑 𝑥−𝑛 4 4 6 6 𝜓 𝑥 = 𝑔 𝜑 𝑥−𝑛 4 4 Properties of their orthonormality, mutual orthogonality and orthogonality with previ- ously defined functions ϕ give us the next conditions 𝑔 𝑔 =𝛿 𝑔 𝑔 =𝛿 𝑔 ℎ =0 𝑔 ℎ =0 152 𝑔 ℎ =0 𝑔 ℎ =0 𝑔 ℎ =0 𝑔 ℎ =0 𝑔 ℎ =0 𝑔 ℎ =0 𝑔 𝑔 =0 Also, we get another two necessary functions 𝑚  and 𝑚  4 𝑚 𝜔 = 𝑔 𝑒 6 4 𝑚 𝜔 = 𝑔 𝑒 6 3.2 Perfect Reconstruction Conditions According to [5], received conditions for filters coefficients are equivalent to the uni- tarity of matrix 𝑚 𝜔 𝑚 𝜔 𝑚 𝜔 𝑚 𝜔 𝑚 𝜔 𝑚 𝜔 ⎛𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ ⎞ ⎜ ⎟ ⎜𝑚 𝜔 + 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ ⎟ ⎜ ⎟ ⎜𝑚 𝜔 + 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ ⎟ ⎜ ⎟ ⎜𝑚 𝜔 + 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ ⎟ ⎝𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ 𝑚 𝜔+ ⎠ (8) Li [14] proved that perfect reconstruction condition is satisfied for the case of the irreducible dilation factor and showed two examples of wavelet basis. In [10] the extension of Littlewood-Paley wavelet basis to the rational case was in- troduced. Both the scale function and wavelet functions in this case are defined in Fourier domain by next formulas: 153 𝑞∙𝜋 𝑞∙𝜋 1 𝑓𝑜𝑟 − ≤𝜔< |𝜑 𝑁𝜔 | = 𝑝 𝑝 0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒 𝑞+𝑚−1 ∙𝜋 𝑞+𝑚 ∙𝜋 𝜓 𝑁𝜔 = 1 𝑖𝑓 ≤ |𝜔| < 𝑝 𝑝 0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒 where 𝑁 = and 𝑚 = 1, … , 𝑝 − 𝑞. We will consider this wavelet basis for the case of reducible fraction 6/4 and check that perfect reconstruction condition will be satisfied. If 𝑁 = then scale function can be taken as 6 4𝜋 𝜑 𝜔 = 1 𝑖𝑓 |𝜔| ≤ 6 4 0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒 or 1 𝑖𝑓 |𝜔| ≤ π 𝜑 𝜔 = 0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒 Wavelet functions can be defined as 6 4𝜋 5𝜋 𝜓 𝜔 = 1 𝑖𝑓 ≤ |𝜔| < 4 6 6 0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒 6 5𝜋 𝜓 𝜔 = 1 𝑖𝑓 ≤ |𝜔| < π 4 6 0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒 According to the (4) – (7) we can write 6 𝜔 𝜑 𝑚 𝜔 = 4 𝜑 𝜔 6 𝜔𝜑 𝑚 𝜔 = 4 ∙𝑒 ∙ 𝜑 𝜔 6 𝜔𝜑 𝑚 𝜔 = 4 ∙𝑒 ∙ 𝜑 𝜔 6 𝜔𝜑 𝑚 𝜔 = 4 ∙𝑒 ∙ 𝜑 𝜔 154 Similarly, we get 6 𝜓 𝜔 m 𝜔 = 4 𝜑 𝜔 6 𝜓 𝜔 m 𝜔 = 4 𝜑 𝜔 After substituting the above expressions into the matrix (8) direct check allows us to verify that the condition of perfect reconstruction, given in [14], will be also satisfied for the case of reducible fraction 6/4. 3.3 Experimental Results In order to illustrate that using of the reducible dilation factor can lead to more precise identifying of signal singularities we will take a look at the example which is based on model data. This mode data is the sum of three sinusoidal signals (see Fig. 1). Fig. 1. Model signal Fourier spectrum of this model signal contains three peaks in frequency domain, that fall into the following frequency ranges (see Fig.2 ): • first signal (S1) – from 2π/3 to 5π/6 155 • second signal (S2) – from 0 to 2π/3 • third signal (S3) – from 5π/6 to π Fig. 2. Fourier spectrum of signal When using the dilation factor 3/2 frequency range is divided into two parts – from 0 to 2π/3 for approximation component and from 2π/3 to π for detail component. Due to this rational wavelet transform will separate signal S2 (see Fig.3. Approximation component), but signal S1 and S3 will be mixed (see Fig.3. Detail component). 156 Fig. 3. Decomposition of model signal with dilation factor 3/2 But, if we take dilation factor 6/4 then frequency range is divided into three parts – again from 0 to 2π/3 for approximation component, but now from 2π/3 to 5π/6 for the first detail component and from 5π/6 to π for the second detail component. Thus, in this case all three source signals will be separated (see Fig. 4). So, for this model signal the use of dilation factor 6/4 is preferable, since it allows separation of all three components from the original signal. 157 Fig. 4. Decomposition of model signal with dilation factor 6/4 4 Conclusions Authors proposed to use reducible rational dilation factor 6/4 except most often used 3/2. It was shown that for this value of dilation factor perfect reconstruction condi- tions are satisfied. An example shows that using dilation factor 6/4 allows more pre- cise separation of signal singularities. Further researches have to be done in order to generalize the results to the case of arbitrary reducible dilation factor. 158 References 1. Rhif, M., Ben Abbes, A., Farah, I.R., Martinez, B., Sang, Y.: Wavelet Transform Applica- tion for/in Non-Stationary Time-Series Analysis: A Review. Applied Science 9, 1345, (2019). 2. Hussain, L., Aziz, W.: Time-Frequency Wavelet Based Coherence Analysis of EEG in EC and EO during Resting State. International Journal of Information Engineering and Elec- tronic Business 7(5), 55–61, (2015). 3. Yazdani, H.R., Nadjafikhah, M., Toomanian, M.: Solving Differential Equations by Wave- let Transform Method Based on the Mother Wavelets & Differential Invariants. Journal of Prime Research in Mathematics 14, 74-86 (2018). 4. Vishwa, A., Sharma, S.: Modified Method for Denoising the Ultrasound Images by Wave- let Thresholding. International Journal of Intelligent Systems and Applications 4(6), 25– 30, (2012). 5. Daubechies, I.: Ten Lectures on Wavelets. SIAM (1992). 6. Gupta, C., Lakshminarayan, C., Wang, S., Mehta, A.: Non-dyadic haar wavelets for streaming and sensor data. In: 2010 IEEE 26th International Conference on Data Engineer- ing, pp. 569–580. (2010). 7. Xiong, R., Xu, J., Wu, F.: A lifting-based wavelet transform supporting non-dyadic spatial scalability. In: 2006 IEEE International Conference on Image Processing, pp. 1861–1864. (2006) 8. Pollock, D.S.G., Cascio, I.L.: Non-dyadic wavelet analysis. In: Kontoghiorghes, E.J., Ga- tu, C. (eds.) Optimization, Econometric and Financial Analysis: Advances In Computa- tional Management Science, vol. 9, pp. 167–204 (2007). 9. Hur, Y., Zheng, F.: Prime Coset Sum: A Systematic Method for Designing Multi-D Wave- let Filter Banks With Fast Algorithms. IEEE Transactions on Information Theory 62(11), 6580–6593 (2016). 10. Bratteli, O., Jorgensen, P.E.T.: Isometrics, shifts, Cuntz algebras and multiresolution wavelet analysis of scale N. Integral Equations Operator Theory 28(4), 382–443 (1997). 11. Auscher, P. Wavelet bases for L2(R) with rational dilation factor. In: Ruskai, M.B. et. al. (eds.) Wavelets and their Applications. Jones and Barlett (1992). 12. Baussard, A., Nicolier, F., Truchetet, F.: Rational multiresolution analysis and fast wavelet transform: application to wavelet shrinkage denoising. Signal Processing 84(10), 1735– 1747 (2004). 13. Feauveau, J.-C.: Analyse multiresolution avec un facteur de résolution √2. J. Traitement du Signal 7(2), 117–128 (1990). 14. Li, Z.: Orthonormal wavelet bases with rational dilation factor based on MRA. In: 7th In- ternational Congress on Image and Signal Processing, pp. 1146-1150. IEEE, China (2014).