下記のWikipediaなどを元に、Harrisコーナー検出に関する導出について取りまとめを行いました。
Harris Corner Detection
2×2行列の固有値とTrace・Determinant
A = \left( \begin{array}{cc} a & b \\ c & d \end{array} \right)
上記のように定義された$2 \times 2$行列$A \in \mathbb{R}^{2 \times 2}$の固有値を$\lambda_{1}, \lambda{2}$、トレースを$\mathrm{tr}(A)$、行列式を$\det{(A)}$とおくとき、下記の式が成立します。
\begin{align}
\mathrm{tr}(A) &= \lambda_{1} + \lambda_{2} \\
\det{(A)} &= \lambda_{1} \lambda_{2}
\end{align}
以下、上記の導出を行います。まず、固有方程式の$\det{(\lambda I_{2} - A)}=0$は二次方程式の公式に基づいて下記のように解くことができます。
\begin{align}
\det{(\lambda I_{2} - A)} &= 0 \\
\left| \begin{array}{c} \lambda - a & -b \\ -c & \lambda - d \end{array} \right| &= 0 \\
(\lambda - a)(\lambda - d) - bc &= 0 \\
\lambda^{2} - (a+d) \lambda + (ad-bc) &= 0 \\
\lambda &= \frac{(a+d) \pm \sqrt{D}}{2} \quad (1) \\
D &= (a+d)^{2} - 4(ad-bc) \quad (2)
\end{align}
$\lambda_{1} \geq \lambda_{2}$を仮定する場合、上記の$(1)$式より、$\lambda_{1}+\lambda_{2}$は下記のように表すことができます。
\begin{align}
\lambda_{1} + \lambda_{2} &= \frac{(a+d) + \cancel{\sqrt{D}}}{2} + \frac{(a+d) - \cancel{\sqrt{D}}}{2} \\
&= \frac{2(a+d)}{2} \\
&= a + d = \mathrm{tr}(A)
\end{align}
上記より、$\mathrm{tr}(A) = \lambda_{1} + \lambda_{2}$を示すことができます。同様に$\lambda_{1} \geq \lambda_{2}$を仮定する場合、$(1), (2)$式より、$\lambda_{1} \lambda_{2}$は下記のように表すことができます。
\begin{align}
\lambda_{1} \lambda_{2} &= \frac{1}{2^{2}} \left[ (a+d) + \sqrt{D} \right] \left[ (a+d) - \sqrt{D} \right] \\
&= \frac{1}{4} \left[ (a+d)^{2} - D \right] \\
&= \frac{1}{4} \left( \cancel{(a+d)^{2}} - \left[ \cancel{(a+d)^{2}} - 4(ad-bc) \right] \right) \\
&= \frac{4(ad - bc)}{4} \\
&= ad - bc = \det{(A)}
\end{align}
上記より、$\det{(A)} = \lambda_{1} \lambda_{2}$を示すことができます。
二乗の和と二次形式
$\displaystyle \sum_{i=1}^{n} (a_{i1} x_{1} + a_{i2} x_{2})^{2}$は下記のように変形することができます。
\begin{align}
\sum_{i=1}^{n} (a_{i1} x_{1} + a_{i2} x_{2})^{2} &= \left( \begin{array}{ccc} a_{11} x_{1} + a_{12} x_{2} & \cdots & a_{n1} x_{1} + a_{n2} x_{2} \end{array} \right) \left( \begin{array}{c} a_{11} x_{1} + a_{12} x_{2} \\ \vdots \\ a_{n1} x_{1} + a_{n2} x_{2} \end{array} \right) \\
&= \left( \begin{array}{cc} x_{1} & x_{2} \end{array} \right) \left( \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ a_{21} & \cdots & a_{2n} \end{array} \right) \left( \begin{array}{ccc} a_{11} & a_{12} \\ \vdots & \vdots \\ a_{n1} & a_{n2} \end{array} \right) \left( \begin{array}{c} x_{1} \\ x_{2} \end{array} \right) \\
&= \left( \begin{array}{cc} x_{1} & x_{2} \end{array} \right) \left( \begin{array}{cc} \displaystyle \sum_{i=1}^{n} a_{i1}^{2} & \displaystyle \sum_{i=1}^{n} a_{i1}a_{i2} \\ \displaystyle \sum_{i=1}^{n} a_{i2}a_{i1} & \displaystyle \sum_{i=1}^{n} a_{i2}^{2} \end{array} \right) \left( \begin{array}{c} x_{1} \\ x_{2} \end{array} \right) \quad (3) \\
&= \mathbf{x}^{\mathrm{T}} A \mathbf{x} \\
\mathbf{x} &= \left( \begin{array}{c} x_{1} \\ x_{2} \end{array} \right), \, A = \sum_{i=1}^{n} \left( \begin{array}{cc} a_{i1}^{2} & a_{i1}a_{i2} \\ a_{i2}a_{i1} & a_{i2}^{2} \end{array} \right)
\end{align}
Harris Corner Detection
S(x,y) = \sum_{u} \sum_{v} w(u,v) \left[ I(u+x, v+y) - I(u, v) \right]^{2} \quad (4)
上記の$I(u+x, v+y)$はテイラー展開に基づいて下記のように近似できます。
I(u+x, v+y) \simeq I(u, v) + I_{x}(u,v)x + I_{y}(u,v)y \quad (5)
$(5)$式を$(4)$式に代入することで下記のような式変形を行うことができます。
\begin{align}
S(x,y) &= \sum_{u} \sum_{v} w(u,v) \left[ I(u+x, v+y) - I(u, v) \right]^{2} \quad (1) \\
& \simeq \sum_{u} \sum_{v} w(u,v) \left[ \cancel{I(u, v)} + I_{x}(u,v)x + I_{y}(u,v)y - \cancel{I(u, v)} \right]^{2} \\
&= \sum_{u} \sum_{v} w(u,v) \left[ I_{x}(u,v)x + I_{y}(u,v)y \right]^{2} \\
&= \sum_{u} \sum_{v} w(u,v) \left[ I_{x}(u,v)x + I_{y}(u,v)y \right] \cdot \left[ I_{x}(u,v)x + I_{y}(u,v)y \right] \\
&= \sum_{u} \sum_{v} w(u,v) \left( \begin{array}{cc} x & y \end{array} \right) \left( \begin{array}{c} I_{x}(u,v) \\ I_{y}(u,v) \end{array} \right) \left( \begin{array}{cc} I_{x}(u,v) & I_{y}(u,v) \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) \\
&= \sum_{u} \sum_{v} w(u,v) \left( \begin{array}{cc} x & y \end{array} \right) \left( \begin{array}{cc} I_{x}(u,v)^{2} & I_{x}(u,v) I_{y}(u,v) \\ I_{x}(u,v) I_{y}(u,v) & I_{y}(u,v)^{2} \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) \\
&= \left( \begin{array}{cc} x & y \end{array} \right) \left[ \sum_{u} \sum_{v} w(u,v) \left( \begin{array}{cc} I_{x}(u,v)^{2} & I_{x}(u,v) I_{y}(u,v) \\ I_{x}(u,v) I_{y}(u,v) & I_{y}(u,v)^{2} \end{array} \right) \right] \left( \begin{array}{c} x \\ y \end{array} \right) \\
&= \mathbf{x}^{\mathrm{T}} A \mathbf{x} \\
\mathbf{x} &= \left( \begin{array}{c} x \\ y \end{array} \right), \quad A = \sum_{u} \sum_{v} w(u,v) \left( \begin{array}{cc} I_{x}(u,v)^{2} & I_{x}(u,v) I_{y}(u,v) \\ I_{x}(u,v) I_{y}(u,v) & I_{y}(u,v)^{2} \end{array} \right)
\end{align}
上記における$A$はHarris行列であり、窓関数$w(u,v)$によってヘッセ行列が重み付けされた行列と解釈することができます。また、導出については前項の「二乗の和と二次形式」と対応させて確認しておくと良いと思います。
Harris行列の固有値とエッジ・コーナーの判定
このHarris行列の固有値を$\lambda_{1}, \lambda_{2}$($\lambda_{1} \leq \lambda_{2}$)とおくとき、固有値の値に基づいて下記のようにエッジ・コーナーの判定を行うことができます。
- $\lambda_{1} \simeq 0, \lambda_{2} \simeq 0$のとき、ピクセル$(x,y)$は特徴点を持たない
- $\lambda_{1} \simeq 0$かつ$\lambda_{2}$が正のある程度大きな値であるとき、エッジが存在する
- $\lambda_{1}$と$\lambda_{2}$のどちらも正の大きい値であるとき、コーナーが存在する
Harris Corner Detection
Harris行列$A$の固有値$\lambda_{1}, \lambda_{2}$の計算はやや計算コストがかかるので、Harris Corner Detectionでは「$2 \times 2$行列の固有値とTrace・Determinant」で導出した$\mathrm{tr}(A) = \lambda_{1} + \lambda_{2}, \det{(A)} = \lambda_{1} \lambda_{2}$を用いて特徴点の検出を行います。
M_c = \det{(A)} - k \mathrm{tr}(A)^{2} = \lambda_{1} \lambda_{2} - k(\lambda_{1}+\lambda_{2})^{2}
$k$は実験から定義されるパラメータであり、$0.04$～$0.15$の値が基本的に用いられます。以下、前項の1.～3.の状況で$M_c$がどのような値を取るか確認します。
・$\lambda_{1}=0.1, \lambda_{2}=0.1, k=0.1$の場合
\begin{align}
M_c &= 0.1^{2} - 0.1 \times (0.1 + 0.1) \\
&= 0.01 - 0.02 = -0.01
\end{align}
・$\lambda_{1}=0.1, \lambda_{2}=10, k=0.1$の場合
\begin{align}
M_c &= 0.1 \times 10 - 0.1 \times (0.1 + 10) \\
&= 1 - 1.01 = -0.01
\end{align}
・$\lambda_{1}=10, \lambda_{2}=10, k=0.1$の場合
\begin{align}
M_c &= 10 \times 10 - 0.1 \times (10 + 10) \\
&= 100 - 20 = 80
\end{align}
上記より、$\lambda_{1}$と$\lambda_{2}$のどちらも正の大きい値であるとき(コーナーが存在するとき)、$M_c$の値が大きくなることが確認できます。