# 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.
#

r"""Estimate homographies from point or line-segment correspondences, and score them.

A homography ``H`` ``(B, 3, 3)`` maps the first image to the second, :math:`x_2 \sim H x_1` for homogeneous
points, as ``cv2.findHomography(src, dst)`` does: the source-to-destination pixel homography that
:func:`~kornia.geometry.transform.warp_perspective` takes. Correspondences are ``(B, N, 2)`` points, or
``(B, N, 2, 2)`` segments as ``[start, end]`` pairs of ``(x, y)`` points, with the first image's argument first. The
estimators scale ``H`` to ``H[2, 2] = 1``, unless that entry is numerically zero. The errors do not depend on the
scale of ``H`` and are distances in the units of the points: squared by default for points, unsquared for segments.
:ref:`Two-view geometry <two-view-conventions>` compares these conventions with OpenCV's.

Which function to use:

- A homography from correspondences known to be inliers: :func:`find_homography_dlt` from four or more points,
  optionally weighted, and :func:`find_homography_lines_dlt` from four or more line segments.
  :func:`find_homography_dlt_iterated` and :func:`find_homography_lines_dlt_iterated` re-weight them by their
  residuals over a few iterations. Exactly four points in closed form:
  :func:`~kornia.geometry.transform.get_perspective_transform`. With outliers:
  :class:`~kornia.geometry.ransac.RANSAC`.
- How well correspondences fit a homography: :func:`oneway_transfer_error` measures in image 2 only,
  :func:`symmetric_transfer_error` in both images through ``H`` and its inverse, and
  :func:`sampson_homography_distance` is the first-order error of moving both points.
  :func:`line_segment_transfer_error_one_way` scores segments by the distance of their mapped endpoints from the
  matched line.
- Whether four correspondences keep their orientation, as two views of a plane in front of both cameras do, before
  fitting them: :func:`sample_is_valid_for_homography`. A mirroring homography fails this test.
- A two-view model other than a plane: :func:`~kornia.geometry.epipolar.find_fundamental`,
  :func:`~kornia.geometry.epipolar.find_essential`.
"""

import math
import warnings
from typing import Optional, Tuple, Union

import torch

from kornia.core.check import KORNIA_CHECK, KORNIA_CHECK_SHAPE
from kornia.core.exceptions import ShapeError
from kornia.core.utils import (
    _at_least_float32,
    _autocast_disabled,
    _extract_device_dtype,
    _symmetric_eigenvector,
    _torch_svd_in_work_dtype,
    safe_inverse_with_mask,
    safe_solve_with_mask,
)
from kornia.geometry.conversions import convert_points_from_homogeneous, convert_points_to_homogeneous
from kornia.geometry.epipolar import normalize_points, normalize_transformation
from kornia.geometry.epipolar._metrics import _shares_points
from kornia.geometry.epipolar.fundamental import _robust_loss
from kornia.geometry.linalg import _inf_where, _nonzero, _sqrt_or_zero
from kornia.geometry.solvers.homogeneous import _null_space_lu

__all__ = [
    "find_homography_dlt",
    "find_homography_dlt_iterated",
    "find_homography_lines_dlt",
    "find_homography_lines_dlt_iterated",
    "line_segment_transfer_error_one_way",
    "oneway_transfer_error",
    "sample_is_valid_for_homography",
    "sampson_homography_distance",
    "symmetric_transfer_error",
]

TupleTensor = Tuple[torch.Tensor, torch.Tensor]


def oneway_transfer_error(
    pts1: torch.Tensor, pts2: torch.Tensor, H: torch.Tensor, squared: bool = True, eps: float = 1e-8
) -> torch.Tensor:
    r"""Compute the squared transfer error in image 2 of correspondences under a homography.

    ``err = oneway_transfer_error(pts1, pts2, H)`` takes correspondences ``(B, N, 2)``, or homogeneous
    ``(B, N, 3)``, and homographies ``(B, 3, 3)`` that map the first image to the second, and returns, per
    correspondence, ``(B, N)`` with the batch dimensions broadcast, the squared distance in image 2 between ``H``
    applied to ``pts1`` and ``pts2``, in the squared units of the points; ``squared=False`` returns the distance. It
    is the residual :class:`~kornia.geometry.ransac.RANSAC` scores homographies with. It measures in image 2 only:
    for both images, use :func:`symmetric_transfer_error`, and for the first-order error of moving both points,
    :func:`sampson_homography_distance`.

    Convention:
        - One set of correspondences scored against several homographies (points with leading dimensions of
          size 1) is computed from one matrix product for all of them, in at least float32; the result matches the
          per-homography computation to roundoff.
        - ``squared=True``, the default here and in :func:`symmetric_transfer_error`, returns the squared
          distance; :func:`line_segment_transfer_error_one_way` defaults to ``squared=False``.
        - The error does not depend on the scale of ``H``, and an exact match scores exactly 0, with a zero
          gradient, with ``squared=False``. A point that ``H`` maps to infinity (:math:`w' = 0`) has error ``inf``.

    Args:
        pts1: correspondences from the left images with shape
          ``(B, N, 2)`` or ``(B, N, 3)``. If they are homogeneous, converted automatically.
        pts2: correspondences from the right images with shape
          ``(B, N, 2)`` or ``(B, N, 3)``. If they are homogeneous, converted automatically.
        H: Homographies with shape ``(B, 3, 3)``.
        squared: if True (default), the squared distance is returned.
        eps: unused; it was added to the projective denominator and inside the square root, which made the error
            depend on the scale of ``H`` and an exact match score ``sqrt(eps)`` (#4881). The singular case is
            guarded exactly instead. Accepted so that existing calls keep working.

    Returns:
        the computed distance with shape ``(B, N)``.

    See Also:
        - :func:`symmetric_transfer_error`: the image-1 error of the inverse homography added.
        - :func:`sampson_homography_distance`: the first-order error of moving both points.
        - :func:`line_segment_transfer_error_one_way`: the image-2 error of line segments.
        - :func:`~kornia.geometry.epipolar.left_to_right_epipolar_distance`: the image-2 error of a fundamental
          matrix.

    """
    KORNIA_CHECK_SHAPE(H, ["B", "3", "3"])
    if H.shape[0] >= 2 and _shares_points(pts1, pts2):
        return _oneway_transfer_error_shared_impl_(pts1, pts2, H, squared)

    if pts1.shape[-1] == 3:
        x1y1 = convert_points_from_homogeneous(pts1)
        x1 = x1y1[..., 0]
        y1 = x1y1[..., 1]
    else:
        x1 = pts1[..., :, 0]
        y1 = pts1[..., :, 1]

    if pts2.shape[-1] == 3:
        u2v2 = convert_points_from_homogeneous(pts2)
        u2 = u2v2[..., 0]
        v2 = u2v2[..., 1]
    else:
        u2 = pts2[..., :, 0]
        v2 = pts2[..., :, 1]

    # ---- Grab H entries and broadcast across N ----
    h00 = H[..., 0, 0][..., None]
    h01 = H[..., 0, 1][..., None]
    h02 = H[..., 0, 2][..., None]
    h10 = H[..., 1, 0][..., None]
    h11 = H[..., 1, 1][..., None]
    h12 = H[..., 1, 2][..., None]
    h20 = H[..., 2, 0][..., None]
    h21 = H[..., 2, 1][..., None]
    h22 = H[..., 2, 2][..., None]

    # From Hartley and Zisserman, Error in one image (4.6)
    # dist = \sum_{i} ( d(x', Hx)**2)
    # ---- Apply homography to pts1 (Euclidean) and dehomogenize ----
    # [x'; y'; w']^T = H @ [x1, y1, 1]^T
    x_num = h00 * x1 + h01 * y1 + h02
    y_num = h10 * x1 + h11 * y1 + h12
    w_den = h20 * x1 + h21 * y1 + h22

    # A point mapped to infinity (w' = 0) is singular (#4881).
    w_safe = _nonzero(w_den)
    u1in2 = x_num / w_safe
    v1in2 = y_num / w_safe

    # ---- Squared transfer error in image 2 ----
    err2 = _inf_where((u1in2 - u2).pow(2) + (v1in2 - v2).pow(2), w_den == 0)
    return err2 if squared else _sqrt_or_zero(err2)


def symmetric_transfer_error(
    pts1: torch.Tensor, pts2: torch.Tensor, H: torch.Tensor, squared: bool = True, eps: float = 1e-8
) -> torch.Tensor:
    r"""Compute the symmetric transfer error of correspondences under a homography, in both images.

    ``err = symmetric_transfer_error(pts1, pts2, H)`` takes the arguments of :func:`oneway_transfer_error` and
    returns, per correspondence, ``(B, N)``, the squared image-2 transfer error of ``H`` plus the squared image-1
    transfer error of :math:`H^{-1}`; ``squared=False`` returns the square root of that sum. A homography that is not
    invertible scores the largest finite value of the dtype. :func:`find_homography_dlt_iterated` re-weights its
    correspondences by it. For the first-order error of moving both points, use :func:`sampson_homography_distance`.

    Convention:
        - Argument order as :func:`oneway_transfer_error`.
        - As :func:`oneway_transfer_error`, the error does not depend on the scale of ``H`` and an exact match
          scores exactly 0 with ``squared=False``.

    Args:
        pts1: correspondences from the left images with shape
          ``(B, N, 2)`` or ``(B, N, 3)``. If they are homogeneous, converted automatically.
        pts2: correspondences from the right images with shape
          ``(B, N, 2)`` or ``(B, N, 3)``. If they are homogeneous, converted automatically.
        H: Homographies with shape ``(B, 3, 3)``.
        squared: if True (default), the squared distance is returned.
        eps: unused, as in :func:`oneway_transfer_error` (#4881).

    Returns:
        the computed distance with shape ``(B, N)``. Rows whose homography is not invertible
        score ``max_num``, i.e. ``torch.finfo(pts1.dtype).max``, for both values of ``squared``.

    See Also:
        - :func:`oneway_transfer_error`: the image-2 term alone.
        - :func:`sampson_homography_distance`: the first-order error of moving both points, without an inverse.
        - :func:`~kornia.geometry.epipolar.symmetrical_epipolar_distance`: the two-image error of a fundamental
          matrix.

    """
    KORNIA_CHECK_SHAPE(H, ["B", "3", "3"])
    if pts1.size(-1) == 3:
        pts1 = convert_points_from_homogeneous(pts1)

    if pts2.size(-1) == 3:
        pts2 = convert_points_from_homogeneous(pts2)

    max_num = torch.finfo(pts1.dtype).max
    # From Hartley and Zisserman, Symmetric transfer error (4.7)
    # dist = \sum_{i} (d(x, H^-1 x')**2 + d(x', Hx)**2)
    # Shield the *input* of the inverse, not its output: ``inv_ex`` backward is
    # ``-H_inv^T @ grad @ H_inv^T`` over a saved ``H_inv`` full of non-finite values, so masking the
    # result afterwards still leaves ``0 * nan = nan`` in ``H.grad``. The mask is taken on a detached
    # copy so it carries no graph, and the differentiable inverse then only ever sees a valid matrix.
    _, good_H = safe_inverse_with_mask(H.detach())
    eye = torch.eye(3, device=H.device, dtype=H.dtype).expand_as(H)
    H_safe = torch.where(good_H.view(-1, 1, 1), H, eye)
    H_inv_safe, _ = safe_inverse_with_mask(H_safe)

    there: torch.Tensor = oneway_transfer_error(pts1, pts2, H_safe, True)
    back: torch.Tensor = oneway_transfer_error(pts2, pts1, H_inv_safe, True)
    good_H_reshape: torch.Tensor = good_H.view(-1, 1).expand_as(there)

    out = there + back
    if not squared:
        out = _sqrt_or_zero(out)
    max_tensor = torch.full_like(out, max_num)
    return torch.where(good_H_reshape, out, max_tensor)


def sampson_homography_distance(
    pts1: torch.Tensor, pts2: torch.Tensor, H: torch.Tensor, squared: bool = True
) -> torch.Tensor:
    r"""Compute the Sampson distance of correspondences to a homography, to first order.

    ``d = sampson_homography_distance(pts1, pts2, H)`` takes correspondences ``(B, N, 2)``, or homogeneous
    ``(B, N, 3)``, and homographies ``(B, 3, 3)`` that map ``pts1`` to ``pts2``, and returns, per correspondence,
    ``(B, N)``, the squared Sampson distance; ``squared=False`` returns its square root. Unlike
    :func:`oneway_transfer_error` and :func:`symmetric_transfer_error`, it accounts for the noise of both points in
    one term and needs no inverse homography. For a fundamental matrix, use
    :func:`~kornia.geometry.epipolar.sampson_epipolar_distance`.

    The first-order approximation of the geometric error: the squared distance by which ``pts1`` and ``pts2``
    together must move for :math:`x_2 \sim H x_1` to hold (Hartley and Zisserman, *Multiple View Geometry*, 2nd ed.,
    section 4.2.6). With :math:`x_1 = (x, y, 1)`, :math:`x_2 = (u, v, 1)` and :math:`H x_1 = (p, q, w)`, the
    algebraic residuals :math:`\epsilon = (v w - q, p - u w)` and their Jacobian :math:`J` with respect to
    :math:`(x, y, u, v)` give :math:`d^2 = \epsilon^\top (J J^\top)^{-1} \epsilon`.

    Convention:
        - Argument order and direction as :func:`oneway_transfer_error`: ``H`` maps ``pts1`` to ``pts2``. Unlike the
          one-way transfer error, the distance accounts for noise in both images and does not depend on the scale
          of ``H``.
        - For an affine ``H`` the constraint is linear in the coordinates, and the distance is the exact geometric
          error.
        - An exact correspondence scores 0; a correspondence whose :math:`J J^\top` is singular scores ``inf``; a
          non-finite correspondence or homography gives NaN.
        - Computed in at least float32 and returned in the promoted dtype of the inputs, or in float32 when they are
          all integers.

    Args:
        pts1: points in the first image with shape ``(B, N, 2)``, or homogeneous ``(B, N, 3)``.
        pts2: points in the second image with shape ``(B, N, 2)``, or homogeneous ``(B, N, 3)``.
        H: homographies with shape ``(B, 3, 3)``. Points with a leading dimension of 1 are scored against every
            homography.
        squared: if True (default), the squared distance is returned, else the distance.

    Returns:
        the computed distance with shape ``(B, N)``.

    See Also:
        - :func:`oneway_transfer_error`: the error in image 2 only, with all the noise on the second point.
        - :func:`symmetric_transfer_error`: the errors of ``H`` in image 2 and of its inverse in image 1, added.
        - :func:`~kornia.geometry.epipolar.sampson_epipolar_distance`: the same first-order error for a fundamental
          matrix.

    """
    KORNIA_CHECK_SHAPE(H, ["B", "3", "3"])
    KORNIA_CHECK(pts1.shape[-1] in (2, 3) and pts2.shape[-1] in (2, 3), "points must have 2 or 3 coordinates")
    dtype = torch.promote_types(torch.promote_types(pts1.dtype, pts2.dtype), H.dtype)
    work = torch.promote_types(dtype, torch.float32)
    # Integer coordinates give a floating distance. Everything runs in at least float32, the dehomogenization too:
    # x / w of a small w overflows float16.
    out_dtype = dtype if dtype.is_floating_point else work
    pts1, pts2 = pts1.to(work), pts2.to(work)
    if pts1.shape[-1] == 3:
        finite = torch.isfinite(pts1).all(-1, keepdim=True)
        pts1 = convert_points_from_homogeneous(pts1).masked_fill(~finite, float("nan"))
    if pts2.shape[-1] == 3:
        finite = torch.isfinite(pts2).all(-1, keepdim=True)
        pts2 = convert_points_from_homogeneous(pts2).masked_fill(~finite, float("nan"))
    x, y = pts1[..., 0], pts1[..., 1]
    u, v = pts2[..., 0], pts2[..., 1]
    # The distance does not depend on the scale of H, but its quadratic is of fourth order in H: dividing by the
    # largest entry keeps tiny and huge finite scales in range. A zero H stays zero, and non-finite entries give NaN.
    H = H.to(work)
    scale = H.abs().amax(dim=(-2, -1), keepdim=True)
    h = (H / torch.where(scale > 0, scale, torch.ones_like(scale)))[..., None]
    p = h[..., 0, 0, :] * x + h[..., 0, 1, :] * y + h[..., 0, 2, :]
    q = h[..., 1, 0, :] * x + h[..., 1, 1, :] * y + h[..., 1, 2, :]
    w = h[..., 2, 0, :] * x + h[..., 2, 1, :] * y + h[..., 2, 2, :]
    e1, e2 = v * w - q, p - u * w
    # Jacobian rows over (x, y, u, v): (v h20 - h10, v h21 - h11, 0, w) and (h00 - u h20, h01 - u h21, -w, 0).
    jx1, jy1 = v * h[..., 2, 0, :] - h[..., 1, 0, :], v * h[..., 2, 1, :] - h[..., 1, 1, :]
    jx2, jy2 = h[..., 0, 0, :] - u * h[..., 2, 0, :], h[..., 0, 1, :] - u * h[..., 2, 1, :]
    a = jx1.square() + jy1.square() + w.square()
    c = jx2.square() + jy2.square() + w.square()
    b = jx1 * jx2 + jy1 * jy2
    det = a * c - b.square()
    num = c * e1.square() - 2 * b * e1 * e2 + a * e2.square()
    # A singular J J^T has no finite correction. The division takes a safe denominator inside the where, so the
    # inf branch leaves finite gradients (#4229); rounding can make the quadratic form slightly negative. NaN fails
    # every comparison below and passes through, as in oneway_transfer_error.
    d2 = num / torch.where(det > 0, det, torch.ones_like(det))
    d2 = torch.where(det <= 0, torch.full_like(det, math.inf), d2)
    d2 = torch.where(d2 < 0, torch.zeros_like(d2), d2)
    if not squared:
        positive = d2 > 0
        d2 = torch.where(positive, torch.where(positive, d2, torch.ones_like(d2)).sqrt(), d2)
    return d2.to(out_dtype)


