Pattern Recognition Using Artificial Neural Network for Coin Validation

Devices for recognizing, identifying and validating objects such as coins are widely used in coin acceptor and coin rejecter mechanisms and many such devices are in existence and used on a regular basis. Such devices sense or feel the coin or other object as it moves past a sensing station and use this information in a device such as a microprocessor or the like to make a determination as to the genuinous, identity and validity of each coin. Such devices are very successful in accomplishing this. However, one of the problems encountered by such devices is the presence of variations in the same type of coin from batch to batch and over time and other variables including wear and dirt. These will cause changes, albeit small changes in some cases and from one coin type to another including in the U.S. and foreign coin markets. Such changes or variations can make it difficult if not impossible to distinguish between genuine and counterfeit coins or slugs where the similarities are relatively substantial compared to the differences.

The present invention takes a new direction in coin recognition, identification and validation by making use of artificial neural network (ANN) technology. This technology has not been used heretofore in devices for sensing, identifying, recognizing and validating coins such as the coins fed into a vending or like machine. The use of ANN has the advantage over known devices by constantly upgrading its parameters of recognition or fingerprint that is initially established for each coin denomination before the device is put in operation. In other words, as each new coin of the same or different type moves past the sensing means employed in the present device, the pattern of recognition that has been established for each such coin, over time, can be modified or "updated" so that any changes in the coins that are sensed over short or even over long periods of time are self-adjusting and this can greatly improve the quality of recognition, identification and validity evaluations thereby also making it possible to reduce the number of losses that are encountered by vending machines. It may also increase the number of valid coins that a machine will accept.

The present invention therefore represents a new use of an existing technology in a coin sensing environment which has not occurred in the past.

The present invention allows for the association of artificial neural network (ANN) technology to be used to determine recognition, identification and validity of metal objects such as coins by using the technology to update the parameters or weights used in establishing whether a coin is valid or not and to identify the type or denomination of coin it is.

In accordance with the present invention, a category representation of each object is established and if a sufficient match is made between the center of an established category representation and the pattern created by a new coin moving into the system for identification, then the coin will be identified as to its type or denomination and as to whether or not it is a valid coin all based on the similarities or dissimilarities between the center and the patterns.

With the present system it is recognized that each different coin denomination will have its own pattern and the same system can be used to recognize, identify and validate, or invalidate, coins of more than one denomination including coins of different denominations from the U.S. and foreign coinage systems.

The novelty of the present invention relates in large part to the signal processing and multi-frequency testing means and methods that are used. The signal processing involves extracting features from signals generated during passage of a coin and interpreting these signals in a pattern recognition process. Pattern recognition and neural network technologies are employed in the present device in a manner to increase the performance sensitivity without adding new or more complicated sensors. In a preferred embodiment of the present device two pairs of coils are programmed to be connected to result in four tank circuits (4 frequencies) using switching means such as reed switches to switch in and out parallel capacitors. This produces a relatively wide range of frequencies capable of covering a large range of coins including coins of many sizes and denominations.

The present device establishes different arbitrary boundaries for each different denomination coin to be distinguished and validated, and as a new coin moves along next to the sensors it produces signals in the tank circuits and optical sensors which are used to generate patterns. As far as validation is concerned two matters are addressed; first, to verify if the object or coin under test is valid or counterfeit, and, second, once it is determined to be a valid coin to determine its denomination. The number of categories into which an object or coin can be classified is usually known and samples are available for comparison and test purposes. Furthermore, each coin when magnetically and optically sensed will produce a distinctive feature vector, and these can be close to one another for some closely related objects or coins.

