一种图像数据无损压缩的编码方法

摘要

本发明公开了一种图像数据无损压缩的编码方法方法，它主要包括：从图像矩阵中提取一阶混合差分矩阵；依一阶混合差分矩阵元素的统计分布，确定合并次数与编码截断阶数；根据合并次数与编码截断阶数对一阶混合差分矩阵元素进行一次编码，实现一次压缩；对一次压缩编码二值码流进行二次编码，实现二次编码压缩。该方法能根据图像数据的统计特征选取压缩量最大情形下所对应的数据合并次数q与编码截断阶数p，依所选合并次数和编码截断阶数构造一种即时编码，灵活性强，算法简单，易于实现，编码效率高；该方法的一次压缩编码表的构成简单；该方法的编码前缀及编码后缀结构统一，解码过程无需匹配，解码效率高。

说明书

技术领域

本发明涉及一种图像数据无损压缩的编码方法，属于数字图像无损压缩技术领域。

背景技术

在信息环境中，信息大部分是以数字化的方式表示、存储和传输的，其中图像占了绝大部分。但是数字化的图像需要占用巨大的空间，为了对图像数据进行有效的处理、存储和传输，必须对图像数据进行压缩存储。因此，数字图像信息压缩编码也就成为多媒体信息处理中的关键技术之一。如何在保证无损的前提下尽可能提高图像的压缩效率，对于与图像有关的应用而言，具有非常重要的意义。

赫夫曼方法是前缀即时码中编码效率最优的编码方法，其对信源的统计特性没有特殊要求，对编码设备的要求也比较简单，综合性能优于香农码和费诺码。但其解码过程需通过码表匹配来实现，因此解码效率低下。一些次优编码方法，如B1码，B2码以及移位码等，虽然编解码效率得到提高，但编码形式固定、单一，对信源的统计特性有特殊要求，压缩效率较低。

发明内容

本发明的目的在于针对现有技术存在的问题提出一种图像数据无损压缩的编码方法，该方法具有灵活性强，算法简单，易于实现，编解码效率高。

为了达到上述目的，本发明采用下述技术方案：

一种图像数据无损压缩的编码方法，其特征在于，该方法具体步骤如下：

（1）、从原始图像逐行读取数据生成图像矩阵D_m×n，从图像矩阵D_m×n中生成横向一阶差分矩阵X_m×n和纵向一阶差分矩阵Y_m×n；

（2）、从横向一阶差分矩阵X_m×n和纵向一阶差分矩阵Y_m×n中生成混合一阶差分矩阵XY_m×n和混合一阶差分矩阵XY_m×n子块的状态二值码流D；

（3）从混合一阶差分矩阵XY_m×n中逐行提取元素符号，0表示正号，1表示负号，生成混合一阶差分矩阵XY_m×n的符号二值码流S和非负混合一阶差分矩阵Z_m×n；

（4）、统计非负混合一阶差分矩阵Z_m×n中各元素出现的个数，生成元素个数统计数组A;

（5）、从元素个数统计数组A中生成元素映射数组T_S，依元素映射数组T_S对非负混合一阶差分矩阵Z_m×n中各元素重新分配数值；

（6）、对元素个数统计数组A分别进行q=0,1,2,3,4次数据合并，建立5组统计数组A₀,A₁,A₂,A₃,A₄和对应的5组组号数组F₀,F₁,F₂,F₃,F₄；

 （7）、依次对5组统计数组A₀,A₁,A₂,A₃,A₄和5组组号数组F₀,F₁,F₂,F₃,F₄，统计编码截断阶数p分别为1,2,3,…,32阶下的编码比特数，选取编码比特数最小时的合并次数q_c和编码截断阶数p_c；

