PaperlayerView exact revision on arXiv

Source-linked AI summary

Ground Sample Distance Constrained k-Coverage Viewpoint Planning via Set Multi-Cover Formulation

Waleed Bin Khalid, Chul Min Yeum

arXiv:2610.36450v1cs.RO

TL;DR

Aerial inspection needs viewpoints that satisfy image-resolution constraints while observing surface regions multiple times, a guarantee overlap-based pruning does not provide. The paper formulates GSD-constrained k-coverage as set multi-cover and applies dynamically weighted greedy selection, achieving full or near-full coverage with 3.00–16.39% more viewpoints than ILP across the evaluated settings.

  • Problem

    The task is selecting camera viewpoints that meet prescribed GSD bounds while observing surface voxels at least k times.

    Source: §I · p. 1

  • Method

    The method formulates viewpoint selection as set multi-cover and uses a dynamically weighted greedy rule that prioritizes coverage deficits and scarce viewing alternatives.

    Source: §IV · p. 4, §VIII · p. 7

  • Results

    3.00–16.39% more viewpoints than corresponding ILP solutions, while achieving full or near-full requested k-coverage across evaluated structures, voxel sizes, and coverage levels.

    Source: §VIII · p. 7, §VII · p. 7

  • Takeaways & Limitations

    Decoupling viewpoint selection from tour generation allows discrete coverage requirements to be evaluated independently of trajectory optimization.

    Source: §I · p. 1

    Evaluation assumes known, static geometry and modeled voxel-center sensing, covers only two structures, and does not assess UAV reachability or downstream reconstruction quality.

    Source: §VIII · p. 7

Abstract

from arXiv · show

Drone-based 3D reconstruction and inspection require viewpoints that satisfy image-quality constraints while observing each surface region multiple times, which overlap-based planning heuristics do not guarantee. We study ground sample distance (GSD)-constrained $k$-coverage viewpoint selection for structures represented by surface voxels. Candidate viewpoints are generated along outward surface directions, screened with distance, viewing-angle, field-of-view, and occlusion tests, and augmented for voxels with insufficient visibility. Selection is then posed as set multi-cover with per-voxel coverage demands. We propose a dynamically weighted greedy heuristic that prioritizes remaining coverage deficits and scarce viewing alternatives, and compare it with sequential overlap-based pruning and an integer linear programming (ILP) formulation on the same candidate pools. Across two structures, four voxel resolutions, and three coverage requirements, the proposed approach achieves full or near-full $k$-coverage with compact viewpoint sets, using only 3.00--16.39\% more viewpoints than ILP while offering an interpretable selection process based on coverage deficits and viewpoint availability.

I. INTRODUCTION

Aerial inspection needs viewpoints that meet image-quality constraints while observing each surface region repeatedly; overlap heuristics do not ensure prescribed per-region observation counts under sensing constraints. This work combines sensing-aware candidate generation, targeted augmentation, and set multi-cover selection for voxelized surfaces.

I. INTRODUCTION

  • Overlap-based planning does not directly enforce a prescribed observation count for each surface region, especially with self-occlusions and complex geometry.The cited 60–80% overlap recommendation is a global acquisition heuristic.Source: §I · p. 1
  • The method targets compact viewpoint sets satisfying prescribed GSD and k-coverage requirements for structures with known geometry.Each surface region is to be observed from at least k distinct viewpoints.Source: §I · p. 1
  • The framework generates sensing-compliant candidates and selects a smaller subset with a globally informed greedy heuristic, compared with ILP on the same candidate set.Viewpoint selection is decoupled from downstream tour generation.Source: §I · p. 1

II. RELATED WORK

  • Some existing systems couple viewpoint generation with trajectory optimization; this study examines viewpoint selection independently of that optimization.The related work also notes that overlap-pruning outcomes can depend on viewpoint ordering and overlap thresholds.Source: §II · pp. 1–2
  • Prior work addresses geometric coverage, sensing-aware planning, and combinatorial optimization, while this work integrates them for GSD-constrained k-coverage over voxelized surfaces.The integration includes targeted augmentation of undercovered regions and per-surface-region multi-cover requirements.Source: §II · pp. 1–2

III. VIEWPOINT GENERATION

The GSD formulation sets candidate distance using the prescribed GSD bound and a maximum oblique viewing angle. Viewpoints are placed along outward surface directions at the resulting perpendicular distance.

A. Ground Sample Distance (GSD) Formulation

  • The formulation evaluates GSD at each visible voxel center and constrains it not to exceed prescribed GSDmax.The adopted model fixes a maximum oblique angle α and computes the corresponding slant range Rs.Source: A. Ground Sample Distance (GSD)… · p. 2
  • The slant distance combines lateral offset d and perpendicular distance h, while w, θFOV, and α denote camera and viewing parameters.α is the angle between the camera viewing direction and the surface normal.Source: A. Ground Sample Distance (GSD)… · p. 2
  • Candidate viewpoints are placed at h = Rs cos(α) along the outward surface normal.Under this placement, the nominal nadir GSD is GSDset = GSDmax cos^2(α).Source: A. Ground Sample Distance (GSD)… · pp. 2–3

B. Voxelization

The method represents the input geometry with a uniform voxel grid and distinguishes exterior empty space from sealed interior cavities.

B. Voxelization

  • A point cloud or mesh is voxelized on a uniform 3D grid with selected voxel size s and computed voxel centers.Each voxel is indexed by (i, j, k), with its center determined from the grid origin and size.Source: B. Voxelization · p. 3

C. Labeling Exterior and Interior Space

  • A padded empty-cell boundary and corner-seeded flood-fill label reachable empty cells as exterior and unreached cells as interior cavities.The flood-fill traverses empty cells only.Source: C. Labeling Exterior and Interior Space · p. 3

D. Computing Normals

Surface-voxel normals are derived from exterior-facing faces, then used to place and orient initial viewpoints. A ray pre-filter removes viewpoints whose target line of sight is blocked.

D. Computing Normals

  • Voxel-sample normal averaging can be unstable when within-voxel sampling is sparse or uneven.The method instead computes normals from exterior-facing voxel faces.Source: D. Computing Normals · p. 3
  • The normal is the normalized sum of exterior-facing face normals, while voxels without such faces are classified as internal and receive no normal.Exterior-facing faces are identified from empty, exterior-labeled 6-connected neighbors.Source: D. Computing Normals · p. 3
  • When opposing exterior faces make the sum negligible, each face normal becomes a separate viewing direction for that voxel.This handles thin walls or edges while retaining outward-facing directions.Source: D. Computing Normals · p. 3

E. Generating Initial Viewpoints

  • An initial viewpoint is placed at the GSD-derived distance along the voxel normal, and its camera optical axis faces the generating surface element.Multi-normal voxels generate one viewpoint per normal direction.Source: E. Generating Initial Viewpoints · p. 3

F. Removing Blocked Viewpoints

  • A ray cast from each viewpoint toward its target voxel removes the viewpoint when a nearer occupied intersection blocks the line of sight.The described pre-filter uses a tolerance τ = s^(3/2) for voxel surface intersections.Source: F. Removing Blocked Viewpoints · p. 3

G. Assigning Visible Voxels to a Viewpoint and Identifying Undercovered Voxels

Candidate visibility is checked against the adopted geometric sensing constraints, then counted per voxel to identify where more viewpoints are needed.

G. Assigning Visible Voxels to a Viewpoint and Identifying Undercovered Voxels

  • Distance, viewing-angle, field-of-view, and occlusion tests determine whether a voxel is visible from a candidate viewpoint.The tests operate on voxel centers and approximate sensing compliance rather than guaranteeing it over each voxel’s entire surface.Source: G. Assigning Visible Voxels to a… · p. 3
  • SBW(v) counts candidate viewpoints that see voxel v; counts below k trigger targeted viewpoint augmentation.SBW(v) ≥ k indicates sufficient candidate visibility, 0 < SBW(v) < k indicates insufficient visibility, and SBW(v) = 0 indicates none.Source: G. Assigning Visible Voxels to a… · p. 3

H. Viewpoint Augmentation

Viewpoint augmentation adds alternative candidates for voxels with insufficient candidate visibility by sampling oblique directions around each voxel’s outward normal.

H. Viewpoint Augmentation

  • For each voxel with SBW(v) < k, the method samples directions around its outward normal and places additional candidates at the initial GSD-derived distance.Candidates undergo the same ray pre-filter before joining the pool and updating visibility and SBW counts.Source: H. Viewpoint Augmentation · p. 3

IV. SELECTING A SUBSET OF VIEWPOINTS

The selection stage formulates viewpoint choice as set multi-cover: select a compact subset that meets each voxel’s feasible coverage target. A dynamically weighted greedy heuristic prioritizes unmet demand and scarce remaining visibility.

IV. SELECTING A SUBSET OF VIEWPOINTS

  • Set multi-cover selects a minimum-cardinality viewpoint subset so each voxel is observed at least k times, when feasible.Each candidate corresponds to the subset of surface voxels it can see.Source: §IV · p. 4
  • The Globally Informed Greedy k-Coverage heuristic dynamically prioritizes voxels with unmet coverage demand and limited remaining visibility.The visibility matrix encodes whether each candidate viewpoint observes each surface voxel.Source: §IV · p. 4
  • Dynamic weights combine urgency from remaining coverage deficits with rarity from the number of remaining viewpoint alternatives.As viewpoints are selected, remaining visibility counts are updated; voxels with fewer alternatives retain higher weights, while those with many alternatives are down-weighted.Source: §IV · p. 4
  • Per-voxel targets are capped at k*(v) = min(k, SBW(v)); augmentation aims to make every target equal k, and a cleanup pass removes redundant selected viewpoints.If candidate visibility is insufficient, the capped targets reflect that limitation; full k-coverage is achievable under the modeled visibility relation when every voxel has sufficient candidate visibility.Source: §IV · p. 4

V. BASELINE ALGORITHMS FOR COMPARISON

The comparison uses sequential overlap-based pruning and an ILP over the same generated candidate set. The ILP explicitly enforces per-voxel coverage and minimizes viewpoint count when optimality is certified.

V. BASELINE ALGORITHMS FOR COMPARISON

  • Overlap pruning accepts a candidate only when its overlap with already covered voxels is below threshold τ, with vertical or visibility-based ordering.Vertical ordering runs bottom to top; visibility-based ordering processes candidates by descending number of visible voxels.Source: §V · pp. 4–5
  • Overlap pruning is order-dependent and can leave voxels uncovered even when feasible solutions exist because it lacks explicit coverage guarantees.Its local decisions use overlap with previously selected views rather than global unmet coverage requirements.Source: §V · p. 5
  • The ILP minimizes selected viewpoints subject to explicit per-voxel k-coverage constraints, establishing a minimum-cardinality solution when optimality is certified.It is used as a global reference for the discrete multi-cover problem over the generated candidate set.Source: §V · pp. 4–5
  • Set multi-cover has exponential worst-case complexity, and finer voxelizations or richer augmentation can make instances grow quickly and prevent timely ILP optimality certification.Without certification, the solver returns its best feasible solution within the imposed time limit.Source: §V · p. 5

VI. EXPERIMENTS

Experiments use two publicly accessible 3D models with distinct geometry and evaluate the pipeline across fine-to-coarse voxel abstractions. The overlap-based pruning baseline is restricted to 0.10 m, while the globally informed greedy and ILP methods span all voxel sizes and coverage requirements.

VI. EXPERIMENTS

  • Two publicly accessible 3D models with distinct geometric characteristics provide the evaluation structures.Their voxelized representations are shown in Fig. 2.Source: §VI · p. 5, Figure 2 · p. 5
  • Experimental parameters span fine-to-coarse voxel sizes, overlap thresholds, and tilt and azimuth ranges for visibility augmentation.Table I summarizes the parameter settings; augmentation adds candidates for challenging regions where normal-aligned viewpoints may not provide enough visibility.Source: §VI · p. 5, Table I · p. 5
  • Sequential Overlap-Based Viewpoint Pruning is tested only at 0.10 m to illustrate behavior across overlap percentages and ordering strategies.Source: §VI · p. 5
  • Globally Informed Greedy k-Coverage and ILP-based selection are evaluated across all voxel sizes and k values.This contrasts with the overlap-based pruning evaluation, which is limited to 0.10 m.Source: §VI · pp. 5–6

VII. RESULTS

Across the evaluated configurations, the greedy method achieves full or near-full requested coverage with compact viewpoint sets, while candidate augmentation improves visibility and retained pairs meet the modeled GSD bound.

VII. RESULTS

  • Targeted augmentation substantially reduces voxels with no or insufficient visible candidates across the evaluated structures, voxel sizes, and coverage levels.The Rooster produces more initial viewpoints than surface voxels because some voxels retain multiple outward-facing normals.Source: §VII · p. 6, Table III · p. 6, Figure 3 · p. 6
  • All reported maximum GSD values are at or below the prescribed 0.5 mm/px bound for retained viewpoint–voxel pairs.These statistics use modeled voxel-center observations and do not establish image quality over entire voxel surfaces or downstream reconstruction accuracy.Source: §VII · p. 6, Table IV · p. 6
  • Increasing the overlap threshold generally selects more viewpoints and reduces uncovered regions, but full coverage remains below 100% in every tested configuration.Vertical and visibility-based sorting also produce substantially different viewpoint counts and coverage distributions at the same threshold.Source: §VII · p. 6, Table V · p. 7
  • Greedy cleanup removes a small number of viewpoints without changing satisfaction of the capped per-voxel targets.No reported ILP viewpoints are removed; this is consistent with minimality only where ILP optimality is certified.Source: §VII · p. 7
  • 3.00–16.39% more viewpoints than the corresponding ILP solutions are used by the greedy method across evaluated configurations.Both methods report full requested k-coverage when every target voxel has at least k admissible candidates; the few lower-coverage cases coincide with residual candidate-visibility deficiencies.Source: §VII · p. 7

VIII. CONCLUSION

The work formulates aerial inspection viewpoint selection as GSD-constrained k-coverage over voxelized surfaces, using a dynamically weighted greedy heuristic to select compact viewpoint sets. It reports full or near-full coverage near the ILP counts, while limiting its claims to modeled sensing and two structures.

VIII. CONCLUSION

  • The framework formulates viewpoint selection as GSD-constrained k-coverage over voxelized surfaces, with candidate viewpoints filtered under a geometric sensing model and augmented for undercovered voxels.Set multi-cover then evaluates per-voxel coverage requirements over the resulting discrete candidate pool.Source: §VIII · p. 7
  • Across evaluated structures, voxel sizes, and coverage levels, the heuristic achieves full or near-full requested k-coverage using 3.00–16.39% more viewpoints than corresponding ILP solutions.The ILP is a discrete minimum-cardinality reference only where optimality is certified; no global camera-pose optimality or theoretical approximation guarantee is claimed.Source: §VIII · p. 7
  • The heuristic prioritizes remaining coverage deficits and scarce viewing alternatives through an interpretable, dynamically weighted selection rule.Source: §VIII · p. 7
  • The study assumes known, static geometry, models sensing at voxel centers, and evaluates only two structures; it does not assess flight feasibility or downstream reconstruction quality.Unassessed factors include UAV reachability and dynamics, collision-safe trajectories, minimum viewpoint separation, and pipeline runtime.Source: §VIII · p. 7
Loading 2610.36450v1…