JP2000090271A - Partial dictionary reduction method, dictionary reduction method and evaluation method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a method for reducing a partial dictionary or dictionary without dropping recognition performance while keeping dictionary capacity suitable by defining the degree of similarity with the other partial dictionary and information quantity provided for a dictionary set as a selection reference. SOLUTION: A dictionary set X is composed of dictionaries X1-Xn, and each dictionary is further composed of several partial dictionaries. For example, the information quantity provided in a partial dictionary (s), which is included in a dictionary Xsk, can be defined by how much the entropy of dictionary input Xs is decreased before and after the provision of output (s). Therefore, the (s) to maximize the mutual information quantity provided for the dictionary set X by the partial dictionary (s) has the maximum mutual information quantity, namely, the information quantity corresponding to the determination of dictionary. Thus, the partial dictionary of a little mutual information, which has just a little information quantity corresponding to the dictionary determination, is reduced and the partial dictionary of much mutual information quantity having much information quantity corresponding to the dictionary determination is remained so that the number of partial dictionaries can be reduced without dropping the ability of dictionary determination.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a partial dictionary reduction method, a dictionary reduction method, and an evaluation method thereof for reducing a matching dictionary for recognizing a position or orientation of an object in an image as a feature pattern.

[0002]

2. Description of the Related Art (1) There is a method of recognizing a position and a posture using an entire object in an image as a feature pattern. (2) There is a method of recognizing a position or a posture based on local features of an object in order to strengthen partial occlusion.

(3) There is a method of reducing the number of local features based on the similarity between individual features. However, the method (1) is vulnerable to partial occlusion and noise because the entire object is treated as a pattern. In addition, the method (2) has a problem that the dictionary increases as the number of learning dictionary images increases.
Furthermore, in the method (3), a reduction candidate is selected based on whether or not there is another local feature having a high degree of similarity. Therefore, if there is at least one local feature that is similar to another, a reduction target is determined. There is a problem that it becomes.

[0004]

As described above, in the conventional method, it is weak to partial occlusion and noise if the position and orientation are recognized by using the entire object as a pattern. Recognizing the position and orientation based on local (partial) features increases the number of dictionary images for learning, and the dictionary increases accordingly. If the local feature is similar to the other, the candidate to be reduced is selected depending on whether or not there is another local feature having a high similarity. As a result, there is a problem that the dictionary capacity becomes inappropriate or the recognition performance drops.

SUMMARY OF THE INVENTION It is an object of the present invention to provide a partial dictionary reduction method and a dictionary reduction method for reducing a partial dictionary or a dictionary without reducing the recognition performance by appropriately setting the dictionary capacity. Another object of the present invention is to provide an evaluation method for evaluating the recognition performance of a reduced partial dictionary or dictionary.

[0006]

A partial dictionary reduction method according to the present invention provides a dictionary set having a plurality of dictionaries comprising a set of local feature quantity partial dictionaries for matching local feature quantities in a physical quantity pattern of an object. Wherein the partial dictionary in the dictionary is similar to other partial dictionaries included in the dictionary, and the amount of information the partial dictionary has with respect to the dictionary set is selected as a selection criterion. Is reduced.

A dictionary reduction method according to the present invention is a dictionary reduction method for a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature values for matching local feature values in a physical quantity pattern of an object. The first dictionary based on the magnitude relation between the similarity of the second dictionary from the first dictionary and the similarity of the first dictionary from the second dictionary based on the similarity between the partial dictionaries. Alternatively, the second dictionary is reduced.

An evaluation method according to the present invention is an evaluation method for evaluating detection performance in a system for detecting a position of an object from input data, and is for determining how much an output detection position deviates from an actual position. The detection performance is evaluated from the value and the value of the certainty factor for the detection position.

An evaluation method according to the present invention is an evaluation method for reducing partial dictionaries in a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature amounts for matching local feature amounts in a physical quantity pattern of an object. The dictionary recognition performance is calculated from a value indicating how much the detected position output from the dictionary set in which the partial dictionary has been reduced is shifted from the actual position and a value of the certainty factor for the detected position. It is characterized in that the degree of convergence of dictionary reduction is evaluated.

The evaluation method according to the present invention is an evaluation method for dictionary reduction in a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature values for matching local feature values in a physical quantity pattern of an object. The correct answer rate as to whether the partial dictionary included in the second dictionary reduced as having a high similarity to the first dictionary correctly selected the partial dictionary of the first dictionary as the partial dictionary having the highest similarity Is compared with the expected value of the correct answer rate based on the number of dictionaries that have not been deleted, and the degree of convergence of the reduction is determined.

The evaluation method according to the present invention is an evaluation method for dictionary reduction in a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature values for matching local feature values in a physical quantity pattern of an object. The dictionary recognition performance is calculated by calculating a dictionary recognition performance from a value indicating how much the detected position output from the dictionary reduced dictionary set deviates from the actual position and a value of the certainty factor for the detected position. It is characterized in that the degree of convergence is evaluated.

[0012]

An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 shows target recognition based on local feature values. As shown in the figure, a local pattern of an object is defined as a feature amount (local feature amount).
By integrating these matching results, it is possible to detect and cut out a person or a face, recognize a posture, and recognize the type, position, and angle of a form.

Hereinafter, individual pattern dictionaries of local feature values are called "partial dictionaries", and individual dictionaries (corresponding to one learning image) including those partial dictionaries are simply called "dictionaries". First
The second embodiment shows a method for reducing the number of partial dictionaries or the number of dictionaries included in a dictionary set composed of partial dictionaries, and the second embodiment shows a method for evaluating the detection performance of a target object position detection system.

First, a first embodiment will be described. First
In the embodiment, as described above, a method of reducing the number of partial dictionaries or the number of dictionaries included in the dictionary set including the partial dictionaries will be described.

As shown in FIG. 2A, dictionaries X1, X2,. . . , Xn.
Each dictionary X1. . . Is further composed of several partial dictionaries. It is assumed that each partial dictionary is a pattern of a × b pixels.

Then, the similarity Sim between the partial dictionaries s and t is Sim
(S, t) can be represented, for example, by the following equation. Sim (s, t) = Σ (s_it_i) i = {a × b} s_i is the pixel value of the i pixel of the partial dictionary s.

I indicates one point in the a × b pattern.
Here, according to the conventional method, s and t are deleted when Sim (s, t)> Th (Th is a certain threshold value). (1-1) Method for Reducing the Number of Partial Dictionaries Here, among the processes shown in FIG. 2, a process for reducing the number of partial dictionaries as shown in FIGS. 2A to 2B will be described.

First, the partial dictionary s included in the dictionary Xs is
Consider the amount of information held for the dictionary Xs. A partial dictionary t (Sim (s, t)> having sufficiently high similarity to the partial dictionary s
Th) is assumed to be Nt (Nt is generally proportional to the total number of partial dictionaries).

If there is an input partial pattern that should be determined to be closest to the partial dictionary s, the probability that s is correctly selected as the partial dictionary having the highest similarity to the input partial pattern is P ( s) = 1 / Nt. This is because the partial dictionaries t and s have a sufficiently high degree of similarity, so that they are identified with each other, and any of such Nt partial dictionaries is evaluated as being closest to the input pattern with equal probability. is there.

If the number of partial dictionaries included in the dictionary Xs is N
If it is s, it can be expressed as P (Xs / s) = 1 / Ns. Here, the posterior probability is calculated using the partial dictionary s
Is regarded as a certainty factor that can be determined to be the dictionary Xs.

Here, the information amount (mutual information amount I (Xs; s)) that the partial dictionary s has for the dictionary Xs is defined as a system that obtains a partial dictionary output for the dictionary input Xs. It can be defined by how much the entropy decreases before and after obtaining the output s.

I (Xs; s) = H (Xs) -H (Xs / s) where H (Xs) is the entropy of Xs before obtaining the output s, and H (Xs / s) is the entropy of the output s. Xs after entropy.

Further, since the partial dictionary s is not included except for the dictionary Xs, I (dictionary other than Xs; s) = 0.

Therefore, the mutual information I (X; s) obtained for the dictionary set X by the partial dictionary s is: I (X; s) = I (Xs; s) +） I (Dictionaries other than Xs; s) = I (Xs; s) = H (Xs) -H (Xs / s) = P (Xs) log (1 / P (Xs))-P (Xs, s) log (1 / P (Xs / s) ) = P (Xs) log (1 / P (Xs))-P (s) P (Xs / s) log (1 / P (Xs / s)) = P (Xs) log (1 / P (Xs) ) + P (s) P (Xs / s) logP (Xs / s).

Xs is a dictionary X1, X2,. . . , Xn, but if there is no bias in the input pattern with respect to the corresponding correct dictionary (that is, unless only patterns close to a particular dictionary are input), P (X
1) =. . . = P (Xn), and the first term of the above equation can be ignored as a constant.

Therefore, finally, the second term P (s) P (Xs / s) logP (Xs / s) = (1 /
S that maximizes Nt) * (1 / Ns) * log (1 / Ns) has the largest mutual information amount, that is, it has an information amount for determining a dictionary. As the number of similar partial dictionaries is smaller (Nt is smaller), the dictionary X
As the number of partial dictionaries included in s is smaller (Ns is smaller),
This value increases.

