Computer Vision and Algebraic Geometry

It might be weird for me to register for the computer vision course alongside my Master’s thesis¹, but as my friends know, I’m pretty much originally a gamer before I’m even started to be interested in mathematics (and then computer science). After playing some video games, I started to form another dream of building my own robot! Interesting!

So I asked Mr. Dae (i.e. Assoc. Prof. Nattee Niparnan, Computer Engineering, Chulalangkorn University) to teach me robotics, and I sent him the current course offerings at ETH. He suggest me to begin with Computer Vision, so here I am.

(Also, if at some point, I turn out to be too busy doing these than spending adequate time with the thesis, I might consider withdrawing from the courses later on… For now let’s just see how it goes…)

Now, as a chuunibyou and edgy person as I am right now, I’m often attracted to recasting things into an algebro-geometric language.

Note: I wrote this post myself, but I used ChatGPT to catch some of the errors. In particular, let me put a big disclaimer here. Disclaimer: Some statements are false! I try to fix them as much as I could, and the main idea should still work, but there may be bugs and I don’t have enough time and energy to polish to the cleanest point, so that’s it.

The Basics of Geometry

Let us fix a base field $\mathbb{C}$ and recall the basic settings. The affine $n$ -space, denoted by $\mathbb{A}^n$ , is simply the set $\mathbb{C}^n$ without the additive structure of a vector space. We equip this with Zariski topology and the sheaf of regular functions to see that this is just the scheme $\operatorname{Spec} \mathbb{C}[z_1, \dots, z_n]$ over $\operatorname{Spec}\mathbb{C}$ .

Now we go to the projective case, which is the main protagonist of the relevant geometry here. We define the projective space $\mathbb{P}^n$ as $\mathbb{C}^{n+1}/{\sim}$ , where $(z_0, z_1, \dots, z_n) \sim (z'_0, z'_1, \dots, z'_n)$ whenever there exists some $\lambda \in \mathbb{C}^\times$ such that $z'_i = \lambda z_i$ for all $i \in \{0, \dots, n\}$ . Equipping this with Zariski topology and the sheaf of regular functions turns this into the scheme $\operatorname{Proj} \mathbb{C}[z_0, \dots, z_n]_\bullet$ over $\operatorname{Spec}\mathbb{C}$ .

Now, there is another important construction, which many books don’t appreciate but I think we should introduce it here: the dual projective space. We define $\mathbb{P}^{n*}$ to be the projectivization of the vector space $(\mathbb{C}^{n+1})^*$ of $\mathbb{C}$ -linear forms of $\mathbb{C}^{n+1}$ . We can think of an element of $\mathbb{P}^{n*}$ as a hyperplane, because the zero locus of a projectivized linear form is really just a hyperplane in $\mathbb{P}^n$ .

There is now an obvious map $\mathbb{P}^n \to \mathbb{P}^{n*}$ . How? Let the point $[w_0 : \dots : w_n]$ be sent to the linear form $(z_0, \dots, z_n) \mapsto \sum_{i=0}^n w_i z_i$ , and then collapsed through the projectivization into its class in $\mathbb{P}^{n*}$ . In this blog post, my decision is to denote this map by the symbol $\intercal$ , and write $x \mapsto x^\intercal$ for such operation (for $x \in \mathbb{P}^n$ ). You may appreciate (or hate) this notation later on.

Convention: Here I try to adapt to both the culture of algebraic geometry and the culture of computer vision, so, for a point $p \in \mathbb{P}^n$ (with a normal font for $p$ ), this is just a point, and the homogeneous coordinates are written $p_0, p_1, \dots, p_n$ . For a single point $p$ there may be multiple choices for its coordinate, i.e., if $p_0, p_1, \dots, p_n$ is a coordinate, then one can just pick $\lambda \in \mathbb{C}^\times$ and then $\lambda p_0, \lambda p_1, \dots, \lambda p_n$ would also be another coordinate. The convention is that if I write $p = [p_0 : \dots : p_n]$ then this means “let $p_0, \dots, p_n$ be any possible form of the homogeneous coordinates for $p$ ; it doesn’t matter what we pick”. The “it doesn’t matter what we pick” is an assertion, and technically has to be check every time I write this and claim something, but we will implicitly keep this in the back of our minds and just work with it (and stop ourselves from doing any operation that isn’t invariant under the choice of such coordinate). Now, when I write $\mathbf{p}$ (in boldface), it is meant to be understood as the vector $\begin{pmatrix}p_0\\p_1\\\vdots\\p_n\end{pmatrix} \in \mathbb{C}^{n+1}$ or also the corresponding matrix in $\operatorname{Mat}_{(n+1) \times 1}(\mathbb{C})$ . That is, boldfaces represent viewing things in a linear algebraic manner, while normal font represents viewing things abstractly (and also in the algebro-geometric sense). For points, we will often use $\mathbf{x}$ to denote the vector of coordinates corresponding to a point in $\mathbb{P}^2$ and use $\mathbf{X}$ to for a point in $\mathbb{P}^3$ .

Points and Lines

There is a computational trick that I didn’t know before. If $p, q \in \mathbb{P}^2$ are 2D projective points, then what would be the line passing through them? Before that, what is a line in $\mathbb{P}^2$ ? Algebraically we may think of a line as a projective subvariety defined as the zero locus of a linear polynomial. And this can be interpreted computationally easily: let $a, b, c \in \mathbb{C}$ be not all zero, then the projective variety $V_{\mathbb{P}^2}(az_0 + bz_1 + cz_2)$ is said to be a line. And we can then interpret this linear-algebraically: a coordinate $(z_0, z_1, z_2)$ is on the line whenever $az_0 + bz_1 + cz_2 = 0$ (and then projectivize this). What I want to say is that the projectivization of the linear form $(z_0, z_1, z_2) \mapsto az_0 + bz_1 + cz_2$ is an element of $\mathbb{P}^{2*}$ corresponding to this line! Therefore, a line in $\mathbb{P}^2$ is just an element of $\mathbb{P}^{2*}$ (one has to check the reverse correspondence, but this is not hard).

An element of $\mathbb{P}^{2*}$ can therefore be represented by homogeneous coordinates $[a : b : c]$ , where its line locus is $\{z \in \mathbb{P}^2 \colon az_0 + bz_1 + cz_2 = 0\}$ . This means, for a line to pass through $p$ and $q$ , such line, parametrized by $[a : b : c]$ , must satisfy

$\begin{cases}ap_0 + bp_1 + cp_2 = 0\\aq_0 + bq_1 + cq_2 = 0.\end{cases}$

What are the answers to this linear system of equations? Surprisingly, a clean answer here is $\begin{pmatrix}a\\b\\c\end{pmatrix} = \mathbf{p} \times \mathbf{q}$ (cross product). We can check this explicitly. Recall that

$\mathbf{p} \times \mathbf{q} = \begin{pmatrix}p_1q_2 - p_2q_1\\p_2q_0 - p_0q_2\\p_0q_1 - p_1q_0\end{pmatrix}.$

You can plug this into the equations and see that they are satisfied. Now, I think the uniqueness question isn’t hard. By linear algebra, the solution space $(a, b, c) \in \mathbb{C}^3$ cut out by two linear equations is a one-dimensional subspace (if $p \ne q$ ), or a two-dimensional subspace (if $p = q$ ). For the case of $p \ne q$ , by projectivization, such one-dimensional subspace reduces to a single object in $\mathbb{P}^{2*}$ . This is the line passing through $p$ and $q$ . For the $p = q$ case there are still infinitely many lines passing through them, and so there is not much we can do to try and extract one correct line. We have:

Proposition 1. For a pair $(p, q) \in (\mathbb{P}^2)^2$ of distinct points, there exists a unique line passing through them. If $p \ne q$ then $(\mathbf{p} \times \mathbf{q})^\intercal \in \mathbb{P}^{2*}$ is that line. $\square$

Now, in computer vision, we often represent things with arrays (and hence vectors and matrices), so instead of keeping things in $\mathbb{P}^{2*}$ , we often write down $\mathbf{l} \in \operatorname{Mat}_{3 \times 1}(\mathbb{C})$ , representing an element $l \in \mathbb{P}^2$ such that $l^\intercal \in \mathbb{P}^{2*}$ is its corresponding line. In practice, we’d use the following characterization: a point $x \in \mathbb{P}^2$ lies on the line $l$ if and only if $\mathbf{l}^\intercal\mathbf{x} = 0$ (if and only if $l^\intercal(x) = 0$ as well).

Onto the next computational trick, suppose $l, l' \in \mathbb{P}^2$ are “lines” (i.e. $l^\intercal, l'^\intercal \in \mathbb{P}^{2*}$ are the corresponding lines). What is the intersection of these two lines? The surprising computational trick is that we can write the lines’ data in vectors $\mathbf{l}, \mathbf{l'} \in \mathbb{C}^3$ , and then consider the cross product $\mathbf{x} := \mathbf{l} \times \mathbf{l'}$ . Then $x \in \mathbb{P}^2$ is the intersection point (with its homogeneous coordinates being $\mathbf{x}$ ) of the two lines! This works whenever $l \ne l'$ . Let us show this. Let $l = [l_0 : l_1 : l_2]$ and $l' = [l'_0 : l'_1 : l'_2]$ . Then $\mathbf{x} = \mathbf{l} \times \mathbf{l'} = \begin{pmatrix}l_1l'_2 - l_2l'_1\\l_2l'_0-l_0l'_2\\l_0l'_1-l_1l'_0\end{pmatrix}$ . If $\mathbf{x} = 0$ then $l_1l'_2 = l_2l'_1$ , $l_2l'_0 = l_0l'_2$ , and $l_0l'_1 = l_1l'_0$ , i.e. $l = l'$ , a contradiction to our assumption that $l \ne l'$ . So $\mathbf{x} \ne 0$ , and so $x$ is well-defined as an element of $\mathbb{P}^2$ . Now let us check that $x$ lies on $l$ and $l'$ . Indeed, $\mathbf{l}^\intercal\mathbf{x} = l_0(l_1l'_2-l_2l'_1) + l_1(l_2l'_0-l_0l'_2) + l_2(l_0l'_1-l_1l'_0) = 0$ , so $x$ lies on $l$ . Similarly one can check that $\mathbf{l'}^\intercal\mathbf{x} = 0$ , and so $x$ lies on $l'$ as well. Observe that maybe $l$ and $l'$ can be parallel in the standard affine patch, but then that means they intersect at the point at infinity, and that’s fine. This gives the following dual to the Proposition 1:

