Pseudo-Bound Optimization for Binary Energies

author: Meng Tang, Department of Computer Science, University of Western Ontario
published: Oct. 29, 2014,   recorded: September 2014,   views: 2528


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


High-order and non-submodular pairwise energies are important for image segmentation, surface matching, deconvolution, tracking and other computer vision problems. Minimization of such energies is generally NP-hard. One standard approximation approach is to optimize an auxiliary function - an upper bound of the original energy across the entire solution space. This bound must be amenable to fast global solvers. Ideally, it should also closely approximate the original functional, but it is very difficult to find such upper bounds in practice. Our main idea is to relax the upper-bound condition for an auxiliary function and to replace it with a family of pseudo-bounds, which can better approximate the original energy. We use fast polynomial parametric maxflow approach to explore all global minima for our family of submodular pseudo-bounds. The best solution is guaranteed to decrease the original energy because the family includes at least one auxiliary function. Our Pseudo-Bound Cuts algorithm improves the state-of-the-art in many applications: appearance entropy minimization, target distribution matching, curvature regularization, image deconvolution and interactive segmentation.

See Also:

Download slides icon Download slides: eccv2014_tang_binary_energies_01.pdf (1.5┬áMB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: