エッジ検出

エッジ検出（エッジけんしゅつ、英: edge detection）は、画像処理やコンピュータビジョンの用語で、特徴検出 (feature detection) や特徴抽出 (feature extraction) の一種であり、デジタル画像の画像の明るさが鋭敏に、より形式的に言えば不連続に変化している箇所を特定するアルゴリズムを指す。

背景

画像の明るさの鋭敏な変化を検出する目的は、実世界の属性の重要な事象や変化を捉えることである。一般的な画像形成モデルにおいて、画像の明るさの不連続な変化は次のような事象と一致する可能性がある。

深さが不連続である。
面の向きが不連続である。
材質が変化している。
照明が変化している。

理想的には、画像にエッジ検出を施すことで、物体の境界を示す連続する曲線が得られ、面の向きが不連続に変化している部分（要するに角）も曲線として得られる。したがって、エッジ検出を画像に施すことで処理すべきデータ量が大幅に削減され、相対的にあまり重要でない情報を排除しつつ、画像の構造的属性だけを保持する。エッジ検出が成功すると、その後の画像処理がずっと単純化される。しかし、それなりに複雑な実際の画像で理想的なエッジを抽出するのはそう簡単ではない。実際の画像から得られるエッジは、興味深い現象と一致しない「偽のエッジ」があったり、エッジ曲線が途切れていて「断片化」していることがあり、その後の画像処理を複雑にしている。

エッジの特徴

3次元のシーンの2次元画像から抽出されるエッジは、視点依存のエッジと視点独立なエッジに分類できる。視点独立のエッジは、3次元の物体の本質的な特徴を反映したもので、表面の形状などに対応している。視点依存のエッジは、視点が変わると変化するもので、どの方向から撮影するかに依存している。例えば視点によって物体同士が重なる場合などである。

典型的なエッジは、例えば赤のブロックと黄色のブロックの間の境界がある。一方、直線状のものは数ピクセル幅の色が異なる部分が背景と違っている。この場合、その物体の両サイドにエッジを検出することになる。

エッジは画像処理の多くの応用で極めて重要な役割を担っており、特にマシンビジョンシステムで制御された照明下で製品を撮影して、それを解析する場合によく使われる。しかし、最近^[いつ?]では前処理としてエッジ検出を行わずに画像処理する手法の研究^[要説明]が進んでいる。

単純なエッジモデル

書籍には理想的なエッジの検出が説明されているが、実際の画像から得られるエッジは理想のエッジとは程遠く、一般に以下のような点に影響を受ける。

被写界深度が有限であるため、それ以外の部分はピンぼけになる（点拡がり関数）。
光源が理想的な点光源でないため、影の境界がぼやける（半影）。
物体の丸い角における陰影。
物体のエッジ近辺での局所的な鏡面反射や拡散反射。

以下のモデルは実際の画像におけるエッジの可変性を完全に捉えているわけではないが、誤差関数 $\operatorname {erf}$ はエッジのぼやけをモデル化する単純な方法としてよく使われている^[1]^[2]。1次元の画像 $f$ があり、 $x=0$ の位置に1つのエッジがあるとき、そのモデルは次のように表される。

$f(x)={\frac {I_{r}-I_{l}}{2}}\left(\operatorname {erf} \left({\frac {x}{{\sqrt {2}}\sigma }}\right)+1\right)+I_{l}$

エッジの左側では、輝度は $I_{l}=\lim _{x\rightarrow -\infty }f(x)$ 、右側では $I_{r}=\lim _{x\rightarrow \infty }f(x)$ となる。尺度パラメータ σ をエッジのぼやけ尺度と呼ぶ。

エッジ検出法

エッジ検出には様々な手法があるが、大まかに2種類に分類できる。探索ベースの手法とゼロ交差法をベースとした手法である。探索ベースの手法ではまず、通常1次微分で勾配を計算することでエッジの強さを計算し、勾配の方向からエッジの局所的方向を予測し、その方向の勾配が局所的に極大となる箇所を探す。ゼロ交差法ベースの手法では、対象の画像から計算した2次微分式でのゼロ交差を探すもので、一般にラプラシアンでのゼロ交差か非線形微分式でのゼロ交差を探す。エッジ検出の前段階として平滑化（ガウス平滑化が一般的）を行うのが普通である（ノイズリダクション参照）。

