Hello Tim
Thank you very much for taking the time of writing such a detailed
explanation. It has been really useful.
Best wishes,
Stefan Pszczolkowski P. Ph.D.
Research Fellow
Radiological Sciences
Division of Clinical Neuroscience
Room B115-117, School of Medicine
University of Nottingham
Queen's Medical Centre, Derby Road
Nottingham
NG7 2UH
Tel: 44 (0) 115 748 4389
Website: https://stefanpsz.github.io/
On 13/06/2018 20:07, Timothy Coalson wrote:
The algorithm used is Dijkstra (A* is used for more specialized
purposes of one vertex to one other specific vertex), but that is not
the whole story. To reduce the impact of the mesh triangulation on
the result, we not only use edge-neighbors, we also take every pair of
edge-connected triangles, and include another "neighbor" resulting
from finding the shortest path between the far vertices in the
two-triangle system (unless that path follows the edges, due to
unusual angles). This is the difference between the default and
"naive" methods. As such, it gives much more accurate distances,
while still using simple Dijkstra code, and is basically the same
speed as the naive version.
But, there is yet another wrinkle: when using group-average surfaces,
there is much less folding definition, and therefore less surface
area, and these make the distances between vertices artificially
shorter than they are in the contributing subjects. We have an
approximate correction for this change to the distances, by comparing
the vertex areas (one third of the area of each triangle using the
vertex) of the group average surface, to the group average of the
vertex areas of the individual surfaces. This correction gets applied
to all of the graph's edge lengths independently (including the
2-triangle-crawled extra "neighbors"), before Dijkstra or A* get run
(and yes, I do tweak the A* euclidean distance heuristic by the
minimum distance correction ratio, in case it anomalously said that an
edge got shorter). It is not clear how to do a similar correction to
exact geodesic distance code, as exact geodesic distance methods seem
like they must require explicit geometry in 3-space, while Dijkstra
applies to arbitrary graphs with positive edge lengths, even if they
violate the triangle inequality, giving us much more freedom to tweak
things.
The original reason we didn't use an exact method is that an exact
method is complicated and slower (the paper I previously looked at
specifically started with Dijkstra to provide a heuristic to speed up
the exact algorithm for the single destination case).
Tim
On Wed, Jun 13, 2018 at 10:11 AM, Stefan Pszczolkowski
<[email protected] <mailto:[email protected]>> wrote:
Hello
I would like to ask what is the underlying method employed for
computing
geodesic distances in the -surface-geodesic-distance Workbench
command.
Is it simply a Dijkstra approximation? or something more
sophisticated
like the exact algorithm of [1]?
I have had a quick look at the code and I found methods like
"dijkstra"
and "aStar", but I quickly realised that is probably better to ask
here :)
Thank you very much!
[1] MITCHELL, J.S.B.,MOUNT, D.M., AND PAPADIMITRIOU, C. H. 1987. The
discrete geodesic problem. SIAM J. of Computing 16(4), 647–668.
--
Stefan Pszczolkowski P. Ph.D.
Research Fellow
Radiological Sciences
Division of Clinical Neuroscience
Room B115-117, School of Medicine
University of Nottingham
Queen's Medical Centre, Derby Road
Nottingham
NG7 2UH
Tel: 44 (0) 115 748 4389
Website: https://stefanpsz.github.io/
This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment.
Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored
where permitted by law.
_______________________________________________
HCP-Users mailing list
[email protected] <mailto:[email protected]>
http://lists.humanconnectome.org/mailman/listinfo/hcp-users
<http://lists.humanconnectome.org/mailman/listinfo/hcp-users>
This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment.
Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored
where permitted by law.
_______________________________________________
HCP-Users mailing list
[email protected]
http://lists.humanconnectome.org/mailman/listinfo/hcp-users
