完整搜尋頁面 →

以 k-means 決定錨框形狀:用 IoU 當距離

選讀・DLCV 03・物件偵測:從 R-CNN 到 DETR 的補充資料(第 2/5 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

本頁內容

補充資料 · 5

  1. 傳統偵測器細說:Viola–Jones、HOG 與 DPM
  2. 以 k-means 決定錨框形狀:用 IoU 當距離
  3. RoI pooling 與 RoIAlign:不捨入的取樣方式
  4. YOLO 家族逐版介紹
  5. DETR 後繼者細說

論文導讀 · 1

  1. 現代觀點綜述導讀

電腦視覺深度學習

  1. 02 · 深度影像分類
  2. 03 · 物件偵測:從 R-CNN 到 DETR
  3. 09 · 深度影像復原:低階視覺
查看完整課程樹 →

白話版。 錨框的形狀其實是對「資料裡有哪些框」的猜測。與其用猜的,不如讓訓練框自己投票:把形狀相近的框分成一群,每一群的典型形狀就是一個錨框。

把每個訓練框簡化成寬與高 (w,h)(w, h),彷彿所有框共用同一個角落,因為錨框只需要形狀。對一個框 b=(w,h)b = (w, h) 與一個群中心 c=(wc,hc)c = (w_c, h_c),YOLO9000 [19] 使用的距離是

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)},

其中分子是兩個共用角落的框的重疊面積,分母是它們的聯集面積。演算法就是一般的 k-means 迴圈:

  1. 從訓練框中選 kk 個作為初始群中心;
  2. 把每個框指派給距離 dd 最小的群中心,也就是 IoU 最高的那一個;
  3. 把每個群中心換成其成員 (w,h)(w, h) 的平均(這是本則補充的選擇;論文只說明了距離,沒有說明更新規則);
  4. 重複步驟 2–3,直到指派不再改變。

對 NN 個框,每一輪需要 O(Nk)O(Nk) 次 IoU 計算。距離的選擇很重要:10 個像素的誤差對 20 像素的框很大,對 200 像素的框卻微不足道。平方歐氏距離會讓大框主導分群,而 1−IoU1 - \text{IoU} 與絕對大小無關。論文用「每個框與其最近群中心的平均 IoU」對 kk 作圖來選 kk,並以 k=5k = 5 作為召回率與模型複雜度之間的折衷 [19]。在 VOC 2007 上,論文(其 Table 1)報告:5 個以 IoU 分群得到的先驗框,平均 IoU 為 61.0;5 個以平方和距離分群的先驗框為 58.7;9 個手工挑選的 Faster R-CNN 錨框 [10] 為 60.9;9 個以 IoU 分群的先驗框為 67.2。

程式碼 · Python · 31 行
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")

輸出

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

這批合成框大多是小框,IoU 距離把四個錨框中的三個用在小框上(歐氏距離只用兩個),平均 IoU 因此較高。增益的大小取決於資料與初始化;這只是在合成框上做的一次固定種子實驗,不是基準測試。兩點提醒:分群結果只是局部最佳解,不同種子會得到不同的錨框;而且它只描述訓練集,換資料集就必須重新計算。

參考文獻

  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