JP4556121B2 - Information processing apparatus and method, and program - Google Patents

Description

  The present invention relates to an information processing apparatus and method, and a program, and in particular, an information processing apparatus capable of searching for a target element at high speed even when searching based on a plurality of evaluation criteria. The present invention relates to a method and a program.

  Conventionally, finding a nearest neighbor vector close to an input vector from a set of n-dimensional vectors when a certain n-dimensional input vector is given is called the Nearest Neighbor search problem, and many fast search methods have been proposed. Has been.

For example, as an optimal vector search method in vector quantization, when a predetermined centroid vector among N centroid vectors v (i) is an attention vector v ₁ , the attention vector v ₁ and the centroid vector v (i ) Is the N / kth closest distance to the vector of interest v ₁ as the radial distance D _R of the vector of interest, the distance D ₁ between the input vector u and the vector of interest v ₁ , and the radial distance D _R of There is a method of comparing a half value D _R / 2 and determining a search range for an optimal vector corresponding to the comparison result (see, for example, Patent Document 1).

  Such a search method is also used for searching for a feature vector in image recognition processing or the like. A feature vector is a vector obtained by combining feature parameters of an image. By comparing the feature vector of the image to be processed with the feature vector of the model image prepared in advance, the relationship between the image to be processed and the model image is specified. As described above, the image recognition process using the feature vector can perform recognition that is strong against a viewpoint change and a brightness change.

Japanese Patent No. 32735881

  However, in the above method, when there are a plurality of types of features to be compared with the search target, the search is performed individually for each feature, and finally the elements that satisfy the conditions for all the features are specified. There is a problem that search processing is performed even for elements that are clearly unnecessary, the efficiency of the search processing is low, and the processing is slow.

  The present invention has been made in view of such a situation, and makes it possible to search a neighborhood vector of an input vector satisfying a plurality of conditions at high speed.

The information processing apparatus of the present invention is an information processing apparatus for comparing features by comparing feature vectors obtained by combining feature parameters of an image with an input image and a model image prepared in advance, and comparing the model Feature vector storage means for grouping and storing the feature vectors of the image for each dimension of the space in which the feature vectors exist, and extracting a plurality of input vectors that are the feature vectors of the input image from the input image The feature read from the feature vector storage means from the input vector of the processing target in the input vector extracted by the input vector extraction means for the group to be processed of the input vector extraction means From the distance to the vector and the input vector to be processed, the proximity of the input vector to be processed Is compared with the distance to the feature vector that is a candidate for the neighborhood vector located at the position, and the feature vector with the shorter distance is used as a new candidate for the neighborhood vector for all feature vectors in the group By performing one by one, a search unit that searches for candidates for the neighborhood vector in the group, and when the neighborhood vector candidate is updated to a new feature vector by the search by the search unit , the candidate for the neighborhood vector If there are change flag update means for setting a change flag indicating that the change flag has been updated and candidates for the neighborhood vector for which the change flag is not set by the change flag update means , the search is performed for all input vectors. Until the input vector to be processed next is searched, If there is no candidate for the neighborhood vector for which the change flag is not set by the update unit, the search for the group is terminated, and the group to be processed next is processed until the search for all the groups is performed. neighborhood vector to be set and to control means for performing the said search, after the search under the control of said control means is performed for all of the groups, the current candidate for the neighborhood vector as the neighboring vector for Setting means.

For each group of feature vectors stored by the feature vector storage means, each of the feature vectors belonging to the group is a mass point, and a center of gravity that is a point of action of the resultant force of gravity acting on each mass point is a common representative point, It further includes a neighborhood table storage unit that stores a neighborhood table that associates a common representative point with the feature vector located in the vicinity of the common representative point, and the search unit is stored in the neighborhood table storage unit. When the distance between the common representative point included in the neighborhood table and the feature vector located in the vicinity of the common representative point is shorter than the distance between the common representative point and the input vector, the neighborhood table storage means from the feature vectors included in the neighborhood table stored, the neighborhood vector in the group It is possible to search for candidates.

For each group of feature vectors stored by the feature vector storage means, each feature vector belonging to the group is used as a mass point, a center of gravity is obtained as a point of action of the resultant force of gravity acting on each mass point, and the center of gravity is obtained. the common and common representative point setting means for setting a representative point, by matching the feature vectors located in the vicinity of the common representative point that is set by the common representative point setting means to the common representative point, the neighborhood table The neighborhood table creating means for creating the neighborhood table, and the neighborhood table storage means can store the neighborhood table created by the neighborhood table creating means.

The image processing apparatus may further include a feature vector extraction unit that extracts the feature vector from the model image, and the feature vector storage unit may store the feature vector extracted by the feature vector extraction unit .

The information processing method of the present invention is an information processing method of an information processing apparatus that compares features by comparing feature vectors obtained by combining feature parameters of an image with an input image and a model image prepared in advance. Then, the feature vector storage means of the information processing device stores the feature vectors of the model image grouped according to the number of dimensions of the space in which the feature vector exists, and the input vector extraction means of the information processing device , from the input image, the input vector the a feature vector of the input image a plurality of extraction, search means of the information processing apparatus, to the group to be processed, the processing in the extracted the input vector The distance from the target input vector to the feature vector read from the storage unit, and the processing target input vector Comparing the distance to the feature vector that is a candidate for a neighborhood vector located in the vicinity of the input vector to be processed, and setting the feature vector having a shorter distance as a new candidate for the neighborhood vector by performing one for all feature vectors in the group, searching for candidates of the neighboring vector in the group, change flag updating means of the information processing apparatus, by the search, a new candidate of the neighboring vector If it is updated feature vector, sets a change flag indicating that the candidate of the neighboring vector is updated, the control unit of the information processing apparatus, a candidate of the neighboring vector in which the change flag is not set exists If, until the search for all the input vectors is performed, prior to the said input vector processed next When the search is performed and there is no candidate for the neighborhood vector for which the change flag is not set, the search for the group is terminated, and until the search for all the groups is performed, the next processing target The search is performed on the group, and the neighborhood vector setting unit of the information processing apparatus performs the search on all the groups according to the control, and then selects the current neighborhood vector candidate as the neighborhood vector Set as.

The program of the present invention compares a feature vector obtained by combining and combining feature parameters of an image with an input image and a model image prepared in advance, thereby comparing a feature with a computer that compares the feature vector of the model image. Feature vector storage means for grouping and storing each dimension of the space in which the feature vector exists ; input vector extraction means for extracting a plurality of input vectors that are the feature vectors of the input image from the input image; For the group to be processed, a distance from the input vector to be processed in the input vector extracted by the input vector extraction unit to the feature vector read from the feature vector storage unit; Positioned near the input vector to be processed from the input vector to be processed One of all the feature vectors in the group is compared with a distance to the feature vector that is a candidate for a neighboring vector, and the feature vector with the shorter distance is used as a new candidate for the neighboring vector. By performing each of the above, when the neighborhood vector candidate is updated to a new feature vector by the search means for searching for the neighborhood vector candidate in the group, and the search by the search means , the neighborhood vector candidate is updated. When there is a change flag update unit that sets a change flag indicating that the change flag has been set, and when there are candidates for the neighborhood vector for which the change flag is not set by the change flag update unit, until the search is performed for all input vectors The search is performed for the input vector to be processed next, and the change flag is updated. If there is no candidate for the neighborhood vector for which the change flag is not set by the stage, the search for the group is terminated, and until the search for all the groups is performed, Control means for performing the search, and a neighborhood vector setting means for setting the current neighborhood vector candidate as the neighborhood vector after the search is performed for all the groups according to the control by the control means. Make it work.

