Matching by intersection over union and the sharpness of the threshold ½
Lax303562.Matching · concepts/Lax303562/Matching.lean · lax-303562
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Instances are finite sets of pixels. The intersection over union of two such sets is the size of their intersection over the size of their union (with the convention that the IoU of two empty sets is ). A prediction is matched to an annotation when their IoU exceeds a threshold, and the published metric uses the threshold with a strict inequality.
The first statement is why this threshold makes the matching unambiguous on the annotation side: distinct annotations of one image are disjoint, and no prediction can exceed IoU with two disjoint sets. The second statement shows that the strictness is necessary: with a prediction can tie the threshold with two disjoint annotations. The third states both at once: is the infimum of the thresholds under which a prediction matches at most one annotation.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Mathlib.Data.Finset.Card |
| 2 | import Mathlib.Data.Real.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Matching by intersection over union and the sharpness of the threshold ½ |
| 7 | type: theorem |
| 8 | --- |
| 9 | Instances are finite sets of pixels. The intersection over union of two such sets |
| 10 | is the size of their intersection over the size of their union (with the |
| 11 | convention that the IoU of two empty sets is `0`). A prediction is matched to an |
| 12 | annotation when their IoU exceeds a threshold, and the published metric uses the |
| 13 | threshold `½` with a strict inequality. |
| 14 | |
| 15 | The first statement is why this threshold makes the matching unambiguous on the |
| 16 | annotation side: distinct annotations of one image are disjoint, and no |
| 17 | prediction can exceed IoU `½` with two disjoint sets. The second statement shows |
| 18 | that the strictness is necessary: with `≥ ½` a prediction can tie the threshold |
| 19 | with two disjoint annotations. The third states both at once: `½` is the infimum |
| 20 | of the thresholds under which a prediction matches at most one annotation. |
| 21 | -/ |
| 22 | |
| 23 | namespace Lax303562.Matching |
| 24 | |
| 25 | /-- Intersection over union of two finite sets; `0` when both are empty. -/ |
| 26 | noncomputable def iou {α : Type*} [DecidableEq α] (X Y : Finset α) : ℝ := |
| 27 | ((X ∩ Y).card : ℝ) / ((X ∪ Y).card : ℝ) |
| 28 | |
| 29 | /-- No prediction has IoU strictly above `½` with two disjoint annotations. -/ |
| 30 | axiom matches_at_most_one {α : Type*} [DecidableEq α] (P A B : Finset α) |
| 31 | (hAB : Disjoint A B) (hA : (1 : ℝ) / 2 < iou P A) (hB : (1 : ℝ) / 2 < iou P B) : |
| 32 | False |
| 33 | |
| 34 | /-- With the non-strict threshold `≥ ½` a prediction can tie with two disjoint |
| 35 | annotations. -/ |
| 36 | axiom ties_at_half : |
| 37 | ∃ (P A B : Finset ℕ), Disjoint A B ∧ (1 : ℝ) / 2 ≤ iou P A ∧ (1 : ℝ) / 2 ≤ iou P B |
| 38 | |
| 39 | /-- The threshold `½` is sharp: strictly above it the matching is unambiguous, |
| 40 | and at `½` it is not. -/ |
| 41 | axiom threshold_sharp : |
| 42 | (∀ (P A B : Finset ℕ), Disjoint A B → (1 : ℝ) / 2 < iou P A → |
| 43 | (1 : ℝ) / 2 < iou P B → False) |
| 44 | ∧ ¬ (∀ (P A B : Finset ℕ), Disjoint A B → (1 : ℝ) / 2 ≤ iou P A → |
| 45 | (1 : ℝ) / 2 ≤ iou P B → False) |
| 46 | |
| 47 | end Lax303562.Matching |
| 48 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments