Feature vector classification device and method thereof

Disclosed is a feature vector classification device which includes an initial condition setting unit; a variable calculating unit configured to receive a training vector and to calculate an error and a weight according to setting of the initial condition setting unit; a loop deciding unit configured to determine whether re-calculation is required, based on a comparison result between the calculated error and an error threshold; and a hyperplane generating unit configured to generate a hyperplane when an end signal is received from the loop deciding unit.

CROSS-REFERENCE TO RELATED APPLICATIONS

A claim for priority under 35 U.S.C. §119 is made to Korean Patent Application No. 10-2011-0106863 filed Oct. 19, 2011, in the Korean Intellectual Property Office, the entire contents of which are hereby incorporated by reference.

BACKGROUND

The inventive concepts described herein relate to a feature vector classification device and a method thereof.

Feature vector classification may be one of critical factors to determine performance and speed of the recognition technique. A support vector machine (hereinafter, referred to as SVM) may be one of manners used to classify and recognize objects using machinery, and may be widely used thanks to its excellent performance.

However, a larger number of support vectors may be stored through nonlinear kernel to express high complexity using the SVM. Also, complicated operations may be required between input vector and support vector. Much hardware for parallel processing may be required to process the complicated operations in real time. That is, it is difficult to realize embedded system.

The complexity of operations can be simplified by a method of reducing the number of support vectors. With the method, classification performance may be seriously lowered.

SUMMARY

One aspect of embodiments of the inventive concept is directed to provide a feature vector classification device which comprises an initial condition setting unit; a variable calculating unit configured to receive a training vector and to calculate an error and a weight according to setting of the initial condition setting unit; a loop deciding unit configured to determine whether re-calculation is required, based on a comparison result between the calculated error and an error threshold; and a hyperplane generating unit configured to generate a hyperplane when an end signal is received from the loop deciding unit.

In example embodiments, an error calculated by the variable calculating unit is a normalized mean square error.

In example embodiments, the variable calculating unit expands and calculates the training vector.

Another aspect of embodiments of the inventive concept is directed to provide a feature vector classification method comprising setting an initial condition; receiving a training vector; selecting features of the training vector one by one to calculate an error and a weight; determining an error, satisfying a specific condition, from among the calculated errors; and comparing the specific error value with an error threshold to judge whether or not to generate a hyperplane.

In example embodiments, the initial condition includes the error threshold and a minimum feature number of the training vector.

In example embodiments, comparing the specific error value with an error threshold to judge whether or not to generate a hyperplane comprises iteratively calculating an error and a weight when the specific error value is larger than the error threshold, iteratively calculating an error and a weight including increasing a feature number of the training vector to further select one feature of the training vector.

In example embodiments, comparing the specific error value with an error threshold to judge whether or not to generate a hyperplane comprises generating a hyperplane using the selected features and the calculated weight with respect to the specific error, when the specific error value is smaller than the error threshold.

In example embodiments, the error satisfying a specific condition is an error having a minimum value from among the calculated errors.

In example embodiments, the error is a normalized mean square error.

In example embodiments, the feature vector classification method further comprises setting a criticality upon setting of the error threshold.

In example embodiments, the feature vector classification method further comprises generating a comparison error using the minimum error, the error threshold being compared with the comparison error instead of the minimum error.

In example embodiments, the training vector is expanded and calculated.

In example embodiments, the error and the weight are calculated when a distribution of the training vector is a Gaussian distribution.

DETAILED DESCRIPTION

FIG. 1is a flowchart illustrating a feature vector classifying method according to an embodiment of the inventive concept. A vector classifying method inFIG. 1may be based on an SVM algorithm. The SVM may be based on structural risk minimization to classify feature vectors by a class unit.

Referring toFIG. 1, in operation S10, a training vector may be received to classify feature vector. Herein, the training vector may be a sample vector that is previously investigated to classify classes. A set X of N training vectors may be expressed by the following equation 1.
X={(x1, y1), (x2, y2) . . . (xN, yN)},xiε R˜(1)

In the equation 1, ximay indicate a training vector having d features. Each feature may be an element indicating a previously normalized feature to classify vectors, and yimay indicate a class of a training vector xi.

In operation S20, a support vector and its weight may be selected from a training vector using a predetermined kernel algorithm. The support vector may be a vector for determining a hyperplane (or, a decision surface) selected between training vectors.

In operation S30, a hyperplane for classifying a feature vector may be generated using the support vector and the weight. Herein, the hyperplane may be a weighted combination formed of a sum of support vectors multiplied with the weight. Thus, it is necessary to calculate a support vector and a corresponding weight to make a hyperplane using the SVM. A process of generating the hyperplane to classify feature vectors may be referred to a training process.

A linear support vector machine (hereinafter, referred to as LSVM) may be the simplest kernel algorithm. The complexity of calculation on a training process using the LSVM may be proportional to the product of the number of support vectors and a support vector dimension. Thus, although a simple structure is used, the number of support vectors or the dimension must be reduced to shorten a time taken at a feature vector classification process. However, a decrease in the number of support vectors may cause a sharp decrease in the accuracy of a hyperplane function. Another embodiment of the inventive concept may be related to propose an algorithm in which the dimension of a training vector used to solve the above-described problem is minimized to reduce the complexity of calculation and the efficiency is simultaneously improved.

FIG. 2is a conceptual diagram schematically illustrating a feature vector classification device according to another embodiment of the inventive concept.

Referring toFIG. 2, a feature vector classification device according to another embodiment of the inventive concept may include an initial condition setting unit110, a variable calculating unit120, a loop deciding unit130, and a hyperplane generating unit140.

The initial condition setting unit110may be configured to set an initial condition of a training process. The initial condition setting unit110may set an error threshold, and may set an initial value k on number of features of training vector to be used for hyperplane generation. The initial condition setting unit110may also set an initial value of an error value t and a criticality χ.

The error threshold may be a reference value for determining whether or not to generate the hyperplane after training is ended. The lower the error threshold, the higher the classification accuracy of the generated hyperplane. However, the lower the error threshold, the longer a time taken to calculate a training process.

The value k may be a dimension of a training vector to be used to generate the hyperplane. That is, the value k may indicate the number of features of a training vector to be used to generate the hyperplane. The larger the value k, the higher the complexity. On the other hand, the larger the value k, the higher the classification performance An initial value of the k may be set to ‘1’ when it is not set by the initial condition setting unit110.

The value t may be an error value, and may indicate the accuracy of judgment. The value t may be calculated through the mean square error. An initial value of the t may be set to ‘∞’ when it is not set by the initial condition setting unit110.

The value χ may be a constant for determining the criticality between a false positive probability and miss detect probability. A detection feature of the hyperplane may be adjusted by controlling the value χ.

The variable calculating unit120may receive values set by the initial condition setting unit110. The variable calculating unit120may receive a training vector. The variable calculating unit120may calculate a weight α on a training vector for hyperplane generation and a corresponding value t within the set values. The weight may be calculated such that the generated hyperplane has a minimum mean square error (hereinafter, referred to as MSE).

Upon selecting of (k−1) features, a weight on a training vector may be previously calculated with respect to the feature number k of the training vector used at a current loop. The variable calculating unit120may further select a new training vector feature (e.g., an mth feature). The variable calculating unit120may calculate values α and t respect to the selected k features. The variable calculating unit120may perform the above-described operation with respect to all selectable features.

In example embodiments, it is assumed that there are two vector classes: TRUE and FALSE. At this time, a TRUE vector and a FALSE vector may be distributed according to the Gaussian distribution. Herein, the TRUE vector may be such a vector that a class is TRUE, and the FALSE vector may be such a vector that a class is FALSE. The following equation 2 may indicate an error value t that is calculated to have a minimum MSE. However, the inventive concept is not limited thereto.

In the equation 2, an error value t may be calculated using a normalized MSE. The smaller the error value t, the higher the accuracy of judgment. Thus, it is necessary to set the error value t to a possible small value for improvement of classification efficiency of the hyperplane.

In the equation 2, NTmay indicate the number of TRUE vectors. NFmay indicate the number of FALSE vectors. fN,Tmay indicate a decision variable of an nth TRUE vector, and fn,Fmay indicate a decision variable of an nth FALSE vector. fTmay be a mean value of decision variables of the TRUE vectors fN,T. fFmay be a mean value of decision variables of the FALSE vectors fn,F. The decision variable may be used to judge whether a vector is TRUE or FALSE.

It is assumed that the variable calculating unit120further selects an mth feature of a training vector in addition to (k−1) features. fn,T(k)may be a decision variable of an nth FALSE vector when the number of features of a training vector is k. fn,F(k)may be a decision variable of an nth FALSE vector when the number of features of a training vector is k. The decision variables fn,T(k)and fn,F(k)may be calculated according to the following equation 3 with respect to decision variables fn,T(k−1)and fn,F(k−1)of a previous loop ((k−1) features).
fn,T(k)=fn,T(k−1)+αgn,m,T, fn,F(k)=fn,F(k−1)+αgn,m,F(3)

In the equation 3, αgn,m,Tmay indicate a value of an mth feature of an nth TRUE vector, and αgn,m,Fmay indicate a value of an mth feature of an nth FALSE vector. α may be a weight on an nth vector. When the number of features of a current training vector is k, fTand fFmay be calculated according to the following equations 4, 5, and 6.

In the equations 4, 5, and 6, fT(k)may be a mean value of a decision variable of TRUE vectors fn,T(k)when the number of features of a current training vector is k. fF(k)may be a mean value of a decision variable of FALSUE vectors fn,F(k)when the number of features of a current training vector is k.

Thus, an error value t and a weight value α on a hyperplane decided by an added feature may be expressed by the following equations 7 and 8.

In the equations 7 and 8, a, b, c, q, and s may be variables defined for ease of calculation, and may be expressed by the following equations 9 to 13, respectively.

