JPH1145340A

JPH1145340A - 温度計符号化を用いた高速パターン認識マンハッタン距離計算

Info

Publication number: JPH1145340A
Application number: JP10172197A
Authority: JP
Inventors: Rodney Gauk L; エル・ロドニー・ゴーク; Wei Han I; イー−ウェイ・ハン; Lee Deeley; デ−レイ・リー
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 1997-06-06
Filing date: 1998-06-03
Publication date: 1999-02-16
Also published as: TW363175B; CN1201956A

Abstract

(57)【要約】【課題】ハードウエアの処理効率を高めた高速パター
ン認識を提供する。【解決手段】パターン照合では、２つのパターンが異
なる度合いを測定する「距離関数」の計算を必要とす
る。この計算には、「差の絶対値の和」または「マンハ
ッタン距離」関数を用いる。短い成分を有するベクトル
のための高速マンハッタン距離関数を実行すると、入力
特徴ベクトルおよび既知の特徴ベクトルを温度計符号形
態に変換する。次に、２つの温度計符号ベクトルのＸＯ
Ｒを取ることにより、これらの差を計算する。次に、Ｘ
ＯＲの結果における値「１」のビットを数えることによ
り、マンハッタン距離を算出する。２つの温度計符号ベ
クトルをビット・スライス形態で格納することにより、
並列計算の利用が可能となる。二進符号特徴ベクトルを
ビット・スライス形態で格納することにより、必要なメ
モリ量を減らし、二進符号から温度計符号への変換を利
用することができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、一般的に、パター
ン認識方法および装置に関し、更に特定すれば、高速マ
ンハッタン距離法(fast Manhattan Distance method)に
関するものである。

【０００２】

【従来の技術】パターン認識の用途では、２つのパター
ンが相違する度合いを測定する「距離関数」の計算を頻
繁に必要とする。例えば、未知のパターンを分類するに
は、この未知のパターンから「辞書」の中にあるあらゆ
る既知のパターン、即ち、「テンプレート」までの距離
を測定し、最も近いテンプレートを選択することによっ
て行うことができる。各テンプレートは、既知の「パタ
ーン・クラス」を表す。選択されたテンプレートのクラ
スが、パターン照合処理の結果となる。実際のパターン
認識アルゴリズムはこれよりも大幅に複雑であるが、既
知のパターンおよび未知のパターン間の距離関数の計算
に、実行時間の大部分を消費することは、尚も共通して
いる。また、既知のパターンの辞書が使用メモリの大部
分を占めることも共通している。その結果、距離関数を
高速に計算し、しかもパターン辞書をメモリ内に簡潔に
格納可能とするが、多くの場合重要となる。

【０００３】典型的に、各パターンは、「特徴(featur
e) 」または「エレメント」と呼ばれる多数の成分を含
むベクトルである。一般的に用いられている距離関数
は、「差の絶対値の和」であり、「マンハッタン距離(M
anhattan Distance)」としても知られている。これを計
算するには、２つのパターン・ベクトルの対応するエレ
メント間の差の絶対値を合計する。したがって、既知の
ベクトルＫ［１，．．．，ｎ］および入力ベクトルＩ
［１，．．．，ｎ］間の距離は、以下の式で表される。

【０００４】

【数１】特徴のサイズは、異なる用途では異なり、用途によって
は極端に短い場合もあり得る。また、用途によっては、
２ビット無符号の特徴の長いベクトルを処理するため
に、効率的な解法が必要な場合がある。

【０００５】短い数値に算術計算を行う最も一般的な従
来技術の方法は、各数値を目標の機械のＡＬＵの幅に拡
張し、拡張した数値を一度に１つずつ（あるいは、単一
命令多データ［ＳＩＭＤ］プロセッサ(single-instruct
ion-multiple-data processor)の場合には、処理素子即
ちＰＥ当たり１つ）処理するというものである。例え
ば、２ビット符号なしの特徴には、各々、１４個の０を
前に追加して、１６ビット符号なし整数を形成し、１６
ビット算術演算論理装置（ＡＬＵ：arithmetic logic u
nit ）において処理する。

【０００６】

