Method and apparatus for designing a highly reliable pattern recognition system

• US 5,940,535 A
• Filed: 10/31/1996
• Issued: 08/17/1999
• Est. Priority Date: 10/31/1996
• Status: Expired due to Term

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Huang, Yea-Shuan
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US08/741,740
• Time in Patent Office: 1,020 Days
• Field of Search: 382/201, 382/224, 382/259, 382/181, 382/182, 382/190, 382/192, 382/199, 382/200, 382/179
• US Class Current: 382/201
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection

Abstract

A design for a high reliability recognition system utilizes two optimized thresholds for each class k of a prototype data base. One threshold is a class region threshold CR_k and the other is a dis-ambiguity threshold DA_k. CR_k specifies a constrained region belonging to a class k, and DA_k corresponds to a value with which a sample belonging to class k can be correctly recognized with a high level of confidence. During recognition, if the distance D(x, r_M) between an input sample x and the representative prototype r_M of a nearest class M is larger than the class region threshold CR_M, x will be rejected. Furthermore, if the distance D(x, r_M) is subtracted from the distance D(x, r_S) between x and the representative prototype r_S of a second nearest class S, the resulting distance difference must be greater than the dis-ambiguity threshold DA_M, or x will be rejected. An inventive algorithm is used to compute optimum thresholds CR_k and DA_k for each class k. The algorithm is based on minimizing a cost function of a recognition error analysis. Experiments were performed to verify the feasibility and effectiveness of the inventive method.

Claims

1. In a recognition system utilizing feature value vector matching between unknown input data and model prototype classes in a database having classes 1≦

k≦

K, a method for decisive recognition, comprising the steps of;

computing a unique class region threshold CR_k for each k^th class,

computing a unique dis-ambiguity threshold DA_k for each k^th class,

receiving an input pattern to be recognized,

determining a feature value vector x for said input pattern,

determining a nearest class M and a second nearest class S to said input pattern,

deciding whether said input pattern should be decisively recognized or rejected in accordance with a class region threshold CR_M and a dis-ambiguity threshold DA_M for said nearest class M, wherein the decision being based on the following equation;

##EQU24## where D denotes a distance function,

r_M denotes the matching prototype feature value vector of the nearest class M,

r_k denotes a prototype feature value vector class k,

r_S denotes the matching prototype feature value vector of the second nearest class S,

CR_M denotes the class region threshold for the nearest class M, and

DA_M denotes the dis-ambiguity threshold for the nearest class M.

2. The method of claim 1 wherein said steps of computing thresholds CR_k and DA_k comprise setting a cost function E of all said input patterns to be:

##EQU25## where situation 1 denotes;

D(x, r_M)>

CR_M, and situation 2 denotes;

D(x, r_M)<

CR_M and D(x, r_S)-D(x, r_M)<

DA_M, and

α

is a cost factor of an incorrect decision.

3. The method of claim 2 wherein said cost function E is expressed in mathematical terms as:

##EQU26## where I denotes the ground-truth class of said feature value vector x O_k =D(x, r_k), and

A is a monotonically decreasing function.

4. The method of claim 3 wherein said steps in claim 1 of computing thresholds CR_k and DA_k further comprise minimizing said cost function E(x) to derive optimum values for said thresholds CR_k and DA_k, according to the following equation:

##EQU27##

5. The method of claim 4 wherein said thresholds CR_k and DA_k are updated in accordance with the following iterative procedure:

(a) establishing a monotonically decreasing function value A,

(b) initializing values of said thresholds CR_k and DA_k according to;

##EQU28## where;

N_k is the total training sample number of class k

x^k_i is the ith training feature vector of class k

r_iM is the closest prototype feature vector of class x

r_iS is the second closest prototype feature vector to x

(c) establishing a cost termination threshold and a maximum iteration number,

(d) for each input pattern sample;

(d1) computing all distance values D_k =D(x,r_k),

(d2) identifying the nearest class M corresponding to distance D_M =min₁≦

j≦

K D_k,

(d3) identifying the second nearest class S corresponding to distance D_S =min_k=1,k≠

M D_k,

(d4) computing the accumulated cost according to said cost function E of said equation (13), and

(d5) updating said thresholds CR_k and DA_k according to said equation (20), and

(e) if said accumulated cost is greater than said cost termination threshold or said number of iterations is less than said maximum iteration number reducing A and repeating steps (d) and (d1)-(d5).

6. The method of claim 3 wherein a recognition is evaluated as right or wrong according to the following equation:

##EQU29##

7. The method of claim 3 wherein said situation 1 rejection is evaluated as right or wrong according to the following equation:

8. The method of claim 3 wherein said situation 2 rejection is evaluated as right or wrong according to the following equation:

9. A character recognition system for recognizing an input pattern as one of a predetermined set of model characters that are organized into K classes comprising:

a memory for storing unique class region threshold CR_k for each k^th class, where 1≦

k≦

K and a unique dis-ambiguity threshold DA_k for each k^th class,

a character input device for recieving an input pattern to be recognized, and

a processor for determining a feature value vector x for said input pattern, for determining a nearest class M and a second nearest class S to said input pattern, and for deciding whether said input pattern should be decisively recognized or rejected in accordance with a class region threshold CM_M and a dis-ambiguity threshold DA_M for said nearest class M, wherein the decision being based on the following equation;

##EQU30## where D denotes a distance function,

r_M denotes the matching prototype feature value vector of the nearest class M,

r_k denotes a prototype feature value vector of a class k,

r_S denotes the matching prototype feature value vector of the second nearest class S,

CR_M denotes the class region threshold for the nearest class M, and

DA_M denotes the dis-ambiguity threshold for the nearest class M.