Fast SVM training algorithm with decomposition on very large data sets.

Training a support vector machine on a data set of huge size with thousands of classes is a challenging problem. This paper proposes an efficient algorithm to solve this problem. The key idea is to introduce a parallel optimization step to quickly remove most of the nonsupport vectors, where block diagonal matrices are used to approximate the original kernel matrix so that the original problem can be split into hundreds of subproblems which can be solved more efficiently. In addition, some effective strategies such as kernel caching and efficient computation of kernel matrix are integrated to speed up the training process. Our analysis of the proposed algorithm shows that its time complexity grows linearly with the number of classes and size of the data set. In the experiments, many appealing properties of the proposed algorithm have been investigated and the results show that the proposed algorithm has a much better scaling capability than Libsvm, SVMlight, and SVMTorch. Moreover, the good generalization performances on several large databases have also been achieved.

A width-invariant property of curves based on wavelet transform with a novel wavelet function.

This paper is an improvement on the characterization of edges. Using a novel wavelet function, it is proven that the maximum moduli of the wavelet transform (MMWT) of a curve produces two new symmetrical curves on both sides of the original with the same direction. The distance between the two curves is shown to be independent of the width d of the original curve if the scale s of the wavelet transform satisfies s/spl ges/d. This property provides a novel method of obtaining the skeletons of the curves in an image.

Stroke-model-based character extraction from gray-level document images.

Global gray-level thresholding techniques such as Otsu's method, and local gray-level thresholding techniques such as edge-based segmentation or the adaptive thresholding method are powerful in extracting character objects from simple or slowly varying backgrounds. However, they are found to be insufficient when the backgrounds include sharply varying contours or fonts in different sizes. A stroke-model is proposed to depict the local features of character objects as double-edges in a predefined size. This model enables us to detect thin connected components selectively, while ignoring relatively large backgrounds that appear complex. Meanwhile, since the stroke width restriction is fully factored in, the proposed technique can be used to extract characters in predefined font sizes. To process large volumes of documents efficiently, a hybrid method is proposed for character extraction from various backgrounds. Using the measurement of class separability to differentiate images with simple backgrounds from those with complex backgrounds, the hybrid method can process documents with different backgrounds by applying the appropriate methods. Experiments on extracting handwriting from a check image, as well as machine-printed characters from scene images demonstrate the effectiveness of the proposed model.

Keratomycosis with an unusual clinical manifestation--a case report.

We report a case of keratomycosis which had recurrent, deep stromal infiltration and an endothelial plaque for half a year after the original corneal foreign body injury. The subject had an unusual clinical picture of deep corneal infiltration and later hair-like material growing from the endothelial plaque into the anterior chamber. Repeated corneal scrapings for smears and cultures all showed negative during the initial treatment. We tried anterior chamber paracentesis and endothelial aspiration and got a positive finding of Cladosporium infection. This case is presented because of the difficulty of diagnosis and management of fungal keratomycosis.

Matching of complex patterns by energy minimization.

Two patterns are matched by putting one on top of the other and iteratively moving their individual parts until most of their corresponding parts are aligned. An energy function and a neighborhood of influence are defined for each iteration. Initially, a large neighborhood is used such that the movements result in global features being coarsely aligned. The neighborhood size is gradually reduced in successive iterations so that finer and finer details are aligned. Encouraging results have been obtained when applied to match complex Chinese characters. It has been observed that computation increases with the square of the number of moving parts which is quite favorable compared with other algorithms. The method was applied to the recognition of handwritten Chinese characters. After performing the iterative matching, a set of similarity measures are used to measure the similarity in topological features between the input and template characters. An overall recognition rate of 96.1% is achieved.

A recursive thresholding technique for image segmentation.

In this correspondence, we present a general recursive approach for image segmentation by extending Otsu's (1978) method. The new approach has been implemented in the scope of document images, specifically real-life bank checks. This approach segments the brightest homogeneous object from a given image at each recursion, leaving only the darkest homogeneous object after the last recursion. The major steps of the new technique and the experimental results that illustrate the importance and the usefulness of the new approach for the specified class of document images of bank checks will be presented.

New algorithms for fixed and elastic geometric transformation models.

This paper describes a new approach that leads to the discovery of substitutions or approximations for physical transformation by fixed and elastic geometric transformation models. These substitutions and approximations can simplify the solution of normalization and generation of shapes in signal processing, image processing, computer vision, computer graphics, and pattern recognition. In this paper, several new algorithms for fixed geometric transformation models such as bilinear, quadratic, bi-quadratic, cubic, and bi-cubic are presented based on the finite element theory. To tackle more general and more complicated problems, elastic geometric transformation models including Coons, harmonic, and general elastic models are discussed. Several useful algorithms are also presented in this paper. The performance of the proposed approach has been evaluated by a series of experiments with interesting results.

Large tree classifier with heuristic search and global training.

In the tree classifier with top-down search, a global decision is made via a series of local decisions. Although this approach gains in classification efficiency, it also gives rise to error accumulation which can be very harmful when the number of classes is very large. To overcome this difficulty, a new tree classifier with the following characteristics is proposed: 1) fuzzy logic search is used to find all ``possible correct classes,'' and some similarity measures are used to determine the ``most probable class''; 2) global training is applied to generate extended terminals in order to enhance the recognition rate; 3) both the training and search algorithms have been given a lot of flexibility, to provide tradeoffs between error and rejection rates, and between the recognition rate and speed. A computer simulation of the decision trees for the recognition of 3200 Chinese character categories yielded a very high recognition rate of 99.93 percent and a very high speed of 861 samples/s, when the program was written in a high level language and run on a large multiuser time-sharing computer.

Analysis and design of a decision tree based on entropy reduction and its application to large character set recognition.

Based on a recursive process of reducing the entropy, the general decision tree classifier with overlap has been analyzed. Several theorems have been proposed and proved. When the number of pattern classes is very large, the theorems can reveal both the advantages of a tree classifier and the main difficulties in its implementation. Suppose H is Shannon's entropy measure of the given problem. The theoretical results indicate that the tree searching time can be minimized to the order O(H), but the error rate is also in the same order O(H) due to error accumulation. However, the memory requirement is in the order 0(H exp(H)) which poses serious problems in the implementation of a tree classifier for a large number of classes. To solve these problems, several theorems related to the bounds on the search time, error rate, memory requirement and overlap factor in the design of a decision tree have been proposed and some principles have been established to analyze the behaviors of the decision tree. When applied to classify sets of 64, 450, and 3200 Chinese characters, respectively, the experimental results support the theoretical predictions. For 3200 classes, a very high recognition rate of 99.88 percent was achieved at a high speed of 873 samples/s when the experiment was conducted on a Cyber 172 computer using a high-level language.

Application of a multilayer decision tree in computer recognition of chinese characters.

A multistage classifier with general tree structure has been developed to recognize a large number of Chinese characters. A simple and efficient method of classifying the characters was achieved by choosing the best feature at each stage of the tree. The features used are Walsh coefficients obtained from two profiles of a character projected onto the X-Y orthogonal axes. Some algorithms for aligning the characters were compared and one of them was adopted in this recognition scheme. A high recognition rate of about 99.5 percent was obtained in an experiment with more than 3000 different Chinese characters.

A method for selecting constrained hand-printed character shapes for machine recognition.

Since handwritten characters vary in shape and writing-stroke sequence, it is desirable to develop a standard set of characters that are of high quality, so that not only are they easy to write, but they are also most suitable for machine recognition. A database of more than 100 000 alphanumeric patterns was assembled. It consisted of 174 models of the alphanumeric characters written by both left-handed and right-handed subjects. Based on frequency density and distance measurements, a nietric called the dispersion factor was computed to rank the various models. The principle of the metric is discussed, and results are given indicating the high quality models of the alphanumerics.

n-Gram Statistics for Natural Language Understanding and Text Processing.

n-gram (n = 1 to 5) statistics and other properties of the English language were derived for applications in natural language understanding and text processing. They were computed from a well-known corpus composed of 1 million word samples. Similar properties were also derived from the most frequent 1000 words of three other corpuses. The positional distributions of n-grams obtained in the present study are discussed. Statistical studies on word length and trends of n-gram frequencies versus vocabulary are presented. In addition to a survey of n-gram statistics found in the literature, a collection of n-gram statistics obtained by other researchers is reviewed and compared.