Application of the traveling salesman problem to optimize skeletonization and stroke reconstruction

Abstract

The preservation of Turots Nusantara manuscripts written in Pegon script faces significant challenges due to physical deterioration and the complexity of handwritten styles. This study proposes a novel digitization approach based on image processing to extract and reconstruct handwriting strokes by combining skeletonization and the travelling salesman problem (TSP) algorithm. The novelty of this research lies in the application of a modified Greedy TSP algorithm capable of recognizing branching and cyclic structures typical of Arabic–Pegon characters, enabling accurate reconstruction of handwritten stroke sequences. The process involves preprocessing (grayscale, thresholding, and morphological operations), skeleton extraction using a thinning method, and weighted graph construction based on Euclidean distance between skeleton points. The proposed system achieved an average precision of 0.552, recall of 0.815, F1-score of 0.657, and accuracy of 0.82. These results demonstrate the method’s effectiveness in detecting and reconstructing character shapes from Pegon manuscripts. Practically, this approach offers potential applications in the automatic digitization, preservation, and analysis of Pegon script, contributing to the conservation of Indonesia’s Islamic intellectual and cultural heritage.