Identifying selected pixels in a digital image

• US 7,587,086 B2
• Filed: 06/04/2004
• Issued: 09/08/2009
• Est. Priority Date: 06/04/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shinkevich, Sergei S
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US10/861,207
• Publication Number:
  US 20050271272A1
• Time in Patent Office: 1,922 Days
• Field of Search: 382/173
• 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 one or more 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, wherein when four pixels are in the pixel field adjacent to the pixel reference point, the pixel state flags associated with the pixel reference point include an upper right flag indicating whether a pixel above and right of the pixel reference point is selected, a lower right flag indicating whether a pixel below and right of the pixel reference point is selected, an upper left flag indicating whether a pixel above and left of the pixel reference point is selected and a lower left flag indicating whether a pixel below and left of the pixel reference point is selected, the setting of the one or more pixel state flags being controlled by a processor;

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

wherein setting the one or more pixel state flags includes

determining the sets of pixel state flags associated with each of a first lineal grouping of pixel state flags, and for each set of pixel state flags associated with an adjacent lineal grouping of pixel state flags, setting at least half of the set of pixel state flags by performing a bit shift operation on at least one of the upper right flag, the lower right flag, the upper left flag or the lower left flag of an adjacent set of pixel state flags, the adjacent set of pixel state flags being adjacent to the set of pixel state flags being set and the adjacent set of pixel state flags being one of the first lineal grouping of pixel state flags;

rendering the selected pixel identifier on a display device.

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 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.

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

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

8. 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.

9. The method as recited in claim 8, 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.

10. A system, comprising:

a processor;

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

the processor operating with the memory to provide;

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, wherein when four pixels are associated with a first pixel reference point, the pixel state flags associated with the first pixel reference point include an upper right flag indicating whether a pixel above and right of the pixel reference point is selected, a lower right flag indicating whether a pixel below and right of the pixel reference point is selected, an upper left flag indicating whether a pixel above and left of the pixel reference point is selected and a lower left flag indicating whether a pixel below and left of the pixel reference point is selected, wherein configuring the sets of pixel state flags further comprises determining the sets of pixel state flags associated with each of a first lineal grouping of pixel state flags, and for each set of pixel state flags associated with an adjacent lineal grouping of pixel state flags, configuring at least half of the set of pixel state flags by performing a bit shift on a configuration stored for a previously configured set of pixel state flags, performing the bit shift including bit shifting at least one of the upper right flag, the lower right flag, the upper left flag or the lower left flag of the previously configured set of pixel state flags, the previously configured set of pixel state flags being adjacent to the set of pixel state flags being configured and the previously configured set of pixel state flags being one of the first lineal grouping of pixel state flags; 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.

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

12. The system as recited in claim 10, 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.

13. The system as recited in claim 10, 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.

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

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

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

17. One or more computer storage 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, the memory value including a set of pixel state flags to indicate which of one or more pixels in a pixel field adjacent to the pixel reference point is selected, wherein when four pixels are in the pixel field adjacent to the pixel reference point, the set of pixel state flags associated with the pixel reference point includes an upper right flag indicating whether a pixel above and right of the pixel reference point is selected, a lower right flag indicating whether a pixel below and right of the pixel reference point is selected, an upper left flag indicating whether a pixel above and left of the pixel reference point is selected and a lower left flag indicating whether a pixel below and left of the pixel reference point is selected, wherein associating the memory value includes;

determining the sets of pixel state flags associated with each of a first lineal grouping of pixel state flags, and

for each set of pixel state flags associated with an adjacent lineal grouping of pixel state flags,

setting at least half of the set of pixel state flags by performing a bit shift operation on at least one of the upper right flag, the lower right flag, the upper left flag or the lower left flag of an adjacent set of pixel state flags, the adjacent set of pixel state flags being adjacent to the set of pixel state flags being set and the adjacent set of pixel state flags being one of the first lineal grouping of pixel state flags;

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

identifying a single unselected pixel surrounded by selected pixels and selecting the unselected pixel.

18. The one or more computer storage media as recited in claim 17, wherein each pixel reference point is a pixel vertex.

19. The one or more computer storage media as recited in claim 17, 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.

20. The one or more computer storage media as recited in claim 17, 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.

21. The one or more computer storage media as recited in claim 17, 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.

22. The one or more computer storage media as recited in claim 21, 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.

23. The one or more computer storage media as recited in claim 21, the scanning step further comprising referencing 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.

24. The one or more computer storage media as recited in claim 17, further comprising rendering the border.

25. The one or more computer storage media as recited in claim 17, further comprising utilizing a previously stored memory value to determine a memory value corresponding to a pixel reference point.

26. The one or more computer storage media as recited in claim 17, further comprising the step of identifying a single selected pixel surrounded by unselected pixels and unselecting the single selected pixel.

27. The one or more computer storage media as recited in claim 26, further comprising rendering the single selected pixel to appear similar to the surrounding unselected pixels.

28. The one or more computer storage media as recited in claim 17, further comprising rendering the single unselected pixel to appear similar to the surrounding selected pixels.