5

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

我一直在阅读Leptonica 库中的 C 实现代码，遇到了一些我认为有点奇怪的东西。

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

该算法规定vbox应沿最长轴拆分，并应使用以下逻辑拆分

通过定位具有中值像素（按人口）的箱，选择较长的边，并在该边的中心划分最大轴。我们可以简单地将具有中值像素的 bin 放在较短的一侧，但是在细分的早期阶段，这往往会将低密度簇（在细分中不考虑）放在同一个 vbox 中作为高密度的一部分即使未来基于中值的细分，它也会在中值 vbox 颜色中超过它。这里使用的算法在早期的细分中特别重要，3 对于给可见但人口少的颜色簇提供自己的 vbox 很有用。这对高密度集群的细分影响不大，最终将在其 vbox 中具有大致相等的人口。

为了论证的方便，我们假设我们有一个正在拆分的 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

总计的值为86

一旦完成，就该执行实际的中位数切割了，对于红色轴，这是在 01346 行执行的

它遍历箱并检查它们的累积总和。这是算法描述中让我想到的部分。它查找值大于total/2的第一个 bin

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

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

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

对不起，如果它有点啰嗦，但我想尽可能彻底，因为它已经让我发疯了几天了；）

4

2 回答 2

2

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

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

于 2012-02-06T18:02:37.060 回答
0

我不知道算法，但我会假设你的数组包含每个红色的人口；让我们用一个例子来解释一下：

假设您有四个红色渐变：A、B、C 和 D 并且您有以下红色值序列：

AABDCADBBBAAA

要找到中位数，您必须根据红色值对它们进行排序并取中间值：

    median
      v
AAAAAABBBBCDD

现在让我们使用他们的方法：

A:6 => 6 
B:4 => 10
C:1 => 11
D:2 => 13

13/2 = 6.5 => B

我认为发生不匹配是因为您正在计算人口；平均颜色为：

(6*A+4*B+1*C+2*D)/13
于 2012-02-01T14:37:07.783 回答