kornia.geometry.solvers#

Affine, polynomial and homogeneous linear solvers used by the geometric estimators.

Affine estimation#

find_affine() fits a full 2D affine transform from at least three non-collinear source points and their corresponding target points. It supports weighted least-squares fitting and returns a source-to-target homogeneous (B, 3, 3) matrix. Use RANSAC with model_type="affine" when the correspondences contain outliers.

kornia.geometry.solvers.find_affine(points1, points2, weights=None)[source]#

Estimate 2D affine transformations from point correspondences.

Fits the weighted least-squares model \(\mathbf{y}=A\mathbf{x}+\mathbf{t}\) independently for each batch. The calculation centers and isotropically normalizes each point set before solving its 2-by-2 normal equation. Inputs must have the same floating-point dtype and device; half inputs are accumulated in float32. Ambient autocast is disabled during fitting to preserve this arithmetic precision.

Parameters:

points1 (Tensor) – Source points with shape \((B, N, 2)\), where \(N \geq 3\).
points2 (Tensor) – Destination points with shape \((B, N, 2)\).
weights (Optional[Tensor], optional) – Optional correspondence weights with shape \((B, N)\). They must be finite and non-negative; other values are not detected and give undefined results. Only relative weights matter. Default: None

Return type:

Tensor

Returns:

Homogeneous affine transformations with shape \((B, 3, 3)\). Degenerate batches without three non-collinear, positive-weight source points contain NaNs, allowing robust estimators to reject singular fits as invalid models.

Homogeneous Solvers#

kornia.geometry.solvers.null_vector_3x4(A)[source]#

Return the null vector of a rank-3 matrix of shape \((*, 3, 4)\).

The null vector \(\mathbf{v} \in \mathbb{R}^4\) satisfies \(A\,\mathbf{v} = \mathbf{0}\). For a matrix of rank 3 this solution is unique up to scale.

The computation uses the 4-D cross-product (cofactor expansion): each component of \(\mathbf{v}\) is a \(3 \times 3\) determinant of the submatrix obtained by dropping the corresponding column of \(A\). For a rank-3 \(A\) this gives the last right singular vector up to scale and sign, but replaces the SVD with 48 scalar multiplications and 20 additions — no LAPACK or cuSOLVER call is made. The sign follows the cofactor formula below ([I | 0] gives [0, 0, 0, -1]), and a lower rank gives the zero vector rather than a unit vector.

\[v_j = (-1)^j \det\!\bigl(A_{[0,1,2],\,\widehat{j}}\bigr), \quad j = 0, 1, 2, 3\]

where \(A_{[0,1,2],\,\widehat{j}}\) denotes the \(3 \times 3\) submatrix formed by deleting column \(j\).

Note

The returned vector is not normalised. Divide by its norm if a unit null vector is required.

Note

The function is only correct when \(A\) has rank exactly 3. For rank-deficient inputs (rank < 3) the result is the zero vector.

Parameters:

A (Tensor) – matrix of shape \((*, 3, 4)\).

Return type:

Tensor

Returns:

Null vector of shape \((*, 4)\).

Raises:

TypeCheckError – if A is not a torch.Tensor.
ShapeError – if the last two dimensions of A are not (3, 4).

Example

>>> A = torch.tensor([[[1., 0., 0., 0.],
...                    [0., 1., 0., 0.],
...                    [0., 0., 1., 0.]]])   # null vector is [0,0,0,-1]
>>> v = null_vector_3x4(A)                   # shape (1, 4)
>>> (A @ v.unsqueeze(-1)).squeeze(-1)         # should be near zero
tensor([[0., 0., 0.]])

Polynomial Solvers#

The polynomial solvers accept coefficients in descending degree order and return real roots with multiplicity, using zero padding for missing real roots. The public quadratic, cubic and quartic paths support fixed-shape graph capture, including mixed batches with lower-degree rows. Near repeated roots, input coefficient rounding can change whether a pair is real or complex; correctness is defined by the represented coefficients. See each function’s precision and gradient conventions. Under torch.compile with Inductor on CUDA, fused multiply-adds can lose exact double roots; this known limitation is not planned to be fixed, and the notes on solve_cubic() and solve_quartic() give the rates and a workaround.

kornia.geometry.solvers.solve_quadratic(coeffs)[source]#

Solve given quadratic equation.

The function takes the coefficients of quadratic equation and returns the real roots.

\[coeffs[0]x^2 + coeffs[1]x + coeffs[2] = 0\]

Convention:

