Graph-based tracing

Description

Vaa3d All-Path-Pruning 2.0 (APP2) dockerised workflow for BIAFLOWS.

need a thumbnail
Description

"we present a new fully automated 3D reconstruction algorithm, called TReMAP, short for Tracing, Reverse Mapping and Assembling of 2D Projections. Instead of tracing a 3D image directly in the 3D space as seen in majority of the tracing methods, we first trace the 2D projection trees in 2Dplanes, followed by reverse-mapping the resulting 2D tracing results back into the 3D space as 3D curves; then we use a minimal spanning tree (MST) method to assemble all the 3D curves to generate the final 3D reconstruction. Because we simplify a 3D reconstruction problem into 2D, the computational costs are reduced dramatically." 

Suitable for high throughput neuron image analysis (image sizes >10GB). This plugin can be used with default parameters or user-defined parameters.

Example_TReMAP_Result
Description

All-path-pruning 2.0 (APP2) is a component of Vaa3D. APP2 prunes an initial reconstruction tree of a neuron’s morphology using a long-segment-first hierarchical procedure instead of the original termini-first-search process in APP. APP2 computes the distance transform of all image voxels directly for a gray-scale image, without the need to binarize the image before invoking the conventional distance transform. APP2 uses a fast-marching algorithm-based method to compute the initial reconstruction trees without pre-computing a large graph. This method allows to trace large images. This method can be used with default parameters or user-defined parameters.

APP2_Vaa3D_example_Result
Description

"We have developed an automatic graph algorithm, called the all-path pruning (APP), to trace the 3D structure of a neuron. To avoid potential mis-tracing of some parts of a neuron, an APP first produces an initial over-reconstruction, by tracing the optimal geodesic shortest path from the seed location to every possible destination voxel/pixel location in the image. Since the initial reconstruction contains all the possible paths and thus could contain redundant structural components (SC), we simplify the entire reconstruction without compromising its connectedness by pruning the redundant structural elements, using a new maximal- covering minimal-redundant (MCMR) subgraph algorithm. We show that MCMR has a linear computational complexity and will converge. We examined the performance of our method using challenging 3D neuronal image datasets of model organisms (e.g. fruit fly)"

This plugin can be used with default parameters or user-defined parameters.

APP_Vaa3D_example_results