在上述思想基础上，LZW编码方法是采用“蚕食”分析算法进行的。首先，对串表进行初始化，初始化的串表中应包含所有可能的单个字符。“蚕食”分析算法就是每一次分析都要从输入字符或图像数据串中分解出前面识别出的最长的数据串，再把这个已识别出的最长的串取出来当做前缀ω，然后加上下一个输入的字符作为k，就形成了一个新的串ωk。把这个串ωk加入串表中，并为其分配代码，通常此代码又称标志值或指针，编码输出就是此代码。
编码过程就是利用这种“蚕食”分析算法一直进行下去，直到不再输入字符串。可以简单地将此分析算法的规则描述如下。
初始化串表，使之包括所有单个字符
读取第一个输入字符--作为前缀ω
step：读取下一个输入字符k
if没有这样的ωk：code（ω）→output；EXIT
ifωk存在于串表中：ωk→ω；repeatstep
elseωk不在串表中：code（ω）→output
ωk→串表
k→ω；repeatstep
可以看到，每分析一次，一个输入串ω被分析出来，并且下一字符k被加进来，扩展为串ωk，同时测试它是否已存在于串表中。如果已存在于串表中，则扩展串ωk变为新一个ω，并重复上述步骤。若测试发现其不在串表中，则将其加入到串表中，并将串ω的指针作为压缩输出，而k则作为下一个ω，再重复前述过程。为了说明编码过程，现举例说明。
【例3.6】假定输入符号如表35所示。同时也假定输入符号中所包含的符号只有abc三个，则初始化串表如表36前3行所示。
对照表35和表36，LZW编码过程如下：
①读入第1个字符a，这是初始串表里面已有的。将a作为前缀ω，保存代码1并输出。
②读第2个字符b，把它当成k，与前面的ω构成ωk，也就是ab。判断ab是否在串表中，在这里ab不在串表中，于是将前缀a的码字（指针）1作为代码输出，并且将ωk即ab放在串表的扩展部分中，其指针为4。而后将k即b作为前缀继续向下做。
③读入第3个字符，将其当成k，前一步的前缀ω已经形成为b。两者组成的ωk为ba。判断ba是否在串表中，发现它不在串表中，于是将前缀b的码字（指针）2作为代码输出，并且将ba放在串表中，其指针为5。而后再将k，此处为a作为前缀继续向下进行。
④读入第4个字符b，将其当成k，而将前面形成的ω前缀（a）加上，构成ωk，即ab。判断ab是否在串表中，发现串表中有ab，于是不输出代码并将ωk当成ω，即此时ω为ab。
⑤读下一个字符c，将c当成k，与前面形成的ω共同构成ωk，此时的ωk就是abc。判断abc是否在串表中，发现它不在串表中，于是将前缀ω，此处为ab的码字（指针）4输出并将ωk即abc存放于串表中，其指针为6。并且将k即c作为ω，继续向下进行。
⑥此过程依据上述原理继续进行，直到最后结束。
在LZW编码中，编码输出的是串表中字串的指针（可以看做是地址）。当输入数据串有较大的冗余度时，所构成的串表是有限的，从而可获得较大的压缩比。
2．LZW解压缩算法
在LZW解压缩过程中，初始化串表是先验可知的。就像前面所提到的例子，由a、b、c构成的初始化串表是已知的。LZW解压缩过程如图317所示，其过程简述如下。
图317LZW解压缩过程
①读入第1个代码，由初始串表查出其对应的字符为a。将a输出，并把1代码作为旧代码（OldCode）予以保存。
②读入第2个代码，判断2是否在串表中，发现2在串表中，则查出代码2的字符为b，并将其输出。查旧代码1对应的字符为a，将它当成ω，再由代码2查表得字符串为b，该字符串左侧第一个字符为k，在此处就是b，于是，得到的ωk为ab。将ab写到串表指针为4的位置上。把刚读入的代码2作为旧代码保存起来。
③读入第3个代码4，判断4是否在串表之中，结果发现代码4在串表中。由代码4查表得到相应的字串ab，将ab输出。再由旧代码（此时旧代码为2）查串表得到其对应的字符b，将b当成ω；再由当前代码4查出其对应的字符为ab，取其左侧第一个字符作为k，此时的ωk为ba，将ba写入代码（即指针）为5的位置上。至此，在原来的初始化串表的基础上已增加了两项。将代码4作为旧代码保存下来。
④类似上述过程逐步进行。
⑤当读入第6个代码8时，判断代码8是否已存在于串表中，结果发现找不到8，即代码8所对应的字串尚未定义。这种没有定义的情况可这样处理：由此时的旧代码（这时的旧代码为5），查出其输出为ba，并把它当成ω，同时，把ba左侧第一个字符当成k。这时构成的ωk即变为bab，则字符串bab就是代码8的输出。同时，将bab写入代码（指针）为8的串表中。将代码8作为旧代码保存起来。
解压缩过程就是这样一个输入代码接一个输入代码地进行下去，直到结束。
可以看到，若输入的代码存在于表中，则查表输出，形成ωk并修改（增加）串表项，将当前代码变为旧代码。
若输入的代码不在串表中，则用那时的旧代码查出输出并定义其为ω；将ω左侧第一个字符（或从右向左数最后一个字符）定为k，形成一个ωk，此ωk就是输出字符串；把此ωk写入代码所对应的串表中--增加串表项；将当前代码作为旧代码保存起来。做这样四件事便可实现译码。
有关LZW数据压缩算法就简单介绍到这里。LZW方法应用十分广泛，尤其在磁盘数据压缩时经常见到。
3.4.7混合编码
有关混合编码的含义前面已经说明。混合编码不仅应用于音频信号的处理，同样也用于图像信息的处理。
混合编码可以综合多种压缩编码的优点，为人们带来好处。例如，就图像压缩来说，变换压缩方法能将时域的信息变换到另一个（频域）中去处理。在频域中，信号的特征（能量）都集中在少数几个系数上，因而可获得好的压缩比。
如果在变换编码的基础上再进一步采用其他算法，例如，采用预测编码、哈夫曼编码或其他编码手段，则有可能进一步减少冗余度，使编码的效率进一步提高。
当然，混合编码可有多种组合形式，其目的都在于最大限度地提高编码效率。
3.5静态图像的JPEG技术标准
静态图像数据的压缩技术是多媒体技术的重要组成部分，它引起了广大技术人员的关注和研究。1986年国际标准化组织（ISO）和当时的国际电报电话咨询委员会（CCITT）联合组织了一个技术委员会JPEG（JointPhotographicsExpertsGroup）--联合图像图形专家组。该组织的目的就是制定静态图像图形数据压缩的国际标准。经过几年的不断努力，终于在1991年提出了连续色调静态图像的数字压缩和编码的标准，这就是通常所说的JPEG标准。
由于JPEG标准是一个适应范围十分广泛的通用标准，因此，它既可以用于灰度图像，又可以用于彩色图像，支持各种各样的应用。本节将对JPEG标准作概要介绍。
3.5.1JPEG的基本内容
JPEG的主要思路是对静态图像进行压缩编码，将压缩的数据进行存储或传送。同时，还要考虑对已压缩的图像数据进行解码，以便重建原始图像。其过程可用图318所示的编码过程框图和图319所示的解码过程框图表示。
JPEG标准实际上就是围绕着图318和图319中所标明的部分进行的。其中主要部分如下。
（1）源图像数据。有各种扫描形式和格式。
（2）编码器。即JPEG的数据压缩算法，同时也应当包括解压缩的算法。
（3）已压缩图像数据。这些数据要存储、传送、交换，必定要具有标准的格式，以便能在不同的环境下使用已压缩图像数据。
以上提到的信源、算法和交换都需要标准化，它们是JPEG标准的核心问题。下面将对它们逐一加以说明。
3.5.2编码算法
由于JPEG希望满足各种应用和需要，而实际上用一种算法很难做到这一点，于是，JPEG将编码算法分成两大类：基本系统和扩展系统。基本系统算法简单，实现起来比较容易；扩展系统采用更加复杂的算法，可提供更好的性能。在这里主要说明基本系统中的编码算法。JPEG标准规定了两类编码和解码算法：有失真算法和无失真算法。
1．有失真算法
有失真算法是基于离散余弦变换的算法，即DCT算法。最简单的DCT过程是基本顺序（BaselineSequential）过程，此过程适用于许多场合。除此之外，还有四种扩展顺序，均基于DCT，它们是基本顺序的扩展，适用于更广泛的应用领域。
图320基于DCT的编码过程图320所表示的有失真（有损）编码过程类似于图316，其中源图像是把整幅图像分成8×8个样本的小块，即子块。每次编码过程处理其中一块，而后逐块进行编码。8×8的样本块经快速余弦变换（FDCT），产生64个DCT系数，其中，一个是直流分量DC系数，63个为AC系数。每个系数用量化表中所给出的量化间隔分别进行量化，便得到规格化的量化系数。
可对得到的规格化量化系数中的DC系数进行差分编码，这是由于DC系数实质上是8×8样本子块的平均值，而相邻子块间通常相关性较大，它们的样本平均值也较接近。于是，编码就采取本子块DC系数减前一子块DC系数所得的差值进行，即差=DCiDCi1，而且通常差值比较小。
图321AC系数的“Z”字形排序
对于所得到的规格化量化系数中的AC系数，首先进行“Z”字形排序，如图321所示。排序的先后顺序如图321中箭头所示。即从AC01开始，顺序为AC10，AC20，AC11，AC02，…，直到AC77。这样，AC系数就被排列为一维的数据序列。
接下来就是对重新排序的AC系数和差分DC系数进行熵编码，以便达到进一步压缩的目的。
JPEG标准指出有两种熵编码算法可以使用：哈夫曼（Huffman）编码和算术编码。其中算术编码不需要哈夫曼编码所用的各字符统计特性构成的表。
在顺序DCT编码过程中，使用哈夫曼编码。在进行哈夫曼编码前，先要对差分DC系数和AC系数进行分组，也就是将它们以一定的大小范围分成若干组。DC系数（差分）及AC系数（规格化）的分组情况如表37所示。
根据表37对DC系数和AC系数的分组，可分别对DC系数和AC系数进行编码。DC系数的编码分两步进行。
首先，由分组大小（ssss）和DC系数构成一个中间码，也可叫做过渡符号。例如，上节中8×8样本子块的DC系数量化后为15。假定其前一样本子块的DC系数为13，则其差值为2。根据差值--差分DC系数2查表37，可以得出分组大小为2，而此时的DC系数也是2，那么，中间码就是（2）（2）。
其次，利用中间码分组大小2查JPEG提供的亮度（或）色度DC系数哈夫曼编码表，从而可以得到该分组的编码为011，并将此码放在前面。在查得的分组编码的后面附加上DC系数2的编码值（用补码表示，值为10），便得到最后的DC系数的输出编码为01110。
对AC系数的编码是在“Z”字形排序之后，此时中间码的前一部分由行程长度和分组大小两部分组成。行程长度是指非零系数前0的个数，分组大小则由表37来决定。若将前一节中规格化DCT系数中的AC系数“Z”字形排序，则可得到这样的序列：
0-2-1-1-100-10000000000000000000
000000000000000000000000000000000000
中间码的后一部分就是AC系数的值，用二进制补码来表示，因为DCT系数可正可负。
现在来看上述AC系数的第一个非零值-2。它前面的行程长度，即0的个数为1。其值为-2，查表37得出分组大小为2。于是，中间码的前一部分就是1/2，而后一部分为-2的补码，表示为10。
再由中间码的前一部分1/2查由JPEG提供的亮度（或色度）AC系数哈夫曼表，即可求得此系数编码为11011。
将查得的11011附加上用补码表示的系数值10，就构成了此系数的编码输出。
在JPEG中，规定行程长度，即连续0的个数，用4位二进制数表示，则最大只能表示15个连续的0。但可用15/0表示16个0而且可连续表示。同时，JPEG规定用中间码（0/0）表示一个子块的结束。综上所述，可用中间码的形式表示前面所举8×8样本子块：
（2）（2），（1/2）（-2），（0/1）（-1），（0/1）（-1），（0/1）（-1），（2/1）（-1），（0/0）
再分别利用哈夫曼表，中间码中的幅值用2的补码表示，如2→10，-2→01，-1→0，即可得到最后熵编码的输出序列为。
其中最后4位1010即为子块结束的中间码（0/0）。
可以看到，经过上面的处理之后，表示8×8个样本只需31bit。经压缩后，每个样本不到0.5bit。
总之，有失真编码过程的关键步骤如下：
①对子块进行快速离散余弦变换（FDCT）；
②利用JPEG提供的量化间隔表对系数量化；
③对DC系数取差分值，对AC系数进行“Z”字形排序；
④对DC系数和AC系数进行熵编码，先找出中间码，再通过查JPEG给出的表即可实现编码输出。
有失真的译码过程与编码过程的顺序恰好相反，其过程框图如图322所示。
对于已压缩图像数据的解压缩译码过程，此处不再详细说明。其主要步骤罗列如下：
①利用JPEG提供的有关哈夫曼编码表进行熵译码，从而获得规格化DCT系数；
②利用JPEG提供的量化间隔表对DCT系数进行逆量化，获得DCT系数；
③对DC系数差分译码并对AC系数进行重新排序，从而得到8×8DCT系数；
④对DCT系数进行反向余弦变换（IDCT），获得重建的8×8原始图像。
2．无失真算法
为了满足不同使用者的需要，JPEG还提供了一种不失真的静态图像压缩算法。这种压缩算法实现起来比较简单而且不使用DCT。这是一种基于预测的图像压缩方法。利用JPEG提出的算法对中等复杂程度的彩色图像进行压缩，典型的无失真压缩比可达到2∶1。
无失真编码器的框图如图323所示，预测器利用源图像数据由其相邻的像素点样本预测当前的样本值。在JPEG标准中，预测点x和其相邻的样本间的位置规定如图324所示。由图324可以看到，点x的预测值要用点a、b、c的值来求得。显然，a与x在同一行上，而点b、c则在前一行上。
JPEG提供了8种可供选择的预测算法，现将它们列于表38中。
