Information conversion device, computer-readable recording medium, and information conversion method

An information conversion device includes a memory and a processor coupled to the memory. The processor executes a process including generating a conversion rule for converting a feature quantity vector into a binary string that is longer than a predetermined bit length. The process includes converting each of the feature quantity vectors into a binary string by using the conversion rule generated at the generating. The process includes calculating importance levels of the respective bits in the binary strings based on the distance-based relations among the feature quantity vectors. The process includes correcting the conversion rule into one that converts each of the feature quantity vectors into a binary string having the predetermined bit length based on the calculated importance levels. The process includes changing the feature quantity vectors into a binary string having the predetermined bit length by using the conversion rule corrected at the correcting.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2012-075195, filed on Mar. 28, 2012, the entire contents of which are incorporated herein by reference.

FIELD

The embodiments discussed herein are related to an information conversion device, a computer-readable recording medium, and an information conversion method.

BACKGROUND

Conventionally, there are known techniques with which pieces of data similar or relevant to inputted query data to the extent that the similarity or relevance thereof satisfy a predetermined condition are searched from multiple pieces of data registered in a database. As one example of such techniques, a technique called neighborhood search is known with which: the levels of similarity or relevance between pieces of data are represented as distances in a multidimensional feature quantity vector space; and pieces of data having distances from query data that do not exceed a threshold, or a predetermined number of pieces of data that are the closest to the query data are selected.

FIG. 8is a diagram for illustrating a conventional neighborhood search. For example, an information processing apparatus that executes neighborhood search stores, as indicated with white circles inFIG. 8, the feature quantity vectors of pieces of data to be searched. Then, upon acquiring query data indicated by (A) inFIG. 8, the information processing apparatus calculates the distance between the query data and each of the feature quantity vectors, and sets, as neighboring data of the query data, pieces of data that fall within a predetermined range in terms of distance from the query data as indicated by (B) inFIG. 8.

Here, in a case where a database has a large number of pieces of data registered therein, calculation of the distances between all of the pieces of data and the query data leads to an increase in calculation cost involved in neighborhood search. Therefore, there are other known techniques each of which aims at reduction in calculation cost involved in neighborhood search in such a manner as to narrow down data to be searched by creating indices for the feature quantity vector space or by using indices that utilize distances from particular feature quantity vectors. However, these techniques are not capable of reducing the calculation cost in a case where each feature quantity vector has a large number of dimensions.

Hence, there are other known techniques with which, in order to reduce a calculation cost for neighborhood search, search processing is speeded up by relaxing the level of strictness on a search result and acquiring a set of similar data approximate to query data. For example, matching search between binary strings and calculation of hamming distances enable processing to be performed faster than calculation of distances between vectors. Hence, there are other known techniques with which reduction in calculation cost is enabled in such a manner that: feature quantity vectors are converted into binary strings with distance-based relations between the feature quantity vectors being maintained; and matching search or calculation of hamming distances with respect to a binary string obtained through conversion of query data is performed.

One example of methods for converting such feature quantity vectors into binary strings is described below.FIG. 9is a diagram for illustrating search processing using binarization. Note that a method for converting feature quantity vectors, indicated by white circles inFIG. 9, into 2-digit binary strings is described by the example illustrated inFIG. 9.

For example, an information processing apparatus stores feature quantity vectors indicated with white circles inFIG. 9. Here, the information processing apparatus applies a projective function thereto, thereby setting the first digits of binary strings to “1” for feature quantity vectors included in the area above a dotted line inFIG. 9, and to “0” for feature quantity vectors included in the area below the dotted line. Further, the information processing apparatus sets the second digits of binary strings to “1” for feature quantity vectors included in the area to the right of a solid line inFIG. 9, and to “0” for feature quantity vectors included in the area to the left of the solid line.

Here, in order for maintaining the accuracy of search in converting the feature quantity vectors into binary strings, it is important to convert feature quantity vectors into binary strings while maintaining distance-based relations among the original feature quantity vectors. However, the above described technique for converting feature quantity vectors into binary strings uses threshold processing to convert feature quantity vectors, which are continuous values, into non-continuous binary strings. Therefore, the technique involves a problem that it is difficult to optimize conversion functions that, while maintaining distance-based relations among the feature quantity vectors, convert feature quantity vectors into binary strings.

SUMMARY

According to an aspect of an embodiment, an information conversion device includes a memory and a processor coupled to the memory. The processor executes a process including generating a conversion rule for converting a feature quantity vector into a binary string that is longer than a predetermined bit length. The process includes converting each of the feature quantity vectors into a binary string by using the conversion rule generated at the generating. The process includes calculating importance levels of the respective bits in the binary strings based on a distance-based relations among the feature quantity vectors. The process includes correcting the conversion rule into one that converts each of the feature quantity vectors into a binary string having the predetermined bit length based on the calculated importance levels. The process includes changing the feature quantity vectors into a binary string having the predetermined bit length by using the conversion rule corrected at the correcting.

