#include <dvmcolor.h>
Structure UnpackColor stores an (r, g, b) tuple, with a extra tag. This structure is used as part of ColorHashTables.
typedef struct UnpackColor {
unsigned char tag;
unsigned char r;
unsigned char g;
unsigned char b;
} UnpackColor;
- tag
- An extra 8 bits of data that can be used by the programmer. In the hash table, tag is used to indicate if an entry in the table is empty or not.
- r
- Red value of pixel (0..255)
- g
- Green value of pixel (0..255)
- b
- Blue value of pixel (0..255)
A color can have three components (r, g, b) that can be accessed individually or can be retrieved in packed format (a 4 byte integer). This provides an efficient way to copy, compare and initialize colors. This structure is used as part of ColorHashTables.
typedef union Color {
UnpackColor unpack;
int pack;
} Color;
- unpack
- Unpacked version of the (r, g, b) value. Each color can be accessed individually.
- pack
- Packed version of the (r, g, b) value.
ColorHashEntry is the type of an entry in ColorHashTable. It contains a Color (r,g,b) as the key, and an integer value.
typedef struct ColorHashEntry {
Color color;
int value;
} ColorHashEntry;
- color
- The key of this hash table entry.
- value
- The value of this hash table entry.
A ColorHashTable is an open-addressing hash table that maps colors to values. ColorHashTables are generally used as caches in Dali. That is, when a color is mapped to a value (e.g., when converting an image to a colormapped image in GIF encoding), the mapping can be stored in a ColorHashTable so the next mapping can be done very quickly.
typedef struct ColorHashTable {
int size;
int numOfEntry;
ColorHashEntry *table;
} ColorHashTable;
- size
- The number of buckets in the hash table.
- numOfEntry
- The number of elements inserted into the hash table.
- table
- A pointer to the table of entries.
A VpNode is a node in the VP (Vintage Point) tree data structure. The actual tree is just an array with 256 VpNodes. For a brief description of the data structure, see the overview of color package.
typedef struct VpNode {
unsigned char index;
unsigned char left;
unsigned char right;
float ll, lu, rl, ru, mu;
} VpNode;
- index
- index to image maps. It specifies the node color of this node.
- left
- a "pointer" to the left subtree, in the form of an index to the VpTree array.
- right
- a "pointer" to the right subtree, in the form of an index to the VpTree array.
- ll,lu,rl,ru
- ll and lu are lower bound and upper bound of distance between the node color and all colors in the left subtree. Similarly, rl and ru are for the right subtree.
- mu
- the "radius" of this node. Every color with distance more than mu will goes to right subtree, otherwise it goes to the left subtree.
A VpTree is a pointer the a root of a VP (Vintage Point) tree data structure, which is implemented as an array of 256 VpNode. In Dali, VpTrees are used to quickly find the closest color in a colormap to a given R,G,B color.
typedef struct VpNode *VpTree;
Return code from various color hash table primitives.
#define DVM_COLOR_HASH_TABLE_OK 0
#define DVM_COLOR_HASH_TABLE_FULL -1
#define DVM_COLOR_NOT_FOUND -2
void RgbToY(ByteImage *r, ByteImage *g, ByteImage *b, ByteImage *y)
Given ByteImages r, g and b (they must have same dimensions), convert them to gray-scale and store the result in ByteImage y
void RgbToYuv444(ByteImage *r, ByteImage *g, ByteImage *b, ByteImage *y, ByteImage *u, ByteImage *v)
void YuvToRgb444(ByteImage *y, ByteImage *u, ByteImage *v, ByteImage *r, ByteImage *g, ByteImage *b)
Given ByteImages r, g, b and y, u, v, these functions convert between the two color spaces using 4:4:4 sampling (i.e., all buffers must have the same dimensions).
void RgbToYuv422(ByteImage *r, ByteImage *g, ByteImage *b, ByteImage *y, ByteImage *u, ByteImage *v)
void YuvToRgb422(ByteImage *y, ByteImage *u, ByteImage *v, ByteImage *r, ByteImage *g, ByteImage *b)
Given ByteImages r, g, b and y, u, v, these functions convert between the two color spaces using 4:2:2 sampling (i.e., the r, g, b, and y must have the same dimensions, u and v must have the same height and half the width of y).
void RgbToYuv411(ByteImage *r, ByteImage *g, ByteImage *b, ByteImage *y, ByteImage *u, ByteImage *v)
void YuvToRgb411(ByteImage *y, ByteImage *u, ByteImage *v, ByteImage *r, ByteImage *g, ByteImage *b)
Given ByteImages r, g, b and y, u, v, these functions convert between the two color spaces using 4:1:1 sampling (i.e., the r, g, b, and y must have the same dimensions, u and v must have the same height and one fourth the width of y).
void RgbToYuv420(ByteImage *r, ByteImage *g, ByteImage *b, ByteImage *y, ByteImage *u, ByteImage *v)
void YuvToRgb420(ByteImage *y, ByteImage *u, ByteImage *v, ByteImage *r, ByteImage *g, ByteImage *b)
Given ByteImages r, g, b and y, u, v, these functions convert between the two color spaces using 4:2:0 sampling (i.e., the r, g, b, and y must have the same dimensions, u and v must have half the height and half the width of y).
ColorHashTable* ColorHashTableNew(int bits)
Allocates a new ColorHashTable of size 2^(bits) and returns a handle to it.
void ColorHashTableClear(ColorHashTable *table)
Initializes the ColorHashTable table to empty. This should be done before inserting elements into table.
void ColorHashTableFree(ColorHashTable *table)
Deallocates the ColorHashTable table
#define ColorHashTableGetSize(x) (x)->size
Returns the allocated size of the ColorHashTable table.
#define ColorHashTableGetNumOfEntry(x) (x)->numOfEntry
Returns the number of entries in the ColorHashTable table.
VpNode* VpTreeNew( );
Allocates a Vptree and returns a pointer to the tree.
void VpTreeInit(ImageMap *rmap, ImageMap *gmap, ImageMap *bmap, VpNode *tree);
Initializes the Vptree tree with data from ImageMaps rmap, gmap and bmap.
void VpTreeFree(VpNode *tree);
Deallocates the Vptree tree.
void RgbTo256(ByteImage *r, ByteImage *g, ByteImage *b, ColorHashTable *table, ImageMap *rmap, ImageMap *gmap, ImageMap *bmap)
Given three ByteImages r, g, b and a ColorHashTable table of size 32678, perform median cut algorithm and produce 256 colors that are closest to the original colors in r, g and b. These 256 colors are stored in three ImageMaps rmap, gmap, and bmap. The ColorHashTable must be emptied before calling this function, and it will be modified by this primitive. Note that this function does not find the mappings from the original colors to the quantized colors.
void RgbQuantWithHashTable(ByteImage *r, ByteImage *g, ByteImage *b, ColorHashTable *table, ImageMap *rmap, ImageMap *gmap, ImageMap *bmap, ByteImage *out)
For each color that appears in ByteImages r, g, b, find the color closest to it from the 256 colors available in rmap, gmap and bmap by comparing the distances one by one. The mappings is stored in ByteImage out, where value v at position (x,y) means that the color from r, g, b at (x,y) is closest to the color at position v from rmap, gmap and bmap. The ColorHashTable is used as a cache to store previously calculated mappings. It must be emptied before calling this function, and it will be modified by this primitive. Typically this is called after a color reduction primitives such as RgbTo256().
void RgbQuantWithVpTree(ByteImage *r, ByteImage *g, ByteImage *b, VpNode *tree, ColorHashTable *table, ImageMap *rmap, ImageMap *gmap, ImageMap *bmap, ByteImage *out)
This is similar to RgbQuantWithHashTable. The difference is that it uses a VpTree data sturcture to find the closest color instead of comparing the distance one by one. The VpTree should be initialized using the 256 colors from rmap, gmap and bmap before calling this function. The ColorHashTable is used as a cache to store previously probed mappings. This function is generally faster than RgbQuantWithHashTable if the images are large, because the overhead in tree creation is offset by the gain in probing time. Typically this is called after a color reduction primitives such as RgbTo256(). VpTreeInit() must be called before this function.
ColorHashTableAdd(ColorHashTable *table, unsigned char r, unsigned char g, unsigned char b, int v)
Adds an entry with key=(r,g,b) and value=v to the hash table. It searches for an existing key (r,g,b). If found, it will overwrites the existing value with the v. Otherwise, it will fill the first empty slots in the hash table with (r,g,b) and v.
Returns DVM_COLOR_HASH_TABLE_OK if addition is successful, or an entry with key (r,g,b) already exists. Otherwise returns DVM_COLOR_HASH_TABLE_FULL.
ColorHashTableAddAt(ColorHashTable *table, int index, unsigned char r, unsigned char g, unsigned char b, int value)
Similar to ColorHashTableAdd except it always adds at location index (overwriting the exisiting entry) and returns DVM_COLOR_HASH_TABLE_OK.
ColorHashTableFind(ColorHashTable *table, unsigned char r, unsigned char g, unsigned char b, int *i, int *v)
Finds the entry with key (r, g, b), sets v to its value and sets i to the index of the array that holds the entry.
Returns DVM_COLOR_HASH_TABLE_OK if the entry is found. DVM_COLOR_HASH_TABLE_NOT_FOUND is returned if no such entry exists, but an empty slots exists in the table. DVM_COLOR_HASH_TABLE_FULL is returned if no such entry exists, but the table is full.
ColorHashTableSet(ColorHashTable *table, index, int value)
Sets the table entry at location index to the value value. Don't care what the key is.
ColorHashTablePackSelf (ColorHashTable *table)
Shifts all non-empty entries to the beginning of the hash table. This destroys the "hash" properties of the hash table and the table can no longer be used for lookups. However this is useful when we want to use the hash table as a normal array (e.g. to scan through all the colors).
VpTreeFind (VpTree tree, ImageMap *rmap, ImageMap *gmap, ImageMap *bmap, unsigned char r, unsigned char g, unsigned char b)
Search for color (r, g, b) in the VpTree tree. Returns the index to the color in the colormap rmap, gmap and bmap that is the closest color to (r, g, b).
Last updated : Saturday, November 14, 1998, 07:50 PM