JPH0634228B2

JPH0634228B2 - パタ−ン抽出装置

Info

Publication number: JPH0634228B2
Application number: JP1902287A
Authority: JP
Inventors: 茂阿部; 泰明中村; 克之亀井
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1987-01-28
Filing date: 1987-01-28
Publication date: 1994-05-02
Anticipated expiration: 2009-05-02
Also published as: JPS63186381A

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明は、２値画像データから特定のパターン、例え
ば直線成分を抽出するパターン抽出装置に関するもので
ある。

〔従来の技術〕

従来、この種のパターン抽出装置として第21図に示すも
のがあった。第22図は従来のパターン抽出装置が行って
いるテンプレートマッチングによる線の抽出に係るテン
プレート、第23図は同じく線の抽出における２値画像デ
ータを示す説明図である。この例は、参考文献、手塚慶
一，北橋忠宏，小川秀夫著，“ディジタル画像処理工
学”、日刊工業新聞社，1985，ＰＰ７２〜７９に示され
たものである。第21図において、(1)はテンプレートデ
ータを記憶する記憶装置で、テンプレートメモリ，(2)
は図面の２値画像データを記憶する記憶装置，(3)はテ
ンプレートメモリ(1)と記憶装置(2)に記憶されたデータ
の一致度を計測する演算装置である。

次に動作について説明する。２値画像データ（以下、画
像データと記す）からｘ軸方向の“１”の画素の直線を
抽出する場合には、テンプレートメモリ(1)に第22図に
示すテンプレートデータを用意し、記憶装置(2)に記憶
された図面の画像データと演算装置(3)で照合する。演
算装置(3)では画像データとテンプレートデータとの相
関をとり、画像データ中の直線の有無を判定する。即
ち、第23図において、画像データをＩ(x,y)、破線
（イ）に示すテンプレートデータの位置座標を(x,y)と
すると、第21図に示すテンプレートデータに関して以下
のような演算を行う。

得られた演算結果を閾値処理をして２値化し、Ｉ(x,y)
からｘ軸方向の直線を抽出した２値画像を得る。式(1)
の計算は第23図の矢印に示すように画像データ上でテン
プレートデータを一画素ずつ移動させて、画像データ全
面について行い、得たＪ(x,y)または閾値処理をして得
た２値画像を記憶装置(2)に格納する。

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

従来のパターン抽出装置は以上のように構成されている
ので、テンプレートデータの画素数の演算を画像データ
の画素数回だけ行うことになる。例えばテンプレートデ
ータが３×３画素，画像データが1000×1000画素とする
と演算回路は9,000,000回となる。よって演算装置(3)が
１秒に1,000,000回演算可能としても９秒かかることに
なり、処理に多大の時間がかかるという問題点があっ
た。また、これを短時間に行おうとすれば、石川，星
野：２値画像マッチング用ＬＳＩの開発，昭和61年度電
子通信学会総合全国大会1295に示されるような専用のハ
ードウェアを必要とする等の問題点もあった。

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

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

この発明に係るパターン抽出装置は、特定パターンを抽
出する初期２値画像データ（Ａ）と、特定パターン抽出
のため上記初期２値画像データ（Ａ）をシフトさせて重
ねる方向及び距離を規定するシフトベクトルデータ
（Ｓ）と、特定パターンが初期２値画像データ（Ａ）中
に存在するときその位置を示す抽出パターン存在２値画
像データ（Ｂ_e）と、この抽出パターン存在２値画像デ
ータ（Ｂ_e）に示された特定パターンの存在位置おのお
のに特定パターンを復元することにより抽出結果となる
抽出パターン復元２値画像データ（Ｃ_e）をそれぞれ記
憶する記憶装置、２つの２値画像データ間でシフトベク
トルの値を換算して対応するビット単位の領域を取り出
し、ビット単位の論理演算結果を記憶装置に格納するラ
スタ演算を行うラスタ演算装置、記憶装置とラスタ演算
装置とを制御し、シフトベクトルデータ（Ｓ）が規定す
る複数のシフトベクトルに従って初期２値画像データ
（Ａ）をシフトさせた位置にある｛複数のラスタ演算用
第１２値画像データ（Ａｉ；ｉ＝１，２，…）｝と｛初
期２値画像データ（Ａ）及び抽出途中２値画像データ
（Ｂｉ；ｉ＝１，２，…）であるラスタ演算用第２２値
画像データ｝間で論理演算をとるラスタ演算を行い、次
のラスタ演算用第２２値画像データとなる抽出途中２値
画像データ（Ｂｉ；ｉ＝１，２，…）を得る処理をシフ
トベクトルデータ（Ｓ）が規定する複数回繰り返すこと
により、初期２値画像データ（Ａ）から抽出パターン存
在２値画像データ（Ｂ_e）に変換する第１変換手段、並
びに記憶装置とラスタ演算装置とを制御し、第１変換手
段で初期２値画像データ（Ａ）をシフトさせた方向と逆
方向に同距離だけ抽出パターン存在２値画像データ（Ｂ
_e）を複数回シフトさせた位置にある｛複数のラスタ演
算用第３２値画像データ（Ｂｅｉ；ｉ＝１，２，…）｝
と｛抽出パターン存在２値画像データ（Ｂ_e）及び復元
途中２値画像データ（Ｃｉ；ｉ＝１，２，…）であるラ
スタ演算用第４２値画像データ｝間で論理演算をとるラ
スタ演算を行い、次のラスタ演算用第４２値画像データ
となる復元途中２値画像データ（Ｃｉ；ｉ＝１，２，
…）を得る処理をシフトベクトルデータ（Ｓ）が規定す
る複数回だけ繰り返すことにより、抽出パターン存在２
値画像データ（Ｂ_e）から抽出パターン復元２値画像デ
ータ（Ｃ_e）に変換する第２変換手段を備えたものであ
る。

