Keyframe-based object scanning and tracking

Described herein are methods and systems for keyframe-based object scanning and tracking. A sensor device captures images of objects in a scene. For each image, a computing device labels each of at least a plurality of pixels in the image, tracks at least one region of the labeled image to determine an estimate of a current pose of at least one object, validates the estimate of the current pose of the at least one object, selects the labeled image as a keyframe based upon validation of the estimate of the current pose, and updates a volumetric model comprising the at least one object using the keyframe. The computing device generates a final 3D model of the at least one object based upon the updated volumetric model.

TECHNICAL FIELD

This subject matter of this application relates generally to methods and apparatuses, including computer program products, for keyframe-based object scanning and tracking—including techniques for improved computer vision tracking using machine learning.

BACKGROUND

Generally, some current techniques for performing unified tracking of an object in a 3D scene are based on using a 2D keyframe and a raycast point cloud derived from the global model. An example of this type of technique is described in U.S. patent application Publication Ser. No. 16/123,256, titled “Combining Sparse Two-Dimensional (2D) and Dense Three-Dimensional (3D) Tracking.”

This technique works well when using a high-quality structured light sensor, which can provide an accurate depth map and which, in turn, provides an accurate pose result. However, when using a sensor that is not as accurate, such as a back-illuminated time-of-flight (ToF) image sensor from Sony Corp., for example, the pose calculation tends to be less accurate resulting in drifting of the tracking as the object is rotated over 360 degrees. This drifting then in turn causes significant problems at the loop-end of the object—as well as in the quality of the 3D global model.

In addition, one of the problems in using dynamic capture in traditional computer vision/object tracking platforms is that there are certain conditions in which the pose computation is not accurate. This results from the fact that there is no single tracking algorithm that works for all possible sets of 2D+3D features used in tracking. When this error occurs, it could cause deformation of the 3D model due to having a wrong pose—which means that the entire scanning process has to be repeated from the start. Therefore, it is important to detect when such condition occurs such that the 3D model is not updated with the latest incoming depth map image until the pose is correct again. Hence, what is needed is a quality check module that can accurately detect the condition of an incorrect pose.

There are two areas in tracking where this ‘false positive pose’ (also known as ‘drifting check’) can help. First, during scanning while the object is being tracked, if such erroneous condition is detected, the system can stop the mapping process. Second, if tracking is lost completely, the system can validate the re-localization of the object. In either case, a reliable detection of such conditions is very important.

In traditional implementations, a set of criteria with adjustable parameters is used to detect the condition of an incorrect pose. However, it is very difficult to properly come up with a set of conditions and parameters that are reliable over a very large number of different types of objects with different sets of features. The process is very time consuming with results not being as reliable as needed.

SUMMARY

Therefore, what is needed are methods and systems that overcome the technical challenges generated by less-accurate ToF sensors to provide accurate and robust object tracking when using such sensors. The techniques described herein advantageously provide keyframe-based tracking—even for dense tracking—based on the depth map. Hence, as described herein, the tracking relies on the local depth map and 2D keyframes—as opposed to the 3D global model. It also allows for a real-time correction of the 3D global model based on the truncated signed distance function (TSDF).

Also, the techniques described herein advantageously apply machine learning techniques to the incorrect pose problem described above, using a set of key criteria along with a large training dataset. This approach thus provides a validation process which verifies that the estimated pose is accurate. As described herein, the algorithm utilizes current color and depth maps, current feature points, reference keyframes, and model raycast data to inform the validation.

The main idea of validation is the same whether the system is using it to verify re-localization or using it as a drifting check during the scanning to detect ‘false positive’ conditions where the pose is inaccurate. The central difference is that false negatives (i.e., when the pose is correct, but the system assigns the pose as being incorrect) have a larger impact during scanning, potentially causing too many tracking losses. Hence, during tracking, the system advantageously leverages the machine learning techniques to both detect false positives and minimize the false negative rate.

