U-正交变换的可逆实现及其图像无损编码

江西理工大学11U-正交变换的可逆实现及其图像无损编码ReversibleFactorizationofUOrthogonaiTransformandImageLosslessCoding绪论.................................................41U一正交变换...................................................................................41.1U·正交函数系........................................................................................41.2离散U一正交变换(DUT)........................................................................52可逆U一正交变换..........................................................................72.1正交矩阵的可逆分解...............................................................................72．3U-正交矩阵的SERM分解....................................................................103可逆U-正交变换的图像无损编码...............................................123．1可逆U-变换的无损编码......................................................................12参考文献................................................13江西理工大学12AbstractUorthogonaltransformisappliedintotheimagelosslesscoding，andthefactorizationsofUorthogonalmatricesintotriangularelementaryreversiblematrices(TERMs)andsingle-rowelementaryreversiblematrices(SERMs)areinvestigated．TheTERMfactorizationofanNbyNmatrixiSdeterminedbyN一1freevariables，andtherefore，thelocalapproximateoptimalTERMfactorizationcanbefoundbyshrinkingsearch—intervaloftheN一1freevariables．Ifrowexchangeisused，an8×8orthogonalmatrixhasonly40320formsofSERMfactorizations，andtheapproximateoptimalSERMfactorizationcanbefoundwiththeexhaustionsearchalgorithm．Attheend。ImagelosslesscodingisachievedbyusingreversibleUmatrices，andtheexperimentalresultsshowthatthecode-rateoflosslesscompressionbasedonreversibleUtransformiscomparabletothat0fnearlosslesscompressionbasedonfloatUorthogonaltransform：thecodingefficiencyofSERMfactorizationoutperformsthatofTERM；theimagecodingperformanceofUorthogonaltransformofdegree3isapproximatetothatofDCT．Asaresult，theUorthogonaltransformationofdegree3canbeusedintotheimagelosslesscodinginsteadofDCT．Keywords:U—orthogonaltransform；triangularelementaryreversiblematrix；single-rowelementaryreversiblematrix；losslesscoding；discretecosinetransform(DCT)江西理工大学13摘要U一正交变换应用到图像无损编码中，研究U一正交矩阵的基本三角可逆矩阵(TERM)分解与单行基本可逆矩阵(SERM)分解．一个N阶U一正交矩阵的TERM分解由N一1个自由变量决定，用区间收缩方法可以搜索到TERM分解的局部近似最优解．如果用行交换方法搜索正交矩阵的SERM分解，那么一个8阶的正交矩阵最多只有40320种可能的SERM分解，用穷举法即能找到SERM的近似最优分解．最后，用U一正交矩阵的可逆分解对图像进行无损编码，实验表明可逆U一正交变换的无损编码的码率与浮点U一正交变换的近似无损编码的码率基本相同，SERM分解要比TERM分解更有效，三次U一正交变换的编码效果与离散余弦变换的编码效果几乎完全相同．因此，在图像无损编码中，可用三次U一正交变换代替DCT．关键词:U一正交变换；基本三角可逆矩阵；单行基本可逆矩阵；无损编码；离散余弦变换江西理工大学14绪论正交变换在图像与视频编码的应用中起着非常重要的作用，如JPEG(jointphotographicexpertsgroup)就是采用离散余弦变换DCT[1]对图像进行变换编码;H.264[2]采用整数DCT和wHT(walsh-对预测残差和直流分量进行变换，然后对变换数据进行熵编码．由于浮点型正交变换的图像编码必然是有损的，而在某些特定的领域中，如医学图像与遥感图像的压缩，所需要的图像编码算法应该是无损的或渐近无损的，特别是在实时的图像传输系统中，高效率的无损编码算法对于图像的存储与传输有着重要的意义．其实，JPEG-LS[33给出了基于线性预测的无损编码，文献[4]给出了一种基于浮点DCT的无损编码算法，但该算法的效率比较低下．应用矩阵的提升方案可以实现线性变换的整数到整数的映射．Sweldens等人应用提升方案实现离散小波的整数变换[513；文献[83用此方法实现了DCT的整数到整数映射；文献[9]对矩阵的可逆实现进行了系统研究，给出了矩阵能够进行可逆分解的条件：除置换矩阵外，一个NXN的可逆矩阵可以分解为不超过3个单位三角矩阵的积，或N+1个单行基本可逆矩阵(single-rowelementaryreversiblematrix。SERM)的积[9]，并用DCT实现图像的无损压缩Ll“．本文给出了正交矩阵的基本三角可逆矩阵(triangularelementaryreversiblematrix，TERM)与SERM分解的具体实现方法，并对U一正交矩阵进行分解，然后对变换系数进行SPIHT(setpartitioninginhierarchicaltrees)[1妇与自适应算术编码AAC，实现图像的无损压缩．另外通过研究基于U一正交变换的图像无损编码算法，展示其良好的数据压缩性能，并期望U一正交变换在其他领域中能得到广泛的应用．1U一正交变换1.1U·正交函数系U一正交函数系是20世纪80年代由文献[13-]53提出的一类L2[o，1]上的分段多项式正交函数系(简称U一系统)；2005年，文献[16-]在U一系统的基础上构造出了另一类L2[o，1]上的正交函数系(称之为V一系统)．U一系统与V一系统在几何图形表示与频谱研究中取得了令人满意的结果m。21|，文献[22]应用三次U一正交变换及其全相位滤波器的构造技术，得到了三次全相位U一变换的图像编码算法．r次U一系统是由[o，1]区间上的前r+1个Legendre多项式为基础构造江西理工大学15出来的，其基本思路是首先构造U一系统的函数生成元，然后对函数生成元进行复制／反复制得到U一系统的其他基函数，这些基函数连同r+1Legendre多项式及函数生成元所构成的函数集合就是r次U一系[15]．1.2离散U一正交变换(DUT)r次U一系统是L2[0，1]中的完备正交函数系m1引，由于U一系统所张成的线性空间L2[o，1]中是稠密的，因此，把任意信号投影到该空间后，即进行江西理工大学16U一正交变换，其能量会集中到少数的几个系数中‘22]，通过剔除幅值较小的系数，即可达到压缩的目的．假设{f(i)：i一0，1，⋯，N一1)是一维离散信号，u(n，i)全U。(z。)，那么离散U一正交变换可定义为那么，式(1)可用矩阵表示为F=Uf．不像Fourier三角函数那样，对U一正交函数等间隔离散化后，所得到的离散点列并不完全正交，只是近似正交．因此，必须采用一些特殊的处理方法，使得变换矩阵的行向量尽可能地保持原基函数的形状．一般可以用下面的方法计算U一正交矩阵．1)把[o，1]区间进行等间隔地划分；2)计算每个区间的积分值，由于U一正交基函数是分段多项式函数，因此用高斯积分可以方便地计算出每个区间的积分值；3)用Gram-Schmidt方法正交化处理，便可得到式(2)所示的U一正交矩阵．式(3)是二次U一系统的8×8正交矩阵2U：2U=0．35360.35360.35360.35360.35360.35360.35360.35360.54010.38580.23150.0772—0.0772—0.2315—0.5388—0.5401江西理工大学170.54010.0772—0.2315—0.3858—0.3858—0.23150.07720.54010.4069—0.2428—0.4617—0.24960.24960.46170.2428—0.46090.2415—0.3795—0.31050.44850.4485—0.3105—0.37950.24150.1332—0.2593—0.09110.6378—0.63780.09110.2593—0.13320.1581—0.47430.4743—0.1581—0.15810.4743—0.47430.15810.1581—0.47430.4743—0.15810.1581—0.47430.4743—0.1581类似二维Fourier变换可以定义二维离散U一正交变换：),(),(),(1010),(ynwxmwnmFNxNyyxf（4）其中，w(m,x),w(n,y)是关于变量x,y的U-正交函数上式也可表示TUfUF2可逆U一正交变换2.1正交矩阵的可逆分解对于线性变换来说，如果变换矩阵是三角矩阵且主对角元素为整数因子，则相应的线性变换都可以可逆实现凹]，文献[9]称这类矩阵为基本三角可逆矩阵(TERM)，其中整数因子定义为与整数或整型复数(实部与虚部都是整数的复数)的乘积并不改变其幅值的数，常见的整数因子有±l，±i．文献[9]也给出了另一类可逆实现的矩阵分解方法，即把变换矩阵分解为单行基本可逆矩阵(SERM)．下面讨论TERM与SERM分解的具体实现方法，以及U一正交变换的可逆分解，首先引入下面的结论：定理1．矩阵A可以分解为有限个基本三角可逆矩阵(或单行基本可逆矩阵)与置换矩阵的积的充分必要条件是1DetA定理2．若A是正交矩阵，则A可以分解为有限个基本三角可逆矩阵或单行基本可逆矩阵与置换矩阵的积．定理2的结论是显然的，因为若A是正交矩阵，则