A Brief Exploration of OCR Technology: 7. Language Models

OCR技术浅探：7. 语言模型 苏剑林 · 2016-06-26 · Machine Learning model OCR language dynamic programming

Because of factors like image quality, even the best-performing recognition models can produce incorrect recognitions. To reduce the error rate, we can combine the recognition problem with a statistical language model and use dynamic programming to find the optimal recognition result. This is one of the important ways to improve OCR performance.

Transition probability

While analyzing our experimental results, we came across a case where, likely due to poor image clarity, the word "television" (电视) was recognized as "电柳" (a nonsense combination). Relying on the image model alone cannot solve this problem well, because from the image model's point of view, "电柳" is in fact the optimal choice. However, a language model can elegantly resolve this issue. The reason is simple: based on a large amount of text data, we can count the probabilities of the words "电视" and "电柳" appearing, and we find that the probability of "电视" is far greater than that of "电柳". So we would conclude that the word is "电视" rather than "电柳".

From a probabilistic point of view, for the recognition result of the region containing the first character $s_1$, our preceding convolutional neural network gives two candidate characters "电" and "宙" (we only take the top two, since the rest have negligible probability), with probabilities $W(s_1)$ of 0.99996 and 0.00004 respectively; for the recognition result of the region containing the second character $s_2$, the convolutional neural network gives "柳", "视", and "规" (again, only the top three, the rest being negligible), with probabilities $W(s_2)$ of 0.87838, 0.12148, and 0.00012 respectively. So there are in fact six possible combinations: "电柳", "电视", "电规", "宙柳", "宙视", "宙规".

Now let's consider their transition probabilities. The so-called transition probability is simply the conditional probability $P(s_2|s_1)$, i.e., the probability that $s_2$ follows $s_1$. Based on 100,000 WeChat texts, we counted that the character "电" appears 145,001 times, while "电柳", "电视", and "电规" appear 0, 12,426, and 7 times respectively; the character "宙" appears 1,980 times, while "宙柳", "宙视", and "宙规" appear 0, 0, and 18 times respectively. From this we can compute

$$\begin{array}{l} \hline \hline P(\text{willow}|\text{electricity})=\frac{0}{145001}=0 \\ P(\text{view}|\text{electricity})=\frac{12426}{145001}\approx 0.08570 \\ P(\text{rule}|\text{electricity})=\frac{7}{145001}\approx 0.00005 \\ P(\text{willow}|\text{zhou})=\frac{0}{1980}=0 \\ P(\text{view}|\text{zhou})=\frac{0}{1980}=0 \\ P(\text{rule}|\text{zhou})=\frac{18}{1980}\approx 0.00909\\ \hline \hline \end{array}$$

The results are shown in the figure below:

Figure 20 Considering transition probability

From a statistical perspective, the optimal combination for $s_1,s_2$ should be the one that maximizes $(14)$:

$$f=W(s_1)P(s_2|s_1)W(s_2)\tag{14}$$

Thus, we can compute that the best combination for $s_1,s_2$ should be "电视" rather than "电柳". In this way, we successfully obtained the correct result through statistical methods, thereby improving accuracy.

Dynamic programming

Figure 21 The planning problem for multi-character images

Similarly, as shown in Figure 21, if a single line of text in an image contains $n$ characters $s_1,s_2,\dots,s_n$ to be determined, then we should maximize

$$f=W(s_1)P(s_2|s_1)W(s_2)P(s_3|s_2)W(s_3)\dots W(s_{n-1})P(s_n|s_{n-1})W(s_n)\tag{15}$$

This is the core idea of statistical language models. Many areas of natural language processing, such as Chinese word segmentation, speech recognition, and image recognition, all rely on the same approach [6]. Here we need to address two main problems: (1) estimating each $P(s_{i+1}|s_i)$; (2) given each $P(s_{i+1}|s_i)$, how to solve for the maximum of $f$.

Transition probability matrix

For the first problem, we simply need to count, from a large corpus, the number of occurrences $\#s_i$ of $s_i$, as well as the number of times $s_i,s_{i+1}$ appear adjacently $\#(s_i,s_{i+1})$, and then take

$$P(s_{i+1}|s_i)=\frac{\#(s_i,s_{i+1})}{\#s_i}\tag{16}$$

There's nothing fundamentally difficult about this in principle. The recognition targets in this work number 3,062 characters, so in theory we should end up with a matrix of size $3062\times 3062$, which is extremely large. Of course, this matrix is very sparse, so we only need to store the entries that carry useful information.

Now let's focus on the case where $\#(s_i,s_{i+1})=0$. In the previous section we simply set $P(s_{i+1}|s_i)=0$ directly, but this is actually not reasonable. The fact that a combination has not been observed does not mean it cannot occur — it only means that its probability is small. Therefore, even for $\#(s_i,s_{i+1})=0$, we should assign it a small probability rather than zero. This is known in statistics as the problem of data smoothing.

A simple smoothing method is to add a small positive constant $\alpha$ (say, 1) to the count of every item (including those with a count of 0), then recompute the total count and the resulting frequencies, so that every item ends up with a positive probability. This approach may slightly reduce the probability of high-frequency items, but since the probabilities here are only meaningful in relative terms, this effect is negligible. (A more principled approach would be to add the constant only when the count is below some threshold $T$, leaving the rest unchanged.) Following this approach, from several hundred thousand WeChat articles, we computed a transition probability matrix for 1.6 million pairs of adjacent Chinese characters.

The Viterbi algorithm

For the second problem, solving for the optimal combination $s_1,s_2,\dots,s_n$ is a shortest/optimal-path problem in dynamic programming, and the most effective method for it is the Viterbi algorithm [6].

The Viterbi algorithm is a simple and efficient algorithm — a Python implementation takes only about ten lines of code. Its core idea is: if the final optimal path passes through some node $s_{i-1}$, then the path from the initial node to $s_{i-1}$ must itself be an optimal path — because any given node $s_i$ only affects its immediate neighbors $P(s_i|s_{i-1})$ and $P(s_{i+1}|s_i)$.

Based on this idea, we can proceed by recursion: when considering each $s_i$, we only need to find the optimal path through each of the candidate points at $s_{i-1}$, and then compare these with the current $s_i$. This way, each step requires at most $l^2$ computations, allowing us to progressively find the optimal path. The efficiency of the Viterbi algorithm is $\mathcal{O}(n\cdot l^2)$, where $l$ is the largest number of candidates at any node $s_i$, and this is proportional to $n$ — making it extremely efficient.

Improving the results

Experiments show that combining a statistical language model with dynamic programming works well for correcting recognition errors involving visually similar characters. In our tests, it was able to correct errors such as the following:

$$\begin{array}{c} \hline \hline \text{electric willow} \quad \to \quad \text{television}\\ \text{research friend} \quad \to \quad \text{研发}\\ \text{faster than} \quad \to \quad \text{quick-dry}\\ \text{surrounding image} \quad \to \quad \text{image}\\ \dots\\ \hline \hline \end{array}\\ $$

Dynamic programming with a statistical language model corrects a substantial number of recognition errors

Since the corpus used to build the transition matrix is not yet large enough, there is still considerable room to improve the correction effect. Nevertheless, given how simple and efficient the Viterbi algorithm is, this step offers an excellent return on investment.