*
11/07/2022 *
The Book of Abstracts of IWCIA 2022 is online!

https://www.iwcia2022.org/abstracts/

Wednesday, July 13

13:00-14:30

Opening Session

Chair: Valentin E. Brimkov

13:30-14:30

Keynote: Bhargab Bhattacharya, Indian Statistical Institute, Kolkata, India

Title: Digital Geometry in Medical Diagnostics and Biochemistry

Digital Geometry (DG) has found profound applications in combinatorial image analysis, computer graphics, as well as in several medical diagnostic tools including computerized tomography. In this talk, we will demonstrate two novel applications of DG. First, we discuss how the basic concepts such as digital straightness, discrete curvature, and concavity index can be utilized to develop automated and powerful tools for detecting and classifying various bone-fractures with high accuracy from a class of orthopaedic X-ray images. In the second part of the talk, we will focus on a completely new discipline of biochemistry where DG finds its presence: automated production of fluid samples over a range of concentration factors (called gradients), using a tiny microfluidic device called Lab-on-Chip (LoC). The optimization of reagent-cost and sample-preparation time during gradient generation using droplet-based LoCs is a major challenge to handle. We show that complex-shaped gradients on a discrete grid can be nicely approximated as a sequence of linear gradients. The optimization problem thus reduces to approximating a digital curve on a square grid with the minimum number of digital straight-line segments (DSS) – which is well studied in the literature. Experimental results on various benchmark gradient-profiles establish the efficiency of the method.

14:40-15:40

Session I – Digital Geometry and Topology

Chair: Kálmán Palágyi

14:40-15:00

Rectangularization of Digital Objects and Its Relation with Straight Skeletons

Anukul Maity, Mousumi Dutt, and Arindam Biswas

The rectangular partitioning of a digital object, $A$ (without holes) is presented here. The partitioning is obtained in such a way that the set of connected output rectangles are related to the straight skeleton of the corresponding digital object. The digital object $A$ is imposed on background grid and its inner isothetic cover, $P$, which tightly inscribes the digital object, is obtained. The combinatorial rules are applied on $P$ to partition it into rectangles. The partitioned rectangles and corresponding straight skeleton have applications in shape analysis. The partitioning algorithm discussed here runs in $O(n/g \log n/g)$ where $n$ being the number of pixels on the periphery of digital object and $g$ being the grid size on which the digital object is imposed. The experimental result shows the correctness, robustness and efficacy of the algorithm.

15:00-15:20

On the Number of 0-Tandems in Simple nD Digital 0-Connected Curves

Lidija Comic

A 0-tandem is a configuration of two voxels sharing exactly one vertex. We propose a formula connecting the number of 0-tandems in a simple $n$D digital open or closed 0-connected curve $\gamma$ with the number of cells in $\gamma$. Our formula generalizes the formula by Brimkov et al. (2006) from closed to open curves, and the formula by Maimone and Nordo (2015) from open curves in 3D to open or closed curves in $n$D. We also propose an alternative formula valid for 3D curves.

15:20-15:40

On Density Extrema for Digital Discs

Nilanjana G. Basu, Partha Bhowmick, and Subhashis Majumder

The act of characterizing and measuring different attributes

of primitive shapes is of paramount importance in the subject of discrete geometry. A very rich collection of work can in fact be found in this domain, which are predominantly focused in the Euclidean space. The digital space, on the contrary, is quite unexplored, possibly because of the fact that it has evolved much later and that it does not readily migrate to the continuous space. In this work, we study the unique problem of characterizing density extrema (of integer points) for discs moving on the integer plane. To the best of our knowledge, there has not been a significant study in this direction, which motivates us to look into this problem. As ‘density’ provides a notion of the relative concentration or rarefaction of a collection of points within a given shape or region, it has applications in image analysis and related areas, apart from different branches of physical science. We present some novel results, which are fundamental to understanding density minima and maxima for circular shapes in digital space. We have also pointed out a few more interesting problems that might advance this study further ahead.

15:50-17:10

Session II – Digital Geometry and Topology

Chair: Tibor Lukic

15:50-16:10

Sufficient Conditions for Topology-Preserving Parallel Reductions on the BCC Grid

Kalman Palagyi, Gabor Karai, and Peter Kardos

