Coverage for paintmaskanimator/bucket_fill.py: 92%
760 statements
« prev ^ index » next coverage.py v7.17.0, created at 2026-11-02 04:50 +0000
1"""バケツ塗りの領域判定（UI非依存）。
3``PaintCanvas.flood_fill`` が抱えていた「どの画素を塗るか」の計算だけを切り出す。
5切り出した理由は串刺し塗りにある。串刺し塗りは同じ判定を別のコマの画像に対して
6繰り返すだけの操作なので、判定が UI 側の後始末（Undo・ステータス表示・シグナル
7発行）と混ざったままだと、同じ 200 行を二度書くことになる。ここには判定だけを
8置き、「塗れなかった理由」は :class:`FillResult` の ``reason`` で返して、
9どう見せるかは呼び出し側に任せる。
11QImage も QWidget も触らず numpy 配列だけを扱うので、GUI なしで単体テストできる。
12"""
13from __future__ import annotations
15from dataclasses import dataclass, field
16from typing import Optional, Tuple
18import numpy as np
20from . import native
21from .imaging import (
22 background_mask_packed,
23 mask_bounds,
24 opaque_rgb_mask_packed,
25 rgba_packed_view,
26 scanline_connected_region,
27)
29__all__ = [
30 "BucketOptions",
31 "BucketSession",
32 "FillResult",
33 "compute_fill_region",
34 "fill_target_mask",
35 "track_fill_region",
36 "enclosed_islands",
37 "guess_target_categories",
38 "TARGET_COLORS",
39 "REFERENCE_LAYER",
40 "REFERENCE_CANVAS",
41 "REFERENCE_INITIAL",
42 "REFERENCES",
43 "seed_category",
44 "dilate",
45 "erode",
46 "extend_line_ends",
47 "REASON_OK",
48 "REASON_OUT_OF_BOUNDS",
49 "REASON_OUTSIDE_SELECTION",
50 "REASON_EMPTY",
51 "REASON_OPEN_REGION",
52]
54#: 塗れた。
55REASON_OK = "ok"
56#: 開始点がキャンバスの外。
57REASON_OUT_OF_BOUNDS = "out_of_bounds"
58#: 開始点が選択範囲の外。
59REASON_OUTSIDE_SELECTION = "outside_selection"
60#: 判定の結果、塗る画素が 1 つも残らなかった。
61REASON_EMPTY = "empty"
62#: 「開いている領域は塗らない」設定で、領域がキャンバス端に達していた。
63REASON_OPEN_REGION = "open_region"
64#: 「対象色」の設定で、クリックした画素が塗る対象ではなかった。
65REASON_NOT_TARGET = "not_target"
67# 対象色（CLIP STUDIO の「対象色」に合わせた選択肢）。
68#: クリックした色の領域（これまでどおり）。
69TARGET_ALL = "all"
70#: 透明な画素だけをたどる。
71TARGET_TRANSPARENT = "transparent"
72#: 透明以外の画素をたどる（透明に囲まれた部分）。
73TARGET_SURROUNDED_BY_TRANSPARENT = "surrounded_by_transparent"
74#: 黒い画素だけをたどる。
75TARGET_BLACK = "black"
76#: 黒以外の画素をたどる（黒い線に囲まれた部分）。
77TARGET_SURROUNDED_BY_BLACK = "surrounded_by_black"
78#: 白と透明の画素だけをたどる。
79TARGET_WHITE_TRANSPARENT = "white_transparent"
80#: 白と透明以外の画素をたどる。
81TARGET_SURROUNDED_BY_WHITE_TRANSPARENT = "surrounded_by_white_transparent"
82#: 透明だけをたどるが、ごく薄い半透明も透明とみなす。
83TARGET_FAINT_AS_TRANSPARENT = "faint_as_transparent"
84#: 透明以外をたどり、その内側に閉じ込められた透明の穴も塗る。
85TARGET_OPAQUE_AND_INNER_TRANSPARENT = "opaque_and_inner_transparent"
86#: 透明をたどり、その中に閉じ込められた透明以外の島も塗る。
87TARGET_TRANSPARENT_AND_CLOSED_OPAQUE = "transparent_and_closed_opaque"
89TARGET_COLORS = (
90 TARGET_ALL,
91 TARGET_TRANSPARENT,
92 TARGET_SURROUNDED_BY_TRANSPARENT,
93 TARGET_BLACK,
94 TARGET_SURROUNDED_BY_BLACK,
95 TARGET_WHITE_TRANSPARENT,
96 TARGET_SURROUNDED_BY_WHITE_TRANSPARENT,
97 TARGET_FAINT_AS_TRANSPARENT,
98 TARGET_OPAQUE_AND_INNER_TRANSPARENT,
99 TARGET_TRANSPARENT_AND_CLOSED_OPAQUE,
100)
102#: 「黒」とみなす RGB の上限（各チャンネル）。線のアンチエイリアスの濃い部分も含める。
103BLACK_MAX = 48
104#: 「白」とみなす RGB の下限（各チャンネル）。
105WHITE_MIN = 240
106#: 「薄い半透明」とみなすアルファの上限（約20%）。
107FAINT_ALPHA_MAX = 50
109# 参照レイヤー（どの絵を見て領域を決めるか）。塗る先はいつもアクティブレイヤーで、
110# 「どこを塗るか」の判定だけを、ここで選んだ絵から行う。
111#: 選択したレイヤーのみ（これまでどおり）。
112REFERENCE_LAYER = "layer"
113#: キャンバス全体（表示しているレイヤーを合成した絵）。
114REFERENCE_CANVAS = "canvas"
115#: 色塗り前の初期状態（保持していなければ今の絵）。
116REFERENCE_INITIAL = "initial"
118#: 参照レイヤーの選択肢。
119REFERENCES = (REFERENCE_LAYER, REFERENCE_CANVAS, REFERENCE_INITIAL)
122@dataclass(frozen=True)
123class BucketOptions:
124 """ツールパネルのバケツ設定を、UI から切り離して持ち回るための値。
126 ``PaintCanvas`` と串刺し塗りの両方が同じ設定で判定するように、
127 チェックボックスの読み出しは :meth:`from_tools` の 1 箇所へ集める。
128 """
130 #: クリック位置につながる領域だけを塗る（OFF ならレイヤー内の同色を一括）。
131 adjacent: bool = True
132 #: 角で接する塗り残しの幅の上限（px）。0 なら拾わない。
133 island_max_width: int = 0
134 #: 含み塗り（「含む色」に接する部分も塗りに含める）。
135 include_masks: bool = False
136 #: 含み塗りの対象色（RGB のタプル列）。「含む色」の登録色、未登録ならサブカラー。
137 mask_colors: Tuple[Tuple[int, int, int], ...] = ()
138 #: 含み塗りの対象に背景（擬似透明）が含まれるか。
139 include_background_mask: bool = False
140 #: 線の隙間を仮想的に閉じてから塗る。
141 close_gap: bool = False
142 #: 隙間閉じの半径（px）。
143 gap_width: int = 4
144 #: キャンバス端の手前で途切れた線を、端まで仮想的に延長してから塗る。
145 extend_lines: bool = False
146 #: 線を延長する最大の長さ（px）。端からこれより遠い線の端は延長しない。
147 extend_length: int = 150
148 #: 領域がキャンバス端まで開いている場合は塗らない。
149 require_closed: bool = False
150 #: どの画素をたどって塗るか（``TARGET_*``）。
151 target_color: str = TARGET_ALL
152 #: どの絵を見て領域を決めるか（``REFERENCE_*``）。塗る先は変わらない。
153 reference: str = REFERENCE_LAYER
154 #: 塗った範囲に囲まれた島（色トレスの斜線など）を塗り替える色。
155 #: ``((元の RGB, 塗り替える RGB), ...)``。使用色パネルの置換色から作る。
156 island_replacements: Tuple[
157 Tuple[Tuple[int, int, int], Tuple[int, int, int]], ...
158 ] = ()
160 @classmethod
161 def from_tools(
162 cls, tools, *, mask_colors=(), background_selected=False,
163 island_replacements=(),
164 ):
165 """ツールパネルのウィジェットから設定を読み出す。
167 ``tools`` が ``None``（ウィンドウを持たないテスト用のキャンバスなど）の
168 ときは ``flood_fill`` の従来の既定値と同じになるようにする。
169 """
170 if tools is None:
171 return cls(
172 mask_colors=tuple(mask_colors),
173 include_background_mask=bool(background_selected),
174 )
175 return cls(
176 adjacent=bool(tools.bucket_adjacent.isChecked()),
177 island_max_width=(
178 max(1, int(tools.bucket_island_fill_width.value()))
179 if _checked(tools, "bucket_island_fill") else 0
180 ),
181 include_masks=bool(tools.bucket_include_sub.isChecked()),
182 mask_colors=tuple(mask_colors),
183 include_background_mask=bool(background_selected),
184 close_gap=bool(tools.bucket_close_gap.isChecked()),
185 gap_width=max(1, int(tools.bucket_gap_width.value())),
186 extend_lines=bool(_checked(tools, "bucket_extend_lines")),
187 extend_length=_extend_length_from_tools(tools),
188 require_closed=bool(tools.bucket_require_closed.isChecked()),
189 target_color=_target_from_tools(tools),
190 reference=_reference_from_tools(tools),
191 island_replacements=(
192 tuple(island_replacements)
193 if _checked(tools, "bucket_island_replace") else ()
194 ),
195 )
198def _checked(tools, name):
199 widget = getattr(tools, name, None)
200 return widget is not None and widget.isChecked()
203def _extend_length_from_tools(tools):
204 widget = getattr(tools, "bucket_extend_length", None)
205 if widget is None: 205 ↛ 206line 205 didn't jump to line 206 because the condition on line 205 was never true
206 return BucketOptions.extend_length
207 return max(1, int(widget.value()))
210def _target_from_tools(tools):
211 combo = getattr(tools, "bucket_target_color", None)
212 value = combo.currentData() if combo is not None else None
213 return value if value in TARGET_COLORS else TARGET_ALL
216def _reference_from_tools(tools):
217 combo = getattr(tools, "bucket_reference", None)
218 value = combo.currentData() if combo is not None else None
219 return value if value in REFERENCES else REFERENCE_LAYER
222@dataclass
223class FillResult:
224 """:func:`compute_fill_region` の結果。
226 ``reason`` が :data:`REASON_OK` のときだけ ``region`` が入る。呼び出し側は
227 真偽値として扱える（``if result:``）。
228 """
230 reason: str = REASON_EMPTY
231 region: Optional[np.ndarray] = None
232 #: 開始点の色種別。``None`` は背景（擬似透明）を表す。
233 target: Optional[Tuple[int, int, int]] = field(default=None)
234 #: ``region`` の外接矩形 ``(x0, y0, x1, y1)``（x1, y1 は排他）。
235 bounds: Optional[Tuple[int, int, int, int]] = None
236 #: :func:`track_fill_region` が前のコマの領域との重なり（IoU）を入れる。
237 #: 追跡でない塗り（クリックした種から塗った場合）は ``None``。
238 score: Optional[float] = None
239 #: 囲まれた島の塗り替え ``((塗り替える RGB, マスク), ...)``。
240 #: ``BucketOptions.island_replacements`` が空なら空。
241 islands: Tuple[Tuple[Tuple[int, int, int], np.ndarray], ...] = ()
242 #: :func:`track_fill_region` で ``score`` を出したときの、動かした前のコマの領域。
243 #: 塗る範囲を広げた呼び出し側が、同じ位置で重なりを測り直すのに使う。
244 matched: Optional[np.ndarray] = None
246 @property
247 def ok(self) -> bool:
248 return self.reason == REASON_OK and self.region is not None
250 @property
251 def mask(self) -> np.ndarray:
252 """塗る画素のマスク。``ok`` が偽のときに読むのは呼び出し側の誤り。"""
253 if self.region is None: 253 ↛ 254line 253 didn't jump to line 254 because the condition on line 253 was never true
254 raise ValueError(f"塗る領域がない（reason={self.reason}）")
255 return self.region
257 def __bool__(self) -> bool:
258 return self.ok
261def dilate(mask, iterations):
262 """8 近傍で ``iterations`` 回膨張させる（Rust）。"""
263 return native.dilate(mask, iterations)
266def dilate_numpy(mask, iterations):
267 """8 近傍で ``iterations`` 回膨張させる（numpy 版）。"""
268 result = mask.copy()
269 for _ in range(iterations):
270 source = result.copy()
271 result[1:, :] |= source[:-1, :]
272 result[:-1, :] |= source[1:, :]
273 result[:, 1:] |= source[:, :-1]
274 result[:, :-1] |= source[:, 1:]
275 result[1:, 1:] |= source[:-1, :-1]
276 result[:-1, :-1] |= source[1:, 1:]
277 result[1:, :-1] |= source[:-1, 1:]
278 result[:-1, 1:] |= source[1:, :-1]
279 return result
282def erode(mask, iterations):
283 """8 近傍で ``iterations`` 回収縮させる（Rust）。"""
284 return native.erode(mask, iterations)
287def erode_numpy(mask, iterations):
288 """8 近傍で ``iterations`` 回収縮させる（numpy 版）。"""
289 result = mask.copy()
290 for _ in range(iterations):
291 padded = np.pad(
292 result, ((1, 1), (1, 1)), mode="constant", constant_values=False
293 )
294 result = (
295 padded[0:-2, 0:-2]
296 & padded[0:-2, 1:-1]
297 & padded[0:-2, 2:]
298 & padded[1:-1, 0:-2]
299 & padded[1:-1, 1:-1]
300 & padded[1:-1, 2:]
301 & padded[2:, 0:-2]
302 & padded[2:, 1:-1]
303 & padded[2:, 2:]
304 )
305 return result
308#: 線の向きを測るために、端からたどる骨格の画素数。
309EXTEND_TRACE_LENGTH = 12
310#: これより短い骨格（点・ごく短いハネ）は向きが定まらないので延長しない。
311EXTEND_MIN_TRACE = 6
312#: 細線化の最大反復回数。線の太さのおよそ半分あれば足りる。
313EXTEND_THIN_ITERATIONS = 8
316def _thin(mask, max_iterations):
317 return native.thin(mask, max_iterations)
320def _thin_numpy(mask, max_iterations):
321 """Zhang-Suen の細線化。``max_iterations`` で打ち切る。
323 太い塊は細り切らないが、延長に使うのは細い線の端点だけなので問題ない。
324 """
325 image = mask.copy()
326 for _ in range(max_iterations):
327 changed = False
328 for step in (0, 1):
329 p = np.pad(image, 1, mode="constant", constant_values=False)
330 # P2..P9：上から時計回り。
331 ring = (
332 p[:-2, 1:-1], p[:-2, 2:], p[1:-1, 2:], p[2:, 2:],
333 p[2:, 1:-1], p[2:, :-2], p[1:-1, :-2], p[:-2, :-2],
334 )
335 count = np.zeros(image.shape, dtype=np.uint8)
336 for neighbor in ring:
337 count += neighbor
338 transitions = np.zeros(image.shape, dtype=np.uint8)
339 for index, neighbor in enumerate(ring):
340 transitions += ~neighbor & ring[(index + 1) % 8]
341 p2, p4, p6, p8 = ring[0], ring[2], ring[4], ring[6]
342 if step == 0:
343 keep = (p2 & p4 & p6) | (p4 & p6 & p8)
344 else:
345 keep = (p2 & p4 & p8) | (p2 & p6 & p8)
346 remove = (
347 image & (count >= 2) & (count <= 6) & (transitions == 1) & ~keep
348 )
349 if remove.any():
350 image &= ~remove
351 changed = True
352 if not changed:
353 break
354 return image
357def _trace_from_end(skeleton, x, y, length):
358 """骨格の端点 ``(x, y)`` から線に沿って ``length`` 画素たどった座標列。
360 分岐に当たったらそこで止める。細線化の階段部分では次の候補が隣り合って
361 2つ出るので、そのときは遠い（斜め）方へ進む。
362 """
363 height, width = skeleton.shape
364 path = [(x, y)]
365 visited = {(x, y)}
366 while len(path) < length:
367 cx, cy = path[-1]
368 candidates = [
369 (nx, ny)
370 for ny in range(cy - 1, cy + 2)
371 for nx in range(cx - 1, cx + 2)
372 if 0 <= nx < width and 0 <= ny < height
373 and (nx, ny) not in visited and skeleton[ny, nx]
374 ]
375 if not candidates:
376 break
377 if len(candidates) > 1 and any(
378 max(abs(ax - bx), abs(ay - by)) > 1
379 for ax, ay in candidates for bx, by in candidates
380 ):
381 break
382 visited.update(candidates)
383 path.append(max(
384 candidates, key=lambda c: (c[0] - cx) ** 2 + (c[1] - cy) ** 2
385 ))
386 return path
389def _cast_ray(boundary, x, y, dx, dy, max_length):
390 """端点から ``(dx, dy)`` 方向へ線を延ばした画素。届かなければ ``None``。
392 自分の線の内側にいる間の境界は無視し、いったん外へ出てから別の境界に
393 当たるか、キャンバスの外へ出たら止める。1 ステップで主軸方向へ 1 画素
394 進むので、延長線は 8 連結になり 4 近傍の塗りを確実に止める。
395 """
396 height, width = boundary.shape
397 major = max(abs(dx), abs(dy))
398 step_x, step_y = dx / major, dy / major
399 pixels = []
400 left_own_line = False
401 for t in range(1, max_length * 2 + 1): 401 ↛ 414line 401 didn't jump to line 414 because the loop on line 401 didn't complete
402 px = int(round(x + step_x * t))
403 py = int(round(y + step_y * t))
404 if not (0 <= px < width and 0 <= py < height):
405 return pixels
406 if boundary[py, px]:
407 if left_own_line:
408 return pixels
409 continue
410 left_own_line = True
411 pixels.append((px, py))
412 if len(pixels) > max_length: 412 ↛ 413line 412 didn't jump to line 413 because the condition on line 412 was never true
413 return None
414 return None
417def extend_line_ends(boundary, max_length, cache=None):
418 """キャンバス端の手前で途切れた線を、端まで延ばした画素の真偽マスク。
420 作画では画面に映る範囲（スタンダードフレーム）の外まで素材を用意するが、
421 フレームの外では線を端まで引かないことが多い。そのまま塗ると線の切れ目から
422 隣の領域へ漏れるので、端点の向きのまま線を延ばした仮想の境界を返す。
424 延ばすのは「その向きでキャンバス端まで ``max_length`` 以内」の端点だけで、
425 途中で別の線に当たればそこで止める。絵の内側の端点（髪のハネなど）は
426 延長しないので、ふつうの塗りには影響しない。
428 :param boundary: 塗りを止める画素（線など）の真偽マスク。
429 :param cache: ドラッグ中だけ保持する細線化のキャッシュ。衝突判定は再利用しない。
430 :returns: 延長線の画素。``boundary`` の画素は含まない。
431 """
432 height, width = boundary.shape
433 extension = np.zeros((height, width), dtype=bool)
434 max_length = max(1, int(max_length))
435 # 端から max_length 以内の帯だけを細線化する（全体を細線化すると大きな
436 # キャンバスで遅い）。向きを測るために少し内側まで含める。
437 band = max_length + EXTEND_TRACE_LENGTH + EXTEND_THIN_ITERATIONS + 2
438 strips = (
439 (0, min(height, band), 0, width),
440 (max(0, height - band), height, 0, width),
441 (0, height, 0, min(width, band)),
442 (0, height, max(0, width - band), width),
443 )
444 for y0, y1, x0, x1 in strips:
445 part = boundary[y0:y1, x0:x1]
446 if not part.any():
447 continue
448 key = (y0, y1, x0, x1, EXTEND_THIN_ITERATIONS)
449 cached = cache.get(key) if cache is not None else None
450 if cached is not None and np.array_equal(cached[0], part):
451 skeleton = cached[1]
452 else:
453 skeleton = _thin(part, EXTEND_THIN_ITERATIONS)
454 if cache is not None:
455 # ドラッグ中だけ保持する。線や参照が変わった帯は必ず計算し直す。
456 if key not in cache and len(cache) >= 4: 456 ↛ 457line 456 didn't jump to line 457 because the condition on line 456 was never true
457 cache.clear()
458 cache[key] = (part.copy(), skeleton)
459 padded = np.pad(skeleton, 1, mode="constant", constant_values=False)
460 neighbors = np.zeros(skeleton.shape, dtype=np.uint8)
461 for oy in range(3):
462 for ox in range(3):
463 if ox != 1 or oy != 1:
464 neighbors += padded[
465 oy:oy + skeleton.shape[0], ox:ox + skeleton.shape[1]
466 ]
467 end_ys, end_xs = np.nonzero(skeleton & (neighbors == 1))
468 for local_x, local_y in zip(end_xs.tolist(), end_ys.tolist()):
469 x, y = local_x + x0, local_y + y0
470 if min(x, y, width - 1 - x, height - 1 - y) > max_length:
471 continue
472 path = _trace_from_end(
473 skeleton, local_x, local_y, EXTEND_TRACE_LENGTH
474 )
475 if len(path) < EXTEND_MIN_TRACE:
476 continue
477 dx = float(path[0][0] - path[-1][0])
478 dy = float(path[0][1] - path[-1][1])
479 if dx == 0.0 and dy == 0.0: 479 ↛ 480line 479 didn't jump to line 480 because the condition on line 479 was never true
480 continue
481 # その向きで端まで max_length 以内の端点だけを延ばす。届く前に
482 # 別の線へ当たった場合はそこで止める。
483 norm = (dx * dx + dy * dy) ** 0.5
484 ux, uy = dx / norm, dy / norm
485 to_edge = min(
486 (width - 1 - x) / ux if ux > 0 else (x / -ux if ux < 0 else np.inf),
487 (height - 1 - y) / uy if uy > 0 else (y / -uy if uy < 0 else np.inf),
488 )
489 if to_edge > max_length:
490 continue
491 ray = _cast_ray(boundary, x, y, dx, dy, max_length)
492 if ray is None: 492 ↛ 493line 492 didn't jump to line 493 because the condition on line 492 was never true
493 continue
494 for px, py in ray:
495 extension[py, px] = True
496 return extension
499def background_mask(pixels):
500 """擬似透明（alpha=0 または純白）の画素。"""
501 return background_mask_packed(rgba_packed_view(pixels))
504def seed_category(pixels, start_x, start_y):
505 """開始点の「色種別」を返す。背景なら ``None``、それ以外は RGB のタプル。
507 串刺し塗りが「このコマは対象外」と判断するための鍵になる。コマごとに絵は
508 動くので、同じ座標が別のコマでは線の上に来ることがある。種別が一致する
509 コマだけを塗ることで、線を塗り潰す事故を防ぐ。
510 """
511 pixel = pixels[start_y, start_x]
512 if int(pixel[3]) == 0 or (
513 int(pixel[0]) == 255 and int(pixel[1]) == 255 and int(pixel[2]) == 255
514 ):
515 return None
516 return (int(pixel[0]), int(pixel[1]), int(pixel[2]))
519def fill_target_mask(pixels, target_color, category, packed=None):
520 """``target_color`` の設定で、たどってよい画素の真偽マスクを返す。
522 ``TARGET_ALL`` は従来どおり、開始点の色種別 ``category``（背景なら None）と
523 同じ画素。それ以外は開始点の色に関係なく、設定で決まる画素。
524 """
525 if packed is None:
526 packed = rgba_packed_view(pixels)
527 if target_color == TARGET_ALL:
528 if category is None:
529 return background_mask_packed(packed)
530 return opaque_rgb_mask_packed(packed, category)
531 alpha = pixels[:, :, 3]
532 rgb = pixels[:, :, :3]
533 transparent = alpha == 0
534 if target_color == TARGET_FAINT_AS_TRANSPARENT:
535 return alpha <= FAINT_ALPHA_MAX
536 if target_color in (TARGET_TRANSPARENT, TARGET_TRANSPARENT_AND_CLOSED_OPAQUE):
537 return transparent
538 if target_color in (
539 TARGET_SURROUNDED_BY_TRANSPARENT, TARGET_OPAQUE_AND_INNER_TRANSPARENT,
540 ):
541 return ~transparent
542 if target_color in (TARGET_BLACK, TARGET_SURROUNDED_BY_BLACK):
543 black = ~transparent & (rgb.max(axis=2) <= BLACK_MAX)
544 return black if target_color == TARGET_BLACK else ~black
545 white_or_clear = transparent | (rgb.min(axis=2) >= WHITE_MIN)
546 if target_color == TARGET_WHITE_TRANSPARENT:
547 return white_or_clear
548 return ~white_or_clear
551def _enclosed_by(region):
552 """``region`` の外側（キャンバス端につながる部分）以外の、region でない画素。"""
553 outside_candidates = ~region
554 edge = np.zeros_like(region)
555 edge[0, :] = edge[-1, :] = True
556 edge[:, 0] = edge[:, -1] = True
557 ys, xs = np.nonzero(outside_candidates & edge)
558 if not xs.size:
559 return outside_candidates
560 outside = scanline_connected_region(
561 outside_candidates, zip(xs.tolist(), ys.tolist())
562 )
563 return outside_candidates & ~outside
566@dataclass
567class CompactFill:
568 """バケツ結果を外接矩形の中だけで保持する。画像全体のマスクを保存しない。"""
570 reason: str
571 target: Optional[Tuple[int, int, int]]
572 bounds: Optional[Tuple[int, int, int, int]]
573 local: Optional[np.ndarray]
574 islands: tuple
575 result_bounds: Optional[Tuple[int, int, int, int]]
576 _sample_mask_key: object = field(default=None, repr=False, compare=False)
578 @classmethod
579 def from_result(cls, result):
580 bounds = result.bounds
581 if bounds is None and result.region is not None:
582 bounds = mask_bounds(result.region)
583 local = None
584 islands = []
585 if bounds is not None and result.region is not None:
586 x0, y0, x1, y1 = bounds
587 local = result.region[y0:y1, x0:x1].copy()
588 for color, mask in result.islands:
589 box = mask_bounds(mask)
590 if box is None: 590 ↛ 591line 590 didn't jump to line 591 because the condition on line 590 was never true
591 continue
592 ix0, iy0, ix1, iy1 = box
593 islands.append((color, box, mask[iy0:iy1, ix0:ix1].copy()))
594 return cls(result.reason, result.target, bounds, local, tuple(islands), result.bounds)
596 @property
597 def ok(self):
598 return self.reason == REASON_OK
600 @property
601 def nbytes(self):
602 return (0 if self.local is None else self.local.nbytes) + sum(
603 local.nbytes for _color, _box, local in self.islands
604 )
606 def materialize(self, shape):
607 region = None
608 if self.local is not None:
609 assert self.bounds is not None
610 region = np.zeros(shape, dtype=bool)
611 x0, y0, x1, y1 = self.bounds
612 region[y0:y1, x0:x1] = self.local
613 islands = []
614 for color, (x0, y0, x1, y1), local in self.islands:
615 mask = np.zeros(shape, dtype=bool)
616 mask[y0:y1, x0:x1] = local
617 islands.append((color, mask))
618 return FillResult(self.reason, region, target=self.target, bounds=self.result_bounds,
619 islands=tuple(islands))
622class _RegionIndex:
623 def __init__(self, passable, gpu_regions=None):
624 gpu_result = gpu_regions.index(passable) if gpu_regions is not None else None
625 if gpu_result is not None: 625 ↛ 626line 625 didn't jump to line 626 because the condition on line 625 was never true
626 self.labels, self.x0, self.y0, self.x1, self.y1 = gpu_result
627 return
628 from .reference_check import _label_runs
629 self.labels, count, (ys, xs, ends, labels) = _label_runs(passable)
630 height, width = passable.shape
631 self.x0, self.y0 = np.full(count, width), np.full(count, height)
632 self.x1, self.y1 = np.zeros(count, dtype=int), np.zeros(count, dtype=int)
633 np.minimum.at(self.x0, labels, xs)
634 np.minimum.at(self.y0, labels, ys)
635 np.maximum.at(self.x1, labels, ends)
636 np.maximum.at(self.y1, labels, ys + 1)
638 def region(self, x, y):
639 label = self.labels[y, x]
640 x0, y0, x1, y1 = self.x0[label], self.y0[label], self.x1[label], self.y1[label]
641 region = np.zeros(self.labels.shape, dtype=bool)
642 region[y0:y1, x0:x1] = self.labels[y0:y1, x0:x1] == label
643 return region
646class BucketSession:
647 """変更しない参照画像で、複数回クリックするときの共通前処理。
649 領域探索は通常のバケツと共通。画像を変更したら新しいセッションを作る。
650 """
652 def __init__(self, pixels, options, *, indexed=False, gpu_regions=None):
653 self.pixels = pixels
654 self.options = options
655 self._background = None
656 self._prepared = {}
657 self._lines = {}
658 self.indexed = indexed
659 self._indices = {}
660 self._results = {}
661 self._result_bytes = 0
662 self.gpu_regions = gpu_regions
664 @property
665 def background(self):
666 if self._background is None:
667 self._background = background_mask_packed(rgba_packed_view(self.pixels))
668 return self._background
670 @property
671 def nbytes(self):
672 """共有キャッシュの上限判定用。重複する配列も保守的に数える。"""
673 total = self.pixels.nbytes + (0 if self._background is None else self._background.nbytes)
674 total += sum(array.nbytes for prepared in self._prepared.values()
675 for array in prepared if array is not None)
676 total += sum(array.nbytes for index in self._indices.values()
677 for array in (index.labels, index.x0, index.y0, index.x1, index.y1))
678 total += sum(array.nbytes for pair in self._lines.values() for array in pair)
679 total += sum(result.nbytes + len(getattr(result, "_native_runs", b""))
680 for result in self._results.values())
681 return total
683 def prepare(self, category):
684 if category not in self._prepared:
685 # 多色の原画でも、画像全体の配列を色数ぶん保持し続けない。
686 if len(self._prepared) >= 4:
687 oldest = next(iter(self._prepared))
688 del self._prepared[oldest]
689 self._indices.pop(oldest, None)
690 # 領域番号は索引ごとに異なるので、その索引の結果も捨てる。
691 self._results.clear()
692 self._result_bytes = 0
693 self._prepared[category] = _prepare_bucket(
694 self.pixels, category, self.options, self.background, None, self._lines,
695 )
696 return self._prepared[category]
698 def compute(self, x, y):
699 return compute_fill_region(self.pixels, x, y, self.options, session=self)
701 def index(self, category, passable):
702 if category not in self._indices:
703 self._indices[category] = _RegionIndex(passable, self.gpu_regions)
704 return self._indices[category]
706 def compact(self, x, y):
707 height, width = self.pixels.shape[:2]
708 if not (0 <= x < width and 0 <= y < height): 708 ↛ 709line 708 didn't jump to line 709 because the condition on line 708 was never true
709 return CompactFill.from_result(self.compute(x, y))
710 category = seed_category(self.pixels, x, y)
711 _target, passable, _gaps = self.prepare(category)
712 if self.indexed and passable is not None and passable[y, x]:
713 key = (category, int(self.index(category, passable).labels[y, x]))
714 else:
715 key = (category, x, y)
716 if key not in self._results:
717 result = self._compact_indexed(x, y, category, passable, _gaps)
718 if result is None:
719 result = CompactFill.from_result(self.compute(x, y))
720 if self._result_bytes + result.nbytes > 32 * 1024 * 1024: 720 ↛ 721line 720 didn't jump to line 721 because the condition on line 720 was never true
721 self._results.clear()
722 self._result_bytes = 0
723 self._results[key] = result
724 self._result_bytes += result.nbytes
725 return self._results[key]
727 def _compact_indexed(self, x, y, category, passable, gaps):
728 # 単色・隣接の通常領域は、索引の矩形から直接作る。小面のたびに
729 # キャンバス全体のマスクを作ってコピーし直す必要はない。
730 options = self.options
731 if (not self.indexed or not options.adjacent or options.target_color != TARGET_ALL
732 or options.include_masks or options.island_replacements or options.island_max_width
733 or passable is None or not passable[y, x]):
734 return None
735 index = self.index(category, passable)
736 label = index.labels[y, x]
737 x0, y0, x1, y1 = (int(values[label]) for values in
738 (index.x0, index.y0, index.x1, index.y1))
739 local = index.labels[y0:y1, x0:x1] == label
740 height, width = passable.shape
741 bounds = (x0, y0, x1, y1)
742 if options.require_closed and (x0 == 0 or y0 == 0 or x1 == width or y1 == height):
743 return CompactFill(REASON_OPEN_REGION, category, bounds, local, (), None)
744 if gaps is not None:
745 ax0, ay0 = max(0, x0 - 1), max(0, y0 - 1)
746 ax1, ay1 = min(width, x1 + 1), min(height, y1 + 1)
747 nearby = gaps[ay0:ay1, ax0:ax1]
748 if nearby.any():
749 area = index.labels[ay0:ay1, ax0:ax1] == label
750 if (dilate(area, 1) & nearby).any():
751 return None # 仮想境界の回収が必要な面は共通バケツへ戻す。
752 return CompactFill(REASON_OK, category, bounds, local, (), bounds)
755def _island_fits_width(local, max_width):
756 """幅の上限より大きい正方形が入る面を除く。長さ・面積は制限しない。
758 階段状の境界にも使えるよう、幅は内接する画素の正方形の一辺で測る。
759 積分画像で偶数幅も含めて判定し、1px設定で2px幅が通るのを防ぐ。
760 """
761 side = int(max_width) + 1
762 if min(local.shape) < side:
763 return True
764 summed = np.pad(local, ((1, 0), (1, 0))).cumsum(axis=0).cumsum(axis=1)
765 counts = (summed[side:, side:] - summed[:-side, side:]
766 - summed[side:, :-side] + summed[:-side, :-side])
767 return not np.any(counts == side * side)
770def collect_small_islands(region, target_mask, max_width):
771 """角で直接接する細い空白だけをたどる。線の画素は飛び越さない。
773 上下左右の接続は通常のバケツが処理済み。追加するのは斜め接続だけ。
774 max_width は拾う隙間の幅の上限で、探索距離は常に1画素とする。
775 """
776 if max_width <= 0 or not region.any():
777 return region
778 touching = dilate(region, 1) & target_mask & ~region
779 if not touching.any():
780 return region
781 index = _RegionIndex(target_mask)
782 labels = index.labels
783 height, width = region.shape
784 result = region.copy()
785 visited = set(int(value) for value in np.unique(labels[region & target_mask]))
786 pending = [int(value) for value in np.unique(labels[touching])]
787 while pending:
788 label = pending.pop()
789 if label in visited:
790 continue
791 visited.add(label)
792 x0, y0, x1, y1 = (int(values[label]) for values in
793 (index.x0, index.y0, index.x1, index.y1))
794 if x0 == 0 or y0 == 0 or x1 == width or y1 == height:
795 continue
796 local = labels[y0:y1, x0:x1] == label
797 if not _island_fits_width(local, max_width):
798 continue
799 result[y0:y1, x0:x1] |= local
800 ax0, ay0 = max(0, x0 - 1), max(0, y0 - 1)
801 ax1, ay1 = min(width, x1 + 1), min(height, y1 + 1)
802 part = labels[ay0:ay1, ax0:ax1]
803 touching = dilate(part == label, 1) & target_mask[ay0:ay1, ax0:ax1]
804 pending.extend(int(value) for value in np.unique(part[touching])
805 if int(value) not in visited)
806 return result
809def _prepare_bucket(pixels, category, options, pseudo_background, selection_mask, line_cache):
810 packed = rgba_packed_view(pixels)
811 if options.target_color == TARGET_ALL:
812 target_mask = (
813 pseudo_background.copy() if category is None
814 else opaque_rgb_mask_packed(packed, category)
815 )
816 else:
817 target_mask = fill_target_mask(pixels, options.target_color, category, packed)
818 if selection_mask is not None:
819 target_mask &= selection_mask
820 gap_recovery_mask = None
821 passable = None
822 if options.adjacent:
823 boundary = ~target_mask
824 if options.extend_lines:
825 extension = extend_line_ends(boundary, options.extend_length, cache=line_cache)
826 if extension.any():
827 boundary = boundary | extension
828 gap_recovery_mask = extension
829 if options.close_gap:
830 gap_radius = max(1, int(options.gap_width))
831 virtual_boundary = erode(dilate(boundary, gap_radius), gap_radius)
832 # 収縮はキャンバス外を空白として扱うため、端まで延長した線も
833 # 削ってしまう。元の境界を残して端からの漏れを防ぐ。
834 virtual_boundary |= boundary
835 gap_recovery_mask = virtual_boundary & target_mask
836 else:
837 virtual_boundary = boundary
838 passable = target_mask & ~virtual_boundary
839 if selection_mask is not None:
840 passable &= selection_mask
841 return target_mask, passable, gap_recovery_mask
844def compute_fill_region(
845 pixels,
846 start_x,
847 start_y,
848 options: BucketOptions,
849 selection_mask=None,
850 *,
851 line_cache=None,
852 session=None,
853) -> FillResult:
854 """``(start_x, start_y)`` から塗る画素の真偽マスクを求める。
856 :param pixels: ``(height, width, 4)`` の RGBA8888 配列。読み取りのみ。
857 :param selection_mask: 選択範囲の真偽マスク。``None`` なら制限なし。
858 :param line_cache: 同じドラッグ内で共有する線端下処理のキャッシュ。
859 :param session: 変更しない同じ画像・設定で前処理を再利用する場合に指定する。
860 """
861 height, width = pixels.shape[:2]
862 if not (0 <= start_x < width and 0 <= start_y < height):
863 return FillResult(REASON_OUT_OF_BOUNDS)
864 if selection_mask is not None and not selection_mask[start_y, start_x]:
865 return FillResult(REASON_OUTSIDE_SELECTION)
867 category = seed_category(pixels, start_x, start_y)
868 # RGBA を uint32 にまとめて比較する（チャンネルごとの np.all より
869 # 1桁以上速く、一時配列も小さい）。
870 if session is not None:
871 if session.pixels is not pixels or session.options != options or selection_mask is not None: 871 ↛ 872line 871 didn't jump to line 872 because the condition on line 871 was never true
872 raise ValueError("BucketSession requires its original image, options and no selection")
873 pseudo_background = session.background
874 target_mask, passable, gap_recovery_mask = session.prepare(category)
875 else:
876 pseudo_background = background_mask_packed(rgba_packed_view(pixels))
877 target_mask, passable, gap_recovery_mask = _prepare_bucket(
878 pixels, category, options, pseudo_background, selection_mask, line_cache,
879 )
880 target_color = options.target_color
881 if not target_mask[start_y, start_x]:
882 return FillResult(REASON_NOT_TARGET, target=category)
884 if options.adjacent:
885 assert passable is not None
886 # 仮想境界上をクリックした場合だけ、その画素を探索開始点として回収する。
887 # 共通前処理の配列は書き換えず、次のクリックにも同じ境界を使う。
888 indexed_region = None
889 if session is not None and session.indexed and passable[start_y, start_x]:
890 indexed_region = session.index(category, passable).region(start_x, start_y)
891 elif not passable[start_y, start_x]:
892 passable = passable.copy()
893 passable[start_y, start_x] = True
894 region = (indexed_region if indexed_region is not None
895 else scanline_connected_region(passable, (start_x, start_y)))
897 if region is None: 897 ↛ 898line 897 didn't jump to line 898 because the condition on line 897 was never true
898 return FillResult(REASON_EMPTY, target=category)
900 if not region[start_y, start_x]: 900 ↛ 901line 900 didn't jump to line 901 because the condition on line 900 was never true
901 return FillResult(REASON_EMPTY, target=category)
903 # 選択範囲そのものが閉じた境界として働くので、そのときは判定しない。
904 if selection_mask is None and options.require_closed and (
905 np.any(region[0, :])
906 or np.any(region[-1, :])
907 or np.any(region[:, 0])
908 or np.any(region[:, -1])
909 ):
910 # 塗らないが、どこまで開いていたかは返す（ドラッグ塗りが同じ領域を
911 # 何度も判定しないため）。ok は偽のまま。
912 return FillResult(REASON_OPEN_REGION, region=region, target=category)
914 if gap_recovery_mask is not None:
915 # 接点は領域の外接矩形の1画素外までに限られる。小さな面のたびに
916 # キャンバス全体を膨張・座標列挙しない。回収の探索先は元の全体マスク。
917 region_bounds = mask_bounds(region)
918 if region_bounds is None: 918 ↛ 919line 918 didn't jump to line 919 because the condition on line 918 was never true
919 return FillResult(REASON_EMPTY, target=category)
920 rx0, ry0, rx1, ry1 = region_bounds
921 gx0, gy0 = max(0, rx0 - 1), max(0, ry0 - 1)
922 gx1, gy1 = min(width, rx1 + 1), min(height, ry1 + 1)
923 touching = dilate(region[gy0:gy1, gx0:gx1], 1)
924 touching &= gap_recovery_mask[gy0:gy1, gx0:gx1]
925 start_y_values, start_x_values = np.nonzero(touching)
926 if start_x_values.size:
927 recovered = scanline_connected_region(
928 gap_recovery_mask,
929 zip((start_x_values + gx0).tolist(), (start_y_values + gy0).tolist()),
930 )
931 region |= recovered
933 # 閉じ込められた穴・島も一緒に塗る対象色。
934 if target_color == TARGET_OPAQUE_AND_INNER_TRANSPARENT:
935 region |= _enclosed_by(region) & (pixels[:, :, 3] == 0)
936 elif target_color == TARGET_TRANSPARENT_AND_CLOSED_OPAQUE:
937 region |= _enclosed_by(region) & (pixels[:, :, 3] != 0)
938 else:
939 # 「隣接」OFFでは、対象色の画素（既定はクリック位置と同じ色）を一括で塗る。
940 region = target_mask
942 final_region = region.copy()
943 if options.include_masks:
944 opaque_pixels = pixels[:, :, 3] > 0
945 mask_family = np.zeros((height, width), dtype=bool)
946 for mask_color in options.mask_colors:
947 # (h, w, 3) の int32 配列を作らず、チャンネルごとに距離を足す。
948 distance = np.zeros((height, width), dtype=np.int32)
949 for channel, value in enumerate(mask_color):
950 delta = pixels[:, :, channel].astype(np.int32)
951 delta -= int(value)
952 delta *= delta
953 distance += delta
954 mask_family |= opaque_pixels & (distance <= 56 * 56)
955 if options.include_background_mask: 955 ↛ 956line 955 didn't jump to line 956 because the condition on line 955 was never true
956 mask_family |= pseudo_background
957 if selection_mask is not None: 957 ↛ 958line 957 didn't jump to line 958 because the condition on line 957 was never true
958 mask_family &= selection_mask
960 if options.adjacent: 960 ↛ 974line 960 didn't jump to line 974 because the condition on line 960 was always true
961 adjacent = np.zeros_like(region)
962 adjacent[1:, :] |= region[:-1, :]
963 adjacent[:-1, :] |= region[1:, :]
964 adjacent[:, 1:] |= region[:, :-1]
965 adjacent[:, :-1] |= region[:, 1:]
966 seed_points = np.argwhere(mask_family & adjacent)
967 if seed_points.size:
968 starts = [
969 (int(point[1]), int(point[0])) for point in seed_points
970 ]
971 final_region |= scanline_connected_region(mask_family, starts)
972 else:
973 # 非隣接モードでは、含み塗りの対象色もレイヤー全体から一括対象にする。
974 final_region |= mask_family
976 if options.adjacent and options.island_max_width > 0:
977 final_region = collect_small_islands(final_region, target_mask, options.island_max_width)
978 if selection_mask is not None:
979 final_region &= selection_mask
980 bounds = mask_bounds(final_region)
981 if bounds is None: 981 ↛ 982line 981 didn't jump to line 982 because the condition on line 981 was never true
982 return FillResult(REASON_EMPTY, target=category)
983 islands = ()
984 if options.island_replacements:
985 islands = enclosed_islands(
986 pixels, final_region, options.island_replacements, selection_mask
987 )
988 # 島は塗る範囲の縁からはみ出すことがある。書き込み・Undo の矩形に含める。
989 for _rgb, island in islands:
990 island_bounds = mask_bounds(island)
991 assert island_bounds is not None # 空の島は enclosed_islands が返さない
992 ix0, iy0, ix1, iy1 = island_bounds
993 bounds = (
994 min(bounds[0], ix0), min(bounds[1], iy0),
995 max(bounds[2], ix1), max(bounds[3], iy1),
996 )
997 return FillResult(
998 REASON_OK, final_region, target=category, bounds=bounds, islands=islands
999 )
1002#: 島とみなすのに、まわりのうち塗った範囲が占める割合の下限。
1003#: 頬の斜線は端が黒線や範囲線に触れることがあるので、すべてとは求めない。
1004ISLAND_MIN_SHARE = 0.6
1007def enclosed_islands(
1008 pixels, region, replacements, selection_mask=None,
1009 min_share=ISLAND_MIN_SHARE,
1010):
1011 """``region`` に囲まれた、置換色のある色の島を探す。
1013 頬の範囲線の中を塗ったとき、中の赤い斜線を別の色にしたい。斜線は塗る範囲の
1014 外（違う色）なので、塗りだけでは残る。置換色を登録してある色のつながった
1015 部分のうち、まわり（1画素外側）の ``min_share`` 以上が塗る範囲のものを島とする。
1017 :param replacements: ``((元の RGB, 塗り替える RGB), ...)``。
1018 :returns: ``((塗り替える RGB, マスク), ...)``。
1019 """
1020 bounds = mask_bounds(region)
1021 if bounds is None or not replacements:
1022 return ()
1023 height, width = region.shape
1024 x0, y0, x1, y1 = bounds
1025 # 島は塗る範囲に囲まれているので、外接矩形の少し外までを見れば足りる。
1026 x0, y0 = max(0, x0 - 1), max(0, y0 - 1)
1027 x1, y1 = min(width, x1 + 1), min(height, y1 + 1)
1028 local_region = region[y0:y1, x0:x1]
1029 local_pixels = pixels[y0:y1, x0:x1]
1030 packed = rgba_packed_view(local_pixels)
1031 near = dilate(local_region, 1) & ~local_region
1032 islands = []
1033 for source, destination in replacements:
1034 source = tuple(int(value) for value in source[:3])
1035 destination = tuple(int(value) for value in destination[:3])
1036 if source == destination: 1036 ↛ 1037line 1036 didn't jump to line 1037 because the condition on line 1036 was never true
1037 continue
1038 candidates = opaque_rgb_mask_packed(packed, source) & near
1039 if selection_mask is not None: 1039 ↛ 1040line 1039 didn't jump to line 1040 because the condition on line 1039 was never true
1040 candidates &= selection_mask[y0:y1, x0:x1]
1041 if not candidates.any():
1042 continue
1043 color = opaque_rgb_mask_packed(packed, source)
1044 chosen = np.zeros_like(local_region)
1045 remaining = candidates.copy()
1046 while remaining.any():
1047 start_y, start_x = (int(value) for value in np.argwhere(remaining)[0])
1048 part = scanline_connected_region(color, (start_x, start_y))
1049 remaining &= ~part
1050 border = dilate(part, 1) & ~part
1051 total = int(np.count_nonzero(border))
1052 inside = int(np.count_nonzero(border & local_region))
1053 if total and inside / total >= min_share:
1054 chosen |= part
1055 if selection_mask is not None: 1055 ↛ 1056line 1055 didn't jump to line 1056 because the condition on line 1055 was never true
1056 chosen &= selection_mask[y0:y1, x0:x1]
1057 if chosen.any():
1058 mask = np.zeros_like(region)
1059 mask[y0:y1, x0:x1] = chosen
1060 islands.append((destination, mask))
1061 return tuple(islands)
1064#: 追跡で試す開始点の数の上限（1回ごとに領域判定が1回走る）。
1065TRACK_MAX_TRIES = 8
1066#: 前のコマの領域との重なり（IoU）がこれ未満なら、推測としても出さない。
1067TRACK_MIN_IOU = 0.1
1068#: これ以上重なっていれば、残りの候補を試さずに採用する。
1069TRACK_GOOD_IOU = 0.75
1070#: 前のコマの領域との面積比がこの倍率を超えたら別物（背景への漏れなど）とみなす。
1071TRACK_MAX_AREA_RATIO = 3.0
1072#: 候補の面積のうち、前のコマの範囲に収まっている割合がこれ以上なら、
1073#: 前のコマの領域が分かれた一部とみなしてまとめて塗る。
1074TRACK_INCLUDE_RATIO = 0.7
1075#: これ以下の面積（px）の図形は、重なりで見つからなければ、まわりの色の並びでも探す
1076#: （:func:`fill_tracking.context_similarity`）。点や星の中心など。
1077TRACK_SMALL_AREA = 2500
1078#: 小さい図形を探すとき、動かした位置からどこまで離れた画素を種にするか（px）。
1079TRACK_SMALL_REACH = 6
1080#: 小さい図形を探すとき、ずれの候補1つあたりに試す種の数の上限。
1081TRACK_SMALL_SEEDS = 6
1082#: まわりの色の並びで見つけた図形は、重なりで見つけたものより取り違えやすい
1083#: （似た形の別の部分を拾うことがある）。重なりと同じ物差しで扱えるよう、
1084#: 似ている度合いからこれだけ引いて ``score`` にする。
1085TRACK_CONTEXT_PENALTY = 0.1
1088def track_fill_region(
1089 pixels,
1090 previous,
1091 reference,
1092 options: BucketOptions,
1093 selection_mask=None,
1094 previous_pixels=None,
1095 previous_lines=None,
1096) -> FillResult:
1097 """前のコマで塗った領域 ``previous`` を手がかりに、このコマで同じ図形を塗る。
1099 1. ``previous_pixels``（前のコマの画素）があれば、塗った範囲のまわりの線画を
1100 比べて、図形がどれだけ動いたかを推定し（:mod:`fill_tracking`）、前の範囲を
1101 そのぶん動かす。区画ごとにずらした範囲（回転や一部だけの動き用）も作る。
1102 2. 動かした範囲（と、推定が外れたときのために元の位置）と重なる閉じた領域を
1103 候補にして、塗ってみる。
1104 3. 重なり（IoU）が一番大きく、面積も大きく変わらない領域を選ぶ。背景へ漏れた
1105 領域は面積が跳ね上がるので弾かれる。
1106 4. シワや重なりで前のコマの1つの領域が今のコマでは何個かに分かれていると、
1107 どの1つも重なりが小さい。そこで、ほとんどが前の範囲に収まっている
1108 （前の範囲に「含まれる」）候補をまとめた範囲も比べ、重なりが大きければ
1109 そちらを採る。
1111 :param previous: 前のコマ（追跡の1つ手前）で塗った画素の真偽マスク。
1112 :param reference: 塗り始めたコマの開始点の色種別（:func:`seed_category`）。
1113 :param previous_pixels: ``previous`` を作ったコマの RGBA 配列。省略時はずれを推定しない。
1114 :param previous_lines: 前のコマの線画（塗りを止める画素）の真偽マスク。
1115 省略時は ``previous_pixels`` から対象色の設定で求める。
1116 :returns: 結果の ``score`` に重なりを入れる。自信がなくても候補があれば ok で返し、
1117 採用するかは呼び出し側が ``score`` で決める。候補が無ければ ``REASON_EMPTY``。
1118 """
1119 from . import fill_tracking
1121 previous_area = int(np.count_nonzero(previous))
1122 if previous_area == 0: 1122 ↛ 1123line 1122 didn't jump to line 1123 because the condition on line 1122 was never true
1123 return FillResult(REASON_EMPTY, target=reference)
1124 # 種の候補は、対象色の設定でたどれる画素（既定は開始点と同じ色）に限る。
1125 target = fill_target_mask(pixels, options.target_color, reference)
1126 if selection_mask is not None: 1126 ↛ 1127line 1126 didn't jump to line 1127 because the condition on line 1126 was never true
1127 target &= selection_mask
1129 references = [previous]
1130 if ( 1130 ↛ 1138line 1130 didn't jump to line 1138 because the condition on line 1130 was always true
1131 previous_lines is None
1132 and previous_pixels is not None
1133 and previous_pixels.shape == pixels.shape
1134 ):
1135 previous_lines = ~fill_target_mask(
1136 previous_pixels, options.target_color, reference
1137 )
1138 if previous_lines is not None and previous_lines.shape == previous.shape: 1138 ↛ 1152line 1138 didn't jump to line 1152 because the condition on line 1138 was always true
1139 current_lines = ~target
1140 shifts = fill_tracking.estimate_shifts(previous_lines, current_lines, previous)
1141 # 動かした位置を先に試す。推定が外れたときのために元の位置も残す。
1142 moved = [
1143 fill_tracking.shift_mask(previous, dy, dx)
1144 for dy, dx in shifts if dy or dx
1145 ]
1146 warped = fill_tracking.warp_region(
1147 previous_lines, current_lines, previous,
1148 shifts[0] if shifts else (0, 0),
1149 )
1150 references = ([warped] if warped is not None else []) + moved + references
1152 eligible = np.zeros(target.shape, dtype=bool)
1153 for reference_mask in references:
1154 eligible |= target & reference_mask
1155 # 動かした範囲がキャンバスの外へ出てしまったときは、元の範囲の重心を使う。
1156 lead = references[0] if references[0].any() else previous
1157 center_y, center_x = (float(value) for value in np.argwhere(lead).mean(axis=0))
1158 reference_areas = [int(np.count_nonzero(mask)) for mask in references]
1160 def iou_with(mask, area, index):
1161 overlap = int(np.count_nonzero(mask & references[index]))
1162 return overlap / max(1, area + reference_areas[index] - overlap)
1164 # (結果, 面積, 手がかりごとの重なりの画素数)
1165 candidates = []
1166 best: Optional[FillResult] = None
1167 best_iou = 0.0
1168 for _attempt in range(TRACK_MAX_TRIES): 1168 ↛ 1213line 1168 didn't jump to line 1213 because the loop on line 1168 didn't complete
1169 points = np.argwhere(eligible)
1170 if not len(points):
1171 break
1172 ys, xs = points[:, 0], points[:, 1]
1173 # 動かした範囲の重心に近い点から試す。
1174 nearest = int(np.argmin((ys - center_y) ** 2 + (xs - center_x) ** 2))
1175 start_x, start_y = int(xs[nearest]), int(ys[nearest])
1176 result = compute_fill_region(
1177 pixels, start_x, start_y, options, selection_mask
1178 )
1179 if not result.ok: 1179 ↛ 1181line 1179 didn't jump to line 1181 because the condition on line 1179 was never true
1180 # 同じ領域から何度も試さないよう、その連続部分ごと候補から外す。
1181 eligible &= ~scanline_connected_region(
1182 eligible.copy(), (start_x, start_y)
1183 )
1184 continue
1185 region = result.mask
1186 eligible &= ~region
1187 area = int(np.count_nonzero(region))
1188 ratio = area / previous_area
1189 if ratio > TRACK_MAX_AREA_RATIO:
1190 continue
1191 overlaps = [
1192 int(np.count_nonzero(region & reference_mask))
1193 for reference_mask in references
1194 ]
1195 candidates.append((result, area, overlaps))
1196 if ratio < 1.0 / TRACK_MAX_AREA_RATIO: 1196 ↛ 1198line 1196 didn't jump to line 1198 because the condition on line 1196 was never true
1197 # 1つだけでは小さすぎるが、分かれた一部としてはまとめる候補に残す。
1198 continue
1199 iou, matched = 0.0, None
1200 for reference_mask, reference_area, overlap in zip(
1201 references, reference_areas, overlaps
1202 ):
1203 value = overlap / max(1, area + reference_area - overlap)
1204 if value > iou:
1205 iou, matched = value, reference_mask
1206 if iou > best_iou:
1207 result.matched = matched
1208 best, best_iou = result, iou
1209 if iou >= TRACK_GOOD_IOU:
1210 break
1212 # 分かれた領域をまとめた範囲。手がかり（動かし方）ごとに作って比べる。
1213 if best_iou < TRACK_GOOD_IOU:
1214 for index in range(len(references)):
1215 members = [
1216 result for result, area, overlaps in candidates
1217 if overlaps[index] >= area * TRACK_INCLUDE_RATIO
1218 ]
1219 if len(members) < 2:
1220 continue
1221 union = np.zeros(target.shape, dtype=bool)
1222 for result in members:
1223 union |= result.mask
1224 iou = iou_with(union, int(np.count_nonzero(union)), index)
1225 if iou > best_iou:
1226 best_iou = iou
1227 best = FillResult(
1228 REASON_OK, union, target=reference, bounds=mask_bounds(union),
1229 islands=tuple(
1230 island for result in members for island in result.islands
1231 ),
1232 matched=references[index],
1233 )
1234 if (
1235 previous_pixels is not None
1236 and previous_pixels.shape == pixels.shape
1237 and previous_area <= TRACK_SMALL_AREA
1238 and best_iou < TRACK_GOOD_IOU
1239 ):
1240 rescued = _track_small_region(
1241 pixels, previous, previous_pixels, target, options, selection_mask
1242 )
1243 if rescued is not None and rescued.score is not None and rescued.score > best_iou: 1243 ↛ 1244line 1243 didn't jump to line 1244 because the condition on line 1243 was never true
1244 best, best_iou = rescued, float(rescued.score)
1245 if best is None or best_iou < TRACK_MIN_IOU:
1246 return FillResult(REASON_EMPTY, target=reference, score=best_iou)
1247 best.score = best_iou
1248 return best
1251def _shift_candidates(previous_pixels, pixels, previous):
1252 """前のコマから今のコマへの、ずれの候補（重複なし、``(0, 0)`` を含む）。
1254 主線の縁の重なりと、まわりの色の並びの2通りで推定する。
1255 """
1256 from . import fill_tracking
1258 shifts = fill_tracking.estimate_shifts(
1259 fill_tracking.line_art(previous_pixels),
1260 fill_tracking.line_art(pixels),
1261 previous,
1262 )
1263 shifts += fill_tracking.estimate_color_shifts(previous_pixels, pixels, previous)
1264 shifts.append((0, 0))
1265 return list(dict.fromkeys(shifts))
1268def _track_small_region(pixels, previous, previous_pixels, target, options, selection_mask):
1269 """小さい図形を、まわりの色の並びが一番似ている閉じた領域として探す。
1271 ``score`` には :func:`fill_tracking.context_similarity` の値から
1272 :data:`TRACK_CONTEXT_PENALTY` を引いた値を入れる。
1273 """
1274 from . import fill_tracking
1276 previous_area = int(np.count_nonzero(previous))
1277 height, width = previous.shape
1278 tried = np.zeros_like(target)
1279 best: Optional[FillResult] = None
1280 best_score = 0.0
1281 for dy, dx in _shift_candidates(previous_pixels, pixels, previous):
1282 moved = fill_tracking.shift_mask(previous, dy, dx)
1283 bounds = mask_bounds(moved)
1284 if bounds is None: 1284 ↛ 1285line 1284 didn't jump to line 1285 because the condition on line 1284 was never true
1285 continue
1286 x0, y0, x1, y1 = bounds
1287 reach = TRACK_SMALL_REACH
1288 x0, y0 = max(0, x0 - reach), max(0, y0 - reach)
1289 x1, y1 = min(width, x1 + reach), min(height, y1 + reach)
1290 near = (
1291 dilate(moved[y0:y1, x0:x1], reach)
1292 & target[y0:y1, x0:x1]
1293 & ~tried[y0:y1, x0:x1]
1294 )
1295 points = np.argwhere(near)
1296 if not len(points):
1297 continue
1298 center_y, center_x = np.argwhere(moved).mean(axis=0)
1299 order = np.argsort(
1300 (points[:, 0] + y0 - center_y) ** 2 + (points[:, 1] + x0 - center_x) ** 2
1301 )
1302 seeds = 0
1303 for index in order:
1304 start_y, start_x = int(points[index][0]) + y0, int(points[index][1]) + x0
1305 if tried[start_y, start_x]:
1306 continue
1307 seeds += 1
1308 result = compute_fill_region(
1309 pixels, start_x, start_y, options, selection_mask
1310 )
1311 if not result.ok: 1311 ↛ 1312line 1311 didn't jump to line 1312 because the condition on line 1311 was never true
1312 tried[start_y, start_x] = True
1313 else:
1314 tried |= result.mask
1315 ratio = int(np.count_nonzero(result.mask)) / max(1, previous_area)
1316 if 1.0 / TRACK_MAX_AREA_RATIO <= ratio <= TRACK_MAX_AREA_RATIO:
1317 score = fill_tracking.context_similarity(
1318 previous_pixels, previous, pixels, result.mask
1319 )
1320 if score > best_score: 1320 ↛ 1323line 1320 didn't jump to line 1323 because the condition on line 1320 was always true
1321 result.matched = moved
1322 best, best_score = result, score
1323 if seeds >= TRACK_SMALL_SEEDS: 1323 ↛ 1324line 1323 didn't jump to line 1324 because the condition on line 1323 was never true
1324 break
1325 if best is not None:
1326 best.score = max(0.0, best_score - TRACK_CONTEXT_PENALTY)
1327 return best
1330def guess_target_categories(pixels, previous, previous_pixels, count=2):
1331 """``previous`` の図形が今のコマで何色の上にあるか、候補を多い順に返す。
1333 見本のコマで塗った図形を、まだ塗っていない（あるいは違う色で塗った）コマへ
1334 塗り写すときに、そのコマでたどる色（:func:`seed_category` と同じ形、背景は
1335 ``None``）を決めるのに使う。ずれの候補ごとに動かした範囲の下の色（主線を除く）を
1336 数え、一番多い色の割合を票として足す。
1337 """
1338 from . import fill_tracking
1340 lines = fill_tracking.line_art(pixels)
1341 votes = {}
1342 for dy, dx in _shift_candidates(previous_pixels, pixels, previous):
1343 moved = fill_tracking.shift_mask(previous, dy, dx) & ~lines
1344 sample = pixels[moved]
1345 if not len(sample):
1346 continue
1347 background = (sample[:, 3] == 0) | np.all(sample[:, :3] == 255, axis=1)
1348 keys = np.where(
1349 background,
1350 -1,
1351 (sample[:, 0].astype(np.int64) << 16)
1352 | (sample[:, 1].astype(np.int64) << 8)
1353 | sample[:, 2].astype(np.int64),
1354 )
1355 values, counts = np.unique(keys, return_counts=True)
1356 top = int(np.argmax(counts))
1357 votes[int(values[top])] = votes.get(int(values[top]), 0.0) + counts[top] / len(keys)
1358 ranked = sorted(votes, key=lambda key: -votes[key])[:count]
1359 return [
1360 None if key < 0 else ((key >> 16) & 255, (key >> 8) & 255, key & 255)
1361 for key in ranked
1362 ]