1 Introduction↩︎

Rolling shutter (RS) cameras equip virtually all consumer devices – smartphones, tablets, action cameras, and drones. Unlike global shutter (GS) sensors that expose all pixels simultaneously, RS sensors read out the image row by row. When the camera moves during the readout interval – typically 15–30 ms for consumer CMOS sensors – each row captures the scene from a slightly different viewpoint. This sequential exposure invalidates the standard pinhole model that underpins most multi-view geometry methods [3]: the epipolar constraint, which normally defines a constant essential matrix across the image, becomes row-dependent.

Relative pose estimation is fundamental to structure from motion (SfM) [4], visual odometry, SLAM, and augmented reality. These systems typically treat the essential matrix \(\mathbf{E}\) as constant across the image. On RS images, this introduces a systematic bias that grows with camera velocity and readout time, and in severe cases causes bundle adjustment to diverge or converge to incorrect reconstructions. As RS cameras continue to dominate consumer and industrial markets, developing RS-aware geometric methods is essential.

Under the first-order RS model of Meingast et al. [3], the RS relative pose problem has 17 degrees of freedom: 5 for the relative pose \((\mathbf{R}, \mathbf{t})\) plus 12 for the per-camera angular and translational velocities \((\mathbf{\omega}_k, \mathbf{v}_k)\), \(k=1,2\). Dai et al. [5] showed that a minimum of 20 PCs is required – far more than the 5 PCs of GS estimation [2]. This gap has practical consequences. The expected RANSAC [6] iteration count scales as \(\eta^{-k}\) (inlier ratio \(\eta\), sample size \(k\)): at \(50\%\) inliers, \(k\!=\!5\) needs \(32\) iterations but \(k\!=\!20\) over a million – making the 20-PC solver [5] prohibitive and motivating smaller samples.

Affine correspondences (ACs) provide a natural path toward this goal. An AC augments a point match with the local \(2 \times 2\) affine transformation between image patches [7], [8], yielding 3 equations per correspondence (1 epipolar + 2 affine). In the GS setting, this tripling of constraints enables essential matrix recovery from just 2 ACs [8] instead of 5 PCs, and homographies from 2 ACs [9] instead of 4 PCs. ACs are routinely available from affine-covariant detectors [10] and learned methods [11], [12] at negligible additional cost.

We make RS relative pose estimation practical by bringing ACs to the problem for the first time. We derive RS-corrected affine constraints that account for the coupling between point perturbations and the row-dependent essential matrix – a coupling absent in the GS formulation – and build a linearized algebraic solver that estimates pose and RS parameters from 7 ACs, reducing RANSAC samples from 20 to 7 and iterations from millions to hundreds. On real-world data, we achieve the best pose and RS parameter estimation accuracy among all tested methods, demonstrating that RS-aware relative pose estimation is now practical with affine correspondences. Our key contributions are:

• We derive RS-corrected affine correspondence constraints that account for the row-dependent essential matrix – a coupling absent in the GS formulation. Each AC yields 3 equations (1 epipolar + 2 affine), so 7 ACs provide 21 equations for the 17 unknowns of the joint pose + RS problem.

• We develop a 7-AC algebraic solver with algebraic degree 20, based on action matrix methods, that makes RS-aware RANSAC practical: the sample size reduction from 20 to 7 decreases the expected RANSAC iterations by orders of magnitude (e.g., from \(10^6\) to \(\sim\)​600 at 50% inliers).

• We show that the proposed method achieves the best pose and RS estimation accuracy on the TUM-RS benchmark among RS and GS baselines, and substantially improves translational velocity estimation – which is poorly conditioned from PCs alone due to a \(\mathbf{v}\)-\(\mathbf{t}\) coupling [5]. On the global-shutter EuRoC MAV dataset [13], the solver generalizes without degradation.

2 Related Work↩︎

RS camera modeling and pose estimation. Meingast et al. [3] introduced the first-order RS model in which each scanline’s pose is linearly interpolated between a reference rotation and translation, adding six motion parameters (angular and translational velocity) per frame. This model has been validated across consumer cameras [5], [14], [15] and remains the standard choice when the readout-time rotation is moderate (\(\lesssim 10^\circ\)). For absolute pose, Albl et al. [14], [16] developed Gröbner-basis minimal solvers under the linearized RS model (6-point, or 5-point with known gravity); Saurer et al. [17] proposed an alternative formulation; and Albl et al. [15] later unified these results. For relative pose, Dai et al. [5] derived the RS epipolar geometry and showed that the linearized two-view problem requires 20 PCs (44 for the quadratic model). The \(\mathbf{v}\)-\(\mathbf{t}\) coupling between the translational velocity and the baseline direction had been identified earlier by Ait-Aider and Berry [18]. Zhuang et al. [19] used differential homographies for RS-aware SfM and rectification, Lee et al. [20] a gyroscope to reduce the unknowns, and Hedborg et al. [4] extended bundle adjustment to RS. Hahn et al. [21] recently gave an algebraic analysis of order-one RS cameras, under a model in which each world point is imaged at most once – distinct from the first-order model used here, where a point may be observed across several rows. Concurrently, Hruby and Pollefeys [22] reduce the correspondence count via a single-scanline formulation using line correspondences – a different input modality. A common theme is that RS solvers need far more correspondences than their GS counterparts, making RANSAC expensive; our solver reduces the RS sample to 7 ACs via affine-correspondence constraints.

Affine correspondences in geometry estimation. An AC augments a point match with the local \(2\times2\) affine transformation between patches, giving richer per-correspondence constraints. Differentiating the epipolar constraint yields two extra equations per AC [7], which Perdoch et al. [23] and Barath and Hajder [8] used to recover the essential matrix from just 2 ACs; homographies follow from 2 ACs [9], and later work consolidated the theory across model types [24], [25]. ACs are widely available from affine-covariant detectors [10] and learned methods [11], [12] at negligible cost, but have not been applied to rolling-shutter geometry – the gap we bridge.

