We present the results and analysis of our chemical structure recognition system, MolRec, in the CLEF 2012 chemical structure recognition task. MolRec analyses a diagram image, extracts vectorised components from the image and applies a rule based system to construct an internal representation of the chemical structure. This internal representation can then be exported to MOL or SMILE format. The task assigned in CLEF was to analyse two sets of chemical diagram images clipped from patent documents. The rst set is of 965 diagram images, the results of which could be evaluated automatically using OpenBabel. The second set is a more challenging collection of 95 images which include elements not supported by OpenBabel and which therefore have to be evaluated manually. On the rst set, MolRec achieved recognition rates of between 94.91% and 96.18% over 4 runs with slightly di erent parameters. On the more exacting second set, MolRec's recognition rate was between 46.32% and 58.95%. Overall the results testi ed to high performance on a large sample of quite complex diagrams but also to the challenges posed by the more di cult images that appear in real patent documents.
We present the recognition results of our MolRec system on the CLEF 2012 corpus of chemical molecule diagrams. MolRec is a rule based system, in that after an initial preprocessing phase, the primary recognition task is performed by a rule engine, in which largely disjoint rules are repeatedly applied to an initial set of geometric primitives, thereby rewriting the set into a graph representation of the given molecule diagram. This nal graph structure then serves as a basis from which other e cient electronic representation formats, such as MOL les, can be generated.
A previous implementation of the system has already performed well in the
TREC 2011 competition [
In this note we will rst give a short overview of the system, detailing its
overall structure and brie y summarising the rewriting rules that perform the
primary recognition (Sec. 2). For a more detailed overview we refer the reader
to [
MolRec employs a rule-based approach for the recognition of chemical
structure diagrams. It consists of two modules, a vectoriser and a rule-engine. The
vectoriser preprocesses an input image, analyses the chemical structure diagram
it represents and generates a set of geometric primitives. These primitives are
then picked up by the rule engine which rewrites them into a graph structure
representation of the recognised molecule. In a post-processing step this graph
structure can then be translated into a variety of output formats such as MOL
les [
2. Optical character recognition (OCR)
3. Separation of bond elements
Binarisation For the rst step of image binarisation we use Otsu's method [
OCR In a second step optical character recognition is performed by extracting a set of structural features from connected components and applying a nearest neighbour classi cation based on a Euclidean metric.
All connected components recognised as characters are removed from the image. Some contextual information is used to disambiguate di cult cases. For example, the lower case, sans serif letter \l" is often visually indistinguishable from short line segments in a molecule diagram, but in all examples we have come across, it does not appear except beside other letters (usually after a capital \C", to denote a Chlorine atom).
The result of this step is a skeleton molecule with all detected characters removed.
Separation of Bond Elements At this point we produce a new copy of the (character free) diagram and apply a thinning algorithm to connected components to thin them to a single pixel width. Using the thinned lines as a guide, we walk the corresponding paths in the original image to determine the average line width by nding the largest disk that ts wholly with the stroke width of the line. At the same time, we build a polyline representation of the thinned lines. At every junction where three or more polylines meet, we split them into separate polylines. Closed polylines are also identi ed.
Because of scanning, discretisation and thinning artifacts, these polylines
are not, as we would like, smooth idealised representations of the lines in the
original diagram. Therefore we clean them up by applying the Douglas-Peucker
line simpli cation algorithm [
In addition to detecting and separating polylines we also detect circles as well as lines with arrows heads and solid triangles. The latter two are then annotated with their respective direction. 2.2
The rule engine essentially works with the geometric primitives resulting from the vectorisation. In particular it uses character groups from the OCR step, as well as line segments, circles, solid triangles and arrows from the bond separation. The goal of the rule engine is to rewrite the input set of primitives into a graph structure that represents the molecule in terms of the atoms (or superatoms) and di erent types of bonds between them.
Rule are de ned in terms of preconditions and consequences. A rule is
applicable if there exist geometric objects that satis es its preconditions. The
consequence results in the removal of existing geometric objects and the addition of
elements to the graph as well as possibly the addition of new geometric objects.
In general, preconditions of di erent rules are mutually exclusive, and thus the
order of rule application is irrelevant. Rules work with a number of parameters,
both fuzzy and strict, that set certain thresholds, for instance the minimal bond
length, under which decisions will be made. These parameters allow for the
customisation of MolRec and its adaptation to particular requirements of datasets.
In this section we will only brie y summarise the main rules and present an
example. For more details we refer the reader to [
The rule engine consists of 18 rules altogether. Two of these rules have to be applied before all other rules. These two rules deal with the recognition of bridge bonds, 3-dimensional structures representing multiple di erent connection paths between di erent parts of the molecule. These are typically presented in a 21=2dimensional perspective drawing form such as in Fig. 1.
The other 16 rules can be applied in arbitrary order. They deal with the recognition of a number of other bonds that MolRec can handle and that are presented in Fig. 2. All these bonds consist of one or several geometric objects, which a rule can select using its preconditions and rewrite into a corresponding graph entry for the recognised bond type.
(b) Closed-bridge
However, there are also single geometric objects that possibly represent more than one bond. An example are so called implicit nodes presented in Fig. 3. Here carbon atoms are understood to be at the grey circled areas separating the bonds. These cases are dealt with by rules that pick double or triple bonds, respectively, while also producing new geometric objects by e ectively cutting the bonds at the implicit nodes. These new objects can then be further processed by other rules.
Not all decisions on bond types can be made by inspecting locally a number of geometric objects only. Consequently some rules mark some of their results as possibly ambiguous. These ambiguities have to be resolved taking context information into account. This is done after all geometric objects have been rewritten within the context of the resulting graph. Furthermore, at this stage MolRec also adds the character groups to the graph, which can be used as further aid for disambiguation. For example, disambiguation of lower case \l", capital case \I", the digit \1" and a vertical single bond is carried out at this stage. In addition character groups identifying more than one atom are identi ed as superatoms. Their structure is looked up in a dictionary and the character group is replaced with the molecule subgraph corresponding to that superatom. An Example Rule - Wavy Bond Wavy bonds (Figure 2(j)) are commonly used in chemical structure diagrams. As the name suggests, they have a wavy form although a less commonly used saw-tooth form can be encountered in the literature.
A vectorisation process will most likely turn a wavy bond into a connected sequence of short line segments arranged in a saw-tooth, or a zig-zag, pattern. As illustrated in Figure 4, a straight line can pass through the centre points of these line segments. A pattern of this form can be identi ed using the following conditions. 1. L = fl1; : : : ; lng, where n 3, is a set of line segments, 2. 8l 2 L : length(l) 2 dl , where dl is the dash length: a parameter of the system representing a range of acceptable values for the length of an individual dash in a dashed line. 3. All elements of L are connected. 4. The centre points of the elements of L are approximately collinear.1 5. Two elements of L, called the end elements, dash-neighbour2 precisely one other element of L. All other elements of L, called internal elements, dashneighbour precisely two other elements of L. 6. Two end points that are not connected must be the pair of end points that are furthest apart.
Consequence A wavy bond between the furthest two endpoints. The new wavy bond has unknown direction.
To understand this rule, note that condition 1 simply selects possible line segments, such as those from Figure 4, for consideration. Condition 2 ensures that each segment is of an appropriate length. That the endpoints of the line segments are connected is guaranteed by condition 3. The approximate collinearity of their centre points in condition 4 ensures that this sequence of line segments, although having a zig-zag form at the micro-structure level, is straight at a macro-structure level. Finally, the last two conditions ensures that the segments form a single sequence as would be obtained from a wavy bond, and not, for example, from any 1 Approximate collinearity is a precisely de ned relationship under which a set of points can be considered to be collinear within the constraints of the limitations of the construction, printing and scanning technologies used for the image. 2 Dash neighbouring is a precisely de ned relationship which specify the conditions under which two line segments can be considered to be consecutive dashes in a dashed line. kind of star structure with multiple end points. The consequence merely identi es the structure as a wavy bond between the end points and leaves undecided the directionality of the bond. 3
We were given a set of 961 test images by CLEF12's organisers. This collection
was split into two sets. The rst set was of 865 images selected for automatic
evaluation by comparison of generated MOL les with the ground truth MOL
les using the OpenBabel toolkit[
We ran MolRec four times on these sets where we slightly adjusted its internal parameters and MolRec achieved the results illustrated in Table 1 and Table 2. The two tables show the number of correct and incorrect recognitions for the four runs on the manual and automatic evaluation sets respectively. Notice that because most of the diagrams mis-recognised in some runs were also mis-recognised in other runs, there were a total of 52 di erent diagrams mis-recognised in the manual evaluation set and a total of 46 di erent diagrams mis-recognised in the automatic evaluation set. Some of these diagrams failed for multiple reasons, so we were able to identify the reasons illustrated in Table 3.
Run # Recognitions
# Mis-Recognitions Accuracy
We now brie y discuss some of the problems that have lead to MolRec misrecognising molecule diagrams in the test set. 4.1
An error in the implementation of our character group formation algorithm lead to the digit \1" being repeated when it appears within a atom group, so, for example, MolRec recognised R21 incorrectly as R211. A separate problem was the di culty in correctly separating di erent atom groups which are closely spaced, as shown in Figure 5. 4.2
We currently do not handle touching characters and therefore they will likely cause mis-recognition. Figure 6 shows several examples. Vectorising junctions where four lines meet was another reason for recognition failure. Two examples are given in Figure 7. MolRec misses such junctions. There were some cases of OCR errors. These included a \G" interpreted as an \O", and the \alkyl" atom (Figure 8(a)) being mis-recognised. Also, as illustrated in Figure 8(b), there was several cases where an \I" was interpreted as a vertical single bond. 4.5
As shown in Figure 9, MolRec incorrectly recognised a number of solid wedge, dashed wedge and wavy bonds.
Fig. 9. Examples of Missed Solid Wedge, Dashed Wedge and Wavy Bonds 4.6
The plus and minus signs, or \+" and \-", are often used to indicate the existence of positive and negative charges respectively. As shown in Figure 10, they are usually placed to the top right of an atom. While correctly recognising the positive charge sign, MolRec missed three negative charge signs including one that was placed at the top left of an atom name. These include an atom that was too close to a bond's endpoint and which was therefore erroneously considered connected (Figure 11(a)), a solid wedge bond that was too close to a closed node so they were considered connected (Figure 11(b)) and a dashed bold bond whose stereocentre was incorrectly determined (Figure 11(c)). While analysing our results we came across a small number of cases where the ground truth was incorrect and our recognition was correct. As shown in Table 4, there were 11 images in total. Such ground truth dataset errors are very di cult to avoid in such a complex task. Despite scoring high recognition rates throughout four runs, the presented experiments demonstrate that there is still plenty of room to improve MolRec. We believe many of the mis-recognition problems can be solved with some relatively simple enhancements of our system, e.g. the error in character grouping or the vectorisation of four-way junctions. Tackling the notoriously di cult touching character segmentation problem is one aspect where we plan to explore viable solutions. Another area we plan to investigate is the recognition of more general Markush structures. Additionally, robust charge sign spotting, accurate identication of solid wedge bonds and precise identi cation of dashed wedge bonds are also areas we need to address further. However, we are pleased with the performance of MolRec and hope to participate in similar events in the future so that we can contribute to progress in the state of the art of chemical structure diagrams.