Сенсорные системы, 2020, T. 34, № 3, стр. 217-225

INTRODUCTION

Modern document entry systems allow to automatize the process of data extraction from various documents, either business, regulatory, or personal. Such systems are used for creating digital archives of historical documents (Van Phan, 2016), recognition of small-scale documents such as business cards (Dangiwa, 2018), ID documents, driving licenses, passports (Arlazarov, 2019), as well as large-scale business documents (Esser, 2013).

Increasing computational power of mobile devices and rising technical characteristics of small-scale digital cameras lead to increased interest in methods for automatic document entry using mobile devices (Арлазаров, 2017; Ravneet, 2018; Povolotskiy, 2019; Skoryukina, 2018) and forensic analysis (Chernyshova, 2019; Полевой, 2019). As a rule, regular smartphones are used for document recognition, due to relatively low cost, sufficient computational power for performing recognition tasks, and ability of capturing video (or sequence of images). The ability to capture video is one of the most important advantages over traditional scanners, as in such case more information could be retrieved in comparison with a single image, and each newly acquired document image may be used to improve the recognition result (Bulatov, 2017). Figure 1 illustrates an example of per-frame recognition results combination in a video stream. As it can be seen, the correct integrated result may be acquired even before any individual frame result is correct.

While processing the sequence of frames and combining the per-frame recognition results a single more precise one, the problem arises – when this process should terminate? The capturing process in a general case might not be naturally limited, and if a sufficiently good combination strategy is employed the increase of the number of integrated observations the expected result precision also increases (Bulatov, 2019a). However, the time required to perform recognition and output the final result is also very important and thus efficient strategies for video stream recognition stopping should be developed and further studied.

The optimal stopping problems themselves occupy a special place in mathematical statistics and decision theory (Ferguson, 2010; Christensen, 2019). Some methods were also proposed for the video stream recognition problem (Arlazarov, 2018; Bulatov, 2019b; Bulatov, 2020b). In (Arlazarov, 2018) a method was presented which consisted of clustering the set of per-frame field recognition results, estimating a confidence score for each cluster, and making a stopping decision based on three parameters: cluster size, cluster confidence, and the total number of processed observations. The method can be applied in two ways: the clusters may be formed from the initial per-frame recognition results, or from the integrated results obtained on each stage. This method, however, is not fully formalized and raises the questions of tuning the clustering parameters. In (Bulatov, 2019b) a method is proposed, which considers the video stream recognition stopping as a monotone sequential decision problem. It presents a stopping strategy derived from the properties of monotone stopping problems, however it was tested only for text recognition results as simple strings, without any per-character alternatives. At the same time an extended string recognition result model with per-character alternatives is an important way of text recognition result representation: it is used for recognition results post-processing (Llobet, 2010) and was shown to be valuable for improving the integrated result precision (Bulatov, 2019a).

The goal of this paper is to investigate the applicability of stopping strategy introduced in (Bulatov, 2019b) for text string recognition with per-character alternatives and to compare it with alternative methods, which are already adapted for such recognition result model. In section 2 a brief description of the stopping method is given, and in section 3 experimental evaluation and comparison for stopping methods is presented.

METHOD DESCRIPTION

In order to provide a description of the stopping method, let us consider text string recognition in a video stream as a sequential decision problem. Let $\mathbb{X}$ represent a set of all possible text string recognition results, and the task is to recognize a text string with correct value $x{\text{*}} \in \mathbb{X}$ given a sequence of images ${{I}_{1}},{{I}_{2}},{{I}_{3}}, \ldots $ which are obtained one at a time. At stage n the image ${{I}_{n}}$ is recognized and the per-frame recognition result ${{x}_{n}} \in \mathbb{X}$ is obtained. After ${{x}_{n}}$ is obtained the results ${{x}_{1}},{{x}_{2}}, \ldots ,{{x}_{n}}$ are combined using some combination algorithm to produce an integrated result ${{R}_{n}} \in \mathbb{X}$. The stopping decision is now to either stop the process and use ${{R}_{n}}$ as the final recognition result, or continue the process in an effort to obtain in the future the integrated result with higher expected accuracy. If the process is stopped at stage n the penalty is paid in form of a linear combination of distance from the obtained result to the correct one (a “price for error”) and the number of frames process (a “price for time”):

