两种基于对象的嵌入式小波图像编码算法比较分析

摘 要:为进一步研究现有基于对象的图像压缩技术,介绍两种基于对象的嵌入式小波图像编码算法――基于对象的集合分裂嵌入块(Object-Based Set Partitioned Embedded bloCK,OB-SPECK)编码算法和基于k-d树的二元集合分裂(Binary Set Splitting with k-d trees,BISK)编码算法,并进行比较分析. 结果表明两种算法在集合分裂方案､对透明因数的处理方法及算法复杂度上有不同之处. 在Matlab中进行的仿真实验表明,在对任意形状对象进行编码时,BISK编码算法在算法性能和图像压缩质量上较OB-SPECK编码算法更优.

关键词:图像压缩; 嵌入式小波图像编码; 集合分裂嵌入块编码; 二元集合分裂 编码

中图分类号:TP391.41

文献标志码: A

Comparison and analysis on two kinds of object-based embedded wavelet image coding algorithms

CHEN Sijia 1,2 ,SU Hongqi2,MA Shan3

(1. Dept. of Computer Foundation Studies,Shandong Institute of Business & Tech.,Yantai Shandong 264005,China;

2. Mechanical Electronics & Info. Eng.,China Univ. of Mining & Tech.,Beijing 100083,China;

3. Software Dept.,Yantai Huadong Soft-Tech. Co.,Ltd.,Yantai Shandong 264000,China)

Abstract:To further study the existing object-based image compression technique,Object-Based Set Partitioned Embedded bloCK(OB-SPECK) coding and Binary Set Splitting with k-d trees(BISK) coding are introduced,which are object-based embedded wavelet image coding algorithms. The two algorithms are compared and the results indicate that there are differences on set partitioned scheme,the methods on processing transparent areas and algorithm complexity between the two algorithms. The simulative experiment is done by Matlab,and it is shown that BISK has higher performance and better image compression quality than OB-SPECK.

Key words:image compression; embedded wavelet image coding; set partitioned embedded block coding; binary set splitting coding

0 引 言

随着信息技术的发展,人们的应用需求发生变化,对多媒体信息的应用要求由浏览型转向基于内容的访问和操作型.如何对图像数据实现基于内容的压缩编码[1],以支持基于内容的交互性,是多媒体数据压缩技术研究面临的新挑战.针对基于内容的图像压缩思想,人们在传统图像压缩编码技术的基础之上提出基于内容的压缩方法.要实现基于对象或区域的编码,需要通过对象(区域)分割和跟踪等方法将基于像素的表征方式转换为基于对象的表征方式.基于对象(区域)的图像编码方法中需要解决的关键问题包括:(1)对象(区域)的分割与提取;(2)对象(区域)的形状信息编码所采取的方法;(3)对象(区域)的纹理和颜色信息编码所采取的方法;(4)用以上几部分合成整体系统时所采取的方法.

通常,处理任意形状图像对象的方法是将位于对象之内的像素看作是“不透明”的,而将那些在对象之外的像素看作是“透明”的,并且仅在绑定的边框中对不透明区域进行处理以适应矩形框编码器.因此,在嵌入式小波编码方法中,人们仅对图像中的不透明区域采用适形离散小波变换[2].

文献[3,4]中提到两种对任意形状对象编码的算法:基于对象的集合分裂嵌入块(Object-Based Set Partitioned Embedded bloCK,OB-SPECK)编码算法和基于k-d树的二维集合分裂(Binary Set Splitting with k-d trees,BISK)[5]编码算法.其中,OB-SPECK编码算法是集合分裂嵌入块(Set Partitioned Embedded bloCK,SPECK)[6]编码算法的扩展,是针对任意形状对象的编码算法;而BISK是另一种嵌入式小波编码,是在SPECK编码算法及其扩展方法 OB-SPECK 编码算法基础上提出的改进方法,与SPECK编码算法十分相似,特别适合对任意形状的图像进行编码.因此,简要介绍这两种算法的基本原理,并对其进行比较分析.

1 OB-SPECK编码算法

OB-SPECK编码算法是在SPECK编码算法基础之上扩展而来,因此首先简要介绍SPECK编码算法的基本原理.

1.1 SPECK编码算法基本原理

假设对1幅图像进行3级小波分解,形成按分解级数定义的分级金字塔结构,见图1,图中箭头指出各子带的重要性排序.

SPECK编码算法的编码思想是利用同一子带中不重要因数的相关性,采用以下定义的块结构进行重要图的排序.它对重要集合的分裂规则是四叉树分裂和倍频带分裂.下面给出算法中所用到的定义和符号.

(1)块:相应小波分解的每个子带定义1个相应的块.块可以只包含单个元素,如8×8因数矩阵经过3级分解后对应的LL3,HL3,LH3和HH3都只包含1个元素.一般1个块中包含2 2N (N=0,1,2,…,n)个元素,其中,n-1是小波分解的层数.

(2)集合S:放置待处理的块,用最低频子带因数初始化(如3级分解中的LL3).

(3)集合I:放置除S 之外的剩余块集合,I= X-S,X是所有块的集合.

(4)LIS:不重要因数集合列表,用最低频子带因数初始化(如3级分解中的LL3).

(5)LSP:重要因数集合列表,存放重要因数以便进一步量化,初始化为空表.

下面介绍算法排序过程.

首先给出因数集合的重要性定义如下:

Sn(T)={1,如果2n≤max(i,j)∈T{|C(i,j)|}