Sequence to Sequence Learning for Optical Character Recognition

Introduction

Deep Neural Nets (dnns) have become present day de-facto standard for any modern machine learning task. The flexibility and power of such structures have made them outperform other methods in solving some really complex problems of speech [Hinton et al. (2012)] and object [Krizhevsky et al. (2012)] recognition. We exploit the power of such structures in an ocr based application for word prediction and retrieval with a single model. Optical character recognition (ocr) is the task of converting images of typed, handwritten or printed text into machine-encoded text. It is a method of digitizing printed texts so that it can be electronically edited, searched, stored more compactly, displayed on-line and used in machine processes such as machine translation, text-to-speech and text mining.

From character recognition to word prediction, ocrs in recent years have gained much awaited traction in mainstream applications. With its usage spanning across handwriting recognition, print text identification, language identification etc. ocrs have humongous untapped potential. In our present work we show an end-to-end, deep neural net, based architecture for word prediction and retrieval. We conceptualize the problem as that of a sequence to sequence learning and use rnn based architecture to first encode input to a fixed dimension feature and later decode it to variable length output. Recurrent Neural Networks (rnn) architecture has an innate ability to learn data with sequential or temporal structure. This makes them suitable for our application. Encoder lstm network reads the input sequence one step at a time and converts it to an expressive fixed-dimensional vector representation. Decoder lstm network in turn converts this fixed-dimensional vector (Figure 1(b)) to the text output.

Encoder-Decoder framework has been applied to many applications recently. [Sutskever et al. (2011)] used recurrent encoder-decoder for character-level language modelling task where they predict the next character given the past predictions. It has also been used for language translation [Sutskever et al. (2014)] where a complete sentence is given as input in one language and the decoder predicts a complete sentence in another language. Vinyals et al. [Vinyals et al. (2014)] presented a model based on a deep recurrent architecture to generate natural sentences describing an image. They used a convolutional neural network as encoder and a recurrent decoder to describe images in natural language. Zaremba et al. [Zaremba & Sutskever (2014)] used sequence to sequence learning for evaluating short computer programs, a domain that have been seen as too complex in past. Vinyals et al. [Vinyals & Le (2015)] proposed neural conversational networks based of sequence to sequence learning framework which converses by predicting the next sentence given the previous sentence(s) in a conversation. In the same spirit as Vinyals et al. (2014); Sutskever et al. (2014), we formulate the ocr problem as a sequence to sequence mapping problem to convert an input (text) image to its corresponding text.

In this paper, we investigate the expressiveness and learnability of lstms in sequence to sequence learning regime for printed text ocr. We demonstrate that sequence to sequence learning is suitable for word prediction task in a segmentation free setting. We even show the expressiveness of the learnt deep word image embeddings (from Encoder network of prediction) on image retrieval task. In (majority of) cases where standard lstm models do not convert a variable length input to a fixed dimensional output, we are required to use Dynamic Time Warping (dtw) for retrieval which tends to be computationally expensive and slow. Converting variable length samples to fixed dimensional representation gives us access to fast and efficient methods for retrieval in fixed dimensional regime –- approximate nearest neighbour.

Sequence learning

A recurrent neural network (rnn) is a neural network with cyclic connections between its units. These cycles create a concept of ‘internal memory’ in network and thus differentiate rnns from other feed forward networks. The internal memory of rnn can be used to process arbitrary sequences of inputs – given a variable length input sequence $X$ we can generate corresponding variable length output sequence $Y$. This is done by sequentially reading each time-step $x_{t}$ of input sequence $X$ and updating its internal hidden representations $h_{t}$. More sophisticated recurrent activation functions like lstm [Hochreiter & Schmidhuber (1997)] and gru [Cho et al. (2014); Chung et al. (2014)] have become more common in recent days. They perform better when compared to other vanilla rnn implementations.

