Skip to content

🐍 Geometric Computer Vision Library for Spatial AI

165 KB
Raw Blame
# LICENSE HEADER MANAGED BY add-license-header
#
# Copyright 2018 Kornia Team
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#


import math
import os
import subprocess
import sys
from concurrent.futures import ThreadPoolExecutor

import pytest
import torch

import kornia
import kornia.geometry.ransac as ransac_module
from kornia.core._compat import torch_version_lt
from kornia.geometry import RANSAC, transform_points
from kornia.geometry._degensac import _h_degenerate_sample
from kornia.geometry.conversions import axis_angle_to_rotation_matrix, convert_points_from_homogeneous
from kornia.geometry.epipolar import find_fundamental, project_to_essential, sampson_epipolar_distance
from kornia.geometry.epipolar._metrics import _sampson_errors, _sampson_quadratic_basis
from kornia.geometry.epipolar.fundamental import _rank2_projection, _refine_fundamental_lm
from kornia.geometry.homography import _refine_homography_lm, _transfer_errors, oneway_transfer_error
from kornia.geometry.ransac import _normalize_correspondences

from testing.base import BaseTester, dynamo_is_available
from testing.casts import dict_to
from testing.default_device import default_device
from testing.geometry.create import create_dominant_plane_scene


class TestRANSACHomography(BaseTester):
    def test_smoke(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(4, 2, device=device, dtype=dtype)
        points2 = torch.rand(4, 2, device=device, dtype=dtype)
        ransac = RANSAC("homography").to(device=device, dtype=dtype)
        torch.random.manual_seed(0)
        H, _ = ransac(points1, points2)
        assert H.shape == (3, 3)

    @pytest.mark.parametrize("model_found", [False, True])
    def test_forward_output_shapes_are_stable(self, device, dtype, model_found):
        generator = torch.Generator().manual_seed(123)
        # A 10 px extent keeps bfloat16 rounding of the transformed points below inl_th; at 100 px it drops inliers.
        points1 = 10.0 * torch.rand(16, 2, generator=generator).to(device=device, dtype=dtype)
        unrelated_points = 10.0 * torch.rand(16, 2, generator=generator).to(device=device, dtype=dtype)
        homography = torch.tensor([[1.0, 0.1, 2.0], [0.05, 1.0, -1.0], [0.001, 0.002, 1.0]], device=device, dtype=dtype)
        points2 = transform_points(homography[None], points1[None])[0] if model_found else unrelated_points
        ransac = RANSAC("homography", inl_th=0.5, batch_size=4, max_iter=1, max_lo_iters=0, seed=0)

        model, inliers = ransac(points1, points2)

        assert model.shape == (3, 3)
        assert inliers.shape == (16,)
        assert inliers.dtype == torch.bool
        assert inliers.device == points1.device
        selected_points = points1[inliers]
        assert selected_points.shape == ((16 if model_found else 0), 2)

    @pytest.mark.xfail(reason="might slightly and randomly imprecise due to RANSAC randomness")
    def test_dirty_points(self, device, dtype):
        # generate input data
        torch.random.manual_seed(0)

        H = torch.eye(3, dtype=dtype, device=device)
        H[:2] = H[:2] + 0.1 * torch.rand_like(H[:2])
        H[2:, :2] = H[2:, :2] + 0.001 * torch.rand_like(H[2:, :2])

        points_src = 100.0 * torch.rand(1, 20, 2, device=device, dtype=dtype)
        points_dst = transform_points(H[None], points_src)

        # making last point an outlier
        points_dst[:, -1, :] += 800
        ransac = RANSAC("homography", inl_th=0.5, max_iter=20).to(device=device, dtype=dtype)
        # compute transform from source to target
        dst_homo_src, _ = ransac(points_src[0], points_dst[0])

        self.assert_close(
            transform_points(dst_homo_src[None], points_src[:, :-1]), points_dst[:, :-1], rtol=1e-3, atol=1e-3
        )

    @pytest.mark.slow
    @pytest.mark.parametrize("data", ["loftr_homo"], indirect=True)
    def test_real_clean(self, device, dtype, data):
        # generate input data
        torch.random.manual_seed(0)
        data_dev = dict_to(data, device, dtype)
        homography_gt = torch.inverse(data_dev["H_gt"])
        homography_gt = homography_gt / homography_gt[2, 2]
        pts_src = data_dev["pts0"]
        pts_dst = data_dev["pts1"]
        ransac = RANSAC("homography", inl_th=0.5, max_iter=20).to(device=device, dtype=dtype)
        # compute transform from source to target
        dst_homo_src, _ = ransac(pts_src, pts_dst)

        self.assert_close(transform_points(dst_homo_src[None], pts_src[None]), pts_dst[None], rtol=1e-2, atol=1.0)

    @pytest.mark.slow
    @pytest.mark.xfail(reason="might slightly and randomly imprecise due to RANSAC randomness")
    @pytest.mark.parametrize("data", ["loftr_homo"], indirect=True)
    def test_real_dirty(self, device, dtype, data):
        # generate input data
        torch.random.manual_seed(0)
        data_dev = dict_to(data, device, dtype)
        homography_gt = torch.inverse(data_dev["H_gt"])
        homography_gt = homography_gt / homography_gt[2, 2]
        pts_src = data_dev["pts0"]
        pts_dst = data_dev["pts1"]

        kp1 = data_dev["loftr_outdoor_tentatives0"]
        kp2 = data_dev["loftr_outdoor_tentatives1"]

        ransac = RANSAC("homography", inl_th=3.0, max_iter=30, max_lo_iters=10).to(device=device, dtype=dtype)
        # compute transform from source to target
        dst_homo_src, _ = ransac(kp1, kp2)

        # Reprojection error of 5px is OK
        self.assert_close(transform_points(dst_homo_src[None], pts_src[None]), pts_dst[None], rtol=0.15, atol=5)

    @pytest.mark.skip(reason="find_homography_dlt is using try/except block")
    def test_jit(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(4, 2, device=device, dtype=dtype)
        points2 = torch.rand(4, 2, device=device, dtype=dtype)
        model = RANSAC("homography").to(device=device, dtype=dtype)
        model_jit = torch.jit.script(RANSAC("homography").to(device=device, dtype=dtype))
        self.assert_close(model(points1, points2)[0], model_jit(points1, points2)[0], rtol=1e-4, atol=1e-4)


class TestRANSACHomographyLineSegments(BaseTester):
    def test_smoke(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(4, 2, 2, device=device, dtype=dtype)
        points2 = torch.rand(4, 2, 2, device=device, dtype=dtype)
        ransac = RANSAC("homography_from_linesegments").to(device=device, dtype=dtype)
        torch.random.manual_seed(0)
        H, _ = ransac(points1, points2)
        assert H.shape == (3, 3)

    @pytest.mark.xfail(reason="might slightly and randomly imprecise due to RANSAC randomness")
    def test_dirty_points(self, device, dtype):
        # generate input data
        torch.random.manual_seed(0)

        H = torch.eye(3, dtype=dtype, device=device)
        H[:2] = H[:2] + 0.1 * torch.rand_like(H[:2])
        H[2:, :2] = H[2:, :2] + 0.001 * torch.rand_like(H[2:, :2])

        points_src_st = 100.0 * torch.rand(1, 20, 2, device=device, dtype=dtype)
        points_src_end = 100.0 * torch.rand(1, 20, 2, device=device, dtype=dtype)

        points_dst_st = transform_points(H[None], points_src_st)
        points_dst_end = transform_points(H[None], points_src_end)

        # making last point an outlier
        points_dst_st[:, -1, :] += 800
        ls1 = torch.stack([points_src_st, points_src_end], dim=2)
        ls2 = torch.stack([points_dst_st, points_dst_end], dim=2)

        ransac = RANSAC("homography_from_linesegments", inl_th=0.5, max_iter=20).to(device=device, dtype=dtype)
        # compute transform from source to target
        dst_homo_src, _ = ransac(ls1[0], ls2[0])

        self.assert_close(
            transform_points(dst_homo_src[None], points_src_st[:, :-1]), points_dst_st[:, :-1], rtol=1e-3, atol=1e-3
        )

    @pytest.mark.skip(reason="find_homography_dlt is using try/except block")
    def test_jit(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(4, 2, 2, device=device, dtype=dtype)
        points2 = torch.rand(4, 2, 2, device=device, dtype=dtype)
        model = RANSAC("homography_from_linesegments").to(device=device, dtype=dtype)
        model_jit = torch.jit.script(RANSAC("homography_from_linesegments").to(device=device, dtype=dtype))
        self.assert_close(model(points1, points2)[0], model_jit(points1, points2)[0], rtol=1e-4, atol=1e-4)


class TestRANSACFundamental(BaseTester):
    def test_smoke(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(8, 2, device=device, dtype=dtype)
        points2 = torch.rand(8, 2, device=device, dtype=dtype)
        ransac = RANSAC("fundamental").to(device=device, dtype=dtype)
        Fm, _ = ransac(points1, points2)
        assert Fm.shape == (3, 3)

    @pytest.mark.slow
    @pytest.mark.parametrize("data", ["loftr_fund"], indirect=True)
    def test_real_clean_8pt(self, device, dtype, data):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("find_fundamental calls torch.linalg.eigh, which has no float16/bfloat16 kernel")
        torch.random.manual_seed(0)
        # generate input data
        data_dev = dict_to(data, device, dtype)
        pts_src = data_dev["pts0"]
        pts_dst = data_dev["pts1"]
        # The ground-truth F leaves up to 0.58px on these 10 points. At 0.5px the best eight-point fit has
        # only its own sample as inliers, which is no consensus, so RANSAC returns the zero failure matrix;
        # at 1px all ten are inliers, and over 100 seeds the refit's largest error is at most 1px.
        ransac = RANSAC("fundamental_8pt", inl_th=1.0, max_iter=20, max_lo_iters=10).to(device=device, dtype=dtype)
        fundamental_matrix, mask = ransac(pts_src, pts_dst)
        # A zero matrix is the failure result and has zero Sampson error for every point.
        assert fundamental_matrix.abs().amax() > 0
        assert mask.all()
        gross_errors = (
            sampson_epipolar_distance(pts_src[None], pts_dst[None], fundamental_matrix[None], squared=False) > 2.0
        )
        assert gross_errors.sum().item() == 0

    @pytest.mark.slow
    @pytest.mark.parametrize("data", ["loftr_fund"], indirect=True)
    def test_real_clean_7pt(self, device, dtype, data):
        torch.random.manual_seed(0)
        # generate input data
        data_dev = dict_to(data, device, dtype)
        pts_src = data_dev["pts0"]
        pts_dst = data_dev["pts1"]
        # compute transform from source to target
        ransac = RANSAC("fundamental_7pt", inl_th=1.0, max_iter=100, max_lo_iters=10).to(device=device, dtype=dtype)
        fundamental_matrix, _ = ransac(pts_src, pts_dst)
        assert fundamental_matrix.abs().amax() > 0
        gross_errors = (
            sampson_epipolar_distance(pts_src[None], pts_dst[None], fundamental_matrix[None], squared=False) > 1.0
        )
        assert gross_errors.sum().item() == 0

    @pytest.mark.slow
    @pytest.mark.xfail(reason="might slightly and randomly imprecise due to RANSAC randomness")
    @pytest.mark.parametrize("data", ["loftr_fund"], indirect=True)
    def test_real_dirty_8pt(self, device, dtype, data):
        torch.random.manual_seed(0)
        # generate input data
        data_dev = dict_to(data, device, dtype)
        pts_src = data_dev["pts0"]
        pts_dst = data_dev["pts1"]

        kp1 = data_dev["loftr_indoor_tentatives0"]
        kp2 = data_dev["loftr_indoor_tentatives1"]

        ransac = RANSAC("fundamental_8pt", inl_th=1.0, max_iter=20, max_lo_iters=10).to(device=device, dtype=dtype)
        # compute transform from source to target
        fundamental_matrix, _ = ransac(kp1, kp2)
        assert fundamental_matrix.abs().amax() > 0
        gross_errors = (
            sampson_epipolar_distance(pts_src[None], pts_dst[None], fundamental_matrix[None], squared=False) > 10.0
        )
        assert gross_errors.sum().item() < 2

    @pytest.mark.slow
    @pytest.mark.parametrize("data", ["loftr_fund"], indirect=True)
    def test_real_dirty_7pt(self, device, dtype, data):
        torch.random.manual_seed(0)
        # generate input data
        data_dev = dict_to(data, device, dtype)
        pts_src = data_dev["pts0"]
        pts_dst = data_dev["pts1"]

        kp1 = data_dev["loftr_indoor_tentatives0"]
        kp2 = data_dev["loftr_indoor_tentatives1"]

        ransac = RANSAC("fundamental_7pt", inl_th=1.0, max_iter=20, max_lo_iters=10).to(device=device, dtype=dtype)
        # compute transform from source to target
        fundamental_matrix, _ = ransac(kp1, kp2)
        assert fundamental_matrix.abs().amax() > 0
        gross_errors = (
            sampson_epipolar_distance(pts_src[None], pts_dst[None], fundamental_matrix[None], squared=False) > 10.0
        )
        assert gross_errors.sum().item() < 2

    @pytest.mark.skip(reason="try except block in python version")
    def test_jit(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(8, 2, device=device, dtype=dtype)
        points2 = torch.rand(8, 2, device=device, dtype=dtype)
        model = RANSAC("fundamental").to(device=device, dtype=dtype)
        model_jit = torch.jit.script(model)
        self.assert_close(model(points1, points2)[0], model_jit(points1, points2)[0], rtol=1e-3, atol=1e-3)

    @pytest.mark.skip(reason="RANSAC is random algorithm, so Jacobian is not defined")
    def test_gradcheck(self, device):
        torch.random.manual_seed(0)
        points1 = torch.rand(8, 2, device=device, dtype=torch.float64, requires_grad=True)
        points2 = torch.rand(8, 2, device=device, dtype=torch.float64)
        model = RANSAC("fundamental").to(device=device, dtype=torch.float64)

        def gradfun(p1, p2):
            return model(p1, p2)[0]

        self.gradcheck(gradfun, (points1, points2), fast_mode=False, requires_grad=(True, False, False))


class TestRANSACLocalOptimization(BaseTester):
    @pytest.mark.parametrize("good_idx", [1, 2])
    def test_polish_step_uses_verify_best_model(self, device, dtype, good_idx):
        """Regression test for RANSAC.forward()'s local-optimization loop.

        It must adopt the model verify() actually selects as best-scoring, not blindly take a fixed index of whatever
        the polisher solver returns. This is only observable when a polisher returns more than one candidate, so the
        polisher is patched to return three: two deliberately bad matrices and the least-squares fit of the data, placed
        at ``good_idx`` so that neither the first nor the last position alone satisfies the test. The minimal solver is
        patched to a plausible but worse fit, so the local-optimization branch adopts a candidate by construction
        rather than depending on how the random minimal samples fall.
        """
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("find_fundamental needs linalg_eigh, which has no float16/bfloat16 kernel")
        torch.random.manual_seed(0)
        points1 = torch.rand(60, 2, device=device, dtype=dtype) * 100.0
        H = torch.tensor([[1.0, 0.05, 3.0], [-0.03, 1.0, -2.0], [1e-4, 1e-4, 1.0]], device=device, dtype=dtype)
        ph = torch.cat([points1, torch.ones(60, 1, device=device, dtype=dtype)], 1) @ H.T
        points2 = ph[:, :2] / ph[:, 2:] + 0.3 * torch.randn(60, 2, device=device, dtype=dtype)

        good_fit = find_fundamental(points1[None], points2[None])
        # A plausible but worse starting model: the least-squares fit to a much noisier copy of the data.
        worse_fit = find_fundamental(points1[None], points2[None] + torch.randn_like(points2[None]))
        bad_fits = [
            torch.eye(3, device=device, dtype=dtype)[None],
            torch.tensor([[0.0, 0.0, 0.0], [0.0, 0.0, -1.0], [0.0, 1.0, 0.0]], device=device, dtype=dtype)[None],
        ]
        candidates = torch.cat([*bad_fits[:good_idx], good_fit, *bad_fits[good_idx:]], dim=0)
        calls = []

        def fake_polisher(kp1, kp2, weights):
            calls.append(1)
            return candidates

        ransac = RANSAC(
            "fundamental_8pt",
            inl_th=1.0,
            batch_size=4,
            max_iter=1,
            max_lo_iters=1,
            score_type="msac",
            local_optimization="dlt",
        )
        ransac.minimal_solver = lambda kp1, kp2, w: worse_fit.expand(kp1.shape[0], 3, 3).clone()
        ransac.polisher_solver = fake_polisher

        Fm, _ = ransac(points1, points2)
        assert len(calls) > 0, "the local-optimization step never ran"
        self.assert_close(Fm, good_fit[0])

    def test_line_segment_polish_improves_the_fit(self, device, dtype):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("line_segment_transfer_error_one_way overflows half precision on 600 px coordinates")
        # Segments about 100 px long, half of them outliers. The polisher's Gaussian weights are on the perpendicular
        # distance in pixels, not on that distance times the segment length (#4867), so local optimization refines
        # the minimal-sample model instead of fitting a handful of segments.
        torch.manual_seed(0)
        H = torch.tensor([[1.1, 0.05, 20.0], [0.02, 0.95, -10.0], [1e-4, 2e-4, 1.0]], device=device, dtype=dtype)
        centers = torch.rand(300, 2, device=device, dtype=dtype) * 600
        half = torch.randn(300, 2, device=device, dtype=dtype)
        half = 50 * half / half.norm(dim=-1, keepdim=True)
        ls1 = torch.stack([centers - half, centers + half], 1)
        ls2_clean = transform_points(H[None], ls1.reshape(1, -1, 2)).reshape(300, 2, 2)
        ls2 = ls2_clean + 0.3 * torch.randn_like(ls2_clean)
        ls2[150:] = torch.rand(150, 2, 2, device=device, dtype=dtype) * 600

        def endpoint_error(model):
            mapped = transform_points(model[None], ls1[:150].reshape(1, -1, 2)).reshape(150, 2, 2)
            return float((mapped - ls2_clean[:150]).norm(dim=-1).mean())

        errors = {}
        for max_lo_iters in (0, 5):
            ransac = RANSAC(
                "homography_from_linesegments",
                inl_th=2.0,
                batch_size=1024,
                max_iter=4,
                max_lo_iters=max_lo_iters,
                seed=0,
                confidence=1.0,
            )
            errors[max_lo_iters] = endpoint_error(ransac(ls1, ls2)[0])
        assert errors[5] < errors[0]
        assert errors[5] < 1.0


class TestRansacMethods:
    def test_max_samples_by_conf(self):
        """Test max_samples_by_conf with realistic scenarios."""
        conf = 0.99

        # Test 1: Very few inliers (1 out of 1000) with sample_size=7
        # An all-inlier minimal sample is impossible.
        x = RANSAC.max_samples_by_conf(n_inl=1, num_tc=1000, sample_size=7, conf=conf)
        assert x == sys.maxsize

        # Test 2: Low inlier ratio (10 out of 1000, 1%) with sample_size=7
        # Should require many iterations
        x = RANSAC.max_samples_by_conf(n_inl=10, num_tc=1000, sample_size=7, conf=conf)
        assert x > 0
        # With 1% inliers, probability of all 7 samples being inliers is very low
        # So we need a huge number of samples
        assert x > 1_000_000  # Should be a very large number

        # Test 3: Medium inlier ratio (500 out of 1000, 50%) with sample_size=4
        # Should require moderate number of iterations
        x = RANSAC.max_samples_by_conf(n_inl=500, num_tc=1000, sample_size=4, conf=conf)
        assert x > 0
        # With 50% inliers, probability of all 4 samples being inliers is ~0.0625
        # So we need log(1-0.99)/log(1-0.0625) β‰ˆ 70 samples
        assert 50 < x < 100

        # Test 4: High inlier ratio (900 out of 1000, 90%) with sample_size=4
        # Should require very few iterations
        x = RANSAC.max_samples_by_conf(n_inl=900, num_tc=1000, sample_size=4, conf=conf)
        assert x > 0
        # With 90% inliers, probability of all 4 samples being inliers is ~0.66
        # So we need log(1-0.99)/log(1-0.66) β‰ˆ 4 samples
        assert x < 10

        # Test 5: Edge case - all points are inliers
        x = RANSAC.max_samples_by_conf(n_inl=100, num_tc=100, sample_size=4, conf=conf)
        assert x == 1  # Only need 1 sample if all are inliers

        # Test 6: Edge case - not enough points for sample
        x = RANSAC.max_samples_by_conf(n_inl=10, num_tc=10, sample_size=15, conf=conf)
        assert x == sys.maxsize

        # Test 7: Edge case - too few inliers (n_inl <= sample_size)
        x = RANSAC.max_samples_by_conf(n_inl=2, num_tc=1000, sample_size=4, conf=conf)
        assert x == sys.maxsize

        # Test 8: Edge case - confidence at boundaries
        x = RANSAC.max_samples_by_conf(n_inl=50, num_tc=100, sample_size=4, conf=1.0)
        assert x == sys.maxsize

        x = RANSAC.max_samples_by_conf(n_inl=50, num_tc=100, sample_size=4, conf=0.0)
        assert x == 1  # Returns 1 when conf <= 0.0

        # Test 9: Verify monotonicity - more inliers should require fewer samples
        x1 = RANSAC.max_samples_by_conf(n_inl=200, num_tc=1000, sample_size=4, conf=conf)
        x2 = RANSAC.max_samples_by_conf(n_inl=500, num_tc=1000, sample_size=4, conf=conf)
        x3 = RANSAC.max_samples_by_conf(n_inl=800, num_tc=1000, sample_size=4, conf=conf)
        assert x1 > x2 > x3  # More inliers = fewer samples needed


class TestRANSACSeed:
    def test_same_seed_reproducible(self, device, dtype):
        """Same seed should produce identical results across two calls."""
        torch.manual_seed(42)
        points1 = torch.rand(20, 2, device=device, dtype=dtype)
        points2 = torch.rand(20, 2, device=device, dtype=dtype)

        ransac = RANSAC("homography", inl_th=2.0, max_iter=5, seed=123).to(device=device, dtype=dtype)
        H1, inliers1 = ransac(points1, points2)
        H2, inliers2 = ransac(points1, points2)

        assert torch.allclose(H1, H2)
        assert torch.equal(inliers1, inliers2)

    def test_different_seeds_differ(self, device, dtype):
        """Different seeds should (very likely) produce different results."""
        torch.manual_seed(42)
        points1 = torch.rand(20, 2, device=device, dtype=dtype)
        points2 = torch.rand(20, 2, device=device, dtype=dtype)

        # Every point is an inlier at this threshold, so local optimization would return the same
        # least-squares fit for any seed; compare the seed-dependent minimal-sample models instead.
        # Under RANSAC scoring every all-inlier sample ties and the first one drawn wins, so the
        # result follows the seed; the MSAC optimum over an exhaustive draw is the same for any seed.
        common = {"inl_th": 2.0, "max_iter": 5, "max_lo_iters": 0, "score_type": "ransac"}
        ransac_a = RANSAC("homography", seed=1, **common).to(device=device, dtype=dtype)
        ransac_b = RANSAC("homography", seed=2, **common).to(device=device, dtype=dtype)

        H_a, _ = ransac_a(points1, points2)
        H_b, _ = ransac_b(points1, points2)

        assert not torch.allclose(H_a, H_b)

    def test_no_seed_differs_from_seeded(self, device, dtype):
        """Without a seed, repeated calls should not be forced to be identical to a seeded call."""
        torch.manual_seed(0)
        points1 = torch.rand(20, 2, device=device, dtype=dtype)
        points2 = torch.rand(20, 2, device=device, dtype=dtype)

        ransac_seeded = RANSAC("homography", inl_th=2.0, max_iter=5, seed=42).to(device=device, dtype=dtype)
        H_s1, _ = ransac_seeded(points1, points2)
        H_s2, _ = ransac_seeded(points1, points2)
        # Seeded should be reproducible
        assert torch.allclose(H_s1, H_s2)

    def test_seed_stored_as_attribute(self, device, dtype):
        ransac = RANSAC("homography", seed=7)
        assert ransac.seed == 7

    def test_none_seed_stored(self, device, dtype):
        ransac = RANSAC("homography")
        assert ransac.seed is None

    def test_local_optimization_has_its_own_seed_stream(self, device, dtype, monkeypatch):
        # More batches than max_iter: the subset-refit generator must not reuse a sampling generator's seed.
        seeds = []

        class Spy(torch.Generator):
            def manual_seed(self, seed):
                seeds.append(seed)
                return super().manual_seed(seed)

        monkeypatch.setattr(kornia.geometry.ransac.torch, "Generator", Spy)
        torch.manual_seed(0)
        kp1 = torch.rand(200, 2, device=device, dtype=dtype) * 100
        ransac = RANSAC(
            "homography",
            inl_th=1.0,
            batch_size=16,
            max_iter=1,
            max_samples=64,
            seed=0,
            lo_sample_size=8,
            confidence=1.0,
            local_optimization="dlt",
        )
        ransac(kp1, kp1.clone())
        assert len(seeds) > 4  # four sampling batches and at least one local optimization
        assert len(seeds) == len(set(seeds))


class TestRANSACEssential(BaseTester):
    def test_smoke(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(8, 2, device=device, dtype=dtype)
        points2 = torch.rand(8, 2, device=device, dtype=dtype)
        ransac = RANSAC("essential").to(device=device, dtype=dtype)
        E, _ = ransac(points1, points2)
        assert E.shape == (3, 3)

    def test_polish_enforces_essential_constraint(self, device, dtype):
        """Regression test for https://github.com/kornia/kornia/issues/3874.

        The polishing (local-optimization) step must return an essential matrix, i.e. its two
        non-zero singular values must be (approximately) equal and the third must be
        (approximately) zero. The buggy version fit a fundamental matrix and returned it as-is,
        violating the constraint and silently breaking decompose_essential_matrix.
        """
        torch.random.manual_seed(0)
        ransac = RANSAC("essential").to(device=device, dtype=dtype)
        kp1 = torch.rand(20, 2, device=device, dtype=dtype)
        kp2 = torch.rand(20, 2, device=device, dtype=dtype)
        inliers = torch.ones(20, dtype=torch.bool, device=device)
        E = ransac.polish_model(kp1, kp2, inliers)  # (1, 3, 3)
        sv = torch.linalg.svdvals(E[0])
        # two non-zero singular values must be equal (essential-matrix constraint)
        assert (sv[0] / sv[1] - 1.0).abs() < 1e-2
        # third singular value must be ~0 (relative to the largest singular value)
        assert (sv[2] / sv[0]).abs() < 1e-4

    def test_forward_enforces_essential_constraint(self, device, dtype):
        """Regression test for https://github.com/kornia/kornia/issues/3874 (forward path).

        forward() must return an essential matrix even when local optimization does not win and
        the best model is the minimal-solver estimate (find_essential), which is not guaranteed
        to be on the essential manifold. The returned model is projected onto the manifold
        before being returned, so the constraint holds for the model forward() selects.

        ``batch_size``/``max_iter`` are trimmed for speed, but ``max_lo_iters`` keeps its default
        so the local-optimization loop still runs: on this input it is entered once per draw and
        never beats the minimal-solver model, exactly as with the default sampler settings.
        """
        torch.random.manual_seed(0)
        ransac = RANSAC("essential", batch_size=32, max_iter=1, local_optimization="dlt").to(device=device, dtype=dtype)
        for _ in range(5):
            kp1 = torch.rand(20, 2, device=device, dtype=dtype)
            kp2 = torch.rand(20, 2, device=device, dtype=dtype)
            E, _ = ransac(kp1, kp2)
            sv = torch.linalg.svdvals(E)
            assert (sv[0] / sv[1] - 1.0).abs() < 1e-2
            assert (sv[2] / sv[0]).abs() < 1e-4

    def test_project_to_essential(self, device, dtype):
        """project_to_essential must enforce the essential-matrix constraint."""
        torch.random.manual_seed(0)
        M = torch.rand(4, 3, 3, device=device, dtype=dtype)
        E = project_to_essential(M)
        svd_input = E.float() if E.dtype in (torch.float16, torch.bfloat16) else E
        sv = torch.linalg.svdvals(svd_input)
        assert torch.all((sv[..., 0] / sv[..., 1] - 1.0).abs() < 1e-2)
        zero_tolerance = max(1e-4, torch.finfo(E.dtype).eps)
        assert torch.all((sv[..., 2] / sv[..., 0]).abs() < zero_tolerance)

    @pytest.mark.skip(reason="try except block in python version")
    def test_jit(self, device, dtype):
        torch.random.manual_seed(0)
        points1 = torch.rand(8, 2, device=device, dtype=dtype)
        points2 = torch.rand(8, 2, device=device, dtype=dtype)
        model = RANSAC("essential").to(device=device, dtype=dtype)
        model_jit = torch.jit.script(model)
        self.assert_close(model(points1, points2)[0], model_jit(points1, points2)[0], rtol=1e-3, atol=1e-3)

    @pytest.mark.skip(reason="RANSAC is random algorithm, so Jacobian is not defined")
    def test_gradcheck(self, device):
        torch.random.manual_seed(0)
        points1 = torch.rand(8, 2, device=device, dtype=torch.float64, requires_grad=True)
        points2 = torch.rand(8, 2, device=device, dtype=torch.float64)
        model = RANSAC("essential").to(device=device, dtype=torch.float64)

        def gradfun(p1, p2):
            return model(p1, p2)[0]

        self.gradcheck(gradfun, (points1, points2), fast_mode=False, requires_grad=(True, False, False))


# Sixteen exact planar matches for the convention pins. _MATCHES_1 is an asymmetric 4 x 4 lattice with a per-point
# diagonal jitter, generated by
#   torch.stack(torch.meshgrid(torch.tensor([160., 230., 330., 440.]), torch.tensor([95., 150., 240., 320.]),
#   indexing="xy"), -1).reshape(16, 2) + torch.linspace(0, 3, 16)[:, None]
# and _H_TRUE is a fixed homography (a mild projective warp) whose entries are all distinct and non-zero, so swapping
# the images changes the model.
_MATCHES_1 = [
    [160.0, 95.0], [230.2, 95.2], [330.4, 95.4], [440.6, 95.6], [160.8, 150.8], [231.0, 151.0], [331.2, 151.2],
    [441.4, 151.4], [161.6, 241.6], [231.8, 241.8], [332.0, 242.0], [442.2, 242.2], [162.4, 322.4], [232.6, 322.6],
    [332.8, 322.8], [443.0, 323.0],
]  # fmt: skip
_H_TRUE = [
    [1.034685, -0.04160598, -63.61482],
    [0.1039753, 1.135451, -62.87412],
    [2.851519e-04, 1.404178e-04, 1.0],
]
# Sixteen fixed points per image that no homography relates to each other or to the matches above.
_UNRELATED_1 = [
    [75.0, 410.0], [390.0, 30.0], [505.0, 260.0], [120.0, 205.0], [285.0, 380.0], [455.0, 60.0], [30.0, 140.0],
    [350.0, 290.0], [205.0, 25.0], [480.0, 395.0], [95.0, 330.0], [260.0, 175.0], [410.0, 225.0], [180.0, 450.0],
    [55.0, 70.0], [300.0, 120.0],
]  # fmt: skip
_UNRELATED_2 = [
    [310.0, 95.0], [60.0, 280.0], [150.0, 30.0], [420.0, 330.0], [25.0, 190.0], [240.0, 400.0], [380.0, 170.0],
    [100.0, 60.0], [470.0, 240.0], [200.0, 130.0], [330.0, 20.0], [45.0, 420.0], [270.0, 300.0], [495.0, 110.0],
    [140.0, 260.0], [215.0, 355.0],
]  # fmt: skip
# A non-planar two-view scene for the fundamental-matrix pin: K1 != K2, fx != fy, cx != cy, a rotation about a
# non-axis direction and a translation off every axis. Twelve points at depth 4 to 6 in camera 1, no two sharing a
# coordinate; the matches are their pixel projections through P1 = K1 [I | 0] and P2 = K2 [R | t].
_SCENE_K1 = [[800.0, 0.0, 320.0], [0.0, 760.0, 200.0], [0.0, 0.0, 1.0]]
_SCENE_K2 = [[700.0, 0.0, 300.0], [0.0, 740.0, 240.0], [0.0, 0.0, 1.0]]
_SCENE_AXIS_ANGLE = [0.1, -0.2, 0.05]
_SCENE_T = [0.5, 0.1, 0.02]
_SCENE_X = [
    [-0.0075, 0.5364, 4.4163], [-0.7359, -0.3852, 5.8596], [-0.0198, 0.7929, 5.4462], [0.2646, -0.3022, 5.4847],
    [-0.9553, -0.6623, 5.0526], [0.0370, 0.3953, 4.4873], [-0.6779, -0.4355, 5.1692], [0.8304, -0.2058, 4.0663],
    [-0.1612, 0.1058, 4.2774], [-0.9277, -0.6295, 4.4845], [-0.3898, 0.8640, 5.6309], [-0.4603, -0.6986, 5.5863],
]  # fmt: skip
_HALF_LINES = (
    "line_segment_transfer_error_one_way builds the unnormalised image-2 line in the input dtype; its constant term "
    "is of order (pixel coordinate)**2, which overflows float16 and which bfloat16 cannot resolve"
)


def _cpu_only(device: torch.device) -> None:
    if device.type != "cpu":
        pytest.skip("the RANSAC convention pins are verified on the CPU only")


def _planar_matches(device, dtype):
    """Sixteen exact matches ``kp2 = H(kp1)``, generated in float64 on the CPU and cast, shape ``(16, 2)`` each."""
    kp1 = torch.tensor([_MATCHES_1], dtype=torch.float64)
    kp2 = transform_points(torch.tensor([_H_TRUE], dtype=torch.float64), kp1)
    return kp1[0].to(device, dtype), kp2[0].to(device, dtype)


def _scene_matches(device, dtype):
    """Pixel matches of the two-view scene, projected in float64 on the CPU and cast, shape ``(12, 2)`` each."""
    f64 = torch.float64
    R = axis_angle_to_rotation_matrix(torch.tensor([_SCENE_AXIS_ANGLE], dtype=f64))[0]
    X = torch.tensor(_SCENE_X, dtype=f64)
    kp1 = convert_points_from_homogeneous(X @ torch.tensor(_SCENE_K1, dtype=f64).T)
    kp2 = convert_points_from_homogeneous(
        (X @ R.T + torch.tensor(_SCENE_T, dtype=f64)) @ torch.tensor(_SCENE_K2, dtype=f64).T
    )
    return kp1.to(device, dtype), kp2.to(device, dtype)


def _planar_segments(device, dtype, stretch: float):
    """Eight segments made of consecutive lattice points and their exact images; segment 0 is ``stretch`` x longer."""
    ls1 = torch.tensor(_MATCHES_1, dtype=torch.float64).reshape(8, 2, 2)
    ls1[0, 1] = ls1[0, 0] + stretch * (ls1[0, 1] - ls1[0, 0])
    ls2 = transform_points(torch.tensor([_H_TRUE], dtype=torch.float64), ls1.reshape(1, 16, 2)).reshape(8, 2, 2)
    return ls1.to(device, dtype), ls2.to(device, dtype)


def _fixed_model(ransac: RANSAC, model: torch.Tensor) -> RANSAC:
    """Make every minimal sample return ``model``, so that forward's thresholding is observed on a known model."""
    ransac.minimal_solver = lambda kp1, kp2, weights: model.expand(kp1.shape[0], 3, 3).clone()
    return ransac


def _max_transfer(model: torch.Tensor, src: torch.Tensor, dst: torch.Tensor) -> torch.Tensor:
    return (transform_points(model[None], src[None]) - dst[None]).abs().max()


class TestConventionRANSAC(BaseTester):
    def test_convention_ransac_model_maps_kp1_to_kp2(self, device, dtype, monkeypatch):
        _cpu_only(device)
        kp1, kp2 = _planar_matches(device, dtype)
        # inl_th=5 keeps every exact match an inlier in bfloat16 too, whose pixel coordinates carry up to 2 px of
        # rounding here.
        model, mask = RANSAC("homography", inl_th=5.0, seed=0, max_iter=3, batch_size=64)(kp1, kp2)
        # A (3, 3) model and an (N,) bool mask; the model maps kp1 onto kp2, and the control (applying it to kp2)
        # misses kp1 by about 213 px.
        assert model.shape == (3, 3)
        assert mask.shape == (16,)
        assert mask.dtype == torch.bool
        assert bool(mask.all())
        assert _max_transfer(model, kp1, kp2) < 0.05 * _max_transfer(model, kp2, kp1)
        swapped, _ = RANSAC("homography", inl_th=5.0, seed=0, max_iter=3, batch_size=64)(kp2, kp1)
        assert _max_transfer(swapped, kp2, kp1) < 0.05 * _max_transfer(swapped, kp1, kp2)
        # No sample reaches consensus on unrelated points: an all-zero model and no inliers.
        unrelated_1 = torch.tensor(_UNRELATED_1[:12], device=device, dtype=dtype)
        unrelated_2 = torch.tensor(_UNRELATED_2[:12], device=device, dtype=dtype)
        model, mask = RANSAC("homography", inl_th=0.5, seed=0, max_iter=3, batch_size=64)(unrelated_1, unrelated_2)
        assert bool((model == 0).all())
        assert mask.shape == (12,)
        assert mask.dtype == torch.bool
        assert not bool(mask.any())
        # "homography" screens its minimal samples with sample_is_valid_for_homography: when every sample is
        # rejected, no model is estimated from the exact matches either.
        samples = []

        def reject_all(points1, points2):
            samples.append(tuple(points1.shape))
            return torch.zeros(points1.shape[0], dtype=torch.bool, device=points1.device)

        monkeypatch.setattr(kornia.geometry.ransac, "sample_is_valid_for_homography", reject_all)
        model, mask = RANSAC("homography", inl_th=5.0, seed=0, max_iter=3, batch_size=64)(kp1, kp2)
        # Every sample is rejected, so nothing stops early: max_iter=3 batches of batch_size=64 minimal samples,
        # the documented maximum.
        assert len(samples) == 3
        assert all(shape == (64, 4, 2) for shape in samples)
        assert bool((model == 0).all())
        assert not bool(mask.any())

    @pytest.mark.parametrize("model_type", ["homography", "fundamental"])
    def test_convention_ransac_inl_th_is_pixels_for_point_models(self, model_type, device, dtype):
        _cpu_only(device)
        if model_type == "homography":
            # inl_th is compared with the one-way transfer error in pixels (forward passes inl_th**2 to the squared
            # error): a match displaced by 10 px is an outlier at inl_th=4 and an inlier at inl_th=15. RANSAC may
            # absorb part of the displacement into a compromise model, so the flip lies at or below 10 px; both
            # thresholds stay clear of it, and in squared-pixel units both would reject the match.
            kp1, kp2 = _planar_matches(device, dtype)
            kp2_bad = kp2.clone()
            kp2_bad[9, 0] += 10.0  # an interior match, displaced along x
            for inl_th, expected in ((4.0, False), (15.0, True)):
                _, mask = RANSAC("homography", inl_th=inl_th, max_iter=20, seed=0)(kp1, kp2_bad)
                assert mask.dtype == torch.bool
                assert mask.shape == (16,)
                assert bool(mask[9]) is expected
                assert int(mask.sum()) == 15 + int(expected)
            # With the true H fixed, the moved match's one-way error is exactly 10 px (its symmetric error is
            # about 15 px): an inlier at inl_th=11 and an outlier at inl_th=9. The minimal samples still pass
            # sample_is_valid_for_homography, which rejects some lattice samples, so a seeded batch of 64 is drawn.
            H = torch.tensor([_H_TRUE], device=device, dtype=dtype)
            for inl_th, expected in ((9.0, False), (11.0, True)):
                ransac = RANSAC(
                    "homography",
                    inl_th=inl_th,
                    batch_size=64,
                    max_iter=1,
                    max_lo_iters=0,
                    seed=0,
                    local_optimization="dlt",
                )
                _, mask = _fixed_model(ransac, H)(kp1, kp2_bad)
                assert bool(mask[9]) is expected
                assert int(mask.sum()) == 15 + int(expected)
            return
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("find_fundamental calls torch.linalg.eigh, which has no float16/bfloat16 kernel")
        kp1, kp2 = _scene_matches(device, dtype)
        if dtype == torch.float64:
            # kp1 is the estimator's first image: the returned F explains every match in this order
            # (x2^T F x1 = 0), and its transpose, the other image order, explains none. float64 only: in float32
            # the fit on these exact matches already misses by a pixel or two.
            F_est, mask_est = RANSAC("fundamental", inl_th=1.0, seed=0, max_iter=3, batch_size=64)(kp1, kp2)
            assert bool(mask_est.all())
            assert sampson_epipolar_distance(kp1[None], kp2[None], F_est[None], squared=False).max() < 1e-2
            assert sampson_epipolar_distance(kp1[None], kp2[None], F_est.mT[None], squared=False).min() > 1.0
        # For the fundamental models inl_th is compared with the Sampson distance in pixels. The model is fixed to
        # the F of the twelve exact matches, so the threshold is observed without sampling.
        F = find_fundamental(kp1[None], kp2[None])
        kp2_bad = kp2.clone()
        kp2_bad[6] += torch.tensor([4.0, -3.0], device=device, dtype=dtype)
        distance = sampson_epipolar_distance(kp1[None], kp2_bad[None], F, squared=False)[0, 6]
        # About 2.6 px: an outlier at inl_th=2 and an inlier at inl_th=4. Compared in squared-pixel units, or with
        # the distance itself against inl_th**2, the two verdicts would not both hold.
        assert 2.0 < distance < 4.0
        for inl_th, expected in ((2.0, False), (4.0, True)):
            ransac = RANSAC(
                "fundamental",
                inl_th=inl_th,
                batch_size=1,
                max_iter=1,
                max_lo_iters=0,
                seed=0,
                local_optimization="dlt",
            )
            model, mask = _fixed_model(ransac, F)(kp1, kp2_bad)
            assert torch.equal(model, F[0])
            assert bool(mask[6]) is expected
            assert int(mask.sum()) == 11 + int(expected)

    def test_convention_ransac_seed_is_private(self, device, dtype):
        _cpu_only(device)
        kp1, kp2 = _planar_matches(device, dtype)
        kp2[9, 0] += 10.0

        def run(seed):
            return RANSAC("homography", inl_th=2.0, seed=seed, max_iter=3, batch_size=16)(kp1, kp2)

        # A seeded call draws from a private generator: it leaves the global RNG state unchanged, and a second
        # instance with the same seed reproduces it whatever the global generator holds.
        state = torch.get_rng_state()
        model_a, mask_a = run(11)
        assert torch.equal(torch.get_rng_state(), state)
        torch.manual_seed(123)
        model_b, mask_b = run(11)
        assert torch.equal(model_a, model_b)
        assert torch.equal(mask_a, mask_b)
        # seed=None draws from the global generator: it advances it, and reseeding it reproduces the result.
        torch.manual_seed(5)
        state = torch.get_rng_state()
        model_c, mask_c = run(None)
        assert not torch.equal(torch.get_rng_state(), state)
        torch.manual_seed(5)
        model_d, mask_d = run(None)
        assert torch.equal(model_c, model_d)
        assert torch.equal(mask_c, mask_d)

    def test_convention_ransac_linesegment_threshold_units_4867(self, device, dtype):
        _cpu_only(device)
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip(_HALF_LINES)
        H = torch.tensor([_H_TRUE], device=device, dtype=dtype)
        # One segment moved 3 px off its line in image 2, scored by the true H. The inlier test uses the mean
        # endpoint-to-line distance in pixels, whatever the segment's length: the 3-px offset is an inlier at
        # inl_th=4 and an outlier at inl_th=2 on a 66-px and on a 129-px segment alike. #4867 compared the distance
        # times the segment length with inl_th**2, which rejected both at inl_th=4.
        for stretch in (1.0, 2.0):
            ls1, ls2 = _planar_segments(device, dtype, stretch)
            d = ls2[0, 1] - ls2[0, 0]
            ls2[0] += 3.0 * torch.stack([-d[1], d[0]]) / d.norm()
            for inl_th, expected in ((4.0, True), (2.0, False)):
                ransac = RANSAC("homography_from_linesegments", inl_th=inl_th, batch_size=1, max_iter=1, max_lo_iters=0)
                _, mask = _fixed_model(ransac, H)(ls1, ls2)
                assert bool(mask[1:].all())
                assert bool(mask[0]) is expected

    def test_convention_ransac_msac_finds_model_with_outliers_4868(self, device, dtype):
        _cpu_only(device)
        kp1, kp2 = _planar_matches(device, dtype)
        kp1 = torch.cat([kp1, torch.tensor(_UNRELATED_1, device=device, dtype=dtype)])
        kp2 = torch.cat([kp2, torch.tensor(_UNRELATED_2, device=device, dtype=dtype)])
        # 16 exact matches and 16 outliers. score_type="ransac" finds the homography of the sixteen.
        model, mask = RANSAC("homography", inl_th=5.0, score_type="ransac", seed=0, max_iter=5, batch_size=256)(
            kp1, kp2
        )
        assert bool(mask[:16].all())
        assert not bool(mask[16:].any())
        # MSAC ranks candidates by their truncated residuals and accepts them by inlier count, so it finds the same
        # sixteen. #4868 compared the MSAC score N - sum(min(err, inl_th**2)) with the minimal sample size, a count,
        # and returned no model here.
        model, mask = RANSAC("homography", inl_th=5.0, score_type="msac", seed=0, max_iter=5, batch_size=256)(kp1, kp2)
        assert bool(model.abs().amax() > 0)
        assert bool(mask[:16].all())
        assert not bool(mask[16:].any())

    def test_convention_ransac_prosac_sampling_4869(self, device, dtype):
        _cpu_only(device)
        # PROSAC draws its first sample from the four top-ranked correspondences and then grows the prefix it samples
        # from, one newest correspondence per sample, so its first samples differ from uniform ones. #4869 stored
        # prosac_sampling and never read it.
        prosac = RANSAC("homography", inl_th=2.0, seed=3, prosac_sampling=True, max_iter=3, batch_size=16)
        uniform = RANSAC("homography", inl_th=2.0, seed=3, prosac_sampling=False, max_iter=3, batch_size=16)
        samples = prosac.sample(4, 32, 6, 0)
        assert samples[0].sort().values.tolist() == [0, 1, 2, 3]
        assert samples.amax(dim=1).tolist() == [3, 4, 5, 6, 7, 8]
        assert not torch.equal(samples, uniform.sample(4, 32, 6, 0))

    @pytest.mark.parametrize(
        "model_type, n, validated_type, validated_n",
        [
            ("fundamental_7pt", 6, "fundamental_8pt", 7),
            ("fundamental", 6, "fundamental_8pt", 7),
            ("essential", 4, "homography", 3),
        ],
    )
    def test_convention_ransac_size_validation_4872(self, model_type, n, validated_type, validated_n, device, dtype):
        _cpu_only(device)
        kp1, kp2 = _planar_matches(device, dtype)
        # Too few correspondences for the validated model types raise kornia's ValueError before sampling.
        with pytest.raises(ValueError):
            RANSAC(validated_type, max_iter=1, batch_size=4, seed=0)(kp1[:validated_n], kp2[:validated_n])
        # fundamental_7pt and essential are validated the same way. #4872 skipped them, and they failed inside the
        # sampler with a RuntimeError.
        with pytest.raises(ValueError):
            RANSAC(model_type, max_iter=1, batch_size=4, seed=0)(kp1[:n], kp2[:n])


class TestRANSACScoringAndStopping(BaseTester):
    @pytest.mark.parametrize("threshold", [0.5, 1.0, 2.0])
    def test_msac_accepts_partial_consensus(self, device, dtype, threshold):
        # A perfect 40% consensus must be accepted regardless of threshold units.
        points = torch.arange(200, device=device, dtype=dtype).reshape(100, 2)
        target = points.clone()
        target[40:] += 100
        identity = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography",
            inl_th=threshold,
            batch_size=1,
            max_iter=1,
            max_lo_iters=0,
            score_type="msac",
            local_optimization="dlt",
        )
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: identity
        model, mask = ransac(points, target)
        self.assert_close(model, identity[0])
        assert mask.shape == (100,)
        assert mask.sum() == 40

    @pytest.mark.parametrize("model_type,n", [("homography", 5), ("essential", 6), ("essential", 7)])
    def test_keep_minimal_consensus_without_polishing(self, device, dtype, model_type, n):
        # Acceptance needs one inlier beyond the minimal sample, not the eight-point polisher's point count.
        points = torch.rand(n, 2, device=device, dtype=dtype)
        matrix = torch.tensor([[0.0, 0.0, 0.0], [0.0, 0.0, -1.0], [0.0, 1.0, 0.0]], device=device, dtype=dtype)
        if model_type == "homography":
            matrix = torch.eye(3, device=device, dtype=dtype)
        ransac = RANSAC(model_type, batch_size=1, max_iter=1, local_optimization="dlt")
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: matrix[None]
        ransac.polisher_solver = lambda a, b, w: matrix[None]
        model, mask = ransac(points, points)
        assert model.abs().sum() > 0
        assert mask.shape == (n,)
        assert mask.all()

    def test_invalid_models(self, device, dtype):
        models = torch.eye(3, device=device, dtype=dtype).repeat(4, 1, 1)
        models[0] = 0
        models[1, 0, 0] = float("nan")
        models[2, 0, 0] = float("inf")
        valid = RANSAC("fundamental_7pt").remove_bad_models(models)
        self.assert_close(valid, models[3:])

    def test_msac_nonfinite_residual_is_outlier(self, device, dtype):
        points = torch.zeros(10, 2, device=device, dtype=dtype)
        candidates = torch.eye(3, device=device, dtype=dtype).repeat(2, 1, 1)
        candidates[1, 0, 2] = 1
        ransac = RANSAC(score_type="msac")
        errors = torch.zeros(2, 10, device=device, dtype=dtype)
        errors[0, 0] = float("nan")
        ransac.error_fn = lambda a, b, m: errors
        best, _, score, count = ransac.verify(points, points, candidates, 4.0)
        self.assert_close(best, candidates[1])
        assert math.isfinite(score)
        assert count == 10

    def test_stopping_uses_support_after_lo_and_checks_unchanged_best(self, device, dtype):
        # LO increases support to 70/100. The MSAC score is intentionally different.
        points = torch.rand(100, 2, device=device, dtype=dtype)
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "fundamental_8pt", batch_size=16, max_iter=10, max_lo_iters=1, score_type="msac", local_optimization="dlt"
        )
        sampled = []
        ransac.minimal_solver = lambda a, b, w: sampled.append(1) or matrix
        ransac.polisher_solver = lambda a, b, w: matrix
        calls = []

        def verify(a, b, models, threshold):
            calls.append(1)
            count = 70 if len(calls) == 2 else 50
            mask = torch.arange(100, device=device) < count
            return matrix[0], mask, float(count - 20), float(count)

        ransac.verify = verify
        ransac(points, points)
        expected = math.ceil(RANSAC.max_samples_by_conf(70, 100, 8, 0.99) / 16)
        assert len(sampled) == expected

    def test_exact_minimal_support_confidence(self):
        # Exactly four inliers among ten: success probability is 1 / C(10, 4).
        expected = math.ceil(math.log1p(-0.99) / math.log1p(-1 / math.comb(10, 4)))
        assert RANSAC.max_samples_by_conf(4, 10, 4, 0.99) == expected

    @pytest.mark.parametrize("confidence,outliers,batches", [(0.99, 1, 1), (1.0, 1, 3), (0.99, 0, 1), (1.0, 0, 3)])
    def test_unit_confidence_runs_full_budget(self, device, dtype, confidence, outliers, batches):
        # 19 of 20 inliers: 0.99 confidence needs three minimal samples, i.e. one batch. With every
        # point an inlier the bound is one sample, but confidence=1 must still run the whole budget.
        points = torch.rand(20, 2, device=device, dtype=dtype)
        target = points.clone()
        target[:outliers] += 100
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography", batch_size=8, max_iter=3, max_lo_iters=0, confidence=confidence, local_optimization="dlt"
        )
        calls = []
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: calls.append(1) or matrix
        ransac(points, target)
        assert len(calls) == batches

    def test_failure_mask_shape(self, device, dtype):
        points = torch.zeros(10, 2, device=device, dtype=dtype)
        ransac = RANSAC("fundamental", batch_size=2, max_iter=1, local_optimization="dlt")
        ransac.minimal_solver = lambda a, b, w: torch.zeros(1, 3, 3, device=device, dtype=dtype)
        _, mask = ransac(points, points)
        assert mask.shape == (10,)
        assert not mask.any()

    @pytest.mark.parametrize("score_type", ["ransac", "msac"])
    def test_under_supported_best_is_rejected(self, device, dtype, score_type):
        # Four agreeing points are no more than a homography's minimal sample, which any sample fits.
        points = torch.rand(10, 2, device=device, dtype=dtype)
        target = points + 100
        target[:4] = points[:4]
        identity = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography", batch_size=1, max_iter=2, max_lo_iters=0, score_type=score_type, local_optimization="dlt"
        )
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: identity
        model, mask = ransac(points, target)
        assert not model.any()
        assert not mask.any()

    def test_stopping_bound_follows_incumbent_support(self, device, dtype):
        # Under MSAC a better-scoring model can have less support than the one it replaces. The
        # stopping bound must then follow the new incumbent, not the larger support it displaced.
        points = torch.rand(100, 2, device=device, dtype=dtype)
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "fundamental_8pt", batch_size=1, max_iter=50, max_lo_iters=0, score_type="msac", local_optimization="dlt"
        )
        sampled = []
        ransac.minimal_solver = lambda a, b, w: sampled.append(1) or matrix
        results = {1: (1.0, 95), 2: (2.0, 60)}

        def verify(a, b, models, threshold):
            score, count = results.get(len(sampled), (0.0, 50))
            return matrix[0], torch.arange(100, device=device) < count, score, float(count)

        ransac.verify = verify
        ransac(points, points)
        assert RANSAC.max_samples_by_conf(95, 100, 8, 0.99) < 50 < RANSAC.max_samples_by_conf(60, 100, 8, 0.99)
        assert len(sampled) == 50

    @pytest.mark.parametrize("lo_sample_size,expected_calls", [(None, 1), (8, 2)])
    def test_invalid_refit_is_not_repeated(self, device, dtype, lo_sample_size, expected_calls):
        # A failed full-inlier refit would fail identically on the unchanged inliers. A failed subset
        # batch still leaves the full refit to try.
        points = torch.rand(20, 2, device=device, dtype=dtype)
        identity = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography",
            batch_size=1,
            max_iter=1,
            max_lo_iters=5,
            lo_sample_size=lo_sample_size,
            seed=0,
            local_optimization="dlt",
        )
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: identity
        calls = []
        ransac.polisher_solver = lambda a, b, w: (
            calls.append(1) or torch.full_like(identity, float("nan")).expand(len(a), 3, 3)
        )
        model, mask = ransac(points, points)
        self.assert_close(model, identity[0])
        assert mask.all()
        assert len(calls) == expected_calls

    @pytest.mark.parametrize("lo_sample_size", [None, 8])
    def test_full_inlier_refit_wins_ties(self, device, dtype, lo_sample_size):
        # RANSAC scoring ties whenever the refit keeps the same support; the least-squares refit
        # must still replace the minimal-sample model, which is only as precise as its sample.
        points = torch.rand(20, 2, device=device, dtype=dtype)
        minimal = torch.eye(3, device=device, dtype=dtype)[None]
        refit = 2 * minimal
        ransac = RANSAC(
            "homography",
            batch_size=1,
            max_iter=1,
            max_lo_iters=3,
            lo_sample_size=lo_sample_size,
            seed=0,
            local_optimization="dlt",
        )
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: minimal
        polished = []
        ransac.polisher_solver = lambda a, b, w: polished.append(1) or refit.expand(len(a), 3, 3)
        mask = torch.ones(20, device=device, dtype=torch.bool)
        ransac.verify = lambda a, b, m, t: (m[0].clone(), mask, 20.0, 20.0)
        model, _ = ransac(points, points)
        self.assert_close(model, refit[0])
        # A tie ends local optimization: it cannot increase support any further.
        assert len(polished) == (2 if lo_sample_size else 1)


class TestRANSACSampling(BaseTester):
    def test_prosac_growth_per_draw(self, device):
        # Chum & Matas (CVPR 2005), eqs. 3--6; m=4, N=10, T_N=64.
        ransac = RANSAC(batch_size=16, max_iter=4, prosac_sampling=True, seed=7)
        samples = torch.cat([ransac.sample(4, 10, 16, i, device) for i in range(4)])
        ends = [1, 3, 7, 14, 25, 43, 69]
        expected = torch.tensor(
            [next(n + 3 for n, end in enumerate(ends) if t <= end) for t in range(1, 65)], device=device
        )
        assert torch.equal(samples.amax(1), expected)
        assert torch.all(samples.sort(1).values.diff(dim=1) > 0)
        # A different batch partition must have the same prefix schedule at equal budget.
        other = RANSAC(batch_size=32, max_iter=2, prosac_sampling=True, seed=7)
        larger = torch.cat([other.sample(4, 10, 32, i, device) for i in range(2)])
        assert torch.equal(larger.amax(1), expected)

    def test_sample_accepts_device_string(self, device):
        ransac = RANSAC(seed=0)
        by_name = ransac.sample(4, 10, 3, 0, str(device))
        assert by_name.device.type == device.type
        assert torch.equal(by_name, ransac.sample(4, 10, 3, 0, device))

    def test_prosac_eventually_uniform(self, device):
        ransac = RANSAC(batch_size=128, max_iter=1, prosac_sampling=True, seed=3)
        samples = ransac.sample(4, 10, 128, 10, device)
        assert torch.any(samples.amax(1) < 9)
        assert torch.all(samples.sort(1).values.diff(dim=1) > 0)

    @pytest.mark.parametrize("population", [4, 10, 1000])
    def test_uniform_without_replacement(self, device, population):
        ransac = RANSAC(seed=0)
        samples = ransac.sample(4, population, 10000, 0, device)
        assert samples.min() >= 0
        assert samples.max() < population
        assert torch.all(samples.sort(1).values.diff(dim=1) > 0)
        # Check marginal inclusion, independent of ordering within each sampled set.
        counts = torch.bincount(samples.flatten(), minlength=population).float()
        expected = 40000 / population
        assert (counts - expected).abs().max() < 7 * math.sqrt(expected)

    @pytest.mark.parametrize("confidence,batches", [(0.99, 1), (1.0, 3)])
    def test_prosac_confidence(self, device, dtype, confidence, batches):
        points = torch.rand(20, 2, device=device, dtype=dtype)
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography",
            batch_size=8,
            max_iter=3,
            max_lo_iters=0,
            prosac_sampling=True,
            confidence=confidence,
            local_optimization="dlt",
        )
        calls = []
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: calls.append(1) or matrix
        ransac(points, points)
        assert len(calls) == batches

    def test_prosac_stopping_uses_ranking(self, device):
        ransac = RANSAC("fundamental_8pt", batch_size=16, max_iter=256, prosac_sampling=True)
        # 150 inliers of 500: ranked first, one draw from the top-150 prefix certifies the model.
        # Ranked last, no prefix qualifies and the uniform bound (over 60,000 draws) caps at the budget.
        ranked = torch.arange(500, device=device) < 150
        assert ransac._prosac_max_samples(ranked, 150) == 1
        assert ransac._prosac_max_samples(ranked.flip(0), 150) == 4096

    @pytest.mark.parametrize("support", [0, 8, 9, 50, 99])
    def test_prosac_stopping_rejects_small_prefix_support(self, device, support):
        ransac = RANSAC("fundamental_8pt", batch_size=16, max_iter=256, prosac_sampling=True)
        # Fewer than 20% of all correspondences cannot terminate, however perfect the prefix
        # (OpenCV USAC guard): the top ten all-inlier matches of a locally fitted model are no evidence.
        inliers = torch.arange(500, device=device) < support
        assert ransac._prosac_max_samples(inliers, support) == 4096

    def test_prosac_stopping_without_replacement(self, device):
        ransac = RANSAC("homography", batch_size=16, max_iter=256, prosac_sampling=True)
        # The best prefix is the whole set. C(10,4)/C(20,4) requires 104 draws
        # for 99% confidence; the with-replacement approximation gives only 72.
        inliers = torch.arange(20, device=device) >= 10
        assert ransac._prosac_max_samples(inliers, 10) == 104
        assert ransac.max_samples_by_conf(10, 20, 4, 0.99) == 104
        ransac.confidence = 1
        assert ransac._prosac_max_samples(inliers, 10) == 4096

    def test_prosac_stopping_never_exceeds_uniform_bound(self, device):
        ransac = RANSAC("homography", batch_size=16, max_iter=256, prosac_sampling=True)
        generator = torch.Generator().manual_seed(0)
        for _ in range(20):
            inliers = (torch.rand(300, generator=generator) < 0.4).to(device)
            support = int(inliers.sum())
            uniform = min(4096, ransac.max_samples_by_conf(support, 300, 4, 0.99))
            assert 1 <= ransac._prosac_max_samples(inliers, support) <= uniform

    @pytest.mark.parametrize("replace_incumbent", [False, True])
    def test_prosac_stopping_after_multiple_batches(self, device, dtype, replace_incumbent):
        points = torch.rand(20, 2, device=device, dtype=dtype)
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography",
            batch_size=16,
            max_iter=16,
            max_lo_iters=0,
            score_type="msac",
            prosac_sampling=True,
            local_optimization="dlt",
        )
        calls = []
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: calls.append(1) or matrix

        def verify(a, b, models, threshold):
            # The initial incumbent requires 104 draws (seven batches). A
            # better MSAC score with less support needs the entire budget.
            replace = replace_incumbent and len(calls) >= 2
            mask = torch.arange(20, device=device) >= (15 if replace else 10)
            return matrix[0], mask, 2.0 if replace else 1.0, float(mask.sum())

        ransac.verify = verify
        for _ in range(2):
            calls.clear()
            ransac(points, points)
            assert len(calls) == (16 if replace_incumbent else 7)

    def test_prosac_minimal_population(self, device):
        ransac = RANSAC("homography", batch_size=16, max_iter=256, prosac_sampling=True)
        assert ransac._prosac_max_samples(torch.ones(4, device=device, dtype=torch.bool), 4) == 4096

    def test_prosac_stopping_respects_growth(self, device):
        ransac = RANSAC("fundamental_8pt", batch_size=16, max_iter=256, prosac_sampling=True)
        # 45 inliers among the top 100 of 200 pass the support guards, but the 3970 draws that
        # prefix needs exceed the ~106 draws PROSAC takes from it: later draws sampled larger
        # prefixes and must not be credited to the top 100. The uniform bound caps at the budget.
        inliers = torch.zeros(200, device=device, dtype=torch.bool)
        inliers[:90:2] = True
        assert ransac._prosac_max_samples(inliers, 45) == 4096
        assert ransac._prosac_schedule(8, 200, inliers.device)[100 - 8].item() < 3970

    def test_prosac_stops_on_a_certified_prefix(self, device, dtype):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("a 1 px threshold on 500 px coordinates is below half-precision resolution")
        # 150 of 500 correspondences follow the homography and are ranked first: PROSAC stops after
        # its first batch, while uniform sampling needs far more than one batch of 16 at 30% inliers.
        torch.manual_seed(0)
        matrix = torch.tensor([[1.1, 0.05, 20.0], [0.02, 0.95, -10.0], [1e-4, -2e-4, 1.0]], device=device, dtype=dtype)
        points1 = torch.rand(500, 2, device=device, dtype=dtype) * 800
        points2 = transform_points(matrix[None], points1[None])[0]
        points2[150:] = torch.rand(350, 2, device=device, dtype=dtype) * 800
        calls = []
        for prosac in (True, False):
            ransac = RANSAC(
                "homography", inl_th=1.0, batch_size=16, max_iter=64, max_lo_iters=0, prosac_sampling=prosac, seed=0
            )
            sample = ransac.sample
            count = []
            ransac.sample = lambda *a, _s=sample, _c=count, **k: _c.append(1) or _s(*a, **k)
            _, mask = ransac(points1, points2)
            calls.append(len(count))
            assert mask[:150].all()
        assert calls[0] == 1
        assert calls[1] > 1


