Object Pose from 2-D to 3-D Point and Line Correspondences

In plain words

A camera sees a known 3-D object, and you want to know where the object sits relative to the camera: how it is turned and how far it is moved. Each matched point or line in the image gives a constraint on that unknown position. The hard part is that the constraints are nonlinear, so simple solvers can be thrown off by noise or get stuck in wrong answers.

The paper writes the position in a compact mathematical form, a "dual-number quaternion", in which each constraint becomes a quadratic equation. It then searches for the position that best fits all constraints at once, using a method that only trusts a small neighbourhood of its current guess at each step. The authors report that this stays accurate where a standard linear method breaks down, which is the case when image measurements are noisy or some matches are wrong.

TL;DR

The paper gives a pose estimator for a calibrated camera and a 3-D object, from point correspondences, line correspondences, or both §1.2. The unknown rigid motion is a dual-number quaternion (r, s), and each correspondence contributes quadratic constraints on it §2.1 §2.2 §3. The error, a sum of squares of those constraints plus penalties that keep r unit-length and orthogonal to s, is minimised with a trust-region method §4 §4.1. On a 460-point calibration set, the author-reported translation error with 100 points at 1 px noise is 0.0002 cm for the proposed point version, against 11.48 cm for the linear Faugeras-Toscani method tab. 2 tab. 8. The paper links no code.

Problem

Given 3-D object points or lines, their image projections, and known intrinsic camera parameters, find the rigid transform from the object frame to the camera frame. This is called the perspective-n-point or exterior calibration problem §1. Closed-form solutions exist when the number of correspondences is limited. For larger sets the problem is nonlinear, with six unknowns (three for rotation, three for translation), so iterative solvers are needed §1 §1.1.

The paper's view is that three choices decide the outcome: the representation of the pose, the error function, and the optimiser §1. Earlier iterative methods used rotation matrices, Euler angles or Newton's method, and reported local minima and sensitivity to initialisation §1.1. A linear method that ignores the orthogonality of rotation is noise-sensitive §1.1. The paper does not state an operating regime beyond the experiments in Section 5.

Method

The method has four parts: a camera model, a quadratic reformulation of the pose using dual-number quaternions, two error functions (line-based and point-based), and a trust-region minimiser. Experiments compare three variants §5.

1. Camera model. Pixel coordinates (u, v) map to camera-frame coordinates x = (u − u0) / αu and y = (v − v0) / αv, with z = 1. The intrinsic parameters u0, v0, αu, αv are assumed known §2 eq. 1.
2. Line constraint. An image line a·x + b·y + c = 0 defines a plane through the centre of projection with normal n = (a, b, c) in camera coordinates §2 eq. 2 eq. 3. An object line with direction v and point p, moved by (R, t), lies in that plane. This gives two constraints, n·(Rv) = 0 and n·(Rp + t) = 0 §2 eq. 4.
3. Counting. Each line correspondence gives two constraints, so three lines are the minimum for six unknowns. N line correspondences can be built from 2N point correspondences for N ≥ 3 §2.
4. Dual-number quaternion. The pose is written as r + ε s, where r and s are quaternions and ε² = 0. The constraints are r·r = 1 and r·s = 0 §2.1. The rotation matrix and translation are read from r and s by the matrices Q(r) and W(r) eq. 6 eq. 7 eq. 8 eq. 9.
5. Quadratic constraints. Using the identities in §2.2 eq. 10 eq. 11 eq. 12, each line gives r^T A r = 0 and r^T B r + r^T C s = 0, with A, B and C built from n, v and p §2.2.
6. Line error function. The sum of squared constraints over all lines, plus penalties λ(r·r − 1)² and λ(r·s)², is eq. 13, with λ = 50 in the experiments §2.2 eq. 13. A split variant first minimises a rotation-only error in r (eq. 14), then solves a linear least-squares problem for s (eq. 15) §2.2.
7. Point constraints. Each point gives the two collinearity equations of its image ray §3 eq. 16 eq. 17, rewritten as constraints on (r, s) through the matrices A^p, B^p, C^p and D^p §3 eq. 18 eq. 19 eq. 20 eq. 21. The point error function is eq. 22, with the same penalties as eq. 13 §3 eq. 22.
8. Least-squares form. The error is written as f(x) = ½ Σ Φ_j(x)² over the unknown vector x (4 values for eq. 14, 8 values for eqs. 13 and 22) §4 eq. 23. The gradient is Jᵀ Φ and the Hessian is JᵀJ plus a second-order term that is dropped in practice (Gauss-Newton) §4 eq. 24 eq. 25.
9. Trust-region loop. At each iterate the paper computes the value, the gradient and H = JᵀJ, then solves for a step inside a sphere of radius δ_k. The step is accepted when the actual reduction is at least a fraction r of the predicted reduction; the radius doubles when the ratio is at least s and halves when it is rejected §4.1 eq. 26 eq. 27 eq. 28.
10. Step computation. The paper adds α = 0.001 to H and first solves the unconstrained system (H + αI) d = −g. If that step is inside the radius it is used; otherwise the constrained step is found with Hebden's method §4 §4.1 app. A eq. 29 eq. 30 eq. 31 eq. 32 eq. 33 eq. 34.
11. Comparison. The paper contrasts this with Levenberg-Marquardt, which it says is poorly conditioned when its damping term is near zero, and with Newton's method, which can increase the error. For large-residual problems it suggests a safeguarded Moré-Sorensen step instead of Hebden's step §4.2 §1.

