""" segmentation.py ---------------- Multi-signal sprite sheet segmentation. Why not just connected components ---------------------------------- A single sprite (e.g. a plant) can be made of several pixel groups that are NOT 4/8-connected to each other -- there might be a 1-2 pixel gap between a leaf and a stem due to anti-aliasing removal or the original artist's pixel placement. Naive connected-component labelling would split that single sprite into multiple "sprites". Conversely, two genuinely different sprites can sit close together on a sheet (dense tilesets, cramped sheets) with only a couple of pixels of gap between them -- naive dilation-based merging would fuse them into one. This module resolves that tension with a two-stage pipeline: 1. `find_components()` -- raw 8-connected components on the foreground mask. This is the ONLY step that looks at raw connectivity. 2. `merge_related_components()` -- decides, pairwise, whether two raw components are parts of the same logical sprite. This is where all of the extra signals from the spec are combined: - component distance (gap gets bigger relative to component size) - horizontal gap / vertical gap independently - bounding boxes / overlap - component size (small components merge more readily -- they're more likely to be a stray anti-aliasing remnant or dithering pixel of a bigger sprite) - alignment (components whose centers line up on the same row/column band are more likely part of one sprite, e.g. a plant stem + leaf, vs. two independent sprites placed on a shared baseline of a *sheet*, which is handled by keeping the merge radius small relative to sprite size) - local density (in a densely packed region of the sheet, the merge radius shrinks so we don't fuse neighbouring sprites) 3. `detect_sprite_boundaries()` -- turns each merged group into a BBox plus its exact pixel mask. 4. `calculate_segmentation_confidence()` -- heuristic score per sprite, flagging the sprite for mandatory manual review when low. This is intentionally NOT a single "smart" algorithm -- it is a small pipeline of clearly separated, independently testable functions, so a better algorithm can be swapped in later per component (see spec: "Tek bir algoritmaya bağımlı olma"). Grid modes ---------- The gap-based pipeline above assumes sprites are separated by at least a sliver of background, and that a sprite's own parts are never separated by more than a few pixels. Real sheets break that assumption in two opposite directions, and each has its own detector. **Over-merge -- no gaps at all.** Portrait/expression sheets (the standard Stardew Valley format: a fixed grid of 64x64 cells with ZERO gap between them) and tilesets drawn edge to edge have no background between cells, so the gap pipeline sees one giant connected blob instead of one sprite per cell. Three detectors cover this: - `detect_tile_grid()` reads the cell pitch straight off the sheet's own edge periodicity -- the average colour discontinuity along a candidate pitch's cut lines versus the sheet's average. This is the only signal available when there is no background anywhere. Note that every MULTIPLE of the true pitch also lines up with real tile boundaries, so it deliberately takes the smallest pitch scoring near the best, or a 16px tileset reads as 32 or 80. - `detect_grid_layout()` scores cell sizes the sheet divides evenly by against content occupancy and uniformity. - `segment_grid()` then cuts along those lines regardless of pixel connectivity. **Shattering -- too many gaps.** Animation and effect sheets have frames made of flying debris or scattered sparkles: parts of ONE frame sit far apart, and individual particles are small enough that `find_components()` discards them as speckle, so whole frames go missing. `detect_separator_grid()` finds the frame pitch by searching for a period AND phase whose every cut line is a fully background row or column -- a cut that cannot, by construction, slice through any pixel blob. `regroup_by_grid()` then collapses the gap result into those cells. That step is merge-only: a sprite the gap stage already joined across a background gap unions its cells rather than being split, so the disconnected-leaf-and-stem case survives untouched. `segment_sheet(mode="auto")` runs the gap pipeline, diagnoses which (if either) failure signature is present, and applies the matching correction; with no signature, the gap result is returned untouched. `mode="grid"` forces a grid cut; `mode="gap"` forces the original pipeline and skips every correction. """ from __future__ import annotations from dataclasses import dataclass, field import numpy as np from scipy import ndimage from config import ( COMPONENT_MERGE_GAP_BASE, COMPONENT_MERGE_GAP_MAX, MAX_SPRITE_AREA_FRACTION, MIN_SPRITE_SIZE_PX, ) from image_utils import BBox @dataclass class RawComponent: """A single 8-connected pixel blob before any merging.""" label_id: int bbox: BBox pixel_count: int mask_slice: tuple[slice, slice] # slice into the full-sheet label array @dataclass class SpriteGroup: """One or more RawComponents merged into a single logical sprite.""" components: list[RawComponent] bbox: BBox = field(init=False) pixel_count: int = field(init=False) def __post_init__(self): box = self.components[0].bbox total_px = 0 for c in self.components[1:]: box = box.union(c.bbox) for c in self.components: total_px += c.pixel_count self.bbox = box self.pixel_count = total_px @dataclass class DetectedSprite: sprite_index: int bbox: BBox confidence: float confidence_reasons: list[str] component_count: int pixel_count: int # Which path produced this sprite: "gap", "tile", "separator" or # "divisor". Downstream consumers use it as a provenance fact rather # than a guess -- a sprite cut from a detected tile grid IS a tileset # tile, and one cut from a separator grid IS an animation frame. source: str = "gap" # --------------------------------------------------------------------------- # Stage 1: raw connected components # --------------------------------------------------------------------------- def find_foreground_regions(foreground_mask: np.ndarray) -> np.ndarray: """ Light morphological cleanup: remove single-pixel salt noise that would otherwise create thousands of spurious 1px "components" on scraped / lightly-compressed sheets. Does NOT touch the sprites that will actually be exported (this mask is used only to decide component membership). """ # Fill tiny 1-pixel holes inside otherwise-solid foreground (common with # lossy-compressed sheets that have single stray background-colored # pixels inside a sprite body). filled = ndimage.binary_closing(foreground_mask, structure=np.ones((2, 2)), iterations=1) return filled | foreground_mask # never remove pixels, only ever add back def find_components(foreground_mask: np.ndarray) -> tuple[np.ndarray, list[RawComponent], list[RawComponent]]: """ 8-connected component labelling on the foreground mask. Returns the integer label array, a RawComponent per usable label, and a THIRD list holding the sub-MIN_SPRITE_SIZE_PX blobs that were rejected as noise. The gap-based pipeline ignores that third list exactly as before -- a lone 1px speck really is speckle and must not become a sprite. It is returned rather than discarded because a scattered 1-2px particle is indistinguishable from speckle *locally*, and only becomes meaningful once a grid tells us it belongs inside a specific animation frame (see `regroup_by_grid`). Sheets whose frames are made of loose particles used to lose those frames entirely here. """ structure = np.ones((3, 3), dtype=int) # 8-connectivity labels, num = ndimage.label(foreground_mask, structure=structure) components: list[RawComponent] = [] noise: list[RawComponent] = [] objects = ndimage.find_objects(labels) for label_id, slc in enumerate(objects, start=1): if slc is None: continue ys, xs = slc sub_mask = labels[slc] == label_id pixel_count = int(sub_mask.sum()) if pixel_count == 0: continue bbox = BBox(x=xs.start, y=ys.start, width=xs.stop - xs.start, height=ys.stop - ys.start) comp = RawComponent(label_id=label_id, bbox=bbox, pixel_count=pixel_count, mask_slice=slc) if max(bbox.width, bbox.height) < MIN_SPRITE_SIZE_PX and pixel_count < MIN_SPRITE_SIZE_PX: noise.append(comp) continue components.append(comp) return labels, components, noise # --------------------------------------------------------------------------- # Stage 2: decide which raw components belong to the same sprite # --------------------------------------------------------------------------- # Largest factor `_should_merge` can ever apply on top of the adaptive gap # threshold (the axis-alignment bonus for small fragments). Kept as a named # constant because `merge_related_components` relies on it to compute a # provably-safe pre-filter bound: no pair whose bounding-box gap exceeds # COMPONENT_MERGE_GAP_MAX * this can possibly merge. ALIGNMENT_BONUS_MULTIPLIER = 1.4 def _adaptive_gap_threshold(a: RawComponent, b: RawComponent) -> float: """ The allowed gap between two components scales with how *small* they are. Two tiny (e.g. 2x2) fragments a few pixels apart are very likely stray parts of the same small sprite (like the disconnected leaf/stem example in the spec). Two large, well-formed components a similar absolute distance apart are much more likely to be separate sprites -- so the allowed gap shrinks as component size grows. """ size_a = max(a.bbox.width, a.bbox.height) size_b = max(b.bbox.width, b.bbox.height) smaller = min(size_a, size_b) # Small components (<=6px) get a generous relative allowance -- they're # the disconnected-fragment case (a stray leaf/stem pixel group a couple # of pixels away from the rest of its own sprite). As components grow # past that, a real sprite's own internal gaps are rarely more than 1-2 # px, so the threshold drops toward the base gap quickly to avoid # bridging two separately-placed sprites on the sheet. if smaller <= 6: factor = COMPONENT_MERGE_GAP_MAX elif smaller <= 12: factor = COMPONENT_MERGE_GAP_BASE + 1 else: factor = COMPONENT_MERGE_GAP_BASE return max(1.0, min(COMPONENT_MERGE_GAP_MAX, factor)) def _should_merge(a: RawComponent, b: RawComponent, local_density: float) -> bool: """ Combine every signal from the spec into one merge decision: - horizontal gap / vertical gap (independently, via BBox.gap_to) - component distance overall - component size (adaptive threshold, see above) - bounding box overlap short-circuits to True - local density shrinks the allowed gap in crowded sheet regions - alignment: components that overlap substantially on one axis are more likely a single sprite's disconnected parts (e.g. stem below leaf) than two side-by-side sprites """ dx, dy = a.bbox.gap_to(b.bbox) # Overlapping or touching bounding boxes -> always the same sprite. if dx <= 0 and dy <= 0: return True threshold = _adaptive_gap_threshold(a, b) # Crowded regions of the sheet (many small sprites close together) # shrink the merge radius so neighbours don't get fused. threshold *= max(0.4, 1.0 - 0.5 * local_density) # Axis alignment bonus: only meaningful for small fragments (the # disconnected-part case). For components already large enough to be # plausible standalone sprites on their own, two boxes sharing a row/ # column band is completely normal for a *grid* of separate sprites, so # alignment must NOT be used to justify a bigger merge radius there. smaller_size = min(max(a.bbox.width, a.bbox.height), max(b.bbox.width, b.bbox.height)) if smaller_size <= 8: x_overlap = min(a.bbox.x2, b.bbox.x2) - max(a.bbox.x, b.bbox.x) y_overlap = min(a.bbox.y2, b.bbox.y2) - max(a.bbox.y, b.bbox.y) aligned = (x_overlap > 0.3 * min(a.bbox.width, b.bbox.width)) or \ (y_overlap > 0.3 * min(a.bbox.height, b.bbox.height)) if aligned: threshold *= ALIGNMENT_BONUS_MULTIPLIER # The effective distance is the max of the two independent gaps (a # diagonal gap of e.g. dx=1,dy=1 should not need a huge threshold). effective_gap = max(dx, dy) return effective_gap <= threshold def _local_density( index: int, all_components: list[RawComponent], radius: float, buckets: dict[tuple[int, int], list[int]], ) -> float: """ Fraction-like density signal: how many other component centers fall within `radius` pixels of this component's center, normalized to a 0..1-ish range. Used to shrink merge distance in crowded sheet areas. `buckets` must be a `_spatial_buckets` index built at this same radius; it only restricts which candidates are enumerated, so the counted set is exactly the same as a full scan would produce. """ component = all_components[index] cx, cy = component.bbox.cx, component.bbox.cy count = 0 for j in _bucket_neighbours(buckets, component, radius): if j == index: continue other = all_components[j] ox, oy = other.bbox.cx, other.bbox.cy if ((ox - cx) ** 2 + (oy - cy) ** 2) ** 0.5 <= radius: count += 1 return min(1.0, count / 6.0) def _spatial_buckets(components: list[RawComponent], cell_size: float) -> dict[tuple[int, int], list[int]]: """ Index component centers into a uniform grid of `cell_size` squares. Both pairwise passes below only ever care about components within some radius R of each other, and bucketing at cell_size=R means every such partner is in one of the 9 surrounding buckets. That turns two O(n^2) sweeps into roughly linear ones, WITHOUT changing which pairs are considered: the same distance test still decides every pair, only the hopeless ones are never enumerated. A 2048x2048 sheet holding ~16k components used to spend minutes here. """ buckets: dict[tuple[int, int], list[int]] = {} for i, c in enumerate(components): key = (int(c.bbox.cx // cell_size), int(c.bbox.cy // cell_size)) buckets.setdefault(key, []).append(i) return buckets def _bucket_neighbours( buckets: dict[tuple[int, int], list[int]], component: RawComponent, cell_size: float, ): """Indices of components in the 3x3 bucket block around `component`.""" kx = int(component.bbox.cx // cell_size) ky = int(component.bbox.cy // cell_size) for dx in (-1, 0, 1): for dy in (-1, 0, 1): yield from buckets.get((kx + dx, ky + dy), ()) def merge_related_components(components: list[RawComponent]) -> list[SpriteGroup]: """ Union-find over raw components using `_should_merge` as the edge test. Runs in O(n^2) which is fine up to a few thousand components (typical sprite sheets); for pathologically dense sheets this is still bounded by MAX_FILES_PER_ZIP / practical sheet sizes. """ n = len(components) if n == 0: return [] parent = list(range(n)) def find(i: int) -> int: while parent[i] != i: parent[i] = parent[parent[i]] i = parent[i] return i def union(i: int, j: int) -> None: ri, rj = find(i), find(j) if ri != rj: parent[ri] = rj # Precompute a density radius from the median component size so it # adapts to the sheet's own scale (16px sprites vs 128px sprites). sizes = sorted(max(c.bbox.width, c.bbox.height) for c in components) median_size = sizes[len(sizes) // 2] if sizes else 16 density_radius = max(24.0, median_size * 3.0) density_buckets = _spatial_buckets(components, density_radius) densities = [_local_density(i, components, density_radius, density_buckets) for i in range(n)] # Only compare components that are reasonably close (broad-phase via a # generous bounding radius) to keep this fast on large sheets. broad_radius = max(64.0, median_size * (COMPONENT_MERGE_GAP_MAX + 4)) merge_buckets = _spatial_buckets(components, broad_radius) # Vectorised narrow phase. `_should_merge` can only ever return True # when the two bounding boxes overlap or their gap is within # COMPONENT_MERGE_GAP_MAX * ALIGNMENT_BONUS_MULTIPLIER (every other # factor in it only ever shrinks the threshold), so gap-testing whole # candidate arrays at once and calling the real decision function only # for survivors is exact -- it changes nothing about which pairs merge, # it just stops evaluating the hopeless majority one at a time. max_gap = COMPONENT_MERGE_GAP_MAX * ALIGNMENT_BONUS_MULTIPLIER x1 = np.array([c.bbox.x for c in components], dtype=np.float64) y1 = np.array([c.bbox.y for c in components], dtype=np.float64) x2 = np.array([c.bbox.x2 for c in components], dtype=np.float64) y2 = np.array([c.bbox.y2 for c in components], dtype=np.float64) cxs = np.array([c.bbox.cx for c in components], dtype=np.float64) cys = np.array([c.bbox.cy for c in components], dtype=np.float64) for i in range(n): ci = components[i] cand = np.fromiter( (j for j in _bucket_neighbours(merge_buckets, ci, broad_radius) if j > i), dtype=np.int64, ) if cand.size == 0: continue dcx = cxs[i] - cxs[cand] dcy = cys[i] - cys[cand] near = (dcx * dcx + dcy * dcy) <= broad_radius * broad_radius gap_x = np.maximum(x1[cand] - x2[i], x1[i] - x2[cand]) gap_y = np.maximum(y1[cand] - y2[i], y1[i] - y2[cand]) keep = near & (np.maximum(gap_x, gap_y) <= max_gap) for j in cand[keep]: j = int(j) local_density = max(densities[i], densities[j]) if _should_merge(ci, components[j], local_density): union(i, j) groups: dict[int, list[RawComponent]] = {} for i, comp in enumerate(components): root = find(i) groups.setdefault(root, []).append(comp) return [SpriteGroup(components=comps) for comps in groups.values()] # --------------------------------------------------------------------------- # Stage 3: boundaries # --------------------------------------------------------------------------- def detect_sprite_boundaries(groups: list[SpriteGroup], sheet_shape: tuple[int, int]) -> list[SpriteGroup]: """ Clip each group's bounding box to the sheet bounds and drop groups that are implausibly large (almost certainly a background-detection failure rather than a real sprite -- e.g. background bled through as foreground). Those cases still show up to the user, just via the confidence step, not silently dropped here; this stage only clips. """ h, w = sheet_shape out = [] sheet_area = h * w for g in groups: b = g.bbox clipped = BBox( x=max(0, b.x), y=max(0, b.y), width=min(w, b.x2) - max(0, b.x), height=min(h, b.y2) - max(0, b.y), ) if clipped.width <= 0 or clipped.height <= 0: continue g.bbox = clipped # Sanity clamp -- extreme outliers are kept (never silently drop a # detection) but will receive a low confidence score below. out.append(g) _ = sheet_area # reserved for future area-ratio heuristics return out # --------------------------------------------------------------------------- # Stage 4: confidence scoring # --------------------------------------------------------------------------- def calculate_segmentation_confidence( group: SpriteGroup, sheet_shape: tuple[int, int], all_groups: list[SpriteGroup], ) -> tuple[float, list[str]]: """ Heuristic 0-100 confidence that a SpriteGroup is a single, cleanly segmented sprite. Lower confidence => surfaced to the user as "possible segmentation problem" and excluded from batch auto-accept. """ has_close_neighbour = any( max(*group.bbox.gap_to(g.bbox)) < NEIGHBOUR_GAP_THRESHOLD for g in all_groups if g is not group ) return _confidence_for( bbox=group.bbox, pixel_count=group.pixel_count, component_count=len(group.components), sheet_shape=sheet_shape, has_close_neighbour=has_close_neighbour, ) # A sprite whose nearest neighbour is closer than this is flagged as a # possible under/over-merge right at the boundary. NEIGHBOUR_GAP_THRESHOLD = 2 def _close_neighbour_flags(bboxes: list[BBox], threshold: int = NEIGHBOUR_GAP_THRESHOLD) -> list[bool]: """ Per bounding box: is any OTHER box closer than `threshold` pixels? Answering this by comparing every pair is O(n^2), which is invisible on a 20-sprite sheet and ruinous on a large tileset -- a 1024x1024 sheet cut into 4096 tiles spent ~45s here alone. Boxes are instead bucketed into a uniform grid; two boxes that close necessarily share a bucket once each is expanded by `threshold`, so the answer is identical, just without enumerating the hopeless pairs. """ n = len(bboxes) flags = [False] * n if n < 2: return flags sizes = sorted(max(b.width, b.height) for b in bboxes) cell = float(max(8, sizes[len(sizes) // 2])) buckets: dict[tuple[int, int], list[int]] = {} oversized: list[int] = [] for i, b in enumerate(bboxes): kx0, kx1 = int((b.x - threshold) // cell), int((b.x2 + threshold) // cell) ky0, ky1 = int((b.y - threshold) // cell), int((b.y2 + threshold) // cell) # A box far larger than the sheet's typical sprite would be # registered in a huge number of buckets; compare those few # against everything instead. if (kx1 - kx0 + 1) * (ky1 - ky0 + 1) > 256: oversized.append(i) continue for kx in range(kx0, kx1 + 1): for ky in range(ky0, ky1 + 1): buckets.setdefault((kx, ky), []).append(i) def mark(i: int, j: int) -> None: if flags[i] and flags[j]: return gap_x, gap_y = bboxes[i].gap_to(bboxes[j]) if max(gap_x, gap_y) < threshold: flags[i] = True flags[j] = True for members in buckets.values(): for a in range(len(members)): for b in range(a + 1, len(members)): mark(members[a], members[b]) for i in oversized: for j in range(n): if i != j: mark(i, j) return flags def _confidence_for( bbox: BBox, pixel_count: int, component_count: int, sheet_shape: tuple[int, int], has_close_neighbour: bool, grid_backed: bool = False, ) -> tuple[float, list[str]]: """ Shared confidence heuristic. `grid_backed=True` means the sprite's boundaries came from a validated grid (every cut line was verified to be pure background, or a tile pitch confirmed by the sheet's own edge periodicity) rather than from the gap heuristic. For those, "several disconnected pieces" and "sparse bounding box" are the EXPECTED shape of a correct result -- a single explosion frame is legitimately a cloud of loose particles -- so those two penalties are skipped. The structural penalties (extreme aspect ratio, covering most of the sheet) still apply, because those would indicate a bad grid rather than an unusual sprite. """ reasons: list[str] = [] score = 100.0 h, w = sheet_shape b = bbox # Signal: many disconnected raw components merged together is riskier # than a single clean component. if not grid_backed and component_count > 1: penalty = min(25, (component_count - 1) * 8) score -= penalty reasons.append("Multiple disconnected regions") # Signal: extreme aspect ratio (long thin fence/wall segments are # legitimate per the spec, but they ARE harder to segment correctly, # so flag rather than silently trust). aspect = b.width / max(1, b.height) if aspect > 6 or aspect < (1 / 6): score -= 12 reasons.append("Unusual bounding box (extreme aspect ratio)") # Signal: sprite occupies a very large fraction of the whole sheet -- # likely a background/segmentation failure rather than one sprite. area_fraction = b.area / max(1, h * w) if area_fraction > MAX_SPRITE_AREA_FRACTION: score -= 30 reasons.append("Bounding box covers most of the sheet") # Signal: pixel density inside the bbox (sparse boxes suggest a bad # merge that bridged two things with a lot of empty space between). density = pixel_count / max(1, b.area) if not grid_backed and density < 0.08: score -= 15 reasons.append("Very sparse bounding box (large empty gaps)") # Signal: very small gap to nearest neighbour sprite -> risk of an # under-merge or over-merge right at the boundary. Meaningless for a # grid-backed sprite: tiles in a tileset touch their neighbours by # definition, so this would fire on every single correct tile. if not grid_backed and has_close_neighbour: score -= 10 reasons.append("Very small gap between neighboring regions") score = max(0.0, min(100.0, score)) return score, reasons # --------------------------------------------------------------------------- # Grid segmentation (portrait/expression sheets with zero gap between cells) # --------------------------------------------------------------------------- @dataclass class GridLayout: cell_width: int cell_height: int columns: int rows: int offset_x: int # leading border/padding before the first column, if any offset_y: int # leading border/padding before the first row, if any score: float # 0-100 confidence this is really the sheet's grid # Which detector produced this layout: "divisor" (cell size the sheet # divides evenly by, scored on content), "separator" (every cut line # verified to be pure background) or "tile" (cell pitch confirmed by # the sheet's own edge periodicity). source: str = "divisor" # Cells that actually contain foreground. 0 when not computed. occupied_cells: int = 0 def _grid_candidate_divisors(length: int) -> list[tuple[int, int, int]]: """ For a sheet dimension `length`, return (cell_size, count, offset) triples for every candidate cell size in GRID_CANDIDATE_SIZES that divides it evenly into 2+ cells (within GRID_DIVISION_TOLERANCE_PX of a whole number of cells, allowing a small leading border/offset). NOTE: single-row/single-column grids (count==1 on one axis) are intentionally NOT included here. This detector only scores a cell size against content statistics, which cannot reliably tell "this cell correctly covers one sprite" from "this cell is too big and merges two stacked sprites into one" -- accepting single-axis candidates here regressed real multi-row sheets. Horizontal animation strips, which is what needed them, are handled by `detect_separator_grid()` instead: it verifies that every cut line is actually background rather than inferring it from occupancy, and its cell size does not have to divide the sheet evenly at all. """ from config import GRID_CANDIDATE_SIZES, GRID_DIVISION_TOLERANCE_PX out = [] for size in GRID_CANDIDATE_SIZES: if size > length: continue # Try zero offset first (most common), then small offsets to # tolerate a thin border/padding strip before the grid starts. for offset in range(0, GRID_DIVISION_TOLERANCE_PX + 1): usable = length - offset count = usable // size remainder = usable % size if count >= 2 and remainder <= GRID_DIVISION_TOLERANCE_PX: out.append((size, count, offset)) break # smallest working offset for this size is enough return out def detect_grid_layout(foreground_mask: np.ndarray) -> GridLayout | None: """ Look for a regular cell grid the sheet's width and height both divide evenly by, then score each candidate by how well actual foreground content aligns with it: a real grid should have most cells containing a meaningful amount of foreground (not mostly-empty cells), and foreground density shouldn't spike right at the cell boundaries in a way that suggests the boundary is cutting through the middle of a sprite rather than between sprites. Returns the best-scoring GridLayout, or None if nothing plausible was found (e.g. a sheet with an irregular sprite count/spacing that genuinely isn't a grid). """ h, w = foreground_mask.shape width_candidates = _grid_candidate_divisors(w) height_candidates = _grid_candidate_divisors(h) if not width_candidates or not height_candidates: return None best: GridLayout | None = None for cell_w, cols, off_x in width_candidates: for cell_h, rows, off_y in height_candidates: if cols * rows < 2: continue # a single "grid cell" isn't a grid score = _score_grid_candidate(foreground_mask, cell_w, cell_h, cols, rows, off_x, off_y) if best is None or score > best.score: best = GridLayout( cell_width=cell_w, cell_height=cell_h, columns=cols, rows=rows, offset_x=off_x, offset_y=off_y, score=score, ) return best def _score_grid_candidate( foreground_mask: np.ndarray, cell_w: int, cell_h: int, cols: int, rows: int, off_x: int, off_y: int, ) -> float: """ 0-100 plausibility score for one grid candidate. Combines: - occupancy: fraction of cells that actually contain a meaningful amount of foreground (an empty-looking grid is probably the wrong cell size, e.g. treating one sprite's sub-region as if it were a whole grid) - uniformity: how similar each occupied cell's foreground pixel count is to the others (real per-cell sprites tend to be similarly sized; wildly uneven cell content suggests the grid lines are cutting sprites in half rather than falling between them) - a size prior: prefers fewer, larger cells over many tiny ones when both fit equally well, since spurious small-cell-size matches are common (e.g. 8px dividing evenly almost always) but rarely the sheet's *actual* sprite grid """ h, w = foreground_mask.shape cell_pixel_counts = [] for r in range(rows): for c in range(cols): y0 = off_y + r * cell_h x0 = off_x + c * cell_w cell = foreground_mask[y0:y0 + cell_h, x0:x0 + cell_w] cell_pixel_counts.append(int(cell.sum())) total_cells = len(cell_pixel_counts) if total_cells == 0: return 0.0 cell_area = cell_w * cell_h occupied = [c for c in cell_pixel_counts if c > 0.02 * cell_area] occupancy_fraction = len(occupied) / total_cells if len(occupied) < 2: return 0.0 # can't judge uniformity with 0-1 real cells; not a usable grid mean_occ = sum(occupied) / len(occupied) if mean_occ == 0: return 0.0 variance = sum((v - mean_occ) ** 2 for v in occupied) / len(occupied) coefficient_of_variation = (variance ** 0.5) / mean_occ uniformity = max(0.0, 1.0 - min(1.0, coefficient_of_variation)) size_prior = min(1.0, cell_area / 1024.0) # favors cells >= ~32x32 fully, tapers below that score = 100.0 * (0.5 * occupancy_fraction + 0.35 * uniformity + 0.15 * size_prior) return score def _occupied_grid_cells( foreground_mask: np.ndarray, layout: GridLayout, ) -> dict[tuple[int, int], dict]: """ Per grid cell that holds any foreground: its pixel bounds, its tight content bbox and its pixel count. Keyed by (row, column). """ h, w = foreground_mask.shape row_range, col_range = _content_cell_ranges(foreground_mask, layout) cells: dict[tuple[int, int], dict] = {} for r in row_range: y0, y1 = _cell_bounds(layout.offset_y, layout.cell_height, r, h) if y1 <= y0: continue band = foreground_mask[y0:y1] if not band.any(): continue for c in col_range: x0, x1 = _cell_bounds(layout.offset_x, layout.cell_width, c, w) if x1 <= x0: continue cell = band[:, x0:x1] if not cell.any(): continue ys, xs = np.nonzero(cell) cells[(r, c)] = { "bounds": (x0, y0, x1, y1), "bbox": BBox( x=x0 + int(xs.min()), y=y0 + int(ys.min()), width=int(xs.max()) - int(xs.min()) + 1, height=int(ys.max()) - int(ys.min()) + 1, ), "pixels": int(cell.sum()), } return cells def _composite_cell_groups( foreground_mask: np.ndarray, layout: GridLayout, cells: dict[tuple[int, int], dict], ) -> list[list[tuple[int, int]]]: """ Group grid cells that are all part of ONE connected piece of artwork into a single composite object. A ladder, door or pillar drawn across two or three cells is one object; cutting it into per-cell fragments produces training samples that mean nothing on their own. What identifies such an object is that it is a self-contained island of artwork -- background all around it -- that happens to be wider or taller than one cell. Merging is deliberately keyed on connected-component identity rather than on "do these two neighbouring cells touch at the border". The border test looks equivalent but is not: two adjacent flat filler tiles touch along their whole shared edge and would be fused into a nonsense sprite, while genuinely interchangeable terrain tiles all touch each other as well. Component identity alone is still not enough, because a dungeon's floor and walls are also one enormous connected region. The two are told apart by extent: a composite object covers a handful of cells, terrain covers dozens. Components over GRID_COMPOSITE_MAX_CELLS, or too scattered to fill their own cell bounding box, stay per-cell. Note this is inherently a no-op for separator grids: their cut lines are pure background by construction, so no component can ever span one. """ from config import GRID_COMPOSITE_MAX_CELLS, GRID_COMPOSITE_MIN_FILL labels, count = ndimage.label(foreground_mask, structure=np.ones((3, 3), dtype=int)) if count == 0: return [[key] for key in cells] # Each cell is attributed to whichever component owns most of its # pixels, so a stray speck from a neighbouring object cannot drag a # cell into the wrong group. by_component: dict[int, list[tuple[int, int]]] = {} for key, info in cells.items(): x0, y0, x1, y1 = info["bounds"] patch = labels[y0:y1, x0:x1] patch = patch[patch > 0] if patch.size == 0: by_component.setdefault(-hash(key), []).append(key) continue values, counts = np.unique(patch, return_counts=True) dominant = int(values[int(np.argmax(counts))]) by_component.setdefault(dominant, []).append(key) out: list[list[tuple[int, int]]] = [] for members in by_component.values(): if len(members) == 1: out.append(members) continue rows = [r for r, _ in members] cols = [c for _, c in members] span = (max(rows) - min(rows) + 1) * (max(cols) - min(cols) + 1) fill = len(members) / max(1, span) if len(members) <= GRID_COMPOSITE_MAX_CELLS and fill >= GRID_COMPOSITE_MIN_FILL: out.append(members) else: out.extend([[m] for m in members]) return out def segment_grid( foreground_mask: np.ndarray, layout: GridLayout, merge_composites: bool = True, ) -> list[DetectedSprite]: """ Cut the sheet strictly along the given grid lines, tightly cropped to each cell's actual foreground content (so a character portrait's bbox doesn't include the cell's empty margin). Cells with no foreground at all are skipped (e.g. a grid sized for the fullest row, where a later row has fewer expressions than others). With `merge_composites` (the default), neighbouring cells whose artwork runs across the shared border are rejoined into one sprite -- see `_composite_cell_groups`. """ h, w = foreground_mask.shape cells = _occupied_grid_cells(foreground_mask, layout) if not cells: return [] groups = ( _composite_cell_groups(foreground_mask, layout, cells) if merge_composites else [[key] for key in cells] ) entries = [] for members in groups: box = None pixels = 0 for key in members: info = cells[key] box = info["bbox"] if box is None else box.union(info["bbox"]) pixels += info["pixels"] entries.append((box, pixels, len(members))) entries.sort(key=lambda e: (round(e[0].y / 8), e[0].x)) base_reason = f"Grid cell ({layout.cell_width}x{layout.cell_height}, {layout.source})" detected: list[DetectedSprite] = [] for idx, (box, pixels, cell_count) in enumerate(entries, start=1): reasons = [base_reason] if cell_count > 1: reasons.append(f"Composite object spanning {cell_count} grid cells") detected.append( DetectedSprite( sprite_index=idx, bbox=box, confidence=min(100.0, 80.0 + layout.score * 0.2), confidence_reasons=reasons, component_count=cell_count, pixel_count=pixels, source=layout.source, ) ) return detected # --------------------------------------------------------------------------- # Separator grid (animation strips / frame sheets with background gutters) # --------------------------------------------------------------------------- def _empty_run_widths(empty: np.ndarray) -> np.ndarray: """ For every index, the length of the run of empty lines it belongs to (0 for non-empty indices). Used to tell a real frame gutter from an incidental one-pixel gap that happens to fall inside a frame. """ widths = np.zeros(empty.shape, dtype=np.int32) n = len(empty) i = 0 while i < n: if not empty[i]: i += 1 continue j = i while j < n and empty[j]: j += 1 widths[i:j] = j - i i = j return widths def _axis_separator_period(empty: np.ndarray, min_cell: int) -> tuple[int, int, int] | None: """ Best (cell_size, first_cut_line, cut_line_count) along one axis such that EVERY cut line the grid would make falls on a fully-background row/column. That constraint is the whole point: a cut line made of pure background cannot possibly slice through a connected pixel blob, so this grid can never chop a sprite in half. Both the period AND its phase have to be searched. A 10x10 lattice of 8px sprites at an 11px pitch has its gutters at 8, 19, 30, ... -- the period is 11 but the phase is 8, and searching only phase 0 finds a much coarser (and badly wrong) period instead. Among the legal candidates, "smallest period" is NOT a safe choice on its own: a frame made of scattered particles usually contains some incidental empty line, and a short period threading those gaps is legal yet cuts frames in half. So candidates are scored by number of cells x min(width of the thinnest gutter used, cap) which rewards a fine partition, but only one whose every cut sits in a gutter wide enough to be a real frame separator rather than a lucky 1px gap inside one. The cap stops a huge trailing empty margin from buying a needlessly coarse grid. Returns None when the axis has no usable periodic gutter structure (e.g. an edge-to-edge tileset with no background columns at all, or a sheet holding a single sprite). """ from config import GRID_SEPARATOR_GUTTER_CAP_PX, GRID_SEPARATOR_MAX_CELL_PX content = np.nonzero(~empty)[0] if content.size == 0: return None first, last = int(content[0]), int(content[-1]) span = last - first + 1 max_cell = min(GRID_SEPARATOR_MAX_CELL_PX, max(min_cell, span // 2)) # Every content position except the very first one (cut lines are only # meaningful strictly inside the content span). interior = content[1:] if interior.size == 0: return None widths = _empty_run_widths(empty) cap = GRID_SEPARATOR_GUTTER_CAP_PX best_score = 0.0 best: tuple[int, int, int] | None = None for cell in range(min_cell, max_cell + 1): # No phase at this period can beat the incumbent any more, and the # bound only shrinks as cells get larger -- stop entirely. if (span // cell + 1) * cap <= best_score: break # A phase is disqualified by any single content pixel sitting on # it, so the whole phase sweep is one modulo pass -- far cheaper # than testing each phase's lines separately. blocked = np.zeros(cell, dtype=bool) blocked[np.unique(interior % cell)] = True for phase in np.nonzero(~blocked)[0]: start = int(phase) + ((first - int(phase)) // cell + 1) * cell if start <= first: start += cell if start > last: continue lines = np.arange(start, last + 1, cell) score = (lines.size + 1) * min(cap, int(widths[lines].min())) if score > best_score: best_score = score best = (cell, start, int(lines.size)) return best def _cell_bounds(origin: int, cell: int, index: int, length: int) -> tuple[int, int]: """ Pixel range of grid cell `index`, where cell i spans [origin + i*cell, origin + (i+1)*cell). `origin` may be negative (a separator grid's first cut line can sit partway into the sheet, making cell 0 a short leading cell). Cell 0 is additionally extended back to 0 and the last cell forward to `length`, so a thin border strip outside the grid proper is never dropped. """ start = 0 if index == 0 else max(0, origin + index * cell) end = min(length, origin + (index + 1) * cell) return start, max(start, end) def _content_cell_ranges( foreground_mask: np.ndarray, layout: GridLayout, ) -> tuple[range, range]: """ Row and column cell indices that can possibly hold content. A grid can nominally span the whole sheet in cells only a few pixels wide, which on a large sheet is millions of cells -- almost all of them provably empty. Walking only the cells intersecting the foreground's bounding box visits the same non-empty cells while keeping the loops proportional to the content, not the canvas. """ h, w = foreground_mask.shape rows_any = np.nonzero(foreground_mask.any(axis=1))[0] cols_any = np.nonzero(foreground_mask.any(axis=0))[0] if rows_any.size == 0 or cols_any.size == 0: return range(0), range(0) def span(origin: int, cell: int, lo: int, hi: int, count: int) -> range: first = max(0, (lo - origin) // cell) last = min(count - 1, (hi - origin) // cell) return range(int(first), int(last) + 1) return ( span(layout.offset_y, layout.cell_height, int(rows_any[0]), int(rows_any[-1]), layout.rows), span(layout.offset_x, layout.cell_width, int(cols_any[0]), int(cols_any[-1]), layout.columns), ) def _grid_cell_counts(foreground_mask: np.ndarray, layout: GridLayout) -> int: """Number of grid cells holding at least one foreground pixel.""" h, w = foreground_mask.shape row_range, col_range = _content_cell_ranges(foreground_mask, layout) occupied = 0 for r in row_range: y0, y1 = _cell_bounds(layout.offset_y, layout.cell_height, r, h) if y1 <= y0: continue band = foreground_mask[y0:y1] if not band.any(): continue for c in col_range: x0, x1 = _cell_bounds(layout.offset_x, layout.cell_width, c, w) if x1 > x0 and band[:, x0:x1].any(): occupied += 1 return occupied def detect_separator_grid(foreground_mask: np.ndarray) -> GridLayout | None: """ Detect a periodic frame layout whose every cut line is pure background. This is the detector for animation strips and effect sheets: frames separated by a background gutter, frame size NOT necessarily a divisor of the sheet size (a 256px sheet of 48px frames with 16px of trailing padding is completely normal), and frames that are internally just a scatter of loose particles. Returns None unless both axes (or one axis, with the other treated as a single band) yield a period explaining at least GRID_SEPARATOR_MIN_CELLS occupied cells. """ from config import GRID_SEPARATOR_MIN_CELL_PX, GRID_SEPARATOR_MIN_CELLS h, w = foreground_mask.shape if h == 0 or w == 0 or not foreground_mask.any(): return None col_empty = ~foreground_mask.any(axis=0) row_empty = ~foreground_mask.any(axis=1) x_period = _axis_separator_period(col_empty, GRID_SEPARATOR_MIN_CELL_PX) y_period = _axis_separator_period(row_empty, GRID_SEPARATOR_MIN_CELL_PX) if x_period is None and y_period is None: return None # The layout's origin is one full cell before the first cut line, so # cell 0 is the (possibly short) leading cell in front of it. cell_w, origin_x = (x_period[0], x_period[1] - x_period[0]) if x_period else (w, 0) cell_h, origin_y = (y_period[0], y_period[1] - y_period[0]) if y_period else (h, 0) columns = max(1, -(-(w - origin_x) // cell_w)) rows = max(1, -(-(h - origin_y) // cell_h)) layout = GridLayout( cell_width=cell_w, cell_height=cell_h, columns=columns, rows=rows, offset_x=origin_x, offset_y=origin_y, score=90.0, source="separator", ) layout.occupied_cells = _grid_cell_counts(foreground_mask, layout) if layout.occupied_cells < GRID_SEPARATOR_MIN_CELLS: return None return layout # --------------------------------------------------------------------------- # Tile grid (edge-to-edge tilesets, detected from image edge periodicity) # --------------------------------------------------------------------------- def _edge_energy_profiles(rgba: np.ndarray) -> tuple[np.ndarray, np.ndarray]: """ Mean absolute RGBA difference between each pair of adjacent columns and rows. Index i holds the discontinuity between line i and line i+1. A tileset's tile boundaries are where unrelated artwork meets, so they carry a much larger discontinuity than the (usually smooth, repetitive) interior of a tile -- which makes this profile a direct read-out of the tile pitch even when there is no background gutter anywhere on the sheet for `detect_separator_grid` to find. """ a = rgba.astype(np.int32) dx = np.abs(a[:, 1:, :] - a[:, :-1, :]).sum(axis=2).mean(axis=0) dy = np.abs(a[1:, :, :] - a[:-1, :, :]).sum(axis=2).mean(axis=1) return dx, dy def _tile_pitch_scores(profile: np.ndarray, length: int) -> dict[int, float]: """ For every candidate tile size dividing `length` evenly, how much stronger the discontinuity along that size's cut lines is than the sheet's average discontinuity. 1.0 means "no better than an arbitrary line", i.e. no evidence of a grid at that pitch. """ from config import TILE_MIN_BOUNDARY_LINES, TILE_MIN_CELL_PX mean_all = float(profile.mean()) if profile.size else 0.0 if mean_all <= 0: return {} scores: dict[int, float] = {} for cell in range(TILE_MIN_CELL_PX, length // 2 + 1): if length % cell: continue lines = np.arange(1, length // cell) * cell - 1 if lines.size < TILE_MIN_BOUNDARY_LINES: continue scores[cell] = float(profile[lines].mean() / mean_all) return scores def detect_tile_grid(rgba: np.ndarray | None, foreground_mask: np.ndarray) -> GridLayout | None: """ Detect a square tile pitch from the sheet's own edge periodicity. Every multiple of the true tile size also lines up with real tile boundaries (its cut lines are a subset of the true ones), so scoring alone always favours the largest multiple -- which is exactly how a 16x16 dungeon tileset gets misread as 32x32 or 80x80. The search therefore takes the SMALLEST pitch that scores within TILE_EDGE_RELATIVE_TOLERANCE of the best one. Needs the actual RGBA pixels (a boolean foreground mask has no colour discontinuities to measure), and returns None without them. """ from config import TILE_EDGE_MIN_RATIO, TILE_EDGE_RELATIVE_TOLERANCE h, w = foreground_mask.shape if rgba is None or rgba.ndim != 3 or rgba.shape[0] != h or rgba.shape[1] != w: return None if h < 8 or w < 8: return None dx, dy = _edge_energy_profiles(rgba) x_scores = _tile_pitch_scores(dx, w) y_scores = _tile_pitch_scores(dy, h) # Square tiles only -- the convention for tilesets, and requiring both # axes to agree is what keeps animation sheets (which show a strong # pitch on one axis only) out of this detector. shared = {c: min(x_scores[c], y_scores[c]) for c in x_scores if c in y_scores} if not shared: return None best = max(shared.values()) if best < TILE_EDGE_MIN_RATIO: return None for cell in sorted(shared): if shared[cell] < TILE_EDGE_RELATIVE_TOLERANCE * best: continue columns, rows = w // cell, h // cell # Cross-check against the content-based score so a pitch that lines # up with strong edges but carves the content nonsensically (mostly # empty or wildly uneven cells) is still rejected. content_score = _score_grid_candidate(foreground_mask, cell, cell, columns, rows, 0, 0) if content_score < 50.0: continue layout = GridLayout( cell_width=cell, cell_height=cell, columns=columns, rows=rows, offset_x=0, offset_y=0, score=min(100.0, 0.5 * content_score + 50.0), source="tile", ) layout.occupied_cells = _grid_cell_counts(foreground_mask, layout) return layout return None # --------------------------------------------------------------------------- # Merge-only regrouping against a validated grid # --------------------------------------------------------------------------- def regroup_by_grid( foreground_mask: np.ndarray, groups: list[SpriteGroup], noise: list[RawComponent], layout: GridLayout, ) -> list[DetectedSprite]: """ Rebuild the sprite list by grid cell instead of by pixel adjacency, WITHOUT ever splitting something the gap pipeline already decided was one sprite. Any gap-based group whose bounding box straddles a cut line unions those cells together, so the plant-leaf-and-stem case (two blobs with background between them, correctly merged upstream) survives even if the grid would otherwise have cut between them. Everything else in a cell -- including the sub-MIN_SPRITE_SIZE_PX particles the gap pipeline discarded -- collapses into that cell's single sprite. The result is therefore a pure coarsening of the gap result: it can only ever merge, never split. """ h, w = foreground_mask.shape cols, rows = layout.columns, layout.rows if cols * rows == 0: return [] # Sparse union-find: a fine grid over a large canvas has far more # nominal cells than occupied ones, so cells are only materialised # when something actually refers to them. parent: dict[int, int] = {} def find(i: int) -> int: parent.setdefault(i, i) while parent[i] != i: parent[i] = parent.setdefault(parent[i], parent[i]) i = parent[i] return i def union(i: int, j: int) -> None: ri, rj = find(i), find(j) if ri != rj: parent[ri] = rj def cell_index(x: int, y: int) -> tuple[int, int]: c = (x - layout.offset_x) // layout.cell_width r = (y - layout.offset_y) // layout.cell_height return min(cols - 1, max(0, int(c))), min(rows - 1, max(0, int(r))) # A group spanning several cells fuses them, so it stays one sprite. for g in groups: b = g.bbox c0, r0 = cell_index(b.x, b.y) c1, r1 = cell_index(b.x2 - 1, b.y2 - 1) anchor = r0 * cols + c0 for r in range(r0, r1 + 1): for c in range(c0, c1 + 1): union(anchor, r * cols + c) # Per-cell geometry straight from the mask, so nothing the component # stage rejected as noise gets lost. component_counts: dict[int, int] = {} for g in groups: c, r = cell_index(int(g.bbox.cx), int(g.bbox.cy)) component_counts[r * cols + c] = component_counts.get(r * cols + c, 0) + len(g.components) for n in noise: c, r = cell_index(int(n.bbox.cx), int(n.bbox.cy)) component_counts[r * cols + c] = component_counts.get(r * cols + c, 0) + 1 row_range, col_range = _content_cell_ranges(foreground_mask, layout) buckets: dict[int, dict] = {} for r in row_range: y0, y1 = _cell_bounds(layout.offset_y, layout.cell_height, r, h) if y1 <= y0: continue band = foreground_mask[y0:y1] if not band.any(): continue for c in col_range: x0, x1 = _cell_bounds(layout.offset_x, layout.cell_width, c, w) if x1 <= x0: continue cell = band[:, x0:x1] if not cell.any(): continue ys, xs = np.nonzero(cell) box = BBox( x=x0 + int(xs.min()), y=y0 + int(ys.min()), width=int(xs.max()) - int(xs.min()) + 1, height=int(ys.max()) - int(ys.min()) + 1, ) idx = r * cols + c bucket = buckets.setdefault(find(idx), {"bbox": None, "pixels": 0, "components": 0}) bucket["bbox"] = box if bucket["bbox"] is None else bucket["bbox"].union(box) bucket["pixels"] += int(cell.sum()) bucket["components"] += component_counts.get(idx, 0) ordered = sorted(buckets.values(), key=lambda b: (round(b["bbox"].y / 8), b["bbox"].x)) detected: list[DetectedSprite] = [] for idx, bucket in enumerate(ordered, start=1): confidence, reasons = _confidence_for( bbox=bucket["bbox"], pixel_count=bucket["pixels"], component_count=max(1, bucket["components"]), sheet_shape=(h, w), has_close_neighbour=False, # unused for grid-backed sprites grid_backed=True, ) reasons = [f"Grid cell ({layout.cell_width}x{layout.cell_height}, {layout.source})"] + reasons detected.append( DetectedSprite( sprite_index=idx, bbox=bucket["bbox"], confidence=confidence, confidence_reasons=reasons, component_count=max(1, bucket["components"]), pixel_count=bucket["pixels"], source=layout.source, ) ) return detected def _gap_based_result_looks_like_grid_failure( detected: list[DetectedSprite], sheet_shape: tuple[int, int], tile_layout: GridLayout | None = None, ) -> bool: """ Heuristic for "the gap-based pipeline probably fused a whole row/ column into one blob because this sheet has no real gaps between sprites" -- see the module docstring's Grid mode section. The real fingerprint of this failure is a detected region that spans almost the FULL HEIGHT or FULL WIDTH of the sheet (e.g. one column of a portrait grid, with cells touching top-to-bottom, becomes a single bbox as tall as the entire sheet). Average area fraction alone is not a safe signal: a sheet with just two genuinely separate, reasonably large sprites can easily average >8% of the sheet's area without being a grid-failure case at all (e.g. two 10x10 sprites on a small 40x20 sheet is 12.5% each, and is exactly the "should stay separate" scenario this pipeline is otherwise designed to get right). Requiring near-full-span on at least one axis avoids that false positive. """ from config import ( GRID_FALLBACK_MAX_REGIONS, GRID_FALLBACK_SPAN_FRACTION, GRID_OVERMERGE_AREA_FRACTION, GRID_SEPARATOR_MIN_CELLS, ) if not detected: return False h, w = sheet_shape sheet_area = max(1, h * w) # A single detected region is normally not a grid failure -- a sheet # that's genuinely just one sprite must never be routed into grid # mode. The exception is a fully opaque tileset, which fuses into ONE # sheet-sized blob and would otherwise be unreachable; that is only # believed when the sheet's own edge periodicity independently reports # a real tile grid, which a lone sprite never does. if len(detected) < 2: if tile_layout is None or tile_layout.occupied_cells < GRID_SEPARATOR_MIN_CELLS: return False b = detected[0].bbox spans = b.height >= GRID_FALLBACK_SPAN_FRACTION * h or b.width >= GRID_FALLBACK_SPAN_FRACTION * w return spans and b.area >= GRID_OVERMERGE_AREA_FRACTION * sheet_area for d in detected: spans_height = d.bbox.height >= GRID_FALLBACK_SPAN_FRACTION * h spans_width = d.bbox.width >= GRID_FALLBACK_SPAN_FRACTION * w if not (spans_height or spans_width): continue if len(detected) <= GRID_FALLBACK_MAX_REGIONS: return True # Many regions AND one of them still swallows a large share of the # sheet: a tileset whose contiguous floor/wall area fused into one # blob while its loose items segmented fine. The area condition is # what separates this from a legitimate full-width fence sprite, # which spans an axis but covers almost none of the sheet. if d.bbox.area >= GRID_OVERMERGE_AREA_FRACTION * sheet_area: return True return False def _gap_based_result_looks_shattered( gap_group_count: int, noise_pixel_fraction: float, layout: GridLayout | None, ) -> bool: """ Heuristic for the opposite failure: one logical frame torn into many pieces, because its parts are separated by more background than the adaptive merge radius allows (an explosion's flying debris, a sparkle burst's scattered stars). Two independent symptoms, either of which is enough: - the gap pipeline reports substantially more regions than the validated grid has occupied cells, i.e. cells are being cut up; - a noticeable share of the sheet's ink was thrown away as sub-MIN_SPRITE_SIZE_PX speckle. Frames built from loose 1-2px particles hit this even when the region COUNT looks reasonable, because the shattered pieces are not merely split -- they are dropped, and whole frames silently disappear. """ from config import GRID_NOISE_PIXEL_FRACTION, GRID_SHATTER_RATIO if layout is None or layout.occupied_cells <= 0: return False if noise_pixel_fraction >= GRID_NOISE_PIXEL_FRACTION: return True return gap_group_count >= GRID_SHATTER_RATIO * layout.occupied_cells # --------------------------------------------------------------------------- # Orchestration # --------------------------------------------------------------------------- def _detect_cutting_grid( foreground_mask: np.ndarray, rgba: np.ndarray | None, tile_layout: GridLayout | None = None, allow_separator: bool = False, ) -> GridLayout | None: """ Best available grid layout for a sheet that has to be re-cut wholesale, tried strongest-evidence first: 1. tile pitch from edge periodicity -- the only detector that works on an edge-to-edge tileset, where there is no background gutter anywhere to measure; 2. optionally a separator grid, whose every cut line is verified to be pure background; 3. the divisor/occupancy detector -- the original path, which is what handles a fixed-cell portrait/expression sheet (neither a measurable tile pitch nor a gutter to find). `allow_separator` is off by default. A separator grid guarantees only that its cuts fall on background, not that they fall BETWEEN sprites: a frame containing a one-pixel internal gap offers a legal cut straight through itself. That is harmless in the merge-only regrouping path, which cannot split a sprite the gap stage joined, but it is not safe when the layout is used to re-cut the sheet outright. Explicit `mode="grid"` turns it on, since there the caller has asked for a grid cut and the separator grid is the best answer for a frame sheet. """ layout = tile_layout if tile_layout is not None else detect_tile_grid(rgba, foreground_mask) if layout is not None: return layout if allow_separator: layout = detect_separator_grid(foreground_mask) if layout is not None: return layout layout = detect_grid_layout(foreground_mask) if layout is not None and layout.score >= 50.0: return layout return None def segment_sheet( foreground_mask: np.ndarray, mode: str = "auto", rgba: np.ndarray | None = None, ) -> tuple[list[DetectedSprite], np.ndarray, list[SpriteGroup]]: """ Full pipeline entry point. `rgba` is the sheet's original HxWx4 pixels. It is optional -- every mask-only caller keeps working exactly as before -- but supplying it enables `detect_tile_grid`, which is the only way to recover the cell pitch of a tileset drawn edge to edge with no background between tiles. `mode`: - "auto" (default): run the gap-based pipeline, then correct it if it shows one of the two failure signatures this sheet type causes: * OVER-MERGE -- a region swallowing a whole row/column or a large share of the sheet, which is what an edge-to-edge tileset or portrait grid collapses into. The sheet is re-cut along a detected grid (see `_detect_cutting_grid`). * SHATTERING -- one logical animation frame torn into many regions, or its loose particles dropped as speckle. The gap result is regrouped by a separator grid, a MERGE-ONLY operation that cannot split anything the gap stage joined (see `regroup_by_grid`). With no failure signature, or no confident grid, the gap-based result is returned untouched -- irregular sheets are unaffected. - "gap": always use the original gap-based pipeline, never grid. - "grid": always use grid segmentation (a usable layout must be found, otherwise raises ValueError -- this mode is for explicit user override, so silently falling back to something else would be confusing). Returns: - list of DetectedSprite (index, bbox, confidence, reasons) - the raw label array (for building exact per-sprite pixel masks; None in grid mode, since there is no connected-component label array -- callers needing exact per-sprite masks in grid mode should crop directly from the sheet using each DetectedSprite's bbox instead) - the SpriteGroup list (empty in grid mode, for the same reason) """ if mode not in ("auto", "gap", "grid"): raise ValueError(f"Unknown segmentation mode: {mode!r}") if mode == "grid": layout = _detect_cutting_grid(foreground_mask, rgba, allow_separator=True) if layout is None: raise ValueError("No usable grid layout detected for this sheet.") return segment_grid(foreground_mask, layout), None, [] gap_detected, labels, groups, noise = _segment_sheet_gap_based(foreground_mask) if mode == "gap": return gap_detected, labels, groups # mode == "auto" tile_layout = detect_tile_grid(rgba, foreground_mask) if _gap_based_result_looks_like_grid_failure(gap_detected, foreground_mask.shape, tile_layout): layout = _detect_cutting_grid(foreground_mask, rgba, tile_layout=tile_layout) if layout is not None: return segment_grid(foreground_mask, layout), None, [] return gap_detected, labels, groups total_pixels = int(foreground_mask.sum()) noise_pixels = sum(n.pixel_count for n in noise) noise_fraction = noise_pixels / max(1, total_pixels) separator = detect_separator_grid(foreground_mask) if _gap_based_result_looks_shattered(len(groups), noise_fraction, separator): regrouped = regroup_by_grid(foreground_mask, groups, noise, separator) if regrouped: return regrouped, labels, groups return gap_detected, labels, groups def _segment_sheet_gap_based( foreground_mask: np.ndarray, ) -> tuple[list[DetectedSprite], np.ndarray, list[SpriteGroup], list[RawComponent]]: """The original gap-based pipeline, unchanged -- see module docstring.""" cleaned = find_foreground_regions(foreground_mask) labels, components, noise = find_components(cleaned) groups = merge_related_components(components) groups = detect_sprite_boundaries(groups, foreground_mask.shape) # Stable ordering: reading order (top-to-bottom, then left-to-right), # which is what the "[1] [2] [3] ..." preview numbering in the spec # expects. groups.sort(key=lambda g: (round(g.bbox.y / 8), g.bbox.x)) close_flags = _close_neighbour_flags([g.bbox for g in groups]) detected: list[DetectedSprite] = [] for idx, g in enumerate(groups, start=1): confidence, reasons = _confidence_for( bbox=g.bbox, pixel_count=g.pixel_count, component_count=len(g.components), sheet_shape=foreground_mask.shape, has_close_neighbour=close_flags[idx - 1], ) detected.append( DetectedSprite( sprite_index=idx, bbox=g.bbox, confidence=confidence, confidence_reasons=reasons, component_count=len(g.components), pixel_count=g.pixel_count, ) ) return detected, labels, groups, noise