Minimal solvers and RANSAC. Nistér’s 5-point algorithm [2] is the standard GS essential-matrix solver, and automatic Gröbner-basis generators [26] extended such techniques to RS settings [14], [16]. A problem’s algebraic complexity (its number of solutions) governs practicality – our joint 7-AC solver has only 20 – and the \(\eta^{-k}\) cost of RANSAC [6] and its variants [27]–[29] in sample size \(k\) makes reducing \(k\) (here from 20 to 7) decisive.

3 Geometric Background↩︎

Rolling Shutter Camera Model. A rolling shutter camera reads out the sensor row by row; if the camera moves during the 15–30 ms readout, each row is captured from a different viewpoint (2). We adopt the standard first-order RS model [3], [5], [15]. Let \(\mathbf{R} \in \mathrm{SO}(3)\) and \(\mathbf{t} \in \mathbb{R}^3\), \(\|\mathbf{t}\| = 1\), be the relative rotation and translation at the reference rows, and let \(\mathbf{\omega}_k, \mathbf{v}_k \in \mathbb{R}^3\) (\(k=1,2\)) denote the angular and translational velocities during readout (absorbing the readout time \(t_\mathrm{ro}\)). For a point whose pixel row is \(y\), let \(\tau = (y - h/2)/h \in [-\tfrac{1}{2}, \tfrac{1}{2}]\) be its scalar normalized row coordinate; the per-scanline pose is \[\begin{align} \tilde{\mathbf{R}}(\tau_1, \tau_2) &= \bigl(\mathbf{I} + \tau_2 [\mathbf{\omega}_2]_{\times}\bigr)\, \mathbf{R}\, \bigl(\mathbf{I} - \tau_1 [\mathbf{\omega}_1]_{\times}\bigr), \tag{1} \\ \tilde{\mathbf{t}}(\tau_1, \tau_2) &= \bigl(\mathbf{t} + \tau_2\,\mathbf{v}_2\bigr) - \tau_1\,\tilde{\mathbf{R}}\,\mathbf{v}_1, \tag{2} \end{align}\] where \([\cdot]_{\times}\) denotes the skew-symmetric matrix, \(\tau_1, \tau_2 \in \mathbb{R}\) are the scalar normalized row coordinates of the point in images 1 and 2, respectively, and \(\mathbf{I}\) is the identity. The row-dependent essential matrix is \[\label{eq:Etilde} \tilde{\mathbf{E}}(\tau_1, \tau_2) = [\tilde{\mathbf{t}}(\tau_1, \tau_2)]_{\times}\;\tilde{\mathbf{R}}(\tau_1, \tau_2).\tag{3}\]

The unknowns of the RS two-view problem decompose into the pose parameters \((\mathbf{R}, \mathbf{t})\) (5 degrees of freedom, as translation is known only up to scale) and the RS motion parameters \(\mathbf{\theta} = (\mathbf{\omega}_1, \mathbf{v}_1, \mathbf{\omega}_2, \mathbf{v}_2) \in \mathbb{R}^{12}\), giving 17 degrees of freedom in total for the entire system [5].

Point Correspondences in GS and RS Cameras. In the global shutter (GS) case (\(\mathbf{\theta} = \mathbf{0}\)), \(\mathbf{E} = [\mathbf{t}]_{\times}\,\mathbf{R}\) is constant and a point pair \((\mathbf{q}_1, \mathbf{q}_2)\) satisfies \[\label{eq:epipolar95gs} \mathbf{q}_2^\top \mathbf{E}\, \mathbf{q}_1 = 0,\tag{4}\] recoverable from 5 PCs [2]. In the RS case, each pair has its own \(\tilde{\mathbf{E}}(\tau_1, \tau_2)\) and the constraint becomes \[\label{eq:epipolar} \mathbf{q}_2^\top\, \tilde{\mathbf{E}}(\tau_1, \tau_2)\, \mathbf{q}_1 = 0.\tag{5}\] Each PC still yields one equation, but the unknowns now include the 12 RS parameters \(\mathbf{\theta}\). The known-pose subproblem requires 12 PCs; the joint problem requires 20 PCs [5] (44 for the quadratic RS model).

Affine Correspondences in GS Cameras. An affine correspondence (AC) augments a point match \((\mathbf{q}_1, \mathbf{q}_2)\) with the local affine map \(\mathbf{A}_c = \partial \mathbf{q}_2 / \partial(q_{1,x}, q_{1,y}) \in \mathbb{R}^{3 \times 2}\), available from affine-covariant detectors [10], [11]. Let \(\mathbf{a}_u, \mathbf{a}_v \in \mathbb{R}^3\) be the columns of \(\mathbf{A}_c\) and \(\mathbf{e}_u = (1,0,0)^\top\), \(\mathbf{e}_v = (0,1,0)^\top\). Differentiating the GS epipolar constraint with respect to \(q_{1,x}\) yields [7], [8] equation \[\label{eq:ac95gs95u} \mathbf{a}_u^\top \mathbf{E}\, \mathbf{q}_1 + \mathbf{q}_2^\top \mathbf{E}\, \mathbf{e}_u = 0.\tag{6}\] Differentiating with respect to \(q_{1,y}\) gives the analogous \[\label{eq:ac95gs95v} \mathbf{a}_v^\top \mathbf{E}\, \mathbf{q}_1 + \mathbf{q}_2^\top \mathbf{E}\, \mathbf{e}_v = 0.\tag{7}\] Together with the epipolar constraint 4 , each AC provides 3 independent equations on the essential matrix. Since \(\mathbf{E}\) has 5 degrees of freedom, just 2 ACs suffice for essential matrix estimation [8] versus 5 PCs with point-only methods.

4 RS Relative Pose Estimation↩︎

