Geometry-based Methods in Vision

Affine Rectification

Affine rectification aims to correct the perspective distortion of an image, restoring affine geometric properties. Here is a detailed breakdown of the algorithm and relevant equations:

1. User Annotation of Lines: The user interactively annotates four line segments on the image. Each segment is defined by two points, and the user clicks on the image to specify the coordinates of these points. A mouse event is used to capture the user's click coordinates, and these points are stored.
2. Line Equation Calculation: For each pair of annotated line segment endpoints, the line equation is calculated using the cross product of the two points. The cross product formula is:

   \[ l = \mathbf{p_1} \times \mathbf{p_2} \]

   where \(\mathbf{p_1}\) and \(\mathbf{p_2}\) are the homogeneous coordinates of the two points. The resulting \(l\) is the equation of the line.
3. Calculating Vanishing Points and the Line at Infinity: For each pair of parallel lines (the four lines annotated by the user), the vanishing point is computed as the cross product of the two lines. The vanishing point represents the intersection of parallel lines in the image plane. The cross product is calculated as:

   \[ v = l_1 \times l_2 \]

   where \( l_1 \) and \( l_2 \) are the equations of two parallel lines, and \( v \) is their vanishing point.

   By computing vanishing points for two pairs of parallel lines, their cross product gives the line at infinity \( l_\infty \):

   \[ l_\infty = v_1 \times v_2 \]

4. Affine Rectification Homography Matrix: The goal of affine rectification is to transform the image so that parallel lines remain parallel. Using the line at infinity, the homography matrix for affine rectification can be constructed as:

   \[ H_A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ l_{\infty,1} & l_{\infty,2} & l_{\infty,3} \end{bmatrix} \]

   where \( l_{\infty,1} \), \( l_{\infty,2} \), and \( l_{\infty,3} \) are the coordinates of the line at infinity in homogeneous form. This matrix transforms the image to affine space.
5. Image Rectification and Display: The original image is transformed using the homography matrix \( H_A \) via OpenCV's warpPerspective function. The rectified image, where parallel lines have been restored, is then displayed and saved.

Metric Rectification

After affine rectification, metric rectification further restores the image's scale and angles so that orthogonal lines in the real scene appear orthogonal in the image. The detailed algorithm steps are:

1. User Re-annotation of Lines: After affine rectification, the user is required to annotate four new line segments. Again, the user clicks on the image to specify the start and end points of these segments, which are used for metric rectification.
2. Calculating Orthogonality Constraints: Metric rectification aims to restore the orthogonality of line pairs. From the user-annotated lines, their equations are recalculated. The row constraint for two lines \( l_1 \) and \( l_2 \) is given by:

   \[ r(l_1, l_2) = [x_1 z_2, x_1 y_2 + x_2 y_1, y_1 z_2] \]

   where \( (x_1, y_1) \) and \( (x_2, y_2) \) are the normalized coordinates of the two lines.
3. Computing the Conic at Infinity \( C'_{\infty} \): Using the orthogonal line pairs, the metric rectification constraint is derived by calculating the conic at infinity matrix \( C'_{\infty} \). From the row constraints, the matrix coefficients are computed by taking the cross product of the constraints:

   \[ c = r(l_1, l_2) \times r(l_3, l_4) \]

   The resulting conic at infinity matrix is:

   \[ C'_{\infty} = \begin{bmatrix} a & b & 0 \\ b & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]

   where \( a \) and \( b \) are derived from the computed coefficients \( c \).
4. Verifying Orthogonality: Using the conic matrix \( C'_{\infty} \), the orthogonality of the annotated line pairs is verified by checking that the dot product of the line equations satisfies the orthogonality condition:

   \[ l_1^T C'_{\infty} l_2 \approx 0 \]

   If this condition holds, the lines are orthogonal.
5. Computing the Metric Rectification Homography Matrix: By performing Singular Value Decomposition (SVD) on the conic matrix \( C'_{\infty} \), the metric rectification homography matrix \( H_S \) is calculated. The SVD is given by:

   \[ C'_{\infty} = U S V^T \]

   By adjusting the singular values in \( S \), the metric rectification homography matrix \( H_S \) is computed as:

   \[ H_S = U \sqrt{S^{-1}} V^T \]

   This matrix transforms the image into metric space.
6. Image Rectification and Display: Finally, the complete transformation matrix is obtained by multiplying the affine rectification matrix \( H_A \) and the metric rectification matrix \( H_S \):

   \[ H = H_A \cdot H_S \]

   This matrix is used to perform metric rectification on the image, restoring the true scale and orthogonal relationships. The rectified image, where orthogonal lines are correctly orthogonal, is displayed and saved.

Algorithm Steps:

1. User Interaction (Obtaining Corresponding Points):
   • I first used OpenCV to display the background image and allowed the user to select four points on the background image via mouse clicks using the click_event function. These points are stored in the global list points.
   • These four points (desk_points) represent the locations on the background image where the target image will be mapped.
   • At the same time, I defined the four corner points of the target image (target_points):

     Point 1: (0, 0, 1) 
     
     Point 2: (w, 0, 1) 
     
     Point 3: (w, h, 1) 
     
     Point 4: (0, h, 1)
                         

     where \( w \) and \( h \) are the width and height of the target image, respectively.
2. Computing the Homography Matrix \( H \):
   • I utilized the set of corresponding points to compute the homography matrix \( H \), satisfying the following relationship:

     \[ s \begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = H \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} \]

     where \( (x, y, 1) \) are points in the target image, \( (x', y', 1) \) are the corresponding points in the background image, and \( s \) is a scale factor.
   • To solve for \( H \), I constructed a linear system \( A \vec{h} = 0 \), where \( \vec{h} \) is the nine-dimensional vector form of \( H \).
   • Constructing Matrix \( A \): For each pair of corresponding points, I used the construct_A_matrix function to build the matrix \( A \):

     \[ A = \begin{bmatrix} -x_i & -y_i & -1 & 0 & 0 & 0 & x_i' x_i & x_i' y_i & x_i' \\ 0 & 0 & 0 & -x_i & -y_i & -1 & y_i' x_i & y_i' y_i & y_i' \end{bmatrix} \]

   • Solving for \( H \): I employed Singular Value Decomposition (SVD) to solve the above equation (via the get_homography_matrix function):

     \[ A = U \Sigma V^T \]

     \( H \) corresponds to the column of \( V \) associated with the smallest singular value, reshaped into a \( 3 \times 3 \) matrix.
3. Image Perspective Transformation and Composition:
   • Using the computed homography matrix \( H \), I performed a perspective transformation on the target image (using the composite_image function):

     warped_target = warpPerspective(target_img, H, (width, height))
                         

   • Created a mask (mask) to determine the non-zero pixels in the target image.
   • Overlaid the transformed target image onto the background image to generate the composite image (combined_image).

Main Function Descriptions:

• click_event: Handles mouse click events, records the points selected by the user on the background image, and draws green circles at the clicked positions.
• draw_circle: Draws circles at specified positions to mark the points selected by the user.
• add_mouse_response: Sets up the mouse callback function and waits for the user to input four points.
• construct_A_matrix: Constructs the matrix \( A \) based on the corresponding points, used to compute the homography matrix.
• get_homography_matrix: Uses the SVD method to solve for the homography matrix \( H \).
• composite_image: Uses the computed \( H \) to perform a perspective transformation on the target image and composes it with the background image.

Mathematical Formulas:

• Homography Transformation Relationship:

  \[ s \begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = H \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} \]

• Construction of Matrix \( A \):

  \[ A = \begin{bmatrix} -x_i & -y_i & -1 & 0 & 0 & 0 & x_i' x_i & x_i' y_i & x_i' \\ 0 & 0 & 0 & -x_i & -y_i & -1 & y_i' x_i & y_i' y_i & y_i' \end{bmatrix} \]

• SVD Decomposition to Solve for \( H \):

  \[ A = U \Sigma V^T \]

  The solution for \( H \) is the column vector in \( V \) corresponding to the smallest singular value, reshaped into a \( 3 \times 3 \) matrix.