Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-12-21
2004-01-06
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Lossless compression
C382S245000, C382S246000, C382S247000, C358S426010, C358S426130
Reexamination Certificate
active
06674912
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a data compression processing method and apparatus for compressing still image data and, more particularly, to a data compression processing method and apparatus able to achieve high-speed compression processing by reducing a processing time required to perform compression processing on still image data according to a Modified Modified READ (or Relative element address designate) coding scheme (hereunder referred to simply as an MMR coding scheme).
2. Description of the Related Art
Currently, a still image of a document, which is handled by a facsimile, is fundamentally a binary image, each pixel of which is represented by two levels, that is, white and black levels. Thus, the image consists of pixels represented by binary image data.
Further, in binary document images handled by a facsimile, sequences of a certain number of consecutive white pixels or black pixels frequently appear. Thus, usually, data compression processing is performed on such mass binary image data by using the MMR coding scheme and coding positions in each of which a change in color between a white run and a black run occurs.
In the case of the compression processing of image data according to this MMR coding scheme, among pixels of a coding line in an image, the position of a changing pixel, at which the color thereof changes from that of the consecutive pixels of the preceding sequence, is coded. Further, the line preceding the coding line is employed as a reference line. Then, the distance between a changing pixel, at which the color thereof changes from that of the consecutive pixels of the preceding sequence, of the reference line and the changing pixel of the coding line is coded.
Thus, to perform the compression processing of image data according to the MMR coding scheme, the positions of changing pixels a
0
, a
1
, and a
2
of the bottom line, namely, the coding line, and those of the changing pixels b
1
, and b
2
of the top line, namely, the reference line are detected. After the positions of these changing pixels are detected, the coding is performed by selecting one of a pass mode, a vertical mode, and a horizontal mode according to the positional relation among a starting or reference changing pixel a
0
, and the changing pixels a
1
, a
2
, b
1
, and b
2
(defined in CCITT Recommendation T.
6
).
However, in the case of image data of high resolution, for example, the distance between the starting changing pixel a
0
and the changing pixel a
1
is long. Thus, the number of bits corresponding to this distance is very large.
In the case of the related art coding scheme, the position of a current pixel is shifted from the position of the pixel a
0
bit by bit until a black pixel is detected. The position of the detected black pixel is designated by “a1”. Further, the number of times of shifting the position from a
0
to a
1
is determined as the distance therebetween.
In this way, the process proceeds by repeating the shifting of the current position of the changing pixel until a black pixel is detected. Further, the position of the detected black pixel is designated by “a1”. Thus, in the case that the distance between the pixels a
0
and a
1
is long, the number of times of shifting the current position of the changing pixel, which is needed for detecting the position of the pixel a
1
, is large.
Such a process proceeds by shifting the position bit by bit for detecting the position of each of the pixels a
2
, b
1
, and b
2
in addition to the pixel a
1
. Thus, the higher the resolution of a still image, the larger the number of times of shifting the current position of the changing pixel. Consequently, a long processing time is required to achieve the coding.
Accordingly, an object of the present invention is to realize high speed compression processing, which is performed according to the MMR coding scheme, by reducing the number of times of repeating the shifting process, which is required to detect the positions of the changing pixels a
1
, a
2
, b
1
, and b
2
.
SUMMARY OF THE INVENTION
To achieve the foregoing object, according to an aspect of the present invention, there is provided a data compression processing method, which comprises the steps of producing a bit string corresponding to pixel data obtained from an image, and sequentially fetching data byte by byte from the bit string, searching a table describing the number of consecutive bits that are arranged to the right of and have the same color as each of bits of each byte of all bit patterns represented by bits included in 1 byte, and detecting the number of consecutive bits that are arranged to the right of and have the same color as each of bits of each of the fetched bytes according to the bit patterns represented by bits of each of the fetched bytes, and detecting the number of consecutive bits that are arranged to the right of and have the same color as each of bits of each fetched byte, and determining a pixel placed at a position corresponding to a number obtained by adding 1 to the detected number of consecutive bits, as a color changing pixel, and thus obtaining the position of each changing pixel in each of the sequentially fetched bytes, and coding the image data according to the position of each of the changing pixels.
Further, according to an embodiment of this compression processing method of the present invention, a reference line and a coding line are set according to the bit string. Then, a bit string of each of the reference line and the coding line is produced. Subsequently, data are sequentially fetched byte by byte from each of the reference line and the coding line. Subsequently, the positions of changing pixels on each of the reference line and the coding line are obtained. Then, the MMR coding is performed by computing the distance between the changing pixels. Thus, the position of the starting changing pixel on the coding line is set to be the position of the starting changing pixel on the reference line.
Moreover, according to another aspect of the present invention, there is provided a data compression processor, which comprises an input buffer, to which pixel data of an image is inputted, for producing and holding a bit string, a lookup table unit for storing at least a table that describes the number of bits, which are arranged to the right of and have the same color as each of bits of each byte of all bit patterns represented by bits included in 1 byte, and a compression processing unit for fetching a bit string of image data from the input buffer. The compression processing unit reads the pixel data from the input buffer byte by byte, and performs compression processing by obtaining the position of a changing pixel according to the number of bits of the same color as that of each of bits detected from the table according to bit patterns that are represented by bits included in the read byte.
REFERENCES:
patent: 5067023 (1991-11-01), Kim
patent: 5204756 (1993-04-01), Chevion et al.
patent: 5610727 (1997-03-01), Kamioka
patent: 59-58971 (1984-04-01), None
patent: 61-224731 (1986-10-01), None
patent: 5-260322 (1993-10-01), None
patent: 7-322077 (1995-12-01), None
Igarashi Isao
Shimada Tsuyahiko
Shimada Yoshiharu
Arent Fox Kintner & Plotkin & Kahn, PLLC
Bayat Ali
Mehta Bhavesh M.
LandOfFree
Data compression processing method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression processing method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression processing method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3255168