Source: http://www.google.com/patents/US5452399?dq=7,453,150
Timestamp: 2013-12-05 19:46:27
Document Index: 336851581

Matched Legal Cases: ['art 410', 'art 412', 'art 410', 'art 412', 'art 412', 'art 410', 'art 412', 'art 412', 'art 410', 'art 410', 'art 410', 'art 410']

Patent US5452399 - Method and apparatus for input classification using a neuron-based voting scheme - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsThe present invention is a classification method and apparatus for classifying an input into one of a plurality of possible outputs. The invention generates a feature vector representative of the input. The invention then calculates a distance measure from the feature vector to the center of each neuron...http://www.google.com/patents/US5452399?utm_source=gb-gplus-sharePatent US5452399 - Method and apparatus for input classification using a neuron-based voting schemePublication numberUS5452399 APublication typeGrantApplication numberUS 08/176,075Publication dateSep 19, 1995Filing dateDec 30, 1993Priority dateJun 19, 1992Fee statusPaidAlso published asDE69329218D1, DE69329218T2, DE69333664D1, DE69333664T2, DE69333811D1, DE69333811T2, EP0574937A2, EP0574937A3, EP0574937B1, EP0944021A2, EP0944021A3, EP0944021B1, EP1199675A1, EP1199675B1, US5638491, US5664067, US5974404Publication number08176075, 176075, US 5452399 A, US 5452399A, US-A-5452399, US5452399 A, US5452399AInventorsMichael C. MoedOriginal AssigneeUnited Parcel Service Of America, Inc.Patent Citations (29), Non-Patent Citations (42), Referenced by (6), Classifications (16), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for input classification using a neuron-based voting schemeUS 5452399 AAbstract The present invention is a classification method and apparatus for classifying an input into one of a plurality of possible outputs. The invention generates a feature vector representative of the input. The invention then calculates a distance measure from the feature vector to the center of each neuron of a plurality of neurons, where each neuron is associated with one of the possible outputs. The invention then selects each neuron that encompasses the feature vector in accordance with the distance measure. The invention then determines a vote for each possible output, where the vote is the number of selected neurons that are associated with each possible output. If the vote for one of the possible outputs is greater than all other votes for all other possible outputs, then the invention selects that possible output as corresponding to the input. Otherwise, if the vote for one of the possible outputs is not greater than all other votes for all other possible outputs, then the invention identifies the neuron that has the smallest distance measure of all other neurons. If that smallest distance measure is less than a specified value, then the invention selects the possible output associated with that identified neuron as corresponding to the input.
CLASSIFICATION SYSTEM Referring now to FIG. 1(a), there is shown a bitmap representation of a nominal letter "O". When the classification system of the present invention classifies optically acquired character images, each character image to be classified may be represented by an input bitmap, an (m preferred embodiment, the classification system of the present invention generates a vector in a k-dimensional feature space from information contained in each input bitmap. Each feature vector F has feature elements f.sub.j, where 0≦j≦k-1. The dimension of the feature space, k, may be any integer greater than one. Each feature element f.sub.j is a real value corresponding to one of k features derived from the input bitmap.
In a preferred embodiment of the present invention, the neurons are hyper-ellipses in the k-dimensional feature space. A hyper-ellipse is any hyper-volume defined by Equation (1), where (m=2) and (A=1). More particularly, a hyper-ellipse is defined by the function: ##EQU3## where c.sub.j define the hyper-ellipse center point, b.sub.j are the hyper-ellipse axis lengths, and the values g.sub.j that satisfy Equation (3) define the points that lie within or on the hyper-ellipse boundary. When all of the axes are the same length, the hyper-ellipse is a hyper-sphere. In a preferred embodiment of the present invention, in at least one of the neurons, at least two of the axes are of different length. By way of example, there is shown in FIG. 2 elliptical neuron 1, having center point (c.sub.0.sup.1, c.sub.1.sup.1) and axes b.sub.0.sup.1, b.sub.1.sup.1 of different length. In a preferred embodiment, the axes of the neurons are aligned with the coordinate axes of the feature space. Those skilled in the art will understand that other neurons having axes that do not all align with the feature-space axes are within the scope of the invention.
Means 316 acts as a tie-breaker for the second and third potential voting outcome in which no outright vote-leader exists, either because of a tie or because the feature vector lies inside no neurons. To break the tie, means 316 selects that neuron x which is "closest" in elliptical distance to feature vector F and compares r.sub.x to a specified threshold value θ.sup.m. If (r.sub.x ≦θ.sup.m) then means 318 selects the output character associated with neuron x as corresponding to the input character bitmap. Otherwise, the tie is not broken and classification system 300 selects no character for the input image. A "no-character-selected" result is one of the possible outputs from classification system 300. For example, if classification system 300 is designed to recognize capital letters and the input image corresponds to the number "7", a no-character-selected result is an appropriate output.
Threshold value θ.sup.m may be any number greater than 1 and is preferably about 1.25. As described earlier, when feature vector F is inside neuron x, then (r.sub.x &lt;1), and when feature vector F is outside neuron x, then (r.sub.x &gt;1). If the voting result from means 310 is a tie for the most non-zero votes, then means 316 will select the output character associated with the encompassing neuron having a center which is "closest" in elliptical "distance" feature vector F. Alternatively, if there are no encompassing neurons, means 316 may still classify the input bitmap as corresponding to the output character associated with the "closest" neuron X, if (r.sub.x &lt;θ.sup.m). Using a threshold value θ.sup.m of about 1.25 establishes a region surrounding each neuron used by means 316 for tie-breaking. In FIG. 2, feature vector F.sub.h will be classified as character "C" if the "distance" measure r.sub.4 is less than the threshold value θ.sup.m ; otherwise, no character is selected.
Referring now to FIG. 4, there is shown a schematic diagram of classification system 400 of the present invention for classifying inputs as corresponding to a set of s possible outputs. Classification system 400 may perform part of the processing performed by classification system 300 of FIG. 3. Classification system 400 accepts feature vector F, represented by feature elements (f.sub.0, f.sub.1, . . . , f.sub.k-1), and generates values q.sup.t and q.sup.m that act as pointers and/or flags to indicate the possible output to be selected. Classification system 400 includes four subsystem levels: input level 402, processing level 404, output level 406, and postprocessing level 408.
B.sup.x =(b.sub.0.sup.x, b.sub.1.sup.x, . . . , b.sub.k-1.sup.x).sup.T,(5)
C.sup.x =(c.sub.0.sup.x, c.sub.1.sup.x, . . . , c.sub.k-1.sup.x).sup.T.(6)
Output level 406 includes two parts: output-total part 410 and output-minimize part 412. Output-total part 410 contains the set O.sup.t of s output processing units o.sub.n.sup.t, and output-minimize part 412 contains the set O.sup.m of s output processing units o.sub.n.sup.m, where n runs from 0 to s-1, where s is also the number of possible outputs for which classification system 400 has been trained. For example, when classifying capital letters, s=26. Each processing unit pair (o.sub.n.sup.t, o.sub.n.sup.m) is associated with only one possible output and vice versa.
Connection matrix W.sup.m represents the connections between processing level 404 and output-minimize part 412 of output level 406 and is related to connection matrix W.sup.t An entry w.sub.nx.sup.m in connection matrix W.sup.m will have a value of 1 for every entry w.sub.nx.sup.t in connection matrix W.sup.t that is not zero Otherwise, entry w.sub.nx.sup.m will have a value of 0.
Each output processing unit o.sub.n.sup.t in output-total part computes an output value o.sub.n.sup.t where: ##EQU5## where the function T(r.sub.x) returns the value 0 if (r.sub.x &gt;1); otherwise, it returns the value 1. In other words, the function T(r.sub.x) returns the value 1 if elliptical processing unit e.sub.x of processing level 404 is activated. Output processing unit o.sub.n.sup.t counts the votes for the possible output with which it is associated and outputs the total. Output-total part 410 of output level 406 is associated with means 306 and means 310 of classification system 300.
Similarly, each output processing unit o.sub.n.sup.m in output-minimize part 412 computes an output value o.sub.n.sup.m where: ##EQU6## where the function "MIN" returns the minimum value of (w.sub.nx.sup.m r.sub.x) over all the elliptical processing units e.sub.x. Therefore, each output processing unit o.sub.n.sup.m examines each of the elliptical processing units e.sub.x to which it is connected and outputs a real value equal to the minimum output value from these elliptical processing units. Output-minimize part 412 of output level 406 is associated with means 308 of classification system 300.
Postprocessing level 408 includes two postprocessing units p.sup.t and p.sup.m. Postprocessing unit p.sup.t is connected to and receives input from every output processing unit o.sub.n.sup.t of output-total part 410 of output level 406. Postprocessing unit p.sup.t finds the output processing unit o.sub.n.sup.t that has the maximum output value and generates the value q.sup.t. If output processing unit o.sub.n.sup.t of output-total part 410 has an output value greater than those of all the other output processing units of output-total part 410, then the value q.sup.t is set to n--the index for that output processing unit. For example, when classifying capital letters n may be 0 for "A" and 1 for "B" etc. Otherwise, the value q.sup.t is set to -1 to indicate that output-total part 410 of output level 406 did not classify the input. Postprocessing unit p.sup.t of postprocessing level 408 is associated with means 312 of classification system 300.
Classification of the input is completed by analyzing the values q.sup.t and q.sup.m. If (q.sup.t ≠1), then the input is classified as possible output q.sup.t of the set of s possible outputs. If (q.sup.t =-1) and (q.sup.m ≠-1), then the input is classified as possible output q.sup.m of the set of s possible outputs. Otherwise, if both values are -1, then the input is not classified as any of the s possible outputs.
PROPORTIONAL SHRINKING ALGORITHM In alternative preferred embodiment, training system spatially adjusts the boundary of a hyper-elliptical neuron to exclude a particular feature vector by shrinking proportionally along one or more axes. Means 510 and 522 of training system 500 may perform proportional shrinking by calculating the vector ΔB of axis length changes Δb.sub.j, where: ##EQU10## where f.sub.0 -c.sub.0 is the absolute value of (f.sub.0 -c.sub.0); F-C is the magnitude of the vector difference between F and C; c.sub.j and b.sub.j define the center point and axis lengths, respectively, of the neuron to be adjusted; f.sub.j are the elements of the feature vector to be excluded from that neuron; and α and γ.sub.j may be constants. The new axis lengths b.sub.j.sup./ for the adjusted neuron are calculated by:
b.sub.j.sup./ =b.sub.j +&#916;b.sub.j                     (22)
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3701095 *Sep 14, 1970Oct 24, 1972Japan Broadcasting CorpVisual feature extraction system for characters and patternsUS3950733 *Jun 6, 1974Apr 13, 1976Nestor AssociatesInformation processing systemUS4044243 *Jul 23, 1976Aug 23, 1977Nestor AssociatesInformation processing systemUS4326259 *Mar 27, 1980Apr 20, 1982Nestor AssociatesSelf organizing general pattern class separator and identifierUS4599693 *Jan 16, 1984Jul 8, 1986Itt CorporationProbabilistic learning systemUS4954963 *Mar 2, 1989Sep 4, 1990Texas Instruments IncorporatedNeural network and systemUS5010512 *Jan 12, 1989Apr 23, 1991International Business Machines Corp.Neural network having an associative memory that learns by exampleUS5033006 *Mar 7, 1990Jul 16, 1991Sharp Kabushiki KaishaSelf-extending neural-networkUS5054093 *Apr 8, 1988Oct 1, 1991Cooper Leon NParallel, multi-unit, adaptive, nonlinear pattern class separator and identifierUS5058180 *Apr 30, 1990Oct 15, 1991National Semiconductor CorporationNeural network apparatus and method for pattern recognitionUS5060278 *May 15, 1990Oct 22, 1991Ricoh Company, Ltd.Pattern recognition apparatus using a neural network systemUS5067164 *Nov 30, 1989Sep 10, 1991At&T Bell LaboratoriesHierarchical constrained automatic learning neural network for character recognitionUS5086479 *Jun 28, 1990Feb 4, 1992Hitachi, Ltd.Information processing system using neural network learning functionUS5119438 *Mar 9, 1990Jun 2, 1992Sharp Kabushiki KaishaRecognizing apparatusUS5181171 *Sep 20, 1990Jan 19, 1993Atlantic Richfield CompanyAdaptive network for automated first break picking of seismic refraction events and method of operating the sameUS5214715 *Jan 31, 1991May 25, 1993Trustees Of Boston UniversityPredictive self-organizing neural networkUS5214744 *Dec 14, 1990May 25, 1993Westinghouse Electric Corp.Method and apparatus for automatically identifying targets in sonar imagesUS5218646 *Feb 8, 1991Jun 8, 1993U.S. Philips Corp.Classification procedure implemented in a hierarchical neural network, and hierarchical neural networkUS5239594 *Feb 6, 1992Aug 24, 1993Mitsubishi Denki Kabushiki KaishaSelf-organizing pattern classification neural network systemUS5245697 *Apr 22, 1991Sep 14, 1993Kabushiki Kaisha ToshibaNeural network processing apparatus for identifying an unknown image pattern as one of a plurality of instruction image patternsUS5247584 *Jan 9, 1992Sep 21, 1993Bodenseewerk Geratetechnik GmbhSignal processing unit for classifying objects on the basis of signals from sensorsUS5251268 *Aug 9, 1991Oct 5, 1993Electric Power Research Institute, Inc.Integrated method and apparatus for character and symbol recognitionUS5260871 *Jul 31, 1991Nov 9, 1993Mayo Foundation For Medical Education And ResearchMethod and apparatus for diagnosis of breast tumorsUS5265192 *Sep 20, 1990Nov 23, 1993Atlantic Richfield CompanyMethod for the automated editing of seismic traces using an adaptive networkJPH0233687A * Title not availableJPH0238588A * Title not availableJPH0242392A * Title not availableJPH02300876A * Title not availableJPS62133589A * Title not available* Cited by examinerNon-Patent CitationsReference1"Learning Systems Based on Multiple Neural Networks," Nestor, Inc. Providence, R.I.2"Learning Systems Based on Multiple Neural Networks," Nestor, Inc., 1988 (14 pages).3 *1989 IEEE 13th Annual Int l. Computer SW and Applications Conf., Sep. 20 22 1989, pp. 672 679, authors Tsu chang Lee and Allen M. Peterson, Title Implementing a Self Development Neural Network Using Doubly Linked Lists .41989 IEEE 13th Annual Int'l. Computer SW and Applications Conf., Sep. 20-22 1989, pp. 672-679, authors Tsu-chang Lee and Allen M. Peterson, Title "Implementing a Self-Development Neural Network Using Doubly Linked Lists".5 *1991 IEEE Int. Symp. on Circuits and Systems, Vol 1/5, 11 June 1991, Singapore, Page 356-359, XP000384785, Yoshikazu Miyanaga, Makoto Teraoka, and Koji Tochinai, "Parallel and Adaptive Clustering Method Suitable for a VLSI System."6 *1991 IEEE Int. Symp. on Circuits and Systems, Vol. 2/5, 11 June 1991, Singapore, page 1176-1179, XP000370414, I-Chang Jou et al., "A Hyperellipsoid Neural Network for Pattern Classification Section."7 *1992 IEEE Int l. Joint Conf. on Neural Networks, Jun. 7 11 1992, pp. 850 855, vol. 4 authors Wilson X. Wen, Huan Liu, and Andrew Jennings, Title Self Generating Neural Networks .81992 IEEE Int'l. Joint Conf. on Neural Networks, Jun. 7-11 1992, pp. 850-855, vol. 4 authors Wilson X. Wen, Huan Liu, and Andrew Jennings, Title "Self-Generating Neural Networks".9Authors: Sheldon Gruber and Leda Villalobos, title "Neural Network Based Inspection of Machined Surfaces Using Laser Scattering", SPIE vol. 1265 Industrial Inspection II (1990); pp. 85-93.10 *Authors: Sheldon Gruber and Leda Villalobos, title Neural Network Based Inspection of Machined Surfaces Using Laser Scattering , SPIE vol. 1265 Industrial Inspection II (1990); pp. 85 93.11Bachmann et al., "A relaxation model for memory with high storage density," Proc. Natl. Acad. Sci. USA, vol. 84, pp. 7529-7531, Nov. 1987, Biophysics.12 *Bachmann et al., A relaxation model for memory with high storage density, Proc. Natl. Acad. Sci. USA, vol. 84, pp. 7529 7531, Nov. 1987, Biophysics.13Hirai et al, "Position Independent Pattern Matching by Neurol Network", IEEE Transactions on Systems, Mon & Cybernehes, vol. 20 No. 4 Jul. 1990, pp. 816-825.14 *Hirai et al, Position Independent Pattern Matching by Neurol Network , IEEE Transactions on Systems, Mon & Cybernehes, vol. 20 No. 4 Jul. 1990, pp. 816 825.15Kavuri, "Solving the Hidden Node Problem in Networks with Ellipsoidal Units and Related Issues," pp.l I-775-780, Jun. 8, 1992.16 *Kavuri, Solving the Hidden Node Problem in Networks with Ellipsoidal Units and Related Issues, pp.l I 775 780, Jun. 8, 1992.17Kelly et al., "An Adaptive Algorithm for Modifying Hyperellipsoidal Decision Surfaces," pp. IV-196-201, Jun. 11, 1992.18 *Kelly et al., An Adaptive Algorithm for Modifying Hyperellipsoidal Decision Surfaces, pp. IV 196 201, Jun. 11, 1992.19Kim et al., "Self Organizing Neural Networks for Unsupervised Pattern Recognition", 10th Annual Int'l Phoenix Conf on Computers & Communications, Mar. 27-30 1991, pp. 39-45.20 *Kim et al., Self Organizing Neural Networks for Unsupervised Pattern Recognition , 10th Annual Int l Phoenix Conf on Computers & Communications, Mar. 27 30 1991, pp. 39 45.21 *Learning Systems Based on Multiple Neural Networks, Nestor, Inc. Providence, R.I.22 *Learning Systems Based on Multiple Neural Networks, Nestor, Inc., 1988 (14 pages).23Namatame, "A Connectionist Learning with High-Order Functional Networks and Its Internal Representation," Tools for Artificial Intelligence, pp. 542-547, Oct. 1989.24 *Namatame, A Connectionist Learning with High Order Functional Networks and Its Internal Representation, Tools for Artificial Intelligence, pp. 542 547, Oct. 1989.25Omatu et al., "Neural Network Model for Alphabetical Letter Recognition," International Neural Network Conference, pp. 19-22, Paris, Jul. 9-13, 1990.26 *Omatu et al., Neural Network Model for Alphabetical Letter Recognition, International Neural Network Conference, pp. 19 22, Paris, Jul. 9 13, 1990.27 *Pattern Recognition letters, Vol. 13, No. 5, May 1992, Amsterdam, NL, pages 325-329, XP000278617, Gek Sok Lim et al., "Adaptive quadratic neural nets."28Reilly et al., "A Neural Model for Category Learning," Biological Cybernetics, pp. 35-41, 1982.29Reilly et al., "Learning System Architectures Composed of Multiple Learning Modules," IEEE First Int'l. Conf. on Neural Networks, pp. II-495-503, Jun. 1987.30 *Reilly et al., A Neural Model for Category Learning, Biological Cybernetics, pp. 35 41, 1982.31 *Reilly et al., Learning System Architectures Composed of Multiple Learning Modules, IEEE First Int l. Conf. on Neural Networks, pp. II 495 503, Jun. 1987.32Reilly, Scofield, Elbaum, and Cooper, "Learning System Architectures Composed of Multiple Learning Modules," IEEE First International Conference on Neural Networks, San Diego, Calif., Jun. 21-24, 1987, pp. II-495 to II-503.33 *Reilly, Scofield, Elbaum, and Cooper, Learning System Architectures Composed of Multiple Learning Modules, IEEE First International Conference on Neural Networks, San Diego, Calif., Jun. 21 24, 1987, pp. II 495 to II 503.34Rumelhart et al., "Learning Internal Representations by Error Propagation," Parallel Distributed Processing, vol. 1, pp. 318-362, 1986.35 *Rumelhart et al., Learning Internal Representations by Error Propagation, Parallel Distributed Processing, vol. 1, pp. 318 362, 1986.36S. Gruber, "Neural network based inspection of machined surfaces using laser scattering," Industrial Inspection II, vol. 1265, 12 Mar. 1990, The Hague, NL, pp. 85-94.37 *S. Gruber, Neural network based inspection of machined surfaces using laser scattering, Industrial Inspection II, vol. 1265, 12 Mar. 1990, The Hague, NL, pp. 85 94.38Scofield et al., "Pattern Class Degeneracy in an Unrestricted Storage Density Memory," 1987 IEEE Conference on Neural Information Processing Systems, Nov. 1987.39 *Scofield et al., Pattern Class Degeneracy in an Unrestricted Storage Density Memory, 1987 IEEE Conference on Neural Information Processing Systems, Nov. 1987.40Specht, "Probabalistic Neural Networks for Classification, Mapping, or Associative Memory," 1988 IEEE International Conference on Neural Networks, pp. I-525-532.41 *Specht, Probabalistic Neural Networks for Classification, Mapping, or Associative Memory, 1988 IEEE International Conference on Neural Networks, pp. I 525 532.42 *Traitement Du Signal, Vol. 8, No. 6, 1991, Paris, FR, Pages 423-430, XP000360600, Joel Minot and Philippe Gentric, "Authentification dynamique de signatures par reseaux de neurones."* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5974404 *Jun 24, 1997Oct 26, 1999United Parcel Service Of America, Inc.Method and apparatus for input classification using a neural networkUS5995953 *Jul 16, 1997Nov 30, 1999International Business Machines CorporationMethod for verification of signatures and handwriting based on comparison of extracted featuresUS6049793 *Nov 13, 1997Apr 11, 2000Tomita; KenichiSystem for building an artificial neural networkUS7275047 *Oct 31, 2003Sep 25, 2007Cerebrus Solutions Ltd.Method and apparatus for interpreting informationUS8260730 *Mar 14, 2005Sep 4, 2012Hewlett-Packard Development Company, L.P.Method of, and system for, classification count adjustmentWO1998021637A2 *Nov 14, 1997May 22, 1998Kenichi TomitaSystem for building an artificial neural network* Cited by examinerClassifications U.S. Classification706/20, 382/156International ClassificationG06F15/18, G06K9/66, G06T7/00, G06K9/62, G06N3/00, G06N99/00Cooperative ClassificationG06K9/6273, G06K9/6223, G06K9/6272, G06K9/6274European ClassificationG06K9/62C1D1C1, G06K9/62C1D1C, G06K9/62B1P1F, G06K9/62C1D1RLegal EventsDateCodeEventDescriptionFeb 26, 2007FPAYFee paymentYear of fee payment: 12Dec 30, 2002FPAYFee paymentYear of fee payment: 8Dec 7, 1998FPAYFee paymentYear of fee payment: 4Apr 23, 1996CCCertificate of correctionRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google