Identifying selected pixels in a digital image

• US 20050271272A1
• Filed: 06/04/2004
• Published: 12/08/2005
• Est. Priority Date: 06/04/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shinkevich, Sergei S.
• Granted Patent: US 7,587,086 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

The present application provides for accurately identifying a selection of pixels in a digital image. A pixel edgewalk procedure utilizes pixel reference points situated around a pixel, such as at pixel vertices, to determine where to draw an outline to encompass selected pixels. Each pixel reference point is represented by one or more bits in memory that indicate certain information about each particular pixel reference point and pixels surrounding the pixel reference point. Utilizing this information, a determination is made as to where an outline can be drawn according to certain pixel reference points to encompass only pixels that are selected pixels. Resource overhead for determining bit settings for some pixel reference points is reduced by utilizing a bit-wise shift in memory bits allocated to an adjacent pixel reference point.

Claims

1. A method, comprising:

for each pixel reference point in a digital image that includes a plurality of pixels, setting up to multiple pixel state flags to indicate which of one or more pixels in a pixel field adjacent to the pixel reference point is selected, there being a set of pixel state flags associated with each pixel reference point; and

traversing the pixel state flags to determine a location for a selected pixel identifier that encompasses one or more sets of selected pixels.

2. The method as recited in claim 1, further comprising determining a direction in which a segment of the selected pixel identifier extends from a pixel reference point from a value of the pixel state flags.

3. The method as recited in claim 1, wherein pixel reference points further comprise pixel vertices.

4. The method as recited in claim 1, wherein a pixel field includes from one to four pixels, depending on a location of a pixel reference point in the digital image.

5. The method as recited in claim 1, further comprising rendering the selected pixel identifier.

6. The method as recited in claim 1, further comprising setting at least some of the sets of pixel state flags by performing a shift operation on existing pixel state flags.

7. The method as recited in claim 1, further comprising setting one or more scan flags associated with a pixel reference point when a set of pixel state flags associated with the pixel reference point is traversed.

8. The method as recited in claim 7, further comprising scan flags that identify a number of times that a set of pixel state flags has been traversed.

9. The method as recited in claim 7, further comprising scan flags that indicate whether a set of pixel state flags can be traversed a subsequent time.

10. The method as recited in claim 1, further comprising omitting a selected pixel identifier if the selected pixel identifier encompasses less than a minimum threshold of pixels.

11. The method as recited in claim 10, further comprising changing pixels appearing within the selected pixel identifier to appear similar to pixels immediately adjacent to the pixels appearing within the selected pixel identifier.

12. A system, comprising:

a processor;

a digital image stored in memory, the digital image including multiple pixels;

a pixel selection module configured to select one or more pixels in the digital image;

a plurality of pixel state flags stored in memory;

a pixel selection identification module configured to;

configure a set of pixel state flags for each of a plurality of pixel reference points in the digital image to indicate which pixels associated with the pixel reference points are selected; and

scan the sets of pixel state flags to determine where a selected pixel identifier will encompass all of a group of contiguous selected pixels.

13. The system as recited in claim 12, wherein there are more than one contiguous group of selected pixels and a selected pixel identifier is determined for each group of selected pixels.

14. The system as recited in claim 12, further comprising one or more scan flags associated with each set of pixel state flags that are set according to how many times a set of pixel state flags has been scanned.

15. The system as recited in claim 12, further comprising determining a vector for each of multiple selected pixel identifier segments according to one or more sets of pixel state flags associated with the selected pixel identifier segments.

16. The system as recited in claim 15, further comprising determining a vector that determines at least a direction of a corresponding selected pixel identifier segment.

17. The system as recited in claim 15, wherein the determining is based on a value of a set of pixel state flags.

18. The system as recited in claim 12, wherein pixel reference identifiers are identified at each vertex of a pixel.

19. The system as recited in claim 12, wherein the configuring step further comprises configuring at least some pixel state flags by manipulating previously configured pixel state flags.

20. One or more computer-readable media containing computer-executable instructions that, when executed on a computer, perform the following steps:

identifying a plurality of pixel reference points in a digital image having multiple pixels, each pixel reference point corresponding to one or more of the pixels;

associating a memory value with each pixel reference point, each memory value denoting which of one or more pixels adjacent to a corresponding pixel reference point are selected; and

scanning the memory values to determine a border of at least one group of contiguous selected pixels.

21. The one or more computer-readable media as recited in claim 20, wherein each pixel reference point is a pixel vertex.

22. The one or more computer-readable media as recited in claim 20, wherein:

each pixel reference point is associated with from one to four pixels; and

each memory value further comprises four bits, each bit corresponding to a possible pixel associated with the pixel reference point that corresponds to the memory value.

23. The one or more computer-readable media as recited in claim 20, further comprising ignoring a border of a group of contiguous selected pixels if the group of contiguous selected pixels contains a number of pixels that is less than a specified minimum threshold.

24. The one or more computer-readable media as recited in claim 20, the scanning step further comprising for each border pixel reference point, determining a vector that indicates where a subsequent border segment should extend from the border pixel reference point.

25. The one or more computer-readable media as recited in claim 24, the scanning step further comprising referencing one or more scan flags associated with a border pixel reference point to determine if the border pixel reference point has been previously scanned.

26. The one or more computer-readable media as recited in claim 24, the scanning step further comprising reference one or more scan flags associated with a border pixel reference point to determine if a border has been completed around a particular group of selected pixels.

27. The one or more computer-readable media as recited in claim 20, further comprising rendering the border.

28. The one or more computer-readable media as recited in claim 20, further comprising utilizing a previously stored memory value to determine a memory value corresponding to a pixel reference point.

29. The one or more computer-readable media as recited in claim 20, further comprising the step of identifying a single selected pixel surrounded by unselected pixels and unselected the single selected pixel.

30. The one or more computer-readable media as recited in claim 29, further comprising rendering the single selected pixel to appear similar to the surrounding unselected pixels.

31. The one or more computer-readable media as recited in claim 20, further comprising the step of identifying a single unselected pixel surround by selected pixels and selecting the unselected pixel.

32. The one or more computer-readable media as recited in claim 31, further comprising rendering the single unselected pixel to appear similar to the surrounding selected pixels.