エッジ検出法は、主に利用する平滑化フィルタの種類とエッジの強さの計算方法が異なる。多くのエッジ検出法は画像の輝度の勾配計算に基づいており、X軸方向とY軸方向で勾配を見積もる計算に使うフィルタの種類もそれぞれで異なる。

キャニー法 (Canny edge detector)

→「en:Canny edge detector」も参照

ジョン・キャニーは1986年^[3]、エッジの検出・局所化・複数応答の最小化を可能にする理想の平滑化フィルタを数学的に検討した。彼はこれらの仮定に基づく理想のフィルタが4つの指数項の総和で表されることを示した。また、そのフィルタはガウス関数の1次微分で近似できることも示した。彼はまた「非最大（エッジ）抑制」という観念を導入した。それは事前平滑化フィルタを適用したとき、エッジが勾配方向の勾配の大きさが局所的な極大となる箇所であると定義したものである。

同氏はコンピュータビジョンの先駆者だが、キャニー法は今^[いつ?]でも最先端のエッジ検出法である。事前条件が特殊でない限り、キャニー法よりも性能のよいエッジ検出法を見つけることは難しい。

キャニー・デリチェ法^[4] (Canny-Deriche detector) もキャニー法と同様の数学的手法で得られたエッジ検出法だが、離散的観点から出発しているため、指数フィルタやガウシアンフィルタではなく画像平滑化の再帰フィルタを生み出した。

後述する微分エッジ検出法は、キャニー法を尺度空間 (scale space) 表現から計算される微分不変量の観点から再定式化したものとも言える。

その他の1次の手法

画像の輝度の勾配を見積もる方法はいくつもある。最も単純な方法は次のような中央差分の式で表される。

$L_{x}(x,y)=-1/2\cdot L(x-1,y)+0\cdot L(x,y)+1/2\cdot L(x+1,y)\,$

$L_{y}(x,y)=-1/2\cdot L(x,y-1)+0\cdot L(x,y)+1/2\cdot L(x,y+1)\,$

これは、次のような畳み込みのフィルタで画像をマスクするのに相当する。

