曾杰，周晋，陈雨*

（1.四川大学电子信息学院智能控制研究所，四川 成都 610065；2.四川大学制革清洁技术国家工程实验室，四川 成都 610065）

引言

在时尚行业，色彩趋势是影响消费者购买决定的重要工具和重要因素[1]。随着国内的微博、抖音和国外的Facebook 等社交网络服务的发展，消费者对与色彩趋势相关的关键词和话题标签越来越敏感[2]，因此拥有时尚品牌的公司寻求利用这种关注度来增加商品销售额[3]。通常时尚行业的色彩趋势以自上而下的方式受到影响，因为趋势是在行业内设定的，然后通过在主要的时尚中心城市，如巴黎、纽约、米兰和伦敦发散开来。Divita 在《Fashion Forecasting》一书中也提及到大部分时尚企业经常聘请顾问或订阅色彩趋势分析报告[4]。

综上所述，色彩搭配是流行趋势分析的一个重要元素，通常来说，读取鞋类图片中的像素点的RGB 值就可轻松取得鞋体的颜色搭配，但这样简单操作得到的色彩结果与图片中鞋体的像素点呈正相关，因此本研究使用最常用的聚类算法K-means[5]来识别鞋体的H 种主要色彩。

方法

K-means 聚类方法属于特定理论分割，其随机选择初始聚类中心，通过对初始聚类中心进行聚类运算来将像素分类。初始聚类中心数量和位置的选择，直接影响到后续聚类的结果。定一个数据集X，K-means 的目标是通过最小化平方差（SSE）将X 划分到K 个互斥的聚类S 中，其中SSE 由式1 表示

式中，||.||2表示欧式距离的L2 范数，是聚类的中心，用于计算每个点到聚类中心的均值。当K=2 或D=2 时，这是一个非确定性多项式问题，但是Lloyd 给出了一个简单的解法[6]：从N 个点中任意选取K 个点作为初始中心，然后计算每个点到每个中心点的欧式距离并将其划分给距离最小的类，根据分类结果重新计算新的聚类中心。重复这两个步骤直到满足预定义的终止条件位为止。

对于固定的D，K-means 算法的时间复杂度是每次迭代o(NK)，在本研究的颜色聚类算法中使用CIELab 色彩空间[7]，D 等于3。K-means 的主要缺点是它经常在一个局部最小值终止，并且它的输出对集群中心的初始选择很敏感。从颜色量化的角度来看，K-means 还有两个额外的缺点。首先，尽管它具有线性时间复杂度，但迭代的算法使得色彩板在生成阶段的计算成本很高。其次，像素映射阶段是低效的，因为对于每个输入像素，都需要对色彩板进行完整的搜索，以确定最接近的颜色。相比之下，预聚类方法通常在一个特殊的数据结构中操作和存储调色板（通常使用二叉树），这允许在映射阶段进行快速最近邻搜索。本研究使用三种加速方法在一定程度上缓解上述缺点。

（1）数据采样

加快K-means 的一个直接的方法是减少数据量，可以通过对输入的图像数据进行采样来实现。在本研究中，使用了两种确定性的子抽样方法。第一种方法在水平和垂直方向上进行2:1 的子采样，只考虑输入图像像素的1/4。这种适度采样在不降低量化质量的情况下能有效地减少计算时间。第二种方法是只对具有独特颜色的像素进行采样。这些像素可以使用一个哈希表来有效地确定，该哈希表使用链表来处理哈希冲突，其哈希函数的形式为其中x=(x1，x2，x3)表示像素点的Lab色彩空间的三个维度取值，m 为素数，序列a=(a1，a2，a3)的元素从集合{0，1，…，m-1}中随机选取。第二种基于哈希的采样方法进一步减少了图像数据，因为图像中通常包含大量重复的颜色。

（2）样本加权

上述第二个基于哈希的采样方法的一个重要缺点是忽略了原始图像的颜色分布。为了解决这个问题，每个点都被分配了一个与其频率成比例的权重。事实上这个加权过程实际上生成了一个一维的颜色直方图。然后根据图像中的像素数量对权重进行归一化，以避免计算中的数值不稳定性。此外，对经典K-means 算法进行了改进，将权值加入到聚类迭代过程中。

