How do I fit a paraboloid surface to nine points and find the minimum?

Question

Given 9 values for $f(x,y)$ where $(x,y) \in \{-1,0,+1\}^2$ I wish to fit a paraboloid surface $z = f(x,y)$ to these 9 values. Once I have $f$ I want to locate its minimum value. The center value $f(0,0)$ is known to be the smallest of the 9 input values so there exists a minimum value of $f$ on the domain $[-1,+1]^2.$ I wish find $(x^*,y^*) = \mathrm{argmin}\ f(x,y).$

I could find 6 the coefficients for \begin{equation} f(x,y) = ax^2 + by^2 + cxy + dx + ey + g \end{equation} using a least squared error fit. To find the minimum I simply solve $f_x = 0$ and $f_y = 0$ which leads to a simple linear system which has a unique solution.

Conversely I could find the 9 coefficients for \begin{equation} f(x,y) = ax^2y^2 + bx^2y + cxy^2 + dx^2 + ey^2 + gxy + hx + iy + j \end{equation} and get an exact fit (9 linear equations and 9 unknowns). Finding the minimum of this function would require something akin to gradient descent.

The problem I am a trying to solve comes from this paper where it cryptically says "This produces values that are integers; to get a subpixel estimate, we fit a parabola to the 3×3 pixels centered at $(u_0,v_0)$ and extract its minimum".

The problem is I don't have a good feel for what the second surface is. Clearly if I hold either $x$ or $y$ constant then I end up with a 2D parabola. But this doesn't necessarily have a unique extrema point? Or does it?

Any insight on how I should be finding the minimum of a parabola fitted to 9 points?

Answer 1

I was hoping to find an answer to this same question, ended up working it out myself. I solved it using least squares to solve the equation for the paraboloid $f(x,y) = ax^2 + by^2 +cxy+dx+ey+g$ so having a set of points $\{x_1,y_1,z_1...x_9,y_9,z_9\}$, I set up my matrix $$\begin{matrix} & x_1^2 & y_1^2 & x_1y_1 & x_1 & y_1 & 1 \\ A=& x_2^2 & y_2^2 & x_2y_2 & x_2 & y_2 & 1 \\ & \vdots \\ & x_9^2 & y_9^2 & x_9y_9 & x_9 & y_9 & 1 \end{matrix}$$ and $$\begin{matrix} & z_1 \\ B=& z_2 \\ & \vdots \\ & z_9 \end{matrix}$$ So that I can solve $Ax=B$ using standard least squares methods. Of course this works for more than 9 points too.

Now this isn't exactly an answer to this question, since I don't know how to then find the minimum of this paraboloid within a given region, but for anyone else who comes across this question wanting to find the global extrema of the entire paraboloid: $$f'_x(x,y) = 2ax+cy+d\\ f'_y(x,y) = cx+2by+e $$ Set these two equations to zero and solve to find the extremum. Once you have it you can test if it is max, min, inflection or unkown by finding D: $$D = f_{xx}(a,b)f_{yy}(a,b)-f_{xy}^2(a,b)\\ D = 4ab-c^2$$ Then, if:

$D>0$ and $f_{xx}(a,b)>0$ then $f$ is min at $a,b$

$D>0$ and $f_{xx}(a,b)<0$ then $f$ is max at $a,b$

$D<0$ then $f$ is a saddle point at $a,b$

$D=0$ no conclusion

As I said, this doesn't actually answer the question, but since the title of this post doesn't make it clear that it is talking about the extrema within a range and not over the whole paraboloid, I imagine this might be helpful to some anyways.

Answer 2

If the paraboloid is assumed to be a rotated parabola around (or parallel with?) the z-axis presumably 4 points will do, just as if a sphere is assumed.