2.1. Character Extraction, Segmentation, and Recognition

Character extraction, segmentation, and recognition are crucial stages in optical character recognition (OCR) ^[7]. These processes involve extracting characters from images and printed documents for information extraction ^[8]. Various methods, such as water flow, neural networks, endpoint, Euler number, and Fourier transform, are used for character extraction to prepare data for further analysis ^[9].

Segmentation divides characters into subunits for detailed analysis. Techniques, like Hough transform, neighborhood connected units, and vertical/horizontal projection profiles, are employed for text segmentation ^{[10- 12]}. Segmentation is vital for converting images into matrices for in-depth analysis.

Character recognition identifies and converts characters into machine-readable text. Template matching, statistical techniques like k-nearest neighbor and fuzzy set reasoning, and stroke recognition methods are used for character recognition ^{[13- 15]}. These techniques play a crucial role in OCR for data analysis. ^{[14, 15]}

2.2. Skeletonization

Skeletonization reduces binary images to one-pixel representations, aiding in effective 2-D and 3-D object display for recognition, retrieval, and analysis ^[16]. Pervouchine et al. applied skeletonization to extract strokes from handwritten documents, benefiting forensic analysis but being content-dependent ^[17]. Ko et al. faced challenges adapting skeletonization to diverse characters, such as Chinese, Korean, and Japanese fonts, proposing SkelGAN for Korean Hangul ^[18].

Various algorithms, like Zhang-Suen (ZS)-series and one-pass thinning (OPTA)-series algorithms, enhance character skeletonization by addressing noise issues; ZS-series deals with boundary noise, while OPTA offers faster thinning ^[19]. Al-Maadeed used text skeletonization with codebook generation for writer identification, achieving high accuracy and addressing ethical concerns ^[20]. This approach works well with Greek and Latin languages and some other open-source datasets ^[20].

2.3. Image Registration

Image registration aligns images from different time intervals, aiding spatial correspondence in documents ^[21]. Pan et al. describe two common approaches: intensity-based, which focuses on grey level intensity areas, and feature-based, which selects common features for optimal results ^[22].

Zhao et al. highlight the interest in using image registration with a deep learning method called recursive cascade architecture for deformed medical images and documents, offering valuable data for research ^[23]. Wang et al. use the iterative closest point (ICP) method for image registration based on point distances, addressing its time consumption with M-estimation and weighting approaches ^[24]. He et al. apply ICP to register 3D points using geometric features, avoiding local extremum issues and registration errors by considering density, surface normal, angle between data points, and curvature features ^[25].

2.4. Wasserstein Distance

Wasserstein Distance is a valuable tool for measuring similarities or distances between probability distributions, widely applied in document analysis, character similarity, and comparison, as well as in forensic science, research, and probability theory ^[26]. In practice, it finds use in image retrieval and computer vision, focusing on the cost of mass transportation between points for tasks like image synthesis and style transfer.

Ye et al. employed Wasserstein Distance to measure text sequence similarity, leveraging probability distribution functions, though it can be affected when character distances vary ^[27]. Fournier et al. noted challenges in applying Wasserstein Distance, especially with complex high-dimensional data, where it may not always effectively measure similarity between probability distributions ^[28]. Kolouri et al. introduced modified sliced Wasserstein Distance, reducing computational demands by using one-dimensional linear projections for more accurate probability measurements, particularly suitable for generative modeling in research science ^[29]. Piccoli et al. utilized generalized Wasserstein distance to handle the transport equation, effectively addressing the Cauchy problem for vector fields and closely spaced sources, resembling Lipschitzian behavior ^[30].

2.5. Mean Euclidean Distance

The mean Euclidean distance calculates the average distance between two data points in Euclidean space, primarily used for character identification in text files ^[31]. It is effective when data points are in the same dimension ^[31]. In statistical analysis and machine learning, it aids in measuring similarity and dissimilarity by considering the structure and shapes of objects in documents.

You et al. introduced a method to approximate mean Euclidean distance using the Yinyang k-means clustering approach, addressing memory consumption issues and enhancing similarity detection between input dimensions ^[32]. Berthold et al. proposed modifying the k-means algorithm for time series comparisons by adding squared Euclidean distance and incorporating the Pearson Correlation coefficient. This approach effectively normalized input data for more accurate comparisons ^[33]. Hammoud et al. found Euclidean distance useful for pre-defined multi-dimensional constellation sets, improving accuracy by eliminating noise through iterative methods in 2D and 3D estimators ^[34]. Lee et al. highlighted the effectiveness of Euclidean Support Vector Machine (E-SVM) for text document classification, especially with kernel functions. While E-SVM offers better classification accuracy than conventional SVM, it comes with increased processing time due to distance calculations between document data points ^[35].

2.6. Dice Coefficient

The Dice coefficient, or Sørensen-Dice index, assesses character similarity by calculating the ratio of shared elements in datasets, commonly used in image segmentation, forensic document analysis, and medical image processing to verify accuracy ^{[36, 37]}. Higher Dice coefficients signify greater similarity, correlating with improved image segmentation performance.

