Deconvolutionbased structured light system with geometrically plausible regularization

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
18Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method for processing images from a structured light system for use with data processing systems, the method comprising:
 obtaining at least one initial image from a structured light system, the or each of said at least one initial image being of a subject having projected on it at least one pattern by said structured light system;
determining characteristics of said structured light system;
iteratively segmenting and deconvolving said at least one initial image using said characteristics of said structured light system and at least one point spread function to result in at least one resulting image, said at least one resulting image being a more accurate image of said subject compared to said at least one image.
1 Assignment
0 Petitions
Accused Products
Abstract
Systems and methods for processing images in a structured light system which may be used to determine the correspondences in a cameraprojector system. Those correspondences can later be used to construct a 3D model, to calibrate a projector or for other purposes. The optical and geometric characteristics of the system are initially determined. The capability of establishing correspondences is affected by the limitations of the system and the properties of the surfaces. Once images of the patterns projected on the surface are acquired, they are iteratively segmented and deconvolved using the known characteristics of the system. The result is a set of correspondences with a reduction of artifacts introduced by the limitations of the system. The characteristics of the structured light system which may be used in the iterative segmentation and deconvolution may include the characteristics of a pattern projected on the scene or object, the physical characteristics of the structured light system, as well as the characteristics of the scene or object itself.
31 Citations
View as Search Results
IMAGE DEBLURRING USING A COMBINED DIFFERENTIAL IMAGE  
Patent #
US 20110102642A1
Filed 11/04/2009

Current Assignee
Monument Peak Ventures LLC

Sponsoring Entity
Monument Peak Ventures LLC

Catadioptric Projectors  
Patent #
US 20100123784A1
Filed 06/19/2009

Current Assignee
Seiko Epson Corporation

Sponsoring Entity
Seiko Epson Corporation

FORMING RANGE MAPS USING PERIODIC ILLUMINATION PATTERNS  
Patent #
US 20120176478A1
Filed 01/11/2011

Current Assignee
Kodak Alaris Inc

Sponsoring Entity
Kodak Alaris Inc

Image deblurring using a combined differential image  
Patent #
US 8,379,120 B2
Filed 11/04/2009

Current Assignee
Monument Peak Ventures LLC

Sponsoring Entity
Intellectual Ventures Fund 83 LLC

Catadioptric projectors  
Patent #
US 8,201,951 B2
Filed 06/19/2009

Current Assignee
Seiko Epson Corporation

Sponsoring Entity
Seiko Epson Corporation

Forming 3D models using two images  
Patent #
US 8,447,099 B2
Filed 01/11/2011

Current Assignee
Kodak Alaris Inc

Sponsoring Entity
Kodak Alaris Inc

Forming 3D models using multiple images  
Patent #
US 8,452,081 B2
Filed 01/11/2011

Current Assignee
Kodak Alaris Inc

Sponsoring Entity
Kodak Alaris Inc

Coded aperture camera with adaptive image processing  
Patent #
US 8,582,820 B2
Filed 09/24/2010

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

High resolution high contrast edge projection  
Patent #
US 8,754,954 B2
Filed 05/16/2011

Current Assignee
National Research Council Canada

Sponsoring Entity
National Research Council Canada

COOPERATIVE PHOTOGRAPHY  
Patent #
US 20140285634A1
Filed 03/18/2014

Current Assignee
Digimarc Corporation

Sponsoring Entity
Digimarc Corporation

IMAGE PROCESSING METHOD AND APPARATUS FOR CALIBRATING DEPTH OF DEPTH SENSOR  
Patent #
US 20150279016A1
Filed 07/28/2014

Current Assignee
Electronics and Telecommunications Research Institute

Sponsoring Entity
Electronics and Telecommunications Research Institute

3D intraoral measurements using optical multiline method  
Patent #
US 9,295,532 B2
Filed 11/10/2011

Current Assignee
Carestream Dental Technology Topco Limited

Sponsoring Entity
CareStream Health Incorporated

3D intraoral measurements using optical multiline method  
Patent #
US 9,349,182 B2
Filed 06/18/2012

Current Assignee
Carestream Dental Technology Topco Limited

Sponsoring Entity
CareStream Health Incorporated

Scanning Microscope and Method for Determining the Point Spread Function (PSF)of a Scanning Microscope  
Patent #
US 20160267658A1
Filed 10/10/2014

Current Assignee
Carl Zeiss Microscopy GmbH

Sponsoring Entity
Carl Zeiss Microscopy GmbH

Cooperative photography  
Patent #
US 9,554,123 B2
Filed 03/18/2014

Current Assignee
Digimarc Corporation

Sponsoring Entity
Digimarc Corporation

Image processing method and apparatus for calibrating depth of depth sensor  
Patent #
US 9,858,684 B2
Filed 07/28/2014

Current Assignee
Electronics and Telecommunications Research Institute

Sponsoring Entity
Electronics and Telecommunications Research Institute

Scanning microscope and method for determining the point spread function (PSF) of a scanning microscope  
Patent #
US 10,048,481 B2
Filed 10/10/2014

Current Assignee
Carl Zeiss Microscopy GmbH

Sponsoring Entity
Carl Zeiss Microscopy GmbH

3D intraoral measurements using optical multiline method  
Patent #
US 10,223,606 B2
Filed 08/28/2014

Current Assignee
Carestream Dental Technology Topco Limited

Sponsoring Entity
Carestream Dental Technology Topco Limited

Hybrid method for 3D shape measurement  
Patent #
US 20110080471A1
Filed 10/05/2010

Current Assignee
Iowa State University Research Foundation Incorporated

Sponsoring Entity
Iowa State University Research Foundation Incorporated

System and method of threedimensional pose estimation  
Patent #
US 7,957,583 B2
Filed 08/02/2007

Current Assignee
ROBOTICVISIONTECH INC.

Sponsoring Entity
ROBOTICVISIONTECH LLC

METHOD AND SYSTEM FOR PROVIDING THREEDIMENSIONAL AND RANGE INTERPLANAR ESTIMATION  
Patent #
US 20110181704A1
Filed 10/11/2009

Current Assignee
Mantis Vision Ltd.

Sponsoring Entity
Mantis Vision Ltd.

DETECTION OF OBJECTS IN IMAGES  
Patent #
US 20100246890A1
Filed 03/26/2009

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Technology Licensing LLC

SYSTEM AND METHOD FOR 3D MEASUREMENT AND SURFACE RECONSTRUCTION  
Patent #
US 20090102840A1
Filed 11/12/2008

Current Assignee
City University of Hong Kong

Sponsoring Entity
City University of Hong Kong

METHOD AND APPARATUS FOR MOTION INVARIANT IMAGING  
Patent #
US 20090244300A1
Filed 03/28/2008

Current Assignee
Massachusetts Institute of Technology

Sponsoring Entity
Massachusetts Institute of Technology

System and method for 3D measurement and surface reconstruction  
Patent #
US 20060017720A1
Filed 07/15/2004

Current Assignee
City University of Hong Kong

Sponsoring Entity
City University of Hong Kong

Generating 3D models by combining models from a videobased technique and data from a structured light technique  
Patent #
US 6,529,627 B1
Filed 11/10/2000

Current Assignee
Geometrix Inc., Geometrix Inc. San Jose CA

Sponsoring Entity
Geometrix Inc., Geometrix Inc. San Jose CA

Structuredlight, triangulationbased threedimensional digitizer  
Patent #
US 6,549,288 B1
Filed 05/14/1999

Current Assignee
Sizmek Technologies Inc

Sponsoring Entity
ENLIVEN MARKETING TECHNOLOGIES CORPORATION

Positionandattitude recognition method and apparatus by use of image pickup means  
Patent #
US 5,499,306 A
Filed 03/07/1994

Current Assignee
Nippondenso Co. Ltd.

Sponsoring Entity
Nippondenso Co. Ltd.

Method and apparatus for measuring threedimensional position and orientation of an object using light projection  
Patent #
US 5,461,478 A
Filed 08/24/1993

Current Assignee
Fanuc Ltd

Sponsoring Entity
Fanuc Ltd

Method and apparatus for calibrating a vision guided robot  
Patent #
US 5,083,073 A
Filed 09/20/1990

Current Assignee
ROY MARY E.

Sponsoring Entity
MAZDA MOTOR MANUFACTURING U.S.A. CORP. A CORP. OF MI

Threedimensional range camera  
Patent #
US 4,687,325 A
Filed 03/28/1985

Current Assignee
General Electric Company

Sponsoring Entity
General Electric Company

11 Claims
 1. A method for processing images from a structured light system for use with data processing systems, the method comprising:
 obtaining at least one initial image from a structured light system, the or each of said at least one initial image being of a subject having projected on it at least one pattern by said structured light system;
determining characteristics of said structured light system;
iteratively segmenting and deconvolving said at least one initial image using said characteristics of said structured light system and at least one point spread function to result in at least one resulting image, said at least one resulting image being a more accurate image of said subject compared to said at least one image.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
 obtaining at least one initial image from a structured light system, the or each of said at least one initial image being of a subject having projected on it at least one pattern by said structured light system;
 11. A computer readable storage medium having stored thereon at least one computer executable command for execution by a data processing system which, when executed by said data processing system, results in performance of the steps of a method for processing images from a structured light system for use with data processing systems, the method comprising:
 obtaining at least one initial image from a structured light system, the or each of said at least one initial image being of a subject having projected on it at least one pattern by said structured light system;
determining characteristics of said structured light system;
iteratively segmenting and deconvolving said at least one initial image using said characteristics of said structured light system and at least one point spread function to result in at least resulting image, said resulting image being a more accurate image of said subject compared to said at least one image.
 obtaining at least one initial image from a structured light system, the or each of said at least one initial image being of a subject having projected on it at least one pattern by said structured light system;
1 Specification
The present application claims priority on U.S. Provisional Patent Application Ser. No. 61/071,915 filed May 23, 2008.
FIELD OF THE INVENTIONThe present invention relates to image processing. More specifically, the present invention relates to methods and systems for processing images which are used to establish correspondences in a cameraprojector system.
BACKGROUND TO THE INVENTIONIt should be noted that a list of the references referred to in this document may be found at the end of the document.
In the past few years, projectorcamera systems have been used in many applications ranging from 3D reconstruction to multiprojector visualization. For many applications, the main task is to establish the correspondence between the pixels of a projector and those of a camera (see FIG. 1). This is accomplished by projecting known light patterns on an unknown scene viewed by a camera. The projector “applies” textures to the scene and the patterns are designed (or structured) such that it is possible to identify which projector pixel illuminates the part of the scene viewed by a camera pixel. Different patterns can be used: a survey by Salvi et al. classified these patterns in 3 categories, namely, direct codification, neighborhood codification and timemultiplexing. The Gray code is probably the best known timemultiplexing code[14]. It uses a succession of patterns composed of white and black stripes. For this reason, it is also known as a stripebased code. The width of the stripes vary with the patterns.
When working with a structured light system, many sources of error can affect image formation. These sources of error can be classified as originating from projection, imaging or from the overall system:
 Projection Depth of field and chromatic aberration affect the detectability of spatial transitions. Calibration parameters vary due to thermal instability. Error is introduced by dithering and signal synchronization.
 Imaging Depth of field, antialiasing filter and small fill factor limit the detectability of the pattern. Also, when using color cameras, artifacts are introduced by Bayer color processing and the Bayer matrix itself.
 Overall system Surface properties and ambient light impact the SignaltoNoise Ratio (SNR). It is also reduced by high frame rates, or nonuniform sensitivity of the projection and of the camera.
Previous work in this field has attempted to overcome these errors. A recent paper by Salvi et al. [26] contains an extensive survey of structured light (SL) techniques. Few methods use energy minimization frameworks for the decoding of patterns [5, 32, 16, 29, 17]. Some use these energy minimization frameworks to remove ambiguity in their code [5, 32, 16], while others use it to reduce sensitivity to noise [29, 17]. In [20], the best focus distance is used as a constraint in the selfcalibration of a SL system.
It should be noted that, however, there is a large body of literature on the problem of thresholding, segmentation and deconvolution [28, 22]. Some methods simultaneously segment and deconvolve the images [24, 2]. However these methods do not address or take advantage of the aspects that are specific to a structured light system.
So far, no reference has been found which explicitly models blurring.
It is therefore an object of the present invention to mitigate if not overcome the shortcomings of the prior art.
SUMMARY OF THE INVENTIONThe present invention provides systems and methods for processing images in a structured light system in order to determine the correspondences in a cameraprojector system. Those correspondences can later be used to construct a 3D model, to calibrate a projector or for other purposes. The optical and geometric characteristics of the system are initially determined. The capability of establishing correspondences is affected by the limitations of the system and the properties of the surfaces. Once images of the patterns projected on the surface are acquired, they are iteratively segmented and deconvolved using the known characteristics of the system. The result is a set of correspondences with a reduction of artifacts introduced by the limitations of the system. The characteristics of the structured light system which may be used in the iterative segmentation and deconvolution may include the characteristics of a pattern projected on the scene or object, the physical characteristics of the structured light system, as well as the characteristics of the scene or object itself.
In one aspect, the present invention provides a method for processing images from a structured light system for use with data processing systems, the method comprising:
 obtaining at least one initial image from a structured light system, the or each of said at least one initial image being of a subject having projected on it at least one pattern by said structured light system;
 determining characteristics of said structured light system;
 iteratively segmenting and deconvolving said at least one initial image using said characteristics of said structured light system and at least one point spread function to result in at least resulting image, said resulting image being a more accurate image of said subject compared to said at least one image.
In another aspect, the present invention provides a method for processing images from a structured light system for use with data processing systems, the method comprising:
 obtaining at least one initial image from a structured light system;
 determining characteristics of said structured light system;
 iteratively segmenting and deconvolving said at least one initial image using said characteristics of said structured light system to result in at least one nonblurred resulting image compared to said at least one image.
In a further aspect, the present invention provides a computer readable storage medium having stored thereon at least one computer executable command for execution by a data processing system which, when executed by said data processing system, results in performance of the steps of a method for processing images from a structured light system for use with data processing systems, the method comprising:
 obtaining at least one initial image from a structured light system, the or each of said at least one initial image being of a subject having projected on it at least one pattern by said structured light system;
 determining characteristics of said structured light system;
 iteratively segmenting and deconvolving said at least one initial image using said characteristics of said structured light system and at least one point spread function to result in at least resulting image, said resulting image being a more accurate image of said subject compared to said at least one image.
These and other features of the invention will become more apparent from the following description in which reference is made to the appended drawings in which:
FIG. 1 is a representation of a structured light system;
FIG. 2 illustrates a projected displacement as a function of angles for a projector and a camera;
FIG. 3 is a schematic of a rectified projectorcamera system with a frontoparallel scene and a mapping of a camera pixel to a projector column for the rectified projectorcamera system;
FIG. 4 illustrates results using the present invention and methods of the prior art;
FIG. 5 shows intensity histograms before and after the present invention is applied;
FIG. 6 provides graphs that show the resistance of change of λ for patterns 1 to 3 of Table 1;
FIG. 7 illustrates the results for two patterns using the present invention and methods of the prior art;
FIG. 8 illustrates the results for a scan of two planes with different orientations using the present invention; and
FIG. 9 is a schematic diagram illustrating the concept of a divide and conquer strategy which may be used when implementing the invention.
DETAILED DESCRIPTION OF THE INVENTIONThe present invention relates to structured light systems. As is well known and as can be seen from FIG. 1, a structured light system involves one or more cameras, one or more projectors, and the scene or object to be imaged. Each projector projects a pattern on the scene or object and each camera captures an image of the scene or object with the pattern projected on it. As was described above, the main task is to establish the correspondence between the pixels of the projector and those of the camera so that it can be determined which projector pixel illuminated a specific part of the scene/object imaged or viewed by a specific camera pixel. The correspondences may be established between fractions of pixels of projector and camera. These correspondences can later be used to construct a 3D model, to calibrate a projector or for other purposes.
The image produced by the camera, unfortunately, can be quite unclear due to a number of sources of error or blurring. As mentioned above, these sources can cause the resulting image to be quite degraded. These sources of error may be generalized as coming from three main sources: the projector, the scene, and the camera. The resulting degradation in the image can thus be seen as a result of the combination of the effects of the three error sources. The image formation can therefore be modeled as a triple convolution of the projector, the scene, and of the camera. Unfortunately, the point spread function (PSF) of each of these three is responsible for the blurring of the resulting image.
It must be noted that the PSF of the system as a whole depends on the physical characteristics of the projector and camera and, indeed, on the characteristics of the system as a whole. It varies as well with the distance of the surface to be scanned as well as the orientation of the scene or object. The PSF also varies with the positioning of the pixels on the detection chip of the camera and on the projection surface of the projector.
In order to recover the nondegraded image, a deconvolution needs to be performed. The deconvolution would recover an approximation of the image without the degradation introduced by the PSFs of the three sources of error. The deconvolution would therefore recover a more accurate or nonblurred image of the subject. To assist in the deconvolution, the PSF of the system (the combined PSFs of the projector, the scene, and of the camera or a combined PSF of any combination of the PSFs of the projector, the scene, and of the camera) can be estimated beforehand using an image of a standard target for PSF determination. Also, since the deconvolution process has some known issues (such as sensitivity to noise, instability, and others), these issues can be compensated for by using the specific characteristics of the structured light system when iteratively deconvolving the image. As well, to help in the stabilization of the deconvolution, a segmentation process may also be performed on the image.
It should be noted that the term “segmentation” in the context of this document is to mean “segmentation” in the field of computer vision and image processing. In computer vision and image processing dictionaries, segmentation is defined as the grouping (or classification) of image pixels into meaningful, usually connected structures such as curves and region. The term is applied to a variety of image modalities, such as intensity data or range data and properties, such as similar feature orientation, feature motion, surface shape or texture.
In the field and context of structured light systems, the above definition holds true. Structured light systems operate by projecting light with known properties onto a surface, and by using a camera to identify the characteristic of the originating light. Some structured light patterns use a small number of different values of the characteristic used for identification (e.g. color or intensity values). As an example of this, structured light systems often use binary patterns (black and white shapes). With such systems, each pixel of a camera can be classified as being lit by a black or white part of the pattern projected by the projector. In such a system, it is expected that neighbour pixels belong to the same class (here, black or white) and it is expected that those pixels would form regions with a shape that depends on the characteristic of the light system and the shape of the object being imaged. Another possible structured light system maximizes the number of classes in the segmentation by using a pattern consisting of a gray scale gradient with all pixels on the same row or column having the same gray level value. For such a system, the number of classes that can be identified can be close to the number of gray levels that a camera can measure. The process of classifying or grouping pixels using a gray scale gradient is still considered as segmentation since, for such a gray scale gradient based system, it is expected that neighbouring pixels belong to the same class, and it is expected that these neighbouring pixels would form region with a shape that depends on the characteristics of the system and on the shape of the object being acquired or imaged.
Some of these characteristics of the structured light system which can be used to assist in the deconvolution and in the segmentation processes may be summarized as follows:
 the structure of the projected patterns
 shapes present in the pattern
 numbers of colors or gray levels used in the patterns
 expected intensities for each color or gray level
 the physical configuration of the structured light system
 the position of the camera and the projector (the geometric calibration of the system)
 the type of the projector used (e.g. whether the projector is an LCD, a DLP, color, or analog projector)
 the type of camera used (e.g. whether the camera is a color or a gray level camera)
 a distance of the object or scene from the scanner
 known characteristics of the scene or object being scanned
 surface texture (e.g. whether the surface of the object or scene is smooth or textured and what type of texture)
 surface geometry (e.g. the rate at which the surface orientation changes)
 the number of the objects within the scene
 the structure of the projected patterns
Of course, other characteristics of the structured light system may also be used.
Once a nonblurred or more accurate image is obtained using the segmentation and deconvolution processes, the correspondences between the camera(s) and the projector(s) in the structured light system can be more easily obtained using the nonblurred image.
The method of the invention can therefore be summarized as having four main steps:
 obtaining images from a structured light system
 determining characteristics of said structured light system
 iteratively segmenting and deconvolving the images using the characteristics of the structured light system (including the point spread function of the structured light system) to result in a more accurate resulting image of the subject and, optionally,
 establishing correspondences between cameras and projector using said nonblurred resulting images.
The iterative aspect of the method may terminate once a preset or predetermined point has been reached. As an example, the method may be terminated once a specific fidelity or clarity of the image is reached. Or, as another example, the method may be terminated once the objective improvement between two successive images produced by the method is lower than a predetermined or given value.
While the sample implementation given below uses a Gray code pattern, other patterns may also be used. These patterns can be classified into three primary categories:
 direct codification
 neighborhood codification
 timemultiplexing codification
Codes from the direct codification category use single patterns that contain all the information needed to establish the correspondence between the projector pixel and the camera pixel. Such patterns are sensitive to noise. Neighborhood codification patterns establish a sparse correspondence between the pixels using a single pattern. To counteract noise sensitivity for these patterns, the spatial resolution is reduced.
Within each category of these patterns, the patterns may be further subcategorized into three other subcategories based on intensity:
 binary intensity
 gray level intensity
 color intensity
The invention described may use patterns from any combination of the primary and secondary categories. In the example which follows, the Gray code used is a member of the timemultiplexing primary category and of the secondary binary intensity category. However, as noted before, any pattern from any of the categories above may be used with the invention.
It should be noted that other patterns may be used as well. Rather than using patterns with white and black stripes, patterns that contain gray level values arranged as a ramp, a triangular wave, a sine wave, or arranged as any other waveform may be used. A single waveform may be used or multiple waveforms (perhaps with different phases) may be used. The acquired images with these waveform based patterns projected on the subject can then be deconvolved and segmented individually or as a group using the regularization terms described below. The resulting image or images (which would be more accurate images of the subject) can then be computed from these acquired or initial images.
Combinations of these resulting images may also be computed from these results of the deconvolution and segmentation processes. Someone skilled in the art of signal processing could further process those combinations of deblurred or more accurate images to obtain the correspondence between a projector and a camera of a structured light system. Alternatively, any combination of the blurred or initial images (whether they are linear combinations or otherwise) can be computed and then deconvolved and segmented. The results of the deconvolution and segmentation of these combined images can then be used by someone skilled in the art of signal processing to compute the correspondence between projector and camera.
As will be seen below, the known characteristics of the pattern used can be used to advantage in the deconvolution and segmentation process. In the example that follows, the Gray code is used and patterns of this code can be segmented into 2 classes (black and white). Also, the intensity of each class (black class or white class) as measured by the camera is known.
In another example of the type of previous knowledge which may be used, a neighborhood codification code has 8 different colors such that each intersection composed of 4 pixels has a unique arrangement of colors; a specific pattern may be segmented into 8 specific classes (each class corresponding to a specific color). For each color or class, the intensity as measured by the camera in absence of blurring is known, and it is also known that the pattern uses a rectangular grid. Such knowledge can be used in the deconvolution process in order to reduce the impact of issues such as sensitivity to noise and instability.
For all cases of patterns, parts of the structure of the pattern are lost when the patterns are projected or “applied” to the scene by the projector. This deformation of the structure of the pattern is expected and, by using a reasonable hypothesis regarding the surface of the scene or object, large parts of the structure of the pattern remain. This remaining structure can then be used to regularize or stabilize the deconvolution.
It should be noted that the detailed implementation given below is only one of many possible implementations. The steps taken to practice the invention follow the general concept outlined above but its implementation need not exactly follow the steps detailed below. As an example, the implementation below uses a second image which is simply the first image with the intensities reversed (i.e. the black areas are now white and vice versa). This step need not be followed for other implementations and, indeed, are not necessarily required for the implementation detailed below.
It must also be noted that while the implementation below uses a foreknowledge of the pattern (i.e. that it is simply a black and white or binary pattern), the principles used are equally applicable to nonbinary patterns (e.g. gray scale or color based patterns).
The implementation of the invention described below provides systems and methods for processing images so that they may be used in applications such as the reconstruction of 3D scenes. A black and white first image is provided. A second black and white image, an identical but color opposite of the first image is also provided. A third image, which is an undegraded or nonblurred version of the difference of the first two images, is then generated by simultaneously deconvolving and segmenting a degraded version of the third image. This is accomplished by deconvolving the degraded version of the third image from the point spread function of the system while using specific regularization terms. These regularization terms, which assist in the segmentation of the degraded version of the third image, are based on the probability that two pixels adjacent to each other in the degraded version belong to different classes or colors. The system which generates the first image may be a structured light system and the first image may be generated by projecting a known light pattern on to a specific scene. Once the nonblurred third image is obtained, the correspondence between the various cameras and projectors in the structured light system can be more easily determined using this nonblurred third image.
The implementation detailed below involves using at least one initial image and generating at least one interim image derived from the initial image. Other implementations which involve generating or deriving multiple interim images, derived from any number of initial images or even derived from any number of interim images, may also be used. The interim images and the initial images may be combined in any way suitable to provide a useful input to the deconvolution and segmentation process.
The present invention explicitly models the blurring induced by the limited depth of field (camera and projector) and reduces the impact of the other error sources by using regularization. Blurring was described as a significant limitation of digital projector profilometry [1] and the present invention allows a significant improvement when working out of focus which occurs when performing depth measurement. The present method iteratively performs a deconvolution and a segmentation of the patterns. Moreover, it takes into consideration the projected displacement which is induced by the camera, the projector and the scene configuration. This allows the use of regularization terms which are geometrically plausible.
Described below are specific implementation details of one embodiment of the invention. These details are implementation specific and need not be taken as being specifically necessary to or limiting in any way as to the scope of the present invention.
In one aspect of the invention, the method takes as input two images G and R of size m×n. The first image, G, is an image of a static scene acquired while one of the Gray code patterns is projected. The image R is simply G with white and black stripes reversed and R(q) is the intensity of image R at pixel q. Using G and R allows an increase in robustness and we define I=G−R. When neglecting the noise, the image formation for I is described as I(q)=H(q) <img id="CUSTOMCHARACTER00001" he="2.79mm" wi="2.79mm" file="US20100034429A120100211P00001.TIF" imgcontent="character" imgformat="tif"/> X(q) where X is the nondegraded image of G−R and H is the Point Spread Function (PSF) of the system which depends on the projector, the camera and the scene configuration. Note that this is different from conventional deconvolution where blurring is introduced only by the camera lens. The system PSF will be further described below and for now the system PSF will be assumed to be spatially invariant. With H and I known, the nondegraded image is the one minimizing
<FORM>∥Hx−i∥<sup>2 </sup> (1)</FORM>
where H is an mn by mn block Toeplitz matrix with Toeplitz blocks representing the convolution with the PSF H [9]. The vector x and i are stacks of the columns of the images X and I respectively and are of length mn. Since this deconvolution is illconditioned the invention simultaneously segments and deconvolves the image I using the result of the segmentation to regularize the deconvolution. There is added a regularization term based on the heuristic that two neighboring pixels should have the same intensity if they belong to the same class (i.e. they are either white or black). This allows the reduction of the impact of noise. The matrix S contains, for each twopixel neighborhood interaction, a row with two nonzero entries corresponding to the neighbors. Those entries are 1 and −1 respectively. Explicitly, each line of Sx represents an equation of the form X(q)−X(q′)=0 where q and q′ are neighbor pixels. The neighborhood structure is presented further below. The regularization term is
<FORM>λ<sup>2</sup>∥M<sub>d </sub>Sx∥<sup>2 </sup> (2)</FORM>
where λ is a userdefined parameter and M<sub>d </sub>is a diagonal matrix where each diagonal entry is the probability that all the pixels involved in the interaction of the corresponding row of S belong to the same class. While the previous regularization term improves the conditioning, the deconvolution is still illposed. In order to fix the scaling and anchor the solution, we add the regularization term
<FORM>γ<sup>2</sup>(∥M<sub>b</sub>(x−u<sub>b</sub>)∥<sup>2</sup>+∥M<sub>w</sub>(x−u<sub>w</sub>)∥<sup>2</sup>) (3)</FORM>
where γ is a userdefined parameter and M<sub>b </sub>and M<sub>w </sub>are diagonal matrices for the black and white class respectively. The vectors u<sub>b </sub>and u<sub>w </sub>are the expected intensity for the black and white class respectively. They are not necessarily spatially constant. These vectors can be estimated by projecting white and black images, or approximated using the image I directly or iteratively estimated as in [24]. Diagonal entries of M<sub>b </sub>and M<sub>w </sub>are the probabilities that the corresponding pixel of X belong to the black and white class respectively. When M<sub>b</sub>, M<sub>w</sub>, M<sub>d</sub>, u<sub>b</sub>, and u<sub>w </sub>are fixed, the terms of Eq. 1, 2 and 3 form a Tikhonov regularization which may be solved iteratively [9]. The matrices M<sub>b</sub>, M<sub>w</sub>, M<sub>d</sub>, depend on the segmentation which is described below.
The segmentation is accomplished by first defining that the set P contains the pixels of image X and the set L={w, b} contains the label for white and black pixels. A Lconfiguration C:P <sup>→</sup> L associates a label to every pixel of P. The probability of a configuration C given X is
<maths id="MATHUS00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>C</mi><mo></mo><mi>X</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mi>Z</mi></mfrac><mo></mo><mrow><munder><mo>∏</mo><mrow><mi>q</mi><mo>∈</mo><mi></mi></mrow></munder><mo></mo><mstyle><mspace width="0.3em" height="0.3ex"/></mstyle><mo></mo><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>q</mi><mo></mo><mrow><mi>C</mi><mo></mo><mrow><mo>(</mo><mi>q</mi><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><munder><mo>∏</mo><mrow><mrow><mo>(</mo><mrow><mi>q</mi><mo>,</mo><msup><mi>q</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow><mo>∈</mo><mi></mi></mrow></munder><mo></mo><mstyle><mspace width="0.3em" height="0.3ex"/></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><mi>C</mi><mo></mo><mrow><mo>(</mo><mi>q</mi><mo>)</mo></mrow></mrow><mo>,</mo><mrow><mi>C</mi><mo></mo><mrow><mo>(</mo><msup><mi>q</mi><mi>′</mi></msup><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>4</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>
where Z is the normalization factor of the Bayes formula and N is the set of pair of neighbor pixels. The probability p(X(q)C(q)) is a Gaussian distribution having mean identical to those of u<sub>b</sub>, and u<sub>w</sub>. In one implementation, the variance is assumed to be equal for both classes. We observed that those hypotheses are acceptable. Also, p(C(q),C(q′)) is the probability of having a class transition between the pixels q and q′. This is related to the projected displacement presented below. For each pixel q, in order to deconvolve X, there is needed the probabilities p(CX,C(q)=b) and p(CX,C(q)=w), that is the probabilities of the most likely segmentation of image X with the pixel q having the label black and white respectively. These probabilities can be approximated using loopy Belief Propagation which must compute these in order to find an approximate solution to the maximization in C of Eq. 4 [31]. Note that for this segmentation, the regularization is based on a geometric model and does not attempt to reduce the noise which is handled in Eq. 2.
The method starts by evaluating p(CX,C(q)=b) and p(CX,C(q)=w) for all pixels q which are used to fill the matrices M<sub>b</sub>, M<sub>w</sub>. Here, we denote the diagonal entry of M<sub>b </sub>corresponding to pixel q as M<sub>b</sub>(q): it is set to p(CX,C(q)=b). The matrix M<sub>w </sub>is similarly filled and each row of M<sub>b </sub>and M<sub>w </sub>is then normalized such that M<sub>b</sub>+M<sub>w</sub>=I. The matrix M<sub>d </sub>can be computed from the normalized M<sub>b </sub>and M<sub>w</sub>. The diagonal entry of M<sub>d </sub>corresponding to two neighbors q and q′ is M<sub>b</sub>(q)M<sub>b</sub>(q′)+M<sub>w</sub>(q)M<sub>w</sub>(q′). The energy function containing the terms of Eqns. 1, 2 and 3 can be minimized using gradient descent or other known methods. A few gradient descent iterations are performed before the recomputation of the probabilities. Those steps are repeated until a nonambiguous segmentation of X is obtained or until a maximum number of iterations is reached. In one implementation, the first segmentation is performed directly on I.
The class transition probabilities used in the previous section depend on the 3D structure of the scene. Explicitly, they depend on the projected displacement which is induced by the scene geometry and the internal and external parameters of the projector and camera. FIG. 1 illustrates a 2D projectorcamera system with a planar scene.
In FIG. 1, the distance along the optical axis between the camera and the scene (which is a plane) is d. The angle between the camera's image plane and scene plane is β, and α is the angle between the projector's optical axes and the camera's image plane. The center of projection of the projector is (c<sub>x</sub>,c<sub>z</sub>). The camera pixels q and q′ correspond to projector pixel T<sup>pc</sup>(q) and T<sup>pc</sup>(q′) respectively.
Using FIG. 1 as a reference, the projected displacement ΔD is
<FORM>ΔD(q,q′)=T<sup>pc</sup>(q)−T<sup>pc</sup>(q′) (5)</FORM>
where T<sup>pc </sup>is a function that applies the homography between the projector plane and the camera plane. FIG. 2 shows, for a 2D cameraprojector system, the value of the projected displacement ΔD for varying angles α and β. Note that the variation is nonnegligible. Also, ΔD is a scalar rather than a vector in this 2D case.
Referring to FIG. 2, the image illustrates the projected displacement as a function of angle α and β for a projector and camera having a focal length of 5 and a sensor element size of 0.1. The distance along the optical axis between the camera and the plane is 200. The projector is located at (20, 0) and the camera is located at the origin.
For now, it will be assumed that the camera and projector planes are rectified and that the scene is a single plane which is frontoparallel to the SL system (see left side of FIG. 3) [10]. In this case, the image viewed by the camera is that of the projector shifted along the horizontal axis. The magnitude of this displacement (the disparity) depends on the depth of the plane in the scene. The right side of FIG. 3 shows the camera and projector images corresponding to such a scene when the stripes in the projector (and camera) are one pixel wide. The camera pixels q and q′ belong to the class black and correspond to the same column in the projector. ΔD(q, q′) is (0, 0), while pixels q′ and q″ belong to different classes and are necessarily from adjacent columns (4 and 5) in the projector and ΔD(q′, q″)=(1, 0). When a smoothing penalty is applied between the labels of q and q′, the presence of a depth discontinuity is penalized. However, when smoothing is applied between q′ and q″, the absence of a depth discontinuity is penalized since a configuration having q′ and q″ match with the same projector pixel is favored. Thus, according to this rectified and frontoparallel model with one pixel wide vertical stripes, the probability of transition between q′ and q″ is 1, while it is 0 between q and q′. For a calibrated SL system in a general configuration, those probabilities can be estimated from the calibration parameters and the expected geometry of the scene. In one implementation, for the narrowest stripe, the probability of transition for horizontal neighbor was set to 0.5. This corresponds to a transition occurring at every 2 camera pixels and is the targeted value for a 3D scanner that would use the present invention. For the vertical transitions, the probability is set to 0.15. This is a crude estimate based on the number of distinct objects expected in the scene and the slant of the surfaces (i.e. we expect 15 transitions in an interval of 100 pixels). Note that the neighborhood interaction having a transition probability of 0.5 can be removed from N. This allows the use of a 2connected neighborhood, making it possible to compute the exact conditional probabilities using dynamic programming. Note that, as the stripes become wider, the difference between horizontal and vertical transition probabilities becomes smaller since there are far less horizontal transitions that are expected, and the number of vertical transitions is expected to remain the same. Since those wide stripes are less ambiguous, it is preferred that a 2connected neighborhood for all patterns be used. This results in a reduction of the computational burden without affecting the quality. The same neighborhood structure in Eq. 2 was also used in Eq. 4.
The system PSF H used in our method is defined as H(q)=H<sub>c</sub>(q)<img id="CUSTOMCHARACTER00002" he="2.79mm" wi="2.79mm" file="US20100034429A120100211P00001.TIF" imgcontent="character" imgformat="tif"/> W(q)<img id="CUSTOMCHARACTER00003" he="2.79mm" wi="2.79mm" file="US20100034429A120100211P00001.TIF" imgcontent="character" imgformat="tif"/> H<sub>p</sub>(q) where H<sub>c </sub>and H<sub>p </sub>are the PSF of the projector and camera and these vary with the distance to the scene. These are conventional lens PSFs, while W is the scene convolution matrix which depends on the distance to the scene, the calibration parameters of the SL system and surface properties. As an example, on the rectified configuration with a frontoparallel scene of FIG. 3, W would be a horizontally shifted diagonal matrix. The magnitude of the shift is equal to the disparity, and the magnitude of the diagonal entries depends on the surface albedo. Note that H may not sum to one because of the surface albedo. In the present invention, it is assumed that H does sum to one. However, the components of u<sub>b</sub>, and u<sub>w </sub>vary spatially and this allows the method to accommodate for the albedo of the scene.
Since it is expected that the scene depth will vary, the system PSF will also vary across the image. Many PSF representations have been designed to cope with spatially varying PSF [3, 15, 25, 7, 18]. Some of these approaches assume that the PSF is piecewise constant [15, 25, 7, 30], while others use coordinate transformations [27, 23], and some others use interpolation of the PSF across the image [3, 25, 18]. For this implementation of the invention, an interpolation approach based on an KarhunenLoève decomposition of the PSFs [18] is used. It allows a compact orthogonal decomposition of the PSFs. The bases are denoted H<sup>k</sup>. The minimization of Eq. 1 with regularization terms 2 and 3 becomes
<maths id="MATHUS00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><msup><mrow><mo></mo><mrow><mrow><munder><mo>∑</mo><mi>k</mi></munder><mo></mo><mrow><msup><mi>H</mi><mi>k</mi></msup><mo></mo><msup><mi>C</mi><mi>k</mi></msup><mo></mo><mi>x</mi></mrow></mrow><mo></mo><mi>i</mi></mrow><mo></mo></mrow><mn>2</mn></msup><mo>+</mo><mi>regularization</mi></mrow></mtd><mtd><mrow><mo>(</mo><mn>6</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>
where C<sup>k </sup>is a diagonal matrix. Each diagonal entry is the coefficient that scales the individual pixel of x prior to the convolution. More details can be found in [18]. The focus for this invention is on the image processing aspects of the pattern segmentation and it is assumed that the PSFs at different points in the image are known. The PSFs for other points are interpolated. We thus have all H<sup>k </sup>available beforehand, and the C<sup>k </sup>are estimated based on the correspondences obtained without the present invention.
During the deconvolution step of the invention, the most computationally expensive operation is the computation of H<sup>k</sup>C<sup>k</sup>X which is performed using a FFT [9]. The convolution for all KarhunenLoève bases can be computed simultaneously. There are many commercially available products that could be used to efficiently perform 2D FFT on programmable hardware. The regularization terms of Eq. 2 and Eq. 3 can be computed in linear time. The minimization of Eq. 6 is performed using a simple steepest descent method which converges slowly. Faster methods for calculating these the above also exist [9].
The segmentation can also be implemented on programmable hardware. An implementation of belief propagation on graphics hardware is presented in [4]. When using a twoconnected neighbourhood (as in one implementation of the invention), all the columns can be processed simultaneously. It is possible to further increase the amount of parallelism by reformulating Eq. 4. This reformulation is presented further below, and, in one implementation, was implemented using offtheshelf graphics hardware. The decoding of SL patterns using a 1024×768 camera is accomplished at a rate of more than 120 patterns per second using an old NVIDIA 6800 graphics card. General purpose computation using graphics hardware has greatly evolved in the last few years and the invention can be implemented using the highlevel programming language CUDA [12]. Other, newer graphics cards may also be used.
Since the steps of the method of the invention can be implemented on programmable hardware, an implementation of the invention running at video framerate is possible. One current software implementation of the invention runs on a computer with 8 DualCore AMD Opteron 8218 processors. At most, 6 cores are used simultaneously. The FFT code and BLAS implementation of the ACML are used also used in this implementation [11]. This implementation also uses the standard FFT driver of the ACML with OpenMP support enabled [13]. This implementation, which is nonoptimized, processes one 640×480 image in 20 seconds. Other implementations which use single or multiple core processors are also possible. As may be imagined, parallel processor architecture based computers, properly programmed, may provide better results than uniprocessor based machines.
Regarding results using one implementation of the invention, FIG. 4 contains an example of Gray code decoded under difficult acquisition conditions. The scanned image was acquired with both camera and projector out of focus and with a low SNR. The scene is composed of a single tilt plane, thus making it easier to assess the quality of the segmentation by visual inspection. The top left image in FIG. 4 illustrates the deconvolved image obtained by the present invention. The top right image in FIG. 4 is the original image. The middle left image is the result of one aspect of the invention while the middle right image is the result of standard thresholding methods. The bottom left image results from a Markovian segmentation while the bottom right image shows the difference histogram between the threshold value and the pixel intensities.
Referring again to FIG. 4, the result obtained by standard thresholding is shown [26]. Note how noisy the segmentation is. We also provide the results when segmenting using a Markovian framework. The method of [29] applied to one pattern was used. The method did significantly oversmooth the left part of the image.
This oversmooth solution and the noisy one of thresholding are explained by the histogram of the distance between the threshold value and the pixel intensities (see bottom right image in FIG. 4). More than 8.6% of the pixels have an intensity equal to the threshold value, thus making those very difficult to classify. In our deconvolved image (see top right image of FIG. 4), less than 0.6% of the pixels are in this situation, thereby making the segmentation much easier to perform.
FIG. 5 contains the intensity histogram of the images before and after the deconvolution for different sizes of stripes. The histograms in FIG. 5 are for the second, third, and fifth patterns of the Gray code. The images of the first pattern are shown in FIG. 4. Referring to FIG. 5, the reduced interclass ambiguity after applying the deconvolution should be noted. The pattern with large stripes are easier to decode since they contain fewer transitions. As an example, with the fifth pattern, both images have very few ambiguous pixels. Nevertheless, the number of pixels having an intensity in the interval ranging from 50 to 80 in the deconvolved image is smaller than the original by an order of magnitude (the class transition occurs at an intensity reading of 63).
Since linearity is preserved under projective transform, a linear regression was performed along each label discontinuity in the camera. The residual error of the fit was used as a metric to compare our approach with standard decoding on the different patterns. Table 1 presents the results. The most significant improvement is for the pattern with the narrowest stripes. FIG. 6 contains graphs of the variation of the residual error with the change of λ for the patterns 1 to 3 of Table 1. Note that the minimum residual error occurs with the same λ for all patterns. In our tests, we observed that the best λ is related to the noise level and seems independent of the width of the stripes. Note that γ was set to 0.5 in all our experiments. While λ is used to suppress noise, γ weighs the energy term of Eq. 3 which anchors the solution. This value was appropriate in the tests performed and the method is much less sensitive to changes of γ than of λ.
<tables id="TABLEUS00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center"/><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 1</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1"/></row><row><entry>Residual error for different Gray code patterns</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="105pt" align="center"/><colspec colname="2" colwidth="28pt" align="center"/><colspec colname="3" colwidth="84pt" align="center"/><tbody valign="top"><row><entry>pattern index</entry><entry>standard</entry><entry>ours</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1"/></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="105pt" align="center"/><colspec colname="2" colwidth="28pt" align="char" char="."/><colspec colname="3" colwidth="84pt" align="center"/><tbody valign="top"><row><entry>1</entry><entry>>0.351</entry><entry>0.127</entry></row><row><entry>2</entry><entry>0.150</entry><entry>0.125</entry></row><row><entry>3</entry><entry>0.180</entry><entry>0.133</entry></row><row><entry>4</entry><entry>0.138</entry><entry>0.133</entry></row><row><entry>5</entry><entry>0.143</entry><entry>0.139</entry></row><row><entry>6</entry><entry>0.143</entry><entry>0.134</entry></row><row><entry>7</entry><entry>0.129</entry><entry>0.114</entry></row><row><entry>8</entry><entry>0.190</entry><entry>0.157</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1"/></row></tbody></tgroup></table></tables>
Referring to the entries in Table 1, pattern 1 has the narrowest stripe. The images of the first pattern are shown in FIG. 4. For this pattern, some stripes are interconnected in the solution obtained by standard thresholding and they were manually removed before computing the error. This manual removal is arbitrary and the most conservative values that could be obtained are shown.
FIG. 7 shows the images associated with a scan of planar surfaces acquired in even harder conditions. The top 4 images are for a pattern with narrow stripes. The bottom 4 images are for a pattern which had wider stripes. For each data set or grouping of four images, the top left image shows the deconvolved image obtained by the invention, the top right image shows the original image, the bottom left image is the end result from applying the invention, and the bottom right image is the result of standard thresholding.
Using the conditions under which the scans of FIG. 7 were obtained and the patterns detailed in Table 1, the first 3 patterns in Table 1 were difficult to segment and standard thresholding yielded useless results for those patterns. Between 30% and 66% of the pixels have the same intensity in both images G and R. In the deconvolved image this percentage of pixels with the same intensity drops to 3.3%, allowing a significant improvement in the decoding.
FIG. 8 shows the images associated with a scan of two planes with different orientations. In FIG. 8, the top left image is a result of an application of the present invention while the top right image is a result of standard thresholding methods. The bottom left image is the original image G (normalized for visualization) while the bottom right image is an intensity histogram which contains some discretization artefacts.
Regarding the implementation of the present invention and computational enhancements which may be used, when the neighborhood of Eq. 4 is 2connected, the optimal solution can be computed using Dynamic Programming (DP). The maximization of Eq. 4 can be reformulated as an energy minimization with a Potts smoothing model [19]. The division and multiplication of the maximization are replaced by summation and subtraction in the minimization framework, making it more attractive for an implementation using programmable hardware. More details can be found in [19]. When a Potts smoothing model is used, DP has a complexity of Θ(N.L) where N is the number of sites and L is the number of labels [8]. The depth of the recurrence relations is linear in the number of sites. Lui et al. proposed a GPUbased SmithWaterman DP that exploits the parallelism already present in the standard recursive formulation [21]. A divideandconquer strategy may be used and a reduction of the depth of the recurrence relation may be accomplished in order to increase the amount of parallel computation. This is done at the cost of increasing the total amount of computation. It is assumed that the number of sites on a DP line is a power of two. If the number of sites on a DP line is not a power of two, the number of sites can be expanded to a power of two by adding dummy sites and setting their likelihood cost to a constant value. In a GPU, this can be efficiently done using the texture's clamping mode of OpenGL.
This concept is illustrated with reference to FIG. 9. FIG. 9 is a schematic illustration of a DP problem containing 8 sites and 2 labels. On the left side of FIG. 9, is the parallelization of the energy computation phase. The gray arrows represent the smoothing cost already being taken into account, while the black ones represent the smoothing cost computed at the current step. On the right side of FIG. 9 is the parallel computation of the recovery phase. The light gray boxes represent sites for which the label is fixed in the current step. The dark gray boxes represent sites for which the label has been fixed in the previous step. The number on a site is the step at which the label is determined. The arrows indicate the dependency between sites. As an example, the labels of sites 0 and 3 must be known before computation of the label of sites 1 and 2.
Again referring to FIG. 9, this use of a divide and conquer strategy and reducing the depth of the recurrence relation is illustrated on a small problem of 8 sites and 2 labels. In the first step, the energies for all the combinations of pairs of sites (0, 1), (2, 3), (4, 5) and (6, 7) are computed simultaneously. Four values are computed for each pair of sites. In the next step, the lowest energy for the combinations of labels of sites (0, 3) and (4, 7) are computed using the result of the previous step. Finally, the lowest energy for the combinations of labels of sites (0, 7) are computed. In general, this binary tree structure significantly reduces the number of steps required to process all the sites. The table t(m<sub>i,j</sub>,n<sub>i,j</sub>,k,l) is the lowest energy of all maps of sites in the interval [m<sub>i,j</sub>,n<sub>i,j</sub>] with site m<sub>i,j </sub>and n<sub>i,j </sub>at label k and l respectively. We define m<sub>i,j</sub>=i2<sup>j </sup>and n<sub>i,j</sub>=m<sub>i+1,j</sub>−1. Explicitly, the table t is defined inductively as
<maths id="MATHUS00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>t</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>e</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>k</mi></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>e</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>s</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>7</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>
where e(m, k) is the likelihood term related to the probability that site m has label k and s(m, n, k, l) is related to the probability that two neighbors m and n have label k and l respectively [19]. For j>1
<maths id="MATHUS00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><mstyle><mspace width="4.4em" height="4.4ex"/></mstyle><mo></mo><mrow><mrow><mrow><mi>t</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mi>min</mi><mrow><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><mrow><msup><mi>l</mi><mi>′</mi></msup><mo>∈</mo><mi>ℒ</mi></mrow></mrow></munder><mo></mo><mrow><msup><mi>t</mi><mi>′</mi></msup><mo></mo><mrow><mo>(</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo></mo><mstyle><mtext></mtext></mstyle><mo></mo><mstyle><mspace width="4.4em" height="4.4ex"/></mstyle><mo></mo><mi>with</mi></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>8</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msup><mi>t</mi><mi>′</mi></msup><mo></mo><mrow><mo>(</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>t</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msubsup><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><mi>k</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>t</mi><mo></mo><mrow><mo>(</mo><mrow><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>s</mi><mo></mo><mrow><mo>(</mo><mrow><msubsup><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>9</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>
and where n′<sub>i,j</sub>=(2i+1)2<sup>j−1 </sup>and m′<sub>i,j</sub>=n′<sub>i,j</sub>−1. The entry of t can be evaluated in Θ(N·L<sup>2</sup>) operations where N is the number of sites and L the number of labels. This is more than the Θ(N·L) of ordinary DP with the Potts smoothing model. However, the depth of the relation for the invention is in Θ(log N) rather than Θ(N). The minimal energy is min<sub>k,l</sub>t(0,N−1,k,l) where N−1 is the index of the last site. However, the entry in table t is not what is required to minimize Eq. 6. What is required is the minimum energy of a label map having site q at label k for all q and k. This is also known as the min marginal. These values can be computed from a table v(m<sub>ij</sub>,n<sub>ij</sub>,k,l) which is the lowest energy map (including all sites) with sites m<sub>ij </sub>and n<sub>ij </sub>having labels k and l respectively. Explicitly, the table v is defined inductively as
<FORM>v(0,N−1,k,l)=t(0,N−1,k,l) (10)</FORM>
and for {(m<sub>ij</sub>,m′<sub>ij</sub>,n′<sub>ij</sub>,n<sub>ij</sub>} <img id="CUSTOMCHARACTER00004" he="2.79mm" wi="2.79mm" file="US20100034429A120100211P00001.TIF" imgcontent="character" imgformat="tif"/> [0,N−1],
<maths id="MATHUS00005" num="00005"><math overflow="scroll"><mtable><mtr><mtd><mrow><mstyle><mspace width="4.4em" height="4.4ex"/></mstyle><mo></mo><mrow><mrow><mi>v</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msubsup><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><mi>k</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>l</mi><mo>,</mo><mrow><msup><mi>l</mi><mi>′</mi></msup><mo>∈</mo><mi>ℒ</mi></mrow></mrow></munder><mo></mo><mrow><msup><mi>v</mi><mi>′</mi></msup><mo></mo><mrow><mo>(</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>11</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mstyle><mspace width="4.4em" height="4.4ex"/></mstyle><mo></mo><mrow><mrow><mrow><mi>v</mi><mo></mo><mrow><mo>(</mo><mrow><msubsup><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>′</mi></msubsup><mo>,</mo><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>k</mi><mo>,</mo><mrow><msup><mi>k</mi><mi>′</mi></msup><mo>∈</mo><mi>ℒ</mi></mrow></mrow></munder><mo></mo><mrow><msup><mi>v</mi><mi>′</mi></msup><mo></mo><mrow><mo>(</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow></mrow></mrow><mo></mo><mstyle><mtext></mtext></mstyle><mo></mo><mstyle><mspace width="4.4em" height="4.4ex"/></mstyle><mo></mo><mi>with</mi></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>12</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msup><mi>v</mi><mi>′</mi></msup><mo></mo><mrow><mo>(</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>v</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><mi>t</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>m</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><msub><mi>n</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mrow><msup><mi>t</mi><mi>′</mi></msup><mo></mo><mrow><mo>(</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>13</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>
The minimum energy of a label map having site m<sub>i,j </sub>at label k is simply min<sub>l</sub>v(m<sub>i,j</sub>,n<sub>i,j</sub>,k,l). This can be computed similarly for a site n<sub>i,j</sub>. Using the equivalence between probabilistic and energy formulations [19], the entries of table v can be converted into the conditional probabilities required in order to fill the matrix M<sub>b </sub>and M<sub>w</sub>.
Sometimes, the label map of minimum energy is required rather than the min marginal. The right side of FIG. 9 shows the recovery process of this label map of minimum energy for a 2label problem containing 8 sites. At step 1, the labels of sites 0 and 7 are computed by looking only at the minimum entry of table t for the pair of sites (0, 7). At step 2, the labels of site 3 and 4 are found by using t for the pair (0, 3) and (4, 7) combined with the result of step 1 and the smoothing cost between site 3 and 4. The process is similar for step 3, except that the results of all previous steps are needed. The label map c<sup>k,l</sup><sub>i,j </sub>is the lowest energy map for all sites in the interval [m<sub>i,j</sub>,n<sub>i,j</sub>] having sites m<sub>i,j </sub>and n<sub>i,j </sub>at labels k and l respectively. Explicitly, the label map c<sup>k,l</sup><sub>i,j </sub>is defined inductively as
<FORM>(c<sub>i,j</sub><sup>k,l</sup>(m<sub>i,j</sub>), c<sub>i,j</sub><sup>k,l</sup>(n<sub>i,j</sub>))=(k,l) (14)</FORM>
and for {m′<sub>i′j′</sub>,n′<sub>i′j′</sub>} <img id="CUSTOMCHARACTER00005" he="2.79mm" wi="2.79mm" file="US20100034429A120100211P00001.TIF" imgcontent="character" imgformat="tif"/>]m<sub>i,j</sub>,n<sub>i,j</sub>[
<maths id="MATHUS00006" num="00006"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mo>(</mo><mrow><mrow><msubsup><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>k</mi><mo>,</mo><mi>l</mi></mrow></msubsup><mo></mo><mrow><mo>(</mo><msubsup><mi>m</mi><mrow><msup><mi>i</mi><mi>′</mi></msup><mo></mo><msup><mi>j</mi><mi>′</mi></msup></mrow><mi>′</mi></msubsup><mo>)</mo></mrow></mrow><mo>,</mo><mrow><msubsup><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>k</mi><mo>,</mo><mi>l</mi></mrow></msubsup><mo></mo><mrow><mo>(</mo><msubsup><mi>n</mi><mrow><msup><mi>i</mi><mi>′</mi></msup><mo></mo><msup><mi>j</mi><mi>′</mi></msup></mrow><mi>′</mi></msubsup><mo>)</mo></mrow></mrow></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mi>arg</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex"/></mstyle><mo></mo><mrow><msub><mi>min</mi><mrow><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><mrow><msup><mi>l</mi><mi>′</mi></msup><mo>∈</mo><mi></mi></mrow></mrow></msub><mo></mo><mrow><mrow><msup><mi>t</mi><mi>′</mi></msup><mo></mo><mrow><mo>(</mo><mrow><msup><mi>i</mi><mi>′</mi></msup><mo>,</mo><msup><mi>j</mi><mi>′</mi></msup><mo>,</mo><mrow><msubsup><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>k</mi><mo>,</mo><mi>l</mi></mrow></msubsup><mo></mo><mrow><mo>(</mo><msub><mi>m</mi><mrow><msup><mi>i</mi><mi>′</mi></msup><mo>,</mo><msup><mi>j</mi><mi>′</mi></msup></mrow></msub><mo>)</mo></mrow></mrow><mo>,</mo><mrow><msubsup><mi>c</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mrow><mi>k</mi><mo>,</mo><mi>l</mi></mrow></msubsup><mo></mo><mrow><mo>(</mo><msub><mi>n</mi><mrow><msup><mi>i</mi><mi>′</mi></msup><mo>,</mo><msup><mi>j</mi><mi>′</mi></msup></mrow></msub><mo>)</mo></mrow></mrow><mo>,</mo><msup><mi>k</mi><mi>′</mi></msup><mo>,</mo><msup><mi>l</mi><mi>′</mi></msup></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>15</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>
The depth of the relation is also in Θ(log N). Note that the present invention scales very well with the increase in length of a DP line.
Regarding the system which may be used to implement the invention, as noted above, a suitable computer system with the proper graphics hardware may be used. For the camera and projector elements of the system, suitable off the shelf components may be used.
It should be noted that while the above description describes using Gray code patterns, other patterns known to persons skilled in the art may also be used with the invention.
The invention described above in both general terms and in one specific implementation also extends the depth of field of a structured light system. The invention allows a significant improvement when performing depth measurements when working out of focus. It should be clear that applying the present invention to 3D scanners is only one of the myriad applications for which the invention may be used for. The invention may therefore be used with many existing technologies and may be modified to work with future technologies as well.
The specific implementation of the invention described above may be summarized as being an iterative method for processing monochromatic images. This method comprising the steps of providing a first image, providing a second image, the second image being an identical color opposite of said first image such that light areas in said first image are dark areas in said second image and dark areas in said first image are light areas in said second image, and generating a third image which is a difference between the first and second images. The third image is processed as described above in order to estimate the correspondences.
For this implementation, the third step is accomplished by deconvolving the degraded version of said the image and the point spread function and by segmenting the degraded version of the third image. This step may also involve using a regularization term based on probabilities of whether specific pixels of the third image are of a specific color.
While this specific implementation utilizes a second image which is derived from the first image, other implementations may use multiple second images derived from the first image to assist the segmentation and deconvolution processes. As well, multiple first images may be obtained from the cameraprojector system and these multiple first images may be used in other implementations to similarly assist in the segmentation and deconvolution processes.
It should be clear that while the description of the specific implementation of the invention above recounts a specific sequence involving segmentation and deconvolution, other sequences are also possible and are also covered as being part of the present invention. Specifically, the present invention may be implemented by segmenting and then deconvolving the image as well by deconvolving and then segmenting the image. A simultaneous segmentation and deconvolution of the image is also possible and is part of the present invention.
It should be noted that the above description describes both a general approach to implementing the invention as well as a specific implementation involving a binary stripe based pattern projected on to a subject. In other implementations, the invention may be embodied as software modules or hardcoded modules embedded in dedicated systems into which the physical characteristics of the structured light system are either entered by a user or stored (such as for fixed structured light systems). For some of these implementations, the pattern projected by the structured light system may be fixed with known characteristics. As noted above, prior knowledge regarding the pattern (or patterns) projected on to the system is desirable as such knowledge assists in the deconvolution and segmentation steps of the method.
The method steps of the invention may be embodied in sets of executable machine code stored in a variety of formats such as object code or source code. Such code is described generically herein as programming code, or a computer program for simplification. Clearly, the executable machine code may be integrated with the code of other programs, implemented as subroutines, by external program calls or by other techniques as known in the art.
Embodiments of the invention may be implemented in any conventional computer programming language. For example, preferred embodiments may be implemented in a procedural programming language (e.g. “C”) or an object oriented language (e.g. “C++”). Alternative embodiments of the invention may be implemented as preprogrammed hardware elements, other related components, or as a combination of hardware and software components.
The embodiments of the invention may be executed by a computer processor or similar device programmed in the manner of method steps, or may be executed by an electronic system which is provided with means for executing these steps. Similarly, an electronic memory means such computer diskettes, CDRoms, Random Access Memory (RAM), Read Only Memory (ROM) or similar computer software storage media known in the art, may be programmed to execute such method steps. As well, electronic signals representing these method steps may also be transmitted via a communication network.
Embodiments can be implemented as a computer program product for use with a computer system. Such implementation may include a series of computer instructions fixed either on a tangible medium, such as a computer readable medium (e.g., a diskette, CDROM, ROM, or fixed disk) or transmittable to a computer system, via a modem or other interface device, such as a communications adapter connected to a network over a medium. The medium may be either a tangible medium (e.g., optical or electrical communications lines) or a medium implemented with wireless techniques (e.g., microwave, infrared or other transmission techniques). The series of computer instructions embodies all or part of the functionality previously described herein. Those skilled in the art should appreciate that such computer instructions can be written in a number of programming languages for use with many computer architectures or operating systems. Furthermore, such instructions may be stored in any memory device, such as semiconductor, magnetic, optical or other memory devices, and may be transmitted using any communications technology, such as optical, infrared, microwave, or other transmission technologies. It is expected that such a computer program product may be distributed as a removable medium with accompanying printed or electronic documentation (e.g., shrink wrapped software), preloaded with a computer system (e.g., on system ROM or fixed disk), or distributed from a server over the network (e.g., the Internet or World Wide Web). Of course, some embodiments of the invention may be implemented as a combination of both software (e.g., a computer program product) and hardware. Still other embodiments of the invention may be implemented as entirely hardware, or entirely software (e.g., a computer program product).
A person understanding this invention may now conceive of alternative structures and embodiments or variations of the above all of which are intended to fall within the scope of the invention as defined in the claims that follow.
REFERENCES [1] M. Baker and J. Chcharo. Accuracy limitations introduced by digital projection sources in profilometric optical metrology systems. In Conf. on Optoelectronic and Microelectronic Materials and Devices, pages 261264, 2004.
 [2] L. Bar, N. Sochen, and N. Kiryati. Variational pairing of image segmentation and blind restoration. In Europ. Conf. on Comput. Vision, pages 166177, 2004.
 [3] A. Boden, D. Redding, R. Hanisch, and J. Mo. Massively parallel spatiallyvariant maximum likelihood restoration of Hubble space telescope imagery. J. Opt. Soc. Am. A, 13:15371545, 1996.
 [4] A. Brunton, C. Shu, and G. Roth. Belief propagation on the GPU for stereo vision. In Canad. Conf. on Comput. and Robot Vision, 2006.
 [5] C. Chen, Y. Hung, C. Chiang, and J. Wu. Range acquisition using color structured lighting and stereo vision. Image Vision Comput., 15:445456, 1997.
 [6] S. Esedoglu. Blind deconvolution of bar code signals. Inverse Problems, 20:121135, 2004.
 [7] M. Faisal, A. D. Lanterman, D. L. Snyder, and R. L. White. Implementation of a modified RichardsonLucy method for image restoration on a massively parallel computer to compensate for spacevariant point spread function of a chargecoupled device camera. J. Opt. Soc. Am. A 12, pages 25932603, 1995.
 [8] M. Gong and Y.H. Yang. Fast stereo matching using reliabilitybased dynamic programming and consistency constraint. In Int. Conf. on Comput. Vision, 2003.
 [9] P. C. Hansen. Deconvolution and regularization with Toeplitz matrices. Numerical Algorithms, 29:323378, 2002.
 [10] R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press, ISBN: 0521540518, second edition, 2004.
 [11] http://developer.amd.com/acml.jsp.
 [12] http://developer.nvidia.com/object/cuda.html.
 [13] http://www.openmp.org.
 [14] S. Inokuchi, K. Sato, and F. Matsuda. Range imaging system for 3D object recognition. In Int. Conf. on Pattern Recogn., pages 806808, 1984.
 [15] J. Kamm and J. G. Nagy. Kronecker product and SVD approximations in image restoration. Linear Algebra and its Applications, 284(13):177192, 1998.
 [16] T. P. Koninckx, I. Geys, T. Jaeggli, and L. Van Gool. A graph cut based adaptive structured light approach for realtime range acquisition. In Int. Symp. on 3D Data Process., Vis. and Transmiss., 2004.
 [17] T. P. Koninckx, P. Peers, P. Dutre, and L. Van Gool. Sceneadapted structured light. In IEEE Conf. on Comput. Vision and Pattern. Recogn., pages 611618, 2005.
 [18] T. Lauer. Deconvolution with a spatiallyvariant PSF. In Astronomical Data Analysis II, volume 4847, pages 167173, 2002.
 [19] S. Li. Markov random field modeling in computer vision. SpringerVerlag, 1995.
 [20] Y. F. Li and S. Y. Chen. Automatic recalibration of an active structured light vision system. IEEE J. Robotics and Automation, 19(2), 2003.
 [21] Y. Liu, W. Huang, J. Johnson, and S. Vaidya. GPU accelerated SmithWaterman. In Int. Conf. on Comput. Science, pages 188195, 2006.
 [22] L. Lucchese and S. Mitra. Color image segmentation: A stateoftheart survey. Image Processing, Vision, and Pattern Recognition, 67(2), 2001.
 [23] S. R. McNown and B. R. Hunt. Approximate shiftinvariance by warping shiftvariant systems. In The Restoration of HST Images and Spectra II, pages 181187, 1994.
 [24] M. Mignotte. A segmentationbased regularization term for image deconvolution. IEEE Trans. Image Process., 2006.
 [25] J. G. Nagy and D. P. O'Leary. Restoring images degraded by spatially variant blur. SIAM Journal on Scientific Computing, 19(4):10631082, 1998.
 [26] J. Salvi, J. Pages, and J. Batlle. Pattern codification strategies in structured light systems. Pattern Recogn., 37(4):827849, 2004.
 [27] A. A. Sawchuk. Spacevariant image restoration by coordinate transformations. J. Opt. Soc. Am. 64, pages 138144, 1974.
 [28] M. Sezgin and B. Sankur. Survey over image thresholding techniques and quantitative performance evaluation. J. Electron. Imaging, 13(1), 2004.
 [29] J. Tardif and S. Roy. A MRF formulation for coded structured light. In 3D Digit. Imag. and Model., 2005.
 [30] H. J. Trussell and B. R. Hunt. Image restoration of spacevariant blurs by sectional methods. IEEE Trans. Acoust. Speech, Signal Processing 26, pages 608609, 1978.
 [31] J. Yedidia, W. Freeman, and Y. Weiss. Exploring Artificial Intelligence in the New Millennium. 2003.
 [32] J. Zhang, B. Curless, and S. Seitz. Rapid shape acquisition using color structured light and multipass dynamic programming. In Int. Symp. on 3D Data Process., Vis. and Transmiss., pages 2436, 2002.