c - 'Modified Median Cut' 的 Leptonica 实现是否根本不使用中位数？

Question

我正在研究图像处理，并决定阅读颜色量化的工作原理，经过一番阅读后，我找到了 Modified Median Cut Quantization算法。

我一直在阅读 C implementation in Leptonica library 的代码并遇到了一些我认为有点奇怪的事情。

现在我想强调的是，我远不是这个领域的专家，我也不是数学头脑，所以我预测这一切都归结为我没有完全理解，而不是算法完全错误。

该算法说明 vbox 应沿最长轴拆分，并且应使用以下逻辑拆分

The largest axis is divided by locating the bin with the median pixel (by population), selecting the longer side, and dividing in the center of that side. We could have simply put the bin with the median pixel in the shorter side, but in the early stages of subdivision, this tends to put low density clusters (that are not considered in the subdivision) in the same vbox as part of a high density cluster that will outvote it in median vbox color, even with future median-based subdivisions. The algorithm used here is particularly important in early subdivisions, and 3is useful for giving visible but low population color clusters their own vbox. This has little effect on the subdivision of high density clusters, which ultimately will have roughly equal population in their vboxes.

为了论证，让我们假设我们有一个正在 split 的 vbox，并且红轴是最大的。在 Leptonica 算法中，第 01297 行的代码似乎执行以下操作

• 迭代红色的所有可能的绿色和蓝色变化
• 对于每次迭代，它都会将其添加到沿红轴找到的总像素(总体)数量
• 对于每种红色，它对当前红色和之前红色的种群求和，从而为每种红色存储一个累加值

注意:当我说“红色”时，我指的是迭代覆盖的轴上的每个点，实际颜色可能不是红色，但包含一定量的红色

因此，为了便于说明，假设我们在红轴上有 9 个“箱子”，并且它们具有以下人口

4 8 20 16 1 9 12 8 8

在所有红色 bin 的迭代之后，partialsum 数组将包含上述 bin 的以下计数

4 12 32 48 49 58 70 78 86

total 的值为 86

一旦完成，就可以执行实际的中值切割，对于红轴，这是在第 01346 行执行的

它遍历 bin 并检查它们的累计总和。这是从算法描述中抛出我的部分。它会查找第一个值大于 total/2

的 bin

total/2 是否意味着它正在寻找一个值大于平均值而不是中值 ?上述 bin 的中位数为 49

43 或 49 的使用可能会对框的拆分方式产生巨大影响，即使算法随后通过移动到较大框的中心继续进行匹配值所在的一侧..

另一件让我有点困惑的事情是论文指定了应该定位具有中值的 bin，但是没有提到如果有偶数个 bin 如何进行。中位数将是结果(a+b)/2 并且不能保证任何 bin 都包含该人口计数。因此，这就是让我觉得有一些近似值可以忽略不计的原因，因为拆分实际上是如何在所选 bin 的较大侧的中心进行的。

对不起，如果它有点长，但我想尽可能彻底，因为它已经让我发疯了几天;)

Answer 1

在 9-bin 示例中，49 是前 5 个 bin 中的像素数。 49 是 9 个部分和的集合中的中位数，但我们想要 86 个像素的集合中的中位数像素，即 43(或 44)，并且它位于第 4 个箱子中。

检查 leptonica 的 colorquant2.c 中修改后的中值切割算法表明，3d 框的实际切割位置不一定与包含中值像素的 bin 相邻。其原因在函数 medianCutApply() 中进行了解释。这是对 Paul Heckbert 原始方法的“修改”之一。另一个重要的修改是根据人口和产品(人口 * 体积)的组合来决定接下来要切割哪个 3d 框，从而允许分割大而稀疏的颜色空间区域。