A biologically inspired approach for recovering the trajectory of offline handwriting

Abstract

Reconstructing the trajectory from the static image of handwritten ink traces is useful in many practical applications envisaging handwriting analysis and recognition from offline data, as it allows the use of methods, algorithms, and tools that deal with online data, achieving better results than those achieved on offline data. In this work, the trajectory recovery is addressed by combining a general graph traversal algorithm with knowledge about the processes involved in human learning of motor skills to perform voluntary and complex movements. The effectiveness of the proposed approach has been quantitatively and extensively evaluated on large and publicly available datasets, containing English and French multi-stroke words and isolated characters. The experimental results show that our approach outperforms the existing ones in terms of Root Mean Square Error and Dynamic Time Warping distance between the recovered trajectories and the actual ones. Furthermore, an “off-the-shelf” online recognition system provided with the trajectory recovered from offline samples showed an overall reduction of 6.8% with respect to the recognition rate achieved by the system when provided with online data; the reduction, however, drops to 2.4% once preprocessing errors are not taken into account.

Appendix

1.1 Distortion correction

As spurious branches are associated with small protrusions appearing on the trace main body, and considering that our approach is dealing with ribbons, i.e., objects whose local thickness is much smaller than the length, the length and the local thickness at the tip (of the spurious branches) are expected to be smaller than the local thickness (T) of the ink trace in correspondence of the protrusion. Considering the ratio $\rho$ between the difference $\Delta = T_{BP}-T_{EP}$ and the length L of the branch, $\rho = 0$ for a branch whose local thickness at the tip of the protrusion is the same as the local thickness of the trace and therefore, cannot be considered as representing a protrusion. On the other hand, a protrusion made by just one pixel would generate a branch for whom $\Delta = T_{BP}-1$ and $L = T_{BP}+1$, so that $\rho \ge 0.5$, and becomes larger and larger as $T_{BP}$ becomes bigger. Consequently, the skeleton branches starting from a BP and ending in an EP, for whom $\rho \ge 0.5$ are considered spurious branches, and removed from the skeleton.

Before distortion correction, a polygonal approximation of each skeletal branch is performed through a split-and-merge algorithm, wherein the vertices of the polyline are constrained to be the extremes of the sequences of collinear pixels (i.e. pixels aligned along the same rectilinear line). They must include the EPs and the BPs of the skeleton.

In order to illustrate the criteria to eliminate the distortions introduced by the skeletonization process, three types of distortions, called V-shape, T-shape, and X-shape, can be distinguished, as shown in Fig. 13.

Fig. 13

Distortions of the ink trace skeleton and their correction. External contours represent the original ink trace

A V-shape distortion occurs when the ink trace presents a sharp curve. In such a case, the polyline of the trace is that of Fig. 13A because of the triangular shape of the ink trace in correspondence with the sharp curve. Such distortions, thus, can be identified by analyzing the polyline segments joining in a BP that connects three segments. If the following conditions hold:

• 1. one of the segments is delimited by an EP;

• 2. the thickness at the BP is bigger than that of the EP;

• 3. the angles $\alpha _1$ and $\alpha _2$ between the segment delimited by the EP and the two other segments joining in the BP have similar amplitude, that is $|\alpha _1-\alpha _2 |\le \theta _1$;

the spurious segment between the BP and EP is removed, and the two segments are connected so that they join in the EP, as represented by the dotted lines in Fig. 13A.

A T-shape distortion occurs when two parts of ink trace touch each other producing a T-shaped pattern. In these cases, the polyline of the touching region is shown in Fig. 13B: it presents three segments joining in a BP whose corresponding ink thickness is bigger than those at the other vertices of the segments connected to the BP, and the segments of the part of ink trace that can be interpreted as the top bar of the T bends toward the vertical bar instead of being parallel to the contour of the top bar. In Fig. 13B, the distorted segments are represented by the continuous lines starting from BP and ending in $V_1$, $V_2$, and $V_3$. The point BP’ is the intersection point between the line connecting $V_1$ and $V_2$ and the line obtained by extending the segments ending in $V_3$, $\alpha$ is the angle measured at the intersection obtained by extending the segments passing from $V_1$ and $V_2$, and d is the distance between BP and BP’. These distortions are characterized by the following conditions:

