File size: 4,223 Bytes
b48dd06 6062e9a b48dd06 6062e9a b48dd06 6062e9a b48dd06 6062e9a b48dd06 6062e9a b48dd06 6062e9a b48dd06 6062e9a b48dd06 6062e9a b48dd06 6062e9a b48dd06 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | import numpy as np
from collections import Counter, deque
def initialize_potential(grid):
return np.array(grid, dtype=float)
def discrete_gradient(phi):
gx = np.zeros_like(phi)
gy = np.zeros_like(phi)
gx[:-1, :] = phi[1:, :] - phi[:-1, :]
gy[:, :-1] = phi[:, 1:] - phi[:, :-1]
mag = np.sqrt(gx**2 + gy**2)
return gx, gy, mag
def dirichlet_energy(phi):
_, _, mag = discrete_gradient(phi)
return np.sum(mag**2)
def sigma_l1(phi_current, phi_target):
return np.sum(np.abs(phi_target - phi_current))
def tile_transform(phi_in, out_shape):
h_in, w_in = phi_in.shape
h_out, w_out = out_shape
out = np.zeros(out_shape, dtype=float)
for i in range(h_out):
for j in range(w_out):
out[i, j] = phi_in[i % h_in, j % w_in]
return out
def fill_enclosed(phi, boundary_mask=None):
"""
Fill zero regions that are fully enclosed by non-zero boundary.
Returns a new array with enclosed holes filled with modal neighbor color.
"""
arr = np.array(phi, dtype=int)
h, w = arr.shape
if boundary_mask is None:
boundary = (arr != 0)
else:
boundary = np.array(boundary_mask, dtype=bool)
visited = np.zeros((h, w), dtype=bool)
filled = arr.copy()
def flood(start_r, start_c):
q = deque()
q.append((start_r, start_c))
comp = []
touches_border = False
visited[start_r, start_c] = True
while q:
r, c = q.popleft()
comp.append((r, c))
if r == 0 or c == 0 or r == h-1 or c == w-1:
touches_border = True
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
if 0 <= nr < h and 0 <= nc < w and not visited[nr, nc]:
if arr[nr, nc] == 0:
visited[nr, nc] = True
q.append((nr, nc))
return comp, touches_border
for i in range(h):
for j in range(w):
if arr[i, j] == 0 and not visited[i, j]:
comp, touches_border = flood(i, j)
if not touches_border:
neighbor_vals = []
for (r, c) in comp:
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
if 0 <= nr < h and 0 <= nc < w:
v = arr[nr, nc]
if v != 0:
neighbor_vals.append(int(v))
if neighbor_vals:
mode_color = Counter(neighbor_vals).most_common(1)[0][0]
else:
mode_color = 1
for (r, c) in comp:
filled[r, c] = mode_color
return filled
class Transform:
def __init__(self, func, name, params=None):
self.func = func
self.name = name
self.params = params or {}
def apply(self, phi):
return self.func(phi, **self.params)
def compose(self, other):
def composed(phi):
return other.apply(self.apply(phi))
return Transform(lambda p: composed(p), f"{self.name}∘{other.name}")
def __repr__(self):
return f"<Transform {self.name}>"
def beam_minimize(phi_in, phi_target, atomic_library, beam_width=4, max_depth=4, lock_coeff=0.1):
identity = Transform(lambda p: p, "Id")
beam = [(identity, phi_in, 0.0)]
best = None
for depth in range(max_depth):
candidates = []
for T_cur, _, _ in beam:
for T_atomic in atomic_library:
T_new = T_cur.compose(T_atomic)
phi_new = T_new.apply(phi_in)
residue = sigma_l1(phi_new, phi_target)
energy = dirichlet_energy(phi_new)
score = residue + lock_coeff * energy
candidates.append((T_new, phi_new, score))
if not candidates:
break
candidates.sort(key=lambda x: x[2])
beam = candidates[:beam_width]
best = beam[0]
if sigma_l1(best[1], phi_target) == 0:
break
return best[0], best[1]
|