# taichi-dither

**Repository Path**: Yingyi1048596/taichi-dither

## Basic Information

- **Project Name**: taichi-dither
- **Description**: 基于Taichi加速的抖动算法图像处理工具，支持多种抖动算法、多色值处理和GPU加速。
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2025-05-12
- **Last Updated**: 2025-05-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 图像仿色处理工具（Taichi Dither）

基于Taichi加速的抖动算法图像处理工具，支持多种抖动算法、多色值处理和GPU加速。

## 目录

- [图像仿色处理工具（Taichi Dither）](#图像仿色处理工具taichi-dither)
  - [目录](#目录)
  - [简介](#简介)
  - [抖动算法原理](#抖动算法原理)
    - [1. 基本抖动 (Basic Dithering)](#1-基本抖动-basic-dithering)
    - [2. Floyd-Steinberg 抖动](#2-floyd-steinberg-抖动)
    - [3. Bayer 抖动](#3-bayer-抖动)
    - [4. Atkinson 抖动](#4-atkinson-抖动)
  - [安装](#安装)
  - [使用方法](#使用方法)
    - [基本使用](#基本使用)
    - [高级选项](#高级选项)
    - [示例代码](#示例代码)
  - [性能测试](#性能测试)
    - [测试方法](#测试方法)
    - [测试参数](#测试参数)
    - [测试结果解析](#测试结果解析)
  - [常见问题](#常见问题)
  - [参考资料](#参考资料)

## 简介

抖动（Dithering）是一种将高位色彩图像转换为低位色彩图像的技术，通过特定的像素排列方式，在减少色彩数量的同时保留图像的视觉效果。本工具基于Python和Taichi实现了多种经典抖动算法，并支持GPU加速。

主要特性：
- ✅ 支持多种经典抖动算法：基本抖动、Floyd-Steinberg抖动、Bayer抖动和Atkinson抖动
- ✅ 支持灰度和彩色图像处理
- ✅ 支持自定义色值数量，从黑白二值到多色值
- ✅ 基于Taichi实现GPU加速，提高处理速度
- ✅ 支持调整输出图像大小，优化处理效率
- ✅ 提供完整的性能测试和比较工具
- ✅ 内置核心计算缓存机制，优化重复处理性能
- ✅ 工厂模式接口设计，便于扩展新算法

**尤其注意的是，由于误差扩散的计算依赖于计算顺序，在GPU并行化加速的时候扩散计算的顺序会混乱，因此所得效果与CPU计算所得差异较大，不会产生规律的模式。**

## 抖动算法原理

抖动算法的核心思想是通过误差扩散（Error Diffusion）技术将量化误差分散到相邻像素，以在全局上保留原始图像的亮度分布和视觉效果。

### 1. 基本抖动 (Basic Dithering)

最简单的抖动算法，将当前像素的量化误差全部传递给右侧相邻像素。

算法步骤：
1. 对每个像素，找到调色板中最接近的颜色
2. 计算量化误差（原始值 - 新值）
3. 将误差全部添加到右侧像素

优点：实现简单
缺点：容易产生水平条纹

```python
for i in range(height):
    for j in range(width):
        old_pixel = image[i, j]
        new_pixel = find_closest_palette_color(old_pixel)
        image[i, j] = new_pixel
        error = old_pixel - new_pixel
        
        if j + 1 < width:
            image[i, j + 1] += error
```

### 2. Floyd-Steinberg 抖动

最经典的抖动算法之一，将量化误差按特定比例分配给周围像素。

误差扩散模式：

$$
\begin{matrix}
    & X & \frac{7}{16} \\
\frac{3}{16} & \frac{5}{16} & \frac{1}{16}
\end{matrix}
$$

算法步骤：
1. 对每个像素，找到调色板中最接近的颜色
2. 计算量化误差
3. 按照上述比例将误差分配给周围像素

优点：效果自然，适用于多种图像类型
缺点：可能产生特定方向的纹理

```python
for i in range(height):
    for j in range(width):
        old_pixel = image[i, j]
        new_pixel = find_closest_palette_color(old_pixel)
        image[i, j] = new_pixel
        error = old_pixel - new_pixel
        
        if j + 1 < width:
            image[i, j + 1] += error * 7/16
        if i + 1 < height:
            if j - 1 >= 0:
                image[i + 1, j - 1] += error * 3/16
            image[i + 1, j] += error * 5/16
            if j + 1 < width:
                image[i + 1, j + 1] += error * 1/16
```

### 3. Bayer 抖动

基于阈值矩阵的抖动算法，通过预设的阈值模式决定像素的颜色。

算法步骤：
1. 生成Bayer阈值矩阵（通常是2^n×2^n大小）
2. 对于每个像素，计算对应的阈值
3. 根据像素值与阈值的比较，分配调色板颜色

优点：产生规则的网格图案，在文本等高对比度图像上效果好
缺点：在平滑渐变区域可能产生明显的图案

```python
# 生成Bayer矩阵
def bayer_matrix(n):
    # ...（详见代码实现）

# 应用Bayer抖动
for i in range(height):
    for j in range(width):
        threshold = bayer_matrix[i % n, j % n] * MAX // (n**2)
        if image[i, j] > threshold:
            image[i, j] = palette[1]  # 白色
        else:
            image[i, j] = palette[0]  # 黑色
```

### 4. Atkinson 抖动

由Bill Atkinson发明的抖动算法，特点是误差扩散范围广，但总误差保持较低。

误差扩散模式：
$$
\begin{matrix}
    & X & \frac{1}{8} & \frac{1}{8} \\
\frac{1}{8} & \frac{1}{8} & \frac{1}{8} \\
    & \frac{1}{8} & 
\end{matrix}
$$

算法步骤：
1. 对每个像素，找到调色板中最接近的颜色
2. 计算量化误差
3. 将误差的1/8分配给周围6个像素

优点：图像清晰，减少了错误累积
缺点：可能丢失一些细节

```python
for i in range(height):
    for j in range(width):
        old_pixel = image[i, j]
        new_pixel = find_closest_palette_color(old_pixel)
        image[i, j] = new_pixel
        error = old_pixel - new_pixel
        error_part = error // 8  # 1/8误差
        
        # 向周围6个像素传播误差
        if j + 1 < width: 
            image[i, j + 1] += error_part
        if j + 2 < width: 
            image[i, j + 2] += error_part
        
        if i + 1 < height:
            if j - 1 >= 0: 
                image[i + 1, j - 1] += error_part
            image[i + 1, j] += error_part
            if j + 1 < width: 
                image[i + 1, j + 1] += error_part
        
        if i + 2 < height:
            image[i + 2, j] += error_part
```

## 安装

安装所有依赖：
```bash
pip install -r requirements.txt
```

安装包：
```bash
git clone https://gitee.com/Yingyi1048596/taichi-dither.git
cd taichi-dither
pip install -e .
```

如需使用GPU加速，请确保您的系统满足Taichi的GPU要求：
- NVIDIA GPU：CUDA支持
- AMD GPU：请参考Taichi文档

## 使用方法

### 基本使用

参见examples中的`use_example.py`。

examples文件夹中包括：

- cache_example.py 展示了使用内核缓存优化编译时间的性能分析
- use_example.py 展示了如何使用 taichi_dither 包
- gpu_test.py 展示了使用taichi对GPU的计算压力测试
- benchmark.py 展示了不同抖动算法和taichi的性能表现

### 高级选项

1. 自定义调色板：

```python
# 设置自定义灰度调色板
ditherer.set_palette([0, 85, 170, 255])  # 4种灰度级别
```

2. 调整输出大小以优化性能：

```python
# 指定输出尺寸，减少计算量
output_img = ditherer.process_image(
    img_path='input.jpg',
    algorithm='bayer',
    num_colors=8,
    use_color=True,
    output_width=400,   # 宽度为400像素
    output_height=300   # 高度为300像素
)
```

## 性能测试

本工具包含完整的性能测试模块，可以评估不同算法、色值数量和硬件配置下的性能表现。

### 测试方法

运行测试脚本：

```bash
# 完整测试（所有参数组合）
python benchmark.py --image test.jpg --output test_results

# 快速测试（减少测试用例数量）
python benchmark.py --image test.jpg --output test_results --fast
```

### 测试参数

测试脚本会评估以下参数组合的性能：

- 处理器：CPU vs GPU
- 算法：Basic, Floyd-Steinberg, Bayer, Atkinson
- 色值数量：2, 4, 8, 16
- 图像尺寸：从小到大多个等级
- 处理模式：灰度 vs 彩色

### 测试结果解析

测试完成后，`test_results` 目录中会生成：

1. **性能报告文本文件**：包含所有测试组合的处理时间和加速比
2. **性能图表**：直观展示不同参数对处理速度的影响
3. **处理结果图像**：可以比较不同算法的效果质量

通过分析测试结果，您可以：
- 确定最适合您应用场景的算法
- 了解GPU加速的收益点
- 根据图像大小和色值数量优化性能

## 常见问题

1. **Q: 为什么在某些图像上抖动效果不佳？**  
   A: 抖动算法效果受原始图像特性影响。对于高对比度图像，尝试Bayer抖动；对于平滑渐变，Floyd-Steinberg或Atkinson通常效果更好。

2. **Q: GPU加速未生效怎么办？**  
   A: 检查GPU驱动是否正确安装，Taichi是否支持您的GPU型号。在某些情况下，小图像或简单处理可能CPU反而更快。

3. **Q: 如何减少处理时间？**  
   A: 减小输出图像尺寸、减少色值数量、使用更简单的算法（如Bayer）、启用GPU加速。

4. **Q: 彩色模式处理很慢，如何优化？**  
   A: 彩色处理计算量大，可以减小图像尺寸、减少色值数量、或先进行图像降采样再处理。

5. **Q: 为什么使用K-Means提取调色板？**  
   A: K-Means可以找到图像中最具代表性的颜色，生成的调色板更贴近原图色彩分布。

6. **Q: 启用缓存机制有什么好处？**  
   A: 核心计算缓存可以避免重复生成已计算过的Taichi内核，显著提高批量处理性能。

## 参考资料

- [Dither技术介绍](https://en.wikipedia.org/wiki/Dither)
- [Floyd–Steinberg抖动算法](https://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dithering)
- [Bayer矩阵抖动](https://en.wikipedia.org/wiki/Ordered_dithering)
- [Taichi编程语言](https://taichi-lang.org/)