Shape and motion from image streams under orthography: a factorization method

article1992IJCV2,633 citations

Introduces a structure-from-motion method that exploits the rank-3 property of orthographic feature trajectories to directly factor image stream measurements into 3D object shape and camera rotation using singular value decomposition.

Listen

Recovering three-dimensional object shape and camera motion from video sequences has traditionally been an unstable and noise-sensitive task. Standard methods rely on perspective projection and calculate depth relative to the camera, which causes small sensor noise to create large reconstruction errors—especially when objects are distant relative to their size, as in site modeling. The article evaluates and demonstrates a factorization method that recovers shape and motion directly under orthographic projection (parallel rays) without using retinotopic depth as an intermediate calculation.

The authors tested this approach by tracking feature points across dense image streams in both controlled laboratory settings and real-world outdoor environments. By organizing the horizontal and vertical image coordinates into a large measurement matrix centered at the object's centroid, the method uses standard matrix decomposition techniques (singular value decomposition) to factor image data directly into separate camera rotation and object shape matrices. To address occlusions and tracking loss where features appear or disappear, the authors introduced an iterative propagation technique to grow a complete solution from partial data.

The evaluation yielded several key findings regarding accuracy and stability. In laboratory testing on a building model with ground-truth data, the method recovered camera rotation with an average error of only 0.2 degrees (peaking below 0.4 degrees) and reconstructed physical dimensions to within approximately one millimeter of actual ruler measurements. Outdoor testing with a hand-held camera rotating across roughly 15 degrees proved that the technique robustly reconstructs structure despite jittery motion and image noise without requiring artificial motion smoothing. In occlusion tests with a rotating sphere, the algorithm successfully recovered complete motion and three-dimensional shape even when roughly 84 percent of the measurement matrix entries were missing.

These findings demonstrate that structure-from-motion algorithms can achieve high numerical stability and computational efficiency by reformulating the problem in world-centered coordinates. Eliminating the need to differentiate small translations from small rotations cuts computational instability and reduces the risk of artifact-driven errors in computer vision pipelines. To achieve fully autonomous deployment, next steps should focus on developing automated methods to filter out false or non-rigid features, such as reflections and independent background movement. The primary boundary condition is that the method assumes orthographic projection, meaning camera translation along the line of sight must remain small relative to scene distance, though within these limits confidence in the resulting shape and motion estimates is exceptionally high.

Carnegie Mellon University Cornell University data stream orthography factorization methods factorization method orthographic projection motion estimation

Tomasi et al (1992).pdf

Paper: Least-Squares Fitting of Two 3-D Point Sets, K. S. Arun et al. (1987). This foundational paper establishes the singular value decomposition method for least-squares rigid body alignment of centered 3D point sets, providing essential mathematical tools used by factorization-based reconstruction.
Paper: Least-Squares Estimation of Transformation Parameters Between Two Point Patterns, S. Umeyama (1991). This work establishes exact SVD-based closed-form alignment between point sets while guaranteeing valid rotation constraints, forming crucial mathematical background for orthographic factorization.

Paper: An efficient solution to the five-point relative pose problem, D. Nistér (2004). This paper develops an efficient five-point relative pose solver to address calibrated perspective reconstruction beyond the orthographic assumption of the factorization method.
Paper: Modeling the World from Internet Photo Collections, Noah Snavely et al. (2008). This work scales structure-from-motion from video streams under controlled projection models to massive, unconstrained Internet photo collections using incremental reconstruction and bundle adjustment.
Paper: Structure-from-Motion Revisited, Johannes L. Schönberger et al. (2016). This paper modernizes full structure-from-motion pipelines to overcome robustness and completeness bottlenecks across unordered image datasets.
Paper: Building Rome in a day, Sameer Agarwal et al. (2009). This paper extends multi-view reconstruction into massive, distributed city-scale structure-from-motion across hundreds of thousands of unstructured images.
Paper: ORB-SLAM: A Versatile and Accurate Monocular SLAM System, Raul Mur-Artal et al. (2015). This work advances visual geometry into real-time simultaneous localization and mapping, solving sequential camera motion tracking and landmark reconstruction under perspective projection.
Paper: Unsupervised Learning of Depth and Ego-Motion from Video, Tinghui Zhou et al. (2017). This paper extends monocular motion and geometry recovery by replacing traditional geometric factorization and point tracking with unsupervised neural networks.

Cover for Shape and motion from image streams under orthography: a factorization method

Abstract

Inferring scene geometry and camera motion from a stream of images is possible in principle, but is an ill-conditioned problem when the objects are distant with respect to their size. We have developed a factorization method that can overcome this difficulty by recovering shape and motion under orthography without computing depth as an intermediate step.

An image stream can be represented by the 2F×P measurement matrix of the image coordinates of P points tracked through F frames. We show that under orthographic projection this matrix is of rank 3.

Based on this observation, the factorization method uses the singular-value decomposition technique to factor the measurement matrix into two matrices which represent object shape and camera rotation respectively. Two of the three translation components are computed in a preprocessing stage. The method can also handle and obtain a full solution from a partially filled-in measurement matrix that may result from occlusions or tracking failures.

The method gives accurate results, and does not introduce smoothing in either shape or motion. We demonstrate this with a series of experiments on laboratory and outdoor image streams, with and without occlusions.

Topics

data stream orthography factorization methods

Keywords

factorization method orthographic projection motion estimation feature tracking camera motion shape matrix scene geometry optical flow

1. Single-View Metrology (40 pts)
2. Mission Possible? (10 pts)
3. Epipolar Geometry (20 pts)
4. Affine Structure from Motion (30%)
Extra Problems (optional)
Vanishing Point Extra Credit (optional, worth 20 points total)

Knowls

Knowl 1 — Metric Rectification in Tomasi-Kanade Affine Factorization
model/method
In the Tomasi-Kanade affine structure from motion framework, singular value decomposition of the centered measurement matrix factors tracked feature trajectories across $F$ frames and $P$ 3D points into an affine motion matrix $\hat{R} \in \mathbb{R}^{2F \times 3}$ and an affine shape matrix $\hat{S} \in \mathbb{R}^{3 \times P}$ .

To eliminate the affine ambiguity and recover Euclidean metric structure, an invertible transformation $Q \in \mathbb{R}^{3 \times 3}$ is computed such that the metric motion is $R = \hat{R}Q$ and metric shape is $S = Q^{-1}\hat{S}$ . Let $\hat{\mathbf{i}}_f^T, \hat{\mathbf{j}}_f^T \in \mathbb{R}^{1 \times 3}$ denote the two rows of $\hat{R}$ for frame $f \in \{1, \dots, F\}$ . The corresponding metric camera coordinate axes $\mathbf{i}_f = Q^T \hat{\mathbf{i}}_f$ and $\mathbf{j}_f = Q^T \hat{\mathbf{j}}_f$ must satisfy the orthographic metric constraints: $\hat{\mathbf{i}}_f^T Q Q^T \hat{\mathbf{i}}_f = 1$ $\hat{\mathbf{j}}_f^T Q Q^T \hat{\mathbf{j}}_f = 1$ $\hat{\mathbf{i}}_f^T Q Q^T \hat{\mathbf{j}}_f = 0$

Defining the symmetric positive-definite matrix $L = Q Q^T \in \mathbb{R}^{3 \times 3}$ with 6 independent variables, these constraints formulate a linear system of equations: $\hat{\mathbf{i}}_f^T L \hat{\mathbf{i}}_f - \hat{\mathbf{j}}_f^T L \hat{\mathbf{j}}_f = 0$ $\hat{\mathbf{i}}_f^T L \hat{\mathbf{j}}_f = 0$ $\hat{\mathbf{i}}_f^T L \hat{\mathbf{i}}_f = 1$

After solving for $L$ via linear least squares, $Q$ is recovered via the Cholesky decomposition $L = Q Q^T$ . The third camera viewing axis for each frame is given by the cross product: $\hat{\mathbf{k}}_f = \frac{\mathbf{i}_f \times \mathbf{j}_f}{\|\mathbf{i}_f \times \mathbf{j}_f\|}$
Knowl 2 — Intrinsic Calibration and Rotation Estimation from Three Orthogonal Vanishing Points
model/method
Given three vanishing points $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3 \in \mathbb{R}^3$ in homogeneous image coordinates corresponding to three mutually orthogonal spatial directions $\mathbf{d}_1, \mathbf{d}_2, \mathbf{d}_3$ , camera intrinsic calibration and orientation can be determined under the assumption of zero skew and square pixels.

