The paper points out that while automatic image tagging is often studied in connection with content-based image retrieval (CBIR), it is actually a much harder problem. Given the difficulty of the latter, the prospects for automatic image tagging do not appear promising. A brief survey of the current state of the art confirms that conclusion. Then the paper discusses an effort to tag images based on nonpixel data and proceeds with the outline of a case where the difficulty of automatic tagging is taken advantage to construct image based CAPTCHA to distinguish human users from Web-bots. That has led to certain interesting approaches to achieve reliable human tagging that is needed for the CAPTCHA application.

Two-dimensional symbologies have been around for a while but they did not reach the broad public until the last few years. Examples include the "bull's eye" code that appears in all United Parcel Service packages and the two-dimensional bar code PDF417 that appears in driver's licenses in several states, metered postage, and identity documents. The paper covers the basic principles of the design of such codes, problems associated with their reading, and examples of applications. It also reviews how such symbologies are related to OCR-based document reading and how the technologies can supplement each other.

We present the RoadFinder Front End (RFFE), a fully automated system that identifies lines of communications (roads) in high altitude imagery. The system combines an effective road seed generator, a behavioral model, and an efficient mechanism for connecting the road seeds. The model associates a cost to filling gaps, turns and inflections in the roads. RFFE is demonstrated using several image sensor types.

We propose a new thinning algorithm based on line sweep operation. Assuming that the contour of the figure to be thinned has been approximated by polygons, the "events" are then the vertices of the polygons, and the line sweep algorithm searches for pairs of edges lying within each slab. The pairing of edges is useful for detecting both regular and intersection regions. The regular regions can be found at the sites where pairings between edges exist. Intersection regions are those where such relations would cease to exist. A salient feature of our approach is that it finds simultaneously the set of regular regions that attach to the same intersection region. Such a set is thus called an intersection set. The output of our algorithm consists of skeletons as well as intersection sets, both can be used as features for subsequent character recognition. Moreover, the line sweep thinning algorithm is efficient in computation as compared with a pixel-based thinning algorithm which outputs skeletons only.

In a previous article (Proc. 3rd Int. Conf. Document Anal. and Recogn., Montreal, Canada, pp. 227-30, 1995), we showed that a line sweep algorithm is an efficient means of line thinning. A line sweep is a process that works on polygonal figures and pairs the edges that bound the figure interior from two sides. In this article, we improve and extend this approach in the following way. First, a new method is used for grouping paired edges into regular and intersection regions. The regular regions can be found at the site where pairings between edges exist. Intersection regions, on the other hand, are where such relations cease to exist, due to the fact that pair relations between edges of wide distance are cancelled. Secondly, a salient feature of our new approach is to simultaneously find the set of regular regions that attach to the same intersection region. Such a set is called an intersection set. The output of our algorithm consists of skeletons as well as intersection sets. Both of them can be used as features for subsequent character recognition. Moreover, the line sweep thinning algorithm is efficient in computation as compared with a pixel-based thinning algorithm which outputs skeletons only.