DESCRIPTION OF EMBODIMENTS

[a] First Embodiment

In a first embodiment described below, one example of the functional configuration of a search system including an information conversion apparatus is described usingFIG. 1.FIG. 1is a diagram for illustrating the functional configuration of a search system according to the first embodiment. As illustrated inFIG. 1, a search system1includes a client apparatus2, an information conversion apparatus10, and an information search apparatus20.

Further, the information conversion apparatus10includes a learned data storage unit11, a conversion rule generation unit12, an importance level calculation unit13, a conversion rule determination unit14. Further, the information search apparatus20includes a search-target database storage unit21, a binary conversion unit23, a binary database storage unit22, and a search processing unit24.

The search system1illustrated inFIG. 1searches neighboring data of the query data from the search-target database storage unit21upon receiving query data from the client apparatus2. Additionally, the search system is a system that notifies the client apparatus2whether data similar to the query data has been registered in the neighborhood of the query data. Specifically, in the search system1, the information search apparatus20converts data to be searched into binary strings by the application of a conversion rule generated by the information conversion apparatus10, and searches neighboring data of the query data.

Here, for example, data that the search system1searches is image data, audio data, or the like, and is biometric data for biometric authentication using fingerprint patterns or vein patterns. That is, the search system1is a system that, when biometric data of a user that has been inputted to the client apparatus2is received thereby as query data, determines whether the biometric data of the user has been registered.

Note that, while feature quantities of various kinds for image and audio data have been proposed, the search system1does not depend on the feature quantities of specific kinds, and is therefore enabled to use feature quantities of any kinds. For example, a SIFT feature quantity, a SURF feature quantity or the like, which is generally used as a feature quantity for an image, may be used as a feature quantity for an image. Feature quantities of these kinds are known as feature quantities that are robust against hiding and variation as a result of using local information in an image as feature quantity vectors. Feature quantity vectors in any form that indicate such feature quantities may be used.

FIG. 2is a diagram for illustrating one example of biometric authentication. Note that the example illustrated inFIG. 2represents processing in ID-less 1:N authentication, where information such as an ID (Identification) of a user is not inputted, and no narrowing down of biometric data by using the ID of the user is involved. As illustrated inFIG. 2, the search system1stores multiple pieces of registered biometric data that have been registered by multiple users.

Then, upon receiving a piece of biometric data as query data from the client apparatus2, the search system1extracts a feature quantity vector indicating the inputted piece of biometric data, and then searches pieces of the registered biometric data that have feature quantity vectors similar to the extracted feature quantity vector. That is, the search system1determines whether a piece of registered biometric data of a user who has inputted the query data has been registered.

Further, the search system1generates a conversion rule for converting a feature quantity vector into a binary string having a predetermined bit length, and then converts the feature quantity vectors of the registered pieces of biometric data into binary strings by applying the generated conversion rule. Additionally, the search system1converts, into a binary string having the predetermined bit length, the feature quantity vector corresponding to the piece of biometric data that has been inputted as the query data. Then, the search system1calculates the hamming distances therefrom of the binary strings obtained by converting the feature quantity vectors of the registered pieces of biometric data. Then, the search system1extracts, as candidates for those to be searched, the registered pieces of biometric data that have the hamming distances not exceeding a predetermined threshold. Thereafter, the search system1executes strict matching processing between the searched registered pieces of biometric data and the piece of biometric data inputted as the query data, and outputs the execution result to the client apparatus2.

Thus, the search system1narrows down data to be searched, by converting, into binary strings in a predetermined form, the feature quantity vectors indicating the features of the registered pieces of biometric data to be searched, and calculating the hamming distances thereof from the binary string obtained by converting the feature quantity vector of the query data. Then, the search system1performs matching between data obtained by narrowing down the original data and the query data, thereby performing matching in biometric authentication.

Note that, in a case where the inputted biometric data and the registered biometric data are in the form of images, a feature quantity vector is obtained by vectorizing, for example, values representing the direction, length and slope of a ridge in a specific region within each image, and the densities and coordinates of characteristic points, such as the terminals and branching points, of the ridge. On the other hand, in a case where the inputted biometric data and the registered biometric data are in the form of voice, a feature quantity vector is obtained by vectorizing values representing the distributions, the levels of strength and the peak values of frequency components.

