Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1998-09-02
2001-06-26
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Template matching
Reexamination Certificate
active
06252987
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to an image data coding system, and in particular to method and apparatus for coding an image including repeatedly usable patterns using a pattern matching technique.
2. Description of the Related Art
There have been proposed several image coding or compression techniques using pattern matching. For example, see “Lossless and Lossy Compression of Text Images by Soft Pattern Matching” by Paul G. Howard (“Coding of Still Pictures” ISO/IEC JTC 1/SC 29/WG1, Jun. 30, 1995). According to the conventional compression technique, an input image is segmented into marks or patterns, each of which is compared with the patterns stored in a library. If the current pattern matches one of the patterns of the library, then an index of the matching pattern is coded based on the bitmap and the size of the current pattern and its offset relative of another previously coded pattern.
In the case where pixels surrounding the current pattern are predicted in value (black or white), a differential value between the current pattern and each of reference patterns is calculated where the reference patterns are selected by pattern matching. The reference pattern having the minimum differential value is used for prediction.
However, there is a possibility that the differential value is affected by variations in matching position and thickness of a line of the current pattern. Such variations may cause an erroneous reference pattern to be selected and used for prediction, resulting in inaccurate pattern matching coding.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a pattern matching coding method and apparatus that can achieve data coding or compression with accuracy and reliability.
According to an aspect of the present invention, a library of reference patterns is stored for reference and the input pattern is matched with a reference pattern selected from the library to find a best reference pattern for the input pattern, wherein a pattern area of the input pattern is equal to that of the reference pattern. An error map of the input pattern is produced with respect to the best reference pattern and then it is determined whether an error pattern of the error map meets a predetermined criterion which provides a discrimination from an error caused by a pattern difference between the input pattern and the best reference pattern. If the error pattern meets the predetermined criterion, the error pattern is deleted from the input pattern to produce a modified input pattern. And the modified input pattern is coded referring to the best reference pattern.
The error pattern meets the predetermined criterion when a ratio of the error pattern to the pattern area is smaller than a predetermined threshold or when the error pattern consists of error pixels which are continuously connected in at least one single-pixel line extending in a direction.
The error pattern may be a minute error of the input pattern with respect to the best reference pattern, wherein the predetermined criterion is set so that the minute error is discriminated from an error caused by a pattern difference between the input pattern and the best reference pattern. The error pattern may be caused by variations in at least one of line thickness of the input pattern and position of the input pattern with respect to the best reference pattern when matching.
As described above, when the error pattern meets the predetermined criterion which provides a discrimination from an error caused by a pattern difference between the input pattern and the best reference pattern, the error pattern is deleted from the input pattern to produce a modified input pattern and then the modified input pattern is coded referring to the best reference pattern. Therefore, an error caused by variations in line thickness of the current pattern and/or variations in matching position can be eliminated, resulting in accurate and reliable image coding or compression.
REFERENCES:
patent: 4542378 (1985-09-01), Suganuma et al.
patent: 5278671 (1994-01-01), Takahashi et al.
patent: 5668897 (1997-09-01), Stolfo
patent: 5684895 (1997-11-01), Harrington
patent: 63-184479 (1988-07-01), None
Howard; “Lossless and Lossy Compression of Text Images by Soft Pattern Matchin”; AT&T Bell Laboratories; Jun. 30, 1995.
Hashimoto Tamae
Hirao Kou-ichirou
Azarian Seyed H.
Foley & Lardner
Johns Andrew W.
NEC Corporation
LandOfFree
Image data coding by 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 Image data coding by pattern matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image data coding by pattern matching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2535390