Prof. Dr. Benedek Nagy

Research on Digital geometry and its applications

Keywords: Discrete Geometry, Computer Graphics, Digital Image Processing, Combinatorics : digital (path-based) distance functions on various grids, neighborhood sequences, digital circles, digital discs, discrete tomography,  distance transform, weighted distances, triangular grid, face-centered cubic grid, body-centered cubic grid, diamond grid, nD grids

The geometry of digital world (e.g., digital pictures, screens) differs from the Euclidean geometry: there are neighbor points (there are points without points between them), the number of points with a given Euclidean distance r is finite and usually not connected, there could be lines “crossing each other" without common point (such as the two diagonals of a chess board)… Therefore the digital geometry is needed. Based on the various neighborhood structures of various grids digital, i.e., path-based distance functions are defined and they can be used in various (digital) fields…
There is also a strong argument to use various (non-standard) grids in applications: With higher precision in image acquisition equipment, the amount of data that is used when processing these images is increasing. By using optimal sampling grids, in 3D, almost 30% fewer samples are needed to get the same representation/reconstruction quality; and as the images are computed, rather than captured directly, there is no special reason to use the standard cubic grid.

Group members, research partners:

Szabolcs Baják (University of Debrecen)
Krisztina Barczi (University of Debrecen)
Gunilla Borgefors (Swedish University of Agricultural Sciences, Sweden)
Lidija Comic (University of Novi Sad, Serbia)
János Farkas (ATOMKI, Debrecen, Hungary)
Tibor Lukic (University of Novi Sad, Serbia)
Gergely Kovács (Edutus College, Hungary) Elisa Moisi (University of Oradea, Romania)
Robin Strand (Uppsala University, Sweden)
Béla Vizvári (Eastern Mediterranean University, Cyprus)

Coordinate systems, Descriptions and connections of various grids. Tolological (cobinatorial) coordinate systems.

Based on an effective coordinate system for the triangular grid, e.g., [ic10], it can be handled as easily, as the square grid by the Cartesian frame, isometric transformations of the grid is also presented [ic17,ic38]. In [ij67] a topological coordinate system is presented for the triangular grid addressing not only the grid-triangles (pixels), but the edges and nodes between them. In [ic6,ij8] various (nD) grids are decribed by n+1 coordinate value. A nice further extension of this work can be found in [ij38,ij39]. A summary on coordinate systems for some non-traditional grids [ic75].
Topological (or combinatorial) coordinate systems for 3D grids are able to address not only the voxels, but also lower dimensional parts of the grids. Various coordinate systems are introduced for varoius non-traditional 3D grids in [ic71,ij83,ij93,ij95,ij96].

Research papers:

Distances based on neighborhood sequences on 2D grids.

In computers the discrete plane/space is used since this world is digital. The discrete space is usually defined by a grid. There are three regular grids in two dimensions: the square grid, the hexagonal grid and the triangular grid. The square grid is the most used due to the simplicity of the Cartesian coordinate frame. There are two types of neighbors defined naturally: the city-block and the chessboard neighborhoods. The hexagonal grid (hexagonal tiling) is the simplest one, since there is only one natural neighborhood among the hexagons of the grid. The triangular grid is a little bit sophisticated (there are three types of natural neighborhoods), however it has some nice and interesting properties. In the digital space the usage of the usual (Euclidean) distance may lead to some strange phenomena. Instead, path-based, so-called digital distances can be used based on the neighborhood structure of the grid. Digital distances are frequently used in computerized applications of geometry, e.g., in image processing, in computer graphics. There are two main approaches to define digital distances: distances based on neighborhood sequences in which the used types of neighbors is varied along a path; and weighted (chamfer) distances, where various types of steps have various weights (lengths). One may also mix these two features obtaining weighted neighbourhood sequence distance [ic50]. Based on an effective coordinate system for the triangular grid, it can be handled as easily, as the square grid by the Cartesian frame. Definitions of digital distances (neighborhood sequences), paths and distances, some important results about them is given: a greedy algorithms that provides a shortest path [ic3,ij2], formula to compute the distance from a point to another point defined by a given neighborhood sequence [ij10,ij28]. Interesting properties of these distances, such as non-metrical distances are shown (triangular inequality and symmetry may be violated) [ij1,ic11,ij12,ij30]. A necessary and sufficient condition to define metrical distances is proved [ij1,ij3]. Some details on digital circles [hc1,ij9,ij24] based on these distances are also presented such as approximations of the Euclidean distance [ij26,ic31,ij50]. Applications, e.g., distance maps [ij25], discrete tomography [ic49] can also be found.

