PATENT DOCUMENT

Publication Number: US-9348423-B2
Application Number: US-201414467074-A
Country: US
Kind Code: B2

Title: Integrated processor for 3D mapping

Abstract:
A device for processing data includes a first input port for receiving color image data from a first image sensor and a second input port for receiving depth-related image data from a second image sensor. Processing circuitry generates a depth map using the depth-related image data. At least one output port conveys the depth map and the color image data to a host computer.

Claims:
The invention claimed is: 
     
       1. A device for processing data, comprising:
 a first input configured to receive, from a first image sensor, color image data comprising a first array of color image pixels; 
 a second input configured to receive, from a second image sensor, depth-related image data; and 
 processing circuitry, which is configured to process the depth-related image data so as to generate a depth map comprising a second array of depth pixels with respective depth values, and to register the depth map with the color image data by incrementally computing and applying different, respective shifts between the depth pixels and the color image pixels responsively to the depth values, using an incremental fitting process, such that the shifts of the depth pixels within a line of the depth map are computed as a function of a preceding pixel shift. 
 
     
     
       2. The device according to  claim 1 , and comprising at least one output configured to convey the registered depth map and color image data to a host processor. 
     
     
       3. The device according to  claim 2 , wherein the first and second inputs, the processing circuitry and the at least one output are integrated circuit components, which are fabricated on a single semiconductor substrate. 
     
     
       4. The device according to  claim 2 , wherein the at least one output comprises a single port, which is coupled to convey the depth map and the color image data to the host processor as a single data stream in a synchronized, multiplexed format. 
     
     
       5. The device according to  claim 2 , wherein the processing circuitry is configured to compress the depth map and the color image data for output to the host processor. 
     
     
       6. The device according to  claim 1 , wherein the processing circuitry is configured to compute the respective shifts for the pixels on the fly, while receiving the depth values, without storing the entire depth map in the device. 
     
     
       7. The device according to  claim 1 , wherein the depth-related image data comprise an image of a pattern that is projected onto an object, and wherein the processing circuitry is configured to generate the depth map by measuring shifts in the pattern. 
     
     
       8. Apparatus for imaging, comprising:
 a first image sensor, which is configured to capture and output a color image of an object, the color image comprising a first array of color image pixels; 
 a second image sensor, which is configured to capture and output depth-related image data with respect to the object; and 
 a processing device, which is coupled to receive the color image data from the first image sensor and to receive the depth-related image data from the second image sensor, and which is configured to process the depth-related image data so as to generate a depth map comprising a second array of depth pixels with respective depth values, and to register the depth map with the color image data by incrementally computing and applying different, respective shifts between the depth pixels and the color image pixels responsively to the depth values, using an incremental fitting process, such that the shifts of the depth pixels within a line of the depth map are computed as a function of a preceding pixel shift. 
 
     
     
       9. The apparatus according to  claim 8 , and comprising a host processor, wherein the processing device comprises at least one output that is coupled to convey the depth map and the color image data to the host processor. 
     
     
       10. The apparatus according to  claim 8 , and comprising an illumination subassembly, which is configured to project a pattern onto the object, wherein the depth-related image data comprise an image of the pattern on the object, and wherein the processing device is configured to generate the depth map by measuring shifts in the pattern. 
     
     
       11. The device according to  claim 8 , wherein the processing device is configured to compute the respective shifts for the pixels on the fly, while receiving the depth values, without storing the entire depth map in the device. 
     
     
       12. A method for processing data, comprising:
 receiving in a processing device color image data, comprising a first array of color image pixels, from a first image sensor; 
 receiving in the processing device depth-related image data from a second image sensor; 
 generating in the processing device, using the depth-related image data, a depth map comprising a second array of depth pixels with respective depth values; and 
 registering the depth map with the color image data by incrementally computing and applying different, respective shifts between the depth pixels and the color image pixels responsively to the depth values, using an incremental fitting process, such that the shifts of the pixels within a line of the depth map are computed as a function of a preceding pixel shift. 
 
     
     
       13. The method according to  claim 12 , and comprising conveying the registered depth map and color image data via an output to a host processor. 
     
     
       14. The method according to  claim 12 , wherein computing the respective shifts comprises calculating the respective shifts for the pixels on the fly, while receiving the depth values, without storing the entire depth map while calculating the respective shifts.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of U.S. patent application Ser. No. 13/874,562, filed May 1, 2013 (now U.S. Pat. No. 8,848,039), which is a continuation of U.S. patent application Ser. No. 12/397,362 (now U.S. Pat. No. 8,456,517), which claims the benefit of U.S. Provisional Patent Application 61/079,254, filed Jul. 9, 2008, which is incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to methods and systems for three-dimensional (3D) mapping, and specifically to processing devices for generation and processing of 3D mapping data. 
     BACKGROUND OF THE INVENTION 
     Various methods are known in the art for optical 3D mapping, i.e., generating a 3D profile of the surface of an object by processing an optical image of the object. This sort of 3D profile is also referred to as a depth map or depth image, and 3D mapping is also referred to as depth mapping. 
     Some methods are based on projecting a laser speckle pattern onto the object, and then analyzing an image of the pattern on the object. For example, PCT International Publication WO 2007/043036, whose disclosure is incorporated herein by reference, describes a system and method for object reconstruction in which a coherent light source and a generator of a random speckle pattern project onto the object a coherent random speckle pattern. An imaging unit detects the light response of the illuminated region and generates image data. Shifts of the pattern in the image of the object relative to a reference image of the pattern are used in real-time reconstruction of a 3D map of the object. Further methods for 3D mapping using speckle patterns are described, for example, in PCT International Publication WO 2007/105205, whose disclosure is incorporated herein by reference. 
     Other methods of optical 3D mapping project different sorts of patterns onto the object to be mapped. For example, PCT International Publication WO 2008/120217, whose disclosure is incorporated herein by reference, describes an illumination assembly for 3D mapping that includes a single transparency containing a fixed pattern of spots. A light source transilluminates the transparency with optical radiation so as to project the pattern onto an object. An image capture assembly captures an image of the pattern on the object, and the image is processed so as to reconstruct a 3D map of the object. 
     As a further example, PCT International Publication WO 93/03579 describes a 3D vision system in which one or two projectors establish structured light comprising two sets of parallel stripes having different periodicities and angles. As another example, U.S. Pat. No. 6,751,344 describes a method for optically scanning a subject in which the subject is illuminated with a matrix of discrete two-dimensional image objects, such as a grid of dots. Other methods involve projection of a grating pattern, as described, for example, in U.S. Pat. No. 4,802,759. The disclosures of the above-mentioned patents and publications are incorporated herein by reference. 
     SUMMARY OF THE INVENTION 
     Embodiments of the present invention that are described hereinbelow provide devices and methods for processing of image data for 3D mapping. 
     In accordance with an embodiment of the present invention, a device for processing data includes a first input port for receiving color image data from a first image sensor and a second input port for receiving depth-related image data from a second image sensor. Processing circuitry generates a depth map using the depth-related image data, and at least one output port conveys the depth map and the color image data to a host computer. 
     In a disclosed embodiment, the first and second input ports, the processing circuitry and the at least one output port are integrated circuit components, which are fabricated on a single semiconductor substrate. 
     In some embodiments, the at least one output port includes a single port and is coupled to convey the depth map and the color image data to the host computer as a single data stream in a multiplexed format. Typically, the processing circuitry is configured to synchronize the depth map with the color image data in the single data stream. Optionally, the device includes a third input port for receiving audio information, wherein the processing circuitry is configured to incorporate the audio information together with the depth map and the color image data into the single data stream for conveyance to the host computer via the single port. In one embodiment, the single port includes a Universal Serial Bus (USB) port. 
     In disclosed embodiments, the processing circuitry is configured to register the depth map with the color image data. The depth map includes an array of pixels with respective depth values, and the processing circuitry is typically configured to compute respective shifts for the pixels responsively to the depth values, and to apply the respective shifts to the pixels in the depth map in order to register the depth map with the color image data. In one embodiment, the processing circuitry is configured to compute the respective shifts incrementally, using an incremental fitting process, such that the shifts of the pixels within a line of the depth map are computed as a function of a preceding pixel shift. Typically, the processing circuitry is configured to compute the respective shifts for the pixels on the fly, while receiving the depth values, without storing the entire depth map in the device. 
     In some embodiments, the processing circuitry is configured to compress the depth map and the color image data for transmission to the host via the at least one output port. In one embodiment, the processing circuitry is configured to apply a process of lossless compression to the depth map and the color image data. 
     In a disclosed embodiment, the depth-related image data include an image of a pattern that is projected onto an object, and the processing circuitry is configured to generate the depth map by measuring shifts in the pattern relative to a reference image. 
     There is also provided, in accordance with an embodiment of the present invention, apparatus for imaging, including a first image sensor, which is configured to capture and output a color image of an object, and a second image sensor, which is configured to capture and output depth-related image data with respect to the object. A processing device includes a first input port for receiving the color image data from the first image sensor and a second input port for receiving the depth-related image data from the second image sensor, as well as processing circuitry, for generating a depth map using the depth-related image data, and at least one output port for conveying the depth map and the color image data to a host computer. 
     Optionally, the apparatus includes an audio sensor, wherein the processing device includes a third input port for receiving audio information from the audio sensor, and wherein the processing circuitry is configured to convey the audio information together with the depth map and the color image data to the host computer via the at least one output port. 
     In a disclosed embodiment, the apparatus includes an illumination subassembly, which is configured to project a pattern onto the object, wherein the depth-related image data include an image of the pattern on the object, and the processing circuitry is configured to generate the depth map by measuring shifts in the pattern relative to a reference image. 
     There is additionally provided, in accordance with an embodiment of the present invention, a method for processing data, including receiving color image data from a first image sensor via a first input port and receiving depth-related image data from a second image sensor via a second input port. A depth map is generated using the depth-related image data, and the depth map and the color image data are conveyed via an output port to a host computer. 
     The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which: 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic, pictorial illustration of a system for 3D mapping, in accordance with an embodiment of the present invention; 
         FIG. 2  is a schematic top view of an imaging assembly, in accordance with an embodiment of the present invention; 
         FIGS. 3A and 3B  are block diagrams of a processing device, in accordance with an embodiment of the present invention; 
         FIG. 4  is a block diagram that schematically shows elements of a depth processor, in accordance with an embodiment of the present invention; 
         FIG. 5  is a block diagram that schematically shows details of a registration engine, in accordance with an embodiment of the present invention; 
         FIGS. 6A and 6B  are block diagrams that schematically show details of a coordinate calculation circuit, in accordance with an embodiment of the present invention; and 
         FIG. 7  is a block diagram that schematically illustrates a compression circuit, in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     System Overview 
       FIG. 1  is a schematic, pictorial illustration of a system  20  for 3D mapping and imaging, in accordance with an embodiment of the present invention. In this example, an imaging assembly  24  is configured to capture and process 3D maps and images of a user  22 . This information may be used by a host computer  26  as part of a 3D user interface, which enables the user to interact with games and other applications running on the computer. (This sort of functionality is described, for example, in U.S. patent application Ser. No. 12/352,622, filed Jan. 13, 2009, whose disclosure is incorporated herein by reference.) This particular application of system  20  is shown here only by way of example, however, and the mapping and imaging capabilities of system  20  may be used for other purposes, as well, and applied to substantially any suitable type of 3D object. 
     In the example shown in  FIG. 1 , imaging assembly  24  projects a pattern of optical radiation onto the body (or at least parts of the body) of user  22 , and captures an image of the pattern that appears on the body surface. The optical radiation that is used for this purpose is typically in the infrared (IR) range. A processing device in assembly  24 , which is described in detail hereinbelow, processes the image of the pattern in order to generate a depth map of the body, i.e., an array of 3D coordinates, comprising a depth (Z) coordinate value of the body surface at each point (X,Y) within a predefined area. (In the context of an array of image-related data, these (X,Y) points are also referred to as pixels.) In the embodiments that are described hereinbelow, the processing device computes the 3D coordinates of points on the surface of the user&#39;s body by triangulation, based on transverse shifts of the spots in the pattern, as described in the above-mentioned PCT publications WO 2007/043036, WO 2007/105205 and WO 2008/120217. Alternatively, system  20  may implement other methods of 3D mapping, using single or multiple cameras or other types of sensors, as are known in the art. 
     In addition, imaging assembly  24  captures color (2D) images of the user and may also receive audio input. The imaging assembly registers and synchronizes the depth maps with the color images, and generates a data stream that includes the depth maps and image data (and possibly the audio data, as well) for output to computer  26 . In some embodiments, as described hereinbelow, the depth maps, color images, and possibly the audio data are integrated into a single data stream, which is output to the computer via a single port, for example, a Universal Serial Bus (USB) port. 
     Computer  26  processes the data generated by assembly in order to extract 3D image information. For example, the computer may segment the depth map in order to identify the parts of the body of user  22  and find their 3D locations. Computer  26  may use this information in driving an output device, such as a display  28 , typically to present 3D image information and/or user interface elements that may be controlled by movements of parts of the user&#39;s body. Generally, computer  26  comprises a general-purpose computer processor, which is programmed in software to carry out these functions. The software may be downloaded to the processor in electronic form, over a network, for example, or it may alternatively be provided on tangible media, such as optical, magnetic, or electronic memory media. 
     As another alternative, the processing functions that are associated here with computer  26  may be carried out by a suitable processor that is integrated with display  28  (in a television set, for example) or with any other suitable sort of computerized device, such as a game console or media player. 
       FIG. 2  is a schematic top view of imaging assembly  24 , in accordance with an embodiment of the present invention. Here the X-axis is taken to be the horizontal direction along the front of assembly  24 , the Y-axis is the vertical direction (into the page in this view), and the Z-axis extends away from assembly  24  in the general direction of the object being imaged by the assembly. 
     For 3D mapping, an illumination subassembly  30  illuminates the object with an appropriate pattern, such as a speckle pattern. For this purpose, subassembly  30  typically comprises a suitable radiation source  32 , such as a diode laser, LED or other light source, and optics, such as a diffuser  34  or a diffractive optical element, for creating the pattern, as described in the above-mentioned PCT publications. A depth image capture subassembly  36  captures an image of the pattern on the object surface. Subassembly  36  typically comprises objective optics  38 , which image the object surface onto a detector  40 , such as a CMOS image sensor. 
     As noted above, radiation source  32  typically emits IR radiation, although other radiation bands, in the visible or ultraviolet range, for example, may also be used. Detector  40  may comprise a monochrome image sensor, without an IR-cutoff filter, in order to detect the image of the projected pattern with high sensitivity. To enhance the contrast of the image captured by detector  40 , optics  38  or the detector itself may comprise a bandpass filter, which passes the wavelength of radiation source  32  while blocking ambient radiation in other bands. 
     A color image capture subassembly  42  captures color images of the object. Subassembly  42  typically comprises objective optics  44 , which image the object surface onto a detector  46 , such as a CMOS color mosaic image sensor. Optics  44  or detector  46  may comprise a filter, such as an IR-cutoff filter, so that the pattern projected by illumination subassembly  30  does not appear in the color images captured by detector  46 . 
     Optionally, a microphone  48  captures audio input, such as voice commands uttered by user  22 . 
     A processing device  50  receives and processes image and audio inputs from subassemblies  36  and  42  and from microphone  48 . Details of these processing functions are presented hereinbelow with reference to the figures that follow. Briefly put, processing device  50  compares the image provided by subassembly  36  to a reference image of the pattern projected by subassembly  30  onto a plane  54 , at a known distance D srs  from assembly  24 . (The reference image may be captured as part of a calibration procedure and stored in a memory  52 , such as a flash memory, for example.) The processing device matches the local patterns in the captured image to those in the reference image and thus finds the transverse shift for each pixel  56 , or group of pixels, within plane  54 . Based on these transverse shifts and on the known distance D cc  between the optical axes of subassemblies  30  and  36 , the processing device computes a depth (Z) coordinate for each pixel. 
     Processing device  50  synchronizes and registers the depth coordinates in each such 3D map with appropriate pixels in the color images captured by subassembly  42 . The registration typically involves a shift of the coordinates associated with each depth value in the 3D map. The shift includes a static component, based on the known distance D cc  between the optical axes of subassemblies  36  and  42  and any misalignment between the detectors, as well as a dynamic component that is dependent on the depth coordinates themselves. The registration process is describes in detail hereinbelow. 
     After registering the depth maps and color images, processing device  50  outputs the depth and color data via a port, such as a USB port, to host computer  26 . The output data may be compressed, as described hereinbelow, in order to conserve bandwidth. As noted above, the audio information provided by microphone  28  may also be synchronized and output together with the depth and color data to computer  26 . 
     Processing Device Architecture 
       FIG. 3  (consisting of  FIGS. 3A and 3B ) is a block diagram that schematically shows functional elements of processing device  50 , in accordance with an embodiment of the present invention. Device  50  may be fabricated as a dedicated integrated circuit, on a single semiconductor substrate, with interfaces to the other components of assembly  24  and a USB port to computer  26  as described above. This sort of implementation is useful in minimizing the cost, size and power consumption of assembly  24 . Alternatively, device  50  may be implemented using a number of separate circuit components. Device  50  may include other interfaces, as well, including data and control interfaces to a “thin” host  60 , such as a special-purpose multimedia application processor. 
     The components of device  50  are described hereinbelow in detail as an example of a possible implementation of the principles of the present invention. Further details of this implementation are presented in the above-mentioned provisional patent application. Alternative implementations will be apparent to those skilled in the art on the basis of the present description and are considered to be within the scope of the present invention. For instance, although the embodiment described hereinbelow uses dedicated hardware processing components, some or all of the processing functions in question may be performed in software by a general-purpose programmable processor with suitable interfaces. The software for this purpose may be downloaded to the processor in electronic form, over a network, for example. Alternatively or additionally, the software may be stored on tangible computer-readable media, such as optical, magnetic, or electronic memory. 
     In the present example, device  50  comprises the following components: 
     A depth processor  62  processes the information captured by depth image capture subassembly  36  in order to generate a depth map. Processor  62  uses dedicated memory space in a memory  130 . This memory can also be accessed by a controller  104 , which is described hereinbelow, but typically not by host computer  26 . Rather, processor  62  may be programmed by the host computer via an application program interface (API). 
     Depth processor  62  receives input video data from detector  40  via a depth CMOS sensor interface  64 . The depth processor processes the video data in order to generate successive depth maps, i.e., frames of depth data, as is described in detail hereinbelow with reference to the figures that follow. The depth processor loads these data into a depth first-in-first-out (FIFO) memory  66  in a USB FIFO unit  68 . 
     In parallel with the depth input and processing, a color processing block  72  receives input color video data from detector  46  via a color CMOS sensor interface  70 . Block  72  converts the raw input data into output frames of RGB video data, and loads these data into a RGB FIFO memory  74  in unit  68 . Alternatively, block  72  may output the video data in other formats, such as YUV or Bayer mosaic format. 
     In addition, audio signals from microphone  48  are digitized by an analog/digital converter (ADC)  76 . The resulting digital audio samples are then conveyed by an audio interface  78  to an audio FIFO memory  80  in unit  68 . In the example shown in  FIG. 3A , interface  78  comprises an Integrated Interchip Sound (I2S) bus receiver. 
     USB FIFO unit  68  acts as a buffer level between the various data suppliers and a USB controller  86 . Unit  68  packs and formats the various data types according to different classes (such as a USB video class and a USB audio class), and also serves to prevent data loss due to USB bandwidth glitches. It arranges the data into USB packets according to the USB protocol and format prior to transferring them to the USB controller. 
     A high-bandwidth bus, such as an Advanced High-performance Bus (AHB) matrix  82 , is used to carry data between the components of device  50 , and specifically for conveying data from USB FIFO unit  68  to USB controller  86  for transfer to host computer  26 . (AHB is a bus protocol promulgated by ARM Ltd., of Cambridge, England.) When there are packets ready in FIFO unit  68  and space available in the internal memory of USB controller  86 , the USB controller uses direct memory access (DMA) to read data from FIFO memories  66 ,  74  and  80  via an AHB slave module  84  and AHB matrix  82 . The USB controller multiplexes the color, depth and audio data into a single data stream for output via USB interface to host computer  26 . 
     For the purpose of USB communications, device  50  comprises a USB physical layer interface (PHY)  88 , which may be operated by USB controller  86  to communicate via a suitable USB cable with a USB port of host computer  26 . The timing of USB PHY  88  is controlled by a crystal oscillator  92  and a phase-locked loop (PLL)  94 , as is known in the art. Alternatively, USB controller  86  may optionally communicate with the host computer via a USB 2.0 Transceiver Macrocell Interface (UTMI) and an external PHY  90 . 
     By the same token, an external ADC  96  may optionally be used to digitize the audio signals generated by microphone  48 . A 2:1 switch  98  selects the source of digital audio data to be input to I2S receiver  78 . 
     The I2S receiver may also output audio data directly to thin host  60  via an audio output interface  100 , in case the thin host is not configured (in distinction to host computer  26 ) to receive the audio data together with the color and depth image data via a single serial bus. In this case, the RGB and depth (RGBD) data are output to the thin host via a separate RGBD interface  102 . Alternatively, for some applications, interface  102  may output only the depth data to thin host  60 . 
     Controller  104  is responsible for managing the functions of device  50 , including boot-up and self-test, configuration, power and interface management, and parameter adjustment. The controller comprises a digital signal processor (DSP) core  106  and an AHB master  108  for controlling data movement on AHB matrix  82 . Typically, controller  104  boots from a boot read-only memory (ROM)  110 , and then loads program code from flash memory  52  via a flash interface  132  into an instruction random-access memory (RAM)  112 . The controller also has its own data memory  114 . Controller  104  may, in addition, have a test interface  116 , such as a Joint Test Action Group (JTAG) interface, for purposes of debugging by an external computer  118 . 
     Controller  104  distributes configuration data and parameters to other components of device  50  via a register configuration interface, such as an Advanced Peripheral Bus (APB)  120 , to which the controller is connected through AHB matrix  82  and an APB bridge  122 . Various control interfaces are available for controlling these other components, including a Serial Synchronous Interface (SSI) and Serial Peripheral Interface (SPI) master unit  124  and slave unit  128 , as well as an Inter-Integrated Circuit (I2C) master unit  122  and slave unit  126 . A power management interface  133  provides power and reset signals to the peripheral devices. These particular interfaces are shown here by way of example, and other interface configurations may alternatively be used for similar purposes. 
       FIG. 4  is a block diagram that schematically shows details of depth processor  62 , in accordance with an embodiment of the present invention. The figure also shows certain functions of the parallel color processing block  72 . 
     To reduce on-chip storage and memory requirements, processor  62  typically uses a sliding window approach, in which only part of each processed image is stored in device  50  at any given time, and not the entire image. The window typically contains only a small number of lines of pixels, as required by the algorithms described hereinbelow. Newly-arrived data continually replaces old, processed data in the processor memory. The depth values are reconstructed by processor  62  on the fly, based on the input image data, and are output on the fly via FIFO buffer  66  to host computer  26 . 
     An input data preprocessing block  140  in processor accepts depth-related pixel values from detector  40  via interface  64  and performs filtering operations to reduce noise and possibly to classify the pixels into different groups. The preprocessed data within the current processing window are stored in a picture memory  142 . The picture memory may comprise a number of memories or banks to allow simultaneous read of multiple data blocks. 
     For purposes of depth computation, a reference read engine  146  reads the reference image from memory  52  via interface  132  into a reference memory  148 . The reference data are read from memory  52  synchronously with the arrival of the corresponding parts of the current image into memory  142  from preprocessing block  140 . Like the picture memory, the reference memory stores only the part of the reference image that falls within the current processing window for the purpose of depth reconstruction, and may comprise a number of memories or banks. Reference read engine  146  may also be controlled to store the reference image initially in memory  52  during the calibration procedure. 
     A match engine  144  matches groups of input pixels from memory  142  with corresponding groups of reference pixels from memory  148  in order to find the relative offset of the input pixels. The match engine translates this offset into a depth value, as explained above, and writes the depth value to an output memory  150 . Again, at any given time, the output memory stores only a small sliding window out of the overall depth map, and may comprise a number of memories or banks. 
     A registration engine  152  registers the depth values generated by match engine  144  with color image data obtained from detector  46 . This registration process is described in detail hereinbelow. Registration engine  152  shifts the locations of the depth values in the depth map to coincide with the appropriate color pixels in the color image. Alternatively, it would be possible to shift the color pixel values to coincide with the corresponding depth map pixels. Following registration, a depth post-processing block  154  applies filtering and possibly other mathematical operations to the depth data. 
     A compression block  156  compresses the depth data prior to passing the data to USB FIFO unit  68 , in order to reduce the required bandwidth on the USB output link. Details of the compression function are described hereinbelow with reference to  FIG. 7 . 
     In parallel with the depth processing operations described above, a color image processor  158  in color processing block  72  converts input pixel values received from interface  70  into image data in accordance with an appropriate video standard, such as RGB or YUV, for example. A compression block  160 , of similar design to block  156 , compresses the color image data, as well. 
     Registration of Depth with Color Image Data 
       FIG. 5  is a block diagram that schematically shows details of registration engine  152 , in accordance with an embodiment of the present invention. The registration engine is connected to receive depth pixel values via a pixel bus  170 . The pixels have the form (x 0 ,y 0 ,dX 0 ), wherein X 0  and Y 0  are the raw horizontal and vertical coordinates, before registration, and dX 0  is the pixel shift value measured by match engine  144  between this pixel and the corresponding pixel in the reference image. (Because illumination subassembly  30  and depth image capture subassembly  36  are arranged along the X axis, only X-direction shift is significant in triangulation of the depth.) 
     A registered coordinate calculation block  172  counts columns and lines of incoming pixels and uses a parabolic fitting process to calculate registered coordinates (x r ,y r ) for each dX 0  pixel shift value. This calculation is described in detail hereinbelow. Input streaming write logic  174  writes the incoming pixel shift values into the appropriate registered locations in an N-line buffer  176 , according to the registered coordinates. Logic  174  also manages buffer line allocation as the pixels advance. 
     A vertical range calculator  178  calculates the minimum registered line number (y r ) that will no longer be affected by the current input line. This number indicates the next line that may be read out of buffer  176 . Calculator  178  likewise uses a parabolic fitting equation for this calculation. Output streaming logic  180  uses the minimum registered line number value in choosing lines of registered pixel values to read out of buffer  176  to pixel bus  170 . As a result of the registration process, this stream of pixel depth values is registered with the corresponding color values in block  72 . 
     Operation of registered coordinate calculation block  172  will now be presented in detail. The calculation performed by block  172  uses the following parameters, some of which are shown in  FIG. 2 :
         D cl —distance between the optical axes of the illumination and depth image capture subassemblies  30  and  36 .   dX—calculated pattern shift at a point between reference and current depth images.   D srs —distance between depth image capture subassembly  36  and reference plane  54 .   D srr —distance between subassembly  36  and a registration reference plane.   d—depth value (which may be positive or negative) of a point on the object surface relative to reference plane  54 .   D cc —distance between the depth and color image capture subassemblies  38  and  44 .       

     The depth d can be calculated from the shift dX as follows: 
                   d   =       dX   *     D   srs           D   cl     -   dX               (   1   )               
Due to geometrical factors, the depth d at a given point causes a shift Δ between the color and depth images at that point:
 
                   Δ   =       Δ   0     +         D   cc     *   d         D   srr     +   d                 (   2   )               
In the above formula, Δ 0  is an initial set of point-wise shifts between the color and depth images at a reference plane at the distance D srr  from assembly  24 , due to the offset and possibly misalignment between the cameras. The formula theoretically applies to both X and Y shifts, but in the configuration shown in  FIG. 2 , the Y shift is essentially constant throughout any given region of interest: Δ y =Δ 0   y , and the above formula applies only to the X shift Δ x .
 
     The registered coordinates for each input pattern shift value dX at point (x 0 ,y 0 ) in the unregistered image are then given by: 
                       x   r     =         x   o     +     Δ   x       =       x   o     +     Δ   0   x     +         D   cc     *   d         D   srr     +   d             ⁢     
     ⁢       y   r     =         y   o     +     Δ   y       =       y   o     +     Δ   0   y                   (   3   )               
The initial set of point-wise shifts could be stored in a lookup table, but to reduce on-chip storage, block  172  may use a parabolic fitting calculation instead:
 
Δ 0   x ( x,y )= a   x   x   2   +b   x   y   2   +c   x   xy+d   x   x+e   x   y+f   x  
 
