Multiframe correspondence estimation

[0001] This invention relates to systems and methods of multiframe correspondence estimation.

[0002] Solving the correspondence problem is a classic problem in computer vision and image processing literature. It is a central to many 3-D (three-dimensional) related applications including stereopsis, 3-D shape recovery, camera calibration, motion estimation, view interpolation, and others. The correspondence problem involves finding a mapping relating points in one coordinate system to those in a second (or more) coordinate system (e.g., the mapping between pixels in one image of a given 3-D scene to those in a second image).

[0003] The traditional method for solving the correspondence problem uses image information directly. The correspondence mapping is determined for every pixel by examining its neighborhood and exploiting color consistency. In this approach an objective function (e.g. maximize correlation or minimize some error metric) is optimized for a given point in one image to find its corresponding match in all the other images. This passive approach works well for scenes that are distinctly textured and have consistent textures across all the images. This approach has difficulty when the scene is more uniform in color or when the illumination varies across the images. Typically, this approach produces only a sparse set of correspondences reliably and becomes more difficult for an arbitrary number of images. The matching algorithms that typically are used in this approach often are designed to establish correspondences between only two frames at a time, in which case ½·K·(K−1) dual-frame matches are required K cameras.

[0004] In contrast, structured light scanning algorithms traditionally use a calibrated camera-projector pair to recover 3-D shape information. In these approaches, a single active column in the projector's coordinate system results in a plane of light. The active plane of light is projected onto the scene of interest and the resulting contour is imaged by the camera. Then, for any image pixel p on the contour, its corresponding 3-D point is found by intersecting the 3-D ray passing through p and the 3-D plane equation.

[0005] Instead of specifying each plane individually, the planes may be specified in parallel using a set of temporally encoded patterns. Light patterns may be formed simply by considering the bitplanes of the binary representation of the column indices. The spatially varying light patterns form a temporal encoding of the columns in the projector's coordinate system. Every light pattern, consisting of binary vertical stripes of varying widths, is projected in succession. The camera decodes the projected patterns and builds up the appropriate bit sequence at every pixel location. Hence, given a pixel location in the camera, the corresponding column in the projector's coordinate system may be determined, and the corresponding 3-D point then may be calculated. Greater 3-D accuracy may be achieved by considering the transitions between adjacent columns.

[0006] The above-mentioned approaches based on temporally encoded patterns work well for arbitrary static scenes with a calibrated setup. There have been many approaches to further improve on the design of the projected light patterns and reduce the total number used. In one approach that requires a labeling process and a particular camera configuration, an uncoded grid pattern with landmark dots is projected. In another approach, a single color pattern is used to handle only neutrally colored scenes. Other approaches use sophisticated binary patterns and matching algorithms to capture dynamic but not very textured scenes.

[0007] The invention features systems and methods of multiframe correspondence estimation.

[0008] In one aspect of the invention, a sequence of patterns of light symbols that temporally encode two-dimensional position information in a so-called projection plane with unique light symbol sequence codes is projected onto a scene. Light patterns reflected from the scene are captured at one or more so-called capture planes. A correspondence mapping between multipixel regions in the capture plane and corresponding regions in the projection plane is computed based at least in part on correspondence between light symbol sequence codes captured at the capture plane and light symbol sequence codes projected from the projection plane.

[0009] In another aspect of the invention, a sequence of patterns of light symbols that temporally encode two-dimensional position information in a projection plane with unique light symbol sequence codes is projected onto a scene. At least two light patterns encode position information at different spatial resolutions. Light patterns reflected from the scene are captured at a capture plane. A correspondence mapping between the capture plane and the projection plane is computed based at least in part on correspondence between light symbol sequence codes captured at the capture plane and light symbol sequence codes projected from the projection plane.

[0010] In another aspect of the invention, a plane of light is projected onto a scene and is swept across the scene. Light contours reflected from the scene are captured at multiple capture planes, each pair of which is related by epipolar geometry with respect to the scene. A correspondence mapping between each pair of capture planes is computed based at least in part on intersection of captured light contours and epipolar lines computed for each of the capture planes.

[0011] In another aspect of the invention, a first light pattern is projected onto a scene. Light patterns reflected from the scene are captured at a capture plane. A coarse correspondence mapping between the capture plane and a reference plane is computed based at least in part on the captured light patterns. One or more undersampled regions of the scene are identified based at least in part on the computed coarse correspondence mapping. A second light pattern different from the first light pattern is projected onto the undersampled regions of the scene. A refined correspondence mapping between the capture plane and the reference plane is computed based at least in part on the light patterns captured during projection of the second light pattern.

[0012] The invention also features systems for implementing the above-described multiframe correspondence estimation methods.

[0013] Other features and advantages of the invention will become apparent from the following description, including the drawings and the claims.

[0032] In the following description, like reference numbers are used to identify like elements. Furthermore, the drawings are intended to illustrate major features of exemplary embodiments in a diagrammatic manner. The drawings are not intended to depict every feature of actual embodiments nor relative dimensions of the depicted elements, and are not drawn to scale.

I. Overview

[0033] A. Process Overview

[0034] FIG. 1 illustrates an example of a correspondence mapping between the coordinate systems of two imaging devices 10, 12 (each of these is referred to herein as a capture plane). In some embodiments described below, a correspondence mapping is computed by relating each capture plane to a third coordinate system 14 (referred to herein as the projection plane). The resulting mapping may serve, for example, as the first step in camera calibration, view interpolation, and 3-D shape recovery.