The invention, in one aspect, features a system for keyframe-based object scanning and tracking. The system comprises a sensor device that captures a plurality of images of one or more objects in a scene, and a computing device coupled to the sensor device that comprises a memory that stores computer-executable instructions and a processor that executes the instructions. For each image of the plurality of images, the computing device labels each of at least a plurality of pixels in the image as either a background pixel, a foreground noise pixel, an object pixel, or an unknown pixel; tracks at least one region of the labeled image to determine an estimate of a current pose of at least one of the one or more objects, wherein the at least one region is determined by the labeled pixels; validates the estimate of the current pose of the at least one of the one or more objects; selects the labeled image as a keyframe based upon validation of the estimate of the current pose of the at least one of the one or more objects; and updates a volumetric model comprising the at least one of the one or more objects using the keyframe. The computing device generates a final 3D model of the at least one of the one or more objects based upon the updated volumetric model.

The invention, in another aspect, features a computerized method of keyframe-based object scanning and tracking. A sensor device captures a plurality of images of one or more objects in a scene. For each image of the plurality of images, a computing device coupled to the sensor device labels each of at least a plurality of pixels in the image as either a background pixel, a foreground noise pixel, an object pixel, or an unknown pixel; tracks at least one region of the labeled image to determine an estimate of a current pose of at least one of the one or more objects, wherein the at least one region is determined by the labeled pixels; validates the estimate of the current pose of the at least one of the one or more objects; selects the labeled image as a keyframe based upon validation of the estimate of the current pose of the at least one of the one or more objects; and updates a volumetric model comprising the at least one of the one or more objects using the keyframe. The computing device generates a final 3D model of the at least one of the one or more objects based upon the updated volumetric model.

Any of the above aspects can include one or more of the following features. In some embodiments, tracking at least one region of the labeled image comprises: rendering an anchor depth map based upon an implicit surface of the at least one of the one or more objects, the implicit surface defined by a Truncated Signed Distance Function (TSDF); identifying one or more reference keyframes based upon the labeled image; defining first error terms between the labeled image and the anchor depth map using Iterative Closest Point (ICP); defining second error terms between the labeled image and the one or more reference keyframes based upon matching features; and minimizing the first error terms and the second error terms to determine the estimate of the current pose of the at least one of the one or more objects.

In some embodiments, validating the estimate of the current pose of the at least one of the one or more objects comprises comparing the estimate of the current pose of the at least one of the one or more objects to a pose of the at least one of the one or more objects in one of the one or more reference keyframes. In some embodiments, validating the estimate of the current pose of the at least one of the one or more objects comprises: generating a feature set using a depth map associated with the labeled image, the anchor depth map, the estimate of the current pose of the at least one of the one or more objects, one or more ORB features of the at least one of the one or more objects, and one or more of the reference keyframes, wherein the feature set comprises a dense error value and a sparse error value; generating a feature vector from the feature set; and executing a machine learning classifier on the feature vector to classify the feature vector as corresponding to a correct object pose or an incorrect object pose.

In some embodiments, the machine learning classifier is trained on training data to predict whether an input feature vector corresponds to a correct object pose. In some embodiments, the machine learning classifier includes a bias value to adjust a classification outcome of the classifier.

In some embodiments, selecting the image as a keyframe based upon validation of the estimate of the current pose of the at least one of the one or more objects comprises: identifying one or more of: a strength of color features in the labeled image, a confidence of the estimate of the current pose, or a presence of foreground noise in the labeled image; and selecting the labeled image as a keyframe based upon the identified strength of color features in the labeled image, the confidence of the estimate of the current pose, or the presence of foreground noise in the labeled image. In some embodiments, the computing device evaluates one or more reference keyframes related to the labeled image to determine whether one or more of the reference keyframes are redundant. In some embodiments, the computing device removes one or more redundant reference keyframes.

