Method for 3D modelling based on structure from motion processing of sparse 2D images

• US 10,198,858 B2
• Filed: 03/27/2017
• Issued: 02/05/2019
• Est. Priority Date: 03/27/2017
• Status: Active Grant

• Current Assignee: 3Dflow SRL
• Original Assignee: 3Dflow SRL
• Inventors: Singh, Yash, Toldo, Roberto, Magri, Luca, Fantoni, Simone, Fusiello, Andrea
• Primary Examiner(s): Xiao, Ke
• Assistant Examiner(s): Imperial, Jed-Justin
• Application Number:
  US15/470,863
• Publication Number:
  US 20180276885A1
• Time in Patent Office: 680 Days
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20072 Graph-based image processing
• CPC Class Codes: G06T 2207/20104 Interactive definition of region of interest [ROI]
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 2210/56 Particle system, point based geometry or rendering
• CPC Class Codes: G06T 2215/16 Using real world measurements to influence rendering
• CPC Class Codes: G06T 7/579 from motion

Abstract

A method based on Structure from Motion for processing a plurality of sparse images acquired by one or more acquisition devices to generate a sparse 3D points cloud and of a plurality of internal and external parameters of the acquisition devices includes the steps of collecting the images; extracting keypoints therefrom and generating keypoint descriptors; organizing the images in a proximity graph; pairwise image matching and generating keypoints connecting tracks according maximum proximity between keypoints; performing an autocalibration between image clusters to extract internal and external parameters of the acquisition devices, wherein calibration groups are defined that contain a plurality of image clusters and wherein a clustering algorithm iteratively merges the clusters in a model expressed in a common local reference system starting from clusters belonging to the same calibration group; and performing a Euclidean reconstruction of the object as a sparse 3D point cloud based on the extracted parameters.

Claims

1. A method based on Structure from Motion for processing a plurality of sparse images of an object acquired by one or more acquisition devices to generate a sparse 3D points cloud and of a plurality of internal and external parameters of the acquisition devices obtained by processing the images, comprising the following steps:

(a) collecting the images;

(b) extracting keypoints from each image and generating a descriptor for each keypoint;

(c) organizing the images in a proximity graph;

(d) pairwise image matching and generating keypoints connecting tracks according to maximum proximity between the keypoints;

(e) performing an autocalibration between image clusters to extract the internal and external parameters of the acquisition devices, wherein a plurality of calibration groups is defined, each calibration group containing a plurality of image clusters, and wherein a clustering algorithm is used to iteratively merge the clusters in a model expressed in a common local reference system, the clustering being carried out starting from clusters belonging to a same calibration group; and

(f) performing a Euclidean reconstruction of the object in form of the sparse 3D point cloud based on the parameters extracted at the preceding step.

2. The method according to claim 1, wherein the step of performing an autocalibration is hierarchical and comprises a projective stereo modeling step if merging single images merging, a resection/intersection step if adding an image to a cluster, and a merging of two models step if merging two groups reconstructed independently from each other.

3. The method according to claim 1, wherein the images are associated to EXIF parameters and the calibration groups are formed based on similarity between the EXIF parameters of the images.

4. The method according to claim 1, wherein, during the step of performing a Euclidean reconstruction, a plurality of calibration groups is defined, each calibration group containing a plurality of image clusters, and wherein a clustering algorithm is used to iteratively merge the clusters in a model expressed in a common local reference system, the clustering being carried out starting from clusters belonging to a same calibration group.

5. The method according to claim 1, further comprising a step of generating a 3D model with a Multiview Stereo algorithm based on the sparse 3D points cloud and on said internal and external parameters of the acquisition devices, the Multiview Stereo algorithm computing a depth map for each image and subsequently generating a dense 3D points cloud based on all computed depth maps.

6. The method according to claim 5, wherein outliers are removed from the dense 3D points cloud by applying visibility constraints.

7. The method according to claim 1, wherein extracting keypoints comprises calculating a global response score threshold for each keypoint, and wherein a predetermined number of keypoints with higher global response scores are taken into account, remaining keypoints being disregarded.

8. The method according to claim 1, wherein the descriptor is calculated on a circular region placed around the keypoint and subdivided into subregions, the descriptor comprising a histogram having a predetermined number of bins configured to assume different values, the values being calculated based on a response of each single pixel belonging to each subregion to a steering filter, which is steered in a predetermined number of orientations.

9. The method according to claim 1, wherein organizing the images in the proximity graph comprises an iteration of a maximum spanning tree algorithm to identify a maximum number of connections between images corresponding to a maximum similarity score by:

(c1) identifying a path connecting the images, such that the similarity is maximum for adjacent images;

(c2) saving image couples for subsequent processing;

(c3) setting to zero a similarity of the identified image couples;

(c4) identifying a further path connecting the images, such that the similarity is maximum for the adjacent images;

(c5) saving further image couples for the subsequent processings;

(c6) setting to zero the similarity of the identified further image couples; and

(c7) iterating steps (c4)-(c6).

10. The method according to claim 1, further comprising a step of extracting silhouettes from a background of an image that comprises:

(g) subdividing the image in groups of contiguous pixels with color variation lower than a predetermined threshold;

(h) displaying the image to a user;

(i) having the user identify at least a foreground area in a foreground and at least a background area in the image by tracing at least two marks on the image, the marks being traced with different modalities to indicate the foreground area and the background area respectively;

(j) creating two clusters of groups of the pixels relative to the foreground and the background areas respectively;

(k) assigning a group of pixels touched by each mark of the user to one of the two clusters of group of pixels based on the modality of the mark;

(l) creating a temporary list of groups of pixels not yet assigned to one of the two clusters; and

(m) assigning iteratively the group of pixel which is present in the temporary list and has a minimum difference of mean color with respect to one of its adjacent groups of pixels to the cluster of group of pixel to which the one of its adjacent groups of pixels belongs.

11. The method according to claim 1, wherein data provided from one or more of gyroscopes, magnetometers, or accelerometers is included in determining neighboring images.