Skip to content

Precise quantification of streamlines lengths#1507

Merged
Lestropie merged 6 commits intodevfrom
streamline_length_precise
Jul 30, 2019
Merged

Precise quantification of streamlines lengths#1507
Lestropie merged 6 commits intodevfrom
streamline_length_precise

Conversation

@Lestropie
Copy link
Copy Markdown
Member

As discussed in #1501.

The only time at which it is safe to perform a multiplication between number of vertices and step size in order to derive the streamline length is within the tractography propagation algorithm itself, when a fixed step size is guaranteed. As soon as there is the possibility of an inconsistent step size (input data from a file, various resampling strategies, truncation), this is no longer safe, and so the sum of inter-vertex distances must be calculated.

Couple of points to note:

  • Whenever tckgen -act -crop_at_gmwmi is specified, streamline lengths are always re-quantified, based on a fixed step size for all but the first and last segments (those are measured explicitly) and compared against the floating-point minimum length (previously the tckgen test for minimum length was purely based on number of vertices).

  • Downsampling that can occur in tckgen (and is on by default for iFOD2) affects length quantification. As such I've thrown in an additional test against the tracking minimum length after downsampling has occurred. I measured the performance penalty of this at about 1%.
    Conceptually this isn't required for iFOD2 under default usage, since in that algorithm it's actually the post-downsampling inter-vertex distance that is controlled, not the "internal" step size within each arc trajectory. But trying to catch this case in order to skip it would be kinda clumsy.

  • I intentionally designed the histogram feature in tckstats to centre the bins at multiples of the step size; therefore floating-point variations in quantified lengths shouldn't be a major issue here.

  • I also tweaked tckstats to be a little more explicit about the presence of empty streamlines (0 vertices) vs. zero-length streamlines (1 vertex).

  • I looked briefly into quantification of spline length rather than piecewise length (in the hope it'd be less sensitive to variations in vertex density), but it went straight into the too-hard basket.

Closes #1501.

Closes #1153.

@Lestropie
Copy link
Copy Markdown
Member Author

Some more musings on the forum, with potentially more to change in the code.

@jdtournier
Copy link
Copy Markdown
Member

Looking at this, I'm reminded that we might want to change the default setting for the max length. Currently, it's set to 100× voxel size, which is really a bit useless. Might be best reserved for a separate pull request - but how do people feel about setting it to the largest image dimension instead (i.e. max FoV)?

@thijsdhollander
Copy link
Copy Markdown
Contributor

Agreed the default is a bit useless. I don't think max FoV will be enough though: if you cropped your FoV to just the brain mask (which many people often do, to deal with large datasets / high resolutions), this doesn't allow a streamline to run "back and forth" through the brain anymore. The default should, in my opinion, just be something that is realistically not reached, but is there anyway to avoid streamlines looping infinitely. So going by my earlier reasoning/argument ... what about 2x max FoV...?

@jdtournier
Copy link
Copy Markdown
Member

what about 2x max FoV...?

Actually seems fair enough to me... 👍

@thijsdhollander
Copy link
Copy Markdown
Contributor

...and just to be safe: max(FoV) could be defined here as the maximal length that fits (as a straight line) in the FoV; i.e. the length of the diagonal connecting opposite corners.

@Lestropie
Copy link
Copy Markdown
Member Author

max(FoV) could be defined here as the maximal length that fits (as a straight line) in the FoV; i.e. the length of the diagonal connecting opposite corners.

I think I might have proposed this last time around? Was still concerned about the influence of FoV cropping though. We've never figured out a better heuristic so it really needs its own issue listing.

Conflicts:
	src/dwi/tractography/streamline.h
@jdtournier jdtournier added this to the 3.0_RC4 release milestone Jan 30, 2019
@Lestropie
Copy link
Copy Markdown
Member Author

Exposing my inner monologue for a moment:

What I'm working on as I write this is, for a given step size / angle / downsampling ratio, what is the maximum number of vertices that a post-downsampling streamline could plausibly have and still be shorter than the minimum length; that way, if a streamline has more vertices than this, the expense of computing the precise length can be skipped.

(While iFOD2 is only 1% slower with these changes, the proportional computational hit is likely to be greater for those algorithms that generate streamlines faster)

This made me realise that this kind of complexity occurs the other way also: if a streamline is terminated due to reaching the maximum number of vertices (calculated based on the step size), then it's possible that after downsampling, that streamline would then be shorter than the maximum length, in which case it could potentially have propagated further.

Therefore: should streamlines be permitted to propagate beyond the maximum number of vertices calculated based on step size alone, and only have their length compared against the maximum length criterion after downsampling has taken place?

- Change the default step size for first-order methods from (0.1 x voxel) to (0.5 x voxel) when RK4 is activated.
- All streamlines must conform to the minimum and maximum length restrictions AFTER down-sampling; likewise, it's not omputationally efficient to compute precisely the length of every generated streamline. Therefore, introduce two sets of vertex count limits: One pair that is utilised before downsampling to detect outright rejection of short tracks and cessation of propagation of long tracks, and another to detect when it is necessary to calculate a precise streamline length in order to compare against the floating-point length criteria. These are calculated based on the minimum radius of curvature and downsampling ratio (among other things), as downsampling reduces the lengths of streamlines. Additionally, if a streamline is longer than the maximum length after downsampling (which is possible given the precise length of the streamline is not known during streamlines propagation, and hence tracking is permitted to extend beyond the maximum length), and ACT is not being used, truncate the streamline to be precisely the maximum length. Also note that even if downsampling is not being used, the precise streamline length may nevertheless need to be verified if ACT cropping at the GM-WM interface is enabled.
- Default angle per step for first-order methods changed to be that which yields a minimum radius of curvature of one voxel, rather than (90deg x step_size / voxel_size).
@Lestropie
Copy link
Copy Markdown
Member Author

Turns out I opened up a can of worms with this one... I'll explain as best I can, and we'll see then what you think might need independent verification / discussion.

  • If one runs tckstats on the output of tckgen, there should not be any streamlines shorter than the minimum length, or longer than the maximum length.

    From this requirement, we can then work backwards:

    • If there's any chance that a streamline might have a length outside of these bounds, based on the number of vertices after downsampling has taken place, then we need to quantify its length precisely; however if this is not numerically possible based on the number of post-downsampling vertices, then we'd rather avoid the expense of that precise streamline length calculation.

    • If there's no chance for a streamline to be within these length criteria, based on the number of vertices before downsampling, then we should either:

      • Throw the streamline out without any further processing if it's too short;

      • Stop tracking if it's too long; but additional checks / manipulation may occur.

        • Note however that this by design requires permitting tracking to continue until even the shortest post-downsampling streamline for that number of pre-downsampling vertices would be longer than the maximum length. So depending on various parameters, individual streamlines being generated may have many more vertices than one might expect based on just the step size & maximum length alone.

        • If ACT is being used, the streamline can then be rejected; if not, the streamline will be truncated post-downsampling so that its length is precisely the maximum length (this is additionally done in such a way as to ensure preservation of the seed point).

    • All of these calculations depend on the minimum radius of curvature: If this is small, and/or if the downsampling factor is large, then the distance between vertices post-downsampling can be substantially smaller than the sum of inter-vertex distances between those two points on the pre-downsampled streamline.

    • All of these calculations are made just a little bit trickier to manage given the internal trickery of iFOD2 😖

      Note also that the calculation of minimum radius of curvature for iFOD2 reported here is wrong: That expression is based on the step size corresponding to the arc length rather than the chord length whereas iFOD2 paths are generated based on the latter. Doesn't matter particularly since it was only a terminal prompt and the calculation wasn't used in any way; just flagging it because with these changes, the calculation of minimum radius of curvature does now have downstream implications.

  • Changed default step size for first-order methods from 1/10th voxel to 1/2 voxel when RK4 is activated. RK4 massively reduces curvature overshoot, which is one of the driving factors in having a small step size for first-order methods; it's also more computationally expensive than first-order integration (5 sample points per step), so a longer step size helps offset that.

  • Changed default angle per step calculation for first-order methods. At some point a long long time ago, this was reverted from the minimum radius of curvature calculation used in MRtrix 0.2 and shown in that paper, to simply be: (90deg * step_size / voxel_size). However many of the changes I've described above depend heavily on calculation of the minimum radius of curvature. So it seemed quite strange to me to have the default maximum angle calculated based on this expression, and then deriving a minimum radius of curvature from it, which then influences subsequent calculations, when really the intent of the default maximum angle calculation is to prevent turning around within a voxel (i.e. a minimum radius of curvature of one voxel). What made more sense to me (and what's bundled in c18e368) is:

    • If the maximum turning angle is specified by the user, calculate from that the minimum radius of curvature, which then gets used in subsequent calculations;

    • If it is not specified by the user, set the minimum radius of curvature to be one voxel, calculate from that the maximum turning angle per step, and then use those in subsequent calculations.

    This does however mean a change to default tracking behaviour for some algorithms (not iFOD2 though).

  • The interpretation of the "maximum turning angle" is slightly different between first-order methods and higher-order methods (i.e. both iFOD2 and RK4). In the former, it's the angle with which one step deviates from the direction of the prior step; in the latter, this angle corresponds to the difference in fibre orientations underlying the two vertices constituting the step. I've tried to add some documentation clarification for this.

