JPH11312220A - 正規化されたグレ―スケ―ル画像の分類駆動型閾値処理 - Google Patents

Abstract

(57)【要約】 【課題】 従来の二値化方法で認識処理を実行した場
合、閾値処理によって画像に関する多くの有益な情報が
失われ、認識精度が劇的に低くなることが多い。 【解決手段】 サンプル画像142のサイズを参照画像146
のサイズへ正規化し、候補画像147の集合を参照画像146
の集合から判定することによってサンプル画像142を認
識し、候補画像147の各々はサンプル画像142の異なる二
値化(バイナリマトリクス145)からの距離が許容範囲内
にある。画像認識のためのシステム120には、スキャナ1
26、正規化ユニット134、距離計算ユニット136、分類ユ
ニット138、明確化ユニット140並びに表示装置128が含
まれる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は一般に画像認識に関
し、特に正規化されたグレースケール画像の分類駆動型
閾値処理による光学的文字認識の方法とシステムとに関
する。

【０００２】

【従来の技術】光学的文字認識技術において、画像分類
装置は、サンプル画像を参照画像の集合すなわちテンプ
レートと一致させることを企図する機能ユニットであ
る。ほとんどの文字画像はグレースケールで標本化さ
れ、その結果一つの画像ピクセル当たり複数のデータ・
ビットが生じるにもかかわらず、画像分類装置は一般に
バイナリ(バイ・レベル)入力データに限定されている。
グレースケールデータの分析は実質的にもっと複雑で、
時間のかかる極めて複雑な技術を必要とする。従って、
グレースケール分類装置は存在するものの、容易に利用
できるほとんどの画像分類装置ではバイナリ入力データ
しか受け付けない。“ボックス連結性アプローチを用い
るマルチフォント光学的文字認識”に対してKrtolica他
に特許された米国特許No. 5,539,840(この米国特許は本
明細書に参考文献として取り入れられている)に記載さ
れているシステムのような、光学的文字認識用の様々な
バイナリ分類装置が当業では知られている。

【０００３】サンプル画像にはグレースケールデータが
含まれるが、画像分類装置はバイナリデータしか受け入
れないので、最初にサンプル画像をグレースケールから
黒と白へ変換しなければならない。このステップには通
常、閾値処理、あるいは二値化と称されるプロセスが必
要とされ、このプロセスには、中間グレーレベル(“二
値化閾値”あるいは“閾値”と通常称される)の選択
と、ピクセルの原グレーレベルが閾値の値より大きい値
を持っているかあるいは小さい値を持っているかによっ
て決められる、各画像ピクセルの値の０又は１のいずれ
かへの変更と、が含まれる。従来のシステムにおいては
一般に、単一の閾値が使用されるサンプル画像の二値化
が一回行われ、二値化後にバイナリ出力データが画像分
類装置へ与えられる。

【０００４】

【発明が解決しようとする課題】しかしながら、従来の
二値化方法で認識処理を実行した場合、閾値処理によっ
て認識精度が劇的に低くなることが多い。画像が閾値化
されると画像に関する多くの有益な情報が失われる。例
えば、8ビットグレースケール画像には、その閾値処理
された画像の8倍のデータが含まれる。このようなデー
タによって、人間の目は画像を認識する際に助けられる
が、従来の画像認識システムでは、これらのデータは閾
値処理を行うことで失われてしまう。

【０００５】更に、閾値処理に伴い画像中へ有害なノイ
ズが入り込む。画像のグレーレベル中の僅かな偏り(dev
iations)が、閾値処理後、鋸歯状エッジ(jagged edge
s)、ストレイ(stray)ピクセル、空隙(gaps)及び他のア
ーティファクトの形ではっきりと現れることが多く、こ
れらのために認識精度が低下する。更に、閾値処理後、
サンプル画像は参照画像のサイズまで通常正規化され
る。しかし、バイナリデータの正規化によって一般にノ
イズが合成され、認識精度が大幅に低くなる。この場合
必要なことは、原グレースケール画像に関するできるだ
け多くの情報を保持し、閾値処理と正規化のプロセスに
関連するノイズを少なくしながら、バイナリデータをバ
イナリ画像分類装置へ与えるための方法とシステムであ
る。

【０００６】先程述べたように、従来のシステムでは、
画像分類処理とは別個のステップとして閾値処理が行わ
れるのが普通である。従って、そのようなシステムで
は、閾値処理とは単純化又は量子化ステップにすぎな
い。しかし、図1に示すように、閾値処理は分類処理に
とって主要な処理であり、分類処理から簡単に分離でき
るものではない。例えば、図1のマトリクス(a)は、１ピ
クセル当たり8ビット(256グレーレベル)で標本化された
グレースケール画像を表す。この二値化閾値(“T”)を1
28と選択した場合、マトリクス(b)がその結果生じたバ
イナリ画像を例示するが、この画像はバイナリ画像分類
装置によって文字“U”と解釈されることになる。しか
し、この閾値を140と選択した場合、マトリクス(c)がそ
の結果生じたバイナリ画像を例示し、この画像はバイナ
リ画像分類装置によって文字“L”であると解釈される
ことになる。この解釈は両方とも妥当(valid)である。
しかし、各々の場合、二値化閾値の選択は、どのピクセ
ルが前景(“1”)にありどのピクセルが背景(“0”)にあ
るかを判定するものである。従って、この閾値処理ステ
ップによって、画像分類処理が有効に決定される。

【０００７】前述の状況は前景と背景との間のコントラ
ストが弱い場合に、また、前景あるいは背景のグレーレ
ベルがサンプル画像を通じて均一でない場合に生じるこ
とが多い。人間の目はこれらの異常を容易に補償するこ
とができる。しかし、分類前に画像を別個に閾値化する
従来の画像認識システムでは頻繁に不正確な結果が生じ
る。実際、上に示すように、いずれかの閾値の恣意的選
択のために、文字画像の妥当で可能性の高い正しい解釈
が除かれることがよく起こる。

【０００８】閾値処理ステップは分類処理とは別個に行
われるので、従来のバイナリ画像分類装置では、異なる
閾値に基づくような択一的解釈を検出することはできな
い。もしこの閾値処理を参照画像を事前に知ることと同
時に行うことができれば、異なる閾値に基づくサンプル
画像についてのいくつかの可能な解釈を決定することが
できよう。更に、この二値化サンプル画像からの容認で
きる“距離”を持つ解釈のみを選択することができよ
う。

【０００９】この場合必要なことは、異なる閾値を用い
て画像のいくつかの解釈を見いだすような、閾値処理と
分類ステップとの一体化のための方法とシステムであ
る。更に必要なことは、二値化サンプルと参照画像間の
距離を最小化し、解釈を選択するための方法とシステム
である。以後、このプロセスを“分類駆動型閾値処理(c
lassification-driven thresholding)”と呼ぶことにす
る。更に必要なことは、全ての可能な閾値化された画像
を参照画像の集合と網羅的に比較することに依らず分類
駆動型閾値処理を効率的に行う方法とシステムである。
最後に必要なことは、文字画像の望ましい解釈を選択す
ることによって候補集合を明確化するための方法とシス
テムである。

