Research on graph theory segmentation method and dataset construction for connected handwritten digits
- 1Hebei Key Laboratory of Optical Fiber Biosensing and Communication Devices, Institute of Information Technology, Handan University, Handan, China.
- 2School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, Hebei, China.
Abstract
Handwritten digit recognition has considerable potential for automating document analysis. However, in real-world scenarios, character adhesion is a critical constraint on the performance of traditional automated educational scoring systems. To address the challenge of segmenting touching handwritten digits, this research presents a systematic investigation from both data and methodological perspectives. First, a standardized, category-balanced Two-digit Touching image dataset is constructed. By covering all 100 combinations from “00” to “99,” it simulates realistic adhesion patterns by defining a maximum overlap ratio and introducing random misalignment, thereby providing a fair benchmark for algorithm evaluation. On the methodological front, this paper proposes a “cutting domain” graph-theoretic segmentation framework. This framework decouples the adhesion segmentation problem into two stages: constructing a structured, low-cost search space (the cutting domain) with a threshold-free growth algorithm, and then transforming the segmentation task into an optimal path search on a graph. Within this cutting domain, the globally optimal Dijkstra’s algorithm and a family of direction-biased A* heuristic algorithms are implemented and compared with traditional methods (the Vertical Projection Method and the Watershed algorithm) as well as a deep supervised segmentation baseline (U-Net). Experimental results show that the proposed graph-theoretic segmentation method significantly outperforms traditional methods. Among the methods tested, the Left-Biased A* algorithm achieves the highest recognition accuracy of 93.13% on the test set, an improvement of over 5 percentage points over traditional methods. Ablation experiments confirm the critical role of connectivity constraints. Further evaluation on real-world handwritten digit strings (the CVL dataset) confirms the framework’s generalization, maintaining 91.4% accuracy, whereas a cross-paradigm comparison shows a supervised U-Net baseline collapsing from 95.90% to 53.05% under the same domain shift. This study provides a standardized evaluation benchmark and novel methodological insights for segmenting touching characters, thereby advancing document image analysis technology.
Related
- A variational construction for Einstein metrics on connected sums of S2× S2
- Addressing threats to validity in large dataset research
- FPGA-Based Implementation of Artificial Neural Network for Accelerated Handwritten Digit Recognition
- ProofLoom: Proof-Obligation-Driven Theory Construction for Autoformalizing Research-Level Stochastic Optimization
- Unknotting number is not additive under connected sum
BibTeX
@article{zhang2026research,
title = {{Research on graph theory segmentation method and dataset construction for connected handwritten digits}},
author = {Zhilai Zhang and Yang Zhang and Yang Wang},
journal = {PLOS One},
year = {2026},
month = oct,
doi = {10.1371/journal.pone.0360920},
url = {https://doi.org/10.1371/journal.pone.0360920},
note = {CC BY},
}
RIS
TY - JOUR
TI - Research on graph theory segmentation method and dataset construction for connected handwritten digits
AU - Zhilai Zhang
AU - Yang Zhang
AU - Yang Wang
PY - 2026
DA - 2026/10/29
JO - PLOS One
DO - 10.1371/journal.pone.0360920
UR - https://doi.org/10.1371/journal.pone.0360920
AB - Handwritten digit recognition has considerable potential for automating document analysis. However, in real-world scenarios, character adhesion is a critical constraint on the performance of traditional automated educational scoring systems. To address the challenge of segmenting touching handwritten digits, this research presents a systematic investigation from both data and methodological perspectives. First, a standardized, category-balanced Two-digit Touching image dataset is constructed. By covering all 100 combinations from “00” to “99,” it simulates realistic adhesion patterns by defining a maximum overlap ratio and introducing random misalignment, thereby providing a fair benchmark for algorithm evaluation. On the methodological front, this paper proposes a “cutting domain” graph-theoretic segmentation framework. This framework decouples the adhesion segmentation problem into two stages: constructing a structured, low-cost search space (the cutting domain) with a threshold-free growth algorithm, and then transforming the segmentation task into an optimal path search on a graph. Within this cutting domain, the globally optimal Dijkstra’s algorithm and a family of direction-biased A* heuristic algorithms are implemented and compared with traditional methods (the Vertical Projection Method and the Watershed algorithm) as well as a deep supervised segmentation baseline (U-Net). Experimental results show that the proposed graph-theoretic segmentation method significantly outperforms traditional methods. Among the methods tested, the Left-Biased A* algorithm achieves the highest recognition accuracy of 93.13% on the test set, an improvement of over 5 percentage points over traditional methods. Ablation experiments confirm the critical role of connectivity constraints. Further evaluation on real-world handwritten digit strings (the CVL dataset) confirms the framework’s generalization, maintaining 91.4% accuracy, whereas a cross-paradigm comparison shows a supervised U-Net baseline collapsing from 95.90% to 53.05% under the same domain shift. This study provides a standardized evaluation benchmark and novel methodological insights for segmenting touching characters, thereby advancing document image analysis technology.
SN - 1932-6203
ER -