Databases Reference
In-Depth Information
P(b|w)
P(w|w)
S
w
S
b
P(b|b)
P(w|b)
F I GU R E 7 . 6
The Capon model for binary images.
pixel separately, we can simply code the length of the runs of each color. For example, if we
had 190 white pixels followed by 30 black pixels, followed by another 210 white pixels, we
would code the sequence 190, 30, 210, along with an indication of the color of the first string
of pixels, instead of coding the 430 pixels individually. Coding the lengths of runs instead of
coding individual values is called run-length coding.
7.7.2 CCITT Group 3 and 4—Recommendations T.4 and
T.6
The recommendations for Group 3 facsimile include two coding schemes. One is a one-
dimensional scheme in which the coding on each line is performed independently of any other
line. The other is two-dimensional; the coding of one line is performed using the line-to-line
correlations.
The one-dimensional coding scheme is a run-length coding scheme in which each line is
represented as a series of alternating white runs and black runs. The first run is always a white
run. If the first pixel is a black pixel, then we assume that we have a white run of length zero.
Runs of different lengths occur with different probabilities; therefore, they are coded using
a variable-length code. The approach taken in CCITT standards T.4 and T.6 is to use a Huffman
code to encode the run lengths. However, the number of possible runlengths is extremely large,
and it is simply not feasible to build a codebook that large. Therefore, instead of generating a
Huffman code for each run length
r
l
, the run length is expressed in the form
r
l
=
64
×
m
+
t
for
t
=
0
,
1
,...,
63
,
and
m
=
1
,
2
,...,
27
.
(10)
When we have to represent a run length
r
l
, instead of finding a code for
r
l
,weusethe
corresponding codes for
m
and
t
. The codes for
t
are called the
terminating codes
, and the
codes for
m
are called the
make-up codes
.If
r
l
<
63, we only need to use a terminating code.
Otherwise, both a make-up code and a terminating code are used. For the range of
m
and
t
given
here, we can represent lengths of 1728, which is the number of pixels per line in an A4-size
document. However, if the document is wider, the recommendations provide for this with an
optional set of 13 codes. Except for the optional codes, there are separate codes for black and
white run lengths. This coding scheme is generally referred to as a
modified Huffman (MH)
scheme. Note that the Huffman codes are static codes based on probability models obtained
using a set of documents that the standards committee considered to be typical.
