Patent Description:
<CIT> discusses reconstruction using two projection and a single camera. Multiple projections can be temporally staggered and matched against each other.

<CIT> discusses depth reconstruction using two laser projection units for different patterns and two cameras and triangulates cross-correlated patches.

<CIT> discusses rotating a pattern serves to distinguish it from the previous capture.

<CIT> discusses that VCSELs emit divergent laser light at relatively low power consumption.

<CIT> discusses illumination-based depth reconstruction with two video cameras and a single projector projecting two different patterns. Block matching is performed as well as graph-based or probabilistic approaches as alternatives.

However, for depth cameras operating at relatively low speed (i.e., capturing a low number of frames per second), high frame-to-frame movements in a scene and artifacts such as motion blur make correlations between frames difficult to solve.

The following description is intended to convey a thorough understanding of the present disclosure by providing a number of specific embodiments and details involving estimating a depth map of an environment based on alternating stereo depth images. It is understood, however, that the present disclosure is not limited to these specific embodiments and details, which are examples only, and the scope of the disclosure is accordingly intended to be limited only by the following claims. The invention is defined in independent computer-implemented method claim <NUM> and independent device claim <NUM>.

<FIG> illustrate techniques for estimating a depth map of an environment by an electronic device based on stereo depth images captured by depth cameras having exposure times that are offset from each other in conjunction with illuminators pulsing illumination patterns into the environment so as to support location-based functionality, such as augmented reality (AR) functionality, virtual reality (VR) functionality, visual localization/odometry or other simultaneous localization and mapping (SLAM) functionality, and the like. A first illuminator pulses a first illumination pattern into the environment at a first frequency and phase, while a second illuminator pulses a second illumination pattern into the environment at the first frequency and a second phase. A first depth camera captures depth images of the environment during the times the first illuminator is pulsing the first illumination pattern, and a second depth camera captures depth images of the environment during the times the second illuminator is pulsing the second illumination pattern. In some embodiments, the electronic device dynamically changes the projected patterns over time.

A processor of the electronic device matches small sections (referred to as patches) of the depth images from the first and second cameras to each other and to corresponding patches of one or more immediately preceding depth images of the environment (e.g., a spatio-temporal image patch "cube"). The processor computes a matching cost for each spatio-temporal image patch cube by converting each spatio-temporal image patch into binary codes and defining a cost function between two stereo (left and right) image patches as the difference between the binary codes. The processor minimizes the matching cost to generate a disparity map. The processor optimizes the disparity map by identifying and rejecting outliers using a decision tree with learned pixel offsets and refining subpixels to generate a depth map of the environment. By leveraging the relatively fast framerate of the depth cameras to include previous depth images in computing a matching cost for stereo depth imaging, the electronic device reduces noise in the matching while allowing for smaller spatial windows (patches), which results in better performance along depth discontinuities. In addition, by varying the projected patterns over time, the electronic device minimizes bias effects from stereo matching. By using the decision tree to identify and reject outliers, the electronic device lowers the computation cost otherwise consumed by cross-checking and decouples the computation from the resolution of the images.

<FIG> illustrates an electronic device <NUM> configured to support location-based functionality, such as SLAM, VR, or AR, using depth image data in accordance with at least one embodiment of the present disclosure. The electronic device <NUM> can include a user-portable mobile device, such as a tablet computer, computing-enabled cellular phone (e.g., a "smartphone"), a notebook computer, a personal digital assistant (PDA), a gaming system remote, a television remote, and the like. In other embodiments, the electronic device <NUM> can include another type of mobile device, such as a head-mounted display, single camera, multi-sensor camera, and the like. For ease of illustration, the electronic device <NUM> is generally described herein in the example context of a mobile device, such as a tablet computer or a smartphone; however, the electronic device <NUM> is not limited to these example implementations.

