JPH03214283A - Conversion table creation circuit using systolic array - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] This invention relates to a conversion table creation circuit in a systolic array that creates a conversion table for normalizing an extracted single character pattern using a systolic array structure, and normalizes extracted character data. The purpose is to provide a conversion table creation circuit using a systrinol array that speeds up pattern recognition by processing histogram information in pipeline processing in parallel to speed up pattern recognition. The m-th cell from the input side of the m-th column shifts and outputs the input data, and the input data and the width data of the m-1th column are different from the cell of the m-1th column. This is a histogram calculation cell that updates the width data and count data from the input side of the m+1 column and outputs it to the m+1 cell from the input side of the m+1 column, and cells other than the histogram calculation cell are configured to be shift registers. .

[Industrial application field]

The present invention relates to a pattern recognition device, and more particularly to a conversion table creation circuit in a systolic array that creates a conversion table for normalizing a single character pattern cut out using a systolic array structure.

(Conventional technology) With the development of computer systems, reading devices have been put into practical use that capture image data, cut out characters from the captured image data, and recognize each character in the text of the read document. The device divides the dot data read by an image scanner, etc. into predetermined area units, compares the characters within the division with the predetermined characters,
The most similar character is output as the result.

This predetermined data is generally stored in a dictionary memory, and is stored, for example, as data characterizing each prescribed character. When a character to be recognized is input, the input character is similarly characterized and the distance from the predetermined characteristic data stored in the dictionary memory is determined. The smallest character from this determined distance is output as the recognition result.

In the above-mentioned system, when recognizing a single extracted character, the recognition rate improves if the characters have a predetermined size. For this reason, conventionally, each character cut out has a predetermined height and width in the lateral direction of the fir tree. In other words, it is normalized.

There are various methods for this normalization, one of which is to obtain histograms in the vertical and horizontal directions of cut out characters, and to normalize the characters by enlarging or reducing them based on the obtained histograms.

With this method, the characters to be recognized have a constant size, so the recognition rate improves.

[Problems to be Solved by the Invention] When obtaining the above-mentioned histogram, conventionally, the cut out area is read out dot by dot, and for example, the left and right, top and bottom dots read previously are either black or white. The information for the next dot I is obtained from the flags of these flags and processed sequentially. Since such a conventional method calculates a histogram by processing dot by dot, it has the problem that the processing requires a lot of time. That is, there was a problem in that it took a long time to perform the recognition process.

SUMMARY OF THE INVENTION An object of the present invention is to provide a conversion table creation circuit using a systrinol array that speeds up pattern recognition by processing histogram information for normalizing extracted character data in parallel in a pipeline process.

[Means to solve the problem]

FIG. 1 is a block diagram of the principle of the present invention.

N cells H(1.1) to H(N,1)...H(1,
N series circuits in which N) to H(N, N) are connected in series are provided.

Among the cells, the m-th cell from the input side of the m-th column is a histogram calculation cell, and the remaining cells are shift registers.

The histogram calculation cell shifts the input data and outputs it to the next cell, and also updates the width data and count data from this data and the width data and count data added from the previous cell in the adjacent column. Add to the next cell in the next column.

Further, for example, the histogram calculation cell has a flag register in the horizontal direction, a width register in the vertical direction, and a counter.

[Operation] N dots (one dot row) are added in donot position units corresponding to N columns and shifted sequentially.

Since the histogram calculation cells are provided diagonally with respect to one dot row, for example, when one dot row is added from the bottom of the systolic array (bottom of the column), one dot row is added from the input side of the first column. The th histogram calculation cell performs vertical and horizontal histogram calculations. Then, each time the data is sequentially shifted in the systolic array, the histogram calculation for the next row and the next column (histogram calculation cells are provided diagonally in the upper right direction) is performed. By repeating this process sequentially, the results of count values and widths are sequentially output from the last histogram calculation cell in the upper right corner. Further, count values and width data in opposing directions remain in the registers and counters in each histogram calculation cell.

