# Hybrid Encoding Scheme for AMBTC Compressed Images Using Ternary Representation Technique
## 3 Proposed Method
### Encoding Procedures  
This section describes the procedures of the proposed method. To distinguish the encoding methods of three types of image blocks, an indicator is prepended to the code stream of each encoded block. The indicators 0\({}_{2}\),10\({}_{2}\), and 11\({}_{2}\) are used to indicate a flat, smooth, and complex block is encoded, respectively. The detailed encoding procedures are shown as follows: \begin{tabular}{l l} Input: & Original image \(I\), block size \(n\times n\), thresholds \(\tau_{0}\) and \(\tau_{1}\), parameter \(\gamma\), and cluster size \(k\). \\ Output: & Code stream \(CS_{f}\). \\ Step 1: & Partition the original image \(I\) into blocks \(\left\{I_{i}\right\}_{i=0}^{N-1}\) of size \(n\times n\). Encode \(\left\{I_{i}\right\}_{i=0}^{N-1}\) using the AMBTC encoder and obtain codes \(\Phi_{i}=\left\{a_{i},b_{i},B_{i}\right\}_{i=0}^{N-1}\), as described in Section 2.1. \\ Step 2: & Scan codes \(\left\{a_{i},b_{i},B_{i}\right\}_{i=0}^{N-1}\). Let \(\left\{B_{s}\right\}_{s=0}^{N_{c}-1}\) be the bitmap of smooth blocks. Clustering \(\left\{B_{s}\right\}_{s=0}^{N_{c}-1}\) into \(k\) groups using the \(k\)-means clustering algorithm, we obtain \(k\) cluster centers \(\left\{C_{a}\right\}_{a=0}^{k-1}\) and \(N_{s}\) cluster indices \(\left\{a_{s}^{*}\right\}_{s=0}^{N_{c}-1}\). Concatenate the binary representation of \(\left\{C_{a}\right\}_{a=0}^{k-1}\) and obtain the concatenated code stream \(CS_{A}\). The \(N_{s}\) pairs of adjusted quantized values \(\left\{\hat{a}_{s},\hat{b}_{s}\right\}_{s=0}^{N_{c}-1}\) of smooth blocks are also obtained, as described in Section 3.2. Similarly, quantized values \(\left\{q_{c}^{0},q_{c}^{1},q_{c}^{2}\right\}_{c=0}^{N_{c}-1}\) and ternary maps \(\left\{T_{c}\right\}_{c=0}^{N_{c}-1}\) of complex blocks are also obtained, as described in Section 3.3. \\ Step 3: & Scan codes \(\left\{a_{i},b_{i},B_{i}\right\}_{i=0}^{N-1}\) again and perform the encoding according to the cases listed below: \\ \end{tabular}   
* If \(b_{i}-a_{i}\leq\tau_{0}\), a flat block is visited and the code stream of block \(I_{i}\) is \(CS_{i}=0_{2}||\left(m_{i}\right)_{2}\). * If \(\tau_{0}<b_{i}-a_{i}<\tau_{1}\), a smooth block is visited. Extract \(\hat{a}_{s}\), \(\hat{b}_{s}\), and \(\alpha_{s}^{*}\) from \(\left\{\hat{a}_{s},\hat{b}_{s},\alpha_{s}^{*}\right\}_{s=0}^{N-1}\) obtained in Step 2, and block \(I_{i}\) is encoded by \(CS_{i}=10_{2}\ ||\ \left(\hat{a}_{s}\right)_{2}||\left(\hat{b}_{s}-\hat{a}_{s} \right)_{2}||\left(\alpha_{s}^{*}\right)_{2}\). Note that \(\left(\hat{b}_{s}-\hat{a}_{s}\right)_{2}\) is encoded using the DES, as described in Section 2.2. * If \(b_{i}-a_{i}\geq\tau_{1}\), block \(I_{i}\) is a complex one. Extract \(q_{c}^{0}\), \(q_{c}^{1}\), \(q_{c}^{2}\), and \(T_{c}\) from \(\left\{q_{c}^{0},q_{c}^{1},q_{c}^{2},T_{c}\right\}_{c=0}^{N-1}\) obtained in Step 2, and block \(I_{i}\) is encoded by \(CS_{i}=11_{2}\ ||\ \left(q_{c}^{0}\right)_{2}||\left(q_{c}^{1}-q_{c}^{0} \right)_{2}||\left(q_{c}^{2}-q_{c}^{1}\right)_{2}||\left({r_{c}^{0}}\right)_{2}\). Note that \((q_{c}^{1}-q_{c}^{0})_{2}\) and \((q_{c}^{2}-q_{c}^{1})_{2}\) are encoded using the DES (see Section 2.2). * Repeat Step 3 until the code stream \(\{CS_{i}\}_{i=0}^{N-1}\) of blocks \(\{I_{i}\}_{i=0}^{N-1}\) are obtained. Concatenate \(\{CS_{i}\}_{i=0}^{N-1}\), we have the concatenated code stream \(CS_{B}\). * Concatenate \(CS_{A}\) and \(CS_{B}\); we obtain the final code stream \(CS_{f}\) of image \(I\), i.e., \(CS_{f}=CS_{A}\Big{|}\Big{|}CS_{B}\). The encoding of a given image block and the number of required bits for each block types are shown in Figure 1.  
We take a simple example to illustrate the encoding of smooth and complex blocks. Let \(I_{0}\) be a \(4\times 4\) block to be encoded, as shown in Figure 2a. Suppose \(\tau_{0}=4\), \(\tau_{1}=16\), \(\gamma=64\), \(\sigma=128\), and \(k=128\) are used in this example.