The dice coefficient is a measure of similarity between two given images. The Dice Coefficient D is defined as:

where $N_r$ is defined as the set of pixels in the reference image and $N_i$ is defined as the set of pixels in the input image.

Liang et al. emphasize the Dice coefficient's role in statistically validating manual and automated medical report segmentation for patient diagnosis but highlight the need to address false negatives, false positives, and class imbalance in model design ^[38]. Oco et al. point out another significant use of the Dice coefficient in identifying language similarity through trigram profiles in documents, particularly in Philippine language documents. This approach has potential applications in phonetic transcription and text analysis, revealing an average difference of 27% in language tree comparisons ^[39].

2.7. Image Clustering

Korean historical books, such as The Song of Enlightenment, utilized moveable metal types for printing, resulting in multiple versions with varying metal types. Yoo employed image processing techniques, including clustering, to identify metal casting defects in these books ^[40].

Lai and Lee applied k-means clustering for binarizing Korean characters, with 3-means clustering outperforming 2-means clustering in character detection and binarization quality ^[41]. Jo et al. used vertical projection and clustering for character segmentation in Korean printed text, achieving high-speed segmentation with 99.25% accuracy and effectively managing touching character issues ^[42]. Song explored the unique history of Korean characters, which differed from China and Japan, highlighting the use of moveable metal types for preserving information in books from the 14th to 19th centuries. Modern image analysis and grouping techniques helped identify changes in characters due to the issues with smoothness and durability of carved text on metal types ^[43]. Similarly, OK utilized image feature extraction and clustering techniques to characterize Korean movable metal type ancient books, shedding light on history and differentiating Korean texts from those of China and Japan ^[44]. This analysis aided in understanding the distinctiveness of Korean historical texts, which were often considered similar to Chinese and Japanese ^[44].

3.1. Characters Extraction, Segmentation, and Classification

The data extraction process begins with high-resolution scans using a flatbed scanner to minimize distortion. These scans include not only printed characters but also non-textual elements like seals, lines, and noise, which must be removed from the dataset. A Trans-UNET network, customized with a specific loss function, is employed to clean the noise and rebuild any broken characters ^[45]. This architecture allows for accurate pixel-wise segmentation of character strokes, even in degraded or noisy input images, which is critical for reconstructing historical typefaces. The Trans-UNET network excels in capturing the intricate details of these characters, ensuring a more precise output. The dataset includes 13,500 image patches, cropped and augmented from the scanned images, with 12,150 patches used for training and 1,350 for testing. Each patch has a resolution of 1024x1024 pixels, and random rotations and scales are applied to ensure the generalization of the model.

To further refine character extraction, the Boundary Gaussian Distance (BGD) loss function is used to enhance the smoothness of character boundaries ^[45]. This method improves upon traditional techniques by applying Gaussian smoothing to ground-truth labels, resulting in clearer, more accurate segmentation, especially when handling ancient documents with rough, noisy strokes. The combination of BGD loss with Dice loss significantly enhances the clarity of the extracted characters, effectively addressing issues like ink bleeds, noise, and missing strokes. The model performs well in difficult cases such as blurred prints and faded characters, demonstrating its effectiveness in processing degraded historical documents.

After noise-free pages are obtained, they are then processed using the segmentation method by Beom et al. ^[6] that involved detection of each character and a convex hull for segmentation. The segmented characters are then fed to PaddleOCR to classify them with respect to their ASCII codes, which are saved in directories corresponding to each character for further analysis ^[46].

3.2. Skeletonization

Once we obtain the binarized images of any two given characters, we then pre-process the images before performing image registration. The reason behind introducing these pre-processing techniques is to cater to the cases where the width of the character is different even though it has been printed using the same type-head as another character. Different widths occur due to the amount of ink applied while printing the character, the greater the amount of ink, the thicker the character will be. Another reason behind that was that without erosion or skeletonization, the union functions that we later use for similarity measurement yield a greater value due to a larger area being part of the characters overlapping, and lesser values of the distance functions because the characters are closer to each other, even if printed using different type-heads.

For the skeletonization process, we use an iterative parallel thinning algorithm ^[47]. We start with a black pixel p in a 3x3 window, with the neighbors named $x_1, x_2, x_3, \dots, x_8$, and all the nine values are collectively denoted by $N_{(p)}$. The odd-numbered values of $x_i$ are all the adjacent neighbors of p. The number of black pixels in $N_{(p)}$ is denoted by $b_{(p)}$. In our conditions, we also use the crossing number $X_H(p)$ defined as the number of times we cross from a white point to a black point when iterated over $N_{(p)}$ in order.

Fig. 4. A visual representation of $N_{(p)}$.

