Tesseractの原理のあれこれその１ 〜Page Layout Analysis〜

背景

私の学生研究において、Tesseractの原理について調査する必要が出てきました。せっかくなので、自分用と知りたい誰か用にQiitaにまとめておきます。また、タイトルの「原理」はTesseractの内部処理のことです。「原理」の方がわかりやすいかなと思ってこうしました。

※この記事は2020年2月23日時点での情報です。Tesseractのwikiは不定期で編集されるので注意してください。

また、私はTesseract内部処理は「Page Layout Analysis」と「テキスト判定」の２つに分けられると考えています。
概要は以下の通りで、

１、Page Layout Analysis
　入力された画像に対し、垂直線と文字以外の画像（図とか写真）の排除及び段組や行、単語の領域の特定を行う。
２、テキスト判定
　Page Layout Analysisで特定した単語の領域の画像に対して、LSTMベースのニューラルネットワークモデルにより文字を予測する。

となっています。また処理の流れとしては、出力は領域と文字がセットで出力されるので以下図のようなイメージです。

そして今回は１、Page Layout Analysisについてまとめていきます。

はじめに　〜資料探し〜　※内容については触れない

　まず、Page Layout Analysisはどこから出てきたのかを示しておきましょう。ある日、TesseractのOCRエンジンの内部構造を調査していました。すると、「Adaptinog the Tesseract Open Source OCR Engine for Multilingal OCR」①と言う論文を見つけました。これ読むと、LSTMモデルを採用する前のOCRエンジンの概要が書かれてました。その一文に、

The new page layout analysis for Tesseract[10] was desigined from the beginning to language-independent, ...

と書かれており、[10]の参考文献は「Hybrid Page Layout Analysis via Tab-Stop Detection」②というタイトルで同じwiki内にありました。ちなみに参考文献①ちゃんと読んでみると、この new page layout analysis は入力された画像から単語単位での画像まで特定する処理となっているみたいです。つまり、参考文献②を読めばその処理が分かるということですね。

　また、これはLSTMモデルを採用する前のOCRエンジン（Ver4.0以前）のことなのでVer4.0以降での内部処理についても明記して置かなければなりませんね。色々調査しているのですが、論文での文献は見つかりませんでした。多分一番詳しい資料は参考文献③なのですがプレゼン資料なのでなんとなくでしかわかりません。
　参考文献③のスライド３枚目を見てみると、

内部処理のフローチャート図があります。途中で「LSTM Line Recognizer」に分かれています。それがVer4.0以降で採用された処理ですね。Adaptive Thresholdingが入力画像の二値化（背景白・テキスト黒）で、次にPage Layout Analysisという処理をたどるみたいですね。プレゼン資料だから断言はできませんが、この「Page Layout Analysis」は参考文献②のことを指していると考えるのが自然でしょう。

　ということで、この記事では論文「Hybrid Page Layout Analysis via Tab-Stop Detection」についてまとめます。

参考文献
①Adaptinog the Tesseract Open Source OCR Engine for Multilingal OCR
②Hybrid Page Layout Analysis via Tab-Stop Detection
③2.Architecture and Data Structures

Page Layout Analysis

さて本題です。Page Layout Analysisについてまとめていきます。まずPage Layout Analysisの処理の全体像をつかむ為に処理のフローチャート図を示しておきます。

ちなみに、これらの処理の前に適切に２値化処理を施しています。なのでテキスト黒・背景白の画像に対して①から④までの処理をかけていくことになります。そして、最後の④で各文字がそのページの何番目の段組のどこの段落の行に含まれるどの単語なのか、といった着目する文字の所属が分かります。それでは、①から④まで１つずつ解説していきます。

①前処理

まず、前処理では以下の２つの処理を行います。
　１、垂直線・図の検出と排除
　２、Connected Components(CCs)の検出と選定

１、垂直線・図の検出と排除

　ここの処理では以下図のように、画像内の垂直方向の線と写真や図などのを検出して排除します。しかし、細かい作業はすべてLeptonicaというライブラリに任せているようで、この論文にはどうやって検出しているかは載っていません。どうしても知りたい方はLeptonicaのリファレンスとか適当にググってください。

２、Connected Components(CCs)の検出と選定

　Connected Components(CCs)についてあまり説明が無いのですが、字面と文脈から予想するに黒い画素値のつながりの領域を指しています。１で垂直線や図は排除しているので、各アルファベットや漢字・ひらがな・カタカナごとに１文字ずつ検出されることになります。先程の画像にCCsの検出をしてみると以下図のようになります。

また、この時にCCsは文字領域のみ検出したいため、検出したCCsを以下の手順で選定します。

手順１：CCsをsmall、medium、largeに分類
手順２：mediumを適切、largeは条件によって適切と判断

　まず、手順１のCCsの分類について説明します。CCはBoxの形をしているので幅wと高さhを元に分類します。とりあえず、hが7dot(300dpiにおいて)以下のCCはsmallに分類されます。それ以上の大きさを持つCCは「全CCsのhで下位75%に位置するh75」とし、

small：h < h75 / 2 のCCs
large：h > h75 * 2 or w > h75 *8 のCCs
medium：small でも large でもないCCs

と分類されます。ここで、mediumと分類されたCCsは文字領域と判定されるのですが、largeについては水平方向の隙間が狭かったら文字領域と判定されるみたいです。（ちゃんと読むとストロークがどうのこうの、、、わからんです）また、smallについては文字として認められません。

②タブ検出

　この処理では言葉通りページ内のタブを検出するのですが、目的としてはページ内に存在する各行の左端と右端を示すタブを求め、そこに垂直線を引くことです。（ここではとりあえず行の端を示す垂直線を求めるだけで、実際の行の領域は③で求めます。
ではどのようにそのタブを見つけるかですが、4.1章を読むと、

The initial candidate tab-stop CCs are found by a radial serch starting at every filtered CC from preprocessing.

とあって、①で検出したCCsから放射状（水平・垂直関係なく）にタブの候補を探すみたいです。

Assuming that the CC is at a tab-stop, the search looks for aligned neighbors and neighbors in the gutter where there should be a space.Each CC is processed independently and marked according to whether it is a candidate left tab, right tab or neither.

また、とあるのですが英語がよくわからないです。
とりあえず、左端を示すタブと右端を示すタブ、それ以外に分類するみたいですね。

そして、これらのタブCCsから行の左端と右端を決める垂直線を引きます。タブCCsの垂直方向に近いもの同士がページの段組となる可能性が高いですよね。なので、垂直方向に近いタブCCsを選定していって、それらから垂直線を引きます。

③コラム検出

　この処理ではまずコラムを求め、②で検出した行端の垂直線とそのコラムを参考にしながらページ内の段組（Column）を表す垂直線を引くことが目的となる。タブCCsなどを参考にしながらCCsを結合していき、1行を表すような領域を求めColumn Partitions(CPs)と呼ぶ。

そして、このCPsの横幅や②で求めた行端の垂直線などを参考にしながらページ内の段組を表す垂直線を引く。これがコラム検出である。

④領域分類

まずCPsを分類する。Leptonicaにより写真や図の位置などは判明しているので、段組の垂直線なども参考にしながら以下図のように分類する。

青色：本文
水色：見出し文
黄色：写真（形状が自由）
紅色：写真（形状が長方形）

　最後にCPsの垂直の間隔などからblockに分類される領域を求めます。これは実質的に段組ごと分けられた文章のまとまりとなります。（Tesseractの出力形式をTSVにした時のblock_numタグに相当します）

以上が論文「Hybrid Page Layout Analysis via Tab-Stop Detection」のまとめでした。

また、Tesseractの分類はこのblockの他に、

1,partition・・・段落、block内の文章のはじめに位置するタブCCを元に分類している
2,line・・・・・・行、block内に存在するCPsを元に分類している
3,word・・・・・単語、line内に存在するCCsの間隔などから分類している
※1と2については文献を見つけていないので憶測です。

などがある。次の章で検証する。

分類の検証

それでは、これまで論文で調査したTesseractのPage Layout Analysisを確かめてみましょう。
eng.traineddataを用いて、以下の記事をTSV形式で出力させてみましょう。

出力結果はこんな感じになる。

選択している箇所は２つ目のblockを示している。論文中の本文の4.3章が始まる直前の

such that all the number tab CCs fall to one side of the
line segment.

に相当することが分かる。また、そのblock内に段落は１つのみなのでpar_numは1のみであり、２行あるのでline_numは2まである。そして単語は行ごとに検出され、1行目には13個の単語・2行目には2つの単語があることになっていて、正しく領域が分類出来ている！

さいごに

　今回はTesseractで行われている内部処理の前半部分についてまとめました。Tesseractに関する日本語の記事はいくつかあるのですが、Tesseractの原理的な記事があまりない印象でした。とりあえず、一番情報があるのはTesserace wikiのdocs①かtessdocs②なので自分で調べたい人はここらへんを見てください。
　Tesseractをもっと知りたい誰かのためになれば！との思いもありつつまとめました。また、ご指摘があれば気軽にコメントくださるとありがたいです。

　次回は、その２としてテキスト判定についてまとめたいと思います。最後まで読んでくださり、ありがとうございます。それじゃ。
※2020年2月25日にテキスト判定について記事をまとめました。
Tesseractの原理のあれこれその２　〜VGSL編〜

①wiki docs : https://github.com/tesseract-ocr/tessdoc
②wiki tessdocs : https://github.com/tesseract-ocr/doc