Pattern recognition has been employed in coin classification heretofore (Barlach) but the known methods of pattern recognition have been of limited value and typically have not been sufficiently reliable as a means to distinguish valid coins from others. The emergence of artificial neural network (ANN) technology has been demonstrated to be a powerful and reliable classifier in pattern recognition. For example, ANN has the capability to form a classifier pattern with any desired arbitrary and irregular shaped boundaries over a feature vector space. With prior devices the classification decisions that were made were thereof based on a sequence of boundary checking steps using limited extracted information. This problem is overcome by the present device which produces multiple frequency responses generated by uniquely controlled magnetic sensors. The manner in which the sensors are controlled to produce the multi-frequency outputs is important to the present invention. The present device includes the sensors, the signal conditioning circuits including the means for controlling the sensors, data acquisition means, feature processing and extraction means and the classifier means. The physical characteristics of the sensors may be of known construction such as shown in Hoorman U.S. Pat. No. 4,625,852 and Hoorman U.S. Pat. No. 4,646,904. The present device controls the sensors in a different way from prior controls and in so doing produces more different frequency outputs resulting in better identification and classification of coins or other objects. The present device takes this information and classifies the objects or coins into the requisite coin denominations or into counterfeits, slugs or other non genuine objects

It is a principal object of the present invention to provide improved means for recognizing, identifying and validating coins of one or more denomination.

Another object is to use artificial neural network (ANN) technology to identify and validate coins of the same or different denomination.

Another object is to provide relatively simple means for using ANN technology in a coin validation environment.

Another object is to increase the accuracy, reliability and consistency of coin recognition, coin identification and coin validation.

Another object is to use ANN classification means for the validation of coins and other monetary means.

Another object is the use of pattern recognition technology to reduce the domain of a feature space over which an ANN can be easily implemented and trained.

Another object is to be able to extract more information from a magnetic sensor device because of the way it is controlled when the information is produced including by the number of frequencies that are generated.

Another object is to use multi-frequency testing to generate patterns to represent objects.

These and other objects and advantages of the present invention will become apparent to those skilled in the art after considering the following detailed specification of preferred embodiments in conjunction with the accompanying drawings.

FIG. 1 is a schematic block diagram of a coin validation system constructed according to the present invention;

FIG. 2 is a side elevational view showing one arrangement for the locations of optical and magnetic sensors along a coin track for producing signal responses representative of certain characteristics of each coin as it passes.

FIG. 3 is a graph of pulse signals generated by spaced optical sensors as an object such as a coin moves past;

FIG. 4 is a damped sinusoidal signal of the type generated by a LC tank circuit;

FIG. 5 is a schematic circuit of a coil excited by an AC source when a coin is adjacent to it, said circuit being shown as a transformer circuit with a coin adjacent thereto;

FIG. 6 is a planar view showing various overlapping decision regions illustrating the boundaries formed by different classifier designs. The arbitrary and irregular boundary is employed in the present invention;

FIG. 7 is a side elevational view illustrating an artificial neuron which simulates a biological nerve cell;

FIG. 8 illustrates a two-layer artificial neural network;

FIG. 9 is a three layer artificial neural network with a "winner-take-all" output layer;

FIG. 10 is a block diagram of the ANN coin validation system showing the output of the feature vector circuit connected to the ANN validation means with the decision outputs; and

FIG. 11 is a block diagram of the circuit of the subject device with the appropriate legends on the circuit blocks.

The term multi-frequency indicates that the testing signal has more than one frequency component at different time intervals.

Referring to the drawings more particularly by reference numbers, number 20 in FIG. 1 refers to the sensors used in the present device. The sensors are mounted adjacent to a coin track 21 along which coins or other objects to be sensed move. The construction of the sensors 20 is important to the invention and will be described more in detail hereinafter.

The outputs of the sensors 20 typically include four signals of different frequencies which are fed to a signal preprocessing circuit 22, the outputs of which are fed to a feature extraction algorithm 24 constructed to respond to particular features of the signals produced by the sensors. The feature extraction algorithm 24 produces outputs that are fed to a cluster classifier device 26 and also to a switch 28 which has its opposite side connected to a neural network classifier circuit 30. The neural network classifier circuit 30 includes means for producing decision outputs based upon the inputs it receives.

