plio.txt

PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



                      THE IRAF PIXEL LIST PACKAGE
                                  and
                 IMIO EXTENSIONS TO SUPPORT IMAGE MASKS
                               Doug Tody
                             February, 1988
                          (Revised June 1988)




1. INTRODUCTION

    The  pixel list package is a general package for flagging individual
pixels or regions of an image, to mark some subset of the pixels  in  an
image.   This  may  be  done  to  flag  bad pixels, or to identify those
regions of an image to be processed by some applications program.   When
the  pixel  list  package  is used to flag the bad pixels in an image we
call this a BAD PIXEL MASK, or BPM.  When used to identify  the  regions
of  an  image  to  be  processed (or ignored), we call the list a REGION
MASK.

A pixel list may be viewed conceptually as either a list  or  an  image;
the  list  is  merely  the  compressed  form  of  a  virtual MASK IMAGE.
Storing a mask image as a list has two major advantages.

    [1] Storage efficiency.  Simple masks may be stored very  compactly,
        e.g.,  as small arrays stored directly in an image header, or in
        a separate mask file or database.
    
    [2] Runtime efficiency.   Storing  a  mask  in  list  form  has  the
        advantage  that  one can determine very quickly whether or not a
        given region of the image (e.g., an  image  line)  contains  any
        pixels  in  the  mask.  The alternative, given a fully populated
        mask image (or flagging the pixels directly in the data  image),
        requires  that  one examine every pixel in the mask image, which
        is very inefficient for simple masks.

The pixel list technique  for  implementing  image  masks  is  the  most
efficient  choice  only  for  simple  or moderately complex masks.  As a
mask image increases in complexity there eventually comes a point  where
it  would  be  simpler  and  more efficient to use a conventional raster
image to store the mask.  For example, if  one  wishes  to  associate  a
flag  value  (such  as  a  weight) with every pixel in an image, and the
flag values vary rapidly in value across the  image,  a  separate  image
should  probably  be  used  (except that other forms of data compression
may be possible; the IRAF NOISE FUNCTION PACKAGE  addresses  one  aspect
of this problem).

The  pixel list related software is subdivided into two parts, the pixel
list package itself, and the extensions to  IMIO  to  make  use  of  the
pixel  list package.  The pixel list package in itself is independent of
IMIO and may be used separately.


                                  -1-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



2. IMIO SUPPORT FOR PIXEL LISTS

    Most image applications tend to fall into two  classes,  the  simple
pointwise  transformation  operators,  and  the more cpu intensive image
analysis operations.  The simple  operators  usually  operate  upon  the
whole  image  (no  mask  required)  and  may  ignore the presence of bad
pixels in the image, provided reasonable  artificial  values  have  been
provided  for  the  bad pixels so that arithmetic problems do not occur,
and provided we keep track of  the  locations  of  the  bad  pixels  (by
propagating  the  bad pixel lists), so that the bad pixel information is
available to subsequent image analysis programs.

The  image  analysis  operators,  on  the  other  hand,  must  know  the 
locations  of the bad pixels in order to exclude them from the fit.  The
analysis is also often performed only  upon  specified  regions  of  the
image,  as  indicated  by  some sort of image mask.  Most image analysis
algorithms are fairly cpu intensive, hence as long as we can access  the
bad  pixel  list and region mask reasonably efficiently, we would prefer
a simple interface, e.g., for every buffer of input image data read,  an
associated  buffer  the  same size and dimensionality as the input image
data buffer, containing the bad pixel or region mask flag values.

In general, if pixel lists are to be used with images, either IMIO  must
provide  direct  support  for pixel lists or the pixel list package must
duplicate much of the functionality of IMIO.  This is because the  pixel
list  must  be  defined  in  terms  of  the  physical  image, whereas an
applications program accessing an image via IMIO may be  operating  upon
some  user  specified  section  of  the  image.  To support applications
transparent sectioning, boundary extension, multiple input buffers,  and
so on, support for pixel lists must be integrated into IMIO.



2.1 MASK IMAGES

    These  considerations  lead  us to make it possible for a pixel list
to appear to an application as a special type of  image  called  a  MASK
IMAGE,  even  though  the mask may be stored as a pixel list internally,
and accessed or queried directly as a list if desired.  If  whenever  we
read  a  block  of data from the data image, we read an equivalent block
of data from the mask image, it is evident  that  whatever  we  come  up
with  for  reading from the mask image is going to have to look an awful
lot   like   IMIO.    Given   the   complexities   of   image    section  
transformations,  automatic buffer allocation strategies, and so on, the
simplest solution is to just go ahead and use IMIO to access the virtual
mask  image.   This leads us to the interface shown in the figure below.
These routines represent an extension to IMIO to  support  pixel  lists.
The  conventional  IMIO  routines, used to access the mask "pixels", are
not shown.

The mask image may be opened by name with IM_PMMAP, or an already opened
pixel  mask,  perhaps  the  result  of  some  computation  done  by  the 


                                  -2-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



applications program, may be opened with IM_PMMAPO.   Alternatively,  if
the  mask  is  stored (or will be stored in the case of a new mask) in a
pixel list file (".pl"  extension),  the  mask  may  be  opened  with  a
conventional  IMMAP  call.   This  last  option  is especially powerful,
since it allows all  image  tasks  to  access  masks  as  if  they  were
conventional images, e.g., one can DISPLAY or IMCOPY a stored mask.

                  im = im_pmmap (maskname, mode, ref_im|NULL)
                 im = im_pmmapo (pm, ref_im)

                         imseti (im, IM_RLIO, YES|NO)
                         imseti (im, IM_PMDES, pm)
                   pm = imstati (im, IM_PMDES)

           bool = im_pmlne[123] (im[, lineno[, bandno]])
           bool = im_pmsne[123] (im, x1, x2[, y1, y2[, z1, z2]])
               bool = im_pmlnev (im, v)
               bool = im_pmsnev (im, vs, ve, ndim)

The  MODE  argument  to IM_PMMAP  specifies both the access mode for the
mask, and any standard transformations to be  performed  upon  the  mask
before  i/o  takes  place (if an existing mask is to be read).  NEW_FILE
mode is used to create a new mask; READ_ONLY to read an  existing  mask,
and  READ_WRITE  to  modify  an  existing mask.  The mode-transformation
flags currently supported are  INVERT_MASK,  which  performs  a  PIX_NOT
operation  on  the  input  mask,  and  BOOLEAN_MASK,  which  converts an
integer input mask to boolean.  Any more  complex  mask  transformations
or  combinations must be performed explicitly by the calling program via
calls to the PMIO or PLIO routines, mapping the resultant mask  onto  an
image descriptor with IM_PMMAPO.

If  a  reference  image  REF_IM is specified at open time, then the mask
image will inherit any  image  section,  boundary  extension,  etc.   in
effect  for  the reference image.  Inheritance occurs when the first i/o
to the mask image takes place.  The reserved names  "BPM"  and  "EMPTY",
respectively  (must  be  upper  case), denote the bad pixel mask for the
reference image, or an empty mask the size of the reference  image.   If
the  reference  image  does not have a bad pixel mask, BPM and EMPTY are
equivalent.  Note that separate image descriptors are used for the  data
(reference)  image  and  any  mask  images.  Multiple mask images may be
associated with the same reference image.

Normal IMIO calls, e.g., IMGS2I, are used to access the  mask  "pixels".
Since  it  is  common  for  a  mask to be empty over large regions of an
image, a set of boolean  functions  are  provided  for  testing  whether
regions  of  the  mask  are  nonempty,  allowing  a program to avoid the
expense of image mask i/o  and  subseqent  testing  of  the  mask  pixel
values  if  not needed.  The boolean functions IM_PMLNE (line not empty)
and IM_PMSNE  (section  not  empty)  and  their  more  general  variants
IM_PMLNEV  and  IM_PMSNEV  test whether the specified region of the mask
image contains any nonzero mask pixels.  The calling sequences of  these
routines  are patterned after the corresponding IMIO pixel i/o routines,


                                  -3-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