【００１０】

【課題を解決するための手段】本発明は、正規化された
グレースケール画像の分類駆動型閾値処理による画像認
識のための方法とシステムを提供することによって、従
来の画像認識システムの前述の問題点を処理するもので
ある。本発明に従って、サンプル画像(142)はサンプル
画像(142)のサイズを参照画像(146)のサイズへ正規化す
る(404)ことによって認識され、参照画像(146)の集合か
ら候補画像(147)の集合が判定され(406)、候補画像(14
7)の各々はサンプル画像(142)の異なる二値化(145)から
の距離が許容範囲内にある。

【００１１】本発明によれば、画像認識のためのシステ
ム(120)にはスキャナ(126)、正規化ユニット(134)、距
離計算ユニット(136)、分類ユニット(138)、明確化ユニ
ット(140)、並びに表示装置(128)が含まれる。

【００１２】

【発明の実施の態様】本発明のこれらの及びその他の更
に詳細で具体的な目的と特徴を添付図面を参照しなが
ら、以下の明細書に完全に開示する。

【００１３】手書き若しくは機械印刷文字の画像を認識
するという文脈で以下の説明を行う。しかし、本明細書
に開示する原理と方法を用いて様々な画像タイプを認識
し、更に画像を特徴づけるために用いられるベクトルを
特徴づけることもできる。従って、本発明の範囲は文字
認識のみに限定されるものではない。更に、以下の説明
はグレースケール画像を認識するという文脈におけるも
のではあるが、本発明の方法とシステムを用いてカラー
画像も認識できるということを当業者は認めるであろ
う。

【００１４】＜システム構成＞図2を参照すると、本発
明による文字画像を認識するためのシステム120の物理
的ブロック図が示されている。一つの実施形態では、本
発明は、従来型のパーソナルコンピュータ上で実行され
るソフトウェアとして実施される。従って、図2に示さ
れるようなシステム120のハードウェア構成は、他の実
施方法も可能ではあるが、そのようなコンピュータから
なる構成要素を組み合わせたものとして実施されること
が望ましい。

【００１５】中央演算処理装置(CPU)122によってソフト
ウェアの命令が実行され、他の構成要素と相互に作用し
て本発明の方法が実行される。記憶装置124によってデ
ータとソフトウェアプログラムの長期保存が行われる
が、この記憶装置はハードディスク装置や他の適当な大
容量記憶装置として実装してもよい。スキャナ126によ
って認識すべき文字を表す二次元配列のピクセル値が得
られる。ある好適な実施形態では、スキャナ126は1イン
チ当たり400ドット(ピクセル)の解像度を備えたデジタ
ルスキャナである。各ピクセルは8ビットグレースケー
ル解像度で量子化される。マウスやキーパッドのような
入力装置127は、ユーザがシステム120の操作をコントロ
ールするのを容易にするものである。表示装置128はCPU
122の制御の下でテキストとグラフィックを表示するた
めのCRTやプリンタのような出力装置である。システム1
20には、例えば、インターネットのようなコンピュータ
ネットワークと接続するためのモデムやイーサネットカ
ードのような通信装置130を含めてもよい。

【００１６】システム120にはまた、CPU122によって実
行されるソフトウェア命令を格納するためのメモリ132
も含まれる。メモリ132はランダムアクセスメモリ(RAM)
のような標準的記憶装置を用いて実装される。ある好適
な実施形態では、メモリ132には、いくつかのソフトウ
ェアオブジェクトや、正規化ユニット134、距離計算ユ
ニット136、分類ユニット138、並びに明確化ユニット14
0を含むモジュールが含まれる。本解説を通じて、前述
のモジュールは別個の機能ユニットであると仮定されて
いるが、様々なユニット機能を組み合わせ一体化して単
一のソフトウェアアプリケーションにしてもよいことは
当業者によって認識されるであろう。

【００１７】ある好適な実施形態では、メモリ132を用
いて、サンプル画像142、グレーマトリクス144、バイナ
リマトリクス145、複数の参照画像146、並びに候補集合
147が格納される。サンプル画像142はスキャナ126によ
って得られたビットマップ化されたグレースケール画像
である。グレーマトリクス144は整数からなる二次元配
列であることが望ましく、この配列を用いてサンプル画
像142中のグレースケール情報が特徴づけられる。バイ
ナリマトリクス145はグレーマトリクス144の二値化バー
ジョンであり、グレーマトリクス144と参照画像146との
間の距離を計算する際に用いられる。参照画像146はグ
レーマトリクス144に対して比較される、以前に得られ
た既知のテンプレートの集合である。グレーマトリクス
144のように、参照画像146は二次元配列として格納され
ていることが望ましいが、この配列にはバイ・レベル
(バイナリ)データしか含まれない。候補集合147は有力
な認識候補として選択された参照画像146の集合であ
る。

【００１８】最後に、メモリ132には、上述のソフトウ
ェアオブジェクトやモジュールを管理し、それらのオブ
ジェクトやモジュールにシステムリソースを与えるオペ
レーティング・システム148が含まれる。

【００１９】＜画像認識システムにおけるデータの流れ
＞図3を参照すると、本発明による画像認識システム120
におけるデータの流れが示されている。最初に、スキャ
ナ126によってサンプル画像142が得られ、一枚の紙のよ
うな走査対象物上の一つの画像がピクセル毎に表示され
る。当業者であれば解るように、通常、テキストの１ペ
ージが全部一度に走査される。これは一般にセグメンテ
ーションという追加ステップを必要とし、そのページは
個々の文字にセグメント化される。これについては“ボ
ックス連結性アプローチを用いるマルチフォント光学的
文字認識”に対してKrtolica他に特許された米国特許N
o.5,539,840に記載されており、この米国特許の発明主
題は本明細書に参考文献として取り入れられている。し
かし、説明の便宜上、画像142は、セグメンテーション
・プロセスによってつくられるような単一の文字のみを
表すものと仮定する。

【００２０】正規化ユニット134がスキャナ126と接続し
ているが、このユニットは、サンプル画像142のサイズ
を参照画像146のサイズへ正規化することによってグレ
ーマトリクス144を生成するものである。以下、図5を参
照しながら、このプロセスを更に詳細に説明する。しか
し手短に言えば、正規化ユニット134によって、サンプ
ル画像142がグレーマトリクス144に対応する格子上へマ
ップされ、格子の各領域によってマップされたピクセル
に対するピクセルの“重み”が計算される。

【００２１】ある好適な実施形態では、グレーマトリク
ス144、バイナリマトリクス145、参照画像146は16×16
の要素のサイズを備えている。このサイズ自体は本発明
にとって決定的に重要な問題ではないが、各マトリクス
についてこのサイズが同一であることが望ましい。更
に、いくつかの要因に留意してこのサイズを選択しなけ
ればならない。例えば、文字のエッジに関する十分な情
報を入手しながらノイズを最小化するためにこのサイズ
を選択すべきであることが当業者によって認識されるで
あろう。更に、ハードウェアとソフトウェアの実装を簡
略化するために二次元のサイズを選択し、コンベンショ
ナルメモリとCPUとに過重な負担をかけないほど十分に
小さいサイズを選択するような実際的配慮が関係してく
る。

【００２２】分類ユニット138が正規化ユニット134と接
続しているが、この分類ユニットはグレーマトリクス14
4を参照画像146と比較して候補集合147を判定するため
のものである。以下図6A〜6Bを参照しながらこのプロセ
スを更に詳細に説明する。従来のシステムとは異なり、
分類ユニット138は、距離計算ユニット136とともに、グ
レーマトリクス144の分類駆動型閾値処理によって候補
集合147を判定する。一つの好適な実施形態では、この
判定は、複数の閾値で二値化されたグレーマトリクス14
4と参照画像146の集合との間の距離の集合を計算するこ
とによって達成される。その後、候補集合147が選択さ
れ、候補画像147とサンプル画像142の二値化との間の距
離は許容範囲内である。

【００２３】明確化ユニット140が分類ユニット138と接
続しているが、二つ以上の候補が分類ユニット138によ
って見つけられた場合、このユニットを使って望ましい
候補147が選択される。手短に言えば、この選択は、各
候補147を原サンプル画像142のサイズへ空間的に正規化
し、この後図6Cを参照しながら説明するような分類方法
を繰り返すことによって達成される。

【００２４】最後に、CRTやプリンタのような表示装置1
28が明確化ユニット140と接続している。認識された候
補画像147は表示装置128によってシステム120のユーザ
へ出力される。唯一の候補画像147が特定されなかった
場合、表示装置128はエラーメッセージを出力すること
が望ましい。

【００２５】＜画像認識の望ましい方法＞図4を参照す
ると、文字画像を認識するための本発明による望ましい
方法のフローチャートが示されている。この方法は認識
対象文字のサンプル画像142を取得する(S402)ことによ
って開始される。この取得は、文字を示すピクセル単位
に、スキャナ126によって達成される。文字の物理的サ
イズは異なるので画像142のピクセルのサイズもまた異
なる。一般に、手書き文字についてはそのサイズが大き
く異なり、縦200ピクセル×横100ピクセルほどのサイズ
になることもある。これと対照的に、機械で印刷された
14ポイントの文字はおおよそ48×32ピクセルのサイズで
ある。また図5を参照すると、文字“M”のサンプル画像
142を含む正規化プロセスが図解されている。この例で
は、サンプル画像142のピクセルのサイズは64×64であ
る。

【００２６】この方法は、サンプル画像142のサイズを
参照画像146のサイズへ正規化する(S404)ことによって
続けられる。ある好適な実施形態では、参照画像146は
二次元マトリクスとして格納され、それぞれのマトリク
スサイズは16×16の要素からなる。従って、比較を行う
ためにサンプル画像142を同様のサイズのマトリクスに
変換すると都合が良い。

【００２７】図5に示すように、正規化ステップは16×1
6のボックス502からなる格子500の上へサンプル画像142
をマップすることによって達成される。格子500を使っ
て値がグレーマトリクス144へ割り当てられ、各ボック
ス502はグレーマトリクス144の対応する要素と関連づけ
られる。上に述べたように、サイズの選択は本発明にと
って決定的に重要な問題ではない。しかし、ある好適な
実施形態では、サンプル画像142を参照画像146と同じサ
イズを持つ格子500上へマップしなければならない。

【００２８】更に図5に示すように、サンプル画像142の
サイズが64×64ピクセルなので、各ボックス502は16個
のピクセルと関連づけられる。更に、拡大された格子部
分506に例示されているように、各ピクセルは対応する
グレーレベルを有し、このグレーレベルは0と255の間の
整数値nをとる。画像142が得られると、スキャナ126に
よってこのグレーレベルが判定される。グレーレベル0
は完全に白いピクセルに対応し、グレーレベル255は完
全に黒いピクセルに対応することが望ましい。0と255の
間の値はグレーの濃淡を表す。しかし、スキャナ126の
中にはこれらのカラーマッピングを逆転できるものもあ
ることは当業者によって認識されるであろう。

【００２９】サンプル画像142が格子500上へマップされ
た後、ボックスに含まれるピクセルのグレーレベルを合
計することによって、各ボックス502に対するピクセル
の“重み”が計算される。次に、各々の合計は、図5の
拡大されたマトリクス部分508に例示されているよう
に、グレーマトリクス144の対応する要素に格納され
る。正規化プロセスが完了すると、グレーマトリクス14
4の各要素は格子500によってマップされた領域の適切な
ピクセルの重みに対応する整数値を持つ。

【００３０】格子500とサンプル画像142の縦のサイズが
横のサイズと同程度に重要であることは当業者であれば
認識されうる。例えば、61×47からなるサイズを有する
サンプル画像142を16×16のサイズの格子500に区分する
こともできる。この区分が行われると、ボックス502は
ピクセルを二等分する傾向がある。近似によってこの問
題を補償することはできるものの、認識精度が損なわれ
る場合がある。従って、ある好適な実施形態では、ピク
セルが二等分された場合、影響を受けたピクセルのグレ
ーレベルは、ピクセルを含む二つ又はそれ以上のボック
ス502の間で比例分割される。このようにして、各ボッ
クス502の相対的重みの正確な計算が可能となる。

【００３１】更に、ある好適な実施形態では、上に説明
した合計プロセスに、当業者に周知の方法を利用した、
整数演算で実行する有理数計算が採用される。これと対
照的に、浮動小数点演算を用いて値計算を行う場合近似
計算が依然として必要であり、速度とメモリという問題
が結果として生じる場合がある。従って、すべての値は
有理数として格納され、全ての関数が有理数を処理する
ように適合される。例えば、そのような関数をカスタム
展開することによって、あるいは整数演算で実行する有
理数計算用のいくつかの標準的パッケージのいずれかを
使用して、この処理を行うことができる。

【００３２】再び図4を参照すると、正規化ステップS40
4の完了後、グレーマトリクス144はサンプル画像142の
正規化されたバージョンとなり、グレースケールデータ
が含まれる。しかし、参照画像146はバイ・レベルデー
タから成るので、参照画像146と比較するためにはグレ
ーマトリクス144を二値化しなければならない。従来の
方法では、閾値が選択され、次いで標準的閾値処理技術
を用いてグレースケールデータが二値化される。しか
し、図1に例示されているように、単一の閾値選択を行
った場合、妥当で確率の高い画像解釈が除去される場合
がある。