The cluster classifier device 26 has an output on which signals are fed to a comparator circuit 32 which receives other inputs from an ellipsoid shaped raster or area 33. The outputs of the comparator circuit 32 are fed to the switch 28 for applying to the neural network classifier 30. The comparator 32 also produces outputs on lead 34 which indicate the presence of a rejected coin. This occurs when the comparator circuit 32 generates a comparison of a particular type. A description of the decisions produced on output 36 of the neural network classifier 30 will be described later.

The sensors 20 employed in the subject device are shown schematically in FIG. 2 and include two spaced optical sensors 40 and 42, located at spaced locations along the coin track 21, and two spaced magnetic sensors 46 and 48, also located at spaced locations along the coin track 21. The optical sensors 40 and 42 are shown spaced upstream respectively of the magnetic sensors 46 and 48 and therefore respond to movements of each coin along the coin track 21 just before the coin reaches the respective magnetic sensor 46 or 48. The optical sensors 40 and 42 monitor the coin track 21 and generate pulse signals as a coin blocks and unblocks their optical paths. These pulse signals provide coin chord size information and also synchronize the oscillations that takes place in the magnetic sensors 46 and 48 so that the signals from the coils in the magnetic sensors reflect the coin presence and generate signals that represent certain characteristics of each coin. The magnetic sensors may be of a known construction but are controlled to operate differently in the present circuit than in any known circuit. For example, each of the magnetic sensors 46 and 48 includes a pair of coils connected magnetically in aiding and opposing manner respectively under control of the operation of the respective optical sensor 40 or 42. When operating in the aiding and opposing manners each pair of coils oscillates at its respective natural frequency, and this occurs once the object or coins is present in the field of the respective sensor and in so doing provides magnetic information about the coin. The signals collected by the sensors 40 and 42 arc processed by the signal preprocessing means 22. Extraction of the most dominate and salient information about the coin occurs in the feature extraction circuit 24. A feature vector (FV) is formed by combining all of the preprocessed information, and this feature vector (FV) is then fed to the hyper ellipsoidal classifier circuit 26 which classifies the object or coin according to its denomination. If the object or coin is not classifiable by its denomination because it is a counterfeit coin or slug, the classifier circuit will produce an output from a comparator 32 that is used to reject the coin. This is done by producing a signal on lead 34. The classification of the coin takes place in the comparison means 32 which compares the output of the cluster classifier 26 with an ellipsoid shaped output received on another input to the comparator 33.

FIG. 3 shows examples of pulse signals that are generated by the optical sensors 40 and 42 as a coin moves down the coin track 21. When the first pulse is produced, a timer is energized commencing at time (t.sub.0), and subsequent pulses generated by the optical sensors interrupt the timer at times t.sub.1, t.sub.2, and t.sub.3 (FIG. 3.). The interrupt signals at times t.sub.1, t.sub.2 and t.sub.3 are associated with movements of the object under test and are used for further processing including for turning on the magnetic sensors 46 and 48 in particular manners and at particular times to produce particular output signals. The signals from the optical and magnetic sensors are transformed into "coin features" and are collected into a coin features vector (FV) for each coin. The time and magnetic characteristics of the signals are processed by "timers" 50 and "peak detector" circuits shown in FIG. 11. The peak detector outputs are converted into numerical values by an analog to digital converter circuit 52. The "timer" records the time intervals by which the optical elements are covered by each coin and these values are related to coin size and is one component of the coin feature vector.

The coin feature vector is presented to the ANN 30 which is a three layer network in the present device. The first layer FIGS. 7, 8 and 9, has two types of neurons. One type performs ellipsoidal clustering which outputs one or zero if the feature is located outside or inside the ellipsoid. The other neurons are feed forward reception neurons. They form an arbitrary decision region within the ellipsoid. The output of network is a single neuron sometimes called the "winner takes all" neuron 56. This is shown in FIG. 9 in the drawings.

