Coverage for paintmaskanimator/reference_check.py: 93%

1"""見本のセルや前後のコマと比べて、塗り残し・塗り間違いの候補を探す（UI 非依存）。 

2 

31枚目だけ仕上げたカットを残りのコマへ塗り進めると、次のような取りこぼしが出る。 

4 

5- 見本で使っている色が、あるコマにだけ無い（星の中心を塗り忘れた、など）。 

6- 見本に無い色が、あるコマに残っている（色トレス線を塗り色に変え忘れた、など）。 

7- ある部分の色が、前後のコマの同じ部分と違う（頬を髪の色で塗った、など）。 

8 

9前の2つはセルの色の集計を見本と比べるだけで分かる。最後の1つは、塗った部分ごとに 

10前後のコマで同じ部分（線画のずれを推定して動かした位置）の色を数え、前後の両方が 

11別の同じ色ならそれを候補にする。前後で色が揃わない所（動きが大きい、形が変わった）は 

12判断できないので挙げない。 

13 

14numpy 配列だけを扱う純粋な関数にしてある（``docs/design-principles.md`` 

15「将来は Rust へ置き換えていく」）。 

16""" 

17from __future__ import annotations 

18 

19from dataclasses import dataclass 

20from typing import Dict, List, Optional, Tuple 

21 

22import numpy as np 

23 

24from . import fill_tracking 

25from .bucket_fill import erode 

26 

27Rgb = Tuple[int, int, int] 

28Bounds = Tuple[int, int, int, int] 

29 

30#: 見本で使っている色が、このセルに無い。 

31KIND_MISSING = "missing" 

32#: 見本に無い色が、このセルに残っている。 

33KIND_EXTRA = "extra" 

34#: この部分の色が、前後のコマの同じ部分と違う。 

35KIND_MISMATCH = "mismatch" 

36#: 自動塗りで、場所や色を決めきれず塗らなかった部分（透明のまま）。 

37KIND_UNPAINTED = "unpainted" 

38#: 自動塗りで、前後のセルと違う色で塗ってあった部分（塗り替えてはいない）。 

39KIND_SUSPECT = "suspect" 

40#: 自動塗りで、手本に無い形（開いた口など）なので塗らなかった部分。 

41KIND_NEW_PART = "new_part" 

42#: 自動塗りで、残すか塗るかを決める手がかりの無かった色トレス線。 

43KIND_UNDECIDED_LINE = "undecided_line" 

44 

45#: 透明を表す値（:func:`fill_tracking._labels` と同じ）。 

46_TRANSPARENT = 0 

47#: 色の集計で、これより少ない画素しか無い色は数えない（見本側・セル側とも）。 

48MIN_COLOR_PIXELS = 5 

49#: 前後のコマと比べる部分の面積（px）の範囲。小さすぎる部分はずれの推定が 

50#: 当てにならず、大きすぎる部分（髪全体など）は形が大きく変わる。 

51MIN_REGION_AREA = 20 

52MAX_REGION_AREA = 40000 

53#: 前後のコマで、動かした範囲のうち一番多い色が占める割合の下限。 

54MIN_AGREEMENT = 0.6 

55#: この画素数だけ縮めると消える細い部分（色トレス線や斜線）は比べない。 

56#: 少し動くだけで前後のコマと重ならなくなり、候補として当てにならない。 

57THIN_RADIUS = 2 

58 

59 

60@dataclass(frozen=True) 

61class Finding: 

62 """見つかった候補1つ。""" 

63 

64 kind: str 

65 #: 問題の色（MISSING は見本の色、EXTRA は残っている色、MISMATCH はこの部分の色。 

66 #: 透明は ``None``）。 

67 rgb: Optional[Rgb] 

68 #: 画素数（MISSING は見本での画素数）。 

69 pixels: int 

70 #: 場所 ``(x0, y0, x1, y1)``（x1, y1 は排他）。MISSING には無い。 

71 bounds: Optional[Bounds] = None 

72 #: MISMATCH で、前後のコマのその部分の色（透明は ``None``）。 

73 expected: Optional[Rgb] = None 

74 #: MISMATCH で、外接矩形の中のこの部分のマスク。 

75 mask: Optional[np.ndarray] = None 

76 

77 

78def _to_rgb(value) -> Optional[Rgb]: 

79 value = int(value) 

80 if value == _TRANSPARENT: 

81 return None 

82 # _labels は RGBA8888 をリトルエンディアンの uint32 として見た値。 

83 return (value & 255, (value >> 8) & 255, (value >> 16) & 255) 

84 