[0035] The multiframe correspondence estimation embodiments described below may be implemented as reasonably fast and low cost systems for recovering dense correspondences among one or more imaging devices. These embodiments are referred to herein as Light Undulation Measurement Analysis (or LUMA) systems and methods. The illustrated LUMA embodiments include one or more computer-controlled and stationary imaging devices and a fixed light source that is capable of projecting a known light pattern onto a scene of interest. Recovery of the multiframe correspondence mapping is straightforward with the LUMA embodiments described below. The light source projects known patterns onto an object or 3-D scene of interest, and light patterns that are reflected from the object are captured by all the imaging devices. Every projected pattern is extracted in each view and the correspondence among the views is established. Instead of attempting to solve the difficult correspondence problem using image information alone, LUMA exploits additional information gained by the use of active projection. In some embodiments, intelligent temporal coding is used to estimate correspondence mappings, whereas other embodiments use epipolar geometry to determine correspondence mappings. The correspondence mapping information may be sued directly for interactive view interpolation, which is a form of 3-D media. In addition, with simple calibration, a 3-D representation of the object's shape may be computed easily from the dense correspondences.

[0036] B. System Overview

[0037] Referring to FIG. 2, in some embodiments, a LUMA system 16 for estimating a correspondence mapping includes a light source 17, one or more imaging devices 18, a processing system 20 that is operable to execute a pattern projection and extraction controller 22 and a correspondence mapping calculation engine 24. In operation, pattern projection and extraction controller 22 is operable to choreograph the projection of light onto a scene and the capture of reflected light at each of the imaging devices 18. Based at least in part on the captured light, correspondence mapping calculation engine 24 is operable to compute a correspondence mapping 26 between different views of the scene. The correspondence mapping 26 may be used to interpolate different views 28, 29 of the scene. The correspondence mapping 26 also may be used to compute a 3-D model 30 of the scene after camera calibration 32 and 3-D computation and fusion 34.

[0038] In some embodiments, processing system 20 is implemented as a computer (or workstation) and pattern projection and extraction controller 22 and correspondence mapping calculation engine 24 are implemented as one or more software modules that are executable on a computer (or workstation). In general, a computer (or workstation) on which calculation engine 24 may execute includes a processing unit, a system memory, and a system bus that couples the processing unit to the various components of the computer. The processing unit may include one or more processors, each of which may be in the form of any one of various commercially available processors. The system memory typically includes a read only memory (ROM) that stores a basic input/output system (BIOS) that contains start-up routines for the computer, and a random access memory (RAM). The system bus may be a memory bus, a peripheral bus or a local bus, and may be compatible with any of a variety of bus protocols, including PCI, VESA, Microchannel, ISA, and EISA. The computer also may include a hard drive, a floppy drive, and CD ROM drive that are connected to the system bus by respective interfaces. The hard drive, floppy drive, and CD ROM drive contain respective computer-readable media disks that provide non-volatile or persistent storage for data, data structures and computer-executable instructions. Other computer-readable storage devices (e.g., magnetic tape drives, flash memory devices, and digital video disks) also may be used with the computer. A user may interact (e.g., enter commands or data) with the computer using a keyboard and a mouse. Other input devices (e.g., a microphone, joystick, or touch pad) also may be provided. Information may be displayed to the user on a monitor or with other display technologies. The computer also may include peripheral output devices, such as speakers and a printer. In addition, one or more remote computers may be connected to the computer over a local area network (LAN) or a wide area network (WAN) (e.g., the Internet).

[0039] There are a variety of imaging devices 18 that are suitable for LUMA. The imaging devices typically remain fixed in place and are oriented toward the object or scene of interest. Image capture typically is controlled externally. Exemplary imaging devices include computer-controllable digital cameras (e.g., a Kodak DCS760 camera), USB video cameras, and Firewire/1394 cameras. USB video cameras or “webcams,” such as the Intel PC Pro, generally capture images 30 fps (frames per second) at 320×240 resolution. The frame rate drastically decreases when multiple cameras share the same bus. Firewire cameras (e.g., Orange Micro's Ibot, Point Grey Research's Dragonfly) offer better resolution and frame rate (640×480 at 30 fps) and may be used simultaneously with many more cameras. For example, in one implementation, four Dragonfly cameras may be on the same Firewire bus capturing VGA resolution at 15 fps or more.

[0040] Similarly, a wide variety of different light sources 17 may be used in the LUMA embodiments described below. Exemplary light sources include a strongly colored incandescent light projector with vertical slit filter, laser beam apparatus with spinning mirrors, and a computer-controlled light projector. In some embodiments, the light source 17 projects a distinguishable light pattern (e.g., vertical plane of light or a spatially varying light pattern) that may be detected easily on the object. In some embodiments, the light source and the imaging devices operate in the visible spectrum. In other embodiments, the light source and the imaging devices may operate in other regions (e.g., infrared or ultraviolet regions) of the electromagnetic spectrum. The actual location of the light source with respect to the imaging devices need not be estimated. The illustrated embodiments include a computer-controlled light projector that allows the projected light pattern to be dynamically altered using software.

[0041] The LUMA embodiments described herein provide a number of benefits, including automatic, flexible, reasonably fast, and low-cost approaches for estimating dense correspondences. These embodiments efficiently solve dense correspondences and require relatively little computation. These embodiments do not rely on distinct and consistent textures and avoid production of spurious results for uniformly colored objects. The embodiments use intelligent methods to estimate multiframe correspondences without knowledge of light source location. These LUMA embodiments scale automatically with the number of cameras. The following sections will describe these embodiments in greater detail and highlight these benefits. Without loss of generality, cameras serve as the imaging devices and a light projector serves as a light source.

II. Intelligent Temporal Coding

[0042] A. Overview

[0043] This section describes embodiments that use intelligent temporal coding to enable reliable computation of dense correspondences for a static 3-D scene across any number of images in an efficient manner and without requiring calibration. Instead of using image information alone, an active structured light scanning technique solves the difficult multiframe correspondence problem. In some embodiments, to simplify computation, correspondences are first established with respect to the light projector's coordinate system (referred to herein as the projection plane), which includes a rectangular grid with w×h connected rectangular regions. The resulting correspondences may be used to create interactive 3-D media, either directly for view interpolation or together with calibration information for recovering 3-D shape.

[0044] The illustrated coded light pattern LUMA embodiments encode a unique identifier corresponding to each projection plane coordinates by a set of light patterns. The cameras capture and decode every pattern to obtain the mapping from every camera's capture plane to the projection plane. These LUMA embodiments may use one or more cameras with a single projector. In some embodiments, binary colored light patterns, which are oriented both horizontally and vertically, are projected onto a scene. The exact projector location need not be estimated and camera calibration is not necessary to solve for dense correspondences. Instead of solving for 3-D structure, these LUMA embodiments address the correspondence problem by using the light patterns to pinpoint the exact location in the projection plane. Furthermore, in the illustrated embodiments, the decoded binary sequences at every image pixel may be determined directly to determine the location in the projection plane without having to perform any additional computation or searching.

[0045] Referring to FIG. 3, in one embodiment, the exemplary projection plane is an 8×8 grid, where the lower right corner is defined to be (0,0) and the upper left corner is (7,7). Only six light patterns 36 are necessary to encode the sixty-four positions. Each pattern is projected onto an object 38 in succession. Two cameras C₁, C₂ capture the reflected patterns, decode the results, and build up bit sequences at every pixel location in the capture planes. Once properly decoded, the column and row may be immediately determined. Corresponding pixels across cameras will automatically decode to the same values. In the illustrated embodiment, both p1 and p2 decode to (row, column)=(3,6).

[0046] The following notation will be used in the discussion below. Suppose there are K+1 coordinate systems (CS) in the system, where the projection plane is defined as the 0^th coordinate system and the K cameras are indexed 1 through K. Let lowercase boldface quantities such as p represent a 2-D point (p_w,p_v) in local coordinates. Let capital boldface quantities such as P represent a 3-D vector (p_x,p_y,p_z) in the global coordinates. Suppose there are a total of N light patterns to be displayed in sequence, indexed 0 through N−1. Then, define image function I_k(p;n)=C as the three-dimensional color vector C of CS k at point p corresponding to light pattern n. Note that I₀(•;n) represents the actual light pattern n defined in the projection plane. Denote V_k(p) to be the indicator function at point p in camera k. A point p in camera k is defined to be valid if and only if V_k(p)=1. Define the mapping function M_ij(p)=q for point p defined in CS i as the corresponding point q defined in CS j. Note that these mappings are bi-directional, i.e. if M_ij(p)=q, then M_ji(q)=p. Also, if points in two CS's map to the same point in a third CS (i.e. M_ik(p)=M_jk(r)=q), then M_ij(p)=M_kj(M_ik(p))=r.

[0047] The multiframe correspondence problem is then equivalent to the following: project a series of light patterns I₀(•;n) and use the captured images I_k(•;n) to determine the mappings M_ij(p) for all valid points p and any pair of cameras i and j. The mappings may be determined for each camera independently with respect to the projection plane since from above
M_ij(p)=M_0j(M_i0(p))

[0048] Referring to FIG. 4, in some embodiments, the LUMA system of FIG. 3 for estimating multiframe correspondences may operate as follows.

• [0049] 1. Capture the color information of the 3-D scene 38 from all cameras (step 40). These images serve as the color texture maps in the final representation.
• [0050] 2. Create the series of light patterns 36 to be projected (step 42). This series includes reference patterns that are used for estimating the projected symbols per image pixel in the capture plane.
• [0051] 3. Determine validity maps for every camera (step 43). For every pixel p in camera k, V_k(p)=1 when the inter-symbol distance (e.g. the l₁₂ norm of the difference of every pair of mean color vectors) is below some preset threshold. The invalid pixels correspond to points that lie outside the projected space or that do not offer enough discrimination between the projected symbols (e.g. regions of black in the scene absorb the light).
• [0052] 4. In succession, project each coded light pattern onto the 3-D scene of interest and capture the result from all cameras (step 44). In other words, project I₀(•;m) and capture I_k(•;m) for camera k and light pattern m. It is important to ensure that there is proper synchronization between the projector and the cameras.
• [0053] 5. For every light pattern, decode the symbol at each valid pixel in every image (step 46). Because of illumination variations and different reflectance properties across the object, the decision thresholds vary for every image pixel. The reference images from step 2 help to establish a rough estimate of the symbols at every image pixel. Every valid pixel is assigned the symbol corresponding to the smallest absolute difference between the perceived color from the captured light pattern and each of the symbol mean colors. The symbols at every image pixel are then estimated by clustering the perceived color and bit errors are corrected using filtering.
  • [0054] 6. Go to step 44 and repeat until all light patterns in the series have been used (step 48). Build up bit sequences at each pixel in every image.
  • [0055] 7. Warp the decoded bit sequences at each pixel in every image to the projection plane (step 50). The bit sequences contain the unique identifiers that are related to the coordinate information in the projection plane. The image pixel's location is noted and added to the coordinate in the projection plane array. To improve robustness and reduce sparseness in the projection plane array, entire quadrilateral patches in the image spaces, instead of single image pixels, may be warped to the projection plane using traditional computer graphics scanline algorithms. Once all images have been warped, the projection plane array may be traversed, and for any location in the array, the corresponding image pixels may be identified immediately across all images.

