Multi-Dimensional Rajan Transform K. Thiagarajan ? , Manish Prateek ? & Ethirajan Govindarajan ? g(i) =x(i)+x(i+N/2) ; 0?j?N/2; 0?i?N/2 h(j) =|x(i)-x(i-N/2)| ; 0?j?N/2; 0?i?N/2 Now each (N/2) point segment is further divided into two halves each consisting of N/4 points so that the following holds good. g1(k)=g(i)+g(j+(N/4)); 0?k?(N/4); 0?j?(N/4) g2(k)=|g(i)-g(i-(N/4)| ; 0?k?(N/4 ) ; (N/4)?j?(N/2) h1(k)=h(j)+h(j+(N/4)); 0?k?(N/4); 0?j?(N/4) h2(k)=|h(j)-h(j-N/4)| ; 0?k?(N/4); 0?j?(N/4) This process is continued until no more division is possible. The total number of stages thus turns out to be log 2 N. Let us denote the sum and difference operators respectively as '+' and '~'. Then the signal flow graph for the Rajan Transform of a number sequence of length 16 would be of the form shown in Fig. 1. If x(n) is a number sequence of length N=2 k ; k>0, then its Rajan Transform(RT) is denoted as X(k). RT is applicable to any number sequence and it induces an isomorphism in a class of sequence, that is, it maps a domain set consisting of the cyclic and dyadic permutations of a sequence on to a range set consisting of sequence of the form X(k)E(r) where X(k) denotes the permutation invariant RT and E(r) an encryption code corresponding to an element in the domain set. This map is a one-to-one and on to correspondence and an inverse map also exists. Hence, it is viewed as a transform. Fig. 1 shows a functional block diagram of a 16-point Rajan Transform algorithm.

It is to be noted that the map x(n) â??" X(k)E(r) is an isomorphic map, and the map x(n) ? X(k) is a homomorphic map. The inverse function is called Inverse Rajan Transform and is applicable to cases where Rajan Transform is considered as an isomorphic function. Homomorphic functions do not have inverse functions. The operation of Inverse Rajan Transform is not explained here in this paper for lack of space and for its irrelevance in the formulation of multi-dimensional Rajan Transforms. Apart from multi-dimensional Rajan Transforms, which are conceptual extensions of onedimensional Rajan Transform, one can as well develop notions like "Set-Theoretic Rajan Transform" which are higher order algebraic tools that work on sequences of sets, functions and relations. These formulations are not in the scope of this paper and thus they are not presented.


# Introduction

ajan transform essentially operates on a number sequence, whose length is a power of two. It transforms any sequence of arbitrary numbers into a sequence of interrelated numbers. The resulting sequence is called 'Rajan Spectrum'. More precisely,Rajan Transform is a homomorphic map that yields the same Rajan Spectrum for an input sequence and all of its permuted versions. The definition and various outcomes of One-Dimensional Rajan Transform (1D-RT) are extended to multi-dimensional case. Onedimensional Rajan Transform is briefly explained on a need to have basis.


# Definition of Rajan Transform

Rajan Transform is essentially a fast algorithm developed on the lines of Decimation-In-Frequency Fast Fourier Transform algorithms, but it is functionally different from the DIF-FFT algorithm. Given a number sequence x(n) of length N, which is a power of 2, first it is divided into the first half and the second half each consisting of (N/2) points so that the following holds good. As outlined earlier, one can implement twodimensional Rajan Transformin two different ways: (i) Row-Column method and (ii) Column-Row method. As stated previously, 2D Rajan Spectrum obtained using first method need not be the same as the spectrum obtained using second method. This could be verified with the help of an example. Consider a two dimensional array
A = [x(m,n)]. 0 0 0 0 A = [x(m,n)] = 1 1 1 0 0 1 0 0 0 1 0 0 2D-RT obtained using Row-Colum method
The RT spectra of the four rows of the array A are the four rows given in the array [X r (g,h)]
0 0 0 0 [X r (g,h)] = 3 1 1 0 1 1 1 1 1 1 1 1
Next, the RT spectra of the four columns in the array [X r (g,h)] are given in the columns of the array [X r,c (k 1 ,k 2 )], which is the 2D-RT of the given array A.
5 3 3 3 [X r,c (k 1 ,k 2 )] = 3 1 1 1 3 1 1 1 1 1 1 1 2D-RT obtained using Column-Row method
The RT spectra of the four columns of the array A are the four columns given in the array [X c (g,h)]
1 3 1 0 [X c (g,h)] = 1 1 1 0 1 1 1 0 1 1 1 0
Next, the RT spectra of the four rows in the array [X c (g,h)] are given in the rows of the array [X c,r (k 1 ,k 2 )], which is the 2D-RT of the given array A.
5 1 3 [X c,r (k 1 ,k 2 )] = 3 1 1 3 1 1 3 1 1
With reference to the example presented above, it is proved that [X r,c (k 1 ,k 2 )] ? [X c,r (k 1 ,k 2 )] in this case. However, one can verify that [X r,c (K 1 ,k 2 )] = [X c,r (k 1 ,k 2 )] for symmetric arrays. In order to do this, let us consider Hilbert matrix H 4 and obtain 2D-RT spectra using both methods.

1 2 3 4
H 4 = [x(m,n)] =
2 3 4 5 3 4 5 6 4 5 6 7

The 2D-RT spectra of H 4 obtained using Row-Column method is X r,c (k 1 ,k 2 ) and it is shown below.
64 08 16 [X r,c (k 1 ,k 2 )] =
08 00 00 16 00 00 00 00 00

The 2D-RT spectra of H 4 obtained using Column-Row method is X c,r (k 1 ,k 2 ) and it is shown below.


# 08 16

[X c,r (k 1 ,k 2 )] = 08 00 00 16 00 00 00 00 00
In this case of symmetric matrix [X r,c (k 1 ,k 2 )]=[X c,r (K 1 ,k 2 )].

# 2D-RT Translation invariance property

Consider the two-dimensional array A showing aT like pattern.
0 0 0 A = [x(m,n)] = 1 1 0 0 1 0 0 1 0 B is the translated version of A. 0 1 1 B = [x t (m,n)] = 0 0 0 0 0 0 0 0 0
One can verify that [X c,r (K 1 ,k 2 )] for both arrays A and B remain the same. Similarly, one can verify that [X r,c (k 1 ,k 2 )] remain the same for both arrays A and B. This amounts to saying that 2D-Rajan Transform is essentially a translation invariant function, which could be effectively used in pattern recognition.


# III.


# Three-Dimensional Rajan Transform

The definition and various properties associated with two dimensional RT is extended to the threedimensional case also. Especially, the basic methods for implementing2D Rajan Transform like Row-Column method and Column-Row method could further be generalized to implement 3D Rajan Transform. One can implement 3-D Rajan Transform using any one of the following six methods: (i) Row-Column-Depth method, (ii) Row-Depth-Column method, (iii) Column-Row-Depth method, (iv) Column-Depth-Row method, (v) Depth-Row-Column method and (vi) Depth-Column-Row method. Let us consider the three dimensional array of matrix size 4x4x4 as shown in Fig. 2.


# Fig. 2: Sample three dimensional array

The above 3-D matrix is represented in a linear array of 2-D planes for easy understanding.


# 3D-RT using Row-Column-Depth (RCD) Approach

The 1D-RT of the four rows of the 0 th plane of the matrix X are {1,1,1,3}?{6,2,2,2}, {1,1,1,3}?{6,2,2,2}, {2,1,2,2}?{7,1,1,1}, {1,0,0,3}? {4,2,4,2}. The 1D-RT of the four rows of the 1 st plane are {1,0,1,0}?{2,2,0,0}, {1,2,3,0}?{6,2,4,0}, {0,0,2,3}? {5,1,5,1}, {3,0,3,3}?{9,3,3,3}. The 1D-RT of the four rows of the 2 nd plane are {2,2,1,0}?{8,2,2,0}, {1,0,1,3}?{5,1,3,3}, {2,1,1,1}?{5,1,1,1}, {2,3,2,1}? {8,0,2,2}. The 1D-RT of the final plane of four rows are {0,1,0,2}?{3,3,1,1}, {2,0,0,2}?{4,0,4,0}, {1,2,2,2}? {7,1,1,1}, {2,2,0,1}?{5,1,3,1}. Now the 3D array of the Rajan Transform computed row wise is given by The 1D-RT of the four columns of the 0 th plane of the matrix X r (k 1 ,k 2 ,k 3 ) are {6,6,7,4}?{23,3,3,1}, {2,2,1,2}?{7,1,1,1}, {2,2,1,4}?{9,3,3,1}, {2,2,1,2}? {7,1,1,1}. The 1D-RT of the four columns of the 1 st plane are {2,6,5,9}?{22,8,6,0}, {2,2,1,3}?{8,2,2,0}, {0,4,5,3}?{12,2,6,4}, {0,0,1,3}?{4,2,4,2}. The 1D-RT of the four columns of the 2 nd plane are {8,5,5,8}?{26,0,6,0}, {2,1,1,0}?{4,2,2,0}, {2,3,1,2}? {8,2,2,0}, {0,3,1,2}?{6,4,2,0}. The 1D-RTs of the final plane of four columns are {3,4,7,5}?{19,1,5,3}, {3,0,1,1}?{5,3,3,1}, {1,4,1,3}?{9,5,1,1}, {1,0,1,1}? {3,1,1,1}.Now the 3D array of the Rajan Transform Row-Column wise is given by The 1D-RT of the depth wise of four corresponding elements in four planes of the matrix X r,c (k 1 ,k 2 ,k 3 ), (RT can compute starting with any element in 0 th plane, in this example the RTs computed starting with row wise for easy understanding) are {23,22, 26,19}?{90,8,6,0}, {7,8,4,5}?{24,2,6,0}, {9,12,8,9}? {38,4,4,2}, {7,4,6,3}?{20,6,2,0}, {3,8,0,1}? {22,6,10,4}, {1,2,2,3}?{8,2,2,0}, {3,2,2,5}? {12,2,4,2}, {1,2,4,1}?{8,2,4,2}, {3,6,6,5}?{20,2,4,2}, {1,2,2,3}?{8,2,2,0}, {3,6,2,1}?{12,2,6,4}, {1,4,2,1}? {8,2,4,2}, {1,0,0,3}?{4,2,4,2}, {1,0,0,1}?{2,0,2,0}, {1,4,0,1}?{6,4,4,2} and {1,2,0,1}?{4,2,2,0}. Now the 3D array of the Rajan Transform Row-Column-Depth wise is given by 3D-RT using Row-Depth-Column (RDC) Approach The 3D matrix using Row-Depth-Column Rajan Transform is       Fig. 11 given in the next page, shows that 3D-RT of the original 3-D matrix (Fig. 6) and the 3D-RT of the translated 3-D matrix (Fig. 10) are the same. So, the invariance property of 3D-RT could be seen to be applicable to 3D images also. This amounts to saying that 1D-RT, 2D-RT and 3D-RT could be reliably used in real world applications.
Note that X r,c,d (k 1 ,k 2 ,k 3 ) ? X r,d,c (k 1 ,k 2 ,k 3 ), but

# Cyclic Shift Invariance Property

Consider the sequence x(n)=3,8,5,6,0,2,9,6. Now, seven more cyclic shifted versions such as x c1 (n) =6,3,8,5,6,0,2,9; x c2 (n)=9,6,3,8,5,6,0,2; x c3 (n) =2,9,6,3,8,5,6,0; x c4 (n)=0,2,9,6,3,8,5,6; x c5 (n)=6,0,2,9,6,3,8,5;

x c6 (n)=5,6,0,2,9,6,3,8 and x c7 (n)=8,5,6,0,2,9,6,3 could be generated from x(n). All the eight sequences have the same X(k)=39,5,13,9,13,1,7,5, meaning Rajan Transform of a given sequence of length N would remain invariant for N cyclically permuted sequences. This property is satisfied by higher order RT, that is, 2D-RT and 3D-RT also.


# Graphical Inverse Invariance Property

Consider x(n)=3,8,5,6,0,2,9,6. Its graphical inverse is x -1 (n)=6,9,2,0,6,5,8,3. Now, one can generate seven more cyclic shifted versions such as x c1 -1 (n)=3,6,9,2,0,6,5,8;

x c2 -1 (n)=8,3,6,9,2,0,6,5; x c3 -1 (n)=5,8,3,6,9,2,0,6, x c4 -1 (n)=6,5,8,3,6,9,2,0; x c5 -1 (n)=0,6,5,8,3,6,9,2; x c6 -1 (n)=2,0,6,5,8,3,6,9 andx c7 -1 (n)=9,2,0,6,5,8,3,6. One can easily verify that all these eight sequences have the same X(k)=39,5,13, 9,13,1,7,5, meaning Rajan Transform of a given sequence of length N would remain invariant for N graphically inverted sequence and its cyclically permuted sequences. This property is satisfied by higher order RT, that is, 2D-RT and 3D-RT also.  
1![Fig. 1: Signal flow graph of Rajan Transform II. Two Dimensional Rajan Transform and its Implementation](image-2.png "Fig. 1 :")
![Fig. 3: 3-D Object of size 3x3x3 with in the 8x8x8 grid](image-3.png "")
5![Fig. 5: Resultant 3-D array after applying column wise RT to Fig. 4](image-4.png "Fig. 5 :")
6![Fig. 6: Resultant 3-D array after applying depth wise RT to Fig. 5](image-5.png "Fig. 6 :")
7![Fig. 7: 3-D Object is translated with in the 8x8x8 grid](image-6.png "Fig. 7 :")
8![Fig. 8: Resultant 3-D array after applying row wise RT to Fig. 7](image-7.png "Fig. 8 :")
9![Fig. 9: Resultant 3-D array after applying column wise RT to Fig. 8](image-8.png "Fig. 9 :")
10![Fig. 10: Resultant 3-D array after applying depth wise RT to Fig. 9](image-9.png "Fig. 10 :")
![3-D Object of size 3x3x3 with in the 8x8x8 grid Corresponding 3D Rajan Transform as shown in Fig.63-D Object is translated with in the 8x8x8 grid Corresponding3D Rajan Transform as shown in Fig.10](image-10.png "")
11![Fig. 11: Translation invariance property demonstrated by 3D-RT](image-11.png "Fig. 11 :")
			© 2020 Global Journals
			Multi-Dimensional Rajan Transform
		
		

			

## Acknowledgement

The first author expresses his gratitude to the second and third authors for introducing the fundamental notion of Rajan Transform for carrying out his Post-Doctoral research work.

			

			

## Dyadic Shift Invariance Property

Consider x(n)=3,8,5,6,0,2,9,6 and transpose its first half with the second half. The resulting sequence Td (2) [x(n)]=0,2,9,6,3,8,5,6 is the 2-block dyadic shifted version of x(n). The symbol Td (2) denotes the 2-block dyadic shift operator. In the same manner, one would obtain Td (4) [Td (2) [x(n)]]=9,6,0,2,5,6,3,8 and Td (8) [Td (4)  [Td (2) [x(n)]]]=6,9,2,0,6,5,8,3. Note that the graphical inverse of x(n) is x -1 (n) =(6,9,2,0,6,5,8,3) and it is the same as Td (8) [Td (4) [Td (2) [x(n)]]]=6,9,2,0,6,5,8,3. One can easily verify that all these dyadic shifted sequences have the same X(k), that is, the sequence 39,5,13,9,13,7,5.

There is yet another way of dyadic shifting the input sequence x(n) to Td (2) [Td (4) [Td (8) [x(n)]]]. Consider the sequence x(n)=3,8,5,6,0,2,9,6 and one can obtain Td (8) [x(n)]=8,3,6,5,2,0,6,9; Td (4) [Td (8) [x(n)]]=6,5,8,3,6,9, 2,0 and Td (2) [Td (4) [Td (8) [x(n)]]]=6,9,2,0,6,5,8,3 as dyadic shifts. Note that Td (2) [Td (4) [Td (8) [x(n)]]] = Td (8) [Td (4)  [Td (2) [x(n)]]]. This property is satisfied by higher order RT, that is, 2D-RT and 3D-RT also.


## Dual Class Invariance Property

Given a sequence x(n), one can construct another sequence y(n) consisting of at least one number which is not present in x(n) such that X(k)=Y(k). In such a case, y(n) is called the 'dual' of x(n). Consider two sequences x(n)=2,4,2,2 and y(n)=3,1,3,3. Then X(k)=Y(k)=10,2,2,2. An underlying theorem to characterize a sequence of length N=2 n to pair up with a dual sequence is "A sequence is said to have a dual if and only if its CPI is an even number and is divisible by N/2". This theorem advocates a necessary condition but not a sufficient condition. For example, consider the sequence x(n)=6,8,2,0. This indeed satisfies the theorem. That is, its CPI is 16 and the value of CPI/(N/2) is 8. Now its dual is computed as y(n)=2,0,6,8, which is not a dual of x(n) as per the definition. In such cases, they are called 'self dual' pairs. Some of the properties of dual sequences are: (i) if y(n) is a dual of x(n), then x(n) is also called the dual of y(n). Hence the pair<x(n),y(n)> is called 'dual pair'; (ii) dual of a sequence, say y(n) will necessarily exhibit geometric symmetry together with the original sequence x(n); (iii) each dual pair has a value called 'Differential Mean' (DM), which is equal to (|x(i)~y(i)|)/2 ; 0?i?(N-1) about which the dual sequences are 'flip' symmetric. DM could be a real number. This property is satisfied by higher order RT, that is, 2D-RT and 3D-RT also.


## Scalar Property

Let x(n) be a number sequence and ? be a scalar. Then the RT of ?x(n) will be ?X(k), where X(k) is the RT of x(n). For example, let us consider a sequence x(n)=1,3,1,2 and a scalar ? of value 2. Now the RT X(k) of x(n) is 7,3,1,1. RT of ?x(n)=2,6,2,4 is 14,6,2,2 which is nothing but ?X(k).This property is satisfied by higher order RT, that is, 2D-RT and 3D-RT also.


## Linearity Property

In general, RT does not satisfy the linearity property for all sequences. It was observed that for a pair x(n) and y(n) which are number sequences either in the increasing order or in the decreasing order, the linearity property works. That is, for ?x(n)+my(n) where ? and m are scalars and x(n) and y(n) are two number sequences either in the increasing or decreasing order, the RT will be ?X(k)+mY(k), where X(k) and Y(k) are respectively the RTs of x(n) and y(n). This property is satisfied by higher order RT, that is, 2D-RT and 3D-RT also.
			
			

				


* 
	
		PRC/Admn/PDF-Thiagarajan/2019-1, Pattern Recognition Division
		
			Thiagarajan
		
		
			August 10, 2020
			Pentagram Research Centre, Hyderabad, India
		
	
	Multi-Dimensional Rajan Transforms and Their Applications