2 Rule trees.

2.1 Rule trees for handwritten documents.

Since a rule tree may be used to represent information associated with either a set of objects (for a layout model) or a set of labels (for a labelling model), in the discussion which follows we use a more generic term, ``item'', to mean either a label or an object.

A rule tree allows a single tree structure to encapsulate the constraints which we associate with a set of items. Constraints concerning the nesting of items are maintained implicitly by the tree's hierarchical structure, and inter-item constraints are specified by utilising operators. These identify different classes of constraints which are appropriate to each particular domain of computer vision. In the domain of documents, operators derived from the Office Document Architecture (ODA) [ 2 ] representational model are appropriate as follows:

An additional operator, ACC, is provided as a convenience to enable more concise labelling model rule trees to be produced. The ACC operator defines an ACCumulation of in-SEQuence items. More formally, if items are attached to an ACC operator, then the constraint enforced is as follows: item may occur, or , items and may occur in SEQuence, or , items may occur in SEQuence, or , items may occur in SEQuence.

When a rule tree is used to represent a labelling model, all of the above operators may be used. When a rule tree is used to represent a layout model, only the SEQuence operator is used, since the model is generated entirely by simple image analysis. Image analysis should be capable of detecting the nesting of items, and their raster-order (SEQuence) but won't detect any of the optionality which is associated with the other operators.

Within the domain of hand-printed forms only layout and occurence constraints are used to guide labelling. In other application domains, for example, object tracking, constraints based on other features such as motion, colour, or occlusion may be more appropriate. A wide range of constraints can be used to guide the labelling process by defining suitable operators and providing the feature detection to enhance the information contained within layout models.

2.2 Example application of rule trees.

Figure  1(a) shows an example form image which we wish to process. Figure  1(b) shows the same image with its background removed. The results of using a simple binary connected components analysis algorithm to locate the hand-printed characters are shown in figure  1(c) . Finally, figure  1(d) shows the results of heuristically merging the connected components into words, and figure  3 (A) shows the layout model which has been automatically generated from some simple analysis of the results shown in figures  1(c) and   1(d) .

           
Figure 1: Image analysis applied to a simple form.

Whilst the layout model is generated automatically by image analysis, corresponding labelling models are produced manually. The rule tree for a simple labelling model for form images of the class shown in figure  1(a) is shown in figure  2 . In this labelling model, the following major constraints are represented: both ``firstname'' and ``surname'' consist of between one and ten characters; both ``day'' and ``month'' consist of either one or two characters; ``year'' consists of either two or four characters; and, finally, a ``simpleform'' contains a ``firstname'' and ``surname'' in any order, followed by an optional sequence of ``day'', ``month'', and ``year''.

If we attempt, manually, to label the items in the layout model according to the labelling scheme shown, then it is necessary to hypothesise two labellings (since the layout model is within the constraints associated with two of the possible labellings which are encoded within the labelling model). The two labellings which may be hypothesised for the layout model shown are illustrated in figure  3 (B and C).

   
Figure 2: A simple labelling model.

   
Figure 3: Layout models. (A) shows the layout model without any assigned labels. (B) and (C) show two different hypothesised labellings. Differences between (B) and (C) are highlighted with an asterisk.