CamCal 008 Stereo Geometry Intro
Highlights: In this post we will learn about stereo geometry and we are doing this for a reason. We are going to talk about point and line duality and how to find the line given two points, or how to find the intersection point given the equation of two lines.
Tutorial Overview:
This post covers the following topics:
1. Projective Geometry
First of all, projective geometry is a fundamental topic for any computer vision practitioner. It encapsulates the relationship between multiple views because projective geometry is very convenient way of representing the projection operator which after all is how images are made.
The Projective Plane
Now, we are going to show you some math. 🙂 Well, the main idea is that a ray in the space is mapped to a point in the image.
Here we can see a ray that intersects the image plane at \(z= 1 \). And the idea is that every point \(\left ( x,y \right ) \) on that image plane at \(z= 1 \), is represented by this ray. And it intersects the image plane at \(\left ( x,y,1 \right ) \). But any point on this ray, \(\left ( sx,sy,s \right ) \), when projected through the center of the projection, would intersect the image plane at the same location. And that is what it means to be projectively similar. That is the relationship between these rays and the points in the image.
In 2D, for example, we take a 2D point \(\left ( x,y \right ) \) and to make it homogeneous we just add a \(1 \) to it and it becomes a homogeneous coordinate. We can think about that last coordinate as the thing that tells us about the scale. So when going from homogenous coordinates to regular we just divide by that scale value, that is what is shown here:
$$ p= \begin{bmatrix}x\\y\end{bmatrix}\rightarrow {p}’= \begin{bmatrix}x\\y\\1\end{bmatrix} $$
$$ {p}’= \begin{bmatrix}{x}’\\ {y}’\\ {w}’\end{bmatrix}\rightarrow p= \begin{bmatrix}{x}’/{w}’\\ {y}’/{w}’\end{bmatrix} $$
In particular homogeneous coordinates actually allow us to do a lot more. They are going to give us natural way of thinking about two dimensional lines. So, here we have our standard equation for a two dimensional line:
$$ ax+bx+c= 0 $$
And in homogeneous coordinates, it can be thought of as just a dot product:
$$ \begin{bmatrix}a & b & c\end{bmatrix}\begin{bmatrix}x\\y\\ 1\end{bmatrix}= 0 $$
$$ l= \begin{bmatrix}a & b & c\end{bmatrix}\Rightarrow \begin{bmatrix}n_{x} &n_{y} & -d\end{bmatrix} $$
Here \(\begin{bmatrix}a & b & c\end{bmatrix} \) can just be thought of as being the component of the unit vector in the direction of the normal between the origin and the line.
When we dot every point on that line with that normal, it has to be a distance \(d \) away so that would be \(-d \). But what is important, we are saying that the normal, \(\begin{bmatrix}a & b & c\end{bmatrix} \) is perpendicular to the point \(\begin{bmatrix}x\\y\\ 1\end{bmatrix} \), or to the ray that defines \(\begin{bmatrix}x\\y\\ 1\end{bmatrix} \). And in fact this perpendicular relationship is key to using projected geometry to define our points and lines.
Point and Line Duality
So to understand this perpendicular relationship, let’s look at the projective space. What does a line in the image correspond to in projective space?
If we have rays \(\left ( x,y,z \right ) \) satisfying:
$$ ax+bx+cz= 0 $$
a line is defined by this plane of rays that is intersecting the image plane. This plane of rays it is defined, like all planes are by a normal. So the line is formed by all the rays that are perpendicular to that normal, because the line is really just a plane in the projected space intersecting the image plane.
We can write this very simply in the same vector notation we were showing before.
$$ 0= \begin{bmatrix}a & b & c\end{bmatrix}\begin{bmatrix}x\\y\\ z\end{bmatrix} $$
in projective geometry and in the homogenous coordinate system, a line is also a homogenous 3-vector.
A line \(l \) is a homogeneous 3-vector and it is perpendicular to every point (ray) \(p \) on the line: \(l^{T}p= 0 \)
So a point is a homogenous 3-vector, but a line is also a homogenous 3-vector. In fact, this relationship that a point is a 3-vector and a line is a 3-vector is what is going to allow us to define this duality between points and lines. A line is defined by that normal to the plane and it is perpendicular to every point \(p \) that is on that plane. And in projective geometry, being perpendicular to a point means being actually perpendicular to the ray that defines that point. And that is what gives us some of that duality.
Now suppose we have two points, \(p_{1} \) and \(p_{2} \). Remember, points are actually these rays, \(p_{1} \) and \(p_{2} \) and we need to solve for the line that goes between them. Well, in projective geometry, it is actually pretty easy.
Since \(l \) is just perpendicular to both \(p_{1} \) and \(p_{1} \), we can take their cross product. $$l= p_{1}\times p_{2} $$ And \(l \) is the normal to the plane.
Next, what is the intersection of two lines?
We have got a line \(l_{1} \) and \(l_{2} \) and they are actually planes and you can see in the previous picture the lines that are made up of the planes where the planes intersect the image planes. So the \(l_{1} \) plane gives us this sort of horizontal line through \(p\) and the \(l_{2} \) plane gives us this sort of vertical line through \(p\).
But what if the point \(p \) is perpendicular to \(l_{1} \) and point \(p \) is perpendicular to \(l_{2} \)? Then what we need is a point whose ray is perpendicular to \(l_{1} \) and \(l_{2} \). So just as we had before in order to find the line that spans the two points, we took that cross product to find the line. And in order to find the point that is the intersection of two lines, we just take the cross product again:
$$ p= l_{1}\times l_{2} $$
So the points and lines form a dual in projective space and that means really given any formula, we can switch back and forth between what are the points and what are the lines. We are going to make use of this when we talk about, fundamental matrices. Remember that if we have a point in a stereo image, it has to appear somewhere on a line, that is the epipolar line and vice versa. So projective geometry allows us to go between points in lines.
2. Homogeneous Coordinates
In homogeneous coordinates, given two points, \(p_{1} \) and \(p_{2} \) ,if we want to find the line, it is easy. We just take their cross product \(l= p_{1}\times p_{2} \).
Likewise, if we have two lines:
$$ a_{1}x+b_{1}y+c_{1}= 0 $$
$$ a_{2}x+b_{2}y+c_{2}= 0 $$
In case that we want to know the intersection of those two lines, that actually took a little bit of work. If we have the equation of two lines and we need to find their intersection, we just need to cross them.
$$ l_{1}= \begin{bmatrix}a_{1} & b_{1} & c_{1}\end{bmatrix} $$
$$ l_{21}= \begin{bmatrix}a_{2} & b_{2} & c_{2}\end{bmatrix} $$
$$ p_{12}= l_{1}\times l_{2} $$
Ideal Points and Lines
In the final analysis, we need to talk about this notion of ideal points and ideal lines.
Let’s start with ideal points. We said that points are the intersection of a ray from the origin hitting the image plane. If the ray is parallel to the image plane, it will intersect the image plane in infinity. The idea is that this notion of an ideal point is essentially a point at infinity. With this in mind, the way you get a point at infinity is:
$$ p\cong \left ( x,y,0 \right ) $$
Scale being \(0 \), gives us a point at infinity. And if we want to think about that, so when we divide by zero, basically the \(x \) and \(y \) will go to infinity.
So that is an ideal point, however, there is the problem with an ideal point because the ray that is supposed to define it, is parallel to the image plane. Well, what about a line, where the normal that defines the plane is parallel to the image plane, and that is shown here.
You will notice that our normal has a \(z \) value of \(0 \). So it is parallel to the image plane. So, what it means is that the plane that it defines is also going to be perpendicular to the image plane, which means it is going to go right through the origin. So, the ideal line corresponds to the image that goes through the origin, or the principle point. And that is typically in the middle of the images, but remember, images might be offset.
So an ideal point is off at infinity, and an ideal line goes through the origin.
Summary
To summarize, here we talked about how can we get from points to lines, and vice-versa we also talked about the duality between them. We also showed how points and lines can be represented in homogeneous coordinates, which will be of great importance for the next post.
