Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-06-29
2001-10-09
Britton, Howard (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S410100, C358S296000, C382S243000, C382S245000
Reexamination Certificate
active
06301300
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus useful for coding and decoding images such as line drawings that comprise mostly background area.
Black-and-white bi-level images can be encoded by run-length coding, which encodes the number of consecutive picture elements or pixels having the same value. When this type of image is transmitted by facsimile, for example, the image is scanned a line at a time, and each scanning line is encoded as run lengths specifying the relative positions of the pixels at which a change from black to white, or from white to black, occurs. In the modified Huffman (MH) code adopted in group-three facsimile equipment, the run-length information is further coded by use of variable-length coding tables, using different tables for black runs and white runs, because the two types of runs have different statistical properties.
When this type of run-length coding is applied to an image comprising mostly white background area, however, most of the coded data is used to encode long runs of background pixels. Variable-length coding of the background in this type of image is inefficient, because the variable-length coding rule forces the use of many redundant bits. If the redundancy could be reduced, higher data compression ratios could be obtained.
More efficient coding schemes, such as arithmetic coding, are known, but they tend to be computationally demanding in terms of program complexity, memory usage, and processing time.
The above problems are not limited to bi-level images, but also occurs in other types of sparse images, including images that employ several colors, or multiple shades of gray. These problems moreover occur not only in facsimile transmission, but also in image storage and retrieval, and in the transmission of image data from a computer to a printer.
SUMMARY OF THE INVENTION
An object of the present invention is to code sparse images efficiently, by reducing the amount of coded image data representing background areas.
Another object of the invention is to code and decode sparse images without extensive computation.
Another object is to code and decode sparse images without extensive memory usage.
The invented image coding method comprises the steps of:
counting runs of non-background pixels, obtaining a run count for each scanning line in the image;
counting consecutive scanning lines having run counts of zero;
coding consecutive scanning lines having run counts of zero as a first command and a first value, the first value indicating the number of scanning lines; and
coding consecutive scanning lines having identical run counts not equal to zero as a second command, a second value indicating the run count, and one-dimensional run information describing each run in each scanning line.
The second value may specify the run count directly, or may specify a value to be added to or subtracted from the previous run count. The run information may give the starting and ending coordinates of each run, or a starting coordinate and run length. If necessary, the run information may also give a single pixel value shared by all pixels in the run, a starting gray level and an ending gray level, or a starting gray level and a gray-level increment value.
The invented decoding method comprises the steps of:
analyzing the coded image data to detect the first and second commands;
generating entire scanning lines of background pixels according to the first command and its accompanying first value; and
generating scanning lines with runs of non-background pixels according to the second command, its accompanying second value, and the run information.
If necessary, the decoding method also comprises the steps of setting and modifying an internal run count according to the first command, second command, and second value, the step of assigning gray levels to the pixels in each run by interpolation between starting and ending gray levels, or the step of assigning gray levels by successively adding a gray-level increment value to a starting gray level.
The invented coder comprises a run analyzer for counting runs of non-background pixels and obtaining one-dimensional run information, a run information buffer for temporarily storing the run information for each scanning line, a run count comparator for comparing the run count of each scanning line with the run count of the preceding scanning line, an offset counter for counting consecutive scanning lines having run counts of zero, and a code assembler. The code assembler outputs a first command and first value when the run count changes from zero to a nonzero value, outputs a second command and second value when the run count changes from any value to a non-zero value, and outputs the run information stored in the run information buffer.
The invented decoder comprises a command analyzer for detecting the first and second commands, and a decoding section for generating scanning lines according to the first and second commands, first and second values, and run information. If necessary, the decoder also comprises a run counter and/or an interpolator.
REFERENCES:
patent: 3184542 (1965-05-01), Horsley
patent: 4103287 (1978-07-01), Frank
patent: 4107648 (1978-08-01), Frank
patent: 4307377 (1981-12-01), Pferd et al.
Britton Howard
Oki Data Corporation
Rabin & Berdo P.C.
LandOfFree
Method and apparatus for efficiently coding and decoding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for efficiently coding and decoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficiently coding and decoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617083