角は画像の中の一種の基礎特徴とも言えます。
もっとも基本的な方法としてはエッジの角度を算出し、近隣のエッジポイントの角度の差を計算します。これは基本的に差分法になりますので、ノイズにとても影響され易いと考えられます。このため、この基本方法から一歩か二歩を進んだ方法にHarris法があります。
Harris法は\( (x,y) \)を中心とする、\( (x+i,y+j) \)のウィンドウを考えます。\( ( (i,j) \in [-w,w]\times[-w,w] ) \) このウィンドウにバイアスを加えて\( (x+i+u,y+j+v) \)と\( (x+i,y+j) \)の差を考えます。もし\( (u,v) \)はエッジの方向にそっているなら、差は小さいはずです。エッジに沿わないなら、差は大きいはずです。Harris法はエッジポイントにおいて、差の合計が最小になるように\( (u,v) \)を探し、最小の合計値を曲率の指標とします。つまり、下記の式になります。
\[ E_{u,v}=\sum_{i=-w}^{w}\sum_{j=-w}^{w}(\frac{\partial P_{x+i,y+j}}{\partial x}u+\frac{\partial P_{x+i,y+j}}{\partial y}v)^2 \]
Harris法は\( \{ (u,v) | \| (u,v) \|=1 \} \)において、最小の\( E_{u,v} \)を探します。
一見、単位円に沿って\( (u,v) \)を試していく必要があるようですが、実際はそうではありません。数学は美しく助けてくれます。まずは、詳しく見ましょう。\( E_{u,v} \)は下記の式に分解できます。
\[ E_{u,v}=A(x,y)^2 u^2 + 2 B(x,y) u v + C(x,y)^2 v^2 \]
\[ A(x,y)=\sum_{i=-w}^{w}\sum_{j=-w}^{w}(\frac{\partial P_{x+i,y+j}}{\partial x})^2 \]
\[ B(x,y)=\sum_{i=-w}^{w}\sum_{j=-w}^{w}(\frac{\partial P_{x+i,y+j}}{\partial x} \frac{\partial P_{x+i,y+j}}{\partial y}) \]
\[ C(x,y)=\sum_{i=-w}^{w}\sum_{j=-w}^{w}(\frac{\partial P_{x+i,y+j}}{\partial y})^2 \]
更に、行列で考えてミマスと、
\( M=\left [ \begin{matrix}
A(x,y) & B(x,y) \\
B(x,y) & C(x,y)
\end{matrix} \right ] \), \( W=\left[ \begin{matrix} u \\ v \end{matrix} \right] \)
とすれば、\( E_{u,v}=W’ M W \)。
行列\( Q \)による直行変換を考えましょう。\( Q \)の両列は\( M \)の固有ベクトルです。\( Q \)は回転でもあります。
\( F_{u,v}=(Q W)’ M Q W = W’ Q’ M Q W = W’ D W \)
\( D \)は対角行列です。\( D=\left[ \begin{matrix} \alpha & 0 \\ 0 & \beta \end{matrix} \right] \)
ここで、回転を無視すれば、\( E_{u,v} \)の値の分布は、\( \alpha \)と\( \beta \)にかなり説明されます。回転は実に無視できます。回転は分布の形状を変えないからです。この考えに基づいて、Harris法は最終に下記の式で曲率の評価指標を算出しています。
\( \kappa_k = \alpha \beta – k ( \alpha + \beta ) \)
この式は最小の\( E_{u,v} \)と完全に一致しないですが、似たような特徴があります。\( E_{u,v} \)所在の\( (x,y) \)はほぼ直線の場合は、\( \alpha \)と\( \beta \)の大きさは近い。逆に、ほぼ角の場合は\( \alpha \)と\( \beta \)の差は大きいです。\( k \)は調整用のパラメータです。\( \alpha \)と\( \beta \)の考え方としては、\( E_{u,v} \)が直線にあれば、\( Q \)での回転でx軸かy軸に沿う直線になります。結果は\( \alpha \)と\( \beta \)のどっちかが0です。逆に角の場合は、どんなに回転しても数値は２方向に蔓延ります。結果、\( \alpha \)と\( \beta \)両方は0ではない。
更に、線形代数から、下記の関係が分かります。\( \alpha \beta = A(x,y) C(x,y) – B(x,y)^2 \)、\( \alpha+\beta = A(x,y) + C(x,y) \)
ここまで、Harris法を計算するすべての要素が揃いました。
効果を見てみましょう。
各図から見れると思いますが、曲がる所はちゃんと検出されています。ただ、まっすぐに使い所も検出される場合があります。これは主に近い二重線などによる物です。二重線であれば、ウィンドウ内の分布は片方向で説明できないので、両方向の分布になり、角と区別がつかなくなります。
でも、Harris法はやはり綺麗です。