特許検索のためのフローチャート画像の解析
Analysis of Flowchart Images for Patent Retrieval

中央大学理工学部ビジネスデータサイエンス学科教授

難波英嗣

2001 年北陸先端科学技術大学院大学情報科学研究科博士後期課程修了。博士 ( 情報科学 )。東京工業大学精密工学研究所助手、広島市立大学大学院情報科学研究科准教授等を経て、2019 年より中央大学理工学部教授。自然言語処理、テキストマイニングの研究に従事。
nanba@kc.chuo-u.ac.jp

03-3817-188

フローチャート画像の解析における関連研究プロジェ

1 はじめにク ト と し て CLEF-IP が あ る [3]。CLEF(Conference

特許中の図表は、特許の内容を理解する上で非常に重and Labs of the Evaluation Forum) とは、ヨーロッ要な役割を果たしている。例えば、非常に複雑な構造をパを中心に行われている情報検索に関するワークショッ

した装置や複雑な手順は、自然言語で説明するよりも装プであり、CLEF-IP は特許を対象としたタスクのこと

置の構造図やフローチャートとして図示した方がはるかを指す。このタスクは実験レベルだけではなく、現実のに分かりやすい。実際に、図表が特許の中でどの程度使課題に即した検索タスクのためのデータセットを提供すわれているのか調べたところ、2019 年には 306,223

ることで、多言語及びマルチモーダル特許検索タスクの件の特許が公開されており、これらの中に 6,568,824研究の促進を図っている。CLEF-IP では図形を認識し、画像が使われていることが分かった。これは 1 特許あフローチャートの要素となるテキスト、エッジ、ノードたり平均 21 件の図表画像が使われていることになる。

を検出しフローチャートの認識を行っている。CLEF-IP

従来の特許検索では、特許中のテキストの他、国際特の基本的な課題は、本研究と共通するが、CLEF-IP が許分類、F タームなどの各種メタデータが利用されてき実施された 2013 年当時と比べ、画像解析技術が大幅た。これらに加え、我々は、画像を解析することで、よに向上している点、また、本研究では、画像データだけり高度な特許検索の実現を目指している。その第一歩とでなく、画像に付随するキャプションや本文のデータがして、本研究では、フローチャート画像の解析に取り組セットになっているという点が異なる。

む。フローチャート画像を解析できれば、将来的には、フローチャート画像を認識するこの他の研究として、ある手順と類似する手順の特許を検索するといった、従Herrera-Cámara のものがある [1]。この研究では、手来の特許検索では困難な検索を実現することが可能にな書きフローチャート画像を解析し、C 言語のソースとしると考えられる。て出力する手法を提案している。Sethi らは、深層学習関連の論文中の図表画像からフローチャートを識別し、さらにフローチャートを解析することで、Keras と2 関連研究

Caffe でソースを出力するシステムを構築している [4]。

論文や特許などの図表画像を解析する研究がこれまで本研究では、フローチャートを解析する際、これらの手にいくつか行われている。Shindo らは、論文から図表法を参考にしている。本研究とこれらの先行研究と異な画像を抽出し、折れ線グラフを解析することで数値情報る点は、次節で述べる解析手法の中で、抽出されたオブ。Oka らは、論文中の表画像からポジェクトの面積でクラスタリングすることで、再現率をを抽出している[5]

リマーの物性情報を抽出している [6]。

244低下させることなく精度を向上させた点である。

3 フローチャート画像の解析ることがわかる。これらの結果から、x 座標と y 座標が何種類あるかを調べれば、長方形とひし形を区別できる。

3.1 解析手順
フローチャート画像の解析は、以下の 6 つの手順から構成される。
① 輪郭の抽出(a) 長方形② 輪郭の近似・座標情報の抽出

図 2：長方形とひし形の区別
長方形とひし形の区別

図2③ 形状の認識④ 面積によるクラスタリング(b) ひし形④ 面積によるクラスタリング
手順 3 で検出されたオブジェクトのうち、不要なも⑤ 文字認識のを除外する。ここで、不要なオブジェクトはどのよう

以下、各手順について述べる。

なものか、図 4 を用いて説明する。図 3 は、2 つのオ① 輪郭の抽出

ブジェクトから構成されるフローチャートであるが、手入力画像をグレースケール画像に変換した後、コン順 3 の結果、(b) のように検出すべき 2 つのオブジェ

ピュータビジョン向けライブラリ OpenCV(https://クトの他に、2 つのオブジェクトをまとめた (a) のようopencv.org) の輪郭検出メソッド findContours を用なものもオブジェクトとして検出されてしまう。

い、フローチャート内のオブジェクトを検出する。
② 輪郭の近似・座標情報の抽出
手順 1 で検出された輪郭は曲線などの多数の点で構成されるが、これを OpenCV の approxPolyDP メソッドを用いてより少ない点で近似し、座標情報を得る。その理由は、次のステップで、オブジェクトの形状を認識するためである。
③ 形状の認識
手順 2 で得られた座標情報を用い、オブジェクトの形状を認識する。形状認識には以下のルールを用いる。

図3

オブジェクト認識におけるクラスタリングの利用

図 3：オブジェクト認識におけるクラスタリングの利用
そこで、OpenCV の contourArea メソッドを用いて各オブジェクトの面積を得た後、DBSCAN[2] を用
if 頂点の数==3：三角形

いて面積が± 90 の範囲のオブジェクトを同一クラスタ

else if 頂点の数==4：に統合する。クラスタリングの結果、一番多くのオブジェ

if 4 つの頂点のうち、x 座標と y 座標が 2 種類ずつある：長方形

クトを含むクラスタを選択する。なお、± 90 という値

else if 4 つの頂点のうち、x 座標と y 座標が 3 種類ずつは経験的に決めたものである。また、極端に大きい ( 面ある：ひし形積が 100000 以上 ) あるいは極端に小さい ( 面積がelse if 頂点の数==5：五角形
else if 頂点の数 6 以上 14 未満：楕円形
else if 頂点の数<=14：円
図 1：オブジェクトの形状認識手順
オブジェクトの形状認識手順

図11000 未満 ) オブジェクトは事前に削除している。
⑤ 文字認識Tesseract(https://github.com/tesseract-ocr)を用いて、各オブジェクトの内部にある文字の認識を行

頂点の数が 4 の時に長方形とひし形を区別する方法

う。Tesseract はオープンソースの OCR エンジンでについて、図 2 を用いて説明する。図 2 から、(a) 長ある。画像全体だけでなく、座標を指定すると、画像の方形の場合 x 座標は x1 と x2、y 座標は y1 と y2 の 2

一部だけ文字認識することができるため、フローチャー

種 類 ず つ あ る。 一 方 で、(b) ひ し 形 の 場 合、x 座 標 はトのノードを認識した後に、ノード内の文字列だけ文字x1、x2、x3、y 座標は y1、y2、y3 の 3 種類ずつあ認識することができる。さらに、認識時に Tesseract

YEAR BOOK 2O21 245

3

特許情報の高度な情報処理技術⑥ フローチャートと本文の対応付け

で使用する言語モデルを指定すれば、55 言語で文字認

図 5 は、図 4 の解析結果として得られたノードにつ識をすることができるため、本研究で開発するシステム

いて、ノードの ID(ID)、クラスター番号 (CLUSTER)、は、日本国特許だけでなく、米国特許や中国特許にも容面積 (AREA)、座標情報 (COORDINATE)、形状の種易に適用することができる。なお、Tesseract で画像類 (POLY)、ノード内の文字 (TXT) の出力結果を表しの一部を文字認識する場合、矩形領域の座標が必要となている。また、この図に対して図 6 のテキストが付随るため、各オブジェクトの矩形領域の座標は、手順 2している。画像を解釈するために、本文中の言及個所がとは別に boundingRect メソッドを用いて得る。

利用できる点が CLEF-IP と本研究との違いである。

⑥ フローチャートと本文の対応付け
画像と本文との対応付けを行う。日本国特許では、本文は XML 形式であり、テキストには段落タグが付与されている。各画像には ID 番号が付与されており、本文中の言及個所との対応付けも容易に行うことができる。

以上の 6 手順を実行した場合、1 画像あたり約 15秒で解析できることを確認した。なお、本来ならばフローチャートのノードだけでなくノードとノードをつなぐエッジについても解析すべきであるが、エッジ解析については今後の課題としたい。

3.2 システムの動作例

図 5：フローチャート中のオブジェクトの形状認識および
フ ロ ー チ ャ ー ト 中 の オ ブ ジ ェ ク ト の 形 状 認 識 お よ び

図5Tesseractを用いた文字認識結果を用いた文字認識結果
Tesseract

発明の名称:「放射線撮像装置、放射線撮像方法及び放射線撮像プログラム」

本研究のシステムの動作例を図 4 と 5 に示す。図 4

キャプション:本発明の第４の実施形態に係るＸ線ＣＴ

では、形状認識の際に形状ごとに色分けをしており、長装置における非一様性の推定〜入射率推定値算出の流れ方形は緑、楕円形は青、ひし形は赤で表している。解析を示すフローチャートである。
本文:この場合の処理は、例えば、図１９に示すフローチ

結果からわかるとおり、矩形領域、条件分岐を示すひし形、ャートに従って、ピクセル毎の非一様性推定から入射率フローの最初と最後を示す楕円が正しく解析されている。

推定値算出までの処理を行う。

一方で、条件分岐が連続する個所の右側の領域など、抽図 6：図 4 のフローチャート画像に関するテキスト
図 6 図 4 のフローチャート画像に関するテキスト出すべきでない個所を誤って抽出してしまっている。

4 実験
3 節で述べた手法の有効性を確認するため実験を行った。
実験データ
日本国特許公開公報 2018 年から抽出した 37 画像( フローチャート ) を用いる。これらの画像に対し、人手で 502 ノードの座標を判定した。なお、各座標はオブジェクトの形状に関係なく、すべて矩形領域の座標として近似的に判定している。
評価方法
出力結果と比較し性能を評価する。ノードの座標の一致度の評価尺度として精度と再現率を用いる。なお、シ

図 ノード抽出の結果
4：ノード抽出の結果
図4246

ステムの出力と人手のノードを比較する際、領域の重なる面積が 90% を超えた時、2 つのノードが一致したと周りに沿ってリストとして得られる。この時、x 座標ま判定する。また、比較手法としてクラスタリングをしな

たは y 座標の増加あるいは減少が一定回数以上ある複い場合の精度、再現率を求める。

雑な形状のものはエラーとして抽出しないという方法が比較手法考えられる。

3.1 節で述べた 6 つの手順のうち、手順 4 においてクラスタリングを行った場合 ( 提案手法 ) とクラスタリングを行わず、すべてのノードを抽出した場合 ( ベースライン手法 ) とで比較した。
実験結果
実験結果を表 1 に示す。表 1 より、提案手法と比較手法を比べると再現率を低下させることなく高い精度を提案手法のほうが優れているという結果が得られた。

オブジェクトが誤って抽出された画像の例

こ の 他、 抽 出 さ れ た オ ブ ジ ェ ク ト 内 の 文 字 列 をTesseract で文字認識し、出力された文字列が不自然

表表1 1オブジェクトの抽出結果
オブジェクトの抽出結果

精度

図8

再現率

(1) 提案手法

0.753

0.673

(2) ベースライン手法

0.693

0.673

な日本語である場合、そのオブジェクトを抽出しないという方法も考えられる。3.1 節手順 5 で述べたとおり、Tesseract で画像の一部を文字認識する場合、矩形領域の座標が必要となるが、エラーオブジェクトの場合、他のオブジェクト内の文字列を断片的に切り取ってしま考察
解析に失敗した例をいくつか示す。図 7 は、オブジェうことがあるため、この場合文字認識すると、オブジェクトが全く抽出できなかった画像の一部を拡大したもの

クト内の文字列は不自然な日本語となってしまう。そこである。おそらく画像をスキャンした際に混入したノイで、言語モデル等を用いて認識された文字列の自然さをズではないかと思われるが、オブジェクトの輪郭線が不測ることにより、エラーオブジェクトかそうでないかの鮮明であることがわかる。このような画像に対しては、判定がある程度可能になると考えられる。

前処理としてノイズ除去あるいはエッジを強調するようなフィルタを適用する必要があると考えられる。

5 おわりに
本研究では、特許中のフローチャートの構造を解析するシステムを構築した。本システムは、まず、物体認識技術を用いてフローチャートの輪郭を抽出、輪郭の近似、座標情報の抽出を行う。次に、抽出されたノードの座標情報に条件を定め、形状を分類し、ノードの形状認識を行う。そして、Tesseract を用いて抽出されたノード

図 7：オブジェクトが抽出できなかった画像の例
図 7 オブジェクトが抽出できなかった画像の例

内の文字の認識を行う。日本国特許公開公報 2018 年から選択した 37 件のフローチャート画像を用いて評価

図 8 は、フローチャートの中に、条件分岐などで閉を行った。実験の結果、フローチャート中のノードを、ループが存在する場合に発生する誤り例である。同様の精度は約 0.753、再現率は約 0.673 で抽出すること

ものは図 5 にも数カ所見られる。このような誤りにつができた。

いては、オブジェクトの輪郭座標である程度検出できるのではないかと思われる。3.1 節の手順 2 において、輪郭座標を近似した場合、座標は、順にオブジェクトのYEAR BOOK 2O21 247

3

特許情報の高度な情報処理技術得ることができたため、クラスタリングは有効であり、

図 8：オブジェクトが誤って抽出された画像の例

参考文献[1] Herrera-Cámara J.I.. FLOW2CODE - From
Hand-drawn Flowchart to Code Execution,
Master Thesis, Texas A&M University,
2017.
[2] Ester, M., Kriegel, H.P., Sander, J., and Xu, X..
A density-Based Algorithm for Discovering
Clusters in Large Spatial Databases withNoise, KDD-96 Proceedings, 1996, p.226231.
[3] Piroi, F., Lupu, M. and Hanbury, A.. Overviewof CLEF-IP 2013 Lab Information Retrieval
in the Patent Domain, Information Access
Evaluation. Multilinguality, Multimodality, andVisualization. CLEF 2013. Lecture Notes
in Computer Science, vol. 8138. Springer,Berlin, Heidelberg, 2013.
[4] Sethi, A., Sankaran, A., Panwar, N., Khare,S., and Mani, S.. DLPaper2Code: Autogeneration of Code from Deep Learning
Research Papers, Proceedings of the 32th
AAAI Conference on Artificial Intelligence,
2018.
[5] Shindo, H. and Matsumoto, Y.. Automatic
Reading of Tables and Figures in ScientificPapers, CBI Annual Meeting, 2019.
[6] Oka, H., Shindo, H., Goto, K., Matsumoto,Y., Yoshizawa, A., Kuwajima, I., and Ishii,
M.. Automatic Extraction of Polymer Data
from Tables in Xml, Proceedings of the3rd International Workshop on ScientificDocument Analysis (SCIDOCA 2018),
2018.

248

特許情報の高度な情報処理技術

3

YEAR BOOK 2O21 249