From the VCR, we can associate with any set of features F a set of optimal viewpoints . One might want to inspect the features in F sequentially, for instance because no viewpoint grants simultaneous visibility of all the features in the set, or because it is desired to ensure maximum visibility or reliability while inspecting each feature. The problem is then to find the shortest path in space to visit all viewpoints in VF - the travelling salesperson problem (TSP) in 3D.
We implemented three existing TSP algorithms, simulated annealing, the elastic net method and the CCAO algorithm. We evaluated their performance over a large number of distributions of viewpoints, recording path lengths and distances from the overall optimal solution found (or from the real shortest path when this was known). With up to 100 sites, CCAO outperformed the other two, and was therefore incorporated in GASP. In brief, the CCAO algorithm (``convex hull, cheapest insertion, angle selection and Or-optimisation'') combines the features of tour construction and tour improvement TSP algorithms to build an initial path through a subset of VF, and extends the path incrementally until all viewpoints are visited. The path is then optimised by analysing possible swaps between arcs leading to lower-cost paths.
Figure 16, below, shows an example of a simple shortest inspection path (complex 3D paths are difficult to visualise) through the optimal stereo-inspection viewpoints of five faces of the stand, namely the four side planes of the base and the top plane of the ``seat''. Solid lines connect points on visible dome facets, dotted lines involve at least one occluded (not shown) viewpoint. The stereo head is represented by its baseline and the directions of the cameras' z axes. This solution was found in less than a second.
Figure 16: Example of inspection path for a stereo sensor
[ Viewer Centred Represenations: Contents | Conclusions ]
Comments to: Sarah Price at ICBL.