从GESP考题到实际项目：手把手用C++实现一个简易的图片调色板压缩工具

从GESP考题到实战项目用C打造16色图像压缩工具项目背景与核心思路去年参加GESP四级考试时那道关于图像压缩的题目让我印象深刻——它要求将256级灰阶的图像压缩到16色。当时只是当作算法题来解但后来突然想到为什么不把它变成一个真正的工具呢于是就有了这个项目一个能读取PPM图像文件进行16色压缩并输出调色板和压缩后图像的小工具。这个项目的核心在于颜色量化Color Quantization技术。简单来说就是从数百万种颜色中选出最具代表性的16种颜色然后用这16种颜色来近似表示原图。GESP考题中的统计高频颜色最近邻匹配正是颜色量化的简化版。我们将基于这个思路但会做以下改进支持真实的图像格式PPM而非十六进制字符串优化颜色匹配算法提升视觉效果输出调色板图像以便直观查看颜色分布添加简单的命令行界面1. 环境准备与项目结构1.1 开发环境配置首先确保你的开发环境已经准备好# 对于Ubuntu/Debian sudo apt update sudo apt install build-essential cmake # 对于macOS brew install cmake项目将使用现代C标准C17因此请检查你的编译器版本g --version # 需要7.0以上 clang --version # 需要5.0以上1.2 项目目录结构建议按以下方式组织项目文件image_compressor/ ├── CMakeLists.txt ├── include/ │ ├── color_quantizer.h │ ├── ppm_loader.h │ └── utils.h ├── src/ │ ├── main.cpp │ ├── color_quantizer.cpp │ └── ppm_loader.cpp ├── test/ │ └── test_images/ └── build/2. PPM图像格式解析2.1 PPM文件格式简介PPMPortable Pixmap Format是最简单的图像格式之一特别适合学习图像处理。一个典型的PPM文件如下P3 # 示例注释 4 4 255 255 0 0 0 255 0 0 0 255 255 255 255 255 255 0 255 0 255 0 255 255 0 0 0 ...更多像素数据...关键组成部分P3表示ASCII格式的PPM宽度和高度以像素为单位最大颜色值通常是255像素数据RGB三元组每个值0-2552.2 实现PPM加载器我们创建一个PPMImage类来封装图像数据// include/ppm_loader.h #pragma once #include vector #include string struct RGB { uint8_t r, g, b; RGB() : r(0), g(0), b(0) {} RGB(uint8_t _r, uint8_t _g, uint8_t _b) : r(_r), g(_g), b(_b) {} }; class PPMImage { public: PPMImage(const std::string filename); bool load(); const std::vectorRGB pixels() const { return pixels_; } int width() const { return width_; } int height() const { return height_; } private: std::string filename_; int width_ 0; int height_ 0; int max_color_ 255; std::vectorRGB pixels_; };对应的实现部分需要处理文件读取和解析// src/ppm_loader.cpp #include ppm_loader.h #include fstream #include sstream #include stdexcept PPMImage::PPMImage(const std::string filename) : filename_(filename) {} bool PPMImage::load() { std::ifstream file(filename_); if (!file.is_open()) { throw std::runtime_error(无法打开文件: filename_); } std::string magic_number; file magic_number; if (magic_number ! P3) { throw std::runtime_error(仅支持P3格式的PPM文件); } // 跳过注释行 while (file.peek() #) { file.ignore(1024, \n); } file width_ height_ max_color_; pixels_.resize(width_ * height_); for (int i 0; i width_ * height_; i) { int r, g, b; file r g b; pixels_[i] RGB(r, g, b); } return true; }3. 颜色量化算法实现3.1 频率统计与调色板生成GESP考题中的方法是统计颜色频率并取前16种高频颜色。我们将其扩展为RGB空间// include/color_quantizer.h #pragma once #include vector #include unordered_map #include ppm_loader.h class ColorQuantizer { public: explicit ColorQuantizer(const PPMImage image); void quantize(int palette_size 16); const std::vectorRGB palette() const { return palette_; } const std::vectoruint8_t indices() const { return indices_; } private: struct ColorCount { RGB color; int count; bool operator(const ColorCount other) const { return count other.count; // 降序排序 } }; const PPMImage image_; std::vectorRGB palette_; std::vectoruint8_t indices_; };实现部分// src/color_quantizer.cpp #include color_quantizer.h #include algorithm #include cmath ColorQuantizer::ColorQuantizer(const PPMImage image) : image_(image) {} void ColorQuantizer::quantize(int palette_size) { std::unordered_mapuint32_t, int color_counts; // 统计颜色频率 for (const auto pixel : image_.pixels()) { uint32_t key (pixel.r 16) | (pixel.g 8) | pixel.b; color_counts[key]; } // 转换为vector并排序 std::vectorColorCount sorted_colors; for (const auto pair : color_counts) { uint32_t key pair.first; RGB color{ static_castuint8_t((key 16) 0xFF), static_castuint8_t((key 8) 0xFF), static_castuint8_t(key 0xFF) }; sorted_colors.push_back({color, pair.second}); } std::sort(sorted_colors.begin(), sorted_colors.end()); // 取前palette_size种颜色作为调色板 palette_.clear(); for (size_t i 0; i std::min(sorted_colors.size(), static_castsize_t(palette_size)); i) { palette_.push_back(sorted_colors[i].color); } // 为每个像素找到最近的调色板颜色 indices_.resize(image_.pixels().size()); for (size_t i 0; i image_.pixels().size(); i) { const auto pixel image_.pixels()[i]; int min_dist INT_MAX; uint8_t best_idx 0; for (uint8_t j 0; j palette_.size(); j) { const auto palette_color palette_[j]; int dr pixel.r - palette_color.r; int dg pixel.g - palette_color.g; int db pixel.b - palette_color.b; int dist dr*dr dg*dg db*db; // 使用平方距离避免开方 if (dist min_dist || (dist min_dist j best_idx)) { min_dist dist; best_idx j; } } indices_[i] best_idx; } }3.2 算法优化思路原始算法有几个可以改进的地方颜色距离计算使用更符合人眼感知的CIE76或CIE94颜色空间初始调色板选择可以使用中位切分法或K-means算法获得更好的初始调色板抖动处理添加Floyd-Steinberg抖动可以减少颜色带状伪影这里我们实现一个简单的K-means改进版本void ColorQuantizer::quantize(int palette_size) { // 初始随机选择调色板颜色 palette_.resize(palette_size); std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis(0, image_.pixels().size() - 1); for (int i 0; i palette_size; i) { palette_[i] image_.pixels()[dis(gen)]; } // K-means迭代 std::vectorint cluster_sizes(palette_size, 0); std::vectorRGB cluster_sums(palette_size); std::vectoruint8_t new_indices(image_.pixels().size()); bool changed; int iterations 0; const int max_iterations 10; do { changed false; std::fill(cluster_sizes.begin(), cluster_sizes.end(), 0); std::fill(cluster_sums.begin(), cluster_sums.end(), RGB(0, 0, 0)); // 分配像素到最近的聚类中心 for (size_t i 0; i image_.pixels().size(); i) { const auto pixel image_.pixels()[i]; int min_dist INT_MAX; uint8_t best_idx 0; for (uint8_t j 0; j palette_.size(); j) { const auto palette_color palette_[j]; int dr pixel.r - palette_color.r; int dg pixel.g - palette_color.g; int db pixel.b - palette_color.b; int dist dr*dr dg*dg db*db; if (dist min_dist) { min_dist dist; best_idx j; } } if (new_indices[i] ! best_idx) { new_indices[i] best_idx; changed true; } cluster_sizes[best_idx]; cluster_sums[best_idx].r pixel.r; cluster_sums[best_idx].g pixel.g; cluster_sums[best_idx].b pixel.b; } // 更新聚类中心 for (int i 0; i palette_size; i) { if (cluster_sizes[i] 0) { palette_[i].r cluster_sums[i].r / cluster_sizes[i]; palette_[i].g cluster_sums[i].g / cluster_sizes[i]; palette_[i].b cluster_sums[i].b / cluster_sizes[i]; } } iterations; } while (changed iterations max_iterations); indices_ std::move(new_indices); }4. 结果输出与可视化4.1 保存压缩后的图像我们可以将压缩后的图像保存为新的PPM文件使用调色板中的颜色void save_compressed_image(const std::string filename, const PPMImage original, const ColorQuantizer quantizer) { std::ofstream file(filename); if (!file.is_open()) { throw std::runtime_error(无法创建文件: filename); } file P3\n; file # 压缩图像 - 16色\n; file original.width() original.height() \n; file 255\n; const auto palette quantizer.palette(); const auto indices quantizer.indices(); for (size_t i 0; i indices.size(); i) { const auto color palette[indices[i]]; file static_castint(color.r) static_castint(color.g) static_castint(color.b) \n; } }4.2 生成调色板预览创建一个显示所有调色板颜色的图像void save_palette_preview(const std::string filename, const std::vectorRGB palette) { const int swatch_size 100; const int palette_size static_castint(palette.size()); const int width swatch_size * palette_size; const int height swatch_size; std::ofstream file(filename); if (!file.is_open()) { throw std::runtime_error(无法创建文件: filename); } file P3\n; file # 调色板预览\n; file width height \n; file 255\n; for (int y 0; y height; y) { for (int i 0; i palette_size; i) { const auto color palette[i]; for (int x 0; x swatch_size; x) { file static_castint(color.r) static_castint(color.g) static_castint(color.b) \n; } } } }4.3 主程序实现将各部分组合起来// src/main.cpp #include iostream #include ppm_loader.h #include color_quantizer.h int main(int argc, char* argv[]) { if (argc ! 2) { std::cerr 用法: argv[0] 输入图像.ppm\n; return 1; } try { // 加载原始图像 PPMImage image(argv[1]); if (!image.load()) { std::cerr 图像加载失败\n; return 1; } // 执行颜色量化 ColorQuantizer quantizer(image); quantizer.quantize(16); // 保存结果 std::string base_name argv[1]; size_t dot_pos base_name.find_last_of(.); if (dot_pos ! std::string::npos) { base_name base_name.substr(0, dot_pos); } save_compressed_image(base_name _compressed.ppm, image, quantizer); save_palette_preview(base_name _palette.ppm, quantizer.palette()); std::cout 处理完成:\n; std::cout - 压缩图像: base_name _compressed.ppm\n; std::cout - 调色板: base_name _palette.ppm\n; } catch (const std::exception e) { std::cerr 错误: e.what() \n; return 1; } return 0; }5. 构建与测试5.1 CMake构建配置创建CMakeLists.txt文件cmake_minimum_required(VERSION 3.10) project(image_compressor) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_executable(image_compressor src/main.cpp src/ppm_loader.cpp src/color_quantizer.cpp ) target_include_directories(image_compressor PRIVATE include)构建项目mkdir build cd build cmake .. make5.2 测试图像处理准备一个测试图像如test.ppm然后运行./image_compressor test.ppm比较原始图像、压缩图像和调色板文件类型描述文件大小test.ppm原始图像较大test_compressed.ppm压缩后的16色图像显著减小test_palette.ppm16色调色板预览很小5.3 效果评估与改进第一次运行时可能会发现压缩图像有明显的颜色带状现象。这是颜色量化算法的常见问题。我们可以尝试以下改进增加抖动处理修改颜色匹配算法添加Floyd-Steinberg抖动更好的初始中心选择使用中位切分法而非随机选择自适应调色板大小根据图像复杂度动态调整调色板大小抖动处理实现示例void apply_floyd_steinberg(PPMImage image, const ColorQuantizer quantizer) { const auto palette quantizer.palette(); auto pixels image.pixels(); int width image.width(); int height image.height(); for (int y 0; y height; y) { for (int x 0; x width; x) { int idx y * width x; const auto old_pixel pixels[idx]; const auto new_pixel palette[quantizer.indices()[idx]]; // 计算误差 int err_r old_pixel.r - new_pixel.r; int err_g old_pixel.g - new_pixel.g; int err_b old_pixel.b - new_pixel.b; // 扩散误差到邻近像素 if (x 1 width) { pixels[idx 1].r err_r * 7 / 16; pixels[idx 1].g err_g * 7 / 16; pixels[idx 1].b err_b * 7 / 16; } if (y 1 height) { if (x 0) { pixels[idx width - 1].r err_r * 3 / 16; pixels[idx width - 1].g err_g * 3 / 16; pixels[idx width - 1].b err_b * 3 / 16; } pixels[idx width].r err_r * 5 / 16; pixels[idx width].g err_g * 5 / 16; pixels[idx width].b err_b * 5 / 16; if (x 1 width) { pixels[idx width 1].r err_r * 1 / 16; pixels[idx width 1].g err_g * 1 / 16; pixels[idx width 1].b err_b * 1 / 16; } } } } }