# Survey on Data Hiding Based on Block Truncation Coding
## 3 Survey of Related Works
### Reversible Data Hiding  
#### 3.2.1 Histogram Modification  
[PERSON] et al. [46] proposed the RDH based on histogram shifting (HS). First, a histogram is constructed from the bitmaps. Second, it embeds secret data by revising the histogram according to be hidden bits. That is, after generating a histogram on three-pixel groups (patterns) in the bitmap BM, the highest and lowest frequencies will be obtained, respectively. Since it is impossible to directly apply HS to bitmap images, a process of converting them to decimal is required. After creating a histogram from virtual pixel values (a decimal number made up of binary numbers), DH is performed by moving the pixel values according to the hidden bits. The detailed process [6] of DH follows the procedure below. 1. Generate its histogram \(H(x)\). 2. Grayscale value \(x\in[0,7]\) is obtained from converting three pixels in the bitmap image to a decimal number. 3. In the histogram \(H(x)\), find the maximum point \(h(a)\)\(a\in[0,7]\) and the minimum point \(h(b)\)\(b\in[0,7]\). 4. If the minimum point \(h(b)>0\), save the position \((i,j)\) of those pixels and the pixel gray value \(b\) as bookkeeping information. 5. Move the whole part of the histogram \(H(x)\) with \(x\in(a,b)\) to the right by 1 unit (Figure 4(b)). 6. Scan the image, and once meeting the pixel \(a\), check the to-be-embedded bit. If the to-be-embedded bit is '1', the pixel grayscale value is changed \(a+1\). If the bit is '0', the pixel value remains \(a\) (Figure 4(c)). In Lin and Liu [46], the first process is to use the order of two compressed quantization levels such as trio \((\mu_{0},\mu_{1},BM)\). If the difference between the values of the quantization levels is \(\mu_{1}-\mu_{0}=(T\geq 1)\), the data can be embedded by the order of the quantization levels. That is, if the bit is \(d=0\), the trio \((\mu_{0},\mu_{1},BM)\) is intact, and if \(d=1\), replace it with trio \((\mu_{1},\mu_{0},BM)\). Hidden bits can be extracted simply by scanning the order of two quantization levels, and there is no problem in restoring the original order. The method of histogram-based DH here is similar to what was mentioned before. First, the BM image is scanned in 4-bit units. If the 4-bit pattern is the _peak point_ and the secret bit is \(d=0\), the _peak point_ is not changed. Otherwise, if the 4-bit pattern is the _peak point_ and \(d=1\), change the _peak point_ to a _zero point_ pattern. For the histogram shift method, it is best if the _zero point_ is 0. Otherwise, the _zero point_ part should be recorded in a separate method and used when restoring the image. [PERSON] et al. [47] introduced HS for DH within every bitmap. First, the histogram is constructed after converting all blocks except for the block where the difference value (DV,  
Figure 5: Embedding procedure using histogram shift. \(|\mu_{0}-\mu_{1}|\)) is 0 in 4-bit units. Find the two pairs of peak \(P\) and low point \(L\) in the generated histogram. For each frequency, find the midpoint between the highest and lowest points. If the secret bit is 0, leave the \(2\times 2\) bitmap unchanged. Otherwise, it modifies the \(2\times 2\) bitmap into a bitmap with converted decimal values equal to the values at that midpoint. Only \(2\times 2\) bitmaps of \(4\times 4\) blocks whose DV is lower than the predefined threshold \(T\) are used to contain secret bits. [PERSON] et al. [48] proposed RDH using HS for AMBTC compressed images. As mentioned earlier, each block of AMBTC contains a bitmap BM made up of 0's and 1's. Here, their suggestion is to use '2' in addition to '0' and '1' for the bitmap. In other words, the secret bit is hidden by moving the pixel '1' to '2' according to hidden bits. Figure 6a shows a histogram of a bitmap BM, where the number of '0' pixels is 8 and '1' pixels is 8. Next, it begins data embedding by dealing out bin '1' according to the message. If the secret bit is '0,' keep '1' (bin 1) values without moving to 2's (bin 2). Otherwise, the 1's (bin 1) move to 2's (bin 2).