コーナー検出法

コーナー検出法(コーナーけんしゅつほう)とは、コンピュータビジョンにおいて確実といえる特徴点を抽出し画像の中身を推測するための手法である。コーナー検出法は動き検出，画像マッチング，画像追跡，イメージモザイキング，パノラマ画像生成，3Dモデリング,物体認識でよく使われている。コーナー検出法は特徴点検出法とも共通点がある。

問題の定式化

コーナーとは2つのエッジの交点と定義することができる。コーナーは、ある局所近傍で方向の異なる2つの際立ったエッジが存在するような点と定義することもできる。特徴点とは、際立って検出できる画像上の点のことをいう。これは、特徴点がコーナーになれるということだけでなく、例えば、強度が極大・極小の点、曲線の終点、あるいは曲率が極大である曲線上の点、といった孤立点でもあることを意味する。実際は、コーナー検出法と呼ばれているものの多くは、コーナー点だけでなく特徴点を検出する。結果として、コーナーだけを検出する場合は検出された特徴点を局所分析してどれが真のコーナーなのかを決定する必要がある。コーナー検出のための後処理と共に使われるエッジ検出の例としてKirsch検出オペレータ、Frei-Chenマスクがある。

なお、書物では﹁コーナー(corner)﹂，﹁特徴点(interest point)﹂，﹁特徴(feature)﹂を取り違えて書かれることがあり、注意が必要である。特に挙げられることとして、"特徴点検出オペレータ(interest point operator)"としてのblob検出器がいくつかあるが、それらは時々誤って"コーナー検出器"として言及されることがある。さらには、細長い像を検出するためのリッジ検出(ridge detection)といったものも存在する。

コーナー検出器は通常それほど安定しておらず、熟練した管理、過失を防ぐための十分な認識が必要である。コーナー検出器の性能は、異なる明るさ、置き換え、回転、その他の変換の下での類似した多数の画像から同じコーナーを検出する能力によって決定される。画像におけるコーナー検出の単純なものとして相関を使うというのがあるが、計算量が多く適していない。代わりによく用いられる方法として、HarrisとStephensの提案を基にした検出法(以下に記述)があり、順にハンス・モラベックの方法を改良したものである。

モラベック︵Moravec︶のコーナー検出アルゴリズム

この方法は最も早く考案されたコーナー検出アルゴリズムの1つで、コーナーを自己相似性が少ない点と定義している。このアルゴリズムは画像の各ピクセルを検査し、ピクセルを中心とするパッチが、近傍の多く重なるパッチとどの程度似ているかを考慮してコーナーかどうかを調べる。類似度はパッチの差分の2乗和(SSD)によって計測される。低い数値は類似性が高いことを指す。

ピクセルが同程度の強度の範囲内ならば、近傍のパッチは類似している。ピクセルがエッジ上にあれば、エッジと直交する方向にある近傍のパッチは大きく異なって見えるが、エッジと等方向にある近傍のパッチは小さな変化として検出される。ピクセルが全ての方向に異なった特徴点上にあれば、近傍のパッチはどれも類似しない。

コーナーの強さはパッチと近傍のパッチ︵水平，垂直と2つの対角線方向︶のSSDの最小値として定義される。この数値が極大であれば特徴点が存在するということになる。

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

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

Harris と Stephens は、位置の異なるパッチを用いる代わりに、真っ直ぐな方向を重視したコーナースコアの差分を考慮することで、モラベックのコーナー検出器を改良した。(コーナースコアは、この検出器が論文で使われて以降、しばしば自己相関として言及される。しかしながら、論文で用いられている数式は明らかに差分の2乗和が使われていることを示している。)

グレースケールの2次元画像を用いるとする。こうしても一般性を失わない。この画像を $I$$I$とする。領域 $(u,v)$$(u,v)$上に画像のパッチを置き、 $(x,y)$$(x,y)$ずらすことを考える。2つのパッチの差分の重みつき2乗和(SSD) $S$$S$は以下で与えられる。

