CN102651795B - 游长缩减的二元序列压缩编码方法 - Google Patents

Abstract

本发明公开了一种游长缩减的二元序列压缩编码方法，它包括：首先将待压缩文件转换为由0和1组成的二值码序列；再将该二值码序列转换为游长序列，计算游长序列中0游长与1游长的算术平均值；获取0游长与1游长的最大缩减次数；生成游长缩减后的游长子序列及其游长缩减前后的转换关系的二值码表；构造游长子序列经缩减后的游长子序列长度编码表，依次拼接各游长子序列长度编码表，生成游长序列的长度编码表；生成游长转换关系编码表；分别在长度编码表和游长序列转换关系编码表的首部加入文件头数据，生成二值码序列的压缩编码表。该方法能够避免对较短游长重新编码，导致的编码位数增加，提高编解码效率，算法简单，易于实现。

Description

游长缩减的二元序列压缩编码方法

技术领域

本发明涉及一种游长缩减二元序列压缩编码方法，属于数据无损压缩技术领域。 

背景技术

现今的电子信息技术领域中，大部分信息是以数字化的方式表示的。数字化多媒体信息尤其是数字视频、音频信号的数据量特别庞大，给存储和传输带来很多问题，如果不对数据进行有效的压缩就难以得到实际的应用。因此，数据压缩技术成为当今数字通信、广播和多媒体中的一项关键技术。

二值图像、文字页面、工程图纸和电路图等经逐行提取元素后均为一种二元序列，将二元序列中的二元分别取为0元和1元，二元序列中的连续的0元和连续的1元组成的一段分别称为一个0游程或1游程，0游程长度称为0游长，1游程长度称为1游长。传统的二元序列的压缩方法一般采用一维游程编码，一维游程编码的基本原理是利用变长编码方法分别对二元序列中的全体0游程和全体1游程无论长短均重新进行编码，对较短游程重新编码后往往导致新的编码位数超过较短游程长度，导致数据量的膨胀，降低了总体的编码压缩效能。例如，国际传真标准CCITT.4(G3)利用Huffman编码对游程进行编码，其压缩效能较低。

本发明提出一种具有选择性的游长缩减的二元序列压缩编码方法，该方法根据二元序列中0游程和1游程的分布状况，分别选取最佳临界0游长和最佳临界1游长，对二元序列中游长大于等于最佳临界0游长的全体0游程，采用其游长缩减后的长度与游长缩减前后的转换关系的一位码元重新进行编码，对二元序列中的全体1游程按相同方法处理，实现较长游程的压缩编码。对游长小于最佳临界0游长的全体0游程和游长小于最佳临界1游长的全体1游程用其原始编码表示，不重新编码，避免了因对较短的0游程和较短的1游程重新编码后所导致的位数增加。解码时只需对游长大于等于最佳临界0游长和最佳临界1游长的0游程和1游程，通过游长缩减后的游长与缩减前后转换关系码元，即可复原原始0游程与1游程的长度。

发明内容

本发明的目的在于针对现有技术存在的问题提出一种游长缩减的二元序列压缩编码方法，该方法算法简单，易于实现，压缩效能高于传统的一维游程编码方法。

本发明提出的游长缩减的二元序列压缩编码方法，包括以下步骤：

（1）、将二元序列中的二元分别用数值“0”和“1”表示，二元序列转换为0和1组成的二值码序列；

（2）、计算步骤（1）所述的二值码序列中全体0游程和全体1游程的游程长度，用游程长度值依次取代二元序列中全体游程后，生成游长序列，其中，0游程对应的游程长度为0游长，1游程对应的游程长度为1游长；

（3）、分别计算步骤（2）所述游长序列中全体0游程和全体1游程的游程长度算术平均值，分别选取游长序列中0游长与1游长的最大临界游长；

（4）、对步骤（2）中所述的游长序列按每组1024个游长单元进行分组，得到游长序列的各个游长子序列，分组后每个游长子序列的单元个数均为1024，最后一个子序列的单元个数为：           

                      N=1024+(M%1024)                                    (1)