• 1. the ink thickness at the BP is bigger than that of both the vertices $V_1$ and $V_2$;

• 2. the segments connecting $V_1$ and $V_2$ with BP form a smooth curve, that is $\alpha \ge \theta _2$;

• 3. the branch point $BP'$ is centrally located within the part of the trace corresponding to the top bar, that is $d<T_{BP}$;

When the previous conditions hold, the branch point BP is replaced by BP’, and the segments starting from $V_1$, $V_2$, and $V_3$ are connected at BP’, as represented by the dotted lines in Fig. 13B.

An X-shape distortion occurs when two parts of the ink trace cross each other. In this case, the polyline of the crossing region presents five segments that connect in two BPs, instead of four segments joining in a single BP, as expected (Fig. 13C). These distortions are detected by considering each pair of BPs connected by a segment of the polyline, from each of which three rectilinear segments start. If the following conditions hold:

• 1. the ink thickness at the $BP_i$ is bigger than those at the vertices $V_{ij}$;

• 2. the segments connecting $V_{ij}$ with $BP_i$ do not form a smooth curve, that is $\alpha _i \le \theta _3$;

the five segments are replaced by four segments, connecting the vertices $V_{ij}$ with the new branch points $BP'$, which is located at the intersection between the segments connecting the vertices $V_{11}$ with $V_{22}$ and $V_{12}$ with $V_{21}$, as represented by the dotted lines in Fig. 13C.

1.2 Starting/ending points selection

These criteria depend on whether or not the graph contains only one type of node or any combination of them, and in the former case, from their type:

• 1. the graph contains only even degree BPs. The leftmost BP is selected as the source node, and the rightmost BP is selected as the destination node. An example of this condition is represented by the shape of the digit ‘8’.

• 2. the graph contains only two odd nodes and any number of even degree nodes. According to the orientation of the connected component represented by the graph (horizontally or vertically extended) and the distance (horizontal or vertical, respectively) between the nodes, the leftmost or the uppermost one is selected as the source, and the rightmost or the lowermost as the destination, as depicted in the flowchart of Fig. 14.

• 3. the graph contains more than two odd nodes and any number of even nodes. Source and destination nodes are selected according to the flowchart reported in Fig. 15. The source/destination node is selected among the two leftmost/rightmost odd nodes of the graph depending on the type of both the candidate node (EP or BP) and the nodes connected to it. In particular, the function selectSrc(NodeSet) selects as the source node the leftmost or the uppermost among those belonging to the NodeSet depending on the orientation of the component, as in the previous case. Similarly, the function selectDst(NodeSet) selects as the destination node the rightmost or the lowermost among those belonging to the NodeSet.

A particular case occurs when the ink trace contains only normal points, as it happens with a skeleton of a trace representing a closed loop, as it may happen in the case of an isolated letter o. In this case, the top-left polygonal approximation point is selected as both source and destination node and the corresponding graph degenerates into a single node.

Fig. 14

Source and destination nodes selection: criteria for graphs containing only two odd nodes and any number of even degree nodes. Circles indicate the source/destination nodes and squares indicate even degree nodes. Grey lines represent the center zone of the handwritten sample

Fig. 15

Source and destination nodes selection: Criteria for graphs containing more than two odd nodes and any number of even degree nodes. Circles indicate the nodes selected as source and destination according to the criteria, squares indicate even nodes, and stars indicate odd nodes. Grey lines represent the center zone of the handwritten sample

1.3 Chinese arcs insertion

Starting from the set of odd degree nodes, the leftmost node $n_i$ is chosen (in case two nodes are located at the same horizontal coordinate, the uppermost is chosen):

• If $n_i$ is an EP, a Chinese arc to the leftmost odd node $n_{i+1}$ is added. This criterion arises from the considerations that handwriting is performed from the left to the right and that an EP usually represents either a point from which a retracing movement is started or a point where the pen tip is lifted from the paper.