$S(x,y)=\sum _{u}\sum _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$$S(x,y)=\sum _{u}\sum _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$
$I(u+x,v+y)$$I(u+x,v+y)$ はテイラー展開により近似できる。$I_{x}$$I_{x}$ , $I_{y}$$I_{y}$を $I$$I$の偏導関数とすると、

$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$
この近似式から次の近似式が導かれる。

$S(x,y)\approx \sum _{u}\sum _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2}$$S(x,y)\approx \sum _{u}\sum _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2}$
これを行列で書くと次のようになる。

$S(x,y)\approx {\begin{pmatrix}x&y\end{pmatrix}}A{\begin{pmatrix}x\\y\end{pmatrix}}$$S(x,y)\approx {\begin{pmatrix}x&y\end{pmatrix}}A{\begin{pmatrix}x\\y\end{pmatrix}}$
A は構造テンソルを表す。

$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}}$$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}}$
この行列はHarris行列であり、< >は平均( $(u,v)$$(u,v)$上での総和)を意味する。円形のウィンドウ︵あるいは円形の重み付けが行われるガウス関数)が用いられていれば、結果は等方的になる。

コーナー︵一般的には特徴点︶は、ベクトル ${\begin{pmatrix}x&y\end{pmatrix}}$${\begin{pmatrix}x&y\end{pmatrix}}$の全ての方向での $S$$S$の大きな変化量により特徴付けられる。 $A$$A$の固有値を分析することにより、この特徴付けは次のように表現できる: $A$$A$は特徴点に対して2つの"大きな"固有値を持たなければならない。固有値の大きさにより、本議論に基づいて以下の推測ができる。

(一)$\lambda _{1}\approx 0$$\lambda _{1}\approx 0$ かつ $\lambda _{2}\approx 0$$\lambda _{2}\approx 0$であれば、ピクセル$(x,y)$$(x,y)$は特徴点をもたない。

(二)$\lambda _{1}\approx 0$$\lambda _{1}\approx 0$ かつ $\lambda _{2}$$\lambda _{2}$が正のある程度大きい値であれば、エッジが存在する。

(三)$\lambda _{1}$$\lambda _{1}$ , $\lambda _{2}$$\lambda _{2}$が正の大きな値であれば、コーナーが存在する。

HarrisとStephensは、平方根の計算が必要なため、固有値の正確な計算は計算量が多いということを言及している。代わりに敏感に調整できる $\kappa$$\kappa$をパラメータとする関数 $M_{c}$$M_{c}$を提案している。

${\displaystyle M_{c}:=\lambda _{1}\lambda _{2}-\kappa \,(\lambda _{1}+\lambda _{2})^{2}=\operatorname {det} ($A)-\kappa \,\operatorname {trace} ^{2}(A)} $M_{c}:=\lambda _{1}\lambda _{2}-\kappa \,(\lambda _{1}+\lambda _{2})^{2}=\operatorname {det} (A)-\kappa \,\operatorname {trace} ^{2}(A)$
したがって、本アルゴリズムは実際に行列$A$$A$の固有値分解を計算する必要はなく、コーナーあるいはより一般的に特徴点を見つけ出すために、 $A$$A$の行列式と固有和を評価するだけで十分である。$\kappa$$\kappa$の値は実験から決めるしかなく、論文で 0.04 - 0.15 の範囲が適性であると報告されている。

コーナー点における共分散行列は $A^{-1}$$A^{-1}$ i.e. ${\frac {1}{\langle I_{x}^{2}\rangle \langle I_{y}^{2}\rangle -\langle I_{x}I_{y}\rangle ^{2}}}{\begin{bmatrix}\langle I_{y}^{2}\rangle &-\langle I_{x}I_{y}\rangle \\-\langle I_{x}I_{y}\rangle &\langle I_{x}^{2}\rangle \end{bmatrix}}$${\frac {1}{\langle I_{x}^{2}\rangle \langle I_{y}^{2}\rangle -\langle I_{x}I_{y}\rangle ^{2}}}{\begin{bmatrix}\langle I_{y}^{2}\rangle &-\langle I_{x}I_{y}\rangle \\-\langle I_{x}I_{y}\rangle &\langle I_{x}^{2}\rangle \end{bmatrix}}$である。

