fp2 / src /fiberpose /ridge_detector.py
vikba's picture
Upload folder using huggingface_hub
beb4f15 verified
Raw History Blame Contribute Delete
23 kB
"""
Steger ridge/line detection (exact math) with Numba speedups.
- RidgeDetector class with public detect_ridges()
- Public API returns detected polylines as plain NumPy arrays
- Convolution and candidate kernels are JIT-compiled with numba without fastmath to preserve quality
- Contour linking is traced in numba; Python only assembles the output polylines
Usage:
det = RidgeDetector()
polylines = det.detect_ridges(img, sigma=2.0, low=8, high=15, polarity="dark")
"""
from __future__ import annotations
from typing import List, Tuple
import math
import numpy as np
import numba as nb
# -------------------------
# Numba kernels
# -------------------------
@nb.njit(cache=True)
def _mirror_r_jit(r: int, h: int) -> int:
if r < 0:
return -r
if r >= h:
return h - r + h - 2
return r
@nb.njit(cache=True)
def _mirror_c_jit(c: int, w: int) -> int:
if c < 0:
return -c
if c >= w:
return w - c + w - 2
return c
@nb.njit(cache=True)
def _convolve_rows_flat(image: np.ndarray, mask: np.ndarray, n: int, w: int, h: int) -> np.ndarray:
out = np.empty((w * h,), dtype=np.float32)
# inner
for r in range(n, h - n):
base = r * w
for c in range(w):
l = base + c
s = 0.0
for j in range(-n, n + 1):
s += float(image[l + j * w]) * float(mask[j + n])
out[l] = np.float32(s)
# borders top
for r in range(0, n):
base = r * w
for c in range(w):
l = base + c
s = 0.0
for j in range(-n, n + 1):
rr = _mirror_r_jit(r + j, h)
s += float(image[rr * w + c]) * float(mask[j + n])
out[l] = np.float32(s)
# borders bottom
for r in range(h - n, h):
base = r * w
for c in range(w):
l = base + c
s = 0.0
for j in range(-n, n + 1):
rr = _mirror_r_jit(r + j, h)
s += float(image[rr * w + c]) * float(mask[j + n])
out[l] = np.float32(s)
return out
@nb.njit(cache=True)
def _convolve_cols_flat(tmp: np.ndarray, mask: np.ndarray, n: int, w: int, h: int) -> np.ndarray:
out = np.empty((w * h,), dtype=np.float32)
# inner
for r in range(h):
base = r * w
for c in range(n, w - n):
l = base + c
s = 0.0
for j in range(-n, n + 1):
s += float(tmp[l + j]) * float(mask[j + n])
out[l] = np.float32(s)
# borders
for r in range(h):
base = r * w
for c in range(0, n):
l = base + c
s = 0.0
for j in range(-n, n + 1):
cc = _mirror_c_jit(c + j, w)
s += float(tmp[base + cc]) * float(mask[j + n])
out[l] = np.float32(s)
for c in range(w - n, w):
l = base + c
s = 0.0
for j in range(-n, n + 1):
cc = _mirror_c_jit(c + j, w)
s += float(tmp[base + cc]) * float(mask[j + n])
out[l] = np.float32(s)
return out
@nb.njit(cache=True)
def _solve_linear_jit(a: float, b: float) -> Tuple[int, float]:
if a == 0.0:
return 0, 0.0
return 1, -b / a
@nb.njit(cache=True)
def _eigen_2x2_jit(drr: float, drc: float, dcc: float) -> Tuple[float, float, float, float]:
"""
Returns (e1, e2, v0x, v0y) where (v0x, v0y) is eigenvector for the principal eigenvalue
following the same selection logic as the Java port.
"""
if drc != 0.0:
theta = 0.5 * (dcc - drr) / drc
t = 1.0 / (abs(theta) + math.sqrt(theta * theta + 1.0))
if theta < 0.0:
t = -t
c = 1.0 / math.sqrt(t * t + 1.0)
s = t * c
e1 = drr - t * drc
e2 = dcc + t * drc
else:
c = 1.0
s = 0.0
e1 = drr
e2 = dcc
n1 = c
n2 = -s
# choose ordering like original (by abs)
if abs(e1) > abs(e2):
return e1, e2, n1, n2
elif abs(e1) < abs(e2):
# swapped
return e2, e1, -n2, n1
else:
if e1 < e2:
return e1, e2, n1, n2
else:
return e2, e1, -n2, n1
@nb.njit(cache=True)
def _ridge_candidates_jit(dr, dc, drr, drc, dcc, w: int, h: int,
low: float, high: float, mode: int,
pixel_boundary: float) -> Tuple[np.ndarray, np.ndarray, np.ndarray, np.ndarray, np.ndarray, np.ndarray]:
N = w * h
ismax = np.zeros((N,), dtype=np.uint8)
ev = np.zeros((N,), dtype=np.float32)
nx = np.zeros((N,), dtype=np.float32)
ny = np.zeros((N,), dtype=np.float32)
px = np.zeros((N,), dtype=np.float32)
py = np.zeros((N,), dtype=np.float32)
for r in range(h):
for c in range(w):
l = r * w + c
e1, _, v0x, v0y = _eigen_2x2_jit(float(drr[l]), float(drc[l]), float(dcc[l]))
val = -e1 if mode == 1 else e1 # 1=light, 2=dark
if val <= 0.0:
continue
ev[l] = np.float32(val)
n1 = v0x
n2 = v0y
a = float(drr[l]) * n1 * n1 + 2.0 * float(drc[l]) * n1 * n2 + float(dcc[l]) * n2 * n2
b = float(dr[l]) * n1 + float(dc[l]) * n2
ok, t = _solve_linear_jit(a, b)
if ok == 0:
continue
p1 = t * n1
p2 = t * n2
if abs(p1) <= pixel_boundary and abs(p2) <= pixel_boundary:
if val >= low:
ismax[l] = 2 if val >= high else 1
nx[l] = np.float32(n1)
ny[l] = np.float32(n2)
px[l] = np.float32(r + p1)
py[l] = np.float32(c + p2)
return ismax, ev, nx, ny, px, py
# -------------------------
# Numba kernels for link_contours
# -------------------------
@nb.njit(cache=True, fastmath=True, boundscheck=True)
def _trace_one_direction(
x0, y0,
dir_flag, # 1 = forward, 2 = backward
ismax, px, py,
alpha_arr, oct4_arr,
label, indx, cross_done,
w, h,
DIRTAB, CLEARTAB,
max_angle_diff,
line_id,
out_x, out_y,
out_start
):
"""
Traces one direction starting at (x0,y0) excluding the seed itself.
Writes points to flat arrays starting at out_start.
Returns the next free output index.
"""
x = x0
y = y0
p = x * w + y
last_oct = int(oct4_arr[p]) # 0..3
if dir_flag == 2:
last_oct += 4
out_i = out_start
while True:
p = x * w + y
pxx = px[p]
pyy = py[p]
alpha_p = alpha_arr[p]
octant = int(oct4_arr[p]) # 0..3
# unwrap octant to 0..7
if octant == 0 and 3 <= last_oct <= 5:
octant = 4
elif octant == 1 and 4 <= last_oct <= 6:
octant = 5
elif octant == 2 and 4 <= last_oct <= 7:
octant = 6
elif octant == 3 and (last_oct == 0 or last_oct >= 6):
octant = 7
last_oct = octant
# choose next among 3 candidates
nextismax = 0
nexti = 1
mindiff = 1e30
for i in range(3):
xx = x + int(DIRTAB[octant, i, 0])
yy = y + int(DIRTAB[octant, i, 1])
if xx < 0 or xx >= h or yy < 0 or yy >= w:
continue
pp = xx * w + yy
if ismax[pp] == 0:
continue
npx = px[pp]
npy = py[pp]
dx = npx - pxx
dy = npy - pyy
dist = np.sqrt(dx*dx + dy*dy)
na = alpha_arr[pp]
diff = abs(alpha_p - na)
if diff >= 0.5*np.pi:
diff = np.pi - diff
score = dist + diff
if score < mindiff:
mindiff = score
nexti = i
nextismax = 1
# clear double responses
for i in range(2):
xx = x + int(CLEARTAB[octant, i, 0])
yy = y + int(CLEARTAB[octant, i, 1])
if 0 <= xx < h and 0 <= yy < w:
pp = xx * w + yy
if ismax[pp] > 0:
na = alpha_arr[pp]
diff = abs(alpha_p - na)
if diff >= 0.5*np.pi:
diff = np.pi - diff
if diff < max_angle_diff:
label[pp] = line_id
idx = indx[pp]
if idx != 0:
cross_done[idx - 1] = True
if nextismax == 0:
break
# step
x += int(DIRTAB[octant, nexti, 0])
y += int(DIRTAB[octant, nexti, 1])
pp = x * w + y
if out_i >= out_x.shape[0]:
return out_i
# append point (excluding seed)
out_x[out_i] = px[pp]
out_y[out_i] = py[pp]
out_i += 1
if label[pp] > 0:
break
label[pp] = line_id
idx = indx[pp]
if idx != 0:
cross_done[idx - 1] = True
return out_i
@nb.njit(cache=True, fastmath=True, boundscheck=True)
def _link_contours_trace_numba(
cross_x, cross_y, cross_val, cross_done,
ismax, px, py,
alpha_arr, oct4_arr,
indx,
w, h,
DIRTAB, CLEARTAB,
max_angle_diff
):
area = cross_x.shape[0]
label = np.zeros((w*h,), dtype=np.int32)
# Worst-case points: each ridge pixel at most once per line, but safe upper bound is area*2
max_points = area * 2 + 8
pts_x = np.empty((max_points,), dtype=np.float32)
pts_y = np.empty((max_points,), dtype=np.float32)
# line offsets (start index into flat arrays)
line_offsets = np.empty((area + 1,), dtype=np.int32)
line_count = 0
out_i = 0
indx_max = 0
while True:
while indx_max < area and cross_done[indx_max]:
indx_max += 1
if indx_max == area:
break
maxv = float(cross_val[indx_max])
if maxv == 0.0:
break
x0 = int(cross_x[indx_max])
y0 = int(cross_y[indx_max])
pos0 = x0*w + y0
line_id = line_count + 1
label[pos0] = line_id
idx0 = indx[pos0]
if idx0 != 0:
cross_done[idx0 - 1] = True
if out_i >= pts_x.shape[0]:
break # or return what you have
# seed point
line_offsets[line_count] = out_i
pts_x[out_i] = px[pos0]
pts_y[out_i] = py[pos0]
alpha0 = alpha_arr[pos0] # [0,π)
out_i += 1
# clear double responses around seed (uses oct4)
octant0 = int(oct4_arr[pos0])
for i in range(2):
xx = x0 + int(CLEARTAB[octant0, i, 0])
yy = y0 + int(CLEARTAB[octant0, i, 1])
if 0 <= xx < h and 0 <= yy < w:
p = xx*w + yy
if ismax[p] > 0:
na = alpha_arr[p]
diff = abs(alpha0 - na)
if diff >= 0.5*np.pi:
diff = np.pi - diff
if diff < max_angle_diff:
label[p] = line_id
idxp = indx[p]
if idxp != 0:
cross_done[idxp - 1] = True
# Trace backward first and reverse it in place, then trace forward, so points run end to end.
tmp_start = out_i
tmp_end = _trace_one_direction(
x0, y0, 2,
ismax, px, py,
alpha_arr, oct4_arr,
label, indx, cross_done,
w, h,
DIRTAB, CLEARTAB,
max_angle_diff,
line_id,
pts_x, pts_y,
tmp_start
)
tmp_len = tmp_end - tmp_start
# reverse the backward segment in-place (so it becomes prepended)
for k in range(tmp_len // 2):
a = tmp_start + k
b = tmp_start + (tmp_len - 1 - k)
# swap x,y
tx = pts_x[a]; pts_x[a] = pts_x[b]; pts_x[b] = tx
ty = pts_y[a]; pts_y[a] = pts_y[b]; pts_y[b] = ty
out_i = tmp_end
# forward direction appends after seed+backward
out_i = _trace_one_direction(
x0, y0, 1,
ismax, px, py,
alpha_arr, oct4_arr,
label, indx, cross_done,
w, h,
DIRTAB, CLEARTAB,
max_angle_diff,
line_id,
pts_x, pts_y,
out_i
)
# keep only lines with >=2 points
line_len = out_i - line_offsets[line_count]
if line_len > 1:
line_count += 1
else:
# drop seed point
out_i = line_offsets[line_count]
label[pos0] = 0
line_offsets[line_count] = out_i
# trim outputs
pts_x = pts_x[:out_i]
pts_y = pts_y[:out_i]
line_offsets = line_offsets[:line_count+1]
return pts_x, pts_y, line_offsets
# -------------------------
# Detector
# -------------------------
class RidgeDetector:
"""Represent ridge detector state used across processing and visualization workflows."""
DERIV_R, DERIV_C, DERIV_RR, DERIV_RC, DERIV_CC = 1, 2, 3, 4, 5
MODE_LIGHT, MODE_DARK = 1, 2
MAX_SIZE_MASK_0 = 3.09023230616781
MAX_SIZE_MASK_1 = 3.46087178201605
MAX_SIZE_MASK_2 = 3.82922419517181
SQRT_2_PI_INV = 0.398942280401432677939946059935
PIXEL_BOUNDARY = 0.6
MAX_ANGLE_DIFFERENCE = math.pi / 6.0
_DIRTAB = np.array([
[[ 1, 0],[ 1,-1],[ 1, 1]],
[[ 1, 1],[ 1, 0],[ 0, 1]],
[[ 0, 1],[ 1, 1],[-1, 1]],
[[-1, 1],[ 0, 1],[-1, 0]],
[[-1, 0],[-1, 1],[-1,-1]],
[[-1,-1],[-1, 0],[ 0,-1]],
[[ 0,-1],[-1,-1],[ 1,-1]],
[[ 1,-1],[ 0,-1],[ 1, 0]],
], dtype=np.int32)
_CLEARTAB = np.array([
[[ 0, 1],[ 0,-1]],
[[-1, 1],[ 1,-1]],
[[-1, 0],[ 1, 0]],
[[-1,-1],[ 1, 1]],
[[ 0,-1],[ 0, 1]],
[[ 1,-1],[-1, 1]],
[[ 1, 0],[-1, 0]],
[[ 1, 1],[-1,-1]],
], dtype=np.int32)
# -------------------------
# Public API
# -------------------------
@classmethod
def detect_ridges(
cls,
image2d: np.ndarray,
*,
sigma: float = 1.5,
low: float = 5.0,
high: float = 10.0,
polarity: str = "dark",
) -> List[np.ndarray]:
img = np.asarray(image2d, dtype=np.float32)
if img.ndim != 2:
raise ValueError("image must be 2D grayscale")
h, w = img.shape
mode = cls.MODE_DARK if polarity.lower() == "dark" else cls.MODE_LIGHT
dr, dc, drr, drc, dcc = cls._gauss_derivatives(img, sigma)
ismax, ev, nx, ny, px, py = cls._ridge_candidates(dr, dc, drr, drc, dcc, w, h, low, high, mode)
alpha, oct4 = cls._precompute_angles(nx, ny)
return cls._link_contours(ismax, ev, px, py, w, h, alpha, oct4)
# -------------------------
# Helpers
# -------------------------
@staticmethod
def _mask_size(maxv: float, sigma: float) -> int:
return int(math.ceil(maxv * sigma))
@staticmethod
def _phi0(x: float, sigma: float) -> float:
return 0.5 * (1.0 + math.erf(x / (sigma * math.sqrt(2.0))))
@classmethod
def _phi1(cls, x: float, sigma: float) -> float:
t = x / sigma
return cls.SQRT_2_PI_INV / sigma * math.exp(-0.5 * t * t)
@classmethod
def _phi2(cls, x: float, sigma: float) -> float:
t = x / sigma
return -x * cls.SQRT_2_PI_INV / (sigma ** 3.0) * math.exp(-0.5 * t * t)
@classmethod
def _gauss_mask_0(cls, sigma: float) -> Tuple[np.ndarray, int]:
n = cls._mask_size(cls.MAX_SIZE_MASK_0, sigma)
h = np.zeros((2 * n + 1,), dtype=np.float64)
for i in range(-n + 1, n):
h[n + i] = cls._phi0(-i + 0.5, sigma) - cls._phi0(-i - 0.5, sigma)
h[0] = 1.0 - cls._phi0(n - 0.5, sigma)
h[2 * n] = cls._phi0(-n + 0.5, sigma)
return h, n
@classmethod
def _gauss_mask_1(cls, sigma: float) -> Tuple[np.ndarray, int]:
n = cls._mask_size(cls.MAX_SIZE_MASK_1, sigma)
h = np.zeros((2 * n + 1,), dtype=np.float64)
for i in range(-n + 1, n):
h[n + i] = cls._phi1(-i + 0.5, sigma) - cls._phi1(-i - 0.5, sigma)
h[0] = -cls._phi1(n - 0.5, sigma)
h[2 * n] = cls._phi1(-n + 0.5, sigma)
return h, n
@classmethod
def _gauss_mask_2(cls, sigma: float) -> Tuple[np.ndarray, int]:
n = cls._mask_size(cls.MAX_SIZE_MASK_2, sigma)
h = np.zeros((2 * n + 1,), dtype=np.float64)
for i in range(-n + 1, n):
h[n + i] = cls._phi2(-i + 0.5, sigma) - cls._phi2(-i - 0.5, sigma)
h[0] = -cls._phi2(n - 0.5, sigma)
h[2 * n] = cls._phi2(-n + 0.5, sigma)
return h, n
# -------------------------
# Convolution (Numba-accelerated)
# -------------------------
@classmethod
def _convolve_gauss(cls, image_flat: np.ndarray, w: int, h: int, sigma: float, deriv: int) -> np.ndarray:
if deriv == cls.DERIV_R:
hr, nr = cls._gauss_mask_1(sigma); hc, nc = cls._gauss_mask_0(sigma)
elif deriv == cls.DERIV_C:
hr, nr = cls._gauss_mask_0(sigma); hc, nc = cls._gauss_mask_1(sigma)
elif deriv == cls.DERIV_RR:
hr, nr = cls._gauss_mask_2(sigma); hc, nc = cls._gauss_mask_0(sigma)
elif deriv == cls.DERIV_RC:
hr, nr = cls._gauss_mask_1(sigma); hc, nc = cls._gauss_mask_1(sigma)
elif deriv == cls.DERIV_CC:
hr, nr = cls._gauss_mask_0(sigma); hc, nc = cls._gauss_mask_2(sigma)
else:
raise ValueError("unknown derivative type")
# Numba prefers contiguous arrays
hr = np.ascontiguousarray(hr)
hc = np.ascontiguousarray(hc)
tmp = _convolve_rows_flat(image_flat, hr, nr, w, h)
out = _convolve_cols_flat(tmp, hc, nc, w, h)
return out
@classmethod
def _gauss_derivatives(cls, img: np.ndarray, sigma: float):
h, w = img.shape
flat = np.ascontiguousarray(img.reshape(-1))
dr = cls._convolve_gauss(flat, w, h, sigma, cls.DERIV_R)
dc = cls._convolve_gauss(flat, w, h, sigma, cls.DERIV_C)
drr = cls._convolve_gauss(flat, w, h, sigma, cls.DERIV_RR)
drc = cls._convolve_gauss(flat, w, h, sigma, cls.DERIV_RC)
dcc = cls._convolve_gauss(flat, w, h, sigma, cls.DERIV_CC)
return dr, dc, drr, drc, dcc
# -------------------------
# Ridge candidates (Numba-accelerated)
# -------------------------
@classmethod
def _ridge_candidates(cls, dr, dc, drr, drc, dcc, w, h, low, high, mode):
# mode is 1/2 already. Keep pixel boundary exact.
return _ridge_candidates_jit(dr, dc, drr, drc, dcc, w, h, low, high, mode, cls.PIXEL_BOUNDARY)
# -------------------------
# Linking
# -------------------------
@staticmethod
def _threshold_runs(ismax: np.ndarray, minv: int, w: int, h: int) -> List[Tuple[int, int, int]]:
"""
ismax is flattened (w*h,).
Returns list of (r, cb, ce) with ismax[r, cb:ce+1] >= minv.
"""
m = (ismax.reshape(h, w) >= minv) # bool (h,w)
# Find transitions per row: start where False->True, end where True->False
# Pad with False at both ends so runs touching borders are handled.
mp = np.pad(m, ((0, 0), (1, 1)), mode="constant", constant_values=False)
starts = np.flatnonzero((~mp[:, :-1]) & (mp[:, 1:])) # indices in flattened (h*(w+1))
ends = np.flatnonzero((mp[:, :-1]) & (~mp[:, 1:]))
# Convert flattened indices to (row, col) in the padded grid
Wp = w + 1
rs = starts // Wp
cs = starts % Wp
re = ends // Wp
ce = (ends % Wp) - 1 # inclusive end in original coords
# starts/ends are aligned per row because of padding; rs==re always
# Build python list of tuples (row, cb, ce)
return list(zip(rs.astype(int).tolist(), cs.astype(int).tolist(), ce.astype(int).tolist()))
@staticmethod
def _precompute_angles(nx, ny):
# Flatten to 1D to match the kernel indexing (p = x*w + y)
nx1 = np.asarray(nx, np.float32).reshape(-1)
ny1 = np.asarray(ny, np.float32).reshape(-1)
# alpha = atan2(nx, -ny) normalized to [0, π)
alpha = np.arctan2(nx1, -ny1).astype(np.float32)
alpha = np.where(alpha < 0.0, alpha + 2.0*np.pi, alpha)
alpha = np.where(alpha >= np.pi, alpha - np.pi, alpha) # now [0,π)
# oct4 = round(4/pi*alpha) mod 4
oct4 = (np.floor((4.0/np.pi) * alpha + 0.5).astype(np.int32) & 3).astype(np.uint8)
return alpha, oct4
@classmethod
def _link_contours(cls, ismax, ev, px, py, w, h, alpha_arr, oct4_arr) -> List[np.ndarray]:
indx = np.zeros((w * h,), dtype=np.int32)
runs = cls._threshold_runs(ismax, 2, w, h)
area = sum((ce - cb + 1) for (_, cb, ce) in runs)
if area == 0:
return []
cross_x = np.empty((area,), dtype=np.int16)
cross_y = np.empty((area,), dtype=np.int16)
cross_val = np.empty((area,), dtype=np.float64)
cross_done = np.zeros((area,), dtype=np.bool_)
k = 0
for r, cb, ce in runs:
base = r * w
for c in range(cb, ce + 1):
pos = base + c
cross_x[k] = r
cross_y[k] = c
cross_val[k] = float(ev[pos])
k += 1
order = np.argsort(-cross_val, kind="quicksort")
cross_x = cross_x[order]; cross_y = cross_y[order]; cross_val = cross_val[order]
for i in range(area):
pos = int(cross_x[i]) * w + int(cross_y[i])
indx[pos] = i + 1
# --- NUMBA TRACE HERE ---
DIRTAB = np.asarray(cls._DIRTAB, dtype=np.int8)
CLEARTAB = np.asarray(cls._CLEARTAB, dtype=np.int8)
pts_x, pts_y, offsets = _link_contours_trace_numba(
cross_x.astype(np.int32),
cross_y.astype(np.int32),
cross_val.astype(np.float32),
cross_done, # bool ok
ismax.astype(np.uint8), # or np.int8
px.astype(np.float32),
py.astype(np.float32),
alpha_arr.astype(np.float32),
oct4_arr.astype(np.uint8),
indx.astype(np.int32),
w, h,
DIRTAB, CLEARTAB,
float(cls.MAX_ANGLE_DIFFERENCE),
)
# --- WRAP NUMBA OUTPUTS TO PY OBJECTS ---
lines = []
for i in range(len(offsets) - 1):
a = int(offsets[i]); b = int(offsets[i+1])
if b - a <= 1:
continue
points_xy = np.empty((b - a, 2), np.float32)
points_xy[:, 0] = pts_y[a:b]
points_xy[:, 1] = pts_x[a:b]
lines.append(points_xy)
return lines