Position Validation Algorithms for Planograms

Within the Planogram Sync & SKU Mapping Strategies section, position validation is the stage that decides where every detected product actually sits relative to where the planogram said it should be. It consumes catalog-resolved detections and the authoritative slot geometry, and it emits the slot-mapped detections that every downstream compliance metric depends on. Get this wrong and nothing after it can be trusted: a detection assigned to the neighboring slot produces a phantom out-of-stock on one position and a phantom over-face on the next, and the error propagates silently into the score a category manager reads at 7am. This page defines the data contract this stage enforces, the homography-and-assignment architecture that runs underneath it, the spatial thresholds that tune it, the failure modes you will actually hit on angled cameras and dense shelves, and the latency budget you have to design against to validate a chain in near real time.

Concept & Data Contract Jump to heading#

Position validation sits between SKU resolution and facing reconciliation, so it has two hard boundaries. At the inbound boundary it consumes SKU-resolved detections — the pixel-space bounding boxes produced upstream by Bounding Box Extraction & SKU Localization, each already carrying a canonical sku, a box confidence, and the capture_timestamp of the frame it came from. Alongside the detections it reads the authoritative planogram geometry: every slot_id, the SKU the slot is reserved for, and the slot’s rectangle expressed in normalized fixture coordinates rather than pixels. At the outbound boundary it produces slot-mapped detections — for each detection, the slot_id it was assigned to, the metric centroid displacement from that slot’s anchor, the Intersection-over-Union against the slot rectangle, and a graded position state that the facings and promotional stages consume verbatim.

The whole point of the contract is that pixels never cross the outbound boundary. Downstream stages must not care what camera, focal length, or mount angle produced the frame; they only see a SKU sitting in a slot at a measured offset. A slot-mapped detection record looks like this:

{
  "planogram_id": "PG-2026-GROCERY-A14",
  "fixture_id": "BAY-014-SHELF-03",
  "registry_revision": 184,
  "capture_timestamp": "2026-06-28T07:42:11Z",
  "homography_rms_px": 1.8,
  "assignments": [
    {
      "slot_id": "BAY-014-SHELF-03-POS-07",
      "expected_sku": "00012345678905",
      "detected_sku": "00012345678905",
      "centroid_offset_mm": 6.4,
      "slot_iou": 0.81,
      "box_confidence": 0.94,
      "position_state": "in_position"
    },
    {
      "slot_id": "BAY-014-SHELF-03-POS-08",
      "expected_sku": "00098765432107",
      "detected_sku": "00012345678905",
      "centroid_offset_mm": 41.2,
      "slot_iou": 0.37,
      "box_confidence": 0.88,
      "position_state": "misplaced"
    }
  ],
  "unassigned_detections": 1,
  "vacant_slots": ["BAY-014-SHELF-03-POS-11"]
}

The position_state enum is graded, not binary — in_position, shifted, misplaced, and vacant — because a binary in/out flag is useless to the people who act on it. A SKU 6.4 mm off its anchor but squarely inside its slot is in_position; the same SKU drifting toward a neighbor but still correctly identified is shifted; a foreign SKU occupying a slot is misplaced; a slot with no qualifying detection is vacant. Every record carries the homography_rms_px reprojection error and the registry_revision it was scored against, so a calibration that quietly degraded or a planogram reset can never be confused for a merchandising failure after the fact. The slot_id assignment is the load-bearing output of this page, and the entire architecture below exists to make that assignment correct under perspective, parallax, and shelf density.

Implementation Architecture Jump to heading#

The naive implementation — assign each detection to the nearest slot centroid in pixel space — fails the moment a camera is mounted at any angle other than dead-center, because pixel distance is not metric distance under perspective and a box near the frame edge is compressed relative to one at the center. A correct stage decomposes into three steps: project both the detections and the slot grid into a shared metric frame, build a cost matrix that fuses spatial proximity with SKU agreement, then solve a global assignment rather than a greedy nearest-neighbor pass.

Projecting to a metric shelf grid Jump to heading#

