Leanne Vis, Maxim Pisarenco, Bart M. N. Smets, Fons van der Sommen, Remco Duits
9 min
This paper introduces an innovative snake model for image segmentation on the projective line bundle R²×P¹, a mathematical space that elegantly captures oriented edges in 2D images. Traditional snakes (active contours) and geodesic models struggle with computational cost and artifacts like cusps when tracking edges, especially overlapping structures in Scanning Electron Microscopy (SEM) images of electronic devices. The authors' sub-Riemannian snakes solve these by computing distance maps only where needed, blending fast spatial snakes with precise geodesic tracking via a smart switching criterion.
The core space is R²×P¹, where R² is image position and P¹ represents projective lines (undirected orientations, like edges without arrowheads). This identifies opposite directions (θ ↔ θ+π), making it ideal for edge detection without directional ambiguity. Unlike the full circle bundle R²×S¹ (which tracks direction), P¹ halves redundancy but introduces challenges like cusps from 'gear-switching' (reversing direction).
The paper defines a new pseudo-distance: symmetric (unlike asymmetric car-like models), cusp-free (no sharp reversals in projections), and satisfying the triangle inequality on a large set. It's data-driven, sub-Riemannian geometry (inspired by Citti-Sarti), restricting motion to forward-like paths—like a car in forward gear only—to ensure smooth geodesics.
Global geodesic tracking requires expensive full-image distance maps (e.g., via Fast-Marching PDE solvers). Sub-Riemannian snakes localize this: start with quick spatial snakes (simple optimization in R²), then switch to accurate minimizing geodesics on R²×P¹ only near critical points. A geometric switching criterion decides when: fast approximation suffices most places, precise computation only for precision.
This hybrid cuts computation dramatically while retaining accuracy. The geodesic tracking model d_c integrates a connected-component-informed cost function from prior work [11], operating in product space to group overlapping structures correctly—unlike 2D methods that mix edges (see Fig. 3).
Cusps are ugly artifacts: sharp direction flips projecting to pointy corners not in real edges. Previous R²×P¹ models [9] had them due to symmetry. Here, asymmetry prevents 'gear-switching': geodesics stay smooth by forward restriction, analogous to no-reverse driving. Sub-Riemannian structure limits horizontal moves (position+orientation), vertical lifts handle curvature—building on vessel tracking but adapted for SEM edges.
Tested on SEM images of overlapping electronic structures (common in chips). The method auto-segments robustly: tracks correct edges, groups via connected components in R²×S¹, avoids cusps. Outperforms priors in accuracy and speed—no manual tuning, handles overlaps where 2D snakes fail.
Why it matters: Revolutionizes segmentation for complex microscopy. Efficient (local distances), artifact-free (cusp-free), smart (hybrid switching), practical (connected-component aware). For students: bridges geometry, geometry, and CV—sub-Riemannian tools unlock real-world imaging challenges.
Geodesic tracking on the projective line bundle $\R^2 \times P^1 $ has many uses, including the segmentation of objects in images. However, global tracking requires expensive distance map computations. We provide a practical solution to this problem by introducing a snake model on $\R^2 \times P^1$, where we only compute the distance map where needed. Our method introduces a geometric criterion for switching between fast spatial snakes and computing minimizing geodesics of a new projective line bundle model. The new pseudo-distance underlying our geometric model is both symmetric and cusp-free, in contrast to previous geodesic sub-Riemannian models on $\R^2 \times P^1$. Our pseudo-distance satisfies the triangle inequality on a large set that we characterize, and includes a connected-component-informed cost function, which is highly advantageous in applications. Experiments on Scanning Electron Microscopy (SEM) images demonstrate our method's robust, automatic segmentation of overlapping electronic structures.
Sam: The process starts by lifting the flat image data into a richer space that includes position and direction info. Then it runs a grouping step—imagine sorting connected blobs of similar edge pixels into separate colors, like labeling teams in a crowded playground photo so overlaps don't mix up. This draws an initial outline for each group. From there, it checks if edges are mostly straight or sharply bent.
Alex: Okay, so grouping helps pick the right blobs first... And that check decides the next move?
Sam: Exactly—for straight parts, it uses a quick 2D edge finder, like a basic detector that sharpens lines based on color gradients at different scales. For curvy sections, it switches to the precise geodesic tracker we discussed. This switching criterion looks at how horizontal the edge stays—if deviation stays low, stick to the fast method; otherwise, go precise. It keeps things efficient since full tracking is heavier.
Alex: That sounds smart—avoids wasting compute on simple bits. And the grouping feeds into the cost somehow?
Sam: Yes, the cost function gets upgraded with that grouping info. Normally, paths might jump between nearby but wrong blobs; here, it penalizes paths far from the target blob's group in the full space, using colors from step two. Figures show it sticks to the correct overlapping structure better.
Alex: Huh, so for stacked chip parts like these FinFETs—which are vertical fins in transistors that look piled from above—that prevents mix-ups.
Sam: Precisely. The paper's tests on various SEM images confirm clean separation of those layers—qualitatively sharp outlines, quantitatively better than Bekkers et al., especially with the new cost. It's a solid step for metrology, measuring tiny device features accurately. The code's even online for trying it.
Alex: Okay, so the connected-component cost keeps paths on the right blob. But how does the paper actually build those distance maps for the geodesics—like, the math step to find smooth forward paths?
Sam: To compute these paths, they first lift the 2D image into a 3D-like space of positions and directions—think taking a flat photo and adding a layer for every possible angle at each pixel, so crossing lines get separated by their tilt. This lifted data, called the orientation score, comes from convolving the image with rotated wavelets, like smearing a directional filter over the picture at every angle to highlight edges. From there, they solve a partial differential equation—a math rule describing how distances spread like waves in this space—to get a map of shortest paths under movement rules. The PDE enforces forward-only motion, like a car stuck in drive with no reverse.
Alex: Lifting separates crossings by angle... Got it. Paths follow steepest descent backtracking on this map?
Sam: Yes—start at the end point and slide downhill along gradients in position and angle fields. This yields smooth curves projecting cusp-free to the image. The new symmetric distance just takes the minimum over four such forward geodesics from equivalent start-end pairs, due to direction flip symmetry.
Alex: So this new distance matches the older projective model inside some cone-shaped safe zone, but longer outside?
Sam: Precisely—in that safe zone, both models pick the same cusp-free minimizer, so distances equal. Outside, the new one is longer since it rejects cusped shortcuts, forcing detours; figures show cases needing one or two extra cusp points to shortcut. It's a trade-off: perfect smoothness at minor metric cost, meaningful for clean edge traces in SEM overlaps.
Alex: Huh... So the cusp ban makes paths reliable, even if not always shortest.
Alex: What about those sphere plots—growing distance balls around the start?
Sam: The spheres plot all points reachable at exact distance R, colored by which symmetric start equivalent's front arrives first. For the new distance, fronts collide neatly at the origin, with fewer points where multiple equal-length paths meet, reducing tracking instabilities. The old model has extra folds and collides off-center, showing more ambiguity.
Alex: Fewer ambiguity points... That keeps edges stable.
Sam: Both models let you reach anywhere globally, but the new one isn't locally controllable near the origin sideways—you need some distance for a lateral approach, forcing an in-place rotation then straight line, avoiding double cusps. This smoothness aids precise SEM edge tracing without artifacts. Overall, it's a meaningful refinement for overlapping structures.
Alex: How does all this play out in the actual tests on those SEM images?
Sam: The paper tests on a real FinFET SEM photo and synthetic ones varying structure widths and top-layer heights, which dims lower layers like partial covers. They measure fit with average surface distance and Hausdorff distance—the worst-case farthest mismatch. Errors stay under one pixel on average and under four pixels worst-case—a clear improvement over the prior model.
Alex: One pixel error... That's tight for microscope work. But why does the old model do worse?
Sam: The old one worsens for bottom structures as top height grows, since paths jump to brighter foreground edges. With the new connected-component-informed cost, paths stick to the right group; figures show no switches versus jumps. Spatial snakes handle straight bits fast in plain 2D, switching to geodesics only if tilt exceeds a small angle—efficient mix.
Alex: Right—so grouping and switching make it reliable without overcomputing. Any fixes suggested?
Sam: They note trading snake speed for geodesic accuracy on rough curves, and propose weighting edge strength in switches for faint spots. Overall, qualitative figures confirm clean outlines on overlaps; quantitatively, it's a clear improvement, especially under occlusion. The code's public too.
Alex: That wraps it up neatly—fixing those edge traces opens real doors for semiconductor inspection without the old artifacts. Thanks, Sam, for breaking it down so clearly.
Sam: My pleasure, Alex. This work from Vis and team shows careful progress in handling image ambiguities. Thanks for listening to ResearchPod.