Graphics processing method and system

Patent metadata

Field	Value
Publication number	US-9153052-B2
Application number	US-404207-A
Country	US
Kind code	B2
Filing date	Dec 20, 2007
Priority date	Oct 22, 2004
Publication date	Oct 6, 2015
Grant date	Oct 6, 2015

Abstract

The embodiments discussed herein involve flood filling a region with anti-aliasing. In forming a fill region, a candidate pixel can be included in the region based on a color of the pixel and also a color of a neighbor of the point. The inclusion basis may be a color distance between a seed color and the points, and a color distance between the seed color and the point's neighbor. Points in the region may be weighted according to their color distance relative to the seed color, where the color distance can also take into account alpha values. Flood filling may be anti-aliased by assigning alpha values to pixels in gaps between corners of the fill region, where an alpha value may be proportional to a point's contribution to the gap. Dimples in a fill region may be tested for and used to determine which of two flood fill algorithms to use.

First claim

What is claimed is:

1. A method of performing a flood fill operation on an image given a seed point, the method comprising:
determining, using a computer having a processor, whether to flood fill a candidate point of the image based on a color of the candidate point, a color of the seed point, and a color of a neighbor point of the candidate point, the determining being based on a color distance between the neighbor point and the seed point, and a color distance between the candidate point and the seed point, wherein the color distance between the candidate point and the seed point is determined by multiplying the smaller of their respective alpha values by a color distance determined based on their respective color channels,
weighting fill contribution of the candidate point determined to be flood filled according to the color distance between the candidate point and the seed point, and
for each point in a gap between two corners surrounding pixels of a fill set, setting an opacity value proportional to contribution to the gap by a first area closest to the fill set and a second area opposite the first area as defined by an imaginary line connecting the corners.

2. A volatile or non-volatile non-transitory computer-readable storage storing information enabling a computing device to perform the method according to claim 1 .

3. A method of, given a seed point, performing flood fill operations on images using a computer having a processor by applying a flood fill algorithm to fill regions of the images, where the flood fill algorithm comprises:
determining, using the processor, whether to flood fill a candidate point in a region of one of the images based on a color distance between a neighbor point of the candidate point and the seed point and a color distance between the candidate point and the seed point, wherein the color distance between the candidate point and the seed point is determined by multiplying the smaller of their respective alpha values by a color distance determined based on their respective color channels, and
weighting fill contribution of the candidate point determined to be flood filled according to the color distance between the candidate point and the seed point,
where the region is at least in part bounded by pixels of the one of the images that have, in a direction away from the region, substantially increasing color distances from a color of the seed point.

4. A flood filling method comprising:
providing an image having pixels corresponding to manually sketched lines and one or more regions formed thereby, and
processing a region of the image using a computer having a processor by:
determining whether to flood fill a candidate point in the region of the image based on a color distance between a neighbor point of the candidate point and a seed point and a color distance between the candidate point and the seed point, wherein the color distance between the candidate point and the seed point is determined by multiplying the smaller of their respective alpha values by a color distance determined based on their respective color channels, and
weighting fill contribution of the candidate point determined to be flood filled according to the color distance between the candidate point and the seed point, and

for each point in a gap between two corners surrounding pixels of a fill set, setting an opacity value proportional to contribution to the gap by a first area closest to the fill set and a second area opposite the first area as defined by an imaginary line connecting the corners.

5. A method according to claim 4 , where the manually sketched lines comprise lines drawn with an implement used primarily for drawing lines by hand.

6. A method according to claim 5 , where the implement comprises a pencil, or a pen, or a crayon, or a marker, or a paint brush.

7. A flood filling device comprising:
at least one processor configured to execute operations including:
providing an image having pixels corresponding to manually sketched lines and one or more regions formed thereby, and
automatically anti-aliasing and flood filling such a region of the image;
processing a region of the image by:
determining whether to flood fill a candidate point in the region of the image based on a color distance between a neighbor point of the candidate point and a seed point and a color distance between the candidate point and the seed point, wherein the color distance between the candidate point and the seed point is determined by multiplying the smaller of their respective alpha values by a color distance determined based on their respective color channels for, and
weighting fill contribution of the candidate point determined to be flood filled according to the color distance between the candidate point and the seed point, and

for each point in a gap between two corners surrounding pixels of a fill set, setting an opacity value proportional to contribution to the gap by a first area closest to the fill set and a second area opposite the first area as defined by an imaginary line connecting the corners.

8. A method of performing a flood fill on an image, given a seed point, the method comprising:
determining, using a computer comprising a processor, whether to flood fill a candidate point in the image based on a color distance between a neighbor point of the candidate point and the seed point and a color distance between the candidate point and the seed point, wherein the color distance between the candidate point and the seed point is determined by multiplying the smaller of their respective alpha values by a color distance determined based on their respective color channels for producing a multiplied alpha distance, and
weighting fill contribution of the candidate point determined to be flood filled according to the color distance between the candidate point and the seed point.

9. A method according to claim 8 , wherein the weighting is done when the candidate point is different in color to the color of the seed point.

10. The method according to claim 8 , wherein the color distance between the candidate point and the seed point is further determined by choosing as the color distance either the multiplied alpha distance or a difference between the alpha values of the candidate point and the seed point.

11. The method according to claim 10 , wherein the larger of the multiplied alpha distance and the difference between the alpha values is chosen as the color distance.

12. A volatile or non-volatile non-transitory computer-readable storage storing information enabling a computing device to perform the method according to claim 8 .

13. A device performing a flood fill on an image, given a seed point, comprising:
a computer configured to execute operations, including:
determining whether to flood fill a candidate point in the image based on a color distance between a neighbor point of the candidate point and the seed point and a color distance between the candidate point and the seed point, wherein the color distance between the candidate point and the seed point is determined by multiplying the smaller of their respective alpha values by a color distance determined based on their respective color channels for producing a multiplied alpha distance, and
weighting fill contribution of the candidate point determined to be flood filled according to the color distance between the candidate point and the seed point.

14. A method of performing a flood fill operation on an image, given a seed point, the method comprising:
generating a fill set with a first fill algorithm and performing the flood fill operation; and
checking for dimp

Assignees

• Ameline Ian R
• Blais Eric A
• Autodesk Inc

Inventors

• Ameline Ian R
• Blais Eric A

Classifications

• G06T11/10 Primary

  Texturing; Colouring; Generation of textures or colours (retouching, inpainting or scratch removal G06T5/77) · CPC title

• G06T11/40 Primary

  Filling planar surfaces by adding surface attributes, e.g. adding colours or textures · CPC title

• G06T2200/12

  involving antialiasing · CPC title

• G06T2207/10024

  Color image · CPC title

• G06T5/30

  Erosion or dilatation, e.g. thinning · CPC title