Bird
Raised Fist0

Implement IoU and Non-Max Suppression for Object Detection

CODINGintermediateInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
šŸ¤–
Implement IoU and Non-Max Suppression for Object Detection
Efficiently filter overlapping bounding boxes in object detection.
codingintermediateFreq: highEvaluation Coding
Prerequisites:Computer Vision - Object Detection
šŸ“
Problem Statement

Implement Intersection over Union (IoU) and Non-Max Suppression (NMS) for object detection. Given a list of bounding boxes and their corresponding confidence scores, return the list of bounding boxes after applying NMS.

I/O Specification
Input:  List of bounding boxes (x1, y1, x2, y2) and their confidence scores.
Output: Filtered list of bounding boxes after applying NMS.
Example
{
  "input": "boxes = [(100, 100, 210, 210), (105, 105, 215, 215), (200, 200, 310, 310)], scores = [0.9, 0.8, 0.7]",
  "expected_output": "[(100, 100, 210, 210), (200, 200, 310, 310)]"
}
šŸŽÆ
Interview Angles
  • Understanding of IoU and its role in object detection.
  • Ability to optimize algorithms using vectorized operations.
  • Handling edge cases in object detection scenarios.
  • Balancing precision and recall in object detection through NMS.
šŸ”µ
Naive Approach

Calculate IoU for each pair of boxes and suppress boxes with lower scores if IoU exceeds a threshold.

O(nĀ²) - For each box, we potentially compare it with every other box.
Why Insufficient
O(nĀ²) because it recomputes IoU for each pair of boxes - fails for n > 10K.
šŸ
Naive Code
Python
import numpy as np

def iou(box1, box2):
    x1 = max(box1[0], box2[0])
    y1 = max(box1[1], box2[1])
    x2 = min(box1[2], box2[2])
    y2 = min(box1[3], box2[3])
    intersection = max(0, x2 - x1) * max(0, y2 - y1)
    area1 = (box1[2] - box1[0]) * (box1[3] - box1[1])
    area2 = (box2[2] - box2[0]) * (box2[3] - box2[1])
    union = area1 + area2 - intersection
    return intersection / union

def non_max_suppression(boxes, scores, iou_threshold):
    indices = np.argsort(scores)[::-1]
    selected_boxes = []
    while len(indices) > 0:
        current = indices[0]
        selected_boxes.append(boxes[current])
        indices = indices[1:]
        indices = [i for i in indices if iou(boxes[current], boxes[i]) < iou_threshold]
    return selected_boxes

boxes = [(100, 100, 210, 210), (105, 105, 215, 215), (200, 200, 310, 310)]
scores = [0.9, 0.8, 0.7]
print(non_max_suppression(boxes, scores, 0.5))
šŸ’”
Key Insight
Sort boxes by scores and use vectorized operations to compute IoU, reducing redundant calculations.
šŸ
Optimized Code
Python
import numpy as np

def iou(box1, box2):
    x1 = np.maximum(box1[0], box2[0])
    y1 = np.maximum(box1[1], box2[1])
    x2 = np.minimum(box1[2], box2[2])
    y2 = np.minimum(box1[3], box2[3])
    intersection = np.maximum(0, x2 - x1) * np.maximum(0, y2 - y1)
    area1 = (box1[2] - box1[0]) * (box1[3] - box1[1])
    area2 = (box2[2] - box2[0]) * (box2[3] - box2[1])
    union = area1 + area2 - intersection
    return intersection / union

def non_max_suppression(boxes, scores, iou_threshold):
    indices = np.argsort(scores)[::-1]
    selected_boxes = []
    while len(indices) > 0:
        current = indices[0]
        selected_boxes.append(boxes[current])
        if len(indices) == 1:
            break
        rest_boxes = np.array(boxes)[indices[1:]]
        ious = np.array([iou(boxes[current], box) for box in rest_boxes])
        indices = indices[1:][ious < iou_threshold]
    return selected_boxes

