JPH03214282A - シストリックアレイによる正規化方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　　要〕 シストリックアレイ構造によって入力パターンの大きさ
を正規化するシストリックアレイによる正規化方式に関
し、 入力するデータを各処理単位で並列にさらにはバイブラ
イン処理を行いパターン認識を高速化するシストリック
アレイによる正規化方弐を提供することを目的とし、 対応するセルと、該セルと隣合う２個のセルとより情報
が加わり、正規化値と変換値との積が最大幅と該セル位
置との積より小さい時に対応するセルの隣のセルのデー
タを取り込み、正規化値と変換値との積が最大幅と該セ
ル位置のセル以上の時前記隣のセルに対向する隣のセル
のデータを取り込むセルを複数個複数段に渡って設ける
ように構成する。

〔産業上の利用分野〕

本発明はパターン認識装置に係り、更に詳しくはシスト
リックアレイ構造によって入力パターンの大きさを正規
化するシストリックアレイによる正規化方弐に関する。

〔従来の技術〕

コンピュータシステムの発展により、画像データを取り
込むとともに、取り込んだ画像データから文字を切り出
し、読み取った書類の文章のそれぞれの文字を認識する
読み取り装置が実用化している。この読み取り装置は例
えばイメージスキャナ等によって読み取ったドントデー
タをあらかじめ定められた領域単位で分割し、その分割
内での文字とあらかじめ定められた文字とを比較し、１
番似通った文字を結果として出力している。このあらか
じめ定められたデータは一般的には辞書メモリに格納さ
れており、例えば各規定の文字を特徴化したデータであ
る。そして認識すべき文字が入力した時、同様にその入
力した文字を特徴化し、前述の辞書メモリに格納されて
いるあらかじめ定められた特徴データとの距離を求めて
いる。この求めた距離が最も小さい文字を認識結果とし
て出力している。

前述のようなシステムにおいては、それらの処理はすべ
てドット単位で行っている。例えば１枡内の文字を切り
出して認識文字とし、その文字から特徴データを求める
ため３×３のウィンドウを設け、その３×３のドソトデ
ータから特徴を求めている。

前述の１枡内の文字の切り出しは、文字の大きさに依存
せず、１文字が入っている領域のみを切り出しているに
すぎない。

一般的に、認識率を高めるためこの認識における文字の
大きさが等しいことが望ましい。このため、従来におい
ては切り出した領域をドット単位やバイト単位で読み出
し、文字の大きさを判断するとともに、その１文字の正
規化をＣＰＵの処理において行っている。

〔発明が解決しようとする課題〕

従来のシステムにおいては、データの切り出し例えば１
文字単位の切り出しさらには１文字単位での文字の大き
さの正規化はドット単位やバイト単位の処理となり、デ
ータのアクセスに多くの時間を有する問題を有していた
。

また特徴データを求めるためにも、１文字単位で辞書デ
ータから特徴データを読み出し、入力した文字の特徴デ
ータと比較しているため、その比較に多くの時間を有す
るいう問題を有していた。

本発明は入力するデータを各処理単位で並列にさらには
バイブライン処理を行いパターン認識を高速化するシス
トリックアレイによる正規化方式を提供することを目的
とする。

〔課題を解決するための手段〕

第１図は本発明の原理ブロソク図である。

正規化セルＰ　（ｑ，ｎ）はそれぞれ対応するセルと、
該隣合うセルとより情報が加わる。すなわち前段のセル
とそのセルに隣合う左右のセルからの合計３つの情報が
加わる。これをＮ個を並列とし、Ｑ段のシストリックア
レイを構成する。

〔作　　用〕

各正規化セルＰ（ｑ、１）〜Ｐ　（ｑ，ｎ）には正規化
すべき画像の行方向のドット行データが加わり、それら
のセルは正規化値と変換値との積が、最大幅とその位置
との積より小さい時に対応するセルの隣のセルのデータ
を取り込み、正規化値と変換値との積が最大幅と該セル
位置との積以上の時前記隣のセルに対向する隣のセルの
データを取り込む。その各正規化セルＰ（ｑ，１）〜Ｐ
（ｑ．ｎ）で求めたデータは次の正規化セルＰ（ｑ−１
．１）〜Ｐ（ｑ−１，ｎ．）に加わり、同様の処理を行
う。そして次のセルへと順次処理を行う。例えば、正規
化セルＰ　（３．３）であるならば隣のセルは正規化セ
ルＰ　（３．２）であり、対向する正規化セルは正規化
セルＰ　（３．４）となる。

以上の動作を各段順次合計Ｑ回行うことにより目的とす
る領域の文字を正規化した領域に拡大や縮小することが
できる。

〔実　　施　　例〕

以下図面を用いて本発明を詳細に説明する。

第２図は本発明の実施例のシステム構成図である。

イメージスキャナ等によって読み取られた情報は画像デ
ータとして画像メモリ１０に格納される。

この画像メモリ１０はイメージスキャナで読み取る１頁
分の記憶容量を有しており、読み取った情報のそれぞれ
各ドットを白あるいは黒の２値すなわち０．１のデータ
として記憶する。