Δ 0   y ( x,y )= a   y   x   2   +b   y   y   2   +c   y   xy+d   y   x+e   y   y+f   y   (4)
 
The twelve fitting coefficients in the above equation are calculated in advance, typically based on a calibration procedure, and are then loaded into the appropriate registers in processor  50 . Alternatively, other types of fitting functions may be used.
 
     Now combining the above formulas, and assuming D srs =D srr , the registered coordinates are given by: 
                       x   r     =       x   o     +       a   x     ⁢     x   o   2       +       b   x     ⁢     y   o   2       +       c   x     ⁢     x   o     ⁢     y   o       +       d   x     ⁢     x   o       +       e   x     ⁢     y   o       +     f   x     +     β   ⁢           ⁢     dX   o           ⁢     
     ⁢       y   r     =       y   o     +       a   y     ⁢     x   o   2       +       b   y     ⁢     y   o   2       +       c   y     ⁢     x   o     ⁢     y   o       +       d   y     ⁢     x   o       +       e   y     ⁢     y   o       +       f   y     ⁢           ⁢   wherein         ⁢     
     ⁢   β   =         D   cc       D   cl       .             (   5   )               
To simplify the above calculation, the values of Δ 0   x  and Δ 0   y  in the formula may be calculated incrementally for each pixel, based on values calculated previously for neighboring pixels
 
Δ 0   x ( x   o +1, y   o )=Δ 0   x ( x   o   ,y   o )+Δ x Δ 0   x ( x   0   ,y   o ) x  
 
Δ 0   y ( x   o +1, y   o )=Δ 0   y ( x   o   ,y   o )+Δ y Δ 0   y ( x   o   ,y   o )
 
Δ 0   x ( x   o   ,y   o +1)=Δ 0   x ( x   o   ,y   o )+Δ x Δ 0   x ( x   o   ,y   o )
 
Δ 0   y ( x   o   ,y   o +1)=Δ 0   y ( x   o   ,y   o )+Δ y Δ 0   y ( x   o   ,y   o )  (6)
 
The values Δ 0   x (0,−1) and Δ 0   y (0,−1), at the upper left corner of the picture, are pre-calculated as the start point for the above incremental calculation.
 
       FIG. 6  (consisting of  FIGS. 6A and 6B ) is a block diagram that schematically shows details of registered coordinate calculation block  172 , in accordance with an embodiment of the present invention.  FIG. 6A  shows an X-coordinate calculation sub-block  186 , while  FIG. 6B  shows a Y-coordinate calculation sub-block  188 . These sub-blocks implement the calculation outlined above in equations (5) and (6). More specific details of the digital logic design of these sub-blocks are presented in the above-mentioned provisional patent application, but some of these details are omitted here for the sake of simplicity. 
     Sub-blocks  186  and  188  are built around incremental parabolic fitting circuits  190  and  192 , which perform the calculations of equation (6). For each successive pixel, circuits  190  and  192  receive as inputs the registered coordinate values calculated for the previous pixel (x prev ,y prev ), as well as the parabolic fitting parameters a, b, c, d, e for X and Y. (Capital and small letters are used interchangeably in the text and figures for convenience.) Multiplexers  196  select the “0” input during horizontal advance along each line of the image (incrementing X) and the “1” input during vertical advance from line to line (incrementing Y). 
     The output of circuits  190  and  192  are the Δ 0   x  and Δ 0   y  shift values for the current pixel. During horizontal advance, these values are stored in column shift accumulators  198  and  206 , which then output the accumulated results for input as the previous X and Y shift values to the fitting calculation of circuits  190  and  192  for the next pixel. The shift values are also stored, via multiplexers  202  and  210 , in line shift accumulators  200  and  208 . During vertical advance, multiplexers  204  and  212  select the contents of accumulators  200  and  208  for input to circuits  190  and  192 . As above, the multiplexers select the “0” input during horizontal advance and the “1” input during vertical advance. 
     For the X-direction, sub-block  186  receives the depth-related pattern shift values dX 0  and dX c  from matching engine  144  and takes the difference between these values in a subtractor  214  to give the incremental shift for the current pixel dX. (When no input value is available for dX 0  or dX c , the value 0 may be used instead.) A multiplier  216  multiplies this shift by the pre-calibrated parameter β. An adder  222  sums the result with the parabolic shift value calculated by circuit  190 . The result, finally, is summed with the current X-coordinate x 0  by an adder  226  to give the registered coordinate x r , as defined by equation (5). The registered Y-coordinate is similarly calculated by an adder  230 , but without any depth-related pattern shift component, as explained above. 
     Returning now to  FIG. 5 , since the registration shift that is calculated for each pixel varies over the area of the image, the stream of registered coordinates generated in registration engine will generally be unsynchronized with the input pixel stream. Buffer  176  and read logic  180  compensate for the variable delay between input and output. The number of lines in buffer  176  is given by the value of 
               max       any   ⁢           ⁢     x   o       ,           ⁢     y   o         ⁢       (       max   ⁢           ⁢     Δ   y       -     min   ⁢           ⁢     Δ   y         )     .           