The trust-region loop in pseudocode, following §4.1 steps k.1 to k.6:

# Practical trust-region loop  [§4.1]
# x: pose unknowns, r (4 values) or (r, s) (8 values)  [§2.2] [§3]
# radius: trust radius delta_k; the paper's values r = 0.25, s = 0.75
def trust_region(x, radius, residual, jacobian):
    # Repeat until the stop test of step k.2 holds  [§4.1]
    while not stop_test(x, radius):
        # k.1: objective, gradient and Gauss-Newton Hessian  [§4.1] [eq. 24]
        objective = 0.5 * sum(residual(x) ** 2)     # [eq. 23]
        gradient = jacobian(x).T @ residual(x)      # [eq. 24]
        hessian = jacobian(x).T @ jacobian(x)       # [§4]
        # k.3 and k.6: retry with a halved radius until the ratio test passes
        while True:
            # Shifted Gauss-Newton system  [§4.1]
            shifted = hessian + 0.001 * identity    # alpha = 0.001  [§4]
            step = solve(shifted, -gradient)
            # Use Hebden's search when the step leaves the trust region  [§4.1]
            if norm(step) >= radius - eps:
                step = hebden_step(shifted, gradient, radius)  # [app. A]
            # k.4: ratio of actual to predicted reduction  [eq. 28]
            predicted = -(gradient @ step + 0.5 * step @ hessian @ step)
            actual = objective - 0.5 * sum(residual(x + step) ** 2)
            ratio = actual / predicted
            if ratio >= 0.25:  # r  [§4.1]
                break
            radius = radius / 2
        # k.5: accept the step, and double the radius if the model was good
        x = x + step
        if ratio >= 0.75:  # s  [§4.1]
            radius = 2 * radius
    return x

Hebden's search for the constrained step, in the form of app. A steps l.1 to l.5:

# Hebden's search for the shift mu  [app. A]
# Start mu with phi(mu) > radius; the paper gives no start value  [app. A]
def hebden_step(hessian, gradient, radius, mu, tol):
    while True:
        # l.1: factor the shifted Hessian as R^T R  [app. A]
        factor = cholesky(hessian + mu * identity)
        # l.2: solve for the step p  [app. A]
        p = solve(factor, -gradient)
        # l.3: stop when the step length is close to the radius  [app. A]
        if abs(norm(p) - radius) < tol:
            return p
        # l.4: solve R^T q = p  [app. A]
        q = solve_transpose(factor, p)
        # l.5: Newton update of mu  [app. A] [eq. 34]
        ratio = (norm(p) / norm(q)) ** 2
        mu = mu + ratio * (norm(p) - radius) / radius

