Bidirectional deformable matching with application to handwritten character extraction

To achieve integrated segmentation and recognition in complex scenes, the model-based approach has widely been accepted as a promising paradigm. However, the performance is still far from satisfactory when the target object is highly deformed and the level of outlier contamination is high. In this paper, we first describe two Bayesian frameworks, one for classifying input patterns and another for detecting target patterns in complex scenes using deformable models. Then, we show that the two frameworks are similar to the forward-reverse setting of Hausdorff matching and that their matching and discriminating properties are complementary to each other. By properly combining the two frameworks, we propose a new matching scheme called bidirectional matching. This combined approach inherits the advantages of the two Bayesian frameworks. In particular, we have obtained encouraging empirical results on shape-based pattern extraction, using a subset of the CEDAR handwriting database containing handwritten words of highly varying shape.     

Shape matching using relaxation techniques

The problem of finding approximate matches of pieces of shapes to parts of larger shapes is investigated. The shapes are represented by polygonal approximations. Initially, figures of merit are assigned to the matches between pairs of angles on the two shapes. Relaxation methods are then used to find acceptable combinations of these matches. This approach was tested on a data base consisting of digitized coastlines in various map projections. In nearly all cases, all matches except the correct one were eliminated by the relaxation processes.     

Term rewriting and its application to recognizing handwritten Hindu numerals

In this paper the theoretical basis is presented and the implementation of a term rewriting system based on algebraic specifications is described. The input to this system is represented by an algebraic specification language, which forms not only the set of axioms but also the sorts, variables, operators and terms of a specific simulated theory or application. Rewriting and matching mechanisms provide the formal methodology for evaluating terms and proving assertions in an algebraic theory. Specifications are evaluated by interpreting terms by means of rewrite rules. The rules are described by the axioms of the specifications where the finite termination and congruence properties are assumed. A term rewriting system to recognize handwritten Hindu numerals is introduced as a case study. Besides rewriting, a robust algorithm is proposed to segment the numeral's image into strokes based on feature points and to identify cavity features. A syntactic representation (term) of the input image is matched and rewritten against a set of rules. Experimental results proved that the proposed system is tolerant to recognize a variety of numeral shapes with 96% successful recognition rate.     

Shape matching and modeling using skeletal context

Shape is a significant visual clue for human perception and shape models show considerable promise as a basis for extracting objects from images. This paper proposes a novel approach for shape matching and modeling using the symmetry characterization of shape interior and the spatial relationships of shape structures. Based on the representative skeletal features, we develop a mechanism to generate a coarse segment matching between different instances of an object. Additionally, the natural correspondence of skeletal branches to sequential segments along the shape curves is employed in the matching process to avoid false correspondences across different segments. Point matches within the corresponding segments are then obtained by solving a constrained assignment problem. The validation of the proposed approach is illustrated on various data sets in the presence of considerable deformation and occlusion and the results are compared with those of popular approaches. We also demonstrate the performance of our method on biological objects for shape modeling, showing better models than those obtained by the state-of-the-art shape modeling approaches.     

Off-line general handwritten word recognition using an approximateBEAM matching algorithm

A recognition system for general isolated off-line handwritten words using an approximate segment-string matching algorithm is described. The fundamental paradigm employed is a character-based segment-then-recognize/match strategy. An additional user supplied contextual information in the form of a lexicon guides a graph search to estimate the most likely word image identity. This system is designed to operate robustly in the presence of document noise, poor handwriting, and lexicon errors. A pre-processing step is initially applied to the image to remove noise artifacts and normalize the handwriting. An oversegmentation approach is used to improve the likelihood of capturing the individual characters embedded in the word. A directed graph is constructed that contains many possible interpretations of the word image, many implausible. The most likely graph path and associated confidence is computed for each lexicon word to produce a final lexicon ranking. Experiments highlighting the characteristics of this algorithm are given     

Statistical character structure modeling and its application to handwritten Chinese character recognition

This paper proposes a statistical character structure modeling method. It represents each stroke by the distribution of the feature points. The character structure is represented by the joint distribution of the component strokes. In the proposed model, the stroke relationship is effectively reflected by the statistical dependency. It can represent all kinds of stroke relationship effectively in a systematic way. Based on the character representation, a stroke neighbor selection method is also proposed. It measures the importance of a stroke relationship by the mutual information among the strokes. With such a measure, the important neighbor relationships are selected by the nth order probability approximation method. The neighbor selection algorithm reduces the complexity significantly because we can reflect only some important relationships instead of all existing relationships. The proposed character modeling method was applied to a handwritten Chinese character recognition system. Applying a model-driven stroke extraction algorithm that cooperates with a selective matching algorithm, the proposed system is better than conventional structural recognition systems in analyzing degraded images. The effectiveness of the proposed methods was visualized by the experiments. The proposed method successfully detected and reflected the stroke relationships that seemed intuitively important. The overall recognition rate was 98.45 percent, which confirms the effectiveness of the proposed methods.     

Absence importance and its application to feature detection and matching

Feature detection and matching play important roles in many fields of computer vision, such as image understanding, feature recognition, 3D-reconstruction, video analysis, etc. Extracting features is usually the first step for feature detection or matching, and the gradient feature is one of the most used selections. In this paper, a new image feature-absence importance (AI) feature, which can directly characterize the local structure information, is proposed. Greatly different from the most existing features, the proposed absence importance feature is mainly based on the consideration that the absence of the important pixel will have a great effect on the local structure. Two absence importance features, mean absence importance (MAI) and standard deviation absence importance (SDAI), are defined and used subsequently to construct new algorithms for feature detection and matching. Experiments demonstrate that the proposed absence importance features can be used as an important complement of the gradient feature and applied successfully to the fields of feature detection and matching.     