画像メモリ１０に格納された画像データはノイズ除去モ
ジュール１１に加わり、読み取り時に発生した雑音を除
去する。例えば、このノイズ除去モジュール１１によっ
て除去されるノイズは文字情報等に無関係な雑音例えば
３×３のマスクで中心を黒、その中心のドットを囲む８
ドットが白等の雑音であり、その中心のドットをノイズ
除去モジュール１１は白とする。このノイズ除去モジュ
ールは文字認識前処理部１２内に設けているがこれに限
るわけでなく、例えば後述する正規化モジュール１６内
に文字単位で格納する時に行ってもよく、またさらには
細線化、線素化の時に行ってもよい。

ノイズ除去モジュール１１によってノイズ除去された画
像情報は行ヒストグラムモジュール１３、列ヒストグラ
ムモジュールｌ４、さらには読み出し制御モジュール１
５に加わる。行ヒストグラムモジュールｌ３は読み取っ
た情報、例えば前述したイメージスキャナによって読み
取った用紙の内容を各ドノト単位で列方向に投影し、各
ドント単位の行のドット数を求めるモジュールである。

すなわち、１ドットの行（横方向）に対し、その１ドソ
ト行にいくつの黒ドットが存在するかを各１ドット行単
位で求める処理である。また列ヒストグラム１４は前述
した行ヒストグラムと同様に列方向に対し投影し、その
投影した黒ドットの数を求める処理である。

画像メモリ１０から行方向に順次１ドノト単位で読み出
し、ノイズ除去モジュール１１を介して加わったデータ
（ラスタースキャンと同様のドットの読み出し）を、行
ヒストグラムモジュール１３は順次黒のドットをカウン
トする（１ドット行分）。そして、順次行単位で黒のド
ント数を求める。この黒のドノト数が各行に対応する行
ヒストグラムとなる。また列ヒストグラム１４は１ドッ
ト行内のドノト数に対応してそれぞれカウンタを有し１
行のドノトが順次加わる度に黒ドットに対応するカウン
タをインクリメントする。前述した動作を１頁分行うこ
とにより行ヒストグラムモジュール１６ならびに列ヒス
トグラムモジュール１４からは、それぞれ行位置ならび
に列位置に対するドット数を表したいわゆる行ヒストグ
ラム１列ヒストグラムが求められる。そしてその結果は
読み出し制御モジュール１５に加わる。

読み出し制御モジュール１５はそれらの行ヒストグラム
，列ヒストグラムから行の位置ならびに列の位置を順次
求める。例えばこの位置は行ヒストグラムの周期や列ヒ
ストグラムの周期によって得ることができる。

読み出し制御モジュール１５は行ならびに列の位置を求
めるが、この他に以下の処理を行う。画像データ例えば
イメージスキャナから読みとった情報は紙の位置等によ
り傾きを有することがある。

このため、読み出し制御モジュール１５は列ヒストグラ
ムならびに行ヒストグラムが最大値をとるよう、ヒスト
グラムを求める角度を順次変更し、補正角度を求める。

そして前述したノイズ除去モジュール１】から加わる画
像情報を再度入力して、最終的なヒストグラムを求め、
その補正した傾きにより得られた行ヒストグラＬ（ヒス
トグラムが最大値をとる）がＯから正に変化する点（正
がら０でも可）より１周期分その傾きに対応した１行の
データを読み出し、読み出し制御モジュール１５内に設
けられた行バンファに格納する。

読み出し制御モジュール１５はさらにその行ハッファに
格納した１行のデータの内、行内における列ヒストグラ
ムを再度求め、列ヒストグラムが０から正に変化する位
置からそのデータを切り出し正規化モジュール１６に出
力する。また変換表作成モジュール１７にも出力する。

この切り出したデータは１文字領域のデータである。

変換表作成モジュール１７は正規化モジュール１Ｇによ
って１文字を正規化するための変換データを求めるモジ
ュールであり、読み出し制御モジュール１５によって切
り出した１文字領域に対し、列方向ならびに行方向に投
影し、黒ドットが存在する列ならびに行からドット単位
（行や列単位）で、列ならびに行方向のカウンタをイン
クリメントし、１文字の領域内の最終値までの値を求め
る。

正規化モジュール１６では、この１文字で切り出したド
ットの行方向並びに列方向の最終値並びに切り出した１
文字の大きさから、その文字が切り出し領域内の全域に
わたって存在する文字に拡大する。例えば６４Ｘ６４ド
ットの領域を１文字領域とする拡大処理を行う。文字の
列方向並びに行方向の値が変換表作成モジュール■７に
おいて４８（列並びに行とも）ドットであったならば、
４８ドットの文字を６４ドットに変換する処理を行う。

この処理では特定位置の行や列のデータを繰り返して同
じデータとし文字を拡大する。また、縮小の場合には特
定位置の行や列を繰り返し読み出してＯＲ加算し同一行
や同一列として縮小する。

正規化モジュール１６によって１文字領域例えば６４Ｘ
６４ドット内に１文字が拡大された後は、細線化モジュ
ール１８がその文字を細線化する処理を行う。この細線
化モジュール１８では中心ドントの上下左右１ドット（
３ｘ３）とさらにその左１ドットと中心からの上２ドッ
ト目の合計１１ドノトのマスクで細線化処理を行う。ま
たこのマスクは３×３の９ドットで行うこともできる。

前述のマスクによってあらかしめ決められたパターンで
あるときに中心ドットをＯとする制御により１回の処理
によって文字を構成するドットの１ドソト分の回りの細
線化が図れる。このマスクの細線化を順次繰り返すこと
により１ドットの線による文字とすることができる。

細線化モジュール１８によって得られた例えば６４Ｘ６
４ドットの細線化文字は線素化モジュール１９に加わり
線素化される。この線素化モジュールでは目的のドット
すなわち中心ドットから上下方向の黒ドットが存在する
場合、左右方向に存在する場合、右上、左下に存在する
場合、さらには左上、右下に存在する場合の合計４種類
の線素によって各ドットを表す。なお上述の４種類の内
、複数に属する場合には例えば、上下方向、続いて左右
方向等の順に優先化を行い、各ドット単位でその線素が
どちらの方向の存在するかを求める。

なお中心がＯドソトすなわち白であった場合には線は存
在しないとする。

線素化モジュール１９６こおいては、上下、左右、右上
がり斜め、左上がり斜めの４方向さらには線素が存在し
ない場合の５種類があるので、その状態を各ドット単位
で３ピントの値で表し、合計３Ｘ６　４　Ｘ６　４の情
報とし、特徴ベクトルモジュール２０に加える。

特徴ベクトルモジュール２０においては前述した線素化
モジュール１９で得られた線素化情報を、左右上下にそ
れぞれ８ドット単位で分割し、その分割した領域を下と
右方向に１領域づつ（２×２８１　＋ｔｉ）の合計１６
ドットの領域を１ベクトルモジュール領域とし、その１
ベクトルモジュール領域内にいくつの上下方向、左右方
向、右上方向、左上方向の４方向の線素が存在するかを
カウントする。１６ＸＩ６ドノトの鎮域を１ベクトルモ
ジュール領域として特徴ヘクトルを求めるが、この１ベ
クトルモジュール領域は８ドット単位で移動させるので
行方向ならびに列方向に対しそれぞれ７領域であり合計
７×７の特徴ベクトルの領域となる。

特徴ベクトル化モジュール２０においては前述した１領
域単位でその方向の数を求めているが、この数の求める
場合にはそれぞれ重み付けをし、中心部を高く周り部を
外にいくにしたがって低くしている。例えばその重み付
けを中心の４×４の領域の各ドットを重み４、その周り
の２ドット分の各ドットを３、さらにその周りの２ドノ
ト分の各ドットを２、さらにその回りの２ドット分の各
ドットを１とし、重み付けを行って特徴ベクトルを求め
る。

この特徴ヘクトルは特定の認識すべき文字を正規化モジ
ュール１６によってすべて同じ大きさにしているので、
同一文字であるならばほぼ同一の特徴ヘクトルを有し、
文字単位でその特徴ベクトルが異なってくる。しかしな
がら非常によく似たモジュールも存在するので、本発明
の実施例においては演算の処理の高速化さらには認識率
の向上をはかるため、特徴ベクトルの標準パターンを用
いてそれぞれの特徴ベクトル化領域すなわちマス内でク
ラス分けを行い、各マス内で２０クラスの標準パターン
と、加わる未知入力との距離を求める。すなわち標準パ
ターンの各マス内の特徴ヘクトルと特報ベクトルモジュ
ール２０によって得られたマス内の特徴ベクトルとの距
離をマス単位で求める。その各マスはクラス分け（クラ
ス１〜クラス２０）されており、各マス内クラスの距離
の順位を距離の小さい順に第５番目までのクラスを求め
る。

距離計算モジュール２１はこの距離をクラス辞書２３−
１　（標準パターンをクラス単位で記憶）を用いて演算
する。尚、個別でもその個々の候補文字に対して求める
場合には候補辞書２３−２を用いる（この時にはスイノ
チＳＷは候補辞書２３２を選択する）。

上位選出＆得点割当モジュール２２では前述の上位５ク
ラスを求めるとともに、各クラスに対応した得点を各マ
ス単位で決定する。すなわち上位選出＆得点割当モジュ
ール２２は距離計算モジュール２１より得られた距離か
らクラス単位で第１〜第５番目の順位の各クラスに対し
与える得点を決定し、各文字の得点を求める。例えば第
１番目の距離（短い距離）であったときには５点、その
次に４点、３，２．１とクラスに対し得点を与える。こ
れはマス１からマス４９に対応してそれぞれ設けられる
。上位選出得点モジュール２２の処理結果は総合評価モ
ジュール２４に加わる。

総合評価モジュール２４は入力対象すなわち入力文字と
その候補とが整合する度合いを計算するモジュールであ
り、連想整合モード、全数整合モード、個別整合モード
の３種類の動作がある。

連想整合モードは、連想辞書２３−３に格納されている
候補に対応したマスクとその属するクラスからその候補
の得点を計算するモードである。

連想辞書は第２図（ｌ））の如く、各マスク毎に候補Ｉ
Ｄをアドレスとして、その候補がそのマスクにおいて属
するクラスのクラスＩＤを格納している。

このデータは、各候補のマスクＩＤに対応するＣｄｉｍ
次元の部分ベクトルの集合をその（重み付き）距離によ
ってクラスタリングして得られるものであり、結果だけ
が連想辞書に格納される。

同時に距離計算モジュールにおけるクラス辞書２３−１
も対応して作成される。

尚、連想辞書２３−３とクラス辞書２３−１は対応して
おり、その種類は同じになる。２種類以上の辞書を１つ
のメモリに格納する場合、使用辞書指定は辞書参照開始
位置となる。（この辞書を候補１０について分割して、
それぞれについて並列に総合評価を行うことができ、よ
り高速なものが要求される場合容易に実現できる）。

