PPM2FLI

NAME
SYNOPSIS
DESCRIPTION
QUANTIZE OPTIONS
FLI/FLC OPTIONS
GENERAL OPTIONS
ENVIRONMENT
EXAMPLES
TECHNICAL NOTES
SEE ALSO
REFERENCES
ACKNOWLEDGMENTS
AUTHOR

NAME

ppm2fli - create a FLI animation from a set of static images

SYNOPSIS

ppm2fli [ options ] [ list-file [ animation-file ] ]

DESCRIPTION

The program ppm2fli generates a FLI/FLC-animation from a series of images. The file list-file contains a list of the names of image files, one per line separated by the new-line character. These images are merged together in the supplied order. The generated animation is written to animation-file.
The file formats which can be read directly are PPM, PGM and PBM (ascii and raw: magic 'P1' to 'P6') as well as FBM (mapped 8bpp and rgb 24bpp). Ppm2fli can invoke external filters which convert other file formats to the PPM or FBM standard. For example such filters are included in the PBMPLUS, NETPBM and FBM packages. Together with these packages a large number of graphic formats can be handled.
The generation of the animation is done in two separate steps:
-
Computation of a common color table for all images
-
Quantization of the images and computing the FLI/FLC frames
The first step is done by scanning all images and using a modified version of the Octree algorithm to compute a color table from the shades found in the images. This color table is supposed to be a -- more or less -- best fit to the color shades which were found in the images.
When the input images are already quantized the result depends on the number of colors which they use altogether. If this number is equal or less than the given maximum (default: 256), the scanning step just evaluates these colors and assembles the color table without any modification. When the input images contain more colors, some colors are put together and assigned to an average value, until the total number is sufficiently low.
Alternatively it's possible to generate the color table by scanning only one image, a so called map image. It may be one from the given list or an extra image. This procedure is faster but the resulting color table may be less suitable for the other images.
Third possibility is to do the quantization separately and generate an extra color table for each image. This may result in a change of the color table between the frames of the FLI animation. However, the program tries to keep the color table as static as possible.
The area of the image that the final animation produces when played is denoted as display_area. Default is a display_area of 640x480 pixels. It is allowed that the size of the input images varies. If the width of an input image is greater than the width of the display_area, an equal number of pixels is removed from each side of the input image. If the width of an input image is less than the width of the display_area, this results in the creation of a border around the image (default: center the image in the display_area). The same is done in vertical direction.

QUANTIZE OPTIONS

