John Bridges is the author of GRASP (Paul Mace Software), PC Paint (Mouse Systems), Imagetools (HSC Software), and a slew of freeware. He is currently working on new versions of his products, as well as a long-term project with the IBM Multi-media Lab. He can be found haunting the PICS forum on CompuServe and can be reached at [73307,606].
Differential (DFF) image storage takes advantage of the inherent similarity between frames in a sequence by keeping track of only the differences between images rather than the images themselves. DFF is therefore particularly effective for compressing animated sequences. For example, many Saturday morning cartoons have an entirely still or fixed background with a few characters moving in front of it. Rather than storing the background over and over again, the DFF technique is used to store the background in the first frame of data, then concentrate on the changes in those characters that actually move on successive frames.
The savings in disk space is dramatic. Even a simple DFF algorithm exceeds the space savings performance of complicated and slow general-purpose, single-image compression algorithms. In fact, you can easily decode a DFF format in real time to display memory.
Another advantage of DFF-encoded animation is that you can reduce the number of bytes per frame that need to be written to video RAM. This is especially important on machines that have slow video RAM access (the PS/2 Model 70, for example, that has a ratio of about 10:1 between regular RAM and video RAM-access). Often on these machines, the majority of animation computing time is spent waiting for the machine to write data into video RAM.
Although it is possible to store differences between pixels that are not a byte in size, for this article I'm going to stick to byte-oriented differences, because storing the differences between individual pixels that are smaller than a byte can take more computing power -- twiddling all those bits around -- than it's worth for most applications.
Storing DFF Information
Here are two ways to store DFF information -- bitmap and skip/copy.
Bitmap DFF data is a bit table with one bit for each possible byte position. Each time a bit is true, a byte has to be copied from a table of changed bytes which follow. In Figure 1(a), the two "images" are represented by strings of 40 characters. When the vertically adjacent letter pairs are the same, the result (represented below the two images) is a 0 (false, or no difference). When they are different, the corresponding bit is a 1 (true). The result is a bit table of 40 bits, or 5 bytes followed by the 14 bytes, which have changed as in Figure 1(b). As you can see, the result is a total of 19 bytes in length.
Figure 1: Bitmapped storage of DFF information
(a)
Image 1: AAAABBBBBBCCCCHHHHHHHDDDDEEEFFFGGGGGGBBB
Image 2: AAAGGGGAAAACCCCHHHHHHHDDDDEEEFFFGGGGGGBB
0001111111100010000001000100100100000100
(b)
Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 14 changed bytes
------------------------------------------------------------------
00011111 11100010 00000100 01001001 00000100 GGGGAAAACHDEFG
Skip/copy, on the other hand, stores the number of bytes to skip and the number of new bytes to copy. Using the same images as in Figure 1, you can see in Figure 2(a) which bytes are skipped and which are to be copied with the results shown in Figure 2(b).
If a single byte is used to represent whether to skip or to copy (with negative numbers being the number of bytes to skip, and positive numbers the number of bytes to copy), the byte stream looks like Figure 2(c). The result is 29 bytes long.
To save even more space, you can represent runs of the same byte to copy with a count of the number of times to repeat that byte, followed by the byte to repeat. This is called run-length encoding. For this example I'll use the numbers from 1 to 63 for the number of bytes to copy, and 64 to 128 for the number of times (plus 64) to repeat the byte which follows as in Figure 2(d). This reduces the data from 29 to 24 bytes.
Figure 2: Skip/copy storage of DFF information
(a) Image 1: AAAABBBBBBCCCCHHHHHHHDDDDEEEFFFGGGGGGBBB Image 2: AAAGGGGAAAACCCCHHHHHHHDDDDEEEFFFGGGGGGBB Changes: GGGGAAAA C H D E F G (b) Skip 3 copy 8: GGGGAAAA Skip 3 copy 1: C Skip 6 copy 1: H Skip 3 copy 1: D Skip 2 copy 1: E Skip 2 copy 1: F Skip 5 copy 1: G Skip 2 (c) - 3 8 GGGGAAAA -3 1 C -6 1 H -3 1 D -2 1 E -2 1 F -5 1 G -2 (d) -3 64+4 G 64+4 A -3 1 C -6 1 H -3 1 D -2 1 E -2 1 F -5 1 G -2
Two-Dimensional DFF
For actual images, DFF data is two-dimensional. There are several tricks to take advantage of the similarity between the horizontal lines within an image.
Figure 3, for example, shows three images. Because we don't know what is displayed on the screen before displaying the first image, I include the differences between "no image" and the first image to yield three frames of DFF information. It should be pointed out that every pixel will change from the "no image" state to the first image.
Also, because the changes in each image do not affect the entire 16 x 16 area, time and space are saved by storing a starting and ending X,Y offset within the frame where the actual changes take place. In particular, this saves space when using the bitmap storage as each byte within the area affected must be a bit value in the bit table. If I stored a full bitmap for each frame, it would take 32 bytes of bitmap for every frame, compared to less than half that in the example described shortly.
In Figure 3(a), the X,Y offsets are 4 bytes, which is applicable only to images up to 255 x 255; for real-world use, that can be changed to 8 bytes for images up to 65535 x 65535. There are three images, each of which represents a frame in an animated sequence. At the corners of each frame are their corresponding coordinates. The resultant bitmaps are shown in Figure 3(b).
Figure 3: Two-dimensional DFF
(a)
Images:
Image 1 Image 2 Image 3
---------------- ---------------- ----------------
0,0 15,0 0,0 15,0 0,0 15,0
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAZZZZZZZZZAAAA AAAAZZZZZZZZZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZZZZZZZZZAAAA AAAAZZZZZZZZZAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
0,15 15,15 0,15 15,15 0,15 15,15
(b)
Frame 1 Frame 2 Frame 3
---------------- ---------------- ----------------
0,0 15,0 0,0 15,0 0,0 15,0
1111111111111111 0000000000000000 0000000000000000
1111111111111111 0000000000000000 0000000000000000
1111111111111111 0001111111110000 0001000000001000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0000000000000000 0000000000000000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001000000010000 0001100000011000
1111111111111111 0001111111110000 0001000000001000
1111111111111111 0000000000000000 0000000000000000
1111111111111111 0000000000000000 0000000000000000
0,15 15,15 0,15 15,15 0,15 15,15
To reduce the size of each list of changed bytes, the repeating bytes or patterns are reduced to a count and the byte or pattern which is to be repeated.
- A zero count means the following 2 bytes are to be treated as a 16 bit value, which is useful for large repeats or blocks of nonrepeating bytes.
- When the values -32767 to -1 are used, they represent the number of times to repeat the byte that follows.
- When the values 64 to 32767 are used, they represent the number of bytes +64 to copy directly (without repetition), followed by the bytes which are to be copied.
- When the values 1 to 64 are used, they represent the number of bytes in a pattern to be repeated followed by the number of times to repeat the pattern, and following that, the pattern itself.
The data in Figure 4 is a bitmap of the changed bytes, followed by the run-length compressed bytes, which are the actual difference information. As you can see, there is tremendous savings when the differences are located within a small area as in frames 2 and 3.
Figure 4: Bitmap of the changed bytes followed by RLE compressed bytes. (a) Frame 1: Difference information between no image and image 1 (39 bytes); the area from 0,0 to 15,15. (b) Frame 2: Difference information between image 1 and image 2 (20 bytes); the area from 3,2 to 11,13. (c) Frame 3: Difference information between image 2 and image 3 (23 bytes); the area from 3,2 to 12,13.
(a) 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 0 -256 A (b) 11111111 11000000 01100000 00110000 00011000 00001000 00000010 00000011 00000001 10000000 11000000 01100000 00111111 1111 -36 Z (c) 10000000 01110000 00111100 00001111 00000011 11000000 11000000 00001100 00001111 00000011 11000000 11110000 00111100 00001110 00000001 2 20 AZ
The example of the skip/copy algorithm shown in Figure 5(a) illustrates a method which is more effective than the bitmap method just used. In this technique, the comparisons are identical to those of the bitmap method. First, image 1 is compared to no image to produce frame 1. Image 1 is compared with image 2 to produce frame 2, and image 2 is compared with image 3 to produce frame 3. The resultant changed bytes are shown in Figure 5(b). Notice that the actual number of bytes that change in frames 2 and 3 is very small (36 bytes in frame 2, and 40 bytes in frame 3). Figure 6 shows frames 1 through 3, stored as skip values and the run-length compressed changes.
Figure 5: The skip/copy algorithm
(a)
Images:
Image 1 Image 2 Image 3
---------------- ---------------- ----------------
0,0 15,0 0,0 15,0 0,0 15,0
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAZZZZZZZZZAAAA AAAAZZZZZZZZZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZAAAAAAAZAAAA AAAAZAAAAAAAZAAA
AAAAAAAAAAAAAAAA AAAZZZZZZZZZAAAA AAAAZZZZZZZZZAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA
0,15 15,15 0,15 15,15 0,15 15,15
(b)
Frame 1 Frame 2 Frame 3
---------------- ---------------- ----------------
0,0 15,0 0,0 15,0 0,0 15,0
AAAAAAAAAAAAAAAA ................ ................
AAAAAAAAAAAAAAAA ................ ................
AAAAAAAAAAAAAAAA ...ZZZZZZZZZ.... ...A........Z...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ................ ................
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...Z.......Z.... ...AZ......AZ...
AAAAAAAAAAAAAAAA ...ZZZZZZZZZ.... ...A........Z...
AAAAAAAAAAAAAAAA ................ ................
AAAAAAAAAAAAAAAA ................ ................
0,15 15,15 0,15 15,15 0,15 15,15
Figure 6: Frames 1-3 stored as skip values. (a) Frame 1: Difference between no image and image 1 (the area from 0,0 to 15,15), 36 bytes. (b) Frame 2: Difference between image 1 and image 2 (the area from 3,2 to 11,13), 54 bytes. (c) Frame 3: Difference between image 2 and image 3 (the area from 3,2 to 12,13), 78 bytes.
(a) Data in Frame 1 Description of the Data ----------------------------------------------------------- 64+16A Copy run of 16 A's in line 0 64+16A Copy run of 16 A's in line 1 64+16A Copy run of 16 A's in line 2 64+16A Copy run of 16 A's in line 3 64+16A Copy run of 16 A's in line 4 64+16A Copy run of 16 A's in line 5 64+16A Copy run of 16 A's in line 6 64+16A Copy run of 16 A's in line 7 64+16A Copy run of 16 A's in line 8 64+16A Copy run of 16 A's in line 9 64+16A Copy run of 16 A's in line 10 64+16A Copy run of 16 A's in line 11 64+16A Copy run of 16 A's in line 12 64+16A Copy run of 16 A's in line 13 64+16A Copy run of 16 A's in line 14 64+16A Copy run of 16 A's in line 15 (b) Data in Frame 2 Description of the Data ----------------------------------------------------------- 64+9 Z Copy run of 9 Zs in line 2 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 3 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 4 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 5 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 6 -9 Skip 9 bytes in line 7 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 8 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 9 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 10 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 11 1 Z-7 1 Z Copy Z, skip 7 bytes, and copy Z in line 12 64+9 Z Copy run of 9 Zs in line 13 (c) Data in Frame 3 Description of the Data ----------------------------------------------------------- 1 A-8 1 Z Copy A, skip 8 bytes and copy Z in line 2 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 3 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 4 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 5 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 6 -10 Skip 10 bytes in line 7 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 8 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 9 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 10 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 11 2 AZ-6 2 AZ Copy AZ, skip 6 bytes, and copy AZ in line 12 1 A-8 1 Z Copy A, skip 8 bytes and copy Z in line 13
The three frames in Figure 7 are encoded using skip values with the run-length of changed bytes and the "repeat any previous line" option. This option is coded as the relative line number, of previous lines, to be repeated.
Figure 7: Frames encoded using skip values with RL of changed bytes and the "repeat any previous line" option. (a) Frame 1: Difference between no image and image 1 (21 bytes) area from 0,0 to 15,15. (b) Frame 2: Difference between image 1 and image 2 (the area from 3,2 to 11,13), 21 bytes. (c) Frame 3: Difference between image 2 and image 3 (the area from 3,2 to 12,13) 26 bytes.
(a) Data in Frame 1 Description of the Data --------------------------------------------------------- 64+16 A Copy run of 16 A's in line 0 -64 Repeat line 0 in line 1 -64 Repeat line 1 in line 2 -64 Repeat line 2 in line 3 -64 Repeat line 3 in line 4 -64 Repeat line 4 in line 5 -64 Repeat line 5 in line 6 -64 Repeat line 6 in line 7 -64 Repeat line 7 in line 8 -64 Repeat line 8 in line 9 -64 Repeat line 9 in line 10 -64 Repeat line 10 in line 11 -64 Repeat line 11 in line 12 -64 Repeat line 12 in line 13 -64 Repeat line 13 in line 14 -64 Repeat line 14 in line 15 (b) Data in Frame 2 Description of the Data --------------------------------------------------------- 64+9 Z Run of 9 Zs in line 2 1 Z-7 1 Z Copy Z, skip 7 bytes and copy Z in line 3 -64 Repeat line 3 in line 4 -64 Repeat line 4 in line 5 -64 Repeat line 5 in line 6 -9 Skip 9 bytes in line 7 -(64+1) Repeat line 6 in line 8 -64 Repeat line 8 in line 9 -64 Repeat line 9 in line 10 -64 Repeat line 10 in line 11 -64 Repeat line 11 in line 12 -(64+10) Repeat line 2 in line 13 (c) Data in Frame 3 Description of the Data --------------------------------------------------------- 1 A -8 1 Z Copy A, skip 8 bytes and copy Z in line 2 2 AZ -6 2 AZ Copy AZ, skip 6 bytes and copy AZ in line 3 -64 Repeat line 3 in line 4 -64 Repeat line 4 in line 5 -64 Repeat line 5 in line 6 -10 Skip 10 bytes in line 7 -(64+1) Repeat line 6 in line 8 -64 Repeat line 8 in line 9 -64 Repeat line 9 in line 10 -64 Repeat line 10 in line 11 -64 Repeat line 11 in line 12 -(64+10) Repeat line 2 in line 13
For purposes of illustration, some of the numbers are shown as arithmetic expressions, but are actually stored as single values. Thus, -(64+1) is stored as -65, and -(64+10) is stored as -74. For example, in frame 2, line 8, there is the value -(64+1) which repeats line 6. Negative 64 indicates the previous line (line 7), and negative 65, which is represented as -(64+1), indicates that line 6 is the line to be repeated.
A further refinement is to add the "repeat previous line N times" option. Now there are skip values with run-length compressed changed bytes; repeat any previous line option; and repeat previous line N times option. Figure 8 is an example that uses all of the options.
Figure 8: Adding to the "repeat previous line N times" option: (a) Frame 1: Difference between no image and image 1 (the area from 0,0 to 15,15), 7 bytes. (b) Frame 2: Difference between image 1 and image 2 (the area from 3,2 to 11,13), 16 bytes. (c) Frame 3: Difference between image 2 and image 3 (the area from 3,2 to 12,13), 21 bytes.
(a) Data in Frame 1 Description of the Data --------------------------------------------------------- 64+16 A Copy run of 16 A's in line 0 95+15 Repeat line 0, 15 times in lines 1 to 15 (b) Data in Frame 2 Description of the Data --------------------------------------------------------- 64+9 Z Copy run of 9 Zs in line 2 1 Z-7 1 Z Copy Z, skip 7 bytes and copy Z in line 3 95+3 Repeat line 3, 3 times in lines 4 to 6 -9 Skip 9 bytes in line 7 -(64+1) Repeat line 6 in line 8 95+4 Repeat line 3, 4 times in lines 9 to 12 -(64+10) Repeat line 2 in line 13 (c) Data in Frame 3 Description of the Data --------------------------------------------------------- 1 A-8 1 Z Copy A, skip 8 bytes and copy Z in line 2 2 AZ-6 2 AZ Copy AZ, skip 6 bytes and copy AZ in line 3 95+3 Repeat line 3, 3 times in lines 4 to 6 -10 Skip 10 bytes in line 7 -(64+1) Repeat line 6 in line 8 95+4 Repeat line 3, 4 times in lines 9 to 12 -(64+10) Repeat line 2 in line 13
For a quick review of the compression codes that have been used for skip/copy examples, refer to Table 1.
Table 1: Compression codes used for skip/copy examples
Code Description
------------------------------------------------------------------------
1 to 63 Number of bytes to directly copy (bytes to copy follow)
64 to 95 Repeat the following byte N-63 times.
96 to 128 Repeat the previous line N-95 times (so, 98 would repeat
the previous line 3 times).
-127 to -64 Repeat line N-64 lines ago (so, -64 would repeat the
previous line and -65 would repeat the line before that).
-63 to -1 Number of bytes to skip forward (skipping unchanged bytes).
Evaluating Storage Savings
By comparing the various methods of compression presented in this article so far, it is fairly easy to evaluate the savings in storage when compressing images using DFF techniques. Table 2 shows the differences between the three 16 x 16 images used earlier. Note that the number of bytes in each image includes 4 bytes for starting and ending X,Y positions of the area within the image that changes from frame to frame. The best results give a total of 44 bytes; the original uncompressed images were 256 bytes each -- 768 bytes. This is a savings of approximately 94 percent!
Table 2: Evaluating storage savings
1 2 3
--------------------------------------------------------------------
Bitmap of changed bytes with run-length compressed
changed bytes 39 20 23
Skip values with run length of changed bytes 36 54 78
Skip values with run length of changed bytes and repeat
any previous line option 21 21 26
Skip values with run length of changed bytes, repeat any
previous line option and repeat previous line N 7 16 21
times option
However, there are situations in which the above algorithms are not so efficient, primarily when widely spaced image changes occur or when you have drastic image changes.
Widely Spaced Image Changes
When the bytes that change are widely spaced within the image, the least-fit rectangle that defines the area in which changes take place can be very large -- often, close to the size of the original image. This is particularly devastating to the bit-map algorithm because the larger the least-fit rectangle, the larger the bitmap must be.
For instance, take a sequence of images 1024 x 768 bytes in size which have four bouncing balls in each image. The balls are "all over the place," but are fairly small in size (maybe 16 x 16). The sequence is 32 frames long, and then it repeats. Because the balls are often widely spaced (at opposite corners of the image), the least-fit rectangle is, on average, 90 percent of the full image size. This would mean the bitmap for each image would be about 88K, or a total of 2.8 Mbytes for all 32 frames!
While the actual change data, even if every pixel in each ball is in a new place on each frame, would still be 2K per frame, or 64K for all 32 frames. Also, those 88K bitmaps have to be scanned for positive bits each time a frame is displayed. For most computers this is an overwhelming task to accomplish for real-time animation.
One alternative is to search for multiple least-fit rectangles. (A good general-purpose algorithm for this task is beyond the scope of this article.) For this example of the four bouncing balls, you could write a special case algorithm which always started with eight least-fit rectangles (four for the new ball positions and four for the old ball positions), then reduce that number for intersecting paths and less-than-extreme movement of a ball between frames (where the old and new positions of a ball can both be held within a small rectangle).
Although the bit-map algorithm for storing differences is well suited to nearly all random changes that occur over large areas of an image when the number of changes is large, there is a major problem. This approach tends to be below par for small changes that are spread over large areas of an image, which requires a large bitmap and a small set of change bytes. It is my opinion that the best use of the bitmap algorithm is for video images, which tend to have a lot of random-noise-type changes between frames, with change ratios (the percentage of the image's bytes which have changed between frames) as high as 70 or 80 percent.
Drastic Image Changes
When a large percentage of the image changes between frames, the skip/copy algorithm does not give a high compression ratio. Good examples are frames that were captured from video and 3-D rendered computer-generated animation. In particular, video captured from a poor/noisy source can have random changes constantly going on, even on a still frame. Video captured from a good source, such as a hi-res video camera, tends to have random changes which give an image that "live" look. Some of these random changes can be suppressed with a good time-based digital filter -- one that removes small pixel fluctuations over a short period of time without affecting normal motion. But the best digital filter can't do much with live action: Even a simple slow pan of a still scene has a drastic change rate. This is where the skip/copy algorithm is at its worst because it has almost no interline repetition to take advantage of, and it must generate zillions of little skips and small copies of nonrepeating bytes.
3-D rendered computer-generated animation (like those displays you see at computer graphics shows) tends to use smooth shading, so even though you may see giant block letters flying across the screen, they are probably smoothly shaded. This means that each time the image moves, almost every pixel changes its value. DFF will still help in avoiding the storage of a fixed background, but the skip/copy method performs somewhat better than the bitmap algorithm for these types of images.
Error Distribution Dithering
Error Distribution Dithering (EDD) is used to compensate for lack of color or gray scale -- when displaying a gray-scale image in a black-and-white mode, for example, or when displaying a full color RGB image on a 16-color display. The great advantage of EDDs is also the reason they are a bane to DFF storage. The concept of EDDs is to distribute the error (the difference between the original color for a pixel and the closest we could come to displaying it) over the surrounding pixels. This gives us a simulation of true gray scale or color, while still maintaining a great deal of the original image's resolution. The problem occurs when a single pixel changes its value: It can affect the value of numerous surrounding pixels. In fact, a small change in one pixel can shift the pattern of error distribution enough so that hundreds of pixels are changed in the dithered image. This means that EDD rendered images often have a change rate of nearly 100 percent. You can find a good example in those cheap video capture boards which capture in gray scale and render an EDD image in black and white for display.
Special Applications Using DFF Technology
One problem with DFF storage is that frame size can vary greatly. You can have one frame that is 1/20 the original raw data size, and another that is 4/5 the original raw data size. On systems where the images are being read from a slow I/O device, in real-time (such as CD-ROM), the frame size must be limited to some maximum number of bytes. One method for doing this is to reduce the resolution of the image (or part of the image) as the number of changes exceeds some maximum.
You can reduce resolution on the X-axis, then Y-axis, one step at a time until the changes are reduced to the maximum frame byte size. Lost resolution is made up on successive frames since you calculate the new frame change information relative to the lower resolution of the previous frame. This has the effect of blurring fast motion, which will sharpen when the action settles down. This is particularly useful on systems that have RGB-type hardware where reduced resolution pixels don't have to look blocky because you have averaged the new lower resolution pixel with the surrounding pixels to get an out-of-focus or blurred effect.
Other possibilities are "lossy" algorithms for RGB pixel-based systems. The term lossy refers to algorithms that sacrifice (lose) data accuracy in exchange for data compression, hence loss + y. You can sacrifice short-term image accuracy (it would take time for changes to resolve completely) in exchange for amazing space savings. An example would be to take the change in red, green, and blue for each pixel over time, and use an algorithm much like ADPCM (adaptive delta pulse-code modulation, a common method of compressing and storing sound). With a lossy algorithm you could store only 1 or 2 bits of change information for red, green, and blue per pixel, per frame. All this is pretty impractical for existing micros, but as machines get faster, and custom hardware for DFF encoding/ decoding becomes available, we will see everyday uses for this type of technology.
Results vary a great deal when you use additional compression on the DFF data, but something like LZW encoding (or one of its variations), or Huffman encoding could pay off with substantial disk space savings. The problem is decoding data of that type in real time. Sadly, that's not realistic on existing micros: Most decent general-purpose compression algorithms are usable only to save disk space for a DFF sequence that will be decompressed into memory or a file before playback.
The hottest use for real-time DFF encoding and decoding is for video transfer over standard phone lines (video phones). If you are willing to sacrifice image quality for fast motion, you can still have crystal clear images -- if you can sit still long enough.
With existing out-of-the-box technology, you can transfer around 1600 bytes per second over a phone line, provided the transfer is in one direction only. That really is not enough for TV-quality images unless you are willing to wait several seconds to see someone's face. But if you use pixel scaling technology, you can make a very low resolution image look quite smooth, if not detailed.
As you sit still in front of the phone, the image would get sharper with more detail as the DFF algorithm continued to send more and more information. Note, the key phrase here is "sit still," which shows we have a long way to go until video phones are as common as FAX machines.
Copyright © 1991, Dr. Dobb's Journal
