US5109431A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pattern discrimination method and apparatus using the same
Assignee: Hitachi Ltd
•
Filing: 1990-05-21
•
Granted: 1992-04-28
•
Expires: 2010-05-21
Abstract
Abstract An apparatus for comparing a data pattern with standard patterns to discriminate the data pattern retrieves vector series of the standard patterns associated with the data pattern. Categorized names are assigned to data of the vector series so as to be respectively associated with elements of the data pattern, thereby determining a similarity degree and a scale factor between the vector series.
Inventors
- 👤 Takushi Nishiya
- 👤 Motohisa Funabashi
- 👤 Kazuo Kera
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 06:08
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/001; G06T7/00; G06T7/20; G06T7/246; G06V; G06V10/00; G06V10/40; G06V10/46; G06V10/70; G06V10/74; G06V10/75; G06V10/752; G06V10/469; G06V10/471
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
258 words
An apparatus for discriminating a pattern comprising: (a) first means for extracting, from an input pattern, first sequential data by use of sum of products representing said input pattern; (b) second means for extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) third means for extracting, from a plurality of standard patterns, second sequential data by use of a sum of products representing the plurality of standard patterns; (d) fourth means for extracting, from the second sequential data, second features represented as a sequence of pairs of an internal and a variation between any concavity and convexity among data of the second sequential data, thereby representing the plurality of standard patterns; (e) a standard pattern storage for storing therein vector series representing the plurality of standard patterns; (f) an input pattern storage for storing therein vector series representing the input pattern; (g) retrieve means for searching the vector series of the input pattern to retrieve vector series of the standard patterns therefrom; and (h) similarity degree means for computing a similarity degree and a scale factor between the vector series retrieved by said retrieve means and the vector series of the standard patterns stored in said standard pattern storage and for determining standard patterns having a larger similarity degree and having a scale factor within a preset range with respect to the retrieved vector series.
Claim 2
Independent Claim
258 words
An apparatus for discriminating a pattern comprising: (a) first means for extracting, from an input pattern, first sequential data by use of sum of products representing said input pattern; (b) second means for extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) third means for extracting, from a plurality of standard patterns, second sequential data by use of a sum of products representing the plurality of standard patterns; (d) fourth means for extracting, from the second sequential data, second features represented as a sequence of pairs of an internal and a variation between any concavity and convexity among data of the second sequential data, thereby representing the plurality of standard patterns; (e) a standard pattern storage for storing therein vector series representing the plurality of standard patterns; (f) an input pattern storage for storing therein vector series representing the input pattern; (g) retrieve means for searching the vector series of the input pattern to retrieve vector series of the standard patterns therefrom; and (h) similarity degree means for computing a similarity degree and a scale factor between the vector series retrieved by said retrieve means and the vector series of the standard patterns stored in said standard pattern storage and for determining standard patterns having a larger similarity degree and having a scale factor within a preset range with respect to the retrieved vector series.
Claim 3
Dependent Claim
62 words
An apparatus according to claim 1 wherein said similarity degree means includes store means for storing therein numbers assigned to standard patterns each having a similarity degree not less than a predetermined value and a scale factor within a preset range centered on one, said numbers being arranged in association with numbers assigned to the retrieved vector series of the input pattern.
Claim 4
Dependent Claim
48 words
An apparatus according to claim 1 further comprising store means for storing names assigned to respective vectors of the standard patterns, said names representing with words characteristics thereof in association with a variation in the value of the vector series, said words being fundamentally increasing, flat, and decreasing.
Claim 5
Dependent Claim
34 words
An apparatus according to claim 1 further comprising a neural net in which the vector series respectively of the standard and input patterns are supplied and which achieves a retrieval between the vector series.
Claim 6
Dependent Claim
247 words
A pattern discriminating apparatus comprising: (a) first means for extracting, from an input pattern, first sequential data by use of sum of products representing the input pattern; (b) second means for extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) third means for extracting, from a plurality of standard patterns, second sequential data by use of sum of products representing the plurality of standard patterns; (d) fourth means for extracting, from the second sequential data, second features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the second sequential data, thereby representing the plurality of standard patterns; (e) fifth means for storing therein the first sequential data of the input pattern and the second sequential data of a plurality of standard patterns; (f) sixth means for comparing the first and second sequential data to retrieve, from the input pattern vector series, a sequence of vector series including a vector series of one of the standard patterns; and (g) seventh means for computing a similarity degree, represented by using sum of inner products, and a scale factor representing a scale reduction ratio between the vector series retrieved by said sixth means and the vector series of the standard patterns stored in said fifth means.
Claim 7
Dependent Claim
247 words
A pattern discriminating apparatus comprising: (a) first means for extracting, from an input pattern, first sequential data by use of sum of products representing the input pattern; (b) second means for extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) third means for extracting, from a plurality of standard patterns, second sequential data by use of sum of products representing the plurality of standard patterns; (d) fourth means for extracting, from the second sequential data, second features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the second sequential data, thereby representing the plurality of standard patterns; (e) fifth means for storing therein the first sequential data of the input pattern and the second sequential data of a plurality of standard patterns; (f) sixth means for comparing the first and second sequential data to retrieve, from the input pattern vector series, a sequence of vector series including a vector series of one of the standard patterns; and (g) seventh means for computing a similarity degree, represented by using sum of inner products, and a scale factor representing a scale reduction ratio between the vector series retrieved by said sixth means and the vector series of the standard patterns stored in said fifth means.
Claim 8
Dependent Claim
251 words
An apparatus according to claim 5 wherein said second means includes: a) means for computing a convolution of an input pattern f(t), (t=0, 1, 2, . . . , T) with an expression ##EQU26## to get a result ##EQU27## and for extracting from the result points having positive and negative maximal values as feature points σ 1 , τ 2 , . . . , τ k of the input pattern; b) average means for computing a convolution based on an expression ##EQU28## to obtain a result ##EQU29## and for attaining a mean value of the input pattern at each said feature point; c) means for computing, based on results g 2 (τ i ) and g 0 (τ i ) from the convolution at the feature points τ i (i=1, 2, . . . , k), an expression f(τ.sub.i)=g.sub.0 (τ.sub.i)W.sub.0 (0)+g.sub.2 (τ.sub.i)W.sub.2 (0) to obtain estimation values f(τ i ) of the input pattern at the feature points τ i ; d) means for determining regression lines h 1 (t) and h k (t) respectively passing the estimation values f(τ 1 ) and f(τ k ) of the input pattern in respective ranges 0≦t≦τ 1 and τ k ≦t≦T to compute estimation values f(0) and f(T) of both ends of the input pattern from expressions f(0)=h.sub.1 (0) f(T)=h.sub.k (T); and e) means for computing a vector series a i (i=1, 2, . . . , k+1) representing a broken line as an approximation of the input pattern from expressions ##EQU30##
Claim 9
Dependent Claim
115 words
An apparatus according to claim 5 wherein the vector series of the standard patterns stored in said fifth means are assigned with names depending on a gradient of vectors associated with features of the respective vectors thereof and said sixth means comprises: a) name means for assigning to the vector series of the input pattern, in association with the features of the respective vectors thereof, the same names assigned to the vector series of the standard patterns; and b) name retrieve means for retrieving a portion from a sequence of the names associated with the vector series of the input pattern, said portion including a sequence of names of vector series of the standard patterns.
Claim 10
Dependent Claim
80 words
An apparatus according to claim 5 wherein said fourth means includes means for computing the similarity degree and the scale factor from expressions ##EQU31## where, (,) designates an inner product of vectors, s i (i=1, 2, . . . , m) is a vector series of the standard patterns, and a ij (j=1, 2, . . . , n i ) stands for a vector series of the input pattern associated with the standard pattern vector series s i .
Claim 11
Dependent Claim
60 words
An apparatus according to claim 5 wherein in an operation to store the standard patterns in said fifth means, a desired standard pattern is drawn on an input device having a pattern drawing capability such that said second means conducts the processing on the pattern to attain a vector series, thereby loading said fifth means with the obtained vector series.
Claim 12
Dependent Claim
27 words
An apparatus according to claim 5 comprising means for transforming input information into a symbol representing a contour of a pattern and for accumulating their the symbol.
Claim 13
Dependent Claim
50 words
An apparatus according to claim 10 including means for converting a control state of a process into a symbol representing a pattern registered to a standard pattern dictionary and for retrieving a preceding process state represented with a symbol identical to the symbol of the pattern, thereby conducting a comparison.
Claim 14
Dependent Claim
38 words
An apparatus according to claim 11 comprising means for computing a selection or a computation of rules beforehand stored for control by use of a symbol representing a process state, the symbol being outputted from said converting means.
Claim 15
Independent Claim
536 words
An apparatus for discriminating a correspondence relationship between two patterns respectively transformed into vector series comprising: (a) first means for extracting, from an input pattern, first sequential data by use of sum of products representing the input pattern; (b) second means for extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) third means for extracting, from a plurality of standard patterns, second sequential data by use of sum of products representing the plurality of standard patterns; (d) fourth means for extracting, from the second sequential data, second features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the second sequential data, thereby representing the plurality of standard patterns; (e) fifth means for storing therein the first sequential data of the input pattern and the second sequential data of a plurality of standard patterns; (f) sixth means for comparing the first and second sequential data to retrieve, from the input pattern vector series, a sequence of vector series including a vector series of one of the standard patterns; and (g) seventh means for computing a similarity degree, represented by using sum of inner products, and a scale factor representing a scale reduction ratio between the vector series retrieved by said sixth means and the vector series of the standard patterns stored in said fifth means, wherein said fifth means comprises: a) first submeans for storing therein a matching degree S(i, j) (i=1, 2, . . . , m; j=1, 2, . . . , n) between a vector series a i (i=1, 2, . . . , m) constituting a pattern and a vector series b j (j=1, 2, . . . , n) configuring another pattern; b) second submeans for storing therein a correspondence degree U(i, j), (i=1, 2, . . . , m; j=1, 2, . . . , n) between a vector a i of the pattern (1) and a vector b j of the pattern (2); c) third submeans for storing therein outputs V(i,j), i=1, 2, . . . , m; j=1, 2, . . . , n) obtained through an appropriate transformation V(i,j)=f[U(i,j)] conducted on the respective values of the correspondence degrees U(i,j) stored in said subsecond means; d) fourth submeans for updating the values of the correspondence degree U(i,j) by use of the matching degree S(i,j) loaded in said fist submeans, the correspondence degree U(i,j) stored in said second submeans, and the output V(i,j) stored in said third submeans; and e) fifth submeans operative after the processing of said second, third, and fourth submeans is interatively accomplished an appropriate number of times for attaining a correspondence relationship between the vector series a i (i=1, 2, . . . , m) of the pattern (1) and the vector series b j (j=1, 2, . . . , n) of the pattern (2) by use of the correspondence degree U(i,j), (i=1, 2, . . . , m; j=1, 2, . . . , n) stored in said second submeans.
Claim 16
Independent Claim
536 words
An apparatus for discriminating a correspondence relationship between two patterns respectively transformed into vector series comprising: (a) first means for extracting, from an input pattern, first sequential data by use of sum of products representing the input pattern; (b) second means for extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) third means for extracting, from a plurality of standard patterns, second sequential data by use of sum of products representing the plurality of standard patterns; (d) fourth means for extracting, from the second sequential data, second features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the second sequential data, thereby representing the plurality of standard patterns; (e) fifth means for storing therein the first sequential data of the input pattern and the second sequential data of a plurality of standard patterns; (f) sixth means for comparing the first and second sequential data to retrieve, from the input pattern vector series, a sequence of vector series including a vector series of one of the standard patterns; and (g) seventh means for computing a similarity degree, represented by using sum of inner products, and a scale factor representing a scale reduction ratio between the vector series retrieved by said sixth means and the vector series of the standard patterns stored in said fifth means, wherein said fifth means comprises: a) first submeans for storing therein a matching degree S(i, j) (i=1, 2, . . . , m; j=1, 2, . . . , n) between a vector series a i (i=1, 2, . . . , m) constituting a pattern and a vector series b j (j=1, 2, . . . , n) configuring another pattern; b) second submeans for storing therein a correspondence degree U(i, j), (i=1, 2, . . . , m; j=1, 2, . . . , n) between a vector a i of the pattern (1) and a vector b j of the pattern (2); c) third submeans for storing therein outputs V(i,j), i=1, 2, . . . , m; j=1, 2, . . . , n) obtained through an appropriate transformation V(i,j)=f[U(i,j)] conducted on the respective values of the correspondence degrees U(i,j) stored in said subsecond means; d) fourth submeans for updating the values of the correspondence degree U(i,j) by use of the matching degree S(i,j) loaded in said fist submeans, the correspondence degree U(i,j) stored in said second submeans, and the output V(i,j) stored in said third submeans; and e) fifth submeans operative after the processing of said second, third, and fourth submeans is interatively accomplished an appropriate number of times for attaining a correspondence relationship between the vector series a i (i=1, 2, . . . , m) of the pattern (1) and the vector series b j (j=1, 2, . . . , n) of the pattern (2) by use of the correspondence degree U(i,j), (i=1, 2, . . . , m; j=1, 2, . . . , n) stored in said second submeans.
Claim 17
Dependent Claim
31 words
An apparatus according to claim 13 wherein the matching degree S(i,j) stored in said first submeans is an inner product between the vector a i and the vector b j .
Claim 18
Dependent Claim
31 words
An apparatus according to claim 13 wherein the output V(i,j) stored in said third submeans is attained from the correspondence degree U(i,j) based on V(i,j)=f[U(i,j)] by use of a function ##EQU32##
Claim 19
Dependent Claim
46 words
An apparatus according to claim 13 wherein the computation of said fourth submeans is achieved according to an expression ##EQU33## where, A 1 , A 2 , and H(i,j) respectively designate appropriate constants and W(i,j;i',j') denotes a weight coefficient indicating a relationship between V(i',j';t) and U(i,j;t+1).
Claim 20
Independent Claim
254 words
A method of discriminating an input pattern with respect to standard patterns in an apparatus having a storage, compute means, and retrieve means, to identify a pattern, said method comprising the steps of: (a) extracting, from an input pattern, first sequential data by use of sum of products representing the input pattern; (b) extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) extracting, from a plurality of standard patterns, second sequential data by use of sum of products representing the plurality of standard patterns; (d) extracting, from the second sequential data, second features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the second sequential data, thereby representing said plurality of standard patterns; (e) storing the first sequential data of the input pattern and the second sequential data of the plurality of standard patterns in said storage; (f) comparing the first and second sequential data to retrieve, from the input pattern vector series, a sequence of vector series including a vector series of one of the standard patterns; and (g) computing a similarity degree, represented by using sum of inner products, and a scale factor representing a scale reduction ratio between the vector series retrieved by step (f) and the vector series of the standard patterns stored in step (e).
Claim 21
Independent Claim
254 words
A method of discriminating an input pattern with respect to standard patterns in an apparatus having a storage, compute means, and retrieve means, to identify a pattern, said method comprising the steps of: (a) extracting, from an input pattern, first sequential data by use of sum of products representing the input pattern; (b) extracting, from the first sequential data, first features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the first sequential data, thereby representing the input pattern as a vector series; (c) extracting, from a plurality of standard patterns, second sequential data by use of sum of products representing the plurality of standard patterns; (d) extracting, from the second sequential data, second features represented as a sequence of pairs of an interval and a variation between any concavity and convexity among data of the second sequential data, thereby representing said plurality of standard patterns; (e) storing the first sequential data of the input pattern and the second sequential data of the plurality of standard patterns in said storage; (f) comparing the first and second sequential data to retrieve, from the input pattern vector series, a sequence of vector series including a vector series of one of the standard patterns; and (g) computing a similarity degree, represented by using sum of inner products, and a scale factor representing a scale reduction ratio between the vector series retrieved by step (f) and the vector series of the standard patterns stored in step (e).
Claim 22
Dependent Claim
52 words
A method according to claim 17 further including storing numbers assigned to standard patterns having a similarity degree not less than a preset value and a scale reduction ratio in a predetermined range centered on one, the numbers being associated with numbers assigned to the retrieved vector series of the input pattern.
Claim 23
Dependent Claim
45 words
A method according to claim 17 further including determining a name for each vector of the vector series of the standard pattern in association with a variation of values thereof, the name representing with a word such a feature thereof as increasing, flat, or decreasing.
Claim 24
Dependent Claim
413 words
A pattern discriminating apparatus comprising: a) first means for extracting from an input pattern features associated with concavity and convexity thereof and for approximating the input pattern to a broken line based on the features, thereby representing the input pattern as a vector series constituting the broken line; b) second means for storing therein the input pattern and a plurality of standard patterns to be compared therewith in a form of vector series respectively representing folded lines, said broken lines being associated with symbols; c) third means for comparing the vector series of the input pattern from said first means and the vector series of the standard patterns from said second means to retrieve from the input pattern vector series a sequence of vector series including vector series of the standard patterns; and d) fourth means for computing a similarity degree and a scale factor between the vector series retrieved by said third means and the vector series of the standard patterns stored in said second means, wherein said first means includes: (1) means for computing a convolution of an input pattern f(t), (t=0, 1, 2, . . . , T) with an expression ##EQU34## to get a result ##EQU35## and for extracting from the result points having positive and negative maximal values as feature points τ 1 , τ 2 , . . . , τ k of the input pattern; (2) average means for computing a convolution based on an expression ##EQU36## to obtain a result ##EQU37## and for attaining a mean value of the input pattern at each said feature point; (3) means for computing, based on the results g 2 (τ i ) and g 0 (τ i ) from the convolution at the feature points τ i (i=1, 2, . . . , k), an expression f(τ.sub.i)=g.sub.0 (τ.sub.i)W.sub.0 (O)+g.sub.2 (W.sub.2 (O) to obtain estimation values f(τ i ) of the input pattern at the feature points τ i ; (4) means for determining regression lines h 1 (t) and h k (t) respectively passing the estimation values f(τ i ) and f(τ k ) of the input pattern in respective ranges 0≦t≦τ 1 and τ k ≦t≦T to compute estimation values f(0) and f(T) of both ends of the input pattern from expressions f(0)=h.sub.1 (0) f(T)=h.sub.k (t); and (5) means for computing a vector series a i (i=1, 2, . . . , k+1) representing a broken line as an approximation of the input pattern from expressions ##EQU38##
Claim 25
Dependent Claim
413 words
A pattern discriminating apparatus comprising: a) first means for extracting from an input pattern features associated with concavity and convexity thereof and for approximating the input pattern to a broken line based on the features, thereby representing the input pattern as a vector series constituting the broken line; b) second means for storing therein the input pattern and a plurality of standard patterns to be compared therewith in a form of vector series respectively representing folded lines, said broken lines being associated with symbols; c) third means for comparing the vector series of the input pattern from said first means and the vector series of the standard patterns from said second means to retrieve from the input pattern vector series a sequence of vector series including vector series of the standard patterns; and d) fourth means for computing a similarity degree and a scale factor between the vector series retrieved by said third means and the vector series of the standard patterns stored in said second means, wherein said first means includes: (1) means for computing a convolution of an input pattern f(t), (t=0, 1, 2, . . . , T) with an expression ##EQU34## to get a result ##EQU35## and for extracting from the result points having positive and negative maximal values as feature points τ 1 , τ 2 , . . . , τ k of the input pattern; (2) average means for computing a convolution based on an expression ##EQU36## to obtain a result ##EQU37## and for attaining a mean value of the input pattern at each said feature point; (3) means for computing, based on the results g 2 (τ i ) and g 0 (τ i ) from the convolution at the feature points τ i (i=1, 2, . . . , k), an expression f(τ.sub.i)=g.sub.0 (τ.sub.i)W.sub.0 (O)+g.sub.2 (W.sub.2 (O) to obtain estimation values f(τ i ) of the input pattern at the feature points τ i ; (4) means for determining regression lines h 1 (t) and h k (t) respectively passing the estimation values f(τ i ) and f(τ k ) of the input pattern in respective ranges 0≦t≦τ 1 and τ k ≦t≦T to compute estimation values f(0) and f(T) of both ends of the input pattern from expressions f(0)=h.sub.1 (0) f(T)=h.sub.k (t); and (5) means for computing a vector series a i (i=1, 2, . . . , k+1) representing a broken line as an approximation of the input pattern from expressions ##EQU38##
References Cited (Backward Citations)
DE63765C
Cited
US3942169A
Cited
US4566124A
Cited
US4731858A
Cited
US4748675A
Cited
US4905295A
Cited
US4961231A
Cited
US4982342A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-04-28 | 1995-10-28 | 1996-04-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-04-28 | 1999-10-28 | 2000-04-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-04-28 | 2003-10-28 | 2004-04-28 | $7700.00 | Window Closed / Lapsed |