Pattern discrimination method and apparatus using the same

• US 5,109,431 A
• Filed: 05/21/1990
• Issued: 04/28/1992
• Est. Priority Date: 09/22/1988
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Funabashi, Motohisa, Nishiya, Takushi, Kera, Kazuo
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/526,000
• Time in Patent Office: 708 Days
• Field of Search: 382/21, 382/30, 382/34, 382/47, 382/9, 382/48, 382/16, 382/25, 364/715.07, 364/715.01, 364/807
• US Class Current: 382/209
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/471 using approximation functions
• CPC Class Codes: G06V 10/752 Contour matching

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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 σ

₁, τ

₂, . . . , τ

_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₂ (τ

_i) and g₀ (τ

_i) from the convolution at the feature points τ

_i (i=1, 2, . . . , k), an expression

space="preserve" listing-type="equation">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₁ (t) and h_k (t) respectively passing the estimation values f(τ

₁) and f(τ

_k) of the input pattern in respective ranges 0≦

t≦

τ

₁ and τ

_k ≦

t≦

T to compute estimation values f(0) and f(T) of both ends of the input pattern from expressions

space="preserve" listing-type="equation">f(0)=h.sub.1 (0)

space="preserve" listing-type="equation">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##

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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

space="preserve" listing-type="equation">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.

14. 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.

15. 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

16. An apparatus according to claim 13 wherein the computation of said fourth submeans is achieved according to an expression ##EQU33## where, A₁, A₂, 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).

17. 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).

18. 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.

19. 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.

20. 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 τ

₁, τ

₂, . . . , τ

_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₂ (τ

_i) and g₀ (τ

_i) from the convolution at the feature points τ

_i (i=1, 2, . . . , k), an expression

space="preserve" listing-type="equation">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₁ (t) and h_k (t) respectively passing the estimation values f(τ

_i) and f(τ

_k) of the input pattern in respective ranges 0≦

t≦

τ

₁ and τ

_k ≦

t≦

T to compute estimation values f(0) and f(T) of both ends of the input pattern from expressions

space="preserve" listing-type="equation">f(0)=h.sub.1 (0)

space="preserve" listing-type="equation">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##