Parallel reductions transform binary pictures only by changing a set of black points to white ones simultaneously. Topology preservation is a major concern of some topological algorithms composed of parallel reductions. For 3D binary pictures sampled on the body-centered cubic (BCC) grid, we propose a new sufficient condition for topology-preserving parallel reductions. This condition takes some configurations of deleted points into consideration, and it provides a method of verifying that formerly constructed parallel reductions preserve the topology. We present two further sufficient conditions that investigate individual points, directly provide deletion rules of topology-preserving parallel reductions, and allow us to construct parallel thinning algorithms.

16:10-16:30

On the Construction of Planar Embedding for a Class of Orthogonal Polyhedra

Nilanjana Karmakar, Arindam Biswas, Subhas C. Nadly, and Bhargab B. Bhattacharya

2D-representations of 3D digital objects find versatile applications to computer vision, robotics, medical imaging, and in discrete geometry. This work presents an algorithm for constructing a planar embedding with only straight-line edges for a general non-intersecting orthogonal polyhedron that has genus 0. We discover certain characterizations of vertices and edges of a polyhedron that lead to efficient graph-drawing on the 2D plane. The original orthogonal polyhedron can be fully reconstructed from this graph provided the information regarding the coordinates of vertices, are preserved. The time complexity of the proposed embedding is linear in the number of edges of the orthogonal polyhedron.

16:30-16:50

Extractive Text Summarization using Topological Features

Ankit Kumar and Apurba Sarkar

The amount of text data generated these days is increasing exponentially and it is becoming very tedious process to extract meaningful information from the huge amount of text data. In this work we propose two methods to summarize the texts using topological features. First method uses the concept of minimum dominating set to group the sentences into multiple clusters and to find the similarity between clusters using topological features (connected components and tunnels). Sentence scoring and extraction of key sentences from each cluster are done by the existing method of TextRank. The second method uses the pretrained GloVe to represent vectors for words and to find the similarity between sentences using topological features. Classical set cover based algorithm has been used to extract the key sentences for the summary. Both methods are compared on the basis of rouge scores with the existing method, i.e., TextRank and results are satisfactory.

16:50-17:10

Largest Area Parallelogram inside a Digital Object in Triangular grid

Md Abdul Aziz Al Aman, Raina Paul, Apurba Sarkar, and Arindam Biswas

A combinatorial algorithm to construct Largest Area Parallelogram inside a digital object having $n$ contour points lying on a Triangular grid (LAPT) is proposed in this work. A triangular grid consists of three sets of parallel lines where the digital object is imposed and then constructs the inner triangular cover (ITC), where the sides of ITC lies on the grid line and within the object. The proposed algorithm maintain few lists and a set of rules to find the LAPT. The proposed algorithm runs in O(k · n/g lg n/g ) time where n number pixel on the boundary of the digital object, g is grid size, and k is the number of convexities.

Thursday, July 14

13:00-14:00 Keynote Talk

Chair: Reneta Barneva

13:00-14:00

Keynote: Benedek Nagy, Eastern Mediterranean University, Famagusta, Cyprus

Title: Non-traditional 2d Grids in Combinatorial Imaging – Advances and Challenges

On the one hand, the digital image processing and many other digital applications are mostly based on the square grid. On the other hand, there are two other regular grids, the hexagonal and the triangular grids. Moreover, there are eight semi-regular grids based on more than one type of tiles. These non-traditional grids and their dual grids have various advantages over the square grid, e.g., on some of them no topological paradox occur. Most of them have more symmetries, i.e., more directions of symmetry axes and also a smaller angle rotation may transform most of these grids into themselves. However, since most of these grids are not point lattices we need to face some challenges to work with them; they may define various digital geometries. We show how a good coordinate system can be characterized, what type of digital distances are studied, tomography and distance transform. Other grid transformations, including translations and rotations with some of them interesting properties are mentioned. Mathematical morphology and cell complexes are also shown. The advantages and challenges are overviewed by various examples on the triangular grid, as a characteristic example for a non-traditional grid.

14:10-15:30

Session I – Picture Languages

Chair: Arindam Biswas

14:10-14:30

Weighted Three Directions On-line Tessellation Automata and Weighted Hexapolic Automata

Meenakshi Paramasivan and D. Gnanaraj Thomas