85 

86def _is_line(rgb) -> bool: 

87 return rgb is not None and max(rgb) <= fill_tracking.LINE_MAX 

88 

89 

90def color_counts(pixels) -> Dict[Rgb, int]: 

91 """不透明な色ごとの画素数。白（消しゴム）と透明は数えない。""" 

92 labels = fill_tracking._labels(pixels) 

93 values, counts = np.unique(labels, return_counts=True) 

94 result = {} 

95 for value, count in zip(values.tolist(), counts.tolist()): 

96 rgb = _to_rgb(value) 

97 if rgb is None or rgb == (255, 255, 255): 

98 continue 

99 result[rgb] = int(count) 

100 return result 

101 

102 

103def compare_colors(reference_pixels, pixels, min_pixels=MIN_COLOR_PIXELS) -> List[Finding]: 

104 """見本 ``reference_pixels`` とこのセル ``pixels`` の使用色の違い。""" 

105 reference = color_counts(reference_pixels) 

106 counts = color_counts(pixels) 

107 findings = [] 

108 for rgb, count in sorted(reference.items(), key=lambda item: -item[1]): 

109 if count >= min_pixels and counts.get(rgb, 0) == 0: 

110 findings.append(Finding(KIND_MISSING, rgb, count)) 

111 extra = [ 

112 (rgb, count) for rgb, count in counts.items() 

113 if count >= min_pixels and rgb not in reference 

114 ] 

115 if extra: 

116 packed = fill_tracking._labels(pixels) 

117 for rgb, count in sorted(extra, key=lambda item: -item[1]): 

118 findings.append(Finding( 

119 KIND_EXTRA, rgb, count, bounds=_bounds(packed == _pack(rgb)) 

120 )) 

121 return findings 

122 

123 

124def _pack(rgb) -> int: 

125 return rgb[0] | (rgb[1] << 8) | (rgb[2] << 16) | (255 << 24) 

126 

127 

128def color_mask(pixels, rgb): 

129 """``pixels`` のうち色 ``rgb`` の画素（``None`` なら透明）。""" 

130 packed = fill_tracking._labels(pixels) 

131 return packed == (_TRANSPARENT if rgb is None else _pack(rgb)) 

132 

133 

134def _bounds(mask) -> Optional[Bounds]: 

135 return fill_tracking.mask_bounds(mask) 

136 

137 

138def label_regions(values): 

139 """同じ値が4近傍でつながった部分に番号を振る。``(番号の配列, 部分の数)``。""" 

140 labels, count, _runs = _label_runs(values) 

141 return labels, count 

142 

143 

144def _label_runs(values): 

145 """:func:`label_regions` と、ランごとの ``(行, 始まり, 終わり, 番号)``。 

146 

147 行ごとに同じ値の連続区間（ラン）へ分け、上下の行で重なって値が同じランを 

148 つなぐ。ランは各行を左から隙間なく覆うので、番号の配列はランの番号を長さ分 

149 並べるだけで作れる。大きさや外接矩形も、画素ごとではなくランごとに数えれば 

150 足りる（ランは画素よりずっと少ない）。 

151 """ 

152 values = np.asarray(values) 

153 height, width = values.shape 

154 if height == 0 or width == 0: 154 ↛ 155line 154 didn't jump to line 155 because the condition on line 154 was never true

155 empty = np.zeros(0, dtype=np.int64) 

156 return np.zeros((height, width), dtype=np.int32), 0, (empty, empty, empty, empty) 

157 from . import native 

158 labeled = native.label_runs(values) 

159 if labeled is not None: 

160 return labeled 

161 change = np.ones((height, width), dtype=bool) 

162 change[:, 1:] = values[:, 1:] != values[:, :-1] 

163 run_y, run_x = np.nonzero(change) 

164 count = run_x.size 

165 run_end = np.empty(count, dtype=np.int64) 

166 run_end[:-1] = run_x[1:] 

167 last_in_row = np.ones(count, dtype=bool) 

168 last_in_row[:-1] = run_y[1:] != run_y[:-1] 

169 run_end[last_in_row] = width 

170 run_value = values[run_y, run_x] 

171 row_start = np.searchsorted(run_y, np.arange(height + 1)) 

172 

173 connected = (native.connect_runs(run_x, run_end, run_value, row_start) 

174 if values.dtype.kind in "biu" else None) 

175 if connected is not None: 

176 run_label, regions = connected 

177 labels = np.repeat(run_label, run_end - run_x).reshape(height, width) 

178 return labels, regions, (run_y, run_x, run_end, run_label) 

