Methods and Systems to Encode and Decode Sequences of Images

• US 20110228847A1
• Filed: 08/13/2009
• Published: 09/22/2011
• Est. Priority Date: 08/13/2009
• Status: Active Grant

• Current Assignee: Johns Hopkins University
• Original Assignee: Johns Hopkins University
• Inventors: Fischer, Kenneth M., Orlin, David J.
• Granted Patent: US 8,817,875 B2
• Time in Patent Office: Days
• US Class Current: 375/240.12
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

Methods and systems to compress and decompress sequences of images, such as video frames, including compression techniques to estimate pixel values, to determine differences between the estimated pixel values and actual pixel values, to arithmetically encode a corresponding sequence of difference values or symbols as a code value, and to output the code value and associated reference information in a data stream. Decompression techniques include techniques to read the code value and associated reference information from the data stream, to arithmetically decode the symbols from the code value, and to reconstruct the sequence of video frames from the decoded symbols and the associated reference information. Also disclosed are techniques to reduce or preclude overflow of registers or buffers used to hold code range values, and to order tables of code range values to improve efficiency of table look-up operations.

Claims

1. A system, comprising:

a module to receive pixel values associated with a sequence of video frames;

a prediction module to estimate pixel values of at least a portion of the video frames in accordance with one or more models, and to generate a sequence of symbols corresponding to differences between the estimated pixel values and corresponding received pixel values;

a module to arithmetically encode a sequence of symbols as a floating point integer code value, including to associate the symbols with portions of a code range in proportion to occurrences of the symbols within the sequence of symbols, and to iteratively refine the code range in accordance with the proportions associated with the symbols;

an underflow module to reduce a number of digits in one or more of a lower limit and an upper limit of the code range when the most significant digits of the lower limit and the upper limit differ by one and a number of digits of at least one of the lower limit and the upper limit exceed a threshold; and

a module to format and output the code value, symbol counts associated with the code value, and un-encoded reference pixel values in a data stream.

2. The system of claim 1, wherein the underflow module includes:

a module to remove a second most significant digit of the lower limit and the upper limit, to shift remaining digits of the lower and upper limits towards the corresponding second most significant digit, and to increment a count k, when the most significant digit of the lower limit and the upper limit differ by one and the number of digits of at least one of the lower and upper limits exceeds the threshold;

a module to detect when a most significant digit of the lower limit and an upper limit are equal to one another and to output the most significant digit as a next significant digit of the code value; and

a module to output k zeros as the next k significant bits of the code value when the most significant bit of the lower limit is incremented to equal the most significant digit of the upper limit, and to output k nines as the next k significant bits of the code value when the most significant bit of the upper limit is decremented to equal the most significant digit of the lower limit.

3. The system of claim 1, wherein the prediction module is configured to represent pixel values with multiple-bytes including a most significant byte and a least significant byte, and wherein the prediction module includes:

a most significant byte model to estimate most significant byte pixel values from first byte reference pixel values; and

a least significant byte model to estimate least significant byte pixel values from least significant byte reference pixel values.

4. The system of claim 3, wherein:

the sequence of video frames corresponds to a sequence of infrared images;

adjacent ones of the images are substantially similar to one another;

the prediction module is configured to represent the symbols with multiple-bytes, including a most significant byte and a least significant byte; and

differences between pixel values of the sequence of infrared images and corresponding pixel values of a reference image are relatively small, the symbols are predominantly relatively small positive and negative values, and the most significant bytes of the symbols are predominantly one of all zeros and all ones.

5. The system of claim 1, wherein the prediction module includes:

a module to estimate pixel values of a video frame as pixel values of a reference video frame.

6. The system of claim 1, wherein the sequence of video frames include multi-spectral pixel data, and wherein the prediction module includes:

a module to estimate pixel values corresponding to one or more of the spectrums from pixel values corresponding to one or more other ones of the spectrums.

7. The system of claim 1, further including:

a module to read the code value, the corresponding symbol counts, and the un-encoded pixel values from the data stream;

a decoder module to decode the sequence of symbols from the code value read from the data stream; and

a corrector module to reconstruct the sequence of video frames from the decoded sequence of symbols and the un-encoded reference pixel values in accordance with the one or more models.

8. The system of claim 7, wherein the corrector module includes:

a module to estimate the pixel values from the un-encoded pixel values in accordance with the one or more models; and

a module to combine the estimated pixel values with the corresponding decoded symbols.

9. The system of claim 7, wherein the decoder module includes:

a module to associate the symbols with portions of a code range in proportion to occurrences of the symbols within the sequence of symbols, as identified by the symbol count read from the data stream;

a module to populate a table with the code ranges associated with the symbols and to order the table in accordance with the proportions; and

a module to search the table in accordance with the ordering of the table to identify a code range that corresponds to the code value, to identify a corresponding symbol, and to arithmetically remove the identified symbol from the code value, iteratively for each of the symbols.

10. A system, comprising:

a module to arithmetically encode a sequence of symbols as a floating point integer code value, including to associate the symbols with portions of a code range in proportion to occurrences of the symbols within the sequence of symbols, and to iteratively refine the code range in accordance with the proportions associated with the symbols; and

