Dynamic Range Run-Length Encoding (DR RLE)

IMAGINE IMG format can use a simple lossless form of compression that can be referred to as Dynamic Range Run-Length Encoding (DR RLE). This combines two different forms of compression to give a quick and effective reduction of dataset size. This compression is most effective on thematic data, but can also be effective on continuous data with low variance or low dynamic range.

Dynamic Range refers to the span from the minimum pixel value to the maximum pixel value found in a dataset. The dynamic range of the data is often several times smaller than the range of the pixel type in which it is stored. This can be computed by taking the difference of the maximum (VMAX) and the minimum (VMIN) value (plus one): RDynamic = VMAX – VMIN + 1. For example, 8 bit data with a minimum value of 1 and a maximum value of 254 would have a dynamic range of 254. 16 bit data with a minimum value of 1023 and a maximum value of 1278 would have a dynamic range of 256. If the dynamic range is less than the natural range of the data type then a smaller data type can used to store the data with a resulting savings in space. In the second case above the Dynamic Range of the data was 256 but the natural range of 16 bit data (two bytes) is 65536. In this case a single byte can be used to store the data by computing a compressed value (VCOMPRESSED) by subtracting the minimum value (VMIN) from the pixel value (VPIXEL). The data can then be saved with one value per byte (instead of one value per two bytes). To recover the data the minimum is added to the compressed value: VPIXEL = VCOMPRESSED +VMIN. This, of course, requires the minimum value (VMIN) to be saved along with the data.

Run-Length Encoding is a compression technique based on the observation that often there are sequential occurrences (runs) of pixel values in an image. In this case, space can often be saved by counting the number of repeats (NRUN) of a value (VRUN) that occur in succession, and then storing the count and only one occurrence of the value. For example, if the pixel value 0 occurred 100 times in a row then the value (VRUN) would be 0 and the count (NRUN) would be 100. If a single byte is then used to store each of the count and the value, then 2 bytes would be used instead of 100. Run-Length Encoded data is stored as a sequence of pairs that consist of the count and the value (NRUN, VRUN).

By first applying Dynamic Range compression and then Run-Length Encoding, a high degree of lossless compression can be obtained for many types of data. By operating on a block of data at a time the Dynamic Range compression can have a greater effect because the data within a block is often more similar in range than the data across the whole image. Note that it is possible to produce a greater amount of data when applying Dynamic Range Run-Length Encoding. Under these circumstances, the data will be stored as the original uncompressed block.

Compressed data for each block is stored as follows:

Name | Type | Description | |

Repeated only once per block at the front of the data stream | Min | EMIF_T_LONG | This is the minimum value observed in the block of data. |

Numsegments | EMIF_T_LONG | This is the number of runs in the block. | |

Dataoffset | EMIF_T_LONG | This is the number of bytes after the start of this data that the segment data starts at. | |

Numbitspervalue | EMIF_T_UCHAR | This is the number of bits used per data value. It will be either 1, 2, 4, 8, 16, or 32 | |

Segment contents repeated "numsegments" times for the block. | Countnumbytes | EMIF_T_UCHAR | This is the number of bytes for the count. It has the value 1, 2, 3 or 4. |

Count[0] | EMIF_T_UCHAR | Present for countnumbytes=1,2,3,4 | |

Count[1] | EMIF_T_UCHAR | Present for countnumbytes=2,3,4 | |

Count[2] | EMIF_T_UCHAR | Present for countnumbytes=3,4 | |

Count[3] | EMIF_T_UCHAR | Present for countnumbytes=4 | |

Data[0] | EMIF_T_UCHAR | Present for numbitspervalue=1,2,4,8,16 or 32 | |

Data[1] | EMIF_T_UCHAR | Present for numbitspervalue=16 or 32 | |

Data[2] | EMIF_T_UCHAR | Present for numbitspervalue=32 | |

Data[3] | EMIF_T_UCHAR | Present for numbitspervalue=32 |