## 3 Preliminaries  
### Ambtc  
The Block Truncation Coding (BTC) [32] is a simple lossy compression method based on moment preserving quantization for blocks of pixels in a grayscale image. Since BTC produces a set of bitmap, mean and standard deviation to represent a block, it gives a CR (size of the original image/size of the compressed image) of 4; hence, the bit rate is 2 bits per pixel for a \(4\times 4\) block. Though the BTC method provides good compression without much degradation on the reconstructed images, it shows some artifacts like the staircase effect. Absolute Moment Block Truncation Coding (AMBTC) [33] preserves the higher mean and lower mean of each of the blocks and improves the staircase effect of the conventional BTC method. Besides, AMBTC is simpler than BTC, thus the computation speed is very fast. The AMBTC algorithm involves the following steps:  
**Step 1:**: The original image of size \(N\times N\) is divided into non-overlapping blocks (\(C\)) of the size \(m\times m\) (let \(m=4\)), and each block is processed separately. Let \(m^{2}=k\).
**Step 2:**: For each block, the average pixel value is calculated by Equation (1).  
\[\tilde{x}=\frac{1}{k}\sum_{i=1}^{k}x_{i} \tag{1}\]  
where \(x_{i}\) represents the \(i\)th pixel value of this block with the size of \(k\). All pixels in the block are quantized into a bitmap \(b_{i}(0\text{ or }1)\) using Equation (2). That is, if the corresponding pixel \(x_{i}\) is greater than or equal to the average (\(\tilde{x}\)), it is assigned with '1', otherwise it is '0'. Pixels in each block are divided into two groups of '1' or '0'.  
\[b_{i}=\begin{cases}1,&\text{if }x_{i}\geq\tilde{x},\\ 0,&\text{if }x_{i}<\tilde{x}.\end{cases} \tag{2}\]
**Step 3:**: The block \(\mathcal{M}\) is partitioned into two sets of pixels \(\mathcal{M}_{0}\) and \(\mathcal{M}_{1}\) such that \(\mathcal{M}=\mathcal{M}_{0}\cup\mathcal{M}_{1}\) and \(\mathcal{M}_{0}\cap\mathcal{M}_{1}=\phi\) where \(\mathcal{M}_{0}=\{0_{0},0_{1},\ldots,0_{t}\}\) and \(\mathcal{M}_{1}=\{1_{1},1_{2},\ldots,1_{k-t}\}\), and \(t\) and \(k-t\) refer to the numbers of pixels in the '0' and '1' groups, respectively. The means \(Q_{1}\) and \(Q_{2}\) of the two groups indicate the quantization levels of the groups '0' and '1'. The two quantization levels are calculated by Equations (3) and (4).  
\[Q_{1}=\left\lfloor\frac{1}{t}\sum_{x_{i}<x}x_{i}\right\rfloor \tag{3}\]  
\[Q_{2}=\left\lfloor\frac{1}{k-t}\sum_{x_{i}\geq x}x_{i}\right\rfloor \tag{4}\]
**Step 4:**: To reconstruct the pixel marked by '0' it will be given the value \(Q_{1}\), and that marked by '1' will be given the value \(Q_{2}\). The values \(Q_{1}\) and \(Q_{2}\) satisfy the following relation. The compressed block is simply uncompressed by using Equation (5).  
\[g_{i}=\begin{cases}Q_{1},&\text{if }b_{i}=0,\\ Q_{2},&\text{if }b_{i}=1.\end{cases} \tag{5}\]  
The image block is compressed into two quantization levels \(Q_{1}\) and \(Q_{2}\), and a bitmap \(\mathcal{M}\), and it can be represented as a \(trio(Q_{1},Q_{2},\mathcal{M})\). A bitmap \(\mathcal{M}\) contains the bit-planes that represent the pixels, and the values \(Q_{1}\) and \(Q_{2}\) are used to decode the AMBTC-compressed image by using Equation (5). If the block size is \(4\times 4\) then it will give the 32-bit compressed data (i.e., the size of the block bitmap is 16 bits; converting \(Q_{1}\) and \(Q_{1}\) to binary results in 16 bits), and hence the bit rate is 2 bpp. For \(m=4\), 16 pixels are represented by a \(trio(Q_{1},Q_{2},\mathcal{M})\) of \(8+8+16=32\) bits, so the compression ratio (CR) is \(\left(16\times 8\right)/32=4\). For \(512\times 512\) pixel images, the file size of 2M-bits can be reduced to 0.5 M-bits.