findHomography returns bad homography and ouliers in the inlier mask

cdeln commented 1 month ago

System Information

OpenCV python version: 4.9.0.80 Operating System / Platform: Ubuntu 23.10 Python version: 3.10.14

Detailed description

findHomography returns a bad homography and an inlier mask with outliers. The RANSAC reprojection threshold is set to 5 pixels, but checking the reprojection error manually afterwards using the returned homography and inlier mask gives a maximum error around 410 pixels (i.e. the inlier mask contains outliers).

Steps to reproduce

Put the source_points.json and the target_points.json files in your current working directory and run the following script

import json

import cv2 as cv
import numpy as np

# Load source and target points from JSON
with open('source_points.json', 'r') as f:
    source_points = np.array(json.load(f))

with open('target_points.json', 'r') as f:
    target_points = np.array(json.load(f))

# Estimate homography from source to target using RANSAC with a specified point to point distance threshold
# Use the "index with None trick" to unsqueeze one axis to fit OpenCV shape requirements
point_to_point_distance_threshold = 5
homography, mask = cv.findHomography(source_points[:, None, :], target_points[:, None, :], cv.RANSAC, point_to_point_distance_threshold)

# Extract the points that passed in the RANSAC step using the mask
# These points should be within the point to point distance threshold specified earlier
mask = mask.astype(bool).squeeze()
predicted_points = cv.perspectiveTransform(source_points[:, None, :], homography).squeeze(1)
point_to_point_distances = np.linalg.norm(predicted_points[mask] - target_points[mask], axis=-1)

# The maximum error is around 410 pixels, which is way bigger than the specified threshold of 5 pixels
assert point_to_point_distances.max() <= point_to_point_distance_threshold, point_to_point_distances.max()

Issue submission checklist

[X] I report the issue, it's not a question
[X] I checked the problem with documentation, FAQ, open issues, forum.opencv.org, Stack Overflow, etc and have not found any solution
[X] I updated to the latest OpenCV version and the issue is still there
[X] There is reproducer code and related data files (videos, images, onnx, etc)

asmorkalov commented 1 month ago

Reproduced the issue with current OpenCV 4.x (f2d6527a4b429c79a05d6e78dbd6ac6f0cb004f7). As workaround I could recommend USAC algorithm. See cv.USAC_DEFAULT option as example. It converges well for your case.

cdeln commented 1 month ago

Thanks @asmorkalov for your suggested workaround.

Please note that USAC is not documented as a supported method for findHomography.

Just to clarify, this is not a convergence issue, but a logical bug in findHomography. It returns an inlier mask with elements set to True for outlier correspondences. Converging or not, this is not the expected behavior of that interface.

This is just repro code, in the prod code that the issue was found in I already check the mask for convergence (mask contains at least 4 inliers) and handle the non-converging case (less than 4 inliers). In this repo code the mask has 29/65 elements set to True, that is, it has logically converged to a solution, which is not correct as shown by the post-hoc check (that I added as a workaround in my prod code as well, in addition to checking the mask).

cdeln commented 2 weeks ago

Inspecting logs from my prod jobs it turns out that this happens way more often than I expected! The bug has gone under the radar for a long time because I do video processing and I handle bad estimation gracefully by interpolating between frames. Here are another two example set of source and target points that reproduce the bug (I can give you as many as you want, if you want to do some fuzz-testing).

However, the post-hoc error check gives an error just above the specified threshold (actual error is around 7 pixels, specified max error is 5 pixels). This makes me wonder if there are any guarantees on the reprojection error, or if that parameter is just used for some internal computations in findHomography? If this is not the case, please document that so that developers can perform the post-hoc check and handle bad estimations gracefully, or better to add a post-hoc check internally in findHomography.

source_points.json target_points.json

PS: Could there be issues with floating point arithmetic? Seeing these edge cases I just realized that it might be part of the drama.

opencv / opencv