# Introduction into the novel two-dimensional discrete orthogonal transforms based on rotation angles/Dvimaciu ortogonaliuju transformaciju, salygojamu sukimosi kampo, tyrimas.

IntroductionIn the IEEE Member Digital Library [1] we can find about a dozen of papers concerning the signal processing based on the rotation angles. We suppose that the cornerstones for the description of discrete orthogonal (orthonormal) transforms are rotation angles of planes in Euclidian space [2]. The angular approach is very well known in linear algebra but it has been used not so often by signal processing people. It seems that H. C. Andrews [3] is a pioneer in the area of parameterization of fast orthogonal (orthonormal) transforms by rotation angles of planes. P. Rieder with colleagues (for example, [4]) use rotation angles in the context of CORDIC-based implementation of orthogonal wavelet transforms and DCT. The pioneer in introducing and using of rotation angle based orthogonal filters is P. P. Vaidyanathan [5]. We avoid here a detailed overview of all available works on rotation angle approach because of the limited space of paper. Such overview is available in [6].

In [2] we introduced several classes of real discrete Rotation Angle Based Orthogonal Transforms (RABOT). These transforms can be interpreted also as a single parametrical transform with infinite number of shapes of basis functions (BFs). On the other hand, we can use rotation angles as the base for different classification schemes of orthogonal transforms [2].

We expect that the use of RABOT transforms could be very promising in signal analysis and synthesis. We are working on that. Particularly, preliminary results show that one of the subclasses of RABOT (in [2] called as CRAIMOT) is very useful for compression of speech. We need a relatively small number of orthogonal functions (sometimes only a few BFs) to represent, for example, the vowels of Latvian speech [7]. Our team works on the development of FPGA-based "angular" devices. Experimental generators [8], analyzers [9] and orthogonal filters [10] are our results in the previous year. We expect an appearance of devices for more wide range applications in the nearest future. Simultaneously with the practical programming of FPGAs we work on the "theory" of angle-based functions (Phi-functions). One of the recent papers deals with a possible generalization of Haar functions [11].

Although our team has issued more than a twenty of papers about Phi-functions during the recent 6 years, this introductory paper is only the first step in the range of "theoretical" works dealing with two-dimensional (2-D) transforms. We do not aim for mathematical perfection and absolute novelty. Some things are well known but some of them appear for the first time.

Basics of two-dimensional orthogonal transforms

The real discrete 2-D Rotation Angle Based Orthogonal Transform (RABOT2D) is closely related to the other real discrete 2-D transforms (Haar, Hartley, Hadamard etc. [12]). It is a separable linear transformation - that is, the 2-D is equivalent to a one-dimensional (1-D) RABOT performed along a single dimension followed by a 1-D RABOT in the other dimension. The definition of the RABOT2D for an input image (signal) X (size of NxN) and output image (spectrum) Y (also size of NxN) is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where x(r,k) and y(r,k) are the value of the element of signal (pixel) and spectrum, respectively. r and k are row and column indexes. [eta](p,q) represents the element of 1-D transform matrix H in p-th row and q-th column. We reduce here and below orthogonal transforms to orthonormal transforms by ignoring the scaling factors that are is usual for such transforms. Such approach simplifies manipulations with formulas.

We can also represent a direct 2-D transform in the matrix form

Y = [(H * [(H * X).sup.T]).sup.T], (2)

where H is a 1-D orthonormal matrix but [(...).sup.T] means the transposition of matrix.

The inverse transform can be presented similarly

X = [([H.sup.T] * [([H.sup.T] * Y).sup.T]).sup.T]. (3)

It is easily to find the equivalent of (1) for the inverse transform, but this is not so significant because for the calculation of orthonormal transforms the fast algorithms can be used.

The inverse transform (3) can be used to calculate the chosen 2-D BF F(r,k), if we assign the 1 to the element [y.sub.0](r,k) of the matrix of all zeros [Y.sub.0]

F(r,k) = [([H.sup.T] * [([H.sup.T] * [Y.sub.0](r,k)).sup.T]).sup.T], (4)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

This assignment means that here has been used only one 2-D spectrum coefficient which corresponds to chosen 2-D BF. If we take into account (5), we can simplify (4)

F(r,k) = [([H.sup.T] * [F.sub.0](r,k)).sup.T] = [F.sup.T.sub.0](r,k) * H, (6)