Research papers:

Distances based on (weighted) neighbourhood sequences on 3D grids.

Digital geometry can be based on various grids in 3D. Various digital distance functions are defined and analysed on the cubic [ij3,ij28], face-centered cubic, body-centered cubic [ij18,ij29,ij36,ij37], honeycomb [ic42], and diamond grids [bc2,ij40,ij44] based on their neighborhood structures, i.e., (weighted) neighborhood sequences. The parameters that minimize an error function that favors distance functions with low rotational dependency is also given in [ij51]. We also give algorithms for computing the distance transform—the tool by which these distance functions can be applied in image processing applications. Indexing and segmentation of images using digital distances can be found in [ic7,ij11]. A relation of the cubic and triangular grids is shown in [ic6,ij8].

Research papers:

Digital distances on higher dimension, nD grids framework, connections of various grids, distances of sets (languages).

A nice description of various nD grids and connection among them can be found in [ij8,ij38,ij39].
Distances based on neighborhood sequences on nD (hyper)cubic grid are analysed in [ic2,ic16,ij3,ij35]: greedy algorithm for shortest path, if and only if condition for metricity, formula for computing distance.
Digital distances, i.e., (weighted) neighborhood sequences are analysed in nD face-centered and body-centered cubic grids in [ij41,ij45].   
Various distance measures of sets (languages) are introduced in [ij27].

Research papers:

Digital polygons, digital circles, dicsc.

The digital representation of a disc depends on the respective position of the object and the grid. An algorithm is presented which results all possible digital images of Euclidean discs [ij14].
Digital objects, such as digital circles can be defined by digital distances [ic23,ij9].
Euclidean circles/discs are approximated by digital circles/discs based on digital distances on the square [ij26], the hexagonal and the triangular grids [hc1,ij3].
Another way is to define digital objects by having a characterisitic property of the Euclidean objects. Since Euclidean circles have the smallest perimeter of all objects having a given area and they have the maximal area among the objects having the same perimeter. In the triangular grid, defining the perimeter of an object by the number of (1- and 3-) neighbour grid-triangles on the boundary, it is proved that in both cases special hexagons are Pareto optimal, i.e., they fulfill both versions of the isoperimetric inequality: they have maximal area among objects that have at most the same perimeter; and they have minimal perimeter among objects that have at least the same area in [ij53,ij68].

Research papers:

Discrete tomography, digitization.

The task of discrete tomography to find the (digitized) object from its projected values. A genetic approach is presented in the triangular grid using three directions of projections in [ic49]. Another evolutionary algorithm [ic55] and simulated annealing with three and six projections [ij66] can also effectively be used [hc14].
A kind of inverse problem is to find all discrete versions of an Euclidean object: An Euclidean object can be digitized in various ways. The digital representation of a disc depends on the respective position of the object and the grid. An algorithm is presented which results all possible digital images of Euclidean discs [ij14].

  • (hc14) with T. Lukic and E. Moisi, Diszkrét tomográfia a háromszögrácson természet-motiválta algoritmusokkal (Soft computing methods for discrete tomography on the triangular grid), KÉPAF 2013, Bakonybél, 450-463.
  • (ij66) Energy-Minimization Based Discrete Tomography Reconstruction Method for Images on Triangular Grid, IWCIA 2012, Lecture Notes in Computer Science - LNCS 7655, (2012), 274-284. (co-author: T. Lukic)
  • (ic55) Reconstruction of Binary Images Represented on Equilateral Triangular Grid Using Evolutionary Algorithms, Advances in Intelligent Systems and Computing - AISC 195 (Springer): Soft Computing Applications (2012), 561-571. (co-authors: E. V. Moisi, V. I. Cretu)
  • (ic49) with E. Moisi: Discrete Tomography on the Triangular Grid: a Memetic Approach, 7th International Symposium on Image and Signal Processing and Analysis (ISPA 2011), Dubrovnik, Croatia, 579-584.
  • (ij14) An algorithm to find the number of the digitizations of discs with a fixed radius, Electronic Notes in Discrete Mathematics 20 (2005), 607-622.