The camera calibration matrix is defined as: $K = \begin{bmatrix} f & 0 & u_0 \\ 0 & f & v_0 \\ 0 & 0 & 1 \end{bmatrix}$ where $f$ is the focal length in pixels and $(u_0, v_0)$ is the principal point (optical center).

The image of the absolute conic $\omega = (K K^T)^{-1}$ is given by: $\omega = \begin{bmatrix} 1/f^2 & 0 & -u_0/f^2 \\ 0 & 1/f^2 & -v_0/f^2 \\ -u_0/f^2 & -v_0/f^2 & (u_0^2 + v_0^2)/f^2 + 1 \end{bmatrix}$

Because the scene directions $\mathbf{d}_i \propto K^{-1} \mathbf{v}_i$ are mutually orthogonal ( $\mathbf{d}_i^T \mathbf{d}_j = 0$ for $i \neq j$ ), the vanishing points satisfy the linear constraints: $\mathbf{v}_i^T \omega \mathbf{v}_j = 0 \quad \text{for } (i,j) \in \{(1,2), (2,3), (1,3)\}$

Solving this system yields $f$ , $u_0$ , and $v_0$ . Once $K$ is known, the camera rotation matrix $R = [\mathbf{r}_1 \ \mathbf{r}_2 \ \mathbf{r}_3] \in SO(3)$ with columns aligned to the three vanishing directions is computed by normalizing the back-projected rays: $\mathbf{r}_i = \frac{K^{-1} \mathbf{v}_i}{\|K^{-1} \mathbf{v}_i\|}, \quad i \in \{1, 2, 3\}$
Knowl 3 — Single-View Height Estimation via Ground Vanishing Line
model/method
In a single perspective image of a scene containing a planar ground surface, the physical height $H$ of an object can be determined from a reference object of known height $H_0$ using the vanishing line of the ground plane (the horizon) and the vertical vanishing point.

Let $\mathbf{l}_{horiz} = [a, b, c]^T$ be the normalized horizon line satisfying $a u + b v + c = 0$ with $a^2 + b^2 = 1$ , determined from the cross product of two horizontal vanishing points $\mathbf{l}_{horiz} = \mathbf{v}_x \times \mathbf{v}_z$ . Let $\mathbf{v}_y$ be the vertical vanishing point.

For a target vertical object with ground contact base $\mathbf{b}$ and top point $\mathbf{t}$ , and a reference object with base $\mathbf{b}_0$ , top $\mathbf{t}_0$ , and known height $H_0$ :
1. The ground line passing through $\mathbf{b}_0$ and $\mathbf{b}$ is intersected with $\mathbf{l}_{horiz}$ to find the ground vanishing point $\mathbf{v}_{ground} = (\mathbf{b}_0 \times \mathbf{b}) \times \mathbf{l}_{horiz}$ .
2. The line connecting $\mathbf{v}_{ground}$ to $\mathbf{t}_0$ is intersected with the target object's vertical line $\mathbf{b} \times \mathbf{v}_y$ to obtain the reference height transferred to the target's distance, $\mathbf{t}_0'$ .
3. The physical height $H$ is computed from the cross-ratio of the collinear points $\{\mathbf{v}_y, \mathbf{t}, \mathbf{t}_0', \mathbf{b}\}$ scaled by $H_0$ . Similarly, the camera's height $H_c$ above the ground plane is determined using the cross-ratio between the base point, the horizon intersection on the vertical line, and $\mathbf{v}_y$ .
Knowl 4 — Feasibility of Projection Screens for Camouflage Under Pure Camera Rotation Versus Observer Translation
theoretical result
A planar projection screen displaying a background scene operates under different geometric constraints depending on observer motion:
1. Purely rotating camera without translation ( $\mathbf{t} = \mathbf{0}$ ): The image transformation between different orientations of a camera with a fixed center of projection is a 2D planar homography $H = K R K^{-1}$ . Because rays passing through the optical center do not exhibit motion parallax, a static projection of the background on a fixed screen perfectly reproduces the appearance for all camera pan, tilt, and roll angles without requiring real-time tracking of camera rotation.
2. Translating observer ( $\mathbf{t} \neq \mathbf{0}$ ): When a single-eyed observer translates, relative motion parallax is induced between foreground and background structures. Camouflaging the scene requires real-time 3D tracking of the observer's eye position to dynamically update the view-dependent planar homography projected on the screen.
3. Simultaneous camera and translating observer: A standard 2D projection screen displays a single radiometric image per surface element and cannot simultaneously generate two distinct view-dependent perspectives for two different centers of projection. Thus, it is geometrically impossible to simultaneously camouflage the screen for a static camera and a spatially separated moving observer using a single planar projection.
Knowl 5 — Robust Fundamental Matrix Estimation via RANSAC and Normalized 8-Point Algorithm
algorithm
Input: Matched 2D point correspondences $(p_i, p_i')$ where $p_i = (u_i, v_i, 1)^T$ and $p_i' = (u_i', v_i', 1)^T$ for $i = 1, \dots, N$ ; inlier threshold $\tau$ ; iteration count $K_{iter}$
Output: Fundamental matrix $F \in \mathbb{R}^{3 \times 3}$ with $\|F\|_F = 1$ , inlier index set $I^*$
Compute normalization matrices $T$ and $T'$ such that points $T p_i$ and $T' p_i'$ have zero mean and average distance $\sqrt{2}$ from the origin
$I^* = \emptyset$
for iter = 1 to $K_{iter}$ do
    Randomly select 8 correspondences
    Construct matrix $A \in \mathbb{R}^{8 \times 9}$ where row $k$ is $[\tilde{u}_k' \tilde{u}_k, \tilde{u}_k' \tilde{v}_k, \tilde{u}_k', \tilde{v}_k' \tilde{u}_k, \tilde{v}_k' \tilde{v}_k, \tilde{v}_k', \tilde{u}_k, \tilde{v}_k, 1]$
    Compute SVD $A = U D V^T$ and take candidate $\tilde{F}$ from the column of $V$ corresponding to the smallest singular value
    Enforce rank-2 constraint: compute SVD $\tilde{F} = U_F \text{diag}(\sigma_1, \sigma_2, \sigma_3) V_F^T$ and set $\tilde{F}_{rank2} = U_F \text{diag}(\sigma_1, \sigma_2, 0) V_F^T$
    Denormalize: $F_{cand} = (T')^T \tilde{F}_{rank2} T$

    current_inliers = empty set
    for $i = 1$ to $N$ do
        Compute symmetric epipolar distance $d_i = \frac{(p_i'^T F_{cand} p_i)^2}{(F_{cand} p_i)_1^2 + (F_{cand} p_i)_2^2} + \frac{(p_i'^T F_{cand} p_i)^2}{(F_{cand}^T p_i')_1^2 + (F_{cand}^T p_i')_2^2}$
        if $d_i < \tau$ then
            Add $i$ to current_inliers
        end if
    end for

    if length(current_inliers) > length( $I^*$ ) then
         $I^* = current_inliers$
    end if
end for
Re-estimate $\tilde{F}$ using all correspondences in $I^*$ with the normalized 8-point method and enforce rank 2
$F = (T')^T \tilde{F}_{rank2} T$
$F = F / \|F\|_F$
return $F$ , $I^*$
Knowl 6 — Automatic Orthogonal Vanishing Point Detection via RANSAC and Line Clustering
algorithm
Input: Line segments $L = \{(x_{k,1}, y_{k,1}, x_{k,2}, y_{k,2})\}_{k=1}^M$ ; inlier threshold $\epsilon$ ; iteration limit $N_{iter}$
Output: Vanishing points $V = [\mathbf{v}_X, \mathbf{v}_Y, \mathbf{v}_Z] \in \mathbb{R}^{3 \times 3}$ ; compatibility matrix $PrefMat \in \{0, 1\}^{M \times 3}$
Represent each line segment $k$ in homogeneous coordinates as $\mathbf{m}_k = (x_{k,1}, y_{k,1}, 1)^T \times (x_{k,2}, y_{k,2}, 1)^T$
$best\_score = 0$
for iter = 1 to $N_{iter}$ do
    Sample pairs of line segments and compute candidate vanishing points $\mathbf{v} = \mathbf{m}_a \times \mathbf{m}_b$
    Hypothesize three mutually orthogonal vanishing points $(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3)$ satisfying $\mathbf{v}_i^T \omega \mathbf{v}_j = 0$ for $i \neq j$ under an assumed optical center

    Compute binary inlier status for all segments: segment $k$ is compatible with $\mathbf{v}_j$ if the point-to-line distance from segment endpoints to the line joining $\mathbf{v}_j$ and segment midpoint is below $\epsilon$
     $score =$ sum of lengths of all inlier line segments across the three vanishing points

    if $score > best\_score$ then
         $best\_score = score$
         $V = [\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3]$
    end if
end for
Construct $PrefMat \in \{0, 1\}^{M \times 3}$ where $PrefMat(k, j) = 1$ if line $k$ is an inlier to $\mathbf{v}_j$
Refine each vanishing point $\mathbf{v}_j$ by solving least squares $\min_{\mathbf{v}_j} \sum_{k: PrefMat(k,j)=1} (\mathbf{m}_k^T \mathbf{v}_j)^2$
return $V$ , $PrefMat$

Coverage note — No substantial technical content from the problem set was omitted; all core problems—single-view metrology, intrinsic calibration and rotation from orthogonal vanishing points, homography-based projection camouflage analysis, robust fundamental matrix estimation, and Tomasi-Kanade affine factorization metric rectification—are fully covered.

References

1.Tomasi and Kanade. Shape and Motion from Image Streams under Orthography: a Factorization Method. 1992
2.Tardif J.-P., Non-iterative Approach for Fast and Accurate Vanishing Point Detection, 12th IEEE International Conference on Computer Vision, Kyoto, Japan, September 27 - October 4, 2009
3.B. Caprile, V. Torre, Using Vanishing Points for Camera Calibration, International Journal of Computer Vision, 1990

Citation

MLA

Tomasi, C., and T. Kanade. “Shape and Motion from Image Streams Under Orthography: A Factorization Method”. International Journal of Computer Vision, vol. 9, no. 2, 1992, pp. 137–54, https://doi.org/10.1007/bf00129684.

APA

Tomasi, C., & Kanade, T. (1992). Shape and motion from image streams under orthography: a factorization method. International Journal of Computer Vision, 9(2), 137–154. https://doi.org/10.1007/bf00129684

Chicago

Tomasi, C., and T. Kanade. 1992. “Shape and Motion from Image Streams Under Orthography: A Factorization Method”. International Journal of Computer Vision 9 (2): 137–54. https://doi.org/10.1007/bf00129684.

Harvard

Tomasi, C. and Kanade, T. (1992) “Shape and motion from image streams under orthography: a factorization method”, International Journal of Computer Vision, 9(2), pp. 137–154. Available at: https://doi.org/10.1007/bf00129684.

Vancouver

1. Tomasi C, Kanade T (1992) Shape and motion from image streams under orthography: a factorization method. International Journal of Computer Vision 9:137–154

BibTeX

@article{Tomasi_1992, title={Shape and motion from image streams under orthography: a factorization method}, volume={9}, ISSN={1573-1405}, url={http://dx.doi.org/10.1007/bf00129684}, DOI={10.1007/bf00129684}, number={2}, journal={International Journal of Computer Vision}, publisher={Springer Science and Business Media LLC}, author={Tomasi, Carlo and Kanade, Takeo}, year={1992}, month=Nov, pages={137–154} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Shape and motion from image streams under orthography: a factorization method

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Metric Rectification in Tomasi-Kanade Affine Factorization

Knowl 2 — Intrinsic Calibration and Rotation Estimation from Three Orthogonal Vanishing Points

Knowl 3 — Single-View Height Estimation via Ground Vanishing Line

Knowl 4 — Feasibility of Projection Screens for Camouflage Under Pure Camera Rotation Versus Observer Translation

Knowl 5 — Robust Fundamental Matrix Estimation via RANSAC and Normalized 8-Point Algorithm

Knowl 6 — Automatic Orthogonal Vanishing Point Detection via RANSAC and Line Clustering

References

Citation

BibTeX

Access the Paper