def line_segment_transfer_error_one_way(
    ls1: torch.Tensor, ls2: torch.Tensor, H: torch.Tensor, squared: bool = False
) -> torch.Tensor:
    r"""Compute the mean distance of image-1 segment endpoints, mapped to image 2, from their lines.

    ``err = line_segment_transfer_error_one_way(ls1, ls2, H)`` takes segment correspondences ``(B, N, 2, 2)`` and
    homographies ``(B, 3, 3)`` that map the first image to the second, and returns, per correspondence, ``(B, N)``,
    the mean perpendicular distance in image 2 of the two endpoints of the image-1 segment, mapped by ``H``, from the
    line through the image-2 segment (:cite:`homolines2001`). Unlike the point errors, it is unsquared by default;
    ``squared=True`` returns its square. A zero-length image-2 segment defines no line and scores 0 up to rounding
    (up to 0.015 px in float32 for coordinates of a few hundred pixels). For point correspondences, use
    :func:`oneway_transfer_error`.

    Convention:
        - Argument order and direction as :func:`oneway_transfer_error`.
        - The image-2 line is scaled to unit :math:`(a, b)`, so the error is the mean perpendicular distance of
          the two mapped endpoints, in pixels.
        - An endpoint that ``H`` maps to infinity (:math:`w' = 0`) gives the segment the error ``inf``, as in
          :func:`oneway_transfer_error`, unless the image-2 segment has zero length; a NaN input stays NaN.

    Args:
        ls1: line segment correspondences from the left images with shape
          ``(B, N, 2, 2)``.
        ls2: line segment correspondences from the right images with shape
          ``(B, N, 2, 2)``.
        H: Homographies with shape ``(B, 3, 3)``.
        squared: if True (default is False), the squared error is returned.

    Returns:
        the computed error with shape ``(B, N)``.

    See Also:
        - :func:`oneway_transfer_error`: the image-2 error of point correspondences.
        - :func:`find_homography_lines_dlt`: the homography that fits line segment correspondences.

    """
    KORNIA_CHECK_SHAPE(H, ["B", "3", "3"])
    KORNIA_CHECK_SHAPE(ls1, ["B", "N", "2", "2"])
    KORNIA_CHECK_SHAPE(ls2, ["B", "N", "2", "2"])
    B, N = ls1.shape[:2]
    ps1, pe1 = torch.chunk(ls1, dim=2, chunks=2)
    ps2, pe2 = torch.chunk(ls2, dim=2, chunks=2)
    # The line and the distances are computed in a dtype that holds every input, and at least float32: none of H,
    # ls1 and ls2 loses precision, and in half precision neither the line's constant term, of order (pixel
    # coordinate)**2, nor H @ p overflows or rounds away. They are returned in the segments' dtype, as
    # transform_points returned the mapped points in theirs.
    out_dtype = torch.promote_types(ls1.dtype, ls2.dtype)
    work_dtype = torch.promote_types(torch.promote_types(H.dtype, out_dtype), torch.float32)
    H_work = H.to(work_dtype)
    ps2_h = convert_points_to_homogeneous(ps2).to(work_dtype)
    pe2_h = convert_points_to_homogeneous(pe2).to(work_dtype)
    ln2 = torch.linalg.cross(ps2_h, pe2_h, dim=3)
    # Scale the image-2 line to a unit (a, b) so the error is a perpendicular distance in pixels, not that
    # distance times the image-2 segment length (#4867). A zero-length segment defines no line; as before the
    # fix its error reads as zero, and the callers that need infinity guard on the segment length themselves.
    scale = ln2[..., :, :2].norm(dim=-1, keepdim=True)
    # Squeeze rather than view(B, N, ...): ls2 may have a batch of 1 against the batch of ls1 and H.
    ln2 = (ln2 / torch.where(scale > 0, scale, torch.ones_like(scale))).squeeze(-2)
    has_line = scale[..., 0, 0] > 0

    distance_start, singular_start = _line_endpoint_distance(ps1.view(B, N, 2), H_work, ln2)
    distance_end, singular_end = _line_endpoint_distance(pe1.view(B, N, 2), H_work, ln2)
    # Average and square in the working dtype, then cast: two float16 distances of 32768 have a representable mean
    # but a sum past the float16 maximum.
    error = 0.5 * (distance_start + distance_end)
    if squared:
        error = error**2
    # Set inf after squaring so no gradient flows through the inf, not even to the other, finite endpoint; a NaN
    # from the other endpoint stays NaN. A zero-length image-2 segment defines no line and keeps reading 0.
    singular = (singular_start | singular_end) & has_line & ~error.isnan()
    return _inf_where(error, singular).to(out_dtype)


def _line_endpoint_distance(
    points: torch.Tensor, H: torch.Tensor, line: torch.Tensor
) -> Tuple[torch.Tensor, torch.Tensor]:
    """Return the distances ``(B, N)`` of ``H``-mapped ``points`` from the unit image-2 ``line``, and ``w' == 0``.

    Maps without the OpenCV-style dehomogenization of :func:`transform_points`, which returns the numerator unchanged
    for ``|w'| <= 1e-8``: a point mapped to infinity (``w' = 0``) is singular, as in :func:`oneway_transfer_error`
    (#4881). The distance is ``|l . (x', y', w')| / |w'|``, so no mapped coordinate is formed that could overflow.
    """
    # A caller's autocast region would run the matrix product in half precision.
    with _autocast_disabled(H.device.type):
        mapped = convert_points_to_homogeneous(points).to(H.dtype) @ H.transpose(-2, -1)
    w = mapped[..., 2]
    return ((mapped * line).sum(-1) / _nonzero(w)).abs(), w == 0


def _line_segment_squared_distance_one_way(ls1: torch.Tensor, ls2: torch.Tensor, H: torch.Tensor) -> torch.Tensor:
    """Squared perpendicular distance, in pixels, of the mapped image-1 endpoints from the image-2 line.

    :func:`line_segment_transfer_error_one_way` returns that pixel distance directly since #4867; a zero-length
    image-2 segment defines no line, so its distance is infinite.
    """
    distance = line_segment_transfer_error_one_way(ls1, ls2, H)
    length = (ls2[..., 1, :] - ls2[..., 0, :]).norm(dim=-1)
    return torch.where(length > 0, distance.square(), torch.full_like(distance, float("inf")))


def _homography_rows(p1: torch.Tensor, points2: torch.Tensor) -> torch.Tensor:
    """DLT rows ``(..., 2N, 9)`` of homogeneous ``p1`` ``(..., N, 3)`` with unit last coordinate and ``points2``.

    Two rows per correspondence, ``[0, -p1, y2 p1]`` and ``[p1, 0, -x2 p1]``, so that ``row . vec(H) = 0`` for
    ``points2 ~ H p1`` with ``H`` row-major; only the first two coordinates of ``points2`` are read.
    """
    # DIAPO 11: https://www.uio.no/studier/emner/matnat/its/nedlagte-emner/UNIK4690/v16/forelesninger/lecture_4_3-estimating-homographies-from-feature-correspondences.pdf
    zeros = torch.zeros_like(p1)
    ax = torch.cat([zeros, -p1, points2[..., 1:2] * p1], dim=-1)
    ay = torch.cat([p1, zeros, -points2[..., 0:1] * p1], dim=-1)
    return torch.stack([ax, ay], dim=-2).flatten(-3, -2)


def _homography_design_rows(points1: torch.Tensor, points2: torch.Tensor) -> torch.Tensor:
    """DLT rows ``(..., 2N, 9)`` of correspondences ``(..., N, 2)``, as :func:`_homography_rows`.

    Each entry is the product the rows used to be written out with coordinate by coordinate, in fewer kernels.
    """
    return _homography_rows(torch.cat([points1, torch.ones_like(points1[..., :1])], dim=-1), points2)


def _four_point_homography(x1: torch.Tensor, x2: torch.Tensor) -> torch.Tensor:
    """Homographies ``(B, 3, 3)`` of unit Frobenius norm through four normalized correspondences.

    ``x1`` is homogeneous ``(B, 4, 3)`` with unit last coordinate and ``x2`` ``(B, 4, 2)`` or homogeneous. The null
    vector of :func:`_homography_rows` comes from :func:`~kornia.geometry.solvers.homogeneous._null_space_lu`, in at
    least float32. Unlike :func:`find_homography_dlt` there is no per-sample normalization, gauge solve or
    ``H[2, 2] = 1`` scaling: RANSAC's sampler normalizes once per call and scores unit-norm models.
    """
    A = _homography_rows(x1, x2)
    h = _null_space_lu(A.to(torch.promote_types(A.dtype, torch.float32)))[..., 0]
    return (h * h.square().sum(-1, keepdim=True).rsqrt()).reshape(-1, 3, 3).to(x1.dtype)


def _transfer_errors(H: torch.Tensor, x1: torch.Tensor, x2: torch.Tensor) -> torch.Tensor:
    """Squared one-way transfer errors ``(M, N)`` of homographies ``(M, 3, 3)`` on one set of correspondences.

    ``x1`` is homogeneous ``(N, 3)`` with unit last coordinate and ``x2`` ``(N, 2)``. ``H x1`` of every model is one
    ``(3M, 3) @ (3, N)`` product; the rest is :func:`oneway_transfer_error`'s formula, with its guard of ``w' = 0``.
    """
    m, n = H.shape[0], x1.shape[0]
    projected = (H.reshape(3 * m, 3) @ x1.T).view(m, 3, n)
    w = projected[:, 2]
    w_safe = _nonzero(w)
    err2 = (projected[:, 0] / w_safe - x2[:, 0]).square() + (projected[:, 1] / w_safe - x2[:, 1]).square()
    return _inf_where(err2, w == 0)


def _oneway_transfer_error_shared_impl_(
    pts1: torch.Tensor, pts2: torch.Tensor, H: torch.Tensor, squared: bool
) -> torch.Tensor:
    """One-way transfer errors of many homographies on one set of correspondences, by :func:`_transfer_errors`.

    ``pts1`` and ``pts2`` have leading dimensions of size 1; homogeneous points are dehomogenized. Half precision is
    computed in float32 and returned in the input dtype.
    """
    num_points = pts1.shape[-2]
    dtype = torch.promote_types(torch.promote_types(pts1.dtype, pts2.dtype), H.dtype)
    work = torch.promote_types(dtype, torch.float32)
    x1 = pts1.reshape(num_points, pts1.shape[-1]).to(work)
    x2 = pts2.reshape(num_points, pts2.shape[-1]).to(work)
    if x1.shape[-1] == 3:
        x1 = convert_points_from_homogeneous(x1)
    if x2.shape[-1] == 3:
        x2 = convert_points_from_homogeneous(x2)
    err2 = _transfer_errors(H.to(work), convert_points_to_homogeneous(x1), x2)
    out = err2 if squared else _sqrt_or_zero(err2)
    shape = torch.broadcast_shapes(pts1.shape[:-2], pts2.shape[:-2], H.shape[:-2])
    return out.reshape(*shape, num_points).to(dtype)


def _transfer_basis(x1: torch.Tensor, x2: torch.Tensor) -> torch.Tensor:
    """Per-correspondence monomials ``(9, 3N)`` of the one-way transfer error, for RANSAC's sampling loop only.

    ``vec(H) @ basis`` is ``[P_0 - u P_2 | P_1 - v P_2 | P_2]`` for ``P = H x1`` and ``x2 = (u, v)``, with ``x1``
    homogeneous ``(N, 3)``. Folding the subtraction into the product is about 10% faster than
    :func:`_transfer_errors` in RANSAC's loop on CPU (2048 models x 500 points: 6.6 against 7.2 ms) and 20-35 us per
    CUDA batch of 512-8192 models; it is accurate on normalized points, but in pixel units its float32 error was 2.5x
    that of :func:`oneway_transfer_error`.
    """
    n = x1.shape[0]
    basis = x1.new_zeros(9, 3 * n)
    basis[0:3, :n] = x1.T
    basis[6:9, :n] = -(x2[:, 0:1] * x1).T
    basis[3:6, n : 2 * n] = x1.T
    basis[6:9, n : 2 * n] = -(x2[:, 1:2] * x1).T
    basis[6:9, 2 * n :] = x1.T
    return basis


def _transfer_from_basis(H: torch.Tensor, basis: torch.Tensor) -> torch.Tensor:
    """Squared one-way transfer errors ``(M, N)`` of homographies ``(M, 3, 3)`` from :func:`_transfer_basis`."""
    n = basis.shape[1] // 3
    out = H.flatten(1) @ basis
    return (out[:, :n].square() + out[:, n : 2 * n].square()) / out[:, 2 * n :].square()


def _refine_homography_lm(
    H: torch.Tensor,
    x1: torch.Tensor,
    x2: torch.Tensor,
    mask: Optional[torch.Tensor],
    loss: str,
    scale2: Union[float, torch.Tensor],
    iters: int,
) -> torch.Tensor:
    """Levenberg-Marquardt on the one-way transfer error, batched over homographies ``(K, 3, 3)``.

    In the spirit of PoseLib's ``refine_homography``: steps are taken in the eight-dimensional orthogonal complement of
    the unit-norm ``vec(H)`` and renormalized. ``x1`` is homogeneous ``(N, 3)`` and ``x2`` ``(N, 2)``, normalized by
    the caller; the loss, ``mask`` and step acceptance are those of
    :func:`~kornia.geometry.epipolar.fundamental._refine_fundamental_lm`. For RANSAC, under ``torch.no_grad``.
    """
    K = H.shape[0]
    dtype, device = H.dtype, H.device
    cpu = K > 0 and device.type == "cpu" and not torch.is_grad_enabled()
    if cpu and K == 1 and mask is not None and mask.dtype == torch.bool:
        x1, x2, mask = x1[mask[0]], x2[mask[0]], None
    eye8 = torch.eye(8, dtype=dtype, device=device)
    eye9 = torch.eye(9, dtype=dtype, device=device)
    last = eye9[8]
    h = H.flatten(1)
    h = h * h.square().sum(1, keepdim=True).rsqrt()
    damping = torch.full((K, 1, 1), 1e-3, dtype=dtype, device=device)

    def normal_equations(h: torch.Tensor) -> Tuple[torch.Tensor, torch.Tensor, torch.Tensor]:
        # Householder reflection of h onto the last axis: its other eight columns span the tangent space.
        v = h + torch.where(h[:, 8:9] >= 0, 1.0, -1.0) * last
        v = v * v.square().sum(1, keepdim=True).rsqrt()
        tangent = (eye9 - 2 * v[:, :, None] * v[:, None, :])[:, :, :8]  # (K, 9, 8)
        stacked = torch.cat([h[:, :, None], tangent], 2).mT.reshape(K, 27, 3)  # rows of H, then of each direction
        P = (stacked @ x1.T).reshape(K, 9, 3, -1)  # (K, 9, 3, N): P = H x1, then its directional derivatives
        # When a mask is given, a zero mask excludes the correspondence. Guarding its projective divisor keeps the
        # residual and Jacobian of a finite row finite, so the zero weight below removes it exactly; masking the whole
        # derivative stack as well costs the compiled CUDA program about 10% of a homography call.
        iz = 1.0 / (P[:, 0, 2] if mask is None else torch.where(mask != 0, P[:, 0, 2], torch.ones_like(P[:, 0, 2])))
        uv = P[:, 0, :2] * iz[:, None]  # (K, 2, N)
        r = (uv - x2.T).flatten(1)  # (K, 2N): u residuals, then v residuals
        J = ((P[:, 1:, :2] - uv[:, None] * P[:, 1:, 2:3]) * iz[:, None, None]).flatten(2)  # (K, 8, 2N)
        r2 = r[:, : x1.shape[0]].square() + r[:, x1.shape[0] :].square()
        w, rho = _robust_loss(r2, loss, scale2)
        if mask is not None:
            w, rho = w * mask, rho * mask
        Jw = J * torch.cat([w, w], 1)[:, None]
        return torch.cat([Jw @ J.mT, Jw @ r[..., None]], 2), rho.sum(1), tangent

    system, cost, tangent = normal_equations(h)
    for iteration in range(iters):
        delta = -torch.linalg.solve_ex(system[..., :8] + damping * eye8, system[..., 8:])[0]
        h_new = h + (tangent @ delta)[..., 0]
        h_new = h_new * h_new.square().sum(1, keepdim=True).rsqrt()
        if cpu and iteration + 1 == iters:
            projection = h_new.reshape(K, 3, 3) @ x1.T
            divisor = projection[:, 2]
            if mask is not None:
                divisor = torch.where(mask != 0, divisor, torch.ones_like(divisor))
            r2 = (projection[:, :2] / divisor[:, None] - x2.T).square().sum(1)
            rho = (
                torch.log1p(r2 / scale2)
                if loss == "cauchy"
                else torch.fmin(r2, torch.as_tensor(scale2, dtype=r2.dtype, device=r2.device))
            )
            cost_new = (rho if mask is None else rho * mask).sum(1)
            accepted = cost_new < cost
            return torch.where(accepted[:, None], h_new, h).reshape(K, 3, 3)
        system_new, cost_new, tangent_new = normal_equations(h_new)
        accept = (cost_new < cost)[:, None, None]
        h, cost = torch.where(accept[:, :, 0], h_new, h), torch.where(accept[:, 0, 0], cost_new, cost)
        system, tangent = torch.where(accept, system_new, system), torch.where(accept, tangent_new, tangent)
        damping = damping * torch.where(accept, 0.1, 10.0)
    return h.reshape(K, 3, 3)


def find_homography_dlt(
    points1: torch.Tensor, points2: torch.Tensor, weights: Optional[torch.Tensor] = None, solver: str = "lu"
) -> torch.Tensor:
    r"""Estimate a homography from four or more weighted point correspondences by the normalized DLT.

    ``H = find_homography_dlt(points1, points2)`` takes correspondences ``(B, N, 2)``, ``N >= 4``, and returns the
    homography ``(B, 3, 3)`` that maps ``points1`` to ``points2``, :math:`x_2 \sim H x_1`: the least-squares
    solution of the Hartley-normalized DLT system, solved with ``solver``, and the source-to-destination pixel
    homography that :func:`~kornia.geometry.transform.warp_perspective` takes. ``weights`` ``(B, N)`` weight each
    correspondence's equations. It is not robust to wrong correspondences: with outliers, use
    :class:`~kornia.geometry.ransac.RANSAC`. For exactly four points in closed form, use
    :func:`~kornia.geometry.transform.get_perspective_transform`; for line segments,
    :func:`find_homography_lines_dlt`.

    Convention:
        - ``H`` is scaled so that ``H[2, 2] = 1`` by :func:`~kornia.geometry.epipolar.normalize_transformation`,
          which leaves it at its unnormalised scale when ``|H[2, 2]|`` is at most ``1e-8``;
          :ref:`two-view-conventions` compares this with OpenCV.
        - ``weights`` multiply each correspondence's squared algebraic residual: a weight of 0 removes the
          correspondence from the equations, and only relative weights matter.
        - ``solver="lu"`` and ``"svd"`` give the same homography on exact data, to roundoff scaled by the
          conditioning of the system; on noisy data they solve different least-squares problems and differ.
        - A caller's autocast region does not change the fit.

    .. note::
        On MPS, the default ``solver="lu"`` needs torch 2.10 or later and ``solver="svd"`` runs from torch 2.5.1;
        see :ref:`MPS linear algebra <mps-linear-algebra>`.

    Args:
        points1: A set of points in the first image with a tensor shape ``(B, N, 2)``.
        points2: A set of points in the second image with a tensor shape ``(B, N, 2)``.
        weights: Tensor containing the weights per point correspondence with a shape of ``(B, N)``.
          Zero-weight points are excluded from the DLT equations and Hartley normalization.
        solver: variants: svd, lu.


    Returns:
        the computed homography matrix with shape ``(B, 3, 3)``. A batch element whose weighted DLT system is
        not finite, because a weight or a point is not finite (zero-weight points included) or an entry overflows,
        is NaN for both solvers and on every device; the other elements are unaffected. If the SVD of
        ``solver="svd"`` fails to converge on a finite system, the whole batch is NaN and a ``RuntimeWarning`` is
        issued.

    See Also:
        - :func:`find_homography_dlt_iterated`: the same fit re-weighted by the transfer error over a few solves.
        - :func:`find_homography_lines_dlt`: a homography from line segment correspondences.
        - :func:`~kornia.geometry.transform.get_perspective_transform`: the exact homography of four points, in
          closed form.
        - :class:`~kornia.geometry.ransac.RANSAC`: a homography robust to wrong correspondences.
        - :func:`~kornia.geometry.epipolar.find_fundamental`: the two-view model of a general scene instead of a
          plane.
        - :func:`~kornia.geometry.epipolar.find_essential`: the two-view model of calibrated cameras in a general
          scene.
        - :func:`~kornia.geometry.solvers.find_affine`: an affine map, the special case with bottom row
          ``[0, 0, 1]``.
        - :func:`~kornia.geometry.calibration.solve_pnp_dlt`: the DLT for 3D-2D correspondences, a camera pose
          rather than a homography.

    """
    device, dtype = _extract_device_dtype([points1, points2])
    # Weights take the points' dtype, as a caller's autocast used to cast them; mixed dtypes now fit outside it too.
    if weights is not None:
        weights = _at_least_float32(weights.to(points1.dtype))
    # Half-precision correspondences are fitted in float32 and the homography is rounded once, on return.
    points1, points2 = _at_least_float32(points1), _at_least_float32(points2)
    # Autocast would run the DLT's matrix products in half precision and return a half-precision homography.
    with _autocast_disabled(points1.device.type):
        A, transform1, transform2 = _homography_dlt_system(points1, points2, weights)
        return _homography_from_dlt_system(
            A, weights, transform1, _inverse_normalization(transform2), solver, device, points1.dtype
        ).to(dtype)


def _inverse_normalization(transform: torch.Tensor) -> torch.Tensor:
    """Invert a Hartley normalization, NaN where it is singular.

    A point set whose mean radius overflows gets a zero scale and a singular normalization. Its homography
    is undefined, so it is NaN rather than built from the identity ``safe_inverse_with_mask`` substitutes.
    """
    inverse, valid = safe_inverse_with_mask(transform)
    return torch.where(valid[..., None, None], inverse, torch.full_like(inverse, float("nan")))


def _homography_dlt_system(
    points1: torch.Tensor, points2: torch.Tensor, weights: Optional[torch.Tensor] = None
) -> Tuple[torch.Tensor, torch.Tensor, torch.Tensor]:
    """Build the weighted-normalized DLT design matrix and its two normalizing transforms."""
    if points1.shape != points2.shape:
        raise ShapeError(
            f"points1 and points2 must have the same shape, got {list(points1.shape)} and {list(points2.shape)}.",
            actual_shape=list(points1.shape),
            expected_shape=list(points2.shape),
        )
    if points1.ndim != 3 or points1.shape[1] < 4:
        raise ShapeError(
            f"points1 and points2 must have shape (B, N, 2) with N >= 4, got {list(points1.shape)}.",
            actual_shape=list(points1.shape),
            expected_shape=["B", "N >= 4", "2"],
        )
    KORNIA_CHECK_SHAPE(points1, ["B", "N", "2"])
    KORNIA_CHECK_SHAPE(points2, ["B", "N", "2"])

    if weights is not None and weights.shape != points1.shape[:2]:
        raise ShapeError(
            f"weights must have shape (B, N) = {list(points1.shape[:2])}, got {list(weights.shape)}.",
            actual_shape=list(weights.shape),
            expected_shape=["B", "N"],
        )
    points1_norm, transform1 = normalize_points(points1, weights=weights)
    points2_norm, transform2 = normalize_points(points2, weights=weights)

    A = _homography_design_rows(points1_norm, points2_norm)
    return A, transform1, transform2


