## 2 The Proposed RDHEI Method
### Room Reservation and Image Encryption
#### 2.1.3 The Bit Plane Reordering  
As presented in Algorithm 2, the quadtree decomposition tries to find homogeneous blocks that are as large as possible to reserve room for data embedding with minimum auxiliary information. This algorithm exploits the high redundancy of the most significant bit planes obtained by the mapping prediction error process. The outputs of this algorithm are used in the reordering process and in the reconstruction process in order to recover the original image after decryption. The algorithm iterates through the homogeneous blocks for each bit plane in accordance with the quadtree decomposition steps, with homogeneous blocks arranged at the start and non-homogeneous blocks at the end, as shown in Figure 9. After bit planes reordering, the auxiliary information can now be inserted into the homogenous part of each bit plane leaving room for data embedding. Further details about the auxiliary information can be found in Figure 9. It is noteworthy that all auxiliary information are compressed using arithmetic coding in order to reduce the amount of bits required for their representations. Figure 9 details the quadtree decomposition and the bit plane reordering steps. For each bit plane, one bit is required to indicate if it is embeddable or not. As we have 8-bit planes, 8 bits are required to identify the embeddable ones. The next 18 bits are used to indicate the length in bits of the embeddable room. These two pieces of auxiliary information will be used by the data hider to insert hidden data into the encrypted bit planes. After the last bit of the embeddable room, we propose to insert the following auxiliary information in order:  
* The compressed binary label map and 10 bits indicating its length. This information needs to be inserted in the MSB plane only. * The compressed binary string representing the quadtree decomposition, with 16 bits indicating its length. * The compressed binary string corresponding to the original values of the homogeneous blocks, which also requires 16 bits to represent its length. Figure 8: (**a**) The MSB plane of the mapped prediction error Lena image, (**b**) and its quadtree decomposition. (**c**) The MSB plane of the mapped prediction error Jetplane image, (**d**) and its quadtree decomposition. ```
structblock \(x\) [Starting row index] \(y\) [Starting column index] \(size\) [Size of the block] \(value\) [One bit to represent the value of an homogeneous block] endstruct Input: An Image bit plane. Output:\(binaryStr\): a string that represents the quadtree decomposition of the input bit plane. \(listHomogeneousBlocks\), the list of homogeneous blocks. function quadtreeDecomposition(\(bitPlane\)) \(rows,cols\gets shape(bitPlane)\) \(binaryStr\leftarrow\) \"\" \(listHomogeneousBlocks\leftarrow[\;]\) \(struct\) block root \(\leftarrow\{0,0,rows,\"\"\}\) \(q\gets Queue()\) \(q.put(root)\) whilenot\(q.empty()\)do \(node\gets q.get()\) \(currentBlock\gets getBlock(bitPlane,node)\) ifisHomogeneous(\(currentBlock\))then \(binaryStr\gets binaryStr+\"0\"\) \(node.value\gets currentBlock[0,0]\) \(listHomogeneousBlocks.append(node)\) continue endif \(binaryStr\gets binaryStr+\"1\"\) //The block is not subdivided into 4 sub-blocks if its size is equal to \(2\times 2\) pixels if\(node.size==2\)then continue endif // If the block is not homogeneous, split it into four sub-blocks and add them to the queue \(halfSize\gets node.size//2\) // Add the new 4 sub-blocks to the queue \(q.put(block(node.x,node.y,halfSize,\"\"))\) \(q.put(block(node.x,node.y+halfSize,halfSize,\"\"))\) \(q.put(block(node.x+halfSize,node.y,halfSize,\"\"))\) \(q.put(block(node.x+halfSize,node.y+halfSize,halfSize,\"\")\) endwhile return\(binaryStr,listHomogeneousBlocks\) endfunction
```  
**Algorithm 2** Quadtree decomposition of a mapped prediction error bit plane. In the proposed method, the total embedding capacity (in bits) is then calculated using Equation (2).