JPS6344285A - パタ−ン認識装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、画像データから特定のパターンを認識する
パターン認識装置に関するものである。

〔従来の技術〕

従来この種の装置として第１０図に示すものがあった。

第１０図は従来のパターン認識装置の具体例として、参
考文献、手塚慶−１北橋忠宏、小川秀夫著、“ディジタ
ル画像処理工学”、日刊工業新聞社、１９８５．ｐｐ１
０？−１１１に示されたテンプレートマツチング手法の
説明図である。

第１１図において、１はテンプレートデータを記憶する
テンプレートメモリ、２は図面の画像データを記憶する
記憶装置、３は前記テンブレートメモリ１と記憶装置２
に記憶されたデータの一致度を計測する演算装置である 次に動作について説明する。まず、第１０図（ａ）に示
すパターンを認識する場合にはテンプレートメモリ１に
第１０図（１））に示すテンプレートデータを用意し、
記憶装置２に記憶さた図面の画像データと演算装置３で
照合する。演算装置３では画像データ中のテンプレート
データのサイズ内の画素（第１１図（Ｃ）の破線内の部
分）について、テンプレートデータの画素の値との一致
度を調べ、パターンの同一性を判定する。この操作を画
像データ中の照合範囲を一画素ずつ移動しく第１０図（
Ｃ）の矢印）、画像データ全面について行い、結果を記
憶装置２に格納する。

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

従来のパターン認識装置は以上のように構成されている
ので、テンプレートデータの画素数の演算を画像データ
の画素数回だけ行うことになる。

例えば、テンプレートデータが３２Ｘ３２画素、画像デ
ータが１００ＯＸ１００Ｏ画素とすると演算回数は約１
，０００，０００，０００回となる。よって演算装置３
が１秒に１，０００，０００回演算可能としても１００
０秒かかることになり処理に多大の時間がかかるという
問題点があった。また、これを短時間に行おうとすれば
、石川、星野：２値画像マツチング用ＬＳＩの開発、昭
和６１年度電子通信学会総合全国大会１２９５に示され
るような専門のハードウェアを必要とする等の問題点が
あった。

この発明は上記のような問題点を解消するためになされ
たもので、既存のハードウェアを用いて短時間で画像デ
ータから特定パターンを認識するパターン認識装置を得
ることを目的とする。

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

この発明に係るパターン認識装置は、認識しようとする
パターンに特徴的な値をもつ画素を指定し、その指定さ
れた画素のみに注目するとともに、画像データに対し高
速のラスター演算を実行するようにしたものである。

〔作　用〕

この発明におけるパターン認識装置は認識しようとする
パターンに特徴的な値を持つ特定画素を指定し、演算回
数を凍らすようにし、ラスター演算の実行は画素の演算
を高速で行うようにする。

〔実施例〕

以下、この発明の一実施例を図について説明する。第１
図において、４は図面の２値画像データを認識しようと
するパターンのデータと演算結果とを記憶する記憶装置
、５はラスター演算を行うラスター演算装置、６は中央
処理装置である。なお、ラスター演算とは、ビット単位
に指定した記憶領域を他の領域に転送し、転送先の領域
と論理演算を行う機能で、ワークステーションに装備さ
れている（「ワークステーションのマルチウィンドウ表
示方法を比較する」日経エレクトロニクス、１９８５年
７月２９日号、Ｎ１１３７４参照）、ラスター演算は、
本来デイスプレィ装置のマルチウィンドウ表示等を行う
ための機能である。

このラスター演算においては、転送元のビットをＳ、転
送先のビットをＤ、論理演算をＦとすると Ｄ−Ｆ（’Ｓ、Ｄ）　　　　　　　・・−・−・・・−
（１）を数Ｍバイト／秒程度で行う（板材、「高機能ワ
ークステーションのアーキテクチャ」、情報処理、ｖｏ
１２５、隘２、ｐｐ９３−１０２．１９８４年２月）。

この機能を用いてパターン認識を高速に行う。

次に動作について説明する。まず第２図のフローチャー
トにおいて、ステップ７では初期設定を行う（ステップ
７）。そして図面等の２値画像データ、認識しようとす
るパターンの基準画素及びそのパターンに特徴的な画素
の値と基準画素に対する座標を記憶装置４に入力する（
ステップ８）。

さらに、記憶装置４に画像データのサイズに合わせて、
演算結果データの領域を確保して　“１”に初期化する
（ステップ９）。以下、第３図（ａｌのパターンを認識
するものとして説明する。この場合、ステップ７では第
８図（ｂ）に示すように、基準画素Ａと特徴的な画素Ｂ
、Ｃ，Ｈの情報を入力する。

