Image analysis – Image transformation or preprocessing – Fourier transform
Reexamination Certificate
1999-04-08
2001-09-04
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Fourier transform
C382S290000, C382S296000
Reexamination Certificate
active
06285802
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to image processing generally and more specifically to text recognition by Fourier transform correlation of imaged multi-line, paged text.
2. Description of the Related Art
Recognition of text in an imaged text database is required for multiple purposes. It is often required to locate a text page in a larger textual database or “book”; or it is sometimes useful to identify duplicate pages which can be deleted, to compress a database without loss of information.
Such a search is relatively easy in the context of encoded information, where characters and words are encoded as a sequence of digital bytes. However, imaged pages, in which the text pages are bitmaps or other graphic representations, are not so easily compared by a computer.
One method of comparing graphic images is cross-correlation, which is usually performed by first two-dimensionally Fourier transforming the images to be compared, then multiplying the pixels point by point, and finally inversely transforming the images back into a spatial representation to show correlation peaks. This well known method has been discussed, for example, in John C. Russ,
The Image Processing Handbook
, (CRC Press, 1992), pages 218-221. Advantages in speed are potentially obtained by performing such correlations optically, by an optical correlator. See for example, U.S. Pat. No. 5,311,359 to Lucas et al., and U.S. Pat. No. 5,148,496 to Anderson. Both of these patents disclose compact optical correlators capable of performing cross-correlation of digitized, pixellated images.
While correlation of images performs well with rotationally aligned images, pages of text are typically not well aligned rotationally. Text pages are usually digitized by feeding them through a digitizing “scanner”, or by imaging them through a digital camera or similar device. Imprecision in feeding and scanning hardware produces varying rotational misalignments in the digitized images. The resulting images are rotated (“skewed”) with respect to horizontal and vertical axes. Two otherwise duplicate images which differ by a slight rotation will not produce a strong correlation when compared. This degradation of correlation with skew angle is so pronounced that a misalignment in the range of only 1-2 degrees will significantly degrade correlation. Therefore, a method of rotationally correcting scanned text is a prerequisite to identification of scanned text by correlation.
One method of rotationally correcting text is disclosed in U.S. Pat. No. 5,235,651 to Nafarieh (1993). This method operates in the context of an optical character recognition (“OCR”) system, and limited in its ability to correct for rotational error. Specifically, the patented system only detects and corrects for inversion of the page, or rotation by 90 degrees (a sideways page). While these corrections may be useful in an OCR system, they are not adequate to allow rapid identification of duplicate imaged pages, which might have errors in rotation of (for example) five degrees or less.
Another method of rotationally correcting images is disclosed by Postl in his U.S. Pat. No. 4,723,297 (1988). His method involves scanning the image repeatedly at varying search angles, optimizing “directional criteria”, and then rotating the image based on the optimized directional criteria. The disclosed method only rotationally corrects skew in images during acquisition; it does not identify duplicate images. It requires many iterations to optimize, is computationally complex, and requires the predetermination of the “directional criteria.” Various other methods have been developed for detecting rotational or “skew” angle in text, but they have generally been mathematically very complex or computationally demanding. Efforts at improvement have focused on reducing the computational demands of the method. See for example, U.S. Pat. No. 5,583,956 to Aghajan, et al., disclosing a method using a subspace-based line detection algorithm, and the other methods cited therein.
SUMMARY OF THE INVENTION
The invention is a method for correcting for rotational misalignment of images and, in the preferred embodiment, for finding the degree of correlation between pages (or portions thereof) of images having a prominent periodic structure (such as multi-line text). The method includes two major steps.
In the first step the rotational misalignments of the pages are detected and corrected, bringing the pages into alignment with vertical and horizontal axes. The angles of rotation of the pages are detected by performing a linear regression analysis of filtered, two-dimensional Fourier transform images of the text pages, to find the angular orientation of the strongest periodic components of the text. The preferred embodiment includes a second step, in which two imaged pages are cross-correlated, preferably by an optical correlator, to find the degree of correlation between the pages.
The method can be reiterated for multiple pages of text, thereby comparing a page with each of the other pages to find duplicate pages of text.
REFERENCES:
patent: 3599147 (1971-08-01), Rogers et al.
patent: 3993976 (1976-11-01), Ginsburg
patent: 4338588 (1982-07-01), Chevillat et al.
patent: 4513441 (1985-04-01), Henshaw
patent: 4539651 (1985-09-01), Ludman
patent: 4558461 (1985-12-01), Schlang
patent: 4635278 (1987-01-01), Maloon et al.
patent: 4723297 (1988-02-01), Posti
patent: 4764973 (1988-08-01), O'Hair
patent: 4817176 (1989-03-01), Marshall et al.
patent: 4843631 (1989-06-01), Steinpichler et al.
patent: 4892408 (1990-01-01), Pernick et al.
patent: 5001766 (1991-03-01), Baird
patent: 5061063 (1991-10-01), Casasent
patent: 5148496 (1992-09-01), Anderson
patent: 5175775 (1992-12-01), Iwaki et al.
patent: 5216541 (1993-06-01), Takesue et al.
patent: 5235651 (1993-08-01), Nafarieh
patent: 5239595 (1993-08-01), Takemura et al.
patent: 5311359 (1994-05-01), Lucas et al.
patent: 5355420 (1994-10-01), Bloomberg et al.
patent: 5420441 (1995-05-01), Newman et al.
patent: 5513304 (1996-04-01), Spitz et al.
patent: 5528702 (1996-06-01), Mitsuoka et al.
patent: 5530772 (1996-06-01), Storey
patent: 5583956 (1996-12-01), Aghajan et al.
patent: 5619596 (1997-04-01), Iwaki et al.
patent: 5668898 (1997-09-01), Tatsuta
patent: 5764383 (1998-06-01), Saund et al.
patent: 5841907 (1998-11-01), Javidi et al.
Russ, The Image Processing Handbook, CRC Press, Inc., pp. 218-222, (1992).
Dennis Phillip W.
Dydyk Robert B.
Mills Stuart A.
Boudreau Leo
Koppel & Jacobs
Litton Systems Inc.
Patel Kanji
LandOfFree
Rotational correction and duplicate image identification by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rotational correction and duplicate image identification by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rotational correction and duplicate image identification by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2469081