Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1999-11-24
2003-06-03
Couso, Von J. (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S291000
Reexamination Certificate
active
06574366
ABSTRACT:
FIELD OF THE INVENTION
This invention is generally related to electronic image recognition techniques and, more particularly, to an electronic image detection method wherein local edge information is utilized for detecting lines and curves.
BACKGROUND OF THE INVENTION
A fundamental problem in electronic image recognition is line detection, or more generally, curve detection. In many applications, we want to find lines or other simple curves in a complex image or document. In a pre-scan image lines might be detected to decide where the edges of a paper document are. Within a document text lines may be used to estimate the skew angle of the document. Also, line and other simple curve detection often serves as the first step for complex object detection, as the contour of a complex object can always be decomposed into simple curves.
One example application of line detection is currency detection. The ability to detect currency patterns in an image can be useful in color copier machines or scanners for the purpose of preventing counterfeiting. The challenge of incorporating such a method in current copier or scanning technology lies in the difficulty with detecting images in a rotation or shift invariant manner. Specifically, the pattern could be of any orientation and at any location of the image. The orientation and the location of the image can be relatively simple to estimate using the line detection techniques.
Examples of skew angle identification and correction can be found in the following patents:
U.S. Pat. No. 5,528,387 to Kelly et al., issued Jun. 18, 1996, which teaches electronic image registration in a scanner. In particular, the edge data of a document is detected and skew angle calculated. The image is then rotated based upon the skew angle and non-image areas are filled using an image generation feature.
U.S. Pat. No. 4,922,350 to Rombola et al., issued May 1, 1990, discloses a two-pass scanning apparatus for detecting the size and position of an original document on a scanner platen. Image signals captured on a first scan are employed to determine boundaries and a best-fit magnification so that the image may be fed to a recording sheet using image signals generated on a subsequent scanning pass.
U.S. Pat. No. 5,253,765 to Moorehead et al, issued Oct. 19, 1003, teaches a system for sorting randomly sized objects (e.g. mushrooms). Invariant moments are employed, utilizing the complete pixel information for all pixels within the border of a captured image, to extract information about the mushroom size and orientation.
U.S. Pat. No. 5,220,398 to Horn et al. teaches an analog VLSI microchip that uses moments to determine the position and orientation of an object in a scene.
In “Invariant Fitting of Planar Objects by Primitives,” published in 1996 IEEE Proceedings of ICPR '96, pp. 508-512 Voss et al, teach a method of pattern recognition using primitives such as triangles, rectangles, circles, ellipses, superquadratics, etc. The authors further describe a technique for describing the primitives using moments in a normalized manner; resulting in a decrease in the numerical effort.
In “Managing and Representing Image Workflow in Prepress Applications,” Technical Association of the Graphic Arts (TAGA) Vol. 1, 1995 Proceedings, pp. 373-385, Venable et al. teach the use of structured images to manage prepress workflow.
The Hough Transform, is probably the most important and most widely-used algorithm for curve detection. The Hough Transform utilizes global feature information (sets of points belonging to a given curve) efficiently. However, prior applications totally ignore local information. This disclosure proposes to improve the Hough Transform by exploiting local information within images and documents. For each detected point a local edge direction is first estimated. This can be done by many standard methods such as that described by A. Rosenfeld and A. C. Kak in an article entitled “Digital Picture Processing”, Academic Press, Inc., where a Sobel operator is used for gray images. The orientation of the estimated local edge controls the accumulation process in the Hough Transform. The disclosed method requires less computation and is more reliable in detection.
The counterfeit detection art includes methods that rely on point detection during recognition. As disclosed in U.S. Pat. No. 5,533,144 to Fan, entitled “Anti-counterfeit pattern detector and method”, an anti-counterfeit detector and method identifies whether a platen image portion to be photocopied contains one or several note patterns. With the 144 method, the detection is performed in a rotation and shift invariant manner. Specifically, the pattern can be of any orientation and at any location of the image and can be embedded in any complicated image background. The image to be tested is processed block by block. Each block is examined to see if it contains an “anchor point” by applying an edge detection and orientation estimation procedure. For a potential anchor point, a matching procedure is then performed against stored templates to decide whether the pre-selected monetary note patterns are valid once detected.
Other pattern detection methods are presented by the following patents:
U.S. Pat. No. 4,153,897 Yasuda, et. al. Issued May 8, 1979
U.S. Pat. No. 5,216,724 Suzuki, et. al. Issued Jun. 1, 1993
U.S. Pat. No. 5,291,243 Hecknam, et. al. Issued Mar. 1, 1994
Yasuda et al. discloses a pattern recognition system where similarities between unknown and standard patterns are identified. Similarities are detected at first in respective shifting conditions where the unknown and standard patterns are relatively shifted from each other over the first limited extent, including the condition without shift. The maximum value of these similarities is then detected. The similarities are further detected in respective shifting conditions where the unknown and standard patterns are relatively shifted from each other over the second extent larger than the first limited extent, when the shifting condition which gave the maximum value is that without relative shift.
Suzuki et al. discloses an apparatus for image reading or processing that can precisely identify a particular pattern, such as banknotes or securities. A detecting unit detects positional information of an original image and a discriminating unit extracts pattern data from a certain part of the original image to discriminate whether the original image is the predetermined image based on the similarity between the pattern data and the predetermined pattern.
Heckman et al. discloses a system for printing security documents which have copy detection or tamper resistance in plural colors with a single pass electronic printer. A validating signature has two intermixed color halftone patterns with halftone density gradients varying across the signature in opposite directions, but different from the background.
All of the references cited herein are incorporated by reference for their teachings.
SUMMARY OF THE INVENTION
In order to more reliably and efficiently detect lines and curves, an electronic image detection method is now disclosed wherein local edge information is utilized. A currency detection method and system based on the disclosed line detection method is also presented.
With the presented method, the local edge information is applied to improve the line detection; the orientation of the local edge controls the accumulation process in Hough Transform.
With the presented currency detection method, a detector is trained off-line with example images resulting in a template generated by recording a test pattern similar to an image pattern to be tested; anchor lines are identified within the template; the long lines are detected during the testing using the disclosed line detection method; the template is rotated and shifted before matching the template to the test pattern so that the anchor lines align with long lines detected within the test pattern; and the template and the test pattern are compared to determine whether there is a match.
The method ca
Couso Von J.
Dudley Mark Z.
Krishnan Aditya
Xerox Corporation
LandOfFree
Line and curve detection using local information does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Line and curve detection using local information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Line and curve detection using local information will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3140382