Full search page →

Anchor shapes by k-means: clustering with an IoU distance

Optional · supplementary note 2 of 5 for DLCV 03 · Object Detection: From R-CNN to DETR. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.

Navigate: this page and this track: Navigate: this page and this track

On this page

Supplementary notes · 5

  1. Classical detectors in detail: Viola–Jones, HOG and DPM
  2. Anchor shapes by k-means: clustering with an IoU distance
  3. RoI pooling versus RoIAlign: sampling without rounding
  4. The YOLO family, version by version
  5. DETR descendants in detail

Paper guides · 1

  1. Guide to the Modern view surveys

Deep Learning for Computer Vision

  1. 02 · Deep Image Classification
View the whole course tree →

Plain version. Anchor shapes are a guess about which boxes the data contains. Instead of guessing, let the training boxes vote: group boxes of similar shape and use each group’s typical shape as one anchor.

Reduce every training box to its width and height (w,h)(w, h), as if all boxes shared a corner, because an anchor only needs a shape. For a box b=(w,h)b = (w, h) and a centroid c=(wc,hc)c = (w_c, h_c) the distance used by YOLO9000 [19] is

d(b,c)=1−IoU(b,c),IoU(b,c)=min⁡(w,wc) min⁡(h,hc)wh+wchc−min⁡(w,wc) min⁡(h,hc),d(b, c) = 1 - \text{IoU}(b, c), \qquad \text{IoU}(b, c) = \frac{\min(w, w_c)\,\min(h, h_c)}{w h + w_c h_c - \min(w, w_c)\,\min(h, h_c)},

where the numerator is the overlap area of two boxes that share a corner and the denominator is their union. The algorithm is the usual k-means loop:

  1. choose kk training boxes as the initial centroids;
  2. assign each box to the centroid with the smallest dd, which is the one with the highest IoU;
  3. replace each centroid by the mean (w,h)(w, h) of its members (this note’s choice; the paper states the distance, not the update rule);
  4. repeat steps 2–3 until the assignments stop changing.

Each pass costs O(Nk)O(Nk) IoU evaluations for NN boxes. The choice of dd matters because a 10-pixel error is large for a 20-pixel box and negligible for a 200-pixel box. Squared Euclidean distance lets big boxes dominate the clustering, while 1−IoU1 - \text{IoU} is blind to absolute size. The paper picks kk by plotting the mean IoU between each box and its nearest centroid against kk, and settles on k=5k = 5 as a compromise between recall and model complexity [19]. On VOC 2007 it reports a mean IoU of 61.0 for 5 IoU-clustered priors, 58.7 for 5 priors clustered with the sum-of-squares distance, 60.9 for 9 hand-picked anchor boxes from Faster R-CNN [10], and 67.2 for 9 IoU-clustered priors (its Table 1).

Code · Python · 31 lines
import numpy as np

def wh_iou(wh, cent):
    """IoU of (w, h) pairs when boxes share a corner: (N, 2) x (K, 2) -> (N, K)."""
    inter = np.minimum(wh[:, None, 0], cent[None, :, 0]) * np.minimum(wh[:, None, 1], cent[None, :, 1])
    union = wh[:, :1] * wh[:, 1:] + (cent[:, 0] * cent[:, 1])[None, :] - inter
    return inter / union

def kmeans(wh, k, dist, iters=50, seed=0):
    cent = wh[np.random.default_rng(seed).choice(len(wh), k, replace=False)].copy()
    for _ in range(iters):
        if dist == "iou":   # distance 1 - IoU: nearest centroid = highest IoU
            assign = wh_iou(wh, cent).argmax(axis=1)
        else:               # ordinary squared Euclidean distance on (w, h)
            assign = ((wh[:, None] - cent[None]) ** 2).sum(-1).argmin(axis=1)
        for c in range(k):
            if np.any(assign == c):
                cent[c] = wh[assign == c].mean(axis=0)
    return cent

# synthetic "training boxes": 1000 small and 100 large, aspect ratios spread around 1
rng = np.random.default_rng(0)
area = np.concatenate([rng.lognormal(np.log(20**2), 0.5, 1000), rng.lognormal(np.log(200**2), 0.8, 100)])
ratio = np.exp(rng.normal(0, 0.6, area.size))            # h / w
wh = np.stack([np.sqrt(area / ratio), np.sqrt(area * ratio)], axis=1)

for dist in ["euclid", "iou"]:
    cent = kmeans(wh, 4, dist)
    n_small = int((cent.prod(axis=1) < 50**2).sum())
    print(f"{dist:6s} mean IoU to nearest centroid {wh_iou(wh, cent).max(axis=1).mean():.3f}, "
          f"centroids for small boxes (area < 50^2): {n_small} of 4")