Two-dimensional hexagonal arrays seen on a triangular grid can be treated as two-dimensional representations of three-dimensional rectangular parallelepipeds. We are introducing weighted three directions on-line tessellation automata (W3OTA) and investigate formal power series on hexagonal pictures. These are functions that map hexagonal pictures to elements of a semiring and provide an extension of two-dimensional hexagonal picture languages to a quantitative setting.

14:30-14:50

A Myhill-Nerode Theorem for Finite State Matrix Automata and Finite Matrix Languages

Abhisek Midya and D. Gnanaraj Thomas

We propose a deterministic version of finite state matrix automaton DFSMA which recognizes finite matrix languages FML. Our main result is a generalization of the classical Myhill-Nerode theorem for DFSMA. Our generalization requires the use of two relations to capture the additional structure of DFSMA. Vertical equivalence \equiv_v captures that words share the same vertical location, horizontal equivalence \equiv_h captures that words share the same horizontal location. A finite matrix language is defined to be regular if relations \equiv_v and \equiv_h exist that satisfy certain conditions, in particular, they have finite index. We show that the language associated to a DFSMA is regular, and we construct, for each finite matrix language, a DFSMA that accepts this language. Our result provides a foundation for learning algorithms for DFSMA.

14:50-15:10

Algebraic Properties of Parikh q-matrices of Two Dimensional Words

Janaki K, Arulprakasam R., Meenakshi Paramasivan, and Rajkumar Dare V.

Based on idea of q−count of certain subwords of a word, the notion of Parikh q−matrix of a word over an ordered alphabet was introduced. On the other hand, with a two-dimensional picture array of symbols arranged in rows and columns, two kinds of upper triangular matrices, known as row and column Parikh q−matrices have also been introduced and investigated. Certain algebraic properties such as Parikh q−matrices commutators, alternate Parikh q−matrices and extending Parikh q−matrices have been investigated for one dimensional case, yet they do not suffice for two dimensional words. In this paper we introduce Parikh q−matrices commutators, alternate Parikh q−matrices and extending Parikh q−matrices for two dimensional words and discuss their properties. We also derive the result used for transferring information with respect to subword occurrences derived from Parikh q−matrices to corresponding information derived from extending Parikh q−matrices.

15:10-15:30

Adjunct Partial Array Token Petri Net Structure

Kalyani T., Sasikala K., D. G. Thomas, and Bhuvaneswari K.

Adjunct Array Token Petri Net Structure (AATPNS) and Adjunct Hexagonal Array Token Petri Net Structure (AHATPNS) are recently introduced in the literature. Partial Array Token Petri Net Structure (PATPNS) is introduced to generate partial array languages. In this paper, we extend this model using some control device called inhibitor arc and propose Adjunct Partial Array Token Petri Net Structure (APATPNS). It is compared with some partial array generating and recognizing models with respect to the generative power.

15:40-17:00

Session II – Theory and Applications

Chair: Lidija Comic

15:40-16:00

Tomography Reconstruction Based on Null Space Search

Tibor Lukic and Tamara Kopanja

The paper introduces a new tomography reconstruction approach for gray and binary image reconstruction. The proposed method intends to find a solution by searching for the best linear combination of the basis vectors of the null space of the projection matrix. One of the advantage of the proposed approach is that the projection error remains always extremely low, practically equal to zero, during the reconstruction process. The method applies a gradient based optimization algorithm. Experimental evaluation, including three relevant and well-known algorithms for comparison, is presented.

16:00-16:20

Instance Segmentation with Boundary Net

Teodor Boyadzhiev and Krassimira Ivanova

Instance segmentation is one of the key technologies in many domains, such as medical image analysis, traffic and critical infrastructures monitoring, understanding of natural scenes. Recent methods for instance segmentation rely on bounding box regression, however the bounding boxes are not a natural representation for many domains.

We address the limitations of the bounding boxes with a new approach called BoundaryNet, in which we train a fully convolutional neural network to draw the boundaries around each object of each class. The boundaries allow for easy bounding box and mask inference while still providing detailed information about the shape of the object. BoundaryNet avoids the restrictions of YOLO such as the number of bounding boxes, while it is more computationally efficient than the R-CNN methods. The conducted experiments with the proposed neural network architecture BoundaryNet on the Common Object in Context (COCO) dataset show promising results in improving the instance segmentation process.

16:20-16:40