In some embodiments, updating a volumetric model comprising the at least one of the one or more objects using the keyframe comprises one or more of: adding the keyframe to the volumetric model; or removing the keyframe from the volumetric model. In some embodiments, adding the keyframe to the volumetric model comprises: determining a distance from each cell in a surface of the at least one of the one or more objects in the volumetric model to a surface of the at least one of the one or more objects in the keyframe; and averaging the determined distance into the volumetric model. In some embodiments, removing the keyframe from the volumetric model comprises subtracting the determined distance from the volumetric model.

In some embodiments, the computing device generates an initial volumetric model of the at least one of the one or more objects, searches for a registration between the initial volumetric model and the updated volumetric model, and merges the initial volumetric model with the updated volumetric model when a registration is found.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a system100for keyframe-based object scanning and tracking. Certain embodiments of the systems and methods described in this application utilize:the object recognition, reconstruction, and analysis techniques as described in U.S. Pat. No. 9,715,761, titled “Real-Time 3D Computer Vision Processing Engine for Object Recognition, Reconstruction, and Analysis;”the dynamic 3D modeling techniques as described in U.S. patent application Ser. No. 14/849,172, titled “Real-Time Dynamic Three-Dimensional Adaptive Object Recognition and Model Reconstruction;”the shape-based registration and modeling techniques described in U.S. Pat. No. 10,169,676, titled “Shape-Based Registration for Non-Rigid Objects with Large Holes;”the 3D photogrammetry techniques described in U.S. Pat. No. 10,192,347, titled “3D Photogrammetry;”the sparse SLAM and unified tracking techniques as described in U.S. patent application Ser. No. 15/638,278, titled “Sparse Simultaneous Localization and Matching with Unified Tracking;”the 2D and 3D video compression techniques described in U.S. patent application Ser. No. 15/726,316, titled “Real-Time Remote Collaboration and Virtual Presence using Simultaneous Localization and Mapping to Construct a 3D Model and Update a Scene Based on Sparse Data;”the object tracking techniques as described in U.S. patent application Ser. No. 16/123,256, titled “Combining Sparse Two-Dimensional (2D) and Dense Three-Dimensional (3D) Tracking;”the 4D hologram technology described in U.S. patent application Ser. No. 16/240,404, titled “4D Hologram: Real-Time Remote Avatar Creation and Animation Control;”the real-time texture alignment techniques described in U.S. patent application Ser. No. 16/374,023, titled “Dynamic Real-Time Texture Alignment for 3D Models;”the 3D capture techniques described in U.S. Provisional Patent Application No. 62/843,680, titled “3D Capture Using Edge Cloud Computing Resources;” andthe remote 3D animation techniques described in U.S. Provisional Patent Application No. 62/843,683, titled “Remote Visualization of 3D Animation With Synchronized Voice in Time.”

Each of the above-referenced patents and patent applications is incorporated by reference herein in its entirety. The methods and systems described in the above patents and patent applications, and in the present patent application, are available by implementing the Starry Night SDK, available from VanGogh Imaging, Inc. of McLean, Va.

The system includes a sensor103coupled to a computing device104. The computing device104includes an image processing module106. In some embodiments, the computing device can also be coupled to a data storage module108, e.g., used for storing certain 3D models, color images, and other data as described herein. The sensor103is positioned to capture images (e.g., color images) of a scene101which includes one or more physical objects (e.g., object102). In some embodiments, a user manually rotates and moves the object102in the scene101so that the sensor103captures a plurality of scans of the object from different angles and/or sides; in some embodiments, the user's hand is captured in the scans along with the object.

Exemplary sensors that can be used in the system100include, but are not limited to, time-of-flight (ToF) sensors that are capable of capturing depth information of the pixels along with the images of a real-world object and/or scene to collect data on its position, location, and appearance. Other types of sensors include 3D scanners, digital cameras, and other types of devices. In some embodiments, the sensor103is embedded into the computing device104, such as a camera in a smartphone, for example. An exemplary sensor103can be a 3D scanner built from combining a depth camera and a high-resolution RGB camera. The cameras can be calibrated so their data can be registered to each other. In one embodiment, the sensor103includes an Orbbec Astra Mini depth camera attached to, e.g., a mobile device with an embedded camera. It should be appreciated that other combinations of these devices or other devices can be used to perform the techniques described herein.

