Footprint Placement for Mosaic Imaging by Sampling and Optimization


  • Scott Mitchell Sandia National Laboratories
  • Christopher Valicka Sandia National Laboratories
  • Stephen Rowe Sandia National Laboratories
  • Simon Zou Sandia National Laboratories



computational geometry, mixed-integer, imaging


We consider the problem of selecting a small set (mosaic) of sensor images (footprints) whose union covers a twodimensional Region Of Interest (ROI) on Earth. We take the approach of modeling the mosaic problem as a Mixed-Integer Linear Program (MILP). This allows solutions to this subproblem to feed into a larger remote-sensor collection-scheduling MILP. This enables the scheduler to dynamically consider alternative mosaics, without having to perform any new geometric computations. Our approach to set up the optimization problem uses maximal disk sampling and point-in-polygon geometric calculations. Footprints may be of any shape, even non-convex, and we show examples using a variety of shapes that may occur in practice. The general integer optimization problem can become computationally expensive for large problems. In practice, the number of placed footprints is within an order of magnitude of ten, making the time to solve to optimality on the order of minutes. This is fast enough to make the approach relevant for near real-time mission applications.We provide open source software for all our methods, “GeoPlace.”




How to Cite

Mitchell, S., Valicka, C., Rowe, S., & Zou, S. (2018). Footprint Placement for Mosaic Imaging by Sampling and Optimization. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 339-346.