The first step removes the camera. A homography projects pixel coordinates onto a fixture-relative metric grid using four or more coplanar reference points — shelf-edge fiducials, fixture dividers, or printed calibration targets. RANSAC outlier rejection keeps a single mislabeled correspondence from skewing the whole transform, and the resulting reprojection RMS is recorded so the stage can self-report calibration drift rather than silently producing garbage:

import cv2
import numpy as np


def fit_shelf_homography(
    image_pts: np.ndarray,        # (N, 2) pixel coords of reference markers
    fixture_pts_mm: np.ndarray,   # (N, 2) same markers in fixture mm coords
    ransac_thresh_px: float = 3.0,
) -> tuple[np.ndarray, float]:
    """Fit a pixel->fixture-mm homography and return it with its RMS error.

    Raises if the fixture has too few visible markers or the fit is degenerate,
    so a bad calibration fails loud at ingestion rather than corrupting scores.
    """
    if len(image_pts) < 4 or len(image_pts) != len(fixture_pts_mm):
        raise ValueError("need >= 4 matched reference points to fit homography")

    H, mask = cv2.findHomography(
        image_pts, fixture_pts_mm, method=cv2.RANSAC,
        ransacReprojThreshold=ransac_thresh_px,
    )
    if H is None or mask.sum() < 4:
        raise ValueError("homography fit degenerate; check marker correspondences")

    projected = cv2.perspectiveTransform(image_pts.reshape(-1, 1, 2), H).reshape(-1, 2)
    rms = float(np.sqrt(np.mean(np.sum((projected - fixture_pts_mm) ** 2, axis=1))))
    return H, rms


def project_centroids(boxes_px: np.ndarray, H: np.ndarray) -> np.ndarray:
    """Project pixel-space box centroids into fixture mm coordinates."""
    cx = (boxes_px[:, 0] + boxes_px[:, 2]) / 2.0
    cy = (boxes_px[:, 1] + boxes_px[:, 3]) / 2.0
    pts = np.stack([cx, cy], axis=1).reshape(-1, 1, 2)
    return cv2.perspectiveTransform(pts, H).reshape(-1, 2)

Global assignment, not greedy nearest-neighbor Jump to heading#

With detections and slots in the same millimeter frame, assignment becomes a balanced linear-assignment problem. The cost of pairing a detection with a slot fuses three signals: metric centroid distance, IoU against the slot rectangle, and whether the detected SKU matches the slot’s expected SKU. SciPy’s linear_sum_assignment solves it globally in one pass, which avoids the cascading mistakes a greedy loop makes when two detections compete for the same slot. Pairs whose cost exceeds a gate are rejected so a detection that belongs to no slot is left unassigned rather than forced into the least-bad one:

from dataclasses import dataclass
import numpy as np
from scipy.optimize import linear_sum_assignment

GATE = 1e6  # prohibitive cost: forbids an assignment past the distance ceiling


@dataclass(frozen=True)
class SlotAssignment:
    slot_id: str
    detection_idx: int | None
    centroid_offset_mm: float
    slot_iou: float
    position_state: str


def build_cost_matrix(
    det_centroids_mm: np.ndarray,   # (D, 2)
    det_skus: list[str],
    slot_centroids_mm: np.ndarray,  # (S, 2)
    slot_skus: list[str],
    slot_ious: np.ndarray,          # (D, S) precomputed IoU per pair
    max_offset_mm: float = 35.0,
    sku_mismatch_penalty_mm: float = 25.0,
) -> np.ndarray:
    """Cost = metric distance + SKU-mismatch penalty, gated past max_offset_mm."""
    dist = np.linalg.norm(
        det_centroids_mm[:, None, :] - slot_centroids_mm[None, :, :], axis=2
    )
    mismatch = np.array(
        [[0.0 if d == s else sku_mismatch_penalty_mm for s in slot_skus]
         for d in det_skus]
    )
    cost = dist + mismatch - slot_ious * 5.0  # reward overlap, in mm-equivalent units
    cost[dist > max_offset_mm] = GATE
    return cost