The computing device104receives images (also called scans) of the scene101from the sensor103and processes the images to generate 3D models of objects (e.g., object102) represented in the scene101. The computing device104can take on many forms, including both mobile and non-mobile forms. Exemplary computing devices include, but are not limited to, a laptop computer, a desktop computer, a tablet computer, a smartphone, a smart watch, an internet of things (IoT) device, augmented reality (AR)/virtual reality (VR) devices (e.g., glasses, headset apparatuses, and so forth), or the like. In some embodiments, the sensor103and computing device104can be embedded in a larger mobile structure such as a robot or unmanned aerial vehicle (UAV). It should be appreciated that other computing devices can be used without departing from the scope of the invention. The computing device104includes network-interface components to connect to a communications network (not shown). In some embodiments, the network-interface components include components to connect to a wireless network, such as a Wi-Fi or cellular network, in order to access a wider network, such as the Internet.

The computing device104includes an image processing module106configured to receive images captured by the sensor103and analyze the images in a variety of ways, including detecting the position and location of objects represented in the images and generating 3D models of objects in the images. The image processing module106is a hardware and/or software module that resides on the computing device104to perform functions associated with analyzing images capture by the scanner, including the generation of 3D models (e.g., .OBJ files) based upon objects in the images. In some embodiments, the functionality of the image processing module106is distributed among a plurality of computing devices. In some embodiments, the image processing module106operates in conjunction with other modules that are either also located on the computing device104or on other computing devices coupled to the computing device104. It should be appreciated that any number of computing devices, arranged in a variety of architectures, resources, and configurations (e.g., cluster computing, virtual computing, cloud computing) can be used without departing from the scope of the invention. An exemplary image processing module106is the Starry Night SDK, available from VanGogh Imaging, Inc. of McLean, Va.

It should be appreciated that in one embodiment, the image processing module106comprises specialized hardware (such as a processor or system-on-chip) that is embedded into, e.g., a circuit board or other similar component of another device. In this embodiment, the image processing module106is specifically programmed with the image processing and modeling software functionality described below.

In some embodiments, the computing device104includes a machine learning classifier107, which is a specialized hardware and/or software module that can be trained with a set of object tracking training data to generate a classification model that automatically validates tracking (i.e., pose information) associated with one or more objects in the scene—as will be described in greater detail below.

The keyframe-based object reconstruction process described herein uses a model that is defined by a set of keyframes. In order to speed up processing, a volumetric model is rebuilt from the keyframe set every time a keyframe is inserted or removed. Keyframes consist of a color image, a depth image aligned to the color image, an estimated pose, and a labeling of all locations in the images into semantic categories. The volumetric model contains a truncated signed distance field (TSDF) and a probabilistic space labeling. The TSDF is generated by projecting each depth image into the model space based on its pose and describes the implicit surface of the object being scanned. The space labeling is created by analyzing the labels associated with the depth image and is used to classify points in future frames.

As will be described below, the scanning system is composed of a tracking and a mapping subsystem. During scanning, the location of the object is tracked against a model, which is built from select input frames. In the event of tracking loss, the system restarts construction at the new location while simultaneously trying to align the new map to the original. The system tracks each frame individually in sequence. Upon receiving a new frame of data, the system first attempts to label regions of the image that correspond to the desired object, unwanted foreground noise, and the background behind the object. The system then attempts to align the object portion of the input by aligning it with a combination of model parameters via several error terms. The first set of terms comes from the input 3D point cloud and an anchor point cloud rendered from the TSDF at the last estimated pose. Further terms are supplied by corner, edge, and 3d features in the keyframes close to the current frame.

FIG. 2is a flow diagram of a computerized method200of keyframe-based object scanning and tracking, using the system100ofFIG. 1. The sensor103captures one or more scans (also called frames or images) of the object102in the scene, and transmits a depth map and a color image for each scan to the image processing module106, for use as input to object tracking and model generation process.