Long Short-Term Memory [Hochreiter & Schmidhuber (1997)] is a rnn architecture that elegantly addresses the vanishing gradients problem using ‘memory units’. These linear units have a pair of auxiliary ‘gating units’ that control the flow of information to and from the unit. Equations 1-5 describe lstm blocks.

Here, $W_{xi},W_{hi},w_{ci},b_{i}$ are input gate parameters. $W_{xo},W_{ho},w_{co},b_{o}$ are output gate parameters. $W_{xf},W_{hf},w_{cf},b_{f}$ are forget gate parameters. $W_{xc},W_{hc},b_{c}$ are parameters associated with input which directly modify the memory cells. The symbol $\odot$ denotes element-wise multiplication. The gating units are implemented by multiplication, so it is natural to restrict their domain to $^{N}$, which corresponds to the sigmoid non-linearity. The other units do not have this restriction, so the tanh non-linearity is more appropriate. We use collection of such units (Figure 1(a)) to describe an encoder-decoder framework for the ocr task. We formulate the task of ocr prediction as a mapping problem between structured input (image) and structured output (text).

To describe the formulation we use vanilla rnns with $L$ hidden layer and no output layer. The encoder reads $I_{i}=\{x_{1},x_{2},...,x_{T_{i}}\}$ one step at a time from $x_{1}$ to $x_{T_{i}}$. Hidden state $h^{n}_{t}$ is updated using equations 8-9 using current input $x_{t}$ and previous hidden state $\{h^{n}_{t-1}\}_{n=1}^{L}$ where $L$ is the number of hidden layers in rnn.

where $W_{ih^{1}},W_{h^{1}h^{1}},b_{h}^{1},W_{ih^{n}},W_{h^{n-1}h^{n}},W_{h^{n}h^{n}},b_{h}^{n}$ are parameters to be learned.

To obtain our fixed dimensional latent representation $z_{i}$ we use the final hidden states $\{h^{n}_{T_{i}}\}_{n=1}^{L}$.

It should be noted that we have used lstm networks instead of vanilla rnns and no output layer for encoder is needed. The hidden states of last step $T_{i}$ are used as initial state of decoder network.

2 Decoder: lstm based Word Predictor

Similar to encoder, we describe the idea using vanilla rnns with $L$ hidden layers and softmax output layer. The goal of word predictor is to estimate the conditional probability $p(Y_{i}|I_{i})$ as shown in equation 11-12, where $I_{i}$ is image input sequence and $Y_{i}$ is output sequence.

The updates for single step for rnn is described in equations 13-16. The hidden state $h^{n}_{t}$ is updated using equations 13 - 14 using current input $x_{t}$ and previous hidden state $\{h^{n}_{t-1}\}_{n=1}^{L}$, where $L$ is number of hidden layers in rnn. The hidden activations, $h^{L}_{t-1}$ are used to predict the output at step $t$ using equations 15-16. $x_{t}$ is the embedding of the most probable state in previous step $t-1$ shown in equation 18.

where $W_{ih^{1}},W_{h^{1}h^{1}},b_{h}^{1},W_{ih^{n}},W_{h^{n-1}h^{n}},W_{h^{n}h^{n}},b_{h}^{n},W_{h^{L}o},b_{o}$ are parameters to be learned.

$W_{e}$ in equation 18 is the embedding matrix for characters. It should be (again) noted that we use lstm networks (equations 1 - 5) instead of vanilla rnns (equations 13, 14).

3 Training

The model described in section 2.1 and 2.2 is trained to predict characters of the input word (image) sequence. The input at time $t$ of decoder is an embedding of the output of time $t-1$. The loss $L$ for a sample $(I,Y)$ is described by equation 20.

Implementation Details

Keeping the aspect ratio of input images intact we resize them to height of $30$ pixels. The resized binary images are then used as an input to the two layer lstm encoder-decoder architecture. We use embedding size of $25$ for all our experiments. The dimensionality of output layer in decoder is equal to number of unique symbols in the dataset. rms prop [Tieleman & Hinton (2012)] with step size of $0.0001$ and momentum of $0.99$ is used to optimize the loss. All relevant parameters are verified and set using a validation set. We use Python’s numpy library to implement lstm based architecture. The network is built using computational graphs.

