言語処理学会 第25回年次大会 発表論文集 (2019年3月)

User-Assisted Tabular Extraction in Japanese Invoice
Vincent Leonardo
Sorami Hisamoto

Yuichiro Shimizu
Yoshitaka Uchida

Kensuke Masugata
Kazuma Takaoka

Works Applications Co., Ltd.
{leonardo v, shimizu yu, masugata k, hisamoto s, uchida yo, takaoka k}@worksap.co.jp

Abstract
We present a user-driven approach to extract tabular information from Japanese business document. Following the previous researches Bart and Sarkar (2010)[1] of the same task, we
further extend the approach to cover Japanese business document. The method utilizes a set of fields (on the first row of atable) provided by the user to extract the remaining rows thatmatch the structure of the provided fields set. Firstly, a setof potential field candidates is generated and evaluated against
the user-selected fields based on an extended set of spatial features. Another level evaluation is performed to verify the structure similarity based on inter-field spatial relationship. Bothevaluation models were trained through Automated Machine
Learning (AutoML). On top of that, we added a simple reevaluation scheme which proven to reduce the false-negatives
case. Pairing it up with the evaluations, we achieved an accuracy improvement of 4.56%. We demonstrate that this method
is able to handle a wide variety of tabular structure regardlessof the language of the documents.

1

Introduction

Invoice processing is a common business operation performed
regularly. Although a large number of businesses have adopted
the usage of electronic invoices, there are still a handful of companies that use paper invoices. This is especially true in a country such as Japan, where ink stamp is still widely preferred overdigital signature as a proof of authenticity. On the other hand,
the record keeping and processing have mostly been digitized(as Enterprise Resource Planning system) due to the benefit ofstorage efficiency and ease of computation. This introduces theneeds of a method to digitize all paper records.
With the lack of a reliable extraction system, most companies perform such extraction task manually. A survey [10]shows that manually processing an invoice is estimated to costaround 9 Euros and can result in an average error rate of 5%.
A separate survey [19] shows that the adoption of automatic
invoice processing may reduce the cost to around 2 Euros per
invoice.
In this paper, we propose a user-assisted method for extracting tabular information in business documents. The user first
selects a set of fields; each field corresponds to a column ofinterests to the user and the set of fields represents a single
row of entry within the tabular structure. The system will utilize the underlying structural relationship between the fields tosearch for other combinations of fields that match the structureof user-selected fields. The red boxes in Figure 1 represent theuser selections and the green boxes are fields combinations withsimilar structure inferred by the system.

2

Related Works

While there exists a plenty of researches (reviewed in [2, 3,
5, 9, 20]) on table extraction, most hold strong assumptions
on certain visual cues of a table. This includes table lines,
white spaces, columns/rows text alignments, heuristic rules,
keywords matching and database of pre-defined layout structure; or any combination of them. Furthermore, most of theresearches mainly focus on extracting tables from academic
papers. Such approaches are hard to be applied to invoice
documents where there is a large variety of layouts depending

Figure 1: Conventional table structure: (a) common single-row
linear structure (b) multi-line linear structure [multi-line input](c) multi-line linear structure [single-line input]. Complex tabular structure: (d) an extreme case of complex tabular structure (e)optional columns and variations in alignment & text size. [red:input, green: targets]on the nature of the business. There are also some table extraction methods that rely on the underlying document format
such as PDF, XML or HTML (e.g., PdfExtra[4], TEXUS [14],Tabby 1 [15], tabula 2 , and camelot 3 ).
A more recent researches [13, 8] model representation of theentire page contents through Convolutional Neural Network.
Both methods are able to handle variation in layouts. They
also show improvement over state-of-the-art sequential information extraction framework in tackling table extraction problem. However, due to the nature of deep learning, it requiresa large amount of training data (25,200 and 12,000 in [13] and[8] respectively). Unfortunately, there is no open-source dataset
on invoice table extraction and creating such a large dataset on
our own is very costly.
All these approaches extract the entire table from the document without user interaction and let the downstream task decides which information to present to the user. There are otherresearches [1, 6] that focus on user-driven extraction which extracts only the relevant results based on user query. These
approaches are able to handle layout variations and also extract table based on user-specified requirements; which makethe system more generalizable to various documents.
The state-of-the-art method in [6] formalizes user selection asa query graph and extract similar patterns from the document
through graph mining. Although the methods show accuracy
improvement over [1], they utilize textual features as feature
vectors which is language sensitive. The textual features suchas string length, number of words and words separation is aweaker representation in Japanese document due to the lackof spacing in Japanese sentence. Some researches [7, 11, 17]
on various information extraction tasks touched on the differences in using linguistic features between English and Japanese
documents.
The method presented in this paper is an extension of thework presented in [1] where they demonstrate the effectivenessof extracting repeating pattern based on a set of user selected1

