design/represent.txt

   1 =head1 NAME
   2
   3   represent.txt - discuss image representation within Imager
   4
   5 =head1 SYNOPSIS
   6
   7   Virtual Images
   8   Image Subsetting
   9   Varying Bits/Sample
  10   Paletted Images
  11   Performance
  12   Robustness
  13   XS Changes
  14
  15 =head1 DESCRIPTION
  16
  17 I'm going to try to explain what we can get from having a flexible
  18 representation of images within Imager.
  19
  20 The main idea is to have all, or almost all of Imager access the
  21 contents of an image through function pointers embedded in the i_img
  22 structure.  This means that the underlying image data can be formatted
  23 to suit special purposes, including paletted images, images kept of
  24 disk (think of 64k x 64k RGB images), and virtual images (where
  25 there's no actual image data.)
  26
  27 =head1 IMAGE TYPES
  28
  29 =head2 Paletted Images
  30
  31 This is the form we've discussed the most.  The main advantage here is
  32 when the user is performing simple manipulations on the image data.
  33 One example that came up recently was when mjd was trying to combine
  34 several images into a single animated GIF file.  If we were
  35 representing the image internally as paletted, and the GIF reader and
  36 writer knew how to do that we could have loaded the images into
  37 paletted images and then written them with no quantization required.
  38
  39 Now we could get complicated and have writes with colours that don't
  40 exist in the image cause an extra entry be added to the palette, but
  41 this leads to complications as to when to convert the image to RGB.
  42 Some paletted formats support large palettes, so if we allowed a few
  43 hundred new colours to be drawn into the image and the tried to save
  44 to a format with only small palettes, not only has the user paid the
  45 performance cost in writing to the image (since paletted writes
  46 include a palette lookup), but also the hit in having to re-quantize
  47 the image anyway.
  48
  49 So my idea was to have the paletted write functions be something like:
  50
  51   if (found entry in palette) {
  52     save to the pixel
  53   } else {
  54     convert image to rgb
  55     call rgb save function
  56   }
  57
  58 An initial implementation might only support 256 colour palettes, we
  59 might expand that later to support larger palettes.
  60
  61 We could expose the quant.c functions to allow the user to create
  62 palettes (and possibly tune them), and to convert from RGB images to
  63 paletted images.
  64
  65 For improved memory usage for large images we could also implement 4
  66 and 1 bit/pixel images.  If we want good support for faxing this could
  67 be useful.
  68
  69 =head2 Virtual Images
  70
  71 Another possible type of image is a B<virtual image> where the i_img
  72 that the user has, has no image data directly associated with it.  The
  73 results of retreiving pixels would simply be the result of some
  74 function.  Such virtualness could even be in terms of "virtual
  75 memory", so a 32-bit processor machine could work with 65536x65536x24
  76 bit images which doesn't even fit into the address-space of the 32-bit
  77 machine.
  78
  79 One possible implementation of function based images would be through
  80 the use of the transform2() engine.  This way the user could specify
  81 the function to be used to generate the virtual image.  This is most
  82 useful for very large images, otherwise simply generating a new image
  83 using the transform2() function would be faster.
  84
  85 =head3 Image Subsetting
  86
  87 This would be mainly for when writing to an image, the user could
  88 supply another image where which pixels were non-black allowed writes
  89 to the corresponding pixels in another image.  Since access is
  90 controlled via another image, we aren't limited to rectangular
  91 subsets.
  92
  93 One simple example might be to create a mask image that has some text
  94 drawn in a large font.  When a gradient or other effect is used it
  95 will fill the letters in the target image.  A more subtle effect could
  96 be lightening, darkening or blurring through the image.
  97
  98 One implementation consideration is that if calculating the pixel
  99 value is expensive the caller may want a method to check if given
 100 pixels are writable, to avoid that extra expense.
 101
 102 =head2 Varying Bits/Sample
 103
 104 The typical Imager image could stay at 8 bits/sample, but some
 105 applications may need to work with images with a higher or lower
 106 colour resolution.  It may also be desirable to work with images where
 107 the sample values are floating point, eg. some FITS images.
 108
 109 The problem with supporting floating point or a larger bit count is
 110 that we need an interface to get and put pixels/rows at the largest
 111 resolution for the high colour resolution.  Since working at this
 112 colour resolution for lower colour resolution images would be
 113 inefficient, we also want another interface at some lower bit-count.
 114 To reduce maintenance costs we want to limit the number of interfaces.
 115
 116 =head1 INTERFACE CONSIDERATIONS
 117
 118 Common interfaces are those interfaces which available for every image
 119 type.  These should include some common bits/sample, and some
 120 all-encompassing bits/sample, eg. 8 bits/sample for the common, and
 121 floating point for the all-encompassing.
 122
 123 The idea is to make it possible for a given filtering function to have
 124 only one implementation at the all-encompassing bits/sample, while
 125 some other function has implementations at multiple bits/sample for
 126 improved speed.
 127
 128 To reduce maintenance we want to reduce the number of common
 129 interfaces, both so that we don't have to write too much code for each
 130 image representation and so that we don't have someone trying to write
 131 five versions of the same code in an attempt to push efficiency to the
 132 limits.
 133
 134 Since we want some function pointers to only be available for some
 135 images (like 'getpixindex' against paletted images), callers need to
 136 be able to detect the type of image that they are working with.
 137
 138 =head2 Performance
 139
 140 Why is performance last?  Well, it needs to be considered in terms of
 141 the other topics above.
 142
 143 Perhaps some method to check the writability at given pixels could be
 144 used to avoid expensive pixel calculations.
 145
 146 We need to strike a balance between speed and maintainability.
 147
 148 While most x86 processors have floating point performance almost as
 149 fast or faster than integer performance, some architectures don't,
 150 hence we need to support use of integer algorithms where appropriate.
 151
 152 =head2 Robustness
 153
 154 By preferring access via the functions we can reduce the possibility
 155 of incorrect access to the image data.
 156
 157 If an image interface function pointer isn't implemented, it should be
 158 set to NULL rather than being left uninitialized.  This is so that use
 159 of the ununsed pointer results in an immediate crash rather than
 160 possibly calling the wrong function and crashing at some later point.
 161
 162 In a debug build of Imager the image interface functions should check
 163 that the correct type of image pointer is being passed in.  This means
 164 that a caller cannot accidentally pass the wrong type of image pointer
 165 to an image access function.
 166
 167 =head1 PROPOSED INTERFACE
 168
 169 The basic interface would include:
 170
 171   typedef struct {
 172     struct { unsigned char r,g,b,a; } rgb;
 173     unsigned char channels[MAX_CHANNELS];
 174     /* and others as we currently have */
 175   } i_color;
 176
 177   typedef struct {
 178     struct { double char r, g, b, a; } rgb;
 179     double channels[MAX_CHANNELS];
 180     /* and others as we currently have */
 181   } i_fcolor;
 182
 183   typedef struct i_img_tag i_img;
 184   typedef int (*i_f_ppix_t)(i_img *im, int x, int y, i_color *pix);
 185   typedef int (*i_f_ppixf_t)(i_img *im, int x, int y, i_fcolor *pix);
 186   typedef int (*i_f_plin_t)(i_img *im, int x, int r, int y, i_color *vals);
 187   typedef int (*i_f_plinf_t)(i_img *im, int x, int r, int y, i_fcolor *vals);
 188   typedef int (*i_f_gpix_t)(i_img *im, int x, int y, i_color *pix);
 189   typedef int (*i_f_gpixf_t)(i_img *im, int x, int y, i_fcolor *pix);
 190   typedef int (*i_f_glin_t)(i_img *im, int x, int r, int y, i_color *vals);
 191   typedef int (*i_f_glinf_t)(i_img *im, int x, int r, int y, i_fcolor *vals);
 192
 193   typedef enum {
 194     i_literal_type, /* keeps RGB values per pixel */
 195     i_palette_type, /* keeps a palette index per pixel */
 196   } i_img_types;
 197
 198   /* interface functions */
 199   typedef int (*i_f_gpal_t)(i_img *im, int x, int r, int y, i_palidx *vals);
 200   typedef int (*i_f_ppal_t)(i_img *im, int x, int r, int y, i_palidx *vals);
 201   typedef int (*i_f_addcolor_t)(i_img *im, i_color *);
 202   typedef int (*i_f_getcolor_t)(i_img *im, int i, i_color *);
 203   typedef int (*i_f_colorcount_t)(i_img *im);
 204   typedef int (*i_f_findcolor_t)(i_img *im);
 205
 206   typedef enum {
 207     /* bits per sample, not per pixel */
 208     /* a paletted image might have one bit perl sample */
 209     i_8_bits = 8,
 210     i_16_bits = 16,
 211     i_double_bits = 64
 212   } i_img_bits;
 213
 214   typedef struct {
 215     char *msg;
 216     int code;
 217   } i_errmsg;
 218
 219   typedef struct {
 220     char *name; /* name of a given tag, might be NULL */
 221     int code; /* number of a given tag, -1 if it has no meaning */
 222     char *data; /* value of a given tag if it's not an int, may be NULL */
 223     int idata; /* value of a given tag if data is NULL */
 224   } i_img_tag;
 225
 226   typedef struct {
 227     int count; /* how many tags have been set */
 228     int alloc; /* how many tags have been allocated for */
 229     i_img_tag *tags;
 230   } i_img_tags;
 231
 232   typedef struct {
 233     int channels;
 234     int xsize, ysize, bytes;
 235     int ch_mask;
 236     i_img_bits bits;
 237     i_img_type type;
 238     int virtual; /* image might not keep any data, must use functions */
 239     void *idata; /* renamed to force inspection of existing code */
 240                  /* can be NULL if virtual is non-zero */
 241     i_img_tags tags;
 242
 243     i_errmsg error_stack[ERRSTK]; /* Store errors with image */
 244
 245     /* interface functions */
 246     i_f_ppix_t i_f_ppix;
 247     i_f_ppixf_t i_f_ppixf;
 248     i_f_plin_t i_f_plin;
 249     i_f_plinf_t i_f_plinf;
 250     i_f_gpix_t i_f_gpix;
 251     i_f_gpixf_t i_f_gpixf;
 252     i_f_glin_t i_f_glin;
 253     i_f_glinf_t i_f_glinf;
 254
 255     /* only valid for type == i_palette_type */
 256     i_f_gpal_t i_f_gpal;
 257     i_f_ppal_t i_f_ppal;
 258     i_f_addcolor_t i_f_addcolor;
 259     i_f_getcolor_t i_f_getcolor;
 260     i_f_colorcount_t i_f_colorcount;
 261     i_f_findcolor_t i_f_findcolor;
 262   } i_img;
 263
 264 I'm using 8-bits for the base interface to remain compatible with
 265 existing code, and because it's a common sample size.
 266
 267 I'm using double for the all-encompassing size since it's the biggest
 268 convenient type that supports floating point based-pixels.
 269
 270 We might want to add functions to set/retrieve the whole palette at
 271 once, though setting the whole palette at once would make existing
 272 image data fairly useless.
 273
 274 =head1 XS CHANGES
 275
 276 I had been considering moving the i_img object from being an
 277 Imager::ImgRef object to being an Imager object.  But I don't see much
 278 point to it, so I'll leave it the way it is now.
 279
 280 =head1 AUTHOR
 281
 282 Tony Cook <tony@develop-help.com>
 283
 284 =head1 HISTORY
 285
 286 16May2001 - initially completed version, could use some polishing
 287 16May2001 - Added i_error stack to the image structure.
 288 24May2001 - Added XS Changes section (TC)
 289
 290 =cut