The coefficients of solve_quadratic(), solve_cubic() and solve_quartic() are batched (B, k + 1) for degree k, highest degree first; Two-view geometry compares this with numpy.roots.
Only real roots are returned, and a repeated root is repeated. A missing real root is reported as 0.0, which is indistinguishable from a root at 0, so count real roots from the discriminant when it matters.
For coeffs = [a, b, c] and D = b**2 - 4 * a * c, solve_quadratic returns [(-b + sqrt(D)) / (2 * a), (-b - sqrt(D)) / (2 * a)], so the order flips with the sign of a.
A zero leading coefficient lowers the degree: with a = 0 the root -c / b of the linear equation is in slot 0, as solve_cubic() and solve_quartic() do for their lower-degree rows.
Half inputs are evaluated in float32. On MPS, which has no float64 and flushes float32 subnormals in products, float32 inputs are solved on the CPU in float64; from about 10**3 rows this is slower than an on-device solve. The output retains the input dtype and device.

Parameters:: coeffs (Tensor) – The coefficients of quadratic equation :(B, 3)
Return type:: Tensor
Returns:: A torch.Tensor of shape (B, 2) containing the real roots to the quadratic equation.

Example

>>> coeffs = torch.tensor([[1., 4., 4.]])
>>> roots = solve_quadratic(coeffs)

kornia.geometry.solvers.solve_cubic(coeffs)[source]#

Solve given cubic equation.

The function takes the coefficients of cubic equation and returns the real roots.

\[coeffs[0]x^3 + coeffs[1]x^2 + coeffs[2]x + coeffs[3] = 0\]

Convention:

