第 4 章 有损压缩
第 4 章 有损压缩
虽然人们总是期望无损压缩,但冗余度很少的信息对象用无损压缩技术并不能得到可接受的结果。当使用的压缩方法会造成一些信息损失时,关键的问题是看这种损失的影响。有损压缩经常用于压缩音频、灰度或彩色图像和视频对象等,因为它们并不要求精确的数据。
在这一章,我们讨论常用的一些有损压缩技术,包括:
预测编码
变换编码
基于模型编码
分形编码
其他编码 zzzzz
必须注意,在由音频、彩色图像、视频以及其他专门数据组成的多媒体对象中,可以单独使用有损压缩技术,也可与无损压缩技术共同使用。
第 1 节 预测编码
预测编码是根据离散信号之间存在着一定关联性的特点,利用前面一个或多个信号预测下一个信号进行,然后对实际值和预测值的差(预测误差)进行编码。如果预测比较准确,误差就会很小。在同等精度要求的条件下,就可以用比较少的比特进行编码,达到压缩数据的目的。
预测编码中典型的压缩方法有脉冲编码调制(PCM ,Pulse Code Modulation)、差分脉冲编码调制(DPCM ,Differential Pulse Code Modulation)、自适应差分脉冲编码调制(ADPCM ,Adaptive Differential Pulse Code Modulation)等,它们较适合于声音、图像数据的压缩,因为这些数据由采样得到,相邻样值之间的差相差不会很大,可以用较少位来表示。
一.PCM
脉冲编码调制(PCM ,p ulse c ode m odulation )是概念上最简单、理论上最完善的编码系统。它是最早研制成功、使用最为广泛的编码系统,但也是数据量最大的编码系统。
PCM 的编码原理比较直观和简单,原理框图如图04-01-1所示。在这个框图中,它的输入是模拟信号,首先经过时间采样,然后对每一样值都进行量化,作为数字信号的输出,即PCM 样本序列x(0),x(1),…,x(n)。图中的“量化,编码”可理解为“量化阶大小(step-size)”生成器或者称为“量化间隔”生成器。
图04-01-1 PCM编码框图
量化有多种方法。最简单的是只应用于数值,称为标量量化,另一种是对矢量(又称为向量)量化。标量量化可归纳成两类:一类称为均匀量化,另一类称为非均匀量化。理论上,标量量化也是矢量量化的一种特殊形式。采用的量化方法不同,量化后的数据量也就不同。因此,可以说量化也是一种压缩数据的方法。
下面介绍标量量化,矢量量化将在本章最后一节介绍。
(一)均匀量化
如果采用相等的量化间隔处理采样得到的信号值,那么这种量化称为均匀量化。均匀量化就是采用相同的“等分尺”来度量采样得到的幅度,也称为线性量化,如图04-01-2所示。量化后的样本值Y 和原始值X 的差 E=Y-X 称为量化误差或量化噪声。
图04-01-2 均匀量化
(二)非均匀量化
用均匀量化方法量化输入信号时,无论对大的输入信号还是小的输入信号一律都采用相同的量化间隔。为了适应幅度大的输入信号,同时又要满足精度要求,就需要增加量化间隔,这将导至增加样本的位数。但是,有些信号(例如话音信号),大信号出现的机会并不
多,增加的样本位数就没有充分利用。为了克服这个不足,就出现了非均匀量化的方法,这
种方法也叫做非线性量化。
非线性量化的基本想法是,对输入信号进行量化时,大的输入信号采用大的量化间隔,小的输入信号采用小的量化间隔,如图04-01-3所示,这样就可以在满足精度要求的情况下用较少的位数来表示。量化数据还原时,采用相同的规则。
在语音信号的非线性量化中,采样输入信号幅度和量化输出数据之间定义了两种对应关系,一种称为μ律压扩(μ-law companding)算法,另一种称为A 律(A-law )压扩算法。
图04-01-3 非均匀量化
1.μ 律压扩
G.711标准建议的μ律压扩主要用在北美和日本等地区的数字电话通信中,按下面的式子(归一化)确定量化输入和输出的关系:
式中:x 为输入信号幅度,规格化成 -1≤ x≤ 1;
sgn(x ) 为x 的极性,x
μ为确定压缩量的参数,它反映最大量化间隔和最小量化间隔之比,取100≤ μ≤ 500,现在多取 μ =255。
由于μ律压扩的输入和输出关系是对数关系,所以这种编码又称为对数PCM 。具体计算时,用μ=255,可以把对数曲线变成8条折线以简化计算过程。
2.A 律压扩
G.711标准建议的A 律压扩主要用在中国大陆和欧洲等地区的数字电话通信中,按下面的式子确定量化输入和输出的关系:
0 ≤ | x| ≤ 1/A
1/A
式中:x 为输入信号幅度,规格化成 -1 ≤ x ≤ 1;
sgn(x ) 为x 的极性,x
A为确定压缩量的参数,它反映最大量化间隔和最小量化间隔之比,通常取A=87.6。 A 律压扩的前一部分是线性的,其余部分与μ律压扩相同。A 律压扩具有与μ律压扩相同的基本性能(在大信号区信噪比高于μ律量化器,但在小信号区不如μ律量化器)和实现方面的优点,尤其是还可以用直线段很好地近似,以便于直接压扩或数字压扩,并易于与线性编码格式相互转换。具体计算时,A =87.56,为简化计算,同样把对数曲线部分变成13条折线。
对于采样频率为8 kHz,样本精度为13比特、14比特或者16比特的输入信号,使用μ率压扩编码或者使用A 率压扩编码,经过PCM 编码器之后每个样本的精度为8比特,输出的数据率为64 kbps。这个数据就是CCITT 推荐的G.711标准:话音频率脉冲编码调制(Pulse Code Modulation (PCM) of Voice Frequencies)。通常的听觉主观感觉认为8位压扩量化有不低于12位均匀量化A/D的信噪比及动态范围。
二.DPCM
在PCM 系统中,原始的模拟信号经过采样后得到的每一个样值都被量化成为数字信号。为了压缩数据,可以不对每一样值都进行量化,而是预测下一样值,并量化实际值与预测值之间的差值,这就是DPCM(Differential Pulse Code Modulation,差分脉冲编码调制)。1952年贝尔(Bell )实验室的C. C. Cutler取得了差分脉冲编码调制系统的专利,奠定了真正实用的预测编码系统的基础。DPCM 的组成如图04-01-4,其中编码器和解码器分别完成对预测误差量化值的熵编码和解码。
图04-01-4 DPCM系统原理框图
DPCM 系统工作时,发送端先发送一个起始值x 0,接着就只发送预测误差值e k = xk – x ^k ,而预测值x ^k 可记为
x ^= f(x ' ,x ' ,…, x' ,k ), k > N (04-01-1)
式中k > N表示x ' 1,x ' 2,…, x' N 的时序在x k 之前,为所谓因果型(Causal )预测,否则为非因果型预测。
接收端把接收到的量化后的预测误差e ^k 与本地算出的x ^k 相加,即得恢复信号x ' k 。如果没有传输误差,则接收端重建信号x ' k 与发送端原始信号x k 之间的误差为:
xk - x' k = x k - ( x^k + e^k )
= ( xk - x^k ) - e^k
= e - e^
k k k 12N
= qk (04-01-2)
这正是发送端量化器产生的量化误差,即整个预测编码系统的失真完全由量化器产生。因此,当x k 已经是数字信号时,如果去掉量化器,使e ^k = ek ,则q k = 0,即x ' k = xk 。这表明,这类不带量化器的DPCM 系统也可用于无损编码。但如果量化误差q k ≠ 0,则x ' k ≠x k ,为有损编码。
如果预测方程式(04-01-2)的右方是各个x ' i 的线性函数,即
N
x' k = Σa i (k) x' i k > N (04-01-3)
i=1
即得常用的线性预测,又称线性预测编码(LPC ,Linear Predictive Coding)。LPC 在语音处理中得到广泛应用,并在此基础上发展了许多算法,典型的有:多脉冲线性预测编码(MPLPC ),规则脉冲激励编码(RPE ),码激励线性预测(CELP ),代数激励线性预测
(ACELP ),矢量和激励线性预测(VSELP ),QCELP (Qualcomm CELP,变速率CELP ),低延时码激励线性预测(LD-CELP ),共轭结构代数激励线性预测(CS-ACELP ),混合激励线性预测(MELP ),间隔同步更新码激励线性预测(PSI-CELP ),松弛码激励线性预测(RCELP ),残差激励线性预测(RELP ),规则脉冲激励长时预测(RPE-LTP )等。
在DPCM 中,“1位量化”的特殊情况称为增量调制(Δ调制)。
为了能够正确恢复被压缩的信号,不仅在接收端有一个与发送端相同的预测器,而且其输入信号也要相同(都是x ' k ,而不是x k ),动作也与发送端的预测器环路(即发送端本地的反量化和解码部分)完全相同。
在图像信号中应用DPCM 时,用作预测的像素和被预测的像素可以在同一行,也可以在不同行(同一帧),甚至在不同帧,分别称为一维预测、二维预测和三维预测。声音信号中的预测只是一维预测。
DPCM 的优点是算法简单,容易硬件实现,缺点是对信道噪声很敏感,会产生误差扩散。即某一位码出错,对图像一维预测来说,将使该像素以后的同一行各个像素都产生误差;而对二维预测,该码引起的误差还将扩散到以下的各行。这样,将使图像质量大大下降。同时,DPCM 的压缩率也比较低。随着变换编码的广泛应用,DPCM 的作用已很有限。
三.ADPCM
进一步改善量化性能或压缩数据率的方法是采用自适应量化或自适应预测,即自适应脉冲编码调制(ADPCM )。它的核心想法是:①利用自适应的思想改变量化阶的大小,即使用小的量化阶(step-size)去编码小的差值,使用大的量化阶去编码大的差值,②使用过去的样本值估算下一个输入样本的预测值,使实际样本值和预测值之间的差值总是最小。它的编码简化框图如图04-01-5所示。
图04-01-5 ADPCM方框图
1.自适应量化
在一定量化级数下减少量化误差或在同样的误差条件下压缩数据,根据信号分布不均匀的特点,希望系统具有随输入信号的变化区间足以保持输入量化器的信号基本均匀的能力,这种能力叫自适应量化。
自适应量化必须有对输入信号的幅值进行估值的能力,有了估值才能确定相应的改变量。若估值在信号的输入端进行,称前馈自适应;若在量化输出端进行,称反馈自适应。信号的估值必须简单,占用时间短,才能达到实时处理的目的。
2.自适应预测
预测参数的最佳化依赖信源的特征,要得到最佳预测参数显然是一件繁琐的工作。而采用固定的预测参数往往又得不到较好的性能。为了能使性能较佳,又不致于有太大的工作量,可以采用自适应预测。
为了减少计算工作量,预测参数仍采用固定的,但此时有多组预测参数可供选择,这些预测参数根据常见的信源特征求得。编码时具体采用哪组预测参数需根据特征来自适应地确定。为了自适应地选择最佳参数,通常将信源数据分区间编码,编码时自动地选择一组预测参数,使该实际值与预测值的均方误差最小。随着编码区间的不同,预测参数自适应地变化,以达到准最佳预测。
四.帧间预测编码
帧间预测编码是利用视频图像帧间的相关性,即时间相关性,来达到图像压缩的目的,广泛用于普通电视、会议电视、视频电话、高清晰度电视的压缩编码。
在图像传输技术中,活动图像特别是电视图像是关注的主要对象。活动图像是由时间上以帧周期为间隔的连续图像帧组成的时间图像序列,它在时间上比在空间上具有更大的相关性。大多数电视图像相邻帧间细节变化是很小的,即视频图像帧间具有很强的相关性,利用帧所具有的相关性的特点进行帧间编码,可获得比帧内编码高得多的压缩比。对于静止图像或活动很慢的图像,可以少传一些帧,如隔帧传输,未传输的帧,利用接收端的帧存储器中前一帧的数据作为该帧数据,对视觉没有什么影响。因为人眼对图像中静止或活动慢的部分,要求有较高的空间分辨率,而对时间分辨率的要求可低些。这种方法叫帧重复方法,广泛应用于视频电话、视频会议系统中,其图像帧速率一般为1~15帧/秒。
采用预测编码的方法消除序列图像在时间上的相关性,即不直接传送当前帧的像素值,而是传送x 和其前一帧或后一帧的对应像素x ' 之间的差值, 这称为帧间预测。当图像中存在着运动物体时,简单的预测不能收到好的效果,例如在图04-01-6中当前帧与前一帧的背景完全一样,只是小球平移了一个位置,如果简单地以第k-1帧像素值作为k 帧的预测值,则在实线和虚线所示的圆内的预测误差都不为零。如果已经知道了小球运动的方向和速度,可以从小球在k-1帧的位置推算出它在k 帧中的位置来,而背景图像(不考虑被遮挡的部分)仍以前一帧的背景代替,将这种考虑了小球位移的k-1帧图像作为k 帧的预测值,就比简单的预测准确得多,从而可以达到更高的数据压缩比。这种预测方法称为具有运动补偿的帧间预测。
图 04-01-6 帧间预测与具有运动补偿的帧间预测
具有运动补偿的帧间预测编码是视频压缩的关键技术之一,它包括以下几个步骤:首先,将图像分解成相对静止的背景和若干运动的物体,各个物体可能有不同的位移,但构成每个物体的所有像素的位移相同,通过运动估值得到每个物体的位移矢量;然后,利用位移矢量计算经运动补偿后的预测值;最后对预测误差进行量化、编码、传输,同时将位移矢量和图像分解方式等信息送到接收端。图04-01-7示出了具有运动补偿的帧间预测器的原理框图。
图04-01-7 具有运动补偿的帧间预测器功能框图
在具有运动补偿的帧间预测编码系统中,对图像静止区和不同运动区的实时完善分解和运动矢量计算是较为复杂和困难的。在实际实现时经常采用的是像素递归法和块匹配法两种简化的办法。
像素递归法的具体作法是,仍需通过某种较为简单的方法首先将图像分割成运动区和静止区。在静止区内像素的位移为零,不进行递归运算;对运动区内的像素,利用该像素左边或正上方像素的位移矢量D 作为本像素的位移矢量,然后用前一帧对应位置上经位移D 后的像素值作为当前帧中该像素的预测值。如果预测误差小于某一阈值,则认为该像素可预测,无需传送信息;如果预测误差大于该阈值,编码器则需传送量化后的预测误差、以及该像素的地址,收、发双方各自根据量化后的预测误差更新位移矢量。由此可见,像素递归法是对每一个像素根据预测误差递归地给出一个估计的位移矢量,因而不需要单独传送位移矢量给接收端。
块匹配法是另一种更为简单的运动估值方法。它将图像划分为许多子块,并认为子块内所有像素的位移量是相同的,这意味着将每个子块视为一个“运动物体”。对于某一时间t, 图像帧中的某一子块如果在另一时间t-t 1的帧中可以找到若干与其十分相似的子块,则称其中最为相似的子块为匹配块,并认为该匹配块是时间t-t 1的帧中相应子块位移的结果。位移矢量由两帧中相应子块的坐标决定。
考虑到一定时间间隔内物体可能的运动速度、运动范围和匹配搜索所需的计算量,在匹
配搜索时一般仅在一个有限范围内进行。假设在给定时间间隔内最大可能的水平和垂直位移
为d h和d v个像素,则搜索范围SR 为
其中M 、N 为子块的水平和垂直像素数。
在块匹配方法中需要解决两个问题:一是确定判别两个子块匹配的准则;二是寻找计算量最少的匹配搜索算法。判断两个子块相似程度的准则可以利用两个块间归一化的二维互相关函数、两子块间亮度的均方差MSE 或两子块间亮度差绝对值的均值MAD 等。通过对不同判别准则的比较研究表明,各种判别准则对位移矢量的估值精度影响差别不是很大。由于MAD 准则的计算不含有乘法和除法运算而成为最常使用的匹配判别准则。MAD 准则定义如下:
其中X k 和X k-1分别表示图像在第k 帧和第k-1帧的像素值。当MAD 最小时,表示两个子块匹
配。
对于匹配搜索算法,最简单和直接的方法就是全搜索方式,即将第k-1帧中的子块在整个搜索区内逐个像素移动,每移动一次计算一次判决函数。总的移动次数为 (2d h + 1)(2d v +
1) 。当d h = d v = 6时,总的计算次数为169。显然,全搜索的运算量是相当大的。为了加快搜索过程,人们提出了许多不同的搜索方法,其中应用较广的有二维对数法、三步法、共轭方向法和正交搜索法。这几种方法都基于如下的假设:当偏离最小误差方向时,判决函数是单调上升的,搜索总沿着判决函数值减小的方向进行。上述几种方案所需的搜索步骤和计算点数略有差异,但基本思路是一致的。
通过上面介绍的两种运动矢量估值方法可以看出,像素递归法对每一个像素给出一个估计的位移矢量,因而对较小面积物体的运动估值较为精确。但像素递归法在估值时需要进行叠代运算,从而存在着收敛速度和稳定性问题。块匹配法对同一子块内位移量不同的像素只能给出同一个位移估值,限制了对每一像素的估值精度。但对于面积较大的运动物体而言,采用块匹配法的预测要比采用像素递归法的预测效果好。另外,从软硬件实现角度看,块匹配算法相对简单,在实际活动图像压缩编码系统中得到较为普遍的应用。
五.活动图像帧间内插
在具有运动补偿的预测编码系统中,利用了活动图像帧间信息的相关性,通过对相邻帧图像的预测误差进行编码而达到压缩数据的目的。运动补偿技术的引入,大大提高了预测精度,使传输每一帧图像的平均数据量进一步降低。在此系统中图像的传输帧率并没有变化,仍与编码前的帧率一样。然而在某些应用场合如可视电话、视频会议等,对图像传输帧率的要求可适当降低,这就为另外一种称为帧间内插的活动图像压缩编码方法提供了可能。
活动图像的帧间内插编码是在系统发送端每隔一段时间丢弃一帧或几帧图像,而在接收端再利用图像的帧间相关性将丢弃的帧通过内插恢复出来,以防止帧率下降引起闪烁和动作不连续。恢复丢弃帧的一个简单办法是利用线性内插,设x(i, j), y(i, j)分别代表两个传输帧中相同空间位置上像素的亮度,在中间第n 个内插帧对应位置的亮度z(i, j) 可用如下的内插公式:
n=1,2,3,……N-1
其中N 为两个传输帧之间的帧间隔数。
简单线性帧间内插的缺点在于当图像中有运动物体时,两个传输帧在物体经过的区域上不再一一对应,因而引起图像模糊。如图04-01-8所示,为解决这一问题可采用带有运动补偿的帧间内插。具有运动补偿的帧间内插和帧间预测都需要进行运动估值,但二者的目的和运动估值不准确所带来的影响不完全相同。
图04-01-8 帧间内插示意图
在帧间预测中引入运动补偿的目的是为了减少预测误差,从而提高编码效率。运动估值的不准确会使预测误差加大,从而使传输的数据率上升,但接收端据此位移矢量和预测误差解码不会引起图像质量下降。而在帧间内插中引入运动补偿的目的,是使恢复的内插帧中的运动物体不致因为内插而引起太大的图像质量下降。这是由于在丢弃帧内没有传送任何信息,要确定运动物体在丢弃帧中的位置必须知道该物体的运动速度。运动估值的不准确,将导致内插出来的丢弃帧图像的失真。另外,在帧间内插中的位移估值一般要对运动区的每一个像素进行,而不是对一个子块;否则,内插同样会引起运动物体边界的模糊。因此,在帧间内插中较多使用能够给出单个像素位移矢量的像素递归法。
其他还有阈值法(只传送像素亮度的帧间差值超过一定阈值的像素)、帧内插(对于活动缓慢的图像,利用前后两帧图像进行内插,得到预测图像,然后对帧差信号进行编码)、运动估计与补偿等。
第 2 节 变换编码
预测编码的压缩能力是有限的。以DPCM 为例,一般只能压缩到每样值2~4比特。20世纪70年代后,科学家们开始探索比预测编码效率更高的编码方法。人们首先讨论了KL 变换
(Karhunen-Loeve Transform)、傅立叶变换等正交变换,得到了比预测编码效率高得多的结果,但苦于算法的计算复杂性太高,进行科学研究可以,实际使用起来很困难。直到20世纪70年代后期,研究者发现离散余弦变换DCT 与KL 变换在某一特定相关函数条件下具有相似的基向量,而用DCT 的变换矩阵来做正交变换就可以节省大量的求解特征向量的计算,因而大大简化了算法的计算复杂性。DCT 的使用使变换编码压缩进入了实用阶段。小波变换是继DCT 之后科学家们找到的又一个可以实用的正交变换,它与DCT 各有千秋,因而分别被不同的研究群体所推崇。
一.变换的基本原理
变换编码是指先对信号进行某种函数变换,从一种信号(空间)变换到另一种(空
间),然后再对信号进行编码。如将时域信号变换到频域,因为声音、图像大部分信号都是
低频信号,在频域中信号的能量较集中,再进行采样、编码,那么可以肯定能够压缩数据。
变换编码系统中压缩数据有变换、变换域采样和量化三个步骤。变换本身并不进行数据压缩,它只把信号映射到另一个域,使信号在变换域里容易进行压缩,变换后的样值更独立和有序。这样,量化操作通过比特分配可以有效地压缩数据。
在变换编码系统中,用于量化一组变换样值的比特总数是固定的,它总是小于对所有变换样值用固定长度均匀量化进行编码所需的总数,所以量化使数据得到压缩,是变换编码中不可缺少的一步。在对量化后的变换样值进行比特分配时,要考虑使整个量化失真最小。
变换编码是一种间接编码方法。它是将原始信号经过数学上的正交变换后,得到一系列的变换系数,再对这些系数进行量化、编码、传输。图04-02-1是变换编码系统方框图。
图04-02-1 变换编码、解码原理框图
图中接收端输出信号与输入信号的误差是因为输入端采用量化器的量化误差所致。当经过正交变换后的协方差矩阵为一对角矩阵,且具有最小均方误差时,该变换称为最佳变换,也称Karhunen-Loeve 变换(K-L 变换)。如果变换后的协方差矩阵接近对角矩阵,该类变换称为准最佳变换,典型的有DCT (离散余弦变换)、DFT (离散傅立叶变换)、WHT 等。
二.K-L 变换
K-L 变换( Karhunen-Loeve Transform)是建立在统计特性基础上的一种变换,有的文献也称为霍特林(Hotelling )变换,因他在1933年最先给出将离散信号变换成一串不相关系数的方法。K-L 变换的突出优点是相关性好,是均方误差(MSE ,Mean Square Error)意义下的最佳变换,它在数据压缩技术中占有重要地位。
假定一幅N x N的数字图像通过某一信号通道传输M 次,由于受随机噪音干扰和环境条件影响,接收到的图像实际上是一个受干扰的数字图像集合
对第i 次获得的图像 f i (x,y) ,可用一个含 N 2 个元素的向量 Xi 表示,即
该向量的第一组分量(N 个元素)由图像fi (x,y) 的第一行像素组成,向量的第二组分量
由图像 f i(x,y) 的第二行像素组成,依此类推。也可以按列的方式形成这种向量,方法类似。
X 向量的协方差矩阵定义为:
m f 定义为:
C f 和 m f 的表达式中,“ E ”是求期望。
对于M 幅数字图像,平均值向量 m f 和协方差矩阵 C f 可由下述方法近似求得:
可以看出, m f 是 N2 个元素的向量, C f 是 N2 x N2 的方阵。
根据线性代数理论,可以求出协方差矩阵的 N2 个特征向量和对应的特征值。假定
是按递减顺序排列的特征值,对应的特征向量
e i =
则K-L 变换矩阵A 定义为: 。
从而可得K-L 变换的变换表达式为:
该变换式可理解为,由中心化图像向量 X - mx 与变换矩阵A 相乘即得到变换后的图像向量Y 。Y 的组成方式与向量X 相同。
K-L 变换虽然具有MSE 意义下的最佳性能,但需要先知道信源的协方差矩阵并求出特征值。求特征值与特征向量并不是一件容易的事,维数较高时甚至求不出来。即使能借助计算机求解,也很难满足实时处理的要求,而且从编码应用看还需要将这些信息传输给接收端。这些因素造成了K-L 变换在工程实践中不能广泛使用。人们一方面继续寻求解特征值与特征向量的快速算法,另一方面则寻找一些虽不是“最佳”、但也有较好的去相关与能量集中的性能且容易实现的一些变换方法。而K-L 变换就常常作为对这些变换性能的评价标准。
三.离散傅立叶变换
给定由N 个信号样本(均匀间隔){x(0),x(1),…,x(n-1)}组成的信号序列,离散傅立叶变换(DFT,Discrete Fourier Transform)可用下式给出:
X(u) =DFT 的反变换可表示为:
u = 0,1,2,…,N-1
x(k) =k = 0,1,2,…,N-1 给定一个二维信号的样本序列{x(k,l), k=0,1,…, N-1, l=0,1,…,N-1},二维离散傅立叶变换(2D-DFT )可用下式给出:
X(u,v) =
2D-DFT的反变换可表示为:
x(k,l) =
k,l = 0,1,2,…,N-1
u,v = 0,1,2,…,N-1
傅立叶变换有很多有用的性质。其中一个是,傅立叶变换有明确的物理意义,即时-空域与频域的映射关系。已经发展了一套快速傅立叶变换(FFT,Fast Fourier Transform)的计算机算法,促进了它在信号处理中的应用,特别是在语音处理中的应用。在图像处理中,研究表明,离散余弦变换(DCT,Discrete Cosine transform)效果比DFT 好些(图04-02-
2),因此更多地应用DCT 。
(a )原始图形
(B )从DCT 恢复 (C )从DFT 恢复
图04-02-2 DCT和DFT 的比较例
四.离散余弦变换
(一)一维离散余弦变换(DCT)的正变换核由下述关系式给出,即
(x=0,1,2, …,N-1;u=1,2, …,N-1) 对应的离散余弦变换可表示为:
C(u) =
u=1,2,…N-1
式中 为f(x)(x=0,1,2,…N-1)的离散余弦变换(DCT )。若取反变换核与正变换核相同,则可定义离散余弦变换为:
(x=0,1,2,…N-1)
(二)二维离散余弦变换
二维离散余弦变换的正反变换核相同,即
(u=1,2,…M-1; v=1,2,…N-1)
对应离散余弦变换为:
(u=1,2,…M-1; v=1,2,…N-1)
离散余弦逆变换为:
(x=1,2,…M-1; y=1,2,…N-1)
二维离散余弦变换的变换核是可分离的,因而可通过两次一维变换实现一个二维变换。
图04-02-3 DCT和IDCT例
五.离散沃尔变换
当N=2n 时,可以得到函数 f(x) 的离散沃尔什( Walsh )变换( W ( u )):
b k (z)是z 的二进制表达式列中的第k 位。例如n=3,则对z=6,其二进制数为110,有b 0(z)=0,b1(z)=1,b2(z)=1。
由沃尔什变换核组成的矩阵是一个对称矩阵,且其行和列正交。这些性质表明反变换与正变换核只差1个常数1/N,即:
所以离散沃尔什反变换为:
由于一维沃尔什变换正变换和反变换只差一个常数项1/N,所以用于正变换的算法也可用于反变换。一维沃尔什正变换和反变换核由以下两式给出:
这两个核完全相同,所以下面两式给出的二维沃尔什正变换和反变换也具有相同形式:
沃尔什正变换核和反变换都是可分离的和对称的,有:
因此,二维的沃尔什正反变换都可分成两个步骤计算,每个步骤用1个一维变换实现。 沃尔什变换可用类似于FFT 算法快速地计算,只需要将那里的指数项设为1
即可。快速沃
尔什变换简写为FWT 。两式对应,有:
六.离散哈达玛变换
哈达玛变换与沃尔什变换相似,所以有些参考书上把二者统称为沃尔什-哈达玛变换。
(一)一维离散哈达玛变换
当N=2n 时,一维哈达玛正变换核和反变换核相似。一维哈达玛变换对可表示为:
(u = 0,1,2,…, N-1)
(x = 0,1,2,…, N-1)
哈达玛变换核除了因子1/N之外,由一系列的+1和-1组成。如N=8时的哈达玛变换核用矩阵表示为:
由此矩阵可得出一个非常有用的结论,即2N 阶的哈达玛变换矩阵可由N 阶的变换矩阵按下述规律形成:
而最低阶(N=2)的哈达玛变换矩阵为:
此性质导出了一种快速哈达玛变换(FHT ),利用这个性质求N 阶(N=2 n
)的哈达玛变
换矩阵要比直接用定义式求此矩阵速度快得多。
(二)二维离散哈达玛变换
二维离散哈达玛变换的正变换核和反变换核相同,为:
这里M=2 m ,N=2n 。则对应的二维哈达玛变换对可表示为:
一个二维变换。 可以看出,二维离散哈达玛变换的正反变换核具有可分离性,因此可以通过两次一维变换来实现
七.小波变换
长期以来,傅立叶分析一直被认为是最完美的数学理论和最实用的方法之一。但是用傅立叶分析只能获得信号的整个频谱,而难以获得信号的局部特性,特别是对于突变信号和非平稳信号难以获得希望的结果。
为了克服经典傅立叶分析本身的弱点,人们发展了信号的时频分析法,1946年Gabor 提出的加窗傅立叶变换就是其中的一种,但是加窗傅立叶变换还没有从根本上解决傅立叶分析的固有问题。小波变换的诞生,正是为了克服经典傅立叶分析本身的不足。
(一)连续小波变换
所谓小波(wavelet )是由满足条件:
(1)
(2)
) (其中
的解析函数经过平移、缩放得到的正交函数族
小波变换(WT ,Wavelet Transform)是用小波函数族ψa,b (t)按不同尺度对函数f(t)∈L 2 (R) 进行的一种线性分解运算:
对应的逆变换为:
小波变换有如下性质:
(1)小波变换是一个满足能量守恒方程的线形运算,它把一个信号分解成对空间和尺度(即时间和频率)的独立贡献,同时又不失原信号所包含的信息;
(2)小波变换相当于一个具有放大、缩小和平移等功能的数学显微镜,通过检查不同放大倍数下信号的变化来研究其动态特性;
(3)小波变换不一定要求是正交的,小波基不惟一。小波函数系的时宽-带宽积很小,且在时间和频率轴上都很集中,即展开系数的能量很集中;
(4)小波变换巧妙地利用了非均匀的分辨率,较好地解决了时间和频率分辨率的矛盾;在低频段用高的频率分辨率和低的时间分辨率(宽的分析窗口),而在高频段则用低的频率分辨率和高的时间分辨率(窄的分析窗口),这与时变信号的特征一致;
(5)小波变换将信号分解为在对数坐标中具有相同大小频带的集合,这种以非线形的对数方式而不是以线形方式处理频率的方法对时变信号具有明显的优越性;
(6)小波变换是稳定的,是一个信号的冗余表示。由于a 、b 是连续变化的,相邻分析窗的绝大部分是相互重叠的,相关性很强;
(7)小波变换同傅立叶变换一样,具有统一性和相似性,其正反变换具有完美的对称性。小波变换具有基于卷积和QMF 的塔形快速算法。
(二)离散二进小波变换
在实际应用中,常常要把连续小波变换离散化。若对连续小波变换ωƒ(a, b)的伸缩因子a 和b 进行采样,选取a=2-j ,b=2-j kb0,则可得到离散的二进小波变换;
这里j, k ∈ Z,采样率b 0 > 0.
由于离散二进小波变换是对连续小波变换的伸缩因子和平移因子按一定规则采样而得到的,因此,连续小波变换所具有的性质,离散二进小波变换一般仍具备。
(三)Mallat 算法
Mallat 算法是便于计算机软件和硬件实现的快速离散算法。这是Mallat 在Burt 和Adelson 的图像分解和重构的塔式算法的启发下,根据多分辨率框架提出的算法。此算法在小波分析中的地位相当于FFT 在经典傅立叶分析的地位。
按Mallat 算法,我们可以把函数f(x)
分解为不同频率通道的成分,并把每一频率通道的
成分按相位进行分解,频率越高,相位划分越细,频率越低,相位划分越粗。Mallat 算法完全是离散的,便于数值计算。
八.图像变换编码补充
图像数据经正交变换后,其变换系数具有相互独立的性质。以二维傅立叶变换来说,频谱幅值大的变换系数均集中在低频部分,这几乎占了图像信息的90%,而高频部分的幅值均很小或趋于零。因而,我们完全可以仅对低频的变换系数采用量化、编码、传输,而高频部分既不编码,也不传输,达到图像数据压缩的目的。早期的图像变换编码就是采用傅立叶变换编码进行的,由于它有快速算法容易在硬件中实现,所以获得在一定范围内应用。
从数学角度看,可以提供许多正交变换方法来应用于图像的压缩编码。除傅立叶变换、Walsh-Hadmard 变换外,还有正弦变换、余弦变换、斜变换、哈尔变换、K-L 变换等。不同的变换会有不同的压缩效果(压缩比和重建的图像品质)。以傅立叶编码为例,高频信息去除得越多,越有可能获得大的压缩比,但同时却降低了重建图像的分辨率。数学证明,采用均方差最小准则,K-L 变换(即离散信号的Hotelling 变换)具有最佳变换性质,而且随子像块分割大小不同,误差大小不同。对几种变换进行比较后可以发现,余弦变换的均方差最接近K-L 变换,除傅立叶变换外,其他几种变换,当子像块超过16x16时,误差下降很慢。大方块尺寸时,傅立叶变换趋向于K-L 变换。正是这个原因,在目前所采用的变换编码方法中,余弦变换是应用最为广泛的一种。
在实用变换编码中,常用变换区域编码和变换阈值编码两种方法。
图像数据通过变换操作本身并不能降低码率。然而,根据变换系数集中在低频区域的特点可以采用编码技术来压缩数据。由于低频区集中在变换域的左上角,可对该区域的变换进行量化、编码、传输,对右下角区域既不编码又不传输即可达到压缩目的。这种编码方法就称为变换区域编码。区域编码压缩比可达到5:1,缺点是由于高频分量被丢弃,使图像分辨率下降。
为解决区域编码存在的问题,在变换编码中有另一种编码方法——阈值编码法。事先设定一个阈值,只对其变换系数的幅值大于此阈值的编码。这样,致使低频成分不仅保留,而且某些高频成分也被选择编码。重建图像时,品质得到改善。由于这种编码方法不是局限在图像数据的固定区域,而大于阈值的变换系数的幅值大小要量化、编码,而且对其系数所处的位置也要编码。因而较区域编码法复杂。如果能根据子像块的细节多少或子像块的亮度分层分布来自动调整阈值,则阈值编码可做到自适应。
第 3 节 基于模型编码
从80年代中后期开始,科学家们开始探讨基于模型的编码,并在包括人脸图像的编码等应用中使用。如果把以预测编码和变换编码为核心的基于波形的编码作为第一代编码技术,则基于模型的编码就是第二代编码技术。
N. Jayant指出,压缩编码的极限结果原则上可通过那些能够反映信号产生过程最早阶段的模型而得到。这就是基于模型编码的思想。一个例子是人类发音的“清晰声带-声道模型”(The Articulatory Vocal Cord-Vocal Tract Model),它把注意焦点从线性预测编码
(LPC ,Linear Predictive Coding)分析扩展到声道区分析,原则上为很低码率矢量量化提供了强得多的定义域,并允许更好地处理声带-声道的相互作用。另一个例子是人脸的线框(wire-frame )模型,它为压缩可视电话这类以人脸为主要景物的序列图像提供了一个强有
力的手段。
基于模型图像编码首先由瑞典Forchheimer 等人于1983年提出。基于模型方法的基本思想是:在发送端,利用图像分析模块对输入图像提取紧凑和必要的描述信息,得到一些数据量不大的模型参数;在接收端,利用图像综合模块重建原图像,是对图像信息的合成过程。基本原理如图04-03-1所示。
图04-03-1 基于模型的图像编码基本原理框图
与经典方法中的预测编码方法类似,基于模型编码在发送端既有分析用的编码器,同时又有综合用的解码器。只有这样,在发送端才能获得与接收端相同的综合后的重建图像,并将后者与原始图像进行“比较”,以确定图像失真是否低于“某种阈值”,以便修正模型参数。
同经典方法比较,基于模型编码还有两点显著不同:
一是编码失真。基于模型编码所引起的失真已从传统方法的量化误差转化为几何失真,并可能进一步转化为物理失真或行为失真。
二是如何评价重建图像质量。传统的以像素为单位计算原始图像与重建图像之间“逼真度”(如均方误差、信噪比)不能测量几何失真和物理失真等,从原理上讲根本不适用于基于模型编码。
表04-03-1列出了基于模型的图像编码技术分类。下面介绍两种技术:一种是基于语义编码,一种是基于物体编码。
表04-03-1 基于模型的图像编码技术分类
类别信源模型 编码的信息
典型编码技术
/表情单元 一. 基于语义编码
基于语义(semantic-based )编码采用显示模型(如人物的头肩部分)去分析和合成运动图像,景物里的物体三维模型为严格已知。瑞典Forchheimer 等人于1983年提出的就是基于语义图像编码。由于物体模型的有效性,景物中的物体能够在语义水平描述。它可以有效地利用景物中已知物体的知识,实现非常高的压缩比。但它仅能够处理已知物体,并需要较复杂的图像分析与识别技术。
为了实现基于语义的图像编码,需要根据景物中特定的一些物体,预先建立它们的通用3D 模型,最常用的是3D 线框模型。3D 线框模型由顶点在3D 空间运动的互连多角形复合而成,将色彩信息映射到该模型上就能实现合成。例如,人物头部3D
线框模型不仅给出面部的几何
形状,而且提供了面部表情的描述。面部表情的变化(例如眨眼、张嘴)可用面部动作编码系统(FACS , Facial Action Coding System)中的动作单元(AU ,Action Unit)来描述。FACS 给出一个包含了人脸可能产生的全部基本动作(即AU )的集合,而AU 是无法分成更小动作的最小动作。把许多AU 按照不同的组合方式一起发生,就形成了脸上的丰富表情。
下面以视频电话为例说明。在开始通信时,首先把双方的基本特征(例如3D 模型、脸部的表面纹理等)传输到对方,建立一个与特定人脸匹配的3D 模型。接下来,随着头部的运动和表情的变化,发送端抽取头部的运动参数和脸部的表情参数,编码后传送到对方;接收端根据已知的3D 模型和接收到的各种参数,用图像综合技术获得重建图像。系统的关键技术是:
(1)人物头、脸及肩部(简称人脸)3D 模型的建立;
(2)运动参数和表情参数的估计;
(3)图像综合。
为了使已建立的人脸3D 模型如同真实人脸一样“动”起来,必须根据先验知识对脸部进行分析,提取有关的头部特征参数及运动状态参数。基于语义常用的人脸部模型见图04-03-2,基于语义编码原理如图04-03-3所示。
基于语义图像编码基于限定景物,且景物中物体的3D 模型严格已知,这样可以有效利用景物中已知物体的知识,只需编码一些有限的描述变化信息的参数,因而压缩比非常惊人。但它仅能处理已知物体,实际情况稍有变化,就可能出现模型失效(例如,在眼部线框密度不够大而出现眨眼动作的时刻,出现较大失真)。此外,基于语义编码还需要较复杂的信号分析与识别技术。
图04-03-2 基于语义编码常用的3D 人脸模型(Candide 模型)
(a) (b) (c)
(a) 原始图像
(b) 人物模型
(c) 背景图像
图04-03-3 基于语义编码在视频中的应用
因此,基于语义图像编码还不能适合于所有的视频图像信号。在大多数的情况下,视频图像信号所表现的自然界是多种多样的,够造不出比较合适的模型来表现。目前,基于模型法还是多应用于特定的场合,如上述的视频电话。
二. 基于物体编码
德国Hannover 大学的Musman 教授在1989年提出的基于物体(object-based或object-
oriented) 图像编码是针对未知物体的,需要实时构造物体的模型(没有先验知识的)。基于物体编码不采用显示模型,适用于处理更一般的已知或未知的物体,因此预期有更广泛的应用前景。
处理时,首先运用图像分析技术,对景物进行分层次的描述,将物体与背景分割出来。对于分割后得到的每个实际三维物体,分别用一个物体模型来描述,并用该模型物体在二维图像平面上的投影(模型图像)来逼近真实图像。基于物体编码只追求最终模型能与输入图像一致,不要求模型物体与真实物体的形状严格一致。因此,假设模型是一个具有一般意义的模型,它既可以是二维的,也可以是三维的。每个分割出来的实际运动物体,用运动参数集、形状参数集和色彩参数集进行描述,然后再对这三个参数集进行编码与传送。根据所假设的物体模型不同,参数集会有些变化。现在基于物体编码所用的模型有4种:2D 刚体模型,2D 柔体模型,3D 刚体模型,3D 柔体模型。
对于活动图像的基于物体编码系统的核心技术是景物的分层次描述、运动估值和运动分割。从原理上讲,因无需模式识别与先验知识,且不受可视电话中头肩图像那样的限制,对于图像分析要简单得多,因而有更广泛的应用前景。但因未能充分利用景物的知识,或只能在低层次上运用物体知识,编码效率不如基于语义方法。因此应根据实际需要来决定具体选用哪一类方法。
目前,基于模型编码进一步的研究方向是把基于物体编码与基于语义编码等结合起来,取长补短。
第 4 节 分形编码
一.分形编码的思路
1988年1月,美国Georgia 理工学院的M. F. Barnsley在BYTE 发表了分形压缩方法。分形编码法(Fractal Coding )的目的是发掘自然物体(比如天空、云雾、森林等)在结构上的自相似形,这种自相似形是图像整体与局部相关性的表现。分形压缩正是利用了分形几何中的自相似的原理来实现的。首先对图像进行分块,然后再去寻找各块之间的相似形,这里相似形的描述主要是依靠仿射变换确定的。一旦找到了每块的仿射变换,就保存下这个仿射变换的系数,由于每块的数据量远大于仿射变换的系数,因而图像得以大幅度的压缩。
分形编码以其独特新颖的思想,成为目前数据压缩领域的研究热点之一。分形编码、基于模型编码与经典图像编码方法相比,在思想和思维上有了很大的突破,理论上的压缩比可超出经典编码方法两三个数量级。
二.分形编码方法和步骤
以平面点集合与图像为例,迭代函数系统压缩编码大致步骤为:
1.图像分割
首先将原图(集合X 或图像)预分割(或预分解)为若干分形子图X (m) (m=1,2,…,M) ,使得每一个子图X (m)具有一定的分形结构,及其局部与整体之间保持某种相似特征。而这种子图分割可以是空间域分割,也可以是频率域或其他空间域分割。在总图像的分割中,常常把同类或者相近的物体放在同一子图中,而把不同的景物,如山脉、河流、沙漠、云雾、森林、草地等,分别置于不同的子图中。
2.提取迭代函数系统(IFS )代码
在分割完分形子图X (m)之后,对每一个分形子图提取IFS 代码,其方法是:
将子图X (m)置于计算机屏幕上,利用人机对话方式,对X (m)进行压缩处理(可伸缩、平移、旋转和仿射等),生成X (m)的一个仿射图X (m)j ,这个仿射图应该覆盖原始子图X (m)的一部分。于是可得所谓仿射变换
:X (m) X(m)j
(m)(m)(m)即通过仿射变换 ,由子图X 生成X 的仿射图X j 。
3.对IFS 代码进行编码
获得了原图的IFS 代码之后,可按子图X (m)或仿射图X (m)j 的预测加权,用常规编码方法对IFS 代码进行编码。
三.分形编码的特点
分形编码的最显著的特点是自相似性(self-similarity )。与经典方法相比,它不但去除了数据之间局部的相关性,而且去除整体与局部之间的相关性,所以有望达到经典编码方法所达不到的压缩比,是一种思想全新、很有潜力的编码技术。分形编码的主要特点有:
(1)分形编码的图像压缩比经典编码方法的压缩比高出许多;
(2)由于分形编码可把图像划分成大得多、形状复杂得多的区分,故压缩所得的文件的大小不会随着图像像素数目的增加即分辩率的提高而变大。而且,分形压缩还能依据压缩时确定的分形模型给出高分辨率的清晰的边缘线,而不是将其作为高频分量加以抑制;
(3)分形压缩和解压缩不对称,压缩较慢,而解压缩很快。这是由于对每块确定仿射变换时,要对整幅图像进行相似性搜索,因而较慢。而恢复时只需简单的反复叠代过程,因而较快。
第 5 节 其他编码
一.子带编码
子带编码(SBC ,Sunband Coding)是一种在频率域中进行数据压缩的方法。在子带编码中,首先用一组带通滤波器将输入信号分成若干个在不同频段上的子带信号,然后将这些子带信号经过频率搬移转变成基带信号,再对它们在奈奎斯特速率上分别重新取样。取样后的信号经过量化编码,并合并成一个总的码流传送给接收端。在接收端,首先把码流分成与原来的各子带信号相对应的子带码流,然后解码、将频谱搬移至原来的位置,最后经带通滤波、相加,得到重建的信号。图04-05-1给出了子带编码、解码的工作原理图。
(a) 编码器
(b)解码器
图04-05-1 子带编码、解码工作原理图
在子带编码中,若各个子带的带宽ΔW k 是相同的,则称为等带宽子带编码,否则,称为变带宽子带编码。
对每个子带分别编码的好处是:
(1)可以利用人耳(或人眼)对不同频率信号的感知灵敏度不同的特性,在人的听觉(或视觉)不敏感的频段采用较粗糙的量化,从而达到数据压缩的目的。例如,在声音低频子带中,为了保护音调和共振峰的结构,就要求用较小的量化阶、较多的量化级数,即分配较多的比特数来表示样本值。而话音中的摩擦音和类似噪声的声音,通常出现在高频子带中,对它分配较少的比特数。
(2)各个子带的量化噪声都束缚在本子带内,这就可以避免能量较小的频带内的信号被其他频带中量化噪声所掩盖。
(3)通过频带分裂,各个子带的取样频率可以成倍下降。例如,若分成频谱面积相同的N 个子带,则每个子带的取样频率可以降为原始信号取样频率的1/N,因而可以减少硬件实现的难度,并便于并行处理。
1976年子带编码技术首次被美国贝尔实验室的R. E. Crochiere等人应用于语音编码。
下面以语音子带编码为例说明其过程。音频频带的分割可以用树型结构的式样进行划分。首先把整个音频信号带宽分成两个相等带宽的子带:高频子带和低频子带。然后对这两个子带用同样的方法划分,形成4个子带。这个过程可按需要重复下去,以产生2K 个子带,K 为分割的次数。用这种办法可以产生等带宽的子带,也可以生成不等带宽的子带。例如,对带宽为4000Hz 的音频信号,当K=3时,可分为8个相等带宽的子带,每个子带的带宽为500Hz 。也可生成5个不等带宽的子带,分别为[0,500), [500,1000) ,[1000,2000), [2000,3000) 和[3000,4000]。
把音频信号分割成相邻的子带分量之后,用2倍于子带带宽的采样频率对子带信号进行采样,就可以用它的样本值重构出原来的子带信号。例如,把4000Hz 带宽分成4个等带宽子带时,子带带宽为1000Hz ,采样频率可用2000Hz ,它的总采样率仍然是8000Hz 。
由于分割频带所用的滤波器不是理想的滤波器,经过分带、编码、译码后合成的输出音频信号会有混迭效应。据有关资料的分析,采用正交镜象滤波器(QMF ,q uandrature m irror f ilter )来划分频带,混迭效应在最后合成时可以抵消。
图04-05-2表示用正交镜象滤波器分割频带的子带编译码简化框图。图中,用QMF 把全带音频信号分割成两个等带宽子带。h H (n ) 和h L (n ) 分别表示高通滤波器和低通滤波器,它们组成一对正交镜象滤波器。这两个滤波器也叫做分析滤波器。图04-05-2(b)是QMF 简化的幅频特性。
(a) QMF分割频道方框图
(b) QMF幅频特性简化图
图04-05-2采用QMF 的子带编译码框图
子带编码器SBC 愈来愈受到重视。在中等速率的编码系统中,SBC 的动态范围
宽、音质高、成本低。使用子带编码技术的编译码器已开始用于话音存储转发
(voice store-and-forward)和话音邮件,采用2个子带和ADPCM 的编码系统也已由CCITT 作为G.722标准向全世界推荐使用。
1986年Woods 等将子带编码又引入到图像编码,此后子带编码在视频信号压缩领域得到了很大发展。目前,已经研制出采用子带编码技术的具有演播室质量的140Mbps HDTV硬件编解码系统。
二.矢量量化编码
矢量量化编码也是在图像、语音信号编码技术中研究得较多的新型量化编码方法,它的出现并不仅仅是作为量化器设计而提出的,更多的是将它作为压缩编码方法来研究的。在传统的预测和变换编码中,首先将信号经某种映射变换变成一个数的序列,然后对其一个一个地进行标量量化编码。而在矢量量化编码中,则是把输入数据几个一组地分成许多组,成组地量化编码,即将这些数看成一个k 维矢量,然后以矢量为单位逐个矢量进行量化。矢量量化是一种限失真编码,其原理仍可用信息论中的率失真函数理论来分析。而率失真理论指出,即使对无记忆信源,矢量量化编码也总是优于标量量化。图04-05-3示出了矢量量化编码的原理框图。
图04-05-3 矢量量化编码原理框图
图中输入信号是一个k 维矢量,该矢量原则上既可以是原始图像,也可以是图像的预测误差或变换矩阵系数的分块(或称分组)。码本C 是一个k 维矢量的集合,即C = {Yi }, i=1,2,…,N,它实际上是一个长度为N 的表,每个表的每个分量是一个k 维矢量,称为码字。矢量编码的过程就是在码本C 中搜索一个与输入矢量最接近的码字。衡量两个矢量之间接近程度的度量标准可以用均方误差准则:
也可以用其他准则,如:
传输时,只需传输码字Y i 的下标 i. 在接收端解码器中,有一个与发送端相同的码本C ,根据下标 i可简单地用查表法找到Y i 作为对应X 的近似。
当码本长度为N 时,为传输矢量下标所需的比特数为log 2N ,平均传输每个像素所需的比特数为(1/k)log 2N 。若k=16,N=256,则比特率为0.5bit/pixel.
在矢量量化编码中,关键是码本的建立和码字搜索算法。
码本的生成算法有两种类型,一种是已知信源分布特性的设计算法;另一种是未知信源分布,但已知信源的一列具有代表性且足够长的样点集合(即训练序列)的设计算法。可以证明,当信源是矢量平衡且遍历时,若训练序列充分长则两种算法是等价的。
码字搜索是矢量量化中的一个最基本问题,矢量量化过程本身实际上就是一个搜索过程,即搜索出与输入最为匹配的码矢。矢量量化中最常用的搜索方法是全搜索算法和树搜索算法。全搜索算法与码本生成算法是基本相同的,在给定速率下其复杂度随矢量维数K
以指数
形式增长,全搜索矢量量化器性能好但设备较复杂。树搜索算法又有二叉树和多叉树之分,它们的原理是相同的,但后者的计算量和存储量都比前者大,性能比前者好。树搜索的过程是逐步求近似的过程,中间的码字是起指引路线的作用,其复杂度比全搜索算法显著减少,搜索速度较快。由于树搜索并不是从整个码本中寻找最小失真的码字,因此它的量化器并不是最佳的,其量化信噪比低于全搜索。
三.感知编码
感知编码将感知知识应用于编码中。感知编码已经在声音编码中得到了应用。
心理声学模型中一个基本的概念就是听觉系统中存在一个听觉阈值,低于这个阈值的声音信号就听不到。听觉阈值的大小随声音频率的改变而改变,各个人的听觉阈值也不同。大多数人的听觉系统对2 kHz ~ 5 kHz之间的声音最敏感。一个人是否能听到声音取决于声音的频率,以及声音的幅度是否高于这种频率下的听觉阈值。显然,低于听觉阈值的信号在声音压缩时可以去掉。
心理声学模型中的另一个概念是听觉掩蔽效应,即一个强的语音信号可以掩盖一个相邻的弱信号。例如,同时有两种频率的声音存在,一种是1000 Hz的声音,另一种是1100 Hz的声音,但它的强度比前者低18分贝,在这种情况下,1100 Hz的声音就听不到。也许你有这样的体验,在一安静房间里的普通谈话可以听得很清楚,但在播放摇滚乐的环境下同样的普通谈话就听不清楚了。声音压缩算法也同样可以根据这种特性去掉更多的冗余数据。
图04-05-4 说明了感知编码的基本方法。方框图的大部分功能都是基于频域的,因为人的听觉过程很容易用频域法理解。感知编码的主要步骤是:首先将输入信号分解为各频谱元素,再根据某个心理听觉阈值和掩蔽门限进行量化编码,最后生成比特流。听觉阈值和掩蔽门限的计算需要对输入信号进行频域分解。我们可以采用与量化编码相同的频域分解方法,也可用到前面所说的独立分析方法。方法的选择要视复杂度和精度而定。
图04-05-4 感知编码策略的基本结构框图
分析滤波部件可以进行正交滤波分解,或者再加上某种离散变换。虽然离散变换可看成一个均匀子带滤波组,但二者的差别仍然存在。
无论听觉阈值和掩蔽门限的计算是基于原输入信号的分析还是基于独立的频域分析,其计算结果都可用于规定各频率元素编码的精度。计算结果可以是听觉阈值和掩蔽门限的集合,各频率元素所分配的比特数,或者是实现透明质量所需的频率相关的信噪比集合。
量化和编码都有很多种实现方法,从直接计算标量量化中的比特分配到利用分解综合系统都可以实现量化编码。这里所说的分析滤波是指先比较量化与非量化的频谱元素,找到每个频谱元素的量化噪声,最后将此噪声与听觉阈值和掩蔽门限比较。
〖参考文献〗
P.K. Andleigh & K. Thakrar, "多媒体系统设计(Multimedia System Design)", 徐光佑、史元春译,电子工业出版社, 1998.
F. Kuo & W. Effelsberg, "Multimedia Communication: Protocols And
Applications", Prentic Hall, 1997.
Ralf Steinmetx & Klara Nahrstedt,《多媒体技术:计算、通信和应用》,潘志庚、叶绿、耿卫东等译,清华大学出版社,2000。
林福宗,《多媒体技术基础》,清华大学出版社,2000年8月。
蔡安妮,孙景鳌编著,《多媒体通信技术基础》,电子工业出版社,2000年8月。 黄孝建编著,《多媒体技术》,北京邮电大学出版社,2000年9月。
胡晓峰,吴玲达,老杨松,司光亚编著,《多媒体技术教程》,人民邮电出版社,2002年1月。
〖相关网站〗
清华大学林福宗《多媒体技术基础》http:www.tsinghua.edu.cn/
〖练习和思考题〗
1. 下图是DM编码器的原理图,如果你已经学过模拟电路和数字电路技术基础,请分析该电路是如何完成增量调制编码的。
编码器原理图
2. 自适应脉冲编码调制(APCM)的基本思想是什么?
3. 差分脉冲编码调制(DPCM)的基本思想是什么?
4. 自适应差分脉冲编码调制(ADPCM)的两个基本思想是什么?
5. 扼要叙述DPCM及运动补偿的基本原理和方法。
6. 说明DCT变换编码的基本方法。
7. 子带编码的优越性是什么?