class TestRANSACDefaults(BaseTester):
    def test_defaults_are_msac_and_bounded_lo(self):
        ransac = RANSAC("fundamental")
        assert ransac.score_type == "msac"
        assert ransac.lo_sample_size == 32
        assert ransac.max_lo_iters == 5
        assert not ransac.prosac_sampling

    @pytest.mark.parametrize(
        "model_type, sample_size, local_optimization",
        [
            ("homography", 4, "lm"),
            ("fundamental", 7, "lm"),
            ("fundamental_7pt", 7, "lm"),
            ("fundamental_8pt", 8, "lm"),
            ("essential", 5, "lm"),
            ("homography_from_linesegments", 4, "dlt"),
        ],
    )
    def test_defaults_per_model(self, model_type, sample_size, local_optimization):
        # "fundamental" draws seven-point samples; Levenberg-Marquardt local optimization is the default wherever it
        # is implemented.
        ransac = RANSAC(model_type)
        assert ransac.minimal_sample_size == sample_size
        assert ransac.local_optimization == local_optimization
        assert ransac.refine_iters == 3

    def test_legacy_configuration_is_still_available(self):
        ransac = RANSAC("fundamental", score_type="ransac", lo_sample_size=None)
        assert ransac.score_type == "ransac"
        assert ransac.lo_sample_size is None


