The Euclidean plane can be partitioned into three kinds of

regular polygons, which results in triangular, square and hexagonal grids.

While the topology of the square grid is well-established, less emphasis

is put on the remaining two regular sampling schemes. In this paper we

summarize the results of our research that aimed to give some general

characterizations of simple pixels and sufficient conditions for topology-

preserving operators in the mentioned grids.

Thinning is a frequently applied technique for extracting centerlines from 2D binary objects. Parallel thinning algorithms can remove a set of object points simultaneously, while sequential algorithms traverse the boundary of objects, and consider the actually visited single point for possible removal. Two thinning algorithms are called equivalent if they produce the same result for each input picture. This paper presents the very first pair of equivalent 2D sequential and parallel subiteration-based thinning algorithms. These algorithms can be implemented directly on a conventional sequential computer or on a parallel computing device. Both of them preserve topology for (8, 4) pictures sampled on the square grid.

%B Image and Signal Processing and Analysis (ISPA), 2015 9th International Symposium on %I IEEE %C Zagreb, Croatia %P 304-309 %8 2015 Sep %@ 978-1-4673-8032-4 %G english %9 Conference paper %R 10.1109/ISPA.2015.7306077 %0 Conference Paper %B Képfeldolgozók és Alakfelismerők Társaságának 10. országos konferenciája %D 2015 %T Vékonyítás a végpont-megőrzés felülvizsgálatáva %A Gábor Németh %A Péter Kardos %A Kálmán Palágyi %XA vékonyítás mint iteratív objektum redukció gyakran alkalmazott

vázkijelölo módszer. A legtöbb létezo vékonyító algoritmus végpontok - vagyis releváns geometriai információt hordozó objektumpontok - megorzésével biztosítja azt, hogy ne törlodjenek az objektumok alakját reprezentáló fontos részletek. Ennek a megközelítésnek hátránya, hogy számos nemkívánatos vázágat eredményezhet. Ebben a cikkben egy olyan módszert mutatunk be, amellyel jelentosen csökkentheto a hamis vázágak száma. Ráadásul az itt bemutatott megközelítés tetszoleges végpont-megorzo 2D vékonyító algoritmusban alkalmazható.

An important requirement for various applications of binary image processing is to preserve topology. This issue has been earlier studied for two special types of image operators, namely, reductions and additions, and there have been some sufficient conditions proposed for them. In this paper, as an extension of those earlier results, we give novel sufficient criteria for general operators working on 2D pictures.

%B Combinatorial Image Analysis %S Lecture Notes in Computer Science %I Springer %C May 2014, Brno, Czech Republic %V 8466 %P 101 - 112 %8 2014 %@ 978-3-319-07147-3 %G eng %U http://dx.doi.org/10.1007/978-3-319-07148-0_10 %9 Conference paper %! Conference Paper %R 10.1007/978-3-319-07148-0_10 %0 Book Section %B International Conference on Cognitive Infocommunications (CogInfoCom) %D 2013 %T Parallel Thinning on the Triangular Grid %A Péter Kardos %A Kálmán Palágyi %E Péter Baranyi %X

One of the fundamental issues of human and computational cognitive psychology is pattern or shape recognition. Various applications in image processing and computer vision rely on skeleton-like shape features A possible technique for extracting these feautures is thinning. Although the majority of 2D thinning algorithms work on digital pictures sampled onthe conventional square grid, the role of some non-conventional grids, like the hexagonal and triangular grid, are of increasing importance as well. In this paper we propose numerous topolgy preserving parallel thinning algorithms that work on the triangular grid.