e.g., IM_PMLNE2 is  intended  for  use  with  the  IMGL2  routines,  and
IM_PMLNEV is intended for use with the IMGNL routines.

By default, mask image i/o operates on data buffers containing arrays of
pixels, as for a conventional data image.  When  i/o  takes  place,  the
interface   automatically   converts   between   pixel  format  and  the 
compressed line list format in which the mask is stored internally.   An
alternative  format  for  the mask data is RANGE LIST format, enabled by
setting the IM_RLIO parameter to YES in an IMSETI call.  Range list  i/o
works  identically to pixel i/o, except that the "pixel arrays" returned
by IMIO (or input to IMIO) are range  list  structures,  as  defined  in
<PLSET.H> and discussed in section 3.3.4.

Range  list  i/o  at  the IMIO level is fully general, i.e., the section
transformation, if any, is applied transparently to the calling program,
and  the  full  range  of  IMIO  i/o  routines may be used.  If the data
buffer is a multidimensional subraster, each line of the subraster  will
be a separate range list, and the physical length in pixels of each line
of the subraster will be as for a pixel subraster.  On a  read,  if  the
length  of  the  encoded range list exceeds the subraster line length in
pixels, and i/o error will occur.  Such an i/o error cannot  occur  when
i/o  is  restricted  to  lines or line segments (1D buffers), since IMIO
will automatically allocate a data  buffer  large  enough  to  hold  the
worst  case  (longest)  range  list.   Range  list  overflow  errors are
unlikely even for subrasters, however, since the range  list  format  is
normally  much  more compact than the equivalent pixel array (except for
very small subrasters or very complex masks).



2.2 MASKED IMAGE I/O (MIO)

    The mask image  i/o  routines  discussed  in  the  previous  section
provide  a  fully  generalized means for directly accessing a mask as an
separate entity, independent of the  associated  reference  data  image.
Two  separate  image  descriptors  are  required,  and  two parallel but
separate sets of calls to the  IMIO  routines.   In  many  applications,
however,  a mask is used only to specify those regions of the data image
to be analyzed or processed.  We want to access  those  regions  of  the
image  visible through the mask, but are not otherwise interested in the
mask itself.  The MASKED IMAGE I/O (MIO) interface is designed for  such
applications.

The  MIO  interface is summarized in the figure below.  A named mask may
be opened on a previously opened image with the MIO_OPEN procedure.   As
for  IM_PMOPEN,  the  reserved  names  "BPM"  and "EMPTY", respectively,
denote the bad pixel mask for the image, or an empty mask  the  size  of
the  image.   If the image does not have a bad pixel mask, an empty mask
will be opened.

The FLAGS argument, if nonzero,  specifies  an  operation  be  performed
upon  the  input mask to generate the mask to be used to access the data


                                  -4-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



image.    The   currently   supported   flags   are   INVERT_MASK    and  
BOOLEAN_MASK.   For  example,  when  the  mask  is  a  bad  pixel  mask, 
INVERT_MASK would cause MIO to access only that  portion  of  the  image
which  is  NOT covered by the bad pixel mask, i.e., the "good" region of
the image.  BOOLEAN_MASK is used to  convert  an  integer  mask  into  a
boolean  mask.   Note  that in the case of inversion of an integer mask,
the PIX_NOT operation merely complements the mask  pixel  values,  hence
will  not  affect  the REGION covered by the mask.  To invert an integer
mask in the region sense, use INVERT_MASK+BOOLEAN_MASK.

                  mp = mio_open (maskname, flags, im)
                 mp = mio_openo (pm, im)
              value = mio_stati (mp, param)
                       mio_seti (mp, param, value)
                   mio_setrange (mp, vs, ve, ndim)
   n|EOF = mio_[gp]lseg[silrdx] (mp, ptr, mval, v, npix)
                      mio_close (mp)

More general mask transformations must be carried out by the user  using
the  PMIO  package to directly compute the desired mask, the mapping the
mask onto an image descriptor with MIO_OPENO.   For  example,  given  as
input  a  bad  pixel  mask and a region mask, one could compute the mask
specifying all pixels in the region  mask  but  not  in  the  bad  pixel
mask.  Any general mask may be computed in this way.

An  MIO  application will not normally need to access the mask directly,
but if such access is required the mask descriptor may be obtained  with
a  call  to  MIO_STATI  to  fetch  the  value  of the parameter P_PMDES.
Similarly, the image descriptor may be  queried  as  parameter  P_IMDES,
and either parameter may be set with the corresponding call to MIO_SETI.

Successive  calls  to  a  get  or  put  line  segment  procedure,  e.g., 
MIO_GLSEGR (get line segment real), return line segments from  the  data
image  until  all  the data present in the area outlined by the mask has
been accessed, at which time EOF is  returned  as  the  function  value.
Each  line segment is returned along with a vector V specifying the line
of the image from which the segment is taken and the index of the  first
pixel  of  the current line segment within the line, a count NPIX of the
number of pixels in the line segment, and the mask value  MVAL  for  the
current  line  segment  (e.g., 1 for a boolean mask).  Each line segment
corresponds to a region of constant nonzero value (MVAL)  in  the  mask.
Line segments are returned sequentially in storage order.

By  default,  the  entire  region  of the image visible through the mask
will  be  accessed.   To  access  only  a  portion  of  the  image,  the 
IMIO_SETRANGE  procedure  may  be  called  before  performing any i/o to
specify the starting and ending vector coordinates  VS  and  VE  of  the
region  to  be  accessed.   Multiple  calls  may be made on the same MIO
descriptor to access multiple regions of the data image, or to  "rewind"
a given region of the image.




                                  -5-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



2.3 MASK IMAGE STORAGE

    As  we  shall  see  in the discussion of the pixel list package, the
pixel list package is designed to permit a list to be  stored  anywhere,
e.g.,  in  a binary file, in a database, as an array in an image header,
or merely as a temporary array in memory.  When the new image structures
become  available  storing  the masks in the image header or in a global
database will probably be the best approach, but  in  the  meantime  the
simplest  solution is to store each pixel list or mask in a small binary
file.  This approach has the  advantage  of  being  independent  of  the
particular  image  format  used  (none of which are currently capable of
storing the pixel list directly in any case).

If desired, the name of the mask file may be stored in the image  header
as  a  simple string valued parameter.  Alternatively, the mask name may
be input as a parameter when a task  is  run.   A  single  mask  may  be
associated  with  several  images, or several masks may be used with the
same image.  The approach to be followed for a particular program is  up
to the programmer or package designer.

The  bad  pixel  mask  is  a  special  case, since it has a well defined
logical meaning  for  an  image,  unlike  the  region  masks  which  are
application  specific.   The  most  straightforward approach is to use a
single boolean mask for the bad pixel list, using  the  optional  header
keyword  BPM  to store the mask name, which should normally be the image
name plus the pixel list file extension ".PL".   An  integer  BPM  could
also  be  used,  but most applications would treat it as a boolean mask,
treating any pixel with a nonzero value as a bad pixel.

Any additional information  required  to  describe  the  bad  pixels  is
application  specific,  and  may be stored in any of several ways, e.g.,
as a set of boolean masks, in  an  integer  mask,  using  flag  bits  or
reserved  values  to  describe each pixel or region, in a separate fully
populated weight image, or using the noise function package.  Most  IRAF
applications  will  probably use the BPM plus a noise function, with the
noise function being stored either as a one-dimensional noise  model  or
as  a separate uncertainty image, transparently to the application.  The
combination of a one-dimensional  noise  model  plus  a  compressed  bad
pixel  list  should  provide  an  efficient and flexible solution to the
pixel variance problem for most applications.



