Computer Vision: Uncalibrated Stereo or Internet Scale 3D Photography

 Suppose you want to do 3D reconstruction with just a cellphone camera? One thing I can do is take an image, move over, and take another image. All we have to do to take a 3D model is to 1. Have a device taking 2 images, but you might have 1 camera take a picture, move over, and take another picture,  or you can  download and perform stereo on famous landmarks. These are used in many map applications, but I can anticipate a challenge here. Pictures may be taken with different cameras at different times of the day. The challenge is we do not know the relative location between the camera, unless you know the location, you can't shoot back rays for them to intersect. This is what we will discuss today, the most beautiful technical results in all of computer vision. 

An uncalibrated stereo can significantly expand the strength of stereo, because now we can make 3D modelling scenes with regular conventional cellphone cameras. This is called the internet scale stereo.

We won't need cameras, we can build large stuff from cameras on the internet. 

The last lecture we derived the image formation for a camera, and we have derived 3D image from its 2D coordinates, with a coordinate transformation from world-centric to camera-centric, then a prospective projection from 3D camera centric to 2D image coordinates. Both of these mapping can be expressed as matrices. This was all in the last lecture, with the mapping of the linear camera model, so I'm not going to repeat it again. 

The one key thing to remember is the intrinsic matrix depends on the internal properties of the camera, which means we can measure it once and it remains the same wherever the camera is.

These 2 matrixes can be combined into a camera projection matrix. We can also use 2 cameras to perform triangulations (shoot back rays from corresponding pixels) and compute the intersection, computing closed-form analytical expressions for the 3D coordinates of the scene point. 

In terms of maps, the camera's projection matrix has intrinsic and extrinsic components, to shoot back rays for both. The reason why this is so challenging is because with the calibrated stereo, we will always need a stereo camera to recover 3D geometry. As a result, our main goal is to "relax" this constraint and our goal is to get this into nearly unconstrained settings. Now, we want to use pretty much any camera and do something like that. It's a big enabling factor for many applications.

We talk about uncalibrated stereo, computing the 3D structure of a scene from 2 arbitrary positions, where we don't know the direction and the relative orientations. Why is this hard?

We cannot determine the location of the 3D point without determining the position of the second camera. It seems impossible to determine the location of the second camera. We have an interesting observation, and the rate going out the second pixel must intersect the first camera's ray. The key observation is that this fact the 2 rays must intersect does restrict the possible space. This ensures the position of the second camera cannot be completely arbitrary. We can extrapolate the same thing for different pixels. We know the rays must intersect. We don't know when we will intersect, but we know that we will intersect, providing sufficient constraints to determine the position of the second camera with relation to the first camera. We are going to formalize this idea in the picture, first proposed more than 30 years ago, changing conventional wisdom. 

We assume we know the intrinsic parameters for both the cameras, what is unknown (extrinsic) is the relative positions and orientation of the camera.

We first assume that camera matrices is known for both cameras. Find a few pairs of corresponding pixels, we can do this manually or use a technique like SIFT to perform this more automatically. 

We assume camera matrix K is known for each camera, and we find a few reliable corresponding points, and find out camera position, and compute the depth using triangulation.

We are going to look at how to use this pixels to find poses.

1. Assume Camera Matrix K is known for each camera

2. Find few reliable Corresponding Points

3. Find relative camera position T and orientation R

4. Find dense correspondence

5. Computer depth using triangulation.

2 scenes are related by a rotation and translation in 2 different coordinate systems.

The following is the equation after substituting epipolar constraints, and we determine an essential matrix.

In general, this isn't possible uniquely into a product of 2 matrices, but we use the fact that both matrices T and R have a special structure, such that E = TxR. The Tx is a skew symmetric matrix, meaning the transpose of the matrix is the skew symmetric of a matrix. The take home message is if E is known, we can calculate t and R (translation and Rotation independently.

If we can estimate E, we then can calculate both translation and rotation independently, as a relationship between the left and right 3D coordinates of a scene point, which are usually unknown. We don't know the 3D coordinates of a point, and unfortunately we cannot directly compute the central matrix. We want to derive a similar relationship in terms of corresponding image pixel coordinates. 

We represent the final matrix with an arbitrary scale factor, providing an expression for image coordinates. 

We take the equations and multiply them by  the inverse o the matrix, making the definition as terms of image matrix and the image coordinate's intrinsic matrix, and the corresponding pixel coordinates.

We take the equations and substitute them into the epipolar constraint. We can combine this into a single 3x3 matrix, making a compact location, and as 2D images of the left and right corresponding pixels, and have a Fundamental Matrix where

F = K1-1T E Kr-1

For each such pair of corresponding pixels, write some equations in terms of the corresponding matrix. The unknown, or the fundamental, is represented by a matrix, and the resulting equation is a linear equation. 

and we express this as a linear equation. 

we stash all the equations with a linear system, with a Known combination of U and V and  unknown batch of coordinates. 

This is very similar to a projection matrix. The fundamental matrix is defined only up to a scale, which sets the L2 norm of the vector F to be 1, which is a sum of squares of all of the entries of a matrix is set to 1. With this extra constraint we minimize A and f product, under the constraint that the L2 norm of the vector F is equal to 1. We can rearrange the entries in the unknown vector F to find the fundamental matrices, and we can recompute the essential matrix by multiplying by the intrinsic matrices of the  2 cameras.

E = KlTFKr. Finally we can decouple this matrix into a translation matrix to a rotation matrix.

We compute fundamental matrix, which then we find the essential matrix which can be decomposed to the translation matrix T and rotation matrix R.

Now that we have computed the relative orientation, we can proceed with the next steps just like we do with the regular calibrating stereo. I need to find dense correspondence, and then finally compute the depth using triangulation. 

The goal of finding correspondences is finding the disparity between certain left and right stereo pairs. For this, we can limit our search to a 1D horizontal line, but we are interested in more general configurations.

Do we have to search across the right image to find corresponding pixels, or can we again limit our search to a single line? 

 

The candidate locations will still lie on a line. Not necessarily a horizontal line, but it will still be a line.

For each possible point we can map it into the corresponding point in the camera, and this set of possible image locations is also a straight line, called the epipolar line. 

This makes the search a lot faster than a simple 2D image search.

Say we've already computed a fundamental image and we are given in an image. We want to find the equation of the epipolar line. To do this, we know the fundamental matrix and know the indices of the left pixel. we get the following and expand the equation out: 

Now we compute the depth using triangulation, computing 3D scene coordinates from pairs of corresponding pinhole projection image coordinates. Remember left and right pixels are corresponding pixels, and are in terms of the camera's intrinsic matrix. 

We need to know the relationship with the left and right center coordinates, and replace expression, with modified imaging equations. 

In total we have 4 linear equations and 3 unknowns and after some rearranging, we can combine all 4 equations into a linear system of equations, and simply solve for this using a least squares solution.

and we might take pseudoinverse, to determine Xr. 

Here is an example result for the pair of stereo images, to be able to recover the 3D structure of the image.

We can extend stereo idea to multiple images by doing 3D reconstructions and stitching these images together. We subsequently reconstruct an entire block.

Just to finish, internet images, it's a very good question and there's an intrinsic matrix, and the information is contained in a matrix data.