Guest editorial: Combinatorial problems and algorithms in image analysis

This special issue of the International Journal of Imaging Systems and Technology (IJIST) considers the latest theoretical finds in combinatorial image analysis, as well as related practical applications. Preliminary versions of the articles were presented at the 13 International Workshop on Combinatorial Image Analysis (IWCIA 2009), held in Playa del Carmen, Mexico, in November 2009. The Workshop featured papers which covered a wide range of topics in combinatorial image analysis: a discipline which applies discrete techniques to image analysis. The papers accepted in IWCIA 2009 were selected after a rigorous double-blind review process including three to four reviews per paper by highly qualified experts. This ensured that they were of the highest possible quality and scientific merit. Aside from the traditional theoretical track featured in IWCIA workshops, this year’s forum once again included a Special Track devoted to the applications of image analysis. This issue was a medium for software developers and researchers to introduce and explain their results and to convey a more technical approach to image analysis. An Application Track appears for the second year in a row in IWCIA issues, and we hope to continue this practice in the future. The papers presented at the theoretical track of the Workshop were published as Vol. 5852 of LNCS (Springer, Berlin Heidelberg), while those from the Special Track on Applications appeared in an edited book ‘‘Progress in Combinatorial Image Analysis’’ published by Research Publishing (Singapore–Chennai). Authors of IWCIA 2009 papers were invited to submit substantially extended versions of their conference papers to this special journal issue based on the overall reviewers’ rating of their articles and the relevance of the research to the scope of IJIST. This special issue includes eight papers. They present new structural results and algorithms in digital geometry and topology and address various applications of image analysis and processing. In the first paper, ‘‘Local Image Segmentation with Geometric Filters,’’ Peter Veelaert proposes a mathematical framework for designing filter banks that detect simple geometric features in an image, such as the planarity of the intensity function. The experimental results show how these filters can be used to perform a fast segmentation of an image patch into planar segments. In the next paper ‘‘On Finding an Orthogonal Convex Skull of a Digital Object’’ the authors Mousumi Dutt, Arindam Biswas, Partha Bhowmick, and Bhargab B. Bhattacharya present an O(n log n) time algorithm for computing the orthogonal convex skull of a digital object. This improves an earlier method of quadratic time complexity. In the paper ‘‘Tiled Top-Down Combinatorial Pyramids for Large Images Representation,’’ the authors Romain Goffe, Luc Brun, and Guillaume Damiand introduce the tiled top-down pyramidal framework which provides a full representation of multi-resolution images with both geometrical and topological relationships. Moreover, the top-down model is combined with decomposition in tiles to provide an accurate memory bounding while allowing global analysis of large images. In the paper ‘‘Topology Preserving Parallel Thinning Algorithms’’ by Gábor Németh and Kálmán Palágyi, the authors present several parallel thinning algorithms for (8,4) binary pictures. These are derived from certain sufficient conditions for topology preservation based on three different parallel thinning approaches. The next paper ‘‘Optimal Consensus Set for Digital Line and Plane Fitting’’ is authored by Rita Zrour, Yukiko Kenmochi, Hugues Talbot, Lilian Buzer, Yskandar Hamam, Ikuko Shimizu, and Akihiro Sugimoto. In it, the authors present a new method for fitting a digital line or plane to a given set of points in a 2D or 3D image in the presence of noise. By using a digital model instead of a continuous one, they show that one can generate all possible consensus sets for model fitting. In the paper ‘‘A New Algorithm for Triangulation from Cross Sections and its Application to Surface Area Estimation,’’ the authors Petra Wiederhold and Mario Villafuerte propose a new heuristic (locally determined) algorithm for the triangulation between point sequences representing cross-sectional contours of a surface. The triangulation algorithm is applied to surface area estimation for which polygonal approximations of cross-sectional contours are used. In the next paper ‘‘Measure of Straight Lines for Digital Contour,’’ the authors David Coeurjolly and Isabelle Sivignon use tools of integral geometry to investigate the set of straight lines whose digitization is a given digital straight segment. After defining a measure on such sets, the authors illustrate several applications to digital geometry for contour analysis. In the last paper ‘‘Cubical Cohomology Ring of 3D Pictures’’ by Rocio Gonzalez-Diaz, Maria Jose Jimenez, and Belen Medrano, the authors present a constructive process, made up by several algorithms, to compute the cohomology ring of 3D binary-valued digital pictures represented by cubical complexes. We hope that the works published in this special issue address intriguing and challenging problems in image analysis, and may also be of interest to a broader scientific audience, including researchers working in areas such as pattern recognition, computer vision, image processing, and computer graphics. Before closing this editorial, we acknowledge with sincere gratitude Z.H. Cho, the Editor-In-Chief of the International Journal of Imaging Systems and Technology, for providing us with the opportunity to edit this special issue, and Eugene Veklerov, Associate Editor of IJIST, for his help. Our thanks go to the authors who submitted their works and made this publication possible. We are also grateful to the reviewers for their time and for sharing their critical, yet constructive comments. We would like to extend our thanks to Paul Min, Journal Administrative Assistant, for his careful support throughout the publication process.