I'm looking to do an optical character recognition (OCR) project. After doing some research I've come across an architecture that seems interesting: CNN+RNN+CTC. I'm familiar with convoluted neural networks (CNN), and recurrent neural networks (RNN), but what is Connectionist Temporal Classification (CTC)? I'd like an explanation in layman's terms.
You have a dataset containing:
- images I1, I2, ...
- ground truth texts T1, T2, ... for the images I1, I2, ...
So your dataset could look something like that:
A Neural Network (NN) outputs a score for each possible horizontal position (often called time-step t in the literature) of the image. This looks something like this for a image with width 2 (t0, t1) and 2 possible characters ("a", "b"):
| t0 | t1
a | 0.1 | 0.6
b | 0.9 | 0.4
To train such a NN, you must specify for each image where a character of the ground truth text is positioned in the image. As an example, think of an image containing the text "Hello". You must now specify where the "H" starts and ends (e.g. "H" starts at the 10th pixel and goes until the 25th pixel). The same for "e", "l, ... That sounds boring and is a hard work for large datasets.
Even if you managed to annotate a complete dataset in this way, there is another problem. The NN outputs the scores for each character at each time-step, see the table I've shown above for a toy example. We could now take the most likely character per time-step, this is "b" and "a" in the toy example. Now think of a larger text, e.g. "Hello". If the writer has a writing style which uses much space in horizontal position, each character would occupy multiple time-steps. Taking the most probable character per time-step, this could give us a text like "HHHHHHHHeeeellllllllloooo". How should we transform this text into the correct output? Remove each duplicate character? This yields "Helo", which is not correct. So, we would need some clever postprocessing.
CTC solves both problems:
- you can train the network from pairs (I, T) without having to specify at which position a character occurs using the CTC loss
- you don't have to postprocess the output, as a CTC decoder transforms the NN output into the final text
How is this achieved?
- introduce a special character (CTC-blank, denoted as "-" in this text) to indicate that no character is seen at a given time-step
- modify the ground truth text T to T' by inserting CTC-blanks and by repeating characters in in all possible ways
- we know the image, we know the text, but we don't know where the text is positioned. So, let's just try all possible positions of the text "Hi----", "-Hi---", "--Hi--", ...
- we also don't know how much space each character occupies in the image. So let's also try all possible alignments by allowing characters to repeat like "HHi----", "HHHi---", "HHHHi--", ...
- do you see a problem here? Of course, if we allow a character to repeat multiple times, how do we handle real duplicate characters like the "l" in "Hello"? Well, just always insert a blank in between in these situations, that is e.g. "Hel-lo" or "Heeellll-------llo"
- calculate score for each possible T' (that is for each transformation and each combination of these), sum over all scores which yields the loss for the pair (I, T)
- decoding is easy: pick character with highest score for each time step, e.g. "HHHHHH-eeeellll-lll--oo---", throw away duplicate characters "H-el-l-o", throw away blanks "Hello", and we are done.
To illustrate this, have a look at the following image. It is in the context of speech recognition, however, text recognition is just the same. Decoding yields the same text for both speakers, even though alignment and position of the character differs.
- an intuitive introduction: https://medium.com/@harald_scheidl/intuitively-understanding-connectionist-temporal-classification-3797e43a86c (mirror)
- a more in-depth introduction: https://distill.pub/2017/ctc (mirror)
- Python implementation which you can use to "play" around with CTC decoders to get a better understanding of how it works: https://github.com/githubharald/CTCDecoder
- and, of course, the paper Graves, Alex, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber. "Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks." In Proceedings of the 23rd international conference on Machine learning, pp. 369-376. ACM, 2006.