Method and system for detecting polygon boundaries of structures in images as particle tracks through fields of corners and pixel gradients

• US 8,081,798 B2
• Filed: 11/20/2008
• Issued: 12/20/2011
• Est. Priority Date: 11/20/2007
• Status: Expired due to Fees

• Current Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Original Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Inventors: Paglieroni, David W., Manay, Siddharth
• Primary Examiner(s): Lu, Tom Y
• Application Number:
  US12/275,177
• Publication Number:
  US 20090252373A1
• Time in Patent Office: 1,125 Days
• Field of Search: None
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 20/176 Urban or other man-made structures

Abstract

A stochastic method and system for detecting polygon structures in images, by detecting a set of best matching corners of predetermined acuteness α of a polygon model from a set of similarity scores based on GDM features of corners, and tracking polygon boundaries as particle tracks using a sequential Monte Carlo approach. The tracking involves initializing polygon boundary tracking by selecting pairs of corners from the set of best matching corners to define a first side of a corresponding polygon boundary; tracking all intermediate sides of the polygon boundaries using a particle filter, and terminating polygon boundary tracking by determining the last side of the tracked polygon boundaries to close the polygon boundaries. The particle tracks are then blended to determine polygon matches, which may be made available, such as to a user, for ranking and inspection.

Claims

1. A method in a computer system for detecting polygon boundaries of structures in an image, comprising:

receiving an image;

detecting in said image a set of polygon corners each substantially matching one of n corner models of an n-sided polygon model based on directions of gradients in pixel gray-values of said image;

initializing tracking of polygon boundaries by selecting pairs of corners from the set of detected polygon corners which match the first 0^th and last (n−

1)^th corners models of the n-sided polygon model, wherein each selected pair defines a first 0^th side of a corresponding one of the polygon boundaries;

using a particle filter performing Sequential Monte Carlo sampling to track intermediate sides of the polygon boundaries after the first 0^th side up to and including a penultimate (n−

2)^th side, wherein the particles used in the particle filter characterize the states of the polygon boundary sides, and observations used in the particle filter characterize the match similarity between the set of detected polygon corners at locations and orientations predicted by the polygon model;

terminating tracking of the polygon boundaries by determining the last (n−

1)^th sides thereof based on specified states of the sides of the polygon boundaries for the previous n−

1 sides; and

blending multiple particle tracks for the same polygon into a single boundary based on importance weights that reflect particle fitness, to produce an array of polygon matches detected in said image.

2. The method of claim 1,

further comprising ranking the blended particle tracks based on corner fitness contributions and edge fitness contributions in user-specified proportions.

3. The method of claim 1,

wherein the corner models are gradient direction corner models, and the step of detecting the set of polygon corners comprises:

for each of M corner model orientations per pixel in said image, determining n corner similarity values as a gradient direction matching (GDM) feature between the direction of the gradient in the pixel gray-value and the n gradient direction corner models; and

determining as polygon corners those pixels satisfying predetermined GDM feature thresholds.

4. The method of claim 2,

wherein the predetermined GDM feature thresholds include those pixels determined to be unambiguous local maxima above a threshold magnitude in a set of optimal GDM feature values.

5. The method of claim 1,

wherein in the initialization step, the selection of the pairs of corners are based on each of n cyclic shifts of the n-sided polygon model.

6. The method of claim 1,

further comprising providing the array of polygon matches for use by a user.

7. The method of claim 6,

wherein the array of polygon matches is graphically rendered for display.

8. A method in a computer system for detecting polygon boundaries of structures in an image, comprising:

computing a set of similarity values characterizing the degree of matching between an estimated gradient direction of each of M corner orientations of each pixel to a gradient direction model of a corner of predetermined acuteness α

of a polygon model;

determining a set of best matching corners from the set of similarity values by finding unambiguous local maxima of predetermined sufficient magnitude in the set of similarity values;

initializing tracking of polygon boundaries by selecting pairs of corners from the set of detected polygon corners which match the first 0^th and last (n−

1)^th corners models of the n-sided polygon model, wherein each selected pair defines a first 0^th side of a corresponding one of the polygon boundaries;

tracking intermediate sides of the polygon boundaries using a particle filter performing SMC sampling, including a penultimate (n−

2)^th side;

terminating polygon boundary tracking by determining the last (n−

1)^th side of the tracked polygon boundaries based on boundary values up to the (n−

1)^th side, to close the polygon boundaries; and

blending the polygon boundary tracks to produce polygon match data identifying polygon structures in the image.

9. A computer system for detecting polygon boundaries of structures in an image, comprising:

input means for receiving the image;

a first data processing module for detecting in said image a set of polygon corners each substantially matching one of n corner models of an n-sided polygon model based on directions of gradients in pixel gray-values of said image;

a second data processing module initializing tracking of polygon boundaries by selecting pairs of corners from the set of detected polygon corners which match the first 0^th and last (n−

1)^th corners models of the n-sided polygon model, wherein each selected pair defines a first 0^th side of a corresponding one of the polygon boundaries;

a third particle filtering module for performing Sequential Monte Carlo sampling to track intermediate sides of the polygon boundaries after the first 0^th side up to and including a penultimate (n−

2)^th side, wherein the particles used in the particle filter characterize the states of the polygon boundary sides, and observations used in the particle filter characterize the match similarity between the set of detected polygon corners at locations and orientations predicted by the polygon model;

a fourth data processing module for terminating tracking of the polygon boundaries by determining the last (n−

1)^th sides thereof based on specified states of the sides of the polygon boundaries for the previous n−

1 sides; and

a fifth data processing module for blending multiple particle tracks for the same polygon into a single boundary based on importance weights that reflect particle fitness, to produce an array of detected polygon matches;

output means for making the array of detected polygon matches available for use.