{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Vectorized pytorch implementation of mAP metric defined for this competition\n\n\nThis is my first Kaggle competition and I've probably spent more time with the metric calculation than the actual model definition xD. I'm not sure if this is a working code and am seeking for your feedbacks on the same!\n\n<span style=\"color:red;\">Version 4:</span> \n* Fixed a bug in the mappings logic (assigning first prediction box on condition)\n* Propogated the `form` argument to `calculate_map` function\n* **The code is working now !!** (let me know if you find any issues)\n\n<span style=\"color:red;\">Version 3:</span> Updated mapping logic","execution_count":null},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","trusted":true},"cell_type":"code","source":"import torch\nfrom torch import tensor\nfrom torchvision.ops.boxes import box_iou","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def align_coordinates(boxes):\n    \"\"\"Align coordinates (x1,y1) < (x2,y2) to work with torchvision `box_iou` op\n    Arguments:\n        boxes (Tensor[N,4])\n    \n    Returns:\n        boxes (Tensor[N,4]): aligned box coordinates\n    \"\"\"\n    x1y1 = torch.min(boxes[:,:2,],boxes[:, 2:])\n    x2y2 = torch.max(boxes[:,:2,],boxes[:, 2:])\n    boxes = torch.cat([x1y1,x2y2],dim=1)\n    return boxes\n\n\ndef calculate_iou(gt, pr, form='pascal_voc'):\n    \"\"\"Calculates the Intersection over Union.\n\n    Arguments:\n        gt: (torch.Tensor[N,4]) coordinates of the ground-truth boxes\n        pr: (torch.Tensor[M,4]) coordinates of the prdicted boxes\n        form: (str) gt/pred coordinates format\n            - pascal_voc: [xmin, ymin, xmax, ymax]\n            - coco: [xmin, ymin, w, h]\n    Returns:\n        iou (Tensor[N, M]): the NxM matrix containing the pairwise\n        IoU values for every element in boxes1 and boxes2\n    \"\"\"\n    if form == 'coco':\n        gt = gt.clone()\n        pr = pr.clone()\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    gt = align_coordinates(gt)\n    pr = align_coordinates(pr)\n    \n    return box_iou(gt,pr)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Borrowing the sample bounding boxes from @pestipeti's [Evaluation metric kernel](https://www.kaggle.com/pestipeti/competition-metric-details-script#Evaluation-metric)","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"# These are the predicted boxes (and scores) from my locally trained model.\npreds = tensor([[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]]).float()\n\ntargs = tensor([[954, 391,  70,  90],\n       [660, 220,  95, 102],\n       [ 64, 209,  76,  57],\n       [896,  99, 102,  69],\n       [747, 460,  72,  77],\n       [885, 163, 103,  69],\n       [514, 399,  90,  97],\n       [702, 794,  97,  99],\n       [721, 624,  98, 108],\n       [826, 512,  82,  94],\n       [883, 944,  79,  74],\n       [247, 594, 123,  92],\n       [673, 514,  95, 113],\n       [829, 847, 102, 110],\n       [ 94, 737,  92, 107],\n       [588, 568,  75, 107],\n       [158, 890, 103,  64],\n       [744, 906,  75,  79],\n       [826,  33,  72,  74],\n       [601,  69,  67,  87]]).float()\n\nscores = tensor([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])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"preds.shape,scores.shape,targs.shape","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# 1. Sort by scores\n\nSort predicted boxes in the descending order of their scores","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"preds = preds[scores.argsort().flip(-1)]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"The output of `calculate_iou` will be a matrix of shape ground-truth boxes(N) x predicted boxes (M)","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"iou_mat = calculate_iou(targs,preds,form='coco'); iou_mat[:4,:4]","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"gt_count, pr_count = iou_mat.shape","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# 2. Thresholding\n\nThresholding the iou-matrix (considering thresh=0.5 as of now)","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"thresh = 0.5\niou_mat = iou_mat.where(iou_mat>thresh,tensor(0.)); iou_mat[:4,:4]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# 3. Mapping logic","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"def get_mappings(iou_mat):\n    mappings = torch.zeros_like(iou_mat)\n    gt_count, pr_count = iou_mat.shape\n    \n    #first mapping (max iou for first pred_box)\n    if not iou_mat[:,0].eq(0.).all():\n        # if not a zero column\n        mappings[iou_mat[:,0].argsort()[-1],0] = 1\n\n    for pr_idx in range(1,pr_count):\n        # Sum of all the previous mapping columns will let \n        # us know which gt-boxes are already assigned\n        not_assigned = torch.logical_not(mappings[:,:pr_idx].sum(1)).long()\n\n        # Considering unassigned gt-boxes for further evaluation \n        targets = not_assigned * iou_mat[:,pr_idx]\n\n        # If no gt-box satisfy the previous conditions\n        # for the current pred-box, ignore it (False Positive)\n        if targets.eq(0).all():\n            continue\n\n        # max-iou from current column after all the filtering\n        # will be the pivot element for mapping\n        pivot = targets.argsort()[-1]\n        mappings[pivot,pr_idx] = 1\n    return mappings","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"mappings = get_mappings(iou_mat)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# 5. Calculating the TP,FP,FN\n\nAt this point, `mappings` will have `1` for all the true-positive (TP) and `0` for the rest. _(Note that, rows of the matrix represent ground-truth boxes while columns represent the predicted ones)_","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"## 5.1 True Positives (TP)\n\nAll the `1`s in the matrix are true-positives, but let's ensure that, no ground-truth/predicted box has been assigned twice","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"assert mappings.sum(1).le(1).all()\nassert mappings.sum(0).le(1).all()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"tp = mappings.sum(); tp","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 5.2 False Positives (FP)\n\n\"all-zeros\" column of `mappings` will be a False Positive (FP) prediction since it wasn't associated to any of the ground-truth boxes","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"fp = mappings.sum(0).eq(0).sum(); fp","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 5.3 False Negative (FN)\n\nSimilarly, \"all-zeros\" row will be considered as a False Negative (FN)","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"fn = mappings.sum(1).eq(0).sum(); fn","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Thus, mAP@.50 for given set of ground-truth and prediction boxes would be:","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"mAP = tp / (tp+fp+fn); mAP","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Putting it together","execution_count":null},{"metadata":{"trusted":true},"cell_type":"code","source":"def calculate_map(gt_boxes,pr_boxes,scores,thresh=0.5,form='pascal_voc'):\n    # sorting\n    pr_boxes = pr_boxes[scores.argsort().flip(-1)]\n    iou_mat = calculate_iou(gt_boxes,pr_boxes,form) \n    \n    # thresholding\n    iou_mat = iou_mat.where(iou_mat>thresh,tensor(0.))\n    \n    mappings = get_mappings(iou_mat)\n    \n    # mAP calculation\n    tp = mappings.sum()\n    fp = mappings.sum(0).eq(0).sum()\n    fn = mappings.sum(1).eq(0).sum()\n    mAP = tp / (tp+fp+fn)\n    \n    return mAP","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"calculate_map(targs,preds,scores,form='coco')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"calculate_map(targs,preds,scores,thresh=0.75,form='coco')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"**Note:** This notebook is intended to serve as a template for discussion in this direction and I'll be documenting the same as we progress. Your feedbacks are much appreciated! Thanks for your time.","execution_count":null},{"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}