サブピクセルレベルのローカライズ

出典: Wikimura

SURFではHessian画像の極大値を(x,y,s)空間(sは画像のスケール)で探す。スケールを高くする際、サンプリング間隔を大きく取るため、極大点の精度が悪くなってしまう。そこで「Distinctive Image Features from Scale-Invariant Keypoints」で紹介されている方法が使われる。

これは、スカラー関数であるHessian画像を、極大点 $\mathbf{x}_0$ の周りで2次近似し、その極大値を求めるというアプローチとなっている。(二次微分のところの書き方は本当はNGらしい)

原理

三次元空間で定義されるスカラー関数を、極大点付近で二次近似する。

$\begin{align} \mathbf{x} &= \begin{bmatrix} x \\ y \\ s \end{bmatrix}\\ F(\mathbf{x}) &\approx F(\mathbf{x}_0) + \frac{ \partial F(\mathbf{x}_0)}{ \partial \mathbf{x}} ( \mathbf{x} - \mathbf{x}_0)+ \frac{1}{2}( \mathbf{x} - \mathbf{x}_0)^\mathrm{T} \frac{ \partial ^2 F(\mathbf{x}_0)}{ \partial \mathbf{x}^2} ( \mathbf{x} - \mathbf{x}_0) \end{align}$

近似したら、これが極大値を取る場所を探す。極大点では勾配が0となるので、次式を解けば良いことになる。

$\frac{ \partial F(\mathbf{x}_0)}{ \partial \mathbf{x}} + \frac{ \partial ^2 F(\mathbf{x}_0)}{ \partial \mathbf{x}^2} ( \mathbf{x} - \mathbf{x}_0) = \mathbf{0}$

結果は以下のようになる。

$\mathbf{x} = \mathbf{x}_0 - \left( \frac{ \partial ^2 F(\mathbf{x}_0)}{ \partial \mathbf{x}^2} \right)^{-1} \frac{ \partial F(\mathbf{x}_0)}{ \partial \mathbf{x}}$

差分近似

勾配ベクトルは、中央差分を使って以下のように表せる。

$\frac{ \partial F(\mathbf{x}_0)}{ \partial \mathbf{x}} \approx \mathbf{g} \equiv \begin{bmatrix} \frac{F_{(+00)} - F_{(-00)}}{2 \Delta x} \\ \\ \frac{F_{(0+0)} - F_{(0-0)}}{2 \Delta y} \\ \\ \frac{F_{(00+)} - F_{(00-)}}{2 \Delta z} \end{bmatrix}$

Hessianは以下のように表せる。

$\frac{ \partial ^2 F(\mathbf{x}_0)}{ \partial \mathbf{x}^2} \approx \mathbf{H} \equiv \begin{bmatrix} \frac{F_{(+00)} - 2F_{(000)} + F_{(-00)}}{\Delta x^2} & \frac{F_{(++0)} - F_{(+-0)} - F_{(-+0)} + F_{(--0)}}{ 4 \Delta x \Delta y} & \frac{F_{(+0+)} - F_{(+0-)} - F_{(-0+)} + F_{(-0-)}}{ 4 \Delta x \Delta z} \\ &&\\ \frac{F_{(++0)} - F_{(+-0)} - F_{(-+0)} + F_{(--0)}}{ 4 \Delta x \Delta y} & \frac{F_{(0+0)} - 2F_{(000)} + F_{(0-0)}}{\Delta y^2} & \frac{F_{(0++)} - F_{(0+-)} - F_{(0-+)} + F_{(0--)}}{ 4 \Delta y \Delta z} \\ &&\\ \frac{F_{(+0+)} - F_{(+0-)} - F_{(-0+)} + F_{(-0-)}}{ 4 \Delta x \Delta z} & \frac{F_{(0++)} - F_{(0+-)} - F_{(0-+)} + F_{(0--)}}{ 4 \Delta y \Delta z} & \frac{F_{(00+)} - 2F_{(000)} + F_{(00-)}}{\Delta z^2} & \end{bmatrix}$

計算を楽にする

実際に計算する際は、勾配とHessianを求めることから始める。この段階で、 $Δ x,Δ y,Δ z$ の除算が必要になる。しかし、これらは打ち消しあうため、もう少し計算量を減らせる。(あまり全体に効果はないかもしれない...)

ここで、以下の行列を定義する。

$\mathbf{S} = \begin{bmatrix} \frac{1}{\Delta x} & 0 & 0 \\ 0 & \frac{1}{\Delta y} & 0 \\ 0 & 0 & \frac{1}{\Delta z} \end{bmatrix}$

これを使うと、勾配は以下のように表せる。

$\begin{align} \mathbf{g} &= \frac{1}{2} \mathbf{S} \begin{bmatrix} F_{(+00)} - F_{(-00)} \\ \\ F_{(0+0)} - F_{(0-0)} \\ \\ F_{(00+)} - F_{(00-)} \end{bmatrix}\\ &= \frac{1}{2} \mathbf{S} \hat{\mathbf{g}} \end{align}$

Hessianは以下のようにあらわせる。

$\begin{align} \mathbf{H} &= \mathbf{S} \begin{bmatrix} F_{(+00)} - 2F_{(000)} + F_{(-00)} & \frac{F_{(++0)} - F_{(+-0)} - F_{(-+0)} + F_{(--0)}}{4} & \frac{F_{(+0+)} - F_{(+0-)} - F_{(-0+)} + F_{(-0-)}}{4} \\ &&\\ \frac{F_{(++0)} - F_{(+-0)} - F_{(-+0)} + F_{(--0)}}{4} & F_{(0+0)} - 2F_{(000)} + F_{(0-0)} & \frac{F_{(0++)} - F_{(0+-)} - F_{(0-+)} + F_{(0--)}}{4} \\ &&\\ \frac{F_{(+0+)} - F_{(+0-)} - F_{(-0+)} + F_{(-0-)}}{4} & \frac{F_{(0++)} - F_{(0+-)} - F_{(0-+)} + F_{(0--)}}{4} & F_{(00+)} - 2F_{(000)} + F_{(00-)} & \end{bmatrix} \mathbf{S}\\ &= \mathbf{S} \hat{\mathbf{H}} \mathbf{S} \end{align}$

これらを使えば、以下の形になる。

$\begin{align} \mathbf{x} &= \mathbf{x}_0 - \mathbf{H}^{-1} \mathbf{g}\\ &= \mathbf{x}_0 - \left( \mathbf{\mathbf{S} \hat{\mathbf{H}} \mathbf{S}}\right)^{-1} \frac{1}{2} \mathbf{S} \hat{\mathbf{g}} \\ &= \mathbf{x}_0 - \frac{1}{2}\mathbf{S}^{-1} \hat{\mathbf{H}}^{-1}\hat{\mathbf{g}} \end{align}$

ここで、Sの逆行列は次式で表される。これは予め計算しておける。また、GSLならベクトルの成分ごとの積を使えば良いので、実際には計算量は3回の乗算にしかならない。

$\mathbf{S}^{-1} = \begin{bmatrix} \Delta x & 0 & 0 \\ 0 & \Delta y & 0 \\ 0 & 0 & \Delta z \end{bmatrix}$

x'Axの微分

二次形式を微分する場合、以下が成り立つらしい。(Aは定数行列)

$\frac{\partial}{ \partial \mathbf{x}} \left( \mathbf{x}^\mathrm{T} \mathbf{A} \mathbf{x} \right) = (\mathbf{A}+\mathbf{A}\mathrm{T})\mathbf{x}$

行列を使っていても、積の微分のルールはそのまま使えるのだが...普通の微分の感覚だと以下のようになってしまう?第一項は行ベクトル、第二項は列ベクトルになるので、もちろんこれはだめ。

$\frac{ \partial \mathbf{x}^\mathrm{T}}{ \partial \mathbf{x}} \mathbf{A} \mathbf{x} + \mathbf{x}^\mathrm{T} \mathbf{A} \frac{ \partial \mathbf{x}}{ \partial \mathbf{x}} = \mathbf{A} \mathbf{x} + \mathbf{x}^\mathrm{T} \mathbf{A}$

ベクトルのまま考えるためには、少し変形がいるらしいが...良く分からない。アインシュタインの縮約ではないが、∑が面倒なので省略して考えてみる。

$\mathbf{x}^\mathrm{T} \mathbf{A} \mathbf{x} \Leftrightarrow x_i a_{ij} x_j$

これなら、微分は...

$\begin{align} \frac{ \partial}{ \partial x_k} \left( x_i a_{ij} x_j \right) &= \frac{ \partial x_i}{ \partial x_k} a_{ij} x_j + x_i \frac{ \partial a_{ij}}{ \partial x_k} x_j + x_i a_{ij} \frac{ \partial x_j}{ \partial x_k} \\ &= a_{ij} x_i + a_{ij} x_j \quad \Leftrightarrow \quad \mathbf{A}^\mathrm{T} \mathbf{x} + \mathbf{A} \mathbf{x} \end{align}$

これで良いのだろうか?

$\frac{ \partial x_i}{ \partial x_k} \Leftrightarrow \begin{bmatrix} \frac{ \partial x_1}{ \partial x_1} & \frac{ \partial x_1}{ \partial x_2} & \frac{ \partial x_1}{ \partial x_3} \\ &&\\ \frac{ \partial x_2}{ \partial x_1} & \frac{ \partial x_2}{ \partial x_2} & \frac{ \partial x_2}{ \partial x_3} \\ &&\\ \frac{ \partial x_3}{ \partial x_1} & \frac{ \partial x_3}{ \partial x_2} & \frac{ \partial x_3}{ \partial x_3} \end{bmatrix} = \mathbf{I}$

サブピクセルレベルのローカライズ

出典: Wikimura

目次

原理

差分近似

計算を楽にする

x'Axの微分

表示

個人用ツール

案内

検索

ツールボックス