Rotational correction and duplicate image identification by fourier transform correlation

• US 6,285,802 B1
• Filed: 04/08/1999
• Issued: 09/04/2001
• Est. Priority Date: 04/08/1999
• Status: Expired due to Term

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: Litton Systems Incorporated
• Inventors: Dennis, Phillip W., Dydyk, Robert B., Mills, Stuart A.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/289,082
• Time in Patent Office: 880 Days
• Field of Search: 382/280, 382/278, 382/289, 382/260, 382/290, 382/291, 382/292, 382/293, 382/294, 382/295, 382/296, 382/321, 356/399, 356/400, 358/497, 358/488
• US Class Current: 382/280
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

The invention corrects for rotational misalignment of images having a prominent periodic structure in a preferred direction, particularly imaged text pages. It preferably also finds the degree of correlation between different images. First the rotational misalignment of an imaged page is detected and corrected, bringing the page into alignment with an axis. The angle of rotation of the page is detected by performing a linear regression analysis on filtered, two-dimensional power spectral density distribution of the page, to find the angular orientation of the periodic components. In the preferred embodiment, two imaged pages are then cross-correlated, preferably by an optical correlator, to find the degree of correlation between the pages.

Claims

1. A method of determining the degree of similarity between imaged pages, comprising the steps of:

providing a reference and a target page, both in image form;

rotationally aligning at least one of said target and reference pages by (a) identifying periodic components in said at least one page by performing a two dimensional Fourier transform of said page to obtain a power spectral density distribution (b) finding a page axis which corresponds in orientation with the periodic components in said at least one page, by performing a linear regression analysis of said power spectral density distribution to compute an angle, relative to a reference axis, of a page axis which best fits said power spectral density distribution of said page, and (c) rotating said at least one page through said angle to align said at least one page with said reference axis;

cross-correlating in two dimensions said target and reference pages to produce a cross-correlation image; and

analyzing said cross-correlation image to determine the presence of a correlation peak which indicates similarity between said reference and said target pages.

2. The method of claim 1, wherein said step of finding a page axis further comprises:

modifying said power spectral density distribution by a filter function in the frequency domain prior to performing said linear regression analysis.

3. The method of claim 2, wherein said target and reference pages comprise text.

4. The method of claim 2, wherein said step of modifying said power spectral density distribution comprises filtering said power spectral density distribution with an angular wedge filter to attenuate power spectral density signals outside of an angular wedge.

5. The method of claim 4, wherein said step of modifying said power spectral density distribution further comprises filtering said power spectral density distribution with an annular frequency filter.

6. The method of claim 1, wherein said step of cross-correlating target and reference pages comprises the steps of:

inputting said target and said reference pages into an optical correlator which optically computes the cross-correlation of said pages, and

reading the output of said optical correlator to obtain the cross-correlation image.

7. The method of claim 1, wherein said linear regression analysis comprises calculating a variance and a covariance of said power spectral density distribution, and calculating said angle as the inverse tangent of the ratio of said covariance to said variance.

8. A method of rotationally aligning a skewed image to a defined reference axis, comprising the steps of:

providing a page, in a digitized image form; and

rotationally aligning said page by (a) identifying periodic components in said page by performing a two dimensional Fourier transform of said page to obtain a power spectral density distribution (b) finding a page axis which best corresponds in orientation with the periodic components in said page, by performing a linear regression analysis of said power spectral density distribution to compute an angle, relative to the reference axis, of a page axis which best fits said power spectral density distribution of said page, and (c) rotating said page through said angle to align said page with the reference axis.

9. The method of claim 8, wherein said page comprises text.

10. The method of claim 8, wherein said step of finding a page axis further comprises:

modifying said power spectral density distribution by a filter function in the frequency domain, prior to said step of performing a linear regression analysis.

11. The method of claim 10, wherein said step of modifying said power spectral density distribution comprises filtering said power spectral density distribution with an angular wedge filter to attenuate power spectral density signals outside of an angular wedge.

12. The method of claim 11, wherein said step of modifying said power spectral density distribution further comprises filtering said power spectral density distribution with an annular frequency filter.

13. The method of claim 8, wherein said linear regression analysis comprises calculating a variance and a covariance of said power spectral density distribution, and calculating said angle as the inverse tangent of the ratio of said covariance to said variance.