JPS6136879A - 輪郭追跡装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〈発明の技術分野〉 本発明は、文字、図形等の画像入力を白黒２値化して入
力パターンを求め、この入力パターンを標準パターンと
照合して、未知゛文字等を認識するパターン認識技術に
関連し、殊に本発明は、前記パターン照合の前処理段階
等において、入力パターンの輪郭を高速度で追跡する輪
郭追跡装置を提供するものである。

〈発明の背景〉 従来のこの種装置は、第１３図に示す如く、文字、図形
等をＣＣＤ　（Ｃｈａｒｇｅｄ−ＣｏｕｐｌｅｄＤｅｖ
ｉｃｅ）より成るカメラ５１にて画像化し、この画像入
力を２値化回路５２で白黒２１Ｉ化して入力パターンを
求め、この入力パターンを画像メモリ５３へ格納した後
、画像メモリ５３中の入力パターンにつき５輪郭追跡回
路５４を動作させて、輪郭線の追跡処理を実行している
。この輪郭追跡処理は、画像メモリ５３上に第１４図に
示すマスク５５を設定してこれを所定方向（図中、矢印
で示す）へ走査し、各画素につきその画素データＳおよ
びその周囲４方向近傍の画素データ５ｏ−ｍ　Ｓ３をチ
ェックし、そのデータ構成に基づき追跡開始点Ａを求め
た後、入力パターンの輪郭黒画素を所定方向へ順次追跡
してゆく。

第１５図は第１４図のパターン部分５６を拡大して示し
である。同図において、今輪郭黒素Ｂｏからつぎの輪郭
黒画素Ｂが追跡された段階を想定すると、つぎに続く輪
郭黒画素は、まず追跡方向に対し左手９０度に位置する
画素Ｂ６　　につきデータ内容がチェックされ、これに
続いて画素Ｂ５　＋　Ｂ４　＋　Ｂ３の順で次々にデー
タ内容がチェックされる。その結果、黒画素データ「１
」をもつ画素Ｂ３　　が検出されると、これをっぎの輪
郭黒画素と定め、更に同様の輪郭追跡処理を繰返し実行
するものである。従って上記の例においては、輪郭黒画
素Ｂ３　を検出するのに、合計４画素アクセスすること
が必要となる。

かくしてこの従来方式によれば、追跡開始点を検出する
のに、マスクの各走査位置毎に５画素アクセスし、更に
隣接する輪郭黒画素を検出するのに、平均４画素（最大
８画素、最小１画素）アクセスする必要かあり、輪郭追
跡の処理時間が著しく長くなり、これがパターン認識効
率を低下させる原因となっている、 〈発明の目的〉 本発明は、入力パターンの輪郭追跡を高速化する新規装
置を提供し、もって輪郭追跡処理時間の短縮、更にはパ
ターン認識効率の向上をはかることを目的とする。

〈発明の構成および効果〉 上記目的を達成するため、本発明では、文字、図形等の
画像入力を白黒２値化して入力パターンを求め、この入
力パターンの各構成画素につきその周囲８方向近傍の画
素データを求めた後、この画素データ構成に基づき入力
パターンの輪郭黒画素を検出すると共につぎの輪郭黒画
素位置までの縦横各方向の変位を求め、各輪郭黒画素に
対応して前記変位を順次格納して、第１図（３）に示す
ような複合連鎖記号化画像（図中、斜線部分が変位格納
画素を示す）を生成するようにした。

本発明によれば、画像入力と同時に入力パターンにおけ
る輪郭黒画素の検出並びに、つきの輪郭黒画素位置の縦
横各変位の検出が可能であると共に、複合連鎖記号化画
像における各変位をチェックするだけでつぎの輪郭黒画
素位置を簡単に把握できるようになった。従って輪郭黒
画素を追跡するのにその都度１回アクセスすれば足り、
従来方式に比較して、輪郭追跡の処理時間を大幅に短縮
でき、パターン認識の効率向上に貢献する等、発明目的
を達成した顕著な効果を奏する。

〈実施例の説明〉 第２図は、本発明にかかる輪郭追跡装置の全体概略構成
を示す。図中、ＣＯＤより成るカメラ１は、文字、図形
等を光学的に読み取って画像入力を得る。２値化回路２
は画像入力信号を所定のスレシュホールドレベルに基づ
き２値化し、白黒画画素より成る入力パターンを求める
。

第１図（１）は２値化された入力パターン（図中、斜線
部分が黒画素を示す）を２次元的に示したものであり、
この入力パターンは縦横各２５６ビツトの画素にて構成
されている。ノイズ除去回路３は、入力パターンに含ま
れるノイズ部分（第１図（１）中、符号ｎｌ　＋　ｎ２
て示す）を除去するための回路であり、その結果、第１
図（２）に示す如く、ノイズ除去（破線部）された滑ら
かな輪郭の入力パターンを得る。変位生成回路４は、現
輪郭黒画素からつぎの隣接する輪郭黒画素までの縦横各
方向の変位を生成するための回路であり、各輪郭黒画素
に対応してその変位を生成して、画像メモリ５に順次格
納してゆく。第１図（３）は、変位格納画素（図中、斜
線で示す）か連鎖的に連なって形成された複合連鎖記号
化画像（Ｈｉｂｒｉｄ　５ｅｑｕｅｎｃｅ　Ｍａｒｋｅ
ｄ　Ｉｍａｇｅ；以下「ｌ−ｌ５Ｍ画像」という）を示
している。上記の画像入力、２値化、ノイズ除去、変位
の生成、Ｉ（８Ｍ画像の形成の一連の処理はビデオ信号
レートで実行され、しかる後に、輪郭追跡部６が前記■
」８Ｍ画像を用いて、入力パターンの輪郭追跡処理を実
行ｒる。

第３図および第４図は、上記ノイズ除去回路３および変
位生成回路４の詳細を示している。

ノイズ除去回路３は、３段に直列接続された夫々２５６
ビツトのシフトレジスタ７．８．９と、各シフトレジス
タ７．８．９の所定３ビツトの画素データ（Ｎｔ、Ｎｚ
、Ｎ５）（Ｎｏ＋Ｎｓ、Ｎ４）（Ｎ７１Ｎ６１Ｎ５）に
よってアドレス指定されるノイズ除去テーブルが格納さ
れたテーブルメモリ１０とから構成されている。このノ
イズ除去テーブルは、中心画素データＮ８　　およびそ
の周囲８方向近傍の画素データＮｏ＝Ｎｔ　　（以下、
「周囲画素データ」という）が所定の合法パターンを形
成するか否か、或いはそれ以外のパターン（例えば違法
パターン）を形成するか否かを判別して、中心画素デー
タＮ８　　がノイズか否かを識別するためのものである
。そして中心画素データＮ８　　がノイズであるとき、
その黒画素データ「１」を消去すべくテーブルメモリ１
０より白画素データ「０」が出力される。尚前記の合法
パターンは、中心画素データＮ８　　が黒画素データ「
１」であり且つ３個の周囲画素データＮ。

＋　Ｎｌ　＋　”２　＋またはＮ２　ｒ　Ｎ３　＋　Ｎ
４　＋またはＮ４　＋　Ｎ５、Ｎ６．またはＮ６　＋　
Ｎ？　＋　Ｎ８が黒画素データ「１」である場合のパタ
ーン構成をいい、また違法パターンは、中心画素データ
Ｎ８が黒画素データ「１」であって、周囲画素データＮ
ｏ＃Ｎフが前記合法パターンにおけるデータ構成をとら
ない場合のパターン構成をいう。

第５図は上記ノイズ除去方法をフローチャートとして示
したものであり、まずステップ３１において、シフトレ
ジスタ７．８．９に入力パターンの３行に亘る構成画素
データがセットされ、つぎのステップ３２で各シフトレ
ジスタの所定ビットの画素データＮｏＮＮ３がテーブル
メモリ１０に入力される。そしてもし中心画素データＮ
８が白画素データ「０」のとき、ステップ３３が“ＮＯ
”であり、テーブルメモリ１０から白画素データ「０」
が出力される（ステップ３４）ｏ７一方中心画素データ
Ｎ８　　が黒画素データ「１」のとき、ステップ３３が
ＹＥＳ”となり、つぎのステップ３５において、中心画
素データＮ８およびその周囲画素データＮｏ、−ｍＮ、
が合法パターンを構成するか否かが判別される。その結
果、合法パターンであるとの判定（ステップ３６が”Ｙ
ＥＳ”）により、テーブルメモリ１０から黒画素データ
「１」が出力される（ステップ３７）。

一方ステップ３６の「合法パターンか」の判定が“ＮＯ
”　のとき、テーブルメモリ１０からノイズ除去用の白
画素データ「０」が出力される（ステップ３８）。かく
てステップ３８におけるテーブルメモリ１０の出力によ
って画素データが変換され、これにより入力パターンに
含まれるノイズの除去が実行される（ステップ３９）。

尚ステップ３１〜３９の処理フローは、シフトレジスタ
７．８．９のシフト動作と共に、入力パターンの全画素
データにつき実行される。

つぎに変位生成回路４は、上記ノイズ除去回路３と同様
の構成の３段のシフトレジスタ１１．１２．１３と、各
シフトレジスタ１１，１２．１３の所定３ビツトの画素
データ（Ｄｌ、Ｄ２゜Ｄｓ）　（Ｄｏｒ　ＤＢ、　Ｄ４
）　（Ｄ？＋　Ｄ６１　Ｄ５）によってアドレス指定さ
れる隣接変位生成テーブルが格納されたテーブルメモリ
１４とから構成されている。この隣接変位生成テーブル
は、中心画素データＤ８および周囲画素データＤｏ、Ｄ
、のパターン構成に応じて、第６図に示すデータ構成の
８ビツトデータを出力する。この８ビツトデータは、前
記の中心画素データＤ８　　が黒画素データか否か（第
７ビツト目）、輪郭点であるか否か（第６ビツト目）、
輪郭点追跡済か否か（第５ビツト目）、つぎの輪郭点位
置までの変位ｄＩ、ｄＪがどれ程か（第０〜３ビツト目
）を示している。上記のうち、変位ｄｌ　　は、第７図
に示す如く、ある輪郭黒画素（図中、＊印で示す）に対
する画像空間上での横方向の変位を示し、また変位ｄ）
　は、ある輪郭黒画素に対する画像空間上での縦方向の
変位を示したものであるが、この場合、その画素が輪郭
黒画素以外のときは変位を示す第０〜３ビツト目のデー
タは無視される。また第８図および第９図に示すような
、両隣りの周囲画素データが白画素データ「０」である
ビゲ状の黒画素ａ、ｂについては、これを無視して変位
ｄｌ、ｄＪ　　が生成されている。

尚、中心の画素が輪郭黒画素であるための必要十分条件
は、中心画素データＤ８　　が黒画素データ「１」であ
り且つ周囲画素データＤＯｒ　Ｄ２　ＨＤ４　ｒ　Ｄ６
のいずれもが白画素データｒＯＪ若しくは黒画素データ
「１」でない場合をいい、従って前記テーブルメモリ１
４の出力データの第６ビツト目は、画素データＤｏ、、
、＝Ｄ８がこの条件を充足するか否かによってそのデー
タ内容が設定される。

上記テーブルメモリ１４の出力データは、画像メモリ５
に順次格納され、その結果、画像メモリ５には第１図（
３）に示すＨ５Ｍ＠像が生成される。このＨ５Ｍｌ＠ｉ
は、黒画素データの対象領域を右（または左）に見なが
ら入力パターンの輪郭線を追跡するとき、っぎの境界黒
画素位置を規定する変位ｄＩ、　ｄＪを各輪郭黒画素位
置に対応させてデータ設定したものであり、前記輪郭追
跡部６は画像メモリ５中のＨ５ＭＩｗｌを走査して追跡
開始点を検出した後、変位ｄＩ、ｄ）を手がかりに輪郭
線の追跡を実行する。

第１０図および第１１図は輪郭追跡部６の回路構成例を
示し、第１２図はその輪郭追跡動作を示す。図示例の輪
郭追跡部６は、プログラムを格納するためのＲＯＭ　（
Ｒｅａｄ　０ｎｌｙ　Ｍｅｍｏｒｙ）１５と、入力パタ
ーンの輪郭追跡結果を格納するため（ｙ）　ＲＡ　Ｍ　
（Ｒａｎｄ□ｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）　１６
と、ＨＳＭ画像の輪郭追跡開始点を検出するための追跡
開始点検出回路１７と、隣接する追跡点を検出するため
の隣接追跡点検出回路１８と、前記プログラムに基づき
ＲＡＭ１６に対するデータの読み書きを行ないつつ各回
路動作を一連１こ制御してＨ５Ｍ画像の輪郭追跡処理を
実行するＣ　Ｐ　Ｕ　（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓ
ｓｉｎｇ　Ｕｎｉｔ　）　１９とから構成される。また
前記隣接追跡点検出回路１８は、画像メモリ５における
輪郭追跡開始点アドレスＳ　ＡＤＲまたは現追跡点アド
レスＴ　ＡＤＲを選択するためのセレクタ２ｏと、セレ
クタ２０の選択出力をセットするためのレジスタ２１と
、レジスタ２工の設定内容に変位ｄ１　、ｄＪをアドレ
ス加算してっぎの追跡点アドレスＴＡＤＲを算出する加
算回路２２とを含む。

然して、第１２図のフローチャートにおいて、まずＣＰ
Ｕ１９は輪郭追跡開始点検出アドレスＡＤＲを初期化し
た後、つぎに追跡開始点検出回路１７によって画像メモ
リ５の走査を開始して、Ｈ５Ｍ画像の追跡開始点アドレ
ス５ＡＤＲを検出する（ステップ４１．４２）。そして
ステップ４３で画像メモリ５の全面が走査されたか否か
をチェックし、この場合、その判定は“Ｎｏ”となるか
ら、ステップ４４へ進み、隣接追跡点検出回路１８がＨ
Ｓ　Ｍ画像の変位ｄＩ、ｄＪを参照してつぎの隣接追跡
点アドレスＴＡＤＲを検出する。そしてつぎのステップ
４５では、ＨＳ　Ｍ画像の対応画素データの追跡部フラ
グを「１」にセットした後、前記隣接追跡点アドレスＴ
ＡＤＲをＲＡＭ１５へ格納する。っぎのステップ４７で
は、この隣接追跡点アドレスＴＡＤＲが追跡開始点アド
レス５ＡＤＲと一致するか否かを判定しており、ＮＯ”
の判定でステップ４４へ戻り、同様の隣接追跡点アドレ
スＴＡＤＲの検出処理が繰返し実行される。かくてステ
ップ４７の判定がＹＥＳ”となったとき、ステップ４８
へ進み、追跡開始点アドレス５ＡＤｋに１加算した値を
追跡開始点検出アドレスＡＤＲとして、つぎの追跡開始
点の検出動作へ移行する（ステップ４２）。

【図面の簡単な説明】

第１図はＨＳ　Ｍ画像の生成過程を説明するための図、
第２図は輪郭追跡装置の全体概略構成を示すブロック図
、第３図はノイズ除去回路および変位生成回路を詳細に
示した輪郭追跡装置のブロック図、第４図はノイズ除去
回路および変位生成回路における画素データの流れを示
す説明図、第５図はノイズ除去方法を示すフローチャー
ト、第６図は変位生成回路のテーブルメモリの出力デー
タ構成を説明するための図、第７図は変位を説明するた
めの図、第８図および第９図はヒゲ状黒画素をもつパタ
ーンについての変位生成動作を説明するための図、第１
０図および第１１図は輪郭追跡部の回路構成例を示すブ
ロック図、第１２図は輪郭追跡処理動作を示すフローチ
ャート、第１３図は従来例の全体構成を示すブロック図
、第１４図および第１５図は従来例の輪郭追跡処理動作
を説明するための図である。

Claims (1)

【特許請求の範囲】
1. 画像入力を白黒２値化して入力パターンを得る手段と、
   入力パターンの各構成画素につきその周囲８方向近傍の
   画素データを求める手段と、各構成画素データおよびそ
   の周囲８方向近傍の画素データに基づき入力パターンに
   おける輪郭黒画素を検出すると共につぎの輪郭黒画素位
   置までの縦横各方向の変位を求める手段と、各輪郭黒画
   素に対応して前記変位を順次格納して複合連鎖記号化画
   像を生成する手段とを具備して成る輪郭追跡装置。