連想辞書２３−３は、候補ａがマスクｍで属するクラス
のクラスＩＤ：Ｋを記した表であり、これをＣ　（ｍ，
ａ）　一Ｋと表すと、候補ａ　（−１〜ｃ　　ｃａｎｄ
）に対して、 で得られる。尚、ここでＰ　（ｍ，ｋ）は得点を表して
いる。この式により候補ａに対する総合評価値Ｖ　（ａ
）を得る。

総合評価モジュールの全数整合モード、個別整合モード
は各候補に対し、計算するモートであり。

全数整合モードはａ−１〜ｃ　　ｃａｎｄ、個別整合モ
ートはＪ＝Ｉ　〜ｃ　　ｋｉｎｄ，ａ＝ｂ（ｊ）とレ、
距離をｄ　（ｍ，ａ）で表し を求める。この値Ｖ　（ａ）は候補ａと入力対象との特
徴ベクトルの（重み付き）距離である。

上位候補選出モジュール２５は各文字対応での上位から
決められた複数の文字例えば５文字を選出し出力する。

この上位５文字が読みとった画像データにおける認識結
果となる。

前述した動作は全てパイプライン処理で成されるもので
ある。すなわち画像データを記憶する画像メモリ１０内
の例えば１頁分のデータをパイプライン処理のよって読
み出し、制御モジュール１５で行単位に分割するととも
に、正規化モジュール１６に１文字単位で出力する。そ
の文字単で前述の細線化，線素化．特徴ベクトル化さら
には認識処理を行う 上位選出モジュール２５は総合評価値に基づいて、候補
に順位をつけ、上位５個を選出するモジュールであり、
入力は連想全数整合モードであるならば（　（ａ’，　
Ｖ（ａ）　！ａ’，　ａ　＝　１　〜Ｃ　　ｃａｎｄを
修正したもの｝ 個別整数合モードであるならば （　（ｊ，　ｖ（ａＮｊ　＝　１〜ｃ　　ｋｉｎｄ，　
ａ　＝　ｂ　（ｊ））（個別整合の総合評価出力） 降／昇順：　（文字連想二大きい順、その他：小さい順
）である。また出力は入力のソート結果の順に並んだ候
補ＩＤ（または入力順序）とその総合評価値である。

第２図における正規化モジュール１６が拡大や縮小処理
を実行する場合には、読み出し制御モジュール１５によ
って切り出した一文字領域内の文字の大きさを求めなく
てはならない。何故ならば本発明の実施例における認識
処理においては認識率を高めるため文字を同し大きさに
しなくてはならないからである。このため第３図におけ
る拡大の原理説明図からも明確なようにＸ軸上のＯ≦Ｘ
≦Ｗの領域をＹ軸上のＯ≦Ｙ≦Ｄの領域に変更する処理
を行う。

以下では、先ず拡大原理から説明し、続いて変換表作成
モジュール１７の詳細な回路動作さらに正規化について
説明する。

Ｘ，Ｙが任意の実数値をとるものとすればＹ軸上の座標
Ｙに対応するＸ軸上のＸは Ｘ＝ＷｘＹ／Ｄ　　　　　　　　　　・−　−　１）で
表わされる。これを用いて拡大された図形の座標Ｔ（Ｉ
は整数、１≦■≦Ｄ）に対応する元の図形上の座標Ｘ（
Ｘは整数） Ｘ−１＜Ｗｘｌ／Ｄ≦Ｘ　　　　　　・−−２）を満た
す点であるものとする。この２）式を変形すると Ｄ（Ｘ−ｉ）＜ｒＸＷ≦ＤＸ　　　・・・３）が得られ
る。従って各Ｉ（１≦Ｉ≦Ｄ）について座標■の要素を
３）式を満たす元の図形の座標Ｘの要素とすることによ
り、幅Ｄに変形拡大された図形が得られる。

この考え方で入力画像データを正規化するため、先ず入
力図形に対して文字の幅Ｗを調べるとともに横方向や樅
方向のヒストグラムを作成する。すなわち、変換表を作
成する。

ヒストグラムは線形であるならば画像データ上の文字の
領域に含まれる最も左の点が属数列の値を１とし、それ
より右の列は１づつ増やすことによって得られる。また
行に対しても同様に、文字の領域に加わる最も上の点が
属する行の値を１としそれより下方の行を１づつ増やし
ていくことによって得られる。この文字の幅Ｗと列の先
端並びに行の先端を変換表作成モジュール１７は求める
。

第４図は本発明の実施例の構成図である。領域ＲＸが読
み出し制御部１５（第２図参照）より切り出されて行単
位でヒストグラム生成回路ｍ（ＮＸＮ）３１に入力する
。ヒストグラム生成回路網（ＮｘＮ）３　１は第５図に
示した縦方向、横方向のヒストグラムとその入力した文
字の幅を求める回路であり、継方向のヒストグラムはバ
ッファ（ＭＸＩ）３２に行単位の値として格納される。

また横方向のヒストグラムはヒストグラム生成回８３１
から正規化回路網３４に図示しないが直接加わる。

ヒストグラム生成回路ｙ４３１はＮｘＮのシストリック
アレイ構造を有しており、ヒストグラム生成回路綱３１
を通遇した画像データ（画像データに変化はない）はバ
ッファ（ＮＸＮ）３３に格納される。すなわち画像ＲＸ
が最終的にはバッファ３３に格納される。尚第２図にお
いては読み出し制御モジュール１５の出力は正規化回路
網１６にも加わるので、この場合にはこのバッファ３３
は必要ではなく正規化モジュール１６内に設けても良い
。

