## 6 Image Compression
### The Implementation on a Distributed System  
An implementation on a small scale system with no interprocessor communication was realized since we were able to partition an image into up to a hundred areas and to apply the square block matching heuristic independently to each area with no relevant loss of compression effectiveness. In [8] we obtained the expected speed-up on the compression and decompression times doubling up the number of processors of a 256 Intel Xeon 3.06 GHz processors machine (avogadro.cilea.it) from 1 to 32. Working only with monochromatic matches and using a variable length encoding for the pointer fields after the flag, we were even able to preserve the compression effectiveness on a large scale system with a thousand processor and no interprocessor communication [41]. To obtain perfect scalability, however, we implemented in [8] the PRAM EREW procedure on a full binary tree architecture under some realistic  
Figure 5: The largest match in (0,0) and (6,6) is computed at step 5.  
assumptions on the image data as follows. We extend the \(m\times m^{\prime}\) image \(I\) with dummy rows and columns so that \(I\) is partitioned into \(x\times y\) areas \(A_{i,j}\) for \(1\leq i,j\leq 2^{h}\), where \(x\) and \(y\) are \(\Theta(\alpha^{1/2})\), \(n=mm^{\prime}\) is the size of the image and \(h=\)min \(\{k:2^{k}\geq\text{max}(m/x,m^{\prime}/y)\}\). We store these areas into the leaves of the tree according to a one-dimensional layout which allows an easy way of merging the monochromatic ones at the upper levels. Let \(\mu=2^{h}\). The number of leaves is \(2^{2h}\) and the leaves are numbered from 1 to \(2^{2h}\) from left to right. It follows that the tree has height \(2h\). Therefore, the height of the tree is O\((\log n)\) and the number of nodes is O\((n/\alpha)\). Such layout is described by the recursive procedure of Figure 6. The initial value for \(i\), \(j\) and \(\ell\) is 1 and \(\ell\) is a global variable. In parallel for each area, each leaf processor applies the sequential parsing algorithm so that in O\((\alpha\log M)\) time each area is parsed into rectangles, some of which are monochromatic. Again, before encoding we wish to compute larger monochromatic rectangles. After the compression heuristic has been executed on each area, we have to show how the procedure to compute larger monochromatic rectangles can be implemented on a full binary tree architecture with the same number of processors without slowing it down. This is possible by making some realistic assumptions. Let \(\ell_{R}\) and \(w_{R}\) be the length and the width of a monochromatic match \(R\), respectively. We define \(s_{R}=\text{max}\ \{\ell_{R},w_{R}\}\). We make a first assumption that the number of monochromatic matches \(R\) with \(s_{R}\geq 2^{k}\lceil\log^{1/2}n\rceil\) is O\((n/(2^{2k}\log n))\) for \(1\leq k\leq h-1\). While computing larger monochromatic rectangles, we store in each leaf the partial results on the monochromatic rectangles covering the corresponding area (it is enough to store for each rectangle the indices of the areas at the upper left and lower right corners). If \(i\) is odd, it follows from the procedure of Figure 6 that the processors storing areas \(A_{2i-1,j}\) and \(A_{2i,j}\) are siblings. Such processors merge \(A_{2i-1,j}\) and \(A_{2i,j}\) provided they are monochromatic and have the same color by broadcasting the information through their parent. It also follows from such procedure that the same can be done horizontally for \(A_{i,2j-1}\) and \(A_{i,2j}\) by broadcasting the information through the processors at level \(2h-2\).