Described below are processing to be executed by the information conversion apparatus10and processing to be executed by the information search apparatus20. Firstly, the processing to be executed by the information conversion apparatus10is described. The information conversion apparatus10uses learned data stored in the learned data storage unit11to generate a conversion rule that converts a feature quantity vector into a binary string having a predetermined bit length.

Specifically, the learned data storage unit11stores, as learned data, a plurality of feature quantity vectors with respect to each user. Here, feature quantity vectors stored in the learned data storage unit11are those included among feature quantity vectors stored in the search-target database storage unit21which is described below. That is, the learned data storage unit11stores a part of those included among feature quantity vectors stored in the search-target database storage unit21.

Further, the learned data storage unit11stores among feature quantity vectors stored in the search-target database storage unit21, feature quantity vectors of biometric data that have been registered by a plurality of users. Note that, in the following description, a plurality of feature quantity vectors registered by the same user is referred to as feature quantity vectors belonging to the same class. That is, the learned data storage unit11stores feature quantity vectors belonging to one class and feature quantity vectors belonging to other classes.

The conversion rule generation unit12generates a conversion rule for converting a feature quantity vector into a binary data having a bit length longer than the predetermined bit length. For example, in a case where the information search apparatus20is to execute search processing using “M”-bit binary strings, the conversion rule generation unit12generates “N” conversion functions for converting feature quantity vectors into 1-bit binary strings. Here, “M” and “N” are integers that satisfy M<N. Then, the conversion rule generation unit12transmits the generated “N” conversion functions to the importance level calculation unit13.

Further, the conversion rule generation unit12receives M conversion functions. Then, the conversion rule generation unit12newly generates (N−M) conversion functions, and transmits the newly generated (N−M) conversion functions to the importance level calculation unit13.

Here, conversion functions to be generated by the conversion rule generation unit12are described. For example, the information search apparatus20generates N sets of N-dimensional parameter vectors wiand offset parameters bi. Then, the conversion rule generation unit12generates N conversion functions each defined by formula (1) given below.

Note that, while uiin boldface type in formula (1) denotes the i-th bit in a binary string u obtained by the conversion, x in boldface type therein denotes a feature quantity vector. In addition, thr( ) in formula (1) denotes a threshold function, which is a function that converts a value in the parentheses to “1” when the value is more than or equal to 0, or to “0” when the value is a negative value.
ui=thr(wi·x+bi)  (1)

That is, the information search apparatus20generates N formulae, each of which is formula (1), where i takes values of “1” to “N,” and then transmits thus generated N conversion functions to the importance level calculation unit13. Note that, by using random numbers or the like, the conversion rule generation unit12generates the parameter vectors wiand the offset parameters biso that values of the parameter vectors wiand the offset parameters bimay be different by corresponding bit (found by the value of the suffix i).

Upon receiving the N conversion functions from the conversion rule generation unit12, the importance level calculation unit13acquires the feature quantity vectors stored in the learned data storage unit11, and generates an N-bit binary string u through calculation using formula (1) with respect to each feature quantity vector. For example, the importance level calculation unit13calculates the value of the first bit u1of the binary string u through calculation using formula (1) with respect to one feature quantity vector by using the parameter vector w1and the offset parameter b1. Then, the importance level calculation unit13calculates the values of the other bits u2to uNof the binary string u by using the parameter vectors w2to wNand the offset parameters b2and bN.

Then, the importance level calculation unit13calculates importance levels of the respective bits u1to uNof the binary string u so that the importance levels may accord with distance-based relations among the feature quantity vectors stored in the learned data storage unit11. That is, the information conversion apparatus10calculates the importance levels of the respective bits u1to uNof the binary string u to thereby evaluate the importance levels of the N conversion functions that convert the feature quantity vectors into the respective bits u1to uN.

