Ecse 6650 Computer Vision Project 2 3-d reconstruction

3-D Reconstruction

Zhiwei Zhu, Ming Jiang, Chih-ting Wu

1. 
   Introduction
   

Given a pair of stereo images, rectification determines a transformation of each image such that pairs of conjugate epipolar lines become collinear and parallel to the horizontal image axis. The importance of rectification is to reduce the correspondence problem from 2-D search to just 1-D search.

In the correspondence problem, we need to determine for each pixel in the left image, which pixel in the right image corresponds to it. The search will be correlation-based. Since the images have been rectified, to find the correspondence of a pixel in the left image does not require a search in the whole right image. Instead, we just need to search on the same row in the right image. Due to different occlusion in the both images, some pixels do not have correspondences.

In the step of reconstruction, by triangulating each pixel and its correspondence, we can compute the 3D coordinate at that pixel.

2. 
   Camera Calibration
   

In the full perspective projection camera, each calibration point projects onto an image plane point with coordinatesdetermined by the equation

and (2-2)

For each pair of 2-D and 3-D point i =0…N , we have equation as

, where . We can set up a system of linear equations as

where .

In general, equation (2-6) has no exact solution, due to errors in the sampling process, and has to be approximated by using a least square approach, i.e. minimizing by imposing the additional normalization constraint

(2-7)

Decomposing A into two matrices B and C, and V into Y and Z

, where , ,and

then the equation(2-7) can be written as
(2-10)
Taking partial derivatives of ε² with respect to Y and Z and setting them to equal to 0 yield
(2-11)

(2-12)
The solution to Z is the eigenvector of matrix. Given Z , then we can solve for Y . Substituting Y into || BY + CZ||² =λ. This could prove that solution Z corresponds to the eigenvector of the smallest positive eigenvalue of matrix.

2. 
   Camera Calibration Results
   

The left and right images taken from the same camera are shown in Figure 1.

Figure 1. The left and right images taken from the same camera

Table 1: The estimated intrinsic and extrinsic parameters

	Intrinsic Parameter Matrix	Rotation Matrix	Translation
Left Camera
Right Camera

From the above table, we can find out the fact that the estimated intrinsic parameters for left and right cameras are a little different from each other, although they are the same camera. When we measured the pixel coordinates of the grid corners in the left and right images, we cannot get the exact one. Usually, there are around 2 or 3 pixels error. Therefore, the measurement of the error can cause the deviation between the estimated left and right camera intrinsic parameters.

3. 
   Fundamental Matrix and Essential Matrix
   

Both the fundamental and essential matrices could completely describe the geometric relationship between corresponding points of a stereo pair of cameras. The only difference between the two is that the fundamental matrix deals with uncalibrated cameras, while the essential matrix deals with calibrated cameras. In this paper, we derived the essential and fundamental followed by the eight-point algorithm.

given 8 corresponding points or more we could get a set of linear equations whose null-space are non-trivial.

For any pair of matching points , from the epipolar geometry, we have

(3-1)
, or (3-2)
The equation corresponding to a pair of points and ,will be
(3-3)
From all points matches, we obtained a set of linear equation of the form
(3-4)
, where f is a nine-vector containing the entries of the matrix F, and A is the equation matrix. The fundamental matrix, and hence the solution vector f. This system of equation can be solved by Singular Value Decomposition (SVD). Applying SVD to A yields the decomposition USV^t with U, the column-orthogonal matrix and V , the orthogonal matrix and S, a diagonal matrix containing the singular values. These singular values σ₁≧σ₂≧…≧σ₉≧ 0 are positive or zero elements in decreasing order. In our caseσ₉ is zero (8 equations for 9 unknowns) and thus the last column of V is the solution.

2. 
   Essential Matrix
   

The Essential matrix contains five parameters (three for rotation and two for the direction of translation).

the Essential matrix is

2. 
   Experiment Results
   

In the following, we will show the computed fundamental matrix F and the essential matrix E:

E =

Figure 2 Triangulation

and (4-2)

Since the relationship between and is given by , we equate the terms to get

and (4-5)

R =

1. Rectification by Construction of New Perspective Projection Matrices

In the implementation of the rectification process, we have tried several methods. Though the algorithm given in the lecture notes can be proved analytically, we have found that the right rectified image has an obvious shift in vertical direction, thus corresponding image points can’t be located along the same row as the given point on the other image. We then switched to the algorithm given in the textbook. It turns out that this algorithm works well with the given image and camera data. However, the book doesn’t give a detailed proof of this algorithm. Suspecting the correctness of both algorithms, we then implemented the algorithm presented in Rectification with Constrained Stereo Geometry, where this algorithm has been proved analytically by A Fusiello. Our implementation of this algorithm has been proved to be successful, supported by the perfectly rectified image and the properties of the epipolar lines and epipoles.

