# Joint Image Compression and Encryption Using IWT with SPIHT, Kd-Tree and Chaotic Maps
## 2 Related Works
### SPIHT-Based Image Compression  
SPIHT is a wavelet-based coding method that was proposed by [PERSON] and [PERSON] in 1996 [17]. Wavelet transform provides satisfactory time and frequency resolution simultaneously. Thus, this method is considered highly suitable for the analysis and compression of images. However, the high computational cost of the traditional wavelet transform limits its application in high-speed and real-time signal processing. In 1998, [PERSON] proposed the Lifting wavelet transform [18], which is an alternative solution for discrete wavelet transform (DWT). Compared with the traditional wavelet transform, the lifting algorithm does not depend on the Fourier transform and requiresless computations (up to 50%) compared to the convolution-based approach. The Lifting wavelet transform is highly suitable for implementation on the hardware and reduces the computational complexity. During the lifting implementation, no extra memory buffer is required because of the in-place computation feature of lifting. Lifting wavelet transform (LWT) has attracted increased interest in image compression as it has low computational complexity due to the utilization of an ordinary wavelet filter in the lifting steps [18]. The lifting-based approach offers an integer-to-integer transformation that is suitable for lossless image compression. LWT is derived from a polyphase matrix representation that can distinguish between even and odd samples. A polyphase matrix is a matrix in which the elements are filter masks. To derive the lifting wavelet transform, the original filter is divided into a series of shorter filters using the filter-factoring algorithm. Those filters are designed as low-pass and high-pass filters with lifting steps. A polyphase matrix is used for matrix decomposition, which leads to additional matrices in the form of a lifting scheme. There are three stages in the LWT (see Figure 1): splitting, prediction and update. In the splitting stage, the input signal is divided into two sets: odd (Equation (1)) and even (Equation (2)) signals, which can be described as:  
\[x_{o}(n)=x(2n+1) \tag{1}\]  
\[x_{e}(n)=x(n+1) \tag{2}\]  
In the prediction stage, the even signal is used to estimate the odd signal via multiplication by a forecasting parameter P. The difference between the odd and predicted signals is the high-frequency coefficients, as expressed in Equation (3). \[d(n)=x_{o}(n)-p(x_{e}(n)) \tag{3}\]  
Then, in the update stage, the even signal is updated, and it results in low-frequency coefficients by Equation (4). \[c(n)=x_{e}(n)-U(d(n)) \tag{4}\]  
SPIHT is one of the most widely used, powerful and efficient image compression techniques, with extremely low computational complexity, especially with lifting-based IWT. With SPIHT, the image is first decomposed into a series of wavelet coefficients via the wavelet transform. These wavelet coefficients are grouped into sets that are known as spatial orientation trees (SOT), as shown in Figure 2a and scanning sequence in Figure 2b. After that, the coefficients in each SOT are encoded progressively from the most significant bit planes to the least significant bit planes, starting with the coefficients with the highest magnitude. Figure 1: Single lifting step. The SPIHT algorithm involves two coding passes: the sorting pass and the refinement pass. The sorting pass looks for zero trees and sorts significant and insignificant coefficients with respect to a specified threshold, as shown in Equation (5). The refinement pass sends the precision bits of the significant coefficients. After one sorting pass and one refinement pass, which can be considered one scan pass, the threshold T is halved, and the coding process is repeated until the expected bit rate is achieved. At the end, the compressed bit stream for all the coefficients is obtained. It provides satisfactory image quality, high PSNR, and optimization for progressive image transmission.