Topology-Preserving Downsampling of Binary Images¶

会议: ECCV 2024
arXiv: 2407.17786
代码: https://github.com/pengchihan/BinaryImageDownsampling (有)
领域: 医学图像
关键词: 二值图像下采样, 拓扑保持, 离散优化, 整数规划, 分割掩码

一句话总结¶

提出首个基于离散优化（整数规划）的拓扑保持二值图像下采样方法，通过将下采样像素的黑白决策编码为布尔变量、拓扑保持作为硬约束、与原图相似度作为目标函数来求解，保证下采样结果具有与原图完全相同的Betti数（连通分量数和孔洞数），同时保持与传统方法竞争性的像素级相似度。

研究背景与动机¶

二值图像（仅含前景和背景像素）广泛应用于分割掩码、文档分析、机器视觉和地图编码等场景。与灰度/彩色图像不同，二值图像自然对应2D图结构，其拓扑（连通分量数β₀和孔洞数β₁，即第零和第一Betti数）在应用中扮演关键角色——例如在医学图像分割中，拓扑正确性直接影响诊断准确性。

核心矛盾在于：所有现有的二值图像下采样方法（双线性/双三次插值+阈值化、各种pooling、ACN方法）都不能保证拓扑不变。即使一个下采样像素对应的原始块内全是黑色像素，出于拓扑正确性考虑也可能需要将其设为白色——这说明正确的下采样决策需要全局信息，任何局部方法都不可行。

本文的洞察：将拓扑保持的下采样问题形式化为离散优化问题——每个大像素的颜色是布尔变量，拓扑保持是硬约束，与原图的相似度是目标函数。这样，任何可行解都自动保证拓扑正确，而优化器会在所有拓扑正确的解中找到最相似原图的那个。另外，不可行问题（无拓扑正确解存在）也能被自动检测出来。

方法详解¶

整体框架¶

输入W×H的二值图像，以A×B的因子下采样。整个方法分为：(1) 分析原图的连通分量和区域邻接图(RAG)；(2) 为每个大像素-分量对创建布尔变量；(3) 构建四组约束确保拓扑保持；(4) 设计目标函数最大化与原图的相似度；(5) 用整数规划求解器(Gurobi)求解。

关键设计¶

布尔变量与覆盖建模:
- 对原图的每个连通分量C_i（含黑色和白色分量），收集所有可能覆盖它的大像素候选P_j^i
- 覆盖范围可扩展到大像素块以外（距离阈值dx=⌊A/4⌋, dy=⌊B/4⌋），增加灵活性
- 每个P_j^i是一个布尔变量，表示该大像素是否被分配给分量C_i
- 设计动机：简单的黑/白决策无法编码哪个分量覆盖了大像素，而分量级别的覆盖建模是拓扑约束的基础
四组拓扑保持硬约束:
- 完全非重叠覆盖约束: 每个大像素恰好被一个分量覆盖 → ∑P_j^i(X,Y) = 1
- 分量非空约束: 每个分量至少被一个大像素覆盖 → ∑P_j^i ≥ 1（否则分量消失）
- 局部邻域正确性约束: 不同黑色分量不能按8-邻域相邻，不同白色分量不能按4-邻域相邻 → (P_0^m + P_1^m) ≤ 1
- 边界保持约束（关键创新）: 确保每对相邻黑白分量之间存在恰好一条闭合的边界循环
  - 枚举12种可能的角(corner)配置，每种有左手侧(LHS)和右手侧(RHS)大像素
  - 角的存在当且仅当所有RHS大像素属于黑分量且所有LHS大像素属于白分量
  - 引入距离(Dist)整数变量和"last"布尔变量，确保边界上的角按单调递增距离排列，仅有一个"last"例外
  - 这有效排除了多个闭合环的可能性
- 设计动机：受网络设计中"no-island"约束启发，通过编码边界的单环结构来保证全局拓扑正确性
目标函数设计:
- 为每个大像素候选计算分数S_j^i：当原始像素与同分量的活跃大像素重叠时加分，加分量与距离成反比
- 具体地，每个原始像素在(2dx+1)×(2dy+1)窗口内对重叠的大像素候选贡献1分
- 最大化所有活跃大像素的总分：max ∑S_j^i × P_j^i
- 设计动机：这个简单的分数设计自然鼓励大像素覆盖与其同分量的原始像素重叠最多的位置

损失函数 / 训练策略¶

本文不涉及深度学习训练。整数规划问题使用Gurobi 11.0求解器求解。