Then, any method that appropriately maintains distance-based relations found between the feature quantity vectors before the conversion may be used as a method used by the importance level calculation unit13to calculate the importance levels of the respective bits u1to uNof the binary string u. For example, the importance level calculation unit13may calculate the importance levels of the respective bits u1to uNby using a technique called RELIEF presented in “A Practical Approach to Feature Selection,”Proceedings of the9th International Workshop on Machine Learning, pp. 249-256, 1992, or a technique called Simba presented in “Margin Based Feature Selection—Theory and Algorithms,”Proceedings of the21st International Conference on Machine Learning(ICML '04), pp. 43-50, 2004.

As one example of processing that the importance level calculation unit13executes to calculate the importance levels of the respective bits u1to uNof the binary string u, processing to calculate the importance levels of the respective bits u1to uNof the binary string u in a manner depending on the class to which the feature quantity vectors belong is described below. First of all, the importance level calculation unit13converts the feature quantity vectors stored in the learned data storage unit11into N-bit binary strings by using conversion functions received from the conversion rule generation unit12.

Then, the importance level calculation unit13takes one binary string as a sample of the binary string u, and calculates the weighted hamming distances of the other binary strings and the binary string u by using formula (2) given below. Here, siin formula (2) denotes the importance level of ui, and is set to “1” for each of the bits u1to uNin the initial state. In addition, v in formula (2) denotes a binary string taken to be compared with the binary string u.
∥u−v∥s=√{square root over (Σisi2(ui−vi)2)}  (2)

Further, the importance level calculation unit13updates the importance level of uiof the binary string u by using formula (3) given below. Here, nearhit(u)idenotes the i-th bit value of a binary string, among binary strings obtained by converting feature quantity vectors belonging to the same class as the feature quantity vectors converted into the binary data u belong to, that has a weighted hamming distance that is the closest to the weight hamming distance of the binary string u.

Here, feature quantity vectors belonging to the same class are of biometric data of the same user. Accordingly, the importance level calculation unit13increases the importance levels of the conversion functions in a case where a relatively short hamming distance between binary strings obtained by converting feature quantity vectors belonging to the same class is given with formulae (2) and (3). Here, feature quantity vectors belonging to different classes are of biometric data of different users. It is therefore preferable that conversion of feature quantity vectors belonging to different classes result in a relatively long hamming distance between binary strings obtained thereby. For this reason, the importance level calculation unit13lowers the importance levels of the conversion functions in a case where a relatively short hamming distance between binary strings obtained by converting feature quantity vectors belonging to different classes is given with formulae (2) and (3).

The importance level calculation unit13updates the importance levels s1to sNof the conversion functions of the respective bits a predetermined number of times. Then, the importance level calculation unit13notifies the conversion rule determination unit14of the updated importance levels s1to sNafter having updated the importance levels s1to sNthe predetermined number of times. Additionally, the importance level calculation unit13notifies the conversion rule determination unit14of conversion functions received from the conversion rule generation unit12.

The importance level calculation unit13thus updates the importance levels s1to sNin a manner depending on the distance-based relations between feature quantity vectors and classes to which feature quantity vectors belong, and therefore, is capable of generating a conversion rule that maintains distance-based relations found between feature quantity vectors before the conversion. Note that, even when the classes are not taken in consideration, the importance level calculation unit13is capable of generating an appropriate conversion rule because the importance level of a conversion function that maintains distance-based relations found between feature quantity vectors at conversion source is increased in updating the importance levels s1to sNin a manner depending on distance-based relations between feature quantity vectors before the conversion.

Corresponding to the updated importance levels calculated by the importance level calculation unit13, the conversion rule determination unit14corrects the conversion rule generated by the conversion rule generation unit12, so that feature quantity vectors may be converted into a binary string having the predetermined bit length. Specifically, the conversion rule determination unit14receives the importance levels s1to sNcalculated by the importance level calculation unit13. Upon reception, the conversion rule determination unit14compares the received importance levels s1to sN, and selects M bits by the order of having the higher importance level. Then, the conversion rule determination unit14identifies M conversion functions used for converting feature quantity vectors into the selected bits. That is, the conversion rule determination unit14identifies M conversion functions that have suitably binarized distance-based relations between feature quantity vectors.

Further, the conversion rule determination unit14determines whether the selection of the importance levels has been performed the predetermined number of times. Upon determining that the selection of the importance levels has not yet been performed the predetermined number of times, the conversion rule determination unit14notifies the conversion rule generation unit12of the M conversion functions identified thereby. On the other hand, upon determining that the selection of the importance levels has been performed the predetermined number of times, the conversion rule determination unit14transmits the M conversion functions identified thereby to the information search apparatus20.

Note that the conversion rule determination unit14may selects conversion functions by using an alternative method. For example, the conversion rule determination unit14selects bits having importance levels that exceed a predetermined threshold value, and identifies conversion functions used for converting feature quantity vectors into the selected bits. Then, until the number of the conversion functions identified thereby reaches M, the conversion rule determination unit14continues causing the conversion rule generation unit12and the importance level calculation unit13to generate conversion functions and calculate importance levels. Thereafter, the conversion rule determination unit14transmits the M conversion functions identified thereby to the information search apparatus20.

Next, the processing to be executed by the information search apparatus20is described. The search-target database storage unit21stores data to be searched, namely, feature quantity vectors of the registered biometric data. Specifically, the search-target database storage unit21stores the feature quantity vectors of the registered biometric data and data IDs which are identifiers for users who have registered the registered biometric data, while associating the feature quantity vectors with the data IDs. That is, the search-target database storage unit21stores the feature quantity vectors while classifying these vectors according to class to which these vectors belong.

Here, one example of information that the search-target database storage unit21stores is described usingFIG. 3.FIG. 3is a diagram for illustrating one example of information stored by the search-target database storage unit. For example, in the example illustrated inFIG. 3, the search-target database storage unit21stores a data ID “1” and feature quantity vectors “a,” “b,” and “c,” indicated in boldface type, in a manner associating these vectors with this data ID. Note that the search-target database storage unit21stores other feature quantity vectors associated with this data ID although such vectors are omitted fromFIG. 3.

Referring back toFIG. 1, the binary database storage unit22stores symbol strings in a manner associating these symbol strings with data IDs. Each of the symbol strings is a symbol string obtained by converting feature quantity vectors by using predetermined conversion functions, and contains a binary symbol and a wildcard symbol. One example of information that the binary database storage unit22stores is described usingFIG. 4.

FIG. 4is a diagram for illustrating one example of information that the binary database storage unit stores. For example, in the example illustrated inFIG. 4, the binary database storage unit22stores an M-bit binary string “01110100110 . . . ” while associating this binary string with the data ID “1.” Note that the binary database storage unit22stores other two or more symbol strings while associating these symbol strings with the data ID “1,” although such symbol strings are omitted fromFIG. 4. That is, the binary database storage unit22stores M-bit binary strings into which feature quantity vectors stored in the search-target database storage unit21have been converted by the below-described binary conversion unit23by use of conversion functions received from the information conversion apparatus10, while classifying these binary strings according to class to which these binary strings belong.

Referring back toFIG. 1, upon receiving the conversion functions from the conversion rule determination unit14of the information conversion apparatus10, the binary conversion unit23converts the feature quantity vectors stored in the search-target database storage unit21into M-bit binary strings by using the received conversion functions. Then, the binary conversion unit23stores the binary strings thus obtained by the conversion in the binary database storage unit22while associating these binary strings with data IDs associated with feature quantity vectors that have been converted into the respective binary strings.

The search processing unit24, upon receiving query data from the client apparatus2, extracts feature quantity vectors indicating feature quantities corresponding to the received query data, and converts the extracted feature quantity vectors by using predetermined conversion functions. Then, search processing unit24searches, out of the binary strings stored in the binary database storage unit22, binary strings that have hamming distances less than or equal to a predetermined value, namely, binary strings into which feature quantity vectors to be selected as candidate of neighboring data of the query data have been converted.

Thereafter, the search processing unit24extracts, from the search-target database storage unit21, the feature quantity vectors having been converted into thus searched binary strings. Then, the search processing unit24executes processing as below when, among the feature quantity vectors thus extracted thereby, feature quantity vectors identical to the feature quantity vectors extracted from the query data are found or a feature quantity vector having a Euclidean distance therefrom less than or equal to a predetermined threshold is found. That is, the search processing unit24transmits to the client apparatus2the notification that data from the registered biometric data is identical to the query data.

On the other hand, the search processing unit24executes processing as below when, among the feature quantity vectors thus extracted thereby, feature quantity vectors identical to the feature quantity vectors extracted from the query data are not found or a feature quantity vector having a Euclidean distance therefrom less than or equal to a predetermined threshold is not found. That is, the search processing unit24transmits to the client apparatus2the notification that no data from the registered biometric data is identical to the query data. As a result, the client apparatus2is enabled to perform biometric authentication of a user who have inputted the query data.

The conversion rule generation unit12, the importance level calculation unit13, the conversion rule determination unit14, the binary conversion unit23, and the search processing unit24are, for example, electronic circuits. An integrated circuit such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array), a CPU (Central Processing Unit), or an MPU (Micro Processing Unit) is applied here as an example of such an electronic circuit.

