Pattern dithering

Claim 3

The method of claim 1 , where: the source image comprises pixels each having a color; the target pixels and the pixels of the source image correspond one-to-one to each other; the region of the source image is a source image pixel corresponding to the target pixel; and the source color is the color of the corresponding source image pixel.

Claim 4

The method of claim 1 , further comprising: determining how many candidate colors to generate; generating the candidate colors in sequence; and selecting the last generated candidate colors as the selected one candidate color.

Claim 5

The method of claim 1 , further comprising: generating two or more temporary colors in the vicinity of the source color; computing a candidate color for each temporary color, where each candidate color is a color in the target palette closest to the respective temporary color; sorting the candidate colors by luminance; and selecting one candidate color based on the position of the target pixel in the target image.

Claim 6

The method of claim 4 , where: the temporary colors are generated using a color space selected for linearity; and the candidate colors are computed using a color space selected for perceptual uniformity.

Claim 7

The method of claim 1 , further comprising sorting the generated candidate colors.

Claim 8

The method of claim 6 , where the candidate colors are sorted by luminance.

Claim 9

The method of claim 1 , where the one candidate color is selected using a dither ordering function whose value depends only on the location of the target pixel in the target image.

Claim 10

The method of claim 8 , where the dither ordering function is a noise function.

Claim 11

The method of claim 9 , where the noise function is biased toward high-frequencies.

Claim 12

The method of claim 8 , where the dither ordering function is a pattern function.

Claim 13

The method of claim 8 , where the dither ordering function is random without bias over the generated candidate colors.

Claim 14

The method of claim 1 , where generating two or more candidate colors comprises: generating a two or more temporary colors in the vicinity of the source color; and mapping the two or more temporary colors to the target palette to generate the two or more candidate colors.

Claim 15

The method of claim 13 , where the mapping operates to select a color in the target palette closest to the temporary color.

Claim 16

The method of claim 14 , where the closest color is determined with respect to a color space of the target palette.

Claim 17

The method of claim 14 , where the closest color is determined in CIE L*a*b* color space.

Claim 18

The method of claim 1 , where generating two or more candidate colors comprises: adding an offset value based on an accumulation error value to the source color to generate a temporary color; mapping the temporary color to the target palette to generate a candidate color; adding a difference between the source color and the candidate color to the accumulation error value; and repeating the above steps until all the candidate colors have been generated.

Claim 19

The method of claim 17 , where the mapping is to a color in the target palette closest to the temporary color.

Claim 20

The method of claim 18 , where the closest color is determined with respect to a color space of the target palette.

Claim 21

The method of claim 18 , where the closest color is determined in CIE L*a*b* color space.

Claim 22

The method of claim 17 , where the offset value is equal to the accumulation error value multiplied by an error multiplier.

Claim 23

The method of claim 21 , where the error multiplier is a value between 0 and 1.

Claim 24

The method of claim 17 , where the mapping comprises computing an approximation to a color in the target palette closest to the temporary color using an inverse color table.

Claim 25

The method of claim 1 , where generating two or more candidate colors permits two or more of the candidate colors to be the same.

Claim 28

The method of claim 25 , where the target color for each target pixel is selected independently of the selection of the target color for any other target pixel.

Claim 29

The method of claim 25 , where: the temporary colors are generated using a color space selected for linearity; and the candidate colors are computed using a color space selected for perceptual uniformity.

Claim 32

The method of claim 28 , where: the source image comprises pixels each having a color; the target pixels and the pixels of the source image correspond one-to-one to each other; the region of the source image is a source image pixel corresponding to the target pixel; the source color is the color of the corresponding source image pixel; and the value of the function depends on the position of the target pixel in the target image.

Claim 33

The method of claim 29 , where N is fixed at 16.

Claim 34

The method of claim 28 , where the integer value n depends on the position of the target pixel in the target image, and where computing the sequence of N candidate colors comprises: generating a sequence of N temporary colors in the vicinity of the source color; and computing a candidate color for each temporary color, where each candidate color is a color in the target palette closest to the respective temporary color.

Claim 35

The method of claim 31 , where: the temporary colors are generated using a color space selected for linearity; and the candidate colors are computed using a color space selected for perceptual uniformity.

Claim 38

The method of claim 33 , where applying a dither ordering function comprises: sorting the candidate colors in order by luminance; evaluating the dither ordering function to determine a position in the sorted order; and selecting the candidate color at the position in the sorted order determined by evaluating the dither ordering function as the selected candidate color.

Claim 39

The method of claim 34 , where the dither ordering function is a noise function.

Claim 40

The method of claim 34 , where the value of the dither ordering function depends only on the location of the target pixel the target image.

Claim 41

The method of claim 33 , where generating two or more candidate colors comprises: selecting a basis set of colors from among the target palette colors close to the source color, the basis set enclosing the source color so that the source color can be expressed as a weighted average of the basis set colors; and generating as the candidate colors the basis set colors in proportions approximately equal to the weights required to produce the weighted average.

Claim 44

