4
$\begingroup$

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).$

paraboloid surface

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 12 '16 at 17:17
  • $\begingroup$ @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. $\endgroup$
    – wcochran
    Mar 9 '20 at 20:58
  • $\begingroup$ 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/… $\endgroup$ Mar 10 '20 at 3:32
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for chiming in. I was not sure anyone was paying attention. I think I ran with the least squared solution too. $\endgroup$
    – wcochran
    May 14 '18 at 4:02
  • $\begingroup$ See here: academia.edu/33443999/… $\endgroup$ Mar 9 '20 at 20:26
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.