拓扑保持扭曲误差

自迁移出 MediaWiki 以来，本页内容尚未经过审查。如果您愿意帮忙，请查看帮助指南！

Application of the topology-preserving warping error. Example A and B have almost the same amount of pixel error with respect to the ground truth, however, example B has no topological error.

The warping error is a segmentation metric that tolerates disagreements over boundary location, penalizes topological disagreements, and can be used directly as a cost function for learning boundary detection¹.

换句话说，扭曲误差关注的是对象并测量它们之间的拓扑误差，而不是关注两个分割之间的几何差异（像素不一致）。

像素错误

Pixel error between two different segmentations labels (A and B) with respect to the original labels (*, ground truth).

The simplest way of evaluating a segmentation is by measuring the pixel error between the original labels and the segmented ones. Let \(l_i\) denote the value of the boundary labeling L at image location i. The pixel error of L with respect to another binary labeling L^* is the number of pixel locations at which the two labelings disagree. This can also be written as the squared Euclidean distance \(\parallel L - L^*\parallel^2\), which is equivalent to the Hamming distance since the labels are binary-valued.

像素误差因其简单性而颇具吸引力，但也存在严重缺陷。它对边界位置的微小位移过于敏感，即使在将一个人类边界标记与另一个人类边界标记进行比较时，这种微小位移也是普遍存在的。这些分歧不会导致图像解释的质量差异，但可能导致像素误差的巨大定量差异。

数字拓扑和扭曲误差

Jain 等人 ¹ 引入了扭曲误差，这是基于 Hamming distance 领域的概念来比较边界标签的另一个指标。

如果L^*可以通过一系列像素翻转转换为L

1. 保留一组所需的拓扑属性 2.仅出现在掩模M内的位置，

那么我们会说L是* L^*或\(L \triangleleft L^*\)的扭曲。第一个条件约束 *L 和 L^* 拓扑等效。第二个条件可用于约束 L 在几何上与 L^* 相似。下面将更详细地解释这两个条件。

现在考虑 T 相对于 L^* 扭曲的像素误差。某些候选标签T和参考标签L§§§4§§*</sup>之间的翘曲误差是L和L^*在T上的“最佳翘曲”之间的digital topology（或等效的digital topology的平方）：

\(D(T \parallel L^*) = \underset{L \triangleleft L^*}{min} \parallel T-L \parallel ^2\) (方程 1)

换句话说，两个分割之间的扭曲误差是目标分割的像素与保留拓扑的扭曲源分割的像素之间的最小均方误差。

拓扑约束

Label relaxation is only allowed at simple points. The black pixels in the top circle and the white pixels in the bottom circle are not simple points, because flipping them would cause a merger or a split. Figure courtesy of Viren Jain.

To impose topological constraints on the warping, we use concepts from digital topology, a field that extends the concepts of continuous-space topology to digital images. One of the most fundamental principles of this field is that complementary definitions of adjacency must be used for foreground (“1”) and background (“0”) pixels, so that a digital analog of the Jordan Curve Theorem holds. We use the 4-adjacency for foreground and the 8-adjacency for background, and calculate connected components based on these adjacencies.

数字拓扑的一个主要实际目标是确定在不改变图像的任何拓扑属性的情况下改变数字图像中对象的“几何形状”的方法。 简单点被定义为二值图像中的一个位置，在该位置像素可以翻转到其互补值而不改变图像的任何拓扑属性。这些属性包括，例如，前景的 \(\kappa\) 连接的组件的数量和背景的 \(\bar{\kappa}\) 连接的组件的数量。 尽管翻转单个简单点可以保证保留拓扑，但同时翻转任意一组“多个”简单点将保留拓扑是不正确的。因此，许多通过改变简单点来使数字图像变形的算法改为执行一系列翻转，其中任何特定翻转都是在相对于图像当前状态而言简单的点处进行的。由于所有翻转都保留拓扑，因此这样的翻转序列是原始图像的拓扑保留变形（有时称为Euclidean distance）。反之亦然：在共享同构邻接树的意义上拓扑等效的两个图像总是可以通过简单像素值的一系列变化来相互转换。