When one character of data passes through the systolic array, vertical and horizontal histograms can be obtained simultaneously at high speed.

[Example] The present invention will be explained in detail below using the drawings.

FIG. 2 is a system configuration diagram of an embodiment of the present invention.

Information read by an image scanner or the like is stored in the image memory 10 as image data.

This image memory 10 has a storage capacity for one page read by an image scanner, and each dot of the read information is divided into white or black 2{I! That is, it is stored as data of 0.1.

The image data stored in the image memory 10 is applied to a noise removal module 11 to remove noise generated during reading. For example, the noise removed by this noise removal module 11 is noise unrelated to character information, etc. For example, a 3 x 3 mask with a black center and 8 pixels surrounding the center dot.
The dots are noise such as white, and the noise removal module 11 makes the dot in the center white. Although this noise removal module is provided in the character recognition pre-processing section 12, it is not limited thereto, and may be performed when storing each character in the normalization module 16, which will be described later. It may be performed at the time of line element formation.

The image information from which noise has been removed by the noise removal module 11 is sent to the row histogram module 13, the column histogram module 14, and further to the readout control module 1.
Join 5. The row histogram module 13 is a module that projects the read information, for example, the content of the paper read by the above-mentioned image scanner, in the column direction in units of dots, and calculates the number of dots in the row in each dot unit.

That is, this is a process of determining for each dot row (horizontal direction) whether or not there are three black dots in that one dot row. Also, the column histogram 14 is a process of projecting in the column direction in the same way as the row histogram described above, and calculating the number of projected black dots.

Data is sequentially read out dot by dot in the row direction from the image memory 10 and added via the noise removal module 11 (reading of dots similar to raster scanning), and the row histogram module 13 sequentially counts black dots (1 line). Then, the number of black dots is sequentially calculated for each row. This number of black dots becomes the row histogram corresponding to each row. The column histogram 14 also has counters corresponding to the number of dots in one dot row.
Each time a row of dots is added in sequence, the counter corresponding to the black dot is incremented. By performing the above-described operations for one page, the row histogram module 16 and the column histogram module 14 obtain so-called row histograms and column histograms representing the number of dots for row positions and column positions, respectively. The result is then applied to the read control module 15.

The readout control module 15 sequentially obtains row positions and column positions from these row histograms and column histograms. For example, this position can be obtained by the period of the row histogram or the period of the column histogram.

The read control module 15 determines the row and column positions, but also performs the following processing. Image data, for example, information read from an image scanner, may have a tilt depending on the position of the paper and the like.

For this reason, the readout control module 15 sequentially changes the angle at which the histogram is obtained so that the column histogram and the row histogram take the maximum value, and obtains a correction angle.

Then, input the image information added from the above-mentioned noise removal module 11 again to obtain the final histogram,
From the point where the row histogram obtained by the corrected slope (the histogram takes the maximum value) changes from 0 to positive (possible to 0), read out one row of data corresponding to the slope for one period. The data is stored in a row buffer provided within the control module 15.

The read control module l5 further obtains the column histogram within the row of one row of data stored in the row buffer, cuts out the data from the position where the column histogram changes from 0 to positive, and outputs it to the normalization module l6. It is also output to the conversion table creation module l7.

This extracted data is data for a single character area.

The conversion table creation module I7 is a module that obtains conversion data for normalizing one character by the normalization module 16. For example, it projects data in the column direction and row direction onto the one character area cut out by the readout control module 15. , the counters in the column and row directions are incremented dot by dot (row and column) from the column and row where the black dot exists, and the value up to the final value in the region of one character is calculated. The circuit and operation of this module will be explained in detail later based on the normalization principle described later.

In the normalization module 16, the final value of the dot cut out by this one character in the row direction and column direction and the cut out 1
Based on the size of the character, the character is expanded to cover the entire area within the extraction area. For example, an enlargement process is performed to make an area of 64×64 dots into one character area. If the column and row values of the character are 48 (both column and row) in conversion table creation module]7, then
Performs processing to convert 48 dot characters to 64 dots.

