Methods and devices for labeling and/or matching
Devices, such as computer readable media, and methods, such as automated methods, for labeling and/or matching. Some of the devices and methods are particularly useful for anatomical labeling of human airway trees. Some of the devices and methods are particularly useful for matching branch-points of human airway trees from represented in two or more graphs.
1. A non-transitory computer readable medium comprising machine readable instructions for:
accessing a representation of a target tree, the representation having edges and vertices;
identifying a vertex in the representation that includes a first out-edge, a second out-edge and an in-edge, where the second out-edge is a terminal edge and where a first vertex defines one end of the first out-edge and a second vertex defines one end of the in-edge, and where the vertex, the first vertex, and the second vertex are different from each other; and
introducing an edge to the representation that extends between the first vertex and second vertex,
where the target tree comprises a human airway tree.
2. The computer readable medium of claim 1 , where the representation is based on volumetric image data taken using computed tomography.
3. The computer readable medium of claim 1 , where the representation is based on volumetric image data taken using magnetic resonance.
4. The computer readable medium of claim 1 , where the human airway tree is diseased.
5. The computer readable medium of claim 1 , also including machine readable instructions for:
computing an inheritance relationship for each possible pair of edges in the representation.
6. The computer readable medium of claim 5 , also including machine readable instructions for:
computing a topological distance between each possible pair of edges in the representation.
7. The computer readable medium of claim 1 , also including machine readable instructions for:
deleting from the representation any terminal branch having a length shorter than a pre-defined threshold length.
8. The computer readable medium of claim 1 , also including machine readable instructions for:
accessing data that includes (a) a reference tree having labels and reference tree edges, and (b) inheritance relationship data about some of the reference tree edges; and
building a tree association graph, where the building includes:
adding a first edge to the tree association graph if (i) a corresponding edge of the representation has an inheritance relationship that is the same as the inheritance relationship of a corresponding reference tree edge, and (ii) the topological distance between a vertex of the first edge and a vertex of the corresponding edge of the representation tree is within a certain limit.
9. The computer readable medium of claim 8 , where the tree association graph has a maximum weighted clique, and the computer readable medium also includes machine readable instructions for:
identifying the maximum weighted clique.
10. The computer readable medium of claim 1 , also including machine readable instructions for:
building a tree association graph having segments and sub-trees; and
labeling some segments of the tree association graph in a series of steps, where one sub-tree is labeled in each step.
11. The computer readable medium of claim 1 , also including machine readable instructions for:
building a tree association graph having branch-points and sub-trees; and
labeling some branch-points of the tree association graph in a series of steps, where one sub-tree is labeled in each step.