21.09.2020 г.
Today we’d like to look into the problem of post-processing the text field recognition results based on a priori knowledge about the text field. A significant part of important documents, including identification documents, consists of the fields of a different kind, such as dates, numbers, car VIN-numbers, TIN and social security numbers, machine-readable fields with their checksums, etc. Although we can’t classify these as the natural language fields, oftentimes there is still some implicit linguistic model that can be applied to these fields, which means some correction algorithms will still be applicable here. In this publication, we’ll focus on two methods of recognition result post-processing that can be used for a wide variety of documents and a number of different text fields.
The language model of a text field can be divided into three components:
With all the information about the semantic and syntactic structure of a document and a recognized text field, we can build a specialized algorithm for recognition result post-processing. However, taking into consideration the need for maintaining and advancing the recognition systems and the complexity of their development, it’d make sense to consider “universal” methods and tools that allow building a decent post-processing algorithm that could work for a wide variety of documents and text fields, and that could be built with minimal effort (from the engineers). The configuration and support method for such an algorithm would be made uniform, the only adjustable component of its structure would be the language model.
We must note that post-processing of text field recognition results is not always useful, on the contrary, it could even be damaging: if you have a good enough text field recognition module and you work with identification documents in critical systems, then you’d want to minimize post-processing and to present the results “as is”, or carefully monitor any changes and let the client know if there are any. But in many cases when we know that the document is valid and the language model of the text field is reliable, a post-processing algorithm allows for a considerable improvement of the final recognition quality.
In our article, we’ll cover two post-processing methods claiming to be universal. The first method is based on weighted finite-state transducers and requires the linguistic model to be presented as a state machine. It’s not very easy to use, but it’s quite versatile. The second method is easier to use, more effective and only requires programming the function that checks the text field validity, but it also has a number of flaws.
The method based on weighted finite-state transducers
A beautiful and rather general model that allows us to build a universal post-processing algorithm will be described in our work. This model relies on the weighted finite-state transducers (WFST).
WFST are a generalization of weighted finite-state automata – if the latter encodes some weighted language (i.e weighted set of strings over some alphabet
), then WFST encodes weighted mapping from a language
over an alphabet
into a language
over an alphabet
. When a weighted state machine takes a string
over an alphabet
, it assigns some weight w to this string accordingly, while WFST takes a string
over an alphabet
and mathes it with a set of pairs
(possibly an infinite set), where
is a string over an alphabet
produced as a result of the string
conversion, and
is a weight of this conversion. Each transition of a converter is marked by two states (the transition is realized between them), an input character (from an alphabet
), an output character (from an alphabet
) and the transition weight. An empty character (or an empty string) is considered to be an element of both alphabets. The weight of a string
conversion into a string
would be the sum of the products of the transition weights down the line where the concatenation of the input characters forms the string
, and the concatenation of the output characters forms the string
, and these strings transform the converter from its initial to one of its terminal states.
strings transform the converter from its initial to one of its terminal states.
For WFSTs a composition operation is defined, on which the post-processing method is based. Suppose we are given two transducers and
, where
converts a string
over
into a string
over
with a weight
, and
converts
over
into a string
over
with a weight
. Then the converter
referred to as a composition of transducers transforms the string
into the string
with the weight
. WFST composition is a computationally expensive operation, but there is a “lazy” way to do it – the positions and transitions of the resulting transducer can be built right when they need to be accessed.
A WFST based algorithm for post-processing the recognition results relies on three main sources of data – a hypothesis model , an error model
and a language model
. All three models are represented as weighted finite state transducers.
Figure 1. Example of a hypothesis model presented as a WFST (the unage from this article). Transitions with zero-probability are not shown.
After we define the hypothesis model, the error model and the language model, we can define the objective of recognition result post-processing as follows: let’s look at the composition for all three models (in terms of the WFST composition). A transducer
encodes various transformations of a string
from the hypothesis model
into a string
from the language model
with the help of the conversions encoded in the error model
. The weight of such a conversion consists of the initial hypothesis weight, the conversion weight and the resulting string weight (when we have a weighted language model). The optimal recognition result post-processing in such a model would be the optimal path (in terms of weight) in the transducer
that takes it from the initial state to one of the terminal states. The input string on this path is equal to the selected initial hypothesis, and the output string – to the corrected recognition result. The optimal path can be found using shortest path algorithms in directed graphs.
The advantage of this approach is its generality and versatility. For example, the error model can be easily expanded so that it becomes possible to consider the character deletions and additions (in order to do that we just need to respectively add transitions with an empty input or output character to the error model). However, this model has some significant flaws as well. First of all, the language model has to be presented as a weighted finite-state transducer here. For complex languages, this finite-state machine can be rather bulky, and it will have to be rebuilt if the language model is changed or refined in any way. We also need to point out that the composition of these three transducers has an even bulkier transducer as a result, and this composition is calculated every time when we start post-processing any recognition result. Due to the cumbersome nature of our composition, in practice, the optimal path search is performed using heuristic approaches, such as an A*-search algorithm.
Approach based on validation grammars
Using the validation grammar model we will be able to build a simpler model for the post-processing problem that will not be as general as the WFST-based model but will be easy to expand and implement.
Let’s denote the validation grammar as a pair where
is an alphabet and
is a predicate that accepts a string over the alphabet
, i.e.
. The validation grammar encodes some language over the alphabet
as follows: the string
is a part of the language if the predicate
takes true value given this string. We should note that a validation grammar is a more general way to represent the language model than a finite-state automata. In fact, any language presented as a finite-state automaton
, can be presented as a validation grammar (with a predicate
, where
is a set of strings accepted by the automaton
). But not all the languages that can be presented as a validation grammar can be presented as a finite state automaton generally (for example, the language with words of an unrestricted length over the alphabet
, where the number of characters
is higher than the number of characters
).
Let’s consider a recognition result (a hypothesis model) as a sequence of cells (the same as earlier). For convenience, we assume that each cell contains K alternatives and estimation values of these alternatives are positive. A string evaluation (weight) will be a product of estimations of all the characters in this string. If the language model presented as a validation grammar
, then the post-processing problem can be defined as a discrete optimization (maximization) problem for a set of controls
(a set of all the strings of a length
over an alphabet
) with a predicate
and a functional
, where
is an estimation of the character
in the
-th unit.
Any discrete optimization problem (i.e. with a finite number of controls) can be solved by a brute-force search. This algorithm goes through the controls (strings) in the descending order of a functional value until the predicate takes a true value. Let’s denote a maximum number of iterations of the algorithm as , i.e. a maximum number of strings with the highest estimates that will be used to calculate the predicate.
First, let’s sort the alternatives in the descending order of their estimates, and we’ll be assuming that the inequality is true for any cell
when
. A position is defined as the sequence of indices
that corresponds with a string
. A position estimate, i.e. a functional value at this position, will be considered a product of the alternative estimates that match the indexes in this position:
. In order to save the positions, we are going to need the data structure PositionBase which allows us to add new positions (when their address is available), to get new positions using their address and check if any given position is added to the database.
In the process of listing the positions, first, we’ll be selecting a yet unprocessed position with the highest estimate, then we’ll be adding all the positions (the positions that can be generated out of the current one by adding one to one of the indices that is included in the position) to the PositionQueue. The PositionQueue will include the triplets , where
is an estimate of an unseen position,
– an address of a processed position in PositionBase from which the current position was derived,
is an index of a position element with an address
that was increased by one in order to get the current position. In order to organize PositionQueue we’ll need a data structure that will allow us to add a new triplet
and extract a triplet with the highest estimate
.
At the first algorithm iteration we are going to have to review the position that has the maximum estimation. If a predicate
is of its true value in a string that matches this position, then the algorithm will terminate. If it’s not, then the position
is added to PositionBase, and all the triplets
are added to PositionQueue, for all
is an address of an initial position in PositionBase. At each consequent algorithm iteration the triplet
with the maximum estimation value
is extracted from PositionQueue. And then the position S is restored according to an initial position address
and an index
. If the position S is already added to PositionBase, it’s skipped, and the next triplet with the maximum estimation value
is extracted from PositionQueue. Otherwise, we check the value of a predicate
in the string that corresponds with a position
. If the predicate
is of true value for this string, then the algorithm terminates. If the predicate
is not of true value for this string, then the string
is added to PositionBase (with the assignment of an address
), all the derivative positions are added to PositionQueue and the process moves to the next iteration.
Let’s point out that after iterations the predicate verification will be done not more than M times, there will be no more than
additions to PositionBase, and the addition to PositionQueue, the extraction from PositionQueue, and the search in PositionBase will happen not more than
times. If in order to implement PositionQueue we use the “heap” data structure and in order to organize PositionBase we use the “trie” data structure, then the computational complexity of the produced algorithm amounts to
, where
is the complexity of checking the predicate
for the string of length
.
The biggest flaw of the algorithm based on validation grammars might be the fact that it’s not able to process the hypotheses of different lengths (which can occur due to segmentation errors: loss or appearance of extra characters, stitching and cutting the characters, etc.), while the hypotheses changes like “character deletion”, “character addition”, or even “character replacement with a pair” can be encoded easily in the error model of the algorithm based on WFST.
Speed and simplicity of use (when working with a new type of text field we just need to give it an access to the validation function) make the method based on validation grammar an extremely powerful tool in the arsenal of the recognition system developers. We utilize this technique for a wide variety of text fields, such as different dates, numbers of bank cards (the predicate is the Luhn code check), fields of machine-readable zones in documents with checksums, and many others.
Other blog posts
18.03.2021 15.03.2021Quantitative assessment of cupping effect in tomographic images
12.03.2021Interpolation and sampling: why do we need them for projective transformation in image processing?
All posts
Tinkoff Bank
Tinkoff Bank chooses Smart Engines for ID, passport, bank card and barcode scanning
MobileTeleSystems
Smart Engines technologies are used in MTS SIM card issuing machines
VerifyMyAge
Smart ID Engine is integrated into customer age verification platform VerifyMyAge
Sum&Substance
Sum&Substance, a global KYC/AML service provider, use Smart ID Engine for IDs scanning