Techniques for rapid stereo reconstruction from images

Stereo image reconstruction techniques are described. An image from a root viewpoint is translated to an image from another viewpoint. Homography fitting is used to translate the image between viewpoints. Inverse compositional image alignment is used to determine a homography matrix and determine a pixel in the translated image.

CROSS-REFERENCE TO RELATED APPLICATION

This patent application is a U.S. National Phase application under 35 U.S.C. §371 of International Application No. PCT/CN2009/000554, filed May 21, 2009, entitled TECHNIQUES FOR RAPID STEREO RECONSTRUCTION FROM IMAGES.

FIELD

The subject matter disclosed herein relates generally to stereo reconstruction by images from multiple vantage points.

RELATED ART

The application of graphics and visual computing is growing in areas such as three dimensional (3D) games, virtual worlds, mirror worlds (e.g., Google Earth), and immersive user interfaces. Stereo reconstruction aims to recover dense 3D scenes from images by two or more separately placed cameras, or equivalently, from images taken by the same camera but at different view positions. In stereo reconstruction, the camera parameters (internal and external) are known by camera calibration. Traditional stereo reconstruction methods are greatly limited either by accuracy or processing speed. Accordingly, there is an increasing demand for fast and accurate stereo reconstruction.

DETAILED DESCRIPTION

Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, the appearances of the phrase “in one embodiment” or “an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in one or more embodiments.

Two known existing solutions for stereo reconstruction include (1) stereo matching stereo reconstruction (e.g., normalized cross correlation (NCC)) and (2) color or photo-consistency optimization based stereo reconstruction. An example of solution (2) is described in Y. Furukawa and J. Ponce, “Accurate, Dense, and Robust Multi-View Stereopsis,” CVPR (2007) (hereafter “Furukawa's method”).

Photo-consistency measures the similarity of correspondence points in a stereo image pair. Photo-consistency may be defined over regions nearby corresponding points as:

where, A is a region centered at a corresponding point,ILand IRrefer to left (root) and right (translated) images,f( )is a metric function which may be ƒ(x)=∥x∥2,x is an image point position, andI(x)refers to the gray value at the point x.

FIG. 1illustrates a patch projection to a stereo image pair. The following is a description of the terms inFIG. 1:C1and C2: camerasO1and O2: camera center of two cameras (the cross point of the axes)b: baseline between two camerasI1and I2: images captured by C1and C2, respectivelyP: 3D pointP1, P2: projections of 3D point P at image planeE1, E2: epipole line passed to P1and P2π: the tangent plane of the 3D model surface at point Pn: the normal vector (direction) at P of the tangent planeH: homography transform induced by the plane πx=P1T(x): template window in the root imageW(x, p): homography warp window in the translated image

Furukawa's method projects a patch around 3D point P into a stereo image pair and computes a photo-consistency metric of corresponding projection points p1, p2. However, the position P is not accurate and Furukawa's method assumes that the position can be changed along one direction or within a cube nearby position P. A photo-consistence measurement exists for each position and the position with the largest photo-consistence measurement may be the optimized result. The speed of computation using Furukawa's method may be unacceptable from back-projection 3D patches into image planes and its accuracy suffers from the sampling rate near the original position.

Various embodiments provide photo-consistency optimization after a traditional NCC-based stereo matching method to improve the accuracy of stereo matching and stereo reconstruction. Various embodiments that use homography fitting convert the photo-consistency measure into an implicit function of pixel coordinates and derive analytical gradient. The optimization is based on homography fitting between image planes, which has an analytical gradient and can be solved efficiently.

Compared to the NCC matching based method, photo-consistency optimization of various embodiments that use homography fitting can provide much more accurate stereo reconstruction results through the correspondence optimization.

Various color or photo-consistence optimization methods (e.g., Furukawa's method) use back-projection of 3D patches into an image plane. However, back-projection of 3D patches into an image plane is computationally intensive and time consuming. Accordingly, various embodiments provide reduced computation time compared at least to Furukawa's method.

FIG. 2depicts a process for stereo reconstruction of a stereo image pair, in accordance with an embodiment. Block202includes receiving an input stereo image pair. The stereo image pair may be provided by one or more digital cameras or a stereo camera to a computer system through an input/output interface. The input stereo image pair has the same format of a general image. For example, each image is a 2D rectangle using (x,y) as coordinates to index pixels gray-value or color.

Block204includes rectifying the input stereo image pair so that their epipolar lines become horizontal or vertical.

Block206includes applying stereo matching methods on the rectified input stereo image pair. For example, block206may include applying normalized cross correlation (NCC) to establish the initial correspondences between pixels from this stereo image pair. A graphics processing unit (GPU) of a computer system may perform image pair rectification and stereo matching.

Block208includes, for each pixel in the root image, using homograph fitting to optimize photo-consistency between a pixel in the root image and the corresponding pixel in the translated image. For example, the root image is the left image inFIG. 1whereas the translated image is the right image inFIG. 1. A central processing unit of a computer system may perform the homograph fitting.

Block210includes triangulating optimized correspondence points to obtain a 3D scene from a single view point. Suitable techniques to perform blocks202,204,206, and210are described for example in H. Hirschmfuller et. al., “Real-Time Correlation-Based Stereo Vision with Reduced Border Errors,” pp 229-246, Vol. 47, IJCV 2002. A GPU of a computer system may perform triangulation of correspondence points to obtain a three dimensional view from a singe view point.

The computing procedure of stereo reconstruction in the process ofFIG. 2can be executed on a central processing unit (CPU) or graphics processing unit (GPU). Generally, the most computing complex part of stereo matching has massive data-level parallelism, which can be accelerated by using the vector processing or multi-thread processing capability of a GPU. The homography fitting is a sequential update procedure, which can be executed on a CPU.

The following describes an exemplary process performed in block208. Homography is the mapping between two point sets corresponding to the same 3D point sets but viewed from different cameras. Homography is used as a transformation for relating two corresponding point sets in two image planes. Referring toFIG. 1, given a point P1in a root image plane, a homography H induced by a tangent plane π (n is the normal of tangent plane) is used to find the corresponding point P2in the translated image plane. In other words, the homography H transfers P1to P2via the tangent plane π. The plane π is a tangent plane of the object surface at the corresponding 3D point P.

Various embodiments apply homography fitting of two regions with respect to homography parameters in the optimization of photo-consistency. Referring toFIG. 1, for each pixel P1in the root image, an m×m window T(x) is placed centered at the pixel P1, where x denotes the image coordinates of the pixels in the root window T(x). The corresponding pixel of x in the translated image is denoted as W(x; p)=H(p)·x, where H(p) is the homography transform. In various embodiments, H(p) is a 3×3 matrix given by internal and external parameters of a stereo camera and p is a 3-element parameter related to the depth and normal of the corresponding 3D point. Other types of homography transforms may be used.

The homography transform can be represented as:
H(p)=Kl·(R−tpT)Kr−1,where Kland Krare the intrinsic matrices of respective left and right cameras,R is the rotation matrix between the two cameras,t is the translation vector between the two cameras,p=n/d, where n is the normal vector of the plane π and d is the distance from the left camera center to the plane π.

The photo-consistency between a pixel x in the root image and the warp window, W(x; p), of the translated image, I, is defined as:

∑x∈A⁢[T⁡(x)-I⁡(W⁡(x;p))]2,
whereT(x) is a template window in the root image,I is a translated image, andW(x; p) is a homography warp window in the translated image.
The photo-consistency is an implicit and nonlinear function of the homography parameter p. In various embodiments, to improve photo-consistency, an inverse compositional image alignment (ICIA) process is used. The ICIA process is modified to provide an optimized homography matrix H(p) and an optimized corresponding pixel in the translated image. For example, a suitable ICIA process is described in: S. Baker, I. Matthews, Lucas-Kanade, “20 Years On: A Unifying Framework,” IJCV (2004). An exemplary ICIA process for homography fitting is described with regard to process300ofFIG. 3.

Block302includes receiving pixel point x=(u, v, 1) as well as parameters of camera pairs and an initial value of a homography parameter, p. The parameters may include camera intrinsic matrix K and extrinsics (e.g., rotation matrix R and translation vector t) and initial value of a homography parameter, p (defined earlier). Parameter p can be initialized by a traditional NCC-based method according to its definition p=n/d.

Block304includes determining the Hessian matrix for the translated image. For example, block304may include: (1) evaluating the gradient ∇T of the root window T(x); (2) evaluating the Jacobian for the right image W related to p at (x; p0), where the Jacobian is expressed as ∇J=∂W/∂p; and (3) determining the Hessian matrix of W related to p. The Hessian matrix may be expressed as H=Σx[∇T∇J]T[∇T∇J]. The Hessian matrix corresponds to an improved homography matrix.

Block306includes determining a pixel in the translated image W(x; p). For example, block306may include (1) determining I(W(x; p)) by warping the translated image I with W(x; p); (2) determining the error image I(W(x; p))−T(x); (3) computing the incremental step Δp=H−1Σx[∇T∇J]T[I(W(x; p))−T(x)]; and (4) updating the warp W(x; p) by determining W(x; p)=W(x; p)·W(x; Δp)−1. Items (1)-(4) of block306are repeated until an absolute value of the incremental step, |Δp|, is less than a limit value. For example, the limit value may be approximately 0.00001. Process300determines an optimized warp window (W(x,p)) that can be used to determine an optimized homography matrix, H=Σx[∇T∇J]T[∇T∇J]. The optimized homography matrix H(p) can be used to determine a corresponding pixel in the translated image W(x; p)·[u, v, 1]T.

The stereo homography fitting techniques described with regard toFIG. 2can be extended for application to multiple-view stereo reconstruction. Multi-view stereo can be viewed as the combination of results from multiple stereo pairs.FIG. 4depicts a process that can be used for a multi-view stereo reconstruction, in accordance with an embodiment. Block402receives multiple three-dimensional scenes from different stereo views. In one example, there are three views, namely views C1, C2, and C3. Binocular stereo pairs may be from views C1-C2, C2-C3and C1-C3.

Block404performs stereo homography and multi-view alignment and integration for each stereo pair. For each stereo pair, stereo homography described with regard toFIGS. 2 and 3is applied. The optimized correspondence by homography fitting may be defined as (x1, x2=w(x1)). After the optimized pair (x1, x2=w(x1)) is obtained, the pair can be triangulated with the known camera parameters according to the method described, for example, in R. Hartley and A. Zisserman, “Multiple View Geometry in Computer Vision,” Chapter 12, Cambridge Press, Second Version (2003). Triangulation may produce a three-dimensional point X12from the correspondence from each stereo pair, X12=triangulate(x1, x2).

Suppose X12is the triangulate result by C1-C2, X23is the result by C2-C3, and X13is the result by C1-C3and X12, X13, and X23correspond to the same 3D point. A 3D point, X, is a function of X12, X13, and X23, namely X=f(X12, X13, X23), where f( ) is a multi-view alignment and integration function and X12, X13, and X23are all three-dimensional points in world coordinates. In some embodiments, the multi-view alignment and integration technique can be an average function or best-fit function, although other functions can be used.

For instance, if f( ) is defined as the average function, then the 3D point is given by: X=(X12+X13+X23)/3.

If f( ) is defined as the best-fit function, the 3D point is chosen which (1) the normalized vector niis almost vertical to the camera plane or (2) nijhas smallest angle to the direction PO. Hence f( ) is defined as a selection function: X=Xi, where

Block406provides a three dimensional scene based on multiple view points. The 3D points determined as X in block404form a three dimensional scene.

FIG. 5Adepicts results of stereo reconstruction on the standard middlebury stereo evaluation set described, for example at http://vision.middlebury.edu/.FIG. 5Bdepicts a result from techniques that use homograph fitting based photo-consistency optimization. It can be seen that the techniques that use homograph fitting based photo-consistency optimization outperform the traditional NCC matching based method significantly at least in terms of image clarity.

Techniques that use homograph fitting based photo-consistency optimization provide similar results as Furukawa's method, but complete faster. Table 1 shows the execution time of these two methods for the stereo reconstruction task.

FIG. 6depicts a block diagram of computer system600, in accordance with an embodiment of the present invention. Computer system600may include host system602, bus616, and network interface620. Computer system600can be implemented in a handheld personal computer, mobile telephone, set top box, or any computing device. Host system602may include chipset605, processor610, host memory612, storage614, and graphics subsystem615. Chipset605may provide intercommunication among processor610, host memory612, storage614, graphics subsystem615, and bus616. For example, chipset605may include a storage adapter (not depicted) capable of providing intercommunication with storage614. For example, the storage adapter may be capable of communicating with storage614in conformance with any of the following protocols: Small Computer Systems Interface (SCSI), Fibre Channel (FC), and/or Serial Advanced Technology Attachment (S-ATA).

In some embodiments, chipset605may include data mover logic capable of performing transfers of information within host memory612, or between network interface620and host memory612, or in general between any set of components in the computer system600.

Processor610may be implemented as Complex Instruction Set Computer (CISC) or Reduced Instruction Set Computer (RISC) processors, multi-core, or any other microprocessor or central processing unit.

Host memory612may be implemented as a volatile memory device such as but not limited to a Random Access Memory (RAM), Dynamic Random Access Memory (DRAM), or Static RAM (SRAM). Storage614may be implemented as a non-volatile storage device such as but not limited to a magnetic disk drive, optical disk drive, tape drive, an internal storage device, an attached storage device, flash memory, battery backed-up SDRAM (synchronous DRAM), and/or a network accessible storage device.

Graphics subsystem615may perform processing of images such as still or video for display. For example, graphics subsystem615may perform video encoding or decoding. For example, graphics subsystem615may perform activities of a graphics processing unit described with regard to any activities described with regard toFIGS. 2-4. An analog or digital interface may be used to communicatively couple graphics subsystem615and display622. For example, the interface may be any of a High-Definition Multimedia Interface, DisplayPort, wireless HDMI, and/or wireless HD compliant techniques. Graphics subsystem615could be integrated into processor610or chipset605. Graphics subsystem615could be a stand-alone card communicatively coupled to chipset605.

Bus616may provide intercommunication among at least host system602and network interface620as well as other peripheral devices (not depicted). Bus616may support serial or parallel communications. Bus616may support node-to-node or node-to-multi-node communications. Bus616may at least be compatible with Peripheral Component Interconnect (PCI) described for example at Peripheral Component Interconnect (PCI) Local Bus Specification, Revision 3.0, Feb. 2, 2004 available from the PCI Special Interest Group, Portland, Oreg., U.S.A. (as well as revisions thereof); PCI Express described in The PCI Express Base Specification of the PCI Special Interest Group, Revision 1.0a (as well as revisions thereof); PCI-x described in the PCI-X Specification Rev. 1.1, Mar. 28, 2005, available from the aforesaid PCI Special Interest Group, Portland, Oreg., U.S.A. (as well as revisions thereof); and/or Universal Serial Bus (USB) (and related standards) as well as other interconnection standards.

Network interface620may be capable of providing intercommunication between host system602and a network in compliance with any applicable protocols such as wired or wireless techniques. For example, network interface may comply with any variety of IEEE 802.3, 802.11, or 802.16. Network interface620may intercommunicate with host system602using bus616. In one embodiment, network interface620may be integrated into chipset605.

Embodiments of the present invention may be provided, for example, as a computer program product which may include one or more machine-readable media having stored thereon machine-executable instructions that, when executed by one or more machines such as a computer, network of computers, or other electronic devices, may result in the one or more machines carrying out operations in accordance with embodiments of the present invention. A machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs (Compact Disc-Read Only Memories), and magneto-optical disks, ROMs (Read Only Memories), RAMs (Random Access Memories), EPROMs (Erasable Programmable Read Only Memories), EEPROMs (Electrically Erasable Programmable Read Only Memories), magnetic or optical cards, flash memory, or other type of media/machine-readable medium suitable for storing machine-executable instructions.

The drawings and the forgoing description gave examples of the present invention. Although depicted as a number of disparate functional items, those skilled in the art will appreciate that one or more of such elements may well be combined into single functional elements. Alternatively, certain elements may be split into multiple functional elements. Elements from one embodiment may be added to another embodiment. For example, orders of processes described herein may be changed and are not limited to the manner described herein. Moreover, the actions of any flow diagram need not be implemented in the order shown; nor do all of the acts necessarily need to be performed. Also, those acts that are not dependent on other acts may be performed in parallel with the other acts. The scope of the present invention, however, is by no means limited by these specific examples. Numerous variations, whether explicitly given in the specification or not, such as differences in structure, dimension, and use of material, are possible. The scope of the invention is at least as broad as given by the following claims.