The Tractability of Segmentation and Scene Analysis |
| |
Authors: | Cooper Martin C |
| |
Affiliation: | (1) IRIT, University of Toulouse III, 31062 Toulouse |
| |
Abstract: | One of the fundamental problems in computer vision is the segmentation of an image into semantically meaningful regions, based only on image characteristics. A single segmentation can be determined using a linear number of evaluations of a uniformity predicate. However, minimising the number of regions is shown to be an NP-complete problem. We also show that the variational approach to segmentation, based on minimising a criterion combining the overall variance of regions and the number of regions, also gives rise to an NP-complete problem.When a library of object models is available, segmenting the image becomes a problem of scene analysis. A sufficient condition for the reconstruction of a 3D scene from a 2D image to be solvable in polynomial time is that the scene contains no cycles of mutually occluding objects and that no range information can be deduced from the image. It is known that relaxing the no cycles condition renders the problem NP-complete. We show that relaxing the no range information condition also produces an NP-complete problem. |
| |
Keywords: | segmentation scene analysis computational complexity NP-completeness |
本文献已被 SpringerLink 等数据库收录! |
|