【００３３】従って、ある好適な実施形態では、サンプ
ル画像142の分類駆動型閾値処理を用いて、距離計算ユ
ニット136と接続した分類ユニット138によって候補集合
147が判定される(S406)。以下の説明によって、候補集
合147を判定する技術を利用する網羅的方法のみならず
分類駆動型閾値処理の理論を概説する。その後、分類駆
動型閾値処理を行うためのより有効で望ましい方法を提
示する。

【００３４】＜網羅的分類駆動型閾値処理＞概念的に
は、分類駆動型閾値処理とは、閾値処理と、全ての可能
な閾値で二値化されたグレーマトリクス144を参照画像1
46の集合と比較することにより候補集合を判定する画像
認識の分類ステップと、を統合したものである。図6
は、分類駆動型閾値処理の網羅的方法を示すフローチャ
ートである。最初の閾値(“T”)を最小値に設定する(S6
02)ことによってこの方法は開始される。ある好適な実
施形態では、この最小値はゼロである。しかし、代替実
施形態では、グレーマトリクス144中の実際の最低値の
ような他の所望の値でTを開始してもよい。

【００３５】Tの値のリセット後、次の参照画像146が選
択される(S604)。その後、Tを二値化閾値として用いて
グレーマトリクス144を二値化し、その結果生じるバイ
・レベルデータをバイナリマトリクス145に格納する方
法が続けられる。ある好適な実施形態では、T以下のグ
レーマトリクス144の値を0に、Tより大きい値を1に変更
することにより、この二値化プロセスを行う。しかし、
本発明の精神から逸脱せずにこの1と0の割り当てを逆に
してもよい。

【００３６】その後、バイナリマトリクス145と選択さ
れた参照画像146との間の距離を計算する(S608)方法が
続けられる。ある好適な実施形態では、距離の測定値と
してハミング距離が利用される。ハミング距離の計算は
当業では周知である。参照マトリクスRとサンプルマト
リクスSの二つのマトリクスの各マトリクスが同じサイ
ズで、かつ各マトリクスが1(黒を表す)か0(白を表す)の
いずれかの値で総数N個の要素を持ち、RとSの双方の中
の値1に等しい対応する要素の数をC[b]で表し、RとSの
双方の中の値0に等しい対応する要素の数をC[w]で表す
と仮定すると、参照マトリクスRとサンプルマトリクスS
との間のハミング距離H(R,S)は以下のように定義され
る： H(R,S) = N-(C[b]+C[w]) 式1 0のハミング距離は、マトリクスRとSとが同一であるこ
と意味することは当業者によって認識されるであろう。
これらのマトリクスがもっと発散するにつれてハミング
距離は大きくなり、ついにはその距離は、一つの画像が
完全に黒く、もう一方の画像が完全に白い最大距離に達
する。従って、好適な16×16のマトリクス間のこの最大
ハミング距離は256である。

【００３７】この距離が計算された(S608)後、この距離
が許容範囲内にあるかどうかの判定(S610)が行われる。
一つの好適な実施形態では、0の距離が唯一の容認でき
る距離であるが、この距離は完全一致を要求するもので
あろう。しかし、ある好適な実施例では、ノイズやその
他の影響によって、結果として非ゼロ距離を生じるスト
レイピクセルと空隙がつくりだされるので、低い非ゼロ
値が実験的に選択される。ある好適な実施形態では、容
認できる距離はハミング距離2である。

【００３８】この距離が許容範囲内にあると判定された
(S610)場合、参照画像146の表示データはメモリ132中の
候補集合147に格納される(S612)。先程述べたように、
参照画像146は周知のテンプレートであり、このテンプ
レートと関連する文字を備えている。従って好適にはこ
の関連する文字とハミング距離のみが候補集合147の中
に存在する必要がある。

【００３９】更に、ある好適な実施形態では、現在の候
補147と関連するハミング距離が容認できるものではあ
るが、格納された候補147の距離より大きい場合には、
現在の候補147は、正しいものにはなりそうにないので
格納してはならない。同様に、現在の候補147の距離が
格納された候補147の距離より小さい場合には、格納さ
れた候補147を廃棄しなければならない。

【００４０】次に、もっと多くの参照画像146を比較す
べきバイナリマトリクス145がまだ残っているどうかの
判定(S614)が行われる。比較すべきもっと多くの参照画
像146がまだ残っている場合、この方法はステップS602
へ戻り、比較しない場合には方法は完了する。

【００４１】ステップS610で、距離が許容範囲内にない
と判定された場合、方法はTの値を増分する(S616)こと
によって継続される。ある好適な実施形態では、この閾
値の増分は、グレーレベルの数で割ったグレーマトリク
ス144の要素の最大の重みと等しい。図5に例示されてい
る例では、閾値の増分は16(4080/255)である。しかし、
この増分値は1又は他の任意の数であってもよい。もっ
とも、閾値の増分を選択する際の速度と精度との間のト
レード・オフは当業者によって認められるであろうが。

【００４２】Tの増分(S616)後、Tが所定の最大値を超え
るかどうかの判定(S618)が行われる。ある好適な実施形
態では、この最大値はグレーマトリクス144の一つの要
素の可能な最大値であり、各ボックス502に含まれるピ
クセル数に従って変化する。例えば、図5では各ボック
ス502には16個のピクセルが含まれる。従ってグレーマ
トリクス144の一つの要素の最大値は4080(255×16)であ
る。ある代替実施形態では、その最大値をグレーマトリ
クス114に格納された実際の最大値に設定することもで
きる。その理由は、その値より大きい閾値処理によって
全く同一のバイナリマトリクス145が生み出されるから
である。ステップS616でこの最大値を超えた場合、方法
はステップS614で続けられ、最大値を超えない場合には
方法はステップS606へ戻り新しい閾値でグレーマトリク
ス144が二値化される。

【００４３】分類駆動型閾値処理のこの“網羅的”方法
を図7Dに例示するが、この図は、図7Aのいくつかの閾値
で二値化されたグレーマトリクス144と、図7Bと7Cにそ
れぞれ示される二つの参照画像146aと146bとの間で計算
されたハミング距離のグラフである。例示を容易にする
ために、グレーマトリクス144とこの二つの参照画像146
a〜bの各々は5×4要素のサイズを持つ。更に、ある好適
な実施形態では、マトリクス144は0と255との間の各整
数値で二値化される。しかし、図を簡略化するために、
図7Dに示す距離は、指示された地点でのみ計算されたも
のであり、従って、線は単に視覚化を行うために引かれ
ているにすぎない。

