Approximate Techniques in Solving Optimal Camera Placement Problems

While the theoretical foundation of the optimal camera placement problem has been studied for decades, its practical implementation has recently attracted significant research interest due to the increasing popularity of visual sensor networks. The most flexible formulation of finding the optimal camera placement is based on a binary integer programming (BIP) problem. Despite the flexibility, most of the resulting BIP problems are NP-hard and any such formulations of reasonable size are not amenable to exact solutions. There exists a myriad of approximate algorithms for BIP problems, but their applications, efficiency, and scalability in solving camera placement are poorly understood. Thus, we develop a comprehensive framework in comparing the merits of a wide variety of approximate algorithms in solving the optimal camera placement problems. We first present a general approach of adapting these problems into BIP formulations. Then, we demonstrate how they can be solved using different approximate algorithms including greedy heuristics, Markov-chain Monte Carlo, simulated annealing, and linear and semidefinite programming relaxations. The accuracy, efficiency, and scalability of each technique are analyzed and compared in depth. Extensive experimental results are provided to illustrate the strength and weakness of each method.

• Publication year

  2011

• Venue

  IEEE International Conference on Computer Vision

• Publication date

  2011-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1155/2013/241913
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Can You See Me Now? Sensor Positioning for Automated and Persistent Surveillance

  2010cited by this paper
• Occlusion-aware multiple camera reconfiguration

  2010cited by this paper
• A fuzzy model for coverage evaluation of cameras and multi-camera networks

  2010cited by this paper
• Optimal Visual Sensor Network Configuration

  2009influential reference
• SCIP: solving constraint integer programs

  2009cited by this paper
• Optimal visual sensor planning

  2009influential reference
• On the set multi-cover problem in geometric settings

  2009cited by this paper
• Human segmentation by fusing visible-light and thermal imaginary

  2009cited by this paper
• Optimal camera placement for total coverage

  2009influential reference
• Directional Sensor Placement with Optimal Sensing Range, Field of View and Orientation

  2008cited by this paper
• Optimal Camera Network Configurations for Visual Tagging

  2008cited by this paper
• Bi-layer video segmentation with foreground and background infrared illumination

  2008cited by this paper
• Multi-Camera Surveillance with Visual Tagging and Generic Camera Placement

  2007cited by this paper
• A General Method for Sensor Planning in Multi-Sensor Systems: Extension to Random Occlusion

  2007cited by this paper
• Optimal Camera Placement for Automated Surveillance Tasks

  2007cited by this paper
• Optimal placement of stereo sensors

  2007cited by this paper
• Understanding and using linear programming

  2007cited by this paper
• Optimal Placement and Selection of Camera Network Nodes for Target Localization

  2006cited by this paper
• Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements

  2006cited by this paper
• InteractiveVirtual Simulation for Multiple Camera Placement

  2006cited by this paper
• On the optimal placement of multiple visual sensors

  2006cited by this paper
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming

  2003cited by this paper
• Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks

  2002cited by this paper
• Monte Carlo Strategies in Scientific Computing

  2002cited by this paper
• An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs

  2001cited by this paper
• Viewpoint Selection using Viewpoint Entropy

  2001cited by this paper
• Approximation algorithms for partial covering problems

  2001cited by this paper
• Art Gallery and Illumination Problems

  2000cited by this paper
• SDPA (SemiDefinite Programming Algorithm)

  1999cited by this paper
• Improved Performance of the Greedy Algorithm for Partial Cover

  1997cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Recent Results in Art Galleries

  1992cited by this paper
• Recent results in art galleries (geometry)

  1992cited by this paper
• Cones of Matrices and Set-Functions and 0-1 Optimization

  1991cited by this paper
• A hierarchy of relaxation between the continuous and convex hull representations

  1990cited by this paper
• Art gallery theorems and algorithms

  1987cited by this paper
• Computational complexity of art gallery problems

  1986cited by this paper