class TestRANSACAutoBatch(BaseTester):
    def test_default_is_auto_with_the_historical_budget(self):
        ransac = RANSAC("homography")
        assert ransac.batch_size == "auto"
        assert ransac.sample_budget == 2048 * 10

    @pytest.mark.parametrize("bad", [0, -1, 2.5, True, "large"])
    def test_rejects_bad_batch_size(self, bad):
        with pytest.raises(ValueError):
            RANSAC("homography", batch_size=bad)

    @pytest.mark.parametrize("bad", [0, -5, True, 1000.0])
    def test_rejects_bad_max_samples(self, bad):
        with pytest.raises(ValueError):
            RANSAC("homography", max_samples=bad)

    def test_explicit_batch_keeps_its_budget(self):
        ransac = RANSAC("fundamental", batch_size=512, max_iter=4)
        assert ransac.sample_budget == 2048
        assert ransac.resolve_batch_size(5000, torch.device("cpu")) == 512
        assert ransac.resolve_batch_size(5000, torch.device("cuda")) == 512

    def test_max_samples_overrides_the_budget(self):
        assert RANSAC("homography", batch_size=256, max_iter=100, max_samples=1000).sample_budget == 1000
        assert RANSAC("homography", max_samples=1000).sample_budget == 1000

    def test_budget_follows_later_attribute_changes(self):
        # The budget is read at call time, like confidence, so configuring the module after construction works.
        ransac = RANSAC("homography", batch_size=256)
        ransac.max_iter = 100
        assert ransac.sample_budget == 25600
        ransac.max_samples = 1000
        assert ransac.sample_budget == 1000

    def test_accelerator_batch_shrinks_for_many_correspondences(self):
        # The residual matrix is batch x N: past 2**27 entries (1 GiB in float32 at peak) the batch shrinks, down to
        # the 2048 of the fixed historical batch, so the default cannot run out of memory where it did not before.
        cuda = torch.device("cuda")
        ransac = RANSAC("homography")
        assert ransac.resolve_batch_size(16384, cuda) == 8192
        assert ransac.resolve_batch_size(50000, cuda) == 2684
        assert ransac.resolve_batch_size(1_000_000, cuda) == 2048
        assert RANSAC("fundamental").resolve_batch_size(1_000_000, cuda) == 2048

    def test_accelerators_take_large_batches(self):
        ransac = RANSAC("homography", max_samples=5000)
        for device in (torch.device("cuda"), torch.device("mps")):
            assert ransac.resolve_batch_size(500, device) == 5000
        assert RANSAC("homography").resolve_batch_size(500, torch.device("cuda")) == 8192
        assert RANSAC("homography_from_linesegments").resolve_batch_size(500, torch.device("cuda")) == 8192
        # The epipolar solvers are compute-bound past 2048 hypotheses on the GPU.
        assert RANSAC("fundamental").resolve_batch_size(500, torch.device("cuda")) == 2048
        assert RANSAC("essential", max_samples=1000).resolve_batch_size(500, torch.device("mps")) == 1000

    @pytest.mark.parametrize("backend", ["xla", "privateuseone"])
    def test_other_devices_keep_historical_batch(self, backend):
        device = torch.device(backend)
        assert RANSAC("homography").resolve_batch_size(500, device) == 2048
        assert RANSAC("fundamental").resolve_batch_size(500, device) == 2048
        assert RANSAC("homography", max_samples=1000).resolve_batch_size(500, device) == 1000

    @pytest.mark.parametrize(
        "model_type,num_tc,expected",
        [
            ("homography", 100, 2048),
            ("homography", 500, 1048),
            ("homography", 4000, 256),
            ("fundamental", 100, 512),
            ("fundamental", 500, 262),
            ("fundamental", 4000, 128),
            ("essential", 4000, 128),
        ],
    )
    def test_cpu_batch_follows_model_and_point_count(self, model_type, num_tc, expected):
        assert RANSAC(model_type).resolve_batch_size(num_tc, torch.device("cpu")) == expected
        assert RANSAC(model_type, max_samples=200).resolve_batch_size(num_tc, torch.device("cpu")) == min(expected, 200)

    def test_last_batch_is_truncated_to_the_budget(self, device, dtype):
        points = torch.rand(20, 2, device=device, dtype=dtype)
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography", batch_size=16, max_samples=40, max_lo_iters=0, confidence=1.0, local_optimization="dlt"
        )
        sizes = []
        ransac.remove_bad_samples = lambda a, b: sizes.append(len(a)) or (a, b)
        ransac.minimal_solver = lambda a, b, w: matrix
        ransac(points, points)
        assert sizes == [16, 16, 8]

    def test_truncated_last_batch_continues_the_prosac_schedule(self, device, dtype):
        # The PROSAC schedule counts draws, not batches: the truncated last batch of a 1000-draw budget takes draws
        # 801 to 1000, from the largest prefixes, rather than restarting at an earlier point of the schedule.
        num_tc = 100
        points = torch.arange(num_tc, device=device, dtype=dtype)[:, None].expand(num_tc, 2)
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography",
            batch_size=400,
            max_samples=1000,
            prosac_sampling=True,
            max_lo_iters=0,
            confidence=1.0,
            local_optimization="dlt",
        )
        batches = []
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.minimal_solver = lambda a, b, w: batches.append(a[..., 0].long()) or matrix.expand(len(a), 3, 3)
        ransac(points, points)
        assert [len(b) for b in batches] == [400, 400, 200]
        ends = ransac._prosac_schedule(4, num_tc, points.device)
        assert int(ends[-1]) >= 1000  # the schedule is still growing at the last draw
        # Every growth draw includes the newest correspondence of its prefix, so the largest index a batch draws is
        # the prefix its last draw belongs to.
        last_draws = torch.tensor([400, 800, 1000], device=points.device)
        expected = (torch.searchsorted(ends, last_draws) + 4).tolist()
        assert [int(b.max()) + 1 for b in batches] == expected

    def test_auto_batch_forward_matches_explicit_batch(self, device, dtype):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("a 1 px threshold on 500 px coordinates is below half-precision resolution")
        # The auto batch is a plain batch size: the same seed gives the same draws as that size given explicitly.
        torch.manual_seed(0)
        kp1 = torch.rand(200, 2, device=device, dtype=dtype) * 500
        matrix = torch.tensor([[1.0, 0.1, 5.0], [0.0, 1.0, 3.0], [0.0, 0.0, 1.0]], device=device, dtype=dtype)
        kp2 = transform_points(matrix[None], kp1[None])[0]
        kp2[:60] = torch.rand(60, 2, device=device, dtype=dtype) * 500
        auto = RANSAC("homography", inl_th=1.0, seed=0, local_optimization="dlt")
        batch = auto.resolve_batch_size(200, kp1.device)
        explicit = RANSAC("homography", inl_th=1.0, batch_size=batch, seed=0, local_optimization="dlt")
        H_auto, mask_auto = auto(kp1, kp2)
        H_explicit, mask_explicit = explicit(kp1, kp2)
        assert torch.equal(mask_auto, mask_explicit)
        self.assert_close(H_auto, H_explicit)
        assert mask_auto[60:].all()


