scott2003view

View Planning for Automated Three-Dimensional Object Reconstruction and Inspection

Authors: Scott, Roth, Rivest · Year: 2003 · Venue: ACM Computing Surveys 35(1):64–96 Raw: accepted manuscript (NRC 45866) — read live; not yet marker-converted into Docs/raw/md/ (LAN cluster down 2026-07-04).

Summary

The canonical survey of the view planning problem (VPP): given a range sensor and a positioning system, find a suitably small set of sensor poses/configurations that satisfies a specified 3D reconstruction or inspection goal. Scott et al. frame the pipeline (plan views → move → scan → register → integrate), argue that scan/register/integrate are adequately semiautomated while view planning remains the open problem, and then organize and critique the field against an explicit set of requirements. This is the taxonomy paper our inspection/view-planning chapter cites for the vocabulary (NBV, model-based vs non-model-based, reconstruction vs inspection) and for the theoretical reduction of view planning to set covering.

Key Claims

• The VPP is the task of computing a minimal set of views for a reconstruction/inspection goal; it is the field’s open problem, unlike the (semi-)automated scan-register-integrate tasks (Abstract, Sec. 1).
• View planning methods split into two top-level categories: model-based (an a priori object/scene model is available, Sec. 5) and non-model-based (no prior model — the incremental “next-best-view” setting, Sec. 6).
• Non-model-based methods are further classified by the domain of reasoning about viewpoints — surface-based, volumetric, or global (Sec. 6, Fig. 5).
• The VPP is isomorphic to the set-covering problem (Tarbox & Gottschlich 1995), hence NP-complete; Scott et al. later express it as covering the rows of a binary measurability matrix by a minimal subset of its columns, with an integer-programming formulation adding a registration constraint (Sec. 9.1).
• Reconstruction vs inspection are distinguished goals: reconstruction builds a model to a sampling-density/precision spec of an initially unknown surface; inspection verifies an existing model — Scott et al. push performance-oriented view planning driven by an input specification for sampling precision and density, rather than mere full-surface coverage.
• Viewpoints are computed by synthesis (a minority; jointly optimize over viewpoint space, but suffer nonlinearity/convergence issues) or, far more commonly, generate-and-test (discretize viewpoint space, then select a subset by optimization) (Sec. 9.2).
• The field then lacked a comprehensive theoretical foundation covering all constraints, error mechanisms, and principled sampling of surface and viewpoint space (Sec. 9–10).

Method

This is a survey/critique, not a new derivation. Its organizing artifacts:

• Imaging environment model — range camera (active triangulation sensors emphasized) + calibrated positioning system + object; a viewpoint defines a 3D frustum (Sec. 2).
• View planning requirements — assumptions, constraints and performance measures against which methods are judged (Sec. 3).
• Measurability matrix $M(i,j)$ — a binary visibility/measurability mapping between viewpoint space and object-surface space; covering all surface elements = covering all matrix rows → set cover (Sec. 5, 9.1).
• Positional space (PS) — Pito’s intermediate representation encoding, per surface element, the sensor directions able to scan it (via a positional-space direction, PSD) so the NBV can be read off overlap of surface “needs” and sensor “potential” (Sec. 6.1.x, Fig. 8).
• The art gallery problem (minimum guards covering a polygon) is invoked as the 2D visibility-coverage analogue of view planning (Sec. 5).

Relevance to thesis

This is the application-side canon for our inspection chapter. Our scorer selecting views on a target-satellite mesh is a view planning problem in Scott et al.’s sense; their categories set the vocabulary we must use with provenance — next-best-view, model-based vs non-model-based, reconstruction vs inspection, surface/volumetric/global reasoning, generate-and-test vs synthesis. Two hooks are directly load-bearing: (1) the set-cover / measurability-matrix reduction gives a principled, citable formulation for “select a minimal set of mesh views that covers the surface”; (2) performance-oriented view planning (plan to a sampling precision/density spec, not just coverage) matches an inspection mission whose goal is a quality-bounded model. Because a free-flying 6-DOF base can realize a large, near-continuous viewpoint space, the survey’s generate-and-test discretization and its warning about over-constrained viewpoint spaces are directly relevant to how we sample candidate views. Regime caveat: the paper assumes a small object and a bench-scale positioning system; it is agnostic to platform dynamics, so it constrains what to look at, not how to fly there (that is the coverage-path / motion-planning layer — see galceran2013survey).

Connections

Topics: motion_planning · d_optimality · next_best_view (PAGE NEEDED) · coverage_path_planning (PAGE NEEDED) · Sources: connolly1985determination · galceran2013survey

Key Equations / Quotes

“view planning remains an open problem—that is, the task of finding a suitably small set of sensor poses and configurations for specified reconstruction or inspection goals.” (Abstract)

“One of the earliest papers on view planning was by Connolly [1985]. He appears to have first coined the term ‘next-best-view’ (NBV).” (Sec. 6.2.2)

“Tarbox and Gottschlich [1995] introduced the measurability matrix concept in a model-based approach to inspection. They showed the VPP to be isomorphic to the set covering problem which is known to be NP-complete.” (Sec. 9.1)

Open Questions

• The survey reports no comprehensive theory encompassing all constraints, error mechanisms, and principled sampling — is the set-cover/measurability formulation the right backbone to extend to a 6-DOF flying inspector, or does continuous viewpoint space demand a synthesis formulation?
• All methods surveyed assume bench-scale object-sensor geometry; how does the taxonomy lift when the “positioning system” is a fully-actuated free-flying base with its own dynamics and singularities?
• Performance-oriented planning ties views to a sampling precision/density spec — what is the analogous quality spec for a satellite-inspection deliverable (coverage completeness, pose-estimation accuracy)?