an underflow a module to reduce a number of digits in one or more of a lower limit and an upper limit of the code range when the most significant digits of the lower limit and the upper limit differ by one and a number of digits of at least one of the lower limit and the upper limit exceed a threshold.

11. The system of claim 10, wherein the underflow module includes:

a module to remove a second most significant digit of the lower limit and the upper limit, to shift remaining digits of the lower and upper limits towards the corresponding second most significant digit, and to increment a count k, when the most significant digit of the lower limit and the upper limit differ by one and the number of digits of at least one of the lower and upper limits exceeds the threshold;

a module to detect when a most significant digit of the lower limit and an upper limit are equal to one another and to output the most significant digit as a next significant digit of the code value; and

a module to output k zeros as the next k significant bits of the code value when the most significant bit of the lower limit is incremented to equal the most significant digit of the upper limit, and to output k nines as the next k significant bits of the code value when the most significant bit of the upper limit is decremented to equal the most significant digit of the lower limit.

12. The system of claim 10, further including a decoder module to decode the sequence of symbols from the code value, wherein the decoder module includes:

a module to associate the symbols with portions of a code range in proportion to occurrences of the symbols within the sequence of symbols;

a module to populate a table with the code ranges associated with the symbols, and to order the table in accordance with the proportions; and

a module to search the table in accordance with the ordering of the table to identify a code range that corresponds to the code value, to identify a corresponding symbol, and to arithmetically remove the identified symbol from the code value, iteratively for each of the symbols.

13. A method, comprising:

receiving pixel values associated with a sequence of video frames;

estimating pixel values of at least a portion of the video frames in accordance with one or more models and generating a sequence of symbols corresponding to differences between the estimated pixel values and corresponding received pixel values;

arithmetically encoding a sequence of symbols as a floating point integer code value, including associating the symbols with portions of a code range in proportion to occurrences of the symbols within the sequence of symbols, and iteratively refining the code range in accordance with the proportions associated with the symbols;

reducing a number of digits in one or more of a lower limit and an upper limit of the code range when the most significant digits of the lower limit and the upper limit differ by one and a number of digits of at least one of the lower limit and the upper limit exceed a threshold; and

formatting and outputting the code value, symbol counts associated with the code value, and un-encoded reference pixel values, in a data stream;

wherein the receiving, the estimating, the arithmetically encoding, the reducing, and the formatting, are performed in a suitably programmed computer system.

14. The method of claim 13, wherein the reducing includes:

removing a second most significant digit of the lower limit and the upper limit, shifting remaining digits of the lower and upper limits towards the corresponding second most significant digit, and increment a count k, when the most significant digit of the lower limit and the upper limit differ by one and the number of digits of at least one of the lower and upper limits exceeds the threshold;

detecting when a most significant digit of the lower limit and the upper limit are equal to one another and outputting the most significant digit as a next significant digit of the code value;

outputting k zeros as the next k significant bits of the code value when the most significant bit of the lower limit is incremented to equal the most significant digit of the upper limit; and

outputting k nines as the next k significant bits of the code value when the most significant bit of the upper limit is decremented to equal the most significant digit of the lower limit.

15. The method of claim 13, further including:

representing pixel values with multiple-bytes, including a most significant byte and a least significant byte;

estimating most significant byte pixel values from first byte reference pixel values; and

estimating least significant byte pixel values from least significant byte reference pixel values.

16. The method of claim 15, wherein the sequence of video frames corresponds to a sequence of infrared images and adjacent ones of the images are substantially similar to one another, the method further including:

representing the symbols with multiple-bytes, including a most significant byte and a least significant byte;

wherein differences between pixel values of the sequence of infrared images and corresponding pixel values of a reference image are relatively small, the symbols are predominantly relatively small positive and negative values, and the most significant bytes of the pixel difference values are predominantly one of all zeros and all ones.

17. The method claim 13, wherein the estimating includes:

estimating pixel values of a video frame as pixel values of a reference video frame.

18. The method claim 13, wherein the sequence of video frames include multi-spectral pixel data, and wherein the estimating includes:

estimating pixel values corresponding to one or more of the spectrums from pixel values corresponding to one or more other ones of the spectrums.

19. The method of claim 13, further including:

reading the code value, the corresponding symbol counts, and the un-encoded pixel values from the data stream;

decoding the sequence of symbols from the code value read from the data stream; and

estimating the pixel values from the un-encoded pixel values in accordance with the one or more models; and

combining the estimated pixel values with the corresponding decoded symbols to reconstruct the sequence of video frames.

20. The method claim 19, wherein the decoding includes:

associating the symbols with portions of a code range in proportion to occurrences of the symbols within the sequence of symbols, as identified by the symbol count read from the data stream;

populating a table with the code ranges associated with the symbols, and ordering the table in accordance with the proportions; and

searching the table in accordance with the ordering of the table to identify a code range that correspond to the code value, identifying a corresponding symbol, and arithmetically removing the identified symbol from the code value, iteratively for each of the symbols.