Related Work and Overview

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.

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:

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.

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.

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

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).

The MRF model (Li 2009) is commonly represented by an energy function E(x) on a regular lattice S

where Ψi(xi) are the data costs, i.e., the costs assigning the label xi to pixel i∈S . The second term Ψi,j(xi,xj) is the cost of assigning labels xi and xj (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).

The prior model Ψi,j(xi,xj) 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.

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 nth 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.

Figure 3a: Neighbourhood System in MRFs

Figure 3b: Glagolitic Character

From the information of the multi-spectral image the observation model Ψi(xi) 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.

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

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).

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.

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.

Evaluation of Order and β n = 1 n = 2 n = 3 n = 4 n = 5 precision 0.81 0.81 0.82 0.82 0.80 recall 0.62 0.65 0.65 0.78 0.70 n = 1 n = 2 n = 3 n = 4 n = 5 precision 0.80 0.79 0.83 0.79 0.75 recall 0.67 0.73 0.66 0.80 0.66

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 β.

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

Precision and Recall Rate Folio   k- means MRF Sauvola 17 recto precision 0,58 0,93 0,67   recall 0,34 0,64 0,72 29 recto precision 0,67 0,82 0,63   recall 0,72 0,78 0,61 30 verso precision 0,54 0,90 0,73   recall 0,75 0,68 0,72 27 recto precision 0,85 0,92 0,55   recall 0,69 0,81 0,64 Average precision 0,66 0,89 0,65   recall 0,63 0,73 0,67

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

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

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.

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:

Static Character Features (Vill, Sablatnig 2008) Number Feature Name Feature 1 Number of static strokes Feature 2 Number of nodes Feature 3 Number of straight static strokes Feature 4 Number of bent static strokes Feature 5 Number of vertical static strokes Feature 6 Number of horizontal static strokes Feature 7 Number of loops Feature 8 Number of open ends Feature 9 Number of closed elements

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

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.

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 and 0.17 for the calligrapher’s data set.

Static Character Feature Calculation

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

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

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

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)

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.

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.