JPS5814708B2 - Pattern recognition device classification device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a classification device in a pattern recognition device that recognizes patterns with a large number of categories, such as Chinese characters.

In printed kanji recognition, the number of character types to be handled is much larger (2,000 to 4,000) than in the recognition of numbers, alphabets, and kana characters. D, No. 6, P
As described in P.36 5-372, a kanji recognition method using hierarchical pattern matching is known.

This recognition method adopts a hierarchical pattern matching structure from macroscopic observation to microscopic observation using fine resolution.In other words, the character pattern is blurred in several stages, from a layer with more blur to a layer with less blur. , is a recognition method that reduces the number of candidates for the category to which a character belongs as it passes through each layer.This method has the following advantages: (1) Kanji recognition processing can be performed efficiently, (2) Reliability against noise is high, etc. It has the characteristics of

As a means for realizing such a recognition method, it is conventionally known to use a processing device such as a general-purpose computer and a storage device to perform recognition through program processing.

However, in order to select candidate characters using such conventional processing methods, the degree of similarity (correlation value) between the unknown input pattern and each standard pattern is sequentially determined and stored in memory.
When the operations for all standard patterns are completed, it is necessary to sort the contents of the memory in descending order of similarity, select N patterns with the highest degree of similarity, and extract the corresponding candidate standard patterns. Therefore, a memory is required to store the similarity corresponding to each standard pattern, which not only increases the memory capacity but also requires complex processing such as rearranging the memory contents, which increases processing time. It had the disadvantage that it was very long.

Furthermore, since it is necessary to serially calculate the degree of similarity between the unknown input pattern and each standard pattern bit by bit, there is also the problem that the time required for the calculation becomes long.

An object of the present invention is to provide a classification device in a pattern recognition device that has a simple configuration and can select candidate patterns at high speed.

In order to achieve such an object, the present invention provides a memory having a memory capacity corresponding to the number of candidate patterns to be selected, and when a new similarity is calculated, if the memory is filled, the corresponding The feature is that the minimum similarity registered in the memory is searched and a new similarity is registered instead.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 1 shows an example of the basic configuration of the pattern recognition device according to the present invention, which has a two-layer processing structure, in which the first layer uses a blur pattern to select 1 to 3 candidate characters from 2000 characters.
In the classification process that narrows down the candidates to one character, the second layer is a process of determining one pattern for the candidates in the first layer using a pattern matching method.

In Figure 1, 10 is a calculator such as a miniconbuque;
Reference numeral 20 indicates a preprocessing device that performs binarization, cutting out, blurring processing, etc. of character patterns, and 30 and 40 indicate a recognition device and a disk device that perform the above-mentioned second layer processing.

50 is a high-speed classification correlator that performs the first layer processing described above;
This is a portion corresponding to the classification device according to the present invention.

Further, 60 is an input/output interface bus.

In such a configuration, the computer 10 is connected to a preprocessing device 20, a recognition device 30, a disk device 40, and a high-speed classification correlator 50 through an input/output interface bus 60.

First, the preprocessing device 20 images and binarizes the character patterns on the width slip, performs the cutting process for each character pattern, and further performs the blurring process.
The value character pattern and the blurred binary character pattern are transferred into the main memory of the computer 10.

Next, the high-speed classification correlator 50 takes in the unknown blur character pattern from the main memory of the computer 10, calculates the degree of similarity (correlation value) between this blur pattern and the blur standard character pattern, and calculates the similarity between the blur pattern and the blur standard character pattern, as described later. The unknown character pattern is classified according to the degree of
send it back to

Next, the recognition device 30 takes in the candidate character symbol table and cut-out character pattern in the main memory of the computer 10, and performs recognition processing by pattern matching with the standard pattern in the disk device 40.

The recognition result is sent back to the computer 10, and is further output to a printer, magnetic tape device, or connection device with a host large-scale computer (not shown).

As shown in FIG. 1, the classification correlator 50 according to the present invention includes an interface circuit 51 . Microprocessor (MPU) 52, standard pattern storage memory 53, parallel inner product calculation circuit 54, high speed memory 55
, a minimum value detection circuit 56, a high-speed multiplication circuit 57, and an internal data bus 58.

An overview of the operation of the classification correlator 50 will be explained.

The one-character blur pattern in the main memory of the computer 10 is transferred to the high-speed memory 55 through the interface circuit 51 and data bus 58.

A correlation value (inner product) between the transferred blur pattern and the blur standard pattern in the memory 53 is calculated by the serial parallel inner product calculation circuit 54.

Now, assuming that the unknown input blur pattern is f(r>.+) and the blur standard pattern is gw(i, j), the similarity S(f, gW) between these patterns is expressed by the following equation (1). It is expressed as follows.

The numerator part on the right side of the equation represents the inner product of the two patterns, and the value determined by the denominator part is
2) and (3), these are called normalization constants α and β.

