The matching problems, while recovering the 3D objects, can be solved much more efficiently if the images are rectified. This step consists of transforming the images so that the Epipolar lines are aligned horizontally. In this case stereo matching algorithms can easily take advantage of the Epipolar constraint and reduce the search space to one dimension (i.e. corresponding rows of the rectified images).
In the previous project（ECSE 6650 Computer Vision, Project #2, 3-D Reconstruction）, we practically applied the rectification theory and recovered the 3D reconstruction, given a pair of stereo images . However, in the procedure of implement, three algorithms led to different results. They are from the class handout , textbook , and Fusiello et al .
In the first place, we were confused with the difference and constraints between and beneath these three algorithms, and thereby we supposed them as three different methods, and regarded them as worthy information to discover . Therefore we were full of interested to investigate the problems and decided to extend it as our final project.
After a series of mathematical approaches and numerical analysis, the results are not “significant” as we expected. Even though the results were not thrilling, we still won’t say this is a fruitless results. Actually, this project brought us to the profound levels of understanding the rectification.
2. Full Perspective projection Camera Model
The pinhole model we used is assumed to be the full perspective projection in homogeneous coordinated system. Thus, each calibration point projects onto an image plane point with coordinates determined by the following equation:
whereis a scale factor, is the homogeneous projection matrix,
is the intrinsic matrix, and is the extrinsic matrix. Hence, equation(2-1) can be rewritten as
3. Epipolar Geometry
Figure（1）Epipolar Geometry The performance of searching the corresponding elements is in the Epipolar geometry as Figure 1. shown. The three points [C1, C2, P] form what is called an epipolar plane and the intersections of this plane with the two image planes form the epipolar lines. The line connecting the two centers of projection [C1, C2] intersects the image planes at the conjugate points e1 and e2, which are called epipoles. Assume that the 3D point P projects into the two image planes as the points p1 and p2 which are expressed in homogeneous coordinates (u1, v1, 1) and (u2, v2, 1)
4. Analysis of The Rectification Algorithms
We need the extrinsic parameters of the stereo system to construct the rectification matrix. For a point in the world reference frame we have
where is the coordinates of the 3D point in the right camera frame is the coordinates of the 3D point in the left camera frame, and are the rotation transformation matrices of the point in the right and left camera frame respectively, while andare the rotation transformation matrices of the point in the right and left camera frame respectively.
From equation (4-1) and (4-2), we have
Since the relationship between and is given by , we equate the terms to get
as the extrinsic parameters matrices of the stereo system.
Once obtain these extrinsic parameters, we can then construct the rectification matrix which consists of a triple of mutually orthogonal unit vectors:
The following reasoning shows how the image is rectified with the rectification matrix and the adjustment made on the intrinsic camera parameters to ensure the correctness of the rectification process.
Apply the rectification matrix to both sides of
be coordinates of the point in the rectified left and camera frame, since
At this stage, we know from (14) that the point has the same y and z coordinates in both the rectified left and right camera frame. We then investigate the rectification effect on the left and right images.
We set the camera intrinsic parameters in rectification procedure as
These intrinsic camera parameters could be different from those we obtain through the calibration procedure, since those intrinsic parameters may be adjusted in order to ensure the rectification, but we have not been able to know the details up to now. The following argument reveals the details of the requirements on the intrinsic parameters.
By projecting the points and onto the image frames, we have
The objective of the rectification procedure is to make the points and have the same coordinates along the vertical direction in the images, which means
We already know from (14) that and
This is the same as
To make the above equation hold for any y and z coordinates, we must have
Meeting the constraints (4-22) will ensure the correctness of the rectification. So we must use a new set of camera intrinsic parameters to rectify the left and right image, since the parameters obtained from the camera calibration procedure is likely to have significant errors and can’t meet the constraints of (4-22), which will result different y coordinates for the same 3D point in the two images.
In practice, we can set the intrinsic parameters matrices of both cameras to their average or set them to either one, as long as they meet the requirements of (4-22). In the following steps, we will name this new camera intrinsic matrix as , which sill be applied to both left and right rectification.
For the rectification of the left image, relate the original image with the rectified image:
Where is the intrinsic matrix obtained from camera calibration, s are the scale factors.
From (4-23) and (4-24) then
The rectification procedure is realized by equation (4-25), while other methods such as bilinear may be used to improve the quality of the rectification image.
We have also noticed in previous experiments that not all of the rectified pixels can be seen in the rectified image. This is a serious problem if the object we want to do 3D reconstruction is not contained in the rectified image. Is there any method to adjust the rectification procedure so that we can control at least partially which part of the scene to show on the rectified image? While changing the focus length can keep all the points within images of the same size as the original, we propose an alternative approach by shifting the image center along the horizontal direction.
It is obvious from (4-21) and (4-22) that changing or will not destroy the rectification effect. By changing the image center, we can move some points outside of the images to inside of images and find matching points with new shifted images.
4.2 The rectification method in the textbook
The following discussion resembles that in the above section. The major issue is that the coordinate transformation defined in this method is different from that in the course lecture notes which results in different forms of rectification matrices.
Multiply both sides of (4-27) by Rrect
It is clear now that for such coordinates definition as (4-26), the rectification matrices for the left and right images are:
4.3. A compact algorithm for rectification of stereo pairs
In this section, we present another algorithm proposed by Fusiello et al.  to rectify a calibrated stereo rig of unconstrained geometry and mounting general cameras. We analyze the components of this algorithm step by step:
where is the projection matrix. Let’s represent the projection matrix as:
where is the intrinsic parameters and and are the rotation matrix and the translation vector. From equation (6-1), we can get the following equations:
where . Here, the focal plane is referred as the plane that is parallel to the image plane and contains the optical center. It is the locus of the points projected to infinity, hence its equation is . The two planes defined by and intersect the image plane in the vertical and horizontal axis of the image coordinates respectively. The optical center is the intersection of these three planes; hence its coordinates are the solution of
From the above equation, we can obtain the coordinates of the left and right camera Optical Centers as follows:
(2) The rotation matrix
After rectification, the rotated cameras have the same orientation but different positions. Positions of the optical centers are the same as the old cameras, while orientation changes because we rotate both cameras around the optical centers in such a way that focal planes become coplanar and contain the baseline.
※ The new Y axis is orthogonal to X (mandatory) and to k:
※ The new Z axis is orthogonal to XY (mandatory):
where is an arbitrary unit vector, which fixes the position of the new Y axis in the plane orthogonal to X.
So, the matrix R is as follows:
which are the X,Y and Z axes respectively of the camera standard reference frame, represented in world coordinates.
(3) How to do the rectification:
For the original left image, we have the following equation:
If we assume that the coordinate system of object frame has the same origin as the coordinate system of the camera frame, then the translation vector is equal to 0. Further, we have the following simplified equation:
For the rectified left image, we have the following simplified equation:
Combining the above two equations, we get the following equation:
Which is final equation used to do the image rectification.
5. Reconstruction from Rectified Image Pair
To original pixel coordinates can be recovered from the rectified coordinates (4-25) and (4-26)
The 3D coordinates can be solved through the perspective projection
With the above equations, we have
Let and represent the projective matrix for left image and right image respectively, thus we have
The combination of the equation (7-3)and(7-4), we have
The least-squares solution of the linear system is given by
The 3-D coordinates can be thus obtained from the two corresponding image points.
6. Experiments and Results:
We set the new intrinsic parameter matrices for the left and right images to different values.
(a) First Experiment
For the left image, we set the following intrinsic parameter matrix for the left camera:
The corresponding rectified image is shown in Figure (2).
Figure (2): the rectified left image For the right image, we set the following intrinsic parameter matrix for the right camera:
The corresponding rectified image is shown in Figure (3).
Figure (3): the rectified right image After obtaining the left and right rectified images, we found that the correspondence points in the left image can be found accurately in the same row of the right rectified image as shown in Figure (4). Also, from Figure (4), we found that the right rectified image is shifted to right by setting the a different value in the intrinsic parameter matrix , and the whole part of the stone are visible in the image.
Figure (4): the correspondence points marked by the white lines in the rectified left and right images.
(b) Second Experiment
For the left image, we set the following intrinsic parameter matrix for the left camera:
The corresponding rectified image is shown in Figure (5).
Figure (5): The rectified left image For the right image, we set the following intrinsic parameter matrix for the right camera:
The corresponding rectified image is shown in Figure (6).
Figure (6): the rectified right image Figure (7) will show that for each point in the rectified left image, the corresponding point in the rectified right image can be located in the same row of the right image.
Figure (7) The correspondence points marked by the white lines in the rectified left and right images From the above experiments, we made some conclusions as follows: First, for each point in the left rectified image, in order to locate its correspondence point in the rectified right image, we have to make sure that two entries of intrinsic parameter matrix, and , should be same in the new for both left and right cameras. Second, we can adjust the entry of the intrinsic parameter matrix to shift the rectified image to be visible.
7. Summary and Conclusions
In this project, three algorithms for image rectification for a pair of stereo images are studied. For each algorithm, the main steps are analyzed systematically, and the necessary verifications are given. Finally, we explored the necessary constraints for them to work successfully. Under the proposed constraints, via mathematical derivation, each of the three algorithms is proved to work successfully on the pair of stereo images. Experiments conducted on the real image also show that the correctness of each algorithm.
Reference: ECSE 6650 Computer Vision Class Handouts, RPI 2002
E. Trucco and A. Verri Introductory Techniques for 3-D Computer Vision, Prentice Hall.,1998
 Andrea Fusiello, Emamuele Trucco, Alessandro Verri. “A compact algorithm for rectification of stereo pairs”, Machine Vision and Applications, Springer-Verlag 2000.