【発明が解決しようとする課題】この従来技術の方法に
は、２つの弱点がある。第１に、高位ビット（この場合
では、１６ビットの内１４ビット）が無駄であるので、
コンピュータの算術演算回路，レジスタ，およびデータ
経路の使用が非常に非効率的となる。第２に、処理のた
めに用いられるアンパック・データ・フォーマット(unp
acked data format)および効率的なメモリ利用に必要な
パック・データ・フォーマット間には、基本的な不整合
がある。既知のパターン辞書をアンパック形態で格納す
ると（例えば、各２ビットの特徴に対して、恐らく８ビ
ットまたは１６ビットを用いる）、処理は単純明解であ
る（何故なら、伸長が不要なので）が、メモリの消費は
必要量よりも数倍多くなる。この追加のメモリが、組込
型システム(embedded system) では法外な費用増となる
可能性がある。一方、辞書をより簡潔に格納すると、各
絶対値−差−および−蓄積処理に先立つデータ・アンパ
ック処理(data unpacking operation)によって、実行時
間が長くなる。これら相反する要因が複合化して、処理
用ハードウエアの使用効率は既に低下しており、その結
果処理が容認できない程遅くなる場合がある。

【０００７】

【課題を解決するための手段】本発明は、特に、大量の
エレメントで表現され、各エレメントが少数のビットで
表現されるパターンを処理する場合に適している。これ
らの用途では、各エレメントは、２ビットまたは３ビッ
ト量で表現することができる。本発明は、処理システム
が許すあらゆるデータ・サイズのベクトルに、エレメン
トをパックするので便利である。その結果、単純なプロ
セッサが、数個のエレメントを平行して処理するように
見える。また、既知のパターン・ベクトルも、同様に、
記憶装置内にパックすることができ、しかも使用に先立
つ操作は最少または不要となる。開示する方法は高速で
あり、特定のデータ・プロセッサのデータ経路サイズに
容易に合わせることができ、既知ベクトルを小さなメモ
リに効率的に格納可能とするものである。

【０００８】本発明の特徴および利点は、以下の詳細な
説明を添付図面に関連付けることにより、一層明確に理
解されよう。図面において、同様の参照番号は、同様の
および対応する部分を引用する。

【０００９】

【発明の実施の形態】図１は、ここに開示する発明によ
るパターン処理方法１００を、フロー・チャート形態で
示す。

【００１０】具体的に図１を参照すると、方法１００は
ステップ１０２において開始され、ここで、既知のパタ
ーンのライブラリと照合すべきパターンを獲得する。こ
のパターンは、マイクロフォン，ビデオ・カメラ，光学
スキャナ，ペン・スタイラス(pen stylus)等の出力とす
ることができる。次に、方法１００は、ステップ１０４
において、獲得したパターンを特徴付ける特徴(featur
e) を抽出する。ステップ１０４の出力は、抽出された
特徴、即ち、入力ベクトルを特徴付けるエレメントを含
むベクトルである。典型的に、特定形式のパターン（漢
字、英語等）、およびパターンをサンプリングする特定
の媒体（光学スキャナ，マイクロフォン等）によって、
特徴付けを行う特徴(characteristic feature)を抽出す
るために用いられる基準が決定される。漢字の特徴抽出
アルゴリズムの一例について、図２および図３に関連付
けて以下で説明する。次に、方法１００は、入力ベクト
ルを、既知パターンの辞書からの１つ以上の既知ベクト
ルと比較する。方法１００は、これらの２つの間の「距
離」即ち非類似度(dissimilarity) に値を割り当てる。
マンハッタン距離関数は、２つのベクトル間の非類似度
の尺度として有用なものの１つである。最後に、方法１
００は、ステップ１０８において、入力ベクトルに最も
類似するパターンを選択する。

【００１１】図２は、英単語の"other" に対応する漢字
２００を示す。漢字は、その難度の観点および言語を使
用する人口の観点双方から、パターン認識の課題として
は特に重要である。図２に示すように、漢字は、比較的
多数のストロークから成り、各々比較的高い空間的自由
度を有する。

