Image analysis – Pattern recognition
Reexamination Certificate
1994-12-02
2001-08-07
Tran, Phuoc (Department: 2621)
Image analysis
Pattern recognition
C382S159000
Reexamination Certificate
active
06272241
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is concerned with pattern recognition devices.
2. Related Art
Pattern recognition devices commonly receive, in digital form, an input pattern of bits which is then processed to produce a scalar value, or a number of such values, which are regarded as a vector. These may then be subjected to a thresholding operation to provide an output indicating the nature of an unknown pattern supplied to the device. Many such devices are learning devices, in that they are not constructed to recognize particular patterns but are, before use, supplied with training patterns, the output of the device being compared with information as to the nature of the pattern, or identifying a class to which it belongs, and the comparison result used as feedback to vary parameters stored within the device.
It is convenient to view such systems in terms of an input space and an output space. For example, one which receives a set of five scalar values and produces two scalar values may be considered as performing a mapping from a point in a five-dimensional input pattern space to a point in a two-dimensional output space.
One form of recognition device which has been proposed is the perceptron, which forms one or more weighted sums of a set of input values, the weighting factors being varied adaptively during the learning process. The main disadvantage of these is their inability to perform non-linear mappings from the input space to the output space, so that they cannot learn such apparently simple functions as the exclusive-or function. A solution to this problem is the multi-level percepton, where the output of a first layer of perceptrons supplies the input to a second layer; however, large amounts of training are required in order to learn quite simple non-linear mappings (i.e. convergence is slow), and this has made the application of multi-layer perceptions to real problems such as speech recognition very difficult.
Another form of recognition device is described in our European patent application Ser. No. 0183389B, and U.S. Pat. No. 4,782,459. This, as shown in
FIG. 1
, has an input store
1
in which an input vector having sixteen elements of 8-bits each are stored. Groups (“n-tuples”) of bits are taken to form n-bit addresses for each of a number of random access memories
2
, and the contents of the memory locations thereby addressed are added in an adder
3
to form a scalar output. During training, this output is compared in a subtractor
4
with the desired output input thereto, and the difference used to control updating of the memory contents. One application of the arrangement shown is as an echo canceller for telecommunications applications where the store
1
is in the form of a shift register receiving successive digitally coded temporal samples of a transmitted signal, the object of the device being to learn a mapping which models the echo characteristics of a transmission path.
As will be explained in greater detail below, the ability of such a recognition device to generalize from examples given in training depends to some extent upon the form in which the input data within the store
1
is coded. It is of course conventional to employ binary coding to represent digital values of a signal, but (as discussed in “Guide to pattern and recognition using random-access memories”- Aleksander and Stonham, computers and digital techniques, February 1979, Vol 2 No 1, Page 36 “6.3 coding of physical data”) this is not particularly suitable for this class of pattern recognition devices since signal values which are quite close in signal space are disproportionately far apart in Hamming distance. The authors there propose a Gray code (which employs the same number of bits as the binary code) to overcome this problem but note that this can lead to spurious results as widely differing input signal levels can be close in Hamming distance. They point out that the most suitable coding is a 1-in-N code (hereinafter referred to as a bar code), in which as many bits as there are signal levels are employed. This code suffers from neither of the above drawbacks. It is, however, very inefficient and can require a large amount of input space; for example, for input data having 256 levels (i.e. the typical output of an 8 bit digital to analog converter), a 256 bit wide input buffer is required—which is clearly impractical (the binary and Gray code versions require only 8 bits, of course).
SUMMARY OF THE INVENTION
The present invention therefore provides in a first aspect a pattern recognition apparatus comprising:
an input for receiving a set of digital values representing a pattern to be recognized;
a plurality of memories each having at least one address line for addressing locations therein, the address lines being connected to receive bits from a digital representation of the set of values; and
means for producing a composite output dependent on data read from the addressed locations of the memories; wherein the apparatus includes means for encoding the input values to form the said digital representation employing a redundant code which has a normalized Hamming distance to normalized signal distance relationship having a mean slope greater than 1 for signal distances up to a predetermined level of at least 10% of the maximum signal distance.
Preferably the slope is at least 1.5, more preferably at least 2.
Another aspect of the present invention provides a pattern recognition apparatus comprising:
an input for receiving a set of digital values representing a pattern to be recognized;
a plurality of memories each having at least one address line for addressing locations therein, the address lines being connected to receive bits from a digital representation of the set of values; and
means for producing a composite output dependent on data read from the addressed locations of the memories; wherein the apparatus includes means for encoding the input values to form the said digital representation using a code employing a number of bits which is:
i) greater than that which a binary code would require to represent an equal number of signal levels; and
ii) less than that number of signal levels; and being selected to have a higher monotonicity (as herein defined) than would such a binary code, irrespective of the magnitudes of said values.
As will be discussed below, the first aspect of the invention provides a pattern recognizer which has similar properties to a bar code recognizer but is physically practical to construct. The second aspect of the invention, (which preferably employs a coding which as above uses a realistically small number of bits) provides a recognition device which can learn complex mapping functions (as discussed below) yet maintains the good generalization properties of the bar code type recognizer.
Also provided according to the invention is a method of training an n-tuple recognizer using redundant coding of the above types. Other preferred features are as recited in the claims.
REFERENCES:
patent: Re. 26780 (1970-02-01), Klinikowski
patent: 2632058 (1953-03-01), Gray
patent: 2755459 (1956-07-01), Carbrey
patent: 3200339 (1965-08-01), Gorlin
patent: 3754238 (1973-08-01), Oswald
patent: 4386339 (1983-05-01), Henry et al.
patent: 4435823 (1984-03-01), Davis
patent: 4490847 (1984-12-01), Aleksander et al.
patent: 4694451 (1987-09-01), Adams
patent: 4733220 (1988-03-01), Knierim
patent: 4782459 (1988-11-01), Johnston
patent: 4797941 (1989-01-01), Lloyd et al.
patent: 4958375 (1990-09-01), Reilly et al.
patent: 5054093 (1991-10-01), Cooper et al.
patent: 0183389 (1986-06-01), None
patent: 0300648 (1989-01-01), None
Guide to Pattern Recognition using Random-access Memories Alexander & Stonham, Computers & Digital Techniques, Feb. 1979, pp. 29-40.
“A New Approach to Mainipulator Control: The Cerebellar Model Articulation Controller”, Albus, Trans. ASME, Sep. 1975, pp. 220-227.
“Data Storage in the Cerebellar Model Articulation Controller,” Albus, Transactions of the ASME, pp. 228-233.
“A Model of the Brain for Robot
British Telecommunications public limited company
Nixon & Vanderhye P.C.
Tran Phuoc
LandOfFree
Pattern recognition does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pattern recognition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern recognition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2502802