查看“︁方块编码”︁的源代码

'''方块编码'''（{{lang-en|'''Block Truncation Coding'''}}，[[縮寫]]：'''BTC'''）是一种用于[[灰度图像]]的[[有损数据压缩]]算法。这种算法将图像分为以方块为单位，在每一方块中，在保持原有[[平均数]]和[[标准方差]]（即保持[[矩 (數學)|二阶矩]]）的同时，减少灰度等级，以达到压缩的目的。方块编码被认为是纹理压缩算法[[S3纹理压缩|DXTC]]的前身；但在DXTC出现之前很久，方块编码已就被引入彩色图像的压缩，即[[色彩单元压缩]]<ref>[http://ieeexplore.ieee.org/iel5/498/3989/00152671.pdf 1990 IEEE Colour Cell Compression Paper]</ref>。 方块编码也被采用于[[視訊壓縮]] <ref>1981 IEEE Paper "Digital Video Bandwidth Compression Using Block Truncation Coding" [http://ieeexplore.ieee.org/iel5/8159/23934/01094938.pdf]</ref> 中。

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

这种算法也被用于了[[火星探路者]]的图像压缩。<ref>{{cite web|url=http://pdsimg.jpl.nasa.gov/data/mpfr-m-rvrcam-2-edr-v1.0/mprv_0001/document/rcinst.htm|title=Rover Camera Instrument Description|publisher=NASA|accessdate=2011-11-09|archive-date=2016-03-05|archive-url=https://web.archive.org/web/20160305001725/http://pdsimg.jpl.nasa.gov/data/mpfr-m-rvrcam-2-edr-v1.0/mprv_0001/document/rcinst.htm|dead-url=yes}}</ref>

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

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

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

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

<math>a=\bar x - \sigma \sqrt{\cfrac {q}{m-q}}</math>

<math>b=\bar x + \sigma \sqrt{\cfrac {m-q}{q}}</math>

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

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

压缩的计算量要远大于解压缩的。解压缩时，只要将值0替换成a，值1替换成b。而压缩时，需要计算平均值，标准方差和用于解压缩的两个值。<ref>Leis, J 2008, ELE4607 Advance Digital Communications, Module 3: Image & Video Coding.  Lecture Slides, University of Southern Queensland, 2008.</ref>

==参见==

* [[色彩单元压缩]]
* [[纹理压缩]]
* [[S3纹理压缩]]

==参考文献==
{{Reflist}}

[[Category:三维计算机图形学|T]]
[[Category:有损压缩算法|T]]