コーナー検出法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

この項目「コーナー検出法」は途中まで翻訳されたものです Template:翻訳中途の呼び出しエラー: 翻訳元の指定は必須です。1=[翻訳元への固定リンク翻訳元の版情報]としてください。。
翻訳作業に協力して下さる方を求めています。詳細はこの項目のノートや履歴、翻訳のガイドラインなどを参照してください。翻訳情報の要約欄への記入をお忘れなく。
Template:翻訳中途の呼び出しエラー: 貼付した年月の指定は必須です。date={{subst:#time:Y年F}}を書き込んでください。

コーナー検出または特異点検出とはコンピュータビジョンにおいて画像の特徴点または角を検出する手法である。コンピュータービジョンではある種の特徴点を抽出し、画像の中身を推測する。コーナー検出は動き検出, 追跡, イメージモザイキング, パノラマ画像生成, 3Dモデリング, 物体認識などで用いられる。

1 問題の定式化
2 モラベック（Moravec）のコーナー検出アルゴリズム
3 HarrisとStephens、Plesseyのコーナー検出アルゴリズム
4 マルチスケールHarrisオペレータ
5 ShiとTomasiの方法
6 曲率による方法
7 ラプラシアン・ガウシアンと派生法
8 WangとBradyの方法
9 SUSANオペレータ
10 Trajkovic and Hedleyの手法
11 FAST特徴検出
12 参考文献
13 実装コード

[編集] 問題の定式化

コーナーとは二つのエッジが交差したものだと定義することができる。また、コーナーは、ローカルの近傍に二つの異なる方向を向いた強いエッジが存在する点と定義できる。特徴点とは、画像の上にある点で、明確に定義された場所にあって安定的に検出することが可能なものである。これは、特徴点がコーナーであると同時に、たとえば、ローカルの輝度が最大や最小、線の終わり、カーブ上にある、曲率が局所的に最大である、等とにより、孤立点でもありえることを意味する。実際には、ほぼすべてのいわゆるコーナー検出手法はコーナーだけを抽出するのではなく、一般的な特徴点を抽出する。結果として、コーナーだけを検出するのであれば、検出された特徴点の局所領域を解析してどれが真のコーナーなのかを決定する必要がある。残念ながら、表現上は「コーナー(corner)」「特徴点(interest point)」「特徴(feature)」はある程度同じ意味に用いられおり、問題を若干わかりづらいものにしている。特に、"特徴点オペレータ(interest point operator)"と呼ばれるいくつかのblob検出器があるが、これらも誤って "コーナー検出器"と呼ばれることがある。さらには、長いオブジェクトを探し出すエッジ検出(ridge detection)という用語も存在する。

コーナー検出器は通常それほど安定しておらず、専門家による監視や、中心的な認識処理の個々の誤りを防ぐために大きな冗長性を必要とする。コーナー検出器の性能は、複数の類似した画像、たとえば照明や透明度、回転などの変換が異なるものから、同じコーナーを検出できる能力によって判定される。コーナー検出の単純なアプローチとしては相関を用いるものがあるが、計算量が多く最善ではない。その他の方法としてよく用いられるのは Harris と Stephens の方法（下記）で、ハンス・モラベックの手法を改善したものである。

[編集] モラベック（Moravec）のコーナー検出アルゴリズム

この方法は、最初期のコーナー検出アルゴリズムの一つで、コーナーを自己相似性が少ない点と定義している。このアルゴリズムは画像の各ピクセルをについて、その点を中心としたパッチが、近傍にある、重なった部分の大きいパッチとどの程度類似しているかを考えることにより、コーナーがあるかどうかを判定する。類似の度合いは、二つのパッチの差分の二乗の総和(SSD)によって計測される。低い数値は高い類似性を意味する。

ピクセルが同じ輝度の領域内にあれば、近傍のパッチは類似している。ピクセルがエッジ上にあれば、エッジと直行する方向にある近傍のパッチは大きく異なって見えるが、エッジと同じ方向にある近傍のパッチは類似している。ピクセルがすべての方向に異なった特徴点の上にあれば、近傍のパッチはどれも類似しない。

パッチと近傍（水平、垂直と斜め二方向）の中で最小のSSDがコーナーの強さとして定義される。この数値が近傍最大であれば、対象とする特徴が存在する。

モラベックにより指摘されたように、このオペレータの大きな問題の一つは等方的でない、すなわち近傍の方向と異なるエッジが存在した場合には、特徴点として検出されないことである。

[編集] HarrisとStephens、Plesseyのコーナー検出アルゴリズム

Harris と Stephens は、ずらしたパッチを用いるのではなく、ある方向についてのコーナー評価スコアの差分を直接考慮することで、モラベックのコーナー検出器を改善した。このコーナー評価スコアは、コーナー検出器が提唱された論文中でその単語が用いられているため、しばしば自己相関と呼ばれる。しかし、論文中の数式は明確に SSD が用いられていることを示している。

一般性を失わなうことなく、グレースケールの2次元画像が用いられると仮定する。画像が $I$ で与えられる。領域 $(u, v)$ の上に画像のパッチを張り、これを $(x, y)$ ずらす。二つのパッチ同士の重み付けされた差分の二乗の総和 $S$ は、以下によって与えられる：

$S(x,y) = \sum_u \sum_v w(u,v) \, \left( I(u,v) - I(u-x,v-y) \right)^2$

Harris の行列 $A$ は二次のテイラー展開により $S$ で近似できる。

$S(x,y) \approx S(0,0) + \begin{pmatrix} x & y \end{pmatrix} \nabla S + \frac{1}{2} \begin{pmatrix} x & y \end{pmatrix} A \begin{pmatrix} x \\ y \end{pmatrix}$

ここで、 $\nabla S$ および $A$ は $S$ の勾配ベクトルとヘッセ行列 (二階微分) をそれぞれ示し、いずれも $\begin{pmatrix} x & y \end{pmatrix} = \begin{pmatrix} 0 & 0 \end{pmatrix}$ で評価される。 $S$ の定義により、 $S (0,0)$ と $\nabla S$ は消滅し、以下を得る：

$S(x,y) \approx \frac{1}{2} \begin{pmatrix} x & y \end{pmatrix} A \begin{pmatrix} x \\ y \end{pmatrix}$

これは小さい $\begin{pmatrix} x & y \end{pmatrix}$ において有効である。

$S$ は画像の輝度 $I$ の関数であるため、 $\begin{pmatrix} x & y \end{pmatrix} = \begin{pmatrix} 0 & 0 \end{pmatrix}$ であることを考慮すると $A$ も $I$ の微分として表現できる：

$A = \sum_u \sum_v w(u,v) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} = \begin{bmatrix} \langle I_x^2 \rangle & \langle I_x I_y \rangle\\ \langle I_x I_y \rangle & \langle I_y^2 \rangle \end{bmatrix},$

ここで、山形かっこは（ $(u, v)$ の総和に対する)平均を意味し、また、偏微分の標準的な記号を用いる。円形のウィンドウ（あるいは円形の重み付けが行われるガウス関数)が用いられていれば、反応性は等方的になる。

コーナー（あるいは、より一般的に特徴点）は、ベクトル $\begin{pmatrix} x & y \end{pmatrix}$ のすべての方向に大きな変動があることによって特徴付けられる。 $A$ の固有値を解析することにより、この特徴付けは次のように表現できる： $A$ は特徴点に対して二つの大きな固有値を持たなければならない。

固有値の大きさにより、本議論に基づき以下の推測ができる：

$\lambda_1 \approx 0$ かつ $\lambda_2 \approx 0$ であれば、ピクセル $(x, y)$ には特徴点は一つもない。
$\lambda_1 \approx 0$ かつ $λ 2$ が正のあるていど大きい値であれば、エッジが存在する。
$λ 1$ と $λ 2$ がいずれも大きく、異なる正の値であれば、コーナーが存在する。

Harris と Stephens は、平方根の計算が必要なため、固有値の正確な計算は計算量が大きく、代わりに, $κ$ を調整可能な感度のパラメータとする関数 $M c$ を提案している。

$M_c = \lambda_1 \lambda_2 - \kappa \, (\lambda_1 + \lambda_2)^2 = \operatorname{det}(A) - \kappa \, \operatorname{trace}^2(A)$

したがって、本アルゴリズムは行列 $A$ の固有値分解を実際に計算するのではなく、コーナーや一般的な特徴点を見つけ出すため $A$ の行列式とトレースを評価するだけで十分である。 $κ$ の値は経験的に決定する必要があり、論文によれば 0.04 - 0.15 の範囲が適していると報告されている。

[編集] マルチスケールHarrisオペレータ

