TL;DR
This paper introduces a novel method for automatically extracting data from line chart images, even those with occluded or differently styled lines. By formulating line tracing as a minimum-cost-flow problem optimized with linear programming, the approach achieves state-of-the-art accuracy across multiple datasets without requiring explicit figure legends.
What Problem Does This Paper Address?
The web is awash with visual data presented in charts, but extracting the underlying numerical information can be a tedious manual process. While automated chart parsing systems exist, they often struggle with complex scenarios like overlapping lines, various line styles (dashed, dotted), and the absence of explicit legends or axis tick marks, which are crucial for accurate data recovery. This paper aims to bridge this gap by providing a robust, automated method for parsing line charts, making their data more accessible for analysis and reuse.
Methods
The core of this work lies in a two-stage approach:
- Semantic Segmentation: A modified FastFCN network with an EfficientNetB3 backbone is trained to predict pixel-wise probability maps for different line styles (solid, dashed, dash-dotted, dotted), as well as for legend and tick mark components. This provides a rich representation of the chart's visual elements.
- Linear Programming for Line Tracing: Instead of tracing lines sequentially, the authors formulate the problem as a graph-based minimum-cost-flow problem. Pixels with high line probability are treated as nodes, and connections between adjacent pixels form edges. A cost function, incorporating terms for color consistency, style consistency, foreground probability, and smoothness, is optimized using linear programming. A novel occlusion model is also introduced to handle overlapping lines by considering occlusion status at each connection point. This simultaneous optimization of all lines is a key differentiator from prior sequential methods.
Finally, Value Extraction involves using OCR to read text labels and estimating axis scales (using tick marks if available, or text label bounding boxes otherwise). This allows mapping the traced pixel coordinates to numerical values.
Datasets
The authors utilize a combination of synthesized and real-world datasets:
- Synthesized Datasets:
- CHART2019-S (CH-S): A dataset from a competition, used for evaluating line charts.
- ExcelChart400K (EXC): A dataset generated by crawling public Excel files.
- SYN: A newly generated dataset with diverse drawing styles, layouts, and line styles, including complex backgrounds.
- Real Image Datasets:
- FigureSeer (FS): A dataset of line charts crawled from CiteSeerX, used for evaluating line chart analysis.
- ICPR-2020-CHART-UB PMC (PMC): A dataset from a competition, including bar and line charts.
- GOV: A newly collected dataset by crawling government websites, featuring varied text and color variations.
Key Insights and Ideas
- Linear Programming for Simultaneous Line Tracing: Framing line tracing as a global optimization problem using linear programming, rather than a sequential dynamic programming approach, significantly improves robustness, especially with occlusions.
- Explicit Occlusion Modeling: The introduction of an occlusion model within the LP framework directly addresses the challenge of overlapping lines, a common issue in real-world charts.
- Relaxing Legend/Tick Mark Dependency: The method's ability to perform well even without explicit legends or tick marks (though it uses them for increased precision when available) makes it more broadly applicable.
- Unified Segmentation Network: Using a single semantic segmentation network for various line styles and components simplifies the pipeline and improves generalization.
Key Results
- Segmentation Performance: The proposed method (FastFCN+B3) achieved an average F1 score of 67.3% on line component segmentation across all datasets, significantly outperforming prior methods like FigureSeer and ChartOCR.
- Value Extraction Accuracy: The paper reports the percentage of charts correctly parsed with varying error tolerances. For instance, at a 5% error tolerance, the accuracy ranged from 22.6% to 46.2% across datasets, with higher performance on synthesized data.
- Efficiency: The segmentation step is fast (under 1 second per image), and while LP processing time scales with the number of lines, it remains efficient for a reasonable number of lines (e.g., 0.9s for 2 lines).
Limitations and Future Work
- Jagged Lines and Complex Backgrounds: The method struggles with charts containing jagged lines due to fixed subsampling of the x-range and with complex patterned backgrounds that can lead to segmentation failures.
- OCR Dependency: The accuracy of value extraction is inherently tied to the performance of the OCR engine.
- Future Work: The authors suggest several avenues for improvement, including:
- Associating text with detected components.
- Handling date values and other specialized axis scales.
- Addressing axis multipliers and range skipping.
- Improving robustness to complex backgrounds through more extensive data augmentation.
- Optimizing LP solver performance by utilizing multi-core CPUs.
Summary updated