Rustで学術論文からテキストを抽出する #8 - Hough変換による表領域の抽出②

Summary

• Hough変換の結果から，表を構成する横線を抽出して表領域を確定する
• 上記のアルゴリズムのためのHough変換のチューニングが大変
• SVG画像と数式は雑に除外してOK

GiHub -> https://github.com/akitenkrad/rsrpp
crates.io -> https://crates.io/crates/rsrpp

ToDo

• pdftotextで論文から単語単位のテキストと位置情報を取得する (Word,Line,Block,Page)
• テキストの属性 (本文, タイトル, 脚注, etc.) を判定する
  • テキストが含まれるエリアを抽出する
    • 2段組みを扱えるようにする
  • セクションのタイトルを識別する
• 図表に含まれるテキストを除外する
  • 表を除外する
    • PDFを画像に変換
    • 画像処理で表の位置を特定

今日のファイル

rsrpp
├── Cargo.toml
├── rsrpp
│   ├── Cargo.toml
│   └── src
│       ├── lib.rs
│       └── parser
│           ├── mod.rs <-- today
│           ├── structs.rs <-- today
│           └── tests.rs
└── rsrpp-cli
    ├── Cargo.toml
    └── src
        └── main.rs

前回までのあらすじ

前回：Rustで学術論文からテキストを抽出する #7

PDFを画像に変換してHough変換により直線を抽出しました．
今回は抽出した直線の中から表に該当する領域を検出する方法を考えます．

表の領域の特性

アルゴリズムの方針は至ってシンプルです．
表は矩形なので，表から検出された横方向の直線は最上段と最下段で必ず同じ長さになります．
つまり，検出された横方向の直線からほぼ同じ長さの直線の組み合わせを抽出し，それらの組のうち最も上と下に位置するものを拾ってくれば，表を構成する直線2本が定ります．
あとはそれぞれの直線の始点と終点の座標を参照すれば表の領域が求まります．

例外的に全く同じ幅の表が同じページ内に2つ以上ある場合はアルゴリズムが誤作動を起こしますが，レアケースとして無視します．

このアルゴリズムにおいて重要なのは，表を構成する横方向の直線が正しく検出されていることと，ノイズになっている表と無関係の直線が多すぎないことです．

この調整のために前回のHough変換ではパラメータを細かくチューニングしました．チューニングの過程は割愛しましたが．

では，Rustでの実装です．

表領域を抽出するアルゴリズム

前回はHough変換部分のみを掲載しましたが，こちらが関数の全体像になります．
画像のパスを受け取って引数のtables: &mut Vec<Coordinate>に抽出した表の座標を格納するようにしています．

//extarct tables以降が直線の座標から表領域を抽出している部分になります．前述のアルゴリズムを素直に実装しています．

なお，Hough変換で抽出される直線は必ずしも水平・垂直なものだけではないので，最初に横方向以外の直線は除外するようにしています．

rsrpp > rsrpp > src > parser > mod.rs

fn extract_tables(image_path: &str, tables: &mut Vec<Coordinate>, width: i32, height: i32) {
    // read the image
    let _src = imgcodecs::imread(image_path, imgcodecs::IMREAD_COLOR).unwrap();
    let mut src = Mat::zeros(width, height, _src.typ()).unwrap().to_mat().unwrap();

    let dst_size = opencv::core::Size::new(width, height);
    // reshape
    imgproc::resize(&_src, &mut src, dst_size, 0.0, 0.0, imgproc::INTER_LINEAR).unwrap();

    // convert the image to grayscale
    let mut src_gray = Mat::default();
    imgproc::cvt_color_def(&src, &mut src_gray, imgproc::COLOR_BGR2GRAY).unwrap();

    // apply Canny edge detector
    let mut edges = Mat::default();
    imgproc::canny_def(&src_gray, &mut edges, 50.0, 200.0).unwrap();

    // apply Hough Line Transform
    let min_line_length = src.size().unwrap().width as f64 / 10.0;
    let mut s_lines = Vector::<Vec4f>::new();
    imgproc::hough_lines_p(
        &edges,
        &mut s_lines,
        2.,
        PI / 180.,
        100,
        min_line_length,
        3.,
    )
    .unwrap();

    // extract tables
    let mut lines: Vec<(Point, Point)> = Vec::new();
    for s_line in s_lines {
        let [x1, y1, x2, y2] = *s_line;

        let a = (y2 - y1) / (x2 - x1);
        if a.abs() > 1e-2 {
            continue;
        }
        let len = ((x1 - x2).powi(2) + (y1 - y2).powi(2)).sqrt() as i32;
        if len < src.size().unwrap().width / 4 {
            continue;
        }
        let line = (Point::new(x1, y1), Point::new(x2, y2));
        lines.push(line);
    }

    let mut lines_gpd_by_len = HashMap::<i32, Vec<(Point, Point)>>::new();
    for line in lines {
        let mut len = ((line.0.x - line.1.x).powi(2) + (line.0.y - line.1.y).powi(2)).sqrt() as i32;
        for key in lines_gpd_by_len.keys() {
            if (len - key).abs() < 3 {
                len = *key;
                break;
            }
        }
        if !lines_gpd_by_len.contains_key(&len) {
            lines_gpd_by_len.insert(len, Vec::new());
        }
        lines_gpd_by_len.get_mut(&len).unwrap().push(line);
    }

    for line in lines_gpd_by_len.values() {
        if line.len() < 3 {
            continue;
        }
        let mut x_values: Vec<f32> = Vec::new();
        let mut y_values: Vec<f32> = Vec::new();
        for l in line {
            x_values.push(l.0.x);
            x_values.push(l.1.x);
            y_values.push(l.0.y);
            y_values.push(l.1.y);
        }
        x_values.sort_by(|a, b| a.partial_cmp(b).unwrap());
        y_values.sort_by(|a, b| a.partial_cmp(b).unwrap());
        let x1 = x_values.first().unwrap().clone();
        let x2 = x_values.last().unwrap().clone();
        let y1 = y_values.first().unwrap().clone();
        let y2 = y_values.last().unwrap().clone();
        tables.push(Coordinate::from_rect(x1, y1, x2, y2));
    }
}

SVG画像や数式の扱い

さて，これでテキストエリアに存在する主だったパーツをだいぶ識別できるようになりました．
残りはSVGや数式になりますが，こちらは正攻法がありません．
ただし，BlockやLineの構造に特徴があり，幅が狭く一つのBlockにはあまり多くのLineが含まれない傾向にあります．
SVGはともかくとして，数式は通常の文章に比べて文字数が少ないためです．

そこで，少々雑ですが，Blockの幅がテキストエリアの幅の3割に満たない場合，かつBlockに含まれるLineの数が3つ以下の場合は強制的に対象外としました．
3という数字に根拠はありません．

本文のテキストが除外されてしまわないように，割と安全側に倒した設定ですが，試してみたところ，表で実装したように，完全に除外することはできませんが，意外とSVGや数式の大部分の記述を除外することができていたので，この方針でFixしました．

次回

今回までで，ほぼPDFのパースは完了です．
次回はこれらをJSONに落とす部分を実装します．

次回：Rustで学術論文からテキストを抽出する #9