-I
Perform an individual quantize of each image independently of all other images. In this case no common table is used and it may occur that new colors are loaded between the FLI/FLC frames. Usually a common color table should be preferred. Only when this results in very poor quantization of the images a varying color table is recommended.
-Qc numcolors
Employ numcolors as the maximum number of colors used in the quantized images (range: 9-256; default: 256). A low value may result in a poor quantization.
-Qd bits
Employ bits as the color depth used in the color map of the quantized images (range: 2-8; default: 8). Lower values reduce the number of colors in the quantized images.
-Qn nodelimit
Set the maximum number of nodes that the Octree is allowed to have in the second-deepest level. A larger value may result in a better quantization but slows down the scanning of the images. Recommended values: between one time and four times the numcolors value (range: 16-2048; default: 512). See section "TECHNICAL NOTES" for more details.
-Qr reducelevels
Set the number of levels which are considered when reducing the Octree (range: 0-8; default: 8). See section "TECHNICAL NOTES" for more details.
-m file
The common color table is generated by scanning only the image in the given file. Usually this is much faster than scanning all images, but the color table represents only colors which occur in the given image. If this image is not representative for the others, their quantization may become very poor.
-w file
The generated color table is written to the given file as a 256x1 PPM ascii image. Then the program terminates without assembling the fli animation. Later this color table file can be used with the `-m' option to generate the fli animation. When the `-w' option is given the parameter animation-file can be omitted. If both `-m' and `-w' are given also the parameter list-file isn't necessary.

FLI/FLC OPTIONS

-D
Include additionally update information with respect to the frame before the last. Default: generated FLI chunks hold update information only for the immediately preceding frame.
In both cases, the resulting animations work with standard players. The additional update information is useful for players that use the double buffering technique (see TECHNICAL NOTES section below).
-N
Same as `-D' but instead of the frame before the last the update information with respect to the following frame is included. This allows the play in reverse direction with the XAnim player. Note that `-D' and `-N' exclude each other.
-O
Generate output using the older FLI format associated with magic number 0xAF11. Some older players cannot handle newer FLI animations associated with the magic number 0xAF12 (these are sometimes known as FLC files). Use the old LC_CHUNKS (12) instead of DELTA_CHUNKS (7), and COLOR_CHUNKS (11) instead of COLOR_256_CHUNKS (4), and set default resolution to 320x200 instead of the usual 640x480.
-b color
If a particular input image does not cover the entire display_area, employ the specified color for all pixels in the border area. Default: zero (See also `+/-ox'). To evaluate which number a certain color has the `-w' option can be used. By that the color table is written to a file (ascii) and then the desired color can be looked up in the table.
-g widthxheight
This defines the width and height of the display_area (allowed range: from 10x10 to 1280x1024). If an odd value of width is specified, it is automatically incremented by one. A particular FLI player may only support a limited set of resolutions. In principle, VGA resolution (320x200) should always work. For players supporting the newer style of FLIs (FLCs) associated with the magic number 0xAF12, 640x480 should also work.
+/-ox hor_position
Disable the automatic centering of input images in horizontal direction. Place the input images at a fix position in the display_area. When `+ox' is used the left border of the input images is kept fix independently of the width of the images. The value gives the distance between the left border of the display_area and the left border of the input image. When `-ox' is used the right border of the input images is kept fix. The value gives the distance between the right border of the display_area and the right border of the input image. In both cases negative values can be specified. Then the respective border of the input images is outside of the display_area and a part of the images is cut off. The option can be used to place input images with varying width at a certain position in the display_area, or to animate a certain section of larger input images.
+/-oy vert_position
Identical to `+/-ox', but controls the vertical position. When `+oy' is used the number of pixels from the upper border of the display_area to the upper border of the input images is set. Respectively `-oy' controls the position with respect to the lower border.
-s speed
Use the specified speed to be stored in the header of the FLI file. The FLI standard requires a speed value in the file. Some players use this number as default when no other speed is given. The meaning of the speed argument depends on the FLI format in use. Higher values reduce the speed. For old format FLIs, the value specifies the number of video ticks between two frames (default: 5). For new format FLIs, the delay between two frames is specified in 1/1000 seconds rather than video ticks (default: 72/1000 seconds, resulting in approximately 15 frames per second).

GENERAL OPTIONS

-v
Print internal information to stdout. `-vv' causes even more things to be written.
+/-f filter
Use the specified filter when reading the input images. This is necessary when other than the default formats are used or when the input files are compressed (see the examples below). The reading is done using the popen subroutine. If `-f' is used the specified filter is supposed to read from stdin. The command used in the popen statement has the form `filter < image'. In the case of `+f' the image name if passed as argument to the filter program. In both cases the filter program has to write the converted image to stdout. The option overwrites the filter defined by the environment variable PPM2FLIFILTER.
-t
Test the file magic of the input files before using the read filter. Only files which have no PPM, PGM, PBM or FBM format are read through the given filter. By default all files are read through a given filter. When no filter is specified the `-t' option has no effect.

ENVIRONMENT

A frequently used read filter can be defined using the environment variable PPM2FLIFILTER. The name of the filter can be preceded by a `+' or `-' sign (see the example below). The `-' sign as first character corresponds to the usage of `-f' in the command line and a `+' works like `+f'. By default `-' is assumed which means that the filter reads from stdin.

EXAMPLES

Basic Usage
Assume the existence of a series of PPM images which have the names
     image01.ppm,
     image02.ppm,
     image03.ppm,
     etc.
The goal is to produce a FLI animation from these files in the given order. First the list-file is prepared. We choose the name `pics.list' for this file. The file is generated by:
     % ls -1 image??.ppm > pics.list
