The Rules

Additional background on the DIADEM metric and digital reconstructions is available, as is a glossary of terms. The program executing the metric is described here.

Editor's note: The metric and its description were modified on 11/25/2009. The description of the prior version can be found here, with the modified sections underlined and italicized.

Who Can Enter?

Researchers working at academic institutions, not-for-profit institutes, and for-profit companies are all eligible to participate. We expect individuals and teams, including teams of highly motivated students, as well as private programmers.

The following will not be able to compete:

  • Judges and members of their research groups
  • The data providers and members of their research groups
  • The organizers and members of their research groups

All participants will need to formally declare that they have not had access to the test data sets and their reconstructions. All judges, data providers, and organizers will declare that they have not shared the test data sets and the manual reconstructions.

How will solutions be judged?

The DIADEM metric compares, on the basis of topology, two digital morphological reconstructions of one and the same neuron. The two reconstructions are both spatially registered to the same image stack and thus to each other. The metric is a multi-step process that scores the connection between each node in the gold standard (for example, manual) reconstruction based on whether or not the test (for example, automated) reconstruction captures that connection. Moreover, the importance of a connection is taken into account such that the score reflects the global topological similarity. This is done by weighting each connection by the size of the subtree to which the connection leads. Finally, excess nodes in the test reconstruction that are not present in the gold standard lower the score. Other special processes exist for specific data sets as described in the individual data set README files.

Below is a basic step-by-step explanation of the general scoring process for a given node (bifurcation or termination), referred to as the target node, in the gold standard tree:

1. All nodes in the test tree that are within a given Euclidean distance threshold of the target node, regardless of node type (i.e. bifurcation or termination), are matches (or are said to match). The specific mechanism of the distance threshold involves separate checks for XY distance and Z distance given the different sources of error. One could imagine a cylinder as the threshold region, with the base in the XY plane and the height spanning the Z dimension.

2. For each match of the target node, the closest ancestor (a node on the direct path to the root) is identified that matches an ancestor of the target node. The lengths of the gold standard and test paths are used to confirm the matches. The process is explained in more detail:

   2A. Both gold standard and test trees are "climbed" (from the target and its match respectively) until a test ancestor is within threshold of a gold standard ancestor (figure 1). The roots of the gold standard and test trees are coregistered and thus constitute matches. The target node and its given match are confirmed if the differences in path length between target node and ancestor, and between match node and its matched ancestor, are within a defined path length error threshold. Specifically, the XY component of the test path length is subtracted from that of the gold standard path length to derive the XY path length error. In order to account for difference in position of the nodes at each endpoint of the path, the test path length is adjusted (figure 2). The adjustment is determined by the difference in distances between the gold standard node and its local trajectory point and between the potential matching test node and the gold standard's trajectory point. The trajectory point is the point at which the gold standard path crosses the gold standard node's threshold boundary. Thus, if the test end point is farther away from the trajectory point than is the gold standard endpoint, the test path length will be shortened by the difference in distances. The test path length will be lengthened if the test endpoint is closer.

The remaining amount is divided by the total gold standard path length to derive an XY error rate. The same process is also used for determining the Z error rate. If the rates are less than the path length error thresholds (whereby there is a threshold for XY and a threshold for Z), then the match is a confirmed match.

Figure 1: Determining ancestor connectivity. Left tree is gold standard, right is test. Green nodes are the target and its match. Blue nodes are ancestor and ancestor match. The blue arrow shows the process of climbing the trees in order to find ancestors that match.

Figure 2: Adjusting the test path length. The gold standard end point node (central gold dot) and its parent and child paths are seen with the test node and its paths (blue). The gold standard path in the direction of its parent crosses the threshold boundary (dashed black circle) forming the trajectory point (green dot). The distances from the trajectory point to either end point node are compared (dashed green lines), and the difference is added to the test path length (bold dashed green line). For the child paths in this figure, the test node is farther from where the trajectory points would be compared to the gold standard node, so the test path length would be reduced.

   2B. It is possible for there to be more than one confirmed match to the target node based on the above criteria. In this case, the connectivity to descendants (nodes on the path to a termination) are checked. Descendants of the target node are tested in order of branch order. Matches to each descendant are traversed to the root looking for nodes that match any of the target node's confirmed matches. If any match is found, the search stops when the last descendant at the current branch order has been tested. If none of the confirmed matches satisfy the descendant connectivity criteria, then the nearest confirmed match to the target node is set as the selected match. If there was only one confirmed match, or if only one confirmed match has matching descendant connectivity, then it is the selected match. If there are multiple confirmed matches that have confirmed descendant connectivity, the closest remaining confirmed match is the selected match.

  2C. If a selected match is found, it will no longer be available for matching to subsequent target nodes.

3. Terminal nodes without a match are marked as misses* (figure 3). If a node match is not found for a target bifurcation (green node in figure 4 below), the following process is used to look for potential continuation matches after all gold standard nodes have already been checked for direct matches.

Figure 3: Termination miss. Gold is gold standard, blue is test. The bifurcation giving rise to the termination miss is scored as a continuation. This assumes that a matching node is found downstream (off of the left side of the figure).

   3A. The gold standard tree is climbed from the target node (green node in figure 4) until an ancestor is found with a test node within the distance threshold (blue nodes in figure 4).

   3B. The gold standard tree is traversed downwards from the target node until a descendant node is within threshold distance of a test node (yellow nodes in figure 4).

   3C. If the path length errors (as described in step 2A) are below the path length error thresholds then the target node is a continuation which counts the same as a selected match.

   3D. If the path distances do not match then step 3B is repeated until a match is found or all descendants have been searched. Along any given topological path from the gold standard node, the search along that path ends when a node with a confirmed match is found. Only one ancestor path exists, but any number of descendant paths may exist.

Figure 4: Determining continuation node. Left tree is gold standard, right tree is test reconstruction.
Green node is the target node. Blue node is ancestor and ancestor match. Yellow node is descendant and its match.

4. The weight of the target node is its degree (for example, the number of terminations to which the node leads).

5. Terminal test nodes that do not match any node in the gold standard tree are excess nodes (figure 5), counted as misses with weight 1. Terminal test nodes are not excess nodes if they have a matching parent (figure 6) or there is a gold standard node within threshold distance of the terminal test node (figure 7). Non-matching bifurcation test nodes are checked for potential continuation matches (see step 3 above), and counted as misses if not found to be a continuation. Their weight is the number of excess terminal descendants with no matching nodes in between. Thus a non-matched test node will not count against the score if its children are matched or not counted as excess nodes.

Figure 5: Excess node. The blue test termination has no basis in the gold standard reconstruction and so is an excess node, counting as a miss.

Figure 6: While the gold terminal node in this case will be a miss, the blue test termination is not an excess node since its parent bifurcation is matched.

Figure 7: While the gold terminal node in this case will be a miss due to improper connectivity, the blue test termination is not an excess node since there is a gold standard node within threshold distance. Since the termination will not count as an excess node, the bifurcation leading to the termination will not count against the score.

Once all gold standard nodes have been processed and excess nodes are determined, a grand score is calculated that describes how well the test reconstruction matches the gold standard in terms of global topology. Each matched node and each continuation node in the gold standard reconstruction has its weight added to the numerator of the grand total, while all nodes in the gold standard reconstruction and all excess nodes have their weights added to the denominator. Moreover, nodes are not differentiated by tree or data file. If multiple files are analyzed in a single run of the metric, all nodes will be included in the grand score based on their individual weights. This produces a score between 0 and 1 that reflects topological similarity, with a score of 1 reflecting a perfect score.

 

* For the Neuromuscular Porjection data set, competitor's may trace the rosette structures and still have terminations scored as matches (see Neuromuscular Projection readme).