其中,N为最后一个游长子序列的单元个数，M为游长序列总的单元个数，符号“%”表示求余；

（5）、分别计算步骤（4）所述游长子序列中的全体0游长和全体1游长在临界游长取值为1，2，…，n时的编码位数，n为最大临界游长，确定最佳临界0游长和最佳临界1游长，具体如下：

（5-1）、分别确定游长子序列中全体0游长和全体1游长在临界游长为p时的编码位数，其中1≤p≤n，具体如下：

（5-1-1）、确定游长子序列中全体0游长在临界游长为p时的编码位数

选取游长子序列中游长大于等于p的全体0游长，对选取后的各0游长值加上p后整除2，得到0游长缩减后新的0游长，余数为0或1，余数表示0游长缩减前后的转换关系的一位码元，新的0游长值加1为原0游长在临界游长为p时的编码位数，将上述选取后的全体0游长在临界游长为p时的编码位数相加，其和记为S₀，并将S₀与游长子序列中全体0游长小于p的0游长值相加，得到游长子序列中全体0游长在临界游长为p时的编码位数；

（5-1-2）、确定游长子序列中全体1游长在临界游长为p时的编码位数

选取游长子序列中游长大于等于p的全体1游长，对选取后的各1游长值加上p后整除2，得到1游长缩减后新的1游长，余数为0或1，余数表示1游长缩减前后的转换关系的一位码元，新的1游长值加1为原1游长在临界游长为p时的编码位数，将上述选取后的全体1游长在临界游长为p时的编码位数相加，其和记为S₁，并将S₁与游长子序列中全体1游长小于p的1游长值相加，得到游长子序列中全体1游长在临界游长为p时的编码位数；

（5-2）、分别确定游长子序列中0游长与1游长的最佳临界游长，具体如下：

选取游长子序列中全体0游长在其对应的各临界游长中编码位数最小值，该最小值对应的临界游长为最佳临界0游长；选取游长子序列中全体1游长在其对应的各临界游长中编码位数最小值，该最小值对应的临界游长为最佳临界1游长；

（6）、按步骤（5-2）所述的最佳临界0游长和最佳临界1游长，对步骤（4）所述的各个游长子序列利用步骤（5）所述方法进行缩减，生成游长缩减后的游长子序列及其游长缩减前后的转换关系的二值码表，具体如下：

（6-1）、选取游长子序列中游长大于等于最佳临界0游长的全体0游长，对选取后的各0游长加上最佳临界0游长后整除2，得到游长缩减后新的0游长，余数为0或1，余数表示0游长缩减前后的转换关系的一位码元，0游长缩减后的长度值所对应的一串0元与转换关系码元为0游长的压缩编码，小于最佳临界0游长的全体0游长不重新编码；

（6-2）、选取游长子序列中游长大于等于最佳临界1游长的全体1游长，对选取后的各1游长加上最佳临界1游长后整除2，得到游长缩减后新的1游长，余数为0或1，余数表示0游长缩减前后的转换关系的一位码元，1游长缩减后的长度值所对应的一串1元与转换关系码元为1游长的压缩编码；小于最佳临界1游长的全体1游长不重新编码；

（6-3）、将缩减前后转换关系码元按0游长和1游长交替的方式依次摆放，生成游长子序列缩减前后转换关系二值码表；

（7）、构造游长子序列经缩减后的游长子序列长度编码表，依次拼接各游长子序列长度编码表，生成步骤（2）所述游长序列的长度编码表，具体如下：

对步骤（6）所述的游长缩减后的游长子序列，按0和1交替的方式的依次摆放其所对应的一串0元和一串1元，生成游长子序列缩减后的二值码子序列，将二值码子序列加上2个前缀，前缀为游长子序列中全体0游长和全体1游长是否可缩减的状态标记，以及0游长和1游长的最佳临界游长，其中，压缩状态标记用0或1表示，0表示不可缩减，所对应的游长子序列中的全体0游长或全体1游长经缩减后的编码位数大于原游长子序列中全体0游长或全体1游长的编码位数，则不可重新编码，第一个前缀为0，第二个前缀为“空”，“空”表明无需在此前缀处填入数据；压缩状态标记1表示可缩减，第一个前缀为1，第二个前缀为最佳临界游长。，将置入前缀后的二值码子序列称为游长子序列的长度编码表，依次将游长子序列的长度编码表拼接起来，生成步骤（2）所述游长序列的长度编码表；

