# An Improved Robust Fractal Image Compression Based on M-Estimator
## 2 Baseline Fractal Image Compression  
The fractal coding process can be described as follows: the original image is partitioned into non-overlapping blocks called range blocks (\(R\)) which are usually \(8\times 8\) pixels each. There are also domain blocks (\(D\)) which are twice the size of range blocks and overlap such that a new domain block starts every pixel. For each range block (\(r_{j}\)), a domain block (\(D_{t}\)) that best approximates this range block under the predetermined contractive transformations (\(\omega_{i}\)), is searched for. In detail, these transformations contract the domain blocks spatially to \(8\times 8\) pixels and then transform the gray levels by a combination of rescaling, offset adjustment, reflection, and rotation. The general fractal affine transformation can be expressed as  
\[\omega_{i}(D_{t})=\varphi_{i}(\gamma_{i}(D_{t})) \tag{1}\]  
where \(\gamma_{i}\) is the down-sampling operation. We denote \(d=\gamma_{i}(D_{t})\), and \(\varphi_{i}\) can be expressed as  
\[\varphi\begin{bmatrix}x\\ y\\ d(x,y)\end{bmatrix}=\begin{bmatrix}a&b&0\\ c&d&0\\ 0&0&s\end{bmatrix}+\begin{bmatrix}t_{x}\\ t_{y}\\ o\end{bmatrix} \tag{2}\]  
where \((t_{x},\ t_{y})\) is the location of domain block \(D_{t}\) in original image, \(s\) is the contract scaling, and \(o\) is the brightness offset. The \(2\times 2\) sub-matrix  
\[\begin{bmatrix}a&b\\ c&d\end{bmatrix}\]represents the isometrical transformations in Equation (3).  
\[\tau_{0}=\begin{bmatrix}1&0\\ 0&1\end{bmatrix},\ \tau_{1}=\begin{bmatrix}1&0\\ 0&-1\end{bmatrix},\ \tau_{2}=\begin{bmatrix}-1&0\\ 0&1\end{bmatrix},\ \tau_{3}=\begin{bmatrix}-1&0\\ 0&-1\end{bmatrix},\]  
\[\tau_{4}=\begin{bmatrix}0&1\\ 1&0\end{bmatrix},\ \tau_{5}=\begin{bmatrix}0&1\\ -1&0\end{bmatrix},\ \tau_{6}=\begin{bmatrix}0&-1\\ 1&0\end{bmatrix},\ \tau_{7}=\begin{bmatrix}0&-1\\ -1&0\end{bmatrix} \tag{3}\]  
Hence, the general affined transformation can also be written as  
\[\omega_{j}(D_{t})=s_{i}\cdot\tau_{i}(\gamma_{i}(D_{t}))+o_{i} \tag{4}\]  
Equation (2) calculates the reconstructed (approximated) range block as the transformation of \(d\), denoted as \(\widetilde{d}\).  
\[\widetilde{d}=s\cdot\tau(d)+o \tag{5}\]  
The parameters are selected so that the transformed domain block (\(D_{t}\)) is a good approximation of the range block \(r_{j}\) by minimizing the matching error  
\[E=\underset{d\in\Omega}{\text{minmin}}E(r,\widetilde{d})=\underset{D\in \Omega}{\text{minminmin}}\|s_{k}\cdot d_{k}+o_{k}I-r\|^{2} \tag{6}\]  
where, \(d_{k}=\tau(d)\), \(k\) is the index of the isometrical transformation. The parameter \(s\) and \(o\) can be obtained by the least-squares method as  
\[s=\frac{<r-\overline{r}I,d-\overline{d}I>}{\|d-\overline{d}I\|^{2}} \tag{7}\]  
\[o=\overline{r}-s\overline{d} \tag{8}\]  
The fractal code consists of \(t_{x}^{*}\), \(t_{y}^{*}\), \(k^{*}\), \(s^{*}\) and \(o^{*}\). In practice, \(t_{x}^{*}\), \(t_{y}^{*}\), \(k^{*}\), \(s^{*}\) and \(o^{*}\) can be quantized by 8, 8, 3, 5, and 7 bits, respectively.  
At decoder, the transformation for all range blocks can be iteratively applied to any initial image which then converges to the fractal approximation of the image.