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.
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 xe2x80x9cLoseless and Lossy Compression of Text Images by Soft Pattern Matchingxe2x80x9d (issued on Jun. 30, 1995) extracts a small unit (hereinafter called xe2x80x9cmarkxe2x80x9d), 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 xe2x80x9cmatchxe2x80x9d 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 xe2x80x9c1xe2x80x9d and performs arithmetic coding for the estimated probability. In the following description, the template shown in FIG. 16 is called xe2x80x9cunmatched templatexe2x80x9d.
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.
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 xe2x80x9cfrequencyxe2x80x9d) 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 Moirxc3xa9. 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 configuration allows the library to grow as coding processing proceeds, ensuring a higher coding efficiency.
According to a second aspect of the present invention, there is provided a coder using pattern matching comprising: a character/image separation unit which extracts an image area from the image data; a dot angle conversion unit which converts a dot angle of the image data in the image area into a specific angle, the image area being extracted by the character/image separation unit; a dot frequency (interval) detecting unit which finds a dot frequency from the image data converted by the dot angle conversion unit; and a mark re-dividing unit which divides the image data, converted by the dot angle conversion unit, by a result found by the dot frequency detecting unit to generate marks for output to the match determination unit. This configuration allows even an image area to be coded through pattern matching and, at the same time, the dot frequency (interval) to be found easily, thus enabling marks to be generated effectively using pattern matching.
The mark re-dividing unit, for example, is configured to divide the image data by the dot frequency or by an integral multiple of the dot frequency, the image data being converted by the dot angle conversion unit.
The dot frequency detecting unit, for example, is configured to find correlation of the image data converted by the dot angle conversion unit.
The dot angle conversion unit may have a plurality of memories containing the image data converted by the dot angle conversion unit and converts the image data by writing the image data into, or reading the image data from, the memories in a direction inclined by a difference angle between the dot angle and the specific angle.
The coding unit may comprise a match template processing unit which, if the library contains the matching first mark, uses the pixels of a template of the first mark in the library and pixels of a predetermined template of the second mark in the input image data as reference pixels; an unmatch template processing unit which, if the library does not contain the matching first mark, uses pixels of a predetermined unmatch template of the second mark in the input image data as the reference pixels; and an arithmetic coding unit which estimates a probability of a pixel level of a processing target pixel using reference pixel values from the match template processing unit and the unmatch template processing unit and arithmetically codes the estimation value.