Efficient diffusion dithering using dyadic rationals
AssigneeQUALCOMM Incorporated
InventorYuriy Reznik
Life of this patent
Estimating the term…
Abstract
Diffusion dithering can be performed efficiently by applying a set of diffusion filter weights with one or more shift, add, and/or subtract operations. An existing diffusion filter can be approximated with dyadic rationals, thereby allowing division operations in applying the filter weights to be performed with bit-shifting operations. An algorithm is identified to calculate the product of a set of filter weights and a pixel error, where the algorithm performs the calculations using one or more shift, add, or subtract operations. An exhaustive search of the combinations of operations can be made to find an efficient algorithm to calculate the products
Claims25
A method of processing an image, the method comprising:
- calculating an error based on a difference between a color of a first pixel in the image and a color value selected from a color palate based on said color;
- calculating first products of said error and each of a plurality of weights in a filter by using one or more shift, add, or subtract operations, or combination thereof, wherein each of said plurality of weights is a dyadic rational;
- and
- distributing said first products to a plurality of second pixels in accordance with said filter.
One or more computer-readable media comprising executable instructions to perform a method of processing an image, the method comprising:
- calculating an error based on a difference between a color of a first pixel in the image and a color value selected from a color palate based on said color;
- calculating first products of said error and each of a plurality of weights in a filter by using one or more shift, add, or subtract operations, or combination thereof, wherein each of said plurality of weights is a dyadic rational;
- and
- distributing said first products to a plurality of second pixels in accordance with said filter.
An apparatus to process an image, the apparatus comprising:
- an interface that receives the image;
- at least one processor that carries out logic to calculate an error based on a difference between a color of a first pixel in the image and a color value selected from a color palate based on said color, to calculate first products of said error and each of a plurality of weights in a filter by using one or more shift, add, or subtract operations, or combination thereof, wherein each of said plurality of weights is a dyadic rational, and to distribute said first products to a plurality of second pixels in accordance with said filter;
- and
- a memory that is coupled to, or integrated with, said processor, said logic being stored in said memory.
An apparatus for processing an image, the apparatus comprising:
- means for calculating an error based on a difference between a color of a first pixel in the image and a color value selected from a color palate based on said color;
- means for calculating first products of said error and each of a plurality of weights in a filter by using one or more shift, add, or subtract operations, or combination thereof, wherein each of said plurality of weights is a dyadic rational;
- and
- means for distributing said first products to a plurality of second pixels in accordance with said filter.
One or more computer-readable media comprising executable instructions to perform a method of facilitating the calculation of dithering weights, the method comprising:
- receiving a plurality of factors;
- initializing an array to contain a first element that comprises a base value;
- populating the array with a plurality of second elements that each comprise:
- (a) a value, and (b) an indication of an operation to be performed on one or more other elements in the array to derive the value, the operation being either to add the values of two elements, to subtract the value of one element from another element, or to left-shift the value of one element a number of bits;
- and
- making a determination that a contents of said array is to be added to a set of saved algorithms, the determination being based on one or more criteria that comprise:
- said array being in a state in which each of the factors is found among the values in the elements of said array.
Dependencies are inferred from the claim text.