JPH03214283A - シストリックアレイによる変換表作成回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　　　要〕 切り出した１文字のパターンをシストリックアレイ構造
によって正規化のための変換表を作成するシストリック
アレイにおける変換表作成回路に関し、 切り出した文字データを正規化するためのヒストグラム
情報をパイプライン処理でかつ並列に行いパターン認識
を高速化するシストリノルアレイによる変換表作成回路
を提供することを目的とし、Ｎ個のセルを直列接続した
直列回路をＮ列設け、第ｍ列目の入力側からｍ番目のセ
ルは、入力データをシフトして出力するとともに、前記
入力データと第ｍ−１列目のｍ−１列目のセルよりプ川
わる幅データとカウントデータとから幅データトカウン
トデータとを更新してｍ＋１列目の入力側からｍ＋１番
目のセルに出力するヒストグラム計算セルであり、該ヒ
ストグラム計算セル以外のセルはシフトレシスタである
ように構成する。

〔産業上の利用分野〕

本発明はパターン認識装置に係り、更に詳しくは切り出
した１文字のパターンをシストリツクアレイ構造によっ
て正規化のための変換表を作成するシストリックアレイ
における変換表作成回路に関する。

（従　来　の　技　術〕 コンピュータシステムの発展により、画像データを取り
込むとともに、取り込んだ画像データから文字を切り出
し、読み取った書類の文章のそれぞれの文字を認識する
読み取り装置が実用化している。この読み取り装置はた
とえばイメージスキャナ等によって読み取ったドットデ
ータをあらかじめ定められた領域単位で分割し、その分
割内での文字とあらかじめ定められた文字とを比較し、
１番似にかよった文字を結果として出力してい“る。

このあらかじめ定められたデータは一般的には辞書メモ
リに格納されており、たとえば各規定の文字を特徴化し
たデータとして記憶されている。そして認識すべき文字
が入力した時、同様にその入力した文字を特徴化し、前
述の辞書メモリに格納されているあらかじめ定められた
特徴データとの距離を求めている。この求めた距離から
最も小さい文字を認識結果として出力している。

前述のようなシステムにおいでは、切り出した１個の文
字を認識する場合、それらの文字があらかじめ決められ
た大きさとなっていると認識率が向上する。このため従
来においては切り出した文字単位で樅横方向にあらかじ
め決められた高さと、幅にしている。すなわち正規化し
ている。

この正規化の方式は種々あるが、その１方式として切り
出した文字の縦方向と横方向に対してヒストグラムを求
め、得られたヒストグラムから文字を拡大や縮小して正
規化する方式がある。

このような方式によって認識すべき文字が一定の大きさ
になるので、認識率が向上する。

［発明が解決しようとする課題］ 前述し，たヒストグラムを求める場合、従来においては
、切り出した領域をドット単位で読み出し、例えばそれ
以前に読み出した左右や上下のドノトが黒であるか白で
あるか等のフラグから次のドッＩ・への情報を求めて順
次処理している。このような従来の方式はドット単位で
処理してヒストグラムを求めているので、その処理に多
くの時間を必要とする問題を有していた。すなわち、認
識処理を行う時間が大となる問題を有していた。

本発明は切り出した文字データを正規化するためのヒス
トグラム情報をパイプライン処理でかつ並列に行いパタ
ーン認識を高速化するシストリノルアレイによる変換表
作成回路を提供することを目的とする。

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

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

Ｎ個のセルＨ（１．１）〜Ｈ（Ｎ，１）・・・Ｈ（１，
Ｎ）〜Ｈ（Ｎ，Ｎ）を直列接続した直列回路をＮ列設け
ている。

そのセルのうち第ｍ列目の入力側からｍ番目のセルはヒ
ストグラム計算セルであり、残りのセルはシフトレジス
タである。

ヒストグラム計算セルは入力データをシフトして次のセ
ルへ出力するとともに、このデータと隣の列の１つ前の
セルから加わる幅データとカウントデータとから幅デー
タとカウントデータとを更新して反対隣の列の１つ後の
セルに加える。

また、例えばヒストグラム計算セルは横方向のフラグレ
ジスタ、縦方向の幅レジスタやカウンタを有する。

［作　　用］ Ｎ個のドット（１ドット行）がＮ個の列に対応するドノ
ト位置単位で加わり順次シフトする。

ヒストグラム計算セルは１ドット行に対して斜め方向に
設けられているので、例えばシストリックアレイの下方
向（列の下方向）から１ドット行が加わった時には、第
１列目の入力側から１番目のヒストグラム計算セルが縦
方向と横方向のヒストグラム計算を行う。そして順次シ
ストリックアレイ中をデータがシフトするたびに次の行
と次の列（斜め右上方向にヒストグラム計算セルが設け
られている）のヒストグラム計算を行う。これを順次繰
り返すことにより、右上最終のヒストグラム計算セルか
ら順次カウント値や幅の結果が出力される。また各ヒス
トグラム計算セル内のレジスタやカウンタにしても対向
する方向のカウント値や幅データが残る。

シストリックアレイ中を１文字のデータが通過する時に
同時に縦方向や横方向のヒストグラムを高速に求めるこ
とができる。

［実　　施　　例］ 以下図面を用いて本発明を詳細に説明する。

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

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

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

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

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

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

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

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

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

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

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

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

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

変換表作成モジュールＩ７は正規化モジュール１６によ
って１文字を正規化するための変換デー夕を求めるモジ
ュールであり、たとえば読み出し制御モジュール１５に
よって切り出した１文字領域に対し、列方向並びに行方
向に投影し、黒ドノトが存在する列並びに行からドット
単位（行や列単位）で、列並びに行方向のカウンタをイ
ンクリメントし、１文字の領域内の最終値までの値を求
める。このモジュールの回路並びに動作については後述
する正規化の原理に基づき後に詳細に説明する。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

前述した第２図における本発明の実施例においては全体
のシステムから変換表作成モジュールについて説明した
。以下ではさらに詳細に変換表作成モジュールにおける
原理と詳細な回路について説明する。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

〔発明の効果〕

以上述べたように本発明によればヒストグラムヲハイブ
ライン構造で並列に処理するのでその変換処理を高速化
することができる。このヒストグラムを高速で求めるの
で、正規化処理を同時に高速化することができる。また
その結果、高速の文字等の認識装置を行うことができる
。

【図面の簡単な説明】

第１図は本発明の原理ブロソク図、 第２図は本発明の実施例の構成図、 第３図は拡大の原理説明図、 第４図は本発明の実施例の全体の構成図、第５図は縦方
向と横方向のヒストグラム図、第６図は本発明のヒスト
グラム計算回路網図、第７図はデータの流れ図、 第８図はヒストグラム計算セル（ｔｉＩ形）図、第９図
は横方向のヒストグラム（非線形）図、第１０図はヒス
トグラム計算セル（非線形）図である。 Ｈ（１．１）〜Ｈ（Ｎ　］） Ｈ（Ｎ、１）〜Ｈ（Ｎ，Ｎ）・・・・・セル、Ｈ（Ｎ，
１）．　Ｈ（Ｎ〜１，２）・・・Ｈ（１，Ｎ）・・・・
・ヒストグラム計算セル．

Claims (1)

1. 【特許請求の範囲】 １）Ｎ個のセル（Ｈ（１、１）〜Ｈ（Ｎ、１）・・・Ｈ
   （１、Ｎ）〜Ｈ（Ｎ、Ｎ））を直列接続した直列回路を
   Ｎ列設け、第ｍ列目の入力側からｍ番目のセルは、入力
   データをシフトして出力するとともに、前記入力データ
   と第ｍ−１列目のｍ−１列目のセルより加わる幅データ
   とカウントデータとから幅データとカウントデータとを
   更新してｍ＋１列目の入力側からｍ＋１番目のセルに出
   力するヒストグラム計算セルであり、 該ヒストグラム計算セル以外のセルはシフトレジスタで
   あることを特徴とするシストリックアレイによる変換表
   作成回路。 ２）前記ヒストグラム計算セルはフラグレジスタを有し
   、加わる入力データが１の時にフラグを１、０の時には
   現在のフラグの値を保持し、 カウント値が０より大の時に入力するカウントデータを
   インクリメントし、０でかつ前記フラグが１か入力する
   データが１の時にカウントデータを１とし、他の時にカ
   ウント値をそのままとして更新して出力し、 フラグが１かあるいは入力データが１の時カウントデー
   タに１加算して幅データとし他の時に同じ値として入力
   する幅データを出力することを特徴とする請求項１記載
   のシストリックアレイによる変換表作成回路。 ３）前記入力データは文字データであり、１文字領域の
   ドットが１ドット行単位で前記直列接続したＮ個の入力
   に加わり、 前記Ｎ列目の入力側からＮ番目のセルは横方向のヒスト
   グラムを出力することを特徴とする請求項１記載のシス
   トリックアレイによる変換表作成回路。 ４）Ｎ個のセル（Ｈ（１、１）〜Ｈ（Ｎ、１）・・・　
   Ｈ（１、Ｎ）〜Ｈ（Ｎ、Ｎ））を直列接続した直列回路
   をＮ列設け、第ｍ列目の入力側からｍ番目のセルは、入
   力データをシフトして出力するシフトレジスタと幅レジ
   スタとカウンタとを有し、入力データが１の時フラグデ
   ータを１とし、０の時はｍ−１列目の入力側からｍ−１
   段目のセルから加わるフラグデータを出力フラグデータ
   としてｍ＋１列目の入力側からｍ＋１番目のセルに出力
   し、カウンタの値が０より大の時カウンタを１歩進し、
   入力するフラグデータが１かあるいは入力データが１で
   ある時カウンタを１とし、他の時にはカウンタを変化さ
   せず、前記ｍ−１列目の入力側からｍ−１段目のセルか
   ら加わるフラグデータが１かあるいは入力データが１の
   時カウンタの値に１加算して幅レジスタに格納し、その
   他の時に幅レジスタの値を保持するヒストグラム計算セ
   ルであり、 他は入力データをシフトして出力するシフトレジスタで
   あることを特徴とするシストリックアレイによる変換表
   作成回路。 ５）前記入力データは文字データであり、１文字領域の
   ドットが１ドット行単位で前記直列接続したＮ個の入力
   に加わり、前記ヒストグラム計算セルは縦方向のヒスト
   グラムを前記幅レジスタとカウンタでそれぞれ求めるこ
   とを特徴とする請求項４記載のシストリッレアレイによ
   る変換表作成回路。