In the equations 9 to 13, Hm,T, Hm,F, Gm,T(k−1), and Gm,F(k−1)may be expressed by the following equations 14 to 17.
Hm,T=gn,m,T−gm,T(14)
Hm,F=gn,m,F−gm,F(15)
Gm,T(k−1)=fn,T(k−1)−fT(k−1)(16)
Gm,F(k−1)=fn,F(k−1)−fF(k−1)(17)

The variable calculating unit120may calculate an error value t and a corresponding weight α when a feature is added with respect to a feature of a training vector that is not selected previously. The variable calculating unit120may judge a minimum error tminhaving a minimum value from among calculated error values t, and may judge a feature m and a weight αm.

The loop deciding unit130may compare the minimum error tminwith a designated error threshold. When the minimum error tminis larger than the designated error threshold, the loop deciding unit130may provide the variable calculating unit120with a command for increasing a feature number k of a predetermined training vector. In connection with the changed value k, the variable calculating unit120may repeat the above-described calculation of values α and t in response to the command from the loop deciding unit130.

If the minimum error tminis smaller than the error threshold, the loop deciding unit130may provide the hyperplane generating unit140with the calculated weight a on the selected feature. The hyperplane generating unit140may generate a hyperplane using the provided information, and a training process may be ended.

It is difficult to judge whether an error value converges on a desired result, based on a comparison result between the minimum error tminand the error threshold. Thus, the loop deciding unit130may calculate a comparison error tdinstead of the minimum error. The comparison error tdmay be a difference between the minimum error tminand a minimum error t_prev of a previous loop (when a feature number of a training vector is (k−1)). The loop deciding unit130may compare the comparison error tdwith the error threshold to judge whether an error value converges on a desired result. Thus, it is possible to obtain a stable result.

Thus, the feature vector classification device100of the inventive concept may be configured to increase a feature number of a training vector to be used to generate a hyperplane one by one until a desired accuracy is obtained. At this time, a feature may be added such that a minimum error gradually increases. As a result, the feature vector classification device100of the inventive concept may provide a hyperplane with low complexity and high accuracy through a minimum training vector dimension.

Also, when a training vector dimension (i.e., a feature number of a training vector to be used) is reduced, a calculation time may be shortened, while the performance is lowered compared with SVM. For this reason, there may be required a method for compensating for the above-described drawback. When a training vector is provided to a variable calculating unit120, it may be expanded and used without using of an original training vector. Thus, the performance may be improved. For example, when an original training vector is [(x)], it may be expanded into [(x), (x)2, (x)3, e(x), etc.].

FIG. 3is a flowchart illustrating a feature vector classification method according to an embodiment of the inventive concept. In operation S110, an initial condition of a training process may be set. The initial condition may include an error threshold th, a feature number k of a training vector to be used, and an error t. A criticality χ can be included in the initial condition.

In operation S120, a training vector may be received to generate a hyperplane. At this time, the training vector can be expanded over a previously set value.

When a feature number of a training vector to be used is (k−1), a weight and an error may be calculated in advance. In operation S130, a feature may be selected under the condition that a feature (e.g., an mth feature) is added. In operation S140, a weight having a minimum MSE on the selected features and a corresponding error may be calculated as described above. In operation S150, there may be judged whether the above-described operation is performed with respect to all features of a training vector that is not selected in advance.

Then, an error value, having the smallest value, from among the calculated error values may be selected (minimum error tmin). A feature and a weight corresponding to the minimum error may be judged in operation S160.

In operation S170, the minimum error may be compared with a predetermined error threshold. When the error threshold is smaller than the minimum error, the method proceeds to operation S175, in which a value k increases by one. Afterwards, the method proceeds to operation S130.

When the error threshold is larger than the minimum error, the method proceeds to operation S180, in which whether a desired condition is achieved is judged and a hyperplane is generated using the calculated weight.

FIG. 4is a flowchart illustrating a feature vector classification method according to another embodiment of the inventive concept. A feature vector classification method inFIG. 4may be similar to that inFIG. 3except that a comparison error is used instead of a minimum error, and similar operations are thus marked by similar reference numerals. As described above, the accuracy of a feature vector classification method may be improved by calculating a comparison error instead of a minimum error. Operation S210may further include setting an initial value of a previous minimum error t_prev. Also, in operation S270, a comparison error may be calculated instead of a minimum error, and a calculated result may be compared with an error threshold. Also, operation S275may further include substituting a current minimum error tminwith the previous minimum error t_prev.

FIG. 5is a table illustrating parameters used to measure the complexity of calculation using a HOG-LBP descriptor.

FIG. 6is a table illustrating the number of multiplication operations when HOG and HOG-LBP descriptors are used according to parameters inFIG. 5. Herein, a manner according to the inventive concept may be referred to as AddBoost. Referring toFIG. 6, compared with a conventional LSVM manner, the number of operations performed according to a manner of the inventive concept may be reduced over about 64%.

FIG. 7is a diagram illustrating a simulation result of a miss detection rate on a false positive per window. InFIG. 7, K may indicate a feature number of a training vector, and X may indicate the number of training vectors. Referring toFIG. 7, compared with a conventional LSVM, a classification method of the inventive concept may show an excellent result with respect to both HOG-LBP and HOG.