K-Means 颜色聚类算法开发记录
📋 目录
📖 项目概述
项目目标
实现一个完整的 K-Means 聚类算法，用于从图片中提取主要颜色，并在终端中可视化显示压缩后的图片。
技术栈
- 语言: C 语言 (C11 标准)
- 图片处理: stb_image.h (单头文件库)
- 编译工具: GCC + Makefile
- 可视化: ANSI 转义序列（24位真彩色）
🛠️ 开发环境准备
1. 安装必要的工具
# 安装 GCC 编译器
sudo apt-get install gcc make
# 验证安装
gcc --version
make --version
2. 下载图片处理库
# 创建 include 目录
mkdir -p include
# 下载 stb_image.h（单头文件图片加载库）
curl -o include/stb_image.h https://raw.githubusercontent.com/nothings/stb/master/stb_image.h
3. 项目目录结构
K-means/
├── src/ # 源代码
│ ├── kmeans.h # 算法头文件
│ ├── kmeans.c # 算法实现
│ ├── image_loader.h # 图片加载头文件
│ ├── image_loader.c # 图片加载实现
│ └── main.c # 主程序
├── include/ # 第三方库
│ └── stb_image.h # 图片加载库
├── images/ # 输入图片
├── output/ # 输出目录
├── obj/ # 编译中间文件
├── bin/ # 可执行文件
├── Makefile # 编译配置
└── README.md # 使用文档
🧠 算法原理
K-Means 算法简介
K-Means 是一种无监督学习聚类算法，用于将数据分成 K 个簇。在我们的应用中：
- 数据点: 图片中的每个像素（RGB 颜色值）
- 目标: 找到 K 个"代表颜色"（质心），使得所有像素都能被分配到最接近的代表颜色
- 距离度量: 欧几里得距离（RGB 空间中的颜色距离）
算法流程
1. 初始化：随机选择 K 个像素作为初始质心
2. 迭代直到收敛：
a. 分配阶段：将每个像素分配给最近的质心
b. 更新阶段：重新计算每个簇的质心（平均值）
c. 判断收敛：如果质心移动距离 < 阈值，停止迭代
3. 输出：K 个主颜色（质心）
数学公式
距离计算（欧几里得距离）：
distance = √[(r₁-r₂)² + (g₁-g₂)² + (b₁-b₂)²]
质心更新：
centroid_r = (所有簇内像素的 r 值之和) / (簇内像素数量)
centroid_g = (所有簇内像素的 g 值之和) / (簇内像素数量)
centroid_b = (所有簇内像素的 b 值之和) / (簇内像素数量)
🚀 实现步骤
第一步：定义数据结构
文件: src/kmeans.h
// 颜色结构体（RGB）
typedef struct {
unsigned char r, g, b; // 每个通道 0-255
} RgbaColor;
// 图片结构体
typedef struct {
RgbaColor* pixels; // 像素数组
unsigned int width; // 宽度
unsigned int height; // 高度
} Image;
设计要点：
- 使用
unsigned char存储 RGB 值（0-255） pixels是一维数组，按行存储：pixels[y * width + x]
第二步：实现距离计算函数
文件: src/kmeans.c
double calc_dist(const RgbaColor* c1, const RgbaColor* c2) {
double dr = (double)c1->r - (double)c2->r;
double dg = (double)c1->g - (double)c2->g;
double db = (double)c1->b - (double)c2->b;
return sqrt(dr * dr + dg * dg + db * db);
}
关键点：
- 必须转换为
double进行计算，避免溢出 - 使用
sqrt()需要链接数学库-lm
第三步：实现质心初始化
void init_centroids(const Image* image, RgbaColor* centroids, unsigned int k) {
srand(time(NULL)); // 设置随机种子
for (unsigned int i = 0; i < k; i++) {
unsigned int idx = rand() % (image->width * image->height);
centroids[i] = image->pixels[idx]; // 从图片中随机选择像素
}
}
设计选择：
- 使用
time(NULL)作为随机种子，确保每次运行结果不同 - 从图片中随机选择像素，而不是随机生成颜色（更符合实际分布）
第四步：实现核心 K-Means 算法
这是最复杂的部分，分为两个阶段：
阶段 1：分配像素到最近的质心
// 对每个像素
for (unsigned int i = 0; i < total; i++) {
double min_dist = 1e30; // 初始化为很大的值
unsigned int best = 0;
// 找到最近的质心
for (unsigned int c = 0; c < k; c++) {
double dist = calc_dist(&image->pixels[i], ¢roids[c]);
if (dist < min_dist) {
min_dist = dist;
best = c;
}
}
labels[i] = best; // 记录像素属于哪个簇
// 累加 RGB 值（用于后续计算平均值）
sum_r[best] += image->pixels[i].r;
sum_g[best] += image->pixels[i].g;
sum_b[best] += image->pixels[i].b;
cluster_sizes[best]++;
}
关键点：
- 使用
unsigned int累加 RGB 值，避免unsigned char溢出 - 同时记录每个簇的大小，用于计算平均值
阶段 2：更新质心
// 对每个簇
for (unsigned int c = 0; c < k; c++) {
if (cluster_sizes[c] == 0) {
// 空簇处理：重新随机初始化
unsigned int idx = rand() % total;
centroids[c] = image->pixels[idx];
continue;
}
// 计算新的质心（平均值）
centroids[c].r = (unsigned char)(sum_r[c] / cluster_sizes[c]);
centroids[c].g = (unsigned char)(sum_g[c] / cluster_sizes[c]);
centroids[c].b = (unsigned char)(sum_b[c] / cluster_sizes[c]);
// 判断是否收敛
if (calc_dist(&old, ¢roids[c]) > threshold) {
settled = 0; // 未收敛
}
}
重要细节：
- 空簇处理：如果某个簇没有像素，重新随机初始化
- 类型转换：除法结果转换为
unsigned char - 收敛判断：质心移动距离小于阈值则认为收敛
第五步：实现图片加载
文件: src/image_loader.c
#define STB_IMAGE_IMPLEMENTATION
#include "../include/stb_image.h"
int load_image(const char* filename, Image* image) {
int width, height, channels;
unsigned char* data = stbi_load(filename, &width, &height, &channels, 3);
if (!data) {
fprintf(stderr, "无法加载图片: %s\n", filename);
return -1;
}
// 分配内存
unsigned int total = width * height;
image->pixels = malloc(sizeof(RgbaColor) * total);
// 转换格式：stb_image 返回的是 RGBRGB... 格式
for (unsigned int i = 0; i < total; i++) {
image->pixels[i].r = data[i * 3 + 0];
image->pixels[i].g = data[i * 3 + 1];
image->pixels[i].b = data[i * 3 + 2];
}
image->width = width;
image->height = height;
stbi_image_free(data); // 释放 stb_image 分配的内存
return 0;
}
注意事项：
STB_IMAGE_IMPLEMENTATION必须在包含头文件之前定义stbi_load()返回的数据格式是RGBRGB...，需要转换- 必须调用
stbi_image_free()释放内存
第六步：实现压缩图片生成
在 kmeans_with_compression() 函数中，算法完成后：
// 生成压缩图片：用主颜色替换原图
compressed->width = image->width;
compressed->height = image->height;
compressed->pixels = malloc(sizeof(RgbaColor) * total);
// 用对应的主颜色替换每个像素
for (unsigned int i = 0; i < total; i++) {
compressed->pixels[i] = centroids[labels[i]];
}
原理：每个像素被替换为它所属簇的质心颜色。
第七步：实现终端可视化
文件: src/main.c
void print_compressed_image(const Image* compressed,
unsigned int max_width,
unsigned int max_height) {
// 计算缩放比例
double scale_x = (double)max_width / compressed->width;
double scale_y = (double)max_height / compressed->height;
double scale = scale_x < scale_y ? scale_x : scale_y;
unsigned int display_width = (unsigned int)(compressed->width * scale);
unsigned int display_height = (unsigned int)(compressed->height * scale);
// 打印图片
for (unsigned int y = 0; y < display_height; y++) {
for (unsigned int x = 0; x < display_width; x++) {
// 计算原图中对应的像素位置
unsigned int orig_x = (unsigned int)(x / scale);
unsigned int orig_y = (unsigned int)(y / scale);
unsigned int idx = orig_y * compressed->width + orig_x;
const RgbaColor* color = &compressed->pixels[idx];
// 使用 ANSI 转义序列设置背景色
printf("\033[48;2;%u;%u;%um \033[0m",
color->r, color->g, color->b);
}
printf("\n");
}
}
ANSI 转义序列说明：
\033[48;2;r;g;bm: 设置背景色（24位真彩色）\033[0m: 重置颜色- 打印两个空格形成颜色块（因为终端字符高大于宽）
💻 核心代码解析
内存管理
// 分配内存
RgbaColor* centroids = malloc(sizeof(RgbaColor) * k);
unsigned int* sum_r = malloc(sizeof(unsigned int) * k);
// ... 其他分配
// 检查分配是否成功
if (!centroids || !sum_r || ...) {
fprintf(stderr, "内存分配失败\n");
// 清理已分配的内存
if (centroids) free(centroids);
// ...
return NULL;
}
// 使用完毕后释放
free(centroids);
free(sum_r);
最佳实践：
- 每次
malloc()后检查返回值 - 分配失败时清理已分配的内存
- 使用完毕后立即释放，避免内存泄漏
避免整数溢出
// ❌ 错误：使用 unsigned char 累加会溢出
unsigned char sum = 0;
for (int i = 0; i < 1000; i++) {
sum += 255; // 溢出！
}
// ✅ 正确：使用更大的数据类型
unsigned int sum_r = 0;
for (unsigned int i = 0; i < total; i++) {
sum_r += image->pixels[i].r; // 不会溢出
}
centroid.r = (unsigned char)(sum_r / cluster_size); // 最后转换
空簇处理
if (cluster_sizes[c] == 0) {
// 空簇：重新随机初始化
unsigned int idx = rand() % total;
centroids[c] = image->pixels[idx];
continue;
}
为什么需要处理空簇？
- 如果某个质心初始化在"偏远"位置，可能没有像素被分配给它
- 空簇会导致除零错误
- 重新初始化可以确保所有簇都有像素
🎨 功能扩展
1. 保存压缩后的图片
可以添加保存功能，将压缩后的图片保存为文件：
// 需要添加 stb_image_write.h
#define STB_IMAGE_WRITE_IMPLEMENTATION
#include "../include/stb_image_write.h"
void save_compressed_image(const Image* compressed, const char* filename) {
unsigned char* data = malloc(compressed->width * compressed->height * 3);
// 转换格式
for (unsigned int i = 0; i < compressed->width * compressed->height; i++) {
data[i * 3 + 0] = compressed->pixels[i].r;
data[i * 3 + 1] = compressed->pixels[i].g;
data[i * 3 + 2] = compressed->pixels[i].b;
}
stbi_write_jpg(filename, compressed->width, compressed->height, 3, data, 90);
free(data);
}
2. K-Means++ 初始化
更智能的初始化方法，可以避免随机初始化的问题：
void init_centroids_plusplus(const Image* image, RgbaColor* centroids, unsigned int k) {
srand(time(NULL));
// 第一个质心随机选择
unsigned int idx = rand() % (image->width * image->height);
centroids[0] = image->pixels[idx];
// 后续质心选择距离已选质心最远的点
for (unsigned int i = 1; i < k; i++) {
double max_min_dist = 0;
unsigned int best_idx = 0;
for (unsigned int j = 0; j < image->width * image->height; j++) {
double min_dist = 1e30;
// 找到到已选质心的最小距离
for (unsigned int c = 0; c < i; c++) {
double dist = calc_dist(&image->pixels[j], ¢roids[c]);
if (dist < min_dist) {
min_dist = dist;
}
}
// 选择最小距离最大的点
if (min_dist > max_min_dist) {
max_min_dist = min_dist;
best_idx = j;
}
}
centroids[i] = image->pixels[best_idx];
}
}
3. 多线程优化
使用 OpenMP 并行计算距离：
#include <omp.h>
// 在分配阶段使用并行
#pragma omp parallel for
for (unsigned int i = 0; i < total; i++) {
// ... 距离计算代码
}
编译时添加 -fopenmp 选项。
🎯 应用场景
1. 图片主色调提取
./bin/kmeans image.jpg 5
提取图片的 5 种主要颜色，用于：
- 设计配色方案
- 图片主题分析
- 颜色统计
2. 图片压缩（颜色量化）
将图片压缩为只使用 K 种颜色：
- 减少文件大小
- 创建艺术效果
- GIF 调色板生成
3. 图片分割
根据颜色聚类结果进行图片分割：
- 前景/背景分离
- 物体识别
- 区域标记
4. 数据可视化
在终端中直接查看图片效果，无需打开图片查看器。
❓ 常见问题与解决方案
Q1: 编译错误 "undefined reference to sqrt"
原因: 没有链接数学库
解决: 在 Makefile 中添加 -lm：
LDFLAGS = -lm
Q2: 程序运行很慢
可能原因:
- 图片太大
- K 值太大
- 迭代次数太多
解决方案:
// 1. 缩小图片（在加载时）
// 2. 减小 K 值（如从 10 改为 5）
// 3. 增加收敛阈值（如从 1.0 改为 2.0）
Q3: 提取的颜色都是黑色或白色
可能原因:
- 图片本身颜色单一
- 算法未正确收敛
- 初始化问题
解决方案:
// 1. 检查图片是否正常加载
// 2. 增加最大迭代次数
// 3. 使用 K-Means++ 初始化
// 4. 减小收敛阈值
Q4: 内存不足
原因: 图片太大，内存分配失败
解决方案:
// 1. 使用较小的图片
// 2. 在加载时缩放图片
// 3. 检查系统可用内存
Q5: 终端看不到颜色
原因: 终端不支持 24 位真彩色
解决方案:
- 使用支持真彩色的终端（GNOME Terminal, Konsole, iTerm2）
- 检查终端设置
- 使用 RGB 和十六进制值作为替代
📊 性能优化建议
1. 提前退出
if (settled) {
printf("迭代 %u 次后收敛\n", iter + 1);
break; // 提前退出，节省时间
}
2. 减少重复计算
// 缓存距离计算结果（如果内存允许）
double* distances = malloc(sizeof(double) * total * k);
3. 使用 SIMD 指令
使用 SIMD 指令集加速距离计算（需要特定 CPU 支持）。
4. 多线程并行
使用 OpenMP 或 pthread 并行处理像素分配。
📝 开发总结
关键学习点
- 算法理解: K-Means 的核心是迭代优化
- 内存管理: C 语言需要手动管理内存，注意分配和释放
- 类型转换: 注意整数溢出，使用合适的数据类型
- 错误处理: 检查所有可能失败的操作（内存分配、文件加载等）
- 可视化: ANSI 转义序列可以实现丰富的终端输出
下一步改进方向
- ✅ 实现基础 K-Means 算法
- ✅ 添加图片加载功能
- ✅ 实现终端可视化
- 🔄 添加 K-Means++ 初始化
- 🔄 实现图片保存功能
- 🔄 添加多线程支持
- 🔄 优化性能（SIMD、缓存等）
🎓 参考资料
祝你开发顺利！如有问题，欢迎查阅代码注释或提出 Issue。
评论