（8）、依次拼接步骤（6-1）所述的游长子序列游长缩减前后的转换关系二值码表，生成游长序列转换关系编码表；

（9）、合并步骤（7）所述游长序列的长度编码表及步骤（8）所述的游长序列转换关系编码表，生成步骤（1）所述二值码序列的压缩编码表。

上述步骤（3）所述的分别选取游长序列中0游长与1游长的最大临界游长n，其具体如下：当游程算术平均值小于16时，则确定最大临界游长n=8；当游程算术平均值大于等于16时，则确定最大临界游长n=16。

上述步骤（6）中所述的对步骤（4）所述的各个游长子序列利用步骤（5）所述方法进行缩减，缩减次数不限于一次，最大缩减的次数的确定，具体如下：

如果游长算术平均值小于1.5，则确定最大缩减次数为2；

如果游长算术平均值大于等于1.5，小于2，则确定最大缩减次数为4；

如果游长算术平均值大于等于2，小于16，则确定最大缩减次数为8；

如果游长算术平均值大于等于16，则确定最大缩减次数为16。本发明的游长缩减的二元序列压缩编码方法的解码方式为游长缩减的反过程，换言之，二元序列经本发明方法压缩处理后，可生成一个压缩文件，通过对压缩文件的解码，即可复原原始文件，例如，游长子序列中0游长的最佳临界0游长为3，设101为该游长子序列中的一个0游长值，则0游长101经游长缩减后的游长为

round((101+3)/2)=52 转换关系码元为0

其中，round表示取整函数，101在原始的二值码序列中用连续的101个0表示，占用101位存储空间，经缩减后，其游长值为52，加上1位转换关系码元，共计53位，比原始的101位节省了48位。

游长复原过程为

2×52+0-3=101

以上步骤（1）-（9）为二元序列经一次游长缩减后生成压缩编码的过程，在实际应用中，可通过游长多次缩减来实现更高的压缩比。

本发明提出的游长缩减的二元序列压缩编码方法具有的优点是：该方法可针对游长子序列中游长的分布状况，对较长游长进行压缩编码，对较短游长不进行缩减，能够避免因对较短游长重新编码后所导致的编码位数增加，提高编解码效率，算法简单，易于实现，压缩效能高于传统的一维游程方法。

附图说明

图1是本发明的游长缩减的二元序列压缩编码方法流程图；

图2 是本发明的游长多次缩减的二元序列压缩编码方法流程图；

图3是采用本发明的游长缩减的二元序列压缩编码方法按压缩比为10.92压缩后的二值图像；

图4是采用本发明的游长缩减的二元序列压缩编码方法按压缩比为13.85压缩后的二值图像。

具体实施方式

本发明是一种游长缩减的二元序列的压缩编码方法，其具体的应用对象为数字图像、二值图像、文字页面、工程图纸和电路图等文件，上述文件经逐行提取元素后生成一种二元序列，将二元取值规定为0和1，其中，对256级灰度数字图像按位平面分解后，可得8个二元取值为0和1的二值图像文件，对24位彩色图像，将3个颜色值按位平面分解后，可得24个二元取值为0和1的二值图像文件。对由上述文件转换后的二元序列经本发明方法压缩处理后，可生成一个压缩文件，通过对压缩文件的解码，即可复原原始文件。

本发明提出的一种游长缩减的二元序列压缩编码方法，如图1所示，该方法中可对二元序列中的游长进行多次缩减，直至达到最佳的压缩效果，如图2所示，首先将待压缩文件转换为由0和1组成的二值码序列，再将该二值码序列转换为游长序列，通过游长序列中0游长与1游长的算术平均值获取0游长与1游长的最大缩减次数，最大缩减次数的确定，具体如下：

如果游长算术平均值小于1.5，则确定最大缩减次数为2；

如果游长算术平均值大于等于1.5，小于2，则确定最大缩减次数为4；

如果游长算术平均值大于等于2，小于16，则确定最大缩减次数为8；

如果游长算术平均值大于等于16，则确定最大缩减次数为16。

将游长序列按步骤（4）所述进行分组处理，生成游长子序列，对各游长子序列中0游长和1游长按0游长最大缩减次数和1游长最大缩减次数分别进行多次缩减，每次缩减时均选择1次最佳临界0游长和最佳临界1游长，按最佳临界0游长和最佳临界1游，分别对游长子序列中的全体0游长和全体1游长进行游长缩减，将多次缩减后的游长子序列按游长属性，即0游长或1游长，转换为游长子序列的二值码序列，加上前缀，生成游长子序列长度编码表，将游长子序列长度编码表依次合并，生成游长序列长度编码表，合并游长序列长度编码表与游长多次缩减过程中生成的转换关系编码表，生成原始二值码序列的压缩编码文件，实现对二元序列的无损压缩。

上述方法中对游长序列的分解是以每组1024个单元来进行分组的，如果游长序列总的游长单元个数少于或等于1024，则不进行分组，这种情形通常会出现在尺寸较小的二值图像中，

如果游长序列总得游长单元个数大于1024，且不是1024的整数倍，则游长序列分组后的最后一组游长子序列的单元个数为下述公式给出：

                      N=1024+(M%1024)                                    

其中,N为最后一个游长子序列的单元个数，M为游长序列总的单元个数，符号“%”表示求余。

上述方法中对游长子序列中0游长与1游长分别按0游长与1游长最大缩减次数进行多次缩减，在具体实施中，如果游长子序列中0游长经k+1次缩减后的编码位数大于第k次缩减后的0游长编码位数，其中k+1小于等于0游长最大缩减次数，则游长子序列中0游长只进行k次游长缩减，缩减次数记为k，对1游长也按相同方式处理。

上述方法中游长子序列长度编码表由两部分内容组成，一是码表的前缀，前缀由压缩状态标记、游长缩减次数、各次游长缩减的最佳临界游长等三段码元组成；二是游长子序列经多次缩减后，新的游长子序列所对应的二值码子序列。如果将游长子序列的顺序下标记为0,1,2，…，游长子序列中的各游长单元按其顺序下标分别称为偶游长或奇游长，如果游长序列中第一个游长单元为1游长，则全体游长子序列中第一个游长单元均为1游长，游长子序列中全体1游长为偶游长。参照表1，游长子序列长度编码表中第一段码元sign_o和sign_e为游长子序列中偶游长和奇游长的压缩状态标记，游长子序列长度编码表中第二段码元S_o和S_e为偶游长与奇游长的缩减次数，如果子序列中偶游长最大缩减次数小于16，则S_o的位数为3位，否则S_o的位数为4位，S_e的位数按相同方式确定，游长子序列长度编码表中第三段码元o₁,o₂, …为游长子序列中偶游长经S_o次缩减后的各次偶游长最佳临界游长，e₁,e₂, …为游长子序列中奇游长经S_e次缩减后的各次奇游长最佳临界游长，如果游长子序列中偶游长最大缩减次数小于16，则o₁,o₂, …的位数为3位，否则o₁,o₂, …的位数为4位，e₁,e₂, …的位数按相同方式确定，游长子序列长度编码表中第四段码元为游长子序列经多次缩减后新的游长子序列所对应的二值码序列。

如果游长子序列长度编码表中第一段码元sign_o=0，sign_e=1，则游长子序列长度编码表中第二段码元为S_e，第三段码元为e₁,e₂, …；如果游长子序列长度编码表中第一段码元sign_o=1，sign_e=0，则游长子序列长度编码表中第二段码元为S_o，第三段码元为o₁,o₂, …，如果游长子序列长度编码表中第一段码元sign_o=0，sign_e=0，则游长子序列长度编码表中第二段与第三段码元均为空，见表1。

表1游长子序列长度编码表

上述方法中，对游长子序列中全体0游长经多次缩减过程中生成的转换关系码元，按倒序的方式摆放，即首先依次摆放最后一次缩减时的转换关系码元，接着依次摆放倒数第二次缩减过程中的转换关系码元，直至依次摆放第一次缩减时的转换关系码元，由此生成游长子序列中0游长缩减前后的转换关系编码表，按同样方式生成游长子序列中的1游长缩减前后的转换关系编码表，合并上述0游长与1游长的转换关系编码表，生成游长子序列的转换关系编码表，依次拼接各游长子序列的转换关系二值码子序列，生成游长序列的转换关系编码表。

现以两个尺寸为256×256的二值图像压缩为例，验证本发明的方法效果。上述两个尺寸为256×256的二值图像，见图3和图4，该两个二值图像中，二元取值分别为0与255，将上述二元取值规定为0和1，即二元中的0对应为0，二元中的255对应为1，经逐行提取二值图像像素后，生成一个由0和1组成的二值码序列，两幅二值图像的二值码序列长度均为256×256=65536位，经本发明方法压缩处理后，压缩后的文件总位数见表2。

表2 二值图像压缩后总位数

图3所示的256×256的二值图像

5999位

图4所示的256×256的二值图像

4732位

图3、图4表示的二值图像经本发明方法压缩后，压缩比分别为：

65536/5999 = 10.92

65536/4732 = 13.85

    从图3、图4两幅二值图像的压缩数据表明，本发明方法对二元序列的压缩具有较高的压缩效能。

以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。 

Claims (3)

1.一种游长缩减的二元序列压缩编码方法，其特征在于，所述方法是在计算机中依次按以下步骤实现的：

步骤（1），将二元序列中的二元分别用数值“0”和“1”表示，二元序列转换为0和1组成的二值码序列；

步骤（2），计算步骤（1）所述的二值码序列中全体0游程和全体1游程的游程长度，用游程长度值依次取代二元序列中全体游程后，生成游长序列，其中，0游程对应的游程长度为0游长，1游程对应的游程长度为1游长；

步骤（3），分别计算步骤（2）所述游长序列中全体0游程和全体1游程的游程长度算术平均值，分别选取游长序列中0游长与1游长的最大临界游长n；

步骤（4），对步骤（2）中所述的游长序列按每组1024个游长单元进行分组，得到游长序列的各个游长子序列，分组后每个游长子序列的单元个数均为1024，最后一个子序列的单元个数为：           

                      N=1024+(M%1024)                                    (1)

其中,N为最后一个游长子序列的单元个数，M为游长序列总的单元个数，符号“%”表示求余；

步骤（5），分别计算步骤（4）所述游长子序列中的全体0游长和全体1游长在临界游长取值为1，2，…，n时的编码位数，n为最大临界游长，确定最佳临界0游长和最佳临界1游长，具体如下：

步骤（5-1）、分别确定游长子序列中全体0游长和全体1游长在临界游长为p时的编码位数，其中1≤p≤n，具体如下：

步骤（5-1-1）、确定游长子序列中全体0游长在临界游长为p时的编码位数

选取游长子序列中游长大于等于p的全体0游长，对选取后的各0游长值加上p后整除2，得到0游长缩减后新的0游长，余数为0或1，余数表示0游长缩减前后的转换关系的一位码元，新的0游长值加1为原0游长在临界游长为p时的编码位数，将上述选取后的全体0游长在临界游长为p时的编码位数相加，其和记为S₀，并将S₀与游长子序列中全体0游长小于p的0游长值相加，得到游长子序列中全体0游长在临界游长为p时的编码位数；

步骤（5-1-2）、确定游长子序列中全体1游长在临界游长为p时的编码位数

选取游长子序列中游长大于等于p的全体1游长，对选取后的各1游长值加上p后整除2，得到1游长缩减后新的1游长，余数为0或1，余数表示1游长缩减前后的转换关系的一位码元，新的1游长值加1为原1游长在临界游长为p时的编码位数，将上述选取后的全体1游长在临界游长为p时的编码位数相加，其和记为S₁，并将S₁与游长子序列中全体1游长小于p的1游长值相加，得到游长子序列中全体1游长在临界游长为p时的编码位数；

步骤（5-2）、分别确定游长子序列中0游长与1游长的最佳临界游长，具体如下：

选取游长子序列中全体0游长在其对应的各临界游长中编码位数最小值，该最小值对应的临界游长为最佳临界0游长；选取游长子序列中全体1游长在其对应的各临界游长中编码位数最小值，该最小值对应的临界游长为最佳临界1游长；

步骤（6），按步骤（5-2）所述的最佳临界0游长和最佳临界1游长，对步骤（4）所述的各个游长子序列利用步骤（5）所述方法进行缩减，生成游长缩减后的游长子序列及其游长缩减前后的转换关系的二值码表，具体如下：

步骤（6-1）、选取游长子序列中游长大于等于最佳临界0游长的全体0游长，对选取后的各0游长加上最佳临界0游长后整除2，得到游长缩减后新的0游长，余数为0或1，余数表示0游长缩减前后的转换关系的一位码元，0游长缩减后的长度值所对应的一串0元与转换关系码元为0游长的压缩编码，小于最佳临界0游长的全体0游长不重新编码；

步骤（6-2）、选取游长子序列中游长大于等于最佳临界1游长的全体1游长，对选取后的各1游长加上最佳临界1游长后整除2，得到游长缩减后新的1游长，余数为0或1，余数表示1 游长缩减前后的转换关系的一位码元，1游长缩减后的长度值所对应的一串1元与转换关系码元为1游长的压缩编码；小于最佳临界1游长的全体1游长不重新编码；

步骤（6-3）、将缩减前后转换关系码元按0游长和1游长交替的方式依次摆放，生成游长子序列缩减前后转换关系二值码表；

步骤（7），构造游长子序列经缩减后的游长子序列长度编码表，依次拼接各游长子序列长度编码表，生成步骤（2）所述游长序列的长度编码表，具体如下：

对步骤（6）所述的游长缩减后的游长子序列，按0和1交替的方式依次摆放其所对应的一串0元和一串1元，生成游长子序列缩减后的二值码子序列，将二值码子序列加上2个前缀，前缀为游长子序列中全体0游长和全体1游长是否可缩减的状态标记，以及0游长和1游长的最佳临界游长，其中，压缩状态标记用0或1表示，0表示不可缩减，所对应的游长子序列中的全体0游长或全体1游长经缩减后的编码位数大于原游长子序列中全体0游长或全体1游长的编码位数，则不可重新编码，第一个前缀为0，第二个前缀为“空”，“空”表明无需在此前缀处填入数据；压缩状态标记1表示可缩减，第一个前缀为1，第二个前缀为最佳临界游长；将置入前缀后的二值码子序列称为游长子序列的长度编码表，依次将游长子序列的长度编码表拼接起来，生成步骤（2）所述游长序列的长度编码表；

步骤（8），依次拼接步骤（6）所述的游长子序列游长缩减前后的转换关系二值码子序列，生成游长转换关系编码表；

步骤（9），合并步骤（7）所述游长序列的长度编码表及步骤（8）所述的游长序列转换关系编码表，生成步骤（1）所述二值码序列的压缩编码表。

2.根据权利要求1所述的游长缩减的二元序列压缩编码方法，其特征在于，上述步骤（3）所述的分别选取游长序列中0游长与1游长的最大临界游长n，具体如下：

当游程算术平均值小于16时，则确定最大临界游长n=8；

当游程算术平均值大于等于16时，则确定最大临界游长n=16 。

3.根据权利要求1所述的游长缩减的二元序列压缩编码方法，其特征在于：上述步骤（6）中所述的对步骤（4）所述的各个游长子序列利用步骤（5）所述方法进行缩减，缩减次数不限于一次，最大缩减的次数的确定，具体如下：

如果游长算术平均值小于1.5，则确定最大缩减次数为2；

如果游长算术平均值大于等于1.5，小于2，则确定最大缩减次数为4；

如果游长算术平均值大于等于2，小于16，则确定最大缩减次数为8；

如果游长算术平均值大于等于16，则确定最大缩减次数为16。