Clustering

• US 7,376,275 B2
• Filed: 08/05/2005
• Issued: 05/20/2008
• Est. Priority Date: 04/25/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malvar, Henrique S., Simard, Patrice Y., Renshaw, Erin L.
• Primary Examiner(s): Mehta; Bhavesh M.
• Assistant Examiner(s): SCHAFFER, JONATHAN C
• Application Number:
  US11/198,562
• Publication Number:
  US 20050271281A1
• Time in Patent Office: 1,019 Days
• Field of Search: 382/218
• US Class Current: 382/218
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18 Extraction of features or characteristics of the image
• CPC Class Codes: G06V 30/19013 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching specially adapted for image segmentation G06T7/10; specially adapted for the analysis of motion G06T7/20; specially adapted for image alignment G06T7/30; specially adapted for the calculation of depth from stereo images G06T7/50; specially adapted for position determination G06T7/70
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition

Abstract

Systems and methods for performing clustering of a document image are disclosed. A property of an extracted mark from a document is compared to the properties of the existing clusters. If the property of the mark fails to match any of the properties of the existing clusters, the mark is added as a new cluster to the existing cluster. One property that can be utilized is x size and y size, which is the width and height, of the existing clusters. Another property that can be employed is ink size, which refers to the ratio of black pixels to total pixels in a cluster. Yet another property that can be utilized is a reduced mark or image, which is a pixel size reduced version the bitmap of the mark and/or cluster. The above properties can be employed to identify mismatches and reduce the number of bit by bit comparisons performed.

Claims

1. A clustering system comprising:

a mark extractor to extract a mark from a document, wherein a user has submitted the document to be encoded in a digitally compressed representation of the document;

a match component that compares at least one property of the mark to properties of existing clusters of marks so as to identify matching existing clusters, wherein the mark is added as a new cluster when no existing cluster of marks has a matching property to the mark;

a two dimensional table that stores the existing clusters; and

a match symbol component that compares the mark to the matching existing clusters to identify a matching cluster that most closely matches the mark.

2. The clustering system of claim 1, further comprising a library to store the existing clusters.

3. The system of claim 1, further comprising a table of match properties of the existing clusters.

4. The clustering system of claim 2, the library comprising a local library and a global library, the local library comprising existing clusters added from a current page of the document and the global library comprising existing clusters added from previous pages of the document.

5. The clustering system of claim 1, the mark extractor being operative to locate the mark and extract the mark from the document.

6. The clustering system of claim 1, the match properties comprising x sizes and y sizes for the existing clusters.

7. The clustering system of claim 1, the match properties comprising ink sizes for the existing clusters.

8. The clustering system of claim 1, the match properties comprising resized images for the existing clusters.

9. The clustering system of claim 6, the at least one property of the mark being x size and y size.

10. The clustering system of claim 7, the at least one property of the mark being ink size.

11. The clustering system of claim 8, the at least one property of the mark being a resized mark image.

12. The clustering system of claim 1, the match component operative to compute an acceptable range of properties.

13. The clustering system of claim 1, the match component further operative to add the mark as a new cluster on the mark mismatching the existing clusters.

14. The clustering system of claim 1, the match symbol component being further operative to add the mark to a set of matching marks of the most matching cluster.

15. The clustering system of claim 13, further comprising a library, the library being operative to store the existing clusters and to sort the existing clusters according to a frequency of occurrence for the existing clusters.

16. A photocopier employing the clustering system of claim 1.

17. A fax machine employing the clustering system of claim 1.

18. A digital camera employing the clustering system of claim 1.

19. A method of clustering comprising:

locating a mark within a document, wherein the document is to be encoded in a digitally compressed representation of the document;

comparing a first property of the mark with first properties of existing clusters to identify matching and mismatching existing clusters;

on a match of the first property, comparing a bitmap of the mark with bitmaps of the matching existing clusters to find a matched existing cluster of the matching existing clusters; and

on one of a mismatch of the first property and on a mismatch of the bitmap, adding the mark as a new cluster to the existing clusters.

20. A computer readable medium storing computer executable components to perform the following:

a component for locating a mark in a document, wherein the document is to be encoded in a digitally compressed representation of the document;

a component for comparing a first property of the mark with first properties of existing clusters to identify matching and mismatching existing clusters;

on a match of the first property, a component for comparing a bitmap of the mark with bitmaps of the matching existing clusters to find a most matched cluster of the matching existing clusters; and

on one of a mismatch of the first property and on a mismatch of the bitmap, a component to add the mark as a new cluster to the existing clusters.