传奇网站免费空间,网店装修店面,广告公司可以做网站吗,免费服务器安全软件前言
之前想对图片素材进行分类管理#xff0c;除了打标签#xff0c;还有一样是通过主题色进行分类。于是开始寻找能提取主主题色的工具#xff0c;最后找到了大名鼎鼎的 Leptonica 库#xff0c;其中就有中位切割算法的实现。下面附上中位切割算法的其它语言版本的实现。…前言
之前想对图片素材进行分类管理除了打标签还有一样是通过主题色进行分类。于是开始寻找能提取主主题色的工具最后找到了大名鼎鼎的 Leptonica 库其中就有中位切割算法的实现。下面附上中位切割算法的其它语言版本的实现。
JavaScript版quantize 此库有提取颜色数量不对的问题见 issues/9Java版theme-color 我自己基于 quantize 实现的Java版
中位切割算法Median cut
theme-color 项目的效果如下 讲中位切分法之前我们先聊聊颜色该如何描述。
颜色模型
常见的颜色模型有RGBHSV等中位切分法基于 RGB 模型。RBG 模型是一种加色模型将红Red、绿Green、蓝Blue三原色的色光以不同的比例相加以合成产生各种色彩光。每个像素由24位编码的RGB值表示使用三个8位无符号整数0到255表示红色、绿色和蓝色的强度所以RGB能表示1677万256∗256∗256万种颜色。如果将所有的颜色采用三维空间来进行描述则如下图所示 算法实现
中位切割算法Median cut 是Paul Heckbert于1979年提出来的算法。原理是将图像颜色映射成三维色彩空间中的长方体沿着RGB中最长的一边从颜色数量统计的中位数一切为二使得到的两个长方体所包含的像素数量相同重复上述步骤直到得到想要数量的长方体。
原理很简单但是 Leptonica 的实现包含了很多细节。
压缩颜色总数
算法需要统计图像的每种颜色的数量色彩分布图也就是需要将三维的长方体映射到一维的数组中RGB 总颜色数量达到1677万 (2^8 * 2^8 * 2^8)这在检索的时候会造成不小的性能开销。如果将8位无符号整数0到255压缩到5位无符号整数0到31那么总数量减少到 2^5 * 2^5 * 2^5 32768而且可以使用 int 来表示数组下标了。
中位切分的优化
在原始的中位切分法中是沿着颜色数量统计的中位数将长方体vbox一切为二的Leptonica 中对此进行了优化改成通过中位数将 vbox 分为左右两个vbox只是分出左右还未切割然后从左右选出体积较大的vbox的中点进行切割。下面放上作者原话 Determine the cut planes, making sure that two vboxes are always produced. Generate the two vboxes and compute the sum in each of them. Choose the cut plane within the greater of the (left, right) sides of the bin in which the median pixel resides. Here’s the surprise: go halfway into that side. By doing that, you technically move away from “median cut,” but in the process a significant number of low-count vboxes are produced, allowing much better reproduction of low-count spot colors. 长方体体积大包含像素少问题
存在某些条件下 VBox 体积很大但只包含少量像素。解决的方法是每次切分前先对所有 vbox 排序再取出优先级最高的 vbox 进行中位切分。如果需要切割的 vbox 总数为 total那前 total * FractByPopulation 个 vbox 以 vbox包含的像素数 排序后 total * (1-FractByPopulation) 个 vbox 以 包含像素数 * vbox体积 排序。
FractByPopulation的值在 Leptonica 库中为 0.85在 quantize 库中为 0.75
总结
本文介绍了中位切割算法以及在 Leptonica 库中的实现。
参考资料
三原色光模式 - 维基百科自由的百科全书 (wikipedia.org)
中位切割算法 - 维基百科自由的百科全书 (wikipedia.org)
图像主题色提取算法_mmcq算法_mingo_敏的博客-CSDN博客
