Patent US4502776A successfully refreshed from Google Patents.
Patent US4888645A successfully refreshed from Google Patents.
US4888645A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for encoding and decoding a digital image
Assignee: International Business Machines Corp
•
Filing: 1987-10-21
•
Granted: 1989-12-19
•
Expires: 2007-10-21
Abstract
Abstract A method for encoding and decoding digital image data, includes the steps of: testing the data for a vertical relationship between adjacent lines of the image; generating directly a reference code word representative of the vertical relationship for each successful test; generating by table lookup a run code word for a stream of data bits of common value for each unsuccessful test whereby a data element representing a number of bits in a code word is stored at a predetermined offset from a table entry for the code word; merging the vertical reference code words and the run code words generated by the above steps to form an encoded data stream; testing the encoded data stream for a reference code; decoding directly the vertical relationship from the reference code for each successful test; decoding by table lookup a run of bits of common value by serial examination of said encoded data stream for each unsuccessful test; and storing data decoded by the above steps in a predetermined relationship. A fast algorithm for modifying an image in run representation form before encoding or after decoding is also described.
Inventors
- 👤 Joan L. Mitchell
- 👤 Karen L. Anderson
- 👤 Gerald Geortzel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 17:23
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/417; H04N1/4175; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
204 words
A method for encoding a binary digital image constituted by strings of bits of one or the other binary value, comprising the steps of: dividing said image into lines of bits containing digital information indicative of said binary values; 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 encoding said line representations by the steps comprising: testing each run end on a given line for a predetermined relationship with another run end on at least one adjacent line; generating directly a reference code word representative of said predetermined relationship for each successful test; 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; and merging said reference code words and said run code words generated by the above steps to form an encoded data stream; and repeating said representing and encoding steps on other image lines to code the lines of the image in sequence.
Claim 2
Independent Claim
204 words
A method for encoding a binary digital image constituted by strings of bits of one or the other binary value, comprising the steps of: dividing said image into lines of bits containing digital information indicative of said binary values; 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 encoding said line representations by the steps comprising: testing each run end on a given line for a predetermined relationship with another run end on at least one adjacent line; generating directly a reference code word representative of said predetermined relationship for each successful test; 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; and merging said reference code words and said run code words generated by the above steps to form an encoded data stream; and repeating said representing and encoding steps on other image lines to code the lines of the image in sequence.
Claim 3
Dependent Claim
35 words
A method according to claim 1 wherein said line representations are stored in a run end buffer and each line representation contains a plurality of run representations of 0 at the beginning of the buffer.
Claim 4
Dependent Claim
37 words
A method according to claim 1 wherein said line representations are stored in a run end buffer and each line representation contains a plurality of copies of the last run end at the end of the buffer.
Claim 5
Dependent Claim
36 words
A method according to claim 1 wherein said line representations are stored in a run end buffer and each line representation contains an indication of the number of run ends contained in the run end buffer.
Claim 6
Dependent Claim
68 words
A method according to claim 1 wherein the binary value of the bits in the string of bits described by the first run end in a given line representation list is determined, and the binary value of the bits of the run for which a run end is being encoded is determined by examination of the position of said run end in said given list of run ends.
Claim 7
Dependent Claim
14 words
A method according to claim 1, further comprising the step of encoding pad lines.
Claim 8
Dependent Claim
20 words
A method according to claim 1, further comprising the step of skipping lines with digital information during the encoding step.
Claim 9
Dependent Claim
22 words
A method according to claim 1 further comprising the step of changing the vertical size of an image during the encoding step.
Claim 10
Dependent Claim
62 words
A method according to claim 1 wherein said digital image is divided into lines of equal length, and further comprising the steps of testing to determine if the end of an image line has been reached and performing said testing only if a run end being encoded has not been determined to be less than a run end on an adjacent line.
Claim 11
Independent Claim
243 words
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.
Claim 12
Independent Claim
243 words
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.
Claim 13
Dependent Claim
22 words
A method as in claim 10 further comprising the step of converting said representations of said image lines to bit map form.
Claim 14
Dependent Claim
21 words
A method as in claim 10 wherein said lines have been encoded without creating a bit map representation of said image.
Claim 15
Dependent Claim
35 words
A method as in claim 10 wherein said line representations are stored in a run end buffer and each line representation contains a plurality of run representations of 0 at the beginning of the buffer.
Claim 16
Dependent Claim
37 words
A method according to claim 10 wherein said line representations are stored in a run end buffer and each line representation contains a plurality of copies of the last run end at the end of the buffer.
Claim 17
Dependent Claim
36 words
A method according to claim 10 wherein said line representations are stored in a run end buffer and each line representation contains an indication of the number of run ends contained in the run end buffer.
Claim 18
Dependent Claim
50 words
A method according to claim 10 further comprising the step of omitting selected lines in the encoded image by omitting their representations from the decoded data stream, so that said selected lines do not appear in the final decoded image and wherein said selected lines are specified by operator control.
Claim 19
Dependent Claim
29 words
A method according to claim 10 further comprising the step during decoding of changing the vertical size of an image as it is decoded in response to operator control.
Claim 20
Dependent Claim
68 words
A method according to claim 10 wherein the binary value of the bits in the string of bits described by the first run end in a given line representation list is determined, and the binary value of the bits of the run for which a run end is being decoded is determined by examination of the position of said run end in said given list of run ends.
Claim 21
Dependent Claim
19 words
A method according to claim 10, further comprising the step of creating pad lines in the decoded line representations.
Claim 22
Dependent Claim
62 words
A method according to claim 13 wherein said digital image is divided into lines of equal length, and further comprising the steps of testing to determine if the end of an image line has been reached and performing said testing only if a run end being decoded has not been determined to be less than a run end on an adjacent line.
Claim 23
Independent Claim
442 words
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.
Claim 24
Independent Claim
442 words
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.
Claim 25
Independent Claim
220 words
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.
Claim 26
Independent Claim
220 words
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.
Claim 27
Dependent Claim
13 words
A system according to claim 22, further comprising means for encoding pad lines.
Claim 28
Dependent Claim
17 words
A system according to claim 22, further comprising means for skipping data lines during the encoding process.
Claim 29
Dependent Claim
21 words
A system according to claim 22, further comprising means for changing the vertical size of an image as it is encoded.
Claim 30
Dependent Claim
60 words
A system according to claim 22 wherein said digital image is divided into lines of equal length, and further comprising means for testing to determine if the end of an image line has been reached, and means for omitting said testing if a run end being encoded is determined to be less than a run end on an adjacent line.
Claim 31
Independent Claim
247 words
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.
Claim 32
Independent Claim
247 words
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.
Claim 33
Dependent Claim
60 words
A system according to claim 27 wherein said digital image is divided into lines of equal length, and further comprising means for testing to determine if the end of an image line has been reached, and means for omitting said testing if a run end being decoded is determined to be less than a run end on an adjacent line.
Claim 34
Dependent Claim
21 words
A system as in claim 27, further comprising means for converting said representations of said image lines to bit map form.
Claim 35
Dependent Claim
30 words
A system according to claim 27, further comprising means, under operator control, for omitting lines described in the encoded image from the final decoded image as specified by operator control.
Claim 36
Dependent Claim
29 words
A system according to claim 27, further comprising means, under operator control, for changing the vertical size of an image as it is decoded as specified by operator control.
Claim 37
Dependent Claim
17 words
A system according to claim 27, further comprising means for creating pad lines in the decoded data.
Claim 38
Independent Claim
454 words
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.
Claim 39
Independent Claim
454 words
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.
References Cited (Backward Citations)
US4212036A
Cited
US4558371A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-12-18 | 1993-06-19 | 1993-12-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-12-18 | 1997-06-19 | 1997-12-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-12-18 | 2001-06-19 | 2001-12-19 | $7700.00 | Window Closed / Lapsed |