Curvature-Based Denoising of Vector-Valued Images

Christian Gapp and Martin Welk

Salient visual information in images is often concentrated on contours or on regions where edges or curves change their direction abruptly. It is therefore of utmost importance in the processing of images, such as denoising, to preserve this kind of information as much as possible. To address this goal, an interesting class of curvature-based denoising methods has been proposed in recent years, which acts directly on the level lines of grey-value images. In this approach, an image is first transformed into a level-line tree, then the level lines are smoothed, and finally the image is reassembled from level lines. Curvature information with high spatial resolution is generated in this approach, which has also potential for further applications in image analysis. Focusing for now on the denoising task, we propose in the present work an extension of curvature-based smoothing to vector-valued images, with RGB colour images as most prominent application case. Adapting all steps of the original method, we replace first level lines by pseudo-level lines (integral curves of the vector field of directions of least vectorial contrast) and design a robust algorithm for their extraction from a vector-valued image. In this context we also propose a modification of the level line extraction from grey-scale images for the sake of better rotational invariance. Taking into account that intensities along pseudo-level lines, unlike true level lines, are not constant anymore, we further adapt the method such as to store intensity information along the pseudo-level lines, and perform an appropriate smoothing on intensities. Third, we adapt the reconstruction process. We present experiments on grey-scale and colour images to validate our proposed modification of the original grey-scale method as well as our new vector-valued curvature-based denoising method.

16:40-17:00

Face Characterization using Convex Surface Decomposition

Somrita Saha and Arindam Biswas

Although in 2-dimensions, the analysis of the face images

has been done in a detailed way, the characterization of faces from 3D input may be interesting and discerning with respect to the uniqueness of a face. In this work, we have attempted to capture the surface curvature of a 3D face and thereof derive its characteristic features. The approach is based on the convex surface decomposition of the face models. The experimental results are encouraging and is amenable to further treatise

towards better realization of the characterization of a face.

Friday, July 15

13:00-14:00 Keynote Talk

Chair: Giorgio Nordo

13:00-14:00

Keynote: Jessica Zhang, Carnegie Mellon University, Pittsburgh, USA

Title: Machine Learning Enhanced Simulation and PDE-Constrained Optimization for Material Transport Control in Neurons

The intracellular transport process plays an important role in delivering essential materials throughout branched geometries of neurons for their survival and function. Many neurodegenerative diseases have been associated with the disruption of transport. Therefore, it is essential to study how neurons control the transport process to localize materials to necessary locations. First, we develop an isogeometric analysis (IGA) based platform for material transport simulation in neurite networks. We model the transport process by reaction-diffusion-transport equations and represent geometry of the networks using truncated hierarchical tricubic B-splines (THB-spline3D). We solve the Navier-Stokes equations to obtain the velocity field of material transport in the networks. We then solve the transport equations using the streamline upwind/Petrov-Galerkin (SU/PG) method. Next, we develop a novel optimization model to simulate the traffic regulation mechanism of material transport in neurons. The transport is controlled to avoid traffic jam of materials by minimizing a pre-defined objective function. The optimization subjects to a set of partial differential equation (PDE) constraints that describe the material transport process based on a macroscopic molecular-motor-assisted transport model of intracellular particles. Different simulation parameters are used to introduce traffic jams and study how neurons handle the transport issue. Our model effectively simulates the material transport process in healthy neurons and explains the formation of a traffic jam caused by reduced number of microtubules (MTs) and MT swirls in abnormal neurons. To enable fast prediction of the transport process within complex neurite networks, we develop a Graph Neural Networks (GNN) based model to learn the material transport mechanism from simulation data. In this study, we build the graph representation of the neuron by decomposing the neuron geometry into two basic structures: pipe and bifurcation. Different GNN simulators are designed for these two basic structures to predict the spatiotemporal concentration distribution given input simulation parameters and boundary conditions. In particular, we add the residual term from PDEs to instruct the model to learn the physics behind the simulation data. To recover the neurite network, a GNN-based assembly model is used to combine all the pipes and bifurcations following the graph representation. The loss function of the assembly model is designed to impose consistent concentration results on the interface between pipe and bifurcation. Through machine learning, we can quickly and accurately provide a prediction of complex material transport patterns including traffic jam and MT swirls.

14:10-15:30

Discrete Tomography, Picture Languages

