Reconstruction of Binary Matrices Satisfying Neighborhood Constraints by Simulated Annealing

Authors: Divyesh Patel, Tanuja Srivastava

Abstract:

This paper considers the NP-hard problem of reconstructing binary matrices satisfying exactly-1-4-adjacency constraint from its row and column projections. This problem is formulated into a maximization problem. The objective function gives a measure of adjacency constraint for the binary matrices. The maximization problem is solved by the simulated annealing algorithm and experimental results are presented.

Keywords: Discrete Tomography, exactly-1-4-adjacency, simulated annealing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1092451

References:

[1] G. T. Herman and A. Kuba, Discrete Tomography: Foundations, algorithms and applications, Boston, 1999.
[2] G. T. Herman and A. Kuba, Advances in Discrete Tomography and its applications, Boston, 2007.
[3] A. Kuba, "The reconstruction of two-directionally connected binary patterns from their orthogonal projections,” Computer Vision, Graphics, and Image Processing 27, pp. 249-265, 1984.
[4] P. Balazs, E. Balogh, and A. Kuba, "Reconstruction of 8-connected but not 4-connected hv-convex discrete sets,” Discrete Applied Mathematics 147, pp. 149-168, 2005.
[5] A. Frosini, C. Picouleau, and S. Rinaldi, "Reconstructing binary matrices with neighborhood constraints: An NP-hard problem,” DGCI 2008, Lecture Notes in Computer Science 4992, pp. 392-400.
[6] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing,” Science, vol. 220, no. 4598, pp. 671-680, 1983.
[7] El-Ghazali Talbi, Meta-heuristics: From Design to Implementation, Wiley, 2009, pp. 126-140.
[8] F. Jarray and G. Tlig, "A simulated annealing for reconstructing hv-convex binary matrices,” Electronic Notes in Discrete Mathematics 36, pp. 447-454, 2010.
[9] H. J. Ryser, "Combinatorial properties of matrices of zeros and ones,” Canad. J. Math. 9, pp. 371-377, 1957.