he unpack code for ICO/CUR file handling could extend 32-bit unsigned values to 64...
[imager.git] / 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