Matching by intersection over union and the sharpness of the threshold ½

Lax303562.Matching · concepts/Lax303562/Matching.lean · lax-303562

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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 00). 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
    1 concept
    100%
    Proven claimThis concept
    Evidence

    This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.

    1 matches_at_most_one proven

    2 threshold_sharp proven

    3 ties_at_half proven

    Lean source view on GitHub

    1import Mathlib.Data.Finset.Card
    2import Mathlib.Data.Real.Basic
    3
    4/-!
    5---
    6title: Matching by intersection over union and the sharpness of the threshold ½
    7type: theorem
    8---
    9Instances are finite sets of pixels. The intersection over union of two such sets
    10is the size of their intersection over the size of their union (with the
    11convention that the IoU of two empty sets is `0`). A prediction is matched to an
    12annotation when their IoU exceeds a threshold, and the published metric uses the
    13threshold `½` with a strict inequality.
    14
    15The first statement is why this threshold makes the matching unambiguous on the
    16annotation side: distinct annotations of one image are disjoint, and no
    17prediction can exceed IoU `½` with two disjoint sets. The second statement shows
    18that the strictness is necessary: with `≥ ½` a prediction can tie the threshold
    19with two disjoint annotations. The third states both at once: `½` is the infimum
    20of the thresholds under which a prediction matches at most one annotation.
    21-/
    22
    23namespace Lax303562.Matching
    24
    25/-- Intersection over union of two finite sets; `0` when both are empty. -/
    26noncomputable 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. -/
    30axiom 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
    35annotations. -/
    36axiom ties_at_half :
    37 ∃ (P A B : Finset ℕ), Disjoint A B ∧ (1 : ℝ) / 2iou P A ∧ (1 : ℝ) / 2iou P B
    38
    39/-- The threshold `½` is sharp: strictly above it the matching is unambiguous,
    40and at `½` it is not. -/
    41axiom 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 : ℝ) / 2iou P A →
    45 (1 : ℝ) / 2iou P B → False)
    46
    47end Lax303562.Matching
    48
    Show ProofShow ProofShow Proof
    Builds on

    none

    Used by

    none

    From Mathlib

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…