https://github.com/cellsrg/tabbypdf
https://tabula.technology/
3
https://camelot-py.readthedocs.io/2― 1137 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

Figure 2: Proposed tabular extraction flow

fields with only the perceptual cues. The authors also showthat the approach adapts well to the various form of documents
including receipts, medical entries, table of contents and search
results. This paper will focus on solving the issue presented in[1] where they are unable to handle missing field(s) which inturn causes the entire record to be missed. The missing fields
could be due to OCR errors or the content itself being optional.

3

Methodology

In this paper, we define tabular structure as a list of information organized in a common structure repeated verticallyalong the page(s). Such structure does not necessarily need to
be in the conventional table style, Figure 1(d)(e) show somevariations of unconventional layout.
We will use the same terminologies defined in [1]. An entry of the repeating structure is referred as record while all theitems of interest in the entry are referred as ﬁeld(s). The ﬁelds
are laid out in a consistent spatial structure across the records(within the document). A ﬁeld can be a single word returnedby the OCR system or a sequence of contiguous words in asingle line or multiple lines. For example, each box in Figure
3 is a ﬁeld/cell and a group of fields of the same colour is arecord/row.
In a conventional table structure, the term record is interchangeable with row, so does ﬁeld with cell

Figure 4: Illustrations of field candidates generations of a particular reference field (in red). (a) highlighted area in purple is thehorizontal overlaps region. Dashed-rectangles indicates all the basecandidates of the reference field. (b) blue lines depict inter-wordhorizontal-gap and a zoomed-view showing the gaps of contiguous
words. (c) highlighted areas in orange are the horizontal-expansion
range of each base candidates and the orange dotted-rectangle is asample of a horizontally-expanded candidate. (d) green boxes are
the 5 additional candidates generated through multi-line expansionof the candidate field 「スチールキャビネット 4W105W-FXP13」.

ity of a candidate pair ci , cj ∈ {Ci × Cj } matches the reference pair Ri , Rj . Finally, we will construct a set records
G0 based on intersecting matching candidate pairs (i.e. G0 =
{ci , cj } ∩ {cj , ck } ∩ · · · ∩ {cn−1 , cn } ).

3.1

Field Candidates Generation

3.1.1

Base Field Candidates (C b )We use the basic assumption that a target field will always
have horizontal overlaps with the reference field even if it is in
a non-linear structure. Therefore, we first select all the tokens(extracted by OCR) that have horizontal overlaps with the reference field as the base candidates (denoted as {Cib }ni=1 ). These
candidates can be a single word or contiguous words on a single line that falls within the horizontal-overlap area of reference
field (e.g. purple area in Figure 4(a)).

Figure 3: Records and fields illustration.

An overview of the processing steps (depicted in Figure 2) is
as follows. A scanned invoice is uploaded to the system which
will be processed through an OCR system. The OCR result ispresented to the user including the bounding box of each word.
The user will proceed with selecting word(s); forming fields ofinterest called reference ﬁelds denoted as {Ri }ni=1 where i is thefield identifier (e.g. “item-description”, “item-quantity”, etc.).
The set of fields will in turn form a reference record denoted
as Q. Based on such reference fields and records, the system
will find the remaining records called target records denoted
as {Gy }m
y=1 , where m is the number of remaining records tobe found in the document. The red boxes in Figure 3 are thereference fields and the remaining coloured boxes are the target
fields.
The system will first generate a set of field candidates
Ci = {ci1 , ci2 , ..., cix } for each reference field Ri (details in
3.1). We train a binary classifier to evaluate the probabilityof each candidate in Ci matching the Ri (discussed in 3.2).
We train another binary classifier to evaluate the probabil-

3.1.2

Horizontally Expanded Candidates (C h )The base candidate selection might not cover the entire
phrase within a single line due to the OCR results being inindividual words. We need to expand the candidates to theneighbouring words within a single line, the expanded candidates are denoted as {Cih }n
i=1 .
We first recursively expand the base candidates horizontally
based on the text size and neighbouring information. We refer
the horizontal distance of the closest edge of two tokens as
gap (illustrated with blue lines in Figure 4(b) . The breaking
condition is either of the following: 1) the horizontal-gap to
the next word is more than half of the character height; or 2)
the gap to the next word is larger or equal than the gap of thereference field to its neighbour dark-red line in Figure 4(b) ;or 3) the next word has horizontal overlaps the neighbour of
the reference field e.g. last entry in Figure 4(c), the next
word after “...D650×H700” is “1”, however “1” has horizontal
overlaps with “6”; the next word of reference field .