Beyond the first-order RS model, we make two explicit approximations, stated here and justified where used: (i) constraints are linearized in the motion parameters \(\mathbf{\theta}\) about \(\mathbf{\theta}=\mathbf{0}\) (valid as \(\|\mathbf{\omega}\|<0.15\) rad, 4.4); and (ii) the null-space basis eliminating \(\mathbf{\theta}\) is fixed at the reference rotation \(\mathbf{R}_\mathrm{ref}=\mathbf{I}\) (4.2). The constraints of 4.1 are exact; the approx. enter only at the solver stage.

4.1 RS-Corrected Affine Constraints↩︎

The original GS affine constraints 6 –7 were derived under the assumption that \(\mathbf{E}\) is constant across the image. In the RS case, the essential matrix \(\tilde{\mathbf{E}}(\tau_1, \tau_2)\) varies with the row coordinates of both points. When we perturb \(\mathbf{q}_1\) to derive the affine constraints, the row coordinates \(\tau_1\) and \(\tau_2\) change as well, because a shift in the image position of a point shifts the row at which it was read out. This introduces additional terms \(\partial \tilde{\mathbf{E}} / \partial \tau_k\) that are absent in the GS formulation.

Derivation. Consider the RS epipolar constraint \(F(\mathbf{q}_1, \mathbf{q}_2) \!=\! \mathbf{q}_2^\top\, \tilde{\mathbf{E}}(\tau_1, \tau_2)\, \mathbf{q}_1 \!=\! 0\). When we differentiate with respect to \(q_{1,x}\) (horizontal shift), three effects contribute: (i) the explicit dependence of \(\mathbf{q}_1\) on its \(x\)-coordinate (\(\partial \mathbf{q}_1/\partial q_{1,x} = \mathbf{e}_u\)); (ii) the induced change in \(\mathbf{q}_2\) via the affine map (\(\partial \mathbf{q}_2/\partial q_{1,x} = \mathbf{a}_u\)); and (iii) the change in the essential matrix caused by the vertical shift of \(\mathbf{q}_2\), which alters its readout row \(\tau_2\). Crucially, a horizontal shift of \(\mathbf{q}_1\) does not change its own readout row \(\tau_1\) (rows are horizontal), but it may shift \(\mathbf{q}_2\) vertically through \(\mathbf{a}_u\), thereby changing \(\tau_2\). Applying the chain rule to all three effects yields \[\label{eq:ac95u} \underbrace{\mathbf{a}_u^\top \tilde{\mathbf{E}}\, \mathbf{q}_1 + \mathbf{q}_2^\top \tilde{\mathbf{E}}\, \mathbf{e}_u}_{\text{same as GS}} + \underbrace{\mathbf{q}_2^\top \frac{\partial \tilde{\mathbf{E}}}{\partial \tau_2}\, \mathbf{q}_1 \cdot \frac{f_y}{h} \cdot (\mathbf{a}_u)_y}_{\text{RS correction}} = 0,\tag{8}\] where \(f_y\) is the focal length in pixels, \(h\) the image height, \((\mathbf{a}_u)_y\) the \(y\)-component of \(\mathbf{a}_u\) (which converts the image-space vertical shift to a normalized-row shift via \(f_y/h\)), and \(\partial\tilde{\mathbf{E}}/\partial\tau_2\) is given below.

For the vertical derivative (\(q_{1,y}\)), a shift of \(\mathbf{q}_1\) now directly changes \(\tau_1\), introducing an additional correction term: \[\label{eq:ac95v} \underbrace{\mathbf{a}_v^\top \tilde{\mathbf{E}}\, \mathbf{q}_1 + \mathbf{q}_2^\top \tilde{\mathbf{E}}\, \mathbf{e}_v}_{\text{same as GS}} + \underbrace{\mathbf{q}_2^\top \frac{\partial \tilde{\mathbf{E}}}{\partial \tau_1}\, \mathbf{q}_1 \cdot \frac{f_y}{h}}_{\substack{\text{RS correction} \\ \text{(from } \tau_1\text{)}}} + \underbrace{\mathbf{q}_2^\top \frac{\partial \tilde{\mathbf{E}}}{\partial \tau_2}\, \mathbf{q}_1 \cdot \frac{f_y}{h} \cdot (\mathbf{a}_v)_y}_{\substack{\text{RS correction} \\ \text{(from } \tau_2\text{)}}} = 0.\tag{9}\] 9 has two correction terms: a vertical shift of \(\mathbf{q}_1\) changes \(\tau_1\) directly (the \(\partial\tilde{\mathbf{E}}/\partial\tau_1\) term) and may also shift \(\mathbf{q}_2\) vertically via \((\mathbf{a}_v)_y\) (the \(\partial\tilde{\mathbf{E}}/\partial\tau_2\) term).

Row derivatives of the essential matrix. From 1 –2 , the derivatives of \(\tilde{\mathbf{R}}\) and \(\tilde{\mathbf{t}}\) with respect to the row coordinates are \[\begin{align} \frac{\partial \tilde{\mathbf{R}}}{\partial \tau_1} &= -\bigl(\mathbf{I} + \tau_2 [\mathbf{\omega}_2]_{\times}\bigr)\, \mathbf{R}\,[\mathbf{\omega}_1]_{\times}, & \frac{\partial \tilde{\mathbf{t}}}{\partial \tau_1} &= -\tilde{\mathbf{R}}\,\mathbf{v}_1 - \tau_1 \frac{\partial \tilde{\mathbf{R}}}{\partial \tau_1}\, \mathbf{v}_1, \tag{10} \\ \frac{\partial \tilde{\mathbf{R}}}{\partial \tau_2} &= [\mathbf{\omega}_2]_{\times}\,\mathbf{R}\, \bigl(\mathbf{I} - \tau_1 [\mathbf{\omega}_1]_{\times}\bigr), & \frac{\partial \tilde{\mathbf{t}}}{\partial \tau_2} &= \mathbf{v}_2 - \tau_1 \frac{\partial \tilde{\mathbf{R}}}{\partial \tau_2}\, \mathbf{v}_1, \tag{11} \end{align}\] Combining these with the product rule applied to the essential matrix 3 gives \(\partial\tilde{\mathbf{E}}/\partial\tau_k = [\partial\tilde{\mathbf{t}}/\partial\tau_k]_{\times}\;\tilde{\mathbf{R}} + [\tilde{\mathbf{t}}]_{\times}\;\partial\tilde{\mathbf{R}}/\partial\tau_k\).

