均匀分块矩阵的分块term分解-eecs.qmul

《均匀分块矩阵的分块term分解-eecs.qmul》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、∗均匀均匀分块矩阵的分块均匀分块矩阵的分块TERM分解佘轶原郝鹏威北京大学信息科学中心视觉与听觉信息处理国家重点实验室北京100871摘要整数映射是实现无损压缩的有效途径也已成为新的图像压缩国际标准JPEG2000中的重要技术之一.对于有限维可逆线性变换它可通过将原变换矩阵分解为三个三角基本可逆矩阵triangularelementaryreversiblematrixTERM)或一系列单行基本可逆矩阵single-rowelementaryreversiblematrixSERM来实现.为提高整数变换的效率并

2、实现并行化本文在均匀分块方式下探讨分块矩阵的分块TERM分解.从扩展行列式det定义着手我们定义了一个分块矩阵映射至矩阵的新函数DET.本文证明它不仅具有一些可与det相类比的重要性质而且对det是完全兼容的.利用这些定义和性质我们最终得出任意给定一有限维可逆线性变换矩阵和分块方式我们总可把它分解为不超过3个分块单位TERM之积可能需要置换和Scaling预处理并由此得到了适于并行的分块单位SERM分解式.本文结论不仅能涵盖元素矩阵最优TERM分解的结果而且可提供灵活的分块方式从而为高效合理的并行实现整数映射奠

3、定了基础.关键词整数整数映射整数映射无损压缩并行计算分块矩阵行列式矩阵分解由于实际应用中计算精度和存贮容量的限制用于数据无损压缩的变换应当是完全可逆的整数[1][2]映射.早期人们在这方面的尝试包括Blume等人提出的S变换Zandi等人的TS变换Said等[3][4]人的S+P变换以及Gormish等人的颜色空间变换等等.它们显示了整数变换技术在图像压缩感兴趣区域编码渐进传输和统一的有损无损压缩系统中的良好前景.可惜当时人们在构造正逆整数变换时大多借助一些特别的技巧尚未形成一套行之有效的统一理论.[5]Bru

4、ekers等人从网络结构角度对完全可逆和完全重构的研究对以上问题有很强的指导意义(i)梯形网络结构是完全可逆的基本单元且其正逆变换实现有对称性至于具体线性和非线性算子在压缩中分别对应变换和量化则是非本质的这样我们就不必煞费苦心的针对某特定取整方式去一步步构造正逆变换(ii)反映到矩阵结构上完全可逆的可能性依赖于向量矩阵分解式存在[10]与否其中行向量矩阵本质上等同于单位SERM(iii)单位三角矩阵总可分解为向量矩阵之积进而在相差一个置换的意义下行列式为1的矩阵也存在向量矩阵分解式.遗憾的是Bruekers等人

5、的工作在当时未引起足够的重视.直至用于构造第二代小波的提升方案[6]LiftingSchemeLS发表后人们才开始利用LS的简化梯形结构来系统的研究整数小波变换.[7]Dewitte等人首先将非线性取整操作融合至提升模式中自然而简便的构造并实现了正逆整数小[8]波变换.Calderbank等人更是将以往的STS等整数变换全部纳入到小波提升框架之下并推广至一般的整数小波变换.此后这类整数实现的研究蓬勃发展并被广泛应用但绝大多数在构造过程中仍未脱离提升步LiftingStep的限制.[9]基于梯形网络结构郝鹏威和石

6、青云最先针对一般的有限维可逆线性变换运用矩阵分解给出[10]了整数实现.最近他们又给出了个数最优的分解式.事实上基于此分解技术的多成分变换的可[11]逆整数实现已被新的图像压缩国际标准JPEG2000所采纳其提案已收入JPEG2000标准第二部分的最终文本中.我们先在第1节里回顾郝鹏威和石青云的整数变换矩阵分解理论并指出其逆变换实现效率上()n的问题第2节介绍符号和约定第3节里我们将在引入W的基础上定义DET函数并详细探讨其性质第4节在此之上给出了形如LUS的最优分块TERM分解为解决实用化的问题我们会在第5节

7、里讨论如何利用置换等技术来对任意的有限维可逆线性变换进行预处理以满足上述分解要求第6节给出分解实例.∗本文得到了优秀博士学位论文奖励基金(200038)的资助和国家973项目”数学机械化与自动推理平台”(G1998030606)的资助11郝鹏威和石青云的整数变换矩阵分解理论分解的基本构成元素是三角基本可逆矩阵TERM).它们是一类特殊的三角矩阵对角元由整环的单位群的元素所构成在{a+bi

8、a,b∈Z}上就是±1和±i这也就是文献[10]定义的所谓整数因子.显然单位三角矩阵是特殊的TERM.具体来说设A=[]a为

9、N阶上TERMupperij,TERM其对角元顺次为j,?,j则正变换yA=x可按如下方式实现1NNyjmm=+xm∑axm,nn,1≤mN≤−1nm=+1yj=xNNN其逆变换可用如下递推方式实现NxyjxyNN==Nmm;−∑axjmNm,nnm,=−1,,1?nm=+1这里可选为上/下取整四舍五入或其他取整方式.对于下TERM