Text Information Extraction in images is concerned with extracting the relevant text data from a collection of document images. It consists in localizing (determining the location) and recognizing (transforming into plain text) text contained in document images. In this work we present a textual information extraction model consisting in a set of prototype regions along with pathways for browsing through these prototype regions. The proposed model is constructed in four steps: (1) produce synthetic invoice data containing the textual information of interest, along with their spatial positions; (2) partition the produced data; (3) derive the prototype regions from the obtained partition clusters; (4) build the concept lattice of a formal context derived from the prototype regions. Experimental results, on a corpus of 1000 real-world scanned invoices show that the proposed model improves signi cantly the extraction rate of an Optical Character Recognition (OCR) engine.
Document processing is the transformation of a human understandable data in a
computer system understandable format. Document analysis and understanding
are the two phases of document processing. Considering a document containing
lines, words and graphical objects such as logos, the analysis of such a
document consists in extracting and isolating the words, lines and objects and then
grouping them into blocks. The subsystem of document understanding builds
relationships (to the right, left, above, below) between the blocks. A document
processing system must be able to: locate textual information, identify if that
information is relevant comparatively to other information contained in the
document, extract that information in a computer system understandable format.
For the realization of such a system, major di culties arise from the variability
of the documents characteristics, such as: the type (invoice, form, quotation,
report, etc.), the layout (font, style, disposition), the language, the typography and
the quality of scanning. In the literature, works in pattern recognition [
The present paper is in the framework of region-based textual information
localization and extraction [
4. derive pathways for browsing through the prototype regions, from the concept lattice of a suitably de ned formal context; The paper is organized as follows. Section 2 is devoted to the construction of prototype regions. The formal context de ned using the obtained prototype regions, and the determination of paths from the concept lattice of that formal context are described in Section 3. Section 4 presents our approach for textual information extraction, using the de ned paths. Finally, some experimental results are presented in Section 5 and the paper is closed with a conclusion and perspectives.
The present work is motivated by the request of a company interested in developing its own system enabling to automatically extract some textual information from scanned invoices. The company has provided us with a corpus of 1000 real-world scanned invoices, emitted by 18 service providers whose business is around car towing and auto repair. All the images are one page A4 documents. The whole set of information the company is interested in, comprises: invoice number, invoice date, net amount, VAT amount, customer reference, the type of service provided, the issuer identity. In our study, we consider only the following ve information: { I1: the key word of the service provided: towing or auto repair, { I2: customer reference: a string of 9-13 characters, { I3: the plate number of the assisted vehicle, { I4: the invoice issuer unique identi er: a string of 14 digits, { I5: the net amount of money requested for the provided service. Each of the textual information is located in a region delimited by a rectangle de ned by the coordinates (x; y) (in pixels) of its top left corner and the coordinates (z; q) of its bottom right corner. In the sequel, by the term region will be meant a rectangular area in an invoice image. Hence, a region may be represented by the four coordinates (x; y; z; q) of its top left and bottom right corners. As the information to be extracted are located in (rectangular) regions we adopt a region-based extraction approach. The regions which the proposed approach is based on are prototypes obtained from the more speci c regions containing, each, a single information. Now, the coordinates of the regions containing the needed information are not available for the real-world scanned invoices at hand. To cope with this, we develop a JAVA program, with a graphical interface, enabling to create synthetic invoice data simulating the real-world scanned invoices along with the approximate coordinates of the speci c rectangles containing the needed information. For instance, from a real-world scanned invoice an initial synthetic invoice is manually created. This synthetic invoice is a single black and white A4 page. This page will contain a string corresponding to a plate number approximately at the same location as the plate number information appears in the real-world invoice. Additionally, the string will be inserted approximately with the same size and the same font as in the real-world invoice in order to look like it. The string is inserted manually in the initial synthetic invoice as one can do with a text editor. However, many strings contained in the real-world invoice are not reproduced in the synthetic invoice. For instance, the information about the emitter and the receiver (address, phone number, ...) are not reproduced because they are not relevant for the study. Thus, the set of textual information I1 to I5 is placed manually on the synthetic invoice. Then, from the obtained initial synthetic invoice a xed number of synthetic invoice images may be created automatically. In such synthetic invoice images, the information locations are maintained identically to the initial synthetic invoice but the contained string may vary. Finally, for each distinct emitter of the real-world invoice images corpus, one initial synthetic invoice image is created manually and a xed number of synthetic invoice images is created automatically from the initial synthetic invoice. A corpus of 1000 synthetic invoice images is thus produced and, for each synthetic invoice, both the textual information and the coordinates of the respective rectangles containing them, are stored in a database. The original distribution per emitter of the real-world invoices is preserved in the synthetic corpus of images. Synthetic data sets can then be generated from this database for closer insight. An example of such data sets is a set of (synthetic invoice) records described by 20 variables representing 5 blocks of 4 coordinates (x; y; z; q), each block being associated with one of the 5 considered information I1 to I5. It should be noted that this possibility to produce a synthetic representation of a real-world scanned invoice is an important step for updating the proposed model, namely when one has to extract information from previously unseen scanned invoice. This point will be discussed later in Section 6. 2.2
As we mentioned in Section 2.1, the regions which our proposed approach is based on are the so-called prototype regions, obtained from the speci c regions that contain, each, a single information. More precisely, a prototype region associated with a given information should be a region containing a homogeneous set of speci c regions related to various positions of this information in di erent invoice images. This makes cluster analysis methods, (such as the partitioning ones) good candidates for capturing such homogeneous sets of speci c regions. Then, in the next section, the construction of prototype regions from such homogeneous sets of speci c regions is explained.
The synthetic data obtained from the previous phase can be partitioned either:
(a) in an overall view taking into account all of the 20 variables, or (b) in 5
independent views, each corresponding to one of the 5 information I1 to I5 and
taking into account, for each view, the 4 associated variables. The approach in
ve independent views consists in creating ve data sets: D1, D2, D3, D4 and
D5. A record in Di is described by the four coordinates of regions containing
information Ii. For both approaches we adopted the K-means [
Recall that for each information Ii, the associated data set Di is partitioned into some number of clusters (see Table 1). Then, we associate to each of these clusters, say C, a prototype region de ned as the smallest rectangle R containing each of the speci c rectangles in C. Thus, we obtain 43 prototype regions R1,...,R43, with the rst 10 related to information I1, the next 10 to I2, the next 10 to I3, the next 3 to I4 and the last 10 to I5. Figure 1 shows the prototype regions related to information I4. The next step of the construction of our proposed model is to set up pathways for e ciently browsing through the set of de ned prototype regions. Such pathways will be obtained from the concept lattice of a suitably de ned formal context. 3
So far, we indicated how we determine prototype regions containing the textual information to be extracted. So we come to the fourth step in our approach, namely, de ne pathways for e ciently browsing through the set of these prototype regions. For this, Formal Concept Analysis (FCA) appears very appropriate. Indeed, the pathways we seek to determine may be obtained from the concept lattice of a suitably de ned formal context. 3.1
Recall that a formal context is a triple K = (O; A; R), where O is a set of objects,
A a set of attributes and R O A a binary relation from O to A. A formal
concept of K is a pair (X; Y ) such that Y = X0 = fa 2 A : xRa for all x 2 Xg
and X = Y 0 = fx 2 O : xRa for all a 2 Y g. Note that the double application of
the derivation operator (:)0 is a closure operator, i.e. (:)00 is extensive, idempotent
and monotone. Sets X O; Y A, such that X = X00 and Y = Y 00 are said to
be closed. The subset X O is called the extent of the concept (X; Y ) and Y its
intent. The concept lattice of the formal context K [
Recall that, given a formal context K = (O; A; R), an association rule is a pair
(X; Y ), denoted as X ! Y , where X and Y are disjoint subsets of A [
... o1000
X
association rule is an association rule whose support and con dence are at least
equal to a xed minimum support threshold and a xed minimum con dence
threshold, respectively. An approximate association rule is an association rule
whose con dence is less than 1. When the minimum support threshold is set to
0, the Luxenburger basis of approximate association rules is the set of rules of
the form X ! Y n X where X = X00, Y = Y 00, X Y and there is no Z such
that Z00 = Z and X Z Y [
The Luxenburger basis can be visualized directly in the line diagram of a concept
lattice. Each approximate rule in the Luxenburger basis corresponds exactly to
one edge in the line diagram. The line diagram of a lattice contains paths by
which one can move from the top concept to the bottom one. The pathways
we adopt for browsing through the set of prototype regions are exactly those
corresponding to sequences of association rules of the Luxenburger basis, i.e.
top-down consecutive edges in the concept lattice. In other words, a pathway
is a sequence Y0 ! Y1 ! ::: ! Yn, where Y0 is the intent of the top formal
concept and for all 0 i < n, Yi ! Yi+1 is an association association rule
of the Luxenburger basis. Given a node of the concept lattice, there are as
many approximate association rules of the Luxenburger basis whose antecedent
is the intent of this node, as are the children nodes of this node in the concept
lattice. Between two approximate association rules having the same antecedent,
the one with highest support is considered rst. For instance, let a pathway
p1: I5=42 ! fI1=9, I3=25g holds with a support of 4% and a pathway p2:
I5=42 ! fI2=19, I3=28g holds with a support of 6%. In the aim to extract
information I1 to I5 from a candidate invoice image, and supposing that I5=42
is the lattice top node's direct child node which holds the highest support value,
prototype region R42 is visited rst in order to nd information I5. Then, using
pathway p2, prototype regions R19 and R28 are visited for nding information
I2 and I3 respectively. When, an information Ii is not found in a prototype
region given by pathway p2, so p1 may be used to nd it. Thus, all approximate
association rules given by the Luxenburger basis are used for information I1 to
I5 localization and extraction. In systems, such as, CREDO [
To extract the textual information of interest, we perform an optical character recognition (OCR) engine on prototype regions, using the pathways determined in the previous step. Recall that a pathway is a sequence Y0 ! Y1 ! ::: ! Yn, where Y0 is the intent of the top formal concept and for all 0 i < n, Yi ! Yi+1 is an approximate association rule of the Luxenburger basis. It should be noted that each node Y in such a sequence represents a set of predicates \Ii=j" indicating that information Ii belongs to prototype region Rj . First, the set of pathways is ordered by descending support value of the intents. Then, in each node given by a pathway, an OCR engine is performed on each prototype region in order to extract the corresponding information Ii. In formal language theory, a regular expression is a sequence of characters that de nes a search pattern, mainly for use in pattern matching with strings. For each sought information Ii, a regular expression is built and then used to check whether the extracted string (by the OCR engine) matches with the given information.
In the literature, approaches such as in [
In this paper, the task of text extraction is done with a free OCR engine named Tesseract OCR (https://github.com/tesseract-ocr). Tesseract OCR was chosen because it is a free software providing a JAVA API. In this paper, we focus on the textual information localization task in administrative document images. Indeed, OCR engine such as ABBYY OCR has a better recognition rate than free OCR such as Tesseract OCR, but both are not able to localize or pick out a given information such as the net amount in invoice images. Their task is just to transform, as e ciently as possible, the text contained in images into plain text. In this work, we propose to combine the proposed localization approach (based on clustering analysis and navigation in a concept lattice) with any OCR engine in order to extract a given information in document images without browsing and recognizing the entire images.
We achieved an experiment in order to test the proposed model for textual information extraction in real-world invoice images. The experiment consists in extracting information I1 to I5, in the set of 1000 real-word invoice images (Section2.1). Despite the fact that the approach was trained and tested with good results on the synthetic data, in this section we present test results of the approach on real-world invoice images. Indeed, the corpus of real-world invoice images contains some noise which is not present in the synthetic invoice images. The real-world invoice images may contain colored images such as a logo, shadow areas and handwritten text. Additionally, they may be scanned with poor quality and may present distortion. Thus, the corpus of real-world invoice images seems to us to be quite interesting for testing the proposed textual information localization and extraction model. We performed two types of extraction: 1. from full images: OCR is performed on the entire page images regardless to speci c regions; 2. from prototype regions, using the pathways presented in Section 3: OCR is performed only on image sub-regions, using the pathways.
To perform OCR on images, the JAVA library of the free OCR engine named Tesseract in its 3.02 version is used. We considered two measures: 1. the rate of correct information among the total number of sought information (recall), 2. the rate of correct information among the total number of detected information (precision).
On the one hand, a sought information is considered detected, if a string which
matches the corresponding regular expression is found. On the other hand, a
sought information is considered correctly extracted, if the extracted textual
information corresponds exactly to the visual information that should be read
in the image. For instance, let 'net amount' be a sought information and assume
that the net amount is 107e in the invoice image. During the process, if the
retrieved information is \101e", the net amount will not be considered correctly
extracted because the real net amount mentioned in the original invoice image is
\107e". The results are presented in Table 3. On the one hand, despite the fact
that according to [
We presented a (prototype) region-based model for localizing and extracting
textual information in document images. Experimental results show that the
proposed model improves signi cantly the correctness of a textual information
extraction process based on an OCR engine. This model is constructed in four
steps:
1. produce synthetic invoice data from real-world invoice images containing the
textual information of interest, along with their spatial positions;
2. partition the produced data;
3. derive the prototype regions from the obtained partition clusters;
4. derive pathways for browsing through the prototype regions, from the
concept lattice of a suitably de ned formal context;
The Step 1 is important when one has to extract information from a previously
unseen invoice image. Indeed, if some information of such an invoice image are
not retrieved, then a synthetic representation of the considered invoice can be
produced, and this triggers incremental updates of the synthetic data sets, the
prototype regions, and the concept lattice. Our future work will focus on these
update processes, and compare them with those proposed in [
This work was partially carried out within the project ClustOverlap supported by Reunion Island Region - grant DIRED 20140704. The authors are also very grateful to the 3 anonymous reviewers for their valuable comments.