The inner product calculation circuit 54 calculates the correlation value (inner product) of the two patterns, and the high-speed multiplication circuit 57 calculates this correlation value by
The pre-calculated normalization constants α and βW are multiplied to obtain the final similarity measure.

Such processing is performed for each standard pattern, and sequentially,
is sent to the microprocessor 52 and minimum value detection circuit 5
It is determined as follows whether or not the candidate character should be registered in the memory stack (memory such as RAM that stores candidate character symbols and their similarities) in 6.

Now, assuming that the number of characters registered in the memory stack is N, this memory stack stores the registered number N of pairs of candidate character numbers and their degrees of similarity.

When a new similarity between a standard pattern and an unknown input pattern is calculated, the similarity is greater than the maximum similarity calculated so far minus a certain relative threshold ε, and the absolute When it is greater than the threshold δ, the new similarity is registered in the memory stack along with the character number.

Assuming that the number of categories is M, the role of the classifier is to calculate M similarities {S(f, gω)|ω=1, 2,...
M}, N categories are selected in descending order of value.

In principle, all S's are arranged in ascending order and N are selected according to a certain rule.

First, if S(f, gω) is smaller than the absolute threshold δ, then
Vugori's power is unlikely to be a candidate, so you can throw it away.

That is, in order to become a candidate category, the degree of similarity needs to be greater than δ.

Next, the number N to be selected needs to be varied depending on the situation.

For example, if the unknown pattern category has many similar patterns, N may be large, and if there are few similar patterns, N may be small.

Making N variable in this way can be achieved by providing a relative threshold ε and selecting a similarity within ε that differs from the maximum similarity (maxS(f, gω)).

Therefore, even when sequentially selecting N candidates, the newly calculated similarity is greater than the maximum similarity calculated so far minus ε, and δ
When it is larger, register the new similarity and character number in the memory stack.

The maximum value of the number N of similarities registered in the memory stack is a predetermined value based on the allowable memory stack size,
NM is set to, for example, 31, and when the number N is smaller than a predetermined value NM, 1 is added to N and that value is additionally registered in the memory stack together with the new similarity.

However, when N becomes NM, there is no new area to register, so by searching for the minimum similarity that has already been registered and writing the new similarity and its character number instead of the minimum similarity. register.

If the new similarity is smaller than the minimum similarity, the state remains unchanged.

In this way, when the above processing with all standard patterns is completed, the similarity degree and character number registered in the memory stack of the minimum value detection circuit 56 are transferred to the main memory of the computer 10, and one unknown pattern is thereby transferred to the main memory of the computer 10. The process for the pattern is finished and the process moves on to the next unknown pattern.

FIG. 2 shows -fO of a specific configuration of the parallel inner product calculation circuit 54 of FIG. 1.

In the figure, the calculation circuit 54 calculates the standard pattern of four picture elements (
4 bits x 4) [Assume that each picture element consists of 4 bits.

], a register 502 that holds four picture elements of an unknown pattern, four multiplication circuits 503 using ROM for multiplying 4-bit integers, and a binary addition that adds the results of multiplication performed in parallel. circuit 504,5
05, a register 506 for holding the intermediate result of addition, and an addition circuit 507 for adding the intermediate result and a new result
It consists of

Assuming that the unknown blur pattern and the standard blur pattern each consist of 8×8 picture elements, the calculation circuit 5
By repeatedly using 4 for 8×8/4=16 times, the inner product of the two patterns is calculated.

In addition, in FIG. 2, 53 is a memory that holds all the standard blurring patterns and the corresponding normalization constant β;
31 is an address designation register of the memory, and 532 is an input/output port of the memory.

55 is a high-speed memory that holds an unknown blur pattern and a normalization constant α determined as described below, 551 is an address register, and 552 is an input/output port.

Control of these circuits is provided by signals sent from microprocessor 52 over data path 58.

Microprocessor 52 to data bus 58 of FIG.
The blurring pattern for one character is sequentially stored in high-speed memory 5 through
5 and stored, four picture elements of that pattern are read out in parallel and stored in the register 502, and at the same time four picture elements corresponding to a certain standard blur pattern are read out from the memory 53. is output and stored in register 501.

The four multiplication circuits 503 calculate the inner product of each pixel of the unknown pattern and the standard pattern, and the adder circuits 504 and 505 perform the addition and hold the result in the register 506.

When the next four picture elements are stored in registers 501 and 502, a similar operation is performed, and the result is added to the contents of register 506 in addition circuit 507, and the result is held in register 506 again. be done.

When such calculations are repeated for all picture elements, the addition result of the adder circuit 507 at that time, that is, the correlation value, is sent to the microprocessor 52 via the data path 58.

The microprocessor 52 stores the correlation value and the memory 5.
The normalization constants β and α stored in 3 and 55 are read out and sent to a high-speed multiplication circuit 57 to determine the degree of similarity between patterns.

Note that the normalization constant α stored in the memory 55 is stored in the same inner product calculation circuit 5 before calculating the correlation value between patterns.
4.

That is, the unknown input pattern is similar to the memory 55.
It is also written into an empty part of the memory 53, the inner product of each picture element of both unknown patterns is calculated, and the square root of the reciprocal of the result is calculated and stored in the memory 55 as a normalization constant α.

FIG. 3 shows an example of a specific configuration of the minimum value detection circuit 56 shown in FIG.
, a second address register 602, and a random access memory (RAM) 60 corresponding to the memory stack described above.
3 control circuit 604, minimum value holding register 605, initial value circuit 606, multiplexer 607, magnitude comparison circuit 6
08, a basic clock generation circuit 609.

For example, the RAM 603 consists of 32 addresses, 0 to 31.
A pair of candidate character numbers and their degrees of similarity is recorded in the fragrance area, and the number N of candidate characters is recorded in address 32.

The minimum value detection circuit 56 includes the calculation circuit 54 and the multiplication circuit 5.
7 is performing the inner product calculation and similarity calculation under the control of the microprocessor MPU52, the RAM 60
RAM that holds the minimum value of similarity registered in 3
autonomously detects the address of

When the microprocessor 52 in FIG. 1 finds candidate characters that meet the various conditions described above, it reads out the number N of candidate characters stored at address 32 in the RAM 603, and determines if the number has reached the maximum value NM, for example 31. If not, the above candidate character number and its similarity are registered at the address of RAM 603 that is N plus 1, and at the same time, 1 is added to the final address.
N, which is increased by the same amount, is registered.

When the number N of candidate characters mentioned above reaches the maximum value, a minimum value detection start signal 627 is transmitted from the MPU 52 to the control circuit 604 via the bus 58.

In response to a signal 625, the control circuit 604 changes the contents of the address register 601 to the address holding the first similarity, for example 0.
Initialize to address.

The initial similarity appears in signal 623.

At the same time, signal 626 is output to multiplexer 607
selects the signal 630 from the initial value circuit 606, and the value of the initial value circuit 606 is latched into the register 605.

After this, multiplexer 607 continues to select signal 623.

For example, the value of 606 is 0.99999, which is the maximum value of similarity.

At this time, the comparison circuit 608 compares the first similarity signal 623 and the initial value signal 631.

Comparison circuit 608 outputs signal 624 when the value of signal 623 is smaller than the value of signal 631.

This signal 624 latches the value of signal 623 into register 605.

That is, the register 605 holds the minimum similarity obtained in the previous iterations.

Additionally, signal 624 causes the contents of address register 601 to be fetched into second address register 602.

That is, 602 stores the address that holds the minimum similarity obtained in the previous iterations.

This completes one cycle and moves on to the next cycle.

In the next cycle, signal 625 causes register 601 to
1 is added to the address that is the content of , and the next similarity is signal 6
Appears as 23.

Similar to the above, the comparison circuit 608 compares the similarity with the previous minimum similarity 631, and outputs the signal 624 when the similarity 623 is smaller, and outputs the signal 62 when it is larger.
Does not output 4.

Similarly, the above cycle is repeated 31 times, which is the maximum number of candidates.

When the above repetition is completed, the end flag is set to the control circuit 604.
The MPU 52 can sense it via the bus 58.

The address holding the obtained minimum value is taken into the MPU 52 via the data path 58 as a signal 632, and becomes the address for registering a new similarity degree.

While the above-mentioned operation is being performed, the domestic debt calculation circuit 54
, a multiplication circuit 57 calculates the degree of similarity with the next standard pattern.

FIG. 4 shows an example of a specific configuration of the address register circuit 601, control circuit 604, and basic clock generation circuit 609 in FIG. 3, and 610 is a decoder. 611,6
12 is a flip-flop, and 613 is a counter.

FIG. 5 is a timing chart explaining the operation of FIG. 4, in which (a) shows the start signal obtained by the decoder 610;
(b) is the clock signal from the generation circuit 609, (C) and (d) are the clock signals from the flip-flops 611 and 6, respectively.
12 output signals are shown.

In FIG. 4, when a control signal 627-1 is sent from the MPU 52 via the bus 58-1, the decoder 61
0, and the start signal 625-1 (Figure 5a)
Then, the address register 601 is cleared to the initial value O, and the counter 613 is set to the predetermined value -31.
Additionally, flip-flops 611 and 612 are reset and set, respectively.

As a result, an activation signal as shown in FIG. 5C is applied from the flip-flop 612 to the generation circuit 609, and a clock signal 625-2 as shown in FIG. 5B is sequentially obtained from the circuit. register 601
The contents of are added by 1.