2.4 EXAMPLE

    Open a data image and the associated mask image, and sum the  pixels
within the area indicated by the mask.

    include <pmset.h>

    task    sum = t_sum



                                  -6-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



    # SUM -- Sum the image pixels lying within the given mask.

    procedure t_sum()

    char    image[SZ_FNAME]              # input data image
    char    mask[SZ_FNAME]               # image mask

    int     npix, mval, totpix, m_flags
    long    v[PM_MAXDIM]
    pointer im, mp, pp
    real    sum

    bool    clgetb()
    real    asumr()
    int     mio_glsegr()
    pointer immap(), mio_open()

    begin
            call clgstr ("image", image, SZ_FNAME)
            call clgstr ("mask", mask, SZ_FNAME)
            m_flags = 0
            if (clgetb ("invert"))
                m_flags = INVERT_MASK

            im = immap (image, READ_ONLY, 0)
            mp = mio_open (mask, m_flags, im)

            sum = 0;  totpix = 0
            while (mio_glsegr (mp, pp, mval, v, npix) != EOF) {
                sum = sum + asumr (Memr[pp], npix)
                totpix = totpix + npix
            }

            call mio_close (mp)
            call imunmap (im)

            call printf ("%d pixels, sum=%g, mean=%g\n")
                call pargi (totpix)
                call pargr (sum)
                if (totpix > 0)
                    call pargr (sum / totpix)
                else
                    call pargr (INDEF)
    end

A more complex application might use the spatial information provided by
V and NPIX, or the flag values provided by MVAL (for an  integer  mask).
For  example,  a  surface  fitting  routine  would  accumulate each line
segment into a least squares matrix, using  the  coordinate  information
provided as well as the pixel values.




                                  -7-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



2.5 THE PIXEL MASK PACKAGE (PMIO)

    We  have  thus  far  discussed two quite different interfaces, i.e.,
the use of IMIO to do pixel i/o to a  mask  mapped  as  a  virtual  mask
image,  and  the  MIO  interface,  used  to access the portion of a data
image visible through a mask.  The next step is to define the  interface
used  to access the mask object directly as a MASK, independently of the
use of masks for image i/o.

            pm = pm_newmask (ref_im, depth)

               pm = pm_open (bufptr|NULL)
             pm = pm_create (naxes, axlen, depth)
            pm = pm_newcopy (pm)
                   pm_close (pm)

                pm_[sg]size (pm, naxes, alxen, depth)
                    pm_seti (pm, param, value)
           value = pm_stati (pm, param)
                   pm_debug (pm, outfd, maxcol, flags)
            bool = pm_empty (pm)
                pm_compress (pm)
                   pm_clear (pm)

                    pm_load (pm, bufptr)
           nwords = pm_save (pm, bufptr, buflen)
                   pm_loadf (pm, fname, title, maxch)
                   pm_savef (pm, fname, title, save_flags)
           pm_[load|save]im (pm, imname[, save_flags])

            ptr = pm_access (pm, v)
     bool = pm_linenotempty (pm, v)
     bool = pm_sectnotempty (pm, vs, ve, ndim)
          pm[gp]l[lrp][sil] (pm, v, buf, b_depth, npix, rop)

          pm_[set|get]plane (pm, v)
                   pm_point (pm, x, y, rop)
                  pm_circle (pm, x, y, r, rop)
                     pm_box (pm, x1,y1, x2,y2, rop)
                    pm_line (pm, x1,y1, x2,y2, width, rop)
                 pm_polygon (pm, x, y, npts, rop)

                     pm_rop (pm_src, vs, pm_dst, vs, vn, rop)
                 pm_stencil (pm_src, vs, pm_dst, vs, pm_stl, vs, vn, rop)

There are two variants on this lowest level  interface,  known  as  PMIO
(pixel  mask  i/o)  and PLIO (pixel list i/o).  These two interfaces are
equivalent with one difference: PMIO can accept a  reference  image  and
inherit  the section transformation of the reference image, allowing the
mask to be accessed in the coordinate system  of  the  reference  image,
while  PLIO  is  a  stand  alone interface, implemented independently of
IMIO without any ties to IMIO.  PMIO is  implemented  as  a  thin  layer


                                  -8-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



upon  PLIO,  with  ties to IMIO to access the section transformation for
the reference image.

The PMIO interface is shown in the figure above.  With the exception  of
the  additional routine PM_NEWMASK, used to create a new, empty mask the
same size as a reference image, the PMIO routines are identical  to  the
corresponding  PLIO  routines  except for the PM package prefix, and the
implied section  transformation.   Indeed,  if  no  reference  image  is
specified  or  if  the  section transformation is unitary (the reference
image was opened without an  image  section),  the  two  interfaces  are
identical.   Hence the discussion of PLIO in the next section will serve
to document PMIO as well.

To use PMIO, merely include <PMSET.H> rather  than  <PLSET.H>,  and  set
the reference image with a call to PM_SETI, e.g.,

        call pm_seti (pm, P_REFIM, ref_im)

This  step  can be skipped if PM_NEWMASK or PM_NEWCOPY is used to create
a new mask, as the reference image will be inherited by the new mask.

Programs which use PMIO to access a mask may  also  use  the  low  level
line,   range,   and  pixel  list  routines  discussed  in  section  3.1 
(PL_RANGEROP etc.) on lists returned  by  PMIO,  since  PMIO  will  have
already   transformed  the  data  into  the  coordinate  system  of  the 
reference image.

In general, the PMIO interface should be  used  in  preference  to  PLIO
whenever  the mask to be accessed is logically associated with some data
image or images.  The region description and logical  region  processing
capabilities  of PLIO are very powerful in their own right, however, and
PLIO should be used directly by applications which do not  consider  the
mask  to be merely an overlay for a data image.  An example would be any
application which operates upon a  2-dimensional  data  structure  other
than an image (e.g., region filtering in the POE image kernel).



3. THE PIXEL LIST PACKAGE (PLIO)

    A  pixel list is a way of representing an N-dimensional image matrix
which is well suited for applications where  the  represented  image  is
sparse,   or  consists  of  a  moderate  number  of  arbitrarily  shaped 
regions.  Routines are provided for creating new lists, for  writing  to
or  reading  from  lists,  for  storing  or  retrieving  lists,  and for
performing various types of operations upon entire  lists  to  make  new
lists.   The  full  set of routines in the package are summarized in the
figure below.

A pixel list, like an image, has a fixed dimensionality and  size  which
is  determined  at list creation time for the lifetime of the list.  New
lists are created with PL_CREATE, which returns a pointer  to  an  empty


                                  -9-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



list.   The  DEPTH  parameter  specifies  the depth of the list in bits,
i.e., the number of bits per pixel, in the range 1-27.  A  boolean  list
has  a  depth  of 1 bit.  In the current implementation the boolean mask
is handled as a degenerate case of an integer  mask,  i.e.,  an  integer
mask which happens to have mask values in the range 0-1.

