Source code

Download source archive ↓

src/image_extra.py

1"""Grayscale image math, segmentation and measurements from Galaxy tools."""
2
3from collections import deque
4from itertools import accumulate
5import math
6import statistics
7
8from images import decode_png, encode_png, filter_pixels, pixel, pointwise
9
10BINARY = {
11    "add": lambda a, b: a + b,
12    "subtract": lambda a, b: a - b,
13    "difference": lambda a, b: abs(a - b),
14    "multiply": lambda a, b: a * b / 255,
15    "divide": lambda a, b: 255 * a / b if b else (255 if a else 0),
16    "minimum": min,
17    "maximum": max,
18    "and": lambda a, b: 255 * bool(a and b),
19    "or": lambda a, b: 255 * bool(a or b),
20    "equals": lambda a, b: 255 * (a == b),
21}
22
23
24def neighbours(x, y, width, height, connectivity):
25    for dy in (-1, 0, 1):
26        for dx in (-1, 0, 1):
27            if (dx or dy) and (connectivity == 8 or not (dx and dy)):
28                xx, yy = x + dx, y + dy
29                if 0 <= xx < width and 0 <= yy < height:
30                    yield xx, yy
31
32
33def regions(rows, accept, connectivity):
34    height, width = len(rows), len(rows[0])
35    visited = set()
36    for y, row in enumerate(rows):
37        for x, value in enumerate(row):
38            if not accept(value, value) or (x, y) in visited:
39                continue
40            points = []
41            queue = deque([(x, y)])
42            visited.add((x, y))
43            while queue:
44                cx, cy = queue.popleft()
45                points.append((cx, cy))
46                for xx, yy in neighbours(cx, cy, width, height, connectivity):
47                    if (xx, yy) not in visited and accept(value, rows[yy][xx]):
48                        visited.add((xx, yy))
49                        queue.append((xx, yy))
50            yield value, points
51
52
53def raster_for(rows, points):
54    output = [bytearray(len(row)) for row in rows]
55    for x, y in points:
56        output[y][x] = 255
57    return [bytes(row) for row in output]
58
59
60def peaks(rows, cutoff):
61    height, width = len(rows), len(rows[0])
62    for value, group in regions(rows, lambda a, b: a >= cutoff and a == b, 8):
63        adjacent = (rows[yy][xx] for x, y in group for xx, yy in neighbours(x, y, width, height, 8))
64        if all(other <= value for other in adjacent):
65            x, y = group[0]
66            yield x, y, value
67
68
69def binary(rows):
70    if any(value not in (0, 255) for row in rows for value in row):
71        raise ValueError("expected a binary mask with values 0 or 255")
72    return rows
73
74
75def particles(rows, min_area, connectivity):
76    for _, group in regions(binary(rows), lambda a, b: bool(b), connectivity):
77        if len(group) >= min_area:
78            yield group
79
80
81def distance_line(values):
82    sites = []
83    boundaries = []
84    for index, value in enumerate(values):
85        if not math.isfinite(value):
86            continue
87        while sites:
88            last = sites[-1]
89            boundary = (value + index*index - values[last] - last*last) / (2*(index - last))
90            if boundary > boundaries[-1]:
91                break
92            sites.pop()
93            boundaries.pop()
94        if not sites:
95            boundary = -math.inf
96        sites.append(index)
97        boundaries.append(boundary)
98    if not sites:
99        return [math.inf] * len(values)
100    result = []
101    position = 0
102    for i in range(len(values)):
103        while position + 1 < len(sites) and boundaries[position + 1] < i:
104            position += 1
105        site = sites[position]
106        result.append((i - site)**2 + values[site])
107    return result
108
109
110def distance(rows):
111    if not any(0 in row for row in binary(rows)):
112        raise ValueError("distance map requires at least one background pixel")
113    horizontal = [distance_line([math.inf if x else 0 for x in row]) for row in rows]
114    vertical = [distance_line(column) for column in zip(*horizontal)]
115    return [bytes(pixel(math.sqrt(d)) for d in row) for row in zip(*vertical)]
116
117
118def threshold(rows, method):
119    counts = [0] * 256
120    for row in rows:
121        for value in row:
122            counts[value] += 1
123    n = sum(counts)
124    mass = [count / n for count in counts]
125    cumulative = list(accumulate(mass))
126    if method == "percentile":
127        return min(range(256), key=lambda t: abs(cumulative[t] - 0.5))
128    first = next(i for i, count in enumerate(counts) if count)
129    last = max(i for i, count in enumerate(counts) if count)
130    if first == last:
131        return first
132    best_score, cut = -math.inf, first
133    if method == "max_entropy":
134        entropy = list(accumulate(-p * math.log(p) if p else 0 for p in mass))
135        for t in range(first, last):
136            low, high = cumulative[t], 1 - cumulative[t]
137            score = entropy[t] / low + (entropy[-1] - entropy[t]) / high + math.log(low*high)
138            if score > best_score + 1e-12:
139                best_score, cut = score, t
140    else:
141        squares = list(accumulate(p*p for p in mass))
142        for t in range(first, last):
143            low, high = cumulative[t], 1 - cumulative[t]
144            metric = squares[t] * (squares[-1] - squares[t])
145            if metric <= 0 or low * high <= 0:
146                continue
147            score = -math.log(metric) + 2 * math.log(low * high)
148            if score > best_score + 1e-12:
149                best_score, cut = score, t
150    return cut
151
152
153def execute(operation, inputs, params):
154    category, name = operation.split("/", 1)
155    rows = decode_png(inputs["source"])
156    width, height = len(rows[0]), len(rows)
157    if category == "pair":
158        other = decode_png(inputs["reference"])
159        if len(other) != height or len(other[0]) != width:
160            raise ValueError("both images must have the same dimensions")
161        op = ((lambda a, b: a if bool(b) != params["invert"] else 0)
162              if name == "mask" else BINARY[name])
163        return encode_png([bytes(pixel(op(a, b)) for a, b in zip(r, s)) for r, s in zip(rows, other)])
164    if category == "unary":
165        if name == "log_legacy":
166            return "".join("\t".join(format(math.log2(v / 255), ".12g") if v else "-inf" for v in row) + "\n"
167                           for row in rows).encode()
168        function = {"invert": lambda v: 255-v, "not": lambda v: 255*(v==0),
169                    "log_2": lambda v: 255*math.log2(1+v/255)}[name]
170        return encode_png(pointwise(rows, function))
171    if category == "peak":
172        points = list(peaks(rows, params["minimum"]))
173        if name == "count":
174            return f"count\n{len(points)}\n".encode()
175        if name == "coordinates":
176            return ("x\ty\tvalue\n" + "".join(f"{x}\t{y}\t{v}\n" for x, y, v in points)).encode()
177        return encode_png(raster_for(rows, ((x, y) for x, y, _ in points)))
178    if category == "particles":
179        objects = list(particles(rows, params["min_area"], params["connectivity"]))
180        if name == "measure":
181            result = ["particle\tarea\tcenter_x\tcenter_y\n"]
182            for index, item in enumerate(objects, 1):
183                x, y = zip(*item)
184                result.append(f"{index}\t{len(item)}\t{statistics.fmean(x):.12g}\t{statistics.fmean(y):.12g}\n")
185            return "".join(result).encode()
186        if name == "outlines":
187            def inner(x, y):
188                surrounding = list(neighbours(x, y, width, height, 4))
189                return len(surrounding) == 4 and all(rows[yy][xx] for xx, yy in surrounding)
190            points = ((x, y) for item in objects for x, y in item if not inner(x, y))
191        else:
192            points = (point for item in objects for point in item)
193        return encode_png(raster_for(rows, points))
194    if category == "threshold":
195        cutoff = threshold(rows, name)
196        return encode_png(pointwise(rows, lambda value: 255 if value > cutoff else 0))
197    if name == "edm":
198        return encode_png(distance(rows))
199    radius = params["radius"]
200    center = (2 * radius + 1)**2 // 2
201    direction = 1 if params["bright"] else -1
202
203    def replace(values):
204        median = statistics.median(values)
205        old = values[center]
206        return median if (old - median) * direction > params["difference"] else old
207
208    return encode_png(filter_pixels(rows, radius, replace))