179 

180 parent = list(range(count)) 

181 

182 def find(index): 

183 while parent[index] != index: 

184 parent[index] = parent[parent[index]] 

185 index = parent[index] 

186 return index 

187 

188 starts, ends, kinds = run_x.tolist(), run_end.tolist(), run_value.tolist() 

189 rows = row_start.tolist() 

190 for y in range(height - 1): 

191 upper, upper_end = rows[y], rows[y + 1] 

192 lower, lower_end = rows[y + 1], rows[y + 2] 

193 while upper < upper_end and lower < lower_end: 

194 if ( 

195 kinds[upper] == kinds[lower] 

196 and starts[upper] < ends[lower] 

197 and starts[lower] < ends[upper] 

198 ): 

199 root_a, root_b = find(upper), find(lower) 

200 if root_a != root_b: 

201 parent[max(root_a, root_b)] = min(root_a, root_b) 

202 if ends[upper] < ends[lower]: 

203 upper += 1 

204 else: 

205 lower += 1 

206 roots = np.fromiter((find(index) for index in range(count)), dtype=np.int64, count=count) 

207 _unique, compact = np.unique(roots, return_inverse=True) 

208 run_label = compact.astype(np.int32).reshape(count) 

209 labels = np.repeat(run_label, run_end - run_x).reshape(height, width) 

210 return labels, int(_unique.size), (run_y, run_x, run_end, run_label) 

211 

212 

213#: 前後のコマで対応する部分の面積比の上限（どちら向きにも）。 

214MAX_AREA_RATIO = 2.0 

215#: 前後のコマで対応する部分の、まわりの色の並びの似ている度合いの下限 

216#: （:func:`fill_tracking.context_similarity`）。 

217MIN_CONTEXT = 0.6 

218 

219 

220class CellRegions: 

221 """1セル分の、色ごとにつながった部分の情報。前後のコマと比べるときに使い回す。""" 

222 

223 def __init__(self, pixels, values=None): 

224 """:param values: 部分分けに使う色の値。省略時は ``pixels`` から作る。""" 

225 self.pixels = pixels 

226 self.values = fill_tracking._labels(pixels) if values is None else values 

227 self.lines = fill_tracking.line_art(pixels) 

228 self.height, self.width = self.values.shape 

229 self.labels, count, runs = _label_runs(self.values) 

230 # 大きさと外接矩形は、画素ごとではなくランごとに数える。 

231 run_y, run_x, run_end, run_label = runs 

232 self._region_values = np.empty(count, dtype=self.values.dtype) 

233 self._region_values[run_label] = self.values[run_y, run_x] 

234 self.sizes = np.bincount( 

235 run_label, weights=run_end - run_x, minlength=count, 

236 ).astype(np.int64) 

237 self.y0 = np.full(count, self.height) 

238 self.y1 = np.zeros(count, dtype=np.int64) 

239 self.x0 = np.full(count, self.width) 

240 self.x1 = np.zeros(count, dtype=np.int64) 

241 np.minimum.at(self.y0, run_label, run_y) 

242 np.maximum.at(self.y1, run_label, run_y) 

243 np.minimum.at(self.x0, run_label, run_x) 

244 np.maximum.at(self.x1, run_label, run_end - 1) 

245 self.on_edge = set(np.unique(np.concatenate([ 

246 self.labels[0], self.labels[-1], self.labels[:, 0], self.labels[:, -1] 

247 ])).tolist()) 

248 

249 def bounds(self, index) -> Bounds: 

250 return ( 

251 int(self.x0[index]), int(self.y0[index]), 

252 int(self.x1[index]) + 1, int(self.y1[index]) + 1, 

253 ) 

254 

255 def local_mask(self, index): 

256 x0, y0, x1, y1 = self.bounds(index) 

257 return self.labels[y0:y1, x0:x1] == index 

258 

259 def mask(self, index): 

260 x0, y0, x1, y1 = self.bounds(index) 

261 out = np.zeros((self.height, self.width), dtype=bool) 

262 out[y0:y1, x0:x1] = self.labels[y0:y1, x0:x1] == index 

263 return out 

264 

265 def value(self, index) -> int: 

266 return int(self._region_values[index]) 

267 

268 def region_under(self, mask): 

269 """``mask`` の下（主線を除く）で一番多い部分の番号と、その割合。""" 

270 sample = self.labels[mask & ~self.lines] 

271 if not sample.size: 271 ↛ 272line 271 didn't jump to line 272 because the condition on line 271 was never true

272 return None, 0.0 

273 indices, counts = np.unique(sample, return_counts=True) 

274 top = int(np.argmax(counts)) 

275 return int(indices[top]), float(counts[top]) / sample.size 

276 

277 

278def _counterpart(current, region, neighbour, min_agreement): 

279 """``neighbour`` のコマで ``region`` に当たる部分の番号。見つからなければ None。 

280 

281 線画のずれを推定して動かした位置で一番多い部分を選び、面積が近く、まわりの 

282 色の並びもよく似ているときだけ「同じ部分」とみなす。 

283 """ 

284 shift = fill_tracking.estimate_shift(current.lines, neighbour.lines, region) 

285 moved = fill_tracking.shift_mask(region, *shift) 

286 index, share = neighbour.region_under(moved) 

287 if index is None or share < min_agreement: 287 ↛ 288line 287 didn't jump to line 288 because the condition on line 287 was never true

288 return None 

289 area = int(np.count_nonzero(region)) 

290 ratio = int(neighbour.sizes[index]) / max(1, area) 

291 if not 1.0 / MAX_AREA_RATIO <= ratio <= MAX_AREA_RATIO: 291 ↛ 292line 291 didn't jump to line 292 because the condition on line 291 was never true

292 return None 

293 similarity = fill_tracking.context_similarity( 

294 current.pixels, region, neighbour.pixels, neighbour.mask(index) 

295 ) 

296 return index if similarity >= MIN_CONTEXT else None 

297 

298 

299def find_mismatches( 

300 previous, current, following, 

301 min_area=MIN_REGION_AREA, max_area=MAX_REGION_AREA, 

302 min_agreement=MIN_AGREEMENT, 

303) -> List[Finding]: 

304 """``current`` の部分のうち、前後のコマの同じ部分と色が違うものを挙げる。 

305 

306 引数はそれぞれのコマの :class:`CellRegions`。前後の両方で同じ部分が見つかり、 

307 その色が揃っていて、このコマの色と違うものだけを返す。 

308 """ 

309 if not ( 309 ↛ 312line 309 didn't jump to line 312 because the condition on line 309 was never true

310 previous.values.shape == current.values.shape == following.values.shape 

311 ): 

312 return [] 

313 findings = [] 

314 candidates = np.nonzero( 

315 (current.sizes >= min_area) & (current.sizes <= max_area) 

316 )[0] 

317 for index in candidates.tolist(): 

318 value = current.value(index) 

319 rgb = _to_rgb(value) 

320 if _is_line(rgb) or rgb == (255, 255, 255): 

321 continue 

322 if rgb is None and index in current.on_edge: 322 ↛ 324line 322 didn't jump to line 324 because the condition on line 322 was never true

323 # キャンバスの端につながる透明は、絵の外（背景）。 

324 continue 

325 local = current.local_mask(index) 

326 if not erode(local, THIN_RADIUS).any(): 326 ↛ 327line 326 didn't jump to line 327 because the condition on line 326 was never true

327 continue 

328 region = current.mask(index) 

329 # 同じ位置でもう同じ色なら、ずれを推定するまでもない。 

330 consistent = False 

331 for neighbour in (previous, following): 

332 same, share = neighbour.region_under(region) 

333 if same is not None and neighbour.value(same) == value and share >= min_agreement: 

334 consistent = True 

335 break 

336 if consistent: 

337 continue 

338 expected = [] 

339 for neighbour in (previous, following): 

340 other = _counterpart(current, region, neighbour, min_agreement) 

341 if other is None: 341 ↛ 342line 341 didn't jump to line 342 because the condition on line 341 was never true

342 break 

343 expected.append(neighbour.value(other)) 

344 if len(expected) != 2 or expected[0] != expected[1] or expected[0] == value: 

345 continue 

346 expected_rgb = _to_rgb(expected[0]) 

347 if _is_line(expected_rgb): 347 ↛ 348line 347 didn't jump to line 348 because the condition on line 347 was never true

348 continue 

349 findings.append(Finding( 

350 KIND_MISMATCH, rgb, int(current.sizes[index]), 

351 bounds=current.bounds(index), expected=expected_rgb, mask=local, 

352 )) 

353 findings.sort(key=lambda finding: -finding.pixels) 

354 return findings 

355 

356 

357__all__ = [ 

358 "Finding", 

359 "KIND_MISSING", 

360 "KIND_EXTRA", 

361 "KIND_MISMATCH", 

362 "color_counts", 

363 "color_mask", 

364 "compare_colors", 

365 "label_regions", 

366 "CellRegions", 

367 "find_mismatches", 

368]