In the information processing apparatus, method, and program of the present invention, the feature vectors of the model image are stored by being grouped according to the number of dimensions of the space in which the feature vector exists, and are the feature vectors of the input image from the input image. Multiple input vectors are extracted, and for the group to be processed, the distance from the input vector to be processed in the extracted input vector to the feature vector read from the storage unit, and the input vector to be processed , The distance to the feature vector that is a candidate for a neighborhood vector that is located in the vicinity of the input vector to be processed is compared, and the processing that uses the feature vector with the shorter distance as a new neighborhood vector candidate is all by performed one for feature vector of the candidate neighboring vectors in the group it is retrieved, the search More, if the candidate of the neighboring vector is updated to a new feature vector, it is set if the change flag to indicate that the candidate of the neighboring vector is updated, if the candidate of the neighboring vector the change flag is not set exists Until the search is performed for all input vectors, the search is performed for the next input vector to be processed. If there is no neighborhood vector candidate for which no change flag is set, the search for the group is terminated, Until the group is searched, the next group to be processed is searched. After the search is performed for all groups according to the control, the current neighborhood vector candidate is set as the neighborhood vector. The

  According to the present invention, a target element can be searched at high speed even when searching for an element that satisfies a plurality of conditions simultaneously.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 1 is a diagram illustrating a configuration example of a feature amount comparison apparatus to which the present invention is applied.

  A feature amount comparison apparatus 10 shown in FIG. 1 is an apparatus for recognizing a feature vector obtained by vectorizing a parameter or the like indicating the feature of information to be processed such as an image or sound, and is an input feature vector. This is a device that compares a vector with a vector group as a model, searches for a vector closest to an input vector (nearest neighbor vector) for each set of vectors, and outputs the nearest neighbor vector group. As shown in FIG. 1, the feature quantity comparison apparatus 10 includes a vector information storage unit 11, a common representative point setting unit 12, a common representative point information storage unit 13, a neighborhood table group creation unit 14, a neighborhood table group storage unit 15, And a nearest neighbor vector group search unit 16.

  The vector information storage unit 11 has a storage medium such as a hard disk or a semiconductor memory, for example, and stores in advance vector information that is information relating to a feature vector serving as a model. The feature vectors are handled as a set for each model, and the vector information storage unit 11 stores a plurality of sets of feature vectors. That is, the vector information storage unit 11 stores feature vectors of a plurality of models, and if necessary, the feature vectors are stored as common representative point setting unit 12, neighborhood table group creation unit 14, and nearest neighbor vector group search unit. 16 is supplied.

  The common representative point setting unit 12 acquires a feature vector from the vector information storage unit 11 and sets a common representative point (common representative point) for each set (model). The common representative point is information indicating the feature of distribution of the feature vector of each set (model), and is a point (vector) representing all or part of the feature vector. That is, the common representative point is a point (new element) indicating the distribution characteristics of the elements of the set when a plurality of sets stored in the vector information storage unit 11 are set as one set. In other words, the set of common representative points is a set obtained by averaging the characteristics of each set stored in the vector information storage unit 11 (a set that absorbs the difference in element distribution between the sets).

  The number of common representative points is arbitrary, and is set by a user or determined in advance, for example. However, from the property of representing feature vectors, the number of common representative points is preferably less than the number of all feature vectors, and more preferably less than the number of feature vectors in each set (model). The common representative point setting unit 12 sets the number of common representative points set in this way based on all or a part of feature vectors. Details of the common representative point setting method will be described later. The common representative point setting unit 12 supplies the common representative point information (common representative point information) that has been set to the common representative point information storage unit 13 for storage.

  The common representative point information storage unit 13 includes a storage medium such as a hard disk or a semiconductor memory, and stores the common representative point information supplied from the common representative point setting unit 12. The common representative point information storage unit 13 supplies the common representative point information to the neighborhood table group creation unit 14 and the nearest neighborhood vector group search unit 16 as necessary.

  When the neighborhood table group creation unit 14 acquires vector information from the vector information storage unit 11 and further acquires common representative point information from the common representative point information storage unit 13, based on them, for each set (model), A neighborhood table that is a list of feature vectors located in the vicinity of each common representative point is created. As will be described later, the neighborhood table is table information listing feature vectors located in the vicinity of each common representative point, and is created for each set (model). That is, the common representative point (group) is a point (group) representing the feature vectors of all sets (models), and the neighborhood table is table information indicating the relationship between each set and its common representative point. Details of the method of creating the neighborhood table and a method of using the neighborhood table will be described later. When the neighborhood table group creation unit 14 creates such a neighborhood table for each set (model), the neighborhood table group creation unit 14 supplies the neighborhood table group to the neighborhood table group storage unit 15 for storage.

  The neighborhood table group storage unit 15 includes a storage medium such as a hard disk or a semiconductor memory, and stores the neighborhood table group supplied from the neighborhood table group creation unit 14. The neighborhood table group storage unit 15 supplies the neighborhood table group to the nearest neighborhood vector group search unit 16 as necessary.

  When the nearest neighbor vector group search unit 16 acquires an input vector, which is a feature vector input from the outside of the feature quantity comparison device 10, the vector information acquired from the vector information storage unit 11 and the common representative point information storage unit 13 The common representative point information and the neighborhood table group acquired from the neighborhood table group storage unit 15 are used as necessary, and the nearest neighbor vector closest to the input vector is searched for each set (model) based on them. The nearest neighbor vector group search unit 16 outputs the nearest neighbor vector group searched in this way to the outside of the feature quantity comparison device 10 as a comparison result.

  Next, a feature amount comparison method by the feature amount comparison apparatus 10 will be described in detail with reference to FIGS.

  Before comparing the feature quantity of the input vector with the feature vector of the model, the feature quantity comparison apparatus 10 first sets a common representative point and generates a neighborhood table as shown in FIG.

  The vector information storage unit 11 (FIG. 1) stores a search target vector group group 21 composed of a plurality of models (sets), as shown in FIG. The search target vector group group includes M search target vector groups (that is, sets (models)) 21-1 to 21-M. Each group is a set of feature vectors 22.

  When the common representative point setting unit 12 (FIG. 1) unifies the search target vector group group 21 and forms a feature vector group including the one set 23, the common representative point setting unit 12 (FIG. 1) represents the feature vector group that is an element of the set 23. R representative points (indicating the distribution of the feature vector group), that is, common representative points 24 that are common to all sets (all models) are set.

  When the neighborhood table group creation unit 14 (FIG. 1) acquires information about the common representative point 24 via the common representative point information storage unit 13 (FIG. 1), the neighborhood table group creation unit 14 (FIG. 1) is based on the vector information acquired from the vector information storage unit 11. Thus, the neighborhood tables 25-1 to 25-M are created for each set and stored in the neighborhood table group storage unit 15.

  This neighborhood table is configured as shown in FIG. 3, for example. The number of neighborhood vectors of each common representative point listed in the neighborhood table is arbitrary and may be a number designated by the user or a predetermined number. It is desirable that the number of feature vectors in each set is smaller than the number of feature vectors in the neighborhood table.

  In each neighborhood table, as shown in FIG. 3, for each of the R common representative points, identification information of K neighborhood vectors and a half of the distance from the common representative point of the neighborhood vectors. The values are registered in order of closeness.

  For example, in the neighborhood table 25-1, as the neighborhood vector of the common representative point 1, the identification information of the closest feature vector is “No. 3”, and the distance between the feature vector and the common representative point 1 is ½. The value of 1 is “0.29”, the identification information of the second closest feature vector is “No. 8”, and the value of half the distance between the feature vector and the common representative point 1 is “ 0.32 ”, the identification information of the feature vector closest to the third is“ No. 9 ”, and the value of a half of the distance between the feature vector and the common representative point 1 is“ 0.42 ”. Yes, the identification information of the feature vector closest to the fourth is “No. 2”, and the value of a half of the distance between the feature vector and the common representative point 1 is “0.46”. The identification information of the near feature vector is “No. 5”, and the feature vector and the common representative 1 1 value of half the distance between is shown to be "0.51". Similarly, in the neighborhood table 25-1, the common vectors from the common representative point 2 to the common representative point R are registered up to the fifth (K-th) in order from the nearest.

  The neighborhood table group creation unit 14 creates M neighborhood tables for each set (model) of feature vectors.

  This neighborhood table is used to narrow down feature vectors to be searched when searching for neighborhood vectors of input vectors.

  As shown in FIG. 4, the nearest neighbor vector group search unit 16 approximates an input vector 27 that is a feature vector of the information 26 in order to compare the feature of the information 26 to be processed with the feature of each model. A vector is searched from the feature vector 22 of each group of the search target vector group group 21. That is, the nearest neighbor vector group search unit 16 first searches the nearest vector 28-1 of the input vector 27 for the set search target vector group 21-1, and then inputs the input vector for the set search target vector group 21-2. 27 nearest neighbor vectors 28-2 are searched. The nearest neighbor vector group search unit 16 similarly searches the nearest neighbor vectors of the input vector 27 for the set search target vector groups 21-3 to 21-M. Then, the nearest neighbor vector group search unit 16 outputs the nearest neighbor vector group searched in this way as a comparison result between the processing target information 26 and the model.

  When searching for the nearest neighbor vector, the nearest neighbor vector group search unit 16 uses the neighborhood table group of FIG. 3 to reduce the search range and search for the nearest neighbor vector group at high speed. That is, the nearest neighbor vector group search unit 16 first calculates the distance between the input vector 27 and the common representative point. Next, the nearest neighborhood vector group search unit 16 compares the distance with one half of the distance between the neighborhood vector and the common representative point in the neighborhood table. When the distance between the input vector 27 and the common representative point is shorter, the nearest neighbor vector group search unit 16 uses the nearest neighbor vector of the input vector 27 as a neighborhood vector group (common representative point) of the common representative points registered in the neighborhood table. (Including points), and other feature vectors are not searched out of the search range. Conversely, when the distance between the input vector 27 and the common representative point is far, the nearest neighbor vector group search unit 16 searches for the nearest neighbor vector of the input vector 27 from all the feature vectors of the set.

  The principle of setting the range will be described with reference to FIG. The input vector v, the common representative point r, and the neighborhood vector k farthest from the common representative point r registered in the neighborhood table (that is, the Kth closest to the common representative point r) are as shown in FIG. Suppose that it is a positional relationship. A circle 31 indicates a distance D between the common representative point r and the neighborhood vector k, and a circle 32 indicates a half (D / 2) of the distance D.

  Considering the common representative point r as a reference, when the nearest neighbor vector of the input vector v is farthest from the input vector, the nearest neighbor vector becomes the common representative point r. That is, as indicated by a dotted circle in FIG. 5, the nearest neighbor vector of the input vector v does not exist at a position far from the common representative point r (the nearest neighbor vector is always located within the dotted circle).

  Therefore, when the input vector v exists inside the circle 32, that is, the distance d between the input vector v and the common representative point r is shorter than half of the distance D between the neighboring vector k and the common representative point r ( In the case of d <D / 2), the dotted circle does not protrude outside the circle 31. That is, in this case, the nearest neighbor vector of the input vector v always exists at a position closer to the neighborhood vector k of the common representative point.

  Based on the principle as described above, the nearest neighbor vector group search unit 16 calculates the distance between the input vector 27 and each common representative point, and the nearest neighbor vector registered in the neighbor table from the common representative point. The half of the distance to the common representative point is compared with the calculated distance. The nearest neighbor vector group search unit 16 performs such processing for each common representative point, and when there is a common representative point whose distance between the input vector and the common representative point is shorter, The nearest neighbor vector of the input vector is searched from the neighborhood vectors. Then, only when there is no common representative point in which the distance between the input vector and the common representative point is shorter for any common representative point, the nearest neighbor vector group search unit 16 includes the search target vector group. All feature vectors are searched, and the nearest neighbor vector is searched from them.

  The nearest neighbor vector group search unit 16 performs such a search for each search target vector group (model), and outputs a nearest neighbor vector group as a comparison result. By doing in this way, the feature quantity comparison apparatus 10 can exclude unnecessary feature vectors that are not clearly the nearest neighbor vector from the search target, so that the target element can be searched at high speed. The common representative point setting unit 12 sets a common representative point common to all search target vector groups (models), and the nearest neighbor vector group searching unit 16 searches for the nearest neighbor vector based on the common representative point. Thus, the feature quantity comparison apparatus 10 can search the nearest neighbor vector from each search target vector group at high speed even when there are a plurality of search target vector groups. That is, the feature quantity comparison apparatus 10 can search a target element from each set at high speed even when there are a plurality of sets to be searched.

  Next, a detailed configuration of each part of the feature amount comparison apparatus 10 of FIG. 1 will be described.

  FIG. 6 is a diagram illustrating a detailed configuration example of the common representative point setting unit 12. In FIG. 6, the common representative point setting unit 12 includes a common representative point target number setting unit 41, a vector group unification unit 42, a centroid calculation unit 43, a common representative point setting unit 44, a common representative point number determination unit 45, and a common representative point division. A unit 46, a member vector allocation unit 47, and a common representative point storage control unit 48.

  The common representative point target number setting unit 41 sets the common representative point target number based on, for example, a user input and supplies the information to the common representative point number determination unit 45. The target number of common representative points is set to 2 to the nth power (n is an integer), for example. In addition, the common representative point target number may be a value instructed by a user or the like, or may be a predetermined value.

  When the vector group unification unit 42 obtains vector information from the vector information storage unit 11, based on the information, the vector group unification unit 42 unifies all the vector groups stored in the vector information storage unit 11 and includes one vector including all vectors. Create a vector group. Then, the vector group unification unit 42 supplies the information to the centroid calculation unit 43.

  Based on the vector information supplied from the vector group unifying unit 42 or the vector information supplied from the member vector allocating unit 47, the centroid calculating unit 43 calculates the centroid of the vector group for each vector group (the centroid position of the vector distribution). Is calculated. For example, in the vector information supplied from the vector group unification unit 42, since the vector group is unified into one, when calculating the centroid position based on the vector information, the centroid calculation unit 43 includes all vectors. Calculate the center of gravity of the group. Further, when calculating the centroid position based on the vector information supplied from the member vector allocating unit 47, the centroid calculating unit 43 sets the member vector group allocated to the same common representative point by the member vector allocating unit 47 as one vector. A barycentric position is calculated for each vector group. The center-of-gravity calculation unit 43 supplies information regarding the calculated center of gravity to the common representative point setting unit 44.

  The common representative point setting unit 44 sets the centroid position supplied from the centroid calculating unit 43 as a common representative point, and supplies the information to the common representative point number determining unit 45 and the member vector assigning unit 47.

  When the common representative point number determination unit 45 acquires the setting result supplied from the common representative point setting unit 44 or the allocation result from the member vector allocation unit 47, the common representative point number determination unit 45 determines the common representative point in the setting result or allocation result. It is determined whether or not the number is less than the common representative point target number supplied from the common representative point target number setting unit 41, and based on the determination result, information on the common representative point is shared by the common representative point dividing unit 46 or the common representative point. This is supplied to the point storage controller 48.

  When the common representative point dividing unit 46 obtains information on the common representative points from the common representative point number determining unit 45, the common representative point dividing unit 46 divides each common representative point into two and sets them in a predetermined direction so as to be separated from the original position. Shift a small amount. For example, the common representative point dividing unit 46 shifts one position of the divided point by a small amount in the positive direction of the x axis and shifts the other position in the negative direction of the x axis. Note that the two point positions may be corrected in any direction as long as they are opposite to each other. That is, the common representative point dividing unit 46 divides the number of common representative points and corrects the position, thereby increasing the number of common representative points by a factor of two. The common representative point dividing unit 46 supplies the information of the common representative point that has been divided and corrected in position to the member vector assigning unit 47.

  The member vector assigning unit 47 obtains information on the common representative points supplied from the common representative point dividing unit 46, that is, information on the common representative points divided by the common representative point dividing unit 46 and doubled in number. Then, a member vector is allocated to each of these common representative points, and the allocation result is supplied to the centroid calculating unit 43, and information regarding the number of common representative points is supplied to the common representative point number determining unit 45.

  Further, when the member vector assigning unit 47 obtains the common representative point setting result supplied from the common representative point setting unit 44, the member vector assigning unit 47 assigns a member vector to each set common representative point based on the setting result. The allocation result is supplied to the center of gravity calculation unit 43 and information regarding the number of common representative points is supplied.

  The common representative point storage control unit 48 supplies information related to the common representative points supplied from the common representative point number determination unit 45 to the common representative point information storage unit 13 and stores the information.

  FIG. 7 is a block diagram illustrating a detailed configuration example of the neighborhood table group creation unit 14 of FIG.

  In FIG. 7, the neighborhood table group creation unit 14 includes an initialization processing unit 61, a neighborhood table group creation control unit 62, a neighborhood table creation unit 63, and a neighborhood table storage control unit 64.

  When the initialization processing unit 61 acquires vector information from the vector information storage unit 11 and the common representative point information from the common representative point information storage unit 13, the initialization processing unit 61 sets variables necessary for creating the neighborhood table group to initial values. And so on.

  The neighborhood table group creation control unit 62 performs control processing related to creation of neighborhood table groups. The neighborhood table creation unit 63 performs processing related to creation of the neighborhood table. The neighborhood table storage control unit 64 controls the neighborhood table group storage unit 15 to store the created neighborhood table.

  FIG. 8 is a block diagram illustrating a detailed configuration example of the neighborhood table creation unit 63 in FIG. In FIG. 8, the neighborhood table creation unit 14 includes a neighborhood table group creation control unit 81, a distance information creation unit 82, a distance information sort unit 83, a distance information extraction unit 84, and a record holding unit 85.

  The neighborhood table creation control unit 81 performs control processing related to creation of the neighborhood table. The distance information creation unit 82 performs processing related to creation of distance information used for the neighborhood table. The distance information sorting unit 83 arranges (sorts) the pieces of distance information created by the distance information creating unit 82 in ascending order of values (in order of short distance). The distance information extraction unit 84 extracts a predetermined number of distance information from the shorter distance information among the sorted distance information. The record holding unit 85 holds the extracted distance information as a record in the neighborhood table, and returns the information to the neighborhood table creation control unit 81.

  FIG. 9 is a block diagram illustrating a detailed configuration example of the distance information creation unit 82 of FIG. In FIG. 9, the distance information creation unit 82 includes a distance information creation control unit 101, a distance calculation unit 102, a 1/2 multiplication unit 103, and a distance information holding unit 104.

  The distance information creation control unit 101 performs control processing related to creation of distance information. The distance calculation unit 102 calculates the distance between the common representative point designated as the processing target and the member vector. The 1/2 multiplier 103 multiplies the calculated distance between the common representative point and the member vector by 1/2. The distance information holding unit 104 holds a half value of the distance between the common representative point and the member vector as distance information, and returns the information to the distance information creation control unit 101.

  FIG. 10 is a block diagram illustrating a detailed configuration example of the nearest neighbor vector group search unit 16 of FIG. In FIG. 10, the nearest neighbor vector group search unit 16 includes an initialization processing unit 121, a nearest neighbor vector group search control unit 122, and a nearest neighbor vector search unit 123, which are stored in the vector information storage unit 11. The nearest neighbor vector group of the input vector is searched from the model.

  When acquiring the input vector, the initialization processing unit 121 acquires vector information from the vector information storage unit 11, acquires common representative point information from the common representative point information storage unit 13, and stores a neighborhood table from the neighborhood table group storage unit 15. A group is acquired, and initialization processing such as setting a variable necessary for searching the nearest neighbor vector group of the input vector to an initial value is performed.

  The nearest neighbor vector group search control unit 122 performs control processing related to the search for the nearest neighbor vector group of the input vector. The nearest neighbor vector search unit 123 is controlled by the nearest neighbor vector group search control unit 122, searches for the nearest neighbor vector of the input vector for each vector group, and returns the search result to the nearest neighbor vector group search control unit 122.

  FIG. 11 is a block diagram illustrating a detailed configuration example of the nearest neighbor vector search unit 123 of FIG. In FIG. 11, the nearest neighbor vector search unit 123 includes an initialization processing unit 141, a nearest neighbor vector search control unit 152, a distance calculation unit 143, a distance comparison unit 144, an in-table search unit 145, a nearest neighbor vector setting unit 146, and An entire group search unit 147 is provided, and the nearest neighbor vector search process for each model (vector group) is performed.

  The initialization processing unit 141 performs initialization processing such as setting a variable necessary for searching for the nearest neighbor vector of an input vector to an initial value. The nearest neighbor vector search control unit 142 performs control processing related to the search of the nearest neighbor vector of the input vector in the processing target vector group.

  The distance calculation unit 143 calculates the distance between the input vector and the common representative point to be processed. The distance comparison unit 144 compares the distance between the calculated input vector and the common representative point to be processed with the distance information in the neighborhood table, and causes the in-table search unit 145 to search for the nearest neighbor vector according to the comparison result. Is executed.

  The in-table search unit 145 searches for the nearest neighbor vector of the input vector from among the member vectors registered in the neighborhood table, and supplies the search result to the nearest neighbor vector setting unit 146.

  The nearest neighbor vector setting unit 146 sets the member vector searched by the in-table search unit 145 or the entire group search unit 147 as the nearest neighbor vector of the input vector, and returns the setting result to the nearest neighbor vector search control unit 142. .

  When the nearest neighborhood vector search control unit 142 determines that the nearest neighbor vector of the input vector does not exist among the neighborhood vectors of all the common representative points, the in-group overall search unit 147 The nearest neighbor vector of the input vector is searched from among the member vectors, and the search result is supplied to the nearest neighbor vector setting unit 146.

  FIG. 12 is a block diagram illustrating a detailed configuration example of the in-table search unit 145 of FIG. 12, the in-table search unit 145 includes an initialization processing unit 161, an in-table search control unit 162, a distance calculation unit 163, an update control unit 164, and a data holding unit 165, and is registered in the neighborhood table. The nearest neighbor vector is searched for a member vector (search in the nearest neighbor vector table).

  The initialization processing unit 161 performs an initialization process such as setting variables necessary for searching the nearest neighbor vector in the table to initial values. For example, the initialization processing unit 161 sets Vkeep, which is a nearest neighbor vector candidate, as a virtual point whose distance from the input vector is infinity, and sets the distance Dkeep from the input vector as infinity. Further, the initialization processing unit 161 sets the value of the variable k to an initial value (for example, “0”). The in-table search control unit 162 performs control processing related to the in-table search for the nearest neighbor vector. The distance calculation unit 163 calculates the distance between the input vector and the member vector registered in the neighborhood table. The update control unit 164 controls the update of data held by the data holding unit 165 based on the calculated distance between the input vector and the member vector. The update control unit 164 returns the control result to the in-table search control unit 162. The data holding unit 165 holds data (for example, Vkeep and Dkeep) related to a vector closest to the input vector (nearest neighbor vector candidate).

  FIG. 13 is a block diagram illustrating a detailed configuration example of the in-group entire search unit 147 of FIG. In FIG. 13, the entire group search unit 147 includes an initialization processing unit 181, an entire group search control unit 182, a distance calculation unit 183, an update control unit 184, and a data holding unit 185. The nearest neighbor vector search for all member vectors (entire search within the group of nearest neighbor vectors) is performed.

  The initialization processing unit 181 performs initialization processing such as setting a variable necessary for the entire search within the group of the nearest neighbor vector to an initial value. For example, the initialization processing unit 181 sets a virtual point whose distance from the input vector is infinity for Vkeep, which is a candidate for the nearest neighbor vector, and sets the distance Dkeep from the input vector to infinity. Further, the initialization processing unit 181 sets the value of the variable i to an initial value (for example, “0”). The in-group entire search control unit 182 performs control processing relating to the entire in-group search for the nearest neighbor vector. The distance calculation unit 183 calculates the distance between the input vector and the member vector in the vector group. The update control unit 184 controls updating of data held by the data holding unit 185 based on the calculated distance between the input vector and the member vector. Also, the update control unit 184 returns the control result to the in-group overall search control unit 182. The data holding unit 185 holds data (for example, Vkeep and Dkeep) related to the vector closest to the input vector (nearest vector candidate).

  Next, the flow of each process executed by the feature quantity comparison apparatus 10 having the above configuration will be described.

  First, the feature quantity comparison apparatus 10 determines a representative point group common to each vector group (model) based on the vector information held in the vector information holding unit 11 by the common representative point setting unit 12 (FIG. 1). Set. The flow of the common representative point setting process will be described with reference to the flowchart of FIG.

  When the common representative point setting process is started, in step S1, the common representative point target number setting unit 41 (FIG. 6) is based on the input target number (for example, 2 to the nth power (n is an integer)). The variable NumReq for the target number of common representative points is set, and the value is supplied to the common representative point number determination unit 45.

  In step S2, the vector group unification unit 42 acquires vector information from the vector information storage unit 11, unifies all the vector groups stored in the vector information storage unit 11 based on the vector information, One group consisting of all or part of the member vectors is generated. That is, the vector group unifying unit 42 reconfigures all member vectors of each group or a part of member vectors extracted from each group by an arbitrary method as one group. Whether to use all of the member vectors or a part of the member vectors for unification of the group may be determined by an arbitrary method every time or may be determined in advance.

  When the group is unified, the center-of-gravity calculation unit 43 acquires vector information of the group unified from the vector group unification unit 42 in step S3, and based on the information, the center-of-gravity point (each member vector) Are used as mass points, and the resultant action point of gravity acting on each mass point is calculated, and the calculation result is supplied to the common representative point setting unit 44.

  In step S4, the common representative point setting unit 44 sets the center of gravity as a common representative point, sets the value of the variable GpNum indicating the number of common representative points to “1”, and sets the setting result as the common representative point number determination unit. 45. In step S5, the common representative point number determination unit 45 determines whether or not the value of the number of common representative points GpNum is smaller than the target number NumReq.

  If it is determined that the number of common representative points GpNum is smaller than the target number NumReq, that is, the target number of common representative points is not set (the number of set common representative points has not reached the target value). ), The common representative point number determining unit 45 supplies the common representative point information to the common representative point dividing unit 46, and the process proceeds to step S6.

  In step S6, the common representative point dividing unit 46 divides each common representative point into two based on the supplied common representative point information, and corrects the position. Then, in step S7, the common representative point dividing unit 46 doubles the number of common representative points GpNum, and supplies the common representative point information to the member vector assigning unit 47.

  The member vector assigning unit 47 assigns each member vector to a common representative point in step S8, and in step S9, whether or not all the common representative points to which each member vector belongs is the same as the previous time, that is, each common representative point. Is the same as in the previous assignment, and it is determined whether or not the same member vector as in the previous assignment is assigned to each common representative point.

  If it is determined that the common representative points to which each member vector belongs are not all the same as the previous time, that is, the common representative points are different from the previous assignment, or the member vectors assigned to each common representative point are different. In this case, the member vector allocation unit 47 supplies the determination result to the centroid calculation unit 43, and the process proceeds to step S10.

  In step S10, the center-of-gravity calculation unit 43 calculates the center-of-gravity point of member vectors belonging to the same common representative point, and the common representative point setting unit 44 sets the center-of-gravity point as a new common representative point. That is, the center-of-gravity calculation unit 43 sets the member vector group assigned to one common representative point as one group, and calculates the center-of-gravity point for each group. The common representative point setting unit 44 sets the calculated barycentric points as common representative points, supplies the processing result to the member vector allocation unit 47, returns the processing to step S8, and repeats the subsequent processing. The member vector assigning unit 47 assigns member vectors to the common representative points again based on the supplied common representative point information.

  That is, the member vector assigning unit 47, the centroid calculating unit 43, and the common representative point setting unit 44 determine that the member vector assigning unit 47 determines that all the common representative points to which each member vector belongs are the same as in the previous time in step S9. Steps S8 to S10 are repeated until the above.

  If it is determined in step S9 that all the common representative points to which each member vector belongs are the same as the previous time, the member vector allocation unit 47 supplies the determination result to the common representative point number determination unit 45, and the process proceeds to step S5. Return and execute the subsequent processing.

  That is, the common representative point number determining unit 45, the common representative point dividing unit 46, the member vector assigning unit 47, the centroid calculating unit 43, and the common representative point setting unit 44 are configured such that the common representative point number determining unit 45 uses the common representative point determining unit 45 in step S5. Steps S5 to S10 are repeated until it is determined that the number GpNum is not smaller than the target number NumReq.

  In step S5, when it is determined that the value of the number of common representative points GpNum is not smaller than the value of the target number NumReq, that is, the common representative points for the target number are set (the number of set common representative points is the target number). If it is determined that the value has reached, the common representative point number determination unit 45 supplies information on the common representative point to the common representative point storage control unit 48, and the process proceeds to step S11.

  In step S11, the common representative point storage control unit 48 supplies the common representative point information to the common representative point information storage unit 13 for storage. The common representative point information storage unit 13 stores information on the supplied common representative point information.

  The common representative point storage control unit 48 ends the common representative point setting process when the process of step S11 ends.

  As described above, the common representative point setting unit 12 performs the common representative point setting process, and sets R common representative points using the centroid points. ) Easily create a neighborhood table for each set (model), and use that neighborhood table to quickly search for neighborhood vectors of input vectors for each set (model). Can do.

  The feature quantity comparison apparatus 10 having set R common representative points as described above, for each vector group (model), the neighborhood table, which is table information related to the neighborhood vector of each common representative point, is represented by the number of vector groups ( M)) (create a neighborhood table group consisting of M neighborhood tables). The neighborhood table group creation unit 14 (FIG. 1) is based on the common representative point information stored in the common representative point information storage unit 13 and the vector information stored in the vector information storage unit 11. Execute the creation process. The flow of the neighborhood table group creation process will be described with reference to the flowchart of FIG.

  When the neighborhood table group creation process is started, the initialization processing unit 61 (FIG. 7) of the neighborhood table group creation unit 14 in step S31, variable j (0 ≦ j ≦ M−1) indicating the vector group to be processed. ), A variable h (0 ≦ h ≦ R−1) indicating a common representative point to be processed, and a variable i (0 ≦ i ≦ N−1) indicating a member vector to be processed are initialized. An initialization process such as setting to a value (eg, “0”) is performed. M, R, and N are arbitrary natural numbers.

  In step S32, the neighborhood table group creation control unit 62 determines whether or not neighborhood tables have been created for all M vector groups. If it is determined that there are vector groups for which neighborhood tables have not yet been created, the determination is made. The result is supplied to the neighborhood table creation unit 63, and the process proceeds to step S33. In step S33, the neighborhood table creation unit 63 creates a neighborhood table for the vector group S (j). Details of this neighborhood table creation processing will be described later.

  When the neighborhood table is created, the neighborhood table creation unit 63 supplies the created neighborhood table to the neighborhood table storage control unit 64, and the process proceeds to step S34.

  In step S34, when the neighborhood table storage control unit 64 acquires the created neighborhood table, the neighborhood table storage control unit 64 supplies the neighborhood table to the neighborhood table group storage unit 15, and is composed of neighborhood tables of other vector groups already stored. Remember to add to group (one or more neighborhood tables). Based on the control, the neighborhood table group storage unit 15 stores the supplied neighborhood table so as to be added to the already stored neighborhood table group. If the neighborhood table group storage unit 15 stores no neighborhood table and the supplied neighborhood table is the first neighborhood table, the neighborhood table group storage unit 15 stores the supplied neighborhood table. Store as a new neighborhood table group.

  When the process of step S34 is completed, the neighborhood table storage control unit 64 returns the processing result to the neighborhood table group creation control unit 62. In step S <b> 35, the neighborhood table group creation control unit 62 adds “+1” to the value of the variable j, and changes the processing target vector group for creating the neighborhood table.

  As described above, the neighborhood table group creation control unit 62, the neighborhood table creation unit 63, and the neighborhood table storage control unit 64 created neighborhood tables for all vector groups in step S32. Steps S32 to S35 are repeated until it is determined that M neighborhood tables have been created). If it is determined in step S32 that the neighborhood tables for all vector groups have been created, the neighborhood table group creation control unit 62 ends the neighborhood table group creation process.

  By executing the neighborhood table group creation processing in this way, the neighborhood table group creation processing unit 14 can create a neighborhood table for each vector group (create a neighborhood table group including M neighborhood tables). At that time, by using a common representative point common to each vector group, the neighborhood table group creation processing unit 14 selects each neighborhood table even when there are a plurality of search target vector sets (vector groups). Can be created at high speed. Further, by using this neighborhood table group for the search of the nearest neighbor vector of the input vector, the feature quantity comparison apparatus 10 can use the neighborhood vector of the input vector from each set even when there are a plurality of vector sets to be searched. Can be searched at high speed.

  Next, details of the flow of the neighborhood table creation process executed by the neighborhood table creation unit 63 (FIG. 7) in step S33 of FIG. 15 will be described with reference to the flowchart of FIG.

  When the neighborhood table creation process is started, the neighborhood table creation control unit 81 (FIG. 8) of the neighborhood table creation unit 63 determines whether or not all R common representative point records have been created in step S51. . As described with reference to FIG. 3, the neighborhood table is composed of records corresponding to the common representative points. The neighborhood table creation control unit 81 obtains all the neighborhood vectors of the common representative points (K (K is an arbitrary natural number)), completes creation of R records, and determines whether the neighborhood table is completed. judge. When it is determined that there is a common representative point for which no record has yet been created (neighbor table has not been obtained) and records for all common representative points have not been created, the neighborhood table creation control unit 81 performs processing. Proceed to S52.

  In step S52, the distance information creation unit 82 obtains distance information (common representative point C (h)) between the common representative point C (h) to be processed and each vector Vm (each member vector of the vector group to be processed). 1/2) of the distance to the member vector Vm is created. Details of this distance information creation processing will be described later. When the distance information creation unit 82 creates the distance information, the distance information creation unit 82 supplies the distance information to the distance information sorting unit 83, and the process proceeds to step S53. In step S <b> 53, the distance information sorting unit 83 sorts the created distance information in ascending order of distance (in ascending order of value) and supplies the sorting result to the distance information extracting unit 84. The distance information extraction unit 84 extracts K pieces of distance information from the shorter distance in step S54, and supplies the extracted distance information to the record holding unit 85.

  In step S55, the record holding unit 85 records the distance information group extracted by the distance information extraction unit 84 in the neighborhood table of the group S (j) that is the current processing target, and records the common representative point C (h). Hold as you add. That is, the record holding unit 85 holds the distance information group supplied from the distance information extraction unit 84 as a record in the neighborhood table.

  The record holding unit 85 returns the processing result to the neighborhood table creation control unit 81. In step S56, the neighborhood table creation control unit 81 adds “+1” to the value of the variable h, changes the processing target common representative point, returns the processing to step S51, and repeats the subsequent processing.

  That is, the neighborhood table creation control unit 81, the distance information creation unit 82, the distance information sort unit 83, the distance information extraction unit 84, and the record holding unit 85 are configured so that the neighborhood table creation control unit 81 sets all the common representative points in step S51. Steps S51 to S56 are repeated until it is determined that a record has been created.

  If it is determined in step S51 that all common representative point records have been created and a neighborhood table has been created for the vector group to be processed, the neighborhood table creation control unit 81 ends the neighborhood table creation process, and records The record group held by the holding unit 85 is supplied as a neighborhood table to the neighborhood table storage control unit 64 (FIG. 7), the process is returned to step S33 in FIG. 15, and the processes after step S34 are executed.

  Next, details of the flow of the distance information creation process executed by the distance information creation unit 82 (FIG. 8) in step S52 of FIG. 16 will be described with reference to the flowchart of FIG.

  When the distance information creation process is started, the distance information creation control unit 101 (FIG. 9) of the distance information creation unit 82 performs the current processing target for the common representative point C (h) that is the current processing target in step S71. It is determined whether or not the distance information of all N member vectors Vm (i, j) in the vector group S (j) is created. When it is determined that there is a member vector Vm (i, j) for which distance information has not yet been created and records for all R common representative points have not been created, the distance information creation control unit 101 performs processing. Proceed to S72.

  In step S72, the distance calculation unit 102 calculates the distance between the common representative point C (h) currently processed and the member vector Vm (i, j). For example, when the common representative point C (h) and the member vector Vm (i, j) exist on one plane and the position is indicated by the x coordinate and the y coordinate, the coordinates of the common representative point C (h) are If (x1, y1) and the coordinates of the member vector Vm (i, j) are (x2, y2), the distance Dcm (h, i) between the common representative point C (h) and the member vector Vm (i, j) , J) is expressed by the following equation (1).

