Home » Personal collection » Acorn hard disk » apps » web » !ChangeFSI/btpc/README
!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 » apps » web |
| Filename: | !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:
- Personal collection » Acorn ADFS disks » Greaseweazled » adfs_1.6M_Apps2.adf » !ChangeFSI/btpc/README
- Personal collection » Acorn hard disk » apps » ImagePrcss » !ChangeFSI/btpc/README
- Personal collection » Acorn hard disk » apps » web » !ChangeFSI/btpc/README
- Personal collection » Acorn hard disk » zipped_disks » 2000_apps_2 » apps2/!ChangeFSI/btpc/README
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
.