Method and apparatus for three-dimensional object segmentation

• US 7,680,323 B1
• Filed: 11/24/2003
• Issued: 03/16/2010
• Est. Priority Date: 04/29/2000
• Status: Active Grant

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Nichani, Sanjay
• Primary Examiner(s): Strege; John B
• Application Number:
  US10/720,801
• Time in Patent Office: 2,304 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/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 method for segmenting stereoscopic information into 3-D objects comprising the steps of:

acquiring a set of multiple images of a scene substantially simultaneously and having a predetermined geometric relationship with each other;

using a vision system to carry out the steps of;

filtering each of said acquired multiple images to obtain multiple sets of features observed in each of said corresponding multiple images;

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;

wherein the step of processing further includes the steps of;

matching features from a right image and a left image to form a set of horizontal disparities; and

matching features from a right image and a top image to form a set of vertical disparities, wherein said right and left images were obtained from image acquisition devices arranged along a horizontal line, and said right and top images were obtained from image acquisition devices arranged along a vertical line substantially perpendicular to said horizontal line;

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

extracting 3-D features from said selected features;

filtering said 3-D features according to location; and

clustering any remaining 3-D features into discrete 3-D objects.

2. The method of claim 1 in which said step of filtering each of said acquired multiple images further includes the steps of:

digitizing each image into a two-dimension grid of pixels, each pixel having a light intensity value;

evaluating said grid to identify areas in which said light intensity values of adjacent pixels indicate presence of an edge of an object;

processing each of said edges using parabolic smoothing, followed by a non-integral sub-sampling, Sobel edge detection, true peak detection and chaining of edgelets into edges;

characterizing each edge according to its xy location, its magnitude, and its orientation angle; and

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

3. The method of claim 1 in which each said step of matching further comprises the steps of:

for each feature in a first image, removing features in a second image that do not satisfy an epipolar constraint, calculating a strength of match (SOM) for each remaining feature in said second image, eliminating features from said second image whose SOM is less than a predetermined threshold, calculating a new SOM according to the SOM of neighboring features on a chain of each remaining feature in said second image, and designating the features having the strongest SOM as a match.

4. The method of claim 3 in which each said step of designating features as a match is repeated for a fixed number of iterations.

5. The method of claim 1 in which the step of selecting further comprises the steps of:

calculating a disparity vector for each feature of each of said result sets;

selecting features of a horizontal result set if said disparity vector is within a predetermined range of vertical orientation angles;

selecting features of a vertical result set if said disparity vector is outside of said predetermined range of vertical orientation angles; and

discarding features of each result set that were not selected.

6. The method of claim 5 in which said predetermined range of vertical orientation angles is approximately 45 degrees to 135 degrees and approximately 225 degrees to 315 degrees.

7. The method of claim 1 in which said step of extracting is implemented by calculating a set of 3-D points corresponding to said selected features.

8. The method of claim 1 in which said step of filtering said 3D features further comprises the steps of:

converting all 3-D points of said selected features into a coordinate system related to a plane; and

eliminating points that exceed application-specific thresholds for relative range, lateral offset, and distance from said plane;

whereby points that do not correspond to objects of interest are eliminated from further segmentation.

9. The method of claim 1 in which said step of clustering further comprises the steps of:

organizing chains of features according to changes in a range dimension between successive points on a chain;

merging said chains according to their overlap; and

identifying separated objects as a function of distance exceeding a predetermined threshold.

10. A method for segmenting stereoscopic information into 3-D objects comprising the steps of:

acquiring a left image, a right image and a top image of a scene, using a trinocular image acquisition device;

using a vision system to carry out the steps of;

separately processing each of said left, right and top images to filter each image and to create corresponding sets of edge characteristics for each image;

stereoscopically matching features between said right and left images to create a set of vertical feature matches, each having a disparity vector;

stereoscopically matching features between said right and top images to create a set of horizontal feature matches, each having a disparity vector;

selecting all features from the set of vertical feature matches having a disparity that is substantially vertical and discarding corresponding features from the set of horizontal matches, to obtain a combined set of selected vertical features and horizontal features;

extracting a set of 3-D features from said combined set of features, based upon predetermined camera geometry;

filtering said set of 3-D features to eliminate features corresponding to predetermined 3-D locations; and

clustering said filtered set of 3-D features into a set of 3-D objects, according to discontinuities in a range dimension among successive 3-D points in a chain of points corresponding to a 3-D feature.

11. The method of claim 10 in which said steps of stereoscopically matching each further comprise the steps of:

for each feature in a first image, removing features in a second image that do not satisfy an epipolar constraint, calculating a strength of match (SOM) for each remaining feature in said second image, eliminating features from said second image whose SOM is less than a predetermined threshold, calculating a new SOM according to the SOM of neighboring features on a chain of each remaining feature in said second image, and designating the features having the strongest SOM as a match.

12. The method of claim 10 in which said disparity is determined to be substantially vertical if the feature being evaluated has an angular orientation that is more than 45 degrees from horizontal.

13. The method of claim 10 in which said step of filtering further comprises the steps of:

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

eliminating 3-D points that exceed application-specific thresholds for relative range from said trinocular 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;

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.