GPU accelerated multi-label digital photo and video editing

• US 20060104513A1
• Filed: 10/03/2005
• Published: 05/18/2006
• Est. Priority Date: 11/15/2004
• Status: Active Grant

• Current Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Aharon, Shmuel, Schiwietz, Thomas, Grady, Leo
• Granted Patent: US 7,630,549 B2
• Time in Patent Office: Days
• US Class Current: 382/180
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

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.

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.

2. The method as claimed in claim 1, wherein the function includes the difference in a first image intensity at a first pixel and a second image intensity of a second pixel.

3. The method as claimed in claim 1, wherein the function includes the difference in a first vector of colors at a first pixel and a second vector of colors at a second pixel.

4. The method as claimed in claim 1, comprising extracting the object from the digital image based on the boundary.

5. The method as claimed in claim 1, wherein the plurality of coefficients is determined using a near-Euclidean LUV color space.

6. The method as claimed in claim 1, wherein the plurality of coefficients is determined using a Lab color space.

7. The method as claimed in claim 1, wherein the foreground node and the background node are masked out by a Z-buffer in the graphics processing unit.

8. The method as claimed in claim 6, wherein the foreground node and the background node are masked out by a Z-buffer in the graphics processing unit.

9. The method as claimed in claim 8, comprising extracting the object from the digital image based on the boundary.

10. The method as claimed in claim 9, wherein the method is performed by a digital imaging editing tool.

11. The method as claimed in claim 1, wherein the digital image is a still image.

12. The method as claimed in claim 1, wherein the digital image is a video image.

13. The method as claimed in claim 1, comprising converting data representative of the digital image from one space to a near-Euclidean LUV color space prior to determining the plurality of coefficients.

14. The method as claimed in claim 1, comprising converting data representative of the digital image from one space to a Lab color space prior to determining the plurality of coefficients.

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.

16. The system as claimed in claim 15, wherein the function includes the difference in a first image intensity at a first pixel and a second image intensity of a second pixel.

17. The system as claimed in claim 15 wherein the function includes the difference in a first vector of colors at a first pixel and a second vector of colors at a second pixel.

18. The system as claimed in claim 15, comprising means for extracting the object from the digital image based on the boundary.

19. The system as claimed in claim 15, wherein the plurality of coefficients is determined using a near-Euclidean LUV color space.

20. The system as claimed in claim 15, wherein the plurality of coefficients is determined using a Lab color space.

21. The system as claimed in claim 15, wherein the foreground node and the background node are masked out by a Z-buffer in the graphics processing unit.

22. The system as claimed in claim 20, wherein the foreground node and the background node are masked out by a Z-buffer in the graphics processing unit.

23. The system as claimed in claim 22, comprising means for extracting the object from the digital image based on the boundary.

24. The system as claimed in claim 23, further comprising a digital imaging editing tool.

25. The system as claimed in claim 15, wherein the digital image is a still image.

26. The system as claimed in claim 15, wherein the digital image is a video image.

27. The system as claimed in claim 15, comprising means for converting data representative of the digital image from one space to a near-Euclidean LUV color space so that the near-Euclidean LUV color space can be used by the means for determining the plurality of coefficients.

28. The system as claimed in claim 15, comprising means for converting data representative of the digital image from one space to a Lab color space so that the Lab color space can be used by the means for determining the plurality of coefficients.

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.