class TestRANSACPolisherScale(BaseTester):
    @pytest.mark.parametrize("model_type", ["homography", "homography_from_linesegments"])
    @pytest.mark.parametrize("inl_th", [0.5, 2.0])
    def test_polisher_gaussian_scale_is_inlier_threshold(self, model_type, inl_th):
        # The IRLS polisher's Gaussian re-weighting uses the inlier threshold as its standard deviation.
        ransac = RANSAC(model_type, inl_th=inl_th)
        assert ransac.polisher_solver.keywords == {"soft_inl_th": inl_th}


class TestRANSACBoundedLO(BaseTester):
    def test_subset_refits_and_final_full_refit(self, device, dtype):
        points = torch.rand(100, 2, device=device, dtype=dtype)
        matrix = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "fundamental",
            batch_size=1,
            max_iter=1,
            max_lo_iters=3,
            lo_sample_size=16,
            seed=0,
            local_optimization="dlt",
        )
        ransac.minimal_solver = lambda a, b, w: matrix
        sizes = []
        ransac.polisher_solver = lambda a, b, w: sizes.append(a.shape[:2]) or matrix
        mask = torch.ones(100, device=device, dtype=torch.bool)
        ransac.verify = lambda a, b, m, t: (matrix[0], mask, 100.0, 100.0)
        ransac(points, points)
        assert sizes == [(3, 16), (1, 100)]

    def test_bad_subset_does_not_replace_best(self, device, dtype):
        points = torch.rand(40, 2, device=device, dtype=dtype)
        identity = torch.eye(3, device=device, dtype=dtype)[None]
        wrong = identity.clone()
        wrong[:, 0, 2] = 100
        ransac = RANSAC(
            "homography",
            batch_size=1,
            max_iter=1,
            max_lo_iters=2,
            lo_sample_size=8,
            score_type="msac",
            seed=3,
            local_optimization="dlt",
        )
        ransac.minimal_solver = lambda a, b, w: identity
        ransac.remove_bad_samples = lambda a, b: (a, b)
        ransac.polisher_solver = lambda a, b, w: wrong
        model, mask = ransac(points, points)
        self.assert_close(model, identity[0])
        assert mask.all()

    def test_seeded_subsets_reproducible(self, device, dtype):
        points = torch.rand(50, 2, device=device, dtype=dtype)
        identity = torch.eye(3, device=device, dtype=dtype)[None]
        ransac = RANSAC(
            "homography",
            batch_size=1,
            max_iter=1,
            max_lo_iters=2,
            lo_sample_size=8,
            seed=13,
            local_optimization="dlt",
        )
        ransac.minimal_solver = lambda a, b, w: identity
        ransac.remove_bad_samples = lambda a, b: (a, b)
        subsets = []
        ransac.polisher_solver = lambda a, b, w: subsets.append(a.clone()) or identity
        ransac(points, points)
        ransac(points, points)
        self.assert_close(subsets[0], subsets[2])
        self.assert_close(subsets[1], subsets[3])
        assert not torch.equal(subsets[0][0], subsets[0][1])


class TestRANSACAutocast(BaseTester):
    @pytest.mark.parametrize("model_type", ["homography", "fundamental"])
    @pytest.mark.parametrize("local_optimization", ["lm", "dlt"])
    def test_autocast_does_not_reach_the_estimate(self, device, model_type, local_optimization):
        # Under a caller's bfloat16 autocast, local_optimization="dlt" fitted in bfloat16 and returned a bfloat16
        # model (CUDA "fundamental" raised in eigh), and "lm" solved and scored its minimal samples in bfloat16, which
        # changed its estimate. Noise at half the threshold puts many inliers where bfloat16 scores flip them.
        if device.type not in ("cpu", "cuda"):
            pytest.skip("CPU and CUDA autocast")
        kp1, kp2, _, _, _ = create_dominant_plane_scene(500, 0.9, 0.5, 0, noise=1.0, device=device)
        results = []
        for enabled in (False, True):
            ransac = RANSAC(model_type, inl_th=2.0, seed=0, local_optimization=local_optimization)
            with torch.autocast(device.type, dtype=torch.bfloat16, enabled=enabled):
                results.append(ransac(kp1, kp2))
        (expected, expected_inliers), (actual, actual_inliers) = results
        assert actual.dtype == torch.float32
        assert expected_inliers.any()
        self.assert_close(actual, expected, atol=0, rtol=0)
        self.assert_close(actual_inliers, expected_inliers, atol=0, rtol=0)


class TestRANSACValidation(BaseTester):
    @pytest.mark.parametrize(
        "kwargs",
        [
            {"inl_th": 0.0},
            {"inl_th": float("nan")},
            {"batch_size": 0},
            {"max_iter": 0},
            {"max_lo_iters": -1},
            {"score_type": "magsac"},
            {"confidence": 1.5},
            {"confidence": 0.0},
            {"lo_sample_size": 3},
            {"local_optimization": "irls"},
            {"refine_iters": -1},
            {"refine_iters": True},
            {"refine_iters": 1.5},
        ],
    )
    def test_invalid_configuration(self, kwargs):
        with pytest.raises(ValueError):
            RANSAC(**kwargs)

    def test_lm_local_optimization_needs_a_supported_model(self):
        with pytest.raises(ValueError):
            RANSAC("homography_from_linesegments", local_optimization="lm")

    @pytest.mark.parametrize("model", ["fundamental_7pt", "essential"])
    def test_mismatched_correspondences(self, device, dtype, model):
        points = torch.zeros(9, 2, device=device, dtype=dtype)
        with pytest.raises(ValueError):
            RANSAC(model).validate_inputs(points, points[:8])

    @pytest.mark.parametrize(("model", "shape"), [("homography", (3, 2)), ("homography_from_linesegments", (3, 2, 2))])
    def test_too_few_correspondences_message_6422(self, device, dtype, model, shape):
        # The message used to contain runs of spaces.
        points = torch.zeros(shape, device=device, dtype=dtype)
        with pytest.raises(ValueError) as excinfo:
            RANSAC(model).validate_inputs(points, points)
        minimal = [4, *shape[1:]]
        size = torch.Size(shape)
        assert str(excinfo.value) == f"kp1 and kp2 should be equal shape at least {minimal}, got {size}, {size}"

    @staticmethod
    def _projection_case(device, dtype, extra_exact_points):
        # Every correspondence fits this rank-two F exactly. Its projection onto the essential manifold
        # fits only the points with y = 0 and moves the others to a squared Sampson error of 0.5.
        points1 = torch.tensor(
            [[0.0, 0.0], [0.0, 1.0], [1.0, 0.0], [1.0, 1.0], [2.0, 1.0], [2.0, 0.0], [3.0, 1.0], [3.0, 0.0]]
            + [[4.0 + i, 0.0] for i in range(extra_exact_points)],
            device=device,
            dtype=dtype,
        )
        points2 = points1.clone()
        points2[:, 1] *= 2
        candidate = torch.tensor([[0.0, 0.0, 0.0], [0.0, 0.0, -1.0], [0.0, 2.0, 0.0]], device=device, dtype=dtype)[None]
        ransac = RANSAC("essential", inl_th=0.01, batch_size=1, max_iter=1, max_lo_iters=0, local_optimization="dlt")
        ransac.minimal_solver = lambda a, b, w: candidate
        return ransac, points1, points2

    def test_essential_mask_matches_projected_output(self, device, dtype):
        ransac, points1, points2 = self._projection_case(device, dtype, extra_exact_points=2)
        model, mask = ransac(points1, points2)
        expected = sampson_epipolar_distance(points1[None], points2[None], model[None])[0] <= 0.01**2
        assert model.abs().amax() > 0
        assert torch.equal(mask, expected)
        assert torch.equal(mask, points1[:, 1] == 0)

    def test_essential_projection_below_minimal_support_fails(self, device, dtype):
        # Four of the eight points survive the projection, fewer than the five-point minimal sample.
        ransac, points1, points2 = self._projection_case(device, dtype, extra_exact_points=0)
        model, mask = ransac(points1, points2)
        assert not model.any()
        assert mask.shape == (8,)
        assert not mask.any()


class TestRANSACMSACSelection(BaseTester):
    def test_skip_candidates_with_insufficient_support(self, device, dtype):
        points = torch.zeros(10, 2, device=device, dtype=dtype)
        candidates = torch.eye(3, device=device, dtype=dtype).repeat(2, 1, 1)
        candidates[1, 0, 2] = 1
        errors = torch.full((2, 10), 100.0, device=device, dtype=dtype)
        # Candidate 0 fits only a minimal sample's worth of points, exactly; candidate 1 has one more inlier.
        errors[0, :4] = 0.0
        errors[1, :5] = 2.0
        ransac = RANSAC("homography", score_type="msac")
        ransac.error_fn = lambda a, b, m: errors
        model, _, _, count = ransac.verify(points, points, candidates, 4.0)
        self.assert_close(model, candidates[1])
        assert count == 5

    def test_msac_score_accumulates_in_float32(self, device):
        # 999 is not a bfloat16 value: summing the per-point scores in bfloat16 rounds it to 1000.
        points = torch.zeros(999, 2, device=device, dtype=torch.bfloat16)
        model = torch.eye(3, device=device, dtype=torch.bfloat16)[None]
        ransac = RANSAC("homography", score_type="msac")
        ransac.error_fn = lambda a, b, m: torch.zeros(1, 999, device=device, dtype=torch.bfloat16)
        _, _, score, count = ransac.verify(points, points, model, 4.0)
        assert score == 999.0
        assert count == 999

    @pytest.mark.parametrize("threshold", [0.0, -1.0, float("nan"), float("inf")])
    def test_invalid_verify_threshold(self, device, dtype, threshold):
        points = torch.zeros(4, 2, device=device, dtype=dtype)
        with pytest.raises(ValueError):
            RANSAC(score_type="msac").verify(points, points, torch.eye(3, device=device, dtype=dtype)[None], threshold)


