Home » Personal collection » Acorn hard disk » zipped_disks » 2000_apps_2 » apps2/!ChangeFSI/btpc/README

apps2/!ChangeFSI/btpc/README

This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.

Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.

Tape/disk: Home » Personal collection » Acorn hard disk » zipped_disks » 2000_apps_2
Filename: apps2/!ChangeFSI/btpc/README
Read OK:
File size: 3ECF bytes
Load address: 0000
Exec address: 0000
Duplicates

There are 3 duplicate copies of this file in the archive:

File contents
Binary Tree Predictive Coding (BTPC), Version 3
===============================================

Contents
========

        What is BTPC?                   Overview
        What's new in Version 3
        Where to find it                Net addresses for code and docs
        Programs                        Details of available code
        Comparisons between BTPC,       Representative results
         JPEG and the state of the art
        Comments on the results         Why and when to use BTPC
        Patents and copyright           No patents, free use.

What is BTPC?
=============

BTPC is a general-purpose image coding method for lossless or lossy compression
of photographs and graphics. It is well suited for coding multimedia images
which combine text, graphics and photographs, and  is also appropriate as a
general-purpose method when the image type is not known in advance.

As a lossy compressor, BTPC is slightly superior to JPEG for photographic
images and much superior for graphics. Visually-transparent coding of color
graphics is usually possible at the rate used by GIF. Against a
state-of-the-art lossy scheme (Said and Pearlman's modified zerotree coder), it
is inferior for photographs but superior for graphics, mixed  and multimedia
images. Moreover (see below), BTPC is much faster.

When applied losslessly, BTPC has good performance on both natural images and
graphics. Against a state-of-the-art lossless scheme (Wu's CALIC), it is
usually inferior for photographs and about the same for graphics. Again, BTPC
is much faster.

BTPC uses a binary pyramid, predictive coding and Huffman coding. No part of it
is covered by patents. C++ source code is available and may be freely used.
BTPC is inherently progressive, and a straightforward modification of the
decoder to write directly to an on-screen picture buffer allows simple,
progressive, image recovery.

What's new in Version 3 - Fast decoding
=======================================

In version 3, BTPC decode times have been halved over the previous version
(2c). Version 3 also improves encoding speed and gives slightly better
compression.

BTPC decoding speed is now equal to that of the Independent JPEG group (IJG)
JPEG decoder, and more than three times faster than its other rivals. Of
course, in the words of the IJG, it is "still not as fast as we'd like".

Where to find it
================

Documentation of Binary Tree Predictive Coding is at:

http://monet.uwaterloo.ca/~john/btpc.html

Source code is at:

ftp://monet.uwaterloo.ca/pub/john/btpcv3.tar.Z

To run
-------

        cbtpc input_pic output_file [quality]
        dbtpc input_file output_pic

The optional quality parameter is a number between 0 and 100. Default is 75.
Quality values roughly approximate JPEG quality values, but 100 is lossless.

This version only reads and writes PGM and PPM raw format files (magic number
"P5" or "P6").

Comparisons between BTPC, JPEG and the State of the Art
=======================================================

I have compared BTPC with the current standard, JPEG, and what I consider to be
the state of the art in still-image compression. For lossless coding I have
compared against Wu's CALIC system, which has been proposed for the lossless
mode of JPEG, and has done well in the first round of tests for that standard.
For lossy coding I have compared against Said and Pearlman's wavelet-based
embedded coder (based on Shapiro's zerotree approach). Both CALIC and the Said
and Pearlman (henceforth S&P) coder exist in slow and fast versions. In each
case the slow version uses an arithmetic coder to improve compression. BTPC and
JPEG can compress color pictures, but S&P and CALIC can not, so the results
here refer only to grayscale images.

I have used an extensive set of test images, most of which are available at
links.uwaterloo.ca. Here I give representative results from that testing. The
programs were run on a SparcStation; times are in seconds. I have included only
decoding time - for all methods encoding time is longer. Indeed, for BTPC, I
have not tried to optimize the encoder at all, so it currently takes between
two and three times as long as the decoder to run. The reason for my neglect of
encoding speed is that fast decoding is more important in the applications I am
interested in (e.g. image databases). Nonetheless, BTPC version 3 encoding is
substantially faster than CALIC and S&P.

Some caveats
------------

I have chosen CALIC and S&P because I believe them to be the best that is
currently being achieved. Possibly some commercial products do better. I would
like to hear about any that are available for evaluation.

Having said this, please bear in mind that BTPC is not intended to beat state
of the art systems like CALIC and S&P in their areas of strength. Rather, it is
supposed to be "general purpose", which means it should do reasonably well over
a wide range of possible inputs, and should run fast. Testing against the state
of the art is a kind of "worst case" comparison, so be warned!

One of BTPC's design criteria was decoding speed. I am not sure that this was
the case for CALIC and S&P. However, both Wu, and Said and Pearlman have argued
that their fast versions are fast (!) so I've considered it fair game to make
them compete in a timing comparison.

A consequence of designing BTPC as a "general-purpose" coder is that the only
difference between lossless and lossy coding is the quantizer step size. For
better or for worse, I have resisted the idea of a separate lossless "mode",
and I am still not sure of the wisdom of this.

1.     Typical figures for photographic images
-----------------------------------------------

Here are two sets of typical results for coding photographic images. These show
the general trend for photos with BTPC falling between JPEG and S&P/CALIC for
compression efficiency, and BTPC and JPEG being much faster than the fast
versions of S&P and CALIC.

512 x 512 Lenna:

Lossy coding at PSNR 36.9 dB (= JPEG coded with Q of 75):

Scheme                          bpp             Decode time
------                          ---             -----------

JPEG (IJG v 6)                  1.05            1.4
BTPC3                           0.93            1.4
S&P fast                        0.66            5.2
S&P slow                        0.60            8.9

Lossless coding:

Scheme                          bpp             Decode time
------                          ---             -----------

BTPC3                           4.66            2.9
CALIC fast                      4.40            10.0
CALIC slow                      4.33            24.7

256 x 256 Cameraman:

Lossy coding at PSNR 34.7 dB (= JPEG coded with Q of 75):

Scheme                          bpp             Decode time
------                          ---             -----------

JPEG (IJG v 6)                  1.34            0.4
BTPC3                           0.95            0.4
S&P fast                        0.91            1.3
S&P slow                        0.82            2.5

Lossless coding:

Scheme                          bpp             Decode time
------                          ---             -----------

BTPC3                           5.02            0.7
CALIC fast                      4.34            2.4
CALIC slow                      4.31            6.2

2.     BTPC's worst case
-------------------------

In my test suite, BTPC's worst case was "achieved" on the 512 x 512
photographic image "Barbara" which includes large areas of stripes. This is the
only picture for which BTPC performed worse than JPEG (and then only
marginally). The reason is that JPEG's DCT is able to exploit the regular
spatial frequency structure of the stripes. BTPC cannot do this. (On the other
hand, BTPC clearly outperforms JPEG on textured pictures with less regular
spatial structure - e.g. Gold Hill.)

512 x 512 Barbara:

Lossy coding at PSNR 36.2 dB (= JPEG coded with Q of 75):

Scheme                          bpp             Decode time
------                          ---             -----------

JPEG (IJG v 6)                  1.33            1.6
BTPC3                           1.36            1.7
S&P fast                        0.93            5.4
S&P slow                        0.87            10.1

Lossless coding:

Scheme                          bpp             Decode time
------                          ---             -----------

BTPC3                           5.31            3.0
CALIC fast                      4.59            10.5
CALIC slow                      4.48            26.5

3.     Typical figures for graphical images
--------------------------------------------

With purely graphical images, BTPC's performance improves relative to the other
schemes. It consistently compresses more than JPEG, S&P and the fast version of
CALIC. It compresses about the same as the slow version of CALIC, at about nine
times the speed. Here are figures for coding two typical presentation graphics.

496 x 672 France:

Lossy coding at PSNR 34.6 dB (= JPEG coded with Q of 75):

Scheme                          bpp             Decode time
------                          ---             -----------

JPEG (IJG v 6)                  1.43            1.7
BTPC3                           0.53            1.7
S&P fast                        1.09            7.1
S&P slow                        0.87            14.4

Lossless coding:

Scheme                          bpp             Decode time
------                          ---             -----------

BTPC3                           0.89            2.2
CALIC fast                      1.40            7.4
CALIC slow                      0.82            21.2

The difference between the two CALIC results is correct, and illustrates a
problem with the use of Huffman coding in the CALIC algorithm on highly
redundant images.

372 x 619 World Map:

Lossy coding at PSNR 34.4 dB (= JPEG coded with Q of 75):

Scheme                          bpp             Decode time
------                          ---             -----------

JPEG (IJG v 6)                  1.83            1.2
BTPC3                           0.63            1.2
S&P fast                        1.52            5.7     [S&P coded a cropped
                                                        version of the image]
S&P slow                        1.27            12.1

Lossless coding:

Scheme                          bpp             Decode time
------                          ---             -----------

BTPC3                           0.63            1.2
CALIC fast                      1.06            3.2
CALIC slow                      0.61            12.0

4.     Typical figures for multimedia images
---------------------------------------------

Because the relative performance of BTPC and the other schemes is different on
photographs and graphics, mixed or multimedia images can give different
results. Here is an example where photographs are embedded within two-level
graphics (UW Library montage). This favors CALIC which has a special mode for
two-level regions.

352 x 464 Library:

Lossy coding at PSNR 30.6 dB (= JPEG coded with Q of 75):

Scheme                          bpp             Decode time
------                          ---             -----------

JPEG (IJG v 6)                  2.36            1.1
BTPC3                           1.58            1.1
S&P fast                        1.87            5.8
S&P slow                        1.61            10.6

Lossless coding:

Scheme                          bpp             Decode time
------                          ---             -----------

BTPC3                           5.42            1.8
CALIC fast                      5.20            6.6
CALIC slow                      5.01            16.4

Summary of the Results
======================

Further results are given at http://monet.uwaterloo.ca/~john/btpc.html. The
ones given above are supposed to be representative of the general trends which
I summarize as:

1. Lossless coding. BTPC compression is usually between 5 and 10% less
   efficient than the state of the art, CALIC, for photographs, and about the
   same efficiency as the slow version of CALIC for graphics. It is
   substantially more efficient than the fast version of CALIC for graphics. It
   is about 3.5 times faster than the fast version and about 9 times faster
   than the slow version on average. BTPC requires more memory than CALIC, in
   that the entire picture is held in store. On the other hand, it allow
   progressive decoding.

2. Lossy coding vs JPEG. BTPC is almost always superior to JPEG. On average it
   is about 20% more efficient than JPEG for photographs, at least twice as
   efficient for graphics. Decoding is as fast as the IJG decoding and uses
   slightly more memory. Encoding currently takes between two and three times
   as long as IJG JPEG.

3. Lossy coding vs the state of the art. Embedded coders like S&P and Shapiro's
   seem to be the future of lossy coding for natural images. BTPC is
   competitive on simple pictures (like cameraman, mentioned above), but on
   more textured images can require 50% more bits than S&P for a photograph.
   However, BTPC codes graphics and multimedia images more efficiently, and its
   decoding time is always less than a third that of fast S&P, and usually less
   than a quarter.

Patents and Copyright
=====================

The BTPC method is patent-free. In particular, no use is made of arithmetic
coding. The source code is copyright (c) 1994, 1995, John A. Robinson, except
for portions of the file colmap.C which are the work of the Independent JPEG
group and therefore copyright (C) 1991, 1992, 1993, 1994, 1995 Thomas G. Lane.
(Previous versions of BTPC contained code from Unix compact: this has now been
replaced.)

You may freely use all the BTPC code on exactly the same terms as the
Independent JPEG group allows use of their code. Following their pattern, and
adapting their README file (see READMEJ for the original), here is how it
works:

I welcome the use of this software as a component of commercial products. No
royalty is required, but I do ask for an acknowledgement in product
documentation, as described below.

In plain English:

1. I don't promise that this software works. (But if you find any bugs,
   please let me know!)
2. You can use this software for whatever you want. You don't have to pay me.
3. You may not pretend that you wrote this software. If you use it in a
   program, you must acknowledge somewhere in your documentation that
   you've used the BTPC Version 3 code.

In legalese:

The author makes NO WARRANTY or representation, either express or implied, with
respect to this software, its quality, accuracy, merchantability, or fitness
for a particular purpose. This software is provided "AS IS", and you, its user,
assume the entire risk as to its quality and accuracy.

This software, excluding the file colmap.C, is copyright (C) 1994, 1995, John
A. Robinson, All Rights Reserved except as specified below.

Permission is hereby granted to use, copy, modify, and distribute this software
(or portions thereof) for any purpose, without fee, subject to these
conditions:

(1) If any part of the source code for this software is distributed, then this
"Patents and Copyright" section of the README file must be included, with this
copyright and no-warranty notice unaltered; and any additions, deletions, or
changes to the original files must be clearly indicated in accompanying
documentation.

(2) If only executable code is distributed, then the accompanying documentation
must state that "this software is based in part on Binary Tree Predictive
Coding Version 3, implemented by J. A. Robinson".

(3) Permission for use of this software is granted only if the user accepts
full responsibility for any undesirable consequences; the author accepts NO
LIABILITY for damages of any kind.

NOTE THAT IF YOU USE THE FILE COLMAP.C YOU MUST COMPLY WITH THE IJG'S TERMS TOO
- SEE THE FILE READMEJ.
00000000  42 69 6e 61 72 79 20 54  72 65 65 20 50 72 65 64  |Binary Tree Pred|
00000010  69 63 74 69 76 65 20 43  6f 64 69 6e 67 20 28 42  |ictive Coding (B|
00000020  54 50 43 29 2c 20 56 65  72 73 69 6f 6e 20 33 0a  |TPC), Version 3.|
00000030  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 3d 3d 3d  |================|
*
00000050  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 3d 3d 0a  |===============.|
00000060  0a 43 6f 6e 74 65 6e 74  73 0a 3d 3d 3d 3d 3d 3d  |.Contents.======|
00000070  3d 3d 0a 0a 20 20 20 20  20 20 20 20 57 68 61 74  |==..        What|
00000080  20 69 73 20 42 54 50 43  3f 20 20 20 20 20 20 20  | is BTPC?       |
00000090  20 20 20 20 20 20 20 20  20 20 20 20 4f 76 65 72  |            Over|
000000a0  76 69 65 77 0a 20 20 20  20 20 20 20 20 57 68 61  |view.        Wha|
000000b0  74 27 73 20 6e 65 77 20  69 6e 20 56 65 72 73 69  |t's new in Versi|
000000c0  6f 6e 20 33 0a 20 20 20  20 20 20 20 20 57 68 65  |on 3.        Whe|
000000d0  72 65 20 74 6f 20 66 69  6e 64 20 69 74 20 20 20  |re to find it   |
000000e0  20 20 20 20 20 20 20 20  20 20 20 20 20 4e 65 74  |             Net|
000000f0  20 61 64 64 72 65 73 73  65 73 20 66 6f 72 20 63  | addresses for c|
00000100  6f 64 65 20 61 6e 64 20  64 6f 63 73 0a 20 20 20  |ode and docs.   |
00000110  20 20 20 20 20 50 72 6f  67 72 61 6d 73 20 20 20  |     Programs   |
00000120  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00000130  20 20 20 20 20 44 65 74  61 69 6c 73 20 6f 66 20  |     Details of |
00000140  61 76 61 69 6c 61 62 6c  65 20 63 6f 64 65 0a 20  |available code. |
00000150  20 20 20 20 20 20 20 43  6f 6d 70 61 72 69 73 6f  |       Compariso|
00000160  6e 73 20 62 65 74 77 65  65 6e 20 42 54 50 43 2c  |ns between BTPC,|
00000170  20 20 20 20 20 20 20 52  65 70 72 65 73 65 6e 74  |       Represent|
00000180  61 74 69 76 65 20 72 65  73 75 6c 74 73 0a 20 20  |ative results.  |
00000190  20 20 20 20 20 20 20 4a  50 45 47 20 61 6e 64 20  |       JPEG and |
000001a0  74 68 65 20 73 74 61 74  65 20 6f 66 20 74 68 65  |the state of the|
000001b0  20 61 72 74 0a 20 20 20  20 20 20 20 20 43 6f 6d  | art.        Com|
000001c0  6d 65 6e 74 73 20 6f 6e  20 74 68 65 20 72 65 73  |ments on the res|
000001d0  75 6c 74 73 20 20 20 20  20 20 20 20 20 57 68 79  |ults         Why|
000001e0  20 61 6e 64 20 77 68 65  6e 20 74 6f 20 75 73 65  | and when to use|
000001f0  20 42 54 50 43 0a 20 20  20 20 20 20 20 20 50 61  | BTPC.        Pa|
00000200  74 65 6e 74 73 20 61 6e  64 20 63 6f 70 79 72 69  |tents and copyri|
00000210  67 68 74 20 20 20 20 20  20 20 20 20 20 20 4e 6f  |ght           No|
00000220  20 70 61 74 65 6e 74 73  2c 20 66 72 65 65 20 75  | patents, free u|
00000230  73 65 2e 0a 0a 57 68 61  74 20 69 73 20 42 54 50  |se...What is BTP|
00000240  43 3f 0a 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 3d 3d 3d  |C?.=============|
00000250  0a 0a 42 54 50 43 20 69  73 20 61 20 67 65 6e 65  |..BTPC is a gene|
00000260  72 61 6c 2d 70 75 72 70  6f 73 65 20 69 6d 61 67  |ral-purpose imag|
00000270  65 20 63 6f 64 69 6e 67  20 6d 65 74 68 6f 64 20  |e coding method |
00000280  66 6f 72 20 6c 6f 73 73  6c 65 73 73 20 6f 72 20  |for lossless or |
00000290  6c 6f 73 73 79 20 63 6f  6d 70 72 65 73 73 69 6f  |lossy compressio|
000002a0  6e 0a 6f 66 20 70 68 6f  74 6f 67 72 61 70 68 73  |n.of photographs|
000002b0  20 61 6e 64 20 67 72 61  70 68 69 63 73 2e 20 49  | and graphics. I|
000002c0  74 20 69 73 20 77 65 6c  6c 20 73 75 69 74 65 64  |t is well suited|
000002d0  20 66 6f 72 20 63 6f 64  69 6e 67 20 6d 75 6c 74  | for coding mult|
000002e0  69 6d 65 64 69 61 20 69  6d 61 67 65 73 0a 77 68  |imedia images.wh|
000002f0  69 63 68 20 63 6f 6d 62  69 6e 65 20 74 65 78 74  |ich combine text|
00000300  2c 20 67 72 61 70 68 69  63 73 20 61 6e 64 20 70  |, graphics and p|
00000310  68 6f 74 6f 67 72 61 70  68 73 2c 20 61 6e 64 20  |hotographs, and |
00000320  20 69 73 20 61 6c 73 6f  20 61 70 70 72 6f 70 72  | is also appropr|
00000330  69 61 74 65 20 61 73 20  61 0a 67 65 6e 65 72 61  |iate as a.genera|
00000340  6c 2d 70 75 72 70 6f 73  65 20 6d 65 74 68 6f 64  |l-purpose method|
00000350  20 77 68 65 6e 20 74 68  65 20 69 6d 61 67 65 20  | when the image |
00000360  74 79 70 65 20 69 73 20  6e 6f 74 20 6b 6e 6f 77  |type is not know|
00000370  6e 20 69 6e 20 61 64 76  61 6e 63 65 2e 0a 0a 41  |n in advance...A|
00000380  73 20 61 20 6c 6f 73 73  79 20 63 6f 6d 70 72 65  |s a lossy compre|
00000390  73 73 6f 72 2c 20 42 54  50 43 20 69 73 20 73 6c  |ssor, BTPC is sl|
000003a0  69 67 68 74 6c 79 20 73  75 70 65 72 69 6f 72 20  |ightly superior |
000003b0  74 6f 20 4a 50 45 47 20  66 6f 72 20 70 68 6f 74  |to JPEG for phot|
000003c0  6f 67 72 61 70 68 69 63  0a 69 6d 61 67 65 73 20  |ographic.images |
000003d0  61 6e 64 20 6d 75 63 68  20 73 75 70 65 72 69 6f  |and much superio|
000003e0  72 20 66 6f 72 20 67 72  61 70 68 69 63 73 2e 20  |r for graphics. |
000003f0  56 69 73 75 61 6c 6c 79  2d 74 72 61 6e 73 70 61  |Visually-transpa|
00000400  72 65 6e 74 20 63 6f 64  69 6e 67 20 6f 66 20 63  |rent coding of c|
00000410  6f 6c 6f 72 0a 67 72 61  70 68 69 63 73 20 69 73  |olor.graphics is|
00000420  20 75 73 75 61 6c 6c 79  20 70 6f 73 73 69 62 6c  | usually possibl|
00000430  65 20 61 74 20 74 68 65  20 72 61 74 65 20 75 73  |e at the rate us|
00000440  65 64 20 62 79 20 47 49  46 2e 20 41 67 61 69 6e  |ed by GIF. Again|
00000450  73 74 20 61 0a 73 74 61  74 65 2d 6f 66 2d 74 68  |st a.state-of-th|
00000460  65 2d 61 72 74 20 6c 6f  73 73 79 20 73 63 68 65  |e-art lossy sche|
00000470  6d 65 20 28 53 61 69 64  20 61 6e 64 20 50 65 61  |me (Said and Pea|
00000480  72 6c 6d 61 6e 27 73 20  6d 6f 64 69 66 69 65 64  |rlman's modified|
00000490  20 7a 65 72 6f 74 72 65  65 20 63 6f 64 65 72 29  | zerotree coder)|
000004a0  2c 20 69 74 0a 69 73 20  69 6e 66 65 72 69 6f 72  |, it.is inferior|
000004b0  20 66 6f 72 20 70 68 6f  74 6f 67 72 61 70 68 73  | for photographs|
000004c0  20 62 75 74 20 73 75 70  65 72 69 6f 72 20 66 6f  | but superior fo|
000004d0  72 20 67 72 61 70 68 69  63 73 2c 20 6d 69 78 65  |r graphics, mixe|
000004e0  64 20 20 61 6e 64 20 6d  75 6c 74 69 6d 65 64 69  |d  and multimedi|
000004f0  61 0a 69 6d 61 67 65 73  2e 20 4d 6f 72 65 6f 76  |a.images. Moreov|
00000500  65 72 20 28 73 65 65 20  62 65 6c 6f 77 29 2c 20  |er (see below), |
00000510  42 54 50 43 20 69 73 20  6d 75 63 68 20 66 61 73  |BTPC is much fas|
00000520  74 65 72 2e 0a 0a 57 68  65 6e 20 61 70 70 6c 69  |ter...When appli|
00000530  65 64 20 6c 6f 73 73 6c  65 73 73 6c 79 2c 20 42  |ed losslessly, B|
00000540  54 50 43 20 68 61 73 20  67 6f 6f 64 20 70 65 72  |TPC has good per|
00000550  66 6f 72 6d 61 6e 63 65  20 6f 6e 20 62 6f 74 68  |formance on both|
00000560  20 6e 61 74 75 72 61 6c  20 69 6d 61 67 65 73 20  | natural images |
00000570  61 6e 64 0a 67 72 61 70  68 69 63 73 2e 20 41 67  |and.graphics. Ag|
00000580  61 69 6e 73 74 20 61 20  73 74 61 74 65 2d 6f 66  |ainst a state-of|
00000590  2d 74 68 65 2d 61 72 74  20 6c 6f 73 73 6c 65 73  |-the-art lossles|
000005a0  73 20 73 63 68 65 6d 65  20 28 57 75 27 73 20 43  |s scheme (Wu's C|
000005b0  41 4c 49 43 29 2c 20 69  74 20 69 73 0a 75 73 75  |ALIC), it is.usu|
000005c0  61 6c 6c 79 20 69 6e 66  65 72 69 6f 72 20 66 6f  |ally inferior fo|
000005d0  72 20 70 68 6f 74 6f 67  72 61 70 68 73 20 61 6e  |r photographs an|
000005e0  64 20 61 62 6f 75 74 20  74 68 65 20 73 61 6d 65  |d about the same|
000005f0  20 66 6f 72 20 67 72 61  70 68 69 63 73 2e 20 41  | for graphics. A|
00000600  67 61 69 6e 2c 20 42 54  50 43 0a 69 73 20 6d 75  |gain, BTPC.is mu|
00000610  63 68 20 66 61 73 74 65  72 2e 0a 0a 42 54 50 43  |ch faster...BTPC|
00000620  20 75 73 65 73 20 61 20  62 69 6e 61 72 79 20 70  | uses a binary p|
00000630  79 72 61 6d 69 64 2c 20  70 72 65 64 69 63 74 69  |yramid, predicti|
00000640  76 65 20 63 6f 64 69 6e  67 20 61 6e 64 20 48 75  |ve coding and Hu|
00000650  66 66 6d 61 6e 20 63 6f  64 69 6e 67 2e 20 4e 6f  |ffman coding. No|
00000660  20 70 61 72 74 20 6f 66  20 69 74 0a 69 73 20 63  | part of it.is c|
00000670  6f 76 65 72 65 64 20 62  79 20 70 61 74 65 6e 74  |overed by patent|
00000680  73 2e 20 43 2b 2b 20 73  6f 75 72 63 65 20 63 6f  |s. C++ source co|
00000690  64 65 20 69 73 20 61 76  61 69 6c 61 62 6c 65 20  |de is available |
000006a0  61 6e 64 20 6d 61 79 20  62 65 20 66 72 65 65 6c  |and may be freel|
000006b0  79 20 75 73 65 64 2e 0a  42 54 50 43 20 69 73 20  |y used..BTPC is |
000006c0  69 6e 68 65 72 65 6e 74  6c 79 20 70 72 6f 67 72  |inherently progr|
000006d0  65 73 73 69 76 65 2c 20  61 6e 64 20 61 20 73 74  |essive, and a st|
000006e0  72 61 69 67 68 74 66 6f  72 77 61 72 64 20 6d 6f  |raightforward mo|
000006f0  64 69 66 69 63 61 74 69  6f 6e 20 6f 66 20 74 68  |dification of th|
00000700  65 0a 64 65 63 6f 64 65  72 20 74 6f 20 77 72 69  |e.decoder to wri|
00000710  74 65 20 64 69 72 65 63  74 6c 79 20 74 6f 20 61  |te directly to a|
00000720  6e 20 6f 6e 2d 73 63 72  65 65 6e 20 70 69 63 74  |n on-screen pict|
00000730  75 72 65 20 62 75 66 66  65 72 20 61 6c 6c 6f 77  |ure buffer allow|
00000740  73 20 73 69 6d 70 6c 65  2c 0a 70 72 6f 67 72 65  |s simple,.progre|
00000750  73 73 69 76 65 2c 20 69  6d 61 67 65 20 72 65 63  |ssive, image rec|
00000760  6f 76 65 72 79 2e 0a 0a  57 68 61 74 27 73 20 6e  |overy...What's n|
00000770  65 77 20 69 6e 20 56 65  72 73 69 6f 6e 20 33 20  |ew in Version 3 |
00000780  2d 20 46 61 73 74 20 64  65 63 6f 64 69 6e 67 0a  |- Fast decoding.|
00000790  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 3d 3d 3d  |================|
*
000007b0  3d 3d 3d 3d 3d 3d 3d 0a  0a 49 6e 20 76 65 72 73  |=======..In vers|
000007c0  69 6f 6e 20 33 2c 20 42  54 50 43 20 64 65 63 6f  |ion 3, BTPC deco|
000007d0  64 65 20 74 69 6d 65 73  20 68 61 76 65 20 62 65  |de times have be|
000007e0  65 6e 20 68 61 6c 76 65  64 20 6f 76 65 72 20 74  |en halved over t|
000007f0  68 65 20 70 72 65 76 69  6f 75 73 20 76 65 72 73  |he previous vers|
00000800  69 6f 6e 0a 28 32 63 29  2e 20 56 65 72 73 69 6f  |ion.(2c). Versio|
00000810  6e 20 33 20 61 6c 73 6f  20 69 6d 70 72 6f 76 65  |n 3 also improve|
00000820  73 20 65 6e 63 6f 64 69  6e 67 20 73 70 65 65 64  |s encoding speed|
00000830  20 61 6e 64 20 67 69 76  65 73 20 73 6c 69 67 68  | and gives sligh|
00000840  74 6c 79 20 62 65 74 74  65 72 0a 63 6f 6d 70 72  |tly better.compr|
00000850  65 73 73 69 6f 6e 2e 0a  0a 42 54 50 43 20 64 65  |ession...BTPC de|
00000860  63 6f 64 69 6e 67 20 73  70 65 65 64 20 69 73 20  |coding speed is |
00000870  6e 6f 77 20 65 71 75 61  6c 20 74 6f 20 74 68 61  |now equal to tha|
00000880  74 20 6f 66 20 74 68 65  20 49 6e 64 65 70 65 6e  |t of the Indepen|
00000890  64 65 6e 74 20 4a 50 45  47 20 67 72 6f 75 70 20  |dent JPEG group |
000008a0  28 49 4a 47 29 0a 4a 50  45 47 20 64 65 63 6f 64  |(IJG).JPEG decod|
000008b0  65 72 2c 20 61 6e 64 20  6d 6f 72 65 20 74 68 61  |er, and more tha|
000008c0  6e 20 74 68 72 65 65 20  74 69 6d 65 73 20 66 61  |n three times fa|
000008d0  73 74 65 72 20 74 68 61  6e 20 69 74 73 20 6f 74  |ster than its ot|
000008e0  68 65 72 20 72 69 76 61  6c 73 2e 20 4f 66 0a 63  |her rivals. Of.c|
000008f0  6f 75 72 73 65 2c 20 69  6e 20 74 68 65 20 77 6f  |ourse, in the wo|
00000900  72 64 73 20 6f 66 20 74  68 65 20 49 4a 47 2c 20  |rds of the IJG, |
00000910  69 74 20 69 73 20 22 73  74 69 6c 6c 20 6e 6f 74  |it is "still not|
00000920  20 61 73 20 66 61 73 74  20 61 73 20 77 65 27 64  | as fast as we'd|
00000930  20 6c 69 6b 65 22 2e 0a  0a 57 68 65 72 65 20 74  | like"...Where t|
00000940  6f 20 66 69 6e 64 20 69  74 0a 3d 3d 3d 3d 3d 3d  |o find it.======|
00000950  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 0a 0a 44 6f 63 75  |==========..Docu|
00000960  6d 65 6e 74 61 74 69 6f  6e 20 6f 66 20 42 69 6e  |mentation of Bin|
00000970  61 72 79 20 54 72 65 65  20 50 72 65 64 69 63 74  |ary Tree Predict|
00000980  69 76 65 20 43 6f 64 69  6e 67 20 69 73 20 61 74  |ive Coding is at|
00000990  3a 0a 0a 68 74 74 70 3a  2f 2f 6d 6f 6e 65 74 2e  |:..http://monet.|
000009a0  75 77 61 74 65 72 6c 6f  6f 2e 63 61 2f 7e 6a 6f  |uwaterloo.ca/~jo|
000009b0  68 6e 2f 62 74 70 63 2e  68 74 6d 6c 0a 0a 53 6f  |hn/btpc.html..So|
000009c0  75 72 63 65 20 63 6f 64  65 20 69 73 20 61 74 3a  |urce code is at:|
000009d0  0a 0a 66 74 70 3a 2f 2f  6d 6f 6e 65 74 2e 75 77  |..ftp://monet.uw|
000009e0  61 74 65 72 6c 6f 6f 2e  63 61 2f 70 75 62 2f 6a  |aterloo.ca/pub/j|
000009f0  6f 68 6e 2f 62 74 70 63  76 33 2e 74 61 72 2e 5a  |ohn/btpcv3.tar.Z|
00000a00  0a 0a 54 6f 20 72 75 6e  0a 2d 2d 2d 2d 2d 2d 2d  |..To run.-------|
00000a10  0a 0a 20 20 20 20 20 20  20 20 63 62 74 70 63 20  |..        cbtpc |
00000a20  69 6e 70 75 74 5f 70 69  63 20 6f 75 74 70 75 74  |input_pic output|
00000a30  5f 66 69 6c 65 20 5b 71  75 61 6c 69 74 79 5d 0a  |_file [quality].|
00000a40  20 20 20 20 20 20 20 20  64 62 74 70 63 20 69 6e  |        dbtpc in|
00000a50  70 75 74 5f 66 69 6c 65  20 6f 75 74 70 75 74 5f  |put_file output_|
00000a60  70 69 63 0a 0a 54 68 65  20 6f 70 74 69 6f 6e 61  |pic..The optiona|
00000a70  6c 20 71 75 61 6c 69 74  79 20 70 61 72 61 6d 65  |l quality parame|
00000a80  74 65 72 20 69 73 20 61  20 6e 75 6d 62 65 72 20  |ter is a number |
00000a90  62 65 74 77 65 65 6e 20  30 20 61 6e 64 20 31 30  |between 0 and 10|
00000aa0  30 2e 20 44 65 66 61 75  6c 74 20 69 73 20 37 35  |0. Default is 75|
00000ab0  2e 0a 51 75 61 6c 69 74  79 20 76 61 6c 75 65 73  |..Quality values|
00000ac0  20 72 6f 75 67 68 6c 79  20 61 70 70 72 6f 78 69  | roughly approxi|
00000ad0  6d 61 74 65 20 4a 50 45  47 20 71 75 61 6c 69 74  |mate JPEG qualit|
00000ae0  79 20 76 61 6c 75 65 73  2c 20 62 75 74 20 31 30  |y values, but 10|
00000af0  30 20 69 73 20 6c 6f 73  73 6c 65 73 73 2e 0a 0a  |0 is lossless...|
00000b00  54 68 69 73 20 76 65 72  73 69 6f 6e 20 6f 6e 6c  |This version onl|
00000b10  79 20 72 65 61 64 73 20  61 6e 64 20 77 72 69 74  |y reads and writ|
00000b20  65 73 20 50 47 4d 20 61  6e 64 20 50 50 4d 20 72  |es PGM and PPM r|
00000b30  61 77 20 66 6f 72 6d 61  74 20 66 69 6c 65 73 20  |aw format files |
00000b40  28 6d 61 67 69 63 20 6e  75 6d 62 65 72 0a 22 50  |(magic number."P|
00000b50  35 22 20 6f 72 20 22 50  36 22 29 2e 0a 0a 43 6f  |5" or "P6")...Co|
00000b60  6d 70 61 72 69 73 6f 6e  73 20 62 65 74 77 65 65  |mparisons betwee|
00000b70  6e 20 42 54 50 43 2c 20  4a 50 45 47 20 61 6e 64  |n BTPC, JPEG and|
00000b80  20 74 68 65 20 53 74 61  74 65 20 6f 66 20 74 68  | the State of th|
00000b90  65 20 41 72 74 0a 3d 3d  3d 3d 3d 3d 3d 3d 3d 3d  |e Art.==========|
00000ba0  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 3d 3d 3d  |================|
*
00000bc0  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 0a 0a 49  |=============..I|
00000bd0  20 68 61 76 65 20 63 6f  6d 70 61 72 65 64 20 42  | have compared B|
00000be0  54 50 43 20 77 69 74 68  20 74 68 65 20 63 75 72  |TPC with the cur|
00000bf0  72 65 6e 74 20 73 74 61  6e 64 61 72 64 2c 20 4a  |rent standard, J|
00000c00  50 45 47 2c 20 61 6e 64  20 77 68 61 74 20 49 20  |PEG, and what I |
00000c10  63 6f 6e 73 69 64 65 72  20 74 6f 20 62 65 0a 74  |consider to be.t|
00000c20  68 65 20 73 74 61 74 65  20 6f 66 20 74 68 65 20  |he state of the |
00000c30  61 72 74 20 69 6e 20 73  74 69 6c 6c 2d 69 6d 61  |art in still-ima|
00000c40  67 65 20 63 6f 6d 70 72  65 73 73 69 6f 6e 2e 20  |ge compression. |
00000c50  46 6f 72 20 6c 6f 73 73  6c 65 73 73 20 63 6f 64  |For lossless cod|
00000c60  69 6e 67 20 49 20 68 61  76 65 0a 63 6f 6d 70 61  |ing I have.compa|
00000c70  72 65 64 20 61 67 61 69  6e 73 74 20 57 75 27 73  |red against Wu's|
00000c80  20 43 41 4c 49 43 20 73  79 73 74 65 6d 2c 20 77  | CALIC system, w|
00000c90  68 69 63 68 20 68 61 73  20 62 65 65 6e 20 70 72  |hich has been pr|
00000ca0  6f 70 6f 73 65 64 20 66  6f 72 20 74 68 65 20 6c  |oposed for the l|
00000cb0  6f 73 73 6c 65 73 73 0a  6d 6f 64 65 20 6f 66 20  |ossless.mode of |
00000cc0  4a 50 45 47 2c 20 61 6e  64 20 68 61 73 20 64 6f  |JPEG, and has do|
00000cd0  6e 65 20 77 65 6c 6c 20  69 6e 20 74 68 65 20 66  |ne well in the f|
00000ce0  69 72 73 74 20 72 6f 75  6e 64 20 6f 66 20 74 65  |irst round of te|
00000cf0  73 74 73 20 66 6f 72 20  74 68 61 74 20 73 74 61  |sts for that sta|
00000d00  6e 64 61 72 64 2e 0a 46  6f 72 20 6c 6f 73 73 79  |ndard..For lossy|
00000d10  20 63 6f 64 69 6e 67 20  49 20 68 61 76 65 20 63  | coding I have c|
00000d20  6f 6d 70 61 72 65 64 20  61 67 61 69 6e 73 74 20  |ompared against |
00000d30  53 61 69 64 20 61 6e 64  20 50 65 61 72 6c 6d 61  |Said and Pearlma|
00000d40  6e 27 73 20 77 61 76 65  6c 65 74 2d 62 61 73 65  |n's wavelet-base|
00000d50  64 0a 65 6d 62 65 64 64  65 64 20 63 6f 64 65 72  |d.embedded coder|
00000d60  20 28 62 61 73 65 64 20  6f 6e 20 53 68 61 70 69  | (based on Shapi|
00000d70  72 6f 27 73 20 7a 65 72  6f 74 72 65 65 20 61 70  |ro's zerotree ap|
00000d80  70 72 6f 61 63 68 29 2e  20 42 6f 74 68 20 43 41  |proach). Both CA|
00000d90  4c 49 43 20 61 6e 64 20  74 68 65 20 53 61 69 64  |LIC and the Said|
00000da0  0a 61 6e 64 20 50 65 61  72 6c 6d 61 6e 20 28 68  |.and Pearlman (h|
00000db0  65 6e 63 65 66 6f 72 74  68 20 53 26 50 29 20 63  |enceforth S&P) c|
00000dc0  6f 64 65 72 20 65 78 69  73 74 20 69 6e 20 73 6c  |oder exist in sl|
00000dd0  6f 77 20 61 6e 64 20 66  61 73 74 20 76 65 72 73  |ow and fast vers|
00000de0  69 6f 6e 73 2e 20 49 6e  20 65 61 63 68 0a 63 61  |ions. In each.ca|
00000df0  73 65 20 74 68 65 20 73  6c 6f 77 20 76 65 72 73  |se the slow vers|
00000e00  69 6f 6e 20 75 73 65 73  20 61 6e 20 61 72 69 74  |ion uses an arit|
00000e10  68 6d 65 74 69 63 20 63  6f 64 65 72 20 74 6f 20  |hmetic coder to |
00000e20  69 6d 70 72 6f 76 65 20  63 6f 6d 70 72 65 73 73  |improve compress|
00000e30  69 6f 6e 2e 20 42 54 50  43 20 61 6e 64 0a 4a 50  |ion. BTPC and.JP|
00000e40  45 47 20 63 61 6e 20 63  6f 6d 70 72 65 73 73 20  |EG can compress |
00000e50  63 6f 6c 6f 72 20 70 69  63 74 75 72 65 73 2c 20  |color pictures, |
00000e60  62 75 74 20 53 26 50 20  61 6e 64 20 43 41 4c 49  |but S&P and CALI|
00000e70  43 20 63 61 6e 20 6e 6f  74 2c 20 73 6f 20 74 68  |C can not, so th|
00000e80  65 20 72 65 73 75 6c 74  73 0a 68 65 72 65 20 72  |e results.here r|
00000e90  65 66 65 72 20 6f 6e 6c  79 20 74 6f 20 67 72 61  |efer only to gra|
00000ea0  79 73 63 61 6c 65 20 69  6d 61 67 65 73 2e 0a 0a  |yscale images...|
00000eb0  49 20 68 61 76 65 20 75  73 65 64 20 61 6e 20 65  |I have used an e|
00000ec0  78 74 65 6e 73 69 76 65  20 73 65 74 20 6f 66 20  |xtensive set of |
00000ed0  74 65 73 74 20 69 6d 61  67 65 73 2c 20 6d 6f 73  |test images, mos|
00000ee0  74 20 6f 66 20 77 68 69  63 68 20 61 72 65 20 61  |t of which are a|
00000ef0  76 61 69 6c 61 62 6c 65  20 61 74 0a 6c 69 6e 6b  |vailable at.link|
00000f00  73 2e 75 77 61 74 65 72  6c 6f 6f 2e 63 61 2e 20  |s.uwaterloo.ca. |
00000f10  48 65 72 65 20 49 20 67  69 76 65 20 72 65 70 72  |Here I give repr|
00000f20  65 73 65 6e 74 61 74 69  76 65 20 72 65 73 75 6c  |esentative resul|
00000f30  74 73 20 66 72 6f 6d 20  74 68 61 74 20 74 65 73  |ts from that tes|
00000f40  74 69 6e 67 2e 20 54 68  65 0a 70 72 6f 67 72 61  |ting. The.progra|
00000f50  6d 73 20 77 65 72 65 20  72 75 6e 20 6f 6e 20 61  |ms were run on a|
00000f60  20 53 70 61 72 63 53 74  61 74 69 6f 6e 3b 20 74  | SparcStation; t|
00000f70  69 6d 65 73 20 61 72 65  20 69 6e 20 73 65 63 6f  |imes are in seco|
00000f80  6e 64 73 2e 20 49 20 68  61 76 65 20 69 6e 63 6c  |nds. I have incl|
00000f90  75 64 65 64 20 6f 6e 6c  79 0a 64 65 63 6f 64 69  |uded only.decodi|
00000fa0  6e 67 20 74 69 6d 65 20  2d 20 66 6f 72 20 61 6c  |ng time - for al|
00000fb0  6c 20 6d 65 74 68 6f 64  73 20 65 6e 63 6f 64 69  |l methods encodi|
00000fc0  6e 67 20 74 69 6d 65 20  69 73 20 6c 6f 6e 67 65  |ng time is longe|
00000fd0  72 2e 20 49 6e 64 65 65  64 2c 20 66 6f 72 20 42  |r. Indeed, for B|
00000fe0  54 50 43 2c 20 49 0a 68  61 76 65 20 6e 6f 74 20  |TPC, I.have not |
00000ff0  74 72 69 65 64 20 74 6f  20 6f 70 74 69 6d 69 7a  |tried to optimiz|
00001000  65 20 74 68 65 20 65 6e  63 6f 64 65 72 20 61 74  |e the encoder at|
00001010  20 61 6c 6c 2c 20 73 6f  20 69 74 20 63 75 72 72  | all, so it curr|
00001020  65 6e 74 6c 79 20 74 61  6b 65 73 20 62 65 74 77  |ently takes betw|
00001030  65 65 6e 0a 74 77 6f 20  61 6e 64 20 74 68 72 65  |een.two and thre|
00001040  65 20 74 69 6d 65 73 20  61 73 20 6c 6f 6e 67 20  |e times as long |
00001050  61 73 20 74 68 65 20 64  65 63 6f 64 65 72 20 74  |as the decoder t|
00001060  6f 20 72 75 6e 2e 20 54  68 65 20 72 65 61 73 6f  |o run. The reaso|
00001070  6e 20 66 6f 72 20 6d 79  20 6e 65 67 6c 65 63 74  |n for my neglect|
00001080  20 6f 66 0a 65 6e 63 6f  64 69 6e 67 20 73 70 65  | of.encoding spe|
00001090  65 64 20 69 73 20 74 68  61 74 20 66 61 73 74 20  |ed is that fast |
000010a0  64 65 63 6f 64 69 6e 67  20 69 73 20 6d 6f 72 65  |decoding is more|
000010b0  20 69 6d 70 6f 72 74 61  6e 74 20 69 6e 20 74 68  | important in th|
000010c0  65 20 61 70 70 6c 69 63  61 74 69 6f 6e 73 20 49  |e applications I|
000010d0  20 61 6d 0a 69 6e 74 65  72 65 73 74 65 64 20 69  | am.interested i|
000010e0  6e 20 28 65 2e 67 2e 20  69 6d 61 67 65 20 64 61  |n (e.g. image da|
000010f0  74 61 62 61 73 65 73 29  2e 20 4e 6f 6e 65 74 68  |tabases). Noneth|
00001100  65 6c 65 73 73 2c 20 42  54 50 43 20 76 65 72 73  |eless, BTPC vers|
00001110  69 6f 6e 20 33 20 65 6e  63 6f 64 69 6e 67 20 69  |ion 3 encoding i|
00001120  73 0a 73 75 62 73 74 61  6e 74 69 61 6c 6c 79 20  |s.substantially |
00001130  66 61 73 74 65 72 20 74  68 61 6e 20 43 41 4c 49  |faster than CALI|
00001140  43 20 61 6e 64 20 53 26  50 2e 0a 0a 53 6f 6d 65  |C and S&P...Some|
00001150  20 63 61 76 65 61 74 73  0a 2d 2d 2d 2d 2d 2d 2d  | caveats.-------|
00001160  2d 2d 2d 2d 2d 0a 0a 49  20 68 61 76 65 20 63 68  |-----..I have ch|
00001170  6f 73 65 6e 20 43 41 4c  49 43 20 61 6e 64 20 53  |osen CALIC and S|
00001180  26 50 20 62 65 63 61 75  73 65 20 49 20 62 65 6c  |&P because I bel|
00001190  69 65 76 65 20 74 68 65  6d 20 74 6f 20 62 65 20  |ieve them to be |
000011a0  74 68 65 20 62 65 73 74  20 74 68 61 74 20 69 73  |the best that is|
000011b0  0a 63 75 72 72 65 6e 74  6c 79 20 62 65 69 6e 67  |.currently being|
000011c0  20 61 63 68 69 65 76 65  64 2e 20 50 6f 73 73 69  | achieved. Possi|
000011d0  62 6c 79 20 73 6f 6d 65  20 63 6f 6d 6d 65 72 63  |bly some commerc|
000011e0  69 61 6c 20 70 72 6f 64  75 63 74 73 20 64 6f 20  |ial products do |
000011f0  62 65 74 74 65 72 2e 20  49 20 77 6f 75 6c 64 0a  |better. I would.|
00001200  6c 69 6b 65 20 74 6f 20  68 65 61 72 20 61 62 6f  |like to hear abo|
00001210  75 74 20 61 6e 79 20 74  68 61 74 20 61 72 65 20  |ut any that are |
00001220  61 76 61 69 6c 61 62 6c  65 20 66 6f 72 20 65 76  |available for ev|
00001230  61 6c 75 61 74 69 6f 6e  2e 0a 0a 48 61 76 69 6e  |aluation...Havin|
00001240  67 20 73 61 69 64 20 74  68 69 73 2c 20 70 6c 65  |g said this, ple|
00001250  61 73 65 20 62 65 61 72  20 69 6e 20 6d 69 6e 64  |ase bear in mind|
00001260  20 74 68 61 74 20 42 54  50 43 20 69 73 20 6e 6f  | that BTPC is no|
00001270  74 20 69 6e 74 65 6e 64  65 64 20 74 6f 20 62 65  |t intended to be|
00001280  61 74 20 73 74 61 74 65  0a 6f 66 20 74 68 65 20  |at state.of the |
00001290  61 72 74 20 73 79 73 74  65 6d 73 20 6c 69 6b 65  |art systems like|
000012a0  20 43 41 4c 49 43 20 61  6e 64 20 53 26 50 20 69  | CALIC and S&P i|
000012b0  6e 20 74 68 65 69 72 20  61 72 65 61 73 20 6f 66  |n their areas of|
000012c0  20 73 74 72 65 6e 67 74  68 2e 20 52 61 74 68 65  | strength. Rathe|
000012d0  72 2c 20 69 74 20 69 73  0a 73 75 70 70 6f 73 65  |r, it is.suppose|
000012e0  64 20 74 6f 20 62 65 20  22 67 65 6e 65 72 61 6c  |d to be "general|
000012f0  20 70 75 72 70 6f 73 65  22 2c 20 77 68 69 63 68  | purpose", which|
00001300  20 6d 65 61 6e 73 20 69  74 20 73 68 6f 75 6c 64  | means it should|
00001310  20 64 6f 20 72 65 61 73  6f 6e 61 62 6c 79 20 77  | do reasonably w|
00001320  65 6c 6c 20 6f 76 65 72  0a 61 20 77 69 64 65 20  |ell over.a wide |
00001330  72 61 6e 67 65 20 6f 66  20 70 6f 73 73 69 62 6c  |range of possibl|
00001340  65 20 69 6e 70 75 74 73  2c 20 61 6e 64 20 73 68  |e inputs, and sh|
00001350  6f 75 6c 64 20 72 75 6e  20 66 61 73 74 2e 20 54  |ould run fast. T|
00001360  65 73 74 69 6e 67 20 61  67 61 69 6e 73 74 20 74  |esting against t|
00001370  68 65 20 73 74 61 74 65  0a 6f 66 20 74 68 65 20  |he state.of the |
00001380  61 72 74 20 69 73 20 61  20 6b 69 6e 64 20 6f 66  |art is a kind of|
00001390  20 22 77 6f 72 73 74 20  63 61 73 65 22 20 63 6f  | "worst case" co|
000013a0  6d 70 61 72 69 73 6f 6e  2c 20 73 6f 20 62 65 20  |mparison, so be |
000013b0  77 61 72 6e 65 64 21 0a  0a 4f 6e 65 20 6f 66 20  |warned!..One of |
000013c0  42 54 50 43 27 73 20 64  65 73 69 67 6e 20 63 72  |BTPC's design cr|
000013d0  69 74 65 72 69 61 20 77  61 73 20 64 65 63 6f 64  |iteria was decod|
000013e0  69 6e 67 20 73 70 65 65  64 2e 20 49 20 61 6d 20  |ing speed. I am |
000013f0  6e 6f 74 20 73 75 72 65  20 74 68 61 74 20 74 68  |not sure that th|
00001400  69 73 20 77 61 73 0a 74  68 65 20 63 61 73 65 20  |is was.the case |
00001410  66 6f 72 20 43 41 4c 49  43 20 61 6e 64 20 53 26  |for CALIC and S&|
00001420  50 2e 20 48 6f 77 65 76  65 72 2c 20 62 6f 74 68  |P. However, both|
00001430  20 57 75 2c 20 61 6e 64  20 53 61 69 64 20 61 6e  | Wu, and Said an|
00001440  64 20 50 65 61 72 6c 6d  61 6e 20 68 61 76 65 20  |d Pearlman have |
00001450  61 72 67 75 65 64 0a 74  68 61 74 20 74 68 65 69  |argued.that thei|
00001460  72 20 66 61 73 74 20 76  65 72 73 69 6f 6e 73 20  |r fast versions |
00001470  61 72 65 20 66 61 73 74  20 28 21 29 20 73 6f 20  |are fast (!) so |
00001480  49 27 76 65 20 63 6f 6e  73 69 64 65 72 65 64 20  |I've considered |
00001490  69 74 20 66 61 69 72 20  67 61 6d 65 20 74 6f 20  |it fair game to |
000014a0  6d 61 6b 65 0a 74 68 65  6d 20 63 6f 6d 70 65 74  |make.them compet|
000014b0  65 20 69 6e 20 61 20 74  69 6d 69 6e 67 20 63 6f  |e in a timing co|
000014c0  6d 70 61 72 69 73 6f 6e  2e 0a 0a 41 20 63 6f 6e  |mparison...A con|
000014d0  73 65 71 75 65 6e 63 65  20 6f 66 20 64 65 73 69  |sequence of desi|
000014e0  67 6e 69 6e 67 20 42 54  50 43 20 61 73 20 61 20  |gning BTPC as a |
000014f0  22 67 65 6e 65 72 61 6c  2d 70 75 72 70 6f 73 65  |"general-purpose|
00001500  22 20 63 6f 64 65 72 20  69 73 20 74 68 61 74 20  |" coder is that |
00001510  74 68 65 20 6f 6e 6c 79  0a 64 69 66 66 65 72 65  |the only.differe|
00001520  6e 63 65 20 62 65 74 77  65 65 6e 20 6c 6f 73 73  |nce between loss|
00001530  6c 65 73 73 20 61 6e 64  20 6c 6f 73 73 79 20 63  |less and lossy c|
00001540  6f 64 69 6e 67 20 69 73  20 74 68 65 20 71 75 61  |oding is the qua|
00001550  6e 74 69 7a 65 72 20 73  74 65 70 20 73 69 7a 65  |ntizer step size|
00001560  2e 20 46 6f 72 0a 62 65  74 74 65 72 20 6f 72 20  |. For.better or |
00001570  66 6f 72 20 77 6f 72 73  65 2c 20 49 20 68 61 76  |for worse, I hav|
00001580  65 20 72 65 73 69 73 74  65 64 20 74 68 65 20 69  |e resisted the i|
00001590  64 65 61 20 6f 66 20 61  20 73 65 70 61 72 61 74  |dea of a separat|
000015a0  65 20 6c 6f 73 73 6c 65  73 73 20 22 6d 6f 64 65  |e lossless "mode|
000015b0  22 2c 0a 61 6e 64 20 49  20 61 6d 20 73 74 69 6c  |",.and I am stil|
000015c0  6c 20 6e 6f 74 20 73 75  72 65 20 6f 66 20 74 68  |l not sure of th|
000015d0  65 20 77 69 73 64 6f 6d  20 6f 66 20 74 68 69 73  |e wisdom of this|
000015e0  2e 0a 0a 31 2e 20 20 20  20 20 54 79 70 69 63 61  |...1.     Typica|
000015f0  6c 20 66 69 67 75 72 65  73 20 66 6f 72 20 70 68  |l figures for ph|
00001600  6f 74 6f 67 72 61 70 68  69 63 20 69 6d 61 67 65  |otographic image|
00001610  73 0a 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |s.--------------|
00001620  2d 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |----------------|
*
00001640  2d 0a 0a 48 65 72 65 20  61 72 65 20 74 77 6f 20  |-..Here are two |
00001650  73 65 74 73 20 6f 66 20  74 79 70 69 63 61 6c 20  |sets of typical |
00001660  72 65 73 75 6c 74 73 20  66 6f 72 20 63 6f 64 69  |results for codi|
00001670  6e 67 20 70 68 6f 74 6f  67 72 61 70 68 69 63 20  |ng photographic |
00001680  69 6d 61 67 65 73 2e 20  54 68 65 73 65 20 73 68  |images. These sh|
00001690  6f 77 0a 74 68 65 20 67  65 6e 65 72 61 6c 20 74  |ow.the general t|
000016a0  72 65 6e 64 20 66 6f 72  20 70 68 6f 74 6f 73 20  |rend for photos |
000016b0  77 69 74 68 20 42 54 50  43 20 66 61 6c 6c 69 6e  |with BTPC fallin|
000016c0  67 20 62 65 74 77 65 65  6e 20 4a 50 45 47 20 61  |g between JPEG a|
000016d0  6e 64 20 53 26 50 2f 43  41 4c 49 43 20 66 6f 72  |nd S&P/CALIC for|
000016e0  0a 63 6f 6d 70 72 65 73  73 69 6f 6e 20 65 66 66  |.compression eff|
000016f0  69 63 69 65 6e 63 79 2c  20 61 6e 64 20 42 54 50  |iciency, and BTP|
00001700  43 20 61 6e 64 20 4a 50  45 47 20 62 65 69 6e 67  |C and JPEG being|
00001710  20 6d 75 63 68 20 66 61  73 74 65 72 20 74 68 61  | much faster tha|
00001720  6e 20 74 68 65 20 66 61  73 74 0a 76 65 72 73 69  |n the fast.versi|
00001730  6f 6e 73 20 6f 66 20 53  26 50 20 61 6e 64 20 43  |ons of S&P and C|
00001740  41 4c 49 43 2e 0a 0a 35  31 32 20 78 20 35 31 32  |ALIC...512 x 512|
00001750  20 4c 65 6e 6e 61 3a 0a  0a 4c 6f 73 73 79 20 63  | Lenna:..Lossy c|
00001760  6f 64 69 6e 67 20 61 74  20 50 53 4e 52 20 33 36  |oding at PSNR 36|
00001770  2e 39 20 64 42 20 28 3d  20 4a 50 45 47 20 63 6f  |.9 dB (= JPEG co|
00001780  64 65 64 20 77 69 74 68  20 51 20 6f 66 20 37 35  |ded with Q of 75|
00001790  29 3a 0a 0a 53 63 68 65  6d 65 20 20 20 20 20 20  |):..Scheme      |
000017a0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
000017b0  20 20 20 20 62 70 70 20  20 20 20 20 20 20 20 20  |    bpp         |
000017c0  20 20 20 20 44 65 63 6f  64 65 20 74 69 6d 65 0a  |    Decode time.|
000017d0  2d 2d 2d 2d 2d 2d 20 20  20 20 20 20 20 20 20 20  |------          |
000017e0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
000017f0  2d 2d 2d 20 20 20 20 20  20 20 20 20 20 20 20 20  |---             |
00001800  2d 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 0a 0a 4a 50 45  |-----------..JPE|
00001810  47 20 28 49 4a 47 20 76  20 36 29 20 20 20 20 20  |G (IJG v 6)     |
00001820  20 20 20 20 20 20 20 20  20 20 20 20 20 31 2e 30  |             1.0|
00001830  35 20 20 20 20 20 20 20  20 20 20 20 20 31 2e 34  |5            1.4|
00001840  0a 42 54 50 43 33 20 20  20 20 20 20 20 20 20 20  |.BTPC3          |
00001850  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001860  20 30 2e 39 33 20 20 20  20 20 20 20 20 20 20 20  | 0.93           |
00001870  20 31 2e 34 0a 53 26 50  20 66 61 73 74 20 20 20  | 1.4.S&P fast   |
00001880  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001890  20 20 20 20 20 30 2e 36  36 20 20 20 20 20 20 20  |     0.66       |
000018a0  20 20 20 20 20 35 2e 32  0a 53 26 50 20 73 6c 6f  |     5.2.S&P slo|
000018b0  77 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |w               |
000018c0  20 20 20 20 20 20 20 20  20 30 2e 36 30 20 20 20  |         0.60   |
000018d0  20 20 20 20 20 20 20 20  20 38 2e 39 0a 0a 4c 6f  |         8.9..Lo|
000018e0  73 73 6c 65 73 73 20 63  6f 64 69 6e 67 3a 0a 0a  |ssless coding:..|
000018f0  53 63 68 65 6d 65 20 20  20 20 20 20 20 20 20 20  |Scheme          |
00001900  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001910  62 70 70 20 20 20 20 20  20 20 20 20 20 20 20 20  |bpp             |
00001920  44 65 63 6f 64 65 20 74  69 6d 65 0a 2d 2d 2d 2d  |Decode time.----|
00001930  2d 2d 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |--              |
00001940  20 20 20 20 20 20 20 20  20 20 20 20 2d 2d 2d 20  |            --- |
00001950  20 20 20 20 20 20 20 20  20 20 20 20 2d 2d 2d 2d  |            ----|
00001960  2d 2d 2d 2d 2d 2d 2d 0a  0a 42 54 50 43 33 20 20  |-------..BTPC3  |
00001970  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001980  20 20 20 20 20 20 20 20  20 34 2e 36 36 20 20 20  |         4.66   |
00001990  20 20 20 20 20 20 20 20  20 32 2e 39 0a 43 41 4c  |         2.9.CAL|
000019a0  49 43 20 66 61 73 74 20  20 20 20 20 20 20 20 20  |IC fast         |
000019b0  20 20 20 20 20 20 20 20  20 20 20 20 20 34 2e 34  |             4.4|
000019c0  30 20 20 20 20 20 20 20  20 20 20 20 20 31 30 2e  |0            10.|
000019d0  30 0a 43 41 4c 49 43 20  73 6c 6f 77 20 20 20 20  |0.CALIC slow    |
000019e0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
000019f0  20 20 34 2e 33 33 20 20  20 20 20 20 20 20 20 20  |  4.33          |
00001a00  20 20 32 34 2e 37 0a 0a  32 35 36 20 78 20 32 35  |  24.7..256 x 25|
00001a10  36 20 43 61 6d 65 72 61  6d 61 6e 3a 0a 0a 4c 6f  |6 Cameraman:..Lo|
00001a20  73 73 79 20 63 6f 64 69  6e 67 20 61 74 20 50 53  |ssy coding at PS|
00001a30  4e 52 20 33 34 2e 37 20  64 42 20 28 3d 20 4a 50  |NR 34.7 dB (= JP|
00001a40  45 47 20 63 6f 64 65 64  20 77 69 74 68 20 51 20  |EG coded with Q |
00001a50  6f 66 20 37 35 29 3a 0a  0a 53 63 68 65 6d 65 20  |of 75):..Scheme |
00001a60  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001a70  20 20 20 20 20 20 20 20  20 62 70 70 20 20 20 20  |         bpp    |
00001a80  20 20 20 20 20 20 20 20  20 44 65 63 6f 64 65 20  |         Decode |
00001a90  74 69 6d 65 0a 2d 2d 2d  2d 2d 2d 20 20 20 20 20  |time.------     |
00001aa0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001ab0  20 20 20 20 20 2d 2d 2d  20 20 20 20 20 20 20 20  |     ---        |
00001ac0  20 20 20 20 20 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |     -----------|
00001ad0  0a 0a 4a 50 45 47 20 28  49 4a 47 20 76 20 36 29  |..JPEG (IJG v 6)|
00001ae0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001af0  20 20 31 2e 33 34 20 20  20 20 20 20 20 20 20 20  |  1.34          |
00001b00  20 20 30 2e 34 0a 42 54  50 43 33 20 20 20 20 20  |  0.4.BTPC3     |
00001b10  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001b20  20 20 20 20 20 20 30 2e  39 35 20 20 20 20 20 20  |      0.95      |
00001b30  20 20 20 20 20 20 30 2e  34 0a 53 26 50 20 66 61  |      0.4.S&P fa|
00001b40  73 74 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |st              |
00001b50  20 20 20 20 20 20 20 20  20 20 30 2e 39 31 20 20  |          0.91  |
00001b60  20 20 20 20 20 20 20 20  20 20 31 2e 33 0a 53 26  |          1.3.S&|
00001b70  50 20 73 6c 6f 77 20 20  20 20 20 20 20 20 20 20  |P slow          |
00001b80  20 20 20 20 20 20 20 20  20 20 20 20 20 20 30 2e  |              0.|
00001b90  38 32 20 20 20 20 20 20  20 20 20 20 20 20 32 2e  |82            2.|
00001ba0  35 0a 0a 4c 6f 73 73 6c  65 73 73 20 63 6f 64 69  |5..Lossless codi|
00001bb0  6e 67 3a 0a 0a 53 63 68  65 6d 65 20 20 20 20 20  |ng:..Scheme     |
00001bc0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001bd0  20 20 20 20 20 62 70 70  20 20 20 20 20 20 20 20  |     bpp        |
00001be0  20 20 20 20 20 44 65 63  6f 64 65 20 74 69 6d 65  |     Decode time|
00001bf0  0a 2d 2d 2d 2d 2d 2d 20  20 20 20 20 20 20 20 20  |.------         |
00001c00  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001c10  20 2d 2d 2d 20 20 20 20  20 20 20 20 20 20 20 20  | ---            |
00001c20  20 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 0a 0a 42 54  | -----------..BT|
00001c30  50 43 33 20 20 20 20 20  20 20 20 20 20 20 20 20  |PC3             |
00001c40  20 20 20 20 20 20 20 20  20 20 20 20 20 20 35 2e  |              5.|
00001c50  30 32 20 20 20 20 20 20  20 20 20 20 20 20 30 2e  |02            0.|
00001c60  37 0a 43 41 4c 49 43 20  66 61 73 74 20 20 20 20  |7.CALIC fast    |
00001c70  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001c80  20 20 34 2e 33 34 20 20  20 20 20 20 20 20 20 20  |  4.34          |
00001c90  20 20 32 2e 34 0a 43 41  4c 49 43 20 73 6c 6f 77  |  2.4.CALIC slow|
00001ca0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001cb0  20 20 20 20 20 20 34 2e  33 31 20 20 20 20 20 20  |      4.31      |
00001cc0  20 20 20 20 20 20 36 2e  32 0a 0a 32 2e 20 20 20  |      6.2..2.   |
00001cd0  20 20 42 54 50 43 27 73  20 77 6f 72 73 74 20 63  |  BTPC's worst c|
00001ce0  61 73 65 0a 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |ase.------------|
00001cf0  2d 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 0a 0a 49  |-------------..I|
00001d00  6e 20 6d 79 20 74 65 73  74 20 73 75 69 74 65 2c  |n my test suite,|
00001d10  20 42 54 50 43 27 73 20  77 6f 72 73 74 20 63 61  | BTPC's worst ca|
00001d20  73 65 20 77 61 73 20 22  61 63 68 69 65 76 65 64  |se was "achieved|
00001d30  22 20 6f 6e 20 74 68 65  20 35 31 32 20 78 20 35  |" on the 512 x 5|
00001d40  31 32 0a 70 68 6f 74 6f  67 72 61 70 68 69 63 20  |12.photographic |
00001d50  69 6d 61 67 65 20 22 42  61 72 62 61 72 61 22 20  |image "Barbara" |
00001d60  77 68 69 63 68 20 69 6e  63 6c 75 64 65 73 20 6c  |which includes l|
00001d70  61 72 67 65 20 61 72 65  61 73 20 6f 66 20 73 74  |arge areas of st|
00001d80  72 69 70 65 73 2e 20 54  68 69 73 20 69 73 20 74  |ripes. This is t|
00001d90  68 65 0a 6f 6e 6c 79 20  70 69 63 74 75 72 65 20  |he.only picture |
00001da0  66 6f 72 20 77 68 69 63  68 20 42 54 50 43 20 70  |for which BTPC p|
00001db0  65 72 66 6f 72 6d 65 64  20 77 6f 72 73 65 20 74  |erformed worse t|
00001dc0  68 61 6e 20 4a 50 45 47  20 28 61 6e 64 20 74 68  |han JPEG (and th|
00001dd0  65 6e 20 6f 6e 6c 79 0a  6d 61 72 67 69 6e 61 6c  |en only.marginal|
00001de0  6c 79 29 2e 20 54 68 65  20 72 65 61 73 6f 6e 20  |ly). The reason |
00001df0  69 73 20 74 68 61 74 20  4a 50 45 47 27 73 20 44  |is that JPEG's D|
00001e00  43 54 20 69 73 20 61 62  6c 65 20 74 6f 20 65 78  |CT is able to ex|
00001e10  70 6c 6f 69 74 20 74 68  65 20 72 65 67 75 6c 61  |ploit the regula|
00001e20  72 0a 73 70 61 74 69 61  6c 20 66 72 65 71 75 65  |r.spatial freque|
00001e30  6e 63 79 20 73 74 72 75  63 74 75 72 65 20 6f 66  |ncy structure of|
00001e40  20 74 68 65 20 73 74 72  69 70 65 73 2e 20 42 54  | the stripes. BT|
00001e50  50 43 20 63 61 6e 6e 6f  74 20 64 6f 20 74 68 69  |PC cannot do thi|
00001e60  73 2e 20 28 4f 6e 20 74  68 65 20 6f 74 68 65 72  |s. (On the other|
00001e70  0a 68 61 6e 64 2c 20 42  54 50 43 20 63 6c 65 61  |.hand, BTPC clea|
00001e80  72 6c 79 20 6f 75 74 70  65 72 66 6f 72 6d 73 20  |rly outperforms |
00001e90  4a 50 45 47 20 6f 6e 20  74 65 78 74 75 72 65 64  |JPEG on textured|
00001ea0  20 70 69 63 74 75 72 65  73 20 77 69 74 68 20 6c  | pictures with l|
00001eb0  65 73 73 20 72 65 67 75  6c 61 72 0a 73 70 61 74  |ess regular.spat|
00001ec0  69 61 6c 20 73 74 72 75  63 74 75 72 65 20 2d 20  |ial structure - |
00001ed0  65 2e 67 2e 20 47 6f 6c  64 20 48 69 6c 6c 2e 29  |e.g. Gold Hill.)|
00001ee0  0a 0a 35 31 32 20 78 20  35 31 32 20 42 61 72 62  |..512 x 512 Barb|
00001ef0  61 72 61 3a 0a 0a 4c 6f  73 73 79 20 63 6f 64 69  |ara:..Lossy codi|
00001f00  6e 67 20 61 74 20 50 53  4e 52 20 33 36 2e 32 20  |ng at PSNR 36.2 |
00001f10  64 42 20 28 3d 20 4a 50  45 47 20 63 6f 64 65 64  |dB (= JPEG coded|
00001f20  20 77 69 74 68 20 51 20  6f 66 20 37 35 29 3a 0a  | with Q of 75):.|
00001f30  0a 53 63 68 65 6d 65 20  20 20 20 20 20 20 20 20  |.Scheme         |
00001f40  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00001f50  20 62 70 70 20 20 20 20  20 20 20 20 20 20 20 20  | bpp            |
00001f60  20 44 65 63 6f 64 65 20  74 69 6d 65 0a 2d 2d 2d  | Decode time.---|
00001f70  2d 2d 2d 20 20 20 20 20  20 20 20 20 20 20 20 20  |---             |
00001f80  20 20 20 20 20 20 20 20  20 20 20 20 20 2d 2d 2d  |             ---|
*
00001fa0  2d 2d 2d 2d 2d 2d 2d 2d  0a 0a 4a 50 45 47 20 28  |--------..JPEG (|
00001fb0  49 4a 47 20 76 20 36 29  20 20 20 20 20 20 20 20  |IJG v 6)        |
00001fc0  20 20 20 20 20 20 20 20  20 20 31 2e 33 33 20 20  |          1.33  |
00001fd0  20 20 20 20 20 20 20 20  20 20 31 2e 36 0a 42 54  |          1.6.BT|
00001fe0  50 43 33 20 20 20 20 20  20 20 20 20 20 20 20 20  |PC3             |
00001ff0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 31 2e  |              1.|
00002000  33 36 20 20 20 20 20 20  20 20 20 20 20 20 31 2e  |36            1.|
00002010  37 0a 53 26 50 20 66 61  73 74 20 20 20 20 20 20  |7.S&P fast      |
00002020  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002030  20 20 30 2e 39 33 20 20  20 20 20 20 20 20 20 20  |  0.93          |
00002040  20 20 35 2e 34 0a 53 26  50 20 73 6c 6f 77 20 20  |  5.4.S&P slow  |
00002050  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002060  20 20 20 20 20 20 30 2e  38 37 20 20 20 20 20 20  |      0.87      |
00002070  20 20 20 20 20 20 31 30  2e 31 0a 0a 4c 6f 73 73  |      10.1..Loss|
00002080  6c 65 73 73 20 63 6f 64  69 6e 67 3a 0a 0a 53 63  |less coding:..Sc|
00002090  68 65 6d 65 20 20 20 20  20 20 20 20 20 20 20 20  |heme            |
000020a0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 62 70  |              bp|
000020b0  70 20 20 20 20 20 20 20  20 20 20 20 20 20 44 65  |p             De|
000020c0  63 6f 64 65 20 74 69 6d  65 0a 2d 2d 2d 2d 2d 2d  |code time.------|
000020d0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
000020e0  20 20 20 20 20 20 20 20  20 20 2d 2d 2d 20 20 20  |          ---   |
000020f0  20 20 20 20 20 20 20 20  20 20 2d 2d 2d 2d 2d 2d  |          ------|
00002100  2d 2d 2d 2d 2d 0a 0a 42  54 50 43 33 20 20 20 20  |-----..BTPC3    |
00002110  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002120  20 20 20 20 20 20 20 35  2e 33 31 20 20 20 20 20  |       5.31     |
00002130  20 20 20 20 20 20 20 33  2e 30 0a 43 41 4c 49 43  |       3.0.CALIC|
00002140  20 66 61 73 74 20 20 20  20 20 20 20 20 20 20 20  | fast           |
00002150  20 20 20 20 20 20 20 20  20 20 20 34 2e 35 39 20  |           4.59 |
00002160  20 20 20 20 20 20 20 20  20 20 20 31 30 2e 35 0a  |           10.5.|
00002170  43 41 4c 49 43 20 73 6c  6f 77 20 20 20 20 20 20  |CALIC slow      |
00002180  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002190  34 2e 34 38 20 20 20 20  20 20 20 20 20 20 20 20  |4.48            |
000021a0  32 36 2e 35 0a 0a 33 2e  20 20 20 20 20 54 79 70  |26.5..3.     Typ|
000021b0  69 63 61 6c 20 66 69 67  75 72 65 73 20 66 6f 72  |ical figures for|
000021c0  20 67 72 61 70 68 69 63  61 6c 20 69 6d 61 67 65  | graphical image|
000021d0  73 0a 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |s.--------------|
000021e0  2d 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |----------------|
000021f0  2d 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 0a 0a  |--------------..|
00002200  57 69 74 68 20 70 75 72  65 6c 79 20 67 72 61 70  |With purely grap|
00002210  68 69 63 61 6c 20 69 6d  61 67 65 73 2c 20 42 54  |hical images, BT|
00002220  50 43 27 73 20 70 65 72  66 6f 72 6d 61 6e 63 65  |PC's performance|
00002230  20 69 6d 70 72 6f 76 65  73 20 72 65 6c 61 74 69  | improves relati|
00002240  76 65 20 74 6f 20 74 68  65 20 6f 74 68 65 72 0a  |ve to the other.|
00002250  73 63 68 65 6d 65 73 2e  20 49 74 20 63 6f 6e 73  |schemes. It cons|
00002260  69 73 74 65 6e 74 6c 79  20 63 6f 6d 70 72 65 73  |istently compres|
00002270  73 65 73 20 6d 6f 72 65  20 74 68 61 6e 20 4a 50  |ses more than JP|
00002280  45 47 2c 20 53 26 50 20  61 6e 64 20 74 68 65 20  |EG, S&P and the |
00002290  66 61 73 74 20 76 65 72  73 69 6f 6e 20 6f 66 0a  |fast version of.|
000022a0  43 41 4c 49 43 2e 20 49  74 20 63 6f 6d 70 72 65  |CALIC. It compre|
000022b0  73 73 65 73 20 61 62 6f  75 74 20 74 68 65 20 73  |sses about the s|
000022c0  61 6d 65 20 61 73 20 74  68 65 20 73 6c 6f 77 20  |ame as the slow |
000022d0  76 65 72 73 69 6f 6e 20  6f 66 20 43 41 4c 49 43  |version of CALIC|
000022e0  2c 20 61 74 20 61 62 6f  75 74 20 6e 69 6e 65 0a  |, at about nine.|
000022f0  74 69 6d 65 73 20 74 68  65 20 73 70 65 65 64 2e  |times the speed.|
00002300  20 48 65 72 65 20 61 72  65 20 66 69 67 75 72 65  | Here are figure|
00002310  73 20 66 6f 72 20 63 6f  64 69 6e 67 20 74 77 6f  |s for coding two|
00002320  20 74 79 70 69 63 61 6c  20 70 72 65 73 65 6e 74  | typical present|
00002330  61 74 69 6f 6e 20 67 72  61 70 68 69 63 73 2e 0a  |ation graphics..|
00002340  0a 34 39 36 20 78 20 36  37 32 20 46 72 61 6e 63  |.496 x 672 Franc|
00002350  65 3a 0a 0a 4c 6f 73 73  79 20 63 6f 64 69 6e 67  |e:..Lossy coding|
00002360  20 61 74 20 50 53 4e 52  20 33 34 2e 36 20 64 42  | at PSNR 34.6 dB|
00002370  20 28 3d 20 4a 50 45 47  20 63 6f 64 65 64 20 77  | (= JPEG coded w|
00002380  69 74 68 20 51 20 6f 66  20 37 35 29 3a 0a 0a 53  |ith Q of 75):..S|
00002390  63 68 65 6d 65 20 20 20  20 20 20 20 20 20 20 20  |cheme           |
000023a0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 62  |               b|
000023b0  70 70 20 20 20 20 20 20  20 20 20 20 20 20 20 44  |pp             D|
000023c0  65 63 6f 64 65 20 74 69  6d 65 0a 2d 2d 2d 2d 2d  |ecode time.-----|
000023d0  2d 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |-               |
000023e0  20 20 20 20 20 20 20 20  20 20 20 2d 2d 2d 20 20  |           ---  |
000023f0  20 20 20 20 20 20 20 20  20 20 20 2d 2d 2d 2d 2d  |           -----|
00002400  2d 2d 2d 2d 2d 2d 0a 0a  4a 50 45 47 20 28 49 4a  |------..JPEG (IJ|
00002410  47 20 76 20 36 29 20 20  20 20 20 20 20 20 20 20  |G v 6)          |
00002420  20 20 20 20 20 20 20 20  31 2e 34 33 20 20 20 20  |        1.43    |
00002430  20 20 20 20 20 20 20 20  31 2e 37 0a 42 54 50 43  |        1.7.BTPC|
00002440  33 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |3               |
00002450  20 20 20 20 20 20 20 20  20 20 20 20 30 2e 35 33  |            0.53|
00002460  20 20 20 20 20 20 20 20  20 20 20 20 31 2e 37 0a  |            1.7.|
00002470  53 26 50 20 66 61 73 74  20 20 20 20 20 20 20 20  |S&P fast        |
00002480  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002490  31 2e 30 39 20 20 20 20  20 20 20 20 20 20 20 20  |1.09            |
000024a0  37 2e 31 0a 53 26 50 20  73 6c 6f 77 20 20 20 20  |7.1.S&P slow    |
000024b0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
000024c0  20 20 20 20 30 2e 38 37  20 20 20 20 20 20 20 20  |    0.87        |
000024d0  20 20 20 20 31 34 2e 34  0a 0a 4c 6f 73 73 6c 65  |    14.4..Lossle|
000024e0  73 73 20 63 6f 64 69 6e  67 3a 0a 0a 53 63 68 65  |ss coding:..Sche|
000024f0  6d 65 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |me              |
00002500  20 20 20 20 20 20 20 20  20 20 20 20 62 70 70 20  |            bpp |
00002510  20 20 20 20 20 20 20 20  20 20 20 20 44 65 63 6f  |            Deco|
00002520  64 65 20 74 69 6d 65 0a  2d 2d 2d 2d 2d 2d 20 20  |de time.------  |
00002530  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002540  20 20 20 20 20 20 20 20  2d 2d 2d 20 20 20 20 20  |        ---     |
00002550  20 20 20 20 20 20 20 20  2d 2d 2d 2d 2d 2d 2d 2d  |        --------|
00002560  2d 2d 2d 0a 0a 42 54 50  43 33 20 20 20 20 20 20  |---..BTPC3      |
00002570  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002580  20 20 20 20 20 30 2e 38  39 20 20 20 20 20 20 20  |     0.89       |
00002590  20 20 20 20 20 32 2e 32  0a 43 41 4c 49 43 20 66  |     2.2.CALIC f|
000025a0  61 73 74 20 20 20 20 20  20 20 20 20 20 20 20 20  |ast             |
000025b0  20 20 20 20 20 20 20 20  20 31 2e 34 30 20 20 20  |         1.40   |
000025c0  20 20 20 20 20 20 20 20  20 37 2e 34 0a 43 41 4c  |         7.4.CAL|
000025d0  49 43 20 73 6c 6f 77 20  20 20 20 20 20 20 20 20  |IC slow         |
000025e0  20 20 20 20 20 20 20 20  20 20 20 20 20 30 2e 38  |             0.8|
000025f0  32 20 20 20 20 20 20 20  20 20 20 20 20 32 31 2e  |2            21.|
00002600  32 0a 0a 54 68 65 20 64  69 66 66 65 72 65 6e 63  |2..The differenc|
00002610  65 20 62 65 74 77 65 65  6e 20 74 68 65 20 74 77  |e between the tw|
00002620  6f 20 43 41 4c 49 43 20  72 65 73 75 6c 74 73 20  |o CALIC results |
00002630  69 73 20 63 6f 72 72 65  63 74 2c 20 61 6e 64 20  |is correct, and |
00002640  69 6c 6c 75 73 74 72 61  74 65 73 20 61 0a 70 72  |illustrates a.pr|
00002650  6f 62 6c 65 6d 20 77 69  74 68 20 74 68 65 20 75  |oblem with the u|
00002660  73 65 20 6f 66 20 48 75  66 66 6d 61 6e 20 63 6f  |se of Huffman co|
00002670  64 69 6e 67 20 69 6e 20  74 68 65 20 43 41 4c 49  |ding in the CALI|
00002680  43 20 61 6c 67 6f 72 69  74 68 6d 20 6f 6e 20 68  |C algorithm on h|
00002690  69 67 68 6c 79 0a 72 65  64 75 6e 64 61 6e 74 20  |ighly.redundant |
000026a0  69 6d 61 67 65 73 2e 0a  0a 33 37 32 20 78 20 36  |images...372 x 6|
000026b0  31 39 20 57 6f 72 6c 64  20 4d 61 70 3a 0a 0a 4c  |19 World Map:..L|
000026c0  6f 73 73 79 20 63 6f 64  69 6e 67 20 61 74 20 50  |ossy coding at P|
000026d0  53 4e 52 20 33 34 2e 34  20 64 42 20 28 3d 20 4a  |SNR 34.4 dB (= J|
000026e0  50 45 47 20 63 6f 64 65  64 20 77 69 74 68 20 51  |PEG coded with Q|
000026f0  20 6f 66 20 37 35 29 3a  0a 0a 53 63 68 65 6d 65  | of 75):..Scheme|
00002700  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002710  20 20 20 20 20 20 20 20  20 20 62 70 70 20 20 20  |          bpp   |
00002720  20 20 20 20 20 20 20 20  20 20 44 65 63 6f 64 65  |          Decode|
00002730  20 74 69 6d 65 0a 2d 2d  2d 2d 2d 2d 20 20 20 20  | time.------    |
00002740  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002750  20 20 20 20 20 20 2d 2d  2d 20 20 20 20 20 20 20  |      ---       |
00002760  20 20 20 20 20 20 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |      ----------|
00002770  2d 0a 0a 4a 50 45 47 20  28 49 4a 47 20 76 20 36  |-..JPEG (IJG v 6|
00002780  29 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |)               |
00002790  20 20 20 31 2e 38 33 20  20 20 20 20 20 20 20 20  |   1.83         |
000027a0  20 20 20 31 2e 32 0a 42  54 50 43 33 20 20 20 20  |   1.2.BTPC3    |
000027b0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
000027c0  20 20 20 20 20 20 20 30  2e 36 33 20 20 20 20 20  |       0.63     |
000027d0  20 20 20 20 20 20 20 31  2e 32 0a 53 26 50 20 66  |       1.2.S&P f|
000027e0  61 73 74 20 20 20 20 20  20 20 20 20 20 20 20 20  |ast             |
000027f0  20 20 20 20 20 20 20 20  20 20 20 31 2e 35 32 20  |           1.52 |
00002800  20 20 20 20 20 20 20 20  20 20 20 35 2e 37 20 20  |           5.7  |
00002810  20 20 20 5b 53 26 50 20  63 6f 64 65 64 20 61 20  |   [S&P coded a |
00002820  63 72 6f 70 70 65 64 0a  20 20 20 20 20 20 20 20  |cropped.        |
00002830  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
*
00002860  76 65 72 73 69 6f 6e 20  6f 66 20 74 68 65 20 69  |version of the i|
00002870  6d 61 67 65 5d 0a 53 26  50 20 73 6c 6f 77 20 20  |mage].S&P slow  |
00002880  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002890  20 20 20 20 20 20 31 2e  32 37 20 20 20 20 20 20  |      1.27      |
000028a0  20 20 20 20 20 20 31 32  2e 31 0a 0a 4c 6f 73 73  |      12.1..Loss|
000028b0  6c 65 73 73 20 63 6f 64  69 6e 67 3a 0a 0a 53 63  |less coding:..Sc|
000028c0  68 65 6d 65 20 20 20 20  20 20 20 20 20 20 20 20  |heme            |
000028d0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 62 70  |              bp|
000028e0  70 20 20 20 20 20 20 20  20 20 20 20 20 20 44 65  |p             De|
000028f0  63 6f 64 65 20 74 69 6d  65 0a 2d 2d 2d 2d 2d 2d  |code time.------|
00002900  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002910  20 20 20 20 20 20 20 20  20 20 2d 2d 2d 20 20 20  |          ---   |
00002920  20 20 20 20 20 20 20 20  20 20 2d 2d 2d 2d 2d 2d  |          ------|
00002930  2d 2d 2d 2d 2d 0a 0a 42  54 50 43 33 20 20 20 20  |-----..BTPC3    |
00002940  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002950  20 20 20 20 20 20 20 30  2e 36 33 20 20 20 20 20  |       0.63     |
00002960  20 20 20 20 20 20 20 31  2e 32 0a 43 41 4c 49 43  |       1.2.CALIC|
00002970  20 66 61 73 74 20 20 20  20 20 20 20 20 20 20 20  | fast           |
00002980  20 20 20 20 20 20 20 20  20 20 20 31 2e 30 36 20  |           1.06 |
00002990  20 20 20 20 20 20 20 20  20 20 20 33 2e 32 0a 43  |           3.2.C|
000029a0  41 4c 49 43 20 73 6c 6f  77 20 20 20 20 20 20 20  |ALIC slow       |
000029b0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 30  |               0|
000029c0  2e 36 31 20 20 20 20 20  20 20 20 20 20 20 20 31  |.61            1|
000029d0  32 2e 30 0a 0a 34 2e 20  20 20 20 20 54 79 70 69  |2.0..4.     Typi|
000029e0  63 61 6c 20 66 69 67 75  72 65 73 20 66 6f 72 20  |cal figures for |
000029f0  6d 75 6c 74 69 6d 65 64  69 61 20 69 6d 61 67 65  |multimedia image|
00002a00  73 0a 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |s.--------------|
00002a10  2d 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 2d  |----------------|
00002a20  2d 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 2d 2d 2d 0a  |---------------.|
00002a30  0a 42 65 63 61 75 73 65  20 74 68 65 20 72 65 6c  |.Because the rel|
00002a40  61 74 69 76 65 20 70 65  72 66 6f 72 6d 61 6e 63  |ative performanc|
00002a50  65 20 6f 66 20 42 54 50  43 20 61 6e 64 20 74 68  |e of BTPC and th|
00002a60  65 20 6f 74 68 65 72 20  73 63 68 65 6d 65 73 20  |e other schemes |
00002a70  69 73 20 64 69 66 66 65  72 65 6e 74 20 6f 6e 0a  |is different on.|
00002a80  70 68 6f 74 6f 67 72 61  70 68 73 20 61 6e 64 20  |photographs and |
00002a90  67 72 61 70 68 69 63 73  2c 20 6d 69 78 65 64 20  |graphics, mixed |
00002aa0  6f 72 20 6d 75 6c 74 69  6d 65 64 69 61 20 69 6d  |or multimedia im|
00002ab0  61 67 65 73 20 63 61 6e  20 67 69 76 65 20 64 69  |ages can give di|
00002ac0  66 66 65 72 65 6e 74 0a  72 65 73 75 6c 74 73 2e  |fferent.results.|
00002ad0  20 48 65 72 65 20 69 73  20 61 6e 20 65 78 61 6d  | Here is an exam|
00002ae0  70 6c 65 20 77 68 65 72  65 20 70 68 6f 74 6f 67  |ple where photog|
00002af0  72 61 70 68 73 20 61 72  65 20 65 6d 62 65 64 64  |raphs are embedd|
00002b00  65 64 20 77 69 74 68 69  6e 20 74 77 6f 2d 6c 65  |ed within two-le|
00002b10  76 65 6c 0a 67 72 61 70  68 69 63 73 20 28 55 57  |vel.graphics (UW|
00002b20  20 4c 69 62 72 61 72 79  20 6d 6f 6e 74 61 67 65  | Library montage|
00002b30  29 2e 20 54 68 69 73 20  66 61 76 6f 72 73 20 43  |). This favors C|
00002b40  41 4c 49 43 20 77 68 69  63 68 20 68 61 73 20 61  |ALIC which has a|
00002b50  20 73 70 65 63 69 61 6c  20 6d 6f 64 65 20 66 6f  | special mode fo|
00002b60  72 0a 74 77 6f 2d 6c 65  76 65 6c 20 72 65 67 69  |r.two-level regi|
00002b70  6f 6e 73 2e 0a 0a 33 35  32 20 78 20 34 36 34 20  |ons...352 x 464 |
00002b80  4c 69 62 72 61 72 79 3a  0a 0a 4c 6f 73 73 79 20  |Library:..Lossy |
00002b90  63 6f 64 69 6e 67 20 61  74 20 50 53 4e 52 20 33  |coding at PSNR 3|
00002ba0  30 2e 36 20 64 42 20 28  3d 20 4a 50 45 47 20 63  |0.6 dB (= JPEG c|
00002bb0  6f 64 65 64 20 77 69 74  68 20 51 20 6f 66 20 37  |oded with Q of 7|
00002bc0  35 29 3a 0a 0a 53 63 68  65 6d 65 20 20 20 20 20  |5):..Scheme     |
00002bd0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002be0  20 20 20 20 20 62 70 70  20 20 20 20 20 20 20 20  |     bpp        |
00002bf0  20 20 20 20 20 44 65 63  6f 64 65 20 74 69 6d 65  |     Decode time|
00002c00  0a 2d 2d 2d 2d 2d 2d 20  20 20 20 20 20 20 20 20  |.------         |
00002c10  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002c20  20 2d 2d 2d 20 20 20 20  20 20 20 20 20 20 20 20  | ---            |
00002c30  20 2d 2d 2d 2d 2d 2d 2d  2d 2d 2d 2d 0a 0a 4a 50  | -----------..JP|
00002c40  45 47 20 28 49 4a 47 20  76 20 36 29 20 20 20 20  |EG (IJG v 6)    |
00002c50  20 20 20 20 20 20 20 20  20 20 20 20 20 20 32 2e  |              2.|
00002c60  33 36 20 20 20 20 20 20  20 20 20 20 20 20 31 2e  |36            1.|
00002c70  31 0a 42 54 50 43 33 20  20 20 20 20 20 20 20 20  |1.BTPC3         |
00002c80  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002c90  20 20 31 2e 35 38 20 20  20 20 20 20 20 20 20 20  |  1.58          |
00002ca0  20 20 31 2e 31 0a 53 26  50 20 66 61 73 74 20 20  |  1.1.S&P fast  |
00002cb0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002cc0  20 20 20 20 20 20 31 2e  38 37 20 20 20 20 20 20  |      1.87      |
00002cd0  20 20 20 20 20 20 35 2e  38 0a 53 26 50 20 73 6c  |      5.8.S&P sl|
00002ce0  6f 77 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |ow              |
00002cf0  20 20 20 20 20 20 20 20  20 20 31 2e 36 31 20 20  |          1.61  |
00002d00  20 20 20 20 20 20 20 20  20 20 31 30 2e 36 0a 0a  |          10.6..|
00002d10  4c 6f 73 73 6c 65 73 73  20 63 6f 64 69 6e 67 3a  |Lossless coding:|
00002d20  0a 0a 53 63 68 65 6d 65  20 20 20 20 20 20 20 20  |..Scheme        |
00002d30  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002d40  20 20 62 70 70 20 20 20  20 20 20 20 20 20 20 20  |  bpp           |
00002d50  20 20 44 65 63 6f 64 65  20 74 69 6d 65 0a 2d 2d  |  Decode time.--|
00002d60  2d 2d 2d 2d 20 20 20 20  20 20 20 20 20 20 20 20  |----            |
00002d70  20 20 20 20 20 20 20 20  20 20 20 20 20 20 2d 2d  |              --|
00002d80  2d 20 20 20 20 20 20 20  20 20 20 20 20 20 2d 2d  |-             --|
00002d90  2d 2d 2d 2d 2d 2d 2d 2d  2d 0a 0a 42 54 50 43 33  |---------..BTPC3|
00002da0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002db0  20 20 20 20 20 20 20 20  20 20 20 35 2e 34 32 20  |           5.42 |
00002dc0  20 20 20 20 20 20 20 20  20 20 20 31 2e 38 0a 43  |           1.8.C|
00002dd0  41 4c 49 43 20 66 61 73  74 20 20 20 20 20 20 20  |ALIC fast       |
00002de0  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 35  |               5|
00002df0  2e 32 30 20 20 20 20 20  20 20 20 20 20 20 20 36  |.20            6|
00002e00  2e 36 0a 43 41 4c 49 43  20 73 6c 6f 77 20 20 20  |.6.CALIC slow   |
00002e10  20 20 20 20 20 20 20 20  20 20 20 20 20 20 20 20  |                |
00002e20  20 20 20 35 2e 30 31 20  20 20 20 20 20 20 20 20  |   5.01         |
00002e30  20 20 20 31 36 2e 34 0a  0a 53 75 6d 6d 61 72 79  |   16.4..Summary|
00002e40  20 6f 66 20 74 68 65 20  52 65 73 75 6c 74 73 0a  | of the Results.|
00002e50  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 3d 3d 3d  |================|
00002e60  3d 3d 3d 3d 3d 3d 0a 0a  46 75 72 74 68 65 72 20  |======..Further |
00002e70  72 65 73 75 6c 74 73 20  61 72 65 20 67 69 76 65  |results are give|
00002e80  6e 20 61 74 20 68 74 74  70 3a 2f 2f 6d 6f 6e 65  |n at http://mone|
00002e90  74 2e 75 77 61 74 65 72  6c 6f 6f 2e 63 61 2f 7e  |t.uwaterloo.ca/~|
00002ea0  6a 6f 68 6e 2f 62 74 70  63 2e 68 74 6d 6c 2e 20  |john/btpc.html. |
00002eb0  54 68 65 0a 6f 6e 65 73  20 67 69 76 65 6e 20 61  |The.ones given a|
00002ec0  62 6f 76 65 20 61 72 65  20 73 75 70 70 6f 73 65  |bove are suppose|
00002ed0  64 20 74 6f 20 62 65 20  72 65 70 72 65 73 65 6e  |d to be represen|
00002ee0  74 61 74 69 76 65 20 6f  66 20 74 68 65 20 67 65  |tative of the ge|
00002ef0  6e 65 72 61 6c 20 74 72  65 6e 64 73 20 77 68 69  |neral trends whi|
00002f00  63 68 0a 49 20 73 75 6d  6d 61 72 69 7a 65 20 61  |ch.I summarize a|
00002f10  73 3a 0a 0a 31 2e 20 4c  6f 73 73 6c 65 73 73 20  |s:..1. Lossless |
00002f20  63 6f 64 69 6e 67 2e 20  42 54 50 43 20 63 6f 6d  |coding. BTPC com|
00002f30  70 72 65 73 73 69 6f 6e  20 69 73 20 75 73 75 61  |pression is usua|
00002f40  6c 6c 79 20 62 65 74 77  65 65 6e 20 35 20 61 6e  |lly between 5 an|
00002f50  64 20 31 30 25 20 6c 65  73 73 0a 20 20 20 65 66  |d 10% less.   ef|
00002f60  66 69 63 69 65 6e 74 20  74 68 61 6e 20 74 68 65  |ficient than the|
00002f70  20 73 74 61 74 65 20 6f  66 20 74 68 65 20 61 72  | state of the ar|
00002f80  74 2c 20 43 41 4c 49 43  2c 20 66 6f 72 20 70 68  |t, CALIC, for ph|
00002f90  6f 74 6f 67 72 61 70 68  73 2c 20 61 6e 64 20 61  |otographs, and a|
00002fa0  62 6f 75 74 20 74 68 65  0a 20 20 20 73 61 6d 65  |bout the.   same|
00002fb0  20 65 66 66 69 63 69 65  6e 63 79 20 61 73 20 74  | efficiency as t|
00002fc0  68 65 20 73 6c 6f 77 20  76 65 72 73 69 6f 6e 20  |he slow version |
00002fd0  6f 66 20 43 41 4c 49 43  20 66 6f 72 20 67 72 61  |of CALIC for gra|
00002fe0  70 68 69 63 73 2e 20 49  74 20 69 73 0a 20 20 20  |phics. It is.   |
00002ff0  73 75 62 73 74 61 6e 74  69 61 6c 6c 79 20 6d 6f  |substantially mo|
00003000  72 65 20 65 66 66 69 63  69 65 6e 74 20 74 68 61  |re efficient tha|
00003010  6e 20 74 68 65 20 66 61  73 74 20 76 65 72 73 69  |n the fast versi|
00003020  6f 6e 20 6f 66 20 43 41  4c 49 43 20 66 6f 72 20  |on of CALIC for |
00003030  67 72 61 70 68 69 63 73  2e 20 49 74 0a 20 20 20  |graphics. It.   |
00003040  69 73 20 61 62 6f 75 74  20 33 2e 35 20 74 69 6d  |is about 3.5 tim|
00003050  65 73 20 66 61 73 74 65  72 20 74 68 61 6e 20 74  |es faster than t|
00003060  68 65 20 66 61 73 74 20  76 65 72 73 69 6f 6e 20  |he fast version |
00003070  61 6e 64 20 61 62 6f 75  74 20 39 20 74 69 6d 65  |and about 9 time|
00003080  73 20 66 61 73 74 65 72  0a 20 20 20 74 68 61 6e  |s faster.   than|
00003090  20 74 68 65 20 73 6c 6f  77 20 76 65 72 73 69 6f  | the slow versio|
000030a0  6e 20 6f 6e 20 61 76 65  72 61 67 65 2e 20 42 54  |n on average. BT|
000030b0  50 43 20 72 65 71 75 69  72 65 73 20 6d 6f 72 65  |PC requires more|
000030c0  20 6d 65 6d 6f 72 79 20  74 68 61 6e 20 43 41 4c  | memory than CAL|
000030d0  49 43 2c 20 69 6e 0a 20  20 20 74 68 61 74 20 74  |IC, in.   that t|
000030e0  68 65 20 65 6e 74 69 72  65 20 70 69 63 74 75 72  |he entire pictur|
000030f0  65 20 69 73 20 68 65 6c  64 20 69 6e 20 73 74 6f  |e is held in sto|
00003100  72 65 2e 20 4f 6e 20 74  68 65 20 6f 74 68 65 72  |re. On the other|
00003110  20 68 61 6e 64 2c 20 69  74 20 61 6c 6c 6f 77 0a  | hand, it allow.|
00003120  20 20 20 70 72 6f 67 72  65 73 73 69 76 65 20 64  |   progressive d|
00003130  65 63 6f 64 69 6e 67 2e  0a 0a 32 2e 20 4c 6f 73  |ecoding...2. Los|
00003140  73 79 20 63 6f 64 69 6e  67 20 76 73 20 4a 50 45  |sy coding vs JPE|
00003150  47 2e 20 42 54 50 43 20  69 73 20 61 6c 6d 6f 73  |G. BTPC is almos|
00003160  74 20 61 6c 77 61 79 73  20 73 75 70 65 72 69 6f  |t always superio|
00003170  72 20 74 6f 20 4a 50 45  47 2e 20 4f 6e 20 61 76  |r to JPEG. On av|
00003180  65 72 61 67 65 20 69 74  0a 20 20 20 69 73 20 61  |erage it.   is a|
00003190  62 6f 75 74 20 32 30 25  20 6d 6f 72 65 20 65 66  |bout 20% more ef|
000031a0  66 69 63 69 65 6e 74 20  74 68 61 6e 20 4a 50 45  |ficient than JPE|
000031b0  47 20 66 6f 72 20 70 68  6f 74 6f 67 72 61 70 68  |G for photograph|
000031c0  73 2c 20 61 74 20 6c 65  61 73 74 20 74 77 69 63  |s, at least twic|
000031d0  65 20 61 73 0a 20 20 20  65 66 66 69 63 69 65 6e  |e as.   efficien|
000031e0  74 20 66 6f 72 20 67 72  61 70 68 69 63 73 2e 20  |t for graphics. |
000031f0  44 65 63 6f 64 69 6e 67  20 69 73 20 61 73 20 66  |Decoding is as f|
00003200  61 73 74 20 61 73 20 74  68 65 20 49 4a 47 20 64  |ast as the IJG d|
00003210  65 63 6f 64 69 6e 67 20  61 6e 64 20 75 73 65 73  |ecoding and uses|
00003220  0a 20 20 20 73 6c 69 67  68 74 6c 79 20 6d 6f 72  |.   slightly mor|
00003230  65 20 6d 65 6d 6f 72 79  2e 20 45 6e 63 6f 64 69  |e memory. Encodi|
00003240  6e 67 20 63 75 72 72 65  6e 74 6c 79 20 74 61 6b  |ng currently tak|
00003250  65 73 20 62 65 74 77 65  65 6e 20 74 77 6f 20 61  |es between two a|
00003260  6e 64 20 74 68 72 65 65  20 74 69 6d 65 73 0a 20  |nd three times. |
00003270  20 20 61 73 20 6c 6f 6e  67 20 61 73 20 49 4a 47  |  as long as IJG|
00003280  20 4a 50 45 47 2e 0a 0a  33 2e 20 4c 6f 73 73 79  | JPEG...3. Lossy|
00003290  20 63 6f 64 69 6e 67 20  76 73 20 74 68 65 20 73  | coding vs the s|
000032a0  74 61 74 65 20 6f 66 20  74 68 65 20 61 72 74 2e  |tate of the art.|
000032b0  20 45 6d 62 65 64 64 65  64 20 63 6f 64 65 72 73  | Embedded coders|
000032c0  20 6c 69 6b 65 20 53 26  50 20 61 6e 64 20 53 68  | like S&P and Sh|
000032d0  61 70 69 72 6f 27 73 0a  20 20 20 73 65 65 6d 20  |apiro's.   seem |
000032e0  74 6f 20 62 65 20 74 68  65 20 66 75 74 75 72 65  |to be the future|
000032f0  20 6f 66 20 6c 6f 73 73  79 20 63 6f 64 69 6e 67  | of lossy coding|
00003300  20 66 6f 72 20 6e 61 74  75 72 61 6c 20 69 6d 61  | for natural ima|
00003310  67 65 73 2e 20 42 54 50  43 20 69 73 0a 20 20 20  |ges. BTPC is.   |
00003320  63 6f 6d 70 65 74 69 74  69 76 65 20 6f 6e 20 73  |competitive on s|
00003330  69 6d 70 6c 65 20 70 69  63 74 75 72 65 73 20 28  |imple pictures (|
00003340  6c 69 6b 65 20 63 61 6d  65 72 61 6d 61 6e 2c 20  |like cameraman, |
00003350  6d 65 6e 74 69 6f 6e 65  64 20 61 62 6f 76 65 29  |mentioned above)|
00003360  2c 20 62 75 74 20 6f 6e  0a 20 20 20 6d 6f 72 65  |, but on.   more|
00003370  20 74 65 78 74 75 72 65  64 20 69 6d 61 67 65 73  | textured images|
00003380  20 63 61 6e 20 72 65 71  75 69 72 65 20 35 30 25  | can require 50%|
00003390  20 6d 6f 72 65 20 62 69  74 73 20 74 68 61 6e 20  | more bits than |
000033a0  53 26 50 20 66 6f 72 20  61 20 70 68 6f 74 6f 67  |S&P for a photog|
000033b0  72 61 70 68 2e 0a 20 20  20 48 6f 77 65 76 65 72  |raph..   However|
000033c0  2c 20 42 54 50 43 20 63  6f 64 65 73 20 67 72 61  |, BTPC codes gra|
000033d0  70 68 69 63 73 20 61 6e  64 20 6d 75 6c 74 69 6d  |phics and multim|
000033e0  65 64 69 61 20 69 6d 61  67 65 73 20 6d 6f 72 65  |edia images more|
000033f0  20 65 66 66 69 63 69 65  6e 74 6c 79 2c 20 61 6e  | efficiently, an|
00003400  64 20 69 74 73 0a 20 20  20 64 65 63 6f 64 69 6e  |d its.   decodin|
00003410  67 20 74 69 6d 65 20 69  73 20 61 6c 77 61 79 73  |g time is always|
00003420  20 6c 65 73 73 20 74 68  61 6e 20 61 20 74 68 69  | less than a thi|
00003430  72 64 20 74 68 61 74 20  6f 66 20 66 61 73 74 20  |rd that of fast |
00003440  53 26 50 2c 20 61 6e 64  20 75 73 75 61 6c 6c 79  |S&P, and usually|
00003450  20 6c 65 73 73 0a 20 20  20 74 68 61 6e 20 61 20  | less.   than a |
00003460  71 75 61 72 74 65 72 2e  0a 0a 50 61 74 65 6e 74  |quarter...Patent|
00003470  73 20 61 6e 64 20 43 6f  70 79 72 69 67 68 74 0a  |s and Copyright.|
00003480  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3d 3d 3d 3d 3d 3d  |================|
00003490  3d 3d 3d 3d 3d 0a 0a 54  68 65 20 42 54 50 43 20  |=====..The BTPC |
000034a0  6d 65 74 68 6f 64 20 69  73 20 70 61 74 65 6e 74  |method is patent|
000034b0  2d 66 72 65 65 2e 20 49  6e 20 70 61 72 74 69 63  |-free. In partic|
000034c0  75 6c 61 72 2c 20 6e 6f  20 75 73 65 20 69 73 20  |ular, no use is |
000034d0  6d 61 64 65 20 6f 66 20  61 72 69 74 68 6d 65 74  |made of arithmet|
000034e0  69 63 0a 63 6f 64 69 6e  67 2e 20 54 68 65 20 73  |ic.coding. The s|
000034f0  6f 75 72 63 65 20 63 6f  64 65 20 69 73 20 63 6f  |ource code is co|
00003500  70 79 72 69 67 68 74 20  28 63 29 20 31 39 39 34  |pyright (c) 1994|
00003510  2c 20 31 39 39 35 2c 20  4a 6f 68 6e 20 41 2e 20  |, 1995, John A. |
00003520  52 6f 62 69 6e 73 6f 6e  2c 20 65 78 63 65 70 74  |Robinson, except|
00003530  0a 66 6f 72 20 70 6f 72  74 69 6f 6e 73 20 6f 66  |.for portions of|
00003540  20 74 68 65 20 66 69 6c  65 20 63 6f 6c 6d 61 70  | the file colmap|
00003550  2e 43 20 77 68 69 63 68  20 61 72 65 20 74 68 65  |.C which are the|
00003560  20 77 6f 72 6b 20 6f 66  20 74 68 65 20 49 6e 64  | work of the Ind|
00003570  65 70 65 6e 64 65 6e 74  20 4a 50 45 47 0a 67 72  |ependent JPEG.gr|
00003580  6f 75 70 20 61 6e 64 20  74 68 65 72 65 66 6f 72  |oup and therefor|
00003590  65 20 63 6f 70 79 72 69  67 68 74 20 28 43 29 20  |e copyright (C) |
000035a0  31 39 39 31 2c 20 31 39  39 32 2c 20 31 39 39 33  |1991, 1992, 1993|
000035b0  2c 20 31 39 39 34 2c 20  31 39 39 35 20 54 68 6f  |, 1994, 1995 Tho|
000035c0  6d 61 73 20 47 2e 20 4c  61 6e 65 2e 0a 28 50 72  |mas G. Lane..(Pr|
000035d0  65 76 69 6f 75 73 20 76  65 72 73 69 6f 6e 73 20  |evious versions |
000035e0  6f 66 20 42 54 50 43 20  63 6f 6e 74 61 69 6e 65  |of BTPC containe|
000035f0  64 20 63 6f 64 65 20 66  72 6f 6d 20 55 6e 69 78  |d code from Unix|
00003600  20 63 6f 6d 70 61 63 74  3a 20 74 68 69 73 20 68  | compact: this h|
00003610  61 73 20 6e 6f 77 20 62  65 65 6e 0a 72 65 70 6c  |as now been.repl|
00003620  61 63 65 64 2e 29 0a 0a  59 6f 75 20 6d 61 79 20  |aced.)..You may |
00003630  66 72 65 65 6c 79 20 75  73 65 20 61 6c 6c 20 74  |freely use all t|
00003640  68 65 20 42 54 50 43 20  63 6f 64 65 20 6f 6e 20  |he BTPC code on |
00003650  65 78 61 63 74 6c 79 20  74 68 65 20 73 61 6d 65  |exactly the same|
00003660  20 74 65 72 6d 73 20 61  73 20 74 68 65 0a 49 6e  | terms as the.In|
00003670  64 65 70 65 6e 64 65 6e  74 20 4a 50 45 47 20 67  |dependent JPEG g|
00003680  72 6f 75 70 20 61 6c 6c  6f 77 73 20 75 73 65 20  |roup allows use |
00003690  6f 66 20 74 68 65 69 72  20 63 6f 64 65 2e 20 46  |of their code. F|
000036a0  6f 6c 6c 6f 77 69 6e 67  20 74 68 65 69 72 20 70  |ollowing their p|
000036b0  61 74 74 65 72 6e 2c 20  61 6e 64 0a 61 64 61 70  |attern, and.adap|
000036c0  74 69 6e 67 20 74 68 65  69 72 20 52 45 41 44 4d  |ting their READM|
000036d0  45 20 66 69 6c 65 20 28  73 65 65 20 52 45 41 44  |E file (see READ|
000036e0  4d 45 4a 20 66 6f 72 20  74 68 65 20 6f 72 69 67  |MEJ for the orig|
000036f0  69 6e 61 6c 29 2c 20 68  65 72 65 20 69 73 20 68  |inal), here is h|
00003700  6f 77 20 69 74 0a 77 6f  72 6b 73 3a 0a 0a 49 20  |ow it.works:..I |
00003710  77 65 6c 63 6f 6d 65 20  74 68 65 20 75 73 65 20  |welcome the use |
00003720  6f 66 20 74 68 69 73 20  73 6f 66 74 77 61 72 65  |of this software|
00003730  20 61 73 20 61 20 63 6f  6d 70 6f 6e 65 6e 74 20  | as a component |
00003740  6f 66 20 63 6f 6d 6d 65  72 63 69 61 6c 20 70 72  |of commercial pr|
00003750  6f 64 75 63 74 73 2e 20  4e 6f 0a 72 6f 79 61 6c  |oducts. No.royal|
00003760  74 79 20 69 73 20 72 65  71 75 69 72 65 64 2c 20  |ty is required, |
00003770  62 75 74 20 49 20 64 6f  20 61 73 6b 20 66 6f 72  |but I do ask for|
00003780  20 61 6e 20 61 63 6b 6e  6f 77 6c 65 64 67 65 6d  | an acknowledgem|
00003790  65 6e 74 20 69 6e 20 70  72 6f 64 75 63 74 0a 64  |ent in product.d|
000037a0  6f 63 75 6d 65 6e 74 61  74 69 6f 6e 2c 20 61 73  |ocumentation, as|
000037b0  20 64 65 73 63 72 69 62  65 64 20 62 65 6c 6f 77  | described below|
000037c0  2e 0a 0a 49 6e 20 70 6c  61 69 6e 20 45 6e 67 6c  |...In plain Engl|
000037d0  69 73 68 3a 0a 0a 31 2e  20 49 20 64 6f 6e 27 74  |ish:..1. I don't|
000037e0  20 70 72 6f 6d 69 73 65  20 74 68 61 74 20 74 68  | promise that th|
000037f0  69 73 20 73 6f 66 74 77  61 72 65 20 77 6f 72 6b  |is software work|
00003800  73 2e 20 28 42 75 74 20  69 66 20 79 6f 75 20 66  |s. (But if you f|
00003810  69 6e 64 20 61 6e 79 20  62 75 67 73 2c 0a 20 20  |ind any bugs,.  |
00003820  20 70 6c 65 61 73 65 20  6c 65 74 20 6d 65 20 6b  | please let me k|
00003830  6e 6f 77 21 29 0a 32 2e  20 59 6f 75 20 63 61 6e  |now!).2. You can|
00003840  20 75 73 65 20 74 68 69  73 20 73 6f 66 74 77 61  | use this softwa|
00003850  72 65 20 66 6f 72 20 77  68 61 74 65 76 65 72 20  |re for whatever |
00003860  79 6f 75 20 77 61 6e 74  2e 20 59 6f 75 20 64 6f  |you want. You do|
00003870  6e 27 74 20 68 61 76 65  20 74 6f 20 70 61 79 20  |n't have to pay |
00003880  6d 65 2e 0a 33 2e 20 59  6f 75 20 6d 61 79 20 6e  |me..3. You may n|
00003890  6f 74 20 70 72 65 74 65  6e 64 20 74 68 61 74 20  |ot pretend that |
000038a0  79 6f 75 20 77 72 6f 74  65 20 74 68 69 73 20 73  |you wrote this s|
000038b0  6f 66 74 77 61 72 65 2e  20 49 66 20 79 6f 75 20  |oftware. If you |
000038c0  75 73 65 20 69 74 20 69  6e 20 61 0a 20 20 20 70  |use it in a.   p|
000038d0  72 6f 67 72 61 6d 2c 20  79 6f 75 20 6d 75 73 74  |rogram, you must|
000038e0  20 61 63 6b 6e 6f 77 6c  65 64 67 65 20 73 6f 6d  | acknowledge som|
000038f0  65 77 68 65 72 65 20 69  6e 20 79 6f 75 72 20 64  |ewhere in your d|
00003900  6f 63 75 6d 65 6e 74 61  74 69 6f 6e 20 74 68 61  |ocumentation tha|
00003910  74 0a 20 20 20 79 6f 75  27 76 65 20 75 73 65 64  |t.   you've used|
00003920  20 74 68 65 20 42 54 50  43 20 56 65 72 73 69 6f  | the BTPC Versio|
00003930  6e 20 33 20 63 6f 64 65  2e 0a 0a 49 6e 20 6c 65  |n 3 code...In le|
00003940  67 61 6c 65 73 65 3a 0a  0a 54 68 65 20 61 75 74  |galese:..The aut|
00003950  68 6f 72 20 6d 61 6b 65  73 20 4e 4f 20 57 41 52  |hor makes NO WAR|
00003960  52 41 4e 54 59 20 6f 72  20 72 65 70 72 65 73 65  |RANTY or represe|
00003970  6e 74 61 74 69 6f 6e 2c  20 65 69 74 68 65 72 20  |ntation, either |
00003980  65 78 70 72 65 73 73 20  6f 72 20 69 6d 70 6c 69  |express or impli|
00003990  65 64 2c 20 77 69 74 68  0a 72 65 73 70 65 63 74  |ed, with.respect|
000039a0  20 74 6f 20 74 68 69 73  20 73 6f 66 74 77 61 72  | to this softwar|
000039b0  65 2c 20 69 74 73 20 71  75 61 6c 69 74 79 2c 20  |e, its quality, |
000039c0  61 63 63 75 72 61 63 79  2c 20 6d 65 72 63 68 61  |accuracy, mercha|
000039d0  6e 74 61 62 69 6c 69 74  79 2c 20 6f 72 20 66 69  |ntability, or fi|
000039e0  74 6e 65 73 73 0a 66 6f  72 20 61 20 70 61 72 74  |tness.for a part|
000039f0  69 63 75 6c 61 72 20 70  75 72 70 6f 73 65 2e 20  |icular purpose. |
00003a00  54 68 69 73 20 73 6f 66  74 77 61 72 65 20 69 73  |This software is|
00003a10  20 70 72 6f 76 69 64 65  64 20 22 41 53 20 49 53  | provided "AS IS|
00003a20  22 2c 20 61 6e 64 20 79  6f 75 2c 20 69 74 73 20  |", and you, its |
00003a30  75 73 65 72 2c 0a 61 73  73 75 6d 65 20 74 68 65  |user,.assume the|
00003a40  20 65 6e 74 69 72 65 20  72 69 73 6b 20 61 73 20  | entire risk as |
00003a50  74 6f 20 69 74 73 20 71  75 61 6c 69 74 79 20 61  |to its quality a|
00003a60  6e 64 20 61 63 63 75 72  61 63 79 2e 0a 0a 54 68  |nd accuracy...Th|
00003a70  69 73 20 73 6f 66 74 77  61 72 65 2c 20 65 78 63  |is software, exc|
00003a80  6c 75 64 69 6e 67 20 74  68 65 20 66 69 6c 65 20  |luding the file |
00003a90  63 6f 6c 6d 61 70 2e 43  2c 20 69 73 20 63 6f 70  |colmap.C, is cop|
00003aa0  79 72 69 67 68 74 20 28  43 29 20 31 39 39 34 2c  |yright (C) 1994,|
00003ab0  20 31 39 39 35 2c 20 4a  6f 68 6e 0a 41 2e 20 52  | 1995, John.A. R|
00003ac0  6f 62 69 6e 73 6f 6e 2c  20 41 6c 6c 20 52 69 67  |obinson, All Rig|
00003ad0  68 74 73 20 52 65 73 65  72 76 65 64 20 65 78 63  |hts Reserved exc|
00003ae0  65 70 74 20 61 73 20 73  70 65 63 69 66 69 65 64  |ept as specified|
00003af0  20 62 65 6c 6f 77 2e 0a  0a 50 65 72 6d 69 73 73  | below...Permiss|
00003b00  69 6f 6e 20 69 73 20 68  65 72 65 62 79 20 67 72  |ion is hereby gr|
00003b10  61 6e 74 65 64 20 74 6f  20 75 73 65 2c 20 63 6f  |anted to use, co|
00003b20  70 79 2c 20 6d 6f 64 69  66 79 2c 20 61 6e 64 20  |py, modify, and |
00003b30  64 69 73 74 72 69 62 75  74 65 20 74 68 69 73 20  |distribute this |
00003b40  73 6f 66 74 77 61 72 65  0a 28 6f 72 20 70 6f 72  |software.(or por|
00003b50  74 69 6f 6e 73 20 74 68  65 72 65 6f 66 29 20 66  |tions thereof) f|
00003b60  6f 72 20 61 6e 79 20 70  75 72 70 6f 73 65 2c 20  |or any purpose, |
00003b70  77 69 74 68 6f 75 74 20  66 65 65 2c 20 73 75 62  |without fee, sub|
00003b80  6a 65 63 74 20 74 6f 20  74 68 65 73 65 0a 63 6f  |ject to these.co|
00003b90  6e 64 69 74 69 6f 6e 73  3a 0a 0a 28 31 29 20 49  |nditions:..(1) I|
00003ba0  66 20 61 6e 79 20 70 61  72 74 20 6f 66 20 74 68  |f any part of th|
00003bb0  65 20 73 6f 75 72 63 65  20 63 6f 64 65 20 66 6f  |e source code fo|
00003bc0  72 20 74 68 69 73 20 73  6f 66 74 77 61 72 65 20  |r this software |
00003bd0  69 73 20 64 69 73 74 72  69 62 75 74 65 64 2c 20  |is distributed, |
00003be0  74 68 65 6e 20 74 68 69  73 0a 22 50 61 74 65 6e  |then this."Paten|
00003bf0  74 73 20 61 6e 64 20 43  6f 70 79 72 69 67 68 74  |ts and Copyright|
00003c00  22 20 73 65 63 74 69 6f  6e 20 6f 66 20 74 68 65  |" section of the|
00003c10  20 52 45 41 44 4d 45 20  66 69 6c 65 20 6d 75 73  | README file mus|
00003c20  74 20 62 65 20 69 6e 63  6c 75 64 65 64 2c 20 77  |t be included, w|
00003c30  69 74 68 20 74 68 69 73  0a 63 6f 70 79 72 69 67  |ith this.copyrig|
00003c40  68 74 20 61 6e 64 20 6e  6f 2d 77 61 72 72 61 6e  |ht and no-warran|
00003c50  74 79 20 6e 6f 74 69 63  65 20 75 6e 61 6c 74 65  |ty notice unalte|
00003c60  72 65 64 3b 20 61 6e 64  20 61 6e 79 20 61 64 64  |red; and any add|
00003c70  69 74 69 6f 6e 73 2c 20  64 65 6c 65 74 69 6f 6e  |itions, deletion|
00003c80  73 2c 20 6f 72 0a 63 68  61 6e 67 65 73 20 74 6f  |s, or.changes to|
00003c90  20 74 68 65 20 6f 72 69  67 69 6e 61 6c 20 66 69  | the original fi|
00003ca0  6c 65 73 20 6d 75 73 74  20 62 65 20 63 6c 65 61  |les must be clea|
00003cb0  72 6c 79 20 69 6e 64 69  63 61 74 65 64 20 69 6e  |rly indicated in|
00003cc0  20 61 63 63 6f 6d 70 61  6e 79 69 6e 67 0a 64 6f  | accompanying.do|
00003cd0  63 75 6d 65 6e 74 61 74  69 6f 6e 2e 0a 0a 28 32  |cumentation...(2|
00003ce0  29 20 49 66 20 6f 6e 6c  79 20 65 78 65 63 75 74  |) If only execut|
00003cf0  61 62 6c 65 20 63 6f 64  65 20 69 73 20 64 69 73  |able code is dis|
00003d00  74 72 69 62 75 74 65 64  2c 20 74 68 65 6e 20 74  |tributed, then t|
00003d10  68 65 20 61 63 63 6f 6d  70 61 6e 79 69 6e 67 20  |he accompanying |
00003d20  64 6f 63 75 6d 65 6e 74  61 74 69 6f 6e 0a 6d 75  |documentation.mu|
00003d30  73 74 20 73 74 61 74 65  20 74 68 61 74 20 22 74  |st state that "t|
00003d40  68 69 73 20 73 6f 66 74  77 61 72 65 20 69 73 20  |his software is |
00003d50  62 61 73 65 64 20 69 6e  20 70 61 72 74 20 6f 6e  |based in part on|
00003d60  20 42 69 6e 61 72 79 20  54 72 65 65 20 50 72 65  | Binary Tree Pre|
00003d70  64 69 63 74 69 76 65 0a  43 6f 64 69 6e 67 20 56  |dictive.Coding V|
00003d80  65 72 73 69 6f 6e 20 33  2c 20 69 6d 70 6c 65 6d  |ersion 3, implem|
00003d90  65 6e 74 65 64 20 62 79  20 4a 2e 20 41 2e 20 52  |ented by J. A. R|
00003da0  6f 62 69 6e 73 6f 6e 22  2e 0a 0a 28 33 29 20 50  |obinson"...(3) P|
00003db0  65 72 6d 69 73 73 69 6f  6e 20 66 6f 72 20 75 73  |ermission for us|
00003dc0  65 20 6f 66 20 74 68 69  73 20 73 6f 66 74 77 61  |e of this softwa|
00003dd0  72 65 20 69 73 20 67 72  61 6e 74 65 64 20 6f 6e  |re is granted on|
00003de0  6c 79 20 69 66 20 74 68  65 20 75 73 65 72 20 61  |ly if the user a|
00003df0  63 63 65 70 74 73 0a 66  75 6c 6c 20 72 65 73 70  |ccepts.full resp|
00003e00  6f 6e 73 69 62 69 6c 69  74 79 20 66 6f 72 20 61  |onsibility for a|
00003e10  6e 79 20 75 6e 64 65 73  69 72 61 62 6c 65 20 63  |ny undesirable c|
00003e20  6f 6e 73 65 71 75 65 6e  63 65 73 3b 20 74 68 65  |onsequences; the|
00003e30  20 61 75 74 68 6f 72 20  61 63 63 65 70 74 73 20  | author accepts |
00003e40  4e 4f 0a 4c 49 41 42 49  4c 49 54 59 20 66 6f 72  |NO.LIABILITY for|
00003e50  20 64 61 6d 61 67 65 73  20 6f 66 20 61 6e 79 20  | damages of any |
00003e60  6b 69 6e 64 2e 0a 0a 4e  4f 54 45 20 54 48 41 54  |kind...NOTE THAT|
00003e70  20 49 46 20 59 4f 55 20  55 53 45 20 54 48 45 20  | IF YOU USE THE |
00003e80  46 49 4c 45 20 43 4f 4c  4d 41 50 2e 43 20 59 4f  |FILE COLMAP.C YO|
00003e90  55 20 4d 55 53 54 20 43  4f 4d 50 4c 59 20 57 49  |U MUST COMPLY WI|
00003ea0  54 48 20 54 48 45 20 49  4a 47 27 53 20 54 45 52  |TH THE IJG'S TER|
00003eb0  4d 53 20 54 4f 4f 0a 2d  20 53 45 45 20 54 48 45  |MS TOO.- SEE THE|
00003ec0  20 46 49 4c 45 20 52 45  41 44 4d 45 4a 2e 0a     | FILE READMEJ..|
00003ecf