×

Binary matrices under the microscope: A tomographical problem. (English) Zbl 1113.68107

Summary: A binary matrix can be scanned by moving a fixed rectangular window (sub-matrix) across it, rather like examining it closely under a microscope. With each viewing, a convenient measurement is the number of 1s visible in the window, which might be thought of as the luminosity of the window. The rectangular scan of the binary matrix is then the collection of these luminosities presented in matrix form. We show that, at least in the technical case of a smooth \(m \times n\) binary matrix, it can be reconstructed from its rectangular scan in polynomial time in the parameters \(m\) and \(n\), where the degree of the polynomial depends on the size of the window of inspection. For an arbitrary binary matrix, we then extend this result by determining the entries in its rectangular scan that preclude the smoothness of the matrix.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68U10 Computing methodologies for image processing
15B36 Matrices of integers

References:

[1] Barcucci, E.; Del Lungo, A.; Nivat, M.; Pinzani, R., Reconstructing convex polyominoes from horizontal and vertical projections, Theoret. Comput. Sci., 155, 2, 321-347 (1996) · Zbl 0872.68134
[2] Chrobak, M.; Dürr, C., Reconstructing hv-convex polyominoes from orthogonal projections, Inform. Process. Lett., 69, 283-289 (1999) · Zbl 1002.68101
[3] Frosini, A.; Nivat, M.; Vuillon, L., An introductive analysis of Periodical Discrete Sets from a tomographical point of view, Theoret. Comput. Sci., 347, 1-2, 370-392 (2005) · Zbl 1080.68105
[4] (Herman, G. T.; Kuba, A., Discrete Tomography: Foundations Algorithms and Applications (1999), Birkhauser: Birkhauser Boston, MA) · Zbl 0946.00014
[5] Nivat, M., Sous-ensembles homogénes de \(Z^2\) et pavages du plan, C. R. Acad. Sci. Paris, Ser. I 335, 83-86 (2002) · Zbl 1115.52301
[6] Ryser, H., Combinatorial properties of matrices of zeros and ones, Canad. J. Math., 9, 371-377 (1957) · Zbl 0079.01102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.