Approximating binary images from discrete X-rays. (English) Zbl 0987.05037
Summary: We study the problem of approximating binary images that are accessible only through few evaluations of their discrete X-ray transform, i.e., through their projections counted with multiplicity along some lines. This inverse discrete problem belongs to a class of generalized set partitioning problems and allows natural packing and covering relaxations. For these (NP-hard) optimization problems we present various approximation algorithms and provide estimates for their worst-case performance. Further, we report on computational results for various variants of these algorithms. In particular, the corresponding integer programs are solved with only small absolute error for instances up to \(250,000\) binary variables.
MSC:
05B40 | Combinatorial aspects of packing and covering |
68U10 | Computing methodologies for image processing |
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
68R05 | Combinatorics in computer science |
82D25 | Statistical mechanics of crystals |
90C27 | Combinatorial optimization |
92C55 | Biomedical imaging and signal processing |