JPH0740306B2 - パターンの輪郭トレース制御回路 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はパターンの輪郭トレース制御回路に関する。

〔従来の技術〕

従来のパターンの輪郭トレース制御回路はパターンメモ
リに記憶されたパターンの輪郭トレースにおいて、パタ
ーンメモリのスキャンの開始アドレス、終了アドレスは
ハードウェアの構成時に一意的に決められ、パターンメ
モリ全体をスキャンするように構成されていた。

又、パターンメモリのスキャンによりブロック（パター
ンの外側輪郭）又はループ（中空部を有するパターンの
内側輪郭）を検出すると自動的にパターンの輪郭トレー
スを開始していた。

パターンの輪郭トレースにおけるパターンメモリのアド
レスデータは遂次、トレースメモリに記憶され、パター
ンの輪郭トレース後にトレースメモリに記憶されたアド
レスデータは外部へ読み出され、パターン認識等の処理
が行われていた。

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

上述した従来のパターンの輪郭トレース制御回路は、パ
ターンメモリのスキャンの開始アドレス、終了アドレス
が一意的であり、パターンによっては当然パターンが存
在しないと判明しているパターンメモリのメモリ空間を
もスキャンしていたため不必要な処理時間を費やしてい
る。特にサイズの小さいパターンにおいてはこの不必要
となるべき処理時間が大きい。

又、形状の複雑なパターンの場合、一つの輪郭トレース
が終了し、次のブロック又はループを検出するために再
度スキャンする時もパターンメモリの最初からスタート
していたため、すでにスキャンを行なっており、既にト
レースしたもの以外にブロック又はループは存在しない
と判明しているにもかかわらず、再度同じメモリ空間を
スキャンしていたため、不必要な時間を費やしていた。

又、メモリスキャン中にブロック又はループを検出する
と自動的にトレースを開始し、トレースメモリを読み出
し状態から書込み状態に自動的に変更していた。そのた
め、いつ書込み状態に変化するかわからないトレースメ
モリをアクセスすることが出来ないため、パターンメモ
リのスキャン中に外部からトレースメモリをアクセスし
て処理を行なう等のことが不可能であった。したがって
パターンメモリのスキャンと他のパターン認識処理がシ
リアル処理になるため効率が悪く、結果的にはパターン
処理時間遅延の原因となっていた。

本発明は、パターンの大小、形状により不必要なメモリ
スキャンを省略し、高速なパターンの輪郭トレースを可
能としたパターンの輪郭トレース制御回路を提供するこ
とを目的としている。

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

上記問題点を解決するために、本発明のパターンの輪郭
トレース制御回路は、パターンを記憶するパターンメモ
リと、このパターンメモリのアドレスをＸ座標およびＹ
座標の組合せとして指定するアップダウンカウンタから
なるアドレスレジスタと、このアドレスレジスタにカウ
ンタ＋１信号を送って前記パターンメモリをＸ軸方向に
スキャンし前記アドレスレジスタの内容が予め定めた値
になったときは前記カウンタ＋１信号の送出を停止して
前記パターンメモリのスキャンを終了するスキャン制御
部と、前記パターンメモリのスキャンにより前記パター
ンのブロックまたはループを検出したときにブロックル
ープ検出信号を出力して前記スキャン制御部に前記カウ
ンタ＋１信号の送出を停止させ前記パターンメモリのス
キャンを停止させるブロックループ検出部と、前記ブロ
ックループ検出信号が出力されると外部から送出される
トレース自動スタート信号がアクティブであれば前記パ
ターンメモリからの情報を受けて前記アドレスレジスタ
に信号を送り前記パターンの輪郭トレースを行い、か
つ、輪郭トレースが行われた前記アドレスに輪郭トレー
ス済であることを示すフラグをたて、この輪郭トレース
が一巡すると、前記アドレスレジスタの内容のうちＸ座
標のみをリセットした後、前記スキャン制御部に前記カ
ウンタ＋１信号の送出を再開させて前記パターンメモリ
のスキャンを再開させ、また、前記トレース自動スター
ト信号がアクティブでなければ前記輪郭トレースを行わ
ないトレース制御部と、前記輪郭トレース中のトレース
の情報を記憶するとともに、前記トレース自動スタート
信号がアクティブでない場合には外部からのアクセスが
可能であるトレースメモリとを備える。

〔実施例〕

以下、本発明について図面を参照して説明する。

第１図は本発明の一実施例のブロック図である。第２図
〜第４図はそれぞれ第１図に示すブロックループ検出部
３、スキャン制御部５およびトレース制御部４の詳細な
ブロック図である。

第５図はパターンメモリ２およびパターンメモリ２に記
憶されたパターン20を一例として示す概念図である。パ
ターンメモリ２内は（Ｘ座標値、Ｙ座標値）からなる座
標（0,0），（1,0），…（8,c），（9,c）で表わされ、
パターンメモリ２には座標（0,0），（1,0），…（8,
c），（9,c）をアドレスとしてデータの書込み、読み出
しが行われる。

第６図はパターン20の輪郭トレースがすべて終了したと
きの、パターンメモリ２に書き込まれたブロックフラグ
ＢとループフラグＬを示す概念図であり、パターンメモ
リ２のパターン20の外側の輪郭に沿った座標にブロック
フラグＢが書き込まれ、パターン20の内側に沿ってルー
プフラグＬが書き込まれた状態を示す。

第７図はパターン20の輪郭トレースにおけるパターンメ
モリ２内のスキャンおよびトレースの動作を示す概念図
である。まず第７図に示すようにパターンメモリ２の座
標の各行を左から右に向けてＸ座標方向に上の行から下
の行へ向けてＹ座標方向に順次パターンメモリ２のスキ
ャンを行う。すなわち、座標（0,0）でスキャンをスタ
ートし、座標（0,0），（1,0）…（9,0），（0,1）…
（1,1）とスキャンを実行する。この順で座標（2,2）を
スキャンするとパターンデータが白→黒に変化する。パ
ターンデータが白→黒に変化した時点でブロックと見な
し、パターンメモリ２の１回目のスキャンを中止し、ブ
ロックトレースを開始する。このブロックトレースは座
標（2,2），（2,3）…（3,2），（2,2）という順でパタ
ーン２の外側を左回りに一巡して終了する。ブロックト
レースを行いながらパターンメモリ２の各座標には、第
６図に示すようにブロックフラグＢを書込んでいく。

ブロックトレースの終了後、パターンメモリ２の２回目
のスキャンを開始する。この時にパターンメモリ２のＹ
座標は、ブロックトレースを終了した時の値を保持し、
Ｘ座標のみはクリアし、座標（0,2）からスタートし、
座標（0,2）（1,2）（2,2）の順でスキャンを行ってい
く。座標（2,2）でパターン２は白→黒に変化するが座
標（2,2）にはブロックフラグＢが既に書込まれている
ため、スキャンをつづける。座標（3,5）から（4,5）に
なった時点でパターン２は黒→白に変化し、ループを検
出したものとみなし、パターンメモリの２回目のスキャ
ンを中止し、ループトレースを開始する。ループトレー
スは座標（4,4），（5,4）…（3,5）（3,4）（4,4）と
いう順にパターン２の内側を右回りに一巡して終了す
る。ループトレースを行いながらパターンメモリ２には
ループフラグＬを書込んでいく。

ループトレースの終了後３回目のスキャンをＸ座標のみ
をクリアし座標（0,4）からスタートし座標（0,4）（1,
4）…（8,c）（9,c）の順でスキャンを行っていき、座
標（9,c）でスキャンエンドとなりパターンメモリ２内
のパターン20の全てのブロック、ループのトレースを終
了する。

第１図において、２ケのアドレスレジスタ1a,1bはによ
り、パターンメモリ２にX,Y座標アドレスを供給する。
アドレスレジスタ1a,1bアップダウンカウンタで構成さ
れている。パターンメモリ２から出力されるパターンデ
ータ21はブロックループ検出部３及びトレース制御部４
に供給される。ブロックループ検出部３より発生するブ
ロック、ループ検出信号９はスキャン制御部５にはイン
バータ14を介してスキャンストップ信号９′となり、ト
レース制御部４にはトレーススタート信号９″となる。
外部からのスキャンスタート信号15はスキャン制御部５
に入力される。