In this process, data in a row or column at a specific position is repeated to make the same data and enlarge the characters. Furthermore, in the case of reduction, rows and columns at specific positions are repeatedly read out and ORed together to reduce them as the same row or column.

The normalization module 16 allows one character area, for example 64X
After one character is enlarged within 64 dots, the thinning module l8 performs a process of thinning the character. In this thinning module 18, one dot above, below, left and right of the center dot (
Thinning processing is performed using a mask of a total of 11 dots: 3×3), one dot to the left, and two dots above from the center. Moreover, this mask can also be performed using 9 dots of 3×3.

By controlling the central dot to be O when the pattern is predetermined by the mask described above, thinning of lines around one dot forming a character can be achieved in one process. By sequentially repeating this thinning of the mask, a character can be formed by a one-dot line.

For example, 64×6 obtained by the thinning module 18
The 4-dot thin line character is added to the line element generation module 19 and converted into line elements. In this line elementization module, when black dots exist in the vertical direction from the target dot, that is, the center dot, when they exist in the horizontal direction, when they exist in the upper right and lower left, and when they exist in the upper left and lower right, Each dot is represented by a total of four types of line elements. In addition, the above 4
If the line element belongs to more than one of the types, priority is given in the order of, for example, the vertical direction, then the horizontal direction, etc., and in which direction the line element exists is determined for each dot unit. Note that if the center is an O dot, that is, white, it is assumed that no line exists.

In the line segmentation module 19, there are four directions: up and down, left and right, diagonal upwards to the right, diagonally upwards to the left, and five types, including the case where there is no line element, so the state is expressed in a 3-bit value for each dot. , a total of 3×6 4×6 4 information and added to the feature vector module 20.

The feature vector module 20 divides the line segmentation information obtained by the line segmentation module 19 described above into units of 8 dots in the left, right, top, and bottom, respectively, and divides the divided regions into 8 dot units each in the downward and right directions (2× 2 areas) with a total of 16 dots is defined as one vector module area, and how many vertical, horizontal, horizontal,
It is counted whether there are line elements in four directions: upper right direction and upper left direction. A feature vector is calculated using an area of 1 6 x 1 6 dots as one vector module area, but since this one vector module area is moved in units of 8 dots, there are 7 areas in each of the row and column directions, resulting in a total of 7 x 7 feature vectors. This is the area of

In the feature vectorization module 20, the above-mentioned IN
The number of directions is calculated for each area, and when calculating this number, weighting is applied to each area, with the center being higher and the surrounding areas becoming lower as they move outward. For example, each dot in the center 4x4 area has a weight of 4, each dot in the 2 dots around it has a weight of 3, each dot in the 2 dots around it has a weight of 2, and then the 2 dots around it have a weight of 4. Each dot is set to 1, weighting is performed, and a feature vector is determined.

This feature vector uses the normalization module l6 to make all the characters to be recognized the same size, so
If they are the same character, they have almost the same feature vector,
The feature vectors differ for each character. However, since there are some very well-developed modules, in order to speed up the calculation process and improve the recognition rate, in the embodiment of the present invention, a standard pattern of feature vectors is used for each feature vectorization region, i.e. Classification is performed within each square, and the distance between the 20 class standard patterns and the added unknown input within each square is determined. That is, the distance between the feature vector in each square of the standard pattern and the feature vector in the square obtained by the special notice vector module 20 is determined for each square. Each of the squares is divided into classes (classes 1 to 20), and the distance ranking of the classes within each square is determined in descending order of distance to the fifth class.

The distance calculation module 21 stores this distance in the class dictionary 23-
1 (standard patterns are stored in class units). Note that when searching for individual candidate characters, the candidate dictionary 23-2 is used (at this time, the switch SW selects the candidate dictionary 232).

