The Reconstruction of Polyominoes from Horizontal and Vertical Projections and Morphological Skeleton is NP-complete

Issue title: Strategies for Tomography

Article type: Research Article

Authors: Hantos, Norbert | Balázs, Péter

Affiliations: Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary. nhantos@inf.u-szeged.hu; pbalazs@inf.u-szeged.hu

Note: [] Address for correspondence: Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary

Abstract: Reconstruction of binary images from their projections is one of the main tasks in many image processing areas, therefore determining the computational complexity of those problems is essential. The reconstruction complexity is highly dependent on the requirements of the image. In this paper, we will show that the reconstruction is NP-complete if the horizontal and vertical projections and the morphological skeleton of the image are given, and it is supposed that the image is 4-connected.

Keywords: reconstruction from projections, binary tomography, NP-completeness, polyomino, morphological skeleton

DOI: 10.3233/FI-2013-868

Journal: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 343-359, 2013