cv::cornerSubPix (サブピクセル推定) アルゴリズムの詳細

OpenCVにはcv::cornerSubPixという関数があるが、これの原理に関する説明が非常に簡素でわかりづらい。

特徴検出 — opencv 2.2 documentation

上記ページに書いてある3つの式の意味についてまとめる。

$\displaystyle{\epsilon_{i}=DI^{T}_{p_{i}}\cdot(q-p_{i})}$
$\displaystyle{\sum_{i} (DI_{p_{i}}\cdot DI^{T}_{p_{i}})-\sum_{i} (DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i})}$
$\displaystyle{q=G^{-1}\cdot b}$

式1について

上記OpenCVの説明ページで「各点 $p$ に向かう画像勾配と直交する」にあたる部分。これについては下記記事がわかりやすかった。

Fundamentals of Features and Corners: Subpixel Corners: Increasing accuracy - AI Shack

式2について

式1から式2の間がちょっとぶっ飛びすぎているし、いろいろと間違っていると思う。

「 $\epsilon_{i}$ を0とすることで」（英語版では"A system of equations may be set up with $\epsilon_{i}$ set to zero"）は違うと思う
突然 $q$ が式2から消えてなくなっているが間違いだと思う

式1～式2の間には次の論理が省略されていると思う。一言で言えば「二乗誤差の最小化」である。

詳細

探索窓内のすべての点について式1で定義される $\epsilon_{i}$ の二乗の総和をEとする。

$\displaystyle{ E=\sum_{i} \epsilon_{i}^{2} }$

これに式1を代入すると、

$\displaystyle{ E=\sum_{i} \left(DI^{T}_{p_{i}}\cdot(q-p_{i})\right)^{2} }$

この総和 $E$ が最小値をとるような $q$ を求めればよい。それはつまり、 $q$ についての微分 $dE/dq$ がゼロになるときである。よって、

$\displaystyle{ \frac{dE}{dq}=2\sum_{i} \left(DI^{T}_{p_{i}}\cdot(q-p_{i})\right)DI^{T}_{p_{i}}=0 }$

$(a\cdot b)a=(aa^T)b$ と書き換えられるので、

$\displaystyle{ \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot(q-p_{i})=0 }$

これを展開すると

$\displaystyle{ \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot q - \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i}=0 }$ 　(★)

この左辺が式2である。繰り返しになるが、 $q$ が書かれてしかるべきだと思う。

式3について

突然1次勾配 $G$ 、2次勾配 $b$ という言葉が出てくるが、次の論理が省略されている。

詳細

上述の式(★)より

$\displaystyle{ \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot q = \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i} }$

$q$ は $\displaystyle{\sum_{i}}$ には依存しないので、

$\displaystyle{ \left(\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\right) \cdot q = \sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i} }$

ここで、

$\displaystyle{ G=\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}} }$

$\displaystyle{ b=\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i} }$

と置くと、上述の式は次のように書き換えらえる。

$\displaystyle{ G\cdot q=b }$

ゆえに、今求めたい $q$ は

$\displaystyle{ q=G^{-1}\cdot b }$

となり、式3となる。

おまけ

ところで、 $G=\sum_{i} DI_{p_{i}}\cdot DI^{T}_{p_{i}}$ は計算すると近似的に次のようになるが、これを structure tensor matrix と呼ぶ。

$DI_{p_{i}}=(I_{x_{p_{i}}}, I_{y_{p_{i}}})^{T}$ とすると、

$\displaystyle{ G=\sum_{i} \begin{pmatrix} I_{x_{p_{i}}}I_{x_{p_{i}}} & I_{x_{p_{i}}}I_{y_{p_{i}}} \\ I_{x_{p_{i}}}I_{y_{p_{i}}} & I_{y_{p_{i}}}I_{y_{p_{i}}} \\ \end{pmatrix} \approx \sum_{i} \begin{pmatrix} I_{xx_{p_{i}}} & I_{x_{p_{i}}}I_{y_{p_{i}}} \\ I_{x_{p_{i}}}I_{y_{p_{i}}} & I_{yy_{p_{i}}} \\ \end{pmatrix} }$