图像压缩技术
|
摘要
随着数字化时代的发展，需要存储、传输和处理的信息的数量成指数级地增加。图像作为数字信息的重要组成部分，是信息交流的重要载体，也是蕴含信息量最大的媒体。因此图像压缩作为图像处理的一个重要组成部分，一直是人们研究的一个热点。
本文的研究背景是二代身份证中的静态图像压缩，研究方向为把尺寸为的24位的真彩图(身份证照片)压缩到1k的存储空间里。面对几百倍的压缩，为了能够得到更好的压缩效果，在原有的SPIHT量化编码方法基础上，本文提出了最优截断方法和感兴趣区域编码方法。这两种方法分别从两个不同角度对原有的SPIHT量化编码方法进行改进，并且都得到了令人满意的效果。
SPIHT算法是Said 和Pearlman根据Shapiro 的EZW算法的基本思想提出的一种基于分层树集合分割排序的编码方法，是公认的编码效率最高的静止图像压缩编码方法之一。它采用了有效的空间方向树结构和比特平面编码方法，不仅能获得很高的压缩编码效率，而且产生的码流是嵌入式的，支持解码器的多码率解码，有利于图像的渐近传输。虽然SPIHT量化编码方法能够对码流的任意位置进行截断来实现对图像的压缩，但是却不能保证所截断的位置是在当前的比特率下最优的。
因此本文提出了最优截断方法来补偿这个不足。该方法先对图像进行分块，构造每个单位块的最优曲线，在对图像进行截断的时候，根据整个图像的最优曲线的截断点来寻找各个单位块最优曲线的相应截断点，从而实现对整个图像的最优截断。
图像的比特率和失真程度的相关性表现为图像存在唯一的一条最优比特率(Rate)和失真(Distortion)曲线(如图 1)。任意算法都是无限地逼近这条最优曲线。最优曲线反映的是在不同比特率条件下，图像的最小失真情况。
图 1 最优曲线
最优截断方法就是根据图像存在一条最优曲线这样的事实提出的。在给定比特率的限制下对图像进行压缩的数学模型表示为：
(1)
当把图像分为块时，
，
这里，表示整个图像的失真值；由于比特率和比特数是成正比的，表示整个图像的所占用的比特数；、分别表示第块的失真值和比特数。
我们发现这个公式实际上是拉格朗日乘数法的表达式。约束条件为各个块比特数之和小于或等于给定的(在这里)，表达式为：
(2)
形象地说，最优截断方法是根据给定的限制条件在最优的曲线上找到一个点(该点横坐标表示的是当前的比特率，纵坐标表示的是图像的失真程度)，在该点处做整个图像最优曲线的切线，计算出切线的斜率，通过得到的斜率在每个单位块的最优曲线上找到相应的位置(切点处曲线的斜率值为)进行截断，实现对整个图像的最优截断。
最优截断方法的实现过程大致表示为：
对图像进行小波变换；
对图像(图像的小波系数)进行分块，分块原理为在最高频子带上采用尺寸最大的单位块，次一级高频子带采用的单位块尺寸为最大单位块尺寸的四分之一，以此类推下去；
定义失真公式如下：
(3)
其中，表示单位块在截断点为时对图像所贡献的失真量，表示小波基函数对子带的模，表示压缩前第块的第个位置的原图像的特征值，表示截断点选取在位置时第块的第个位置的重构值，的取值范围为，可表示为：
(4)
这里，表示的邻域，表示的大小(可以理解为邻域内像素的个数)。
根据给定的限制条件，通过迭代的方法找寻各个单位块的截断位对图像进行最优截断。
最优截断方法对真彩图的实验效果图(图像的压缩比为36倍)为：
a 原 图 b 压缩效果图
R_PSNR = 33.478783
G_PSNR = 34.478783
B_PSNR = 29.311990
图2 最优截断方法实验效果图
虽然最优截断方法可以使得我们根据图像的最优曲线
合理地分配空间给各个单位块，但是有时为了某些特殊的需求，图像的不同区域有着不同的重要性。在这种情况下，我们就不能对所有的小波系数“一视同仁”，对重要程度高的图像区域应给予更多重视。这时就不适合采用最优截断方法，而需要采用另一种量化编码方法—感兴趣区域编码。
所谓在感兴趣区域编码是指在压缩过程中，在原图像中人为地指定一块区域(这个区域可以是规则图形也可以是不规则图形)，使得压缩后该块区域较图像中的其它区域有更高的图像压缩质量。进行感兴趣区域编码需要考虑两个问题，一是如何确定感兴趣区域，二是采用何种感兴趣区域编码方法。
前人确定感兴趣区域方法主要有两种，规则感兴趣区域的选取方法和基于边缘检测的感兴趣区域选取方法。规则感兴趣区域的选取方法是指选取矩形或椭圆形或是两者的组合图形作为感兴趣区域，这样使得很多实际上属于非感兴趣区域的系数归入了感兴趣区域，本该低精度压缩的部分被高精度压缩，占用了宝贵的存储空间。基于边缘检测的感兴趣区域选取方法虽然可以精确区分感兴趣区域和非感兴趣区域，但是由于边缘检测技术受?
Following the development of digital age， the information which need to save， transport， transact is increasing exponential. As an important component of information， image which includes the most amount of information is the carrier of the information communicating. As one of the most components of Image Processing ， Image Compression is always the research hotspot.
The research background of this paper is the still image compression of the Second Generation ID card， and the aim of research is that saving RGB image in the 1024 bits. Under this condition， this paper put forward the optimizing truncation method and ROI coding method for the better compression performance. They both improve the SPIHT algorithm from the different direction and achieve state-of-the-art compression performance.
SPIHT algorithm which Said and Pearlman put forward was based on Shapiro’s EZW algorithm is one of the coding methods of Set Partitioning in Hierarchical Trees， and is one of the most efficient methods of still image compression coding. This algorithm which uses the Spatial Orientation Tree Structure and bit-plane coding does not only achieve the better compression coding efficiency， but also it outputs the embedded bit-stream and supports the different multi-rate decoder and makes for the progressive transmission of the image. Though the SPIHT algorithm can truncate the bit-stream at any point， this method can’t be sure that the compression performance is the best quality at the current rate.
So this paper put forward the optimizing truncation method for compensating this shortage. This method can be described that dividing the whole image into some blocks， and figuring the optimizing curves of the each block. When truncating the bit-stream， we can search the truncation point of every block on the optimizing curve of every block based on the optimizing curve of the whole image， so achieve state-of-the-art optimizing truncation to the whole image.
The relation of rate and distortion can be described that the image have the one and only optimizing curve (Fig 1). Any algorithm is approaching this optimizing curve limitlessly. The optimizing curve can show the minimum distortion performance at the different constrained rate.
Fig 1 The optimizing curve
The optimizing truncation method is put forward based on the fact of that the image has the one and only optimizing curve. At the constrained rate， the method’s mathematics model is as follows：
(1)
while the image is divided into blocks，
，
Here， denotes the distortion of the whole image; denotes the bits of the whole image because the rate and the bits of the image is direct ratio; and denote respectively the distortion and bits of the th block.
It does well know that this equation is in fact the Lagrangian function. And the constrained condition is that the sum of all the block’s bits subject to a constraint ()， the equation is as follows：
(2)
More generally， the optimizing truncation method is to find the
point whose value of x-axis denotes the current rate and value of y-axis denotes the distortion of the image on the optimizing curve， figure the tangent line on this point and computer the slope value of the tangent line under the constraint condition. We can search the corresponding truncating point of each block by the slope value of those points being equal to and achieve the optimizing truncation to the image.
The optimizing truncation method can be performed as follows：
Wavelet transforming to the image;
Dividing the image to some blocks， the principle of dividing is described that we define the maximum size of the block at the highest resolution level， define the quarter of the maximum size at the next resolution level， and so on;
The distortion equation is as follows：
(3)
Here， denotes the ith block’s distortion with truncation point of ， denotes
本文的研究背景是二代身份证中的静态图像压缩，研究方向为把尺寸为的24位的真彩图(身份证照片)压缩到1k的存储空间里。面对几百倍的压缩，为了能够得到更好的压缩效果，在原有的SPIHT量化编码方法基础上，本文提出了最优截断方法和感兴趣区域编码方法。这两种方法分别从两个不同角度对原有的SPIHT量化编码方法进行改进，并且都得到了令人满意的效果。
SPIHT算法是Said 和Pearlman根据Shapiro 的EZW算法的基本思想提出的一种基于分层树集合分割排序的编码方法，是公认的编码效率最高的静止图像压缩编码方法之一。它采用了有效的空间方向树结构和比特平面编码方法，不仅能获得很高的压缩编码效率，而且产生的码流是嵌入式的，支持解码器的多码率解码，有利于图像的渐近传输。虽然SPIHT量化编码方法能够对码流的任意位置进行截断来实现对图像的压缩，但是却不能保证所截断的位置是在当前的比特率下最优的。
因此本文提出了最优截断方法来补偿这个不足。该方法先对图像进行分块，构造每个单位块的最优曲线，在对图像进行截断的时候，根据整个图像的最优曲线的截断点来寻找各个单位块最优曲线的相应截断点，从而实现对整个图像的最优截断。
图像的比特率和失真程度的相关性表现为图像存在唯一的一条最优比特率(Rate)和失真(Distortion)曲线(如图 1)。任意算法都是无限地逼近这条最优曲线。最优曲线反映的是在不同比特率条件下，图像的最小失真情况。
图 1 最优曲线
最优截断方法就是根据图像存在一条最优曲线这样的事实提出的。在给定比特率的限制下对图像进行压缩的数学模型表示为：
(1)
当把图像分为块时，
，
这里，表示整个图像的失真值；由于比特率和比特数是成正比的，表示整个图像的所占用的比特数；、分别表示第块的失真值和比特数。
我们发现这个公式实际上是拉格朗日乘数法的表达式。约束条件为各个块比特数之和小于或等于给定的(在这里)，表达式为：
(2)
形象地说，最优截断方法是根据给定的限制条件在最优的曲线上找到一个点(该点横坐标表示的是当前的比特率，纵坐标表示的是图像的失真程度)，在该点处做整个图像最优曲线的切线，计算出切线的斜率，通过得到的斜率在每个单位块的最优曲线上找到相应的位置(切点处曲线的斜率值为)进行截断，实现对整个图像的最优截断。
最优截断方法的实现过程大致表示为：
对图像进行小波变换；
对图像(图像的小波系数)进行分块，分块原理为在最高频子带上采用尺寸最大的单位块，次一级高频子带采用的单位块尺寸为最大单位块尺寸的四分之一，以此类推下去；
定义失真公式如下：
(3)
其中，表示单位块在截断点为时对图像所贡献的失真量，表示小波基函数对子带的模，表示压缩前第块的第个位置的原图像的特征值，表示截断点选取在位置时第块的第个位置的重构值，的取值范围为，可表示为：
(4)
这里，表示的邻域，表示的大小(可以理解为邻域内像素的个数)。
根据给定的限制条件，通过迭代的方法找寻各个单位块的截断位对图像进行最优截断。
最优截断方法对真彩图的实验效果图(图像的压缩比为36倍)为：
a 原 图 b 压缩效果图
R_PSNR = 33.478783
G_PSNR = 34.478783
B_PSNR = 29.311990
图2 最优截断方法实验效果图
虽然最优截断方法可以使得我们根据图像的最优曲线
合理地分配空间给各个单位块，但是有时为了某些特殊的需求，图像的不同区域有着不同的重要性。在这种情况下，我们就不能对所有的小波系数“一视同仁”，对重要程度高的图像区域应给予更多重视。这时就不适合采用最优截断方法，而需要采用另一种量化编码方法—感兴趣区域编码。
所谓在感兴趣区域编码是指在压缩过程中，在原图像中人为地指定一块区域(这个区域可以是规则图形也可以是不规则图形)，使得压缩后该块区域较图像中的其它区域有更高的图像压缩质量。进行感兴趣区域编码需要考虑两个问题，一是如何确定感兴趣区域，二是采用何种感兴趣区域编码方法。
前人确定感兴趣区域方法主要有两种，规则感兴趣区域的选取方法和基于边缘检测的感兴趣区域选取方法。规则感兴趣区域的选取方法是指选取矩形或椭圆形或是两者的组合图形作为感兴趣区域，这样使得很多实际上属于非感兴趣区域的系数归入了感兴趣区域，本该低精度压缩的部分被高精度压缩，占用了宝贵的存储空间。基于边缘检测的感兴趣区域选取方法虽然可以精确区分感兴趣区域和非感兴趣区域，但是由于边缘检测技术受?
Following the development of digital age， the information which need to save， transport， transact is increasing exponential. As an important component of information， image which includes the most amount of information is the carrier of the information communicating. As one of the most components of Image Processing ， Image Compression is always the research hotspot.
The research background of this paper is the still image compression of the Second Generation ID card， and the aim of research is that saving RGB image in the 1024 bits. Under this condition， this paper put forward the optimizing truncation method and ROI coding method for the better compression performance. They both improve the SPIHT algorithm from the different direction and achieve state-of-the-art compression performance.
SPIHT algorithm which Said and Pearlman put forward was based on Shapiro’s EZW algorithm is one of the coding methods of Set Partitioning in Hierarchical Trees， and is one of the most efficient methods of still image compression coding. This algorithm which uses the Spatial Orientation Tree Structure and bit-plane coding does not only achieve the better compression coding efficiency， but also it outputs the embedded bit-stream and supports the different multi-rate decoder and makes for the progressive transmission of the image. Though the SPIHT algorithm can truncate the bit-stream at any point， this method can’t be sure that the compression performance is the best quality at the current rate.
So this paper put forward the optimizing truncation method for compensating this shortage. This method can be described that dividing the whole image into some blocks， and figuring the optimizing curves of the each block. When truncating the bit-stream， we can search the truncation point of every block on the optimizing curve of every block based on the optimizing curve of the whole image， so achieve state-of-the-art optimizing truncation to the whole image.
The relation of rate and distortion can be described that the image have the one and only optimizing curve (Fig 1). Any algorithm is approaching this optimizing curve limitlessly. The optimizing curve can show the minimum distortion performance at the different constrained rate.
Fig 1 The optimizing curve
The optimizing truncation method is put forward based on the fact of that the image has the one and only optimizing curve. At the constrained rate， the method’s mathematics model is as follows：
(1)
while the image is divided into blocks，
，
Here， denotes the distortion of the whole image; denotes the bits of the whole image because the rate and the bits of the image is direct ratio; and denote respectively the distortion and bits of the th block.
It does well know that this equation is in fact the Lagrangian function. And the constrained condition is that the sum of all the block’s bits subject to a constraint ()， the equation is as follows：
(2)
More generally， the optimizing truncation method is to find the
point whose value of x-axis denotes the current rate and value of y-axis denotes the distortion of the image on the optimizing curve， figure the tangent line on this point and computer the slope value of the tangent line under the constraint condition. We can search the corresponding truncating point of each block by the slope value of those points being equal to and achieve the optimizing truncation to the image.
The optimizing truncation method can be performed as follows：
Wavelet transforming to the image;
Dividing the image to some blocks， the principle of dividing is described that we define the maximum size of the block at the highest resolution level， define the quarter of the maximum size at the next resolution level， and so on;
The distortion equation is as follows：
(3)
Here， denotes the ith block’s distortion with truncation point of ， denotes
引文
黄贤武，王加俊，李家华，《数字图像处理与压缩编码技术》，电子科技大学出版社。
David Taubman，“High Performance Scalable Image Compression with EBCOT”，IEEE Transactions on Image Processing，Vol.9，No.7， pp.1158-1170，July 2000。
程正兴，《小波分析算法与应用》，西安交通大学。
Robert M.Gray， David L.Neuhoff，“Quantization”，IEEE Transactions on Information Theory， Vol. 44， No.6， October 1998。
Editor MARTIN BILIEK， Coeditors CHARILAOS CHRISTOPOULS， and Eric MAJANI， “JPEG 2000 Part 1 Final Draft International Standard”， ISO/IEC JTC1/SC29 WGI N1646R， JPEG 200016 March 2000。
张益贞，刘滔，《Visual C++实现MPEG/JPEG编解码技术》，人民邮电出版社。
章毓晋，《图像工程-图像处理和分析》，清华大学出版社。
张琳，“数字图像编码方法研究”，吉林大学硕士论文，2003。
， Diego Santa-Cruz and Touradj Ebrahimi， “New approach to JPEG 2000 compliant Region Of Interest coding”， Signal Processing Laboratory – Swiss Federal Institute Of Technology， CH-1015， Lausanne， Switzerland， SPIE’s
46th annual meeting， Applications of Digital Image Processing XXIV， vol.4472， pp.267-275， San Diego， CA， USA， Jul.29-Aug.3， 2001。
S.Grace Chang，Bin Yu，Martin Vetterli，“Adaptive Wavelet Thresholding for Image Denoising and Compression”，IEEE TRANSACTIONS ON IMAGE PROCESSING，VOL.9，NO.9，SEPTEMBER 2000.
A.Mazzarri and R.Leonardi，“Perceptual embedded image coding using wavelet transforms”， IEEE Int. Conf. Image Processing，vol.1，1995， pp，586-589.
“Quality Improvement Using Contrast Sensitivity Filtering”， ISO/IEC JTC1/SC29/WG1 N1306， June 1999.
A.B. Watson， “DCT quantization matrices visually optimized for individual images”， Proc.SPIE， vol. 1913， pp.202-216， 1993.
丁贵广，郭宝龙，“静止图像的分级压缩算法”，西安电子科技大学机电工程学院.
程正兴，张玲玲，“多小波分析与应用”，工程数学学报，2001年2月，第18卷，第1期.
黄卓君，马争鸣，“多小波图象变换的统计分析”，中国图象图形学报，2001年12月，第6(A)卷，第12期.
黄卓君，马争鸣，“多小波图象编码”，中国图象图形学报，2000年4月，第5(A)卷，第4期.
[美]崔锦泰著，程正兴译，《小波分析导论》，西安交通大学出版社，1995.
王向阳， “关于图像压缩编码算法研究的综述”，烟台师范
学院学报(自然科学版)，2001，17(4)，pp288-295.
贾志科，崔慧娟，唐昆，“改进的SPIHT图像压缩编码方法”，清华大学学报(自然科学版)，2001，Vol.41，No.7.
A.Said， W.Pearlman，“A new， fast and efficient image codec based on set partitioning in hierarchical trees”，IEEE Trans. Circuits Syst. Video Technol.， Vol.6， pp.243-250， June 1996.
J.M.Shapiron，“An embedded hierarchical image coder using zerotrees of wavelet coefficients”，in IEEE Data Compression Conf.， Snowbird， UT， 1993， pp.214-223.
李洪刚，王桥，吴乐南，“改进的SPIHT算法”，电子与信息学报，2002年4月，第24卷，第4期，pp.445-449.
郭武，梅丽，罗建书，“一种基于SPIHT的ROT图像编码”，中国空间科学技术，2003年2月，第1期，pp.61-65.
杨旭东，王万良，“基于改进的MSE 准则的小波图像压缩”，计算机辅助设计与图形学学报，2003年4月，第15卷，第4期，pp.402-409.
David Taubman，“High Performance Scalable Image Compression with EBCOT”，IEEE Transactions on Image Processing，Vol.9，No.7， pp.1158-1170，July 2000。
程正兴，《小波分析算法与应用》，西安交通大学。
Robert M.Gray， David L.Neuhoff，“Quantization”，IEEE Transactions on Information Theory， Vol. 44， No.6， October 1998。
Editor MARTIN BILIEK， Coeditors CHARILAOS CHRISTOPOULS， and Eric MAJANI， “JPEG 2000 Part 1 Final Draft International Standard”， ISO/IEC JTC1/SC29 WGI N1646R， JPEG 200016 March 2000。
张益贞，刘滔，《Visual C++实现MPEG/JPEG编解码技术》，人民邮电出版社。
章毓晋，《图像工程-图像处理和分析》，清华大学出版社。
张琳，“数字图像编码方法研究”，吉林大学硕士论文，2003。
， Diego Santa-Cruz and Touradj Ebrahimi， “New approach to JPEG 2000 compliant Region Of Interest coding”， Signal Processing Laboratory – Swiss Federal Institute Of Technology， CH-1015， Lausanne， Switzerland， SPIE’s
46th annual meeting， Applications of Digital Image Processing XXIV， vol.4472， pp.267-275， San Diego， CA， USA， Jul.29-Aug.3， 2001。
S.Grace Chang，Bin Yu，Martin Vetterli，“Adaptive Wavelet Thresholding for Image Denoising and Compression”，IEEE TRANSACTIONS ON IMAGE PROCESSING，VOL.9，NO.9，SEPTEMBER 2000.
A.Mazzarri and R.Leonardi，“Perceptual embedded image coding using wavelet transforms”， IEEE Int. Conf. Image Processing，vol.1，1995， pp，586-589.
“Quality Improvement Using Contrast Sensitivity Filtering”， ISO/IEC JTC1/SC29/WG1 N1306， June 1999.
A.B. Watson， “DCT quantization matrices visually optimized for individual images”， Proc.SPIE， vol. 1913， pp.202-216， 1993.
丁贵广，郭宝龙，“静止图像的分级压缩算法”，西安电子科技大学机电工程学院.
程正兴，张玲玲，“多小波分析与应用”，工程数学学报，2001年2月，第18卷，第1期.
黄卓君，马争鸣，“多小波图象变换的统计分析”，中国图象图形学报，2001年12月，第6(A)卷，第12期.
黄卓君，马争鸣，“多小波图象编码”，中国图象图形学报，2000年4月，第5(A)卷，第4期.
[美]崔锦泰著，程正兴译，《小波分析导论》，西安交通大学出版社，1995.
王向阳， “关于图像压缩编码算法研究的综述”，烟台师范
学院学报(自然科学版)，2001，17(4)，pp288-295.
贾志科，崔慧娟，唐昆，“改进的SPIHT图像压缩编码方法”，清华大学学报(自然科学版)，2001，Vol.41，No.7.
A.Said， W.Pearlman，“A new， fast and efficient image codec based on set partitioning in hierarchical trees”，IEEE Trans. Circuits Syst. Video Technol.， Vol.6， pp.243-250， June 1996.
J.M.Shapiron，“An embedded hierarchical image coder using zerotrees of wavelet coefficients”，in IEEE Data Compression Conf.， Snowbird， UT， 1993， pp.214-223.
李洪刚，王桥，吴乐南，“改进的SPIHT算法”，电子与信息学报，2002年4月，第24卷，第4期，pp.445-449.
郭武，梅丽，罗建书，“一种基于SPIHT的ROT图像编码”，中国空间科学技术，2003年2月，第1期，pp.61-65.
杨旭东，王万良，“基于改进的MSE 准则的小波图像压缩”，计算机辅助设计与图形学学报，2003年4月，第15卷，第4期，pp.402-409.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |