Camera Coverage Estimation Based on Multistage Grid Subdivision

Meizhen Wang, Xuejun Liu, Yanan Zhang, Ziran WangISPRS Int. J. Geo Inf 2017 · DOI

TL;DR

This paper introduces a novel multistage grid subdivision method for accurately and efficiently estimating camera coverage, especially in urban environments with occlusions. By adaptively refining grid resolution based on coverage status, it balances the trade-off between computational cost and precision, offering a more practical solution for camera network planning and analysis.

What Problem Does This Paper Address?

Accurately estimating the visual coverage of individual cameras and camera networks is crucial for numerous applications, including surveillance, optimal camera placement, and network planning. Existing methods often struggle to balance precision and efficiency, especially when dealing with complex environments that include occlusions from buildings and vegetation. Many approaches simplify camera models or scene geometry, leading to inaccurate coverage estimations. Furthermore, real-world scenarios often involve a large number of cameras and dynamic parameters, necessitating fast and reliable coverage estimation techniques. This paper aims to address this by proposing a method that can adapt its resolution to achieve both high accuracy where needed and efficiency overall.

Methods

The core of the proposed method is a multistage grid subdivision algorithm. Here's how it works:

  1. Initial Coverage Estimation: The theoretical Field of View (FOV) of a camera is first determined using its intrinsic and extrinsic parameters. This theoretical coverage is then bounded by a Minimum Bounding Rectangle (MBR).
  2. Initial Grid Subdivision: The MBR is initially divided into grids of a user-defined size ($w_0$).
  3. Line of Sight (LOS) Analysis: For each grid, the status of its four corners is determined using a Line of Sight (LOS) algorithm. This algorithm checks if a direct line of sight exists from the camera to the corner point, considering potential obstacles (like buildings or trees) represented by vector data. Each corner is assigned a binary status (1 for covered, 0 for not covered).
  4. Grid Status Encoding: The four corner statuses of a grid are combined into a four-digit code (e.g., 0000 for fully uncovered, 1111 for fully covered). Codes with mixed 0s and 1s indicate partial coverage.
  5. Adaptive Subdivision: Grids with non-homogeneous codes (i.e., not fully covered or fully uncovered) are recursively subdivided into four smaller sub-grids. This subdivision continues until a maximum predefined level ($max\_level$) is reached or all sub-grids have homogeneous codes. This adaptive approach allows for finer resolution only in areas where coverage is uncertain or partial.
  6. Coverage Geometry and Area: Finally, the total camera coverage is estimated by aggregating the geometry and area of all grids that are determined to be covered (or partially covered).

The method explicitly considers obstacles using vector data and assumes a relatively flat ground plane, making it suitable for urban environments.

Datasets

The paper evaluates the proposed method using:

  • Simulated Data: Three geometric shapes (circle, diamond, five-pointed star) were used to simulate different coverage scenarios with varying complexity.
  • Real Geographic Environment Data: A real-world scenario involving 15 cameras (8 PTZ and 7 still cameras) deployed in a geographic environment with buildings as major obstacles was used for validation.

No new benchmarks were introduced; rather, existing simulated and real-world data were used to validate the proposed method against different parameter settings.

Key Insights and Ideas

  • Adaptive Resolution is Key: The core insight is that not all areas require the same level of detail for coverage estimation. By subdividing only where necessary, the method achieves a better balance between accuracy and efficiency than fixed-grid approaches.
  • Trade-off Management: The method explicitly acknowledges and manages the trade-off between accuracy and efficiency, allowing users to tune parameters ($w_0$ and $max\_level$) to prioritize one over the other.
  • Obstacle Handling: Integrating vector-based obstacle data directly into the LOS calculation is crucial for realistic coverage estimation in urban settings.
  • Grid Status Encoding: The four-corner status encoding provides a compact way to represent grid coverage and drives the adaptive subdivision process.

Key Results

  • Accuracy vs. Efficiency: The experiments demonstrated that increasing the max_level (deeper subdivision) leads to higher accuracy but also significantly increases the computational cost (point number). Conversely, increasing the initial_grid_size ($w_0$) decreases accuracy but improves efficiency.
  • Parameter Sensitivity: The choice of initial_grid_size and max_level critically influences both accuracy and efficiency. For high efficacy with acceptable accuracy, a larger initial grid size and smaller max level are recommended. For high accuracy, a smaller initial grid size and larger max level are preferred.
  • Real-world Performance: In the real geographic environment experiment, the method provided coverage estimations that were visually consistent with the camera placements and obstacles. PTZ cameras, due to their dynamic nature, required more computation.
  • Coverage Rate Vibrations: The paper notes that coverage rate can vibrate, especially when grids crossing boundaries are subdivided, which is an artifact of the grid-based approximation.

Limitations and Future Work

  • Flat Ground Assumption: The current method assumes a flat ground plane. For rolling terrain, it may lead to inaccuracies due to unconsidered terrain occlusions.
  • Boundary Approximation: The coverage boundary can appear serrated due to the grid-based approximation, especially when the physical coverage boundary is not aligned with grid lines.
  • Sampling Limitations: Like all sampling-based methods, there's an inherent trade-off. If the initial grid size is too large, it might miss small holes or islands, leading to over/underestimation.
  • Future Work: The authors suggest extending the method to handle 3D terrain by incorporating high-precision DEM/DSM data and considering different Levels of Detail (LODs) for 3D buildings.

Summary updated

BibTeX
@article{wang2017camera,
  author = {Meizhen Wang and Xuejun Liu and Yanan Zhang and Ziran Wang},
  title = {{Camera Coverage Estimation Based on Multistage Grid Subdivision}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2017},
  doi = {10.3390/ijgi6040110},
}
Figure