Source code

Download source archive ↓

src/images.py

1"""Deterministic, memory-bounded subsets of Galaxy ImageJ and ImageMagick tools."""
2
3from collections import Counter
4import math
5import random
6import statistics
7import struct
8import zlib
9
10PNG_HEADER = b"\x89PNG\r\n\x1a\n"
11MAX_EDGE = 512
12
13
14def checked_size(width, height):
15    if not 1 <= width <= MAX_EDGE or not 1 <= height <= MAX_EDGE:
16        raise ValueError(f"image dimensions must be within 1–{MAX_EDGE} pixels")
17
18
19def paeth(left, top, diagonal):
20    point = left + top - diagonal
21    nearby = (left, top, diagonal)
22    return min(nearby, key=lambda value: abs(point - value))
23
24
25def decode_png(data):
26    if not data.startswith(PNG_HEADER):
27        raise ValueError("expected a PNG image")
28    offset = len(PNG_HEADER)
29    width = height = 0
30    compressed = bytearray()
31    ended = False
32    while offset + 12 <= len(data):
33        size, kind = struct.unpack_from(">I4s", data, offset)
34        stop = offset + 8 + size
35        if stop + 4 > len(data):
36            raise ValueError("truncated PNG chunk")
37        payload = data[offset + 8:stop]
38        crc, = struct.unpack_from(">I", data, stop)
39        if zlib.crc32(kind + payload) != crc:
40            raise ValueError("invalid PNG chunk checksum")
41        if offset == len(PNG_HEADER) and kind != b"IHDR":
42            raise ValueError("missing PNG header")
43        if kind == b"IHDR":
44            if offset != len(PNG_HEADER) or size != 13:
45                raise ValueError("invalid PNG header")
46            width, height, depth, color, mode, filtering, interlace = struct.unpack(">II5B", payload)
47            checked_size(width, height)
48            if (depth, color, mode, filtering, interlace) != (8, 0, 0, 0, 0):
49                raise ValueError("expected an 8-bit noninterlaced grayscale PNG")
50        elif kind == b"IDAT":
51            compressed.extend(payload)
52        elif kind == b"IEND":
53            ended = not size and stop + 4 == len(data)
54            break
55        elif kind in {b"tRNS", b"acTL", b"fcTL", b"fdAT"} or not kind[0] & 32:
56            raise ValueError("unsupported PNG transparency, animation or critical chunk")
57        offset = stop + 4
58    if not ended or not compressed:
59        raise ValueError("incomplete PNG image")
60    expected = (width + 1) * height
61    decoder = zlib.decompressobj()
62    try:
63        raw = decoder.decompress(compressed, expected + 1)
64    except zlib.error as error:
65        raise ValueError("invalid PNG raster data") from error
66    if len(raw) != expected or not decoder.eof or decoder.unused_data:
67        raise ValueError("invalid PNG raster length")
68
69    rows = []
70    previous = bytes(width)
71    for offset in range(0, len(raw), width + 1):
72        kind = raw[offset]
73        if kind > 4:
74            raise ValueError("invalid PNG row filter")
75        row = bytearray(raw[offset + 1:offset + 1 + width])
76        if kind:
77            for x in range(width):
78                left, top = row[x - 1] if x else 0, previous[x]
79                diagonal = previous[x - 1] if x else 0
80                correction = (left, top, (left + top) // 2, paeth(left, top, diagonal))[kind - 1]
81                row[x] = (row[x] + correction) & 255
82        previous = bytes(row)
83        rows.append(previous)
84    return rows
85
86
87def encode_png(rows):
88    width, height = len(rows[0]), len(rows)
89    checked_size(width, height)
90    if any(len(row) != width for row in rows):
91        raise ValueError("invalid raster shape")
92
93    def chunk(kind, payload):
94        return struct.pack(">I", len(payload)) + kind + payload + struct.pack(">I", zlib.crc32(kind + payload))
95
96    header = struct.pack(">II5B", width, height, 8, 0, 0, 0, 0)
97    raster = b"".join(b"\0" + row for row in rows)
98    return PNG_HEADER + chunk(b"IHDR", header) + chunk(b"IDAT", zlib.compress(raster, 6)) + chunk(b"IEND", b"")
99
100
101def pixel(value):
102    return max(0, min(255, math.floor(value + 0.5)))
103
104
105def pointwise(rows, fn):
106    return [bytes(pixel(fn(value)) for value in row) for row in rows]
107
108
109POINT = {
110    "add": lambda x, value: x + value,
111    "subtract": lambda x, value: x - value,
112    "multiply": lambda x, value: x * value,
113    "divide": lambda x, value: x / value,
114    "and": lambda x, value: x & value,
115    "or": lambda x, value: x | value,
116    "xor": lambda x, value: x ^ value,
117    "min": lambda x, value: max(x, value),
118    "max": lambda x, value: min(x, value),
119    "gamma": lambda x, value: 255 * (x / 255) ** value,
120    "set": lambda x, value: value,
121    "log": lambda x, _: math.log(x) * 255 / math.log(255) if x else 0,
122    "exp": lambda x, _: math.exp(x * math.log(255) / 255),
123    "square": lambda x, _: x * x,
124    "sqrt": lambda x, _: math.sqrt(x),
125}
126
127
128def neighbourhood(rows, radius):
129    width, height = len(rows[0]), len(rows)
130    for y in range(height):
131        yield (
132            [rows[max(0, min(height - 1, y + dy))][max(0, min(width - 1, x + dx))]
133             for dy in range(-radius, radius + 1) for dx in range(-radius, radius + 1)]
134            for x in range(width)
135        )
136
137
138def filter_pixels(rows, radius, fn):
139    return [bytes(pixel(fn(samples)) for samples in group) for group in neighbourhood(rows, radius)]
140
141
142def gaussian_filter(rows):
143    kernel = (1, 2, 1, 2, 4, 2, 1, 2, 1)
144    return filter_pixels(rows, 1, lambda v: sum(a * b for a, b in zip(v, kernel)) / 16)
145
146
147def local_variance(values):
148    mean = sum(values) / len(values)
149    return sum(x * x for x in values) / len(values) - mean * mean
150
151
152def neighbourhood_filter(rows, op, params):
153    if op == "gaussian_blur":
154        return gaussian_filter(rows)
155    radius = params.get("radius", 1)
156    if op == "unsharp_mask":
157        blurred = gaussian_filter(rows)
158        return [bytes(pixel(a + params["amount"] * (a - b)) for a, b in zip(row, smooth))
159                for row, smooth in zip(rows, blurred)]
160    if op == "top_hat":
161        opened = filter_pixels(filter_pixels(rows, radius, min), radius, max)
162        return [bytes(max(0, a - b) for a, b in zip(row, damped)) for row, damped in zip(rows, opened)]
163    math_filters = {"mean": statistics.fmean, "median": statistics.median, "minimum": min,
164                    "maximum": max, "variance": local_variance}
165    if op in math_filters:
166        return filter_pixels(rows, radius, math_filters[op])
167    if op == "sharpen":
168        return filter_pixels(rows, 1, lambda v: (12 * v[4] - sum(v) + v[4]) / 4)
169
170    def magnitude(v):
171        top, bottom = v[0] + 2 * v[1] + v[2], v[6] + 2 * v[7] + v[8]
172        left, right = v[0] + 2 * v[3] + v[6], v[2] + 2 * v[5] + v[8]
173        return math.hypot(right - left, bottom - top)
174
175    if op == "edges":
176        return filter_pixels(rows, 1, magnitude)
177    raise ValueError("unknown image filter")
178
179
180def geometry(rows, op, params):
181    width, height = len(rows[0]), len(rows)
182    if op == "flip":
183        return list(reversed(rows))
184    if op == "flop":
185        return [row[::-1] for row in rows]
186    if op == "rotate_90":
187        return [bytes(column) for column in zip(*reversed(rows))]
188    if op == "rotate_270":
189        return [bytes(column) for column in reversed(list(zip(*rows)))]
190    if op == "rotate_180":
191        return [row[::-1] for row in reversed(rows)]
192    if op == "resize":
193        target_width = max(1, pixel_dimension(width * params["percent"] / 100))
194        target_height = max(1, pixel_dimension(height * params["percent"] / 100))
195        checked_size(target_width, target_height)
196        columns = [(2 * x + 1) * width // (2 * target_width) for x in range(target_width)]
197        return [bytes(rows[(2 * y + 1) * height // (2 * target_height)][x] for x in columns)
198                for y in range(target_height)]
199    if op == "trim":
200        side, n = params["edge"], params["pixels"]
201        return geometry(rows, "crop", dict(
202            x=n if side == "west" else 0, y=n if side == "north" else 0,
203            width=width - n if side in ("east", "west") else width,
204            height=height - n if side in ("north", "south") else height))
205    x, y, w, h = (params[p] for p in ("x", "y", "width", "height"))
206    if w < 1 or h < 1 or x + w > width or y + h > height:
207        raise ValueError("crop rectangle lies outside the image")
208    return [row[x:x + w] for row in rows[y:y + h]]
209
210
211def pixel_dimension(value):
212    return math.floor(value + 0.5)
213
214
215def tonal(rows, op, params):
216    histogram = Counter(value for row in rows for value in row)
217    count = sum(histogram.values())
218    if op == "threshold_manual":
219        return pointwise(rows, lambda x: 255 if params["low"] <= x <= params["high"] else 0)
220    if op in ("threshold_mean", "threshold_otsu"):
221        total = sum(x * n for x, n in histogram.items())
222        threshold = total / count
223        if op == "threshold_otsu":
224            best = -1
225            seen = weighted = 0
226            for x in range(255):
227                seen += histogram[x]
228                weighted += x * histogram[x]
229                if 0 < seen < count:
230                    score = (weighted * count - total * seen) ** 2 / (seen * (count - seen))
231                    if score > best:
232                        best, threshold = score, x
233        return pointwise(rows, lambda x: 255 if x > threshold else 0)
234    lo, hi = min(histogram), max(histogram)
235    if lo == hi:
236        return rows
237    if op == "stretch":
238        return pointwise(rows, lambda x: (x - lo) * 255 / (hi - lo))
239    count_min = histogram[lo]
240    cumulative = 0
241    table = {}
242    for x in sorted(histogram):
243        cumulative += histogram[x]
244        table[x] = 255 * (cumulative - count_min) / (count - count_min)
245    return pointwise(rows, table.__getitem__)
246
247
248def noise(rows, op, params):
249    rng = random.Random(params["seed"])
250    if op == "gaussian_noise":
251        return pointwise(rows, lambda x: x + rng.gauss(0, params["sigma"]))
252    probability = params["probability"]
253    def impulse(x):
254        draw = rng.random()
255        return 0 if draw < probability / 2 else 255 if draw < probability else x
256    return pointwise(rows, impulse)
257
258
259def compare(rows, other, op):
260    if len(rows) != len(other) or len(rows[0]) != len(other[0]):
261        raise ValueError("comparison requires images with the same dimensions")
262    left, right = b"".join(rows), b"".join(other)
263    error = [abs(a - b) for a, b in zip(left, right)]
264    mse = statistics.fmean(x * x for x in error) / 255 ** 2
265    if op == "ncc":
266        a, b = statistics.fmean(left), statistics.fmean(right)
267        numerator = math.fsum((x - a) * (y - b) for x, y in zip(left, right))
268        denominator = math.sqrt(math.fsum((x - a) ** 2 for x in left) * math.fsum((y - b) ** 2 for y in right))
269        value = numerator / denominator if denominator else "NA"
270    elif op == "psnr":
271        value = -10 * math.log10(mse) if mse else "inf"
272    else:
273        metrics = {"ae": lambda: sum(n != 0 for n in error), "mae": lambda: statistics.fmean(error) / 255,
274                   "mse": lambda: mse, "pae": lambda: max(error) / 255, "rmse": lambda: math.sqrt(mse)}
275        value = metrics[op]()
276    formatted = value if isinstance(value, str) else format(value or 0, ".12g")
277    return f"metric\tvalue\n{op.upper()}\t{formatted}\n".encode()
278
279
280def execute(operation, inputs, params):
281    rows = decode_png(inputs["source"])
282    category, op = operation.split("/", 1)
283    if category == "compare":
284        return compare(rows, decode_png(inputs["reference"]), op)
285    if category == "combine":
286        other = decode_png(inputs["reference"])
287        if op == "montage":
288            left, right = len(rows[0]), len(other[0])
289            checked_size(left + right, max(len(rows), len(other)))
290            output = [(rows[y] if y < len(rows) else bytes(left)) +
291                      (other[y] if y < len(other) else bytes(right))
292                      for y in range(max(len(rows), len(other)))]
293        else:
294            if len(rows) != len(other) or len(rows[0]) != len(other[0]):
295                raise ValueError("composite requires images with the same dimensions")
296            weight = params["opacity"]
297            output = [bytes(pixel((1 - weight) * a + weight * b) for a, b in zip(r1, r2))
298                      for r1, r2 in zip(rows, other)]
299        return encode_png(output)
300    if category == "point":
301        value = params.get("value")
302        if op == "divide" and value == 0:
303            raise ValueError("divisor must be positive")
304        output = pointwise(rows, lambda x: POINT[op](x, value))
305    elif category == "geometry":
306        output = geometry(rows, op, params)
307    elif category == "filter":
308        output = neighbourhood_filter(rows, op, params)
309    elif category == "tone":
310        if op == "threshold_manual" and params["low"] > params["high"]:
311            raise ValueError("minimum threshold exceeds maximum")
312        output = tonal(rows, op, params)
313    else:
314        output = noise(rows, op, params)
315    return encode_png(output)