Output

euclid mean IoU to nearest centroid 0.633, centroids for small boxes (area < 50^2): 2 of 4
iou    mean IoU to nearest centroid 0.668, centroids for small boxes (area < 50^2): 3 of 4

Most of these synthetic boxes are small, and the IoU distance spends three of four anchors on them instead of two, which raises the mean IoU. The size of the gain depends on the data and the initialization; this is one seeded run on synthetic boxes, not a benchmark. Two cautions: the clusters are only a local optimum, so different seeds give different anchors, and they describe the training set only, so they have to be recomputed for a new dataset.

References

  1. Z. Zou, K. Chen, Z. Shi, Y. Guo and J. Ye, “Object detection in 20 years: A survey,” Proceedings of the IEEE, vol. 111, no. 3, 2023. doi
  2. L. Liu, W. Ouyang, X. Wang, P. Fieguth, J. Chen, X. Liu and M. Pietikäinen, “Deep learning for generic object detection: A survey,” International Journal of Computer Vision, 2020. doi
  3. M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn and A. Zisserman, “The PASCAL Visual Object Classes (VOC) challenge,” International Journal of Computer Vision, vol. 88, 2010. doi
  4. T.-Y. Lin, M. Maire, S. Belongie, L. Bourdev, R. Girshick et al., “Microsoft COCO: Common objects in context,” in Proc. ECCV, 2014. doi
  5. P. Viola and M. Jones, “Rapid object detection using a boosted cascade of simple features,” in Proc. IEEE CVPR, 2001. doi
  6. N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” in Proc. IEEE CVPR, 2005. doi
  7. P. F. Felzenszwalb, R. B. Girshick, D. McAllester and D. Ramanan, “Object detection with discriminatively trained part-based models,” IEEE TPAMI, 2010. doi
  8. R. Girshick, J. Donahue, T. Darrell and J. Malik, “Rich feature hierarchies for accurate object detection and semantic segmentation,” in Proc. IEEE CVPR, 2014. arXiv
  9. R. Girshick, “Fast R-CNN,” in Proc. IEEE ICCV, 2015. arXiv
  10. S. Ren, K. He, R. Girshick and J. Sun, “Faster R-CNN: Towards real-time object detection with region proposal networks,” IEEE TPAMI, 2017 (conference version 2015). doi
  11. H. Rezatofighi, N. Tsoi, J. Gwak, A. Sadeghian, I. Reid and S. Savarese, “Generalized intersection over union: A metric and a loss for bounding box regression,” in Proc. IEEE/CVF CVPR, 2019. arXiv
  12. Z. Zheng, P. Wang, W. Liu, J. Li, R. Ye and D. Ren, “Distance-IoU loss: Faster and better learning for bounding box regression,” in Proc. AAAI, 2020. arXiv
  13. N. Bodla, B. Singh, R. Chellappa and L. S. Davis, “Soft-NMS — Improving object detection with one line of code,” in Proc. IEEE ICCV, 2017. arXiv
  14. T.-Y. Lin, P. Dollár, R. Girshick, K. He, B. Hariharan and S. Belongie, “Feature pyramid networks for object detection,” in Proc. IEEE CVPR, 2017. doi
  15. T.-Y. Lin, P. Goyal, R. Girshick, K. He and P. Dollár, “Focal loss for dense object detection,” in Proc. IEEE ICCV, 2017. doi
  16. K. He, G. Gkioxari, P. Dollár and R. Girshick, “Mask R-CNN,” in Proc. IEEE ICCV, 2017. doi
  17. Z. Cai and N. Vasconcelos, “Cascade R-CNN: Delving into high quality object detection,” in Proc. IEEE/CVF CVPR, 2018. doi
  18. J. Redmon, S. Divvala, R. Girshick and A. Farhadi, “You only look once: Unified, real-time object detection,” in Proc. IEEE CVPR, 2016. doi
  19. J. Redmon and A. Farhadi, “YOLO9000: Better, faster, stronger,” IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 7263–7271, 2017. CVF · arXiv
  20. J. Redmon and A. Farhadi, “YOLOv3: An incremental improvement,” tech. report, arXiv:1804.02767, 2018. arXiv
  21. A. Bochkovskiy, C.-Y. Wang and H.-Y. M. Liao, “YOLOv4: Optimal speed and accuracy of object detection,” arXiv:2004.10934, 2020. arXiv
  22. C.-Y. Wang, A. Bochkovskiy and H.-Y. M. Liao, “YOLOv7: Trainable bag-of-freebies sets new state-of-the-art for real-time object detectors,” in Proc. IEEE/CVF CVPR, 2023. doi
  23. C.-Y. Wang, I-H. Yeh and H.-Y. M. Liao, “YOLOv9: Learning what you want to learn using programmable gradient information,” in Proc. ECCV, 2024. doi
  24. A. Wang, H. Chen, L. Liu, K. Chen, Z. Lin et al., “YOLOv10: Real-time end-to-end object detection,” in Proc. NeurIPS, 2024. arXiv
  25. Y. Tian, Q. Ye and D. Doermann, “YOLOv12: Attention-centric real-time object detectors,” arXiv:2502.12524, 2025. arXiv
  26. W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu and A. C. Berg, “SSD: Single shot multibox detector,” in Proc. ECCV, 2016. arXiv
  27. H. Law and J. Deng, “CornerNet: Detecting objects as paired keypoints,” in Proc. ECCV, 2018. doi
  28. X. Zhou, D. Wang and P. Krähenbühl, “Objects as points,” arXiv:1904.07850, 2019. arXiv
  29. Z. Tian, C. Shen, H. Chen and T. He, “FCOS: Fully convolutional one-stage object detection,” in Proc. IEEE/CVF ICCV, 2019. arXiv
  30. N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov and S. Zagoruyko, “End-to-end object detection with transformers,” in Proc. ECCV, 2020. doi
  31. H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, 1955. doi
  32. X. Zhu, W. Su, L. Lu, B. Li, X. Wang and J. Dai, “Deformable DETR: Deformable transformers for end-to-end object detection,” in Proc. ICLR, 2021. arXiv
  33. H. Zhang, F. Li, S. Liu, L. Zhang, H. Su, J. Zhu, L. M. Ni and H.-Y. Shum, “DINO: DETR with improved denoising anchor boxes for end-to-end object detection,” arXiv:2203.03605, 2022. arXiv
  34. Y. Zhao, W. Lv, S. Xu, J. Wei, G. Wang et al., “DETRs beat YOLOs on real-time object detection,” in Proc. IEEE/CVF CVPR, 2024. doi
  35. M. Minderer, A. Gritsenko, A. Stone, M. Neumann, D. Weissenborn et al., “Simple open-vocabulary object detection with vision transformers,” in Proc. ECCV, 2022. arXiv
  36. S. Liu, Z. Zeng, T. Ren, F. Li, H. Zhang et al., “Grounding DINO: Marrying DINO with grounded pre-training for open-set object detection,” in Proc. ECCV, 2024. doi
  37. T. Cheng, L. Song, Y. Ge, W. Liu, X. Wang et al., “YOLO-World: Real-time open-vocabulary object detection,” in Proc. IEEE/CVF CVPR, 2024. doi
  38. N. Carion, L. Gustafson, Y.-T. Hu, S. Debnath, R. Hu et al., “SAM 3: Segment anything with concepts,” arXiv:2511.16719, 2025. arXiv
  39. G. Cheng, X. Yuan, X. Yao, K. Yan, Q. Zeng et al., “Towards large-scale small object detection: Survey and benchmarks,” IEEE TPAMI, vol. 45, no. 11, 2023. arXiv
  40. COCO Consortium, “COCO detection evaluation,” official evaluation description (12 metrics, 101-point interpolation). link · official evaluator
  41. M. Everingham, S. M. A. Eslami, L. Van Gool, C. K. I. Williams, J. Winn and A. Zisserman, “The PASCAL Visual Object Classes challenge: A retrospective,” International Journal of Computer Vision, vol. 111, 2015. doi
  42. S. Shao, Z. Li, T. Zhang, C. Peng et al., “Objects365: A large-scale, high-quality dataset for object detection,” in Proc. IEEE/CVF ICCV, 2019. doi
  43. A. Kuznetsova, H. Rom, N. Alldrin, J. Uijlings, I. Krasin et al., “The Open Images Dataset V4: Unified image classification, object detection, and visual relationship detection at scale,” International Journal of Computer Vision, 2020. arXiv
  44. A. Gupta, P. Dollár and R. Girshick, “LVIS: A dataset for large vocabulary instance segmentation,” in Proc. IEEE/CVF CVPR, 2019. doi
  45. T. Shehzadi, K. A. Hashmi, M. Liwicki, D. Stricker and M. Z. Afzal, “Object detection with transformers: A review,” Sensors, vol. 25, no. 19, 2025. doi
  46. C. Zhu and L. Chen, “A survey on open-vocabulary detection and segmentation: Past, present, and future,” IEEE TPAMI, 2024. doi