def _rank8_null_vector(normal: torch.Tensor) -> torch.Tensor:
    """Null vector of a ``(B, 9, 9)`` DLT normal matrix whose LU has only its last pivot zero, else NaN.

    Only the last pivot being zero means the first eight columns are independent, so the null vector has
    ``h[8] != 0`` and, the matrix being symmetric, its leading 8x8 block is non-singular: fixing ``h[8] = 1``
    leaves that block's system, solved with ``normal`` itself so the result stays differentiable. Roundoff
    can leave a degenerate matrix with tiny non-zero pivots instead, so the first eight must also be above
    ``sqrt(eps)`` relative to the largest. On the integer keypoints of the tests (exact identities, shifts
    and 90-degree rotations) the smallest stayed above ``4e-2``; on coincident or collinear points it was
    below ``1e-6``. Non-finite matrices are factorized as zeros (see #4770) and give NaN.
    """
    work_dtype = torch.float64 if normal.dtype == torch.float64 else torch.float32
    normal = normal.to(work_dtype)
    finite = normal.isfinite().flatten(1).all(-1)
    normal = torch.where(finite[:, None, None], normal, torch.zeros_like(normal))
    lu, _, info = torch.linalg.lu_factor_ex(normal.detach())
    diagonal = lu.diagonal(dim1=-2, dim2=-1).abs()
    tiny = torch.finfo(work_dtype).tiny
    leading = diagonal[:, :8].amin(-1) > diagonal.amax(-1).clamp_min(tiny) * torch.finfo(work_dtype).eps ** 0.5
    rank8 = finite & (info == normal.shape[-1]) & leading
    # Rows that are not rank 8 solve the identity against zero, so their (discarded) values and gradients
    # stay finite and cannot leak NaN into parameters shared with the rest of the batch.
    block = torch.where(rank8[:, None, None], normal[:, :8, :8], torch.eye(8, device=normal.device, dtype=work_dtype))
    rhs = torch.where(rank8[:, None], -normal[:, :8, 8], torch.zeros_like(normal[:, :8, 8]))
    head = torch.linalg.solve_ex(block, rhs)[0]
    null = torch.cat([head, torch.ones_like(head[:, :1])], -1)
    return torch.where(rank8[:, None], null, torch.full_like(null, float("nan")))


def _svd_null_vector(normal: torch.Tensor) -> torch.Tensor:
    """Right singular vector of the smallest singular value of each ``(B, 9, 9)`` matrix, NaN where it is undefined.

    A matrix with a non-finite entry has no null vector, and the backends disagree on what its SVD returns:
    CPU ``torch.linalg.svd`` raises for the whole batch, while CUDA can return a finite vector, such as a basis
    vector, for a matrix with a single NaN entry. Such matrices are decomposed as zeros and their vectors are
    replaced by NaN, so on every backend the finite matrices keep their vectors and the others are NaN, as with
    the LU solver (#4770). If the SVD still fails on a finite batch, every vector is NaN and a warning is issued;
    there is no partial result to keep.
    """
    finite = normal.isfinite().flatten(1).all(-1)
    safe = torch.where(finite[:, None, None], normal, torch.zeros_like(normal))
    try:
        # A half input is decomposed in float32, and S and V stay at the precision they were computed in.
        _, S, V = _torch_svd_in_work_dtype(safe.detach())
    except RuntimeError:
        warnings.warn("SVD did not converge", RuntimeWarning, stacklevel=1)
        return torch.full_like(normal[..., 0], float("nan"))
    # The normal matrix is positive semidefinite, so its singular values are its eigenvalues, and the null vector's
    # gradient stays finite when other eigenvalues are equal, as for the identity homography on a grid.
    null = _symmetric_eigenvector(safe, S, V, -1).to(normal.dtype)
    return torch.where(finite[:, None], null, torch.full_like(null, float("nan")))


def _homography_from_dlt_system(
    A: torch.Tensor,
    weights: Optional[torch.Tensor],
    transform1: torch.Tensor,
    transform2_inv: torch.Tensor,
    solver: str,
    device: torch.device,
    dtype: torch.dtype,
) -> torch.Tensor:
    """Solve the (weighted) DLT system of :func:`_homography_dlt_system` and denormalize the homography.

    The operand order matches the original single-call implementation.
    """
    eps: float = 1e-8
    num_points = A.shape[1] // 2
    if weights is None:
        # All points are equally important
        w_full = None
    else:
        # We should use provided weights
        if not (len(weights.shape) == 2 and weights.shape == (A.shape[0], num_points)):
            raise ShapeError(
                f"weights must have shape (B, N) = {[A.shape[0], num_points]}, got {list(weights.shape)}.",
                actual_shape=list(weights.shape),
                expected_shape=["B", "N"],
            )
        w_full = weights.repeat_interleave(2, dim=1).unsqueeze(1)

    # Only the minimal four-point LU path works from the design matrix itself (see below).
    # Every other case forms the normal equations in the exact operand order the pre-gauge
    # implementation used, so weighted results stay bit-identical to it.
    minimal_lu = solver == "lu" and num_points == 4
    if not minimal_lu:
        A = A.transpose(-2, -1) @ A if w_full is None else (A.transpose(-2, -1) * w_full) @ A

    if solver == "svd":
        H = _svd_null_vector(A).view(-1, 3, 3)
    elif solver == "lu":
        if not minimal_lu:
            B = torch.ones(A.shape[0], A.shape[1], device=device, dtype=dtype)
            sol, _, valid = safe_solve_with_mask(B, A)
            # Exact correspondences leave the normal matrix singular, and its null vector is the homography.
            # Roundoff usually keeps the LU pivots non-zero and the solve above lands on that vector, but an
            # exactly zero last pivot (identical point sets after Hartley normalization, an integer shift)
            # makes the solve fail. With only that pivot zero the rank is 8, so the homography is unique and
            # the leading 8x8 block determines it with h[8] = 1. Any other singular system (an earlier zero
            # pivot, as for coincident points) has no unique homography: report it as NaN rather than the
            # identity system's solution that ``safe_solve_with_mask`` leaves in its place.
            sol = torch.where(valid[:, None, None], sol, _rank8_null_vector(A).to(sol.dtype)[..., None])
        else:
            # A four-point sample gives eight equations for nine unknowns, so the normal matrix
            # is singular and LU-factoring it is what produced all-NaN homographies. Work from
            # the design matrix instead: its null vector comes from a pivoted LU factorization of
            # it, the largest component of that vector fixes the homogeneous gauge, and the
            # retained 8x8 system is solved for the rest. A fixed h33=1 gauge is invalid whenever
            # the bottom-right entry is zero. Five or more points keep the normal-equation
            # formulation above.
            Aw = A if w_full is None else A * w_full.transpose(-2, -1)
            # torch.linalg.qr on CUDA can spin forever on a design matrix that mixes NaN with the
            # structured zeros of the DLT rows (#4770). Hand QR and the solve finite entries only,
            # and report the affected batch elements as NaN below, as the CPU path already does.
            finite_entries = Aw.isfinite()
            finite = finite_entries.flatten(1).all(-1)
            Aw = torch.where(finite_entries, Aw, torch.zeros_like(Aw))
            gauge_dtype = torch.float64 if dtype == torch.float64 else torch.float32
            design = Aw.detach().to(gauge_dtype)
            # One batched LU factorization on every backend: torch.linalg.qr has no batched CUDA kernel
            # (one cusolver call per matrix, ~250 ms for a 2048-sample RANSAC batch), and a batched SVD or
            # QR costs about three times the LU on CPU. A zero-weight correspondence leaves the null vector
            # finite, since the unit triangular factor the basis is solved from is never singular; asking for
            # that basis keeps it finite on CUDA too, where the fast path reports rank deficiency as NaN.
            null = _null_space_lu(design, rank_deficient_basis=True)[..., 0]
            null = null / null.norm(dim=-1, keepdim=True)
            gauge = null.abs().argmax(dim=-1)
            retained = torch.arange(8, device=device).expand(A.shape[0], -1)
            retained = retained + (retained >= gauge[:, None]).to(retained.dtype)
            selected = Aw.gather(-1, retained[:, None].expand(-1, 8, -1))
            B = -Aw.gather(-1, gauge[:, None, None].expand(-1, 8, 1)).squeeze(-1)
            sol, _, valid = safe_solve_with_mask(B, selected)
            sol = sol.squeeze(-1)
            # A fully de-weighted correspondence zeroes two rows and leaves the retained system
            # singular. The null vector is finite and still satisfies the surviving equations,
            # so fall back to it rather than handing the caller a NaN homography.
            null = (null / null.gather(-1, gauge[:, None])).to(sol.dtype)
            sol = torch.where(valid[:, None], sol, null.gather(-1, retained))
            positions = torch.arange(9, device=device).expand(A.shape[0], -1)
            source = (positions - (positions > gauge[:, None]).to(positions.dtype)).clamp(0, 7)
            sol = torch.where(
                positions == gauge[:, None], torch.ones_like(positions, dtype=sol.dtype), sol.gather(-1, source)
            )
            sol = torch.where(finite[:, None], sol, torch.full_like(sol, float("nan")))
        H = sol.reshape(-1, 3, 3)
    else:
        raise NotImplementedError
    H = transform2_inv @ (H @ transform1)
    return normalize_transformation(H, eps)


def find_homography_dlt_iterated(
    points1: torch.Tensor, points2: torch.Tensor, weights: torch.Tensor, soft_inl_th: float = 3.0, n_iter: int = 5
) -> torch.Tensor:
    r"""Estimate a homography by iteratively re-weighted DLT, with Gaussian weights of the transfer error.

    ``H = find_homography_dlt_iterated(points1, points2, weights)`` takes correspondences ``(B, N, 2)`` and initial
    weights ``(B, N)`` and returns the homography ``(B, 3, 3)`` that maps ``points1`` to ``points2``, as
    :func:`find_homography_dlt` does, after ``n_iter`` weighted DLT solves: each solve after the first re-weights the
    correspondences by a Gaussian of their symmetric transfer error under the previous estimate, of standard
    deviation ``soft_inl_th`` pixels. A correspondence whose symmetric error is ``e = 3 * soft_inl_th`` keeps a
    weight of ``exp(-4.5)``, about 0.01, so the iterations suppress a few outliers when the first solve is close; for
    many outliers use :class:`~kornia.geometry.ransac.RANSAC`, which refines its homography with this function under
    ``local_optimization="dlt"``.

    Convention:
        - Direction, ``H[2, 2] = 1`` and autocast as :func:`find_homography_dlt`. Each solve after the first re-weights
          with the Gaussian kernel ``exp(-e**2 / (2 * soft_inl_th**2))`` of the symmetric transfer error ``e``
          (the root of the summed squared forward and backward transfer errors), so ``soft_inl_th`` is a
          standard deviation in pixels: a correspondence with ``e = soft_inl_th`` keeps weight ``exp(-1/2)``.

    .. note::
        On MPS this needs torch 2.10 or later; see :ref:`MPS linear algebra <mps-linear-algebra>`.

    Args:
        points1: A set of points in the first image with a tensor shape ``(B, N, 2)``.
        points2: A set of points in the second image with a tensor shape ``(B, N, 2)``.
        weights: Tensor containing the weights per point correspondence with a shape of ``(B, N)``.
          Used for the first iteration of the IRWLS.
        soft_inl_th: standard deviation, in pixels, of the Gaussian re-weighting kernel given above.
        n_iter: number of solves, including the initial one.

    Returns:
        the computed homography matrix with shape ``(B, 3, 3)``, NaN for a batch element as in
        :func:`find_homography_dlt`.

    See Also:
        - :func:`find_homography_dlt`: a single weighted solve.
        - :func:`find_homography_lines_dlt_iterated`: the same re-weighting for line segment correspondences.
        - :func:`symmetric_transfer_error`: the error the weights are computed from.

    """
    device, dtype = _extract_device_dtype([points1, points2])
    # Weights take the points' dtype, as a caller's autocast used to cast them; mixed dtypes now fit outside it too.
    if weights is not None:
        weights = _at_least_float32(weights.to(points1.dtype))
    # Half-precision correspondences are fitted and re-weighted in float32, and the homography is rounded once.
    points1, points2 = _at_least_float32(points1), _at_least_float32(points2)
    work = points1.dtype
    # Autocast would run the solves and the re-weighting errors in half precision.
    with _autocast_disabled(points1.device.type):
        # Weighted Hartley normalization changes with each set of IRLS weights.
        A, transform1, transform2 = _homography_dlt_system(points1, points2, weights)
        transform2_inv = _inverse_normalization(transform2)
        H: torch.Tensor = _homography_from_dlt_system(A, weights, transform1, transform2_inv, "lu", device, work)
        for _ in range(n_iter - 1):
            squared_errors: torch.Tensor = symmetric_transfer_error(points1, points2, H, True)
            weights_new: torch.Tensor = torch.exp(-squared_errors / (2.0 * (soft_inl_th**2)))
            A, transform1, transform2 = _homography_dlt_system(points1, points2, weights_new)
            transform2_inv = _inverse_normalization(transform2)
            H = _homography_from_dlt_system(A, weights_new, transform1, transform2_inv, "lu", device, work)
    return H.to(dtype)


def sample_is_valid_for_homography(points1: torch.Tensor, points2: torch.Tensor) -> torch.Tensor:
    """Test whether four correspondences keep their orientation across two views.

    ``valid = sample_is_valid_for_homography(points1, points2)`` takes minimal samples ``(B, 4, 2)`` of the first and
    the second image, or ``(B, N, 2)`` of which the first four points are read, and returns a ``(B,)`` bool mask that
    is True where each of the four triples of points has the same orientation in both images: the oriented
    constraint of :cite:`Marquez-Neila2015`, analogous to OpenCV's USAC degeneracy test
    (https://github.com/opencv/opencv/blob/4.x/modules/calib3d/src/usac/degeneracy.cpp#L88).
    :class:`~kornia.geometry.ransac.RANSAC` uses it to discard minimal samples for ``"homography"`` before fitting
    them.

    Convention:
        - It checks only that the four triples of the first four points keep their orientation across the two
          views, so a mirror-image sample is rejected. A triple that is collinear in both views, for instance
          through a repeated point, counts as kept, so collinearity alone does not reject a sample.

    Args:
        points1: A set of points in the first image with a tensor shape ``(B, N, 2)``; only the first four
          points are used.
        points2: A set of points in the second image with a tensor shape ``(B, N, 2)``; only the first four
          points are used.

    Returns:
        Mask with the minimal sample is good for homography estimation ``(B,)``.

    See Also:
        - :func:`find_homography_dlt`: the fit of a sample that passes.
        - :class:`~kornia.geometry.ransac.RANSAC`: the estimator that draws the samples this tests.

    """
    if points1.shape != points2.shape:
        raise ShapeError(
            f"points1 and points2 must have the same shape, got {list(points1.shape)} and {list(points2.shape)}.",
            actual_shape=list(points1.shape),
            expected_shape=list(points2.shape),
        )

    # Triples to test: (0,1,2), (0,1,3), (0,2,3), (1,2,3), gathered by slicing, shape (B, 4, 2). Index tensors
    # would be copied to the device on every call.
    def _triples(points: torch.Tensor) -> Tuple[torch.Tensor, torch.Tensor, torch.Tensor]:
        p0, p1, p2, p3 = points[:, 0], points[:, 1], points[:, 2], points[:, 3]
        return torch.stack([p0, p0, p0, p1], 1), torch.stack([p1, p1, p2, p2], 1), torch.stack([p2, p3, p3, p3], 1)

    p1_i, p1_j, p1_k = _triples(points1)
    p2_i, p2_j, p2_k = _triples(points2)

    # 2D orientation (signed area) for each triple:
    # orient(a,b,c) = cross2d(b-a, c-a) = (bx-ax)*(cy-ay) - (by-ay)*(cx-ax)
    def _orient(a: torch.Tensor, b: torch.Tensor, c: torch.Tensor) -> torch.Tensor:
        ab = b - a
        ac = c - a
        return ab[..., 0] * ac[..., 1] - ab[..., 1] * ac[..., 0]  # shape (B, 4)

    left_sign = torch.sign(_orient(p1_i, p1_j, p1_k))
    right_sign = torch.sign(_orient(p2_i, p2_j, p2_k))

    # Valid if all four orientation signs match across views
    return (left_sign == right_sign).all(dim=1)


def find_homography_lines_dlt(
    ls1: torch.Tensor, ls2: torch.Tensor, weights: Optional[torch.Tensor] = None
) -> torch.Tensor:
    """Estimate a homography from four or more line segment correspondences by the DLT.

    ``H = find_homography_lines_dlt(ls1, ls2)`` takes segment correspondences ``(B, N, 2, 2)``, ``N >= 4``, each a
    ``[start, end]`` pair of ``(x, y)`` points, and returns the homography ``(B, 3, 3)`` that maps image-1 points to
    image-2 points, scaled to ``H[2, 2] = 1`` unless that entry is numerically zero, from the constraint that both
    endpoints of each image-1 segment map onto the line through the matching image-2 segment (:cite:`homolines2001`).
    The endpoints need not be point correspondences, so segments detected with different extents still constrain
    ``H``. For point correspondences, use :func:`find_homography_dlt`; with outliers,
    :class:`~kornia.geometry.ransac.RANSAC` with ``model_type="homography_from_linesegments"``.

    Convention:
        - ``H`` maps image-1 points to image-2 points, as in :func:`find_homography_dlt`. ``weights`` has one entry
          per segment.
        - Each segment gives two constraints on the eight degrees of freedom of ``H``, so at least four segments
          are needed, as :func:`find_homography_dlt` needs four points.
        - A caller's autocast region does not change the fit.

    Args:
        ls1: A set of line segments in the first image with a tensor shape ``(B, N, 2, 2)``, or
          ``(N, 2, 2)``, which is treated as :math:`B = 1`. ``N`` must be at least 4.
        ls2: A set of line segments in the second image with a tensor shape ``(B, N, 2, 2)``, or
          ``(N, 2, 2)``, which is treated as :math:`B = 1`.
        weights: Tensor containing the weights per segment with a shape of ``(B, N)``.
          Zero-weight segments are excluded from Hartley normalization.

    Returns:
        the computed homography matrix with shape ``(B, 3, 3)``. A batch element whose weighted DLT system is
        not finite, because a weight or an endpoint is not finite (zero-weight segments included) or an entry
        overflows, is NaN on every device; the other elements are unaffected. If the SVD fails to converge on a
        finite system, the whole batch is NaN and a ``RuntimeWarning`` is issued.

    Raises:
        ShapeError: if fewer than four segments are given, as in :func:`find_homography_dlt`.

    See Also:
        - :func:`find_homography_dlt`: a homography from point correspondences.
        - :func:`find_homography_lines_dlt_iterated`: the same fit re-weighted by the line distance over a few
          solves.
        - :func:`line_segment_transfer_error_one_way`: the residual of segments under the result.
        - :class:`~kornia.geometry.ransac.RANSAC`: a homography from segments with outliers, with
          ``model_type="homography_from_linesegments"``.

    """
    if len(ls1.shape) == 3:
        ls1 = ls1[None]
    if len(ls2.shape) == 3:
        ls2 = ls2[None]
    KORNIA_CHECK_SHAPE(ls1, ["B", "N", "2", "2"])
    KORNIA_CHECK_SHAPE(ls2, ["B", "N", "2", "2"])
    BS, N = ls1.shape[:2]
    # Fewer segments leave the DLT system under-determined: its null space then holds an arbitrary
    # homography, or NaN for none at all (#5991).
    if N < 4:
        raise ShapeError(f"find_homography_lines_dlt needs at least 4 line segments, got {N}: {ls1.shape}")
    # Raises unless both segment sets share a device and a dtype.
    _, dtype = _extract_device_dtype([ls1, ls2])
    # Weights take the segments' dtype, as a caller's autocast used to cast them; mixed dtypes now fit outside it too.
    if weights is not None:
        weights = _at_least_float32(weights.to(dtype))
    # Half-precision segments are fitted in float32 and the homography is rounded once, on return.
    ls1, ls2 = _at_least_float32(ls1), _at_least_float32(ls2)

    points1 = ls1.reshape(BS, 2 * N, 2)
    points2 = ls2.reshape(BS, 2 * N, 2)

    if weights is not None and weights.shape != ls1.shape[:2]:
        raise ShapeError(
            f"weights must have shape (B, N) = {list(ls1.shape[:2])}, got {list(weights.shape)}.",
            actual_shape=list(weights.shape),
            expected_shape=["B", "N"],
        )
    # Autocast would run the DLT's matrix products in half precision and return a half-precision homography.
    with _autocast_disabled(ls1.device.type):
        endpoint_weights = weights.repeat_interleave(2, dim=1) if weights is not None else None
        points1_norm, transform1 = normalize_points(points1, weights=endpoint_weights)
        points2_norm, transform2 = normalize_points(points2, weights=endpoint_weights)
        # Pair each segment's own endpoints: the flattened points are [start_0, end_0, start_1, end_1, ...].
        segments1_norm = points1_norm.reshape(BS, N, 2, 2)
        segments2_norm = points2_norm.reshape(BS, N, 2, 2)
        lst1, le1 = segments1_norm[:, :, 0], segments1_norm[:, :, 1]
        lst2, le2 = segments2_norm[:, :, 0], segments2_norm[:, :, 1]

        xs1, ys1 = torch.chunk(lst1, dim=-1, chunks=2)  # BxNx1
        xs2, ys2 = torch.chunk(lst2, dim=-1, chunks=2)  # BxNx1
        xe1, ye1 = torch.chunk(le1, dim=-1, chunks=2)  # BxNx1
        xe2, ye2 = torch.chunk(le2, dim=-1, chunks=2)  # BxNx1

        A = ys2 - ye2
        B = xe2 - xs2
        C = xs2 * ye2 - xe2 * ys2

        eps: float = 1e-8

        # http://diis.unizar.es/biblioteca/00/09/000902.pdf
        ax = torch.cat([A * xs1, A * ys1, A, B * xs1, B * ys1, B, C * xs1, C * ys1, C], dim=-1)
        ay = torch.cat([A * xe1, A * ye1, A, B * xe1, B * ye1, B, C * xe1, C * ye1, C], dim=-1)
        # The row count is spelled out: a ``-1`` cannot be inferred for an empty batch.
        A = torch.cat((ax, ay), dim=-1).reshape(BS, 2 * N, ax.shape[-1])

        if weights is None:
            # All points are equally important
            A = A.transpose(-2, -1) @ A
        else:
            # We should use provided weights
            if not ((len(weights.shape) == 2) and (weights.shape == ls1.shape[:2])):
                raise ShapeError(
                    f"weights must have shape (B, N) = {list(ls1.shape[:2])}, got {list(weights.shape)}.",
                    actual_shape=list(weights.shape),
                    expected_shape=["B", "N"],
                )
            # Scale each segment's two design rows by its weight instead of materializing the
            # (B, 2N, 2N) diagonal weight matrix, whose storage grows quadratically with N.
            w_full = weights.repeat_interleave(2, dim=1).unsqueeze(1)
            A = (A.transpose(-2, -1) * w_full) @ A

        H = _svd_null_vector(A).view(-1, 3, 3)
        H = _inverse_normalization(transform2) @ (H @ transform1)
        return normalize_transformation(H, eps).to(dtype)


def find_homography_lines_dlt_iterated(
    ls1: torch.Tensor, ls2: torch.Tensor, weights: torch.Tensor, soft_inl_th: float = 4.0, n_iter: int = 5
) -> torch.Tensor:
    r"""Estimate a homography from line segments by iteratively re-weighted DLT.

    ``H = find_homography_lines_dlt_iterated(ls1, ls2, weights)`` takes segment correspondences ``(B, N, 2, 2)``,
    ``N >= 4``, and initial weights ``(B, N)`` and returns the homography ``(B, 3, 3)`` that maps image-1 points to
    image-2 points, as :func:`find_homography_lines_dlt` does, after ``n_iter`` weighted solves: each solve after the
    first re-weights the segments by a Gaussian, of standard deviation ``soft_inl_th`` pixels, of the mean distance
    of their mapped endpoints from the matched lines under the previous estimate. For point correspondences, use
    :func:`find_homography_dlt_iterated`.

    Convention:
        - As :func:`find_homography_dlt_iterated`, with :func:`find_homography_lines_dlt` as the solver and, as
          ``e`` in the Gaussian kernel, the perpendicular distance in pixels of the mapped image-1 endpoints from
          the image-2 line. A zero-length image-2 segment gets weight zero.

    Args:
        ls1: A set of line segments in the first image with a tensor shape ``(B, N, 2, 2)``, or
          ``(N, 2, 2)``, which is treated as :math:`B = 1`, as in :func:`find_homography_lines_dlt`.
        ls2: A set of line segments in the second image with a tensor shape ``(B, N, 2, 2)``, or
          ``(N, 2, 2)``, which is treated as :math:`B = 1`.
        weights: Tensor containing the weights per segment with a shape of ``(B, N)``.
          Used for the first iteration of the IRWLS.
        soft_inl_th: standard deviation, in pixels, of the Gaussian re-weighting kernel of
          :func:`find_homography_dlt_iterated`.
        n_iter: number of solves, including the initial one.

    Returns:
        the computed homography matrix with shape ``(B, 3, 3)``. A batch element is NaN when one of its
        solves is, as in :func:`find_homography_lines_dlt`.

    Raises:
        ShapeError: if fewer than four segments are given, as in :func:`find_homography_lines_dlt`.

    See Also:
        - :func:`find_homography_lines_dlt`: a single weighted solve.
        - :func:`find_homography_dlt_iterated`: the same re-weighting for point correspondences.
        - :func:`line_segment_transfer_error_one_way`: the distance the weights are computed from.

    """
    # Promote unbatched segments as find_homography_lines_dlt does: the re-weighting below needs the batch axis.
    if len(ls1.shape) == 3:
        ls1 = ls1[None]
    if len(ls2.shape) == 3:
        ls2 = ls2[None]
    # Half-precision segments are fitted and re-weighted in float32, and the homography is rounded once, on return.
    dtype = ls1.dtype
    if weights is not None:
        weights = weights.to(dtype)
    ls1, ls2 = _at_least_float32(ls1), _at_least_float32(ls2)
    # Autocast would run the re-weighting distances in half precision.
    with _autocast_disabled(ls1.device.type):
        H: torch.Tensor = find_homography_lines_dlt(ls1, ls2, weights)
        for _ in range(n_iter - 1):
            squared_distances: torch.Tensor = _line_segment_squared_distance_one_way(ls1, ls2, H)
            weights_new: torch.Tensor = torch.exp(-squared_distances / (2.0 * (soft_inl_th**2)))
            H = find_homography_lines_dlt(ls1, ls2, weights_new)
    return H.to(dtype)