【００４４】図7Dに示すように、二値化グレーマトリク
ス144と参照画像146aとの間のハミング距離はT＝153で
最小距離(この場合0)に達する。従って、グレーマトリ
クス144がT＝153で二値化された場合、その結果生じる
バイナリマトリクス145は参照画像146aと同一となる。
その後、Tが増加するにつれて、その距離はT＝166から
始まり増加し始める。同様のグラフが参照画像146bにつ
いて提供されている。もっともこの場合最短距離は1で
あり、T＝199で最短距離に到達している。

【００４５】図7Dのグラフの各々を関数によって数学的
に表現してもよい。 F(T;B,N): = ΣΣ|Bij-I(Nij-T)| 式2 ここで、各Σはそれぞれi=0〜m-1，j=0〜n-1の範囲であ
り、BijとNijはそれぞれ、m×nのマトリクスB(参照画像
146)とN(グレーマトリクス144)の要素であり、Tは閾
値、Iはステップ関数である: 前述の方法を適用することによって、グレーマトリクス
144からの容認できる距離を持つ候補画像の集合147を判
定することができる。しかし、この方法は、0と255の間
の各整数値で二値化されたグレーマトリクス144と、各
参照画像146との間の距離を計算しなければならないの
で、“網羅的”である。多数の計算が必要なことは当業
者が認めるところであろう。例えば、256個のグレーレ
ベルと256個の参照画像146があると仮定すると、65536
(256×256)個の距離を計算し、候補集合147を判定する
必要がある。多くのコンピュータにとってこのプロセス
はあまりに時間がかかりすぎて実際上使用できないであ
ろう。

【００４６】＜分類駆動型閾値処理を行うための効率的
方法＞参照画像146の集合が既知であるということを認
識することによって、分類駆動型閾値処理を行うもっと
効率的方法の達成が可能である。従って、必ずしも全て
の距離計算を行う必要はない。実際、最短ハミング距離
を得るためにほんのわずかの距離計算は必要となるかも
しれない。この目的を達成するためには、図7D中の各グ
ラフが単一の関数ではなく、二つの関数の和を表すとい
うことを理解しなければならない。すなわち、一つの関
数は参照画像146の“前景”と、グレーマトリクス144の
対応する要素との間の距離を表し、一つの関数は参照画
像146の“背景”と、グレーマトリクス144の対応する要
素との間の距離を表す。ある好適な実施形態では、“前
景”とは1を含む参照画像146の部分であり、一方“背
景”とは0を含む参照画像146の部分である。

【００４７】図7Eを参照すると、上に説明した距離関数
に対応する4つのグラフ702，703，704，705が示されて
いる。グラフ702は、画像146aの背景と、グレーマトリ
クス144の対応する要素との間の距離とを表す。グラフ7
03は、画像146aの前景と、グレーマトリクス144の対応
する要素との間の距離を表す。グラフ704と705は、画像
146bと関連するという点を除いてグラフ702と703と同様
のグラフである。

【００４８】グラフ702と704によって表される関数はT
の単調非増加関数であることを数学的に示すことができ
る。更に、グラフ703と705によって表される関数はTの
単調非減少関数であることを数学的に示すことができ
る。以下の説明で非増加グラフ702と704がゼロ閾値軸
(T)と交わるTの値を以後“T0”と呼ぶことにする。同様
に、非減少関数がT軸と交わるTの値を以後“T1”と呼ぶ
ことにする。数学的に、これらの値を次のように計算す
ることができる。 T0:= max{Nij|for all i,j such that Bij = 0}; T1:= min{Nij|for all i,j such that Bij = 1}-1; 式4 図7Eは図示のこれらのマトリクスに対するT0とT1を例示
するものである。

【００４９】これらの関数の数学的性質に基づいて、T0
とT1の値を用いて最短ハミング距離が0であるかどうか
を判定するか、あるいは、距離が最小になる閾値の範囲
を判定することができる。例えば、T0≦T1であればT0と
T1の間のTの全ての値についてハミング距離は0になる。
一方、T0＞T1であればTの全ての値についてハミング距
離は0より大きくなる。ただし最短距離はT0とT1の間で
得られる。従って、T0とT1の値を知ることによって多く
の二値化と距離計算を行わずに済むことが可能となる。
このプロセスの方がずっと効率的であり、従って、分類
駆動型閾値処理を行うための望ましい方法が提供され
る。

【００５０】図6Aを参照すると、本発明による分類駆動
型閾値処理によって候補集合147を判定する望ましい方
法のためのフローチャートが示されている。上に説明し
たように、この方法では参照画像146に関してT0とT1の
値をまず第一に決定しなければならない。従って、ある
好適な実施形態では、次の参照画像146を選択する(S65
0)ことによって方法が開始される。その後、図8Cと8Dに
例示されるように、グレーマトリクス144が、選択され
た参照画像146の前景と背景に対応する前景部分710(太
枠で示す)と背景部分712とに区分される(S652)。図示の
例では、区分されたマトリクス144aは、図8Aの選択され
た参照画像146aに従う区分けに対応し、区分されたマト
リクス144bは、図8Bの選択された参照画像146bに従う区
分けに対応する。

【００５１】グレーマトリクス144が区分された(S652)
後、T0とT1の値を決定する(S654)ことによってこの方法
は続けられる。ある好適な実施形態では、グレーマトリ
クス144の背景部分712で最大値を得ることによってT0が
決定される。区分されたマトリクス144aの場合、T0は15
3である。区分されたマトリクス144bについては、T0は1
99である。その後、前景部分710の最小値-1を得ること
によってT1が決定される。区分されたマトリクス144aの
場合、T1は165(すなわち166-1)である。区分されたマト
リクス144bについては、T1は198(すなわち199-1)であ
る。

【００５２】次に、T0≦T1かどうかを判定する(S656)こ
とによってこの方法は続けられる。上に説明したよう
に、T0≦T1であれば、T0とT1の間(T0とT1の両端を含む)
のTの全ての値について、バイナリマトリクス145と参照
画像146との間のハミング距離は0であり、このことは例
えば図8Cの区分されたマトリクス144aの場合真であり、
この場合T0(153)はT1(165)より小さい。従って、区分さ
れたマトリクス144aが例えばT＝153で二値化されれば、
その結果生じるバイナリマトリクス145は参照画像146a
と全く同一となり、完全一致が得られる。これは、T＝1
53でのハミング距離が0になることが示されている図7D
のグラフ上で確かめることができる。

【００５３】T0≦T1と判定された(S656)場合、候補集合
147中の現在の参照画像146の表示データを格納し(S65
8)、0より大きい距離を持つ任意の候補147を取り除くこ
とによってこの方法はステップS658で続けられる。ある
好適な実施形態では、画像146が完全にバイナリマトリ
クス145と一致すれば、バイナリマトリクス145から非ゼ
ロ距離を持ついずれの候補147も廃棄しなければならな
い。なぜならそれらの候補は正しい解釈にはなりそうに
ないからである。以下に説明するように、非ゼロ距離
(すなわちT0＞T1)を持つ候補147はそれらの候補と関連
するT0とT1値と共に暫定的に格納される。従って、これ
らの候補は簡単に特定し廃棄することができる。

【００５４】しかし、ステップS656でT0＞T1であると判
定された場合、最短ハミング距離0で候補147が既に得ら
れたかどうかを判定することによってこの方法は続けら
れる。好適には、完全一致が既に得られた場合には完全
一致に満たないものを格納する必要はない。従って、距
離0で候補147が既に得られていればステップS662で方法
は続けられ、得られていなければT0とT1に対する関連値
をもつ現在の参照画像の表示データを暫定的に格納する
(S661)ことによって方法は続けられる。

【００５５】ある好適な実施形態では、不要な計算を減
らすために実際のハミング距離をこの時点では計算しな
いことが望ましい。候補147についての最短ハミング距
離が全ての閾値に対して非ゼロとなることを認識するだ
けで十分である。その後、0の最短距離をもつ候補147が
特定された場合、全ての非ゼロ候補147は距離にかかわ
らず廃棄される。

【００５６】T0＞T1である場合の一例が区分されたマト
リクス144bに見られる。ここではT0の値(199)がT1の値
(198)を超えている。上に説明したように、これは最短
ハミング距離がTの全ての値について0より大きくなるこ
と、従って最小値はT0とT1の間で得られることを意味す
る。このことは図7Dを参照しながらグラフ上で確かめる
ことができる。上に述べたように、最短距離をこの時点
で計算する必要はない。代わりに、画像146bの表示デー
タが、それぞれT0とT1(すなわち199と198)に対するその
関連値と共に暫定的に格納される(S661)。

【００５７】ステップS658とS661のいずれかのステップ
の後、バイナリマトリクス145と比較すべきもっと多く
の参照画像146がまだ残っているかどうかを判定する(S6
62)ことによって方法は続けられる。もっと多くの参照
画像146がまだ比較のために残っている場合には、方法
はステップS650へ戻り、残っていない場合には、少なく
とも一つの完全一致(T0≦T1)がステップS656によって得
られたかどうかを判定することによってステップS664で
方法は続けられる。もし少なくとも一つの完全一致が得
られれば、蓋然性の高い候補集合147が判定されたとい
う理由で方法S406は終了する。

【００５８】次に図6Bを参照すると、完全一致が得られ
なかった場合、候補集合147はT0とT1値を持ついくつか
の暫定的に格納された候補から成る。従って、暫定的に
格納された各々の候補147に対する最短ハミング距離を
得ることが必要である。その後、ある好適な実施形態で
は、容認できる距離をもつ候補147のみが保持され他は
全て廃棄される。

【００５９】ステップS664の後、次の格納された候補14
7を選択する(S666)ことによって方法は続けられる。距
離がまだ計算されていない候補147のみが選択されるこ
とが望ましい。次に、候補147とグレーマトリクス144と
の間の最短距離が計算される(S668)。しかしながら、網
羅的方法とは異なり、必ずしも全ての可能な二値化をテ
ストする必要はない。先程述べたように、T1とT0の間の
値でグレーマトリクス144を閾値処理することによって
最短ハミング距離を得ることができる。従って、グレー
マトリクス144はT1とT0の間の各整数値で二値化され、
候補147からの距離が計算される。得られた最低の距離
が最短距離として選択される。

【００６０】このステップは若干の距離計算を必要とす
るものの、網羅的方法に比べれば必要な計算ははるかに
少ないことを当業者は認めるであろう。実際、図8Bの画
像146bが選択された候補である場合、網羅的方法で必要
な256回の計算に対してたった二回の距離計算(T＝198と
199での)しか必要としない。加えて、Allen GershoとRo
bert M. Gray著「ベクトル量子化と信号圧縮」(Kluwer
Academic Publications、Boston、1992(第5版 1996年))
に記載されている三角不等式に基づくベクトル量子化法
を用いることによって距離計算の回数を更に減らすこと
が可能である。

【００６１】選択された候補147について最短距離を計
算した(S668)後、その距離が許容範囲内にあるかどうか
を判定する(S670)ことによって方法は続けられる。上に
説明したように、小さな、この許容範囲を実験的に決定
して、蓋然性の高い候補集合147を選択することが望ま
しい。この距離が容認できるものでなければ、候補147
は廃棄され(S674)、容認できるものであれば、この計算
された最短距離が前に決定された候補147の距離以下で
あるかどうかの判定(S672)が行われる。ある好適な実施
形態では、この計算された最短距離が前に決定された距
離より大きい場合には、選択された候補147が正しいも
のである蓋然性は小さく従って廃棄される(S674)。しか
し、この計算された最短距離が前に決定された距離以下
である場合には、候補集合147にその距離を格納する(S6
76)ことによって方法は続けられる。

【００６２】ステップS674とS676のいずれかのステップ
の後、最短距離がまだ決定されていない候補が残ってい
るかどうかを判定することによって方法は続けられる。
まだ候補が残っている場合には、方法はステップS666へ
戻り、残っていなければ方法は完了する。

【００６３】再び図4を参照すると、分類駆動型閾値処
理を用いて候補集合147を判定(S406)後、候補集合147の
サイズが1より大きいかどうかを判定する(S408)ことに
よって方法は続けられる。好適には、認識された文字と
して二つ以上の文字が選択されないことが望ましい。従
って、1より大きい候補147がステップS406で得られた場
合、候補集合147を明確化する(S408)ことによって方法
は続けられる。

【００６４】選択された閾値に依ってグレースケール画
像142の二つの解釈が可能な曖昧な候補集合147の一例が
図1に例示されている。例えば、T＝128であれば、画像1
42は文字“U”と解釈される。しかし、T＝140であれ
ば、画像142は文字“L”と解釈される。両方の解釈とも
妥当であり、各解釈ともハミング距離は0である。従来
のやり方では、分類に先立つ単一の閾値で画像142が二
値化されるので、従来型の画像分類装置ではこれらの解
釈の一方は見逃されたであろう。しかし、本発明では、
候補集合147は両方の解釈を含めて判定される(S406)。
それにもかかわらず、人間の眼が“U”か“L”のいずれ
かとしてこの文字を認識することができるのであれば唯
一の正しい解釈がある。

【００６５】先程述べたように、原ソース画像142に
は、正規化されたグレースケールマトリクス144以外の
走査された対象物に関するより多くのデータが含まれ
る。実際、図5に例示されているようにソース画像142の
16個のピクセルを使ってグレーマトリクス144の一つの
要素がつくられる。従って、候補集合147を明確化し、
好適な文字を選択する際に画像142中の追加情報を手助
けとすることができる。

【００６６】この明確化プロセスは図6A〜Bで説明した
方法と同様である。しかし、以下に更に詳細に説明する
ように、候補147の参照画像146の各々は、前に行ったよ
うにソース画像142を参照画像146のサイズまで縮小され
るのではなく、先ず最初にソース画像142のサイズまで
空間的に正規化(拡大)される。その後、図6A〜Bの分類
駆動型閾値処理方法が繰り返されて新しい候補集合147
が計算される。

