A practical iterative algorithm for sensor positioning

Several problems in computer vision require locating multiple sensors. In some cases the problem, which is in general three-dimensional, can be reduced to 2D. This problem can be modeled as an art gallery problem, which is NP-hard and no finite algorithm, even exponential, is known for its solution....

Full description

Saved in:
Bibliographic Details
Main Authors: Bottino, A., Laurentini, A.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Computer vision
Heuristic algorithms
Image reconstruction
Inspection
Iterative algorithms
Rendering (computer graphics)
Sensor phenomena and characterization
Surveillance
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Several problems in computer vision require locating multiple sensors. In some cases the problem, which is in general three-dimensional, can be reduced to 2D. This problem can be modeled as an art gallery problem, which is NP-hard and no finite algorithm, even exponential, is known for its solution. Algorithms able to closely approximate the optimal solution and computationally feasible in the worst case are unlikely to exist. In this paper we propose a new sensor locating incremental algorithm. The technique converges toward the optimal solution. It locally refines a starting approximation provided by an integer covering algorithm, where each edge is observed entirely by at least one sensor. A lower bound for the number of sensors, specific of the polygon considered, is used for halting the algorithm, and a set of rules that allow to simplify the problem are presented
ISSN:1946-0740
1946-0759
DOI:10.1109/ETFA.2005.1612650