A method for adjusting an image using message passing comprises associating each pixel of an image with a node of a graph and one or more cliques of nodes, determining for a node of the graph a respective set of possible pixel labels for which a unary potential is known, computing for that node a unary potential of a possible pixel label for which the unary potential is unknown, adjusting a clique potential associated with each clique to which that node belongs based on the unary potentials, and adjusting, based on the adjusted clique potential associated with each clique to which that node belongs, at least one of the messages between that node and the other nodes of each clique. Once a convergence criterion is met, an adjusted image is produced having pixel labels determined from the adjusted messages.