第３図においてスキャンスタート信号15が入力されると
スキャン制御部５のフリップフロップ７がリセットさ
れ、フリップフロップ40がセットされ、クロック16とイ
ンバータ17を介したフリップフロップ７の出力およびフ
リップフロップ40の出力が入力されるアンド回路41から
カウンタ＋１信号が出力される。カウンタ＋１信号８は
オア回路18を介してアドレスレジスタ1bに供給され、内
容をカウトアップする。アドレスレジスタ1bはＸ座標方
向の座標数（第５図に示す例では10）をカウント数と
し、このカウント数までカウンタ＋１信号８を計数する
と桁上げ信号をアドレスレジスタ1aに送出する。

パターンメモリ２をスキャンしている時は、第２図に示
すようにパターンメモリ２の各アドレスからその座標に
パターンの有無（パターンが有る部分は黒、パターンが
無い部分は白とする）を示すパターン信号21aと、ルー
プフラグＬが書き込まれているか否かを示すループフラ
グ信号21bと、ブロックフラグが書き込まれているか否
かを示すブロックフラグ信号21cが読み出される。パタ
ーン信号21aはフリップフロップ22のリセット端子、Ｄ
フリップフロップ25およびインバータ26を介してフリッ
プフロップ23のリセット端子に入力される。Ｄフリップ
フロップ25の出力はフリップフロップ23のセット端子お
よびインバータ27を介してフリップフロップ22のセット
端子に入力される。アンド回路29にはフリップフロップ
22の出力およびＤフリップフロップ24とインバータ28を
介したループフラグ信号21bが入力される。アンド回路3
0にはフリップフロップ23の出力およびインバータ42を
介したブロックフラグ信号21cが入力される。アンド回
路29はパターンメモリ２のスキャン中にループを検出し
た場合（例えば第７図に示す座標（4,5））に論理値
“1"の出力を生じる。アンド回路30はブロックを検出し
た場合（例えば第７図に示す座標（2,2））に論理値
“1"の出力を生じる。オア回路31はアンド回路29,30の
出力を入力し、ブロックループ検出信号９を出力する。

第１図に示すスキャンスタート信号15が入力されると、
アドレスデータ32a,32bによりアドレスレジスタ1a,1bに
予め設定されたアドレス（第７図に示す例では座標（0,
0））から、パターンメモリ２のスキャンを開始する。
スキャン中にブロックループ検出部３がブロック又はル
ープを検出するとブロックループ検出信号９すなわち、
スキャンストップ信号９′及びトレーススタート信号
９″を出力する。スキャンストップ信号９′は、第３図
に示すようにフリップフロップ40（出力をアンド回路41
に入力）をリセットし、カウンタ＋１信号８の出力を禁
止する。

また、トレーススタート信号９″は第４図に示すフリッ
プフロップ11をトレース中にセットし、フリップフロッ
プ11の出力は制御ROM34をイネーブルにし、パターンメ
モリ２のパターンの輪郭トレースを開始する。ただし、
トレーススタート信号９″と外部から送信されるトレー
ス自動スタート信号12を入力するアンド回路35の出力を
クロック端子に接続し、トレースエンド信号36をクリア
端子に接続し、データ入力端子を定電圧に接続するフリ
ップフロップ13が制御ROM34に接続され、トレーススタ
ート信号９″が出力されてもトレース自動スタート信号
12がアクティブでないと制御ROM34はイネーブルにされ
ず、パターンの輪郭トレースは開始されない。

またスキャンストップ信号９′によりカウンタ＋１信号
８の出力が禁止されパターンメモリ２のスキャンも中止
されるのでトレース自動スタート信号12がアクティブで
ないと、アドレスレジスタ1a,1bの内容はブロック又は
ループの検出時の値に維持される。

このようにトレース及びスキャンが中止された後にトレ
ース自動スタート信号12をアクティブにすると制御ROM3
4がイネーブルにされアドレスレジスタ1a,1b内に維持さ
れていた座標からブロック又はループのトレースが開始
される。

制御ROM34はパターンメモリ２からのパターンデータ21
を入力情報として、パターンの輪郭トレースを続行する
ために次にアクセスすべきアドレスを作成するために、
パターンメモリ２のX,Yアドレスを＋１または−１する
Ｘ座標UP/DOWN信号13aおよびＹ座標UP/DOWN信号13bを出
力する。X,Y座標UP/DOWN信号13a,13bは第１図に示すよ
うにオア回路18を介してアドレスレジスタ1b,1aに入力
される。

また制御ROM34はパターンの輪郭トレースにブロック・
ループフラグ信号37をパターンメモリ２に送出し、パタ
ーンメモリ２の対応アドレスにブロックフラグＢまたは
ループフラグＬを書込む。またパターンの輪郭トレース
中のパターンメモリ２のアドレスデータはトレースメモ
リ６に記憶され、トレースメモリ６からトレース順序を
読み出してパターン認識処理等が行われる。

トレースがパターンの輪郭を一巡してトレース開始時の
パターンメモリ２の座標に戻った時に、アドレスレジス
タ1a,1bの内容がトレース開始時の値と等しくなったこ
とを検出して出力されるトレースエンド信号36（第４
図）がフリップフロップ11のリセット端子に入力され、
トレースエンド信号36の出力によりパターンの輪郭トレ
ースが終了する。またトレースエンド信号36は第３図に
示すスキャンスタート信号15と同様にフリップフロップ
７をリセットするとともにフリップフロップ40をセット
し、Ｘ座標クリア信号37によりアドレスレジスタ1bをク
リアするとともにアンド回路41からカウンタ＋１信号８
を出力させ、パターンメモリ２のスキャンを再開させ
る。なお、アドレスレジスタ1aはクリアされないため、
パターンの輪郭トレースが終了した時のＹ座標でＸ座標
が０の座標からスキャンが再開される。

パターンメモリ２のスキャンを続行し、アドレスレジス
タ1aから出力されるＹ座標がレジスタ38内に書き込まれ
た設定値（第７図に示す例では座標（9,c）のアドレ
ス）と等しくなった時は、比較器39からの信号がフリッ
プフロップ７をセットし、スキャンエンド信号10を出力
し、この出力を入力するインバータ17の出力がカウンタ
＋１信号８の出力を禁止し、パターンメモリ２のスキャ
ンは終了となる。

本実施例によるパターンメモリ２のスキャンおよびパタ
ーンの輪郭トレースを第９図に示すパターン20′を一例
として説明する。また第８図は従来のパターンの輪郭ト
レース制御回路によるパターン20′の輪郭トレースを説
明する図である。

第８図および第９図において、記号〜はそれぞれパ
ターンメモリ２の１〜３回目のスキャンのスタートポイ
ントを示す。記号はスキャン終了ポイントを示す。第
８図をみるとわかる様に従来回路では、スキャンは３回
とも同じポイントからスタートし、パターンメモリ２の
終了ロケーションで終了している。

本発明では第９図に示すように最初のスタートは第８図
に示す従来回路によるものと同じポイントであるが2,3
回目のスキャンのスタートはパターンメモリ２の途中よ
りスタートでき、予め設定したＹ座標の位置でスキャン
を終了することが出来る。パターン処理において文字等
のパターンの高さがあらかじめ明白の場合は、処理時間
を大きく短縮することが出来る。

又、本実施例では第４図に示す自動スタート信号12をア
クティブにしないでパターンの輪郭トレースの開始を禁
止しておけば、スキャンによりブロック又はループが検
出されてもトレースが開始されず、トレースメモリがブ
ロックトレース等による割込みを受けることがないた
め、パターンメモリのスキャン中に並行して外部からト
レースメモリをアクセスして処理することが可能であ
る。

