# Hybrid Encoding Scheme for AMBTC Compressed Images Using Ternary Representation Technique
## 3 Proposed Method
### Encoding of Smooth Blocks  
If \(\tau_{0}<b_{i}-a_{i}<\tau_{1}\), the fluctuation of pixel values of block \(I_{i}\) is more than that of a flat block. Therefore, we refer to \(I_{i}\) as a smooth block. To reduce the bitrate, a codebook consisting of the \(k\) most representative bitmaps (codewords) is found, and the bitmap of the smooth block will be replaced by an index pointing to one of the codewords in the codebook. We use the \(k\)-means algorithm [20] to obtain the \(k\) most representative bitmaps. Let \(\left\{a_{s},b_{s},B_{s}\right\}_{s=0}^{N_{s}-1}\) be the set of AMBTC codes satisfying \(\tau_{0}<b_{i}-a_{i}<\tau_{1}\) for \(0\leq i\leq N-1\), where \(N_{s}\) is the number of smooth blocks. Firstly, an initial codebook \(\left\{C_{\alpha}^{0}\right\}_{\alpha=0}^{k-1}\) is constructed by randomly selecting \(k\) bitmaps from \(\left\{B_{s}\right\}_{s=0}^{N_{s}-1}\), where \(k\) is much less than \(N_{s}\). Secondly, the bitmaps \(\left\{B_{s}\right\}_{s=0}^{N_{s}-1}\) are classified into \(k\) clusters according to the similarities between \(\left\{B_{s}\right\}_{s=0}^{N_{s}-1}\) and \(\left\{C_{\alpha}^{0}\right\}_{\alpha=0}^{k-1}\). That is, if \(B_{s}\) has more bits identical to \(C_{\alpha}^{0}\) than other codewords, then \(B_{s}\) is classified into group \(\alpha\), where \(0\leq\alpha\leq k-1\). Thirdly, \(\left\{B_{s}\right\}_{s=0}^{N_{s}-1}\) of the same group are averaged and rounded to obtain the updated codebook \(\left\{C_{\alpha}^{1}\right\}_{\alpha=0}^{k-1}\). Repeat the classification process \(t\) times and the final representative bitmaps \(\left\{C_{\alpha}^{t}\right\}_{\alpha=0}^{k-1}\) are obtained. Normally, setting \(t=6\) can already obtain a satisfactory result. We denote the final representative bitmaps as \(\left\{C_{\alpha}\right\}_{\alpha=0}^{k-1}\). Once the classification process is completed, the classification results \(\left\{\alpha_{s}^{*}\right\}_{s=0}^{N_{s}-1}\) of bitmaps \(\left\{B_{s}\right\}_{s=0}^{N_{s}-1}\) are also obtained. Note that the codeword with index \(\alpha_{s}^{*}\) has the nearest distance to \(B_{s}\), that is:  
\[\alpha_{s}^{*}=\underset{\alpha}{\text{argmin}}\bigg{(}\sum_{j=0}^{n\times n- 1}\left(B_{s,j}-C_{\alpha,j}\right)^{2}\bigg{)}^{1/2} \tag{6}\]  
where \(B_{s,j}\) and \(C_{\alpha,j}\) represent the \(j-\)th element of \(B_{s}\) and \(C_{\alpha}\), respectively. Instead of recording \(\left\{B_{s}\right\}_{s=0}^{N_{s}-1}\), the proposed method uses the binary representation of \(\left\{\alpha_{s}^{*}\right\}_{s=0}^{N_{s}-1}\) as the required bitmap information. Therefore, the bits required to record the bitmap are reduced from \(n\times n\) bits to \(\log_{2}(k)\) bits. To successfully decode the bitmap, we must have cluster centers \(\left\{C_{\alpha}\right\}_{\alpha=0}^{k-1}\) and cluster indices \(\left\{\alpha_{s}^{*}\right\}_{s=0}^{N_{s}-1}\). Therefore, \(\left\{C_{\alpha}\right\}_{\alpha=0}^{k-1}\) must be included as part of the compressed codes. When decoding a smooth block, because we use cluster center \(C_{\alpha_{s}^{*}}\) to replace the original bitmap \(B_{s}\), the quality of the reconstructed image block will be reduced. To minimize the reduced quality, a quantized value adjustment (QA) technique [18] is employed. QA is a technique originally used in a data hiding technique to reduce the distortions of the reconstructed AMBTC block when the original bitmap is replaced by secret data. Because bits in the bitmap are altered, distortions of the reconstructed block are inevitable. QA subtly adjusts the quantized values by counting the bit difference between the original bitmap and secret data. In the proposed method, the original bitmap is replaced by a cluster center, which resembles the situations in which the bitmap is replaced by secret data. Therefore, the QA technique can be applied in the proposed method.