Systems and methods for memory utilization for object detection

Patent metadata

Field	Value
Publication number	US-9286217-B2
Application number	US-201414468208-A
Country	US
Kind code	B2
Filing date	Aug 25, 2014
Priority date	Aug 26, 2013
Publication date	Mar 15, 2016
Grant date	Mar 15, 2016

Abstract

A method for memory utilization by an electronic device is described. The method includes transferring a first portion of a first decision tree and a second portion of a second decision tree from a first memory to a cache memory. The first portion and second portion of each decision tree are stored contiguously in the first memory. The first decision tree and second decision tree are each associated with a different feature of an object detection algorithm. The method also includes reducing cache misses by traversing the first portion of the first decision tree and the second portion of the second decision tree in the cache memory based on an order of execution of the object detection algorithm.

First claim

What is claimed is:

1. A method for memory utilization by an electronic device, comprising:
transferring a first portion of a first decision tree and a second portion of a second decision tree from a first memory to a cache memory, wherein the first portion and second portion of each decision tree are stored contiguously in the first memory, wherein the first decision tree and second decision tree are each associated with a different feature of an object detection algorithm; and
traversing the first portion of the first decision tree and the second portion of the second decision tree in the cache memory based on an order of execution of the object detection algorithm.

2. The method of claim 1 , wherein reducing cache misses results in lower latency for processing the object detection algorithm compared to when the first portion and second portions are not contiguously arranged in the first memory.

3. The method of claim 1 , wherein reducing cache misses results in less power consumption for processing the object detection algorithm compared to when the first portion and second portions are not contiguously arranged in the first memory.

4. The method of claim 1 , further comprising:
loading frequently grouped portions of decision trees together to fit in a fixed memory size; and
accessing the frequently grouped portions of the decision trees based on the order of execution of the object detection algorithm.

5. The method of claim 4 , wherein a feature in the object detection algorithm comprises a local binary pattern (LBP) feature.

6. The method of claim 1 , further comprising:
determining a feature based on an integral image;
determining how the feature will be saved in memory; and
storing the feature in the memory using at least one pointer and a width of a rectangle used in the feature.

7. The method of claim 6 , wherein the feature is stored in memory using two pointers and the width of the rectangle used in the feature.

8. The method of claim 6 , wherein the feature is stored in memory using one pointer, the width of each rectangle used in the feature and a height of each rectangle used in the feature.

9. The method of claim 6 , wherein the feature is stored in memory using four pointers and the width of the rectangle used in the feature.

10. The method of claim 6 , wherein the feature comprises a Haar feature.

11. An electronic device for memory utilization, comprising:
a processor;
memory in electronic communication with the processor; and
instructions stored in the memory, the instructions being executable by the processor to:
transfer a first portion of a first decision tree and a second portion of a second decision tree from a first memory to a cache memory, wherein the first portion and second portion of each decision tree are stored contiguously in the first memory, wherein the first decision tree and second decision tree are each associated with a different feature of an object detection algorithm; and
traverse the first portion of the first decision tree and the second portion of the second decision tree in the cache memory based on an order of execution of the object detection algorithm.

12. The electronic device of claim 11 , wherein reducing cache misses results in lower latency for processing the object detection algorithm compared to when the first portion and second portions are not contiguously arranged in the first memory.

13. The electronic device of claim 11 , wherein reducing cache misses results in less power consumption for processing the object detection algorithm compared to when the first portion and second portions are not contiguously arranged in the first memory.

14. The electronic device of claim 11 , further comprising:
loading frequently grouped portions of decision trees together to fit in a fixed memory size; and
accessing the frequently grouped portions of the decision trees based on the order of execution of the object detection algorithm.

15. The electronic device of claim 14 , wherein a feature in the object detection algorithm comprises a local binary pattern (LBP) feature.

16. The electronic device of claim 11 , further comprising:
determining a feature based on an integral image;
determining how the feature will be saved in memory; and
storing the feature in the memory using at least one pointer and a width of a rectangle used in the feature.

17. The electronic device of claim 16 , wherein the feature is stored in memory using two pointers and the width of the rectangle used in the feature.

18. The electronic device of claim 16 , wherein the feature is stored in memory using one pointer, the width of each rectangle used in the feature and a height of each rectangle used in the feature.

19. The electronic device of claim 16 , wherein the feature is stored in memory using four pointers and the width of the rectangle used in the feature.

20. The electronic device of claim 16 , wherein the feature comprises a Haar feature.

21. An apparatus for memory utilization, comprising:
means for transferring a first portion of a first decision tree and a second portion of a second decision tree from a first memory to a cache memory, wherein the first portion and second portion of each decision tree are stored contiguously in the first memory, wherein the first decision tree and second decision tree are each associated with a different feature of an object detection algorithm; and
means for traversing the first portion of the first decision tree and the second portion of the second decision tree in the cache memory based on an order of execution of the object detection algorithm.

22. The apparatus of claim 21 , wherein reducing cache misses results in lower latency for processing the object detection algorithm compared to when the first portion and second portions are not contiguously arranged in the first memory.

23. The apparatus of claim 21 , wherein reducing cache misses results in less power consumption for processing the object detection algorithm compared to when the first portion and second portions are not contiguously arranged in the first memory.

24. The apparatus of claim 21 , further comprising:
means for loading frequently grouped portions of decision trees together to fit in a fixed memory size; and
means for accessing the frequently grouped portions of the decision trees based on the order of execution of the object detection algorithm.

25. The apparatus of claim 21 , further comprising:
means for determining a feature based on an integral image;
means for determining how the feature will be saved in memory; and
means for storing the feature in the memory using at least one pointer and a width of a rectangle used in the feature.

26. A non-transitory tangible computer-readable medium having instructions thereon, the instructions comprising:
code for causing an electronic device to transfer a first portion of a first decision tree and a second portion of a second decision tree from a first memory to a cache memory, wherein the first portion and second portion of each decision tree are stored contiguously in the first memory, and wherein the first decision tree and second decision tree are each associated with a different feature of an object detection algorithm; and
code for causing the electronic device to traverse the first portion of the first decision tree and the second portion of the second decision tree in the cac

Assignees

• Qualcomm Inc

Inventors

• Xu Lei
• Zhou Bo
• Castelloe Michael Warren
• Quan Shuxue
• Zhang Xinping
• Du Junchen
• Harthattu Ashwath
• Guo Feng
• Qi Yingyong

Classifications

• G06K9/00973

  Physics · mapped topic

• G06F12/0802 Primary

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F2212/60

  Details of cache memory · CPC title

• G06V10/94 Primary

  Hardware or software architectures specially adapted for image or video understanding · CPC title