Binary Tree Predictive Coding (BTPC), Version 4.1
=================================================

Contents
========

	What is BTPC?
	What's new in Version 4.1?
	What's new in Version 4?
	Net addresses for code and docs
	Details of available code
	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 4.1?
==========================

Version 4.1 corrects some bugs from version 4. Most of these affected
performance on Windows platforms only. Thanks to Bill Sebastian for
informative bug reports.

What's new in Version 4?
========================

In version 4, BTPC encode and decode times are about 10% faster, on
average, than version 3. The compression rate is slightly improved. 
BTPC decoding speed is now faster than that of the Independent JPEG group 
(IJG) JPEG decoder, and more than three times faster than its other rivals. 

The code now works without modification under DOS and can be incorporated
into Windows programs easily. DOS executables are included in this release.

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

Source code and makefile for Unix systems are tarred and compressed at:

  http://www.engr.mun.ca/~john/btpcv4.tar.Z

Source code and executables for DOS are zipped at:

  http://www.engr.mun.ca/~john/btpc4.zip

BTPC is documented in:
  J A Robinson, "Efficient General-Purpose Image Compression with Binary Tree
  Predictive Coding", IEEE Transactions on Image Processing, Vol 6, No 4,
  April 1997, pp 601-607.
and, in more detail, at
  http://www.engr.mun.ca/~john/btpc.html

The file README3 in this package gives comparisons between BTPC version 3, 
JPEG, and state of the art coders. Version 4 is only marginally better at
compression than version 3, so the relative placings of the coders still
holds. However, now that BTPC coding and decoding are faster, it beats
JPEG in speed as well as compression performance.

Programs
========

When uncompressed and untarred the btpcv4.tar.Z file yields sources for 
two programs:

cbtpc	- Convert PGM or PPM file to compressed BTPC
dbtpc	- Convert compressed BTPC to PGM or PPM

To make
-------

1.      Edit the first line of the makefile if your c++ compiler is not
	called c++.
2.      rename cbtpc.cpp to cbtpc.C etc. if your compiler demands it.
3.      make btpc
	(This will make the cbtpc and dbtpc programs. Also included in
	the archive are the programs psnr and bpp which I use in testing.
	If these are useful to you, just do make all.)
4.	Some compilers (not g++) gripe that the function btpc_dec_level in 
	declevel.cpp is too big to optimize. This can be fixed by compiling 
	declevel.cpp with appropriate flags. For example, in the makefile
		$(C++) $(COPTS) -c declevel.C
	may be replaced by
		$(C++) -Olimit 1200 $(COPTS) -c declevel.C
	on Decstations and SGIs (for which the compiler is called CC), or by
		$(C++) +Onolimit $(COPTS) -c declevel.C
	on a HP/UX machine. Check your compiler documentation.

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").

PC programs
-----------

Source code and DOS executables are included in the BTPC zipfile. The
executables were made using Optima++. Note that the executables have to
run under DOS because they take command line parameters, just like the
Unix versions.


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, 1997 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. 

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 4 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, 1997 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 4, 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.
