Coverage for paintmaskanimator/fill_tracking.py: 90%
253 statements
« prev ^ index » next coverage.py v7.17.0, created at 2026-11-02 04:50 +0000
« prev ^ index » next coverage.py v7.17.0, created at 2026-11-02 04:50 +0000
1"""串刺し塗りの追跡で使う、コマ間のずれの推定(UI 非依存)。
3前のコマで塗った範囲と今のコマの図形が重なっていることを前提にすると、
4図形がその幅ほど動いたコマで追跡が切れる。そこで、塗った範囲のまわりの
5線画(塗る対象でない画素)を前のコマと今のコマで比べ、どれだけずれたかを
6位相相関で求める。前の範囲をそのぶん動かしてから比べれば、大きく動いても
7重なりが保てる。
9図形は平行移動するだけでなく、回転したり一部だけ動いたりもする(腕を振る、
10髪がなびくなど)。全体を1つのずれで動かすと片側しか合わないので、
11:func:`warp_region` で範囲を区画に分け、区画ごとのずれで動かした範囲も作る
12(動きの推定を画素ごとに行う方法の、軽い近似)。
14numpy 配列だけを扱う純粋な関数にしてあるので、あとで Rust の部品に置き換えやすい
15(``docs/design-principles.md``「将来は Rust へ置き換えていく」)。
16"""
17from __future__ import annotations
19from typing import Optional, Tuple
21import numpy as np
23#: ずれを数える窓の一辺の上限。これより大きい窓は間引いて計算する。
24#: ずれは粗くてよい(最後は実際に塗って重なりで選ぶ)ので、速さを優先する。
25_MAX_WINDOW = 256
27#: :func:`warp_region` の区画の一辺の目安(px)。範囲がこれより小さい向きは分けない。
28LOCAL_TILE = 32
29#: 1つの向きに分ける区画の数の上限。
30LOCAL_MAX_TILES = 6
31#: 区画ごとに探す、全体のずれからの追加のずれの範囲(px)。範囲の大きさの
32#: 1/4 を目安に、この間に収める。全体のずれは範囲の片側に合っていることが
33#: あるので、反対側の区画はそのぶん大きくずれている。
34LOCAL_MIN_RADIUS = 6
35LOCAL_MAX_RADIUS = 64
36#: 区画の縁の線がこれより少ないと、ずれを測れないので全体のずれを使う。
37LOCAL_MIN_TEMPLATE = 6
38#: 相関の山の高さが一番高い山のこの割合以上なら同じくらいそれらしいとみなし、
39#: ずれの小さいものを選ぶ。まっすぐな線は線に沿ったずれが決まらず、同じ形が
40#: 並んでいると同じ高さの山がいくつも出るため。
41PEAK_TOLERANCE = 0.9
44def mask_bounds(mask) -> Optional[Tuple[int, int, int, int]]:
45 """真の画素を囲む ``(x0, y0, x1, y1)``(x1, y1 は排他)。無ければ None。"""
46 rows = np.flatnonzero(mask.any(axis=1))
47 if not rows.size:
48 return None
49 cols = np.flatnonzero(mask.any(axis=0))
50 return int(cols[0]), int(rows[0]), int(cols[-1]) + 1, int(rows[-1]) + 1
53def shift_mask(mask, dy, dx):
54 """``mask`` を (dy, dx) だけ動かす。はみ出した分は捨て、空いた所は偽。"""
55 height, width = mask.shape
56 out = np.zeros_like(mask)
57 if abs(dy) >= height or abs(dx) >= width:
58 return out
59 src_y = slice(max(0, -dy), height - max(0, dy))
60 dst_y = slice(max(0, dy), height - max(0, -dy))
61 src_x = slice(max(0, -dx), width - max(0, dx))
62 dst_x = slice(max(0, dx), width - max(0, -dx))
63 out[dst_y, dst_x] = mask[src_y, src_x]
64 return out
67def _outline(region, lines, width=3):
68 """``region`` の縁に接する線画だけを残す(遠くの動かない線を比べないため)。"""
69 from .bucket_fill import dilate
71 return lines & dilate(region, width) & ~region
74def estimate_shifts(previous_lines, current_lines, region, count=3, margin=None):
75 """``region`` の縁の線画が、前のコマから今のコマへどれだけ動いたかの候補。
77 相関の山の高い順に ``count`` 個まで ``(dy, dx)`` を返す(一番高い山とほぼ同じ
78 高さの山どうしは、ずれの小さい順)。図形の縁の線
79 (塗った範囲に接する線)だけを型にするので、近くにある動かない線に
80 引きずられにくい。どれが正しいかは、呼び出し側が実際に塗って比べて決める。
82 :param previous_lines: 前のコマの線画(塗る対象でない画素)の真偽マスク。
83 :param current_lines: 今のコマの線画の真偽マスク。
84 :param region: 前のコマで塗った範囲。
85 :param margin: 探すずれの最大。省略時は範囲の大きさの3倍。
86 """
87 bounds = mask_bounds(region)
88 if bounds is None:
89 return []
90 height, width = region.shape
91 x0, y0, x1, y1 = bounds
92 if margin is None: 92 ↛ 94line 92 didn't jump to line 94 because the condition on line 92 was always true
93 margin = max(64, int(max(x1 - x0, y1 - y0) * 3))
94 wx0, wy0 = max(0, x0 - margin), max(0, y0 - margin)
95 wx1, wy1 = min(width, x1 + margin), min(height, y1 + margin)
96 if wx1 - wx0 < 8 or wy1 - wy0 < 8: 96 ↛ 97line 96 didn't jump to line 97 because the condition on line 96 was never true
97 return []
98 template = _outline(region, previous_lines)
99 step = max(1, int(np.ceil(max(wx1 - wx0, wy1 - wy0) / _MAX_WINDOW)))
100 before = _downsample(template[wy0:wy1, wx0:wx1], step)
101 after = _downsample(current_lines[wy0:wy1, wx0:wx1], step)
102 if not before.any() or not after.any(): 102 ↛ 103line 102 didn't jump to line 103 because the condition on line 102 was never true
103 return []
104 correlation, size = _correlate(before, after)
105 limit_y, limit_x = margin // step, margin // step
106 # (山の高さ, ずれ)。同じ形が並んでいると同じ高さの山がいくつも出るので、
107 # 多めに集めてから選ぶ。
108 peaks = []
109 for _ in range(count * 4):
110 peak_y, peak_x = np.unravel_index(int(np.argmax(correlation)), correlation.shape)
111 height_value = float(correlation[peak_y, peak_x])
112 if height_value <= 0: 112 ↛ 113line 112 didn't jump to line 113 because the condition on line 112 was never true
113 break
114 dy = int(peak_y) - size[0] if peak_y >= size[0] // 2 else int(peak_y)
115 dx = int(peak_x) - size[1] if peak_x >= size[1] // 2 else int(peak_x)
116 # 同じ山の近くを次の候補にしないよう、まわりを消しておく。
117 for y in range(peak_y - 2, peak_y + 3):
118 for x in range(peak_x - 2, peak_x + 3):
119 correlation[y % size[0], x % size[1]] = -np.inf
120 if abs(dy) <= limit_y and abs(dx) <= limit_x: 120 ↛ 109line 120 didn't jump to line 109 because the condition on line 120 was always true
121 peaks.append((height_value, (dy * step, dx * step)))
122 if not peaks: 122 ↛ 123line 122 didn't jump to line 123 because the condition on line 122 was never true
123 return []
124 # 一番高い山とほぼ同じ高さの山(同じ形の隣の図形など)が並ぶときは、
125 # 動きの小さいものを先にする。コマ間の動きは小さいほうがそれらしい。
126 top = peaks[0][0]
127 near = [shift for value, shift in peaks if value >= top * PEAK_TOLERANCE]
128 rest = [shift for value, shift in peaks if value < top * PEAK_TOLERANCE]
129 near.sort(key=lambda shift: shift[0] ** 2 + shift[1] ** 2)
130 return (near + rest)[:count]
133def _downsample(mask, step):
134 """``step`` 画素四方ごとに、1つでも真なら真にして縮める(float32)。
136 1画素おきに間引くと、1画素幅の線が消えたり残ったりしてずれが測れなくなる。
137 """
138 if step <= 1:
139 return mask.astype(np.float32)
140 rows, cols = mask.shape
141 padded = np.zeros((-(-rows // step) * step, -(-cols // step) * step), dtype=bool)
142 padded[:rows, :cols] = mask
143 blocks = padded.reshape(padded.shape[0] // step, step, padded.shape[1] // step, step)
144 return blocks.any(axis=(1, 3)).astype(np.float32)
147def _fast_length(n):
148 """``n`` 以上で、素因数が 2・3・5 だけの長さ(FFT が速い長さ)。"""
149 n = max(1, int(n))
150 while True:
151 m = n
152 for factor in (2, 3, 5):
153 while m % factor == 0:
154 m //= factor
155 if m == 1:
156 return n
157 n += 1
160def _correlate(before, after, reach=None):
161 """``after`` が ``before`` からどれだけずれると一番重なるかの相関の表。
163 線画は「線か、線でないか」の2値なので、輪郭と今のコマの線が一番多く
164 重なるずれを数える(相互相関)。ゼロで埋めて広げ、回り込みを防ぐ。
165 表の添字 ``(i, j)`` は、サイズの半分以上なら負のずれを表す。
167 :param reach: 調べるずれの最大。指定すると、そのぶんだけ広げる(速い)。
168 """
169 rows, cols = before.shape
170 if reach is None:
171 size = (2 * rows, 2 * cols)
172 else:
173 size = (_fast_length(rows + 2 * reach + 1), _fast_length(cols + 2 * reach + 1))
174 correlation = np.fft.irfft2(
175 np.fft.rfft2(after, size) * np.conj(np.fft.rfft2(before, size)), size
176 )
177 return correlation, size
180def _crop(mask, y0, y1, x0, x1):
181 """``mask[y0:y1, x0:x1]`` を切り出す。キャンバスの外は偽で埋める。"""
182 height, width = mask.shape
183 out = np.zeros((y1 - y0, x1 - x0), dtype=bool)
184 sy0, sy1 = max(0, y0), min(height, y1)
185 sx0, sx1 = max(0, x0), min(width, x1)
186 if sy0 < sy1 and sx0 < sx1: 186 ↛ 188line 186 didn't jump to line 188 because the condition on line 186 was always true
187 out[sy0 - y0:sy1 - y0, sx0 - x0:sx1 - x0] = mask[sy0:sy1, sx0:sx1]
188 return out
191def _paste(out, part, y, x):
192 """``part`` を ``out`` の ``(y, x)`` を左上にして重ねる(はみ出しは捨てる)。"""
193 height, width = out.shape
194 rows, cols = part.shape
195 dy0, dy1 = max(0, y), min(height, y + rows)
196 dx0, dx1 = max(0, x), min(width, x + cols)
197 if dy0 < dy1 and dx0 < dx1: 197 ↛ exitline 197 didn't return from function '_paste' because the condition on line 197 was always true
198 out[dy0:dy1, dx0:dx1] |= part[dy0 - y:dy1 - y, dx0 - x:dx1 - x]
201def _best_offset(template, target, limit):
202 """``template`` を ``target`` に重ねる、``limit`` 以内のずれ ``(dy, dx)``。
204 同じくらい重なるずれが並ぶとき(まっすぐな線の一部など)は、一番小さい
205 ずれを選ぶ。測れなければ ``(0, 0)``。
206 """
207 if int(np.count_nonzero(template)) < LOCAL_MIN_TEMPLATE or not target.any():
208 return 0, 0
209 step = max(1, int(np.ceil(max(template.shape) / _MAX_WINDOW)))
210 before = _downsample(template, step)
211 after = _downsample(target, step)
212 reach = limit // step
213 correlation, size = _correlate(before, after, reach)
214 offset_y = np.arange(size[0])
215 offset_y = np.where(offset_y >= size[0] // 2, offset_y - size[0], offset_y)
216 offset_x = np.arange(size[1])
217 offset_x = np.where(offset_x >= size[1] // 2, offset_x - size[1], offset_x)
218 allowed = (np.abs(offset_y)[:, None] <= reach) & (np.abs(offset_x)[None, :] <= reach)
219 correlation = np.where(allowed, correlation, -np.inf)
220 peak = float(correlation.max())
221 if peak <= 0: 221 ↛ 222line 221 didn't jump to line 222 because the condition on line 221 was never true
222 return 0, 0
223 ys, xs = np.nonzero(correlation >= peak * PEAK_TOLERANCE)
224 distance = offset_y[ys] ** 2 + offset_x[xs] ** 2
225 nearest = int(np.argmin(distance))
226 return int(offset_y[ys[nearest]]) * step, int(offset_x[xs[nearest]]) * step
229def warp_region(previous_lines, current_lines, region, shift=(0, 0)):
230 """``region`` を区画に分け、区画ごとに今のコマの線へ合わせて動かした範囲。
232 まず全体を ``shift`` だけ動かしたとみなし、そこから区画ごとに、その区画の
233 縁の線が一番よく重なる追加のずれを探す。回転や一部だけの動きでも、範囲の
234 両端がそれぞれ合う。区画の境目には小さな隙間や重なりができるが、追跡では
235 塗り直す領域を選ぶ手がかりにしか使わないので問題ない。
237 :param shift: 全体のずれ ``(dy, dx)``(:func:`estimate_shifts` の結果など)。
238 :returns: 動かした範囲の真偽マスク。範囲が小さく分けられないときは None。
239 """
240 from .bucket_fill import dilate
242 bounds = mask_bounds(region)
243 if bounds is None: 243 ↛ 244line 243 didn't jump to line 244 because the condition on line 243 was never true
244 return None
245 x0, y0, x1, y1 = bounds
246 columns = min(LOCAL_MAX_TILES, max(1, (x1 - x0) // LOCAL_TILE))
247 rows = min(LOCAL_MAX_TILES, max(1, (y1 - y0) // LOCAL_TILE))
248 if columns * rows < 2:
249 return None
250 base_y, base_x = (int(value) for value in shift)
251 xs = np.linspace(x0, x1, columns + 1).round().astype(int)
252 ys = np.linspace(y0, y1, rows + 1).round().astype(int)
253 radius = max(
254 LOCAL_MIN_RADIUS, min(LOCAL_MAX_RADIUS, max(x1 - x0, y1 - y0) // 4)
255 )
256 out = np.zeros_like(region)
257 for ty0, ty1 in zip(ys[:-1].tolist(), ys[1:].tolist()):
258 for tx0, tx1 in zip(xs[:-1].tolist(), xs[1:].tolist()):
259 part = region[ty0:ty1, tx0:tx1]
260 if not part.any(): 260 ↛ 261line 260 didn't jump to line 261 because the condition on line 260 was never true
261 continue
262 wy0, wy1 = ty0 - radius, ty1 + radius
263 wx0, wx1 = tx0 - radius, tx1 + radius
264 # 区画の部分だけを窓に置き、その縁に接する前のコマの線を型にする。
265 # 区画の切れ目(塗った範囲の内側)には線が無いので型に入らない。
266 local = np.zeros((wy1 - wy0, wx1 - wx0), dtype=bool)
267 local[radius:radius + part.shape[0], radius:radius + part.shape[1]] = part
268 template = _crop(previous_lines, wy0, wy1, wx0, wx1)
269 template &= dilate(local, 3) & ~local
270 target = _crop(
271 current_lines, wy0 + base_y, wy1 + base_y, wx0 + base_x, wx1 + base_x
272 )
273 dy, dx = _best_offset(template, target, radius)
274 _paste(out, part, ty0 + base_y + dy, tx0 + base_x + dx)
275 return out
278def estimate_shift(previous_lines, current_lines, region, margin=None):
279 """一番それらしいずれ ``(dy, dx)``。推定できなければ ``(0, 0)``。"""
280 shifts = estimate_shifts(previous_lines, current_lines, region, 1, margin)
281 return shifts[0] if shifts else (0, 0)
284# ----------------------------------------------------------------------
285# 小さい図形の追跡
286# ----------------------------------------------------------------------
287# 点や星の中心のように数十画素しかない図形は、縁の線が短すぎて、上の
288# 「縁の線の重なり」ではずれが決まらない(どの曲線にも同じくらい重なる)。
289# 3コマで数画素動くだけで前の範囲と重ならなくなるので、重なり(IoU)で選ぶ
290# こともできない。そこで「その図形のまわりにどんな色が並んでいるか」で比べる。
291# 髪の中の点なら、まわりは髪の色とピンクの粒で、別の場所の似た点とは並びが違う。
293#: 主線とみなす RGB の上限(各チャンネル)。``bucket_fill.BLACK_MAX`` と揃える。
294LINE_MAX = 48
295#: まわりの色の並びを比べる窓の半径(px)。
296CONTEXT_RADIUS = 24
297#: ずれを探すのに使う、まわりの色の数(多い順)。
298_CONTEXT_COLORS = 6
301def line_art(pixels):
302 """濃い色の不透明画素(主線)の真偽マスク。
304 塗る対象の色に関係なく、コマ間で同じものを指す手がかりになる。透明の部分を
305 塗るときに「透明でない画素」を線とみなすと、髪の塗りまで線になって比べられない。
306 """
307 # チャンネルごとに比べる。`max(axis=2)` は飛び飛びの並びを畳むので、同じ結果でも
308 # キャンバス1枚ぶん遅い。
309 red, green, blue = pixels[:, :, 0], pixels[:, :, 1], pixels[:, :, 2]
310 dark = red <= LINE_MAX
311 dark &= green <= LINE_MAX
312 dark &= blue <= LINE_MAX
313 dark &= pixels[:, :, 3] > 0
314 return dark
317def _labels(pixels):
318 """画素ごとの色を1つの整数にする。透明はどの色でも同じ値(0)にそろえる。"""
319 pixels = np.ascontiguousarray(pixels)
320 height, width = pixels.shape[:2]
321 packed = pixels.reshape(height, width * 4).view(np.uint32).astype(np.int64)
322 packed[pixels[:, :, 3] == 0] = 0
323 return packed
326def estimate_color_shifts(
327 previous_pixels, current_pixels, region, count=3, radius=CONTEXT_RADIUS,
328 margin=None,
329):
330 """``region`` のまわりの色の並びが、前のコマから今のコマへどれだけ動いたかの候補。
332 まわりの色ごとに「その色の画素」を型にして相互相関を取り、足し合わせた山の
333 高い順に ``(dy, dx)`` を返す。``region`` そのものの画素は比べない(前のコマで
334 塗った色と、今のコマのまだ塗っていない色は違うので)。
335 """
336 bounds = mask_bounds(region)
337 if bounds is None: 337 ↛ 338line 337 didn't jump to line 338 because the condition on line 337 was never true
338 return []
339 height, width = region.shape
340 x0, y0, x1, y1 = bounds
341 if margin is None: 341 ↛ 343line 341 didn't jump to line 343 because the condition on line 341 was always true
342 margin = max(64, int(max(x1 - x0, y1 - y0) * 3))
343 tx0, ty0 = max(0, x0 - radius), max(0, y0 - radius)
344 tx1, ty1 = min(width, x1 + radius), min(height, y1 + radius)
345 wx0, wy0 = max(0, tx0 - margin), max(0, ty0 - margin)
346 wx1, wy1 = min(width, tx1 + margin), min(height, ty1 + margin)
347 before = _labels(previous_pixels[ty0:ty1, tx0:tx1])
348 after = _labels(current_pixels[wy0:wy1, wx0:wx1])
349 keep = ~region[ty0:ty1, tx0:tx1]
350 values, counts = np.unique(before[keep], return_counts=True)
351 if not values.size: 351 ↛ 352line 351 didn't jump to line 352 because the condition on line 351 was never true
352 return []
353 rows, cols = before.shape
354 size = (after.shape[0] + rows, after.shape[1] + cols)
355 correlation = np.zeros(size, dtype=np.float64)
356 for value in values[np.argsort(-counts)[:_CONTEXT_COLORS]]:
357 found = (after == value)
358 if not found.any(): 358 ↛ 359line 358 didn't jump to line 359 because the condition on line 358 was never true
359 continue
360 template = ((before == value) & keep).astype(np.float32)
361 correlation += np.fft.irfft2(
362 np.fft.rfft2(found.astype(np.float32), size)
363 * np.conj(np.fft.rfft2(template, size)),
364 size,
365 )
366 shifts = []
367 for _ in range(count):
368 peak_y, peak_x = np.unravel_index(int(np.argmax(correlation)), correlation.shape)
369 if not np.isfinite(correlation[peak_y, peak_x]) or correlation[peak_y, peak_x] <= 0: 369 ↛ 370line 369 didn't jump to line 370 because the condition on line 369 was never true
370 break
371 offset_y = int(peak_y) if peak_y < size[0] // 2 else int(peak_y) - size[0]
372 offset_x = int(peak_x) if peak_x < size[1] // 2 else int(peak_x) - size[1]
373 correlation[
374 max(0, peak_y - 2):peak_y + 3, max(0, peak_x - 2):peak_x + 3
375 ] = -np.inf
376 # 窓の中での位置のずれを、キャンバス全体でのずれに直す。
377 shifts.append((wy0 + offset_y - ty0, wx0 + offset_x - tx0))
378 return shifts
381def _context_window(pixels, region, center, radius):
382 """``center`` を中心にした一辺 ``2 * radius + 1`` の窓の、色の整数と図形のマスク。
384 キャンバスの外にはみ出した所は色を -1 にする(比べない)。
385 """
386 height, width = region.shape
387 center_y, center_x = center
388 size = 2 * radius + 1
389 window = np.full((size, size), -1, dtype=np.int64)
390 inside = np.zeros((size, size), dtype=bool)
391 y0, x0 = center_y - radius, center_x - radius
392 sy0, sx0 = max(0, y0), max(0, x0)
393 sy1, sx1 = min(height, y0 + size), min(width, x0 + size)
394 if sy1 > sy0 and sx1 > sx0: 394 ↛ 399line 394 didn't jump to line 399 because the condition on line 394 was always true
395 window[sy0 - y0:sy1 - y0, sx0 - x0:sx1 - x0] = _labels(
396 pixels[sy0:sy1, sx0:sx1]
397 )
398 inside[sy0 - y0:sy1 - y0, sx0 - x0:sx1 - x0] = region[sy0:sy1, sx0:sx1]
399 return window, inside
402def _center(mask):
403 # round() は偶数への丸めなので、同じ形を奇数画素ずらすと中心が1画素ずれる。
404 return tuple(int(np.floor(value + 0.5)) for value in np.argwhere(mask).mean(axis=0))
407def context_similarity(
408 previous_pixels, previous_region, current_pixels, current_region,
409 radius=CONTEXT_RADIUS,
410):
411 """2つの図形が同じものらしいかを 0〜1 で返す。
413 それぞれの重心を中心にした窓で、図形の外側の画素の色がどれだけ一致するかを
414 7割、重心をそろえたときの形の重なりを3割として足す。図形そのものの色は
415 比べない(塗ってあるかどうかで違うため)。
417 まわりがほぼ一色の白地なら、どこを比べても一致してしまい手がかりにならないので、
418 そのときの色の一致は 0 とする(:func:`_agreement`)。
419 """
420 if not previous_region.any() or not current_region.any(): 420 ↛ 421line 420 didn't jump to line 421 because the condition on line 420 was never true
421 return 0.0
422 before, before_inside = _context_window(
423 previous_pixels, previous_region, _center(previous_region), radius
424 )
425 after, after_inside = _context_window(
426 current_pixels, current_region, _center(current_region), radius
427 )
428 compared = ~before_inside & ~after_inside & (before >= 0) & (after >= 0)
429 surroundings = _agreement(before[compared], after[compared])
430 union = int(np.count_nonzero(before_inside | after_inside))
431 shape = int(np.count_nonzero(before_inside & after_inside)) / max(1, union)
432 return 0.7 * surroundings + 0.3 * shape
435#: まわりの色の並びが、偶然でもこの割合以上一致してしまうなら手がかりにしない
436#: (白地に細い線だけ、のような窓)。
437CONTEXT_MAX_EXPECTED = 0.9
440def _agreement(before, after):
441 """2つの色の並びの一致した割合(0〜1)。
443 色の出現頻度だけから見込める一致の割合(偶然の一致)が
444 :data:`CONTEXT_MAX_EXPECTED` を超える、ほぼ一色の窓では 0 を返す。
445 """
446 if not before.size: 446 ↛ 447line 446 didn't jump to line 447 because the condition on line 446 was never true
447 return 0.0
448 values, inverse = np.unique(np.concatenate([before, after]), return_inverse=True)
449 counts_before = np.bincount(inverse[:before.size], minlength=values.size)
450 counts_after = np.bincount(inverse[before.size:], minlength=values.size)
451 expected = float(np.dot(counts_before, counts_after)) / (before.size * after.size)
452 if expected > CONTEXT_MAX_EXPECTED:
453 return 0.0
454 return float(np.count_nonzero(before == after)) / before.size