MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I want to find a region $R$ that best matches $R^*$, by defining a convex polygon $h$ in the histogram. $R$ will be the pixels in the image space that are chosen by $h$. my question is:

1) How to optimize the vertices of the polygon such that $R$ best matches $R^*$?

2) If I also want to know the number of vertices, is there any method for that (supposed to be a tradeoff between computation time and the precision, since infinite number of vertices would give a arbitrary convex shape).

As an initial effort, I think the set of points in R is only function of the vertices of $h$, instead of all the interior points of $h$. If I move each vertex one by one, I probably only get local optimal solution. This is probably not a problem that can be solved in polynomial time? I'm not sure if it's related to any 'convex problem'. The functional form $R = f(h)$ seems different from the convex function I know.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.