System and Method for Compact Descriptor for Visual Search

• US 20130016908A1
• Filed: 12/29/2011
• Published: 01/17/2013
• Est. Priority Date: 07/11/2011
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Li, Zhu, Xin, Xin, Katsaggelos, Aggalos K.
• Granted Patent: US 8,755,605 B2
• Time in Patent Office: Days
• US Class Current: 382/191
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: G06K 7/1447 extracting optical codes from image or text carrying said optical code
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods

Abstract

A method and an apparatus for processing an image generates, using a linear embedding operator, a second set of feature points from a first set of feature points of the image, so that a pair-wise nearest neighbor (NN) topological relationship among the first set of feature points is preserved in the second set of feature points. The linear embedding operator is determined by an affinity model comprising a first affinity parameter, a second affinity parameter, and an affinity matrix, wherein a sparsity of the affinity matrix is controlled by the first affinity parameter and the second affinity parameter.

Claims

1. A method for processing an image, the method comprising:

generating, using a linear embedding operator, a second set of feature points from a first set of feature points of the image, wherein a pair-wise nearest neighbor (NN) topological relationship among the first set of feature points is preserved in the second set of feature points, a feature point is a point represented by a group of numbers.

2. The method of claim 1, wherein feature points in the first set of feature points are of a first dimension represented by a first quantity of numbers and feature points in the second set of feature points are of a second dimension smaller than the first dimension represented by a second quantity of numbers.

3. The method of claim 2, wherein a feature point in the second set of feature points has eight dimensions and a number in each dimension represented by six bits.

4. The method of claim 1, wherein the second set of feature points is used for visual search to identify the image from an image repository.

5. The method of claim 1, wherein the first set of feature points and the second set of feature points have a same number of feature points.

6. The method of claim 1, wherein the first set of feature points is a scale-invariant feature transform (SIFT) feature points of the image or a speeded up robust features (SURF) feature points of the image.

7. The method of claim 1, wherein the linear embedding operator is determined by an affinity model comprising a first affinity parameter d_max, a second affinity parameter a, and an affinity matrix W=(w_j,k) of size n*n, wherein a sparsity of the affinity matrix W=(w_j,k) is controlled by the first affinity parameter and the second affinity parameter, and n is a number of feature points in the first set of feature points.

8. The method of claim 7, wherein the linear embedded operator is a solution A to an objective equation

9. The method of claim 7, wherein the linear embedding operator is a matrix A computed by A=eigenvalue(L), wherein the matrix L=S−

W, S is a diagonal matrix with entry

10. The method of claim 7, wherein the affinity matrix is determined by the first affinity parameter d_max and the second affinity parameter a as

11. The method of claim 7, wherein the first affinity parameter d_max is a first zero gradient of sorted pair-wise distance function for a sample feature point repository comprising a plurality of feature points.

12. The method of claim 7, wherein the second affinity parameter a is chosen so that the affinity matrix W=(w_j,k) is sparse.

13. The method of claim 12, wherein the second affinity parameter a value is obtained with equation e⁻

a*d^max2=0.25.

14. The method of claim 1, wherein a feature point F_j in R^nj of the second set of feature points has a first precision for a first dimension and a second precision for a second dimension.

15. The method of claim 14, wherein the first precision for the first dimension with a higher variance for the feature point F_j is more than the second precision for the second dimension with a lower variance for the feature point F_j.

16. An apparatus for processing an image, the apparatus comprising:

a receiver configured to receive a first set of feature points of the image; and

a linear embedding unit configured to generate, using a linear embedding operator, a second set of feature points from the first set of feature points, wherein a pair-wise nearest neighbor (NN) topological relationship among the first set of feature points is preserved in the second set of feature points, a feature point is a point represented by a group of numbers.

17. The apparatus of claim 16, further comprising:

an affinity unit configured to generate an affinity model used to determine the linear embedding operator, wherein the affinity model comprises a first affinity parameter d_max, a second affinity parameter a, and an affinity matrix W=(w_j,k) of size n*n, n is a number of feature points in the first set of feature points, wherein a sparsity of the affinity matrix W=(w_j,k) is controlled by the first affinity parameter and the second affinity parameter.

18. The apparatus of claim 17, wherein the affinity matrix is determined by the first affinity parameter d_max and the second affinity parameter a as

19. The apparatus of claim 17, wherein the apparatus is located in a user equipment or in a base station.

20. An apparatus for processing an image, the apparatus comprising:

an image repository wherein an image in the image repository is represented by a set of feature points;

a receiver configured to receive a set of compressed feature points of a first image; and

a searching unit configured to match the feature points of images stored in the repository to the set of received compressed feature points of the first image; and

wherein the compressed feature points are generated by a linear embedding operator determined by an affinity model comprising a first affinity parameter, a second affinity parameter, and an affinity matrix, wherein a sparsity of the affinity matrix is controlled by the first affinity parameter and the second affinity parameter.