Rustで学術論文からテキストを抽出する #4 - テキストエリアの抽出

:::note
## Summary
- Block，Lineの座標からPDFのテキストエリアを算出する
- LineとPageの幅から2段組みかどうかを判定できる
- テキストエリアからはみ出るテキストは本文でないとみなして除外する

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

## ToDo
- [x] pdftotextで論文から単語単位のテキストと位置情報を取得する (`Word`,`Line`,`Block`,`Page`)
- [ ] テキストの属性 (本文, タイトル, 脚注, etc.) を判定する
    - [ ] テキストが含まれるエリアを抽出する
        - [ ] 2段組みを扱えるようにする
- [ ] 図表に含まれるテキストを除外する
## 今日のファイル
```text
├── 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で学術論文からテキストを抽出する #3](https://qiita.com/akitenkrad/items/8b00674f13ceabe787d2)

pdftotextから得られる情報だけでは完全にテキストの属性を判定するのは困難であることがわかりました．そこで，まずは本文やセクションタイトルなど最終出力に必要な情報が存在しているテキストエリアを抽出し，脚注など不要なテキストを除外することを考えます．

前回そのための準備としてエリアを扱う`Coordinate`構造体を実装したので，今回はそれを使ってテキストエリアを検出するロジックを組み立てていきます．

```mermaid
graph LR
    A[要件定義]

    subgraph Popplerの観察
    B[Popperの観察]
    B1[pdftotext]
    end
    
    subgraph 今回はここ
    subgraph テキストの属性判定
    C[テキストの属性判定]
    C1[テキストエリアの抽出]
    end
    end
    
    D[テキスト抽出PoC]
    
    A-->B
    B1-->C
    C1-->D

```

## テキストエリアの左上の座標と右下の座標を知りたい

やりたいことはシンプルで，テキストエリア全体をカバーする`Coordinate`インスタンスを作成できれば完了です．
そのためには，**テキストエリアの左上の座標と右下の座標**を算出する必要があります．
もっと言ってしまえば，テキストエリアの $(x_{\text{min}}, y_{\text{min}}, x_{\text{max}}, y_{\text{max}})$の組合わせがわかればOKです．
これを，pdftotextから得られるテキストの座標情報から推定します．

画像処理では左上が原点になります．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3933655/d0755e6b-9596-1ce2-d94a-1af8a19cbc02.png)

基本的な方針は，

1. 各ページから上下左右の最も端に位置する矩形の座標を取得する
2. ページ全体に関して上記の中央値をとる

以上です．

今回対象にしているComputer Scienceの論文は大体10ページ前後のものが多いですが，どのページも本文が含まれるテキストエリアの位置は同じです．
表紙やAppendixなど一部例外はありますが，全体を並べた場合，平均的には求めるテキストエリアに落ち着くハズ．
平均値ではなく中央値を使っているのは，表紙やAppendixなど例外値に引っ張られないようにするためです．

## Rustでの実装

まずは各ページの上下左右の端を取得する関数を `Page`に実装します．
pdftotextの出力は Page > Flow > Block > Line > Word という構造になっていますが，この中のBlockを使って座標を算出していきます．

```rust:rsrpp > rsrpp > src > parser > structs.rs
#[derive(Debug, Clone, PartialEq)]
pub struct Page {
    pub blocks: Vec<Block>,
    pub width: f32,
    pub height: f32,
    pub tables: Vec<Coordinate>,
    pub page_nubmer: PageNumber,
    pub number_of_columns: i8,
}

impl Page {
    ...
    ...
    
    pub fn top(&self) -> f32 {
        let mut values: Vec<f32> = Vec::new();
        for block in &self.blocks {
            for line in &block.lines {
                values.push(line.y);
            }
        }
        values.sort_by(|a, b| a.partial_cmp(b).unwrap());
        return values.first().unwrap().clone();
    }

    pub fn bottom(&self) -> f32 {
        let mut values: Vec<f32> = Vec::new();
        for block in &self.blocks {
            for line in &block.lines {
                values.push(line.y + line.height);
            }
        }
        values.sort_by(|a, b| b.partial_cmp(a).unwrap());
        return values.first().unwrap().clone();
    }

    pub fn left(&self) -> f32 {
        let mut values: Vec<f32> = Vec::new();
        for block in &self.blocks {
            for line in &block.lines {
                values.push(line.x);
            }
        }
        values.sort_by(|a, b| a.partial_cmp(b).unwrap());
        return values.first().unwrap().clone();
    }