Chair: Partha Bhowmick

14:10-14:30

Characterization and Reconstruction of Hypergraphic Pattern Sequences

Michela Ascolese and Andrea Frosini

The notion of hypergraph has been introduced as a generalization of graphs so that each hyperedge is a subset of the set of vertices, without constraints on its cardinality. Our study focuses on $3$-uniform hypergraphs, i.e., those hypergraphs whose (hyper) edges have three as common cardinality. A widely investigated problem related both to graphs and to hypergraphs concerns their characterization and reconstruction from their degree sequences. Concerning graphs, this problem has been efficiently solved in 1960 by Erdős and Gallai, while no efficient solutions are possible in the case of hypergraphs, even in the simple case of 3-uniform hypergraphs, as shown in 2018 by Deza et al. These problems are among the most studied in the fields of Discrete Tomography and, in a more general fashion, of Image Analysis. So, to reduce the NP-hard core of the hypergraph reconstruction problem, we consider a class of degree sequences that show interesting peculiar properties. Here, in particular, we characterize the subclass P of them by using the new notion of pattern and pattern sequence. First, we focus on t-pattern sequences, i.e., sequences with constant pattern t ≥1, and we study the remarkable behaviour of their last elements, called tails. In particular, for any fixed t, we show that the tails tend to a fixed point when increasing the sequences’ lengths. The elements of these fixed points, on varying t, are the same and form the sequence A002620 in OEIS. Finally, we provide a fast algorithm to reconstruct the hypergraphs that realize the sequences in P by iteratively discovering the elements of the characterizing pattern sequence.

14:30-14:50

The Generalized Microscopic Image Reconstruction Problem for Hypergraphs

Niccolò di Marco and Andrea Frosini

In this paper we study a particular case of the microscopic image reconstruction problem, first introduced by Nivat and Frosini and then extended to undirected unweighted graphs by Bar-Noy et al. We consider a general hypergraph H = (V,E) such that each node v has assigned a physical value $l_v$ that we would determine. Since in many applications it may be difficult or almost impossible to directly extract these values, we study how to retrieve them starting from the set of probes $P_v = \sum_{w \in N(w)} l_w$, i.e., the sum of labels of v‘s neighbors. In particular, we prove that the values $l_v$ can be found in polynomial time using linear algebra tools and that the problem can be shifted to undirected weighted graphs trough the concept of 2-section of a hypergraph. Finally, we provide some classes of hypergraphs whose 2-intersection graphs have a specific form (a line or an s-tree) and whose related reconstruction problem from the probes can be performed with the minimum number of zero or one surgical probe.

14:50-15:10

2D Oxide Picture Languages and its Properties

Helen Vijitha Ponraj, Robinson Thamburaj, and Meenakshi Paramasivan

In the theory of formal languages, two-dimensional (picture) languages are a generalization of string languages to two dimensions. Pictures may be regarded as digitized finite arrays occur in the studies concerning pattern recognition, image analysis, cellular automata and parallel computing. Several studies have been done for generating and (or) recognizing rectangular, triangular and hexagonal arrays using the formal syntactic methods. Motivated by oxide molecular structures, the oxide pictures, a special class of two-dimensional pictures is considered. Various generating and recognizing schemes such as Oxide Tiling System, Oxide Wang System, Oxide Tile Rewriting Grammar and Oxide Sgraffito Automata have been developed recently. This paper discusses certain unary operations such as turns and binary operations such as union, overlapping performed on this special class of picture languages.

15:10-15:30

Lyndon Partial Words and Arrays with Applications

Meenakshi Paramasivan, R. Krishna Kumari, R. Arulprakasam, and V. Rajkumar Dare

Lyndon words have been extensively studied in different contexts of free Lie algebra and combinatorics. In this paper, we introduce Lyndon partial words and arrays and also the trees associated with Lyndon partial words. We also study free monoids morphisms that preserve finite Lyndon partial words and check whether a morphism preserves or does not preserve the lexicographic order.

Abstracts - IWCIA 2022
Abstracts Schedule made according to local Rome, Italy time UTC/GMT+2, please check https://www.timeanddate.com/worldclock for your respective time.Note: the names with underlining correspond to authors who will present the work. Wednesday, July 13 13:00-14:30 Opening SessionChair: Valentin E. Brimk...