Harrisオペレータにおいて二次モーメント行列（"構造テンソル"とも呼ばれる場合がある） $A$ の計算は、画像の微分 $I x, I y$ と、これらのローカル近傍における微分値を非線形結合したものの総和の計算を必要とする。微分値の計算は通常スケール空間の平滑化の段階を含むため、Harrisオペレータの演算上の定義は二つのスケールのためのパラメータを必要とする： (i) 画像の演算に先立つ平滑化のための局所的なスケール および(ii) 微分演算子上で非線形演算を統合された画像記述子に加算するための 統合スケール $I$ は原画像の輝度を示し、 $L$ ガウシアンカーネルによる畳み込みで得られた $I$ のスケール空間表現を示す。

$g(x, y, t) = \frac {1}{2{\pi} t}e^{-(x^2+y^2)/2t}$

局所スケールパラメータ $t$ を用い:

$L(x, y, t)\ = g(x, y, t) * I(x, y)$

and let $L_x = \partial_x L$ and $L_y = \partial_y L$ は、 $L$ の偏導関数を示す。さらに、ガウシアンウィンドウ関数 $g (x, y, s)$ を統合スケールパラメータ $s$ とともに導入する。そして、マルチスケール二次モーメント行列 (Lindeberg and Garding 1997) が下記のように定義できる。

$\mu(x, y; t, s) = \int_{\xi = -\infty}^{\infty} \int_{\eta = -\infty}^{\infty} \begin{bmatrix} L_x^2(x-\xi, y-\eta; t) & L_x(x-\xi, y-\eta; t) \, L_y(x-\xi, y-\eta; t) \\ L_x(x-\xi, y-\eta; t) \, L_y(x-\xi, y-\eta; t) & L_y^2(x-\xi, y-\eta; t) \end{bmatrix} g(\xi, \eta; s) \, d\xi \, d\eta.$

ここで、 $μ$ の固有値を、 $A$ の固有値と同様の方法で計算し、マルチスケールHarrisのコーナー評価を次のように計算することができる。

$M_c(x, y; t, s) = \operatorname{det}(\mu(x, y; t, s)) - \kappa \, \operatorname{trace}^2(\mu(x, y; t, s))$ .

局所スケールパラメータ $t$ と、統合スケールパラメータ $s$ の選択については、これらのスケールパラメータが通常、 $s = γ 2 t$ であるような相対統合スケールパラメータ $γ$ を $[\sqrt{2}, 2]$ の間から選択する。それにより、マルチスケールの Harris コーナー評価値 $M c (x, y; t,γ 2 t)$ を、スケール空間の任意のスケール $t$ において、マルチスケールのコーナー検出器を取得するために計算することができ、これは画像領域内で変動するサイズのコーナー構造(Baumberg 2000)に対応するものである。

実際は、マルチスケールのコーナー検出器はよくスケール選択ステップによって補完され、スケールで正規化されたラプラシアン演算子(Lindeberg 1998)

$\nabla^2_{norm} L(x, y; t)\ = t \nabla^2 L(x, y, t) = t (L_{xx}(x, y, t) + L_{yy}(x, y, t))$

がスケール空間の各スケールごとに計算され、また自動スケールの選択によるスケール適応コーナー点（"Harris-Laplace演算子"）が(Mikolajczyk and Schmid 2004)が同時に求められる:

マルチスケールコーナー評価値 $M c (x, y; t,γ 2 t)$ の空間的な最大値

$(\hat{x}, \hat{y}; t) = \operatorname{argmaxlocal}_{(x, y)} M_c(x, y; t, \gamma^2 t)$
スケールで正規化されたラプラシアン演算子 $\nabla^2_{norm}(x, y, t)$ のスケールによる局所最大最小値

$\hat{t} = \operatorname{argmaxminlocal}_{t} \nabla^2_{norm}L(\hat{x}, \hat{y}; t)$ .

[編集] ShiとTomasiの方法

[編集] 曲率による方法

[編集] ラプラシアン・ガウシアンと派生法

[編集] WangとBradyの方法

[編集] SUSANオペレータ

日本で最近よく用いられる手法である。S.M. Smithらによって開発された検出法。SUSANとはSmallest Univalue Segment Assymilating Nucleusの略である。

円形マスクを用いてマスク中の「任意の閾値以上の画素数」をカウントする。

[編集] Trajkovic and Hedleyの手法

[編集] FAST特徴検出

[編集] 参考文献

[編集] 実装コード

ここで紹介したいくつかの手法はそれぞれの著者自身などがコードを書いて公開している。

SUSAN（C言語コード）

この「コーナー検出法」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる人を求めています（Portal:コンピュータ）。

カテゴリ: 翻訳中途 | コンピュータビジョン | コンピュータ関連のスタブ項目

See also ebooksgratis.com: no banners, no cookies, totally FREE.