**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**32949

##### 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.