[Imgcif-l] Handling sparse images
Herbert J. Bernstein
yaya at bernstein-plus-sons.com
Tue May 27 15:05:42 BST 2008
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 at dowling.edu
=====================================================
More information about the imgcif-l
mailing list