〔作用〕

この発明におけるラスタ演算装置は、ラスタ演算の実行
を高速で行うことができ、特定パターンの抽出を高速に
行う。さらに第１変換手段により初期２値画像データ
（Ａ）から抽出する特定パターンの存在を示す抽出パタ
ーン存在２値画像データ（Ｂ_e）に変換し、第２変換手
段により抽出パターン存在２値画像データ（Ｂ_e）から
抽出パターン復元２値画像データ（Ｃ_e）に変換するの
で、演算回数を減らすことができる。

〔実施例〕

以下、この発明の一実施例を図について説明する。第１
図において、(4)は図面の２値画像データと抽出しよう
とする特定パターンのデータと演算途中及び結果の２値
画像データを記憶する記憶装置、(5)はラスタ演算を行
うラスタ演算装置、(6)は中央演算処理装置（以下、Ｃ
ＰＵと記す）、(8)，(9)はＣＰＵ(6)で処理される第１
変換手段、第２変換手段である。なお、ラスタ演算と
は、ビット単位に指定した記憶領域を他の領域に転送
し、転送先の領域と論理演算を行う機能で、ワークステ
ーションに装備されている（「ワークステーションのマ
ルチウインドウ表示方法を比較する」日経エレクトロニ
クス，1985年７月29日号，no．374参照）。ラスタ演算
は、本来ディスプレイ装置のマルチウインドウ表示等を
行うための機能である。

ラスタ演算においては、転送元のビットをＳ，転送先の
ビットをＤ、論理演算をＦとすると、Ｄ←Ｆ（Ｓ，Ｄ） ……………(2) を数Ｍバイト／秒程度で行う。ラスタ演算についての参
考文献として坂村、「高機能ワークステーションのアー
キテクチャ」，情報処理、vol.25,no.2，pp93−102，19
84年２月がある。この機能を用いて特定パターン抽出を
高速に行う。

特定パターンを抽出する２値画像データを初期２値画像
データ（Ａ）とし、特定パターン抽出のため初期２値画
像データ（Ａ）をシフトさせて重ねる方向及び距離を規
定する特定パターンのデータをシフトベクトルデータ
（Ｓ）とする。シフトベクトルデータ（Ｓ）は特定パタ
ーンの位置情報と画素の値より決定され、例えばｘ軸方
向の直線抽出のための特定パターン(11)は第２図に示さ
れるようになり、このシフトベクトルデータ（Ｓ）とし
ては基準画素０と“１”の画素Ａ，Ｂのそれぞれの０対
する座標となり、これは第３図のステップ(7)で記憶装
置に記憶される。

第３図はＣＰＵ(6)で処理される処理手順を示すフロー
チャートである。

動作について説明する。第３図に示すフローチャートに
おいて、ステップ(7)で初期２値画像データ（Ａ）とシ
フトベクトルデータ（Ｓ）の初期設定を行う。初期２値
画像データ（Ａ）は２値（０と１）で、これをＩ(x,
y)，（０≦ｘ≦ｘｍ，０≦ｙ≦ｙｍ）とする。ステップ
(7)でこのＩ(x,y)を記憶装置(4)にビットマップデータ
として格納する。以下、第２図に示す特定パターン(11)
を用いて、ｘ軸方向に、連続して３画素以上が“１”の
値をもつ画素から成る直線を抽出するものとして説明す
る。特定パターン(11)に基づき、シフトベクトルデータ
（Ｓ）として、その基準画素Ｏと“１”の画素のＯに対
する座標をステップ(7)で記憶装置(4)に格納する。ステ
ップ(8)は第１変換手段を構成し、ラスタ演算装置(5)で
ラスタ演算を行い、初期２値画像データ（Ａ）；Ｉ(x,
y)上で、特定パターン(11)と一致するパターンを探し、
存在すればその基準点を抽出する。このステップ(8)で
抽出された画像データは抽出パターン存在２値画像デー
タ（Ｂ_e）となる。ステップ(8)の動作を第４図と第５図
を用いて説明する。例えば、初期２値画像データ
（Ａ）；Ｉ(x,y)を第４図(a)に示す。背景の画素は
“０”である。Ｉ(x,y)の中から第２図に示す特定パタ
ーン(11)と一致する箇所を抽出する。まず、特定パター
ン(11)の画素Ｏ(0,0)とＡ(1,0)に着目する。これに対応
するシフトベクトルデータ（Ｓ）のよりＩ(x,y)を−▲▼＝(−0,1)だけシフトさせ、ラ
スタ演算用第１２値画像データ(Ａ₁)を得る。これを第
４図(b)に示す。第４図(c)は、第４図(a)の初期２値画
像データ（Ａ）をラスタ演算用第２２値画像データと
し、第４図(b)をラスタ演算用第１２値画像データ
（Ａ₁）として、画像データ（Ａ），（Ａ₁）間で各画素
ごとに論理演算、この場合は論理積をとった抽出途中２
値画像データ（Ｂ₁）を示すものであり、第４図(c)上で
は、第４図(a)の画像上でｘ軸方向に２画素以上“１”
が並んでいる箇所のみ“１”となる。これは、特定パタ
ーン(11)の画素ＯとＡに対応するパターンの存在箇所を
第４図(a)から検出したことになる。同様に、特定パタ
ーン(11)の画素Ｂ(2,0)について第４図(a)に示す初期２
値画像データ（Ａ）を(−2,0)だけシフトさせてラスタ
演算用第１２値画像データ（Ａ₂）とする。第４図(c)で
示す抽出途中２値画像データ（Ｂ₁）をラスタ演算用第
２２値画像データとし、画像データ（Ａ₂），（Ｂ₁）間
で論理積をとる。結果は抽出途中２値画像データ
（Ｂ₂）となり、第４図(d)に示す。第４図(d)では第４
図(a)上でｘ軸方向に３画素以上“１”が並ぶ箇所が
“１”となる。この例では、特定パターン(11)は３画素
より構成されているので、以上の処理により第４図(a)
上に特定パターン(11)が存在するとき、その基準画素が
第４図(d)上で“１”となる抽出パターン存在２値画像
データ（Ｂ_e）が得られる。この演算をラスタ演算で実
行する。第５図は第１変換手段であるステップ(8)の動
作を示すフローチャートである。ステップ(80)で記憶装
置(4)上に抽出パターン存在２値画像データ（Ｂ_e）の格
納用のビットマップ領域Ｄ₁（x,y），（０≦ｘ≦xm，０
≦ｙ≦ym）を確保し、“１”に初期化する。ステップ(8
1)で記憶装置(4)よりシフトベクトルデータ（Ｓ）を取
り出し、ステップ(82)でラスタ演算を実行する際の初期
２値画像データ（Ａ）；Ｉ（x,y）のシフト量を設定す
る。これは、特定パターン(11)上の“１”の画素（X,
Y）より、（−Ｘ，−Ｙ）となる。また、ラスタ演算を
行う画像データ上の領域も設定する。このシフト量と画
像データの領域によりＣＰＵ(6)でラスタ演算装置(5)を
制御する。ステップ(83)ではラスタ演算装置(5)によ
り、記憶装置(4)上のＩ（x,y），Ｄ₁（x,y）に対し、次
のラスタ演算を実行する。

