ZHANG’S METHOD

The zhang’s method relies in getting a series of n images of a chessboard patterns where are known

• $n,m$ number of internal corners of the pattern, different in the 2 directions
• $k$ size of squares of the pattern

from this images the goal is to extract the $PPM$ matrix parameters:

flowchart TD

	A[Acquire n images of a planar pattern \n with m internal corners];
	B[For each such image compute an initial \n guess for homography Hi];
	C[Refine each Hi by minimizing \n the reprojection error];
	D[Get an initial guess for A given the homographies Hi];
	E[Given A and Hi , get an initial guess for Ri and T];
	F[Compute an initial guess for lens distortion parameters k];
	G[Refine all parameters A, Ri, Ti, k by minimizing the reprojection error];
	A-->B
	B-->C
	C-->D
	D-->E
	E-->F
	F-->G

GETTING CORNERS IMAGE COORDINATES

Corners can be detected easily from the image by using the Harris detector

SETTING A WRF

so given a set of images the WRF is taken with origin at the top-left corner of the patter(that could easily be detected)

Given this setup with the WRF parallel to the $Z$ axis we can consider the control point to have $z=0$ so the relation with the image points became a HOMOGRAPHY

MAKING A GUESS FOR $H$

so given a pattern with $m$ corners it’s possible to write $m$ sets of 3 linear equations where 2D and 3D coordinates are known so we can compute the $H$ matrix

$$k\stackrel{\sim }{m}=H{\stackrel{\sim }{w}}_{{}^{\prime }}\Rightarrow \stackrel{\sim }{m}\times H{\stackrel{\sim }{w}}_{{}^{\prime }}=0\Rightarrow \left[\begin{array}{c}v{h}_3^T{\stackrel{\sim }{w}}_{{}^{\prime }}-h_2^T{\stackrel{\sim }{w}}_{{}^{\prime }}\\ h_1^T{\stackrel{\sim }{w}}_{{}^{\prime }}-u{h}_3^T{\stackrel{\sim }{w}}_{{}^{\prime }}\\ u{h}_2^T{\stackrel{\sim }{w}}_{{}^{\prime }}-v{h}_1^T{\stackrel{\sim }{w}}_{{}^{\prime }}\end{array}\right]=0$$

So extracting the $h$ vector from the system:

$$\left[\begin{array}{ccc}{0}^T& -{\stackrel{\sim }{w}}^{{}^{\prime }T}& v{\stackrel{\sim }{w}}^{{}^{\prime }T}\\ {\stackrel{\sim }{w}}^{{}^{\prime }T}& 0^T& -u{\stackrel{\sim }{w}}^{{}^{\prime }T}\\ -v{\stackrel{\sim }{w}}^{{}^{\prime }T}& u{\stackrel{\sim }{w}}^{{}^{\prime }T}& 0^T\end{array}\right]\times \left[\begin{array}{c}{h}_1\\ h_2\\ h_3\end{array}\right]=Ah=0$$

From this system in 3 equations in 9 unknowns only 2 equation are linear independent, the last one is discarded. For each image a system of $2m$ equations is built in order to minimize the algebraic error due to the norm of $Ah$ minimizing the problem

$$Ah:h^{\ast }argmi{n}_{h\in R^9}\Vert Ah\Vert$$

Now the solution to this system can be found with singular value decomposition (SVD) of matrix $A$

$$A=UD{V}^T$$

REFINING $H$

In order to minimize the reprojection error $H$ is chosen by the following non linear minimization problem:

$$H=argmi{n}_{H\in R^9}(\sum _{j=1}^m\Vert {\stackrel{\sim }{m}}_j-H{\stackrel{\sim }{w}}_j^{{}^{\prime }}{\Vert }^2)$$

The way the reprojection error is minimized is by comparing the output of the $H$ matrix with the actual image coordinates and minimizing the squared error, the error minimized is also called the geometric error this can be done by the Levenberg-Marquardt algorithm

MAKING A GUESS FOR $A$

With the previous $H$ knowledge it can be said that between $H$ and the $PPM$ exists the following relation

$$H=[h_1,h_2,h_3]=[p_1,p_2,p_4]=\lambda A[r_1,r_2,T]$$

Given that $R$ is an orthogonal matrix the following relations are true

$$r_1^T{r}_2=0\Rightarrow h_1^T{A}^{-T}{A}^{-1}{h}_2=0$$ $$r_1^T{r}_1=r_2^T{r}_2\Rightarrow h_1^T{A}^{-T}{A}^{-1}{h}_1=h_2^T{A}^{-T}{A}^{-1}{h}_2$$

In this equation the unknowns are $B=A^{-T}{A}^{-1}$ given the fact that $A$ is upper-triangular $B$ turns out to be symmetric so the unknowns are just $6$

So given the following definitions

$$B=A^T{A}^{-1}=\left[\begin{array}{ccc}{B}_{11}& B_{12}& B_{13}\\ B_{12}& B_{22}& B_{23}\\ B_{13}& B_{23}& B_{33}\end{array}\right],b=[B_{11},B_{12},B_{22},B_{13},B_{23},B_{33}{]}^T$$ $$h_i^T=[h_{i1},h_{i2},h_{i3},]$$ $$v_{ij}^T=[h_{i1}{h}_{j1},h_{i1}{h}_{j2}+h_{i2}{h}_{j1},h_{i2}{h}_{j2},h_{i3}{h}_{j1}+h_{i1}{h}_{j3},h_{i3}{h}_{j2}+h_{i2}{h}_{j2},h_{i3}{h}_{j3}]$$

So the following relation is true

$$h_i^{T}B{h}_j=v_{ij}^{T}b\Rightarrow \{\begin{array}{l}{h}_i^{T}B{h}_2=0\Rightarrow v_{12}{b}^T=0\\ h_1^{T}B{h}_1=h_2^{T}B{h}_2\Rightarrow v_{11}^{T}b=v_{22}^{T}b\Rightarrow (v_{11}-v_{22}{)}^{T}b=0\end{array}$$

So each image gives 2 independent equations in 6 unknowns for the system $Vb=0$ which can be solved by the SVD

MAKING A GUESS FOR $R$ AND $T$

Now that $A$ can be guessed the extrinsic parameter of the $PPM$ can be computed so given the previous equation

$$h_1=\lambda A{r}_1\Rightarrow r_1=\frac{1}{\lambda }{A}^{-1}{h}_1$$

so because $r_1$ is a unit vector:

$$\lambda =\Vert h_1{A}^{-1}\Vert$$

$r_2$ can be computed in the same way:

$$h_2=\lambda A{r}_2\Rightarrow r_2=\frac{1}{\lambda }{A}^{-1}{h}_2$$

$r_3$ can be derived by exploiting orthogonality $r_3=r_1\times r_2$

Finally $T$ can be computed from the $3^{rd}$ vector

$$h_3=\lambda AT\Rightarrow T=\frac{1}{\lambda }{A}^{-1}{h}_3$$

MAKING A GUESS FOR THE DISTORTION PARAMETERS $K$

At this point the un-distorted coordinates can be calculated from the $H$ matrix and the distorted coordinates can be recovered by the image, so given the lens distortion model:

$$\left[\begin{array}{c}{x}_{{}^{\prime }}\\ y_{{}^{\prime }}\end{array}\right]=L(r)\times \left[\begin{array}{c}\stackrel{\sim }{x}\\ \stackrel{\sim }{y}\end{array}\right]+\left[\begin{array}{c}d\stackrel{\sim }{x}\\ d\stackrel{\sim }{y}\end{array}\right]$$

And a Taylor approximation of the non linear function:

$$L(r)=1+k_1{r}^2+k_2{r}^4$$

And the relation between distorted and ideal coordinates

$$\left[\begin{array}{c}{u}^{{}^{\prime }}\\ v^{{}^{\prime }}\\ 1\end{array}\right]=A\left[\begin{array}{c}{x}^{{}^{\prime }}\\ y^{{}^{\prime }}\\ 1\end{array}\right]=\left[\begin{array}{ccc}{a}_u& 0& u_0\\ 0& a_v& v_0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}{x}^{{}^{\prime }}\\ y^{{}^{\prime }}\\ 1\end{array}\right]\to \{\begin{array}{l}{x}^{{}^{\prime }}=\frac{u^{{}^{\prime }}-u_0}{a_u}\\ y^{{}^{\prime }}=\frac{v^{{}^{\prime }}-v_0}{a_v}\end{array}$$ $$\left[\begin{array}{c}\stackrel{\sim }{u}\\ \stackrel{\sim }{v}\\ 1\end{array}\right]=A\left[\begin{array}{c}\stackrel{\sim }{x}\\ \stackrel{\sim }{y}\\ 1\end{array}\right]\to \{\begin{array}{l}\stackrel{\sim }{x}=\frac{\stackrel{\sim }{u}-u_0}{a_u}\\ \stackrel{\sim }{y}=\frac{\stackrel{\sim }{v}-v_0}{a_v}\end{array}$$

The distortion parameters $k_1,k_2$ can be computed with a linear system of equations

$$\left[\begin{array}{c}{x}_{{}^{\prime }}\\ y_{{}^{\prime }}\end{array}\right]=(1+k_1{r}^2+k_2{r}^4)\left[\begin{array}{c}\stackrel{\sim }{x}\\ \stackrel{\sim }{y}\end{array}\right]\to \{\begin{array}{l}\frac{u^{{}^{\prime }}-u_0}{a_u}(1+k_1{r}^2+k_2{r}^4)\frac{\stackrel{\sim }{u}-u_0}{a_u}\\ \frac{v^{{}^{\prime }}-v_0}{a_v}(1+k_1{r}^2+k_2{r}^4)\frac{\stackrel{\sim }{v}-v_0}{a_v}\end{array}$$ $$\left[\begin{array}{cc}(\stackrel{\sim }{u}-u_0)r^2& \stackrel{\sim }{u}-u_0)r^4\\ (\stackrel{\sim }{v}-v_0)r^2& \stackrel{\sim }{v}-v_0)r^4\end{array}\right]\left[\begin{array}{c}{k}_1\\ k_2\end{array}\right]=\left[\begin{array}{c}(u^{{}^{\prime }}-\stackrel{\sim }{u})\\ (v^{{}^{\prime }}-\stackrel{\sim }{v})\end{array}\right]$$

REFINING ALL PARAMETERS

There is the need to refine all the parameter found in order to minimize the reprojection error, again this can be achieved by an optimization problem where the objective function is

$$\sum _{i=1}^n\sum _{j=1}^m\Vert m_{ij}-\hat{m}(A,k,T_i,R_i,w_j){\Vert }^2$$

The solution to this problem can be computed with Levenberg-Marquardt algorithm

PREVIOUS NEXT