System and method for image segmentation by optimizing weighted curvature

1. A method of segmenting an object in a digital image, comprising the steps of:

acquiring an N-dimensional digital image, said image comprising a plurality of data items associated with an N-dimensional domain of points, wherein said digital image is represented as a graph wherein each point of said image is associated with a vertex of said graph and said graph includes an edge connecting each pair of vertices corresponding to adjacent points in said image;

computing, for each vertex v i in said graph, weights w ijk of a curvature clique v j v i v k for each successive pair of edges e ij , e ik incident on said vertex v i , taken clockwise, wherein v i and v j are connected by edge e ij , and v i and v k are connected by edge e ik ;

decomposing each curvature clique into pairwise edge weights to form a new set of edges by adding, for all vertices v j , v k such that v i and v j are connected by edge e ij , and v i and v k are connected by edge e ik , an edge e ij with weight w ij , an edge w ik with weight w ik , and an edge e jk with weight w jk , wherein weight w ij for edge e ij equals weight w ik for edge e ik equals ½ w ijk , and weight w jk for edge e jk connecting vertices v j and v k equals −½ w ijk ;

computing an indicator function x of the points of the image indicative of whether each point belongs to an object of interest by minimizing a functional

E

curvature

⁡

(

x

)

=

∑

e

mn

∈

E

*

⁢

w

mn

⁢



x

m

-

x

n



of said indicator function, wherein e mn is an edge in the new set of edges E*; and

segmenting said object of interest from said image based on the value of the indicator function x at each image point, wherein a point v i belongs to the object of interest if x i =1, and belongs to a background if x i =0.

2. The method of claim 1 , wherein

w

ijk

=

α

p

min

⁡

(



e

→

ij



,



e

→

ik



)

p

-

1

is a weight of a curvature clique v j v i v k for vertices, α is an angle at vertex v i formed by edges e ij and e ik , and p>1.

3. The method of claim 1 , wherein the weight of a curvature clique for vertices v i , v j , v k is multiplied by a factor w ij ′w ik ′ wherein each w′ ij , w′ ik is a function that decreases with increasing image contrast.

4. The method of claim 3 , wherein

w ij ′=exp(−β( I ( i )− I ( j )) 2 ),

w ij ′=exp(−β( I ( i )− I ( k )) 2 ),

I is the image intensity associated with each pixel, and parameter β≧0 controls an affinity strength.

5. The method of claim 1 , wherein said functional of said indicator function further includes a boundary length energy term represented by

E

length

⁡

(

x

)

=

∑

e

inm

∈

E

⁢

w

mn

⁢



x

m

-

x

n



,

wherein w mn is a boundary length weight.

6. The method of claim 5 , further comprising adding to said graph, for each vertex v i in said graph and each vertex v j in a neighborhood of v i , an edge e ij with associated boundary length weight w ij .

7. The method of claim 1 , wherein said functional of said indicator function further includes an intensity model energy term represented by

E

data

⁡

(

x

)

=

∑

v

i

∈

V

⁢

x

i

⁡

(

I

i

-

μ

F

)

2

+

∑

v

i

∈

V

⁢

(

1

-

x

i

)

⁢

(

I

i

-

μ

B

)

2

,

wherein v i is a vertex, V is the set of vertices in the graph representing the image, I i is an image intensity associated with vertex v i , and μ F and μ B respectively represent mean intensity values inside and outside the object of interest represented by x.

8. The method of claim 7 , wherein said graph includes two auxiliary vertices S and T, and further comprising adding to said graph, for each vertex v i corresponding to an image point, edges w iS and e iT with respective weights w iS and w iT whose values are based on an appearance model of an object appearance and a background appearance.

9. The method of claim 8 , wherein edge e iS has weight w iS =(I i −μ F ) 2 and edge e iT has weight w iT =(I i −μ B ) 2 .

10. The method of claim 1 , further comprising acquiring foreground and background seeds to constrain the segmentation, wherein a foreground seed v i is set to x i =1 while a background seed is set to x i =0.

11. The method of claim 1 , wherein minimizing the functional of said indicator function x comprises applying a Quadratic Psuedo Binary Optimization with Probing to said graph to find a minimum cut that partitions the graph into two components S 1 corresponding to the object of interest and S 2 = S 1 .

12. A method of segmenting an object in a digital image, comprising the steps of:

acquiring an N-dimensional digital image, said image comprising a plurality of data items associated with an N-dimensional domain of points, wherein said digital image is represented as a graph wherein each point of said image is associated with a vertex of said graph and said graph includes an edge connecting each pair of vertices corresponding to adjacent points in said image;

computing, for each vertex v i in said graph wherein adjacent vertices v i , v j , v k form an angle α=∠v j v i v k , weights for each successive pair of edges e ij , e ik incident on said vertex v i , taken clockwise, wherein v i and v j are connected by edge e ij , and v i and v k are connected by edge e ik , and adding, for all vertices v j , v k such that v i and v j are connected by edge e ij , and v i and v k are connected by edge e ik , an edge e ij with weight w ij , an edge e ik with weight w ik , and an edge e jk with weight w jk , to form a new set of edges, wherein weight w ij for edge e ij equals weight w ik for edge e ik equals weight −w jk for edge e jk connecting vertices v j and v k ;

adding two auxiliary vertices S and T to the graph and adding to said graph, for each vertex v i corresponding to an image point, edges e iS and e iT with respective weights w iS and w iT whose values are based on an appearance model of an object appearance and a background appearance; and

applying a Quadratic Psuedo Binary Optimization with Probing to said graph with said new set of edges to find a minimum cut that partitions the graph into two components S 1 and S 2 = S 1 , wherein S 1 corresponds to the object of interest, SεS 1 , TεS 2 , wherein a point v i εS 1 if x i =1 and v i εS 2 if x i =0.

13. The method of claim 12 , wherein applying a Quadratic Psuedo Binary Optimization with Probing to said graph comprises computing an indicator function x of the points of the image indicative of whether each point belongs to an object of interest that minimizes a functional

E

curvature

⁡

(

x

)

=

∑

e

ij

∈

E

*

⁢

w

ij

⁢



x

i

-

x

j



of said indicator function, wherein e ij is an edge in the new set of edges E*, w ij =½ w ijk ,

w

ijk

=

α

p

min

⁡

(



e

→

ij



,



e

→

ik



)

p

-

1

⁢

exp

⁡

(

-

β

⁡

(

I

⁡

(

i

)

-

I

⁡

(

j

)

)

2

)

⁢

exp

⁡

(

-

β

⁡

(

I

⁡

(

i

)

-

I

⁡

(

k

)

)

2

)

is a weight of a curvature clique v j v i v k for vertices, α is an angle at vertex v i formed by edges e ij and e ik , p>1, I is an image intensity associated with each pixel, and parameter β≧0.

14. A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for segmenting an object in a digital image, the method comprising the steps of:

acquiring an N-dimensional digital image, said image comprising a plurality of data items associated with an N-dimensional domain of points, wherein said digital image is represented as a graph wherein each point of said image is associated with a vertex of said graph and said graph includes an edge connecting each pair of vertices corresponding to adjacent points in said image;

computing, for each vertex v i in said graph, weights w ijk of a curvature clique v j v i v k for each successive pair of edges e ij , e ik incident on said vertex v i , taken clockwise, wherein v i and v j are connected by edge e ij , and v i and v k are connected by edge e ik ;

decomposing each curvature clique into pairwise edge weights to form a new set of edges by adding, for all vertices v j , v k such that v i and v j are connected by edge e ij , and v i and v k are connected by edge e ik , an edge e ij with weight w ij , an edge e ik with weight w ik , and an edge e jk with weight w jk , wherein weight w ij for edge e ij equals weight w ik for edge e ik equals ½ w ijk , and weight w jk for edge e jk connecting vertices v j and v k equals −½ w ijk ;

computing an indicator function x of the points of the image indicative of whether each point belongs to an object of interest by minimizing a functional

E

curvature

⁡

(

x

)

=

∑

e

mn

∈

E

*

⁢

w

mn

⁢



x

m

-

x

n



of said indicator function, wherein e mn is an edge in the new set of edges E*; and

segmenting said object of interest from said image based on the value of the indicator function x at each image point, wherein a point v i belongs to the object of interest if x i =1, and belongs to a background if x i =0.

15. The computer readable program storage device of claim 14 , wherein

w

ijk

=

α

p

min

⁡

(



e

→

ij



,



e

→

ik



)

p

-

1

is a weight of a curvature clique v i v i v k for vertices, α is an angle at vertex v i formed by edges e ij and e ik , and p>1.

16. The computer readable program storage device of claim 14 , wherein the weight of a curvature clique for vertices v i , v j , v k is multiplied by a factor w ij ′w ik ′ wherein each w′ ij , w′ ik is a function that decreases with increasing image contrast.

17. The computer readable program storage device of claim 16 , wherein

w ij ′=exp(−β( I ( i )− I ( j )) 2 ),

w ik ′=exp(−β( I ( i )− I ( k )) 2 ),

I is the image intensity associated with each pixel, and parameter β≧0 controls an affinity strength.

18. The computer readable program storage device of claim 14 , wherein said functional of said indicator function further includes a boundary length energy term represented by

E

length

⁡

(

x

)

=

∑

e

inm

∈

E

⁢

w

mn

⁢



x

m

-

x

n



,

wherein w mn is a boundary length weight.

19. The computer readable program storage device of claim 18 , the method further comprising adding to said graph, for each vertex v i in said graph and each vertex v j in a neighborhood of v i , an edge e ij with associated boundary length weight w ij .

20. The computer readable program storage device of claim 14 , wherein said functional of said indicator function further includes an intensity model energy term represented by

E

data

⁡

(

x

)

=

∑

v

i

∈

V

⁢

x

i

⁡

(

I

i

-

μ

F

)

2

+

∑

v

i

∈

V

⁢

(

1

-

x

i

)

⁢

(

I

i

-

μ

B

)

2

,

wherein v i is a vertex, V is the set of vertices in the graph representing the image, I i is an image intensity associated with vertex v i , and μ F and μ B respectively represent mean intensity values inside and outside the object of interest represented by x.

21. The computer readable program storage device of claim 20 , wherein said graph includes two auxiliary vertices S and T, and further comprising adding to said graph, for each vertex v i corresponding to an image point, edges e iS and e iT with respective weights w iS and w iT whose values are based on an appearance model of an object appearance and a background appearance.

22. The computer readable program storage device of claim 21 , wherein edge e iS has weight w iS =(I i −μ F ) 2 and edge e iT has weight w iT =(I i −μ B ) 2 .

23. The computer readable program storage device of claim 14 , the method further comprising acquiring foreground and background seeds to constrain the segmentation, wherein a foreground seed v i is set to x i =1 while a background seed is set to x i =0.

24. The computer readable program storage device of claim 14 , wherein minimizing the functional of said indicator function x comprises applying a Quadratic Psuedo Binary Optimization with Probing to said graph to find a minimum cut that partitions the graph into two components S 1 corresponding to the object of interest and S 2 = S 1 .