A parallel information-based complexity approach to visual surface reconstruction

Abstract

In this paper, we give a novel insight into studying the low level vision. We attack low level problems by parallel information-based complexity techniques. Here we only study the visual surface reconstruction. We obtain tight bounds on the complexity, considered as a function of two variables simultaneously: the number of processors, the required precision. This result seems to be new even in serial case. Our results will provide a benchmark for the intrinsic difficulty of visual surface reconstruction. With this, one can compare its computational complexity with the cost any algorithm that solves the problem to tell how well the given algorithm measures up. To the best of our knowledge, it is the first attempt to introduce parallel information-based complexity techniques into studying low level vision.

Keywords:

• Low level vision
• algebraic complexity
• parallel complexity
• information-based complexity
• visual surface reconstruction

C.R. Categories::

• F.1.3
• I.2.6