Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem

Details Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem

2011-12-05

arxiv.org/abs/1112.0974v1

Computer Science

Computer Vision and Pattern Recognition

Scientific paper

We consider a variational convex relaxation of a class of optimal partitioning and multiclass labeling problems, which has recently proven quite successful and can be seen as a continuous analogue of Linear Programming (LP) relaxation methods for finite-dimensional problems. While for the latter case several optimality bounds are known, to our knowledge no such bounds exist in the continuous setting. We provide such a bound by analyzing a probabilistic rounding method, showing that it is possible to obtain an integral solution of the original partitioning problem from a solution of the relaxed problem with an a priori upper bound on the objective, ensuring the quality of the result from the viewpoint of optimization. The approach has a natural interpretation as an approximate, multiclass variant of the celebrated coarea formula.

Affiliated with

Also associated with

No associations

Rating

Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-395982