Modeling segmentation cuts using support vector machines

Eduardo Vellasques, Luiz S. Oliveira, Alceu S. Britto, Alessandro L. Koerich, Robert Sabourin2006

TL;DR

This paper introduces a novel filtering method using Support Vector Machines (SVMs) to identify and discard unnecessary segmentation cuts in handwritten touching digits. By modeling over-segmented digits based on concavity analysis, the approach significantly reduces computational cost and improves recognition accuracy for downstream classifiers.

What Problem Does This Paper Address?

Recognizing handwritten numerical strings is a complex task, particularly when digits touch and merge into a single connected component. Traditional segmentation-based systems often rely on over-segmentation, generating numerous potential segmentation points (hypotheses) that a subsequent classifier must evaluate. This leads to a combinatorial explosion of possibilities, increasing computational burden and potentially reducing recognition accuracy. The challenge lies in efficiently and accurately distinguishing between correct segmentation points and those that arise from over-segmentation, without resorting to computationally expensive full classification of every hypothesis.

Methods

The core of this paper's contribution is a two-stage approach:

  1. Over-segmentation Modeling (MCA): The authors propose using Multilevel Concavity Analysis (MCA) to model what an over-segmented digit looks like. MCA analyzes the "concavity level" of pixels within a segment and compares it to the original digit's concavity. Differences in these levels are used to create a feature vector. Specifically, they extract 7 features related to background pixels surrounded by different numbers of black pixels, changes in concavity, and foreground pixels within the MCA region. These features are then concatenated into a 42-dimensional vector for each segment.
  2. SVM-based Filtering: A Support Vector Machine (SVM) is trained to classify segmentation cuts. The SVM learns to distinguish between "necessary" cuts (those that correctly segment digits) and "unnecessary" cuts (those that result from over-segmentation). The SVM is chosen for its tolerance to outliers and effectiveness in high-dimensional data. The paper also explores using a Multi-Layer Perceptron (MLP) for comparison.

Datasets

  • Synthetic Touching Digit Database: A large synthetic database of touching digits was used, containing 273,452 pairs generated by connecting 2,000 isolated digits from the NIST SD19 database. This database is notable for its synthetic nature, allowing for optimal ground-truth segmentation points. It was split into several subsets (base_0 to base_4).
  • NIST SD19 Database (hsf_0 series): A subset of 20,000 isolated digits from this database was used to train the over-segmented digit model.

Key Insights and Ideas

  • Modeling Over-segmentation is Easier: The authors argue that modeling what an over-segmented digit looks like is more straightforward than directly modeling "unnecessary cuts." This shift in perspective simplifies the problem.
  • Concavity as a Discriminator: The difference in concavity before and after segmentation proves to be a powerful feature for identifying over-segmented regions.
  • SVM as an Efficient Filter: SVMs are shown to be effective in quickly filtering out a significant portion of unnecessary segmentation hypotheses, thereby reducing the workload for the main recognition classifier.
  • Trade-off between Filters and Rejection: The study highlights a trade-off between the filtering capabilities of SVM and MLP, with SVM performing better at lower error rates and MLP at lower rejection rates, but both offering improvements.

Key Results

  • Elimination of Unnecessary Cuts: The proposed SVM filter successfully eliminated 67.9% of unnecessary segmentation cuts generated by the Fenrich [10] segmentation algorithm.
  • Improved Recognition Rate: The filtering approach led to a significant increase in the recognition rate for the general-purpose classifier.
  • High Accuracy on Optimal Cuts: When tested on optimal segmentation cuts (ground truth), the method achieved high success rates: 98.9% with SVM and 99.4% with MLP.
  • MLP Performance: In the MLP case, 59.2% of unnecessary cuts were discarded, also leading to an improved recognition rate.

Limitations and Future Work

  • Current Focus on Two-Digit Strings: The experiments were primarily conducted on two-digit, single-touching strings.
  • Future Work: The authors plan to extend the method to strings of different lengths and with multiple touches. They also aim to explore feature selection to optimize the feature set and evaluate the method with other recognition-based segmentation algorithms. Investigating the use of structural features in a less constrained manner is also a future direction.

Summary updated

Abstract

In this paper we propose a method to evaluate segmentation cuts for handwritten touching digits. The idea of this method is to work as a filter in segmentation-based recognition systems. These types of systems usually rely on over-segmentation methods, where several segmentation hypotheses are created for each touching group of digits and then assessed by a general-purpose classifier. Through the use of the proposed method, unnecessary segmentation cuts can be identified without any attempt of classification by a general-purpose classifier, reducing the number of paths in a segmentation graph, what can consequently lead to a reduction in computational cost. Concavity analysis is performed in each digit before and after segmentation. The difference of those concavities is used to model the segmentation cuts. SVM is used to classify those segmentation cuts. The preliminary results obtained are very promising as for the segmentation algorithm tested, 67.9 % of the unnecessary segmentation cuts were eliminated. Moreover, it was possible to achieve a significant increase in the recognition rate for the generalpurpose classifier.
BibTeX
@misc{vellasques2006modeling,
  author = {Eduardo Vellasques and Luiz S. Oliveira and Alceu S. Britto and Alessandro L. Koerich and Robert Sabourin},
  title = {{Modeling segmentation cuts using support vector machines}},
  year = {2006},
}
Figure