Coding method and coder using pattern matching

Details Coding method and coder using pattern matching Coding method and coder using pattern matching

2000-01-27

2003-02-25

Couso, Jose L. (Department: 2621)

Image analysis

Image compression or coding

Reexamination Certificate

active

06526172

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a coding method and a coder effectively using pattern matching, and more particularly to a coding method and a coder using pattern matching capable of coding image data, including character areas and image areas, at a high compression rate.
BACKGROUND OF THE INVENTION
A coding method using pattern matching is known as a method for compressing binary data including character areas and image areas. For example, the pattern matching coding method described in ISO/IEC JTC1/SC29/WG1 N205 “Loseless and Lossy Compression of Text Images by Soft Pattern Matching” (issued on Jun. 30, 1995) extracts a small unit (hereinafter called “mark”), for example, one character unit at a time, from the image, and compares it with a plurality of marks stored previously in the library. When the library contains a mark matching the extracted mark, the extracted mark is coded while referencing the mark in the library. The “match” in this description includes a perfect match as well as a close match (i.e., close to a perfect match).
FIG. 14
is a block diagram showing the configuration of a coder which executes the coding method described in the above publication. As shown in
FIG. 14
, a character/image separation unit
200
separates image data received from an input terminal
1
into two types of areas: a character area where characters concentrate and an image area where characters do not concentrate. The image data in the character area is output to a mark extraction unit
201
, while the image data in the image area is output to a coding unit
202
.
The mark extraction unit
200
extracts characters from a character area, one character at a time. The extracted character is treated as a mark. Extracted marks are output to a match checking unit
203
and a storage unit
204
. The match checking unit
203
checks if the library contains a mark that matches an extracted mark. If there is a matching mark, the match checking unit
203
outputs the extracted mark and the matching mark found in the library to a coding unit
205
. The storage unit
204
, which creates the library, adds received marks to the library.
The coding unit
205
performs arithmetic coding using the templates shown in FIGS.
15
(A) and
15
(B). That is, using the reference pixels (indicated by numbers
1
-
4
) in the template, shown in FIG.
15
(A), for the extracted mark and the reference pixels (indicated by numbers
5
-
11
) in the template, shown in FIG.
15
(B), for the extracted mark , the coding unit
205
estimates the probability at which the pixel level of the processing target pixel is, for example,
1
. In general, the coding unit
205
assigns a short code to the probability of 100% or 0%, and a longer code as the probability approaches 50%.
The reference pixel position at number
7
in FIG.
15
(B) corresponds to the position of P which is the processing target pixel. In the following description, the templates shown in FIGS.
15
(A) and
15
(B) are called match templates.
When the library does not contain a mark that matches the extracted mark, the coding unit
205
performs arithmetic coding using the template shown in FIG.
16
. That is, using the reference pixels (indicated by numbers
1
-
10
) in the template shown in
FIG. 16
, the coding unit
205
estimates the probability that the pixel level of the processing target pixel P becomes “1” and performs arithmetic coding for the estimated probability. In the following description, the template shown in
FIG. 16
is called “unmatched template”.
The coding unit
202
receives image data of an image area and codes it using a coding method suitable for compressing general binary data, for example, using the JBIG method. Coded data output from the coding units
202
and
205
is output from an output terminal
3
.
SUMMARY OF THE DISCLOSURE
As described above, when the library contains a mark that matches an extracted mark, the match template is used. That is, not only the preceding pixels in the extracted mark (past pixels in the scan direction: pixels
1
-
4
) but also those pixels ahead of (beyond) a position of the processing target pixel (future pixels in the scan direction: pixels
8
-
11
) in the mark having a high correlation with the extracted mark are used to estimate the pixel level of the processing target pixel position P. Therefore, the estimated result is more likely to be 100% or 0% and, as a result, the amount of data is reduced.
However, in the above-described coding method, the coding efficiency of an image area is not high because a standard coding method is used for it. Thus, when the image area is relatively large, the compression rate is not increased. In addition, the need to install two coding units,
202
and
205
, increases the size of the coder circuit.
The inventor of the present invention has disclosed in Japanese Patent Application No. Hei 10-110835 a coder which checks the dot frequency interval (herein may be termed as simply “frequency”) in an image area to allow a mark in the library matching an extracted mark to be used even in the image area, that is, a coder which may use a match template. Such a unit, when used, for example, in a newspaper telephotography system having relatively large dot areas, increases coding efficiency and decreases the circuit size.
However, in a system such as a color paper telephotography system, the dot angle of image data in one color differs from that of image data in another color to prevent such occurrence as Moiré. Therefore, the dot angle of image data is not always 0 degree or 45 degrees. For example, such a combination is used of a dot angle of 15 degrees in a cyan image, a dot angle of 45 degrees in a magenta image, a dot angle of 0 degree in a yellow image, and a dot angle of 75 degrees in a black image. Note that the dot angle is defined as an angle of a sequence of dots with respect to the sub scan direction of the image.
It is easy to find a dot frequency (interval) when the dot angle is 0 degree or 45 degrees. However, it is difficult to find a dot frequency when the dot angle is not 0 degree or 45 degrees. This results in more cases where no mark that matches the extracted mark is found in the library. In this case, the coding efficiency is lower than a case where the library contains the match matching the extracted mark.
In view of the foregoing, it is an object of the present invention to provide a coding method and a coder which use pattern matching that ensures high coding efficiency even when the dot angle is not 0 degree or 45 degrees as in a color paper telephotography system.
According to an aspect of the present invention, there is provided a coding method using pattern matching comprises the steps of: separating an image area from the image data; converting a dot angle of the image data in the image area to a specific angle; finding a dot frequency (interval) of the image data whose dot angle has been converted; and dividing the image data, whose dot angle has been converted, by the dot frequency or by an integral multiple of the dot frequency into a plurality of marks. This configuration allows even an image area to be coded through pattern matching and, at the same time, the dot frequency to be found easily, thus enabling marks to be generated effectively using pattern matching.
The specific angle for use in dot angle conversion is, for example, 0 degree or 45 degrees so that the dot frequency is easily found.
When the library contains the matching first mark, pixels positioned ahead of (beyond) a position of a processing target pixel may also be included in the reference pixels. The pixels positioned ahead of the position of the processing target pixel are future pixels that are in the scan direction. Therefore, the estimated result is more likely to be 100% or 0% and, as a result, the amount of code data is reduced.
When the library does not contain the matching first mark, the pixels of the mark that are in a predetermined template may be used as reference pixels.
A newly found mark may be added to the library. This c

Affiliated with

Also associated with

Rating

Coding method and coder using pattern matching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Coding method and coder using pattern matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coding method and coder using pattern matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3163301