Descriptor storage and searches of k-dimensional trees

• US 8,706,711 B2
• Filed: 12/29/2011
• Issued: 04/22/2014
• Est. Priority Date: 06/22/2011
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Vaddadi, Sundeep, Hamsici, Onur C., Hong, John H., Reznik, Yuriy, Lee, Chong U.
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US13/340,024
• Publication Number:
  US 20120330967A1
• Time in Patent Office: 845 Days
• Field of Search: 707/706, 707/797
• US Class Current: 707/706
• CPC Class Codes: G06F 18/211 Selection of the most significant subset of features
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

Various arrangements for using a k-dimensional tree for a search are presented. A plurality of descriptors may be stored. Each of the plurality of descriptors stored is linked with a first number of stored dimensions. The search may be performed using the k-dimensional tree for one or more query descriptors that at least approximately match one or more of the plurality of descriptors linked with the first number of stored dimensions. The k-dimensional tree may be built using the plurality of descriptors wherein each of the plurality of descriptors is linked with a second number of dimensions when the k-dimensional tree is built. The second number of dimensions may be a greater number of dimensions than the first number of stored dimensions.

Claims

1. A method for using k-dimensional trees for a search, the method comprising:

storing a first plurality of descriptors, wherein each of the first plurality of descriptors stored is linked with a first number of stored dimensions;

searching, by a computer system, a first k-dimensional tree with a query descriptor for a matching descriptor from among the first plurality of descriptors linked with the first number of stored dimensions, wherein;

the first k-dimensional tree is built using the first plurality of descriptors wherein each of the first plurality of descriptors is linked with a second number of dimensions when the first k-dimensional tree is built; and

the second number of dimensions is a greater number of dimensions than the first number of stored dimensions;

storing, by the computer system, a second plurality of descriptors, wherein each of the second plurality of descriptors stored is linked with the first number of stored dimensions; and

following searching the first k-dimensional tree, searching, by the computer system, a second k-dimensional tree using the query descriptor to find the matching descriptor from among the second plurality of descriptors linked with the first number of stored dimensions, wherein

the second k-dimensional tree is built using the second plurality of descriptors wherein each of the second plurality of descriptors is linked with the second number of dimensions when the second k-dimensional tree is built.

2. The method for using k-dimensional trees for the search of claim 1, further comprising:

building the first k-dimensional tree using the first plurality of descriptors, wherein;

each of the first plurality of descriptors is linked with the second number of dimensions when the first k-dimensional tree is built; and

the first plurality of descriptors are at least partially based on image data.

3. The method for using k-dimensional trees for the search of claim 2, wherein:

each dimension stored as part of the first number of stored dimensions matches a dimension of the second number of dimensions used to build the first k-dimensional tree.

4. The method for using k-dimensional trees for the search of claim 2, wherein:

each dimensions stored as part of the first number of stored dimensions is compressed using a PCA sub-space projection.

5. The method for using k-dimensional trees for the search of claim 1, further comprising:

determining the query descriptor based on a query image.

6. The method for using k-dimensional trees for the search of claim 5, further comprising:

identifying one or more images that at least approximately match the query image based at least in part on the search using the second k-dimensional tree.

7. The method for using k-dimensional trees for the search of claim 1, wherein searching the second k-dimensional tree is performed because the matching descriptor was not located when searching the first k-dimensional tree.

8. A computer-readable medium comprising instructions configured to cause a computer to:

store a first plurality of descriptors, wherein each of the first plurality of descriptors stored is linked with a first number of stored dimensions;

search a first k-dimensional tree with a query descriptor for a matching descriptor from among the first plurality of descriptors linked with the first number of stored dimensions, wherein;

the first k-dimensional tree is built using the first plurality of descriptors wherein each of the first plurality of descriptors is linked with a second number of dimensions when the first k-dimensional tree is built; and

the second number of dimensions is a greater number of dimensions than the first number of stored dimensions;