The top selection and score allocation module 22 determines the top five classes mentioned above and determines the score corresponding to each class for each square. That is, the top selection and score assignment module 22 determines the score to be given to each of the first to fifth ranking classes in class units based on the distance obtained from the distance calculation module 21, and calculates the score of each character. For example, for the first distance (short distance), 5 points are given, then 4 points, 3, 2, I, and so on for the classes. These are provided corresponding to cells 1 to 49, respectively. The processing results of the top selection score module 22 are added to the comprehensive evaluation module 24. The comprehensive evaluation module 24 is a module that calculates the degree of matching between an input object, that is, an input character and its candidate, and has three types of operation: an associative matching mode, an exhaustive matching mode, and an individual matching mode.

The associative matching mode is a mode in which the score of a candidate is calculated from the mask corresponding to the candidate stored in the associative dictionary 23-3 and the class to which the candidate belongs.

As shown in Figure 2 0)), the associative dictionary has candidates ■D for each mask.
The class ID of the class to which the candidate belongs in the mask is stored, using the address as the address.

This data is the Cdim corresponding to each candidate's mask ID.
It is obtained by clustering a set of dimensional subvectors according to their (weighted) distances, and only the results are stored in an associative dictionary.

Class dictionary 23-1 in the distance calculation module at the same time
is also created correspondingly.

Note that the associative dictionary 23-3 and the class dictionary 23-1 correspond, and their class II is the same. 2 or more types of dictionaries in 1
When storing in one memory, the specification of the dictionary to be used becomes the dictionary reference start position. (This dictionary can be divided into candidate IDs and a comprehensive evaluation can be performed on each in parallel.
If higher speed is required, it can be easily realized).

The associative dictionary 23-3 is a table in which the class ID: K of the class to which candidate a belongs with mask m is written, and this is written as C (m,
When expressed as a)=K, for candidate a (=1 to c cand), it is obtained as follows. Note that P (m, k) represents the score here. Based on this formula, the overall evaluation value V (a
).

The total matching mode and individual matching mode of the comprehensive evaluation module are modes in which calculations are made for each candidate.

The total matching mode is a=1 to c can, the individual matching mode is J-1 to c kind, a=b(j),
Express the distance by d (m, a). This value V (a) is the (weighted) distance between the feature vectors of candidate a and the input object.

The top candidate selection module 25 selects and outputs a plurality of characters, for example, five characters determined from the top in each character correspondence.

The top five characters become the recognition result in the read image data.

All of the operations described above are performed by pipeline processing. That is, data for one page, for example, in the image memory 10 that stores image data is read out by vibrating processing, divided into lines by the control module 15, and outputted to the normalization module 16 in units of characters. The top selection module 25, which performs the above-mentioned thinning, line elementization, feature vectorization, and recognition processing on the single character, is a module that ranks candidates based on the comprehensive evaluation value and selects the top five.
If the input is in associative exhaustive matching mode, then { (a',
V(a)la', a = 1~c cand} If it is in the discrete integer sum mode ((j, v(aNj = 1~c kind,
a = b (j)) (Comprehensive evaluation output of individual matching) Descending/ascending order = (Character association: Largest order, Others: Smallest 1
1 (fund)). Further, the output is the candidate IDs (or input order) arranged in the order of the input sort results and their comprehensive evaluation values.

In the embodiment of the present invention shown in FIG. 2 described above, the conversion table creation module was explained from the perspective of the entire system. Below, the principles and detailed circuits of the conversion table creation module will be explained in more detail.

When the normalization module l6 in FIG. 2 executes enlargement or reduction processing, the size of the character within the region M of one character cut out by the readout control module 15 must be determined. This is because in the recognition process in the embodiment of the present invention, characters must be made the same size in order to increase the recognition rate. Therefore, as is clear from the diagram explaining the principle of enlargement in Figure 3, 0≦X on the X axis.
Processing is performed to change the area where ≦W to an area where O≦Y≦D on the Y axis.

In the following, the enlargement principle will be explained first, and then the detailed circuit operation of the conversion table creation module 17 will be explained.

Assuming that X and Y take arbitrary real values, the X on the X axis corresponding to the coordinate Y on the Y axis is expressed as X=WxY/D·−−1). Using this, the coordinates I (I
is an integer, the coordinate on the original figure corresponding to work≦1≦D)
(X is an integer) X-1<WXI/D≦X...2). When this equation 2) is modified, D(X-1)<IXW≦DX ---3) is obtained. Therefore, by setting the element at the coordinate I for each I (1≦■≦D) to the element at the coordinate X of the original figure that satisfies equation 3), a figure deformed and enlarged to the width D can be obtained.

