732 lines
29 KiB
Python
732 lines
29 KiB
Python
# coding=utf-8
|
|
"""
|
|
Noyau de calcul de l'extension « Gray Iso-Layers », sans dependance a inkex.
|
|
|
|
Testable avec pytest seul et reutilisable hors Inkscape (scripts, schema
|
|
des parametres). Seule dependance : numpy (fourni avec Inkscape).
|
|
|
|
Conventions :
|
|
- un champ (`field`) est un tableau numpy 2D de gris, 0 = noir, 1 = blanc,
|
|
indexe [ligne, colonne] ;
|
|
- un anneau est un tableau numpy (n, 2) de points (x, y), ferme implicitement ;
|
|
un contour (`rings`) est une liste d'anneaux, les trous suivent la regle
|
|
pair-impair ;
|
|
- les anneaux sont exprimes en « echantillons » : x de 0 a largeur - 1, y de 0
|
|
a hauteur - 1, les echantillons du bord etant poses sur le bord de l'image ;
|
|
- l'axe y est oriente vers le bas (repere SVG).
|
|
"""
|
|
|
|
import numpy as np
|
|
|
|
# Valeur de la bordure ajoutee autour du champ : assez grande pour que les
|
|
# contours se referment exactement sur les echantillons du bord.
|
|
_OUTSIDE = -1e12
|
|
|
|
# Segments de contour par cas du « marching squares ». Le cas est le nombre
|
|
# 8.HG + 4.HD + 2.BD + 1.BG (coins dans la region) ; chaque segment relie deux
|
|
# aretes de la cellule (T haut, R droite, B bas, L gauche). Les cas 5 et 10
|
|
# (selles) sont traites a part.
|
|
_CASES = {
|
|
1: ("LB",), 2: ("BR",), 3: ("LR",), 4: ("TR",), 6: ("TB",), 7: ("TL",),
|
|
8: ("TL",), 9: ("TB",), 11: ("TR",), 12: ("LR",), 13: ("BR",), 14: ("LB",),
|
|
}
|
|
_SADDLES = {
|
|
# cas : (segments si le centre est dans la region, segments sinon)
|
|
5: (("TL", "BR"), ("TR", "LB")),
|
|
10: (("TR", "LB"), ("TL", "BR")),
|
|
}
|
|
|
|
|
|
def parse_color(value, default=("#b3b3b3", 1.0)):
|
|
"""Couleur Inkscape (entier RGBA decimal ou 0x..., ou #rrggbb[aa]).
|
|
|
|
Renvoie (couleur CSS #rrggbb, opacite entre 0 et 1). Le parametre
|
|
« color » d'Inkscape arrive sous forme d'entier RGBA ; on le decode
|
|
nous-memes pour ne pas dependre de l'API couleur d'inkex, qui a change
|
|
entre les versions 1.x.
|
|
"""
|
|
text = str(value).strip()
|
|
try:
|
|
if text.startswith("#"):
|
|
digits = text[1:]
|
|
if len(digits) == 3:
|
|
digits = "".join(c * 2 for c in digits)
|
|
if len(digits) == 6:
|
|
digits += "ff"
|
|
if len(digits) != 8:
|
|
return default
|
|
number = int(digits, 16)
|
|
else:
|
|
number = int(text, 0)
|
|
except ValueError:
|
|
return default
|
|
number &= 0xFFFFFFFF
|
|
red, green, blue = (number >> 24) & 255, (number >> 16) & 255, (number >> 8) & 255
|
|
alpha = (number & 255) / 255.0
|
|
return "#{:02x}{:02x}{:02x}".format(red, green, blue), round(alpha, 4)
|
|
|
|
|
|
def gray_to_hex(gray):
|
|
"""Couleur CSS #rrggbb d'un gris entre 0 (noir) et 1 (blanc)."""
|
|
value = int(round(255 * min(1.0, max(0.0, float(gray)))))
|
|
return "#{0:02x}{0:02x}{0:02x}".format(value)
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Preparation du champ
|
|
# --------------------------------------------------------------------------
|
|
|
|
def gaussian_blur(field, sigma):
|
|
"""Flou gaussien separable d'ecart-type `sigma` (en echantillons).
|
|
|
|
Les bords sont prolonges par repetition, pour ne pas les assombrir.
|
|
"""
|
|
field = np.asarray(field, dtype=float)
|
|
if sigma <= 0:
|
|
return field.copy()
|
|
radius = max(1, int(np.ceil(3 * sigma)))
|
|
taps = np.arange(-radius, radius + 1)
|
|
kernel = np.exp(-0.5 * (taps / float(sigma)) ** 2)
|
|
kernel /= kernel.sum()
|
|
|
|
result = field
|
|
for axis in (0, 1):
|
|
pad = [(0, 0), (0, 0)]
|
|
pad[axis] = (radius, radius)
|
|
padded = np.pad(result, pad, mode="edge")
|
|
size = result.shape[axis]
|
|
blurred = np.zeros_like(result)
|
|
for k, weight in enumerate(kernel):
|
|
window = [slice(None), slice(None)]
|
|
window[axis] = slice(k, k + size)
|
|
blurred += weight * padded[tuple(window)]
|
|
result = blurred
|
|
return result
|
|
|
|
|
|
def box_blur(field, radius):
|
|
"""Moyenne sur une fenetre carree de cote 2 * radius + 1, bords repetes."""
|
|
field = np.asarray(field, dtype=float)
|
|
radius = int(radius)
|
|
if radius < 1:
|
|
return field.copy()
|
|
size = 2 * radius + 1
|
|
total = np.cumsum(np.cumsum(np.pad(field, radius, mode="edge"), axis=0), axis=1)
|
|
total = np.pad(total, ((1, 0), (1, 0)))
|
|
return (total[size:, size:] - total[:-size, size:]
|
|
- total[size:, :-size] + total[:-size, :-size]) / float(size * size)
|
|
|
|
|
|
def edge_preserving_blur(field, radius, contrast=0.1):
|
|
"""Lissage qui respecte les contours (filtre guide par l'image elle-meme).
|
|
|
|
Dans une fenetre de `radius` echantillons, les variations plus faibles que
|
|
`contrast` (texture de la peau, grain) sont aplanies, tandis que les
|
|
transitions plus marquees (bord d'un visage, yeux, bouche) restent nettes,
|
|
la ou un flou gaussien les etalerait.
|
|
"""
|
|
field = np.asarray(field, dtype=float)
|
|
radius = int(radius)
|
|
if radius < 1:
|
|
return field.copy()
|
|
mean = box_blur(field, radius)
|
|
variance = np.maximum(box_blur(field * field, radius) - mean * mean, 0.0)
|
|
# keep = 1 sur un contour (on garde l'image), 0 en zone calme (on garde
|
|
# la moyenne locale).
|
|
keep = variance / (variance + contrast ** 2)
|
|
return box_blur(keep, radius) * field + box_blur(mean * (1.0 - keep), radius)
|
|
|
|
|
|
def smooth(field, blur, preserve_edges=False):
|
|
"""Lisse un champ avant sa decoupe en niveaux, puis l'etire sur 0..1.
|
|
|
|
`blur` est la taille du lissage en echantillons. Sans `preserve_edges`,
|
|
c'est l'ecart-type d'un flou gaussien. Avec, c'est le rayon d'un lissage
|
|
qui respecte les contours, suivi d'un leger flou gaussien (un cinquieme)
|
|
qui arrondit le trace des lignes de niveau.
|
|
"""
|
|
field = normalize(field)
|
|
if blur > 0 and preserve_edges:
|
|
field = edge_preserving_blur(field, max(1, int(round(blur))))
|
|
field = gaussian_blur(field, blur / 5.0)
|
|
elif blur > 0:
|
|
field = gaussian_blur(field, blur)
|
|
return normalize(field)
|
|
|
|
|
|
def normalize(field):
|
|
"""Etire le champ sur toute la plage 0..1 (champ uniforme : tout a 0)."""
|
|
field = np.asarray(field, dtype=float)
|
|
low, high = float(field.min()), float(field.max())
|
|
if high - low < 1e-9:
|
|
return np.zeros_like(field)
|
|
return (field - low) / (high - low)
|
|
|
|
|
|
def thresholds(levels):
|
|
"""Seuils reguliers separant `levels` niveaux de gris sur 0..1."""
|
|
return [k / float(levels) for k in range(1, levels)]
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Contours
|
|
# --------------------------------------------------------------------------
|
|
|
|
def contour_rings(field, threshold, above=True):
|
|
"""Contour ferme de la region `field >= threshold` (ou `<=` si `above`
|
|
est faux), par « marching squares » avec interpolation lineaire.
|
|
|
|
Le champ est borde d'une valeur hors region : la ou la region touche le
|
|
bord de l'image, le contour longe ce bord, il est donc toujours ferme.
|
|
"""
|
|
field = np.asarray(field, dtype=float)
|
|
height, width = field.shape
|
|
if height < 2 or width < 2:
|
|
return []
|
|
signed = (field - threshold) if above else (threshold - field)
|
|
g = np.full((height + 2, width + 2), _OUTSIDE)
|
|
g[1:-1, 1:-1] = signed
|
|
rows, cols = g.shape
|
|
|
|
inside = g >= 0
|
|
tl, tr = inside[:-1, :-1], inside[:-1, 1:]
|
|
bl, br = inside[1:, :-1], inside[1:, 1:]
|
|
case = 8 * tl + 4 * tr + 2 * br + 1 * bl
|
|
center = (g[:-1, :-1] + g[:-1, 1:] + g[1:, :-1] + g[1:, 1:]) >= 0
|
|
|
|
# Identifiant entier de chaque arete de la grille : les deux cellules qui
|
|
# partagent une arete designent ainsi exactement le meme point de contour.
|
|
ii, jj = np.indices(case.shape)
|
|
count = rows * cols
|
|
edge = {
|
|
"T": ii * cols + jj, # arete horizontale (i, j)-(i, j+1)
|
|
"B": (ii + 1) * cols + jj,
|
|
"L": count + ii * cols + jj, # arete verticale (i, j)-(i+1, j)
|
|
"R": count + ii * cols + jj + 1,
|
|
}
|
|
|
|
starts, ends = [], []
|
|
|
|
def add(mask, segments):
|
|
for first, second in segments:
|
|
starts.append(edge[first][mask])
|
|
ends.append(edge[second][mask])
|
|
|
|
for number, segments in _CASES.items():
|
|
add(case == number, segments)
|
|
for number, (if_inside, if_outside) in _SADDLES.items():
|
|
add((case == number) & center, if_inside)
|
|
add((case == number) & ~center, if_outside)
|
|
|
|
starts = np.concatenate(starts)
|
|
ends = np.concatenate(ends)
|
|
if starts.size == 0:
|
|
return []
|
|
|
|
# Chaque arete traversee appartient a exactement deux segments : on en
|
|
# deduit, pour chaque point, ses deux voisins le long du contour.
|
|
ids, inverse = np.unique(np.concatenate([starts, ends]), return_inverse=True)
|
|
first, second = inverse[:starts.size], inverse[starts.size:]
|
|
node = np.concatenate([first, second])
|
|
other = np.concatenate([second, first])
|
|
order = np.argsort(node, kind="stable")
|
|
neighbours = other[order].reshape(-1, 2).tolist()
|
|
|
|
points = _edge_points(g, ids, cols, count)
|
|
# Retour au repere de l'image (sans la bordure), bord compris.
|
|
points -= 1.0
|
|
np.clip(points[:, 0], 0, width - 1, out=points[:, 0])
|
|
np.clip(points[:, 1], 0, height - 1, out=points[:, 1])
|
|
|
|
rings = []
|
|
visited = [False] * len(neighbours)
|
|
for start in range(len(neighbours)):
|
|
if visited[start]:
|
|
continue
|
|
chain, previous, current = [], -1, start
|
|
while not visited[current]:
|
|
visited[current] = True
|
|
chain.append(current)
|
|
n0, n1 = neighbours[current]
|
|
previous, current = current, (n1 if n0 == previous else n0)
|
|
ring = _drop_duplicates(points[chain])
|
|
if len(ring) >= 3:
|
|
rings.append(ring)
|
|
return rings
|
|
|
|
|
|
def _edge_points(g, ids, cols, count):
|
|
"""Point de passage du contour sur chaque arete (repere du champ borde)."""
|
|
vertical = ids >= count
|
|
flat = np.where(vertical, ids - count, ids)
|
|
i, j = flat // cols, flat % cols
|
|
a = g[i, j]
|
|
b = np.where(vertical, g[np.minimum(i + 1, g.shape[0] - 1), j],
|
|
g[i, np.minimum(j + 1, cols - 1)])
|
|
t = a / (a - b)
|
|
x = np.where(vertical, j, j + t)
|
|
y = np.where(vertical, i + t, i)
|
|
return np.column_stack([x, y]).astype(float)
|
|
|
|
|
|
def _drop_duplicates(ring, eps=1e-7):
|
|
"""Retire les points consecutifs confondus (coins de l'image, valeurs
|
|
tombant pile sur le seuil)."""
|
|
if len(ring) < 2:
|
|
return ring
|
|
step = np.abs(ring - np.roll(ring, 1, axis=0)).max(axis=1)
|
|
return ring[step > eps]
|
|
|
|
|
|
def ring_area(ring):
|
|
"""Aire d'un anneau (formule du lacet, valeur absolue)."""
|
|
ring = np.asarray(ring, dtype=float)
|
|
if len(ring) < 3:
|
|
return 0.0
|
|
x, y = ring[:, 0], ring[:, 1]
|
|
return 0.5 * abs(float(np.dot(x, np.roll(y, -1)) - np.dot(y, np.roll(x, -1))))
|
|
|
|
|
|
def _keep_mask(points, tolerance, anchors):
|
|
"""Douglas-Peucker : masque des points conserves entre les `anchors`
|
|
(indices croissants, toujours conserves)."""
|
|
keep = np.zeros(len(points), dtype=bool)
|
|
keep[list(anchors)] = True
|
|
stack = list(zip(anchors[:-1], anchors[1:]))
|
|
while stack:
|
|
first, last = stack.pop()
|
|
if last - first < 2:
|
|
continue
|
|
p, q = points[first], points[last]
|
|
inner = points[first + 1:last]
|
|
dx, dy = q - p
|
|
length = float(np.hypot(dx, dy))
|
|
if length < 1e-12:
|
|
distance = np.hypot(inner[:, 0] - p[0], inner[:, 1] - p[1])
|
|
else:
|
|
distance = np.abs(dx * (inner[:, 1] - p[1]) - dy * (inner[:, 0] - p[0])) / length
|
|
worst = int(np.argmax(distance))
|
|
if distance[worst] > tolerance:
|
|
middle = first + 1 + worst
|
|
keep[middle] = True
|
|
stack.append((first, middle))
|
|
stack.append((middle, last))
|
|
return keep
|
|
|
|
|
|
def simplify_ring(ring, tolerance):
|
|
"""Simplification de Douglas-Peucker d'un anneau ferme.
|
|
|
|
Aucun point conserve ne s'ecarte de plus de `tolerance` du trace d'origine.
|
|
"""
|
|
ring = np.asarray(ring, dtype=float)
|
|
count = len(ring)
|
|
if tolerance <= 0 or count < 5:
|
|
return ring
|
|
# Deux ancres : le premier point et le plus eloigne de lui.
|
|
far = int(np.argmax(((ring - ring[0]) ** 2).sum(axis=1)))
|
|
if far == 0:
|
|
return ring
|
|
closed = np.vstack([ring, ring[:1]])
|
|
return closed[:-1][_keep_mask(closed, tolerance, [0, far, count])[:-1]]
|
|
|
|
|
|
def simplify_chain(chain, tolerance):
|
|
"""Simplification de Douglas-Peucker d'une ligne ouverte (extremites fixes)."""
|
|
chain = np.asarray(chain, dtype=float)
|
|
if tolerance <= 0 or len(chain) < 3:
|
|
return chain
|
|
return chain[_keep_mask(chain, tolerance, [0, len(chain) - 1])]
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Lignes de niveau et bord de l'image
|
|
#
|
|
# Le bord de l'image est repere par une abscisse curviligne `s`, qui part du
|
|
# coin haut-gauche et tourne dans le sens horaire : haut, droite, bas, gauche.
|
|
# --------------------------------------------------------------------------
|
|
|
|
def _sides(points, right, bottom):
|
|
"""Pour chaque point, les cotes de l'image qu'il touche : colonnes haut,
|
|
droite, bas, gauche."""
|
|
eps = 1e-6 * max(right, bottom, 1e-12)
|
|
x, y = points[:, 0], points[:, 1]
|
|
return np.column_stack([np.abs(y) < eps, np.abs(x - right) < eps,
|
|
np.abs(y - bottom) < eps, np.abs(x) < eps])
|
|
|
|
|
|
def _border_position(point, right, bottom):
|
|
"""Abscisse curviligne d'un point pose sur le bord de l'image."""
|
|
top, on_right, on_bottom, _left = _sides(np.asarray([point]), right, bottom)[0]
|
|
x, y = float(point[0]), float(point[1])
|
|
if top:
|
|
return x
|
|
if on_right:
|
|
return right + y
|
|
if on_bottom:
|
|
return right + bottom + (right - x)
|
|
return (2 * right + bottom + (bottom - y)) % (2 * (right + bottom))
|
|
|
|
|
|
def _border_point(position, right, bottom):
|
|
"""Point du bord de l'image d'abscisse curviligne `position`."""
|
|
position %= 2 * (right + bottom)
|
|
if position <= right:
|
|
return position, 0.0
|
|
if position <= right + bottom:
|
|
return right, position - right
|
|
if position <= 2 * right + bottom:
|
|
return right - (position - right - bottom), bottom
|
|
return 0.0, bottom - (position - 2 * right - bottom)
|
|
|
|
|
|
def _border_corners(start, end, right, bottom):
|
|
"""Coins de l'image rencontres en longeant le bord de `start` a `end`
|
|
dans le sens des abscisses croissantes."""
|
|
perimeter = 2 * (right + bottom)
|
|
span = (end - start) % perimeter
|
|
corners = []
|
|
for position, corner in ((0.0, (0.0, 0.0)), (right, (right, 0.0)),
|
|
(right + bottom, (right, bottom)),
|
|
(2 * right + bottom, (0.0, bottom))):
|
|
distance = (position - start) % perimeter
|
|
if 0 < distance < span:
|
|
corners.append((distance, corner))
|
|
return [corner for _distance, corner in sorted(corners)]
|
|
|
|
|
|
def _border_value(field, position):
|
|
"""Valeur du champ au point du bord d'abscisse `position` (interpolee)."""
|
|
rows, cols = field.shape
|
|
x, y = _border_point(position, cols - 1.0, rows - 1.0)
|
|
j, i = min(int(x), cols - 2), min(int(y), rows - 2)
|
|
u, v = x - j, y - i
|
|
return ((1 - u) * (1 - v) * field[i, j] + u * (1 - v) * field[i, j + 1]
|
|
+ (1 - u) * v * field[i + 1, j] + u * v * field[i + 1, j + 1])
|
|
|
|
|
|
def contour_lines(field, threshold, tolerance=0.0, min_area=0.0):
|
|
"""Ligne de niveau `field = threshold`, simplifiee une fois pour toutes.
|
|
|
|
Renvoie `(closed, opened)` : les boucles fermees a l'interieur de l'image,
|
|
et les lignes ouvertes, dont les deux extremites sont sur le bord. Les
|
|
deux regions que la ligne separe la reutilisent telle quelle : leurs
|
|
frontieres communes coincident donc exactement. Les boucles et les lignes
|
|
qui delimitent une aire inferieure a `min_area` (en echantillons carres)
|
|
sont ecartees.
|
|
"""
|
|
field = np.asarray(field, dtype=float)
|
|
right, bottom = field.shape[1] - 1.0, field.shape[0] - 1.0
|
|
closed, opened = [], []
|
|
for ring in contour_rings(field, threshold):
|
|
sides = _sides(ring, right, bottom)
|
|
# Segment i -> i+1 pose sur le bord : ses deux bouts sur un meme cote.
|
|
border = (sides & np.roll(sides, -1, axis=0)).any(axis=1)
|
|
if border.all():
|
|
continue
|
|
if not border.any():
|
|
if ring_area(ring) >= min_area:
|
|
ring = simplify_ring(ring, tolerance)
|
|
if len(ring) >= 3:
|
|
closed.append(ring)
|
|
continue
|
|
count = len(ring)
|
|
start = next(i for i in range(count) if border[i - 1] and not border[i])
|
|
chain = [ring[start]]
|
|
for step in range(count):
|
|
i = (start + step) % count
|
|
if not border[i]:
|
|
chain.append(ring[(i + 1) % count])
|
|
continue
|
|
if len(chain) > 1:
|
|
chain = np.array(chain)
|
|
if _cut_area(chain, right, bottom) >= min_area:
|
|
chain = simplify_chain(chain, tolerance)
|
|
# Une ligne reduite a deux points d'un meme cote de
|
|
# l'image ne detache plus rien : elle longe le bord.
|
|
if len(chain) > 2 or not _sides(chain, right, bottom).all(axis=0).any():
|
|
opened.append(chain)
|
|
chain = [ring[(i + 1) % count]]
|
|
return closed, opened
|
|
|
|
|
|
def _cut_area(chain, right, bottom):
|
|
"""Aire de la plus petite des deux parts que la ligne detache de l'image."""
|
|
corners = _border_corners(_border_position(chain[-1], right, bottom),
|
|
_border_position(chain[0], right, bottom),
|
|
right, bottom)
|
|
area = ring_area(np.vstack([chain] + [np.array([c]) for c in corners]))
|
|
return min(area, right * bottom - area)
|
|
|
|
|
|
def region_rings(field, lines, inside):
|
|
"""Contour ferme d'une region bornee par des lignes de niveau.
|
|
|
|
`lines` est la liste des `(closed, opened)` de `contour_lines` qui bordent
|
|
la region ; `inside(valeur)` dit si une valeur du champ est dans la region.
|
|
Les lignes ouvertes sont refermees en longeant le bord de l'image, du
|
|
cote ou il appartient a la region.
|
|
"""
|
|
field = np.asarray(field, dtype=float)
|
|
right, bottom = field.shape[1] - 1.0, field.shape[0] - 1.0
|
|
perimeter = 2 * (right + bottom)
|
|
|
|
def on_border(position):
|
|
return inside(_border_value(field, position))
|
|
|
|
rings = [ring for closed, _opened in lines for ring in closed]
|
|
chains = [chain for _closed, opened in lines for chain in opened]
|
|
if not chains:
|
|
# Aucune ligne n'atteint le bord : il est tout entier dans la region,
|
|
# ou tout entier dehors.
|
|
probes = [on_border(perimeter * (k + 0.5) / 32.0) for k in range(32)]
|
|
if sum(probes) > 16:
|
|
rings.append(image_ring(int(right) + 1, int(bottom) + 1))
|
|
return rings
|
|
|
|
# Extremites des lignes, dans l'ordre ou on les rencontre sur le bord :
|
|
# entre deux extremites voisines, le bord est alternativement dans la
|
|
# region et hors d'elle.
|
|
ends = sorted((_border_position(chain[-end], right, bottom), index, end)
|
|
for index, chain in enumerate(chains) for end in (0, 1))
|
|
count = len(ends)
|
|
score = 0.0
|
|
for i in range(count):
|
|
span = (ends[(i + 1) % count][0] - ends[i][0]) % perimeter
|
|
# Plusieurs sondes par intervalle : une seule pourrait tomber sur une
|
|
# petite forme ecartee par `min_area` et fausser le vote.
|
|
votes = sum(1 if on_border((ends[i][0] + span * (n + 0.5) / 9.0) % perimeter)
|
|
else -1 for n in range(9))
|
|
score += span * votes * (1 if i % 2 == 0 else -1)
|
|
first = 0 if score >= 0 else 1
|
|
|
|
# link[i] = (extremite reliee a i par le bord, sens de parcours du bord)
|
|
link = {}
|
|
for i in range(first, first + count, 2):
|
|
start, end = i % count, (i + 1) % count
|
|
link[start] = (end, 1)
|
|
link[end] = (start, -1)
|
|
where = {(index, end): i for i, (_s, index, end) in enumerate(ends)}
|
|
|
|
used = [False] * len(chains)
|
|
for origin in range(len(chains)):
|
|
if used[origin]:
|
|
continue
|
|
points, index, entry = [], origin, 0
|
|
while not used[index]:
|
|
used[index] = True
|
|
chain = chains[index]
|
|
points.extend(chain if entry == 0 else chain[::-1])
|
|
leave = where[(index, 1 - entry)]
|
|
reach, direction = link[leave]
|
|
if direction > 0:
|
|
corners = _border_corners(ends[leave][0], ends[reach][0], right, bottom)
|
|
else:
|
|
corners = _border_corners(ends[reach][0], ends[leave][0], right, bottom)[::-1]
|
|
points.extend(corners)
|
|
_s, index, entry = ends[reach]
|
|
ring = _drop_duplicates(np.array(points, dtype=float))
|
|
if len(ring) >= 3:
|
|
rings.append(ring)
|
|
return rings
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Couches
|
|
# --------------------------------------------------------------------------
|
|
|
|
def iso_boards(field, levels=16, blur=0.0, min_area=0.0, tolerance=0.0,
|
|
shapes="light", preserve_edges=False):
|
|
"""Decoupe un champ de gris en une planche par niveau.
|
|
|
|
Le champ est lisse (`blur` en echantillons, `preserve_edges` : voir
|
|
`smooth`), etire sur 0..1 puis quantifie en `levels` niveaux a seuils
|
|
reguliers : le niveau k couvre les valeurs de k / levels a
|
|
(k + 1) / levels. Renvoie les planches du fond vers l'avant de la pile :
|
|
`(niveau, gris, rings, mark)` avec `niveau` de 0 (le plus sombre) a
|
|
levels - 1 et `gris` entre 0 et 1.
|
|
|
|
`shapes` choisit la forme de chaque planche :
|
|
- "light" : le niveau et tous les plus clairs (planches a empiler, la plus
|
|
sombre au fond, couvrant toute l'image) ;
|
|
- "dark" : le niveau et tous les plus sombres (la plus claire au fond) ;
|
|
- "band" : l'aplat du niveau seul, borde sur tous ses cotes ; les planches
|
|
pavent l'image sans se recouvrir.
|
|
|
|
`mark` est le repere d'assemblage : la ligne de niveau `(closed, opened)`
|
|
qui borde la planche suivante de la pile, a reporter sur celle-ci pour
|
|
savoir ou la poser. Elle a exactement le trace de la decoupe de la
|
|
planche suivante, sans les troncons qui longent le bord de l'image. Il
|
|
vaut `None` pour la derniere planche et pour les planches "band", qui ne
|
|
s'empilent pas.
|
|
|
|
Dans tous les cas les contours sont les lignes de niveau des seuils, donc
|
|
les frontieres des aplats de l'image quantifiee. Les formes d'aire
|
|
inferieure a `min_area` (fraction de la surface de l'image) sont
|
|
ecartees, les autres simplifiees a `tolerance` echantillons pres. Il y a
|
|
toujours `levels` planches : une planche sans forme est renvoyee vide.
|
|
"""
|
|
field = np.asarray(field, dtype=float)
|
|
height, width = field.shape
|
|
levels = max(2, int(levels))
|
|
field = smooth(field, blur, preserve_edges)
|
|
smallest = min_area * (width - 1) * (height - 1)
|
|
|
|
cuts = thresholds(levels)
|
|
# lines[k] : ligne de niveau du seuil k / levels, entre les niveaux k - 1 et k.
|
|
lines = [None] + [contour_lines(field, cut, tolerance, smallest) for cut in cuts]
|
|
lines.append(None)
|
|
low = [-np.inf] + cuts
|
|
high = cuts + [np.inf]
|
|
|
|
def band(k):
|
|
borders = [lines[n] for n in (k, k + 1) if lines[n] is not None]
|
|
return region_rings(field, borders, lambda v: low[k] <= v < high[k]), None
|
|
|
|
def lighter(k):
|
|
# Bordee par lines[k] ; la planche suivante (k + 1) par lines[k + 1].
|
|
borders = [lines[k]] if lines[k] is not None else []
|
|
return region_rings(field, borders, lambda v: v >= low[k]), lines[k + 1]
|
|
|
|
def darker(k):
|
|
# Bordee par lines[k + 1] ; la planche suivante (k - 1) par lines[k].
|
|
borders = [lines[k + 1]] if lines[k + 1] is not None else []
|
|
return region_rings(field, borders, lambda v: v < high[k]), lines[k]
|
|
|
|
if shapes == "dark":
|
|
order, board = range(levels - 1, -1, -1), darker
|
|
else:
|
|
order, board = range(levels), (band if shapes == "band" else lighter)
|
|
return [(k, k / float(levels - 1)) + board(k) for k in order]
|
|
|
|
|
|
def iso_layers(field, levels=16, blur=0.0, min_area=0.0, tolerance=0.0,
|
|
shapes="band", preserve_edges=False):
|
|
"""Comme `iso_boards`, sans les reperes d'assemblage : liste de
|
|
`(niveau, gris, rings)`."""
|
|
return [board[:3] for board in iso_boards(field, levels, blur, min_area,
|
|
tolerance, shapes, preserve_edges)]
|
|
|
|
|
|
def image_ring(width, height):
|
|
"""Anneau du rectangle de l'image, en echantillons."""
|
|
return np.array([(0.0, 0.0), (width - 1.0, 0.0),
|
|
(width - 1.0, height - 1.0), (0.0, height - 1.0)])
|
|
|
|
|
|
# --------------------------------------------------------------------------
|
|
# Ecriture SVG
|
|
# --------------------------------------------------------------------------
|
|
|
|
def scale_rings(rings, scale_x, scale_y, offset_x=0.0, offset_y=0.0):
|
|
"""Passe des echantillons au repere de destination."""
|
|
factor = np.array([scale_x, scale_y], dtype=float)
|
|
offset = np.array([offset_x, offset_y], dtype=float)
|
|
return [np.asarray(ring, dtype=float) * factor + offset for ring in rings]
|
|
|
|
|
|
def scale_lines(lines, scale_x, scale_y, offset_x=0.0, offset_y=0.0):
|
|
"""Comme `scale_rings`, pour une ligne de niveau `(closed, opened)`."""
|
|
return tuple(scale_rings(part, scale_x, scale_y, offset_x, offset_y)
|
|
for part in lines)
|
|
|
|
|
|
def rings_to_d(rings, smooth=True, box=None, precision=3, matrix=None):
|
|
"""Donnees `d` d'un chemin SVG : un sous-chemin ferme par anneau.
|
|
|
|
Avec `smooth`, les points sont relies par une spline de Catmull-Rom
|
|
convertie en courbes de Bezier. `box` = (x0, y0, x1, y1) est le rectangle
|
|
de l'image : les troncons qui le longent restent des droites et les
|
|
courbes n'en sortent pas, pour que le bord des couches reste net.
|
|
|
|
`matrix` = ((a, c, e), (b, d, f)) est une transformation affine appliquee
|
|
aux points ecrits (une courbe de Bezier la subit sans se deformer) ; `box`
|
|
reste exprime dans le repere des anneaux.
|
|
"""
|
|
fmt = _formatter(precision, matrix)
|
|
parts = []
|
|
for ring in rings:
|
|
parts.extend(_subpath(ring, True, smooth, box, fmt))
|
|
return " ".join(parts)
|
|
|
|
|
|
def lines_to_d(lines, smooth=True, box=None, precision=3, matrix=None):
|
|
"""Donnees `d` d'une ligne de niveau `(closed, opened)` : un sous-chemin
|
|
ferme par boucle, un sous-chemin ouvert par ligne aboutissant au bord.
|
|
|
|
Memes options que `rings_to_d`, et meme trace : une ligne ecrite ici se
|
|
superpose exactement au contour de la region qu'elle borde.
|
|
"""
|
|
closed, opened = lines
|
|
fmt = _formatter(precision, matrix)
|
|
parts = []
|
|
for ring in closed:
|
|
parts.extend(_subpath(ring, True, smooth, box, fmt))
|
|
for chain in opened:
|
|
parts.extend(_subpath(chain, False, smooth, box, fmt))
|
|
return " ".join(parts)
|
|
|
|
|
|
def _formatter(precision, matrix):
|
|
"""Ecriture d'un point "x,y", apres transformation affine eventuelle."""
|
|
number = "{:.%df}" % precision
|
|
|
|
def fmt(point):
|
|
x, y = point[0], point[1]
|
|
if matrix is not None:
|
|
(a, c, e), (b, d, f) = matrix
|
|
x, y = a * x + c * y + e, b * x + d * y + f
|
|
return number.format(x) + "," + number.format(y)
|
|
|
|
return fmt
|
|
|
|
|
|
def _subpath(points, closed, smooth, box, fmt):
|
|
"""Commandes SVG d'un anneau (`closed`) ou d'une ligne ouverte."""
|
|
points = np.asarray(points, dtype=float)
|
|
count = len(points)
|
|
if count < (3 if closed else 2):
|
|
return []
|
|
parts = ["M " + fmt(points[0])]
|
|
if not smooth:
|
|
parts.extend("L " + fmt(point) for point in points[1:])
|
|
return parts + ["Z"] if closed else parts
|
|
|
|
on_box, along = _on_box(points, box)
|
|
if not closed:
|
|
# Les extremites d'une ligne ouverte sont sur le bord de l'image :
|
|
# meme traitement que dans l'anneau qui la contient.
|
|
on_box = on_box.copy()
|
|
on_box[[0, -1]] = True
|
|
before = np.roll(points, 1, axis=0)
|
|
after = np.roll(points, -1, axis=0)
|
|
# Sur le bord, la tangente ne doit pas etre tiree par le troncon droit
|
|
# voisin : on la replie sur le point lui-meme.
|
|
tangent = np.where(on_box[:, None], 0.0, (after - before) / 6.0)
|
|
for k in range(count if closed else count - 1):
|
|
nxt = (k + 1) % count
|
|
if along[k]:
|
|
# Le dernier troncon droit est trace par la fermeture « Z ».
|
|
if nxt:
|
|
parts.append("L " + fmt(points[nxt]))
|
|
continue
|
|
chord = (points[nxt] - points[k]) / 6.0
|
|
c1 = points[k] + (chord if on_box[k] else tangent[k])
|
|
c2 = points[nxt] - (chord if on_box[nxt] else tangent[nxt])
|
|
if box is not None:
|
|
c1 = np.clip(c1, box[:2], box[2:])
|
|
c2 = np.clip(c2, box[:2], box[2:])
|
|
parts.append("C {} {} {}".format(fmt(c1), fmt(c2), fmt(points[nxt])))
|
|
return parts + ["Z"] if closed else parts
|
|
|
|
|
|
def _on_box(ring, box):
|
|
"""Pour chaque point de l'anneau : est-il pose sur le rectangle `box`, et
|
|
le segment qui le relie au point suivant longe-t-il un cote de `box` ?"""
|
|
if box is None:
|
|
nowhere = np.zeros(len(ring), dtype=bool)
|
|
return nowhere, nowhere
|
|
x0, y0, x1, y1 = box
|
|
sides = _sides(ring - np.array([x0, y0]), x1 - x0, y1 - y0)
|
|
return sides.any(axis=1), (sides & np.roll(sides, -1, axis=0)).any(axis=1)
|