In many real world applications, the cost of a wrong decision may be much higher than the benefit of having a high classification rate. This kind of classification problems represent very challenging tasks, because they require highly reliable systems and may benefit of introducing a reject option. To this purpose, many classification systems have been proposed, among which classifier ensembles represent a successful example. This approach aims at combining classifiers making uncorrelated errors. In this framework, the Random Forest (RF) represents a case of special interest. A RF is made of a suitable ensemble of decision trees and has proved to be very effective in several fields. In this paper, the RF classification reliability is experimentally analyzed with reference to the case of handwriting recognition. The aim is to verify if such reliability can be effectively used to introduce a new reject option, which considers, for each unknown sample, a subset of few classes including with high probability the correct one. The whole system operates as a pre-classification stage and the reject option should allow us to obtain a low error rate without significantly affecting the recognition rate. Experiments, carried out on two real world datasets, have shown the effectiveness of the proposed method.

We propose a feature selection--based approach for improving classification performance of a two stage classification system in contexts where a high number of features is involved. A problem with a set of $N$ classes is subdivided into a set of $N$ two class problems. In each problem, a GA--based feature selection algorithm is used for finding the best subset of features. These subsets are then used for training $N$ classifiers. In the classification phase, unknown samples are given in input to each of the trained classifiers by using the corresponding subspace. In case of conflicting responses, the sample is sent to a suitably trained supplementary classifier. The proposed approach has been tested on a real world dataset containing hyper--spectral image data. The results favourably compare with those obtained by other methods on the same data.

We present a method to recover the dynamic writing order from static images of handwriting. The static handwriting is initially represented by its skeleton, which is then converted into a graph, whose arcs correspond to the skeleton branches, and nodes to either end point or branch point of the skeleton. Criteria derived by handwriting generation are then applied to transform the graph in such a way that all its nodes, but the first and the last, have an even degree, so that it can be traversed from the first to the last by using the Fleury's algorithm. The experimental results show that combining criteria derived from handwriting generation models with graph traversal leads to reconstruct the original sequence produced by a writer even in case of complex handwriting, i.e handwriting with retracing, crossings and pen-up's.

A large amount of handwritten documents exist in image form, as scanned documents. The supporting electronic media allows for better preservation, but to access their content they must be processed by some kind of recognition technologies that convert the image to searchable text. In case of cursively written documents, even the best available technology introduces recognition errors that may drive down the performance of a document retrieval system. We propose a recognition-free approach which embodies two main components: a shape matching algorithm, working on the ink, and a string matching algorithm working on the ink interpretation of a reference set. Experiments on a data set of 16,500 cursive words produced by hundreds of writers show promising results and suggest that the proposed method can be a viable tool to build inexpensive retrieval system for cursive documents.

We present a Genetic Algorithm based feature selection approach according to which feature subsets are represented by individuals of an evolving population. Evolution is controlled by a fitness function taking into account statistical properties of the input data in the subspace represented by each individual, and aims to select the smallest feature subset that optimizes class separability. The originality of our method lies particularly in the definition of the evaluation function. The proposed approach has been tested on a standard database of handwritten digits, showing to be effective both for reducing the number of features used and for improving classifier performance.

A new prototyping method based on the evolutionary computation paradigm and on the concept of Vector Quantization is proposed. It uses a specifically devised evolutionary algorithm for evolving a set of prototype feature vectors and does not require any a priori knowledge about either the actual number of prototypes or the statistical properties of the input data. Experiments performed by using both synthetic data and handwritten digits randomly extracted from the NIST database have confirmed the effectiveness of the approach.

In this paper we propose a method based on a graph-theoretical cluster analysis for automatically finding cluster of micro-calcifications in mammographic images. It is applied to the image after a micro-calcification detection phase and is able to cope with the unavoidable false positives that each automatic detection algorithm produces. The proposed approach has been tested on a standard database of 40 mammographic images and revealed to be very effective even when the detection phase gives rise to several false positives.

We propose a genetic programming based approach for generating prototypes in a classification problem. In this context, the set of prototypes to which the samples of a data set can be traced back is coded by a multitree, i.e. a set of trees, which represents the chromosome. Differently from other approaches, our chromosomes are of variable length. This allows coping with those classification problems in which one or more classes consist of subclasses. The devised approach has been tested on several problems and the results compared with those obtained by a different genetic programming based approach recently proposed in the literature.

