Distance transform

Overview

A distance transform turns a set of marked points into a map. Each pixel gets a value computed from its distance to the nearest marked point. The base quantity is the Euclidean distance to the nearest head 2102.07925 §3.1 eq. 1, which the paper calls the Euclidean distance transform 2102.07925 §2.3. A network can be trained to predict such a map, and the marked points can be recovered from the peaks of the prediction.

So far the only card on this concept is for crowd localization from point labels, so every variant below comes from one paper. The raw distance is transformed further, first by an inverse and then by a focal exponent, so that a head becomes a sharp local maximum and the background stays near zero 2102.07925 §3.1 eq. 2 eq. 3.

Variants

Euclidean nearest-point distance

The map P(x, y) is the distance from each pixel to the nearest head in the set of annotated points 2102.07925 §3.1 eq. 1. Distances are in pixels, so the map depends on image resolution (see Contradictions).

Inverse distance transform (IDT)

The inverse 1 / (P + C), with a constant C that avoids division by zero 2102.07925 §3.1 eq. 2. The paper notes that this is the K = 1 case of an iKNN map from Olmschenk et al., which that work did not use for localization 2102.07925 §3.1. The paper reports that its response decays too fast near a head and stays too high in background 2102.07925 §3.1 fig. 3. Its localization on ShanghaiTech Part A at sigma = 8 is an F-measure of 75.1%, against 77.6% for the focal version 2102.07925 tab. 9. Card: Focal Inverse Distance Transform Maps for Crowd Localization (IDT is its alpha = 0 case).

Focal inverse distance transform (FIDT)

The exponent of P grows with P, so the decay is slower near a head and the background goes to nearly zero 2102.07925 §3.1 eq. 3. The paper fixes alpha = 0.02, beta = 0.75 and C = 1 2102.07925 §4 tab. 9. Nearby settings reach F-measures of 76.3% (alpha 0.01, beta 0.65) and 76.9% (alpha 0.03, beta 0.85) on the same split 2102.07925 tab. 9. Heads are read off the map as local maxima, using a 3x3 max-pool and a threshold at 100/255 of the peak 2102.07925 §3.2.2 alg. 1. Card: Focal Inverse Distance Transform Maps for Crowd Localization.

When to use which

Implementation sketch

The target is built from the head points, then decoded by local maxima. Distances are in pixels, so resizing the image changes the target (see Contradictions).

# Build the FIDT target from head points  [arxiv:2102.07925 §3.1] [eq. 1] [eq. 3]
# Input:  image size (H, W); head points (x, y), in pixels
# Output: target map (H, W)

def fidt_target(H, W, points):
    # Distance to the nearest head, per pixel  [eq. 1]
    P = nearest_point_distance(H, W, points)
    # Focal inverse with C = 1, alpha = 0.02, beta = 0.75  [eq. 3] [§4]
    return 1 / (P ** (0.02 * P + 0.75) + 1)

# Decode heads from a predicted map  [arxiv:2102.07925 §3.2.2] [alg. 1]
# Input:  predicted map (H, W)
# Output: head coordinates, one row per head

def decode_heads(pred):
    # Keep pixels that equal their 3x3 neighbourhood maximum  [alg. 1]
    local_max = pred * (max_pool3x3(pred) == pred)
    peak = max(local_max)
    # Adaptive threshold: 100/255 of the peak  [§3.2.2]
    keep = local_max >= (100 / 255) * peak
    return coordinates_where(keep)

The paper also reports an empty-image rule: if the peak is below 0.10, the count is zero, and the 0.10 value was chosen from NWPU validation maxima 2102.07925 §3.2.2 §5.4 fig. 9. A model with a different loss scale needs its own value. The training loss is MSE plus a structural similarity term computed on a 30 x 30 region for each person, with weight 1 on each 2102.07925 §3.3 eq. 8. The card records that the released training script does not include the structural term.

Contradictions

None known across papers, because only one card exists. Open points within the one paper:

• Label types differ in the comparison. The paper's NWPU localization numbers set its point-labelled method against a box-trained baseline, TopoCount 2102.07925 §5.1.
• Resolution. Eq. 1 and eq. 3 use pixel distances, and the paper resizes the three large datasets to a longer side below 2048 2102.07925 §4. The paper does not discuss how alpha and beta interact with resizing.
• Reproduction. The loss ablation compares L2, L2 with SSIM, and L2 with the per-person structural term 2102.07925 tab. 10. The card records that the released training script does not include the structural term, so the ablation cannot be reproduced from the release.

Papers

• Focal Inverse Distance Transform Maps for Crowd Localization: defines the IDT and FIDT maps, the local-maxima decoder and an I-SSIM training term for point-supervised head localization.