Research on graph theory segmentation method and dataset construction for connected handwritten digits

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.