Computer vision

A pseudo-boolean function is a function from the space B^n of boolean (0-1) vector to the real numbers. They occur naturally in problems in computer vision related to segmentation where every pixel in an image should be labelled 0 or 1 to minimize a certain cost function. Although the minimization of such functions in in general NP hard, many techniques have been develloped to minimize certain classes of such functions. This is the topic of pseudo-boolean optimization, which will be the subject of this talk. Useful methods include graph-cuts algorithms, message passing and linear programming relaxation. The extension to functions with a finite label set will also be considered.