Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Calculating percentage of Bounding box overlap, for image detector evaluation

In testing an object detection algorithm in large images, we check our detected bounding boxes against the coordinates given for the ground truth rectangles.

According to the Pascal VOC challenges, there's this:

A predicted bounding box is considered correct if it overlaps more than 50% with a ground-truth bounding box, otherwise the bounding box is considered a false positive detection. Multiple detections are penalized. If a system predicts several bounding boxes that overlap with a single ground-truth bounding box, only one prediction is considered correct, the others are considered false positives.

This means that we need to calculate the percentage of overlap. Does this mean that the ground truth box is 50% covered by the detected boundary box? Or that 50% of the bounding box is absorbed by the ground truth box?

I've searched but I haven't found a standard algorithm for this - which is surprising because I would have thought that this is something pretty common in computer vision. (I'm new to it). Have I missed it? Does anyone know what the standard algorithm is for this type of problem?

like image 674
user961627 Avatar asked Aug 17 '14 12:08

user961627


People also ask

How do you calculate bounding box accuracy?

The measure works by calculating the overlapping areas of intersection between two bounding boxes, divided by the total area of both bounding boxes. This produces an “accuracy score” that can be used to measure how close two bounding boxes match.

How do you calculate IOU of bounding boxes?

You're calculating the area of the intersection of the two boxes. And dividing by the area of the union of the two boxes. Well, go look at the "Jaccard index" (IoU) formula. The correct Jaccard Index formula is: iou = intersection_area / (union_area - intersection_area) .

How IoU is calculated?

IoU is calculated by dividing the overlap between the predicted and ground truth annotation by the union of these.

What is intersection over union and how is it used with object detection bounding boxes?

IOU(Intersection over Union) is a term used to describe the extent of overlap of two boxes. The greater the region of overlap, the greater the IOU. IOU is mainly used in applications related to object detection, where we train a model to output a box that fits perfectly around an object.


2 Answers

For axis-aligned bounding boxes it is relatively simple. "Axis-aligned" means that the bounding box isn't rotated; or in other words that the boxes lines are parallel to the axes. Here's how to calculate the IoU of two axis-aligned bounding boxes.

def get_iou(bb1, bb2):     """     Calculate the Intersection over Union (IoU) of two bounding boxes.      Parameters     ----------     bb1 : dict         Keys: {'x1', 'x2', 'y1', 'y2'}         The (x1, y1) position is at the top left corner,         the (x2, y2) position is at the bottom right corner     bb2 : dict         Keys: {'x1', 'x2', 'y1', 'y2'}         The (x, y) position is at the top left corner,         the (x2, y2) position is at the bottom right corner      Returns     -------     float         in [0, 1]     """     assert bb1['x1'] < bb1['x2']     assert bb1['y1'] < bb1['y2']     assert bb2['x1'] < bb2['x2']     assert bb2['y1'] < bb2['y2']      # determine the coordinates of the intersection rectangle     x_left = max(bb1['x1'], bb2['x1'])     y_top = max(bb1['y1'], bb2['y1'])     x_right = min(bb1['x2'], bb2['x2'])     y_bottom = min(bb1['y2'], bb2['y2'])      if x_right < x_left or y_bottom < y_top:         return 0.0      # The intersection of two axis-aligned bounding boxes is always an     # axis-aligned bounding box     intersection_area = (x_right - x_left) * (y_bottom - y_top)      # compute the area of both AABBs     bb1_area = (bb1['x2'] - bb1['x1']) * (bb1['y2'] - bb1['y1'])     bb2_area = (bb2['x2'] - bb2['x1']) * (bb2['y2'] - bb2['y1'])      # compute the intersection over union by taking the intersection     # area and dividing it by the sum of prediction + ground-truth     # areas - the interesection area     iou = intersection_area / float(bb1_area + bb2_area - intersection_area)     assert iou >= 0.0     assert iou <= 1.0     return iou 

Explanation

enter image description hereenter image description here

Images are from this answer

like image 94
Martin Thoma Avatar answered Sep 26 '22 03:09

Martin Thoma


The top-voted answer has a mathematical error if you are working with screen (pixel) coordinates! I submitted an edit a few weeks ago with a long explanation for all readers so that they would understand the math. But that edit wasn't understood by the reviewers and was removed, so I've submitted the same edit again, but more briefly summarized this time. (Update: Rejected 2vs1 because it was deemed a "substantial change", heh).

So I will completely explain the BIG problem with its math here in this separate answer.

So, yes, in general, the top-voted answer is correct and is a good way to calculate the IoU. But (as other people have pointed out too) its math is completely incorrect for computer screens. You cannot just do (x2 - x1) * (y2 - y1), since that will not produce the correct area calculations whatsoever. Screen indexing starts at pixel 0,0 and ends at width-1,height-1. The range of screen coordinates is inclusive:inclusive (inclusive on both ends), so a range from 0 to 10 in pixel coordinates is actually 11 pixels wide, because it includes 0 1 2 3 4 5 6 7 8 9 10 (11 items). So, to calculate the area of screen coordinates, you MUST therefore add +1 to each dimension, as follows: (x2 - x1 + 1) * (y2 - y1 + 1).

If you're working in some other coordinate system where the range is not inclusive (such as an inclusive:exclusive system where 0 to 10 means "elements 0-9 but not 10"), then this extra math would NOT be necessary. But most likely, you are processing pixel-based bounding boxes. Well, screen coordinates start at 0,0 and go up from there.

A 1920x1080 screen is indexed from 0 (first pixel) to 1919 (last pixel horizontally) and from 0 (first pixel) to 1079 (last pixel vertically).

So if we have a rectangle in "pixel coordinate space", to calculate its area we must add 1 in each direction. Otherwise, we get the wrong answer for the area calculation.

Imagine that our 1920x1080 screen has a pixel-coordinate based rectangle with left=0,top=0,right=1919,bottom=1079 (covering all pixels on the whole screen).

Well, we know that 1920x1080 pixels is 2073600 pixels, which is the correct area of a 1080p screen.

But with the wrong math area = (x_right - x_left) * (y_bottom - y_top), we would get: (1919 - 0) * (1079 - 0) = 1919 * 1079 = 2070601 pixels! That's wrong!

That is why we must add +1 to each calculation, which gives us the following corrected math: area = (x_right - x_left + 1) * (y_bottom - y_top + 1), giving us: (1919 - 0 + 1) * (1079 - 0 + 1) = 1920 * 1080 = 2073600 pixels! And that's indeed the correct answer!

The shortest possible summary is: Pixel coordinate ranges are inclusive:inclusive, so we must add + 1 to each axis if we want the true area of a pixel coordinate range.

For a few more details about why +1 is needed, see Jindil's answer: https://stackoverflow.com/a/51730512/8874388

As well as this pyimagesearch article: https://www.pyimagesearch.com/2016/11/07/intersection-over-union-iou-for-object-detection/

And this GitHub comment: https://github.com/AlexeyAB/darknet/issues/3995#issuecomment-535697357

Since the fixed math wasn't approved, anyone who copies the code from the top-voted answer hopefully sees this answer, and will be able to bugfix it themselves, by simply copying the bugfixed assertions and area-calculation lines below, which have been fixed for inclusive:inclusive (pixel) coordinate ranges:

    assert bb1['x1'] <= bb1['x2']     assert bb1['y1'] <= bb1['y2']     assert bb2['x1'] <= bb2['x2']     assert bb2['y1'] <= bb2['y2']  ................................................      # The intersection of two axis-aligned bounding boxes is always an     # axis-aligned bounding box.     # NOTE: We MUST ALWAYS add +1 to calculate area when working in     # screen coordinates, since 0,0 is the top left pixel, and w-1,h-1     # is the bottom right pixel. If we DON'T add +1, the result is wrong.     intersection_area = (x_right - x_left + 1) * (y_bottom - y_top + 1)      # compute the area of both AABBs     bb1_area = (bb1['x2'] - bb1['x1'] + 1) * (bb1['y2'] - bb1['y1'] + 1)     bb2_area = (bb2['x2'] - bb2['x1'] + 1) * (bb2['y2'] - bb2['y1'] + 1) 
like image 34
Mitch McMabers Avatar answered Sep 23 '22 03:09

Mitch McMabers