このヒストグラム生成回路網３１によって得られた緬方
向並びに横方向のヒストグラムは正規化回路モジュール
１６に加わり、このヒストグラムをもとに正規化モジュ
ール１６は動作する。尚正規化回路綱３４は横方向（列
単位）の正規化を行う回路である。縦方向（行単位）の
正規化はバノファ３３　（ＭｘＮ）からのデータ読み込
み用セル構造回路３５によるドット行単位の呼び出しに
よって正規化している。すなわち縦方向の正規化を行い
ながら横方向の正規化に必要な計算をし、この値と入力
データを正規化回路網３４に出力する。

データ読み込み用セル構造回路Ｎ４３５は縦方向を正規
化する回路であり、データ読み込み用セル回路綱３５と
正規化回路網３４の動作が始まる時刻をｔ＝１とするな
らば、縦方向の正規化を行うため、時刻もで正規化後の
図形のｔ行目に対応する行を読み込む。

Ｄ　−　ｈ２（ｉ’　−１）　＜　ｔ　Ｌ≦Ｄ−ｈ２（
ｉ”）　・・・４）が成り立つよう、入力画像の行ｉ゛
を時刻Ｌ７−読み取る。換言するならば、ヒストグラム
の値が４）式を満足するまで縦方向（行の読み出し順方
向）のヒストグラムと入力画像を読み込めば、縦方向の
正規化が行える。これは ｗｈｉｌｅ　（　ｔ　Ｌ　＞　Ｄ−ｈ２（ｉ’）　＆＆
　ｉ’＜Ｍ　）ｒｅａｄ　ｄａｔａ　＆＆　ｈｉｓｔｏ
ｇｒａｍ；なる処理をセルが行うことで実現できる。ま
た、横方向の正規化を行う時も３）式を満足する処理を
行えば良い。横方向のヒストグラムの値および横方向の
文字幅Ｗ呼び込みＪ列のセルではＤ−ｈｌ（ｊ−１）’
　，　　“ｊ　ＩＡ　’，　　’　Ｄ−ｈｌ（ｊ）を計
算し、さらに Ｄ　−１＋１（ｊ’）＜ｊ　’ｄ　　　ならば　ｊ−＋
ｊ−１ｊ　Ｗ　≦Ｄ−ｈｌ（ｊ’−１）　　ならば　ｊ
　−＋　ｊ　−１−　１と変換していくことで行う。尚
ｊは正規化の図形における列、ｊ”は入力図形のおける
列を表している。

このような正規化回路網３４の動作、ならびにデータ読
み込み用セル回路綱３５の動作により、横方向と縦方向
の正規化がなされ、得られる図形はＤＸＤの正規化され
た図形になる。

前述の正規化を行うためには入力文字のヒストグラムを
必要とする。以下ではこのヒストグラム生成についてさ
らに詳細に説明する。

第６図は本発明の実施例のヒストグラム生成回路網図で
ある。各セルＨ（１．１）〜Ｈ　（Ｎ，Ｎ）はヒストグ
ラム計算セルあるいはシフトレジスタより成る。第４図
に示した如＜ＭＸＭの入力データＲＸがヒストグラム計
算セルＨ（Ｎ，ｌ）とシフトレジスタＨ（Ｎ，２）〜Ｈ
　（Ｎ，Ｎ）に１行ドット単位で加わる。そしてそのヒ
ストグラム計算セルＨ（Ｎ，１）の出力はシフトレジス
タＨ（Ｎ−１．１）にまたシフトレジスタＨ（Ｎ，２）
の出力はヒストグラム計算セルＨ　（Ｎ−１．２）に加
わる。さらにシフトレジスタＨ（Ｎ，３）〜Ｈ　（Ｎ，
Ｎ）の出力はシフトレジスタＨ（Ｎ−１．３）〜Ｈ　（
Ｎ−１，Ｎ）に加わる。すなわち、第１番目においては
行の左端にヒストグラム計算セルを、次の段においては
２番目のドット位置、また３段目においては３ドット目
の位置に順次ヒストグラム計算セルを設け、それぞれ１
番目から２番目、３番目へとそのデータを出力する構造
としている。さらに換言するならばシフトレジスタをそ
れぞれドット対応でセルＨ（Ｎ，ｌ）から順次セルＨ（
１．１）までをシフトレジスタで構成し、その時セルＨ
（Ｎ，１）をヒストグラム計算セルとし、２番目におい
ては２番目のセルＨ（Ｎ−１．２）をヒストグラム計算
セルとし、３番目は同様に３個目の位置に、そして順々
に最終的にはセルＨ　（１．Ｎ）にヒストグラム計算セ
ルを設けそれぞれのドット位置単位で左から次のヒスト
グラム計算セルの位置に結果を出力する構造としている
。

このそれぞれのヒストグラム計算セル並びにシフトレジ
スタは１クロツタに対応してデータを次の段のシフトレ
ジスタやヒストグラム計算セルに出力する。尚シフトレ
ジスタは送られてきたデータを１クロンクを遅延するも
のである。

以下ではさらに詳細に動作を説明する。ヒストグラム生
成回路網の動作の始まる時刻ｔをｔ＝１とし、１クロッ
クごとにｔが１づつ増えていくものとするならば、時刻
ｔでの各セルでの動作は次のようになる。

■　ｔ≦Ｍのとき、セル（Ｎ，１）〜セル（ＮＮ）は入
力データのｔ行目を読み込む。Ｍ＜ｔのとき，セル（Ｎ
，１）〜セル（Ｎ．Ｎ）はＯを読み込む。

■　ヒストグラム計算セル（ｉ，Ｎ−ｉ＋１）はセル（
ｉ＋１，Ｎ　　ｉ）から送られてきた演算結果とセル（
ｉ＋１，Ｎ−ｉ＋１）から送られてきたデータを用い、
後述のセルの動作に従って処理を行う。

■　ヒストグラム計算セル（ｉ，Ｎ−ｉ＋１）は、演算
結果をセル（ｉ−１，Ｎ−ｉ＋２）に送る。

マタ、１〜Ｎ−１行のすべてのセルｃｉ，ｊ）は、セノ
レ（ｉ＋１，ｊ）から送られてきたデータをそのままセ
ル（ｉ−１，ｊ）に送る。

但し、Ｎ≦ものときセル（１，Ｎ）の演算結果は入力デ
ータの横方向のヒストグラム（（Ｎ−ｔ＋１）行目）の
イ直（ｘｗｉｄｔｈ　，　ｘｃｏｕｎｔ）となるから、
（ＭＸＩ）のバッファ３２に格納していく。また、セル
（１．ｊ）（０≦ｊ≦１）のデータ（ｙｗｉｄｔｈ，ｙ
ｃｏυｎｔ）は（ＭＸＮ）のバノファに送られる。

以上の動作はＭ＋Ｎ−１クロシクで全て完了し、Ｊ行目
のヒストグラム計算セルに入力データのＪ行目（横方向
）のヒストグラムの値が格納され、（ＭＸＩ）のバッフ
ァのＩ行目に入力データの１行目（樅方向）のヒストグ
ラムの値が格納されることになる。

セルを第６図のように配置すれば、たとえば入力図形の
Ｉ行目のデータがセル（Ｎ，１）で処理され、時刻（＋
＋１）で処理結果とその２行目のデータがセル（Ｎ−１
．２）で処理されるという具合に同じ行のデータが順に
出会っていくので縦方向と横方向のヒストグラムが同時
に作れる。尚セルを第６図のように配置するかわりに１
次限に配置されたヒストグラム計算セルを用い、図７に
示すようにデータを１クロックづつ別単位で遅延させて
入力してもよい。前述では横方向、縦方向の動作につい
て説明したが以下では前述のヒストグラム計算セルの動
作についてさらに詳細に説明する。

先ず線形の場合のヒストグラム計算セルの横方向のヒス
トグラムについて説明する。横方向のヒストグラムは、
前述したように、画像データ上で文字の領域に含まれる
最も左の点が属する列の値を１とし、それより右の列は
１づつ値を増やしていくことで得られる。従って、入力
画像のある列を走査したとき、もしその列に黒画像が含
まれていて、しかもその列より左の列には黒画像が含ま
れていないとき、その列のヒストグラムの値を１とし、
その列より右の列は、ヒストグラムの値を１ずつ増やす
。ｊ列目のセルはまず（ｊ−１）列Ｈのセルの値を判別
し、それが１以上であればその値に１を加えたものを自
分のセルの値とする。

もし（ｊ−１）列目のセルの値がＯであれば、ｊ列目に
黒画素があるか否か調べ、あればセルの値を１にし、な
ければセルの値を０にする。各セルに前述の処理を設け
、入力画像に対し１行目から順に処理すれば、最終的に
横方向のヒストグラムが得られる。

また、文字の幅は、入力画像データ上の最も右の黒画素
の存在する列のヒストグラムの値に等しく、これを求め
ればよい。

なお、縦方向のヒストグラムも、全く同様の考え方で得
ることができる。但し、横方向のときに空間的に分布さ
せていた機能を時間的に配置することになる。

第８図は線形におけるヒストグラム計算セルの詳細な構
成図である。ｆｌａｇは黒画素があったかどうかを判定
するフラグであり、ｃｏｕｎｔはヒストグラムの値を格
納し、ｉｖｉｄｔｈは文字幅の値を格納する。　゛Ｘ゛
ｙ゜は縦方向か横方向かを表している。また、ｙｆｌａ
ｇ，ｘｉｕｉｄｔｈ，ｘｃｏｕｎｔは、左の列のセルの
値を用いて処理して結果を右のセルに送り、ｙｗｉｄｔ
ｈ，ｙｃｏｕｎｔ，ｘｆａｌｇは自分のセルの値を用い
て処理して結果を自分のセルに格納する．そしてｘｆｌ
ａｇ，ｘｃｏｕｎｔ，ｘｉ＋＋ｉｄｔｈ並びにｙｆｌａ
ｇ，ｙｃｏｕｎｔ，ｙｗｉ６ｔｈはそれぞれ以下の式に
よって決定される。

横方向 ｘｆｌａｇ　＝　ｉｆ　ｄａｔａ　＝＝１　ｔＪ＋ｅｎ
　１ｅｌｓｅ　ｘｆｌａｇ ｘｃｏｕｎｔ　＝　ｉｆ　ｘｃｏｕｎｔ＞Ｏ　ｔｈｅｎ
　ｘｃｏｕｎｔ＋１ｅｌｓｅ　ｉｆ　ｘｆｌａｇ＝＝１
　ｏｒ　ｄａｔａ＝＝１　ｔｈｅｎ　１ｅｌｓｅ　ｘｃ
ｏｕｎｔ ｘｗｉｄｔｈ　＝　ｉｆ　ｘｆｌａｇ＝＝１　ｏｒ　ｄ
ａｔａ＝＝１　ｔｈｅｎ　ｘｃｏｕｎｔ＋１ｅｌｓｅ　
ｘｗｉｄｔｈ 縦方向 ｙｆｌａｇ　二ｉｆ　ｄａｔａ＝＝１　ｔｈｅｎ　１ｅ
ｌｓｅ　ｙｆｌａｇ ｉｆ　ｙｃｏｕｎｔ＞Ｏ　ｔｈｅｎ　ｙｃｏｕｎｔ＋１
ｅｌｓｅ　ｉｆ　ｙｆｌａｇ＝＝１　ｏｒ　ｄａｔａ＝
＝１　ｔｈｅｎ　１ｅｌｓｅ　ｙｃｏｕｎｔ ｙｗｉｄｔｈ　＝　ｉｆ　ｙｆｌａｇ＝＝ｌ　ｏｒ　ｄ
ａｔａ＝＝ｌ　ｔｈｅｎ　ｙｃｏｕｎｔ＋１ｙｃｏｕｎ
ｔ ｅｌｓｅ　ｙｗｉｄｔｈ このようなセルを用いて処理を行うと、最終的に、横方
向のヒストグラムは各セル内のｘｃｏｕｎｔに、横方向
の文字幅はセル（１，Ｎ）のｘｗｉｄｔｈに、紺方向の
文字幅はセル（１，Ｎ）のｙｗｉｄｔｈに格納され、縦
方向のヒストグラムは、時刻Ｎ以降セル（１，Ｎ）のｙ
ｃｏｕｎｔとして順に出力されることになる。

次に非線形の場合のヒストグラム計算セルの横方向のヒ
ストグラムについて説明する。非線形の場合は、各列ご
とに、黒画素を横切る回数を数え、それを積算していく
。従って、ｊ列目のセルは、ｊ列内で黒画素を横切った
回数を計算し、その値を積算する。

第９図は非線形におけるヒストグラム計算セルの詳細な
構成図である。ｆｌａｇは黒画素を横切っている途中で
あるかどうかを判定するフラグであり、ｃｏｕｎｔはヒ
ストグラムの値を格納する。ｓｔａｃｋはその行でヒス
トグラムに加算された値の積算値を格納する。　’ｘ”
ｙ’　は縦方向か横方向かを表している。また、ｙｆａ
ｌｇ，ｙｃｏｕｎｔ，ｘｓｔａｃｋは、左の列（７）　
セル（７）　｛ｉ　ヲ用いて処理して結果を右のセルに
送り、ｙｓｔａｃｋ，ｘｃｏｕｎｔ，ｘｆｌａｇは自分
のセルの値を用いて処理して結果を自分のセルに格納す
る。

そして、ｘｆｌａｇ，ｘｃｏｕｎｔ，ｘｓｔａｃｋ，並
びにｙｆｌａｇ，ｙｃｏｕｎｔ，ｙｓｔａｃｋはそれぞ
れ以下の式によって決定される。

横方向 ｘｆｌａｇ　＝ ｉｆ　　ｄａｔａ＝＝ｏ　　ｔｈｅｎ　　Ｏｅｌｓｅ　
　１ ＝　ｉｆ　ｄａｔａ＝＝１　ａｎｄ　ｘｆｌａｇ＝＝Ｏ
ｔｈｅｎ　　ｘｃｏｕｎｔ＋ｘｓｔａｃｋ＋］ｅｌｓｅ
　　ｘｃｏｕｎｔ＋ｘｓｔａｃｋｉｆ　ｄａｔａ＝＝ｌ
　ａｎｄ　ｘｆｌａｇ＝＝Ｑｅｌｓｅ　　ｘｓｔａｃｋ ｘｃｏｕｎｔ ｘｓｔａｃｋ ｔｈｅｎ ｘｓｔａｃｋ＋１ 縦方向 ｙｆｌａｇ ｙｃｏｕｎｔ ｉｆ　　ｄａｔａ＝＝ｏ　　ｔｈｅｎ　　Ｏｅｌｓｅ　
　１ ＝　　ｉｆ　ｄａｔａ＝＝１　ａｎｄ　ｙｆｌａｇ＝＝
０ｔｈｅｎ　ｙｃｏｕｎｔ＋ｙｓｔａｃｋ＋１ｅｌｓｅ
　ｙｃｏｕｎｔ＋ｙｓｔａｃｋ＋１ｙｓｔａｅｋ　＝　
ｉｆ　ｄａｔａ＝＝１　ａｎｄ　ｙｆｌａｇ＝＝Ｏ　ｔ
ｈｅｎ　ｙｓｔａｃｋ＋１ｅｌｓｅ　ｙｓｔａｃｋ このようなセルを用いて処理を行うと、最終的に、横方
向のヒストグラムは第１０図の例に示すごとく横方向の
文字幅はセル（１，Ｎ）のｘｃｏｕｎｔに、縦方向の文
字幅はセル（Ｌ　　Ｎ）のｙｃｏｕｎｔに格納され、縦
方向のヒストグラムは、時刻ＮＪ：Ｊ．ＩＩセル（１，
Ｎ）のｙｃｏｕｎｔとして順に出力されることになる。