例えば第９図に示すパターン20′を例に説明すると、１
回目のスキャン時にはトレース自動スタート信号12をア
クティブにしておき、外側の輪郭のブロックトレース後
の２回目のスキャン時にはトレース自動スタート信号12
をアクティブにしないで、２回目のスキャン中に図示し
ないCPUがトレースメモリ６をアクセスしてトレースし
た外側の輪郭の情報を読み出し特徴抽出等の解析を行
い、この読み出しが終了した時にトレース自動スタート
信号12をアクティブにし、さらにパターン20′のループ
を検出した時（トレースメモリ６からの外側の輪郭の情
報の読み出し終了時が、既にパターン20′のループ検出
の後ならばトレースメモリ６の読み出しを終了してトレ
ース自動スタート信号12をアクティブにした時）にパタ
ーン20′の内側の輪郭のトレースを開始する。その後の
３回目のスキャン時にトレース自動スタート信号12をア
クティブにしないで、パターンメモリ２のスキャンとト
レースメモリ６からの内側の輪郭の情報の読み出しを並
行して行う。

このようにトレース自動スタート信号12をアクティブに
しないでパターンの輪郭トレースの開始を禁止しておけ
ば、パターンメモリ２の2,3回目のスキャンのスタート
を行いパターンメモリ２のスキャンと並行して、CPUが
トレースメモリ６を読み出し、１回目,2回目の輪郭トレ
ースの結果の解析を行なうことが出来る。特にOCR等で
認識されるパターンは多くの場合、数字、アルファベッ
トおよびカナ文字であり、これらのパターンは１回また
は２回のスキャンだけで実際に有効なスキャン（ブロッ
クまたはループを検出するスキャン）が終了してしまう
ことがほとんどである。このような場合に、３回目のス
キャン（ブロックまたはループを検出しないスキャン）
が終了するまで、多くの処理時間がかかるトレースメモ
リ６のデータの解析を開始できないのでは、パターン認
識全体の処理効率を非常に低下させることになる。しか
し、スキャンとCPUによるトレースメモリ６のデータの
解析とを並行して行うことで、スキャンが終了してから
CPUによるトレースメモリ６のデータの解析を開始する
場合と比べて、処理時間を大幅に短縮できる。

なお、複数文字を続けて読む場合には、トレース自動ス
タート信号12により、ある文字（又は文字の一部）の輪
郭の情報をトレースメモリ６から読み出すのと、次の文
字のスキャンを並列に行うこともできる。例えば上述の
図９に示すパターン20′の説明では、１回目のスキャン
時にトレース自動スタート信号12をアクティブにしてお
いたが、図９に示すパターン20′が前の文字パターンの
処理の後の処理であるならば、パターン20′の１回目の
スキャン時にもトレース自動スタート信号12をアクティ
ブにしておかないでトレースメモリ６からの前の文字の
輪郭の情報読出しと並行してパターン20′の１回目のス
キャンを行うことができる。

次にパターン20′のスキャン・トレースの処理時間の算
出を行なう。なお、l₁,l₂はそれぞれパターン20′の外
側の輪郭をトレースするに要する時間および内側の輪郭
をトレースするに要する時間、Ｘはパターンメモリ２を
Ｘ方向に１回だけスキャンする時間、X₁,X₂はそれぞれ
パターンメモリ２の左辺からパターン20′の外側の輪郭
の最上点までスキャンする時間および左辺からパターン
20′の内側の輪郭の最上点までスキャンする時間、Ｈは
パターンメモリ２の縦の辺のＹ座標上の大きさ、H₁〜H₃
はそれぞれパターンメモリ２のＹ座標上の上辺からパタ
ーン20′の最上点までの大きさ、上辺からパターン20′
の内側の輪郭の最上点までの大きさおよび上辺からパタ
ーン20′の最下点までの大きさである。

