256 lines
14 KiB
Markdown
256 lines
14 KiB
Markdown
# 生成算法说明
|
||
|
||
本文档描述当前代码实际算法。核心代码位于 `backend/core/pipeline.py`、`backend/core/layout.py`、`backend/core/weights.py`、`backend/EfficientWordCloud/efficient_wordcloud/src/ewc_core.cpp`。
|
||
|
||
## 总流程
|
||
|
||
```
|
||
1. 读取 Excel 名单 → pipeline.main()
|
||
2. 智能画幅计算 → mask.calculate_dynamic_dimensions()
|
||
3. 生成并归一化掩膜 → mask.prepare_mask()
|
||
4. 计算权重 → weights.extract_weights_from_df() + weights.get_stroke_complexity_batch()
|
||
5. 估算字号范围 → weights.calculate_font_by_area_model()
|
||
6. 小画布布局 → layout.OptimizedEfficientWordCloud.generate_from_frequencies()
|
||
7. C++ 按真实字形找位置并原子写入 → IntegralGrid.place_glyph_exact()
|
||
8. 二分搜索能容纳全部姓名的最大字号缩放；仍放不下则扩大画布后重排
|
||
9. 密度优化 → 探测更大字号并保留完整率不下降的候选
|
||
10. 高清精修 → render.refine_layout_with_hd_clearance() 加入隔离带局部微调
|
||
11. 输出 PNG / SVG / DB / metrics
|
||
```
|
||
|
||
## 名单与重复填充
|
||
|
||
`N_REPETITIONS` 决定目标词数：
|
||
|
||
```
|
||
total_target = len(names) * N_REPETITIONS
|
||
```
|
||
|
||
布局序列由 `_build_layout_sequence()` 生成。行为：**按原名单循环追加**，不是把同一个名字所有副本先放完。
|
||
|
||
```
|
||
[A, B, C], N_REPETITIONS=4
|
||
→ [A, B, C, A, B, C, A, B, C, A, B, C]
|
||
```
|
||
|
||
同名副本在同一批布局中使用相同目标字号。放置失败不会触发逐词缩字号。
|
||
|
||
## 权重逻辑
|
||
|
||
### Excel 权重
|
||
|
||
- `WEIGHT_COL_NAME` 优先于 `WEIGHT_COL_INDEX`
|
||
- 有效权重必须是可转数字且大于 `0`
|
||
- `REMOVE_DUPLICATES=True` 时，同名权重取最大值
|
||
- `REMOVE_DUPLICATES=False` 时，仍按名字聚合成权重映射
|
||
|
||
### 笔画权重
|
||
|
||
- `ENABLE_STROKE_WEIGHTS=True` 时，系统渲染每个字符到 `64×64` 灰度图，用像素占用量估算复杂度
|
||
- 一个名字的笔画权重取其中最复杂字符的值
|
||
- 若同时存在 Excel 权重：Excel 值作为基础权重，笔画复杂度除以全体中位数后作为乘数
|
||
- 这样手动权重比例仍保留，且 Excel 权重全为 `1` 时笔画开关也不会失效
|
||
- `ENABLE_STROKE_WEIGHTS=False` 且无 Excel 权重时，所有名字权重默认为 `10`
|
||
|
||
## 字号范围估算
|
||
|
||
`calculate_font_by_area_model()` 使用以下输入估算 `min_font` / `max_font`：
|
||
|
||
- 可填充面积（掩膜中 `0` 的像素数）
|
||
- 目标填充率 `TARGET_FILL_RATIO`
|
||
- 打包效率 `PACKING_EFFICIENCY`
|
||
- 重复次数 `N_REPETITIONS`
|
||
- 名字长度、各名字权重
|
||
|
||
公式思想：
|
||
|
||
- 可填区域越大，字号越大
|
||
- 名字越多、重复次数越高，字号越小
|
||
- 字符越多，总字符质量越高，字号越小
|
||
- 权重越高，在 `log1p(weight)` 归一化后获得更高面积质量
|
||
|
||
最终 `max_font = min_font × SIZE_RATIO`。
|
||
|
||
## 字号打分
|
||
|
||
`build_log_rank_scores(..., per_word=True)` 按姓名权重计算固定分数，映射到展开后的重复序列。结果是：
|
||
|
||
- 同名副本目标分数相同
|
||
- 同名副本初始目标字号相同
|
||
- 权重相同时，所有姓名初始目标字号相同
|
||
|
||
`SIZE_RATIO=1` 时，`min_font == max_font`，所有同权重姓名在重试前后都保持完全相同字号。
|
||
|
||
## 等字号模式
|
||
|
||
`SIZE_RATIO=1` 时，面积估算阶段直接令 `min_font = max_font`。所有字号重试也只改变单一字号值。
|
||
|
||
等字号批次的特殊优化：
|
||
|
||
1. 视作整批同字号布局，使用整批字号打分（`per_word=False`）
|
||
2. 密度优化阶段在完整候选中比较字符级最大空洞（`largest_empty_square_size`），并尝试不同布局种子降低空洞
|
||
3. 高清精修阶段允许优先级回溯（把失败词提前到队列最前）
|
||
|
||
## 放置策略
|
||
|
||
放置顺序按字号分档：大字号先随机撒开，其余再从中心螺旋填充。
|
||
大字号需要整片空白才放得下，等螺旋填满画布就没有空间了，因此必须先放。
|
||
档内按索引顺序放置，保证同一 `layout_seed` 完全可复现。
|
||
|
||
每个词的放置流程：
|
||
|
||
1. 根据目标分数得到目标字号（线性插值于 `min_font` 到 `max_font`）
|
||
2. 逐词独立随机决定横排或竖排，竖排概率为 `VERTICAL_RATIO`（流水线以此换算 `prefer_horizontal = 1 - VERTICAL_RATIO`）；
|
||
当前竖排为整词旋转 90°（字符侧倒），不是字符直立的传统竖排
|
||
3. 用 PIL 渲染真实字形 bitmap，施加单侧安全边距（margin）生成碰撞 mask
|
||
4. 调用 C++ `place_glyph_exact()` 搜索合法位置并原子写入
|
||
5. 当前方向找不到时，只尝试同字号的另一方向
|
||
6. 任意姓名失败即视为本次整批布局不完整
|
||
7. **不逐词缩字号**。Python 统一缩放整批字号范围后重新布局
|
||
8. 触及字号下限仍失败时，按 `CANVAS_RETRY_GROWTH` 扩大画布并整批重排
|
||
9. 将完整布局映射到高清字号和坐标
|
||
10. 高清画布进行逐词隔离带精修，局部无合法位置时扩大画布并整批重排
|
||
|
||
## C++ 真实字形搜索
|
||
|
||
`IntegralGrid` 维护两个核心结构：
|
||
|
||
- `canvas`：真实占用像素（`1` 表示已占用或掩膜阻挡）
|
||
- `data`：兼容旧矩形查询的积分图；当前主路径不依赖逐词重建
|
||
|
||
`place_glyph_exact()` 有三种放置模式，由 `layout.py` 按字号分配：
|
||
|
||
**大字号（`placement_mode=2`）**：字号达到 `min_font + (max_font - min_font) * 0.80` 的姓名先放，随机探测取第一个合法位置。
|
||
探测受一个软半径约束：前 `75%` 次探测限制在质心周围 `0.55 → 1.0` 倍掩膜半径内，之后放开。
|
||
约束只影响落点偏好，不会排除任何合法位置，因此不影响完整率。
|
||
等字号批次中 `max_font == min_font`，不存在大字号档，全部走螺旋。
|
||
|
||
**小字号（`placement_mode=1`）**：先试可填区域质心，再沿费马螺旋（黄金角 `2.39996`，`radius = 1.25 * sqrt(step)`）向外搜索。
|
||
`spiral_cursor` 在整批姓名间持续推进。每个词以随机相位 `theta_offset ∈ [0, 2π)` 起扫，
|
||
使相邻两词的角距不再恒为黄金角；随机量取自按 `layout_seed` 派生的逐词种子，同一种子完全可复现，
|
||
不同种子给出真正不同的排布，而不只是同一图形换名字。
|
||
|
||
相位必须取满整圈。曾尝试限制在 `±60°` 的窄扇区内，结果明显更差：
|
||
扇区会让词跳过边界上已经合法的位置而退到更差的位置，实测 800 词的最终墨水密度下降 31%（`0.255 → 0.176`）。
|
||
取满整圈则不损失密度，因为半径增长时扫描本来就会覆盖所有角度。
|
||
|
||
注意这并不会让排布显得无序：半径仍与放置顺序高度相关（Pearson `r ≈ 0.98`）。
|
||
中心向外且保持紧密的填充必然按半径递增推进——「有序」与「紧密」是同一件事。
|
||
要在不牺牲密度的前提下打散这种观感，需要多个螺旋原点，而不是在单一螺旋上加抖动。
|
||
|
||
**兼容模式（`placement_mode=0`）**：纯随机探测，取第一个合法位置。
|
||
|
||
三种模式共用后续步骤：
|
||
|
||
1. 随机探测失败后，从种子决定的偏移开始环形完整扫描，保证存在合法位置时一定能找到
|
||
2. 对每个候选位置逐像素比较碰撞 mask 与 C++ `canvas`
|
||
3. 命中后只写入真实字形，占位查询和写入在同一次 C++ 调用中完成
|
||
|
||
真实字形搜索允许透明角落和笔画间空隙安全交错，比外接矩形碰撞更密。安全边距只参与候选检查，不会被双侧累计放大。
|
||
|
||
## 高清精修（隔离带）
|
||
|
||
正式流水线不在低清工作网格增加边距，因为 `1` 个工作像素会被放大成约 `5–6` 个高清像素并显著损失容量。
|
||
|
||
隔离带优先作用在最终高清画布，宽度为 `1px`，不是用户参数。精修流程：
|
||
|
||
1. 小画布完整布局放大到高清
|
||
2. 逐词在高清画布上验证，加入 `1px` 隔离带
|
||
3. 碰撞时先在 `max_shift=24px` 内做局部微位移
|
||
4. 邻域内无解时，`_find_free_placement()` 以逐步放大的窗口（`256 → 1024 → 全画布`）在整张画布上找空位，
|
||
取离原位置最近的一个。窗口内用积分图筛选：足迹范围内完全空白的位置必定可放，
|
||
无需逐像素比较，因此绝大多数候选位置只花两次加法就被排除。
|
||
这一步把「一个词放不下就整条流水线换更大画布重来」变成一次局部搬移——
|
||
后者是全流程中最贵的失败路径，实测会让端到端耗时翻倍且仍可能最终失败
|
||
5. 精修失败时，最多进行 `1` 次确定性整批优先级回溯（把失败词移到队列最前）
|
||
6. 若轮廓过窄无法容纳额外隔离带，降为精确零间隙碰撞（`clearance=0`）
|
||
7. 全部候选无解时，才由外层扩大画布后整批重新布局
|
||
|
||
密度搜索会保留各档完整整批候选。最高密度候选若无法在有限位置修正范围内通过高清隔离验收，则改用上一档完整整批候选；不会对碰撞姓名单独缩字号，也不会接受带重叠的高密度结果。
|
||
|
||
## 字号缩放二分搜索
|
||
|
||
目标是找到**能放下全部姓名且轮廓覆盖最好的字号缩放**。单纯追求最大字号会让费马螺旋把词压在质心圆盘内、走不到掩膜远端，于是非圆形掩膜（心形尖端、人物四肢）填成圆形。
|
||
|
||
流水线用「探测」来判定某个缩放是否可行。探测在遇到第一个放不下的姓名时立刻停止：
|
||
一个姓名只有在螺旋、随机探测和全画布穷举扫描都失败后才算放不下，所以单个失败即可证明该缩放不可行，
|
||
不必把整批跑完。这一点对速度至关重要——放不下的姓名要付出完整搜索的代价，
|
||
实测约为可放下姓名的 `10` 倍，把注定失败的整批跑到底是流水线中最昂贵的操作。
|
||
`OptimizedEfficientWordCloud.max_failures` 控制这一行为，为 `None` 时跑满整批并尽量多放。
|
||
|
||
搜索过程：
|
||
|
||
1. 从 `scale=1.0` 开始探测；失败则按 `sqrt(已放置比例)` 收缩再试，最多 `4` 次
|
||
2. 得到一个可行值后，在最大失败值与最小可行值之间二分最多 `3` 次，把之前收缩让掉的字号找回来
|
||
3. 相邻两个缩放取整后字号相同时停止——工作网格上字号是小整数，再细分没有意义
|
||
4. 多个可行结果中取**形状覆盖度最高**的那个（`compute_coverage_score`），覆盖度并列时才取缩放更大者
|
||
|
||
### 形状覆盖度
|
||
|
||
`compute_coverage_score()` 把可填区域切成 `8×8` 像素的块，只统计可填像素占比 ≥ 30% 的「区域块」，计算其中被墨迹触达的比例：
|
||
|
||
```
|
||
coverage = 被触达的区域块数 / 区域块总数
|
||
```
|
||
|
||
这是「轮廓是否被填出来」的直接度量：质心圆盘只触达中心几块，覆盖度低；铺进掩膜每个臂/尖端的布局触达各块，覆盖度高。块粒度（而非逐像素加权）让它对掩膜几何稳健——一个尖端无论宽 3px 还是 30px 都是一个块，触达它都被同等奖励。
|
||
|
||
## 填充率重试
|
||
|
||
一次布局完成后，`compute_fill_ratio_fast()` 重新渲染 layout 并计算填充率，`compute_coverage_score()` 计算形状覆盖度。
|
||
|
||
- 面积模型首次完整放入但明显低于 `TARGET_FILL_RATIO` 时，进入**双向密度优化**：每轮同时探测「加大字号」和「减小字号」两个方向，取覆盖度更高的候选。减小字号让费马螺旋走更远、触达掩膜远端，即使填充率略降也能提升覆盖度——这正是纠正「填成圆形」的关键方向。覆盖度与填充率都无提升时停止
|
||
- 整批未完整放入时，流水线不会输出半成品：先整批等比例调整字号；触及最小字号仍失败时按 `CANVAS_RETRY_GROWTH` 扩大画布并重新生成
|
||
|
||
## 字号硬约束
|
||
|
||
- 不存在逐词缩字号、gap filling 或大字号自动压缩路径
|
||
- `USER_MIN_FONT_SIZE` 和 `USER_MAX_FONT_SIZE` 是不可越过的边界；冲突时直接报错
|
||
- `SIZE_RATIO=1` 在面积估算、整批重试和高清放大阶段始终保持单一字号
|
||
- 完整名单不可关闭；放不下时只能整批重排、整批等比例调整或扩大画布
|
||
|
||
## 空洞优化（等字号模式）
|
||
|
||
等字号模式下，字符级最大空洞（`largest_empty_square_size`）用于判断是否存在"可放字符级空洞"：
|
||
|
||
- 当前 `largest_empty_square ≥ ceil(font_size * 1.25)` 时视为存在字符级空洞
|
||
- 流水线会在同一字号档位尝试最多 `3` 种不同布局种子（按人数递减预算）
|
||
- 目标是最小化最大空洞尺寸，不改变任何字号
|
||
|
||
## 自动画幅
|
||
|
||
`calculate_dynamic_dimensions()` 先对 `BASE_HD_WIDTH × BASE_HD_HEIGHT` 做一次 probe 掩膜，计算可填比例 `free_ratio`，再用以下公式扩展：
|
||
|
||
```
|
||
area_per_word = (MIN_READABLE_HEIGHT_PX²) × avg_len × 1.05
|
||
required_area = num_words × area_per_word × N_REPETITIONS / TARGET_FILL_RATIO
|
||
required_area /= free_ratio
|
||
scale_factor = √(required_area / current_area)
|
||
new_w = clamp(base_w × scale_factor, max_edge=6000)
|
||
```
|
||
|
||
- 扩展后宽高向上取整到最近的 `100`
|
||
- 最大边长限制为 `6000px`，避免 SVG/PNG 过度膨胀
|
||
- 掩膜只生成一次，扩展后复用
|
||
|
||
## 性能：按字符缓存
|
||
|
||
一份中文名单里不同**字符**的数量远小于不同**姓名**的数量——750 个三字姓名通常只含约 `34` 个不同字符。
|
||
两处最重的工作因此按字符而不是按姓名缓存：
|
||
|
||
- **SVG 轮廓**（`layout._char_shape`）：每个 `(字符, 字号, 方向)` 只取一次字形轮廓并格式化一次路径字符串。
|
||
一个姓名由若干字符路径拼成，字符在词内的位置放进元素的 `transform` 平移量，
|
||
所以缓存的路径字符串被逐字节复用，不需要重新解析或平移坐标。
|
||
导出时每个字形输出一个 `<path>`，几何结果与整词单路径完全一致（已逐点验证）。
|
||
- **高清字形位图**（`render._word_ink`）：隔离精修与独立的重叠审计会在相同字号下光栅化相同姓名，
|
||
两者共用一份缓存。
|
||
|
||
`_path_bbox()` 只在每个字符首次构建时调用一次，词的包围盒由各字符包围盒平移后取并集算出，
|
||
不再对生成好的路径字符串做正则重解析。
|
||
|
||
## 零重叠保证
|
||
|
||
输出前 `count_layout_overlap_pixels()` 会独立重渲染整个 layout 并统计被两个及以上词占用的像素。
|
||
该值必须为 `0`，否则 `placement_ok` 为假，流水线拒绝输出而不是交付带重叠的结果。
|
||
这项校验独立于隔离精修，即使精修逻辑有误也能兜住。
|