Efficient decision tree traversal in an adaptive boosting (AdaBoost) classifier

1. A method for object classification in a decision tree based adaptive boosting classifier, the method comprising:

retrieving, by a single-instruction multiple data (SIMD) processor from memory, feature vectors extracted from N consecutive window positions in an image stored in the memory, wherein N is a vector width of the SIMD processor divided by a bit size of a feature, and wherein a feature vector comprises N feature values, one feature value for each of the N consecutive window positions; and

evaluating, by the SIMD processor, the N consecutive window positions concurrently, using the feature vectors and vector instructions of the SIMD processor, wherein the SIMD processor concurrently traverses decision trees for the N consecutive window positions, wherein a decision tree comprises a plurality of nodes, a threshold value for each node, and a plurality of leaves, each leaf comprising a partial score.

2. The method of claim 1 , wherein evaluating the N consecutive window positions comprises:

loading a plurality of the feature vectors using a vector load instruction of the SIMD processor, wherein one feature vector is loaded for each node of a single decision tree of the adaptive boosting classifier;

comparing each feature vector to a corresponding threshold vector using a vector compare instruction of the SIMD processor to generate a mask vector for each node, wherein the corresponding threshold vector comprises N copies of the threshold value for the node corresponding to the feature vector, and wherein the mask vector comprises N comparison results, one for each of the N features of the feature vector;

generating a partial score vector based on the mask vectors and the partial score values of the leaves of the decision tree, the partial score vector comprising N partial score values, one for each of the N consecutive window positions;

accumulating the N partial score values into an accumulated score vector, the accumulated score vector comprising N accumulated score values, one for each of the N consecutive window positions; and

comparing the accumulated score vector to an exit threshold vector using a vector compare instruction of the SIMD processor to determine whether or not object classification can be terminated for one or more of the N consecutive window positions.

3. The method of claim 2 , wherein generating the partial score vector comprises:

generating a leaf selection mask vector for each of the leaves of the decision tree based on the mask vectors, wherein the leaf selection mask vector is a logical combination of mask vectors for nodes in a traversal path of the single decision tree that reaches the leaf corresponding to the leaf selection mask vector; and

performing a logical and operation of each leaf selection mask vector with a corresponding leaf vector to select partial score values for each of the N consecutive window positions from the leaf vectors, wherein a corresponding leaf vector comprises N copies of a partial score of the leaf.

4. The method of claim 1 , wherein the decision trees are two-level binary decision trees.

5. The method of claim 1 , wherein the adaptive boosting classifier is trained for pedestrian classification.

6. The method of claim 1 , wherein the SIMD processor is a digital signal processor.

7. A digital system, comprising:

a single-instruction multiple-data (SIMD) processor;

a non-transitory computer readable storage medium coupled to the SIMD processor, the non-transitory computer readable storage medium storing:

features extracted from an image;

a plurality of decision trees, wherein each decision tree comprises a plurality of nodes, a threshold value for each node, and a plurality of leaves, each leaf comprising a partial score; and

a program for execution by the SIMD processor, the program including instructions for a decision tree based adaptive boosting classifier trained for object classification instructions to evaluate N consecutive window positions concurrently using the features and vector instructions of the SIMD processor, wherein the SIMD processor concurrently traverses decision trees for the N consecutive window positions, and wherein N is a vector width of the SIMD processor divided by a bit size of a feature.

8. The digital system of claim 7 , wherein the instructions further comprise instructions to extract the features from the N consecutive window positions in the image.

9. The digital system of claim 8 , comprising a camera coupled to the SIMD processor, the camera to provide the image.

10. The digital system of claim 7 , wherein the instructions further comprise instructions to evaluate the N consecutive window positions by:

loading a plurality of feature vectors from the non-transitory computer readable storage medium using a vector load instruction of the SIMD processor, wherein one feature vector is loaded for each node of a single decision tree of the plurality of decision trees and wherein a feature vector comprises N feature values, one feature value for each of the N consecutive window positions;

comparing each feature vector to a corresponding threshold vector using a vector compare instruction of the SIMD processor, to generate a mask vector for each node, wherein the corresponding threshold vector comprises N copies of the threshold value for the node corresponding to the feature vector, and wherein the mask vector comprises N comparison results, one for each of the N features of the feature vector;

