File size: 3,567 Bytes
beb4f15
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
"""Vectorized disk rasterization that reproduces ``cv2.circle`` exactly.

Several pipeline stages need "the pixels covered by filled circles drawn along a
polyline". Drawing each circle into a full-size mask makes those stages cost
O(objects x image area). The helpers here return pixel indices instead, so the
cost is proportional to the covered area only.
"""

from __future__ import annotations

from functools import lru_cache

import cv2
import numpy as np

# Upper bound on (points x stencil pixels) materialized at once by stamp_disks.
_STAMP_CHUNK = 1 << 22


@lru_cache(maxsize=None)
def disk_mask(radius: int) -> np.ndarray:
    """Boolean (2r+1, 2r+1) mask of the pixels ``cv2.circle(..., thickness=-1)`` fills."""
    radius = int(radius)
    canvas = np.zeros((2 * radius + 1, 2 * radius + 1), dtype=np.uint8)
    cv2.circle(canvas, (radius, radius), radius, 1, thickness=-1)
    mask = canvas.astype(bool)
    mask.flags.writeable = False
    return mask


@lru_cache(maxsize=None)
def disk_offsets(radius: int) -> tuple[np.ndarray, np.ndarray]:
    """(dy, dx) offsets of the pixels in ``disk_mask(radius)`` relative to its center."""
    dy, dx = np.nonzero(disk_mask(radius))
    dy = dy - int(radius)
    dx = dx - int(radius)
    dy.flags.writeable = False
    dx.flags.writeable = False
    return dy, dx


def disk_radii(radii: np.ndarray, expansion: float) -> np.ndarray:
    """Integer disk radii ``max(1, round(radius * expansion))`` (round half to even, like ``round``)."""
    scaled = np.asarray(radii, dtype=np.float64) * float(expansion)
    return np.maximum(1, np.rint(scaled).astype(np.int64))


def stamp_disks(
    points_xy: np.ndarray,
    radii_px: np.ndarray,
    owners: np.ndarray,
    shape: tuple[int, int],
) -> tuple[np.ndarray, np.ndarray]:
    """Pixels covered by filled disks, as unique ``(pixel, owner)`` pairs.

    Each point ``i`` contributes a disk of integer radius ``radii_px[i]`` centered at
    ``round(points_xy[i])`` and attributed to ``owners[i]`` (a non-negative id). Centers outside the image
    are skipped and disks are clipped at the image border, matching a loop of
    ``cv2.circle`` calls on an image of ``shape``.

    Returns flat pixel indices (``y * width + x``) and owner ids, sorted by owner then pixel.
    """
    h, w = int(shape[0]), int(shape[1])
    pts = np.asarray(points_xy, dtype=np.float64).reshape(-1, 2)
    cx = np.rint(pts[:, 0]).astype(np.int64)
    cy = np.rint(pts[:, 1]).astype(np.int64)
    radii_px = np.asarray(radii_px, dtype=np.int64).reshape(-1)
    owners = np.asarray(owners, dtype=np.int64).reshape(-1)

    inside = (cx >= 0) & (cy >= 0) & (cx < w) & (cy < h)
    cx, cy, radii_px, owners = cx[inside], cy[inside], radii_px[inside], owners[inside]

    keys: list[np.ndarray] = []
    for radius in np.unique(radii_px):
        sel = np.flatnonzero(radii_px == radius)
        dy, dx = disk_offsets(int(radius))
        step = max(1, _STAMP_CHUNK // dy.size)
        for start in range(0, sel.size, step):
            idx = sel[start:start + step]
            ys = cy[idx, None] + dy[None, :]
            xs = cx[idx, None] + dx[None, :]
            valid = (ys >= 0) & (ys < h) & (xs >= 0) & (xs < w)
            pixel = ys[valid] * w + xs[valid]
            owner = np.broadcast_to(owners[idx, None], valid.shape)[valid]
            keys.append(np.unique(owner * (h * w) + pixel))

    if not keys:
        empty = np.zeros(0, dtype=np.int64)
        return empty, empty.copy()
    key = np.unique(np.concatenate(keys))
    return key % (h * w), key // (h * w)