Related Work and Overview

§ 13 A large number of publications, competitions (Gatos, Ntirogiannis, et al. 2009) and new applications are devoted to the subject of converting document images into binary images and separating text from background. Overview papers comparing different methods are given for instance in Gupta et al. (2007) or Leedham et al. (2003). In general, binarisation algorithms for document image analysis can be divided into three main classes (Garain, Paquet, et al. 2006):

• global thresholding,
• adaptive thresholding, or
• clustering algorithms.

§ 14 Global and adaptive thresholding techniques use a threshold T to distinguish between foreground and background and are therefore executed primarily on grey level images I(i,j). The resulting black and white binary image BW(i,j) is defined as:

§ 15 Clustering algorithms like k-means use the grey level or colour to classify similar observations into foreground or background (Leydier, et al. 2004). Generating binary images from colour or multispectral images is still not prevalent (Garain, et al. 2006). Alternatively, in the simplest way, colour images are converted into grey level images and then converted into binary images by thresholding.

§ 16 In the case of old and degraded documents, local methods outperform global ones. For instance, Sauvola and Pietikäinen (2000) developed an adaptive document image binarisation by determining a threshold for each pixel. Gatos et al. (2006) developed an adaptive degraded image binarisation algorithm following several distinctive steps: Wiener filtering, a rough estimation of the foreground region, the calculation of the background model, and finally post-processing methods like shrink and swell filtering to improve the quality. Recently Moghaddam and Cheriet (2009) proposed a method for the restoration of single-sided low-quality document images based on a multi-level classifier. This approach is designed for colour images of historical documents and is based on connected component labelling to capture spatially linked pixels of similar colour. Wolf and Doerman (2002) use MRF models for the binarisation of low quality text. Their model for the spatial relationship is defined on a neighbourhood of 4x4 pixel cliques. Cao and Govindarayu (2009) use MRFs for the binarisation of degraded handwritten forms where the spatial relations are obtained from a training set of high quality binarised images and consist of 114 representatives of shared patches.

§ 17 In contrast to the studies cited above we have developed an algorithm for foreground-background segmentation operating on multispectral images. Therefore we do not use threshold or clustering, but combine spectral and spatial features.

MRF Based Foreground-Background Separation of MSI Data

§ 18 Our main idea for foreground-background separation is to combine spatial and spectral features. Therefore we utilise an MRF model which provides a probability theory for analysing spatial or contextual dependencies (Li 2009). Emphasis on the combination of spatial and spectral components is particularly important in the case of ancient documents with varying textures (e.g. of the hair and flesh sides of parchment). Therefore, we include the visual nature of characters by means of stroke features. The only parameter we need is the mean stroke width, which can also be evaluated automatically (Pervouchine, Leedham, et al. 2005).

§ 19 The MRF model (Li 2009) is commonly represented by an energy function E(x) on a regular lattice S where Ψ_i(x_i) are the data costs, i.e., the costs assigning the label x_i to pixel i∈S . The second term Ψ_i,j(x_i,x_j) is the cost of assigning labels x_i and x_j (belonging to a clique C) to two neighbouring pixels, where ß is a weighting parameter controlling the prior. The labelling x with minimum energy E(x) is the optimal solution and can be found via energy minimization methods like belief propagation (Freeman, Pasztor, et al. 2000) or Iterated Conditional Modes (ICM) (Besag 1986).

§ 20 The prior model Ψ_i,j(x_i,x_j) reflects the fact that the segmentation of image regions is locally homogeneous. For the domain of character segmentation we propose to use higher order MRFs with cliques covering the stroke properties of the characters.

§ 21 For a regular lattice S the neighbour set N of i is defined as the set of nearby sites within a radius r. A first order MRF involves directly connected pixels in both the horizontal and vertical direction, see Figure 3a. The numbers n = 1 ... 5 in the figure indicate the neighbouring sites in an n^th order neighbourhood system. As observed by Roth and Black (2005) MRF priors with small neighbourhood systems of only first order limit the expressiveness of the models. Thus C is the set of all pixels s within a radius r, where r corresponds to the radius of the mean stroke width. Our experiments for manually segmented characters allocate a mean stroke width of 5 pixels. Thus the prior considers a neighbourhood set of at least third or fourth order. To illustrate the neighbourhood system on our images consider Figure 3b. The figure shows one character from our data set with a white circle corresponding to a neighbourhood system of the fourth order.

§ 22 From the information of the multi-spectral image the observation model Ψ_i(x_i) is extracted. The observation model or image process follows a normal distribution N(µ,Σ) (Kato, Pong 2006). Each class (foreground/text and background) is represented by its mean vector µ and covariance matrix Σ. The entities are modelled by a Gaussian mixture model.

§ 23 Energy minimisation in finding optimal solutions can be done either by local methods, like ICM, or global methods like simulated annealing (Li 2009). We used ICM to solve this energy which is a good trade-off between quality and computing time (Kato 2006). ICM uses a deterministic strategy to find local minima. It starts with estimation and then selects a label for each pixel that gives the largest decrease of the energy function. The process is repeated until convergence.

Experiments and Results

§ 24 Our segmentation method has been tested on a varied set of ancient documents. The test set consists of four folia for which ground truth data was generated manually by specialists of our philological team. An example can be seen in Figure 4a showing a single line from folio 29 recto from a single band with high contrast (BP 450). As stated in "Multispectral Image Acquisition," above, our MSI acquired nine spectral images with a spatial resolution of 565 dpi. The proposed MRF based binarisation approach is compared to state-of-the-art algorithms developed especially for historical, low contrast or noisy document images. The first method is an adaptation of the k-means algorithm proposed by Leydier et al. (2004), but in contrast to the original work we use the MSI data instead of a colour image as input, resulting in a nine dimensional feature space. Furthermore, we compare the MRF based approach to the Sauvola binarisation method (Sauvola, et al. 2000). Since thresholding algorithms perform on single gray level images, the method of Sauvola and Pietikannen (2006) is performed on a single band image with the best contrast (BP 450).

§ 25 To evaluate the results and to rank the performance of the different methods, we use the statistical measures of precision and recall (Gatos, Ntirogiannis, et al. 2009): where TP is the number of true positives, FP the number of false positives, and FN the number of false negatives. A pixel is classified as true positive if it is identified correctly. It is classified as false positive if it is wrongly classified as a match, i.e., pixels which are detected as text, although they belong to the background. Finally, false negative describes a foreground pixel that was wrongly classified as belonging to the background.

§ 26 The first experiment aimed at analysing the behaviour of the neighbourhood system N and the weighting parameter ß. Table 2 shows the precision and recall rate for ß = 0.1 and ß = 0.3 and a neighbourhood system n = 1…5. It can be seen that the recall values are very low for n < 3 which results from the background noise, i.e., noise is detected as text when the neighbourhood considered is too small. The best solution is obtained with n = 4 and ß = 0.1 which is in concordance to the proposed stroke characteristics.

Table 2: Evaluation of Order and ß

§ 27 Generally it can be said that the smaller the considered neighbourhood system, the more noise emerges in the background. On the other side, a neighbourhood set considering too many pixels leads to missing characters or to closed character gaps or holes. The same can be said for the influence of ß.

§ 28 The precision and recall rate for the ground truth data of the four manually segmented folia can be seen in Table 3.

Table 3: Precision and Recall Rate

§ 29 Especially for folio 17 recto and 30 verso the folia segmented with the k-means algorithm show only suboptimal results due to low contrast. The thresholding method shows a better recall rate of average 0.67, but has lower precision (0.65). The proposed MRF method has the best performance with an average precision rate of 0.89 and an average recall rate of 0.73. A description of the results is given for folio 29 recto. Figure 4 shows the results from folio 29 recto after the segmentation with the Sauvola binarisation method (4b), k-means clustering (4c), and the MRF approach (4d) with parameters ß = 0.1 and a neighbourhood of fourth order.

