YOLOV3中k-means聚类获得anchor boxes过程详解

Zephus

  YOLOV3中k-means聚类获得anchor boxes过程详解

??我们都知道yolov3对训练数据使用了k-means聚类的算法来获得anchor boxes大小，但是具体其计算过程是怎样的呢？下面我们来详细的分析其具体计算过程：

第一步：首先我们要知道我们需要聚类的是bounding box，所以我们无需考虑其所属类别，第一步我们需要将所有的bounding box坐标提取出来，也许一张图有一个矩形框，也许有多个，但是我们需要无区别的将所有图片的所有矩形框提取出来，放在一起。
第二步：数据处理获得所有训练数据bounding boxes的宽高数据。给的训练数据往往是其bounding box的4个坐标，但是我们后续需要聚类分析的是bounding box的宽高大小，所以我们需要将坐标数据转换为框的宽高大小，计算方法很简单：长=右下角横坐标-左上角横坐标、宽=右下角纵坐标-左上角纵坐标。
第三步：初始化k个anchor box，通过在所有的bounding boxes中随机选取k个值作为k个anchor boxes的初始值。
第四步：计算每个bounding box与每个anchor box的iou值。传统的聚类方法是使用欧氏距离来衡量差异，也就是说如果我们运用传统的k-means聚类算法，可以直接聚类bounding box的宽和高，产生k个宽、高组合的anchor boxes，但是作者发现此方法在box尺寸比较大的时候，其误差也更大，所以作者引入了iou值，可以避免这个问题。iou值计算方法：这里参考下图和计算代码：

1. min_w_matrix = np.minimum(cluster_w_matrix, box_w_matrix)#cluster_w_matrix, box_w_matrix分别代表anchor box和bounding box宽大小
2. min_h_matrix = np.minimum(cluster_h_matrix, box_h_matrix)#cluster_h_matrix, box_h_matrix分别代表anchor box和bounding box高大小
3. inter_area = np.multiply(min_w_matrix, min_h_matrix)#inter_area表示重叠面积
4. IOU = inter_area / (box_area + cluster_area - inter_area)#box_area表示bounding box面积 ;cluster_area表示anchor box面积

复制代码

由于iou值往往越大越好，所以作者定义了一个距离d参数，用来表示其误差：
d=1-IOU 第五步：分类操作。经过前一步的计算可以的到每一个bounding box对于每个anchor box的误差d（n,k），我们通过比较每个bounding box其对于每个anchor box的误差大小{d(i,1)，d(i,2)，…,d(i,k)},选取最小误差的那个anchor box，将这个bounding box分类给它，对于每个bounding box都做这个操作，最后记录下来每个anchor box有哪些bounding box属于它。
第六步：anchor box更新。经过上一步，我们就知道每一个anchor box都有哪些bounding box属于它，然后对于每个anchor box中的那些bounding box，我们再求这些bounding box的宽高中值大小（这里参照github上作者qqwweee那个yolov3项目，也许也有使用平均值进行更新），将其作为该anchor box新的尺寸。
第七步：重复操作第四步到第六步，直到在第五步中发现对于全部bounding box其所属的anchor box类与之前所属的anchor box类完全一样。（这里表示所有bounding box的分类已经不再更新）
第八步：计算anchor boxes精确度。至第七步，其实已经通过k-means算法计算出anchor box。但是细心的同学可能已经发现，k-means.py还给出其精确度大小，其计算方法如下：使用最后得到的anchor boxes与每个bounding box计算其IOU值，对于每个bounding box选取其最高的那个IOU值（代表其属于某一个anchor box类），然后求所有bounding box该IOU值的平均值也即最后的精确度值。
应网友要求附上代码（代码来源）：

1. import numpy as np
2. import xml.etree.ElementTree as ET
3. import glob
4. import random
6. defcas_iou(box,cluster):
7.     x = np.minimum(cluster[:,0],box[0])
8.     y = np.minimum(cluster[:,1],box[1])
10.     intersection = x * y
11.     area1 = box[0]* box[1]
13.     area2 = cluster[:,0]* cluster[:,1]
14.     iou = intersection /(area1 + area2 -intersection)return iou
16. defavg_iou(box,cluster):return np.mean([np.max(cas_iou(box[i],cluster))for i inrange(box.shape[0])])defkmeans(box,k):# 取出一共有多少框
17.     row = box.shape[0]# 每个框各个点的位置
18.     distance = np.empty((row,k))# 最后的聚类位置
19.     last_clu = np.zeros((row,))
21.     np.random.seed()# 随机选5个当聚类中心
22.     cluster = box[np.random.choice(row,k,replace =False)]# cluster = random.sample(row, k)whileTrue:# 计算每一行距离五个点的iou情况。for i inrange(row):
23.             distance[i]=1- cas_iou(box[i],cluster)# 取出最小点
24.         near = np.argmin(distance,axis=1)if(last_clu == near).all():break# 求每一个类的中位点for j inrange(k):
25.             cluster[j]= np.median(
26.                 box[near == j],axis=0)
28.         last_clu = near
30.     return cluster
32. defload_data(path):
33.     data =[]# 对于每一个xml都寻找boxfor xml_file in glob.glob('{}/*xml'.format(path)):
34.         tree = ET.parse(xml_file)
35.         height =int(tree.findtext('./size/height'))
36.         width =int(tree.findtext('./size/width'))# 对于每一个目标都获得它的宽高for obj in tree.iter('object'):
37.             xmin =int(float(obj.findtext('bndbox/xmin')))/ width
38.             ymin =int(float(obj.findtext('bndbox/ymin')))/ height
39.             xmax =int(float(obj.findtext('bndbox/xmax')))/ width
40.             ymax =int(float(obj.findtext('bndbox/ymax')))/ height
42.             xmin = np.float64(xmin)
43.             ymin = np.float64(ymin)
44.             xmax = np.float64(xmax)
45.             ymax = np.float64(ymax)# 得到宽高
46.             data.append([xmax-xmin,ymax-ymin])return np.array(data)if __name__ =='__main__':# 运行该程序会计算'./VOCdevkit/VOC2007/Annotations'的xml# 会生成yolo_anchors.txt
47.     SIZE =416
48.     anchors_num =6# 载入数据集，可以使用VOC的xml
49.     path = r'./VOCdevkit/VOC2007/Annotations'# 载入所有的xml# 存储格式为转化为比例后的width,height
50.     data = load_data(path)# 使用k聚类算法
51.     out = kmeans(data,anchors_num)
52.     out = out[np.argsort(out[:,0])]print('acc:{:.2f}%'.format(avg_iou(data,out)*100))print(out*SIZE)
53.     data = out*SIZE
54.     f =open("yolo_anchors.txt",'w')
55.     row = np.shape(data)[0]for i inrange(row):if i ==0:
56.             x_y ="%d,%d"%(data[i][0], data[i][1])else:
57.             x_y =", %d,%d"%(data[i][0], data[i][1])
58.         f.write(x_y)
59.     f.close()

复制代码

相关博客：(yolo v3)使用自己数据集k-means聚类产生的anchor效果反而变差解决方法
参考：https://github.com/bubbliiiing/yolov4-tiny-keras/blob/master/kmeans_for_anchors.py