Dcm = √ (x1−x2) ² + (y1−y2) ² (1)

  That is, the distance Dcm is indicated by the square root of the sum of the squares of the differences between the coordinates. When the distance calculation unit 102 calculates the distance in this way, the distance calculation unit 102 supplies the distance to the ½ multiplication unit 103. In step S <b> 73, the ½ multiplier 13 multiplies the calculated distance by ½, calculates Dcm / 2, and supplies the multiplication result to the distance information holding unit 104.

  In step S74, the distance information holding unit 104 holds the multiplication result as distance information of the member vector Vm (i, j), and returns the processing result to the distance information creation control unit 101. In step S75, the distance information creation control unit 101 adds “+1” to the value of the variable i indicating the processing target member vector Vm to change the processing target member vector. When the process target member vector is changed, the distance information creation control unit 101 returns the process to step S71, and repeats the subsequent processes for the new process target member vector.

  That is, the distance information creation control unit 101, the distance calculation unit 102, the ½ multiplication unit 103, and the distance information holding unit 104 have created the distance information for all the member vectors in step S71. Steps S71 to S75 are repeated until it is determined.

  In step S71, the distance information of all N member vectors Vm (i, j) in the vector group S (j) that is the current processing target for the common representative point C (h) that is the current processing target. The distance information creation control unit 101 ends the distance information creation process, and supplies the distance information held by the distance information holding unit 104 to the distance information sorting unit 83 (FIG. 8). The process returns to step S52 in FIG. 16 to execute the processes after step S53.

  The nearest neighbor vector group search unit 16 of the feature quantity comparison device 10 of FIG. 1 has information on common representative points stored in the neighborhood table group stored in the neighborhood table group storage unit 15 and the common representative point information storage unit 13. Based on the vector information stored in the vector information storage unit 11, the nearest neighbor vector for the input vector is searched for each vector group (model), and these are output as a nearest neighbor vector group. The flow of this nearest neighbor vector group search process will be described with reference to the flowchart of FIG. When the input vector is input and the nearest neighbor vector group search process is started, the initialization processing unit 121 of the nearest neighbor vector group search unit 16 acquires the vector information from the vector information storage unit 11 in step S91. The information of the common representative point is acquired from the representative point information storage unit 13, the neighborhood table group is acquired from the neighborhood table group storage unit 15, and the value of the variable j indicating the vector group to be processed, the common representative point of the processing target Initialization processing such as setting the value of the variable h indicating, and the values of the variables i and k indicating the member vector to be processed to initial values (for example, “0”).

  In step S92, the nearest neighbor vector group search control unit 122 determines whether or not the nearest vector of the input vector has been searched for all M vector groups (models), and determines that there is an unprocessed vector group. In this case, the determination result is supplied to the nearest neighbor vector search unit 123, and the process proceeds to step S93. In step S93, the nearest neighbor vector search unit 123 executes a process of searching for the nearest neighbor vector of the input vector for the processing target vector group. Details of this nearest neighbor vector search processing will be described later. When the nearest neighbor vector search unit 123 searches for the nearest neighbor vector, the nearest neighbor vector search unit 123 supplies the search result to the nearest neighbor vector group search control unit 122, and the process proceeds to step S94. In step S94, the nearest neighbor vector group search control unit 122 adds “+1” to the value of the variable j, changes the processing target vector group, returns the process to step S91, and thereafter processes the new processing target vector group. Repeat the process.

  That is, the nearest neighbor vector group search control unit 122 and the nearest neighbor vector search unit 123 perform step S92 until it is determined in step S92 that the nearest neighbor vector group search control unit 122 has searched nearest neighbor vectors for all M vector groups. Thru | or the process of step S94 is repeated.

  In step S92, when the nearest neighbor vectors of the input vectors are searched for all the vector groups and it is determined that all the nearest neighbor vectors are obtained, the nearest neighbor vector group search control unit 122 selects the nearest neighbor vector group. To output the nearest neighbor vector group search process.

  As described above, the nearest neighbor vector group search unit 16 searches each vector group (model) for the nearest neighbor vector of the input vector, and outputs the nearest neighbor vector group. Even if there is a feature, the features of each model can be easily compared with the features of the input information.

  Next, details of the flow of the nearest neighbor vector search process executed by the nearest neighbor vector search unit 123 (FIG. 10) in step S93 of FIG. 18 will be described with reference to the flowchart of FIG.

  When the nearest neighbor vector search process is started, the initialization processor 141 (FIG. 11) of the nearest neighbor vector search unit 123, in step S111, sets the value of the variable h indicating the common representative point to be processed, and the processing target. Initialization processing such as setting the values of variable i and variable k indicating the member vector to initial values (for example, “0”) is performed.

  In step S112, the nearest neighbor vector search control unit 142 determines whether or not the presence determination of the nearest neighbor vector has been performed for all R common representative points C (h). When it is determined that the presence determination of the nearest neighbor vector is not performed for all the common representative points C (h), that is, it is determined that there is an unprocessed common representative point, the nearest neighbor vector search control unit 142 sets the determination result as a distance. The data is supplied to the calculation unit 143, and the process proceeds to step S113.

  In step S113, the distance calculation unit 143 calculates the distance Dinc (h) between the input vector Vin and the common representative point C (h), and supplies the calculation result to the distance comparison unit 144. The distance calculation unit 143 calculates the square root of the sum of the squares of the differences between the coordinates as in the case of the above-described equation (1), that is, the distance between the common representative point and the member vector.

  In step S114, the distance comparison unit 144 compares the distance Dinc (h) with the maximum value of the distance information of the record of the common representative point C (h) in the neighborhood table. In step S115, the distance Dinc (h) is greater. Determine whether it is short. If it is determined that the maximum value of the distance information of the record of the common representative point C (h) in the neighborhood table is shorter than the distance Dinc (h), the distance comparison unit 144 uses the comparison result as the nearest neighbor vector search control. Returning to unit 142, the process proceeds to step S116.

  In step S116, the nearest neighbor vector search control unit 142 adds “+1” to the value of the variable h, changes the processing target common representative point C (h), returns the process to step S112, and sets a new common representative point. For C (h), the processes after step S112 are executed.

  That is, the nearest neighbor vector search control unit 142, the distance calculation unit 143, and the distance comparison unit 144 determine that the nearest neighbor vector search control unit 142 determines the presence of the nearest neighbor vector for all common representative points C (h) in step S112. Until the distance comparison unit 144 determines in step S115 that the distance Dinc (h) is shorter than the maximum value of the distance information of the record of the common representative point C (h) in the neighborhood table, the process proceeds to step S112. Thru | or the process of step S116 is repeated.

  In step S115, when it is determined that the distance Dinc (h) is shorter than the maximum value of the distance information of the record of the common representative point C (h) in the neighborhood table, the distance comparison unit 144 determines the determination result. The data is supplied to the in-table search unit 145, and the process proceeds to step S117. In step S117, the in-table search unit 145 searches for a vector closest to the input vector in the treatment target vicinity table. That is, the in-table search unit 145 limits the search range of the nearest neighbor vector of the input vector to the neighborhood vectors registered in the neighborhood table, and searches for the nearest neighbor vector from those neighborhood vectors. The details of the flow of the nearest neighbor vector search process will be described later.

  The table search unit 145 supplies the search result to the nearest neighbor vector setting unit 146 when the process of step S117 is completed. The nearest neighbor vector 146 sets the vector searched by the in-table search unit 145 supplied as the search result in step S118 as the nearest neighbor vector, and sets the nearest neighbor vector to the nearest neighbor vector group search control unit 122. Then, the nearest neighbor vector search process ends, the process returns to step S93 in FIG. 18, and the processes after step S94 are executed.

  That is, in the neighborhood table, when there is a common representative point whose distance to the input vector is shorter than the maximum value of distance information of the record (1/2 of the distance), the in-table search unit 145 determines the common point. The nearest neighbor vector of the input vector is searched from the neighborhood vectors of representative points (member vectors registered in the neighborhood table).

  In step S112, if it is determined that the presence determination of the nearest neighbor vector has been performed for all common representative points C (h), that is, the distance from the input vector in the vicinity table is the maximum value of the distance information of the record. If there is no common representative point shorter than (half the distance), the nearest neighbor vector search control unit 142 supplies the determination result to the in-group overall search unit 147, and the process proceeds to step S119.

  In step S119, the in-group entire search unit 147 searches for a vector (nearest neighbor vector) closest to the input vector from all member vectors in the group. Then, the entire group search unit 147 supplies the search result to the nearest neighbor vector setting unit 146, returns the process to step S118, and executes the subsequent processes.

  In this case, the nearest neighbor vector setting unit 146 sets the member vector searched by the overall group search unit 147 supplied as the search result in step S118 as the nearest neighbor vector, and sets the nearest neighbor vector to the nearest neighbor. This is supplied to the vector group search control unit 122, the nearest neighbor vector search process is terminated, the process returns to step S93 in FIG. 18, and the processes after step S94 are executed.

  As described above, the nearest neighbor vector search unit 123 sets the nearest neighborhood vector search range within the neighborhood vector or the entire vector group according to the distance between the input vector and the common representative point, and performs search processing within the search range. I do. In this way, when the input vector is close to one of the common representative points, specifically, the distance between the input vector and the common representative point is registered in the record of the common representative point in the neighborhood table. When there is a common representative point that is shorter than the maximum value of the distance information (one half of the distance between the common representative point and the neighborhood vector), the nearest neighborhood vector search unit 123 sets the search range of the nearest neighborhood vector as the common representative point. Since it can be limited to the neighborhood vectors of points, unnecessary candidates (member vectors that are not clearly nearest neighbor vectors) can be removed from the search range, and the nearest neighbor vectors can be searched at high speed.

  Further, by performing the processing as described above, only the group that needs to have all the member vectors of the vector group as the search range is subjected to the search processing for the entire vector group. For groups, it is possible to switch to search processing within the neighborhood vector. That is, even when there are a plurality of vector sets to be searched, the nearest neighbor vector search unit 123 can search a neighborhood vector of an input vector from each set at high speed without reducing the search accuracy. It is what you want to do.

  Next, details of the flow of the table search processing executed by the table search unit 145 (FIG. 11) in step S117 of FIG. 19 will be described with reference to the flowchart of FIG.

  First, when the intra-table search process is started, the initialization processing unit 161 (FIG. 12) of the intra-table search unit 145 sets the value of the variable k indicating the neighborhood vector to be processed to the initial value (step S131). For example, “0” is set, the nearest vector candidate Vkeep held by the data holding unit 165 is set to a virtual point at infinity from the input vector, or the distance from the nearest vector candidate Vkeep to the input vector An initialization process such as setting Dkeep to infinity is performed.

  In step S132, the in-table search control unit 162 determines whether or not all K neighborhood vectors Vt (k) (0 ≦ k ≦ K−1) included in the record have been searched. If it is determined that there is an unprocessed neighborhood vector Vt (k), the in-table search control unit 162 supplies the determination result to the distance calculation unit 163, and the process proceeds to step S133.

  In step S133, the distance calculation unit 163 calculates a distance Dint (k) between the input vector Vin and the neighborhood vector Vt (k) to be processed, supplies the calculation result to the update control unit 164, and the process proceeds to step S134. Proceed.

  In step S134, the update control unit 164 determines whether or not the distance Dint (k) is shorter than the distance Dkeep between the input vector Vin and the nearest neighbor vector candidate Vkeep. When it is determined that the distance Dint (k) is shorter than the distance Dkeep, the update control unit 164 supplies information on the processing target neighborhood vector Vt (k) and the distance Dint (k) to the data holding unit 165, and step S135. Proceed with the process. In step S135, the data holding unit 165 stores the information on the stored nearest neighbor vector candidate Vkeep and the distance Dkeep from the input vector, and the supplied neighborhood vector Vt (k) and distance Dint (k). Use to update.

  The update control unit 164 returns the control result to the in-table search control unit 162, and the process proceeds to step S136. If it is determined in step S134 that the distance Dint (k) is longer than the distance Dkeep between the input vector Vin and the held vector Vkeep, the update control unit 164 omits the process in step S135 and the control result thereof Is returned to the in-table search control unit 162, and the process proceeds to step S136.

  In step S136, the in-table search control unit 162 adds “+1” to the value of the variable k, changes the processing target neighborhood vector Vt (k), returns the processing to step S132, and sets a new processing target neighborhood vector Vt. The subsequent processing is repeated for (k).

  That is, the in-table search control unit 162, the distance calculation unit 163, the update control unit 164, and the data holding unit 165 search the table search control unit 162 for all neighboring vectors Vt (k) included in the record in step S132. The processing from step S132 to step S136 is repeated until it is determined that it has been performed.

  If it is determined in step S132 that all the neighboring vectors Vt (k) included in the record have been searched, the in-table search control unit 162 stores the nearest neighbor vector candidates Vkeep and the data holding unit 165. Information on the distance Dkeep from the input vector is supplied as a search result to the nearest neighbor vector setting unit 146, the table search process is terminated, the process returns to step S117 in FIG. 19, and the processes after step S118 are executed.

  Next, details of the flow of the entire group search process executed by the entire group searching unit 147 (FIG. 11) in step S119 of FIG. 19 will be described with reference to the flowchart of FIG.

  First, when the entire group search process is started, the initialization processing unit 181 (FIG. 13) of the group internal search unit 147 initializes the value of the variable i indicating the member vector to be processed in step S151. Set to a value (for example, “0”), set the nearest neighbor vector candidate Vkeep held by the data holding unit 185 to a virtual point at infinity from the input vector, or from the nearest neighbor vector candidate Vkeep input vector The initialization process such as setting the distance Dkeep to infinity is performed.

  In step S152, the in-group entire search control unit 182 determines whether or not processing has been performed for all N member vectors Vm (i, j) included in the group. If it is determined that there is an unprocessed member vector Vm (i, j), the in-group overall search control unit 182 supplies the determination result to the distance calculation unit 183, and the process proceeds to step S153.

  In step S153, the distance calculation unit 183 calculates the distance Dint (i) between the input vector Vin and the member vector Vm (i, j) to be processed, supplies the calculation result to the update control unit 184, and performs the processing step. Proceed to S154.

  In step S154, the update control unit 184 determines whether the distance Dint (i) is shorter than the distance Dkeep between the input vector Vin and the nearest neighbor vector candidate Vkeep. When it is determined that the distance Dint (i) is shorter than the distance Dkeep, the update control unit 184 supplies information on the processing target member vector Vm (i, j) and the distance Dint (i) to the data holding unit 185, The process proceeds to step S155. In step S155, the data holding unit 185 uses the supplied member vector Vm (i, j) and the distance Dint (i) as the information on the held nearest neighbor vector candidate Vkeep and the distance Dkeep from the input vector. Update using the information.

  The update control unit 184 returns the control result to the in-group overall search control unit 182 and advances the process to step S156. If it is determined in step S154 that the distance Dint (i) is longer than the input vector Vin, the nearest neighbor vector Vkeep held and the distance Dkeep from the input vector, the update control unit 184 performs the process of step S155. The control result is omitted, and the control result is returned to the in-table search control unit 182, and the process proceeds to step S156.

  In step S156, the in-table search control unit 162 adds “+1” to the value of the variable i, changes the processing target member vector Vm (i, j), returns the processing to step S152, and sets a new processing target member. The subsequent processing is repeated for the vector Vm (i, j).

  That is, the in-table search control unit 162, the distance calculation unit 163, the update control unit 164, and the data holding unit 165 are configured so that the in-table search control unit 162 includes all N member vectors Vm (i, j) The processing from step S152 to step S156 is repeated until it is determined that the search is performed for (0 ≦ i ≦ N−1).

  If it is determined in step S152 that all N member vectors Vm (i, j) included in the vector group have been searched, the intra-group entire search control unit 182 Information on the side vector Vkeep and the distance Dkeep from the input vector is supplied to the nearest neighborhood vector setting unit 146 as a search result, the entire group search process is terminated, the process returns to step S119 in FIG. Execute the process.

  As described above, the feature quantity comparison apparatus 10 in FIG. 1 calculates a representative point common to each vector group (model), creates a neighborhood table using the common representative point, and uses them to calculate an input vector. Since the nearest neighbor vector is searched, even if there are a plurality of search target vector sets, the neighborhood vector of the input vector can be searched from each set at high speed. That is, the feature quantity comparison apparatus 10 can search a target element from each set at high speed even when there are a plurality of sets to be searched.

  In the above, the constants N, M, R, K, etc. of each parameter are arbitrary natural numbers as long as there is no contradiction in the magnitude relationship between them, and may be values designated by the user in advance. It may be a predetermined value.

  In addition, the present invention may be any vector information as an input vector for searching the nearest neighbor vector or a member vector (model) to be searched, and may be applied to a search other than vector information, for example. it can. For example, the present invention can be applied to any search process that searches a target element from a set.

  In FIG. 1, the feature amount comparison device 10 has been described. However, the present invention can also be applied to a system including a plurality of devices. For example, the units of the feature amount comparison device 10 in FIG. You may make it comprise as a different apparatus. FIG. 22 is a diagram illustrating a configuration example of a feature amount comparison system to which the present invention is applied.

  22, the feature amount comparison system 200 includes a storage device 211, a common representative point setting device 212, a neighborhood table group creation device 214, and a nearest neighbor vector group search device 216. The feature amount comparison device in FIG. Processing similar to 10 is performed.

  The storage device 211 includes a vector information storage unit 11, a common representative point information storage unit 13, and a neighborhood table group storage unit 15, and stores the various types of information described above in the respective storage units.

  The common representative point setting device 212 corresponds to the common representative point setting unit 12 in FIG. 1, the neighborhood table group creation device 214 corresponds to the neighborhood table group creation unit 14 in FIG. 1, and the nearest neighborhood vector group search device 216 corresponds to FIG. Corresponding to the nearest neighbor vector group search unit 16 and the same processing is performed. Therefore, these descriptions are omitted.

  That is, even in the case of the feature quantity comparison system 200 configured by a plurality of devices in this way, the present invention can be applied as in the case of the feature quantity comparison device 10 of FIG. That is, the feature quantity comparison system 200 can search a target element from each set at high speed even when there are a plurality of sets to be searched.

  1 may be configured as a part of another device. For example, the feature amount comparison apparatus 10 may be configured as a part of an image processing apparatus that performs image recognition processing or the like.

  FIG. 23 is a block diagram illustrating a configuration example of an image processing apparatus to which the present invention has been applied. In FIG. 23, the image processing device 230 vectorizes the features of the input image and compares the feature vector with the feature vector of the model image, thereby detecting features common to (or approximate to) those images. A device for recognizing an input image.

  In FIG. 23, the image processing unit 230 includes a learning unit 231 and a recognition unit 232. The learning unit 231 is a processing unit that performs a process of registering a feature vector of a model image as a model dictionary, and includes a feature point extraction unit 241, a feature amount extraction unit 242, and a model dictionary registration unit 243.

  The feature point extraction unit 241 extracts a predetermined feature point determined in advance from the model image and supplies it to the feature amount extraction unit 242. The feature amount extraction unit 242 extracts feature amounts of the feature points extracted by the feature point extraction unit 241, and registers them as feature vectors in the model dictionary registration unit 243.

  When the input image is input, the recognition unit 232 extracts the feature vector, compares it with the feature vector of the model image, and determines a portion that matches (approximates) the model. An extraction unit 244, a feature amount extraction unit 245, a feature amount comparison unit 246, and a model detection determination unit 247 are included.

  The feature point extraction unit 244 extracts a predetermined feature point determined in advance from the input image and supplies it to the feature amount extraction unit 245. The feature amount extraction unit 245 extracts the feature amount of the feature point extracted by the feature point extraction unit 244 and supplies it to the feature amount comparison unit 246. The feature amount comparison unit 246 has the same configuration as that of the feature amount comparison device 10 in FIG. 1, and is registered in the model dictionary registration unit 243 by executing the same processing as the feature amount comparison device 10 in FIG. 1. The feature vector of the model image that has been input is compared with the feature vector of the input image, and the comparison result is supplied to the model detection determination unit 247. The model detection / determination unit 247 determines whether or not the feature of the input image has been detected in the model image based on the comparison result, and outputs the determination result to the outside of the apparatus as a recognition processing result.

  As described above, the feature quantity comparison apparatus 10 of FIG. 1 may be used as the feature quantity comparison unit 246 and used for the feature vector comparison processing of the image processing apparatus 230. Also in this case, the feature quantity comparison unit 246 executes the same process as each process in the feature quantity comparison apparatus 10 described above.

  Further, at this time, a processing unit similar to each unit (FIG. 1) of the feature quantity comparison device 10 may be configured as other than the feature quantity comparison unit 246. FIG. 24 is a block diagram illustrating another configuration example of the image processing device 230 in FIG.

  In the case of FIG. 24, the image processing apparatus 250 includes a learning unit 251 and a recognition unit 252 as in the image processing apparatus 230 of FIG. The learning unit 251 includes a model dictionary registration unit 263, a common representative point setting unit 12, and a neighborhood table group creation unit 14 instead of the model dictionary registration unit 243 of the learning unit 231. The model dictionary registration unit 263 includes a vector information storage unit 11, a common representative point information storage unit 13, and a neighborhood table group storage unit 15 in addition to the function of the model dictionary registration unit 243.

  The recognition unit 252 includes a nearest neighbor vector group search unit 16 instead of the feature amount comparison unit 246 of the recognition unit 232.

  That is, in the case of the image processing device 230 in FIG. 23, the recognition unit 232 includes the feature amount comparison unit 246 corresponding to the feature amount comparison device 10 in FIG. 1, and in the case of the image processing device 250 in FIG. 252 has only the nearest neighbor vector group search unit 16 of the feature quantity comparison device 10 of FIG. 1, and other configurations (vector information storage unit 11, common representative point setting unit 12 of the feature quantity comparison device 10 of FIG. The learning unit 251 includes the common representative point information storage unit 13, the neighborhood table group creation unit 14, and the neighborhood table group storage unit 15).

  As described above, how each unit of the feature quantity comparison device 10 can be processed by the image processing device 230 as long as the processing content or the like thereof does not substantially change (as long as the processing amount is configured to correspond to the feature quantity comparison device 10). You may make it comprise.

  Moreover, you may make it combine the structure of the feature-value comparison of this invention demonstrated above with another technique. For example, in order to further facilitate the processing of the member vector group, a coordinate conversion process using principal component analysis may be applied to the above-described feature amount comparison process.

  FIG. 25 is a block diagram illustrating another configuration example of the feature amount comparison apparatus. A feature value comparison device 280 in FIG. 25 is configured to apply a coordinate conversion process using principal component analysis to the feature value comparison process by the feature value comparison device 10 in FIG. 11, member vector coordinate conversion unit 281, input vector coordinate conversion unit 282, nearest neighbor vector group coordinate conversion unit 283, conversion coordinate vector information storage unit 291, conversion coordinate common representative point setting unit 292, conversion coordinate common representative point information storage unit 293, a conversion coordinate neighborhood table group creation unit 294, a conversion coordinate neighborhood table group storage unit 295, and a conversion coordinate nearest neighbor vector group search unit 296.

  The member vector coordinate conversion unit 281 performs principal component analysis based on the vector information stored in the vector information storage unit 11 as described later, and converts the coordinates of each member vector. The member vector coordinate transformation unit 281 supplies the vector information (transformed coordinate vector information) on the transformed coordinates after the coordinate transformation to the transformed coordinate vector information storage unit 291 for storage. The member vector coordinate conversion unit 281 supplies information related to the principal component analysis result to the input vector coordinate conversion unit 282.

  The input vector coordinate conversion unit 282 performs the same coordinate conversion processing on the input vector as the member vector coordinate conversion unit 281 based on the information on the principal component analysis result supplied from the member vector coordinate conversion unit 281, and the coordinates The converted input vector on the converted coordinate (converted coordinate input vector) is supplied to the converted coordinate nearest neighbor vector group search unit 296. Further, the input vector coordinate conversion unit 282 supplies information on the principal component analysis result to the nearest neighbor vector group coordinate conversion unit 283.

  When the nearest neighbor vector group coordinate conversion unit 283 acquires the nearest neighbor vector group (transformed coordinate nearest neighbor vector group) on the transformed coordinate supplied from the transformed coordinate nearest neighbor vector group search unit 296, the nearest neighbor vector group coordinate transformation unit 283 receives from the input vector coordinate transformation unit 282. Based on the supplied information on the principal component analysis result, a coordinate conversion process corresponding to the input vector coordinate conversion unit 282 is performed on the acquired converted coordinate nearest neighbor vector group, and the converted coordinate nearest neighbor vector group is converted into the original coordinates. The system is converted into a system (coordinate system of vector information stored in the vector information storage unit 11), and the nearest neighbor vector group of the original coordinate system is output to the outside of the feature quantity comparison device 280.

  Conversion coordinate vector information storage unit 291, conversion coordinate common representative point setting unit 292, conversion coordinate common representative point information storage unit 293, conversion coordinate neighborhood table group creation unit 294, conversion coordinate neighborhood table group storage unit 295, and conversion coordinate nearest neighbor The vector group search unit 296 includes the vector information storage unit 11, the common representative point setting unit 12, the common representative point information storage unit 13, the neighborhood table group creation unit 14, the neighborhood table group 15, and the nearest neighborhood vector group shown in FIG. It corresponds to the search unit 16 and performs the same processing as these except for processing on the converted coordinates. Therefore, the description is omitted.

  Next, coordinate transformation using principal component analysis will be described with reference to FIG. FIG. 26A shows an example of the distribution of feature vectors 22 (member vectors) in the vector group 21-1. As shown in FIG. 26A, it is assumed that the feature vectors 22 of the vector group 21-1 are distributed on the plane indicated by the x-coordinate and the y-coordinate. Since the feature vector 22 is a vector indicating a predetermined feature such as image information, for example, the distribution of the feature vector 22 is not uniform, and there is a high possibility that a predetermined bias occurs. For example, when an edge portion of an image is extracted as a feature point, each feature vector 22 includes the feature of the edge portion. That is, since any feature vector 22 includes the same or similar features, the distribution of the feature vectors 22 is also biased.

  Therefore, the distribution of the feature vectors 22 has a direction in which each feature vector 22 is distributed in the widest range (that is, a direction having the highest contribution ratio to the distribution). The direction with the highest contribution rate is referred to as the main component.

  The feature quantity comparison device 280 in FIG. 25 analyzes the principal component from the distribution of the member vectors, and converts the coordinates of the member vector into coordinates having the principal component as an axis, as shown in FIG. 26B.

  That is, as shown in FIG. 26A, the feature quantity comparison device 280 converts the coordinates of the feature vector 22 distributed in the coordinate system indicated by the x coordinate and the y coordinate to the x ′ coordinate that is the main component of the feature vector 22 and Convert to a coordinate system indicated by y ′ coordinates perpendicular to x ′ coordinates. FIG. 26B shows the distribution of the feature vector 22 after coordinate conversion.

  By this coordinate transformation, as shown in FIG. 26A, the distribution of the feature vector 22 that is almost the same as the range a in the x coordinate direction and the range b in the y coordinate direction, as shown in FIG. It changes to a ′ in the x ′ coordinate direction and b ′ in the y ′ coordinate direction (a ′ >> b ′). That is, the distribution of the feature vector 22 is biased in the x ′ coordinate direction by coordinate conversion.

  By performing the principal component analysis and converting the coordinates in this way, the feature amount comparison apparatus 280 omits the distribution in the direction in which the contribution rate is low with respect to the distribution of the member vectors, for example, as illustrated in FIG. Dimensional compression is possible. For example, when a group of feature vectors 22 distributed almost in series in the x′-axis direction as shown in FIG. 27A is a member vector of the vector group 21-1, if the feature vector 22 is coordinate-transformed as shown in FIG. It can be seen that 22 is distributed only in the x ′ coordinate direction, which is the main component, and hardly distributed in the y ′ coordinate direction perpendicular to the x ′ coordinate. In such a case, the feature quantity comparison apparatus 280 omits the distribution in the y′-axis direction whose contribution ratio to the distribution is overwhelmingly smaller than the main component, and all the feature vectors 22 are on the x′-axis (1 Dimensional)). That is, in this case, the feature quantity comparison device 280 dimensionally compresses the distribution of the feature vector 22 from two dimensions to one dimension. By dimensionally compressing the feature vector distribution in this way, the feature quantity comparison device 280 can reduce the order of the arithmetic expression, for example, in the calculation of the distance between vectors, and can reduce the calculation quantity. That is, the feature quantity comparison apparatus 280 can perform high-speed processing by reducing the load of the nearest neighbor vector search process by performing such dimension compression.

  In addition to dimensional compression, the feature quantity comparison device 280 performs the principal component analysis in this way and performs coordinate transformation, for example, as shown in FIG. Vector search can be performed at high speed.

  In the nearest neighbor vector search, as described above, the feature quantity comparison device 280 calculates the distance to the input vector one by one for each member vector in the search range, and the distance is the shortest. Let be the recent bar vector. Specifically, the feature quantity comparison device 280 first holds a point where the distance Dkeep from the input vector is infinite as an initial value of the nearest neighbor vector candidate Vkeep. Then, the feature quantity comparison device 280 calculates the distance between all the member vectors in the search range and the input vector one by one, and if the calculated distance is shorter than the held distance Dkeep, the nearest neighbor vector candidate Update the distance Dkeep from Vkeep and its input vector. The feature quantity comparison device 280 repeats such processing, and finally sets a candidate (keep held after processing all member vectors) Vkeep as a nearest neighbor vector.

  That is, in the vector group 21 as shown in FIG. 28A, when the feature vector 22A is held as the nearest neighbor vector candidate Vkeep with respect to the input vector 27, the feature quantity comparison device 280 first inputs the feature vector 22B. The distance from the vector 27 is calculated and compared with the distance between the feature vector 22A and the input vector 27. When the feature vector 22A is closer to the input vector 27, the feature quantity comparison device 280 next calculates the distance between the feature vector 22C and the input vector 27, and calculates the distance between the feature vector 22A and the input vector 27. Compare. Similarly, if the feature vector 22A is closer to the input vector 27, the feature amount comparison device 280 next calculates the distance between the feature vector 22D and the input vector 27, and calculates the distance between the feature vector 22A and the input vector 27. Compare with distance. In this way, the feature quantity comparison device 280 calculates the distance between the feature vector and the input vector one by one, and compares it with the distance between the current nearest neighbor vector candidate and the input vector. If a member vector closest to the input vector is newly searched, the feature quantity comparison device 280 sets the member vector as a new nearest neighbor vector candidate and holds the information.

  The distance between the vectors calculated at this time is represented by the square root of the sum of the squares of the differences between the coordinate components of the two points, as represented by Expression (1). Since the square of the difference between the coordinate components is always a positive value, the absolute value of the difference between the two distances (which feature vector is closer to the input vector) is determined by the sum of the positive values. . That is, for example, when calculating the distance between two points and comparing the magnitude with a certain reference distance, if the square of the difference between the coordinate components of the two points is greater than the square of the reference distance, The distance between the points is always longer than the reference distance.

  Therefore, when calculating the distance between the member vector and the input vector, the difference is calculated and added in order from the square of the component having a high contribution rate (a term having a relatively large value), and the nearest neighbor is added each time the addition is performed. By comparing with the square of the distance Dkeep from the input vector of the vector candidate Vkeep, the feature quantity comparison device 280 is configured to add (the difference 2 of the component with a low contribution ratio to the second) when the addition result exceeds the square of the distance Dkeep. Since the member vector cannot be a candidate of the nearest neighbor vector (even if a value with a relatively small value) is not added), the distance calculation for the member vector is stopped and the distance calculation for the next member vector is stopped. Can be migrated to.

  In other words, when calculating the distance between the member vector and the input vector, the feature amount comparison apparatus 280 adds the squares of the differences between the components of the coordinates of the two points in descending order of the contribution rate. The addition result is like a curve shown in FIG. 28B. In other words, the feature quantity comparison device 280 is provided with a bias for each component in the distribution of the feature vector 22 and performs the addition as described above. The possibility of exceeding the value of the candidate distance (Dkeep) is increased, and the possibility that the calculation can be omitted increases.

  Therefore, each time the square of the component difference is added, by comparing the addition result with the value of the distance (Dkeep) that is held, the feature amount comparison device 280 can calculate the calculation amount of the distance calculation. It is possible to search for the nearest neighbor vector efficiently and to search for the nearest neighbor vector of the input vector at high speed.

  Next, a detailed configuration example of the feature amount comparison apparatus 280 in FIG. 25 will be described. FIG. 29 is a block diagram illustrating a detailed configuration example of the member vector coordinate conversion unit 281 of FIG. 29, the member vector coordinate conversion unit 281 has a vector group unification unit 311, a principal component analysis unit 312, a coordinate conversion unit 313, a dimension compression unit 314, and a conversion coordinate vector information storage control unit 315.

  The vector group unification unit 311 unifies vector groups based on the vector information acquired from the vector information storage unit 11, generates one vector group, and supplies the information to the principal component analysis unit 312.

  The principal component analysis unit 312 performs a principal component analysis of the member vector distribution and supplies the analysis result to the coordinate conversion unit 313. The coordinate conversion unit 313 performs coordinate conversion of each member vector into a coordinate system having the principal component as a coordinate axis based on the supplied analysis result, and supplies the conversion result to the dimension compression unit 314. The dimension compression unit 314 performs dimension compression on the distribution of the member vectors on the converted coordinates as necessary, and supplies the processing result to the converted coordinate vector information storage control unit 315. The conversion coordinate vector information storage control unit 315 supplies the conversion coordinate vector information, which is vector information of the member vector on the supplied conversion coordinates, to the conversion coordinate vector information storage unit 291 and stores it.

  Next, the flow of the feature amount comparison process executed by the feature amount comparison apparatus 280 will be described with reference to the flowchart of FIG.

  When the feature amount comparison process is started, the member vector coordinate conversion unit 281 analyzes the principal components of the distribution of all member vectors based on the vector information supplied from the vector information storage unit 11 in step S171, and the analysis. Each member vector is coordinate-transformed based on the result. Details of the member vector coordinate conversion processing will be described later.

  In step S172, when the conversion coordinate common representative point setting unit 292 acquires the conversion coordinate vector information from the conversion coordinate vector information storage unit 291, the common representative point (conversion coordinate) on the conversion coordinate based on the vector information on the conversion coordinate. Set a common representative point. The conversion coordinate common representative point setting process is the same as the common representative point setting process described with reference to the flowchart of FIG.

  In step S173, the converted coordinate neighborhood table group creation unit 294 generates the vector information on the converted coordinates acquired from the converted coordinate vector information storage unit 291 and the common on the converted coordinates acquired from the converted coordinate common representative point information storage unit 293. Based on the representative points, a neighborhood table group (transformed coordinate neighborhood table group) on the transformed coordinates is created. The conversion coordinate neighborhood table group creation process is the same as the neighborhood table group creation process described with reference to the flowchart of FIG.

  In step S174, the input vector coordinate conversion unit 282 determines whether or not an input vector has been input. If it is determined that the input vector has been input, the input vector coordinate conversion unit 282 relates to the principal component analysis result supplied from the member vector coordinate conversion unit 281 in step S175. Based on the information, the coordinates of the input vector are converted, and the input vector on the conversion coordinate (converted coordinate input vector) is supplied to the converted coordinate nearest neighbor vector group search unit 296.

  In step S176, the converted coordinate nearest neighbor vector search unit 296 searches for the nearest neighbor vector group (converted coordinate nearest neighbor vector group) of the supplied converted coordinate input vector on the converted coordinate. Since this converted coordinate nearest neighbor vector search process is the same as the nearest neighbor vector group search process described with reference to the flowchart of FIG. 18 except that it is on the converted coordinates, detailed description thereof is omitted. The converted coordinate nearest neighbor vector search unit 296 that has searched for the converted coordinate nearest neighbor vector group supplies the converted coordinate nearest neighbor vector search unit 296 to the nearest neighbor vector group coordinate conversion unit 283, and advances the process to step S177.

  In step S177, the nearest neighbor vector group coordinate conversion unit 283 converts the coordinates of each converted coordinate nearest neighbor vector into the original coordinate system based on the information on the principal component analysis result supplied from the input vector coordinate conversion unit 282. . The nearest neighbor vector group coordinate conversion unit 283 outputs the converted nearest neighbor vector group (the nearest neighbor vector group of the original coordinate system) to the outside of the feature quantity comparison device 280 as a feature quantity comparison result, and the process is performed in step S178. Proceed to

  If it is determined in step S174 that no input vector is input, the input vector coordinate conversion unit 282 advances the process to step S178. In step S178, the nearest neighbor vector group coordinate conversion unit 283 determines whether or not to end the feature amount comparison process. If it determines not to end the process, the process returns to step S174, and the subsequent processes are repeated. .

  If it is determined in step S178 that the feature amount comparison process is to end based on, for example, a user instruction, the nearest neighbor vector group coordinate conversion unit 283 ends the feature amount comparison process.

  Next, details of the flow of the member vector coordinate transformation process executed in step S171 of FIG. 30 will be described with reference to the flowchart of FIG.

  When the member vector coordinate conversion process is started, the vector group unification unit 311 (FIG. 29) of the member vector coordinate conversion unit 281 executes all vector groups based on the vector information supplied from the vector information storage unit 11 in step S191. Are generated, one vector group including all or part of the member vectors of each vector group is generated, the information is supplied to the principal component analysis unit 312, and the process proceeds to step S192.

  In step S192, the principal component analysis unit 312 performs principal component analysis of all member vectors, supplies the analysis result to the coordinate conversion unit 313, and advances the processing to step S193. In step S193, the coordinate conversion unit 313 converts the coordinates of all member vectors based on the analysis result, supplies the conversion result to the dimension compression unit 314, and advances the processing to step S194. In step S194, the dimension compression unit 314 determines whether or not to perform dimension compression on the supplied transformed coordinate member vector based on, for example, a user instruction and the like. If it is determined to perform the process, the process proceeds to step S195. Then, dimension compression processing is performed from a dimension (coordinate) having a low contribution rate to the distribution of the converted coordinate member vector, and the distribution of the converted coordinate member vector is dimensionally compressed to a desired number of dimensions. When the process of step S195 ends, the dimension compression unit 314 supplies the processing result to the converted coordinate vector information storage control unit 315, and the process proceeds to step S196.

  If it is determined in step S194 that the dimension compression is not performed, the dimension compression unit 314 omits the process in step S195, and without performing the dimension compression process, the vector information of the converted coordinate member vector is directly used as the converted coordinate vector. The information is supplied to the information storage control unit 315, and the process proceeds to step S196.

  In step S196, the conversion coordinate vector information storage control unit 315 supplies the supplied conversion coordinate vector information to the conversion coordinate vector information storage unit 291 (FIG. 25) and stores it. The converted coordinate vector information storage unit 291 stores the converted coordinate vector information supplied from the converted coordinate vector information storage control unit 315.

  When the process of step S196 ends, the converted coordinate vector information storage control unit 315 ends the member vector coordinate conversion process, returns the process to step S171 of FIG. 30, and executes the subsequent processes.

  As described above, by analyzing the principal components of the distribution of member vectors, performing coordinate conversion of each vector based on the analysis result, and comparing feature quantities on the converted coordinates, the feature quantity comparison device 280 The neighborhood vector of the input vector can be searched from each set at higher speed. That is, the feature quantity comparison apparatus 280 can search for a target element from each set at a higher speed even when there are a plurality of sets to be searched.

  In the above, the comparison processing of one type of feature vector has been described. However, the number of types of feature vectors to be compared (the types of coordinate components constituting the vectors) may be any number, and may be plural. That is, a plurality of feature vectors existing in different spaces may be compared with the same model. When there are a plurality of types of feature vectors to be compared, the number of dimensions of each feature vector may be different from each other.

  However, in this case, the comparison processing as described above may be performed for each feature vector. However, the comparison processing result of the first type of feature vector is used for the comparison processing of the feature vector to be compared next. The feature amount comparison apparatus may be configured to perform the search process at a higher speed.

  FIG. 32 is a schematic diagram illustrating an example of a flow of processing when comparing a plurality of types of feature vectors.

  In FIG. 32, a feature quantity (model feature quantity 332) is extracted for each model stored in one model dictionary 331 (uppermost stage) (second stage from the top), and for each type of model feature quantity 332 A vector map is constructed (third level from the top). In FIG. 32, a 36-dimensional vector map construction 333-1 (left side in the third stage from the top) of the feature quantity 1 and an 18-dimensional vector map construction 333-2 (right side in the third stage from the top) of the feature quantity 2 are performed. Then, when the input vector 334 (left side of the lowermost stage) is input, a search for a similar pair group 335 of the feature quantity 1 of the input vector 334 is performed on the 36-dimensional vector map of the feature quantity 1 (four stages from the top). Left side)

  The 36-dimensional vector map of the feature quantity 1 is constructed using, for example, the common representative points and the neighborhood table as described above. In this case, the search 335 for the similar pair group of the feature quantity 1 is performed as shown in FIG. It is performed by the same method as the nearest neighbor vector search process described above with reference to FIG. That is, in the similar pair group search 335 of the feature quantity 1, an infinite point is set as the initial value of the nearest neighbor vector candidate, and the distances between all the member vectors in the search range and the input vector are calculated one by one. Each time the nearest member vector is retrieved from the input vector, the nearest neighbor vector candidate is updated to that member vector. Such search processing is repeated to obtain the nearest neighbor vector in the vector group.

  Then, the similar pair group of feature quantity 1 obtained as a search result of the similar pair group search 335 of feature quantity 1 is used as the initial value 336 (fourth center from the top), and the similarity of feature quantity 2 A pair group search 337 is performed (right side of the fourth row from the top). By performing the search process according to such a procedure, the search result of the similar pair group search 337 of the feature quantity 2 becomes the neighborhood vector 338 of the input vector in both the feature quantity 1 and the feature quantity 2 (in the two types of feature quantities). Vector approximating the input vector).

  When a search is performed from a point at infinity as in the search 335 for a similar pair group of feature amount 1, all member vectors can be candidates for the nearest neighbor vector. Therefore, in the case of such a search, the amount of calculation in the nearest neighbor vector search by the feature quantity comparison device becomes relatively large. On the other hand, when a search is performed from a predetermined point, such as the search 337 for a similar pair group of feature amount 2, the feature amount comparison device clearly has a far point that is not a nearest neighbor vector (distant from the predetermined point). The calculation for point) can be omitted.

  In FIG. 32, since the feature quantity comparison device searches for a member vector that is a neighborhood vector of the input vector in both feature quantity 1 and feature quantity 2, it does not become a neighborhood vector in the search 335 of a similar pair group of feature quantity 1. The member vector does not need to be a search target in the search 337 of the similar pair group of the feature amount 2. Therefore, as described above, by using the search result in the similar pair group search 335 of the feature quantity 1 as the initial value of the search 337 of the similar pair group of the feature quantity 2, the feature quantity comparison apparatus can detect the similarity of the feature quantity 2. The calculation amount in the pair group search 337 can be reduced.

  Further, by comparing the feature quantities in this way, the feature quantity comparison device performs a similar pair search of the feature quantity 1 and a similar pair search of the feature quantity 2 independently of each other, and compares the search results again. The feature quantity 1 and the feature quantity 2 can be obtained only by performing the search 335 of the similar pair group of the feature quantity 1 and the search 337 of the similar pair group of the feature quantity 2 without requiring a complicated process of extracting pairs satisfying both. The neighborhood vector 338 of the input vector in both can be searched, and the total calculation amount can be reduced.

  That is, by performing such a search, the feature amount comparison apparatus, for example, in image recognition using a feature vector, when detecting a nearest neighbor vector with respect to an input vector that is nearest to a plurality of evaluation criteria, The neighborhood search with the evaluation criteria is permuted, and when a neighborhood vector closer to the nearest neighborhood vector is detected by the neighborhood calculation in the previous stage, it is determined that there is no nearest neighborhood vector that is the nearest neighborhood based on multiple assessment criteria. Therefore, by interrupting the neighborhood search, it is possible to quickly search for a neighborhood vector (nearest neighbor search based on a plurality of evaluation criteria) of an input vector that satisfies a plurality of conditions. That is, this feature quantity comparison apparatus can search a target element satisfying a plurality of conditions from a set at high speed.

  Hereinafter, an example of an apparatus to which such a feature amount comparison method is applied will be described.

  FIG. 33 is a diagram illustrating another configuration example of the image processing apparatus to which the present invention has been applied.

  In FIG. 33, the image processing device 350 includes a learning unit 351 and a recognition unit 352. The learning unit 351 is a processing unit that prepares the features of a model image to be compared for feature amounts in advance, and includes a plurality of types of feature point extraction unit 361, a plurality of types of feature amount extraction unit 362, and a model dictionary registration unit 363. ing.

  The multiple-type feature point extraction unit 361 extracts multiple types of feature points from the input model image, and supplies them to the multiple-type feature amount extraction unit 362. Note that the multi-type feature point extraction unit 361 is the same as the feature point extraction unit 241 in FIG. 23 except that there are a plurality of types of feature points to be extracted from the model image (for example, the method for extracting each feature point). Since there is, detailed description thereof is omitted.

  The multi-type feature quantity extraction unit 362 extracts the feature quantity of each feature point extracted by the multi-type feature point extraction unit 361 from the model image, and supplies it to the model dictionary registration unit 363 as a model feature quantity. Note that the multi-type feature quantity extraction unit 362 performs the feature quantity shown in FIG. 23 except that there are a plurality of types of feature points for extracting feature quantities from the model image (for example, a feature quantity extraction method for each feature point). Since it is the same as that of the extraction part 242, the detailed description is abbreviate | omitted.

  The model dictionary registration unit 363 registers and holds the model feature quantity group 332 supplied from the plural types of feature quantity extraction unit 362 in the model dictionary. In addition, the model dictionary registration unit 363 supplies the model feature amount group 332 to the multiple types feature amount comparison unit 366 of the recognition unit 352 as necessary. The model dictionary registration unit 363 is the same as the model dictionary registration unit 243 in FIG. 23 except that there are a plurality of types of model feature values to be held (for example, for each model feature value holding method). Detailed description is omitted.

  The recognition unit 352 is a processing unit that recognizes an input image by comparing the feature vector of the input image with the feature vector of the model image registered in the model dictionary in the learning unit 351 as described above. A feature point extraction unit 364, a feature amount extraction unit 365, a plurality of types of feature amount comparison unit 366, and a model detection determination unit 367 are provided.

  The feature point extraction unit 364 extracts predetermined feature points from the input image that has been input, and supplies the feature points and the input image to the feature amount extraction unit 365. The feature point extraction unit 364 has basically the same configuration as the feature point extraction unit 244 in FIG. 23 and performs the same processing, and thus detailed description thereof is omitted.

  The feature amount extraction unit 365 extracts the feature amount of the feature point extracted by the feature point extraction unit 364, and supplies information regarding the feature amount to the multiple types feature amount comparison unit 366. Since the feature quantity extraction unit 365 has basically the same configuration as the feature quantity extraction unit 245 of FIG. 23 and performs the same processing, a detailed description thereof will be omitted.

  The multi-type feature quantity comparison unit 366 has a model feature quantity group in which the model dictionary registration unit 363 holds a feature vector (input vector) of the input image based on the feature quantity of the input image supplied from the feature quantity extraction unit 365. Compared with 332, by searching for a member vector that is a neighborhood vector of the input vector for all of a plurality of types of feature points, the feature of the input image is compared with the feature of the model image, and the comparison result is used as a model detection determination unit. 367. Details of the multiple-type feature amount comparison unit 366 will be described later.

  The model detection determination unit 367 determines whether or not the feature of the model image has been detected from the input image based on the comparison result in the plural types of feature amount comparison unit 366. The model detection / determination unit 367 has basically the same configuration as the model detection / determination unit 247 in FIG. 23 and performs the same processing, and thus detailed description thereof is omitted.

  FIG. 34 is a block diagram illustrating a detailed configuration example of the plural types of feature amount comparison unit 366 of FIG.

  33, a plurality of types of feature quantity comparison unit 366 includes a feature quantity information acquisition unit 381, a vector information storage unit 391, a common representative point setting unit 392, a common representative point information storage unit 393, a neighborhood table group creation unit 394, and a neighborhood table. A group storage unit 395 and a neighborhood vector group search unit 396 are provided.

  The feature amount information acquisition unit 381 acquires feature amount information for specifying the type of feature point to be compared from the outside (for example, user input), and uses it as necessary, a common representative point setting unit 392, a neighborhood table group The data is supplied to the creation unit 394 and the neighborhood vector group search unit 396.

  The vector information storage unit 391, the common representative point setting unit 392, the common representative point information storage unit 393, the neighborhood table group creation unit 394, and the neighborhood table group storage unit 395 perform processing on each of a plurality of types of feature vectors. 1 correspond to the vector information storage unit 11, the common representative point setting unit 12, the common representative point information storage unit 13, the neighborhood table group creation unit 14, and the neighborhood table group storage unit 15 of FIG. Process. Therefore, description of these details is omitted.

  The neighborhood vector group search unit 396 is based on the vector information acquired from the vector information storage unit 391, the common representative point information acquired from the common representative point information storage unit 393, and the neighborhood table group acquired from the neighborhood table group storage unit 395. Then, a neighborhood vector group for the inputted input vector group is searched. Then, the neighborhood vector group search unit 396 supplies the neighborhood vector group that is the search result to the model detection determination unit 367 (FIG. 33).

  FIG. 35 is a block diagram illustrating a detailed configuration example of the neighborhood vector group search unit 396 in FIG. 36, the neighborhood vector group search unit 396 includes an initialization processing unit 411, a neighborhood vector group search control unit 412, a neighborhood vector search unit 413, a feature-specific neighborhood vector candidate setting unit 414, a change flag confirmation unit 415, and a neighborhood vector. A setting unit 416 is provided.

  The initialization processing unit 411 performs initialization processing such as setting a variable necessary for searching for a neighborhood vector group to an initial value. For example, the initialization processing unit 411 initializes a feature-specific neighborhood vector candidate that is a candidate for a feature-specific neighborhood vector that is a neighborhood vector corresponding to one input vector, or sets a variable j (0 ≦ j ≦ M−1). It is set to an initial value (for example, “0”), or a feature-specific neighborhood vector candidate change flag is initialized. The change flag will be described later.

  The neighborhood vector group search control unit 412 performs control processing related to the search for neighborhood vector groups that satisfy the conditions for all types of features set as search targets. The neighborhood vector search unit 413 searches for feature-specific neighborhood vectors for each input vector input. At this time, as described with reference to FIGS. 1 to 21, the neighborhood vector search unit 413 calculates the distance between the input vector and the model member vector one by one, and is shorter than the feature-specific neighborhood vector candidates. When the member vector is searched, the information on the feature-specific neighborhood vector candidates is updated, and the member vector is set as a new feature-based neighborhood vector candidate. The neighborhood vector search unit 413 repeats the processing as described above, and finally sets the feature-specific neighborhood vector candidates as feature-specific neighborhood vectors (search results).

  The feature-specific neighborhood vector candidate setting unit 414 sets the previous search result (feature-specific neighborhood vector) by the neighborhood vector search unit 413 as the initial value of the feature-specific neighborhood vector candidate in the next search. The feature-specific neighborhood vector search unit 414 performs feature-specific neighborhood vector search for a new input vector using the feature-specific neighborhood vector candidates.

  Further, when the candidate is updated in the search for the feature-specific neighborhood vector, the neighborhood vector search unit 413 sets a change flag indicating the update. The neighborhood vector candidate setting unit 414 supplies the change flag information to the change flag confirmation unit 415.

  The change flag confirmation unit 415 confirms the state of each supplied change flag and supplies the confirmation result to the neighborhood vector group search control unit 412. The change flag is a flag indicating that the neighborhood vector candidate has changed, and is provided for each candidate. That is, a candidate with a change flag is a candidate that has been updated at least once.

  The neighborhood vector group search control unit 412 controls the neighborhood vector group search process based on the confirmation result. For example, when there are no more invariant feature-specific neighborhood vector candidates, the neighborhood vector group search control unit 412 finishes the neighborhood vector group search process, and controls each unit to search for the next vector group. Transition. For example, when the neighborhood vector search unit 413 finishes searching for feature-specific neighborhood vectors for all input vectors and there is an invariant feature-specific neighborhood vector candidate for which no change flag is set, the feature-specific neighborhood The vector (candidate) is supplied to the neighborhood vector setting unit 416.

  The neighborhood vector setting unit 416 is controlled by the neighborhood vector group search control unit 412 to set the feature-specific neighborhood vector (candidate) that has not changed as a neighborhood vector (group).

  Next, the flow of the multiple-type feature quantity comparison process executed by the multiple-type feature quantity comparison unit 366 (FIG. 34) of the image processing apparatus 350 (FIG. 33) will be described with reference to the flowchart of FIG.

  When the multi-type feature quantity comparison process is started, the feature quantity information acquisition unit 381 of the multi-type feature quantity comparison unit 366 compares the feature quantity (feature vector) in step S211 using the model dictionary registration unit 363, user input, or the like. Get information about. The feature amount information acquisition unit 381 supplies the acquired information to the common representative point setting unit 392 and the neighborhood table group creation unit 394, and the process proceeds to step S212.

  In step S212, the common representative point setting unit 392 determines the feature amount based on the vector information acquired from the vector information storage unit 391 (vector information supplied from the model dictionary registration unit 363 and stored in the vector information storage unit 391). A common representative point is set for each type (for each type of feature vector). When the common representative point setting unit 392 sets the common representative point, the common representative point setting unit 392 supplies the common representative point to the common representative point information storage unit 393 for storage, and the process proceeds to step S213.

  In step S213, the neighborhood table group creation unit 394 obtains vector information acquired from the vector information storage unit 391 (vector information supplied from the model dictionary registration unit 363 and stored in the vector information storage unit 391), and common representative point information. Based on the common representative point information acquired from the storage unit 393 (common representative point set by the processing in step S212), a neighborhood table is created for each type of feature amount (for each type of feature vector). When the neighborhood table group creation unit 394 creates the neighborhood table, the neighborhood table group creation unit 394 supplies the neighborhood table to the neighborhood table group storage unit 395 and stores it, and the process proceeds to step S214.

  In step S214, the neighborhood vector group search unit 396 stores the vector information acquired from the vector information storage unit 391 (vector information supplied from the model dictionary registration unit 363 and stored in the vector information storage unit 391), and common representative point information storage. Based on the common representative point information acquired from the unit 393 (common representative point set by the processing in step S212) and the neighborhood table group obtained from the neighborhood table group storage unit 395, the neighborhood corresponding to the input vector group input Search for vectors. Details of the neighborhood vector group search process will be described later. When the neighborhood vector group search unit 396 searches for the neighborhood vector group, the neighborhood vector group is supplied as a search result to the model detection determination unit 367 (FIG. 33), and the multiple-type feature amount comparison process ends.

  Next, the flow of the neighborhood vector group search process executed in step S214 of FIG. 36 will be described with reference to the flowchart of FIG.

  When the neighborhood vector group search process is started, the initialization processing unit 411 of the neighborhood vector group search unit 396 performs the initialization process in step S241, and sets the feature-specific neighborhood vector candidate as an initial value at a point at infinity. In addition, the setting of the change flag is initialized, or the value of the variable j indicating the vector group to be processed is set to an initial value (for example, “0”). When the initialization process ends, the initialization processing unit 411 supplies the processing result to the neighborhood vector group search control unit 412 and advances the process to step S242.

  In step S242, the neighborhood vector group search control unit 412 determines whether or not the neighborhood vector group of the input vector group has been searched for all vector groups, and if it is determined that there is an unsearched vector group, the determination result Is supplied to the neighborhood vector search unit 413, and the process proceeds to step S243.

  In step S243, the neighborhood vector search unit 413 searches for feature-specific neighborhood vectors for the first input vector. This feature-based neighborhood vector search method may be any method, for example, a method such as the nearest neighbor vector search process described with reference to the flowchart of FIG. The number of vectors to be searched may be one or may be plural. When searching for the feature-by-feature vectors, the neighborhood vector search unit 413 supplies the search result to the neighborhood vector candidate setting unit 414, and the process proceeds to step S244.

  In step S244, the neighborhood vector candidate setting unit 414 sets the searched vector as an initial value of the feature-specific neighborhood vector candidate in the next search, supplies the information to the neighborhood vector search unit 413, and the process proceeds to step S245. Proceed.

  In step S245, the neighborhood vector search unit 413 searches for feature-specific neighborhood vectors for the next input vector. In this search, when a vector closer to the feature-specific neighborhood vector candidate is searched, the neighborhood vector search unit 413 updates the feature-based neighborhood vector candidate, sets the searched vector as the feature-based neighborhood vector candidate, A change flag corresponding to the neighborhood vector candidate is set. When the search is completed, the neighborhood vector search unit 413 supplies the final feature-specific neighborhood vector candidate to the feature-specific neighborhood vector candidate setting unit 414 as a feature-specific neighborhood vector. The neighborhood vector search unit 413 also supplies information on change flags to the feature-specific neighborhood vector candidate setting unit 414.

  In step S246, similar to the case of step S244, the feature-specific neighborhood vector candidate setting unit 414 further sets the currently searched vector as the initial value of the feature-specific neighborhood vector candidate in the next search. At this time, the value of the change flag is left as it is. The feature-specific neighborhood vector candidate setting unit 414 further supplies the information to the neighborhood vector search unit 413, and also supplies the change flag confirmation unit 415 with information on the change flag of each feature-based neighborhood vector candidate, and the process proceeds to step S247. Proceed to

  In step S247, the change flag confirmation unit 415 confirms the state of the change flag of the supplied feature-specific neighborhood vector candidate, supplies the confirmation result to the neighborhood vector group search control unit 412, and advances the process to step S248.

  In step S248, the neighborhood vector group search control unit 412 determines whether there is an invariant feature neighborhood vector candidate based on the confirmation result. If it is determined that there are invariant feature-specific neighborhood vector candidates, the neighborhood vector group search control unit 412 advances the process to step S249, and has searched for feature-specific neighborhood vectors for all input vectors in the input vector group that has been input. Determine whether or not.

  When it is determined that there is an unprocessed input vector in the input vector group that has been input, the neighborhood vector group search control unit 412 supplies the determination result to the neighborhood vector search unit 413 and returns the process to step S245, To process the input vector. That is, the neighborhood vector group search control unit 412, the neighborhood vector search unit 413, the feature-specific neighborhood vector candidate setting unit 414, and the change flag confirmation unit 415 are the feature vector neighborhoods that the neighborhood vector group search control unit 412 does not change in step S 248. The processing from step S245 to step S249 is repeated until it is determined that no vector candidate exists or until it is determined that feature-based neighborhood vectors have been searched for all input vectors of the input vector group input in step S249.

  If it is determined in step S249 that the feature-based neighborhood vectors have been searched for all the input vectors of the input vector group, the neighborhood vector group search control unit 412 sends the feature vector neighborhood vector to the neighborhood vector setting unit 416. Then, the process is supplied to step S250.

  In step S250, the neighborhood vector setting unit 416 sets an invariant feature-specific neighborhood vector among the supplied feature vector neighborhood vectors as a neighborhood vector group of the input vector group. When the setting is completed, the neighborhood vector setting unit 416 supplies the neighborhood vector group to the model detection determining unit 367 (FIG. 33), notifies the neighborhood vector group search control unit 412 of the end of the process, and the process proceeds to step S251. Proceed.

  If it is determined in step S248 that all the feature-specific neighborhood vector candidate change flags are set and there is no invariant feature-specific neighborhood vector candidate, the neighborhood vector group search control unit 412 includes the vector group. It is determined that there is no vector located in the vicinity with respect to all input vectors (determined that a desired neighborhood vector group cannot be obtained in the vector group), and the search for the neighborhood vector group in the vector group is terminated. The process proceeds to step S251.

  In step S251, the neighborhood vector group search control unit 412 adds “+1” to the value of the variable j to change the processing target vector group. In step S252, the neighborhood vector group search control unit 412 initializes the feature-specific neighborhood vector candidate, sets it as an infinite virtual point, returns the processing to step S242, and repeats the subsequent processing.

  That is, the neighborhood vector group search control unit 412, the neighborhood vector search unit 413, the feature-specific neighborhood vector candidate setting unit 414, and the change flag confirmation unit 415 are the neighborhood vector group search control unit 412 in the neighborhood of all vector groups in step S <b> 242. The processing from step S242 to step S252 is repeated until it is determined that the vector group has been searched.

  If it is determined in step S242 that the neighborhood vector group has been searched in all the vector groups, the neighborhood vector group search control unit 412 ends the neighborhood vector group search process, and the process returns to step S214 in FIG. Further, the plural types of feature amount comparison processing is terminated.

  As described above, in the search for a plurality of types of feature vectors, the neighborhood vector search unit 396 can reduce unnecessary calculation amount by using the search result of one feature vector for the search of other feature vectors. It is possible to search the neighborhood vector group of the input vector group at higher speed. That is, the neighborhood vector search unit 396 includes a plurality of vector sets to be searched, and even when comparing an input vector group including a plurality of types of input vectors with the vector set to be searched, The neighborhood vector group of the input vector group can be searched at high speed.

  Therefore, the image processing apparatus 350 has a plurality of vector sets to be searched, and even if an input vector group consisting of a plurality of types of input vectors is compared with the vector set to be searched, input from each vector set is performed. The neighborhood vector group of the vector group can be searched at high speed. In other words, the image processing apparatus 350 can search a target element group from each set at high speed even when there are a plurality of sets to be searched, and even when a plurality of types of elements are searched.

  In the above description, the case where there are a plurality of search target vector groups (models) has been described. However, the search performed when there are a plurality of types of features to be compared with the search target described with reference to FIGS. 32 to 37. The method can be applied even when there is one vector group (model) to be searched. That is, the search method using the search result of one feature vector for searching for another feature vector only needs to have a plurality of types of features to be compared (types of input vectors). Is not dependent.

  Therefore, the image processing device 350 can quickly search for a neighborhood vector group of input vector groups composed of input vectors of different types when comparing a search target with a plurality of types of features. That is, the image processing apparatus 350 can obtain the target element group from the search target set at high speed even when comparing the search target with a plurality of types of features.

  Note that each device described above may be configured by a plurality of devices divided in units of the above-described processing units, for example. Of course, the division unit may be any unit and may be a unit other than the processing unit. Moreover, you may make it comprise what was demonstrated as a some apparatus as one apparatus. Moreover, you may make it further combine the function which is not mentioned above with the apparatus mentioned above. In addition, as long as no contradiction or malfunction occurs, a part of the above-described function (processing unit) may be omitted. Furthermore, the processing described to be executed in a certain processing unit may be executed in another processing unit.

  The search processing method to which the present invention is applied can be applied to other than image recognition processing, and can be used for information processing on data other than image data such as voice data and text data.

  The series of processes described above can be executed by hardware or can be executed by software. In this case, for example, the feature amount comparison device 10 of FIG. 1, the devices of the feature amount comparison system 200 of FIG. 22, the image processing device 230 of FIG. 23, the image processing device 250 of FIG. 24, and the feature amount comparison device 280 of FIG. 33 and the image processing apparatus 350 in FIG. 33 may be configured as a personal computer as shown in FIG.

  In FIG. 38, a CPU (Central Processing Unit) 501 of the personal computer 500 performs various processes according to a program stored in a ROM (Read Only Memory) 502 or a program loaded from a storage unit 513 into a RAM (Random Access Memory) 503. Execute the process. The RAM 503 also appropriately stores data necessary for the CPU 501 to execute various processes.

  The CPU 501, ROM 502, and RAM 503 are connected to each other via a bus 504. An input / output interface 510 is also connected to the bus 504.

  The input / output interface 510 includes an input unit 511 including a keyboard and a mouse, a display including a CRT (Cathode Ray Tube) and an LCD (Liquid Crystal Display), an output unit 512 including a speaker, and a hard disk. A communication unit 514 including a storage unit 513 and a modem is connected. The communication unit 514 performs communication processing via a network including the Internet.

  A drive 515 is connected to the input / output interface 510 as necessary, and a removable medium 521 such as a magnetic disk, an optical disk, a magneto-optical disk, or a semiconductor memory is appropriately mounted, and a computer program read from them is It is installed in the storage unit 513 as necessary.

  When the above-described series of processing is executed by software, a program constituting the software is installed from a network or a recording medium.

  For example, as shown in FIG. 38, the recording medium is distributed to distribute the program to the user separately from the apparatus main body, and includes a magnetic disk (including a flexible disk) on which the program is recorded, an optical disk ( Removable media 521 including a CD-ROM (compact disk-read only memory), a DVD (digital versatile disk), a magneto-optical disk (including MD (mini-disk) (registered trademark)), or a semiconductor memory In addition to being configured, it is configured by a ROM 502 on which a program is recorded and a hard disk included in the storage unit 513, which is distributed to the user in a state of being pre-installed in the apparatus main body.

  In the present specification, the step of describing the program recorded on the recording medium is not limited to the processing performed in chronological order according to the described order, but is not necessarily performed in chronological order. It also includes processes that are executed individually.

  Further, in this specification, the system represents the entire apparatus composed of a plurality of devices (apparatuses).

It is a block diagram which shows the structural example of the feature-value comparison apparatus to which this invention is applied. It is a figure explaining the mode of neighborhood table group creation. It is a figure which shows the structural example of a neighborhood table group. It is a figure explaining the mode of search of a nearest neighbor vector. It is a figure explaining the example of narrowing down a search range. It is a block diagram which shows the detailed structural example of the common representative point setting part of FIG. It is a block diagram which shows the detailed structural example of the neighborhood table group production | generation part of FIG. It is a block diagram which shows the detailed structural example of the vicinity table preparation part of FIG. It is a block diagram which shows the detailed structural example of the distance information preparation part of FIG. FIG. 2 is a block diagram illustrating a detailed configuration example of a nearest neighbor vector group search unit in FIG. 1. It is a block diagram which shows the detailed structural example of the nearest neighbor vector search part of FIG. It is a block diagram which shows the detailed structural example of the search part in a table of FIG. It is a block diagram which shows the detailed structural example of the whole group internal search part of FIG. It is a flowchart explaining the example of a common representative point setting process. It is a flowchart explaining the example of a neighborhood table group creation process. It is a flowchart explaining the example of a neighborhood table creation process. It is a flowchart explaining the example of distance information creation processing. It is a flowchart explaining the example of a nearest neighbor vector group search process. It is a flowchart explaining the example of a nearest neighbor vector search process. It is a flowchart explaining the example of the search process in a table. It is a flowchart explaining the example of the whole group search process. It is a block diagram which shows the structural example of the feature-value comparison system to which this invention is applied. It is a block diagram which shows the structural example of the image processing apparatus to which this invention is applied. It is a block diagram which shows the other structural example of the image processing apparatus to which this invention is applied. It is a block diagram which shows the other structural example of the feature-value comparison apparatus to which this invention is applied. It is a schematic diagram explaining the mode of coordinate transformation. It is a schematic diagram explaining the mode of dimensional compression. It is a figure explaining the mode of comparison of the distance between vectors. It is a block diagram which shows the detailed structural example of the member vector coordinate transformation part of FIG. It is a flowchart explaining a feature-value comparison process. It is a flowchart explaining a member vector coordinate transformation process. It is a figure explaining a mode that a neighborhood vector group is searched. FIG. 20 is a block diagram illustrating still another configuration example of an image processing apparatus to which the present invention has been applied. It is a block diagram which shows the detailed structural example of the multiple types feature-value comparison part of FIG. FIG. 35 is a block diagram illustrating a detailed configuration example of a neighborhood vector group search unit in FIG. 34. It is a flowchart explaining a multiple types feature-value comparison process. It is a flowchart explaining a neighborhood vector group search process. It is a figure which shows the structural example of the personal computer to which this invention is applied.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 Feature-value apparatus, 11 Vector information storage part, 12 Common representative point setting part, 13 Common representative point information storage part, 14 Neighbor table group creation part, 15 Neighbor table group memory part, 16 Nearest vector group search part, 41 Common Representative point target number setting unit, 42 vector group unifying unit, 43 centroid calculating unit, 44 common representative point setting unit, 45 common representative point number determining unit, 46 common representative point dividing unit, 47 member vector assigning unit, 48 common representative point storage Control unit, 61 initialization processing unit, 62 neighborhood table group creation control unit, 63 neighborhood table creation unit, 64 neighborhood table storage control unit, 81 neighborhood table creation control unit, 82 distance information creation unit, 83 distance information sort unit, 84 Distance information extraction unit, 85 record holding unit, 101 distance information creation control unit, 102 distance calculation unit, 103 1/2 multiplication unit, 104 distance information holding unit, 121 initialization processing unit, 122 nearest neighbor vector group search control unit, 123 nearest neighbor vector search unit, 141 initialization processing unit, 142 nearest neighbor vector Search control unit, 143 distance calculation unit, 144 distance comparison unit, 145 in-table search unit, 146 nearest neighbor vector setting unit, 147 entire group search unit, 161 initialization processing unit, 162 in-table search control unit, 163 distance calculation Unit, 164 update control unit, 165 data holding unit, 181 initialization processing unit, 182 whole group search control unit, 183 distance calculation unit, 184 update control unit, 185 data holding unit, 200 feature quantity comparison system, 230 image processing Device, 246 feature comparison unit, 250 strokes Image processing device, 263 model dictionary registration unit, 280 feature quantity comparison device, 281 member vector coordinate conversion unit, 282 input vector coordinate conversion unit, 283 nearest neighbor vector coordinate conversion unit, 311 vector group unification unit, 312 principal component analysis unit, 313 Coordinate transformation unit, 314 dimensional compression unit, 315 transformation coordinate vector information storage control unit, 350 image processing device, 366 multiple types feature quantity comparison unit, 381 feature quantity information acquisition unit, 411 initialization processing unit, 412 neighborhood vector group search Control unit, 413 neighborhood vector search unit, 414 feature-specific neighborhood vector candidate setting unit, 415 change flag confirmation unit, 416 neighborhood vector setting unit, 500 personal computer

Claims (6)

An information processing apparatus for comparing features by comparing feature vectors obtained by combining feature parameters of an image with an input image and a model image prepared in advance.
Feature vector storage means for storing the feature vectors of the model image grouped for each dimension of the space in which the feature vectors exist ;
Input vector extraction means for extracting a plurality of input vectors that are the feature vectors of the input image from the input image;
For the group to be processed, a distance from the input vector to be processed in the input vector extracted by the input vector extraction unit to the feature vector read from the feature vector storage unit; Compare the distance from the input vector to be processed to the feature vector that is a candidate for a nearby vector located in the vicinity of the input vector to be processed, and use the shorter feature vector as the new neighborhood Search means for searching for candidates for the neighboring vectors in the group by performing processing as vector candidates one by one for all feature vectors in the group ;
Change flag updating means for setting a change flag indicating that the neighborhood vector candidate is updated when the neighborhood vector candidate is updated to a new feature vector by the search by the search means ;
If there is a candidate for the neighborhood vector for which the change flag is not set by the change flag update means, the search is performed for the next input vector to be processed until the search is performed for all input vectors. ,
When there is no candidate for the neighborhood vector for which the change flag has not been raised by the change flag update unit, the search for the group is terminated, and the next processing target object is processed until the search for all the groups is performed. Let the group perform the search
And control means,
An information processing apparatus comprising: neighborhood vector setting means for setting a current candidate for the neighborhood vector as the neighborhood vector after the search is performed for all the groups in accordance with control by the control means . For each group of feature vectors stored by the feature vector storage means, each of the feature vectors belonging to the group is a mass point, and a center of gravity that is a point of action of the resultant force of gravity acting on each mass point is a common representative point, Further comprising a neighborhood table storage means for storing a neighborhood table in which a common representative point is associated with the feature vector located in the vicinity of the common representative point;
The search means is configured such that a distance between the common representative point included in the neighborhood table stored in the neighborhood table storage means and the feature vector located in the vicinity of the common representative point is the input to the common representative point and the input The information processing according to claim 1, wherein if the distance to the vector is shorter than the distance vector, the candidate for the neighborhood vector in the group is searched from the feature vectors included in the neighborhood table stored by the neighborhood table storage unit. apparatus. For each group of feature vectors stored by the feature vector storage means, the feature vector belonging to the group is used as a mass point, a center of gravity is obtained as a point of action of the resultant force of gravity acting on each mass point, and the center of gravity is determined. Common representative point setting means for setting as the common representative point;
Wherein by matching the feature vectors located in the vicinity of the common representative point that is set to the common representative point by a common representative point setting means further includes a neighborhood table creation means for creating the neighborhood table,
The information processing apparatus according to claim 2, wherein the neighborhood table storage unit stores the neighborhood table created by the neighborhood table creation unit. Further comprising feature vector extraction means for extracting the feature vector from the model image;
The information processing apparatus according to claim 1, wherein the feature vector storage unit stores the feature vector extracted by the feature vector extraction unit. An information processing method of an information processing apparatus for comparing features by comparing a feature vector obtained by combining vector feature parameters with an input image and a model image prepared in advance,
The feature vector storage means of the information processing apparatus stores the feature vectors of the model image grouped for each dimensionality of the space in which the feature vectors exist ,
The input vector extracting unit of the information processing apparatus, from the input image, a plurality of extracting the input vector is a feature vector of the input image,
The search means of the information processing apparatus, for the group to be processed, a distance from the input vector to be processed in the input vector extracted to the feature vector read from the storage unit, Compare the distance from the input vector to be processed to the feature vector that is a candidate for a nearby vector located in the vicinity of the input vector to be processed, and use the shorter feature vector as the new neighborhood By performing the processing as a vector candidate one by one for all feature vectors in the group, the candidate for the neighborhood vector in the group is searched,
Change flag updating means of the information processing apparatus, by the search, if the candidate of the neighboring vector is updated to a new feature vector, it sets a change flag indicating that the candidate of the neighboring vector is updated,
Control means of the information processing apparatus,
If there is a candidate for the neighborhood vector for which the change flag is not set, the search is performed for the input vector to be processed next until the search is performed for all the input vectors.
If there is no candidate for the neighborhood vector for which the change flag is not set, the search for the group is terminated, and the group to be processed next is processed until the search for all the groups is performed. Do a search ,
A neighborhood vector setting unit of the information processing apparatus sets the current neighborhood vector candidate as the neighborhood vector after the search is performed on all the groups according to the control . A computer for comparing features by comparing feature vectors obtained by combining vector feature parameters with an input image and a model image prepared in advance.
Feature vector storage means for storing the feature vectors of the model image grouped for each dimension of the space in which the feature vectors exist ;
Input vector extraction means for extracting a plurality of input vectors that are the feature vectors of the input image from the input image;
For the group to be processed, a distance from the input vector to be processed in the input vector extracted by the input vector extraction unit to the feature vector read from the feature vector storage unit; Compare the distance from the input vector to be processed to the feature vector that is a candidate for a nearby vector located in the vicinity of the input vector to be processed, and use the shorter feature vector as the new neighborhood Search means for searching for candidates for the neighboring vectors in the group by performing processing as vector candidates one by one for all feature vectors in the group ;
Change flag updating means for setting a change flag indicating that the neighborhood vector candidate is updated when the neighborhood vector candidate is updated to a new feature vector by the search by the search means ;
If there is a candidate for the neighborhood vector for which the change flag is not set by the change flag update means, the search is performed for the next input vector to be processed until the search is performed for all input vectors. ,
If there is no candidate for the neighborhood vector for which the change flag has not been raised by the change flag update means, the search for the group is terminated, and the next processing target is processed until the search for all the groups is performed. Control means for performing the search for the group ;
A program for functioning as neighborhood vector setting means for setting a current candidate for the neighborhood vector as the neighborhood vector after the search is performed for all the groups in accordance with control by the control means .

Images