注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

BCB-DG's Blog

...

 
 
 

日志

 
 

DCT在彩色图像有损RLE压缩中的应用  

2008-11-25 13:59:02|  分类: Delphi |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

作者:唐俊
                摘要:游程编码(RLE)压缩方法原理简单且易于实现,对于相邻数据相似性很大的数据进行压缩,压缩效果特别明显。在众多的压缩算法中,RLE压缩属于无损压缩,能够对原始数据进行完整的还原。 DCT是一种对数据进行变换的技术,通过DCT变换将数据中的信息进行集中,然后通过对那些含有很少信息的大量数据进行量化,将他们量化成可供RLE压缩的信息高度集中的数据。将DCT和RLE相结合能够实现彩色图像的有损压缩,并且能够在可以接受的损失范围内,获取比较好的压缩比。

  关键字:彩色图像;RLE;DCT;有损压缩

  1、引言

  数字信号相对模拟信号有着很多优点,如可以有效地防止信号干扰、数据的复制不会造成损失等。但是数字信号也有缺陷,由于其无法很好的表示自然界的连续信号,而需要对模拟信号进行采样并量化才能保存,并且这个过程是由损失的。

  用数字信号来存储图像数据需要庞大的存储空间,图像在计算机中是以位图的形式存储的,一副800乘600的24位真彩色图像,需要480,000个像素来表示,因而总共需要1.37M的存储空间,而动态影像对存储容量的要求更加巨大。因此,数据压缩技术对于数字图像的存储和传输有着重大的意义。

  2、RLE压缩

  RLE称为游程编码,顾名思义,游程编码对它需要编码的数据从头到尾进行读取,碰到前后相连的相等数据的时候,将该数据的值和出现的次数进行存储,连续相同的数据越多,则压缩的效果越明显。

  对于图像文件中的各个像素数据,由于图像颜色的梯度变化,相邻像素的颜色值相同的可能性极大,RLE压缩方法的原理就是将一扫描行中颜色值相同的相邻像素,用一个计数值和那些像素的颜色值来代替。可以看出RLE 是一种无失真压缩算法,如果给定形成这个字符串的字符、长度和串的位置,就能恢复出原始的数据。算法简单方便,具有较好的时间复杂度,已经广泛地使用在PCX、GEM、TIFF、MacPaint等图像文件格式中,另外,RLE压缩算法还是BMP、TGA等图像格式的可选数据处理方式。

  最适合用RLE进行压缩的是黑白图片,即整个图片上除了黑色就是白色,没有任何的灰度,考虑如下的图像:

  该图片有8行、8列,共64个像素,如果白色区域用“1”表示,黑色区域用“0”表示,则整个图像的数据表示为:1,1,1,1,1,1,1,1;0,0,0,0,0,0,0,1;1,1,1,0,1,1,1,1;1,1,1,0,1,1,1,1;1,0,0,0,0,0,1,1;1,1,1,0,1,1,1,1;1,1,1,0,1,1,0,1;0,0,0,0,0,0,0,0。

  假如每一个像素用一个字节来表示的话,将连续的“1”或者“0”只保留一个,并在前面加上数量的话,则可以表示成:8,1,7,0,4,1,0,7,1,0,5,1,5,0,5,1,0,7,1,0,2,1,0,1,8,0。这样一来,原来需要64个数字才能表示的图形现在用26个数字就能表示出来,节约了60%的存储空间。

