Package sc.fiji.snt.tracing

package sc.fiji.snt.tracing
Path-finding algorithms for interactive neuron tracing.

This package provides A*-based search algorithms for finding optimal paths between user-specified points in neuronal images. These are the core tracing engines used by SNT's interactive tracing mode.

Package Organization

Core Classes

TracerThread
The primary A* path finder. Computes optimal paths between two points using intensity-based cost functions and configurable heuristics.
BiSearch
Bidirectional A* search that explores from both endpoints simultaneously, often faster for long paths.
FillerThread
Region-growing algorithm for filling/segmenting neuronal volumes. Used for distance-based analysis and volume rendering.
TubularGeodesicsTracer
Geodesic path finder optimized for tubular structures using orientation-enhanced cost functions.
ManualTracerThread
Lightweight tracer for manual point-to-point connections without automated path optimization.

Search Infrastructure

SearchInterface
Common interface for all search algorithms, defining lifecycle methods and result retrieval.
AbstractSearch
Base implementation with shared functionality: priority queue management, neighbor iteration, path reconstruction.
SearchNode / DefaultSearchNode
Graph nodes storing position, costs (g, h, f), and parent pointers for path reconstruction.
PathResult
Encapsulates search results: the found path, search statistics, and success/failure status.

Algorithm Overview

The A* algorithm finds the optimal path by minimizing f(n) = g(n) + h(n), where:

  • g(n) - Actual cost from start to node n (computed via Cost)
  • h(n) - Estimated cost from n to goal (computed via Heuristic)

Cost functions typically use image intensity (brighter = lower cost for neurites), while heuristics use Euclidean distance or Dijkstra (h=0) for guaranteed optimality.

Usage Example


 // Create tracer with reciprocal cost (bright = low cost)
 TracerThread tracer = new TracerThread(
     searchImage,
     startX, startY, startZ,
     endX, endY, endZ,
     new Reciprocal(minCost, maxCost),
     new Euclidean()
 );

 // Run search (blocks until complete)
 tracer.run();

 // Get result
 Path path = tracer.getResult();
Author:
Mark Longair, Tiago Ferreira, Cameron Arshadi
See Also:
  • Class
    Description
    AbstractSearch
    Abstract class for path-finding over RandomAccessibleIntervals
    BiSearch
    A flexible implementation of the bidirectional heuristic search algorithm described in Pijls, W.H.L.M., Post, H., 2009.
    BiSearchNode
    A SearchNode which can maintain both a from-start and from-goal search state.
    BiSearchNode.State
     
    CrossSectionUtils
    Static utilities for computing cross-sectional planes perpendicular to a path tangent.
    DefaultSearchNode
    A SearchNode which can maintain both a from-start and from-goal search state.
    FillerThread
    Seeded-volume segmentation via single-source shortest paths.
    ManualTracerThread
    A tracer thread for manual tracing.
    SearchInterface
    Tracer classes implementing searches between two points should implement this interface.
    SearchNode
    Interface representing a node in 3D space that can be used in pathfinding and search algorithms.
    SearchThread
    Implements a common thread that explores the image using a variety of strategies, e.g., to trace tubular structures or surfaces.
    TracerThread
    SNT's default tracer thread: explores between two points in an image, doing an A* search with a choice of distance measures.
    TubularGeodesicsTracer
    A tracer thread for FijiITKInterface.TubularGeodesics (assumes the tubularity add-on to be installed)