Method and System for Evaluation Using Probabilistic Boosting Trees

• US 20120069003A1
• Filed: 09/09/2011
• Published: 03/22/2012
• Est. Priority Date: 09/22/2010
• Status: Active Grant

• Current Assignee: Siemens Healthineers AG (Siemens AG)
• Original Assignee: Siemens Corp. (Siemens AG)
• Inventors: Sofka, Michal, Zhou, Shaohua Kevin, Birkbeck, Neil
• Granted Patent: US 8,860,715 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06V 10/446 using Haar-like filters, e.g. using integral image techniques
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

A method and system for evaluating probabilistic boosting trees is disclosed. In an embodiment, input data is received at a graphics processing unit. A weighted empirical distribution associated with each node of the probabilistic boosting tree is determined using a stack implementation. The weighted empirical distribution associated with each node is added to a total posterior distribution value.

Claims

1. A method for training a probabilistic boosting tree, comprising:

receiving training data at a graphics processing unit (GPU);

dividing the training data into a first dataset and a second dataset using a classifier;

training a first sub-tree and a second sub-tree at the GPU, the first sub-tree using the first dataset and the second sub-tree using the second dataset;

generating a posterior distribution model based on the trained first sub-tree and the trained second sub-tree.

2. The method of claim 1, wherein training a first sub-tree and a second sub-tree at the GPU comprises:

training a classifier at each node of the first sub-tree and the second sub-tree.

3. The method of claim 2, wherein training a classifier at each node of the first sub-tree and the second sub-tree comprises:

computing a feature matrix for each node.

4. The method of claim 3, computing a feature matrix for each node comprises:

computing feature bounds;

mapping feature values to samples within a histogram bin based on the feature bounds; and

computing an error associated with each classifier.

5. The method of claim 1, further comprising:

determining a set of classifications based on the posterior distribution model.

6. The method of claim 1, wherein the method for evaluating a probabilistic boosting tree is implemented using a parallel computing architecture.

8. The method of claim 1, further comprising:

detecting structures in a 3D volume using the trained probabilistic boosting tree.

7. The method of claim 7, wherein the parallel computing architecture is Compute Unified Device Architecture (CUDA).

9. A method for determining the posterior distribution of a probabilistic boosting tree, comprising:

receiving input data at a graphics processing unit (GPU)

determining a weighted empirical distribution associated with each node of the probabilistic boosting tree using a stack implementation;

adding the weighted empirical distribution associated with each node to a total posterior distribution value.

10. The method of claim 9, wherein determining a weighted empirical distribution associated with each node of the probabilistic boosting tree using a stack implementation comprises:

pushing a root node of the probabilistic boosting tree onto a stack;

determining whether to descend down the probabilistic boosting tree thru a node in a left sub-tree or thru a node in a right sub-tree.

11. The method of claim 10, wherein determining whether to descend down the probabilistic boosting tree thru a node in a left sub-tree or thru a node in a right sub-tree comprises:

determining a discriminative classifier of the root node;

if the discriminative classifier of the root node satisfies a first condition, descending a left node in the left sub-tree;

if the discriminative classifier of the root node satisfies a second condition, descending a right node in the right sub-tree; and

if the discriminative classifier of the root node satisfies a third condition, descending both the left node and the right node;

wherein the first condition signifies that a left node must be descended, the second condition signifies that a right node must be descended, and the third condition signifies that both a left node and a right node must be descended.

12. The method of claim 11, wherein descending to a left node in the left sub-tree comprises:

determining a discriminative classifier of the left node;

if the left node is a leaf node, adding a weighted empirical distribution of the left node to the total posterior distribution value;

if the left node satisfies the first condition, pushing the left node onto the stack and descend a left child node of the left node;

if the left node satisfies the second condition, pushing the left node onto the stack and descend a right child node of the left node;

if the left node satisfies the third condition, pushing the left node onto the stack and descend both the left child node and the right child node.

13. The method of claim 11, wherein descending to a right node in the right sub-tree comprises:

determining a discriminative classifier of the right node;

if the right node is a leaf node, adding a weighted empirical weighted distribution of the left node to the total posterior distribution value;

if the right node satisfies the first condition, pushing the right node onto the stack and descend a left child node of the right node;

if the right node satisfies the second condition, pushing the right node onto the stack and descend a right child node of the right node;

if the right node satisfies the third condition, pushing the right node onto the stack and descend both the left child node and the right child node.

14. The method of claim 9, wherein the method for evaluating a probabilistic boosting tree is implemented using a parallel computing architecture.

15. The method of claim 9, wherein the parallel computing architecture is Compute Unified Device Architecture (CUDA).

16. The method of claim 11, wherein the stack is associated with one of a plurality of threads running in parallel.

17. A method for evaluating a forest of probabilistic boosting trees, comprising:

receiving input data at a graphics processing unit (GPU);

