JPH0140380B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は分類、検索に際し必須となる認識辞書
の自動作成に係り、特に情報認識システムの操作
の簡易化を図り、高速オンライン情報認識を実現
するに好適な認識辞書作成に特徴を有する情報認
識システムに関する。

〔発明の背景〕

一般に認識対象は、予め作成した認識辞書に従
つて識別される。当該認識辞書は、認識対象（以
下、カテゴリと称す）各々について様々な特徴量
を幾度か抽出した後、前記特徴量軸上における分
布データを解析することにより作成される。

その際、解析の簡易化のため及び解析者の主観
を交えないために当該認識辞書は、標準化された
方法で自動作成するのが望ましい。また認識辞書
の構造としては、認識の処理速度を重視した判定
木構造が有力である。

従来提案されている判定木辞書作成方法では十
分な認識速度は得られなかつた。例えば分離度
（隣り合うカテゴリの分散化）が最大の特徴量軸
上で、複数のカテゴリを２つのクラスに分類し、
分類後の複数のカテゴリから成る新たなクラスに
対して同様の分類を繰返していく方法がある。こ
の場合、認識時間は認識結果を出力するまでの、
カテゴリから抽出する特徴量の個数に比例して大
きくなる。このため当該個数を少なくするように
判定木辞書を作る必要があるにも拘らず、従来方
法では全く当該個数が考慮されていなかつた。し
たがつて判定木構造及びその結果としての認識速
度は偶然に決定されており、認識速度の短縮化は
企図されていなかつた。

〔発明の目的〕

本発明の目的は、特徴量軸上における複数カテ
ゴリの分布データから、認識結果を出力するまで
にカテゴリから抽出する特徴量の個数が少ない判
定木辞書を自動作成する方法を提供することにあ
る。

〔発明の原理及び特徴〕

本発明の原理を第１図ないし第３図を用いて説
明する。

判定木辞書による認識の最大の特長は、判定木
に沿つて同定を進めるに従つて、候補となるカテ
ゴリが指数関数的に減少していき、その結果、少
数回の特徴量抽出で認識結果が得られることであ
る。

一般に認識時間はほとんど特徴量抽出に要する
時間に支配されるから、上記特長は認識時間を短
縮する上で非常に有効となる。例えば、第１図の
＜例題＞に示す単語を識別するための判定木例の
＜木＞、＜木＞について考えよう。木の節に
記入した数字は、未知の単語から抽出する文字が
頭文字から何番目であるかを示し、（ ）内の文
字は当該抽出文字が該当する文字を示している。
すなわち、単語の１つの文字を１つの特徴量とし
て考えて作つた判定木である。＜木＞は常に未
知の単語から、２文字だけ抽出すれば答が出る。
すなわち未知の単語に対して単純に３文字抽出し
て、辞書の単語と同定を試みるよりも早く答が出
る。一方＜木＞はBoy、Bobに対して３文字抽
出しなければならないが、Bet、Can、Sinに対し
ては１文字の抽出で解答ができる。いずれの木も
常に単純に３文字抽出するよりも早いと言える。
各々の木は異なつた性質を有する。即ち＜木＞
は最大認識時間が短く、＜木＞は総合認識時間
（あるいは平均認識時間）が短い。

ここで最大認識時間とは、カテゴリの１つを認
識するのに要する時間の最大値である。換言すれ
ば上位のカテゴリに対して推測した判定木へ開示
点から、当該判定木の先端で最深箇所に到達する
までに抽出する特徴量の計算時間の総和である。

また総合認識時間とは、カテゴリすべてを認識
するのに要する時間を言う。換言すれば上位のカ
テゴリに対して推測した判定木の開始点から、当
該判定木のすべての先端に到達するまでに抽出す
る特徴量の計算時間の総和である。

最大認識時間は、認識結果を出力するまでに抽
出する特徴量の個数に比例するから、＜木＞及
び＜木＞の最大認識時間と総合認識時間とを特
徴量の数で表わすと次の様になる。

＜木＞ 最大認識時間 ２ 総合認識時間 16 ＜木＞ 最大認識時間 ３ 総合認識時間 15 一方、認識の際に問題になる認識時間もの最
大認識時間との総合認識時間を有する（第２
図）。

課題 １： の最大認識時間は、例えば“一定の速度で動
かすことしかできないベルトコンベアー上の認識
対象を、１個毎にカメラで画像として捕られ、そ
のカテゴリを知る“場合に考慮しなければならな
い。なぜならカテゴリの１つを認識するのに要す
る最大時間がベルトコンベアーの動作速度、すな
わちライン全体のコストを決定することになるか
らである。他方、の総合認識時間は、例えば
“数種類の認識対象を一度に画像として捕えられ、
それぞれの位置を知る“場合に考慮しなければな
らない。なぜなら、すべての被写体を認識するま
での総合時間がラインのコストを決定することに
なるからである。

一般に及びのいずれの認識時間を問題にす
るかはシステムの適用（アプリケーシヨン）毎に
異なると考えられる。すなわち認識システムにお
いて判定木構造の認識辞書を作成する際に最大認
識時間と総合認識時間をそれぞれ独立に短縮でき
る手段を設ければ、様々なアプリケーシヨンにお
ける、柔軟で高速な認識を実現できる。そこで判
定木構造の認識辞書を作成する過程において、最
大認識時間と総合認識時間をそれぞれ独立に短縮
できる手段を取り入れることにした（本発明の第
一の特徴）。

課題 ２： さらに、最大認識時間あるいは総合認識時間を
短縮するにはいかなる方法を用いればよいかとい
う問題が有る。第１図の例題の様に、認識対象及
び対象となる特徴量の種類（例えば、単語の文字
数）が少数であれば、考えられるすべての判定木
を作成した後、適当なものを選択するという方法
が最も確実である。しかし認識対象及び特徴量の
種類が多数の場合（例えば、英和辞典のすべての
単語について第１図の様な判定木を作る場合）に
おいては処理時間が極めて莫大になり現実的では
ない。そこで一回の判定木の作成で容易に最大認
識時間あるいは総合認識時間を短縮できる方法が
必要になる。

判定木を自動作成するには一般に次の様な手順
を踏めば良い。

手順１ 複数のカテゴリから成るある上位のクラ
スを分類するための特徴量を、ある評価尺度
で選択する。

手順２ 手順１で選択した特徴量軸上で、上記上
位のクラスを分類し、新しい複数の下位のク
ラスに分解する。

手順３ 手順２の分類後、なおかつ複数のカテゴ
リがクラスを形成していれば、その下位のク
ラスに対して同様な手順を踏み、すべてのカ
テゴリが各々独立すれば完了とする。

すなわち上記の手順１の特徴量の選択方法及び
手順２のクラス分け方法が木の構造を決定する。

そこで最大認識時間及び総合認識時間をそれぞ
れ独立に短縮できる特徴量選択方法を新たに発明
した（本発明の第２の特徴）。第３図を用いてこ
れを説明する。

いま複数のカテゴリから成る上位のクラス
｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝があり、こ
れが特徴量Ｘ軸上で分類され、複数の下位のクラ
ス｛Ａ，Ｂ，Ｃ｝、｛Ｄ，Ｅ，Ｆ｝、｛Ｇ，Ｈ｝に分
解されたとする。このとき分類で生じた各下位の
クラスのカテゴリ数から以後の判定木を仮想す
る。特徴量Ｘから始まるこの仮想判定木の最大
認識時間、すなわち特徴量Ｘから仮想判定木の先
端で最も深い箇所に到達するまでに抽出する特徴
量の数（以後これを最大推定深さと呼ぶ）、ある
いは総合認識時間、すなわち特徴量Ｘから仮想
判定木のすべての先端に到達するまでに抽出する
特徴量の数（以後これを推定ノード数和と呼ぶ）
を特徴量選択の際の評価尺度とする。

最大推定深さが最小の特徴量で常に分類を行え
ば最大認識時間が、また推定ノード総和が最小の
特徴量で常に分類を行えば総合認識時間が、それ
ぞれ小さな判定木を作ることができる。

ここで仮想判定木としては、例えば第３図に示
す様に分類で生じた任意の下位のクラス｛Ｄ，
Ｅ，Ｆ｝に対して、最悪の判定木を仮定すると容
易に最大推定深さ及び推定ノード数和が求まる。
ここで最悪の判定木とは、下位のクラス｛Ｄ，
Ｅ，Ｆ｝に対して以後の判定木作成過程におい
て、次の様な特徴量しか存在しないと仮定した時
の判定木である。

X_EF：ＥとＦは分離できるがＥとＤ及びＦとＤは
分離できない。

X_DE：ＤとＥは分離できるがＤとＦ及びＥとＦは
分離できない。

X_FD：ＦとＤは分離できるがＦとＥ及びＤとＥは
分離できない。

X_EF，X_DE，X_FDの配置においてカテゴリＤ，
Ｅ，Ｆの配置が様々の場合が考えられるが、木の
構造をすべての場合において等しくなる。このと
き、下位のクラス｛DEF｝の最大推定深さは３
となり当該クラスのカテゴリ数と等しくなる。ま
た、下位クラス｛DEF｝の推定ノード数和に関
してはカテゴリＤがX_DE及びX_FDの先端に分岐し
ている。Ｄの「場合の数」を１、そしてＥ及びＦ
の「場合の数」を各々１と考えれば、３つのカテ
ゴリに対して３つの特徴量を抽出する判定木であ
るから、推定ノード数和は３×３＝９となる。す
なわち当該クラスのカテゴリ数の２乗と等しくな
る。

したがつて、複数のカテゴリから成るある上位
のクラスをある特徴量軸上でクラス分けしたとき
に分解されてできた各下位のクラスのカテゴリ数
を｛N₁，N₂…N_K｝とすると、当該特徴量の最大
推定深さ及び最大推定ノード数和は次の様にな
る。

(1) 最大推定深さ max｛N₁｝ １≦ｉ≦Ｋ …(1) (2) 推定ノード数和 _K 〓ⁱ⁼¹ （N₁ ²） …(2) 〔発明の実施例〕 本発明の一実施例を、第７図から第１６図を用
いて説明する。

第４図は、本実施例である。画像認識システム
の全体構成を示している。

(1) 構成 本システムは、光信号を電気信号に変換する
ビデオカメラ１、ビデオカメラ１のアナログ信
号をデジタル信号に変換するＡ／Ｄコンバータ
２、当該コンバータ２より送られるデジタル信
号を格納するイメージメモリ３、当該メモリ３
の内容を演算処理するイメージプロセツサ４、
イメージメモリ３のアクセス制御を行うアドレ
スプロセツサ５、イメージメモリ３及びイメー
ジプロセツサ４及びアドレスプロセツサ５の間
においてデータ及びコントロール信号を転送す
るためのイメージプロセツサバス６、本画像認
識システムを管理するシステムプロセツサ７、
その内部構成要素である中央演算処理装置８、
主記憶装置９、周辺機器との送受信を行う送受
信装置１０、画像認識システムを構築する各要
素間において、データ及びコントロール信号の
転送を行うためのシステムバス１１、イメージ
メモリ３のデジタル信号をアナログ信号に変換
するＤ／Ａコンバータ１２、送受信装置１０か
らのデジタル信号をキヤラクタコードに変換・
表示１、更にＤ／Ａコンバータのアナログ信号
を画像として表示する表示装置１３、外部より
送受信装置１０にデータを入力するキーボード
１４、画像認識システム全体を起動させる際に
必要なデータを格納しておく外部記憶装置１５
より構成されている。

判定木辞書を作成するモジユールは、システ
ムプロセツサ７上のプログラムとして実現され
ている。認識辞書を作成するプログラムは、大
きく２つに分れる。一方は、認識辞書を作成す
るための前データを操作者と会話式に採用する
シヨーイング部、他方は、当該シヨーイング部
で採取したデータから認識辞書を組立てる辞書
組立て部である。第５図にシヨーイング部、第
６図に辞書組立て部の構成図を示す。

シヨーイング部はイメージメモリ３に格納さ
れている画像からイメージプロセツサ４が抽出
する画像（あるいは被写体）の複数の特徴量の
値を記憶する特徴量記憶部１６、上記画像（被
写体）のカテゴリのコードが記憶されているシ
ヨーイングカテゴリコード記憶部１７、認識対
象としているカテゴリ各々の特徴量抽出回数が
記憶されているカテゴリシヨーイング回数記憶
部１８、認識対象としているカテゴリ各々の各
特徴量の平均及び分散値を記憶しているシヨー
イングデータ記憶部１９、シヨーイングカテゴ
リコード記憶部１７及び特徴量記憶部１６及び
シヨーイングデータ記憶部１９及びカテゴリシ
ヨーイング回数記憶部１８の内容から、現在特
徴量を抽出したカテゴリの各特徴量の新しい平
均及び分散値を求め、シヨーイングデータ記憶
部１９に再び格納するシヨーイングデータ算出
部２０より構成されている。辞書組立て部は、
辞書組立て部を初期状態にする初期化部２１、
判定木の節に相当する複数個の同一フオーマツ
トのセルから成る判定木辞書２２、検索する対
象となるセルの番号が記憶されている検索セル
番号記憶部２３、辞書としての情報を書き込む
対象となるセルの番号が記憶されている書き込
みセル番号記憶部２４、検索セル番号のセル
（すなわち判定木の節）の情報から、今後、枝
分れの必要があるか否かと判定するセル検索部
２５、当該セル検索部２５により、枝分れの必
要があると判定されたセルに割当てるための特
徴量を選択する特徴量選択部２６、当該特徴量
選択部２６で必要な分類安全率を記憶している
分類安全率記憶部２７、ここで作成する判定木
構造の認識辞書において、短縮したい認識時間
が、最大認識時間であるのかあるいは総合認識
時間であるのかを示すコードが記憶されている
木構造指定コード記憶部２８、特徴量選択部２
６で出力する特徴量コードを記憶する特徴量コ
ード記憶部２９、当該特徴量コード記憶部２９
及び上記枝分れの必要のあるセル（すなわち判
定木の節）の情報を用いて、新しいセル（判定
木の節）を作成する書き込み部３０から構成さ
れている。

また、第７図に判定木辞書２２のセルの内部
構成を、第８図に特徴量選択部２６の内部構成
を、第９図に特徴量評価値算出部３８の内部構
成を示す。

判定木辞書２２の各セルは、そのセルの上位
のセル（すなわち、上位の節）で抽出した特徴
量と比較するしきい値を記憶するしきい値記憶
部３１、そのセルの上位のセルで抽出した特徴
量が、当該しきい値よりも大であつた場合に該
当するカテゴリの候補数を記憶する候補カテゴ
リ個数記憶部３２、当該候補カテゴリ個数が１
である場合にのみ有効な候補カテゴリのコード
を記憶する該当カテゴリコード記憶部３３、上
記候補カテゴリ個数が２以上である場合に新し
く抽出する特徴量のコードを記憶する抽出特徴
量コード記憶部３４、ここで抽出する特徴量と
比較するしきい値を記憶する下位のセル（すな
わち下位の節）の番号を記憶する子セル番号記
憶部３５、上位のセルで抽出した特徴量がしき
い値31以下であつた場合に比較する当該しきい
値31より小さな次のしきい値を記憶する同位の
セル（すなわち判定木の枝）の番号を記憶する
同位セル番号記憶部３６、上記候補カテゴリの
個数３２が２以上の場合のみ有効な当該候補カ
テゴリコードの配列（すなわち複数のカテゴリ
から成るクラス）を記憶している候補カテゴリ
コード配列記憶部３７より構成されている。

特徴量選択部２６は、ある候補カテゴリコー
ドの配列３７について、特徴量の評価値を算出
する特徴量評価値算出部３８及び３９等、特徴
量評価値算出部３８及び３９等から出力される
特徴量評価値である最大推定深さを記憶する最
大推定深さ記憶部４０及び４０等、同様の推定
ノード数和を記憶する推定ノード数和記憶部４
１及び４３等、各特徴量に対する最大推定深さ
４０，４２等か、あるいは推定ノード数和４
１，４３等が最小になる特徴量コードを出力す
る特徴量評価値比較部４４から構成されてい
る。なお、特徴量評価値算出部、最大推定深さ
記憶部、推定ノード数和記憶部は、第１３図の
特徴量記憶部１６で記憶される特徴量の数に対
応して設ける。

特徴量評価値算出部３８は、候補カテゴリコ
ードの配列３７に対して、特徴量軸上でクラス
分けするためのしきい値を算出するクラス分け
部４５、当該クラス分け部から出力されるしき
い値の配列を記憶するしきい値配列記憶部４
６、当該しきい値によりクラス分けされて生じ
る各クラスに含まれるカテゴリの個数を求める
カテゴリ個数算出部４７、当該しきい値により
クラス分けされて生じる各下位のクラスに含ま
れるカテゴリの個数の配列を記憶するカテゴリ
個数配列記憶部４８、カテゴリの個数の配列４
８からカテゴリの個数の最大値を抽出する最大
推定深さ計算部４９、カテゴリの個列４８から
各カテゴリの個数の２乗和を計算する推定ノー
ド数和計算部５０より構成されている。

(2) 動作 次に動作を説明する。本認識辞書作成方法は
大きく２つの動作から成る。一方は、認識辞書
を作成するための前データを操作者と会話式に
採取するシヨーイング、他方は当該シヨーイン
グ部で採取したデータから認識辞書を組立てる
辞書組立である。

まずシヨーイング部の動作を第５図及び第１
０図を用いて説明する。第１０図はシヨーイン
グ部の動作の流れ図を示したものである。本シ
ステムが起動するとステツプ５１において、操
作者に対して画像の入力を促す文が表示装置１
３に表示され、キー入力待ちとなる。そこで操
作者が、カメラ１（第４図）で認識対象物を撮
映できることを確認した後、キーボード１４か
ら任意のキーコードを入力することにより次の
ステツプに進む。次にステツプ５２では、カメ
ラ１より認識対象物の画像がＡ／Ｄコンパレー
タ２を介してイメージメモリ３に多階長のデジ
タルデータとして記憶され、更に当該イメージ
メモリ３のデジタルデータからイメージプロセ
ツサ４が、イメージメモリ３を２値化した時の
画像の面積や周囲長等の特徴量を抽出し、その
特徴量が特徴量記憶部１６に記憶される。

次にステツプ５３において、操作者に対して
画像のカテゴリのコードの入力を促す文が表示
装置１３に表示され、キー入力待ちとなる。そ
こで操作者が画像のカテゴリコードをキーボー
ド１４より入力し、次のステツプに進む。ここ
で入力されたカテゴリコードはシヨーイングカ
テゴリコード記憶部１７に記憶され、更にシヨ
ーイングカテゴリコード記憶部１７のコードに
対応するカテゴリシヨーイング回数１８が更新
される。

次にステツプ５４において、シヨーイング部
データ算出部２０が特徴量記憶部１６、カテゴ
リシヨーイング回数記憶部１８、シヨーイング
部データ記憶１６及びシヨーイングカテゴリコ
ード記憶部１７の情報から、現在特徴量を抽出
したカテゴリの各特徴量における新しい平均値
と分散値を求め、再びシヨーイングデータ記憶
部１９に記憶される。

次にステツプ５５において操作者に対してシ
ヨーイングを継続するか否かの入力を促する文
が表示装置１３に表示され、キー入力待ちとな
る。そこで操作者のキー入力により、再びシヨ
ーイングを行うか、終了するかが決定する。
尚、ここで登録したカテゴリに関して認識辞書
が作られる。

次に第６図及び第１１図から第１３図を用い
て辞書組立部の動作を説明する。第１１図は辞
書組立て動作の流れ図を示している。シヨーイ
ングによつて操作者が認識を行いたいカテゴリ
すべてについて特徴抽出を行つた後、辞書組立
て部が起動する。即ちステツプ５６において、
操作者に対してクラス分けの安全率の入力を促
する文が表示装置１３に表示され、キー入力待
ちとなる。そこで操作者が適当な値をキーボー
ド１４から入力し、次のステツプに進む。ここ
で入力された値は、クラス分け安全率記憶部２
７に記憶される。なお、クラス分け安全率につ
いては後述する。

次にステツプ５７において、操作者に対して
木構造指定コードの入力を促す文が表示装置１
３に表示され、キー入力待ちとなる。そこで操
作者がφあるいは１を木構造指定コードとして
キーボード１４から入力し、次のステツプに進
む。ここで、入力された木構造指定コードは、
木構造指定コード記憶部２８に記憶される。な
お、木構造指定コードとは、最大認識時間を短
縮するか、あるいは総合認識時間を短縮するか
を決定するコードで、当該コードがφの場合は
最大認識時間、１の場合は総合認識時間をそれ
ぞれ短縮するための判定木を作成する。

次にステツプ５８において、辞書組立て部が
初期化される。すなわち判定木辞書２２のすべ
てのセルについて、しきい値記憶部３１をφ，
φ、候補カテゴリ個数記憶部３２及び下位セル
番号記憶部３５をφクリアし、抽出特徴量コー
ド記憶部３４及び同位セル番号記憶部３６には
実在しない値を代入する（例えば特徴量コード
がφ〜63番まで実在するならば、ここで127を
代入する）。また、検索セル番号記憶部２３に
φ、書き込みセル番号記憶部２４に１を代入す
る。更に、セル番号φのセルの候補カテゴリ個
数として、シヨーイング部で特徴抽出したカテ
ゴリの個数を代入し、また、当該セルの候補カ
テゴリコードの配列３７としてシヨーイング部
で特徴抽出したカテゴリのコードすべてを代入
する。

次にステツプ５９において、セル検索部２５
により未対策のセルが採し出され、その番号が
検索セル番号記憶部２３に記憶される。なお検
索は、検索セル番号記憶部２３に記憶されてい
るセルから、セル番号が増加する方向に順番に
行い現在注目しているセルと書き込みセル番号
記憶部２４に記憶されているセルとが一致した
時、判定木辞書組立て部の動作が終了する。こ
こで上記の未対策のセルとは抽出特徴量コード
が実在せず、かつ、候補カテゴリ個数が２以上
であるセルを言う。

次にステツプ６０において特徴量選択部２６
により当該未対策のセルの複数の候補カテゴリ
をクラス分けするための特徴量が選択され、特
徴量コード記憶部２９に記憶される。すなわち
第８図に示す様に各特徴量評価値算出部（３８
あるいは３９等）によつて求められた特徴量の
評価値である最大推定深さ（４０あるいは４３
等）、あるいは推定ノード数和（４１あるいは
４３等）が最小の特徴量コードが特徴量評価値
比較部４４により出力される。なお木構造指定
コード記憶部２８の内容が「φ」の場合は、最
大推定深さ、「１」の場合は推定ノード数和が
それぞれ最小の特徴量コードが出力される。ま
た特徴量評価値算出部（３８あるいは３９等）
の内部構成を第９図に示し、その動作の流れ図
を第１２図に示した。以下詳細に特徴量評価値
算出部の動作を説明する。各特徴量評価値算出
部は、対象とする特徴量が異るだけであり、動
作はすべて第１２図の流れ図に従う。また内部
構成も第９図に示すものと等しい。特徴量評価
値算出部は、まずステツプ６２でクラス分け部
４５により候補カテゴリ（例えば
｛ABCDEFGH｝）を対象とする特徴量軸上で
クラス分け安全率２７のもとでクラス分けし、
しきい値を算出する。しきい値は複数個発生
し、しきい値配列記憶部４６に記憶部される。

次にステツプ６３で、カテゴリ個数算出部４
７により、しきい値配列記憶部４６に記憶され
ているしきい値（例えばカテゴリＣとＤの間の
しきい値T_CD等）でクラス分けされて生じた各
下位のクラスのカテゴリ数を求め、カテゴリ個
数配列記憶部４８に記憶される（例えば、
T_CD，T_EF，T_FGにより、｛ABC｝、｛DE｝、｛Ｆ｝、
｛GH｝なる下位のクラスが生じれば、カテゴ
リ個数配列は（３、２、１、２）となる。

次にステツプ６４で最大推定深さ算出部４９
により、カテゴリ個数配列４８の最大要素（第
９図の例では、３）が抽出され、最大深さ記憶
部４０に記憶される。次にステツプ６５で推定
ノード数和算出部５０によりカテゴリ個数配列
４８の各要素の２乗和（第９図の例では、3²＋
2²＋１＋2²＝18）が計算され、推定ノード数和
記憶部４１に記憶される。以上が特徴量選択部
２６の動作である。

次に第１１図に戻りステツプ６１でセル書き
込み部３０により検索セル番号２３に対応する
セルの候補カテゴリから成るクラスを特徴量記
憶部２９に記憶されている特徴量軸上で改めて
クラス分けし、書き込みセル番号記憶部２４が
記憶されているセルから番号が増加する方向に
新しいセルが作られる。第１３図を用いてセル
書き込み部３０の動作の流れを説明する。

セル書き込み部３０ではまずステツプ６６
で、検索セル番号２３に対応するセルの候補カ
テゴリ配列３７を、特徴量コード２９に対応す
る特徴量軸上でクラス分けを行う。

次にステツプ６７において検索セル番号２３
に対応するセルの抽出特徴量コード記憶部３４
に、特徴量コード記憶部２９の内容をコピーす
る。次にステツプ６８において検索セル番号２
３に対応するセルの下位セル番号記憶部３５
に、書き込みセル番号記憶部２４の内容をコピ
ーする。

次にステツプ６９から７４までを、クラス分
けで得られたしきい値の個数よりも１回多い回
数だけ繰返す。ステツプ６９ではクラス分けで
得られたしきい値を、その大なる順に、書き込
みセル番号２４に対応するセルのしきい値記憶
部３１へコピーする。尚、（しきい値数＋１）
回目のループにおいては、しきい値は記入しな
い。次にステツプ７０において、今回のループ
のしきい値と、前回のループの間に存在するカ
テゴリのコードを、書き込みセル番号２４に対
応するセルの候補カテゴリコード配列記憶部３
７にコピーする。なお前回のループのしきい値
が存在しない場合、すなわち最初のループにお
いては、前回のしきい値は無限大と考え、ま
た、今回のしきい値が存在しない場合、すなわ
ち最後のループにおいては、今回のしきい値は
無限小と考える。

次にステツプ７１において候補カテゴリの個
数を書き込みセル番号２４に対応するセルの候
補カテゴリ個数記憶部３２に記入する。次にス
テツプ７２において書き込みセル番号２４に対
応するセルの同位セル番号記憶部３６に、書き
込みセル番号２４より「１」つ大きい値を記入
する。なお、最後のループでは同位セル番号は
記入しない。次にステツプ７３において、書き
込みセル番号２４に対応するセルの候補カテゴ
リ個数３２が１である場合にのみ、該当カテゴ
リコード記憶部３３に候補カテゴリコードをコ
ピーする。次にステツプ７４において書き込み
セル番号記憶部２４の内容を更新する。次にス
テツプ７５においてループ回数がステツプ６６
で求めたしきい値の数より「１」大きい値にま
で達した時、セル書き込み部３０の動作を終了
させる。

セル書き込み部３０の動作が終了すれば再び
第１１図のステツプ５９に戻り、以下同様な動
作を繰返すことにより、認識辞書が作成され
る。以上が本認識辞書作成方法の実施例であ
る。第１４図に参考のため、本認識辞書の使用
方法の流れ図を示した。以下これを用いて、本
認識辞書の使用方法を説明する。

まずステツプ７６において検策セル番号を先
頭のφにする。次にステツプ７７において当該
検索セル番号に対応するセルの抽出特徴量コー
ド３４を判定し、当該特徴量コード３４が実在
する値であればステツプ７８へ、実在しない値
であればステツプ８２へ、それぞれ進む。ステ
ツプ７８では、検索セル番号に対応するセルの
抽出特徴量コード３４に対応する特徴量を入力
した画像から抽出する。次にステツプ７９で検
索セル番号として当該検索セル番号に対応する
セルの下位セル番号を代入する。次にステツプ
８０においてステツプ７９で抽出した特徴量の
値が検索セル番号に対応するセルのしきい値３
１よりも大であるが、あるいは検索セル番号に
対応するセルの同位セル番号が実在しないもの
であればステツプ７７へ、そうでなければステ
ツプ８１へ進む。ステツプ８１では検索セル番
号として、当該検索セル番号に対応するセルの
同位セル番号を代入し、ステツプ７９に進む。
ステツプ８２では、検索セルの番号に対応する
セルの情報を出力する。すなわち、候補カテゴ
リ個数３２が１であれば該当カテゴリコードを
出力する。また、当該候補カテゴリ個数３２が
２以上であればリジエクトする。

〔変形実施例の説明〕

画像から抽出する特徴量の計算時間はその種類
によつて若干のばらつきがある。本発明では、そ
の特徴量の計算時間のばらつきも考慮して、判定
木を作ることができる。本実施例においては、選
択の対象となる特徴量の計算時間は一様であると
仮定して、特徴量の評価値は(1)及び(2)式のものを
用いた。ここで、選択の対象となる特徴量の計算
時間の平均値を１とした時の特徴量コードｋを有
する特徴量の計算時間をＴ〔ｋ〕とすると、特徴
量の計算時間のばらつきを考慮した特徴量評価値
は次の様になる。

(1) 最大推定深さ max｛Ni−１＋Ｔ〔ｋ〕｝ １≦ｉ≦Ｋ …(1)′ (2) 推定ノード数和 _K 〓ⁱ⁼¹ Ni^*（Ni−１＋Ｔ〔ｋ〕） …(2)′ 但し、 Ｋ：クラス分けで生じた下位クラスの個数 ｉ：クラス分けで生じたｉ番目の下位クラス Ni：クラス分けで生じたｉ番目のカテゴリ個
数 すなわち仮定した判定木では、平均的な計算
時間を要する特徴量を使用するものとしてい
る。

画像から抽出する特徴量の計算時間がその種
類によつてばらつきが有つても、高速な認識を
実現する判定木が容易に作成できる。

〔発明の効果〕

本発明によれば画像認識システムにおいて認識
対象を認識するために使用する認識辞書を自動作
成でき、しかも高速な認識が実現できる。

第１５図から第１７図までを用いて本発明の効
果を具体的に説明する。

第１５図及び第１６図は、第１図の例と同様の
単語識別の判定木であるが、第１５図は最大推定
深さ（ここでは下位のクラスのカテゴリ数の最大
値）、第１６図は推定ノード数和（ここでは下位
のクラスのカテゴリ数の２乗和）が最小になる文
字で常に分類したものである。対象とした単語
は、英和辞典の頭文字がＺの単語すべてである。
また第１７図に従来の分離度を用いた判定木の上
位部分を示した。なお分離度の計算に際しては、
アルフアベツト順に大きなコードを用つものと
し、また空白は「Ｚ」の次に大きなコードである
とした（例えばａ＝０、ｂ＝１、…Ｚ＝25）。

第１５図から第１７図によると、各々の最大認
識時間及び総合認識時間を抽出する文字数で表わ
すと次の様になる。

(1) 最大推定深さの場合（第１５図） 最大認識時間 ４ 総合認識時間 91 (2) 推定ノード数和の場合（第１６図） 最大認識時間 ４ 総合認識時間 81 (3) 従来方法の場合（第１７図） 最大認識時間 ７以上14以内 総合認識時間 227以上 （38単語中９単語識別するのに38文字を抽出
しており、残りの27文字がすべて７文字の
抽出で識別できるとした） したがつて、本例に関しては従来方法に比較し
て、本発明の最大認識時間は1/2〜1/3、総合認識
時間は1/3程度となる。選択の対象となる特徴量
の数が更に増加すれば、従来方法に比較して更に
認識時間の短縮化が達成される効果がある。

【図面の簡単な説明】

第１図は単語識別の判定木例、第２図は判定木
による認識で問題になる認識時間の説明図、第３
図は特徴量選択方法の概念図、第４図は本発明の
実施対象である画像認識システムの全体構成図、
第５図は本実施例のシヨーイング部の内部構成、
第６図は本実施例の認識辞書組立て部の内部構
成、第７図は上認識辞書を構成するセルの内部構
成、第８図は上記辞書組立て部の一部である特徴
量選択部の内部構成、第９図は上記特徴量選択部
の一部である特徴量評価値算出部の内部構成、第
１０図はシヨーイング部の動作流れ図、第１１図
は認識辞書組立て部の動作流れ図、第１２図は特
徴量評価値算出部の動作流れ図、第１３図は上記
認識辞書組立て部のセル書き込み部の動作流れ
図、第１４図は上記認識辞書の使用方法の流れ
図、第１５図は最大推定深さによる単語識別の判
定木、第１６図は推定ノード数和による単語識別
の判定木、第１７図は従来方法による単語識別の
判定木の上位部分。 ３７…候補カテゴリの配列記憶部、３８…特徴
量評価値算出部、４５…クラス分け部、４６…し
きい値配列記憶部、４７…カテゴリ数配列算出
部、４８…しきい値配列記憶部、４９…最大推定
深さ算出部、５０…推定ノード数和算出部、４０
…最大推定深さ記憶部、４１…推定ノード数和記
憶部。

Claims (1)

1. 【特許請求の範囲】 １ 特徴量の抽出及び判定の順序を記載した判定
   木認識辞書を、対象情報の入力により作成する情
   報認識システムにおいて、 前記対象情報の１つを認識するのに要する時間
   の最大値（以下、最大認識時間と称す）及び前記
   対象情報のすべてを認識するのに要する時間（以
   下、総合認識時間と称す）を各々独立に短縮する
   ための手段と、 前記最大認識時間及び前記総合認識時間のうち
   いずれの認識時間を短縮するかを選択する手段と
   を設けたことを特徴とする情報認識システム。 ２ 特許請求の範囲第１項記載の情報認識システ
   ムにおける前記判定木認識辞書の作成は、 前記抽出した後に生ずる新たな対象情報数を推
   測することによつて前記最大認識時間及び前記総
   合認識時間を仮想的に求め、前記特徴量として最
   小値を採用することに特徴を有する情報認識シス
   テム。