Trace Editor/Features

From FarsightWiki
(Difference between revisions)
Jump to: navigation, search
m (→Algorithms)
(→Algorithms)
Line 63: Line 63:
 
*Minimal distance between end points
 
*Minimal distance between end points
 
**[[Angle between traces-]] The angle is measured between the two traces by computing the [http://en.wikipedia.org/wiki/Vector_norm norm of their vectors] and the [http://en.wikipedia.org/wiki/Dot_product dot product]. <br />The equation is:  <math>v_1 \cdot v_2 = |v_1||v_2| \cos(\theta)</math> which when solved for <math>\theta</math> is: <math> \theta = \arccos(\frac{v_1 \cdot v_2}{|v_1||v_2|}) </math>  
 
**[[Angle between traces-]] The angle is measured between the two traces by computing the [http://en.wikipedia.org/wiki/Vector_norm norm of their vectors] and the [http://en.wikipedia.org/wiki/Dot_product dot product]. <br />The equation is:  <math>v_1 \cdot v_2 = |v_1||v_2| \cos(\theta)</math> which when solved for <math>\theta</math> is: <math> \theta = \arccos(\frac{v_1 \cdot v_2}{|v_1||v_2|}) </math>  
−
**[[Path length-]] If the end points are not the best fit for the merge this is when path length is considered. An example of this would be a peak in the neurite on completion the given merge. An example if given in an image in this section. This is also discussed in large gaps being that in the large gap case these type of error cause more of a problem. a sharp change in a neurite in a subsection prior to the end point would indicate this error. Merging at the sharp direction change( especially in the small gap case) can alleviate the neurite of peaks.  
+
**[[Path length-]] The path length is considered if the end points are not the best fit for the merge. For instance, a merging that would cause a sharp peak in the neurite. This is a more serious problem for large gaps (see below). To help alleviate this for small gaps, merge at the point where the direction changes sharply.
−
**[[Gap distance is too large-]] If the distance between the two points e<sub>1</sub>, e<sub>2</sub> is greater then the excepted distance for a small gap then they will not be considered. This is tested prior to computing the angular difference due to the expense of computing angles. Between this case and the angular case we have a similar metric to the cost function in "Automated Three-Dimensional Tracing of Neurons in Confocal and Brightfield Images"; however, the conditions under which we check for small gaps is when there are only two end points to be merged
+
**[[Gap distance is too large-]] The distance between the two points e_1, e_2  is computed to save computation.  If the distance is longer than the excepted small gap distance, then the traces will not be considered for merging. A cost function adapted from "Automated Three-Dimensional Tracing of Neurons in Confocal and Brightfield Images" will take into account small gaps with two end points.
−
**[[Consider possibility of loops]] Even though this might not be possible in the 3D case, if we were to use a 2D projection of the picture there might be a situation where multiple breaks might end in a loop. consider the cross sectioning of two neurites. A gap at anyone of the intersections could cause connection problems. This matter on the cost function this could mean a loop will form. This formation might not be correct, but I think we should at least consider it.  
+
**[[Consider possibility of loops]] Though less probable in 3D, often there are 2D projections of 3D images resulting in loops being in the images. Loops in the branching structure can be avoided by checking the parents, as a trace cannot have two parents, but there can be two children.  
 
[[Image:problem_graph.jpeg|200px|thumb|right| Two neurites that might cause a problem for the merging minor gaps algorithm.]]
 
[[Image:problem_graph.jpeg|200px|thumb|right| Two neurites that might cause a problem for the merging minor gaps algorithm.]]
 
*Another trace is a better fit (Cost Function)
 
*Another trace is a better fit (Cost Function)

Revision as of 20:35, 2 July 2009

Feature computation for Trace Editor

Feature List

Feature Description Equation or Variable
Gap Size Minimum distance between endpoints of two traces d= \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}
Angle The angle created between two traces normalized as vectors \theta = \arccos(\frac{v_1 \cdot v_2}{|v_1||v_2|})
Path Length Total length along a trace, indicated by the size of the trace L = \sum_{i=0}^{end - 1}\sqrt{(e_ix-e_{i+1}x)^2 + (e_iy-e_{i+1}y)^2+(e_iz-e_{i+1}z)^2}
Euclidean Distance Straight line distance between the endpoints of a trace D = \sqrt{(e_{1x}-e_{2x})^2 + (e_{1y}-e_{2y})^2+(e_{1z}-e_{2z})^2}
Fragmentation Smoothness Ratio of Path Length to Euclidean Distance[1] s= \frac{L}{D}
Maximum Gap Distance The maximum distance between endpoints that can be merged Δ
Weights The weights are used in the cost algorithm α β
Cost Weighted scalar evaluating the merge C=\alpha\frac{\theta}{\pi}+\beta\frac{d}{\Delta}
Curvature The Hessian matrix for checking branching point existence and interpolating the path. (Still under consideration) \left[\begin{array}{ccc} f(x)_{xx}(X) + \frac{\alpha}{2}f_{yy}(X) + \frac{\alpha}{2}f_{zz}(X) & (1-\alpha)f_{xy}(X) & (1-\alpha)f_{xz}(X) \\ (1-\alpha)f_{xy}(X) & f_{yy}(X) + \frac{\alpha}{2}f(x)_{xx}(X) +\frac{\alpha}{2}f_{zz}(X) & (1-\alpha)f_{yz}(X) \\ (1-\alpha)f_{xz}(X) & (1-\alpha)f_{yz}(X) & f_{zz}(X) + \frac{\alpha}{2}f(x)_{xx}(X) +\frac{\alpha}{2}f_{yy}(X) \end{array} \right]
Parent Considering nerves branching from the soma are a tree like structure, a parent point can be used to find a cycle.

Algorithms

The algorithms suggested are used to control the editing process allowing for rule based cluster editing. The Goal is to complete group editing in five steps.

Proposed steps of editing
1: Merge Small Gaps
Goal: Create longest continuous trace segments by merging close endpoints
Methods: Nearest neighbors  (Closest end points), 
Rejection based on conflicts and thresholds
  • Minimal distance between end points
    • Angle between traces- The angle is measured between the two traces by computing the norm of their vectors and the dot product.
      The equation is: v_1 \cdot v_2 = |v_1||v_2| \cos(\theta) which when solved for θ is: \theta = \arccos(\frac{v_1 \cdot v_2}{|v_1||v_2|})
    • Path length- The path length is considered if the end points are not the best fit for the merge. For instance, a merging that would cause a sharp peak in the neurite. This is a more serious problem for large gaps (see below). To help alleviate this for small gaps, merge at the point where the direction changes sharply.
    • Gap distance is too large- The distance between the two points e_1, e_2 is computed to save computation. If the distance is longer than the excepted small gap distance, then the traces will not be considered for merging. A cost function adapted from "Automated Three-Dimensional Tracing of Neurons in Confocal and Brightfield Images" will take into account small gaps with two end points.
    • Consider possibility of loops Though less probable in 3D, often there are 2D projections of 3D images resulting in loops being in the images. Loops in the branching structure can be avoided by checking the parents, as a trace cannot have two parents, but there can be two children.
Two neurites that might cause a problem for the merging minor gaps algorithm.
  • Another trace is a better fit (Cost Function)
    • Smallest gap
    • Better Angular alignment
  • "Bad merge"
    • The merge causes corners
    • Needs to be smoothed 
2: Interpolate Large Gaps
Goal: Connect Large gaps that step 1 cannot  simply connect by addition of a  single cell
Method: Larger gaps need new segments created, 
new Trace Bits must be added, 
smoothing operator.
Example showing how Merging and branching are interconnected. The Merging that creates sharp turns needs to be smoothed. The Traces need to create a new branch point and trace bits to interpolate the original path of the branch.
  • Curve fitting to find trend of:
    • Direction
    • Curvature
  • Interpolation
    • Extend the line
    • Most probable vector
    • Avoid creating edges 
3: Branch Points
Goal: Detect and control Branching
Method: Detect most probable intercepts, 
Determination of main branch and child, 
Type of branch point
  • Distance maps
    • Nearest neighbors (traces)
    • Closest trace bits
  • Angle of intercept
  • Interpolation 
4: Soma Detection
Goal: Correspond processes with a soma
Method: Segmentation of original data, 
Localize the area to attach processes to soma, 
Correct direction of traces
  • Image intensity
  • Blob segmentation
  • Centroid
  • Distance map
  • Connectivity
    • Connected components
    • Localization of processes
Illustration of how the processes should be connected to a soma(shown in red).
The Dendrites are shown in blue, where the axon is shown in yellow.
5: Fragments
Goal: Removal of small traces that do not correspond to a process
Method: Small traces removed, 
Leftovers from splitting operators, 
Line fragments that cannot be merged
  • Lowest percentile of length
    • Traces with no parents or children
    • Type dependent

References

Template:Reflist


Cite error: <ref> tags exist, but no <references/> tag was found
Retrieved from "http://farsight-toolkit.ee.uh.edu/wiki/Trace_Editor/Features"
Personal tools