where [F.sub.0](r,k) is the matrix with the r-th 1-D BF instead of k-th row and all zeros in the other rows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

Finally, the 2-D BF can be expressed as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

where [[eta].sub.p,q] = [eta](p, q).

Fast Algorithms

The 1-D RABOT transform has a fast algorithm (RABFOT) defined as the product of sparse orthogonal (orthonormal) matrices [2]

H = [B.sub.l] * ... * [B.sub.2] * [B.sub.1] = B([phi]l) * ... * B([phi]2) * B([phi]1), l [less than or equal to] n = [log.sub.2](N), (9)

where [B.sub.p] - sparse orthonormal matrix (the Stairs-like Orthonormal Generalized Rotation Matrix (SOGRM) [2])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

where [[tau].sup.l.sub.1,j] [[tau].sup.2.sub.i,j] are 2-element row-vectors which originate from the elementary four-element rotation matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Elements [f.sup.mn.sub.i,j] in (11) present the cosine and sine values of angle [[PHI].sub.ij]. We use shortcuts for the cosine (c) and sine (s) values

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

where G and R geometrically represent the kind of rotation of planes (see [2]). In such a way we can create an infinite number of orthonormal (also orthogonal) transforms by using the rectangular matrix of rotation angles ([2])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

In formula (9) [[phi].sub.p] represents the p-th column-vector of angle matrix [phi]

[[phi].sub.p] = [[[[PHI].sub.1 p], [[PHI].sub.2 p],..., [[phi].sub.N/2p]].sup.T]. (14)

We can define some relations between the elements of angle matrix and get some classes of orthogonal transforms (OT) (see the section about the classification of RABOTs).

We can replace the transform matrix H in (2) and (3) by the product of SOGRM matrices (10) to get the fast version of RABOT2 - RABFOT2. For the direct transform we obtain

Y = [([B.sub.l] *...* [B.sub.2] * [B.sub.1] * [(Bl *...* [B.sub.2] * [B.sub.1] * X).sup.T]).sup.T]. (15)

But, in the case of inverse transform we have

X = ([([B.sub.l] *...* [B.sub.2] * [B.sub.1]).sup.T] * [[([([B.sub.l] *...* [B.sub.2] * [B.sub.1]).sup.T] * Y).sup.T]).sup.T]. (16)

Sometimes for the implementation of [H.sup.T] it is more convenient to use the transposed form of SOGRM matrices

[H.sub.T] = [([B.sub.l] *...* [B.sub.2] * [B.sub.1]).sup.T] = [B.sup.T.sub.1] * [B.sup.T.sub.2] *...* [B.sub.T.sub.l]. (17)

In the case of the generation of single 2-D BF ((6)) it is also possible to get the benefit of the number of operations used for the generation of BF by the allocation of SOGRMs

F(r,k) = [F.sup.T.sub.0](r,k) * [B.sub.l] *...* [B.sub.2] * [B.sub.1]. (18)

Classes of RABOT2 transforms

Each reader can create his own novel class of transform by choosing restrictions on the angle matrix (13). It is possible also to define 2-D RABOT (RABOT2) similar to the 1-D RABOT [2]. We will limit our efforts to a preliminary short description of RABOT2 only (see Table 1).

Shapes of BFs

We can get an infinite number of shapes of BFs by a simple change of angles in matrix (13). In such a way, for example, the angle matrix (for N= [2.sup.3]) with a triangle structure and two different values ([pi]/6, [pi]/4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

gives the set of BFs which are shown in Fig. 2.

[FIGURE 1 OMITTED]

It is possible also to define the a 2-D version of generalized Haar-like functions [11] for the angle matrix with zeros in the lower right corner

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

Corresponding BFs are shown in Fig. 3

[FIGURE 2 OMITTED]

Number of Operations for the Calculation of RABOT2

In the case of practical implementation of RABOT2 the estimation of the number of arithmetical operations is of primary importance.

1. Number of Operations for the Direct Calculation. The formula (1) or (2) can be used to estimate the number of multiplications and summations. We have NxN=[N.sup.2] 2-D BFs or the same number of spectrum coefficients. For the calculation of spectrum we need.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

where [n.sub.mult2D] - the number of multiplications, [n.sub.sum2D] - the number of additions, but [n.sub.op2D] - the total number of operations. It is evident that such a number of operations is practically senseless (e.g. [12]). We need close to 8 millions (8355840) operations for a gray scale picture with resolution of 128x128 pixels.

2. Number of Operations for the Fast Calculation. As mentioned above, the sparseness of [B.sub.j] in (10) ensures a fast algorithm for the calculation of RABOT. The total number of mathematical operations for the calculation of fast transform (FT) by using (15) or (16) may be easily found. Matrices [B.sub.j] contain mainly zeros. There are only two elements per column and per row which are not equal to zero. A single elementary rotation takes four multiplications and two summations in general case. We have N/2 rotations per each SOGRM and we must perform these rotations on each of N columns of the transformed matrix (in the first step - on the signal/spectrum X/Y matrix). The mentioned operations must be repeated 2x l times.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

where [n.sub.mult 2D FT] - the number of multiplications for FT, [n.sub.sum 2D FT] - the number of additions for FT, but [n.sub.op 2D FT] - the total number of operations for FT. The improvement of performance is almost 10000 times for the example from the previous subsection (a picture with resolution of 128x128 pixels).

In the case of CORDIC implementation of rotations it is possible to reduce the number of operations to

[n.sub.oprot 2D FT] = l * [N.sup.2] [less than or equal to] [log.sub.2](N) * [N.sup.2]. (23)

3. Number of Operations for the Generation of BF. Our experience with 2-D signals shows that sometimes for the synthesis of signals are necessary only a few BFs. In this case FT can be slower as the direct calculation. We expect that a similar situation could occur with 2-D signals too. In such a context the estimation of the number of operations needed for the calculation of standalone 2-D BF could be important. From (18) we see that NxN multiplications are necessary in the final stage (multiplication by [F.sub.0]). The number of multiplications increases in a geometrical progression for the sequence of terms [B.sub.j] when going leftward through the factorized matrices

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (24)

4. Comparison of the Number of Operations. The next figure shows the results obtained by formulas (22)-(24).

[FIGURE 3 OMITTED]

This result indicates that for the calculation of single BF we need a relatively large number of operations when comparing it with the number of operations needed for FT.

Analyzer-Synthesizer-Generator

The main practical result of this work is a MATLAB based tool called as "Analyzer-Synthesizer-Generator" (ASG). This initial tool is very useful for 2-D Phi-Function generation (BFS). ASG is also very handy for image analysis and synthesis and can be used for educational and research goals. ASG allows the import of images from different sources and displays them in the left window of GUI desktop (Fig. 4). In dependence of the state of control this window shows also spectrum image, set of BFs, synthesized image and 1D transform matrix. The right part of desktop is used for setting the angles, but the lower part is allocated for the tool control. In the recent version (look for next papers) the tool is equipped with the automatic search of optimal transform (i.e. angle matrix) for a given image, and it is targeted on the development of optimal image compression algorithms.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Conclusions

This is an introductory work offering a compact, on rotation angles based description of existing and new classes of fast 2-D orthogonal transforms.

In our opinion the angle-based approach provides.

* unified fast algorithm for the synthesis of novel 2-D parametrical orthogonal transforms,

* new schemes of classification and comparison of existing and novel 2-D orthogonal transforms,

* new techniques for analysis and synthesis of 2-D signals - to a much wider extent the image processing possibilities than in the case of wavelets,

* promising 2-D signal compression algorithms,

* promising 2-D signal filtering algorithms.

Acknowledgments

This work has been partly supported by the project 09.1552 (the Council of Science of Latvia), by the European Social Fund doctoral scholarship support project (EU) and by the National Research Program "Innovative signal processing technologies for development of smart and efficient electronic systems" (the Ministry of Education and Science). We are also very thankful to Andra Martinsone for collaboration and help.

References

[1.] Aboltins A. Comparison of Orthogonal Transforms for OFDM Communication System // Electronics and Electrical Engineering.--Kaunas. Technologija, 2011.--No. 5(111). P. 77-80.

[2.] Misans P., Terauds M Introduction into the fast orthogonal transforms based on rotation angles - part I. A new methodical approach only or a gateway to novel DSP algorithms? // Proc. of the 5th Electronic Circuit and Systems Conference (ECS'05).--Slovakia, Bratislava, 2005.--P. 8594.

[3.] Andrews H. C. Multidimensional rotations in feature selection // IEEE Transactions On Computers, 1971.--Vol. 18.--No. 5.--P. 1045-1051.

[4.] Rieder P., Goetze J., Nossek J. A., Burrus C. S., Parameterization of orthogonal wavelet transforms and their implementation // IEEE Transactions On Circuits And Systems--II. Analog And Digital Signal Processing, 1988. Vol. 45.--No. 2.--P. 217-226.

[5.] Vaidyanathan P. P. A unified approach to orthogonal digital filters and wave digital filters, based on LBR two-pair extraction // IEEE Transactions On Circuits And Systems, 1985.--Vol. CAS-32.--No. 7.--P. 673-686.

[6.] Terauds M. Generation of discrete fast orthogonal transforms, Ph.D. dissertation.--Faculty of Electronics and Telecommunications, Riga Technical University, 2009.

[7.] Valters G., Misans P. Initial version of FPGA-based CRAIMOT basis functions generator // Proc. of the 14th IEEE International Conference Mixed Design of Integrated Circuits and Systems (MIXDES 2007).--Ciechocinek, Poland, 2007.--P. 632-637.

[8.] Misans P., Terauds M., Valters G., Derums U., Vasilevskis N. FPGA-based CRAIMOT basis function generator // Proc. of the 25th IEEE Norchip Conference. Aalborg, Denmark, 2007.

[9.] Misans P., Valters G. Initial version of FPGA-based CRAIMOT spectrum analyzer// Proc. of the 6th Electronic Circuits and Systems Conference (ECS'07).--Bratislava, Slovakia, 2007.-- P. 159-164.

[10.] Misans P., Valters G. Introduction into the parametrical decomposition-reconstruction filters based on Haar-like orthonormal transforms // Proc. of the 6th Electronic Circuits and Systems Conference (ECS'07).--Bratislava, Slovakia, 2007.--P. 107-112.

[11.] Misans P. Introduction into the Haar like transforms based on rotation angles // Scientific Proc. of Riga Technical University, Telecommunications and Electronics.--Riga, RTU, 2007.--Vol. 7.--P. 6-13.

[12.] Jain A. K. Fundamentals of digital image processing. Englewood Cliffs, NJ, Prentice Hall, 1989.--153 p.

Received 2011 02 15

P. Misans, U. Derums

Faculty of Electronics and Telecommunications of Riga Technical University, Azenes iela 12, LV-1048, Riga, Latvia, phone: ?+371-9-135-489, fax: ?7-08-92-92, e-mail: name.family@rtu.lv

Table 1. Description of RABOT2 Transform RABOT - Rotation Angle [[phi].sub.ij] = [[phi].sub.ij] Based OT CRAOT - Constant Rotation [[phi].sub.ij] = [phi] Angle OT CRAIMOT - Constant Rotation Angle Inside [[phi].sub.ij] = [[phi].sub.i] Matrix OT CRMOT - Constant Rotation Matrix OT [[phi].sub.ij] = [[phi].sub.j] RAHT - Rotation Angle-based Haar-like see [11] Transforms Transform Comments RABOT - Rotation Angle angles in (13) are different Based OT all angles are equal CRAOT -- Constant Rotation Angle OT CRAIMOT - Constant all rows in (13) are Rotation Angle Inside equal (one constant Matrix OT angle per B) CRMOT - Constant all columns in (13) are Rotation Matrix OT equal (all B matrices are equal) RAHT -- Rotation angle matrix has a Angle-based Haar-like triangle structure with Transforms constant value angle in the right lower corner

Printer friendly Cite/link Email Feedback | |

Title Annotation: | SIGNAL TECHNOLOGY/SIGNALU TECHNOLOGIJA |
---|---|

Author: | Misans, P.; Derums, U. |

Publication: | Elektronika ir Elektrotechnika |

Article Type: | Report |

Geographic Code: | 4EXLA |

Date: | Jun 1, 2011 |

Words: | 2811 |

Previous Article: | Three-Dimensional cell counting based on two dimensional cross-section images/Trimaciu lasteliu apskaiciavimas taikant dvimaciu vaizdu skersinius... |

Next Article: | Automated regression testing using symbolic execution/Programines irangos regresinis testavimas naudojant simbolinius vyksmus. |

Topics: |