This paper introduces a novel technique for analyzing digital curves by identifying turns and twists. A turn or twist, being a local feature, is well-defined for any three consecutive runs. A twist indicates an inflection, while a turn signifies no inflection. Determining the presence of inflections in a digital curve involves identifying twists interspersed among turns. We construct a definite grammar tree within the domain of regular language using a word-theoretic interpretation of pixel runs. We demonstrate how the pre-images of these runs facilitate a combinatorial classification of digital curves in discrete geometry, correlating with the grammar tree classification. This approach results in efficient vectorization of digital curves through a well-defined segmentation that adheres to certain invariant properties . Experimental results are provided to demonstrate the merit and efficacy of our method.

An electrical or an electronic circuit often contains special combinations of circuit symbols in the form of sub-circuits. Identification and analysis of these sub-circuits can substantially simplify the underlying topology of a circuit. This paper explains our maiden attempt towards topological simplification of a circuit by identifying two important classes of sub-circuits—one formed by symbols connected in series and another by symbols connected in parallel. Although a sub-circuit is usually formed with the same type of circuit symbols, our method can handle any combination, irrespective of the symbol types. The method, in general, is based on a novel histogram analysis, mathematical morphology, and geometric features during the symbol identification phase, and a set of adjacency lists representing the connectivity matrix during the analysis phase. The idea may be extended to match topologically similar but spatially different circuits using graph isomorphism. It may also be used for vectorization of circuit drawings utilizing the information on the segmented circuit elements and their connectivity matrices. We have tested the proposed method on a dataset containing 83 scanned images of a variety of electronic and electrical drawings. Some of the results are presented here to demonstrate its efficacy and robustness.

Skew correction of a scanned document page is an important preprocessing step in document image analysis. We propose here a fast and robust skew estimation algorithm based on rank analysis in Farey sequence. Our target document class comprises two major Indian scripts with headlines, namely Devnagari and Bangla. At the beginning, straight edge segments from the edge map of the document page are detected by our algorithm using properties of digital straightness. Straight edges derived in this manner are binned by Farey ranks in correspondence with their slopes. The principal bin, identified from these bins using the strength of accumulated edge points, represents the principal direction along the direction of headlines, from which the gross skew angle is estimated. A fast refinement algorithm is then applied with a finer tuning of Farey ranks, to detect the skew up to the desired level of precision. The algorithm has been tested on a diverse set of document images, containing Bangla and Devnagari scripts. Experimental results are quite encouraging in terms of accuracy, sensitivity to non-textual objects, effectiveness in dealing with unrestricted layouts, and computational efficiency.

A novel algorithm to recognize hand-drawn graphs is proposed. The algorithm uses properties of digital-geometric straightness combined with a new idea of Farey sequence, followed by geometric refinement, in order to speed up the recognition of graph edges. In the next phase, the nodes of the graph - which, being hand-drawn, are very grossly circular - are recognized using the annular regions containing the vertices of their corresponding isothetic covers. Results of the two phases are finally compiled using interval search to output the adjacency list of the graph. The problems of jaggedness, waviness, and similar unforeseen aberrations usually present in a hand-drawn graph are well-tackled by the adopted techniques, as verified by our experimentation on various hand-drawn graphs. Some results have been given in this paper to show the usability and efficiency of the proposed algorithm.

A novel approach towards word segmentation and baseline detection in a handwritten document is proposed. It is based on certain structural properties of isothetic covers tightly enclosing the words in a handwritten document. For an appropriate grid size, the isothetic covers successfully segregates the words so that each cover corresponds to a particular word. By analyzing the horizontal chords of these covers, the corresponding baselines are extracted. The method is fast, robust, and efficient by dint of its traversal strategy along the word boundaries in a combinatorial manner and usage of limited operations strictly in the integer domain. Some results on several Bengali and English handwritings have been given to demonstrate its strength and elegance.

Estimation of discrete curvature is a challenging problem, since a mere replacement of functional derivatives by numerical differences fails to produce the desired result. Several algorithms have been proposed so far, which are mostly based on the concepts of real geometry and hence are computationally expensive. The existing measure of k-curvature, though easy to compute, is crippled with some unwanted syndromes arising out of improper consideration of chain codes. Hence, an improved algorithm for estimating k-curvature is proposed, which is marked by its inherent simplicity and computational attractiveness, and produces the expected estimate, whether the concerned point has an extreme (high or low) curvature or the concerned segment has a constant or changing curvature. Examples and experimental results demonstrate the fitness and effectiveness of the proposed technique for digital curves of arbitrary shapes.

There are several algorithms for digitization of a real disc (circle) to derive a digital disc, and also for finding the real disc corresponding to a digital disc. However, the correspondence of a digital disc with a regular polygon in the real plane is not well studied. This paper presents some theories and related experiments on setting the correspondence from a digital disc to its polygonal cover in the real plane. For an ideal regular polygon covering a digital disc, all the grid points of the digital disc should lie on and inside the polygon, and vice versa. That an ideal regular polygon corresponding to a digital disc is possible for some of the digital discs, especially for the ones having smaller radii, is shown. Further, for a disc whose ideal regular polygon is not possible, an approximate polygon, tending to the ideal one, is possible, in which the error of approximation can be controlled by the number of vertices of the approximate polygon. These (ideal or approximate) polygonal covers of digital discs have several applications in many problems of point set pattern matching. We have reported the conditions under which an ideal regular polygon always exists corresponding to a digital disc, and the conditions under which the existence of an ideal regular polygon becomes uncertain. Experimental results have been given to demonstrate the possibilities of approximation and the trade-off in terms of error versus the number of vertices in the approximate polygon.

Matching and analysis of patterns or shapes in the digital plane are of utmost importance in various problems of computer vision and pattern recognition. A digital point set is such a pattern that corresponds to an object in the digital plane. Although there exist several data structures that can be employed for Approximate Point Set Pattern Matching (APSPM) in the real domain, they require substantial modification to support algorithms in the digital domain. To bridge this gap, a novel data structure called "angular tree" is proposed, targeting an efficient and error-controllable circular range query in the digital plane. The farthest pair of points may be used as the starting correspondence between the pattern set and the background set. Several classical discrete structures and methodologies of computational geometry, as well as some topological features of circles/discs in digital geometry, have been used in tandem, for successful realization of the proposed APSPM algorithm in the digital plane. The APSPM algorithm based on the angular tree has been implemented and tested on various point sets and the reported results demonstrate the efficiency and versatility of the new data structure for supporting APSPM algorithms.

Several existing DSS (digital straight line segment) recognition algorithms can be used to determine the digital straightness of a given one-pixel-thick digital curve. Because of the inherent geometric constraints of digital straightness, these algorithms often produce a large number of segments to cover a given digital curve representing a real-life object=image. Thus, a curve segment, which is not exactly digitally straight, but appears to be visually straight, is fragmented into multiple DSS when these algorithms are run. In this paper, a new concept of approximate straightness is introduced by relaxing certain conditions of DSS, and an algorithm is described to extract those segments from a digital curve. The number of such segments required to cover the curve is found to be significantly fewer than that of the exact DSS-cover. As a result, the data set required for representing a curve also reduces to a large extent. The extracted set of segments can further be combined to determine a compact polygonal approximation of a digital curve based on certain approximation criteria and a specified error tolerance. The proposed algorithm involves only primitive integer operations and thus runs very fast compared to those based on exact DSS. The overall time complexity becomes linear in the number of points present in the representative set. Experimental results on several digital curves demonstrate the speed, elegance and efficacy of the proposed method.

Efficient and successful joining of torn pieces of papers to reconstruct the original documents is an important and challenging issue in many disciplines, especially in forensics and investigation sciences. Automation of the process by means of appropriate techniques can speed up the problem solving substantially. In this paper, we propose a fast, efficient, and useful technique for the reconstruction of hand-torn pages of documents from their images, using contour descriptors for shape-based matching. Chain code of the closed digital arc representing a contour, and its Minkowski sum, have been exploited in our reconstruction work. Experimental results demonstrate the strength and robustness of the method.