[0056] In the end, the correspondence mapping M_k0(•) between any camera k and the projection plane may be obtained, and these mapping may be combined as described above to give the correspondence mapping M_ij(p)=M_0j(M_i0(p)) between any pair of cameras i and j for all valid points p.

[0057] Referring to FIG. 5, in one exemplary illustration of a 2-D depiction of a three-camera system, correspondence, occlusions, and visibility among all cameras may be computed automatically with the above-described approach without additional computation as follows. The light projector 17 shines multiple coded light patterns to encode the location of the two points, points A and B. These patterns are decoded in each of the three cameras. Scanning through each camera in succession, it is found that point a1 in camera 1 maps to the first location in the projection plane while b1 maps to the second location in the projection plane. Likewise for camera 3, points a3 and b3 map to the first and second locations, respectively, in the projection plane. Finally, a2 in camera 2 maps to the first location, and it is found that there are no other image pixels in camera 2 that decode to the second location because the scene point corresponding to the second location in the projection plane is occluded from camera 2's viewpoint. An array may be built up in the projection plane that keeps track of the original image pixels and traverse this array to determine correspondences. The first location in the projection plane contains the three image pixels a1, a2, and a3, suggesting that (a) all three cameras can see this particular point A, and (b) the three image pixels all correspond to one another. The second location in the projection plane contains the two image pixels b1 and b3 implying that (a) cameras 1 and 3 can view this point B, (b) the point must be occluded in camera 2, and (c) only b1 and b3 correspond.

[0058] The above-described coded light pattern LUMA embodiments provide numerous benefits. Dense correspondences and visibility may be computed directly across multiple cameras without additional computationally intensive searching. The correspondences may be used immediately for view interpolation without having to perform any calibration. True 3-D information also may be obtained with an additional calibration step. The operations are linear for each camera and scales automatically for additional cameras. There also is a huge savings in computation using coded light patterns for specifying projection plane coordinates in parallel. For example, for a 1024×1024 projection plane, only 22 binary colored light patterns (including the two reference patterns) are needed. In some implementations, with video rate (30 Hz) cameras and projector, a typical scene may be scanned in under three seconds.

[0059] Given any camera in the set up, only scene points that are visible to that camera and the projector are captured. In other words, only the scene points that lie in the intersection of the visibility frustum of both systems may be properly imaged. Furthermore, in view interpolation and 3-D shape recovery applications, only scene points that are visible in at least two cameras and the projector are useful. For a dual-camera set up, the relative positions of the cameras and the projector dictate how sparse the final correspondence results will be. Because of the scalability of these LUMA embodiments, this problem may be overcome by increasing the number of cameras.

[0060] B. Coded Light Patterns

[0061] 1. Binary Light Patterns

[0062] Referring back to FIG. 3, in the illustrated embodiment, the set of coded light patterns 36 separate the reference coordinates into column and row: one series of patterns to identify the column and another series to identify the row. Specifically, a set of K+L binary images representing each bit plane is displayed, where K=log₂(w) and L=log₂(h) for a w×h projection plane. This means that the first of these images (coarsest level) consists of a half-black-half-white image while the last of these images (finest level) consists of alternating black and white lines. To make this binary code more error resilient, the binary representation may be converted to a Gray code using known Gray-coding techniques to smooth black-white transition between adjacent patterns. In this embodiment, reference patterns consisting of a full-illumination (“all white”) pattern, and an ambient (“all black”) pattern are included. Note that only the intensity of the images is used for estimation since the patterns are strictly binary.

[0063] 2. Multicolor Light Patterns

[0064] Referring to FIG. 6, in another embodiment, a base-4 encoding includes different colors (e.g., white 52, red 54, green 56, and blue 58) to encode both vertical and horizontal positions simultaneously. In this manner, only N base-4 images are required, where N=log₄(w×h). An exemplary pattern is shown in FIG. 6 for an 8×8 reference grid. The upper left location in the reference grid consists of (white, white, white, white, white, white) for the base-2 encoding of FIG. 3 and (white, white, white) for the base-4 encoding of FIG. 6. The location immediately to its right in the projection plane is (white, white, white, white, white, black) for base-2 and (white, white, red) in the base-4 encoding, and so forth for other locations. In this embodiment, reference patterns consist of all white, all red, all green, and all blue patterns.

[0065] 3. Error Resilient Light Patterns

[0066] To overcome decoding errors, error resiliency may be incorporated into the light patterns so that the transmitted light patterns may be decoded properly. While adding error resiliency will require additional patterns to be displayed and hence reduce the speed of the capture process, it will improve the overall robustness of the system. For example, in some embodiments, various conventional error protection techniques (e.g. pattern replication, (7, 4) Hamming codes, soft decoding, other error control codes) may be used to protect the bits associated with the higher spatial frequency patterns and help to recover single bit errors.

[0067] In some embodiments, which overcome problems associated with aliasing, a sweeping algorithm is used. As before, coded light patterns are first projected onto the scene. The system may then automatically detect the transmitted light pattern that causes too much aliasing and leads to too many decoding errors. The last pattern that does not cause aliasing is swept across to discriminate between image pixels at the finest resolution.

[0068] Referring to FIG. 7A, in one exemplary four-bit Gray code embodiment, each row corresponds to a light pattern that is projected temporally while each column corresponds to a different pixel location (i.e., the vertical axis is time and the horizontal axis is spatial location). Suppose the highest resolution pattern (i.e. very last row) produces aliasing. In this case, a set of patterns is used where this last row pattern is replaced by two new patterns, each consisting of the third row pattern “swept” in key pixel locations; the new pattern set is displayed in FIG. 7B. Notice that the new patterns are simply the third row pattern moved one location to the left and right, respectively. In these embodiments, the finest spatial resolution pattern that avoids aliasing is used to sweep the remaining locations. This approach may be generalized to an arbitrary number of light patterns with arbitrary spatial resolution. In some embodiments, a single pattern is swept across the entire spatial dimension.

[0069] C. Mapping Multipixel Regions

[0070] In the above-described embodiments, the same physical point in a scene is exposed to a series of light patterns, which provides its representation. A single camera may then capture the corresponding set of images and the processing system may decode the unique identifier representation for every point location based on the captured images. The points seen in the image may be mapped directly to the reference grid without any further computation. This feature is true for any number of cameras viewing the same scene.

[0071] The extracted identifiers are consistent across all the images. Thus, a given point in one camera may be found simply by finding the point with the same identifier; no additional computation is necessary. For every pair of cameras, the identifiers may be used to compute dense correspondence maps. Occlusions are handled automatically because points that are visible in only one camera will not have a corresponding point in a second camera with the same identifier.

[0072] In some embodiments, the coded light patterns encode individual point samples in the projection plane. As mentioned in the multiframe correspondence estimation method described above in connection with FIG. 4, these positions are then decoded in the capture planes and warped back to the appropriate locations in the projection plane. In the following embodiments, a correspondence mapping between multipixel regions in a capture plane and corresponding regions in a projection plane are computed in ways that avoid problems, such as sparseness and holes in the correspondence mapping, which are associated with approaches in which correspondence mappings between individual point samples are computed.

[0073] 1. Mapping Centroids

[0074] Referring to FIG. 8, in some embodiments, the centroids of neighborhoods in a given camera's capture plane are mapped to corresponding centroids of neighborhoods in the projection plane. The centroids may be computed using any one of a wide variety of known techniques. One approach to obtain this mapping is to assume a translational model as follows:

• • [0075] Compute the centroid (u_c, v_c) and approximate dimensions (w_c, h_c) of the current cluster C in a given capture plane.
  • [0076] Compute the centroid (u_r, v_r) and approximate dimensions (w_r, h_r) of the corresponding region R in the projection plane.
  • [0077] Map each point (u,v) in C to a new point in R given by (w_c*(u−u_c)+u_r, w_r*(v−v_c)+v_r). That is, the distance the point in C is away from the centroid is determined and the mapping is scaled to fit within R.

[0078] In some embodiments, hierarchical ordering is used to introduce scalability to the correspondence results. In these embodiments, the lowest resolution patterns are first projected and decoded. This provides a mapping between clusters in the cameras' space to regions in the projection plane. The above-described mapping algorithm may be applied at any resolution. Even if not all the light patterns are used, the best mapping between the cameras and the projector may be determined by using this method. This mapping may be computed for every resolution, thereby creating a multiresolution set of correspondences. The correspondence mapping then may be differentially encoded to efficiently represent the correspondence. The multiresolution set of correspondences also may serve to validate the correspondent for every image pixel, since the correspondence results should be consistent across the resolutions.

[0079] In these embodiments, local smoothness may be enforced to ensure that the correspondence map behaves well. In some embodiments, other motion models (e.g. affine motion, splines, homography/perspective transformation) besides translational may be used to improve the region mapping results.

[0080] 2. Mapping Corner Points

[0081] Referring to FIG. 9, in an exemplary 4×4 projection plane embodiment, after decoding, the set of image points A′ is assigned to rectangle A in the projection plane, however the exact point-to-point mapping remains unclear. Instead of mapping interior points, the connectedness of the projection plane rectangles is exploited to map corner points that border any four neighboring projection plane rectangles. For example, the corner point p that borders A, B, C, D in the projection plane corresponds to the image point that borders A′, B′, C′, D′, or in other words, the so-called imaged corner point p′.

[0082] As shown in FIG. 10, the coded light patterns 36 of FIG. 3 exhibit a natural hierarchical spatial resolution ordering that dictates the size of the projection plane rectangles. The patterns are ordered from coarse to fine, and each associated pair of vertical-horizontal patterns at the same scale subdivides the projection plane by two in both directions. Using the coarsest two patterns alone results in only a 2×2 projection plane 60. Adding the next pair of patterns increases the projection plane 62 to 4×4, with every rectangle's area reduced by a fourth, and likewise for the third pair of patterns. All six patterns encode an 8×8 projection plane 64.

[0083] Referring to FIG. 11, in some embodiments, since it may be difficult in some circumstances to locate every corner's match at the finest projection plane resolution, each corner's match may be found at the lowest possible resolution and finer resolutions may be interpolated where necessary. In the end, subpixel estimates of the imaged corners at the finest projection plane resolution are established. In this way, an accurate correspondence mapping from every camera to the projection plane may be obtained, resulting in the implicit correspondence mapping among any pair of cameras.

[0084] In these embodiments, the following additional steps are incorporated into the algorithm proposed in Section II.A. In particular, before warping the decoded symbols (step 50; FIG. 4), the following steps are performed.

• [0085] 1. Perform coarse-to-fine analysis to extract and interpolate imaged corner points at finest resolution of the projection plane. Define B_k(q) to be the binary map for camera k corresponding to location q in the projection plane at the finest resolution, initially all set to 0. A projection plane location q is said to be marked if and only if B_k(q)=1. For a given resolution level l, the following substeps are performed for every camera k:
  • [0086] a. Convert bit sequences of each image point to the corresponding projection plane rectangle at the current resolution level. For all valid points p, the first l decoded symbols are decoded and used to determine the coordinate (c,r) in the 2^l+1×2^l+1 projection plane. For example, in the case of binary light patterns, the corresponding column c is simply the concatenation of the first l decoded bits, and the corresponding row r is the concatenation of the remaining bits. Hence, M_k0(p)=(c,r).
  • [0087] b. Locate imaged corner points corresponding to unmarked corner points in the projection plane. Suppose valid point p in camera k maps to unmarked point q in the projection plane. Then, p is an imaged corner candidate if there are image points within a 5×5 neighborhood that map to at least three of q's neighbors in the projection plane. In this way, the projection plane connectivity may be used to overcome possible decoding errors due to specularities and aliasing. Imaged corners are found by spatially clustering imaged corner candidates together and computing their subpixel averages. Set B_k(q)=1 for all corner points q at the current resolution level.
  • [0088] c. Interpolate remaining unmarked points in the projection plane at the current resolution level. Unmarked points with an adequate number of defined nearest neighbors are bilaterally interpolated from results at this or coarser levels.
  • [0089] d. Increment l and repeat steps a–c for all resolution levels l. The result is a dense mapping M_0k(•) of corner points in the projection plane to their corresponding matches in camera k.

[0090] In some embodiments, different known corner detection/extraction algorithms may be used.

• [0091] 2. Validate rectangles in the projection plane. For every point (c,r) in the projection plane, the rectangle with vertices {(c,r),(c+1,r),(c+1,r+1),(c,r+1)} is valid if and only if all its vertices are marked and they correspond to valid points in camera k.

[0092] D. Identifying and Correcting Bit Errors

[0093] Although, for the most part, the coded light patterns may be decoded properly at every image pixel, decoding errors may occur. In some implementations, the main sources of decoding errors are specularities and aliasing.

[0094] 1. Addressing Specularity Problems

[0095] In the case of specularities, regions in the scene reflect the illuminant to other portions of the scene. Because of this behavior, disjoint regions in the scene will decode to the same location in the projection plane. The artifact itself does not pose any problems but coupled with the sampling issues described above may lead to incorrectly computed centroids or corner points and hence incorrectly mapped correspondences. In some embodiments, the disjoint regions are filtered out and consistency is used to determine the correct mapping.

[0096] In some embodiments, the hierarchical nature of the above-described light patterns is exploited to handle decoding errors due to specularities, where surfaces in the scene reflect the incoming light to other parts of the scene, thereby causing multiple surfaces to incorrectly share the same code.

[0097] For example, the coded light patterns 36 of FIG. 3 include horizontal and vertical stripes at different spatial resolutions. Without loss of generality, consider only the vertical patterns; the horizontal patterns and more general 2-D patterns may be similarly considered. Every position in the decoded sequence of symbols for a given image pixel corresponds to one of the received light patterns. Ordering the light patterns according to resolution (coarse to fine) also orders the sequence of symbols (most significant symbol [MSS] to least significant symbol [LSS]). If only the MSS is considered for every image pixel, then the received light pattern is automatically clustered into N regions, where N represents the number of symbols. These clusters also refer to particular spatial regions in the projector's coordinate system. If the next most significant symbol is considered, then the received light pattern will be further clustered into a total of N² regions. Similarly, as more symbols are considered, the clusters are subdivided into smaller regions.

[0098] Clusters at one resolution typically should break into smaller, better-connected clusters at a finer resolution because, at finer resolutions, it is more likely that a given cluster will consist of points all from the same physical surface and not transcend depth boundaries. If, to the contrary, a cluster is found to break into two or more clusters with the same code, then part of the cluster may correspond to a specularity error. In some embodiments, a separable 1-D algorithm along both rows and columns may be employed to identify these situations at progressively finer resolutions. Iterative clustering algorithms then may be used to identify disparate clusters with the same code and eliminate the appropriate ones. In some implementations, this approach works fairly well for small regions of specularities.

[0099] In one exemplary illustration, FIG. 12A shows the clustering in the projection and capture planes. Note that the different shades of gray are simply used to label corresponding clusters and are not necessarily the light symbols transmitted in the light patterns. The MSS is 0 for shade 70 and 1 for shade 72. The next most significant symbol is shown in FIG. 12B. In this case, there are now four regions/clusters. Because of specularities, there are small clusters of shade 70 that appear to above and to the right of shade 74. At this finer resolution, shade 70 in the camera space has fragmented into multiple regions 70, 70′ with the same code. These regions are the ones that may be identified and filtered.

[0100] 2. Addressing Aliasing Problems

[0101] As mentioned above, another source of decoding errors is aliasing. This phenomenon may occur, for example, when the spatial resolution of the projection plane is finer than that of the camera's dimensions. For example, a projector could have XGA (1024×768) dimensions while the cameras have VGA (640×480) resolution. Depending on the relative positions of the equipment, it is possible that the perceived spatial frequency of the light patterns is much higher than the sampling rate of the cameras. In this case, the cameras tend to capture aliasing artifacts in the form of moiré patterns. These patterns, in turn, cause decoding errors at many image pixels since the decoded light patterns now no longer correspond to the original symbol colors. In some embodiments, hybrid solutions are used. In these embodiments, coded light patterns are used until the lowest allowable spatial frequency is reached and then this last pattern is swept to encode the remaining positions.