%B International Conference on Cognitive Infocommunications (CogInfoCom) %I IEEE %C Budapest %P 277 - 282 %8 Dec 2013 %@ 978-1-4799-1543-9 %G eng %9 Conference paper %M 14046653 %R 10.1109/CogInfoCom.2013.6719256 %0 Book Section %B Proceedings of the IASTED International Conference on Computer Graphics and Imaging (CGIM) %D 2013 %T Sufficient Conditions for Topology Preserving Additions and General Operators %A Péter Kardos %A Kálmán Palágyi %E L Linsen %XTopology preservation is a crucial issue of digital topology. Various applications of binary image processing rest on topology preserving operators. Earlier studies in this topic mainly concerned with reductions (i.e., operators that only delete some object points from binary images), as they form the basis for thinning algorithms. However, additions (i.e., operators that never change object points) also play important role for the purpose of generating discrete Voronoi diagrams or skeletons by influence zones (SKIZ). Furthermore, the use of general operators that may both add and delete some points to and from objects in pictures are suitable for contour smoothing. Therefore, in this paper we present some new sufficient conditions for topology preserving reductions, additions, and general operators. Two additions for 2D and 3D contour smoothing are also reported.

%B Proceedings of the IASTED International Conference on Computer Graphics and Imaging (CGIM) %I IASTED - Acta Press %C Calgary %P 107 - 114 %8 Feb 2013 %G eng %9 Conference paper %R 10.2316/P.2013.797-040 %0 Book Section %B Proceedings of International Symposium on Image and Signal Processing and Analysis (ISPA) %D 2013 %T On Topology Preservation in Triangular, Square, and Hexagonal Grids %A Péter Kardos %A Kálmán Palágyi %E Giovanni Ramponi %E Sven Lončarić %E Alberto Carini %E Karen Egiazarian %X

There are three possible partitionings of the continuous plane into regular polygons that leads to triangular, square, and hexagonal grids. The topology of the square grid is fairly well-understood, but it cannot be said of the remaining two regular sampling schemes. This paper presents a general characterization of simple pixels and some simplified sufficient conditions for topology-preserving operators in all the three types of regular grids.

%B Proceedings of International Symposium on Image and Signal Processing and Analysis (ISPA) %I IEEE %C Trieste %P 782 - 787 %8 Sep 2013 %G eng %9 Conference paper %M 14027933 %R 10.1109/ISPA.2013.6703844 %0 Conference Paper %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2013 %D 2013 %T Topology preserving parallel thinning on hexagonal grids %A Péter Kardos %A Kálmán Palágyi %E László Czúni %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2013 %I NJSZT-KÉPAF %C Veszprém %P 250 - 264 %8 Jan 2013 %G eng %9 Conference paper %0 Journal Article %J INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS %D 2013 %T Topology-preserving hexagonal thinning %A Péter Kardos %A Kálmán Palágyi %XThinning is a well-known technique for producing skeleton-like shape features from digital binary objects in a topology-preserving way. Most of the existing thinning algorithms work on input images that are sampled on orthogonal grids; however, it is also possible to perform thinning on hexagonal grids (or triangular lattices). In this paper, we point out to the main similarities and differences between the topological properties of these two types of sampling schemes. We give various characterizations of simple points and present some new sufficient conditions for topology-preserving reductions working on hexagonal grids.

%B INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS %I Taylor & Francis %V 90 %P 1607 - 1617 %8 2013 %@ 0020-7160 %G eng %U http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.724198#preview %N 8 %9 Journal article %! INT J COMPUT MATH %R 10.1080/00207160.2012.724198 %0 Book Section %B Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications III %D 2012 %T Hexagonal parallel thinning algorithms based on sufficient conditions for topology preservation %A Péter Kardos %A Kálmán Palágyi %E Paolo Di Giamberardino %E Daniela Iacoviello %E Renato M Natal Jorge %E Joao Manuel R S Taveres %XThinning is a well-known technique for producing skeleton-like shape features from digital

binary objects in a topology preserving way. Most of the existing thinning algorithms presuppose that the input

images are sampled on orthogonal grids.This paper presents new sufficient conditions for topology preserving