(8）、逐行提取非负混合一阶差分矩阵Z_m×n元素，依次放入数组E中，依步骤（7）选取的2个参数，即合并次数q_c和编码截断阶数p_c，对数组E中各元素进行合并与编码，生成一次压缩编码二值码流T₁；

（9）、统计一次压缩编码二值码流T₁中连续0和连续1的长度，得到一次压缩编码二值码流T₁的长度分布数组L；

（10）、用长度分布数组L的长度商数组Q和余数二值码流R表示长度分布数组L，实现二次编码压缩，生成二次编码二值码流T₂。

本发明的一种图像数据无损压缩的编码方法具有如下特点：

（1）、该方法能根据图像数据的统计特征选取压缩量最大情形下所对应的数据合并次数q与编码截断阶数p，依所选合并次数和编码截断阶数构造一种即时编码，灵活性强，算法简单，易于实现，编码效率高；（2）、该方法的一次压缩编码表的构成简单，对于数值小于编码截断阶数的压缩元素，由编码前缀，即1元即时码表示，对于数值大于等于编码截断阶数的压缩元素，由编码前缀和编码后缀联合表示；（3）、该方法的一次压缩编码表的主要部分为其前缀编码，前缀编码可按位平面层面分解，并依位平面层面摆放，基于图像数据的连续性，这种二值码流的层面摆放方式为后续的二次压缩编码提供可能，两次编码后的整体压缩效率高；（4）、该方法的编码前缀及编码后缀结构统一，解码过程无需匹配，解码效率高。

附图说明

图1是本发明的一种图像数据无损压缩的编码方法的流程图；

图2是生成混合一阶差分矩阵XY_m×n方法示意图；

图3是数组                                                在合并次数q_c和编码截断阶数p_c下的编码表；

图4是序列按位平面层面的分解图。

具体实施方式

下面结合附图和256级灰度的任意图像，对本发明作进一步描述。

如图1所示，本发明的一种图像数据无损压缩的编码方法，其具体步骤如下：

步骤（1）、从原始图像逐行读取数据生成图像矩阵D_m×n，从图像矩阵D_m×n中生成横向一阶差分矩阵X_m×n与纵向一阶差分矩阵Y_m×n，具体如下：

从宽为m，高为n的原始图像中逐行提取图像象素值，将提取所得象素值置入图像矩阵D_m×n中,其中D_m×n=(d_ij) _m×n，

分别计算第i行、第j列处的横向一阶差分值x_ij与纵向一阶差分值y_ij，具体计算公式如下：

      x_ij=d_ij-d_i,j-1   ，i=1,2,…,m,   j=2,3,…,n                       （1）

      y_ij=d_ij-d_i-1,j  ， i=2,3,…,m,   j=1,2,…,n                       （2）

其中，x_ij为横向一阶差分矩阵X_m×n 在(i,j)处的横向一阶差分值，y_ij为纵向一阶差分矩阵Y_m×n 在(i,j)处的纵向一阶差分值，横向一阶差分矩阵X_m×n中第1列差分元素值、纵向一阶差分矩阵Y_m×n中第1行差分元素值的具体计算公式如下：

x_i1=d_i1-d_i-1,1     ，i=2,3,…,m                                    （3）

y_1j=d_1j-d_1,j-1    ，j=2,3,…,n                                   （4）

    横向一阶差分矩阵X_m×n和纵向一阶差分矩阵Y_m×n第1行第1列差分元素值置为0；

步骤（2）、从横向一阶差分矩阵X_m×n和纵向一阶差分矩阵Y_m×n中生成混合一阶差分矩阵XY_m×n和混合一阶差分矩阵XY_m×n子块的状态二值码流D，具体如下：

对横向一阶差分矩阵X_m×n和纵向一阶差分矩阵Y_m×n按4×4大小的子块划分，各得

（m×n）/16个子块，分别计算横向一阶差分矩阵X_m×n和纵向一阶差分矩阵Y_m×n相同位置子块元素绝对值之和，取绝对值之和最小的子块对应的各个元素置入混合一阶差分矩阵XY_m×n相同位置子块处，生成一阶混合差分矩阵XY_m×n=(xy_ij)_m×n，参见附图2，对横向一阶差分矩阵X_m×n和纵向一阶差分矩阵Y_m×n相同位置子块，记，，若，则将横向一阶差分矩阵X_m×n子块数据置入混合一阶差分矩阵XY_m×n相同位置子块处，此时子块的状态标记为0；若，则将纵向一阶差分矩阵Y_m×n子块数据置入混合一阶差分矩阵XY_m×n相同位置子块处，此时子块的状态标记为1，将子块的状态标记0或1依次置入子块的状态二值码流D中；

步骤（3）、从混合一阶差分矩阵XY_m×n中逐行提取元素符号，0表示正号，1表示负号，生成混合一阶差分矩阵XY_m×n的符号二值码流S和非负混合一阶差分矩阵Z_m×n，具体如下：

从混合一阶差分矩阵XY_m×n=(xy_ij)_m×n中逐行提取矩阵的各元素符号，正号元素记为0，负号元素记为1，依次将符号元素0或1置入一阶混合差分矩阵XY_m×n的符号二值码流S，对混合一阶差分矩阵XY_m×n=(xy_ij)_m×n各元素取绝对值，生成非负混合一阶差分矩阵Z_m×n=(|xy_ij|)_m×n；

步骤（4）、统计非负混合一阶差分矩阵Z_m×n中各元素出现的个数，生成元素个数统计数组A，具体如下：

统计非负混合一阶差分矩阵Z_m×n=(|xy_ij|)_m×n中各元素出现的个数，按元素出现次数的大小置入元素个数统计数组A=(n₀,n₁,…,n_e)中，其中n₀≥n₁≥…≥n_e，n₀,n₁,…,n_e分别对应非负混合一阶差分矩阵Z_m×n=(|xy_ij|)_m×n中元素值a₀,a₁,a₂,…,a_e出现的个数, 0≤e≤255，其中|xy_ij|{a₀,a₁,a₂,…,a_e}，表示非负混合一阶差分矩阵Z_m×n中任一点元素值|xy_ij|仅在集合{ a₀,a₁,a₂,…,a_e}中取值；

步骤（5）、从元素个数统计数组A中生成元素映射数组T_S，依元素映射数组T_S对非负混合一阶差分矩阵Z_m×n各元素重新分配数值，具体如下：

依次将元素个数统计数组A=(n₀,n₁, …,n_i,…,n_e)中n_i所对应的非负一阶混合差分矩阵Z_m×n中元素a_i,置入元素映射数组T_S中，生成元素映射数组T_S=(a₀,a₁, …,a_i,…,a_e)，逐行提取非负混合一阶差分矩阵Z_m×n各元素|xy_ij|，|xy_ij|为非负混合一阶差分矩阵Z_m×n中第i行第j列元素，如果|xy_ij|=a_k ，一阶非负混合差分矩阵Z_m×n中第i行第j列元素值|xy_ij|置为k，

其中a_k是映射数组T_S=(a₀,a₁,a₂,…,a_e)中的第k+1个元素，0≤k≤e；

步骤（6）、对步骤（4）所得元素个数统计数组A分别进行q=0,1,2,3,4次数据合并，建立5组统计数组A₀,A₁,A₂,A₃,A₄和对应的5组组号数组F₀,F₁,F₂,F₃,F₄，具体如下：

为论述方便，假定e=255，则

0次合并统计数组A₀=A=(n₀,n₁,…,n₂₅₅)；   

0次合并组号数组F₀=(0,1,2,…,255)；

1次合并统计数组A₁=(n₀+n₁, n₂+n₃…, n₂₅₄+n₂₅₅)=；

1次合并组号数组F₁=(0,1,2,…,127)；

2次合并统计数组A₂=(n₀+n₁+ n₂+n₃,…, n₂₅₂+n₂₅₃+ n₂₅₄+n₂₅₅)=；

2次合并组号数组F₂=(0,1,2,…,63)；

3次合并统计数组A₃=(n₀+n₁+…+n₇,…, n₂₄₈+n₂₄₉+…+n₂₅₅)=；

3次合并组号数组F₃=(0,1,2,…,31)；

4次合并统计数组A₄=(n₀+n₁+…+n₁₅,…, n₂₄₀+n₂₄₁+…+n₂₅₅)=；

4次合并组号数组F₄=(0,1,2,…,15)，

其中，A为步骤（4）所述元素个数统计数组，组号数组F_k中元素a_i经k+1次合并后对应到组号数组F_k+1中元素round[a_i/2]，round为取整函数，0≤k≤3；

步骤（7）、依次对5组统计数组A₀,A₁,A₂,A₃,A₄和5组组号数组F₀,F₁,F₂,F₃,F₄，统计编码截断阶数p分别为1,2,3,…,32阶下的编码比特数，选取编码比特数最小时的合并次数q_c和编码截断阶数p_c，具体如下：

编码截断阶数p为可用1元即时二进制码0,10,110,…,11…10，分别表示元素0,1,2,…,p-1，其中，11…10由p-1个1和1个0组成，大于p-1的元素的二进制码，由p个1的二进制码组成其前缀，由b位二进制码组成其后缀，其中参数b由公式（6）确定，

如果编码截断阶数为p，合并次数为q，对图像矩阵D_m×n编码占用的比特数G为

   （5）

其中， B₀(D)为步骤（2）所述子块的状态二值码流D占用比特数；B₁(S)为步骤（3）所述混合一阶差分矩阵元素的符号二值码流S占用比特数；B₂(T_s)为步骤（5）所述元素映射数组T_s占用比特数，对应的组号元素为，参数b按如下公式确定：

记，

如果0≤f≤1,则b=1；

如果2≤f≤3,则b=2；

如果4≤f≤7,则b=3；

如果8≤f≤15,则b=4；                                              （6）

如果16≤f≤31,则b=5；

如果32≤f≤63,则b=6；

如果64≤f≤127,则b=7；

如果128≤f≤255,则b=8，

对0,1,2,3,4次合并后的5组统计列表A₀,A₁,A₂,A₃,A₄和5组组号数组F₀,F₁,F₂,F₃,F₄，分别统计编码截断阶数为p=1,2, …,32阶下占用的编码比特数，由5种合并，32个编码截断阶数，共计得5×32=160种组合形式，按公式（5）分别计算160种组合的编码占用的比特数G，从160种组合中选取编码占用的比特数G最小时对应的编码截断阶数p=p_c和元素合并次数q=q_c，其中1≤p_c≤32，0≤q_c≤4；

步骤（8）、逐行提取非负混合一阶差分矩阵Z_m×n元素，依次放入数组E中，依步骤（7）选取的2个参数，即合并次数q_c和编码截断阶数p_c，对数组E中各元素进行合并与编码，生成一次压缩编码二值码流T₁,具体如下：

逐行提取矩阵Z_m×n=(|xy_ij|)_m×n元素，依次放入数组E中，E的表达式为

E=(|xy₁₁|,|xy₁₂|,…, |xy_1n|,|xy₂₁|,|xy₂₂|,…, |xy_2n|,…, |xy _m1|,|xy _m2|,…, |xy _mn|)，

 按步骤（7）所选合并次数q_c，对数组E中各元素整除，商置入数组，余数置入数组，中各余数的二进制表示位数为q_c 位，参照附图3，对数组中各元素进行编码，小于p_c的元素0,1,2,…,p_c-1对应的编码为；大于p_c的元素对应的编码为，其中参数b的取值由步骤（7）所述公式（6）确定，

将各元素编码的前缀部分，即1元即时码0,10,110,…,11…10,11…11，依数组中元素顺序进行纵向分解，按位平面层面依次置入一次压缩编码二值码流T₁中，接着在一次压缩编码二值码流T₁中置入后缀部分的b位二进制数，然后在一次压缩编码二值码流T₁中置入余数数组对应的二值码流、步骤（3）所述混合一阶差分矩阵XY_m×n的符号二值码流S和步骤（2）所述混合一阶差分矩阵XY_m×n子块的状态二值码流D，生成一次压缩编码二值码流T₁。

例如某序列为{3,3,2,3,5,4,0,0,4,1,2,1,2,6,2,1,1,1,2,1}，假定数据合并次数为0，编码截断阶数为5，参照附图4，前缀部分分解为5层位平面，1层位平面为11111100111111111111，2层位平面为11111110101110001，3层位平面110111100100，4层位平面为000111，5层位平面1001，按位平面层面的摆放结果如下：11111100111111111111,11111110101110001,  110111100100, 000111, 1001；

步骤（9）、统计一次压缩编码二值码流T₁中连续0和连续1的长度，得到一次压缩编码二值码流T₁的长度分布数组L，具体如下：

统计步骤（8）一次压缩编码二值码流T₁中0段和1段的长度，得到长度分布数组L=(l₁,l₂,l₃,…,l_r)，

如一次压缩编码二值码流T₁=(00010000111110011100001111111111000001010111),则长度分布数组L=(3,1,4,5,4,10,5,1,1,1,1,3)；

步骤（10）、用长度分布数组L的长度商数组Q和余数二值码流R表示长度分布数组L，实现二次编码压缩，生成二次编码二值码流T₂,具体如下：

对长度分布数组L=(l₁,l₂,…,l_r)中各元素按公式（7）计算，得到长度商数组Q和余数二值码流R，其中

Q=round((l₁+1)/2,(l₂+1)/2,…,(l_r+1)/2)                          （7）

round表示取整函数，余数置入余数二值码流R=(b₁,b₂,…, b_i,…,b_r)中，其中，当(l_i+1)/2为偶数时，b_i为0，当(l_i+1)/2为奇数时，b_i为1。

长度商数组Q中元素为1时，编码为0或1，如果该原始长度由0组成，则编码为0，如果该原始长度由1组成，则编码为1；长度商数组Q中元素为2时，编码为00或11，如果该原始长度由0组成，则编码为00，如果该原始长度由1组成，则编码为11。如某二值码流串0111111000111111111111，其长度分布数组L=(1,6,3,12)，长度商数组Q编码为011100111111，余数二值码流R为0101。

将长度商数组Q的二进制编码与余数二值码流R组合后，生成二次编码二值码流T₂。

为了验证使用本发明的方法压缩效果，通过对Lena、Columbia等100多幅图像进行压缩测试，验证了本发明的方法压缩效果，实验结果得出，对于70%以上图像而言，经二次编码后，图像每象素的平均比特数低于步骤（2）所述的混合一阶差分矩阵XY_m×n所对应的信源数据的香农熵。

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