An  existing  list  is accessed by opening a descriptor with PL_OPEN and
loading the list  into  the  runtime  descriptor  structure,  either  by
specifying  a  non-NULL  buffer pointer BUFPTR, or by calling one of the
PL_LOAD functions after opening a null descriptor.

               pl = pl_open (bufptr|NULL)
             pl = pl_create (naxes, axlen, depth)
            pl = pl_newcopy (pl)
                   pl_close (pl)

                pl_[sg]size (pl, naxes, axlen, depth)
                    pl_seti (pl, param, value)
           value = pl_stati (pl, param)
                   pl_debug (pl, outfd, maxcol, flags)
            bool = pl_empty (pl)
                pl_compress (pl)
                   pl_clear (pl)

                    pl_load (pl, bufptr)
           nwords = pl_save (pl, bufptr, buflen)
                   pl_loadf (pl, fname, title, maxch)
                   pl_savef (pl, fname, title, save_flags)
           pl_[load|save]im (pl, imname[, save_flags])

            ptr = pl_access (pl, v)
     bool = pl_linenotempty (pl, v)
     bool = pl_sectnotempty (pl, vs, ve, ndim)
          pl[gp]l[lrp][sil] (pl, v, buf, b_depth, npix, rop)

          pl_[set|get]plane (pl, v)
                   pl_point (pl, x, y, rop)
                  pl_circle (pl, x, y, r, rop)
                     pl_box (pl, x1,y1, x2,y2, rop)
                    pl_line (pl, x1,y1, x2,y2, width, rop)
                 pl_polygon (pl, x, y, npts, rop)

                     pl_rop (pl_src, vs, pl_dst, vs, vn, rop)
                 pl_stencil (pl_src, vs, pl_dst, vs, pl_stl, vs, vn, rop)

Pixel lists are stored externally as opaque  binary  byte  arrays.   The
function  PL_SAVE  will encode a pixel list as a byte array and store it
in the indicated buffer, resizing the buffer if  necessary.   If  BUFPTR
is  NULL  a  new  buffer  will  be allocated, overwriting the NULL.  The
PL_LOAD  function  performs  the  inverse  function.   The  F   suffixed 
functions  are  provided  for  convenience  when  storing lists in small
binary files.  The IM suffixed functions  create  masks  out  of  actual


                                 -10-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



data  images,  and  vice  versa.   In  the  most general case, a list is
encoded into an array in memory and then stored away by the applications
wherever  they wish, e.g., as an array parameter in an image header when
the new image structures become available.

Pixel  list  i/o  is  provided  via  the  PL[GP]L[LRP][SIL]  family   of 
functions,  which  read,  write,  or  edit  (via  the ROP) lines or line
segments of masks.  The naming convention is as follows:

         pl             package prefix
        [gp]            get or put
         l              line segment
        [lrp]           as a line list, range list, or pixel array
        [sil]           in an array of type short, int, or long

For example, PLGLPS would get a line  from  a  mask  image  as  a  fully
populated  array of type short.  For maximum efficiency, since this is a
low level interface, the data  is  read  from  or  copied  into  a  user
allocated  buffer, rather than having the pixel list package control the
buffer.

The functions PLGLL[SIL] return the packed line list for  the  indicated
line  or  line  segment.   This  is the copy-out form of access with the
least overhead, but requires that the application have knowledge of  the
internal line list format.

Alternatively,  if it is only desired to read from a list, accessing the
list in the internal format, the internal list for an image line may  be
directly  accessed  by pointer with the PL_ACCESS function.  This is the
most efficient form of access.  The variant PL_LINENOTEMPTY  is  similar
except  that  the  NULL pointer is returned if the indicated line of the
list is empty, providing an efficient and convenient way to perform  the
empty test on mask image lines.

The  functions  PLGLR[SIL]  are  similar  to  the  get line list form of
access, but instead of returning the encoded list-list in  the  internal
format,  it  returns  a simple array of ranges of absolute pixel indices
and associated mask values.  This is the recommended  way  of  accessing
the  mask  as  a  list  structured  object,  since  it  does not require
knowledge of the internal packed line  list  format.   For  example,  to
print line V of the mask on descriptor PL as a series of range lists:

        int     buf[3,1024], n, i, plglri()

        n = plglri (pl, v, buf, 0, axlen[1], 0)
        do i = 1, n {
            call printf ("range at %d, %d pixels, mask value = %o\n")
                call pargi (buf[1,i]);  call pargi (buf[2,i])
                call pargi (buf[3,i])
        }

These  routines  require  that  the  depth in bits of the output line or


                                 -11-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



range list or pixel array be specified.   This  is  necessary  to  avoid
generating  numbers  the  size  of  the machine integer when inverting a
mask (PIX_NOT), e.g., if the mask depth is 8 bits, the complement  of  a
0  pixel should be 377, not 37777777777.  The depth argument may also be
used to convert an integer mask to a boolean mask, or vice versa  (using
the  PIX_VALUE field of the rasterop discussed in the next section).  If
B_VALUE is zero, clipping of the output values is disabled.  This  would
be  appropriate,  for  example,  when simply reading from a mask without
modifying the pixel values.

New pixel lists may be created by having  the  application  prepare  the
packed  line  lists  externally,  inserting them directly into the pixel
list structure with a  PUT  routine.   This  is  generally  inadvisable,
however,  because  the packed line list format is considered internal to
the PLIO package.  A better alternative is to input the mask data  as  a
populated  array  or  as a range list, letting the PL package manage the
internal line list.

A more convenient approach to  creating  or  modifying  masks  for  most
applications  is  to  define  the mask by specifying a series of include
and exclude standard region types (circles,  boxes,  lines,  points,  or
polygons),  using  the  block  of routines beginning with PL_SETPLANE in
the figure.  Note that these are two  dimensional  operators;  they  are
provided  for convenience even though the pixel list package can support
images of any dimension (if the  image  has  three  or  more  dimensions
PL_SETPLANE  may be used to specify the plane to be operated upon).  The
most general routine is PL_POLYGON, which may be used  to  operate  upon
the  pixels  in  the interior of any general polygon.  All of the region
drawing operators will permit regions to extend beyond the  boundary  of
the mask, clipping as necessary at the boundary.



3.1 PIXEL, LINE, AND RANGE LIST ROUTINES

    Most  of  the  N  dimensional  region or mask oriented PMIO and PLIO
routines eventually result in calls to the low level  pixel,  line,  and
range  rasterop  routines  and  format  conversion routines shown in the
figure below.  These routines form  the  functional  core  of  the  PLIO
package  and will often be responsible for most of the execution time of
routines which use PLIO.

There are two main classes of routines.  The PL_PIXROP, PL_LINEROP,  and
PL_RANGEROP  routines  perform  the  general  raster  operation on pixel
arrays,  line  lists,  and  range  lists.   The  PL_LINESTENCIL  routine 
performs  the stencil rasterop operation upon line lists; currently only
a list list version is available since this is a  rarely  used  routine.
Lastly,  a  set  of six routines are provided for converting between any
two of the three formats, e.g., line list to range list or  pixel  array
and  vice  versa,  omitting  the like-to-like conversions.  For example,
PL_P2RI would convert a pixel array  to  a  range  list,  both  of  type
integer.


                                 -12-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



                 pl_linerop (ll_src, xs, src_maxval,
                             ll_dst, ds, dst_maxval, ll_out, npix, rop)
             pl_linestencil (ll_src, xs, src_maxval, ll_dst, ds, dst_maxval,
                             ll_stn, xs, ll_out, npix, rop)

             pl_pixrop[sil] (px_src, xs, src_maxval,
                             px_dst, ds, dst_maxval, npix, rop)
           pl_rangerop[sil] (rl_src, xs, src_maxval,
                             rl_dst, ds, dst_maxval, rl_out, npix, rop)

    n = pl_[lrp]2[lrp][sil] (op_src, xs, op_dst, npix)

Note  that  these low level routines specify the mask depth as a maximum
pixel value, rather than taking the depth in  bits  as  the  high  level
PMIO  and  PLIO  routines  do,  and  that there are no "PM_" versions of
these routines - the one set of routines may be used with both PLIO  and
PMIO.



3.2 RASTEROPS

    The  argument  ROP  in the circle, box, and other routines discussed
in the previous sections is called a RASTEROP, and specifies the bitwise
operation  to be performed to generate the destination operand.  Much of
the generality and conciseness of the pixel list package is due  to  the
rasterop  abstraction, which is patterned after a similar construct used
by the Sun Microsystems SUNVIEW interface  to  specify  operations  upon
PIXRECTS, which are logically similar to PLIO masks.

The  rasterop  defines  the  operation  to  be performed to generate the
destination mask, in terms of bitwise boolean operations performed  upon
the  input  source and destination masks.  Rasterops are constructed via
a series of bitwise AND and OR operations,  using  the  following  macro
defines:

        PIX_SRC                   specifies the source mask
        PIX_DST                   specifies the destination mask
        PIX_NOT(op)               inverts the operand mask
        PIX_VALUE(value)          specifies the bitplanes to be set

Examples  of  some  of  the  possible  operations  (out of a total of 16
possible operations) are shown below.  This  table  is  reproduced  from
the SunView Pixrect Reference Manual.










                                 -13-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



             RASTEROP                        DESCRIPTION

        PIX_SRC                   copy source to destination
        PIX_DST                   no-op
        PIX_SRC | PIX_DST         paint (OR source to destination)
        PIX_SRC & PIX_DST         mask (AND of source and destination)
        PIX_NOT(PIX_SRC)&PIX_DST  erase (AND destination with negation
                                    of source)
        PIX_NOT(PIX_DST)          invert area (negate the existing
                                    values)
        PIX_SRC ^ PIX_DST         inverting paint (XOR of source and
                                    destination)

Here,  the  |&^  denote  the  SPP  OR, AND, and XOR intrinsic functions,
which must be used to construct  actual  rasterop  expressions  in  SPP,
e.g.:

        PIX_NOT(PIX_SRC) | PIX_DST | PIX_VALUE(v)

would actually be written as

        or (PIX_NOT(PIX_SRC), PIX_DST) + PIX_VALUE(v)

The following additional macros are defined to deal with the more common
cases of setting or clearing a region.

        PIX_SET                   (PIX_SRC | PIX_NOT(PIX_SRC))
        PIX_CLR                   (PIX_SRC & PIX_NOT(PIX_SRC))

As a simple example, consider the case of specifying a region mask as  a
series  of include and exclude circles and boxes.  This is trivial for a
boolean mask: an include circle or box  is  specified  by  the  rasterop
PIX_SET,  and  an  exclude by PIX_CLR.  In the equivalent operation upon
an integer mask this would cause any mask values which had already  been
set   to   be   replaced,   hence   it  might  be  desirable  to  use  a 
PIX_SRC|PIX_DST rasterop instead, to OR the bits of the new flag  values
into  those  of  any  flag  values  already  set.  Similarly, when using
PL_LTOP to unpack a line list into a pixel  array,  the  PIX_SRC|PIX_DST
rasterop  might  be  specified  to  OR the mask segment into an existing
pixel array.

General bitwise boolean operations upon masks are provided by the PL_ROP
and PL_STENCIL operators, which operate upon entire masks or rectangular
subregions of masks.   The  PL_ROP  operator  combines  the  source  and
destination  masks  to  produce a new mask; PL_STENCIL performs the same
operation, but only in the regions specified by the stencil mask,  which
must  be a boolean mask.  The input mask may be NULL (depending upon the
rasterop specified), or the source and  destination  masks  may  be  the
same.

The  equivalent  operators for line lists, range lists, and pixel arrays
are the PL_S2D family of routines, where  S=D=[LRP]  for  a  line  list,


                                 -14-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



range  list,  or pixel array rop.  The routine PL_LINESTENCIL implements
the stencil operation for a line list.

As noted above, when operating upon  integer  masks  (DEPTH  >  1),  the
PIX_VALUE  macro  is  used  to  specify the flag value for the indicated
region.  For example, the following rasterop would set  all  the  pixels
in a region to the same value:

        PIX_VALUE(value)

to OR in the new value instead of replacing any existing flag values:

        PIX_VALUE(value) | PIX_DST

If  a  boolean  mask  is  to  be  written  to an integer mask, PIX_VALUE
specifies the flag value to be used for the regions  set  to  1  in  the
input  boolean  mask.  For example, one might wish to combine a set of 8
boolean masks to form a single 8 bit deep integer mask,  with  each  bit
in  the  integer  mask  corresponding  to one of the input boolean masks
(001 = mask 1, 002 = mask 2, 040 = mask 3, etc.).  This  could  be  done
using   the   rasterop  shown  above,  incrementing  PIX_VALUE  in  each 
operation to specify the bitplane to be set.



3.2.1 RASTEROP EXPRESSION EVALUATION

    As mentioned above, there are sixteen possible ways to  combine  the
source  and  destination  masks  subject  to  the  four possible boolean
operations (AND, OR, XOR, and NOT).  More precisely,  although  numerous
bitwise  expressions  can  be constructed, many of these are equivalent,
and  there  are  only  sixteen  fundamental   operations.    These   are 
summarized in the following table.

                Operation                             Opcode

        PIX_CLR                                         00
        PIX_SET                                         17

        PIX_SRC                                         14
        PIX_DST                                         12

        PIX_NOT(PIX_SRC)                                03
        PIX_NOT(PIX_DST)                                05

        PIX_SRC & PIX_DST                               10
        PIX_SRC | PIX_DST                               16
        PIX_SRC ^ PIX_DST                               06

        PIX_SRC & PIX_NOT(PIX_DST)                      04
        PIX_SRC | PIX_NOT(PIX_DST)                      15
        PIX_NOT(PIX_SRC) & PIX_DST                      02


                                 -15-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



        PIX_NOT(PIX_SRC) | PIX_DST                      13

        PIX_NOT (PIX_SRC & PIX_DST)                     07
        PIX_NOT (PIX_SRC | PIX_DST)                     01
        PIX_NOT (PIX_SRC ^ PIX_DST)                     11

As  an  example  of  the  redundancy  of arbitrary rasterop expressions,
compare the following with the equivalent expressions (same  opcode)  in
the table above.

        PIX_NOT(PIX_SRC) & PIX_NOT(PIX_DST)             01
        PIX_NOT(PIX_SRC) ^ PIX_NOT(PIX_DST)             06
        PIX_NOT(PIX_SRC) | PIX_NOT(PIX_DST)             07
        PIX_NOT(PIX_SRC) ^ PIX_DST                      11
        PIX_SRC ^ PIX_NOT(PIX_DST)                      11

Any   number  of  additional  logically  redundant  expressions  may  be 
constructed.  The programmer should not worry about simplifying  logical
expressions,  but  should choose instead whatever expression is clearest
for  their  particular  application,  letting   the   interface   handle 
expression optimization internally.

Of  the  sixteen possible fundamental operations, there are four trivial
operations (CLR, SET, SRC, DST), seven composite  operations,  and  four
primary  operations,  namely,  AND,  OR,  XOR, and NOT (two cases of the
latter).  The composite operations are all implementable as two  primary
operations  in  sequence.  PIX_NOT is implemented by actual inversion of
the list rather than as a mode flag, to  avoid  complications  when  the
list is read.



3.2.2 RASTEROP ENCODING

    The  rasterop argument specifies the bitwise boolean operation to be
performed, and optionally the pixel value to be used (in the case of  an
integer  mask).  Both are specified as a single integer value, packed as
shown in the figure below.

        +--+-------------+--------+
        |32|31          5|4      1|
        +--+-------------+--------+
        |  | pixel value | opcode |
        +--+----------------------+