3、利用RLE对真彩色图像压缩中存在的问题

  RLE算法很适合那种有大片相同颜色的图片中,而在现实生活中的照片都是真彩色的,相邻的像素之间虽然有颜色的相近,但是却很少找到颜色完全相同的大量相邻像素,真彩色图像的这种性质让RLE压缩算法无法对其进行有效的压缩。

  在图二中,由于存在着大量的相同颜色的色块,通过颜色直方图可以明显的看到,整幅图的颜色都集中在四个区域,分别是黑、黄、粉红、白四种颜色,其他的颜色很少。因此图二很适合采用RLE进行压缩。

  而对于图三来说,由于是真彩色的照片,图像中的相邻像素的颜色虽然很接近,但是却不是完全一样,通过颜色直方图可以清楚的看到,所有的颜色分布比图二要均匀的多。如果直接采用RLE进行压缩的话,无法达到比较好的压缩效果。

  4、图像的二维变换

  图像变换的目的是将一副图像的像素(相关的)变换到一种去相关的表示,以达到压缩的目的。去相关的最主要目的就是将数据中的信息通过某种变化进行集中,然后将那些只含少量信息的数据进行量化,得到大量的相同数据,以便利用RLE等算法进行压缩。

  考虑我们有如下4×4的矩阵数据:

  将该矩阵与变换矩阵W相乘,可以得到新的矩阵C’。

  矩阵C’和D相比,C’的第一行的数据要明显的变大,其他的数据大部分都变小,能量在朝第一行集中。如果在此基础上将矩阵C’继续与变换矩阵W相乘,则可以将能量朝矩阵的左上角转移。

  经过上面两步的运算,能量朝左上角集中,降低了矩阵中数据的相关性。在此基础上对矩阵C进行量化后,便可以形成利于RLE压缩的数据。而由于将能量转移到左上角,所以对于其他的数据进行量化处理,并不会造成比较大的信息损失。

  5、DCT的原理

  离散余弦变换,简称DCT ,是一种实数域变换,其变换核为余弦函数,计算速度快。DCT 除了具有一般的正交变换性质外,它的变换阵的基向量能很好地描述图像信号的相关特征。因此,图像信号的变换中,DCT 变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中,都把DCT 作为其中的一个基本处理模块。而且对于具有一阶马尔柯夫过程的随机信号,DCT十分接近于Karhunen - Loeve 变换,也就是说它是一种最佳近似变换。

  DCT变换在图像压缩中有很多应用,它是JPEG、MPEG等数据压缩标准的重要数学基础。在JPEG压缩算法中,先将输入图像划分为8 ×8 或16 ×16的图像块,对每个图像块作DCT 变换,然后舍弃高频的系数,并对余下的系数进行量化以进一步减少数据量;最后使用无失真编码来完成压缩任务。解压缩时首先对每个图像块做DCT 反变换,然后将图像拼接成一副完整的图像。

  6、DCT 变换的定义

  由于图像是二维相关的,因此DCT变换在图像处理中的应用通常也是二维的。二维DCT变换的公式定义为:

其中0≤i,j≤n﹣1。图像被分成n×n个像素块 ,通常取n=8。n 并不是越大越好,因为随着n的增大,数据的计算量成指数增加,所以在给n取值的时候需要根据计算机的性能进行权衡。

  通过上面的公式进行了DCT变换之后,每个n×n的像素块的能量都往左上角集中了,如果需要进行有算压缩,则可以将变换后产生的矩阵进行量化,量化的越厉害则能够获得最大的压缩比,当然这一切都是以图像质量的损失来换取的。

  将变换后的数据进行还原成为逆变换,上面的公式的逆变换公式IDCT为:

  7、VB对二维DCT变换的实现

  真彩色图像以24位来表示一个像素的颜色,其中红、绿、蓝分别占用8位。考虑到同一个像素的红、绿、蓝三色的分布并不均匀,因此将三种颜色分别进行处理,这样就实现了将一张真彩色图像转换成了三张256阶灰度图像来处理,以达到增加压缩效果的目的。

  利用VB对红色分量的图像数据进行DCT编码的代码如下:

  For i = 0 To 7

  If i = 0 Then ci = 0.7071 Else ci = 1

  For j = 0 To 7

  If j = 0 Then cj = 0.7071 Else cj = 1

  g(i, j) = 0.25 * ci * cj

  tempdata = 0

  For x = 0 To 7

  For y = 0 To 7

  tempdata = tempdata + (pdata_r(i8 + x, j8 + y) * Cos((2 * y + 1) * j * PI / 16) * Cos((2 * x + 1) * i * PI / 16))

  Next y

  Next x

  g(i, j) = g(i, j) * tempdata

  Write #2, Round(g(i, j), 2);

  Next j

  Next i

利用上面的变换程序对下面的n×n像素块中的红色分量进行变换,可以通过对比变换前的原始数据和变换后的结果,了解变换对能量进行的集中。

  原始数据如下:

  变换后的数据如下,变换后的数据只保留了整数,左上角的数字集中了绝大部分的能量,其他的数据都在0-30之间变化。可以看出变换后的数据在相同数据上并不会比变换前多,因此如果就这样进行RLE编码,没有任何的压缩效果。要增加压缩效果,必须对经过DCT变换后的数据进行量化,如将除左上角之外的所有数据的个位数据舍去,则可以得到量化后的数据。