Summary. Each AC yields three equations on the RS two-view geometry: the epipolar constraint 5 plus two new affine constraints 8 –9 . The RS correction terms vanish when \(\mathbf{\theta} = \mathbf{0}\) (since \(\partial\tilde{\mathbf{E}}/\partial\tau_k \to 0\) when there is no RS motion), recovering the standard GS constraints as a special case. These constraints are general: they hold for any RS two-view configuration under the first-order RS model and do not require any linearization. In the remainder of this section, we exploit them to build efficient minimal solvers for RANSAC.

4.2 Minimal Solver from 7 Affine Correspondences↩︎

The RS-corrected AC constraints 5 , 8 –9 involve all 17 unknowns (5 pose + 12 RS motion). Solving this full nonlinear system directly is algebraically intractable: even the known-pose subproblem alone (12 RS unknowns) already has 254 isolated solutions (supplementary material), and the full 17-DoF system further couples the pose with the row-dependent \((\tau_1,\tau_2)\) terms.

Key observation: the RS parameters enter approximately linearly. The epipolar constraint 5 is a polynomial of multi-degree \((2, 1, 2, 1)\) in \((\mathbf{\omega}_1, \mathbf{v}_1, \mathbf{\omega}_2, \mathbf{v}_2)\): it is linear in each translational velocity \(\mathbf{v}_k\) and quadratic in each angular velocity \(\mathbf{\omega}_k\). However, the RS parameters are physically small (\(\|\mathbf{\omega}_k\| < 0.15\) rad for virtually all consumer cameras; see 4.4), so the quadratic terms \(O(\|\mathbf{\omega}\|^2) \!<\! 5 \!\times\! 10^{-3}\) are negligible compared to measurement noise. We therefore linearize the RS constraints in \(\mathbf{\theta}\) around the GS solution \(\mathbf{\theta} = \mathbf{0}\), keeping only first-order terms.

For a given pose \((\mathbf{R}, \mathbf{t})\), setting \(\mathbf{\theta} = \mathbf{0}\) reduces the essential matrix to \(\mathbf{E}_0 = [\mathbf{t}]_{\times}\,\mathbf{R}\) and the row derivatives to the compact forms \[\label{eq:dE95domega1} \frac{\partial \tilde{\mathbf{E}}}{\partial \omega_{1,k}} \bigg|_{\mathbf{\theta}=\mathbf{0}} \!=\! -\tau_1 [\mathbf{t}]_{\times}\,\mathbf{R}\,[\mathbf{e}_k]_{\times}, \qquad \frac{\partial \tilde{\mathbf{E}}}{\partial v_{2,k}} \bigg|_{\mathbf{\theta}=\mathbf{0}} \!=\! \tau_2 [\mathbf{e}_k]_{\times}\,\mathbf{R},\tag{12}\] with analogous expressions for \(\mathbf{\omega}_2\) and \(\mathbf{v}_1\). Each of the three per-AC constraints becomes a linear function of \(\mathbf{\theta}\) with coefficients that depend on \((\mathbf{R}, \mathbf{t})\) and the data (\(\mathbf{q}_1, \mathbf{q}_2, \tau_1, \tau_2, \mathbf{A}_c\)). Stacking all \(3N\) linearized constraints for \(N\) ACs yields \[\label{eq:linear95system} \mathbf{J}(\mathbf{R}, \mathbf{t})\;\mathbf{\theta} = -\mathbf{r}_0(\mathbf{R}, \mathbf{t}),\tag{13}\] where \(\mathbf{r}_0\) collects the GS residuals (evaluating each constraint at \(\mathbf{\theta}\!=\!0\)) and \(\mathbf{J}\) is the \(3N \!\times\! 12\) Jacobian matrix. The system is linear in \(\mathbf{\theta}\) but nonlinear in \((\mathbf{R}, \mathbf{t})\).

Eliminating the RS parameters via null-space projection. The key idea of our solver is to eliminate the 12 RS unknowns \(\mathbf{\theta}\) from the linear system 13 and obtain conditions that constrain only the 5 pose unknowns \((\mathbf{R}, \mathbf{t})\).

With \(N = 7\) ACs, the system 13 has \(3 \times 7 = 21\) rows and 12 columns. It is overdetermined in \(\mathbf{\theta}\): there are more equations than unknowns. Such a system has a solution only if the right-hand side \(-\mathbf{r}_0\) lies in the column space of \(\mathbf{J}\). Equivalently, \(\mathbf{r}_0\) must be orthogonal to every vector in the left null space of \(\mathbf{J}\). Let \(\mathbf{U}_\perp \in \mathbb{R}^{21 \times 9}\) be an orthonormal basis for this \(21 - 12 = 9\)-dimensional subspace. Then 13 has a solution if and only if \[\label{eq:consistency} \mathbf{U}_\perp^\top \mathbf{r}_0(\mathbf{R}, \mathbf{t}) = \mathbf{0}.\tag{14}\] This projects out the 12 RS unknowns entirely, yielding 9 polynomial equations in the 5 pose unknowns \((\mathbf{R}, \mathbf{t})\) alone. Once a pose satisfying 14 is found, the RS parameters are recovered from 13 by least squares fitting.

