02-核心拟合流程

# LPGS 核心拟合流程

> **文档版本**：v1.0.0 · **算法版本**：LPGS v1.0

## 1. 图像加载与预处理

### 1.1 分辨率归一化

源图像首先被缩放至最大维度不超过 `MAX_DIM = 500` 像素：

```
scale = min(1.0, MAX_DIM / max(srcWidth, srcHeight))
scaledW = round(srcWidth * scale)
scaledH = round(srcHeight * scale)
```

这一步确保无论输入图像多大，拟合工作始终在一个固定量级的像素空间中进行，保证算法运行时间的可预测性。

### 1.2 边缘填充（Edge-Aware Mode）

当启用边缘感知模式时，图像四周会被填充 3% 的透明边距：

```
edgePadding = ceil(max(scaledW, scaledH) * 0.03)
imgW = scaledW + edgePadding * 2
imgH = scaledH + edgePadding * 2
```

填充区域的作用是为边缘处的形状提供"溢出空间"，避免形状被硬性裁切。填充区域内的目标像素被设为完全透明。

### 1.3 Alpha 预混合（Preserve Transparency）

当启用透明度保留模式时，对目标图像进行 Alpha 预混合处理：

对于每个像素：

- 若 `targetAlpha < alphaThreshold`：该像素视为"透明"，将目标颜色替换为当前画布颜色（等效于"忽略此像素"）
- 若 `targetAlpha >= alphaThreshold`：将半透明像素与背景色混合：
  ```
  targetRGB = targetRGB * (alpha/255) + currentRGB * (1 - alpha/255)
  targetAlpha = 255
  ```

预混合后，所有参与拟合的像素的 Alpha 均为 255，将半透明拟合问题转化为不透明拟合问题。

### 1.4 初始误差计算

预处理完成后，计算初始总 SSD：

```
E₀ = Σ Σ (T_c(p) - C_c(p))²
     p  c∈{R,G,B}
```

其中 T 为目标图像，C 为当前画布（初始为纯色背景），求和仅覆盖 Alpha 阈值以上的像素。

---

## 2. 误差网格（Error Grid）

### 2.1 网格构建

将图像划分为 `16×16` 像素的网格单元，每个单元记录其内部所有像素的平均 SSD 误差：

```
gridCell[gx, gy] = mean( SSD(p) for p in cell[gx, gy] )
```

网格尺寸为 `(imgW + 15) / 16 × (imgH + 15) / 16`，即约 `31×31` 个单元（对于 500px 图像）。

### 2.2 加权位置采样

误差网格用于指导新形状的放置位置。采样过程如下：

1. 计算所有网格单元的误差总和 `totalError`
2. 生成一个 `[0, totalError)` 区间的随机数 `r`
3. 按网格单元顺序累加误差值，当累加值首次超过 `r` 时，选中该单元
4. 在选中单元的像素范围内均匀随机取一个坐标点

这等价于以误差值为权重的**轮盘赌选择**（Roulette Wheel Selection）：误差越大的区域被选中的概率越高。

### 2.3 脏标记机制

误差网格设有脏标记 `_errorGridDirty`。每当 `ApplyShape()` 修改了当前画布后，脏标记置为 `true`，下次采样时触发重建。这避免了每帧都重建网格的开销。

---

## 3. 边缘距离图（Edge Distance Map）

### 3.1 构建算法

边缘距离图是一个与图像同尺寸的浮点数组，记录每个像素到最近的不透明边缘的距离。构建过程采用**两遍扫描距离变换**（Two-Pass Distance Transform）：

**初始化**：
- 不透明像素（`originalAlpha >= threshold`）→ 距离设为 `maxDist = sqrt(imgW² + imgH²)`
- 透明像素 → 距离设为 `0`

**前向扫描**（左上 → 右下）：
```
对于每个像素 (x, y):
    minD = 当前值
    minD = min(minD, distMap[y-1, x]   + 1)      // 上
    minD = min(minD, distMap[y, x-1]   + 1)      // 左
    minD = min(minD, distMap[y-1, x-1] + 1.414)  // 左上
    minD = min(minD, distMap[y-1, x+1] + 1.414)  // 右上
    distMap[y, x] = minD
```