― 1138 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

Similar to Field-to-Field features, we compute the separation using all edges combinations. This not only gives
us the saliency of a field, but we also obtain information regarding the alignment of a field with respects to
its neighbours. This also serves as good features in verifying multi-line candidates (using the separation differenceof bottom neighbour). We compute such features using
the nearest neighbour in 4 directions which gives us 4 × 18
features:
C
N i

R
N i

Ex d − EyCi − Ex d

− EyRi ;9 feats.: (x, y) ∈ {l, c, r} & 9 feats.: (x, y) ∈ {t, m, b};d ∈ {lef t, top,right, bottom}
Figure 5: All edges spatial difference. (a) describes horizontal
differences between Ri and Ci [{l, c, r} in Eq. 1 ] and (b) describes
the vertical differences [{t, m, b} in Eq.1]

3.1.3

Multi-line Expanded Candidates (C m )There are some fields that can span multiple lines such as
item descriptions. For such fields, we also expand the candidates downwards using the C h . We simply sort C h based on its
y position in ascending order. We then construct the multi-line
candidates (denoted as C m ) by merging each subsequent lines
together up to (number of line in R) + 3 lines. The limit of
3 additional-lines is decided based on the observation of maximum line variation of a field type in our dataset, it also limits
the number of candidates the be evaluated in the next step.
Figure 4(d) shows an example of line expansion of a single candidate.

3.2

Evaluating Candidates

Once we obtain a set of field candidates Cim that could potentially match reference field Ri , we can evaluate their matching probability to obtain a subset of Cim that will be the target
ﬁeldi . We evaluate the candidate-reference pair based on thefeatures computed from the visual difference of each candidate
field against the reference field (referred as single-ﬁeld features,
described in section 3.2.1). On top of that, we also added a
re-evaluation algorithm to recovers some false negatives prediction (discussed in 3.2.3). The use of additional features andthe re-evaluation algorithm are the key points that serve toimprove the previous work [1].
Note that we only need to evaluate the candidates in C msince it also contains the C b and C h candidates. For the sakeof simplicity, we refer C m as C from this point onwards.

3.2.1

Single-Field Features

a. Field-to-Field Features
We crafted a set of features based on the coordinates difference between two fields. We included the center-x andmiddle-y of the boxes which will handle center aligned
fields. Instead of just computing basic edge-to-edge differences (distance of left edge of Ci against left edge of Ri
and so on), we compute all edge combinations differences.
Figure 5 illustrates the edge-to-edge relationship.
* l, c, r refers to left-x, center-x, right-x* t, m, b refers to top-y, middle-y, bottom-yC* Ee i refers to e-edge of Ci ; e ∈ {l, c, r, t, m, b}
ExCi −EyRi ;9 feats.: (x, y) ∈ {l, c, r} & 9 feats: (x, y) ∈ {t, m, b}

(1)

3.2.2

Candidate Evaluation

The features in a. and b. are combined and denoted as
f s (Ci , Ri ). We then train a single-field model M s (details in3.4) to obtain a probability of Ci matching Ri given f s (Ci , Ri ).
Given a threshold θ, we regardPositive prediction Ci+ ; if M s f s (Ci , Ri ) ≥ θ
Negative prediction Ci− ; otherwise

3.2.3

(3)

Missed-Candidate Re-evaluation

A false negative in single-field evaluation has large impact
on the overall result as the double-field evaluation will be performed only on candidates that are evaluated as positive bysingle-field evaluation (for optimal performance). As there arebound to be some false negatives from M s using f s (Ci , Ri ),we iteratively re-evaluate the negative-predictions Ci− with thepositive predictions Ci+ until there is no new Ci+ or no Ci−
left. This allows us to recover false-negative cases Ci− thathave a low probability of matching Ri but high probability ofmatching other candidate fields Ci+ .

3.3

Target Record Predictions