Font recognition and contextual processing are developed as two components that enhance the recognition accuracy of a text recognition system presented in a previous paper ((H. Shi and T. Pavlidis, 1996). Font information is extracted from two sources: one is the global page properties, and the other is the graph matching result of recognized short words such as a, it and of etc. Contextual processing is done by first composing word candidates from the recognition results and then checking each candidate with a dictionary through a spelling checker. Positional binary trigrams and word affixes are used to prune the search for word candidates.

Human vision is guided by context but it has been difficult to replicate that process in machine vision. On the other hand bar codes have a precise formal definition so that high level structure (the equivalent) of context is used to guide low level recognition. The paper discusses some of the processes involved in bar code reading and uses them to suggest novel processes for mechanical text reading.

We propose a new thinning algorithm based on line sweep procedures. A line sweep is a process where the plane is divided into parallel slabs by lines passing through certain "events" and then items are processed according to an order of the slabs. Assuming that the contours of the object that are to be thinned have been approximated by polygons, the "events" are then the vertices of the polygons and the line sweep algorithm looks for pairs of polygon sides that lie within each slab. Since the procedure is applied in both horizontal and vertical direction, possible conflicts may exist among the pairs of polygon sides. A subsequent effort is to resolve the conflicts according to a few generic types into which they can be classified. After the conflict resolution, the object can be decomposed into the regions that can be represented by the skeletons computed from the pairs of polygon sides, and the regions that are the singular parts of the object. Both types of regions can be used as features for subsequent pattern recognition operations.

Past research in shape analysis and OCR has often emphasized graph matching techniques. We propose to use matching of graph embeddings because this is what is actually of interest. In this way we obtain faster and simpler algorithms since most decisions can be made on the basis of graph labels (the geometry of the embedding) rather than the topology of the graph. The latter has to examined only in very few cases. The proposed algorithm consists of four sieves that compare branches of two embeddings by (normalized), angle, y-position, x-position, and length. Pairs of graphs that pass all the sieves have a node correspondence established so the next step compares degrees. Finally paths are determined using Kleene's algorithm and compared with prototype arcs.

A segmentation-free approach to OCR is presented as part of a knowledge-based word interpretation model. It is based on the recognition of subgraphs homeomorphic to previously defined prototypes of characters. Gaps are identified as potential parts of characters by implementing a variant of the notion of relative neighborhood used in computational perception. Each subgraph of strokes that matches a previously defined character prototype is recognized anywhere in the word even if it corresponds to a broken character or to a character touching another one. The characters are detected in the order defined by the matching quality. Each subgraph that is recognized is introduced as a node in a directed net that compiles different alternatives of interpretation of the features in the feature graph. A path in the net represents a consistent succession of characters. A final search for the optimal path under certain criteria gives the best interpretation of the word features. Broken characters are recognized by looking for gaps between features that may be interpreted as part of a character. Touching characters are recognized because the matching allows nonmatched adjacent strokes. The recognition results for over 24,000 printed numeral characters belonging to a USPS database and on some hand-printed words confirmed the method's high robustness level.>

Traditionally, zero crossings of the second derivative provide edge features for the classification of blurred waveforms. The accuracy of these edge features deteriorates in the case of severely blurred images. In this paper, a new feature is presented that is more resistant to the blurring process, the image, and waveform peaks. In addition, an estimate of the standard deviation /spl sigma/ of the blurring kernel is used to perform minor deblurring of the waveform. Statistical pattern recognition is used to classify the peaks as bar code characters. The noise tolerance of this recognition algorithm is increased by using an adaptive, histogram-based technique to remove the noise. In a bar code environment that requires a misclassification rate of less than one in a million, the recognition algorithm showed a 43% performance improvement over current commercial bar code reading equipment.>

A method for the recognition of multifont printed characters is proposed, giving emphasis to the identification of structural descriptions of character shapes using prototypes. Noise and shape variations are modeled as series of transformations from groups of features in the data to features in each prototype. Thus, the method manages systematically the relative distortion between a candidate shape and its prototype, accomplishing robustness to noise with less than two prototypes per class, on average. The method uses a flexible matching between components and a flexible grouping of the individual components to be matched. A number of shape transformations are defined, including filling of gaps, so that the method handles broken characters. Also, a measure of the amount of distortion that these transformations cause is given. Classification of character shapes is defined as a minimization problem among the possible transformations that map an input shape into prototypical shapes. Some tests with hand-printed numerals confirmed the method's high robustness level.>

In the framework of structural character recognition, the authors present a method to reduce the number of prototypes to match with a given sample. The basic idea is that a coarse description of the sample, even if not adequate for the recognition, can be powerful enough to discriminate among the prototypes those that most likely will match the sample. Once this subset has been found, a more detailed description is computed, and the main classification step entered. To achieve the purpose, a multilevel description of the character, in terms of the features provided by the feature extractor. At the intermediate level, the character is decomposed into components by removing the branch points. Eventually, each component is further split into simple, meaningful parts called superfeatures. By using the highest level of the description a fast and reliable selection of the prototypes to be considered as candidates for the matching can be obtained, while the lowest one is used by the main classifier to choose which one of the prototypes, among the selected ones, has the best matching with the sample. Experiments have proved that the method is correct and efficient. It is correct since it makes it possible to select a subset of prototypes which always contains the right one, and it is efficient since it significantly reduces the number of prototypes to be matched with the sample.>

It is known that when a bilevel image is blurred, the intensity of the original pixels is related with the sign of the curvature of the pixels of the blurred image. A technique for threshold selection is presented where a partial histogram is constructed solely from the pixels where curvature achieves extrema values. The method is most suitable when low-contrast images with textured backgrounds (but not sparse dot matrices) are a large fraction of the input population.>

A segmentation-free approach to OCR is presented as part of a knowledge based word interpretation model. This method is based on the recognition of subgraphs homeomorphic to previously defined prototypes of characters. Gaps are identified as potential part of characters by implementing a variant of the notion of relative neighborhood used in computational perception. In the system, each subgraph of features that matches a previously defined character prototype is recognized anywhere in the word even if it corresponds to a broken character or to a character touching another one. Each subgraph that is recognized is introduced as a node in a direct net that compiles different alternatives of interpretation of the features in the feature graph. A final search for the optimal path under certain criteria gives the best interpretation of the word features.>

A method for recognizing degraded text is described. One application domain is postal address blocks, where the system must function with varying and unspecified fonts, dot matrix printing, and poor print quality. The design achieves tolerance to differing contrast and degraded print via gray-scale analysis, and omnifont capability and good performance on touching and broken characters by encoding character shapes as graphs. Experimental results on address blocks supplied by the US Postal Service are presented. Experiments on subsampling the data indicate that the performance at 100 dpi is very close to that of the original 300 dpi.>

A method for feature extraction directly from gray-scale images of scanned documents without the usual step of binarization is presented. This approach eliminates binarization by extracting features directly from gray-scale images. In this method, a digitized gray-scale image is treated as a noisy sampling of the underlying continuous surface and desired features are obtained by extracting and assembling topographic characteristics of this surface. The advantages and effectiveness of the approach are both shown theoretically and demonstrated through preliminary experiments of the proposed method.>

An algorithm for processing closely spaced edges and accurately restoring their locations is presented. The convolution distortion model is based on interacting edges. The restoration algorithm takes three edges as input and forces the effects of two of them to cancel each other. Thus the third edge appears to be isolated and is located using a traditional edge detector. Experiments on bar code waveforms reveal that this approach outperforms the current commercial bar code readers.

An approach to feature extraction that eliminates binarization by extracting features directly from gray scale images is presented. It not only allows the processing of poor quality input (e.g., low contrast, dirty images), but also offers the possibility of significantly lower resolution for digitization.>

Previous bar code decoding algorithms operated on the binarized output of a hardware digitizer which limited the working range of the algorithm. The authors propose a new and more aggressive bar code decoder that operates on the location of the peaks of the bar code waveform. This algorithm can operate in high convolution distortion environments and is based on statistical pattern recognition techniques. However no training data is required and the misdecode rate is controlled by a single adjustable parameter.>

A new technique for page segmentation without skew normalization is described and applied to both English and Japanese complex printed-page layouts. There is no need to make any assumption about the shape of blocks, hence the technique can handle not only skewed pages but it can also be extended to handle documents where columns are not rectangles. In this technique, based on the bottom-up strategy, the connected components are extracted on the reduced image and are classified with their local information. Since the skew angle is also estimated with the local information of blocks, the computational time is very short. Merging text blocks into string lines and into columns is performed with the skew information.>

An algorithm that attempts to improve a triangulation by shifting the vertices so that curvature within the triangles is nearly equal is presented. Unnecessary triangles are removed. The method is an effective way of guaranteeing that the triangle vertices are points of higher curvature, and that the triangle edges correspond to distinctive edges on the surfaces. Triangulations of surfaces with constant curvature-and hence no distinctive features-will gain nothing from this or any other optimization algorithm. As demonstrated by the results, the techinque of moving triangle vertices can improve some triangulation models. Greatest improvements occur with surfaces characterized by sharp edges, such as the pyramid and ridge models. Less improvement occurs on models that already approximate the surface topology and/or have less distinctive features.>

Fully automatic road recognition remains an elusive goal in spite of many years of research. Most practical systems today use tedious manual tracing for the entry of data from satellite and aerial images to geographical data bases. The paper presents a semi-automatic method for the entry of such data. First ribbons of high contrast are found by analyzing gray scale surface principal curvatures. Then, pixels belonging to such ribbons are fitted by conic splines, and then a graph is constructed whose nodes are end points of the arcs fitted by the splines. The key new idea is to assign edges between all nodes and label them with a cost function based on physical constraints on roads. Once a pair of end points is chosen, a shortest path algorithm is used to determine the road between them. Thus a global optimization is performed over all possible candidates.>

A method for the recognition of multifont printed characters is proposed, giving emphasis to the identification of structural descriptions of character shapes using prototypes. Noise and shape variations are modeled as series of transformations from groups of features in the data to features in each prototype. Thus, the method manages systematically the relative distortion between a candidate shape and its prototype, accomplishing robustness to noise with less than two prototypes per class, on the average. Our method uses a flexible matching between components and a flexible grouping of the individual components to be matched. A number of shape transformations are defined. Also, a measure of the amount of distortion that these transformations cause is given. The problem of classification of character shapes is defined as a problem of optimization among the possible transformations that map an input shape into prototypical shapes. Some tests with hand printed numerals confirmed the method's high robustness level.>

It is shown that in a very simple form residual analysis achieves results that are at least as good as if not better than those obtained by other techniques. There are many ways for extensions of the method. For example, moving average filters of regularization can be used to obtain the residual images. Also, the strength of the correlation, measured by D/sub rr/(O), can be used to eliminate noise, weak edges, etc. A more ambitious extension is by considering smoothing filters that leave invariant the function representing the reflectance from smooth surfaces.>

Images are considered as consisting of three parts: features, noise, and smooth components. After a smoothing operation, the difference between the result and the original image has the characteristics of noise in areas away from features. Systematic trends in the difference indicate features such as edges, corners, or textures. It is shown that the autocorrelation function of the residuals takes specific forms when computed along various paths, and in particular along a circle or a disk centered at a zero crossing of residuals. Then, feature detection is reduced to classifying the autocorrelation profile. An implementation of this technique is described.>

A hierarchical triangulation built from a digital elevation model in grid form is described. The authors present an algorithm that produces a hierarchy of triangulations in which each level of the hierarchy corresponds to a guaranteed level of accuracy. The number of very thin triangles (slivers) is significantly reduced. Such triangles produced undesirable effects in animation. In addition the number of levels of the triangulated irregular network (TIN) tree is reduced. This speeds up searching within the data structure. Tests on data with digital elevation input have confirmed the theoretical expectations. On eight such sets the average sliveriness with the method was between 1/5 and 1/10 of old triangulations and number of levels was about one third. There was an increase in the number of descendants at each level, but the total number of triangles was also lower.>

Some basic problems encountered when assembling the results of image analysis on architectures with coarse parallelism are discussed. The emphasis is on strategies that minimize the distortion in the final result caused by processing image tiles independently. Methods are presented that can be used to reduce the disparity between the results of processing each title independently and processing each as part of a whole image. A seaming algorithm has been constructed to seam the tiles with the results of region segmentation using the gray-level mean difference or maximum-minimum criteria. Experimental results, obtained on a Sequent machine and a Sun 3/160 workstation, are given to illustrate the performance of the algorithm.>

A method that combines region growing and edge detection for image segmentation is presented. The authors start with a split-and merge algorithm wherein the parameters have been set up so that an over-segmented image results. Region boundaries are then eliminated or modified on the basis of criteria that integrate contrast with boundary smoothness, variation of the image gradient along the boundary, and a criterion that penalizes for the presence of artifacts reflecting the data structure used during segmentation (quadtree in this case). The algorithms were implemented in the C language on a Sun 3/160 workstation running under the Unix operating system. Simple tool images and aerial photographs were used to test the algorithms. The impression of human observers is that the method is very successful on the tool images and less so on the aerial photograph images. It is thought that the success in the tool images is because the objects shown occupy areas of many pixels, making it is easy to select parameters to separate signal information from noise.>

The definition of optimal correspondent subsequence (OCS), which extends the finite alphabet editing error minimization matching to infinite alphabet penalty minimization matching, is given. The authors prove that the string distance derived from OCS is a metric. An algorithm to compute the string-to-string OCS is given. The computational complexity of OCS is analyzed. OCS is more efficient than relaxation and elastic matching for 1D problems. An algorithm combining syntactic information in template matching is given to show the ease of integrating regular grammar into the OCS technique. Since in different applications different penalty functions may be required, two of them are discussed: one pointwise and the other piecewise. The pointwise application consists of a stereo epipolar line matching problem solved by using string-to-string OCS. The feasibility of applying OCS to UPC bar-code recognition is investigated, showing the elegance of string-to-regular-expression OCS compared to the relaxation and elastic matching techniques.>

The authors provide theoretical justification for the use of zero crossings of residuals (between a filtered image and the original) for edge detection. The smoothed version is obtained by bilinear interpolation as a result of two-dimensional discrete regularization of subsampled images. The method is also applicable to smoothed images obtained by convolution with a Gaussian. Examples of applications of the method are shown for three kinds of pictures: aerial photographs, low-quality pictures of tools, and a high-quality picture of a face. The same parameters are used in all the examples. In addition they show examples of the results of one of the Canny edge detectors on the same pictures.>

The authors present a method that combines region growing and edge detection for image segmentation. They start with a split-and-merge algorithm where the parameters have been set up so that an oversegmented image results. Then region boundaries are eliminated or modified on the basis of criteria that integrate contrast with boundary smoothness, variation of the image gradient along the boundary, and a criterion that penalizes for the presence of artifacts reflecting the data structure used during segmentation (quadtree, in this case).>

A postprocessor of the split-and-merge procedure is presented to solve two problems encountered in image segmentation: (1) the proper setting of parameters is difficult and the result may be undergrown (too many regions) or overgrown (too few regions); and (2) the outlines obtained do not lie at edges. The postprocessor carries out two operations, namely, boundary elimination and edge editing, to solve these two problems, respectively. The processing time of these two procedures grows about linearly with the image complexity.>

Regularization is equivalent to fitting smoothing splines to the data so that efficient and reliable numerical algorithms exist for finding solutions. however, the results exhibit poor performance along edges and boundaries. To cope with such anomalies, a more general class of smoothing splines that preserve corners and discontinuities is studied. Cubic splines are investigated in detail, since they are easy to implement and produce smooth curves near all data points except those marked as discontinuities or creases. A discrete regularization method is introduced to locate corners and discontinuities in the data points before the continuous regularization is applied.>

We describe the current state of a system that recognizes printed text of various fonts and sizes for the Roman alphabet. The system combines several techniques in order to improve the overall recognition rate. Thinning and shape extraction are performed directly on a graph of the run-length encoding of a binary image. The resulting strokes and other shapes are mapped, using a shape-clustering approach, into binary features which are then fed into a statistical Bayesian classifier. Large-scale trials have shown better than 97 percent top choice correct performance on mixtures of six dissimilar fonts, and over 99 percent on most single fonts, over a range of point sizes. Certain remaining confusion classes are disambiguated through contour analysis, and characters suspected of being merged are broken and reclassified. Finally, layout and linguistic context are applied. The results are illustrated by sample pages.

We describe a method for inferring constraints that are desirable for a given (rough) drawing and then modifying the drawing to satisfy the constraints wherever possible. The method has been implemented as part of an online graphics editor running under the UNIX™ operating system and it has undergone modifications in response to user input. Although the framework we discuss is general, the current implementation is polygon-oriented. The relations examined are: approximate equality of the slope or length of sides, collinearity of sides, and vertical and horizontal alignment of points.

The correlation coefficients are used for segmentation according to texture. They are first evaluated on a set of square regions forming two levels of the quadratic picture tree (or pyramid). If the coefficients of a square and its four children in the tree are similar, then that region is considered to be of uniform texture. If not, it is replaced by its children. In this way, the split-and-merge algorithm is used to achieve a preliminary segmentation. It is followed by a grouping algorithm using the correlation coefficients and the region adjacency graph, plus a small region elimination step. The latter regions are grouped according to their gray level because texture cannot be defined reliably on very small regions. Examples of implementation on four pictures are included.

Conic splines are formed by arcs of conics, each defined by its endpoints and the tangents at them plus an intermediate point.Instead of the common general equation that depends on five parameters, an equation with a single parameter is used, thus simplifying significantly the curve fitting problem.The resulting guided conics resemble Bezier polynomials and for parabolas are identical to them.Such splines can be used conveniently both for interactive design and for automatic curve fitting.They allow circular, elliptical, and hyperbolic arcs to be included in the spline family, while the common forms using a B-spline basis allow the inclusion of parabolic arcs only.Conic splines are described either in a rational parametric or in algebraic form f(x, y) = 0.A simple estimate for the distance of a point from such a curve is given and is used to test the quality of approximations.The data to be fitted are first approximated by a polygon, and then simple heuristics are used to decide which sequences of vertices should be approximated by conics.The conics found by the applications of the heuristics are usually close approximations of the data and need no further adjustments.When adjustments are needed, the interval is split and a conic is fitted on each part.It is shown theoretically that exact knot placement at the optimal locations is less important for higher order splines than for polygons.Examples of application of the method to the fitting of font and other contours are given.Comparisons with other methods suggest that conic splines require no more knots than cubic splines for similar quality of approximation.

The paper discusses algorithms for filling contours in raster graphics. Its major feature is the use of the line adjacency graph for the contour in order to fill correctly nonconvex and multiply connected regions, while starting from a “seed.” Because the same graph is used for a “parity check” filling algorithm, the two types of algorithms can be combined into one. This combination is useful for either finding a seed through a parity check, or for resolving ambiguities in parity on the basis of connectivity.

The k-syntactic similarity approach is couched in graphical representation terms and its ability to provide global recognition capability while retaining a low time complexity is explored. One potential application domain, that of composite shape decomposition into approximately convex subshapes, is described. This is shown to be equivalent to finding cycles within a particular graph. The approach yields valid decompositions in many cases of interest, and is capable of identifying those cases where additional semantic considerations are necessary for proper analysis. The permissible graph structures representing composite shapes given a reasonable set of relations are determined. Experimental results on nonideal data are given.

Algorithms for shape analysis are reviewed and classified under various criteria, whether they examine the boundary only or the whole area and whether they describe the original picture in terms of scalar measurements or through structural descriptions. The emphasis is on methodologies which have been popular during the last five years and among them, those which are information preserving.

The algorithm described in this paper uses the geometric distance between con ductor boundaries as the criterion for a printed wiring board fault detection. A paging scheme is used so that only small parts of the picture need be stored in core. This also makes the method easily amenable to parallelism.

This Special Issue is composed of the papers selected from the 1978 IEEE Computer Society Workshop on Pattern Recognition (PR) and Artificial Intelligence (Al) held in Princeton, NJ, April 12-14, 1978. The Workshop was sponsored by the Technical Committee on Machine Intelligence and Pattern Analysis. Inevitably, the contributors to the Workshop determined, to a large degree, the tone and complexion of this Special Issue. For this reason, a brief account of the Workshop Proceedings, though now history, is given. About half of the papers presented at the Workshop were also submitted for the Special Issue, a total of 37. Those of high quality were far more than the number that could be accommodated within the available number of pages. We decided to choose three topics where the interaction between the methodologies of PR and Al was most prevelant: analysis of images, analysis of speech, and certain general algorithms. All the selected papers present either theoretical, or experimental results, or both. We felt that such results clearly demonstrate the progress achieved and can be seen as very impressive if measured against the difficult problem of emulating functions associated with human intelligence by machines. It is true that they often fall short from some of the earlier ambitious goals, but the time is probably ripe to reexamine such goals in view of the accumulated experience. The following is a brief scanning of the contents of this issue, especially as related to the integration and/or interaction of PR and Al methodologies.

Description of contours in terms of complex arcs allows the use of simple algorithms for matching. An example of such matchings for island contours is included.

In many cases a picture is described in terms of various plane objects and their shape. This paper describes a parser whose input is a piecewise linear encoding of a contour and whose output is a string of high-level descriptions: arcs, corners, protrusions, intrusions, etc. Such a representation can be used not only for description but also for recognition. Previous syntactic techniques for contour description have often used high-level languages for the description of contours. This has been necessary in order to guarantee contour closure and eliminate the noise. In the present approach the numerical preprocessing of the contour removes most of the noise and also produces the answers to certain simple questions about its shape. Therefore, simpler grammars can be used for the contour description. Examples of descriptions of contours are given for handwritten numerals, white blood cells, and printed wiring circuit boards.

A method is described for automating the counting of asbestos fibers in air samples by computer processing of digitized pictures. Preliminary results show the method is feasible.

The problem of locating optimally the breakpoints in a continuous piecewise-linear approximation is examined. The integral square error E of the approximation is used as the cost function. Its first and second derivatives are evaluated and this allows the application of Newton's method for solving the problem. Initialization is performed with the help of the split-and-merge method [8]. The evaluation of the derivatives is performed for both waveforms and contours. Examples of implementation of both cases are shown.

A method is described for the recognition of free-form (unconstrained) handwritten numerals. At first the tracings of the input characters are converted into polygons, and then they are processed by a general syntactic parser whose output is a high-level representation in terms of strokes, quadratic arcs, corners, etc., in much the same way as a human observer might. Next a number of regular expressions are defined which characterize each class of symbols, and the final recognition is performed by a finite automaton. The method was tested on IEEE Data Base 1.2.2 with a success rate of about 95 percent.

Certain theoretical aspects of fuzzy decision trees and their applications are discussed. The main result is a branch-bound-backtrack algorithm which, by means of pruning subtrees unlikely to be traversed and installing tree-traversal pointers, has an effective backtracking mechanism leading to the optimal solution while still requiring usually only O(log n) time, where n is the number of decision classes.

In the past, picture segmentation has been performed by merging small primitive regions or by recursively splitting the whole picture. This paper combines the two approaches with significant increase in processing speed while maintaining small memory requirements. The data structure is described in detail and examples of implementations are given.

article The Use of Algorithms of Piecewise Approximations for Picture Processing Applications Share on Author: Theodosios Pavlidis Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 2Issue 4Dec. 1976 pp 305–321https://doi.org/10.1145/355705.355706Online:01 December 1976Publication History 13citation433DownloadsMetricsTotal Citations13Total Downloads433Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A technique for decomposition of polygons into simpler components is described and illustrated with applications in the analysis of handwritten Chinese characters and chromosomes. Polygonal approximations of such objects are obtained by methods described in the literature and then parts of their concave angles are examined recursively for separating convex or other simple shape components. Further decomposition of the latter is possible. The final result can be expressed as a labeled graph and processed further through the introduction of either fuzzy predicates or syntactic pattern recognition techniques.

The problem of piecewise polynomial L2 approximation with variable boundaries is considered. Necdssary and sufficient conditions for local optima are derived. These suggest simple functional iteration, algorithms for locating the boundaries.

The outlines of handwritten numerals are approximated by polygons using a method previously developed by Pavlidis and Horowitz [10]. This enables a simple evaluation of many intuitively descriptive features for numerals, for example, relative position and type of concave arcs. The method was tested on the Munson data (IEEE Data Base 1.2.2), and an overall error rate of 9.4 percent was achieved without any statistical optimization. A characteristic property of this approach is the existence of two steps: the first step (primitive feature generation) is primarily numerical, and the second step (feature selection and classification) makes extensive use of semantics.

This book covers most of the major topics in pattern recognition at a level appropriate to a new student of the field. Therefore it can be very useful as a textbook either for an introductory graduate, or an advanced undergraduate course. The authors have deliberately played down the mathematical formalism (no long or rigorous proofs) and assumed only that background which students in such courses are expected to have. They supply numerous problems and quite a few illustrative and instructive examples. One attractive feature is the critical evaluation of many of the techniques discussed which their own experience enables them to do. I enjoyed reading statements like the one on p. 179 about the literature on linear discriminant functions. Finally each chapter is followed by extensive historical and bibliographical remarks.

Piecewise approximation is described as a way of feature extraction, data compaction, and noise filtering of boundaries of regions of pictures and waveforms. A new fast algorithm is proposed which allows for a variable number of segments. After an arbitrary initial choice, segments are split or merged in order to drive the error norm under a prespecified bound. Results of computer experiments with cell outlines and electrocardiograms are reported.

Waveform segmentation is treated as a problem of piecewise linear uniform (minmax) approximation. Various algorithms are reviewed and a new one is proposed based on discrete optimization. Examples of its applications are shown on terrain profiles, scanning electron microscope data, and electrocardiograms. The processing is sufficiently fast to allow its use on-line. The results of the segmentation can be used for pattern recognition, data compression, and nonlinear filtering not only for waveforms but also for pictures and maps. In the latter case some additional preprocessing is required and it is described in [19].

Topological characterizations of sets of graphs which can be generated by contextfree or linear grammars are given.It is shown, for example, that the set of all planar graphs cannot be generated by a context-free grammar while the set of all outerplanar graphs can

This note describes the determination of waveform segments which contain the information necessary for classification. The method is successful in discriminating between the vibration record of internal combustion engines before and after repair.

This paper deals with the classification of signals in terms of their autocorrelation functions. For each of two classes the eigenfunctions of the autocorrelation function are found, and a proper subset of each one is chosen. An unknown signal is classified by comparing the norms of its projections on the two subsets of eigenfunctions. By working with the eigenfunctions corresponding to the smallest eigenvalues, the method approximates singular detection. An application of this technique is shown for the classification of engine-vibration records as a basis for automatic mechanical fault diagnosis.

An attempt is made to define meaningful counterparts of topological notions in quantized spaces.Finitely presented Abelian groups are used as a model for such spaces.Then the notion of dimension is introduced through a recursive definition and it is proven that for free Abelian groups it equals the number of generators.

A notion of equivalence (c-equivalence) is defined as the counterpart of homeoinorphism for quantized spaces.It is shown that sets with the same number of components and holes are c-equivalent in two-dimensional spaces.Then it is shown that for each arbitrary set there is a set c-equivalent to it with certain "regular" features (rectangular perimeter, holes with diameter one, etc.).