In order to normalize input image data based on this idea, first, the character width W of the input figure is checked, and horizontal and vertical histograms are created. That is, create a conversion table.

If the histogram is linear, the leftmost point included in the character area on the image data is obtained by setting the value of the genus sequence to 1, and increasing the value by 1 for the columns to the right. Similarly, for lines, the value is obtained by setting the value of the line to which the uppermost point added to the character area belongs to 1 and increasing the value by 1 for the lines below it. The conversion table creation module 17 determines the width W of this character, the leading edge of the column, and the leading edge of the row.

FIG. 4 is a block diagram of an embodiment of the present invention. The numeral area RX is extracted by the readout control unit 15 (see FIG. 2) and input to the histogram generation circuit network (NxN) 31 in units of rows. Histogram generation circuit network (NXN) 3 1 is a circuit for calculating the vertical and horizontal histograms shown in FIG. Stored as a value.

Also, the horizontal histogram is generated by the histogram generation circuit 31.
The normalization circuitry 34 is directly connected to the normalization circuitry 34 (not shown).

The histogram generation circuit 31 has an NXN systolic array structure, and the image data (the image data remains unchanged) that has passed through the histogram generation circuit 31 is stored in a buffer (NxN) 33. That is, the image RX is finally stored in the buffer 33. In FIG. 2, the output of the read control module 15 is also applied to the normalization circuit network 16, so in this case, the buffer 33 is not necessary and may be provided within the normalization module 16.

The vertical and horizontal histograms obtained by this histogram generation circuitry 31 are applied to the normalization circuit module 16, and the normalization module 16 operates based on this histogram. Note that the normalization circuit network 34 is a circuit that performs horizontal direction (column unit) normalization. The normalization in the vertical direction (in units of rows) is performed by calling the data in units of dot rows by the cell structure circuit 35 for reading data from the buffer 33 (MxN). That is, calculations necessary for horizontal normalization are performed while performing vertical normalization, and this value and input data are output to the normalization circuit 34.

The data reading cell structure circuitry 35 is a circuit that normalizes the vertical direction.If the time when the data reading cell circuitry 35 and the normalization circuitry 34 start operating is t=1, then the vertical normalization In order to perform the normalization, at time L, a line corresponding to the t-th line of the figure after normalization is read.

