{"cells":[{"metadata":{},"cell_type":"markdown","source":"It might be a good idea to read the source code to understand how mAP is calculated.\nAnd I think it's important to know some tips at the same time.\n\n1. [mAP understanding with code](#mAP-understanding-with-code)\n2. [The lower the confidence threshold is better](#The-lower-the-confidence-threshold-is-better)\n3. [Class dependence is linear](#Class-dependence-is-linear)\n4. [Small sample class is important](#Small-sample-class-is-important)"},{"metadata":{},"cell_type":"markdown","source":"### Credits\n\nI borrowed @ZFTurbo's great code for mAP calculation here.\n\nhttps://github.com/ZFTurbo/Mean-Average-Precision-for-Boxes\n\npycocotools is often used for mAP calculation, but I recommend this one.\nThis is very easy to use neither too much nor too little.\n\n<pre>\n!pip install map-boxes\n\nfrom map_boxes import mean_average_precision_for_boxes\n\nann = ann[['ImageID', 'LabelName', 'XMin', 'XMax', 'YMin', 'YMax']].values\ndet = det[['ImageID', 'LabelName', 'Conf', 'XMin', 'XMax', 'YMin', 'YMax']].values\nmean_ap, average_precisions = mean_average_precision_for_boxes(ann, det)\n</pre>\n\nIn addition, as we can see below, this source code is very simple and easy to read."},{"metadata":{},"cell_type":"markdown","source":"# mAP-understanding-with-code\nI would like to explain the source code for computing mAP.\nIf you don't know anything about mAP, try reading the documentation first.\n\n[mAP (mean Average Precision) for Object Detection](https://jonathan-hui.medium.com/map-mean-average-precision-for-object-detection-45c121a31173).\n\n[Breaking Down Mean Average Precision (mAP)](https://towardsdatascience.com/breaking-down-mean-average-precision-map-ae462f623a52).\n\n"},{"metadata":{"trusted":true,"_kg_hide-input":true},"cell_type":"code","source":"import pandas as pd\nimport numpy as np\nfrom tqdm.notebook import tqdm\nimport matplotlib.pyplot as plt\nfrom IPython.display import Image","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### IOU Calculation\n\nCompute all the IOUs between the N annotation boxes and the query_boxes.\n"},{"metadata":{"_kg_hide-input":true,"trusted":true},"cell_type":"code","source":"Image(\"../input/vinbig-validation-data/iou.png\")","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def compute_overlap(boxes, query_boxes):\n    \"\"\"\n    Args\n        boxes:       (N, 4) ndarray of float\n        query_boxes: (4)    ndarray of float\n    Returns\n        overlaps: (N) ndarray of overlap between boxes and query_boxes\n    \"\"\"\n    N = boxes.shape[0]\n    overlaps = np.zeros((N), dtype=np.float64)\n    box_area = (\n        (query_boxes[2] - query_boxes[0]) *\n        (query_boxes[3] - query_boxes[1])\n    )\n    for n in range(N):\n        iw = (\n            min(boxes[n, 2], query_boxes[2]) -\n            max(boxes[n, 0], query_boxes[0])\n        )\n        if iw > 0:\n            ih = (\n                min(boxes[n, 3], query_boxes[3]) -\n                max(boxes[n, 1], query_boxes[1])\n            )\n            if ih > 0:\n                ua = np.float64(\n                    (boxes[n, 2] - boxes[n, 0]) *\n                    (boxes[n, 3] - boxes[n, 1]) +\n                    box_area - iw * ih\n                )\n                overlaps[n] = iw * ih / ua\n    return overlaps","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### check if true positive or false positive\n\nAll detected bounding boxes will be assigned to the GT box that has the largest IOU.\nThen check whether they are TP or FP by iou_threshold.\nHere, if multiple detected bounding boxes are mapped to the same GT box, then only the highest scored bounding box needs to be assigned to that GT.\nSo note that **the detections passed to this function need to be pre-sorted**."},{"metadata":{"trusted":true},"cell_type":"code","source":"def cehck_if_true_or_false_positive(annotations, detections, iou_threshold):\n    annotations = np.array(annotations, dtype=np.float64)\n    scores = []\n    false_positives = []\n    true_positives = []\n    detected_annotations = [] # a GT box should be mapped only one predicted box at most.\n    for d in detections:\n        scores.append(d[4])\n        if len(annotations) == 0:\n            false_positives.append(1)\n            true_positives.append(0)\n            continue\n        overlaps = compute_overlap(annotations, d[:4])\n        assigned_annotation = np.argmax(overlaps)\n        max_overlap = overlaps[assigned_annotation]\n        if max_overlap >= iou_threshold and assigned_annotation not in detected_annotations:\n            false_positives.append(0)\n            true_positives.append(1)\n            detected_annotations.append(assigned_annotation)\n        else:\n            false_positives.append(1)\n            true_positives.append(0)\n    return scores, false_positives, true_positives","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Average Precision Calculation\n\nThis part is a bit complicated, but what is being done here is simply calculation of area under curve of presision / recall curve."},{"metadata":{"trusted":true},"cell_type":"code","source":"def _compute_ap(recall, precision):\n    \"\"\" Compute the average precision, given the recall and precision curves.\n    Code originally from https://github.com/rbgirshick/py-faster-rcnn.\n    # Arguments\n        recall:    The recall curve (list).\n        precision: The precision curve (list).\n    # Returns\n        The average precision as computed in py-faster-rcnn.\n    \"\"\"\n    # correct AP calculation\n    # first append sentinel values at the end\n    mrec = np.concatenate(([0.], recall, [1.]))\n    mpre = np.concatenate(([0.], precision, [0.]))\n\n    # compute the precision envelope\n    for i in range(mpre.size - 1, 0, -1):\n        mpre[i - 1] = np.maximum(mpre[i - 1], mpre[i])\n\n    # to calculate area under PR curve, look for points\n    # where X axis (recall) changes value\n    i = np.where(mrec[1:] != mrec[:-1])[0]\n\n    # and sum (\\Delta recall) * prec\n    ap = np.sum((mrec[i + 1] - mrec[i]) * mpre[i + 1])\n    return ap","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Utility Functions\n\nThese functions will group bounding boxes by image ID and label."},{"metadata":{"trusted":true},"cell_type":"code","source":"def get_real_annotations(table):\n    res = dict()\n    ids = table['ImageID'].values.astype(np.str)\n    labels = table['LabelName'].values.astype(np.str)\n    xmin = table['XMin'].values.astype(np.float32)\n    xmax = table['XMax'].values.astype(np.float32)\n    ymin = table['YMin'].values.astype(np.float32)\n    ymax = table['YMax'].values.astype(np.float32)\n\n    for i in range(len(ids)):\n        id = ids[i]\n        label = labels[i]\n        if id not in res:\n            res[id] = dict()\n        if label not in res[id]:\n            res[id][label] = []\n        box = [xmin[i], ymin[i], xmax[i], ymax[i]]\n        res[id][label].append(box)\n\n    return res\n\ndef get_detections(table):\n    res = dict()\n    ids = table['ImageID'].values.astype(np.str)\n    labels = table['LabelName'].values.astype(np.str)\n    scores = table['Conf'].values.astype(np.float32)\n    xmin = table['XMin'].values.astype(np.float32)\n    xmax = table['XMax'].values.astype(np.float32)\n    ymin = table['YMin'].values.astype(np.float32)\n    ymax = table['YMax'].values.astype(np.float32)\n\n    for i in range(len(ids)):\n        id = ids[i]\n        label = labels[i]\n        if id not in res:\n            res[id] = dict()\n        if label not in res[id]:\n            res[id][label] = []\n        box = [xmin[i], ymin[i], xmax[i], ymax[i], scores[i]]\n        res[id][label].append(box)\n    return res\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### mean Average Precision Calculation\nNow we can calculate mAP."},{"metadata":{"trusted":true},"cell_type":"code","source":"def mean_average_precision_for_boxes(ann, pred, iou_threshold=0.4, exclude_not_in_annotations=False, verbose=True):\n    \"\"\"\n    :param ann: path to CSV-file with annotations or numpy array of shape (N, 6)\n    :param pred: path to CSV-file with predictions (detections) or numpy array of shape (N, 7)\n    :param iou_threshold: IoU between boxes which count as 'match'. Default: 0.5\n    :param exclude_not_in_annotations: exclude image IDs which are not exist in annotations. Default: False\n    :param verbose: print detailed run info. Default: True\n    :return: tuple, where first value is mAP and second values is dict with AP for each class.\n    \"\"\"\n\n    valid = pd.DataFrame(ann, columns=['ImageID', 'LabelName', 'XMin', 'XMax', 'YMin', 'YMax'])\n    preds = pd.DataFrame(pred, columns=['ImageID', 'LabelName', 'Conf', 'XMin', 'XMax', 'YMin', 'YMax'])\n    ann_unique = valid['ImageID'].unique()\n    preds_unique = preds['ImageID'].unique()\n\n    if verbose:\n        print('Number of files in annotations: {}'.format(len(ann_unique)))\n        print('Number of files in predictions: {}'.format(len(preds_unique)))\n\n    # Exclude files not in annotations!\n    if exclude_not_in_annotations:\n        preds = preds[preds['ImageID'].isin(ann_unique)]\n        preds_unique = preds['ImageID'].unique()\n        if verbose:\n            print('Number of files in detection after reduction: {}'.format(len(preds_unique)))\n\n    unique_classes = valid['LabelName'].unique().astype(np.str)\n    if verbose:\n        print('Unique classes: {}'.format(len(unique_classes)))\n\n    all_detections = get_detections(preds)\n    all_annotations = get_real_annotations(valid)\n    if verbose:\n        print('Detections length: {}'.format(len(all_detections)))\n        print('Annotations length: {}'.format(len(all_annotations)))\n\n    average_precisions = {}\n    for zz, label in enumerate(sorted(unique_classes)):\n\n        # Negative class\n        if str(label) == 'nan':\n            continue\n\n        false_positives = []\n        true_positives = []\n        scores = []\n        num_annotations = 0.0\n\n        for i in range(len(ann_unique)):\n            detections = []\n            annotations = []\n            id = ann_unique[i]\n            if id in all_detections:\n                if label in all_detections[id]:\n                    detections = all_detections[id][label]\n            if id in all_annotations:\n                if label in all_annotations[id]:\n                    annotations = all_annotations[id][label]\n\n            if len(detections) == 0 and len(annotations) == 0:\n                continue\n                \n            num_annotations += len(annotations)\n            \n            scr, fp, tp = cehck_if_true_or_false_positive(annotations, detections, iou_threshold)\n            scores += scr\n            false_positives += fp\n            true_positives += tp\n\n        if num_annotations == 0:\n            average_precisions[label] = 0, 0\n            continue\n\n        false_positives = np.array(false_positives)\n        true_positives = np.array(true_positives)\n        scores = np.array(scores)\n\n        # sort by score\n        indices = np.argsort(-scores)\n        false_positives = false_positives[indices]\n        true_positives = true_positives[indices]\n\n        # compute false positives and true positives\n        false_positives = np.cumsum(false_positives)\n        true_positives = np.cumsum(true_positives)\n\n        # compute recall and precision\n        recall = true_positives / num_annotations\n        precision = true_positives / np.maximum(true_positives + false_positives, np.finfo(np.float64).eps)\n\n        # compute average precision\n        average_precision = _compute_ap(recall, precision)\n        average_precisions[label] = average_precision, num_annotations, precision, recall\n        if verbose:\n            s1 = \"{:30s} | {:.6f} | {:7d}\".format(label, average_precision, int(num_annotations))\n            print(s1)\n\n    present_classes = 0\n    precision = 0\n    for label, (average_precision, num_annotations, _, _) in average_precisions.items():\n        if num_annotations > 0:\n            present_classes += 1\n            precision += average_precision\n    mean_ap = precision / present_classes\n    if verbose:\n        print('mAP: {:.6f}'.format(mean_ap))\n    return mean_ap, average_precisions","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"One of the most frequently asked questions about mAP is where the confidence scores are used.\nConfidence scores is used to sort for the following two purposes.\n1. detections shold be sorted by confidence scores before cehck_if_true_or_false_positive().\n2. false_positives and ture_positives list shold be sorted by confidence scores before Average Precision Calculation."},{"metadata":{},"cell_type":"markdown","source":"That's it.\nSometimes reading the source code is the best way to understand.\nI hope this helps to understand mAP!"},{"metadata":{},"cell_type":"markdown","source":"# The-lower-the-confidence-threshold-is-better\n\nThe lower the confidence threshold, the higher the mAP we will always get."},{"metadata":{"_kg_hide-input":true,"trusted":true},"cell_type":"code","source":"# predicted boxes\ndf_pred = pd.read_csv('../input/vinbig-validation-data/valid_cv5.csv')\ndf_pred = df_pred.sort_values('conf', ascending=False)\n\n# GT annotation\ndf = pd.read_csv('../input/vinbigdata-chest-xray-abnormalities-detection/train.csv')\ndf.loc[df['class_id'] == 14, 'x_min'] = 0\ndf.loc[df['class_id'] == 14, 'y_min'] = 0\ndf.loc[df['class_id'] == 14, 'x_max'] = 1\ndf.loc[df['class_id'] == 14, 'y_max'] = 1\n\n# use only first rad here\ntgt_rad = 0\nfilterd_df_list = []\nfor image_id, df_img in df.groupby('image_id'):\n    rad_ids = df_img['rad_id'].unique()\n    rad_id = rad_ids[tgt_rad]\n    filterd_df_list.append(df_img[df_img['rad_id'] == rad_id])\ndf_anno = pd.concat(filterd_df_list).reset_index(drop=True)\n\nclass_name = df[['class_name','class_id']].set_index('class_id').to_dict()['class_name']","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"df_pred_thre001 = df_pred[df_pred.conf > 0.01]\ndf_pred_thre05 = df_pred[df_pred.conf > 0.5]\npred_thre001 = df_pred_thre001[['image_id', 'class_id', 'conf','x_min','x_max','y_min','y_max']].values\npred_thre05 = df_pred_thre05[['image_id', 'class_id', 'conf','x_min','x_max','y_min','y_max']].values\nanno = df_anno[['image_id', 'class_id','x_min','x_max','y_min','y_max']].values\n\nmean_ap_thre001, average_precisions_thre001 = mean_average_precision_for_boxes(anno, pred_thre001, verbose=False)\nmean_ap_thre05, average_precisions_thre05 = mean_average_precision_for_boxes(anno, pred_thre05, verbose=False)\nprint('mAP with threshold 0.01', round(mean_ap_thre001,2))\nprint('mAP with threshold 0.5 ', round(mean_ap_thre05,2))","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"This reason can be clearly understood by comparing the following two (right and loft) figures and the fact that AP is the area under the precision/recall curve.\n**Using a large threshold is the same thing as using only part of the area under the precision/recall curve.**"},{"metadata":{"_kg_hide-input":true,"trusted":true},"cell_type":"code","source":"# prot precision/recall curve\ndef plot_precision_recall_curve(precision1, recall1, precision2, recall2, thre1, thre2):\n    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12,4))\n\n    ax1.plot(recall1, precision1)\n    ax1.step(recall1, precision1, color='b', alpha=0.2, where='post')\n    ax1.fill_between(recall1, precision1, alpha=0.2, color='b')\n    ax1.set_title(f\"threshold {thre1}\")\n    ax1.set(xlabel='recall', ylabel='precision')\n    ax1.set_xlim([0.0, 1.0])\n    ax1.set_ylim([0.0, 1.05])\n    #ax1.invert_xaxis()\n    \n    ax2.plot(recall2, precision2)\n    ax2.step(recall2, precision2, color='b', alpha=0.2, where='post')\n    ax2.fill_between(recall2, precision2, alpha=0.2, color='b')\n    ax2.set_title(f\"threshold {thre2}\")\n    ax2.set(xlabel='recall', ylabel='precision')\n    ax2.set_xlim([0.0, 1.0])\n    ax2.set_ylim([0.0, 1.05])\n    \n    fig.tight_layout()\n    plt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"for i in range(15):\n    idx = str(i)\n    average_precision001, _, precision001, recall001 = average_precisions_thre001[idx]\n    average_precision05, _, precision05, recall05 = average_precisions_thre05[idx]\n    print(f'class name:{class_name[i]}, AP with threshold0.01:{average_precision001}, AP with threshold0.5:{average_precision05}')\n    plot_precision_recall_curve(precision001, recall001, precision05, recall05, 0.01, 0.5)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"So we should use as low a confidence threshold as possible.\nThe only disadvantage is that if we lower the threshold and increase the number of predictions, inference time will increases.\n\nFrom the left graph of the threshold value of 0.01, we can see that if we make the threshold value smaller, there is not much room for improvement.\nTherefore, even though the smaller the threshold value, the better the mAP becomes, the improvement is limited.\nThe max mAP score depends on the shape of precision/recall curve."},{"metadata":{},"cell_type":"markdown","source":"# Class-dependence-is-linear\nWe can expect the class dependency of mAP to be linear.\n<pre>\nmAP(all class) = mAP(class_id == n) + mAP(class_id != n)\n</pre>\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"df_pred_all = df_pred\ndf_pred_class0 = df_pred[df_pred.class_id == 0]\ndf_pred_not_class0 = df_pred[df_pred.class_id != 0]\n\npred_all = df_pred_all[['image_id', 'class_id', 'conf','x_min','x_max','y_min','y_max']].values\npred_class0 = df_pred_class0[['image_id', 'class_id', 'conf','x_min','x_max','y_min','y_max']].values\npred_not_class0 = df_pred_not_class0[['image_id', 'class_id', 'conf','x_min','x_max','y_min','y_max']].values\nanno = df_anno[['image_id', 'class_id','x_min','x_max','y_min','y_max']].values\n\nmean_ap_all, _ = mean_average_precision_for_boxes(anno, pred_all, verbose=False)\nmean_ap_class0, _ = mean_average_precision_for_boxes(anno, pred_class0, verbose=False)\nmean_ap_not_class0, _ = mean_average_precision_for_boxes(anno, pred_not_class0, verbose=False)\nprint('all', mean_ap_all)\nprint('sum', mean_ap_class0 + mean_ap_not_class0)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"This is obvious from the definition of mAP.\nSo you can check the scores for each class individually of not only CV but also LB.\nIt is difficult to make local CV for some competition like [Human Protein Atlas - Single Cell Classification](https://www.kaggle.com/c/hpa-single-cell-image-classification), checking for each class of LB is sometime helps."},{"metadata":{},"cell_type":"markdown","source":"# Small-sample-class-is-important\n\nSmall sample class is equally important as big class. Because:\n<pre>\nmax(mAP(a small class)) == max(mAP(a big class))\n</pre>\n\nFurthermore big classes are generally easier and have less room for improvement and smaller classes are generally more difficult and there is more room for improvement.\nSo we need to pay attention to small class.\n\nIf mAP is mean \"weighted\" average precision, this would be not true.\n\nNormally, this weight information does not disclosed.\nHowever, it is possible to guess the weights based on the second feature (class dependence is linear) and the public leaderboard score again."},{"metadata":{},"cell_type":"markdown","source":"I hope this information is useful especially for beginners.\n\nFor explanation of mAP itself, please see following.\n\n[github repo by ZFTurbo](https://github.com/ZFTurbo/Mean-Average-Precision-for-Boxes)\n\n[mAP (mean Average Precision) for Object Detection](https://jonathan-hui.medium.com/map-mean-average-precision-for-object-detection-45c121a31173).\n\n[Breaking Down Mean Average Precision (mAP)](https://towardsdatascience.com/breaking-down-mean-average-precision-map-ae462f623a52).\n\n[Explanation of scoring metric (mAP@0.4)](https://www.kaggle.com/c/vinbigdata-chest-xray-abnormalities-detection/discussion/212287) by @pestipeti.\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}