確率的エッジ検出を実装してみた -

作者: 田中和之
出版社/メーカー: 森北出版
発売日: 2006/09/21
メディア: 単行本
購入: 4人クリック: 45回
この商品を含むブログ (7件) を見る

この本の 11 章の確率的エッジ検出に興味があってサンプルコードも無かったので実装してみた。ただし X と Windows Bitmap 周りの実装はかなり適当なので注意。

http://github.com/iwagaki/sandbox/tree/master/statistical_edge_detection/

実行例

./sample --alpha 1.0 --alpha2 100.0 --beta 10000.0 --gamma 20.0 --i lena_gray_small.bmp

アルゴリズムの概要

理解した範囲では、

輝度の差が大きいところをエッジの候補とする
そのままでは顔の輪郭など連続的に輝度の差があるとエッジが太くなるが、これを「境界線は隣り合わない」という事前分布で押さえ込む

となっている。上下左右の隣り合うピクセルの合間にエッジデータ（ライン場 H,V）が隠れていると仮定して、それがピクセルの輝度（F）に影響しているという数理モデルを考えている。このモデルで F が与えられた時に、見えないパラメータである H,V を推定する問題になっている。

まず間違い？

http://www.morikita.co.jp/soft/84661/index.html

ここの正誤表には出ていないようだが、p.143 (11.7) の式はおかしいと思う。

$\Pr\{F=f|H=h, V=v, \alpha, \gamma \} \\ = \frac{1}{Z_{data}(\alpha, \gamma)} \exp \left( - \frac{1}{2} \alpha \sum_{x=0}^{N-1} \sum_{y=0}^{M-1} (1-h_{x,y})((f_{x,y} - f_{x+1,y})^2 - \gamma^2) - \frac{1}{2} \alpha \sum_{x=0}^{N-1} \sum_{y=0}^{M-1} (1 - v_{x,y})((f_{x,y} - f_{x1,y+1})^2 - \gamma^2 ) \right)$

のように ΣΣ が入ると思う。これは p.91 の (7.34) も同様。

反復条件付き最大化の実装上のポイント

p.144 に書かれているアルゴリズムはこのまま実装すると計算コストがとんでもないことになる。Step 3, Step 4 で argmax P(h,v) を求める時に、注目する 4 エッジの組み合わせの数だけ P(h,v) を再計算してしまうと相当に重くなる。P(h,v) の exp の中は和であるので、exp の積に書き換えられる。P(h,v) と P(h',v') を比較するとき、不変なところは括り出すことで、変化する 4 エッジに依存する項だけ計算して比較できる。

疑問なこと１：事前分布は妥当なのだろうか？

エッジが抽出された出力画像を作るには、α,β,γ の値を調整する必要がある。直観的には、

αは尤度の強度（どれだけ画像の方を信じるか）
βは事前分布の強度（どれだけ前提条件の方を信じるか＝ p.142 図 11.4 のエッジではないパターンの組み合わせが出現しないようにするか）
γは隣同士のピクセルの輝度の差がどの程度ならばエッジと見なすか

というパラメータになっている。しかし実際にはなかなか思い通りにいかなかった。αとβは尤度と事前分布のバランスをとっていると思うが、エッジの線を細くするためにβを強くしすぎると平坦な部分に模様ができてしまった。整理すると、

γの閾値で決まるエッジの部分には、太いエッジが現れないように事前分布を強く適用させたい
γの閾値で決まる平坦な部分には、模様が出ないように事前分布を弱く適用したい

ということができない。考えてみると、 (11.6) の事前分布は、「こういうパターンはエッジにふさわしくない」という事前知識をモデル化したものだと思われるが、これはあくまで「エッジ部分に対する事前分布」であって、「平坦な部分についての事前分布」ではないように思える。でも事前分布は一律適応されているので、バランスをコントロールしにくいのではないかと考えた。

そこで (11.7) の実装で、αを一律かけるのではなく、パラメータを追加して (f(x,y) - f(x+1,y))^2 - γ^2 の正負によってαまたはα2をかけるように実装してみた。

    double df = static_cast<double>(f.pos(x, y).r() - f.pos(x + 1, y).r());
    double d = df * df - gamma * gamma;

    if (g_is_original)
        return alpha * (1 - h.pos(x, y).v()) * d;
    else
        return (d > 0.0 ? alpha : alpha2) * (1 - h.pos(x, y).v()) * d;

事前分布ではなく、代わりに尤度の強度を調整しているのだけど、これでエッジ付近だけに事前分布を強く適応できるようになった（正しいかどうかはともかくとして）。

疑問なこと２：反復条件付き最大化では局所解は問題にならないのか？

最適化するパラメータ (h, v) が超高次元になるのだが、事後確率最大化の方法として、反復条件付き最大化が使われている。アルゴリズムを読んでみると局所的な最適化を反復しているだけで、普通に考えるとものすごく局所解にはまってしまいそうな気がする。でも実際にやってみるとミクロで見ると解は揺れているが、マクロで見ると人間の顔が突然まったく違う顔になったりはしない。

あるエッジは周囲のエッジには影響しているが十分離れた点には寄与しないモデルになっている。こういう１つ１つのパラメータのモデルへの寄与が局所的だと局所最適化で十分結果がでる、ということなのかな？逆にあるパラメータで事後確率が大きく変化するような場合、そういう寄与率の高いパラメータがあるモデルでは局所解が問題になりそうな気がする。