US4610027A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for converting a bit map of an image to a run length or run end representation
Assignee: International Business Machines Corp
•
Filing: 1983-12-30
•
Granted: 1986-09-02
•
Expires: 2003-12-30
Abstract
Abstract A method for converting an image from a bit map to a run end or run length representation includes the steps of: storing said image as a bit map representation; initializing all variables to be used in the conversion process; converting by table lookup, each run of continuous color to a run representation, storing, in a run representation buffer, as a count value, each run representation; repeating the steps of converting and storing for each run of continuous color to the end of the image.
Inventors
- 👤 Karen L. Anderson
- 👤 Gerald Goertzel
- 👤 Joan L. Mitchell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 03:49
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/46; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/419
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
469 words
A method for converting an image stored as a bit map in binary form, with alternating bit strings of either of two types, to a run representation form, comprising the steps of: (a) segmenting a first line of bit strings of said bit map into units of equal number of bits for use in indexing lookup tables; (b) creating a first lookup table which contains, for each possible unit used as an index value, the number of leading bits in the unit which are of the first binary type; (c) creating a second lookup table which contains, for each possible unit used an an index value, the number of leading bits in the unit which are of the second binary type; (d) converting the first line of said image to run representation form by the steps of: (1) converting the first bit string in said first line to a run representation by: (i) determining the length of said first bit string by using the first and successive units as indices to said first lookup table to obtain the number of leading bits in each unit which belong to said first bit string until a unit is found wherein not all of the bits belong to said first string; (ii) storing the run representation of said first string in a run representation buffer; and (iii) modifying said unit wherein not all of the bits belong to said first string by discarding those leading bits in said unit that belong to said first bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; (2) converting the second bit string in said line to a run representation by: (i) determining the length of said second bit string by using said modified unit, ignoring said non-image bits, and successive units as indices to said second lookup table to obtain the number of leading bits in each unit which belong to said second bit string until a unit is found wherein not all of the bits belong to said second string; (ii) storing the run representation of said second string in said run representation buffer; and (iii) modifying said unit wherein not all of the bits belong to said second string by discarding those leading bits in said unit that belong to said second bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; (3) repeating said steps of converting for successive bit strings until all of the bit strings in said first line have been stored in run representation form in said run representation buffer; and (e) repeating the steps of segmenting and converting for successive lines to the end of the image.
Claim 2
Independent Claim
469 words
A method for converting an image stored as a bit map in binary form, with alternating bit strings of either of two types, to a run representation form, comprising the steps of: (a) segmenting a first line of bit strings of said bit map into units of equal number of bits for use in indexing lookup tables; (b) creating a first lookup table which contains, for each possible unit used as an index value, the number of leading bits in the unit which are of the first binary type; (c) creating a second lookup table which contains, for each possible unit used an an index value, the number of leading bits in the unit which are of the second binary type; (d) converting the first line of said image to run representation form by the steps of: (1) converting the first bit string in said first line to a run representation by: (i) determining the length of said first bit string by using the first and successive units as indices to said first lookup table to obtain the number of leading bits in each unit which belong to said first bit string until a unit is found wherein not all of the bits belong to said first string; (ii) storing the run representation of said first string in a run representation buffer; and (iii) modifying said unit wherein not all of the bits belong to said first string by discarding those leading bits in said unit that belong to said first bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; (2) converting the second bit string in said line to a run representation by: (i) determining the length of said second bit string by using said modified unit, ignoring said non-image bits, and successive units as indices to said second lookup table to obtain the number of leading bits in each unit which belong to said second bit string until a unit is found wherein not all of the bits belong to said second string; (ii) storing the run representation of said second string in said run representation buffer; and (iii) modifying said unit wherein not all of the bits belong to said second string by discarding those leading bits in said unit that belong to said second bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; (3) repeating said steps of converting for successive bit strings until all of the bit strings in said first line have been stored in run representation form in said run representation buffer; and (e) repeating the steps of segmenting and converting for successive lines to the end of the image.
Claim 3
Dependent Claim
39 words
A method according to claim 1, further comprising the step of: inserting a representation of additional bits as padding at the beginning of the bit string run representations in said run representation buffer in accordance with a predetermined format.
Claim 4
Dependent Claim
31 words
A method according to claim 1, further comprising the step of: testing continguous units to determine if all their bits have a same value to reduce processing time for long strings.
Claim 5
Dependent Claim
56 words
A method according to claim 1, wherein said step of converting further comprises converting bit strings to run representation form in pairs consisting of one run of said first binary type and a second run of said second binary type, utilizing knowledge of the type of a particular bit string being converted to improve processing efficiency.
Claim 6
Dependent Claim
29 words
A method according to claim 1 further comprising the step of: assigning first and second address pointers to locate bit string data and run representation data for each run.
Claim 7
Dependent Claim
39 words
A method according to claim 1, further comprising the step of inserting a representation of additional bits as padding at the end of the bit string run representations in said run representation buffer in accordance with a predetermined format.
Claim 8
Dependent Claim
13 words
A method according to claim 1 wherein said run representations comprise run ends.
Claim 9
Dependent Claim
13 words
A method according to claim 1 wherein said run representations comprise run lengths.
Claim 10
Dependent Claim
27 words
A method according to claim 1 further comprising the step of storing a representation of the length of the run representation buffer in the run representation buffer.
Claim 11
Dependent Claim
29 words
A method according to claim 1 further comprising the step of storing three zero run representations in the run representation buffer prior to storing the bit string run representations.
Claim 12
Dependent Claim
44 words
A method according to claim 1 further comprising the step of storing the run representations in pairs with the first representation of each pair representing a run of said first binary type and the second representation representing a run of said second binary type.
Claim 13
Dependent Claim
28 words
A method according to claim 1 further comprising the step of storing a copy of the run representation of the last bit string in said run representation buffer.
Claim 14
Dependent Claim
417 words
Apparatus for converting an image stored as a bit map in binary form, with alternating bit strings of either of two types, to a run representation form, comprising: means for segmenting a first line of bit strings into units of equal numbers of bits for use in indexing lookup tables; lookup table means for containing, for each possible unit used as an index value, the number of leading bits in each unit which are of the first binary type and the number of leading bits in each unit which are of the second binary type; means for converting the first bit string in said first line to a run representation by using the first and successive units as indices to said lookup table means to obtain the number of leading bits in each unit which belong to said first bit string until a unit is found wherein not all of the bits belong to said first string, indicating the end of said first string has been encountered; buffer means for storing run representations; means for storing the run representation of said first bit string in said run representation buffer means when the end of said string is encountered; means for modifying said unit wherein not all of the bits belong to said first bit string by discarding those leading bits in said unit that belong to said first bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; means for converting the second bit string to a run representation by using the said modified unit, ignoring said non-image bits, and successive units as indices to said lookup table means to obtain the number of leading bits in each unit which belong to said second bit string until a unit is found wherein not all of the bits belong to said second string; means for storing the run representation of said second string in said run representation buffer means; means for modifying said unit wherein not all of the bits belong to said second bit string by discarding those leading bits in said unit that belong to said second bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; and means for actuating said segmenting, converting, modifying, and storing means for successive bit strings in said first line and each following line to the end of the image.
Claim 15
Dependent Claim
417 words
Apparatus for converting an image stored as a bit map in binary form, with alternating bit strings of either of two types, to a run representation form, comprising: means for segmenting a first line of bit strings into units of equal numbers of bits for use in indexing lookup tables; lookup table means for containing, for each possible unit used as an index value, the number of leading bits in each unit which are of the first binary type and the number of leading bits in each unit which are of the second binary type; means for converting the first bit string in said first line to a run representation by using the first and successive units as indices to said lookup table means to obtain the number of leading bits in each unit which belong to said first bit string until a unit is found wherein not all of the bits belong to said first string, indicating the end of said first string has been encountered; buffer means for storing run representations; means for storing the run representation of said first bit string in said run representation buffer means when the end of said string is encountered; means for modifying said unit wherein not all of the bits belong to said first bit string by discarding those leading bits in said unit that belong to said first bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; means for converting the second bit string to a run representation by using the said modified unit, ignoring said non-image bits, and successive units as indices to said lookup table means to obtain the number of leading bits in each unit which belong to said second bit string until a unit is found wherein not all of the bits belong to said second string; means for storing the run representation of said second string in said run representation buffer means; means for modifying said unit wherein not all of the bits belong to said second bit string by discarding those leading bits in said unit that belong to said second bit string and shifting the remaining image bits to the leading bit positions in said modified unit while introducing non-image bits in the trailing positions; and means for actuating said segmenting, converting, modifying, and storing means for successive bit strings in said first line and each following line to the end of the image.
Claim 16
Dependent Claim
22 words
Apparatus as in claim 13 wherein said run representation buffer means comprises a run representation buffer for each line of image data.
Claim 17
Dependent Claim
26 words
Apparatus as in claim 14 further comprising means for storing a representation of the length of each run representation buffer in the respective run representation buffer.
Claim 18
Dependent Claim
28 words
Apparatus as in claim 14 further comprising means for storing three zero run representations in each run representation buffer prior to storing the bit string run representations therein.
Claim 19
Dependent Claim
42 words
Apparatus as in claim 14 further comprising means for storing the run representations in pairs with the first representation of each pair representing a run of said first binary type and the second element representing a run of said second binary type.
Claim 20
Dependent Claim
26 words
Apparatus as in claim 14 further comprising means for storing a copy of the run representation of the last bit string in each run representation buffer.
Claim 21
Dependent Claim
29 words
Apparatus as in claim 13, further comprising means for testing contiguous units to determine if all their bits have a same value to reduce processing time for long strings.
References Cited (Backward Citations)
US3980809A
Cited
US4121259A
Cited
US4207599A
Cited
US4327379A
Cited
US4386373A
Cited
US4516173A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-09-01 | 1990-03-03 | 1990-09-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-09-01 | 1994-03-03 | 1994-09-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-09-01 | 1998-03-03 | 1998-09-02 | $7700.00 | Window Closed / Lapsed |