reductions working on hexagonal grids (or triangular lattices) and eight new 2D hexagonal parallel thinning

algorithms that are based on our conditions.The proposed algorithms are capable of producing both medial lines

and topological kernels as well.

Thinning as a layer-by-layer reduction is a frequently used technique for skeletonization. Sequential thinning algorithms usually suffer from the drawback of being order-dependent, i.e., their results depend on the visiting order of object points. Earlier order-independent sequential methods are based on the conventional thinning schemes that preserve endpoints to provide relevant geometric information of objects. These algorithms can generate centerlines in 2D and medial surfaces in 3D. This paper presents an alternative strategy for order-independent thinning which follows an approach, proposed by Bertrand and Couprie, which accumulates so-called isthmus points. The main advantage of this order-independent strategy over the earlier ones is that it makes also possible to produce centerlines of 3D objects.

%B IASTED International Conference on Signal Processing, Pattern Recognition and Applications (SSPRA) %I IASTED ACTA Press %C Crete, Greek %P 28 - 34 %8 June 2012 %G eng %U http://www.actapress.com/Content_of_Proceeding.aspx?proceedingID=736 %9 Conference paper %R 10.2316/P.2012.778-025 %0 Conference Paper %B IEEE International Conference on Cognitive Infocommunications (CogInfoCom) %D 2012 %T On Order–Independent Sequential Thinning %A Péter Kardos %A Kálmán Palágyi %E IEEE %XThe visual world composed by the human and computational cognitive systems strongly relies on shapes of objects. Skeleton is a widely applied shape feature that plays an important role in many fields of image processing, pattern recognition, and computer vision. Thinning is a frequently used, iterative object reduction strategy for skeletonization. Sequential thinning algorithms, which are based on contour tracking, delete just one border point at a time. Most of them have the disadvantage of order-dependence, i.e., for dissimilar visiting orders of object points, they may generate different skeletons. In this work, we give a survey of our results on order-independent thinning: we introduce some sequential algorithms that produce identical skeletons for any visiting orders, and we also present some sufficient conditions for the order-independence of templatebased sequential algorithms.

%B IEEE International Conference on Cognitive Infocommunications (CogInfoCom) %I IEEE %C Kosice, Slovakia %P 149 - 154 %8 2012 %@ 978-1-4673-5187-4 %G eng %U http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6413305 %9 Conference paper %R 10.1109/CogInfoCom.2012.6421971 %0 Book Section %B Combinatorial Image Analysis (IWCIA) %D 2012 %T On topology preservation for triangular thinning algorithms %A Péter Kardos %A Kálmán Palágyi %E Reneta P Barneva %E Valentin E Brimkov %E Jake K Aggarwal %XThinning is a frequently used strategy to produce skeleton-like shape features of binary objects. One of the main problems of parallel thinning is to ensure topology preservation. Solutions to this problem have been already given for the case of orthogonal and hexagonal grids. This work introduces some characterizations of simple pixels and some sufficient conditions for parallel thinning algorithms working on triangular grids (or hexagonal lattices) to preserve topology.

%B Combinatorial Image Analysis (IWCIA) %S Lecture Notes in Computer Science %I Springer Verlag %C Austin, TX, USA %P 128 - 142 %8 Nov 2012 %@ 978-3-642-34731-3 %G eng %9 Conference paper %! LNCS %R 10.1007/978-3-642-34732-0_10 %0 Book Section %B Digital Geometry Algorithms %D 2012 %T Topology Preserving Parallel 3D Thinning Algorithms %A Kálmán Palágyi %A Gábor Németh %A Péter Kardos %E Valentin E Brimkov %E Reneta P Barneva %XA widely used technique to obtain skeletons of binary objects is thinning, which is an iterative layer-by-layer erosion in a topology preserving way. Thinning in 3D is capable of extracting various skeleton-like shape descriptors (i.e., centerlines, medial surfaces, and topological kernels). This chapter describes a family of new parallel 3D thinning algorithms for (26, 6) binary pictures. The reported algorithms are derived from some sufficient conditions for topology preserving parallel reduction operations, hence their topological correctness is guaranteed. ` `

