ResearchGate
See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/282271616
New 2D discrete Fourier transforms in image processing
Article in Proceedings of SPIE  The International Society for Optical Engineering • March 2015
DOI: 10.1117/12.2083389
CITATIONS
0
READS
1,067
2 authors:
Artyom M Grigoryan University of Texas at San Antonio 186 PUBLICATIONS 2,104 CITATIONS
SEE PROFILE
Sos Agaian
University of Texas at San Antonio 214 PUBLICATIONS 1,139 CITATIONS
SEE PROFILE
Some of the authors of this publication are also working on these related projects:
project Steganography with multilevel embedding View project
project image processing View project
All content following this page was uploaded by Artyom M Grigoryan on 06 February 2021.
The user has requested enhancement of the downloaded file.


New 2D Discrete F in Image P

Fourier Transforms 'rocessing



Artyom M. Grigoryan and Sos S. Agaian
Department of Electrical and Computer Engineering
University of Texas at San Antonio
Outline

Abstract

Introduction

Tensor and paired transforms of the image

Splittingsignals

Complexity of the algorithm

Redundancy of the tensor representation

Comparison with the existent algorithms

Conclusion

References
Abstract

In this s paper, the concept of the twodimensional discrete Fourier transformation (2D DFT) is defined in the general case, when the form of relation between the spatialpoints (x,y) and frequencypoints (Ш_{1},Ш_{2}) is defined in the exponential kernel of the transformation by a nonlinear form L(x,y; (jO_{p}M_{2}).

The traditional concept of the 2D DFT uses the Diaphanous form x№_{l}+y№_{2} and this 2D DFT is the particular case of the transforms described by this form L(x,y; (jO_{p}M_{2}).

Properties of the general 2D discrete Fourier transforms are described and examples are given. The special case of the NXNpoint 2D Fourier transforms, when N=2^{r}, r>1, is analyzed and effective representation of these transforms is proposed.

The proposed concept of nonlinear forms can be also applied for other transformations such as Hartley, Hadamard, and cosine transformations.
Tensor Representation of the (N*N) Image
The tensor representation of an imagef _{m} which is the (2D)frequencyand(1D)time representation, the image is described by a set of 1D splittingsignals of length N each
The components of the signals are the raysums of the image along the parallel lines
Each splittingsignals defines 2D DFT at N frequencypoints of the set
Tp^s = {(kp mod iV, ks mod TV); к = 0 : (TV — 1)}
on the cartesian lattice X = Т_{;}у._{;}у = {(//.///): n.m = 0. 1 (A — 1)}
Example: 512*512point 2D DFT
Figure 1. (a) The the maximum image composed from a stack images by fluorescence in situ hybridization (FISH) image, (b) splittingsignal for the frequencypoint (p,s) = (1,5), (c) magnitude of the shifted to the middle 1D DFT of the signal, and (d) the 2D DFT of the image with the frequencypoints of the set T_{1 5}.
Set of generators (p,s) for splittingsignals
The N=2^{r} case is considered.
The set J_{NN} of frequencypoints (p, s), or generators, of the splittingsignals is selected in a way that covers the Cartesian lattice
^{X}n,n = {(p^{,s}); p>^{s} = ^{0} : (^{N  1)} }with a minimum number of subsets Tp,s.
The set J_{N N} contains 3N/2 generators and can be defined as
Jn,n = {(!,«);« = 0: (N  1)} U {(2p, l);p = 0 : (JV/2  1)}.
The tensor representation is unique, and the image can be defined through the 2D
DFT calculated by
AT—1
^kp rrioci IV,ks rnocl IV ^ ^ fp,sIV i к О (/V l)
t—O
The total number of components of 3N/2 splittingsignals equals N^{2}+N^{2}/2, which
exceeds the number of points in the image. Many subsets Tp,s, (p,s) eJ_{NN}, have
intersections at frequencypoints.
2D paired representation of images
To remove the redundancy in the tensor representation, we consider the concept of the paired transform. In paired representation, the image is described by a unique set of splittingsignals of lengths N/2,N/4, ..., 2, 1, and 1,
where 2^{k} =g.c.d.(p,s), and k=r1 when (p,s)=(0,0). These 1D signals are generated by the set of (3N2) generators (p,s).
The components of the 2D paired transform
N—1N—1
VV Xp,_{s},2^((^{n}>^{m})/™ ,m fp,s,2^{k}t fp,s,2^{k}t+N/2i
n—0 m=0
are calculated by the system of orthogonal paired functions defined as
Set of generators (p,s) in TR of Images
• The set of N^{2} triplets of the paired functions is taken equal to the set
r—1
Un,n= U {(P,s,2^{k}t),(p,s)€2^{k}J_{N/2KN/2k}, t = 0 :  1)} U {(0,0,0)}
k— 0
The number of generators (p,s) in the set equals 3N2. The splittingsignals in paired representation carry the spectral information of the image at N/2^{k}+1 frequencypoints of the following subsets of T'p,s :
Tp _{S} = {((2m + 1 )p mod N, (2m + 1 )s mod N); m = 0 : N/2^{k+1} — 1}, where 2^{k} =g.c.d.(p,s).
The following equation holds:
Example: Paired splittingsignals of image
• Two splittingsignals of the FISH image 512X512 in paired representation:

signalf _{51}; t=0: 255} is generated by (p,s) = (1,5)

signal {f_{2 6 2t}; t=0 : 127} is generated by (p,s) = (2,6)=2(1,3)
imagesignal (1,5) (l,5)subset imagesignal (2,6) (2,6)subset
0 100 200 100 200 300 400 500 0 50 100 100 200 300 400 500
(a) (b) 2D DFT (c) (d) 2D DFT
Figure 2. (a) The paired splittingsignal for the frequencypoint (1,5) and (b) the 2D DFT of the image with the frequencypoints of the subset T^{,}_{1 5}. (c) The paired splittingsignal for the frequencypoint (2,6) and (d) the 2D DFT of the image with the frequencypoints of the subset T_{2 6}. (The 2D DFT of the image and subsetsT are cyclicly shifted to the center.)
2D Paired Transform is Orthogonal
• The mutual intersections of the subsets T'p,s with generators (p, s) such that
(p, s, 2^{k}t) G Un,n
are empty.
Here, 2^{к} =g.c.d.(p,s) and k=r1 when (p,s)=(0,0).
• Therefore, all splittingsignals in the paired representation carry the spectral information of the image at disjoint subsets of frequencypoints, and the paired transformation
is unitary
New Class of Discrete Fourier Transforms
• When considering the 2D discrete Fourier transformation with the rectangular fundamental period X_{NN}, we take into consideration the following fact:
The kernel W of the transform connects all samples (n_{1}, n_{2}) of the imagef_{n1 n2} and the frequencypoints (p_{p} p_{2}) via the simple form L, namely, the Diophantus form
considered in the arithmetics modulo N. Analyzing the procedure of construction of the paired transform with respect to the 2D DFT, where N=2^{r}, r>1, it is not difficult to note that the following three conditions have been used:

L(ni,n_{2};pi,P2) = maps X_{N}__{N} onto X_{N} = {0,1,N  1},

kL(n_{l},n_{2};pi,p2) = L(ni,n_{2};kp_{1},kp_{2}), к = 0 : (N  1), (pi,p_{2}) € X_{N},_{Ni}

+ N/2) = — Wjv(t), t = 0 : (N/2 — 1), W^(t) = exp(27ri/iV)
The condition #3 indicates only that the paired transform corresponds to the paired representation with respect to the Fourier transform, and for other transforms it can be changed in accordance with their properties. Naturally, the question arises about finding other forms L that satisfy conditions 1) and 2). Such forms exist and we describe a few one and twodimensional examples.
1

0

0

0

0

0

0

1

0

0

1

0

0

1

0

0

1

0

1

0

0

1

0

1

1

1

1

1

1

1

1

1

New Class of Discrete Fourier Transforms
Similarly, with the aid of the described algorithm, the orthogonal transformion (xV; L_{2}) is constructed in the general case N = 2r, r > 1, too.
• In order to find the Fourier transform that corresponds to this transformation (хлп L_{2}) it is sufficient to look on condition (3). In our case, when W is the exponential kernel of the Npoint DFT, which can be denoted by (JFy; L_{2}) and written as
N 1
N 1
F_{p} = ((Fn;L_{2}) of)_{p} = £ f_{n}W(L_{2}(n;p)) = £ <
2 n^{2}+n)p
n—0
n—0
p = 0 : (N  l).
High order forms L of the polynomials Qk in can be considered, too. Example 2. (Transform for the polynomial of degree k=3)
Q_{3}(n) = 2 n^{3} + n
L(n; p) = L_{3} (n;p) = (2n^{3} + n)p, n, p = 0 : (iV — 1)
JV—1
ЛГ1
= ((Jw; L_{3}) О /) = У] =
2 n^{3j}rn)p
n—0
n—0
New Class of Discrete Fourier Transforms
• Definition 3.1. Let p is a point of X_{N} and let t € {0,, ...,N/21}. The functions
are called onedimensional paired functions by the form L.
This definition generalizes the concept of the paired functions which are the paired functions by the form
We call the transformation (Xjv5 L) which corresponds to the paired functions the paired transformion by the form L.
The described Npoint transform L) is called the Fourier transformion by the
form L.
New Class of 2D Discrete Fourier Transforms
• New paired functions and unitary transformations (^_{N N}\ L), where N—2^{r}, r> 1, can be considered in the twodimensional case.
Let L be the certain form satisfying conditions (1) and (2). For any (p_{1?}p_{2}) € X_{NN} and point t € {0,1,2, ... ,N1}, we define the set of samples
V_{P}i,P2,t = {(n_{b}n_{2}); (n_{b}n_{2}) L(n_{b}n_{2};p_{b}p_{2}) = t mod N}
and its characteristic function Xpi,p_{2},t (^{n}l) ^{n}2)
Definition 3.2. The function
Xpi,p_{2},i(^{n}b^{n}2) = Xpi,P2,t(^{n}i^{n}2) ~ Xpi,P2,t+N/n(ni,П_{2}),
is called the twodimensional pairedfunction by the form L.
2D Paired transformations and DFTs by forms
Using the same set of triples U_{N},_{N} , the complete system of orthogonal paired functions can be formed. The set of the 2D paired functions by the form L
Xn,N \^Xp_{1:}p_{2},t'> ^{r}^^{1}pi,p2',L ^ ^N.Ni t ^ Xn, ^ ®}
is complete. These functions determine the orthogonal transformation which is called
the paired trantformation by the form L and is denoted as (%д_{Г} ,лг5 ^)*
Example 3. (8 X 8point transform for the polynomial)
N=8. The mask of the first paired function is
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
2D Paired transformations by forms
L(n_{1},n_{2};pi,P2) = nipi + n_{2}p2
Theses surfaces are calculated for the above nonlinear form in arithmetic modulo 256
in parts a and b for the frequencypoints (p_{1?} p_{2})=(1,2) and (1,4), respectively.
2D Paired transformations by forms
Theses surfaces are calculated for the above nonlinear form in arithmetic modulo 256
in parts a and b for the frequencypoints (p_{1?} p_{2})=(1,2) and (1,4), respectively.
2D Paired transformations by forms
The surfaces are calculated for the above nonlinear form in arithmetic modulo 256 in parts a and b for the frequencypoints (p_{1}, p_{2})=(1,2) and (1,4), respectively.
2D discrete Fourier transforms by forms
Definition 3.2. The twodimensional NXNpoint discrete transform written in the form
is called the twodimensional Fourier trantform by thejorm L and is denoted by L)
When L is of the form
L(m,n_{2}]Pi,P2) = Q^{X}{n i)pi + Q^{2}{n_{2})p2
the 2D DFT by this form is
2D discrete Fourier transforms by forms №V,N] L)
Example 4. The twodimensional NXNpoint DFT by forms
Г2.2(«1,П_{2};Р1,Р2) = (2nf + ni)pi + (2n + n_{2})?>2 Г2,з(»1,^2;Р1,Р2) = (2 rij + 7li)pi + (2n + n_{2})p_{2}
The correspondinf 2D DFT by this forms are
Image and its 2D DFT by a form L
Figure 6. (a) “Lena” image resampled to the size 128X128, (b) 2D DFT by the form L_{2 2} in the absolute scale and shifted to the center, and (c) the traditional 2D DFT.
Conclusion
A new concept of the twodimensional Fourier transforms which generalizes the traditional 2D DFT is presented. The 2D DFT is defined in the general case, when the form of relation between the spatial points (x,y) and frequency points (^,^_{2}) is defined in the exponential kernel of the transformation by a nonlinear form L(x,y;M_{1},№_{2}).
The traditional concept of the 2D DFT is defined for the Diophantus form x№_{1}+y№_{2} and this 2D DFT is the particular case of the Fourier transforms described by such forms L(x,y; C^_{1}}^_{2}). The specialcase of the NXNpoint 2D Fourier transforms, when N=2^{r}, r>1, is analyzed and effective representation of these transforms is proposed. Together with the traditional 2D DFT, the proposed 2D DFTs can be used in image processing in image filtration and image enhancement..
References

A.M. Grigoryan and S.S. Agaian, Multidimensional Discrete Unitary Transforms: Representation, Partitioning, and Algorithms, New York: Marcel Dekker, 2003.

A.M. Grigoryan, “An algorithmfor computing the discrete Fourier transform with arbitrary orders,”JournalVichislitelnoi Matematiki i Matematicheskoi Fiziki, AS USSR. vol. 30, no. 10, pp. 1576—1581, Moscow 1991.(translated in http://fasttransforms.com/ArtUSSR papers/ArtJVMATofASUSSR1991.pdf).
MUCH!
QUESTIONS, PLEASE?
Dostları ilə paylaş: 