Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-04-20
2002-09-03
Couso, Jose L. (Department: 2721)
Image analysis
Pattern recognition
Template matching
C382S176000, C382S232000
Reexamination Certificate
active
06445821
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a pattern matching coding device using pattern matching and a coding method therefor, and more particularly to a pattern matching coding device for coding by extracting a mark from an image region and a character region and a coding method therefor.
2. Description of the Related Art
As a document on the conventional art, ISO/IEC JTC 1/SC 29/WGI N205 Lossless and Lossy Compression of Test Images by Soft Pattern Matching, pages 1-29 (issued on Jun. 30, 1995) by Paul G. Howard (AT & T Bell Labs) is accessible.
The above-mentioned document states a coding method which is effective for image data including mainly binary character and image and employs a pattern matching coding system. According to this conventional pattern matching coding method, characters are extracted from an image in a small unit such as a unit of a single character (hereinafter referred to as mark) and that mark is compared with a plurality of marks accumulated preliminarily (hereinafter referred to as library).
If there is a mark equivalent to an extracted mark in a library, when the extracted mark is coded, also that match mark in the library is referred to as a part of a coding template at the same time, thereby making it possible to achieve coding.
However, such a method of the conventional art has a problem that since only the character region is an object for processing and a conventional coding method is applied for the image region, compression rate is not improved.
Further, according to the conventional method, since different coding portions need to be provided for the character region and image region, there is a problem that the circuit size is enlarged.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a pattern matching coding device in which a mark is extracted also from the image region and subjected to the same processing as the character region, thereby eliminating the necessity of a coding portion dedicated for the image region, so that the circuit size can be reduced.
Further, another object of the present invention is to provide a pattern matching coding device in which when the mark is cut off from the image region, a periodicity of the object image is recognized and a region of a size matching with that period is cut off from the image as a mark, thereby making it possible to achieve a high compression rate.
According to the present invention, there is obtained a pattern matching coding device comprising: a character/image separating portion for separating an inputted image data to a character region and an image region; a mark cut-off portion for cutting off a mark from the character region; an image period determining portion for determining a period of a grid image and a dither image the image region and notifying the period information to the mark cut-off portion, a match determining portion for determining whether or not there is a match library in old libraries; an accumulating portion for accumulating the mark cut off by the mark cut-off portion and using it as a library; and a coding portion for carrying out arithmetic coding using a template for referring to the mark cut off by the mark cut-off portion and reference match library accumulated in the accumulating portion at the same time.
Further, according to the present invention, there is obtained a pattern matching coding device comprising: a memory for accumulating inputted first image data; a boundary tracing portion for fetching second image data of a necessary part from the memory and cutting off a mark; a mark correlation check portion in which a first mark larger than a predetermined value is inputted from the boundary tracing portion and an observation window for observing a pixel on a straight line is moved in the first mark so as to search for a pixel having a high correlation; a mark redividing portion for sending period information observed in the mark correlation check portion and redividing the first mark to a size matching with the period; an accumulative FIFO memory for accumulating the redivided second mark; a match determining portion for referring to libraries accumulated in the accumulative FIFO memory and determining whether or not there is any library matching with the second mark or a third mark of normal size sent from the boundary tracing portion; a match template to which, by determining that the library sent from the match determining portion is matching with a fourth mark and sent from the match determining portion with the fourth mark, it is sent from the match determining portion together with the fourth mark as a match library; an unmatch template to which only the fourth mark from the match determining portion is sent; and an arithmetic coder for outputting a template value of the unmatch template as an encoded code and outputting a template value from the match template as an encoded code.
Still further, according to the present invention, there is obtained a coding method for a pattern matching coding device, wherein image data is separated to character region and image region by a character/image separating portion; a mark is cut off from the character region by a mark cut-off portion; the image region is inputted to both the mark cut-off portion and image period determining portion; the image period determining portion determines the period of grid image and dither image in the image region; the period information is notified to the mark cutoff portion; the cut-off mark is accumulated in an accumulating portion for use as a library and used for the match determining portion to determine whether or not there is a match library in old libraries and if there is a match library, both the mark and the match library are sent to a coding portion; and the coding portion carries out arithmetic coding by using a template for referring to the mark and the match library at the same time.
Still further, according to the present invention, there is obtained a coding method for a pattern matching coding device, wherein inputted first image data is accumulated in a memory; second image data of a necessary part is fetched from the memory by a boundary tracing portion and a mark is cut off; a first mark larger than a predetermined value is inputted from the boundary tracing portion and an observation window for observing a pixel on a straight line is moved in the first mark by the boundary tracing portion so as to search for a pixel having a high correlation; period information observed in the mark correlation check portion is sent and the first mark is redivided to a size matching with the period by a mark redividing portion; the redivided second mark is accumulated in a library by an accumulative FIFO memory; libraries accumulated in the accumulative FIFO memory are referred to and it is determined whether or not there is the library matching with the second mark or a third mark of normal size sent from the boundary tracing portion by a match determining portion; the library sent from the match determining portion is determined to match with a fourth mark and sent from the match determining portion together with the fourth mark to a match template; only the fourth mark from the match determining portion is sent to an unmatch template; and a template value from the ummatch template is outputted as an encoded code and a template value from the match template is outputted as an encoded code by an arithmetic coder.
REFERENCES:
patent: 4410916 (1983-10-01), Pratt et al.
patent: 4606069 (1986-08-01), Johnsen
patent: 4922545 (1990-05-01), Endoh et al.
patent: 5828461 (1998-10-01), Kubo et al.
patent: 6016361 (2000-01-01), Hongu et al.
patent: 6052479 (2000-04-01), Hiraishi et al.
patent: 6058225 (2000-05-01), Mori et al.
patent: 6091844 (2000-07-01), Fuji et al.
patent: 6115494 (2000-09-01), Sonoda et al.
patent: 6148121 (2000-11-01), Fujimori et al.
patent: 6-38048 (1994-02-01), None
patent: 6-152982 (1994-05-01), None
Howard, Paul G., “Lossless and Lossy Compression of Text Images by Soft Pattern M
Couso Jose L.
Desire Gregory
NEC Corporation
Sughrue & Mion, PLLC
LandOfFree
Pattern matching coding device using pattern matching and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pattern matching coding device using pattern matching and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern matching coding device using pattern matching and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2886309