JP3361564B2 - High-speed matching method and apparatus - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a high-speed matching method, and more particularly to a high-speed matching method for performing a matching calculation between a dictionary vector and an input vector such as a character or voice recognition device. .

[0002]

2. Description of the Related Art FIG. 16 is a diagram showing a flowchart of a matching section in a conventional recognition apparatus. Typically,
Given an input feature vector, a large classification process (step
1), small classification process (step 2), detailed classification process (step 3)
After that, the recognition result (candidate) is obtained. Separate matching dictionaries and feature vectors are used for each classification process, and matching calculation with input vectors (depending on the adopted recognition method) is performed, and the calculation results are sorted to create recognition candidates. The reason for dividing the processing in this way is to increase the processing speed. In general, a recognition dictionary for detailed identification employs a multidimensional vector in order to achieve a high recognition rate. Therefore, when matching calculation is performed only for this detailed classification dictionary for all recognition target categories, the amount of calculation becomes enormous and the speed is reduced.
In order to solve this, in the conventional method, the number of candidates is reduced until the recognition performance can be guaranteed by the classification process using the recognition dictionary (however, the recognition performance is deteriorated) using the feature vector with a smaller number of dimensions, High speed was realized by multi-step processing such as sending to classification processing (using a more multi-dimensional dictionary).

In the example of the conventional system shown in FIG. 16, the number of vector dimensions to be used increases from the large classification to the detailed classification. As an example of this conventional method, one of the dictionaries used in each process
The number of vector dimensions per category, the number of input candidates, the number of output candidates, and the amount of calculation are shown in Table 1 below.

[0004]

[Table 1]

This example is for a recognition device with a target category number of 5000 (such as Japanese OCR), and the calculation amount 12800000 when calculated only with the detailed classification dictionary.
(= 256 × 5000) is reduced to 396800 (about 1/3). In the conventional method, a method combining this with simplification of the calculation method is also used. For example, a method that uses multiplication such as Euclidean distance or similarity in the matching process is used in the detailed classification and the like, and an operation such as absolute difference is used in the large classification and the like. In general, subtraction can be executed faster than multiplication, so that higher speed can be realized than using expensive operation in large classification.

[0006]

As described above, in the conventional matching method, it is necessary for each classification unit to perform matching calculation for the number of input candidates, which is not a drastic speedup. Occurs. For example, Table 1 above
In this example, if the calculation is not performed for all 5000 categories in the large classification process, but only for 1000 categories by a certain method, the total calculation amount is 1
It is 40800, which is about one digit faster.

The present invention has been made in view of such circumstances, and utilizes the fact that the distance relationship between category vectors in the dictionary is known, and a flag table storing the distance relationship is stored for each category. Distance (or similarity) obtained in advance and obtained by matching calculation with the target category
Based on, the logical operation with the flag table is used to determine what may be candidates for the subsequent categories, and the category determined to be possible is set as the next target category, and the same thereafter. It is an object of the present invention to provide a high-speed matching method that aims at speeding up by performing matching calculation only on a category having a high possibility by repeating processing.

[0008]