（3）均值排序(sort-means)算法[8]

K-means 的分配阶段涉及到许多冗余的距离计算。对于每个点计算到每个K 聚类中心的距离。考虑两个聚类中心ca，cb和一个距离d，利用三角不等式，我们可以得到d(ca，cb)≤d(xi，ca)+d(xi，cb)。因此，如果我们已知2d(xi，ca)≤d(ca，cb)，我们不需要计算d(xi，cb)就可以得出d(xi，ca)≤d(xi，cb)。均值排序该算法在为每个点寻找最近的聚类中心时，通过对每个集群中心关联的距离值进行升序排序，并借助三角不等式检验避免了大量的距离计算，进一步减少了距离计算的数量。在每次迭代中，点与聚类中心的距离按距离的顺序递增进行比较。如果一个中心点距离足够远，则跳过其余所有中心点，继续进行下一个点。通过这种方式，均值排序算法避免了去计算所有距离中心。

本研究将朴素版的K-means 算法称为KM，使用了上述三种预处理算法的K-means 算法称为WSM，WSM 算法的伪代码由算法1 表述。

算法1 WSM算法伪代码

结果与讨论

选用3 张典型的运动鞋、板鞋和靴子进行色彩搭配校验（图1），量化方法的效率是通过CPU 时间(以ms 为单位)来衡量的，其中包括调色板生成和像素映射阶段所需的时间，所有时间数据均取100 次平均。

两种算法都以相同的随机中心初始化，并在20 次迭代后终止，表1 给出了K=32,64 在测试图像上每个像素的计算距离次数和计算时间。对于KM,计算距离次数总是等于调色板大小K，因为最近邻搜索涉及到对每个输入像素的调色板的完整搜索。相比之下，WSM 需要的距离计算平均要少约9-12 倍，这是由于灵活的引用了三角形不等式，在几次迭代之后，一旦聚类中心稳定下来，就可以避免许多计算。其他大多数KM 加速方法都会产生创建和更新辅助数据结构的开销。这意味着在运算时间上运用了加速算法的K-means 相对于朴素版K-means 计算每一个距离的速度要更慢。但是表1 显示WSM 不是这样的，因为它通过利用原始图像中的颜色冗余信息来减少聚类阶段之前的数据量。可以看出，WSM 实际上比KM 快9-14 倍左右。特别是特定图像的速度与图像中惟一颜色的数量成反比。因此，最明显的计算加速效果出现在总体基础色较少的鞋类图片上，如运动鞋和靴子其基础色偏少，因此加速效果也更好（运动鞋：K=32 时WSM比KM 快14.11 倍；靴子：K=32 时WSM 比KM 快10.77 倍）。综上所述，WSM 能在保证输出性能等效的情况下，显著提高K-means 的性能。

表1 KM与WSM的性能对比

将鞋身图片的每一个像素点导入Lab 色彩空间中，可以得到该鞋身的色彩分部图，若将这些像素点划分到M 个聚类中，则每个聚类可由式2 表示

使用K-means 算法进行M 个聚类的迭代计算表征鞋身的色彩模型，图2 展示了一个基础色相对丰富的运动鞋在M=6 时的鞋身聚类颜色分布示意图。图2 显示，6 个色彩聚类结果已经能很好的识别该单张鞋类图片的所有基础色彩构成和每个基础色彩的比例信息。该方法对大数据鞋类图片进行色彩构成分析后，结合销量等信息可用于消费者对于鞋类色彩选择偏好的分析与预测。

结论

本研究使用K-means 算法对色彩进行聚类识别鞋身色彩搭配，同时针对朴素版K-means 算法效率低下的缺点，融入了多种预处理算法，使得取不同K 时，K-means 聚类算法的效率高了9～14 倍。单鞋的识别结果显示，改进后的K-means 聚类算法能很好的识别鞋身的主要基础色彩和每种基础色彩的比例，这些提取出来的色彩搭配数据可用作分析鞋类流行趋势的关键信息。