Mean Average Precision (mAP) | Explanation and Implementation for Object Detection

this video will be covering intersection over Union non- maximum suppression and mean average Precision this is the second video of the object detection series and in this one we'll first do a very quick review of IOU see how it's implemented in code then revisit nms and lastly we'll get into map where we'll first see different parts involved in Computing map calculate mean average Precision step by step for an example and finally see how to implement it so let's start with IOU we have already looked at the common ways of defining bounding boxes the first one by top left and bottom right Corners X1 y1 and X2 Y2 the second one was by the coordinates of center of box X comma Y and width and height and we saw that it's easy to convert from one to the other for this video I'll assume the top left and bottom right coordinates specification for the bounding box but since they are interconvertible it shouldn't really matter intersection of a union is a measure of overlap between two boxes and gives a sense of how well the two boxes align with each other and given a predicted box in red and ground truth box in green we can use intersection over Union to evaluate how good our prediction is it is mathematically defined as the area of intersection between the boxes divided by the area of Union of the two boxes here are some variations of predicted box positions and their IOU with respect to a fixed ground truth in order to get a sense of how to implement it let's look at various samples of box positions and for each of them these are the coordinates X1 y1 and X2 Y2 of the two corners green colored coordinates for the green box and red ones are for the red box in order to compute the area of intersection required for IOU we need the width and height of this overlap rectangle focusing on the top left corner of the overlap rectangles for all of these cases you can see that the X1 coordinate of this corner is the max of X1 of the red box and the X1 of green box so whichever X1 is larger that will be the x coordinate for this corner of the overlap rectangle and same for y1 as in the y coordinate of this corner it will be the maximum of y1 of red box and y1 of green box now for the bottom right corner of these overlap rectangles in this case from these examples it's clear that the x coordinate of the bottom right corner is the minimum of X2 of red box and X2 of green box and similarly Y2 that is the y coordinate of the bottom right corner of these overlap rectangles seems to be minimum of Y2 of red and Y2 of green box and once the x and y coordinate of the corners of these overlap rectangles are computed calculating the area is just the product of difference of the y-coordinates and the x coordinates that covers the numerator part the denominator which is the area of Union will just be the sum of the areas of the two boxes minus the area of intersection so now let's put everything that we have in code for implementations the goal will be to project what's happening inside the functions in the simplest manner purely from understanding perspective rather than trying to make the implementation most efficient so this getor IOU method will compute the intersection of a union for us and it's going to takeen two boxes for which the IOU needs to be calculated and the argument boxes will be a list of four values X1 y1 and X2 Y2 we'll first extract these coordinates from the input list and then we'll compute the coordinates of corners of the overlapping rectangle we saw that the top left X1 and y1 is just the max of X1 and y1 of both the boxes and bottom right X2 and Y2 is the minimum of X2 and Y2 of both the boxes now if the values are such that X2 is less than X1 or Y2 is less than y1 then this is a case where boxes don't overlap at all so we can just return zero as the IOU right away but if that's not the case then there is some overlap so we compute the intersection area as the product of X2 - X1 and Y2 - y1 and now for the denominator part we also compute the individual box areas we add them up and subtract the intersection area to get the area of Union and then finally return IOU as intersection divide by area of Union it would make sense to also do some assertions before Computing IOU just to ensure that the Box coordinates are indeed valid like here debore X2 should be greater than debore X1 and so on but this is all we essentially need for computing IOU next we move to non- maximum suppression we saw in our previous rcnn video that we need non- maximum suppression as a post-processing step to ensure that we filter out all the Redundant or duplicate boxes that our model predicts for an image and the way we do that is we start off with all the predictions by a model and then apply nms separately for each class for each of the predictions we also have a confidence score which either the model can predict separately or it could just be the classification probability for the class that model predicts we then sort the detections using the confidence score in a decreasing order so let's say we start with person class then we pick the highest confidence box remove it from our predictions list and add it to our final output detections list from the predictions we also remove all instances which have an overlap greater than some predefined threshold with this highest confidence box we repeat this step till no prediction ins tenses of this person class remain and then we repeat the same steps for all classes applying this postprocessing step for all the classes would remove the duplicate boxes and leave us with a filtered set of predictions where each prediction belongs to a different object instance so basically suppress the ones that are not maximum scoring to summarize these steps we apply nms separately for each class sort predictions by confidence score create a list of detections to keep and repeat the following steps till the list of predictions is not empty we remove the highest confidence box and add it to the list of detections to keep we also remove all predictions that have high overlap with this maximum scoring instance the list of detections to keep is what the nms method will finally return so let's Implement that now this nms method will do the non- maximum suppression for us and receives a list of detections as the argument the detections will be a list of boxes each having five values X1 y1 X2 Y2 and score the first thing we do is sort based on decreasing order of confidence score this keep underscore debts will be output detections list we are going to iterate till we have some predictions left in our sorted detections list and within this Loop we first get the maximum confidence box and add it to our keep list the next thing that we do is remove this and all the other boxes that have high overlap with this maximum confidence box and our overlap threshold is defined by the nms uncore threshold argument to do this we'll update our sorted uncore debts to now be a list with all boxes from index one that have an overlap less than threshold with the zeroth index box which is the maximum confidence box because of sorting the iteration from index one ensures that the maximum confidence box is also removed from the sorted uncore debts list this minus one is needed because the IOU method that we implemented accepts box as a list of X1 y1 and and X2 Y2 so every iteration in the loop keeps reducing the size of sorted debts until finally it's empty and then we return the keep undor debts list as our post nms filter detections note that up till now I said that nms is applied for each class independently but there is nothing stopping us from applying nms in a class agnostic Manner and this decision depends primarily on the use case and some of the later methods that we will see indeed use class agnostic nms so nms can either receive boxes per class and be called separately for each class or it can receive all boxes and run in a class agnostic fashion now finally we are on to the main part of this video which is map or mean average precision mean average Precision is one of the Benchmark metrics that we use to evaluate and compare performance of object detection models Even in our previous video looking at rcnn results we saw that map was used for comparing performance between different models but before map let's talk a bit about precision and recall given a set of predictions by a model and since we are working with object detection let's say our predictions are boxes that our model predicts to be a person and our corresponding ground truth will be the ground truth boxes belonging to person class the overlapping region between these two that is boxes which we predicted to have a person and there is indeed a person in that location will be true positives boxes where our model incorrectly predicts a person to be present will be false positives and those ground truth person instances which our model fails to detect will be false negative Precision is the metric which tells us that of all the predictions that our model made how many were actually correct in our person detection case this means of all the boxes where our model predicted a person to be present how many of those got matched to a valid ground truth person box and by match I mean had a high overlap measured using IOU with a ground truth box so this will be true positive divide by true positive plus false positive and recall means of all the ground truth boxes how many were actually detected by a model so how many of the ground truth person boxes had high overlap with a predicted Box by a model and this will be true positive divide by true positive plus false negative or true positive divide by number of ground truth boxes we want both these metrics to be of high value so here assume we want to detect cars and person so just having a high precision and low recall will mean that our predicted boxes are indeed valid instances but we'll miss a lot of valid op objects and if we have a very high recall but low Precision that means while we cover all ground truth person and cars we'll also generate a lot of false positives which is again bad there's a trade-off between both and ideally we want both to be high cuz we don't want to miss a lot of ground truth objects so less false negatives and simultaneously we don't want to detect objects where actually there aren't any so no false positives for getting to what map means we need to understand what AP means AP stands for average precision and actually to understand that we need to get into Precision recall curve Precision recall curve plots the value of precision against recall for different confidence threshold values so what does this exactly mean remember for our object detection case we used confidence score and for now just think of it as the class probability that the model predicts then usually higher the class probability higher the chance that the box contains an instance of that class we can then use different threshold values to decide if a prediction should be marked as positive or not like assume here if we decide that threshold to be 0.9 so then only the very high confidence scoring boxes as in those with greater than equals to 0.9 will be marked as valid object predictions by a model so this would mean that we make smaller number of Highly confident detections and generally that would reduce the chance that we capture all ground truth objects which means that the recall is low but our Precision will be high because all our predictions are highly confident predictions and would most likely be correct on the other hand if we use a very low confidence threshold say 0.25 that means we would make a large number of detections so higher chance to capture all ground truth objects so generally High recall but because there are quite a few low confidence boxes that would also mean low precision as we would also be including a lot of false positives not necessarily but generally I say generally for both the cases because it could happen that all the newly added low confidence scoring boxes end up being false positives then even after reducing the confidence threshold our recall will actually not increase the average Precision summarizes Precision recall curve into one single value and is effectively the area under the Precision recall curve and you can see that if a model achieves High Precision values even at high recall levels then the area under the Precision recall curve would be larger and hence a higher AP now let's see how to compute map using an example to make things clearer so here assume these are the the two images and the green boxes are the ground truth boxes and there are only two object types person and car hence these are the ground truth regions this is the prediction by our model and for Simplicity assume it predicts the right class for each of them so then these are the detected regions Also let's give random scores for the predicted boxes we compute AP for each class separately and for now let's just see how we would compute AP for person class we'll take all the predicted boxes that have person as the predicted class similar to nms we'll sort them in decreasing order of their confidence scores we start picking detections in that order and for each find the best matching ground truth box for matching we only consider the ground truth box that belong to the same class so here person and of the same image which means these four ground truth boxes we pick the best matching ground truth box based on overlap and this ground truth box comes out to have the highest overlap of 0.71 then if this ground truth box has not been matched before and if its IOU is greater than some predefined threshold we mark it as a true positive and we mark this ground truth box as matched we are marking this as matched because future detections for which this this already matched ground truth box ends up being the best one we'll mark those detections as false positives because this ground truth box has already been taken assume our predefined threshold is 0.65 then we mark this as matched and we start building this true positive and false positive table which will just be zero or one for each instance this guy was a true positive so we mark one and zero here then we move to the next confident box and repeat the same here there's only one ground truth person box present in this image so that ends up being the best matching ground truth box but the overlap ends up being less than our threshold so we'll mark this prediction as a false positive then comes this detection repeating the same we find the best ground truth box again this best ground tooth box is not yet matched and its IOU is greater than the threshold so it's also a true positive and we mark this also as matched the remaining two are also matched to their respective ground truth boxes now we start accumulating these true positive values and false positive values as we go down this table each cell here is just a sum of the current value and the values that came before it lastly we compute the Precision and recall for each of those cells precision is computed using true positive and false positive cumulative values recall on the other hand is just a fraction of ground truth boxes that we actually covered so there were five ground truth person boxes so we use that and the cumulative true positive values to compute recall these values are just the Precision and recall values that we would get using the different confidence threshold for example look at this row if we used a confidence threshold of 0.83 the two detections below it will be ignored and we would effectively have predicted three boxes out of which two would be correct so 2x3 will be the Precision and out of the five ground truth person boxes we only detected two so 2x 5 would be the recall with these points we plot the Precision and recall curve and like we saw finding the area within this Curve will give us the average precision but this is the average Precision for person class doing the same for all classes and taking the mean of those APS would give us maap and here we computed this average Precision metric using an IOU threshold of 0.65 in papers you will often see this metric which just means that we are Computing maps at all IOU threshold values starting from 0.5 till 0.95 at intervals of 0.05 and and the final map metric is the average of maps at different IOU threshold values the actual computation of AP from the Precision recall curve can be done using multiple approaches and typically the object detection challenges will specify the method that would be used to compute AP one of them is through interpolation and the other is through approximating the area under the curve using rectangles let's see the area approach first so this was our original plot the first thing we do is add boundary Precision recall values these are 0a 0 at both the extremes of precision values and 0a 1 at both the extremes of recall values then we get rid of the zigzag nature of the plot by replacing each Precision value with the maximum Precision value on the right and now the area is computed by calculating the area of these rectangles so here the boundary point 0a 0 gets replaced with 0a 1 as that's the maximum on the right and similarly for all of these points the Precision gets modified to 0.8 as that is the maximum value on the right for computing the area the way we do in implementation is that we find points where the recall value changes and then keep adding these rectangular areas each of these is simply the change in recall from from the previous value times the Precision value the other approach is to calculate the interpolated average Precision value which we get by using a set of equally spaced recall points so for instance for vocc 2007 challenge they used 11 Point interpolation then for each of these equally spaced points we compute the interpolated precision as the maximum Precision value for all recall levels which are greater than equal to that point so for 0 0.1 and 0.2 that value will be 1 for points from 0.3 till 0.8 that value will be 0.8 and for points after the maximum recall value in our plot we assume the Precision to be zero then AP is the average of these interpolated Precision values and here we had 11 points so this will be our AP a thing to keep in mind is that the exact calculation of AP is actually different for different data sets like for KOCO we have 101 Point interpolation for vocc 2007 11 Point interpolation was used so it's best to take a look at the data set or challenge provided source code to understand what exact method they are using we will now look at an implementation of AP and here I have mostly used parts of code from mm detection and ultral litics library and we'll compute AP using the area as well as 11o interpolation method our computor map method will receive the detection boxes and the ground truth boxes and detection boxes would be a list of dictionary with the dictionary at index I holding bounding box details for imagei these will have classes as the keys and list of bounding boxes as the values which would be all boxes that the model predicted to be of that particular class for the image at that index for our example of two classes person and car this is how it would look the bounding box information will be X1 y1 X2 Y2 and confidence score the ground truth boxes will have similar structure except that bounding box list will only have four values X1 y1 and X2 Y2 we first just get the different classes because we need to compute a separately for each of them so it just goes over the ground truth boxes and collects the set of keys this list will hold the AP for each class now we Loop over each class and first we'll fetch all the prediction boxes for all the images belonging to this class this will be a list of list every item in this list will have two values first being the index of the image this detection belongs to and second will be the bounding box information together with score then like we had seen the first thing we do is sort these detection by confidence score the negative sign basically ensures that it's in decreasing order of confidence scores since we want to maintain information regarding which ground truth box has been matched we create this GT matched variable for that purpose initially all ground truth boxes are unmatched so we have false as their value this is a nested list with the outer list being for the different images and the inner list is of length equal to the number of ground truth boxes of this class present in that image then we get the total number of ground truth boxes for this class this is needed for the recall computation and for this we simply iterate over the images and keep adding the number of boxes for this class in each image these are our true positive and false positive values for each prediction initialized to be all zero now this Loop will go over all the predictions for each prediction we get all ground truth boxes belonging to this image and this class then we attempt to find the best matching ground truth box where for each of these ground truth boxes we are getting the IOU with the predicted box and finally getting the one with the best intersection over Union if this best box has an IOU greater than threshold and it's not yet matched we Mark true positive for this index to be one and also Mark this ground truth box as matched otherwise we'll mark false positive to be one so even if IOU is greater but the ground truth box is already matched to a higher confidence detection we will end up marking this as a false positive then we compute our cumulative true positive and false positive values and recall and precision is computed just like we had seen we talked about two methods of computing AP so let's look at the area method first here we append the boundary values to both recall and precision values then remove the zigzag Nature by replacing each Precision value with the maximum imum Precision value on the right this line identifies the points where the recall values change and then this computes the area of each of these rectangles and adds them up for the interpolation and here we use 11 Point interpolation we first generate 11 equally spaced points from 0 to 1 for each point we get interpolated precisions as the Precision values for all recall levels greater than that point we fetch the max of these interpolated Precision values and keep adding them up and finally divide by 11 now all of this would have computed the AP for one class and for each class we keep repeating and adding it to our ap's list and finally map is just the mean this will compute map for 1 I threshold if we want to compute map as a mean over multiple IOU thresholds we simply call this function for each of those threshold values get the respective Bean average precisions and take mean of that and with this we are done with the map implementation which was the last part of this video so in this video we got into all the necessary components for evaluation of object detection models we had already seen IOU and nms in previous video but in this one we also implemented it and we also discussed about mean average precision and its implementation so hopefully all the details regarding map are a bit clearer for you in the next video we'll continue our rcnn to YOLO V8 journey and move to fast and faster rcnn as always thank you for watching this video and I hope you have a great [Music] day