Class-specific feature polynomial classifier for pattern classification and its application to handwritten numeral recognition

The polynomial classifier (PC) that takes the binomial terms of reduced subspace features as inputs has shown superior performance to multilayer neural networks in pattern classification. In this paper, we propose a class-specific feature polynomial classifier (CFPC) that extracts class-specific features from class-specific subspaces, unlike the ordinary PC that uses a class-independent subspace. The CFPC can be viewed as a hybrid of ordinary PC and projection distance method. The class-specific features better separate one class from the others, and the incorporation of class-specific projection distance further improves the separability. The connecting weights of CFPC are efficiently learned class-by-class to minimize the mean square error on training samples. To justify the promise of CFPC, we have conducted experiments of handwritten digit recognition and numeral string recognition on the NIST Special Database 19 (SD19). The digit recognition task was also benchmarked on two standard databases USPS and MNIST. The results show that the performance of CFPC is superior to that of ordinary PC, and is competitive with support vector classifiers (SVCs).     

一种新的李群分类器在手写体数字中的应用

李群是变换空间的一种基本表示理论。目前针对李群数据所设计的分类器较少,对多分类的效果也不是很好。以手写体数字的应用为背景,引入了支持向量机分类算法来处理李群数据。由于李群数据具有矩阵表现的形式,设计了一种矩阵高斯核函数,使得支持向量机能够处理矩阵数据。仿真结果表明,支持向量机方法在李群数据上具有很好的性能。     

Recognition of handwritten Chinese characters by elastic matching

A method was proposed to match handwritten Chinese character patterns. Two given patterns are iteratively deformed until they match. An energy function and a neighborhood of influence is defined for each iteration. Initially a large neighborhood is used such that the movements result in large features being coarsely aligned. The neighborhood size is gradually reduced in successive iterations so that finer and finer details are aligned. The amount of computation increases with the square of the number of moving parts which is quite favorable compared with other algorithms. Extensive testing was carried out to evaluate the performance of the algorithm under various parameter settings. The method was applied to the recognition of handwritten Chinese characters with satisfactory results.     

Model-based stroke extraction and matching for handwritten Chinese character recognition

This paper proposes a model-based structural matching method for handwritten Chinese character recognition (HCCR). This method is able to obtain reliable stroke correspondence and enable structural interpretation. In the model base, the reference character of each category is described in an attributed relational graph (ARG). The input character is described with feature points and line segments. The strokes and inter-stroke relations of input character are not determined until being matched with a reference character. The structural matching is accomplished in two stages: candidate stroke extraction and consistent matching. All candidate input strokes to match the reference strokes are extracted by line following and then the consistent matching is achieved by heuristic search. Some structural post-processing operations are applied to improve the stroke correspondence. Recognition experiments were implemented on an image database collected in KAIST, and promising results have been achieved.     

A confidence value estimation method for handwritten Kanji character recognition and its application to candidate reduction

This paper describes a method for estimating a confidence value (CV) by which we can express the potential correctness of handwritten Kanji character recognition candidates. An accumulated confidence value (ACV), calculated as the sum of CVs, is also applied to reduce the number of candidates. Such reduction is vital to increasing the speed of such applications as Kanji address recognition, and it also reduces the probability of misreadings in linguistic postprocessing. Sorted sets of character candidates, ranked in increasing order of each candidates distance value, are used as feature vectors. A CV is defined as the a posteriori probability with respect to each rank. To obtain good quality approximations of probability density functions (PDFs), we introduce a subspace within which correct data can easily be separated from erroneous data and then estimate PDF parameters over this subspace. Next, we use an ACV as a measure for expressing a threshold for candidate acceptance in Kanji character recognition. The efficiency of the proposed method is evaluated in an experiment using IPTP CD-ROM2 Japanese address images, and a comparison with the results for a conventional method shows that a roughly 35% reduction in the number of candidates is obtained without reducing the number of correct candidates.Received: 29 October 2001, Accepted: 30 September 2003, Published online: 1 April 2004Correspondence to: Eiki Ishidera     

改进主曲线及在手写体数字骨架化中应用研究

针对主曲线算法初始化步骤效果差,导致后面所得结果不能正确反映数据的拓扑结构,对其进行改进,用连通k近邻代替第一主成分线找到数据的初始拓扑结构。将改进后的算法应用于脱机手写体数字骨架化,实验证明改进的算法克服了上面提到的缺点,能更好的找到数据的拓扑结构,在时间复杂度、连通性、参数等各方面都优于其他改进算法。改进算法适于具有“连通性”的数据。     

Shape matching of two-dimensional objects

In this paper we present results in the areas of shape matching of nonoccluded and occluded two-dimensional objects. Shape matching is viewed as a ``segment matching' problem. Unlike the previous work, the technique is based on a stochastic labeling procedure which explicitly maximizes a criterion function based on the ambiguity and inconsistency of classification. To reduce the computation time, the technique is hierarchical and uses results obtained at low levels to speed up and improve the accuracy of results at higher levels. This basic technique has been extended to the situation where various objects partially occlude each other to form an apparent object and our interest is to find all the objects participating in the occlusion. In such a case several hierarchical processes are executed in parallel for every object participating in the occlusion and are coordinated in such a way that the same segment of the apparent object is not matched to the segments of different actual objects. These techniques have been applied to two-dimensional simple closed curves represented by polygons and the power of the techniques is demonstrated by the examples taken from synthetic, aerial, industrial and biological images where the matching is done after using the actual segmentation methods.