【００１２】図３は、図２に示した文字の画素アレイ表
現３００を表したものである。ここでは、"other" の漢
字の光学画像が、二進値の１２ｘ１２マトリクスに変換
されている。１２ｘ１２マトリクス内の各位置は、画像
内の対応する空間位置即ち画素を表す。特定のマトリク
ス位置における１は、当該マトリクス位置に割り当てら
れた特定の空間点における、暗い画素（即ち、文字を形
成するインク・トレースの存在）を示す。逆に、特定の
マトリクス位置において０があるのは、当該マトリクス
位置に割り当てられた特定の空間点における、明るい画
素（即ち、インク・トレースがない）を示す。経験的
に、画像の領域の縁から、予め設定された境界内の数点
における最初の１までの距離をサンプルすることは、有
効な特徴抽出技法であることがわかっている。特徴抽出
ステップ１０４（図１に示す）の処理を例示する目的の
ために、表現３００は、左縁から右方向に４画素以内の
２点までの距離、右縁から左方向に４画素以内の２点ま
での距離、上縁から４画素以内の２点までの距離、およ
び下縁から上方向に４画素内の２点までの距離をサンプ
ルする。図示した方法は、インク・トレースが縁（即
ち、最初の画素）上には決して存在しないことを想定し
ており、存在する場合はそれを無視する。更に、４画素
の境界内にインク・トレースが検出されない場合、０の
距離を記録する。かかる方法は、８つの２ビットの特徴
即ちエレメントから成る、パターン・ベクトルを生成す
る。図示の例では、入力ベクトル（ｘ１，ｘ２，ｘ３，
ｘ４，ｙ１，ｙ２，ｙ３，ｙ４）が値（３，１，０，
２，３，２，０，１）を有する。

【００１３】本発明の一実施例は、「温度計符号(therm
ometer code)」の使用を基本とする。温度計符号の基本
的な考え方は新しいものではない。実際に、デジタル・
バー・グラフ表示を読むときはいつでも温度計符号の使
用が見られる。表示のセグメントは、表示されている量
の温度計符号表現のビットに対応する。例えば、２ビッ
ト符号なし二進整数は、以下のように、３ビット温度計
符号に対応する。

【００１４】

【表１】同様に、３ビット符号なし二進整数は、以下のように、
７ビット温度計符号に対応する。

【００１５】

【表２】一般的に、符号なし整数ｘのｎビットの温度計符号表現
は、ｎ−ｘ個の０、およびそれに続くｘ個の１を含む。

【００１６】また、オフセット温度計符号を用いて、負
数や、０以外のどこかから開始する区間の範囲の数値を
処理することも可能である。例えば、区間［−２，＋
６］の中の整数は、以下のオフセット温度計符号によっ
て表すことができる。

【００１７】

【表３】一般的に、値ｘのｎビット・オフセット温度計符号表現
は、ｎ−ｘ＋ｓ個の０、およびそれに続くｘ−ｓ個の１
を含み、ここでｓは区間の開始値（上述の例では、−
２）である。

【００１８】図４は、図１に示したステップ１０６の第
１実施例４００をフロー・チャート形態で示す。概略的
に、第１実施例４００は、２つのベクトル、即ち、入力
ベクトルおよび既知ベクトル間のマンハッタン距離を計
算し、その際これら２つのベクトルのパックされた温度
計符号表現間のハミング距離を計算する。最初に、第１
実施例４００は、ステップ４０２およびステップ４０４
において、それぞれ、入力ベクトルおよび既知ベクトル
を温度計符号フォーマットに変換する。ステップ４０
２，４０４の一方または双方は、入力ベクトルまたは既
知ベクトルが既に温度計符号フォーマットになっている
場合、省略することができる。ステップ４０２およびス
テップ４０４については、図５に関連付けて以下で更に
詳細に説明する。次に、ステップ４０６において、２つ
のベクトルの温度計符号表現のＸＯＲを取る。ＸＯＲを
取った結果における１の数を数える。これは、２つのベ
クトルの対応するエレメント間の距離の絶対値の和を示
す。最後に、第１実施例４００は、ステップ４１０にお
いて、入力ベクトルと比較すべき既知ベクトルがまだあ
るか否かについて判定を行う。入力ベクトルと比較すべ
きパターンが未だある場合、第１実施例４００はステッ
プ４０４に戻り、追加のパターンを用いて処理を継続す
る。入力ベクトルと比較すべきパターンがもはやない場
合、第１実施例４００は終了する。

