GPU accelerated multi-label digital photo and video editing
First Claim
1. A method of segmenting an object in a digital image having a plurality of pixels, wherein a foreground node located within the object and a background node located outside of the object are selected, comprising:
- determining a plurality of coefficients, each one of the plurality of coefficients being a function of the relative image data associated with two of the plurality of pixels; and
solving a system of linear equations, the system of linear equations including the plurality of coefficients and being a function of the foreground node and the background node, to determine a boundary of the object, using a graphics processing unit.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and system for segmenting an object in a digital image are disclosed. A user selects at least one foreground pixel or node located within the object and at least one background pixel or node located outside of the object. A random walk algorithm is performed to determine the boundaries of the object in the image. In a first step of the algorithm, a plurality of coefficients is determined. Next, a system of linear equations that include the plurality of coefficients are solved to determine a boundary of the object. The processing is performed by a graphics processing unit. The processing can be performed using the near-Euclidean LUV color space or a Lab color space. It is also preferred to use a Z-buffer in the graphics processing unit during processing. The object, once identified, can be further processed, for example, by being extracted from the image based on the determined boundary.
-
Citations
29 Claims
-
1. A method of segmenting an object in a digital image having a plurality of pixels, wherein a foreground node located within the object and a background node located outside of the object are selected, comprising:
-
determining a plurality of coefficients, each one of the plurality of coefficients being a function of the relative image data associated with two of the plurality of pixels; and
solving a system of linear equations, the system of linear equations including the plurality of coefficients and being a function of the foreground node and the background node, to determine a boundary of the object, using a graphics processing unit. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A system for segmenting an object in a digital image having a plurality of nodes, wherein a foreground node located within the object and a background node located outside of the object are selected, comprising:
-
means for determining a plurality of coefficients, each one of the plurality of coefficients being a function of by determining the relative image data associated with two of the plurality of pixels; and
a graphics processing unit for solving a system of linear equations, the system of linear equations including the plurality of coefficients and being a function of the foreground node and the background node, to determine a boundary of the object. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A method of segmenting a digital image having a plurality of pixels and K objects, with K being 2 or greater, at least one of the marked nodes being located within the object and at least one of the marked nodes being located outside of the object are selected, comprising:
-
determining K systems to be solved;
for each of K systems, determining a plurality of coefficients by determining the relative image data associated with two of the plurality of pixels;
for each of the N systems, solving a system of linear equations, each system of linear equations including the plurality of coefficients and being a function of the foreground node and the background node, to determine a boundary of the object;
determining when K−
1 of the K systems have converged to an answer that indicates a location of a boundary of the objects; and
when it is determined that K−
1 of the K systems has converged, terminating the solving of the system of linear equations that have not converged.
-
Specification