$L_{x}={\begin{bmatrix}-1/2&0&1/2\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{y}={\begin{bmatrix}+1/2\\0\\-1/2\end{bmatrix}}*L$

比較的古くからあるSobelオペレータは、次のフィルタに基づいている。

$L_{x}={\begin{bmatrix}-1&0&+1\\-2&0&+2\\-1&0&+1\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{y}={\begin{bmatrix}+1&+2&+1\\0&0&0\\-1&-2&-1\end{bmatrix}}*L$

1次微分の見積もりがこのように与えられると、勾配の大きさは次のように計算できる。

$|\nabla L|={\sqrt {L_{x}^{2}+L_{y}^{2}}}$

このとき勾配の方向は次のように見積もられる。

$\theta =\operatorname {atan2} (L_{y},L_{x})$

同様の手法としては他にもPrewittオペレータやRoberts crossがある。

しきい値処理と連結処理

勾配の大きさなどでエッジの強さを計算すると、次にしきい値を適用して必要なエッジだけを抽出する必要がある。しきい値を低く設定すればエッジは多くなり、ノイズの影響を受けやすくなるため、画像の本質的でない特徴を捉えてしまいやすくなる。逆にしきい値を高く設定すると断片化したエッジしか得られないことになる。

勾配の強さを画像化したものにしきい値を適用すると、得られるエッジは太いのが普通で、なんらかの方法でそれを細くする必要がある。非最大抑制でエッジ検出した場合、その定義上エッジは細くなり、エッジ連結処理を施すことでエッジの線同士を連結して多角形を形成することができる。離散的な手法で非最大抑制のような効果を得るには、1次微分から勾配方向を見積もり、それを45度単位に丸め、その勾配方向での勾配の強さを比較する。

適切なしきい値を求めるために一般に使われる手法は、ヒステリシスを伴った適応的しきい値処理と呼ばれる手法である。これは、複数のしきい値を使うもので、まず最大のしきい値でエッジの始点を求める。始点が見つかったら、そこからエッジがどう続いているかをピクセル単位に検討していき、最小のしきい値より上のエッジ箇所を全て見ていき、しきい値未満になった時点で追跡をやめる。この手法はエッジが連続的な曲線になっていると仮定しており、不要なエッジを検出することなく、必要なエッジのかすかな部分も検出できるという利点がある。それでも適切なしきい値を選択する問題は残っており、一般に画像によって適切なしきい値は異なる。

2次の手法

一部のエッジ検出法は輝度の2次微分に基づいている。これは輝度勾配における変化率を捉えるものである。したがって、理想の連続的ケースでは2次導関数でのゼロ交差が勾配の局所的極大になる。

初期のマー・ヒルドレス法 (Marr–Hildreth algorithm) は、ガウシアン平滑化画像にラプラシアンを適用してゼロ交差を検出するものであった。しかし、この方法では偽のエッジも検出しやすい。また、曲線のエッジに弱い性質がある。このため、現在ではほとんど使われない。

微分エッジ検出

より洗練された2次のエッジ検出法として微分エッジ検出 (differential edge detection) がある。これは自動的にサブピクセルの正確さでエッジの位置を求めることができるもので、勾配方向の2次導関数のゼロ交差を以下のように検出する手法に基づいている。非最大抑制^[2]の必要条件を表現する微分幾何学的方法に基づき、画像の全ての点に画像の勾配方向を v-軸とする局所的な座標系 $(u,v)$ を導入する。画像は事前にガウシアン平滑化されているものとし、尺度 $t$ における尺度空間表現 $L(x,y;t)$ を計算しておく。尺度表現の勾配の大きさは、v-方向 $L_{v}$ における1次微分係数に等しく、それをv-方向に1次微分した値はゼロになるはずである。

$\partial _{v}(L_{v})=0$

そして、 $L_{v}$ をv-方向に2次微分すると負になる。

$\partial _{vv}(L_{v})\leq 0$

局所的な偏導関数 $L_{x}$ , $L_{y}$ ... $L_{yyy}$ で明示的な式として書くと、このエッジの定義は微分不変量のゼロ交差曲線として表現できる。

$L_{v}^{2}L_{vv}=L_{x}^{2}\,L_{xx}+2\,L_{x}\,L_{y}\,L_{xy}+L_{y}^{2}\,L_{yy}=0$

このとき、以下の微分不変量の符号条件が成り立つ。

$L_{v}^{3}L_{vvv}=L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\,L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}\leq 0$

ここで、 $L_{x}$ , $L_{y}$ ... $L_{yyy}$ は、元の画像をガウシアン平滑化したものから得た尺度空間表現 $L$ から計算した偏導関数である。このようにして、エッジをサブピクセルの正確さで曲線として自動的に得ることができる。ヒステリシスしきい値処理をこれに適用することもできる。

1次微分の近似は上述したように中央差分で計算できるが、2次微分の近似は次のような尺度空間表現 $L$ から計算できる。

$L_{xx}(x,y)=L(x-1,y)-2L(x,y)+L(x+1,y)\,$

$L_{xy}(x,y)=(L(x-1,y-1)-L(x-1,y+1)-L(x+1,y-1)+L(x+1,y+1))/4\,$

$L_{yy}(x,y)=L(x,y-1)-2L(x,y)+L(x,y+1)\,$

これは次のような畳み込みのフィルタによるマスクと対応している。

$L_{xx}={\begin{bmatrix}1&-2&1\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{xy}={\begin{bmatrix}-1/4&0&1/4\\0&0&0\\1/4&0&-1/4\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{yy}={\begin{bmatrix}1\\-2\\1\end{bmatrix}}*L$

脚注

^ W. Zhang and F. Bergholm: Multi-Scale Blur Estimation and Edge Type Classification for Scene Analysis, International Journal of Computer Vision, Volume 24, Issue 3, pages 219 - 250, 1997
^ ^a ^b Lindeberg, T., "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, 30, 2, pp 117--154, 1998.
^ Canny, J., A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714, 1986.
^ R. Deriche, Using Canny's criteria to derive an optimal edge detector recursively implemented, Int. J. Computer Vision, Vol. 1, pp. 167-187, April 1987.

参考文献

Ziou, D. and Tabbone, S.: Edge Detection Techniques An Overview, International Journal of Pattern Recognition and Image Analysis, 8(4):537--559, 1998 (Contains an extensive set of references.)

背景