1. 
   Calculate the intrinsic parameters and extrinsic parameters by camera calibration.
   
2. 
   Decide the positions of the optical center. The position of the optical center is constraint by the fact that its projection to the image plane is at 0.
   
3. 
   Calculate the new coordinate system. Let c1 and c2 be the two optical centers. The new x axis is along the direction of the line c1-c2, and the new y digestion is orthogonal to the new x and the old z. The new z axis is then orthogonal to baseline and y. Then the rotation part R the new projection matrix is derived based on this.
   
4. 
   Construct the new PPMs and the rectification matrices.
   
5. 
   Apply the new rectification matrixes to the images.
   

2. Resampling-Bilinear Interpolation

Figure 3 Bilinear Interpolation

The grayscale value at location (x, y) at each new warped pixel in J_new as B_x,y  This can be achieved in two stages:
First we defined B_x,0 = (1 - x) B_0,0 + xB_1,0 (5-6)

and B_x,1 = (1 - x) B_0,1 + x B_1,1. (5-7)

From these two equations, we get

B_x,y= (1 - y) B _x,0+ y B_x,1=(1 - y)(1 - x) B_0,0 + x (1 - y) B_1,0+ y (1 - x) B_0,1+ xyB_1,1 (5-8)

3. 
   _{Rectification Results}
   

6. 
   Draw the Epipolar Lines
   

Left: 1.0e+004 * (-1.8508 -0.0304)

Right: 1.0e+003 *(-1.8514 0.2502)

Epiloles after rectification:

Left: 1.0e+018 *( -1.0271 0.0000)

Right: 1.0e+018 *( -1.0068 0.0000)

Before rectification:

-0.0006 -0.0198 3.7996

-0.0005 -0.0199 3.9630

0.0000 -0.0198 4.9736

0.0001 -0.0199 5.0736

After rectification:

-0.0000 -0.0200 3.5044

-0.0000 -0.0200 3.7241

-0.0000 -0.0200 4.9826

The lines are shown in the figures

Epipolar lines before rectification
Epipolar lines after rectification

6. 
   Correlation-based Point Matching
   

1. 
   Correlation Method
   

where

2. 
   Disparity Map
   

Figure 5. Triangulation map

Where, is the disparity, b is the baseline distance, and f is the focus length.

After locating the corresponding points on the same row in the left and right images, we can compute the disparity for each matched pair one by one. Also, we can see that the depth Z is inversely proportional to the disparity d, in here, we set d = .
In order to illustrate the disparity for each matched pair, we first normalize the disparity values within the pixel intensity range (0-255). Thus we can display the disparity as pixel intensities. As a result, the brighter is the image point, the higher is the disparity and the smaller is the depth. Note that since we only consider well-correlated points on the maps, we set the disparity to 255 for lowly correlated points. Figure 3 shows the selected region in the left image to do the correlation-based point matching. Also, the corresponding searching region in the right image is cropped and shown.



Figure 6. (a) Left rock image (b) Right rock image
From Figure 3, we can see that the rock is in the left lower part of the image. The calculated disparity maps with different threshold value for correlation is shown in Figure 4. From the disparity maps, we can distinguish the rock from the background based on the pixel intensities very well because the rock is brighter than the background. Also, this shows that the rock is closer to the camera than the background. Due to the some mismatched points between the left and right points, some background points are also as bright as the rock part, but that is not very significant. Compared with rock part, most of the background points are darker.

(a) Threshold value = 0.3 (b) Threshold value = 0.4

(c) Threshold value = 0.5 (d) Threshold value = 0.6

Figure 7. The disparity maps with different threshold values (a) (b) (c) (d)

6. 
   3-D Reconstruction
   

Assume the object frame coincide with the left camera frame and let (c_l, r_l) and (c_r, r_r) be the left and right image points respectively. The 3-D coordinates (x, y, z) can be solved through the perspective projection equations from left and right image as

This equation system contains of 5 unknowns (x, y, z, _l, _r) and 6 linear equations, the solution can be obtained using the least-squares method. Let and represent the projective matrix for left image and right image, respectively, thus we have

The constructed 3D map are shown in Figure 8.

Figure 8. 3D reconstruction of rock pile

6. 
   Summary and Conclusion