Method and apparatus for three-dimensional object segmentation

• US 6,701,005 B1
• Filed: 04/29/2000
• Issued: 03/02/2004
• Est. Priority Date: 04/29/2000
• Status: Expired due to Fees

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Nichani, Sanjay
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US09/563,013
• Time in Patent Office: 1,403 Days
• Field of Search: 382/154, 382/190, 382/192, 382/193, 382/195, 382/199, 382/201, 382/203, 382/206, 382/291, 345/419, 345/420, 345/421, 345/422, 345/423, 345/424, 345/426, 345/425, 345/427, 356/12, 348/94, 348/95
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/33 using feature-based methods

Abstract

A three-dimensional (3-D) machine-vision involving a method and apparatus for performing segmentation of 3-D objects. Multiple stereo-related sets (left/right, top/left, top/right) of two-dimensional video pixel data are separately processed into sets of edges. Each stereo-related set is then pair-wise processed to convert pairs of sets of edge data into 3-D point data. Multiple sets of pair-wise 3-D data are then merged and used for obtaining 3-D features which are then clustered into discrete 3-D objects that can lie on any arbitrary plane.

Claims

1. A system for segmenting stereoscopic information into 3-D objects comprising:

an image acquisition device for acquiring a set of multiple images of a scene substantially simultaneously and having a predetermined geometric relationship with each other, and for presenting each of said multiple images as a 2-D array of pixels, each pixel having a corresponding light intensity value;

an edge processor for filtering each of said acquired multiple images to obtain multiple sets of features observed in each of said corresponding multiple images;

a matching unit for processing at least two pairs of sets of features to generate at least two result sets according to matching features between members of each pair of sets of features;

a merging unit selecting features from said at least two result sets according to a predetermined orientation threshold;

a 3-D computation processor for extracting 3-D features from said selected features;

a filter for removing data corresponding to undesired 3-D features according to predetermined location parameters; and

an object locator for clustering any remaining 3-D features into discrete 3-D objects, wherein said edge processor further comprises;

an edge detector using parabolic smoothing, followed by a non-integral sub-sampling, Sobel edge detection, true peak detection and chaining of edgelets to identify a set of edges in each image, and for characterizing each edge according to its xy location, its magnitude, and its orientation angle; and

a filter for discarding any edge that has a magnitude less than a predetermined threshold.

2. The system of claim 1 in which said matching unit further comprises:

a feature analyzer for finding a correspondence between features of two feature sets, said analyzer further including;

an epipolar constraint means for ignoring features that do not satisfy the epipolar constraint;

an initial strength of match (SOM) calculator for calculating an SOM for each prospective feature match between a first feature set when compared to each feature in a second feature set, resulting in a set of prospective feature matches, each one having a corresponding SOM;

a weak SOM remover for removing prospective feature matches having a low SOM;

an SOM adjuster for evaluating remaining prospective features with respect to said SOM of neighboring features on a chain of each remaining feature in said set of prospective feature match, and

a selector for designating the prospective feature matches having the highest SOM as a match.

3. A system for segmenting stereoscopic information into 3-D objects comprising:

an image acquisition device for acquiring a set of multiple images of a scene substantially simultaneously and having a predetermined geometric relationship with each other, and for presenting each of said multiple images as a 2-D array of pixels, each pixel having a corresponding light intensity value;

an edge processor for filtering each of said acquired multiple images to obtain multiple sets of features observed in each of said corresponding multiple images;

a matching unit for processing at least two pairs of sets of features to generate at least two result sets according to matching features between members of each pair of sets of features,

a merging unit for selecting features from said at least two result sets according to a predetermined vertical orientation threshold;

a 3-D computation processor for extracting 3-D features from said selected features;

a filter for removing data corresponding to undesired 3-D features according to predetermined location parameters, wherein said filter comprises

a mapper for converting all 3-D points of said extracted 3-D features into a coordinate system related to a horizontal plane; and

a screening processor for eliminating 3-D points that exceed application-specific thresholds for relative range from said image acquisition device, lateral offset, and height above said horizontal plane, including elimination of 3-D points less than a predetermined height above said plane;

wherein said image acquisition device is a trinocular image acquisition device and whereby 3-D points that do not correspond to objects of interest, and 3-D points corresponding to shadows on said plane are eliminated from further segmentation; and

an object locator for clustering any remaining 3-D features into discrete 3-D objects.

4. A system for segmenting stereoscopic information into 3-D objects comprising:

an image acquisition device for acquiring a set of multiple images of a scene substantially simultaneously and having a predetermined geometric relationship with each other, and for presenting each of said multiple images as a 2-D array of pixels, each pixel having a corresponding light intensity value;

an edge processor for filtering each of said acquired multiple images to obtain multiple sets of features observed in each of said corresponding multiple images;

a matching unit for processing at least two pairs of sets of features to generate at least two result sets according to matching features between members of each pair of sets of features,

a merging unit for selecting features from said at least two result sets according to a predetermined vertical orientation threshold;

a 3-D computation processor for extracting 3-D features from said selected features;

a filter for removing data corresponding to undesired 3-D features according to predetermined location parameters; and

an object locator for clustering any remaining 3-D features into discrete 3-D objects wherein said object locator comprises a segmenter for organizing chains of features into contiguous segments according to abrupt changes in a range dimension z between successive points on a chain, a merging process for merging said contiguous segments into objects according to their overlap in range or in lateral distance and an output for designating separated objects in which a lateral separation exceeds a predetermined threshold.