😥

@Lestropie Lestropie merged commit b1a0b48 into dev Jul 30, 2019
@Lestropie Lestropie deleted the streamline_length_precise branch July 30, 2019 10:02
Lestropie added a commit that referenced this pull request Sep 30, 2019
Revert changes that were made in #1507 with respect to determination of the default maximum angle for the various tracking algorithms. There, this decision was changed from being based on (90deg * step_size / vox()) to being a minimum radius of curvature of one voxel. Additionally, the default step size in the presence of RK4 was changed from 0.1*vox() to 0.5*vox(). This commit reverts these changes, but retains the calculation of minimum radius of curvature necessary for streamline length calculation optimisations.
Lestropie added a commit that referenced this pull request Nov 21, 2019
Resolve divergence between #1630 and #1507. Use a single function Tractography::Shared::set_step_and_angle() that is responsible for setting up both the step size and maximum deviation angle per step. Remove calculation of maximum angle based on radius of curvature, in favour of a fixed angle for each algorithm. Use separate member variables for maximum angles and related quantities between first-order and higher-order integration as was introduced in #1507.

Conflicts:
	src/dwi/tractography/algorithms/fact.h
	src/dwi/tractography/algorithms/iFOD1.h
	src/dwi/tractography/algorithms/iFOD2.h
	src/dwi/tractography/algorithms/nulldist.h
	src/dwi/tractography/algorithms/sd_stream.h
	src/dwi/tractography/algorithms/seedtest.h
	src/dwi/tractography/algorithms/tensor_det.h
	src/dwi/tractography/tracking/shared.cpp
	src/dwi/tractography/tracking/shared.h
	src/dwi/tractography/tracking/tractography.cpp
Lestropie added a commit that referenced this pull request Oct 1, 2020
- Reduces redundancy of code surrounding calculation of streamline tengents.
- Moves to using single-precision floating-points to represent streamline tengents based on vertices that are only stored at single-precision.
- Remove function templates for Tractography::Streamline::calc_length(), for which the implementations were removed in #1507.
@Lestropie Lestropie mentioned this pull request Feb 20, 2023
13 tasks
Lestropie added a commit that referenced this pull request Aug 26, 2025
- Reduces redundancy of code surrounding calculation of streamline tengents.
- Moves to using single-precision floating-points to represent streamline tengents based on vertices that are only stored at single-precision.
- Remove function templates for Tractography::Streamline::calc_length(), for which the implementations were removed in #1507.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants