{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Evaluation metric\nIn this notebook I'll try to explain and implement the competition metrics. \n\nIf you find a bug please leave a comment. Thanks.\n\nAnd do not forget to vote :)\n\n-----\n**UPDATE v2 - <span style=\"color:red\">BUG fix!</span>**\n\nInside the `calculate_precision` function I did not pass the `form` param, it was hardcoded `coco`.\nThis caused wrong calculations if you used the `pascal_voc` format.\n\n**UPDATE v3 - <span style=\"color:red\">Optimized with Numba!</span>**\n- I optimized the code, so with help of numba it will run much faster\n- Added the tips of Alexander (see the comments below)\n- <span style=\"color:red\">Importnat change</span>: In some of the methods the order of the `gt_box`, `pred_box` arguments were mixed. Please double check your code. The correct order is `gt` first, `pred` second.\n\n**UPDATE v4 - <span style=\"color:red\">Another BUG fixed!</span>**"},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","trusted":true},"cell_type":"code","source":"import pandas as pd\nimport numpy as np\nimport numba\nimport re\nimport cv2\nimport ast\nimport matplotlib.pyplot as plt\n\nfrom numba import jit\nfrom typing import List, Union, Tuple\n\nDIR_INPUT = '/kaggle/input/global-wheat-detection'\nDIR_TRAIN = f'{DIR_INPUT}/train'\nDIR_TEST = f'{DIR_INPUT}/test'","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Intersection over Union (IoU)\n> Intersection over Union is a measure of the magnitude of overlap between two bounding boxes (or, in the more general case, two objects). It calculates the size of the overlap between two objects, divided by the total area of the two objects combined.\n>\n> It can be visualized as the following:\n> ![iou](https://storage.googleapis.com/kaggle-media/competitions/rsna/IoU.jpg) \n>\n> The two boxes in the visualization overlap, but the area of the overlap is insubstantial compared with the area taken up by both objects together. IoU would be low - and would likely not count as a \"hit\" at higher IoU thresholds."},{"metadata":{},"cell_type":"markdown","source":"### About the `form` param\nI made a mistake in my starter notebook. I did not know that `Albumentation` accepts the box coordinates in many formats, so my starter code could be a bit confusing.\nIn this notebook, I implemented both formats, so you can use whatever you prefer:\n\n- **pascal_voc**: min/max coordinates `[x_min, y_min, x_max, y_max]`\n- **coco**: width/height instead of maxes `[x_min, y_min, width, height]`\n\nMake sure you use the same format everywhere (including during your train/validation/inference calculations)"},{"metadata":{},"cell_type":"markdown","source":"## IOU Calculation"},{"metadata":{"trusted":true},"cell_type":"code","source":"@jit(nopython=True)\ndef calculate_iou(gt, pr, form='pascal_voc') -> float:\n    \"\"\"Calculates the Intersection over Union.\n\n    Args:\n        gt: (np.ndarray[Union[int, float]]) coordinates of the ground-truth box\n        pr: (np.ndarray[Union[int, float]]) coordinates of the prdected box\n        form: (str) gt/pred coordinates format\n            - pascal_voc: [xmin, ymin, xmax, ymax]\n            - coco: [xmin, ymin, w, h]\n    Returns:\n        (float) Intersection over union (0.0 <= iou <= 1.0)\n    \"\"\"\n    if form == 'coco':\n        gt = gt.copy()\n        pr = pr.copy()\n\n        gt[2] = gt[0] + gt[2]\n        gt[3] = gt[1] + gt[3]\n        pr[2] = pr[0] + pr[2]\n        pr[3] = pr[1] + pr[3]\n\n    # Calculate overlap area\n    dx = min(gt[2], pr[2]) - max(gt[0], pr[0]) + 1\n    \n    if dx < 0:\n        return 0.0\n    \n    dy = min(gt[3], pr[3]) - max(gt[1], pr[1]) + 1\n\n    if dy < 0:\n        return 0.0\n\n    overlap_area = dx * dy\n\n    # Calculate union area\n    union_area = (\n            (gt[2] - gt[0] + 1) * (gt[3] - gt[1] + 1) +\n            (pr[2] - pr[0] + 1) * (pr[3] - pr[1] + 1) -\n            overlap_area\n    )\n\n    return overlap_area / union_area\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### No overlapping"},{"metadata":{"trusted":true},"cell_type":"code","source":"box1 = np.array([834.0, 222.0, 56.0, 36.0])\nbox2 = np.array([26.0, 144.0, 124.0, 117.0])\n\nassert calculate_iou(box1, box2, form='coco') == 0.0","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Partial (50%) overlapping"},{"metadata":{"trusted":true},"cell_type":"code","source":"box1 = np.array([100, 100, 100, 100])\nbox2 = np.array([100, 100, 200, 100])\n\nres = calculate_iou(box1, box2, form='coco')\nassert  res > 0.5 and res < 0.50249","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Full overlapping"},{"metadata":{"trusted":true},"cell_type":"code","source":"box1 = np.array([834.0, 222.0, 56.0, 36.0])\nbox2 = box1\n\nassert calculate_iou(box1, box2, form='coco') == 1.0","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Mean Average Precision\n\n> This competition is evaluated on the mean average precision at different intersection over union (IoU) thresholds. The IoU of a set of predicted bounding boxes and ground truth bounding boxes is calculated as:\n>\n> $$IoU(A, B) = \\frac{A\\cap B}{A\\cup B}$$\n>\n>The metric sweeps over a range of IoU thresholds, at each point calculating an average precision value. The threshold values range from 0.5 to 0.75 with a step size of 0.05. In other words, at a threshold of 0.5, a predicted object is considered a \"hit\" if its intersection over union with a ground truth object is greater than 0.5.\n>\n> At each threshold value t, a precision value is calculated based on the number of true positives (TP), false negatives (FN), and false positives (FP) resulting from comparing the predicted object to all ground truth objects:\n>\n> $$Precision(t)=\\frac{TP(t)}{TP(t) + FP(t) + FN(t)}$$\n>\n\n- A **true positive** is counted when a single predicted object matches a ground truth object with an IoU above the threshold.\n- A **false positive** indicates a predicted object had no associated ground truth object.\n- A **false negative** indicates a ground truth object had no associated predicted object.\n\n> **Important note**: if there are no ground truth objects at all for a given image, ANY number of predictions (false positives) will result in the image receiving a score of zero, and being included in the mean average precision.\n>\n> The average precision of a single image is calculated as the mean of the above precision values at each IoU threshold:\n>\n> $$Avg. Precision = \\frac{1}{n_{thresh}}*\\sum_{t=1}^{n} precision(t)$$\n>\n> In your submission, you are also asked to provide a confidence level for each bounding box. Bounding boxes will be evaluated in order of their confidence levels in the above process. This means that bounding boxes with higher confidence will be checked first for matches against solutions, which determines what boxes are considered true and false positives.\n>\n>Lastly, the score returned by the competition metric is the mean taken over the individual average precisions of each image in the test dataset."},{"metadata":{"trusted":true},"cell_type":"code","source":"train_df = pd.read_csv(f'{DIR_INPUT}/train.csv')\ntrain_df.shape","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# From Andrew's kernel\nbox_data = np.stack(train_df['bbox'].apply(lambda x: ast.literal_eval(x)))\ntrain_df[['x', 'y', 'w', 'h']] = pd.DataFrame(box_data).astype(np.float32)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## MAP calculation"},{"metadata":{"trusted":true},"cell_type":"code","source":"@jit(nopython=True)\ndef find_best_match(gts, pred, pred_idx, threshold = 0.5, form = 'pascal_voc', ious=None) -> int:\n    \"\"\"Returns the index of the 'best match' between the\n    ground-truth boxes and the prediction. The 'best match'\n    is the highest IoU. (0.0 IoUs are ignored).\n\n    Args:\n        gts: (List[List[Union[int, float]]]) Coordinates of the available ground-truth boxes\n        pred: (List[Union[int, float]]) Coordinates of the predicted box\n        pred_idx: (int) Index of the current predicted box\n        threshold: (float) Threshold\n        form: (str) Format of the coordinates\n        ious: (np.ndarray) len(gts) x len(preds) matrix for storing calculated ious.\n\n    Return:\n        (int) Index of the best match GT box (-1 if no match above threshold)\n    \"\"\"\n    best_match_iou = -np.inf\n    best_match_idx = -1\n\n    for gt_idx in range(len(gts)):\n        \n        if gts[gt_idx][0] < 0:\n            # Already matched GT-box\n            continue\n        \n        iou = -1 if ious is None else ious[gt_idx][pred_idx]\n\n        if iou < 0:\n            iou = calculate_iou(gts[gt_idx], pred, form=form)\n            \n            if ious is not None:\n                ious[gt_idx][pred_idx] = iou\n\n        if iou < threshold:\n            continue\n\n        if iou > best_match_iou:\n            best_match_iou = iou\n            best_match_idx = gt_idx\n\n    return best_match_idx\n\n@jit(nopython=True)\ndef calculate_precision(gts, preds, threshold = 0.5, form = 'coco', ious=None) -> float:\n    \"\"\"Calculates precision for GT - prediction pairs at one threshold.\n\n    Args:\n        gts: (List[List[Union[int, float]]]) Coordinates of the available ground-truth boxes\n        preds: (List[List[Union[int, float]]]) Coordinates of the predicted boxes,\n               sorted by confidence value (descending)\n        threshold: (float) Threshold\n        form: (str) Format of the coordinates\n        ious: (np.ndarray) len(gts) x len(preds) matrix for storing calculated ious.\n\n    Return:\n        (float) Precision\n    \"\"\"\n    n = len(preds)\n    tp = 0\n    fp = 0\n    \n    # for pred_idx, pred in enumerate(preds_sorted):\n    for pred_idx in range(n):\n\n        best_match_gt_idx = find_best_match(gts, preds[pred_idx], pred_idx,\n                                            threshold=threshold, form=form, ious=ious)\n\n        if best_match_gt_idx >= 0:\n            # True positive: The predicted box matches a gt box with an IoU above the threshold.\n            tp += 1\n            # Remove the matched GT box\n            gts[best_match_gt_idx] = -1\n\n        else:\n            # No match\n            # False positive: indicates a predicted box had no associated gt box.\n            fp += 1\n\n    # False negative: indicates a gt box had no associated predicted box.\n    fn = (gts.sum(axis=1) > 0).sum()\n\n    return tp / (tp + fp + fn)\n\n\n@jit(nopython=True)\ndef calculate_image_precision(gts, preds, thresholds = (0.5, ), form = 'coco') -> float:\n    \"\"\"Calculates image precision.\n\n    Args:\n        gts: (List[List[Union[int, float]]]) Coordinates of the available ground-truth boxes\n        preds: (List[List[Union[int, float]]]) Coordinates of the predicted boxes,\n               sorted by confidence value (descending)\n        thresholds: (float) Different thresholds\n        form: (str) Format of the coordinates\n\n    Return:\n        (float) Precision\n    \"\"\"\n    n_threshold = len(thresholds)\n    image_precision = 0.0\n    \n    ious = np.ones((len(gts), len(preds))) * -1\n    # ious = None\n\n    for threshold in thresholds:\n        precision_at_threshold = calculate_precision(gts.copy(), preds, threshold=threshold,\n                                                     form=form, ious=ious)\n        image_precision += precision_at_threshold / n_threshold\n\n    return image_precision","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"For local validation, you need to calculate image precision for all of your validation images and take the average.\n\n```python\nvalidation_image_precision = []\niou_thresholds = [x for x in np.arange(0.5, 0.76, 0.05)]\n\nfor images, targets in valid_data_loader:\n    # ...\n    #\n    # outputs = model.forward(images)\n    #\n    # ...\n    #\n    # preds = ... # shape: (#predicted box, 4)\n    # scores = ... # shape: (#predicted box, )\n    # gt_boxes = ... # shape: (#ground-truth box, 4)\n    \n    preds_sorted_idx = np.argsort(scores)[::-1]\n    preds_sorted = preds[preds_sorted_idx]\n    \n    for idx, image in enumerate(images):\n        image_precision = calculate_image_precision(preds_sorted,\n                                                    gt_boxes,\n                                                    thresholds=iou_thresholds,\n                                                    form='coco')\n        \n        validation_image_precisions.append(image_precision)\n\nprint(\"Validation IOU: {0:.4f}\".format(np.mean(validation_image_precisions))\n```"},{"metadata":{},"cell_type":"markdown","source":"# Testing"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Our testing sample\nsample_id = '1ef16dab1'\n\ngt_boxes = train_df[train_df['image_id'] == sample_id][['x', 'y', 'w', 'h']].values\ngt_boxes = gt_boxes.astype(np.int)\n\n# Ground-truth boxes of our sample\ngt_boxes","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# No GT - Predicted box match\npred_box = np.array([0, 0, 10, 10])\nassert find_best_match(gt_boxes, pred_box, 0, threshold=0.5, form='coco') == -1\n\n# First GT match\npred_box = np.array([954., 391., 70., 90.])\nassert find_best_match(gt_boxes, pred_box, 0, threshold=0.5, form='coco') == 0","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# These are the predicted boxes (and scores) from my locally trained model.\npreds = np.array([[956, 409, 68, 85],\n                  [883, 945, 85, 77],\n                  [745, 468, 81, 87],\n                  [658, 239, 103, 105],\n                  [518, 419, 91, 100],\n                  [711, 805, 92, 106],\n                  [62, 213, 72, 64],\n                  [884, 175, 109, 68],\n                  [721, 626, 96, 104],\n                  [878, 619, 121, 81],\n                  [887, 107, 111, 71],\n                  [827, 525, 88, 83],\n                  [816, 868, 102, 86],\n                  [166, 882, 78, 75],\n                  [603, 563, 78, 97],\n                  [744, 916, 68, 52],\n                  [582, 86, 86, 72],\n                  [79, 715, 91, 101],\n                  [246, 586, 95, 80],\n                  [181, 512, 93, 89],\n                  [655, 527, 99, 90],\n                  [568, 363, 61, 76],\n                  [9, 717, 152, 110],\n                  [576, 698, 75, 78],\n                  [805, 974, 75, 50],\n                  [10, 15, 78, 64],\n                  [826, 40, 69, 74],\n                  [32, 983, 106, 40]]\n                )\n\nscores = np.array([0.9932319, 0.99206185, 0.99145633, 0.9898089, 0.98906296, 0.9817738,\n                   0.9799762, 0.97967803, 0.9771589, 0.97688967, 0.9562935, 0.9423076,\n                   0.93556845, 0.9236257, 0.9102379, 0.88644403, 0.8808225, 0.85238415,\n                   0.8472188, 0.8417798, 0.79908705, 0.7963756, 0.7437897, 0.6044758,\n                   0.59249884, 0.5557045, 0.53130984, 0.5020239])\n\n# Sort highest confidence -> lowest confidence\npreds_sorted_idx = np.argsort(scores)[::-1]\npreds_sorted = preds[preds_sorted_idx]","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def show_result(sample_id, preds, gt_boxes):\n    sample = cv2.imread(f'{DIR_TRAIN}/{sample_id}.jpg', cv2.IMREAD_COLOR)\n    sample = cv2.cvtColor(sample, cv2.COLOR_BGR2RGB)\n\n    fig, ax = plt.subplots(1, 1, figsize=(16, 8))\n\n    for pred_box in preds:\n        cv2.rectangle(\n            sample,\n            (pred_box[0], pred_box[1]),\n            (pred_box[0] + pred_box[2], pred_box[1] + pred_box[3]),\n            (220, 0, 0), 2\n        )\n\n    for gt_box in gt_boxes:    \n        cv2.rectangle(\n            sample,\n            (gt_box[0], gt_box[1]),\n            (gt_box[0] + gt_box[2], gt_box[1] + gt_box[3]),\n            (0, 0, 220), 2\n        )\n\n    ax.set_axis_off()\n    ax.imshow(sample)\n    ax.set_title(\"RED: Predicted | BLUE - Ground-truth\")","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"show_result(sample_id, preds, gt_boxes)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"precision = calculate_precision(gt_boxes.copy(), preds_sorted, threshold=0.5, form='coco')\nprint(\"Precision at threshold 0.5: {0:.4f}\".format(precision))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"precision = calculate_precision(gt_boxes.copy(), preds_sorted, threshold=0.75, form='coco')\nprint(\"Precision at threshold 0.75: {0:.4f}\".format(precision))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Numba typed list!\niou_thresholds = numba.typed.List()\n\nfor x in [0.5, 0.55, 0.6, 0.65, 0.7, 0.75]:\n    iou_thresholds.append(x)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"image_precision = calculate_image_precision(gt_boxes, preds_sorted,\n                                            thresholds=iou_thresholds,\n                                            form='coco')\n\nprint(\"The average precision of the sample image: {0:.4f}\".format(image_precision))","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"---------------------------------"},{"metadata":{},"cell_type":"markdown","source":"**Thanks for reading. Please vote if you find this notebook useful.**"},{"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}