Patent ID: 8131069

Claim:
A method for determining an optimal labeling of pixels in computer vision, comprising the steps of: providing a digitized image comprising a plurality of intensities associated with an N-dimensional grid of points; modeling said image by a graph comprising a set of interior nodes N and a set of edges E wherein each image point p is associated with a graph node and each pair of nearest neighbor points p, q is connected by a graph edge, wherein each graph node p is associated with a singleton potential c(p), and each graph edge is associated with a pairwise potential function d(p, q); randomly assign a label from a set of labels L to each point p to initialize a set of unary variables x, said unary variables including an indicator function x p ( )that indicate which label is assigned to which point p, and initialize a set of dual variables y to zero, wherein said dual variables include a height variable h p (a) associated with each node p and label a, and balance variables y pq (a), y qp (a) associated with each edge (p, q) and label a, wherein h p ⁡ ( a ) ≡ c p ⁡ ( a ) + ∑ q ⁢ : ⁢ ⁢ qp ∈ E ⁢ y pq ⁡ ( a ) ; and for each label in L, selecting a new label c from said set L, constructing a capacitated graph G and solving a max-flow in said capacitated graph G to calculate an updated pair x′, y′, wherein said updated unary and dual variables satisfy the conditions h p ( x p )=min aεl ,h p ( a ), ∀ pεV, y pq ( x p )+ y qp ( x p )= w pq d ( x p ,x q ), ∀ pqεE, y pq ( a )+ y qp ( b )≦2 w pq d max , ∀ pqεE,aεL,bεL, wherein w pq is a weighting associated with each edge p,q, and wherein said label selection divides said image into disjoint regions.