CN1067833C - 数字影像数据的压缩/解压缩方法 - Google Patents

Abstract

数字影像数据的压缩/解压缩方法，该数字影像包含一目前像素，其值为X，及两个与其邻接的象素，其值分别为A、B，Δ为A、B间之差值，该压缩方法包括：(1)根据与X相邻的象素A、B值产生目前像素X的一预测值P；(2)计算P及X间的差值e；(3)以一第一准则，将e值映射成一预测误差值e′；(4)产生一参数k，其为Δ的一函数；(5)根据参数k值对目前像素的预测误差值e′进行莱斯编码，而获得一编码值；(6)如所得编码值位元数超过一预定长度，则以一替代码取代该编码值。

Description

数字影像数据的压缩/解压缩方法

本发明有关一种数字影像数据的压缩/解压缩方法。

针对数字影像数据的压缩，习知的可变长度霍夫曼(Huffman)编码方法的主要缺失，系于编码之前需先对所有的编码分类(class)建立完整的一概率表(probability table)。针对即时(real-time)高速的数据压缩需求，此一缺失显已构成严重的瓶劲，此因霍夫曼概率表需适时的更新之故。美国专利号4,916,544披露一个有条件的编码方式，其系考虑被编码像素的值以及两个邻近像素之值，才指定一个可变长度码给被编码像素。于此4,916,544专利中，实质上具相同出现机率的影像值被合并成一编码类(class)。尤其当影像抓取速度很高时，习知的影像压缩/解压缩方法都不足以应付。

针对此，本发明提供一种利用莱斯(Rice)编码的数据压缩/解压缩方法。

本发明提供的一种数字影像数据的压缩/解压缩方法，此数字影像包含一目前像素，其值为X，及两个与其邻接的像素，其值分别为A、B，Δ为A、B间之差值，此方法包含一压缩步骤，其包含：

根据A、B值产生目前像素的一预测值P；

计算P及X间的差值e；

以一第一准则，将e值映射成一预测误差值e′；

产生一参数k，其为Δ的一函数；

根据参数k值对目前像素的预测误差值e′进行莱斯编码，而获得一编码值；

如所得编码值位元数超过一预定长度，则以一替代码取代该编码值，替代码由一预定型态码其后跟随X值所构成。

本发明的目的、特征及优点将参考附图，结合实施例进行详细描述。

附图简要说明：

图1揭示被压缩像素与邻近像素的关系；

图2揭示本发明方法中的压缩流程；

图3揭示本发明方法中的解压缩流程；

图4揭示执行本发明解压缩流程的一硬件实施例；

图5揭示图4中解码单元之一细部设计。

如图1所示，设目前待压缩像素40之值为X，而同一列前一像素44之值为A，同一行中前一像素42之值为B。于下述，以八个二进位码来代表像素值，亦即每个像素值介于0与255之间。

1、压缩

图2的流程中主要包含四个程序，即预测2、差值映射(mapping)4，莱斯编码6、及统计图末尾舍入(Histogram Tail Truncation)12。

(a)预测

由于自然影像(natural image)之特征，一个影像内相邻像素间之相关性(correlation)都应很高，除了影像边缘区域之外。因此，一般而言，目前待压缩像素的值X可以藉相邻像素值加以预测。

为了简化硬件的设计；本发明采用公式P=(A+B)/2以产生目前像素的预测值P。经由公式e=X-P之计算，预测值与真正值X之差值e即可获得。此值由图2的方框2输出。

举例而言，当A=130,B=146,X=144时，预测值P=138，而差值e=X-P=6。

(b)差值e的映射

差值e的可能范围为[-P,255-P]。当极端情形(P=0,X=255)或(P=255,X=0)发生时，差值可能介于[-255,255]间，此范围之值需要九位元代表。

下述映射程序之目的即执行对差值e的一对一映射，使映射的结果e′只需八位元代表。值得注意的是，此一映射程序只是一选择(optional)性程序，缺少此一程序并不影响发明的其他步骤。

if(e≠0)

{

      if(p≤128)

      if(|e|≤p)

            if(e＜0)e′=-2^*e

            else    e′=2^*e-1

       else e′= p +|e|

 else

       if(|e|＜(255-p))

            if(e＜0)e′=-2^*e

            else    e′=2^*e-1

       else e′=255-p+|e|

当P≤128，上述步骤将差值e的可能[-P,-P+1,-P+2,...-1,0,1,...,P,P+1,P+2,...,255-P]值分别映射成[0,+1,-1,+2,-2,...+P,-P,P+1,P+2,...255-P]的误差预测值e′。

而当P≥128,差值e的可能值[-P,-P+1,-P+2,...-1,0,1...,P,P+1,P＋2,...,255-P]被分别映射成[0,+1,-1,+2,-2,...255-P,-(255-P),-(255-P)-1,...-P]的误差预测值e′。值得注意的是，经过此一映射程序，仍能达到小e值映射小e′值的要求。

当P=138,e=6时，此e值被映射成e′=2×e-1=11，此值于图2中的方框四输出。

(c)莱斯编码(表1)

由于小差值发生的机率一定高于大差值发生的机率，因此吾人亦采用统计的概念进行编码，以便节省编码的大小。本发明采用下述的莱斯编码法。

莱斯编码法包含下列步骤，藉参数k对整数n进行编码：(1)先计算「(n/2^k)」值，并将所得以单进(Unary)码表示，其中「」代表整数运算，亦即「(n/2^k)」个“1”，然后再加上一个位元的“0”作为分隔码，此分隔码分隔单进码及下述的二进位码；(2)计算(n mod 2^k)，mod为余数运算，然后所得值以k位元二进位码方式输出；(3)将(1)(2)所得码组合即形成莱斯码。

举例而言，当n=4,k=2,「(n/2^k)」=「(4/4)」=1，此时单进码为“1”；(n mod 2^k)=(4 mod 4)=0，其二位元二进位码为“00”。此二码组合后(须先加一个分隔码“0”)，得到其莱斯码为“1000”，其中右边向左数第三个“0”即为分隔码。表1列示有n=0～8时，而参数k=0～3时，其分别对应的莱斯码。

表1

Rice	n=0	n=1	n=2	n=3	n=4	n=5	n=6	n=7	n=8
k=0	0	10	110	1110	11110	111110	1111110	11111110	111111110
k=1	00	01	100	101	1100	1101	11100	11101	111100
k=2	000	001	010	011	1000	1001	1010	1011	11000
k=3	0000	0001	0010	0011	0100	0101	0110	0111	10000

由表1可知，采用小参数k值来编码小整数值n较有利。相反地，采用大参数k值来编码大整数值较有利。因此，如何选择一个适宜参数k值就成为一个关键的问题。因对所有邻近像素值A,B言，清楚定义e′是小或大是有困难的，因此可能有许多准则可选择k值。但为了硬件的单纯，最好选择一个单纯的法则选择k值。

对自然影像而言，邻接的影像都呈现高度相关，除了边缘部分之外，因此，只于影像边缘区的像素会产生大的e′值。而边缘区的存在与否可由邻接点值A,B获知。本发明所采用的一法则系取k=α(Δ)，其中α为依下述准则的运算子，Δ|A-B|。

k=1,ifΔ＜=2

k=2,if2＜Δ＜=4

k=3,if4＜Δ＜=8

k=4,if8＜Δ

例如，A=130,B=146，则Δ=16，因而取k=4。当以参数k=4来对e′=11编码时，「(n/2^k)」=「(11/16)」=0，亦即单进码的数目为零；(n mod 2^k)=(11 mod 16)=11，其4位元二进位码为1011。因此，e′=11时，目前像素X的莱斯码为01011。

(d)统计图末尾舍入：

通常，得到长的莱斯码的机率很小。但一旦发生，会使得压缩比变差，且为了对付这些长莱斯码，硬件的设计也变复杂。流程图中的方框10及12可预防此问题的发生。当所得的莱斯码的长度大于16位元时，前述的编码方式即停止，而目前像素码即以一个24位元的码代替。此24位元码包含16位元的前导“1”值，然后跟随8位元的像素值。16位元的前导“1”作为一个前置(prefix)指标，以告知：后面8位元值即为目前像素的真正值。

例如，当邻近像素的A,B值分别为140，且目前像素位在边缘区且其值X=10(二进位码=00001010)时，P=140Δ=0,k=1,e=130,而e′=245，以k=1对e′=245编码时，其莱斯码为122个“1”加上“0”加上“1”(二进位码)。但其长度大于16个位元，故以111111111111111100001010取代。

(e)电路

基于前述末尾舍入法则，可使得电路的设计变得非常单纯。上述关于压缩程序可以用一些简单的缓冲器(buffer)，及算术、逻辑运算子，如+,-,X,/，及比较运算来完成。对熟习此项技术人士而言，此一硬件线路的设计是多样化而具许多选择。

2、解压缩

如图3所示，本发明的解压缩方法包含四大程序：即统计图末尾舍入的回复22，莱斯码解码24，预测误差的映射34以及目前像素值的产生36。

(a)统计图末尾舍入的回复

首先，先确定被解压缩的码是否有前置值，其为16个前导“1”位元。如有，则于方框26中直接将后面的8位元值作为目前像素值。否则，此一码送至方框24作莱斯解码，以求得预测误差。

例如，如码值111111111111111100001010须作解压缩，吾人可用几个“与”门就可测得16个“1”值的存在。因此，直接将00001010作为像素值即可。

(b)莱斯码解码

于方框24中，利用前述莱斯编码法叙述中有关的相同准则，吾人先利用邻接像素值之差产生k参数值。依所获得之k值，可变长度莱斯码被解码后即可得到目前像素的预测误差e′。

例如，假如邻接像素的解码完成后分别得到像素值A=130,B=146。利用压缩时所用的准则，即Δ=|A-B|,k=α(Δ)，则k=4。对莱斯码01011进行莱斯解码，其过程为：2^k=16，且无单进码，故「(n/16)」=0，所以n＜16,1011=11(十进位)，由(n mod 16)=11，得n=11。亦即经由解码，得到其预测误差e′=11。

(c)预测误差e′，的映射：

获得预测误差e′后，采用反向映射即可得到目前像素值与预测值之差e。其详细的步骤如以下的程序：

                     {

                   if(p＜128)

                       if(e′＜2^*p)

                                if(e′is odd) $e=\left[\frac{e\′}{2}\right]+1$

                                      else $e=-\frac{e\′}{2}$

                             else e=e′-p

                    else

                         if(e′≤2^* p)

                               if(e′is odd) $e=\left[\stackrel{e\′}{2}\right]+1$

                                else $e=-\frac{e\′}{2}$

                          else e=-e′-P

                        }

(d)目前像素值的产生

目前像素的预测值由公式P=(A+B)/2得到，此相同于压缩时所用的公式。最后，将预测值加上差值e，即可得到目前像素值，即X=p+e。

(e)电路

本发明所采用的解压缩电路，如图4所示。其分别进行：(1)将像素码数据由目前行缓冲器(buffer)64送至莱斯解码器68进行解码，或送至统计图末尾舍入滤波器(filter)70，供取得八位元的像素原始值；(2)解码器68输出e′值至另一解码单元74以产生目前像素X值；(3)统计图末尾舍入滤波器70或解码单元74的输出被写入至写缓冲器(Write buffer)76；(4)写缓冲器的值送至输出缓中器80。

当系统是采用32位元的总线时，缓冲器读-写运作最有效率的方式亦为32位元传输方式。输入缓冲器72接收并暂时储存被压缩影像数据，而输出缓冲器80暂时贮存并输出已解压缩的影像值至外围设备装置。每当它收到的数据超过32位元，则64位元长的写缓冲器76将32位元内容送至输出缓冲器80。

目前行缓冲器64及上一行缓冲器62皆为64元宽。有两个指标，目前行缓冲器指标66及上一行缓冲器指标64供分别指示其内有效内容值之长度。目前行缓冲器64内贮存待解压缩之码。当目前行缓冲器指标值小于32时，会从输入缓冲器72将一个32位元数据送给目前行缓冲器64。

由于统计图末尾舍入之安排，本发明最长的编码为24位元，每当一个32位元传输完毕时，在目前行缓冲器64内存在至少一待解压缩码等待被解压缩。上一行缓冲器62贮存邻近像素数据供解压缩之用。每当解码完成乙次，上行缓冲器指标值60减少8(位元)。同样地，当上一行缓冲器指标值小于32时，会从输出缓冲器80将一个32位元数据送给上一行缓冲器62。

PK单元67供产生参数k及预测值p，其由上一行缓冲器62及最后位元组缓冲器78分别取得邻接像素值A、B。

依据参数k值，莱斯解码器68将由目前行缓冲器64送来之码予以解码，解码的方式系检测第一个“0”位元，以检测尾随其后的k位元二进位码，经过运算及判断后，输出预测误差e′至解码单元74。

根据e′、P值，解码单元74算出差值e，以及利用公式X=p+e，计算出X值，然后将其送至写缓冲器76以及最后位元组缓冲器78。

图5揭露一个解码单元74的实施例。其中，MUX代表多工器，ADD代表一个加法器，SUB代表一个减法器。图5中信号的意义分别为：

ME=e′           ,MEB=e′=(255-e′)

ME05=e′/2       ,ME05B=e′/2=(255-ME05)

P2=P^*2       ,P2B=(255-P2)

ME_ODD =1         当e’为奇数

       =0      当e’为偶数

P_GE_ 128=1  当P＞=128

       =0  当p＜128

Claims (6)

1、一种数字影像数据的压缩/解压缩方法，此数字影像包含一目前像素，其值为X，及两个与其邻接的像素，其值分别为A、B，Δ为A、B间之差值，此方法包含一压缩步骤，其包含：

根据A、B值产生目前像素的一预测值P；

计算P及X间的差值e；

以一第一准则，将e值映射成一预测误差值e′；

产生一参数k，其为Δ的一函数；

根据参数k值对目前像素的预测误差值e′进行莱斯编码，而获得一编码值；

如所得编码值位元数超过一预定长度，则以一替代码取代该编码值，替代码由一预定型态码其后跟随X值所构成。

2、如权利要求1所述的方法，其中，所述预定型态码为一组连续“1”值所组成。

3、如权利要求1所述的方法，其中，所述预测误差e′是差值e的一对一映射，使得表示预测误差e′所需的位元数少于表示差值e所需的位元数。

4、如权利要求1所述的方法，其中，所述预测误差e′等于差值e。

5、如权利要求1所述的方法，其中，此方法进一步包含一解压缩方法，其包含：

如待解压缩的编码值的领先位元包含该预定型态码，则输出该X值。

6、如权利要求1所述的方法，其中，此方法进一步包含一解压缩方法，其包含：

如果待解压缩的编码值的领先位元未包含该预定型态码，则根据A、B值产生预测值P；

根据前述函数，由Δ值产生k值；

根据k值，将编码值予以解码，以获得预测误差e′；

根据第一准则及e′值，计算差值e；

将预测值p与差值e相加，以获得目前像素值X。

Images