GPU accelerated isoperimetric algorithm for image segmentation, digital photo and video editing
View Patent ↗A system and method for segmenting an object in an image using an isoperimetric ratio in a graphics processing unit is disclosed. The object is identified by one or more selected pixels located within the object. The system includes a graphics processing unit and software loadable on the graphics processing unit. The software is operable to find weights for edges, to build a Laplacian matrix and a d vector, to eliminate the row and column corresponding to the one or more selected pixels to determine L 0 and d 0 , to solve x 0 in the equation L 0 x 0 =d 0 ; and to threshold the potentials x at the value that selects the object having the lowest isoperimetric ratio.
1. A system for segmenting an object in an image, the object being identified by one or more selected pixels located within the object, comprising:
a graphics processing unit; and
software loaded on the graphics processing unit, the software being operated to:
(a) create from the image a weighted graph with image pixels being graph nodes;
(b) determine weights for all edges in the graph of neighboring pixels for the image;
(c) build a Laplacian matrix L with the weights;
(d) determine a vector d having values associated with a pixel equal to a sum of the weights of the neighbors of that pixel;
(e) eliminate the row and column corresponding to the one or more selected pixels from the Laplacian matrix L and the vector d to determine L 0 and d 0 ;
(f) solve x in the equation L 0 x=d 0 ;
(g) threshold the potentials x to determine a family of segmentations and select one of the segmentations with a minimum isoperimetric ratio described by
h
G
=
min
x
(
x
T
Lx
)
/
x
T
d
as the object; and
(h) segment the object from the image.
2. The system as claimed in claim 1 . wherein the edge weights are a function of the difference between a value associated with a first pixel and a value associated with a second pixel.
3. The system as claimed in claim 2 , wherein the edge weights are equal to w ij =exp(−β∥C i −C j ∥ 2 where w ij represents the weight between nodes v i and V j , β is a free parameter, C i is the vector of color values at node v i and C j is the vector of color values at node v j .
4. The system as claimed in claim 1 , wherein a golden section search algorithm is used to find the object from a subset of the family of segmentations.
5. The system as claimed in claim 1 , wherein the one or more selected pixels are input into a Z buffer in the graphics processing unit such that the one or more selected pixels are excluded from processing.
6. A method of segmenting an object in an image, the object being identified by one or more selected pixels located within the object, comprising:
creating from the image a graph with image pixels being graph nodes;
determining weights for all edges in the graph of neighboring pixels for the image;
building a Laplacian matrix L with the weights;
determining a vector d having values associated with a pixel equal to a sum of the weights of the neighbors of that pixel;
eliminating the row and column corresponding to the one or more selected pixels from the Laplacian matrix L and the vector d to determine L 0 and d 0 ;
solving x in the equation L 0 x=d 0 ; and
thresholding the potentials x to determine a family of segmentations and select one of the segmentations having a minimum isoperimetric ratio described by
h
G
=
min
x
(
x
T
Lx
)
/
x
T
d
as the object; and
segmenting the object from the image;
wherein the steps are performed in a graphics processing unit.
7. The method as claimed in claim 6 , wherein the edge weights are a function of the difference between a value associated with a first pixel and a value associated with a second pixel.
8. The method as claimed in claim 7 , wherein the edge weights are equal to w ij =exp(−β∥C i −C j μ 2 where w ij represents the weight between nodes v i and v j , β is a free parameter, C i is the vector of color values at node v i and C j is the vector of color values at node v j .
9. The method as claimed in claim 6 , wherein a golden section search algorithm is used to find the object from a subset of the family of segmentations.
10. The method as claimed in claim 6 , wherein the one or more selected pixels are input into a Z buffer in the graphics processing unit such that the one or more selected pixels are excluded from processing.
11. A system for segmenting an object in an image, the object being identified by one or more selected pixels located within the object, comprising:
a graphics processing unit; and
software loaded on the graphics processing unit, the software being operated to:
(a) identify a plurality of possible objects, wherein each possible object includes the one or more selected pixels;
(b) create a weighted graph having the one or more selected pixels as nodes, for each of the plurality of possible objects that include the one or more selected pixels;
determine an isoperimetric ratio described by (x T Lx)/x T d of the weighted graph associated with a possible object; wherein L is a Laplacian matrix defined with edge weights, d is vector with each element corresponding to a pixel and having value equal to a sum of the edge weights of the neighbors of that pixel, and x is a given indication vector that takes a binary value at each node; and
(d) select the object from the plurality of possible objects in accordance with the isoperimetric ratio.
12. The system as claimed in claim 11 , wherein an edge weight of the weighted graph is a function of a value associated with a first pixel and a value associated with a second pixel.
13. The system as claimed in claim 12 , wherein the edge weights are equal to w ij =exp(−β(I i −I j ) 2 ) where β is a constant and I is an intensity value.
14. The system as claimed in claim 11 , wherein a golden section search algorithm is used to determine a subset of a family of segmentations to be considered.
15. The system as claimed in claim 11 , wherein the one or more selected pixels are input into a Z buffer in the graphics processing unit such that the one or more selected pixels are excluded from processing.
16. A method of segmenting an object in an image, the object being identified by one or more selected pixels located within the object, comprising:
identifying a plurality of possible objects, wherein each possible object includes the one or more selected pixels;
creating a weighted graph having the one or more selected pixels as nodes for each of the plurality of possible objects that include the one or more selected pixels;
determining an isoperimetric ratio described by (x T Lx)/x T d of the weighted graph associated with a possible object; wherein L is a Laplacian matrix defined with edge weights, d is vector with each element corresponding to a pixel and having value equal to a sum of the edge weights of the neighbors of that pixel, and x is a given indication vector that takes a binary value at each node; and
selecting the object from the plurality of possible objects in accordance with the isoperimetric ratio,
wherein the steps are performed in a graphics processing unit.
17. The method as claimed in claim 16 , wherein an edge weight of the weighted graph is a function of a value associated with a first pixel and a value associated with a second pixel.
18. The method as claimed in claim 17 , wherein the edge weights are equal to w ij =exp(−β(I i −I j ) 2 ) where β is a constant and I is an intensity value.
19. The method as claimed in claim 16 , wherein a golden section search algorithm is used to determine a subset of a family of segmentations to be considered.
20. The method as claimed in claim 16 , wherein the one or more selected pixels are input into a Z buffer in the graphics processing unit such that the one or more selected pixels are excluded from processing.