Abstract:
A combination of three computational components may provide memory and computational efficiency while producing results with little latency, e.g., output can begin with the second frame of video being processed. Memory usage may be reduced by maintaining key frames of video and pose information for each frame of video. Additionally, only one global volumetric structure may be maintained for the frames of video being processed. To be computationally efficient, only depth information may be computed from each frame. Through fusion of multiple depth maps from different frames into a single volumetric structure, errors may average out over several frames, leading to a final output with high quality.

Description:
BACKGROUND 
     There has been an increasing interest in using consumer mobile devices, such as tablet computers and mobile phones, for so-called augmented reality or mixed reality applications. Using such applications, an individual can manipulate virtual objects in virtual scenes on a device based on images captured by the device of its surroundings. 
     SUMMARY 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is intended neither to identify key or essential features, nor to limit the scope, of the claimed subject matter. 
     A combination of three computational components provides memory and computational efficiency while producing results with little latency, e.g., output can begin with the second frame of video being processed. Memory usage is reduced by maintaining key frames of video and pose information for each frame of video, but not retaining image data from all frames of video being processed. Additionally, only one global volumetric structure is maintained for the frames of video being processed. To be computationally efficient, only depth information is computed from each frame. Through fusion of multiple depth maps from different frames into a single volumetric structure, errors average out over several frames, leading to a final output with high quality. 
     Accordingly in one aspect, a device has a camera tracking circuit, a depth map estimation circuit and a volumetric fusion circuit. The camera tracking module has an input to receive an image from a sequence of images and an output to provide a pose for the camera. It also provides an output storing the image as a key frame based on the pose of the image and a pose of other stored key frames. The depth map estimation circuit has an input to receive the image from the sequence of images and one or more key frames from among the stored key frames selected for the image. This circuit has an output to provide a depth map for the image. The volumetric fusion circuit has an input to receive the depth map for the image and an output to provide a three-dimensional model as a fusion of depth maps received for the sequence of images. 
     In another aspect, a process for generating a three-dimensional model from a sequence of images from a camera involves repeating several steps for each image in the sequence of images. For each image, one or more key frames are selected from the sequence of images. A depth map for the image is determined using the image and the selected one or multiple key frames. The depth map is merged into a volumetric representation of a scene represented in the image. 
     In another aspect, a computer program product includes a computer storage device. Computer program instructions are stored in the computer storage device that, when read from the storage device and processed by a processor or circuit of a computer, instruct the computer to perform a process for generating a three-dimensional model from a sequence of images from a camera. This process involves repeating several steps for each image in the sequence of images. For each image, one or more key frames are selected from the sequence of images. A depth map for the image is determined using the image and the selected key frame. The depth map is merged into a volumetric representation of a scene represented in the image. 
     In some implementations, one or more processing units are housed in a mobile device that incorporates the camera. The depth map for an image can include a measure of depth for each pixel in the image. The pose for an image can include rotation and translation of the camera with respect to a fixed coordinate system. The three-dimensional model can be defined in a virtual volume, wherein an initial pose of the camera is defined at a point in the virtual volume. The three-dimensional model can be defined by representing a surface using a signed distance field in the virtual volume. The three-dimensional model can be output after processing a first and second image from the image sequence, and thus with low latency. 
     In the following description, reference is made to the accompanying drawings which form a part hereof, and in which are shown, by way of illustration, specific example implementations of this technique. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the disclosure. 
    
    
     
       DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of an example device with a single camera from which a three-dimensional model can be reconstructed for use in augmented and/or virtual reality applications using the device. 
         FIG. 2  is a flow chart describing how a user may use a device such as shown in  FIG. 1 . 
         FIG. 3  is a data flow diagram describing a processing pipeline for generating three-dimensional models from an image sequence from a single camera. 
         FIG. 4  is a flow chart describing an example operation of the processing pipeline shown in  FIG. 3 . 
         FIG. 5  is a diagram of example data structures that can be used in the processing pipeline shown in  FIG. 3 . 
         FIG. 6  is a block diagram of an example computer with which components of such a system can be implemented. 
     
    
    
     DETAILED DESCRIPTION 
     A system may use stereoscopic imaging with high resolution cameras or special purpose hardware to construct three-dimensional models of scenes. Such hardware may be significantly more expensive than, and thus, not commonly available for, various consumer electronics. Techniques for generating three-dimensional models using a single camera may use active illumination or structured light, or may employ time of flight cameras. These approaches may be expensive in terms of production cost and power utilization. These techniques may be computationally intensive, use significant amounts of memory, and use several frames of image data before imaging results are available. 
     Consumer mobile devices may have a single camera of relatively low quality, limited memory, and relatively simple processing capability, such as a single general purpose processor or programmable integrated circuit. Consumer mobile devices may lack additional light sources, and may rely on battery power for operation. These mobile device aspects limit imaging techniques difficult on these devices. 
     The following section describes an example device with a single camera from which a three-dimensional model can be reconstructed for use in augmented and/or virtual reality applications using the device. 
     Referring to  FIG. 1 , a mobile device  100  with a single camera  102 , such as a mobile phone, tablet computer, wearable device, or other mobile device, provides an end user with input devices  104 , such as a touch sensor, microphone and the like, and output devices  106 , such as a display and audio speakers. In this example, an augmented reality or virtual reality application  108  receives input data  110  from the input devices  104  and a three-dimensional model  112  of a scene, and provides outputs  114  to the output devices  106 . 
     With a mobile device, camera, memory, processing and power resources are generally limited in comparison to other computers, such as desktops. For example, on the mobile device  100 , there may be a single camera  102  that provides an image sequence  116 . There may be a single processor, limited random access memory, and limited persistent storage, with less capability for expanding such resources. The mobile device also typically is powered by a battery. While a three-dimensional modeling system may be implemented in mobile device  100 , the three-dimensional modeling system may be implemented in other devices such as a desktop computer, public display computer, an on-board computer in a vehicle, or a computer built into an appliance. Devices having limited power, hardware, or computing resources may advantageous include a three-dimensional modeling system as disclosed here. 
     It may be desirable to provide a three-dimensional model construction module  120  that uses limited memory and processing resources and that operates on an image sequence  116  from a single camera  102  on the device  100 . The three-dimensional model construction module  120  generates the three-dimensional model  112 , which can be used, for example, by an augmented reality and/or virtual reality application on the device. Other applications may take advantage of such a three-dimensional model, such as a three-dimensional modeling and/or animation tool. 
     In  FIG. 2 , a flow chart describes how a user interacts with an environment using a device such as shown in  FIG. 1 . A processing pipeline, such as described in  FIG. 3 , which implements the three-dimensional model construction module is activated in step  200 . For example, an application on the device may be activated. In one example, the activation process may include a step of determining a scale of depth, e.g., an initial depth scaling. This determination may be based on input from a sensor, for example, a camera, gyroscope, or proximity sensor. In step  202 , the user and/or a program executing on a device activates the camera so that it starts generating an image sequence. The application that provides the processing pipeline may have a control that allows the user to activate the camera. 
     In step  204 , the user may manipulate the camera in the environment. The user may provide sufficient movement of the camera to allow the processing pipeline to receive a sufficient number of images from different angles of the environment, from which it can compute depth information based on differences between images at different camera poses. For example, the user may walk around an object or scene and point the camera at the object or scene from different directions, locations, or angles. 
     In step  206 , given a sequence of images, the processing pipeline generates a three-dimensional model. The processing pipeline, using the example implementation described below, can begin outputting the model after processing as few as two frames of image data from the camera. The quality of the model improves as more frames of image data are processed. In step  208 , the model can be provided to another application that uses the model, such as an augmented reality or virtual reality application. 
     Having now described an example use of such model construction, an example implementation of a processing pipeline will now be described in connection with  FIGS. 3 through 5 . 
     In this implementation, three components are advantageously combined, with minimal memory requirements, to generate a three-dimensional model with low latency. A high quality model may be achieved by fusion of depth maps of several images over time. One of the components determines a camera pose for each image to identify key frames and selects a key frame for each input image of the image sequence from the camera. Another component computes a depth map for each image by comparing the image to its corresponding one or multiple key frames. Another component performs volumetric fusion of the depth maps for each image into one global volumetric representation. It may be feasible to implement each component to process a batch of images from the sequence of images. Alternatively, the components may be implemented as a processing pipeline, in which each component processes its inputs from the preceding component successively at the rate the images are received from the camera. In this system, a model may be output with reduced latency and then successively improved as additional images are received from the camera. 
     Each component of the processing pipeline, as described below, may be implemented using the combination of a computer program running on a processor or programmable circuit of the device. Alternatively, each component can be implemented using a special purpose processing circuit such as an application-specific integrated circuit (ASIC), that may be part of the device. 
     In  FIG. 3 , the camera  300  provides an image sequence  302  to the first component, a camera pose tracking component  304 . The camera pose tracking component passes through each successive image, as indicated at  306 . The camera pose tracking component also generates key frames  308  and pose data for the key frames  310  that may be stored. Generally, the entire image sequence need not be stored; the key frames and pose data for each key frame may be sufficient. 
     Within the camera pose tracking component, the camera pose is compared to a most recent key frame to determine whether another key frame is to be generated. If the two poses are sufficiently different, then the current frame may be designated as a key frame. 
     Also within the camera pose tracking component, one or multiple key frames for comparing the current frame are selected, as indicated at  312 . The selected key frame may be the most recently used key frame. Alternatively, other selections may be made that involve comparison of the current image and its pose to other key frames and their poses to identify one or multiple key frames which have the largest image overlap with the current frame. This may guarantee a greatest number of matches between pixels when performing depth map estimation, and may ensure that the viewpoints are different in the two views, so that each image provides a novel perspective on the scene and provides useful three-dimensional information. 
     The current image, and an indication of its selected one or multiple key frames, are passed to a depth estimation module  314 . The depth estimation module determines a depth map  316  for the current image based on a comparison of the current image and its corresponding one or multiple key frames. Several techniques may be used for estimating the depth map. Generally, estimating the depth map involves matching every pixel in the current frame to every pixel in one or multiple of the selected key frames. Given a set of matched pixels between these two viewpoints, stereo triangulation is performed to obtain a depth estimate for each pixel. 
     For example, in one implementation, the depth map can be computed using a technique that computes both depth and surface normals. Alternatively, the computation of surface normals may be omitted and techniques for computing depth may be used. Further, the technique may use a Zero Mean Normalized Cross Correlation score (ZNCC) on small patches for cost computation. The ZNCC score compensates for local gain and offset changes, and thus handles large radiometric differences in the input images. Such radiometric changes are likely to occur because the input images are captured at different points in time. By using small patches, computational complexity and edge fattening artifacts are reduced. 
     The depth map  316  from each frame is received by a volumetric fusion module  318  that performs a fusion of the depth map with the current estimate of the three-dimensional model  320 . Several techniques may be used for fusion of the depth map of each frame with the model. 
     For example, in one implementation, volumetric fusion may be performed using a three-dimensional model defined by a data structure as a virtual volume with signed distance fields representing surfaces. The volumetric fusion involves processing the sequence of noisy depth maps from the depth map estimator, and, for each frame, incrementally updating the volume by integrating (or fusing) surface observations into the stored signed distance filed. New data is added into empty regions, and existing data is filtered to remove noise based on the received depth map. The volume is raycast using the current camera pose estimate, marching individual rays through the grid, to find sign changes in the signed distance field (i.e., the zero-crossings) to extract surface points and normals. After several frames, the three-dimensional model begins to converge to a high quality result. 
     Referring now to  FIG. 4 , a flow chart an example operation of the processing pipeline shown in  FIG. 3  will now be described. 
     Upon receiving a next frame in an image sequence from the camera, the pose information for the frame is processed  400 . If the pose information is sufficiently different from other key frames as determined at  402 , this frame can be marked as a key frame and stored. A key frame for comparison with the current frame is then selected  404 . The depth data for the current frame is then computed  406  using the selected key frame. Volumetric fusion is then applied  408  to the depth map to merge it with previously computed depth information. The process repeats  410  for subsequent frames received from the camera. 
     The process described in  FIG. 4  can be performed in a pipelined fashion, such that pose information for one frame is being processed while depth information for the previous frame is being computed, while the depth map for yet another frame is being merged with the three-dimensional model. 
     In the example implementation described above, various data structures are used to manage the data used by the processing pipeline, example implementations of which are shown in  FIG. 5 . 
     The key frames  500  that are stored in storage include the original image data  502  from the camera as well as associated pose information  504  generated by the camera pose estimation module. The pose information  504  can take several forms. An example implementation is to store rotation and translation of the camera with respect to a fixed coordinate system. A current frame and its pose information from the camera tracker may have the same data structure. 
     The depth map  510  output by the depth estimator for a frame includes a map  512 , which is a matrix of depth values with the same x and y dimensions as the image data, and a depth value for each x, y pair or index to the matrix. Other data  514  about the depth map may also be provided. 
     Finally, the three dimensional model  520  output by the volumetric fusion module encodes surfaces implicitly as a signed distance field (SDF). Thus, a virtual volume  522  may be defined by x, y and z coordinates. A list  524  of surfaces is defined over time, with each surface being defined as a signed distance field  526  within the volume. This data structure is initialized with the camera assumed to be at the origin, which is also the center of a virtual volume&#39;s front face. 
       FIG. 6  illustrates an example computer in which three-dimensional modeling techniques may be implemented. This is only one example of a computer and is not intended to suggest any limitation as to the scope of use or functionality of such a computer. The following description is intended to provide a brief, general description of such a computer. The computer can be any of a variety of general purpose or special purpose computing hardware configurations. Examples of well-known computers that may be suitable include, but are not limited to, personal computers, game consoles, set top boxes, hand-held or laptop devices (for example, media players, notebook computers, tablet computers, cellular phones, personal data assistants, voice recorders), server computers, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like. 
     With reference to  FIG. 6 , an example computer  600 , in a basic configuration, includes at least one processing unit  602  and memory  604 . The computer can have multiple processing units  602 . A processing unit  602  can include one or more processing cores (not shown) that operate independently of each other. Additional co-processing units, such as graphics processing unit  620 , also can be provided. Depending on the configuration and type of computer, memory  604  may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. This configuration is illustrated in  FIG. 6  by dashed line  606 . The computer  600  also may include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in  FIG. 6  by removable storage  608  and non-removable storage  610 . 
     A computer storage medium is any medium in which data can be stored in and retrieved from addressable physical storage locations by the computer. Computer storage media includes volatile and nonvolatile, removable and non-removable media. Memory  604 , removable storage  608  and non-removable storage  610  are all examples of computer storage media. Some examples of computer storage media are RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optically or magneto-optically recorded storage device, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices. Computer storage media and communication media are mutually exclusive categories of media. 
     Computer  600  may also contain communications connection(s)  612  that allow the device to communicate with other devices over a communication medium. Communication media typically transmit computer program instructions, data structures, program modules or other data over a wired or wireless substance by propagating a modulated data signal such as a carrier wave or other transport mechanism over the substance. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal, thereby changing the configuration or state of the receiving device of the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio frequency, infrared and other wireless media. Communications connections  612  are devices, such as a wired network interface, wireless network interface, radio frequency transceiver, e.g., Wi-Fi, cellular, long term evolution (LTE) or Bluetooth, etc., transceivers, navigation transceivers, e.g., global positioning system (GPS) or Global Navigation Satellite System (GLONASS), etc., transceivers, that interface with the communication media to transmit data over and receive data from communication media, and may perform various functions with respect to that data. 
     Computer  600  may have various input device(s)  614  such as a keyboard, mouse, pen, camera, touch input device, sensor (e.g., accelerometer or gyroscope), and so on. Output device(s)  616  such as a display, speakers, a printer, and so on may also be included. All of these devices are well known in the art and need not be discussed at length here. Various input and output devices can implement a natural user interface (NUI), which is any interface technology that enables a user to interact with a device in a “natural” manner, free from artificial constraints imposed by input devices such as mice, keyboards, remote controls, and the like. 
     Examples of NUI methods include those relying on speech recognition, touch and stylus recognition, hover, gesture recognition both on screen and adjacent to the screen, air gestures, head and eye tracking, voice and speech, vision, touch, gestures, and machine intelligence, and may include the use of touch sensitive displays, voice and speech recognition, intention and goal understanding, motion gesture detection using depth cameras (such as stereoscopic camera systems, infrared camera systems, and other camera systems and combinations of these), motion gesture detection using accelerometers or gyroscopes, facial recognition, three dimensional displays, head, eye, and gaze tracking, immersive augmented reality and virtual reality systems, all of which provide a more natural interface, as well as technologies for sensing brain activity using electric field sensing electrodes (EEG and related methods). 
     Each component of this system that operates on a computer generally is implemented using one or more computer programs processed by one or more processing units in the computer. A computer program includes computer-executable instructions and/or computer-interpreted instructions, which instructions are processed by one or more processing units in the computer. Generally, such instructions define routines, programs, objects, components, data structures, and so on, that, when processed by a processing unit, instruct the processing unit to perform operations on data, or configure the computer to include various devices or data structures. This computer system may be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer programs may be located in both local and remote computer storage media. 
     Alternatively, or in addition, the functionality described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-programmable Gate Arrays (FPGAs), Program-specific Integrated Circuits (ASICs), Program-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), etc. 
     The terms “article of manufacture”, “process”, “machine” and “composition of matter” in the preambles of the appended claims are intended to limit the claims to subject matter deemed to fall within the scope of patentable subject matter defined by the use of these terms in 35 U.S.C. §101. 
     Any or all of the aforementioned alternate embodiments described herein may be used in any combination desired to form additional hybrid embodiments. It should be understood that the subject matter defined in the appended claims is not necessarily limited to the specific implementations described above. The specific implementations described above are disclosed as examples only.