evaluating the plurality of probabilistic boosting trees using a stack implementation;

generating a combined posterior distribution based on a posterior distribution of each of the plurality of probabilistic boosting trees.

18. A system for training a probabilistic boosting tree, comprising:

means for receiving training data at a graphics processing unit (GPU);

means for dividing the training data into a first dataset and a second dataset using a classifier;

means for training a first sub-tree and a second sub-tree at the GPU, the first sub-tree using the first dataset and the second sub-tree using the second dataset;

means for generating a posterior distribution model based on the trained first sub-tree and the trained second sub-tree.

19. The system of claim 18, wherein means for training a first sub-tree and a second sub-tree at the GPU comprises:

means for training a classifier at each node of the first sub-tree and the second sub-tree.

20. The system of claim 19, wherein means for training a classifier at each node of the first sub-tree and the second sub-tree comprises:

means for computing a feature matrix for each node.

21. The system of claim 20, wherein means for computing a feature matrix for each node comprises:

means for computing feature bounds;

means for mapping feature values to samples within a histogram bin based on the feature bounds; and

means for computing an error associated with each classifier.

22. The system of claim 18, further comprising:

means for determining a set of classifications based on the posterior distribution model.

23. The system of claim 18, wherein the system for evaluating a probabilistic boosting tree is a parallel computing architecture.

24. The system of claim 23, wherein the parallel computing architecture is Compute Unified Device Architecture (CUDA).

25. The system of claim 18, further comprising:

means for detecting structures in a 3D volume using the trained probabilistic boosting tree.

26. A system for determining the posterior distribution of a probabilistic boosting tree, comprising:

means for receiving input data at a graphics processing unit (GPU)

means for determining a weighted empirical distribution associated with each node of the probabilistic boosting tree using a stack implementation;

means for adding the weighted empirical distribution associated with each node to a total posterior distribution value.

27. The system of claim 26, wherein means for determining a weighted empirical distribution associated with each node of the probabilistic boosting tree using a stack implementation comprises:

means for pushing a root node of the probabilistic boosting tree onto a stack;

means for determining whether to descend down the probabilistic boosting tree thru a node in a left sub-tree or thru a node in a right sub-tree.

28. The system of claim 27, wherein means for determining whether to descend down the probabilistic boosting tree thru a node in a left sub-tree or thru a node in a right sub-tree comprises:

means for determining a discriminative classifier of the root node;

means for descending a left node in the left sub-tree if the discriminative classifier of the root node satisfies a first condition;

means for descending a right node in the right sub-tree if the discriminative classifier of the root node satisfies a second condition; and

means for descending both the left node and the right node if the discriminative classifier of the root node satisfies a third condition;

wherein the first condition signifies that a left node must be descended, the second condition signifies that a right node must be descended, and the third condition signifies that both a left node and a right node must be descended.

29. The system of claim 28, wherein means for descending to a left node in the left sub-tree comprises:

means for determining the discriminative classifier of the left node;

means for adding a weighted empirical weighted distribution of the left node to the total posterior distribution value if the left node is a leaf node;

means for pushing the left node onto the stack and descend a left child node of the left node if the left node satisfies the first condition;

means for pushing the left node onto the stack and descend a right child node of the left node if the left node satisfies the second condition;

means for pushing the left node onto the stack and descend both the left child node and the right child node if the left node satisfies the third condition.

30. The system of claim 28, wherein means for descending to a right node in the right sub-tree comprises:

means for determining the discriminative classifier of the right node;

means for adding a weighted empirical distribution of the left node to the total posterior distribution value if the right node is a leaf node;

means for pushing the right node onto the stack and descend a left child node of the right node if the right node satisfies the first condition;

means for pushing the right node onto the stack and descend a right child node of the right node if the right node satisfies the second condition;

means for pushing the right node onto the stack and descend both the left child node and the right child node if the right node satisfies the third condition.

31. The system of claim 26, wherein the system for evaluating a probabilistic boosting tree is implemented using a parallel computing architecture.

32. The system of claim 31, wherein the parallel computing architecture is Compute Unified Device Architecture (CUDA).

33. The system of claim 28, wherein the stack is associated with one of a plurality of threads running in parallel.

34. A system for evaluating a forest of probabilistic boosting trees, comprising:

means for receiving input data at a graphics processing unit (GPU);

means for evaluating the plurality of probabilistic boosting trees using a stack implementation;

means for generating a combined posterior distribution based on a posterior distribution of each of the plurality of probabilistic boosting trees.

35. A non-transitory computer readable medium encoded with computer executable instructions for training a probabilistic boosting tree, the computer executable instructions defining steps comprising:

receiving training data at a graphics processing unit (GPU);

dividing the training data into a first dataset and a second dataset using a classifier;

training a first sub-tree and a second sub-tree at the GPU, the first sub-tree using the first dataset and the second sub-tree using the second dataset;

