Tensor Transform Based Method of Image Reconstructions by Projections



Yüklə 0,51 Mb.
tarix17.02.2022
ölçüsü0,51 Mb.
#83790
Art spie2015Novel2DDFT






ResearchGate


See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/282271616

New 2-D 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 multi-level 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 2-D 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

  • Splitting-signals

  • 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 two-dimensional discrete Fourier transformation (2-D DFT) is defined in the general case, when the form of relation between the spatial-points (x,y) and frequency-points 12) is defined in the exponential kernel of the transformation by a nonlinear form L(x,y; (jOpM2).

  • The traditional concept of the 2-D DFT uses the Diaphanous form x№l+y№2 and this 2­D DFT is the particular case of the transforms described by this form L(x,y; (jOpM2).

  • Properties of the general 2-D discrete Fourier transforms are described and examples are given. The special case of the NXN-point 2-D Fourier transforms, when N=2r, 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 (2-D)-frequency-and-(1-D)-time representation, the image is described by a set of 1-D splitting-signals of length N each





The components of the signals are the ray-sums of the image along the parallel lines





Each splitting-signals defines 2-D DFT at N frequency-points 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*512-point 2-D DFT








Figure 1. (a) The the maximum image composed from a stack images by fluorescence in situ hybridization (FISH) image, (b) splitting-signal for the frequency-point (p,s) = (1,5), (c) magnitude of the shifted to the middle 1-D DFT of the signal, and (d) the 2-D DFT of the image with the frequency-points of the set T1 5.











Set of generators (p,s) for splitting-signals


The N=2r case is considered.

The set JNN of frequency-points (p, s), or generators, of the splitting-signals is selected in a way that covers the Cartesian lattice

Xn,n = {(p,s); p>s = 0 : (N - 1)} with a minimum number of subsets Tp,s.

The set JN 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 2-D
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 splitting-signals equals N2+N2/2, which
exceeds the number of points in the image. Many subsets Tp,s, (p,s) eJNN, have
intersections at frequency-points.






2-D 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 splitting-signals of lengths N/2,N/4, ..., 2, 1, and 1,





where 2k =g.c.d.(p,s), and k=r-1 when (p,s)=(0,0). These 1-D signals are generated by the set of (3N-2) generators (p,s).

The components of the 2-D paired transform


N—1N—1


VV Xp,s,2^((n>m)/™ ,m fp,s,2kt fp,s,2kt+N/2i

n0 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 N2 triplets of the paired functions is taken equal to the set

r
1

Un,n= U {(P,s,2kt)-,(p,s)€2kJN/2KN/2k, t = 0 : - 1)} U {(0,0,0)}

k— 0

The number of generators (p,s) in the set equals 3N-2. The splitting-signals in paired representation carry the spectral information of the image at N/2k+1 frequency-points of the following subsets of T'p,s :

Tp S = {((2m + 1 )p mod N, (2m + 1 )s mod N); m = 0 : N/2k+1 — 1}, where 2k =g.c.d.(p,s).


The following equation holds:
























Example: Paired splitting-signals of image

Two splitting-signals of the FISH image 512X512 in paired representation:

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

  • signal {f2 6 2t; t=0 : 127} is generated by (p,s) = (2,6)=2(1,3)


image-signal (1,5) (l,5)-subset image-signal (2,6) (2,6)-subset





0 100 200 100 200 300 400 500 0 50 100 100 200 300 400 500


(a) (b) 2-D DFT (c) (d) 2-D DFT





Figure 2. (a) The paired splitting-signal for the frequency-point (1,5) and (b) the 2-D DFT of the image with the frequency-points of the subset T,1 5. (c) The paired splitting-signal for the frequency-point (2,6) and (d) the 2-D DFT of the image with the frequency-points of the subset T2 6. (The 2-D DFT of the image and subsetsT are cyclicly shifted to the center.)





2-D Paired Transform is Orthogonal


The mutual intersections of the subsets T'p,s with generators (p, s) such that

(p, s, 2k
t) G Un,n

are empty.

Here, 2к =g.c.d.(p,s) and k=r-1 when (p,s)=(0,0).


Therefore, all splitting-signals in the paired representation carry the spectral information of the image at disjoint subsets of frequency-points, and the paired transformation








is unitary



New Class of Discrete Fourier Transforms


When considering the 2-D discrete Fourier transformation with the rectangular fundamental period XNN, we take into consideration the following fact:

The kernel W of the transform connects all samples (n1, n2) of the imagefn1 n2 and the frequency-points (pp p2) 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 2-D DFT, where N=2r, r>1, it is not difficult to note that the following three conditions have been used:

  1. L(ni,n2;pi,P2) = maps XN_N onto XN = {0,1,N - 1},

  2. kL(nl,n2;pi,p2) = L(ni,n2;kp1,kp2), к = 0 : (N - 1), (pi,p2) € XN,Ni

  3. + 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 two-dimensional 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; L2) is constructed in the general case N = 2r, r > 1, too.

In order to find the Fourier transform that corresponds to this transformation (хлп L2) it is sufficient to look on condition (3). In our case, when W is the exponential kernel of the N-point DFT, which can be denoted by (JFy; L2) and written as


N 1


N 1


Fp = ((Fn;L2) of)p = £ fnW(L2(n;p)) = £ <


2 n2+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)

Q3(n) = 2 n3 + n

L(n; p) = L3 (n;p) = (2n3 + n)p, n, p = 0 : (iV — 1)


JV—1


ЛГ-1


= ((Jw; L3) О /) = У] =


2 n3jrn)p


n0


n—0






New Class of Discrete Fourier Transforms


Definition 3.1. Let p is a point of XN and let t € {0,, ...,N/2-1}. The functions





are called one-dimensional 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 N-point transform L) is called the Fourier transformion by the

form L.






New Class of 2-D Discrete Fourier Transforms


New paired functions and unitary transformations (^N N\ L), where N—2r, r> 1, can be considered in the two-dimensional case.

Let L be the certain form satisfying conditions (1) and (2). For any (p1?p2) € XNN and point t € {0,1,2, ... ,N-1}, we define the set of samples

VPi,P2,t = {(nbn2); (nbn2) L(nbn2;pbp2) = t mod N}


and its characteristic function Xpi,p2,t (nl) n2)


Definition 3.2. The function


Xpi,p2,i(nbn2) = Xpi,P2,t(ni-n2) ~ Xpi,P2,t+N/n(ni2),





is called the two-dimensional pairedfunction by the form L.









2-D Paired transformations and DFTs by forms

Using the same set of triples UN,N , the complete system of orthogonal paired functions can be formed. The set of the 2-D paired functions by the form L

Xn,N \^Xp1:p2,t'> r-^1pi,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 8-point 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









2-D Paired transformations by forms

L(n1,n2;pi,P2) = nipi + n2p2










Theses surfaces are calculated for the above nonlinear form in arithmetic modulo 256
in parts a and b for the frequency-points (p1? p2)=(1,2) and (1,4), respectively.






2-D Paired transformations by forms








Theses surfaces are calculated for the above nonlinear form in arithmetic modulo 256
in parts a and b for the frequency-points (p1? p2)=(1,2) and (1,4), respectively.






2-D Paired transformations by forms








The surfaces are calculated for the above nonlinear form in arithmetic modulo 256 in parts a and b for the frequency-points (p1, p2)=(1,2) and (1,4), respectively.



2-D discrete Fourier transforms by forms


Definition 3.2. The two-dimensional NXN-point discrete transform written in the form





is called the two-dimensional Fourier trantform by thejorm L and is denoted by L)

When L
is of the form

L(m,n2]Pi,P2) = QX{n i)pi + Q2{n2)p2

the 2-D DFT by this form is















2-D discrete Fourier transforms by forms №V,N] L)





Example 4. The two-dimensional NXN-point DFT by forms

Г2.21212) = (2nf + ni)pi + (2n| + n2)?>2 Г2,з(»1,^2;Р1,Р2) = (2 rij + 7li)pi + (2n| + n2)p2


The correspondinf 2-D DFT by this forms are








Image and its 2-D DFT by a form L











Figure 6. (a) “Lena” image resampled to the size 128X128, (b) 2-D DFT by the form L2 2 in the absolute scale and shifted to the center, and (c) the traditional 2­D DFT.






Conclusion


A new concept of the two-dimensional Fourier transforms which generalizes the traditional 2-D DFT is pre-sented. The 2-D 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 2-D DFT is defined for the Diophantus form x№1+y№2 and this 2-D DFT is the particular case of the Fourier transforms described by such forms L(x,y; C^1}^2). The specialcase of the NXN-point 2-D Fourier transforms, when N=2r, r>1, is analyzed and effective representation of these transforms is proposed. Together with the traditional 2-D DFT, the proposed 2-D 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/Art-USSR- papers/Art-JVMATofASUSSR1991.pdf).






MUCH!


QUESTIONS, PLEASE?


Yüklə 0,51 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə