方塊編碼

方塊編碼（英語：Block Truncation Coding，縮寫：BTC）是一種用於灰度圖像的有損數據壓縮算法。這種算法將圖像分為以方塊為單位，在每一方塊中，在保持原有平均數和標準方差（即保持二階矩）的同時，減少灰度等級，以達到壓縮的目的。方塊編碼被認為是紋理壓縮算法DXTC的前身；但在DXTC出現之前很久，方塊編碼已就被引入彩色圖像的壓縮，即色彩單元壓縮^[1]。 方塊編碼也被採用於視訊壓縮 ^[2] 中。

方塊編碼由普渡大學的米歇爾和德爾普兩位教授首先提出。如果以4x4的方塊為基本單位，用8比特的整型來傳輸或存儲，這種算法可以達到4：1的壓縮比率。如果用更大尺寸的方塊，可以達到更大的壓縮比率，但圖像質量也會相應地降低。

這種算法也被用於了火星探路者的圖像壓縮。^[3]

壓縮過程

圖像被劃分成4x4的方塊，對於每個方塊，計算其平均數和標準方差。這兩個值將用來決定解壓縮時相應的方塊所擁有的像素值。之後，根據平均數將這個方塊中的像素分為兩個灰度等級：

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

這裏的${\displaystyle x(i,j)}$是原圖像中的像素值， ${\displaystyle y(i,j)}$是壓縮後的像素值。如果原像素值大於平均值，壓縮後其值為1，否則為0。像素值如果等於平均值，其值可以為1，也可以為0，取決於具體實現的設置。每個像素壓縮之後只需要一個比特，每一方塊將需要16個比特來存儲像素值。

然後根據平均值和標準方差，計算出a和b兩個值，這兩個值和16比特的像素值一起被存儲。計算公式為：

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

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

其中${\displaystyle \sigma }$為標準方差, (${\displaystyle {\bar {x}}}$)為平均值，m為方塊中的總像素值，q為原圖像中值大於平均值的像素個數。解壓縮過程中，值為0的像素被賦值為a，為1的被賦值為b。

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

壓縮的計算量要遠大於解壓縮的。解壓縮時，只要將值0替換成a，值1替換成b。而壓縮時，需要計算平均值，標準方差和用於解壓縮的兩個值。^[4]

參見

• 色彩單元壓縮
• 紋理壓縮
• S3紋理壓縮

參考文獻

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]. （原始內容存檔於2016-03-05）.
4. Leis, J 2008, ELE4607 Advance Digital Communications, Module 3: Image & Video Coding. Lecture Slides, University of Southern Queensland, 2008.