以上のようにヒストグラム計算セルを構成することによ
り、線形、非線形のヒストグラムである変換表を得るこ
とができる。

第１１図は本発明の正規化回路網の構成図である。デー
タ読み込み用セル構造回路網３５（第４図参照）データ
読み込みセルＲ．Ｓ１〜ＲＳｎよりなり、ヒストグラム
生成回路網３１によってヒストグラムが求められてバッ
ファ３３に格納されたデータをドット行単位で読み込む
。本発明の実施例においては横方向はこの正規化回路網
３４によって正規化し縦方向は前述したデータ読み込み
用セル構造回路網３５で行っている。

データ読み込み用セル回路網３５は前述の樅方向の正規
化を行いながら横方向の正規化に必要な値を計算し、こ
の値と入力データを正規化回路網３４に渡す。

第１７図は正規化セルの構成図である。各セルには対応
するセル（前段のセル）からＴ２，Ｕ２，Ｌ２，Ｅ２が
加わる。また対応するセルの隣からはＵｌ．Ｌｌ．Ｅｌ
がその反対方向のセルからはＵ３，Ｌ３．Ｅ３が加わる
。各セルは各正規化セルＰ（１，ｊ）は前述の入力から
Ｐ，　　Ｕ，　　Ｌ，　　Ｅを求め次段の正規化セルに
加える。この正規化セルＰ（ｆ，ｊ）は第１２図に示す
それぞれの処理を行う。すなわち ｔ　＝　ｔ２ ｕ−ｉｆｆｆ２≧ｔ２　ｔｈｅｎ　ｕｌｅｌｓｅ　ｉｆ
　ｕ２　＜ｔ２　ｔｈｅｎ　ｕ３ｅｌｓｅ　ｕ２ ｆｆ＝ｉｆ２≧ｔ２ｔｈｅｎ　　ｆｌ ｅｌｓｅ　　ｉｆ　ｕ２　　＜ｔ２　ｔｈｅｎ　　Ｉ！
３ｅｌｓｅ　　１２ ｅ＝ｉｆｆ２　　≧　ｔ２　ｔｈｅｎ　　ｅｌｅｌｓｅ
　　ｉｆ　　ｕ２　　＜　　ｔ２　　ｔｈｅｎ　ｅ３ｅ
ｌｓｅ　ｃ２ なる処理を行う。この得られた結果ｔ，ｕ，１ｅを次の
セルＰ（１−１，ｊ）へ出力する。尚この結果はそれぞ
れ隣のセルにも出力する。換言するならばセルＰ　（１
−１，　　ｊ−１）、Ｐ　（１−１，ｊ＋１）へ出力す
る。

以上の動作により正規化回路綱３４の処理によって横方
向の正規化を行うことができる。前述した正規化回路綱
ＮＸＤの横方向の段数は第４図に示す左並びに右方向の
拡大数によって段数を求めればよい。換言するならば左
や右のブランク（入力データ）の最大値とすればよい。

すなわち文字の入力のドット幅の最大値を入力等処理し
ておけばよい。

この処理によりＤＸＤの正規化された文字パターンを得
ることができる。

Ｃ発明の効果〕 以上述べたように、本発明によればシストリックアレイ
によってバイブラインでかつ並列に正規化処理を的確に
高速に行うことができる。また、文字等の認識処理に用
いることにより、文字の認識率の向上を計るとともに、
高速に行うことが可能となる。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明の実施例のシステム構成図、第３図は拡
大の原理説明図、 第４図は本発明の実施例の詳細な構成図、第５図は縦一
横方向のヒストグラム図、第６図は本発明の実施例のヒ
ストグラム生成回路網図、 第７図はデータの流れの説明図、 第８図はヒストグラム計算セルの詳細な構成図、第９図
はヒストグラム計算セル（非線形）、第１０図は横方向
のヒストグラム（非線形）図、第１１図は正規化回路網
の構成図、 第１２図は正規化セルの構成図である。 Ｐ（１．１）〜Ｐ　（ｑ，ｎ） ・・・正規化セル，

Claims (1)

1. 【特許請求の範囲】 １）対応するセルと、該セルと隣合う２個のセルとより
   情報が加わり、正規化値と変換値との積が最大幅と該セ
   ル位置との積より小さい時に対応するセルの隣のセルの
   データを取り込み、正規化値と変換値との積が最大幅と
   該セル位置のセル以上の時前記隣のセルに対向する隣の
   セルのデータを取り込むセル（Ｐ（１、１）〜Ｐ（ｑ、
   ｎ））を複数個複数段に渡って設けてなることを特徴と
   するシストリックアレイによる正規化方式。 ２）前記情報は文字のドットであり前記最大幅とは入力
   文字が１個の文字の領域に存在する最大値であることを
   特徴とする請求項１記載のシストリックアレイによる正
   規化方式。３）前記シストリックアレイの入力は行単位
   であり、列方向に対して正規化後の図形に対応する行を
   順次読み取ることを特徴とする請求項１記載のシストリ
   ックアレイによる正規化方式。 ４）前記読み取りは現在の読み取り行数と入力文字の最
   大項との積が正規化値とヒストグラムとの積より大とな
   るまで同一行を読み取ることを特徴とする請求項３記載
   のシストリックアレイによる正規化方式。