[0102] In some embodiments, a confidence metric is computed for every decoded symbol. For example, in one embodiment, the l₂ norm between a received color vector and the mean color vector of the assigned symbol is used to compute the confidence metric. In practice, this distance typically is small for transmitted light patterns below the Nyquist sampling rate and hence the symbol can be properly decoded. However, the distance may become large (sometimes halfway between two symbols), especially when spatial aliasing occurs and along pattern spatial transitions. In some embodiments, the transmitted light patterns are ordered in sequence (with the Gray code representation, adjacent stripes differ in code by exactly one bit), in which case the potentially erroneous symbols of the decoded sequence are marked and the results from neighboring image pixels may be used to correct the erroneously decoded symbol, as follows (the following algorithm may be applied to every image pixel):

• • [0103] Determine the nearest symbol based on distance to the mean color vector.
  • [0104] If the distance (i.e. confidence metric) is greater than some predetermined threshold, then mark this symbol as erroneous. Keep track of both the decoded symbol sequence as well as an error sequence corresponding to each symbol.
  • [0105] After every image pixel has been examined, apply a recursive algorithm to correct the erroneous symbols using neighboring information. For example, for a given image pixel with an erroneous symbol, look at the corresponding symbol of each of its eight neighbors. If at least two of these symbols are not erroneous, then take the mean value of the symbols to produce the new symbol for the current image pixel. In an alternative approach, the median of the valid symbols is considered. These steps are repeated until every erroneous symbol is corrected or until no more image pixels can be corrected.

[0106] In the end, this recursive filtering process helps to reduce decoding error due to transitions or specularities.

III. Scanning Light Plane

[0107] The LUMA embodiments described below estimate correspondences based on light plane patterns that are swept across the 3-D scene of interest. These embodiments exploit constraints due to the active projection as well as inherent constraints to the geometry of the camera set up. For the purpose of the following discussion, it is assumed that the camera set up consists of only two cameras; the approach easily extends to more than two cameras.

[0108] As shown in FIG. 13, in some embodiments, a light source 80 (in this example, it is modeled as a general light source with a translating vertical slit filter) projects a vertical plane of light 81 onto the scene 82 of interest. The projection is captured and extracted in each of two cameras, which have respective centers C₁, C₂, as projected contours 84, 86. In general, any point along one camera's contour corresponds to some point constrained to lie along the second camera's 1-D contour. For example, a point P lying on the surface of the object illuminated by the vertical plane will project to image points (p₁ and p₂ in the example) that lie on the projected contours in both cameras C₁, C₂ as long as P is visible to both cameras.

[0109] A second constraint due to the epipolar geometry of the camera configuration also applies. A scene point P, along with the two camera centers, C₁ and C₂, form a 3-D plane 88 that passes through all three points. This virtual plane 88 crosses the two cameras' image planes and generally intersects at two so-called epipolar lines 90, 92. Any point lying along the epipolar line of one camera has a corresponding point constrained to lie along the associated 1-D epipolar line of the second camera. For any point in one camera, its corresponding point must satisfy both constraints simultaneously.

[0110] Referring to FIG. 14, in some embodiments, a pair-wise correspondence mapping is computed using the system of FIG. 13, as follows:

• • [0111] 1. Capture the color information of the scene from all cameras (step 100). These images serve as the color texture maps for the final results.
  • [0112] 2. Project a single light plane onto the scene of interest and capture from all cameras (step 102).
  • [0113] 3. Disable the light plane and capture reference images from all cameras (step 104).
  • [0114] 4. Perform difference imaging to locate the contours in all images (step 106). The reference images from step 104 are used to quickly identify the location of the projected contours. Usually, the image captures occur in a much darker setting to ensure better contrast and more reliable results. In some embodiments, morphological dilation and thinning techniques are applied to improve the overall fidelity of the extracted contours.
  • [0115] 5. Traverse the contour points in one image and match the corresponding points in the second image (step 108). As described above, a given contour point in one image has a corresponding point in the second image that is constrained to lie along both the projected contour and the appropriate epipolar line. Since the two constraints are independent (i.e. the lines are not parallel), their intersection is precisely the corresponding point.

[0116] In some embodiments, to simplify the procedure, complete point lists are formed for all contour points with respect to each camera. Then, for every point p in the first image, its correspondent q in the other image may be found by traversing the appropriate list and solving for the epipolar constraint. The epipolar geometry for the two views may be represented as a single 3×3 matrix F, which is called the fundamental matrix. The signed distance d of a candidate contour point q′ in the second image to the epipolar line given by the projective expression d=q′^TF p may be determined (in this case, both p and q′ are defined in homogeneous coordinates). Note that this distance d is zero when the candidate point lies on the epipolar line, and hence is the corresponding match to p. In some embodiments, all candidate points are traversed and the absolute distance is minimized as long as it lies within some predetermined tolerance.

[0117] The above-described algorithm does not enforce a one-to-one mapping for contour points (i.e., multiple contour points of one image may be found to map to the same contour point in the second image). In other embodiments, the problem is cast as a global optimization and solved using dynamic programming. In another approach, minimization is performed starting with the second image to ensure that the two image points p and q are truly correspondents of each other. In some embodiments, the projective expression is sped up immensely using look up tables.

• • [0118] 6. Shift the light plane to the next position (step 110). Go to step 102 and repeat until the light plane has swept the entire width of the object (step 112).

[0119] In the end, a dense mapping between image points in the first camera's coordinate system to those in the second camera's coordinate system is produced. In the illustrated embodiments, it is assumed the scene of interest is fixed in position and does not move relative to the imaging set up. Note also that a light source that is computer-controlled makes it easier to identify the projected contours and discern the correct object color but is not necessary.

[0120] The above-described sweeping light plane embodiments produce dense correspondences automatically from a single viewpoint. It is a reasonably flexible technology that is independent of both light source location and orientation of light plane. The light source typically should be conveniently located and oriented, ideally placed to maximize visibility by the cameras. The light planes may be oriented arbitrarily but they should not be parallel to epipolar lines. The light plane orientation in the above-described embodiments is orthogonal to any given epipolar line.

[0121] The resulting correspondence information may be used directly for view interpolation after weak calibration (i.e. knowledge about the fundamental matrix or epipolar geometry must be established). With strong calibration (i.e. all camera parameters known or estimated), true 3-D information may be computed through triangulation.

[0122] Using this approach, in one implementation, an average-sized object (e.g., a human face) may be scanned with roughly 200–300 light plane patterns and may be captured in about a minute. The resolution of the final results depends on the camera resolution.

[0123] This approach also may be used with a single camera with respect to the projector's coordinate system given weak calibration between the two coordinate systems. For an imaged contour point in the capture plane, its correspondent is determined simply by intersecting the corresponding contour in the projection plane with the appropriate epipolar line. In this manner, dense correspondences between any camera and the projection plane may be established, thereby producing a computationally scalable approach to solve for multiframe correspondences among any number of cameras.

IV. Turntable-Based Embodiments

[0124] Referring to FIG. 15, in some embodiments, a multiframe correspondence system 120 includes multiple stationary computer-controlled imaging devices 122, 124, 126 (e.g., digital cameras or video cameras), a computer-controlled turntable 128 on which to place the object 129 of interest, a fixed lighting source 130 (e.g. strong colored incandescent light projector with vertical slit filter, laser beam apparatus with vertical diffraction, light projector) that is controlled by a computer 132. The cameras 122–126 are placed relatively close to one another and oriented toward the turntable 128 so that the object 129 is visible. The light source 130 projects a series of light patterns from the source. The projected light is easily detected on the object. In the illustrated embodiment, the actual location of the light source 130 need not be estimated.

[0125] Referring to FIG. 16, in some embodiments, the embodiments of FIG. 15 may be operated as follows to compute 3-D structure. For the purpose of the following description, it is assumed that there are only two cameras; the general case is a straightforward extension. It is also assumed that one of the camera viewpoints is selected as the reference frame. Let T be the number of steps per revolution for the turntable.

• • [0126] 1. Calibrate the cameras (step 140). Standard calibration techniques may be sued to determine the relative orientation, and hence the epipolar geometry, between the cameras from a known test pattern. The location of the turntable center is estimated by projecting the center to the two views and triangulating the imaged points.
  • [0127] 2. For every step j=1:T (steps 142, 144),
    • [0128] a. Perform object extraction for every frame (step 146). This is an optional step but may lead to more reliable 3-D estimation. The turntable is first filmed without the object to build up statistics on the background. For better performance, a uniform colored background may be added. Then, at every step and for both views, the object is identified as the points that differ significantly from the background statistics.
    • [0129] b. Project and capture light patterns in both views (step 148) and compute a correspondence mapping (step 150). Any of the above-described coded light pattern and sweeping light plane embodiments may be used in this step.
    • [0130] c. Compute 3-D coordinates for the contour points (step 152). With the estimated relative orientation of the cameras, this computation is straightforward by triangulation of the corresponding points. The color for the corresponding scene point comes from the multiple views and may be used for view dependent texture mapping.
  • [0131] 3. Impose some higher structure on the resulting cloud of points (step 154). Traditional triangular tessellations may be used to generate a model of the object. Note that the center and rotational angle of the turntable are important in order to form a complete and consistent model; the center's location is obtained above and the angle is simply computed from the number of steps per revolution. The 3-D model may be formed by formulating the model directly or by stitching together partial mesh estimates together.

[0132] In some implementations, the quality of the scan will depend on the accuracy of the calibration step, the ability to discriminate the projected light on the object, and the reflectance properties of the scanned object.

V. Iterative Multiframe Correspondence Estimation

[0133] Referring to FIG. 17, in some embodiments, active feedback is incorporated into the above-described multiframe correspondence mapping embodiments to improve three-dimensional (3-D) modeling of an object of interest. In these embodiments, basic shape recovery is achieved by projecting a first set of light patterns onto the scene and then detecting the projected light patterns (step 160). Based on the detected light patterns, a coarse model of the object is obtained (step 162). Next, problem areas like holes and poorly sampled areas are identified in the model (step 164). The system then projects modified light patterns that focus in on these areas (step 166) and capture their projections to obtain a refined model of the object (step 168). For example, finer grid patterns or cross-like patterns that sample every point in a given area may be projected. With known patterns, it is straightforward to estimate and predict the projected locations to sub-pixel accuracy, as described above. These steps are repeated until convergence (step 170). The result is an increase in the accuracy with which correspondences may be estimated through active feedback.

[0134] Further improvements may be made for objects that are well understood. One example is a human face. Based on prior experience, areas on a face that are troublesome for 3-D shape recovery (e.g., on the sides of the nose) may be identified immediately and directly targeted. For example, the above-described systems may obtain a coarse face model, do a rough estimation of the location of the eyes and nose, and then focus in on the troublesome areas. The light patterns may be tuned specifically for human faces a priori to give the best results.

V. Other Embodiments

[0135] Other embodiments are within the scope of the claims.

[0136] The systems and methods described herein are not limited to any particular hardware or software configuration, but rather they may be implemented in any computing or processing environment, including in digital electronic circuitry or in computer hardware, firmware, or software.