ぷろぐ((>ω<))

ぷろぐらみんぐ関係のメモ

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

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

特徴検出 — opencv 2.2 documentation


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

  1. \displaystyle{\epsilon_{i}=DI^{T}_{p_{i}}\cdot(q-p_{i})}
  2. \displaystyle{\sum_{i} (DI_{p_{i}}\cdot DI^{T}_{p_{i}})-\sum_{i} (DI_{p_{i}}\cdot DI^{T}_{p_{i}}\cdot p_{i})}
  3. \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} 
}