Line and curve detection using local information

• US 6,026,186 A
• Filed: 11/17/1997
• Issued: 02/15/2000
• Est. Priority Date: 11/17/1997
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Fan, Zhigang
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/972,203
• Time in Patent Office: 820 Days
• Field of Search: 382/202, 382/201, 382/203, 382/281, 382/217, 382/218
• US Class Current: 382/201
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

An image detection method is disclosed wherein local edge information within an image is utilized for accurately detecting lines and curves of the images. The method can more accurately determine the location and orientation of a pattern and thus provides more reliable image match for pattern detection. A detector is trained off-line with example images resulting in a stored template generated by recording a test pattern similar to a pattern to be tested; anchor lines are identified within said template. Long lines are detected in subsequent test patterns using the disclosed method. The template is rotated and shifted before matching it to the test pattern so that anchor lines align with long lines detected within the test pattern. The template and test pattern are then compared to determine whether there is a match. The system comprises a microprocessor is programmed to facilitate the training of a detector off-line with example images which are scanned into said system wherein a template is generated by recording an image pattern of said example images similar to a test pattern to be detected. The microprocessor identifies anchor lines within the template. It detects the long lines using the disclosed line detection method; rotates and shifts the template before matching it to the test pattern so that anchor lines align with lines which are detected within said test pattern; and compares the template to the test pattern to determine whether said anchor lines exist within said test pattern.

Claims

1. An image detection method using local edge information for detecting lines and curves comprising;

a) indexing a 2-D array by (θ

,b) so as to construct a line for each detected point P_i =(x_i,y_i) as;

space="preserve" listing-type="equation">b=k x.sub.i -y.sub.i

in a kb-plane wherein k=tan θ

, for φ

+Δ

<

θ

<

φ

-Δ

, φ

is the edge orientation and Δ

is a preset parameter;

b) lines corresponding to all of said each detected point P_i, and obtaining peaks at (θ

,b) corresponding to collinear sets of said each detected point P_i, and determining a position for said each detected point P_i through equations of corresponding lines;

wherein total computation for determining lines and curves during image detection is obtained by calculating;

space="preserve" listing-type="equation">b=k x.sub.i -y.sub.i

K times for each detected point, where K=Δ

/R, wherein R is the resolution for θ

estimation;

wherein θ

is a local edge estimated and Δ

is a parameter dependent on the accuracy of a local edge orientation estimation.

2. The method of claim 1 comprising a detector trained off-line with example images resulting in a template generated by recording a test pattern similar to a pattern to be tested;

anchor lines or curves identified within said template;

long lines detected using the method of claim 1;

said template is rotated and shifted before matching said template to said test pattern so that said anchor lines or curves align with long lines or curves detected within said test pattern; and

said template and said test pattern are compared to determine whether there is a match.