Optimization problem that obviously should have solution leads to gradient that can't be $0$?

46 Views Asked by At

Let's say I have an image which is a matrix of pixel values. The intensity at pixel position $(x,y)$ is given by $g(x,y)$. Somewhere in the image is hidden a circle or an arc of a circle (pixel values will be high at the circular arc and lower elsewhere). I want to estimate the coordinates of the center and the radius of the circle. Let's call these $(c_x,c_y,r)$. I know that if I plug a point into the equation of the circle, I should get $0$ if it lies on the circle, a negative value if it lies inside and positive if it lies outside. So, I define an objective function:

$$O(c_x,c_y,r)=\sum_{x=0}^n\sum_{y=0}^n((x-c_x)^2+(y-c_y)^2-r^2)^2g(x,y)$$

I know that this will be lowest when the circle overlaps with the circular arc in the image since the circle equation part will become zero and erase the large pixel values at the circular arc. So, I want to find $c_x, c_y, r$ that minimize $O(c_x,c_y,r)$. Taking gradient with respect to $r$ I get:

$$\sum_{x=0}^n\sum_{y=0}^n 2((x-c_x)^2+(y-c_y)^2-r^2)g(x,y)(-2r)$$

At the optimal value, this term should become $0$. However, it is easy to construct images $g(x,y)$ that have a prominent circular arc but where the gradient equation above can't be zero unless $r=0$. This doesn't make sense. I know there is a $(c_x,c_y,r)$ where the objective function above is minimized (because I put a circle in the image). However, it is also the case that the derivative of the objective function with respect to $r$ at that point is not zero (because I made some arbitrary pixel outside the circle high as well for example). What gives?

1

There are 1 best solutions below

7
On

That loss function is a degree-$4$ polynomial, so it gets blown up by outliers. It's not obvious at all that it is minimized where it "should" be.