Method for encoding and decoding a digital image

A method for decoding a data stream representing a binary digital image constituted by strings of bits of one or the other binary value and encoded as a series of image lines containing information indicative of the run ends of said strings, said information comprising at least one of (1) run code words indicative of the difference between successive run ends, and (2) reference codes indicating a predetermined relationship between a run end in one line and another run end on at least one adjacent line, comprising the steps of:

• decoding said data stream into representations of said lines, said representations each comprising a list of run ends, each list being indicative of the respective offsets from the beginning of a given line to the last bit in each string of bits of identical value in said given line, and wherein said decoding comprises the steps of:
• testing the first line representation in said encoded data stream during decoding for a reference code indicating a predetermined relationship between the run end currently being decoded and another run end on at least one adjacent line;
• decoding directly a predetermined relationship from said reference code for each successful test;
• and
• decoding a run code word indicative of the difference between said run end and the immediately
• preceding run end on the same line for each unsuccessful test;
• and
• repeating said data stream decoding step to decoding step to decode the remaining lines of said image.

A method for modifying a line in a binary image to remove predetermined numbers of pels from the beginning and end of said line and to add predetermined numbers of pels of selected binary value to the beginning and end of said line, comprising the steps of:

• representing the digital information in said line as a list of run ends in the form of offsets from the beginning of said line to the last bit in each string of bits of identical value in said line;
• storing said run ends representing said line in a run end buffer;
• modifying said stored line representation by the steps of:
• calculating the net number of pels D to be added to the beginning of the line by subtracting the predetermined number of pels to be removed from the beginning of the line from the predetermined number of pels of a selected binary value to be added to the beginning of the line;
• calculating a limit L as the sum of the number of pels of said stored line which are to be represented in the modified line and said predetermined number of pels to be removed from the beginning of the line;
• indexing through said line representation until a run end is found which exceeds said predetermined number of pels to be removed from the beginning of the line;
• if said predetermined number of pels to be added to the beginning of the line is not zero and said found run end describes a run of pels of different binary value from that of said pels to be added to the beginning of the line, storing a representation of the number of said pels to be added to the beginning of the line in an output run representation buffer;
• then
• beginning with said found run end, adding the net number of pels to be added D to each remaining run end and storing the results successively in said output run representation buffer, until a run end is found which equals or exceeds the limit L, whereupon said adding and storing is ceased;
• if said predetermined number of pels to be added to the end of the line is not zero and said run end which equals or exceeds the limit L describes a run of pels of different binary value from that of said pels to be added to the end of the line, storing the sum of L and D in said output run representation buffer;
• and then
• storing the sum of L, D, and said number of pels to be added to the end of the line in said output run representation buffer.

A system for encoding a binary digital image constituted by strings of bits of one or the other binary value, comprising:

• means for dividing said image into lines of bits containing digital information indicative of said binary values;
• means for representing the digital information on each of said lines as a list of run ends, each list being indicative of the respective offsets from the beginning of a given line to the last bit in each string of bits of identical value in said given line;
• and
• means for encoding said line representations, said encoding means comprising:
• means for testing each run end on a given line for a predetermined relationship with another run end on at least one adjacent line;
• means for generating directly a reference code word representative of said predetermined relationship for each successful test;
• means for generating a run code word for the difference between said run end and the immediately preceding run end on the same line for each case where no predetermined relationship is found:
• means for merging said reference code words and said run code words generated by said respective generating means to form an encoded data stream;
• and
• means for repeatedly activating said representing and encoding means to operate on other image lines to code the lines of the image in sequence.

A system for decoding a data stream representing a binary digital image consituted by strings of bits of one or the other binary value and encoded as a series of image lines containing information indicative of the run ends of said strings, said information comprising at least one of (1) run code words indicative of the difference between successive run ends, and (2) reference codes indicating a predetermined relationship between a run end in one line and another run end on at least one adjacent line, comprising:

• means for decoding said data stream into representations of said lines wherein said representations each comprise a list of run ends, each list being indicative of the respective offsets from the beginning of a given line to the last bit in each string of bits of identical value in said given line, and wherein said decoding means comprises:
• means for testing the first line representation in said encoded data stream during decoding for a reference code indicating a predetermined relationship between the run end currently being decoded and another run end on at least one adjacent line;
• means for decoding directly a predetermined relationship from said reference code for each successful test;
• and
• means for decoding a run code word indicative of the difference between said run end and the immediately preceding run end on the same line for each unsuccessful test;
• and
• means for repeatedly activating said data stream decoder means to decode the remaining lines of said image.

A system for modifying a line in a binary image to remove predetermined numbers of pels from the beginning and end of said line and to add predetermined numbers of pels of selected binary value to the beginning and end of said line, comprising:

• means for representing the digital information in said line as a list of run ends in the form of offsets from the beginning of said line to the last bit in each string of bits of identical value in said line;
• run end buffer means for storing said run ends representing said line as a stored line representation;
• an output run representation buffer;
• and
• means for modifying said stored line representation by the steps of:
• calculating the net number of pels D to be added to the beginning of the line by subtracting the predetermined number of pels to be removed from the beginning of the line from the predetermined number of pels of a selected binary value to be added to the beginning of the line;
• calculating a limit L as the sum of the number of pels of said stored line which are to be represented in the modified line and said predetermined number of pels to be removed from the beginning of the line;
• indexing through said line representation until a run end is found which exceeds said predetermined number of pels to be removed from the beginning of the line;
• if said predetermined number of pels to be added to the beginning of the line is not zero and said found run end describes a run of pels of different binary value from that of said pels to be added to the beginning of the line, storing a representation of the number of said pels to be added to the beginning of the line in said output run representation buffer;
• then
• beginning with said found run end, adding the net number of pels to be added D to each remaining run end and storing the results successively in said output run representation buffer, until a run end is found which equals or exceeds the limit L, whereupon said adding and storing is ceased;
• if said predetermined number of pels to be added to the end of the line is not zero and said run end which equals or exceeds the limit L describes a run of pels of different binary value from that of said pels to be added to the end of the line, storing the sum of L and D in said output run representation buffer;
• and then
• storing the sum of L, D, and said number of pels to be added to the end of the line in said output run representation buffer.