class TestRANSACLineScoring(BaseTester):
    def test_squared_distance_independent_of_segment_length(self, device, dtype):
        # Horizontal segments all displaced vertically by 3px: squared distance = 9,
        # regardless of whether the segment is 1px or 10px long.
        source = torch.tensor(
            [[[[0.0, 0.0], [1.0, 0.0]], [[0.0, 0.0], [3.0, 0.0]], [[0.0, 0.0], [5.0, 0.0]], [[0.0, 0.0], [10.0, 0.0]]]],
            device=device,
            dtype=dtype,
        )
        target = source.clone()
        target[..., 1] += 3
        estimator = RANSAC("homography_from_linesegments", score_type="msac")
        errors = estimator.error_fn(source, target, torch.eye(3, device=device, dtype=dtype)[None])
        self.assert_close(errors, torch.full((1, 4), 9.0, device=device, dtype=dtype))

    def test_zero_length_target_is_outlier(self, device, dtype):
        source = torch.tensor([[[[0.0, 0.0], [1.0, 0.0]]]], device=device, dtype=dtype)
        target = torch.zeros_like(source)
        estimator = RANSAC("homography_from_linesegments")
        errors = estimator.error_fn(source, target, torch.eye(3, device=device, dtype=dtype)[None])
        assert torch.isinf(errors).all()


class TestRANSACEssentialInvalidPolisher(BaseTester):
    @pytest.mark.parametrize("lo_sample_size", [None, 8])
    def test_discard_nonfinite_polisher_before_projection(self, device, dtype, lo_sample_size):
        points = torch.rand(20, 2, device=device, dtype=dtype)
        valid = torch.tensor([[0.0, 0.0, 0.0], [0.0, 0.0, -1.0], [0.0, 1.0, 0.0]], device=device, dtype=dtype)[None]
        candidates = torch.cat([torch.full_like(valid, float("nan")), valid])
        estimator = RANSAC(
            "essential",
            batch_size=1,
            max_iter=1,
            max_lo_iters=2,
            lo_sample_size=lo_sample_size,
            seed=0,
            local_optimization="dlt",
        )
        estimator.minimal_solver = lambda a, b, w: valid
        estimator.polisher_solver = lambda a, b, w: candidates
        model, mask = estimator(points, points)
        assert torch.isfinite(model).all()
        assert mask.all()


def _skew(v: torch.Tensor) -> torch.Tensor:
    return torch.tensor([[0.0, -v[2], v[1]], [v[2], 0.0, -v[0]], [-v[1], v[0], 0.0]], dtype=v.dtype)


def _two_view_scene(n: int, outliers: int, noise: float, seed: int):
    """Pixel matches of a 640x480 two-view scene, the first ``outliers`` replaced by random points. float64 CPU.

    Returns the matches, their noise-free second-image positions, the ground-truth F and the inlier mask.
    """
    generator = torch.Generator().manual_seed(seed)
    f64 = torch.float64
    K = torch.tensor([[800.0, 0.0, 320.0], [0.0, 800.0, 240.0], [0.0, 0.0, 1.0]], dtype=f64)
    R = axis_angle_to_rotation_matrix(torch.tensor([[0.05, -0.1, 0.02]], dtype=f64))[0]
    t = torch.tensor([1.0, 0.1, 0.2], dtype=f64)
    X = torch.randn(n, 3, generator=generator, dtype=f64) * torch.tensor([2.0, 2.0, 1.0], dtype=f64)
    X = X + torch.tensor([0.0, 0.0, 8.0], dtype=f64)
    kp1 = convert_points_from_homogeneous(X @ K.T)
    clean = convert_points_from_homogeneous((X @ R.T + t) @ K.T)
    kp2 = clean + noise * torch.randn(n, 2, generator=generator, dtype=f64)
    kp2[:outliers] = torch.rand(outliers, 2, generator=generator, dtype=f64) * torch.tensor([640.0, 480.0], dtype=f64)
    F = torch.linalg.inv(K).T @ _skew(t) @ R @ torch.linalg.inv(K)
    inliers = torch.arange(n) >= outliers
    return kp1, kp2, clean, F / F.norm(), inliers


def _planar_scene(n: int, outliers: int, noise: float, seed: int):
    """Matches ``kp2 = H(kp1)`` over 600x600 px, the first ``outliers`` replaced by random points. float64 CPU."""
    generator = torch.Generator().manual_seed(seed)
    f64 = torch.float64
    H = torch.tensor([[1.1, 0.05, 20.0], [0.02, 0.95, -10.0], [1e-4, 2e-4, 1.0]], dtype=f64)
    kp1 = torch.rand(n, 2, generator=generator, dtype=f64) * 600
    clean = transform_points(H[None], kp1[None])[0]
    kp2 = clean + noise * torch.randn(n, 2, generator=generator, dtype=f64)
    kp2[:outliers] = torch.rand(outliers, 2, generator=generator, dtype=f64) * 600
    return kp1, kp2, clean, H, torch.arange(n) >= outliers


def _model_errors(model_type: str, model: torch.Tensor, kp1: torch.Tensor, kp2: torch.Tensor) -> torch.Tensor:
    """Unsquared pixel errors in float64: Sampson distances, or one-way transfer errors for homographies."""
    model, kp1, kp2 = model.cpu().double(), kp1.cpu().double(), kp2.cpu().double()
    if model_type == "homography":
        return oneway_transfer_error(kp1[None], kp2[None], model[None], squared=False, eps=0.0)[0]
    return sampson_epipolar_distance(kp1[None], kp2[None], model[None], squared=False, eps=0.0)[0]


_FOCAL, _CENTER = 800.0, (320.0, 240.0)


def _px(model_type: str, pixels: float) -> float:
    """A distance given in pixels, in the input units of ``model_type``: calibrated units for ``"essential"``."""
    return pixels / _FOCAL if model_type == "essential" else pixels


def _to_input_units(model_type: str, kp: torch.Tensor) -> torch.Tensor:
    """Pixel coordinates of :func:`_two_view_scene`'s camera, as normalized camera coordinates for ``"essential"``."""
    if model_type != "essential":
        return kp
    return (kp - torch.tensor(_CENTER, dtype=kp.dtype, device=kp.device)) / _FOCAL


def _scene(model_type: str, n: int, outliers: int, noise: float, seed: int):
    """``kp1, kp2, clean, model, inliers``; for ``"essential"`` the two-view scene in normalized camera coordinates."""
    if model_type == "homography":
        return _planar_scene(n, outliers, noise, seed)
    kp1, kp2, clean, F, inliers = _two_view_scene(n, outliers, noise, seed)
    if model_type != "essential":
        return kp1, kp2, clean, F, inliers
    K = torch.tensor([[_FOCAL, 0.0, _CENTER[0]], [0.0, _FOCAL, _CENTER[1]], [0.0, 0.0, 1.0]], dtype=F.dtype)
    E = K.T @ F @ K
    return (*(_to_input_units(model_type, kp) for kp in (kp1, kp2, clean)), E / E.norm(), inliers)


_LM_MODELS = ["homography", "fundamental", "fundamental_8pt", "essential"]


class TestRANSACLevenbergMarquardt(BaseTester):
    """``local_optimization="lm"``, the default for homographies, fundamental and essential matrices.

    Essential-matrix cases use the two-view scene in normalized camera coordinates (focal length 800 px), with every
    pixel threshold and tolerance converted by :func:`_px`.
    """

    @pytest.mark.parametrize("model_type", _LM_MODELS)
    def test_recovers_exact_model_among_outliers(self, device, dtype, model_type):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("sub-pixel checks on 600 px coordinates are below half-precision resolution")
        kp1, kp2, _, _, inliers = _scene(model_type, 200, 60, 0.0, seed=0)
        ransac = RANSAC(model_type, inl_th=_px(model_type, 1.0), seed=0)
        model, mask = ransac(kp1.to(device, dtype), kp2.to(device, dtype))
        assert model.shape == (3, 3)
        assert model.dtype == dtype
        assert model.device == kp1.to(device, dtype).device
        assert mask.shape == (200,)
        assert mask.dtype == torch.bool
        assert mask.device == model.device
        assert torch.equal(mask.cpu(), inliers)
        tolerance = _px(model_type, 1e-4 if dtype == torch.float64 else 5e-2)
        assert _model_errors(model_type, model, kp1[inliers], kp2[inliers]).max() < tolerance

    @pytest.mark.parametrize("model_type", _LM_MODELS)
    def test_mask_holds_the_inliers_of_the_returned_model(self, device, dtype, model_type):
        kp1, kp2, _, _, _ = _scene(model_type, 300, 120, 0.7, seed=1)
        kp1, kp2 = kp1.to(device, dtype), kp2.to(device, dtype)
        model, mask = RANSAC(model_type, inl_th=_px(model_type, 1.5), seed=0)(kp1, kp2)
        errors = _model_errors(model_type, model, kp1, kp2)
        # Classify the returned model on the actual input coordinates, including rounding in half precision.
        assert mask.any()
        assert torch.equal(mask.cpu(), errors <= _px(model_type, 1.5))

    def test_msac_does_not_discard_supported_candidates(self, device, dtype, monkeypatch):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("this tight-threshold regression uses float32/float64 coordinates")
        generator = torch.Generator().manual_seed(31)
        kp1 = (torch.rand(40, 2, generator=generator) * 100).to(device, dtype)
        kp2 = (torch.rand(40, 2, generator=generator) * 100).to(device, dtype)
        # Fix the sampled sets across backends: CPU and CUDA generators give different draws for the same seed.
        ransac = RANSAC("fundamental_8pt", seed=0, max_samples=256, confidence=1, inl_th=0.3)
        samples = ransac.sample(8, 40, 256, 0, device="cpu").to(device)
        monkeypatch.setattr(ransac, "sample", lambda *args, **kwargs: samples)
        # The eight highest MSAC scores belong to models supported by at most their eight-point sample.
        # A lower-scoring candidate has additional support and must remain eligible for local optimization.
        model, mask = ransac(kp1, kp2)
        assert mask.sum() > 8
        assert torch.isfinite(model).all()

    def test_failure_when_model_cast_loses_support(self, device, dtype):
        if dtype != torch.bfloat16:
            pytest.skip("the model loses consensus when rounded to bfloat16")
        kp1, kp2, _, _, _ = _scene("homography", 12, 0, 0.0, seed=1)
        model, mask = RANSAC("homography", seed=0, max_samples=256, inl_th=0.5)(
            kp1.to(device, dtype), kp2.to(device, dtype)
        )
        assert not mask.any()
        assert torch.equal(model, torch.zeros_like(model))

    @pytest.mark.parametrize("model_type", _LM_MODELS)
    def test_refinement_improves_on_the_minimal_model(self, device, dtype, model_type):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("sub-pixel accuracy on 600 px coordinates is below half-precision resolution")
        kp1, kp2, clean, _, inliers = _scene(model_type, 300, 90, 0.5, seed=2)
        args = kp1.to(device, dtype), kp2.to(device, dtype)
        th = _px(model_type, 1.5)
        minimal, _ = RANSAC(model_type, inl_th=th, seed=0, max_lo_iters=0, refine_iters=0)(*args)
        refined, _ = RANSAC(model_type, inl_th=th, seed=0)(*args)
        # The distance of the noise-free matches from each model: the best of the minimal models misses them by 0.2
        # to 0.4 px at 0.5 px of noise, the Levenberg-Marquardt refits on two hundred inliers by about 0.1 px.
        miss_minimal = _model_errors(model_type, minimal, kp1[inliers], clean[inliers]).mean()
        miss_refined = _model_errors(model_type, refined, kp1[inliers], clean[inliers]).mean()
        assert miss_refined < 0.75 * miss_minimal
        assert miss_refined < _px(model_type, 0.15)

    @pytest.mark.parametrize("model_type", _LM_MODELS)
    def test_no_consensus_returns_the_failure_result(self, device, dtype, model_type):
        generator = torch.Generator().manual_seed(0)
        kp1 = _to_input_units(model_type, torch.rand(40, 2, generator=generator) * 600).to(device, dtype)
        kp2 = _to_input_units(model_type, torch.rand(40, 2, generator=generator) * 600).to(device, dtype)
        # A sample's model fits its own points; at 1e-4 px no other random point is expected on an epipolar line.
        model, mask = RANSAC(model_type, inl_th=_px(model_type, 1e-4), seed=0, max_samples=512)(kp1, kp2)
        assert bool((model == 0).all())
        assert model.dtype == dtype
        assert mask.shape == (40,)
        assert mask.dtype == torch.bool
        assert not bool(mask.any())

    @pytest.mark.parametrize("model_type", _LM_MODELS)
    def test_nonfinite_correspondences_are_outliers(self, device, dtype, model_type):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("sub-pixel checks on 600 px coordinates are below half-precision resolution")
        kp1, kp2, _, _, _ = _scene(model_type, 150, 0, 0.0, seed=3)
        kp1[:3] = float("nan")
        kp2[3:6, 0] = float("inf")
        ransac = RANSAC(model_type, inl_th=_px(model_type, 1.0), seed=0)
        model, mask = ransac(kp1.to(device, dtype), kp2.to(device, dtype))
        assert torch.isfinite(model).all()
        assert not bool(mask[:6].any())
        assert bool(mask[6:].all())

    @pytest.mark.parametrize("model_type", _LM_MODELS)
    def test_seeded_call_is_reproducible_and_private(self, device, dtype, model_type):
        kp1, kp2, _, _, _ = _scene(model_type, 120, 50, 0.5, seed=4)
        kp1, kp2 = kp1.to(device, dtype), kp2.to(device, dtype)
        state = torch.get_rng_state()
        th = _px(model_type, 2.0)
        model_a, mask_a = RANSAC(model_type, inl_th=th, seed=11, max_samples=1024)(kp1, kp2)
        assert torch.equal(torch.get_rng_state(), state)
        torch.manual_seed(123)
        model_b, mask_b = RANSAC(model_type, inl_th=th, seed=11, max_samples=1024)(kp1, kp2)
        assert torch.equal(model_a, model_b)
        assert torch.equal(mask_a, mask_b)

    @pytest.mark.parametrize("score_type", ["msac", "ransac"])
    def test_score_types(self, device, dtype, score_type):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("sub-pixel checks on 600 px coordinates are below half-precision resolution")
        kp1, kp2, _, _, inliers = _planar_scene(200, 80, 0.0, seed=5)
        _, mask = RANSAC("homography", inl_th=1.0, score_type=score_type, seed=0)(
            kp1.to(device, dtype), kp2.to(device, dtype)
        )
        assert torch.equal(mask.cpu(), inliers)

    def test_half_precision_inputs(self, device, dtype):
        if dtype not in (torch.float16, torch.bfloat16):
            pytest.skip("half-precision inputs only")
        # A 10 px extent keeps bfloat16 rounding of the exact matches below inl_th; the pipeline computes in float32.
        kp1, kp2, _, _, inliers = _planar_scene(64, 16, 0.0, seed=6)
        kp1, kp2 = kp1 / 60, kp2 / 60
        kp2[:16] = torch.rand(16, 2, generator=torch.Generator().manual_seed(0), dtype=torch.float64) * 10 + 20
        model, mask = RANSAC("homography", inl_th=0.5, seed=0)(kp1.to(device, dtype), kp2.to(device, dtype))
        assert model.dtype == dtype
        assert torch.isfinite(model).all()
        assert torch.equal(mask.cpu(), inliers)

    @pytest.mark.parametrize(
        "model_type, max_samples, expected",
        [
            ("homography", 2000, [512, 1024, 464]),
            ("fundamental", 2000, [256, 512, 1024, 208]),
            ("essential", 2000, [64, 128, 256, 512, 1024, 16]),
        ],
    )
    def test_auto_batches_grow_on_cpu_and_cover_the_budget(self, device, model_type, max_samples, expected):
        if device.type != "cpu":
            pytest.skip("the CPU batch schedule")
        # confidence=1 draws the whole budget: batches double from the first one, the last is cut to the budget.
        kp1, kp2, _, _, _ = _scene(model_type, 100, 30, 0.5, seed=7)
        ransac = RANSAC(model_type, max_samples=max_samples, confidence=1.0, seed=0)
        sizes = []
        sample = ransac.sample
        ransac.sample = lambda m, n, batch, *a, _s=sample, **k: sizes.append(batch) or _s(m, n, batch, *a, **k)
        ransac(kp1.float(), kp2.float())
        assert sizes == expected

    def test_essential_auto_batches_per_device(self):
        # A five-point sample needs few draws at high inlier ratios: small first batches on every device, the CPU
        # one smallest (tuned on PhotoTourism, where a first batch of 256 doubled the time at equal accuracy).
        ransac = RANSAC("essential", max_samples=100000)
        assert ransac._lm_batch_range(100, torch.device("cpu")) == (64, 1024)
        assert ransac._lm_batch_range(100, torch.device("cuda")) == (256, 8192)
        assert ransac._lm_batch_range(100, torch.device("mps")) == (256, 8192)

    def test_explicit_batch_size_is_kept(self, device):
        kp1, kp2, _, _, _ = _planar_scene(100, 30, 0.5, seed=8)
        ransac = RANSAC("homography", batch_size=300, max_samples=1000, confidence=1.0, seed=0)
        sizes = []
        sample = ransac.sample
        ransac.sample = lambda m, n, batch, *a, _s=sample, **k: sizes.append(batch) or _s(m, n, batch, *a, **k)
        ransac(kp1.to(device, torch.float32), kp2.to(device, torch.float32))
        assert sizes == [300, 300, 300, 100]

    def test_prosac_offset_continues_the_schedule(self, device):
        # Batches of different sizes pass the number of sets drawn so far: each growth draw includes the newest
        # correspondence of its prefix, so its largest index follows the schedule from that offset.
        ransac = RANSAC("homography", max_samples=1000, prosac_sampling=True, seed=0)
        ends = ransac._prosac_schedule(4, 100, device)
        samples = ransac.sample(4, 100, 50, 3, device, offset=120)
        draws = torch.arange(121, 171, device=device)
        assert samples.amax(1).tolist() == (torch.searchsorted(ends, draws) + 3).tolist()
        # Without an offset, the batch index times the batch size is assumed, as before.
        assert torch.equal(ransac.sample(4, 100, 40, 3, device), ransac.sample(4, 100, 40, 3, device, offset=120))

    def test_prosac_finds_the_ranked_consensus(self, device, dtype):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("sub-pixel checks on 600 px coordinates are below half-precision resolution")
        # 60 of 300 matches follow the homography and are ranked first.
        kp1, kp2, _, _, inliers = _planar_scene(300, 240, 0.0, seed=9)
        kp1, kp2, inliers = kp1.flip(0), kp2.flip(0), inliers.flip(0)
        _, mask = RANSAC("homography", inl_th=1.0, prosac_sampling=True, seed=0)(
            kp1.to(device, dtype), kp2.to(device, dtype)
        )
        assert torch.equal(mask.cpu(), inliers)


