Pattern matching coding device using pattern matching and coding method therefor

• US 6,445,821 B1
• Filed: 04/20/1999
• Issued: 09/03/2002
• Est. Priority Date: 04/21/1998
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Arai, Mitsutoshi
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/294,366
• Time in Patent Office: 1,232 Days
• Field of Search: 382/135, 382/162, 382/165, 382/173-179, 382/209, 382/217-218, 382/309, 382/317-319, 382/321, 358/296, 358/302
• US Class Current: 382/209
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 1/41 Bandwidth or redundancy reduction by scanning H04N1/17 ; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 1/4115 involving the recognition of specific patterns, e.g. by symbol matching

Abstract

Image data is separated to character region and image region in a character/image separating portion (102). A mark is cut off from the character region by a mark cut-off portion (103). The image region is inputted to both the mark cut-off portion and an image period determining portion (104). The image period determining portion determines the period of grid image and dither image in the image region and notifies that period information to the mark cut-off portion. The mark cut-off portion cuts off the mark from an image in accordance with the period information. The mark cut-off by the mark cut-off portion is accumulated in an accumulating portion (106) for use as a library and it is determined whether or not there is a match library in old libraries by a match determining portion (105). If the match determining portion determines that there is a match library, it sends both the mark and match library to a coding portion (107). The coding portion carries out arithmetic coding by using a template for referring to the mark and reference match library at the same time.

Claims

1. A pattern matching coding device comprising:

a memory that accumulates inputted first image data;

a boundary tracing portion that fetches second image data of a necessary part from said memory and cuts off a mark;

a mark correlation check portion in which a first mark larger than a predetermined value is inputted from said boundary tracing portion and an observation window configured to observe a pixel on a straight line is moved in said first mark so as to search for a pixel having a high correlation;

a mark redividing portion that sends period information observed in said mark correlation check portion and redivides said first mark to generate a second mark having a size matching with the period;

an accumulative FIFO memory that accumulates the redivided second mark;

a match determining portion that refers to libraries accumulated in said accumulative FIFO memory and determines whether or not there is any library matching with said second mark or a third mark of normal size sent from said boundary tracing portion;

a match template to which, by determining that said library sent from said match determining portion matches with a fourth mark, said library is sent from said match determining portion together with said fourth mark as a match library;

an unmatch template to which only said fourth mark from said match determining portion is sent;

an arithmetic coder that outputs a template value of said unmatch template as an encoded code and outputs a template value from said match template as an encoded code.

2. 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 said memory by a boundary tracing portion and a mark is cut off;

a first mark larger than a predetermined value is inputted from said boundary tracing portion and an observation window for observing a pixel on a straight line is moved in said first mark by said boundary tracing portion so as to search for a pixel having a high correlation;

period information observed in said mark correlation check portion is sent and said first mark is redivided to generate a second mark having 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;

a plurality of said libraries accumulated in said accumulative FIFO memory are referred to and it is determined whether or not there is said library matching with said second mark or a third mark of normal size sent from said boundary tracing portion by a match determining portion;

said library sent from said match determining portion is determined to match with a fourth mark and sent from said match determining portion together with said fourth mark to a match template;

only said fourth mark from said match determining portion is sent to an unmatch template; and

a template value from said unmatch template is outputted as an encoded code and a template value from said match template is outputted as an encoded code by an arithmetic coder.

3. A coding method for a pattern matching coding device as claimed in claim 2, wherein if there are a plurality of the match libraries, a library found first is selected and if there is no match library, only said fourth mark from the match determining portion is sent to said unmatch template.

4. A coding method for a pattern matching coding device as claimed in claim 2, wherein when said boundary tracing portion fetches said second image data of a necessary part from said memory and cuts-off said mark, said cut off mark is smaller than a predetermined value, said mark is determined to be a character region or a region of a grid image having independent grids.

5. A pattern matching coding device, comprising:

a boundary tracer that receives stored image data, cuts off a mark and generates a first output or a second output in accordance with a size of said mark;

a mark correlator that comprises an observation window that generates a period in accordance with said first output;

a mark redivider that receives said second output, redivides said mark in accordance with information of said period, and stores said redivided mark;

a match determining device that determines whether a match exists between said redivided mark or said second output and an old library, and generates a match output in accordance with a result of said determination;

an accumulator that generates a new library in accordance with said redivided mark or said second output;

a template that receives said match output and generates a template value; and

a coder that performs an operation on said template value to generate an encoded output.

6. The device of claim 5, wherein said template receives only said second output or said redivided mark when no match exists with said old library and said second output or said redivided mark, and said template receives said second output or said redivided mark when a match exists between said old library and said second output or said second redivided mark.

7. The device of claim 5, wherein said first output is generated when said mark exceeds a size threshold, and said second output is generated when said mark is less than or equal to said size threshold.

8. The device of claim 5, further comprising an accumulative FIFO memory that stores said redivided mark.

9. The device of claim 5, wherein said period information comprises a distance between a counter corresponding to a maximum value of a plurality of observation pixels, and a reference pixel.

10. The device of claim 5, wherein said mark comprises a unit of a single character.

11. The device of claim 5, wherein said mark size comprises an integer multiple of said period.