【００６７】サンプル画像142で使用可能な追加画像デ
ータのために、分類駆動型閾値処理法の繰り返しによっ
て原候補147の中のいくつかが除去されることが予期さ
れる。しかし、相対的に大きなサイズのソース画像142
が与えられた場合このプロセスの結果多数の計算が生じ
ることを当業者は認めるであろう。それにもかかわら
ず、ある好適な実施形態では、候補集合147は小さくな
る傾向があるため、ほんの少数の解釈しか再評価する必
要はない。

【００６８】図6Cを参照すると、候補集合147を明確化
し(S410)、望ましい候補を選択する好適な方法が示され
ている。この方法は、選択された候補147の参照画像146
をソース画像142のサイズまで空間的に正規化する(S68
2)ことによって開始される。バイナリ画像の空間的正規
化方法は当業では周知である。例えば、16×16のサイズ
の参照画像146を64×64のサイズのサンプル画像142のサ
イズまで空間的に正規化(拡大)する場合、当業者であれ
ば、拡大された画像では参照画像146の各ピクセルを16
倍大きく再現しなければならないことを認めるであろ
う。これが完了したとき、正規化された参照画像146の
集合が作られる。

【００６９】ある好適な実施形態では、図6A〜Bに説明
した方法とほぼ同じ方法を用いて新しい候補集合147を
決定する(S406)ことによってその方法は続けられる。し
かし、今回はグレーマトリクス144が事実上サンプル画
像142であり、参照画像146はステップS682でつくられた
正規化された参照画像146の集合である。好適には、説
明したこの方法に対して行うべき一つの変更として、容
認できる距離をステップS670で大きくして、新しいグレ
ーマトリクス144(サンプル画像142)の相対的に大きなサ
イズを考慮に入れることがある。

【００７０】ステップS406が完了すると、候補147が一
つしか残っていないかどうかの判定(S684)が行われる。
一つしか残っていなければ、その残った候補147が好適
な候補147として認識される。しかし、二つ以上の候補1
47が得られた場合には、一つの好適な実施例では候補14
7の全てが拒絶される。しかし、ある好適な実施形態で
は、文脈分析あるいは幾何学分析のいずれかを用いてこ
の曖昧さが解決される(S688)。 手短に言えば、文脈分
析とは問題の文字の周辺の文字又は語を参照したり、あ
るいは恐らく辞書などを参照することによって曖昧さを
解決するプロセスである。例えば、文字“U”と“L”の
いずれかを決めるとき、単語の最初の７文字が“GRAYSC
A”であったという事実によって、正しい解釈は(“GRAY
SCALE”という単語のスペルになるように)“L”である
ということが示唆される。

【００７１】同様に、幾何学的分析とは、走査された文
字の幾何学的性質を調べることによってあり得ない候補
選択を除去するプロセスである。例えば、文字“W”と
“I”のいずれかを決定する際、原サンプル画像142のサ
イズにもどって参照することにより、画像142が相対的
に幅が広ければ文字“I”が除去されることになろう。
両方の方法とも光学的文字認識の当業者には周知の方法
である。例えば、“ボックス連結性アプローチを用いる
マルチフォント光学的文字認識”に対してKrtolica他に
特許された米国特許No.5,539,840には最小境界フレーム
の幾何学的性質に基づいて文字を除去するプロセスが開
示されている。ステップS686とステップS688のいずれか
のステップ後にこの方法は終了する。

【００７２】再び図4を参照すると、ステップ408か410
のいずれかのステップ後、例えば表示装置128か通信装
置130のいずれかによって好適な候補147が出力される。
あるいは、好適な候補147を記憶装置124に格納してもよ
い。候補147が特定されなかった場合、又は曖昧さが解
決されなかった場合、システム120はエラーメッセージ
を出力することが望ましい。

【００７３】上記の説明は好適な実施形態の動作の例示
を含むものであるが、本説明は本発明の範囲の限定を意
図するものではない。本発明の範囲は上述した請求項に
よってのみ限定されるべきものである。上記の説明から
本発明の精神と範囲に依然として含まれる多くの変形が
当業者には明らかであろう。

【図面の簡単な説明】

【図１】異なる二値化閾値の選択によって生じた分類問
題の一例を示す図である。

【図２】本発明による文字画像142を認識するためのシ
ステム120の物理ブロック図である。

【図３】本発明による画像認識システム120のデータの
流れ図である。

【図４】本発明による文字画像142を認識するための望
ましい方法のフローチャートである。

【図５】正規化プロセスの図解を示す図である。

【図６】本発明による候補集合147を判定する網羅的方
法を表すフローチャートである。

【図６Ａ】本発明による候補集合147を判定する望まし
い方法を表すフローチャートである。

【図６Ｂ】本発明による候補集合147を判定する望まし
い方法を表すフローチャートである。

【図６Ｃ】本発明による候補集合147を明確化する望ま
しい方法を表すフローチャートである。

【図７Ａ】グレーマトリクス144の一例を示す図であ
る。

【図７Ｂ】参照画像146の一例を示す図である。

【図７Ｃ】参照画像146の一例を示す図である。

【図７Ｄ】いくつかの閾値におけるグレーマトリクス14
4と、それぞれ二つの参照画像146a及び146bとの間で計
算されたハミング距離のグラフである。

【図７Ｅ】いくつかの閾値におけるグレーマトリクス14
4の部分と、それぞれ二つの参照画像146aと146bの部分
との間のハミング距離のグラフである。

【図８Ａ】参照画像146の一例を示す図である。

【図８Ｂ】参照画像146の一例を示す図である。

【図８Ｃ】図8Aの参照画像146aの前景と背景によるグレ
ーマトリクス144の区分けを示す図である。

【図８Ｄ】図8Bの参照画像146bの前景と背景によるグレ
ーマトリクス144の区分けを示す図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ロジャー ディー メレン アメリカ合衆国 カリフォルニア州 94306， パロアルト スイート 200， ミランダ アベニュー 4009 キャノン リサーチ センター アメリカ， イン ク． 内

Claims (20)

【特許請求の範囲】
1. 【請求項１】 画像認識システムにおいて、マルチ・ビ
   ット値を有する複数のピクセルからなるサンプル画像を
   バイナリの参照画像の集合から認識する方法であって、 前記サンプル画像のサイズを前記参照画像のサイズまで
   正規化する正規化ステップと、 前記参照画像の集合から候補画像の集合を判定する判定
   ステップと、を有し、 前記候補画像の各々は、前記サンプル画像の異なる二値
   化からの距離が許容範囲内にあることを特徴とする方
   法。