スキャン・トレースの処理時間は従来のパターンの輪郭
トレース制御回路では（H₁＋H₂＋Ｈ）×Ｘ＋（X₁＋X₂＋
l₁＋l₂）となるが本実施例ではH₃X＋（X₁＋X₂＋l₁＋
l₂）となる。X₁＋X₂＋l₁＋l₂が固定項であるから（H₁＋
H₂＋Ｈ）−H₃の処理時間差が発生する。仮にH₁＝1,H₂＝
20,H₃＝30,H＝40とすると実施例は従来回路の約1/2の処
理時間となり、処理時間の短縮に極めて効果的である。

〔発明の効果〕

以上説明したように本発明は、パターンメモリ内の輪郭
のトレースの開始の可否をトレース自動スタート信号で
制御することにより、パターンメモリのスキャンとトレ
ースメモリの読み出しの並行処理を可能とし、パターン
処理時間を短縮できる効果がある。

またパターンの輪郭トレース後にパターンメモリのスキ
ャンを再開する際に、従来のパターンの輪郭トレース制
御回路のようにパターンメモリの端の座標からスキャン
を再開せず、輪郭トレース前にスキャンを停止した座標
とほぼ同じ座標から再開するようにできるため、パター
ンが複雑（ブロック、ループ数が大きくなる。）になれ
ばなるほどさらに処理時間短縮の効果は大きくなる。又
パターンが小さくなるとさらにこの効果は大きくなる。

【図面の簡単な説明】

第１図は本発明の一実施例のブロック図、第２図〜第４
図はそれぞれ第１図に示すブロック・ループ検出部３の
詳細ブロック図、スキャン制御部５の詳細ブロック図お
よびトレース制御部４の詳細ブロック図、第５図〜第７
図はそれぞれ第１図に示すパターンメモリ２に記憶され
たパターン20の概念図、輪郭トレース終了時のフラグの
状態を示す概念図およびスキャンおよび輪郭トレースの
動作を説明するための概念図、第８図は従来のパターン
の輪郭トレース制御回路のパターン20′の輪郭トレース
の概念図、第９図は第１図に示す実施例によるパターン
20′の輪郭トレースの概念図である。 1a,1b……アドレスレジスタ、２……パターンメモリ、
３……ブロックループ検出部、４……トレース制御部、
５……スキャン制御部、６……トレースメモリ、20,2
0′……パターン。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭57−101987（ＪＰ，Ａ) 特開 昭61−40684（ＪＰ，Ａ) 特開 昭60−173682（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】パターンを記憶するパターンメモリと、 このパターンメモリのアドレスをＸ座標およびＹ座標の
   組合せとして指定するアップダウンカウンタからなるア
   ドレスレジスタと、 このアドレスレジスタにカウンタ＋１信号を送って前記
   パターンメモリをＸ軸方向にスキャンし前記アドレスレ
   ジスタの内容が予め定めた値になったときは前記カウン
   タ＋１信号の送出を停止して前記パターンメモリのスキ
   ャンを終了するスキャン制御部と、 前記パターンメモリのスキャンにより前記パターンのブ
   ロックまたはループを検出したときにブロックループ検
   出信号を出力して前記スキャン制御部に前記カウンタ＋
   １信号の送出を停止させ前記パターンメモリのスキャン
   を停止させるブロックループ検出部と、 前記ブロックループ検出信号が出力されると外部から送
   出されるトレース自動スタート信号がアクティブであれ
   ば前記パターンメモリからの情報を受けて前記アドレス
   レジスタに信号を送り前記パターンの輪郭トレースを行
   い、かつ、輪郭トレースが行われた前記アドレスに輪郭
   トレース済であることを示すフラグをたて、この輪郭ト
   レースが一巡すると、前記アドレスレジスタの内容のう
   ちＸ座標のみをリセットした後、前記スキャン制御部に
   前記カウンタ＋１信号の送出を再開させて前記パターン
   メモリのスキャンを再開させ、また、前記トレース自動
   スタート信号がアクティブでなければ前記輪郭トレース
   を行わないトレース制御部と、 前記輪郭トレース中のトレースの情報を記憶するととも
   に、前記トレース自動スタート信号がアクティブでない
   場合には外部からのアクセスが可能であるトレースメモ
   リと を含むことを特徴とするパターンの輪郭トレース制御回
   路。