D-h2(i'-1)<t L ≦ D-h2(
i' ) ・ ・ ・ ・4] is read at time t so that row i'' of the input image is satisfied.In other words, read the row i'' of the input image at time t so that the histogram value satisfies equation 4) in the vertical direction (line reading forward direction). If you load the histogram and input image,
Vertical normalization can be performed. This is while (t L >D-h2(i')&&
i'<M) read data && histo
This can be achieved by the cell performing the following process. Also, when normalizing in the horizontal direction, processing that satisfies equation 3) may be performed. The value of the horizontal histogram and the horizontal character width W are called in. 'D − hHj−
1)', "jW", "D - hl(j)"
If D−hl(j”)<j W, then j→j−1,
If jri≦D−hl(j' −1), then j−+j+
This is done by converting to 1. Note that j represents a column in the normalization figure, and j' represents a column in the input figure.

By the operation of the normalization circuit network 34 and the data reading cell circuit network 35, horizontal and vertical normalization is performed, and the resulting figure becomes a DXD normalized figure.

In order to perform the above-mentioned normalization, a histogram of input characters is required. This histogram generation will be explained in more detail below.

FIG. 6 is a histogram generation circuit diagram according to an embodiment of the present invention. Each cell H(1.1) to H(N,N) consists of a histogram calculation cell or a shift register. As shown in FIG.
Add dots to (N, N) in one line. The output of the histogram calculation cell H (N, 1) is sent to the shift register H (N-1.1) and also to the shift register H (N, 2).
The output of is applied to the histogram calculation cell H (N-1.2). Furthermore, shift registers H (N.3) to H (N,
The output of N) is the shift register (N-1, 3) to H (N
-1, N). That is, in the first row, the histogram calculation cell is placed at the left end of the row, in the next row, the histogram calculation cell is placed at the second dot position, and in the third row, the histogram calculation cell is placed at the third dot position, and the cells are placed sequentially from the first to the third dot position. The structure is such that the data is output to the second and third nodes. In other words, the shift registers are sequentially moved from cell H(N, 1) to cell H(1) corresponding to
．． Up to 1) are configured with shift registers, and at that time cell H (
N, 1) is the histogram calculation cell, in the second the second cell H (N-1.2) is the histogram calculation cell, in the third the same way, in the third position, and in turn the final A histogram calculation cell is provided in cell H (1, N), and the result is output to the next histogram calculation cell position from the left for each dot position.

Each histogram calculation cell and shift register outputs data to the next stage shift register or histogram calculation cell in correspondence with one clock. Note that the shift register delays the sent data by one clock.

The operation will be explained in more detail below. Assuming that the time t at which the operation of the histodaram generation circuit network begins is t=1, and t is incremented by 1 for each ex-clock, the operation of each cell at time t is as follows.

(2) When t≦M, cells (N, 1) to (N.N) read the t-th row of input data. When M<t, the cell (
N, 1) to cell (N, N) read 0.

■ Histogram calculation cell (i, N-i+1) is cell (
The calculation results sent from cell (i+1,N-i) and cell (i
+1, N-i+1), processing is performed according to the operation of the cell, which will be described later.

(2) Histogram calculation cell (i, N-i+1) sends the calculation result to cell (i-1, N-i+2).

Furthermore, all cells (i.j) in rows 1 to N-1 send the data sent from cell (i+1, j) to cell (i-1, j) as they are.

However, when N≦t, the calculation result of cell (1, N) is the value (xsvidth, xcounυ) of the horizontal histogram ((N-t+1)th row) of the input data, so (
MXI) is stored in the buffer 32. Also, the cell (
1, j) (0≦j≦1) data (ywidth, xc
ount) is sent to (MxN) buffers.

All the above operations are completed in M+N-1 clocks, and the histogram value of the J-th row (horizontal direction) of the input data is stored in the histogram calculation cell of the J-th row, and is input to the ■ row of the (MXI) buffer. The histogram value of the ■th row (vertical direction) of the data will be stored.

If the cells are arranged as shown in Figure 6, for example, the data in the first row of the input figure will be processed in cell (N, 1), and the time (I
+1), the processing result and its second row data are stored in cell (N-1)
．． As data from the same row is encountered in sequence in step 2), vertical and horizontal histograms can be created at the same time. Note that instead of arranging the cells as shown in Figure 6,
Using a histogram calculation cell placed at the next limit, data may be input after being delayed in units of one clock at a time, as shown in FIG. Although the operations in the horizontal and vertical directions have been described above, the operations of the histogram calculation cell described above will be explained in more detail below.

First, a horizontal histogram of a histogram calculation cell in a linear case will be explained. The horizontal histogram is
As described above, the value is obtained by setting the value of the column to which the leftmost point included in the character area belongs to 1 on the image data, and increasing the value by 1 in the columns to the right. Therefore, when scanning a certain column of the input image, if that column contains a black image, and the column to the left of that column does not contain any black images, the value of the histogram of that column is set to 1. year,
In the columns to the right of that column, the histogram values are increased by 1. The cell in the j-th column first determines the value of the cell in the (j-1)th column, and if it is greater than or equal to 1, the value obtained by adding 1 to that value is set as the value of its own cell.

If the value of the cell in the (j-1)th column is O, it is checked whether there is a black pixel in the jth column, and if so, the cell value is set to 1, and if not, the cell value is set to 0. By applying the above-described processing to each cell and sequentially processing the input image from the first row, a horizontal histogram is finally obtained.

Further, the width of the character is equal to the value of the histogram of the column in which the rightmost black pixel exists on the input image data, and this can be calculated.

Note that a vertical histogram can also be obtained using exactly the same concept. However, the functions that were distributed spatially in the horizontal direction will now be distributed temporally.

FIG. 8 is a detailed configuration diagram of a linear histogram calculation cell. flag is a flag for determining whether there is a black pixel, count stores a histogram value, and Width stores a character width value. 1x1
1y1 indicates whether the direction is vertical or horizontal. Also, y
flag xiuidth, xcount is processed using the value of the cell in the left column and sends the result to the right cell, yw
i6th, ycount, and xfalg process using the values of their own cells and store the results in their own cells. and xflag, xcount, xwidth and yfl
ag, ycount, and ywi6th are each determined by the following formulas.

Horizontal xflag = if data ==1 then
1else xflag xcount = if xcount>O
then xcount+1else if xfl
ag-=1 or data==I then 1el
se xcount xwidth = if xflag==1 or d
ata==l then xcount+1else
xwidth vertical direction yflag = if data==1 then 1
else yflag ycount = if ycount>O then
ycount+1 else if yflag==I
or data==l then 1else yc
ount ywidth = if yflag==1 or d
ata==1 then ycount+1else
ywidth When processing is performed using such cells, the histogram of the lateral force is finally created by xcounef. , the horizontal character width is stored in xwidth of cell (1, N), the vertical character width is stored in ywidth of cell (1, N),
The vertical histogram is sequentially output as the ycount of the cell (1, N) after time N.

Next, the horizontal histogram of the histogram calculation cell in the nonlinear case will be explained. In the case of non-linearity, the number of times black pixels are crossed for each column is counted and the numbers are integrated. Therefore, the cell in the j-th column calculates the number of times a black pixel is crossed within the j-th column, and integrates the values.

FIG. 9 is a detailed configuration diagram of a nonlinear histogram calculation cell. flag is a flag that determines whether or not a black pixel is being crossed, and count stores the value of the histogram. The stack stores the integrated value of the values added to the histogram in that row.゛X゛y' represents the vertical direction or the horizontal direction. Also, yfa
lg, ycount, xstack process using the value of the cell in the left column and send the result to the right cell, and ystack
k, xcount, and xflag are processed using the values of their own cells, and the results are stored in their own cells.

Then, xflag, xcount, xstack, and yflag, ycount, ystack are each determined by the following two.

Horizontal xflag = if data = = o then O
else 1 if data==1 and xflag==Oth
en xcount+xstack+1else x
count+xstackxstack = if d
ata-=1 and xflag==O then
xstack+1else xstack xcount Vertical direction yflag = if data==O then O
else 1 ycount = if data==I and y
flag=ycount+ystack
+1else ycount+ystack+1yst
ack=if data==1 and yfla
g==o then ystack+1 else ys
tack When processing is performed using such a cell, the horizontal histogram will eventually look like the example in Figure 10, where the character width in the horizontal direction is equal to the XCount of cell (1, N), and the character width in the vertical direction is The character width of is stored in ycount of cell (1.N),
The vertical histogram is sequentially output as the ycount of the cell (1, N) after time N.

By configuring the histogram calculation cell as described above, a conversion table that is a linear or nonlinear histogram can be obtained.

〔Effect of the invention〕

As described above, according to the present invention, since the histograms are processed in parallel in a high line structure, the conversion process can be speeded up. Since this histogram is obtained at high speed, the normalization process can be speeded up at the same time. As a result, a high-speed character recognition device can be realized.

[Brief explanation of drawings]

Fig. 1 is a diagram of the principle of the present invention, Fig. 2 is a block diagram of an embodiment of the present invention, Fig. 3 is a diagram explaining the principle of enlargement, Fig. 4 is a block diagram of the entire embodiment of the present invention, Figure 5 is a vertical and horizontal histogram diagram, Figure 6 is a histogram calculation circuit diagram of the present invention, Figure 7 is a data flow diagram, Figure 8 is a histogram calculation cell (tiI type) diagram, and Figure 9 is a diagram of a histogram calculation cell (tiI type). A horizontal histogram (nonlinear) diagram, FIG. 10 is a histogram calculation cell (nonlinear) diagram. H(1.1)~H(N]) H(N,1)~H(N,N)...Cell, H(N,
1). H(N~1,2)...H(1,N)...
・Histogram calculation cell.