We present an algorithm for graph isomorphism and subgraph isomorphism suited for dealing with large graphs. A first version of the algorithm has been presented in a previous paper, where we examined its performance for the isomorphism of small and medium size graphs. The algorithm is improved here to reduce its spatial complexity and to achieve a better performance on large graphs; its features are analyzed in detail with special reference to time and memory requirements. The results of a testing performed on a publicly available database of synthetically generated graphs and on graphs relative to a real application dealing with technical drawings are presented, confirming the effectiveness of the approach, especially when working with large graphs.

The performance of an attributed relational graph (ARG) matching algorithm, tailored for dealing with large graphs, is evaluated in the context of a real application. The detection of component parts in CAD images of mechanical drawings. The matching problem is a graph-subgraph isomorphism and the algorithm exploits semantic information about nodes while does not require information about the topology of the graphs to be matched. Experimental results, compared with those obtained with a different method, show the overall efficiency of the algorithm and the matching time reduction obtainable by exploiting the semantic information held by ARGs.

At present, mammography is the only non-invasive diagnostic technique of breast cancer at a very early stage. A visual clue of such disease particularly significant is the presence of clusters of microcalcifications. Reliable methods for an automatic recognition of malignant clusters are very difficult to accomplish because of the small size of the microcalcifications and the poor quality of the mammographic images. In this paper we propose a novel approach for automating the recognition of malignant clusters, based on the adoption of a multiple expert system. The approach has been successfully tested on a standard database of 40 mammographic images.

A three-stage serial multi-expert system for facing the problem of signature verification is proposed. The first two stages, respectively devoted to the recognition of random and simple forgeries and of skilled forgeries, employ suitable criteria for estimating the reliability of the performed classification. In case of uncertainty the signature is forwarded to the successive stage which takes the final decision, taking into account the decisions of the previous stages together with their reliability estimations. Criteria for selecting the features to be used at each stage and for computing classification reliability and reliability thresholds are discussed The obtained results are compared with those achieved, on the same database of 49 writers, by other existing systems.

A graph matching algorithm is illustrated and its performance compared with that of a well known algorithm performing the same task. According to the proposed algorithm the matching process is carried out by using a state space representation: a state represents a partial solution of the matching between two graphs, and a transition between states corresponds to the addition of a new pair of matched nodes. A set of feasibility rules is introduced for pruning states corresponding to partial matching solutions not satisfying the required graph morphism. Results outlining the computational cost reduction achieved by the method are given with reference to a set of randomly generated graphs.

The paper illustrates an algorithm for the inexact matching of attributed relational graphs. A sample graph is considered matchable with one of the prototypes if, by using a defined set of syntactic and semantic transformations, it can be made isomorphic to the graph of the prototype. The applicability of a transformation is contextually defined, i.e. each transformation can be defined with reference to a prototype, and can be applied only when the sample graph is being matched with that prototype. The reduction of the computational complexity with respect to a brute-force approach is given with reference to an OCR application.

Criteria for evaluating the classification reliability of a neural classifier and for accordingly making a reject option are proposed. Such an option, implemented by means of two rules which can be applied independently of topology, size, and training algorithms of the neural classifier, allows one to improve the classification reliability. It is assumed that a performance function P is defined which, taking into account the requirements of the particular application, evaluates the quality of the classification in terms of recognition, misclassification, and reject rates. Under this assumption the optimal reject threshold value, determining the best trade-off between reject rate and misclassification rate, is the one for which the function P reaches its absolute maximum. No constraints are imposed on the form of P, but the ones necessary in order that P actually measures the quality of the classification process. The reject threshold is evaluated on the basis of some statistical distributions characterizing the behavior of the classifier when operating without reject option; these distributions are computed once the training phase of the net has been completed. The method has been tested with a neural classifier devised for handprinted and multifont printed characters, by using a database of about 300000 samples. Experimental results are discussed.

In this paper, we present a system for singling out character strings from line drawings. Characters, candidate according to a preliminary selection, are replaced with rectangles preserving information about character size, position and orientation. Rectangles are clustered on the basis of a set of criteria. Each cluster is seen as a graph whose nodes represent rectangles, while arcs represent their possible connections, established on the basis of properly defined visibility criteria. Strings within clusters are searched, in a proper state space, according to a hierarchy derived from the knowledge of the problem, injected by means of models representing the most common configurations of strings in terms of their topological and geometrical properties. The system is implemented in an object-oriented fashion. Experimental results on a large set of documents of different types are reported.

A system for the automatic placement of names on cadastral maps, using a method which, because of its generality, can be easily applied to other types of maps is presented. The method is based on a robust algorithm that, after having detected character strings on the original paper map, encases them with rectangles, and searches for the most convenient location where to place such rectangles on the computer version of the map. The system is part of an operative package working to feed the GIS of the Italian Land Register by means of the automatic interpretation of cadastral maps. Results obtained on a sample set of more than 100 maps are reported.>

A neural classifier for isolated omnifont characters is discussed. A method for characterizing a given training set of characters, based on the definition of some statistical parameters is introduced; on the basis of such characterization an architecture is defined made of a set of neural networks properly connected. Depending on the value of the parameters characterizing the training set, both sizing and training of each network are separately carried out according to a suitable methodology. It is shown that higher recognition rates can be achieved than those obtained by using a single neural network as classifier.>

The problem of computing area and perimeter of a digital figure presented by its discrete medial axis transform (MAT) is addressed. The figure is seen as the union of the square-shaped maximal neighborhoods centered on the local maxima of the MAT. The contribution given by each maximal neighborhood to figure area and perimeter is computed while tracing the MAT. Multiple overlaps among the maximal neighborhoods are possible. However, due to the properties of the local maxima and their associated maximal neighborhoods a single tracing of the MAT is provided to be sufficient to obtain the desired result. Thus, the procedure requires O(N) time, where N is the number of MAT pixels.>

An analytical model describing the performance of a mesh-connected array of state-of-the-art VLSI microprocessors embedded in a CSP-like environment, is presented. The mode has been developed in the framework of a study aimed at the design and evaluation of a reconfigurable architecture especially suitable for the execution of both low and high level vision tasks. The validity of the model is demonstrated and its use illustrated.>

In picture processing it is often convenient to deal with a stick-like version (skeleton) of binary digital images. Although skeleton connectedness is not necessary for storage and retrieval purposes, this property is desirable when a structural description of images is of interest. In this paper a parallel procedure is described which, applied to a connected image, originates a connected skeleton made by the union of simple digital arcs. The procedure involves a step by step propagation of the background over the image. At every step, contour elements either belonging to the significant convex regions of the current image or being local maxima of the original image are selected as skeleton elements. Since the final set so obtained is not ensured to be connected, the configurations in correspondence of which disconnections appear are investigated and the procedures to avoid this shortcoming are given. The presence of the whole set of local maxima among the skeleton elements ensures the possibility of recovering the original image by means of a reverse distance transform. The details of the program implementing the proposed algorithm on a parallel processor are finally included.

Picture processing includes a variety of algorithms employed at different stages within a recognition process. Although single parallel algorithms have been suggested, no systematic comparison with sequential algorithms is available. We propose here some parallel algorithms solving a selected set of picture-processing tasks and compare their speed, when implemented on a CLIP machine, with that of the equivalent sequential algorithms implemented on a standard minicomputer. It is shown that parallel algorithms are faster than the sequential ones by a factor depending on the size of the digitization matrix, even when arithmetical operations are widely involved.

This paper reports some results on the use of parallel-structured computers to detect and describe concavities in simply connected planar regions (``domains'' or ``blobs''). We show, in particular, how these concavities may be obtained by a parallel filling-in process-somewhat like pouring liquid into several cups simultaneously. It has been shown that the concavities and concavity tree of a regular cellular blob (i.e., a digitized simply connected planar region) can be obtained by the use of a sequential algorithm that finds the minimum-perimeter polygon (MPP) passing through the boundary cells of the cellular blob. In this paper we show how any such MPP may be computed by a sequence of simultaneous local operations in a parallel-structured computer. We also show that the ratio of computation times for sequential algorithms to those for parallel algorithms operating on the cellular image of a large circular blob is approximately proportional to the square root of the blob's perimeter, assuming the size of the vertex-detecting window is fixed and large enough to detect one or more vertices of the MPP. We also show that filling in the concavities by a sequence of parallel local operations terminates to an approximation of the cellular hull (i.e., the digitization of the convex hull of the original blob) in a finite time, and that this approximation is a subset of the cellular hull.