generating a partial score vector based on the mask vectors and the partial score values of the leaves of the decision tree, the partial score vector comprising N partial score values, one for each of the N consecutive window positions;

accumulating the partial score values into an accumulated score vector, the accumulated score vector comprising N accumulated score values, one for each of the N consecutive window positions; and

comparing the accumulated score vector to an exit threshold vector using a vector compare instruction of the SIMD processor, to determine whether or not object classification termination for one or more of the N consecutive window positions.

11. The digital system of claim 10 , wherein generating the partial score vector comprises:

generating a leaf selection mask vector for each of the leaves of the decision tree based on the mask vectors, wherein the leaf selection mask vector is a logical combination of mask vectors for nodes in a traversal path of the single decision tree that reaches the leaf corresponding to the leaf selection mask vector; and

performing a logical and operation of each leaf selection mask vector with a corresponding leaf vector to select partial score values for each of the N window positions from the leaf vectors, wherein a corresponding leaf vector comprises N copies of a partial score of the leaf.

12. The digital system of claim 7 , wherein the decision trees are two level binary decision trees.

13. The digital system of claim 7 , wherein the adaptive boosting classifier is trained for pedestrian classification.

14. The digital system of claim 7 , wherein the SIMD processor is a digital signal processor.

15. A non-transitory computer readable storage medium storing a program for execution by a single-instruction multiple-data (SIMD) processor, for object classification in a decision tree based adaptive boosting classifier, the program including instructions for:

retrieving, from the non-transitory computer readable storage medium, feature vectors extracted from N consecutive window positions in an image, wherein N is a vector width of the SIMD processor divided by a bit size of a feature, and wherein a feature vector comprises N feature values, one feature value for each of the N consecutive window positions; and

evaluating the N consecutive window positions concurrently, using the feature vectors and vector instructions of the SIMD processor, concurrently traversing decision trees for the N consecutive window positions, wherein a decision tree comprises a plurality of nodes, a threshold value for each node, and a plurality of leaves, each leaf comprising a partial score.

16. The non-transitory computer readable storage medium of claim 15 , wherein the instructions for evaluating the N consecutive window positions comprise instructions for:

loading a plurality of the feature vectors using a vector load instruction of the SIMD processor, wherein one feature vector is loaded for each node of a single decision tree of the adaptive boosting classifier;

comparing each feature vector to a corresponding threshold vector using a vector compare instruction of the SIMD processor, to generate a mask vector for each node, wherein the corresponding threshold vector comprises N copies of the threshold value for the node corresponding to the feature vector, and wherein the mask vector comprises N comparison results, one for each of the N features of the feature vector;

generating a partial score vector based on the mask vectors and the partial score values of the leaves of the decision tree, the partial score vector comprising N partial score values, one for each of the N consecutive window positions;

accumulating the partial score values into an accumulated score vector, the accumulated score vector comprising N accumulated score values, one for each of the N consecutive window positions; and

comparing the accumulated score vector to an exit threshold vector using a vector compare instruction of the SIMD processor, to determine termination of object classification for one or more of the N consecutive window positions.

17. The non-transitory computer readable storage medium of claim 16 , wherein the instructions for generating a partial score vector comprise instructions for:

generating a leaf selection mask vector for each of the leaves of the decision tree based on the mask vectors, wherein the leaf selection mask vector is a logical combination of mask vectors for nodes in a traversal path of the single decision tree that reaches the leaf corresponding to the leaf selection mask vector; and

performing a logical and operation of each leaf selection mask vector with a corresponding leaf vector, to select partial score values for each of the N window positions from the leaf vectors, wherein a corresponding leaf vector comprises N copies of a partial score of the leaf.

18. The non-transitory computer readable storage medium of claim 15 , wherein the decision trees are two-level binary decision trees.

19. The non-transitory computer readable storage medium of claim 15 , wherein the adaptive boosting classifier is trained for pedestrian classification.

20. The non-transitory computer readable storage medium of claim 15 , wherein the SIMD processor is a digital signal processor.