Ｄ₁（x,y）←Ｉ（x+X,y+Y）・Ｄ₁（x,y） ………(3) これはＩ（x,y）を（−Ｘ，−Ｙ）だけシフトして、Ｄ₁
（x,y）と論理積をとることを意味する。演算の領域
は、ｘについてｘ≧０のとき０≦ｘ≦xm−X,X＜０のと
き−Ｘ≦ｘ≦xm,yについてＹ≧０のとき０≦ｙ≦ym−Y,
Y＜０のとき−Ｙ≦ｙ≦ymである。Ｉ（x+X,y+Y）はラス
タ演算用第１２値画像データ（Ａｉ；ｉ＝１，２，…
…）の画素を示し、Ｄ₁（x,y）はラスタ演算用第２２値
画像データの画素を示す。ステップ(84)で、特定パター
ン(11)上のすべての“１”の画素について式(3)の演算
を行ったかどうか判定し、行っていればステップ(8)を
終了、そうでなければステップ(81)へ移り、特定パター
ン(11)の次の“１”画素について演算を進める。Ｈ以上
がステップ(8)の動作であり、初期２値画像データ
（Ａ）が抽出パターン存在２値画像データ（Ｂ_e）に変
換される。次のステップ(9)では、ステップ(8)で得られ
た抽出パターン存在２値画像データ（Ｂ_e）より、その
画像データ上に特定パターン(11)を復元して抽出結果と
なる抽出パターン復元２値画像データ（Ｃ_e）を得る第
２変換手段である。ステップ(8)で得られた抽出パター
ン存在２値画像データ（Ｂ_e）；Ｄ₁(x,y)上では、初期
２値画像データ（Ａ）；Ｉ(x,y)に特定パターン(11)が
存在するとき、その基準画素のみが“１”となってい
る。即ち、第４図(d)では、第４図(a)に第２図のパター
ンが存在するとき、基準画素Ｏに対応する位置の画素の
みが“１”となっている。そこで、ステップ(9)で、特
定パターン(11)の基準画素Ｏ以外の“１”画素（Ａ，
Ｂ）に対応する位置の画素も“１”にする。ステップ
(9)の動作を第６図と第７図を用いて説明する。第６図
(a)はステップ(8)で得られた抽出パターン存在２値画像
データ（Ｂ_e）；Ｄ₁(x,y)で、第４図(d)に等しい。ま
ず、第２図の特定パターン(11)の画素Ｏ(0,0)とＡ(1,0)
に着目する。これに対応するシフトベクトルデータ
（Ｓ）の▲▼＝(1,0)よりＤ₁(x,y)を▲▼＝(1,
0)だけシフトさせて、ラスタ演算用第３２値画像データ
(B_e1)とする。これは第１変換手段において初期２値画
像データ（Ａ）をシフトさせた方向と逆方向で同距離の
シフトになりこれを第６図(b)に示す。第６図(c)は、第
６図(a)に示す抽出パターン存在２値画像データ（Ｂ_e）
であるラスタ演算用第４２値画像データと第６図(b)に
示すラスタ演算用第３２値画像データ(B_e1)の各画素ご
との論理演算、この場合は論理和をとった画像である。
第６図(c)上では、第４図(a)上に特定パターン(11)が存
在するとき、そのＯとＡに対応する画素が“１”とな
る。論理和によって得られた画像データを復元途中２値
画像データ（Ｃ₁)とし、次のラスタ演算用第４２値画像
データとなる。同様に、特定パターン(11)の画素Ｂ(2,
0)について第６図(a)を▲▼(2,0)だけシフトさせた
ラスタ演算用第３２値画像データ(B_e2)と第６図(c)との
論理和をとる。得られた復元途中２値画像データ（Ｃ₂)
を第６図(d)に示す。特定パターン(11)は３画素より構
成されるため、シフトベクトルデータ（Ｓ）で規定する
シフト数は２回となり、第６図(d)は第４図(a)上の特定
パターン(11)を抽出した結果の抽出パターン復元２値画
像データ（Ｃ_e）となる。第６図(d)ではｘ軸方向に３画
素以上“１”が並べば、それらがすべて抽出されてい
る。したがってｘ軸方向の直線が抽出される。この演算
をラスタ演算で実行する。第７図は第２変換手段である
ステップ(9)の動作を示すフローチャートである。ステ
ップ(90)でＣＰＵ(6)により記憶装置(4)上に抽出結果で
ある抽出パターン復元２値画像データ（Ｃ_e）格納用の
ビットマップ領域Ｄ₂(x,y)，（０≦ｘ≦xm，０≦ｙ≦y
m)を確保し、“０”に初期化する。ステップ(91)で記憶
装置(4)より特定パターン(11)の画素の座標(X,Y)を取り
出す。ステップ(92)では、ラスタ演算装置(5)でラスタ
演算を実行する際のＤ₁(x,y)のシフト量を設定する。シ
フト量は特定パターン(11)上の“１”の画素(X,Y)よ
り、(X,Y)となる。また、ラスタ演算を実行する画像デ
ータ上の領域も設定する。ステップ(93)では、ＣＰＵ
(6)の制御のもとでラスタ演算装置(5)により、記憶装置
(4)上のＤ₁(x,y)，Ｄ₂(x,y)に対して次のラスタ演算を
実行する。