Generally speaking only peak values of the damped sinusoidal wave form are collected to reduce the number of digitized data points to a manageable number. To accomplish this, a differentiator 54 is used to find the derivative of the voltage (V.sub.t) and this triggers the analogue-to-digital convertor 52 each time the output crosses zero. This way of handling the data simplifies the number of data points that need to be considered.

The signal preprocessing means 22 which receives the outputs of the magnetic sensors 46 and 48 may contain redundant and/or irrelevant material. The signal preprocessing means 22 extracts as much as possible of the more dominant and salient information from the signals, and from this information forms a discriminative feature vector (FV) that is used for classification purposes. The preprocessing step is an important step for increasing the efficiency of the classifiers 26 and 30. The information in the output of the signal preprocessor 22 contains several pieces of information including information as to the size and magnetic characteristics of the object or coin in question. Size information is obtained primarily from the optical signals produced by the optical sensors 40 and 42. The means for measuring distance or coin size may assume that the coin moves at a constant acceleration through the acceptor.

The damped sinusoidal waveforms generated by the tank circuits when a coin is present contain information which relates to the magnetic characteristics of the coin, i.e. the coin size, coin conductivity, permeability and the depth of penetration. Each damped sinusoidal wave form has several parameters of importance including parameters as to amplitude, damping factor, angular frequency and phase angle. Certain of these characteristics such as amplitude and phase angle are determined not only by the object under test but also by the initial condition of the tank circuit. This being so they are not good feature candidates because of their variances due to the initial conditions of the tank circuit. The other two parameters, namely, the damping factor and angular frequency are dependent upon tank circuit components only and are included in the feature vector (FV). It is preferred to choose fundamental features which are more directly related to the object or coin under test, if possible. These features are extracted from the output of the magnetic sensors. The magnetic sensors are able to detect subtle changes in the metal material of the coin or other object under test.

FIG. 5 illustrates how a pair of secondary circuit metal objects such as coins can be modeled as a secondary circuit in a transformer-like situation so that each has its own inductance L2 and its own series resistance R2. M.sub.12 is the mutual inductance between the coils L.sub.1 and L.sub.2, and k is the coefficient of coupling between the two coils. In the circuit of FIG. 5, L.sub.1 and R.sub.1 are constants in a particular validation unit and can be estimated as air parameters when no object or coin is present at the location of the coil. By contrast, L.sub.2 and R.sub.2 which relate to the coin, depend upon completing the material characteristics of the coin under test. Any subtle difference in material in the coin will directly and immediately change L.sub.2 and R.sub.2 and these subtle differences will be reflected in the outputs of the magnetic sensors as the coin moves by. The coin therefore forms a secondary circuit having its own inductance and resistance as shown in FIG. 5. The inductance and resistance of each tank circuit are constants in a particular unit and are known when no object is present. This means that even small changes in L and R will appear in the feature vector (FV). When a tank circuit is rung the shape of the damped sinusoidal waveform that is produced will depend on the capacitance, the inductance and the equivalent resistance of the coil. The damping factor and the angular frequencies can be determined mathematically, if we know the value of the capacitance, the inductance and the resistance. However, we don't know these values. Therefore Gauss least square means are used to estimate these parameters.

In a typical application the tank circuits are activated four times when an object or coin is present. This means that four changes in the resistance and in the inductance based on the different tank circuit characteristics or combinations will be produced and collected. This will also be based on the damping factors and frequencies of the respective tank circuits. These changes in resistance and inductance plus the changes in the cords of the damped waves produced constitute the feature vector (FV) for each object or coin under test. Thus each object or coin will have its own feature vector and the feature vector will distinctively represent that particular coin.

The cluster classifier 26 and the neural network classifier 30 are constructed to search for an optimal partition of a feature space S into c regions which we will call decision regions where c is the number of classes or decision regions in a feature space. The classifier should have the capability to correctly and/or meaningfully assign a class label to a feature vector (FV) in the feature space (S). A classifier design can be divided into two categories, one being supervised learning and the other unsupervised learning. In the present coin validation means supervised learning is employed since labeled samples are available, one for each different coin denomination. There are two kinds of decision regions defined in a coin feature space (S), one being acceptance regions and the other being rejection regions. If a feature vector (FV) falls in one of the acceptance regions the object associated with it is classified as a coin, otherwise it is rejected. The rejection region overlays almost the entire feature space except for a number of small acceptance regions.

FIG. 6 illustrates a two dimensional decision region. An ellipsoidal cluster forms a semi-regular partition region with abrupt boundaries in a feature space (S) while a neural network on the other hand constructs any arbitrary and irregular decision region in the ellipsoid. An ellipsoidal boundary is generally much better than a rectangular shaped one. Some regions in the pattern may have holes which cause discontinuous decision boundaries. The complimentary functions of these two region types produces a classifier which has very fine resolution at the decision border and irregularity in decision region geometry. In the case of coin validation means a data base of coins and counterfeits is created by initially inserting them into the validation system. Each record in the data base has an associated feature vector (FV), a label of some kind to identify a coin from a counterfeit, and a denomination if it is labeled as a coin. The number of records for each category is determined by the distribution and features of the feature vector (FV).

An ellipsoidal cluster E in a p-dimensional Euclidian space having a size r established in which the eccentricity and orientation of the cluster space or ellipsoid is determined. There is one ellipsoidal cluster for each coin category. It can be shown mathematically that the center of the ellipsoid is the average of all samples belonging to the same class and the axis of the ellipsoid is defined by the standard deviations of each element in the feature vector.

Once this information has been established, the distance of a point in the feature vector (FV) to the cluster can be determined. The distance as defined for these point are used to make preliminary decisions. For example, an object with a feature vector (FV) is a candidate for a certain class coin if the distance from the feature vector to the cluster is less than or equal to some distance. However this is not a final decision as to the coin's acceptability for several reasons. First, the real cluster geometry of the samples may form an ellipsoid whose axes are oblique to the coordination axes and the principal component method may be used to rotate the ellipsoid. Secondly, regardless of the first reason the decision region formed by an ellipsoid is still regarded as a semi-regular region and counterfeit overlapping volume may be observed within the ellipsoid. Therefore, an artificial neural network ANN is further used to alternate the decision region within the ellipsoid. This combination of a cluster and an ANN makes the training of the ANN much easier because the domain of a mapping on which an ANN is defined is much smaller than the entire feature space.

An artificial neural network is a collection of parallel processing elements called neurons linked by their synaptic weights. These neurons can be arranged in several layers. Designing a neural network for a pattern recognition application is to train the neural network to identify a partition in a feature space. Theoretically, as long as the number of neurons in the hidden layer is sufficiently large any vector input-output mapping can be realized by a multi-layer feed forward neural network. Supported by this theory, a decision region with arbitrary geometric boundaries can be realized by a neural network.

A neuron in an ANN simulates a nerve cell in a biological neural network (see FIGS. 7 and 8). In a feed forward multi-layer neural network, each neuron receives an input from its previous layer or from an input and transmits its output to the next layer or to the output. The knowledge about the external world is encoded in a neural networks' synaptic weight, and information retrieval is done by manipulation of these weights with the input or feature vector.

Back propagation is the most powerful learning algorithm to train a neural network (modify its synaptic weights) under a supervised learning manner. Back propagation is a gradient descent algorithm. Initially, all weights in a neural network are randomized between similar - and + values such as between -0.5 and +0.5. Learning starts with the presentation of an input-target pair. The neural network matches the given input to an output. Comparison between the target and the output generates an error vector. It is this error vector, by back propagation through all of the neurons, that modifies synaptic weights in an attempt to minimize the mean square error objective function .epsilon.. The gradient descent method repeatedly updates each weight, each updating being called a presentation and all presentations in a training set are termed a cycle. After being trained for a number of cycles, the neural network may reduce its error function to a minimum value. When this is done the network has been trained to discover the relationship between the input and target vectors in the training set.