boxes = [(100, 100, 210, 210), (105, 105, 215, 215), (200, 200, 310, 310)]
scores = [0.9, 0.8, 0.7]
print(non_max_suppression(boxes, scores, 0.5))
šŸ”
Line-by-Line
indices = np.argsort(scores)[::-1]
Sort indices of boxes by descending scores to prioritize higher confidence boxes.
selected_boxes.append(boxes[current])
Add the current box with the highest score to the result list.
if len(indices) == 1:
Check if only one box is left to avoid unnecessary IoU calculations.
rest_boxes = np.array(boxes)[indices[1:]]
Select the remaining boxes to compare against the current box.
ious = np.array([iou(boxes[current], box) for box in rest_boxes])
Compute IoU for the current box against all remaining boxes in a vectorized manner.
indices = indices[1:][ious < iou_threshold]
Filter out boxes with IoU above the threshold, keeping only those below.
āš”
Complexity
O(n log n) - Sorting the boxes by score takes O(n log n), and each IoU computation is O(1) due to vectorization.
Output
[(100, 100, 210, 210), (200, 200, 310, 310)]
šŸ”²
Edge Cases
No boxes
Returns an empty list as there are no boxes to process.
if len(indices) == 0: return selected_boxes
Single box
Returns the single box as there are no overlaps to suppress.
if len(indices) == 1: break
All boxes suppressed
Returns an empty list if all boxes have IoU above the threshold.
indices = indices[1:][ious < iou_threshold]
āš ļø
Common Mistakes
Incorrect IoU calculation leading to wrong suppression.
Symptom: Boxes that should be suppressed are not, or vice versa.
Not sorting boxes by score before suppression.
Symptom: Lower confidence boxes are incorrectly retained.
Failing to handle edge cases like no boxes or single box.
Symptom: Code crashes or returns incorrect results for edge cases.
Using loops instead of vectorized operations.
Symptom: Code is significantly slower on large inputs.

Practice

(1/5)
1. What is the time complexity of computing the forward pass for a single layer in a neural network using NumPy?
easy
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(1)

Solution

  1. Step 1: Identify operations

    Forward pass involves matrix-vector multiplication.

  2. Step 2: Determine complexity

    Matrix-vector multiplication is O(n) where n is the number of neurons.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Matrix-vector multiplication is O(n) [OK]
Hint: Matrix-vector multiplication is O(n) [OK]
Common Mistakes:
2. 
import numpy as np

confusion_matrix = np.array([[50, 10], [5, 35]])

precision = confusion_matrix[0, 0] / (confusion_matrix[0, 0] + confusion_matrix[1, 0])
recall = confusion_matrix[0, 0] / (confusion_matrix[0, 0] + confusion_matrix[0, 1])

print(f"Precision: {precision}, Recall: {recall}")
easy
A. Precision: 0.8333, Recall: 0.8333
B. Precision: 0.9091, Recall: 0.9091
C. Precision: 0.8333, Recall: 0.9091
D. Precision: 0.9091, Recall: 0.8333

Solution

  1. Step 1: Calculate Precision

    Precision is calculated as TP / (TP + FP) = 50 / (50 + 5) = 0.9091.

  2. Step 2: Calculate Recall

    Recall is calculated as TP / (TP + FN) = 50 / (50 + 10) = 0.8333.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Precision uses FP, Recall uses FN. [OK]
Hint: Precision uses FP, Recall uses FN. [OK]
Common Mistakes:
3. 
import numpy as np

def euclidean_distance(a, b):
    return np.sqrt(np.sum((a - b) ** 2))

vector1 = np.array([1, 2, 3])
vector2 = np.array([4, 5])

result = euclidean_distance(vector1, vector2)
print(result)
medium
A. Returns NaN due to broadcasting
B. Throws a ValueError due to shape mismatch
C. Returns 0.0
D. Returns a large number due to incorrect subtraction

Solution

  1. Step 1: Check vector shapes

    vector1 has shape (3,), vector2 has shape (2,).

  2. Step 2: Identify operation failure

    Subtraction fails due to shape mismatch, raising a ValueError.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Shape mismatch leads to ValueError. [OK]
Hint: Shape mismatch leads to ValueError. [OK]
Common Mistakes:
4. You implemented PCA but the variance explained by the first principal component is unexpectedly low. What is the most likely cause?
medium
A. Data was not centered before computing the covariance matrix.
B. Eigenvectors were not normalized.
C. Covariance matrix was computed using rowvar=True.
D. Too few principal components were selected.

Solution

  1. Step 1: Identify the impact of centering data

    Centering data is crucial for PCA as it ensures the covariance matrix reflects true variance.

  2. Step 2: Eliminate wrong options

    Eigenvectors were not normalized. is incorrect because normalization affects direction, not variance. Covariance matrix was computed using rowvar=True. affects orientation, not variance. Too few principal components were selected. is irrelevant to the variance of the first component.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Center data before PCA to capture variance. [OK]
Hint: Center data before PCA to capture variance. [OK]
Common Mistakes:
5. How can you optimize the dropout layer implementation to reduce computational overhead during training?
hard
A. Use in-place operations to apply the mask.
B. Use a fixed mask for all training iterations.
C. Precompute masks for all layers before training.
D. Reduce the dropout rate to minimize mask application.

Solution

  1. Step 1: Identify Optimization Opportunities

    In-place operations reduce memory usage and computational overhead by modifying data directly.

  2. Step 2: Eliminate Wrong Options

    Use a fixed mask for all training iterations. reduces randomness, harming model performance. Precompute masks for all layers before training. increases memory usage. Reduce the dropout rate to minimize mask application. changes model behavior, not efficiency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    In-place operations save memory and time. [OK]
Hint: In-place operations save memory and time. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard