图像数据压缩

		行 变 换
列 变 换

图3.1 小波图像变换过程[3]

实验结论:用report(‘jimm')对jimm_org.png真彩图像文件计算阈值分别为0，5，10和20的情况下进行3级非标准haar小波变换和重构后，系数为“0”的数目和以PNG格式存储的重构图像文件大小，实验结果得到图像测试表(如表3.2)所示：

表3.2 图像测试表

(图3.2)表示了在不同阈值下的重构图像：

δ=0

δ≤5

δ≤10

δ≤20

图3.2 不同阈值下的重构图像[5]

从图像测试表和观察不同阈值下的重构图像可得出以下结论：

可利用小波变换与重构对图像文件进行压缩。

通常在给定小波基函数条件下，阀值越大，系数为0的数目就越多，重构图像文件压缩率也越高，重构的图像失真程度随之增加。

阀值>0时，利用小波变换与重构进行图像压缩是一种有损压缩方法，可以根据实际需要在图像失真度允许的范围内选择适当的阀值来确定压缩率。

3.3LZW压缩算法

LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号，如(表3.3)所示。这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串[8]。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。Welch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。

表3.3 词典

LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Codestream)，码字代表单个字符或多个字符组成的字符串[9]。

LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串——缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。

LZW编码算法的具体执行步骤如下：

步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P是的；

步骤2： 当前字符(C) ：=字符流中的下一个字符；

步骤3： 判断缀-符串P+C是否在词典中

1 如果“是”：P ：= P+C // (用C扩展P) ；

2 如果“否”

把代表当前前缀P的码字输出到码字流;

把缀-符串P+C添加到词典;

令P ：= C //(现在的P仅包含一个字符C);

步骤4： 判断码字流中是否还有码字要译

1 如果“是”，就返回到步骤2；

2 如果“否”

把代表当前前缀P的码字输出到码字流;

结束。

LZW编码算法可用伪码表示。开始时假设编码词典包含若干个已经定义的单个码字。例如，256个字符的码字，用伪码可以表示成：

Dictionary[j]← all nsingle-character， j＝1, 2，…，n

j ← n+1

Prefix ← read first Character inCharstream

while((C← nextCharacter)!=NULL)

Begin

IfPrefix.C is in Dictionary

Prefix ← Prefix.C

else

Codestream← cW forPrefix

Dictionary[j]← Prefix.C

j ← n+1

Prefix ← C

end

Codestream← cW forPrefix

译码算法：

LZW译码算法中还用到另外两个术语：①当前码字(Current code word)：指当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串；②先前码字(Previous code word)：指先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串。

LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(roots)。LZW算法在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典中。

LZW译码算法的具体执行步骤如下：

步骤1： 在开始译码时词典包含所有可能的前缀根(Root)。

步骤2： cW ：=码字流中的第一个码字。

步骤3： 输出当前缀-符串string.cW到码字流。

步骤4： 先前码字pW ：= 当前码字cW。

步骤5： 当前码字cW ：= 码字流中的下一个码字。

步骤6： 判断先前缀-符串string.pW是否在词典中

1 如果“是”，则：

把先前缀-符串string.pW输出到字符流。

当前前缀P ：=先前缀-符串string.pW。

当前字符C ：=当前前缀-符串string.cW的第一个字符。

把缀-符串P+C添加到词典。

2 如果“否”，则：

当前前缀P ：=先前缀-符串string.pW。

当前字符C ：=当前缀-符串string.cW的第一个字符。

输出缀-符串P+C到字符流，然后把它添加到词典中。

步骤7： 判断码字流中是否还有码字要译

1 如果“是”，就返回到步骤4。

2 如果“否”, 结束。

LZW译码算法可用伪码表示如下:

Dictionary[j]← all nsingle-character， j＝1, 2，…，n

j ← n+1

cW ← first code fromCodestream

Charstream←Dictionary[cW]

pW ← cW

While((cW← next Codeword)!=NULL)

Begin

If cW isin Dictionary

Charstream←Dictionary[cW]

 4/5   首页 上一页 2 3 4 5 下一页 尾页