Package sc.fiji.snt.tracing.auto.gwdt

Class SparseStorageBackend

java.lang.Object
sc.fiji.snt.tracing.auto.gwdt.SparseStorageBackend
All Implemented Interfaces:
StorageBackend
public class SparseStorageBackend extends Object implements StorageBackend
Sparse storage backend using hash maps for memory-efficient tracing.

Only stores non-default values (e.g., foreground voxels, traced nodes). Achieves 10-100× memory reduction for sparse neuronal structures. Best for thin structures with lots of background.

Trade-offs:
  • Memory: 10-100× less than ArrayStorageBackend
  • Speed: ~1.5-2× slower due to hash lookups vs array indexing
  • Best for: Sparse images where <10% of voxels are foreground
Author:
Tiago Ferreira

  • Constructor Summary

    Constructors
    Constructor
    Description
    SparseStorageBackend(long[] dims)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    DirectedWeightedGraph
    buildGraph(long[] dims, double[] spacing, double threshold)
    Build graph from computed Fast Marching data.
    void
    computeGWDT(net.imglib2.RandomAccessibleInterval<?> source, double threshold, double[] spacing, double minIntensity, double maxIntensity)
    Compute Gray-Weighted Distance Transform.
    void
    dispose()
    Clean up resources (close files, free memory, delete temp files).
    long
    estimateMemoryUsage()
    Get estimated memory usage in bytes.
    Set<Long>
    getAliveIndices()
    Returns the set of linear indices that have been marked as ALIVE during Fast Marching.
    String
    getBackendType()
    Get storage backend type name for logging.
    double
    getDistance(long index)
    Get Fast Marching distance at linear index.
    double
    getGWDT(long index)
    Get GWDT value at linear index.
    double
    getMaxGWDT()
    Get maximum GWDT value across the entire image.
    long
    getParent(long index)
    Get parent pointer at linear index.
    byte
    getState(long index)
    Get Fast Marching state at linear index.
    void
    initializeFastMarching(long[] dims, long seedIndex)
    Initialize Fast Marching data structures.
    void
    reinitializeFastMarching(long[] dims, long seedIndex, Set<Long> excludedIndices)
    Re-initializes Fast Marching data structures (distances, parents, state) while preserving the pre-computed GWDT.
    void
    setConnectivityType(int type)
    Sets the connectivity type for neighbor iteration.
    void
    setDistance(long index, double distance)
    Set Fast Marching distance at linear index.
    void
    setGWDT(long index, double value)
    Overwrites the GWDT value at a linear index.
    void
    setParent(long index, long parentIndex)
    Set parent pointer at linear index.
    void
    setState(long index, byte stateValue)
    Set Fast Marching state at linear index.
    void
    setTrackAliveIndices(boolean track)
    Enable or disable tracking of ALIVE indices during Fast Marching.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • SparseStorageBackend

      public SparseStorageBackend(long[] dims)

  • Method Details

    • computeGWDT

      public void computeGWDT(net.imglib2.RandomAccessibleInterval<?> source, double threshold, double[] spacing, double minIntensity, double maxIntensity)
      Description copied from interface: StorageBackend
      Compute Gray-Weighted Distance Transform.

      For each foreground pixel, GWDT = sum of intensities along shortest path to background. Uses Fast Marching with background pixels as seeds.

      Specified by:
      computeGWDT in interface StorageBackend
      Parameters:
      source - input image (untyped RandomAccessibleInterval)
      threshold - background threshold
      spacing - voxel spacing [x, y, z]
      minIntensity - minimum intensity in source (for normalization)
      maxIntensity - maximum intensity in source (for normalization)

    • getGWDT

      public double getGWDT(long index)
      Description copied from interface: StorageBackend
      Get GWDT value at linear index.
      Specified by:
      getGWDT in interface StorageBackend
      Parameters:
      index - linear voxel index
      Returns:
      GWDT value, or Double.MAX_VALUE if not computed

    • setGWDT

      public void setGWDT(long index, double value)
      Description copied from interface: StorageBackend
      Overwrites the GWDT value at a linear index. Used to apply waypoint attractors between GWDT computation and Fast Marching: pulling a voxel's GWDT value toward StorageBackend.getMaxGWDT() makes its traversal cost approach zero, so the FM wavefront prefers it.

      The maximum reported by StorageBackend.getMaxGWDT() is not automatically recomputed; callers that bias above the original max should refresh it externally if needed.

      Specified by:
      setGWDT in interface StorageBackend
      Parameters:
      index - linear voxel index
      value - the new GWDT value

    • getMaxGWDT

      public double getMaxGWDT()
      Description copied from interface: StorageBackend
      Get maximum GWDT value across the entire image.
      Specified by:
      getMaxGWDT in interface StorageBackend
      Returns:
      maximum GWDT value

    • initializeFastMarching

      public void initializeFastMarching(long[] dims, long seedIndex)
      Description copied from interface: StorageBackend
      Initialize Fast Marching data structures.

      Allocates storage for distances, parents, and state arrays. Initializes all values to defaults (distances=MAX_VALUE, parents=-1, state=FAR).

      Specified by:
      initializeFastMarching in interface StorageBackend
      Parameters:
      dims - image dimensions
      seedIndex - linear index of seed voxel (root)

    • reinitializeFastMarching

      public void reinitializeFastMarching(long[] dims, long seedIndex, Set<Long> excludedIndices)
      Description copied from interface: StorageBackend
      Re-initializes Fast Marching data structures (distances, parents, state) while preserving the pre-computed GWDT. Voxels whose linear indices appear in excludedIndices are pre-marked as ALIVE with distance 0, effectively making them impassable barriers for the next FM run.

      Excluded voxels are stamped directly into the state array after ALIVE tracking is initialized, so they are not added to the tracked ALIVE set. This ensures StorageBackend.buildGraph(long[], double[], double) only sees voxels reached by the current FM pass, not leftover exclusions.

      This enables a NeuTube-style recovery pass: after tracing from one seed, the traced region (optionally dilated) is excluded and a new FM run can proceed from a different seed without recomputing the GWDT.

      Specified by:
      reinitializeFastMarching in interface StorageBackend
      Parameters:
      dims - image dimensions
      seedIndex - linear index of the new seed voxel
      excludedIndices - set of linear indices to pre-mark as ALIVE (impassable); may be null or empty

    • setDistance

      public void setDistance(long index, double distance)
      Description copied from interface: StorageBackend
      Set Fast Marching distance at linear index.
      Specified by:
      setDistance in interface StorageBackend
      Parameters:
      index - linear voxel index
      distance - geodesic distance from seed

    • getDistance

      public double getDistance(long index)
      Description copied from interface: StorageBackend
      Get Fast Marching distance at linear index.
      Specified by:
      getDistance in interface StorageBackend
      Parameters:
      index - linear voxel index
      Returns:
      distance from seed, or Double.MAX_VALUE if unreached

    • setParent

      public void setParent(long index, long parentIndex)
      Description copied from interface: StorageBackend
      Set parent pointer at linear index.
      Specified by:
      setParent in interface StorageBackend
      Parameters:
      index - linear voxel index
      parentIndex - linear index of parent voxel in shortest path tree

    • getParent

      public long getParent(long index)
      Description copied from interface: StorageBackend
      Get parent pointer at linear index.
      Specified by:
      getParent in interface StorageBackend
      Parameters:
      index - linear voxel index
      Returns:
      parent index, or -1 if root or unset

    • setState

      public void setState(long index, byte stateValue)
      Description copied from interface: StorageBackend
      Set Fast Marching state at linear index.
      Specified by:
      setState in interface StorageBackend
      Parameters:
      index - linear voxel index
      stateValue - one of FAR (0), TRIAL (1), or ALIVE (2)

    • getState

      public byte getState(long index)
      Description copied from interface: StorageBackend
      Get Fast Marching state at linear index.
      Specified by:
      getState in interface StorageBackend
      Parameters:
      index - linear voxel index
      Returns:
      state value: FAR (0), TRIAL (1), or ALIVE (2)

    • buildGraph

      public DirectedWeightedGraph buildGraph(long[] dims, double[] spacing, double threshold)
      Description copied from interface: StorageBackend
      Build graph from computed Fast Marching data.

      Walks the parent pointers to reconstruct the shortest path tree, converting voxel coordinates to physical coordinates and creating SWCPoint nodes connected by edges.

      Specified by:
      buildGraph in interface StorageBackend
      Parameters:
      dims - image dimensions
      spacing - voxel spacing for coordinate conversion
      threshold - background threshold (for validation)
      Returns:
      directed weighted graph representing the traced tree

    • estimateMemoryUsage

      public long estimateMemoryUsage()
      Description copied from interface: StorageBackend
      Get estimated memory usage in bytes.
      Specified by:
      estimateMemoryUsage in interface StorageBackend
      Returns:
      estimated memory footprint of this backend

    • getBackendType

      public String getBackendType()
      Description copied from interface: StorageBackend
      Get storage backend type name for logging.
      Specified by:
      getBackendType in interface StorageBackend
      Returns:
      human-readable backend type (e.g., "Array (in-memory)", "Sparse", "Disk-backed")

    • getAliveIndices

      public Set<Long> getAliveIndices()
      Description copied from interface: StorageBackend
      Returns the set of linear indices that have been marked as ALIVE during Fast Marching. Only available when ALIVE tracking is enabled; returns null otherwise.
      Specified by:
      getAliveIndices in interface StorageBackend
      Returns:
      the tracked ALIVE indices, or null if tracking is disabled

    • dispose

      public void dispose()
      Description copied from interface: StorageBackend
      Clean up resources (close files, free memory, delete temp files).

      Called automatically after tracing completes. Implementations should release any resources and allow garbage collection.

      Specified by:
      dispose in interface StorageBackend

    • setConnectivityType

      public void setConnectivityType(int type)
      Sets the connectivity type for neighbor iteration.

    • setTrackAliveIndices

      public void setTrackAliveIndices(boolean track)
      Description copied from interface: StorageBackend
      Enable or disable tracking of ALIVE indices during Fast Marching.

      When enabled, the backend maintains a set of linear indices that have been marked as ALIVE. This allows StorageBackend.buildGraph(long[], double[], double) to iterate only touched voxels instead of scanning the entire volume, providing dramatic speedup for large sparse images.

      Memory cost: ~24 bytes per ALIVE voxel

      Recommended settings:
      • ArrayStorageBackend: ON (default) - moderate speedup, low cost
      • SparseStorageBackend: OFF (default) - already iterates keys only
      • DiskBackedStorageBackend: ON (default) - essential for performance
      Specified by:
      setTrackAliveIndices in interface StorageBackend
      Parameters:
      track - true to track ALIVE indices, false to use full-volume scan