# SIFT - Taylor Expansion

I'm trying to implement SIFT algorithm. After I found the min/max points in DOG images I need to find the real min/max subpixels by taylor exapnsion:

$$$$D(\mathbf{x}) = D + \frac{\partial D^T}{\partial \mathbf{x}}\mathbf{x} + \frac{1}{2}\mathbf{x}^T\frac{\partial^2D}{\partial \mathbf{x}^2}\mathbf{x}$$$$

http://en.wikipedia.org/wiki/Scale-invariant_feature_transform

I'm not sure how I do it. I understand the idea behind using taylor expansion.

Consider one-dimensional function $f(x)$.

The first order taylor expansion is $f(x_0+h) \approx f(x_0) + f'(x_0)h$

The second order taylor exapnsion is $f(x_0+h) \approx f(x_0) + f'(x_0)h + \frac 1 2 f''(x_0)h^2$

Now we expand three-dimensional function. $$D(\mathbf{x_0}+\mathbf h) \approx D(\mathbf{X_0}) + \bigg(\frac{ \partial D}{\partial \mathbf x}\bigg)^T\bigg|_{\mathbf x=\mathbf x_0}\mathbf h + \frac 1 2 \mathbf h^TH(\mathbf x)\mathbf h$$ , where $$\frac {\partial D}{\partial \mathbf x} = \begin{bmatrix} \frac {\partial D}{\partial x} \\ \frac {\partial D}{\partial y} \\ \frac {\partial D}{\partial \sigma}\end{bmatrix} = \begin{bmatrix} \frac {D(x+1,y,\sigma) - D(x-1,y,\sigma)}{2} \\ \frac {D(x,y+1,\sigma)-D(x,y-1,\sigma}{2} \\ \frac {D(x,y,\sigma+1) - D(x,y,\sigma-1)}{2} \end{bmatrix}$$ $$H(\mathbf x) = \begin{bmatrix} D_{xx} & D_{xy} & D_{x\sigma} \\ D_{yx} & D_{yy} & D_{y\sigma} \\ D_{\sigma x} & D_{\sigma y} & D_{\sigma\sigma} \end{bmatrix}$$

Additionally, $D_{xy}$ $$= \frac { \frac{D(x+1,y+1,s)-D(x-1,y+1,s)}{2} - \frac{D(x+1,y-1,s)-D(x-1,y-1,s)}{2} } 2$$

Let's go back. $$D' = \bigg ( \frac{ \partial D}{ \partial \mathbf x} \bigg ) ^T + H(\mathbf x) \mathbf h = 0$$ $$\mathbf h = - H^{-1}(\mathbf x) \bigg ( \frac{ \partial D }{\partial \mathbf x} \bigg ) ^T$$

Assume that $\mathbf{x_0}$ is discrete feature point. Iteratively we can get $\mathbf h$.

If $\mathbf{x_0}$ is the closest point to $\mathbf h$, then we select $\mathbf{x_0}+\mathbf h$. (Imagine that 3-dimensional space)

My english ability is poor and there may be some errors.

• Actually, x is set of 3 points (x,y and sigma)? – EPBRD Aug 22 '13 at 11:01
• $\mathbf x$ is a 3-dimensional vector and x is a scalar. – jakeoung Aug 23 '13 at 2:39
• And how does Dxx described? Does it need for calculation of 3x3 Dx matrix and calculation of Dxx using same way as Dx itself (the second derivative by x)? – EPBRD Aug 24 '13 at 10:43