The point-based error in its matrix form, from §3 eq. 22:

# Point-correspondence matrices  [§3] [eq. 20] [eq. 21]
# point: object point (X, Y, Z); x, y: camera-frame image coordinates  [§3]
def point_matrices(point, x, y):
    # Purely imaginary quaternions for the point and its two image halves
    point_quat = (0, point)                 # M_i
    mx = (0, 1, 0, -x)                      # m_x,i
    my = (0, 0, 1, -y)                      # m_y,i
    A = Q(mx).T @ W(point_quat)
    B = Q(mx).T
    C = Q(my).T @ W(point_quat)
    D = Q(my).T
    return A, B, C, D

# Penalised point error  [eq. 22]
# matrices: one (A, B, C, D) tuple per point  [§3]
def point_error(real, dual, matrices, lam):
    total = 0
    for A, B, C, D in matrices:
        # Two quadratic constraints per point  [eq. 22]
        total += (real @ A @ real + 2 * real @ B @ dual) ** 2
        total += (real @ C @ real + 2 * real @ D @ dual) ** 2
    # Penalties for r.r = 1 and r.s = 0; the paper uses lam = 50  [§2.2]
    total += lam * (real @ real - 1) ** 2
    total += lam * (real @ dual) ** 2
    return total

Pose from the dual-number quaternion, from eq. 6 and eq. 7:

# Rotation and translation from (r, s)  [eq. 6] [eq. 7]
def pose_from_dual_quaternion(real, dual):
    # The real part gives the rotation in the lower-right 3 x 3 block  [eq. 6]
    rotation = (W(real).T @ Q(real))[1:, 1:]
    # The dual part gives the translation, with a factor of 2  [eq. 7]
    translation = (2 * W(real).T @ dual)[1:]
    return rotation, translation

Hyperparameters

Results

Author-reported. Setup: a 3-D calibrating object with 460 points viewed by one camera; the reference is the linear Faugeras-Toscani solution on all 460 points §5. The baseline is that linear method, run on the same subsets. The paper gives no numbers for Newton or Levenberg-Marquardt, only a qualitative comparison §4.2 §6.

Other reported results:

• Line-based rotation then translation is the cheapest variant (about 0.25 s at 230 lines in Table 3), and the joint line and point variants cost more §6 tab. 3 tab. 5 tab. 7.
• Translation from the linear method is "not reliable" beyond about half a pixel of noise tab. 2.
• Matching errors: the non-linear method degrades gently as point mismatches increase from 1 to 10, while the linear method gives erroneous results §5.1 fig. 9. The values are in plots only.

Paper vs code

No official code. The paper does not link a repository, a project page or a code availability statement §1 §6. The arXiv metadata has no comment field [raw/arxiv metadata]. Searches on the GitHub repository API for "dual quaternion pose", "dual quaternion trust region", "object pose line correspondences", "phong horaud pose" and "horaud inria" returned no repository from the authors. The results for "dual quaternion pose" were unrelated third-party projects, which were not used.

Pitfalls

• Scale of n. Figure 1 says n is a unit normal fig. 1, but eq. 3 identifies n with (a, b, c) from the image line eq. 3, which need not be unit length. The error functions scale with |n|² eq. 13 eq. 22, so the penalty λ = 50 balances differently for different normalisations. The paper does not say which is used. Normalise n and state the choice.
• Factor of ½. The least-squares form uses f = ½ Σ Φ² eq. 23, but the error functions in eqs. 13, 14, 15 and 22 have no ½. The paper says the two forms are equivalent §4. They have the same minimisers, but the gradient and Hessian differ by a factor of 2, and the fixed shift α = 0.001 is therefore relative to a different scale. Use one convention throughout.
• Penalties as residuals. The paper does not state the residual vector Φ for the penalty terms. Treating them as extra squared residuals with weight √λ is the natural reading, but it is not written out.
• Hebden start and tolerance. μ_0 and the stop tolerance are not given app. A. μ_0 = 0 satisfies φ(μ_0) > δ whenever the unshifted step is longer than δ. This follows from eq. 30 and step k.3 and is our reading, not a stated rule.
• Which matrix Hebden uses. Step k.3 defines H' = H + 0.001 I and then says to use Hebden's algorithm. Whether Hebden shifts H' or the raw H is not stated.
• Stop tests. The tolerances ε, ε_g, ε_f, ε_δ are not given §4.1. The paper checks the stop test only at step k.2. The retry loop (k.3 to k.6) can shrink δ without rechecking it §4.1.
• Quality ratio. The denominator of r_k is q(0) − q(d). It is zero when no reduction is predicted, which can happen at convergence. The paper does not say how this case is handled eq. 28.
• Initialisation claim. The discussion says the final result is independent of the initialisation §6. No initial pose or radius is given, and no experiment varies the start. Treat the claim as untested in the paper.
• Rotation-then-translation. This variant fixes r after minimising eq. 14 and then solves for s only §2.2 §5. The translation is then t = 2W(r)ᵀ s eq. 7. The paper does not say whether r is re-estimated jointly with s afterwards.
• Quaternion sign. The paper does not discuss that r and −r give the same rotation. Our reading is that the error in eq. 13 is unchanged if both r and s change sign, since each term is quadratic in (r, s) jointly. Check this before comparing r across runs.
• Negative αu. The ground-truth intrinsics in Table 1 have αu = −1730.3 tab. 1. The text does not comment on the sign. Check your camera convention against the image model in §2 before comparing with other sources.
• Reference is a linear estimate. The "ground truth" is the Faugeras-Toscani estimate on all 460 points §5. The proposed point method on 460 points still differs from it by about 0.0001 cm tab. 7, so baseline errors are relative to a reference that is itself an estimate.
• Noise units and axis units. The table headers give no units. The noise amplitude is in pixels by the caption of Table 2 ("half of a pixel"). The axis error is the norm of a difference of unit vectors and is dimensionless. The angle error is in radians and the translation error in centimetres fig. 5 fig. 6 fig. 7.
• Large-residual problems. Gauss-Newton drops the second-order term, which is justified only when residuals are small §4.2. For large residuals the paper suggests a safeguarded Moré-Sorensen step, but no experiment uses it §4.2.
• Cost of the joint variants. The joint point variant takes 4.83 s at 460 points tab. 7. The rotation-first line variant takes 0.25 s at 230 lines tab. 3. The two runs use different data sizes and different error functions, so the timings are not a like-for-like comparison §6.
• Source date. The arXiv record is dated 2026-10-14 [raw/arxiv metadata]. The LaTeX source is a journal manuscript with a commented-out journal line for International Journal of Computer Vision, 15(3), 225-243 (1995). Whether the text is the 1995 article unchanged is not stated.

Lineage

• Builds on: dual-number quaternions, which Walker, Shao and Volz (1991) introduced to computer vision for 3-D/3-D pose; this paper applies them to 2-D/3-D pose §1.2.
• Builds on: the line-correspondence coplanarity constraint of Horaud, Dhome, Chen, Liu and Kumar and Hanson, which the paper reuses §1.2.
• Builds on: the trust-region method of Sorensen and Moré, with Fletcher's survey and Hebden's shift search for the subproblem §1.2 §4 app. A.
• Compared against: the linear calibration method of Faugeras and Toscani (1986), used as baseline and reference §1 §5 tab. 1; Newton's method, as used by Yuan (1989) and Lowe (1987, 1991) §1.1 §4; and Levenberg-Marquardt §4.2.
• Superseded by: no card in this wiki.