Coverage in visual sensor networks with Pan-Tilt-Zoom cameras: The MaxFoV problem

We consider the problem of target coverage in visual sensor networks with Pan-Tilt-Zoom (PTZ) cameras. The finely controllable movement in PTZ dimensions creates a large number of possible Field-of-View (FoV) settings, making it prohibitively expensive to consider them all in coverage algorithms. However, these FoVs are redundant as each group of targets is generally covered by many FoVs. Thus, an important problem is, how to identify FoVs that cover all maximal subsets of targets (MaxFoV) efficiently? We show that MaxFoV is an instance of generating all maximal cliques, which is NP-hard in general but polynomial if the number of cliques is polynomial. We construct an optimal algorithm to solve the problem with a worst case complexity of O(n³). Simulation and testbed experiments show that the algorithm drastically reduces the number of FoVs allowing multi-camera coverage to scale without sacrificing coverage quality.