（信号与信息处理专业论文）双正交变换及矢量量化应用研究.pdf

中文摘要 随着正交变换理论的日臻完善，正交变换已广泛应用于数字信号处理的各个 领域。一类新型的双正交变换一全相位双正交变换在图像编码领域表现出良好 的编码性能，成为该领域的一个亮点。本文首先研究了全相位双正交变换在图像 编码领域的应用。通过对全相位列率滤波理论的深入阐述，本文引入了三种全相 位双正交变换：全相位离散余弦双正交变换、全相位离散反余弦双正交变换和全 相位w a l s h 双正交变换。它们都可以代替d c t ，作为j p e g 编码方案中的图像变 换核。接着，借鉴方向性d c t 变换，本文提出方向性双正交变换，并将其编码 性能与基于d c t 的j p e g 编码方案作了比较，实验结果表明，方向性变换可以 在一定程度上提高编码质量。 为了进一步扩展双正交变换理论的应用范围，本文研究了矢量量化技术。首 先，对矢量量化技术的码书训练、码字搜索做了介绍。在保证编码质量的前提下， 缩短编码时间和降低码率是当前研究的重要问题。快速码字搜索算法是减少编码 时间的重要技术。本文提出了一种改进的哈达玛变换域等均值等方差最近邻搜索 算法，测试结果表明，这种算法能够排除更多的码字，效率更高。接着，研究了 与图像处理相关的两种技术：边缘匹配和快速相关矢量量化。本文提出了一种基 于d c t 分类的边缘匹配矢量量化算法，充分考虑了当前处理图像块与其相邻图 像块之间的相关性以及各码字与该输入矢量之间的边缘匹配失真。实验结果表 明，该算法的p s n r 值高于基本边缘匹配矢量量化器且码率更低。之后本文又对 该方法进行了改进，并提出一种新的基于d c t 分类的边缘匹配矢量量化算法， 这种算法可以使运算时间缩短3 0 4 0 。为了降低码率和进一步缩短编码时间， 目前已有相关矢量量化的图像编码算法，但是这种算法造成编码质量的下降。本 文提出了改进的基于对角线相关矢量量化编码算法。测试结果表明，这种算法的 编码质量提高了0 8 0 9 d b 且码率进一步降低。 最后，本文将双正交变换与矢量量化技术相结合，提出一种可行的编码方案， 作为双正交变换理论的应用之一。实验结果表明，在较低的码率下仍能够取得较 好的编码质量。 关键词：图像编码；全相位双正交变换；矢量量化；方向性变换；y p e g a b s t r a c t o r t h o g o n a lt r a n s f o r mh a sb e e nw i d e l ya p p l i e dt od i g i t a ls i g n a lp r o c e s s i n gf r o m d a t ac o m p r e s s i o nt os i g n a lr e s t o r a t i o n an e wm e m b e ri nt h ef a m i l yo fb t s ，n a m e da l l p h a s eb i o r t h o g o n a lt r a n s f o r m ( a p b t ) ，h a sb e c o m eah i g h l i g h td u et oi t sr e a s o n a b l e p e r f o r m a n c ei ni m a g ec o d i n g f i r s t l y , a l lp h a s e ( d i s c r e t ec o s i n e i n v e r s ed i s c r e t e c o s i n e w a l s h ) b i o r t h o g o n a lt r a n s f o r m s 踟i n 仃o d u c e da f t e rt h ee x p l a n a t i o nf o r d e s i g no fa l lp h a s es e q u e n c yf i l t e r s t h et h r e et r a n s f o r m sa b o v ec a l lb eu s e da s s u b s t i t u t e sf o rd i s c r e t ec o s i n et r a n s f o r m ( d e nt oi m p l e m e n tt h ew e l l k n o w nj p e g s c h e m e s e c o n d l y , d i r e c t i o n a l - a p b ti sp r e s e n t e di nt h i sp a p e r t h ec o d i n gr e s u l t so f d i r e c t i o n a la p b t - j p e ga r ec o m p a r e dw i t ht h ej p e gs c h e m eb a s e do nd c t ( d c t - j p e g ) ，w h i c hi n d i c a t et h a tc o d i n gq u a l i t yc a l lb ei m p r o v e ds l i g h t l y i no r d e rt oe x t e n dt h ea p p l i c a t i o no fb i o r t h o g o n a lt r a n s f o r mt h e o r yf u r t h e r , t h e p a p e ri n t r o d u c e st h ev e c t o rq u a n t i z a t i o nt e c h n i q u e ，w h i c hi n c l u d e sc o d e b o o kt r a i n i n g a n dk e yw o r ds e a r c h i n g o nt h eb a s i so fh i g hc o d i n gq u a l i t y , r e d u c i n ge n c o d i n gt i m e a n dc u t t i n gd o w nb i tr a t e sa r et h ei m p o r t a n tp r o b l e m so fc u r r e n tr e s e a r c h f a s t c o d e w o r ds e a r c ha l g o r i t h mi s8 1 1i m p o r t a n tt e c h n o l o g yt or e d u c ee n c o d i n gt i m e t h i s p a p e rp r e s e n t sam o d i f i e dh a d a m a r d t r a n s f o r mb a s e de q u a l a v e r a g ee q u a l v a r i a n c e n e a r e s tn e i g h b o rs e a r c ha l g o r i t h m ( m h t e e n n s ) t h ee x p e r i m e n ts h o w st h a tt h i s a l g o r i t h mc a ne x c l u d em o r e c o d e w o r da n db em o r ee f f i c i e n t t h e n ，t h ep a p e r i n t r o d u c e st w or e l e v a n tt e c h n i q u e s ：t h es i d e m a t c hv e c t o rq u a n t i z e r ( s m v q ) a n df a s t c o r r e l a t i o nv e c t o rq u a n t i z a t i o n ( f c v q ) a ni m a g ec o d i n ga l g o r i t h mb a s e do nt h e c l a s s i f i e ds i d e - m a t c hv e c t o rq u a n t i z a t i o ni nd c td o m a i ni sp r e s e n t e d c o r r e l a t i v e p r e d i c t i o n sb e t w e e nn e i g h b o r i n gi m a g eb l o c k sa r em a d ei nt h ea l g o r i t h m n em a t c h d i s t o r t i o nb e t w e e ni n p u ti m a g eb l o c k sa n dt h ec o d ev e c t o r si sa l s oc o n s i d e r e d t h e e x p e r i m e n t a lr e s u l ts h o w st h a tc o m p a r e dw i t hb a s i cs m v q ，i tr e d u c e sb i tr a t e sa n d r a i s e st h ep s n rv a l u e t h e nt h ea l g o r i t h mi sm o d i f i e d a n dan e wa l g o r i t h mi s p r e s e n t e dw h i c hc 如r e d u c ec o d i n gt i m eb y3 0 0 o - 4 0 i no r d e rt or e d u c eb i tr a t e s a n dr e d u c em o r ee n c o d i n gt i m e ，f c v qw a sp r e s e n t e d ，b u tc o d i n gq u a l i t yi sd e c l i n e d t h i sp a p e rp r e s e n t sam o d i f i e dd i a g o n a lb a s e df a s tc o r r e l a t i o nv e c t o rq u a n t i z a t i o n a l g o r i t h m ( m d f c v q ) n l ee x p e r i m e n ts h o w s t h a tt h ea l g o r i t h mi m p r o v e st h eq u a l i t y b y0 8 - 0 9d ba n dr e d u c e sb i tr a t e s f i n a l l y , t h i sp a p e rc o m b i n e sf a s tc o d e w o r ds e a r c h a l g o r i t h ma n dc o r r e l a t i o nv e c t o rq u a n t i z a t i o n c o m p a r e dw i t hp r e v i o u sa l g o r i t h m ，a n e wa l g o r i t h mi sp r e s e n t e d , w h i c hh a sh i g b e rq u a l i t ya n dl o w e rb i tr a t e s f i n a l l y , c o m b i n e dw i t hb i o r t h o g o n a lt r a n s f o r ma n dv e c t o rq u a n t i z a t i o n ，t h i sp a p e r p r e s e n t saf e a s i b l ec o d i n gs c h e m e ，w h i c hc a l l b ea na p p l i c a t i o no fb i o r t h o g o n a l t r a n s f o r mt h e o r y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tg o o dc o d i n gq u a l i t yc a nb ea l s o o b t a i n e da tl o wb i tr a t e k e yw o r d s ：i m a g ec o d i n g ；a l lp h a s eb i o r t h o g o n a lt r a n s f o r m ( a p b t ) ；v e c t o r q u a n t i z a t i o nf v q ) ；d i r e c t i o n a lt r a n s f o r m ； p e g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他入已经发表 或撰写过的研究成果，也不包含为获得盘壅盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：砌f 咖乖多签字日期：切7 年f 月彬日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权鑫鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 、( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：初f 绎么号 导师签名： 签字日期：珈夕年夕月2 弘日 ，名 ，1 圣叫乏 签字日期：阳1 年，月呷日 第一章绪论 1 1 图像压缩编码概述 第一章绪论 1 1 1 图像压缩的发展历程 自1 9 4 8 年提出电视信号数字化的设想后，即开始了图像压缩的研究，到现 在已有6 0 多年的历史。2 0 世纪五六十年代的图像压缩编码主要集中在预测编码、 哈夫曼编码等技术的研究，还不成熟。1 9 6 9 年在美国召开的第一届“图像编码会 议”标志着图像编码作为一门独立学科的诞生。到了七八十年代，图像压缩技术 的主要成果体现在变换编码技术上，矢量量化编码技术也有较大的发展。8 0 年 代末，小波变换理论、分形理论、人工神经网络理论、视觉仿真理论建立，人们 开始突破传统的信源编码理论，图像压缩编码向着更高的压缩率和更好的压缩质 量的方向发展，进入了一个崭新的发展时期j 。 1 1 2 图像压缩的分类 据统计，目前已有4 0 多种图像压缩编码算法面世。在分类上，也存在几种 不同的方法。根据对编码信息的恢复程度，数据压缩编码可分为无损压缩编码( 或 称为无失真压缩编码) 和有损压缩编码( 或称为限失真压缩编码) 。无损压缩编码是 指解码后的数据与原始数据完全相同，没有任何信息损失，常用的无损编码方法 有哈夫曼编码、算术编码、l z w 编码等；有损压缩编码实施解码后的数据与原 始数据有定的偏差，恢复数据只是某种失真度下的近似，常用的方法主要有离 散余弦编码( d c t ) 、差分脉冲预测编码( d p c m ) 、量化等；根据所用方法的原理 不同，可分为预测编码、统计编码、变换编码等。下面我们主要根据第二种分类 ，方法对图像压缩方法的基本原理和方法进行介绍【2 1 。 1 统计编码 统计编码又称熵编码，它是对于有不同概率的事件分配以不同长度的码字， 对概率大的事件分配以短的码字，从而使平均码字最短。统计编码实现事件出现 的概率与码字长度的最佳匹配。典型的统计编码方法有哈夫曼编码( h u f f m a n ) 、 算术编码和行程编码等。 2 预测编码 第一章绪论 预测编码的理论基础是现代统计学和控制论。预测编码是根据某一模型，利 用以往的样本值对新样本值进行预测，然后将样本的实际值与其预测值相减得到 一个误差值，然后对该误差值进行编码，如果模型足够好且样本序列在时间上的 相关性较强，那么误差信号的幅度将远小于原始信号，从而可以用较少的数据对 其差值量化以得到较大的数据压缩结果。现在常用的方法是差分脉冲编码调制 法。利用预测编码的方法压缩图像数据的空间和时间冗余性，这种方法直观、简 捷、易于实现，它的不足在于压缩能力有限。 3 变换编码 变换编码先对图像进行某种函数变换，从一种表示空间变换到另一种表示空 间，然后在变换后的域上对信号进行编码。目前在图像压缩中经常使用的变换有： ( 1 ) k a r h u n e n l o e v e 变换( k l t ) 。它是一种最优变换。k l t 可以有效地去除原 始数据的相关性，从而实现高效压缩。但是由于k l t 的变换核随原始数据而变， 是不固定的，并且不存在快速算法，限制了它在实际中的应用，一般常作为其它 方法的参照。 ( 2 ) 离散余弦变换( d c t ) 。对于像素间呈现高度相关的典型图像，d c t 的性 能与k l t 的性能没有实质的区别。并且d c t 有快速实现算法。与w a l s h h a d a m a r d 变换相比，d c t 具有更强的信息集中能力，并且易于软硬件实现，正是由于这 些优点，d c t 已经成为当前图像压缩中应用最广泛的技术。 ( 3 ) w a l s h h a d a m a r d 变换( w r i t ) 。与d c t 相比，w h t 在压缩方面的性能要 逊色许多，但由于实现起来算法简单，且具有简洁的去相关能力，以及特别有利 于硬件实现，使得哪也成为一种比较流行的算法p 刮。 1 1 3 图像压缩编码标准 国际标准化组织( i s o ) 、国际电子学委员会( i e c ) 、国际电信联盟( 1 m 等国际 组织，于9 0 年代领导制定了许多重要的多媒体数据压缩标准。如静止图像压缩 标准j p e g 、j p e g 2 0 0 0 ，动态图像压缩标准h 2 6 1 、h 2 6 3 、h 2 6 4 、m p e g 1 、 m p e g - 2 、m p e g - 4 、m p e g 7 等等。这些标准已在数字电视、多媒体领域得到广 泛应用【2 1 。 这些图像编码方法根据变换编码( t r a n s f o r mc o d i n g ) 中采用的变换核，可以分 为两大类。第一类方法又称为传统图像编码方法，其变换编码的变换核为块变换， 以d c t 应用最为广泛，例如p e g 即属此类。这类编码方法通常首先利用块变 换消除图像的空间冗余( s p m i mr e d u n d a n c y ) ；再通过块运动估计( m o t i o n e s t i m a t i o n ) 和运动补偿( m o t i o nc o m p e n s a t i o n ) 技术消除时间冗余；最后利用变字 长编码( v a r i a b l e 1 e n g t hc o d i n g ) 消除统计冗余。然而，随着研究和应用的不断深入， 2 第一章绪论 基于块变换的图像( 视频) 编码的缺点逐渐暴露出来，尤其在低比特率( b i tr a t e ) 环 境下，容易导致方块效应( b l o c k a r t i f a c t s ) 、飞蚊噪声等失真现象。这是因为在一 般情况下，图像信号是高度非平稳的，图像中的一些突变结构比如边缘区域信息 远比图像的平滑区域信息重要，用d c t 或其它正交变换的基矢量作为非平稳信 号的逼近，其效果并不是最优的。另外，2 0 世纪9 0 年代以i n t e r n e t 为代表的新 兴信息媒体对图像的浏览和传输有了许多新要求，例如嵌入式编码( e m b e d d e d c o d i n g ) 的优越性迅速彰显，还有多分辨率编码( m u l t i - r e s o l u t i o nc o d i n g ) 在各应用 领域的灵活性，等等。要求在图像编码算法实现中，能灵活地提供关于质量、分 辨率等的分级结构，这就引出了第二类图像编码方法。 第二类图像编码方法以小波变换( w a v e l e tt r a n s f o r m ) 等子带变换( s u b b a n d t r a n s f o r m ) 为变换编码的变换核，例如j p e g 2 0 0 0 即属此类。2 0 世纪8 0 年代后期 发展起来的小波变换，由于其具有良好的空间频率局域化特性，成为非平稳信号 处理的有力工具。由于小波基的无条件基特性，使其成为一大类信号非线性逼近 的最优基。许多信号在小波基的表示下，均可获得稀疏表示。小波变换理论中的 一个关键思想是多分辨率分解，它很好地体现在了小波图像编码中，使得图像编 码成为小波变换应用中最成功的领域之一。小波图像编码的研究表明，现代应用 中需要的许多特征如多分辨率编码、多层质量控制、嵌入式码流等，均能与小波 图像编码结构非常自然地融合在一起，在较大压缩比情况下，小波编码的重建图 像质量明显优于基于块变换的图像编码方法p 叫。 1 2 正交变换的研究意义和国内外现状 变换编码( t r a n s f o r mc o d i n g ) l 勺基本思想是将在欧几里德几何空间( 空间域) 表 示的图像信号变换到另外的向量空间( 变换域) 进行表示，去掉图像的空间冗余 度，然后再根据图像在变换域中系数的特点和人眼的视觉特性进行编码。变换编 码经常与量化一起使用，进行有损数据压缩p j 。 1 9 6 8 年，出现了正交变换图像编码，a n d r e w s 等人提出不对图像本身编码， 而对其二维离散傅立叶变换( d f t ) 系数进行编码和传输，但因d f t 是一种复杂变 换，运算量大，不易实时处理。1 9 7 4 年，a h m e d 等人提出了离散余弦变换f d c t ) ， d c t 常常被认为是图像信号的准最佳变换0 0 。d c t 变换的最大特点是对于一般 的图像都能够将像块的能量集中于少数低频d c t 系数上，这样就可能只编码和 传输少数系数而不严重影响图像质量。d c t 不能直接对图像产生压缩作用，但 是对图像的能量具有很好的集中效果，为压缩打下了基础。 除了最常用的离散余弦变换，其次还有小波变换、h a d a m a r d 变换等等。离 第一章绪论 散余弦变换在性能上接近k l t ，能够很好的实现能量集中，广泛的应用于几乎所 有的视频压缩标准中f 1 1 1 。从最常见的j p e g 静止图像压缩标准到m p e g 等运动 图像压缩标准，都使用了变换编码。d c t 用于图像编码是1 9 7 4 年由a h m e d 和 r a o 提出的。d c t 的提出虽然比f f t 晚，但其性能更接近理想的k l t ，且有与 信号较为匹配的独立变换矩阵，所以在信号处理中得到广泛应用。d c t 本身是 无损的酉变换，通过它能够去除帧内或帧间的冗余信息。随着s h a p i r o 的e z w 以及s a i d 等人的s p i h t 成功应用，对基于d c t 的压缩编码提出了挑战。 由于正交变换在块边界处存在着固有的不连续性，因此在块的边界处可能产 生很大的幅度差异，这就是所谓的“方块效应”，人眼对此很敏感。为了解决这个 问题，可用滤波器来平滑块边界处的“突跳”，这有一定的效果，但也会或多或少 地模糊图像的细节。 1 3 矢量量化的研究意义和国内外现状 在图像编码中，量化是一个十分重要的问题。矢量量化( v e c t o rq u a n t i z a t i o n ， v q ) 是一种高效率的压缩编码技术，具有很大的潜力。近年来备受关注和重视， 并取得了一些令人鼓舞的新进展。矢量量化的许多结构模型和设计方法都是标量 量化的自然推广。从一维到多维的跳跃促使大量的新思想、新概念和新技术出现。 矢量量化在量化时用输出组集合( 码书) 中匹配的一组输出值( 码字) 来代替一 组输入采样值( 输入矢量) ，理论基础是香农的率失真理论，其基本原理是用码书 中与输入矢量最匹配的码字的索引代替输入矢量进行传输，而解码时只需简单的 查表操作。矢量量化作为一种有效的有损压缩技术，其突出特点是压缩比大且解 码算法简单。矢量量化压缩技术的应用领域非常广阔，如军事部门和气象部门的 卫星( 或航天飞机) 遥感照片的压缩编码和实时传输、雷达图像和军用地图的存储 与传输、数字电视和d v d 视频压缩、医学图像的压缩与存储、网络化测试数据 的压缩和传输、语音编码、图像识别和语音识别等等【1 2 1 。 1 9 8 0 年l i n d e ，b u z o 和g r a y 提出了一种有效的l b g 矢量量化码书设计方法 1 3 - 1 5 该经典文献是矢量量化技术发展的基石。如果将l b g 码书设计算法结合穷 尽搜索编码算法看作基本矢量量化器，目前人们已提出了诸多具有不同特色和应 用背景的矢量量化器。这些矢量量化器在某些指标甚至整体指标上大大优于基本 矢量量化器，如约束矢量量化、反馈矢量量化、自适应矢量量化p 6 、变换域矢量 量化i l7 。、神经网络矢量量化、模糊矢量量化等。矢量量化思想的广泛性使得基于 矢量量化和应用到矢量量化思想的图像编码算法一直以来不断得到创新和改进。 这里主要对变换域矢量量化器在图像压缩编码方面的研究现状做一概括：最早的 4 第一章绪论 变换域矢量量化方法是在文献 1 7 】中阐述的，而文献【1 8 】首次提出了基于离散余 弦变换的矢量量化图像编码算法。9 0 年代以来，基于变换域的思想和其它矢量量 化思想结合地越来越多，如用在分类v q ( c l a s s i f i e dv q ) 中1 1 9 1 ，即利用变换域系数 作为特征矢量对块进行分类( 平滑块，边缘块) ，量化器对属于不同类的d c t 系数 分别进行量化。基于变换系数分类的方法简单( 例如，只利用前4 个变换域系数对 块进行分类) ，而且由于分类v q 可以保留视觉信息，较好地缓解了v q 中的边缘 降质问题，提高了编码质量。 1 4 存在的问题及本文的主要工作 本论文选题来自于高等学校博士学科点专项科研基金项目“双正交变换理论 研究及其编码应用”( n o 2 0 0 6 0 0 5 6 0 5 1 ) ，主要研究内容包括以下几个方面： 1 双正交变换理论方面 ( 1 ) 存在的问题：目前正交变换理论已经相当成熟，尤其是对离散余弦变换 ( d c t ) 的研究最为深入，在数字图像、视频压缩领域得到了广泛应用。当今的 j p e g 、m p e g 等国际编码标准均采用了d c t 变换。然而，在图像压缩编码中采 用正交变换并不是最优的选择。其缺点之一是d c t 变换存在着严重的方块效应， 并且量化表比较复杂，量化特别是改变压缩率时的量化需要较复杂的计算，量化 表也需要占定的内存空问。我们认为，存在方块效应的主要原因在于d c t 变 换是基于周期延拓的，解决这个问题是本课题研究双正交变换的动机之一。 ( 2 ) 主要工作：d c t 变换已经作为图像和视频编码的核心算法被国际标准 j p e g 、m p e g 所采用，它还被广泛应用于图像处理、模式识别等领域。本文所 要研究的双正交变换同样也能在这些领域得到应用。本文借鉴方向性d c t 的编 码方式，尝试方向性双正交变换的编码方式，得出一种更有效的双正交变换方法。 2 矢量量化方面 ( 1 ) 存在的问题：由于矢量量化技术能有效利用矢量中各分量之间以及矢量 与矢量之间的关联性来消除多余度，使它能作为种高效的数据编码技术广泛应 用于图像和语音信号的数据压缩。虽然矢量量化具有高效压缩和解码迅速的优 点，但传统的矢量量化方法存在自身无法克服的缺陷：首先，早期的l b g 聚类 迭代算法在用于设计码书时，对初始码书要求敏感，在训练中存在无效码矢且训 练时间长；其次，恢复图像存在可见的方块效应；再次，图像细节、边缘部分失 真严重；最后，编码时间长，传统的穷尽搜索运算复杂度高，搜索速度慢，限制 了矢量量化的实时应用。 从8 0 年代到9 0 年代，矢量量化技术在图像压缩编码领域取得了飞速发展， 第一章绪论 但矢量量化本身的缺陷影响了它的高压缩倍数及快速解码这一颇具吸引力的优 点。为了取其精华，目前，越来越多的研究者把目光投向了将矢量量化与其它的 编码方法相结合的领域，如v q 巾p c m + d c t 算法，取得了单独的矢量量化所无 法比及的效果。此外，将矢量量化与小波变换相结合，将分形变换引入到矢量量 化中也有所发展，种种研究表明，将矢量量化方法与其它编码方法相结合的方向 无疑是行之有效的。 ( 2 ) 主要工作：本文主要研究边缘匹配矢量量化( s m v q ) 和快速相关矢量量化 ( f c v q ) 。s m v q 利用了相同像素块之间的相关性降低了码率，然而对于相同的 码书，s m v q 的编码质量比穷尽搜索矢量量化口u l ls e a r c hv q ) 差，同时，需要大 量的计算来产生每个输入矢量的可匹配码字。f c v q 在减少编码时间的同时降低 了码率。但f c v q 将引入额外失真，因为它的码字搜索范围并不是整个码书， 不能保证为每个输入矢量找到最近码字。本文针对上述缺点对它们分别进行改 进，尝试提出两种新的矢量量化编码方法。 在码书设计方面，采用经典的l b g 算法，这种方法需要设计良好的初始码 书。拟采用随机法、删除法、分裂法。 在码字的搜索方面，拟采用部分失真搜索算法、等均值最近邻搜索算法、等 均值等方差最近邻搜索算法、改进的等均值等方差最近邻搜索算法、哈达玛变换 域部分失真搜索算法和哈达玛变换域等均值等方差最近邻搜索算法。同时提出一 种新的码字搜索算法一改进的哈达玛变换域等均值等方差最近邻搜索算法。 3 双正交变换与矢量量化结合应用 d c t 的变换系数，系数往往比较集中，而且出现了大面积零系数，非常适合 z i g z a g 扫描和游程编码；然而对于双正交变换来说，变换后的系数出现非零元素 并不像d c t 变换那样多，采用和d c t 一样的编码方式在相同的编码质量下需要 更高的码率，这样找到一种适合双正交变换的后续编码方案就显得尤为重要。鉴 于矢量量化的优点，本文尝试将矢量量化应用于双正交变换中，得出一种有效的 图像编码方法，同时拓展双正交变换理论的应用范围。 本文的具体章节安排如下： 第一章是绪论部分，简要介绍数字图像编码的基本情况，阐述正交变换和矢 量量化的研究意义和国内外现状，以及其存在的问题和本文的主要工作。 第二章将首先对全相位列率滤波理论做细致探讨，并由此引入全相位双正交 变换，包括全相位余弦、反余弦、w a l s h 双正交变换三种。接着，定义由三种双 正交变换引入的新图像变换核用于j p e g 图像编码算法，研究了基于双正交变换 的j p e g 编码方案( b t - j p e g ) 的编码性能，并与基于d c t 的j p e g 编码方案进行对 比。 6 第一章绪论 第三章详细研究基于块的方向性变换，首先详细研究并阐述方向性d c t 变 换，之后借鉴方向性d c t 变换，尝试研究方向性双正交变换，并将编码效果与基 于d c t 的j p e g 编码方案进行对比。 第四章主要研究矢量量化技术。首先介绍矢量量化技术，并详细研究矢量量 化技术的码书设计和码字搜索。之后研究两种用于图像编码的矢量量化技术：边 缘匹配和相关矢量量化。 第五章主要是将双正交变换与矢量量化技术相结合，与j p e g 编码方案做比 较，主要突出在低码率下的编码质量，并对码率控制进行探讨。 7 第二章全相位双正交变换与j p e g 编码 第二章全相位双正交变换与j p e g 编码 全相位双正交变换的概念来源于全相位列率滤波理论。在研究列率滤波之 前，首先介绍一下“频率”、“广义频率”和“列率”这几个概念。“频率”一词适用于 正弦( 周期) 函数组，其过零点在一个区间是等间隔的。“频率”是用以区别函数组 e o s 2 n f i ) 与 s i n2 妒 中各个函数的一个参量，它被解释为一个正弦函数在单位 时间内所经历的完整周期数( 或过零点数目的一半) 。“频率”的概念，可以通过定 义“广义频率”为每单位时间内过零点平均数的一半而加以推广。1 9 7 2 年，h a r m u t h 引入了“列率”一词来描述广义频率，用以区别那些在一个区间内的过零点非等间 隔地分布、同时又不一定是周期性的函数【2 0 】。当应用于正弦函数时，列率的定义 和频率的定义一致。将上述定义应用于周期或非周期函数厂( f ) ，得到： ( 1 ) 周期函数的列率等于每一周期内符号变更次数的一半； ( 2 ) 若变更次数是有限的，非周期函数的列率等于每单位时间内符号变更次 数的一半。 将上述定义稍加修改，便可用于相应的离散函数f ( n t ) ，f ( n t ) 由对厂( ，) 等 间隔采样得到( 间隔长度为丁) 。设每单位时间内f ( n t ) 的符号变更次数为叩，若瑁 为奇数，则f ( n t ) 的列率定义为( 0 + 1 ) 2 ；若7 7 为偶数，则其列率定义为r 2 。 2 1 全相位离散余弦列率滤波器 基于离散余弦变换离散余弦反变换( i n v e r s ed c t , i d c t ) 的列率滤波【2 1 之3 】可 由下式表示 j ，= c 1 厂c z ，) ( 2 - 1 ) 其中，j ，为滤波输出向量，所有j ，连接起来即得到总的滤波输出信号j ，c 为 n x n 阶d c t 矩阵，( ) t 表示矩阵转置，厂为长度为的列率响应向量。符号“” 表示两向量对应元素的相乘运算。乙为时域离散信号z 经分段得到的第，段长度 为的数据向量。 将式( 2 - 1 ) 表示成分量形式，则j ，的第f 个元素( 江0 ，l ，n - i ) n - i r n 一1 1 乃( 垆c t ( f ，k ) tf ( k ) c ( k ，j ) z t ( j ) i o l ，2 ” j ( 2 2 ) = 乃( ，) c t ( 七) c ( 七，j ) 厂( 七) 3 第二章全相位双正交变换与j - p e g 编码 令 趣( 歹) = c t ( f ，k ) c ( k ，歹) 厂( 七) ( 2 - 3 ) 则 y ，( f ) = 红( 歹) z ，( - ) - - - ( h ，z ，) ( 2 - 4 ) 其中，( ) 为向量内积运算。 对应不同起点存在n 个不同的数据段，它们都可以包含输入信号的某点 z ( n ) 。为能利用式( 2 - 4 ) ，不妨将这些有重合部分的数据段仍用 z 巾= o ，1 ，n - 1 ) 表示，即 t = 【z 。( o ) ，知( 一1 ) 】= 【z ( 以一+ 1 ) ，z ( n 一+ 2 ) ，z ( 刀) 】 z j = 【z l ( 0 ) ，毛( 一1 ) 】_ 【z ( 疗一+ 2 ) ，z ( 刀) ，z ( 刀+ 1 ) 】 ( 2 5 ) z 二，= 【z n - 1 ( o ) ，知一。( 一1 ) 】= 【z ( 行) ，z ( 刀+ 1 ) ，z ( n + n 1 ) 】 将以上数据段分别代入式( 2 3 ) ，则对应同一点z ( n ) ，可能出现个不同的滤波 值y o ( n - 1 ) ，y 。( n - 2 ) ，躲一l ( o ) 。为消除数据段起点不同对滤波的影响，取这 个可能滤波值的均值作为z ( 以) 的滤波响应y ( n ) ，即 y ( 咖专委乃( - 1 - 0 ( 2 - 6 ) 将式( 2 4 ) 和式( 2 5 ) 代入上式，得 j ，( 刀) 2 亩缶n - - i 缶v - i 一- ( ) 毛( ，) 2 丙1 缶v - i 缶 - 1 - l - f ( ，) z ( 刀一+ 1 + f + ) ( 2 7 1 = q ( k ) z ( n - k ) = 蟹奎z 其中符号“，表示卷积运算，且g 的第刀个元素 咖，： _ i1 娶, v 4 叫) ，胪0 1 ， ， i 专丕怕吲) ，舻卜n ，2 州，- 1 式( 2 7 ) 是全相位余弦列率滤波的卷积形式，即滤波输出信号y ( 力) 是时域离散信号 z 与全相位余弦列率滤波器口的卷积。全相位离散余弦列率滤波器( a p d c s f ) 是长 度为2 n 一1 的f i r 滤波器，不但易于实现，而且可消除传统列率滤波的方块化痕 迹，使滤波性能得到改善2 1 2 2 】。对于离散余弦变换， 9 第二章全相位双正交变换与j p e g 编码 以“，信警， 代入式( 2 3 ) ， i = o ，1 ，n - 1 ，j = 0 i = 0 ，1 ，n - 1 ，= 1 ，2 ，n - 1 ( 2 9 ) 1 厂( 七) l( 2 1 0 ) j 由上式易得红( _ ，) = h i ( i ) ，将其代入式( 2 - 8 ) ，有 g ( ，1 ) = g ( 一刀) 以= 0 ，l ，一l 上式说明，全相位离散余弦列率滤波器口具有线性相位。定义向量 吼= 【g ( o ) ，g ( 1 ) ，一，q ( n 一1 ) 】1 显然，只要求出吼即可根据式( 2 - 1 1 ) 得到整个全相位离散余弦列率滤波器。 矩阵s 和r 分别为 r ( m ， s =0o ： 由式( 2 8 ) 和式( 2 1 0 ) 可以证明 0 2 一2 0 o o 2 0 2 一3 0 0 0 2 0 20 l 0 2 0 2 0l 2 2 o o 1l ( 2 - 1 3 ) m = 0 ，1 ，n ，刀= 0 ( 2 - 1 4 ) m = 0 ，1 ，n ，”= l ，2 ，n - 1 咀= 嘉时= 击侈 其中若是列率响应向量到时域滤波器的过渡矩阵， v ( m ，栉) = ( 2 - 1 5 ) 矩阵v = s r ，且 m = 0 , 1 ，一l m 刀巍01 一，n - 1 ( 2 - 1 6 ) = ， 、， 拧= 1 ，n - 1 这样，长度为2 n l 的一维全相位离散余弦列率滤波器的设计公式由式( 2 1 1 ) 、 式( 2 - 1 5 ) 和式( 2 1 6 ) 组成。 类似地，上述关于一维a p d c s f 的设计方法可以推广至二维情形。定义对应 于二维空间某点z ( m ，玎) 的全相位离散余弦列率滤波的卷积运算t d 复y ( m ，一) 是所有 l o 警警 州问 一 得 w 、，、， d 动义 0 0 毫 定 2o o 0 o o 蒌i o ? u 一r 等旦等 慨 嗍 叫 ，一 肛 第二章全相位双正交变换与j p e g 编码 n 个包含z ( m ，力) 的二维数据块在该点的离散余弦列率滤波值的均值。设数据 块互，的离散余弦列率滤波输出矩阵 耳，f = c 1 ( n c z k ，c 1 ) c ( 2 - 1 7 ) 其中，为n x n 阶列率响应矩阵。与一维情形类似，存在卷积算法 砌，加寺k k ，( - 1 - 叫小，)亿18)=0i - - 0 j 一- u ， = q ( 历， ) z ( m ，玎) 其中q 为( 2 n 一1 ) x ( 2 n 1 ) 阶全相位离散余弦列率滤波器，具有线性相位，即 q ( 聊，刀) = q ( 一研，帕= q ( 册，一力) = q ( - m , - n ) ( 2 - 1 9 ) 拂，撑= o ，l ，( 一1 ) 定义 q = q ( o ，o )q ( o ，1 ) q ( o ，n - 1 ) q ( 1 ，o ) q ( 1 ，1 ) q ( 1 ，n - 1 ) 9 ( 一1 ，0 ) q ( 一1 ，1 ) q ( 一l ，n - 1 ) ( 2 - 2 0 ) 只要求出q l 即可由式( 2 一1 9 ) 所示的对称性得到整个二维a p d c s f 。可以证明 q = - 嘉4v fvt(2-21) 文献 2 2 ，2 3 表明，a p d c s f 可实现无波形失真的良好滤波效果，而且计算量 仅为快速d c t 算法的l 4 ，由a p d c s f 概念演绎出的这种基于列率分析设计线 性相位数字滤波器的新方法，比基于离散f o u r i e r 变换的设计方法更简洁和直观， 在数字滤波、数据压缩和特征选择等数字信号处理领域有着广阔的应用前景。 2 2 全相位双正交变换的引入 全相位双正交变换的概念来源于全相位列率滤波理论。2 1 节介绍了全相位 离散余弦列率滤波器( a f d c s f ) 的设计。而除了a p d c s f 之外，全相位列率滤波 器还包括全相位离散反余弦列率滤波器和全相位w a l s h 列率滤波器等 2 3 - 2 5 】。 2 2 1 节根据a p d c s f 引入全相位余弦双正交变换；2 2 2 节根据全相位反余 弦列率滤波器引入全相位反余弦双正交变换；2 2 3 节则由全相位w a l s h 列率滤 波器引入全相位w a l s h 双正交变换。 2 2 1 全相位离散余弦双正交变换 由式( 2 一1 6 ) 可以看出，过渡矩阵导为非正交可逆矩阵，定