• If $n_i$ is a BP, among the odd nodes connected to it through a “loop” or a “bridge” is not considered for being further connected. This criterion follows from the particular topology of loops and bridges. Here a “loop” is a path that starts and ends in the same BP (f.i., the upper part of the trajectory of the letter and ), and as “bridge” an arc whose removal disconnects the graph (f.i., the ligature between two characters). Being very unlikely that a loop or a bridge be drawn twice when writing the word, the presence of a retracing involving these two types of branches is excluded. Once the odd nodes connected through loops or bridges were excluded from being further connected, three cases can be observed:

  • no already connected nodes are available for being connected: a pen-up is added between the node $n_i$ and the leftmost unconnected odd node $n_{i+1}$;

  • only one connected node is available: it is connected to $n_i$ with a retracing arc;

  • two or more odd nodes already connected are available for being connected: if there are EPs, the closest EP is connected to $n_i$, otherwise the closest BP is chosen, and in both cases, a retracing arc is added.

This procedure is performed until all the odd nodes are connected and transformed into even ones, and the graph becomes semi-Eulerian.

1.4 Changes in the estimated trajectory according to the estimated energy

Fig. 16

Selection of the alternative starting point of the trajectory, according to the info carried by the energy vector and the value of the energy score

Fig. 17

Selection of the alternative ending point of the trajectory, according to the info carried by the energy vector and the value of the energy score

Fig. 18

Changes of the additional arcs for constructing the semi-Eulerian graph according to the info carried by the energy vector

Fig. 19

Changes of the traverse path according to the info carried by the energy vector

An estimated trajectory is changed according to the following steps:

• 1. the energy vector is analyzed in search of a non-zero value in correspondence of the EP or BP that is the starting point of the trajectory. If such an element is found and there are alternative nodes to be considered as source nodes, the current source node is removed from the possible candidates, and a new source node is selected, as described in the paragraph 2.2, a new trajectory is generated by the unfolding module, segmented in strokes and its energy consumption is estimated by computing the energy score. Eventually, between the two trajectories, the one with the lowest energy score is selected for the next step, as illustrated in Fig. 16;

• 2. the energy vector of the selected trajectory is analyzed in search of a non-zero value in correspondence of the EP or BP that is the ending point of the trajectory. If such an element is found and there are alternative nodes to be considered as destination nodes, the current destination node is removed from the possible candidates, a new destination node is selected as described in the paragraph 2.2, a new trajectory is generated, and its energy consumption is estimated, as illustrated in Fig. 17. As in the previous case, the trajectory with the lowest energy score is selected for the next step;

• 3. if the selected trajectory contains additional arcs and non-zero values are found in correspondence with the EP/BP representing the starting/ending of the additional arc, the additional arc is removed, and other possible combinations for connecting odd nodes are evaluated following the procedure for building the semi-Eulerian graph described in the paragraph 2.2, a new trajectory is generated and its energy consumption estimated, as illustrated in Fig. 18. This step is iterated until a trajectory is generated whose energy vector elements corresponding to the starting/ending points of the additional arcs are equal to zero, or all alternative additional arcs have been evaluated. Therefore, the step is repeated at most $n_{IT}$ times, where $n_{IT}$ depends on the number of odd nodes n to be connected:

  $$\begin{aligned} n_{IT}= \prod _{i=0}^{\frac{n}{2}-1} (n-2i-1) \end{aligned}$$

  Among the set of estimated trajectories, the one with the lowest energy score is selected for the last step;

• 4. the energy vector is analyzed in search of the non-zero value in correspondence of BPs that are not the starting/ending point of the trajectory, and if such elements are found, for each BP another possible choice of coupling the arcs connected to it is made, a new trajectory is generated and its energy consumption evaluated, as illustrated in Fig. 19. This step is iterated until a trajectory is generated, whose energy vector elements corresponding to the BPs that are neither starting nor ending points are equal to zero, which therefore represents the desired one, or all alternative couplings of the arcs connected to the BP have been evaluated. As at each step an alternative is evaluated for each BP, the step is repeated at most $n-1$ times, where n is the largest degree of the BPs under investigation. Among the set of estimated trajectories, the one with the lowest energy score is selected as the final one.