• Optimization by simulated annealing: Quantitative studies

  1984cited by this paper
• Model Building in Mathematical Programming

  1979cited by this paper
• A Greedy Heuristic for the Set-Covering Problem

  1979cited by this paper
• A combinatorial theorem in plane geometry

  1975cited by this paper

• Roadside lidar-based scene understanding toward intelligent traffic perception: A comprehensive review

  2026cites this paper
• VF-Plan: Bridging the Art Gallery Problem and Static LiDAR Scanning with Visibility Field Optimization

  2025cites this paper
• Cost Optimization in Selection and Placement of Security Cameras

  2025cites this paper
• A Surrogate Metric-Based Framework for Placing Infrastructure Sensing Units to Enhance Cooperative Vehicle-Infrastructure Perception

  2025cites this paper
• Exact optimization of surveillance camera placement in dynamic construction sites

  2025cites this paper
• Vehicle-Road-Cloud Collaborative Perception Framework and Key Technologies: A Review

  2024cites this paper
• A Continuous Camera Placement Optimization Model for Surround View

  2024cites this paper
• A Review of Smart Camera Sensor Placement in Construction

  2024cites this paper
• DroNeRF: Real-Time Multi-Agent Drone Pose Optimization for Computing Neural Radiance Fields

  2023cites this paper
• Optimization of a Network of Cameras to Monitor an Area in a Smart City

  2023cites this paper
• Optimal Camera Configuration for Large-Scale Motion Capture Systems

  2023cites this paper
• Optimal Camera Placement to Generate 3D Reconstruction of a Mixed-Reality Human in Real Environments

  2023cites this paper
• OASIS: Optimal Arrangements for Sensing in SLAM

  2023cites this paper
• A Virtual Method for Optimizing Deployment of Roadside Monitoring Lidars at As-Built Intersections

  2023cites this paper
• Adversarial Path Planning for Optimal Camera Positioning

  2023cites this paper
• AutoSCOOP: Automated Road-Side Sensor Coverage Optimization for Robotic Vehicles on Proving Grounds

  2022cites this paper
• Using artificial intelligence search in solving the camera placement problem

  2022cites this paper
• Point cloud-based optimization of roadside LiDAR placement at constructed highways

  2022cites this paper
• QoE-aware Data Caching Optimization in Edge Computing Environment

  2022cites this paper
• A Multi-Resolution Approach For Large Real-World Camera Placement Optimization Problems

  2022cites this paper
• Multi Camera Placement via Z-buffer Rendering for the Optimization of the Coverage and the Visual Hull

  2021cites this paper
• Visual Sensor Pose Optimisation Using Visibility Models for Smart Cities

  2021influential citation
• Optimal Placement of Roadside Infrastructure Sensors towards Safer Autonomous Vehicle Deployments

  2021cites this paper
• Visual Sensor Pose Optimisation Using Rendering-based Visibility Models for Robust Cooperative Perception

  2021influential citation
• Efficient Global Optimization of Non-differentiable, Symmetric Objectives for Multi Camera Placement

  2021cites this paper
• DATA-DRIVEN APPROACH TO HOLISTIC SITUATIONAL AWARENESS IN CONSTRUCTION SITE SAFETY MANAGEMENT

  2020influential citation
• Visual Sensor Placement Based on Risk Maps

  2020influential citation
• Design and development of a ceiling-mounted workshop Measurement Positioning System for large-scale metrology

  2020cites this paper
• Solving Optimal Camera Placement Problems in IoT Using LH-RPSO

  2020cites this paper
• Optimal Camera Placement To Visualize Surrounding View From Heavy Machinery

  2020cites this paper
• Maximizing Camera Coverage in Multicamera Surveillance Networks

  2020cites this paper
• Robust Hybrid Approach of Vision-Based Tracking and Radio-Based Identification and Localization for 3D Tracking of Multiple Construction Workers

  2020cites this paper
• Directional sensor placement in vegetable greenhouse for maximizing target coverage without occlusion

  2020cites this paper
• Solving Surveillance Coverage Demand Based on Dynamic Programming

  2020influential citation
• Analysis of 3D Scene Visual Characteristics Based on Virtual Modeling for Surveillance Sensors Parameters

  2020cites this paper
• Directional sensor placement in vegetable greenhouse for maximizing target coverage without occlusion

  2020cites this paper
• Robust Optimal Sensor Planning for Occlusion Handling in Dynamic Robotic Environments

  2019cites this paper
• Sensor-Based Optimization of Terrestrial Laser Scanning Measurement Setup on GPU

  2019cites this paper
• On the optimal placement of cameras for surveillance and the underlying set cover problem

  2019cites this paper
• The Maximum Visibility Facility Selection Query in Spatial Databases

  2019cites this paper
• Systematic Camera Placement Framework for Operation-Level Visual Monitoring on Construction Jobsites

  2019cites this paper
• Analysis of Three-Dimensional Scene Visual Characteristics Based on Virtual Modeling and Parameters of Surveillance Sensors

  2019cites this paper
• Reconfiguration of PTZ Camera Network with Minimum Resolution

  2019cites this paper
• Placing Visual Sensors Using Heuristic Algorithms for Bridge Surveillance

  2018cites this paper
• Optimal robot base placements for coverage tasks

  2018cites this paper
• View and Path Planning for Scaling 3D Acquisition to Many Objects

  2018cites this paper
• Optimizing Camera Placement Based on Task Modeling

  2018cites this paper
• Optimizing Visual Sensor Coverage Overlaps for Multiview Surveillance Systems

  2018influential citation
• Optimal Camera Placement Using Sine-Cosine Algorithm

  2018cites this paper
• Optimal Camera Pose and Placement Configuration for Maximum Field-of-View Video Stitching

  2018cites this paper
• Deployment optimization for camera network coupling with geographic environment

  2018cites this paper
• Tropical Principal Component Analysis and Its Application to Phylogenetics

  2017cites this paper
• Evaluating Coverage Effectiveness of Multi-Camera Domes Placement for Volumetric Surveillance

  2017cites this paper
• Optimizing Visual Surveillance Sensor Coverage Using Dynamic Programming

  2017cites this paper
• Camera Placement in Smart Cities for Maximizing Weighted Coverage With Budget Limit

  2017cites this paper
• Modeling Multicamera Coverage for Placement Optimization

  2017cites this paper
• Dynamic Reconfiguration in Camera Networks: A Short Survey

  2016cites this paper
• Camera coverage prioritization to support security monitoring

  2016cites this paper
• Automated view and path planning for scalable multi-object 3D scanning

  2016cites this paper
• VOE: A new sparsity-based camera network placement framework

  2016cites this paper
• Two-Phase Algorithm for Optimal Camera Placement

  2016cites this paper
• Designing Camera Networks by Convex Quadratic Programming

  2015cites this paper
• Camera Placement Optimization in Object Localization Systems

  2015cites this paper
• Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance

  2015cites this paper
• Secondary coverage configuration to support surveillance monitoring

  2015cites this paper
• A Multiple Feature-Based Image-Switching Strategy in Visual Sensor Networks

  2015cites this paper
• Optimizing visual sensor parameters for total coverage maximization

  2014cites this paper
• Extracting patterns of behavior from a network of binary sensors

  2014cites this paper
• Hazardous based area mapping for surveillance monitoring

  2014cites this paper
• Target coverage in camera networks for manufacturing workplaces

  2014cites this paper
• Surveillance of a 2D Plane Area with 3D Deployed Cameras

  2014influential citation
• Modeling camera coverage using imagery techniques for surveillance applications

  2014cites this paper
• Optimizing Visual Sensor Parameters for Total

  2014cites this paper
• An Approach to Segmenting Initial Object Movement in Visual Sensor Networks

  2014cites this paper