プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

画像処理を始めよう ーエッジ 1 ー

 ちまちま書いてるうちに新年明けました。
 さて、Capyの記事書いてるときに、よくよく考えてみたらエッジの話って書いたことなくね?って気がついて、Steerable filterの話がてらエッジの話をすることにしておきました。でも一つの記事では収まりそうもありませんでした。
 実際にフィルタかけた画像とかはそのうち用意する。(^^;)




エッジ(edge)とはなんぞ?

 エッジエッジと言うけれど、エッジってなんぞ?
 エッジの前にまずは輪郭(countour)から考えてみましょう。文脈によってはエッジも輪郭も同じ意味って事もありますが、一般に輪郭とは

1 物の外形を形づくっている線。「顔の―」「―を描く」

となっています。(goo辞書)要するに物体と物体の境界を表す場所を輪郭と呼びます。


(赤い線が輪郭線)

 もし物体が3D情報として与えられているなら、異なる物体と物体の識別が容易に行えますから、輪郭の判断は簡単です。しかし、我々が扱うのは2D画像。良くても2D動画。物体の認識というのはかなり難しい。したがって、輪郭の抽出というのもかなり難しい。というか、一般に物体の認識がしたいが為に輪郭の情報が欲しいのです。でも輪郭を抽出するには物体がわかっている必要が………んあぁ、もう!(#^ω^)

 そこで、何らかの別な表見を持って輪郭を表現する必要があります。その表現に一般に用いられるのがエッジです。
 一つの丸い黒円がある画像を考えてみます。



 円上の赤い線の位置における色の変化を表したのが下の凹みたいな線です。色の変化が円の輪郭の位置で起こっているのがわかります。一般に輪郭における特徴として、物体の材質等が変わるため、色や明るさの急な変化が起こる事があげられます。むろん、輪郭ならば変化が必ず起こるわけではありませんし、逆に輪郭でない場所でも色や明るさの急な変化というのは起こります。従って、この変化を持って輪郭であるかないかを断定することは出来ませんが、ある程度輪郭らしさというものを表現することは出来そうです。この色や明るさの急な変化をエッジと言います。画像処理においてエッジやエッジ線という言葉がよく出てきますが、「画像にエッジという線や点がある」と誤解はしないでください。「エッジ」とは画像の色や明るさの変化が急である事象を指します。



エッジの抽出

 では、エッジはどうやって抽出するのか。基本となる考え方は3つあります。

  1. エッジは微分で得られる
  2. エッジはハイパスフィルタで得られる
  3. いや、なんかもう、適当に機械学習とかでゴリゴリすりゃいんじゃね?




 3は最近の計算機の性能が上がったが故に可能になってきたゴリ押し方法です。3はもはや話題になっているのがエッジなのか輪郭なのかよくわからなくなってきます。輪郭でもエッジでもないけどそれらっぽい何かです。今回はこいつについては放っておきましょう。あと、SUSANとか数学的に美しくないゴリってる定義でエッジ出してる奴もいるけど、この手のも無視しておきましょう。(周辺画素との変化量の和の様な物が閾値を超えているか否かでエッジを判断する。一応微分の亜種と見なせるんだと思う。元論文は読んだことないから細かい理論背景は知らない。) あ、これら別にゴリッてる手法を批判してるわけじゃないので。これからは基本的にこういったゴリゴリ美しくない方法が主流になっていくと私は思っています。でもゴリッてるのでやっぱ嫌いです。(オイ コーナー検出のFASTとかもゴリッてるしな〜。



 エッジの定義は「色等の変化が急であること」でした。これには二つの見方があります。一つは「エッジがあるところはグラフの傾きが急である」という見方。もう一つは「高周波成分を含んでいる」という見方。要するに、実領域で見るか、周波数領域で見るかという違いです。
 グラフの傾きが急であるかどうかを調べるには、色や明るさの関数を微分してみればいいのです。その結果、傾きがある値よりも大きかったらエッジと見なします
 高周波成分を出したかったら、ある周波数よりも低周波成分をカットしてしまえば良いと言うことになります。すなわち、ハイパスフィルタをかける事でエッジが得られることになります。
 微分フィルタは基本的にハイパスフィルタの構造をしているので、1は2でもあるのですが、考え方は違います。



微分によるエッジ抽出

 微分微分ゆーてんだから、とりあえず微分すりゃいいんだろー?式で書けばこうやな。
\frac{\partial I(x,y)}{\partial x},\frac{\partial I(x,y)}{\partial y}

 この微分の計算の仕方には一般に差分法が使われます。差分法には前進差分、後進差分、中央差分があります。
\frac{df(x)}{dx} \simeq f(x+1)-f(x)
\frac{df(x)}{dx} \simeq f(x)-f(x-1)
\frac{df(x)}{dx} \simeq \frac{f(x+1)-f(x-1)}{2}\simeq f(x+1) - f(x-1)




 別に一階微分でなくとも、もっと高階層の微分でもかまいません。高階層の微分であればあるほど、エッジに鋭利に反応するようになります。



 ここで問題になってくるのがノイズです。ノイズにはカメラ特有のノイズもあるでしょうし、物体のちょっとしたザラザラや、陰影などの影響もあるでしょう。基本的に画像処理の文脈でのエッジはエッジではなく、輪郭を暗に含んだエッジです。これらのノイズによるエッジを全て取っていては困るわけです。
 ノイズの影響を低減する簡単な手法はぼかすことです。エッジを得るためにぼかすというのもなんだか妙な話ですが。ぼかしつつエッジを得る単純な手法はプレヴィットフィルター(Prewitte filter)かソーベルフィルタ(Sobel filter)が代表的な手法としてあげられるでしょう。これらは、エッジを取る方向に垂直な方向にぼかしフィルタをかけます。PrewitteフィルタとSobelフィルタの2次元x方向の微分フィルタは以下のような形状をしています。
Prewitte = \left(\begin{array}{ccc}1\\1\\1\end{array}\right)\left(\begin{array}{ccc}-1&0&1\end{array}\right)
Sobel = \left(\begin{array}{ccc}1\\2\\1\end{array}\right)\left(\begin{array}{ccc}-1&0&1\end{array}\right)
 y方向微分フィルタは転置するだけです。どちらも微分には中央差分を利用していることがわかりますね。違いは、ぼかしに平均値を使うか、真ん中を重くするかどうか程度の物です。Sobelフィルタの方が性能がよいといわれています。
 ちなみに、この記事を書くためにSobelフィルタとPrewitteフィルタの出自を調べてきたのですが、Sobelフィルタよくわからんかったー。(´・д・`) Prewitteフィルタは予想通りPrewitteさんが1970年に作った様ですが*1、SobelフィルタはSobelさんが作ったんじゃないのか………?なお、Prewitteの論文タイトルはわかったのですが、論文自体はWeb上で発見することは出来ませんでした。




 ん〜、SobelとかPrewitteはわかったけど、何でぼかしと微分を同時にするの?もっと素直にエッジを取った結果をぼかす、でいいんじゃね?もしくは、先に画像をぼかすとか。むろん、それもありです。そして、その二つの操作は同じ結果になります。
\frac{\partial I(x,y)}{\partial x}*g(x,y)=\frac{\partial I*g}{\partial x}
 式中のIは画像、gはぼかし関数、*はたたみ込み演算子です。ふむ、まぁ、別にこれでもいいんですが、たたみ込みの性質を利用してもちょっと式を変更してみます。

\frac{\partial I}{\partial x}*g=\frac{\partial I*g}{\partial x}=I*\frac{\partial g}{\partial x}

 およ。どーやら微分した画像をぼかしたり、ぼかした画像を微分しなくても、最初っからぼかし関数を微分したフィルタを画像にかけても同じ結果が得られるようです。(むろん、ぼかしフィルタが微分可能であることが前提ですが。)
 こうやって表現すると様々なメリットがあります。例えば、g=ガウス関数として話を進めていきましょう。ガウス関数は何階でも微分可能です。差分法による怪しげ〜な微分の定義なんてしなくても、
\frac{\partial \exp(-x^2-y^2)}{\partial x} = -2x\exp(-x^2-y^2)
の様にビシッと微分することが出来ます。しかも、上の式は分解可能なので高速に計算も出来ると来た。すばらしい。さらにガウス微分フィルタの有利な点は、(上の式でははしょっていますが)偏差σの値を変更することで、画像のスケールにも対応することが可能になります。この辺のことはSIFTの記事で話しましたね。すばらしい。

 まぁ、すばらしぃすばらしぃ言ったけど、ぶっちゃけ特に理由がなければ高速に計算できるSobelフィルタで十分ってことのが多いよ。

 ただし、こういったエッジ検出で得られる輪郭線は太いという問題があります。輪郭線は太さ1pxがいい、ということはよくあります。そこで細線化処理が必要になってきます。その為の手法として細線化を行うのではなく、非極値抑制処理や零交差点をエッジ点と見なす手法があります。零交差点で有名な物にはCanny法があります。(いつか書く)




エッジの方向

 微分ってのは定義上、どうしても軸方向にしか微分できません。でも、輪郭線ってのは縦横だけじゃなくて、斜めだってあるわけです。方向の情報だってほしい
 一般には二つ方法があります。

  1. 先に画像を-θ回転させてx方向に微分する方法。微分値が最大となるθ方向がエッジ方向である。
  2. x方向y方向に微分した結果を利用し、atan\left(\frac{f_y}{f_x}\right)から勾配方向を求める方法。(fxはfをx方向に微分するという意味。)




 1はまぁ、良さそうだけど、回転って結構重い処理だし、回転によるぼけとか出てくるし、てゆーか全部のθについて回転とかやりたくないよね。2はよく利用される方法だけど、どの程度正しいものか非常に怪しいよね。あ、省いたけど、非極値抑制処理で方向も取ろうと思ったらとれます。



 エッジの方向を取り出したい、っていう手法で代表的な物はAdelson,Freemanらが体系化したSteerable filterがあります。この論文の元はSpatiotemporal energy models for the perception of motion(1985)という同Adelsonらにより提案された動画のモーションエネルギーモデルで提案された物だと思います。


 Steerable filterの基本理念は1と2の方法をくっつけたものと捕らえることが出来ます。ある方向θについての微分を別な方向の微分フィルタの和で表し、全てのθの中から最も鋭利な反応を示した方向θをエッジの方向とするというのが大枠です。

 「x方向に微分したガウス微分フィルタ」を回転させたフィルタfをいくつか用意します。必要なフィルタの数は1階微分なら2こ、2階微分なら3個という様にN階微分ならN+1個のフィルタfが必要です。フィルタfi(0〜N)の回転角度はiπ/Nです。これらのフィルタを画像にたたみ込んだ結果にsinθ,cosθで構築される係数kiを加えた物をGとします。(長いので実際に利用するフィルタの数式とかは論文を参照してください。)
G(\theta) = \sum_{i=0}^{N}\left(k_i(\theta)f_{\theta_i}*I\right)
 この別な方向に微分した結果を利用して、別な方向の値を求めるというやり方は2の方法に通じる物です。

 さらに、直交するエネルギーも考慮するためにヒルベルト変換したフィルタを回転させたフィルタhをいくつか用意します。ヒルベルト変換したフィルタhはガウスとxのN+1多項式のかけ算で近似し、用意するフィルタhの個数はN+2個です。(論文を参照してください。)先ほど同様にこれらを加えたフィルタの結果をHとします。
H(\theta) = \sum_{i=0}^{N+1}\left(k_i(\theta)h_{\theta_i}*I\right)
 なお、ここでの直交ってのは垂直って意味じゃなくて、信号理論における直交を指します。ある信号Iをフーリエ変換すると、負の周波数って出てきますよね?こいつを削除して、逆フーリエ変換するとI+iQという複素数が出てくる信号になります。ちなみに、正の周波数を削除して逆フーリエ変換するとI-iQになります。この実空間には出てこないQの部分はIから位相が90°ずれた直交信号になります。まぁ、実は私もこれ以上のことは理解していないので、自分で調べてくれい。

 で、最終的にエネルギーEをG2+H2という形で得ます。このEが最も大きくなる方向がその点におけるエッジの方向です。(そのθの探し方については論文読んでください。GとHを計算してしまえば、これらはただの定数で、Eはθの関数になるので1の様に全部のθを求めるなんてことはしなくても良いのです。)

 ただし、GとHの計算に本当に回転させたフィルタを利用すると、これらのフィルタはx,y方向にフィルタを分離できないので計算量が多いという問題があります。そこで、x,y方向に分離するように式を変形します。論文中ではx,y方向に分離するフィルタは、実際にフィルタの数式をゴリゴリ足し算して、ゴリゴリ分離して得ているんだと思います。確認のため私も実際に計算したよ。くっそ面倒くさかった。しかし、結果として得られた式は単に分解したとかそう言うものではないのです。


 実は方向微分って言う物があります。これは普通の微分の定義とはちょっとずれてて
\frac{\partial f({\bf x})}{\partial {\bf \theta}} = \lim_{h\to0}\frac{f({\bf x}+h{\bf \theta})-f({\bf x})}{h}
という定義です。(x,θはベクトル。θは方向ベクトル) 一般的な微分の定義から見たら、これ許されるの?って感じですが、こういう定義なのです。これを解くと
\frac{\partial f({\bf x})}{\partial {\bf \theta}}=\nabla f\cdot {\bf \theta}=({\bf \theta}\cdot\nabla) f
になります。({\bf \theta}\cdot\nabla)が方向微分演算子とみることが出来ますね。二階微分なら
\frac{\partial^2 f({\bf x})}{\partial {\bf \theta^2}}=({\bf \theta}\cdot\nabla)^2 f
となります。
 Freemanらが言う分離したフィルタGはこの方向微分に一致します。なお、ヒルベルト変換されたフィルタに関してですが、ごめんなさい、よくわかりません。これだけきれいに方向微分に一致したのだから、ヒルベルト変換の方も何か言えそうですけどね。(そもそも近似してるからどうとも言えないけど。)

 勾配方向ではなく、ある方向に微分した結果がほしい、という様な場合にはこの方向微分が直接使えます。
 





 はい、ちょー疲れた。大体、微分でのエッジに関する話はまとめたと思います。次は周波数空間で見たエッジだね。いわゆるガボールフィルタとかの話が出てくる………予定。私の根性があれば。

*1:J.M.S. Prewitt "Object Enhancement and Extraction" in "Picture processing and Psychopictorics",Academic Press,1970