where ρ is a metric function on the set $\mathbb{X}$, and c is a constant representing the price paid for each observation (in relation to the cost of the recognition error).

The stopping rule is formally defined as a sequence of real-valued functions, which represent the conditional probability of stopping after the stage n is reached (Ferguson, 2006). However, such conditional probability functions define a random stopping time N, which could be used to denote the stopping rule instead with more clarity (the conditional probability of stopping could also be inferred from the random stopping time N). The distribution of $N$ depends on the obtained observations ${{x}_{1}},{{x}_{2}},{{x}_{3}}, \ldots $. The stopping problem is an optimization problem of finding a stopping rule with a goal to minimize the expected loss, which can be expressed as follows:

where $\operatorname{E} ( \cdot )$ is a mathematical expectation, and ${{X}_{1}},{{X}_{2}}, \ldots ,{{X}_{k}}$ are random recognition results with identical joint distribution with $x{\text{*}}$ of which ${{x}_{1}},{{x}_{2}}, \ldots ,{{x}_{k}}$ are realizations observed at stages $1,2, \ldots ,k$.

Optimal stopping problems, such as (2), can be classified into a variety of subtypes, and for each type some theoretical results have been achieved over the years. A large class of optimal stopping problems grounded in real applications are the finite horizon problems, which could be solved using the backwards induction method (Berezovskij, 1981). The finite horizon problem is characterized by a fixed stage T such that any stopping rule calls for stopping on the stage $n = T$. For the task of text string recognition in a video stream this would correspond to a predefined “time-out”: the number of processed video frames after which the procedure is always stopped (possibly with a null result). The addition of such a “time-out” T to the stopping problem (2) does not divert it from the practical relevance.

The other important subtype of stopping rule problems are the so-called monotone stopping problems (Ferguson, 2006; Chow, 1961). The definition is as follows: consider the event ${{A}_{n}} = \left\{ {{{L}_{n}} \leqslant \operatorname{E} \left( {{{L}_{{n + 1}}}\,{\text{|}}\,{{X}_{1}} = {{x}_{1}}, \ldots ,{{X}_{n}} = {{x}_{n}}} \right)} \right\}$, which indicates that the loss which would be suffered if the process is stopped at stage n is not greater than the expected loss of stopping at the next stage, given that only the first n observations were obtained. The optimal stopping problem is considered monotone if the occurrence of the event ${{A}_{n}}$ leads to the occurrence of ${{A}_{{n + 1}}}$ for all n. In other words, if the current loss is not greater than the expected loss at the next stage, then this will be true for all future stages as well. It can be proven (Ferguson, 2006) using the backwards induction method, that for monotone stopping problems with a finite horizon the optimal stopping rule for the problem (2) is the so-called “myopic” rule:

which calls the process to stop at the earliest stage when the event ${{A}_{n}}$ occurs.

In terms of the loss function (1) the events ${{A}_{n}}$ considered in the definition of the monotone stopping problem can be expressed as follows:

Since x* is unknown at the moment of making the stopping decision (and thus the loss function (1) cannot be computed), the occurrence of the event ${{A}_{n}}$ also cannot be determined. Thus, some additional assumptions need to be made in order to be able to estimate the left-hand side of the inequality in (4). The stopping method proposed in (Bulatov, 2019b) for the problem of text string recognition in a video stream is relying on an assumption that the expected distances between two consecutive integrated results decrease over time:

Let us consider the event B_n = $\left\{ {\operatorname{E} \left( {\rho ({{R}_{n}},{{R}_{{n + 1}}})|{{X}_{1}} = {{x}_{1}}, \ldots ,{{X}_{n}} = {{x}_{n}}} \right) \leqslant c} \right\}$, which occurs when the current estimation of the distance from the current combined recognition result to the next one is not greater than the relative cost of the observation. Due to assumption (5) we can expect that the occurrence of ${{B}_{n}}$ will lead to the occurrence of ${{B}_{{n + 1}}}$ for all n. At the same time, due to the triangle inequality governing the metric function ρ, the occurrence of ${{B}_{n}}$ leads to the occurrence of ${{A}_{n}}$. This means, that if ${{B}_{n}}$ has occurred, the events ${{A}_{n}},{{A}_{{n + 1}}},{{A}_{{n + 2}}}, \ldots $ will occur as well, so starting from this stage the problem is effectively monotone and it is optimal to stop (however, the true optimal stopping rule may have called for stopping the process at the earlier stages). Thus, we obtain a stopping rule which does not depend on the correct recognition result value $x{\text{*}}$:

To implement the stopping rule (6) we need to estimate the expected distance from the current combined result to the next one. To achieve this, a modelling of the next integrated result is proposed in (Bulatov, 2019b), defining the following stopping method:

where c is an observation cost (essentially, a threshold parameter of the stopping method), δ is an external parameter, and $R({{x}_{1}},{{x}_{2}}, \ldots ,{{x}_{n}},{{x}_{i}})$ is a modeled integration result of all consecutive observations obtained by the stage n concatenated with i-th observation.

It is noted in (Bulatov, 2019b) that the concrete method of modelling the next integrated result might depend on the nature of the combination algorithm and other specifics of the problem, however the proposed method could still be used in a quite general case, by replacing the recognition results combination method and the metric function ρ. In the original paper the experiments were conducted using Tesseract (Smith, 2007) as the recognition algorithm, simple string of characters as a recognized string representation, a normalized Levenshtein distance (Yujian, 2007) as a metric function ρ, and ROVER (Fiscus, 1997) as a combination algorithm. It was not clear whether this stopping method would be effective for an extended string recognition result model, containing per-character classification alternatives. In the extended model, the string recognition result can be represented as a matrix of alternatives:

where ${{c}_{{ij}}}$ are character labels, ${{q}_{{ij}}} \in [0,1]$ – class membership estimations for each character, K – the size of the alphabet, and M – the length of the string. The combination algorithms for string recognition result in this extended model can be viewed as a generalization of the ROVER approach, and to define the metric function ρ a generalized Levenshtein distance may be used after defining the metric on the individual character classification results (Bulatov, 2019a).

To compare different stopping methods the expected performance profiles can be used – a methodology from the field of anytime algorithms (Zilberstein, 1996). Expected performance profiles are graphical plots which show dependence of the expected accuracy on the expected time required to obtain it.

EVALUATION

In order to evaluate the stopping method described in section 2 we used an open dataset MIDV-500 (Arlazarov, 2019) which contains 500 video sequences of 50 types of identity documents with ground truth. Each original clip contained 30 frames. The frames on which the document was not fully visible were removed from the consideration, and the resulting clip was repeated in a loop until the original size of 30 frames was reached. In addition we used an extension of this dataset called MIDV-2019 (Bulatov, 2020a), which has the same ground truth format, but features two additional capturing conditions.

The ground truth in the MIDV-500 contains both ideal values for text field recognition and the ideal geometric coordinates, i.e. for each field its geometric position in the document boundaries is known, making it possible to crop the field from any frame of the dataset. Text fields were cropped with margins with width equal to 30% of the smallest text field bounding box side. Since physical dimensions of each document type in the MIDV-500 dataset is also known, it is possible to crop each field in a uniform resolution. For recognition, all text fields were cropped with the resolution of 300 DPI. After cropping each text field was recognized using a text string recognition subsystem of Smart IDReader document recognition software (Bulatov, 2017), obtaining the recognized value as a sequence of character classification results with alternatives. For combination of per-frame recognition result a method from (Bulatov, 2019a) was used, which could be regarded as a generalization of the ROVER (Fiscus, 1997) approach for string recognition results with per-character alternatives. As a distance metric ρ a normalized version of the generalized Levenshtein distance was used, with a taxicab metric for individual character classification results.

In (Arlazarov, 2018) a stopping method was proposed, which was based on clusterization of the set of text field recognition results to n clusters, and making a stopping decision based on some properties of the most populous cluster. The method proposed in (Bulatov, 2019b) and described in section 2 was compared with this method in the original paper, however since the paper was focused on a simplified string recognition result model, not all features of the stopping method presented in (Arlazarov, 2018) were used, as the per-character alternatives were not available when using Tesseract as the text string recognition algorithm.

The clusterization of the observations is performed by their lengths (i.e. by the number of characters in the obtained string recognition results). For each cluster its confidence value is computed according to the following formula:

where C is a cluster of observations with the same length $M(C)$. The stopping decision is made by three thresholding: the size of the largest cluster, the confidence of the largest cluster, and, if there is more than one cluster, the difference between confidences of the two largest clusters. Such thresholding meant that there are three stopping method parameters (three thresholds).

Two variations of the stopping method proposed in (Arlazarov, 2018) can be realized – the first, denoted hereinafter as ${{N}_{{CX}}}$ which treats input observations ${{x}_{1}},{{x}_{2}}, \ldots ,{{x}_{n}}$ as strings to compose clusters with, and the second – ${{N}_{{CR}}}$ – treats the integrated results ${{R}_{1}},{{R}_{2}}, \ldots ,{{R}_{n}}$ as observations and components of the clusters. Figure 2 and 3 illustrate the quality maps of the both approaches with variation of all three thresholds: each data point represents the mean number of observations processed before stopping and the mean distance of the integrated result to the correct value.

One of the main disadvantages of this stopping methods is that it is unclear how to jointly select the values for all thresholds to achieve the highest efficiency. In Figure 2 the black line represents the best option constructed a posteriori, which will be used for comparison with the method described in section 2.

Figures 4 and 5 illustrate the expected performance profiles comparison for the best achievable versions of the stopping methods ${{N}_{{CX}}}$ and ${{N}_{{CR}}}$, the stopping method based on the modelling of the next integrated result ${{N}_{\Delta }}$, described in section 2, and, as a baseline, a simple stopping method ${{N}_{K}}$ which stops after observing $K$-th per-frame result. It can be seen that even though the best versions of the clustering stopping methods were evaluated, without clear understanding of how to obtain these jointly optimal threshold values, the method ${{N}_{\Delta }}$ still outperforms them.

Table 1 and 2 show the achieved mean integrated result accuracy (in terms of distance to the correct value) at stopping time, using the evaluated stopping methods and with restrictions to the mean number of processed observations. It can be seen that the method based on modelling the next integrated result and thresholding the estimation of the expected distance from the current result to the next one (${{N}_{\Delta }}$) outperforms the other methods. In particular, it allows to achieve higher result quality with the same average number of processed observations even when compared with the best achievable version of the previously proposed method (Arlazarov, 2018).

The stopping method ${{N}_{\Delta }}$ has a disadvantage to the clustering methods with regards to the computational efficiency when making the stopping decision. The computations required for the stopping method ${{N}_{\Delta }}$ to make the stopping decision at stage n grows linearly relatively to the number of processed frames, whereas for the clustering methods this dependence is virtually constant. Figure 6 illustrates the mean time per decision relative to the number of frames for the three evaluated methods. Table 3 shows the tabular representation of the measured time characteristics.

As it can be seen from the performed experiments, the modelling of the next result according to (7) is very time-consuming, especially if an extended string recognition result representation is considered. This issue could be mitigated by approximate calculation of the next integrated results without complete integration, or alternative estimations of the expected distance to the next integrated result, such as using time series predictions. The essence of the stopping method does not change, as the main idea would still be to threshold the estimated expected distance to the next integrated observation, however the computational efficiency could be significantly improved.

CONCLUSION

The paper describes the problem of stopping the process of text line recognition in a video stream. Previously presented stopping methods were described and their properties analyzed. A method based on modelling of the next integrated result is described and applied to the model of text recognition result as an alternatives matrix with extended per-character classification results. The applicability of the stopping method in these conditions is shown, and the comparative evaluation is performed against previously published methods. It was shown that the next integrated result modelling method outperforms the previously published clustering methods, even in their best achievable configurations, but requires more time to make a decision. As future work it is planned to evaluate different ways to estimate the expected distance between the current integrated result and the next one, either with more efficient approximate modelling, or using time series analysis, in order to improve on the computational efficiently of the stopping decision.