In this manner, the partial dictionaries having a small amount of mutual information having little information amount for the dictionary determination are reduced, and the partial dictionaries having a large mutual information amount having a large information amount for the dictionary determination are left. The number of partial dictionaries can be reduced without reducing the ability to determine a dictionary as much as possible. (1-2) Convergence Judgment Method for Reducing the Number of Partial Dictionaries As the number of partial dictionaries is reduced, the amount of information in the entire dictionary decreases, so that recognition performance generally decreases. The recognition performance Acc is obtained by the recognition performance evaluation based on the position detection deviation described later in the second embodiment, and a certain threshold value Th_acc is set. If Acc ≧ Th_acc, sufficient recognition performance is maintained. If Acc <Th_acc, it is determined that sufficient recognition performance cannot be maintained and that the deletion has converged. (2-1) Method of reducing the number of dictionaries In the above description, the number of dictionaries was reduced in units of the partial dictionaries.
The number of dictionaries is reduced in units of s.

In the process shown in FIG. 2, (a) of FIG.
(C) corresponds to a process for reducing the number of dictionaries. The similarity of the dictionary Xt viewed from the dictionary Xs
Based on the similarity between the partial dictionary s included in s and the partial dictionary t included in the dictionary Xt, Can be defined as Similarly, Sim (Xs ← Xt) can be defined.

Here, that Sim (Xt ← Xs) is large means that Xt is a dictionary having a high similarity when viewed from Xs (it has many partial dictionaries having a high similarity).

Further, Sim (Xt ← Xs) >> Si
For m (Xs ← Xt), this is where Xs is only close to Xt. Xt may be close to Xs, but there are others other than Xs. Means that FIG. 3 shows such a situation two-dimensionally.

Here, for the sake of simplicity, if the similarity Sim is considered as Sim (Xt ← Xs) = 1 / Dist (Xt ← Xs) using the distance Dist, if Xs and Xt are sufficiently close, Sim (Xt ← Xs) >> Sim (except Xt ← Xs) That is, Dist (Xt ← Xs) << Dist (except Xt ← Xs), the distance Dist to a dictionary Xy is Dist (Xy ← Xs) ≒ Dist (Xy ← Xt) + Dist (Xt ← Xs) ≒ Dist (Xy ← Xt), and Sim (Xy ← Xs) ≒ Sim (Xy ← Xt), so that Xs is the same as Xt with respect to other dictionaries Xy. can do.

Therefore, Sim (Xt ← Xs) is sufficiently large, and Sim (Xt ← Xs) is equal to Sim (Xs ← Xt).
If Xs is large enough, Xs can be merged with Xt and identified, and the dictionary Xs can be deleted. (2-2) Convergence determination method for reducing the number of dictionaries It is assumed that the dictionary X0 is merged with the dictionary X1 and deleted. At this time, for each of the partial dictionaries included in the deleted dictionary X0, the partial dictionary having the highest similarity among the partial dictionaries included in the remaining unmerged dictionaries (assuming N) is determined. Think about choosing. Dictionary X0
Has been merged with the dictionary X1 as having a high degree of similarity, so ideally all of the partial dictionaries of X0 should select the partial dictionary of X1 as the partial dictionary having the highest similarity. However, in practice, a part of the partial dictionary of X0 selects the partial dictionary of X1, but others select a partial dictionary other than X1. The rate at which the partial dictionary of X1 is correctly selected is set as the correct answer rate R_correct.

On the other hand, the number of dictionaries remaining without being merged is N
Therefore, if there is no bias in the number of partial dictionaries in each dictionary, the expected value of the correct answer rate is 1 / N. If X0 and X1 are sufficiently similar and have an appropriate merge, R_co
rrect keeps a sufficiently high value, and the value is much larger than 1 / N. However, as shown in FIG.
If the degree of similarity is not sufficiently higher than the degree of similarity with other dictionaries, the selection is dispersed among the remaining N dictionaries, and the correct answer rate approaches 1 / N.

Therefore, the merge that maintains R_correct ≧ k / N (k is an appropriate coefficient) is an appropriate merge. If R_correct <k / N (k is an appropriate coefficient), the merge of X0 and X1 is performed. Assuming that the similarity is not sufficiently high as compared with merging with another dictionary, it can be determined that the merging has converged. Here, the coefficient k is the strictness of the criterion for convergence determination. The larger the value of k, the higher the accuracy rate (the merging has not progressed so much). Even if the rate decreases, the number of dictionaries remaining decreases because merging is continued.

On the other hand, in the method of using the recognition performance evaluation based on the position detection deviation described in the second embodiment instead of the correct answer rate, a certain threshold Th_ac is applied to the detection performance Acc.
c is set, and if Acc ≧ Th_acc, it is determined that sufficient recognition performance is maintained and the deletion process is continued. If Acc <Th_acc, sufficient recognition performance is no longer maintained and it is determined that the deletion has converged. .

Next, a second embodiment will be described. Second
In the embodiment, an evaluation method of the detection performance in the target position detection system will be described.

