💻 computer science

A Dynamic Programming Framework for Discovering Count and Values of Multilevel Image Thresholding

本文介绍了 MET-DP，这是一种新颖的动态规划框架，它利用改进的最小误差阈值准则自动确定多级图像分割的最优阈值数量，相较于传统方法展现出更优的计算效率和自动阈值检测能力，尽管其图像质量指标（SSIM 和 PSNR）略低于用户指定方法。

原作者： Eslam Hegazy, Mohamed Gabr

发布于 2026-05-27

📖 1 分钟阅读☕ 轻松阅读

原作者： Eslam Hegazy, Mohamed Gabr

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你有一个巨大的罐子，里面装满了成千上万颗弹珠，颜色从漆黑到刺眼的白，中间包含各种深浅不一的灰色。你的目标是将这些弹珠分成不同的组（例如“深色”、“中等”和“浅色”），以便理解它们所构成的画面。

在计算机视觉领域，这种排序过程被称为图像阈值分割。“阈值”就是你在不同色度之间划出的无形界线，用来决定一个组在何处结束，下一个组在何处开始。

以下是使用日常类比对本文内容的简要拆解：

问题：“有多少个？”的困境

大多数传统的弹珠排序方法，就像一位严格的图书管理员，要求你在开始之前必须确切地告诉他需要建造多少个书架（组）。

用户的负担：你必须猜测：“我应该分成 2 组？5 组？还是 10 组？”如果你猜错了，排序结果就会显得杂乱无章。
缓慢的方法：为了找到“最佳”的组数，旧方法会尝试先建 1 个书架，然后是 2 个，接着是 3 个，一直试到 15 个，并检查每一种情况的质量。这就像试穿 15 双不同的鞋子来寻找最合脚的一双——虽然有效，但非常耗时。
随机的方法：一些较新的方法使用“猜测与检查”算法（就像掷骰子）来寻找合适的方案。它们速度很快，但有时会陷入糟糕的境地，或者每次运行时给出不同的结果。

解决方案：“智能排序器”（MET-DP）

本文的作者创造了一种名为MET-DP的新方法。你可以将其想象为一个“智能排序器”机器人，它不需要你告诉它要建造多少个书架。它会观察罐子里的弹珠，并自行计算出最佳的组数。

它是如何工作的（魔法技巧）：

动态规划：机器人不使用从头开始尝试每一种单一组合的方法（这很慢），而是利用一种“智能记忆”技术。它一步步构建解决方案，记住之前做出的最佳选择，因此无需重新计算。这就像在解迷宫时标记你已经走过的路径，以免迷路。
修改后的规则（MET）：机器人使用一套特定的规则书（基于某种称为“最小误差阈值”的概念）来决定何时停止添加新组。
- 旧规则书：如果你不断添加组，得分（从数学角度）总是变得“更好”，因此机器人会无限地添加组，直到每颗弹珠都拥有自己的盒子。这毫无用处。
- 新规则书：作者修改了规则书，使得只有当添加一个组实际上能够分离出不同的弹珠簇时，才被视为“好”。如果你试图将一组相似的弹珠强行拆分只是为了增加一个书架，得分实际上会下降。这告诉机器人：“停下！你已经找到了正确的数量。”

结果：速度 vs. 完美

作者在三种类型的“罐子”（图像）上测试了这个智能排序器：

自然照片（风景、动物）。
卫星照片（城市和农田的地图）。
医疗照片（皮肤病变和脑部扫描）。

以下是他们的发现：

速度：智能排序器是个速度狂魔。因为它在一次单次遍历中就确定了组数，所以它比那些必须分别尝试 1 组、2 组、3 组的旧方法快得多。如果你需要快速处理大量弹珠，这就是获胜者。
找到正确的数量：它非常擅长发现数据中的自然分组。例如，如果一张图片包含深色的天空、灰色的建筑物和白色的云朵，它能正确识别出主要有 3 个组。
“过度分割”的缺陷：有时，机器人会变得过于兴奋。如果弹珠的颜色上有微小的随机凸起（噪声），机器人可能会认为这些凸起很重要，从而创建过多的组。这就像在排序弹珠时，决定将一颗颜色稍深的红色弹珠单独放一个书架，尽管它本质上与其他弹珠并无二致。
“分割不足”的缺陷：相反，有时它会忽略微小但重要的细节，将两个不同的组合并成一个大桶。
图像质量：当作者使用标准指标（SSIM 和 PSNR）测量最终图像质量时，旧方法（即你告诉它们组数的方法）通常能产生稍微更清晰、更“像素完美”的图像。智能排序器非常擅长发现结构，但如果你已经知道需要多少个组，旧方法在保留确切的像素细节方面略胜一筹。

结论

本文介绍了一种工具，它可以自动决定图像需要多少个组，而无需人工干预。

优点：它极其快速，非常适合具有清晰、明显模式的图像。它省去了你猜测正确数量的头痛。
缺点：它有时会被微小的细节（噪声）搞糊涂，可能导致分割过多或过少。此外，如果你的主要目标是获得绝对最高的像素级完美质量，传统的“手动”方法仍然略占优势。

简而言之：如果你需要一种快速、自动的方式来理解图像的整体形状，这种新方法是一个强有力的竞争者。如果你需要手术般的精确度，并且不介意多花一点时间，那么旧的方法可能仍然更好。

技术摘要：一种用于发现多级图像阈值数量与值的动态规划框架