经过量化后的数据中,出现了大量的0、10、20、-10和-20,其他的数据很少,因此可以利用RLE对其进行编码,将获得一个比较好的压缩比。但是由于对数据进行了量化,因此,部分数据还原后,与原始数据出现了较大的差异,即量化得太严重,已经让图像产生了较大的偏差。因此,在具体量化的时候,应该根据实际还原的效果来决定选用的量化参数,本文的程序中采用的量化方法是将数据对5求模后的尾数进行舍去。

  8、VB对RLE压缩编码的实现

  本人中采用一种最简单的RLE编码规则,即前后没有重复的数据保持不变,如果有重复数据,则在重复数据前先写入符号“@”和重复次数。程序流程图如下:

  图五

  程序实现中的三个技术处理细节:

  8.1、由于图像的尺寸不一定能够被8整除,因此当出现不能被8整除的图像尺寸时,需要采取一定的措施,使得DCT变换能够正常进行。一种方法就是对图像多余的部分进行裁剪,这样虽然会造成图像的右边和下边像素的丢失,但是对于大图像来说,几个像素的丢失并不会对整个图像造成很大的影响,因此可以对其进行忽略。另一种方法就是在图像的右边和下边进行添加空白像素,将图片的大小补齐成能够被8整除。这样便可以实现DCT运算,在图像还原的时候将补上去的像素不进行显示即可较好的解决此问题。

8.2、由于真彩色图像具有红、绿、蓝三种颜色分量,因此在进行DCT变换时,应该将三种颜色分开进行DCT运算,为了将三种颜色分开,再程序中定义了三个数组,用来在内存中分开存放三种颜色的数据。

  ReDim pdata_r(Me.Picture1.ScaleWidth, Me.Picture1.ScaleHeight)

  ReDim pdata_g(Me.Picture1.ScaleWidth, Me.Picture1.ScaleHeight)

  ReDim pdata_b(Me.Picture1.ScaleWidth, Me.Picture1.ScaleHeight)

  这样虽然要用掉一部分内存,但是却能够比较方便的将不同的颜色分开,在进行DCT变换的时候先对8×8像素块中的红色进行DCT变换,然后将变换后得到的64个数据存入文件,接着对绿色进行变换,将绿色的64个数据存入文件,蓝色采用同样的方式。因此在存储的文件中,数据不时按像素顺序存放的,而是以64个像素为单位,采用红、绿、蓝三色分开存储。

  8.3、在进行IDCT的时候,由于事先对数据进行过量化,造成了一部分数据失真,因此在IDCT后,可能会由于误差的原因导致出现有数据为负数或者是大于255的数据。这样的数据如果参与颜色的计算和显示的话,将会导致还原后的图像中出现难看的杂色像素,如图六所示:

  要解决这个问题,只需要检查经过IDCT还原后的数据,如果数据小于0,则让它等于0,如果大于255则让它等于255,经过这样的处理后,还原的图像上就变得很干净,效果如图七所示。

9、误差分析

  将仅对DCT变换后的数据舍去小数,不进行任何其它量化的时候,逆变换后的结果基本和原来的数据相同,在进行比较的63360个数据中,58206个数据完全匹配, 5154个数据有微小差异,还原精度相当高。

  当采用将数据对5求模后的尾数进行舍去的方法对数据进行量化后,在63360个数据中,有21558个数据完全匹配,41802存在差异,但是数据之间的差值并不大,并且还原效果在肉眼可以接受的范围内,如图八所示。

  当采用将数据对10求模后的尾数进行舍去的方法对数据进行量化后,误差已经比较大,肉眼已经可以分辨出来,图像上呈现块状,块之间的像素的颜色不连续,如图九所示。

  10、压缩效果分析

  在不同的量化条件下的RLE压缩效果如下表所示:

  通过比较可以发现,量化越厉害,则RLE压缩的效果越明显,在不量化的情况下,进行RLE非但可能不能压缩数据,反而造成了数据的膨胀。因此,量化直接决定了RLE的效果。

  11、总结

  通过RLE压缩效果可以看到,如果需要将数据进行进一步的压缩,必须采用其他的一些方法,例如对压缩后的数据进行哈夫曼编码等。另外DCT变换时,像素块的大小也直接影响了RLE的压缩。如果将像素块增大,则当能量向左上角集中后,后面有大量的含有微小能量的数据,这样在量化后进行RLE的效果将更好。但是在进行像素块大小调节时,需要对压缩比和运算时间有一个综合的考虑。

  评论这张
 
阅读(499)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017