System and method for image segmentation by optimizing weighted curvature

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 vi in said graph wherein adjacent vertices vi, vj, vk form an angle α=∠vjvivk, weights for each successive pair of edges eij, eik incident on said vertex vi, taken clockwise, wherein vi and vj are connected by edge eij, and vi and vk are connected by edge eik, and adding, for all vertices vj, vk such that vi and vj are connected by edge eij, and vi and vk are connected by edge eik, an edge eij with weight wij, an edge eik with weight wik, and an edge ejk with weight wjk, to form a new set of edges, wherein weight wij for edge eij equals weight wik for edge eik equals weight −wjk for edge ejk connecting vertices vj and vk;
• adding two auxiliary vertices S and T to the graph and adding to said graph, for each vertex vi corresponding to an image point, edges eiS and eiT with respective weights wiS and wiT 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 S1 and S2= S1, wherein S1 corresponds to the object of interest, SεS1, TεS2, wherein a point viεS1 if xi=1 and viεS2 if xi=0.

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 vi in said graph, weights wijk of a curvature clique vjvivk for each successive pair of edges eij, eik incident on said vertex vi, taken clockwise, wherein vi and vj are connected by edge eij, and vi and vk are connected by edge eik;
• decomposing each curvature clique into pairwise edge weights to form a new set of edges by adding, for all vertices vj, vk such that vi and vj are connected by edge eij, and vi and vk are connected by edge eik, an edge eij with weight wij, an edge eik with weight wik, and an edge ejk with weight wjk, wherein weight wij for edge eij equals weight wik for edge eik equals ½ wijk, and weight wjk for edge ejk connecting vertices vj and vk equals −½ wijk;
• 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 emn 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 vi belongs to the object of interest if xi=1, and belongs to a background if xi=0.