In order to achieve the above object, the present invention provides (1) a setting for each dictionary category in a recognition dictionary.
1 bit for each dictionary category corresponding to the specified dictionary number
Information, that is, the number of bits
One binary flag table containing binary information
Then, for each dictionary category, the degree of similarity described below is divided by a certain number.
In the data structure that has the flag table of the number of divided
In advance, all the words in the flag table of all dictionary categories are
Is initialized to 0 and the same as one flag table.
It has a recognition result flag of the same structure,
The degree of similarity with each dictionary category vector in the recognition dictionary
Note that all recognition result flags must be
The bit is initialized to 0, and the dictionary category vector is set.
For each input vector in the recognition dictionary
Calculator to calculate the degree of similarity with dictionary category vector
Stage, the input vector obtained by the calculation means, and
Sorting based on similarity to dictionary category vector
And a recognition candidate creating means for performing recognition and creating recognition candidates.
Corresponds to the dictionary number of each dictionary category selected as a recognition candidate
Set the bit of the recognition result flag to 1 and
In each dictionary category that is not selected as a recognition candidate
The bit of the recognition result flag corresponding to the dictionary number is set to 0
The recognition result flag,
It scans all dictionary categories in the dictionary in order,
The calculation means for the Gori vector and the input vector
Based on the degree of similarity found in
One flag selected by the degree of similarity in the flag table.
Attention to determine the lag table as the attention flag table
Flag table determining means,
The flag table is obtained by calculating the logical sum with the recognition result flag.
A flag table creating means for creating a table
And a calculation means, a recognition candidate creation means, and a flag.
Creation means, attention flag table determination means, and flags
A table creation method can be applied to the input vector.
Creating a flag table by a, in (2) above (1), the recognition dictionary Dictionary category
Are arranged in the order of the dictionary numbers set for each
The dictionary category for the book number is earlier,
All dictionary categories with dictionary numbers smaller than the dictionary category
Select the dictionary category with the lowest similarity to
It has a recognition dictionary sorting means that sorts sequentially,
Therefore, the recognition dictionary rearranged by the recognition dictionary rearrangement means
The use of識辞statement, (3) set for each dictionary categories in the recognition dictionary dictionary number
Corresponding to the No., each dictionary category is displayed as 1-bit information.
That is, it has bit information for the number of dictionary categories
Binary data is used as one flag table and dictionary
The number of similarities divided by a certain number
In the data structure having the flag table of
Possibility of having the same configuration as the flag table
However, before each recognition process for input data,
All bits in the capability flag table are initialized to 1 and the input data is
Input vector which is the feature vector for recognition to the data
The feature vector creation means for creating
Then, the similarity with each dictionary category vector in the recognition dictionary
Calculating means for calculating a match and the possibility flag table
Scan each bit in sequence and check if the bit is 1.
And a bit in the determining means
Is 1, that is, it may be a recognition candidate.
For the determined dictionary category corresponding to the bit
And the similarity between the input vector and the dictionary category vector
The degree is calculated by the calculation means, and the obtained degree of similarity is calculated.
Based on the flag table of the dictionary category
One flag table selected according to the degree of similarity
Flag table determining means for determining a table
Is determined by the attention flag table determination means
Of the attention flag table and the possibility flag table
Calculate the logical product and store the result in the possibility flag table
Update means for updating the possibility flag table by
And a determination means, a calculation means,
Set the attention flag table determination means and update means to the possibility flag.
All bits in the table, ie all dictionaries
Matching at high speed by executing for categories
Carrying out the grayed processing, (4) is set for each dictionary categories in the recognition dictionary the dictionary number
Corresponding to the No., each dictionary category is displayed as 1-bit information.
That is, it has bit information for the number of dictionary categories
Binary data is used as one flag table and dictionary
The number of similarities divided by a certain number
In the data structure having the flag table of
Initialize all bits in flag table of all dictionary categories to 0
It is converted to a recognition result with the same structure as one flag table.
Has a result flag, and each in the recognition dictionary for the input vector
A postscript to calculate the similarity with the dictionary category vector
Before the calculation step, all bits of the recognition result flag are set to 0 in advance.
It is initialized to and matched with the dictionary category vector
For each power input vector, each dictionary category in the recognition dictionary
Calculation step for calculating the degree of similarity with the re-vector,
The input vector obtained by the calculation step and each word
Sorting based on the degree of similarity with the calligraphy category vector
And a recognition candidate creating step for creating a recognition candidate,
It corresponds to the dictionary number of each dictionary category selected as the recognition candidate.
The corresponding recognition result flag bit is set to 1, and other
That is, each dictionary category not selected as a recognition candidate
The bit of the recognition result flag corresponding to the dictionary number of
And a flag creation step of creating a recognition result flag,
Scan all dictionary categories in the recognition dictionary in turn,
The calculation for the category vector and the input vector
Based on the similarity calculated in step, the dictionary category
Is selected by the degree of similarity in the flag table of
Determine one flag table as the flag table of interest
Attention flag table determination step
Table and the recognition result flag.
Create a flag table with and
And the calculation step, recognition
Candidate creation step, flag creation step, attention flag table
Table determination step and flag table creation step.
Flag on the input vector by
Creating a table (5) in the (4), the recognition dictionary Dictionary category
Are arranged in the order of the dictionary numbers set for each
The dictionary category for the book number is earlier,
All dictionary categories with dictionary numbers smaller than the dictionary category
Select the dictionary category with the lowest similarity to
There is a recognition dictionary sorting step that sorts sequentially.
In advance, the recognition dictionary is rearranged by the rearrangement step.
Use the obtained recognition dictionary, (6) Dictionary number set for each dictionary category in the recognition dictionary
Corresponding to the No., each dictionary category is displayed as 1-bit information.
That is, it has bit information for the number of dictionary categories
Binary data is used as one flag table and dictionary
The number of similarities divided by a certain number
In the data structure having the flag table of
Possibility of having the same configuration as the flag table
However, before each recognition process for input data,
All bits in the capability flag table are initialized to 1 and the input data is
Input vector which is the feature vector for recognition to the data
Feature vector creation step and input vector
For each dictionary category vector in the recognition dictionary
A calculation step for calculating the degree of similarity, and the possibility flag
Each bit of the table is scanned in turn and the bit is 1
The determination step for determining whether or not
Bit is 1, that is, it is not a recognition candidate.
Which corresponds to the bit that was determined to be
For the calligraphy category, the input vector and dictionary category
Calculate the degree of similarity with the vector in the calculation step,
Based on the obtained degree of similarity, the dictionary
One flag selected by the degree of similarity in the lag table
Table to determine the table as the flag table of interest.
Lag table determination step and the attention flag table
The attention flag table determined by the determination step and the previous
It is possible to obtain the result by calculating the logical product with the recordability flag table.
The possibility flag table by storing it in the
And an update step for updating the cable.
, The determination step, the calculation step, the attention flag table
Table determination step and update step.
Table for all bits, that is, all dictionary categories
High-speed matching process by performing on the gori
It is characterized by doing the work .

