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