OpenCV 中 K-Means 聚类算法解析：从 T 恤尺码问题到 kmeans() 源码实现

OpenCV 中 K-Means 聚类算法解析从 T 恤尺码问题到 kmeans() 源码实现【免费下载链接】opencvOpen Source Computer Vision Library项目地址: https://gitcode.com/GitHub_Trending/opencv31/opencv本篇围绕 OpenCV 官方教程 Understanding K-Means Clustering 展开先通过经典的 T 恤尺码问题直观理解 K-Means 聚类的思想与迭代流程再对照当前仓库中kmeans()的真实实现kmeans.cpp、core.hpp深入解读函数参数、收敛判据与初始化策略。读完后你既能讲清楚 K-Means 为什么这样工作也能直接上手调用 OpenCV 的聚类接口并完成颜色量化等工程应用。1. 核心思想T 恤尺码问题K-Means 是一种无监督聚类算法目标是在已知簇数 K 的前提下把数据划分成 K 个组使组内样本尽可能聚集。官方教程用一个常见的例子来建立直觉假设一家公司要发布新款 T 恤显然需要按不同尺码生产以满足所有人。公司收集了人们的身高与体重数据并将其绘制到二维图上公司不可能为每一种身材都造一种 T 恤而是把人群划分为 Small、Medium、Large 三组只生产这 3 个尺码来覆盖所有人。这种把人群分成三组的分组操作正是 K-Means 聚类要解决的问题算法会给出最优的 3 个尺码以覆盖所有人如果 3 组不够用公司可以把人群再细分为 5 组甚至更多——这就是参数 K 的作用。2. K-Means 的迭代流程逐步骤图解K-Means 是一个迭代算法。下面沿用教程中的数据点集可以把它理解为上面 T 恤问题的抽象数据目标是将数据聚成两组。Step 1随机初始化质心。算法随机选取两个质心 $C1$ 和 $C2$有时也会直接取两个已有数据点作为质心。Step 2最近邻标记。计算每个数据点到两个质心的距离若某测试数据离 $C1$ 更近则标记为 0若离 $C2$ 更近则标记为 1如果有更多质心则继续标记 2、3……。在本例中0 标记的点用红色绘制1 标记的点用蓝色绘制得到如下初始标记结果Step 3重算质心。分别计算所有蓝色点和所有红色点的平均值这两个均值点就是新的质心即 $C1$ 和 $C2$ 平移到新计算出的位置注意教程中的图片并非真实数值、也不成比例仅用于示意。随后用新质心重新执行 Step 2再次把数据标记为 0 和 1如此反复Step 2 与 Step 3 不断交替执行直到两个质心收敛到固定点为止。也可以由调用方提供停止条件来提前终止例如达到最大迭代次数或达到指定精度等。收敛后的质心具有这样的性质测试数据到其对应质心的距离之和最小即 $C1 \leftrightarrow Red_Points$ 与 $C2 \leftrightarrow Blue_Points$ 的距离和最小$$\text{minimize } J \sum_{All: Red_Points} distance(C1, Red_Point) \sum_{All: Blue_Points} distance(C2, Blue_Point)$$最终聚类结果大致如下需要说明的是上面只是对 K-Means 聚类的直观理解教程原文明确称其为 top layer即最表层概念。围绕该算法还有很多改进变体例如如何更好地选择初始质心、如何加速迭代过程等——OpenCV 的实现正体现了这些改进见第 4、5 节。3. OpenCV 中的 K-Meanskmeans() API在 OpenCV 中K-Means 聚类由核心模块的cv::kmeans函数实现声明位于 core.hppdouble kmeans( InputArray data, int K, InputOutputArray bestLabels, TermCriteria criteria, int attempts, int flags, OutputArray centers noArray() );函数文档说明同样见 core.hppdata参与聚类的数据。必须是float坐标的 N 维点数组例如Mat points(count, 2, CV_32F)、Mat points(count, 1, CV_32FC2)或std::vectorcv::Point2f points(sampleCount)K要划分的簇数对应教程里的3 个尺码或2 组数据bestLabels输入/输出整数数组存储每个样本的簇索引。输出时bestLabels_i为第i行样本对应的0 起始簇号criteria终止判据即最大迭代次数和/或期望精度。精度由criteria.epsilon指定当某次迭代中每个簇质心的移动距离都小于criteria.epsilon时算法停止——这正是教程第 2 节描述的质心收敛到固定点的量化版本attempts以不同初始标记重复执行算法的次数函数返回具有最佳紧凑度compactness的那一次结果flags初始化/标记策略见下文KmeansFlags枚举centers可选输出矩阵每行一个簇质心返回值每次 attempt 计算紧凑度度量 $\sum_i | samples_i - centers_{labels_i} |^2$函数返回其中最差最小值。文档还指出可以把该函数当作核心引擎使用——设置attempts 1、每次用自定义算法初始化 labels 并以KMEANS_USE_INITIAL_LABELS标志传入就能在外部挑选最紧凑的聚类方案。3.1 数据格式与边界约束源码确认从 kmeans.cpp 的kmeans_实现可以直接读到硬性约束CV_Assert( data0.dims 2 type CV_32F K 0 ); CV_CheckGE(N, K, There cant be more clusters than elements);即输入数据只能是CV_32Ffloat32矩阵维数不超过 2支持N×dims或1×N的行向量形式簇数 K 不能大于样本数 N。教程第 2 节随机选两个质心的 Step 1在实现中对应先扫描全部样本求出各维度的取值区间 box再在 box 内随机生成 K 个初始质心的逻辑而在 K1 的退化情形下实现会把attempts强制为 1、迭代上限强制为 2直接结束。3.2 flags三种初始质心策略kmeans的 flags 参数对应 core.hpp 中的KmeansFlags枚举标志值含义KMEANS_RANDOM_CENTERS0每次尝试都随机选取初始质心教程 Step 1 描述的基础行为KMEANS_PP_CENTERS2使用 Arthur Vassilvitskii 提出的 k-means 质心初始化KMEANS_USE_INITIAL_LABELS1首次可能也是唯一一次尝试时直接使用用户提供的标记而不从初始质心计算后续尝试则改用随机或半随机质心其中KMEANS_PP_CENTERS对应的是教程Additional Resources部分提到的经典改进——如何选择初始质心。源码中该路径调用generateCentersPP(data, centers, K, rng, SPP_TRIALS)SPP_TRIALS 3即跑 3 轮 k-means 抽样再取较优者这比纯随机初始化更不容易落入差局部最优。3.3 收敛判据与紧凑度实现里对TermCriteria有如下默认处理kmeans.cpp若判据类型包含EPSepsilon会被先与 0 取大再平方即与源码中计算质心位移平方的方式对齐否则取FLT_EPSILON若判据类型包含COUNTmaxCount被限制在[2, 100]区间否则默认为 100每轮迭代结束后检查isLastIter (iter MAX(criteria.maxCount, 2) || max_center_shift criteria.epsilon)——最大迭代次数或质心位移平方小于 epsilon二者满足其一即停止。每次迭代内部的执行顺序对应教程 Step 2/3重算质心按当前 labels 把样本累加到所属簇除以计数得到新质心同时统计max_center_shift所有质心相对旧位置位移平方的最大值重新标记调用KMeansDistanceComputer计算每个样本到各质心的距离并更新 labels该步骤通过parallel_for_并行执行并行粒度由环境变量参数控制static int CV_KMEANS_PARALLEL_GRANULARITY (int)utils::getConfigurationParameterSizeT(OPENCV_KMEANS_PARALLEL_GRANULARITY, 1000);即可以通过OPENCV_KMEANS_PARALLEL_GRANULARITY调整kmeans的并行块大小默认 1000。收敛后各次 attempt 的紧凑度compactness Σ dists[i]即样本到其质心距离平方和的总和进行比较保留最小紧凑度对应的 labels、centers 与紧凑度值作为最终返回结果。这一多次尝试取最优的设计正是应对 K-Means 对初始质心敏感、易陷局部最优这一固有短板的工程手段。3.4 测试与示例入口单元测试位于 test_math.cpp对kmeans各类 flags 组合与收敛行为做了验证性能基准位于 perf_math.cpp头文件注释中引用的官方示例为samples/cpp/snippets/kmeans.cpp与samples/python/snippets/kmeans.pyPython 侧即cv2.kmeans可用于直接复制运行。4. 实践建议与小结K 的选取教程 T 恤例子中先分 3 组不够再细分到 5 组的做法对应工程上通过业务指标如颜色量化后的视觉质量或轮廓系数等离线指标选择 KK 越大模型越复杂调用前的数据准备数据必须转为CV_32FK 不能超过样本数 N颜色量化等场景下通常把每个像素的 BGR 通道展开为一条 3 维样本想要更好的初始质心优先使用KMEANS_PP_CENTERS想完全控制初始化流程时可用KMEANS_USE_INITIAL_LABELS把函数当作纯迭代引擎收敛行为criteria的epsilon控制质心移动量阈值maxCount被实现钳制在 [2, 100] 内attempts越大越可能逼近全局最优但耗时线性增加。小结本文档给出的 T 恤问题与四步迭代图解完整对应了 OpenCVkmeans()实现中的随机初始化 → 最近质心标记 → 均值重算质心 → 按 epsilon/最大迭代收敛 → 多次 attempts 取最小紧凑度的执行链路。理解了这条链路你就能在颜色量化、向量分组、数据压缩等场景中正确地配置K、criteria、attempts与flags并解释每次迭代究竟改变了什么。【免费下载链接】opencvOpen Source Computer Vision Library项目地址: https://gitcode.com/GitHub_Trending/opencv31/opencv创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考