问题陈述
多级图像阈值化是计算机视觉中的基础预处理步骤，通常被表述为一个聚类问题，即将像素强度分离为不同的组。尽管最先进的方法通常依赖于目标函数（例如 Otsu、Kapur、Kittler）和搜索策略来寻找最佳阈值，但一个关键的局限性依然存在：大多数方法要求用户手动指定阈值的数量（ $n$ ）作为输入。确定合适的 $n$ 并非易事，因为 SSIM 和 PSNR 等相似性度量指标本质上倾向于更高数量的阈值以最大化图像保真度，这使得它们不适合用于自动选择最佳 $n$ 。此外，虽然精确搜索策略（如动态规划 DP）能保证在固定 $n$ 下获得最优解，但当用户尝试通过迭代多个候选值来搜索最佳 $n$ 时，它们会遭受运行时间呈指数级增长的困扰。相反，近似的元启发式方法虽然提供了速度，但由于随机性和陷入局部最优的风险，缺乏可靠性。

方法论
作者提出了一种名为MET-DP的新方法，该方法将改进的最小误差阈值（MET）准则与动态规划算法的特定变体相结合。方法论的核心贡献如下：

改进的 MET 准则：作者观察到，传统的目标函数（Otsu、Kapur）随着阈值数量的增加，其数值呈现单调递增，导致它们无法用于自动阈值数量选择。相比之下，Kittler（MET）准则并不随阈值增加而严格递减。作者修改了 MET 准则，允许在成本计算过程中将阈值值同时包含在下类和上类中（一种“重叠”表述），同时在最终的图像分割中保持传统的互斥分配。这一修改创造了一个成本景观，其中最小值可以指示最佳阈值数量，而不会偏向更高的数量。
动态规划变体：与传统的 DP 方法（算法 1）不同，后者将 $n$ 作为输入并计算第 $i$ 个阈值在位置 $j$ 的表 $dp[i][j] $，所提出的算法（算法 2）在区间$ [i, j] $上递归运行。它确定将区间分割为单个类别或在最优点$ k$ 处进行分割的最小成本。递推关系定义为：
$J(i, j) = \min \left( Q(i, j), \min_{k=i+1}^{j-1} \{ Q(i, k) + J(k, j) \} \right)$
其中 $Q$ 是单个类别的成本， $J$ 是总成本。这种结构使得算法能够在单次遍历中同时发现最佳阈值值集合和最佳阈值数量。
复杂度：所提出的算法时间复杂度为 $O(L^3)$ ，空间复杂度为 $O(L^2)$ ，其中 $L$ 是强度级别的数量（例如 256）。作者指出，虽然传统 DP 对于固定的 $n$ 具有 $O(n \cdot L^2)$ 的复杂度，但所提出方法的运行时间相对于阈值数量实际上是恒定的，因为它不需要针对不同 $n$ 值进行迭代运行。

关键结果
MET-DP 方法在包含 15 张图像（自然图像、卫星图像和医学图像）的多样化数据集上进行了评估，并在包含 718 张图像的更大集合上进行了统计分析。

自动阈值选择：MET-DP 成功地为各种图像类型确定了合适的阈值数量。例如，它正确识别出三峰直方图（图像 326085）需要 3 个阈值，而传统方法未能正确分离这些峰。然而，该方法对直方图的微小波动表现出敏感性，导致在某些医学图像中出现“过度阈值化”（例如图像 007-Flair-60 出现了 25 个阈值），而在其他图像中出现“阈值不足”（例如 Tile-8-Part-008 中合并了不同的峰）。
运行效率：在比较测试中，传统方法针对 1 到 15 的阈值数量进行迭代运行，MET-DP 展示了显著更低的总 CPU 运行时间。虽然传统方法的运行时间随测试数量的增加呈多项式增长（ $O(m^2 \cdot L^2)$ ），但 MET-DP 保持固定的运行时间，仅取决于 $L$ 。
分割质量：
- SSIM：MET-DP 取得了具有竞争力的结构相似性指数度量（SSIM）值，通常在具有复杂多峰直方图的图像上（例如自然图像 147091 和 77200701）优于传统方法。
- PSNR：与 Otsu 和 Kapur 相比，该方法产生的峰值信噪比（PSNR）值通常较低。作者将此归因于该方法倾向于分离细微波动，这与传统方法产生的更平滑分割相比，降低了像素级的保真度。

意义与主张
本文声称 MET-DP 提供了一种计算高效、自适应的自动多级阈值化框架。其主要意义在于消除了对用户定义阈值数量的需求，这是自动化视觉流水线中的一个常见瓶颈。作者强调，改进的 MET 准则特别适合此任务，因为与 Otsu 或 Kapur 不同，其数值并不随阈值数量单调增加，从而允许在成本函数中识别出“最佳点”。

作者谦逊地总结道，虽然 MET-DP 在计算效率和自动参数选择方面优于传统方法，但在原始图像重建质量（PSNR）方面并未普遍超越传统方法。他们建议该方法特别适用于需要自动阈值选择且分离细微强度变化至关重要的应用，而传统方法可能仍然更适合优先考虑高 PSNR 或容噪、粗略分割的任务。本文并未提出新的应用，而是将 MET-DP 定位为无监督阈值数量确定这一特定问题的稳健替代方案。

问题：“有多少个？”的困境

解决方案：“智能排序器”（MET-DP）

结果：速度 vs. 完美

结论

类似论文