图像压缩 题解

题目分析

本题要求将一幅 256 级灰阶的灰度图像压缩为 16 级灰阶的图像，每个像素的值从 0~255 映射到 0~15。压缩的关键在于：只能保留出现次数最多的 16 种灰阶，其他灰阶则用与之最接近的保留灰阶替代。题目输入规模较小（图像行数最多 20，每行最多 20 个像素），因此即使使用简单的暴力算法也能顺利通过。

主要难点集中在：

1. 十六进制字符串与整数之间的转换；
2. 统计所有灰阶的出现次数；
3. 按照“次数多优先，次数相同灰阶值小优先”的规则选出 16 个保留灰阶；
4. 遍历所有像素，将其映射到距离最近的保留灰阶（距离相同选编号小者）；
5. 按要求格式输出结果。

解题思路

整个算法可以分为以下几个步骤：

1. 输入处理与统计

• 读入整数 n，表示图像有 n 行。
• 逐行读入字符串，每两个字符构成一个像素的十六进制灰阶值。可以写一个函数 trans 将十六进制字符转为 0~15 的整数，再通过 高4位 × 16 + 低4位 得到完整的 0~255 灰阶值。
• 用一个二维数组 image[i][j] 保存原始图像，同时用一个一维数组 his[256] 统计每种灰阶值出现的次数。

2. 选出 16 个保留灰阶

• 我们需要选出出现次数最多的前 16 种灰阶。如果次数相同，则灰阶值小的排在前面。这可以通过循环 16 次实现：
  每次扫描 his 数组，找到当前最大值。因为扫描顺序是从 0 到 255，当出现并列最大值时，先遇到（灰阶值小）的会保留，符合题目要求。
• 将选出的灰阶值依次存入 color[0] ~ color[15]，编号 0~15 就对应了它们的优先级（0 出现次数最多）。同时将选中的灰阶在 his 中标记为 -1，防止重复选择。

3. 压缩映射

• 遍历每个像素的原始灰阶值 c，在 color 数组中找到与其最接近的保留灰阶。“最接近”定义为绝对值之差最小；如果出现相等差值，则选择编号较小的保留灰阶。
• 因为 color 数组中的顺序恰好是编号顺序（0 到 15），我们只需要顺序扫描，记录当前最小差值，只有当遇到严格更小的差值时才更新最近编号。这样就能自动满足“差值相等时选编号较小者”的要求。
• 将每个像素压缩后的编号（0~15）存储到另一个二维数组 cpimg 中。

4. 输出结果

• 第一行输出选定的 16 个灰阶的原始十六进制值，每个灰阶对应两位十六进制字符，共 32 个字符。写一个函数 itrans 将 0~15 的数字转换为十六进制字符，然后分别输出高 4 位和低 4 位。
• 接下来 n 行输出压缩后的图像，每个像素输出一位十六进制数（即压缩后的编号 0~15，直接使用 itrans）。

算法说明

字符与数字的转换

• trans(char a)：判断字符是否 ≤'9'，是则 a - '0'；否则为大写字母 A~F，转换公式为 a - 'A' + 10。
• itrans(int n)：若 n≥10，返回 n - 10 + 'A'；否则返回 n + '0'。

选取保留灰阶

采用贪心选择，每次取当前剩余次数最多的灰阶。由于 n 很小（≤20），而且灰阶只有 256 个，这种 O(16×256) 的做法非常高效。

压缩映射

对每个像素值 c，遍历 16 个保留灰阶 color[i]，计算 abs(c - color[i])。维护当前最小距离 dis 和对应编号 res。因为 i 从小到大，所以在距离相等时不会更新 res，从而保留编号更小的灰阶。

时间复杂度分析

• 输入与统计：图像最多 20×20 = 400 个像素，每个像素处理常数时间，O(像素数)。
• 选择 16 个灰阶：16 次遍历整个 his 数组（256 个元素），O(16×256) = 常数时间。
• 压缩映射：每个像素遍历 16 种保留灰阶，O(400×16) = 常数时间。
• 总体时间复杂度为 O(像素数 + 16×256 + 像素数×16)，在题目给定的小数据范围下可以忽略不计。
  空间复杂度也极低，几个 20×20 的数组和长度为 256 的辅助数组即可。

参考代码及解释

cpp
复制
1#include <iostream>
2#include <cstring>
3using namespace std;
4
5int image[20][20];      // 原始图像灰阶值 0~255
6int cpimg[20][20];      // 压缩后图像编号 0~15
7int his[256];           // 灰阶频率统计
8int color[16];          // 选出的 16 种保留灰阶值
9
10// 十六进制字符 -> 数字
11int trans(char a) {
12    if (a <= '9')
13        return (a - '0');
14    return (a - 'A' + 10);
15}
16
17// 数字 -> 十六进制字符
18char itrans(int n) {
19    if (n >= 10)
20        return (char)(n - 10 + 'A');
21    return (char)(n + '0');
22}
23
24// 压缩映射：找到 c 最近的保留灰阶，返回其编号
25int compress(int c) {
26    int dis = 256, res = -1;
27    for (int i = 0; i < 16; i++) {
28        int d = c - color[i];
29        if (d < 0) d = -d;
30        if (d < dis) {
31            dis = d;
32            res = i;
33        }
34    }
35    return res;
36}
37
38int main() {
39    int N = 0, M = 0;
40    cin >> N;
41
42    // 初始化频率数组
43    for (int i = 0; i < 256; i++)
44        his[i] = 0;
45
46    // 读取图像并统计频率
47    for (int i = 0; i < N; i++) {
48        char line[50];
49        cin >> line;
50        M = strlen(line) / 2;     // 每行像素个数
51        for (int j = 0; j < M; j++) {
52            int c = trans(line[j * 2]) * 16 + trans(line[j * 2 + 1]);
53            image[i][j] = c;
54            his[c]++;
55        }
56    }
57
58    // 选择出现次数最多的 16 个灰阶
59    for (int c = 0; c < 16; c++) {
60        int max = -1, max_id = -1;
61        for (int i = 0; i < 256; i++)
62            if (his[i] > max) {
63                max = his[i];
64                max_id = i;
65            }
66        color[c] = max_id;
67        his[max_id] = -1;   // 标记已选
68    }
69
70    // 将图像映射到 16 级灰阶
71    for (int i = 0; i < N; i++)
72        for (int j = 0; j < M; j++)
73            cpimg[i][j] = compress(image[i][j]);
74
75    // 输出保留的 16 种灰阶（两位十六进制）
76    for (int c = 0; c < 16; c++)
77        cout << itrans(color[c] / 16) << itrans(color[c] % 16);
78    cout << endl;
79
80    // 输出压缩后图像（一位十六进制）
81    for (int i = 0; i < N; i++) {
82        for (int j = 0; j < M; j++)
83            cout << itrans(cpimg[i][j]);
84        cout << endl;
85    }
86    return 0;
87}

代码解释

• 第 18‑21 行：trans 函数将十六进制字符转为对应的数值 0_{15。注意题目保证输入都是大写十六进制字符（A}F）。
• 第 23‑25 行：itrans 函数是 trans 的逆操作，将 0~15 的数值转为 '0'~'F' 的字符。
• 第 28‑36 行：compress 函数进行压缩映射。它线性扫描 color 数组，寻找与给定像素值 c 最接近的保留灰阶，并返回其编号 i。由于只用 < 更新，避免了差值相等时编号较大的灰阶被选中。
• 第 44‑45 行：读入一行的字符串后在内存中连续存放，strlen(line) 得到字符串总长度，除以 2 即为该行像素数。
• 第 47 行：line[j*2] 和 line[j*2+1] 分别是像素灰阶的高四位和低四位的十六进制字符。
• 第 56‑63 行：采用 “擂台法” 找出当前 his 数组中的最大值，max 记录最大频次，max_id 记录对应的灰阶值。取出后立即将 his[max_id] 设为 -1，保证下次循环不会再次选中它。
• 第 72‑73 行：输出保留灰阶时，先输出高 4 位（color[c] / 16），再输出低 4 位（color[c] % 16），每个灰阶占两个十六进制字符。
• 第 77‑81 行：输出压缩后的图像，每个像素用一位十六进制表示其编号即可。

总结

本题属于模拟类题目，没有复杂的数据结构和算法，重点在于细心处理十六进制转换、频率统计后的排序规则，以及最近距离映射时的优先级要求。数据范围很小，即使采用最直接的暴力方法也能在时间限制内完成。在实现时，注意用“只取严格更优”的条件来满足“次数相同时灰阶值小优先”和“距离相同时编号小优先”的规则。