Feature conversion device, similar information search apparatus provided therewith, coding parameter generation method, and computer program

• US 8,630,482 B2
• Filed: 02/27/2012
• Issued: 01/14/2014
• Est. Priority Date: 02/28/2011
• Status: Active Grant

• Current Assignee: Denso IT Laboratory, Inc. (DENSO Corporation)
• Original Assignee: Denso IT Laboratory, Inc. (DENSO Corporation)
• Inventors: Yoshida, Yuichi, Ambai, Mitsuru
• Primary Examiner(s): Rahmjoo, Mike
• Application Number:
  US13/405,716
• Publication Number:
  US 20120219212A1
• Time in Patent Office: 687 Days
• Field of Search: 382/159, 382/156, 382/224, 382/227, 382/187, 382/228
• US Class Current: 382/159
• CPC Class Codes: G06F 16/316 Indexing structures

Abstract

A bit code converter transforms a learning feature vector using a transformation matrix updated by a transformation matrix update unit, and converts the transformed learning feature vector into a bit code. When the transformation matrix update unit substitutes a substitution candidate for an element of the transformation matrix, a cost function calculator fixes the substitution candidate that minimizes a cost function as the element. The transformation matrix update unit selects the element while sequentially changing the elements, and the cost function calculator fixes the selected element every time the transformation matrix update unit selects the element, thereby finally fixing the optimum transformation matrix. A substitution candidate specifying unit specifies the substitution candidate such that a speed of transformation processing that the bit code converter performs using the transformation matrix using the transformation matrix is enhanced based on a constraint condition stored in a constraint condition storage unit.

Claims

1. A feature conversion device comprising:

a learning pair selector that inputs a plurality of learning feature vectors thereto and selects a plurality of pairs of learning feature vectors from the learning feature vectors;

a bit code converter that transforms the learning feature vector using a transformation matrix and converts the transformed learning feature vector into a bit code;

a cost function calculator that calculates a cost function indicating a sum of differences between a distance between the learning feature vectors input to the learning pair selector and a distance between the bit codes into which the transformed learning feature vectors are converted by the bit code converter with respect to all the pairs of learning feature vectors; and

a transformation matrix update unit that selects an element of the transformation matrix used in the bit code converter and substitutes a substitution candidate for the selected element to update the transformation matrix,

wherein the bit code converter transforms the learning feature vector using the transformation matrix updated by the transformation matrix update unit and converts the transformed learning feature vector into a bit code,

the cost function calculator fixes the element by selecting one element from the substitution candidate and the original element based on the cost function when the transformation matrix update unit substitutes the substitution candidate for the element of the transformation matrix,

the transformation matrix update unit selects the element while sequentially changing the elements and the cost function calculator fixes the selected element every time the transformation matrix update unit selects the element, thereby finally fixing the optimum transformation matrix, and

the substitution candidate is specified such that a speed of transformation processing that the bit code converter performs using the transformation matrix is enhanced.

2. The feature conversion device according to claim 1, wherein the cost function calculator calculates an amount of change of the cost function when each of the substitution candidates is substituted for the element, fixes an adoption probability according to the amount of change, and selects one element from the substitution candidate and the original element according to the adoption probability.

3. The feature conversion device according to claim 1, wherein the distance between the learning feature vectors input to the learning pair selector with respect to the pair of learning feature vectors is a distance based on one of an L1 norm, an L2 norm, and an intervector angle.

4. The feature conversion device according to claim 1, wherein the distance between the bit codes converted by the bit code converter with respect to the pair of learning feature vectors is a distance based on the Hamming distance.

5. The feature conversion device according to claim 1, wherein the element of the transformation matrix is restricted to an integer, and the substitution candidate is restricted to an integer.

6. The feature conversion device according to claim 5, wherein the element of the transformation matrix is restricted to one of −

1, 0, and 1, and the substitution candidate is restricted to one of −

1, 0, and 1.

7. The feature conversion device according to claim 5, wherein the element of the transformation matrix is restricted to a power-of-two number, and the substitution candidate is restricted to a power-of-two number.

8. The feature conversion device according to claim 1, wherein the number of non-zero elements of the transformation matrix is restricted to a predetermined range, and the substitution candidate is specified such that the number of non-zero elements of the transformation matrix is maintained within the predetermined range.

9. The feature conversion device according to claim 1, wherein the learning pair selector selects an arbitrary pair of learning feature vectors from the plurality of input learning feature vectors.

10. The feature conversion device according to claim 1, wherein the learning pair selector selects a pair of learning feature vectors from the plurality of input learning feature vectors based on the distance between the learning feature vectors.

11. The feature conversion device according to claim 10, wherein the learning pair selector selects a pair of learning feature vectors from the plurality of input learning feature vectors such that the number of sets of a pair of learning feature vectors having the distance lower than a predetermined distance and the number of sets of a pair of learning feature vectors having the distance not lower than the predetermined distance become a predetermined ratio.

12. The feature conversion device according to claim 10, wherein the learning pair selector selects a pair of learning feature vectors from the plurality of input learning feature vectors such that a frequency of the distance becomes a uniform distribution or a particular distribution.

13. The feature conversion device according to claim 10, wherein the learning pair selector selects a pair of learning feature vectors from the plurality of input learning feature vectors such that the number of sets of a pair of learning feature vectors having the farthest distance relationship and the number of sets of a pair of learning feature vectors having the closest distance relationship become a predetermined ratio.

14. The feature conversion device according to claim 1, the cost function calculator uses a result of the cost function, which is calculated using the transformation matrix before the transformation matrix update unit substitutes the substitution candidate for the element of the transformation matrix, to calculate the cost function of the transformation matrix after the transformation matrix update unit substitutes the substitution candidate for the element of the transformation matrix.

15. A similar information search apparatus comprising:

the feature conversion device according to claim 1, and a similar vector search unit,

wherein the bit code converter converts the plurality of learning feature vectors into the plurality of bit codes using the fixed optimum transformation matrix,

the bit code converter converts an input feature vector into the bit code using the fixed optimum transformation matrix when the input feature vector is provided, and

the similar vector search unit includes;

a bit code retaining unit that retains the plurality of bit codes into which the plurality of learning feature vectors are converted by the bit code converter; and

a nearest neighbor search unit that inputs the bit code into which the feature vector is converted by the input bit code converter and searches a bit code similar to the bit code into which the feature vector is converted, the bit code is searched from the plurality of bit codes retained by the bit code retaining unit by a nearest neighbor search.

16. A coding parameter generating method for outputting a transformation matrix as a coding parameter used to convert a feature vector into a bit code, the coding parameter generating method comprising:

a first step of selecting a plurality of pairs of learning feature vectors from a plurality of learning feature vectors;

a second step of initializing the transformation matrix under a constraint condition;

a third step of calculating a cost function indicating a sum of differences between a distance between the learning feature vectors and a distance between the bit codes into which the learning feature vectors are converted using the initialized transformation matrix with respect to the plurality of pairs of learning feature vectors;

a fourth step of selecting an element set to a substitution target from elements of the transformation matrix;

a fifth step of substituting a particular substitution candidate for the element selected in the fourth step;

a sixth step of calculating the cost function using the transformation matrix in which the substitution candidate is substituted for the selected element in the fifth step;

a seventh step of determining whether all the substitution candidates are substituted for the selected element, and returning to the fifth step when all the substitution candidates are not substituted for the selected element;

an eighth step of tentatively fixing an optimum transformation matrix by fixing the substitution candidate having the smallest calculated cost function in the substitution candidates as the selected element when all the substitution candidates are substituted for the selected element in the seventh step;

a ninth step of determining whether the optimum transformation matrix tentatively fixed in the eighth step converges, and returning to the fourth step when the optimum transformation matrix does not converge; and

a tenth step of outputting the tentatively-fixed optimum transformation matrix as a finally-fixed optimum transformation matrix when the optimum transformation matrix tentatively fixed in the eighth step converges,

wherein one or more of the steps are performed using a processor.

17. A non-transitory computer-readable medium storing a program to perform the coding parameter generation method according to claim 16.