U正交变换的可逆实现及其图像无损编码本科毕业论文.doc

U-正交变换的可逆实现及其图像无损编码Reversible Factorization of U Orthogonai Transform and Image Lossless Coding绪论31 U一正交变换31.1 U·正交函数系31.2 离散U一正交变换(DUT)42 可逆U一正交变换62.1正交矩阵的可逆分解623 U-正交矩阵的SERM分解93 可逆U-正交变换的图像无损编码1131可逆U-变换的无损编码11参考文献12AbstractU orthogonal transform is applied into the image lossless coding，and the factorizations of U orthogonal matrices into triangular elementary reversible matrices(TERMs)and single-row elementary reversible matrices(SERMs)are investigatedThe TERM factorization of an N by N matrix iS determined by N一1 free variables，and therefore，the local approximate optimal TERM factorization can be found by shrinking searchinterval of the N一1 free variablesIf row exchange is used，an 8×8 orthogonal matrix has only 40320 forms of SERM factorizations，and the approximate optimal SERM factorization can be found with the exhaustion search algorithmAt the end。Image lossless coding is achieved by using reversible U matrices，and the experimental results show that the code-rate of lossless compression based on reversible U transform is comparable to that 0f near lossless compression based on float U orthogonal transform：the coding efficiency of SERM factorization outperforms that of TERM；the image coding performance of U orthogonal transform of degree 3 is approximate to that of DCTAs a result，the U orthogonal transformation of degree 3 can be used into the image lossless coding instead of DCTKey words:Uorthogonal transform；triangular elementary reversible matrix；single-row elementary reversible matrix；lossless coding；discrete cosine transform(DCT)摘要U一正交变换应用到图像无损编码中，研究U一正交矩阵的基本三角可逆矩阵(TERM)分解与单行基本可逆矩阵(SERM)分解一个N阶U一正交矩阵的TERM分解由N一1个自由变量决定，用区间收缩方法可以搜索到TERM分解的局部近似最优解如果用行交换方法搜索正交矩阵的SERM分解，那么一个8阶的正交矩阵最多只有40320种可能的SERM分解，用穷举法即能找到SERM的近似最优分解最后，用U一正交矩阵的可逆分解对图像进行无损编码，实验表明可逆U一正交变换的无损编码的码率与浮点U一正交变换的近似无损编码的码率基本相同，SERM分解要比TERM分解更有效，三次U一正交变换的编码效果与离散余弦变换的编码效果几乎完全相同因此，在图像无损编码中，可用三次U一正交变换代替DCT关键词 :U一正交变换；基本三角可逆矩阵；单行基本可逆矩阵；无损编码；离散余弦变换 绪论 正交变换在图像与视频编码的应用中起着非常重要的作用，如JPEG(joint photographic expertsgroup)就是采用离散余弦变换DCT1对图像进行变换编码;H.2642采用整数DCT和wHT(walsh-对预测残差和直流分量进行变换，然后对变换数据进行熵编码由于浮点型正交变换的图像编码必然是有损的，而在某些特定的领域中，如医学图像与遥感图像的压缩，所需要的图像编码算法应该是无损的或渐近无损的，特别是在实时的图像传输系统中，高效率的无损编码算法对于图像的存储与传输有着重要的意义 其实，JPEG-LS33给出了基于线性预测的无损编码，文献4给出了一种基于浮点DCT的无损编码算法，但该算法的效率比较低下应用矩阵的提升方案可以实现线性变换的整数到整数的映射Sweldens等人应用提升方案实现离散小波的整数变换513；文献83用此方法实现了DCT的整数到整数映射；文献9对矩阵的可逆实现进行了系统研究，给出了矩阵能够进行可逆分解的条件：除置换矩阵外，一个NXN的可逆矩阵可以分解为不超过3个单位三角矩阵的积，或N+1个单行基本可逆矩阵(single-row elementary reversible matrix。SERM)的积9，并用DCT实现图像的无损压缩Ll“本文给出了正交矩阵的基本三角可逆矩阵(triangular elementary reversible matrix，TERM)与SERM分解的具体实现方法，并对U一正交矩阵进行分解，然后对变换系数进行SPIHT(set partitioning inhierarchical trees)1妇与自适应算术编码AAC，实现图像的无损压缩另外通过研究基于U一正交变换的图像无损编码算法，展示其良好的数据压缩性能，并期望U一正交变换在其他领域中能得到广泛的应用1 U一正交变换1.1 U·正交函数系 U一正交函数系是20世纪80年代由文献13-53提出的一类L2o，1上的分段多项式正交函数系(简称U一系统)；2005年，文献16-在U一系统的基础上构造出了另一类L2o，1上的正交函数系(称之为V一系统)U一系统与V一系统在几何图形表示与频谱研究中取得了令人满意的结果m。21|，文献22应用三次U一正交变换及其全相位滤波器的构造技术，得到了三次全相位U一变换的图像编码算法 r次U一系统是由o，1区间上的前r+1个Legendre多项式为基础构造出来的，其基本思路是首先构造U一系统的函数生成元，然后对函数生成元进行复制反复制得到U一系统的其他基函数，这些基函数连同r+1 Legendre多项式及函数生成元所构成的函数集合就是r次U一系15 1.2 离散U一正交变换(DUT) r次U一系统是L20，1中的完备正交函数系m1引，由于U一系统所张成的线性空间L2o，1中是稠密的，因此，把任意信号投影到该空间后，即进行U一正交变换，其能量会集中到少数的几个系数中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正交矩阵：= 0353 6 0.353 6 0.353 6 0.353 6 0.353 6 0.353 6 0.353 6 0.353 6 0.5401 0.3858 0.2315 0.0772 0.0772 0.2315 0.5388 0.54010.5401 0.0772 0.2315 0.3858 0.3858 0.2315 0.0772 0.5401 0.4069 0.2428 0.4617 0.2496 0.2496 0.4617 0.2428 0.4609 0.2415 0.3795 0.3105 0.4485 0.4485 0.3105 0.3795 0.2415 0.1332 0.2593 0.0911 0.6378 0.6378 0.0911 0.2593 0.1332 0.1581 0.4743 0.4743 0.1581 0.1581 0.4743 0.4743 0.1581 0.1581 0.4743 0.4743 0.1581 0.1581 0.4743 0.4743 0.1581 类似二维Fourier变换可以定义二维离散U一正交变换： （4）其中，w(m,x),w(n,y)是关于变量x,y的U-正交函数上式也可表示2 可逆U一正交变换2.1正交矩阵的可逆分解对于线性变换来说，如果变换矩阵是三角矩阵且主对角元素为整数因子，则相应的线性变换都可以可逆实现凹，文献9称这类矩阵为基本三角可逆矩阵(TERM)，其中整数因子定义为与整数或整型复数(实部与虚部都是整数的复数)的乘积并不改变其幅值的数，常见的整数因子有±l，±i文献9也给出了另一类可逆实现的矩阵分解方法，即把变换矩阵分解为单行基本可逆矩阵(SERM)下面讨论TERM与SERM分解的具体实现方法，以及U一正交变换的可逆分解，首先引入下面的结论：定理1 矩阵A可以分解为有限个基本三角可逆矩阵(或单行基本可逆矩阵)与置换矩阵的积的充分必要条件是定理2若A是正交矩阵，则A可以分解为有限个基本三角可逆矩阵或单行基本可逆矩阵与置换矩阵的积定理2的结论是显然的，因为若A是正交矩阵，则因此，对u一正交变换来说，可以把U一正交矩阵分解为TERM或SERM与置换矩阵的乘积，实现可逆的线性变换由于可逆变换需要对变换系数进行舍入处理，这样有可能降低正交变换性能因此，在分解过程中，必须考虑可逆线性变换的误差假设正交矩阵A可以分解为置换矩阵P与有限个基本可逆矩阵矩阵S。(i=1，2，L)的积，即，x，y，'分别为N维的输入向量、正交变换的输出向量及可逆变换的输出向量，H；是用S。(i=1，2，L)作整数变换所产生的误差如果采用四舍五入对变换系数进行取整，那么H，的每个分量的取值都在(一05，05)内，因此，总误差“满足下列关系9：其中的值达到最小时，所得到的分解是近似最优的。2.2 U一正交变换的TERM分解为了讨论U一正交矩阵的基本三角可逆矩阵分解，首先引入拉伸矩阵的一般提升形式假设口0，那么拉伸矩阵可以分解为如下一般形式：由式（7）可以解出：因此，由式(7)可把矩阵A分解为8个TERM矩阵与置换矩阵的积9，分解过程如下所述：1)对正交矩阵A进行LU分解，即分解为APLDU，其中P为置换矩阵，L为单位下三角矩阵。U为单位上三角矩阵，D为对角矩阵；2)对角矩阵D分解为拉伸矩阵的乘积，即D=diag(1，1，±1)，与为拉伸矩阵9；3)应用式(7)(8)把拉伸矩阵Do与DE各分解为4个TERM矩阵 由式(7)可知拉伸矩阵与的分解形式不是唯一的，由式(8)知二阶拉伸矩阵的分解由一个参数确定而当N一8时，Dc，的拉伸分解由4个参数确定，记为的拉伸分解由3个参数确定，记为，即8阶正交矩阵的TERM分解由(i=1，2，7)确定下面构造区间收缩算法搜索参数的值，使得式(6)中的,最小确定=(i=1，2，7)的搜索范围与搜索步长由式(8)可知，lYI(y的绝对值)过大或过小都会造成式(7)有较大矩阵元素出现，从而式(6)的值就越大根据这个原则先确定搜索集：其中d为初始搜索步长，一a，a为初始搜索区间选取适当的a与d，,为当前搜索的最小误差，初始值为无穷大为了方便，记M=.在集合中取出个数作为(i=1，2，7)，计算式(6)中的f()，如果<f()，则置()，把。作为当前最优解，并把此时的值记为(i=1，2，7)反复地执行步骤，直到搜索完所有的Y；组合置，确定新的搜索集： 然后进行新一轮搜索，即执行步骤，直到搜索步长达到指定的值，或者前后两次E。的差小于指定的阈值例如，取a=48，d=16，则M=6，在进行第1轮搜索时，除0值跳过外，需要279 936(6的7次方)次循环，假设第1轮搜索完成后的为1,6，则下一轮Y。的搜索集为 用以上的方法可以找到局部最优的TERM分解，表1是二次U一正交变换和三次U一正交变换的分解结果，其中搜索的初始值为a=4.8，d=1.6，停止条件是步长值d<0.0125，其中f()是式(6)中取无穷范数的值23 U-正交矩阵的SERM分解SERM分解是文献9提出的一种可逆分解方法，SERM矩阵的结构简单，寻找最优的SERM分解一般比较难但是，简单地应用行交换方式可以简化搜索过程，用穷举法可找到局部最优SERM分解由文献9可知，一个8阶正交矩阵可分解为:于，I为单位矩阵(m=1，2，8)为8阶单位矩阵的第m列，(m=1，2，8)为第m个素为0的8维列向量，为第8个元素为0的8维列向量。假设正交矩阵；E仃为误差估计值，初始值取无穷大若则第1行与后面的某一行进行交换，使交换后的此时，相当于A左乘以置换矩阵，取，计算：=用Gauss消元法，化简式(9)右侧的矩阵，即(10)对于式(10)右侧矩阵的右下角的N一1阶子矩阵按步骤作相同分解，直到式(10)右端的表达式变为上三角矩阵，即其中d=1或-1.计算因此，A可分解为，其中是SERM矩阵。对中矩阵进行分解，有LU=，其中(m=1，2，N)是SERM矩阵计算式(6)中的f()，如果f<E。，则置为当前最优分解交换第N-1行与第N行，重新计算步骤中的然后转用同样交换行的方法，搜索步骤中的所有可能的 用以上方法计算8阶矩阵的分解最多只有40 320(8的阶乘)种可能分解当式(6)中p取无穷时u。的近似最优SERM分解为=一08516 1.0636 15524 13567 20820 06091 0.3251 0.0000，=O.0000 0.4972 1.0698 1.1185 0.7387 0.5604 0.2527 05401，O.0801 0.0000 1.1556 0.8995 1.2608 0.1424 0.5816 05833，0.1890 0.3652 0.0000 0.1156 0.6732 0.6300 0.5776 0.2130，O.4460 0.3273 0.5656 0.0000 0.2929 0.3316 0.5177 0.1909，O.4603 0.4629 0.0236 0.3156 0.0000 0.4690 0.7321 0.2700，0.1532 0.5698 0.0849 0.4706 0.5521 0.0000 0.8704 0.1330，一O.1138 0.3943 0.8453 0.0674 0.0073 1.3035 0.0000 -0.4394，0.0834 -0.0193 1.1208 0.9722一O.8213 2.2664 1.7027 0.0000，其中，f()=4087，交换行号为3，2，7，5 7，7，7，置换矩阵P=5,2，1，6，3，7，3，8，其中3 可逆U-正交变换的图像无损编码 熵编码、SPIHT编码等都可以实现数据的无损压缩，当图像经过可逆正交变换后，其变换域的熵相对原图像来说会得到较大改进，从而可以提高无损压缩的编码效率831可逆U-变换的无损编码SPIHT算法11改进了EZW(embedded zerotreewavelet)23的重要图的表示方法，用空间方向树表示小波系数。SPIHT算法能够生成嵌入位流，使接收方能以任意码率重构图像，具有良好的渐进传输性能，位流更加容易控制自适应算术编码12是一种高效的熵编码方法，不需要单独统计信源符号的频率值，有良好的实时性、灵活性与自适应性强对于输入图像进行分块二维可逆U一变换，然后对U一变换系数进行SPIHT编码与算术编码在SPIHT编码时，把每个系数块(64个系数)看成类似8×8的图像块经过2层小波变换的系数，即把每个系数块划分为10个不同的频带解码时，如果被解码的输入流是经过算术编码后的码流，那么，首先对输入数据进行自适应算术解码，然后SPIHT解码，再进行可逆U一变换的逆变换，即可得到重构图像。参考文献1 Wallace G KThe JPEG still picture compression standardJIEEE Trans on Consumer Electronics，1992，38(1):18-342 Joint Video Tearn of ITUT VCEG and ISOIEC MPEGITu二T RecH264 ISOIECl449610 AVC Draft ITU-TRecommendation and Final Draft International Standard ofJoint Video Specification isOL2003200910-01http：liphhideimagecomGllassetspdfsJVT-G050pdf3 Taubman D S，Marcellin M W JPEG2000 ImageCompression Fundamentals，Standards and Practice FMBoston：Kluwer Academic Publisher，2004(in Chinese)(Taubman D S，Marcellin M WJPEG2000图像压缩基础、标准和实践M魏江力，柏正桡，译北京：电子工业出版社2004)4 Mandyam G，Ahmed N，Magotra NLossless imagecompression using the discrete cosine transformJJournalof Visual Communication and Image Representation，1997，8(I)：21-265 Sweldens WThe lifting scheme l A custom-designconstruction of biorthogonal waveletsJApplied andComputational Harmonic Analysis，1996，3(2)：1862006 Calderbank A R，Daubechies I，Sweldens W，et a1Wavelettransforms that map integers tO integers l-J-IApplied andComputational Harmonic Analysis，1998。5(3)：332-3697 Daubechies I，Sweldens WFactoring wavelet transformsinto lefting stepsJJournal of Fourier Analysis andApplication，1998，4(3)：2472698 Yan Yusong，Shi QingyunReversible DCT mappingintegers tO integers and lossless image compression-J1Journal of Software，2000，11(5)；620-627(in Chinese)(闫宇松，石青云可逆的DCT整型变换与失真图像压缩J软件学报，2000，11(5)：620-627)9 Hao Pengwei，Shi QingyunMatrix factorizations for reversible integer mappingJIEEE Trans on Signal Processing2001，49(10)：2314-232410 Wei Changjiang，Hao Pengwei，Shi QingyunImage coding research based on integer DCTJJournal of Image and Graphics，2002，7(3)：287291(in Chinese)(韦长江，郝鹏威，石青云基于整型DCT变换的图象编码研究J中国图象图形学报，2002，7(3)：287291)11 Said A，Pearlman WAA new fast and efficient image codec based on set partitioning in hierarchical trees口IEEE Trans on Circuits and System for Video Technology。1996。6(3)：243-25012 Witten I H，Neal R M，Cleary J GArithmetic coding for data compressionCommunications of the ACM，1987，30(6)：520-54013 Qi Dongxu，Feng YuyuOn the convergence of Fourier-UseriesJJournal of China University of Science and Technology：Issue of Math，1983，13(5)：7-17(in Chinese)(齐东旭，冯玉瑜关于Fourier-U级数的收敛性FJ中国科技大学学报：数学专辑，1983。13(5)：7-17)14 Qi Dongxu，Feng YuyuOn the orthogonal complete system UFJActa Seientic Nature，University of Jilin，1984(2)：21-31(in Chinese)(齐东旭，冯玉瑜关于正交完备系UJ吉林大学自然科学学报，1984(2)：21-31)15 Feng Yuyu，Qi DongxuA sequence of piecewise orthogonal polynomialsJSIAM Journal on Mathematical Analysis1984，15(4)：834-844