In the depicted example, the electronic device <NUM> includes a plurality of sensors to obtain information regarding a local environment <NUM> of the electronic device <NUM>. The electronic device <NUM> obtains visual information (imagery) for the local environment <NUM> via color (RGB) imaging camera <NUM> and depth cameras <NUM> and <NUM>. In one embodiment, the imaging camera <NUM> is implemented as a wide-angle imaging camera having a fish-eye lens or other wide-angle lens to provide a wide-angle view of the local environment <NUM>. The depth camera <NUM> (also referred to as left depth camera <NUM>), in one embodiment, uses a modulated light illuminator <NUM> (also referred to as left illuminator <NUM>) to project a first modulated light pattern into the local environment, and captures reflections of the first modulated light pattern as it reflects back from objects in the local environment <NUM>. The depth camera <NUM> (also referred to as right depth camera <NUM>), in one embodiment, uses a modulated light illuminator <NUM> (also referred to as right illuminator <NUM>) to project a second modulated light pattern into the local environment, and captures reflections of the second modulating light pattern as it reflects back from objects in the local environment. In some embodiments, the depth cameras <NUM> and <NUM> are implemented as a pair of monochrome infrared (IR) cameras with a bandpass filter. Although depth cameras <NUM> and <NUM> are referred to as left and right cameras in the example embodiment of <FIG>, it will be appreciated that in other embodiments the cameras may be in different configurations and arrangements. It will further be appreciated that both cameras can capture images of the same environment concurrently.

In some embodiments, each of the left illuminator <NUM> and the right illuminator <NUM> emit infrared (IR) light. In some embodiments, each of the left illuminator <NUM> and the right illuminator <NUM> are vertical cavity surface emitting lasers (VCSELs). A VCSEL emits light from a larger surface than a laser, and therefore emits more light while still being safe for eyes. In some embodiments, the left illuminator <NUM> and the right illuminator <NUM> are coupled with suitable masks (not shown) to emit structured light (i.e., modulated light patterns). In some embodiments, these modulated light patterns are temporally-modulated light patterns. The captured reflections of the modulated light patterns are referred to herein as "depth images. " A processor (not shown) of the electronic device <NUM> then may calculate the depths of the objects, that is, the distances of the objects from the electronic device <NUM>, based on the analysis of the depth imagery.

In operation, the left illuminator <NUM> pulses the first illumination pattern into the environment <NUM> at a first frequency and at a first phase, while the right illuminator <NUM> pulses the second illumination pattern into the environment at the first frequency and at a second phase, to minimize interference between the first and second illumination patterns. For example, if each of the left depth camera <NUM> and the right depth camera <NUM> has an exposure time of <NUM> and runs at <NUM> frames per second (fps), and each of the left illuminator <NUM> and the right illuminator <NUM> pulse their respective illumination patterns into the environment for <NUM> pulses synchronized with the left depth camera <NUM> and the right depth camera <NUM>'s exposure times, respectively, there will be a gap of <NUM> between two consecutive frames. Thus, the exposures of the left depth camera <NUM> and the right depth camera <NUM> are temporally offset such that they do not interfere with each other even if they are facing one another while maintaining a frame rate of 210fps. The first and second phases of pulses are dynamically adjustable. In some embodiments, each of the first and second illumination patterns are a regular grid of dots, and the left illuminator <NUM> and right illuminator <NUM> are rotated with respect to each other so that the combination of the two illumination patterns results in a locally unique pattern. In some embodiments, the electronic device <NUM> includes additional illuminators, each mounted at a slightly different angle. The processor (not shown) activates a different subset of illuminators at each frame of the left depth camera <NUM> and the right depth camera <NUM> to generate a varying pattern over time.

The electronic device <NUM> generates depth data based on the detection of spatial features in image data captured by the depth cameras <NUM> and <NUM>. To illustrate, in the depicted example of <FIG> the local environment <NUM> includes a hallway of an office building that includes three corners <NUM>, <NUM>, and <NUM>, a baseboard <NUM>, and an electrical outlet <NUM>. In this example, the depth camera <NUM> captures depth data <NUM> based on reflections of the first modulated light pattern projected by the illuminator <NUM> as it reflects back from objects in the local environment <NUM>, and the depth camera <NUM> captures depth data <NUM> based on reflections of the second modulated light pattern projected by the illuminator <NUM> as it reflects back from objects in the local environment <NUM>. In some embodiments, the electronic device trains or calibrates the processor (not shown) based on images <NUM> of the local environment <NUM> captured by the RGB camera <NUM>.

The processor (not shown) of the electronic device <NUM> estimates the depths of objects in the environment <NUM> via triangulation of corresponding points identified in the depth image <NUM> from the left depth camera <NUM> and the depth image <NUM> from the right depth camera <NUM>, denoted as IL and IR, respectively. To this end, the processor finds for each pixel pL = (x, y) in the left image IL its correspondent pixel pR = (x',y') in the right image IR. Assuming the stereo system to calibrated and rectified, for each matched pair pL and pR, y = y'. The displacement d = x - x' is referred to as disparity. Given the disparity value d for a given pixel, a depth value <MAT> is inversely proportional to d. The quantity b is the baseline of the stereo system and f is the focal length.

The processor computes a matching cost defining a distance or similarity function (also referred to as a correlation function) between patches (small sections) of the depth image <NUM> and the depth image <NUM>. The processor uses the correlation function to find an optimal disparity according to certain criteria, such as lowest distance. In some embodiments, the processor refines disparities to achieve subpixel precision and reject outliers to generate a depth map of the environment <NUM>, as explained further below.

<FIG> is a block diagram of the electronic device <NUM> of <FIG> in accordance with some embodiments. The electronic device <NUM> includes a depth camera controller <NUM> for controlling the left depth camera <NUM> and the right depth camera <NUM>, an illuminator controller <NUM> for controlling the left illuminator <NUM> and the right illuminator <NUM>, and a processor <NUM>. The processor <NUM> includes a matching cost calculator <NUM>, a disparity optimizer <NUM>, a subpixel refiner <NUM>, an outlier identifier <NUM>, and a depth map generator <NUM>.

The depth camera controller <NUM> is a module configured to control the activation and exposure times of the left depth camera <NUM> and the right depth camera <NUM>. The depth camera controller <NUM> adjusts the frame rate, exposure time, and phase of the left depth camera <NUM> and the right depth camera <NUM>. In some embodiments, the depth camera controller <NUM> ensures that the left depth camera <NUM> and the right depth camera <NUM> have non-overlapping exposure times. In some embodiments, the depth camera controller <NUM> coordinates the frame rate, exposure time, and phase of the left depth camera <NUM> and the right depth camera <NUM> in coordination with the illuminator controller <NUM>.

The illuminator controller <NUM> is a module configured to control the activation and pulse durations of, and illumination patterns projected by, the left illuminator <NUM> and the right illuminator <NUM>. The illuminator controller <NUM> activates the left illuminator <NUM> to pulse a first illumination pattern into the environment at a frequency and phase matched to the frequency and phase of the left depth camera <NUM>, and activates the right illuminator <NUM> to pulse a second illumination pattern into the environment at a frequency and phase matched to the frequency and phase of the right depth camera <NUM>. Thus, during a time when the left illuminator <NUM> pulses the first illumination pattern into the environment, the left depth camera <NUM> captures a depth image, and during the time when the right illuminator <NUM> pulses the second illumination pattern into the environment, the right depth camera <NUM> captures a depth image. In some embodiments, the time when the left illuminator <NUM> pulses the first illumination pattern and time when the right illuminator <NUM> pulses the second illumination pattern are non-overlapping.

The processor <NUM> is configured to receive depth images (not shown) from the left depth camera <NUM> (the left image) and the right depth camera <NUM> (the right image). In some embodiments, the processor is further configured to receive images from the RGB camera (not shown). The matching cost calculator <NUM> is a module configured to compute a matching cost for patches (sections) of the left and right image frames. The patch size must be large enough to uniquely identify a pixel based on the texture (from the illumination pattern) in its surrounding area. Given an image patch xL in the left image and an image patch xR in the right image of size n, the matching cost calculator <NUM> computes a matching cost based on their appearance that is independent of the patch (window) size n. The matching cost calculator <NUM> defines a function b = sign (xW) that remaps every image patch x in a binary representation b ∈ {<NUM>,<NUM>}k using k hyperplanes W ∈ Rn×k. In order to have a O (<NUM>) mapping that is independent of the signal dimensionality n, the matching cost calculator <NUM> ensures that the hyperplanes W are sparse. The sparsity enforces that the matching cost calculator <NUM> only has to access a small subset of pixels inside each patch, which reduces the compute and memory accesses. The matching cost calculator <NUM> learns a binary mapping signal sign (xW) that preserves the original signal x as much as possible.

