方块编码

维基百科,自由的百科全书
跳转至: 导航搜索

方块编码英语Block Truncation Coding縮寫BTC)是一种用于灰度图像有损数据压缩算法。这种算法将图像分为以方块为单位,在每一方块中,在保持原有平均数标准方差(即保持二阶矩)的同时,减少灰度等级,以达到压缩的目的。方块编码被认为是纹理压缩算法DXTC的前身;但在DXTC出现之前很久,方块编码已就被引入彩色图像的压缩,即色彩单元压缩[1]。 方块编码也被采用于视频压缩 [2] 中。

方块编码由普渡大學的米歇尔和德尔普两位教授首先提出。如果以4x4的方块为基本单位,用8比特的整型来传输或存储,这种算法可以达到4:1的压缩比率。如果用更大尺寸的方块,可以达到更大的压缩比率,但图像质量也会相应地降低。

这种算法也被用于了火星探路者的图像压缩。[3]

压缩过程[编辑]

图像被划分成4x4的方块,对于每个方块,计算其平均数标准方差。这两个值将用来决定解压缩时相应的方块所拥有的像素值。之后,根据平均数将这个方块中的像素分为两个灰度等级:

y(i,j) = 
\begin{cases} 
  1,  & x(i,j) > \bar x \\
  0,  & x(i,j) \le \bar x 
\end{cases}

这里的x(i,j)是原图像中的像素值, y(i,j)是压缩后的像素值。如果原像素值大于平均值,压缩后其值为1,否则为0。像素值如果等于平均值,其值可以为1,也可以为0,取决于具体实现的设置。每个像素压缩之后只需要一个比特,每一方块将需要16个比特来存储像素值。

然后根据平均值和标准方差,计算出a和b两个值,这两个值和16比特的像素值一起被存储。计算公式为:

a=\bar x - \sigma \sqrt{\cfrac {q}{m-q}}

b=\bar x + \sigma \sqrt{\cfrac {m-q}{q}}

其中\sigma为标准方差, (\bar x)为平均值,m为方块中的总像素值,q为原图像中值大于平均值的像素个数。解压缩过程中,值为0的像素被赋值为a,为1的被赋值为b。

x(i,j) = 
\begin{cases} 
  a,  & y(i,j) = 0 \\
  b,  & y(i,j) = 1 
\end{cases}

压缩的计算量要远大于解压缩的。解压缩时,只要将值0替换成a,值1替换成b。而压缩时,需要计算平均值,标准方差和用于解压缩的两个值。[4]

参见[编辑]

参考文献[编辑]

  1. ^ 1990 IEEE Colour Cell Compression Paper
  2. ^ 1981 IEEE Paper "Digital Video Bandwidth Compression Using Block Truncation Coding" [1]
  3. ^ Rover Camera Instrument Description. NASA. [2011-11-09]. 
  4. ^ Leis, J 2008, ELE4607 Advance Digital Communications, Module 3: Image & Video Coding. Lecture Slides, University of Southern Queensland, 2008.