Algorithms based on graph cuts have had a major impact on an important class of vision problems. In these problems, which arise in applications such as stereo, every pixel must be assigned a label from some predefined set. There is a known cost to assign a given label to any pixel, as well as a known cost for assigning different labels to adjacent pixels. I will describe some recent work that addresses a broader class of problems, where the labels are not specified in advance, and where the cost of assigning a given label to any pixel must be determined. This broader class of problems arises from applications such as multi-modal imaging, stereo imaging with unknown camera gain/bias, texture segmentation and layered motion segmentation. I will present some preliminary results that suggest that these problems can be solved by combining graph cuts with ideas from Expectation-Maximization and mutual information.