Databases Reference
In-Depth Information
In the two-dimensional scheme, instead of reporting the run lengths, which in terms of our
Markov model are the lengths of time we remain in one state, we report the transition times
when we move from one state to another state. Look at Figure
7.7
. We can encode this in two
ways. We can say that the first row consists of a sequence of runs 0, 2, 3, 3, 8, and the second
row consists of runs of lengths 0, 1, 8, 3, 4 (notice the first runs of length zero). Or, we can
encode the location of the pixel values that occur at a transition from white to black or black
to white. The first pixel is an imaginary white pixel assumed to be to the left of the first actual
pixel. Therefore, if we were to code transition locations, we would encode the first row as 1,
3, 6, 9 and the second row as 1, 2, 10, 13.
Generally, rows of a facsimile image are heavily correlated. Therefore, it would be easier
to code the transition points with reference to the previous line than to code each one in terms
of its absolute location, or even its distance from the previous transition point. This is the basic
idea behind the recommended two-dimensional coding scheme. This scheme is a modification
of a two-dimensional coding scheme called the
Relative Element Address Designate
(READ)
code [
99
,
100
] and is often referred to as
Modified READ
(MR). The READ code was the
Japanese proposal to the CCITT for the Group 3 standard.
To understand the two-dimensional coding scheme, we need some definitions.
a
0
:
This is the last pixel whose value is known to both the encoder and decoder. At the
beginning of encoding each line,
a
0
refers to an imaginary white pixel to the left of the
first actual pixel. While it is often a transition pixel, it does not have to be.
a
1
:
This is the first transition pixel to the right of
a
0
. By definition, its color should be the
opposite of
a
0
. The location of this pixel is known only to the encoder.
a
2
:
This is the second transition pixel to the right of
a
0
. Its color should be the opposite of
a
1
,
which means it has the same color as
a
0
. The location of this pixel is also known only to
the encoder.
b
1
:
This is the first transition pixel on the line above the line currently being encoded to the
right of
a
0
whose color is the opposite of
a
0
. As the line above is known to both encoder
and decoder, as is the value of
a
0
, the location of
b
1
is also known to both the encoder and
decoder.
b
2
:
This is the first transition pixel to the right of
b
1
on the line above the line currently being
encoded.
For the pixels in Figure
7.7
, if the second row is the one being currently encoded, and if we
have encoded the pixels up to the second pixel, the assignment of the different pixels is shown
in Figure
7.8
. The pixel assignments for a slightly different arrangement of black and white
pixels are shown in Figure
7.9
.
F I GU R E 7 . 7
Two rows of an image. The transition pixels are marked with a dot.
