Interactive image segmentation on directed graphs
AssigneeSiemens Aktiengesellschaft
InventorsDheeraj Singaraju, Leo Grady
Life of this patent
Estimating the term…
Abstract
Methods for segmentation of an object from a background in an image are disclosed. Segmentation is achieved by an adapted Random Walker segmentation method using directed edges in a graph. The segmentation applies the minimization of an approximation of an energy function. A minimizer of the approximated energy function can be found by using iterative steps. Weights are assigned to an edge between two nodes. The weights are dependent on the direction of an edge. A system for segmentation of an object from a background is also disclosed.
Claims20
A method for segmentation of an object from a background in an image having a plurality of pixels, comprising:
- on a processor, defining an energy function on a combinatorial graph, the combinatorial graph having directed edges between nodes, the energy function depending on the value of a first and a second edge weight of a directed edge, the energy function being determined by an expression
- E
-
- (
- x
- )
- =
- ∑
- e
- ij
- ∈
- ɛ
-
- [
- w
- ij
-
- I
-
- (
- x
- i
- ≥
- x
- j
- )
- +
- w
- ji
-
- I
-
- (
- x
- i
- <
- x
- j
- )
- ]
-
- (
- x
- i
- -
- x
- j
- )
- 2
- ,
- wherein E(x) is an energy of a weighted graph formed by a function associated to nodes x, eij∈ε are edges in the weighted graph between nodes i and j, wij is a weight of an edge eij, I is an indicator function, and xi and xj are the values of node i and node j, respectively;
- creating a contour that segments the plurality of pixels into background and foreground pixels by determining a minimizer of the energy function by the processor;
- and
- generating by the processor to a display an image that contains a segmentation of the object.
A system for segmentation of an object from a background in an image having a plurality of pixels, comprising:
- a processor;
- a memory readable by the processor, the memory comprising program code executable by the processor, the program code adapted to perform the following steps:
- defining an energy function on a combinatorial graph, the combinatorial graph having directed edges between nodes, the energy function depending on the value of a first and a second edge weight of a directed edge, the energy function being determined by an expression
- E
-
- (
- x
- )
- =
- ∑
- e
- ij
- ∈
- ɛ
-
- [
- w
- ij
-
- I
-
- (
- x
- i
- ≥
- x
- j
- )
- +
- w
- ji
-
- I
-
- (
- x
- i
- <
- x
- j
- )
- ]
-
- (
- x
- i
- -
- x
- j
- )
- 2
- ,
- wherein E(x) is an energy of a weighted graph formed by a function associated to nodes x, eij∈ε are edges in the weighted graph between nodes i and j, wij is a weight of an edge eij, I is an indicator function and xi and xj are the values of node i and node j, respectively;
- and
- creating a contour that segments the plurality of pixels into background and foreground pixels by determining a minimizer of the energy function.
A method for segmentation of an object from a background in an image having a plurality of pixels wherein one or more pixels are marked as object, one or more pixels are marked as background and the remaining pixels are unmarked, comprising:
- instructing a processor to perform a Random Walker segmentation method which is a segmentation determined from a solution to a Dirichlet problem with boundary conditions given by foreground and background seeds to obtain a labeling of an unmarked pixel as a probability of whether a random walker starting from the unmarked pixel would first reach the object or the background adapted to a combinatorial graph having directed edges between nodes, a node of a graph representing a pixel of the image;
- segmenting the object from the background by the adapted Random Walker method;
- and
- generating by the processor to a display an image that contains a segmentation of the object.
Dependencies are inferred from the claim text.