"""Fingerprint minutiae extraction: endpoints (ridgE endings) + bifurcations. Pipeline: 1. Load grayscale BMP 2. Otsu binarization -> ridge mask (ridges = dark) 3. Morphological cleanup (open/close) to break up grain noise 4. Skeletonize ridges 5. Walk skeleton: endpoint = 1 neighbor, bifurcation = >=3 neighbors 6. Noise filtering: - cluster nearby candidates (bifurcation pairs ~1-2 px apart get merged) - reject candidates in the outer 15% border band - reject candidates whose local ridge width is < 3 px (grain, not a ridge) - cap density per region 7. Draw markers: endpoint = green circle, bifurcation = red X """ import sys import cv2 import numpy as np from skimage.morphology import skeletonize src = sys.argv[1] out = sys.argv[2] img = cv2.imread(src, cv2.IMREAD_GRAYSCALE) if img is None: print("FAIL: cannot read", src) sys.exit(1) h, w = img.shape print(f"image {w}x{h}") # --- 1. binarize: ridges are the dark lines --- # denoise lightly first den = cv2.GaussianBlur(img, (3, 3), 0) _, bin_img = cv2.threshold(den, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU) # Otsu on a mostly-white bg: white=255, dark ridges=0. We want ridge mask (1=ridge). ridge = (bin_img == 0).astype(np.uint8) frac_dark = ridge.mean() print(f"ridge fraction: {frac_dark:.3f}") # sanity: if dark fraction is > 0.5 we inverted wrong if frac_dark > 0.5: ridge = 1 - ridge print("inverted ridge mask") # --- 2. cleanup: close small gaps, open grain --- k3 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (3, 3)) ridge = cv2.morphologyEx(ridge, cv2.MORPH_CLOSE, k3, iterations=1) ridge = cv2.morphologyEx(ridge, cv2.MORPH_OPEN, k3, iterations=1) # keep only components that look like real ridge strokes (area filter) n_lab, labels, stats, _ = cv2.connectedComponentsWithStats(ridge, connectivity=8) min_area = 80 keep = np.zeros_like(ridge) for i in range(1, n_lab): if stats[i, cv2.CC_STAT_AREA] >= min_area: keep[labels == i] = 1 ridge = keep print(f"components kept: {(ridge > 0).any()}") # --- 3. skeletonize --- skel = skeletonize(ridge > 0).astype(np.uint8) print(f"skeleton pixels: {skel.sum()}") # --- 4. neighbor count on skeleton --- ys, xs = np.nonzero(skel) coords = set(zip(ys.tolist(), xs.tolist())) def n_neigh(y, x): c = 0 for dy in (-1, 0, 1): for dx in (-1, 0, 1): if dy == 0 and dx == 0: continue if (y + dy, x + dx) in coords: c += 1 return c cands = [] # (y, x, type) for (y, x) in coords: n = n_neigh(y, x) if n == 1: cands.append((y, x, 'end')) elif n >= 3: cands.append((y, x, 'bif')) print(f"raw candidates: end={sum(1 for c in cands if c[2]=='end')}, bif={sum(1 for c in cands if c[2]=='bif')}") # --- 4b. branch-length analysis: remove grain-induced spurious events --- # Build skeleton graph; for each event compute the lengths of its incident # branches (walk to the next event). Reject events where the shortest branch # is too short (grain stubs) or where an endpoint sits on a stubby island. from collections import deque skel_pts = sorted(coords) adj = {} for (y, x) in coords: nb = [] for dy in (-1, 0, 1): for dx in (-1, 0, 1): if dy == 0 and dx == 0: continue if (y + dy, x + dx) in coords: nb.append((y + dy, x + dx)) adj[(y, x)] = nb event_set = {(c[0], c[1]) for c in cands} def branch_lengths(pt): """Length of each branch leaving pt, measured to the next event point.""" lengths = [] for nb in adj[pt]: if nb in event_set: continue # branch to another event: handled from that side # BFS outward until we hit an event or dead end visited = {pt, nb} q = deque([(nb, 0)]) maxlen = 0 while q: (cy, cx), d = q.popleft() maxlen = max(maxlen, d) for nn in adj[(cy, cx)]: if nn in visited: continue if nn in event_set: maxlen = max(maxlen, d + 1) continue visited.add(nn) q.append((nn, d + 1)) lengths.append(maxlen) return lengths MIN_BRANCH = 10 # px; grain stubs are shorter than this filtered_cands = [] for (y, x, t) in cands: bl = branch_lengths((y, x)) if not bl: filtered_cands.append((y, x, t)) continue if t == 'bif': # all but at most one branch must be substantial short = sum(1 for L in bl if L < MIN_BRANCH) if short > 1: continue else: # endpoint: the single ridge it ends must be long enough if len(bl) == 1 and bl[0] < MIN_BRANCH: continue filtered_cands.append((y, x, t)) print(f"after branch-length filter: end={sum(1 for c in filtered_cands if c[2]=='end')}, bif={sum(1 for c in filtered_cands if c[2]=='bif')}") cands = filtered_cands # --- 5. cluster nearby candidates (same event) --- def cluster(cands, radius=3): used = [False] * len(cands) groups = [] for i, c in enumerate(cands): if used[i]: continue stack = [i] used[i] = True group = [c] while stack: j = stack.pop() yj, xj, _ = cands[j] for k in range(len(cands)): if not used[k]: yk, xk, _ = cands[k] if abs(yk - yj) <= radius and abs(xk - xj) <= radius: used[k] = True stack.append(k) group.append(cands[k]) groups.append(group) return groups groups = cluster(cands) events = [] for g in groups: y = sum(c[0] for c in g) / len(g) x = sum(c[1] for c in g) / len(g) t = 'bif' if any(c[2] == 'bif' for c in g) else 'end' events.append((int(y), int(x), t)) print(f"after clustering: end={sum(1 for e in events if e[2]=='end')}, bif={sum(1 for e in events if e[2]=='bif')}") # --- 6. filters --- # 6a. ridge-width: local ridge thickness at the event must be >= 3 px # 6b. fade-out endpoints: ridge mask boundary distance. A true endpoint ends # in the middle of the print (surrounded by valley); a fade-out "end" sits # at the outer boundary of the whole ridge region. border = int(0.15 * min(h, w)) # distance from each ridge pixel to the OUTER edge of the whole ridge region: # dilate heavily to merge ridges into one solid blob, then distance transform blob = cv2.dilate(ridge, cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (15, 15)), iterations=2) dist_to_outer = cv2.distanceTransform(blob, cv2.DIST_L2, 5) dist = cv2.distanceTransform(ridge, cv2.DIST_L2, 5) def ridge_width(y, x): y0, y1 = max(0, y - 6), min(h, y + 7) x0, x1 = max(0, x - 6), min(w, x + 7) return 2 * dist[y0:y1, x0:x1].max() final = [] for (y, x, t) in events: if y < border or y >= h - border or x < border or x >= w - border: continue if ridge_width(y, x) < 3.0: continue if ridge_width(y, x) > 9.0: continue # binarization merged neighboring ridges -> topology unreliable if t == 'end' and dist_to_outer[y, x] < 10: continue # tip at the print's outer edge (fade-out), not a true endpoint final.append((x, y, t)) for (x, y, t) in final: if t == 'end': print(f"DEBUG end ({x},{y}) dist_to_outer={dist_to_outer[y,x]:.1f} width={ridge_width(y,x):.1f}") print(f"after border+width+fade filter: end={sum(1 for e in final if e[2]=='end')}, bif={sum(1 for e in final if e[2]=='bif')}") # --- 7. density cap: keep at most ~1 per 20x20 cell, prefer bifurcations --- cell = 20 grid = {} final_sorted = sorted(final, key=lambda e: (e[2] != 'bif', e[0], e[1])) # bif first capped = [] for (x, y, t) in final_sorted: key = (x // cell, y // cell) if key in grid: continue grid[key] = t capped.append((x, y, t)) print(f"after density cap: end={sum(1 for e in capped if e[2]=='end')}, bif={sum(1 for e in capped if e[2]=='bif')}") # --- 8. draw --- vis = cv2.cvtColor(img, cv2.COLOR_GRAY2BGR) for i, (x, y, t) in enumerate(capped, 1): if t == 'end': cv2.circle(vis, (x, y), 9, (0, 255, 0), 2) cv2.putText(vis, str(i), (x + 10, y - 6), cv2.FONT_HERSHEY_SIMPLEX, 0.4, (0, 200, 0), 1) else: cv2.rectangle(vis, (x - 8, y - 8), (x + 8, y + 8), (0, 0, 255), 2) cv2.putText(vis, str(i), (x + 10, y - 6), cv2.FONT_HERSHEY_SIMPLEX, 0.4, (0, 0, 220), 1) cv2.imwrite(out, vis, [cv2.IMWRITE_PNG_COMPRESSION, 3]) print(f"WROTE {out}") print(f"TOTAL: {len(capped)} minutiae (end={sum(1 for e in capped if e[2]=='end')}, bif={sum(1 for e in capped if e[2]=='bif')})")