Image analysis – Pattern recognition
Reexamination Certificate
1998-03-18
2001-02-06
Tran, Phuoc (Department: 2721)
Image analysis
Pattern recognition
C382S173000, C382S177000, C382S218000, C382S227000, C358S461000
Reexamination Certificate
active
06185330
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to encoding/decoding of binary still images, and in particular, to a pattern matching encoding device for encoding binary still images, a pattern matching decoding device for decoding the encoded binary still images, and record mediums storing programs for pattern matching encoding and pattern matching decoding.
DESCRIPTION OF THE PRIOR ART
In pattern matching encoding (i.e. encoding of binary still images using pattern matching), an image to be encoded is segmented first into a plurality of groups of contiguous black pixels or into patterns corresponding to letters, numbers, symbols, etc., and pattern matching process is executed to each of the segmented pattern. Subsequently, encoding of the segmented patterns is executed by means of arithmetic coding according to the result of the pattern matching, in which bitmap information of the pattern itself along with information indicating the position and the size of the pattern is encoded.
In the arithmetic coding, pixels in the vicinity of a current or object pixel is utilized as reference pixels for predicting black/white of the current pixel, in which the hitting ratio of the prediction can be raised by utilizing a matched pattern as the reference pixels. As a result, encoding with high compression rate can be realized by the pattern matching encoding. The high compression rate encoding is usable for data transmission between facsimile machines etc.
FIG. 1
is a flow chart showing a conventional pattern matching encoding method which is disclosed in U.S. Pat. No. 5,303,313. In the method of
FIG. 1
, a plurality of patterns are extracted from an input image as input patterns (the ‘symbols’ in FIG.
1
), in which every connected region of black pixels is extracted as an input pattern (steps U
1
, U
2
, U
3
). Each input pattern is matched against library patterns (the ‘templates’ in
FIG. 1
) (step U
4
). Here, the library composed of library patterns (i.e. templates) is generated from scratch as new input patterns are extracted. Therefore, each input pattern is matched against library patterns which have been created in the library so far. The input pattern is added to a matching template group if matching one exists in the library. If the input pattern matches none of the library patterns, the input pattern forms a new template group and serves as the library pattern (i.e. template) in that group so that later input patterns can be matched against it (step U
5
). In the encoding process, an input pattern which matched a library pattern in the library is encoded using the matched library pattern as a reference pattern (step U
6
, U
7
).
As described above, in the conventional pattern matching encoding, input patterns extracted from the input image are encoded by referring to the matched library pattern in the library. In the case where no matching library pattern is found for an input pattern, the input pattern is added to the library and is used for reference in the subsequent pattern matching encoding. Therefore, optimization of the library proceeds as the pattern matching encoding using the library is repeated. Conversely, a library with which few pattern matching encoding have been executed has not been optimized enough.
If the optimization of the library is insufficient, the number of library patterns which can be matched against the input pattern is small, and thus similarity between patterns is low and the matching rate is necessitated to be low. Consequently, the optimal library pattern to be referred to in the arithmetic coding can not be obtained, and hit rate of the pixel prediction remains low, and thus compression rate of the input pattern can not be increased.
The problem becomes critical as variety of input patterns increases. For example, when the input image is an English document, variety of characters (i.e. input patterns) to be processed is relatively low and the number of necessary library patterns can be relatively small, and thus the library tends to be easily optimized.
However, in the case where the input image is a Japanese document for example, a library storing library patterns for ‘kanji’ (Chinese characters with a large variety) as well as ‘hiragana’ (rounded Japanese alphabets) and ‘katakana’ (angular Japanese alphabets) has to be constructed to be usable.
In such cases, the optimization of the library takes longer, and thus the compression rate of the input patterns can not be increased rapidly.
SUMMARY OF THE INVENTION
It is therefore the primary object of the present invention to provide a pattern matching encoding device for encoding binary still images, by which the library storing the library patterns can be optimized faster with a smaller number of execution of the pattern matching encoding, thereby compression rate of the input patterns by encoding can be increased faster without needing a large number of the execution.
Another object of the present invention is to provide a computer-readable record medium storing a pattern matching encoding program for encoding binary still images, by which the library storing the library patterns can be optimized faster with a smaller number of execution of the pattern matching encoding, thereby compression rate of the input patterns by encoding can be increased faster without needing a large number of the execution.
Another object of the present invention is to provide a pattern matching decoding device which can decode the encoded binary still images which have been encoded by the pattern matching encoding device or by the computer operating according to the program stored in the computer-readable record medium.
Another object of the present invention is to provide a computer-readable record medium storing a pattern matching decoding program by which the encoded binary still images can be decoded.
In accordance with a first aspect of the present invention, there is provided a pattern matching encoding device for executing pattern matching encoding of binary still images in which each input pattern extracted from the input image is matched against library patterns which have been registered in the library so far and the input pattern is encoded using a matched library pattern as a reference pattern if the matched library pattern is found, comprising a library pattern selection means, a pattern segmentation means, a matching means, a pattern combination means, and an encoding means. The library pattern selection means selects library patterns which can be matched against the input pattern, from the library patterns which have been registered in the library so far. The pattern segmentation means segments each of the library patterns selected by the library pattern selection means and the input pattern into two or more parts and thereby generates segmented library patterns and segmented input patterns. The matching means matches each of the segmented input patterns against corresponding segmented library patterns. The pattern combination means generates a new library pattern by combining the segmented library patterns each of which has matched one of the segmented input patterns in the matching executed by the matching means. And the encoding means regards the new library pattern as the matched library pattern and encodes the input pattern using the new library pattern as the reference pattern.
In accordance with a second aspect of the present invention, in the first aspect, the pattern segmentation means segments each of the library patterns selected by the library pattern selection means and the input pattern into two parts.
In accordance with a third aspect of the present invention, in the second aspect, the pattern segmentation means segments each pattern into a ¼ left-hand part and a ¾ right-hand part.
In accordance with a fourth aspect of the present invention, in the first aspect, the input pattern is registered as a library pattern in the library.
In accordance with a fifth aspect of the present invention, in the first aspect, the new library pattern generated by the pattern c
Mariam Daniel G.
McGinn & Gibb PLLC
NEC Corporation
Tran Phuoc
LandOfFree
Device and record medium for 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 Device and record medium for pattern matching..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and record medium for pattern matching... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606954