The following is an example of a typical rasterop (note that  since  the
pixel  value  field  has a reserved range of bits which is zero prior to
expression  evaluation,  the  "+"  operator  is  equivalent  to  the  OR 
intrinsic function).

        or(PIX_SRC, PIX_NOT(PIX_DST)) + PIX_VALUE(pix_value)



                                 -16-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



Note  that the width of the pixel value field in the rasterop constrains
the effective mask depth to be 27 bits or less, if  full  generality  is
desired  in  rasterop  operations.   Masks of up to 31 bits (the minimum
unsigned precision of a LONG) can be stored and accessed, but  rasterops
using PIX_VALUE are limited to 27 bits.



3.3 PIXEL LIST DATA STRUCTURES

    A  pixel  list  consists  of  an array of pointers to the LINE LISTS
forming the mask.  There is one pointer for  each  image  line;  if  the
pointer  is  NULL,  no mask values are set on the associated image line.
N-dimensional images are easily handled by an N-1 dimensional  array  of
line pointers.

Each  line  list  consists  of a series of offsets and mask pixel values
(the pixel values  are  normally  omitted  for  a  boolean  mask).   The
offsets  specify  the  number  of pixels for which the mask has the same
value.   This  line  list  format  has  the  following  two  significant 
advantages  over  the  alternative  technique  of  specifying  a list of
ranges using absolute pixel coordinates:

    [1] A higher degree of data compression is  possible.   If  absolute
        pixel  coordinates  are  used  in  the list, the list must be an
        array of 32 bit integer values  in  order  to  avoid  a  builtin
        limit  on  the  size  of the image which can be represented.  By
        using offsets, list elements as small as one byte are possible.
    
    [2] A  list  composed  of  offsets  is  invariant  with  respect  to 
        translation.   For  example,  when  extracting a subraster of an
        image, one can extract the corresponding segment  of  each  line
        list  and  perhaps  edit the first element, and the remainder of
        the list may be used without change.

When describing regular regions such as boxes it will often be the  case
that  successive  lines  of  the  mask  are  equivalent,  in  which case
multiple line list pointers may point to the  same  line  list.   Hence,
the  line  lists will provide good compression of regular objects in any
two dimensional plane of the mask.  This technique can  be  extended  to
higher  dimensions  if  desirable,  without affecting the line list data
structures visible to an application.



3.3.1 LINE LIST ENCODING

    A good compromise  between  storage  efficiency  and  efficiency  of
runtime  access, while keeping things simple, is achieved if we maintain
the compressed line lists  as  variable  length  arrays  of  type  short
integer  (16  bits  per  list element), regardless of the mask depth.  A
line list  consists  of  a  series  of  simple  INSTRUCTIONS  which  are


                                 -17-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



executed  in  sequence  to  reconstruct a line of the mask.  Each 16 bit
instruction consists of the sign bit (not used at present), a three  bit
OPCODE, and twelve bits of data, i.e.:

        +--+-----------+-----------------------------+
        |16|15       13|12                          1|
        +--+-----------+-----------------------------+
        |  |   opcode  |            data             |
        +--+-----------------------------------------+

The  significance  of  the  data  depends  upon  the  instruction.   The 
instructions currently implemented are summarized in the table below.

     Instruction     Opcode           Description

        ZN            00        Output N zeros
        HN            04        Output N high values
        PN            05        Output N-1 zeros plus one high value
        SH            01        Set high value, absolute
        IH,DH         02,03     Increment or decrement high value
        IS,DS         06,07     Like IH-DH, plus output one high value

In order to reconstruct a mask line,  the  application  executing  these
instructions  is  required to keep track of two values, the CURRENT HIGH
VALUE and the  CURRENT  POSITION  in  the  output  line.   The  detailed
operation of each instruction is as follows:

    ZN      Zero the next N (=DATA) output pixels.
    
    HN      Set the next N output pixels to the current high value.
    
    PN      Zero  the  next  N-1  output  pixels, and set pixel N to the
            current high value.
    
    SH      Set the  high  value  (absolute  rather  than  incremental),
            taking   the  high  15  bits  from  the  next  word  in  the 
            instruction stream, and the low 12  bits  from  the  current
            data value.
    
    IH,DH   Increment  (IH)  or decrement (DH) the current high value by
            the DATA value.  The current position is not affected.
    
    IS,DS   Increment (IS) or decrement (DS) the current high  value  by
            the DATA value, and STEP, i.e., output one high value.

The  high  value  is  assumed to be set to 1 at the beginning of a line,
hence the IH,DH and IS,DS  instructions  are  not  normally  needed  for
boolean  masks.   If  the  length of a line segment of constant value or
the difference between two  successive  high  values  exceeds  4096  (12
bits),  then  multiple instructions are required to describe the segment
or intensity change.



                                 -18-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



The performance  of  this  encoding  is  very  good  for  typical  masks
consisisting  of  isolated high or low values or extended regions at the
same level.  The worst case performance occurs  when  successive  pixels
have  different  values.   Even  in  this  case  the  encoding will only
require one word (16 bits) per mask pixel,  provided  either  the  delta
intensity  change  between  pixels  is usually less than 12 bits, or the
mask represents a zero floored step function of  constant  height.   The
worst  case  cannot  exceed  npix*2  words provided the mask depth is 24
bits or less.



3.3.2 EXAMPLE: LINE LIST ENCODING

    As a simple example, consider the following line of a boolean  mask.
The  set  pixels  are 1, 4, 8 through 11, and so on, shown as INDEX LIST
in the figure.  The corresponding OFFSET LIST (line  list  encoding)  is
also  shown.  Note that both encodings require the same amount of space,
assuming 16 bits per list element in both cases; the  index  list  would
require twice as much space if 32 bit list elements were used.

        Index list:     1, 4, 8-11, 15, 23-39           7 words
        Offset list:    P1 P3 Z3 H4 P4 Z7 H17           7 words

        Inverted I-L:   2-3, 5-7, 12-14, 16-22          8 words
        Inverted O-L:   Z1 H2 Z1 H3 Z4 H3 Z1 H7         8 words

The  bottom  half  of  the  figure  shows the encodings for the inverted
lists, i.e., the lists which would be produced  by  a  PIX_NOT  rasterop
operation.   Since  both  encodings  reflect  only  the points in a line
where level changes occur, the information content and list size of  the
normal  and  inverted lists are comparable.  The encoding for an integer
mask would be equivalent except for the addition of occasional SH or  SL
instructions to set the high value.



3.3.3 LINE LIST STRUCTURE

    The  full  line  list  structure consists of a header describing the
line list entry in the PLIO descriptor, plus  the  LL  encoding  of  the
line,  as  illustrated  below.  This information is internal to the PLIO
package and should not be used in applications code.

        define  LL_START        4
        struct linelist {
                short   nref            # number of lines pointing here
                short   blen            # length of buffer containing list
                short   len             # encoded linelist length, words
                short   ll[]            # encoded pixel data
        }



                                 -19-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



The linelist encoding includes any trailing zeros,  i.e.,  executing  of
the encoded instructions will regenerate the entire mask line.



3.3.4 RANGE LIST STRUCTURE

    The  range list structure provides applications programs with a list
representation of a mask, for cases where it  would  be  inefficient  or
inconvenient  to  access the mask as a pixel array.  Range lists are not
used to store masks in external storage, hence data compression  is  not
an issue, nor is machine independence.

        rtype = short|int|long
        struct rangelist {
                rtype   x               # x coordinate of first pixel
                rtype   n               # number of pixels in range
                rtype   v               # pixel value
        }

        int     rl[3,ARB]               # typical range list array decl

The  range  list  structure  is defined in <plset.h>, e.g. (refer to the
actual file for more reliable documentation for these definitions):

        RL_FIRST        # first data range entry in list
        RL_LENELEM      # size of each element of list (i.e., 3)
        RL_MAXLEN       # maximum range list length (arg=pl)

        RL_LEN          # physical length of range list (RL_LEN(rl))
        RL_AXLEN        # length of mask image line (RL_AXLEN(rl))
        RLI_LEN         # RL_LEN for rl = ptr to int
        RLI_AXLEN       # RL_AXLEN  "     "     "
        RLS_LEN         # RL_LEN for rl = ptr to int
        RLS_AXLEN       # RL_AXLEN  "     "     "

        RL_X            # use as RL_X(rl,i), rl = range list array
        RL_N            # Npix field of range list array element
        RL_V            # Value field of range list array element

        RL_XOFF         # offset of xstart field 
        RL_NOFF         # offset of npix field
        RL_VOFF         # offset of value field

The range list is represented as a simple  two  dimensional  integer  or
short  integer  array.   The  first line of the two dimensional array is
used as the RANGE LIST HEADER, and is used to store the  LEN  and  AXLEN
parameters  describing  the  encoded  mask  line.  Each subsequent entry
defines a  range  NPIX  of  mask  image  pixels,  starting  at  pixel  X
(absolute  pixel  coordinates), all of which have the value VALUE.  Only
nonzero ranges are stored.  Note that the LEN field defines  the  entire
length of the structure, including the header range and data ranges.


                                 -20-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



3.3.5 EXAMPLE: A SMALL MASK

    A  complete  example  of  a  small  mask (75 columns by 40 lines) is
shown below.  This mask and the sample output were prepared by the  PLIO
debug interpreter, file ZZDEBUG.X in the PLIO source directory.

40 .1111111..............................................................22222
39 .1111111..............................................................22222
38 .1111111...............................................................2222
37 .1111111...............................................................2222
36 .1111111............................................................4......
35 .1111111.....................11111111111111111111111111...........4444.....
34 .1111111.....................11111111111111111111111111........44444444....
33 .1111111......................1111111111111111111111111......44444444......
32 .1111111......................1111111111111111111111111...44444444.........
31 .1111111......................1111111111111111111111111.44444444...........
30 .1111111...........4..........1111111111111111111111115444444..............
29 .1111111...........4..........11111111111111111111155554444................
28 .1111111...........4..........111111111111111111155555544..................
27 .1111111...........4..........1111111111111111555555551....................
26 .1111111.....................11111111111111155555555111....................
25 .1111111.....................11111111111115555555111111....................
24 ............................1111111111155444444.1111111....................
23 ...........................111111111155544444....111111....................
22 ..............1...........1111111155555444........11111....................
21 ........................1111111155555554..........11111....................
20 ........................111111555555511...........11111....................
19 ........................111555555551111...........11111....................
18 ........................155555555111111...........11111....................
17 ......................445555551111111111.........111111....................
16 ....................444455551111111111111.......1111111....................
15 ..................4444445111111111111111111111111111111....................
14 ...............44444444.1111111111111111111111111111111....................
13 .............44444444......................................................
12 ..........44444444.........................................................
11 ........44444444...........................................................
10 .........4444........................22222.................................
 9 ..........4.........................2222222..............22222.............
 8 ....................................2222222.............2222222............
 7 ....................................2222222.............2222222............
 6 .....................................22222..............2222222............
 5 11111111111111111111.....................................22222.............
 4 11111111111111111111.......................................................
 3 11111111111111111111.......................................................
 2 11111111111111111111.......................................................
 1 11111111111111111111.......................................................
   123456789012345678901234567890123456789012345678901234567890123456789012345
            1         2         3         4         5         6         7     

This  first  figure  shows  the  mask  itself,  output  graphically as a
character matrix.  This is an integer mask wherein the integer value  of
each  pixel  is  the  ASCII  value of the character shown.  The mask was


                                 -21-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



created by OR-in a number of regions together, using  a  different  mask
value  for each region.  The result in areas where the regions intersect
is a new mask pixel value.

The figure below shows the internal data structures  used  to  represent
the  previous  mask.   Both the line list and range list representations
of the mask are shown.  The size of the packed line list is  582  words,
189  of which are free (no longer used due to updates), hence the packed
line list size would be 393 words following a  call  to  PL_COMPRESS  to
compress the mask.

    Mask 1EECD naxes=2 [75,40] maxval=177 plane=[75,40]
    max buffered line size 1024, max actual line size 16
    40 lines total, 40 are nonempty, mask is nonempty
    llbp=42AF5, len=1190, op=583, free=189, nupdates=35

    Index at 1EFF1 containing 40 lines:
         4     4     4     4    17    26    35    35   166   177   187
       194   201   208   218   228   241   254   266   554   292   568
       319   333   347   360   492   507   523   539   423   435   447
       459   471   483   148   148   157   157

    Line list containing 40 lines:
    [1:4]      IH48(49) H20 Z55 (75,49)
    [5]        IH48(49) H20 IH1(50) Z37 H5 Z13 (75,50)
    [6]        IH49(50) Z37 H5 Z14 H7 Z12 (75,50)
    [7:8]      IH49(50) Z36 H7 Z13 H7 Z12 (75,50)
    [9]        IH51(52) P11 DH2(50) Z25 H7 Z14 H5 Z13 (75,50)
    [10]       IH51(52) Z9 H4 DH2(50) Z24 H5 Z33 (75,50)
    [11]       IH51(52) Z8 H8 Z59 (75,52)
    [12]       IH51(52) Z10 H8 Z57 (75,52)
    [13]       IH51(52) Z13 H8 Z54 (75,52)
    [14]       IH51(52) Z15 H8 DH3(49) Z1 H31 Z20 (75,49)
    [15]       IH51(52) Z18 H6 IS1(53) DH4(49) H30 Z20 (75,49)
    [16]       IH51(52) Z20 H4 IH1(53) H4 DH4(49) H13 Z7 H7 Z20 (75,49)
    [17]       IH51(52) Z22 H2 IH1(53) H6 DH4(49) H10 Z9 H6 Z20 (75,49)
    [18]       IH48(49) P25 IH4(53) H8 DH4(49) H6 Z11 H5 Z20 (75,49)
    [19]       IH48(49) Z24 H3 IH4(53) H8 DH4(49) H4 Z11 H5 Z20 (75,49)
    [20]       IH48(49) Z24 H6 IH4(53) H7 DH4(49) H2 Z11 H5 Z20 (75,49)
    [21]       IH48(49) Z24 H8 IH4(53) H7 DS1(52) DH3(49) Z10 H5 Z20
               (75,49)
    [22]       IH48(49) P15 Z11 H8 IH4(53) H5 DH1(52) H3 DH3(49) Z8 H5
               Z20 (75,49)
    [23]       IH48(49) Z27 H10 IH4(53) H3 DH1(52) H5 DH3(49) Z4 H6 Z20
               (75,49)
    [24]       IH48(49) Z28 H11 IH4(53) H2 DH1(52) H6 DH3(49) Z1 H7 Z20
               (75,49)
    [25]       IH48(49) Z1 H7 Z21 H13 IH4(53) H7 DH4(49) H6 Z20 (75,49)
    [26]       IH48(49) Z1 H7 Z21 H15 IH4(53) H8 DH4(49) H3 Z20 (75,49)
    [27]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H16 IH4(53) H8
               DS4(49) Z20 (75,49)
    [28]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H19 IH4(53) H6


                                 -22-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



               DH1(52) H2 Z18 (75,52)
    [29]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H21 IH4(53) H4
               DH1(52) H4 Z16 (75,52)
    [30]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H24 IS4(53)
               DH1(52) H6 Z14 (75,52)
    [31]       IH48(49) Z1 H7 Z22 H25 IH3(52) Z1 H8 Z11 (75,52)
    [32]       IH48(49) Z1 H7 Z22 H25 IH3(52) Z3 H8 Z9 (75,52)
    [33]       IH48(49) Z1 H7 Z22 H25 IH3(52) Z6 H8 Z6 (75,52)
    [34]       IH48(49) Z1 H7 Z21 H26 IH3(52) Z8 H8 Z4 (75,52)
    [35]       IH48(49) Z1 H7 Z21 H26 IH3(52) Z11 H4 Z5 (75,52)
    [36]       IH48(49) Z1 H7 IH3(52) P61 Z6 (75,52)
    [37:38]    IH48(49) Z1 H7 IH1(50) Z63 H4 (75,50)
    [39:40]    IH48(49) Z1 H7 IH1(50) Z62 H5 (75,50)

    Line list containing 40 lines:
    [1:4]      1-20(49)
    [5]        1-20(49) 58-62(50)
    [6]        38-42(50) 57-63(50)
    [7:8]      37-43(50) 57-63(50)
    [9]        11(52) 37-43(50) 58-62(50)
    [10]       10-13(52) 38-42(50)
    [11]       9-16(52)
    [12]       11-18(52)
    [13]       14-21(52)
    [14]       16-23(52) 25-55(49)
    [15]       19-24(52) 25(53) 26-55(49)
    [16]       21-24(52) 25-28(53) 29-41(49) 49-55(49)
    [17]       23-24(52) 25-30(53) 31-40(49) 50-55(49)
    [18]       25(49) 26-33(53) 34-39(49) 51-55(49)
    [19]       25-27(49) 28-35(53) 36-39(49) 51-55(49)
    [20]       25-30(49) 31-37(53) 38-39(49) 51-55(49)
    [21]       25-32(49) 33-39(53) 40(52) 51-55(49)
    [22]       15(49) 27-34(49) 35-39(53) 40-42(52) 51-55(49)
    [23]       28-37(49) 38-40(53) 41-45(52) 50-55(49)
    [24]       29-39(49) 40-41(53) 42-47(52) 49-55(49)
    [25]       2-8(49) 30-42(49) 43-49(53) 50-55(49)
    [26]       2-8(49) 30-44(49) 45-52(53) 53-55(49)
    [27]       2-8(49) 20(52) 31-46(49) 47-54(53) 55(49)
    [28]       2-8(49) 20(52) 31-49(49) 50-55(53) 56-57(52)
    [29]       2-8(49) 20(52) 31-51(49) 52-55(53) 56-59(52)
    [30]       2-8(49) 20(52) 31-54(49) 55(53) 56-61(52)
    [31]       2-8(49) 31-55(49) 57-64(52)
    [32]       2-8(49) 31-55(49) 59-66(52)
    [33]       2-8(49) 31-55(49) 62-69(52)
    [34]       2-8(49) 30-55(49) 64-71(52)
    [35]       2-8(49) 30-55(49) 67-70(52)
    [36]       2-8(49) 69(52)
    [37:38]    2-8(49) 72-75(50)
    [39:40]    2-8(49) 71-75(50)

