画像から教師無しでグラフ構造抽出を行う

概要

画像の領域分割 (segmentation) を行って分けられた領域をノードとし，壁抽出した結果を利用してエッジをつなぐことで，教師無しで画像からグラフ構造の抽出を行う方法を提案してみる．

具体的には以下のようなイメージで間取り画像からグラフ構造を抽出することを目標とする．

graph-ideal

既存手法の例として，白黒の間取り画像からドアの形等を検出し，ルールベースでグラフ構造の抽出を行う手法が挙げられるが，今回扱う間取り画像は会社ごとによりドアの形状など，間取りの表記方法が異なるため難しい．そこで今回はRGB値の差分を利用した汎用的な領域分割手法として提案された Efficient Graph-Based Image Segmentation を利用し，間取りの構造を考慮した改善を行うことでグラフ構造の抽出を試みる．若干今の時代としては古い気はするが，アルゴリズムが直感的ということと公式の実装がシンプルで改変しやすかったのでこれを利用してみた．

Efficient Graph-Based Image Segmentation

segmentationのアルゴリズムとして代表的な手法の一つであり，以下にその概要を述べる．なおここで述べるグラフはセグメンテーションのためのグラフ構造であり，抽出したい方のグラフ構造ではないことに注意．

まず一つ一つの画素を一つのノードとし，それらのエッジ $e$ の重み $w$ を画素間の相対的な距離として計算する．具体的には，ノード1,2間の距離を以下の ${\rm RGB}$ 値の差分の二乗和平方根で与えることとする \begin{align} w(e) = \sqrt{(R_1 - R_2)^2 + (G_1 - G_2)^2 + (B_1 - B_2)^2}. \end{align} ここで，領域 (コンポーネント) $C$ の内部差 $\mathrm{Int}$ を $C$ の最小全域木 (Minimum Spanning Tree; MST) 内のエッジの重みの最大値とし \begin{align} \mathrm{Int}(C) = \max_{e \in MST(C)} w(e), \end{align} 2つの領域の最小内部差 $\mathrm{MInt}$ を以下で定義する \begin{align} \mathrm{MInt}(C_1, C_2) = \min(\mathrm{Int}(C_1) + \tau(C_1), \mathrm{Int}(C_2) + \tau(C_2)). \end{align} ただし， $\tau(C)$ は経験的な領域ペナルティであり，ここでは \begin{align} \tau(C) = \frac{k}{|C|} \end{align} とする．ただし $|C|$ は領域の大きさ (画素数)， $k$ は領域の併合しやすさを決めるパラメータであり， $k$ を大きくすると領域の結合が起こりやすくなる． 2つの隣接領域の差 $\mathrm{Dif}$ を接続しているエッジの重みの最小値 \begin{align} \mathrm{Dif}(C_1, C_2) = \min_{e=(v_1,v_2)|v_1 \in C_1, v_2 \in C_2} w(e) \end{align} とすれば，以下の条件を満たすとき領域を併合する \begin{align} \mathrm{Dif}(C_1, C_2) \leq \mathrm{MInt}(C_1, C_2). \label{eq:imsegcond} \end{align}

データ構造を素集合森 (素集合データ構造) にすることで，最終的な計算量は画素数を $n$ とすれば $O(n\log n)$ となり，高速化を実現している．

ここまででアルゴリズムの適用に際して決めなければならないパラメータは領域ペナルティの $k$ があるが，他にも結果をロバストにするためにこのアルゴリズムの適用前に標準偏差 $\sigma$ のガウシアンフィルタで処理し，さらに領域の併合の際には最小の領域サイズ $min\_size$ を制約に加えているため，結局実装上におけるパラメータは3つあり，領域ペナルティの $k$ ，最小の領域サイズ $min\_size$ ，ガウシアンフィルタの標準偏差 $\sigma$ となる．本研究においては経験的に結果の良かったパラメータを初期値として用いている ( $k=600,min\_size=3500,\sigma=0.8$ )．

その他の処理

resize - 画像のサイズ調整

上式より結合条件は画素数に依存するため，画素数をある程度統一することで精度の改善を試みた．画素数の決定は経験的に結果が良かった画像に合わせ，幅，あるいは高さの最大画素数を600にリサイズしたものを入力画像とした．

wall - 壁の抽出

元画像を2値化，さらに文字などの小領域を削除するためにモルフォロジー変換を行うことで壁の抽出を行い，壁の有無によって，領域間，すなわち隣接したノード間にエッジを繋ぐか否かを決定した．また，2値化した画像から壁画像を引くことで文字や床目といった必要のない部分 (smallcomp) を抽出し，これを利用して文字や床目が含まれる部分を壁以外の隣接した画素値で置き換えた．

filter(gaussian, median) - ノイズ等の除去

入力画像に対して上下左右隣接する画素値を比較し，それらの中央値に置き換えるメディアンフィルタ，また，領域分割後に周囲8近傍の領域と自身の領域との多数決フィルタを導入することで，ノイズの除去，領域の抽象化を行った．

seg_loop - ノード数の調整

経験的に得たパラメータを初期値とし，領域分割を行った結果からノード数を計算する．もしもノード数が少なすぎる，または多すぎる場合はパラメータを一定数調整してノード数が適切になるまで実行し直すよう実装した．今回は全体のノード数が実際の間取りに即するように7以上20以下に制限した．

なお，背景と壁はノードとして除外しており，具体的には画像の4隅に含まれる領域を背景，壁抽出した画像から，抽出された部分と重なっている部分，及び領域分割結果から抽出された部分が8割以上含まれている領域を壁とした．

グラフ構造抽出法

以上の処理を組み合わせ，領域分割結果から，それぞれの領域をノードとし，隣接する領域間でエッジを繋ぐ (seg2graph) ことで，グラフ構造抽出を行った．全体の処理の概要図を以下に示す．なおそれぞれの名前は上で述べた処理を行うことを示している．

imseg-flow

この図は全て実際の間取りで行った結果を載せている (詳細な実験は4章で行う)．最下段はグラフ構造の抽出結果を表し，壁抽出を行っていない場合 (左)，ノード間で隣接しているもの全てにエッジをつなぐことになるが，壁のある部分にはエッジを繋ぐべきではないため，壁抽出を行ってエッジを繋がない部分を見つけ (中)，さらにそれを利用して領域分割の結果を妨げる文字などの部分を取り除いて領域分割を行う (右)と，構造抽出の結果が最も良くなることを期待する．

現時点で利用できるノードの情報は，文字認識では現実的な精度が出せず，部屋の種類の特定には至らなかったため，ノードの色及び位置，大きさ，エッジの本数とした．今回は領域ごとに色 (多数決，RGB値の8段階)，重心位置，画素数を出力した．

他の手法では例えば文字認識，ドア検出を利用したグラフ構造抽出のアプローチ “Automated topometric graph generation from floor plan analysis” がある．また，異なる手法でもグラフ構造抽出を行い，それらを組み合わせることで最終的な目標である類似度の推定精度の向上が期待できる．

実験

とある物件検索サイトから間取り画像をとってきて，それに対して今回のグラフ構造抽出法を利用した結果．使用するパラメータに依存するが，うまくいくとこんな感じ．最左列は人手によるもの，右3つは↑の図のフローを適用したもの．最下段はmathematicaによる部屋の認識例を比較のため載せて，残りは2値化による壁とそれ以外の抽出結果．

graph-best1