Note that this only works if no other files in the directory match the specified pattern and the desired order corresponds to the numbering system in the file names. In the second step a FLI file with the name `anim.fli' is generated using the command:
     % ppm2fli pics.list anim.fli
The generated animation has the resolution 640x480. Assume that the given images are only 320x240. Then they appear in the middle of the 640x480 display area and are surrounded by a border area. To avoid this border we fit the FLI resolution at the pixel size of the input images. This can be done by:
     % ppm2fli -g 320x240 pics.list anim.fli
In the next example we begin with a series of 768x512 images. The goal is to animate these images, cutting off the top 20 lines of each image. Again the name of the list-file is `pics.list' and the name of the generated FLI file is `anim.fli'.
The appropriate command line is:
     % ppm2fli -g 768x492 +oy -20 pics.list anim.fli
Note 1):
492 = 512 - 20.
Note 2):
If in the given example the `+oy' option was omitted, 10 lines at the top and bottom would be cut off.
Read Filters
We assume that all input images are in the GIF format and that we have the PBMPLUS package with the program giftoppm installed. Like in the example described above we create a list file with the names of the GIF files. Then the FLI is generated by the command
     % ppm2fli -fgiftoppm pics.list anim.fli
In this case all images given in `pics.list' have to be in GIF format.
If we use the FBM package instead of PBMPLUS we have to use another utility. Now the command line looks like
     % ppm2fli -ffbcat pics.list anim.fli
The utility fbcat converts the GIF images to FBM format which is read by ppm2fli. Because fbcat understands also other formats, like SUN raster or FBM, the input files can have different formats.
It is also possible to use shell scripts as filters. For instance we want to animate a ray-tracer scene. The images were generated by POV-Ray but we made a big mess. Some are stored in QRT format, some as TGA files and others are already converted to PPM. To save disk space some files are compressed by gzip. We are in luck because we used always the correct extensions in the file names. We have gunzip installed and the utilities qrttoppm and tgatoppm are available. We edit a shell script with the following content:
     #! /bin/ksh

     name=$1
     cmd=cat

     function isit
     {
          base=${name%.$1}
          if test "$name" = "$base.$1"; then cmd=$2; fi;
     }

     isit "gz" "gunzip"
     isit "qrt"     "qrttoppm"
     isit "qrt.gz"  "(gunzip | qrttoppm)"
     isit "tga"     "tgatoppm"
     isit "tga.gz"  "(gunzip | tgatoppm)"

     $cmd < $name
The script is stored as `myfilter' in the current directory (... chmod a+x myfilter). To use this filter we type
     % ppm2fli +fmyfilter pics.list anim.fli
Note that now `+f' is required because our filter doesn't read from stdin. It needs the file name as parameter to choose the corresponding utility. The given script works only for the Bourne/Korn shell.
When the filter requires additional parameters they can be passed in an easy way. For instance works
     % ppm2fli -f "gzip -d" pics.list anim.fli
for a series of "gzipped" input files.
Even more complicated things are possible. For example the ghostscript program can be used as read filter to animate a series of PS images. The necessary option may look like
  -f "gs -g320x480 -q -r36 -sDEVICE=ppm -sOutputFile=- -"
which works for the `tiger.ps' example. Note that to reduce the data flow `ppmraw' should be preferred to the `ppm' device.
When a certain filter is often used, the environment variable PPM2FLIFILTER can be set to define the filter. In a bash environment this may look like
     % export PPM2FLIFILTER=-fbcat
Then always the fbcat utility is used as read filter unless something else is defined in the command line.
Usage of a Map File
Again we assume a series of images, but now the goal is to produce two animations with a different order of the images. For this purpose we edit by hand two list files `order1.lst' and `order2.lst'. To save time and to avoid a repeated scanning of the input images the scanning is done in a separate step. The result of the scanning is the common color table. This table has to be stored in an extra file. We choose the name `ct.ppm' for this file. Then the first step looks like:
     % ppm2fli -w ct.ppm order1.lst
In the next step the first animation is generated:
     % ppm2fli -m ct.ppm order1.lst order1.fli
And finally:
     % ppm2fli -m ct.ppm order2.lst order2.fli
Usually, if no individual quantization is used, all images are read twice. Once for generating the color table and the second time when the quantize & assembling is done. Thus, the options `-m' and `-w' can help to save a lot of time, especially when the input files are compressed or have another file format and each reading through a filter requires more time.
Note that the map file is not read through a given filter. Thus, this file always has to be in one of the formats which can be read directly.
Quantization using an external utility
A modified version of the Octree algorithm is implemented in ppm2fli. By default this algorithm is used when the input files contain more than 256 colors. This maximum of colors can be changed to lower values using the option `-Qc'. Sometimes it may be desirable to use a different quantization algorithm. In the following example we want to animate a ray-tracer scene generated by the POV-Ray program. The image files are in gzipped QRT format and we have the PBM package with the utility qrttoppm installed. Again the list-file with the names of the QRT images has the name `pics.list'. The quantization shall be done with the ppmquant program of the PBM package, because it offers the possibility of Floyd-Steinberg error diffusion. Nevertheless we would like to get a FLI animation where the color table is static. Then we do in the first step
     % ppm2fli pics.list -w ct.ppm -f"(gunzip | qrttoppm)"
By that the color table is evaluated by the Octree algorithm and stored in the file `ct.ppm'. To avoid a exceeding command line we edit a shell script with the content
     #! /bin/csh
     gunzip | qrttoppm | ppmquant -fs -map ct.ppm
and store this file as `myquant' in the current directory (... chmod a+x myquant). When this is done we generate the FLI animation `anim.fli' by the command
     % ppm2fli pics.list anim.fli -m ct.ppm -fmyquant
Note that usually the Floyd-Steinberg error diffusion results in a large number of isolated pixels in the quantized image. This is used to avoid the typical color steps which occur in regions with smooth transitions between different colors. But the compression method used in the FLI format is inefficient when too many isolated pixels occur within an image. Thus, the better image quality is payed by a much larger size of the FLI file.

TECHNICAL NOTES

The Modified Octree Algorithm
The Octree algorithm does the quantization in three phases:
(1)
Scanning of the image
(2)
Reduction of the Octree
(3)
Mapping
First the images are scanned to evaluate what colors are present. For this purpose internally a list of colors is created. To speed up the sorting a tree structure -- the so called Octree -- is used rather than a linear list. This tree structure has a main node which can have up to 8 sub-nodes. Each sub-note itself can have again 8 sub-sub-nodes and so on. So the sub-nodes can be regarded as sub-trees.
A geometric interpretation exists for the sorting of RGB colors by the Octree: A RGB color can be regarded as a point with coordinates (red,green,blue) in a 3-dimensional space. The orthogonal coordinate system of this space has axis in the directions red, green and blue. Total black is defined as the origin of this space (0,0,0). Because of the discrete 8bit representation of each RGB component the point (255,255,255) corresponds to maximum bright white. All possible
256*256*256 > 16 Million
RGB combinations form a regular three-dimensional grid in this space. The grid can be covered by a cube with side length 255. This cube corresponds to the main node of the Octree. The sorting is done by subdividing the cube symmetrically in 8 sub-cubes of equal size. The sub-cubes contain the points
1. (r,g,b) = (  0 - 127,   0 - 127,   0 - 127)
2. (r,g,b) = (  0 - 127,   0 - 127, 128 - 255)
3. (r,g,b) = (  0 - 127, 128 - 255,   0 - 127)
4. (r,g,b) = (  0 - 127, 128 - 255, 128 - 255)
5. (r,g,b) = (128 - 255,   0 - 127,   0 - 127)
6. (r,g,b) = (128 - 255,   0 - 127, 128 - 255)
7. (r,g,b) = (128 - 255, 128 - 255,   0 - 127)
8. (r,g,b) = (128 - 255, 128 - 255, 128 - 255)
These sub-cubes correspond to sub-nodes of the main node in the Octree.
At the beginning all 8 bits of the RGB values are taken into account when sorting the colors. It is checked for a pixel in which sub-cube its color belongs. Then it is checked if a corresponding sub-node for this sub-cube already exists. If not a new node in the Octree is generated which represents this sub-cube. Then the sub-cube itself is divided in eight sub-sub-cubes and so on. The subdivision is done until the color is located in the finest cube which contains only one of the possible discrete RGB points. This results in 8 levels of sub-cubes, which all represent a node in different levels of the Octree. The nodes in the finest level (also called deepest level), which have no sub-nodes, are called leaves.
The sorting procedure is done for all pixels in the input images. Additionally the modified algorithm does for each sub-cube a count of the pixels which where located in this cube. Furthermore a sum of the RGB values is computed for all pixels in each sub cube.
In principle all pixels in a true color picture can have different shades. Thus, the Octree might grow and grow, and it may become impossible to store the information for all nodes in the main memory. Of course this depends on the content of the input images. To avoid a very large Octree a reduction is done, when the number of nodes that the Octree has in the second-deepest level exceeds a certain threshold. The reduction is done by throwing away all leaves in the deepest level. The sorting is stopped in the second-deepest level where the nodes of the Octree are now leaves. But, theoretically 7 levels still allow
128*128*128 > 2 Million
different RGB combinations or possible finest sub-cubes. So it can be necessary to reduce the level of sort accuracy further until the Octree remains small enough. But this may cause later a poor result of the quantization, because all pixels which colors share a common leaf of the Octree will have the same color in the resulting quantized image. Thus, it is desirable to keep the accuracy level a high as possible and a compromise between computational effort and quantize quality has to be obtained.
In the second phase of the quantization the color table is computed. For this purpose the Octree which was generated during the scanning process has to be reduced further until the number of leaves is lower (or equal) than the specified maximum of colors. Compared to the reduction during the scanning process, which is done only "level-wise", the final reduction is performed in a more complicated way. It is taken into account how many pixels belong to each node in the Octree. The node with the minimum pixel count is searched. It's sub-trees are discarded and it becomes a leaf. This is repeated until the number of leaves is low enough. Then for each leaf the average color values are computed: The sums of the red, green and blue values are divided by the number of pixels. These averaged RGB values are replaced by the nearest integers and the resulting numbers are taken as entry in the color table.
After the color table is generated the final stage is done. All pixels in the images are sorted again using the -- now reduced -- Octree until a leaf is reached. Then the pixel is mapped to the respective entry in the color table. For all pixels which were used during the scanning process a leaf in the reduced Octree exists. This leaf represents a cube in the color space that contains the color of the pixel (beside other colors depending on the level of the leaf).
In some circumstances it is useful to be able to map also images which were not scanned previously. If such an "unknown" image is mapped pixels may occur which have colors that are not represented by any leaf in the Octree. These "unknown" colors are located in cubes which were not considered previously. The sorting process is extended to handle also such situations. In all cases the sorting starts regularly and it is evaluated in which sub-cube the color of a pixel belongs. If a node for this sub-cube exists in the Octree the search is continued regularly. If no node exists -- this means no scanned pixel had a color which belonged to the same sub-cube -- an extra procedure is started. For all sub-nodes that exist the distance in the 3-dimensional color space between the color of the pixel and the average color of this sub-node is computed (NOTE: In ppm2fli the maximum norm is used as the distance, not the geometric distance). Then the search is continued with the sub-node that represents the lowest distance. The procedure is repeated until a leaf is reached. Like in the regular case the pixel is mapped to the color of this leaf. If this extra search procedure is necessary for some pixels, ppm2fli counts them and writes in a message how many "non-fitting" pixels were found.
Controlling the quantization
In the following we assume that the maximum number of colors was determined previously and the numcolors parameter is kept fix. Usually this value is 256 anyway. Then the program has two parameters by which the selection of the output color table can be controlled. These are the nodelimit and the reducelevels parameters. The first one sets the maximum number of nodes in the second-finest level. Like described above the level of the Octree is reduced when during the scanning of the input images this value is exceeded. With a deeper level in the Octree, finer nuances between output colors are possible. This is useful when smooth transitions are present in the input images. Typically, steps occur in such transitions due to the quantization. These steps may be reduced when a larger nodelimit is used and the final Octree is one level deeper. The depth of the Octree can be watched using the `-vv' option. After the scanning of each file a lines occurs which look like
Octree - node count (5): 1 8 23 66 228 999 0 0 0
The number in the brackets indicates the deepest level. Then follow the number of nodes in each level from 0 to 8. The zero level contains only the main node of the Octree and the first number is always one. Recommended values of nodelimit are between one time and four times the numcolors value. Higher values increase the computational effort and slow down the scanning process.
The reducelevels parameter controls the final reduction of the Octree. It determines the number of levels in which the search for the node with the minimum pixel count is done. When reducelevels is zero, the reduction is done only in the finest level. Therefore, the resulting Octree contains leaves only in two different levels: the deepest and the second-deepest.
The influence of this parameter on the color table becomes clear in the following example: Assume a 640x480 image which shows a small, bright-red object in front of a green dominated background. The small object consists of only 1000 pixels. The green and blue components of the colors in this object are zero. The red values rage from 150 to 250. In the green background the red and blue values are zero. The green values rage from 1 to 255. For each of this green values much more than 1000 pixels can be found in the image (which has more than 300,000 pixels). Thus, we have a total of
101+255=356
different colors in the image. We assume that the nodelimit parameter is larger than 356. Then the Octree has a leaf for each color after the scanning. Until now no reduction was necessary. But now 100 leaves have to be removed from the Octree. By default, the nodes in all levels are searched for the node with minimum pixel count. This will be always a node which represents a red color, because the 1000 red pixels can't stand the statistical superiority of the green background. What happens is that all red pixels are going to receive the same (averaged) red by the quantization and the green nuances in the background are resolved in an optimal way.
When the reduction is limited to the finest level, the number of leaves that represent red colors can only be reduced by a factor of 8. From 101 leaves 13 will remain and the same number of entries in the color table is occupied by red shades. Thus, the red object doesn't look totally poor like in the first case. Now the green background has to be represented by 12 entries less. The preference of shades with higher pixel count is limited with a zero reducelevels value. By default, the nodes in all levels may be turned to leaves, which results in the strongest preference of dominant shades in the color table. Also the statistic of the reduced Octree can be watched using the `-vv' option. When the scanning is finished a lines occurs which look like
Octree - leaf count (4): 0 4 14 53 184 0 0 0 0
The number in the brackets indicates the deepest leaf level. This is followed by the number of leaves in each level from 0 to 8.
In general, the effect of changes of the above mentioned parameters depends strongly on the input data. To get optimal results, some experiments with different values should be done.
FLI/FLC optimization for special players
One special feature of ppm2fli is activated by the `-D' option. By that the program generates optimized animations for players which use double buffering. A double-buffer player uses two buffers for the display. When playing an animation both buffers have to be updated separately. For this a the player needs the update information with respect to the frame which was located previously in the same buffer. This frame is not the last one, which was processed in exactly the other buffer, but the frame before the last. Ordinary FLI/FLC animations contain in each frame the update information with respect to the previous frame. Thus a double buffer player has to combine somehow the updates of two FLI frames to make the changes in one of the buffers. This becomes much easier when the FLI already contains this information in each frame. Still the animation can be played with a regular player. In this case only some unnecessary updates are done which may slow down the animation.
A second special feature is activated by the `-N' option. Then the frames of the generated FLI animation contain the update information with respect to the last and the following frame. This allows the animation to be played in reverse direction. For instance with the XAnim player the play direction can be altered interactively. This may help when visualizing and analyzing some unsteady phenomena or just can be used as a fancy effect. Together with the utility unflick an existing FLI animation can easily be converted to be suitable for reverse play.

SEE ALSO

fbm(1), unflick(1), and ppm(5)

REFERENCES

The quantization is based on the Octree algorithm introduced by Michael Gervautz and Werner Purgathofer (Technical University Vienna, Austria). It is described in the article `A Simple Method for Color Quantization: Octree Quantization' published in Graphic Gems edited by Andrew Glassner pp. 287 ff.

ACKNOWLEDGMENTS

The special feature, to generated FLI animations which can be played forward and backward, is based on contributions and ideas of Marc Podlipec (podlipec@wellfleet.com). This manual page includes parts form that one of fbm2fli which was assembled by R. P. C. Rodgers (rodgers@nlm.nih.gov).

AUTHOR

Klaus Ehrenfried (klaus.ehrenfried@tu-berlin.de). Release of January 2002.
http://vento.pi.tu-berlin.de/fli.html