多重スケールHarrisオペレータ

Harrisオペレータによる2次モーメント行列(構造テンソル)$A$$A$の計算は、偏導関数$I_{x},I_{y}$$I_{x},I_{y}$の非線形結合の総和計算だけでなく、これら偏導関数の計算を必要とする。偏微分が大抵スケール空間の平滑化を必要とするようになってから、Harrisオペレータでは2つのスケールパラメータの定義が必要になった‥ (i) 偏微分に先立つ平滑化のための局所スケール (ii) 微分演算子上での非線形作用素を積分された画像描写へと累積するための積分スケール

$I$$I$は元の画像強度を表し、$L$$L$はガウス核の畳み込みにより得られた$I$$I$のスケール空間表現を表す。

$g(x,y,t)={\frac {1}{2{\pi }t}}e^{-(x^{2}+y^{2})/2t}$$g(x,y,t)={\frac {1}{2{\pi }t}}e^{-(x^{2}+y^{2})/2t}$
局所スケールパラメータ$t$$t$を用い:

$L(x,y,t)\ =g(x,y,t)*I(x,y)$$L(x,y,t)\ =g(x,y,t)*I(x,y)$
$L_{x}=\partial _{x}L$$L_{x}=\partial _{x}L$ , $L_{y}=\partial _{y}L$$L_{y}=\partial _{y}L$として、$L$$L$の偏導関数を表すことにする。 さらに、ガウス窓(Gaussian window)$g(x,y,s)$$g(x,y,s)$を積分スケールパラメータ$s$$s$と共に取り入れる。このとき、多重スケール2次モーメント行列は次のように定義できる。

$\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 .$$\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 .$
このとき、$\mu$$\mu$の固有値を$A$$A$の固有値と同様に計算でき、多重スケールHarrisコーナー測度を次のように定義できる。

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

局所スケールパラメータ$t$$t$と、積分スケールパラメータ$s$$s$の選択については、これらのスケールパラメータが通常であるような相対積分スケールパラメータ$\gamma$$\gamma$を用いて対にすると、$s=\gamma ^{2}t$$s=\gamma ^{2}t$ , $\gamma$$\gamma$は $[1,2]$$[1,2]$から取る。このようにして、画像領域で変化するコーナー構造に反応する多重スケールコーナー検出器を手に入れるために、多重スケールHarrisコーナー測度$M_{c}(x,y;t,\gamma ^{2}t)$$M_{c}(x,y;t,\gamma ^{2}t)$を、スケール空間でのどのスケール$t$$t$に対しても計算することができる。

実際は、この多重スケールコーナー検出器はスケール標準化されたラプラス作用素であるようなスケール選択することで補完される。

$\nabla _{norm}^{2}L(x,y;t)=t\nabla ^{2}L(x,y,t)=t(L_{xx}(x,y,t)+L_{yy}(x,y,t))$$\nabla _{norm}^{2}L(x,y;t)=t\nabla ^{2}L(x,y,t)=t(L_{xx}(x,y,t)+L_{yy}(x,y,t))$
がスケール空間の各スケールごとに計算され、適合したスケールに自動選択された(Harris-Laplace演算子)コーナー点が同時に計算される。

多重スケールコーナー測度$M_{c}(x,y;t,\gamma ^{2}t)$$M_{c}(x,y;t,\gamma ^{2}t)$の空間的な最大値

$({\hat {x}},{\hat {y}};t)=\operatorname {argmaxlocal} _{(x,y)}M_{c}(x,y;t,\gamma ^{2}t)$$({\hat {x}},{\hat {y}};t)=\operatorname {argmaxlocal} _{(x,y)}M_{c}(x,y;t,\gamma ^{2}t)$
スケール標準化されたラプラス作用素$\nabla _{norm}^{2}(x,y,t)$$\nabla _{norm}^{2}(x,y,t)$のスケールの極大・極小値

${\hat {t}}=\operatorname {argmaxminlocal} _{t}\nabla _{norm}^{2}L({\hat {x}},{\hat {y}};t)$${\hat {t}}=\operatorname {argmaxminlocal} _{t}\nabla _{norm}^{2}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言語コード）