This article explores a minimally supervised method for extracting components, mostly letters, from historical manuscripts, and clustering them into classes capturing linguistic equivalence. The clustering uses the DBSCAN algorithm and an additional classification step. This pipeline gives us cheap, but partial, manuscript transcription in combination with human annotation. Experiments with different parameter settings suggest that a system like this should be tuned separately for different categories, rather than rely on one-pass application of algorithms partitioning the same components into non-overlapping clusters. The method could also be used to extract features for manuscript classification, e.g. dating and scribe attribution, as well as to extract data for further palaeographic analysis.
1.1
The present work explores a minimally supervised method for extraction and clustering of writing components from historical manuscripts. The primary purpose is to locate letters and to group them into classes capturing graphemic equivalence. The method will to some extent also find ligatures, scribal abbreviations, parts of letters, and letter sequences.
Clustering of writing components can be used as
a first step in the transcription of manuscripts. By
annotating clusters which group elements correctly
– and manually correcting those that almost do – we
will get cheaply acquired transcriptions, admittedly
incomplete, associated with regions of the images.
Components labelled in this way can be used as
data for training of systems for handwritten text
recognition. Another possible application is to use
these data to compare different manuscripts, for
instance, in the kind of digital palaeography proposed
by
The dominant approach in the field of handwritten
text recognition is building systems based on
supervised machine learning. This kind of work relies
on labelled data, i.e. transcriptions. Less attention
has been paid to methods for automatic analysis
of handwriting which do not rely on transcriptions.
When no linguistic labelling is available, clustering
is a way of finding structure in writing.
The two main components of the current system are responsible for component extraction and clustering, respectively. As these components have to be based on certain a priori assumptions, they can be designed in a variety of ways, and their operation has to be guided by a number of parameters. We will present and evaluate a baseline system, which has proved useful as a point of departure during the development phase. Its parameter setting is to a large extent comprehensible as reflecting properties of writing. After having looked at the baseline system, we will proceed to look at a few modified set-ups.
We will evaluate the clustering results using the
measures precision and recall (see e.g.
The first steps in the processing of the image files
(JPEG, TIFF) are scaling and binarization by a
version of the algorithm of
In order to adapt the component extraction to the actual size and scale of the writing, the processing is guided by the typical stroke width, ws (for the manuscript images being analysed). The system estimates ws by determining the most common width of sequences of continuous horizontal foreground (ink) pixels separated by at least two pixels of background. After that, the system rescales the images to make sure all manuscripts are processed at roughly the same writing-relative resolution. In the experiments we discuss here, ws = 7 pixels.
The component extraction process is guided by five parameters, (ti; wmn; wmx; hmn; hmx). First, the system performs connected component labelling to find connected stretches of writing. Components whose width and height are in the intervals [wmn; wmx] and [hmn; hmx], respectively, are extracted, while those wider than wmx are fed to a segmentation module. Loosely speaking, ti is the thickest amount of ink that allows a vertical cut to be made.
To be more specific, the segmentation process operates on the column sum of foreground (i.e. ink) I(x), as computed with reference to the bounding box surrounding the component. It scans the component pixel by pixel, xL being the current position. When xL = 0 or I(xL) ti, the system looks for a xR 2 [xL + wmn; xL + wmx] where I(xR) ti and I(xR) is the smallest value. If it is not unique, the leftmost (smallest) xR is preferred. A component spanning xL to xR is then proposed, and scanning resumes with xL = xR. If no xR meets the condition, scanning resumes with xL = xL + 1. If the height of a proposed component spanning xL to xR is in the interval [hmn; hmx], it is added to the set of extracted components.
In order to normalize the segmentation with respect to the size and scale of the writing, each of the segmentation parameters is defined as the product of a constant and ws (the typical stroke width). We used (ti; wmn; wmx; hmn; hmx) = (1:0ws; 3:0ws; 8:0ws; 3:0ws; 15:0ws) in the set-ups discussed here. These parameters represent a heuristic assumption about the appearance of the handwriting. We have tailored them to medieval book hands, aiming for a “wide-spectrum” retrieval of letter-size elements, but more or less excluding the letter i (bold case will be used for linguistic categories, rather than something like hii) and other “minim” components. 4
Clustering is performed in three steps. The first one uses the density-based DBSCAN algorithm for obtaining a “core clustering”. Secondly, small (< 40 elements here) clusters are removed. The third step is classification with the purpose of assigning additional not yet clustered components to the remaining (larger) core clusters. 4.1
Each manuscript component is characterized by a feature vector, which quantifies the distribution of foreground pixels as captured by a grid of 11 11 equal subrectangles over the bounding box. This consequently gives us 121 features, as illustrated by Figure 1. Each value is the ratio of the number of foreground pixels to the size of the subrectangle region (i.e. fi 2 [0:0; 1:0]).
The clustering and classification relies on Euclidean distance operating on these vectors: distance( f ; g) = qåin=1 ( fi gi)2. 4.2
The system uses the density-based DBSCAN
algorithm
The absolute distance values, as defined by the feature model and the distance metric (and thereby Eps), are hard to work with in a direct and intuitive way. For this reason, we suggest a data-oriented criterion, sensitive to the properties of the set of components to be clustered, for selecting the Eps value. Thus, we estimate Eps from a given threshold, pE ps, in such a way that pE ps is the probability that two randomly selected image components be at most Eps distant from each other. The intuition is that this probability should correspond to that of two random components being evident instances of the same graphemic type. In the baseline set-up, we estimated Eps from pE ps = 0:0007. If we compare this number with English electronic text, we can note that the corresponding character-related probability is around 0:07, i.e. roughly 100 times higher than the number we assume here.
After the DBSCAN step, which typically gives us clusters of highly varying sizes, we remove the clusters which we think are too small (size < 40 in the experiments here) to merit attention. This will make the output easier to inspect and use. 4.3
We add more elements to the clusters formed by the core clustering, using a “nearest neighbour” classification procedure on the DBSCAN noise and the components from the removed small clusters. If we have retrieved n core clusters, with sets of elements E1; : : : ; En, respectively, the system computes the centroids, c1; : : : ; cn, for each cluster. It also determines the distance di, such that a certain fraction, f , of the elements of Ei is within that distance of the centroid. So, di is the smallest distance such that fe 2 Ei j distance(e; ci) < dig > f Ei . In the experiments reported here, f = 0:9. This will, loosely speaking, exclude peripheral components.
The classification procedure assigns each component, e (which does not yet belong to a cluster), to cluster i if and only if ci is the nearest centroid among c1; ...; cn, and distance(e; ci) < di. 4.4
The system exists in the form of a Java implementation. For the purpose of the experiments reported here, it presents the set of clusters by means of images and HTML files, as in Figure 2. The members of each cluster are exhibited in a separate document as in Figure 3, page by page and ordered by their closeness to the centroid. 5
In the experiments we conducted in order to evaluate the system, we used eight 7th–15th century book manuscripts as data. We tried a number of different clustering parameter settings. Complete outputs for all combinations of data and set-ups discussed here are available as Supplementary Materials at http: 5.1
In our experiments, we applied the system to eight different manuscripts, representing four different important medieval periods and styles, each in two clearly different instances, spanning roughly seven centuries, see Table 1. The styles are Irish and Carolingian minuscule, textualis, and cursiva, The first four manuscripts are in Latin; the rest in Old Swedish. The pages of B 59 (the oldest book in Swedish) are worn and stained. B 10 suffers from bleed-through. Otherwise, the data are from fairly well-preserved books. The digitizations are of high quality – we used the highest resolutions available – in JPEG or TIFF format. Each file is between 2MB and 90MB in size. The terms of use allow the images to be used freely for research purposes. (The URLs for images and metadata are found in Table 1). 5.2
We applied the system with the baseline parameter settings (specified above) on the eight manuscripts. From each sequence of pages, the system extracted exactly 20 000 components. Between 25 and 44 images had to be read. The clustering assigned between 5000 and 14 800 of them to clusters. We manually inspected the clusters and performed an analysis of which linguistic categories they represent. We also estimated the precision scores. In the case of letter categories, we accepted also a few similar majuscule instances of the same letter, e.g. O among o, as true positives. Table 2 summarizes the results.
Clusters for between 5 and 15 letters (not counting allographs) were established. Letters like a, d, m, and q (q only for Latin) had a strong tendency to appear. As expected, no i cluster was found. In a few cases, two different clusters for the same letter had been established. The number of clusters for ligatures and bigrams (ordinary two-letter sequences) were strikingly higher for the textualis and cursiva manuscripts, reflecting the fact that connected letters are typical of these styles.
We can distinguish two kinds of outcome: For some manuscripts, components were only assigned to meaningful clusters (Gen. 1, CS 557, CS 564, C 61(b)). In the other cases, also large “useless” clusters were established (CS 60, B 59, B 10, C 61(a)). This suggests that more generous clustering settings could be worth exploring in the former cases, while the latter situation invites using more reluctant DBSCAN parameter values. 5.3
We tried to cluster the manuscripts Gen. 1, CS 557, CS 564, and C 61(b), whose components were potentially “underclustered” by the baseline set-up, with pE ps = 0:0014 (i.e. doubled), otherwise using the baseline settings. Table 3 summarizes the results. A general tendency is, as can be expected, that the clusters become larger and less pure. The change also gives us new useful clusters, e.g. h for Gen. 1 and b, h, (ligature d with macron), &, and (pro abbreviation) for CS 564. The CS 557 output covers 18 minuscule letter categories. However, this setting also to some extent leads to merging of categories discerned in the baseline set-up. So, for instance, in the Gen. 1 output, f joins the p[s2 blend, and instances of n and r – just like instances of a and o in C 61(b) – get mixed up in the same cluster. 5.4
We also tried two ways of making the clustering of components more restrictive. The first one was tightening the DBSCAN neighbourhoods by halving the probability pE ps (i.e. pE ps = 0:00035) from which Eps is estimated. Secondly, we doubled the neighbourhood size requirement, i.e. used minPts = 22. Applying the two settings to two of the “overclustered” manuscripts produced the outputs characterized in Table 3. Figure 4 aligns two cluster set overviews for B 59, one for the baseline set-up and one for pE ps = 0:00035.
We can see that the more restrictive settings, as expected, make the clusters fewer and smaller across the board. For CS 60 the outcome is otherwise similar to that for the baseline set-up. A new cluster is formed by the detachment of a p[r category. For B 59 the response to the more restrictive settings is more pronounced and fruitful. Fairly pure clusters appear for three or four additional letters, d (only with the lower pE ps), f, k, and i (thorn). Some letter sequence categories disappear, but we also see a few new ones. For both manuscripts, the two set-ups (pE ps = 0:00035 and minPts = 22) have fairly similar consequences. 5.5
Tables 2–4 give an idea about how the recall scores for different categories compare to each other. (The recall is 0 for categories for which the system does not establish a corresponding cluster.) Letters like a, d, m, and q seem to be “easy” ones, while the more infrequent letters are more difficult to retrieve or have been filtered out by the size constraint.
The component extraction set-up is probably more or less responsible for the scarcity of i, f, and l clusters.
We will not provide a fully-fledged analysis of absolute recall, but we have estimated recall for a few cases and categories. For this purpose, we annotated the three first pages (or four, i.e. two spreads for C 61(b)) of the sequences for Gen. 1, CS 557, CS 564, and C 61(b) as regards three letter categories, e, m, and o. We counted blackink minuscule non-ligature letter instances in the main text columns as the relevant ones, excluding e.g. majuscule and red ink writing and later additions. (The ligature versus non-ligature distinction was sometimes difficult to apply, e.g. for Gen. 1.) We manually counted the true positives using the overviews of the clustered components (arranged page by page, as in Figure 3). Table 5 gives the precision and recall scores for the two set-ups described earlier for the manuscripts. Scores for the baseline core clustering (i.e. excluding the contribution by the classification step) are also reported.
We see that the absolute recall scores vary considerably. The low values for e and CS 564 pertain to the “clean-cut” e category; many e:s are assigned to sequence categories. The m and o categories seem to reach high recall scores in several cases. Instances of these are easy to extract because they are internally well connected and isolated from other letters.
We may also expect the feature model to “agree” with the shapes of m and o in well capturing the differences between them and other letters.
The pE ps = 0:0014 set-up leads to a clear increase in recall in most cases, without loss in precision. For m and o in CS 564, and C 61(b) precision is somewhat compromised. For C 61(b) it even leads to the merging of the a and o clusters (separated in the baseline output). The o-precision for the a[o cluster is just 29%.
The classification step is responsible for 13–35% (comparing manuscript outputs) of the components being assigned to clusters in the baseline set-up. (These components carry a tag indicating their classification-based assignment.) In the small-scale study of Table 5, classification generally leads to a pronounced improvement in recall compared to the core DBSCAN output of the baseline system.
In only two cases, a fall in precision can be obCS 60 a:1138†, c:601?, d:593?, e1:317, c=16, n=14:6k e2:181, m:734?, o:851, q:371, p=27 s:755, t:361 [e2: part of ligatures] er:62†, &:248 CS 557 c=17, n=5:0k p=44 CS 564 c=17, n=6:7k p=42 b:241+93, d1:273, g:64, h:84, l:85, is:104, ss:56 m:585, n:144, o:676, p:597, q:195, r:409+86, s:1141, v:191 a:389, d:563, e:115, m:998‡, o:248, es:104, os:45, ss:92, n[u:1289‡ p:487, q:157, r:195+45, s:1324, ...s:78, it:84 u:456? b[h[li:718?, n[u:4300‡ c[e arc:52, useless: 3274 – B 59 a:2938†, m:361†, n:1562‡, o:488, c=23, n=14:8k s:1220‡ p=44 B 10 a:2218?, a¨:178, b:216†, d:168, c=26, n=10:1k e:375?, k:96, m:487‡, o:933, p=35 s:951‡, t:197?, i:314, v:487?, w:54,
y:112 [a: some with lost diacritic] C 61(a) a:446, d:173, g:383, h:946?, o:116, dh:69, eß:274, c=24, n=10:6k t:443† ot:123, sk:50?, p=31 ß:98, th:934? C 61(b) a:1594, a¨:456, d:508, e:436, en:134, ff:63†, c=27, n=11:2k g:158+60, k:117, m:905†, n:1180†, fo¨:114†, hy:94, p=25 o:511, r:148?, s:237‡, v:88, w:261, sk:205, ta:52, y:130 ti:152 tin:41 al:57, bo:47, fa:105?, fi:157, gh:63, gi:94†, ll:71†, sk:256†, sti:53† a...:367, ...a:290†, e...:110, sk[st:52†, useless: 3846+ 2172+223+190+109 an:130?, fi:66, a...:116, ...a:53, g...:189, ff:69, ffi:68, gi:109? t...:83, useless: 2261+103+97 ...a:88, d...:498, ...d:223, g...:128, ...g:142+107, h...:576†, ...l:47, ...p:46, t...:297?, macron:863, useless: 3535 ...h...:2889+111†, s...:461†, m/n-minim:109
Gen. 1 a:1460?, b:341+51, c:555, d1:284, en:129†, er:63, n[r:2306?, f[p[s2:1906?, pE ps = 0:0014 d2:405, e:863?, h:113, l:349, &:128, e...:55, li:79 r-frag.:156 c=23, n=13:2k m:630, o:994, q:303, s1:213,
t:615†, u:1231 (absent: f, n, r) CS 557 pE ps = 0:0014 c=27, n=9:5k a:594, b:404, c:111, d1:309, co:104, er:184, d2:167, e:423, E:54, g:112, h:108, &:104, is:113, l:109?, m:960, n:685, o:841, p:628, ri:64, ss:66 q:245, r:609+138†, s:1149, t:64, u:969, v:229 – CS 564 a:592, b:282?, d:660, e:202, h:121, :54, er:248, &:85, d...:64, n[u:2992‡, o...:54, pE ps = 0:0014 m:1369‡, o:568, p:542?, q:219, it:245?, on:82, :61, ...s:277, st...:55, useless: c=28, n=10:9k r:276+79, s:1331 ri:119?, ss:103 151+77+54 (absent: u) C 61(b) a¨:488, d:625, e:483, g:214+66, pE ps = 0:0014 k:169, m:945†, n:1277†, r:213?, c=31, n=13:4k s:296‡, v:105, w:330?, y:163 (absent: a, o) en:202†, ff:84†, gh:59†, hy:337†, sk:217, ß:137, ti:174†, tin:43 a[o:2471?, ...h...:2860†, k...:69, r...:78, ...p:50, s...:788†, t...:81†, th...:90†, useless: 200+40 served. The effect of the classification step varies even more for individual categories. Just to take two extreme examples from the full baseline output for CS 557 (see Table 2): for m, 322 of 585 elements were retrieved by classification, but only 1 of 1141 for s. (100% precision in both cases.) 6
In this study, we have shown that simple component extraction and clustering in combination with limited human intervention can be used to produce partial transcriptions of medieval manuscripts in a range of styles. This kind of pipeline will provide a low-cost method for initial annotation, which is potentially useful in many contexts of handwriting analysis and digital philology. However, the basic modules of the system are simple and invite improvement.
The component extraction module relies on very basic methods for binarization, connected component labelling, and component segmentation. We have not considered more sophisticated designs in this paper, but that is certainly one of the more obvious points for future work. Just modifying the segmentation parameters of the current implementation would give us other components to cluster and consequently very different outputs. The system works without making use of modules for layout analysis or line segmentation, other than what is achieved by the connected component labelling. This makes the system more robust with regard to some kinds of manuscript, but using such modules would potentially be useful for guiding the component extraction in other cases.
The feature model seems to work quite well for the styles studied here, because letter distinctions generally correspond to marked contrasts in how ink is distributed in the bounding box. Admittedly, we have only studied fairly regular book styles. The b[h[li mixture produced for C 60 is an example where the model, so to speak, fails to separate the categories. The 11 11 “resolution” is reasonable for letters, but will blur larger components, e.g. letter sequences. The model does not capture absolute or relative size of the components. This is an advantage when there is linguistically insignificant size variation, but could have helped to separate p and s in Gen. 1, see Figure 3. This letter pair also illustrates another problem: A significant part of the p’s is a typically unconnected dot. Another conclusion that should be drawn is that a system like this could benefit from also looking at the contexts in which the components occur. The current system only “sees” the foreground components as framed by the bounding box.
When we looked at the results of the clustering we saw that settings that are fruitful for the retrieval of one letter category might lead to merging of other categories. And, contrariwise, a set-up that will to keep the two categories separated might prevent the system from establishing clusters for other categories. This suggests that a system like the present one should be tuned separately for different categories, rather than rely on a one-pass application of algorithms partitioning the components into non-overlapping clusters. This kind of approach would also benefit from the use of statistical criteria which would help us find good parameter settings automatically.
The author is grateful for the support of two projects, funded by the Swedish Research Council (Vetenskapsra˚det, Dnr 2012-5743) and Riksbankens Jubileumsfond (Dnr NHS14-2068:1), and led by Anders Brun and Lasse Ma˚rtensson, respectively. Thanks also to the participants of the Workshop on Computational Methods in the Humanities (COMHUM 2018) for discussion.