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

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 $$f(x,y) = ax^2 + by^2 + cxy + dx + ey + g$$ 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 $$f(x,y) = ax^2y^2 + bx^2y + cxy^2 + dx^2 + ey^2 + gxy + hx + iy + j$$ 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?

• Odd that they say "parabola" instead of "paraboloid". My first inclination would be use fit the six-parameter paraboloid and see how it works. It is certainly simpler. Nov 12, 2016 at 17:17
• @LukeHutchison Why is $g$ independent? It "moves" the paraboloid "up and down." All six coefficients (first equation) are free. If I threw out the corner points and set c = 0, then you only need 5 points for an axis-aligned paraboloid. But I want to allow something more general than that. Mar 9, 2020 at 20:58
• I was wrong, I misinterpreted the paper I linked to. You need to fit 6 points to uniquely define a 2d paraboloid in 3d space, since you have 6 constants to find ($a$, $b$, $c$, $d$, $e$ and $g$). academia.edu/33443999/… Mar 10, 2020 at 3:32

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.

• Thanks for chiming in. I was not sure anyone was paying attention. I think I ran with the least squared solution too. May 14, 2018 at 4:02
• See here: academia.edu/33443999/… Mar 9, 2020 at 20:26
• Thanks for this! For others interested, here is the solution to the two equations for the maximum: y = (((2.0 * a * e) / c) - d) / (c - 4 * a * b / c) x = -(2 * b * y + e) / c Jan 20, 2022 at 7:32
• If someone can, please fix the notation on f'y(x, y) to f'_y(x, y). If a moderator has any control, this rule that edits must be 6 chars is dumb. No, there's nothing else to improve. It's just a one-char notation fix. I don't know why that shouldn't be allowed. Oct 11 at 3:21
• @jspencer Thanks, fixed it :) Nov 2 at 12:59

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.