Studying topological characteristics of digital images is a fundamental issue in image analysis and understanding. In the present paper we first propose a linear time constantworking space algorithm for determining the genus of a connected digital image. The computation is based on a combinatorial relation for digital images that may be of independent interest as well. We also propose definitions of dimension for planar digital images. These definitions serve as an alternative to the one proposed by Mylopoulos and Pavlidis1, and make up some of its shortcomings. We study various properties of the so-defined image dimension, in particular, characterization of dimension in terms of Euler characteristic. We also show that image dimension can be found within linear time and constant memory.

Genus and dimension of digital images and their time and space-efficient computation

NORDO, Giorgio;MAIMONE, ANGELO
2008

Abstract

Studying topological characteristics of digital images is a fundamental issue in image analysis and understanding. In the present paper we first propose a linear time constantworking space algorithm for determining the genus of a connected digital image. The computation is based on a combinatorial relation for digital images that may be of independent interest as well. We also propose definitions of dimension for planar digital images. These definitions serve as an alternative to the one proposed by Mylopoulos and Pavlidis1, and make up some of its shortcomings. We study various properties of the so-defined image dimension, in particular, characterization of dimension in terms of Euler characteristic. We also show that image dimension can be found within linear time and constant memory.
File in questo prodotto:
File Dimensione Formato  
GENUS AND DIMENSION OF DIGITAL IMAGES.pdf

solo gestori archivio

Tipologia: Versione Editoriale (PDF)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 239.09 kB
Formato Adobe PDF
239.09 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/11570/1901075
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact