JP2654022B2 - Dictionary search method - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a dictionary search method applied for the purpose of searching for a symbol string that matches an unknown symbol string from a dictionary in which symbol strings are registered, and more particularly, to a recognition dictionary in a pattern recognition device. The present invention relates to a dictionary search method suitable for searching for a dictionary.

(Prior art)

An apparatus for recognizing patterns such as characters is provided with a dictionary in which feature vectors (feature strings) of various patterns are registered, and a dictionary is searched for a feature vector that matches a feature vector (unknown feature string) extracted from an input pattern. Thus, a candidate pattern of the input pattern is determined.

By the way, in the matching of feature vectors in such a dictionary search, due to the influence of noise, pattern deformation, etc., the correspondence of all the elements of the feature vector is uniquely determined, and the elements are compared with each other. When it is determined that they do not match (established or unestablished), the recognition rate decreases. As a countermeasure, when matching with the dictionary feature vector, if some elements of the feature vector of the input pattern are ignored, matching or non-matching is determined, or the procedure of the correspondence relationship of the compared elements is changed. It is valid.

However, even if such a control of the matching method is performed, if only one feature vector is registered in the dictionary for one type of pattern, the pattern cannot be fully deformed. To do so, it is necessary to register a plurality of feature vectors for a single pattern in a dictionary. Furthermore, when selecting one from a plurality of candidates (for example, determining whether the input pattern is α or β or neither), it is necessary to register each feature vector of the plurality of candidates in the dictionary. There is. In this case, in addition to the control of the matching method, it is necessary to devise a method for appropriately controlling the flow of the dictionary search after a match is obtained with the feature vector of a certain dictionary.

However, conventionally, the above matching method and control of the dictionary search flow are performed using a state transition diagram (for example, IEICE Technical Report PRL85-35, Kato "Automatic dictionary creation method in stroke structure analysis method"). ), There is a problem that the description for the control is extremely complicated and the control processing becomes complicated.

〔Purpose〕

SUMMARY OF THE INVENTION It is an object of the present invention to provide a dictionary search method that easily controls a matching method and a dictionary search flow in a search for a symbol string dictionary such as a pattern recognition dictionary.

〔Constitution〕

According to the present invention, control information is added to each dictionary symbol string registered in the dictionary, and a matching method between the dictionary symbol string and the unknown symbol string is controlled according to the control information added to the dictionary symbol string. Then, when the result of matching between the dictionary symbol string and the unknown symbol string matches, the flow of the subsequent dictionary search is controlled according to the control information added to the dictionary symbol string.

〔Example〕

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.

FIG. 1 shows a functional block diagram of one embodiment of the present invention.
In FIG. 1, a symbol string such as a pattern feature vector is stored in the dictionary memory 100 in advance as a dictionary symbol string (hereinafter, a dictionary code string). An unknown symbol string (hereinafter, unknown code string) such as a feature vector of an input pattern is input to an input register 102, and a dictionary search result is output to an output register 104. The search control unit 106 performs access to the dictionary memory 100 and controls the entire dictionary search process, and includes a register group 108 in association with the control and the like. This register group 108 includes CODE, AN, BN, JADR, CN, MODE, F
It consists of LG and RLT registers.

110 is a matching processing unit that executes a matching process between the dictionary code sequence and the unknown code sequence. The unknown code string and the dictionary code string are stored in the A register 1 by the search control unit 106.
12 and B register 114, respectively. The ADR1 counter 116 is an address counter that specifies the read address of the A register 112, and the ADR2 counter 118 is the address counter that specifies the read address of the B register 114. The comparison circuit 120 compares the codes output from the A and B registers for coincidence and non-coincidence, and compares the comparison result with the matching control unit.
Enter 122. The matching control unit 122 controls the operation of the matching processing unit 110, includes a CNT counter 124 related to control of the matching procedure, and can access a specific register (flag) in the register group 108. is there. The output code of the B register 114 is also input to the matching control unit 122. ADR1 counter 116 and ADR2
The counter 118 is controlled by the matching control unit 122.

FIG. 2 shows the overall flow of the dictionary search process. Step 203 is a processing step performed by the matching processing unit 110, and the remaining steps are steps of the search control unit 106. Details of the dictionary search processing operation will be described later.

FIG. 3 illustrates the structure of the dictionary. As shown, the constituent units of the dictionary include a variable-length dictionary code string, a character code (1 byte), a mode identifier (1 byte), a jump address (1 byte), and the number of codes (1 byte).
The number of codes indicates the number of bytes of the dictionary code string.