def assign_detections(
    cost: np.ndarray, slot_ids: list[str],
    offsets_mm: np.ndarray, slot_ious: np.ndarray,
    shift_mm: float = 12.0, iou_floor: float = 0.30,
) -> list[SlotAssignment]:
    rows, cols = linear_sum_assignment(cost)
    out: list[SlotAssignment] = []
    taken = set()
    for d, s in zip(rows, cols):
        if cost[d, s] >= GATE:
            continue  # gated pair: leave slot vacant, detection unassigned
        offset, iou = float(offsets_mm[d, s]), float(slot_ious[d, s])
        if iou < iou_floor:
            state = "misplaced"
        elif offset > shift_mm:
            state = "shifted"
        else:
            state = "in_position"
        out.append(SlotAssignment(slot_ids[s], int(d), offset, iou, state))
        taken.add(s)
    for s_idx, sid in enumerate(slot_ids):
        if s_idx not in taken:
            out.append(SlotAssignment(sid, None, float("inf"), 0.0, "vacant"))
    return out

The library choices are deliberate. OpenCV owns the projective geometry because its findHomography exposes RANSAC and a clean reprojection path; SciPy’s Hungarian solver is chosen over a hand-rolled greedy matcher specifically because retail shelves routinely present two near-identical facings competing for adjacent slots, and only a global optimum resolves that without thrashing. The metric frame is what lets the same max_offset_mm and shift_mm thresholds apply to a wide-angle ceiling camera and a chest-height fixed mount without per-camera retuning — the thresholds owned by Threshold Tuning for Compliance Accuracy are expressed in millimeters precisely so they survive the projection.

Production Configuration & Tuning Jump to heading#

The spatial thresholds, not the detector weights, are what make this stage agree with a human auditor, and they belong in versioned configuration so they can be reconciled against ground-truth audits without a deploy. A typical configuration scopes the gates by shelf tier and fixture class, because eye-level slots warrant a tighter band than a churned-up bottom shelf:

position_validation:
  homography:
    ransac_thresh_px: 3.0
    max_rms_px: 4.0            # above this, flag calibration drift, do not score
    min_reference_markers: 4
  assignment:
    max_offset_mm: 35.0        # distance ceiling: past this, leave unassigned
    sku_mismatch_penalty_mm: 25.0
    iou_floor: 0.30            # below this overlap, a matched SKU is still misplaced
    shift_mm: 12.0             # in-position vs shifted boundary
  tier_overrides:
    eye_level: { shift_mm: 8.0 }    # hero zone; tight
    bottom:    { shift_mm: 20.0 }   # bulk/restock churn; loose
  fixture_overrides:
    curved_endcap: { max_offset_mm: 50.0 }  # piecewise projection, wider band

The max_offset_mm ceiling of 35.0 is the single most consequential setting: too tight and a legitimately shifted facing gets gated into unassigned and shows as a false vacancy; too loose and a misplaced foreign SKU gets dragged into the wrong slot and scored as present. The max_rms_px guard of 4.0 is what separates this stage from naive implementations — when reprojection error climbs past it the fixture is flagged for recalibration and its frames are not scored, because a drifted homography produces confident, wrong assignments that are far more damaging than a skipped capture. Eye-level slots tighten shift_mm to 8.0 because that is where merchandising compliance has the most revenue leverage, while bottom shelves loosen to 20.0 to absorb restock churn without generating noise. Promotional fixtures never use these bands at all: endcaps and secondary displays have non-standard geometry and route through Promotional Display Alignment Checks, which loads its own override schema per campaign.

Failure Modes & Debugging Workflow Jump to heading#

When the assignments look wrong, the root cause is almost always one of five recurring problems. Work them in this order:

1. Homography drift from a bumped camera. Symptom: an entire fixture’s detections shift uniformly in one direction, so many slots read shifted or vacant at once and homography_rms_px creeps up over days. Reproduce by nudging a calibrated mount a few degrees and rescoring the same shelf. Fix: enforce the max_rms_px guard so the fixture self-flags for recalibration instead of scoring, and re-establish reference markers — never compensate by loosening max_offset_mm, which only masks the drift.
2. Parallax at the fixture periphery. Symptom: assignments are clean in the center of the frame but systematically off toward the edges, worst on tall fixtures shot from a low mount. Reproduce on any single-homography fit of a deep or tall bay. Fix: switch to piecewise homography per shelf tier, or where stereo/LiDAR capture exists, apply depth-aware correction so the planar assumption stops breaking at the periphery.
3. Dense-shelf assignment ambiguity. Symptom: two adjacent identical facings swap slots intermittently between captures, so one slot over-faces while its neighbor under-faces by the same amount. Reproduce on tightly packed rows of the same SKU. Fix: confirm you are running the global linear_sum_assignment solve rather than a greedy nearest-neighbor pass — greedy matching is the usual culprit — and lower iou_floor cautiously so overlap, not just centroid distance, breaks the tie.
4. Missing or occluded fiducials. Symptom: fit_shelf_homography raises or the RMS spikes on stores where a shopper, a stocking cart, or a price-tag rail covers a calibration marker. Reproduce by masking one marker before the fit. Fix: place redundant markers so any four remain visible, and fall back to the previous capture’s cached homography when fewer than min_reference_markers are detected rather than scoring against a degenerate fit.
5. Stale catalog inflating phantom misplacements. Symptom: a slot’s expected_sku no longer matches the product that physically belongs there, so position_state reads misplaced across many stores simultaneously. This is identifier drift, not a spatial fault — resolve it at the SKU resolution layer per Planogram Sync & SKU Mapping Strategies, and confirm the record’s registry_revision matches the planogram that was effective at capture_timestamp. Borderline visual look-alikes that get the wrong detected_sku should be routed back through the consensus and fallback logic in Error Handling in Computer Vision Pipelines rather than retuning spatial gates.

Keep a labeled error repository bucketed by these five causes; a quarterly review of which bucket dominates tells you whether to recalibrate cameras, switch to piecewise projection, or fix the catalog, and it is the only durable way to stop the same misassignment from recurring across resets. The per-fixture diagnostic that turns these symptoms into numeric tolerances lives in Validating Shelf Position Tolerances in Retail.

Scaling & Performance Benchmarks Jump to heading#

Position validation is dominated by the assignment solve, which is O(n^3) in the number of slots per fixture but trivially small at fixture scope — a bay of 40 slots solves in well under 5 ms, and the homography fit and projection add a few milliseconds more, so a full fixture clears in under 15 ms on a single CPU core. The scaling constraint is fan-out across a chain, not per-record compute, so the stage should never be the bottleneck if it is fed in capture-event batches rather than per-detection. For very dense fixtures, precompute a scipy.spatial.cKDTree over slot centroids and restrict the cost matrix to each detection’s k nearest slots, which collapses the matrix from D x S to D x k and keeps the Hungarian solve cheap even on wide gondola runs.

Partition the validation queue by store_id — or fixture_id for flagship locations — to preserve per-fixture ordering, because a fixture’s homography state and consecutive-capture diffing both assume frames arrive in order. Design against a soft latency SLA of one minute from capture to a category manager’s dashboard during a morning reset window, and watch consumer lag on the validation partition rather than CPU; a backlog here almost always signals a burst of captures from a chain-wide reset, and adding workers clears it linearly because each fixture is independent. Cost discipline mirrors the rest of the platform: run the projection and assignment on the store-level server that already hosts inference — the same edge tier the Vision Model Routing for Shelf Detection stage runs on — and sync only the typed slot-mapped record upstream, never raw frames or homography matrices. At chain scale that keeps the validation tier a rounding error on the analytics bill while still emitting a per-slot, per-capture audit trail across thousands of locations.

Frequently Asked Questions Jump to heading#

Related Jump to heading#

• Validating Shelf Position Tolerances in Retail — the per-fixture how-to that turns the spatial states here into measured tolerance bands
• Automating Facings vs Actuals Validation — the downstream stage that consumes these slot-mapped detections
• Threshold Tuning for Compliance Accuracy — how the metric offset and IoU thresholds are reconciled against ground-truth audits
• Promotional Display Alignment Checks — position logic for endcaps and secondary displays outside standard bay geometry
• Bounding Box Extraction & SKU Localization — the upstream detector that produces the SKU-resolved boxes this stage consumes
• Planogram Sync & SKU Mapping Strategies — the parent layer that binds detections to authoritative catalog identifiers