Proposition 2. For a pair $(l, l') \in (\mathbb{P}^2)^2$ of distinct “lines”, there exists a unique point $x \in \mathbb{P}^2$ lying on the intersection of $l^\intercal$ and $l'^\intercal$ , and a homogeneous coordinates of $x$ can be taken to be $\mathbf{x} := \mathbf{l} \times \mathbf{l'}$ . $\square$

(Uniqueness can be proven similarly to Proposition 1.)

Conics

JensVyff, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

Depending on where you’re from, you might define a conic as:

circles, ellipses, parabolas, and hyperbolas
the zero locus of a quadratic polynomial $Ax^2 + Bxy + Cy^2 + Dx + Ey + F$
the intersection of a plane through the standard double cone
a plane algebraic curve of degree $2$
an algebraic curve of genus zero

Here I’ll introduce the viewpoint from computer vision: a conic is represented by a matrix $C \in \operatorname{Mat}_{3 \times 3}(\mathbb{C})$ , where the conic is the zero locus of $x \mapsto \mathbf{x}^\intercal C \mathbf{x}$ . More precisely, the conic corresponding to $C$ is the set $\left\{[z_0 : z_1 : z_2] \in \mathbb{P}^2 \colon \begin{pmatrix}z_0 & z_1 & z_2\end{pmatrix}C\begin{pmatrix}z_0\\z_1\\z_2\end{pmatrix} = 0\right\}$ . In other words, a conic is a zero locus of a quadratic form, projectivized. Without loss of generality we can restrict such $C$ to be a symmetric matrix, so we have $6$ parameters, i.e. it looks like

$\begin{pmatrix}a & b & c\\b & d & e\\c & e & f\end{pmatrix},$

where $a, b, c, d, e, f \in \mathbb{C}$ . Since the locus is the same up to projectivization, the parameters can all be simultaneously scaled by any $\lambda \in \mathbb{C}^\times$ and they’re still giving the same conic, so there are actually $5$ degrees of freedom, or in other words, the moduli space of conics in $\mathbb{P}^2$ has generic dimension $5$ . What does this mean? We have the following proposition:

Proposition 3. For general five points $p_1, p_2, p_3, p_4, p_5 \in \mathbb{P}^2$ there exists a unique conic passing through the points.

Proof. (Existence) Let us parametrize the conics by the family $\mathcal{C} := \{C \in \operatorname{Mat}_{3 \times 3}(\mathbb{C}) \colon C^\intercal = C\}/{\sim} \cong \mathbb{P}^5$ . When we want to impose that $p_1$ lies on the conic, this amounts to imposing that $p_1^\intercal C p_1 = 0$ . If we view $C$ as the unknown and $p_1$ as a given known point, then the equation $p_1^\intercal C p_1 = 0$ is exactly a linear constraint on the parameters of $C$ (perhaps it will be much clearer if we expand the matrix multiplication, but I don’t want to make it messy). This means “the collection of $C$ such that the conic associated to $C$ passes through $p_1, p_2, p_3, p_4, p_5$ ” is the zero locus of $\mathcal{C}$ cut out by five linear equations. If you translate this phrase using $\mathcal{C} \cong \mathbb{P}^5$ , you can see that the question is then “what’s the intersection locus of five hyperplanes in $\mathbb{P}^5$ “.

At this point I can import the Chow ring machinery and fancier stuffs, but I think it’s better to think intuitively that each linear equation (corresponding to a hyperplane in $\mathbb{P}^5$ ) reduces the dimension by one, and so with five general hyperplanes, the intersection locus is a nontrivial zero-dimensional locus. This (roughly and intuitively) proves the existence. For readers who want a rigorous Chow ring machinery, here I’ll note that $A(\mathbb{P}^n) = \mathbb{Z}[\zeta]/(\zeta^{n+1})$ where $\zeta \in A^1(\mathbb{P}^n)$ is the rational equivalence class of a hyperplane. This is Theorem 2.1. of Eisenbud–Harris. Now if we consider $A(\mathbb{P}^5)$ and ask for $\zeta \cdot \zeta \cdot \zeta \cdot \zeta \cdot \zeta$ , then we get $\zeta^5 \ne 0$ in $A(\mathbb{P}^5)$ , hence a nontrivial intersection locus, for general hyperplanes.

(Uniqueness) For general readers, I wish to ask you a simpler question that I found from David Bessis’ Mathematica: Can a straight line intersect a circle at three points? You can convince yourself that the answer is no, perhaps by trying to perform such intersection, and to picture such phenomena in your mind. A next logical example is the number of intersections of two ellipses. I think it’s not hard to try on your own to imagine two ellipses intersecting at four points. But you will find it impossible that two ellipses intersect at five points (if you really try to make them intersect at more than four points, you will eventually coerce them to intersect at every point, which is infinitely many points, and is a degenerate case). If you’re already convinced here, then the proof is done: perhaps we prescribe the points $p_1, p_2, p_3, p_4, p_5$ and suppose there are two conics $C_1$ and $C_2$ passing through all the five points. If $C_1 = C_2$ then we are done, but if not, then $C_1$ and $C_2$ are distinct conics, and they can intersect only at most at $4$ points, a contradiction to the fact that $p_1, p_2, p_3, p_4, p_5$ lie on the intersection of $C_1$ and $C_2$ .

For a rigorous statement and proof, we need Bézout’s theorem to conclude that $C_1$ and $C_2$ intersect at at most $4$ points.

Note that in the statement, I used the phrase “general five points” because it is not true that this statement holds “for all five points”! One obvious problem you might see is when the points are not distinct and so the uniqueness proof doesn’t go through. Another problem is when some of the points are collinear, and so the dimension reduction argument in the proof of existence doesn’t go through. So, by “general five points”, what I mean is that “the set $(p_1, p_2, p_3, p_4, p_5) \in (\mathbb{P}^2)^5$ such that the statement holds is Zariski-dense in $(\mathbb{P}^2)^5$ “. $\square$

Now, there is a very natural and beautiful generalization, which I’ll state it here and leave it to the readers who wish to prove it by themselves (or, perhaps, ask your favorite LLM).

Theorem 4. Let $d \in \mathbb{Z}_{\geq 1}$ be given. For a general tuple of $\frac{(d+2)(d+1)}{2}-1$ points in $\mathbb{P}^2$ , there exists a unique plane algebraic curve of degree $d$ passing through all the points.

Now let us move on to the computer vision part!

The Pinhole Camera

How does a camera work? (Disclaimer: I don’t know!) For readers who know how a camera works, please feel free to comment (or even teach me)! Since I’m not intrinsically interested in constructing a camera or something like that, I’ll just abstract it away, and consider the pinhole camera model as a standing hypothesis.

In this model, we consider the camera as a box on the right (the blue plane acts as the front of the camera, and the yellow plane acts as the “film”, or some plane that “records the image”). The pinhole is what makes such recording possible: sunlight hits the object in the “3D Scene”, then reflect its color in every direction. The pinhole is the filter that “we only want to capture these few directions of rays”, so that the possible rays of light that hit the image plane will only be the rays passing through the pinhole point.

What if the pinhole is too large? This is where the image gets blurry: the top of the tree gets sent across a chunk of vertical spaces, and so on. See the following image.

What if the pinhole is too small? Actually, theoretically, there’s no downside to that. Just make it the smallest as you can, but if it’s too small to be practically used, the light gets blocked by the pinhole itself and then we can’t capture the image.

There is a fun mini-experiment, if you have a myopia or something like that. Normally we use eyeglasses (i.e. lenses) to refract the light rays and correct the focal point. But there is another way. Put off your eyeglasses, pinch a tiny hole on a piece of paper (or use your hand to make a very small hole), and look through it (place it very closely to one of your eyes, and close the other eye). You might see the image clearly. Here is my attempt to explain how it works.

Basically, the problem of myopia is that the green ray and the blue ray converge before they hit the retina. Important, and this is where a lot of people got it wrong, including me, and got corrected by a friend of mine (thanks Atom!): it is not true that the lens makes the light rays focus at the retina. The light rays (from different parts of the scene, i.e. see red vs blue rays) focus before they hit the retina, turning the image into an upside-down image. It is only that the rays coming from a single point of the scene can hit the eye surface at different spots, making it blurry at first. The lens of the eye then tries to focus these rays to get a sharp image of the point at the retina. Now, how does the pinhole help in the case of myopia? The pinhole is a filtering device that tries to only allow (near-)parallel rays to pass through, so at a single point of the scene, multiple rays reflected into all directions are filtered out, leaving only a small bunch of rays that are already nearly parallel into the eye. The lens can then focus these rays (in the example image above the focal point is even before the lens), and then the image hits the retina, with a very small degree of blurry effect corresponding to different rays emitted from the same point of the scene.

Now, back to computer vision. For our purposes, we will now assume our camera model to be the pinhole camera model without lenses (because this simplifies things a lot). To model this mathematically, a pinhole camera is just a particular kind of linear mapping from the scene in $\mathbb{R}^3$ to the image in $\mathbb{R}^2$ . For simplicity, instead of viewing the image upside down, we will assume that the computer can just flip the image directly, and model our image space as having the same orientation as the scene. And for simplicity, we replace the real affine spaces by complex projective spaces, $\mathbb{P}^3$ and $\mathbb{P}^2$ . Consider the following model:

Abstractly, we would want something like the following definition.

Definition. A pinhole camera is a matrix $\mathbf{P} \in \operatorname{Mat}_{3 \times 4}(\mathbb{C})$ which defines a partial map $\mathbb{P}^3 \dashrightarrow \mathbb{P}^2$ by sending $\mathbf{X}$ (viewed as a vector in $\mathbb{C}^4$ ) to $\mathbf{PX}$ (matrix multiplication).

Why is this only a partial map and not an actual projective morphism or something like that? The problem is that, for some bad values of $\mathbf{X}$ , the matrix multiplication $\mathbf{PX} \in \mathbb{C}^3$ may vanish, and hence not well-defined in $\mathbb{P}^2$ ! (For example, inputting the pinhole gives an undefined projected point!)

This makes it a bit hard to define it purely in algebro-geometric terms, but let me give it an attempt. Consider the sheaf $\mathcal{O}_{\mathbb{P}^4}(1)^{\oplus 3}$ , and grab a rational section $\sigma \in \Gamma(\mathcal{O}_{\mathbb{P}^4}(1)^{\oplus 3}, U)$ over a dense open $U$ . This corresponds to the pinhole camera matrix $\mathbf{P} \in \operatorname{Mat}_{3 \times 4}(\mathbb{C})$ given by $\sum_{j=0}^3 \mathbf{P}_{i,j}z_j = \sigma_i(z_0, z_1, z_2, z_3)$ . So, uh…, yes… a pinhole camera is a rational section of the sheaf $\mathcal{O}_{\mathbb{P}^4}(1)^{\oplus 3}$ .

Note: I think this phenomenon is closely related to the situation of quasimap, which is defined from a nodal curve $C$ to $\mathbb{P}^m$ as a morphism $f$ in the following commutative diagram:

Rendered by QuickLaTeX.com

where $[\mathbb{C}^{m+1}/\mathbb{C}^\times]$ is the quotient stack. But ok, I don’t know much about quotient stack (yet), so I don’t think I should try to guess how things work. It’s just that the idea of pinhole camera came up while I was listening to the talk of Denis Nesterov in last Wednesday’s seminar.

Now, before moving on, I want to dissect $\mathbf{P} \in \operatorname{Mat}_{3 \times 4}(\mathbb{C})$ a bit more so that we won’t miss what’s in the literature. There are two parts of the camera transformation: the intrinsic part $\mathbf{K} \in \operatorname{Mat}_{3 \times 3}(\mathbb{C})$ and the extrinsic part $[\mathbf{R} | \mathbf{t}]$ , with $\mathbf{R} \in \operatorname{Mat}_{3 \times 3}(\mathbb{C})$ and $\mathbf{t} \in \operatorname{Mat}_{3 \times 1}(\mathbb{C})$ , and we have $\mathbf{P} = \mathbf{K}[\mathbf{R} | \mathbf{t}]$ (the notation $[\mathbf{R} | \mathbf{t}]$ is just the block matrix notation: it is a $3 \times 4$ matrix whose first three columns are from $\mathbf{R}$ and the last column is from $\mathbf{t}$ ). This may sound nonsense to the pure mathematicians, but it’s actually important (in an applied sense) to know which parameter controls which quantity in real life.

Since a pinhole camera $\mathbf{P} \in \operatorname{Mat}_{3 \times 4}(\mathbb{C})$ defines a partial map $\mathbb{P}^3 \dashrightarrow \mathbb{P}^2$ by sending $\mathbf{X}$ to $\mathbf{PX}$ , observe that the actual map $\mathbb{P}^3 \dashrightarrow \mathbb{P}^2$ is the same when you scale $\mathbf{P}$ by some scalar $\lambda \in \mathbb{C}^\times$ . This means there are $11$ degrees of freedom for $\mathbf{P}$ . In these $11$ degrees of freedom, we interpret it into $5$ intrinsic parameters (i.e. design $\mathbf{K}$ in such a way with $5$ degrees of freedom) corresponding to focal length, skew, and principal point, and $6$ extrinsic parameters (i.e. design $\mathbf{R}$ and $\mathbf{t}$ in such a way with $6$ degrees of freedom) corresponding to $3$ for rotation and $3$ for translation. We describe the design of $\mathbf{K}$ and $[\mathbf{R} | \mathbf{t}]$ in the following.

In pixel coordinates, let

$\mathbf{K} := \begin{pmatrix}\alpha_x & s & p_x\\0 & \alpha_y & p_y\\0 & 0 & 1\end{pmatrix}, \qquad \alpha_x = fm_x, \alpha_y = fm_y.$

Here, we have:

$f$ is the focal length in length units,
$(m_x, m_y)$ convert from length to pixels,
$s$ is the skew,
and $(p_x, p_y)$ is the principal point.

We say that $\mathbf{K}$ is intrinsic because it’s the property of the camera, no matter how we move the camera around, while $[\mathbf{R} | \mathbf{t}]$ is extrinsic because it depends largely on the camera’s pose. Here, $\mathbf{t} \in \operatorname{Mat}_{3 \times 1}(\mathbb{C})$ corresponds to where the camera is positioned in the world. The entries in the matrix for $\mathbf{t}$ are free, so $\mathbf{t}$ has $3$ degrees of freedom.

And $\mathbf{R} \in \operatorname{Mat}_{3 \times 3}(\mathbb{C})$ corresponds to how the camera is rotated. Actually, we can just restrict to $\mathbf{R} \in \mathrm{SO}_3(\mathbb{R})$ . Since $\dim \mathrm{SO}_3(\mathbb{R}) = 3$ , we see that $\mathbf{R}$ has $3$ degrees of freedom.²

Under the settings above, we redefine the notion of the pinhole camera using this decomposition $\mathbf{K}[\mathbf{R} | \mathbf{t}]$ .

Redefinition. A pinhole camera is a matrix $\mathbf{P} \in \operatorname{Mat}_{3 \times 4}(\mathbb{C})$ coming from $\mathbf{P} = \mathbf{K}[\mathbf{R} | \mathbf{t}]$ with $\mathbf{K} = \begin{pmatrix}\alpha_x & s & p_x\\0 & \alpha_y & p_y\\0 & 0 & 1\end{pmatrix}$ where $\alpha_x, \alpha_y \ne 0$ , $\mathbf{R} \in \mathrm{SO}_3(\mathbb{R})$ , and $\mathbf{t} \in \mathbb{C}^3$ . We call $\mathbf{K}$ the intrinsic matrix of $\mathbf{P}$ , and $[\mathbf{R} | \mathbf{t}]$ the extrinsic matrix of $\mathbf{P}$ .

Proposition 5. For a pinhole camera $\mathbf{P}$ , we have $\operatorname{rank}\mathbf{P} = 3$ .

Proof. Since $\alpha_x, \alpha_y \ne 0$ , and $\det\mathbf{K} = \alpha_x\alpha_y$ , we see that $\mathbf{K}$ is invertible, and so $\operatorname{rank}\mathbf{P} = \operatorname{rank}[\mathbf{R} | \mathbf{t}]$ . But $\mathbf{R} \in \mathrm{SO}_3(\mathbb{R}) \subseteq \mathrm{SL}_3(\mathbb{R})$ so $\mathbf{R}$ has full rank, and so $\mathbf{P}$ also has rank at least $3$ . Since $\mathbf{P}$ is a $3 \times 4$ matrix, its rank is at most $3$ , so its rank is exactly $3$ . $\square$

Basic Problems of Computer Vision

Here I’ll introduce briefly some of the very first basic problems we wish to solve in computer vision. As we all know, computer vision is the inverse of computer graphics. In graphics, we have some data of an object, a 3D model, or something like that, and we wish to visualize such object into the scene. In vision, we have the image data of a scene, and we wish to learn about what is happening. The first problem is therefore the homography problem, or, more appropriately, the correspondence problem: you have two images of basically the same thing. How do you “match” which part of the first image correspond to which part of the second image? See the following example.

These two images are not exactly the same, but they “morally” present the same scene. I took them within the same minute, at the exact same place (but perhaps with some hand movement and some camera rotation) during a trip to Grindelwald with Mammoth (a friend of mine) in September 2025.

Here is an example of a possible correspondence (not really very good but it’s what my program spits out). This mainly uses the Harris corner detector and then mutual nearest neighbors. The Harris corner detector is a nice, simple, and classical way to detect corners, where the descriptor here is the sum of squared differences (SSD) between $9 \times 9$ pixels patches around each keypoint.

There are obviously better ways of doing things. For example, instead of just detecting corners and matching them using SSD, one can also detect blobs using Laplacian of Gaussians (LoG) or similar techniques. And for the descriptor, this raw $9 \times 9$ neighborhood extraction is a very basic (and inefficient) way. One can replace this by SIFT or other techniques as well. I’ll not go through the mechanism of Harris detector here since it would be too long and it’s outside the current post’s focus. I’m just presenting this as a possible basic solution to the correspondence problem.

What’s the point of the correspondence problem? Basically, it’s the first step to teach the computer “how to see things” from images. But it’s not just that. Some applications include, for example, deduction of a homography between two camera poses, attaching different images to form a panorama, etc. I still don’t have much experience on that side, so I won’t go more into the details. Let us now move on to the next problems.

Multi-View Geometry

The next collection of problems I’d like to present here concerns the existence of multiple cameras. Why do we even want to have multiple cameras? Have you ever wondered why do you have two eyes (instead of one)? The basic problem of having one eye is that it is intrinsically impossible to know the depth (i.e. whether an object is near or far) in a flat image without external data. Under the standard $\mathbb{P}^3 \dashrightarrow \mathbb{P}^2$ pinhole camera, one degree of freedom is gone (in a sense, it’s intuitively a kind of projection, but not necessarily mathematically a projection; the axis to which the projection is done along is forgotten upon such projection). This problem can be fixed once one has at least two cameras (intuitively, two cameras impose high enough constraints to pin down the depth). We will see how this works later, but let me introduce the three fundamental problems of multi-view geometry first.

Correspondence Geometry: Given an image point $x \in \mathbb{P}^2$ , how does this constrain where the corresponding point $x' \in \mathbb{P}^2$ appears in another image? (If this is confusing or if it sounds nonsense, I recommend you to go back to the correspondence problem above that we’ve tried to match points of one image with points of another image; this scenario is similar, but the question is more precise: if I fix the pixel $\mathbf{x}$ , how much can we say about the corresponding $\mathbf{x'}$ in another image)

Camera Geometry (Motion): Given a collection of corresponding points $(\mathbf{x}_i, \mathbf{x'}_i)_{i=1, \dots, n}$ , how can we recover the relative cameras and poses $(\mathbf{P}, \mathbf{P'})$ ?

Scene Geometry (Structure): Given correspondences $(\mathbf{x}_i, \mathbf{x'}_i)_{i=1, \dots, n}$ , and known cameras $(\mathbf{P}, \mathbf{P'})$ , then where are the 3D points $\mathbf{X}_1, \dots, \mathbf{X}_n$ actually located?

It’s not like they are three separated problems, but rather a sequential process where we solve the first problem then go to the next, and then to the last, in order to reconstruct a 3D scene out of images from two cameras.

Let us now develop the geometry to solve these problems.

Epipolar Geometry

Let us set the stage. Suppose there are two cameras: $\mathbf{C}$ and $\mathbf{C'}$ , and $\mathbf{C}$ and $\mathbf{C'}$ denote their “centers” (i.e. their imaginary pinholes) respectively. Suppose we’re looking at a point object $X \in \mathbb{P}^3$ in the scene. The image $x \in \mathbb{P}^2$ is obtained by $\mathbf{x} := \mathbf{PX}$ , where $\mathbf{P}$ is the camera projection matrix of $\mathbf{C}$ . Similarly, the image $x' \in \mathbb{P}^2$ can be obtained in the same way: $\mathbf{x'} := \mathbf{P'X}$ , where $\mathbf{P'}$ is the camera projection matrix of $\mathbf{C'}$ . Let $\pi$ be the unique plane through the points $\mathbf{X}, \mathbf{C}, \mathbf{C'}$ (this is well-defined assuming $\mathbf{X}, \mathbf{C}, \mathbf{C'}$ are not collinear). We call $\pi$ the epipolar plane.

Then, one can draw a line connecting $\mathbf{C}$ to $\mathbf{C'}$ . This is called the baseline. It intersects the image plane of the first camera at a point $\mathbf{e}$ , called epipolar point. Similarly, it also intersects the image plane of the second camera at a point $\mathbf{e'}$ , also called epipolar point. The straight line connecting $\mathbf{x}$ and $\mathbf{e}$ (and then extended indefinitely) is called the epipolar line, denoted by $\mathbf{l}$ . The same process can be done on the other side, getting $\mathbf{l'}$ . The following picture illustrates everything I’ve said.

This illustration above is (intentionally) symmetric (since it’s harder to draw in a more general case), but in general it need not be so. Now consider if you’re looking using the first camera on the left. You capture the image. What do you see? You see the object at $\mathbf{X}$ but you only know the image coordinate $\mathbf{x}$ , and not the world coordinate $\mathbf{X}$ . The only deductible information is that $\mathbf{X}$ must lie on the ray (in the world coordinates) from $\mathbf{C}$ to $\mathbf{x}$ . We also know that this ray must be on the epipolar plane $\pi$ . We then see that this plane $\pi$ , when intersected with the image plane of the second camera, gives the epipolar line $\mathbf{l'}$ . And then we see that the corresponding image point $\mathbf{x'}$ must lie somewhere on $\mathbf{l'}$ .

This is an additional deduced constraint for the Correspondence Geometry problem: once we know $\mathbf{C}, \mathbf{x}, \mathbf{C'}$ , and the image plane of the second camera, we can deduce immediately that $\mathbf{x'}$ must lie on $\mathbf{l'}$ (and $\mathbf{l'}$ can be computed from the known information). This constraint is called the epipolar constraint.

What can we say once we know the epipolar constraint? Well, for simplicity, suppose we know every parameters (including $\mathbf{X}$ , epipolar points and lines, image planes, and the epipolar plane). The epipolar constraint is precisely $\mathbf{l'}^\intercal\mathbf{x'} = 0$ . Now what is $\mathbf{l'}$ ? Since $\mathbf{l'}$ is defined as the line passing through $\mathbf{e'}$ and $\mathbf{x'}$ , we may apply Proposition 1 and see that $\mathbf{l'} = \mathbf{e'} \times \mathbf{x'}$ . This allows us to get the following remarkable deduction:

Theorem 6. Let $\mathbf{P}, \mathbf{P}' \in \operatorname{Mat}_{3 \times 4}(\mathbb{C})$ be the camera projection matrices for the two cameras. Then there exists a unique (up to scaling) matrix $\mathbf{F} \in \operatorname{Mat}_{3 \times 3}(\mathbb{C})$ of rank $2$ such that for all object point $\mathbf{X}$ in the scene (assume $X \ne C,C'$ ), if $\mathbf{x} := \mathbf{PX}$ is the image point on the first camera, and $\mathbf{x'} := \mathbf{P'X}$ is the image point on the second camera, then they satisfy $\mathbf{x'}^\intercal\mathbf{F}\mathbf{x} = 0$ .

Before going to the proof, let me state a small lemma that might illuminate us why the epipolar constraint and the epipolar plane is useful.

Lemma 7. Given the prescription of everything, i.e., $\mathbf{x}, \mathbf{x'}, \mathbf{e}, \mathbf{e'}$ (assuming $x_2 = x'_2 = e_2 = e'_2 = 1$ and assuming that $X, C, C'$ are not collinear), the epipolar plane $\pi \in \mathbb{P}^{3*}$ , the first epipolar line $l^\intercal \in \mathbb{P}^{2*}$ , and the second epipolar line $l'^\intercal \in \mathbb{P}^{2*}$ , there exists an “invertible linear projective transformation” $H \colon \mathbb{P}^2 \dashrightarrow \mathbb{P}^2$ (i.e. there exists a matrix $\mathbf{H} \in \mathrm{GL}_3(\mathbb{C})$ ) sending $l$ to $l'$ (i.e. $\mathbf{l'}^\intercal\mathbf{Hz} = 0 \iff \mathbf{l}^\intercal \mathbf{z} = 0$ for all $\mathbf{z} \in \operatorname{Mat}_{3 \times 1}(\mathbb{C}) \setminus \{0\}$ such that $\mathbf{Hz} \ne 0$ ), which sends $x$ to $x'$ (i.e. $\mathbf{Hx} = \mathbf{x'}$ ) and $e$ to $e'$ (i.e. $\mathbf{He} = \mathbf{e'}$ ).