In some embodiments, the matching cost calculator <NUM> computes an inverse linear mapping Z that reconstructs the original space x from the binary codes b. Thus, the matching cost calculator <NUM> learns a set of sparse hyperplanes W ∈ Rn×k and an inverse map Z ∈ Rk×n that minimizes the equation <MAT> where X ∈ Rm×n is a matrix of training examples. The matching cost calculator <NUM> uses the ℓ<NUM> - norm |W|<NUM> to induce sparsity on the hyperplanes W, making the linear mapping independent of the patch dimension n. In some embodiments, the matching cost calculator <NUM> optimizes the equation using an alternate minimization.

The matching cost calculator <NUM> extends the linear mapping to spatio-temporal patches based on one or more depth images captured immediately prior to the capture of the left and right images. The matching cost calculator <NUM> assumes that the motion between subsequent image frames at time t and time t + <NUM> is very small, given the high frame rate of high speed depth cameras <NUM>, <NUM>. Based on the assumed small amount of motion from one frame to the next, the matching cost calculator <NUM> uses a straight spatio-temporal image volume x (as shown in depth images <NUM> of <FIG>) with dimensions n = P × P × F, where P is the spatial window size and F is a temporal buffer of F frames. Because the mapping W is sparse, the mapping does not depend on the temporal buffer size F or on the spatial resolution P. By changing the illumination patterns projected by the left illuminator <NUM> and the right illuminator <NUM> over time, the electronic device <NUM> changes the appearance of the patch over time in order to ensure that the information added across multiple frames is not redundant. By matching with a spatio-temporal window, the matching cost calculator <NUM> reduces noise in matching, allows for smaller spatial windows, and removes bias effects.

At runtime, the matching cost calculator <NUM> converts each spatio-temporal image patch x to k = <NUM> binary codes b = sign(xW). The matching cost calculator <NUM> defines the cost function between two image patches xL and xR as the Hamming distance between the codes bL and bR. The matching cost calculator <NUM> obtains the computations in <NUM>(<NUM>) and the computations are independent of the patch size n.

The disparity optimizer <NUM> is a module configured to identify the image patches of the left and right image frames with the lowest matching cost to generate a disparity map indicating disparities between pixels of the patches of the left and right image frames. In some embodiments, to find the image patches with the lowest matching cost without evaluating all possible disparity labels dk, the disparity optimizer <NUM> initializes the depth image by testing random disparities for each pixel and selecting the disparity with the smallest Hamming distance in the binary space. For example, in some embodiments, the disparity optimizer <NUM> tests <NUM> random disparities for each pixel. Thus, for a pixel pi with a current lowest disparity di, the disparity optimizer <NUM> tests all disparity labels in a <NUM> × <NUM> neighborhood <IMG> and selects the one with the best cost. The disparity optimizer <NUM> defines the cost function as <MAT> where <MAT> is the Hamming distance between the codes at the pixel p in the left image and the codes computed at the location p + d in the right image, wherein a pixel p is defined only by its x component and p + d is a shift along that dimension. The disparity optimizer <NUM> uses the term S(dk, d) = max(τ, |dk - d| to enforce smoothness among neighboring pixels. In some embodiments, the disparity optimizer <NUM> considers a very small local neighborhood <IMG> = <NUM> × <NUM>, such that it can easily solve the cost function equation by enumerating all the possible solutions in the <NUM> × <NUM> window and selecting the best one. In some embodiments, the disparity optimizer <NUM> re-iterates the optimization multiple times until it reaches convergence. The disparity optimizer <NUM> generates a disparity map (not shown) based on the lowest cost calculated for each pixel.

In some embodiments, the disparity optimizer <NUM> further exploits high frame rate data in the initialization step. For each pixel p at time t, the disparity optimizer <NUM> tests the pixel's previous disparity at time t - <NUM>. If the Hamming distance is lower than all the random disparities, the disparity optimizer <NUM> uses the previous values to initialize the iterative optimization. Given a 210fps depth camera, many of the pixels will typically have the same disparity between two consecutive frames.

The subpixel refiner <NUM> is a module configured to achieve subpixel precision using a parabola interpolation. Given a pixel p with a disparity d, the subpixel refiner <NUM> fits a parabola by considering the disparities d - <NUM> and d + <NUM>. The subpixel refiner <NUM> computes the Hamming distances of the binary codes for the disparities d, d - <NUM>, and d + <NUM> and fits a quadratic function. The subpixel refiner <NUM> picks as the optimal value of d the best disparity d* that lies at the global minimum of the quadratic function. In some embodiments, the subpixel refiner <NUM> repeats the parabola fitting at the end of each iteration of the optimization performed by the disparity optimizer <NUM> and for every pixel.

The outlier identifier <NUM> is a module configured to identify and remove invalid pixels directly from the data. The outlier identifier <NUM> trains by cross-checking a collection of disparity maps of the environment and calculating a weighted median against an RGB image of the environment. The outlier identifier <NUM> synchronizes and calibrates the left depth camera <NUM> and the right depth camera <NUM> against the RGB camera (not shown). The outlier identifier <NUM> marks each pixel as either "valid" or "invalid" based on cross-checking the depth images against the RGB images and a weighted median filter. The outlier identifier <NUM> then learns a function that decides to either invalidate or accept a given disparity. In some embodiments, to keep the computation low and independent of the image resolution, the outlier identifier <NUM> uses a decision tree to determine pixel validity.

The outlier identifier <NUM> populates a node in the decision tree with two learned pixel offsets u = (Δx, Δy) and v = (Δx', Δy') and a threshold value τ. When evaluating a pixel at position p = (x,y), the decision tree of the outlier identifier <NUM> decides where to route a particular example based on the sign of I(p + u) - I(p + v) > τ, where I(p) is the intensity value of a pixel p. In some embodiments, at training time, the outlier identifier <NUM> samples <NUM> possible split parameters δ = (u, v, τ) for the current node. Each δ induces a split on the set S of the data into left SL(δ) and right SR(δ) child sets. The outlier identifier <NUM> selects the set of parameters δ that maximizes the Information Gain defined as: <MAT> where the entropy E(S) is the Shannon entropy of the empirical distribution p(valid|S) of the class label "valid" in S. Each leaf node contains a probability of p(valid|p, I) and the outlier identifier <NUM> invalidates pixels when this quantity is less than <NUM>.

The depth map generator <NUM> is a module configured to generate a three-dimensional (3D) point cloud (referred to as a depth map) for each image frame pair from the left depth camera <NUM> and the right depth camera <NUM> based on the disparity map generated by the disparity optimizer <NUM>. In some embodiments, the depth map generator <NUM> further bases the depth map on the subpixel refinements identified by the subpixel refiner <NUM>. In some embodiments, the depth map generator <NUM> additionally bases the depth map on the validity determinations made by the outlier identifier <NUM>. The depth map can be used as an input for efficient, low latency, high quality computer vision algorithms including scene and object scanning, non-rigid tracking, and hand tracking.

<FIG> illustrates the illuminators <NUM> and <NUM> of the electronic device <NUM> alternately projecting two illumination patterns <NUM> and <NUM> into the environment <NUM> in accordance with some embodiments. In some embodiments, the illumination patterns <NUM>, <NUM> are regular dot grids rotated with respect to each other such that their combination results in a locally unique pattern. The left illuminator <NUM> pulses a first illumination pattern <NUM> into the environment <NUM> at a first frequency and at a first phase, while the right illuminator <NUM> pulses a second illumination pattern <NUM> into the environment <NUM> at the first frequency and at a second phase offset from the first phase. Thus, the left illuminator <NUM> pulses the illumination pattern <NUM> during a first time t and the right illuminator <NUM> pulses the illumination pattern <NUM> during a second time t + <NUM>. In some embodiments, the illuminator controller (not shown) varies the first and second illumination patterns over time to minimize depth bias from the reflected patterns.

The depth camera controller (not shown) activates the left depth camera <NUM> in coordination with the pulsing of the left illuminator <NUM> and activates the right depth camera <NUM> in coordination with the pulsing of the right illuminator <NUM>. Thus, in some embodiments, the depth camera controller activates the left depth camera <NUM> to capture a depth image during the time t, and activates the right depth camera <NUM> to capture a depth image during the time t + <NUM> to produce a set of depth images <NUM>. By alternately pulsing the left and right illuminators <NUM>, <NUM> and alternately activating the left and right depth cameras <NUM>, <NUM>, the electronic device <NUM> avoids interference between the illuminators <NUM>, <NUM> and the depth cameras <NUM>, <NUM>. In some embodiments, the depth camera controller and the illuminator controller adjust the phases of the illuminators <NUM>, <NUM> and the depth cameras <NUM>, <NUM> to minimize interference.

<FIG> is a diagram illustrating the matching cost calculator <NUM> of <FIG> matching patches <NUM>, <NUM>, <NUM> from each of a depth image <NUM> from a first depth camera, a depth image <NUM> from a second depth camera, and a previous depth image <NUM> in accordance with some embodiments. In the illustrated example, each of the depth images <NUM>, <NUM>, <NUM> illustrates a ball <NUM> rolling along a hallway toward the depth cameras. The matching cost calculator <NUM> computes a binary descriptor (code) for each pixel from the spatio-temporal neighborhood within patches <NUM>, <NUM>, and <NUM> and defines a cost that pixels in the depth images <NUM> and <NUM> are originating from the same scene point as the Hamming distance of the binary codes.

<FIG> is a flow diagram illustrating a method <NUM> of estimating a depth map based on captured depth images in accordance with some embodiments. At block <NUM>, the processor <NUM> of the electronic device <NUM> receives a left depth image, a right depth image, and the depth image captured immediately prior to the capture of the left and right depth images. At block <NUM>, the matching cost calculator <NUM> computes a matching cost for each patch of the left and right depth images. At block <NUM>, the disparity optimizer minimizes the matching cost to generate a disparity map. At block <NUM>, the subpixel optimizer <NUM> refines subpixel precision using a parabola interpolation and the outlier identifier <NUM> identifies and removes invalid pixels from the disparity map. At block <NUM>, the depth map generator <NUM> generates a 3D point cloud based on the refined disparity map.

Such storage media can include, but is not limited to, optical media (e.g., compact disc (CD), digital versatile disc (DVD), Blu-Ray disc), magnetic media (e.g., floppy disc , magnetic tape, or magnetic hard drive), volatile memory (e.g., random access memory (RAM) or cache), non-volatile memory (e.g., read-only memory (ROM) or Flash memory), or microelectromechanical systems (MEMS)-based storage media.

Claim 1:
A computer-implemented method comprising:
pulsing, at a first illuminator (<NUM>) of an electronic device (<NUM>), a first illumination pattern (<NUM>) into an environment of the electronic device at a first phase and a first frequency;
pulsing, at a second illuminator (<NUM>) of the electronic device, a second illumination pattern (<NUM>) into the environment of the electronic device at a second phase and the first frequency, wherein the second illumination pattern (<NUM>) is rotated with respect to the first illumination pattern (<NUM>);
dynamically adjusting the first and second phases;
capturing, at a first camera (<NUM>) of the electronic device, reflections of the first illumination pattern (<NUM>) as a first series of images of the environment at the first phase and the first frequency;
capturing, at a second camera (<NUM>) of the electronic device, reflections of the second illumination pattern (<NUM>)
as a second series of images of the environment at the second phase and the first frequency;
comparing, at a processor (<NUM>) of the electronic device, a first patch (<NUM>) of a first image (<NUM>) of the first series of images to a second patch (<NUM>) of a second image (<NUM>) of the second series of images and at least one patch of each of one or more images captured by the first and/or second cameras (<NUM>, <NUM>) immediately prior to the first image, wherein each patch comprises a plurality of pixels;
computing a cost function for the compared patches;
generating a disparity map indicating disparities between corresponding pixels of corresponding patches of the first image and the second image based on the cost function; and
refining the disparities of the disparity map to generate an estimated depth map of the environment.