Thinning and shrinking algorithms, respectively, are capable of extracting medial lines and topological kernels from digital binary objects in a topology preserving way. These topological algorithms are composed of reduction operations: object points that satisfy some topological and geometrical constraints are removed until stability is reached. In this work we present some new sufficient conditions for topology preserving parallel reductions and fiftyfour new 2D parallel thinning and shrinking algorithms that are based on our conditions. The proposed thinning algorithms use five characterizations of endpoints.

%B ACTA CYBERNETICA-SZEGED %I University of Szeged, Institute of Informatics %C Szeged %V 20 %P 125 - 144 %8 2011 %@ 0324-721X %G eng %N 1 %9 Journal article %! ACTA CYBERN-SZEGED %0 Book Section %B Combinatorial Image Analysis (IWCIA) %D 2011 %T A family of topology-preserving 3d parallel 6-subiteration thinning algorithms %A Gábor Németh %A Péter Kardos %A Kálmán Palágyi %E Jake K Aggarwal %E Reneta P Barneva %E Valentin E Brimkov %E Kostadin N Koroutchev %E Elka R Korutcheva %XThinning is an iterative layer-by-layer erosion until only the skeleton-like shape features of the objects are left. This paper presents a family of new 3D parallel thinning algorithms that are based on our new sufficient conditions for 3D parallel reduction operators to preserve topology. The strategy which is used is called subiteration-based: each iteration step is composed of six parallel reduction operators according to the six main directions in 3D. The major contributions of this paper are: 1) Some new sufficient conditions for topology preserving parallel reductions are introduced. 2) A new 6-subiteration thinning scheme is proposed. Its topological correctness is guaranteed, since its deletion rules are derived from our sufficient conditions for topology preservation. 3) The proposed thinning scheme with different characterizations of endpoints yields various new algorithms for extracting centerlines and medial surfaces from 3D binary pictures. © 2011 Springer-Verlag Berlin Heidelberg.

%B Combinatorial Image Analysis (IWCIA) %S Lecture Notes in Computer Science %I Springer Verlag %C Madrid, Spain %P 17 - 30 %8 May 2011 %@ 978-3-642-21072-3 %G eng %9 Conference paper %! LNCS %R 10.1007/978-3-642-21073-0_5 %0 Conference Paper %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2011 %D 2011 %T Iterációnkénti simítással kombinált vékonyítás %A Péter Kardos %A Gábor Németh %A Kálmán Palágyi %E Zoltan Kato %E Kálmán Palágyi %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2011 %I NJSZT %C Szeged %P 174 - 189 %8 Jan 2011 %G eng %U http://www.inf.u-szeged.hu/kepaf2011/pdfs/S05_01.pdf %9 Conference paper %0 Conference Paper %B Signal and Image Processing and Applications (SIPA) %D 2011 %T Order-independent sequential thinning in arbitrary dimensions %A Péter Kardos %A Kálmán Palágyi %E Ioannis Andreadis %E M Zervakis %XSkeletons are region based shape descriptors that play important role in shape representation. This paper introduces a novel sequential thinning approach for n-dimensional binary objects (*n* =1,2,3, ...). Its main strength lies in its order--independency, i.e., it can produce the same skeletons for any visiting orders of border points. Furthermore, this is the first scheme in this field that is also applicable for higher dimensions.

The main issue of this paper is to introduce some conditions for template-based sequential thinning that are capable of producing the same skeleton for a given binary image, independent of the visiting order of object points. As an example, we introduce two order-independent thinning algorithms for 2D binary images that satisfy these conditions. ` `

