Reconstructing convex polyominoes from their horizontal and vertical projections

E. Barcucci, A. Del Lungo, M. Nivat, R. Pinzani

IBP-Litp 1994/71: Rapport de Recherche Litp / Litp research reports
29 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Reconstructing convex polyominoes from their horizontal and vertical projections

Résumé : Le problème de reconstruire des ensembles de pixels à partir de leurs projections est un problème classique en tomographie, que l'on rencontre dans d'autres domaines comme la reconnaissance ou la compression des images. Dans cet article ou se donne les deux projections horizontales et verticales c'est à dire le nombre de pixels sur chaque parallèle à l'un des axes : le problème de la reconstruction est NP-complet pour les ensembles de pixels horizontalement ou verticalement convexes, et par contre nous décrivons un algorithme polynomial pour les ensembles convexes, c'est à dire horizontalement et verticalement convexes. La difficulté est qu'un couple de projections peut-être commun à un nombre exponentiel de polyominos (ensemble de pixels) convexes.

Abstract : Reconstructing discrete bidimensional sets from their projections is involved in many different problems of computer-aided tomography, pattern recognition, image processing and data compression. In this paper, we examine the problem of reconstructing a discrete bidimensional set S satisfying some convexity conditions from its two orthogonal projections (H , V ). We develop an algorithm that start out from ( H , V ) and reconstructs set S , when S is a convex polyomino, in polynomial time. At the same time, we show that determining the existence of a row-convex (column-convex) polyomino or set with connected rows (columns) having orthogonal projections ( H , V ) assigned is an NP-complete problem. Moreover, by using the algorithm to reconstruct convex polyominoes from their two orthogonal projections we prove that the numerical matching with target sums problem can be solved in polynomial time if its sequences are unimodal.

Publications internes Litp 1994 / Litp research reports 1994