Check-actuated control mechanisms – Including means to test validity of check – Having means to test surface configuration
Reexamination Certificate
2001-08-30
2003-07-08
Walsh, Donald P. (Department: 3651)
Check-actuated control mechanisms
Including means to test validity of check
Having means to test surface configuration
C194S302000, C382S135000, C382S136000, C382S137000, C382S225000
Reexamination Certificate
active
06588571
ABSTRACT:
The invention relates to a method and apparatus for classifying items. The invention is concerned especially with the classification of coins or banknotes.
Coins and banknotes inserted into mechanisms, such as vending machines, change machines and the like, are classified, on the one hand according to value, and/or on the other hand, between originals and copies or counterfeits thereof. Various methods of performing such classifications are known. As one example, described in GB 2 238 152 A, the contents of which are incorporated herein by reference. For example, measurements are taken from an inserted coin which represent different features of the coin, such as material and the thickness. Those measurements are then compared with respective stored pairs of values, each set of pair of values corresponding to a respective acceptable denomination of coin. When each measured value falls within the respective range for a given denomination, the inserted coin is classified as belonging to that denomination.
In the type of classification discussed above, the measured values can be regarded as elements in a feature vector, and the acceptable measurements for different denominations correspond to regions in feature space, known as acceptance regions. In the example given above, the feature space is two-dimensional, and acceptance regions are rectangles, but the feature space can have any number of dimensions, with corresponding complexity in the acceptance regions. For example, GB 2 254 949 A, the contents of which are incorporated herein by reference, describes ellipsoidal acceptance regions in three-dimensional feature space.
Other examples of methods and apparatus for classifying bills and coins are described in EP 0 067 898 A, EP 0 472 192 A, EP 0 165 734 A. Other methods of classification include the use of neural networks, as described, for example, in EP 0 553 402 A and EP 0 671 040 A, the contents of which are also incorporated herein by reference.
A significant problem in the classification of coins is the difficulty of separating different denominations. The population distributions of the different denominations of interest may be such that it is not possible easily to define appropriate acceptance boundaries with which adequately separate the denominations. Another problem is that in order to achieve adequate separation, it may be necessary to consider feature vectors having a large number of elements, which makes it more difficult to understand the various distributions and thus more difficult to obtain suitable acceptance boundaries. These problems are akin to general classification problems in data analysis which has been studied and have led to various different techniques including statistical methods.
As an example of a statistical method of data analysis, principal component analysis (“PCA”), is a method whereby data expressed in one space is transformed using a linear transformation into a new space, where most of the variation within the data can be explained using fewer dimensions than in the first space. The method of PCA involves finding the eigenvectors and eigenvalues of the covariance matrix of the variables. The eigenvectors are the axes in the new space, with the eigenvector having the highest eigenvalue being the first “principal component” and so on in decreasing size. Details of PCA can be found in textbooks on multivariate analysis, such as “Introduction to Multivariate Analysis” by Chatfield and Collins, see Chapter 4.
Another method of data analysis for classification purposes is linear discriminant analysis (“LDA”). LDA is useful when it is known that the data falls into separate groups. LDA aims to transform the data into a new space so as to maximize the distance between the centre of each group of data as projected onto axes in the new space and also to minimize the variance of each group along the axes. Methods for doing this are described in, for example, “Introduction to Statistical Pattern Recognition” by Fukunaga (“Fukunaga”). In one example, the maximisation is performed by finding a linear transformation which maximises the value of the trace of C
−1
V where V is the inter-class covariance matrix and C is the covariance matrix of all samples. As explained in Fukunaga, this amounts to finding the eigenvectors and eigenvalues of C
−1
V. The eigenvectors are the axes of the new space. As described in the paper, when there are N classes, the new space has N−1 dimensions.
In many situations, neither PCA nor LDA will give adequate separation of the groups of data. A further method of data analysis is non-linear component analysis (NCA), which is based on PCA. In NCA, the data is projected into a new space using a non-linear mapping, and then PCA is performed in the new space. Details of NCA are given in the article “Nonlinear component Analysis as a Kernel Eigenvalue Problem” by Bernhard Scholkopf, Alexander Smola and Klaus-Robert Muller, Neural Computation 10, 1299-1319 (1998). (“Scholkopf”.)
A problem with NCA is that the dimension of the non-linear space may be very large, and so the number of principal components is also very large. For a given problem, it is not known how many principal components are needed for a good classification.
Generally, the invention relates to a method of deriving a classification for classifying items of currency comprising measuring known samples for each class and deriving features vectors from the measured samples, mapping the feature vectors to a second space in which there is a clearer separation of the different classes and deriving a separating function using the separation in the second space.
More specifically, the present invention provides a method of deriving a classifier for classifying items of currency into two or more classes comprising measuring known samples for each class and deriving feature vectors from the measured samples, selecting a function corresponding to a mapping of the feature vector space to a second space, mapping feature vectors to image vectors, and deriving coefficients representing N−1 axes, where N is the number of classes, in the second space, obtaining values representing the projections of the image vectors for the measured samples onto the N−1 axes, and using those values to derive a separating function for separating the classes equivalent to a separating function in the second space.
The invention also provides a method for classifying an item of currency comprising measuring features of the item, generating a feature vector from the measured values, and classifying the item using a classifying derived by a method according to any one of claims 1 to 6.
The invention also provides an apparatus for classifying items of currency comprising measuring means for measuring features of an item of currency, feature vector generating means for generating a feature vector from the measured values, and classifying means for classifying the item using a classifier derived according to the method of any one of claims 1 to 6.
The invention also provides an apparatus for classifying items of currency comprising measuring means for measuring features of an item of currency, feature vector generating means for generating a feature vector from the measured values, and classifying means for classifying the item using a function corresponding to a non-linear mapping of the feature vector space to a second higher-dimensional space, mapping feature vectors to image vectors, and coefficients representative of N−1 axes, where N is the number of classes that can be classified by the apparatus, in the second space, and a function equivalent to a separating function in the second space.
REFERENCES:
patent: 4386432 (1983-05-01), Nakamura et al.
patent: 5503262 (1996-04-01), Baudat et al.
patent: 5522491 (1996-06-01), Baudat et al.
patent: 5947255 (1999-09-01), Shimada et al.
patent: 6226408 (2001-05-01), Sirosh
patent: 2002/0117375 (2002-08-01), Baudat et al.
patent: 0 367 921 (1990-05-01), None
patent: 0 887 761 (1998-12-01), None
Bishop, C.M., “Neural Networ
Beauchaine Mark J
Walsh Donald P.
LandOfFree
Classification method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Classification method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classification method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3029477