This section is based on Atallah *et al.* [2]. The reader might
also want to consult [8,9,13,16].

The detection of the above-mentioned approximate repetitiveness is done by
approximate pattern matching, whence the name *Pattern Matching Image
Compression* (PMIC). The main idea behind it is a lossy extension of the
Lempel-Ziv data compression scheme in which one searches for the longest
prefix of an uncompressed file that *approximately* occurs in the
already processed file. The distance measure subtending the notion of
approximate occurrence can be the *Hamming distance*, or of the *
square error distortion*, or the *string edit* distance, or any of
the other distances considered in the distortion theory (cf.
[3]).

In short, let us consider a stationary and ergodic sequence
taking values in a finite alphabet (think of as
an image scanned row by row). For image compression the alphabet has
size . We write *X*_{m}^{n} to denote , and
for simplicity . The substring *X _{1}*

A variable-length compression code can be designed based on *L*_{n}. The
code is a pair (`pointer to a position` *i*, `length of` *L*_{n}), if
a sufficiently long *L*_{n} is found. Otherwise we leave the next *L*_{n}
symbols uncompressed. We clearly need bits for the
above code. The compression ratio *r* can be approximated by

(1) |

and to estimate it one needs to find out probabilistic behavior of *L*_{n}.
In [8,9] it is proved that where *r _{0}*(

The above main idea is enhanced by several observations that constitute
PMIC scheme. They are:

**Additive Shift**. It is reasonable to expect that in an image there are
several substrings, say *x*^{m}, *y*^{m}, that differ only by *almost*
constant pattern, that is, *y*_{i}=*x*_{i} +*c* for where *c* is
not necessary a constant, but whose variation is rather small.

In such a case we store the average difference *c* as well as a
(*pointer*,*length*) pair, which enables us to recover *y*_{i} from *x*_{i}
(instead of storing *y*_{i} explicitly). In general, we determine the
additive shift *c* by checking whether the following condition is fulfilled
or not

where *D*' is a constant. If the above holds, we compute the shift *c* as . It can be easily verified that for
*x*_{i}=*y*_{i}+*c*, and *c* a constant, the above procedure returns *c*. In
passing, we should observe that this enhancement improves even *
lossless* (*D*=0) image compression based on the Lempel-Ziv scheme.

**Reverse Prefix**. We check for similarities between a substring in the
uncompressed file and a *reversed* (i.e., read backward) substring in
the database.

**Variable Maximum Distortion**. It is well known that human vision can
easily distinguish an ``undesired'' pattern in a low frequency (constant)
background while the same pattern might be almost invisible to humans in
high frequency (quickly varying) background.

Therefore, we used a low value of maximum distortion, say *D _{1}*, for slowly
varying background, and a high value, say

where *x*_{ij} is the value of (*i*,*j*) pixel. In our implementation, we
used the lower value of *D* whenever and the higher value
of *D* otherwise.

**Max-Difference Constraint**. Our code will also satisfy the additional
constraint that where *DD* is a suitably chosen
value. This additional constraint, which we call *max-difference*
constraint, ensures that visually noticeable ``spikes'' are not averaged
out of existence by the smoothing effect of the square error distortion
constraint. We incorporate this max-difference constraint in the function
by adopting the convention that if , otherwise is the
standard distortion as defined above (i.e., Hamming or square of
difference).

**Small Prefix**. It does not make too much sense to
store a (*pointer*,*position*) when the longest prefix is small.
In this case, we store the original pixels of the image.

**Run-Length Coding**. For those parts of the
picture that do not vary at all, or vary little,
we used run-length coding: if the next pixels vary little,
we store a pixel value and the number of repetitions.

(a) (b)

(c) (d)

Figure 1: Different flavors of PMIC on the ``Lena'' image

Comparisons of different flavors of PMIC on the ``Lena'' image:
(a) Classical PMIC (compression ratio equal to 4.3);
(b) JPEG (compression ratio equal to 7.9);
(c) PMIC with simple predictive coding (compression ratio equal to 7.9);
(d) PMIC with column compression (compression equal to 5.3).
As mentioned above, in this paper we investigate an impact of
prediction algorithms on PMIC. A simple prediction enhancement can
work as follows (prediction loop - our main contribution of
this paper - is described in depth in next sections):
**Prediction**. A significant speed up in compression without major
deterioration in quality can be obtained by using prediction. It works as
follows: we compressed only every second row of an image, and when
decompressed we restore the missing row by using a prediction (cf.
[11], and next sections). For high quality image compression, one can
design a two-rounds approach where in the second round one sends the
missing rows. Figure 1 shows two versions of the
compressed Lena picture: one with PMIC, and the other with PMIC and
predictive ``reduction/expansion''.

Finally, we also explore in this paper one more feature, namely:

**Column compression**. PMIC is performed on rows.
In order to have it performed on columns,
one simple way to proceed is to ``transpose'' the original image before
compression. Indeed, the rows of the compressed ``transposed''
image are the columns of the original one. This algorithm has been
performed on several different images, and this feature can sometimes
increase either the compression ratio or the quality level, as shown in
Figure 1.

Let us discuss algorithmic challenges of PMIC. It boils down to
an efficient implementation of finding the longest prefix of length *L*_{n}
in yet uncompressed file.
We present below one possible implementation (for others the
reader is refereed to [2].
Let *x _{1}*

**Algorithm** `PREFIX`

**Input:** *x _{1}*

beginInitialize allS_{ij}:= 0.fori=1ton-mdoforj=1tomdoComputeS_{ij}:=S_{i,j-1}+d(x_{i+j-1},y_{j})doenddoendLetkbe the largestjsuch that , and lettbe the correspondingiOutputkandtend

The above can easily be modified to incorporate the enhancements
discussed above (additive shift, etc.) and to use *O*(1) variables
rather than the *S*_{ij} array.

In order to compress an image we apply `PREFIX` several
times to compress a row, which we call `COMPRESS_ROW` algorithm,
and this is further use to compress a whole image in either
`COMPRESS_LONG_DATABASE` (where the database sequence is of
multiplicity of *N*, i.e., *f N* where *f* is a small integer)
or `COMPRESS_SHORT_DATABASE` (where the database sequence is
of length *O*(1) but located just above the ``point'' of compression).
In the former case the algorithmic complexity of
compression is *O*(*N ^{4}*) while in the latter case it is which
is only away from the optimal complexity