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

江西理工大学U-正交变换的可逆实现及其图像无损编码ReversibleFactorizationofUOrthogonaiTransformandImageLosslessCodingTOC\o"1-3"\h\u27362绪论 3270911U一正交变换 3182221.1U·正交函数系 3139601.2离散U一正交变换(DUT) 4205872可逆U一正交变换 641882.1正交矩阵的可逆分解 660002．3U-正交矩阵的SERM分解 977903可逆U-正交变换的图像无损编码 1186953．1可逆U-变换的无损编码 1117986参考文献 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)摘要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(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多项式为基础构造出来的，其基本思路是首先构造U一系统的函数生成元，然后对函数生成元进行复制／反复制得到U一系统的其他基函数，这些基函数连同r+1Legendre多项式及函数生成元所构成的函数集合就是r次U一系[15]．1.2离散U一正交变换(DUT)r次U一系统是L2[0，1]中的完备正交函数系m1引，由于U一系统所张成的线性空间L2[o，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正交矩阵：=0．35360.35360.35360.35360.35360.35360.35360.35360.54010.38580.23150.0772—0.0772—0.2315—0.5388—0.54010.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一正交变换：（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，的每个分量的取值都在(一0．5，0．5)内，因此，总误差“满足下列关系[9]：其中的值达到最小时，所得到的分解是近似最优的。2.2U一正交变换的TERM分解为了讨论U一正交矩阵的基本三角可逆矩阵分解，首先引入拉伸矩阵的一般提升形式．假设口≠0，那么拉伸矩阵可以分解为如下一般形式：由式（7）可以解出：因此，由式(7)可把矩阵A分解为8个TERM矩阵与置换矩阵的积[9]，分解过程如下所述：1)对正交矩阵A进行LU分解，即分解为A—PLDU，其中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=4．8，d=1．6，则M=6，在进行第1轮搜索时，除0值跳过外，需要279936(6的7次方)次循环，假设第1轮搜索完成后的为1,6，则下一轮Y。的搜索集为用以上的方法可以找到局部最优的TERM分解，表1是二次U一正交变换和三次U一正交变换的分解结果，其中搜索的初始值为a=4.8，d=1.6，停止条件是步长值d<0.0125，其中f()是式(6)中取无穷范数的值．2．3U-正交矩阵的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阶矩阵的分解最多只有40320(8的阶乘)种可能分解．当式(6)中p取无穷时u。的近似最优SERM分解为=[一0．85161.06361．55241．3567—2．08200．6091—0.32510.0000]，=[O.0000—0.4972—1.0698—1.11850.7387—0.56040.25270．5401]，[O.08010.00001.15560.8995—1.26080.1424—0.5816—0．5833]，[0.1890—0.36520.00000.1156—0.67320.6300—0.5776—0.2130]，[O.4460—0.32730.56560.00000.2929—0.3316—0.5177—0.1909]，[O.46030.4629—0.02360.31560.00000.46900.73210.2700]，[0.15320.5698—0.08490.4706—0.55210.00000.8704—0.1330]，[一O.11380.39430.84530.06740.0073—1.30350.0000-0.4394]，[0.0834-0.0193—1.12080.9722一O.82132.26641.70270.0000]，其中，f()=40．87，交换行号为[3，2，7，57，7，7]，置换矩阵P=[5,2，1，6，3，7，3，8]，其中．3可逆U-正交变换的图像无损编码熵编码、SPIHT编码等都可以实现数据的无损压缩，当图像经过可逆正交变换后，其变换域的熵相对原图像来说会得到较大改进，从而可以提高无损压缩的编码效率[8]．3．1可逆U-变换的无损编码SPIHT算法[11]改进了EZW(embeddedzerotreewavelet)[23]的重要图的表示方法，用空间方向树表示小波系数。SPIHT算法能够生成嵌入位流，使接收方能以任意码率重构图像，具有良好的渐进传输性能，位流更加容易控制．自适应算术编码[12]是一种高效的熵编码方法，不需要单独统计信源符号的频率值，有良好的实时性、灵活性与自适应性强．对于输入图像进行分块二维可逆U一变换，然后对U一变换系数进行SPIHT编码与算术编码．在SPIHT编码时，把每个系数块(64个系数)看成类似8×8的图像块经过2层小波变换的系数，即把每个系数块划分为10个不同的频带．解码时，如果被解码的输入流是经过算术编码后的码流，那么，首先对输入数据进行自适应算术解码，然后SPIHT解码，再进行可逆U一变换的逆变换，即可得到重构图像。参考文献[1]WallaceGK．TheJPEGstillpicturecompressionstandard[J]．IEEETransonConsumerElectronics，1992，38(1):18-34[2]JointVideoTearnofITU—TVCEGandISO／IECMPEG．ITu二TRec．H．264ISO／IECl4496—10AVCDraftITU-TRecommendationandFinalDraftInternationalStandardofJointVideoSpecificationis／OL]．2003[2009—10-01]．http：／lip．hhi．de／imagecom—Gllassets／pdfs／JVT-G050．pdf[3]TaubmanDS，MarcellinMW．JPEG2000ImageCompressionFundamentals，StandardsandPracticeFM]．Boston：KluwerAcademicPublisher，2004(inChinese)(TaubmanDS，MarcellinMW．JPEG2000图像压缩基础、标准和实践[M]．魏江力，柏正桡，译．北京：电子工业出版社．2004)[4]MandyamG，AhmedN，MagotraN．Losslessimagecompressionusingthediscretecosinetransform[J]．JournalofVisualCommunicationandImageRepresentation，1997，8(I)：21-26[5]SweldensW．TheliftingschemelAcustom-designconstructionofbi—orthogonalwavelets[J]．AppliedandComputationalHarmonicAnalysis，1996，3(2)：186—200[6]CalderbankAR，DaubechiesI，SweldensW，eta1．WavelettransformsthatmapintegerstOintegersl-J-I．AppliedandComputationalHarmonicAnalysis，1998。5(3)：332-369[7]DaubechiesI，SweldensW．Factoringwavelettransformsintoleftingsteps[J]．JournalofFourierAnalysisandApplication，1998，4(3)：247—269[8]YanYusong，ShiQingyun．ReversibleDCTmappingintegerstOintegersandlosslessimagecompression[-J1．JournalofSoftware，2000，11(5)；620-627(inChinese)(闫宇松，石青云．可逆的DCT整型变换与失真图像压缩[J]．软件学报，2000，11(5)：620-627)[9]HaoPengwei，ShiQingyun．Matrixfactorizationsforreversibleintegermapping[J]．IEEETransonSignalProcessing．2001，49(10)：2314-2324[10]WeiChangjiang，HaoPengwei，ShiQingyun．ImagecodingresearchbasedonintegerDCT[J]．JournalofImageandGraphics，2002，7(3)：287—291(inChinese)(韦长江，郝鹏威，石青云．基于整型DCT变换的图象编码研究[J]．中国图象图形学报，2002，7(3)：287—291)[11]SaidA，PearlmanWA．Anewfastandefficientimagecodecbasedonsetpartitioninginhierarchicaltrees口]．IEEETransonCircuitsandSystemforVideoTechnology。1996。6(3)：243-250[12]WittenIH，NealRM，ClearyJG．Arithmeticcodingfordatacompression．CommunicationsoftheACM，1987，30(6)：520-540[13]QiDongxu，FengYuyu．OntheconvergenceofFourier-Useries[J]]．JournalofChinaUniversityofScienceandTechnology：IssueofMath，1983，13(5)：7-17(inChinese)(齐东旭，冯玉瑜．关于Fourier-U级数的收敛性FJ]．中国科技大学学报：数学专辑，1983。13(5)：7-17)[14]QiDongxu，FengYuyu．Ontheorthogonalcompletesystem{U}FJ]．ActaSeienticNature，UniversityofJilin，1984(2)：21-31(inChinese)(齐东旭，冯玉瑜．关于正交完备系{U}[J]．吉林大学自然科学学报，1984(2)：21-31)[15]FengYuyu，QiDongxu．Asequenceofpiecewiseorthogonalpolynomials[J]．SIAMJournalonMathematicalAnalysis．1984，15(4)：834-844基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统基于51单片机的嵌入式Internet系统的设计与实现单片机监测系统在挤压机上的应用MSP430单片机在智能水表系统上的研究与应用HYPERLINK"/de