2023年GESP四级图像压缩详解（洛谷B3851题）：从原理到C++实现

2天前比赛题解57

一、算法原理概述

本题目要求实现一个简单的图像压缩算法，核心思想是将256级灰度（00-FF）压缩到16级灰度。通过统计原始图像中各个灰度值的出现频率，选取出现频率最高的16个灰度值作为压缩后的灰度表，然后将每个原始灰度值替换为压缩表中距离最近的灰度值对应的索引（0-F）。

二、完整代码解析（含注释）

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>
#include <sstream>
using namespace std;

// 自定义比较函数，用于灰度值排序
// 首先按出现频率降序排列，频率相同的按灰度值升序排列
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second != b.second ? a.second > b.second : a.first < b.first;
}

int main() {
    int n;  // 图像行数
    cin >> n;
    vector<string> original_lines(n);  // 存储原始图像数据
    map<int, int> freq;  // 灰度值频率统计
    
    // 读取并存储原始数据，同时统计频率
    for (int i = 0; i < n; ++i) {
        cin >> original_lines[i];
        // 每两个字符表示一个16进制灰度值
        for (size_t j = 0; j < original_lines[i].length(); j += 2) {
            string hex = original_lines[i].substr(j, 2);
            int gray = stoi(hex, nullptr, 16);  // 转换为10进制灰度值
            freq[gray]++;  // 统计频率
        }
    }

    // 将频率统计结果转为vector便于排序
    vector<pair<int, int>> gray_freq(freq.begin(), freq.end());
    sort(gray_freq.begin(), gray_freq.end(), cmp);  // 按自定义规则排序
    
    // 选取前16个最高频的灰度值
    vector<int> compressed_gray;
    for (int i = 0; i < 16; ++i) {
        compressed_gray.push_back(gray_freq[i].first);
    }
    
    // 输出压缩后的16级灰度表（16进制格式）
    for (int gray : compressed_gray) {
        cout << hex << uppercase << setw(2) << setfill('0') << gray;
    }
    cout << endl;
    
    // 处理每行数据，进行灰度值替换
    for (const auto& line : original_lines) {
        string compressed_line;
        for (size_t j = 0; j < line.length(); j += 2) {
            string hex = line.substr(j, 2);
            int gray = stoi(hex, nullptr, 16);  // 当前灰度值
            int min_dist = 256;  // 最小距离初始化为最大值
            int best_index = 0;  // 最佳匹配索引
            
            // 在压缩表中寻找距离最近的灰度值
            for (int k = 0; k < 16; ++k) {
                int dist = abs(gray - compressed_gray[k]);
                // 距离更小，或距离相同但索引更小
                if (dist < min_dist || (dist == min_dist && k < best_index)) {
                    min_dist = dist;
                    best_index = k;
                }
            }
            
            // 将索引转换为字符：0-9或A-F
            compressed_line += (best_index < 10) ? char('0' + best_index) 
                                               : char('A' + best_index - 10);
        }
        cout << compressed_line << endl;
    }
    
    return 0;
}