Consolidation of equivalence classes of scanned symbols

• US 5,818,965 A
• Filed: 12/20/1995
• Issued: 10/06/1998
• Est. Priority Date: 12/20/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Davies, Daniel
• Primary Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/575,313
• Time in Patent Office: 1,021 Days
• Field of Search: 382/181, 382/182, 382/224, 382/225, 382/226, 382/227, 382/228, 382/229, 382/190, 382/235, 382/245, 395/601, 395/606, 395/614, 707/1
• US Class Current: 382/225
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding

Abstract

A method and apparatus for consolidation of equivalence classes of scanned symbols as may be used for image data compression. The present invention performs run-length symbol extraction and classifies symbols based on both horizontal and vertical run length information. An equivalence class is represented by an exemplar. Feature-based classification criteria for matching an exemplar is defined by a corresponding exemplar template. The feature-based classification criteria all use quantities that can be readily computed from the run endpoints. Reducing the number of equivalence classes is achieved through a process called equivalence class consolidation. Equivalence class consolidation utilizes the symbol classifier to identify matched exemplars indicating equivalence classes which may be merged. For a consolidated equivalence class, the exemplar matching the most symbols is selected as the representative for the class.

Claims

1. In a system for classifying symbols in image data, said image data representing an image, a method for merging equivalence classes to create a consolidated equivalence class, said method comprising the steps of:

a) classifying symbols extracted from image data to create a plurality of equivalence classes, each of said equivalence classes having an exemplar representing the equivalence class;

b) matching a first equivalence class exemplar to a second equivalence class exemplar, said matching step using endpoint ranges derived from one of run endpoints of the first equivalence class exemplar and run endpoints of the second equivalence class exemplar;

c) if said first equivalence class exemplar and said second equivalence class exemplar match, combining said first equivalence class and said second equivalence class exemplar to create a consolidated equivalence class;

d) repeating step b)-c) for each of said plurality of equivalence classes to create a plurality of consolidated equivalence classes; and

e) for each of said plurality of consolidated equivalence classes, selecting an exemplar from a set of exemplars used to create said consolidated equivalence class, to represent said consolidated equivalence class.

2. The method as recited in claim 1 wherein said step of matching a first equivalence class exemplar to a second equivalence class exemplar is further comprised of the steps of:

b1) determining if said second equivalence class is a size within an allowable range of said first equivalence class and said first equivalence class is a size within an allowable range of said second equivalence class;

b2) if not within said ranges, determining that said first equivalence class exemplar and said second equivalence class exemplar do not match;

b3) if within said range comparing symbol features of said second equivalence class exemplar to thresholds specified by said first equivalence class exemplar;

b4) if symbol features of said second equivalence class exemplar are not within thresholds specified by said first equivalence class exemplar, determining that said first equivalence class exemplar and said second equivalence class exemplar do not match;

b5) if symbol features of said second equivalence class exemplar are within thresholds specified by said first equivalence class exemplar, comparing run endpoints of said second class equivalence class exemplar with run endpoints of runs in said first equivalence class exemplar to determine if a match exists;

b6) if run endpoints do not match, determining that said first equivalence class exemplar and said second equivalence class exemplar do not match; and

b7) if run endpoints do match, determining that said first equivalence class exemplar and said second equivalence class exemplar do match.

3. The method as recited in claim 2 wherein said step of combining said first equivalence class and said second equivalence class exemplar to create a consolidated equivalence class further comprises the steps of:

c1) specifying an allowable range of said consolidated equivalence class to include limitations of both said first equivalence class and said second equivalence class; and

c2) specifying an actual range of said consolidated equivalence class to include exemplars of both said first equivalence class and said second equivalence class.

4. The method as recited in claim 3 wherein said first equivalence class is an existing consolidated equivalence class and said second equivalence class has a single exemplar.

5. The method as recited in claim 3 wherein said first equivalence class is an existing consolidated equivalence class and said second equivalence class is an existing consolidated equivalence class.

6. The method as recited in claim 3 wherein said first equivalence class has a single exemplar and said second equivalence class is an existing consolidated equivalence class.

7. The method as recited in claim 3 wherein said first equivalence class has a single exemplar and said second equivalence class has a single exemplar.

8. The method as recited in claim 3 wherein said step of classifying symbols extracted from image data to create a plurality of equivalence classes is performed using information derived from runs of extracted symbols.

9. The method as recited in claim 8 wherein said step of selecting an exemplar from a set of exemplars used to create said consolidated equivalence class, to represent said consolidated equivalence class is comprised of determining which of said exemplars matches the most extracted symbols.

10. The method as recited in claim 1 wherein step of classifying symbols extracted from image data to create a plurality of equivalence classes is further comprised of the step of generating an output data stream comprised of a dictionary of exemplars and exemplar identifier/position information, said output data stream for representing said image.

11. The method as recited in claim 10 further comprising the step of updating said dictionary to reflect consolidation of equivalence classes.

12. The method as recited in claim 11 wherein said output data stream is a compressed version of said image data.

13. The method as recited in claim 1 wherein said first equivalence class exemplar is compared in a first unshifted version.

14. The method as recited in claim 13 wherein said first equivalence class exemplar is compared in a second right shifted version.

15. The method as recited in claim 14 wherein said first equivalence class exemplar is compared in a third up shifted version.

17. The system as recited in claim 13 wherein said first criteria is based on features and runs of an extracted symbol and a single exemplar.

18. The system as recited in claim 14 wherein said second criteria is based on exemplars of equivalence classes being considered for consolidation.

19. The system as recited in claim 13 wherein said classification means further comprises means for determining whether endpoint positions of the runs of a first of the equivalence class exemplars are within corresponding endpoint ranges of legal endpoint locations of a second of the equivalence class exemplars.

16. A system for classifying symbols in image data comprising:

symbol extraction means for extracting a symbol from said image data;

classification means coupled to said symbol extraction means, said classification means for defining equivalence classes and classifying extracted symbols into a plurality of equivalence classes based on a first criteria, said classification means operating on endpoint ranges derived from run data of extracted symbols;

equivalence class consolidation means coupled to said classifications means said equivalence class consolidation means for reducing the number of equivalence classes defined by said classification means based on a second criteria; and

output generation means coupled to said equivalence class consolidation means, said output generation means for generating an output comprised of a plurality of pairs of positional information and exemplar identifiers, and a dictionary of a plurality of exemplars.

20. In a system for classifying symbols in image data, said image data representing an image, a method for merging equivalence classes to create a consolidated equivalence class, said method comprising the steps of:

a) classifying symbols extracted from image data to create a plurality of equivalence classes, each of said equivalence classes having an exemplar representing the equivalence class;

b) matching a first equivalence class exemplar to a second equivalence class exemplar, said matching step using endpoint ranges derived from one of run endpoints of the first equivalence class exemplar and run endpoints of the second equivalence class exemplar;

wherein said matching step further comprises the step of determining whether endpoint positions of the runs of one of the first and the second equivalence class exemplars are within corresponding endpoint ranges of legal endpoint locations of the other of the first and the second equivalence class exemplars;

c) if said first equivalence class exemplar and said second equivalence class exemplar match, combining said first equivalence class and said second equivalence class exemplar to create a consolidated equivalence class;

d) repeating step b)-c) for each of said plurality of equivalence classes to create a plurality of consolidated equivalence classes; and

e) for each of said plurality of consolidated equivalence classes, selecting an exemplar from a set of exemplars used to create said consolidated equivalence class, to represent said consolidated equivalence class.