Channels ▼
RSS

Differential Image Compression


FEB91: DIFFERENTIAL IMAGE COMPRESSION

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.
For an example of the kind of savings to be had, consider that for frame 1 there is a list of 256 As which can be reduced from 256 bytes to 4 bytes encoded as: 0 -256 A. Remember, in two's complement, -256 requires 2 bytes.

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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video