============================================================================ ChangeFSI theory ============================================================================ This file contains a theoretical explanation of how ChangeFSI works, likely only to be of interest to advanced users. Displaying an image =================== RISC OS ------- RISC OS provides basic facilities for displaying images: The ColourTrans module can convert a colour specified using 8 bits for red, green and blue components to the closest colour available from the palette. It can also look at the palette which a sprite uses, and return a list of the closest colours in the current screen mode. The SpriteExtend module can then use this list to paint sprites. Images can thus be displayed in a screen mode that does not provide all the colours used by the image. SpeiteExtend can also change the size of an image. Since these facilities are widely used by interactive programs, they must be fast; indeed, a normal sprite plot takes only one ARM instruction per pixel. However, the need for speed means that some compromises in image quality have been made: ColourTrans makes no effort to use dithering (the practise of putting patterns of different coloured pixels together to represent other colours); SpriteExtend simply discards additional information if reducing the picture in size; and together they make no attempt to enhance the picture when making it larger. ChangeFSI --------- ChangeFSI takes the opposite approach: it provides far more extensive facilities for image conversion and processing, and produces higher quality images; but is slower, taking 105 ARM instructions per pixel - and that's apart from any instructions used to read the image in, change its size and write the result out. Desirable properties for the output image's colour set ====================================================== ChangeFSI can convert images so that the source and output images use different sets of colours. When choosing the colours used in the output, these properties are desirable: (1) Maximising the volume of the colour cube -------------------------------------------- Colour represented in a red, green and blue computer graphics system can be thought of as a point in a 3D cube whose axes are the red, green and blue values. The eight vertices of the cube correspond to black, red, green, blue, cyan, magenta, yellow, and white. The colour volume spanned by the r, g and b axes in the output should be large enough to contain the source image. If not, then whatever clever approximations, dithering or error diffusion techniques are used, the output image will appear faded in some way compared to the source (eg "the red doesn't seem quite the same"). To achieve this aim:  For an arbitrary set of source images, the colour volume used by the output image should cover as much of the R, G, B colour cube as possible - ideally all of it (i.e. 0 - fullscale for each of the colours).  For an animated set of source images the colour volume used by the output images must be consistent, and span them all, otherwise parts of the animation may noticably differ.  For a single source image the colour volume used by the output image need only span that used by the source. When trying to span the entire colour cube, it is important to use the system hardware to the limit. For example, if one has two bits of control over the Archimedes 4 bit D to A converters, the largest range is covered by values 0, 5, 10 and 15 (rather than 0, 4, 8 and 12). (2) Giving hue consistency at different saturations --------------------------------------------------- The output image should provide a consistent set of colours representing derived colours at different levels of intensity. This may be impossible if its palette has different numbers of bits of red, green and blue. Colours that are only slightly off-white and secondary colours (cyan, magenta and yellow) are particularly difficult. (3) Working with the multi-tasking desktop ------------------------------------------ The output image should not change the system's palette, to avoid interfering with other desktop programs - or should at least get the agreement of all other programs first. Use of colours in ChangeFSI output ================================== Colour matching --------------- Colour matching is done in r, g, b space: the distance between colours is the square root of: delta_r²Χ3 + delta_g²Χ10 + delta_b²Χ1 and so the 'closest colour' is the one for which this is a minimum. The red, green and blue weights of 3, 10 and 1 are hard wired; you cannot alter them. 256 colour output ----------------- When outputting 256 colour sprites, ChangeFSI uses the default desktop palette. It is quite well designed, having properties (1) and (2) above (it even has 16 shades of grey), and obviously has property (3). It is used by many Acorn programs (Draw, Paint) and by external programs (Euclid, ProArtisan, Atelier, ..) to great effect. There are two colour matching algorithms ChangeFSI can use:  "John Bowler's" algorithm, which assumes the default palette and derives values for r, g, b and tint algorithmically.  The "devious" algorithm, which searches the palette for the closest colour. 16 colour output ---------------- For colour images the default 16 colour desktop palette does not satisfy properties (1) and (2) above. ChangeFSI therefore has to make compromises and use one of these two methods:  The "digital RGB" algorithm, which sets 8 of the colours in the palette to the standard 8 "digital colours" (black, red, green, blue, cyan, magenta, yellow and white). This satisfies properties (1) and (2) above, but doesn't satisfy property (3) above. However, the standard palette provides close matches for all 8 digital colours except magenta, so ColourTrans can display these images with fair success. By default colour 0=white and 7=black already, so only 6 colours need be changed. It doesn't matter which ones since ColourTrans will map the colours anyway, but the smallest change is 8=blue, 9=yellow, 10=green, 11=red, 13=cyan, and 14=magenta (leaving 0-7, 12 and 15 unchanged).  The "devious" algorithm, which searches the palette for the closest colour. Note that ChangeFSI needs to be in the 16 colour mode in order to read the palette. For monochrome images, ChangeFSI can:  Use the default desktop palette, with the 8 greys it provides. This satisfies properties (1), (2) and (3) above.  Use a palette with 16 greys. This satisfies properties (1) and (2) above, but not (3). 4 colour output --------------- When outputting a colour image to a 4 colour sprite ChangeFSI is really pushed. For example, each pixel can display only one of (say) black, red, green or blue. However, this only spans half the colour cube. The somewhat extreme compromises available are:  Use a palette with black, cyan, magenta and yellow. The rest has to be left to luck: there is no way it can approximate to pure shades of red, green or blue.  Use the "devious" algorithm, which searches the palette for the closest colour. Note that ChangeFSI needs to be in the 4 colour mode in order to read the palette. When outputting a monochrome image, ChangeFSI uses a palette with 4 greys. 2 colour output --------------- With 2 colour modes ChangeFSI outputs in monochrome using a palette providing black and white. However, you can change the dithering method used to represent shades of grey. Output summary -------------- The table below summarises how all the output modes available to ChangeFSI measure up against the desirable properties above: Number of Bits Colour Consistent Desktop Mode and colours used cube hue palette suffix --------- ---- ------ ---------- ------- -------- 2^24 24 Y Y - S32/p3/p6/Irlam/JPEG 2^21 21 Y Y - p6,7 2^18 18 Y Y - p6,6 2^15 15 Y Y - S16/p15/p6,5 2^12 12 Y Y - p6,4 512 9 Y Y - p6,3 256 grey 8 n Y - AIM/JPEGMONO 256 grey 8 n Y - 28d 256 8 Y Y Y 28 256 8 Y Y Y 28r 16 grey 4 n Y n 27t 16 grey 4 n Y n p2/p5 8 grey 3 n Y Y 27 16 4 ? ? Y 27r 16 3 Y Y can be 27d 4 grey 2 n Y Y 26 4 2 n n n 26c 4 2 n n n 26r 2 (black/white) 1 n Y Y 25 2 (black/white) 1 n Y Y 25c/25d/25t 2 (black/white) 1 n Y Y p1/p4 Dithering ========= Because the colours available for the output image may not match those used by the source image, ChangeFSI uses dithering: this is the process of approximating intensity variations with patterned areas. There are two basic types of dithering technique: Dispersed dot dither -------------------- The intensity is given by the average number of dots in the area. This technique is suited to output devices where all dots are the same size, and do not overlap or leave gaps. An LCD produces "ideal square" pixels, and so is perfect; a CRT produces a gaussian spot (a circle or ellipse which decays in intensity towards the edges), which is a good approximation. The grey level patterns used by the desktop in a 1 bit per pixel mode are a good example of dispersed dot dithering. Clustered dot dither -------------------- The intensity is given by the size of the dots in the area. This technique is suited to output devices where the dots are different sizes, overlap, or leave gaps. Clustered dot dither reduces the effects of mis-sized pixels by ensuring they are adjacent (and thus the error is confined to the periphery of the shape), but this does have a cost in poorer resolution. Printers produce large dots that overlap each other; the diameter of the dot is at least as large as the diagonal of the underlying square pixel. Each inked pixel 'caves in' the side of adjacent uninked pixels, so inked pixels are effectively larger than uninked ones. Hence dispersed dot dithering is unsuitable for printers; using it for a 50% tint would print to half the dots, but this would cover more than half the paper's area in ink. The patterns used to print colour magazines and newspaper photographs are a good example of clustered dot dithering. Colour and greyscale dithering in ChangeFSI ------------------------------------------- Colour or greyscale output is almost always for monitors or LCDs; ChangeFSI always uses a dispersed dot dither for such images. Monochrome dithering in ChangeFSI --------------------------------- Monochrome output could be for the screen or for a printer, so ChangeFSI gives you a choice between dispersed and clustered dot dithering. To select clustered dot dithering, you add a suffix ("c", "t" or "d") to the mode number for output:  For "c" the algorithm (due to Robert L Gard, 1976) approximates tones in the range 0-16 (i.e. 17 levels) by using 0-16 "on" pixels in a 4 by 4 cell.  For "t" the algorithm (similar to Gard's) approximates tones in the range 0-9 (i.e. 10 levels) by using 0-9 "on" pixels in a 3 by 3 cell.  For "d" the algorithm (similar to Gard's) approximates tones in the range 0-4 (i.e. 5 levels) by using 0-4 "on" pixels in a 2 by 2 cell. The "on" pixels are carefully chosen to provide a symmetry of white/black and black/white patterns, and a diagonally oriented dot grid. The diagonal angle reduces the eye's ability to see the rectangular patterns produced. The various sizes of the halftone cell allow some trade off between representing the tonal values correctly and loss of resolution. Start with "c"; then progress to "t", and finally to "d" if the resolution is not acceptable. See also the section below on black correction. Error diffusion =============== Any approximation to a colour will produce an error. ChangeFSI tracks these errors and ensures that over wide areas there is no overall error using a technique called "error diffusion", first devised by R W Floyd and L Steinberg in 1975. In this technique the approximation is made, and the error is then distributed to nearby pixels in the following ratios: current pixel 7/16 of error 3/16 of error 5/16 of error 1/16 of error Additionally, ChangeFSI scans through the picture in a serpentine fashion, doing a row of pixels left to right followed by the next row right to left. This reduces the probability of regular patterns to which the eye is sensitive. You can turn dithering off if you wish. Scaling images ============== The conversion from one colour range to another is made at the same time as a change in size of the image. Size is changed by ratios of areas between the input and output: the total weight of r, g, and b in the source area is calculated and this result is then approximated to the output using error diffusion to preserve information. For example, consider halving in size an image with adjacent pixels of intensities 1 and 2; the output pixel needs to be value 1.5, so the 0.5 error is sent to adjacent pixels to keep the overall colour the same. The size change is expressed as a ratio of output to input (e.g. 40:20) which ChangeFSI reduces to the smallest possible terms (2:1 in this case), so you can give values like 256:512. Size change is either both x and y (if one ratio is given), or separate x and y (if two ratios are given). Note that the size of a RISC OS pixel is known, so changing from (say) mode 21 to (say) mode 13 does not need any additional specified scaling. The full size output for mode 21 is the reference, so scale to 640 by 512. A common scaling is to fill the output sprite with the input and an "=" parameter to x and/or y ratios will do this without ever having to know the size of the input. Simply omitting the fractional part causes ChangeFSI to put in the source size, thus giving output which is the specified number of pixels in size. Disabling resizing ------------------ ChangeFSI can read any pixel size information from the source image, or guess it (e.g. if there are less than 320 by 256 pixels in a source image, ChangeFSI assumes there are 45 pixels per inch, as in MODE 13), or derive it from other information. It will then scale the output image appropriately. You can disable this; this may be necessary for formats like TIFF or IFF where the pixel size is specified, but may be wrong. Using -info will display the pixel ratios which ChangeFSI is using - a combination of the size guess, the output pixel size and any deliberate scaling. Processing options ================== In addition to strictly converting the source image, ChangeFSI can also process it. The notes below only give additional information not covered in the other text files in this directory, and so do not cover all the options. Expand dynamic range -------------------- You can expand the dynamic range of the source image so the output image fills the available colour volume. Red, green and blue are each processed by the same amount, so colours are preserved. This is not a good option for animated sequences unless all source images possess the same range. Histogram equalisation ---------------------- Histogram equalisation is a more extreme form of expanding the dynamic range. The output image is spread as evenly as possible over the available colour volume. Red, green and blue are processed separately, so colours are not preserved. Technically, the histogram of level versus number of points at that level is made as flat as possible, giving full use of the number of colours available. This is very harsh: even on monochrome inputs it can produce an inferior picture, whilst on colour pictures it can distort the colour of each point, since red, green, and blue are computed separately. However, it can often recover a picture that is otherwise completely useless, or can expose information locked in a small part of the input scale. Again this is not a good option for animated sequences. Black correction ---------------- The value used for black correction tells ChangeFSI how much larger than an ideal square pixel are the dots produced by a printer. The default value is 32, which represents the minimum circle enclosing the square pixel; such a dot covers 50% more area than the square pixel. Values above 64 give rather poor results on some pictures but may be worth experimenting with. The maximum value of 128 corresponds to an inked dot covering four times the area of the ideal black square pixel, which will generally make ChangeFSI produce an entirely white output. To print black-corrected images, you need a method which exactly copies the pixels ChangeFSI has made to those of the output device. You can use !Paint for this; for example, for a 300dpi printer, scale X and Y by 90:300. The images may not photocopy very well, since a photocopier makes the dots blacker again. Some printers produce dots of pseudo-randomly varying sizes, and black correction may not help with these (the picture looks "noisy") - in which case use one of the clustered output methods. Black correction makes pictures on the screen look very pale, since, if anything, black pixels on screen are smaller than the ideal square. Gamma correction ---------------- A useful option for output intended for the screen only is Gamma correction. CRT displays do not have a simple linear relationship between brightness of the spot and input voltage: instead of brightness = constant Χ voltage, the response is brightness = constant Χ voltage^(1/gamma). In the TV industry, gamma has been standardised as 2.2, but there is wide variation in the computer industry: the monitor's response will vary depending on what make it is, and how it is adjusted. Low values of gamma (0 to 1) make colours darker, and high values (above 1) make colours lighter; the effects are particularly noticeable on dim colours. Gamma correction is most relevant when it's known that the input has a linear intensity (e.g. input from a scanner, or from another computer with more bits per colour component than the Archimedes). Pre-sharpening -------------- Pre-sharpening enhances the edges of objects in the picture; this is very useful since the dithering process inevitably smears information over the display. Pre-sharpening the image can result in a more acceptable output. Default values of sharpening can be overridden for special effects: for example, a value of 8 does edge detection. Lower amounts of sharpening are obtained with larger values. In general the more input and output pixels and the greater the output range in a pixel in the images, the less sharpening is required. Sharpening a picture which is already dithered can give a very bad result. The sharpening is achieved with the following matrix: -1 -1 -1 -1 sharpen -1 -1 -1 -1 ChangeFSI computes the sum of nine pixels with the above weights for each input pixel and renormalises the result (divides by sharpen-8). Order of processing =================== The order in which ChangeFSI applies processing depends on whether or not there are more output pixels than input. Pictures with more output pixels than input ------------------------------------------- Processing is applied in the following order for pictures with more output pixels than input: 1) range or histogram equalisation 2) sharpen 3) scale 4) error diffusion. This order is chosen because:  Since the input pixels (rather than the output pixels) are sharpened, there is no false edge introduced when pixels are replicated. Pictures with fewer output pixels than input -------------------------------------------- Processing is applied in the following order for pictures with fewer output pixels than input: 1) scale 2) range or histogram equalisation 3) sharpen 4) error diffusion. This order is chosen because:  Ranging can enhance down-sized images. Say a black/white dithered image is reduced in size, so that the output from the scaling process is an approximation to the original grey levels; then ranging can expand this if possible.  Sharpening can be used to offset the blurring effects of scaling.  Since the output pixels (rather than the input pixels) are sharpened, the effect is consistent over differently scaled images. Changing the order of processing -------------------------------- In general it is a good idea to start from the unprocessed input each time and do everything in one pass, rather than using the program several times over. It is not a good idea to sharpen a dithered image, unless it has been shrunk. However, there may be times when ChangeFSI's choice of order is wrong, particularly when changing the aspect ratio, where it is possible to trigger some undesirable sharpening artifacts. In such cases you should use the program twice with sharpening (say) disabled and enabled in the order required. Speeding up ChangeFSI ===================== For those worried about speed, the program will go faster if you:  Ignore the pixel aspect and don't specify a scale. (Ignoring the source pixel size and scaling by 1:1 or 1:2 ratios is almost as quick.)  Disable dithering where possible (e.g. when reading monochrome source).  Avoid expanding the dynamic range, histogram equalisation, pre-sharpening and smoothing.  Use monochrome modes (e.g. 25, 26, 27 and 27t). Adding new formats ================== Work will be done on other formats when and if both image and documentation arrive at Acorn. Adding a new format is a matter of:  Putting in automatic recognition of the format at the start of the program.  Reading the size of the image and the colour palette mapping in the next section of the program.  Writing a "read pixel row" element inside PROCiprow.  Providing an entry in PROCrewind. If you write a new format interface, please send it to Acorn so that it will be included in later versions. ChangeFSI has already got code for dealing with images with 1, 2, 4 and 8 bits per pixel packed into bytes and for images with up to 8 bit planes. There is support code for LZW decompression and LZW decoding. The VIDC 256 colour mode ======================== The VIDC controller ------------------- VIDC1 uses a 4 bit DAC for each of red, green, and blue. It has a palette with 16 entries. In a 256 colour mode, 4 bits of the colour number directly affect the DACs, controlling the top 2 bits of green, and the top bit of red and blue. The remaining 4 bits of the colour number are used to look up a palette entry which affects the remaining DAC bits. This means that:  Since there are three 4 bit DACs, there are 4096 (i.e. 2^12) possible colours.  Since the colour number is 8 bits, there are only 256 colours available simultaneously. Which of the 4096 colours they are depends in part on how the palette is programmed, but also:  Since 4 bits of the colour number are directly connected to the DACs, this restricts the choice of which 256 colours are available from the 4096 possible ones. Only 256 different selections are possible. Therefore there are 256 simultaneous colours available in a selection out of 4096 colours, where there are only 256 "legal" selections. The new VIDC20 allows an arbitrary selection of colours, but the default situation is identical. The default RISC OS palette --------------------------- The default RISC OS 256 colour palette is set up so the colour number contains the 2 most significant bits of red, of green, and of blue; the reamining 2 bits control the 2 least significant bits in parallel ("adds white" to a colour). Thus peak red, green and blue is obtained, without side effects if varied simultaneously, but with a side effect if a peak of one colour alone is required. This palette is optimal, since it spans the colour cube. Using other VIDC palettes ------------------------- One can also program the palette to use different numbers of bits per pixel: for example 4 bits of green, 3 bits of red and 1 bit of blue. The constraints are: 2 <= green bits per pixel <= 4 1 <= red bits per pixel <= 4 1 <= blue bits per pixel <= 4 (and total bits per pixel = 8) Modes like these are often useful for real time solid modelling, where the expense of dithering with error diffusion cannot be afforded. However, these selections are non-optimal, since the colour cube is not completely spanned. Acknowledgements ================ Thanks are due to Steve Green and the BBC and Irlam Instruments for the intermediate systems that led to John Bowler's and the Devious algorithms: until Aug 91 ChangeFSI used their work for its "Precise Matching" algorithm. It no longer uses any of their code, but owes a debt for overall approach. A small thank you to Spencer Thomas for putting me on the track which led to the Devious colour matching system's algorithm. References ========== Further information on dithering can be found in "Digital Halftoning" by Robert Ulichney published by the MIT Press, ISBN 0-262-21009-6. Histogram equalisation is in "Algorithms for Graphics and Image Processing" by Theo Pavlidis published by Computer Science Press, ISBN 0-914894-65-X.