Introduction
Motivation
기존의 Table Structure Recognition 방법론들은 다음과 같이 spanning cells을 포함하는 complicated tables를 정확히 인식하지 못한다는 문제점을 가지고 있습니다.
논문에서는 Table Structure Recognition task를 그래프의 edge prediction problem로 재구성하고 이를 위한 새로운 Graph Neural Network를 제안함으로써 이 문제를 해결하고자 하였습니다.
Contributions
- PDF 파일에서의 Table Structure Recognition을 위한 새로운 Graph Neural Network인 GraphTSR 모델을 제안하고 SOTA 성능(2019년 기준)을 달성
- 과학 논문에서 추출한 15,000개의 table들을 통해 구축한 SciTSR 데이터셋을 배포
Related Works
Methods
기존의 Table Structure Recognition 방법론들은 Rule-base Methods와 Data-driven Methods로 구분할 수 있습니다.
- Rule-base Methods : 주로 ruling line을 찾아 table strucutre를 구성하는 방식으로 발전
- Data-driven Methods : Image를 통해 특정한 format으로 예측해내는 방식으로 발전
- DeepDeSRT : Table Structure Recognition 문제를 image semantic segmentation 문제로 보고 column과 row의 위치를 인식하도록 함
- Image-to-text : 기본적으로 Transformer의 encoder-decoder 구조로 table image를 encoding하고 이를 decoder의 input으로 줌으로써 HTML과 같은 text 형태의 sequence들을 예측
- 최근에는 SPADE, BROS와 같이 언어모델과 Graph Generator를 이용한 방법론들이 나타남(이 논문이 나오고 나서)
Datasets
Table Structure Recognition을 위한 기존의 데이터셋들은 다음과 같이 두개가 있습니다.
- ICDAR-2013 dataset : PDF 문서에서 table을 추출하여 만든 데이터셋으로 156 개의 비교적 작은 수의 데이터로 구성되어 있어 학습용 데이터로 사용하기에 한계가 있음
- TableBank : large-scale의 Table Detection과 Table Structure Recognition 데이터셋으로 구성되어 있지만 column coordinates information이 없는 데이터셋
Proposed Method
Problem Definition & Method
논문에서는 table의 각 cell들을 vertex로 삼고 최종적으로 “vertical” 또는 “horizontal”의 label을 갖는 edge들을 예측하도록 문제를 정의하였습니다. (실제로는 “no relation”까지 총 3개의 label 중 하나로 예측하도록 하는 classification 문제)
논문에서는 다음과 같은 (a), (b), (c), (d)의 총 4단계로 문제를 나누어 Table Structure Recognition 문제를 해결했습니다.
- Pre-processing : PDF로부터 cell의 내용과 일치하는 bounding box를 추출하는 과정(이 때, OCR과 같은 기술을 사용하는 것이 아니라, PDF는 비교적 깨끗한 이미지이므로 rule-based 방식으로 쉽게 추출할 수 있었다고 합니다.) — (a)
- Graph construction : 추출한 cell들을 각각 그래프의 vertex로 삼고 이웃 vertex들을 연결하여 edge로 삼는 과정 — ( b)
- Relation prediction : 논문에서 제안하는 Table Structure Recognition을 위한 Graph Neural Network인 GraphTSR을 통해 labeled relations을 갖는 graph를 예측하는 과정 — (c)
- Post-processing : labeled graph를 통해 table structure를 복구하는 과정 — (d)
Graph Construction
table의 각 cell들에 대해 모든 edge를 구성하고 이들에 대한 label을 모두 예측하는 것은 의 시간복잡도가 걸리는 비효율적인 일입니다.
따라서, 논문에서는 이 문제를 해결하고자 KNN(K Nearest Neighbors) 방법을 통해 K개의 근처 cell들에 대해서만 edge를 구성하도록 하여 시간복잡도를 까지 줄였습니다.
GraphTSR
논문에서 제안한 Table Structure Recognition을 위한 Graph Neural Network는 다음과 같은 형태로 구성됩니다. 기본적으로 transformer와 유사한 구조를 가지지만 세부적으로는 조금 다릅니다.
- Vertex and edge features : graph의 vertex와 edge들의 feature를 추출하는 과정으로 이 과정에서 추출되는 feature들은 다음과 같습니다.
[Vertex features]
1. size of cells
2. absolute locations
3. relative locations
[Edge features]
1. distance between cells including Euclidean distance (absolute)
2. distance between cells including x-axis distance (absolute)
3. distance between cells including y-axis distance (absolute)
4. distance between cells including Euclidean distance (relative)
5. distance between cells including x-axis distance (relative)
6. distance between cells including y-axis distance (relative)
7. overlap of cell pairs along x-axis
8. overlap of cell pairs along y-axis
- Graph Attention : Edge-to-Vertex Attention Blocks과 Vertex-to-Edge Attention Blocks에 들어가는 Attention으로 이웃 노드들간의 global dependency가 아닌 local dependency를 Attention하는 Layer입니다.
Dot-product Attention과 비교해보면 다음과 같이 Graph Attention은 이웃 노드들에 대해서만 Attention을 수행하는 것을 확인할 수 있습니다. (왼쪽이 Dot-product Attention, 오른쪽이 Grpah Attention)
- Graph attention blocks : Graph attention blocks는 vertex들을 encoding하는 Edge-to-Vertex Attention blocks과 edge들을 encoding하는 Vertex-to-Edge Attention Blocks으로 구성됩니다.
두 개의 Attention blocks 모두 Graph Attention과 Layer Normalization, Feed Forward 등을 거치는 것은 동일하지만 Graph Attention의 key, value, query가 다릅니다.
예를 들어, Vertex-to-Edge Attention Blocks의 경우, query는 edge의 features를 사용하지만 key, value는 vertex의 feature를 사용합니다.
- Linear & Sofrmax : 마지막으로 encoding된 edge vector들을 “vertical”, “horizontal”, “no relation” 중 하나로 예측하는 과정입니다.
이 때, 위의 Figure 3에서 확인할 수 있듯이 encoding된 vertex vector들은 사용되지 않습니다.
SciTSR Dataset
SciTSR Dataset은 PDF 파일에서 추출한 15,000개의 table을 포함하는 데이터셋입니다.
데이터셋을 구성한 과정은 다음과 같다고 합니다.
- LaTeX source file들을 크롤링
- LaTex code에서 ‘\begin{table}’, ‘\end{table}’과 같은 키워드를 통해 table 추출
- ‘\\’, ‘&’와 같은 기호를 통해 table의 structure label 추출
- 이 때, ‘\multirow{}’, ‘\multicolumn{}’과 같은 키워드들은 spanning cell을 의미한다고 보고 parsing했다고 합니다.
이를 통해서 최종적으로 구축된 SciTSR dataset의 통계량은 다음과 같습니다.
위의 표2에서 SciTSR-COMP는 spanning cell들을 포함하는 complicated table로 구성된 데이터셋입니다.
Experiments
Baseline Experiments & Results
논문에서는 Tabby, DeepDeSRT, Adobe SDK. 총 3개의 baseline들과 논문에서 제안한 GraphTSR의 성능을 비교하는 실험을 진행합니다.
위의 표에서 확인할 수 있듯이 기본적으로 다른 baseline들보다 GraphTSR의 성능이 우수한 것을 확인할 수 있습니다.
(참고로 비교적 최근 논문인 BROS 논문에서는 SciTSR 데이터셋에 대해 0.997의 성능을 달성하였다고 합니다.)
또한, 논문의 저자들은 SciTSR 데이터셋을 학습셋으로, ICDAR-2013 데이터셋을 평가셋으로 삼았을 때의 성능이 똑같은 셋팅에서 DeepDeSRT보다 성능이 좋았으므로 GraphTSR 모델의 일반화 성능이 우수하다고 주장하고 있습니다.
Results on complicated tabels
아래의 표는 SciTSR 데이터셋에서 complicated table에 해당하는 데이터들만으로 실험한 결과를 보여줍니다.(complicated table이 없는 데이터셋을 학습 데이터셋으로, complicated table로만 구성된 대이터셋을 평가셋으로 사용)
다른 baseline들에 비해 GraphTSR이 complicated table을 비교적 잘 인식함을 확인할 수 있습니다.
또한, 논문의 저자들은 아래의 그림을 통해 다른 모델들과 달리 GraphTSR은 spanning cell도 잘 표현함을 실제 예측 결과를 통해 보여주고 있습니다.
Impact of the number of attention blocks
논문에서는 Graph Attention Blocks의 수가 모델의 성능에 어떠한 영향을 끼치는지 확인하기 위해 Block의 수에 대한 성능을 측정하였습니다.
Graph Attention Blocks의 수가 늘어날수록 성능이 좋아지는 것을 확인할 수 있습니다.
특히, 이러한 현상은 Recall에서 두드러지는데, 저자들은 block의 수가 너무 적으면 모델이 주변 노드들을 보수적으로 연결하여 대부분의 edge들을 “no relation”으로 예측한다고 주장합니다.
Conclusion
이 논문은 complicated table의 구조를 표현할 수 있는 graph 형태를 정의하고 GraphTSR이라는 Graph Neural Network를 제안하여 이를 예측하도록 했습니다.
저는 이 논문이 문제를 정의한 방식과 Graph Attention 방법이 흥미로웠습니다.
또한, 이전에 읽었던 SPADE, BROS 논문들의 이론적 배경이 이 논문을 기반으로 했을거 같다는 생각도 하게 되었습니다.
앞으로 로민에서 Table Structure Recognition을 할 일이 많을 것으로 예상하기에 이러한 부류의 방법론들에 대해 조금더 연구해보는 것이 좋겠다는 생각을 하게 되었습니다.
Share article