【００１９】図５は、図４に示したステップ４０２また
はステップ４０４の図式表現を示す。ここでは、１６個
の２ビット符号なし二進量を、温度計符号フォーマット
の１６個の３ビット量に変換する。１６個の２ビット量
は、「ビット・スライス(bit-slice) 」される。即ち、
各量の最下位ビット（ＬＳＢ）は各々Ｂ₀ に格納され
る。同様に、各量の最上位ビット（ＭＳＢ）は各々Ｂ₁
に格納される。好適実施例では、Ｂ₀ およびＢ₁ は、そ
の幅が第１実施例４００を実行する処理システムのデー
タ経路に等しい。その結果、処理システムは、第１実施
例４００を１回繰り返す毎に、１６回のエレメント変換
および比較を行うことができる。実施例によっては、い
ずれかの処理システムの単一のレジスタに格納可能な
量、またはデータ・バス上を伝達可能な量よりも、各パ
ターン毎に処理するエレメントの方が多い場合もある。
これらの場合、ステップ４１０の前に判断ステップを設
けてステップ４０２に戻るようにして、いくつかの断片
に区分されたベクトルの処理に対処すればよい。

【００２０】２ビット符号なし二進表現を３ビット温度
計符号表現に変換する場合、Ｂ₀ のＩ番目のビットおよ
びＢ₁ のＩ番目のビットを論理的に結合し、Ｔ₀ のＩ番
目のビット、Ｔ₁ のＩ番目のビット、およびＴ₂ のＩ番
目のビットを発生する。ここで、Ｉは０ないし１５の範
囲の整数インデックスである。温度計符号エレメントも
ビット・スライスされる。即ち、各量の各ＬＳＢをＴ₀
に格納し、各量の各中間ビットをＴ₁ に格納し、各量の
各ＭＳＢをＴ₂ に格納する。Ｔ₀ はＢ₀ とＢ₁のビット
毎の論理ＯＲである。Ｔ₁ はＢ₁ と等しい。Ｔ₂ は、Ｂ
₀ とＢ₁ のビット毎の論理ＡＮＤである。

【００２１】図５は２ビット符号なし二進表現から３ビ
ット温度計符号表現への変換を示すが、開示する発明
は、これよりもサイズが大きいデータ幅でも動作可能で
ある。当業者は、より大きなサイズのデータをより大き
なサイズの温度計符号に変換することができよう。逆
に、データは、ビット・スライスする必要がない。これ
らの場合、エレメントの温度計符号表現は単独に処理可
能であり、あるいは線型的にメモリ素子にパックするこ
とができる。後者の場合、５つの３ビット量（Ａないし
Ｅ）を、１つの１６ビット・レジスタにパックすること
ができ、無駄なビットは１つのみである（Ａ１，Ａ２，
Ａ３，Ｂ１，Ｂ２，Ｂ３，Ｃ１，Ｃ２，Ｃ３，Ｄ１，Ｄ
２，Ｄ３，Ｅ１，Ｅ２，Ｅ３，Ｘ）。ここでは、上述の
変換アルゴリズムを修正し、個々の温度計ビットを特定
のビット位置に配置しなければならない。

【００２２】図６は、開示する発明の説明において有用
な例を図式形態で示す。ここでは、十進数（３，１，
３，１，０，０，１，２）という入力ベクトルを十進数
（１，３，０，１，２，３，２，１）という既知ベクト
ルと比較する。これら２つのベクトル間の正しいマンハ
ッタン距離は、

【００２３】

【数２】で表され、十進数の１４となる。