Claims (1)

[Claims] 1) N cells (H(1,1) to H(N,1)...H
(1, N) to H(N, N)) are connected in series, and the m-th cell from the input side of the m-th column shifts and outputs the input data, and A histogram that updates the width data and count data from the data and the width data and count data added from the cell in the m-1th column and outputs it from the input side in the m+1st column to the m+1th cell. A conversion table creation circuit using a systolic array, characterized in that the cells are calculation cells, and the cells other than the histogram calculation cells are shift registers. 2) The histogram calculation cell has a flag register, which sets the flag to 1 when the added input data is 1, holds the current flag value when it is 0, and increments the input count data when the count value is greater than 0. Then, when the flag is 1 or the input data is 1, the count data is set to 1, and at other times, the count value is updated and output as is, and when the flag is 1 or the input data is 1, the count data is set to 1. 2. The conversion table creation circuit using a systolic array according to claim 1, wherein the circuit adds 1 to the width data and outputs the width data which is input as the same value at other times. 3) The input data is character data, and the dots in one character area are added to the N series-connected inputs in units of one dot row, and the Nth cell from the input side of the Nth column is a horizontal histogram. 2. A conversion table creation circuit using a systolic array according to claim 1, wherein the circuit outputs the following. 4) N cells (H(1,1) to H(N,1)...
N columns of series circuits in which H(1,N) to H(N,N)) are connected in series are provided, and the m-th cell from the input side of the m-th column is a shift register that shifts input data and outputs it. It has a width register and a counter, and when the input data is 1, the flag data is set to 1, and when it is 0, it is set to m-1 from the input side of the m-1th column.
The flag data added from the cell in the row is outputted as output flag data to the m+1 cell from the input side in the m+1 column, and when the counter value is greater than 0, the counter is incremented by one.
When the input flag data is 1 or the input data is 1, the counter is set to 1, otherwise the counter is not changed, and the flag data is added from the m-1st cell from the input side of the m-1th column. It is a histogram calculation cell that adds 1 to the counter value and stores it in the width register when is 1 or the input data is 1, and holds the value of the width register at other times, and otherwise shifts the input data and outputs it. A conversion table creation circuit using a systolic array characterized by being a shift register. 5) The input data is character data, and the dots in one character area are added to the N series-connected inputs in units of one dot row, and the histogram calculation cell calculates a vertical histogram using the width register and counter, respectively. 5. A conversion table creation circuit using a systolyre array according to claim 4.