Globally optimal uninitialized graph-based rectilinear shape segmentation
AssigneeSiemens Medical Solutions USA, Inc.
InventorsAli Kemal Sinop, Leo Grady
Life of this patent
Estimating the term…
Abstract
An improved method of graph-based segmentation of objects in images uses the property of rectilinear shape classes which optimize the ratio of specific metrics, that can be expressed as Laplacian matrices applied to indicator vectors. A relaxation of the binary formulation of this problem allows a solution via generalized eigenvectors. This segmentation algorithm incorporating shape information requires no initialization, is non -iterative and finds a steady-state (i.e., global optimum) solution. The method is generally applicable to segmentation of rectilinear shapes.
Claims18
A method of segmenting a rectilinear object in an image forming a graph based on cuts of the object in the image, the method comprising:
- (a) obtaining the image;
- (b) calculating edge weights in accordance with
- w
- ij
- =
- {
- 1
- 2
- ,
- if
-
-
- nodes
-
-
- v
- i
-
-
- and
-
-
- v
- j
-
-
- are
-
-
- adjacent
-
-
- in
-
-
- the
-
-
- grid
- ,
- 0
- ,
- Otherwise
- }
- ,
- on a four-connected grid for L1 and, for L2, connect each node to every node within a radius of four pixels with edge weights equal to
- w
- i
- =
- δ
- 2
-
- Δ
-
-
- ϕ
- k
- 2
-
-
- e
- i
-
- ,
-
- for
-
-
- e
- i
- ∈
- E
- k
- ,
- where δ is grid spacing, Δφk is the angle between two edges in Ek, Ek ⊂ E indicates the edge family incident on node vk, i and j represent pixels in the image, and |ei| is the magnitude of this edge's direction;
- (c) approximating a ratio of perimeter metrics
- arg
-
-
- min
- x
-
- x
- T
-
- L
- 1
-
- x
- x
- T
-
- L
- 2
-
- x
- ,
- subject to [x ε{0,1}N], where N is the size of the graph, for the object by constructing Laplacian matrices L1 and L2 for the image;
- (d) relaxing an integer constraint on the ratio of perimeter metrics, resulting in a generalized eigenvector problem;
- (e) solving the generalized eigenvector problem;
- and
- (f) finding a binary segmentation from the eigenvector solution by thresholding the eigenvector to produce a binary indicator vector that minimizes said ratio of perimeter metrics, wherein said step of approximating the ratio of perimeter metrics includes modulating each edge weight of L2-graph.
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for segmenting a rectilinear object in an image forming a graph based on cuts of the object in the image, the method steps comprising:
- (a) obtaining the image;
- (b) calculating edge weights in accordance with
- w
- ij
- =
- {
- 1
- 2
- ,
- if
-
-
- nodes
-
-
- v
- i
-
-
- and
-
-
- v
- j
-
-
- are
-
-
- adjacent
-
-
- in
-
-
- the
-
-
- grid
- ,
- 0
- ,
- Otherwise
- }
- ,
- on a four-connected grid for L1 and, for L2, connect each node to every node within a radius of four pixels with edge weights equal to
- w
- i
- =
- δ
- 2
-
- Δϕ
- k
- 2
-
-
- e
- i
-
-
-
- for
-
-
- e
- i
- ∈
- E
- k
- ,
- where δ is grid spacing, Δφhd k is the angle between two edges in Ek, Ek ⊂ E indicates the edge family incident on node vk, i and j represent pixel in the image, and |ei| is the magnitude of this edge's direction;
- (c) approximating a ratio of perimeter metrics
- arg
-
-
- min
- x
-
- x
- T
-
- L
- 1
-
- x
- x
- T
-
- L
- 2
-
- x
- ,
- subject to [x ε{0,1}N], where N is the size of the graph, for the object by constructing Laplacian matrices L1 and L2 for the image;
- (d) relaxing an integer constraint on the ratio of perimeter metrics, resulting in a generalized eigenvector problem;
- (e) solving the generalized eigenvector problem;
- and
- (f) finding a binary segmentation from the eigenvector solution by thresholding the eigenvector to produce a binary indicator vector that minimizes said ratio of perimeter metrics, wherein said step of approximating the ratio of perimeter metrics includes modulating each edge weight of L2-graph.
A system for segmenting a rectilinear object in an image forming a graph based on cuts of the object in the image, the system comprising:
- means for reading a program of executable instructions tangibly embodied in a storage media;
- a means for storing the program of executable instructions, the executable instructions containing instructions for perform method steps for segmenting a rectilinear object in an image, the method steps comprising:
- (a) obtaining the image;
- (b) calculating edge weights in accordance with
- w
- ij
- =
- {
- 1
- 2
- ,
- if
-
-
- nodes
-
-
- v
- i
-
-
- and
-
-
- v
- j
-
-
- are
-
-
- adjacent
-
-
- in
-
-
- the
-
-
-
- grid
- 0
- ,
-
- Otherwise
- .
- }
- ,
- on a four-connected grid for L1 and, for L2, connect each node to every node within a radius of four pixels with edge weights equal to
- w
- i
- =
- δ
- 2
-
- Δϕ
- k
- 2
-
-
- e
- i
-
- ,
- for
-
-
- e
- i
- ∈
- E
- k
- ,
- where δ is grid spacing, Δφk is the angle between two edges in k, Ek ⊂ E indicates the edge family incident on node vk, i and j represent pixel in the image, and |ei| is the magnitude of this edge's direction;
- (c) approximating a ratio of perimeter metrics
- arg
-
-
- min
- x
-
-
- x
- T
-
- L
- 1
-
- x
- x
- T
-
- L
- 2
-
- x
- ,
- subject to [x ε{0,1}N], where N is the size of the graph, for the object by constructing Laplacian matrices L1 and L2 for the image;
- (d) relaxing an integer constraint on the ratio of perimeter metrics, resulting in a generalized eigenvector problem;
- (e) solving the generalized eigenvector problem;
- and
- (f) finding a binary segmentation from the eigenvector solution by thresholding the eigenvector to produce a binary indicator vector that minimizes said ratio of perimeter metrics, wherein said step of approximating the ratio of perimeter metrics includes modulating each edge weight of L2-graph;
- and
- a data processor for reading the program of executable instructions from the storage media and executing the executable instructions.
Dependencies are inferred from the claim text.