Selected topics of combinatorial image analysis

The present special issue of the International Journal of Computer Mathematics (IJCM) is devoted to the 14th International Workshop on Combinatorial Image Analysis (IWCIA 2011), held in Madrid, Spain, in May 2011.

Along with the more traditional approaches to image analysis, the one based on ‘discrete’, or ‘combinatorial’ structures and algorithms, is becoming increasingly important. As the processed images are usually discrete, it appears quite natural to design essentially discrete mathematical tools and algorithms that process the available discrete (or ‘digital’) data sets directly, using integer arithmetic, thus avoiding errors due to rounding. Often combinatorial methods outperform (in terms of speed and accuracy) solutions based on numeric computations.

The IWCIA series provides a common forum for researchers from all-over the world, where they can present their research findings, discuss recent advances in the area of image analysis, and promote collaboration with each other. In Madrid, the IWCIA workshop series celebrated its 20th anniversary. The workshop received 60 submissions. All papers were refereed by at least three reviewers in a double-blind setting. As a result, 25 papers were accepted for oral and 13 for poster presentation and for inclusion in the conference proceedings published as volume 6636 of Springer's Lecture Notes in Computer Science. After the conference, the authors of 21 papers were invited to submit substantial extensions of their conference papers to this special issue of IJCM. The selection criteria for invitation included the score received from workshop reviews and the paper relevance to IJCM scope. After a long and quite rigorous reviewing process by at least two referees, including two to three review/revision rounds, nine papers have been recommended for publication. We believe that as a result of the very careful and rigorous selection and refereeing process the present journal issue contains only papers of very high quality.

The first four papers are from the area of digital geometry and its applications to image analysis. In the paper ‘A combinatorial algorithm to construct 3D isothetic covers’ by Nilanjana Karmakar, Arindam Biswas, Partha Bhowmick, and Bhargab B. Bhattacharya, the authors present a combinatorial algorithm for construction of outer and inner isothetic covers of a 3D digital object 5. Such a cover can be useful for obtaining a unique approximation of 3D objects as well as of shape-related information. Experimental results have demonstrated the algorithm's effectiveness.

In the paper ‘Topology-preserving hexagonal thinning’ the authors Péter Kardos and Kálmán Palágyi point out certain basic similarities and differences between topological properties of binary digital objects defined on orthogonal and hexagonal grids 4. They present various characterizations of simple points and as well as new sufficient conditions for topology-preserving reductions on hexagonal grids. These results can be used in the design of thinning techniques for producing skeleton-like shape features in a topology-preserving way.

In the paper ‘A Jordan curve theorem with respect to a pretopology on ℤ²’, Josef Šlapal studies a pretopology on ℤ² with the property that the Khalimsky topology is one of its quotient pretopologies 8. The author proves an analog of the Jordan curve theorem for this pretopology, thus showing that such a pretopology provides a large variety of digital Jordan curves.

In the paper ‘Isoperimetrically optimal polygons in the triangular grid with Jordan-type neighbourhood on the boundary’, the authors Benedek Nagy and Krisztina Barczi define two types of neighbourhood relations on a triangular grid and use them to define digital circles 6. They show that certain special hexagons are Pareto optimal. The latter implies that the so-defined polygons have maximal area among the objects whose perimeter is at most a given length, and have minimal perimeter among objects enclosing at most a certain area.

The next two papers are devoted to some problems of discrete geometry and algorithms for their solutions. In the paper ‘Approximability issues of guarding a set of segments’, Valentin E. Brimkov considers a geometric version of the set cover problem, in which one looks for the minimum number of ‘guards’ that can monitor a set of segments in the plane 2. In view of the fact that this last problem is still NP-hard, the author studies various approximability issues and defines subclasses for which efficient algorithms exist. Possible applications are particularly seen in surveillance and security.

In the paper ‘Recognition of concurrency relations between inaccurate lines’, Peter Veelaert and Michael Heyvaert propose a new efficient method for recognizing multiple concurrency relations between inaccurately drawn lines 9. A solution is found by combining borderline cases, for whose efficient encoding the authors introduce the concept of a ‘rank vector’ which evaluates the degrees of freedom that are left when a line is pushed within its borders towards a solution. Experiments demonstrate that the proposed method is superior to the existing conventional non-linear problem-solvers.

In the next paper titled ‘Singularity analysis of digital signals through the evaluation of their unpredictable point manifold’, the authors Oriol Pont, Antonio Turiel, and Hussein Yahia present an algorithm for estimating the values of singularity exponents at every point of a digital signal of any dimension 7. They show that the key ingredient for robust and accurate reconstructability performance lies on the definition of multiscale measures in the sense that they encode the degree of singularity and the local predictability at the same time.

In the paper ‘Expressiveness and complexity of regular pure 2D context-free languages (RP2DCFL)’, Marcello Bersani, Achille Frigeri, and Alessandra Cherubini study picture languages and related closure properties of (regularly controlled) pure 2D context-free grammars, as for the latter NP-hardness of parsing is proved 1. Moreover, comparison with other interesting picture grammars clarifies their mutual relationship with respect to expressiveness.

In the last paper titled ‘Ischemic heart disease detection using selected machine learning methods’, Marcin Ciecholewski presents a new method for diagnosis of ischemic heart disease 3. It is based on certain concepts from optimization theory, which make it possible to formulate the problem for support vectors and then use the Osuna – Platt algorithm for the considered problem. The author compares experimentally his approach with other known methods and makes conclusions about its accuracy and sensitivity.

We believe that this special issue would be of interest not only to researchers in the area of image analysis, but also to the broader audience of IJCM.

We would like to thank everyone who contributed to this publication. First of all, we are sincerely grateful to Professor George Loizou, Editor-In-Chief of the IJCM, for providing us with the opportunity to edit this special issue, and for his overall support. We would like to thank all authors who submitted papers and made this publication possible. We are obliged to the referees for their time and for their critical and constructive comments. We are thankful to Ms. Lucy Francis from IJCM Editorial Office, and Ms. Katie Chandler, Publisher responsible for IJCM at Taylor & Francis, for their assistance during the publication process.