The system of claim 38 , further comprising: means for generating two or more temporary colors in the vicinity of the source color; means for computing a candidate color for each temporary color, where each candidate color is a color in the target palette closest to the respective temporary color; means for sorting the candidate colors by luminance; and means for selecting one candidate color based on the position of the target pixel in the target image.

Claim 45

The system of claim 39 , where: the temporary colors are generated using a color space selected for linearity; and the candidate colors are computed using a color space selected for perceptual uniformity.

Claim 46

A computer program product stored on a computer-readable medium, for generating a target image of target pixels having a target palette from a source image, the computer program comprising instructions operable to cause a computer to: determine a source color of a region of the source image corresponding to a location of a target pixel; generate two or more candidate colors for a target color of the target pixel from the source color, where the candidate colors are colors in the target palette; select one candidate color; and set the target color of the target pixel to be the selected candidate color.

Claim 47

A computer program product stored on a computer-readable medium, for generating a target image of target pixels having a target palette from a source image, the computer program comprising instructions operable to cause a computer to: determine a source color of a region of the source image corresponding to a location of a target pixel; generate two or more candidate colors for a target color of the target pixel from the source color, where the candidate colors are colors in the target palette; select one candidate color; and set the target color of the target pixel to be the selected candidate color.

Claim 48

The computer program product of claim 41 , further comprising instructions operable to cause a computer to: generate two or more temporary colors in the vicinity of the source color; compute a candidate color for each temporary color, where each candidate color is a color in the target palette closest to the respective temporary color; sort the candidate colors by luminance; and select one candidate color based on the position of the target pixel in the target image.

Claim 49

The computer program product of claim 42 , further comprising instructions operable to cause a computer to: generate the temporary colors using a color space selected for linearity; and compute the candidate colors using a color space selected for perceptual uniformity.

Claim 50

The computer program product of claim 41 , wherein the instructions operable to cause a computer to select one candidate color include instructions operable to cause a computer to select the one candidate color using a dither ordering function whose value depends only on the location of the target pixel in the target image.

Claim 51

The computer program product of claim 41 , wherein the instructions operable to cause a computer to generate two or more candidate colors include instructions operable to cause a computer to: add an offset value based on an accumulation error value to the source color to generate a temporary color; map the temporary color to the target palette to generate a candidate color; add a difference between the source color and the candidate color to the accumulation error value; and repeat the above steps until all the candidate colors have been generated.

Claim 52

A computer program product stored on a computer-readable medium, for generating from a source image a target image comprising target pixels having colors limited to colors found in a target palette, the computer program product comprising instructions operable to cause a computer to: determine a source color of a region of the source image corresponding to a location of a target pixel; evaluate a function to calculate an integer value n in a range of integers 1 to N; use the source color to compute a sequence of N candidate colors, where each candidate color is a color in the target palette; and set a target color of the target pixel to be the n'th candidate color in the sequence of N candidate colors.

Claim 53

A computer program product stored on a computer-readable medium, for generating from a source image a target image comprising target pixels having colors limited to colors found in a target palette, the computer program product comprising instructions operable to cause a computer to: determine a source color of a region of the source image corresponding to a location of a target pixel; evaluate a function to calculate an integer value n in a range of integers 1 to N; use the source color to compute a sequence of N candidate colors, where each candidate color is a color in the target palette; and set a target color of the target pixel to be the n'th candidate color in the sequence of N candidate colors.

Claim 54

The computer program product of claim 46 , wherein the integer value n depends on the position of the target pixel in this target image, and wherein the instructions operable to cause a computer to use the source color to compute the sequence of N candidate colors include instructions operable to cause a computer to: generate a sequence of N temporary colors in the vicinity of the source color; and compute a candidate color for each temporary color, where each candidate color is a color in the target palette closest to the respective temporary color.

Claim 55

A computer program product stored on a computer-readable medium, for generating from a source image a target image comprising target pixels having colors limited to colors found in a target palette, the computer program product comprising instructions operable to cause a computer to: determine a source color of a region of the source image corresponding to a location of a target pixel; generate two or more candidate colors for a target color of the target pixel from the source color, where the candidate colors are colors in the target palette, where any target palette color can occur more than once among the candidate colors, and where candidate colors are generated to have an average color close to the source color; determine a luminance value for each candidate color; apply a dither ordering function to select one candidate color from the two or more candidate colors, the dither ordering function operating to spread out luminance differences so that in any local area, overly bright pixels tend to be near overly dark pixels; and set the target color of the target pixel to be the selected candidate color.

Claim 56

A computer program product stored on a computer-readable medium, for generating from a source image a target image comprising target pixels having colors limited to colors found in a target palette, the computer program product comprising instructions operable to cause a computer to: determine a source color of a region of the source image corresponding to a location of a target pixel; generate two or more candidate colors for a target color of the target pixel from the source color, where the candidate colors are colors in the target palette, where any target palette color can occur more than once among the candidate colors, and where candidate colors are generated to have an average color close to the source color; determine a luminance value for each candidate color; apply a dither ordering function to select one candidate color from the two or more candidate colors, the dither ordering function operating to spread out luminance differences so that in any local area, overly bright pixels tend to be near overly dark pixels; and set the target color of the target pixel to be the selected candidate color.