The image processing module106labels (202) the input frame. In the labeling process, each pixel in the depth image of each keyframe is labeled as either background, foreground noise, object, or unknown. Generally, background pixels are those which must be behind the object. They imply there is no part of the object along the ray associated with that pixel. Object pixels are those depth points corresponding to the object that the system is trying to track and reconstruct. Foreground noise pixels are any points around the object that the system does not wish to track, including the user's hands or clutter in the environment. Parts of the object may be behind the foreground noise point. Unknown pixels are those that cannot be accurately categorized or do not have any depth data. In some embodiments, the image processing module106generates label data (e.g., a mapping file that defines the pixel labels in conjunction with the depth/image data) and stores the generated label data in database108. Labels are generated by examining each pixel's geometric relationship to the total scene geometry for that frame and the estimated model location. For instance, the image processing module106labels a group of points close to the camera surrounded by distant points as an object, while a point that is part of a large plane of points is probably part of the table on which the user is scanning, and the image processing module106labels the point as background.

FIG. 3is a diagram showing how the system100labels portions of the keyframe. As shown inFIG. 3, the image processing module106receives an input keyframe302, and labels the sphere304in the middle of the keyframe as ‘object,’ labels a portion306of the keyframe as ‘background,’ labels another portion308of the keyframe as ‘surface,’ and labels certain regions310a,310baround the object as ‘noise.’

Once the frame is labeled, the image processing module106tracks (204) a region (i.e., an object region) of the labeled frame. Using a keyframe-based model allows the image processing module106to track many different features than just the 3D surface. It also allows the module106to check surface reconstruction against ground truth to help detect error conditions.FIG. 7is a workflow diagram of object region tracking, using the system100ofFIG. 1.

As shown inFIG. 7, the current input frame702comprises a color and depth image, both already warped to a common alignment. The module106also has a rough estimate of the pose702aof the object in the current input frame based on the optimized pose704aof the previous frame704. In order to optimize the current estimated pose, the module106renders an anchor depth map706based on the implicit surface defined by the TSDF as well as identifying several nearby reference keyframes (e.g.,708a,708b). The module106defines error terms between the current frame702and the anchor map706using projection iterative closest point (ICP), and further error terms between the current frame702and the reference keyframes708a,708bbased on matching corner and edge features. Minimizing these terms gives the module106an optimal estimate710afor the current pose of the object (e.g., in an optimized frame710).

The module106can then validate the tracking by comparing the current frame702to the individual keyframes708a,708b. A large error in several keyframes may indicate that tracking was not successful, while a large error in a single keyframe may mean that the keyframe pose is inaccurate and should be removed. As the module106continues to track the object(s), the module106accumulates statistics about the reference keyframes used and how accurate they are compared to other nearby keyframes. Low-quality keyframes can be removed and high accuracy input frames can be saved as keyframes. This way, tracking and model quality continues to improve throughout the tracking process.

In some embodiments, the image processing module106utilizes advanced algorithmic techniques described herein to train the machine learning classifier module107with a set of training data, then leverage the trained classifier107to automatically validate the tracking (e.g., the pose information). The module106can encapsulate indicator values into a fixed-size vector of real numbers and a machine learning classifier107is trained using a large number of examples of these vectors individually labeled “true” or “false.” As a result, the classifier107solves the incorrect pose problem, allowing the image processing module106to automatically find the best transformation for every set of data in a short amount of time. As well, the training process produces hard numbers proving exactly how good a given approach is.

Data Requirements

In order to be confident in the output of training the machine learning classifier107, the image processing module106must have a statistically meaningful set of data which covers more-or-less all situations that one is interested in handling. As well, the larger the feature vector, the more data is needed. For a three-element vector, two hundred samples may be sufficient. A ten-element vector may require several thousand. There should be a similar number of “true” and “false” samples.

Generally, in machine learning applications, data collection typically happens in rounds. An initial set of data is labeled and a classifier is trained. The classifier (e.g., machine learning classifier107) can then be tested using more data. If the classifier107performs well, then the training phase is complete. If not, the module106can add the incorrectly classified data to the training set. This approach deliberately trains the classifier107on the cases it would otherwise get wrong.

Another way to estimate how much training data the module106needs by looking at the cross-validation results. If the training results (in terms of false positives and false negatives) are significantly better than the cross-validation results, then the classifier107is probably overfitting the data. The module106can then either reduce the size of the feature vector or add more data items

How Regression Works

The machine learning classifier107uses logistic regression to find the best separating hyperplane between the data. The classifier107starts by assigning “true” samples a value of 1 and “false” 0. Call this value yifor sample i. The module106wants to find θ that best approximates {xi, yi} for all i via the function

The classifier107finds this value by running Newton's method on a cost function summing errors for each data sample. The classifier107then rounds the predicted f(x) to either 0 or 1 to classify any new data. Alternatively, the classifier107can simply test if the dot product of θ and x is greater or less than zero. This simple classification scheme has the advantage of being very fast, so it can be run every frame.

Extracting Features

FIG. 4is a flow diagram of a method for classifying pose information using machine learning. As shown inFIG. 4, a feature set (i.e., a set of input parameters to be classified) is generated using certain input data created from one or more scans of the objects—depth map402, anchor points404, current pose406, ORB features408, keyframe410. The feature set comprises three values: two values for dense error412and one value for sparse error414. The two values in the dense error feature412are (i) the ratio of matched dense points to total points in the current model and (ii) the ratio of missing dense points to total points in the current 3D model. In this example, a matched point is a point where the input depth map402value is within some small distance of the expected 3D model point value (as determined from the current pose406and anchor points404). A missing point is a point where the input depth map402value is much larger than the expected model point value, indicating that the image processing module106can see through where part of the 3D model is supposed to be if the pose was correct. The sparse error value414is a count of the number of 2D ORB features408that currently can be seen and which have a close match in the keyframe410. It should be appreciated that the more matching ORB features, the more likely that the pose is correct. The image processing module106generates a feature vector416from the dense error412values and the sparse error414value, and transmits the feature vector to the machine learning classifier107as input. The classifier107executes to classify the vector as corresponding to an object pose that is correct (e.g., Yes) or incorrect (e.g., No) and generate associated output418for use by the module106.

FIG. 5is a flow diagram for classifying object pose information using machine learning. As shown inFIG. 5, the classifier107can be used after tracking508every input frame, using the input sensor data502, anchor point data504, and keyframe data506(as described above). If the current pose is untrusted, such as when the image processing module106has recently re-localized (i.e., re-localization512), the image processing module106uses the classifier107aas trained. Once the current pose is trusted, the machine learning classifier107bcan include bias in the classification process (e.g., by lowering the passing threshold) to avoid having too many false positives. In this way, the classifier107acts as both a validator for re-localization and a drifting check during normal tracking. As above, the classifier107aor the classifier with bias107bexecutes to classify the vector as corresponding to an object pose that is correct (e.g., Yes) or incorrect (e.g., No) and generate associated output510for use by the image processing module106.

FIG. 8is a graph showing the performance of an exemplary machine learning classifier (e.g., classifier107) that detects drift. A positive result indicates that drifting has occurred. The graph ofFIG. 8shows the tradeoff between the true positive rate (TPR), i.e. how many drifted frames were correctly identified, versus the false positive rate (FPR), i.e. how many correctly aligned frames were misclassified as drifted. Different bias levels correspond to different points on the curve. The point802labeled “no bias” presents an optimal balance between TPR and FPR for a single frame and is used during re-localization. However, during tracking the system can consider many similar frames in succession, so a large negative bias can be chosen (point804), lowering the FPR at the cost of the TPR.

Also, it should be appreciated that the machine learning techniques described herein can be used for any part of tracking where the image processing module106needs to accept or reject some value based on the current state. As an example, the image processing module106can use the machine learning techniques to intelligently decide which features are more relevant versus others in order to provide more accurate pose calculation. The same regression and data analysis is valid for many classification tasks.

Turning back toFIG. 2, once the tracking and validation (204) is complete, the image processing module106determines whether to keep the optimized frame and if so, the image processing module106selects (206) the optimized frame as a keyframe. For example, the current loose frame is considered for inclusion in the keyframe set based on a number of criteria, including uniqueness of position, strength of color features, confidence of the pose estimate, and presence of foreground noise. Once a keyframe is inserted, the module106re-evaluates nearby keyframes to see if those nearby keyframes are now redundant. If so, the module106removes them, erasing their influence on the TSDF and object boundary. Removing low-quality keyframes helps improve both cropping and tracking of future frames, creating a positive feedback loop that improves overall model quality.FIG. 9is a workflow diagram of insertion and evaluation of keyframes, using the system100ofFIG. 1. As an example, the object being scanned is a teddy bear. As shown inFIG. 9, the image processing module106captures a current loose frame as a first keyframe (step902) that includes a model of the object. The image processing module106adds other keyframes—for example, the module106can add a new keyframe (step904); however, this keyframe may include a misaligned model of the object. The module106can still determine whether nearby keyframes are now redundant (step906)—even for keyframes that may contain a misaligned model. The module106does not add the redundant keyframes. Then, the module106can remove poor or low-quality keyframes (step908) and in some cases, can replace the removed keyframes with new keyframes that are of better quality.

As mentioned above, the keyframe has previously been labeled to identify, e.g., either background, foreground noise, object, or unknown pixels. The image processing module106uses the keyframe labels to create probabilistic labels of the volumetric model. For each voxel in the volumetric model, the image processing module106projects the voxel to each keyframe and determines what information both the label (e.g., background, foreground noise, object, or unknown) and depth map can give about that location in space. For instance, by counting the number of times a particular voxel appears as either background, object, or in front of any depth point, the module106estimates the probability that the voxel either contains an object point or is empty. The module106then uses this estimate to influence future labels. For instance, if a new depth point under consideration lies in a voxel with a large chance of being empty then the module106can label the depth point as foreground noise, whereas if the voxel is frequently labeled as object, then the new point is probably an object point as well and the image processing module106can label the depth point as object.

FIG. 6is a diagram showing an exemplary volumetric probability model technique used by the image processing module106. As shown inFIG. 6, the image processing module106projects each voxel to each keyframe602a,602b,602cand determines a probability that each voxel is part of the object (i.e., high object probability, white region604) or is not part of the object (i.e., low object probability, shaded region606). The image processing module106also determines a projected object boundary608.

It should be appreciated that, depending on the quality of the input depth data and the available processing resources on the computing device104platform, the image processing module106may not have enough information to reconstruct a smooth model. For example, if keyframes are noisy, the module106needs more keyframes to smooth out that noise. If the image processing module106and/or computing device104in general have limited memory, the module106needs to use fewer keyframes. In environments that are both noisy and constrained, the module106needs to combine multiple depth maps into a single keyframe. To do this, the image processing module106keeps a set of approximately thirty of the most recent aligned depth images. When the module106selects an image to be a keyframe, the module106can combine the depth map of the selected frame with the set of most recent aligned depth maps, smoothing out noise and increasing the amount of information available in a single keyframe. Where a typical model may need three hundred good input frames to produce a high quality model, the module106can use fifty multi-frame keyframes and get the same quality results. This also allows the module106to run post-processing model adjustment faster than otherwise. Because many frames are already combined into one, there are fewer keyframes to adjust and optimize.

