本篇笔记介绍了图像数据的基本表示方法，包括 1 位二值图像、8 位灰度图像、24 位真彩色图像和 8 位索引彩色图像，并详细讲解了抖动技术及颜色查找表（LUT）的构造方法。此外，还介绍了几种常见的图像文件格式，如 GIF、JPEG、BMP 及其他格式，并分析了它们的存储结构和特点。（由 gpt-4o 生成摘要）

1. Basic Data Types

1.1. 1-Bit Images

• 1 位图像(1-Bit image)，也称为 二值图像(binary image) 或 单色图像(monochrome image)。
• 每个像素存储为单个位，通常 0 代表黑色，1 代表白色。
  • 例：对于分辨率为 640 × 480 的单色图像，$\displaystyle{\frac{640 \times 480 \text{ b}}{8 \text{ b/B}} = 38.4 \text{KB}}$，故存储该图需要 38.4KB 的空间。
• 用途：适用于仅包含简单图形和文本的图片。

1.2. 8-Bit Grey-Level Image

• 每个像素用单个 字节(byte) 表示 灰度值(gray value)，范围为 0 到 255。
  • 例：对于分辨率为 640 × 480 的 8 位灰度图像，需要 $\displaystyle{640 \times 480 \text{ B} = 307.2 \text{ KB}}$ 的存储空间。
• 位图(bitmap)：整个图像可以看作是像素值的二维数组，称为位图。
• 位平面(bitplane)：将图像中所有像素的处于同一位位置的比特提取出来，组成一个新的二值图像 (黑白图像) ，就是一个 1 位位平面。
  • 8 位灰度图像可以看作是 8 个 1 位的集合。所有位平面共同构成一个字节，存储 $0 \sim 255$ 之间的灰度值。
• 硬件上，存储图像数组的空间通常由 帧缓存(frame buffer) / 显卡(video card) 提供。

1.2.1. Dithering

• DPI(dot per inch)：每平方英寸上的点数。

为了在 2 级（1-位）打印机上 打印(print) 灰度图像，通常需要用到 抖动(dithering) 技术，这可以将 强度分辨率(intensity resolution) 转换为 空间分辨率(spatial resolution)。

主要策略是用更大的图案（$N \times N$ 的矩阵）替换像素值，使得打印点的数量近似于模拟 半色调打印(halftone printing) 中使用的不同大小的墨水圆盘。一个 $N \times N$ 矩阵可以表示 $N^2 + 1$ 级强度，例如，$2 \times 2$ 图案可以表示五个强度级别：

最直观的思路是根据上面的强度级别，用 $n \times n$ 点矩阵替换每个像素（如果强度 > 抖动矩阵条目，则在该条目位置打印一个“开”点）。以使用 $2 \times 2$ 为例，由于 $256>2\times 2+1$，我们需要先把强度划分成 $5$ 个级别，分别对应上面的 $4,3,2,1,0$ 的矩阵，逐像素进行替换即可。需要注意，这样得到的图片的大小会增大 $N \times N$ 倍，这在抖动矩阵较大时不够优秀。

有序抖动(ordered dithering) 算法通过引入一个抖动矩阵，打印图片时对于每个像素点进行处理，仅当抖动矩阵对应位置的数值大于强度时，才打印，这样就不需要额外的存储空间（相当于是把比较的步骤移到了打印时进行）。下图是 $5 \times 5$ 的标准抖动矩阵，和灰度值为 15 时的打印效果：

1.3. 24-Bit Color Image

• 每个像素使用三个字节：分别代表 红(red, R)、绿(green, G)、蓝(blue, B) 三个颜色分量。
  • 每个颜色分量的值范围从 0 到 255，即每个像素是三个颜色分量的灰度值的组合。
  • 支持 $256 \times 256 \times 256 = 16,777,216$ 种颜色，通常称为真彩色。
• 许多 24 位彩色图像实际上存储为 32 位图像，通过引入一个额外的 Alpha 通道 值指示特殊效果信息，例如 透明度(transparency flag)。
  • 半透明(Semi-transparency) 图像颜色计算公式：
    $$\text{半透明图像颜色} = \text{源图像颜色} × (100\% - \text{透明度}) + \text{背景图像颜色} × \text{透明度}$$