Additionally, the learned data storage unit11, the search-target database storage unit21, the binary database storage unit22are storage devices such as a semiconductor memory device such as a RAM (Random Access Memory) or a flash memory, a hard disk, or an optical disc.

Next, processing to be executed by the information conversion apparatus10to generate a conversion rule is described usingFIG. 5.FIG. 5is a flowchart for illustrating the flow of the processing for generating conversion rules. First of all, the information conversion apparatus10accepts input of a termination condition (step S101). For example, the information conversion apparatus10acquires, as the termination condition, a setting for the number of times that the processing is to be repeated.

Subsequently, the information conversion apparatus10generates conversion functions corresponding to N bits (step S102). Then, the information conversion apparatus10calculates the importance levels s1to sNof the respective bits (step S103). Subsequently, based on the importance levels s1to sNof the respective bits calculated in the processing in step S103, the information conversion apparatus10selects conversion functions corresponding to M bits from the conversion functions corresponding to N bits (step S104).

Subsequently, the information conversion apparatus10determines whether the termination condition accepted in step S101has been satisfied (step S105). Then, when the termination condition has not been satisfied (No in step S105), the information conversion apparatus10newly generates conversion functions corresponding to (N=M) bits (step S106). Then, the information conversion apparatus10executes the processing in step S103by using the conversion functions newly generated in step S106corresponding to (N−M) bits and the conversion functions selected in step S104.

