Patent Document ID: 8842894
Application ID: 13454765
Patent Flag: 1

Claim One:
1. A tree structure extraction apparatus that extracts, from medical image data including a first linear structure and a second linear structure, each repeatedly branching from an origin and extending in directions away from the origin in such a manner to become wider, the first linear structure and the second linear structure as a first tree structure and a second tree structure respectively, each being defined by a plurality of nodes including a root node corresponding to the origin and a plurality of edges connecting the plurality of nodes, the apparatus comprising: a computer and a memory wherein the memory causes the computer to function as a tree structure creation means that creates, based on the medical image data, a candidate of a tree structure defined by a plurality of undetermined nodes representing the first linear structure and the second linear structure and a plurality of undetermined edges connecting the plurality of undetermined nodes, and determines a first root node corresponding to the origin of the first linear structure, as a node constituting the first tree structure, and also a second root node corresponding to the origin of the second linear structure, as a node constituting the second tree structure, in the created candidate of the tree structure, and that compares costs representing probabilities of connection of the undetermined edges connected to the first root node and costs representing probabilities of connection of the undetermined edges connected to the second root node, and selects, as a determined edge, the undetermined edge having the cost representing the highest probability of connection from the edges the costs of which have been compared, and selects, as a determined node, the undetermined node connected to the determined edge, and that repeats processing of comparing costs representing probabilities of connection of all of the undetermined edges connected to the determined nodes, and selecting, as a determined edge, the undetermined edge that has a cost representing the highest probability of connection from the undetermined edges the costs of which have been compared, and selecting, as a determined node, the undetermined node connected to the determined edge, thereby making all of the undetermined nodes in the candidate of the tree structure determined, and creates the first tree structure defined by the determined edges and the determined nodes, and the origin of which is the first root node, and the second tree structure defined by the determined edges and the determined nodes, and the origin of which is the second root node, wherein the costs are weighted in such a manner that a probability of connection of an edge satisfying the characteristic that each of the first linear structure and the second linear structure repeatedly branches from its origin and extends in directions away from the origin in such a manner to become wider is higher.