rle.txt

图形RLE压缩格式算法介绍

                         DESIGN OF THE UTAH RLE FORMAT

                               Spencer W. Thomas

              University of Utah, Department of Computer Science








                                   ABSTRACT

      The  Utah  RLE  (Run Length Encoded) format is designed to provide an
    efficient, device  independent  means  of  storing  multi-level  raster
    images.    Images of arbitrary size and depth can be saved.  The design
    of the format is presented, followed by  descriptions  of  the  library
    routines used to create and read RLE format files.

1. Introduction
  The Utah RLE (Run Length Encoded) format is designed to provide an efficient,
device independent means of storing multi-level  raster  images.    It  is  not
designed  for  binary  (bitmap) images.  It is built on several basic concepts.
The central concept is that of a channel.  A channel corresponds  to  a  single
color,  thus  there  are  normally  a  red channel, a green channel, and a blue
channel.  Up to 255 color channels  are  available  for  use;  one  channel  is
reserved  for  "alpha"  data.    Although  the format supports arbitrarily deep
channels, the current implementation is restricted to 8 bits per channel.

  Image data is stored in an RLE file in a scanline form,  with  the  data  for
each  channel of the scanline grouped together.  Runs of identical pixel values
are compressed into a count and a  value.    However,  sequences  of  differing
pixels are also stored efficiently (not as a sequence of single pixel runs).

  The  file  header  contains  a  large  amount of information about the image,
including its size, the number of channels  saved,  whether  it  has  an  alpha
channel,  an optional color map, and comments.  The comments may be used to add
arbitrary extra information to the saved image.

  A subroutine interface has been written to allow programs to read  and  write
files  in  the  RLE  format.  Two interfaces are available, one that completely
interprets the RLE file and returns scanline pixel data, and one that returns a
list  of  "raw"  run  and  pixel  data.  The second is more efficient, but more
difficult to use, the first is easy to use, but slower.

  The Utah RLE format has been used to save images from many  sources,  and  to
display  saved  images  on  many  different  displays  and  from many different
computers.

2. Description of RLE Format
  All data in the RLE file is treated as  a  byte  stream.    Where  quantities
larger than 8 bits occur, they are written in PDP-11 byte order (low order byte
first).

  The RLE file consists of two parts, a header followed by scanline data.   The
header contains general information about the image, while the scanline data is
a stream of operations describing the image itself.



2.1. The Header
























                         Figure 2-1:   RLE file header

  The header has a fixed part and a variable part.  A diagram of the header  is
shown  in  Figure  2-1.    The magic number identifies the file as an RLE file.
Following this are the coordinates of the lower left corner of  the  image  and
the size of the image in the X and Y directions.  Images are defined in a first
quadrant coordinate system (origin at the  lower  left,  X  increasing  to  the
right, Y increasing up.)  Thus, the image is enclosed in the rectangle

    [xpos,xpos+xsize-1]X[ypos,ypos+ysize-1].

The  position  and  size are 16 bit integer quantities; images up to 32K square
may be saved (the sizes should not be negative).

  A flags byte follows.  There are currently four flags defined:

  ClearFirst   If this flag is set, the image rectangle should first be cleared
               to the background color (q.v.) before reading the scanline data.

  NoBackground If  this  flag  is set, no background color is supplied, and the
               ClearFirst flag should be ignored.

  Alpha        This flag indicates the presence of an  "alpha"  channel.    The
               alpha channel is used by image compositing software to correctly
               blend anti-aliased edges.  It is stored as channel -1 (255).

  Comments     If this flag is set, comments are present in the  variable  part
               of the header, immediately following the color map.

  The next byte is treated as an unsigned 8 bit value, and indicates the number
of color channels that were saved.  It  may  have  any  value  from  0  to  254
(channel 255 is reserved for alpha values).

  The  pixelbits  byte  gives the number of bits in each pixel.  The only value
currently supported by the software is 8  (in  fact,  this  byte  is  currently
ignored when reading RLE files).  Pixel sizes taking more than one byte will be
packed low order byte first.

  The next two bytes describe the size and shape of the color map.    Ncmap  is
the  number  of  color  channels in the color map.  It need not be identical to
ncolors, but interpretation of values of ncmap different from 0, 1, or  ncolors
may  be  ambiguous,  unless  ncolors  is  1.  If ncmap is zero, no color map is
saved.  Cmaplen is the log base 2 of the length of each channel  of  the  color
map.  Thus, a value for cmaplen of 8 indicates a color map with 256 entries per
channel.

  Immediately following the fixed header is  the  variable  part  of  the  file
header.  It starts with the background color.  The background color has ncolors
entries; if necessary, it is filled out to an odd number of bytes with a filler
byte  on  the  end  (since  the  fixed header is an odd number bytes long, this
returns to a 16 bit boundary).

  Following the background color is the color  map,  if  present.    Color  map
values  are  stored as 16 bit quantities, left justified in the word.  Software
interpreting the color map must apply a shift appropriate to the application or
to  the  hardware  being  used.    This convention permits use of the color map
without knowing the original output precision.  The channels  of  the  map  are
stored  in  increasing  numerical  order  (starting  with  channel 0), with the
entries of each channel stored also in increasing order  (starting  with  entry
0).  The color map entries for each channel are stored contiguously.

  Comments,  if  present,  follow  the color map.  A 16 bit quantity giving the
length of the comment block comes first.  If the length is odd, a  filler  byte
will  be  present  at the end, restoring the 16 bit alignment (but this byte is
not part  of  the  comments).    The  comment  block  contains  any  number  of
null-terminated text strings.  These strings will conventionally be of the form
"name=value", allowing for easy retrieval of specific  information.    However,
there  is  no restriction that a given name appear only once, and a comment may
contain an arbitrary string.  The intent of  the  comment  block  is  to  allow
information to be attached to the file that is not specifically provided for in
the RLE format.



2.2. The Scanline Data
  The scanline data  consists  of  a  sequence  of  operations,  such  as  Run,
SetChannel,  and  Pixels,  describing  the  actual  image.   An image is stored
starting at the lower left corner and proceeding upwards in order of increasing
scanline  number.    Each  operation  and  its associated data takes up an even
number of bytes, so that all operations begin on a 16 bit boundary.  This makes
the implementation more efficient on many architectures.















                    Figure 2-2:   RLE file operand formats

  Each  operation  is  identified  by an 8 bit opcode, and may have one or more
operands.  Single operand operations fit into a  single  16  bit  word  if  the
operand  value is less than 256.  So that operand values are not limited to the
range 0..255, each operation has a long variant, in which  the  byte  following
the  opcode  is  ignored  and the following word is taken as a 16 bit quantity.
The long variant of an opcode is indicated by  setting  the  bit  0x40  in  the
opcode (this allows for 64 opcodes, of which 6 have been used so far.)  The two
single operand formats are shown pictorially in Figure 2-2.

  The individual operations will now be discussed in detail.  The  descriptions
are  phrased  in  terms  of the actions necessary to interpret the file.  Three
indices are necessary: the current channel, the scanline number, and the  pixel
index.  The current channel is the channel to which data operations apply.  The
scanline number is just the Y position of the scanline in the image.  The pixel
index is the X position of the pixel within the scanline.  The operations are:

  SkipLines    Increment  the  scanline  number  by  the  operand  value.  This
               operation terminates the current  scanline.    The  pixel  index
               should be reset to the xpos value from the header.

  SetColor     Set  the  current  channel to the operand value.  This operation
               does not have a long variant.  Note that an operand value of 255
               will  be interpreted as a -1, indicating the alpha channel.  All
               other operand values are positive.  The pixel index is reset  to
               the xpos value.

  SkipPixels   Skip over pixels in the current scanline.  Increment pixel index
               by the operand value.   Pixels  skipped  will  be  left  in  the
               background color.

  PixelData    Following this opcode is a sequence of pixel values.  The length
               of the sequence is given by the operand value.  If the length of
               the  sequence  is  odd, a filler byte is appended.  Pixel values
               are inserted into the scanline in increasing X order.  The pixel
               index is incremented by the sequence length.

  Run          This  is  the only two operand opcode.  The first operand is the
               length (N) of the run.  The second operand is the  pixel  value,
               followed  by  a  filler  byte  if necessary(E.g., a 16 bit pixel
               value would not need a filler byte.).  The next N pixels in  the
               scanline  are  set to the given pixel value.  The pixel index is
               incremented by N, to point to the pixel following the run.

  EOF          This opcode has no operand, and indicates the  end  of  the  RLE
               file.    It  is  provided  so that RLE files may be concatenated
               together  and  still  be  correctly  interpreted.    It  is  not
               required,  a  physical end of file will also indicate the end of
               the RLE data.



2.3. Subroutine Interface
  Two similar subroutine interfaces are provided for reading and writing  files
in  the  RLE format.  Both read or write a scanline worth of data at a time.  A
simple "row" interface communicates in terms of arrays of pixel values.  It  is
simple  to  use,  but  slower  than  the  "raw" interface, which uses a list of
"opcode" values as its communication medium.

  In both cases, the interface must be initialized by calling a setup function.
The two types of calls may be interleaved; for example, in a rendering program,
the background could be written using  the  "raw"  interface,  while  scanlines
containing image data could be converted with the "row" interface.  The package
allows multiple RLE streams to be open simultaneously, as is necessary for  use
in  a  compositing  tool,  for  example.  All data relevant to a particular RLE
stream is contained in a "globals" structure.

  The globals structure echoes the format of the RLE header.   The  fields  are
described below:

  dispatch     The  RLE  creation routines are capable of writing various types
               of output files in addition to RLE.  This value is an index into
               a dispatch table.  This value is initialized by sv_setup.

  ncolors      The  number  of  color  channels in the output file.  Up to this
               many color channels will be saved, depending on  the  values  in
               the channel bitmap (see below).

  bg_color     A  pointer  to  an  array  of  ncolors  integers  containing the
               background color.

  alpha        If this is non-zero, an  alpha  channel  will  be  saved.    The
               presence  or  absence  of  an alpha channel has no effect on the
               value in ncolors.

  background   Indicates how to treat background pixels.  It has the  following
               values:

               0    Save all pixels, the background color is ignored.

               1    Save  only  non-background pixels, but don't set the "clear
                    screen" bit.  This indicates "overlay" mode, a  cheap  form
                    of compositing (but see note below about this.)

               2    Save  only  non-background  pixels, clear the screen to the
                    background color before restoring the image.

  xmin, xmax, ymin, ymax
               Inclusive bounds of the image region being saved.

  ncmap        Number of channels of color map to be saved.  The color map will
               not be saved if this is 0.

  cmaplen      Log base 2 of the number of entries in each channel of the color