01-概述

# LPGS 算法概述

> **文档版本**：v1.0.0 · **算法版本**：LPGS v1.0 · **最后更新**：2026-06-01

## 算法全称

**LPGS** — **L**uMKFs **P**rism **G**auss **S**plat

中文名：**LuMKFs 棱镜高斯溅射引擎**

## 一句话定义

LPGS 是一种基于**误差驱动的随机贪心搜索**的图像几何拟合算法：通过迭代地向画布上叠加半透明的几何基元（圆、椭圆、细线），逐步逼近目标图像，使当前画布与目标图像之间的像素级 SSD（Sum of Squared Differences）误差持续下降。

## 算法定位

| 维度 | 描述 |
|------|------|
| 问题域 | 图像 → 几何基元序列的逆向分解 |
| 优化目标 | 最小化 SSD(I_target, I_current) |
| 搜索策略 | 随机采样 + 贪心选择 + 局部变异 |
| 收敛保证 | 单调递减——每步仅当总误差下降时才接受新形状 |
| 输出形式 | 有序的几何基元列表（含位置、尺寸、旋转、颜色、透明度） |

## 核心思想

LPGS 的核心思想可以概括为 **"溅射"（Splat）**：

1. **溅射**：每次向画布"溅射"一个几何形状，该形状会覆盖画布上的部分像素
2. **棱镜**：每个形状就像一个棱镜，将画布上的颜色"折射"到更接近目标的方向
3. **高斯**：颜色求解过程采用最小二乘法（与高斯分布的最大似然估计等价），在给定形状参数下寻找全局最优的颜色和透明度

算法不追求一步到位的完美解，而是通过大量"小溅射"的累积效应，从粗到细地逼近目标图像。

## 与相关算法的关系

LPGS 的算法框架与 [Geometrize](https://www.geometrize.co.uk/) / [Primitive](https://github.com/fogleman/primitive) 系列算法同源，但在以下方面有本质区别：

| 特性 | Geometrize/Primitive | LPGS |
|------|---------------------|------|
| 误差驱动采样 | 无/简单 | 16×16 误差网格加权采样 |
| 颜色求解 | 单轮最小二乘 | 两轮迭代最小二乘 |
| 边缘感知 | 无 | 距离变换 + 形状越界检测 |
| 透明度处理 | 不支持 | Alpha 预混合 + 阈值过滤 |
| 精度模式 | 无 | ROI 框选 + 自动检测高误差区域 |
| 多线程 | 无 | 并行候选评估 |
| 基元类型 | 多种（三角形、矩形等） | 圆形、椭圆、细线（line） |

**拟合对比**
![](/media/202606/对比_1780373164.jpg)

## 算法整体流程

```
┌─────────────────────────────────────────────────────────┐
│                    图像加载与预处理                      │
│  缩放至 MAX_DIM=500 → 边缘填充 3% → Alpha 预混合         │
└────────────────────────┬────────────────────────────────┘
                         ▼
┌─────────────────────────────────────────────────────────┐
│                    构建初始误差状态                      │
│  计算初始 SSD → 构建误差网格 → 构建边缘距离图             │
└────────────────────────┬────────────────────────────────┘
                         ▼
              ┌──────────────────────┐
              │   主循环 RunLoop()   │◄────────────────────┐
              │ 每帧添加 Speed 个形状 │                    │
              └──────────┬───────────┘                    │
                         ▼                                │
              ┌──────────────────────┐                    │
              │   TryOneShape()      │                    │
              │候选生成→评估→变异优化 │                    │
              └──────────┬───────────┘                    │
                         ▼                                │
              ┌──────────────────────┐                    │
              │  形状数 < MaxShapes?  │─── 是 ────────────┘
              └──────────┬───────────┘
                         │ 否
                         ▼
              ┌──────────────────────┐
              │   拟合完成/精度模式    │
              │  → ROI 框选 → 后处理  │
              └──────────────────────┘
```

## 关键设计原则

1. **单调性**：每一步只接受使总 SSD 下降的形状，保证误差曲线单调递减
2. **误差驱动**：新形状的采样位置由误差分布决定，误差大的区域被优先处理
3. **由粗到细**：形状尺寸随进度递减（`sizeMult = 1.0 - progress * 0.55`），前期大形状铺底，后期小形状补细节
4. **分离关注点**：形状参数（几何）由随机搜索决定，颜色参数由解析求解决定——两者解耦
5. **增量式**：每个新形状基于当前画布状态评估，天然支持暂停/继续/精度追加