Methods and devices for labeling and/or matching

Patent metadata

Field	Value
Publication number	US-9820651-B2
Application number	US-201313987683-A
Country	US
Kind code	B2
Filing date	Aug 21, 2013
Priority date	May 5, 2004
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

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.

First claim

We claim:

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.

Assignees

• Univ Iowa Res Found
• Garrett Mark T

Inventors

• Tschirren Juerg
• Sonka Milan
• Reinhardt Joseph
• Mclennan Geoffrey
• Hoffman Eric

Classifications

• A61B5/08

  Measuring devices for evaluating the respiratory organs · CPC title

• G16H50/50

  for simulation or modelling of medical disorders · CPC title

• A61B5/00 Primary

  Measuring for diagnostic purposes (radiation diagnosis A61B6/00; diagnosis by ultrasonic, sonic or infrasonic waves A61B8/00); Identification of persons · CPC title

• G06T19/00 Primary

  Manipulating three-dimensional [3D] models or images for computer graphics · CPC title

• G06V10/426

  Graphical representations · CPC title