The Fractional Discrete Cosine Transform

902IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.50,NO.4,APRIL 2002The Fractional Discrete Cosine TransformGianfranco Cariolaro ,Member,IEEE ,Tomaso Erseghe,and Peter KraniauskasAbstract—The extension of the Fourier transform operator to a fractional power has received much attention in signal theory and is finding attractive applications.The paper introduces and de-velops the fractional discrete cosine transform (DCT)on the same lines,discussing multiplicity and computational aspects.Similar-ities and differences with respect to the fractional Fourier trans-form are pointed out.I.I NTRODUCTIONFRACTIONAL operators,particularly the fractional Fourier transform (FRT),have been investigated in some depth in recent years.The FRT was introduced [1],[2]as an extension of the ordinary Fourier transform (FT)and applied to bulk op-tics [3]–[5]and to fiber optics [6],[7]as a fundamental tool for optical information processing [8].More recently,the FRT has also been considered for discrete-time periodic signals as an ex-tension of the discrete Fourier transform (DFT)[9]–[13].The purpose of this paper is an investigation of the fractional dis-crete-cosine transform (DCT).It is well known that the DCT may be regarded as a cosine version of the DFT,which,due to its ability of compacting energy distribution,is used very suc-cessfully as a coding tool,particularly in the field of image com-pression.Nowadays,the DCT forms part of several standards [14]–[16].Starting from the DCToperator -size real sequence intoanother1TheprCARIOLARO et al.:FRACTIONAL DISCRETE COSINE TRANSFORM903on the unit circle,i.e.,can be diagonalized in the form2is a unitary matrix,withcolumnsare unitarymatrices having thepropertiesbeing real assures thatsomebe the mul-tiplicities of theeigenvalues,respectively;then,forconjugate eigenvalues and eigenvectors,we can use the nota-tionand.To find more subtle properties,we must further investigatethe eigenvalues,i.e.,the solutions of theequation,where.From(5),we alsohave,the eigenvalues of theDCTmatrixas,using the standard explicit formulas for thesolution of algebraic equations up to the fourth degree,with thehelp of symmetries in the characteristic polynomial,we can finda closed-form expression for the eigenvalues.For example,for,the real parts of theeigenvaluescan be calculated as solutionsofwhere of the characteristic poly-nomial,an exact evaluation of the eigenvalues would re-quire the solution of an algebraic equation ofdegree,we proceed numerically,setting any desired accuracy for the calculations.The numericalevidence for the distinctness of DCT eigenvalues is illustratedin Fig.1.3We finally remark that the order most used in DCTapplicationsis,for which value the claim of the conjec-ture has been proved analytically.Having consolidated this point,we can state Property4):Theorthonormal set of DCT eigenvectors is unique.Hence,the rep-resentation of the DCT matrix given by(3)is also unique.Considering that only thecase,for which wehave,we findthat,andfor N up to128.904IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.50,NO.4,APRIL2002Fig.2.Relationship between DFT and DCT:The DFT S(k)of the signal s(n)gives the DCT Sn s nsy sn n nns n s sn s s nn si n nn st ss nno n n s n n s ns nn s no s n s nn s si se s n n ss n n n s ks s no nn s s se s n n nnn s nnoso s nsn ss nnsus nssnCARIOLARO et al.:FRACTIONAL DISCRETE COSINE TRANSFORM 905A.Real Power of the FDCT MatrixTo get a real power of the DCT matrix,we consider the ex-pansion (3)ofthpowers ,that is,thematrix,the corre-spondingFDCT,can be calculated by (11).By the additive property,wehave,namely(13)Thematrixnon-natural,could be nonunique,andthe second is that a real power of a complexnumberis not unique.We saw that the DCT eigenvectorbasisaregivenbya generating sequence(GS)of the FDCT.4TheDCT condition is obvious.The key to the other is the additive propertyof the power to a real number,namely, = ,combined with orthonor-mality of eigenvectorsuuu u uu uuuuuC.Properties of the FDCTThe FDCT has been defined by modifying the DCT and,more specifically,by preserving the orthonormal basis of eigenvec-torsand changing the correspondingeigenvalues .Since these new eigenvalues have modulus 1and aredistinct(for),for everyfraction and everyGS ,namely,it is unitary,real orthog-onal,and has a unique orthonormal basis (givenby).In particular,the unitary property assures the Parseval’s relation-shipforevery906IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.50,NO.4,APRIL2002Fig.3.Eigenvalue constellations for defining the square roots of the DCT matrix(for clarity,the conjugate eigenvectors are not indicated).Note that the orthogonalitypropertyin the inverse FDCT(13)is simply givenby the transposeofdistinct square roots.For example,for,we give the numerical valuesof the DCTmatrix,starting with thefraction,which corresponds to the ordinary DCT.In thisexample,the FDCT was calculated with theGS.Fig.5further illustrates the dependence of the FDCT on theGS,for a givenGS.A.General Interpolation FormulaConsidering the trigonometric expressionofCARIOLARO et al.:FRACTIONAL DISCRETE COSINE TRANSFORM907Fig.4.FDCTs of (left)a rectangular sequence (center)a cosine-shaped sequence,and (right)an exponential sequence with N =16and GS q =0.Fig.5.FDCT of a rectangular sequence with N =16and different GSs q with a fixed fraction a =(3=4).constructing the wholefunction ,frombeequationsare known,we solve the systemwith respect to theunknowns,then(22)wherefractions .The only assumption is that thefractionsmust be chosen908IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.50,NO.4,APRIL 2002such that thematrixfractions are equally spaced.From (22),we find that theFDCT is obtainedas,it is sufficient toevaluate theFDCTsof the givensequencefractions .To calculate the inverseFDCT,yields(24)and permits evaluation of the FDCT matrix by merely calcu-lating thefirstweights obtained with thechoice are illus-trated in Fig.6for.As a check,we notethat ,wherefor otherwise.A further check can be made by using thepropertyoriginalsequence;;;,byiterating the DCTalgorithmoperations [24],the calculationof.putation via the DCT and IDCT Thechoicewhich is essentially equivalent to (24).For the FDCT ityieldswhere,for -fold evaluation of theDCT andforbya,wefindis the IDCT of the IDCTofare illustrated in Fig.7for .Note that the excur-sions ofthe are smaller than in the previous case,at least within therangeorCARIOLARO et al.:FRACTIONAL DISCRETE COSINE TRANSFORM909Fig.7.Weights of FDCT for N =8with fractions 03;02;01;0;1;2;3;4.allow an evaluation of the FDCT by a combination of thehalf-DCT with the DCT.As an example,for,the second choice gives an FDCT matrix interpolationformulaand itshalf-DCT.In general,an interpolationformula depends on theGSdependon.V .O THER F ORMS OF DCTAlthough the DCT and IDCT expressions (1)are by far the most common,many other formulations do exist.Strang [18]lists eight different forms,which we summarize in Table I.In particular,DCT-2and DCT-3correspond to the forward and in-verse DCTs defined by (1a)and (1b),respectively.All the other transforms of Table I also have real ,unitary,two separate eigenspaces exist:one for 1and one for,and,for ,the dimension of at least one of these eigenspaces is greater than one [25].This implies that there is no unique eigenvector basis and that the DCT fractionalization rule (17)has two-fold multiplicity given bya)the choice of an orthonormal setof;b)the choice of a generatingsequence910IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.50,NO.4,APRIL 2002values.This implies that the orthonormal set of eigenvectors is unique so that multiplicity is confined to the choice of GS.Un-like the DCT-2,forthat is symmetricin,with regard to compression capability(in two-dimensional applications,two fractions could be opti-mized).In some preliminary work on the well-known test image “Lena,”using FDCT’s on8and theGS,is recovered with afraction,whenever.If anFDCT ,is recovered with anotherGSwhere we used the orthonormality of thematrices.In conclusion,for encryption,we can use both thefraction,which may have thecardinalityof,the number of effective GSsis).As a closing note,we believe that if the aforementioned ap-plications tourned out to be really attractive,an effort should be made to find fast algorithms for practical implementation.A PPENDIXO THER R EPRESENTATIONS OF DCT AND FDCT M ATRICES The complex representation (3)holds for the class of uni-tary matrices.More specifically,sinceand,andletis realorthogonalcan be writtenas(28)where.Considering thateachwithis real orthogonalandcan be directly ex-pressed in terms of a skew-symmetricmatrixwithin the definitionofCARIOLARO et al.:FRACTIONAL DISCRETE COSINE TRANSFORM911[4]L.M.Bernardo and O.D.D.Soares,“Fractional Fourier transforms andimaging,”J.Opt.Soc.Amer.A,vol.11,no.10,pp.2622–2626,Oct.1994.[5]H.M.Ozaktas and D.Mendlovic,“Fractional Fourier optics,”J.Opt.Soc.Amer.A,vol.12,no.4,pp.743–751,Apr.1995.[6] D.Mendlovic and H.M.Ozaktas,“Fractional Fourier transforms andtheir optical implementation:I,”J.Opt.Soc.Amer.A,vol.10,no.9,pp.1875–1881,Sept.1993.[7]H.M.Ozaktas and D.Mendlovic,“Fractional Fourier transforms andtheir optical implementation:II,”J.Opt.Soc.Amer.A,vol.10,no.12, pp.2522–2531,Dec.1993.[8] A.W.Lohmann and B.H.Soffer,“Relationship between the Radon-Wigner and fractional Fourier transforms,”J.Opt.Soc.Amer.A,vol.11, no.6,pp.1798–1801,June1994.[9]G.Cariolaro,T.Erseghe,P.Kraniauskas,and urenti,“A unifiedframework for the fractional Fourier transform,”IEEE Trans.Signal Processing,vol.46,pp.3206–3219,Dec.1998.[10]S.C.Pei,M.H.Yeh,and C.C.Tseng,“Discrete fractional Fourier trans-form based on orthogonal projections,”IEEE Trans.Signal Processing, vol.47,pp.1335–1348,May1999.[11]L.Barker,C.Candan,and T.Hakioglu et al.,“The discrete harmonicoscillator,Harper’s equation and the discrete fractional Fourier trans-form,”J.Phys.A-Meth.Gen.,vol.33,pp.2209–2222,Mar.2000. [12] C.Candan,M.A.Kutay,and H.M.Ozaktas,“The discrete fractionalFourier transform,”IEEE Trans.Signal Processing,vol.48,pp.1329–1337,May2000.[13]S.C.Pei and J.J.Ding,“Closed-form discrete fractional and affineFourier transforms,”IEEE Trans.Signal Processing,vol.48,pp.1338–1353,May2000.[14]W.B.Pennebaker and J.L.Mitchell,JPEG Still Image Data Compres-sion Standard.New York:Van Nostrand Reinhold,1993.[15] B.Haskell,A.Puri,and ravali,Digital Video:An Introductionto MPEG-2.London,U.K.:Chapman&Hall,1997.[16]J.L.Mitchell,MPEG Video Compression Standard.London,U.K.:Chapman&Hall,1997.[17]S.C.Pei and M.H.Yeh,“The discrete fractional cosine and sine trans-forms,”IEEE Trans.Signal Processing,vol.49,pp.1198–1207,June 2001.[18]G.Strang,“The discrete cosine transform,”SIAM Rev.,vol.41,no.1,pp.135–147,1999.[19]G.Cariolaro,T.Erseghe,P.Kraniauskas,and urenti,“Multiplicityof fractional Fourier transforms and their relationships,”IEEE Trans.Signal Processing,vol.48,pp.227–241,Jan.2000.[20] F.R.Gantmacher,The Theory of Matrices.New York:Chelsea,1960,vol.I.[21] B.W.Dickinson and K.Steiglitz,“Eigenvectors and functions of thediscrete Fourier transform,”IEEE Trans.Acoust.,Speech,Signal Pro-cessing,vol.ASSP-30,pp.25–31,Jan.1982.[22]R.A.Horn and C.R.Johnson,Matrix Analysis.Cambridge,MA:Cambridge Univ.Press,1985.[23],Topics in Matrix Analysis.Cambridge,MA:Cambridge Univ.Press,1991.[24]R.J.Clark,Transform Coding of Images,London,U.K.:Academic,1985.[25]R.Bellmann,Introduction to Matrix Analysis.New York:McGraw-Hill,1970.Gianfranco Cariolaro(M’66)was born in1936.He received the degree in electrical engineering in1960and the Libera Docenza degree in electricalcommunications in1968,both from the Universityof Padova,Padova,Italy.He was appointed Full Professor at the Universityof Padova in1975and is currently Professor ofelectrical communications and signal theory.Hismain research is in the fields of data transmission,images,digital television,multicarrier modulationsystems(OFDM),cellular radios,deep-space communications,and the fractional Fourier transform.He is author of several books,including Unified Signal Theory(Torino,Italy:UTET,2nd ed.,1996).Tomaso Erseghe was born in Valdagno,Italy,in1972.He received the laurea degree in telecom-munication engineering from the University ofPadova,Padova,Italy,in1996,with a degree thesison the fractional Fourier transform.He is currentlypursuing the Ph.D.degree in telecommunicationengineering at the University of Padova.He worked as an R&D Engineer at Snell&Wilcox,Petersfield,U.K.,a British broadcast equip-ment manufacturer,in the areas of image restorationand motion compensation.His research interests include advanced signal theory,ultra-wide-band communication systems,and the fractional Fourier transform.He has also been involved in the AURORA and MetaVision research projects sponsored by the EuropeanCommunity.Peter Kraniauskas was born in Lithuania in1939.He received the Electromechanical Engineering de-gree from the University of Buenos Aires,BuenosAires,Argentina,in1962and the Ph.D.degree fromthe University of Newcastle Upon Tyne,NewcastleUpon Tyne,U.K.,in1974.After20years in industry,including research anddevelopment posts with Xerox Research and theRacal Electronics Group,he become an IndependentEngineering Consultant to teach signal and systemsfundamentals in high-tech industry and research establishments.He is the author of the text book Transforms in Signals and Systems(Wokingham,U.K.:Addison-Wesley,1992),whose graphical approach he is currently extending to imaging with waves.。