震惊！！！酷家乐商品颜色检索系统首次披露
一、导读
在很多搜索的场景中，我们希望能通过颜色来快速筛选自己中意的结果，比如在电商网站购买衣服时，买家希望筛选出自己偏爱颜色的衣服。对应到酷家乐的工具中，设计师希望能通过颜色筛选出自己想要找的模型，比如在沙发类目下通过红色来召回所有的红色沙发。
二、问题剖析
该问题为典型的Dominant Color问题，什么叫Dominant Color？简单举例：Google有提供一个API可以提取一幅图片的Dominant Colors，其实就是一幅图片的主要颜色。
一般基于图像分割（如硬分割中的K-Means与软分割的代表Fuzzy C-Means）可提取出图片主色。但对于实际的业务问题，我们需要得出人眼观感的主要颜色，这正是问题的难点，因为人眼观感会受到诸如背景色、反光、感兴趣区域等影响。比如
这样一幅图片，分割出的结果会有大占比的灰白色背景以及反射光干扰最终的结果，但人眼一眼望过，留下的印象是这是个蓝色沙发，所以单纯做图片的颜色分割并不能适应我们的业务场景，针对我们的业务问题需要特别处理。
三、算法设计与实现
1. 算法流程
- Resize:：为了加快处理速度，图片统一等比例调整；
- Segment：采用MeanShift和FloodFill进行图片分割；
- Merge：将分割好的图片相同颜色区域合并；
- Gaussian Score：给每个区域进行Gaussian权重打分，然后按打分排序；
- Select：选择我们感兴趣的Dominant Colors；
- Tag：根据给定标准色将分出的主色划分到某一标准色；
2. MeanShift
基本原理
MeanShift，即均值漂移算法，在聚类、图像平滑、分割、跟踪等方面有着广泛的应用。 通俗解释：对于给定的一定数量样本，任选其中一个样本，以该样本为中心点划定一个圆形区域，求取该圆形区域内样本的质心，即密度最大处的点，再以该点为中心继续执行上述迭代过程，直至最终收敛。
Step1 在d维空间中，任选一个点，以该点为圆心，r为半径做一个球(d>2时为高维球)，落在该球内的所有点和圆心可以产生一个向量，向量以圆心为起点以落在球内的点为终点，这些向量都相加，结果就是MeanShift向量。
Step2 再以向量的终点为圆心，再做一个高维球（如下图），重复以上步骤，就可得到一个向量。
Step3 最终，可以收敛到概率密度最大的地方。
当然，MeanShift还可以扩展，比如加入核函数等。
工程实现
生产化实现时基于OpenCV，实现为pyrMeanShiftFiltering，严格来说并不是做图像分割，而是进行图像在色彩层面的平滑滤波，它可以中和色彩分布相近的颜色，平滑色彩细节，侵蚀掉面积较小的颜色区域。
物理空间x, y两维，物理空间漂移半径sp；色彩空间r, g, b三维，色彩空间漂移半径sr。所以该函数在迭代时，不停地在五维球内去计算向量，更新输出图像 上对应的初始原点的色彩值为本轮迭代的终点的色彩值，如此完成一个点的色彩均值漂移。
关键参数：sp, sr，二者设值越大，对图像色彩的平滑效果越明显。举例：
3. FloodFill
基本原理
FloodFill，即漫水填充，是一种用特定的颜色填充联通区域，通过设置可连通像素的上下限以及连通方式来达到不同的填充效果的方法。漫水填充经常被用来标记或分离图像的某些部分以便对其进行进一步处理或分析，也可以用来从输入图像获取掩码区域，掩码会加速处理过程，或只处理掩码指定的像素点，操作的结果总是某个连续的区域。
形象化地解释，可以考虑往一幅图上泼水，把颜色差异明显的区域想像成在边界处有堤坝，当水从某个像素点开始流动，那么很容易浸润相同颜色的像素点（因为同属一个区域），而水将无法流过颜色差异较大的区域。
在这里，我们使用FloodFill只是用来把一块块的颜色区域确定下来！
工程实现
生产化实现时基于OpenCV，实现为floodFill。这里涉及到三个关键参数：
- `maks`：漫水填充不会填充掩模mask的非零像素区域。例如，一个边缘检测算子的输出可以用来作为掩膜，以防止填充到边缘
- `loDiff`：表示当前观察像素值与其部件邻域像素值或者待加入该部件的种子像素之间的亮度或颜色之负差（lower brightness/color difference）的最大值
- `upDiff`：表示当前观察像素值与其部件邻域像素值或者待加入该部件的种子像素之间的亮度或颜色之正差（lower brightness/color difference）的最大值
举例：
- 请忽略FloodFill后图片中的色块颜色，设置的是随机值，进行FloodFill只是为了确定颜色的连通域；
- 比较后面两幅图可以看出，当颜色容差设置的较大时，相近的颜色会被水漫过
4. Merge
经过FloodFill后颜色的连通域已经确定，但即使是相同的颜色，也有可能分布在不同的连通域里，所以要对这些相同的颜色进行合并。举例，如下图中的黄色花区域经过FloodFill之后形成各自的连通域，但其实应该合并为同一种颜色区域。在合并时需要指定合并的色差范围，在一定色差范围内的区域被认定为同一种颜色。
到这一步，对于图片颜色的分割已经完成，剩余的工作是如何找出真正的主色！
5. Gaussian Score
在这一步，我们对合并后的颜色区域进行打分，打分的前提假设是：对于商品的图片，人眼感兴趣的颜色位于图片中央。所以对颜色区域进行权重计算的规则是：离中心越近的像素点其权重越高，权重值按照二维高斯函数求得，任何一个颜色区域最终会得到其区域内所有像素点的分数，将区域内像素点的权重值平均后作为该颜色区域的打分。基于颜色的分数排序，可以得到一幅图片的主要颜色顺序。
6. Select
其实经过第5步的高斯权重打分并排序后，基本上一幅图像的主色排在了前面，只需要按需要取前一个或者前两个就Okay了。但存在问题如下：
- 不同图像主色数目可能不一样，有些图像只有一个主色，有些可能多种，Gaussian Score后不能简单地取TopN来确定主色；
- 除背景外，如果图像存在两种以上的主色，那么靠近中央的颜色色块将占据地理优势而成为主色（即使其他主色的色块大小可能稍大于该色块），提取的主色将会不全！
所以，我们期待有一种选择策略，可以将图片的主色给合理地从分割出的颜色中选择出来，即满足：
- 一幅图至少一种主色；
- 可以动态地找出多种主色；
- 最大可能避免背景色的干扰；
策略如下：
- 对于除Texture和Tile类型外的商品进行背景色剔除，在剔除的过程中动态调整 色差大小，保证最后至少有一种主色存活；
- 剔除存活的颜色区域中较小的色块，在剔除的过程中动态调整 色块大小，保证最后至少有一种主色存活；
最终效果已经比较令人满意。
7. Tag
以上所有的步骤都只是在努力找出该图片的主色，但还有关键的一环，就是为分割出的图片主色打上颜色标签。这一步也至关重要，因为这涉及到色度学里面一个重要概念：色差。所有的色差都应该在CIELab色彩空间下计算！因为在CIELab空间是人眼感知均匀的，RGB就不是。举个例子：
两对颜色单纯计算RGB空间下色差是一样的，但在人眼感知上，第一组两个颜色的差异程度与第二组两颜色差异程度是不一样的！
所以，我们计算色差需要在人眼感知均匀的CIELab空间，而打标的标准色，需满足：
- 靠近的颜色对在CIELab的色差是等距的；
- 尽量覆盖人眼所有识别的颜色范围，粒度可以有粗细，但要满足第一条原则；
这里，我们最终确定使用著名的Pantone色卡。
四、结果展示
这里展示图片的提取主色效果及打标效果，如
- 下方第一行是算法提取出的主色，比如该图片提出出了两种主色；
- 下方第二行是对应标准色中的颜色，标准色的选取会影响最终的打标效果；
单色情况
双色情况
多色情况
基于颜色标签搜索模型
可以看到颜色标签筛选的结果比较令人满意。
五、总结展望
回顾一下在使用颜色标签来检索商品的整个流程中我们做了哪些事情：图片预处理——基于Mean Shift与Flood Fill进行色彩分割——色彩区域合并——色彩区域权重计算——色彩区域筛选——色彩标签划分——搜索引擎索引。可以看到，基于颜色的商品筛选，本质上拆解为了两个子问题：
- 图片主色识别；
- 为图片主色建立标签系统并索引；
本算法基于传统的图像处理算法，已经可以得到相当不错的实际效果，在召回率与准确率上都取得了令人满意的效果。但传统的图像处理算法并不能从语义层面理解图像中的物体并给定其颜色，对于一些特殊情况只能通过归纳或统计的规则进行规避，以后或可考虑从语义层面识别图片主色。
酷家乐模型搜索支撑着用户日常的模型检索，一路走来，得益于算法/工程/产品的充分结合，目前虽然满足与解决了用户的日常搜索需求，但精益求精，我们仍然可以从各个角度去提高改善搜索的质量，以充分满足用户的需求。
六、参考
[1]. http://www.cnblogs.com/mikewolf2002/archive/2013/08/20/3269883.html
[2]. http://blog.csdn.net/dcrmg/article/details/52705087
关注我们
酷家乐质量效能团队热衷于技术的成长和分享，几乎每个月都会举办技术分享活动（海星日），每半年举办一次技术专题竞赛分享（火星日），并将优秀内容写成技术文章。
我们尽可能保障分享到社区的内容，是我们用心编写、精心挑选的优质文章。如果您想更全面地阅读我们的文章，请您关注我们的微信公众号"酷家乐技术质量"。