Due to factors such as image quality, even the best-performing recognition models have the possibility of recognition errors. To reduce the error rate, the recognition problem can be combined with statistical language models, using dynamic programming to provide the optimal recognition result. This is one of the important methods for improving OCR recognition performance.
Transition Probability
During our analysis of experimental results, we encountered a specific case. Due to possible reasons like unclear images, the word "Television" (Dian-Shi) was recognized as "Electric-Willow" (Dian-Liu). Using only the image model cannot solve this problem effectively because, from the perspective of the image model, recognizing it as "Electric-Willow" is the optimal choice. However, a language model can solve this problem quite ingeniously. The reason is simple: based on a large amount of text data, we can calculate the probabilities of the words "Television" and "Electric-Willow." We find that the probability of "Television" is far greater than that of "Electric-Willow," so we conclude that the word is "Television" rather than "Electric-Willow."
From a probabilistic perspective, for the recognition result s_1 of the first character region, our previous Convolutional Neural Network (CNN) provided two candidate characters: "Electric" and "Universe" (selecting only the top two, as subsequent probabilities were too small). The probabilities W(s_1) for each candidate were 0.99996 and 0.00004, respectively. For the recognition result s_2 of the second character region, the CNN provided "Willow," "Vision," and "Regulation" (selecting only the top three), with probabilities W(s_2) of 0.87838, 0.12148, and 0.00012, respectively. Therefore, there are actually six combinations: "Electric-Willow," "Electric-Vision," "Electric-Regulation," "Universe-Willow," "Universe-Vision," and "Universe-Regulation."
Next, we consider their transition probabilities. The so-called transition probability is actually the conditional probability P(s_2|s_1), which is the probability that s_2 follows s_1. Through 100,000 WeChat texts, we calculated that the character "Electric" appeared 145,001 times, while the sequences "Electric-Willow," "Electric-Vision," and "Electric-Regulation" appeared 0, 12,426, and 7 times, respectively. The character "Universe" appeared 1,980 times, while "Universe-Willow," "Universe-Vision," and "Universe-Regulation" appeared 0, 0, and 18 times. Thus, we can calculate:
\begin{array}{l} \hline \hline P(\text{Willow}|\text{Electric})=\frac{0}{145001}=0 \\ P(\text{Vision}|\text{Electric})=\frac{12426}{145001}\approx 0.08570 \\ P(\text{Regulation}|\text{Electric})=\frac{7}{145001}\approx 0.00005 \\ P(\text{Willow}|\text{Universe})=\frac{0}{1980}=0 \\ P(\text{Vision}|\text{Universe})=\frac{0}{1980}=0 \\ P(\text{Regulation}|\text{Universe})=\frac{18}{1980}\approx 0.00909\\ \hline \hline \end{array}
The results are shown in the figure below:
From a statistical perspective, the optimal combination of s_1, s_2 should maximize the value of Equation (14): f=W(s_1)P(s_2|s_1)W(s_2) \tag{14} Therefore, it can be calculated that the best combination of s_1, s_2 is "Electric-Vision" (Television) rather than "Electric-Willow." In this way, we successfully obtained the correct result through statistical methods, thereby improving the accuracy.
Dynamic Programming
Similarly, as shown in Figure 21, if a single-line text image has n characters s_1, s_2, \dots, s_n to be determined, 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 fields in Natural Language Processing, such as Chinese word segmentation, speech recognition, and image recognition, use the same method. Two main problems need to be solved here: (1) the estimation of each P(s_{i+1}|s_i); and (2) how to solve for the maximum value of f given each P(s_{i+1}|s_i).
Transition Probability Matrix
For the first problem, one only needs to count the number of occurrences of s_i (denoted as \#s_i) and the number of times s_i and s_{i+1} appear adjacently (denoted as \#(s_i, s_{i+1})) from a large corpus, and then assume: P(s_{i+1}|s_i)=\frac{\#(s_i, s_{i+1})}{\#s_i} \tag{16} In essence, there is no inherent difficulty. The recognition targets in this article consist of 3,062 characters. Theoretically, a 3062 \times 3062 matrix should be generated, which is very large. Of course, this matrix is very sparse, and we can save only the valuable elements.
Now, we must specifically consider the case where \#(s_i, s_{i+1})=0. In the previous section, we directly treated P(s_{i+1}|s_i)=0, but this is actually unreasonable. Not appearing does not mean it will never appear; it only means the probability is very small. Therefore, even for \#(s_i, s_{i+1})=0, a small probability should be assigned instead of zero. This is known in statistics as the data smoothing problem.
A simple smoothing method is to add a small positive constant \alpha (such as 1) to the frequency of all items (including those with a frequency of 0), and then recalculate the total and the frequency so that every item gets a positive probability. This approach might decrease the probability of high-frequency items, but since the probabilities here only have relative significance, the impact is not significant (a more reasonable approach is to add the constant only when the frequency is below a certain threshold T). Following this logic, from hundreds of thousands of WeChat articles, we calculated a transition probability matrix for 1.6 million adjacent Chinese character pairs.
Viterbi Algorithm
For the second problem, solving for the optimal combination s_1, s_2, \dots, s_n is an optimal path problem in dynamic programming, for which the most effective method is the Viterbi algorithm.
The Viterbi algorithm is a simple and efficient algorithm that can be implemented in about ten lines of Python code. Its core idea is: if the final optimal path passes through a certain s_{i-1}, then the path from the initial node to s_{i-1} must also be an optimal path—because each node s_i only affects the two adjacent probabilities P(s_i|s_{i-1}) and P(s_{i+1}|s_i).
Based on this idea, we can use a recursive method. When considering each s_i, we only need to find the optimal paths passing through each candidate point of s_{i-1} and then compare them with the current s_i. In this way, each step only requires calculating no more than l^2 times to gradually find the optimal path. The efficiency of the Viterbi algorithm is \mathcal{O}(n \cdot l^2), where l is the maximum number of candidates for a node s_i. This is proportional to n, making it very efficient.
Improvement Effects
Experiments show that combining statistical language models with dynamic programming can effectively resolve some recognition errors involving visually similar characters. In our tests, it corrected errors such as:
\begin{array}{c} \hline \hline \text{Electric-Willow} \quad \to \quad \text{Television}\\ \text{Research-Friend} \quad \to \quad \text{R\&D}\\ \text{Fast-In} \quad \to \quad \text{Quick-Dry}\\ \text{Enclosed-Image} \quad \to \quad \text{Image}\\ \dots\\ \hline \hline \end{array}
Dynamic programming through statistical language models can correct many recognition errors.
Since the corpus used to generate the transition matrix is not large enough, there is still significant room for improvement in the correction effect. Regardless, due to the simplicity and efficiency of the Viterbi algorithm, this is a very cost-effective step.
When reposting, please include the original address of this article: https://kexue.fm/archives/3842
For more detailed information regarding reposting, please refer to: Scientific Space FAQ