"""Compute every tile position of a round well in closed form.
The tile grid is computed from a circle model, not reconstructed from the links
that register. Reconstructing it from registered links infers the grid from the
edges that are missing, and on one acquisition placed only 27 of 333 tiles.
The well is round. Each column holds as many fields as fit inside the circle at
that x, so the columns have different heights and the index offset to the next
column is that column's height -- which is why the measured horizontal offsets
were +11, +4, -11, -9, -4, -13 and -5 rather than one number. Fitting the
circle takes four parameters and answers every tile at once::
columns 21, snaked down (even columns top to bottom)
circle radius 10.25 grid units, centre at column 10, row -10
heights 5, 9, 13, 15, 17, 17, 19, 19, 21, 21, 21, 21, 21,
19, 19, 17, 17, 15, 13, 9, 5 SUM = 333
The model was validated by prediction. Seven measured offsets against four free
parameters would only be a fit; the model was then asked to predict the four
neighbours of six sites it had never seen -- 20, 60, 140, 200, 260, 300 -- and
registration confirmed 24 of 24, at peak/mean 23.6 to 53.1 against control
pairs at 9.0 to 15.6. The controls came back at shift (0,0), which is the
no-overlap signature behaving as it should.
Rows are absolute grid rows, not counted from each column's own top. In a round
well every column starts at a different row, so "row 3 of column c" and "row 3
of column c+1" are not side by side. The neighbour is at the same absolute grid
row, which is why :meth:`WellLayout.position` returns absolute rows and
:meth:`WellLayout.neighbours` looks them up directly.
Typical use::
from spacr.ops_layout import round_well_layout
layout = round_well_layout(333)
for a, b, axis in layout.pairs():
shift = register(tile(a), tile(b)) # phase correlation, per 372
"""
from __future__ import annotations
import math
from dataclasses import dataclass
from functools import lru_cache
from typing import Dict, Iterator, List, Optional, Tuple
__all__ = [
"WellLayout",
"round_well_layout",
"MEASURED_WELL",
]
#: The acquisition this model was fitted and then confirmed against:
#: ``(columns, radius, centre column, centre row)`` for well A1 of
#: `screenA/20200202_6W-LaC024A`, 333 sites at 10X.
MEASURED_WELL: Tuple[int, float, int, int] = (21, 10.25, 10, -10)
#: Microns between tile centres at 10X, from the reference implementation's
#: `plate_coordinate`. Measured against a 1267 px pitch, which puts the
#: scale at about 1.01 px/micron with a 213 px overlap on a 1480 px tile.
TILE_PITCH_UM: float = 1280.0
#: ``name -> (column step, row step)``. The four neighbours a tile can
#: have. Vertical steps continue a column; horizontal steps cross to the
#: next one, which is where the varying offset comes from.
DIRECTIONS: Dict[str, Tuple[int, int]] = {
"up": (0, -1),
"down": (0, 1),
"left": (-1, 0),
"right": (1, 0),
}
@dataclass(frozen=True)
[docs]
class WellLayout:
"""A round well's tiles, addressed by site index and by grid position.
:ivar columns: how many columns of fields the acquisition raster has.
:ivar radius: the well's radius, in grid units (one tile pitch = 1).
:ivar centre: ``(column, row)`` of the circle's centre. The row is negative
for the measured well because site 0 is at the top and rows increase
downwards.
:ivar snake: whether the acquisition snakes -- odd columns collected
bottom to top. Micro-Manager's HCS plugin does, which is why the
reference implementation carries a `remap_snake` at all.
:ivar half_tile: half a tile's side, in grid units. A site is kept when its
whole tile lies inside the circle: at ``(dx, dy)`` from the centre,
when ``(|dx| + half_tile)**2 + (|dy| + half_tile)**2 <= radius**2``.
Zero keeps every site whose centre is inside.
The tile has to fit, not its centre. The centre rule holds the
333-field sequencing well and cannot produce the column heights the
1,281-field phenotype well was measured at, for any radius. With the
footprint term both come out as measured, and every column is centred
on the same row.
"""
columns: int = MEASURED_WELL[0]
radius: float = MEASURED_WELL[1]
centre: Tuple[int, int] = (MEASURED_WELL[2], MEASURED_WELL[3])
snake: bool = True
half_tile: float = 0.0
[docs]
def span(self, column: int) -> Optional[Tuple[int, int]]:
"""``(first row, last row)`` of one column, or None if it is empty.
:param column: the column index.
:returns: the inclusive absolute row range of the sites whose whole
tile lies inside the circle -- see :attr:`half_tile`.
"""
if not 0 <= column < self.columns:
return None
across = abs(column - self.centre[0]) + self.half_tile
remainder = self.radius * self.radius - across * across
if remainder < 0:
return None
reach = math.sqrt(remainder) - self.half_tile
if reach < 0:
return None
half = math.floor(reach)
origin = self.centre[1]
return origin - half, origin + half
@property
[docs]
def heights(self) -> List[int]:
"""How many fields each column holds, left to right."""
out = []
for column in range(self.columns):
span = self.span(column)
out.append(0 if span is None else span[1] - span[0] + 1)
return out
@property
[docs]
def site_count(self) -> int:
"""How many tiles the well holds."""
return len(_index(self)[0])
def _walk(self) -> Iterator[Tuple[int, int]]:
"""Every ``(column, row)`` in acquisition order."""
for column in range(self.columns):
span = self.span(column)
if span is None:
continue
top, bottom = span
rows = range(top, bottom + 1)
if self.snake and column % 2:
rows = range(bottom, top - 1, -1)
for row in rows:
yield column, row
[docs]
def positions(self) -> List[Tuple[int, int]]:
"""``site -> (column, row)`` for every site, in index order."""
return list(_index(self)[0])
[docs]
def position(self, site: int) -> Tuple[int, int]:
"""The ``(column, row)`` of one site.
:param site: the site index.
:returns: the column and the absolute grid row -- not the row counted
from this column's own top. See the module note.
:raises IndexError: when the well holds no such site.
"""
places = _index(self)[0]
if not 0 <= site < len(places):
raise IndexError(f"site {site} is outside a well of "
f"{len(places)}")
return places[site]
[docs]
def site(self, column: int, row: int) -> Optional[int]:
"""The site index at one grid position, or None when it is empty.
:param column: the column index.
:param row: the absolute grid row.
:returns: the site index, or None outside the circle.
"""
return _index(self)[1].get((column, row))
[docs]
def neighbours(self, site: int) -> Dict[str, int]:
"""The sites physically adjacent to one site.
At most four candidates, each a real adjacency, rather than a band of
index neighbours such as `max_site_gap`'s window, of which at most four
could touch.
:param site: the site index.
:returns: ``{direction: site}`` for the neighbours that exist.
"""
column, row = self.position(site)
index = _index(self)[1]
found: Dict[str, int] = {}
for name, (dcol, drow) in DIRECTIONS.items():
other = index.get((column + dcol, row + drow))
if other is not None:
found[name] = other
return found
[docs]
def pairs(self) -> List[Tuple[int, int, str]]:
"""Every adjacent pair once, as ``(first, second, axis)``.
Once, not twice: registering a pair in both directions doubles the work
and asks the same question. The axis is "vertical" or "horizontal",
which the caller wants because a vertical link continues a column and a
horizontal one crosses a snake turn -- and because the two carry
different expected shifts.
Ordered by geometry, not by site index: the second tile is always the
one below for a vertical pair and the one to the right for a horizontal
one, because a caller cropping an overlap band assumes that --
`register_edge` takes the bottom of the first and the top of the
second. Ordering by index is wrong on every odd column, because the
raster snakes and in a bottom-to-top column the tile above carries the
higher index. That error is silent: edges are lost while each surviving
component still solves with a residual of 0.00 px.
:returns: the pairs, ordered by their first site.
"""
index = _index(self)[1]
seen: List[Tuple[int, int, str]] = []
for place, site in index.items():
column, row = place
for name in ("down", "right"):
dcol, drow = DIRECTIONS[name]
other = index.get((column + dcol, row + drow))
if other is None:
continue
axis = "vertical" if dcol == 0 else "horizontal"
seen.append((site, other, axis))
return sorted(seen)
[docs]
def micron_position(self, site: int,
pitch: float = TILE_PITCH_UM) -> Tuple[float, float]:
"""Where the reference implementation says a tile is, in microns.
A stitch is scored by its residual against this position, not by how
many tiles were placed.
:param site: the site index.
:param pitch: microns between tile centres.
:returns: ``(x, y)`` in microns, relative to the circle's centre.
"""
column, row = self.position(site)
return ((column - self.centre[0]) * pitch,
(row - self.centre[1]) * pitch)
@lru_cache(maxsize=32)
def _index(layout: "WellLayout"):
"""``(site -> place, place -> site)`` for one layout, walked once.
The walk is the same answer every time and the callers ask for it per
tile, so it is cached on the layout itself -- which is why the class
is a FROZEN dataclass: it has to be hashable for this, and a layout
that could be edited under its own cache would answer for the well it
used to be.
:param layout: the well.
:returns: the ordered places, and the reverse map.
"""
places = tuple(layout._walk())
return places, {place: site for site, place in enumerate(places)}
def _reach(radius: float, half_tile: float) -> int:
"""How many columns either side of the centre hold a whole tile.
:param radius: the circle's radius, in pitches.
:param half_tile: half a tile's side, in pitches.
:returns: the largest ``|dx|`` at which a tile fits, or 0 when none
does.
At a half tile of zero this is ``floor(radius)`` to the bit, because
``sqrt(r * r) == r`` in binary floating point -- which keeps the centre
rule's column count, and so its column indices, as they were.
"""
remainder = radius * radius - half_tile * half_tile
if remainder < 0:
return 0
return max(0, math.floor(math.sqrt(remainder) - half_tile))
def _candidate(radius: float, columns: Optional[int],
half_tile: float) -> WellLayout:
"""The layout one radius gives, centred on its middle column.
:param radius: the circle's radius, in pitches.
:param columns: the column count when it is known, else None.
:param half_tile: half a tile's side, in pitches.
:returns: the layout, which may hold no field at all.
"""
span = columns or 2 * _reach(radius, half_tile) + 1
return WellLayout(columns=span, radius=radius,
centre=(span // 2, -(span // 2)), half_tile=half_tile)
def _exact_radius(site_count: int, half_tile: float,
above: float) -> Optional[float]:
"""A radius inside the window that holds exactly ``site_count`` fields.
:param site_count: how many fields the acquisition holds.
:param half_tile: half a tile's side, in pitches.
:param above: a radius known to hold more than ``site_count``, which
bounds the fields worth looking at.
:returns: the middle of the window of radii holding exactly that many,
or None when there is no such window -- fields entering the circle
together, as a symmetric well's do in fours and eights.
Needed because the search steps the radius by 0.05, and with the
footprint term the radii holding one count can span a ten-thousandth
of a pitch (372 PART 14-L: 1,281 fields at a half tile of 0.5005). So
each grid position's own threshold ``hypot(|dx| + a, |dy| + a)`` is
listed and the window read off directly.
THE MIDDLE, NOT AN EDGE. Bisecting onto the edge was tried first and
found wells no circle holds: at a threshold, the float arithmetic for
``(k, 0)`` and ``(0, k)`` can disagree in the last bit, and a radius
that close keeps two of four mirror-image fields -- a "23-field well".
A window narrower than float noise is refused for the same reason.
"""
reach = int(math.ceil(above)) + 1
entering: Dict[float, int] = {}
for dx in range(reach + 1):
for dy in range(dx, reach + 1):
threshold = math.hypot(dx + half_tile, dy + half_tile)
if threshold > above:
continue
copies = 1 if dx == dy == 0 else 4 if dx == 0 or dx == dy else 8
entering[threshold] = entering.get(threshold, 0) + copies
ordered = sorted(entering)
held = 0
for index, threshold in enumerate(ordered):
held += entering[threshold]
if held > site_count or index + 1 == len(ordered):
return None
if held == site_count:
upper = ordered[index + 1]
if upper - threshold <= 1e-9 * max(1.0, upper):
return None
return (threshold + upper) / 2
return None
[docs]
def round_well_layout(site_count: int = 333,
columns: Optional[int] = None,
half_tile: float = 0.5857) -> WellLayout:
"""The layout whose circle holds exactly ``site_count`` fields.
The measured well is returned unchanged whenever the search lands on
its 333 sites, so the confirmed model is never re-derived. For any
other count the radius is searched -- a well imaged at a different
magnification or a different plate format is the same circle with a
different number of fields in it.
:param site_count: how many tiles the acquisition holds.
:param columns: the column count, when it is known. Derived from the
circle otherwise.
:param half_tile: half a tile's side in tile pitches -- the tile size
over twice the registered pitch. A field is kept when its whole
tile lies inside the circle; zero keeps it when its centre does.
The default is the phenotype acquisition's measured 0.5857. The
sequencing acquisition measured 0.5840, and every value strictly
between 0.5 and 2.0 gives both wells -- 333 and 1,281 fields -- the
column heights they were measured at.
:returns: the layout.
:raises ValueError: when no circle holds exactly that many fields: a count
that no round well produces means the acquisition is not one, and
guessing the nearest would place every tile slightly wrong. Also when
``half_tile`` is negative or not a number.
For one half tile, the count fixes the fields. The number of fields
inside the circle only grows with the radius, so every radius that
holds exactly ``site_count`` holds the same ones. The radius the layout
carries is one of those, not a measurement.
"""
if site_count < 1:
raise ValueError("a well holds at least one field")
half_tile = float(half_tile)
if not half_tile >= 0.0:
raise ValueError(
f"a half tile of {half_tile} pitches is no footprint; it is half "
"the tile's side over the pitch, so zero or more")
measured = WellLayout()
step = 0.05
radius = 0.5
while radius <= site_count:
candidate = _candidate(radius, columns, half_tile)
held = sum(candidate.heights)
if held > site_count:
inside = _exact_radius(site_count, half_tile, radius)
if inside is None:
break
candidate = _candidate(inside, columns, half_tile)
if sum(candidate.heights) != site_count:
break
held = site_count
if held == site_count:
if (site_count == measured.site_count
and candidate.positions() == measured.positions()):
return measured
return candidate
radius += step
raise ValueError(
f"no round well holds exactly {site_count} fields at a half tile of "
f"{half_tile}; the acquisition is not a circle, so its layout has to "
"be measured rather than fitted")