# New Orthogonal Transforms for Signal and Image Processing
## 5 Proposed Orthogonal Transform and Its Modifications
### Two-Dimensional (2D) Transform  
This case applies to two-dimensional signals represented by the square matrix \(X(i,j)\) of \(N\) dimensions, \(N=2^{n}\), \(i=1,\;2,\;3,\;\ldots,\;N\), \(j=1,\;2,\;3,\;\ldots,\;N\), which is mainly associated with image processing. In the general case a 2D transform has the form:  
\[\text{FT:}\qquad S(i,j) =A(n)\cdot X(i,j)\cdot A(n) \tag{25}\] \[\text{IT:}\qquad X(i,j) =\frac{1}{C^{2}}\cdot A(n)\cdot S(i,j)\cdot A(n)\]  
where  
\(S(i,j)\)--matrix of spectral components. \(X(i,j)\)--matrix of 2D signal. \(A(n)\)--transform matrix described by Equation (15). C--constant described by Equation (16). It is seen that the forward and inverse transforms have the same structure--they differ only in the constant \(C\). The 2D transform can be calculated directly using Equation (24) or by grouping the channels as shown in Figure 3e,f. The transform matrix \(A(n)\) consists of the power of parameter \(a\). For \(a=1\) we obtain the 2D Walsh-Hadamard transform. It is obvious that if the transform (25) is used for image processing we are dealing with large values of \(N\). For this reason, large powers of parameter \(a\
eq 1\) may not be calculated by a computer. Thus, it seems purposeful to propose a sparse matrix \(A_{m}(n)\) with the following form:  
\[A_{m}(n)= \begin{bmatrix}A(m)&0&0&\cdots&0\\ 0&A(m)&0&\cdots&0\\ 0&0&A(m)&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&A(m)\end{bmatrix} \] (26a) where \[A_{m}(n)\]--matrix with dimension \[N=2^{n}\], \[n=2,3,4,\ldots\] \[A(m)\]--matrix ( 15 ) or ( 4 ) with dimension, \[M=2^{m}\], \[m=1,\;2,\;3,\;\ldots\], \[m<n\]. For example, for the parameters \(n=3\), \(m=2\) the matrix \(A_{2}(3)\) is:  
\[A_{2}(3)= \begin{bmatrix}\cdot\begin{pmatrix}A(2)\\ \vdots\\ \cdots\\ \vdots\\ A(2)\end{pmatrix}\cdot\end{bmatrix}  \tag{26b}\]  
where \(A(2)\) is defined either by (2) or (17b). It is seen that like \(A(n)\) matrix \(A_{m}(n)\) is symmetric and orthogonal, so we have:  
\[A_{m}(n)=A_{m}^{T}(n)\,\ A_{m}(n)\cdot A_{m}^{T}(n)=C\cdot I \tag{27}\]  
\[A_{m}^{-1}(n)=A_{m}^{T}(n)\,\ I\ \mbox{--unit matrix}\]  
\[\mbox{where}\quad C=\sum_{i=1}^{2^{n}}a^{2i} \tag{28}\]  
The matrix \(A_{m}(n)\) consists of many zeros, defined by:  
\[L_{0}=N\cdot(N-M) \tag{29}\]  
The percentage ratio of the number of zeros to all elements of the matrix \(A_{m}(n)\) is as follows:  
\[\frac{L_{0}}{L_{total}}=\frac{N\cdot(N-M)}{N^{2}}=(1-\frac{M}{N})\cdot 100\% \tag{30}\]  
For instance, if \(M=4,N=512\), more than 99% of the transform matrix \(A_{2}(9)\) elements are zeros. Matrix (26a) can therefore be used as a transform matrix for the following transform, which is a modified version of transforms (23) and (25) using submatrices \(A(m)\). \[ \begin{array}{c}\mbox{1D Transform:}\\ \mbox{FT:}\qquad S(n)=A_{m}(n)\cdot X(n)\\ \mbox{IT:}\qquad X(n)=\frac{1}{C}\cdot A_{m}(n)\cdot S(n)\\ \mbox{2D Transform:}\\ \mbox{FT:}\qquad S(i,j)=A_{m}(n)\cdot X(i,j)\cdot A_{m}(n)\\ \mbox{IT:}\qquad X(i,j)=\frac{1}{C^{2}}\cdot A_{m}(n)\cdot S(i,j)\cdot A_{m}(n )\end{array}  \tag{31}\]  
\(C\) is defined by Equation (28). Transforms (31) and (32) with many zeros can be treated as a specific case of compression in the spatial domain. Calculating modified orthogonal transforms using sparse matrices expressed by (31) and (32) is not only simple but can also provide very fast calculations. However, this is the subject considered in the next section. It is obvious that instead of using matrices (15) in all of the proposed orthogonal transforms (23), (25), (31) and (32) we can also use the symmetric and orthogonal matrix (4) as the transform matrix. In this case, we can consider different versions of the orthogonal transforms, in particular the transforms described by Equations (31) and (32) for which the submatrices \(A(m)\) are the same or different. It was shown that each submatrix \(A(m)\) of the matrix \(A_{m}(n)\) is defined by the first three values of the basis sequence.