Document matching and annotation lifting

• US 20030048949A1
• Filed: 09/10/2001
• Published: 03/13/2003
• Est. Priority Date: 09/10/2001
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Goldberg, David, Ye, Ming, Bern, Marshall W.
• Granted Patent: US 6,968,085 B2
• Time in Patent Office: Days
• US Class Current: 382/218
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques
• CPC Class Codes: G06V 30/1904 involving a deformation of the sample or reference pattern; Elastic matching

Abstract

A method for matching an original document image with a copy image is disclosed. The original document image is defined as an ensemble of blocks, each of the blocks having neighboring blocks. A mask is formed for each of the blocks by dilating foreground pixels included in the block. A best match is searched in the copy image, for each of the blocks, using a search window, by correlating pixels in the mask with pixels in a corresponding portion in the copy image. Each of the best matches has a matching score. Each of the blocks is indicated as “unmatched” when the corresponding matching score is less than a matching threshold. A displacement vector is computed for each of the matched blocks.

Claims

1. A method for matching an original document image with a copy image, the method comprising the operations of:

(a) defining the original document image as an ensemble of blocks, each of the blocks having neighboring blocks;

(b) forming a mask for each of the blocks by dilating foreground pixels included in the block;

(c) searching for a best match in the copy image, for each of the blocks, using a first search window, by correlating pixels in the mask with pixels in a corresponding portion in the copy image, each of the best matches having a matching score;

(d) indicating each of the blocks as “

unmatched”

when the corresponding matching score is less than a matching threshold; and

(e) computing a displacement vector for each of the matched blocks.

2. The method of claim 1 further comprising the operation of:

(f) binarizing a gray-level copy using a first binarization threshold to produce the copy image.

3. The method of claim 2 further comprising the operations of:

(g) computing a second binarization threshold based on the matched blocks;

(h) binarizing the gray-level copy using the second binarization threshold to produce a second binary copy;

(i) assigning to each of the unmatched blocks a displacement vector based on an average of respective displacement vectors of the neighboring blocks of said unmatched block;

(j) searching for a new best match in the second binary copy, for each of the blocks, using a second search window, by correlating pixels in the mask with pixels in a corresponding portion in the second binary copy, each of the new best matches having a new matching score;

(k) indicating each of the blocks as “

unmatched”

when the corresponding new matching score is less than a matching threshold; and

(l) computing a new displacement vector for each of the new matched blocks.

4. The method of claim 3 further comprising the operation of:

(m) repeating operations (i) through (l) until all the blocks are matched.

5. The method of claim 3 wherein the second search window is smaller than the first search window.

6. The method of claim 1 wherein the blocks are overlapping.

7. The method of claim 1 wherein operation (c) is performed via a hierarchical search procedure.

8. The method of claim 1 further comprising the operations of:

shifting each of the blocks by the respective displacement vector;

stitching the shifted blocks together to produce a registered original.

9. The method of claim 1 wherein the original document image and the copy image are in gray-level form.

10. The method of claim 1 wherein the original document image and the copy image are in binary form.

11. The method of claim 1 wherein the original document image is in binary form and the copy image is in gray-level form.

12. A method for searching for a best match of a block of a document image, the best match being in a copy image, the method comprising the operations of:

(a) defining a search window;

(b) defining a first box centered within the search window, the first box being smaller than the search window;

(c) computing matching scores for matches located at points located within the first box;

(d) designating the point having the highest matching score as the best match;

(e) defining a second box centered around the best match, the second box being smaller than the first box; and

(f) repeating operation (c) and (d) with the second box replacing the first box.

13. The method of claim 12 wherein the points in operation (c) are the corners, side midpoints and center of the first box.

14. The method of claim 12 further comprising the operation of:

(g) repeating operations (e) and (f) until the points are adjacent to each other.

15. The method of claim 12 further comprising the operations of:

(h) defining a second search window around the best match if the best match is located at a boundary of the first search window; and

(i) repeating operations (a) through (f).

16. A method for producing an annotation image from a copy image and a registered original document image, the method comprising the operations of:

(a) forming a first mask by dilating foreground pixels in the registered original document image;

(b) forming a first annotation image by using portion of the copy image that lies outside the first mask;

(c) forming a second mask by dilating the first mask;

(d) defining each of connected components located on the first annotation image in the space between the first mask and the second mask as a broken stroke end; and

(e) connecting each of the broken stroke ends to at least one other broken stroke end, the other broken stroke end being chosen in accordance with a line tracing protocol.

17. The method of claim 16 wherein operation (e) comprises the operation of allowing a broken stroke end to be connected to more than one other broken stroke end when said broken stroke end is itself a connected component in the first annotation image.

18. The method of claim 16 wherein operation (e) comprises the operations of:

(1) forming a list of candidate connections for a broken stroke end;

(2) computing a connection score for each of the candidate connections; and

(3) selecting the candidate connection having the highest connection score.

19. The method of claim 18 wherein, in operation (2), the connection score is based on consistency, smoothness and proximity measures.

20. The method of claim 18 wherein, in operation (2), the connection score is computed as cs/p where c represents the consistency measure, s represents the smoothness measure and p represents the proximity measure.

21. A system for matching an original document image with a copy image, the system comprising:

(a) a partition module for defining the original document image as an ensemble of blocks, each of the blocks including foreground pixels;

(b) a mask forming module for forming a mask for each of the blocks by dilating the foreground pixels included in the block;

(c) a search module for searching for a best match in the copy image, for each of the blocks, by correlating pixels in the mask with pixels in a corresponding portion in the copy image, the search module assigning to each of the best matches a matching score, and indicating each of the blocks as “

unmatched”

when the corresponding matching score is less than a matching threshold; and

(d) a displacement computing module for computing a displacement vector for each of the matched blocks.

22. The system of claim 21 wherein the partition module defines the blocks such that the blocks are overlapping.

23. The system of claim 21 wherein the search module uses a hierarchical search procedure.

24. The system of claim 21 further comprising:

a registration module shifting each of the blocks by the respective displacement vector and stitching the shifted blocks together to produce a registered original.

25. A system for producing an annotation image from a copy image and a registered original document image, the system comprising:

(a) an initial annotation image module, the initial annotation image module forming a first mask by dilating foreground pixels in the registered original document image, forming a first annotation image by using portion of the copy image that lies outside the first mask, forming a second mask by dilating the first mask, and defining each of connected components located on the first annotation image in the space between the first mask and the second mask as a broken stroke end; and

(b) a broken stroke repair module connecting each of the broken stroke ends to at least one other broken stroke end, the other broken stroke end being chosen in accordance with a line tracing protocol.

26. The system of claim 25 wherein the broken stroke repair module allows a broken stroke end to be connected to more than one other broken stroke end when said broken stroke end is itself a connected component in the first annotation image.

27. The system of claim 25 wherein the broken stroke repair module comprises:

(1) a connection module for forming a list of candidate connections for a broken stroke end;

(2) a score computing module for computing a connection score for each of the candidate connections; and

(3) a selecting module for selecting the candidate connection having the highest connection score.