From the previous step in section 3.2, we manage to obtainsome set Ci+ that matches the reference fields Ri . With therecovery of some false-negatives candidates in 3.2.3, the next
step is to eliminate false-positive cases. We do so by validating
the relationship between a pair of candidate fields Ci+ , Cj+ tothe relation of reference fields pair Ri , Rj . The relationship validation is performed through binary classification (using modelM d ) using a feature set f d (Ci+ , Cj+ ), (Ri , Rj ) described in
3.3.1. A candidate pair is said to match a reference pair when
the probability of M d is greater than some threshold γ.
The pair-relationship validation will produce multiple candidate pairs that correspond to some reference field pairs. We
will combine some intersecting pairs to generate record predictions G0 . Two pairs of candidate fields are said to intersectwhen they share one common field candidate. For example,++ +the pair (c+i , cj ) intersects (cj , ck ) as they share the common++ +0field candidate c+j . A predicted-record g = {c1 , c2 , . . . , cn }is generated by finding all intersecting candidates across thefields.

3.3.1

Including the existence of vertical & horizontal overlaps,
there will be 20 field-to-field features.
b. Neighbours-to-Neighbours Features
In [1], the authors compute the separation of Ci (against
its nearest neighbour) to determine its perceptual-saliency.
However, there is a possibility that the Ri itself is not
perceptually salient. Instead, we compute the difference inCthe separation between Ci and its neighbour Nd i againstR
the separation between Ri and its neighbour Nd i ; whered ∈ {lef t, top, right, bottom}.

(2)

Double-Field Features

We use the difference between the edges distance of Ci to Cj
and Ri to Rj . In [1], only the distance of the same edge (i.e.
left-edge of Ci to left-edge of Cj ) is computed. As mentioned
in b., we can obtain better information based on inter-fieldalignment from all edges distance (i.e. left-edge of Ci to centerx of Cj , etc.). Therefore, we formulate 18 features representing
such edge differences:― 1139 ―CR
f d (Ci , Cj ), (Ri , Rj ) = ExCi − Ey j − ExRi − Ey j ;(4)

9 features: (x, y) ∈ {l, c, r} & 9 features: (x, y) ∈ {t, m, b}

Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

Table 1: Comparison with previous work (in %) against our
method in stages. Same-edge refers to using the difference of thesame edge (i.e. left-to-left, right-to-right, etc.) only. All-edges use
edges combination as depicted in Figure 5. Single-Field (SF): refer
to 3.2.1 and Re-evaluation: refer to 3.2.3

FeaturesSame-edge(as used in [1])All-edges(Our method)

3.4

Method

Prec.

Rec.

F1

SF Only
SF+Re-eval
Full Method
SF Only
SF+Re-eval
Full Method

86.34
81.14
94.81
90.95
86.56
96.90

68.98
91.81
90.57
89.83
94.29
93.05

79.69
86.15
92.64
90.38
90.26
94.94

Training

All the features described in 3.2 are normalized against thewidth or height of the page (i.e. all features are in the form of
0-100% of the page size).
The training inputs are constructed from document images
with annotated records, each having at least 2 records. Insteadof just using the first record against other records, we construct
the training pairs from all combinations of records. This allows
us to not only learn the relationship of the first record (i.e. user
input) against other records but also the inter-record relationship which is useful for re-evaluation as discussed in section
3.2.3.
In [1], authors train a Bayesian model to evaluate a set ofcandidate fields as a whole by defining a custom log-likelihood.
In this paper, we focus on algorithm improvement and features
engineering; to provide enough information to learn about thestructure of the fields. We leave the model selection to an
automated process.
We adopt Automated Machine Learning (AutoML), specifically using the Tree-based Pipeline Optimization Tool
(TPOT4 )[12]. TPOT uses genetic programming (GP) to select the best combination of features, model and parameters.
We train two pipelines through TPOT; one as the field-to-fieldmodel M s and another for the field-pair model M p .

4

Experiments

4.1

DatasetWe use real-world Japanese invoice images obtained fromWorks Applications Co., Ltd.5 The training set consists of 18
invoice images with various layout structure including both linear & non-linear. Each invoice contains 2 to 11 records totallingup to 92 records. Each record consists of 2 to 6 fields. Notethat the number of fields across the records in a single document
might vary due to some field being optional (i.e. not present insome records). With the training set construction described in
3.4, we constructed 1245 positive and 33368 negative samples
from the 18 invoices.
We prepare a separate dataset of 27 invoices for evaluation
purposes. All these invoices are from different vendors, hence
have a great variation of layout. And none of the layouts exists
in the training dataset. There are 2-23 records per invoice; 128
records in total. There are 2 to 6 fields in a single record.
For evaluation purpose, we simply use the first record on eachdocument to represent user input and attempt to detect theother records; simulating the real-world user operation. This
gives a split of 27 input records and 101 records to be tested.

4.2

Results