The mode identifier is information for designating a matching method (partial correspondence, whole correspondence) and a method of controlling a flow of a subsequent dictionary search when matching is performed. The jump address is determined when the matching of the dictionary code string to which the jump is specified by the mode identifier matches (establishes).
Next, the start address of a dictionary constituent unit to be advanced to be matched is specified. Also, a special code for controlling the procedure of the correspondence relation of the symbols to be compared in the matching is inserted as needed in the dictionary code string. Such a mode identifier, a jump address and a special code are added to each dictionary code string as control information.

At the end of the dictionary, the code "F
F "is placed.

FIG. 4 shows a specific example of a dictionary having such a structure. To are dictionary constituent units. The character code 0 is a reject code. Code 0 in each dictionary code string
Is a special code as a part of the control information. The codes other than the special codes in the dictionary code string are, for example, stroke direction codes of a character pattern.

Here, the relationship between identifiers (general surfaces are “b1, b2”) and modes will be described.

For dictionary code strings whose identifiers are set to "00", such as the dictionary constituent units of ".", Matching is performed for "partial correspondence", and if the result is a match, the search ends (exits from the dictionary), and In the case of, the process proceeds to the matching process with the dictionary code string of the dictionary constituent unit () located immediately after.

For a dictionary code string whose identifier is set to “01” as in the dictionary constituent unit of “1”, “partial correspondence” is matched. If the result of the matching is a match, the process proceeds to the matching process of the dictionary code string of the dictionary constituent unit () specified by the jump address (jump).
However, if the result does not match, the process proceeds to the dictionary code string matching process of the dictionary constituent unit () immediately after.

For dictionary code strings whose identifiers are set to "10", such as the dictionary constituent unit of
And exit from the dictionary if the result is a match. When the result of the matching does not match, the process proceeds to the matching process with the dictionary code string of the immediately following dictionary constituent unit ().

For the dictionary code string whose identifier is set to “11” as in the dictionary constituent unit of “1”, matching of “overall correspondence” is performed, and if the result is a match, the dictionary constituent unit specified by the jump destination address ( )) (Jumping) to the matching process with the dictionary code string, and in the case of a non-match, the processing proceeds to the matching processing of the dictionary code string of the immediately following dictionary constituent unit ().

FIG. 6 is a flowchart of the operation of the matching processing unit 110, and FIG. 7 is a detailed flowchart of step 316 in FIG. The matching processing operation will be described with reference to these flowcharts.

When activated by the search control unit 106, the matching control unit 122 sets -1 to the CNT counter 124 as an initial setting (step 301).

Step 302 is an initial setting step for the actual matching process after step 303.
Set the value of CNT counter 124 to ADR1 counter 116, and
Set 0 to counter 118, and FLG register (flag)
Is set to 1.

Next, the matching control unit 122 checks whether the FLG register is in a reset state (set value is 0) (step 303). If the FLG register is in a reset state, the process jumps to step 306. If the FLG register is set, it is checked whether the output code of the B register 114 (code of the dictionary code string read from the address specified by the ADR2 counter 188) is 0, that is, a special code (step 304). Otherwise, jump to step 306. If it is a special code, F
When the LG register is reset to 0, the ADR2 counter 11
8 is incremented by 1 (step 305), and the process returns to step 303.

In step 306, ADR1 counter 116 is incremented by 1 to
The code is read from the next address of the register 112, and the comparison circuit 120 checks whether the comparisons match (step 307).

If a match is found, the code is read from the next address of the B register 114 by incrementing the ADR2 counter 118 by one, and the FLG
A register is set (step 308). And ADR2
It is checked whether the value of the counter 118 is equal to or less than the value of the BN register (step 309). The search control unit 1 is stored in the BN register.
06 sets the number of codes in the dictionary code string in advance.

B register if ADR2 counter value ≤ BN register value
It is checked whether the output code of 114 is a special code, that is, 0 (step 310).
The ADR1 counter 116 is incremented by 1 to read the code at the next address of the A register 112. If it is determined in step 310 that the output code of the B register 114 is 0, the ADR2 counter 118 is incremented by 1 to read the code at the next address of the B register 144, and the FLG register is reset (step 31).
1) Return to step 306.

If the judgment condition of step 309 is not satisfied, step 316
Proceed to. The details of this step 316 are shown in FIG. First, it is checked whether the value of the b1 part of the MODE register is 0 (step 401). The MODE register has a search control unit 1
The identifier information is set in 06 in advance. If b1 = 0, that is, if the dictionary code string is specified as “partial correspondence” matching, the matching control unit 122 determines that the matching result is a match, and RLT as a result flag
The register is set to 1 (step 405).

If b1 ≠ 0 (the dictionary code string is specified to match “all”), the ADR1 counter 116
Is checked to see if it matches the value of the AN register (step 40
2). In the AN register, the number of codes in the unknown code string is set in advance by the search control unit 106.

If the comparison in step 402 matches, that is, if the matching has progressed to the last code in the unknown code sequence,
The result of the matching is determined to be unmatched, and 1 is stored in the RLT register.
Is set (step 404). Otherwise, the result of the matching is determined to be non-matching and 0 is set in the RLT register (step 403).

FIG. 6 will be described again. If it is determined in step 307 that the codes do not match, it is checked whether the FLG register is set (step 312). If it is in the reset state, the process returns to step 306 to read the code at the next address of the A register 112. If it is in the set state, it is checked whether the value of the b1 portion of the MODE register is 0 (step 313). b1
In the case of $ 0, that is, the dictionary code string is "whole correspondence"
If the matching is specified, it is determined that the matching does not match, and 0 is set in the RLT register (step 31).
Five). If b1 = 0, the CNT counter 124 is incremented by 1 (step 314), and the process returns to step 302 to perform matching again. In this case, the matching process is performed from the code of the address next to the first address of the A register 112 in the previous matching.

If the process has proceeded to steps 315, 403, 404, and 405, the matching control unit 122 notifies the search control unit 1 of the end of the matching process.
Notify 06.

The matching process described above will be described using a specific code string.

First, the “partial correspondence” matching operation will be described.

Under the control of the search control unit 106, the code sequence shown in FIG. 8 is set as an unknown code sequence in the A register 112 with the address relationship as shown, and the code sequence shown in FIG. It is assumed that a code string is set in the B register 114 based on the illustrated address relationship. The transition of the address, code, and flag in the matching process in this case is
Figure 10 shows.

The search control unit 106 sets the MODE register in the register group 108 to b1 = 0.

When activated, the matching control unit 122 sets the FLG register to 1 and reads the code at address 0 of the B register 114. However, since this code is not a special code 0, the code at address 0 of the A register 112 is read. Read (1st
Step 1 in FIG. Since the codes read from the A and B registers 112 and 114 are both 4 and coincide, the ADR2 counter 118 is incremented by 1 to read the code of the address 1 of the B address 114 (step 2).

Since this code is a special code 0, the matching control unit 122 resets the FLG register to 0, and
The code of the address 3 of the B register 114 is read out by incrementing the R2 counter 118 by 1 (step 3).

Since this code does not match at 2 and the FLG register is also in the reset state, the ADR1 counter 116 is incremented by 1 and the A register 1
The code of address 12 is read (step 4). This is also a mismatch, and since FDG = 0, the ADR1 counter 116
Is incremented by 1, and the code at address 2 is read (step 5).

Since this code is 2, which matches the code in the code string in the dictionary, the ADR2 counter 118 is incremented by 1 when the FLG register is set, and the next code is read from the B register 114 (step 6). Since this code is 0, the FLG register is reset, and the ADR2 counter 118 is incremented by 1 to read the next code (step 7).

Since this code is not 0, the ADR1 counter 116 is incremented by 1
Then, the code at the address 3 of the A register 112 is read (step 8). Since this code is 1 and does not match the output code 4 of the B register 114 and FLG = 0, ADR1
The counter 116 is incremented by one, and the code at address 4 of the A register 112 is read (step 9). This code matches at 4, so the FLG register is set. At this time, since the ADR2 counter 118 at this time has increased to the address corresponding to the last code of the dictionary code string, the matching control unit
Reference numeral 124 determines that a match has been obtained, and sets 1 to the RLT register as a flag of the determination result of the matching result.

As described above, the matching is performed while the procedure of the correspondence relation of the codes to be compared is controlled by the control code 0. In this case, since the matching method is “partial correspondence”, the codes of the addresses 1 and 3 of the unknown code string are used. Is ignored,
The code of address 0,2,4 is the address 0,2,4 of the dictionary code string
Are determined to be matched or established (correspondence is established).

In the case of matching (“partial correspondence”) between the unknown code string in FIG. 8 and the dictionary code string in FIG. 9 (b), the transition of the address, code, and flag is performed by the same operation as in the above example.
As shown in the figure, the correspondence between the codes cannot be established in step 7, and the process proceeds to step 315 in FIG. 6, and the result does not match.

Next, the matching (“partial correspondence”) with the unknown code string in FIG. 8 and the dictionary code string in FIG. 9C will be described. In this case, the transition of the address, code, and flag is as shown in FIG.

First, the code at address 0 in the dictionary code string is read (step 1). Since this code is 0, that is, a special code, the process proceeds to step 305 in FIG. {Circle around (1)}, the ADR2 counter 118 is incremented by 1 to read the code at the address 1 of the dictionary code string, and the comparison with the unknown code string starts from this (step 2).

The matching process proceeds, and the code comparison becomes inconsistent in step 10, and the FLG register is set at that time. Therefore, the process proceeds to step 313 in FIG. Here b1 = 0
(“Partial correspondence”), the process returns to step 302 via step 314. Therefore, the second matching starts in step 11 of FIG. A lot
The code at the address 0 of the unknown code string is excluded from the matching, and the matching is performed for the code after the address 1.

The matching process proceeds, and if a match is obtained up to the last code of the unknown code string in step 7, step 308 in FIG.
Then, the process proceeds to step 309, from which the process proceeds to step 316, where it is finally determined that they match.

When the third matching is performed, the codes at addresses 0 and 1 in the unknown code string are ignored, and the codes after address 2 are targeted.

Next, the matching process of “overall correspondence” will be described. In the matching of “whole correspondence”, when all dictionary code strings are present in the unknown code string, it is determined whether the matching has progressed to the last code of the unknown code string (No. 7).
In step 402 in the figure, if the process has reached the end, it is determined that matching has been matched, but if not, the process determines that there is no match. The role of the special code 0 in the dictionary code sequence is the same as in the case of “partial correspondence”.

For example, in the case of matching between the unknown code string shown in FIG. 8 and the dictionary code string shown in FIG. 13A, the code at address 1 of the unknown code string matches all the dictionary code strings, and the unknown code string Since the matching does not proceed to the final code, the process proceeds from step 402 to step 404 in FIG.
Finally, it is determined that they do not match.

This is the same as the matching between the unknown code string in FIG. 8 and the dictionary code string in FIG. 13 (b), and it is determined that they do not match.

In the case of matching between the unknown code string in FIG. 8 and the dictionary code string in FIG.
Can be matched for all of the codes (3, 4, 1) in the dictionary code string, so that the matching is determined to be a match.

Here, a specific example of the code string and matching will be described. Direction codes 1 to 4 as shown in FIG. 14A are defined corresponding to the moving directions of the tracking points of the pattern contour portion in the stroke feature extraction. Then, for example, the pattern of the numeral “3” in FIG. 14 (b) is described in advance as a dictionary code string (“all correspondence”) as in FIG. 14 (e).
In this case, an unknown code string as shown in FIG. 14 (c) is extracted from the deformed pattern of the numeral “3” shown in FIG. 14 (c). By matching with the code string, a correspondence can be obtained.

Next, the dictionary search operation when the contents of the dictionary are as shown in FIG. 4 and an unknown code string as shown in FIG. 5 is input via the input register 102 will be described with reference to FIG. I do.

When the unknown code string input to the search control unit 106 is set in the A register 112, the number of codes is set to the register group 1
Set to the AN register in 08 (step 200). In addition,
The search control unit 106 has a dictionary access pointer, and is set to address 0 at this time.

Next, the search control unit 106 checks whether one byte of the address specified by the pointer is the terminator “FF”. At first, one byte of the address 0, that is, the byte of the character code of the dictionary constituent unit is checked. Since the byte is not a terminator, the process proceeds to step 202.

When the process proceeds to step 202 for the first time, the search control unit 106
Reads out the dictionary constituent units and converts the character code (α) to CO
The DE register, the identifier in the MODE register, and the destination address
The number of codes is set in the JADR register, the BN register is set, and the dictionary code string is set in the B register 114. Then, the pointer is updated to the start address (8) of the next dictionary constituent unit.
Since the dictionary code string has a variable length, the length is recognized based on the number of codes, and the pointer is updated. After such control, the search control unit 106 sets the matching control unit 122
Start

A, B, and register 11 are controlled by the matching control unit 122.
The matching process as described above is performed on the code strings in 2,114 (step 203). When a final matching result is obtained, an end notification is sent to the search control unit 10.
Sent to 6.

Upon receiving the end notification, the inspection control unit 106 checks the value of the RLT register, which is a flag of the matching result (step 2).
04). The first is the matching with the dictionary code string,
RLT = 0 because there is no match. Therefore, the search control unit 106 proceeds to step 206 and refers to one byte (the first byte of the dictionary constituent unit) of the address indicated by the pointer,
The determination in step 201 is performed.

In this case, since it is not a terminator, the dictionary constituent unit is read, the dictionary code string is set in the B register 114, the other bytes are set in the corresponding registers of the register group 108, and the matching control unit 122 is started (step 202). ).

Because matching can be obtained by matching dictionary constituent units,
The search control unit 106 checks the value of the MODE register (Step 208). Here, the value (identifier) of the MODE register is 0
Since it is 1, the jump address of the dictionary constituent unit is set as the pointer, and one byte of the address 24, that is, the first byte of the constituent unit is referred to (step 210), and the judgment of step 201 is performed.

This byte is not a terminator, so step 20
Proceed to 2 to store the dictionary code string in the dictionary
After setting to 14 and other bytes to the register group 108, the matching control unit 122 is started.

Since the matching of this dictionary code string does not match,
The processing proceeds to step 204, step 206, step 202,
The matching of the unknown code string of the dictionary code string of the dictionary constituent unit is executed. This match is a match and RL
Since the T register is set to 1, the process proceeds to step 208.
In this case, since the value of the MODE register is 00, step 21
Proceed to 2. In this step, the search control unit 106
The character code (α) set in the register is set in the output register 104 and exits from the dictionary (step 212). That is, the search of the dictionary is completed.

If the matching with the dictionary code string does not match, as a result of referring to the terminator, step 214 is executed.
The reject code is set in the output register 104, and the dictionary search ends.

As described above, the flow of the dictionary search can be flexibly controlled according to the control information added to the dictionary code string, and the control is simple and the description for the control is also easy.

In addition, the matching control unit, the inspection control unit, and the like in FIG. 1 may be realized by hardware or may be realized by software.

(Effect)

As is apparent from the above description, according to the present invention, by adding control information to each dictionary symbol string registered in the dictionary, it is possible to easily control the matching method in the dictionary search and the flow of the dictionary search. Therefore, there is a great effect in realizing pattern recognition that is resistant to pattern deformation.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a functional block diagram of one embodiment of the present invention, FIG. 2 is a flowchart of a dictionary search operation, FIG. 3 is a diagram showing an example of a dictionary configuration, and FIG. FIG. 5 shows a specific example, FIG. 5 shows an example of an unknown code string, FIG. 6 is a flowchart of a matching process, FIG. 7 is a detailed flowchart of step 316 in FIG. 6, and FIG. FIG. 9 is a diagram showing an unknown code sequence for explanation, FIG. 9 is a diagram showing a dictionary code sequence for explaining a “partial correspondence” matching process,
10 to 12 are diagrams showing transitions of addresses, codes and flags in the matching process between the unknown code sequence in FIG. 8 and each dictionary code sequence in FIG. 9, and FIG. FIG. 14 is a diagram showing a dictionary code sequence for explaining the matching process, and FIG. 14 is a diagram for explaining a pattern of numbers in association with a dictionary code sequence and an unknown code sequence. 100 dictionary memory, 102 input register, 104 output register, 106 search control unit, 108 register group, 110 matching processing unit, 112
... A register, 114 ... B register, 116 ... ADR1 counter, 118 ... ADR
2 counter, 120... Comparison circuit, 122... Matching control unit.

Claims (2)

(57) [Claims] 1. A method in which control information is added to each dictionary symbol string registered in a dictionary and a matching method between the dictionary symbol string and the unknown symbol string is controlled according to the control information added to the dictionary symbol string. A dictionary for controlling a flow of a subsequent dictionary search in a case where a result of matching between the dictionary symbol string and the unknown symbol string matches, according to control information added to the dictionary symbol string. retrieval method. 2. The method according to claim 1, wherein a procedure of a correspondence relation of symbols to be compared in matching between the dictionary symbol string and the unknown symbol string is controlled by a special code inserted into the dictionary symbol string as a part of control information. The dictionary search method according to claim 1.