Image compression using variable bit size run length encoding
AssigneeATI Technologies ULC
InventorEdward W. Brakus, Jr.
Life of this patent
Estimating the term…
Abstract
Variable bit size run length encoding (“RLE”) is used to encode uninterrupted runs of adjacent first symbols and adjacent second symbols within a sequence that may represent an image. The symbols may be 1s and 0s. The bit size used to encode a run length for a current run is varied in dependence on the bit sized used or required to encode a run length of a previous run of the same symbol type. Further, an image to be encoded may be transformed into an image/bit sequence representing changes from line to line in the image. By so transforming the image, the correlation from run length to run length of like colors is increased, thereby improving the efficiency of the variable bit size RLE.
Claims29
A method of encoding a bit sequence of alternating runs of adjacent 1s and adjacent 0s, said method comprising:
- determining the run-length of each of said runs of adjacent 0s in said sequence;
- determining the run-length of each of said runs of adjacent 1s in said sequence;
- encoding each of said run-lengths of said runs of adjacent 0s using a varying bit size, wherein said varying bit size used to encode each of said run-lengths of adjacent 0s is varied in dependence on the bit size used to encode a run-length of a prior run of adjacent 0s in said bit sequence.
A method of decoding a series of run-lengths into alternating runs of adjacent 0s and 1s representing computer readable data, said run lengths encoded using varying numbers of bits, said method comprising:
- determining an assumed bit size used to encode a current run-length of 0s based on a bit size used to decode an immediately prior run length of 0s;
- increasing said assumed bit size of said current run-length if all bits in said run length having said assumed bit size have a defined pattern, to form an adjusted bit size where all bits in said run-length having said adjusted bit size do not have said defined pattern;
- extracting a number of adjacent 0s, said number based on a value in binary of said run-length having said adjusted bit size.
A computing device comprising a processor in communication with processor readable memory storing processor executable instructions, adapting said computing device to encode a bit sequence of alternating runs of adjacent 1s and adjacent 0s, by:
- determining the run-length of each of said runs of adjacent 0s in said sequence;
- determining the run-length of each of said runs of adjacent 1s in said sequence;
- encoding each of said run-lengths of said runs of adjacent 0s using a varying bit size,
- wherein said varying bit size used to encode each of said run-lengths of adjacent 0s is varied in dependence on the bit size used to encode a run-length of a prior run of adjacent 0s in said bit sequence.
Computer readable memory storing computer executable instructions, that when executed at a computing device adapt said computing device to encode a bit sequence of alternating runs of adjacent 1s and adjacent 0s, by:
- determining the run-length of each of said runs of adjacent 0s in said sequence;
- determining the run-length of each of said runs of adjacent 1s in said sequence;
- encoding each of said run-lengths of said runs of adjacent 0s using a varying bit size, wherein said varying bit size used to encode each of said run-lengths of adjacent 0s is varied in dependence on the bit size used to encode a run-length of a prior run of adjacent 0s in said bit sequence.
Computer readable medium storing a bit sequence representing a plurality of sequential tokens of varying bit sizes, each token representing one of i) data encoding a run length in a sequence of first and second symbols;
- and ii) an indicator that the bit size of the next token in said plurality of sequential tokens has changed from the size of the current token.
A method of encoding a sequence of alternating runs of adjacent first symbols and adjacent second symbols, said method comprising:
- determining the run-length of each of said runs of adjacent first symbols in said sequence;
- determining the run-length of each of said runs of adjacent second symbols in said sequence;
- encoding each of said run-lengths of said runs of adjacent first symbols using a varying bit size, wherein said varying bit size used to encode each of said run-lengths of adjacent first symbols is varied in dependence on the bit size used to encode a run-length of a prior run of adjacent first symbols in said sequence.
A data providing medium providing a bit sequence representing a plurality of sequential tokens of varying bit sizes, each token representing one of i) data encoding a run length in a sequence of first and second symbols;
- and ii) an indicator that the bit size of the next token in said plurality of sequential tokens has changed from the size of the current token.
Dependencies are inferred from the claim text.