Fixed null-space basis. Strictly, \(\mathbf{U}_\perp\) depends on \((\mathbf{R}, \mathbf{t})\) through \(\mathbf{J}\), which would make 14 implicitly nonlinear in the pose. We avoid this complication by computing \(\mathbf{U}_\perp\) once at a fixed reference rotation \(\mathbf{R}_\mathrm{ref} = \mathbf{I}\) (identity) and a generic translation. This is an approximation, justified by two observations. First, \(\mathbf{J}\) depends on the pose only through the linearization point of the RS model, and its left null space varies smoothly – so moderate deviations from \(\mathbf{I}\) preserve the rank structure. Second, we verify empirically that \(\mathbf{R}_\mathrm{ref} = \mathbf{I}\) yields equal or better numerical conditioning than recomputing \(\mathbf{U}_\perp\) at the initial 5-point estimate, producing a success rate above 85% for rotation errors below \(1^\circ\) on synthetic data. A pose-dependent \(\mathbf{U}_\perp\) would moreover break the linear-in-\(\mathbf{t}\) factorization that yields the clean \(\mathbf{G}_\mathrm{poly}\) structure of 15 .

Polynomial formulation. The 9 consistency conditions 14 involve the rotation \(\mathbf{R}\) and translation \(\mathbf{t}\), which we now parameterize to obtain a polynomial system. We use the Cayley parameterization \(\mathbf{R}(\mathbf{s}) = (\mathbf{I} - [\mathbf{s}]_{\times})(\mathbf{I} + [\mathbf{s}]_{\times})^{-1}\), where \(\mathbf{s} = (s_1, s_2, s_3) \in \mathbb{R}^3\), and write the translation as \(\mathbf{t} = (1, u, v)^\top\) (up to scale; this assumes \(t_x \neq 0\), which holds generically and can be ensured by a coordinate permutation when \(|t_x|\) is small).

A crucial simplification comes from the fact that \(\mathbf{r}_0\) depends linearly on \(\mathbf{t}\). This means 14 can be factored as \[\label{eq:G95system} \mathbf{G}_\mathrm{poly}(\mathbf{s}) \begin{pmatrix}1 \\ u \\ v\end{pmatrix} = \mathbf{0},\tag{15}\] where \(\mathbf{G}_\mathrm{poly}(\mathbf{s})\) is a \(9 \times 3\) matrix whose entries are degree-2 polynomials in \(\mathbf{s}\). (The Cayley parameterization introduces a common denominator \(d(\mathbf{s}) = 1 + \|\mathbf{s}\|^2\), which we absorb into \(\mathbf{G}_\mathrm{poly}\) to clear fractions.) We determine \(\mathbf{G}_\mathrm{poly}\) numerically: each entry has 10 monomials \(\{1, s_1, s_2, s_3, s_1^2, s_1 s_2, \ldots, s_3^2\}\), so evaluating 14 at 20 random \(\mathbf{s}\)-samples and solving a \(20 \times 10\) least-squares system per entry recovers the polynomial coefficients (to machine precision).

Eliminating the translation via minors. The system 15 states that \((1, u, v)^\top\) lies in the null space of the \(9 \times 3\) matrix \(\mathbf{G}_\mathrm{poly}(\mathbf{s})\). A nontrivial null vector exists if and only if \(\mathbf{G}_\mathrm{poly}\) has rank at most 2, all its \(3 \times 3\) subdeterminants (minors) vanish. To work with a smaller set of minors, we first reduce from 9 rows to 5 by forming 5 random linear combinations (with i.i.dGaussian coefficients), yielding a \(5 \times 3\) matrix \(\hat{\mathbf{G}}(\mathbf{s})\) with degree-2 entries. By Bézout’s theorem [30], the solution set is independent of the (generic) choice of combination coefficients. We reduce to \(5\) rows rather than fewer because \(5\times3\) is the smallest reduction whose minor ideal is zero-dimensional: a \(4\times3\) reduction leaves a positive-dimensional solution set in \(\mathbf{s}\). We then require all \(\binom{5}{3} = 10\) maximal minors of \(\hat{\mathbf{G}}\) to vanish. Each \(3 \times 3\) determinant has degree \(3 \times 2 = 6\) in \(\mathbf{s}\). A key algebraic observation simplifies this system: every minor is divisible by the Cayley denominator \(d(\mathbf{s}) = 1 + \|\mathbf{s}\|^2\). This occurs because \(\mathbf{G}_\mathrm{poly}\) was constructed by multiplying the rational matrix \(\mathbf{G}(\mathbf{s})\) by \(d(\mathbf{s})\); at the complex roots of \(d(\mathbf{s}) = 0\), the Cayley rotation is undefined (it corresponds to a \(180^\circ\) rotation), and the original constraints impose no condition on \((u,v)\), so \(\hat{\mathbf{G}}\) must drop rank there, forcing \(d(\mathbf{s})\) to divide every maximal minor. We verify this computationally by evaluating each minor at random complex points on the variety \(\{d(\mathbf{s}) = 0\}\), confirming vanishing to machine precision (\(\sim\! 10^{-14}\)), while \(d(\mathbf{s})^2\) does not divide the minors.

After dividing out \(d(\mathbf{s})\), we obtain 10 polynomial equations of degree 4 in \(\mathbf{s} = (s_1, s_2, s_3)\). The number of isolated solutions is determined by the Hilbert function [30] of the ideal, which stabilizes at \(H = 20\) (verified by computing the rank of Macaulay matrices at successive degrees). This establishes the algebraic degree of the system as 20.

Action matrix solver. We extract all 20 solutions using action matrices [30], a standard technique in computational algebraic geometry for solving zero-dimensional polynomial systems. The idea is to construct a matrix whose eigenvalues are the coordinates of the solutions.