generating a posterior distribution model based on the trained first sub-tree and the trained second sub-tree.

36. The computer readable medium of claim 35, wherein the computer executable instructions defining the step of training a first sub-tree and a second sub-tree at the GPU comprises computer executable instructions defining the step of:

training a classifier at each node of the first sub-tree and the second sub-tree.

computing an empirical distribution to determine the first dataset to send to the first sub-tree and to determine the second dataset to send to the second sub-tree.

37. The computer readable medium of claim 36, wherein the computer executable instructions defining the step of training a classifier at each node of the first sub-tree and the second sub-tree comprises computer executable instructions defining the step of:

computing a feature matrix for each node.

38. The computer readable medium of claim 37, wherein the computer executable instructions defining the step of computing a feature matrix for each node comprises wherein the computer executable instructions defining the steps of:

computing feature bounds;

mapping feature values to samples within a histogram bin based on the feature bounds; and

computing an error associated with each classifier.

39. The computer readable medium of claim 35, further comprising computer executable instruction defining the step of:

determining a set of classifications based on the posterior distribution model.

40. The computer readable medium of claim 35, wherein the computer executable instructions for evaluating a probabilistic boosting tree are implemented using a parallel computing architecture.

41. The computer readable medium of claim 40, wherein the parallel computing architecture is Compute Unified Device Architecture (CUDA).

42. The computer readable medium of claim 35, further comprising computer executable instructions defining the step of:

detecting structures in a 3D volume using the trained probabilistic boosting tree.

43. A non-transitory computer readable medium encoded with computer executable instructions for determining the posterior distribution of a probabilistic boosting tree, the computer executable instructions defining steps comprising:

receiving input data at a graphics processing unit (GPU);

determining a weighted empirical distribution associated with each node of the probabilistic boosting tree using a stack implementation;

adding the weighted empirical distribution associated with each node to a total posterior distribution value.

44. The computer readable medium of claim 43, wherein the computer executable instructions defining the step of determining a weighted empirical distribution associated with each node of the probabilistic boosting tree using a stack implementation comprises computer executable instructions defining the steps of:

pushing a root node of the probabilistic boosting tree onto a stack;

determining whether to descend down the probabilistic boosting tree thru a node in a left sub-tree or thru a node in a right sub-tree.

45. The computer readable medium of claim 44, wherein the computer executable instructions defining the step of determining whether to descend down the probabilistic boosting tree thru a node in a left sub-tree or thru a node in a right sub-tree comprises computer executable instructions defining the steps of:

determining a discriminative classifier of the root node;

if the discriminative classifier of the root node satisfies a first condition, descending a left node in the left sub-tree;

if the discriminative classifier of the root node satisfies a second condition, descending a right node in the right sub-tree; and

if the discriminative classifier of the root node satisfies a third condition, descending both the left node and the right node;

wherein the first condition signifies that a left node must be descended, the second condition signifies that a right node must be descended, and the third condition signifies that both a left node and a right node must be descended.

46. The computer readable medium of claim 45, wherein the computer executable instructions defining the step of descending to a left node in the left sub-tree comprises computer executable instructions defining the steps of:

determining the discriminative classifier of the left node;

if the left node is a leaf node, adding a weighted empirical weighted distribution of the left node to the total posterior distribution value;

if the left node satisfies the first condition, pushing the left node onto the stack and descend a left child node of the left node;

if the left node satisfies the second condition, pushing the left node onto the stack and descend a right child node of the left node;

if the left node satisfies the third condition, pushing the left node onto the stack and descend both the left child node and the right child node.

47. The computer readable medium of claim 45, wherein the computer executable instructions defining the step of descending to a right node in the right sub-tree comprises computer executable instructions defining the steps of:

determining the discriminative classifier of the right node;

if the right node is a leaf node, adding a weighted empirical weighted distribution of the left node to the total posterior distribution value;

if the right node satisfies the first condition, pushing the right node onto the stack and descend a left child node of the right node;

if the right node satisfies the second condition, pushing the right node onto the stack and descend a right child node of the right node;

if the right node satisfies the third condition, pushing the right node onto the stack and descend both the left child node and the right child node.

48. The computer readable medium of claim 43, wherein the computer executable instructions for evaluating a probabilistic boosting tree are implemented using a parallel computing architecture.

49. The computer readable medium of claim 48, wherein the parallel computing architecture is Compute Unified Device Architecture (CUDA).

50. The computer readable medium of claim 45, wherein the stack is associated with one of a plurality of threads running in parallel.

51. A non-transitory computer readable medium encoded with computer executable instructions for evaluating a forest of probabilistic boosting trees, the computer executable instructions defining steps comprising:

receiving input data at a graphics processing unit (GPU);

evaluating the plurality of probabilistic boosting trees using a stack implementation;

generating a combined posterior distribution based on a posterior distribution of each of the plurality of probabilistic boosting trees.