Coefficient layout and zero padding as solve_quadratic(). Three real roots are returned unsorted, and a single real root is in slot 0. Where the discriminant is within rounding of 0, the cubic’s values at its stationary points, evaluated with compensated Horner on the input coefficients, decide between one root, a double root and three roots.
A zero leading coefficient lowers the degree, and the roots of the remaining polynomial come first.
The closed form is evaluated on the row scaled by an exact power of two to a unit root bound, and the roots are scaled back, so its intermediates neither overflow nor underflow for a tiny leading coefficient or for roots far from unit scale (#4914).
Half inputs are evaluated in float32. Float32 cubics are solved in float64 (on MPS, which has no float64, on the CPU), so a row’s roots do not depend on the rest of its batch. On MPS, beyond roughly 5 * 10**5 rows this is slower than an on-device solve. The output retains the input dtype and device.

Parameters:: coeffs (Tensor) – The coefficients cubic equation : (B, 4)
Return type:: Tensor
Returns:: A torch.Tensor of shape (B, 3) containing the real roots to the cubic equation.

Example

>>> solve_cubic(torch.tensor([[1., 0., 0., 1.]]))
tensor([[-1.,  0.,  0.]])

Note

At the acos boundary reached by a repeated (or near-repeated) real root, backward suppresses the derivative of the acos argument to keep gradients finite. Repeated-root derivatives are undefined; this is a surrogate convention, not a mathematical Jacobian. A double root that the cubic’s values at its stationary points identify takes the derivative of that stationary point, and the third root keeps the sum of the roots at -b / a. solve_quartic() inherits these conventions for the rows it solves as cubics.

Note

Known limitation, not planned to be fixed: under torch.compile() with the Inductor backend on CUDA, Triton contracts a multiplication followed by an addition into one fused multiply-add by default. That breaks the error-free transformations of the compensated evaluation at the stationary points, so an exact double root can come back as a single root: 1 % of exact (x - p)(x - q)^2 rows in float32 and 2 % in float64. Eager execution, other backends and Inductor on CPU are not affected, and torch._inductor.config.emulate_precision_casts = True turns the contraction off.

kornia.geometry.solvers.solve_quartic(coeffs)[source]#

Solve given quartic equation.

The function takes the coefficients of quartic equation and returns the real roots.

\[coeffs[0]x^4 + coeffs[1]x^3 + coeffs[2]x^2 + coeffs[3]x + coeffs[4] = 0\]

Convention:

Coefficient layout and zero padding as solve_quadratic(). Genuine quartic roots are sorted in descending order, followed by padding; lower-degree rows preserve solve_cubic()’s order.
Quartics are evaluated after an exact power-of-two variable rescaling to a unit root bound. Root reality and multiplicity are resolved against the original coefficients with compensated Horner evaluation, before monic normalization can erase the distinction: the signs of the quartic at its stationary points fix the number of real roots wherever they are resolvable, and the local Taylor quadratic decides a nearly multiple root.
A row is solved as the cubic of its last four coefficients when its leading coefficient is 0, or when both hold: |a| is smaller than 1e-6 (1e-12 in float64) times min(1, max_i |coeffs_i|), and the scale-invariant root bound max(|b/a|, |c/a|^(1/2), |d/a|^(1/3), |e/a|^(1/4)) exceeds 1 / tol (tested as |coeffs_k| > |a| / tol^k, without dividing by a). Since the bound is at most 4 times the largest root’s magnitude, a quartic whose roots are all smaller than 1 / (4 * tol) stays a quartic at every scale; the bound can only move a row from the cubic path to the quartic path.

Parameters:: coeffs (Tensor) – The coefficients quartic equation : (B, 5)
Return type:: Tensor
Returns:: A torch.Tensor of shape (B, 4) containing the real roots to the quartic equation.

Example

>>> coeffs = torch.tensor([[1., -10., 35., -50., 24.]])
>>> roots = solve_quartic(coeffs)

Note

Ferrari intermediates and root polishing are evaluated in float64 and the returned roots preserve the input dtype and device. On MPS, which has no float64, the quartic computation runs on the CPU; autograd follows the copies in both directions.

Note

Variable rescaling is bounded to normal reciprocal powers of two in the compute dtype. It does not recover input coefficients that have underflowed, and extreme subnormal coefficient scales may remain below unit scale. A float64 coefficient that underflows once the variable is rescaled counts as 0: in \(x^4 + 1.75 x^3 - 78 x^2 + 5 \cdot 10^{-324}\), the real pair \(\pm 2.5 \cdot 10^{-163}\) is reported as a double root at 0.

Note

Simple roots use the implicit-function Jacobian, coupled to preserve Vieta’s sum when all four roots are real. A repeated-root Jacobian is undefined; repeated roots use a finite surrogate with the same sum convention. Coefficient rounding can turn a generating repeated root into a complex pair; the solver classifies the represented input polynomial.

Note

Known limitation, not planned to be fixed: under torch.compile() with the Inductor backend on CUDA, Triton contracts a multiplication followed by an addition into one fused multiply-add by default. That breaks the error-free transformations of the compensated Horner evaluation that decides multiplicity and the number of real roots, so a quartic with an exact double root or a tight cluster can lose roots: 7 % of exact (x - p)^2 (x - q)(x - r) rows, and 3 % of four-root clusters in float64. Eager execution, other backends and Inductor on CPU are not affected, and torch._inductor.config.emulate_precision_casts = True turns the contraction off.

Note

The same surrogate convention applies at this function’s own two sqrt boundaries: when the resolvent radicand R^2 is 0 (a pure biquadratic such as \(x^4 - 16\)) and when the constant-term identity used for E has a zero radicand, backward suppresses the diverging sqrt derivative to keep gradients finite. The result is finite but is not the root Jacobian; the forward values are unaffected.

kornia.geometry.solvers.multiply_deg_one_poly(a, b)[source]#

Multiply two polynomials of the first order [@nister2004efficient].

Parameters:

a (Tensor) – a first order polynomial for variables \((x,y,z,1)\).
b (Tensor) – a first order polynomial for variables \((x,y,z,1)\).

Return type:

Tensor

Returns:

degree 2 poly with the order \((x^2, x*y, x*z, x, y^2, y*z, y, z^2, z, 1)\).

kornia.geometry.solvers.multiply_deg_two_one_poly(a, b)[source]#

Multiply two polynomials a and b of degrees two and one [@nister2004efficient].

Parameters:

a (Tensor) – a second degree poly for variables \((x^2, x*y, x*z, x, y^2, y*z, y, z^2, z, 1)\).
b (Tensor) – a first degree poly for variables \((x y z 1)\).

Return type:

Tensor

Returns:

a third degree poly for variables, \((x^3, y^3, x^2*y, x*y^2, x^2*z, x^2, y^2*z, y^2, x*y*z, x*y, x*z^2, x*z, x, y*z^2, y*z, y, z^3, z^2, z, 1)\).

kornia.geometry.solvers.determinant_to_polynomial(A)[source]#

Represent the determinant by the 10th polynomial, used for 5PC solver [@nister2004efficient].

Convention:

Each row of A holds two cubics (columns 0 to 3 and 4 to 7) and a quartic (columns 8 to 12) in z, highest degree first. The returned coefficients are lowest degree first (cs[i] multiplies z**i), the reverse of the solve_quadratic() layout.

Parameters:: A (Tensor) – torch.Tensor \((B, 3, 13)\).
Return type:: Tensor
Returns:: a degree 10 poly of shape \((B, 11)\), representing determinant (Eqn. 14 in the paper).