25
$\begingroup$

I went through this thread Mapping Irregular Quadrilateral to a Rectangle

If i know the 4 corresponding points in image say
p1->p1'
p2->p2'
p3->p3'
p4->p4'

then how to compute pi(x,y) from pi'(x,y)

enter image description here enter image description here

i don't know how to compute elements in Homography matrix H from those 8 known points
[x']= [h11 h12 h13] [x]
[y']= [h21 h22 h23] [y]
[(1)]=[h31 h32 (1)] [(1)]

[Excuse me. I am not sure if I should extend this question, or create a new one, since I can't post comments on threads]

I want to ask the same question, but using absolute values so I can visualize it. Lets say my points on the image plane are:

p[0] = x:407 y:253
p[1] = x:386 y:253
p[2] = x:406 y:232
p[3] = x:385 y:232

these points are in a 500px width x 333px height image plane with 0,0 at top left corner. These points represents a picture of a real plane where a 30mm side square are located. Assuming this picture was taken by a fixed camera at origin heading Z axis.

So, I know the physical distance between p0,p1 ; p0,p2 ; p1,p3; p2,p3 are 30mm.

But is it possible to get the X,Y,Z from each of these points using only this information above?

$\endgroup$
  • $\begingroup$ Thank you guyz. after searching a lot i found this wiimote librarry by brian brianpeek.com/page/wiimotelib. in his code warp matrix calculation is implemented. that's what i was actually looking for. $\endgroup$ – Sagar Mar 23 '14 at 19:28
21
$\begingroup$

You can compute the homography matrix H with your eight points with a matrix system such that the four correspondance points $(p_1, p_1'), (p_2, p_2'), (p_3, p_3'), (p_4, p_4')$ are written as $2\times9$ matrices such as:

$p_i = \begin{bmatrix} -x_i \quad -y_i \quad -1 \quad 0 \quad 0 \quad 0 \quad x_ix_i' \quad y_ix_i' \quad x_i' \\ 0 \quad 0 \quad 0 \quad -x_i \quad -y_i \quad -1 \quad x_iy_i' \quad y_iy_i' \quad y_i' \end{bmatrix}$

It is then possible to stack them into a matrix $P$ to compute:

$PH = 0$

Such as:

$PH = \begin{bmatrix} -x_1 \quad -y_1 \quad -1 \quad 0 \quad 0 \quad 0 \quad x_1x_1' \quad y_1x_1' \quad x_1' \\ 0 \quad 0 \quad 0 \quad -x_1 \quad -y_1 \quad -1 \quad x_1y_1' \quad y_1y_1' \quad y_1' \\ -x_2 \quad -y_2 \quad -1 \quad 0 \quad 0 \quad 0 \quad x_2x_2' \quad y_2x_2' \quad x_2' \\ 0 \quad 0 \quad 0 \quad -x_2 \quad -y_2 \quad -1 \quad x_2y_2' \quad y_2y_2' \quad y_2' \\ -x_3 \quad -y_3 \quad -1 \quad 0 \quad 0 \quad 0 \quad x_3x_3' \quad y_3x_3' \quad x_3' \\ 0 \quad 0 \quad 0 \quad -x_3 \quad -y_3 \quad -1 \quad x_3y_3' \quad y_3y_3' \quad y_3' \\ -x_4 \quad -y_4 \quad -1 \quad 0 \quad 0 \quad 0 \quad x_4x_4' \quad y_4x_4' \quad x_4' \\ 0 \quad 0 \quad 0 \quad -x_4 \quad -y_4 \quad -1 \quad x_4y_4' \quad y_4y_4' \quad y_4' \\ \end{bmatrix} \begin{bmatrix}h1 \\ h2 \\ h3 \\ h4 \\ h5 \\ h6 \\ h7 \\ h8 \\h9 \end{bmatrix} = 0$

While adding an extra constraint $|H|=1$ to avoid the obvious solution of $H$ being all zeros. It is easy to use SVD $P = USV^\top$ and select the last singular vector of $V$ as the solution to $H$.

Note that this gives you a DLT (direct linear transform) homography that minimizes algebraic error. This error is not geometrically meaningful and so the computed homography may not be as good as you expect. One typically applies nonlinear least squares with a better cost function (e.g. symmetric transfer error) to improve the homography.

Once you have your homography matrix $H$, you can compute the projected coordinates of any point $p(x, y)$ such as:

$\begin{bmatrix} x' / \lambda \\ y' / \lambda \\ \lambda \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} x \\ y \\ 1 \end{bmatrix}$

$\endgroup$
  • $\begingroup$ The 8x2 p_i matrices seems to be 9x2 in the answer. $\endgroup$ – anorm Oct 14 '15 at 7:29
  • $\begingroup$ @anorm They should be 9x2. I think 8x2 is just a typo $\endgroup$ – marcman Nov 9 '15 at 19:20
  • $\begingroup$ @marcman h33 has been set to 1. That why its 8. $\endgroup$ – Sabri Meviş Nov 16 '15 at 10:31
  • $\begingroup$ @SabriMeviş: Regardless, PH is trying to multiply (9x8) by an (1x8). Won't work. That vector should be [h_1, ..., h_8, 1]' in your case. I also think anorm was referring to the block LaTeX p_i where they are clearly (9x2) but described as (8x2) $\endgroup$ – marcman Nov 16 '15 at 15:02
  • 4
    $\begingroup$ @tony can you clarify the dimension mismatch, and how h1-h8 relate to h11-h33 ? $\endgroup$ – Guig Jun 19 '17 at 21:19
8
$\begingroup$

Rather than taking SVD of the system, there is an easier way to solve this. since the last component in the $H$ vector is considered as $1$, we can add one more constraint equation $(h9=1)$ (since $h_{33}$ is considered $1$) to this set and convert $P$ matrix into $9\times 9$ matrix and system will become non-homogenous.

$PH = \begin{bmatrix} -x_1 & -y_1 & -1 & 0 & 0 & 0 & x_1x_1' & y_1x_1' & x_1' \\ 0 & 0 & 0 & -x_1 & -y_1 & -1 & x_1y_1' & y_1y_1' & y_1' \\ -x_2 & -y_2 & -1 & 0 & 0 & 0 & x_2x_2' & y_2x_2' & x_2' \\ 0 & 0 & 0 & -x_2 & -y_2 & -1 & x_2y_2' & y_2y_2' & y_2' \\ -x_3 & -y_3 & -1 & 0 & 0 & 0 & x_3x_3' & y_3x_3' & x_3' \\ 0 & 0 & 0 & -x_3 & -y_3 & -1 & x_3y_3' & y_3y_3' & y_3' \\ -x_4 & -y_4 & -1 & 0 & 0 & 0 & x_4x_4' & y_4x_4' & x_4' \\ 0 & 0 & 0 & -x_4 & -y_4 & -1 & x_4y_4' & y_4y_4' & y_4' \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix}h1 \\ h2 \\ h3 \\ h4 \\ h5 \\ h6 \\ h7 \\ h8 \\h9 \end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\1 \end{bmatrix}$

This is a $Ax=b$ kind of problem which can be solved much faster than computing SVD.

$\endgroup$
  • 1
    $\begingroup$ There are some special cases where the ninth element is zero $\endgroup$ – Sridhar Thiagarajan May 10 at 2:57
2
$\begingroup$

After a while I am answering my own question (in a way I can understand.I hope it can help other people too)

I am really sorry for not having a good math basis, but there is a GAP between information most people provide from copy/pasted formulas found on google and what I can understand. I see, by the way, many formulas have some mistakes that confuses those in the search of an answer.

So,

Basically, you have 2 collections of 4 points, A and B rectangles.

A = { p1x,p1y ; p2x,p2y ; p3x,p3y ; p4x,p4y }

B = { p1x,p1y ; p2x,p2y ; p3x,p3y ; p4x,p4y }

I want to map a point in rectangle A to rectangle B.

I then build a 8 x n matrix (M1), where n is number of points * 2(x,y). (result will be a 8x8 matrix)

for each point:
{xA, yA, 1, 0, 0, 0, -xA*xB, -yA*xB}
{0, 0, 0, xA, yA, 1, -xA*yB, -yA*yB}

I also make a 1 x 8 matrix (M2) with the "target"(B) points. Result must be 1x8 and not 8x1.

for each point:
{xB}
{yB}

Next, we are finding the so called H matrix. I am using this formula:

H = ( M1 transpose * M1 )inv * ( M1 transpose * M2)

Result is a 3 x 3 matrix (H).

Finally, any 2d point in rectangle A can be found in rectangle B using this operation:

point_in_A = (x,y,1)
tempMatrix (1x3) = H(3x3) * point_in_A(1x3)
tempMatrix will be (x, y, scale);

using tempMatrix values below:

result xy_in_B = (x / scale , y / scale);

That is it.

$\endgroup$
  • 3
    $\begingroup$ Please, use Latex. $\endgroup$ – 1 0 Jul 15 '16 at 7:35
  • 3
    $\begingroup$ Hi, this is unfortunately not the best solution. You're finding the 3x3 homography as a solution to over-specified linear system in eight unknowns, assuming the ninth is one (also missing in your answer). This works as long as the ninth element of H is nonzero. But there are special cases when it is zero and then this method fails. Better use the SVD trick for total least squares (refer to e.g. the Hartley-Zisserman book for algorithm and details). $\endgroup$ – the swine Jun 20 '17 at 13:05
  • 1
    $\begingroup$ @MithleshUpadhyay OP may have a Latex allergy. In this case, SE's MathJax support may be a good alternate :-) $\endgroup$ – uhoh Sep 12 '17 at 0:32
  • 1
    $\begingroup$ the end result is H is a 1x8 matrix not a 3x3 $\endgroup$ – ghostbust555 Nov 3 '17 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.