Patterns.

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star was open. There are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages [ij15]. It was shown that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties.
Primitive words are analysed from the point of view of their scattered subwords [ij15]. The language of primitive words is the language of the words that are not proper powers of another word. We take a look at the Parikh-vectors of these words, that is, we consider the commutative closure of languages formed by primitive words. After first looking at the shortest (one letter) subwords we move on towards giving necessary conditions for a word to be non-primitive in terms of scattered subword multiplicity. Furthermore, we prove that knowing the multiplicity of every word in a fixed set of words as scattered subwords in some word is not enough to decide whether it is primitive or not.

Research papers:

  • (ij15) On the language equivalence of NE star-patterns, Information Processing Letters 95 (2005), 396-400.
  • (ij34) Scattered subword complexity of non-primitive words, Journal of Automata, Languages and Combinatorics - JALC 13 (2008) 3/4, 233-247. (co-author: Sz. Fazekas)

(Hyper)Graph Generation.

Contextual hypergraph grammars are introduced as generalization of total contextual string grammars. We study the position of the class of languages generated by contextual hypergraph grammars in comparison with graph languages generated by hyperedge replacement grammars and double-pushout hypergraph grammars. Moreover, several examples show the potential of the new class of grammars. Various trees are computed and self-assembly is modelled in this framework.

Research papers:

  • (ij19) Contextual Hypergraph Grammars - A New Approach to the Generation of Hypergraph Languages, DLT 2006, Tenth International Conference DEVELOPMENTS IN LANGUAGE THEORY, Santa Barbara, CA, USA, 327-338. (Lecture Notes in Computer Science, LNCS 4036, co-authors: A.-H. Dediu, R. Klempien-Hinrichs and H.-J. Kreowski)
  • (ic29) with Adrian-Horia Dediu, Self-assembling tilings of Boolean tree-like circuits modelled by contextual hypergraph grammars (2007), NSIP2007, IEEE International Workshop on Nonlinear Signal and Image Processing, Bucharest, Romania, 150-153.
  • (ic27) with Adrian-Horia Dediu, Computing Trees with Contextual Hypergraph Grammars (2007), ForLing2007-FCT2007, International Workshop on NON-CLASSICAL FORMAL LANGUAGES IN LINGUISTICS, Budapest, Hungary, 39-53.

A very brief summary of the above results were presented in

  • (hc13) Digitális geometria Debrecenben: távolságfüggvények és képfeldolgozás különbözõ rácsokon (Digital Geometry in Debrecen: Distance Functions and Image Processing on Various Grids), IF 2011, Informatika a Felsõoktatásban 2011, (Informatics in Higher Education), Debrecen, 428-434.

Selected research grants:

  • Domus Hungarica Grant (2012) for Tibor Lukic to do common research in Debrecen (supervisor: Benedek Nagy)
  • DIGAVIP 2007-08
  • OTKA 2003-2006

Contact:

  • Benedek Nagy
  • E-mail: nbenedek (dot) inf (at) gmail

If you have any problem with downloading any of these papers please email me for a copy.

Prof. Dr. Benedek Nagy