Method and apparatus for compressing binary data using pattern matching encoding

• US 6,016,361 A
• Filed: 11/05/1997
• Issued: 01/18/2000
• Est. Priority Date: 11/05/1996
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Hirao, Kouichirou, Hongu, Takahiro
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/964,633
• Time in Patent Office: 804 Days
• Field of Search: 382/258, 382/209, 382/217, 382/218, 382/221, 382/243, 358/470
• US Class Current: 382/209
• CPC Class Codes: H04N 1/4115 involving the recognition of specific patterns, e.g. by symbol matching

Abstract

In a method and an apparatus for pattern matching encoding disclosed a font bit map library is provided separately from a temporary updating library, in which temporary bit map pattern data capable of being updated according to a character pattern cut out from input binary image data is stored. In the font bit map library is stored font bit map library pattern data of an input character pattern font or a font designated by the user. A pattern matching process on the character pattern, is executed by comparing the character pattern with temporary bit map pattern data and font bit map pattern data. The character pattern is newly registered in the temporary updating library, when it is judged as being matched with only the temporary bit map pattern or as being matched with neither of the temporary bit map pattern or the font bit map pattern. It is possible to improve data compressibility without sacrifice in image quality.

Claims

1. A pattern matching encoding apparatus for encoding unit patterns extracted from input binary image data based on a result of matching of the unit patterns with library patterns, said pattern matching encoding apparatus comprising:

a first memory means for storing first library patterns capable of being updated according to the unit patterns;

a second memory means for storing second library patterns of a preliminarily designated font; and

a pattern matching means for executing a pattern matching process of matching the unit patterns by comparison of the unit patterns with the first library patterns and the second library patterns.

2. The pattern matching encoding apparatus according to claim 1, which further comprises:

updating control means for newly registering each of the unit patterns in the first memory means when the unit patterns are judged by the pattern matching means as being matched with the first library patterns although partially unmatched therewith.

3. The pattern matching encoding apparatus according to claim 2, wherein the updating control means newly registers each of the unit patterns in the first memory means when the unit pattern is judged by the pattern matching means as being matched with neither of the first and second library patterns.

4. The pattern matching encoding apparatus according to claim 3, wherein the pattern matching means executes the pattern matching process by comparing bit map data of each of the unit patterns with bit map data of the first library patterns and the second library patterns and judging the unit pattern as being matched when the ratio of the number of unmatched pixels in the bit map data is not greater than a predetermined ratio and as being unmatched when the ratio is greater than the predetermined ratio.

5. The pattern matching encoding apparatus according to claim 2, wherein the pattern matching means executes the pattern matching process by comparing bit map data of each of the unit patterns with bit map data of the first library patterns and the second library patterns and judging the unit pattern as being matched when the ratio of the number of unmatched pixels in the bit map data is not greater than a predetermined ratio and as being unmatched when the ratio is greater than the predetermined ratio.

6. The pattern matching encoding apparatus according to claim 1, wherein the pattern matching means executes the pattern matching process by comparing bit map data of each of the unit patterns with bit map data of the first library patterns and the second library patterns and judging the unit pattern as being matched when the ratio of the number of unmatched pixels in the bit map data is not greater than a predetermined ratio and as being unmatched when the ratio is greater than the predetermined ratio.

7. The pattern matching encoding apparatus according to claim 1, which further comprises:

a font storage means for storing a plurality of different fonts;

a font designating means for designating one of the plurality of fonts; and

a font developing means for developing the designated font into a font bit map to generate the second library patterns.

8. The pattern matching encoding apparatus according to claim 7, wherein the font designating means designates a font by detecting the font size and font type from the unit patterns.

9. The pattern matching encoding apparatus according to claim 7, wherein the font designating means includes an operating means for externally executing the font designation.

10. A method of pattern matching encoding of unit patterns extracted from input binary image data based on a result of matching of the unit patterns with library patterns, comprising the steps of:

storing first library patterns capable of being updated according to each of the unit patterns;

storing second library patterns of a preliminarily designated font;

comparing the unit pattern with the first library patterns and the second library patterns; and

newly registering the unit patterns as the first library patterns when the unit patterns are judged as being matched with only the first library patterns although partially unmatched therewith or when the unit patterns are judged as being matched with neither of the first and second library patterns.

11. A pattern matching encoding apparatus for encoding unit patterns extracted from input binary image data based on a result of matching of the unit patterns with library patterns, said pattern matching encoding apparatus comprising:

a first memory configured to store first library patterns capable of being updated according to the unit patterns;

a second memory configured to store second library patterns of a preliminarily designated font; and

a pattern matching circuit configured to execute a pattern matching process of matching the unit patterns by comparison of the unit patterns with the first library patterns and the second library patterns.

12. The pattern matching encoding apparatus according to claim 11, which further comprises:

an updating control circuit configured to newly register each of the unit patterns in the first memory when the unit patterns are judged by the pattern matching circuit as being matched with the first library patterns although partially unmatched therewith.

13. The pattern matching encoding apparatus according to claim 12, wherein the updating control circuit newly registers each of the unit patterns in the first memory when the unit pattern is judged by the pattern matching circuit as being matched with neither of the first and second library patterns.

14. The pattern matching encoding apparatus according to claim 13, wherein the pattern matching circuit executes the pattern matching process by comparing bit map data of each of the unit patterns with bit map data of the first library patterns and the second library patterns and judging the unit pattern as being matched when the ratio of the number of unmatched pixels in the bit map data is not greater than a predetermined ration and as being unmatched when the ratio is greater than the predetermined ratio.

15. The pattern matching encoding apparatus according to claim 12, wherein the pattern matching circuit executes the pattern matching process by comparing bit map data of each of the unit patterns with bit map data of the first library patterns and the second library patterns and judging the unit pattern as being matched when the ratio of the number of unmatched pixels in the bit map data is not greater than a predetermined ratio and as being unmatched when the ratio is greater than the predetermined ratio.

16. The pattern matching encoding apparatus according to claim 11, wherein the pattern matching circuit executes the pattern matching process by comparing bit map data of each of the unit patterns with bit map data of the first library patterns and the second library patterns and judging the unit pattern as being matched when the ratio of the number of unmatched pixels in the bit map data is not greater than a predetermined ration and as being unmatched when the ratio is greater than the predetermined ratio.

17. The pattern encoding apparatus according to claim 11, which further comprises:

a font storage configured to store a plurality of different fonts;

a font designating circuit configured to designate one of the plurality of fonts; and

a font developing circuit configured to develop the designated font into a font bit map to generate the second library patterns.

18. The pattern matching encoding apparatus according to claim 17, wherein the font designating circuit designates a font by detecting the font size and font type from the unit patterns.

19. The pattern matching encoding apparatus according to claim 17, wherein the font designating circuit includes an operating circuit configured to execute the font designation externally.