【００２４】図７は、図６に示したデータを用いた、図
４に示した第１実施例４００の処理を図式形態で示す。
ここでは、８つの入力エレメントを８つの既知エレメン
トと比較する。上述のように、Ｔ₀ ，Ｔ₁ ，Ｔ₂ は各
々、各エレメントの温度計符号表現の異なる１ビットを
含む。これら８つのエレメント対のＸＯＲを取り、中間
結果を生成する。この中間結果は、対応するエレメント
間の差の絶対値を表す。図示の例では、ＸＯＲの結果
は、（１１１００１００），（１１１０１１１１），
（００１０１１００）となる。ＸＯＲの結果における１
の数を数えて、２つのベクトル間のマンハッタン距離を
判定する。この例では、１の数は１４個であり、図６と
の関連で先に述べた数に等しい。

【００２５】図８は、図１に示したステップ１０６の第
２実施例８００を、フロー・チャート形態で示す。概略
的に、第２実施例８００は、排他的論理和論理演算（Ｘ
ＯＲ）を用いることによって、２つのベクトル、即ち、
入力ベクトルおよび既知ベクトル間のマンハッタン距離
を計算するものである。この論理演算は、２つの場合を
除いて、ベクトル全てに渡って合計した、２つのベクト
ル間の差の絶対値を正確に判定する。次いで、これら２
つの場合を識別し、正しいベクトルを以前の結果に適用
する。最後に、個々のＸＯＲ結果を合計することによ
り、２つのベクトルの対応するエレメント間の差の絶対
値の和を計算する。

【００２６】２ビット二進エレメントから成るベクトル
を考えると、２つの対応するエレメント間の差の絶対値
は、２つの場合を除いて、２つのエレメントについて実
行したＸＯＲ演算に等しい。ＸＯＲ演算は、２つのエレ
メントが（０１，１０）または（１０，０１）に等しい
場合、２つのエレメント間の差の絶対値に等しくならな
い。これら２つの場合、ＸＯＲを取った出力は、正しい
マンハッタン距離は（０１）の代わりに、正しくないベ
クトル・エレメント（１１）を生成する。したがって、
このＸＯＲ出力のＭＳＢを０に変化させ、正しい距離
（０１）を生成しなければならない。以下で説明するよ
うに、第２実施例８００はこれらエラー状態を検出し、
最終結果を出力する前に、それらを補正するものであ
る。

【００２７】引き続き図８を参照する。最初に、ステッ
プ８０２において、入力ベクトルのＭＳＢの、同じエレ
メントの対応する最下位ビット（ＬＳＢ）とのＸＯＲを
取る。この中間結果は、入力ベクトルにおいて、（０
１）または（１０）という形態のエレメントを識別す
る。この中間結果は以下で用いる。次に、ステップ８０
４において、入力ベクトルおよび既知ベクトルのＸＯＲ
を取る。この結果から、上述の２つの場合を除いて、入
力ベクトルおよび既知ベクトルの対応するエレメント間
の距離の絶対値が生成される。

【００２８】ステップ８０６において、第２実施例８０
０は、ＸＯＲ計算値がマンハッタン距離とは異なる２つ
の場合を識別する。論理的に、ステップ８０６は、エラ
ー補正ベクトルＥバーを計算する。ここで、

【００２９】

【数３】となる。

【００３０】上記式における第１および第２ＸＯＲ演算
は、ステップ８０４において行われる。上記式における
第３のＸＯＲ演算はステップ８０２において行われる。

【００３１】ステップ８０８において、エラー補正ベク
トルＥバーと、入力ベクトルのＭＳＢ、Ｉ１とのＸＯＲ
を取る。上述のように、結果のＭＳＢビットのいくつか
を論理０に変更する。次に、第２実施例８００は、ステ
ップ８１０において、ベクトル・エレメント対間の個々
の差を合計する。２ビット二進方式の場合、第２実施例
８００は、結果のＭＳＢ間の１の数を数え、結果のＬＳ
Ｂ間の１の数を数え、これら２つの数を、それらのビッ
ト桁数(bit significance)の値と乗算する。２ビット二
進方式の場合、ＭＳＢ間の１の数を２と乗算し、ＬＳＢ
間の１の数を単純に加算する。ステップ８０８では、こ
れら２つの数を加算し、マンハッタン距離を生成する。

【００３２】最後に、第２実施例８００は、ステップ８
１２において、入力ベクトルと比較すべき既知ベクトル
が未だあるか否かについて判定を行う。入力ベクトルと
比較すべきパターンが未だある場合、第２実施例８００
はステップ８０４に戻り、追加のパターンを用いて処理
を継続する。入力ベクトルと比較すべきパターンがもは
やない場合、第２実施例８００は終了する。

【００３３】図９は、図６に示したデータを用いた、図
８に示した第２実施例の処理を、図式形態で示す。先の
説明から、２つのベクトル間の正しいマンハッタン距離
は、

【００３４】

【数４】で求められ、十進数の１４であることを思い出された
い。入力ベクトルのＭＳＢおよびＬＳＢは、それぞれ、
二進数の（１０１００００１）および（１１１１００１
０）である。既知のベクトルのＭＳＢおよびＬＳＢは、
それぞれ、二進数の（０１００１１１０）および（１１
０１０１０１）である。最初に、第２実施例８００は、
ＭＳＢおよびＬＳＢが入力ベクトルの各エレメントにお
いて異なる場合を判定する。上述のように、入力ベクト
ルのＭＳＢおよびＬＳＢ間でＸＯＲ演算を行うことによ
って、この関数が得られる。この例では、入力ベクトル
の排他的論理和関数は（０１０１００１１）となる。第
２、第４、第７、および第８エレメントが、潜在的な問
題箇所である。何故なら、これらのエレメントは（０
１）または（１０）のいずれかに対応するからである。

【００３５】次に、第２実施例８００は、入力ベクトル
および既知ベクトルのＸＯＲを取ることによって、２つ
のベクトルの「ほぼ正しい」差を生成する。この例で
は、これら２つのベクトルのＸＯＲは、（１１１０１１
１１），（００１００１１１）となる。次に、第２実施
例８００は、正しくないエレメントがどれであるのかを
突き止める。最初に、第２実施例８００は、現在の結果
のＭＳＢおよびＬＳＢのＡＮＤを取る。この例では、中
間結果ベクトル（１１１０１１１１），（００１００１
１１）のＭＳＢおよびＬＳＢのＡＮＤ関数は、（００１
００１１１）となる。ここでは、第３エレメントおよび
第６ないし第８エレメントが、中間結果としての（１
１）に対応するので、これらのエレメントは潜在的な問
題箇所である。補正する必要のある中間結果は、値（１
１）を有し、その入力ベクトル・エレメントが（０１）
または（１０）のいずれかのものである。したがって、
先に生成したベクトル（００１００１１１）およびベク
トル（０１０１００１１）のＡＮＤを取って、補正ベク
トルＥバー（００００００１１）を生成する。この補正
ベクトルを、中間結果（１１１０１１１１）のＭＳＢと
ＸＯＲを取り、最後の２ビットを２つの論理０に変更す
る。その結果、入力ベクトルおよび既知ベクトルの補正
後の差は、（１１１０１１００），（００１００１１
１）となる。

【００３６】次に、第２実施例８００は、補正した差ベ
クトルにおける１を数え、それらの桁数に応じて１に重
み付けを行う。この例では、ＭＳＢ部分に５つの１があ
り、ＬＳＢ部分には４つの１がある。ＭＳＢ部分の１
に、ＬＳＢ部分の１よりも２倍の重み付けを行うことに
より、最終的な正しいマンハッタン距離である１４が得
られる。

【００３７】図１０は、汎用コンピュータ２０を示すブ
ロック図である。汎用コンピュータ２０は、コンピュー
タ・プロセッサ２２，およびバス２６によって接続され
たメモリ２４を有する。メモリ２４は、ＤＲＡＭ，ＳＲ
ＡＭ，ＲＯＭ，ＦＬＡＳＨ，ＥＥＰＲＯＭ，およびバブ
ル・メモリのような、比較的高速な機械読み取り可能媒
体を含む。更に、バスには、二次記憶装置３０，外部記
憶装置３２，モニタ３４のような出力装置，キーボード
（マウス付き）３６のような入力装置，およびプリンタ
３８が接続されている。二次記憶装置３０は、ハード・
ディスク・ドライブ，磁気ドラム，およびバブル・メモ
リのような機械読み取り可能媒体を含む。外部記憶装置
３２は、フロッピ・ディスク，リムーバブル・ハード・
ドライブ，磁気テープ，ＣＤ−ＲＯＭ，および他のコン
ピュータをも含み、通信ラインを介して接続することが
できる。二次記憶装置３０および外部記憶装置３２間に
おいてここで定めた区別は、主に本発明を記載する際の
都合によるものである。したがって、これらの装置間に
は、かなりの機能的重複があることは認められよう。パ
ターン照合，特徴抽出，および特徴化ソフトウエアのよ
うなコンピュータ・ソフトウエア３３の実行可能バージ
ョン、およびユーザ・プログラムは、外部記憶装置３２
から読み取り、直接メモリ３４にロードして実行する
か、あるいはメモリ３４にロードし実行する前に、二次
記憶装置３０に格納することが可能である。

【００３８】この明細書に含まれる前述の説明および図
は、本発明に関連する利点の多くを例証するものであ
る。特に、２つの高速マンハッタン距離方法は、小エレ
メントのパターン認識の問題に有用であることが明らか
となっている。これら２つの方法は、独立して用いるこ
とも、組み合わせて用いることも可能である。本発明に
ついて、その特定実施例を参照しながら、説明し図示し
たが、本発明がこれら代表的な実施例に限定されること
を意図するものではない。本発明の精神から逸脱するこ
となく、変更や改造が可能であることを、当業者は認め
よう。例えば、温度計符号の実施例は、３ビット位置を
超えての拡張も容易に行うことができる。したがって、
本発明は、特許請求の範囲に該当する改造および変更を
全て含むことを意図するものである。

【００３９】請求項の要素および段階には番号および／
または文字が付されているが、これは読解および理解に
役立てるためのみに与えられたものである。したがっ
て、番号付けおよび／または符号付け自体が、請求項に
おける要素および／または段階の順序を示すことを意図
する訳ではなく、そのような順序を示すと見做すべきで
はない。

【図面の簡単な説明】

【図１】開示した発明によるパターン処理方法を示すフ
ロー・チャート。

【図２】英単語の"he"に対応する漢字を示す図。

【図３】図２に示した文字の画素アレイ表現を示す図。

【図４】図１に示した一ステップの第１実施例を示すフ
ロー・チャート。

【図５】図４に示した一ステップを示す図。

【図６】開示した発明の説明に有用な一例を示す図。

【図７】図６に示したデータを用いた、図４に示した第
１実施例の処理を示す図。

【図８】図１に示した一ステップの第２実施例を示すフ
ロー・チャート。

【図９】図６に示したデータを用いた、図８に示した第
２実施例の処理を示す図。

【図１０】本発明を実施する際に利用する汎用コンピュ
ータを示すブロック図。

【符号の説明】

２０汎用コンピュータ２２コンピュータ・プロセッサ２４バス２６バス３０二次記憶装置３２外部記憶装置３４モニタ３６入力装置３８プリンタ

───────────────────────────────────────────────────── フロントページの続き (72)発明者デ−レイ・リーアメリカ合衆国テキサス州オースチン、シニック・バルフ・ドライブ9605

Claims

【特許請求の範囲】

【請求項１】入力特徴ベクトルおよび既知の特徴ベクト
ル間のマンハッタン距離を計算する方法であって：Ａ）前記入力特徴ベクトルを入力温度計符号ベクトルに
変換する段階（４０２）；Ｂ）前記既知の特徴ベクトルを既知の温度計符号ベクト
ルに変換する段階（４０４）；Ｃ）前記入力温度計符号ベクトルと前記既知の温度計符
号ベクトルのＸＯＲを取ることによって、差ベクトルを
計算する段階（４０６）；およびＤ）前記差ベクトル内のビット数を数えて、マンハッタ
ン距離を計算する段階（４０８）；から成ることを特徴
とする方法。
【請求項２】入力温度計符号ベクトルおよび既知の温度
計符号ベクトル間のマンハッタン距離を計算する方法で
あって：Ａ）前記入力温度計符号ベクトルと前記既知の温度計符
号ベクトルのＸＯＲを取ることによって、差ベクトルを
計算する段階（４０６）；およびＢ）前記差ベクトル内のビット数を数えて、マンハッタ
ン距離を計算する段階（４０８）；から成ることを特徴
とする方法。
【請求項３】入力特徴ベクトルおよび既知の特徴ベクト
ル間のマンハッタン距離を計算するデータ処理システム
（２０）であって：Ａ）前記入力特徴ベクトルを入力温度計符号ベクトルに
変換する手段（４０２）；Ｂ）前記既知の特徴ベクトルを既知の温度計符号ベクト
ルに変換する手段（４０４）；Ｃ）前記入力温度計符号ベクトルと前記既知の温度計符
号ベクトルのＸＯＲを取ることによって、差ベクトルを
計算する手段（４０６）；およびＤ）前記差ベクトル内のビット数を数えて、マンハッタ
ン距離を計算する手段（４０８）；から成ることを特徴
とするデータ処理システム（２０）。
【請求項４】入力特徴ベクトルおよび既知の特徴ベクト
ル間のマンハッタン距離を計算する方法であって：Ａ）前記既知の特徴ベクトルの最上位部からの各エレメ
ントと、前記入力特徴ベクトルの最上位部とのＸＯＲを
取り、暫定的最終ベクトルを生成する段階（８０２）；Ｂ）前記既知の特徴ベクトルの最下位部からの各エレメ
ントと、前記入力特徴ベクトルの最下位部とのＸＯＲを
取り、最下位最終ベクトルを生成する段階（８０４）；Ｃ）前記暫定的最終ベクトルにおいて、あらゆる特殊な
場合を突き止める段階（８０６）；Ｄ）前記暫定的最終ベクトルにおける前記あらゆる特殊
な場合を補正し、最上位最終ベクトルを生成する段階
（８０８）；Ｅ）前記最上位最終ベクトルにおける１ビットの数を数
え、最上位ビット・カウントを生成する段階（８１
０）；Ｆ）前記最下位最終ベクトルにおける１ビットの数を数
え、最下位ビット・カウントを生成する段階（８１
０）；およびＧ）前記最下位ビット・カウントと、前記最上位ビット
・カウントを２倍した数とを加算し、マンハッタン距離
を生成する段階（８１０）；から成ることを特徴とする
方法。
【請求項５】入力特徴ベクトルおよび既知の特徴ベクト
ル間のマンハッタン距離を計算するデータ処理システム
（２０）であって：Ａ）前記入力特徴ベクトルの最上位部からの各エレメン
トと、前記入力特徴ベクトルの最下位部からの対応する
エレメントとのＸＯＲを取り、中間入力ベクトルを生成
する手段（８０２）；Ｂ）前記既知の特徴ベクトルの最上位部からの各エレメ
ントと、前記入力特徴ベクトルの最上位部とのＸＯＲを
取り、暫定的最終ベクトルを生成する手段（８０４）；Ｃ）前記既知の特徴ベクトルの最下位部からの各エレメ
ントと、前記入力特徴ベクトルの最下位部とのＸＯＲを
取り、最下位最終ベクトルを生成する段階（８０４）；Ｄ）前記中間入力ベクトルからの各エレメントと、前記
暫定的最終ベクトルからの対応するエレメントおよび前
記最下位最終ベクトルからの対応するエレメントとのＡ
ＮＤを取り、エラー・ベクトルを生成する手段（８０
６）；Ｅ）前記暫定的最終ベクトルからの各エレメントと、前
記エラー・ベクトルからの対応するエレメントとのＸＯ
Ｒを取り、前記最上位最終ベクトルを生成する手段（８
０８）；Ｆ）前記最上位最終ベクトルにおける１ビットの数を数
え、最上位ビット・カウントを生成する手段（８１
０）；Ｇ）前記最下位最終ベクトルにおける１ビットの数を数
え、最下位ビット・カウントを生成する手段（８１
０）；およびＨ）前記最下位ビット・カウントと、前記最上位ビット
・カウントを２倍した数を加算し、マンハッタン距離を
生成する手段（８１０）；から成ることを特徴とするデ
ータ処理システム（２０）。