class TestRANSACEssentialLevenbergMarquardt(BaseTester):
    """What is specific to essential matrices with ``local_optimization="lm"``: no normalization, unit-norm output."""

    def _skip_half(self, dtype):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("calibrated thresholds of 1e-3 are below half-precision resolution")

    @pytest.mark.parametrize("seed", [0, 2, 3])
    def test_returns_a_unit_frobenius_essential_matrix(self, device, dtype, seed):
        self._skip_half(dtype)
        kp1, kp2, _, _, _ = _scene("essential", 200, 60, 0.5, seed=seed)
        E, _ = RANSAC("essential", inl_th=_px("essential", 1.5), seed=0)(kp1.to(device, dtype), kp2.to(device, dtype))
        singular_values = torch.linalg.svdvals(E.cpu().double())
        expected = torch.tensor([2**-0.5, 2**-0.5, 0.0], dtype=torch.float64)
        self.assert_close(singular_values, expected, atol=1e-6 if dtype == torch.float64 else 1e-3, rtol=0)
        # E and -E are the same model; the sign is fixed so that equal inputs give equal outputs on every backend.
        # Without the rule, the scene of seed 2 returns a negative largest entry on the CPU in either dtype.
        assert E.flatten()[E.abs().argmax()] > 0

    @pytest.mark.parametrize("n", [6, 7, 8])
    def test_small_inputs(self, device, dtype, n):
        self._skip_half(dtype)
        kp1, kp2, _, truth, _ = _scene("essential", n, 0, 0.0, seed=3)
        E, mask = RANSAC("essential", inl_th=_px("essential", 1.0), seed=0)(
            kp1.to(device, dtype), kp2.to(device, dtype)
        )
        assert E.shape == (3, 3)
        assert mask.shape == (n,)
        # Noise-free: every correspondence is an inlier and E is the true one, up to sign.
        assert bool(mask.all())
        E = E.cpu().double()
        tolerance = 1e-9 if dtype == torch.float64 else 1e-4
        assert min(float((E - truth).norm()), float((E + truth).norm())) < tolerance

    def test_pixel_coordinates_by_mistake_stay_finite(self, device, dtype):
        self._skip_half(dtype)
        # Pixel coordinates are not a valid input for "essential", but must not produce NaN or raise.
        kp1, kp2, _, _, _ = _two_view_scene(100, 30, 0.0, seed=4)
        E, mask = RANSAC("essential", inl_th=1.0, seed=0)(kp1.to(device, dtype), kp2.to(device, dtype))
        assert torch.isfinite(E).all()
        assert mask.shape == (100,)

    @pytest.mark.parametrize("seed", [0, 1, 2])
    def test_planar_scene(self, device, dtype, seed):
        self._skip_half(dtype)
        # A calibrated plane admits multiple essential matrices with the same epipolar fit. Check the recovered
        # consensus and essential manifold, not equality to one generating motion (which depends on sampled ties).
        generator = torch.Generator().manual_seed(12)
        f64 = torch.float64
        XY = (torch.rand(120, 2, generator=generator, dtype=f64) - 0.5) * 4
        X = torch.cat([XY, (4.0 + 0.3 * XY[:, :1] - 0.2 * XY[:, 1:])], 1)
        R = axis_angle_to_rotation_matrix(torch.tensor([[0.05, -0.1, 0.02]], dtype=f64))[0]
        t = torch.tensor([1.0, 0.1, 0.2], dtype=f64)
        Y = X @ R.T + t
        kp1, kp2 = X[:, :2] / X[:, 2:], Y[:, :2] / Y[:, 2:]
        kp2[:30] = (torch.rand(30, 2, generator=generator, dtype=f64) - 0.5) * 1.2
        E, mask = RANSAC("essential", inl_th=1e-4, seed=seed)(kp1.to(device, dtype), kp2.to(device, dtype))
        assert torch.equal(mask.cpu(), torch.arange(120) >= 30)
        E = E.cpu().double()
        tolerance = 1e-9 if dtype == torch.float64 else 1e-6
        self.assert_close(
            torch.linalg.svdvals(E), E.new_tensor([0.5**0.5, 0.5**0.5, 0.0]), atol=tolerance, rtol=tolerance
        )
        error = sampson_epipolar_distance(kp1[None, 30:], kp2[None, 30:], E[None], eps=0.0)
        assert error.max() < (1e-16 if dtype == torch.float64 else 1e-10)

    def test_batch_of_one_sample(self, device, dtype):
        self._skip_half(dtype)
        kp1, kp2, _, _, inliers = _scene("essential", 60, 10, 0.0, seed=5)
        ransac = RANSAC("essential", inl_th=_px("essential", 1.0), seed=0, batch_size=1, max_samples=64)
        _, mask = ransac(kp1.to(device, dtype), kp2.to(device, dtype))
        assert mask.shape == (60,)
        assert torch.equal(mask.cpu(), inliers)


class TestRANSACLevenbergMarquardtKernels(BaseTester):
    """RANSAC's normalization and the Levenberg-Marquardt refiners it calls."""

    def _skip_half(self, dtype):
        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("the kernels run in float32 or float64")

    def test_normalize_correspondences(self, device, dtype):
        self._skip_half(dtype)
        kp1, kp2, _, _, _ = _two_view_scene(50, 0, 0.0, seed=14)
        kp1[3] = float("nan")
        kp2[7, 0] = float("inf")
        x1, x2, t1, t2, s1, s2 = _normalize_correspondences(kp1, kp2, True)
        finite = torch.ones(50, dtype=torch.bool)
        finite[[3, 7]] = False
        # Correspondences that are not finite in both images stay non-finite and do not enter the statistics.
        assert not torch.isfinite(x1[3]).all()
        assert not torch.isfinite(x2[7]).all()
        c1, c2 = kp1[finite].mean(0), kp2[finite].mean(0)
        radius = ((kp1[finite] - c1).norm(dim=1).mean() + (kp2[finite] - c2).norm(dim=1).mean()) / 2
        # One scale for both images: sqrt(2) over the mean of the two mean radii (normalize_points adds eps = 1e-8).
        expected_scale = float((radius + 1e-8) / math.sqrt(2.0))
        self.assert_close(torch.tensor([s1, s2]), torch.tensor([expected_scale, expected_scale]), rtol=1e-12, atol=0.0)
        self.assert_close(x1[finite, :2], (kp1[finite] - c1) / s1, rtol=1e-9, atol=1e-12)
        ones = torch.ones(48, 1, dtype=kp1.dtype)
        self.assert_close((t1 @ torch.cat([kp1[finite], ones], 1).T).T, x1[finite])
        self.assert_close((t2 @ torch.cat([kp2[finite], ones], 1).T).T, x2[finite])

    @pytest.mark.parametrize("model_type", ["homography", "fundamental"])
    @pytest.mark.parametrize("loss", ["cauchy", "truncated"])
    def test_refinement_reaches_a_local_minimum(self, device, dtype, model_type, loss):
        self._skip_half(dtype)
        if device.type == "mps":
            pytest.skip("the refinement kernels run in float64, which MPS does not support")
        # Noisy inliers only, refined from a perturbed ground truth: the refit's cost is below the start's and does
        # not drop along small steps in any direction of the model's manifold.
        kp1, kp2, _, truth, _ = _scene(model_type, 80, 0, 1.0, seed=13)
        x1, x2, t1, t2, s1, s2 = _normalize_correspondences(kp1, kp2, model_type != "homography")
        if model_type == "homography":
            start = t2 @ truth @ torch.linalg.inv(t1)
            refine, scale2, x2_arg = _refine_homography_lm, (2.0 / s2) ** 2, x2[:, :2]

            def errors(models):
                return _transfer_errors(models, x1, x2[:, :2])

        else:
            start = torch.linalg.inv(t2).mT @ truth @ torch.linalg.inv(t1)
            refine, scale2, x2_arg = _refine_fundamental_lm, (2.0 / s1) ** 2, x2

            def errors(models):
                return _sampson_errors(models, x1, x2)

        start = start / start.norm()
        start = start + 1e-2 * torch.randn(3, 3, generator=torch.Generator().manual_seed(0), dtype=torch.float64)
        if model_type != "homography":
            start = _rank2_projection(start[None])[0]

        def cost(models):
            r2 = errors(models)
            return (torch.log1p(r2 / scale2) if loss == "cauchy" else torch.fmin(r2, torch.tensor(scale2))).sum(1)

        refined = refine(start[None].to(device), x1.to(device), x2_arg.to(device), None, loss, scale2, 20).cpu()
        assert cost(refined) < cost(start[None])
        steps = 1e-4 * torch.randn(32, 3, 3, generator=torch.Generator().manual_seed(1), dtype=torch.float64)
        neighbours = refined + steps * refined.norm()
        if model_type != "homography":
            neighbours = _rank2_projection(neighbours)
        assert (cost(neighbours) >= cost(refined) * (1 - 1e-9)).all()


class TestRANSACScoring(BaseTester):
    @pytest.mark.parametrize("model_type", ["homography", "fundamental", "essential"])
    @pytest.mark.parametrize("score_type", ["ransac", "msac"])
    @pytest.mark.parametrize("prosac", [False, True])
    def test_score_and_support_match_full_residuals(self, device, dtype, model_type, score_type, prosac):
        from kornia.geometry.epipolar._metrics import _sampson_from_quadratic_basis, _sampson_quadratic_basis
        from kornia.geometry.homography import _transfer_basis, _transfer_from_basis

        if dtype in (torch.float16, torch.bfloat16):
            pytest.skip("RANSAC scoring uses at least float32")
        generator = torch.Generator().manual_seed(10)
        x1 = torch.rand(137, 3, generator=generator).to(device, dtype)
        x2 = torch.rand(137, 3, generator=generator).to(device, dtype)
        x1[:, 2] = x2[:, 2] = 1
        x1[0] = float("nan")
        models = torch.rand(29, 3, 3, generator=generator).to(device, dtype)
        models[0] = float("nan")
        planar = model_type == "homography"
        basis = _transfer_basis(x1, x2[:, :2]) if planar else _sampson_quadratic_basis(x1, x2)
        residual_fn = _transfer_from_basis if planar else _sampson_from_quadratic_basis
        errors = residual_fn(models, basis)
        threshold = 0.1
        ransac = RANSAC(model_type, score_type=score_type, prosac_sampling=prosac)
        expected_support = (errors <= threshold).sum(1)
        expected_scores = ransac._lm_score(errors, threshold)
        # Force several tiles, including a tail of one model, without allocating huge fixtures.
        scores, support, masks = ransac._lm_score_models(models, basis, threshold, max_residuals=137 * 7)
        self.assert_close(scores, expected_scores)
        self.assert_close(support, expected_support.to(support.dtype), rtol=0, atol=0)
        assert scores[0] == 0
        assert support[0] == 0
        if prosac:
            assert masks is not None
            self.assert_close(support, masks.sum(1).to(support.dtype), rtol=0, atol=0)
        else:
            assert masks is None

    def test_msac_does_not_mutate_residuals(self, device, dtype):
        errors = torch.tensor([[0.0, 0.25, 1.0, 2.0, float("nan"), float("inf")]], device=device, dtype=dtype)
        original = errors.clone()
        score = RANSAC()._lm_score(errors, 1.0)
        self.assert_close(score, errors.new_tensor([1.75]))
        assert torch.equal(errors.isnan(), original.isnan())
        self.assert_close(errors.nan_to_num(), original.nan_to_num(), rtol=0, atol=0)


_COMPILED_MODELS = ["homography", "fundamental", "fundamental_8pt", "essential"]
_NO_COMPILED_PROGRAM = torch_version_lt(2, 14, 0) or not dynamo_is_available()
_NO_COMPILED_PROGRAM_REASON = "RANSAC(compile=True) needs torch 2.14 or later"