**后向扫描**（右下 → 左上）：
```
对于每个像素 (x, y):
    minD = 当前值
    minD = min(minD, distMap[y+1, x]   + 1)      // 下
    minD = min(minD, distMap[y, x+1]   + 1)      // 右
    minD = min(minD, distMap[y+1, x+1] + 1.414)  // 右下
    minD = min(minD, distMap[y+1, x-1] + 1.414)  // 左下
    distMap[y, x] = minD
```

两遍扫描各执行 2 次（共 4 遍），以获得更精确的距离场。

### 3.2 用途

边缘距离图在边缘感知模式下用于两个目的：

1. **限制形状大小**：形状的最大半径被限制为其中心到边缘距离的 0.8 倍，防止形状"溢出"到透明区域
2. **检测越界**：`ShapeOverlapsTransparent()` 检查形状内部是否有超过 5% 的像素落在透明区域

---

## 4. 候选形状生成（RandomShape）

### 4.1 位置采样

- **标准模式**：通过误差网格加权采样获取位置
- **精度模式**：在 ROI 区域内均匀随机采样

### 4.2 形状类型与参数

LPGS 支持三种基元类型，每种有不同的参数空间：

| 类型 | 参数 | 位置采样 | 尺寸范围 | 旋转 |
|------|------|---------|---------|------|
| **circle** | X, Y, Radius | 误差加权 | `[4, 4 + minDim*0.2] × sizeMult` | 无 |
| **ellipse** | X, Y, Rx, Ry, Angle | 误差加权 | Rx: `[5, 5 + imgW*0.16] × sizeMult`<br>Ry: `[3, 3 + imgH*0.16] × sizeMult` | `[0, π)` 均匀随机 |
| **line** | X, Y, Rx, Ry, Angle | 误差加权 | Rx: `[15, 15 + minDim*0.35] × sizeMult`<br>Ry: `[1.5, 4.5] × sizeMult` | 局部梯度方向 + π/2 |

### 4.3 尺寸递减策略

形状尺寸随拟合进度递减：

```
progress = shapeCount / maxShapes
sizeMult = 1.0 - progress * 0.55
```

- 拟合初期（`progress ≈ 0`）：`sizeMult ≈ 1.0`，生成大形状铺底
- 拟合末期（`progress ≈ 1.0`）：`sizeMult ≈ 0.45`，生成小形状补细节

在精度模式下，尺寸额外缩小 60%：`sizeMult *= 0.4`。

### 4.4 细线的梯度对齐

细线（line）类型的旋转角度不是纯随机的，而是基于目标图像的**局部梯度方向**：

1. 在采样位置取 3×3 邻域
2. 计算每个像素的灰度强度（BT.601 权重：`0.299R + 0.587G + 0.114B`）
3. 用 Sobel-like 方式计算梯度向量 `(gx, gy)`
4. 细线方向 = 梯度方向 + π/2（垂直于梯度，即沿边缘方向）

若梯度幅值过小（`gx² + gy² < 0.01`），则退化为随机角度。

---

## 5. 形状评估（EvaluateShape）

这是 LPGS 的数学核心——给定一个形状的几何参数，求解其最优颜色和透明度。

### 5.1 问题建模

对于形状覆盖的像素集合 S，应用形状后的新像素值为：

```
C'_c(p) = C_c(p) + α × (s_c - C_c(p)),  p ∈ S
```

其中：
- `C_c(p)`：当前画布在像素 p 的颜色通道 c 值
- `s_c`：形状的颜色通道 c 值（待求）
- `α`：形状的透明度（待求）

目标是最小化应用形状后的局部 SSD：

```
min_{s_R, s_G, s_B, α}  Σ_{p∈S} Σ_c (T_c(p) - C'_c(p))²
```

### 5.2 两轮迭代最小二乘求解

**第一轮**：

1. 用目标像素的平均颜色作为初始估计：

```
   s_c⁽⁰⁾ = (1/|S|) × Σ_{p∈S} T_c(p)
   ```

