## 6 Image Compression
### The Generalized LZ1-Type Method  
The square matching compression procedure scans an \(m\times m^{\prime}\) image by a raster scan (the greedy matching technique could work with any other scan described in [14]). A 64K table with one position for each possible \(4\times 4\) subarray is the only data structure used. All-zero and all-one squares are handled differently. The encoding scheme is to precede each item with a flag field indicating whether there is a monochromatic square, a match, or raw data. When there is a match, the \(4\times 4\) subarray in the current position \((i,j)\) is hashed to yield a pointer to a copy in some position \((k,h)\). This pointer is used for the current greedy match and then replaced in the hash table by a pointer to the current position. The procedure for computing the largest square match takes \(\mbox{O}(M)\) time, where \(M\) is the size of the match. Obviously, this procedure can be used to compute the largest monochromatic square in a given position \((i,j)\) as well. If the \(4\times 4\) subarray in position \((i,j)\) is monochromatic, then we compute the largest monochromatic square in that position. Otherwise, we compute the largest match in the position provided by the hash table and update the table with the current position. If the subarray is not hashed to a pointer, then it is left uncompressed and added to the hash table with its current position. The positions covered by matches are skipped in the linear scan of the image. We wish to point out that besides the proper matches we call a match every square of the parsing of the image produced by the heuristic. We also call pointer the encoding of a match. Each pointer starts with a flag field indicating whether there is a monochromatic match (0 for the white ones and 10 for the black ones), a proper match (110) or a raw match (111). If we use rectangular matches, the pointer is more expensive in size since two fields for the dimension of proper or monochromatic matches are needed. However, the matches are larger and there is a gain in compression effectiveness. The procedure for finding the largest rectangular match is described in Figure 4. We denote with \(p_{i,j}\) the pixel in position \((i,j)\). At the first step, the procedure computes the longest possible width for a rectangle match in \((i,j)\) with respect to the position \((k,h)\). The rectangle \(1\times l\) computed at the first step is the current rectangular match and the sizes of its sides are stored in \(side1\) and \(side2\). In order to check whether there is a better match than the current one, the longest one-dimensional match on the next row and column \(j\), not exceeding the current width, is computed with respect to the row next to the current copy and to column \(h\). Its length is stored in the temporary variable \(width\) and the temporary variable \(length\) is increased by one. If the rectangle \(R\) whose sides have size \(width\) and \(length\) is greater than the current match, the current match is replaced by \(R\). We iterate this operation on each row until the area of the current match is greater or equal to the area of the longest feasible \(width\)-wide rectangle, since no further improvement would be possible at that point. For example, in Figure 5 we apply the procedure to find the largest rectangular match between position \((0,0)\) and \((6,6)\). A one-dimensional match of width 6 is found at step 1. Then, at step 2 a better match is obtained which is \(2\times 4\). At step 3 and step 4 the current match is still \(2\times 4\) since the longest match on row 3 and 9 has width 2. At step 5, another match of width 2 provides a better rectangle match which is \(5\times 2\). At step 6, the procedure stops since the longest match has width 1 and the rectangle match can cover at most 7 rows. It follows that \(5\times 2\) is the greedy match since a rectangle of width 1 cannot have a larger area. Obviously, this procedure can be used for computing the largest monochromatic rectangle in a given position \((i,j)\) as well.