In this work we present a new thinning scheme for reducing the noise sensitivity of 3D thinning algorithms. It uses iteration-by-iteration smoothing that removes some border points that are considered as extremities. The proposed smoothing algorithm is composed of two parallel topology preserving reduction operators. An efficient implementation of our algorithm is sketched and its topological correctness for (26, 6) pictures is proved. © 2011 Elsevier Inc. All rights reserved.

%B GRAPHICAL MODELS %V 73 %P 335 - 345 %8 Nov 2011 %@ 1524-0703 %G eng %N 6 %9 Journal article %! GRAPH MODELS %R 10.1016/j.gmod.2011.02.001 %0 Conference Paper %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2011 %D 2011 %T A topológia-megőrzés elegendő feltételein alapuló 3D párhuzamos vékonyító algoritmusok %A Gábor Németh %A Péter Kardos %A Kálmán Palágyi %E Zoltan Kato %E Kálmán Palágyi %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2011 %I NJSZT %C Szeged %P 190 - 205 %8 Jan 2011 %G hun %U http://www.inf.u-szeged.hu/kepaf2011/pdfs/S05_02.pdf %9 Conference paper %0 Book Section %B Combinatorial Image Analysis (IWCIA) %D 2011 %T On topology preservation for hexagonal parallel thinning algorithms %A Péter Kardos %A Kálmán Palágyi %E Jake K Aggarwal %E Reneta P Barneva %E Valentin E Brimkov %E Kostadin N Koroutchev %E Elka R Korutcheva %XTopology preservation is the key concept in parallel thinning algorithms on any sampling schemes. This paper establishes some sufficient conditions for parallel thinning algorithms working on hexagonal grids (or triangular lattices) to preserve topology. By these results, various thinning (and shrinking to a residue) algorithms can be verified. To illustrate the usefulness of our sufficient conditions, we propose a new parallel thinning algorithm and prove its topological correctness. © 2011 Springer-Verlag Berlin Heidelberg.

%B Combinatorial Image Analysis (IWCIA) %S Lecture Notes in Computer Science %I Springer Verlag %C Madrid, Spain %P 31 - 42 %8 May 2011 %@ 978-3-642-21072-3 %G eng %9 Conference paper %! LNCS %R 10.1007/978-3-642-21073-0_6 %0 Journal Article %J ALKALMAZOTT MATEMATIKAI LAPOK %D 2010 %T Bejárásfüggetlen szekvenciális vékonyítás %A Péter Kardos %A Gábor Németh %A Kálmán Palágyi %B ALKALMAZOTT MATEMATIKAI LAPOK %V 27 %P 17 - 40 %8 2010 %@ 0133-3399 %G eng %N 1 %9 Journal article %! ALKALMAZOTT MATEMATIKAI LAPOK %0 Conference Paper %B Proceedings of the International Conference on Signal Processing, Pattern Recognition and Applications (SPPRA) %D 2010 %T Topology preserving 2-subfield 3D thinning algorithms %A Gábor Németh %A Péter Kardos %A Kálmán Palágyi %E B Zagar %E A Kuijper %E H Sahbi %XThis paper presents a new family of 3D thinning algorithms for extracting skeleton-like shape features (i.e, centerline, medial surface, and topological kernel) from volumetric images. A 2-subfield strategy is applied: all points in a 3D picture are partitioned into two subsets which are alternatively activated. At each iteration, a parallel operator is applied for deleting some border points in the active subfield. The proposed algorithms are derived from Ma's sufficient conditions for topology preservation, and they use various endpoint characterizations.

%B Proceedings of the International Conference on Signal Processing, Pattern Recognition and Applications (SPPRA) %I IASTED ACTA Press %C Innsbruck, Austria %P 310 - 316 %8 Feb 2010 %G eng %9 Conference paper %0 Book Section %B Proceedings of the International Conference on Image Analysis and Recognition (ICIAR) %D 2010 %T Topology Preserving 3D Thinning Algorithms using Four and Eight Subfields %A Gábor Németh %A Péter Kardos %A Kálmán Palágyi %E Aurélio Campilho %E Mohamed Kamel %XThinning is a frequently applied technique for extracting skeleton-like shape features (i.e., centerline, medial surface, and topological kernel) from volumetric binary images. Subfield-based thinning algorithms partition the image into some subsets which are alternatively activated, and some points in the active subfield are deleted. This paper presents a set of new 3D parallel subfield-based thinning algorithms that use four and eight subfields. The three major contributions of this paper are: 1) The deletion rules of the presented algorithms are derived from some sufficient conditions for topology preservation. 2) A novel thinning scheme is proposed that uses iteration-level endpoint checking. 3) Various characterizations of endpoints yield different algorithms. © 2010 Springer-Verlag.

%B Proceedings of the International Conference on Image Analysis and Recognition (ICIAR) %S Lecture Notes in Computer Science %I Springer Verlag %C Póvoa de Varzim, Portugal %V 6111 %P 316 - 325 %8 June 2010 %G eng %9 Conference paper %! LNCS %R 10.1007/978-3-642-13772-3_32 %0 Book Section %B Proceedings of the Computational Modeling of Objects Represented in Images (CMORI) %D 2010 %T Topology Preserving Parallel Smoothing for 3D Binary Images %A Gábor Németh %A Péter Kardos %A Kálmán Palágyi %E Reneta P Barneva %E Valentin E Brimkov %E Herbert A Hauptman %E Renato M Natal Jorge %E João Manuel R S Tavares %XThis paper presents a new algorithm for smoothing 3D binary images in a topology preserving way. Our algorithm is a reduction operator: some border points that are considered as extremities are removed. The proposed method is composed of two parallel reduction operators. We are to apply our smoothing algorithm as an iteration-by-iteration pruning for reducing the noise sensitivity of 3D parallel surface-thinning algorithms. An efficient implementation of our algorithm is sketched and its topological correctness for (26,6) pictures is proved. © 2010 Springer-Verlag.

%B Proceedings of the Computational Modeling of Objects Represented in Images (CMORI) %I Springer Verlag %C Buffalo, USA %V 6026 %P 287 - 298 %8 May 2010 %G eng %9 Conference paper %R 10.1007/978-3-642-12712-0_26 %0 Conference Paper %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2009 %D 2009 %T Kritikus párokat vizsgáló bejárásfüggetlen szekvenciális vékonyító algoritmus %A Péter Kardos %A Gábor Németh %A Kálmán Palágyi %E Dmitrij Chetverikov %E Tamas Sziranyi %B A Képfeldolgozók és Alakfelismerők Társaságának konferenciája - KÉPAF 2009 %I Akaprint %C Budapest %P 1 - 8 %8 Jan 2009 %G hun %9 Conference paper %0 Book Section %B Proceedings of the International Workshop on Combinatorial Image Analysis (IWCIA) %D 2009 %T An order-independent sequential thinning algorithm %A Péter Kardos %A Gábor Németh %A Kálmán Palágyi %E Petra Wiederhold %E Reneta P Barneva %XThinning is a widely used approach for skeletonization. Sequential thinning algorithms use contour tracking: they scan border points and remove the actual one if it is not designated a skeletal point. They may produce various skeletons for different visiting orders. In this paper, we present a new 2-dimensional sequential thinning algorithm, which produces the same result for arbitrary visiting orders and it is capable of extracting maximally thinned skeletons. © Springer-Verlag Berlin Heidelberg 2009.

%B Proceedings of the International Workshop on Combinatorial Image Analysis (IWCIA) %I Springer Verlag %C Playa del Carmen, Mexico %P 162 - 175 %8 Nov 2009 %@ 978-3-642-10208-0 %G eng %U http://link.springer.com/chapter/10.1007/978-3-642-10210-3_13 %9 Conference paper %R 10.1007/978-3-642-10210-3_13