Ｄ₂(x,y)←Ｄ₁（ｘ−Ｘ，ｙ−Ｙ）＋Ｄ₂(x,y) ……
(4) これは、Ｄ₁(x,y)を(X,Y)だけシフトして、Ｄ₂(x,y)と
論理和をとることを意味する。Ｄ₁（ｘ−Ｘ，ｙ−Ｙ）
はラスタ演算用第３２値画像データ(B_e1)；ｉ＝１，
２，…）の画素を示し、Ｄ₂(x,y)はラスタ演算用第４２
値画像データの画素を示す。ステップ(92)で設定された
演算領域は、ｘについてＸ≧０のときＸ≦ｘ≦xm，Ｘ＜
０のとき０≦ｘ≦xm＋Ｘ，ｙについてＹ≧０のときＹ≦
ｙ≦ym，Ｙ＜０のとき０≦ｙ≦ym＋Ｙである。ステップ
(94)で特定パターン(11)上のすべての“１”画素につい
て式(4)の演算を行ったかどうか判定し、行っていれば
ステップ(9)を終了、そうでなければステップ(91)へ移
り、特定パターン(11)上の次の“１”の画素について演
算を進める。最初に基準画素Ｏについて演算を実行すれ
ば、式(4)の演算でＤ₂(x,y)はＤ₁(x,y)に一致する。以
上がステップ(9)の動作であり、抽出パターン存在２値
画像データ（Ｂ_e）が抽出パターン復元２値画像データ
（Ｃ_e）に変換される。ステップ(10)では、ステップ(9)
で得られた抽出パターン復元２値画像データ（Ｃ_e）；
Ｄ₂(x,y)をＣＰＵ(6)により記憶装置(4)から出力する。
以上により、初期２値画像データ（Ａ）上のｘ方向に３
画素以上“１”が連続する直線が抽出される。第４図
(a)と第６図(d)を比較すると、第４図(a)に示す初期２
値画像データ（Ａ）上のｘ軸方向の直線（３個以上並ん
だ“１”画素）が第６図(d)において抽出されているこ
とがわかる。

式(3)，(4)の演算はラスタ演算装置(5)で高速に実行可
能である。以上述べたように、第２図の特定パターンを
用いる抽出では、画像データに対し６回のラスタ演算を
行えばよい。この場合1000×1000画素の画像データのと
き、ラスタ演算装置(5)の能力を１Ｍバイト／秒として
も、演算時間は約0.6秒となる。特定パターンの画素数
を９としても、演算時間は約1.8秒であり、従来のパタ
ーン抽出装置と比較すると、大巾に処理時間を短縮でき
る。

上記実施例における特定パターンは３画素で構成してい
るため、シフトベクトルデータ（Ｓ）として▲▼，
▲▼の２つにつながるが、一般的にシフトベクトル
データ（Ｓ）がｎ個で構成されている場合には、第１変
換手段では、Ａ₁とＡ間でラスタ演算を行なってＢ₁を
得、Ａ₂とＢ₁間でラスタ演算を行ってＢ₂を得、Ａ₃とＢ
₂間でラスタ演算を行ってＢ₃を得、以下順次Ａ_nとＢ_n-1
間までラスタ演算を行ってＢ_eを得ることにより、初期
２値画像データ（Ａ）から抽出パターン存在２値画像デ
ータ（Ｂ_e）に変換し、第２変換手段では、Ｂ_e1とＢ_eで
ラスタ演算を行なってＣ₁を得、Ｂ_e2とＣ₁間でラスタ演
算を行ってＣ₂を得、Ｂ_e3とＣ₂間でラスタ演算を行って
Ｃ₃を得、以下順次Ｂ_enとＣ_n-1間までラスタ演算を行っ
てＣ_eを得ることにより、抽出パターン存在２値画像デ
ータ（Ｂ_e）から抽出パターン復元２値画像データ
（Ｃ_e）に変換する。

なお、上記実施例では、ｘ軸方向の直線を抽出したが、
他の傾きの直線についても同様に実行できる。また、第
２図に示す特定パターンを用いると、第８図に示す傾き
が０に近い直線も抽出できる。抽出する直線の傾きを絞
るには、ｘ軸方向の直線でいうならば、特定パターンを
ｘ軸方向に長くする。特定パターンの“１”の画素の長
さは、直線を抽出しようとする初期２値画像データによ
り適当に設定する。

また、上記実施例では、特定パターンより幅の広い直線
はすべて抽出するが、第９図のような特定パターン(11)
を用いることにより、特定の幅（第９図では幅１画素）
の直線のみを抽出できる。このとき第９図の“０の画素
に対するラスタ演算は“１”の画素のものとは異なる。
第１変換手段におけるステップ (83)では、式(3)の代わりに、を行う。(X,Y)は特定パターン(11)上、基準画素Ｏに対
する“０”の画素Ｏの座標はＩ(x+X，y+Y)の“１”と“０”の反転を示す。また、
第２変換手段において、特定パターン(11)の画素が
“０”の場合はラスタ演算を実行しない。従ってステッ
プ(8)、ステップ(9)はそれぞれ第10図、第11図のような
フローチャートになる。第10図では、ステップ(82)でシ
フト量，演算領域の設定に加え、ステップ(83)で行うラ
スタ演算の種類も設定する。特定パターン(11)をＴ(x,
y)とすると、Ｔ(X,Y)＝１なら式(3)，Ｔ(X,Y)＝０なら
式(5)の演算に設定する。第11図ではステップ(95)で特
定パターン(11)；Ｔ(X,Y)の値を判定し、“１”ならス
テップ(93)で式(4)のラスタ演算を実行し、“０”なら
ステップ(92)，ステップ(93)を省略してステップ(94)を
実行する。また、上記実施例では直線の抽出について説
明したが、破線，点線，一点鎖線，二点鎖線などについ
ても実行できる。第12図に破線抽出のための特定パター
ン(11)を示す。“−”で示した画素は“０”でも“１”
でもよいということを意味し、第１変換手段におけるス
テップ(83)、第２変換手段におけるステップ(93)のラス
タ演算（式(3)，式(4))を実行しない。第12図に示す特
定パターン(11)を用いた破線の抽出の動作を第13図に示
す。第13図(a)が初期２値画像データ（Ａ）；Ｉ(x,y)
で、第13図(b)が、ステップ(8)で得られる抽出パターン
存在２値画像データ（Ｂ_e）；Ｄ₁(x,y)，第13図(c)がス
テップ(9)で得られる抽出パターン復元２値画像データ
（Ｃ_e）；Ｄ₂(x,y)である。“−”の画素についてステ
ップ(93)のラスタ演算（式(4))を実行してもよい。この
とき破線はつながって抽出され、抽出パターン復元２値
画像データ（Ｃ_e）は第３図(d)に示されるようになる。
第12図の特定パターン(11)を用いた一点鎖線，二点鎖線
の抽出の動作を第14図に示す。第14図(a)は初期２値画
像データ（Ａ）；Ｉ(x,y)，第14図(b)はステップ(8)で
得られる抽出パターン復元２値画像データ（Ｂ_e）；Ｄ₁
(x,y)，第14図(c)がステップ(9)で得られる抽出パター
ン復元２値画像データ（Ｃ_e）；Ｄ₂(x,y)で、一点鎖
線，二点鎖線が抽出されている。

また、上記実施例では、Ｄ₁(x,y)を“１”に初期化した
が、ステップ(83)で一回目には式(3)の代わりに、Ｄ₁(x,y)←Ｉ(x+X,y+Y) ……………(6) Ｔ(x,y)が“０”のときは式(5)の代わりに、を実行すれば、Ｄ₁(x,y)の初期化は必要ない。同様に、
Ｄ₂(x,y)を“０”に初期化したが、ステップ(93)で一回
目には式(4)の代わりに、Ｄ₂(x,y)←Ｄ(x+X,y+Y) ……………(8) を実行すれば、Ｄ₂(x,y)の初期化は必要ない。また、Ｄ
₁(x,y)，Ｄ₂(x,y)の初期化はそれぞれステップ(80)，ス
テップ(90)で行ったが、ステップ(7)で行ってもよい。
また、“１”の画素から成る直線を抽出したが、“１”
と“０”を反転させて考え、“０”の画素から成る直線
を抽出することもできる。Ｄ₁(x,y)，Ｄ₂(x,y)の“１”
と“０”を反転させ、Ｉ(x,y)上“１”の画素から成る
直線を抽出し、それをＤ₁(x,y)，あるいはＤ₂(x,y)上で
“０”の画素から成る直線として表すこともできる。ま
た、Ｉ(x,y)とＤ₁(x,y)とＤ₂(x,y)はラスタ演算装置(5)
によるラスタ演算が可能であれば、それぞれ異なる記憶
装置に格納してもよい。とくに、Ｄ₂(x,y)をディスプレ
イ装置上のディスプレイ用の記憶装置に格納すれば、演
算結果が即座にディスプレイ装置に表示される。また、
複数の２値画像データから成るカラーの画像データにも
適用できる。また、第１変換手段におけるステップ(83)
でＤ₁(x,y)がすべて“０”になった場合、初期２値画像
データ（Ａ）；Ｉ(x,y)上に特定パターンが存在しない
ことを意味するので、ステップ(8)を打ち切り、さらに
ステップ(9)のステップ(92)，(93)，(94)を省略するよ
うにしてもよい。また、さらに他の実施例として、特定
パターンを複数の部分パターンに分割して抽出を行うこ
ともできる。第15図，第16図を用いて説明する。第15図
(a)は抽出しようとする特定パターン(11)；Ｔ(x,y)，第
15図(b)は第15図(a)に示す特定パターン(11)を部分パタ
ーン(11a)；Ｐ(x,y)，(11b)；Ｑ(x,y)に分割した図で、
特定パターン(11)の基準画素をＯ、部分パターン(11
a)；Ｐ(x,y)，(11b)；Ｑ(x,y)基準画素をそれぞれＯ_P，
Ｏ_Qとする。ステップ(8)では、まず、部分パターン(11
a)；Ｐ(x,y)，部分パターン(11b)；Ｑ(x,y)をそれぞれ
特定パターンとして抽出パターン存在２値画像データ
（Ｂ_eP）；Ｄ_1P(x,y)，（Ｂ_eQ）；_1Q(x,y)を求める。こ
れを第16図に示す。第16図(a)が初期２値画像データ
（Ａ）；Ｉ(x,y)，第16図(b)が抽出パターン存在２値画
像データ（Ｂ_eP）；Ｄ_1P(x,y)，第16図(c)が抽出パター
ン存在２値画像データ（Ｂ_eQ）；Ｄ_1Q(x,y)である。こ
こで次のラスタ演を行う。

Ｄ₁(x,y)←Ｄ_1P(x+X_P,y+Y_P) ……………………(9) Ｄ₁(x,y)←Ｄ_1Q(x+X_Q,y+Y_Q)・Ｄ₁(x,y)……(10) 式(10)による結果である抽出パターン存在２値画像デー
タ（Ｂ_e）；Ｄ₁(x,y)を第16図(d)に示す。ステップ(9)
についても同様に行える。抽出パターン存在２値画像デ
ータ（Ｂ_e）；Ｄ₁(x,y)から部分パターンＰ(x,y)，Ｑ
(x,y)を復元した抽出パターン復元２値画像データ（Ｃ
_eP）；Ｄ_2P(x,y)，抽出パターン復元２値画像データ
（Ｃ_2Q）；Ｄ_2Q(x,y)に変換し、Ｄ₂(x,y)←Ｄ_2P(x-X_P,y-Y_P) ……………………(11) Ｄ₂(x,y)←Ｄ_2Q(x-X_Q,y-Y_Q)＋Ｄ₂(x,y)……(12) のラスタ演算を行う。式(12)による結果である抽出パタ
ーン復元２値画像データ（Ｃ_e）；Ｄ₂(x,y)を第16図(e)
に示す。第15図(a)に示す特定パターンが抽出されてい
る。この実施例では特にＰ(x,y)とＱ(x,y)が同一パター
ンのとき、抽出パターン存在２値画像データ（Ｂ_e）；
Ｄ_1P(x,y)とＤ_1Q(x,y)，抽出パターン復元２値画像デー
タ（Ｃ_e）；Ｄ_2Q(x,y)とＤ_2Q(x,y)がそれぞれ等しくな
るので、部分パターンＰ(x,y)，Ｑ(x,y)のどちらか一方
に関して求めればよく、演算回数を少なくできる。ラス
タ演算の対象の２値画像データ，演算領域，シフト量の
制御をＣＰＵ(6)で行う。

また、ステップ(8)でのパターン基準画素の検出は特定
パターン完全に一致する箇所のみを検出したが、特定パ
ターンの一部と合った箇所を検出するように、ラスタ演
算を設定してもよい。

また、ラスタ演算装置(5)を設けるかわりにラスタ演算
の機能を中央演算処理装置(6)で行うようにすることも
でき、この場合の構成を示すブロック図を第17図に示
す。第17図において、(4)は記憶装置、(6)はラスタ演算
機能を有する中央演算処理装置、(12)は中央演算処理装
置(6)のラスタ演算の機能を示す。中央演算処理装置(6)
で行うラスタ演算を第18図に示す。第18図はステップ(8
3)およびステップ(93)に相当する。ステップ(13)はラス
タ演算の初期設定で、画像データの転送元のアドレス、
転送先のアドレスを設定する。ステップ(14)で転送元の
データと転送先のデータを取り出し、ステップ(15)で式
(3)，(4)の論理演算を行い、転送先のアドレスにステッ
プ(16)で格納する。ステップ(17)ではステップ(82)，ス
テップ(92)で設定された領域について演算が実行された
かどうか判定する。領域内すべての画素について演算を
終了していれば、ラスタ演算を終了し、そうでなけれ
ば、ステップ(18)で転送元，転送先のアドレスを変更し
て、ステップ(14)に戻る。以上を中央演算処理装置(6)
のラスタ演算機能(12)で行う。

また、さらに他の実施例として、ラスタ演算装置(5)に
記憶装置を組み込んでもよい。この場合のブロック図を
第19図に示す。第19図において、(4)は記憶装置、(5)は
記憶装置を組み込んだラスタ演算装置、(6)は中央演算
処理装置，(19)はラスタ演算装置(5)内の記憶装置を示
す。動作について説明する。初期２値画像データ
（Ａ）；Ｉ(x,y)をラスタ演算装置(5)内の記憶装置(19)
に記憶し、特定パターン；Ｔ(x,y)によるシフトベクト
ルデータ（Ｓ）を記憶装置(4)に記憶する。記憶装置(4)
に記憶したシフトベクトルデータ（Ｓ）に従って中央演
算処理装置(6)で、ラスタ演算装置(5)が行う演算の種
類、記憶領域を制御する。ラスタ演算装置(5)は、ラス
タ演算装置(5)内の記憶装置(19)に記憶された初期２値
画像データ（Ａ）；Ｉ(x,y)，及びラスタ演算装置(5)内
の記憶装置(19)に確保されたラスタ演算用２値画像デー
タＤ₁(x,y)，Ｄ₂(x,y)に対しステップ(8)，ステップ(9)
でラスタ演算を行い、結果をラスタ演算装置(5)内の記
憶装置(19)に格納する。

また、上記実施例では、直線，破線などの直線上の図形
の抽出について説明したが、エッジや一般のパターンの
抽出についても上記実施例と同様の結果を奏する。第20
図に直線状の図形以外を抽出するための特定パターン(1
1)の例を示す。第20図(a)はエッジ抽出のための特定パ
ターン(11)，第20図(b)が十字のパターンを抽出するた
めの特定パターン(11)の例である。

〔発明の効果〕

以上のように、この発明によれば、特定パターンを抽出
する初期２値画像データ（Ａ）と、特定パターン抽出の
ため上記初期２値画像データ（Ａ）をシフトさせて重ね
る方向及び距離を規定するシフトベクトルデータ（Ｓ）
と、特定パターンが初期２値画像データ（Ａ）に存在す
るときその位置を示す抽出パターン存在２値画像データ
（Ｂ_e）と、この抽出パターン存在２値画像データ
（Ｂ_e）に示された特定パターンの存在位置おのおのに
特定パターンを復元することにより抽出結果となる抽出
パターン復元２値画像データ（Ｃ_e）をそれぞれ記憶す
る記憶装置、２つの２値画像データ間でシフトベクトル
の値を換算して対応するビット単位の領域を取り出し、
ビット単位の論理演算結果を記憶装置に格納するラスタ
演算を行うラスタ演算装置、記憶装置とラスタ演算装置
とを制御し、シフトベクトルデータ（Ｓ）が規定する複
数のシフトベクトルに従って初期２値画像データ（Ａ）
をシフトさせた位置にある｛複数のラスタ演算用第１２
値画像データ（Ａｉ；ｉ＝１，２，…）｝｛初期２値画
像データ（Ａ）及び抽出途中２値画像データ（Ｂｉ；ｉ
＝１，２，…）であるラスタ演算用第２２値画像デー
タ｝間で論理演算をとるラスタ演算を行い、次のラスタ
演算用第２２値画像データとなる抽出途中２値画像デー
タ（Ｂｉ；ｉ＝１，２，…）を得る処理をシフトベクト
ルデータ（Ｓ）が規定する複数回繰り返すことにより、
初期２値画像データ（Ａ）から抽出パターン存在２値画
像データ（Ｂ_e）に変換する第１変換手段、並びに記憶
装置とラスタ演算装置とを制御し第１変換手段で初期２
値画像データ（Ａ）をシフトさせた方向と逆方向に同距
離だけ抽出パターン存在２値画像データ（Ｂ_e）を複数
回シフトさせた位置にある｛複数のラスタ演算用第３２
値画像データ（Ｂｅｉ；ｉ＝１，２，…）｝と｛抽出パ
ターン存在２値画像データ（Ｂ_e）及び復元途中２値画
像データ（Ｃｉ；ｉ＝１，２，…）であるラスタ演算用
第４２値画像データ｝間で論理演算をとるラスタ演算を
行い、次のラスタ演算用第４２値画像データとなる復元
途中２値画像データ（Ｃｉ；ｉ＝１，２，…）を得る処
理をシフトベクトルデータ（Ｓ）が規定する複数回繰り
返すことにより、抽出パターン存在２値画像データ（Ｂ
_e）から抽出パターン復元２値画像データ（Ｃ_e）に変換
する第２変換手段を備えることにより、画像データから
特定パターンを抽出する時間を短縮できるパターン抽出
装置を得ることができる効果がある。

【図面の簡単な説明】

第１図はこの発明の一実施例によるパターン抽出装置を
示すブロック図，第２図はこの発明の一実施例によるパ
ターン抽出装置に係る特定パターンを示す説明図、第３
図はこの発明の一実施例によるパターン抽出装置の動作
を示すフローチャート、第４図(a)〜(d)はこの発明の一
実施例に係る第１変換手段による画像データの動作を順
に示す説明図、第５図はこの発明の一実施例に係る第１
変換手段の動作を示すフローチャート、第６図(a)〜(d)
はこの発明の一実施例に係る第２変換手段による画像デ
ータの動作を順に示す説明図、第７図はこの発明の一実
施例に係る第２変換手段の動作を示すフローチャート，
第８図はこの発明の一実施例により抽出される画像デー
タを示す説明図、第９図はこの発明の他の実施例による
パターン抽出装置に係る特定パターンを示す説明図、第
10図、第11図はこの発明の他の実施例に係る第１変換手
段、第２変換手段の動作を示すフローチャート、第12図
はこの発明のさらに他の実施例に係る特定パターンを示
す説明図、第13図(a)〜(d)、第14図(a)〜(c)はそれぞれ
第12図に示す特定パターン抽出の動作を示す説明図、第
15図(a)，(b)、第16図(a)〜(e)はこの発明のさらに他の
実施例に係る特定パターン、及びパターン抽出装置のパ
ターン抽出の動作を示す説明図、第17図はこの発明のさ
らに他の実施例によるパターン抽出装置を示すブロック
図、第18図は第17図に示すパターン抽出装置に係るラス
タ演算機能の動作を示すフローチャート、第19図はこの
発明のさらに他の実施例によるパターン抽出装置を示す
ブロック図、第20図(a)，(b)はそれぞれこの発明のさら
に他の実施例による特定パターンを示す説明図、第21図
は従来のパターン抽出装置を示すブロック図、第22図は
従来のパターン抽出装置に係るテンプレートの説明図、
第23図は従来のパターン抽出装置の動作を示す説明図で
ある。 (4)は記憶装置、(5)はラスタ演算装置、(6)は中央演算
処理装置、(8)は第１変換手段、(9)は第２変換手段、11
は特定パターンである。なお、図中、同一符号は同一、又は相当部分を示す。