On the other hand, when the termination condition has been satisfied (Yes in step S105), the information conversion apparatus10outputs the conversion functions selected in step S104to the information search apparatus (step S107), and finishes processing.

Next, the flow of processing to be executed by the importance level calculation unit13to calculate the importance levels of the each bit, namely, the importance levels of conversion functions, is described usingFIG. 6.FIG. 6is a flowchart for illustrating the flow of the processing for calculating the importance levels of conversion functions. Note that the processing inFIG. 6corresponds the processing in step S103illustrated inFIG. 5.

First of all, the importance level calculation unit13previously acquires, as data to be used for leaning, a portion of feature quantity vectors stored in the search-target database storage unit21and stores this portion in the learned data storage unit11(step S201). In this acquisition, the importance level calculation unit13acquires feature quantity vectors that belong to a plurality of classes.

Subsequently, the importance level calculation unit13initializes all of the importance levels s1to sNof the respective bits to “1” (step S202). Subsequently, upon acquiring the conversion functions corresponding to N bits, the importance level calculation unit13randomly selects one of the feature quantity vectors stored in the learned data storage unit11, as a piece of learned data (step S203). Then, the importance level calculation unit13performs calculation using formulae (1) and (2) with respect to the piece of learned data, thereby updating the respective importance levels s1to sNof the respective bits (step S204).

Subsequently, the importance level calculation unit13determines whether the number of times of repetition has satisfied the termination condition (step S205). Then, upon determining that the number of times of repetition has satisfied the termination condition (Yes in step S205), the importance level calculation unit13outputs the importance levels s1to sNto the conversion rule determination unit14(step S206), and finishes processing. On the other hand, upon determining that the number of times of repetition has not satisfied the termination condition (No in step S205), the importance level calculation unit13executes the processing in step S203again.

Effects of First Embodiment

As described above, the information conversion apparatus10generates a conversion rule for converting a feature quantity vector into a binary string having a bit length of N. Then, the information conversion apparatus10converts feature quantity vectors into binary strings by applying the generated conversion rule, and calculates the importance levels of the feature quantity vectors on the basis of distance-based relations found among the feature quantity vectors.

Subsequently, the information conversion apparatus10corrects the conversion rule so that the conversion rule may convert a feature quantity vector into a binary string having a bit length of M. Thereafter, using the conversion rule corrected by the information conversion apparatus10, the information search apparatus20converts feature quantity vectors into binary strings each having a bit length of M. As a result, the search system1is enabled to generate the most appropriate conversion functions with respect to each set of data to be searched.

Further, the information conversion apparatus10generates N conversion functions that convert a feature quantity vector into a 1-bit binary string, and converts a feature quantity vector into a 1-bit binary string by using these generated N conversion functions. Then, the information conversion apparatus10calculates the importance levels for the bit of the N-bit binary string, and selects M conversion functions from the generated N conversion functions based on thus calculated importance levels.

That is, the information conversion apparatus10generates conversion functions for converting a feature quantity vector into bits, the number of which is larger than the number of bits needed for the search processing. Then, the information conversion apparatus10selects, from thus generated conversion functions, only conversion functions that perform conversion through which distance-based relations between feature quantity vectors are maintained. As a result, the information conversion apparatus10is enabled to maintain distance-based relations between feature quantity vectors by using a smaller number of bits than in the conventional cases. Additionally, the information conversion apparatus10is enabled to generate binary strings that have a small number of bits per each with maintaining distance-based relations between feature quantity vectors. It is thereby made possible to speed up the search processing executed by the information search apparatus20.

Further, the information conversion apparatus10is enabled to generate a conversion rule that results in a smaller hamming distance between binary strings when the binary strings are those obtained by converting feature quantity vectors belonging to the same class. As a result, it is made possible to improve the precision of the search processing using hamming distances in the information search apparatus20.

Further, the information conversion apparatus10selects, from the generated N conversion functions, M conversion functions in descending order of the importance levels. As a result, the information conversion apparatus10is enabled to generate a conversion rule that more accurately converts feature quantity vectors into binary strings.