2. 【請求項２】 更に、２つ以上の画像からなる候補画像
   の集合に応じて、認識を行うために望ましい候補画像を
   選択することによって前記候補集合を明確化する明確化
   ステップを有することを特徴とする請求項１に記載の方
   法。
3. 【請求項３】 前記明確化ステップにおいては、 正規化されていないサンプル画像のサイズまで前記候補
   画像を空間的に正規化し、 前記正規化された候補画像から候補画像の第２の集合を
   決定し、 候補画像の前記第２の集合の各々は、前記正規化されて
   いないサンプル画像の異なる二値化からの距離が許容範
   囲内にあることを特徴とする請求項２に記載の方法。
4. 【請求項４】 更に、２つ以上の画像からなる候補画像
   の前記第２の集合に応じて、幾何学的分析や文脈分析に
   よって望ましい候補画像を選択する選択ステップ、を有
   することを特徴とする請求項３に記載の方法。
5. 【請求項５】 前記判定ステップにおいては、 複数の閾値で二値化された前記サンプル画像と、参照画
   像の前記集合との間の距離の集合を計算し、 前記サンプル画像の第１の二値化からの距離が許容範囲
   内にある第１の参照画像を候補として選択し、 前記サンプル画像の第２の二値化からの距離が許容範囲
   内にある第２の参照画像を候補として選択し、 前記第１の二値化が前記第２の二値化とは異なる閾値を
   有することを特徴とする請求項１に記載の方法。
6. 【請求項６】 前記距離はハミング距離であることを特
   徴とする請求項５に記載の方法。
7. 【請求項７】 前記認識すべき画像は文字画像であるこ
   とを特徴とする請求項５に記載の方法。
8. 【請求項８】 前記判定ステップにおいては、各参照画
   像に対して、 前記参照画像の前景と背景に対応する前景部分と背景部
   分とに前記サンプル画像のピクセルを区分けし、 前記背景部分の最大ピクセル値に対応する第１の値を決
   定し、 前記前景部分の最小ピクセル値から１を減じた値に対応
   する第２の値を決定し、 前記第２の値以下である前記第１の値に応じて、前記参
   照画像を候補として選択し、 前記第２の値より大きい前記第１の値に応じて、 前記サンプル画像と前記参照画像との間の最短距離を計
   算し、 許容範囲内にある前記最短距離に応じて、前記参照画像
   を候補として選択することを特徴とする請求項１に記載
   の方法。
9. 【請求項９】 以前に選択された候補が前記参照画像の
   最短距離よりも小さい関連最短距離を有する場合、前記
   参照画像は候補として選択されないことを特徴とする請
   求項８に記載の方法。
10. 【請求項１０】 更に、前記参照画像の前記最短距離が
    ゼロであることに応じて、ゼロより大きい関連最短距離
    を有する、以前に選択された候補を廃棄することを更に
    含むことを特徴とする請求項８に記載の方法。
11. 【請求項１１】 前記正規化ステップにおいては、 複数のボックスからなる格子上へ前記サンプル画像をマ
    ップし、 各ボックス内に含まれる前記ピクセル値を合計し、 前記ピクセル値の合計を、正規化されたサンプル画像の
    対応する位置範囲内に格納することを特徴とする請求項
    １に記載の方法。
12. 【請求項１２】 前記格子によって二等分されるピクセ
    ルの値が前記ピクセルを含む前記ボックス間で比例分割
    され、 前記比例値は、整数演算を用いて行われる有理数計算を
    利用して算出されることを特徴とする請求項１１に記載
    の方法。
13. 【請求項１３】 マルチ・ビット値を有する複数のピク
    セルからなるサンプル画像をバイナリ参照画像の集合か
    ら認識するシステムであって、 前記サンプル画像のサイズを前記参照画像のサイズまで
    正規化する正規化ユニットと、 前記正規化ユニットと接続して、複数の閾値で二値化さ
    れた前記サンプル画像と、参照画像の前記集合との間の
    距離の集合を計算する距離計算ユニットと、 前記正規化ユニットと接続して、候補画像の集合を参照
    画像の前記集合から判定するための分類ユニットと、を
    有し、 前記候補画像の各々は、前記サンプル画像の異なる二値
    化からの距離が許容範囲内にあることを特徴とするシス
    テム。
14. 【請求項１４】 更に、前記分類ユニットと接続して、
    前記候補集合を明確化し、前記候補画像を正規化されな
    いサンプル画像と比較することによって認識を行うため
    に望ましい候補画像を選択するための明確化ユニットを
    有することを特徴とする請求項１３に記載のシステム。
15. 【請求項１５】 前記認識すべき画像は文字画像である
    ことを特徴とする請求項１３に記載のシステム。
16. 【請求項１６】 前記距離はハミング距離であることを
    特徴とする請求項１３に記載のシステム。
17. 【請求項１７】 マルチ・ビット値を有する複数のピク
    セルからなるサンプル画像をバイナリ参照画像の集合か
    ら認識するための、コンピュータ内に一体化されたコン
    ピュータ可読コードを有するコンピュータ可読媒体であ
    って、 前記サンプル画像のサイズを前記参照画像のサイズまで
    正規化する正規化ステップのコードと、 参照画像の集合から候補画像の集合を判定する判定ステ
    ップのコードとを有し、 前記候補画像の各々は、前記サンプル画像の異なる二値
    化からの距離が許容範囲内にあることを特徴とするコン
    ピュータ可読媒体。
18. 【請求項１８】 前記判定ステップのコードは、 前記参照画像の前景と背景に対応する前景部分と背景部
    分とに前記サンプル画像のピクセルを区分けするコード
    と、 前記背景部分の最大ピクセル値に対応する第１の値を決
    定するコードと、 前記前景部分の最小ピクセル値から１を減じた値に対応
    する第２の値を決定するコードと、 前記第２の値以下である前記第１の値に応じて、前記参
    照画像を候補として選択するコードと、 前記第２の値より大きい前記第１の値に応じて、 前記サンプル画像と前記参照画像との間の最短距離を計
    算し、 許容範囲内にある前記最短距離に応じて、前記参照画像
    を候補として選択するコードと、を有することを特徴と
    する請求項１７に記載のコンピュータ可読媒体。
19. 【請求項１９】 更に、認識を行うために望ましい候補
    画像を選択することによって前記候補集合を明確化する
    明確化ステップのコードを有することを特徴とする請求
    項１７に記載のコンピュータ可読媒体。
20. 【請求項２０】 前記明確化ステップのコードは、 正規化されていないサンプル画像のサイズまで前記候補
    画像を空間的に正規化するコードと、 前記正規化された候補画像から候補画像の第２の集合を
    決定するコードと、を有し、 候補画像の前記第２の集合の各々は、前記正規化されて
    いないサンプル画像の異なる二値化からの距離が許容範
    囲内にあることを特徴とする請求項１７に記載のコンピ
    ュータ可読媒体。