Image selection techniques

• US 8,452,087 B2
• Filed: 09/30/2009
• Issued: 05/28/2013
• Est. Priority Date: 09/30/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sun, Jian, Liu, Jiangyu
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US12/571,317
• Publication Number:
  US 20110075921A1
• Time in Patent Office: 1,336 Days
• Field of Search: 382/162, 382/164, 382/173, 382/100, 382/275, 382/199, 382/276, 382/282, 382/254, 382/266, 340/541, 348/143, 348/222.1, 703/2
• US Class Current: 382/164
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

Tools disclosed herein comprise progressive, paint stroke based region recognition and selection tools. Using these tools, a user may partially paint a region of interest directly on an image (by using a paint brush or other similar tool). Unlike conventional selection tools, a user is not required to paint the entire region pixel-by-pixel. Rather the desired region is automatically and intelligently recognized based on the partial selection. This is accomplished via a progressive selection algorithm. In addition, these tools provide the ability to quickly execute such region selections on multi-megapixel images.

Claims

1. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct a device to perform actions comprising:

a. selecting a portion of a foreground region of an image;

b. creating a color foreground model based at least on the selected portion;

c. creating a color background model based at least on the remaining unselected portion of the image;

d. determining whether unselected pixels belonging to the unselected portion are foreground pixels that form a portion of the foreground region or background pixels that form a portion of a background region based at least on the color foreground model and the color background model;

e. at least partly in response to determining that unselected pixels are foreground pixels that form a portion of the foreground region, labeling the unselected pixels of the image as foreground pixels; and

f. at least partly in response to determining that unselected pixels are background pixels that form a portion of the background region, labeling the unselected pixels as background pixels; and

g. wherein the determining if unselected pixels are foreground pixels or background pixels comprises;

i. determining an average pixel color of the pixels comprising the foreground model;

ii. determining an average pixel color of the pixels comprising the background model; and

iii. comparing the color of an unselected pixel of the image to the average pixel color of the foreground model and the average pixel of the background model.

2. The one or more processor-accessible media as recited in claim 1, wherein the comparing comprises minimization of an energy function:

E(X)=Σ

_pE_d(x_p)+λ

Σ

_p,qE_c(x_p,x_q), where λ

is weight, x_p encodes a cost of pixel p, E_c(x_p,x_q)=|x_p−

x_q|·

(β

·

∥

I_p−

I_q∥

ε

)<sup>−

1</sup>, where ε

=0.05 and β

=(≅

∥

I_p−

I_q∥

²≈

)<sup>−

1</sup>, is the expectation operator over the entire image, E(X) is a representation of the energy function, E_d(x_p) is a data term, X is a label of each pixel, X_p is a label of pixel p, X_q is a label of pixel q, I is a pixel color, I_p is the color of pixel p, and I_q is the color of pixel q.

3. The one or more processor-accessible media as recited in claim 2, wherein the minimization of the energy function is computed in parallel via multiple processor-cores by:

i. extracting a plurality of nodes from E(X)=Σ

_pE_d(x_p)+λ

Σ

_p,qE_c(x_p,x_q),

ii. creating a graph based at least on the plurality nodes;

iii. dividing the graph into a plurality of subgraphs; and

iv. concurrently determining an augmenting path in the plurality of subgraphs.

4. The one or more processor-accessible media as recited in claim 3, wherein the number of subgraphs is equal to a number of processor-cores of a computing device that the parallel computation will be executed on.

5. The one or more processor-accessible media as recited in claim 2, wherein the minimization of the energy function further comprises:

creating a graph where each graph node represents an unselected pixel; and

optimizing the graph.

6. The one or more processor-accessible media as recited in claim 1, further comprising instructions in the memory for:

a. defining borders between the foreground region and a background region by;

i. creating a fixed narrow band from a low resolution version of the image;

ii. creating an adaptive band based at least partially on the fixed narrow band;

iii. overlaying the adaptive band over a high resolution version of the image; and

iv. labeling pixels in the adaptive band as either foreground pixels or background pixels.

7. The one or more processor-accessible media as recited in claim 1, wherein the foreground color model comprises a Gaussian Mixture Model.

8. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct a device to perform actions comprising:

a. selecting a portion of a foreground region of an image;

b. creating a color foreground model based at least on the selected portion;

c. creating a color background color model based at least on a portion of the remaining unselected portion of the image; and

d. determining whether unselected pixels belonging to the unselected portion are foreground pixels that form a portion of the foreground region or background pixels that form a portion of a background region based at least on the color foreground model and the color background model;

i. at least partially in response to determining that unselected pixels are foreground pixels that form a portion of the foreground region, labeling the unselected pixels of the image as foreground pixels; and

ii. at least partly in response to determining that unselected pixels are background pixels that form a portion of the background region, labeling the unselected pixels as background pixels.

9. The one or more processor-accessible media as recited in claim 8, wherein the determining if unselected pixels are foreground pixels or background pixels comprises:

a. determining an average pixel color of the pixels comprising the background model; and

b. comparing the color of an unselected pixel of the image to the average pixel color of the foreground model and the average pixel background model.

10. The one or more processor-accessible media as recited in claim 9, wherein the comparing comprises minimization of an energy function:

E(X)=Σ

_pE_d(x_p)+λ

Σ

_p,qE_c(x_p,x_q), where λ

is weight, x_p encodes a cost of pixel p, E_c(x_p,x_q)=∥

x_p−

x_q|·

(β

·

∥

I_p−

I_q∥

+ε

)¹, where ε

=0.05 and β

=(∥

I_p−

I_q∥

²)<sup>−

1</sup>, is the expectation operator over the entire image, E(X) is a representation of the energy function, E_d(x_p) is a data term, X is a label of each pixel, X_p is a label of pixel p, X_q is a label of pixel q, I is a pixel color, I_p is the color of pixel p, and I_q is the color of pixel q.

11. The one or more processor-accessible media as recited in claim 10, wherein the minimization of the energy function is computed in parallel via multiple processor-sores by:

i. extracting a plurality of nodes from E(X)=Σ

_pE_d(x_p)+λ

Σ

_p,qE_c(x_p,x_q);

ii. creating a graph based at least on the plurality nodes;

iii. dividing the graph into a plurality of subgraphs; and

iv. concurrently determining an augmenting path in the plurality of subgraphs.

12. The one or more processor-accessible media as recited in claim 11, wherein the number of subgraphs is equal to a number of processor-cores of a computing device that the parallel computation will be executed on.

13. The one or more processor-accessible media as recited in claim 8, further comprising instructions in the memory for:

a. defining borders between the foreground region and a background region by;

i. creating a fixed narrow band from a low resolution version of the image;

ii. creating an adaptive band based at least partially on the fixed narrow band;

iii. overlaying the adaptive band over a high resolution version of the image; and

iv. labeling pixels in the adaptive band as either foreground pixels or background pixels.

14. The one or more processor-accessible media as recited in claim 8, wherein the selection of the foreground portion is done via at least one paint brush stroke.

15. The one or more processor-accessible media as recited in claim 8, the foreground color model comprises a Gaussian Mixture Model.

16. A computing device comprising:

a processor;

a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for;

a. selecting a portion of a foreground region of an image;

b. creating a color foreground model based at least on the selected portion;

c. creating a color background model based at least on a portion of the remaining unselected portion of the image;

d. determining if unselected pixels belonging to the unselected portion are foreground pixels that form a portion of the foreground region or background pixels that form a portion of a background region based at least on the color foreground model and the color background model;

i. at least partly in response to determining that unselected pixels are foreground pixels, that form a portion of the foreground region, labeling the unselected pixels of the image as foreground pixels; and

ii. at least partly in response to determining that unselected pixels are background pixels that form a portion of the background region, labeling the unselected pixels as background pixels.

17. The computing device of claim 16, wherein the determining if unselected pixels are foreground pixels or background pixels comprises:

a. determining an average pixel color of the pixels comprising the foreground model;

b. determining an average pixel color of the pixels comprising the of the background model; and

c. comparing the color of an unselected pixel of the image to the average pixel color of the foreground model and the average pixel of the background model.

18. The computing device of claim 17, wherein the comparing comprises minimization of an energy function:

E(X)=Σ

_pE_d(x_p)λ

Σ

_p,qE_c(x_p,x_q), where λ

is weight, x_p encodes a cost of pixel p, E_c(x_p,x_q)=|_p−

x_q|·

(β

·

∥

I_p−

I_q∥

+ε

)¹, where ε

=0.05 and β

=(∥

I_p−

I_q∥

²)<sup>−

1</sup>, is the expectation operator over the entire image, E(X) is a representation of the energy function, E_d(x_p) is a data term, X is a label of each pixel, X_p is a label of pixel p, X_q is a label of pixel q, I is a pixel color, I_p is the color of pixel p, and I_q is the color of pixel q.

19. The computing device of claim 16, wherein the selection of foreground portion is done via at least one paint brush stroke.

20. The computing device of claim 16, the foreground color model comprises a Gaussian Mixture Model.