We build the Macaulay matrix at extension degree \(d_\mathrm{ext} = 5\), which has dimensions \(40 \times 56\). This matrix is formed by multiplying each of the 10 degree-4 polynomials by the 4 monomials \(\{1, s_1, s_2, s_3\}\) (degree \(\leq 1\)), producing 40 rows; columns index all \(\binom{5+3}{3} = 56\) monomials of degree \(\leq 5\) in \((s_1, s_2, s_3)\). The SVD of this matrix reveals a clear gap at the 36th singular value (ratio \(\sigma_{36}/\sigma_{37} > 10^3\)), confirming a 20-dimensional null space \(\mathbf{V}_\mathrm{null} \in \mathbb{R}^{56 \times 20}\) that represents the quotient algebra of the ideal. For each variable \(s_k\), the action matrix is \[\label{eq:action} \mathbf{M}_k = \mathbf{V}_\mathrm{null}^\top\, \mathbf{S}_k\, \mathbf{V}_\mathrm{null} \in \mathbb{R}^{20 \times 20},\tag{16}\] where \(\mathbf{S}_k\) is the \(56 \times 56\) monomial shift matrix that maps each basis monomial \(m\) to \(s_k \cdot m\) (or to zero if \(\deg(s_k \cdot m) > 5\)). The eigenvalues of \(\mathbf{M}_k\) are precisely the \(s_k\)-coordinates of the 20 solutions. Since the three action matrices commute, they can be simultaneously diagonalized: eigendecomposing \(\mathbf{M}_1\) and applying the same eigenvector transform to \(\mathbf{M}_2\) and \(\mathbf{M}_3\) yields the complete triples \((s_1^{(i)}, s_2^{(i)}, s_3^{(i)})\) for \(i = 1, \ldots, 20\).

Solution recovery. For each real Cayley vector \(\mathbf{s}^{(i)}\), the translation parameters \((u, v)\) are recovered from the overdetermined system 15 via least squares, and the pose is computed as \(\mathbf{R} = (\mathbf{I} - [\mathbf{s}]_{\times})(\mathbf{I} + [\mathbf{s}]_{\times})^{-1}\), \(\mathbf{t} = (1, u, v)^\top / \|(1, u, v)\|\). Solutions are ranked by the polynomial residual \(\|\mathbf{G}_\mathrm{poly}(\mathbf{s})(1, u, v)^\top\|\), which consistently identifies the correct solution. The RS parameters \(\mathbf{\theta}\) are then recovered from 13 by least squares.

Computational cost. The algebraic solver runs in \({\sim}1.2\) ms in C++ (null space \(0.04\), \(\mathbf{G}_\mathrm{poly}\) fitting \(0.2\), minors and \(d(\mathbf{s})\) division \(0.02\), \(40\times56\) SVD \(0.3\), action matrices and eigendecomposition \(0.6\) ms). Though slower than the microsecond solvers ideal for RANSAC inner loops, the reduced sample size (\(k{=}7\) vs.\(20\)-\(44\)) more than compensates via far fewer iterations.

Degeneracies. Null-space elimination requires \(\mathbf{J}\) to have full column rank (12); this fails for degenerate samples (all 7 ACs on one row, where the \(\tau\)-dependent terms vanish). Such cases are rare in RANSAC and are detected via the SVD gap of the \(40\times56\) Macaulay matrix – if absent, the solver returns nothing and RANSAC proceeds.

Remark: 6-AC solver. Each AC gives 3 constraints, so \(N=5\) ACs underdetermine the 17-DoF system while \(N=6\) overdetermine it by one, making 6 ACs theoretically sufficient. However, the resulting \(6\times3\) matrix is too small for the minor-based elimination above; a hidden-variable alternative [26] instead suffers from a positive-dimensional spurious component (46-dimensional null space) that destabilizes extraction and costs \({\sim}55\) ms per call – unsuitable for RANSAC (full derivation in the supplementary material).

4.3 Integration into RANSAC↩︎

We integrate the 7-AC solver into SupeRANSAC [31] with local optimization.

Hypothesis generation. For each RANSAC iteration, we draw 7 ACs and run: (1) Nistér’s 5-point algorithm [2] on the first 5 point coordinates, selecting the best \(\mathbf{E}\) via the 6th and 7th ACs and decomposing into \((\mathbf{R}, \mathbf{t})\); then (2) the action-matrix solver (4.2), producing up to 20 candidates filtered by cheirality and physical RS parameter bounds. A GS fallback (\(\mathbf{\theta} = \mathbf{0}\)) is always included. Models are scored via the RS Sampson distance [5] \(d_S^2 = ((\mathbf{q}_2^\top \tilde{\mathbf{E}}_i\, \mathbf{q}_1)^2) / (\|\tilde{\mathbf{E}}_i\, \mathbf{q}_1\|_{1:2}^2 + \|\tilde{\mathbf{E}}_i^\top \mathbf{q}_2\|_{1:2}^2)\), where \(\tilde{\mathbf{E}}_i = \tilde{\mathbf{E}}(\tau_{1,i}, \tau_{2,i})\) is the essential matrix of pair \(i\).

Non-minimal refinement. The best hypotheses are refined via joint Levenberg–Marquardt (LM) over all 17 parameters on the inlier set, minimizing \[\label{eq:lm95cost} C = \sum_{i=1}^{N_\mathrm{in}} \bigl(r_{0,i}^2 + w_\mathrm{ac}^2\, r_{1,i}^2 + w_\mathrm{ac}^2\, r_{2,i}^2\bigr),\tag{17}\] where \(r_{0,i}\) is the epipolar residual 5 and \(r_{1,i}, r_{2,i}\) the affine residuals 8 –9 of pair \(i\), each evaluated with its own \(\tilde{\mathbf{E}}_i\) under the full nonlinear RS model. All three residuals are computed on normalized image coordinates (\(\mathbf{K}^{-1}\mathbf{q}\)) and thus share a common scale; we keep the affine terms in algebraic form since, unlike the epipolar residual, they have no direct point-to-line distance analogue. The weight \(w_\mathrm{ac}\) balances the affine against the epipolar terms: all reported results use \(w_\mathrm{ac}=1\), and the pose AUC is insensitive to this choice for \(w_\mathrm{ac}\in[0.5,2]\); a principled, data-driven alternative sets \(w_\mathrm{ac}\) to the ratio of the held-out standard deviations of the epipolar and affine residuals.

Handling the \(\mathbf{v}\)-\(\mathbf{t}\) coupling. The translational velocity \(\mathbf{v}_k\) is poorly separated from \(\mathbf{t}\) through epipolar constraints alone [5], [18], making the LM Jacobian ill-conditioned along \(\mathbf{t}\). We apply mild damping \(\lambda_v \mathbf{I}\) on the \(\mathbf{v}\)-blocks, biasing toward small velocities. The affine residuals additionally help alleviate this coupling, as they depend on \(\partial\tilde{\mathbf{E}}/\partial\tau_k\) and thus provide information to distinguish \(\mathbf{v}_k\) from \(\mathbf{t}\): while epipolar constraints measure only the projection of motion along epipolar lines – where \(\mathbf{v}\) and \(\mathbf{t}\) produce nearly identical effects – the AC constraints capture the spatial gradient of this projection across rows, which varies differently with \(\mathbf{v}\) (row-dependent) than with \(\mathbf{t}\) (constant).

4.4 Physically Feasible RS Parameters↩︎

The RS motion parameters \(\mathbf{\omega}_k\) and \(\mathbf{v}_k\) represent the total rotation and translation accumulated during the sensor readout, so their physical magnitudes are tightly constrained. Since the model parameters relate to their physical counterparts as \(\|\mathbf{\omega}\|_\mathrm{model} = \|\mathbf{\omega}\|_\mathrm{phys} \cdot t_\mathrm{ro}\) and \(\|\mathbf{v}\|_\mathrm{model} = \|\mathbf{v}\|_\mathrm{phys} \cdot t_\mathrm{ro}\), even an aggressively maneuvering drone (angular velocity \(\sim\)​10 rad/s, translational velocity \(\sim\)​30 m/s) with a typical readout time \(t_\mathrm{ro} \approx 30\) ms yields \(\|\mathbf{\omega}\| \leq 0.3\) rad (\(\sim\)​17\(^\circ\)) and \(\|\mathbf{v}\| \leq 0.9\). For handheld cameras, the values are 1–2 orders of magnitude smaller. Notably, while \(\|\mathbf{\omega}\|\) remains small across all scenarios, \(\|\mathbf{v}\|\) can reach \({\sim}0.9\) m for fast-moving platforms, underscoring the importance of accurately estimating \(\mathbf{v}\) – which, as we show in 5.1, is poorly conditioned from point correspondences alone. This has two important consequences for our solver.

Justification of linearization. Since the RS parameters are small, the nonlinear terms in the epipolar constraint – which scale as \(\tau^2 \|\mathbf{\omega}\|^2 \leq 0.25 \cdot 0.02 = 5 \times 10^{-3}\) – are 2–3 orders of magnitude below typical measurement noise. The linearization in \(\mathbf{\theta}\) used by our solver (4.2) is therefore an excellent approximation, not merely a practical heuristic.

Early rejection. The physical constraints on \(\mathbf{\theta}\) provide a useful sanity check during RANSAC: candidate models with \(\|\mathbf{\omega}\| > 0.5\) rad or unreasonably large \(\|\mathbf{v}\|\) can be discarded, avoiding unnecessary scoring over the full correspondence set.

5 Experiments↩︎

We evaluate the proposed RS-7AC solver in three settings: (i) controlled synthetic experiments that isolate the effect of individual noise sources on solver accuracy, (ii) real-world experiments on the TUM RS dataset [1] within a full RANSAC pipeline, and (iii) a test on the global-shutter EuRoC MAV dataset [13] – the special case of zero readout time – to verify the method does not degrade in the absence of RS distortion. We compare against GS-5PC (Nistér’s 5-point algorithm [2], which ignores RS), GS-2AC (the 2-AC essential matrix solver of Barath and Hajder [8], which also ignores RS but uses affine correspondences), and the RS-20PC and RS-44PC solvers of Dai et al. [5] (linearized and GN-refined).

5.1 Synthetic Experiments↩︎

We generate synthetic RS two-view scenes (50 random 3D points; two RS cameras with \(f_x\!=\!f_y\!=\!500\) px, \(640\times480\); random relative pose with rotation \(\leq10^\circ\) and forward-dominant translation; RS motion scaled by a factor \(\alpha\) applied to both \(\mathbf{\omega}_k\) and \(\mathbf{v}_k\)). Ground-truth affine frames follow from central-finite-difference differentiation of the full RS projection (including the iterative row solve): \(\mathbf{A}_c = (\partial\mathbf{q}_2/\partial\mathbf{X}) (\partial\mathbf{q}_1/\partial\mathbf{X})^{\dagger}\).

Each solver receives its minimal sample (5/20/44 PCs for GS-5PC/RS-20PC/RS-44PC, 7 ACs for RS-7AC) with oracle model selection; since minimal models are too noisy to compare directly, the best is refined on all 50 correspondences by joint LM, measuring each solver’s quality as a RANSAC initialization. RS-7AC refines with the combined cost 17 (\(w_\mathrm{ac}=1\)), the others with epipolar residuals only. We report median errors over 500 trials.

We sweep (1) point noise \(\sigma_p \in [0, 3]\) px (fixed \(\alpha = 0.5\)), (2) affine noise \(\sigma_a \in [0, 0.1]\) (fixed \(\sigma_p = 0.5\) px, \(\alpha = 0.5\)), and (3) RS magnitude \(\alpha \in [0, 3]\) (fixed \(\sigma_p = 0.5\) px, \(\sigma_a = 0.01\)), where \(\alpha\) scales both \(\mathbf{\omega}_k\) and \(\mathbf{v}_k\) simultaneously. Affine noise is additive Gaussian on each entry of the \(3 \times 2\) affine matrix. The swept range is calibrated to real data: \(\sigma_a \approx 0.05\) matches the median AC residual of AffNet and \(\sigma_a \approx 0.1\) that of RoMa on TUM-RS (supplementary material), so the tested noise levels reflect those of practical matchers.