The detection position of the object output from the position detection system is (x, y), its certainty is R, and the position of the true object is (X, Y). Then, D, which is the square of the difference between the detected position of the object and the position of the true object, is given by D = (X−x) * (X−x) + (Y−y) * (Y−y). Is done. When the squared deviation D is equal to or smaller than Th, the detection is successful, and when it exceeds Th, the detection is failed. At this time, the detection performance Acc is calculated as follows: Acc = a * sqrt (Th−D) * R...
<= Th) or -b * sqrt (D-Th) * R ... Detection failed (D> t)
h) (a and b are non-negative coefficients) (sqrt () indicates a square root)

In this example, the certainty factor R is weighted as shown in FIG. 5 based on the magnitude of the square D of the deviation. When the detection is successful, the higher the confidence R, the higher the detection performance A
cc takes a high value. Conversely, in the case of unsuccessfulness, the higher the certainty factor R, the lower the detection performance Acc. The feature is that "a large penalty is given to the result that is most unfavorable for the detection system that the result output with high certainty is large wrong".

As described above, according to the embodiment of the present invention, the local feature is robust against environmental changes, and by appropriately reducing the dictionary capacity, it is possible to detect a person.
Applications such as person posture recognition, courier label recognition, form recognition, and product (outer box) type recognition can be realized at higher speed and at lower cost.

In addition to a simple similarity between partial dictionaries (local feature amounts), a dictionary having a large amount of information useful for recognition is deleted as much as possible by taking into account the information amount of the dictionary included in the partial dictionary. Can be left behind. Thereby, the number of dictionaries can be reduced without lowering the recognition performance.

[0041]

As described in detail above, according to the present invention,
It is possible to provide a partial dictionary reduction method and a dictionary reduction method for reducing a partial dictionary or a dictionary without reducing the recognition performance by appropriately setting the dictionary capacity. Further, it is possible to provide an evaluation method for evaluating the recognition performance of the reduced partial dictionary or dictionary.

[Brief description of the drawings]

FIG. 1 is a diagram for explaining target object recognition based on local feature values.

FIG. 2 is a diagram showing a dictionary reduction process.

FIG. 3 is a diagram expressing a pattern distance of a dictionary two-dimensionally.

FIG. 4 is a schematic diagram of a dictionary merge situation.

FIG. 5 is a diagram showing an example of a weighting coefficient for an evaluation value based on the size of a shift.

[Explanation of symbols]

 X: Dictionary set X1, X2, ... Xn: Dictionary

Claims (6)

[Claims] 1. A method for reducing a partial dictionary in a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature values for matching local feature values in a physical quantity pattern of an object, comprising: A partial dictionary, wherein the number of partial dictionaries is reduced based on a similarity between the dictionary and other partial dictionaries included in the dictionary and an information amount of the partial dictionary with respect to the dictionary set as a selection criterion. How to reduce. 2. A dictionary reduction method for a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature amounts for matching local feature amounts in a physical quantity pattern of an object, comprising: Based on the degree, the second from the first dictionary
The first dictionary or the second dictionary is reduced according to the magnitude relation between the similarity of the first dictionary and the similarity of the first dictionary from the second dictionary. . 3. An evaluation method for evaluating a detection performance in a system for detecting a position of an object from input data, wherein a value indicating how much the output detection position is deviated from an actual position, An evaluation method characterized in that detection performance is evaluated from a value of certainty factor for a position. 4. An evaluation method for reducing partial dictionaries in a dictionary set having a plurality of dictionaries including a set of partial dictionaries of local feature amounts for matching local feature amounts in a physical quantity pattern of an object, comprising: Is calculated from the value of how much the detected position output from the reduced dictionary set is shifted from the actual position and the value of the certainty factor for the detected position, and the convergence of the partial dictionary reduction is calculated. An evaluation method characterized in that the degree is evaluated. 5. A method for evaluating dictionary reduction in a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature values for matching local feature values in a physical quantity pattern of an object, comprising: The partial dictionary included in the second dictionary, which has been reduced as having a high similarity to the dictionary, does not delete the correct answer rate as to whether the partial dictionary of the first dictionary was correctly selected as the partial dictionary having the highest similarity. An evaluation method characterized in that the degree of convergence of reduction is determined by comparing the expected value of the correct answer rate based on the number of dictionaries. 6. A method for evaluating dictionary reduction in a dictionary set having a plurality of dictionaries comprising a set of partial dictionaries of local feature amounts for matching local feature amounts in a physical quantity pattern of an object, wherein the dictionary is reduced. The recognition performance of the dictionary is calculated from the value of how much the detection position output from the set of dictionary that has been deviated from the actual position and the value of the certainty factor for the detection position, and the degree of convergence of dictionary reduction is evaluated. An evaluation method characterized in that: