Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | Vol. 125, nr 3/4 | 343--359
Tytuł artykułu

The Reconstruction of Polyominoes from Horizontal and Vertical Projections and Morphological Skeleton is NP-complete

Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Reconstruction of binary images from their projections is one of the main tasks in many image processing areas, therefore determining the computational complexity of those problems is essential. The reconstruction complexity is highly dependent on the requirements of the image. In this paper, we will show that the reconstruction is NP-complete if the horizontal and vertical projections and the morphological skeleton of the image are given, and it is supposed that the image is 4-connected.
Wydawca

Rocznik
Strony
343--359
Opis fizyczny
Bibliogr. 11 poz., wykr.
Twórcy
autor
  • Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary, nhantos@inf.u-szeged.hu
autor
  • Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary, pbalazs@inf.u-szeged.hu
Bibliografia
  • [1] Barcucci, E., Del Lungo, A.D., Nivat, M., Pinzani, R.: Reconstructing convex polyominoes from horizontal and vertical projections, Theoretical Computer Science, 155, 1996, 321-347.
  • [2] Chrobak M., Durr, C., Reconstructing hv-convex poliominoes from orthogonal projections, Information Pro¬cessing Letters, 69, 1999, 283-289.
  • [3] Gardner, R.J., Gritzmann, P., Prangenberg, D.: On the computational complexity of reconstructing lattice sets from their X-rays, Discrete Mathematics, 202(1-3), 1999, 45-71.
  • [4] Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
  • [5] Gonzalez, R.C., Woods, R.E.: Digital Image Processing (3rd Edition), Prentice Hall, 2008.
  • [6] Hantos, N., Balazs, P., Palagyi, K.: Binary image reconstruction from two projections and skeletal informa¬tion, 15th International Workshop on Combinatorial Image Analysis (IWCIA 2012), LNCS 7655, Springer, Heidelberg, 2012, 263-274.
  • [7] Herman, G.T., Kuba, A. (eds.): Advances in Discrete Tomography and Its Applications, Birkhauser, Boston, 2007.
  • [8] Maragos, P., Schafer, R.W.: Morphological skeleton representation and coding of binary images, IEEE Trans¬actions on Acoustics, Speech and Signal Processing, Volume 34, Issue 5, 1986, 1228-1244.
  • [9] Ryser, H.: Combinatorial mathematics, Mathematical Association of America, New York, 1963.
  • [10] Shapiro, L., and Stockman, G.: Computer Vision, Prentice Hall, 2002.
  • [11] Woeginger, G.J.: The reconstruction of polyominoes from their orthogonal projections, Information Process¬ing Letters, 77(5-6), 2001, 225-229.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-d7690863-7a39-4b8e-9162-beea292ddce3
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.