I’ve tried to make a proof of this one, but my proof contained some errors and it’s quite tedious and long, so I retract the proof and leave this statement here as a linear algebra grinding exercise for anyone interested (or disprove it if you don’t trust it). It is intuitively very clear why it works (you can just draw two lines and find a map that project one into another), and it should morally be true, but then yes you have to grind the details to establish it.

We call such $H$ a homography from the first image plane to the second image plane with respect to $\pi$ , and write $\mathbf{H}_\pi$ for $\mathbf{H}$ .

Why is this relevant? In Theorem 6, if we ask for $\mathbf{F}$ for a single correspondence $\mathbf{x} \leftrightarrow \mathbf{x'}$ instead of for all correspondences, we now have a very nice simple solution. Recall that the epipolar constraint is $\mathbf{l'}^\intercal\mathbf{x'} = 0$ , and we saw that $\mathbf{l'} = \mathbf{e'} \times \mathbf{x'}$ . Lemma 6 shows that there exists an invertible $\mathbf{H}_\pi$ with $\mathbf{x'} = \mathbf{H}_\pi\mathbf{x}$ . This means the epipolar constraint, when transposed to $\mathbf{x'}^\intercal\mathbf{l'} = 0$ , amounts to

$\mathbf{x'}^\intercal(\mathbf{e'} \times (\mathbf{H}_\pi\mathbf{x})) = 0.$

But for any vector $\mathbf{v}$ , the cross product $\mathbf{e'} \times \mathbf{v}$ is just $\begin{pmatrix}e'_2v_3 - e'_3v_2\\e'_3v_1 - e'_1v_3\\e'_1v_2 - e'_2v_1\end{pmatrix}$ , so $\mathbf{e'} \times \mathbf{v} = [\mathbf{e'}]_\times \mathbf{v}$ , where

$[\mathbf{e'}]_\times = \begin{pmatrix}0 & -e'_3 & e'_2\\e'_3 & 0 & -e'_1\\-e'_2 & e'_1 & 0\end{pmatrix}.$

This means we can write the epipolar constraint as $\mathbf{x'}^\intercal [\mathbf{e'}]_\times \mathbf{H}_\pi \mathbf{x} = 0$ , and so it is now clear to define $\mathbf{F} := [\mathbf{e'}]_\times \mathbf{H}_\pi$ . This has rank $2$ since $[\mathbf{e'}]_\times$ has rank $2$ and $\mathbf{H}_\pi$ is invertible. So, for a single correspondence, we got $\mathbf{F}$ already! The rest is to try to establish some (potentially different) $\mathbf{F}$ that works for all correspondences.

Recall that $\mathbf{PC} = 0$ (i.e. it is undefined in $\mathbb{P}^2$ to project the pinhole of the camera onto the image plane). Recall also that by our Proposition 5, $\operatorname{rank}\mathbf{P} = 3$ . By the rank–nullity theorem, $\dim\operatorname{ker}\mathbf{P} = 1$ , and so the subspace $\mathbb{C}\mathbf{C} \subseteq \mathbb{C}^4$ is exactly the kernel of $\mathbf{P}$ . Let $W := (\mathbb{C}\mathbf{C})^\perp$ be its orthogonal complement, then we see that $\mathbf{P}|_W \colon W \to \mathbb{C}^3$ is an isomorphism of vector spaces, hence invertible. Let $\mathbf{B} \in \operatorname{Mat}_{4 \times 3}(\mathbb{C})$ be its inverse, i.e. that $\mathbf{BPv} = \mathbf{v}$ for all $\mathbf{v} \in W$ . Since $\mathbf{P}|_W$ is bijective, $\mathbf{B}$ is well-defined, and we see that $\operatorname{im}\mathbf{B} \subseteq W$ automatically. Note: this $\mathbf{B}$ is closely related to the concept of a pseudoinverse, but since I haven’t received any formal education on that topic, and I’m too lazy to go out of my way to develop the singular value decomposition (SVD) machinery and to prove the existence and uniqueness of pseudoinverses, I decided to just use the ad-hoc approach in this way. Also another important fact is that we defined $\mathbf{B}$ based on $\mathbf{P}$ and $\mathbf{C}$ (and not anything about the image or the scene).

The next step will depend on the object in the scene. For an object point $X \in \mathbb{P}^3$ in the scene, we get $\mathbf{x} = \mathbf{PX}$ , so $\mathbf{Bx} = \mathbf{BPX}$ . Since $\mathbb{C}^4 = W \oplus \mathbb{C}\mathbf{C}$ , we can write $\mathbf{X} = \mathbf{X}_W + \lambda\mathbf{C}$ uniquely, and we see that $\mathbf{Bx} = \mathbf{BP}(\mathbf{X}_W + \lambda\mathbf{C}) = \mathbf{BP}\mathbf{X}_W = \mathbf{X}_W = \mathbf{X} - \lambda\mathbf{C}$ . That is, $\mathbf{X} = \mathbf{Bx} + \lambda\mathbf{C}$ . Now if we view from the second camera, we get $\mathbf{x'} = \mathbf{P'X} = \mathbf{P'}(\mathbf{Bx} + \lambda\mathbf{C})$ . But now, recall the epipolar constraint $\mathbf{l'}^\intercal\mathbf{x'} = 0$ and recall that $\mathbf{l'} = \mathbf{e'} \times \mathbf{x'}$ (see, i.e. before Lemma 6). And the epipolar point $\mathbf{e'}$ is defined as the projection of $\mathbf{C}$ onto the image plane of the second camera, i.e. $\mathbf{e'} = \mathbf{P'C}$ . Substituting these, we get

$\mathbf{l'} = \mathbf{P'C} \times \mathbf{P'}(\mathbf{Bx} + \lambda\mathbf{C}) = \mathbf{P'C} \times \mathbf{P'Bx} + \lambda \underbrace{\mathbf{P'C} \times \mathbf{P'C}}_{0}.$

And we substitute back $\mathbf{P'C} = \mathbf{e'}$ to see that $\mathbf{l'} = [\mathbf{e'}]_\times \mathbf{P'Bx}$ .

So the epipolar constraint becomes $0 = \mathbf{x'}^\intercal \mathbf{l'} = \mathbf{x'}^\intercal [\mathbf{e'}]_\times \mathbf{P'Bx}$ . Put $\mathbf{F} := [\mathbf{e'}]_\times \mathbf{P'B}$ to see that $\mathbf{x'}^\intercal \mathbf{F} \mathbf{x} = 0$ . Observe that the definition of $\mathbf{F}$ doesn’t depend on the choice of $X$ , i.e., it works for all object points. Also, recall that $[\mathbf{e'}]_\times$ has rank $2$ , and $\mathbf{P'B}$ is invertible, so $\mathbf{F}$ has rank $2$ . This proves the existence part of Theorem 6.

Before proving the uniqueness, let us deduce some more useful properties of the fundamental matrix.

Lemma 8. Let the camera settings $\mathbf{P}, \mathbf{P'}, \mathbf{C}, \mathbf{C'}$ be given. Let $\mathbf{e} := \mathbf{PC'}$ and $\mathbf{e'} := \mathbf{P'C}$ be the epipoles. Let $\mathbf{F}$ be a fundamental matrix for this setting. Then,

For any $\mathbf{x} \in \mathbb{C}^3$ , $\mathbf{e'}^\intercal \mathbf{F} \mathbf{x} = 0$ . And similarly for any $\mathbf{x'} \in \mathbb{C}^3$ , $\mathbf{x'}^\intercal \mathbf{F} \mathbf{e} = 0$ .
$\mathbf{e} \in \operatorname{ker}\mathbf{F}$ and $\mathbf{e'} \in \operatorname{ker}\mathbf{F}^\intercal$ .
For a point $\mathbf{x}$ on the first image plane (this works even if $\mathbf{x}$ is not an image point, i.e. when $x_2 = 0$ ) such that $\mathbf{x} \not\sim \mathbf{e}$ , without knowing the actual object point $\mathbf{X}$ , we can deduce the epipolar line in the second image, as it satisfies $\mathbf{l'} \sim \mathbf{Fx}$ . Similarly, on the other side, $\mathbf{l} \sim \mathbf{F}^\intercal\mathbf{x'}$ for all $\mathbf{x'} \not\sim \mathbf{e'}$ .

Proof. For the first item, consider the illustration above. Let $\mathbf{x} \in \mathbb{C}^3$ be any image point (i.e. assume $x_2 = 1$ ). We try to draw the red line, say, let $R := \{\mathbf{X} \in \mathbb{C}^4 \colon \mathbf{PX} \sim \mathbf{x}\}$ . Note: $\mathbf{C} \notin R$ since $\mathbf{PX} = 0$ , but the rest is fine. Now, for each object point $\mathbf{X} \in R$ , we can project to $\mathbf{P'X}$ , and this lies on the line $\mathbf{l'}^\intercal$ , and by definition, when projected to $\mathbf{PX}$ , we get the point $x$ (but possibly differently scaled in the homogeneous coordinates). In this sense, this means the point $x$ and the point $x' := P'(X)$ are in correspondence, and so, by the defining property of $\mathbf{F}$ , this means $(\mathbf{P'X})^\intercal\mathbf{Fx} = 0$ for all $\mathbf{X} \in R$ . Taking limit as $\mathbf{X}$ approaches $\mathbf{C}$ , since $\mathbf{X} \mapsto (\mathbf{P'X})^\intercal\mathbf{Fx}$ is continuous, we see that $(\mathbf{P'C})^\intercal\mathbf{Fx} = 0$ as well, and since $\mathbf{P'C} = \mathbf{e'}$ , we deduce that $\mathbf{e'}^\intercal\mathbf{Fx} = 0$ . This proves the first direction of the first statement in case that $\mathbf{x}$ corresponds to the coordinate of an actual point (i.e. $x_2 = 1$ ). Now what if $x_2 = 0$ ? In that case $\mathbf{x} + \begin{pmatrix}0\\0\\1\end{pmatrix}$ is an image point, so $\mathbf{e'}^\intercal\mathbf{F}(\mathbf{x} + \begin{pmatrix}0\\0\\1\end{pmatrix}) = 0$ . And also $\begin{pmatrix}0\\0\\1\end{pmatrix}$ itself is an image point, so $\mathbf{e'}^\intercal\mathbf{F} \begin{pmatrix}0\\0\\1\end{pmatrix} = 0$ . Subtracting them gives $\mathbf{e'}^\intercal\mathbf{F}\mathbf{x} = 0$ . This proves the general case. The other direction is the same, by symmetry. This proves the first statement.

Now, for the second statement, we use the first statement: we know that $\mathbf{x'}^\intercal \mathbf{F} \mathbf{e} = 0$ for all $\mathbf{x'} \in \mathbb{C}^3$ , and by picking a basis and plugging into $\mathbf{x'}$ , this is enough to see that $\mathbf{Fe} = 0$ , and so $\mathbf{e} \in \operatorname{ker}\mathbf{F}$ . Similarly, $\mathbf{e'}^\intercal \mathbf{F} \mathbf{x} = 0$ for all $\mathbf{x} \in \mathbb{C}^3$ means $\mathbf{x}^\intercal \mathbf{F}^\intercal \mathbf{e'} = 0$ for all $\mathbf{x} \in \mathbb{C}^3$ and so $\mathbf{F}^\intercal \mathbf{e'} = 0$ , so $\mathbf{e'} \in \operatorname{ker}\mathbf{F}^\intercal$ . This proves the second statement.

Now, for the third, suppose $\mathbf{X}$ is the object point, which is unknown to us (this exists even if $\mathbf{x}$ is not an image point, i.e. $x_2 = 0$ , since $\mathbf{P}$ has full rank; recall Proposition 5). The epipolar constraint tells us that $\mathbf{l'}^\intercal \mathbf{x'} = 0$ (and also $\mathbf{l'}^\intercal \mathbf{e'} = 0$ since the second epipole lies on the epipolar line). By the defining properties of the fundamental matrix, we see that $\mathbf{x'}^\intercal \mathbf{Fx} = 0$ . This means $(\mathbf{Fx})^\intercal \mathbf{x'} = 0$ , i.e. $\mathbf{x'}$ lies on the line $(\mathbf{Fx})^\intercal$ . Now, by the first statement, we see that $\mathbf{e'}^\intercal \mathbf{Fx} = 0$ , which is $(\mathbf{Fx})^\intercal\mathbf{e'} = 0$ , i.e. $\mathbf{e'}$ lies on the line $(\mathbf{Fx})^\intercal$ . Since there is only a unique line passing through two points (recall Proposition 1), and both $(\mathbf{Fx})^\intercal$ and $\mathbf{l'}^\intercal$ pass through $\mathbf{e'}$ and $\mathbf{x'}$ , we see that they must be the same line, i.e. $\mathbf{l'} \sim (\mathbf{Fx})^\intercal$ . By symmetry, the other side works similarly. This completes the proof. $\square$

Now we can go back to our main theorem.

Proof of uniqueness (up to scaling) of Theorem 6. Suppose $\mathbf{F}$ and $\mathbf{F'}$ are two fundamental matrices. By Lemma 8(3), for each point $\mathbf{x} \not\sim \mathbf{e}$ its epipolar line on the second camera $\mathbf{l'}$ satisfies $\mathbf{l'} \sim \mathbf{Fx}$ and $\mathbf{l'} \sim \mathbf{F'x}$ . This means $\mathbf{Fx} \sim \mathbf{F'x}$ . That is, for each $\mathbf{x} \in \mathbb{C}^3 \setminus \mathbb{C}\mathbf{e}$ there exists $\lambda(\mathbf{x}) \in \mathbb{C}^\times$ such that $\mathbf{Fx} = \lambda(\mathbf{x}) \mathbf{F'x}$ . A priori, $\lambda \colon \mathbb{C}^3 \setminus \mathbb{C}\mathbf{e} \to \mathbb{C}^\times$ is just a function without any structure (i.e. we can’t assume continuity, linearity, or anything), but observe that for $\mathbf{x}, \mathbf{y} \in \mathbb{C}^3$ , and any $\alpha, \beta \in \mathbb{C}$ , the relation above tells us that

$\lambda(\alpha\mathbf{x}+\beta\mathbf{y})(\alpha\mathbf{F'x} + \beta\mathbf{F'y}) = \lambda(\alpha\mathbf{x}+\beta\mathbf{y})\mathbf{F'}(\alpha\mathbf{x}+\beta\mathbf{y}) = \mathbf{F}(\alpha\mathbf{x}+\beta\mathbf{y}) = \alpha\mathbf{Fx} + \beta\mathbf{Fy} = \alpha\lambda(\mathbf{x})\mathbf{F'x} + \beta\lambda(\mathbf{y})\mathbf{F'y}.$

Rearranging the terms, we get $(\lambda(\alpha\mathbf{x}+\beta\mathbf{y})-\lambda(\mathbf{x}))\alpha\mathbf{F'x} + (\lambda(\alpha\mathbf{x}+\beta\mathbf{y})-\lambda(\mathbf{y}))\beta\mathbf{F'y} = 0$ .

This means, whenever $\mathbf{F'x}$ and $\mathbf{F'y}$ are linearly independent, we can see that $\lambda(\alpha\mathbf{x}+\beta\mathbf{y}) = \lambda(\mathbf{x}) = \lambda(\mathbf{y})$ . (And also, when $\mathbf{y} = 0$ we get $\lambda(\alpha\mathbf{x}) = \lambda(\mathbf{x})$ )

Since $\mathbf{F'}$ is of rank $2$ , as usual, we have $\dim\operatorname{ker}\mathbf{F'} = 1$ , and by Lemma 8(2), $\mathbf{e} \in \operatorname{ker}\mathbf{F'}$ . So if $\mathbf{F'x}$ and $\mathbf{F'y}$ are linearly dependent, then pick some $\mathbf{z} \ne 0$ such that $\mathbf{F'z} \notin \mathbb{C}\mathbf{F'x}$ and $\mathbf{F'z} \notin \mathbb{C}\mathbf{F'y}$ (this exists since $\dim\operatorname{im}\mathbf{F'} = 2$ ), then $\mathbf{F'z}$ and $\mathbf{F'x}$ are linearly independent, and $\mathbf{F'z}$ and $\mathbf{F'y}$ are linearly independent, so $\lambda(\mathbf{x}) = \lambda(\mathbf{z}) = \lambda(\mathbf{y})$ . This shows that $\lambda(\mathbf{x}) = \lambda(\mathbf{y})$ for all $\mathbf{x}, \mathbf{y} \in \mathbb{C}^3 \setminus \mathbb{C}\mathbf{e}$ , whether they’re linearly independent or not, and so $\lambda$ is a constant function! Therefore, there exists some $\lambda \in \mathbb{C}^\times$ such that $\mathbf{Fx} = \lambda\mathbf{F'x}$ for all $\mathbf{x} \in \mathbb{C}^3$ . Picking $\mathbf{x}$ to be each basis element shows that $\mathbf{F} = \lambda\mathbf{F'}$ , and so this proves the uniqueness up to scaling of the fundamental matrix. $\square$

By the existence part, we’ve explicitly constructed $\mathbf{F} := [\mathbf{e'}]_\times \mathbf{P'B}$ , and by the uniqueness part, this is the unique fundamental matrix up to scaling. Therefore, for a pair of pinhole cameras $((\mathbf{P}, \mathbf{C}), (\mathbf{P'}, \mathbf{C'}))$ , we can construct $\mathbf{B}$ , and hence $\mathbf{F}$ , by the above procedure, and so this is a well-defined function

$\mathcal{F} \colon \mathrm{Cam} \times \mathrm{Cam} \to \mathrm{FundMatrix}.$

Now, I wonder, whether the converse of Theorem 6 is true. That is, suppose $\mathbf{x}, \mathbf{x'} \in \mathbb{C}^3$ satisfy $\mathbf{x'}^\intercal \mathbf{Fx} = 0$ , then is it true that $\mathbf{x}$ and $\mathbf{x'}$ are in correspondence, i.e. that there exists $\mathbf{X} \in \mathbb{C}^4$ such that $\mathbf{x} \sim \mathbf{PX}$ and $\mathbf{x'} \sim \mathbf{P'X}$ ?

Assume that $\mathbf{x} \not\sim \mathbf{e}$ and $\mathbf{x'} \not\sim \mathbf{e'}$ . By uniqueness of Theorem 6, we can assume $\mathbf{F} = [\mathbf{e'}]_\times \mathbf{P'B}$ immediately. Suppose $\mathbf{x}, \mathbf{x'} \in \mathbb{C}^3$ satisfy $\mathbf{x'}^\intercal \mathbf{Fx} = 0$ , then, expanding $\mathbf{F}$ , we get $\mathbf{x'}^\intercal(\mathbf{e'} \times \mathbf{P'Bx}) = 0$ . Let $\mathbf{l'} := \mathbf{e'} \times \mathbf{P'Bx}$ to see that $\mathbf{l'}^\intercal\mathbf{x'} = 0$ . Geometrically and intuitively, this means $\mathbf{x'}$ lies on the unique line (in $\mathbb{P}^2$ ) that passes through $\mathbf{e'}$ and $\mathbf{P'Bx}$ . In the locus form, we can take $\{(1-\lambda)\mathbf{e'} + \lambda\mathbf{P'Bx} \colon \lambda \in \mathbb{C}\}$ to be that line. The fact that this passes through $\mathbf{x'}$ (and $\mathbf{x'} \not\sim \mathbf{e'}$ ) tells us that there exists some $\lambda \in \mathbb{C}^\times$ such that $(1-\lambda)\mathbf{e'} + \lambda\mathbf{P'Bx} \sim \mathbf{x'}$ . Fix such $\lambda$ and write $\kappa \in \mathbb{C}^\times$ such that $(1-\lambda)\mathbf{e'} + \lambda\mathbf{P'Bx} = \kappa\mathbf{x'}$ .

Now, put $\mathbf{X} := \mathbf{C} + \lambda(\mathbf{Bx} - \mathbf{C})$ . Observe that $\mathbf{PX} = \mathbf{PC} + \lambda\mathbf{PBx} - \lambda\mathbf{PC} = \lambda\mathbf{x}$ . This means $\mathbf{PX} \sim \mathbf{x}$ . Now observe also that $\mathbf{P'X} = \mathbf{P'C} + \lambda\mathbf{P'Bx} - \lambda\mathbf{P'C} = (1-\lambda)\mathbf{e'} + \lambda\mathbf{P'Bx} \sim \mathbf{x'}$ . This shows that $\mathbf{x}$ and $\mathbf{x'}$ are in correspondence!

The problem when at least one of the image point is at its epipole is that $\mathbf{x'}^\intercal\mathbf{Fx} = 0$ immediately, but there is no such world point $\mathbf{X}$ that projects to them!

This shows that the converse of Theorem 6 is true whenever $\mathbf{x} \not\sim \mathbf{e}$ and $\mathbf{x'} \not\sim \mathbf{e'}$ .

Now, and this may be a stretch, but let me dub it “The Fundamental Theorem of Epipolar Geometry”, is therefore the following consequence.

Theorem 9. For two pinhole cameras with matrices $\mathbf{P}$ and $\mathbf{P'}$ and pinholes at $\mathbf{C}$ and $\mathbf{C'}$ , let $\mathbf{F}$ be their fundamental matrix, then the following is an exact sequence of $\mathbb{C}$ -vector spaces.

$\Delta \xrightarrow{\mathbf{X} \otimes \mathbf{Y} \mapsto \mathbf{PX} \otimes \mathbf{P'Y}} \mathbb{C}^3 \otimes \mathbb{C}^3 \xrightarrow{\mathbf{x} \otimes \mathbf{x'} \mapsto \mathbf{x'}^\intercal\mathbf{F}\mathbf{x}} \mathbb{C} \to 0,$

where $\Delta := \operatorname{span}\{\mathbf{X} \otimes \mathbf{X}, \mathbf{C'} \otimes \mathbf{X}, \mathbf{X} \otimes \mathbf{C} \colon \mathbf{X} \in \mathbb{C}^4\} \subseteq \mathbb{C}^4 \otimes \mathbb{C}^4$ .

Proof. The first map looks injective, but is actually not (one can see this by comparing the dimensions). Nevertheless, the lifted version works: suppose $\mathbf{PX} = \mathbf{PZ}$ and $\mathbf{P'X} = \mathbf{P'Z}$ , then this means $\mathbf{X} - \mathbf{Z} \in \operatorname{ker}\mathbf{P} \cap \operatorname{ker}\mathbf{P'} = \{0\}$ , so $\mathbf{X} = \mathbf{Z}$ .

The second map is surjective. Indeed, $\mathbf{F}$ has rank $2$ , so for $\mathbf{x}$ outside $\operatorname{ker}\mathbf{F}$ , we may look for $\mathbf{x'}$ such that $(\mathbb{C}^3 \setminus (\mathbb{C}\mathbf{x'})^\perp) \cap \operatorname{im}\mathbf{F} \ne \varnothing$ . There are infinitely many such $\mathbf{x'}$ , so we can simply grab such a pair $(\mathbf{x}, \mathbf{x'})$ and see that $\mathbf{x'}^\intercal\mathbf{Fx} \ne 0$ . Scaling $\mathbf{x}$ by any $\lambda \in \mathbb{C}^\times$ gives the surjectivity.

Now, onto the exactness, the fact that the image of the first map is in the kernel of the second map is precisely Theorem 6: for any $\mathbf{x} \otimes \mathbf{x'}$ arising from some correspondence, we have $\mathbf{x'}^\intercal\mathbf{F}\mathbf{x} = 0$ . The fact that the kernel of the second map is in the image of the first map is the converse of Theorem 6 we’ve just shown: if we know that $\mathbf{x'}^\intercal\mathbf{F}\mathbf{x} = 0$ , then there exists some $\mathbf{X}$ such that $\mathbf{x} \sim \mathbf{PX}$ and $\mathbf{x'} \sim \mathbf{P'X}$ . $\square$

Phew. Now we have a partial solution for the Correspondence Geometry problem: if the settings $(\mathbf{P}, \mathbf{C}, \mathbf{P'}, \mathbf{C'})$ are given, then the task is just to compute the fundamental matrix $\mathbf{F}$ , and then every correspondence can be characterized by $\mathbf{x'}^\intercal\mathbf{F}\mathbf{x} = 0$ .

The main problem is that in practice, we may not know the camera settings! This leads us to the second problem: the problem of motion.

The Problem of Motion

We haven’t yet established a way to calculate $\mathbf{F}$ directly from empirical correspondences (which we will eventually do, just a bit later), but suppose we magically know about $\mathbf{F}$ , then can we deduce back $(\mathbf{P}, \mathbf{C}, \mathbf{P'}, \mathbf{C'})$ ? It turns out that we can, up to some projective ambiguity. This intuitively leads us to this sequence:

$0 \to \mathrm{Cam} \times \mathrm{Cam} \xrightarrow{\mathcal{F}} \mathrm{FundMatrix} \to \mathrm{PGL}_4(\mathbb{C}) \to 0.$

Strictly speaking, this is nonsense, since we’re not working over an abelian category, and so there’s no such thing as an exact sequence. But what I want to show is that the preimage of $\mathcal{F}$ can be determined up to an ambiguity of $\mathrm{PGL}_4(\mathbb{C})$ . (Uhh… what’s the right way to say it? The fiber of $\mathcal{F}$ at each point is isomorphic to $\mathrm{PGL}_4(\mathbb{C})$ ? I guess???) Let me formulate it in a better way.

By the way, here we distinguish between different scales of a pinhole camera projection matrix, so, uhh, perhaps not $\mathrm{PGL}$ but rather $\mathrm{GL}$ would be the correct description for $\mathrm{Cam}$ . I think the following is the correct precise theorem, and let us prove it.

Theorem 10. Let $(\mathbf{P}, \mathbf{P'})$ be a pair of pinhole camera projection matrices. If $\mathbf{H} \in \mathrm{GL}_4(\mathbb{C})$ , then the pair $(\mathbf{PH}, \mathbf{P'H})$ has the same fundamental matrices as $(\mathbf{P}, \mathbf{P'})$ .

Proof. A pair $(\mathbf{x}, \mathbf{x'})$ is in correspondence if and only if $\mathbf{x'}^\intercal\mathbf{Fx} = 0$ if and only if there exists some $\mathbf{X}$ such that $\mathbf{x} \sim \mathbf{PX}$ and $\mathbf{x'} \sim \mathbf{P'X}$ if and only if, for $\mathbf{Y} := \mathbf{H}^{-1}\mathbf{X}$ , we have $\mathbf{x} \sim \mathbf{PHY}$ and $\mathbf{x'} \sim \mathbf{P'HY}$ if and only if $\mathbf{x'}^\intercal\widetilde{\mathbf{F}}\mathbf{x} = 0$ , where $\widetilde{\mathbf{F}}$ is the fundamental matrix for $(\mathbf{PH}, \mathbf{P'H})$ . This means $\mathbf{x'}^\intercal\mathbf{Fx} = 0 \iff \mathbf{x'}^\intercal\widetilde{\mathbf{F}}\mathbf{x} = 0$ . Since $\mathbf{x}$ and $\mathbf{x'}$ are arbitrary, we see that $\mathbf{F} \sim \widetilde{\mathbf{F}}$ . $\square$

The converse is also true, and this is called the uniqueness theorem:

Theorem 11. Let $(\mathbf{P}, \mathbf{P'})$ and $(\widetilde{\mathbf{P}}, \widetilde{\mathbf{P'}})$ be two pairs of pinhole camera projection matrices. If $\mathcal{F}(\mathbf{P}, \mathbf{P'}) \sim \mathcal{F}(\widetilde{\mathbf{P}}, \widetilde{\mathbf{P'}})$ then there exists some $\mathbf{H} \in \mathrm{GL}_4(\mathbb{C})$ such that $\widetilde{\mathbf{P}} \sim \mathbf{PH}$ and $\widetilde{\mathbf{P'}} \sim \mathbf{P'H}$ .

I’m too lazy to prove this one. I looked it up in the lecture notes, but the details are quite tedious linear algebra grinding. But Theorem 10 was enough to deduce a useful canonical form for pairs of pinhole cameras projection matrices: If we have $(\mathbf{P}, \mathbf{P'})$ , then since they are of full rank, there exists some $\mathbf{H} \in \mathrm{GL}_4(\mathbb{C})$ such that $\mathbf{PH} = [\mathbf{I}_3 | 0]$ . When this happens, we look at $\mathbf{P'H}$ and record it as $\mathbf{P'H} = [\mathbf{M} | \mathbf{m}]$ . Once in this form, one checks that $\mathcal{F}(\mathbf{PH}, \mathbf{P'H}) = [\mathbf{m}]_\times\mathbf{M}$ (just push the formula).

Now, the following Projective Reconstruction Theorem allows us to (theoretically) reconstruct the pinhole cameras projection matrices from a collection of correspondences.

Theorem 12 (Projective Reconstruction Theorem). Let $(\mathbf{x}_i, \mathbf{x'}_i)_{i=1,\dots,n}$ be a collection of correspondences. Suppose these correspondences determine a unique fundamental matrix, i.e. there exists a unique (up to scaling) $\mathbf{F} \in \mathrm{Mat}_{3 \times 3}(\mathbb{C})$ of rank $2$ such that $\mathbf{x'}_i^\intercal \mathbf{F} \mathbf{x}_i = 0$ for all $i$ . Then the scene and cameras may be reconstructed from these correspondences alone, i.e., the $(\mathbf{P}, \mathbf{C}, \mathbf{P'}, \mathbf{C'})$ can be recovered. Moreover, any two such reconstructions are projectively equivalent.

Proof. For existence, put $\mathbf{P} := [\mathbf{I}_3 | 0]$ . Grab $\mathbf{e'} \in \operatorname{ker}\mathbf{F}^\intercal \setminus \{0\}$ . Then put $\mathbf{P'} := [[\mathbf{e'}]_\times \mathbf{F} | \mathbf{e'}]$ . Take $\mathbf{C}$ and $\mathbf{C'}$ from their kernels. Uniqueness follows from the uniqueness theorem (Theorem 11). $\square$

In this way, we get an answer to the motion problem, and the rough idea is: if we know a bunch of correspondences $\mathbf{x}_i \leftrightarrow \mathbf{x'}_i$ , the idea is to (in some way, and we will explore this next) compute the fundamental matrix $\mathbf{F}$ that is valid for the correspondences, and then recover $(\mathbf{P}, \mathbf{C}, \mathbf{P'}, \mathbf{C'})$ using the projective reconstruction theorem.

Computing the Fundamental Matrix

This is the core computational heart (but unfortunately I’ll not go through in deep details since my time is short…). Given an (assumed imperfect) empirical data of correspondences $(\mathbf{x}_i, \mathbf{x'}_i)_{i=1,\dots,n}$ , how to compute the fundamental matrix $\mathbf{F}$ ? We begin with the natural idea: use its characterization and solve the algebraic system!

More precisely, we wish to find $\mathbf{F}$ such that $\mathbf{x'}_i^\intercal \mathbf{F} \mathbf{x}_i = 0$ for all $i$ . We can rewrite this equation in an expanded form:

$\sum_{j=0}^2\sum_{k=0}^2 F_{j,k}(\mathbf{x'}_i)_j(\mathbf{x}_i)_k = 0.$

In this way, we can reformulate the unknown $\mathbf{F}$ as an unknown vector $\mathbf{f} := \begin{pmatrix}F_{1,1}\\F_{1,2}\\F_{1,3}\\F_{2,1}\\F_{2,2}\\F_{2,3}\\F_{3,1}\\F_{3,2}\\F_{3,3}\end{pmatrix}$ and get the corresponding linear system. For each correspondence $\mathbf{x}_i \leftrightarrow \mathbf{x'}_i$ , write $\mathbf{x}_i \sim \begin{pmatrix}x_i\\y_i\\1\end{pmatrix}$ and $\mathbf{x'}_i \sim \begin{pmatrix}x'_i\\y'_i\\1\end{pmatrix}$ , and the equation becomes

$\begin{pmatrix}x'_1x_1 & x'_1y_1 & x'_1 & y'_1x_1 & y'_1y_1 & y'_1 & x_1 & y_1 & 1\\&&&&\vdots &&&&\\x'_nx_n & x'_ny_n & x'_n & y'_nx_n & y'_ny_n & y'_n & x_n & y_n & 1\end{pmatrix}\begin{pmatrix}F_{1,1}\\F_{1,2}\\F_{1,3}\\F_{2,1}\\F_{2,2}\\F_{2,3}\\F_{3,1}\\F_{3,2}\\F_{3,3}\end{pmatrix} = 0.$

Writing the matrix on the left as $\mathbf{A}$ , the problem is simply $\mathbf{Af} = 0$ . But if $n$ is too large then the system is overdetermined. We also have to add another nonlinear constraint that $\det\mathbf{F} = 0$ (but we will do this later). For now, if $n = 8$ and we assume the input to be linearly independent, then $\operatorname{ker}\mathbf{A}$ has dimension $1$ , so we can pick a nontrivial solution out of the kernel.

For higher $n$ , the system is overdetermined, but there is still an intuitive solution: try to fit the noisy points onto some $\mathbf{F}$ that produces best fit. In this sense we would minimize $\|\mathbf{Af}\|$ subject to $\|f\| = 1$ .

The above algorithm is what we call the Eight-Point Algorithm, and it has been developed in the literature, but from the practical side, there is a big problem around it: numerical stability. There are noises, and the last homogeneous coordinate is always set to $1$ , and small measurement errors tend to amplify into large solution errors.

However, with proper normalization, the eight-point algorithm becomes effective again. See [Hartley] for details.

Now back to the rank $2$ constraint. In practice it is enough to require $\det(\mathbf{F}) = 0$ . This, surprisingly, has an intuitive geometric explanation as well. The requirement that $\mathbf{F}$ has rank $2$ is equivalent to requiring that whatever point $\mathbf{x}$ one has on the first image, when one calculates the epipolar line $\mathbf{l'} := \mathbf{Fx}$ , it should pass through some specific epipole $\mathbf{e'}$ . In general, without this requirement, the epipolar lines may become a mess.

We often do this by approximating the closest rank-2 matrix from a given $\mathbf{F}$ . Suppose the algorithm recovers $\mathbf{F}$ , then we want to find $\mathbf{F'}$ of rank two such that the error $\|\mathbf{F}-\mathbf{F'}\|$ is minimized. A natural way to do this is to SVD and truncate out the smallest value. (I will probably revisit this again once I seriously go and learn about SVD, but right now let’s just move on with the rough idea)

There are other useful algorithms, such as the Seven-Point Algorithm (since the fundamental matrix up to scale has only $7$ degrees of freedom, there is a way to compute it using only seven points) and the Five-Point Algorithm (instead of estimating the fundamental matrix, we move to another realm and define the essential matrix, which has only $5$ degrees of freedom instead of $7$ ). I leave them (and my very limited understanding) here and I wish to learn more about them later once I have more time.

The Structure Problem and Triangulation

We’ve made a rough idea how to solve the correspondence problem and the motion problem. So now we can assume the existence of $(\mathbf{x}_i \leftrightarrow \mathbf{x'}_i)_{i=1,\dots,n}$ and $(\mathbf{P}, \mathbf{P'})$ . The structure problem asks us to recover the actual points $\mathbf{X}_1, \dots, \mathbf{X}_n$ such that $\mathbf{P}\mathbf{X}_i \sim \mathbf{x}_i$ and $\mathbf{P'}\mathbf{X}_i \sim \mathbf{x'}_i$ . To solve this, we use a process called triangulation.

Indeed, if $\mathbf{x} \sim \mathbf{PX}$ , then we see that $\mathbf{x} \times \mathbf{PX} = 0$ . Expand $\mathbf{P}$ into three rows $\begin{pmatrix}\mathbf{p}_1^\intercal\\\mathbf{p}_2^\intercal\\\mathbf{p}_3^\intercal\end{pmatrix}$ where each $\mathbf{p}_i$ is a $4$ -vector corresponding to the $i$ th row. Write $\mathbf{x} = \begin{pmatrix}x\\y\\1\end{pmatrix}$ . We have

$\mathbf{x} \times \mathbf{PX} = \begin{pmatrix}x\\y\\1\end{pmatrix} \times \begin{pmatrix}\mathbf{p}_1^\intercal\mathbf{X}\\\mathbf{p}_2^\intercal\mathbf{X}\\\mathbf{p}_3^\intercal\mathbf{X}\end{pmatrix} = \begin{pmatrix}y\mathbf{p}_3^\intercal\mathbf{X} - \mathbf{p}_2^\intercal\mathbf{X}\\\mathbf{p}_1^\intercal\mathbf{X}-x\mathbf{p}_3^\intercal\mathbf{X}\\x\mathbf{p}_2^\intercal\mathbf{X} - y\mathbf{p}_1^\intercal\mathbf{X}\end{pmatrix}.$

These rows are not linearly independent, i.e., the system

$\begin{pmatrix}y\mathbf{p}_3^\intercal\mathbf{X} - \mathbf{p}_2^\intercal\mathbf{X}\\\mathbf{p}_1^\intercal\mathbf{X}-x\mathbf{p}_3^\intercal\mathbf{X}\\x\mathbf{p}_2^\intercal\mathbf{X} - y\mathbf{p}_1^\intercal\mathbf{X}\end{pmatrix} = 0$

has its third row equals $-x$ times the first plus $y$ times the second, so we can discard the third row, and rewrite in the matrix form:

$\begin{pmatrix}y\mathbf{p}_3^\intercal - \mathbf{p}_2^\intercal\\\mathbf{p}_1^\intercal-x\mathbf{p}_3^\intercal\end{pmatrix}\mathbf{X} = 0.$

We can do similarly for the $\mathbf{x'} \sim \mathbf{P'X}$ as well, and merge the systems together, to get:

$\begin{pmatrix}y\mathbf{p}_3^\intercal - \mathbf{p}_2^\intercal\\\mathbf{p}_1^\intercal-x\mathbf{p}_3^\intercal\\y'\mathbf{p'}_3^\intercal - \mathbf{p'}_2^\intercal\\\mathbf{p'}_1^\intercal-x'\mathbf{p'}_3^\intercal\end{pmatrix}\mathbf{X} = 0.$

The rest is just solving this system. This is the linear triangulation process.

This looks simple and easy, but it is still not the optimal one (in a sense), assuming noise exists. The optimal triangulation tries to minimize the reprojection error, i.e., tries to estimate $\widehat{\mathbf{X}}$ that has the maximum likelihood of being the true explanation of the actual object. To do this, we define the MLE for this problem:

$\widehat{\mathbf{X}} := \arg\min_\mathbf{X} \|\mathbf{x} - \pi(\mathbf{PX})\|^2 + \|\mathbf{x'} - \pi(\mathbf{P'X})\|^2,$

where $\pi$ is the dehomogenization perspective projection $\begin{pmatrix}x\\y\\z\end{pmatrix} \mapsto \begin{pmatrix}x/z\\y/z\\1\end{pmatrix}$ . This is an actual MLE under Gaussian noise in image measurements.

To this end, we’ve made a rough way in the basic pipeline: solve for the correspondence problem first (perhaps using Harris detector, or others), and then from the correspondence problem, solve the correspondence geometry problem of two cameras by computing the fundamental matrix, and then from the fundamental matrix, apply the projective reconstruction theorem to postulate the pinhole camera matrices, and once this is done, perform a linear triangulation to recover the structure. This whole thing is packaged as the Structure-from-Motion problem (SfM) and it is one of the fundamental problems in computer vision.

There are also modern algebro-geometric interpretations that would perhaps make a more natural synthesis of algebraic geometry and computer vision. See, for example, this.

I’ve asked for permission from my thesis supervisor, Prof. Andrew Kresch, to register for some other courses alongside the thesis, and he accepted and supported this. ↩︎
I actually used $\mathbb{C}$ by default, but when we talk about orthogonality or something that requires Euclidean inner product, it’s more appropriate to restrict to $\mathbb{R}$. This complicates thing up a bit, since the “degree of freedom” is ambiguous whether we mean the real dimension or the complex dimension of an object (say, a manifold, or a variety). I hope you can decide by yourself whether right now we’re restricting to $\mathbb{R}$ or considering the whole $\mathbb{C}$, and count the dimensions accordingly. ↩︎

Computer Vision and Algebraic Geometry

The Basics of Geometry

Points and Lines

Conics

The Pinhole Camera

Basic Problems of Computer Vision

Multi-View Geometry

Epipolar Geometry

The Problem of Motion

Computing the Fundamental Matrix

The Structure Problem and Triangulation

Comments

Cancel reply

More posts

Stacks

Math 2.1 – A Rant

Computer Vision and Algebraic Geometry

I declare myself as an enemy to the mathematics community, and here’s why