store a second plurality of descriptors, wherein each of the second plurality of descriptors stored is linked with the first number of stored dimensions; and

following searching the first k-dimensional tree, search a second k-dimensional tree using the query descriptor to find the matching descriptor from among the second plurality of descriptors linked with the first number of stored dimensions, wherein

the second k-dimensional tree is built using the second plurality of descriptors wherein each of the second plurality of descriptors is linked with the second number of dimensions when the second k-dimensional tree is built.

9. The computer-readable medium of claim 8, wherein the instructions are further configured to cause the computer to:

build the first k-dimensional tree using the first plurality of descriptors, wherein;

each of the first plurality of descriptors is linked with the second number of dimensions when the first k-dimensional tree is built; and

the first plurality of descriptors are at least partially based on image data.

10. The computer-readable medium of claim 9, wherein

each dimension stored as part of the first number of stored dimensions matches a dimension of the second number of dimensions used to build the first k-dimensional tree.

11. The computer-readable medium of claim 8, wherein the instructions are further configured to cause the computer to:

determine the query descriptor based on a query image.

12. The computer-readable medium of claim 11, wherein the instructions are further configured to cause the computer to:

identify one or more images that at least approximately match the query image based at least in part on searching the second k-dimensional tree.

13. The computer-readable medium of claim 8, wherein searching the second k-dimensional tree is performed because the matching descriptor was not located when searching the first k-dimensional tree.

14. A system for using k-dimensional trees for a search, the system comprising:

a processor; and

a first memory communicatively coupled with and readable by the processor having stored therein a series of processor-readable instructions which, when executed by the processor, cause the processor to;

cause a first plurality of descriptors to be stored, wherein each of the first plurality of descriptors stored is linked with a first number of stored dimensions;

search a first k-dimensional tree with a query descriptor for a matching descriptor from among the first plurality of descriptors linked with the first number of stored dimensions, wherein;

the first k-dimensional tree is built using the first plurality of descriptors wherein each of the first plurality of descriptors is linked with a second number of dimensions when the first k-dimensional tree is built; and

the second number of dimensions is a greater number of dimensions than the first number of stored dimensions;

cause a second plurality of descriptors to be stored, wherein each of the second plurality of descriptors stored is linked with the first number of stored dimensions; and

following searching the first k-dimensional tree, search a second k-dimensional tree using the query descriptor to find the matching descriptor from among the second plurality of descriptors linked with the first number of stored dimensions, wherein

the second k-dimensional tree is built using the second plurality of descriptors wherein each of the second plurality of descriptors is linked with the second number of dimensions when the second k-dimensional tree is built.

15. The system for using k-dimensional trees for the search of claim 14, wherein the series of processor-readable instructions is further configured to cause the processor to:

build the first k-dimensional tree using the first plurality of descriptors, wherein;

each of the first plurality of descriptors is linked with the second number of dimensions when the first k-dimensional tree is built; and

the first plurality of descriptors are at least partially based on image data.

16. The system for using k-dimensional trees for the search of claim 15, wherein

each dimension stored as part of the first number of stored dimensions matches a dimension of the second number of dimensions used to build the first k-dimensional tree.

17. The system for using k-dimensional trees for the search of claim 15, wherein the processor and the memory are part of a computer server system.

18. The system for using k-dimensional trees for the search of claim 15, wherein the processor and the memory are part of a mobile device.

19. The system for using k-dimensional trees for the search of claim 15, wherein the system further comprises an interface configured to receive an indication to perform an image search.

20. The system for using k-dimensional trees for the search of claim 19, wherein the indication comprises the query descriptor.

21. The system for using k-dimensional trees for the search of claim 19, wherein the indication comprises a query image.

22. The system for using k-dimensional trees for the search of claim 21, wherein the series of processor-readable instructions is further configured to cause the processor to:

determine the query descriptor based on a query image captured using a mobile device.

