Discussion List Archives

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Imgcif-l] Handling sparse images

One of the issues raised at the recent workshop at BNL was to provide
a mechanism for the handling of sparse images in imgCIF, such as
pixel overflow tables and masks.  Here is a rough first draft of
a proposed change to the imgCIF dictionary and to CBFlib to support
sparse images.  Comments, corrections and suggestions would be appreciated.

   -- Herbert


We propose to add an additional compression type

    X-CBF_BACKGROUND_OFFSET_DELTA

(aka BOD compression) which takes an array of pixels and represents
it as a sequence of variable-length numbers.  Each of the numbers
is a signed ones-complement little-endian integer of 7, 14, 21,
28, ... bits in length.  The format of each integer is as a sequence of
octets:

   LO EO1 EO2 ...

The leading octet is mandatory.  The extension octets, EOn, are optional.
As an 8-bit signed integer, LO is always non-negative and represents a
signed 7-bit signed integer (-63 to -0 and 0 to +63) if there are no extension
octets, or, if there are extension octets, represents the least-significant
7 bits of a larger signed integer.  EOn is always negative, representing the
next 7 bits of the intended number with the sign bit of the octet set.

After reconstruction, these numbers are signed-extended and converted 
to two's complement numbers by adding 1 to the negative numbers. 
This leaves
the bit pattern of all 1's representing the one's complement -0 as
a flag.

The resulting 2's complement numbers or flags can represent three 
possible parameters:

   Background -- the value to be assigned to pixels that are not otherwise
specified while scanning to the next pixel to be set.  If the Background
is the flag value processing is terminated. If the Background is not 
the flag value, an Offset follows.
   Offset -- an offset in pixels in the linearized array of pixels from the
index of the last pixel value to have been set to the index of next pixel
value to be set the next pixel value to be set.  If the offset is the
flag value a new Background follows.  If the Offset is not the flag
value, one or more Deltas follow.
   Delta -- a difference between the next pixel value to be set and the
last pixel value to have been set.  If the first Delta is a flag value,
then a series of deltas follows until terminated by another flag value.
The Offset is incremented by 1 for each Delta except for the last one
given.  A new Offset follows the Delta(s).  Initially the last pixel
value is set to Background, and the index into the pixel array is 0

Note that, as with all CBF images, the bit-length and type (integer or real)
of the pixels is known.  For purposes of this compression, all pixels,
whether signed or unsigned, real or integer, are treated as signed,
two's complement integers for purposes of computing and applying deltas.

To give an example, if we had an 8x8 image with a background of 1 and
a 16 pixels in the middle set to 1000, an appropriate sequence of 2's
complement numbers would be:

   1,             set the background, pixel 0 and last pixel value to 1
   18, 999,       set pixels 1-17 to 1, pixel 18 to 1000
   flag, 1000,    set the background to 1000
   4, -999,       set pixels 19,20,21 to 1000, pixel 22 to 1
   flag,1         set the background to 1
   4, 999         set pixels 23,24,25 to 1, pixel 26 to 1000
   flag, 1000,    set the background to 1000
   4, -999,       set pixels 27,28,29 to 1000, pixel 30 to 1
   flag,1         set the background to 1
   4, 999         set pixels 31,32,33 to 1, pixel 34 to 1000
   flag, 1000,    set the background to 1000
   4, -999,       set pixels 35,36,37 to 1000, pixel 38 to 1
   flag,1         set the background to 1
   4, 999         set pixels 39,40,41 to 1, pixel 42 to 1000
   flag, 1000,    set the background to 1000
   4, -999,       set pixels 43,44,45 to 1000, pixel 46 to 1
   flag,1         set the background to 1
   17, 0          set pixels 47-62 to 1, pixel 63 to 1
   flag, flag     end

As octets this would be

   01             1
   12  67  87     18, 999
   7F  68  87     flag, 1000
   04  14  F8     4, -999
   7F  01         flag,1
   04  67  87     4, 999
   7F  68  87     flag, 1000
   04  14  F8     4, -999
   7F  01         flag,1
   04  67  87     4, 999
   7F  68  87     flag, 1000
   04  14  F8     4, -999
   7F  01         flag,1
   04  67  87     4, 999
   7F  68  87     flag, 1000
   04  14  F8     4, -999
   7F  01         flag,1
   11  00         17, 0
   7F  7F

Note that more efficient representations are possible, e.g. by making
one full pass setting the background, then using a negative offset to
return to the central pixels and making use of runs of deltas.

-- 
=====================================================
  Herbert J. Bernstein, Professor of Computer Science
    Dowling College, Kramer Science Center, KSC 121
         Idle Hour Blvd, Oakdale, NY, 11769

                  +1-631-244-3035
                  yaya@dowling.edu
=====================================================
_______________________________________________
imgcif-l mailing list
imgcif-l@iucr.org
http://scripts.iucr.org/mailman/listinfo/imgcif-l

Reply to: [list | sender only]
International Union of Crystallography

Scientific Union Member of the International Science Council (admitted 1947). Member of CODATA, the ISC Committee on Data. Partner with UNESCO, the United Nations Educational, Scientific and Cultural Organization in the International Year of Crystallography 2014.

International Science Council Scientific Freedom Policy

The IUCr observes the basic policy of non-discrimination and affirms the right and freedom of scientists to associate in international scientific activity without regard to such factors as ethnic origin, religion, citizenship, language, political stance, gender, sex or age, in accordance with the Statutes of the International Council for Science.