#P3842. 第2题-Yolo检测器中的anchor聚类
-
1000ms
Tried: 783
Accepted: 240
Difficulty: 5
所属公司 :
华为
时间 :2025年9月28日-AI方向
-
算法标签>K-means 聚类
第2题-Yolo检测器中的anchor聚类
解题思路
本题要求用 K-means 在宽高空间对检测框进行聚类,以获得 YOLO 的 Anchor 尺寸。与欧氏距离不同,这里采用 d = 1 − IOU 作为距离度量,能更贴近目标检测中对宽高匹配的要求。
算法选择与要点
-
初始化(稳定初始化):直接取前 K 个框作为初始聚类中心(宽、高)。
-
分配阶段:对每个样本框 (w,h) 计算到所有中心 (Wk,Hk) 的距离
d=1−IOU((w,h),(Wk,Hk))其中
$$\text{IOU}=\frac{\min(w,W_k)\cdot \min(h,H_k)}{w\cdot h + W_k\cdot H_k - \min(w,W_k)\cdot \min(h,H_k) + 1e-16} $$将样本分配给距离最小的簇。
-
更新阶段:对每个簇计算所有成员在宽、高上的均值并向下取整(floor),作为新的中心。如果某簇为空,则保留原中心不变。
-
终止条件:最多迭代 T 次;或当新旧中心配对的 d 值之和
$$\sum_{k=1}^{K} \left(1-\text{IOU}\big((W_k^{old},H_k^{old}),(W_k^{new},H_k^{new})\big)\right) < 1e-4 $$时提前停止。
-
输出:将最终 K 个中心按面积(宽×高)从大到小排序输出。 注意:迭代中每次更新的中心与最终输出都要向下取整,但 IOU 与 d 的计算始终用浮点数(避免精度问题,分母加 1e−16)。
该流程等价于在“宽高-IOU”空间上的 K-means 变体,常用于 Anchor 聚类以提升先验框与真实框的匹配度。
代码实现
Python
import sys
import math
# 计算两个宽高框的 IOU(基于宽高,无位置信息)
def iou_wh(w1, h1, w2, h2):
inter = min(w1, w2) * min(h1, h2)
union = w1 * h1 + w2 * h2 - inter
return inter / (union + 1e-16)
# 使用 d = 1 - IOU 的 K-means 聚类,返回最终中心(整数)
def kmeans_anchors(boxes, K, T):
# 初始化:取前 K 个框为初始中心(转为浮点便于计算)
centers = [(float(boxes[i][0]), float(boxes[i][1])) for i in range(K)]
n = len(boxes)
for _ in range(T):
# 分配阶段:为每个样本选择最近中心
assign = [0] * n
for i, (w, h) in enumerate(boxes):
best_k = 0
best_d = 1.0 - iou_wh(w, h, centers[0][0], centers[0][1])
for k in range(1, K):
d = 1.0 - iou_wh(w, h, centers[k][0], centers[k][1])
if d < best_d:
best_d = d
best_k = k
assign[i] = best_k
# 更新阶段:计算新中心(对均值向下取整)
sums = [[0.0, 0.0] for _ in range(K)]
cnts = [0] * K
for (w, h), k in zip(boxes, assign):
sums[k][0] += w
sums[k][1] += h
cnts[k] += 1
new_centers = []
for k in range(K):
if cnts[k] == 0:
# 空簇:保留原中心
new_centers.append((centers[k][0], centers[k][1]))
else:
W = math.floor(sums[k][0] / cnts[k])
H = math.floor(sums[k][1] / cnts[k])
new_centers.append((float(W), float(H)))
# 终止条件:新旧中心 d 值之和
change = 0.0
for k in range(K):
change += (1.0 - iou_wh(centers[k][0], centers[k][1], new_centers[k][0], new_centers[k][1]))
centers = new_centers
if change < 1e-4:
break
# 最终结果向下取整并按面积从大到小排序
final_centers = [(int(math.floor(w)), int(math.floor(h))) for (w, h) in centers]
final_centers.sort(key=lambda x: x[0] * x[1], reverse=True)
return final_centers
def main():
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
N = int(next(it)); K = int(next(it)); T = int(next(it))
boxes = []
for _ in range(N):
w = float(next(it)); h = float(next(it))
boxes.append((w, h))
centers = kmeans_anchors(boxes, K, T)
out = []
for w, h in centers:
out.append(f"{w} {h}")
print("\n".join(out))
if __name__ == "__main__":
main()
Java
import java.io.*;
import java.util.*;
/* ACM 风格,读取输入,输出结果;核心逻辑放在静态函数里 */
public class Main {
// 计算宽高框的 IOU
static double iouWH(double w1, double h1, double w2, double h2) {
double inter = Math.min(w1, w2) * Math.min(h1, h2);
double union = w1 * h1 + w2 * h2 - inter;
return inter / (union + 1e-16);
}
// d = 1 - IOU 的 K-means 聚类
static int[][] kmeansAnchors(double[][] boxes, int K, int T) {
int N = boxes.length;
// 初始化:前 K 个样本
double[][] centers = new double[K][2];
for (int k = 0; k < K; k++) {
centers[k][0] = boxes[k][0];
centers[k][1] = boxes[k][1];
}
for (int t = 0; t < T; t++) {
int[] assign = new int[N];
// 分配阶段
for (int i = 0; i < N; i++) {
double w = boxes[i][0], h = boxes[i][1];
int bestK = 0;
double bestD = 1.0 - iouWH(w, h, centers[0][0], centers[0][1]);
for (int k = 1; k < K; k++) {
double d = 1.0 - iouWH(w, h, centers[k][0], centers[k][1]);
if (d < bestD) {
bestD = d;
bestK = k;
}
}
assign[i] = bestK;
}
// 更新阶段
double[] sumW = new double[K];
double[] sumH = new double[K];
int[] cnt = new int[K];
for (int i = 0; i < N; i++) {
int k = assign[i];
sumW[k] += boxes[i][0];
sumH[k] += boxes[i][1];
cnt[k]++;
}
double[][] newCenters = new double[K][2];
for (int k = 0; k < K; k++) {
if (cnt[k] == 0) {
// 空簇,保持不变
newCenters[k][0] = centers[k][0];
newCenters[k][1] = centers[k][1];
} else {
// 向下取整
double W = Math.floor(sumW[k] / cnt[k]);
double H = Math.floor(sumH[k] / cnt[k]);
newCenters[k][0] = W;
newCenters[k][1] = H;
}
}
// 终止条件:新旧中心 d 值之和
double change = 0.0;
for (int k = 0; k < K; k++) {
change += (1.0 - iouWH(centers[k][0], centers[k][1], newCenters[k][0], newCenters[k][1]));
}
centers = newCenters;
if (change < 1e-4) break;
}
// 最终向下取整并按面积降序
int[][] ans = new int[K][2];
for (int k = 0; k < K; k++) {
ans[k][0] = (int)Math.floor(centers[k][0]);
ans[k][1] = (int)Math.floor(centers[k][1]);
}
Integer[] idx = new Integer[K];
for (int i = 0; i < K; i++) idx[i] = i;
Arrays.sort(idx, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
long areaB = 1L * ans[b][0] * ans[b][1];
long areaA = 1L * ans[a][0] * ans[a][1];
return Long.compare(areaB, areaA); // 面积降序
}
});
int[][] sorted = new int[K][2];
for (int i = 0; i < K; i++) {
sorted[i][0] = ans[idx[i]][0];
sorted[i][1] = ans[idx[i]][1];
}
return sorted;
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
if (!sc.hasNext()) return;
int N = sc.nextInt();
int K = sc.nextInt();
int T = sc.nextInt();
double[][] boxes = new double[N][2];
for (int i = 0; i < N; i++) {
boxes[i][0] = sc.nextDouble();
boxes[i][1] = sc.nextDouble();
}
int[][] res = kmeansAnchors(boxes, K, T);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.length; i++) {
sb.append(res[i][0]).append(" ").append(res[i][1]);
if (i + 1 < res.length) sb.append("\n");
}
System.out.print(sb.toString());
}
}
C++
#include <bits/stdc++.h>
using namespace std;
// 计算两个宽高框的 IOU
double iouWH(double w1, double h1, double w2, double h2) {
double inter = min(w1, w2) * min(h1, h2);
double uni = w1 * h1 + w2 * h2 - inter;
return inter / (uni + 1e-16);
}
// d = 1 - IOU 的 K-means 聚类
vector<pair<int,int>> kmeansAnchors(const vector<pair<double,double>>& boxes, int K, int T) {
int N = (int)boxes.size();
// 初始化:前 K 个样本
vector<pair<double,double>> centers(K);
for (int k = 0; k < K; ++k) centers[k] = boxes[k];
for (int t = 0; t < T; ++t) {
// 分配阶段
vector<int> assign(N, 0);
for (int i = 0; i < N; ++i) {
double w = boxes[i].first, h = boxes[i].second;
int bestK = 0;
double bestD = 1.0 - iouWH(w, h, centers[0].first, centers[0].second);
for (int k = 1; k < K; ++k) {
double d = 1.0 - iouWH(w, h, centers[k].first, centers[k].second);
if (d < bestD) {
bestD = d;
bestK = k;
}
}
assign[i] = bestK;
}
// 更新阶段
vector<double> sumW(K, 0.0), sumH(K, 0.0);
vector<int> cnt(K, 0);
for (int i = 0; i < N; ++i) {
int k = assign[i];
sumW[k] += boxes[i].first;
sumH[k] += boxes[i].second;
cnt[k] += 1;
}
vector<pair<double,double>> newCenters(K);
for (int k = 0; k < K; ++k) {
if (cnt[k] == 0) {
// 空簇,保持不变
newCenters[k] = centers[k];
} else {
double W = floor(sumW[k] / cnt[k]);
double H = floor(sumH[k] / cnt[k]);
newCenters[k] = {W, H};
}
}
// 终止条件
double change = 0.0;
for (int k = 0; k < K; ++k) {
change += (1.0 - iouWH(centers[k].first, centers[k].second,
newCenters[k].first, newCenters[k].second));
}
centers.swap(newCenters);
if (change < 1e-4) break;
}
// 最终向下取整并按面积从大到小排序
vector<pair<int,int>> ans;
ans.reserve(K);
for (int k = 0; k < K; ++k) {
int W = (int)floor(centers[k].first);
int H = (int)floor(centers[k].second);
ans.emplace_back(W, H);
}
sort(ans.begin(), ans.end(), [](const pair<int,int>& a, const pair<int,int>& b){
long long A = 1LL * a.first * a.second;
long long B = 1LL * b.first * b.second;
if (A != B) return A > B; // 面积降序
if (a.first != b.first) return a.first > b.first; // 次级规则(可选)
return a.second > b.second;
});
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, T;
if (!(cin >> N >> K >> T)) return 0;
vector<pair<double,double>> boxes(N);
for (int i = 0; i < N; ++i) {
cin >> boxes[i].first >> boxes[i].second;
}
auto centers = kmeansAnchors(boxes, K, T);
for (int i = 0; i < (int)centers.size(); ++i) {
cout << centers[i].first << " " << centers[i].second;
if (i + 1 < (int)centers.size()) cout << "\n";
}
return 0;
}
题目内容
【背景信息】YOLO (You Only Look Once) 系列算法在目标检测领域采用了基于Anchor的机制。Anchor是预定义在图像上的一组固定尺寸和比例的参考框,在特征图的每个位置上预设多个Anchor框作为物体位置和尺寸预测的基准。通过模型预测Anchor与真实框的偏移量(Δx,Δy,Δw,Δh),而非直接输出坐标,避免了直接回归绝对坐标的困难。
【任务目标】 基于k-means聚类算法生成YOLO目标检测中的Anchor框:给定N个检测框的宽和高,聚类得到K个Anchor尺寸,并按照面积从大到小的顺序输出Anchor尺寸。
【任务目标】
基于k-means聚类算法生成YOLO目标检测中的Anchor框:给定N个检测框的宽和高,聚类得到K个Anchor尺寸,并按照面积从大到小的顺序输出Anchor尺寸。
聚类的流程如下:
初始化:为保证聚类结果的稳定性,采用稳定初始化策略,直接取前K个框作为初始中心。
分配阶段:计算每个框到所有聚类中心的距离,分配到最近的中心。
更新阶段:计算每个簇中所有框的宽高均值作为新的聚类中心(在每次迭代计算聚类中心时,均进行向下取整)。
迭代终止条件:当达到设定迭代次数T或新旧聚类中心之间的d值之和小于1e-4时停止迭代。
注:聚类使用 d=1−IOU 作为距离度量,d和IOU的计算均使用浮点数。
其中IOU的核心公式为交并面积比,即
IOU=并集面积交集面积对于检测框B1(w1,h1) 和 B2(w2,h2),交集面积计算为:
$$intersection = \min(w_1, w_2) \times \min(h_1, h_2) $$并集面积则为两框总面积减去交集:
$$union = w_1 \times h_1 + w_2 \times h_2 - intersection $$最终:IOU = intersection/(union + 1e-16) (加极小值避免除零)
输入描述
第一行:N,K,T,以空格分开。
其中:
-
N 为训练集中检测框的个数,10≤N≤80
-
K 为聚类中心个数,3≤K≤9
-
T 为聚类迭代次数,2≤T≤30
接下来 N 行:每行为检测框的宽与高,用空格分开。
输出描述
按照聚类中心的面积从大到小的顺序,输出聚类后的中心。
(聚类中心的面积 = 聚类中心的宽 × 聚类中心的高)
样例1
输入
12 4 20
12 23
34 21
43 23
199 23
34 23
108 12
200 107
12 78
123 110
34 23
56 48
78 66
输出
133 94
121 27
36 22
12 50
说明
-
输入第一行为 12420,代表12个检测框,要聚成4类,最大迭代次数为20,接下来的12行是检测框的宽与高。
-
取前4个框 [12,23],[34,21],[43,23],[199,23] 作为初始聚类中心。
-
迭代更新计算聚类中心,注意每次迭代时聚类中心都做向下取整。
-
按照聚类中心的面积(宽 × 高)从大到小排序,输出4个Anchor聚类中心。
样例2
输入
12 3 10
12 23
34 21
43 23
199 23
34 23
108 12
200 107
12 78
123 110
34 23
56 48
78 66
输出
150 76
51 25
12 50
说明
-
输入第一行为 12310,代表12个检测框,要聚成3类,最大迭代次数为10,接下来的12行是检测框的宽与高。
-
取前3个框 [12,23],[34,21],[43,23] 作为初始聚类中心。
-
迭代更新计算聚类中心,注意每次迭代时聚类中心都做向下取整。
-
按照聚类中心的面积(宽 × 高)从大到小排序,输出3个Anchor聚类中心。
提示
注:每次迭代的距离度量 d 和交并比 IOU 都是用浮点数计算,但每次迭代和最终输出的聚类中心都要做向下取整。