2. 在 s_c⁽⁰⁾ 给定下，求解最优 α：

```
   分子 = Σ_c [ s_c⁽⁰⁾ × (ΣT_c - ΣC_c) - (ΣT_cC_c - ΣC_c²) ]
   分母 = Σ_c [ |S| × (s_c⁽⁰⁾)² - 2 × s_c⁽⁰⁾ × ΣC_c + ΣC_c² ]
   α = 分子 / 分母    （分母 < 0.001 时，α 默认取 0.5）
   ```

3. 在 α 给定下，反推最优颜色：

```
   s_c = ( ΣT_c - (1-α) × ΣC_c ) / (α × |S|)
   ```

**第二轮**：

用第一轮得到的 s_c 重新计算 α，再重新计算 s_c。两轮迭代足以收敛到高精度解。

### 5.3 约束

- `α ∈ [0.01, 0.99]`：避免完全透明或完全不透明
- `s_c ∈ [0, 255]`：颜色值钳位到合法范围

### 5.4 改进量计算

评估完成后，计算形状的**改进量**：

```
oldSSD = 形状覆盖区域 + 非覆盖区域（应用前）
newSSD = 形状覆盖区域（应用后） + 非覆盖区域（不变）
improvement = oldSSD - newSSD
newTotalSSD = totalError - oldSSD + newSSD
```

注意：`oldSSD` 和 `newSSD` 的计算范围是形状的包围盒（bounding box），但只有形状内部的像素会改变，外部像素的误差在 `oldSSD` 和 `newSSD` 中相同（会抵消）。

---

## 6. 候选选择与变异优化（TryOneShape）

### 6.1 候选生成与评估

1. 生成 `Candidates`（默认 64）个随机形状
2. 对每个候选调用 `EvaluateShape()` 求解最优颜色
3. 若启用边缘感知模式，检查形状是否越界（`ShapeOverlapsTransparent`）
4. 选择使 `NewTotalSSD` 最小的候选

### 6.2 变异优化

对最优候选进行 16 轮随机扰动（mutation），每轮：

1. 复制当前最优形状
2. 对位置、尺寸、旋转施加随机扰动：
   - 位置：`±0.3 × 半径` 范围内偏移
   - 尺寸：`×(1 ± 0.3)` 范围内缩放
   - 旋转（椭圆）：`±0.4 rad`，细线：`±0.3 rad`
3. 若启用边缘感知，限制变异后形状的大小
4. 评估变异后形状
5. 若变异后更优，则替换当前最优

### 6.3 接受准则

只有当 `bestSSD < totalError` 时，才接受该形状并应用到画布。这保证了总误差的单调递减性。

---

## 7. 形状应用（ApplyShape）

将形状的颜色混合到当前画布：

```
对于形状覆盖的每个像素 p:
    C_B(p) = round(C_B(p) + α × (s_B - C_B(p)))
    C_G(p) = round(C_G(p) + α × (s_G - C_G(p)))
    C_R(p) = round(C_R(p) + α × (s_R - C_R(p)))
```

注意像素存储格式为 BGRA（字节数组中 B 在前），且 Alpha 通道不参与混合。

应用后，误差网格脏标记置为 `true`，总误差更新为 `bestSSD`。

---

## 8. 精度拟合模式

### 8.1 预留机制

标准拟合阶段只使用 `(1 - reserveRatio)` 的形状配额。例如 `MaxShapes = 500, ReserveRatio = 20%`，则标准拟合最多使用 400 个形状，剩余 100 个留给精度模式。

### 8.2 ROI 框选

用户可以在输出预览上手动框选一个矩形区域（ROI），精度拟合将只在该区域内添加形状。

### 8.3 自动检测

`AutoDetectRoi()` 在误差网格上滑动一个 1/4 画布大小的窗口，找到平均误差最高的区域作为 ROI。

### 8.4 精度模式行为

进入精度模式后：
- 形状位置只在 ROI 内采样
- 形状尺寸额外缩小 60%（`sizeMult *= 0.4`）
- `MaxShapes` 增加 `precisionAddNum`（默认 50）