Answers.Body: <p>To understand homographies and how to find them, you will need a good dose of projective geometry. I will briefly describe some preliminary concepts that you need to know before trying to find the homography, but don't expect to understand all these concepts with one reading iteration and only by reading this answer, if you are not familiar with them, especially, if you don't even know what homogenous coordinates are. For more details, I suggest you read the book <a href="http://cvrs.whu.edu.cn/downloads/ebooks/Multiple%20View%20Geometry%20in%20Computer%20Vision%20(Second%20Edition).pdf" rel="noreferrer">Multiple view geometry in computer vision</a> (2004) by Richard Hartley and Andrew Zisserman, in particular, chapter 4.</p>
  
  <h2>The projective space <span class="math-container">$\mathbb{P}^2$</span></h2>
  
  <p><span class="math-container">$\mathbb{P}^2$</span> is the <a href="https://en.wikipedia.org/wiki/Projective_space" rel="noreferrer">projective space</a> of <span class="math-container">$\mathbb{R}^2$</span>, so it is <span class="math-container">$\mathbb{R}^2$</span> augmented with lines and <a href="https://en.wikipedia.org/wiki/Point_at_infinity" rel="noreferrer">points at infinity</a>. All <strong>points</strong> and <strong>lines</strong> of <span class="math-container">$\mathbb{P}^2$</span> actually belong to <span class="math-container">$\mathbb{R}^3$</span>, i.e. they are vectors of three components, because they are <a href="https://en.wikipedia.org/wiki/Homogeneous_coordinates" rel="noreferrer">homogenous representations</a> of the counterparts in <span class="math-container">$\mathbb{R}^2$</span>. To emphasize, in <span class="math-container">$\mathbb{P}^2$</span>, both points <strong>and</strong> lines can be represented by a vector in <span class="math-container">$\mathbb{R}^3$</span>, which is the homogenous representation of the counterpart vector in <span class="math-container">$\mathbb{R}^2$</span> (if it exists, e.g. points at infinity do not exist in <span class="math-container">$\mathbb{R}^2$</span>).</p>
  
  <h2>What is a homography?</h2>
  
  <p>A <a href="https://en.wikipedia.org/wiki/Homography" rel="noreferrer"><strong>homography</strong></a> (aka projectivity, collineation or projective transformation) is an invertible map <span class="math-container">$h$</span> from the projective space <span class="math-container">$\mathbb{P}^2$</span> to itself, <span class="math-container">$$h: \mathbb{P}^2 \rightarrow \mathbb{P}^2,$$</span> such that <span class="math-container">$\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3$</span> lie on the same <strong>straight-line</strong> if and only if <span class="math-container">$h(\mathbf{x}_1), h(\mathbf{x}_2), h(\mathbf{x}_3)$</span> do. </p>
  
  <p>This property is called <strong>collinearity</strong>. In practice, this property means that projective transformations can map straight-lines in one image to straight-line to another image, but it cannot map e.g. straight-lines to parabolas (and vice-versa). So, if you have a distorted image, a homography cannot convert it to a non-distorted image. </p>
  
  <h3>All and only linear maps in <span class="math-container">$\mathbb{P}^2$</span> are homographies</h3>
  
  <p>All linear maps in <span class="math-container">$\mathbb{P}^2$</span> are homographies and only linear maps can be homographies. Hence, when you want to find a homography, you are looking for a linear map in <span class="math-container">$\mathbb{P}^2$</span>.</p>
  
  <h3>A homography can be represented as <span class="math-container">$3 \times 3$</span> matrix</h3>
  
  <p>Given that homographies are linear maps they can be represented as an invertible matrix </p>
  
  <p><span class="math-container">$$\mathbf{H} 
  = 
  \begin{bmatrix} 
  h_{11} &amp; h_{12} &amp; h_{13} \\ 
  h_{21} &amp; h_{22} &amp; h_{23} \\ 
  h_{31} &amp; h_{32} &amp; h_{33} 
  \end{bmatrix} 
  \in \mathbb{R}^{3 \times 3},
  $$</span>
  such that, <span class="math-container">$\forall \mathbf{x} \in \mathbb{P}^2$</span>, the following equation holds
  <span class="math-container">$$
  h(\mathbf{x}) = \mathbf{H}\mathbf{x}
  $$</span></p>
  
  <h3>Homographies map points in <span class="math-container">$\mathbb{P}^2$</span> to points in <span class="math-container">$\mathbb{P}^2$</span></h3>
  
  <p>Given that homographies map points in <span class="math-container">$\mathbb{P}^2$</span> to other points in <span class="math-container">$\mathbb{P}^2$</span> and there's a matrix <span class="math-container">$\mathbf{H} \in \mathbb{R}^{3 \times 3}$</span> for each homography <span class="math-container">$h$</span>, then it follows that, <span class="math-container">$\forall \mathbf{x} \in \mathbb{P}^2$</span>,
  <span class="math-container">\begin{align}
  \mathbf{x}' 
  &amp;= 
  \mathbf{H}\mathbf{x} \\
  \begin{bmatrix} 
  \mathbf{x}'_1 \\ \mathbf{x}'_2 \\ \mathbf{x}'_3
  \end{bmatrix}
  &amp;=
  \begin{bmatrix} 
  h_{11} &amp; h_{12} &amp; h_{13} \\ 
  h_{21} &amp; h_{22} &amp; h_{23} \\ 
  h_{31} &amp; h_{32} &amp; h_{33} 
  \end{bmatrix} 
  \begin{bmatrix} 
  \mathbf{x}_1 \\ \mathbf{x}_2 \\ \mathbf{x}_3
  \end{bmatrix}
  \tag{1}\label{1}
  \end{align}</span>
  where <span class="math-container">$\mathbf{x}' \in \mathbb{P}^2$</span>, for some homography <span class="math-container">$\mathbf{H} \in \mathbb{R}^{3 \times 3}$</span>.</p>
  
  <p>In practice, this means that you can transform points in an image <span class="math-container">$I_1$</span> to points in image <span class="math-container">$I_2$</span> by matrix multiplication. </p>
  
  <h3>A homography has <span class="math-container">$8$</span> degrees of freedom</h3>
  
  <p>Although the matrix <span class="math-container">$\mathbf{H}$</span> has <span class="math-container">$9$</span> entries, it has only <span class="math-container">$8$</span> degrees of freedom, which means that, in practice, there are only <span class="math-container">$8$</span> variables that you need to find. This property comes from the fact that only the ratio between the elements of <span class="math-container">$\mathbf{H}$</span> actually counts. This means that equation \ref{1} can actually be written as 
  <span class="math-container">\begin{align}
  \mathbf{x}' = \lambda \mathbf{H}\mathbf{x} \tag{2}\label{2}
  \end{align}</span>
  for all <span class="math-container">$\lambda \in \mathbb{R} \setminus \{0 \}$</span>.</p>
  
  <h2>How to estimate a homography from point correspondences?</h2>
  
  <p>We want to estimate a homography <span class="math-container">$\mathbf{H} \in \mathbb{R}^{3 \times 3}$</span> from point-to-point correspondences <span class="math-container">$\{(\mathbf{x}^i, \mathbf{x}'^i) \}_{i=1}^N$</span>, where <span class="math-container">$N \geq 4$</span>, such that <span class="math-container">$\mathbf{x}'^i = \mathbf{H}\mathbf{x}^i, \forall i$</span>. </p>
  
  <p>First, recall that the matrix <span class="math-container">$\mathbf{H}$</span> has <span class="math-container">$8$</span> degrees of freedom (i.e. variables we want to find). </p>
  
  <h3>Each point-to-point correspondence represents <span class="math-container">$2$</span> constraints</h3>
  
  <p>Each point-to-point correspondence <span class="math-container">$(\mathbf{x}^i, \mathbf{x}'^i)$</span> accounts for <span class="math-container">$2$</span> constraints, i.e. <span class="math-container">$\mathbf{H}\mathbf{x}^i$</span> maps to the point <span class="math-container">$\mathbf{x}'^i$</span>, which has <span class="math-container">$2$</span> degrees of freedom (even if it's defined by 3 components) because it's represented in homogenous coordinates and so, as for equation \ref{2}, it's defined "up to scale". In other words, these <span class="math-container">$2$</span> degrees of freedom represent <span class="math-container">$2$</span> constraints. </p>
  
  <h3><span class="math-container">$4$</span> point-to-point correspondences are necessary to estimate a homography</h3>
  
  <p>Given that <span class="math-container">$1$</span> point-to-point correspondence represents <span class="math-container">$2$</span> constraints, then <span class="math-container">$4$</span> point-to-point correspondences corresponds to <span class="math-container">$8$</span> constraints. Given this and given that homographies have <span class="math-container">$8$</span> degrees of freedom, at least <span class="math-container">$4$</span> point-to-point correspondences are necessary to estimate a homography.</p>
  
  <p>The equation \ref{2} can actually be written as </p>
  
  <p><span class="math-container">$$
  \mathbf{x}' \times \lambda \mathbf{H}\mathbf{x} = \mathbf{0} \label{3} \tag{3}
  $$</span>
  where <span class="math-container">$\times$</span> is the cross-product.</p>
  
  <h3>Direct linear transformation</h3>
  
  <p>If you manipulate equation \ref{3}, then you will end up with another equation (if you ignore the scaling factor <span class="math-container">$\lambda$</span>, which we can ignore because the homography converts points independently of their magnitude)</p>
  
  <p><span class="math-container">$$
  \mathbf{A}_i \mathbf{h} = \mathbf{0} 
  $$</span>
  where <span class="math-container">$\mathbf{A}_i \in \mathbb{R}^{2 \times 9}$</span> is the <em>design matrix</em> (i.e. the matrix that contains the input data to estimate the homography) that contains the elements of the the point-to-point correspondence <span class="math-container">$(\mathbf{x}^i, \mathbf{x}'^i)$</span> and <span class="math-container">$\mathbf{h} \in \mathbb{R}^{9}$</span> is a vector that contains the <strong>unknown</strong> elements of <span class="math-container">$\mathbf{H}$</span>. The details of this manipulation can be found in section 4.1 of the book <a href="http://cvrs.whu.edu.cn/downloads/ebooks/Multiple%20View%20Geometry%20in%20Computer%20Vision%20(Second%20Edition).pdf" rel="noreferrer">Multiple view geometry in computer vision</a>.</p>
  
  <p>Now, the idea is that you can vertically stack <span class="math-container">$N \geq 4$</span> equations of the form <span class="math-container">$\mathbf{A}_i \mathbf{h} = \mathbf{0}$</span> to build the final linear system that you would like to solve
  <span class="math-container">$$\mathbf{A} \mathbf{h} = \mathbf{0} \tag{4}\label{4}$$</span>
  where <span class="math-container">$\mathbf{A} \in \mathbb{R}^{2N \times 9}$</span>. </p>
  
  <p>The solution to this system is the vector <span class="math-container">$\mathbf{h} \in \mathbb{R}^{9}$</span>, that is, your homography!</p>
  
  <p>If you know something about linear algebra, you know that the solutions to <span class="math-container">$\mathbf{A} \mathbf{h} = \mathbf{0}$</span> are elements of the null space of <span class="math-container">$\mathbf{A}$</span>.</p>
  
  <p>Then, to find <span class="math-container">$\mathbf{h}$</span>, you will typically use <em>singular value decomposition</em> (SVD). See e.g. <a href="https://math.stackexchange.com/q/1771013/168764">How is the null space related to singular value decomposition?</a> for a possible explanation of why you can use SVD to find an element of the null space.</p>
  
  <p>This algorithm (which is described on page 91 of the cited book, i.e. Algorithm 4.1) is called <strong>direct linear transformation</strong>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-10T21:57:14.740Z
Answers.Text: A wonderful explanation .
Answers.UserDisplayName: Hisan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-10T13:30:50.760Z
Answers.LastActivityDate: 2020-05-10T22:17:25.727Z
Answers.LastEditDate: 2020-05-10T22:17:25.727Z
Answers.UserDisplayName: nbro
Body: <p>I want to understand the process of finding a homography matrix given 4 points in both images. I am able to do that in python OpenCV, but I wonder how it works behind the scenes.</p>
  
  <p>Suppose I have points <span class="math-container">$p_1, p_2, p_3, p_4$</span> in the first image and <span class="math-container">$p'_1, p'_2, p'_3, p'_4$</span> in the second. How am I going to generate the homography matix given these points.</p>
  
Tags: <computer-vision><linear-algebra><projective-transformations>
Title: How do you find the homography matrix given 4 points in both images?
UserDisplayName: Hisan
ThreadText: # How do you find the homography matrix given 4 points in both images?
  
  (Asked by: username_0 on 2020-05-10)
  
  I want to understand the process of finding a homography matrix given 4 points in both images. I am able to do that in python OpenCV, but I wonder how it works behind the scenes.
  
  Suppose I have points $p\_1, p\_2, p\_3, p\_4$ in the first image and $p'\_1, p'\_2, p'\_3, p'\_4$ in the second. How am I going to generate the homography matix given these points.
  
  **Tags:** computer-vision, linear-algebra, projective-transformations
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-10. Score: 9 | Accepted answer
  
  To understand homographies and how to find them, you will need a good dose of projective geometry. I will briefly describe some preliminary concepts that you need to know before trying to find the homography, but don't expect to understand all these concepts with one reading iteration and only by reading this answer, if you are not familiar with them, especially, if you don't even know what homogenous coordinates are. For more details, I suggest you read the book [Multiple view geometry in computer vision](http://cvrs.whu.edu.cn/downloads/ebooks/Multiple%20View%20Geometry%20in%20Computer%20Vision%20(Second%20Edition).pdf) (2004) by Richard Hartley and Andrew Zisserman, in particular, chapter 4.
  
  ## The projective space $\mathbb{P}^2$
  
  $\mathbb{P}^2$ is the [projective space](https://en.wikipedia.org/wiki/Projective_space) of $\mathbb{R}^2$, so it is $\mathbb{R}^2$ augmented with lines and [points at infinity](https://en.wikipedia.org/wiki/Point_at_infinity). All **points** and **lines** of $\mathbb{P}^2$ actually belong to $\mathbb{R}^3$, i.e. they are vectors of three components, because they are [homogenous representations](https://en.wikipedia.org/wiki/Homogeneous_coordinates) of the counterparts in $\mathbb{R}^2$. To emphasize, in $\mathbb{P}^2$, both points **and** lines can be represented by a vector in $\mathbb{R}^3$, which is the homogenous representation of the counterpart vector in $\mathbb{R}^2$ (if it exists, e.g. points at infinity do not exist in $\mathbb{R}^2$).
  
  ## What is a homography?
  
  A [**homography**](https://en.wikipedia.org/wiki/Homography) (aka projectivity, collineation or projective transformation) is an invertible map $h$ from the projective space $\mathbb{P}^2$ to itself, $$h: \mathbb{P}^2 \rightarrow \mathbb{P}^2,$$ such that $\mathbf{x}\_1, \mathbf{x}\_2, \mathbf{x}\_3$ lie on the same **straight-line** if and only if $h(\mathbf{x}\_1), h(\mathbf{x}\_2), h(\mathbf{x}\_3)$ do.
  
  This property is called **collinearity**. In practice, this property means that projective transformations can map straight-lines in one image to straight-line to another image, but it cannot map e.g. straight-lines to parabolas (and vice-versa). So, if you have a distorted image, a homography cannot convert it to a non-distorted image.
  
  ### All and only linear maps in $\mathbb{P}^2$ are homographies
  
  All linear maps in $\mathbb{P}^2$ are homographies and only linear maps can be homographies. Hence, when you want to find a homography, you are looking for a linear map in $\mathbb{P}^2$.
  
  ### A homography can be represented as $3 \times 3$ matrix
  
  Given that homographies are linear maps they can be represented as an invertible matrix
  
  $$\mathbf{H}
  =
  \begin{bmatrix}
  h\_{11} & h\_{12} & h\_{13} \\
  h\_{21} & h\_{22} & h\_{23} \\
  h\_{31} & h\_{32} & h\_{33}
  \end{bmatrix}
  \in \mathbb{R}^{3 \times 3},
  $$
  such that, $\forall \mathbf{x} \in \mathbb{P}^2$, the following equation holds
  $$
  h(\mathbf{x}) = \mathbf{H}\mathbf{x}
  $$
  
  ### Homographies map points in $\mathbb{P}^2$ to points in $\mathbb{P}^2$
  
  Given that homographies map points in $\mathbb{P}^2$ to other points in $\mathbb{P}^2$ and there's a matrix $\mathbf{H} \in \mathbb{R}^{3 \times 3}$ for each homography $h$, then it follows that, $\forall \mathbf{x} \in \mathbb{P}^2$,
  \begin{align}
  \mathbf{x}'
  &=
  \mathbf{H}\mathbf{x} \\
  \begin{bmatrix}
  \mathbf{x}'\_1 \\ \mathbf{x}'\_2 \\ \mathbf{x}'\_3
  \end{bmatrix}
  &=
  \begin{bmatrix}
  h\_{11} & h\_{12} & h\_{13} \\
  h\_{21} & h\_{22} & h\_{23} \\
  h\_{31} & h\_{32} & h\_{33}
  \end{bmatrix}
  \begin{bmatrix}
  \mathbf{x}\_1 \\ \mathbf{x}\_2 \\ \mathbf{x}\_3
  \end{bmatrix}
  \tag{1}\label{1}
  \end{align}
  where $\mathbf{x}' \in \mathbb{P}^2$, for some homography $\mathbf{H} \in \mathbb{R}^{3 \times 3}$.
  
  In practice, this means that you can transform points in an image $I\_1$ to points in image $I\_2$ by matrix multiplication.
  
  ### A homography has $8$ degrees of freedom
  
  Although the matrix $\mathbf{H}$ has $9$ entries, it has only $8$ degrees of freedom, which means that, in practice, there are only $8$ variables that you need to find. This property comes from the fact that only the ratio between the elements of $\mathbf{H}$ actually counts. This means that equation \ref{1} can actually be written as
  \begin{align}
  \mathbf{x}' = \lambda \mathbf{H}\mathbf{x} \tag{2}\label{2}
  \end{align}
  for all $\lambda \in \mathbb{R} \setminus \{0 \}$.
  
  ## How to estimate a homography from point correspondences?
  
  We want to estimate a homography $\mathbf{H} \in \mathbb{R}^{3 \times 3}$ from point-to-point correspondences $\{(\mathbf{x}^i, \mathbf{x}'^i) \}\_{i=1}^N$, where $N \geq 4$, such that $\mathbf{x}'^i = \mathbf{H}\mathbf{x}^i, \forall i$.
  
  First, recall that the matrix $\mathbf{H}$ has $8$ degrees of freedom (i.e. variables we want to find).
  
  ### Each point-to-point correspondence represents $2$ constraints
  
  Each point-to-point correspondence $(\mathbf{x}^i, \mathbf{x}'^i)$ accounts for $2$ constraints, i.e. $\mathbf{H}\mathbf{x}^i$ maps to the point $\mathbf{x}'^i$, which has $2$ degrees of freedom (even if it's defined by 3 components) because it's represented in homogenous coordinates and so, as for equation \ref{2}, it's defined "up to scale". In other words, these $2$ degrees of freedom represent $2$ constraints.
  
  ### $4$ point-to-point correspondences are necessary to estimate a homography
  
  Given that $1$ point-to-point correspondence represents $2$ constraints, then $4$ point-to-point correspondences corresponds to $8$ constraints. Given this and given that homographies have $8$ degrees of freedom, at least $4$ point-to-point correspondences are necessary to estimate a homography.
  
  The equation \ref{2} can actually be written as
  
  $$
  \mathbf{x}' \times \lambda \mathbf{H}\mathbf{x} = \mathbf{0} \label{3} \tag{3}
  $$
  where $\times$ is the cross-product.
  
  ### Direct linear transformation
  
  If you manipulate equation \ref{3}, then you will end up with another equation (if you ignore the scaling factor $\lambda$, which we can ignore because the homography converts points independently of their magnitude)
  
  $$
  \mathbf{A}\_i \mathbf{h} = \mathbf{0}
  $$
  where $\mathbf{A}\_i \in \mathbb{R}^{2 \times 9}$ is the *design matrix* (i.e. the matrix that contains the input data to estimate the homography) that contains the elements of the the point-to-point correspondence $(\mathbf{x}^i, \mathbf{x}'^i)$ and $\mathbf{h} \in \mathbb{R}^{9}$ is a vector that contains the **unknown** elements of $\mathbf{H}$. The details of this manipulation can be found in section 4.1 of the book [Multiple view geometry in computer vision](http://cvrs.whu.edu.cn/downloads/ebooks/Multiple%20View%20Geometry%20in%20Computer%20Vision%20(Second%20Edition).pdf).
  
  Now, the idea is that you can vertically stack $N \geq 4$ equations of the form $\mathbf{A}\_i \mathbf{h} = \mathbf{0}$ to build the final linear system that you would like to solve
  $$\mathbf{A} \mathbf{h} = \mathbf{0} \tag{4}\label{4}$$
  where $\mathbf{A} \in \mathbb{R}^{2N \times 9}$.
  
  The solution to this system is the vector $\mathbf{h} \in \mathbb{R}^{9}$, that is, your homography!
  
  If you know something about linear algebra, you know that the solutions to $\mathbf{A} \mathbf{h} = \mathbf{0}$ are elements of the null space of $\mathbf{A}$.
  
  Then, to find $\mathbf{h}$, you will typically use *singular value decomposition* (SVD). See e.g. [How is the null space related to singular value decomposition?](https://math.stackexchange.com/q/1771013/168764) for a possible explanation of why you can use SVD to find an element of the null space.
  
  This algorithm (which is described on page 91 of the cited book, i.e. Algorithm 4.1) is called **direct linear transformation**.
  
  > **Comments:**
  > **username_0**: A wonderful explanation .  
  
  ---
  
  