US5751859A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compression of text images by soft pattern matching
Assignee: Nokia of America Corp
•
Filing: 1995-06-14
•
Granted: 1998-05-12
•
Expires: 2015-06-14
Abstract
Abstract Bilevel textual images are compressed by segmenting the image into marks (401) and then coding each mark using a soft pattern matching method. Each mark is compared (403) with the marks in a library of marks and if an acceptable match is found (404), the index of the matching mark is coded (412). Each pixel in a current mark is then coded using a statistical coder that codes each pixel based on the value of the pixel and a set of probabilities of all sample values based on a context that consists of pixels in the current mark and pixels in the matching mark (414, 415, 416, 417). In order to reduce the overall bit count of the image, pixels which are poorly predicted (i.e., pixels black or white! in value, but whose context makes them more likely to be white or black!)) (705) are color-reversed (706, 709) prior to coding, if so doing will not perceptibly alter a reconstructed image (708). If a matching mark is not found among the marks in the library, each pixel in the mark is coded using a statistical coder using a context of pixels in the non-matching mark (406, 407, 408, 409, 410). Again, pixels which are poorly predicted (721) are color-reversed (722, 725) prior to coding if the reversed pixels will not perceptibly alter the image (724).
Inventors
- 👤 Paul Glor Howard
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 14:40
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/001
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
95 words
A method for compressing the length of a bitstream representing coded samples of a digitally sampled analog signal in a system which encodes each sample of the analog signal using a statistical coder that codes each sample based on the value of the sample and the set of probabilities of all possible sample values, the method comprising the step of: modifying to a more probable value an actual value of a selected sample whose probability of occurrence of such actual value is less than the probability of occurrence of at least one other possible value.
Claim 2
Independent Claim
95 words
A method for compressing the length of a bitstream representing coded samples of a digitally sampled analog signal in a system which encodes each sample of the analog signal using a statistical coder that codes each sample based on the value of the sample and the set of probabilities of all possible sample values, the method comprising the step of: modifying to a more probable value an actual value of a selected sample whose probability of occurrence of such actual value is less than the probability of occurrence of at least one other possible value.
Claim 3
Dependent Claim
89 words
The method of claim 1 further comprising the steps of (1) prior to modifying an actual value of a selected sample to the more probable value, determining whether an encoded signal that would be converted back to an analog signal using the more probable value of the selected sample would be imperceptibly different from the original digitally sampled analog signal; and (2) modifying the selected sample to the more probable value only if the converted back analog signal would be imperceptibly different from the original digitally sampled analog signal.
Claim 4
Independent Claim
97 words
A method for compressing a digitally sampled original image in which one or more bits represent the value of each pixel in the image, each pixel being coded using a statistical coding method that codes each pixel based on the value of the pixel and the set of probabilities of all possible pixel values, the method comprising the step of: modifying to a more probable value an actual value of at least one selected pixel whose probability of occurrence of such actual value is less than the probability of occurrence of at least one other possible value.
Claim 5
Independent Claim
97 words
A method for compressing a digitally sampled original image in which one or more bits represent the value of each pixel in the image, each pixel being coded using a statistical coding method that codes each pixel based on the value of the pixel and the set of probabilities of all possible pixel values, the method comprising the step of: modifying to a more probable value an actual value of at least one selected pixel whose probability of occurrence of such actual value is less than the probability of occurrence of at least one other possible value.
Claim 6
Dependent Claim
71 words
The method of claim 3 further comprising the steps of (1) prior to modifying an actual value of a selected pixel to the more probable value, determining whether an image that would be recreated from the modified value of the selected pixel would be imperceptibly different from the original image; and (2) modifying the value of the pixel only if the recreated image would be imperceptibly different from the original image.
Claim 7
Dependent Claim
65 words
The method of claim 4 wherein the step of determining whether an image that would be created from the modified value of the selected pixel would be imperceptibly different from the original image comprises the step of determining whether the selected pixel is isolated from other selected pixels or is one of a small group of selected pixels which are isolated from other selected pixels.
Claim 8
Independent Claim
218 words
A method for compressing a bilevel image of textual information, the bilevel image being scanned into black and white pixels, the method comprising the steps of: segmenting the pixels of the image into marks; comparing the pixels from a current mark with the pixels in a set of marks in a library of marks; determining whether the current mark matches one of the marks in the library of marks using a predetermined measure of acceptability; if the current mark matches one of the marks in the library, coding an index of the matching mark and comparing the pixels in the current mark with the pixels in the matching mark; for each pixel from the current mark that does not match a corresponding pixel in the matching mark, tentatively flipping the value of the pixel; for each tentatively flipped pixel from the current mark, determining whether the pixel is isolated from other tentatively flipped pixels from the current mark or part of a small isolated group of pixels that are separated from other tentatively flipped pixels from the current mark; permanently flipping the value of each tentatively flipped pixel from the current mark that is isolated or part of a small isolated group; and coding each permanently flipped pixel value from the current mark using a statistical coding method.
Claim 9
Independent Claim
218 words
A method for compressing a bilevel image of textual information, the bilevel image being scanned into black and white pixels, the method comprising the steps of: segmenting the pixels of the image into marks; comparing the pixels from a current mark with the pixels in a set of marks in a library of marks; determining whether the current mark matches one of the marks in the library of marks using a predetermined measure of acceptability; if the current mark matches one of the marks in the library, coding an index of the matching mark and comparing the pixels in the current mark with the pixels in the matching mark; for each pixel from the current mark that does not match a corresponding pixel in the matching mark, tentatively flipping the value of the pixel; for each tentatively flipped pixel from the current mark, determining whether the pixel is isolated from other tentatively flipped pixels from the current mark or part of a small isolated group of pixels that are separated from other tentatively flipped pixels from the current mark; permanently flipping the value of each tentatively flipped pixel from the current mark that is isolated or part of a small isolated group; and coding each permanently flipped pixel value from the current mark using a statistical coding method.
Claim 10
Dependent Claim
67 words
The method of claim 6 wherein the statistical coding method for each permanently flipped pixel value from the current mark comprises the steps of: determining a context of each pixel; determining a probability associated with the determined context of each pixel; and coding the value of each pixel based on both the probability associated with the context of the pixel and an actual value of the pixel.
Claim 11
Dependent Claim
49 words
The method of claim 7 wherein the context of each pixel is determined by the values of selected pixels from the current mark surrounding the pixel being coded and the values of selected pixels in the matching mark including and surrounding the pixel corresponding to the pixel being coded.
Claim 12
Dependent Claim
25 words
The method of claim 8 wherein an arithmetic coder is used to code the value of each pixel based on its value and its context.
Claim 13
Dependent Claim
36 words
The method of claim 8 further comprising the step of adding the current mark to the library of marks if the current mark and the matching mark differ by more that a measurably determinable predetermined difference.
Claim 14
Dependent Claim
161 words
The method of claim 6, wherein if the current mark does not match one of the marks in the library, the method further comprises the steps of: determining for each pixel in the current non-matching mark whether the pixel is the same as a predetermined number of preselected neighbor pixels; if the pixel is not the same as said predetermined number of preselected neighbor pixels, tentatively flipping the value of the pixel; for each tentatively flipped pixel in the current non-matching mark, determining whether the pixel is isolated from other tentatively flipped pixels in the current non-matching mark or part of a small isolated group of pixels that are separated from other tentatively flipped pixels in the current non-matching mark permanently flipping the value of each tentatively flipped pixel in the current non-matching mark that is isolated or part of a small isolated group; and coding each permanently flipped pixel value in the current non-matching mark using a statistical coding method.
Claim 15
Dependent Claim
65 words
The method of claim 11 wherein the statistical coding method for each pixel in the current non-matching mark comprises the steps of: determining a context of each pixel; determining a probability associated with the determined context of each pixel; and coding the value of each pixel based on both the probability associated with the context of the pixel and an actual value of the pixel.
Claim 16
Dependent Claim
29 words
The method of claim 12 wherein the context of a pixel in the current non-matching mark is determined by the values of selected pixels surrounding the pixel being coded.
Claim 17
Dependent Claim
25 words
The method of claim 13 wherein an arithmetic coder is used to code the value of each pixel based on its value and its context.
Claim 18
Dependent Claim
20 words
The method of claim 13 further comprising the step of adding the current non-matching mark to the library of marks.
Claim 19
Dependent Claim
21 words
The method of claim 6 further comprising the step of ignoring a mark if its size is below a predetermined threshold.
Claim 20
Dependent Claim
16 words
The method of claim 6 further comprising the step of smoothing the edges of a mark.
Claim 21
Dependent Claim
28 words
The method of claim 17 wherein the step of smoothing the edges of a mark comprises the step of removing single protruding pixels along edges of the mark.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-11 | 2001-11-10 | 2002-05-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-11 | 2005-11-10 | 2006-05-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-11 | 2009-11-10 | 2010-05-12 | $7700.00 | Window Closed / Lapsed |