Further, the information conversion apparatus10repetitively executes the processing described below. That is, after selecting the M conversion functions, the information conversion apparatus10newly generates (N−M) conversion functions, then generates an N-bit binary string again by using the selected M conversion functions and these (N−M) conversion functions, and then calculates the importance levels of the respective bits of thus generated binary string. Then, the information conversion apparatus10newly selects the M conversion functions based on thus calculated importance levels.

As a result, the information conversion apparatus10is enabled to select, from a large number of conversion functions, conversion functions having higher importance levels than the other conversion functions. Therefore, the information conversion apparatus10is enabled to generate a more precise conversion rule.

Further, the information conversion apparatus10repetitively executes generation of new conversion functions and calculation of importance levels until M conversion functions, the importance levels of which exceed the predetermined threshold, are selected. Therefore, the information conversion apparatus10is enabled to select, from a large number of conversion functions, conversion functions having higher importance levels than the other conversion functions, and generate a more precise conversion rule.

Further, the information conversion apparatus10generates conversion functions by using s parameter vectors and offset parameters generated in a random manner, and therefore, is enabled to generate conversion functions that appropriately binarize a feature quantity vector space.

Further, the information conversion apparatus10calculates importance levels based on a difference between: the smallest of the hamming distances between pairs of binary strings where each of the pairs is obtained by converting feature quantity vectors belonging to the same class; and the smallest of the hamming distances between pairs of binary strings where each of the pairs is obtained by converting feature quantity vectors belonging to different classes.

For example, when a pair of binary strings obtained by converting feature quantity vectors from the same class by using formulae (2) and (3) gives a shorter hamming distance, the information conversion apparatus10increases the importance level of a corresponding conversion function. On the other hand, when a pair of binary strings into which feature quantity vectors belonging to different classes have been converted is obtained using formulae (2) and (3) gives a shorter hamming distance, the information conversion apparatus10lowers the importance level of a corresponding conversion function.

As a result, the information conversion apparatus10is enabled to, when feature quantity vectors are converted into binary strings, generate a conversion rule that reflects distance-based relations among the feature quantity vectors and classes to which the feature quantity vectors belong. Therefore, the information conversion apparatus10is enabled to provide a higher level of precision to the search without slowing down the processing speed of the search processing executed by the information search apparatus20.

Besides, the information search apparatus20uses a conversion rule, generated by the information conversion apparatus10, for converting feature quantity vectors to be searched into binary strings. Further, the information search apparatus20converts a feature quantity vector extracted from query data into a binary string. Then, the information search apparatus20searches feature quantity vectors located in the neighborhood of the query data, by using the hamming distances to the binary strings into which the feature quantity vectors to be searched have been converted from the binary string into which the feature quantity vector extracted from the query data has been converted.

Here, processing of calculating the hamming distances is more speedily executable than processing of calculating the Euclidian distances between feature quantity vectors. Therefore, the information search apparatus20is enabled to provide a higher processing speed to the search processing. Further, the information search apparatus20converts feature quantity vectors into binary strings by using M conversion functions selected from N conversion functions based on the importance levels thereof by the information conversion apparatus10. As a result, the information search apparatus20is enabled to execute the search processing at high speed without deteriorating the precision of the search.

[b] Second Embodiment

Although one embodiment according to the present invention is described above, embodiments other than the above described embodiment may be implemented in many different forms. Accordingly, another embodiment included in the present invention is described below as a second embodiment.

(1) Regarding Conversion Functions to be Selected

The information conversion apparatus10described above selects conversion functions that have converted feature quantity vectors into bits having high importance levels. However, embodiments are not limited to this, and, for example, the information conversion apparatus10may always select a conversion function for converting a feature quantity vector into a bit that clearly has a high importance level. For example, in a case where there is a conversion function known for being effective when feature quantity vectors to be searched fall within a particular type, the information conversion apparatus10may always include this conversion function in a conversion rule. Alternatively, the information conversion apparatus10may set, as the initial value of the importance level of a bit obtained by conversion using such an effective conversion function, a value higher than values set as the initial values of the other bits.

Further, in selection of conversion rules, the information conversion apparatus10may redundantly select a conversion function that performs conversion into a bit having a high importance level. When executing such processing, the information conversion apparatus10is enabled to generate a conversion rule that generates a binary string that emphasizes positional relations between feature quantity vectors. As a result, when the information search apparatus20performs neighborhood search on query data, a smaller number of feature quantity vectors are acquired as a search result. Therefore, the information conversion apparatus10is enabled to, when the information search apparatus20performs matching with the query data, reduce the computational complexity involved therein and provide a higher processing speed to the search processing.