23. The system for using k-dimensional trees for the search of claim 22, wherein the series of processor-readable instructions is further configured to cause the processor to:

identify an image that at least approximately matches the query image based at least in part on searching the second k-dimensional tree.

24. The system for using k-dimensional trees for the search of claim 14, wherein searching the second k-dimensional tree is performed because the matching descriptor was not located when searching the k-dimensional tree.

25. An apparatus for using k-dimensional trees for a search, the apparatus comprising:

means for storing a first plurality of descriptors, wherein each of the first plurality of descriptors stored is linked with a first number of stored dimensions and the means for storing the first plurality of descriptors comprises a non-transitory computer-readable storage medium;

means for searching a first k-dimensional tree with a query descriptor for a matching descriptor from among the first plurality of descriptors linked with the first number of stored dimensions, wherein;

the first k-dimensional tree is built using the first plurality of descriptors wherein each of the first plurality of descriptors is linked with a second number of dimensions when the first k-dimensional tree is built;

the second number of dimensions is a greater number of dimensions than the first number of stored dimensions, and

the means for searching the first k-dimensional tree comprises a processor,

means for storing a second plurality of descriptors, wherein each of the second plurality of descriptors stored is linked with the first number of stored dimensions; and

means for searching a second k-dimensional tree using the query descriptor to find the matching descriptor from among the second plurality of descriptors linked with the first number of stored dimensions, such searching occurring after searching the first k-dimensional tree wherein

the second k-dimensional tree is built using the second plurality of descriptors wherein each of the second plurality of descriptors is linked with the second number of dimensions when the second k-dimensional tree is built.

26. The apparatus for using k-dimensional trees for the search of claim 25, further comprising:

means for building the first k-dimensional tree using the first plurality of descriptors, wherein;

each of the first plurality of descriptors is linked with the second number of dimensions when the first k-dimensional tree is built; and

the first plurality of descriptors are at least partially based on image data.

27. The apparatus for using k-dimensional trees for the search of claim 26, wherein:

each dimension stored as part of the first number of stored dimensions matches a dimension of the second number of dimensions used to build the first k-dimensional tree.

28. The apparatus for using k-dimensional trees for the search of claim 25, further comprising:

means for determining the query descriptor based on a query image.

29. The apparatus for using k-dimensional trees for the search of claim 28, further comprising:

means for identifying one or more images that at least approximately match the query image based at least in part on searching the second k-dimensional tree.

30. The apparatus for using k-dimensional trees for the search of claim 25, wherein the means for searching the second k-dimensional tree is used because the matching descriptor was not located when searching the first k-dimensional tree.

31. A system for using k-dimensional trees for a search, the system comprising:

a mobile device that comprises an image capture device, the mobile device configured to;

capture a query image;

create a query descriptor using the query image; and

transmit the query descriptor to a computer system; and

the computer system comprising a computer-readable medium comprising instructions configured to cause a computer to;

receive the query descriptor from the mobile device;

cause a first plurality of descriptors to be stored, wherein each of the first plurality of descriptors stored is linked with a first number of stored dimensions;

search a first k-dimensional tree with the query descriptor to find a matching descriptor from among the plurality of descriptors linked with the first number of stored dimensions, wherein;

the first k-dimensional tree is built using the plurality of descriptors wherein each of the plurality of descriptors is linked with a second number of dimensions when the first k-dimensional tree is built; and

the second number of dimensions is a greater number of dimensions than the first number of stored dimensions;

cause a second plurality of descriptors to be stored, wherein each of the second plurality of descriptors stored is linked with the first number of stored dimensions; and

following searching the first k-dimensional tree, search a second k-dimensional tree using the query descriptor to find the matching descriptor from among the second plurality of descriptors linked with the first number of stored dimensions, wherein

the second k-dimensional tree is built using the second plurality of descriptors wherein each of the second plurality of descriptors is linked with the second number of dimensions when the second k-dimensional tree is built.