The  line  list  and range list tables shown consist of two columns, the
first listing the range of mask lines pointing  to  the  line  or  range


                                 -23-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



list  shown  to the right (a sequence of identical mask lines will point
to the same encoded line list).   Each  instruction  which  changes  the
mask  pixel  value  is  followed  by  the  new  current  mask  value  in 
parenthesis.  Zero ranges are omitted in the  range  list  format.   The
"pl_circle"  regions  appear  as ellipses since a printed character does
not have a unit aspect ratio.



3.3.6 PIXEL LIST DESCRIPTOR

    For runtime access to a mask we require, for an N dimensional  mask,
an  N-1  dimensional  array  of  line list pointers, plus the line lists
themselves.  Multiple line list pointers may point to the  same  encoded
line  list.   All  line  pointers  are  valid  at  all times, i.e., NULL
pointers are not permitted, even for empty mask lines.   Initially,  all
line  pointers  will  point  to  the  same  entry, the encoded line list
representation of an empty line,  i.e.,  a  line  of  zeros  (i.e.,  the
single instruction ZN where N=axlen[1]).

        struct pldes {
                int     pl_magic        # magic / version no.
                int     pl_private1     # used by PMIO (ref_im)
                int     pl_private2     # used by PMIO (mapxy flag)
                int     pl_maxline      # max encoded line lentgh
                int     pl_maxval       # mask depth as max pixel value
                int     pl_naxes        # number of axes
                int     pl_axlen[7]     # axis lengths
                int     pl_plane[7]     # current plane for pl_setplane
                int     pl_llbp         # line list bufptr
                int     pl_llop         # next location in llbuf
                int     pl_lllen        # current llbuf length
                int     pl_llfree       # amount of free space in list
                int     pl_llnupdates   # line list has been modified
                int     pl_llinc        # llbuf increment on overflow
                int     pl_nlp          # number of line pointers
                int     pl_lp[]         # array of line pointers
        }

The  main  descriptor,  which is a dynamically allocated data structure,
is a  fixed  size  descriptor,  the  size  of  which  depends  upon  the
dimensionality  and  size  of the mask.  A single additional dynamically
allocated buffer of type  SHORT  is  used  to  store  the  encoded  line
lists.   The  size  of  this  buffer  may vary at runtime as the mask is
edited.  New line lists, or edited line lists which  increase  in  size,
are  inserted  at  the  end  of  the buffer.  As existing line lists are
freed a count of the amount of free space is kept in PL_LLFREE.  If  the
percent  of  free space reaches a predetermined level garbage collection
is possible by copying the list,  otherwise  the  line  list  buffer  is
reallocated  to increase its size.  The line pointers PL_LP are actually
offsets into LLBUF, rather than true pointers.



                                 -24-
PLIO (Feb88)            Pixel List Package Design           PLIO (Feb88)



3.3.7 EXTERNAL STORAGE FORMAT

    A mask is stored externally as a variable length array of 32 bit MII
integers  (the  stored  mask  header)  followed  by  two variable length
arrays of 16 bit MII integers, packed in the following format:

        struct pl_extern {
                int     ple_magic       # magic / version no.
                int     ple_naxes       # mask dimensionality
                int     ple_axlen[7]    # length of each axis
                int     ple_llop        # output pointer into llbuf
                int     ple_lllen       # llbuf length, words
                int     ple_nlp         # number of line pointers (lines)
                int     ple_nlpx        # length of compressed index
                int     ple_exlen       # length of full pl_extern struct
                int     ple_flags       # flag bits
                int     ple_maxline     # saved pl_maxline
                int     ple_maxval      # saved pl_maxval
                short   ple_pkindex[]   # packed line list index array
                short   ple_llbuf[]     # line list buffer
        }

The PL_COMPRESS function is applied before a mask is  encoded  into  the
external  storage format, to eliminate the unused space in the line list
buffer  which  occurs  during  dynamic  updates  to  the  runtime   list 
structure.   The  line list index, containing one integer entry for each
line in the mask in the runtime format,  is  compressed  using  PL_P2LI,
storing  in  the external representation the compressed array encoded as
a line list in PLE_PKINDEX.  This  is  especially  important  for  large
masks,  as  otherwise  the  index  array  could  be  by  far the biggest
contributer to the size of the  mask  when  encoded  into  its  external
format.

No  format  conversions  are required other than decoding the compressed
line list index and possibly byte swapping,  hence  accessing  a  stored
list  is  very  fast.  Further data compression is possible when packing
the list for storage, but it is not clear if this is justified.