The*_*kie 5 c algorithm math colors quantization
我正在玩图像处理,并决定阅读颜色量化的工作原理,经过一些阅读后我发现了修正中值切割量化算法.
我一直在阅读Leptonica库中C实现的代码,并且遇到了一些我觉得有点奇怪的东西.
现在我要强调的是,我不是这方面的专家,我不是数学头,所以我预测这一切都归结于我不理解所有这一切而不是算法的实现是错误的一点都不
该算法声明vbox应沿着摘要轴分割,并且应使用以下逻辑进行拆分
通过将bin与中值像素(按群体)定位,选择较长边并在该边的中心划分来划分最大轴.我们可以简单地将具有中间像素的bin放在较短的一侧,但是在细分的早期阶段,这倾向于将低密度簇(在细分中不考虑)放在相同的vbox中作为高密度的一部分即使未来基于中位数的细分,也会以中值vbox颜色进行投票的集群.这里使用的算法在早期细分中特别重要,并且3对于给出可见但低群体颜色群集它们自己的vbox是有用的.这对高密度集群的细分几乎没有影响,最终将在其vbox中具有大致相等的人口.
为了论证,让我们假设我们有一个vbox,我们正在分裂过程中,红轴是最大的.在Leptonica算法中,在01297行,代码似乎执行以下操作
注意:当我说"红色"时,我指的是沿着轴的每个点被迭代覆盖,实际颜色可能不是红色但包含一定量的红色
因此,为了便于说明,假设我们沿红轴有9个"箱"并且它们具有以下种群
4 8 20 16 1 9 12 8 8
在迭代所有红色区后,partialsum数组将包含上述区间的以下计数
4 12 32 48 49 58 70 78 86
而总将有86的值
一旦完成,就应该执行实际的中值切割,而对于红轴,则在线01346执行
它迭代垃圾箱并检查它们累积的总和.这是从算法描述中抛出我的部分.它看起来在第一仓,有一个值,该值大于小于总/ 2
不会总/ 2意味着它正在寻找具有价值比大仓平均数值,而不是中位数？上述垃圾箱的中位数为49
使用43或49可能会对盒子的分割方式产生巨大影响,即使算法然后通过移动到匹配值所在的较大边的中心来进行.
令我困惑的另一件事是该文件规定应该找到具有中值的bin,但是如果存在偶数个bin则不提及如何继续..中位数将是(a +的结果)b)/ 2并且不保证任何垃圾箱都包含该人口数.所以这就是让我觉得有些近似值可以忽略不计的原因,因为分裂实际上是在所选bin的较大边的中心处.
对不起,如果它有点长的啰嗦,但我想尽可能多,因为它已经让我疯了几天了;)
小智 3
在 9-bin 示例中，49 是前 5 个 bin 中的像素数。49 是9 个部分和的集合中的中位数，但我们想要86 个像素的集合中的中位数像素，即 43（或 44），并且它位于第 4 个 bin 中。
对 leptonica 的 colorquant2.c 中修改后的中值切割算法的检查表明，3d 框的实际切割位置不一定出现在包含中值像素的箱附近。函数 MedianCutApply() 中解释了其原因。这是对保罗·赫克伯特原始方法的“修改”之一。另一个重要的修改是根据总体和乘积（总体 * 体积）的组合来决定下一步要切割哪个 3D 框，从而允许分割较大但稀疏的颜色空间区域。