Experiments

We demonstrate the utility of the proposed recurrent encoder-decoder framework by two related but independent tasks. Independent baselines are set for both prediction and retrieval experiments.

Prediction: We use $295$K annotated English word images from seven books for our experiments. We perform three way data split for all our experiments – 60% training, 20% validation and remaining 20% for testing. Results are reported by computing ‘label error rate’. Label error rate is defined as ratio of sum of insertions, deletions and substitutions relative to length of ground truth over dataset. We compare the results of our pipeline with state-of-art lstm-ctc [Graves et al. (2006)], an open-source ocr tesseract [tes ] and a commercial ocr abbyy [abb ].

Retrieval: We use $108$K annotated word images from book titled ‘Adventures of Sherlock Holmes’ for retrieval experiments. In all $43$K word images are used for querying the retrieval system. We compare retrieval results with SIFT [Lowe (2004)] based bag of words representation, augmented profiles [Kumar et al. (2007)] and commercial [ocr abbyy].

Table 2 exhibits prediction baseline. We observe that lstm Encoder-Decoder outperforms vanilla rnn Encoder-Decoder by significant margin. It even scores better when compared to lstm with ctc output layer and abbyy. When compared to ctc layer based lstm networks, our network requires more memory space. The strength of our network is fixed length representation for variable length input which enables us to perform better and faster retrieval.

Table 1 depicts retrieval baseline. Features from lstm encoder (referred as deep word image embedding (dwie)) are used for comparisons with other state-of-art results. We observe that dwie features significantly outperform sift [Lowe (2004)] based bag of words (bow) and augmented profiles [Kumar et al. (2007)]. When compared to abbyy, dwie features perform a notch better for top $5000$ retrieval but perform similar for top $100$ retrieval. The memory states at last position of each sequence are used as dwie features. Various normalization (L1 and L2) and augmentations with hidden states were tried out as shown in Table 2.

Table 3 demonstrates the qualitative performance of retrieval system using both deep word image embedding (dwie) and bag of words (bow) models. The table illustrates top $20$ retrievals using both the methods. We observe the proposed embeddings to be better than naive (bow) in such settings. In majority of the cases we find all relevant(exact) matches at top in case of deep embeddings, which is not the case with (bow) model. dwie seems highly sensitive to small images components like ‘.’ (for query ‘A.’) which is not the case with bow model. Simple bow fails to recover any relevant samples for query ‘A.’ in top $20$ retrievals.

Figure 2 shows t-sne [van der Maaten & Hinton (2008)] plots of word image encodings. We show two levels of visualization along with groupings in context of word image representation. It’s clear from the figure 2(a) that representation is dominated by first character of the word in word image. Sequence of correct encodings play a major role in full word prediction – a wrong letter prediction in early stages would result in overall invalid word prediction.

Figure 3(a) is a plot of learnt embeddings which shows relative similarities of characters. The similarities are both due to structure and language of characters – (i) all the numbers (0-9) are clustered together (ii) punctuations are clustered at top right of graph (iii) upper case and lower case characters tend to cluster together, viz. (m,M), (v,V), (a,A) etc. As embeddings are learnt jointly while minimizing cost for correct predictions, they tend to show relative similarity among nearby characters based jointly on structure in image space and language in output space. Figure 4 illustrates training label error rate for various learning models – lstm with ctc output layer and lstm encoder-decoder.

Conclusion

We demonstrate the applicability of sequence to sequence learning for word prediction in printed text ocr. Fixed length representation for variable length input using a recurrent encoder-decoder architecture sets us apart from present day state of the art algorithms. We believe with enough memory space availability, sequence to sequence regime could be a better and efficient alternative for ctc based networks. The network could well be extended for other deep recurrent architectures with variable length inputs, e.g. attention based model to describe the image contents etc.

References