补充：Baseline膨胀方法作为对照—— - 在下采样图中为每个分量创建拓扑正确的初始表示（点或边界框） - 迭代膨胀黑色分量然后白色分量 - 保证拓扑正确但贪心策略导致相似度差

实验关键数据¶

主实验¶

CNCB数据集542张分割掩码（512×512）的下采样对比：

方法	Factor	IoU↑	Dice↑	Betti误差↓	PH距离↓
Bicubic	2	93.08%	96.34%	0.061	0.018
Pooling	2	93.41%	96.53%	0.046	0.015
ACN	2	91.78%	95.61%	0.092	0.051
Dilation	2	59.71%	73.78%	0	0.026
Ours	2	93.10%	96.34%	0	0.005
Bicubic	8	73.27%	83.46%	0.339	0.091
Pooling	8	73.33%	83.21%	0.404	0.115
Dilation	8	53.40%	68.07%	0	0.051
Ours	8	73.31%	83.55%	0	0.030

消融实验¶

不同下采样率对PH计算加速的影响：

图像尺寸	原始(512)	256(×2)	128(×4)	64(×8)	32(×16)
PH计算时间(s)	0.965	2.157	0.864	0.624	0.568
PH距离	-	0.005	0.012	0.030	0.062

最短路径计算加速（200次Dijkstra平均）：

方法	Factor	距离误差↓	FP↓	FN↓	时间(s)↓
Bicubic	4	1.65	0.00	0.78	2.49
Pooling	4	2.63	0.00	0.00	2.96
Dilation	4	0.38	0.00	0.00	3.66
Ours	4	0.17	0.00	0.00	3.63
Bicubic	8	5.05	0.00	2.12	0.95
Ours	8	0.19	0.00	0.00	1.34
Bicubic	16	11.57	0.00	1.85	0.96
Ours	16	10.47	0.00	0.00	0.99

关键发现¶

拓扑保证与相似度可以兼得：本文方法在Betti数误差为0的同时，IoU/Dice与最好的非拓扑保持方法几乎相同
PH距离全面最低：即使在持久同伦这种连续拓扑度量上，本文方法也优于所有其他方法
Dilation方法虽然拓扑正确但相似度极差：IoU仅59.71%（×2）vs 93.10%（本文），说明贪心策略无法兼顾两个目标
不可行案例很少：×2/×4/×8/×16分别仅有2/1/3/8个不可行案例，说明绝大多数情况都存在拓扑正确解
计算速度随下采样率提高而加快：因为大像素候选变少，×4以上时<1秒，可交互式使用
最短路径应用是拓扑保证的独特优势：非拓扑正确方法会产生false positive和false negative，使结果不可靠
PH计算加速在×4以上时间净收益为正：下采样+计算PH的总时间<直接计算原图PH的时间

亮点与洞察¶

形式化问题定义的力量: 将看似不可能的"保证拓扑正确"转化为整数规划的硬约束，优雅而有力
边界保持约束的创新设计: 受"no-island"约束启发，通过距离整数变量和"last"标记确保单一闭合环的存在，是全文最核心的技术贡献
充分利用不可能性: 当问题无可行解时，IP求解器能立即检测出来，这比启发式方法更可靠
实际应用驱动: PH计算加速和最短路径两个应用展示了拓扑保证在实际中的独特价值
一个反直觉的发现：即使对应块内全是黑像素，下采样像素也可能需要设为白色——只有全局优化能处理这种情况
12种角配置的穷举虽然看起来工程化，但为问题提供了完备的建模基础

局限与展望¶

无法处理极细结构：道路网络和血管等薄结构可能无法满意地保持，因为目标函数对黑白分量的偏好相同
IP求解器依赖：使用Gurobi商业求解器，增加了部署门槛
下采样因子限制：A和B必须整除W和H，限制了灵活性
不支持连续或非均匀下采样：只能做整数倍下采样
未来研究方向：(1)为细结构设计偏好性目标函数，(2)将约束集成到神经分割网络的多尺度表示中，(3)扩展到3D体积数据

评分¶

新颖性: ⭐⭐⭐⭐⭐ (首次解决拓扑保持下采样问题，问题定义和约束设计均有原创性)
实验充分度: ⭐⭐⭐⭐ (医学图像+两个应用场景，定量全面，但仅测试一个数据集)
写作质量: ⭐⭐⭐⭐ (数学严谨，但符号密集，需要读者有拓扑学基础)
价值: ⭐⭐⭐⭐ (解决了一个有明确需求的问题，但应用场景相对小众)