[0009]

According to the present invention, in a character or voice recognition device, a matching process between an input pattern (characters or voice) and a recognition dictionary provided in advance is performed at high speed. , The distance relationship between each dictionary vector is known, a flag table storing the distance relationship is set in advance for each dictionary vector, and the matching result (distance or distance) between the input vector and the target category vector is set. Based on the similarity, etc.), a logical operation using a flag table is used to determine only the categories (possibility categories) that are possible candidates for recognition, and to focus on the next possibility category. As a category, the matching process and the determination process using a flag are sequentially repeated and processed at high speed.

[0010]

Embodiments will be described below with reference to the drawings. In the following description, for simplicity, the case where a normal Euclidean distance is used for the matching calculation will be described. First, a visual method will be described with reference to FIGS. FIG. 12 is a positional relationship between a dictionary vector and an input vector, FIG. 13 is a calculation example of a conventional method, FIG. 14 is a calculation result with a first category of the present invention method and a possibility category, and FIG. 15 is a first example of the present invention method. The calculation results for two categories and the possibility categories are shown. Less than,
This will be explained sequentially.

FIG. 12 is a plot of the positional relationship between each category vector of the dictionary and the input vector on a two-dimensional plane (category vector is indicated by ◯, input vector is indicated by ⊚). In the conventional method, as shown in FIG. 13, distance calculation is performed between the input vector and all the category vectors, and the recognition candidates are obtained by sorting them (sorting from the smallest distance). The reason why distances are calculated for all category vectors is that the input vector is unknown and the distance relationship with each dictionary vector is unknown. However, even if the input vector is unknown, the positional relationship between each category vector is known. The method of the present invention takes advantage of this fact by first referring to FIG.
As shown in FIG. 4, there is a possibility that the category (the input vector is the first category) based on the calculation result of the distance from the first category of the dictionary.
A category closer to the category and a category farther from the category) are selected, and one of them is set as the second category.
Next, as shown in FIG. 15, the matching calculation has not yet been performed based on the distance calculation result with the second category, and it is determined that there is a possibility from the calculation result in the first category. From within, again determine the possible categories. After that, by repeating this processing, only the possible categories are subjected to the matching processing, and the matching processing is performed at high speed. 14 and 15 show the processing result by the first category and the processing result by the second category in the method of the present invention. Possible categories are the shaded categories in the figure.

Next, the structure and method of creating the flag table used in the high speed matching method of the present invention will be described.
The flag table is a binary table corresponding to the category number of the dictionary. Each bit corresponds to each category of the dictionary, and if the bit value is 1, there is a possibility, and if 0, there is no possibility.

[0013]

[Table 2]

Table 2 is an example of a Japanese OCR flag table. From this flag table, country, field, trouble,
Mouth, band, etc. categories are selected as possible categories. One flag table is the recognition target category-
Bit capacity is required. Therefore, the memory capacity (the number of bytes) can be roughly estimated by the number of categories ÷ 8. For example,
In the case of 5000 categories, one flag table has 625 bytes. In the present invention, first, the distance calculated by the matching calculation is divided into m pieces for each equal range, and the number (m pieces) of flag tables is prepared for each category of the dictionary. Table 3 below shows an example of the flag table configuration per category when the maximum distance is 1000 and the number of divisions m is 10.

[0015]

[Table 3]

This maximum distance varies depending on the number of dimensions of the feature vector used and the normalization method. Further, if the number of divisions m is larger, the distance relationship between the categories becomes the best approximation, but the memory capacity also increases, so it is arbitrarily determined by the system. In one system,
Some feature vectors may not have undergone some kind of normalization. In this case, logically,
I can not set the maximum distance, but I set the maximum distance by experiment (based on frequency information etc.), divide it into m,
The method of the present invention can be applied by setting "more than the maximum distance" as the m + 1 range.