The algorithm monitors learning as it proceeds so that learning may occur automatically when the partition space and the feature space have been discovered. This is accomplished by monitoring between the output of the neural network and the target with each presentation.

To avoid unnecessary computation, an error margin is introduced to the error between the neural network output and the target. This sets the error to zero before back propagation if the output is found to be within the margin of the target. In training a neural network it is sometimes possible to overshoot which indicates a larger learning rate and occurs when the error approaches zero or a very small value. There are ways to reduce the learning rate. One way is to decrease it at a certain fixed rate in the course of training. We choose the learning rate to be a certain percentage of the current error. Such methods are known and are not part of the present invention. It is also possible to use more than one ANN for the classification of all categories. This again is not at the heart of the invention.

After all of the neural networks have been trained, and such training is known the subject coin validation system is ready for classification. The signals with their distinctive features are then collected from the unknown object or coin and are formed into the feature vector (FV). The feature vector is first verified to see if it falls within an ellipse as defined by the mathematics of the system. The object or coin is rejected as being counterfeit if its feature vector is found not to fall in any ellipse. Otherwise it is assumed to be a valid coin. If not rejected the object or coin is considered as a candidate and the same feature vector is fed to the neural network and the output levels from the network are compared against each other. The object or coin is again subject to being rejected as counterfeit if the output value of the first neuron level is greater than that of the second neuron level. Otherwise it will be accepted as a valid coin belonging in a predetermined denomination or range of denominations.

It has been found by test of the coinage of several different countries including the United States, the United Kingdom and Germany that the various denominations can easily be separated in this manner. In addition, testing has shown that it is possible to solve the problem of different hardnesses with respect, for example, to the U.S. nickel vs. the Canadian nickel, the German DM vs. the U.K. 5 pence coin, the German DM vs. the Polish 20 zloty, the German DM vs. Australian 5 cent piece, and the U.K. 50 pence vs. the old U.K. 10 pence covered with foil. In all of these cases the similarities are substantial yet the separation process is effective. Thus the present invention presents a clustering of neural network devices in a coin validation systems. This novel application of ANN to a coin validation system has a number of advantages over existing coin mechanisms, and tests have demonstrated a more reliable and more flexible coin validation system using ANN.

The present system has self compensation capability by measuring air parameters against which all other features are compared. This significantly reduces performance variations among different units due to component deviations as well as environmental fluctuations. The dominant and salient features have been carefully selected and preprocessed and these features are only determined by the object under test. This means that a self-tuning or customer-tuned coin validator may be developed based on this technology. The present system in its preferred form, as stated, uses multi-frequency coin validation by capacitor switching in decaying oscillating tank circuits. The wide range of oscillation frequencies of the tank circuits covers almost the entire frequency band currently used in international acceptors. This means that the present system not only generates more features for discrimination but also makes it possible to produce a universal acceptor capable of classifying all coin denominations from various countries. Clustering such as ellipsoid clustering also relieves the requirements on training samples and simplifies the neural network training. The validation coin class for each coin is also narrowed which means that the counterfeit class occupies a large volume of the feature space.

Thus there has been shown and described novel means for separating coins or other objects from slugs or counterfeit coins, and it does so in a manner which enables the various coins to be identified as to validity, size, and denomination. It will apparent to those skilled in the art, however, that many changes, modifications, variations and other uses and applications of the present device are possible. All such changes, modifications, variations and other uses and applications which do not depart from the spirit and scope of the invention are deemed to be covered by the invention which is limited only by the claims which follow.