Subspace-based line detection

• US 5,418,892 A
• Filed: 01/12/1993
• Issued: 05/23/1995
• Est. Priority Date: 01/12/1993
• Status: Expired due to Fees

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Aghajan, Hamid K., Kailath, Thomas
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/003,255
• Time in Patent Office: 861 Days
• Field of Search: 395/128, 395/133, 395/141, 395/142, 395/143, 395/118, 395/157, 395/158, 395/443, 395/449, 395/456
• US Class Current: 345/418
• CPC Class Codes: G01S 3/74 Multi-channel systems specially adapted for direction-finding, i.e. having a single antenna system capable of giving simultaneous indications of the directions of different signals systems in which the directions of different signals are determined sequentially and displayed simultaneously G01S3/04, G01S3/14
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 2207/30256 Lane; Road marking
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/77 using statistical methods
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

A new signal processing method solves the problem of fitting multiple lines in a two-dimensional image. The Subspace-Based Line Detection (SLIDE) algorithm formulates the multi-line fitting problem in a special parameter estimation framework such that a signal structure similar to the sensor array processing signal representation is obtained. Any spectral estimation method can then be exploited to obtain estimates of the line parameters. In particular, subspace-based algorithms of sensor array processing (e.g., the ESPRIT technique) can be used to produce closed-form and high resolution estimates for line parameters. The signal representation employed in this formulation can be generalized to handle both problems of line fitting (in which a set of binary-valued discrete pixels is given) and of straight edge detection (in which one starts with a grey-scale image).

Claims

1. A method of estimating line parameters including angles and offsets of straight lines in a two-dimensional image comprising the steps of

a) producing an edge-enhanced image from a grey-scale image,

b) performing a constant-μ

propagation on the image to obtain a measurement vector z,

c) estimating the cisoidal components of said measurement vector z including the number of angles present, and

d) estimating the offsets of lines for each angle.

2. The method as defined by claim 1 wherein step c) includes

rearranging the measurement vector such that P snapshot vectors of size M are produced,

computing the same covariance matrix of said snapshots, and

performing eigendecomposition of said sample covariance matrix to estimate the number of angles present.

3. The method as defined by claim 1 wherein step d) includes using a least-squares minimization.

4. The method as defined by claim 1 wherein step d) includes projecting images along each detected angle and searching for peaks.

5. The method as defined by claim 1 wherein step d) includes applying a variable τ

propagation stage of a subspace-based line detection algorithm.