【発明の詳細な説明】〔概 要〕シストリックアレイ構造によって入力パターンの大きさ
を正規化するシストリックアレイによる正規化方式に関
し、入力するデータを各処理単位で並列にさらにはバイブラ
イン処理を行いパターン認識を高速化するシストリック
アレイによる正規化方弐を提供することを目的とし、対応するセルと、該セルと隣合う２個のセルとより情報
が加わり、正規化値と変換値との積が最大幅と該セル位
置との積より小さい時に対応するセルの隣のセルのデー
タを取り込み、正規化値と変換値との積が最大幅と該セ
ル位置のセル以上の時前記隣のセルに対向する隣のセル
のデータを取り込むセルを複数個複数段に渡って設ける
ように構成する。[Detailed Description of the Invention] [Summary] Regarding a normalization method using a systolic array that normalizes the size of an input pattern using a systolic array structure, input data is processed in parallel in each processing unit, and furthermore, Vibration processing is performed in parallel. The purpose is to provide a normalization method using a systolic array that speeds up pattern recognition. When the product of is smaller than the product of the maximum width and the cell position, the data of the cell next to the corresponding cell is imported, and when the product of the normalized value and the converted value is greater than or equal to the maximum width and the cell at the cell position, the data of the cell next to the corresponding cell is imported. A plurality of cells that capture data of an adjacent cell opposite to a cell are provided in a plurality of stages.
本発明はパターン認識装置に係り、更に詳しくはシスト
リックアレイ構造によって入力パターンの大きさを正規
化するシストリックアレイによる正規化方弐に関する。The present invention relates to a pattern recognition device, and more particularly to a normalization method using a systolic array that normalizes the size of an input pattern using a systolic array structure.
コンピュータシステムの発展により、画像データを取り
込むとともに、取り込んだ画像データから文字を切り出
し、読み取った書類の文章のそれぞれの文字を認識する
読み取り装置が実用化している。この読み取り装置は例
えばイメージスキャナ等によって読み取ったドントデー
タをあらかじめ定められた領域単位で分割し、その分割
内での文字とあらかじめ定められた文字とを比較し、１
番似通った文字を結果として出力している。このあらか
じめ定められたデータは一般的には辞書メモリに格納さ
れており、例えば各規定の文字を特徴化したデータであ
る。そして認識すべき文字が入力した時、同様にその入
力した文字を特徴化し、前述の辞書メモリに格納されて
いるあらかじめ定められた特徴データとの距離を求めて
いる。この求めた距離が最も小さい文字を認識結果とし
て出力している。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. This reading device divides don't data read by an image scanner or the like into predetermined area units, compares characters within the divisions with predetermined characters, and
Characters with similar numbers are output as results. This predetermined data is generally stored in a dictionary memory, and is, for example, 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 character with the smallest calculated distance is output as the recognition result.
前述のようなシステムにおいては、それらの処理はすべ
てドット単位で行っている。例えば１枡内の文字を切り
出して認識文字とし、その文字から特徴データを求める
ため３×３のウィンドウを設け、その３×３のドソトデ
ータから特徴を求めている。In the system described above, all of these processes are performed dot by dot. For example, characters within one square are cut out to be recognized characters, a 3x3 window is provided to obtain feature data from the characters, and features are obtained from the 3x3 dosoto data.
前述の１枡内の文字の切り出しは、文字の大きさに依存
せず、１文字が入っている領域のみを切り出しているに
すぎない。The above-mentioned cutting out of characters within one square does not depend on the size of the characters, and only the area containing one character is cut out.
一般的に、認識率を高めるためこの認識における文字の
大きさが等しいことが望ましい。このため、従来におい
ては切り出した領域をドット単位やバイト単位で読み出
し、文字の大きさを判断するとともに、その１文字の正
規化をＣＰＵの処理において行っている。Generally, it is desirable that the sizes of characters in this recognition be the same in order to increase the recognition rate. For this reason, conventionally, the cut out area is read in dot units or byte units, the size of the character is determined, and each character is normalized in the CPU processing.
従来のシステムにおいては、データの切り出し例えば１
文字単位の切り出しさらには１文字単位での文字の大き
さの正規化はドット単位やバイト単位の処理となり、デ
ータのアクセスに多くの時間を有する問題を有していた
。In conventional systems, data extraction, for example 1
Cutting out character units and normalizing the character size of each character requires processing in dot units or byte units, which poses the problem of requiring a large amount of time to access data.
また特徴データを求めるためにも、１文字単位で辞書デ
ータから特徴データを読み出し、入力した文字の特徴デ
ータと比較しているため、その比較に多くの時間を有す
るいう問題を有していた。Furthermore, in order to obtain feature data, the feature data is read out from the dictionary data character by character and compared with the feature data of the input character, so there is a problem in that the comparison takes a lot of time.
本発明は入力するデータを各処理単位で並列にさらには
バイブライン処理を行いパターン認識を高速化するシス
トリックアレイによる正規化方式を提供することを目的
とする。SUMMARY OF THE INVENTION An object of the present invention is to provide a normalization method using a systolic array that speeds up pattern recognition by processing input data in parallel in each processing unit and further processing the vibration line.
第１図は本発明の原理ブロソク図である。FIG. 1 is a diagram of the principle of the present invention.
正規化セルＰ （ｑ，ｎ）はそれぞれ対応するセルと、
該隣合うセルとより情報が加わる。すなわち前段のセル
とそのセルに隣合う左右のセルからの合計３つの情報が
加わる。これをＮ個を並列とし、Ｑ段のシストリックア
レイを構成する。Each normalized cell P (q, n) has a corresponding cell,
More information is added to the adjacent cell. That is, a total of three pieces of information are added from the previous cell and the adjacent left and right cells. N pieces of these are arranged in parallel to form a Q-stage systolic array.
各正規化セルＰ（ｑ、１）〜Ｐ （ｑ，ｎ）には正規化
すべき画像の行方向のドット行データが加わり、それら
のセルは正規化値と変換値との積が、最大幅とその位置
との積より小さい時に対応するセルの隣のセルのデータ
を取り込み、正規化値と変換値との積が最大幅と該セル
位置との積以上の時前記隣のセルに対向する隣のセルの
データを取り込む。その各正規化セルＰ（ｑ，１）〜Ｐ
（ｑ．ｎ）で求めたデータは次の正規化セルＰ（ｑ−１
．１）〜Ｐ（ｑ−１，ｎ．）に加わり、同様の処理を行
う。そして次のセルへと順次処理を行う。例えば、正規
化セルＰ （３．３）であるならば隣のセルは正規化セ
ルＰ （３．２）であり、対向する正規化セルは正規化
セルＰ （３．４）となる。Dot row data in the row direction of the image to be normalized is added to each normalization cell P (q, 1) to P (q, n), and for those cells, the product of the normalization value and the conversion value is the maximum width When the product of the normalized value and the transformed value is smaller than the product of the maximum width and the cell position, the data of the cell next to the corresponding cell is taken in, and when the product of the normalized value and the converted value is greater than or equal to the product of the maximum width and the cell position, the data of the cell next to the corresponding cell is taken in. Import data from adjacent cells. Each normalized cell P (q, 1) ~ P
The data obtained in (q.n) is the next normalized cell P(q-1
．． 1) to P(q-1, n.) and performs similar processing. Then, processing is performed sequentially to the next cell. For example, if the normalized cell is P (3.3), the adjacent cell is the normalized cell P (3.2), and the opposing normalized cell is the normalized cell P (3.4).
以上の動作を各段順次合計Ｑ回行うことにより目的とす
る領域の文字を正規化した領域に拡大や縮小することが
できる。By performing the above operation sequentially for each stage a total of Q times, characters in the target area can be enlarged or reduced to a normalized area.
以下図面を用いて本発明を詳細に説明する。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 stores each dot of the read information as binary data of white or black, that is, 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 l4, 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 of each dont unit.
すなわち、１ドットの行（横方向）に対し、その１ドソ
ト行にいくつの黒ドットが存在するかを各１ドット行単
位で求める処理である。また列ヒストグラム１４は前述
した行ヒストグラムと同様に列方向に対し投影し、その
投影した黒ドットの数を求める処理である。That is, this is a process of determining how many black dots are present in one dot row (horizontal direction) for each one dot row. The column histogram 14 is a process of projecting in the column direction and calculating the number of projected black dots in the same way as the row histogram described above.
画像メモリ１０から行方向に順次１ドノト単位で読み出
し、ノイズ除去モジュール１１を介して加わったデータ
（ラスタースキャンと同様のドットの読み出し）を、行
ヒストグラムモジュール１３は順次黒のドットをカウン
トする（１ドット行分）。そして、順次行単位で黒のド
ント数を求める。この黒のドノト数が各行に対応する行
ヒストグラムとなる。また列ヒストグラム１４は１ドッ
ト行内のドノト数に対応してそれぞれカウンタを有し１
行のドノトが順次加わる度に黒ドットに対応するカウン
タをインクリメントする。前述した動作を１頁分行うこ
とにより行ヒストグラムモジュール１６ならびに列ヒス
トグラムモジュール１４からは、それぞれ行位置ならび
に列位置に対するドット数を表したいわゆる行ヒストグ
ラム１列ヒストグラムが求められる。そしてその結果は
読み出し制御モジュール１５に加わる。The row histogram module 13 sequentially counts black dots (1 dot read out) from the image memory 10 in the row direction and adds the data through the noise removal module 11 (dot reading similar to raster scanning). dot line). Then, the number of black donts is calculated sequentially for each row. The number of black dots becomes the row histogram corresponding to each row. The column histogram 14 also has a counter corresponding to the number of dots in one dot row.
The counter corresponding to the black dot is incremented each time a dot is added to a row. 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 one 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 noise removal module 1 mentioned above again to obtain the final histogram.
From the point where the row histogram L (the histogram takes the maximum value) obtained by the corrected slope changes from O to positive (it can be positive to 0), read one row of data corresponding to the slope for one period, The data is stored in a row buffer provided within the read control module 15.
読み出し制御モジュール１５はさらにその行ハッファに
格納した１行のデータの内、行内における列ヒストグラ
ムを再度求め、列ヒストグラムが０から正に変化する位
置からそのデータを切り出し正規化モジュール１６に出
力する。また変換表作成モジュール１７にも出力する。The read control module 15 further obtains the column histogram within the row of one row of data stored in the row huffer, cuts out the data from the position where the column histogram changes from 0 to positive, and outputs it to the normalization module 16. It is also output to the conversion table creation module 17.
この切り出したデータは１文字領域のデータである。This extracted data is data for a single character area.
変換表作成モジュール１７は正規化モジュール１Ｇによ
って１文字を正規化するための変換データを求めるモジ
ュールであり、読み出し制御モジュール１５によって切
り出した１文字領域に対し、列方向ならびに行方向に投
影し、黒ドットが存在する列ならびに行からドット単位
（行や列単位）で、列ならびに行方向のカウンタをイン
クリメントし、１文字の領域内の最終値までの値を求め
る。The conversion table creation module 17 is a module that obtains conversion data for normalizing one character using the normalization module 1G. Counters in the column and row directions are incremented dot by dot (row and column) starting from the column and row where the dot exists, and the value up to the final value within the area of one character is determined.
正規化モジュール１６では、この１文字で切り出したド
ットの行方向並びに列方向の最終値並びに切り出した１
文字の大きさから、その文字が切り出し領域内の全域に
わたって存在する文字に拡大する。例えば６４Ｘ６４ド
ットの領域を１文字領域とする拡大処理を行う。文字の
列方向並びに行方向の値が変換表作成モジュール■７に
おいて４８（列並びに行とも）ドットであったならば、
４８ドットの文字を６４ドットに変換する処理を行う。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 value in the column direction and row direction of the character is 48 dots (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 18 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 with a total of 11 dots, including 1 dot to the left and 2 dots above from the center. Moreover, this mask can also be performed using 9 dots of 3×3.
前述のマスクによってあらかしめ決められたパターンで
あるときに中心ドットをＯとする制御により１回の処理
によって文字を構成するドットの１ドソト分の回りの細
線化が図れる。このマスクの細線化を順次繰り返すこと
により１ドットの線による文字とすることができる。By controlling the center dot to be O when the pattern is predetermined by the above-mentioned mask, thinning of lines around one dot of the dots constituting the 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. This line segmentation module calculates the sum of black dots that 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 four types of line elements. If the line element belongs to more than one of the four types described above, priority is given in the order of, for example, the vertical direction, then the horizontal direction, etc., and it is determined in which direction the line element exists for each dot.
なお中心がＯドソトすなわち白であった場合には線は存
在しないとする。Note that if the center is Odosoto, that is, white, it is assumed that no line exists.
線素化モジュール１９６こおいては、上下、左右、右上
がり斜め、左上がり斜めの４方向さらには線素が存在し
ない場合の５種類があるので、その状態を各ドット単位
で３ピントの値で表し、合計３Ｘ６ ４ Ｘ６ ４の情
報とし、特徴ベクトルモジュール２０に加える。In the line segmentation module 196, there are 4 directions: up and down, left and right, upward diagonal to the right, diagonal upward to the left, and 5 types of cases where no line element exists, so the state is determined by 3 focus values for each dot. The information is expressed as 3×6 4×6 4 in total 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× 281 +ti) total 16
Let the dot area be one vector module area, and that 1
It counts how many line elements exist in the vector module area in four directions: vertical, horizontal, upper right, and upper left. The feature hectares are calculated using the area of 16XI6 donoto as one vector module area, but this one vector module area is moved in units of 8 dots, so there are 7 areas in each of the row and column directions, and a total of 7 x 7 feature vectors. It becomes an area.
特徴ベクトル化モジュール２０においては前述した１領
域単位でその方向の数を求めているが、この数の求める
場合にはそれぞれ重み付けをし、中心部を高く周り部を
外にいくにしたがって低くしている。例えばその重み付
けを中心の４×４の領域の各ドットを重み４、その周り
の２ドット分の各ドットを３、さらにその周りの２ドノ
ト分の各ドットを２、さらにその回りの２ドット分の各
ドットを１とし、重み付けを行って特徴ベクトルを求め
る。In the feature vectorization module 20, the number of directions is calculated for each area as described above, but when calculating this number, weighting is applied to each area, with the center being higher and the surrounding areas being lower as they move outward. There is. 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 hector has all the characters to be recognized the same size by the normalization module 16, so
If they are the same characters, they have almost the same characteristic hector,
The feature vectors differ for each character. However, since there are very similar modules, in the embodiment of the present invention, in order to speed up the calculation process and improve the recognition rate, 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 Suinochi 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, if it is the first distance (short distance), 5 points are given, then 4 points, 3, 2.1 points, etc. are given to the class. These are provided corresponding to squares 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 (l), the associative dictionary has candidate I for each mask.
With D as an address, the class ID of the class to which the candidate belongs in the mask is stored.
このデータは、各候補のマスクＩＤに対応するＣｄｉｍ
次元の部分ベクトルの集合をその（重み付き）距離によ
ってクラスタリングして得られるものであり、結果だけ
が連想辞書に格納される。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 to each other and have the same type. When storing two or more types of dictionaries in one memory, the specification of the dictionary to be used becomes the dictionary reference start position. (Divide this dictionary into 10 candidates,
Comprehensive evaluation can be performed for each in parallel, and if higher speed is required, it can be easily achieved).
連想辞書２３−３は、候補ａがマスクｍで属するクラス
のクラスＩＤ：Ｋを記した表であり、これをＣ （ｍ，
ａ） 一Ｋと表すと、候補ａ （−１〜ｃ ｃａｎｄ
）に対して、で得られる。尚、ここでＰ （ｍ，ｋ）は得点を表して
いる。この式により候補ａに対する総合評価値Ｖ （ａ
）を得る。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,
a) If expressed as 1K, candidate a (-1~c cand
), it is obtained by . 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 motes that are calculated for each candidate.
全数整合モードはａ−１〜ｃ ｃａｎｄ、個別整合モ
ートはＪ＝Ｉ 〜ｃ ｋｉｎｄ，ａ＝ｂ（ｊ）とレ、
距離をｄ （ｍ，ａ）で表しを求める。この値Ｖ （ａ）は候補ａと入力対象との特
徴ベクトルの（重み付き）距離である。The complete matching mode is a-1 to c can, and the individual matching mode is J=I to c kind, a=b(j),
Express the distance by d (m, a). This value V (a) is the (weighted) distance of the feature vector between 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 pipeline processing, divided into lines by the control module 15, and outputted to the normalization module 16 in units of characters. The character alone is thinned or lined as mentioned above. The top selection module 25 that performs feature vectorization and recognition processing is a module that ranks candidates and selects the top five based on the comprehensive evaluation value.
If the input is in associative exhaustive matching mode ((a',
V(a)! a', a = 1 ~ modified version of C can} 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 2 in descending order, others: in descending order). Further, the output is the candidate IDs (or input order) arranged in the order of the input sort results and their comprehensive evaluation values.
第２図における正規化モジュール１６が拡大や縮小処理
を実行する場合には、読み出し制御モジュール１５によ
って切り出した一文字領域内の文字の大きさを求めなく
てはならない。何故ならば本発明の実施例における認識
処理においては認識率を高めるため文字を同し大きさに
しなくてはならないからである。このため第３図におけ
る拡大の原理説明図からも明確なようにＸ軸上のＯ≦Ｘ
≦Ｗの領域をＹ軸上のＯ≦Ｙ≦Ｄの領域に変更する処理
を行う。When the normalization module 16 in FIG. 2 executes enlargement or reduction processing, the size of a character within a single character area 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, O≦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.
以下では、先ず拡大原理から説明し、続いて変換表作成
モジュール１７の詳細な回路動作さらに正規化について
説明する。Below, the enlargement principle will be explained first, and then the detailed circuit operation of the conversion table creation module 17 and the normalization 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 T(I
is an integer, the coordinate on the original figure corresponding to 1≦■≦D
(X is an integer) It is assumed that the point satisfies X-1<Wxl/D≦X ·--2). By transforming this equation 2), D(X-i)<rXW≦DX...3) is obtained. Therefore, by setting the element at the coordinate ■ for each I (1≦I≦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 a histogram in the horizontal direction and in the fir direction is 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 region RX is cut out by the readout control unit 15 (see FIG. 2) and input to the histogram generation circuit m(NXN) 31 row by row. Histogram generation circuit network (NxN) 3 1 is a circuit for calculating the histogram in the vertical and horizontal directions and the width of the input character shown in FIG. Stored as a value.
また横方向のヒストグラムはヒストグラム生成回８３１
から正規化回路網３４に図示しないが直接加わる。Also, the horizontal histogram is histogram generation time 831.
The normalization circuitry 34 is directly connected to the normalization circuitry 34 (not shown).
ヒストグラム生成回路ｙ４３１はＮｘＮのシストリック
アレイ構造を有しており、ヒストグラム生成回路綱３１
を通遇した画像データ（画像データに変化はない）はバ
ッファ（ＮＸＮ）３３に格納される。すなわち画像ＲＸ
が最終的にはバッファ３３に格納される。尚第２図にお
いては読み出し制御モジュール１５の出力は正規化回路
網１６にも加わるので、この場合にはこのバッファ３３
は必要ではなく正規化モジュール１６内に設けても良い
。The histogram generation circuit y431 has an NxN systolic array structure.
The image data passed through (the image data remains unchanged) is stored in the buffer (NXN) 33. That is, 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, this buffer 33
is not necessary and may be provided in the normalization module 16.
このヒストグラム生成回路網３１によって得られた緬方
向並びに横方向のヒストグラムは正規化回路モジュール
１６に加わり、このヒストグラムをもとに正規化モジュ
ール１６は動作する。尚正規化回路綱３４は横方向（列
単位）の正規化を行う回路である。縦方向（行単位）の
正規化はバノファ３３ （ＭｘＮ）からのデータ読み込
み用セル構造回路３５によるドット行単位の呼び出しに
よって正規化している。すなわち縦方向の正規化を行い
ながら横方向の正規化に必要な計算をし、この値と入力
データを正規化回路網３４に出力する。The vertical and horizontal histograms obtained by the 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 34 is a circuit that performs horizontal direction (column unit) normalization. Normalization in the vertical direction (in units of rows) is performed by calling in units of dot rows by the cell structure circuit 35 for reading data from the vanofer 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 network 34.
データ読み込み用セル構造回路Ｎ４３５は縦方向を正規
化する回路であり、データ読み込み用セル回路綱３５と
正規化回路網３４の動作が始まる時刻をｔ＝１とするな
らば、縦方向の正規化を行うため、時刻もで正規化後の
図形のｔ行目に対応する行を読み込む。The data reading cell structure circuit N435 is a circuit that normalizes the vertical direction, and if the time when the data reading cell circuitry 35 and the normalization circuit network 34 start operating is t=1, then the vertical normalization is performed. In order to do this, read the line corresponding to the t-th line of the figure after normalization based on the time.
Ｄ − ｈ２（ｉ’ −１） ＜ ｔ Ｌ≦Ｄ−ｈ２（
ｉ”） ・・・４）が成り立つよう、入力画像の行ｉ゛
を時刻Ｌ７−読み取る。換言するならば、ヒストグラム
の値が４）式を満足するまで縦方向（行の読み出し順方
向）のヒストグラムと入力画像を読み込めば、縦方向の
正規化が行える。これはｗｈｉｌｅ （ ｔ Ｌ ＞ Ｄ−ｈ２（ｉ’） ＆＆
ｉ’＜Ｍ ）ｒｅａｄ ｄａｔａ ＆＆ ｈｉｓｔｏ
ｇｒａｍ；なる処理をセルが行うことで実現できる。ま
た、横方向の正規化を行う時も３）式を満足する処理を
行えば良い。横方向のヒストグラムの値および横方向の
文字幅Ｗ呼び込みＪ列のセルではＤ−ｈｌ（ｊ−１）’
， “ｊ ＩＡ ’， ’ Ｄ−ｈｌ（ｊ）を計
算し、さらにＤ −１＋１（ｊ’）＜ｊ ’ｄ ならば ｊ−＋
ｊ−１ｊ Ｗ ≦Ｄ−ｈｌ（ｊ’−１） ならば ｊ
−＋ ｊ −１− １と変換していくことで行う。尚
ｊは正規化の図形における列、ｊ”は入力図形のおける
列を表している。D − h2(i' −1) < t L≦D−h2(
i'')...The line i'' of the input image is read at time L7 so that 4) holds true.In other words, the histogram is read in the vertical direction (line reading forward direction) until the histogram value satisfies equation 4). By loading the histogram and the input image, vertical normalization can be performed. This is done 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. Horizontal histogram value and horizontal character width W In the cell of column J, D-hl(j-1)'
, "j IA ', ' Calculate D-hl(j), and if D -1+1(j')<j 'd, then j-+
j-1j If W ≦D-hl(j'-1) then j
This is done by converting −+ j −1− 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 line 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. 4, the input data RX of
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 H(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 each
The structure is such that the data is output from the second to the third. In other words, the shift registers are sequentially moved from cell H(N, l) to cell H(
1. Up to 1) are configured with shift registers, and then 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, in the same way, in the third position, and in turn the final Specifically, 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 corresponding to one crotter to the next stage shift register or histogram calculation cell. 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 histogram generation circuit network begins is t=1, and t is incremented by 1 every clock, the operation of each cell at time t is as follows.
■ ｔ≦Ｍのとき、セル（Ｎ，１）〜セル（ＮＮ）は入
力データのｔ行目を読み込む。Ｍ＜ｔのとき，セル（Ｎ
，１）〜セル（Ｎ．Ｎ）はＯを読み込む。(2) When t≦M, cells (N, 1) to (NN) read the t-th row of input data. When M<t, the cell (N
, 1) ~ Cell (N.N) reads O.
■ ヒストグラム計算セル（ｉ，Ｎ−ｉ＋１）はセル（
ｉ＋１，Ｎ ｉ）から送られてきた演算結果とセル（
ｉ＋１，Ｎ−ｉ＋１）から送られてきたデータを用い、
後述のセルの動作に従って処理を行う。■ Histogram calculation cell (i, N-i+1) is cell (
i+1, N i) and the calculation result sent from cell (
Using the data sent from i+1, N-i+1),
Processing is performed according to the cell operation described later.
■ ヒストグラム計算セル（ｉ，Ｎ−ｉ＋１）は、演算
結果をセル（ｉ−１，Ｎ−ｉ＋２）に送る。(2) Histogram calculation cell (i, N-i+1) sends the calculation result to cell (i-1, N-i+2).
マタ、１〜Ｎ−１行のすべてのセルｃｉ，ｊ）は、セノ
レ（ｉ＋１，ｊ）から送られてきたデータをそのままセ
ル（ｉ−１，ｊ）に送る。All cells ci, j) in rows 1 to N-1 send the data sent from cell (i+1, j) as is to cell (i-1, j).
但し、Ｎ≦ものときセル（１，Ｎ）の演算結果は入力デ
ータの横方向のヒストグラム（（Ｎ−ｔ＋１）行目）の
イ直（ｘｗｉｄｔｈ ， ｘｃｏｕｎｔ）となるから、
（ＭＸＩ）のバッファ３２に格納していく。また、セル
（１．ｊ）（０≦ｊ≦１）のデータ（ｙｗｉｄｔｈ，ｙ
ｃｏυｎｔ）は（ＭＸＮ）のバノファに送られる。However, when N≦, the calculation result of cell (1, N) becomes the horizontal histogram ((N-t+1)th row) of the input data, so
(MXI) buffer 32. Also, data (ywidth, y
coυnt) is sent to Vanofa of (MXN).
以上の動作はＭ＋Ｎ−１クロシクで全て完了し、Ｊ行目
のヒストグラム計算セルに入力データのＪ行目（横方向
）のヒストグラムの値が格納され、（ＭＸＩ）のバッフ
ァのＩ行目に入力データの１行目（樅方向）のヒストグ
ラムの値が格納されることになる。All the above operations are completed in M+N-1 cross cycles, 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 input to the I-th row of the buffer of (MXI). The histogram value of the first row of data (in the fir direction) will be stored.
セルを第６図のように配置すれば、たとえば入力図形の
Ｉ行目のデータがセル（Ｎ，１）で処理され、時刻（＋
＋１）で処理結果とその２行目のデータがセル（Ｎ−１
．２）で処理されるという具合に同じ行のデータが順に
出会っていくので縦方向と横方向のヒストグラムが同時
に作れる。尚セルを第６図のように配置するかわりに１
次限に配置されたヒストグラム計算セルを用い、図７に
示すようにデータを１クロックづつ別単位で遅延させて
入力してもよい。前述では横方向、縦方向の動作につい
て説明したが以下では前述のヒストグラム計算セルの動
作についてさらに詳細に説明する。If the cells are arranged as shown in Figure 6, for example, the data on the I-th row of the input figure will be processed in the cell (N, 1), and the data at the time (+
+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) column H, and if it is 1 or more, adds 1 to that value and sets 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 ividth stores a character width value.゛X゛y゜ represents the vertical direction or the horizontal direction. Also, yfla
g, xiuidth, xcount process using the value of the cell in the left column and send the result to the right cell, and ywidt
h, ycount, and xfalg process using the values of their own cells and store the results in their own cells. and xfl
ag, xcount, xi++idth and yfla
g, ycount, and ywi6th are each determined by the following formulas.
横方向ｘｆｌａｇ ＝ ｉｆ ｄａｔａ ＝＝１ ｔＪ＋ｅｎ
１ｅｌｓｅ ｘｆｌａｇｘｃｏｕｎｔ ＝ ｉｆ ｘｃｏｕｎｔ＞Ｏ ｔｈｅｎ
ｘｃｏｕｎｔ＋１ｅｌｓｅ ｉｆ ｘｆｌａｇ＝＝１
ｏｒ ｄａｔａ＝＝１ ｔｈｅｎ １ｅｌｓｅ ｘｃ
ｏｕｎｔｘｗｉｄｔｈ ＝ ｉｆ ｘｆｌａｇ＝＝１ ｏｒ ｄ
ａｔａ＝＝１ ｔｈｅｎ ｘｃｏｕｎｔ＋１ｅｌｓｅ
ｘｗｉｄｔｈ縦方向ｙｆｌａｇ 二ｉｆ ｄａｔａ＝＝１ ｔｈｅｎ １ｅ
ｌｓｅ ｙｆｌａｇｉｆ ｙｃｏｕｎｔ＞Ｏ ｔｈｅｎ ｙｃｏｕｎｔ＋１
ｅｌｓｅ ｉｆ ｙｆｌａｇ＝＝１ ｏｒ ｄａｔａ＝
＝１ ｔｈｅｎ １ｅｌｓｅ ｙｃｏｕｎｔｙｗｉｄｔｈ ＝ ｉｆ ｙｆｌａｇ＝＝ｌ ｏｒ ｄ
ａｔａ＝＝ｌ ｔｈｅｎ ｙｃｏｕｎｔ＋１ｙｃｏｕｎ
ｔｅｌｓｅ ｙｗｉｄｔｈこのようなセルを用いて処理を行うと、最終的に、横方
向のヒストグラムは各セル内のｘｃｏｕｎｔに、横方向
の文字幅はセル（１，Ｎ）のｘｗｉｄｔｈに、紺方向の
文字幅はセル（１，Ｎ）のｙｗｉｄｔｈに格納され、縦
方向のヒストグラムは、時刻Ｎ以降セル（１，Ｎ）のｙ
ｃｏｕｎｔとして順に出力されることになる。Lateral direction xflag = if data ==1 tJ+en
1else xflag xcount = if xcount>O then
xcount+1else if xflag==1
or data==1 then 1else xc
ount xwidth = if xflag==1 or d
ata==1 then xcount+1else
xwidth Vertical direction yflag 2 if data==1 then 1e
lse yflag if ycount>O then ycount+1
else if yflag==1 or data=
=1 then 1else ycount ywidth = if yflag==l or d
ata==l then ycount+1ycount
t else ywidth When processing is performed using cells like this, the horizontal histogram is finally set to xcount in each cell, the horizontal character width is set to xwidth of cell (1, N), and the dark blue direction is set to xcount in each cell. The character width is stored in ywidth of cell (1, N), and the vertical histogram is stored in ywidth of cell (1, N) after time N.
It will be output in order as a count.
次に非線形の場合のヒストグラム計算セルの横方向のヒ
ストグラムについて説明する。非線形の場合は、各列ご
とに、黒画素を横切る回数を数え、それを積算していく
。従って、ｊ列目のセルは、ｊ列内で黒画素を横切った
回数を計算し、その値を積算する。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' indicates whether the direction is vertical or horizontal. Also, yfa
lg, ycount, xstack is the left column (7)
Cell (7) {i Processes using wo and sends the result to the cell on the right, processes ystack, xcount, and xflag using the values of its own cell and stores the results in its own cell.
そして、ｘｆｌａｇ，ｘｃｏｕｎｔ，ｘｓｔａｃｋ，並
びにｙｆｌａｇ，ｙｃｏｕｎｔ，ｙｓｔａｃｋはそれぞ
れ以下の式によって決定される。Then, xflag, xcount, xstack, and yflag, ycount, ystack are determined by the following formulas, respectively.
横方向ｘｆｌａｇ ＝ｉｆ ｄａｔａ＝＝ｏ ｔｈｅｎ Ｏｅｌｓｅ
１＝ ｉｆ ｄａｔａ＝＝１ ａｎｄ ｘｆｌａｇ＝＝Ｏ
ｔｈｅｎ ｘｃｏｕｎｔ＋ｘｓｔａｃｋ＋］ｅｌｓｅ
ｘｃｏｕｎｔ＋ｘｓｔａｃｋｉｆ ｄａｔａ＝＝ｌ
ａｎｄ ｘｆｌａｇ＝＝Ｑｅｌｓｅ ｘｓｔａｃｋｘｃｏｕｎｔｘｓｔａｃｋｔｈｅｎｘｓｔａｃｋ＋１縦方向ｙｆｌａｇｙｃｏｕｎｔｉｆ ｄａｔａ＝＝ｏ ｔｈｅｎ Ｏｅｌｓｅ
１＝ ｉｆ ｄａｔａ＝＝１ ａｎｄ ｙｆｌａｇ＝＝
０ｔｈｅｎ ｙｃｏｕｎｔ＋ｙｓｔａｃｋ＋１ｅｌｓｅ
ｙｃｏｕｎｔ＋ｙｓｔａｃｋ＋１ｙｓｔａｅｋ ＝
ｉｆ ｄａｔａ＝＝１ ａｎｄ ｙｆｌａｇ＝＝Ｏ ｔ
ｈｅｎ ｙｓｔａｃｋ＋１ｅｌｓｅ ｙｓｔａｃｋこのようなセルを用いて処理を行うと、最終的に、横方
向のヒストグラムは第１０図の例に示すごとく横方向の
文字幅はセル（１，Ｎ）のｘｃｏｕｎｔに、縦方向の文
字幅はセル（Ｌ Ｎ）のｙｃｏｕｎｔに格納され、縦
方向のヒストグラムは、時刻ＮＪ：Ｊ．ＩＩセル（１，
Ｎ）のｙｃｏｕｎｔとして順に出力されることになる。Horizontal xflag = if data = = o then Oelse
1 = if data==1 and xflag==O
then xcount+xstack+]else
xcount+xstackif data==l
and xflag==Qelse xstack xcount xstack then xstack+1 Vertical direction yflag ycount if data==o then Oelse
1 = if data==1 and yflag==
0then ycount+ystack+1else
ycount+ystack+1ystaek=
if data==1 and yflag==O t
hen ystack+1else ystack When processing is performed using such a cell, the horizontal histogram will eventually be as shown in the example in Figure 10, where the horizontal character width is equal to xcount of cell (1, N), and the vertical The character width is stored in ycount of cell (LN), and the vertical histogram is at time NJ:J. II cell (1,
N) will be output in order as ycount.
以上のようにヒストグラム計算セルを構成することによ
り、線形、非線形のヒストグラムである変換表を得るこ
とができる。By configuring the histogram calculation cell as described above, a conversion table that is a linear or nonlinear histogram can be obtained.
第１１図は本発明の正規化回路網の構成図である。デー
タ読み込み用セル構造回路網３５（第４図参照）データ
読み込みセルＲ．Ｓ１〜ＲＳｎよりなり、ヒストグラム
生成回路網３１によってヒストグラムが求められてバッ
ファ３３に格納されたデータをドット行単位で読み込む
。本発明の実施例においては横方向はこの正規化回路網
３４によって正規化し縦方向は前述したデータ読み込み
用セル構造回路網３５で行っている。FIG. 11 is a block diagram of the normalization circuit network of the present invention. Data reading cell structure circuit network 35 (see FIG. 4) Data reading cell R. The histogram generation circuit 31 reads the data stored in the buffer 33 in units of dot rows. In the embodiment of the present invention, the horizontal direction is normalized by this normalization circuit network 34, and the vertical direction is normalized by the aforementioned data reading cell structure circuit network 35.
データ読み込み用セル回路網３５は前述の樅方向の正規
化を行いながら横方向の正規化に必要な値を計算し、こ
の値と入力データを正規化回路網３４に渡す。The data reading cell circuit network 35 calculates the value necessary for normalization in the horizontal direction while performing the above-mentioned normalization in the vertical direction, and passes this value and input data to the normalization circuit network 34.
第１７図は正規化セルの構成図である。各セルには対応
するセル（前段のセル）からＴ２，Ｕ２，Ｌ２，Ｅ２が
加わる。また対応するセルの隣からはＵｌ．Ｌｌ．Ｅｌ
がその反対方向のセルからはＵ３，Ｌ３．Ｅ３が加わる
。各セルは各正規化セルＰ（１，ｊ）は前述の入力から
Ｐ， Ｕ， Ｌ， Ｅを求め次段の正規化セルに
加える。この正規化セルＰ（ｆ，ｊ）は第１２図に示す
それぞれの処理を行う。すなわちｔ ＝ ｔ２ｕ−ｉｆｆｆ２≧ｔ２ ｔｈｅｎ ｕｌｅｌｓｅ ｉｆ
ｕ２ ＜ｔ２ ｔｈｅｎ ｕ３ｅｌｓｅ ｕ２ｆｆ＝ｉｆ２≧ｔ２ｔｈｅｎ ｆｌｅｌｓｅ ｉｆ ｕ２ ＜ｔ２ ｔｈｅｎ Ｉ！
３ｅｌｓｅ １２ｅ＝ｉｆｆ２ ≧ ｔ２ ｔｈｅｎ ｅｌｅｌｓｅ
ｉｆ ｕ２ ＜ ｔ２ ｔｈｅｎ ｅ３ｅ
ｌｓｅ ｃ２なる処理を行う。この得られた結果ｔ，ｕ，１ｅを次の
セルＰ（１−１，ｊ）へ出力する。尚この結果はそれぞ
れ隣のセルにも出力する。換言するならばセルＰ （１
−１， ｊ−１）、Ｐ （１−１，ｊ＋１）へ出力す
る。FIG. 17 is a configuration diagram of a normalization cell. T2, U2, L2, and E2 are added to each cell from the corresponding cell (previous cell). Also, from next to the corresponding cell, Ul. Ll. El
However, from the cells in the opposite direction, U3, L3 . E3 will be added. Each normalized cell P(1,j) obtains P, U, L, and E from the above-mentioned input and adds them to the next normalized cell. This normalized cell P(f,j) performs each process shown in FIG. That is, t = t2 u-ifff2≧t2 then ulelse if
u2 <t2 then u3else u2 ff=if2≧t2then fl else if u2 <t2 then I!
3 else 12 e=if2 ≧ t2 then else
if u2 < t2 then e3e
The process lse c2 is performed. The obtained results t, u, 1e are output to the next cell P(1-1,j). Note that this result is also output to each adjacent cell. In other words, cell P (1
-1, j-1), output to P (1-1, j+1).
以上の動作により正規化回路綱３４の処理によって横方
向の正規化を行うことができる。前述した正規化回路綱
ＮＸＤの横方向の段数は第４図に示す左並びに右方向の
拡大数によって段数を求めればよい。換言するならば左
や右のブランク（入力データ）の最大値とすればよい。Through the above-described operation, horizontal normalization can be performed by the processing of the normalization circuit 34. The number of stages in the horizontal direction of the normalization circuit NXD described above can be determined by the number of expansions in the left and right directions shown in FIG. In other words, the maximum value of the left and right blanks (input data) may be used.
すなわち文字の入力のドット幅の最大値を入力等処理し
ておけばよい。In other words, the maximum value of the dot width for character input may be processed for input, etc.
この処理によりＤＸＤの正規化された文字パターンを得
ることができる。Through this processing, a DXD normalized character pattern can be obtained.
Ｃ発明の効果〕以上述べたように、本発明によればシストリックアレイ
によってバイブラインでかつ並列に正規化処理を的確に
高速に行うことができる。また、文字等の認識処理に用
いることにより、文字の認識率の向上を計るとともに、
高速に行うことが可能となる。C. Effects of the Invention] As described above, according to the present invention, normalization processing can be performed accurately and at high speed in a parallel manner using a systolic array. In addition, by using it for character recognition processing, it is possible to improve the recognition rate of characters, and
It becomes possible to perform the process at high speed.
第１図は本発明の原理ブロック図、第２図は本発明の実施例のシステム構成図、第３図は拡
大の原理説明図、第４図は本発明の実施例の詳細な構成図、第５図は縦一
横方向のヒストグラム図、第６図は本発明の実施例のヒ
ストグラム生成回路網図、第７図はデータの流れの説明図、第８図はヒストグラム計算セルの詳細な構成図、第９図
はヒストグラム計算セル（非線形）、第１０図は横方向
のヒストグラム（非線形）図、第１１図は正規化回路網
の構成図、第１２図は正規化セルの構成図である。Ｐ（１．１）〜Ｐ （ｑ，ｎ）・・・正規化セル，Fig. 1 is a block diagram of the principle of the present invention, Fig. 2 is a system configuration diagram of an embodiment of the present invention, Fig. 3 is an explanatory diagram of the principle of enlargement, and Fig. 4 is a detailed configuration diagram of an embodiment of the present invention. Fig. 5 is a vertical and horizontal histogram diagram, Fig. 6 is a histogram generation circuit network diagram of an embodiment of the present invention, Fig. 7 is an explanatory diagram of data flow, and Fig. 8 is a detailed configuration of the histogram calculation cell. Figure 9 is a histogram calculation cell (nonlinear), Figure 10 is a horizontal histogram (nonlinear) diagram, Figure 11 is a configuration diagram of the normalization circuit network, and Figure 12 is a configuration diagram of the normalization cell. . P (1.1) ~ P (q, n) ... normalized cell,
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2008420AJPH03214282A (en) | 1990-01-19 | 1990-01-19 | Normalization system applying systolic array |
| EP91100646AEP0447751B1 (en) | 1990-01-19 | 1991-01-21 | Image processing system |
| DE69131304TDE69131304T2 (en) | 1990-01-19 | 1991-01-21 | Image processing system |
| CA002034617ACA2034617C (en) | 1990-01-19 | 1991-01-21 | Data processing system |
| US07/644,360US5436982A (en) | 1990-01-19 | 1991-01-22 | Data processing system |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2008420AJPH03214282A (en) | 1990-01-19 | 1990-01-19 | Normalization system applying systolic array |
| Publication Number | Publication Date |
|---|---|
| JPH03214282Atrue JPH03214282A (en) | 1991-09-19 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2008420APendingJPH03214282A (en) | 1990-01-19 | 1990-01-19 | Normalization system applying systolic array |
| Country | Link |
|---|---|
| JP (1) | JPH03214282A (en) |
| Publication | Publication Date | Title |
|---|---|---|
| Hsu et al. | Ratio-and-scale-aware YOLO for pedestrian detection | |
| CN112396002B (en) | SE-YOLOv 3-based lightweight remote sensing target detection method | |
| CN113642571B (en) | Fine granularity image recognition method based on salient attention mechanism | |
| Paisitkriangkrai et al. | Pedestrian detection with spatially pooled features and structured ensemble learning | |
| US20150036942A1 (en) | Object recognition and tracking using a classifier comprising cascaded stages of multiple decision trees | |
| US20220157077A1 (en) | Method for verifying the identity of a user by identifying an object within an image that has a biometric characteristic of the user and separating a portion of the image comprising the biometric characteristic from other portions of the image | |
| CN114758145A (en) | Image desensitization method and device, electronic equipment and storage medium | |
| CN112464954A (en) | Lightweight target detection network applied to embedded equipment and training method | |
| WO2024131115A1 (en) | Text sorting method and apparatus, and electronic device and storage medium | |
| KR102421604B1 (en) | Image processing methods, devices and electronic devices | |
| CN118522019B (en) | Text recognition method, electronic device and storage medium | |
| CN115965799B (en) | Image recognition method, device, computer equipment and storage medium | |
| Singh et al. | A comprehensive survey on Bangla handwritten numeral recognition | |
| CN116976372A (en) | Picture identification method, device, equipment and medium based on square reference code | |
| JPH03214282A (en) | Normalization system applying systolic array | |
| JPH03214283A (en) | Conversion table creation circuit using systolic array | |
| JP4418726B2 (en) | Character string search device, search method, and program for this method | |
| CN114694159A (en) | Engineering drawing BOM identification method and device, electronic equipment and storage medium | |
| Fischler et al. | An approach to general pattern recognition | |
| JPH03214284A (en) | Data conversion system | |
| JPH03268088A (en) | General evaluation circuit | |
| JPH03214285A (en) | Data conversion system | |
| JPH03240175A (en) | histogram calculation circuit | |
| JP2018136703A (en) | Image recognizing device | |
| JP2002236877A (en) | Character string recognizing method, character recognizing device and program |