Continuing withFIG. 2, the image processing module updates (208) the volumetric model using the selected keyframe. The volumetric model is an implicit surface defined by the estimated distance from each cell in the volume to the true surface of the object. The biggest advantage of maintaining a keyframe-based model is the ability to easily modify the model to add, remove, or readjust input data to fix errors. In some embodiments, the image processing module106adds a keyframe to the volumetric model by averaging in the distance from each cell to the object's surface found in the keyframe. The module106can then remove the keyframe by subtracting this distance back out from the (potentially updated) cell average. Readjustment is equivalent to removing a keyframe and then re-adding it. There are generally three major sources of model error encountered during object reconstruction: noise, drift, and cutoff. Noise occurs when non-model points are incorrectly added to the model. In the present system, this may happen when the image processing module106incorrectly labels a portion of an input point cloud as part of the object. The portion then gets incorporated into the model, creating erroneous surfaces. To address this, the module106gradually relabels keyframes as more accurate model information is gathered.FIG. 10is a workflow diagram of removing noisy keyframes and re-adding keyframes after removing noise, using the system100ofFIG. 1. As shown inFIG. 10, the image processing module106captures a current loose frame as a first keyframe (step1002) that includes a model of the object. Then, the image processing module106may add a new keyframe that includes noise (step1004)—e.g., the arm of the teddy bear is not smooth. The module106can remove the noisy keyframe (step1006) and eliminate the noise (e.g., by smoothing the keyframe) then re-add the keyframe (step1008) after removing the noise.

Drift occurs when the object is first scanned in a 360-degree arc. When a loop is first closed around the object, every small drifting error from frame to frame is added together to create a large error between the initial object pose and the current object pose. This means that keyframes taken from disparate times in the frame sequence do not line up with each other. As noted previously, the module106detects this during tracking, when the current input data may line up very well with one reference keyframe but not another. The image processing module106fixes this problem by identifying the magnitude of the pose error and optimizing the keyframe poses to reduce this error. Once the keyframes are optimized, the module106can rebuild the volumetric model and continue scanning. The last model error mentioned above is cutoff, which occurs when the probabilistic labeling is incorrect and a voxel that should be part of the object is labeled as empty. This happens both when keyframe labeling is wrong and when the keyframe pose has some error. In both cases, the solution is as discussed before, namely to relabel the keyframe or adjust its pose to improve alignment.

Finally, the image processing module106processes (210) the updated volumetric model to generate a final 3D model. It should be appreciated that, during scanning, especially with inexperienced users, it is fairly easy to lose tracking on the object. The naive strategy when this happens is to try to re-localize the object before continuing to scan. This requires the user to return the object to some previously scanned pose, perhaps trying several poses if re-localization is not working well. As a result, scanning time and user frustration increases.

To avoid this, the system100makes use of the fact that the volumetric model can be reconstituted from any set of keyframes. The image processing module106starts by creating a new volumetric model, then merges this new model into the old model once the module106is able to register the two together. This allows the user to continue to scan and make progress on the model. While this new model is being built, the image processing module106searches for a registration between the new model and old model in a separate processing thread, then seamlessly merges the two together once the registration is found. If a registration cannot be found, the module106can wait and let the new model grow more detailed, making a second attempt at registration more likely to succeed. Merging the two models involves transforming the new model's keyframes into the coordinate system of the old model, combining all keyframes into one set, then rebuilding the volumetric model.

FIG. 11is a workflow diagram of registration and merging of the volumetric model during tracking loss, using the system100ofFIG. 1. The image processing module106generates a model (step1102) using the TSDF volume and keyframe. If tracking is lost while the image processing module106builds the model using a new keyframe, the module106can simply create a new model (step1104). The module106then searches for a registration between the new model and old model in a separate processing thread (step1106)—for example, given any number of models, the module106repeatedly tries to combine the current model with any of the older ones. Once the module106finds a registration between an old model and the new model, the module106merges the two models together (step1108). This eventually leads back to a single unified model once the object has been fully scanned.

To provide for interaction with a user, the above described techniques can be implemented on a computer in communication with a display device, e.g., a CRT (cathode ray tube), plasma, or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse, a trackball, a touchpad, or a motion sensor, by which the user can provide input to the computer (e.g., interact with a user interface element). Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, and/or tactile input.

One skilled in the art will realize the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The foregoing embodiments are therefore to be considered in all respects illustrative rather than limiting of the invention described herein.