System and method for path based tree matching
View Patent ↗A system and method for tree matching are provided. The method for tree matching includes: acquiring tree-like structures representing a physical object or model; extracting a path from a first tree-like structure and a path from a second tree-like structure; comparing the paths of the first and second tree-like structures by computing a similarity measurement for the paths; and determining if the paths match based on the similarity measurement.
1. A method for tree matching, comprising:
using a processor to carry out the steps of:
acquiring first and second tree-like structures representing a physical object or model, wherein each tree-like structure includes a plurality of paths;
comparing a first path of the first tree-like structure to each path of the second tree-like structure, wherein a similarity measurement is computed for each path to which the first path is compared; and
identifying the path of the second tree-like structure that matches the first path as the path with the lowest similarity measurement,
wherein the similarity measurement for a path to which the first path is compared is computed by calculating a mean distance between the path and the first path, a mean difference between directions of the path and the first path and a variance in the distance between the path and the first path.
2. The method of claim 1 , further comprising:
using the processor to carry out the step of:
repeating the comparing and identifying steps until each path of the tree-like structures has been matched or excluded.
3. The method of claim 2 , wherein the paths of the tree-like structures are compared according to a hierarchy of one or both of the tree-like structures.
4. The method of claim 3 , further comprising:
using the processor to carry out the step of:
determining if the paths of the tree-like structures match based on similarity measurements of other paths of the tree-like structures.
5. The method of claim 4 , further comprising:
using the processor to carry out the step of:
generating a matching matrix for recording matched paths.
6. The method of claim 4 , further comprising:
using the processor to carry out the step of:
generating a probability matrix for matching a path to a next-best matching path when a best matching path has already been matched to another path.
7. The method of claim 2 , further comprising:
using the processor to carry out the step of:
aligning the tree-like structures before comparing the first path to the paths of the second tree-like structure.
8. The method of claim 1 , wherein the tree-like structures are airways, arteries or veins.
9. The method of claim 1 , wherein the tree-like structures are acquired by tracking, segmentation, or skeletonization.
10. The method of claim 1 , further comprising:
using the processor to carry out the step of:
extracting paths from the tree-like structures, prior to comparing the paths, wherein the paths are extracted by segmentation, centerline extraction or directly from the tree-like structures.
11. The method of claim 10 , wherein extracting the paths comprises selecting one of the paths of one of the tree-like structures as the path to be compared to the paths of the other tree-like structure.
12. The method of claim 11 , wherein a short path, which matches a sub-section of a long path, is selected as the path of one of the tree-like structures to be compared to the paths of the other tree-like structure.
13. A system for tree matching, comprising:
a memory device for storing a program;
a processor in communication with the memory device, the processor operative with the program to:
acquire first and second tree-like structures representing a physical object or model, wherein each tree-like structure includes a plurality of paths;
compare a first path of the first tree-like structure to each path of the second tree-like structure, wherein a similarity measurement is computed for each path to which the first path is compared; and
identify the path of the second tree-like structure that matches the first path as the path with the lowest similarity measurement,
wherein the similarity measurement for a path to which the first path is compared is computed by calculating a mean distance between the path and the first path, a mean difference between directions of the path and the first path and a variance in the distance between the path and the first path.
14. The system of claim 13 , wherein the processor is further operative with the program to:
repeat the comparing and identifying steps until each path of the tree-like structures has been matched or excluded.
15. The system of claim 14 , wherein the paths of the tree-like structures are compared according to a hierarchy of one or both of the tree-like structures.
16. The system of claim 15 , wherein the processor is further operative with the program to:
determine if the paths of the tree-like structures match based on similarity measurements of other paths of the tree-like structures.
17. The system of claim 16 , wherein the processor is further operative with the program to:
generate a matching matrix for recording matched paths.
18. The system of claim 16 , wherein the processor is further operative with the program to:
generate a probability matrix for matching a path to a next-best matching path when a best matching path has already been matched to another path.
19. The system of claim 14 , wherein the processor is further operative with the program to:
align the tree-like structures before comparing the first path to the paths of the second tree-like structure.
20. The system of claim 13 , wherein the tree-like structures are airways, arteries or veins.
21. The system of claim 13 , wherein the tree-like structures are acquired by tracking, segmentation, or skeletonization.
22. The system of claim 13 , wherein the processor is further operative with the program to:
extract paths from the tree-like structures, prior to comparing the paths, wherein the paths are extracted by segmentation, centerline extraction or directly from the tree-like structures.
23. The system of claim 22 , wherein extracting the paths comprises selecting one of the paths of one of the tree-like structures as the path to be compared to the paths of the other tree-like structure.
24. The system of claim 23 , wherein a short path, which matches a sub-section of a long path, is selected as the path of one of the tree-like structures to be compared to the paths of the other tree-like structure.
25. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for tree matching, the method comprising:
acquiring first and second tree-like structures representing a physical object or model, wherein each tree-like structure includes a plurality of paths;
comparing a first path of the first tree-like structure to each path of the second tree-like structure, wherein a similarity measurement is computed for each path to which the first path is compared; and
identifying the path of the second tree-like structure that matches the first path as the path with the lowest similarity measurement,
wherein the similarity measurement for a path to which the first path is compared is computed by calculating a mean distance between the path and the first path, a mean difference between directions of the path and the first path and a variance in the distance between the path and the first path.