第九章 图像编码

北京大学遥感所1第九章

图像编码第九章 图像编码北京大学遥感所2■

概述■

信息量和信息熵■

图像信息熵值和信息剩余度■

编码技术■

预测编码JPEG与MPEG简介§9.1概述北京大学遥感所3■

什么是图像编码？Q 数字图像作为数字存储时数据量特别大，并且传输时占用频带宽，因而需要事先对图像进行压缩编码。图像的压缩编码，依据图像信号固有的统计特征和人类的视觉特征进行。Q 图像信号固有的统计特征表明：

图像相邻象素之间，相邻行之间，或者相邻帧之间，存在较强的相关性。利用某种编码方法在一定程度上消除这些相关性，就可以实现图像信息的数据压缩。§9.1概述北京大学遥感所4■

无损压缩编码：（也叫信息保持压缩编码）Q

无损压缩编码方法是基于图像信息的统计特性，其表现特点是图像信息在一行的相邻象素间、或相邻行列之间、相邻帧之间具有较强的相关性，去掉这些相关性，即可去掉图像信息中许多冗余信息，而保持那些有用信息。Q 信息论理论证明，只要编码后的图像的每个象素的平均码元长度大于图像的熵值，则总能保持图像中的有用信息，在解码重建图像时不致于造成失真。§9.1概述北京大学遥感所5■

有损压缩编码：Q

经采用某种方法对图像数据压缩虽然会造成一定程度的失真，但在重建时，这种失真人眼难以察觉，能被人眼视觉所忽略，或从主观感觉上觉察不出它与原图像之间的差别。Q

这种压缩编码属于信息非保持编码，与信息保持编码相比具有更高的压缩效率§9.1概述■

研究图像编码技术的目的：在保证图像观察质量的前提下，尽可能最大限度地降低码率（单位时间内所传输图像数据的比特-bit数），以利于节省图像数据的存储空间，减少传输时间、传输通道，降低成本。流程图如下：原始图像数据编码器被压缩的图像数据传输传输解码器重建图像数据被压缩的图像数据北京大学遥感所6§9.2信息量和信息熵北京大学遥感所7■

“信息”是指对消息接收者来说预先不知道的报导。从概率统计的角度来看，由信息源发出一系列消息{ak

}，出现概率率

p(ak

),

k

0,1,

2,...,

K

1■

其中，K为消息源的总数量。■

假定接收者接收到符号为ak的概率为p(ak

)，则信息量定义为

I

log[

p(ak

)]§9.2信息量和信息熵北京大学遥感所8■

其中信息源发出的各个是独立无关的，称为无记忆信息源。当无记忆信息源发出的各个消息是等概率的，信息量为最大。消息源的熵定义为K

1H

E{I

(ak

)}

p(ak

)

log[

p(ak

)]k

0■

上式称为信息熵或信源熵，熵值的单位是：“比特/符号”。§9.2信息量和信息熵■

如果一幅亮度分辨率为8bit的黑白图像，从其亮度直方图的分布看是等概率的，它的熵值为：255H

pi

log2

pi1北京大学遥感所91256256*

log ⎛⎞i

0

256

*2

⎜⎟⎝⎠

8比特

/

象素■

对于一个8bit的图像来说，如果其直方图分布是等概率的，它的熵值就是8比特/象素。§9.3图像信息熵值和信息剩余度■

编码效率：■

一幅图像在一般情况下各亮度值总是非等概率的，因此其熵值总是小于等概率的熵值。去掉这些冗余的信息，便压缩编码后的图像熵值不低于图像信息源熵值，就不会丢失图像的有用信息。■

相对熵和剩余度：一个信息源实际输出的熵与该信息源的最大可能熵之比称为相对熵

h

,信源的剩余度定义为

r

1

ha北京大学遥感所10N

log

nH

(

X

)

§9.4编码技术北京大学遥感所11哈夫曼编码(Huffmancoding)■

链码■

拓扑数据结构■

关系结构金字塔编码（pyramids）四叉树（Quad-trees）§9.4.1哈夫曼编码北京大学遥感所12哈夫曼编码(Huffmancoding)Q

最早于50年代提出，它是一种无损的统计编码方法。哈夫曼方法用变长的码来使冗余量达到最小。其基本思想是：对于出现概率大的信息符号编以短字长的码字，对于出现概率小的信息符号编以长字长的码字。Q

它属于信息保持编码，又叫做熵保存编码，或者叫熵编码。§9.4.1哈夫曼编码北京大学遥感所13具体算法：Q

将各消息按照概率由大到小排成一个序列；Q

将其中两个最小概率所对应的符号为子结点，（概率较小者为左结点，概率较大者为右结点）由此构造其父结点，其概率等于二者概率之和；Q

将新生成的结点与未经处理的消息按照概率大小重新排列，形成一个新的概率序列；重复上述步骤，直到所有结点全部插入到结点表中；Q

设所有的结点左结点为1，右结点为0，从根结点开始经中间结点到达叶结点，其路径代码即是该结点的Huffman编码。§9.4.1哈夫曼编码互换，此时平均码长为

，则

为，可见，N

'

N

[n

p(l

)

n

p(l

)]

[n

p(l

)

n

p(l

)]b a a b a a b b

N

nb

[

p(la

)

p(lb

)]

na

[

p(la

)

p(lb

)]

N

(nb

na

)[

p(la

)

p(lb

)]Q

证明：设最佳排列方式的码字平均长度为

N，则mN

ni

P(li

)i

1Q

其中p(li

)

为信源符号li

出现的概率，ni为编码后符号的码字长度，a b a b当 p(l

)

时p(l，)

有

n

n

,

a,

b

1,

2,

mQ

将abl 与

l' 'N NQ

因为

nb

na，p(la

)

p(lb

)

，所以Q

N

是最短的。N

'

N北京大学遥感所14§9.4.1哈夫曼编码举例：某信源发出的8个消息及其相应出现的概率为：P(A)=0.1;P(B)=0.18;P

(C)

=0.4;P(D)=0.05;P(E)=0.06;P(F)=0.1;P(G)=0.07;P(H)=0.04C：1；B：001；A：011；F：0000G：0100；E：0101；D：00010；H：000111北京大学遥感所15m平均码长为：L

ni

p(i)

2.61比特/消息i

18信源实际输出的熵：H

p(i)

log2

p(i)

2.55比特/消息编码效率为：

2.55

/

2.61

97.8%§9.4.2行程编码北京大学遥感所16■

行程编码：指在一行扫描的象素中，比较相邻象素的幅度。当幅度有显著变化时，就说明有一个行程存在。■

通常用于图像矩阵中符号串的表示。例如，传真机就使用这种方式。在二值图像中，行程编码仅记录图像中属于物体的区域，该区域表示成以表为元素的表。图像的每行表示成一个子表，它的第一个元素为行号，然后是两个纵坐标构成的项，第一个为行程的开始的纵坐标（列号），第二个为行程的结束的纵坐标。一行中可以有若干个这样的序列项。§9.4.2行程编码0 123 4 5 6北京大学遥感所170123456行程编码;编码为((11144)(214)(52355)).§9.4.3链码北京大学遥感所18■

链码：描述物体的边界，链码中的符号一般对应于图像基元的邻接关系。如下图所示。链码可以用静态数据结构来表示，如1维数组，取其大小为链码的最大可能长度；也可以用动态数据结构来表示，且这样在节省存储空间方面更合适。§9.4.3链码76504123链码示例：000077665555556600000006444444442221111112234445652211北京大学遥感所19§9.4.4拓扑数据结构■

拓扑数据结构：图像描述成一组元素及其相互关系的图结构。例如，赋值的属性图，区域邻接图。区域邻接图例子如下：132450北京大学遥感所2013

245区域邻接图例子§9.4.5关系结构北京大学遥感所21■

关系结构：信息集中在语义上重要的图像组成部分（它们是图像分割的结果）即物体之间的关系上，适合用于高层次的图像理解工作。例如，使用关系结构描述自然场景的示意图（物体及其关系属性表）如下：§9.4.5关系结构1北京大学遥感所22234567示例关系表No.ObjectnameColorMin.rowMin.col.Inside1SunWhite54022SkyBlue00-3CloudGrey2018024TreetrunkBrown957565TreecrownGreen5363-6HillLight

green970-7PondBlue1001606§9.4.6金字塔编码Level

0北京大学遥感所23Level

2Level

1金字塔编码§9.4.7四叉树（Quad-trees）0北京大学遥感所2423101112120121

122

123四叉树编码010111201211312212323§9.5预测编码北京大学遥感所25◈预测编码（DifferentialPulseCodeModula-tion）是统计冗余数据压缩理论的三个重要分支之一。◈预测编码的理论基础是现代统计学和控制论，它主要减少了数据在时间和空间上的相关性。◈对于静止图像来说，预测编码将被图像变换编码所取代。◈而预测编码对于视频图像来说，它充分利用了连续帧之间的统计冗余性，是当今主流技术并且还会流行于未来。§9.5预测编码北京大学遥感所26№.1预测编码的基本原理☪预测编码是根据图像数学模型利用以往的样本值对于新样本值进行预测，然后将样本的实际值与其预测值相减得到一个误差值，对这一误差值进行编码,是有损压缩编码。☪如果模型足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号，从而可以用较少的数据对其差值量化得到较好的数据压缩效果。§9.5预测编码北京大学遥感所27№.1预测编码的基本原理☪如果能精确地预测数据源输出，那就不存在关于数据源的不确定性，也就不存在要传输的信息。☪通常预测器的设计不是利用数据源的实际数学模型，而是根据经验事先准备一个经验数学模型，因为数据源的实际数学模型是非常复杂，而且是时变的。☪实验结果表明：以最小均方预测误差设计的预测器不但能获得最小均方预测误差，容易实现，同时在视觉效果上也是比较好的。§9.5预测编码＋＋＋＋－№.2预测编码的流程图＋编码传输滤波预测输出量化预测抽样输入北京大学遥感所28预测编码原理图§9.5预测编码北京大学遥感所29№.3预测编码的统计特性☪一般情况下，相邻两象素灰度值突变的概率较小。如果取一幅图像第i行的第j列象素的亮度离散值为

f(i,j)

，则△1=

f(i,j)-f(i,j-1)△2=

f(i,j)-f(i-1,j)其中△称为差值信号。☪幅度差值愈大的差值信号出现的概率愈小，而零值或接近零值的差值信号出现的概率最大。§9.5预测编码№.3预测编码的统计特性☪图像差值信号的概率分布如图所示：概率差值信号-2北京大学遥感所30-1012§9.5预测编码北京大学遥感所31№.4预测编码的编码方法☪前一个象素亮度实际值为FN-1，则下一个象素亮度预测值为☪如根据前N个亮度真实值预测得到，则函数表达式为其中ai（i＝1，2，……N－1）称为预测系数。☪如函数关系为线性相关，则可表示为

FNi

1N

1

ai

Fi

FˆN

f (

F

N

1

)FˆN N

1

N

2

f

(F

,

F

,

)§9.5预测编码北京大学遥感所32№.4预测编码的编码方法☪一般情况下，最佳预测应该是均方误差最小，☪不同图像的待测系数不同，但是要遵循系数和☪在实际应用中，都用上述方法计算待测系数比较麻烦，这时可以参照前人得到的数据。在JPEG标准中推荐了一些值可供参考。N N即

E{(F

Fˆ

)2}

min

1为1，即

ai§9.5自适应预测编码北京大学遥感所33№.1预测编码的缺陷☪对黑白灰度有突变的点，会有较大的预测误差，致使重建图像的边缘模糊，分辨率降低。☪对图像亮度值变化缓慢区域，其差值信号应为零，但因其预测值偏大而使重构图像有颗粒噪声。☪为了改善图像质量，克服上述缺点，提出了一种基于预测编码的改进方法——自适应预测编码。§9.5自适应预测编码北京大学遥感所34№.2自适应预测编码的公式☪公式如下：其中，k为自适应系数。一般情况下，令k＝1 ，对灰度变化大的区域，令k＝1.125

，对灰度变化缓慢区域，令

k＝0.875

，以减少颗粒噪声的影响。由于k是可变的，因此此方法也称为非线性预测编码。N

1Fi

1

k

ai

Fii

1

§9.5自适应预测编码№.3几种编码的效果图比较北京大学遥感所35采用固定系数预测编码后的结果自适应预测编码后的重构图像直接采用均匀标量量化后的a1=0.5,a1=0.340,结果a2=0.5,a2=0.664,a3=-0.5a3=-0.005§9.6图像变换编码北京大学遥感所36№.1变换编码的基本原理☪图像变换编码的基本概念：指将给定的图像数据变换（如正交变换）到另一个数据域（如频域）上，然后进行量化、编码和传输，使得大量的信息能用较少的数据来表示

。☪编码器由预处理、正变换、量化与编码几部分组成，译码器由译码、反变换及后处理组成。☪以傅氏变换为例，变换后的大的频谱系数90％集中在低频，可以压缩低频，忽略高频。§9.6图像变换编码№.2变换编码的流程图☪如下所示：输入函数与输出函数不同是由于量化误差导致。预处理后处理反变换正变换译码量化编码传输或存储f

(x,

y)北京大学遥感所37F

(u,

v)

f

(

x,

y

)§9.6图像变换编码北京大学遥感所38№.3变换编码的常用变换☪傅氏变换☪Walsh－Hadamard变换☪正弦变换☪余弦变换——应用最广☪斜变换☪哈尔变换☪K－L变换§9.6图像变换编码北京大学遥感所39№.4变换编码的方法☪变换区域编码：根据变换系数集中在变换域左上角低频区域的特点，对该区域的变换系数进行量化、编码、传输，

对右下角高频区域既不变换也不传输。☪变换阈值编码：实现设定一个阈值，只对变换系数的幅值大于此阈值的编码，不仅低频保留，某些高频成分也保留。如能根据子象块自动调整阈值，就属于自适应。§9.6图像变换编码№.5离散余弦（DCT）变换编码的基本原理源图像数据FDCT量化器 熵编码器被压缩数据表说明表说明重建的图像数据IDCT解量化器熵解码器表说明表说明北京大学遥感所40§9.6图像变换编码№.5离散余弦（DCT）变换编码的基本原理☪二维余弦正变换（8*8子图像）☪二维余弦反变换（8*8子图像）7 71cos]416

16x

0

y

0(2x

1)u

(2

y

1)v

F

(u,

v)

C(u)C(v)[

f

(x,

y)

cos7 7北京大学遥感所411cos]41616x

0

y

0(2x

1)u

(2

y

1)v

f

(u,

v)

[

C(u)C(v)F

(x,

y)

cos§9.6图像变换编码北京大学遥感所42№.6LZW编码的基本原理☪LZW编码：当表中没有的字符串头一次出现的时候，将这个字符串和分配给它的代码同时保存，以后该串再次出现时就只存储它的代码。字符串表和采用LZW的图像文件格式有GIF。☪因此字符串表在压缩中动态生成，但不必存在压缩文件里，它可由解压缩算法来重构它。§9.6图像变换编码北京大学遥感所43№.7彩色图像的变换编码☪将输入的R、G、B三种彩色信号转换成亮度和色度信号，然后进行变换编码。☪转换公式是：Y=0.3R+0.59G+0.11BU=B-YV=R-Y§9.7国际标准北京大学遥感所44◈JPEG标准：研究静止图像算法的国际标准。1987年用Y：U：V＝4：2：2，每像素16bit，宽高比为4：3的电视图像进行了测试，选出三个方案，进行评选，其中8×8的方案得分最高。◈MPEG标准：用于数字存储媒介中活动图像及伴音的编码标准◈JBIG标准：二值传真图像标准◈H.261标准:为适应可视电视和会议电视的需要，CCITT第15研究组承担了视频的编解码标准的研究工作。§9.7国际标准JPEG北京大学遥感所45№.1JPEG算法简介☪由国际标准化组织和CCITT联合发起的联合图像专家组（JPEG），建立了静态图像压缩的公开算法。在视觉效果不受到损失的前提下，算法可以达到15到20的压缩比。如果在图像质量上稍微牺牲一点的话，可以达到40：1或更高的压缩比。§9.7国际标准JPEG北京大学遥感所46№.1JPEG算法简介☪如果处理的是彩色图像，JPEG算法首先将RGB分量转化成亮度分量和色差分量，同时丢失一半的色彩信息（空间分辨率减半）。然后，用DCT来进行块变换编码，舍弃高频的系数，并对余下的系数进行量化以进一步减小数据量。最后，使用RLE和Huffman编码来完成压缩任务。§9.7国际标准JPEG北京大学遥感所47№.2JPEG推荐亮度量化表1611101624405161121214192658605514131624405769561417222951878062182237565610910377243555648110411392496478871031211201017292959811210010399§9.7国际标准JPEG北京大学遥感所48№.2JPEG推荐色度量化表171824479999999918212666999999992426569999999999476699999999999999999999999999999999