Method for comparing image sections to determine similarity therebetween

• US 5,539,841 A
• Filed: 04/27/1995
• Issued: 07/23/1996
• Est. Priority Date: 12/17/1993
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Jaquith, Eric W., Huttenlocher, Daniel P.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/430,106
• Time in Patent Office: 453 Days
• Field of Search: 382/257, 382/256, 382/218
• US Class Current: 382/218
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/19067 Matching configurations of points or features, e.g. constellation matching
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A method for comparing two image sections consisting of a plurality of image signals, or pixels, where each image section represents a token (e.g., character, symbol, glyph, string of components, or similar units of semantic understanding), in order to identify when similar tokens are present within the image sections. The invention further operates without the need for individually detecting and/or identifying the components making up the tokens. In one embodiment, the method relies upon the detection of connected components within words to first isolate individual word tokens and then applies a two stage process where dilated images of the tokens are compared with model representations of the tokens to determine the relative similarity therebetween.

Claims

1. A method performed by a computer for comparing at least two image sections having a plurality of image signals, each image section representing a token, to identify similar tokens, each token representing a unit of semantic understanding comprising the steps of:

(a) rasterizing, using source image derivation system, a document to produce an image section representing a token;

(b) storing image signals of an image section representing a first token in a first model memory;

(c) dilating the image signals representing the first token to produce a dilated representation of the first token and storing the detailed representation of the first token in first image memory;

(c) storing image signals of an image section representing a second token in second model memory;

(e) dilating the image signals of an image section representing the second token to produce a dilated representation of the second token and storing the dilated representation of the second token in a second image memory;

(f) comparing the image signals stored in the first model memory with the images signals stored in the second image memory to determine a first similarity metric;

(g) comparing the image signals store in the second model memory with the image signals stored in the first image memory to determine a second similarity metric; and

(h) indicating whether the first token is similar to the second token in response to the first and second similarity metrics.

2. The method of claim 1, wherein the steps of producing a dilated representation of the token comprises the steps of:

(a) copying the image signals represented in the model memory into the image memory; and

(b) dilating the image signals in the image memory by a predetermined dilation radius so as to produce a dilated representation of the image signals therein.

3. The method of claim 2, wherein the step of dilating the image signals further comprises the step of using a predetermined dilation radius not greater than 1.4 to produce the dilated representation of the image signals.

4. The method of claim 1, wherein the step of comparing the image signals stored in the model memory with the image signals stored in the image memory to determine a similarity metric includes the steps of:

(a) counting the total number of black image signals in the model memory;

(b) logically ANDing the image section stored in the model memory with the image section stored in the image memory;

(c) counting the number of black image signals which are present in the logically ANDed image sections to determine the number of matching black signals; and

(d) dividing the number of matching black signals by the total number of black image signals to determine the similarity metric.

5. The method of claim 1, wherein the step of indicating whether the first token is similar to the second token includes the step of identifying the first and second tokens as being similar whenever both the first similarity metric and the second similarity metric are greater than a predefined threshold.

6. The method of claim 1, further comprising the step of extracting image signals representing the first token from rasterized data defining an image.

7. The method of claim 6, further comprising the step of extracting image signals representing the second token from rasterized data defining the image.

8. The method of claim 6, wherein the step of extracting image signals representing the first token from rasterized data defining the image comprises the steps of:

(a) finding connected components within the image;

(b) identifying boundaries about each group of connected components within the image;

(c) locating text rows using the boundaries identified in step (b); and

(d) combining adjacent groups of connected components within the text rows located in step (c), based upon a relationship between the boundaries of adjacent groups, so as to segment the image by word tokens.

9. The method of claim 1, wherein the image signals representing a first token are identified as falling within a first bounding box and the image signals representing a second token are identified as falling within a second bounding box, further comprising the steps of:

(a) comparing a common dimension of the first and second bounding boxes; and

(b) determining that the first and second tokens may be similar if the common dimensions of the first and second bounding boxes are within a predefined tolerance, otherwise determining that the first and second tokens are dissimilar.

10. The method of claim 1, further comprising the step of extracting image signals representing the first token from rasterized data defining an image wherein the first token is defined as a string of symbols.

11. The method of claim 10, further comprising the step of extracting image signals representing the second token from rasterized data defining an image wherein the second token is defined as a string of symbols.

12. A method performed in a programmable computer for comparing at least two image sections, each image section consisting of a plurality of image signals, wherein a first image section represents a token from an unknown image object and a second image section represents a token from a known image object stored in a dictionary of images and where a token represents a unit of semantic understanding, to identify the unknown token as matching the token previously stored in the dictionary of images, comprising the steps of:

a) storing image signals of an image section representing an unknown token in a first model memory;

(b) dilating the image signals representing the unknown token to produce a dilated representation of the unknown token and storing the dilated representation of the unknown token in a first image memory;

(c) replicating image signals of an image section representing a known token stored in a dictionary of images to a second model memory;

(d) dilating the image signals representing the known token to produce a dilated representation of the second token and storing the dilated representation of the second token in a second image memory;

(e) comparing the image signals stored in the first model memory with the image signals stored in the first image memory to determine a second similarity metric;

(f) comparing the image signals stored in the second model memory with the image signals stored in the first image memory to determine a second similarity metric; and

(g) indicating whether the unknown token is similar to the known token in response to the first and second similarity metrics.

13. The method of claim 12, wherein the steps of producing a dilated representation of the token comprises the steps of:

(a) replicating the image signals represented in the model memory in the image memory; and

(b) dilating the image signals in the image memory by a predetermined dilation radius so as to produce a dilated representation of the image signals therein.

14. The method of claim 13, wherein the step of dilating the image signals further comprises the step of using a predetermined dilation radius not greater than 1.4 to produce the dilated representation of the image signals.

15. The method of claim 12, wherein the step of comparing the image signals stored in the model memory with the image signals stored in the image memory to determine a similarity metric includes the steps of:

(a) counting the total number of black image signals in the model memory;

(b) logically ANDing the image section stored in the model memory with the image section stored in the image memory;

(c) counting the number of black image signals which are present in the logically ANDed image section to determine the number of matching black signals; and

(d) dividing the number of matching black signals by the total number of black image signals to determine the similarity metric.

16. The method of claim 12, wherein the step of indicating whether the unknown token is similar to the known token includes the step of identifying the unknown and known tokens as being similar whenever both the first similarity metric and the second similarity metric are greater than a predefined threshold.

17. The method of claim 12, further comprising the step of extracting image signals representing the unknown token from rasterized data defining the image.

18. The method of claim 17, wherein the step of extracting image signals representing the unknown token from rasterized data defining the image comprises the steps of:

(a) finding connected components within the image;

(b) identifying boundaries about each group of connected components within the image;

(c) locating text rows using the boundaries identified in step (b); and

(d) combining adjacent groups of connected components within the text rows located in step (c), based upon a relationship between the boundaries of adjacent groups, so as to segment the image by tokens.

19. The method of claim 12, wherein the image signals representing an unknown token are identified as falling within a first bounding box and the image signals representing a known token are identified as falling within a second bounding box, further comprising the steps of:

(a) comparing a common dimension of the first and second bounding boxes; and

(b) determining that the tokens may be similar if the common dimensions of the first and second bounding boxes are within a predefined tolerance, otherwise determining that the first and known tokens are dissimilar.

20. The method of claim 12, further comprising the step of extracting image signals representing the unknown token from rasterized data defining an image, wherein the first token is defined as a string of symbols within the image.

21. The method of claim 20, further comprising the step of rasterizing image signals representing the known token as a function of a known string of symbols that are to be represented by the known token.