利用离散余弦变换进行图像压缩的方法_沙磊

第24卷　第3期　1997年7月　　　成都理工学院学报　　　JO U R NA L O F CHENG DU U NI VER SI T Y OF T ECHN OL O GY V ol. 24N o. 3Jul. 1997　

利用离散余弦变换进行图像压缩的方法

(成都理工学院信息工程与地球物理系) 　　(煤炭科学研究院西安分院) 【摘要】采用复杂图像的程序在每一种计算机应用领域都能见到, 随着图形图像所需存储量的激增和廉价数字信号处理芯片的出现, 有效的图像有损压缩技术开始逐渐脱离专用硬件设备走到桌面计算机中来。该文在分析了音频和视频数据同异点的基础上阐述了一种基于离散余弦变换的图像压缩方法, 并给出了算法的基本步骤和一些技巧。实际计算结果表明, 通过该算法在极小甚至没有降低图像质量的情况下可获得极高的压缩率。现存的主要问题是计算速度要达到实时运行仍很困难。

关键词　有损压缩, 离散余弦变换, 量化矩阵, 编码分类号　T P391. 41

沙　磊叶　霞

最近10年来, 对图形存储的研究发展迅猛。70年代末期和80年代早期, 大多数图形压缩采用传统的无损技术, 通用的PC 文件格式用这些技术能对图形压缩10%～90%, 著名的标准

压缩格式有PCX 、GIF 和BM P 等。随着图形图像所需存储量的增加, PCX 这样的文件格式已变得不适用了。将文件大小裁剪一半无疑是有意义的, 但开发者和用户占用存储空间的速度是如此之快以致于多媒体的系统需求显得极其昂贵。更有甚者, 如果没有办法大幅度减少存储需求, 在桌面计算机上就无法处理全运动视频。总之, 必须改进压缩技术, 以期进一步提高压缩效果。80年代中后期, 新型图像压缩技术的研究成果开始在桌面计算机图像处理中得到商业应用, 更为重要的是已经开始制定采用这些新压缩技术的国际标准。

与传统的计算机数据文件相比, 图形图像有一个优点, 即在压缩和还原过程中可以作微小的改动而用户不会感到质量的变化。譬如, 对阴影部分的像素作一些小的改动根本不会被察觉, 因为计算机图像通常都是从现实信息源扫描得到的, 因此它们常常包含照片或者其他印刷品中固有的损伤。有损压缩并不改变图像的基本性质, 因此是可行的。在这一点上, 图形图像和声音数据是相似的。但是, 当我们使用语音压缩技术对图形进行压缩时却难以达到预期效果, 主要的原因是音频和视频数据之间的区别。

用传统方式采样的音频数据具有很强的重复性。包括语音在内的声音是由每秒重复几次的正弦波组成。虽然计算机中DAC 的输入数据流由几十种不同频率合成, 但正弦波通常都会组合成重复波形。音频数据的重复性决定了它的可压缩性, 线性预测编码和自适应脉码调制等

X :, , , ,

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

・109・

技术利用了这一特性, 能将音频数据流压缩50%～95%。在研究图形压缩的初期, 人们将类似的方法用于数字化图像。开始, 研究者们对光栅数据流进行压缩, 如电视上显示的图像, 当图形数据被光栅化后, 它们以像素序列的形式显示, 即从上到下逐行显示, 每行从左到右显示, 这样每结束一行就显示一窄条图像, 直到填满全屏; 数字化时, 像素值的范围小到1比特, 大到24比特。桌面计算机的图形现在一般采用每像素8

比特。

1　压缩算法

我们使用的有损压缩算法分为三部分, 如图1, 它们依次是DCT 变换、系数量化和无损压缩, 分述如下:

1. 1　离散余弦变换DCT (discrete cosine transform )

上述压缩过程中最关键的是一个称为DCT 的数学变换。DCT 和著名的快速Fourier 变换(FFT ) 属于同一类数学运算, 这类变换的基本运算是将信号从一种表达形式变成另一种表达形式, 并且这种变换过程是可逆的, 即在两个变换过程中除开舍号进行取样, 然后把它们变换成一个等同的频率域表示形式。在

DCT 变换

↓

系数量化

↓

无损压缩

图1　有损压缩算法流程F ig . 1　F low char t fo r t he

入误差和截断误差, 本质是都是无损失的。首先, 对时空域的信lossy co mpression algo r ithm 这里, 信号是一幅图像, x 和y 轴是屏幕的二维坐标, 此时信号的振幅简单地说就是屏幕上一个特定点的像素为一个用来表示灰度的值, 这样, 一幅图像就可以看作一个三维复值信号。1. 1. 1　DCT 的特性

离散余弦变换公式是

N -1N -1

f (i , j ) =C (i ) C (j ) 66p (x , y ) cos cos

2N 2N x =0y =02N 其中

　1　　　　　(k >0)

公式表明:DCT 对一个N ×N 的方阵P 进行处理, 得到一个N ×N 的频率系数方阵F 。

逆离散余弦变换公式是

p (x , y ) =

C (i ) C (j ) f (i , j ) cos cos 662N 2N 2N i =0j =0

C (k ) =

2　　　　(k =0) 　1　　　　　(k >0)

N -1N -1

(1)

C (k ) =

1/2　　　　(k =0)

(2)

　　初看起来DCT 公式似乎相当复杂, 但实际上它可简单实现。首先, 简单的查表可以代替公式中的许多项, 必须相乘的两个余弦项只需在程序开始时计算一次并存储起来供以后使用。在求和号外的C (k ) 项同样用查表来代替。

把像素变换成频率系数后仍有相同多的点。但是, 在N ×N 矩阵中第0行的一个元素在

信号的一个方向的频率分量为0, 第0列的所有元素则在另一个方向的频率分量为0。随着行列逐渐远离原点, 经过DCT 变换的矩阵的系数就表示越来越高的频率, 最高的频率在矩阵的(N -1, N -1) 处。由于计算机屏幕上的大多数图像都由低频信息构成, 因此这一点是很有意义的。这样, 在0行和0列的分量(DCT 分量) 就比高频分量携带了更多关于图像的有用信息。

・110・

成都理工学院学报　　　　　　　　　　　　　　第24卷

要; 所以说DCT 变换确定了图像的一部分信息, 这些信息可被“扔掉”并且不会对图像的质量带来严重影响。在图像未进行变换前要实现这一点是难以想象的, 当图像在时空域描述时要找出哪些像素对图像的全貌是重要的, 而哪些是不重要的则是相当困难的。

1. 1. 2　DCT 的实现

在检验DCT 算法时出现的第一个问题就是计算DCT 矩阵中每一个元素所需的时间与矩阵的大小有很大的关系。通常使用两层嵌套循环, 因此计算量为O (N *N ) , 当N 增大时处理DCT 输出数组中每个元素所需时间将急剧增加, 这就使得要对整个图像进行离散余弦变换实际上是不可能的, 即使对一个256×256的灰度块进行DCT 变换所需的计算量也太大。为了避开这个困难, DCT 的实现常常将图像分成一些更小更易处理的块, 一般选择8×8的块作为DCT 计算的大小。

随着DCT 块的大小的增加, 可能会给出更好的压缩, 但不会太大。研究表明, 像素间的联系倾向于迅速减小, 所以即使相隔15或20个位置的像素对预测器也没有多大用处。这就意味着一个64×64的DCT 块可能不比将其分为4个16×16的块的压缩效果好, 而且由于计算时间长得多而可能会变得更差。

即使用16×16比特块来作为DCT 计算的基础可能是一个好的量值, 但我们仍选用8×8的块, 这样作的主要原因是期望能用当前的技术来达到实用的目的, 这类压缩被称作“块编码”。

前面DCT 的定义是相对简明的, 对DCT 的每个元素循环的内部成员进行N ×N 次运算, 循环内的命令行进行两次乘法和一次加法。DCT 的一种更加有效的形式可以用矩阵运算来进行计算,

首先建立被称为余弦变换矩阵的N ×N 矩阵C , 它由下式定义。

1/c ij =

N 　　　　　　　　(i , j =0)

2/N cos 　　(i , j >0)

(3)

然后对其进行转置, 记为C t , 称为余弦变换矩阵的转置。它们都可在程序初始化时一次性建立。然后便可以利用DCT 函数的如下变形

F =C *P *C t

(4)

运算“*”表示矩阵乘法, 等式中的多个因子都是一个N ×N 矩阵, P 表示像素矩阵, 前面选择这些矩阵都是8×8的。两个方阵相乘时输出矩阵的每个元素的算术代价是N 次乘法和N 次加法。由于我们进行两次矩阵乘法, 因而建立DCT 矩阵中的每个元素需用2N 次乘法和2N 次加法, 这和一般的两层嵌套循环相比是一个相当大的改进。1. 1. 3　DCT 的输出

一幅灰度图像的输入块是由8×8的像素值矩阵构成(图2) , 它经DCT 产生输出矩阵(如图3) 。输出矩阵表明应建立谱压缩特有的DCT 。为此, 把矩阵左上角的(0, 0) 处值称为“DCT 系数”, 它表示输入矩阵所有模的平均值, 这是因为它表示了在x 和y 轴上的DCT 分量。DCT 系数基本上是模的阶, 它大于DCT 矩阵中的其他值。另外, DCT 矩阵有一个共同的倾向:随着元素离DCT 系数越来越远, 它的模就倾向于越来越小。这意味着通过DCT 来处理数据, 已将图像的表示集结到输出矩阵的左上角的系数, 同时DCT 矩阵的右下部分系数几乎不包含有用信息。

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

18621-10-8-3490

-18-34-24-510

1526-2148

-9-96-15

1842

23-11-18-8-11

8-11

-9113-318-4-74

・111・

-1414-20-3181-1-6

197-1815-7-20

[***********]136148

[***********]156155

[***********]

[***********]162152

[***********]144147

[***********]140147

[***********]147136

-2-181-8

-3-2

123-167136

155

图3　图2所示像素矩阵输入块经DCT 变换后输出的频率系数矩阵

Fig. 3　Fr equency-co efficient mat rix g enerated

by DCT to the input pict ur e -element

blo ck illustrat ed F ig. 2

其中左上角第一个元素称为DCT 系数

图2　一个像素矩阵的输入块

F ig. 2　I nput blo ck o f a picture-element mat rix

1. 2　量化

存储DCT 输出矩阵比存储原来的像素矩阵占用更多的空间。DCT 函数的输入由8比特像素构成, 但输出值的变化范围是-1024～1023, 占用11比特。为使DCT 矩阵占用较少的空间, 需要进行一种强有力的操作, 这种操作称作“量化”。简单地说, 量化就是通过减少精确度来减少存储一个整数所需比特数的过程。一旦一幅DCT 图像压缩后, 我们离原点处的DCT 系数越远时, 这个元素对图像的贡献就越小, 我们就可以大大减小系数的精确度。

采用量化矩阵来实现量化。对DCT 矩阵中每一个元素, 在量化矩阵中的同一位置都有一个相应的量化值。量化值表明在已压缩的图像中该元素的阶跃量是多大, 这个量的范围是0到255。与图像关系最大的元素将用最小的阶跃量来编码, 阶跃量为1, 具有最大的精确度, 离原点(0, 0) 越远的元素其阶跃量越大。量化的实际公式十分简单:

量化值(i , j ) =〔f (i , j ) /量化矩阵(i , j ) 〕

(5)

这里符号〔x 〕表示与x 最接近的整数。可见, 当量化值较大时, 显然可以保证所有较高频率的分量实际上都将被四舍五入为0。仅在高频系数很大时才将其编码为非0值, 但这种情况很少

出现。在解码过程中, 逆量化公式为

f (i , j ) =量化值(i , j ) õ量化矩阵(i , j )

(6)

　　不难看出, 当使用大的定量值时, 就有在逆量化过程中所用的DCT 输出会有大的误差危险, 幸运的是逆量化过程中高频分量的误差不会对图像的质量有严重影响。

显然有许多方案可用来选择量化矩阵中的元素值。一般用两种实验方法检测不同量化方案, 一种是测量输入图像和已解压图像间的数学误差, 第二种方法就是用人眼去判断解压后的效果。需要指出的是后者并非总是与误差水平内的数学差异完全一致。

在运行时选择量化矩阵的好处是在使用DCT 来压缩图像时控制图像的质量很容易。通过给较大的DCT 系数选择特别高的阶跃量可以获得很好的压缩率, 但图像质量很差; 通过慎重地选择小的阶跃量, 压缩率将下降到不是很好的水平, 但图像的质量会很好。这样用户有很大的灵活性, 从而可根据所想象的要求存储能力来选择图像的质量。

我们采用一个很简单的算法来建立量化表。为了确定量化阶跃量的值, 要求用户输入一个在,

・112・

成都理工学院学报　　　　　　　　　　　　　　第24卷

进一步的试验都于事无补。

量化矩阵(i , j ) =1+(1+i +j ) õ质量因子一个质量因子为2的量化矩阵例子如图4所示。

[1**********]7

[1**********]19

[1**********]921

[**************]

[**************]5

[**************]7

[**************]9

[**************]1

(7)

1. 3　编码

压缩算法的最后部分是对量化后的图像进行编码。这一部分由三步组成:第一, 将(0, 0) 点的DCT 系数由绝对值变成相对值。因为图像中相邻块之间有很强的相关性, 因此, 对相邻块的DCT 系数之差进行编码生成的数很小。第二, 对图像系数进行曲徊排序。第三, 将排序结果用两种机制编码, 一种是对0值用游程编码, 另一种称为熵编码。1. 3. 1　曲徊排序

上述算法能够实现高效压缩的原因之一是经过量化后大量的DCT 矩阵元素被截成0。由于这么多0值, 对0的处理与对其他数的处理

图4　质量因子为2的量化矩阵

F ig. 4　Q uantiza tio n mat rix fo r quality facto r =2

大不相同。不采用Huffm an 或算术编码来压缩0值, 而是用游程编码算法(RLE, Run-Leng th Encoding ) , 所用码字很简单, 就是累积图像中的0的个数。因为在很多图像中一半以上的系数都被量化为0, 所以这种编码的压缩效率非常高。

增加游程长度的一种方法是对系数重新进行曲徊排序, 即不像一般程序员熟悉的那样逐行对系数进行压缩, 而是按对角线从最大的可能值扫描到最小的可能值, 实际曲徊路线如图5所示。由于量化步长完全按此路线增加(见公式7) , 所以这种排序对我们来说是最佳的。

1. 3. 2　熵编码

经过将DCT 元素转换成与上一块的差值并将DCT 按曲徊序列记录后, 用熵编码方案输出结果。输出编码中以RLE 作为主要部分, 基本上包括三种记录, 这三种记录不断重复构成一个完整序列。三种记录是:

游程长度:DCT 输出矩阵中当前元素之前连续0的个数;

比特数:表示下一幅值所用的比特数;

幅值:DCT 系数的大小。

图5　曲徊排序路线示意图

F ig . 5　Schematic dia gr am of a zig zag sequence

这里所用的编码序列是Huffman 码和可变长度

整数码的组合。游程长度和比特数组合成Huffman 码, 后者是将幅值编码成可变长整数码所用的位数。可变长整数编码方案利用下列实事:DCT 元素大都是较小的数, 因此较小数用较少:

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

比特数12322

幅　值　　　-1, 1

-3～-2, 2～3-7～-4, 4～7-15～-8, 8～15-31～-16, 16～31

・113・

其中, 每个比特数都对应两个对称的正值和负值范围, 中间跳过的值用少一位比特数编码。当然这种可变比特数编码不如Huffm an 编码效率高, 但非常实用, 这是因为数据特性和所要求的很一致, 即值小的数多, 大的少。1. 4　颜色处理

前面涉及的都是如何压缩只有单个颜色分量的图像, 即灰度图像, 彩色图像一般由三个分量组成, 如红、绿、蓝(RGB ) 或亮度、色度(YUV ) , 在这种情况下将它们当作三幅独立的图像处理。压缩过程本质上是一致的。1. 5　文件还原

还原算法是上述压缩算法的逆运算。

2　算　例

图2是试算的灰度图像的一个输入块, 它是一个8×8的像素值矩阵, 这些像素值基本上随机分布在140到179之间。经过DCT 变换后产生的输出矩阵如图3所示。

在进行量化处理时, 选用了不同的质量因子以便于对比。质量因子为2的量化矩阵见图4, 根据这个配置, 在(0, 6) 处的DCT 元素至少应达到16才能被编码成一个非0值。这就确定了一个元素将给图像提供有用信息时其量的一个临界值。低于这个临界值的任何元素都将被扔掉, 这是算法中出现损失的唯一地方。因为第一步DCT 除了微小的数学误差外, 并没有出现损失, 而量化后的编码也是无损的。

图6表示对DCT 矩阵量化的效果, 可以看出, 量化/逆量化过程会产生明显的效应, 矩阵的高频部分大多被截断为0, 从而使它们在还原阶段不起作用; 矩阵中其他DCT 元素可能也会被修改, 但幅度很小。有趣的是, 尽管上述改变似乎是对整幅图, 但当量化因子为2时却几乎

624-100000

-4-5-300000

23010-100

-100-10000(a )

20-100000

00000000

00-100000

10000000

186-2020

-35

14270130-1700

-900-150000(b )

220-1500000

00000000

00-1900000

170000000

-7-2700000

00000

图6　量化效果

F ig. 6　Q uantization effect

(4b

・114・

成都理工学院学报　　　　　　　　　　　　　　第24卷

察觉不到变化, 而显著的效果是剔除了这么多系数后至少能将图像压缩60%。

图7是试算的灰度图像经过压缩/还原后的一些结果, 它们对应不同的质量因子。前几个看起来相当好, 实际上很难看出区别; 质量因子为5时仔细观察可以发现有些区域经压缩后质量有所降低; 而质量因子为10、15和20的图像则有明显失真,

尽管它们有较高的压缩率。

图7　经过压缩/还原后的试算图像

F ig. 7　A pr act ical co mputing ex ample fo r co mpr ession/r estor ation

上述实验结果很说明问题, 在大多数情况下这种算法可将图像压缩约85%而无大的失真。通过改进甚至可望达到更好的压缩效果, 比如采用Huffman 编码方法等。

3　结　语

实际计算结果表明, 由DCT 变换、系数量化和无损压缩这三部分能够组合成一个性能卓越而且使用灵活的图像压缩器, 它能根据用户要求将连续调图像压缩到原图的10%以下而几乎不产生失真。

DCT 是整个算法的核心, 它的具体实现本身就是一个正在迅速发展着的课题。为了达到足够的精度, 这里所用的DCT 形式都采用可靠的浮点运算, 这是一种基本方法。需要指出的一点是, 给出一种使用将其转换成整数来进行数字运算的DCT 形式是完全可能的, 这种形式在大多数平台上都快得多。另外, 由于DCT 与离散Fo urier 变换有关, 因此可将用来加速Fo urier 变换的许多技术用于DCT 。实际上, 人们正无时无刻不在努力将数字信号处理技术用于DCT , 以提高其速度。

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

・115・

参

A cademic P ress, 1983

考文献

1　Scho w eng erdt R A . T echniques for Imag e Pr ocessing and Classificatio n in Remo te Sensing . N ew Y or k :2　P avlidis T. A lgo rithms for G r aphics and Ima ge Pr ocessing. N ew Y or k:Computer Seience P ress Inc,

1982

3　陈达. 多媒体与CD -RO M . 北京:清华大学出版社, 19954　何圣静, 傅德荣. 多媒体技术. 北京:北京理工大学出版社, 19945　董士海等. 图像格式编程指南. 北京:清华大学出版社, 1994

6　Berg land G D . T he fast Fo ur ier tr ansfo rm r ecur siv e equatio ns fo r arbitr ar y length r ecor ds . M ath Comp ,

1967, 21(98) :236～2387　Ber gland G D. T he fast F ourier t ransfor m algo rithm using base 8iterat ions. M ath Comp, 1968, 22

(102) :275～279

8　刘德贵等. 新编工程实用算法与F O RT R AN 77程序. 北京:国防工业出版社, 1990. 119　《数学手册》编写组. 数学手册. 北京:高等教育出版社, 1979

10　Ro ger s D F, A dams J A. M athemat ical Elem ents for Co mputer Gr aphics. N ew Y or k:M cG raw -Hill,

1976

11　Denes P B . A scan -type g r aphics sy st em fo r interactive co mput ing . P ro c IEEE Co nf on Co mput er

Gr aphics, Pat tern Reco gnition and D ata Str uct ur e, 1975, 21

12　Jar vis J F, Judice C N , N inke W H. A sur ver y o f techniques fo r the ima ge displa y o f co ntinuo us tone

picture o n bilev el display s. Computer G r aphics and I mage P ro cessing , 1976, 5(1) :13～14

13　Jar vis J F , Ro ber ts C S . A new technique for display ing continuous t one images on bilev el display . IEEE

T r ans, 1976, CO M -24(8) :891～898

A METHOD FOR PICTURE COMPRESSION USING

DISCRETE COSINE TRANSFORM

(Chengdu U niver sity of T echnology , China )

Sha Lei Ye Xia

(X i ′an I nstitute of Coal M ining Science )

Abstract 　Softwares adopted co mplicated pictures are comm on in every area of computer application. As the demanding of sto rage capacity by photogr aphs increases sharply and

num erical sig nal pro cessing units beco me mor e and mor e cheap , effective techniques o f lossy co mpr ession are g enerally seper ated from some special hardw ar es and applied to table -co mpter sy stems. In this paper, the autho rs first analy ze the similarities and differ ences o f audio-and v ideo-data, then expound a picture co mpr ession technique based upon discrete co-sine transfo rm (DCT ) , and finally g ive detailed steps and some basic skills of its alg orithm . Practical com puting r esults by this technique show that ver y hig h compression ratios are available under m inimum -lo w ering or even no -low er ing of raw picture quality. The main ex-tant problem is computing speed . It is very difficult to reach r eal -time operatio n at present . Key words 　lossy co mpression ; discrete cosine transform ; quantization m atr ix ; coding

第24卷　第3期　1997年7月　　　成都理工学院学报　　　JO U R NA L O F CHENG DU U NI VER SI T Y OF T ECHN OL O GY V ol. 24N o. 3Jul. 1997　

利用离散余弦变换进行图像压缩的方法

关键词　有损压缩, 离散余弦变换, 量化矩阵, 编码分类号　T P391. 41

沙　磊叶　霞

X :, , , ,

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

・109・

比特。

1　压缩算法

我们使用的有损压缩算法分为三部分, 如图1, 它们依次是DCT 变换、系数量化和无损压缩, 分述如下:

1. 1　离散余弦变换DCT (discrete cosine transform )

DCT 变换

↓

系数量化

↓

无损压缩

图1　有损压缩算法流程F ig . 1　F low char t fo r t he

离散余弦变换公式是

N -1N -1

f (i , j ) =C (i ) C (j ) 66p (x , y ) cos cos

2N 2N x =0y =02N 其中

　1　　　　　(k >0)

公式表明:DCT 对一个N ×N 的方阵P 进行处理, 得到一个N ×N 的频率系数方阵F 。

逆离散余弦变换公式是

p (x , y ) =

C (i ) C (j ) f (i , j ) cos cos 662N 2N 2N i =0j =0

C (k ) =

2　　　　(k =0) 　1　　　　　(k >0)

N -1N -1

(1)

C (k ) =

1/2　　　　(k =0)

(2)

把像素变换成频率系数后仍有相同多的点。但是, 在N ×N 矩阵中第0行的一个元素在

・110・

成都理工学院学报　　　　　　　　　　　　　　第24卷

1. 1. 2　DCT 的实现

首先建立被称为余弦变换矩阵的N ×N 矩阵C , 它由下式定义。

1/c ij =

N 　　　　　　　　(i , j =0)

2/N cos 　　(i , j >0)

(3)

然后对其进行转置, 记为C t , 称为余弦变换矩阵的转置。它们都可在程序初始化时一次性建立。然后便可以利用DCT 函数的如下变形

F =C *P *C t

(4)

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

18621-10-8-3490

-18-34-24-510

1526-2148

-9-96-15

1842

23-11-18-8-11

8-11

-9113-318-4-74

・111・

-1414-20-3181-1-6

197-1815-7-20

[***********]136148

[***********]156155

[***********]

[***********]162152

[***********]144147

[***********]140147

[***********]147136

-2-181-8

-3-2

123-167136

155

图3　图2所示像素矩阵输入块经DCT 变换后输出的频率系数矩阵

Fig. 3　Fr equency-co efficient mat rix g enerated

by DCT to the input pict ur e -element

blo ck illustrat ed F ig. 2

其中左上角第一个元素称为DCT 系数

图2　一个像素矩阵的输入块

F ig. 2　I nput blo ck o f a picture-element mat rix

1. 2　量化

量化值(i , j ) =〔f (i , j ) /量化矩阵(i , j ) 〕

(5)

出现。在解码过程中, 逆量化公式为

f (i , j ) =量化值(i , j ) õ量化矩阵(i , j )

(6)

我们采用一个很简单的算法来建立量化表。为了确定量化阶跃量的值, 要求用户输入一个在,

・112・

成都理工学院学报　　　　　　　　　　　　　　第24卷

进一步的试验都于事无补。

量化矩阵(i , j ) =1+(1+i +j ) õ质量因子一个质量因子为2的量化矩阵例子如图4所示。

[1**********]7

[1**********]19

[1**********]921

[**************]

[**************]5

[**************]7

[**************]9

[**************]1

(7)

1. 3　编码

上述算法能够实现高效压缩的原因之一是经过量化后大量的DCT 矩阵元素被截成0。由于这么多0值, 对0的处理与对其他数的处理

图4　质量因子为2的量化矩阵

F ig. 4　Q uantiza tio n mat rix fo r quality facto r =2

1. 3. 2　熵编码

游程长度:DCT 输出矩阵中当前元素之前连续0的个数;

比特数:表示下一幅值所用的比特数;

幅值:DCT 系数的大小。

图5　曲徊排序路线示意图

F ig . 5　Schematic dia gr am of a zig zag sequence

这里所用的编码序列是Huffman 码和可变长度

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

比特数12322

幅　值　　　-1, 1

-3～-2, 2～3-7～-4, 4～7-15～-8, 8～15-31～-16, 16～31

・113・

还原算法是上述压缩算法的逆运算。

2　算　例

图2是试算的灰度图像的一个输入块, 它是一个8×8的像素值矩阵, 这些像素值基本上随机分布在140到179之间。经过DCT 变换后产生的输出矩阵如图3所示。

624-100000

-4-5-300000

23010-100

-100-10000(a )

20-100000

00000000

00-100000

10000000

186-2020

-35

14270130-1700

-900-150000(b )

220-1500000

00000000

00-1900000

170000000

-7-2700000

00000

图6　量化效果

F ig. 6　Q uantization effect

(4b

・114・

成都理工学院学报　　　　　　　　　　　　　　第24卷

察觉不到变化, 而显著的效果是剔除了这么多系数后至少能将图像压缩60%。

尽管它们有较高的压缩率。

图7　经过压缩/还原后的试算图像

F ig. 7　A pr act ical co mputing ex ample fo r co mpr ession/r estor ation

3　结　语

第3期　　　　　　　　沙　磊等:　利用离散余弦变换进行图像压缩的方法

・115・

参

A cademic P ress, 1983

考文献

1982

6　Berg land G D . T he fast Fo ur ier tr ansfo rm r ecur siv e equatio ns fo r arbitr ar y length r ecor ds . M ath Comp ,

1967, 21(98) :236～2387　Ber gland G D. T he fast F ourier t ransfor m algo rithm using base 8iterat ions. M ath Comp, 1968, 22

(102) :275～279

8　刘德贵等. 新编工程实用算法与F O RT R AN 77程序. 北京:国防工业出版社, 1990. 119　《数学手册》编写组. 数学手册. 北京:高等教育出版社, 1979

10　Ro ger s D F, A dams J A. M athemat ical Elem ents for Co mputer Gr aphics. N ew Y or k:M cG raw -Hill,

1976

11　Denes P B . A scan -type g r aphics sy st em fo r interactive co mput ing . P ro c IEEE Co nf on Co mput er

Gr aphics, Pat tern Reco gnition and D ata Str uct ur e, 1975, 21

12　Jar vis J F, Judice C N , N inke W H. A sur ver y o f techniques fo r the ima ge displa y o f co ntinuo us tone

picture o n bilev el display s. Computer G r aphics and I mage P ro cessing , 1976, 5(1) :13～14

13　Jar vis J F , Ro ber ts C S . A new technique for display ing continuous t one images on bilev el display . IEEE

T r ans, 1976, CO M -24(8) :891～898

A METHOD FOR PICTURE COMPRESSION USING

DISCRETE COSINE TRANSFORM

(Chengdu U niver sity of T echnology , China )

Sha Lei Ye Xia

(X i ′an I nstitute of Coal M ining Science )

Abstract 　Softwares adopted co mplicated pictures are comm on in every area of computer application. As the demanding of sto rage capacity by photogr aphs increases sharply and

利用离散余弦变换进行图像压缩的方法_沙磊

相关文章