JPS6136678B2 - - Google Patents

Description

Detailed Description of the Invention (1) Technical Field of the Invention The present invention relates to a vector data multiplication processing method, particularly to a weighted multi-value standard pattern used in, for example, matching processing in, for example, a figure recognition device. The present invention relates to a vector data multiplication processing method that efficiently multiplies vector data corresponding to matching with an input graphic pattern.

(2) Background and problems of the technology Conventionally, in figure recognition devices such as printed characters, multi-value standard patterns are stored in a dictionary memory in order to reduce the influence of positional deviation, and input figure Matching with a pattern (generally detected in binary form) is performed.

Although the present invention is not limited to the above case, in the above matching process, each element of a standard pattern made of multivalued elements and an input graphic pattern made of two types of elements are multiplied by each other. becomes.

In such a case, the number of elements is generally large, and if the multivalued elements are sequentially multiplied, the processing time will be long. In addition, in the above matching process, etc., if a match cannot be clearly achieved, it is desirable to stop midway without performing multiplication for all elements and start matching with the next standard pattern. In the case of a method of sequential multiplication, it becomes clear that the above matching cannot be achieved until all elements are multiplied, so to speak.
Cannot be canceled midway.

(3) Object and structure of the invention The present invention aims to solve the above points, and focuses on the fact that in the case of the standard pattern mentioned above, each element can be expressed with, for example, about 3 bits. It aims to solve the problem. Therefore, in the vector data multiplication processing method of the present invention, either the multiplier or the multiplicand is composed of a multi-value element string, and the other is composed of a binary element string, and multiplication processing is performed. In the vector data multiplication processing method, the vector data composed of the above-mentioned multivalued element string is decomposed into a plurality of binary element strings with different weights, and the above-mentioned binary element string is a binary mutual multiplication circuit unit that processes each element of the vector data on the side consisting of the above and each element in the binary element string having different weights by mutual binary multiplication processing; The purpose of the present invention is to include an addition circuit section that weights and adds outputs from the value mutual multiplication circuit section, and performs multivalue multiplication processing by performing binary mutual multiplication processing for each element.
This will be explained below with reference to the drawings.

(4) Embodiments of the Invention FIG. 1 is an explanatory diagram conceptually explaining an embodiment of multiplication processing according to the present invention, and FIG. 2 shows an embodiment of the present invention.

In FIG. 1, 1 indicates vector data corresponding to an input graphic pattern, and 2 indicates vector data corresponding to a standard pattern. As shown in the figure, it is assumed that each element of vector data 2 is multivalued data.

When multiplication is performed between each element for such theta 1 and 2, in the simplest case, it is necessary to perform multi-value multiplication 25 times in the case shown in FIG. 1A.

On the other hand, in the case of the present invention, as shown in FIG. 1B, each element of vector data 2 shown in FIG. It is decomposed into element data strings 3, 2 with a weight of "2" and element data strings 3, 1 with a weight of "1". and,
First, each element of vector data 1 and element data strings 3 and 4 is multiplied,
Next, each element of vector data 1 and element data strings 3 and 2 is multiplied,
Then, each element of vector data 1 and element data strings 3 and 1 is multiplied with each other. Then, the multiplication results with different weights are added. Of course, at this time, it is also possible to add separately for each element if necessary.

By doing this, each element string has 1 bit, and the multiplication process of binary values can be performed simply by passing the bits through an AND circuit, which greatly simplifies the circuit configuration. In addition, in the case of the above matching process, the degree of matching can be roughly known at the stage when the multiplication is completed for the element data strings 3 and 4 with weight "4", and it is easy to take measures such as canceling the multiplication. Become. Furthermore, if we process 8 bits at a time for each multiplication process, the 25 element data can be processed 4 times since each element data is 1 bit, as shown in Figure 1. In the case shown in figure B, it is possible to complete the multiplication in 4 times x 3 = 12 times.

FIG. 2 shows an embodiment of the invention. The symbols 1, 3, 4, 3, 2, 3, 1 in the figure correspond to those in FIG. 1, 4 is an AND circuit, and 5 is a ROM. ”
6 represents a multi-value adder circuit, and 7 represents a register.

First, a one-byte bit string "00100001" is extracted from the element data strings 3 and 4, for example, in order from the upper left to the lower right in a raster pattern, and is supplied to the AND circuit 4. On the other hand, in vector data 1, the bit string for 1 byte is "10101011".
is extracted and supplied to the AND circuit 4.

These bits are subjected to AND logic for each element, and are led to the ROM 5 as a bit string "00100001".

At this time, the ROM 5 adds a weight of "4" to the logic "1" and outputs the multi-value data string "00400004" to the addition circuit 6. Initially, the contents of register 7 are zero, so the addition result by adder circuit 6 is
The value becomes "8" and is held in register 7. Similarly, three times of processing is performed for element data string 3,
4 will be carried out.

Next, a data string with a weight of "2" added to the element data strings 3 and 2 is outputted from the ROM in the same manner. Then, it is added to the value of the corresponding element in register 7 and set in register 7. The same applies to element data strings 3 and 1. Finally, the multiplication result is obtained on the register 7. Note that the contents of the register 7 can be extracted at any time, so that it can be determined whether or not to terminate the multiplication process as described above.

In the above description, it is assumed that one of the vector data has binary elements from the beginning. However, the present invention is not limited to this, and it goes without saying that multivalued element arrays can be multiplied together by converting into binary multiplication if necessary. Further, it is also possible to provide the register 7 so as to separate and output the multiplication results for each element as necessary.

(5) Effects of the Invention As explained above, according to the present invention, the circuit configuration is simplified and the calculation time is reduced. Particularly when used in the above-mentioned verification process, it becomes possible to determine whether or not to terminate the calculation at an early stage, thereby making it possible to improve the processing speed.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram conceptually explaining an embodiment of multiplication processing according to the present invention, and FIG. 2 shows an embodiment of the present invention. In the figure, 1 and 2 are vector data, 3 is an element data string, 4 is an AND circuit, and 5 is
The ROM gives weight, 6 represents an adder circuit, and 7 represents a register.

Claims (1)

[Claims] 1. In a vector data multiplication processing method in which multiplication processing is performed with either a multiplier or a multiplier made up of a multi-valued element string and the other made up of a binary element string,
Regarding the vector data on the side composed of the above multivalued element string, two or more vector data with different weights are
In addition to decomposing into an element string of values, each element of the vector data on the side composed of the above binary element string and each element in the above binary element string with different weights are multiplied by each other. A binary mutual multiplication processing circuit section that performs processing and an addition circuit section that weights and adds the outputs from the binary mutual multiplication circuit section, and performs binary mutual multiplication processing for each element. A vector data multiplication processing method characterized by performing multi-value multiplication.