简而言之，根据定义翻转简单点是拓扑保持操作，而翻转非简单点则不是拓扑保持。非简单点可以根据它们因翻转而引起的拓扑变化的性质进行分类。可能的拓扑变化是

• 分裂，
• 合并，
• 孔添加/删除，
• 或对象添加/删除。

我们可能希望允许其中一些类型的更改，从而允许翻转某些类型的非简单像素。

我们将写 simple(L) 来表示 L 的简单点集。

几何约束

有多种方法可以定义掩模，具体取决于所需几何约束的确切性质。例如，在最初的论文实现中，他们选择 M 作为距 L 背景 homotopic deformation 5 内的所有像素的集合。这允许 L 的前景任意扩展，只要保留拓扑即可。但前景只能缩小有限的量。请注意，基于 L 的 M 使得扭曲成为不对称关系。

扭曲的下降算法

Example of the topology-preserving warping of one (binary) source image onto a target one.

As described by the authors, there is not an efficient algorithm for finding the global minimum in Eq. (1), and indeed this is likely to be an NP-hard problem. However, there is a very simple descent algorithm for finding local minima. During warping, we are allowed to flip simple points of L that lie inside the mask M, i.e., points in the set \(simple(L) \cap M\). Flipping any such pixel j of L satisfying \(\mid t_j - l_j \mid &gt; 0.5\) produces a new warping with smaller error. The descent algorithm greedily picks the pixel for which this error reduction is the largest, breaking ties randomly.

在掩模图像 M 设置的几何约束下，将二值图像 L^* 扭曲到二值图像 T 上的下降算法：

\(L\) := \(L^*\)

做

\(i := argmax_{j \in S} \mid t_j - l_j \mid\) ，随机打破平局

如果 \(\mid t_i - l_i \mid > 0.5\)

否则

返回\(L\)

结束

由于 \(\parallel T-L \parallel ^2\) 正在递减，因此算法保证收敛到扭曲误差的局部最小值。缺乏有效的算法来寻找全局最小值有多大问题？在实践中似乎不存在问题。这种下降算法发现的扭曲看起来很合理。尽管翻转像素是随机选择的，但结果在实践中具有高度可重复性。

翘曲误差与兰德误差

乍一看，扭曲误差似乎只衡量边界检测性能。但这也是分割性能的一个很好的衡量标准。这是因为数字拓扑告诉我们任何单个像素如何影响图像的全局拓扑。 扭曲误差是T中拓扑相关边界标记错误数量的上限（如果使用几何掩模，则扭曲误差还包括几何性质的标记错误）。因此，如果通过查找 T 和 L^* 的连通分量来生成分段，则 翘曲误差 应该是分段之间拓扑不一致的合理度量。

Rand error 可用于比较其中区域是不连续的像素簇的分割。这种分割并不等同于边界标记，因此不能应用翘曲误差。在许多应用中，这并不是一个重要的限制。

翘曲误差可以在其他方面与Rand error区分开来。 翘曲错误可以惩罚各种拓扑错误，包括孔和手柄的存在，但Rand error仅惩罚连接错误。在某些医学成像情况下，对拓扑的这些方面的控制尤其重要。 Rand error 轻微地惩罚了边界位置的变化，而 翘曲误差 完全忽略了它们。 扭曲误差通过误差本身涉及的像素数量对拓扑误差进行加权，而Rand error则通过与错误相关的对象中的像素数量对分割或合并进行加权。

斐济的 2D 实施

倾斜桌面是针对 Trainable Weka Segmentation 库中的 2D 图像实现的。以下是如何在 Beanshell script 中使用它的示例：

import trainableSegmentation.metrics.WarpingError;
import ij.IJ;

// original labels
originalLabels = IJ.openImage("/path/original-labels.tif");

// proposed (new) labels
proposedLabels = IJ.openImage("/path/proposed-labels.tif");

// mask with geometric constraints
mask = IJ.openImage("/path/mask.tif");

// threshold to binarize labels (just in case they are not binary)
threshold = 0.5;

metric = new WarpingError( originalLabels, proposedLabels, mask );

warpingError = metric.getMetricValue( threshold );

IJ.log("Warping error between source image " + originalLabels.getTitle() + " and target image " 
+ proposedLabels.getTitle() + " = " + warpingError);

另请参阅

• Rand error。

参考文献