CSC 310, ASSIGNMNENT 2, SPRING 2004

Programs.

I wrote one encode program (encmono2) and one decode program
(decmono2) for use in both Part 1 and Part 2 of the assigment.  These
programs implement contexts of up to size 16, with optional backing up
to smaller contexts if the larger ones haven't been seen often enough
before.  Counts are incremented by 10 when each pixel is seen,
starting with a specified initial count.  An initial "-a" argument
causes all contexts to have their counts updated on each pixel;
without this argument, only the context used for encoding and the
higher-order contexts are updated.

In detail, the program arguments start with the optional "-a"
argument, which causes all contexts to be updated, and an optional
"-s" argument (encode program only), which causes some statistics to
be output.  These options (if any are present) are followed by the
specifications of the contexts to use, starting with the size of the
largest context, and the initial count to use for this context.  This
may be followed by any number of backup contexts, specified by three
numbers: the number of counts needed for the previous (higher-order)
context to be used, the size of the backup context, and the initial
count to use for that context.  For instance, the command

   encmono2 16 1 2 4 10

encodes using the 16-pixel context, with counts initialized to 1,
provided this context has been at least twice before.  If it has been
seen less than two times before, the 4-pixel context is used, with
counts initialized to 10.  Since no "-a" option was included, if the
16-pixel context is used, only it has its counts updated, whereas if
the 4-pixel context is used, the counts are updated for both the
4-pixel and the 16-pixel contexts.

Some complexities in the program are avoided using two methods.  One
is that the image is stored in an array with a border of 0s in the
margin, so that no special checks are needed for pixels near the edge.
Second, the shapes of the contexts are specified by arrays of offsets
in x and y to the pixels in the context (from the pixel being encoded),
and the values of pixels in the context are combined into an integer
by concatenating the bits in these pixels.  This avoids any need for
special programming for each size of context, and also allows for any
context size up to the maximum of 16 (not just 2, 4, 8, and 16).


Results for Part 1.

For Part 1, I found that the best results for all files were obtained
using 16-pixel contexts, with counts initialized to 1 (with 10 added
when a pixel is encountered).  There was substantial variation in
the size of the compressed files, as follows:

    5651 page1.enc2
    2841 page2.enc2
    4284 page3.enc2
    6828 page4.enc2
    6858 page5.enc2

The amount of white space in a page seems to be one of the main
factors in how compressible it is, as would be expected, since in a
large block of white, the white pixels can be predicted with high
probability.  Page3 may be less compressible than page2, even though
it has quite a bit of white space, because it has many random dots in
the figures, whose locations are not very predictable.


Results for Part 2.

I first tried a scheme in which contexts of size 16, 8, 4, and 2 were
used, with backup to a lower-order context if the higher-order context
had not been seen before.  Counts were intialized to one, and were
updated (by adding 10) only for the context used and higher-order
contexts.  Results were as follows:

    5556 page1.enc2
    2744 page2.enc2
    4199 page3.enc2
    6729 page4.enc2
    6751 page5.enc2

This is an improvement over Part 1 for all the pages.  Updating the
counts for all contexts (with the "-a" option) made things worse for
all pages.  The scheme with arguments 16 1 1 8 10 5 4 10 is slightly
better, producing the following compressed file sizes:

    5531 page1.enc2
    2726 page2.enc2
    4129 page3.enc2
    6696 page4.enc2
    6714 page5.enc2

As can be seen in the detailed output for Part 2, some other schemes
are better than this for some of the pages, but worse for others.