For any input line y o , the greatest registered line y r  in buffer  176  that can receive pixels from input line y o  is y r =y o +min Δ y (y o ). This value is calculated by vertical range calculator  178  and fed to logic  180 . On this basis, logic  180  can read out from buffer  176  all lines above line y r .
 
     Depending on the values of the coefficients f x  and f y  in equation (5), there may be several columns and/or rows at the edges of the depth map produced by depth processor  62  that do not overlap with the color image produced by color processing block  72 . As a result, read logic  180  may need to discard lines of depth values at the edge of the depth map that “spill over” the edge of the color image, and add one or more lines of null or dummy depth values to extend the depth map so that it covers the entire color image. Such dummy values may be created synthetically by post-processing block  154 . 
     Lossless Compression of Depth and Color Images 
       FIG. 7  is a block diagram that schematically shows details of lossless compression blocks  156  and  160 , in accordance with an embodiment of the present invention. The block design shown in the figure is capable of compressing from one to three image components simultaneously. For depth maps, only one component is typically used. For color images, two or three components may be used, depending on the type of color encoding. The compression block uses difference and run-length encoding to compress the input stream efficiently without data loss. This compression makes it possible to transmit both the depth and color image data (as well as audio data) over the limited bandwidth afforded by the single USB serial link to host computer  26 . Alternatively, the compression blocks may be bypassed when sufficient output bandwidth is available. 
     A pixel distributor  240  divides the stream of input pixel values into components. For each component, a subtractor  244  calculates the difference between the current component value and the previous value, as provided by a component delay line  242 . The difference values are input to a pixel merger circuit  246 , which merges the differences back into a single difference stream. Circuit  246  also receives and merges the component values themselves, which are used instead of the difference values for the first pixel in each line and whenever the difference between successive pixels exceeds a certain threshold. 
     A symbol generator  248  encodes the difference and/or original pixel values. Typically, the symbol generator uses run-length encoding to represent the number of repetitions of the same value, and thus reduce the data volume still further. The symbol generator may also add synchronization signals on line and frame boundaries, to assist in subsequent decoding and reduce the impact of any possible data loss downstream. A bit stream packer  250  converts the encoded symbols into a continuous bit stream for USB transmission. The bit stream packer may add stuff bits so that the beginning of each new line and frame will be properly byte-aligned in a USB packet. 
     Although the embodiments above use specific device architectures, protocols, and configurations, the principles of the present invention may similarly be applied using architectures, protocols, and configurations of other types. It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.

Metadata:
Filing Date: 20140825
Publication Date: 20160524
Grant Date: 20160524
Priority Date: 20080709
Inventors: SPEKTOR EVGENY
MOR ZAFRIR
RAIS DMITRI
Assignee: APPLE INC
CPC Classifications: [{"code": "G06T7/521", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06V10/803", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F3/017", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F18/251", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/521", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06F18/251", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06V10/803", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06V10/145", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N13/0253", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06K9/00355", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N13/0207", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06K9/6289", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F3/005", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F3/017", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06T7/0057", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06K9/2036", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T2200/28", "inventive": false, "first": false, "tree": "[]"}, {"code": "H04N13/207", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F3/005", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N13/254", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T2200/28", "inventive": false, "first": false, "tree": "[]"}, {"code": "G06V10/145", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N13/207", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06V40/28", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N13/254", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T2200/28", "inventive": false, "first": false, "tree": "[]"}, {"code": "G06V40/28", "inventive": true, "first": false, "tree": "[]"}]
Family ID: 41504786