We evaluated our approach in stages from Single-Field evaluation (SF Only), Missed-Candidate Re-evaluation (SF + Reeval) and the Double-Field evaluation (Full Method).
As observed in Table 1, introducing more edges relation can
increase the performance. We also observed that recovering
the false negative cases (improving Recall) through candidates
re-evaluation will affect the precision (introducing some false
positives). However, after running the double-field evaluation
45

https://github.com/EpistasisLab/tpot
https://www.worksap.co.jp(full method) the precision can be improved while maintaining
the recall, hence achieving better overall performance.
From the end-user point of view, we manage to retrieve 96
out of the 101 records (95%). 14 of the 96 retrieved records are
partially retrieved record (missing 1-2 fields).

5

Discussions

We have demonstrated the usefulness of using more extensive
visual features in improving the accuracy of tabular extractiontask. The proposed algorithm also solves the problem in handling missing/optional fields as faced by [1]. Partial records
only require the user to fix 1-2 cells while not retrieving therecord (problem in [1]) would require the user to manually fix
the entire row.
Unfortunately, the candidates re-evaluation is unable to fully
recover all candidates in some cases. [6] presented a missingfield recovery method that uses word gaps and area on English
invoices. In future, we would like to incorporate a similar recovery method but with less reliance on word gaps as there is
no word spacing in the Japanese language.
We would also like to explore the feasibility of incorporating
textual features as implemented in [6], but specific to Japanese
language context. Few possible ways in learning the Japanese
textual features include usage of Sudachi [18] and/or various
Japanese word vectors such as nwjc2vec [16].

References[1] E. Bart, P. Sarkar. Information extraction by finding repeatedstructure. In Proc. of the 9th IAPR International Workshop
on Document Analysis Systems, DAS ’10, 2010.
[2] A. C. e Silva, A. M. Jorge, L. Torgo. Design of an end-to-end
method to extract information from tables. IJDAR, 8, 2006.
[3] D. W. Embley et al. Table-processing paradigms: a research
survey. IJDAR, 8, 2006.
[4] M. Fan, D. S. Kim. Table region detection on large-scale PDF
files without labeled data. CoRR, 2015.
[5] M. Göbel et al. Icdar 2013 table competition. In 2013 12th
ICDAR, 2013.
[6] T. Kasar, T. K. Bhowmik, A. Belaı̈d. Table information extraction and structure recognition using query patterns. In
2015 13th (ICDAR), 2015.
[7] A. Katsuta et al. Information extraction from english &japanese resume with neural sequence labelling methods. In
In Proc. of the 24th Annual Meeting of the Association for
Natural Language Processing, 2018.
[8] A. R. Katti et al. Chargrid: Towards understanding 2d documents. In Proc. of the 2018 Conference on EMNLP, 2018.
[9] S. Khusro, A. Latif, I. Ullah. On methods and tools of tabledetection, extraction and annotation in pdf documents. J.
Inf. Sci., 2015.
[10] B. Klein, S. Agne, A. Dengel. Results of a study on invoicereading systems in germany. In Document Analysis Systems
VI, 2004.
[11] T. T. N. Le et al. Extracting indices from japanese legal
documents. Artiﬁcial Intelligence and Law, 23, 2015.
[12] R. S. Olson et al. Evaluation of a tree-based pipeline optimization tool for automating data science. In Proc. of GECCO
2016, 2016.
[13] Y. Qian et al. GraphIE: A graph-based framework for information extraction. CoRR, 2018.
[14] R. Rastan, H.-Y. Paik, J. Shepherd. Texus: A task-based
approach for table extraction and understanding. In Proc. ofthe 2015 ACM Symposium on Document Engineering, 2015.
[15] A. Shigarov et al. TabbyPDF: Web-based system for PDF
table extraction. In Information and Software Technologies,
2018.
[16] H. Shinnou et al. nwjc2vec: Word embedding data constructed from NINJAL web japanese corpus. Journal of Natural Language Processing, 2017.
[17] K. Sudo, S. Sekine, R. Grishman. Automatic pattern acquisition for japanese information extraction. In Proc. of the 1st
International Conference on Human Language Technology
Research, HLT ’01, 2001.
[18] K. Takaoka et al. Sudachi: a japanese tokenizer for business.
In Proc. of the 11th LREC, 2018.
[19] V. Voutilainen, T. Pento. Electronic invoice processing as atool for cost reduction. Frontiers of e-Business Research,
2003.
[20] R. Zanibbi, D. Blostein, R. Cordy. A survey of table recognition: Models, observations, transformations, and inferences.
Document Analysis and Recognition, 7, 2004.

― 1140 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.