ここでは、Ａ、Ｂ、Ｃ，Ｅをパターンの特定画素とする
。ステップ８では特定画素の基準画素に対する座標（Ｘ
、Ｙ）とその値Ｐを基準画素Ａの値に設定する。すなわ
ち、Ｘ＝Ｙ＝Ｏ，Ｐ＝１である。

ステップ９では座標Ｘ、　Ｙによりラスター演算の演算
対象領域を設定する。画像データが（ｘ。

ｙ）、０≦Ｘ≦ｘｍ、Ｏ≦ｙ≦ｙｍのとき、領域は次の
ようになる。ＸについてはＸ≧０のとき０≦Ｘ≦ｘｍ−
Ｘ、Ｘ＜Ｏのとき−ＸＳＸ≦ｘｍ。

ｙについてもＹ≧０のとき０≦ｙ≦ｙｍ−Ｙ。

ｙ＜ｏのとき−Ｙ≦ｙ：５７ｍである。ステップ１０で
はｐの値を判定し、ｐ≠０すなわちり−１ならばステッ
プ１１へ、ｐ＝０ならばステップ１２へ移る。

ステップ１１では画像データに対し次のラスター演算を
行う。

Ｄ　（ｘ、ｙ）−３（ｘ＋Ｘ、ｙ＋Ｙ）−Ｄ　（ｘ。

ｙ）−−−−・−（２） ここで、Ｓ　（ｘ、ｙ）は画像データの画素、Ｄ（ｘ、
ｙ）は記憶装置４の演算結果データを格納する領域の画
素である。ｘ、ｙは画像データ、演算結果データの座標
、・は論理積を表す。この演算について第４図で説明す
る。第４図（ａｌは画像データを示す図で、第３図（ａ
ｌのパターンを含む。第４図（ｂｌはＳ　（Ｘ＋Ｘ、ｙ
−ｔ−Ｙ）を第３図中）の已について説明する図、第４
図（Ｃ１は演算結果を示す図である。

第４図（ａ）に示す画像データＳ　（ｘ、　　ｙ）を第
３図Ｃｂ＞のＢについての演算とすると、Ｂの基準画素
Ａに対する座標は（Ｘｓ　、　Ｙｓ　）で値は“１”で
あるから、Ｓ　（ｘ　＋　Ｘｇ　、　　ｙ　＋　ＹＢ　
）とＳ　（ｘ。

ｙ）を重ねると第４図（ｂ）のようになる。ここで４１
はＳ　（ｘ、　　ｙ）すなわち画像データ、４２はｓ　
（ｘ＋ｘａ　、　　）’＋Ｙｍ　）を示す。画像データ
上でパターンの基準画素となる画素（ｘｏ、ｙｏ）では
、Ｓ　（ｘ、＋Ｘ、、Ｙａ＋Ｙ＋＋）が“１”となる。

従って、パターン上の特定画素（Ｘ、　Ｙ）が“１″な
ら、Ｓ　（ｘ　＋　Ｘ　、　ｙ　＋　Ｙ　）が１″とな
る画素にパターンの基準画素が存在する可能性がある。

それ以前の演算結果データＤ　（ｘ、ｙ）に（２）式の
演算を行うことにより、Ｄ　（ｘ、ｙ）には基準画素の
ある可能性のある画素が“１”となって残る。、′１”
に初期化したＤ　（ｘ、ｙ）に対し、Ａについて（２）
式を行うと、Ｄ　（ｘ、ｙ）はＳ（ｘ、ｙ）と等しくな
る。このＤ　（ｘ、ｙ）に対し、Ｂについて（２）式を
行った結果が第４図（Ｃ）である。ステップ９で設定す
る領域はＡについての演算では画像データ全域、Ｂにつ
いての演算では、第４図Ｔｏ）の４１と４２が重なって
いる領域である。

ステップ１２では次のラスター演算を行う。

Ｄ（ｘ、ｙ）　＝Ｓ　（ｘ＋Ｘ、ｙ＋Ｙ）　　ＨＤ（ｘ
、ｙ）　−−−＜３）Ｓ　（Ｘ　”　Ｘ　＋　ｙ　＋’
Ｙ　）はＳ　（ｘ　＋Ｘ、ｙ＋Ｙ）の否定を表す。この
演算について第５図で説明する。第５図（ａ）は画像デ
ータを示す図、第５図（ｂｌはＳ　（ｘ＋Ｘ、ｙ＋Ｙ）
について第３図（ｂｌの已について説明する図、第５図
ｔｃ）は演算結果を示す図である。ＥのＡに対する座標
は（ｘ、、ｙ、）で値は“０”であるから、Ｓ　（ｘ＋
）（ｔ、）’＋Ｙｔ　）とＳ　（ｘ、ｙ）を重ねると第
５図ｆｔ）ｌのようになる。

５１はＳ　（ｘ、　ｙ）　、５２はＳ　（Ｘ＋ＸＥ、）
＋＋Ｙｚ）を示す。

