跳转至

图像拼接

Image Stitching

Affine Transformation

[x′y′1]=[abcdef001][xy1]=[ax+by+cdx+ey+f1] \begin{bmatrix}x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} a & b & c \\ d & e & f \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix}x \\ y \\ 1 \end{bmatrix} = \begin{bmatrix}ax+by+c \\ dx+ey+f \\ 1 \end{bmatrix}

Solution1:\texttt{Solution1:}

[x′y′]=[xy1000000xy1]=[abcdef] \begin{bmatrix}x' \\ y' \end{bmatrix} = \begin{bmatrix} x & y & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & x & y & 1 \end{bmatrix} = \begin{bmatrix}a \\ b \\ c \\ d \\ e \\ f \end{bmatrix}
[x1y11000000x1y11x2y21000000x2y21⋮⋮⋮⋮⋮⋮xnyn1000000xnyn1][abcdef]=[x1′y1′x2′y2′⋮xn′yn′] \begin{bmatrix} x_1 & y_1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & x_1 & y_1 & 1 \\ x_2 & y_2 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & x_2 & y_2 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ x_n & y_n & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & x_n & y_n & 1 \\ \end{bmatrix} \begin{bmatrix}a \\ b \\ c \\ d \\ e \\ f \end{bmatrix} = \begin{bmatrix}x_1' \\ y_1' \\ x_2' \\ y_2' \\ \vdots \\ x_n' \\ y_n' \end{bmatrix}
⇒A2n×6  t6×1=b2n×1\Rightarrow \bm{\underset{2n\times 6}{A}\; \underset{6\times 1}{t} = \underset{2n\times 1}{b}}
  • Least squares: find t\bm{t} that minimizes ∣∣At−b∣∣2\bm{||At - b||^2}
  • The solution is given by
ATAt=Atbt=(ATA)−1Atb \bm{A^TAt = A^tb } \\ \bm{t = (A^TA)^{-1}A^tb } \\

Solution2:\texttt{Solution2:}

[x1y11000−x1′000x1y11−y1′x2y21000−x1′000x2y21−y1′⋮xnyn1000−xn′000xnyn1−yn′][abcdef1]=[00⋮00] \begin{bmatrix} x_1 & y_1 & 1 & 0 & 0 & 0 & -x_1' \\ 0 & 0 & 0 & x_1 & y_1 & 1 & -y_1' \\ x_2 & y_2 & 1 & 0 & 0 & 0 & -x_1' \\ 0 & 0 & 0 & x_2 & y_2 & 1 & -y_1' \\ &&&& \vdots \\ x_n & y_n & 1 & 0 & 0 & 0 & -x_n' \\ 0 & 0 & 0 & x_n & y_n & 1 & -y_n' \\ \end{bmatrix} \begin{bmatrix} a \\ b \\ c \\ d \\ e \\ f \\ 1 \end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ \vdots \\ 0 \\ 0 \end{bmatrix}

Projective Transformation

[x′y′1]≅[h00h01h02h10h11h12h20h21h22][xy1] \begin{bmatrix}x'\\ y' \\ 1 \end{bmatrix} \cong \begin{bmatrix} h_{00} & h_{01} & h_{02} \\ h_{10} & h_{11} & h_{12} \\ h_{20} & h_{21} & h_{22} \end{bmatrix} \begin{bmatrix}x \\ y \\ 1 \end{bmatrix}
xi′=h00xi+h01yi+h02h20xi+h21yi+h22x_i' = \frac{h_{00}x_i + h_{01}y_i + h_{02}}{h_{20}x_i + h_{21}y_i + h_{22}}
yi′=h10xi+h11yi+h12h20xi+h21yi+h22y_i' = \frac{h_{10}x_i + h_{11}y_i + h_{12}}{h_{20}x_i + h_{21}y_i + h_{22}}
xi′(h20xi+h21yi+h22)=h00xi+h01yi+h02x_i'(h_{20}x_i + h_{21}y_i + h_{22}) = h_{00}x_i + h_{01}y_i + h_{02}
yi′(h20xi+h21yi+h22)=h10xi+h11yi+h12y_i'(h_{20}x_i + h_{21}y_i + h_{22}) = h_{10}x_i + h_{11}y_i + h_{12}
[x1y11000−x1′x1−x1′y1−x1′000x1y11−y1′x1−y1′y1−y1′⋮xnyn1000−xn′xn−xn′yn−xn′000xnyn1−yn′xn−yn′yn−yn′][h00h01h02h10h11h12h20h21h22]=[00⋮00] \begin{bmatrix} x_1 & y_1 & 1 & 0 & 0 & 0 & -x_1'x_1 & -x_1'y_1 & -x_1' \\ 0 & 0 & 0 & x_1 & y_1 & 1 & -y_1'x_1 & -y_1'y_1 & -y_1' \\ &&&& \vdots \\ x_n & y_n & 1 & 0 & 0 & 0 & -x_n'x_n & -x_n'y_n & -x_n' \\ 0 & 0 & 0 & x_n & y_n & 1 & -y_n'x_n & -y_n'y_n & -y_n'\\ \end{bmatrix} \begin{bmatrix}h_{00} \\ h_{01} \\ h_{02} \\ h_{10} \\ h_{11} \\ h_{12} \\ h_{20} \\ h_{21} \\ h_{22} \end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ \vdots \\ 0 \\ 0 \end{bmatrix}
⇒A2n×9  h9×1=02n×1\Rightarrow \bm{\underset{2n\times 9}{A}\; \underset{9\times 1}{h} = \underset{2n\times 1}{0}}
  • Least squares: find h\bm{h} that minimizes ∣∣Ah−0∣∣2\bm{||Ah - 0||^2}
  • Since h\bm{h} is defined up to scale, solve for unit vector h^\hat{\bm{h}}
  • Solution: h^\hat{\bm{h}} = eigenvector of ATA\bm{A^TA} with smallest eigenvalue

RANSAC

  1. Randomly choose s samples. Typically s = minimum sample size that lets you fit a model
  2. Fit a model (e.g., transformation matrix) to those samples
  3. Count the number of inliers that approximately fit the model
  4. Repeat N times
  5. Choose the model that has the largest set of inliers