Additionally, the information conversion apparatus10is configured to generate N conversion functions each of which converts a feature quantity vector into one bit and select M conversion functions from the N conversion functions based on the importance levels of the respective bits, thereby generating a conversion for converting a feature quantity vector into an M-bit binary string. However, embodiments are not limited to this.

For example, the information conversion apparatus10generates not only conversion functions each of which converts a feature quantity vector into one bit but also conversion functions each of which converts a feature quantity vector into a binary string of a plurality of digits. At this time, the information conversion apparatus10performs the generations so that, in converting a feature quantity vectors into a binary string by using all of these generated conversion functions, the feature quantity vector may be converted into a binary string having a bit length longer than the bit length of a binary string to be used for the search processing. Then, the information conversion apparatus10may select conversion functions from the generated a plurality of conversion functions based on the importance levels of the respective bits so that the number of bits of a binary string into which the selected conversion functions convert a feature quantity vector may correspond to a bit length to be used in the search processing.

For example, the information conversion apparatus10generates a plurality of conversion functions each configured to convert a feature quantity vector into a 1-bit binary string, a plurality of conversion functions each configured to convert a feature quantity vector into a 2-bit binary string, and a plurality of conversion functions each configured to convert a feature quantity vector into a 3-bit binary string. Then, in a case where the bit length of each binary string to be used for the search processing is 15 bits, the information conversion apparatus10may select conversion functions as follows. For example, the information conversion apparatus10may select one of the conversion functions each configured to convert a feature quantity vector into a 1-bit binary string, one of the conversion functions each configured to convert a feature quantity vector into a 2-bit binary string, and four of the conversion functions each configured to convert a feature quantity vector into a 3-bit binary string.

(2) Regarding Forms for Embodiments

The information conversion apparatus10described above is an apparatus independent from the information search apparatus20. However, embodiments are not limited to this, and, for example, the functions of the information conversion apparatus10may be included in the information search apparatus20. Alternatively, the information conversion apparatus10may include the function to be executed by the binary conversion unit23of the information search apparatus20, and may generate a conversion rule to be applied to feature quantity vectors stored in an information search apparatus currently in operation, and execute processing of generating binary strings by the application of the generated conversion rule.

(3) Regarding Mathematical Formulae

The mathematical formulae used by the information conversion apparatus10to calculate importance levels are simply examples, and the information conversion apparatus10may use mathematical formulae of any forms. That is, any mathematical formulae may be used as long as these formulae make it possible to increase the importance levels of conversion functions that are capable of reflecting, into binary strings, distance-based relations among feature quantity vectors and distinctions among classes to which feature quantity vectors belong. Further, the above described conversion functions are simply examples and the information conversion apparatus10may use conversion functions each containing another parameter. Further, the information conversion apparatus10may have no need to apply the same form, in terms of parameter, conversion matrix and the like, to conversion functions to be generated, and the conversion functions that generate the respective bits may take different forms.

Incidentally, the information conversion apparatus10according to the first embodiment is described as a case that implements various kinds of processing by using hardware. However, embodiments are not limited to this, and the processing may be implemented by causing a computer included in the information conversion apparatus10to execute a previously provided program. Accordingly, one example of a computer that executes a program having the same functions as the information conversion apparatus10presented in the first embodiment is described below usingFIG. 7.FIG. 7is a diagram for illustrating one example of a computer that executes an information conversion program.

A computer100presented as an example inFIG. 7has a ROM (Read Only Memory)110, a HDD (Hard Disk Drive)120, a RAM (Random Access Memory)130, and a CPU (Central Processing Unit)140connected to one another via a bus160. Further, the computer100presented as an example inFIG. 7includes an I/O (Input/Output)150for transmitting and receiving packets.

The HDD120stores a feature quantity vector table121that stores feature quantity vectors to be converted. The RAM130has an information conversion program131previously stored therein. In the example illustrated inFIG. 11, the CPU140reads out the information conversion program131from the RAM130and executes this program, so that the information conversion program131starts to function as an information conversion process141. Note that the information conversion process141performs the functions as those performed by the conversion rule generation unit12, the importance level calculation unit13and the conversion rule determination unit14, which are illustrated inFIG. 1.

Note that implementation of the information conversion program described in this embodiment is enabled by executing a previously provided program on a personal computer or a workstation. Such a program may be provided via a network such as the Internet. Further, such a program is recorded on a computer-readable recording medium such as a hard disk, a flexible disk (FD), a CD-ROM (Compact Disc Read Only Memory), an MO (Magneto Optical Disc), or a DVD (Digital Versatile Disc). Further, such a program may be executed by being read out from a recoding medium.

One embodiment makes it possible to optimize a conversion function without difficulty in a manner corresponding to a set of data to be searched.