1.4. 8-Bit Color Image

• 8 位彩色图像(8-Bit Color Image) 也称为 256 色图像(256-colors image)。
• 使用 颜色查找表(Color Lookup table)（也称为 调色板(palette)）的思想——图像存储的是一组字节，而不是真实的颜色值。字节值是颜色表的索引，索引指向 3 字节的颜色值。
  • 通常选择最重要的 256 种颜色。
  • 这些颜色可以通过聚类 $256 \times 256 \times 256$ 种颜色生成，例如使用 中位切割算法(Median-cut Algorithm)。

1.4.1. To Devise a Color Lookup Table

最简单的思想是根据按 RGB 分配，人眼对 红色(R) 和 绿色(G) 比对 蓝色(B) 更敏感，可以为 R 分配 3 位，G 分配 3 位，B 分配 2 位，总共 8 位。通过截断处理，如 R 和 G 从 8 位缩小到 3 位，通过将其除以 32（$256/8=32$）然后截断得到 3 位的索引值。这是一种均匀的颜色分配方式。

聚类(clustering) 方法可以帮我们找到更合适的 LUT，常见的聚类方法有 K-Means 和 Median Cut，这里主要介绍 中值切割(Median Cut) 算法：循环 8 轮，每轮根据 R,G,B 三个维度上的颜色范围（最大值 $-$ 最小值）选择范围跨度最大的进行切分，通过从这一维度的中位数位置切开，进行中值切割，并递归这一过程。

中值切割算法相对于 K-Means 速度更快但是质量略差，也可以结合两者以获得高效且高质量的 LUT 算法。

2. Popular Image File Format

2.1. GIF Image

• 图形交换格式(Graphics Interchange Format, GIF)。
• 由 UNISYS 公司 和 CompuServe 公司 于 1987 年发明，最初用于通过电话线传输图形图像。现在不属于任何特定应用程序。
• GIF 图片使用 LZW(Lempel-Ziv-Welch) 压缩算法。
  • 是一种 无损压缩(lossless compression) 算法。
  • 对于连续色调图像，压缩率约为 50%。
• GIF 最多支持于 8 位（256 色）图像。
• 以 隔行扫描(interlacing) 的方式存储
  • 可以通过四遍扫描 渐进显示(gradually display) 图像。
• GIF89a 支持动画和 透明色(transparent color)。
• GIF 文件格式：

2.2. JPEG Image

• 联合图像专家组(Joint Photographic Experts Group, JPEG)
• 利用人类视觉系统的一些局限性，JPEG 可以通过 有损压缩(lossy compression) 实现高压缩率。
• 允许用户设置所需的 质量级别(quality level) 或 压缩比(compression ratio)（输入大小除以输出大小）。

2.3. BMP Image

• 由 Microsoft 创建，作为 Windows 的主要图像格式，可以存储 1 位、4 位、8 位以及真彩色数据。
• BMP 文件有三种存储形式：
  • 原始数据，不压缩(Original data without compression)，最流行。
  • 游程编码(Run Length Encoding, RLE)：用于 8 位图像（256 色）BI-RLE8。
  • RLE：用于 4 位图像(16 色)BI_RLE4。
• BMP 文件由四个部分组成：
  • 文件头(File Head)：类型和其他信息。
  • 位图信息头(Information head of bitmap)：长度、宽度、压缩算法等。
  • 调色板(Palette)：颜色 LUT 表格，24 位真彩色图像没有调色板。
  • 图像数据(Image Data)：真彩色图像存储 (R,G,B) 三个分量，带调色板的图像存储调色板的索引。
• BMP 文件格式：

2.4. Other Image Formats

• PNG(Portable Network Graphics) - 便携式网络图形
• TIFF(Tagged Image File Format) - 标签图像文件格式
• EXIF(Exchangeable Image File Format) - 可交换图像文件格式
• ……