    pub fn right(&self) -> f32 {
        let mut values: Vec<f32> = Vec::new();
        for block in &self.blocks {
            for line in &block.lines {
                values.push(line.x + line.width);
            }
        }
        values.sort_by(|a, b| b.partial_cmp(a).unwrap());
        return values.first().unwrap().clone();
    }
}
```

単一のページでの座標取得ができるようになったので，テキストエリアを算出する関数を実装します．
入力は`Page`のベクトルで，出力は`Coordinate`のインスタンスです．
前述の通り，各ページから端の座標を取得してきて中央値を取っています．

```rust:rsrpp > rsrpp > src > parser > mod.rs
fn get_text_area(pages: &Vec<Page>) -> Coordinate {
    let mut left_values: Vec<f32> = Vec::new();
    let mut right_values: Vec<f32> = Vec::new();
    let mut top_values: Vec<f32> = Vec::new();
    let mut bottom_values: Vec<f32> = Vec::new();

    for page in pages {
        left_values.push(page.left());
        right_values.push(page.right());
        top_values.push(page.top());
        bottom_values.push(page.bottom());
    }

    let left = sci_rs::stats::median(left_values.iter()).0;
    let right = sci_rs::stats::median(right_values.iter()).0;
    let top = sci_rs::stats::median(top_values.iter()).0;
    let bottom = sci_rs::stats::median(bottom_values.iter()).0;

    return Coordinate {
        top_left: Point { x: left, y: top },
        top_right: Point { x: right, y: top },
        bottom_left: Point { x: left, y: bottom },
        bottom_right: Point {
            x: right,
            y: bottom,
        },
    };
}
```

## 2段組み論文への対応

pdftotextで出力される`Line`はPDF内の1行を表しているようです．
したがって，2段組み論文の場合はほとんどの`Line`の幅が`Page`全体の幅のおよそ $\frac{1}{2}$ になると考えられます．
これを利用してPDFが2段組みになっているかどうかを判定します．
また，2段組みの論文は2つの列のテキストが入り乱れて順番が滅茶苦茶になっているので，左側→右側になるように`Block`の順番を調整します．

実装では，$\text{Lineの平均幅} < \frac{\text{ページの幅}}{1.5}$ として2段組かどうかを判定しました．
なぜ $1.5$ なのかというところに論理的な根拠はありません．
これで大体うまくいきいます．

```rust:rsrpp > rsrpp > src > parser > mod.rs
fn adjst_columns(pages: &mut Vec<Page>, config: &ParserConfig) {
    let page_width = config.pdf_info.get("page_width").unwrap().parse::<f32>().unwrap();
    let half_width = page_width / 2.2;
    let last_page = config.sections.iter().map(|(page_number, _)| page_number).max().unwrap();
    let avg_line_width = pages
        .iter()
        .filter(|page| page.page_nubmer <= *last_page)
        .map(|page| {
            page.blocks
                .iter()
                .map(|block| {
                    block.lines.iter().map(|line| line.width).sum::<f32>()
                        / block.lines.len() as f32
                })
                .sum::<f32>()
                / page.blocks.len() as f32
        })
        .sum::<f32>()
        / pages.len() as f32;

    if avg_line_width < page_width / 1.5 {
        // Tow Columns
        for page in pages.iter_mut() {
            page.number_of_columns = 2;
            let mut right_blocks: Vec<Block> = Vec::new();
            let mut left_blocks: Vec<Block> = Vec::new();
            for block in page.blocks.iter() {
                if half_width < block.x {
                    right_blocks.push(block.clone());
                } else {
                    left_blocks.push(block.clone());
                }
            }
            left_blocks.append(&mut right_blocks);
            page.blocks = left_blocks;
        }
    }
}
```

これでテキストエリアを座標で識別できるようになったので，すべての`Line`をまわしてテキストエリアと重複しているかどうかをチェックすれば，テキストエリアに含まれる本文+$\alpha$だけを抽出できます．
下のプログラムは最後に実装する`parse()`の一部です．
後に出てきますが，セクションのタイトルだけはテキストエリアをはみ出すことがあるので，それ以外のテキストについてテキストエリアに含まれるかどうかを`IoU`を使って判定しています．

最後に2段組み対応を行なっています．

```rust:rsrpp > rsrpp > src > parser > mod.rs
    // compare text area and blocks
    let section_titles =
        config.sections.iter().map(|(_, section)| section.to_lowercase()).collect::<Vec<String>>();
    let text_area = get_text_area(&pages);
    let title_index_regex = regex::Regex::new(r"\d+\.").unwrap();
    for page in pages.iter_mut() {
        let mut remove_indices: Vec<usize> = Vec::new();
        let width = if page.number_of_columns == 2 {
            page.width / 2.2
        } else {
            page.width / 1.1
        };
        for (i, block) in page.blocks.iter_mut().enumerate() {
            let block_coord = Coordinate::from_object(block.x, block.y, block.width, block.height);
            let iou = text_area.iou(&block_coord);
            let block_text = block.get_text();
            let block_text = title_index_regex.replace(&block_text, "").trim().to_string();

            if (iou - 0.0).abs() < 1e-6 {
                remove_indices.push(i);
            } else if !section_titles.contains(&block_text.to_lowercase())
                && (block.width / width < 0.3 && block.lines.len() < 4)
            {
                remove_indices.push(i);
            }
        }
        for i in remove_indices.iter().rev() {
            page.blocks.remove(*i);
        }
    }

    adjst_columns(&mut pages, config);

```

## 次回

まずは，論文の本文+$\alpha$が含まれるエリアを特定し，脚注などを除外することができたので，次は主要な要素の一つであるセクションのタイトルを識別する方法を模索します

[次回：Rustで学術論文からテキストを抽出する #5](https://qiita.com/akitenkrad/items/0a4c8ddcabaa4e55c7a5)