class TestRANSACCompiled(BaseTester):
    """``compile=True``: the whole of ``local_optimization="lm"`` as one compiled graph.

    Every test that compiles has ``compile`` in its name, which keeps it to the dynamo CI jobs. The tests that
    compile whole programs from a cold cache are also marked ``slow``, so they run in the scheduled dynamo job
    rather than on every pull request.
    """

    def test_graph_mode_rejects_unsupported_configurations(self):
        if torch_version_lt(2, 14, 0):
            with pytest.raises(ValueError, match=r"2\.14"):
                RANSAC("homography", compile=True)
            return
        with pytest.raises(ValueError, match="local_optimization"):
            RANSAC("homography_from_linesegments", compile=True)
        with pytest.raises(ValueError, match="local_optimization"):
            RANSAC("homography", local_optimization="dlt", compile=True)
        with pytest.raises(ValueError, match="prosac"):
            RANSAC("homography", prosac_sampling=True, compile=True)
        with pytest.raises(ValueError, match="degensac"):
            RANSAC("fundamental", degensac=True, compile=True)
        # Checked before anything is compiled.
        with pytest.raises(ValueError, match="batches of at most"):
            RANSAC("homography", batch_size=1 << 21, compile=True)(torch.rand(8, 2), torch.rand(8, 2))

    @pytest.mark.slow
    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    @pytest.mark.parametrize("model_type", _COMPILED_MODELS)
    def test_compile_recovers_the_eager_estimate(self, device, dtype, model_type):
        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")
        if dtype not in (torch.float32, torch.float64):
            pytest.skip("the compiled program is checked in float32 and float64")
        kp1, kp2, _, _, inliers = _scene(model_type, 300, 120, 0.5, seed=1)
        kp1, kp2 = kp1.to(device, dtype), kp2.to(device, dtype)
        th = _px(model_type, 1.5)
        _, eager_mask = RANSAC(model_type, inl_th=th, seed=0)(kp1, kp2)
        model, mask = RANSAC(model_type, inl_th=th, seed=0, compile=True)(kp1, kp2)
        assert model.shape == (3, 3)
        assert model.dtype == dtype
        assert model.device == kp1.device
        assert mask.shape == (300,)
        assert mask.dtype == torch.bool
        assert mask.device == kp1.device
        # The mask holds the inliers of the returned model, as in eager mode.
        assert torch.equal(mask.cpu(), _model_errors(model_type, model, kp1, kp2) <= th)
        # The same algorithm with its own random stream: the same consensus up to borderline correspondences.
        assert (mask & eager_mask).sum() >= 0.98 * eager_mask.sum()
        assert (mask.cpu() & ~inliers).sum() <= 2
        assert (mask.cpu() & inliers).sum() >= 0.9 * inliers.sum()

    @pytest.mark.slow
    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    @pytest.mark.parametrize("artifact", ["0", "1"])
    @pytest.mark.parametrize("model_type", _COMPILED_MODELS)
    def test_compile_one_graph_for_every_input(self, monkeypatch, artifact, device, model_type):
        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")
        from torch._dynamo.utils import counters

        from kornia.geometry import _ransac_program

        # A fresh program per parametrization: with the on-disk artifact, a guard that an input violates raises.
        monkeypatch.setenv("KORNIA_RANSAC_AOT", artifact)
        monkeypatch.setattr(_ransac_program, "_PROGRAMS", {})
        RANSAC(model_type, seed=0, compile=True)(
            *(kp.to(device, torch.float32) for kp in _scene(model_type, 50, 10, 0.5, 0)[:2])
        )
        graphs = counters["stats"]["unique_graphs"]
        # Sizes on both sides of inductor's 4096-element float32 reduction threshold, and every per-call number.
        for n, inl_th, confidence, max_samples in ((9, 2.0, 0.99, 64), (1500, 1.0, 1.0, 300), (5000, 3.0, 0.9, 2000)):
            kp1, kp2, _, _, _ = _scene(model_type, n, n // 4, 0.3, seed=n)
            kp1, kp2 = kp1.to(device, torch.float32), kp2.to(device, torch.float32)
            threshold = _px(model_type, inl_th)
            ransac = RANSAC(model_type, inl_th=threshold, confidence=confidence, max_samples=max_samples, compile=True)
            model, mask = ransac(kp1, kp2)
            assert mask.shape == (n,)
            assert torch.equal(mask.cpu(), _model_errors(model_type, model, kp1, kp2) <= threshold)
        assert counters["stats"]["unique_graphs"] == graphs

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_seeded_calls_repeat_and_keep_the_global_generator(self, device):
        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")
        kp1, kp2, _, _, _ = _planar_scene(200, 80, 0.5, seed=3)
        kp1, kp2 = kp1.to(device, torch.float32), kp2.to(device, torch.float32)
        ransac = RANSAC("homography", seed=7, compile=True)
        cuda_states = torch.cuda.get_rng_state_all() if torch.cuda.is_available() else []
        state = torch.get_rng_state()
        first = ransac(kp1.float(), kp2.float())
        second = ransac(kp1.float(), kp2.float())
        assert torch.equal(first[0], second[0])
        assert torch.equal(first[1], second[1])
        assert torch.equal(torch.get_rng_state(), state)
        for index, cuda_state in enumerate(cuda_states):
            assert torch.equal(torch.cuda.get_rng_state(index), cuda_state)

    @pytest.mark.slow
    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_seeded_calls_are_thread_safe(self):
        """Concurrent seeded estimators use private streams and do not perturb another thread's generator."""
        points = torch.rand(32, 2, generator=torch.Generator().manual_seed(0)) * 100

        def run(seed):
            return RANSAC(
                "homography", batch_size=32, max_samples=32, max_lo_iters=0, refine_iters=0, compile=True, seed=seed
            )(points, points)[0]

        expected = run(7)
        torch.manual_seed(123)
        unrelated_expected = torch.rand(32)
        torch.manual_seed(123)

        with ThreadPoolExecutor(max_workers=4) as executor:
            first = executor.submit(run, 7)
            unrelated = executor.submit(torch.rand, 32)
            second = executor.submit(run, 7)
            first, unrelated, second = first.result(), unrelated.result(), second.result()
        assert torch.equal(first, expected)
        assert torch.equal(second, expected)
        assert torch.equal(unrelated, unrelated_expected)

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    @pytest.mark.parametrize("seed", [0, (1 << 63) - 1, 1 << 63, (1 << 64) - 1])
    def test_compile_preserves_full_generator_seed_domain(self, monkeypatch, seed):
        from kornia.geometry import _ransac_program

        captured = []

        def load(key, inputs):
            captured.append(inputs[-1])
            return lambda *args: (torch.zeros(3, 3), torch.zeros(len(args[0]), dtype=torch.bool))

        monkeypatch.setattr(_ransac_program, "load_program", load)
        points = torch.rand(8, 2)
        RANSAC("homography", compile=True, seed=seed)(points, points)
        expected = ((seed + (1 << 63)) % (1 << 64)) - (1 << 63)
        assert captured[0].item() == expected

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    @pytest.mark.parametrize("seed", [True, 1.2])
    def test_compile_rejects_non_integer_seeds_before_compilation(self, monkeypatch, seed):
        from kornia.geometry import _ransac_program

        monkeypatch.setattr(
            _ransac_program, "load_program", lambda *args: pytest.fail("invalid seeds must not compile")
        )
        points = torch.rand(8, 2)
        with pytest.raises(TypeError, match="seed must be an integer"):
            RANSAC("homography", compile=True, seed=seed)(points, points)

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_sampler_hash_matches_its_integer_reference(self, device):
        """The int64 tensor form of lowbias32 equals the 32-bit integer hash: no signed product overflows."""
        from kornia.geometry._ransac_program import _mix32

        def lowbias32(x):
            x ^= x >> 16
            x = (x * 0x7FEB352D) & 0xFFFFFFFF
            x ^= x >> 15
            x = (x * 0x846CA68B) & 0xFFFFFFFF
            return x ^ (x >> 16)

        values = [0, 1, 0xFFFF, 0x10000, 0x7FFFFFFF, 0x80000000, 0xFFFFFFFF]
        values += torch.randint(0, 1 << 32, (2000,), generator=torch.Generator().manual_seed(0)).tolist()
        actual = _mix32(torch.tensor(values, dtype=torch.int64, device=device)).cpu().tolist()
        assert actual == [lowbias32(v) for v in values]

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_sampler_keys_are_private_reproducible_and_batch_independent(self, device):
        """A sample's keys are a hash of the seed and the sample's index alone.

        No generator is involved, so seeded calls leave every global generator untouched; batch boundaries do not change
        the stream; CPU and accelerators draw identical keys; and calls whose seeds differ by a batch offset or by
        ``2**32`` do not share samples.
        """
        from kornia.geometry._ransac_program import _uniform_keys

        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")

        def keys(seed, drawn, batch=4, target=device):
            return _uniform_keys(torch.tensor(seed), torch.tensor(drawn), batch, 8, target)

        cuda_states = torch.cuda.get_rng_state_all() if torch.cuda.is_available() else []
        state = torch.get_rng_state()
        for seed in [0, (1 << 63) - 1, -(1 << 63), -1]:
            first = keys(seed, 0)
            assert first.dtype == torch.float64
            assert first.shape == (4, 8)
            assert bool(((first >= 0) & (first < 1)).all())
            assert torch.equal(first, keys(seed, 0))
            assert torch.equal(first.cpu(), keys(seed, 0, target=torch.device("cpu")))
        assert torch.equal(torch.get_rng_state(), state)
        for index, cuda_state in enumerate(cuda_states):
            assert torch.equal(torch.cuda.get_rng_state(index), cuda_state)
        assert torch.equal(keys(7, 0, 256), torch.cat([keys(7, 0, 128), keys(7, 128, 128)]))
        assert not torch.equal(keys(0, 128), keys(128, 0))
        assert not torch.equal(keys(0, 0), keys(1 << 32, 0))
        assert len({keys(seed, 0, 1)[0, 0].item() for seed in range(256)}) == 256

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_sampler_draws_uniform_subsets(self, device):
        """Floyd's algorithm, which the program uses on every device: distinct indices, every 4-subset of 10 equally
        likely (chi-square over the 210 subsets, 209 degrees of freedom, far below 4.5 standard deviations)."""
        from kornia.geometry._ransac_program import _draw_samples

        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")
        draws = 105_000
        samples = _draw_samples(4, 10, draws, device, torch.tensor(5), torch.tensor(0)).cpu()
        assert samples.shape == (draws, 4)
        assert samples.min() >= 0
        assert samples.max() < 10
        ordered = samples.sort(1).values
        assert (ordered[:, 1:] != ordered[:, :-1]).all()
        _, counts = (ordered * torch.tensor([1000, 100, 10, 1])).sum(1).unique(return_counts=True)
        assert len(counts) == math.comb(10, 4)
        expected = draws / math.comb(10, 4)
        assert ((counts - expected) ** 2 / expected).sum() < 209 + 4.5 * math.sqrt(2 * 209)

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_normalizes_autocast_and_keys_ambient_guards(self, monkeypatch):
        """Artifact guards from ambient defaults do not collide, and caller autocast cannot alter a program."""
        from kornia.geometry import _ransac_program

        seen = []

        def load(key, inputs):
            seen.append(key)

            def program(*args):
                return torch.zeros(3, 3), torch.zeros(len(args[0]), dtype=torch.bool)

            return program

        monkeypatch.setattr(_ransac_program, "load_program", load)
        points = torch.rand(16, 2)
        estimator = RANSAC("homography", compile=True, seed=0)
        original_dtype, original_threads = torch.get_default_dtype(), torch.get_num_threads()
        changed_threads = 1 if original_threads != 1 else 2
        try:
            with torch.autocast("cpu", dtype=torch.bfloat16):
                with _ransac_program._compiled_autocast_disabled():
                    assert not torch.is_autocast_enabled("cpu")
                    assert not torch.is_autocast_enabled("cuda")
                estimator(points, points)
            torch.set_default_dtype(torch.float64)
            torch.set_num_threads(changed_threads)
            estimator(points, points)
        finally:
            torch.set_default_dtype(original_dtype)
            torch.set_num_threads(original_threads)
        assert seen[0][-3:] == (original_threads, original_dtype, str(torch.get_default_device()))
        assert seen[1][-3:] == (changed_threads, torch.float64, str(torch.get_default_device()))

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_explicit_cpu_controls_ignore_default_device(self, monkeypatch):
        from kornia.geometry import _ransac_program

        captured = []

        def load(key, inputs):
            captured.append((key, inputs))
            return lambda *args: (torch.zeros(3, 3), torch.zeros(len(args[0]), dtype=torch.bool))

        monkeypatch.setattr(_ransac_program, "load_program", load)
        points = torch.rand(8, 2)
        with default_device("meta"):
            RANSAC("homography", compile=True, seed=0)(points, points)
        assert captured[0][0][-1] == "meta"
        assert all(control.device.type == "cpu" for control in captured[0][1][2:])

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_caps_cpu_scoring_batches_without_changing_budget(self, monkeypatch):
        """Large explicit batches are split before their candidate-by-correspondence score matrix grows unbounded."""
        from kornia.geometry import _ransac_program

        captured = []

        def load(key, inputs):
            captured.append(inputs)
            return lambda *args: (torch.zeros(3, 3), torch.zeros(len(args[0]), dtype=torch.bool))

        monkeypatch.setattr(_ransac_program, "load_program", load)
        num_tc, budget = 100_000, 1_000_000
        RANSAC("homography", batch_size=budget, max_samples=budget, compile=True)(
            torch.rand(num_tc, 2), torch.rand(num_tc, 2)
        )
        # Homographies have one candidate per sample, so the limit is exactly the residual cap divided by N.
        expected = ransac_module._COMPILED_CPU_SCORE_RESIDUALS // num_tc
        assert captured[0][4].item() == budget
        assert captured[0][5].item() == captured[0][6].item() == expected

    @pytest.mark.slow
    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_cpu_score_cap_runs_explicit_confidence_one_budget(self):
        # This crosses 2**22 residuals at an explicit batch of 256, so CPU compilation splits it into scoring-safe
        # batches. confidence=1 makes the requested sample budget observable independent of consensus quality.
        count, budget = (1 << 15) + 1, 256
        generator = torch.Generator().manual_seed(0)
        kp1 = torch.rand(count, 2, generator=generator) * 100
        kp2 = kp1 * 1.1 + 5
        model, mask = RANSAC(
            "homography",
            batch_size=budget,
            max_samples=budget,
            confidence=1.0,
            max_lo_iters=0,
            refine_iters=0,
            seed=0,
            compile=True,
        )(kp1, kp2)
        assert torch.isfinite(model).all()
        assert mask.shape == (count,)
        assert mask.sum() == count

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    @pytest.mark.parametrize("error_type", [AssertionError, RuntimeError])
    def test_compile_artifact_guard_rejection_recovers_with_traced_program(self, error_type):
        from kornia.geometry._ransac_program import _artifact_or_traced

        calls = {"artifact": 0, "traced": 0}

        def artifact(*args):
            calls["artifact"] += 1
            raise error_type("GuardManager rejected ambient dispatch state")

        def traced(*args):
            calls["traced"] += 1
            return torch.zeros(3, 3), torch.zeros(len(args[0]), dtype=torch.bool)

        program = _artifact_or_traced(artifact, traced)
        points = torch.rand(8, 2)
        with pytest.warns(UserWarning, match="artifact was incompatible"):
            first = program(points)
        second = program(points)
        assert calls == {"artifact": 1, "traced": 2}
        assert torch.equal(first[0], second[0])
        assert torch.equal(first[1], second[1])

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_artifact_runtime_error_propagates(self):
        from kornia.geometry._ransac_program import _artifact_or_traced

        def artifact(*args):
            raise RuntimeError("a compiled kernel failed")

        def traced(*args):
            pytest.fail("a runtime kernel failure must not be replayed through the traced program")

        with pytest.raises(RuntimeError, match="kernel failed"):
            _artifact_or_traced(artifact, traced)(torch.rand(8, 2))

    @pytest.mark.slow
    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    @pytest.mark.parametrize("artifact", ["0", "1"])
    def test_compile_reuses_program_across_inference_contexts(self, monkeypatch, artifact, device):
        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")
        from torch._dynamo.utils import counters

        from kornia.geometry import _ransac_program

        monkeypatch.setenv("KORNIA_RANSAC_AOT", artifact)
        monkeypatch.setattr(_ransac_program, "_PROGRAMS", {})
        kp1 = torch.rand(100, 2, generator=torch.Generator().manual_seed(0)) * 100
        kp2 = kp1 * 1.1 + 5
        kp1, kp2 = kp1.to(device), kp2.to(device)
        estimator = RANSAC("homography", seed=0, compile=True)
        expected = estimator(kp1, kp2)
        # The compiled program disables both autocast dispatch keys internally, so it reuses the same graph here.
        autocast_dtype = torch.float16 if device.type == "cuda" else torch.bfloat16
        with torch.autocast(device.type, dtype=autocast_dtype):
            actual = estimator(kp1, kp2)
        self.assert_close(actual[0], expected[0], rtol=0, atol=0)
        assert torch.equal(actual[1], expected[1])
        graphs = counters["stats"]["unique_graphs"]
        with torch.inference_mode():
            inference_kp1, inference_kp2 = kp1.clone(), kp2.clone()
            for points in ((kp1, kp2), (inference_kp1, inference_kp2)):
                actual = estimator(*points)
                self.assert_close(actual[0], expected[0], rtol=0, atol=0)
                assert torch.equal(actual[1], expected[1])
        # Inference tensors can also arrive from a caller that already left its inference context.
        actual = estimator(inference_kp1, inference_kp2)
        self.assert_close(actual[0], expected[0], rtol=0, atol=0)
        # A differentiable/noncontiguous input must not invalidate an artifact traced from detached inputs.
        actual = estimator(kp1.T.contiguous().T.requires_grad_(), kp2.T.contiguous().T.requires_grad_())
        self.assert_close(actual[0], expected[0], rtol=0, atol=0)
        assert counters["stats"]["unique_graphs"] == graphs
        if artifact == "1":
            # Exercise the disk load, as well as reuse of the in-memory program.
            monkeypatch.setattr(_ransac_program, "_PROGRAMS", {})
            with torch.inference_mode():
                actual = estimator(inference_kp1, inference_kp2)
            self.assert_close(actual[0], expected[0], rtol=0, atol=0)
            assert counters["stats"]["unique_graphs"] == graphs

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_no_consensus_returns_the_failure_result(self, device):
        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")
        # Every sample maps a triangle onto a single point: sample_is_valid_for_homography rejects them all.
        points1 = (10.0 * torch.rand(16, 2, generator=torch.Generator().manual_seed(123))).to(device)
        points2 = torch.full((16, 2), 5.0)
        for compile in (False, True):
            model, mask = RANSAC("homography", inl_th=0.5, seed=0, compile=compile)(points1, points2.to(device))
            assert torch.equal(model, torch.zeros(3, 3, device=device))
            assert not mask.any()
            # A minimal sample alone is never a consensus.
            model, mask = RANSAC("homography", seed=0, compile=compile)(points1[:4], 2 * points1[:4])
            assert torch.equal(model, torch.zeros(3, 3, device=device))
            assert not mask.any()

    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_non_finite_correspondences_are_never_inliers(self, device):
        if device.type not in ("cpu", "cuda"):
            pytest.skip("the compiled program supports CPU and CUDA")
        kp1, kp2, _, _, inliers = _planar_scene(200, 40, 0.3, seed=4)
        kp1, kp2 = kp1.to(device, torch.float32), kp2.to(device, torch.float32)
        kp1[50], kp2[60, 1], kp2[70, 0] = float("nan"), float("inf"), float("-inf")
        _, mask = RANSAC("homography", seed=0, compile=True)(kp1, kp2)
        assert not mask[[50, 60, 70]].any()
        expected = inliers.to(device).clone()
        expected[[50, 60, 70]] = False
        assert (mask & expected).sum() >= 0.95 * expected.sum()
        assert (mask & ~expected).sum() == 0

    @pytest.mark.slow
    @pytest.mark.skipif(_NO_COMPILED_PROGRAM, reason=_NO_COMPILED_PROGRAM_REASON)
    def test_compile_artifact_serves_a_new_process(self, tmp_path):
        script = (
            "import torch\n"
            "from torch._dynamo.utils import counters\n"
            "from kornia.geometry import RANSAC\n"
            "torch.set_num_threads(int(__import__('os').environ['RANSAC_TEST_THREADS']))\n"
            "torch.set_default_dtype(getattr(torch, __import__('os').environ['RANSAC_TEST_DTYPE']))\n"
            "g = torch.Generator().manual_seed(0)\n"
            "kp1 = torch.rand(300, 2, generator=g, dtype=torch.float32) * 600\n"
            "kp2 = kp1 * 1.1 + 5\n"
            "model, mask = RANSAC('homography', seed=0, max_lo_iters=0, refine_iters=0, compile=True)(kp1, kp2)\n"
            "print(int(mask.sum()), counters['stats']['unique_graphs'])\n"
        )
        env = {**os.environ, "TORCHINDUCTOR_CACHE_DIR": str(tmp_path), "KORNIA_RANSAC_AOT": "1"}
        outputs = []
        # The first process writes the float32/default one-thread artifact. A different ambient dtype and thread
        # count must not load an artifact guarded for that process; the third process proves its own key is reusable.
        for threads, dtype in ((1, "float32"), (2, "float64"), (2, "float64")):
            result = subprocess.run(  # noqa: S603 - fixed script and interpreter; no shell or external input.
                [sys.executable, "-c", script],
                env={**env, "RANSAC_TEST_THREADS": str(threads), "RANSAC_TEST_DTYPE": dtype},
                capture_output=True,
                text=True,
                check=True,
                timeout=600,
            )
            outputs.append(result.stdout.split())
        assert list((tmp_path / "kornia_ransac").glob("*.bin"))
        assert [output[0] for output in outputs] == ["300"] * 3
        assert int(outputs[0][1]) >= 1
        assert int(outputs[1][1]) >= 1
        assert outputs[2][1] == "0"


class TestRANSACDegensacOptions(BaseTester):
    @pytest.mark.parametrize(
        "model_type", ["fundamental", "fundamental_7pt", "fundamental_8pt", "homography", "essential"]
    )
    def test_default_is_off(self, model_type):
        assert RANSAC(model_type).degensac is False

    @pytest.mark.parametrize("model_type", ["fundamental", "fundamental_7pt"])
    def test_explicit_opt_in(self, model_type):
        assert RANSAC(model_type, degensac=True).degensac is True

    def test_default_is_off_with_dlt(self):
        assert RANSAC("fundamental", local_optimization="dlt").degensac is False

    @pytest.mark.parametrize(
        ("model_type", "local_optimization"),
        [
            ("homography", None),
            ("essential", None),
            ("fundamental_8pt", None),
            ("fundamental", "dlt"),
            ("homography_from_linesegments", None),
        ],
    )
    def test_true_rejects_unsupported(self, model_type, local_optimization):
        with pytest.raises(ValueError, match="degensac"):
            RANSAC(model_type, local_optimization=local_optimization, degensac=True)

    def test_rejects_non_bool(self):
        with pytest.raises(ValueError, match="degensac"):
            RANSAC("fundamental", degensac=1)

    @pytest.mark.parametrize("model_type", ["fundamental", "fundamental_8pt", "homography", "essential"])
    def test_minimal_models_omit_unused_origins(self, model_type, device, dtype):
        ransac = RANSAC(model_type)
        work = torch.float64 if dtype == torch.float64 else torch.float32
        x1 = torch.cat([torch.rand(8, ransac.minimal_sample_size, 2), torch.ones(8, ransac.minimal_sample_size, 1)], -1)
        x2 = torch.cat([torch.rand_like(x1[..., :2]), torch.ones_like(x1[..., :1])], -1)
        x1, x2 = x1.to(device, work), x2.to(device, work)
        models, origin = ransac._lm_minimal_models(x1, x2)
        assert origin is None
        tracked_models, tracked_origin = ransac._lm_minimal_models(x1, x2, track_origins=True)
        assert tracked_origin is not None
        assert len(tracked_origin) == len(models)
        assert torch.equal(models.isnan(), tracked_models.isnan())
        self.assert_close(models.nan_to_num(), tracked_models.nan_to_num(), atol=0, rtol=0)

    def test_raw_record_setters_are_draw_order_prefix_maxima(self):
        scores = torch.tensor([0.5, 2.0, 1.0, 3.0, 3.0, -1.0, 4.0])
        assert RANSAC._raw_record_setters(scores, 1.0) == [1, 3, 6]
        assert RANSAC._raw_record_setters(scores, 5.0) == []
        assert RANSAC._raw_record_setters(scores, -1.0) == [0, 1, 3, 6]

    @pytest.mark.parametrize("model_type", ["fundamental", "fundamental_8pt", "homography", "essential"])
    def test_lm_minimal_models_report_their_sample(self, model_type, device, dtype):
        # Every model fits its own sample far better than the other fifteen, so the reported row identifies it; the
        # eight-point model is not exact on its sample after the rank-2 projection, hence argmin rather than zero.
        work = torch.float64 if dtype == torch.float64 else torch.float32
        ransac = RANSAC(model_type)
        generator = torch.Generator().manual_seed(0)
        m = ransac.minimal_sample_size
        x1 = torch.cat([torch.rand(16, m, 2, generator=generator), torch.ones(16, m, 1)], -1)
        x2 = torch.cat([torch.rand(16, m, 2, generator=generator), torch.ones(16, m, 1)], -1)
        models, rows = ransac._lm_minimal_models(x1.to(device, work), x2.to(device, work), track_origins=True)
        assert rows is not None
        assert rows.shape == (len(models),)
        assert rows.dtype == torch.long
        assert bool((rows[1:] >= rows[:-1]).all())  # draw order
        finite = torch.isfinite(models).flatten(1).all(1)
        models, rows = models[finite].cpu().double(), rows[finite].cpu()
        s1, s2 = x1.double(), x2.double()
        if model_type == "homography":
            mapped = torch.einsum("mij,snj->msni", models, s1)
            residual = (mapped[..., :2] / mapped[..., 2:] - s2[None, ..., :2]).norm(dim=-1).amax(-1)
        else:
            residual = torch.einsum("sni,mij,snj->msn", s2, models, s1).abs().amax(-1)
        assert float((residual.argmin(1) == rows).double().mean()) >= 0.9


def _degensac_inputs(kp1, kp2, inl_th, device, work):
    """The normalized inputs ``_forward_lm`` builds for a seven-point fundamental matrix."""
    x1_host, x2_host, t1, t2, s1, _ = _normalize_correspondences(kp1.cpu().double(), kp2.cpu().double(), True)
    x1, x2 = x1_host.to(device, work), x2_host.to(device, work)
    return x1, x2, x1_host, x2_host, t1, t2, _sampson_quadratic_basis(x1, x2), (inl_th / s1) ** 2


def _degenerate_sample(labels, generator):
    """Five plane correspondences and two outliers, an H-degenerate seven-point sample."""
    plane = (labels == 0).nonzero().flatten().cpu()
    outliers = (labels == 2).nonzero().flatten().cpu()
    return torch.cat(
        [
            plane[torch.randperm(len(plane), generator=generator)[:5]],
            outliers[torch.randperm(len(outliers), generator=generator)[:2]],
        ]
    )


def _skip_half(dtype):
    if dtype in (torch.float16, torch.bfloat16):
        pytest.skip("the scene's pixel coordinates quantize at the noise scale in half precision")


def _off_plane_error(F, clean1, clean2):
    """Median Sampson distance, in pixels, of the noise-free off-plane correspondences to F, on the host."""
    points1, points2 = clean1[None].cpu().double(), clean2[None].cpu().double()
    return float(sampson_epipolar_distance(points1, points2, F[None].cpu().double(), squared=False)[0].median())


def _explains_off_plane(F, clean1, clean2):
    """Whether F puts the noise-free off-plane correspondences within 2 px of their epipolar lines (median)."""
    return bool(F.abs().sum() > 0) and _off_plane_error(F, clean1, clean2) < 2.0


class TestRANSACDegensacRecovery(BaseTester):
    @pytest.mark.parametrize("max_lo_iters", [0, 5])
    def test_degenerate_samples_are_recovered(self, device, dtype, max_lo_iters):
        # Every sample the degeneracy test flags must come back as a model that explains the off-plane geometry;
        # a sample it does not flag must come back as None.
        _skip_half(dtype)
        work = torch.float64 if dtype == torch.float64 else torch.float32
        kp1, kp2, labels, clean1, clean2 = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        ransac = RANSAC("fundamental", inl_th=1.0, max_lo_iters=max_lo_iters, seed=0, degensac=True)
        x1, x2, x1_host, x2_host, t1, t2, basis, threshold = _degensac_inputs(kp1, kp2, 1.0, device, work)
        generator = torch.Generator().manual_seed(1)
        flagged = 0
        for _ in range(10):
            sample = _degenerate_sample(labels, generator)
            models, _ = ransac._lm_minimal_models(x1[sample.to(device)][None], x2[sample.to(device)][None])
            models = models[torch.isfinite(models).flatten(1).all(1)]
            scores, counts, _ = ransac._lm_score_models(models, basis, threshold)
            model = models[int(scores.masked_fill(counts <= 7, -1.0).argmax())]
            result = ransac._degensac_recover(
                model, sample.to(device), x1, x2, x1_host, x2_host, basis, threshold, torch.Generator().manual_seed(2)
            )
            degenerate = _h_degenerate_sample(model.cpu().double(), x1_host[sample], x2_host[sample], 3 * threshold)
            if degenerate is None:
                assert result is None
                continue
            flagged += 1
            assert result is not None
            out_models, scores, counts, masks = result
            assert masks is None
            # One model per recovery, as Chum's rFtH returns one: near-duplicates from one search would crowd the
            # eight-model pool (on the loftr_fund pair they cost test_real_dirty_7pt its margin in 2 of 20 seeds).
            assert out_models.shape == (1, 3, 3)
            assert scores.shape == counts.shape == (1,)
            best = out_models[int(scores.argmax())].cpu().double()
            assert _explains_off_plane(t2.mT @ best @ t1, clean1.cpu(), clean2.cpu())
        assert flagged >= 5

    def test_record_checks_are_batched(self, device, dtype, monkeypatch):
        _skip_half(dtype)
        sizes = []
        original = ransac_module._h_degenerate_samples

        def check(models, *args):
            sizes.append(len(models))
            return original(models, *args)

        def scalar_check(*args):
            raise AssertionError("a record's already batched degeneracy test must not run again")

        monkeypatch.setattr(ransac_module, "_h_degenerate_samples", check)
        monkeypatch.setattr(ransac_module, "_h_degenerate_sample", scalar_check)
        kp1, kp2, _, clean1, clean2 = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        F, _ = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=True)(kp1, kp2)
        assert sizes
        assert max(sizes) > 1
        assert _explains_off_plane(F.cpu(), clean1.cpu(), clean2.cpu())

    @pytest.mark.parametrize("score_type", ["msac", "ransac"])
    def test_batched_recovery_matches_scalar_checks(self, device, dtype, score_type, monkeypatch):
        _skip_half(dtype)
        kp1, kp2, _, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, 5, device=device, dtype=dtype)
        estimator = RANSAC("fundamental", inl_th=1.0, seed=5, degensac=True, score_type=score_type)
        batched = estimator(kp1, kp2)

        def scalar_checks(models, x1, x2, threshold):
            return [_h_degenerate_sample(f, a, b, threshold) for f, a, b in zip(models, x1, x2)]

        monkeypatch.setattr(ransac_module, "_h_degenerate_samples", scalar_checks)
        scalar = estimator(kp1, kp2)
        assert torch.equal(batched[0], scalar[0])
        assert torch.equal(batched[1], scalar[1])

    def test_unseeded_recoveries_leave_the_global_generator(self, device, dtype):
        # The minimal samples of an unseeded call come from the global generator. Recoveries drawing from it too
        # would shift every later sample, so an unseeded call with a recovery would sample a different sequence than
        # degensac=False (on the loftr_fund pair: 9 of 20 global seeds with 2+ gross errors instead of 5).
        _skip_half(dtype)
        work = torch.float64 if dtype == torch.float64 else torch.float32
        kp1, kp2, labels, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        ransac = RANSAC("fundamental", inl_th=1.0, degensac=True)
        x1, x2, x1_host, x2_host, _, _, basis, threshold = _degensac_inputs(kp1, kp2, 1.0, device, work)
        generator = torch.Generator().manual_seed(4)
        samples = torch.stack([_degenerate_sample(labels, generator) for _ in range(8)]).to(device)
        models, rows = ransac._lm_minimal_models(x1[samples], x2[samples], track_origins=True)
        assert rows is not None
        scores, counts, _ = ransac._lm_score_models(models, basis, threshold)
        scores = scores.masked_fill(counts <= 7, -1.0)
        state = torch.get_rng_state()
        recoveries = ransac._degensac_batch(
            models, samples[rows], scores, -1.0, x1, x2, x1_host, x2_host, basis, threshold, 0
        )
        assert recoveries  # the recovery drew
        assert torch.equal(torch.get_rng_state(), state)

    def test_unseeded_recovery_draws_follow_the_samples(self, device, dtype, monkeypatch):
        # An unseeded call seeds its private recovery generator from the sample that triggered the recovery, which
        # comes from the global generator: the draws differ between calls without advancing it. A constant seed
        # would repeat the same draws, and so the same luck, on every unseeded call.
        _skip_half(dtype)
        seeds = []
        original = RANSAC._degensac_recover

        def spy(
            self,
            model,
            sample,
            x1,
            x2,
            x1_host,
            x2_host,
            basis,
            threshold,
            generator,
            seen_planes=None,
            homography=None,
        ):
            seeds.append(generator.initial_seed())
            return original(
                self, model, sample, x1, x2, x1_host, x2_host, basis, threshold, generator, seen_planes, homography
            )

        monkeypatch.setattr(RANSAC, "_degensac_recover", spy)
        kp1, kp2, _, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        per_call = []
        for global_seed in (0, 1):
            seeds.clear()
            torch.manual_seed(global_seed)
            RANSAC("fundamental", inl_th=1.0, degensac=True)(kp1, kp2)
            per_call.append(set(seeds))
        assert per_call[0]
        assert per_call[1]
        assert per_call[0] != per_call[1]

    def test_repeated_plane_is_searched_once(self, device, dtype, monkeypatch):
        # Every degenerate record setter of a dominant plane finds the same plane (the refined planes of repeated
        # recoveries have Jaccard index 0.997-1.0 on these scenes), and nine searches of it per call made DEGENSAC
        # eleven times slower than plain RANSAC; VSAC skips a model whose inliers repeat (Jaccard index 0.95).
        _skip_half(dtype)
        work = torch.float64 if dtype == torch.float64 else torch.float32
        kp1, kp2, labels, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        ransac = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=True)
        x1, x2, x1_host, x2_host, _, _, basis, threshold = _degensac_inputs(kp1, kp2, 1.0, device, work)
        generator = torch.Generator().manual_seed(4)
        samples = torch.stack([_degenerate_sample(labels, generator) for _ in range(8)]).to(device)
        models, rows = ransac._lm_minimal_models(x1[samples], x2[samples], track_origins=True)
        assert rows is not None
        scores, counts, _ = ransac._lm_score_models(models, basis, threshold)
        scores = scores.masked_fill(counts <= 7, -1.0)
        records = [
            record
            for record in RANSAC._raw_record_setters(scores.cpu(), -1.0)
            if _h_degenerate_sample(
                models[record].cpu().double(),
                x1_host[samples[rows][record].cpu()],
                x2_host[samples[rows][record].cpu()],
                3 * threshold,
            )
            is not None
        ]
        assert len(records) >= 2  # several degenerate record setters of the same plane
        calls = []
        original = ransac_module._plane_parallax_search
        monkeypatch.setattr(ransac_module, "_plane_parallax_search", lambda *a: calls.append(1) or original(*a))
        recoveries = ransac._degensac_batch(
            models, samples[rows], scores, -1.0, x1, x2, x1_host, x2_host, basis, threshold, 0
        )
        assert len(calls) == 1
        assert len(recoveries) == 1

    def test_dominant_plane_is_refined_once_per_call(self, device, dtype, monkeypatch):
        # A later record setter's homography is noisier than the refined plane (Jaccard index 0.03-1.0 against it at
        # N=4000), so a Jaccard test before innerH let one to five repeated refinements through per call; its inliers
        # lie inside the refined plane (98.3-100% of them in every repeat measured), which a containment test sees.
        _skip_half(dtype)
        refinements = []
        original = ransac_module._inner_homography
        monkeypatch.setattr(ransac_module, "_inner_homography", lambda *a: refinements.append(1) or original(*a))
        for seed in range(3):
            refinements.clear()
            kp1, kp2, _, _, _ = create_dominant_plane_scene(4000, 0.6, 0.95, seed, device=device, dtype=dtype)
            RANSAC("fundamental", inl_th=1.0, seed=seed, degensac=True)(kp1, kp2)
            assert len(refinements) == 1, f"seed {seed}"

    def test_dominant_plane_is_searched_at_most_twice_per_call(self, device, dtype, monkeypatch):
        _skip_half(dtype)
        calls = []
        original = ransac_module._plane_parallax_search
        monkeypatch.setattr(ransac_module, "_plane_parallax_search", lambda *a: calls.append(1) or original(*a))
        kp1, kp2, _, clean1, clean2 = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        F, _ = RANSAC("fundamental", inl_th=1.0, confidence=0.999, seed=0, degensac=True)(kp1, kp2)
        assert _explains_off_plane(F.cpu(), clean1.cpu(), clean2.cpu())
        assert 1 <= len(calls) <= 2  # one plane; nine searches before deduplication

    def _recover_once(self, max_lo_iters, score_type, scene_seed, device, dtype):
        """Recover the scene's first degenerate sample (5 plane + 2 outliers) with a fixed recovery generator."""
        work = torch.float64 if dtype == torch.float64 else torch.float32
        kp1, kp2, labels, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, scene_seed, device=device, dtype=dtype)
        x1, x2, x1_host, x2_host, _, _, basis, threshold = _degensac_inputs(kp1, kp2, 1.0, device, work)
        sample = _degenerate_sample(labels, torch.Generator().manual_seed(scene_seed)).to(device)
        ransac = RANSAC("fundamental", inl_th=1.0, score_type=score_type, max_lo_iters=max_lo_iters, degensac=True)
        models, _ = ransac._lm_minimal_models(x1[sample][None], x2[sample][None])
        models = models[torch.isfinite(models).flatten(1).all(1)]
        scores, counts, _ = ransac._lm_score_models(models, basis, threshold)
        model = models[int(scores.masked_fill(counts <= 7, -1.0).argmax())]
        generator = torch.Generator().manual_seed(999)
        return ransac._degensac_recover(model, sample, x1, x2, x1_host, x2_host, basis, threshold, generator)

    def test_refinement_never_lowers_the_recovered_score(self, device, dtype):
        # With score_type="ransac" the truncated LM can trade inliers: on this sample it took the recovered model from
        # 568 to 566. The recovery keeps the better of its raw and refined models.
        _skip_half(dtype)
        raw = self._recover_once(0, "ransac", 5, device, dtype)
        refined = self._recover_once(5, "ransac", 5, device, dtype)
        assert raw is not None
        assert refined is not None
        assert float(refined[1][0]) >= float(raw[1][0])

    def test_worse_refinement_keeps_the_raw_model(self, device, dtype, monkeypatch):
        _skip_half(dtype)
        raw = self._recover_once(0, "msac", 0, device, dtype)
        # A "refinement" that returns a scrambled model scores far below the raw one.
        monkeypatch.setattr(RANSAC, "_lm_refine", lambda self, models, *args: models.roll(1, dims=-1))
        kept = self._recover_once(5, "msac", 0, device, dtype)
        assert raw is not None
        assert kept is not None
        assert torch.equal(kept[0], raw[0])
        assert torch.equal(kept[1], raw[1])

    def test_non_degenerate_sample_returns_none(self, device, dtype):
        # Seven off-plane correspondences are not always in general position at the test's tolerance: a five-point
        # homography fit leaves two redundant constraints, and five of the first seven here fit one within 2.2 px^2
        # < 3 t. The contract is the implication: a sample the test does not flag is not recovered.
        _skip_half(dtype)
        work = torch.float64 if dtype == torch.float64 else torch.float32
        kp1, kp2, labels, _, _ = create_dominant_plane_scene(1000, 0.6, 0.5, 0, device=device, dtype=dtype)
        ransac = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=True)
        x1, x2, x1_host, x2_host, _, _, basis, threshold = _degensac_inputs(kp1, kp2, 1.0, device, work)
        off_plane = (labels == 1).nonzero().flatten().cpu()
        unflagged = 0
        for group in range(6):
            sample = off_plane[7 * group : 7 * group + 7]
            models, _ = ransac._lm_minimal_models(x1[sample.to(device)][None], x2[sample.to(device)][None])
            for model in models[torch.isfinite(models).flatten(1).all(1)]:
                if _h_degenerate_sample(model.cpu().double(), x1_host[sample], x2_host[sample], 3 * threshold) is None:
                    unflagged += 1
                    recovered = ransac._degensac_recover(
                        model, sample.to(device), x1, x2, x1_host, x2_host, basis, threshold, None
                    )
                    assert recovered is None
        assert unflagged >= 3