Next, rearrangement of dictionary categories will be described. Before creating the flag table, the dictionary categories are rearranged. The reason for this is that in the present invention, the possibility category is determined thereafter by the distance between a certain target category and the input vector.
This is because the possibility category determination does not function effectively when vectors with similar distances between categories (for example, similar characters such as 0 and o) are continuous. To solve this,
In the present invention, the category vectors in the dictionary are rearranged by a method of sequentially arranging the category vector farthest from the previous category.

FIG. 1 is a block diagram of dictionary rearrangement according to the high speed matching system of the present invention. In the figure, 1 is a dictionary rearrangement processing unit, 2 is an average vector generation unit, 3 is a nearest neighbor category determination unit, and 4 is Category vector copy unit, 5 copy flag control unit, 6 dictionary rearrangement control unit, 7 average vector buffer, 8 input dictionary buffer, 9 result dictionary buffer, 10 result dictionary counter, 11 selection number buffer, 12 is an input dictionary counter, 13 is a maximum cumulative distance buffer, 14 is a cumulative distance buffer, 15 is a counter, 16
Is a distance buffer, 17 is a category selection control unit, and 18 is a category selection processing unit.

FIGS. 2A and 2B are block diagrams of the input dictionary and the result dictionary, respectively. FIG. 3 is a flowchart of dictionary rearrangement. Hereinafter, each step will be described in order. The meanings of the symbols in the flowchart are shown in Table 4 below.
It is as follows.

[0020]

[Table 4]

Step 1 : First, the copy flags of all categorical vectors of the input dictionary (flags indicating whether or not they have already been copied to the result dictionary buffer) are cleared to 0. step2 : Obtain an average vector from all category vectors in the input dictionary. step3,4 : Obtain the category vector of the input dictionary closest to the average vector (nearest neighbor category), and copy it to the first in the result buffer as the first category. At this time, the copy flag of the input dictionary category selected as the first category is set to 1. step5 : Initialize the result dictionary counter to 1. step6 : It is checked whether the value of the result dictionary counter is the number of recognition target categories. If it is the number of categories to be recognized, the dictionary rearrangement process is terminated.

[0022] step7: all of the copy flag is 0 (still,
Among the categories that have not been copied to the result dictionary), the farthest category is selected as the next category for each category of the result dictionary that has already been copied (to the selection flow). step8 : Copy the next category to the result dictionary and set the copy flag of the corresponding input dictionary to 1. step9 : The result dictionary counter is incremented. After that, the same processing is repeated until all the input dictionary categories are copied to the result dictionary (until the result dictionary counter becomes the recognition target category).

FIG. 4 is a flow chart of category selection. Hereinafter, each step will be described in order. In addition,
The meanings of the symbols in the flowchart are as shown in Table 5 below.

[0024]

[Table 5]

Steps 1, 2 : Clear the input dictionary counter required for control and the maximum cumulative distance buffer to zero. step3,4 : Search the input dictionary category for which the copy flag is 0. step5-10 : The cumulative distance buffer used for evaluation is cleared to 0, the distance between this input category vector and each category of the (already copied) result dictionary is calculated, and the obtained distance is added to the cumulative distance buffer. To go. Steps 11 to 14 : The maximum cumulative distance buffer is compared with the contents of this cumulative distance buffer, and if the cumulative distance buffer is smaller, the process moves to the scanning of the next input dictionary category. If the cumulative distance buffer is larger, its contents are copied to the maximum cumulative distance buffer, and the current input dictionary category number (contents of the input dictionary counter) is copied to the selection number buffer. After that, the same processing is performed for all the input dictionary categories, and the number finally stored in the selection number buffer becomes the category number to be copied to the next result dictionary.

Next, a method of creating the flag table will be described. The flag table is created experimentally, and the input data used for the creation is a large number and many kinds of feature vectors used for creating the dictionary. FIG. 5 is a block diagram of the flag table creation unit. In the figure, 21 is a flag table creation processing unit, 22 is a distance calculation unit, 23 is a sorting unit, and 24.
Is a recognition result flag setting unit, 25 is an attention flag determination unit, 2
6 is an attention flag update unit, 27 is a flag table creation control unit, 28 is an input feature data buffer unit, 29 is a distance buffer, 30 is a recognition result (correction) buffer, 31 is a recognition result flag buffer, 32 is a recognition result buffer, 33 is a category counter.

FIGS. 6A to 6C show recognition result flags,
It is a block diagram of each of a recognition dictionary and a flag table unit. FIG. 7 is a flowchart for creating the flag table. Hereinafter, each step will be described in order. The meanings of the symbols in the flow chart are as shown in Table 6 below.

[0028]

[Table 6]

Step 1 : First, all flag tables in the dictionary are cleared to 0. step2-4 : After calculating the distance between each input data and each dictionary category vector (using the recognition method adopted for this calculation), a recognition candidate is created by sorting. This processing uses the normal matching processing as it is. Therefore, as the number of candidates selected by sorting, the number conventionally adopted (or the recognition performance is guaranteed by the dictionary) is used. At this time, the distance to each dictionary vector is stored in the distance buffer. Steps 5 and 6 : Based on the sorting result, a bit corresponding to the candidate number selected as a recognition candidate is set to 1, and a bit other than the recognition candidate is set to 0 to create a recognition result flag. This recognition result flag is binary data for the number of categories with the same configuration as the flag table of Table 2.

[0030]step7,8: After setting these data,
A flag table is created for each dictionary category. Well
Instead, the dictionary category is sequentially set as the attention category, and the result buffer is
Based on the distance stored in
Flags corresponding to the range from the flag table (Table 3)
The table is determined and it is set as the attention flag table. step9,10 : This flag table and recognition result flag
The logical sum (OR) of the
Store as table value (flag table update process
Reason: Table 7). After that, the same processing is repeated until there are no input vectors.
You

[0031]

[Table 7]

As a result of this processing, in the flag table thus obtained, when the distance from a certain category vector to the input vector is obtained, the bit of the category position to be finally adopted as a candidate becomes 1. In the binary data, the flag table in the range with a small distance is 1 in the category close to the category vector, and 0 in the others. In the flag table in the range with a relatively large distance, the position of the category corresponding to the distance is 1. It is 0 for very close categories and distant categories.
This information saves the distance relationship between each category vector of the known dictionary, and the important element of the present invention is to save the information and to the learning vector (feature vector used to create the flag table). That is, the reduction in recognition performance does not logically occur. Therefore, the recognition performance for the learning vector is completely preserved in addition to the preservation of the distance relation.

Next, the high-speed matching method will be described. FIG. 8 is a block diagram of the high-speed matching process, in which 41 is a distance calculation unit, 42 is a flag table determination unit,
43 is a high-speed matching control unit, 44 is a distance buffer, 4
5 is a possibility flag table, 46 is a category counter,
47 is an input feature vector, 48 is a recognition dictionary, 49 is an attention flag table number buffer, 50 is a start address register, 51 is an end address register, 52 is a counter,
Reference numeral 53 is a logical operation unit, and 54 is an update control unit.

FIGS. 9A to 9C are block diagrams of the possibility flag table, the recognition dictionary, and the flag table section. FIG. 10 is a flowchart of the high speed matching process. Hereinafter, each step will be described in order. The meanings of the symbols in the flowchart are as shown in Table 8 below.

[0035]

[Table 8]

Steps 1, 2 : First, all bits of the possibility flag table are set to 1. This versatility flag table has the same structure as the flag table of Table 2, and each bit position corresponds to each category number in the dictionary. Initialize the category counter to 0. step 3,4 : It is judged whether the bit of the possibility flag table indicated by the category counter is 1 (whether the category may be subjected to matching calculation). If it is 0, the matching process is not performed, the categorical counter is incremented, and the process is advanced to the category of the next dictionary. step5 : When the bit of the possibility flag table is 1, the distance between the dictionary category vector and the input vector is calculated. step 6 : Determine the attention flag table of the dictionary category based on the obtained distance.

[0037] step7: logically ANDed with the attention flag table and likelihood flag table (the AND), the result is copied to the likelihood flag table (likelihood flag table update process: see below). step8 : increment the category counter and proceed to the next dictionary category. After that, similar processing is repeated until the category counter reaches the number of recognition target categories. With the above processing, based on the distance calculated by the category of interest, the possibility of subsequent categories is determined successively, and the matching calculation with unnecessary categories is passed, realizing high-speed matching processing. it can.

Finally, the update processing of the possibility flag will be described. The possibility flag is a logical product (AND) with the flag of interest.
Will be updated by In the above-described high-speed matching processing operation, this logical product range may be all of the flags (corresponding to the number of recognition target category bits). However, the necessary range of the updated possibility flag is the range after the current category number. Therefore, the logical product (A
The ND) process only needs to be performed within that range.
The update process in which this range is limited will be described. Since the flag table is binary data, it is usually data of the number of bytes which can be roughly estimated by the number of categories / 8. Since logical operations can be performed in byte units, the logical product (A
ND) is also performed in byte units. Since this byte unit processing is a problem of memory access length,
If 6-bit or 32-bit access is possible, it can be processed in the same manner as the present invention. Further, the larger the access width, the faster the processing.

FIG. 11 is a flowchart for updating the possibility flag table. Hereinafter, each step will be described in order. The meanings of the symbols in the flowchart are as shown in Table 9 below.

[0040]

[Table 9]

Step 1 : First, the head byte address of the flag is calculated based on the current category number (this is calculated by category number / 8), and the result is substituted into the address counter. Steps 2 to 5 : A logical product (AND) operation is performed on the byte data of the possibility flag indicated by the address counter and the byte data of the attention flag, and the result is assigned to the possibility flag. Similarly, the operation is repeated until the address counter reaches the end. By this processing, the possibility flag can be updated only in the range necessary for the high-speed matching processing.

Next, application of a matching method other than the distance measure will be described. INDUSTRIAL APPLICABILITY The present invention is effective for those adopting a matching method using all distance measures such as normal absolute difference distance and Eulide distance. Besides this,
Many measures of similarity are also used in the recognition device. The degree of similarity (S) is calculated by the following formula (1).

[0043]

[Equation 1]

This is because the inner product value of two vectors is normalized by the norm of each vector, and is equivalent to the following equation (2) of the following equation 2 in which the norm of each vector is normalized to 1. .

[0045]

[Equation 2]

Considering the Euclidean distance (D) using this vector, the following equation (3) is obtained.

[0047]

[Equation 3]

After all, the degree of similarity and the Euclidean distance are in an equivalent (front and back) relationship. Therefore, the present invention can be applied to the similarity method.

As described above, the present invention is a flag table configuration for storing the distance relation of each category vector of the dictionary for use in high-speed matching processing and a method of creating the flag table, and is characterized by the following points. (1) One flag table is binary data corresponding to each category number in the dictionary, and if the bit value of the flag table is 1, the corresponding category may be a candidate (needs matching processing), When the bit value is 0, it means that there is no possibility of being a corresponding category candidate (no need for matching processing). (2) The configuration of the flag table per category is such that the maximum value of the scale (distance etc.) used in the recognition method is divided by a certain number of divisions, and a flag table with meaning corresponding to each divided distance range is It is configured by including the divided number of pieces, and one attention flag table of the attention category can be determined based on the matching calculation result (distance or the like) between the input vector and the attention category.

(3) In order to operate the present invention effectively,
Before creating the flag table, an operation of rearranging the category vectors of the dictionary is performed for each category vector of the dictionary determined previously in order from the one having the farthest relationship. (4) The recognition result candidates obtained as a result of the matching process and the sorting process and the dictionary of the dictionary are obtained based on the matching method and the number of candidates that have been adopted, using a large amount of various feature vectors used to create the dictionary as input data. Based on the matching result with each category vector (distance, etc.), the flag that saves the distance relationship of each category vector by repeating the update process of the corresponding flag table of each category until there is no input feature vector. How to create a table.

Further, this is a method for performing a high-speed matching process using a flag table that stores the distance relationship of each category vector of the dictionary, and is characterized by the following points. (1) A possibility fractal table having the same structure as one flag table is provided, and all bit values of the possibility fractal table are initialized to 1 before the matching process. (2) The attention category to be subjected to the matching process is determined by determining whether the possibility flag bit value corresponding to the category indicated by the category counter is one. (3) The matching calculation adopted is performed for the input vector and its attention category, and the attention category attention flag table is determined based on the calculation result (distance etc.).

(4) With respect to the attention flag table and the possibility flag table, the possibility flag table is updated using a logical operation only for bit data after the current category counter. (5) After that, the same process is repeated until the category counter reaches the number of categories to be recognized, so that the matching calculation is performed only with a possible category vector, thereby performing the matching process at high speed.

[0053]

As is apparent from the above description, the present invention has the following effects. That is, the present invention is a method for performing high-speed matching processing between an input pattern (characters or voice) and a recognition dictionary provided in advance in a character or voice recognition device. In order to realize the high-speed matching process in the present invention, the fact that the distance relationship between the dictionary vectors is known is used, and a flag table storing the distance relationship is set in advance for each dictionary vector and Based on the matching result with the category vector of interest (distance, similarity, etc.), a logical operation using a flag table is used to determine only the category (possible category) that may be a recognition candidate for subsequent categories. However, with the next possibility category as the attention category, the matching process and the determination process by the flag can be repeated and processed at high speed.

[Brief description of drawings]

FIG. 1 is a block diagram for explaining an embodiment of a high-speed matching type dictionary rearrangement processing unit according to the present invention.

FIG. 2 is a configuration diagram of an input dictionary and a result dictionary in FIG.

FIG. 3 is a flowchart of a dictionary rearrangement process of a high speed matching system according to the present invention.

FIG. 4 is a flowchart of category selection processing of a high speed matching method according to the present invention.

FIG. 5 is a configuration diagram of a flag table creation unit of a high-speed matching method according to the present invention.

FIG. 6 is a configuration diagram of a recognition result flag, a recognition dictionary, and a flag table unit in FIG.

FIG. 7 is a flowchart of a flag table creation process of a high speed matching method according to the present invention.

FIG. 8 is a configuration diagram of a high-speed matching processing unit of a high-speed matching system according to the present invention.

9 is a configuration diagram of a possibility flag table, a recognition dictionary, and a flag table unit in FIG.

FIG. 10 is a flowchart of a high-speed matching processing unit of a high-speed matching method according to the present invention.

FIG. 11 is a flowchart of a possibility flag table updating process of the high speed matching method according to the present invention.

FIG. 12 is a diagram showing a positional relationship between a dictionary vector and an input vector according to the present invention.

FIG. 13 is a diagram showing a calculation example of a conventional method for explaining the present invention.

FIG. 14 is a diagram showing calculation results and a possibility category with the first category of the present invention.

FIG. 15 is a diagram showing a calculation result and a possibility category with the second category of the present invention.

FIG. 16 is a flowchart of a conventional matching process.

[Explanation of symbols]

1 ... Dictionary rearrangement processing unit, 2 ... Average vector creation unit, 3
... nearest category determination unit, 4 ... category vector copy unit, 5 ... copy flag control unit, 6 ... dictionary rearrangement control unit, 7 ... average vector buffer, 8 ... input dictionary buffer, 9 ... result dictionary buffer, 10 ... result Dictionary counter,
11 ... Selection number buffer, 12 ... Input dictionary counter, 1
3 ... maximum cumulative distance buffer, 14 ... cumulative distance buffer,
15 ... Counter, 16 ... Distance buffer, 17 ... Category selection control unit, 18 ... Category selection processing unit.

─────────────────────────────────────────────────── ─── Continuation of the front page (58) Fields surveyed (Int.Cl. ⁷ , DB name) G06T ⁷ /00-7/60 G06K 9/62-9/82 G10L 15/00-17/00 JISST file ( JOIS)

Claims (6)

(57) [Claims] 1. It is set for each dictionary category in the recognition dictionary.
1-bit information for each dictionary category corresponding to the dictionary number
Represented as, that is, bit information for the number of dictionary categories
Binary data with is used as one flag table, and the similarity degree described below is divided by a certain number for each dictionary category.
Data structure with a flag table of the number of items
Beforehand, all bits of the flag table of all dictionary categories
Is initialized to 0, and a recognition result flag with the same structure as one flag table
And each dictionary category in the recognition dictionary for the input vector
Before the calculation means described below to calculate the degree of similarity with the vector,
Initialize all bits of the recognition result flag to 0 in advance.
The input vector to be matched with the dictionary category vector
In contrast, it is similar to each dictionary category vector in the recognition dictionary
Calculating means for calculating the degree, the input vector obtained by the calculating means, and each dictionary
Sorting is performed based on the degree of similarity with the Tegori vector.
The recognition candidate creating means for creating a recognition candidate and the dictionary number of each dictionary category selected as the recognition candidate.
The corresponding recognition result flag bit is set to 1, and other
That is, each dictionary category not selected as a recognition candidate
The bit of the recognition result flag corresponding to the dictionary number of
, A flag creating means for creating a recognition result flag and all dictionary categories in the recognition dictionary are sequentially scanned to
The calculation for the category vector and the input vector
Based on the degree of similarity calculated by
One selected according to the degree of similarity in the flag table
Flag table of interest as flag table of interest
Attention flag table determination means , logic of the attention flag table and the recognition result flag
A flag table that creates a flag table by finding the sum
And a calculation means, a recognition candidate creation means, a flag creation means, and a note creation means.
Eye flag table determination means and flag table creation
Means by implementing the means on the input vector.
A flag table creating device for creating a table. 2. The recognition dictionary is set for each dictionary category.
Are arranged in the order of the dictionary numbers
The categories are earlier, that is, the dictionary category
For all dictionary categories with dictionary numbers smaller than
Select the dictionary category with the lowest degree of similarity and sort them sequentially
It has a recognition dictionary rearranging means for
Use the recognition dictionary sorted by the dictionary sorting means
The flag table production according to claim 1, characterized in that
Equipment. 3. It is set for each dictionary category in the recognition dictionary.
1-bit information for each dictionary category corresponding to the dictionary number
Represented as, that is, bit information for the number of dictionary categories
Binary data with is used as one flag table, and the similarity degree described below is divided by a certain number for each dictionary category.
Data structure with a flag table of the number of items
Te, the possibility of the same configuration as one flag table Furagutebu
Before each recognition process for input data,
All bits of the possibility flag table are initialized to 1, and an input vector that becomes a feature vector for recognition is input data.
A feature vector creating means for creating a vector and an input vector for each dictionary category in the recognition dictionary.
A calculation means for calculating the degree of similarity with the cutout, and each bit of the possibility flag table is scanned in order,
Calculating means for determining whether or not the bit is 1;
If the bit is judged to be a candidate for knowledge,
For the corresponding dictionary category,
The degree of similarity with the call category vector is calculated by the calculation means.
Based on the calculated similarity, the dictionary category
One selected according to the degree of similarity in the flag table
Flag table of interest as flag table of interest
Attention flag table determination means and the attention flag table determination means
Logic of flag table and possibility flag table
Find the product and store the result in the possibility flag table
Update means to update the possibility flag table by
Characterized by having the determination means, the calculation means, the attention flag table determiner
Stage, the updating means, pairs all bits possibility flag table
, Ie, for all dictionary categories
By doing so, high-speed matching that performs high-speed matching processing
Processing equipment. 4. It is set for each dictionary category in the recognition dictionary.
1-bit information for each dictionary category corresponding to the dictionary number
Represented as, that is, bit information for the number of dictionary categories
Binary data with is used as one flag table, and the similarity degree described below is divided by a certain number for each dictionary category.
Data structure with a flag table of the number of items
Beforehand, all bits of the flag table of all dictionary categories
Is initialized to 0, and a recognition result flag with the same structure as one flag table
And each dictionary category in the recognition dictionary for the input vector
Before the calculation step described below to calculate the degree of similarity with the vector
In advance, all bits of the recognition result flag are initialized to 0.
Every input vector to be matched with the dictionary category vector
In contrast, it is similar to each dictionary category vector in the recognition dictionary
The calculation step for calculating the degree, the input vector obtained by the calculation step, and the respective words
Sorting based on the degree of similarity with the calligraphy category vector
Recognition candidate creation step of creating a recognition candidate, and the dictionary number of each dictionary category selected as the recognition candidate.
The corresponding recognition result flag bit is set to 1, and other
That is, each dictionary category not selected as a recognition candidate
The bit of the recognition result flag corresponding to the dictionary number of
, A flag creation step of creating a recognition result flag, and sequentially scans all dictionary categories in the recognition dictionary,
The calculation for the category vector and the input vector
Based on the similarity calculated in step, the dictionary category
Is selected by the degree of similarity in the flag table of
Determine one flag table as the flag table of interest
Attention flag table determination step
Table and the recognition result flag.
Create a flag table with and
And the calculation step, the recognition candidate creation step, and the flag creation.
Step, attention flag table determination step, and
Perform the lag table creation step for the input vector.
A flag table that creates a flag table by applying
Bull making method. 5. The recognition dictionary is set for each dictionary category.
Are arranged in the order of the dictionary numbers
The categories are earlier, that is, the dictionary category
For all dictionary categories with dictionary numbers smaller than
Select the dictionary category with the lowest degree of similarity and sort them sequentially
And a recognition dictionary rearrangement step for performing
Recognition dictionaries sorted by the recognition dictionary sorting step
5. The flag table as set forth in claim 4, characterized in that
Cable creation method. 6. A method is set for each dictionary category in the recognition dictionary.
1-bit information for each dictionary category corresponding to the dictionary number
Represented as, that is, bit information for the number of dictionary categories
Binary data with is used as one flag table, and the similarity degree described below is divided by a certain number for each dictionary category.
Data structure with a flag table of the number of items
Te, the possibility of the same configuration as one flag table Furagutebu
Before each recognition process for input data,
All bits of the possibility flag table are initialized to 1, and an input vector that becomes a feature vector for recognition is input data.
The feature vector creation step for creating a vector and the dictionary vector for each dictionary in the recognition dictionary for the input vector.
Calculation step for calculating the degree of similarity to the cutout, and scanning each bit of the possibility flag table in order,
A determination step for determining whether the bit is 1
And the bit is 1 in the determination step, that is,
If there is a possibility that the
Input dictionary for the dictionary category corresponding to
The degree of similarity between the
Calculated with the step, and based on the degree of similarity obtained, the dictionary
Select by the degree of similarity in the flag table of the category
One flag table exposed is the flag table of interest.
Determined by the attention flag table determination step and the attention flag table determination step
A discussion of the attention flag table and the possibility flag table
It is possible to obtain the logical product and store the result in the possibility flag table.
Update step to update possibility flag table by
Characterized by having a flop, said determination step, calculation step, attention flag table
Decision step, update step, possibility flag table
For all bits of, that is, for all dictionary categories
By performing this, it is possible to perform matching processing at high speed.
High-speed matching processing method.