At the same time, the contents of the counter 613 are counted up, and when the 31st clock is applied, it outputs an output, sets the flip-flop 611, and outputs a termination signal 627-2 as shown in FIG. 5d. Hey, bus 5
8-2, the flip-flop 612 is reset, and the operation of the generation circuit 609 is stopped.

As in the embodiment described above, a RAM 603 having a capacity corresponding to the number of candidate patterns is provided, and the minimum similarity value registered in this RAM is determined using dedicated hardware consisting of registers, comparison circuits, etc. By replacing the minimum number similarity with a new similarity, the memory capacity for storing similarity can be significantly reduced, and it can also be done using dedicated hardware and in parallel with other processing. Since the minimum value detection process can be performed using the same method, the processing time can be significantly shortened.

Furthermore, since the process for determining the correlation coefficient is performed in parallel by the parallel inner product calculation circuit 54, the similarity calculation process can be performed at high speed, and the overall processing time can be significantly shortened.

Furthermore, by providing separate memories for storing the standard pattern and unknown pattern, and by providing a high-speed multiplier, it is possible to further improve the processing time.

In the above-mentioned embodiment, an example of pattern processing for two layers has been described, but the present invention can also be applied to pattern processing for three or more layers.

In that case, the high-speed classification correlators shown in FIG. 1 may be provided in parallel for each layer, or one high-speed classification correlator may be used in a time-sharing manner.

Further, as the preprocessing device 20 and the recognition device 30 shown in FIG. 1, conventionally known dedicated devices may be used, or a program processing device equipped with a microprocessor and memory may be used.

As described above, according to the present invention, not only can the memory capacity for storing various types of information, especially similarity degrees, be significantly reduced, but also the processing time for pattern classification processing can be significantly shortened. There is an effect.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of an example of the basic structure of a pattern recognition device according to the present invention, FIGS. 2 and 3 are block diagrams each showing an example of a specific structure of a part of FIG. 1, and FIG. is a configuration diagram showing an example of a specific configuration of a part of FIG. 3, and FIG.
It is a time chart explaining the operation|movement of a figure. 20 is a preprocessing device, 30 is a recognition device, 50 is a high-speed classification correlator, 52 is a microprocessor, 54 is a parallel inner product calculation circuit, and 56 is a minimum value detection circuit.

Claims (1)

[Claims] 1. A preprocessing device that cuts out an unknown pattern to be identified from an imaged visual field information pattern and performs specific processing on the unknown pattern to obtain a processed pattern, and a processed pattern obtained by the device. and a classification device that obtains N (N: positive integer) candidate patterns by determining the degree of similarity between the processing pattern and the plurality of standard patterns. a calculation means for sequentially and repeatedly calculating the degree of similarity between candidate patterns; a memory means for storing up to NM (NM: an integer of 2 or more) degrees of similarity of candidate patterns; and NM degrees of similarity stored in the memory means. detection means for detecting a minimum value of NM, and after the number N of candidate patterns becomes equal to NM, the degree of similarity newly determined by the calculation means is greater than the minimum degree of similarity detected by the detection means. A classification device characterized in that, when the degree of similarity is large, the newly determined degree of similarity is stored at an address on the memory means having the degree of minimum similarity. 2. The classification device according to claim 1, wherein the processed pattern is a Batano obtained by blurring the unknown pattern. 3. The minimum value detection means compares the similarity sequentially read from the memory means with a specific similarity, and produces an output when the similarity from the memory means is smaller than the specific similarity; First, a predetermined initial value is set, and register means stores the similarity from the memory means as the specific similarity based on the output from the comparison means. or second
Classification system described in Section 4. The detection means further includes second register means for storing a storage address of the degree of similarity read from the memory means when an output is generated from the comparison means. A classification device according to claim 3, characterized in that: 5. The calculation means includes a first memory that stores the first standard pattern, a second memory that stores the processing pattern, and a plurality of both patterns stored in the first and second memories. It is characterized by comprising a calculation circuit that sequentially calculates inner products of picture elements in parallel to calculate a correlation value, and a multiplication circuit that calculates similarity by multiplying the correlation value calculated by the circuit by a predetermined constant. A classification device according to claims 1 and 2. 6 A pre-processing device that cuts out an unknown pattern to be identified from the imaged visual field information pattern and performs specific processing on the unknown pattern to obtain a processed pattern, and a processed pattern obtained by the device and a plurality of standard patterns. a classification device that obtains a predetermined number of candidate patterns by calculating the similarity between the processed pattern and the standard pattern; and a memory means for storing the degrees of similarity, and when the degrees of similarity sequentially determined by the calculating means are larger than a value obtained by subtracting a predetermined value from the maximum value of the already stored degrees of similarity, the A classification device characterized in that the calculated similarity degree is stored in the memory means.