Claims

【特許請求の範囲】

【請求項１】特定パターンを抽出する初期２値画像デー
タ（Ａ）と，上記特定パターン抽出のため上記初期２値
画像データ（Ａ）をシフトさせて重ねる方向、距離およ
びシフト回数ｎを規定するシフトベクトルデータ（Ｓ）
と，上記特定パターンが上記初期２値画像データ（Ａ）
中に存在するときその位置を示す抽出パターン存在２値
画像データ（Ｂ_e）と，この抽出パターン存在２値画像
データ（Ｂ_e）に示された上記特定パターンの存在位置
おのおのに上記特定パターンを復元することにより得ら
れる抽出パターン復元２値画像データ（Ｃ_e）をそれぞ
れ記憶する記憶装置，２つの２値画像データ間でシフト
ベクトルの値を換算して対応するビット単位の領域を取
り出し，ビット単位の論理演算結果を上記記憶装置の格
納するラスタ演算を行うラスタ演算装置，上記記憶装置
と上記ラスタ演算装置とを制御し，上記シフトベクトル
データ（Ｓ）が規定する複数のシフトベクトルに従って
上記初期２値画像データ（Ａ）をシフトさせた位置にあ
る｛複数のラスタ演算用第１２値画像データ（Ａｉ；ｉ
＝１，２，・・・）｝と｛上記初期２値画像データ
（Ａ）及び抽出途中２値画像データ（Ｂｉ；ｉ＝１，
２，・・・）であるラスタ演算用第２２値画像データ｝
間で論理演算をとるラスタ演算を行い，次の上記ラスタ
演算用第２２値画像データとなる上記抽出途中２値画像
データ（Ｂｉ；ｉ＝１，２，・・・）を得る処理を上記
シフトベクトルデータ（Ｓ）が規定するシフト回数ｎだ
け繰り返すことにより，上記初期２値画像データ（Ａ）
から上記抽出パターン存在２値画像データ（Ｂ_e）に変
換する第１変換手段，並びに上記記憶装置と上記ラスタ
演算装置とを制御し，第１変換手段で上記初期２値画像
データ（Ａ）をシフトさせた方向と逆方向に同距離だけ
上記抽出パターン存在２値画像データ（Ｂ_e）を複数回
シフトさせた位置にある｛複数のラスタ演算用第３２値
画像データ（Ｂｅｉ；ｉ＝１，２，・・・）｝と｛上記
抽出パターン存在２値画像データ（Ｂ_e）及び復元途中
２値画像データ（Ｃｉ；ｉ＝１，２，・・・）であるラ
スタ演算用第４２値画像データ｝間で論理演算をとるラ
スタ演算を行い，次の上記ラスタ演算用第４２値画像デ
ータとなる上記復元途中２値画像データ（Ｃｉ；ｉ＝
１，２，・・・）を得る処理を上記シフトベクトルデー
タ（Ｓ）が規定するシフト回数ｎだけ繰り返すことによ
り，上記抽出パターン存在２値画像データ（Ｂ_e）から
上記抽出パターン復元２値画像データ（Ｃ_e）に変換す
る第２変換手段を備えたパターン抽出装置。
【請求項２】シフトベクトルデータ（Ｓ）は，特定パタ
ーンの位置情報と画素の値により決定されることを特徴
とする特許請求の範囲第１項記載のパターン抽出装置。
【請求項３】ラスタ演算用第１２値画像データとラスタ
演算用第２２値画像データ間で行う論理演算は論理積演
算である特許請求の範囲第１項記載のパターン抽出装置
【請求項４】ラスタ演算用第３２値画像データとラスタ
演算用第４２値画像データ間で行う論理演算は論理和演
算である特許請求の範囲第３項記載のパターン抽出装
置。
【請求項５】第１変換手段では，Ａ₁とＡ間でラスタ演
算を行ってＢ₁を得，Ａ₂とＢ₁間でラスタ演算を行って
Ｂ₂を得，Ａ₃とＢ₂間でラスタ演算を行ってＢ₃を得，順
次シフトベクトルＳが規定するシフト回数ｎに対してＡ
ｎとn-1間までラスタ演算を行ってＢｅを得ることによ
り，初期２値画像データ（Ａ）から抽出パターン存在２
値画像データ（Ｂ_e）に変換するようにした特許請求の
範囲第１項記載のパターン抽出装置。
【請求項６】第２変換手段では，Ｂｅ₁とＢｅでラスタ
演算を行ってＣ₁を得，Ｂｅ₂とＣ₁間でラスタ演算を行
ってＣ₂を得，Ｂｅ₃とＣ₂間でラスタ演算を行ってＣ₃を
得，順次シフトベクトルＳが規定するシフト回数ｎに対
してＢｅｎとＣn-1間までラスタ演算を行ってＣｅを得
ることにより，抽出パターン復元２値画像データ
（Ｃ_e）に変換するようにした特許請求の範囲第１項記
載のパターン抽出装置。