Figure 4a: 29r Original

Figure 4b: Sauvola

Figure 4c: k-means

Figure 4d: MRF

§ 30 It can be seen that especially the thresholding image contains noise in the background and even within the characters. The resulting binary image from the k-means method fails to identify the rightmost character, and others are broken. The result of the MRF approach segments even the rightmost character which has very low contrast. Moreover, the characters do not show missing or broken parts like the results from the k-means algorithm. Conspicuously, the recall rate is sometimes very high; for example, in folio 30 verso, when segmented with k-means. But it can be seen that the precision is very low at the same time, which denotes that the letters are detected rather as blobs than as characters. Thus the segmented characters cannot be identified any more.

Character Decomposition and Primitive Extraction

§ 32 After the binarisation described in "Foreground-Background Separation," above, each character is reduced to a skeleton that serves as the basis for primitive extraction. The quality of the binary image is essential for the stroke extraction procedure and the number of true positives grows in correlation with the readability of the binary images.

§ 33 In our approach we adapted a linguistic method of graphetic script description developed by Miklas (1992 unpublished), which is based mainly on binary principles. He distinguishes two categories of character features: a) dynamic, pertaining to the realisation (production) of the letter, and b) static, describing the shape of the character, i.e., which characteristic elements, or primitives, does it consist of (perception). Sample static character features are:

Table 4: Static Character Features (Vill, Sablatnig 2008)

§ 34 Based on its skeleton each character-form is dissected into nodes and strokes. Nodes are defined as junctions in the skeleton with a minimum of three strokes crossing, while strokes are skeleton segments between nodes, from a node to an endpoint in the character (see Figure 5), or loops (Vill, Sablatnig 2008).

Figure 5: Schematic Views of Static Stroke Segmentation of Glagolitic Character

§ 35 The individual characteristics of each stroke (vertical, horizontal, straight, bent, etc.) constitute a sensitive classification system (Vill, Sablatnig 2008) that can even cover differences between individual hands.

§ 36 A precision and recall evaluation was executed on image data from the manuscripts, as well as on samples from a professional calligrapher (Table 5). Both datasets were also evaluated as ground truth data by our philological team. The average precision TP rate coincides closely with the ground truth data. The recall rate indicated good results with 0.20 FN for the Missale Sinaiticum and 0.17 for the calligrapher’s data set.

Table 5: Static Character Feature Calculation

§ 37 These results proved that the adaptation of philological criteria for computer application is feasible for the evaluation of static graphetic features (for further details see Vill, Sablatnig 2008).

Character Database

§ 38 After the automatic decomposition of static strokes, the calculated data can be transferred to a database (Gau, Vill, et al. 2010) with fundamental overview, query, statistics, and print out options (Figure 6, left side).

Figure 6: Graphical User Interface of the Character Database

§ 39 The graphical user interface of the database also permits manual evaluation according to the same criteria as the automatic evaluation (Figure 6, right side). This comparison between computer and human perception provides ground truth for the quality of the computer's primitive extraction on the one hand and for psycholinguistics on the other.

Layout Analysis

§ 40 In a subsequent application we perform an analysis of the page layout (ruling, margins, decorations, etc.) based on the binary images provided by the separation step. The ruling (line) structure is automatically detected by the script flow and then extrapolated on those parts of damaged pages, where the script is not visible, by using a priori knowledge of the document layout scheme (for details see Kleber, Sablatnig, et al. 2008).

Figure 7: a) Results of Semi-Automatic Layout Analysis and b) Underlying Layout Scheme (A Priori Knowledge)

§ 41 Figure 7a illustrates a sample result of the semi-automatic layout analysis with red lines calculated from detected script and green and blue lines extrapolated according to the a priori knowledge (Figure 7b) of the layout scheme.

§ 42 This combination of IT with philological expertise made it possible to automate layout analysis even for damaged manuscripts to such an extent that it can automatically discern textual areas from margins and script from decorations or other high-contrast non-textual elements, like patches of mould.