Method for detecting alterations in printed document using image comparison analyses

• US 7,965,894 B2
• Filed: 06/30/2009
• Issued: 06/21/2011
• Est. Priority Date: 06/30/2009
• Status: Active Grant

• Current Assignee: Konica Minolta Laboratory U.S.A., Inc. (Konica Minolta Inc.)
• Original Assignee: Konica Minolta Systems Lab Incorporated (Konica Minolta Inc.)
• Inventors: Ming, Wei, Tian, Yibin
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): Koziol; Stephen R
• Application Number:
  US12/495,749
• Publication Number:
  US 20100329576A1
• Time in Patent Office: 721 Days
• Field of Search: 382/181, 382/218, 382/219
• US Class Current: 382/218
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20224 Image subtraction
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06V 20/80 Recognising image objects characterised by unique random patterns
• CPC Class Codes: G06V 30/155 Removing patterns interfering with the pattern to be recognised, such as ruled lines or underlines
• CPC Class Codes: G06V 30/186 by deriving mathematical or geometrical properties from the whole image

Abstract

A document alteration detection method compares a target image with an original image using a two-step process. In the first step, the original and target images are divided into connected image components and their centroids are obtained, and the centroids of the image components in the original and target images are compared. Each centroid in the target image that is not in the original image is deemed to represent an addition, and each centroid in the original image that is not in the target image is deemed to represent a deletion. In the second step, sub-images containing the image components corresponding to each pair of matching centroids in the original and target images are compared to detect any alterations.

Claims

1. A method implemented in a data processing apparatus for detecting alterations between an original image and a target image, the original and target images being binary bitmap images, the method comprising:

(a) extracting connected image components from the original and target images;

(b) calculating a centroid for each of the extracted connected image components in the original and target images;

(c) comparing all centroids of the original image and all centroids of the target image to determine whether each centroid of the original image has a matching centroid of the target image, and whether each centroid of the target image has a matching centroid of the original image;

(d) for each centroid of the original image that does not have a matching centroid in the target image, identifying the corresponding connected image component of the original image as a deleted connected image component;

(e) for each centroid of the target image that does not have a matching centroid in the original image, identifying the corresponding connected image component of the target image as an added connected image component;

(f) for each pair of matching centroids of the original and target images, comparing a pair of sub-images of the original and target images containing connected image components corresponding to the centroids to detect alterations; and

(g) generating an alteration map which indicates any deleted or added connected image components identified in steps (d) and (e) and any alterations detected in step (f).

2. The method of claim 1, wherein step (f) includes:

(f1) defining a sub-image of the original image containing the connected image component corresponding to the centroid of the original image;

(f2) defining a sub-image of the target image containing the connected image component corresponding to the centroid of the target image;

(f3) generating a difference map of the sub-image of the original image and the sub-image of the target image;

(f4) generating an edge map from the sub-image of the original image or the sub-image of the target image, the edge map representing an edge area of the connected image components contained in the sub-image; and

(f5) modifying the difference map generated in step (f3) by excluding any pixels of the difference map that fall within the edge area of the edge map.

3. The method of claim 2, wherein step (f) further includes, after steps (f1) and (f2) and before step (f3):

(f6) aligning the sub-image of the original image and the sub-image of the target image relative to each other.

4. The method of claim 2, wherein step (f) further includes, after step (f5):

(f7) de-noising the modified difference map obtained in step (f5).

5. The method of claim 1, wherein step (c) includes comparing the positions of the centroids in of the original image and the target image, wherein a centroid of the original image and a centroid of the target image are determined to be matching centroids if their positions are identical to within a predetermined positional tolerance.

6. The method of claim 1, wherein step (c) includes comparing a pattern of centroids of the original image with a pattern of centroids of the target image.

7. The method of claim 1, further comprising, before step (a):

(h) pre-processing the target image, including one or more steps of deskewing, resizing and image registration.

8. The method of claim 1, wherein the alteration map comprises a difference map.

9. The method of claim 1, wherein the alteration map comprises the original image or the target image and one or more markers indicating the alterations.

10. The method of claim 1, further comprising:

(i) printing the alteration map or displaying the alteration map on a display device.

11. A computer program product comprising a non-transitory computer readable storage medium having a computer readable program code embedded therein for controlling a data processing apparatus, the computer readable program code configured to cause the data processing apparatus to execute a process for detecting alterations between an original image and a target image, the original and target images being binary bitmap images, the process comprising:

(a) extracting connected image components from the original and target images;

(b) calculating a centroid for each of the extracted connected image components in the original and target images;

(c) comparing all centroids of the original image and all centroids of the target image to determine whether each centroid of the original image has a matching centroid of the target image, and whether each centroid of the target image has a matching centroid of the original image;

(d) for each centroid of the original image that does not have a matching centroid in the target image, identifying the corresponding connected image component of the original image as a deleted connected image component;

(e) for each centroid of the target image that does not have a matching centroid in the original image, identifying the corresponding connected image component of the target image as an added connected image component;

(f) for each pair of matching centroids of the original and target images, comparing a pair of sub-images of the original and target images containing connected image components corresponding to the centroids to detect alterations; and

(g) generating an alteration map which indicates any deleted or added connected image components identified in steps (d) and (e) and any alterations detected in step (f).

12. The computer program product of claim 11, wherein step (f) includes:

(f1) defining a sub-image of the original image containing the connected image component corresponding to the centroid of the original image;

(f2) defining a sub-image of the target image containing the connected image component corresponding to the centroid of the target image;

(f3) generating a difference map of the sub-image of the original image and the sub-image of the target image;

(f4) generating an edge map from the sub-image of the original image or the sub-image of the target image, the edge map representing an edge area of the connected image components contained in the sub-image; and

(f5) modifying the difference map generated in step (f3) by excluding any pixels of the difference map that fall within the edge area of the edge map.

13. The computer program product of claim 12, wherein step (f) further includes, after steps (f1) and (f2) and before step (f3):

(f6) aligning the sub-image of the original image and the sub-image of the target image relative to each other.

14. The computer program product of claim 13, wherein step (f) further includes, after step (f5):

(f7) de-noising the modified difference map obtained in step (f5).

15. The computer program product of claim 11, wherein step (c) includes comparing the positions of the centroids in of the original image and the target image, wherein a centroid of the original image and a centroid of the target image are determined to be matching centroids if their positions are identical to within a predetermined positional tolerance.

16. The computer program product of claim 11, wherein step (c) includes comparing a pattern of centroids of the original image with a pattern of centroids of the target image.

17. The computer program product of claim 11, further comprising, before step (a):

(h) pre-processing the target image, including one or more steps of deskewing, resizing and image registration.

18. The computer program product of claim 11, wherein the alteration map comprises a difference map.

19. The computer program product of claim 11, wherein the alteration map comprises the original image or the target image and one or more markers indicating the alterations.

20. The computer program product of claim 11, wherein the process further comprises:

(i) printing the alteration map or displaying the alteration map on a display device.