八叉树颜色量化算法c实现

以下是八叉树颜色量化算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_COLOR 256
#define MAX_LEVEL 8

typedef struct {
    unsigned char r, g, b;
} RGB;

typedef struct node {
    int leaf;
    int pixel_count;
    int red_sum, green_sum, blue_sum;
    struct node *children[8];
} Node;

int leaf_count = 0;
Node *root = NULL;

int get_color_index(RGB color, int level) {
    int index = 0;
    if (color.r & (1 << level)) {
        index |= 4;
    }
    if (color.g & (1 << level)) {
        index |= 2;
    }
    if (color.b & (1 << level)) {
        index |= 1;
    }
    return index;
}

void add_color(RGB color) {
    Node *node = root;
    int level;
    for (level = MAX_LEVEL - 1; level >= 0; level--) {
        int index = get_color_index(color, level);
        if (!node->children[index]) {
            node->children[index] = (Node *)malloc(sizeof(Node));
            memset(node->children[index], 0, sizeof(Node));
            node->leaf = 0;
        }
        node = node->children[index];
        node->pixel_count++;
        node->red_sum += color.r;
        node->green_sum += color.g;
        node->blue_sum += color.b;
    }
    node->leaf = 1;
    leaf_count++;
}

void reduce_tree(Node *node, RGB *palette, int *index) {
    int i;
    if (node->leaf) {
        palette[*index].r = node->red_sum / node->pixel_count;
        palette[*index].g = node->green_sum / node->pixel_count;
        palette[*index].b = node->blue_sum / node->pixel_count;
        (*index)++;
    } else {
        for (i = 0; i < 8; i++) {
            if (node->children[i]) {
                reduce_tree(node->children[i], palette, index);
            }
        }
    }
}

void free_tree(Node *node) {
    int i;
    for (i = 0; i < 8; i++) {
        if (node->children[i]) {
            free_tree(node->children[i]);
        }
    }
    free(node);
}

void quantize_image(RGB *image, int width, int height, RGB *palette, int color_count) {
    int i, j;
    root = (Node *)malloc(sizeof(Node));
    memset(root, 0, sizeof(Node));
    leaf_count = 0;
    for (i = 0; i < height; i++) {
        for (j = 0; j < width; j++) {
            add_color(image[i * width + j]);
        }
    }
    int palette_index = 0;
    reduce_tree(root, palette, &palette_index);
    free_tree(root);
}

int main() {
    RGB image[] = {
        {255, 0, 0}, {0, 255, 0}, {0, 0, 255},
        {255, 255, 0}, {255, 0, 255}, {0, 255, 255},
        {128, 0, 0}, {0, 128, 0}, {0, 0, 128},
        {128, 128, 0}, {128, 0, 128}, {0, 128, 128},
        {255, 255, 255}, {128, 128, 128}, {0, 0, 0}
    };
    int width = 3;
    int height = 5;
    RGB palette[MAX_COLOR];
    int color_count = 8;
    quantize_image(image, width, height, palette, color_count);
    int i;
    for (i = 0; i < color_count; i++) {
        printf("Palette color %d: %d %d %d\n", i, palette[i].r, palette[i].g, palette[i].b);
    }
    return 0;
}