Vectorize `compute_iou_matrix` with NumPy

[dpascualhe]

In our detection_metrics module, compute_iou_matrix currently uses a Python double for loop to fill a matrix of IoU values, which is slow for large datasets.

# current (slow)
for i, pb in enumerate(pred_boxes):
    for j, gb in enumerate(gt_boxes):
        iou_matrix[i, j] = compute_iou(pb, gb)

Deliverables: rewrite said function using fully vectorized NumPy broadcasting to compute all pairwise IoUs at once and make sure that the new implementation still yields the exact same results

[Arkadeep455]

Hi there,
I have started working on this issue.

[dpascualhe]

@Arkadeep455 , before starting to work in this issue. How do you plan to tackle it down?

[Arkadeep455]

So, my first approach even before I start any coding is to analyze the code and identify the design pattern which in this case is I think is a creation pattern. Once, I have fully analyzed the code and understood the problem statement, I write the code in different languages to check it's execution time and to figure out if it will improve the performance of the overall code. Since, this problem statement is all about calculations, I have chosen C language as it will speeds up calculations and to achieve better optimization.

After all this I went after the main problem statement. My first approach was parallel processing after few iterations I started all over again with NumPy broadcasting after some research.

Also, I tried to run only that loop in C so that the code remains same and the loop gets executed in hardware level and it worked out well. I am planning to include that part inside comments.

Now, shall I make a pull request?

[Bissmella]

Hi @dpascualhe

I would also like to contribute to this issue as well if possible :)

Here is my proposed plan:
Based on the compute_iou_matrix, and iou_matrix functions, the predictions has shape of [N, 4] and the ground-truths have shape of [M, 4]. We need to compare each i for N with all M ground truth boxes.

1. We do following reshaping to allow broadcasting and comparison of each prediction to all ground truth:

predictions: [N, 4] --> [N, 1, 4]
ground-truth:     [M, 4] --> [1, M, 4]

2. Intersections can be found easily (again based on code the boxes are in top-left, bottom-right format) so the intersection x1, x2, y1, y2 can be calculated by getting the maximum of top-left coordinates (x1, y1) and minimum of bottom-right coordinates (x2, y2). Results: 4 intersection arrays x1, x2, y1, y2 with shapes of [N, M]

3. Calculate intersection area by first calculating width and height from arrays in step 2. The intersection area is simply width x height resulting to intersection-area array of shape [N, M]

4. Calculate union by union = prediction-area + ground-truth-area - intersecation-area because intersection is included in both pred and ground-truth.

5. Calculate and return iou = intersection-area / union

So both functions become one with no for loops.

[dpascualhe]

Thanks to both of you for your proposals!

@Arkadeep455 , your approach seems a bit overengineered. We should be keeping things pure Python, especially as this is not super critical. I think we can go with @Bissmella solution, but I'd love if you could test and review it whenever the PR is ready.

@Bissmella , can you raise your PR and mention @Arkadeep455 and myself so that we can review it? Thanks!

[Arkadeep455]

Hi @dpascualhe,

I wrote the code in pure python language, did not include any C code or anything else after analysis.

Just saw your reply after pushing all the changes. Took me a bit of time for the test cases to pass. Let's see what @Bissmella thinks about this.