# Joint Image Compression and Encryption Using IWT with SPIHT, Kd-Tree and Chaotic Maps
## 3 Compact Data Structures
### Kd-Tree  
Initially, Kd-tree was used for the representation of web graphs. Here, we used Kd-tree for the compression of binary sparse matrices with permutations and substitution operations. The Kd-tree structure uses various matrix properties, such as sparseness and large homogeneous areas of zeros and ones. Kd-tree efficiently compresses the large areas of zeros and ones and provides efficient navigation over these compressed values. The simplest variant of Kd-tree is K\({}^{2}\)-tree, where; K = 2; K\({}^{2}\)-tree is similar to a compact Quad tree [39].  
In K\({}^{2}\)-tree, a binary matrix is divided recursively from left to right and from top to bottom. A conceptual tree is built from this recursive division; a 1-bit is added to the sub-tree T (root tree) of the conceptual tree if the sub-matrix contains at least a single 1-bit and 0-bits otherwise. At each partitioning level, each matrix is divided into K\({}^{2}\) sub-matrices of equal size. During this recursive division of the binary matrix, two sub-trees (T and L) are built:  
* T (tree): stores all the level-wise traversal bits, except the last-level values when the original matrix values have been reached. The bits in the T tree are placed level-wise.
* L (last-level leaves): stores leave values of the original binary matrix after recursive subdivisions with replacement of consecutive zeros and ones (more than three).  
Figure 3 shows an example of a K\({}^{2}\)-tree in which the matrix was divided into four sub-matrices and for each sub-matrix, the root node has a bit. Each bit indicates whether the sub-matrix has at least one 1 or all zeros. Therefore, the root node of Figure 3 is 1011, since the first sub-matrix has 1 s, the second does not have 1 s, and so on. The sub-matrices that have 1 s are divided again, following the same method, until the subdivision reaches the cell level.  
The original binary matrix can be constructed by navigating these trees. For this, we must construct a rank structure with sub-tree T. The rank structure counts the number of ones in the root sub-tree T. Each 1-bit in T represents a sub-matrix, depending upon its position, and each 0-bit represents a zero matrix. If we know the position of slightly in root tree T, we can determine the position of its children via pos0 = rank1 (T, pos) \(\times\) K\({}^{2}\) of T: L. In this way, navigate the conceptual tree using trees T and L.  
Variants of the K\({}^{2}\)-tree can be used to compress contiguous zeros and ones, or any other specific pattern, together. With these variants of kd-tree, we can compress binary images that contain large areas of homogeneous values. In these variants, the strategy is to check for specific contiguous values and remove these contagious values from the original matrix via a specific bit representation in the root tree. The sizes of these homogeneous areas vary with the level. If we remove homogenous regions of multiple values from the original matrix, then we need more bits in the root tree to represent  
Figure 3: Binary matrix with K\({}^{2}\)-tree example where K = 2.  
the values in the original matrix. In our case, we compress homogenous regions of zeros and ones. Conceptually, these values are represented by nodes of different colors. The variants of the K\({}^{2}\)-tree for compression of zeros and ones can be traversed in the same way as the original K\({}^{2}\)-tree. With modified navigation rules, we can easily implement the compression of ones with K\({}^{2}\)-trees.  
Depending upon the size and distribution of the values in the binary matrix, we can change the number of division levels by changing the value of K. Usually, for a very large matrix, higher values of K at the start and smaller values at lower levels improve compression. To further improve the compression efficiency, we have used different values of K for ones and zeros, which also improve the security level by introducing more uncertainty in the data size. These variants of K\({}^{2}\)-tree can be used efficiently for the compression of binary raster images.