Digital image processing technique including improved gray scale compression
First Claim
1. A method for storing gray scale image data for a defined image having a plurality of individual pixels each having one of a plurality of discrete gray scale values comprising:
- (a) dividing said defined image into discrete first blocks of 8×
8 pixels each;
(b) identifying each of said blocks for which every pixel in said block has an equivalent gray scale value;
(c) for each said block identified in step (b), storing a selected code representative of said pixels in said block having equivalent grey scale values and of said gray scale value;
(d) for each block not identified, storing a second code representative of said pixels in said block not having equivalent gray scale values and subdividing said block into smaller blocks;
(e) repeating said steps (b), (c) and (d) until only 1×
2 pixel blocks remain, each pixel having a different gray scale value;
(f) then storing said second code and a third code representative of a gray scale value for a first pixel and the difference between the gray scale value of said first pixel and a gray scale value for a second pixel.
4 Assignments
0 Petitions
Accused Products
Abstract
An improved technique for gray scale compression of document image data is disclosed. The method comprises evaluating subportions of an image array as to relative levels of sameness and attempting to create sub-arrays having the same pixel value. Successively smaller sub-arrays are evaluated as to gray scale sameness unti 2×1 pixel arrays are encountered. At that time a code unique to each possible 2×1 pixel arrangement is stored. A high speed, real-time compression implementation is facilitated through described hardware. Document images are subdivided into 8 pixel by 512 pixel slices. As one document slice is stored in a first buffer RAM, a previously stored slice is compressed. As the pixel information is stored, tests are performed for 8×8 and 4×4 array sameness and one bit data stored according to the results of those tests. High speed compression is facilitated by querying the stored data as to the 8×8 and the 4×4 array sameness prior to further processing. Pixel gray scale information is provided as input to look up tables which provide coded information as to gray scale value in a variable length coded output. Status of 8×8 and 4×4 blocks as to sameness controls sequencing of the input to the look up tables. The microprocessor controller handles no pixel data but merely processes coded data for placement on appropriate bus and storage in an appropriate memory medium.
50 Citations
22 Claims
-
1. A method for storing gray scale image data for a defined image having a plurality of individual pixels each having one of a plurality of discrete gray scale values comprising:
-
(a) dividing said defined image into discrete first blocks of 8×
8 pixels each;(b) identifying each of said blocks for which every pixel in said block has an equivalent gray scale value; (c) for each said block identified in step (b), storing a selected code representative of said pixels in said block having equivalent grey scale values and of said gray scale value; (d) for each block not identified, storing a second code representative of said pixels in said block not having equivalent gray scale values and subdividing said block into smaller blocks; (e) repeating said steps (b), (c) and (d) until only 1×
2 pixel blocks remain, each pixel having a different gray scale value;(f) then storing said second code and a third code representative of a gray scale value for a first pixel and the difference between the gray scale value of said first pixel and a gray scale value for a second pixel.
-
-
2. A method for digital image processing, including compressed storage of image data:
-
(a) developing digital data for an image comprised of an array of pixels each having gray scale value; (b) defining a plurality of subportions of said image, each having a selected number of pixels; (c) storing a first code indicating whether all gray scale values in a said sub-portion are equivalent; (d) storing a second code with said first code;
representing the equivalent gray scale value if said first code indicates that all gray scale values in said sub-portion are equivalent;(e) subdividing said sub-portions into second sets of pixels if said first code indicates that all gray scale values in said sub-portion are not equivalent; (f) repeating steps (c), (d) and (e) until all sets of pixels having a first code indicating non-equivalency have been finally subdivided to a selected minimum number of pixels;
then(g) storing a third code representative of a gray scale value of a first pixel in said finally subdivided set; and (h) storing a fourth code representative of the difference between the gray scale value for said first pixel and that for subsequent pixels; (i) repeating steps (c)-(h) for each of said subportions.
-
-
3. A method for storing an image comprised of multiple pixels each having a discrete gray scale value comprising:
-
dividing said image into a plurality of 8 pixel by 8 pixel blocks; storing a first code indicative of whether all pixels in a first of said blocks have an equivalent gray scale value; storing a second code representative of said equivalent gray scale value when said first code indicates equivalency; subdividing said first block into four 4 pixel×
4 pixel sub-blocks when said first code does not indicate equivalency;storing a first code for each one of said sub-blocks indicate of whether all pixels in said each sub-block have an equivalent gray scale value; storing a second code representative of said equivalent gray scale value for said each sub-block when said first code for said each sub-block indicates equivalency; further subdividing each of said sub-blocks into four 2 pixels by 2 pixels sub-sub-blocks where said first code for said each sub-blocks does not indicate equivalency; storing a first code for each one of said sub-sub-blocks indicative of whether all pixels in said each sub-sub-block have an equivalent gray scale value; storing a second code representative of said equivalent gray scale value for said each sub-sub-block when said first code for said sub-sub-block indicates equivalency; further subdividing each of said sub-sub-blocks into two 1 pixel by 2 base blocks when said first code for said sub-sub-block does not indicate equivalency; storing a first code for said each one of said base blocks indicative of whether both pixels in said base block have an equivalent value; storing a second code representative of the gray scale value of a first of said two pixels in said base block when said first code does not indicate equivalency; storing a third code representative of the difference between the gray scale value for said first pixel and the gray scale value for a second pixel in said base block when said first code for said base block does not indicate equivalency.
-
-
4. A system for compressing gray scale image data for storage comprising:
-
first memory means for temporarily storing a selected portion of said gray scale image data; second memory means for temporarily storing information indicative of blocks of said selected portion of said image data having a constant gray scale value; processor means responsive to the information stored in said second memory means for selectively addressing said first memory means and for storing a code representative of said stored gray scale image data, said code identifying said constant gray scale value and the size of the block; third memory means for temporarily storing a second selection portion of said gray scale image data while said processor means selectively addresses said first means; and fourth memory means for temporarily storing information indicative of blocks of said second selected portion of said image data having a constant gray scale value. - View Dependent Claims (5, 6, 7, 8, 9)
-
-
10. A system for storing gray scale image data for one or more selected images in a compressed format comprising:
-
first buffer means for storing a portion of said gray scale image data having a first memory means for storing said a portion of said gray scale image data and a second memory means for storing information representing blocks of said a portion of said image data having a same gray scale value; second buffer means for storing another portion of said gray scale image data having a third memory means for storing said another portion of said gray scale image data and a fourth memory means for storing information representing blocks of said another portion of said image data having a same gray scale value; lookup table means for providing an output code indicative of stored gray scale image data; processor means for selectively addressing said first and second buffer means to provide input to said lookup table means and for providing said output code for storage. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
Specification