Fig. 4 shows a visual representation of $N_{(p)}$. The algorithm we used for skeletonization consists of two sub-iterations for a single iteration. In the first sub-iteration, we delete the pixel p if the conditions 1, 2, and 3 are met, and in the second sub-iteration, we delete the pixel p if the conditions 1, 2, and 4 are met.

Condition 1:

where

Condition 2:

where

Condition 3:

Condition 4:

In our case, we use n as infinity, making the whole skeletonization process go on iteratively until the length of the given image gets to one pixel thick.

3.3. Image Registration Using Iterative Closest Point (ICP)

Image registration plays a critical role in ensuring accurate comparison between printed characters, as unaligned images can result in significant errors when computing similarity metrics. To align images before comparison, we use the Iterative Closest Point (ICP) algorithm, a well-established method for registering two point-clouds ^[48]. In our process, we convert the two given images (a fixed and a moving image) into 3D point-clouds, where each pixel of the image corresponds to a point in space. Specifically, we extract the pixel coordinates of the white pixels (representing character strokes) from the 2D images and then add a third dimension (z = 0) to treat the images as 3D point-clouds suitable for ICP processing.

The ICP algorithm consists of two primary steps: (1) finding correspondences between points in the two point-clouds (i.e., matching the closest points from the moving image to the fixed image), and (2) computing the transformation (rotation and translation) that minimizes the distance between these correspondences. This process is repeated iteratively until the transformation converges, meaning that the difference between the moving and fixed point-clouds is minimized. During each iteration, we calculate the distance between the closest corresponding points, and the transformation is adjusted to bring the moving image closer to the fixed image. The algorithm stops when the change in the transformation matrix becomes negligible, indicating that the best alignment has been achieved.

To handle cases where the two images do not overlap perfectly, we use a matching threshold $d_{max}$. This threshold is a part of generic ICP functions provided in MATLAB and helps discard correspondences between points that are too far apart, which could otherwise reduce the accuracy of the alignment. Once the ICP algorithm has converged, the final transformation matrix is applied to the moving image, aligning it with the fixed image. The registered image can then be compared directly with the fixed image using similarity metrics.

In our approach, we convert 2D images into point-clouds, apply the ICP algorithm for alignment, and then re-convert the registered point-cloud into an image format. This ensures that the characters are aligned correctly before similarity computations are performed, minimizing errors due to misalignment. The detailed steps of the ICP algorithm and the transformation process are essential for accurately comparing characters that may have subtle variations due to printing inconsistencies.

Algorithm 1: Generic ICP algorithm.

3.4. Similarity Computation

A lot of research has been done in the past with respect to images and graphs for similarity computation. For our use case, we tried a few state-of-the-art methods later followed by a comparative analysis to conclude the best one for our character similarity measurement. The methods are described as follows:

3.4.2 Mean Euclidean Distance

We apply a distance function to our fixed image and the registered image we obtain from the previous step. For the distance function, we are using Euclidean distance. It is defined as the length of a straight line between two points in Euclidean space. Given that we have two points, $A(x_A, y_A)$ and $B(x_B, y_B)$, the Euclidean distance D between them is defined as follows:

(11)

$ d(A,B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}. $

This process is then repeated for each element in the point sets obtained from the images.

The next step consists of getting the minimum value for each column in the obtained array which is calculated using the following equation:

(12)

$ distance\_min = \min_{i=1}^{n} \{d(A_i - B_i)\}. $

In the equation above, $n$ defines the number of columns in $d(A,B)$.

The final step consists of getting the mean distance. The mean distance is obtained as follows:

(13)

$ \mu = \frac{1}{N} \sum_{i=1}^{N} distance\_min_i. $

After comparing the results obtained from this method on different images, we were able to see a pattern that the more similar the image, the lesser we obtain the mean distance.

We implement an algorithm to group similar images based on their Dice similarity score, represented in Algorithm 2. It begins by loading all images $I$ from a specified folder and sorting them according to their page numbers extracted from the file names. This step ensures that images from the same page are not incorrectly grouped together. Once the images are loaded and sorted, the algorithm calculates the Dice similarity score, $D_{ij}$, for every unique pair of images $(I_i, I_j)$ that belong to different page numbers. The Dice scores for all image pairs are stored in a matrix $D$ for later use.

A threshold value $\theta$ is defined to determine if two images are considered similar enough to be placed within the same group. The grouping process then iterates through each image in $I$, starting from the first. This initial image is assigned to the first group in $G$. The algorithm checks the Dice scores between the first image and all subsequent images, adding any images with $D_{ij} > \theta$ to the first group.

Algorithm 2: Type Grouping Algorithm

This process of expanding the initial group continues until all images below the threshold are reached. New groups are then created, and the assignment is repeated for the remaining unassigned images.

Finally, the groups are organized and printed to view the final groupings. Unique group IDs $g_k$ are determined and each group is represented as a cell in the array $G$, containing the images indices assigned to that group. This allows for easy visualization of how the algorithm has clustered visually similar images together based on their computed Dice similarity scores.