3 shows the results. For pose estimation (top two rows), RS-7AC achieves competitive pose accuracy despite using only 7 correspondences versus 20-44. At moderate noise (\(\sigma_p = 0.5\) px, \(\alpha = 0.5\)), the median rotation error is \(0.65^\circ\) for RS-7AC versus \(0.46^\circ\) for RS-44PC and \(4.21^\circ\) for GS-5PC. RS-44PC benefits from its larger sample in this oracle setting, but the gap is small and, as we show in 5.2, is more than offset by the RANSAC advantage of the smaller sample size in real-world conditions. The RS-aware methods degrade gracefully with increasing RS magnitude, whereas GS-5PC, which ignores RS, accumulates systematic bias. For RS parameter estimation (bottom two rows), RS-7AC exhibits \({\sim}2\times\) higher angular velocity error \(\mathbf{\omega}\) than the point-based baselines, as the 7-AC algebraic solver provides a less accurate \(\mathbf{\omega}\) initialization than the overdetermined linear systems of RS-20PC and RS-44PC. However, the translational velocity \(\mathbf{v}\) reveals the opposite trend: RS-20PC and RS-44PC, which rely solely on point correspondences, suffer from the \(\mathbf{v}\)-\(\mathbf{t}\) coupling discussed in 4.3, yielding median velocity errors of \(\sim\)​25 – far worse than predicting zero. RS-7AC, leveraging affine constraints in both estimation and refinement, achieves \({\sim}3\times\) lower velocity error (\(\sim\)​10), confirming that ACs provide information about \(\mathbf{v}\) that PCs alone cannot resolve.

A direct comparison of raw solver outputs is not meaningful here, as the methods consume different inputs (7 ACs vs. or 44 PCs); the oracle setup instead measures each solver’s quality as an initialization for refinement. Under real RANSAC with outliers (1), RS-7AC outperforms the baselines on both \(\mathbf{\omega}\) and \(\mathbf{v}\), as the large samples of RS-20PC and RS-44PC cripple clean-sample selection.

5.2 Real-World Experiments↩︎

We evaluate on the TUM-RS dataset [1] (10 RS fisheye sequences with motion-capture ground truth), testing all 10 sequences at strides of 10 and 20 frames (increasing baseline and RS effect). We extract ACs with two feature types: (i) Key.Net [32] + AffNet [11] + HardNet [33], a classical pipeline (Key.Net keypoints, AffNet local affine shape, HardNet descriptor, mutual-NN ratio matching), with \(\mathbf{A}_c\) from the matched affine shapes; and (ii) RoMa [34], a dense matcher whose pixel-level warp field we differentiate (central finite differences) to get a per-point \(2\times2\) Jacobian. Since every warp-field sample yields one AC, \(\#\)ACs \(=\) \(\#\)PCs at no extra cost – ACs are thus not fewer than PCs for dense matchers; their per-point accuracy is quantified in the supplementary material. All methods run in the same SupeRANSAC [31] pipeline (PROSAC sampling [35], MAGSAC scoring [29], nested local optimization). We report pose AUC at \(5^\circ\), \(10^\circ\), and \(20^\circ\), the per-pair error being \(\max(\epsilon_R,\epsilon_t)\).

1 shows the results. The proposed RS-7AC solver consistently outperforms all baselines by a significant margin. At stride 10, RS-7AC achieves an AUC@\(5^\circ\) of 0.502, improving over GS-5PC (0.428) by 17% relative and over RS-44PC (0.267) by 88%. The advantage persists at stride 20, where the larger baseline amplifies the RS effect.

The strong performance of the GS methods over the Dai et al.solvers stems from sample size: drawing an all-inlier sample of size \(k\) at outlier ratio \(\epsilon\) has probability \((1-\epsilon)^k\), which at \(\epsilon=30\%\) drops from \(0.08\) for \(k=7\) to \(\sim\!10^{-7}\) for \(k=44\), crippling RANSAC for the 20- and 44-PC solvers. GS-2AC [8] benefits from an even smaller sample (\(k{=}2\)) but lacks RS modeling. Our 7-AC sample thus combines small-sample RANSAC efficiency with RS-aware modeling.

Runtime. RS-20PC and RS-44PC are by far the slowest (13–46 s) due to their large samples; RS-7AC runs in 3.7 s (AffNet) and 7.5 s (RoMa) – only \({\sim}2\times\) slower than GS-5PC despite a 17-DoF vs.-DoF problem, thanks to its small sample. GS-2AC is fastest (\({\sim}0.3\)-\(1.3\) s) but lacks RS modeling.

Global-Shutter Special Case. To verify that the RS solver does not degrade without RS distortion, we evaluate on the EuRoC MAV dataset [13] (six indoor global-shutter sequences, 752\(\times\)​480, 20 fps, three from Vicon Room 1 and three from Machine Hall, with Vicon ground truth), using RoMa features at strides 10 and 20. As the camera is global-shutter, the RS parameters should be near-zero, and pose accuracy measures how gracefully the method handles their absence.

2 shows the results. The proposed solver achieves similar pose accuracy to the GS baselines, demonstrating that it gracefully handles the GS special case. Notably, it correctly recovers near-zero RS parameters (\(\epsilon_\omega \approx 0.01\) rad, \(\epsilon_v \approx 0.03\)), confirming that the solver does not introduce spurious distortions when RS effects are absent. In contrast, the Dai et al.solvers yield much higher RS parameter errors (\(\epsilon_\omega \approx 0.04\)-\(0.08\) rad, \(\epsilon_v \approx 10\)-\(20\)), as their large minimal samples make RANSAC less likely to find clean inlier sets even in the GS regime.

6 Conclusion↩︎

We introduced affine correspondences into rolling shutter two-view geometry and developed a linearized 7-AC solver (degree 20, 1.8 ms) that reduces the RANSAC sample from 20 to 7, making RS-aware robust estimation practical. On TUM-RS, the method achieves the best pose accuracy among all baselines and substantially improves translational velocity estimation, which is poorly conditioned from point correspondences alone. On the global-shutter EuRoC MAV dataset, the solver handles the GS special case gracefully, being comparable to the GS 5-point algorithm while correctly recovering near-zero RS parameters.

References↩︎