画像データ上でパターンの基準画素となる画素（ｘｏ、
ｙｏ）ではＳ　（ｘｏ　＋Ｘｉ　、Ｙｏ　＋Ｙｔ　）は
“０”になる。従って、パターン上の特定画素（Ｘ、　
Ｙ）が“０”なら、Ｓ　（ｘ＋Ｘ、ｙ＋Ｙ）が“０″と
なる画像データ上の画素（Ｘ、　　）ｌ）にパターンの
基準画素が存在する可能性がある。それ以前の演算結果
データＤ　（ｘ、ｙ）に（３）式の演算を行うことによ
り、Ｄ　（ｘ、ｙ）には基準画素のある可能性のある画
素が“１”となって残る。Ｓ（ｘ、ｙ）に等しいＤ　（
ｘ、ｙ）に対し、已について（３）式を行った結果が第
５図（Ｃ１である。

ステップ１３では、パターンの特定画素すべてについて
演算を終了したかを判断し、終了していれば、ステップ
１５に進み、中央処理装置６で演算結果の画像データか
ら値が“１”の画素の座標を読みとり、認識したパター
ンの座標として処理を終了し、残っていれば、ステップ
１４でｘ、　ｙ。

Ｐを次の特定画素の情報に変更してステップ３に移る。

この装置によるパターン認識を第６図に示す。第６図（
ａ）の画像データから、第３図（ａ）のパターンを認識
する。画像データに第３図（ｂｌのＡについての演算を
行うと演算結果Ｄ　（ｘ、　　ｙ）は第６図（ａ）に等
しくなる。これに已についての演算を行うと第６図（ｂ
ｌ、さらにＣについて行うと第６図（Ｃ）、さらに已に
ついて演算を行うと第６図（ｄ）に示す演算結果が得ら
れ、第３図（ａ）のパターンの基準画素が存在する画素
が“１“のまま残り、この“１”の座標を読みとってパ
ターンが認識される。この値が“１”である画素の座標
を認識したパターンの座標として出力する。パターン上
の特定画素の指定は画像データとの関連で、そのパター
ンに特徴的な画素を選ぶ。（２）、（３）式の演算、ス
テップ１１及び１２はラスター演算装置で高速に行う。

例えば、１０００ｘｌＯＯＯ画素の画像データの場合、
ラスター演算装置の能力をＩＭバイト／秒としてもパタ
ーン上の特定画素１画素分について、演算時間は約０．
１秒、パターン上、指定する画素を１０画素とすると演
算時間は約１秒となる。

また、仮に３２Ｘ３２画素のパターンについて３２Ｘ３
２画素すべてを特定画素としたとしても演算時間は約１
００秒である。パターンの特定画素の指定と、ラスター
演算の実行により処理時間を短縮することができる。

なお、上記実施例では、Ｄ　（ｘ、　　ｙ）を“１”に
初期化したが、パターンの基準画素の値により、“１”
なら画像データ、“０”なら画像データを反転したもの
に初期化してもよい。また、最初のラスター演算で、Ｐ
が１なら Ｄ　（ｘ、ｙ）”Ｓ　（ｘ＋Ｘ、ｙ＋Ｙ）　　・・・（
４１ＰがＯなら Ｄ　（ｘ、ｙ）＝Ｓ　　ｘ＋Ｘ、ｙ十Ｙ）　　−（５）
を実行するようにすれば、Ｄ　（ｘ、ｙ）の初期化は必
要ない。また、Ｄ　（ｘ、ｙ）においてパターンの存在
する画素を“１”としたが、“１”と“０”を反転させ
て考え、存在する画素を“０”として行うこともできる
。また、パターンの基準点は、パターンごとに設定して
も、全パターンで同一の画素にしてもよい。また、Ｓ　
（ｘ、ｙ）とＤ　（ｘ、ｙ）はラスター演算装置による
ラスター演算が可能であれば、異なる記憶装置に格納し
てもよい。とくに、Ｄ　（ｘ、　　ｙ）をデイスプレィ
装置上のデイスプレィ用の記憶装置に格納すれば、演算
結果が即座にデイスプレィ装置に表示される。

また、複数の２値画像データからなるカラーの画像デー
タにも適用できる。また、パターンの基準画素について
は、設定だけを行って、その画素の値によるラスター演
算は行わない動作にしてもよい。また、パターンの特定
画素は、初期設定の段階ですべて入力するようにしたが
、第２図のステップ１３の手前で１画素ずつ逐次的に入
力してもよい。また、すべての特定画素についての演算
を行った後に処理を終了するようにしたが、演算結果デ
ータＤ　（ｘ、ｙ）がすべて“０”になるか、“１″と
なる画素の数が一定値以下になったときに処理を終了す
るようにしてもよい。

また、他の実施例として第７図はラスター演算の機能を
中央処理装置（ＣＰＵ）で行うようにしたものである。

第７図において、６はラスター演算機能をも果たす中央
処理装置（ＣＰＵ）　、１６は前記中央処理装置６のラ
スター演算機能部を示す。中央処理装置６で行うラスタ
ー演算のフローチャートを第８図に示す。第８図は第２
図のフローチャートのステップ１１およびステップ１２
の内容に相当する。ステップ８１はラスター演算の初期
設定で、画像データの転送元のアドレス、転送先のアド
レスを設定する。ステップ８２で転送元のデータと転送
先のデータを取り出し、ステップ８３で論理演算を行い
、転送先のアドレスにステップ８４で格納する。ステッ
プ８５では、第２図ステップ９で設定された領域につい
て演算が実行されたかどうか判定する。領域内すべての
画素について演算を終了していれば、ラスター演算を終
了し、そうでなければ、ステップ８６で転送元、転送先
のアドレスを変更して、ステップ８２に戻る。以上を中
央処理装置６で行う。ステップ８３で行う論理演算は、
特定画素が“１”のときは、（２）式に示す転送元と転
送先の画素の論理積であり、特定画素が“０”のときは
、（３）式に示す転送元の画素の否定と転送先の画素と
の論理積である。

また、ラスター演算装置内に第２の記憶装置を組み込む
ようにしてもよい、この実施例を第９図に示す。第９図
において、１７はラスター演算装置５内に組み込んだ第
２の記憶装置を示す。次に動作について説明する。

まず、画像データをラスター演算装置５内の第２の記憶
装置１７に記憶し、特徴画素のデータを記憶装置４に記
憶する。記憶装置（第１の）４に記憶した特徴画素のデ
ータにより、中央処理装置６で、ラスター演算装置５が
行う演算の種類、記憶領域を制御する。ラスター演算装
置５は、ラスター演算装置５′内の第２の記憶装置１７
に記憶された画像データに対しラスター演算を行い、結
果をラスター演算装置５内の第２の記憶装置１７に格納
する。

〔発明の効果〕

以上のように、この発明によれば、認識しようとするパ
ターンに特徴的な値を持つ特定画素を指定し、その指定
された画素のみに注目すると共に画素データに対し高速
のラスター演算を実行すると共にラスター演算機能を装
備したワークステーションによって実行できるので、専
用のハードウェアを用いることもなく短時間で特定のパ
ターンの認識ができる効果がある。

【図面の簡単な説明】

第１図はこの発明の一実施例によるパターン認識装置を
示すブロック図、第２図はこの発明の一実施例によるパ
ターン認識装置の動作を示すフローチャート、第３図、
第４図、第５図及び第６図はこの発明の一実施例による
パターン認識装置の動作を示す説明図、第７図はこの発
明の他の実施例によるパターン認識装置を示すブロック
図、第８図はこの発明の他の実施例によるパターン認識
装置の動作を示すフローチャート、第９図はこの発明の
他の実施例によるパターン認識装置を示すブロック図、
第１０図は従来のパターン認識装置の動作を示す説明図
、第１１図は従来のパターン認識装置を示すブロック図
である。 ４は記憶装置、５はラスター演算装置、６は中央処理装
置、１６はラスター演算機能部、１７はラスター演算装
置内の第２の記憶装置である。 なお、図中、同一符号は同一、又は相当部分を示す。 （外２名） 第２図 第４図 ｙ 第５図　　　　第６図 ■ 第７図　　　第８図 第９図 １７：”）ス９−：＊’ｌ＊！ｌ肉／ｌ、ｆ２Ｑｉ己十
）Ｊ　置第１０図　　　　第１１図 手続補正書（自発）

Claims (3)

【特許請求の範囲】
1. （１）図面の２値画像データを格納し、認識しようとす
   るパターンの特定画素のデータと後述のラスター演算結
   果とを格納する記憶装置と、前記記憶装置のビット単位
   の領域のデータを他の領域に転送し転送先の領域のデー
   タと論理演算を行うラスター演算装置と、前記記憶装置
   に格納された認識しようとするパターンの特定画素の位
   置情報と画素の値とにより前記ラスター演算装置の夫々
   の転送先及び転送元の領域と論理演算の種類とを制御す
   ると共に、該ラスター演算結果を転送先領域より読みと
   る中央処理装置とを備えたパターン認識装置。
2. （２）前記記憶装置を備えた中央処理装置にラスター演
   算機能部を持たせるようにしたことを特徴とする特許請
   求の範囲第１項記載のパターン認識装置。
3. （３）図面の２値画像データを格納し、認識しようとす
   るパターンの特定画素のデータを格納する第１の記憶装
   置以外にラスター演算結果を格納する第２の記憶装置を
   ラスター演算装置内に組込むようにしたことを特徴とす
   る特許請求の範囲第１項記載のパターン認識装置。