_SCENES = {"frontal": {}, "zoom": {"zoom": 3.0}, "skew": {"skew": 0.5}}


class TestRANSACDegensac(BaseTester):
    @pytest.mark.parametrize("scene", sorted(_SCENES))
    def test_recovers_dominant_plane(self, device, dtype, scene):
        # On main (a7d177cbf) plain seven-point RANSAC fails every one of these seeds on every scene on CPU, so the
        # explicit recovery's assertions fail there. Accelerators sample differently (MPS: plain succeeds on one
        # frontal and zoomed seed), so the plain count only asserts that the scenes stay hard for it.
        _skip_half(dtype)
        plain_failures = 0
        for seed in range(5):
            kp1, kp2, labels, clean1, clean2 = create_dominant_plane_scene(
                1000, 0.6, 0.95, seed, device=device, dtype=dtype, **_SCENES[scene]
            )
            F, mask = RANSAC("fundamental", inl_th=1.0, confidence=0.999, seed=seed, degensac=True)(kp1, kp2)
            assert _explains_off_plane(F.cpu(), clean1.cpu(), clean2.cpu()), f"seed {seed}"
            off_plane = labels == 1
            assert float((mask & off_plane).sum()) >= 0.8 * float(off_plane.sum()), f"seed {seed}"
            F_plain, _ = RANSAC("fundamental", inl_th=1.0, confidence=0.999, seed=seed, degensac=False)(kp1, kp2)
            plain_failures += int(not _explains_off_plane(F_plain.cpu(), clean1.cpu(), clean2.cpu()))
        assert plain_failures >= 3

    @pytest.mark.parametrize("score_type", ["msac", "ransac"])
    def test_both_score_types(self, device, dtype, score_type):
        _skip_half(dtype)
        kp1, kp2, _, clean1, clean2 = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        F, _ = RANSAC("fundamental", inl_th=1.0, confidence=0.999, seed=0, score_type=score_type, degensac=True)(
            kp1, kp2
        )
        assert _explains_off_plane(F.cpu(), clean1.cpu(), clean2.cpu())

    def test_never_degenerate_is_bitwise_plain(self, device, dtype, monkeypatch):
        # With the test stubbed to find no degenerate sample, the record tracking, sample rows and host transfers
        # must leave the result bit for bit the same, even where recoveries would fire.
        _skip_half(dtype)
        monkeypatch.setattr(ransac_module, "_h_degenerate_samples", lambda models, *args: [None] * len(models))
        kp1, kp2, _, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        F, mask = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=True)(kp1, kp2)
        F_plain, mask_plain = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=False)(kp1, kp2)
        assert torch.equal(F, F_plain)
        assert torch.equal(mask, mask_plain)

    def test_scene_without_plane_keeps_its_accuracy(self, device, dtype, monkeypatch):
        # Without a dominant plane, record setters are still often H-degenerate at Chum's 3 t: five of seven
        # correspondences fit one homography within 0.6-2.1 t in 5 of these 6 seeds. The recoveries then join the
        # pool, so the estimate is not bitwise the plain one, but it must explain the geometry as well.
        _skip_half(dtype)
        calls = []
        original = ransac_module._plane_parallax_search
        monkeypatch.setattr(ransac_module, "_plane_parallax_search", lambda *a: calls.append(1) or original(*a))
        # plane_fraction=0 puts every inlier at a random depth: no dominant plane. Which seeds draw an H-degenerate
        # record setter depends on the device's generator and batch sizes, not only on the scene (#6263): CPU and CUDA
        # fire on different seeds, and on some CUDA setups none of the first six does. So the first six seeds always
        # run, further seeds run until a recovery has happened, and every seed that runs must keep the accuracy.
        for seed in range(30):
            if seed >= 6 and calls:
                break
            kp1, kp2, _, clean1, clean2 = create_dominant_plane_scene(1000, 0.6, 0.0, seed, device=device, dtype=dtype)
            F, mask = RANSAC("fundamental", inl_th=1.0, seed=seed, degensac=True)(kp1, kp2)
            F_plain, mask_plain = RANSAC("fundamental", inl_th=1.0, seed=seed, degensac=False)(kp1, kp2)

            error, error_plain = _off_plane_error(F, clean1, clean2), _off_plane_error(F_plain, clean1, clean2)
            assert error <= error_plain + 0.01, f"seed {seed}"
            assert abs(int(mask.sum()) - int(mask_plain.sum())) <= 0.01 * len(mask), f"seed {seed}"
        assert calls  # the recovered path ran

    def test_recovered_incumbent_does_not_hide_later_records(self, device, dtype, monkeypatch):
        # The stub's first model outscores every raw model. A trigger tied to the incumbent's score would stop
        # testing after the first batch; the raw record keeps finding record setters in later batches.
        _skip_half(dtype)
        batches = []

        def stub(
            self,
            model,
            sample,
            x1,
            x2,
            x1_host,
            x2_host,
            basis,
            threshold,
            generator,
            seen_planes=None,
            homography=None,
        ):
            batches.append(generator.initial_seed())
            models = model[None].clone()
            huge = torch.full((1,), 1e9, dtype=x1.dtype, device=x1.device)
            return models, huge, torch.full((1,), float(len(x1)), dtype=x1.dtype, device=x1.device), None

        monkeypatch.setattr(RANSAC, "_degensac_recover", stub)
        kp1, kp2, _, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        RANSAC("fundamental", inl_th=1.0, batch_size=64, max_iter=20, confidence=1.0, seed=0, degensac=True)(kp1, kp2)
        assert len(set(batches)) >= 2

    def test_seeded_calls_are_reproducible_and_private(self, device, dtype, monkeypatch):
        _skip_half(dtype)
        kp1, kp2, _, _, _ = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)

        def device_state():
            if device.type == "cuda":
                return torch.cuda.get_rng_state(device)
            if device.type == "mps":
                return torch.mps.get_rng_state()
            return None

        calls = []
        original = ransac_module._plane_parallax_search
        monkeypatch.setattr(ransac_module, "_plane_parallax_search", lambda *a: calls.append(1) or original(*a))
        cpu_state, accelerator_state = torch.get_rng_state(), device_state()
        first = RANSAC("fundamental", inl_th=1.0, seed=3, degensac=True)(kp1, kp2)
        second = RANSAC("fundamental", inl_th=1.0, seed=3, degensac=True)(kp1, kp2)
        assert calls  # the recovery drew
        assert torch.equal(first[0], second[0])
        assert torch.equal(first[1], second[1])
        assert torch.equal(torch.get_rng_state(), cpu_state)
        if accelerator_state is not None:
            assert torch.equal(device_state(), accelerator_state)

    # Review focus 1: non-finite correspondences.
    def test_non_finite_rows_are_skipped(self, device, dtype):
        _skip_half(dtype)
        kp1, kp2, _, clean1, clean2 = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        kp1[:5] = float("nan")
        kp2[5:10] = float("inf")
        F, mask = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=True)(kp1, kp2)
        assert not bool(mask[:10].any())
        assert _explains_off_plane(F.cpu(), clean1.cpu(), clean2.cpu())

    # Review focus 2: a fully planar scene. Its off-plane set is the outliers, so the pair search runs on them and may
    # return a model consistent with the plane plus a few outliers (as Chum's code does; VSAC's DEGENSAC+ adds a
    # randomness check against that). Every model consistent with the plane is valid here: the plane must stay in.
    def test_fully_planar_scene(self, device, dtype):
        _skip_half(dtype)
        kp1, kp2, labels, _, _ = create_dominant_plane_scene(1000, 0.6, 1.0, 0, device=device, dtype=dtype)
        F, mask = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=True)(kp1, kp2)
        assert F.shape == (3, 3)
        assert bool(F.abs().sum() > 0)
        plane = labels == 0
        assert float((mask & plane).sum()) >= 0.9 * float(plane.sum())

    # Review focus 3: tiny inputs.
    @pytest.mark.parametrize("num_points", [7, 10, 20])
    def test_tiny_inputs(self, device, dtype, num_points):
        kp1, kp2, _, _, _ = create_dominant_plane_scene(num_points, 0.8, 0.9, 0, device=device, dtype=dtype)
        F, mask = RANSAC("fundamental", inl_th=1.0, seed=0, degensac=True)(kp1, kp2)
        assert F.shape == (3, 3)
        assert mask.shape == (num_points,)
        assert mask.dtype == torch.bool

    # Review focus 4: PROSAC's stopping rule takes the recovered incumbent's mask.
    def test_prosac(self, device, dtype, monkeypatch):
        # The raw degenerate incumbent already certifies itself after the first batch here, so the final model alone
        # cannot show which mask set the recovered incumbent's bound: spy on PROSAC's termination test instead.
        _skip_half(dtype)
        recovered, tested = [], []
        original_recover, original_prosac = RANSAC._degensac_recover, RANSAC._prosac_max_samples

        def spy_recover(self, *args):
            result = original_recover(self, *args)
            if result is not None:
                recovered.append(result[3][0].clone())
            return result

        def spy_prosac(self, inliers, num_inliers):
            tested.append(inliers.clone())
            return original_prosac(self, inliers, num_inliers)

        monkeypatch.setattr(RANSAC, "_degensac_recover", spy_recover)
        monkeypatch.setattr(RANSAC, "_prosac_max_samples", spy_prosac)
        kp1, kp2, labels, clean1, clean2 = create_dominant_plane_scene(1000, 0.6, 0.95, 0, device=device, dtype=dtype)
        order = torch.argsort(labels.cpu(), stable=True).to(device)  # inliers first, a best-first ranking
        F, _ = RANSAC("fundamental", inl_th=1.0, seed=0, prosac_sampling=True, degensac=True)(kp1[order], kp2[order])
        assert _explains_off_plane(F.cpu(), clean1.cpu(), clean2.cpu())
        # The recovered incumbent's stopping bound is PROSAC's test on its own inlier mask.
        assert recovered
        assert any(torch.equal(mask, inliers) for mask in recovered for inliers in tested)

    # Review focus 5: half-precision correspondences run the float64 host recovery and float32 device scoring.
    def test_half_precision_smoke(self, device):
        if device.type != "cpu":
            pytest.skip("the half-precision RANSAC legs run on CPU; accelerator half kernels are covered elsewhere")
        for dtype in (torch.float16, torch.bfloat16):
            kp1, kp2, _, _, _ = create_dominant_plane_scene(500, 0.6, 0.95, 0, device=device, dtype=dtype)
            F, mask = RANSAC("fundamental", inl_th=2.0, seed=0, degensac=True)(kp1, kp2)
            assert F.shape == (3, 3)
            assert F.dtype == dtype
            assert mask.shape == (500,)