Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-08-16
2003-03-18
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06535877
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a pattern recognition apparatus which performs pattern matching between an input pattern as a recognition target and standard patterns described in a plurality of net structure dictionaries using beam search, thereby obtaining a recognition candidate.
Conventionally, when the number of objects to be recognized is very large in voice recognition or the like, pattern matching using beam search is used with which pattern recognition using a small-capacity RAM (Random Access Memory) and a small quantity of calculation is enabled, as disclosed in H. Sakoe et al., “A High Speed DP-Matching Algorithm Based on Synchronization, Beam Search and Vector Quantization”, THE TRANSACTIONS OF THE INSTITUTE OF COMMUNICATION ENGINEERS, Vol. J71-D, No. 9, pp. 1650-1659, September 1988 (reference 1).
Beam search is a technique of removing matching paths that do not affect the recognition result using a net structure dictionary. To avoid influence on the recognition result, many paths must be left at the initial stage, as pointed out in Japanese Patent Laid-Open No. 10-153999 (reference 2). However, when the standard patterns of the recognition target are described in the net structure dictionary, the number of matching paths to be searched is small by itself, and the number of paths to be left can also be relatively small. Hence, when a recognition apparatus is formed using a net structure dictionary, the capacity of a storage means for storing paths can be small.
For pattern recognition, the recognition rate becomes high when the number of recognition targets is small. For this reason, preferably, the use conditions are finely sorted, and a small number of targets are recognized in units of finely sorted conditions. On the other hand, in some cases, recognition targets under different use conditions, e.g., place names in each administrative district and nationwide place names may be simultaneously recognized. If it is known that only a place name in a specific administrative district is to be recognized, a net structure dictionary related to this specific administrative district is used as a recognition target, thereby improving the recognition rate. If a nationwide place name is to be recognized, the place name dictionary for each administrative district is simultaneously used together as a recognition target.
In this case, the dictionary for the nationwide place names is unnecessary. Unlike a case wherein nationwide and administrative district dictionaries are independently prepared, the capacity of a storage means (memory) for storing the dictionaries is halved. Thus, when a plurality of dictionaries can be simultaneously used as recognition targets, the dictionary storage capacity can be reduced.
A conventional pattern-recognition apparatus which performs pattern matching using beam search which uses a plurality of net structure dictionaries as recognition targets will be described next. As shown in
FIG. 4
, this pattern recognition apparatus comprises two, net structure dictionary (A)
401
and net structure dictionary (B)
402
, a beam search pattern matching section
403
, input section
404
, and display section
405
.
Using the beam search algorithm described in reference 1, the beam search pattern matching section
403
obtains the pattern distance between an input pattern input from the input section
404
and a standard pattern described in each of the net structure dictionaries
401
and
402
and outputs to the display section
405
a recognition target in a dictionary, which gives the minimum pattern distance, as a recognition result.
The operation of the conventional pattern recognition apparatus will be described below in more detail.
Prior to the description of the operation, a general net structure dictionary will be described. A net structure dictionary is a set of recognition target words and is designed to connect an arc
501
corresponding to a tone of a recognition target word to a numbered node
502
so as to form each recognition target word, as shown in FIG.
5
.
Letting v be the dictionary number, and &lgr;v be the net structure dictionary, the net structure dictionary having the structure shown in
FIG. 5
is described as follows. Note that Av is the set of arcs representing a standard pattern, Nv is the set of nodes connecting arcs, Wv is the recognition target set, ENv is the end node set, PAv is the partial arc set, and WNv is the recognition target node set.
&lgr;v=(Nv, Av, Wv, ENv, PAv, WNv) {V=1, 2, . . . , V}
Nv={nv_i: i=0, 1, . . . , Iv}
Av={av_j: j=1, 2, . . . , Jv}
Wv={wv_k: k=1, 2, . . . , Kv}
ENv(av_j): the end node of an arc av_;
PAv(nv_i): the set of arcs having a node nv_i as a start node
WNv(wv_k): a node representing the end of a word wv_k
With this description, a net structure dictionary shown in
FIG. 6
is constructed. As shown in
FIG. 6
, in a net structure dictionary A, an arc “A(2)” common to recognition target words “AO (“blue” in Japanese)” and “AKA (“red” in Japanese)” is connected to arcs “O(3)” and “KA(4)” by node #
2
, thereby forming a net structure. Additionally, an arc “I(5)” common to recognition target words “IKE (“pond” in Japanese)” and “ISHI (“stone” in Japanese)” is connected to arcs “KE(6)” and “SHI(7)” by node #
5
, thereby forming a net structure.
In a net structure dictionary B, an arc “A(2)” common to recognition target words “AKI (“autumn” in Japanese)” and “ASA (“morning” in Japanese)” is connected to arcs “KI(3)” and “SA(4)” by node #
2
, thereby forming a net structure. Similarly, an arc “U(5)” common to recognition target words “UE (“upside” iin Japanese)” and “USU (“mortar” in Japanese)” is connected to arcs “E(6)” and “SU(7)” by node #
5
, thereby forming a net structure.
In the above net structure, the independent beam search pattern matching section
403
(
FIG. 4
) obtains a recognition result by the following procedure. In the following description, let X=(x
0
x
1
x
2
. . . xt . . . xT) (t is time) be the input pattern, d(t, v_j) be the local pattern distance between the input pattern xt at time t and the arc av_j, g(t,·) be the accumulated distance of local pattern distances until time t, and J(t) be the set of standard patterns of arcs on the search matching path at time t. A standard pattern of an arc is represented by a standard pattern of DP-matching described in reference 1.
Letting S be the maximum number of search matching paths, a recognition result w is obtained. Additionally, let min[ ] be a calculation that gives the minimum value, and argmin[g(·, k)|S] be a calculation for acquiring the value k that gives the Sth value g in the ascending order.
<Initial Settings>
Step S
20
J(t=0)={0
—
1}
g(t=0, v_k)=∞{k=0, 1, . . . , Jv, v=1, . . . V}
g(t=0, 0
—
1)=d(0, 0
—
1) t=1
<Processing Main Body>
Step S
21
g(t, v_k)=min[g(t−1, v_k), g(t−1, v_j)]+d(t, v_k){av_k &egr; PAv(EN(av_j)), v_j &egr; J(t−1)}J(t)={argmin[g(t, v_k)|S]}
Step S
22
If t<T, the flow advances to step S
21
.
Step S
23
v_m=argmin[g(T, v_k)|1]
v_k &egr; J(t), EN(av_k) &egr; WNv, v=1, 2, . . . , V
Recognition result: w that satisfies WNv(w)=EN(av_m)
END
However, when a plurality of dictionaries are used, as described above, a plurality of search matching paths with the same connection of standard patterns are present although the dictionaries are net structure dictionaries. For this reason, unless the number of paths to be left without being removed is increased, the recognition result is affected, as will be described below.
For example, the two net structure dictionaries A and B having the structures shown in
FIG. 6
are used, the search matching path passes through the same arc of the two dictionaries. In this case,
LandOfFree
Pattern recognition apparatus 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 apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern recognition apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3005639