画像に描かれたグラフの接続(エッジ)を深層学習で読み取る

はじめに

回路図やUML図のような「図として描かれた構造情報」を、画像から自動で読み取り、コンピュータに扱いやすい形式へ変換（構造化）したいと思いました。そうすることで、図をプログラムで解析したり、LLMに読み込ませたりできるようになります。

今回はその第一歩として、「ノードとエッジで構成されたグラフの画像から、構造を復元する」というのをやりました。

入力として使うのは、以下のようなグラフ画像です（ノードの位置と番号はあらかじめ分かっているとします。これは物体検出などで取得できます）：

この画像から、どのノード同士が線（エッジ）でつながっているかを推定します。

推定されたエッジの例:

エッジのリスト

[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (2, 3), (3, 4)]

上の情報を使って、構造を再現したグラフがこちらです:

モチベーション

ある日、Discordで電気回路の問題を写真付きで質問している人を見かけました。でも返ってきたのは「まず自分で考えたら？」という返答でした。
ChatGPTに聞けば親切に教えてくれるはずです。でも、ChatGPTに回路図を写真のまま渡しても理解できません。人間なら写真から回路を読み取れますが、AIに理解させるには、「どの部品がどうつながっているか」をデータとして渡す必要があります。

また、電気回路の問題はシミュレーションでも解けますが、これも同様に、回路図画像をコンピュータが扱える形式（構造化データ）に変換する必要があります。もちろん、手作業でやることもできますが、面倒です。だったら画像から自動で変換できたら便利では？と思いました。
他にもUML図（クラス図など）も画像から構造化できたら面白いなとも考えていました。

こうした図は本質的に「ノードとエッジ」で構成されたグラフ構造を持っています。

そこで今回は、まずは簡単なグラフ画像を対象に、「画像から構造を復元するタスク」を試してみました。

今回の焦点はエッジの推定です。ノードの位置や番号はあらかじめ分かっている前提で、どのノードとどのノードが接続されているかを判定します。

タスクの定義

ノード間の接続判定（二値分類タスク）

ノードのIDとそのバウンディングボックス（ノードを囲む四角形）は既知とします。
各ノードに対してバウンディングボックスを可視化した図：

ノードの検出は画像処理や物体検出技術を使えば簡単にできます。
問題は「どのノードとどのノードが線（エッジ）でつながっているのか」をどう判定するかです。

これは、ノードペアを入力として「接続されているかどうか（0または1）」を出力する二値分類タスクに帰着できます。

このタスクを解くために深層学習を使用します。

解法

使用技術・ライブラリ

• グラフデータの生成：NetworkX
• 画像生成と処理：OpenCV
• 深層学習：PyTorch

コードはGitHubに公開しています → https://github.com/DanielOkada/graph-from-image

入力データの工夫

判定対象の2つのノードを黒塗りにし、それ以外のノードは白く塗りつぶして見えなくします。こうすることで注目ノードを強調します。

元グラフ:

ノードを塗りつぶしたグラフ(注目ノードが3と1の場合の例):

こうすることで、モデルに「どのノードペアを判定すればよいか」を伝えられます。
また、ノードを塗りつぶすことでノードの形・色・中の文字などに影響されずに学習できます。

モデルと学習

EfficientNetを画像分類モデルとしてファインチューニングし、ノードペアが接続されているかを学習させました。EfficientNetは軽量で高精度な画像分類モデルです。
データはランダムに生成したグラフ画像を用います。

• グラフのノード数：5
• エッジができる確率：0.5
• 学習時間：5分未満（GPU）

結果

ノード間の接続判定（推論例）

以下は実際の推論例です。

F1スコアは0.99と高精度です。

この推論をグラフのすべてのノードの組み合わせに対して行います。そして、つながっていると判定されたノード間にエッジを張ることで、グラフ全体を再構築できます。

グラフ画像からの再構築結果

以下は再構築結果です。ノードの位置は元の画像と一致させてあります。

グラフのすべてのエッジが元と完全に一致した割合（完全一致率）は0.89でした。
ノードのすべての組み合わせに対して推論しないといけないので完全一致は難しいですが、それでも9割近い精度がでました。

学習していないノード数にもある程度対応

ノード数を5個に固定して学習しましたが、興味深いことに、ノード数を増やしてもある程度推定が可能です。：

ノード数が増えるとエッジが重なって判定が難しくなります。さすがに間違いが多くなりますが、学習していない割にはある程度推定できています。
ノード数が8個での再構築例:

手書きグラフの認識

手書きのグラフも認識できるか試してみました。

手書き画像は背景のノイズや影があるため、そのままでは解析が難しいです。
そこで、グラフ構造の線を強調するために 二値化（黒白変換） を行います。

ノードのバウンディングボックスを取得します。今回はとりあえず手作業でノードを番号順に囲みます。

推論と再構成を行った結果がこちらです。

手書きのグラフも変換できました！

他にも試しましたが、なかなかうまくいっています。

手書きなので少し線に歪みありますが、それでも意外と動いてくれるのが驚きでした。

おわりに

今回は「ノードの位置とIDが既知」である前提のもと、
深層学習を用いてエッジを推定し、グラフ画像から構造を復元しました。

この仕組みがあれば、回路図やUML図といった図を画像から「構造化されたデータ」に変換することができるかもしれないです。

今後は、ノードの自動検出（位置・種類）も組み込んで、
完全自動の構造復元にも挑戦したいです。