In this paper we examine the problem of reconstructing a discrete two-dimensional set from its two orthogonal projection (H,V) when the set satisfies some convexity conditions. We show that the algorithm of the paper [Int. J. Imaging Systems and Technol. 9 (1998) 69] is a good heuristic algorithm but it does not solve the problem for all (H,V) instances. We propose a modification of this algorithm solving the problem for all (H,V) instances, by starting to build the "spine". The complexity of our reconstruction algorithm is O(mn·log(mn)·min{m2,n2}) in the worst case. However, according to our experimental results, in 99% of the studied cases the algorithm is able to reconstruct a solution without using the newly introduced operation. In such cases the upper bound of the complexity of the algorithm is O(mn·log(mn)). A systematic comparison of this algorithm was done and the results show that this algorithm has the better average complexity than other published algorithms. The way of comparison and the results are given in a separate paper [Linear Algebra Appl. (submitted)]. Finally we prove that the problem can be solved in polynomial time also in a class of discrete sets which is larger than the class of convex polyominoes, namely, in the class of 8-connected convex sets

Brunetti, S., DEL LUNGO, A., DEL RISTORO, F., Nivat, M., Kuba, A. (2001). Reconstruction of 4- and 8-connected convex discrete sets from row and column projections. LINEAR ALGEBRA AND ITS APPLICATIONS, 339, 37-57 [10.1016/S0024-3795(01)00435-9].

Reconstruction of 4- and 8-connected convex discrete sets from row and column projections

BRUNETTI, SARA;
2001-01-01

Abstract

In this paper we examine the problem of reconstructing a discrete two-dimensional set from its two orthogonal projection (H,V) when the set satisfies some convexity conditions. We show that the algorithm of the paper [Int. J. Imaging Systems and Technol. 9 (1998) 69] is a good heuristic algorithm but it does not solve the problem for all (H,V) instances. We propose a modification of this algorithm solving the problem for all (H,V) instances, by starting to build the "spine". The complexity of our reconstruction algorithm is O(mn·log(mn)·min{m2,n2}) in the worst case. However, according to our experimental results, in 99% of the studied cases the algorithm is able to reconstruct a solution without using the newly introduced operation. In such cases the upper bound of the complexity of the algorithm is O(mn·log(mn)). A systematic comparison of this algorithm was done and the results show that this algorithm has the better average complexity than other published algorithms. The way of comparison and the results are given in a separate paper [Linear Algebra Appl. (submitted)]. Finally we prove that the problem can be solved in polynomial time also in a class of discrete sets which is larger than the class of convex polyominoes, namely, in the class of 8-connected convex sets
2001
Brunetti, S., DEL LUNGO, A., DEL RISTORO, F., Nivat, M., Kuba, A. (2001). Reconstruction of 4- and 8-connected convex discrete sets from row and column projections. LINEAR ALGEBRA AND ITS APPLICATIONS, 339, 37-57 [10.1016/S0024-3795(01)00435-9].
File in questo prodotto:
File Dimensione Formato  
BDDKNLAA01.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 297.16 kB
Formato Adobe PDF
297.16 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/25999
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo