JP3482191B2

JP3482191B2 - 住所読み取りのための方法

Info

Publication number: JP3482191B2
Application number: JP2000618921A
Authority: JP
Inventors: シュスラーミヒャエル
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 1999-05-12
Filing date: 2000-04-04
Publication date: 2003-12-22
Anticipated expiration: 2020-04-04
Also published as: AU755267B2; JP2002544629A; EP1190373A1; DE50000887D1; DK1190373T3; NZ515488A; US6934405B1; ATE229201T1; CA2373207A1; EP1190373B1; WO2000070549A1; AU5058500A

Description

【発明の詳細な説明】

【０００１】住所読み取りシステムは、例えば手紙又は
小包のような郵便関係の発送物に存在するテキスト部分
から、特に受け取り人住所の領域から文字及び数字を認
識し、これらの文字及び数字の集合から配達情報を導出
するという任務を有する。このために、一連の認識方法
が使用される。これらの一連の認識方法は発送物を走査
した後でこの走査から結果的に得られる電子画像を徐々
に分析し、この電子画像の部分を分類し、この結果、最
終的に配達に重要な情報を電子テキスト形式で発生す
る。この部分ステップは、詳しく言えば、レイアウト分
析（発送物タイプ認識、関心領域/region of interest
（ＲＯＩ）の決定、行、単語及び/又は記号へのテキス
ト画像のセグメンテーション）、文字分類又はつながっ
た筆跡の認識及びこれらのテキスト部分の最終的な解釈
である。

【０００２】各認識方法の作動方式はパラメータによっ
て制御される。これらのパラメータの多くは予め設定さ
れた数学的な最適化規準を介してシステムの学習フェー
ズの間に推定/学習/トレーニングされる。これらのパラ
メータを以下においてトレーニング可能なパラメータと
呼ぶ。残りの全てのパラメータを以下では自由パラメー
タと呼ぶが、これらの自由パラメータにはこのような最
適化規準が欠如している。トレーニング可能なパラメー
タの推定にも自由パラメータの調整にも、いわゆる見本
発送物のサンプルが必要とされる。各サンプル要素は発
送物画像の部分及び要求される正確な解答（ラベル、目
標結果）から構成される。住所読み取りシステム全体に
対してそれぞれ完全な発送物画像及び配達情報から構成
されるサンプルが存在する。個々の認識方法ごとにもサ
ンプル（方法固有のサンプル）が存在し、これらのサン
プルはそれぞれ認識方法の入力画像及びその要求される
出力から構成される。学習サンプルとテストサンプルと
を区別する。学習サンプルはトレーニング可能なパラメ
ータの推定のために必要とされる。テストサンプルはト
レーニングされた認識方法のパフォーマンスの評価に使
用される。自由パラメータの適切な調整の方法は、様々
なパラメータ値による認識方法のパフォーマンスの反復
的な評価である。このプロセスは、数学的な意味におけ
る大域的な最適条件（globale Optimum）の発見が特に
存在せず、制限時間内での良好な認識パフォーマンスの
達成が存在する場合に、自由パラメータの最適化とも呼
ばれる。

【０００３】従来技術では、住所読み取りシステムの自
由パラメータは手動の反復的なテストによって調整され
る。様々なパラメータ調整は、開発者によって、部分的
にはヒューリスティックな尺度によって、部分的には方
法固有のテストサンプルに対するそれぞれの認識方法の
評価によって、さらに部分的にはテストサンプルに対す
る読み取りシステム全体の評価によって判定される。さ
らに、このプロセスの自動化を目指しているパターン認
識システムの分野の個々の刊行された論文が存在する。
これらのパターン認識システムは選択された自由パラメ
ータの調整のために数学的な最適化方法を使用し、この
数学的な最適化方法の理論は例えば[ Press et al. :Nu
merical Recipes in C, Cambridge University Press,
1992 ]、[ D.E.Goldberg, Genetic Algorithms in Sear
ch, Optimization & Machine Learning, Addison-Wesle
y, 1989 ]、[ I. Rechenberg, Evolutionsstrategien '
94, Frommann-Holzboog, 1994 ]に記述されている。特
に進化的/遺伝的アルゴリズムはこの場合しばしば適用
される。概要的論文[ Applying Genetic Algorithmson
Pattern Recognition: An Analysis and Survey, Y.-K.
Wang and K.-C. Fan, in Proceedings of the Interna
tional Conference on Pattern Recognition,1996 ]に
は３タイプの問題が区別されている。第１に特徴の選択
の最適化、第２に分類関数（Klassifikationsfunktio
n）の最適化、第３に分類子学習（Klassifikatorlerne
n）の最適化である。パターン認識システムの遺伝的最
適化のためのさらに他の論文は別冊[ Pattern Recognit
ion Letters: Special Issue on Genetic Algorithms,
Vol.16, No. 8, August 1995 ]に見出される。これらの
刊行物のやり方は次のようにまとめられる：１．既に評価されたパラメータ調整を考慮して自由パ
ラメータの１つ又は複数の異なる調整を選択する、２．テストサンプルに基づいてこのパラメータ調整
（これらの複数のパラメータ調整）を評価する、３．目指すパフォーマンスが達成された場合には終
了、さもなければ１に戻る。

【０００４】住所読み取りシステム内の認識方法に適用
すれば、これは次のことを意味する。すなわち、パラメ
ータ調整のパフォーマンスをテストサンプルに基づいて
測定するためには、このパラメータ調整の各評価に対し
てこの方法を完全にトレーニングしなくてならない、と
いうことを意味する。

【０００５】住所読み取りシステムにおける個々の認識
方法はそのトレーニングのために大きな学習サンプルが
必要であるという点で際立っている。このトレーニング
における面倒な計算は現代のワークステーションコンピ
ュータにおいて大抵の場合かなりの時間がかかる。よっ
て、数学的な最適化方法を使用する上述の技術はただ非
常に条件付きでのみ住所読み取り方法の自由パラメータ
の最適化に適しているだけである。というのも、良好な
結果を達成するためには平均して４ヶ月の計算時間が必
要だからである。

【０００６】従って、請求項１に記載の本発明の課題
は、住所読み取りシステムの自由パラメータをそれ自体
は公知のストラテジの助力で自動的にかつコスト安に最
適化する、住所読み取りのための方法を提供することで
ある。本発明の有利な実施形態は従属請求項に記載され
ている。

【０００７】ここに記述される方法は、住所読み取り方
法の自由パラメータの調整のプロセスを自動化しかつシ
ステム化し、これにより従来な最適化方法によるよりも
良好な結果を可能にする。住所読み取りシステムにおけ
る認識方法が複数の部分ステップに分割されるという事
実が徹底的に利用される。一般的に自由パラメータは個
々の部分ステップに割り当てられ、この結果、ストラク
チャリングは次のように実施される：認識方法の各部分
ステップの後で処理されたデータ（例えばサンプルの処
理された画像及び/又はトレーニングされたパラメータ
のセット）は中間記憶される。これらのデータは部分ス
テップの新たな呼び出しにおいて上書きされるまで保持
され続ける。既に行われた評価の後で自由パラメータを
変更しなければならない場合には、最初にこれらのパラ
メータがあらわれる箇所の部分ステップの実施が開始さ
れ得る。認識方法の完全な学習及びテストフェーズが最
初から実行される必要はない。このようにして著しい計
算時間コストが節約される。

【０００８】それゆえ、自由パラメータにはコストが割
り当てられる。この認識方法を新たな値に対して評価す
るために自由パラメータの値の変更の際にほんの僅かな
計算時間コストしかかからない場合には、この自由パラ
メータには僅かなコストを有する。これは、パラメータ
により影響を受ける１つ/複数の部分ステップがこれら
の部分ステップの実行シーケンスの相対的にかなり後ろ
の方にあることを意味する。逆に、自由パラメータの新
たな値の評価が大きな計算時間コストを必要としかつこ
れらの部分ステップの実行シーケンスが相対的にかなり
前の方で実行されなければならない場合には、この自由
パラメータは高いコストを有する。

【０００９】最適化方法は次のように実行される：最初
に、任意に選択された自由パラメータによる認識方法の
少なくとも１つの完全な評価が実施される。これは中間
記憶されたデータの初期化に使用される。これらの自由
パラメータの集合から高いコストのパラメータが選択さ
れ、これらのパラメータの値において保持される。他の
全ての自由パラメータは一般的に行われている数学的な
最適化方法に従って改善される。これは、まず最初に、
繰り返しこれらの自由パラメータの値が既に評価された
パラメータ調整を考慮して変化され、第２に、これらの
変化された値によってこの認識方法がトレーニングされ
評価されることによって行われる。この場合、トレーニ
ング及び評価は最初から開始する必要はなく、中間記憶
されたデータが利用される。パラメータ調整が数回評価
された後で、高いコストのパラメータの新しい集合が選
択され、それらの値において保持される。例えば、予め
保持されたパラメータのうちのいくつかが解放され、最
適化処理に取り入れられる。またしばらくの間最適化方
法がこれらのパラメータ値の改善のために使用され、次
いで新たにパラメータ値が選択される。このやり方によ
って、所定の時間で、これまでのやり方によって可能で
あったよりもはるかに多くのパラメータ調整が評価され
る。

【００１０】これらのコストは、その自由パラメータが
変化される最初の処理ステップ以後の予測された計算時
間によって決定される。

【００１１】有利には、住所は分類法を用いて読み取ら
れる。この分類法のパフォーマンスは認識率である。

【００１２】有利な実施形態では、システマティックな
概観的な評価を保障するために、コスト閾値は最も低い
パラメータコストから最も高いパラメータコストへと及
び/又はその逆に変化される。評価コストを小さく保持
するために、各自由パラメータをただ１つの処理ステッ
プに割り当て、処理ステップのパラメータは同一のコス
トを有すると有利であり、及び/又は、同時に同一のコ
ストを有する自由パラメータだけを変化させると有利で
ある。

【００１３】有利には、自由パラメータを進化ストラテ
ジに従って変化させる。この場合、親としての少なくと
も２つの異なるパラメータ値割り当てから複数の子孫が
発生され、これらの子孫のうちの最良のパフォーマンス
を有する少なくとも２つの子孫が新しい親として選択さ
れる。学習及びテストフェーズの全ステップは、予め新
しい親として選択されたのと同じ数の子孫に対してだけ
実行しさえすればよい。

【００１４】評価すべきパフォーマンスは、例えばＲＯ
Ｉ発見、筆跡認識のような当該認識方法のパフォーマン
スでもよく、読み取りシステム全体のパフォーマンスで
もよい。

【００１５】本発明を次に詳しく実施例において図面に
基づいて説明する。

【００１６】図１は手書き住所の読み取りのためのフロ
ーチャートである。

【００１７】図２は筆跡読み取り器の分類の自由パラメ
ータの進化的最適化を概略的に示している。

【００１８】図３は筆跡読み取り器のＨＭＭトレーニン
グのための自由パラメータの進化的最適化を概略的に示
す。

【００１９】住所読み取りシステムの構成要素は手書き
単語に対する認識方法である。その入力は単語画像及び
許容された単語のリスト、例えば都市名又はストリート
名である。出力としては許容された単語のうちの１つの
単語に対する単語画像の最も良好にマッチする割り当
て、すなわち単語の分類が予定される。

【００２０】この実施例で考察される筆跡読み取りシス
テムは、いわゆる隠れマルコフモデル（ＨＭＭ）による
確率的モデリングに基づいている。図１は筆跡読み取り
システムの経過及び基本的なモジュール及びその変動環
境への組み込みを示している。サンプルからの画像は少
なくとも以下のステップを実行する：まず最初に手書き
単語の画像が前処理される。この前処理３には、位置、
サイズ及び傾きに関する文字の正規化ならびに妨害、例
えばアンダーラインの除去が所属している。次いで、特
徴ウィンドウが段階的に左から右へとこの画像上を導か
れることによって、この前処理された画像から一連の特
徴ベクトル４が計算される。これらの特徴ベクトルの次
元は主軸変換（Hauptachsentransformation）Ｈ．Ａ．
Ｔ６によって低減される。最後に、これらのベクトルが
ベクトル量子化８される、すなわちコードブックの正規
分布の重み付けされた総和によって表現される。

【００２１】システムの変動の際には２つのフェーズが
存在する。これら２つのフェーズは繰り返し実施されな
ければならない：学習フェーズ及びテストフェーズであ
る。図１には破線は右側に学習フェーズが、左側にテス
トフェーズが図示されている。学習フェーズではこのシ
ステムは認識課題のためにトレーニングされる。このた
めに、手書き単語及びこれらの手書き単語の文字変換
（Transliteration）（電子テキスト形式における単語
の表現）の画像の膨大な学習サンプル２が使用される。
大きなパラメータ集合は学習サンプルの統計から推定さ
れる、例えば主軸変換行列５、コードブック７及びＨＭ
Ｍモデルパラメータ９（図１参照）。テストフェーズで
はこのトレーニングされたシステムがそのパフォーマン
スについてテストされる。すなわち、このトレーニング
されたシステムがどのくらい良好に手書き単語を読み取
れるか評価される。この評価は、手書き単語及びこれら
の手書き単語の文字変換の画像のテストサンプル１に基
づいて行われる。テストサンプルの各画像は分類１０の
ためにこのシステムに与えられる。各分類１０の結果が
画像の文字変換と比較され、これによって各画像毎に正
しく分類（認識）されたか又は間違って分類（認識）さ
れたかが判定される。全テストサンプルにわたって正し
く分類された単語画像の割合がもとめられる（認識率１
１、図１参照）。これによってこのシステムの認識パフ
ォーマンスの尺度が得られる。

【００２２】筆跡認識システムは若干数の処理ステップ
から成る。二、三の処理ステップはこのシステムの学習
フェーズにおいてのみ実行され（統計からの推定）、他
の処理ステップはテストフェーズにおいてのみ実行され
（分類及び認識率の計算）、残りの全ての処理ステップ
は学習画像によってもテスト画像によっても実行される
単語画像の表示形式の変換である（前処理、特徴抽出、
特徴低減、ベクトル量子化）。

【００２３】全ての処理ステップは若干数のパラメータ
を含み、これらのパラメータによってこれらの処理ステ
ップの作用が制御される。それ自体大量のパラメータを
統計的に推定する学習フェーズの処理ステップもその作
用においてはパラメータによって制御される。例えば、
コードブック推定７の際には若干数の正規分布密度の平
均値及び共分散行列が統計的に推定される。しかし、こ
の個数がどのくらいの大きさであるかは予め設定されな
ければならない。

【００２４】これらのパラメータはトレーニング可能な
パラメータと自由パラメータとに区別される。トレーニ
ング可能なパラメータの値は統計的推定から得られる。
これらのトレーニング可能なパラメータはここではこれ
以上考察しない。これに対して、自由パラメータにおい
てはこれらの自由パラメータの値をどのように選択すべ
きか不明瞭である。自由パラメータのいくつかの例は次
のようなパラメータである。

【００２５】前処理３小文字領域、アルファベットの小文字で一般的な小文字
よりも上に突き出た部分の領域及びアルファベットの小
文字で一般的な小文字よりも下に突き出た部分の領域の
正規化された高さ；特別な方法パラメータ特徴計算４特徴ウィンドウの幅及び特徴ウィンドウの段階的に動か
す際のステップ幅；特徴の個数；特徴の種類コードブック推定７正規分布密度の個数；推定方法の種類；特別な方法パラ
メータＨＭＭトレーニング９各文字に対するモデル状態の個数；文脈モデリングの種
類；特別な方法パラメータ自由パラメータの正しい調整は筆跡認識システムのパフ
ォーマンスにとって決定的な重要性を持つ。この目的
は、筆跡認識システムが良好な認識パフォーマンスを実
現するための自由パラメータの値を発見することであ
る。問題に依存せずに評価関数の最適条件を発見する多
数の数学的な最適化方法が存在する。これらの最適化方
法のやり方は、評価関数を繰り返し異なる入力値に対し
て評価し、関数値から巧妙なやり方で新しい入力値を導
出することである。このような最適化方法の例は最急降
下法、シンプレックス法、シミュレーテッド・アニーリ
ング（シミュレートされた焼きなまし）、進化的アルゴ
リズムである。

【００２６】理論的には筆跡認識システムの全ての自由
パラメータをこのような最適化方法で同時に最適化する
ことが可能であろう。評価関数はテストサンプルにおけ
る認識率である。この評価関数を具体的なパラメータセ
ットに対して評価するためには、まず最初に完全にこの
システムの学習フェーズを実施し、次いでテストフェー
ズを実施する必要がある。ここで考察される筆跡認識シ
ステムでは、ただ一つのこのような評価に現代の高性能
なワークステーションコンピュータにおいて２０時間ま
でかかってしまう。なぜなら、個々の処理ステップは膨
大な計算に結びついているからである。しかし、満足で
きる結果を得るためには、自由パラメータの個数に応じ
て規模において百から数千の評価が必要である。従っ
て、ただ一つの最適化実行は数ヶ月から数年の計算時間
を必要とする。これは実際にはまったく実用的ではな
い。

【００２７】以下に記述される方法は所要計算時間を大
幅に低減する。個々の評価のための計算時間を低減する
ために、この方法は筆跡認識システムの構造を適切なや
り方で利用する。筆跡認識システムにおける各処理ステ
ップ、例えば前処理又はコードブックの推定の後で、処
理されたデータは中間記憶される（例えば前処理された
画像又は推定されたコードブック）。これらのデータは
処理ステップの新たな呼び出しにおいて上書きされるま
で保持されつづける。既に行われた評価の後でただ１つ
のパラメータ値だけが変化されるべき場合には、初めて
このパラメータが現れる箇所における処理ステップの実
施を開始すればよい。このシステムの完全な学習及びテ
ストフェーズを実行する必要はない。例えばコードブッ
ククラスの個数が変化されるべき場合には、既存の低減
された特徴ベクトルが利用される。このやり方で著しい
計算時間コストが節約される。

【００２８】パラメータＰ_ｉのコストＣ（Ｐ_ｉ）は、こ
のパラメータの値だけが変化された場合にこのシステム
の評価のために必要とされる計算時間の推定として定義
される。この場合、この推定の正確さは副次的な重要性
しかもたない。決定的に重要なのは、パラメータのコス
トによるこれらのパラメータのオーダである。このオー
ダはコストから導出される。

【００２９】例えば前処理のパラメータはＨＭＭトレー
ニングのパラメータよりもコストが高い。パラメータは
これらのパラメータのコストに従ってグループ化され
る。各処理ステップの自由パラメータは１つの群にまと
められる。ここで記述される方法のアイデアは、高いコ
ストのパラメータ群をしばらくの間一定に保持し、低い
コストのパラメータ群だけを最適化することである。

【００３０】自由パラメータのコストを考慮しかつ中間
結果を使用して筆跡認識システムの自由パラメータを最
適化することが、進化ストラテジを使用する例において
示される。

【００３１】進化ストラテジは進化的アルゴリズムの下
位クラスであり、そのやり方において自然進化を指向し
ている。進化ストラテジの概念はこの場合［I. Rechenb
erg,Evolutionsstrategien '94, Frommann-Holzboog, 1
994］の場合のように使用される。生物学との類似にお
いて、各パラメータ値割り当ては個体の一意的な指定と
して及び遺伝子（ゲン）として捉えられる。個体の群は
集団（Population）と呼ばれる。１つ又は少数の最初の
個体（Ur-Individuen）から開始する。これらの最初の
個体は例えばランダムに発生されたパラメータ値割り当
てであればよい。これらの最初の個体は親として子孫の
個体の集団を発生する（再交配（Rekombination））。
各々の新しい個体は、２つの親の遺伝子（パラメータ値
割り当て）の混合（交叉（Crossover））によってなら
びに発生した遺伝子における容易なランダムな変化（突
然変異（Mutation））によって発生される。新しい個体
の適応度（Fitness）がもとめられる。すなわち、これ
らの新しい個体の品質がこれらの新しい個体のパラメー
タ値割り当てを有する最適化すべきシステムの評価に基
づいて判定される。新たな世代の親になるために、最高
の適応度を有する個体が選択され（選択）、残りは死滅
する（survival of the fittest）。個体の発生、評価
及び選択のこのプロセスは任意に長期間繰り返される。

【００３２】自由パラメータの集合はＦ＝｛Ｐ_ｉ｜ｉ＝
１．．．Ｎ｝で示される。これらの自由パラメータはそ
のコストに従ってＫ個の群Ｆ_ｋ＝｛Ｐ_ｉ｜C（Ｐ_ｉ）＝
ｃ_ｋ｝，ｋ＝１．．．Ｋにまとめられる。Ｋは筆跡認識
システムの処理ステップ数である。具体的な例における
やり方は次のようなものである（図２参照）。２０個の
個体（パラメータ値割り当て）が完全にランダムにその
許容された値域内部で発生される。図では各個体はその
パラメータ値のベクトルを表す矩形によって示されてい
る。各個体毎にまず最初に筆跡認識システムのトレーニ
ングフェーズが実行され、次いでテストフェーズが実行
される。

【００３３】図２では、初期個体は全部斜線によって示
されている。なぜなら、これらの初期個体の評価のため
に完全にトレーニング及びテストフェーズが実施されな
ければならないからである。これが初期評価である。こ
の後で、各個体毎に認識率が確定する。最高の認識率を
有する２つの個体が次に考察される。これが選択であ
る。これらの２つの個体は次の世代の親である。

【００３４】まず最初に、分類の処理ステップが改善さ
れる。分類の自由パラメータは例えばサーチビームの幅
及び棄却閾値（Rueckweisungsschwellwert/rejection t
hreshold）である。これら２つの親は次の特別の交叉操
作によって２０個の子孫を発生する。１４個の子孫は、
最良と評価された親部分から分類には所属しない全ての
パラメータの値割り当てを継承し、６個の子孫は２番目
に最良と評価された親部分から分類には所属しない全て
のパラメータの値割り当てを継承する。これは図２では
幅広い矢印によって示されている。ここで全２０個の子
孫に対してさらに分類のパラメータの値が決定されなけ
ればならない。子孫が第１の親部分からパラメータ値を
得るか又は第２の親部分から得るかが、各分類パラメー
タに対して個々に非決定論的に決定される。この場合、
最良と評価された親部分は確率１４/２０で選択され、
２番目に最良と評価された親部分は確率６/２０で選択
される。これは図２では個々の細い矢印で示されてい
る。

【００３５】次にこれらの２０個の子孫は突然変異され
る。分類パラメータの値が個々にこれら２０個の子孫の
各々において許容された値域内部でランダムに容易に変
更される。ランダム関数として正規分布が使用され、こ
の正規分布の平均値がパラメータの目下の値である。

【００３６】次にこれらの２０個の子孫が評価される。
まず最初に全ての非分類パラメータの値割り当てを最良
と評価された親部分から継承した１４個の子孫が評価さ
れる。最初の子孫の評価においてだけ一度この筆跡認識
システムの全処理ステップ（トレーニング及びテストフ
ェーズ）が実行されなければならない。残りの１３個の
子孫は分類パラメータにおいてのみ異なっており、従っ
て、各子孫に対して分類が実行されさえすればよい。こ
れは図２ではパラメータベクトル（個体）の斜線の領域
によって示されている。次いで、その他の６個の子孫が
評価される。これらの６個の子孫に対しては最初の１４
個の子孫と同様のことが行われる。

【００３７】最初のように、ここでこれらの２０個の評
価された個体から２個の最良の個体が新しい世代の親と
して選択される（選択）。これらの２個の個体は交叉及
び突然変異によってまた２０個の子孫を発生し、これら
の２０個の子孫が評価される。所定の世代数にわたって
分類パラメータだけが最適化される。次いで、これらの
分類パラメータの良好な値が「固定」され、先行する処
理ステップ、すなわちＨＭＭトレーニングのパラメータ
が最適化される。

【００３８】ここでＨＭＭトレーニングの処理ステップ
が改善される（図３参照）。ＨＭＭトレーニングの自由
パラメータは例えば各文字に対するモデル状態の個数、
文脈モデリングの種類及び特別な方法パラメータであ
る。２つの親が交叉によって２０個の子孫を発生する。
１４個の子孫は最良と評価された親部分からＨＭＭトレ
ーニングには所属しない全てのパラメータの値割り当て
を継承し、６個の子孫は２番目に最良と評価された親部
分からＨＭＭトレーニングには所属しない全てのパラメ
ータの値割り当てを継承する。これは図３では幅広い矢
印によって示されている。ここで全２０個の子孫に対し
てさらにＨＭＭトレーニングパラメータの値が決定され
なければならない。子孫が第１の親部分からパラメータ
値を得るか又は第２の親部分から得るかが、各ＨＭＭト
レーニングパラメータに対して個々に非決定論的に決定
される。この場合も、最良と評価された親部分は確率１
４/２０で選択され、２番目に最良と評価された親部分
は確率６/２０で選択される。これは図３では個々の細
い矢印で示されている。

【００３９】次にこれらの２０個の子孫は突然変異され
る。ＨＭＭトレーニングパラメータの値が個々にこれら
２０個の子孫の各々において許容された値域内部でラン
ダムに容易に変更される。ランダム関数として正規分布
が使用され、この正規分布の平均値がパラメータの目下
の値である。

【００４０】次にこれらの２０個の子孫が評価される。
まず最初に全ての非ＨＭＭトレーニングパラメータの値
割り当てを最良と評価された親部分から継承した１４個
の子孫が評価される。最初の子孫の評価においてだけ一
度この筆跡認識システムの全処理ステップ（トレーニン
グ及びテストフェーズ）が実行されなければならない。
残りの１３個の子孫はＨＭＭトレーニングパラメータに
おいてのみ異なっている。これらの１３個の子孫に対し
てはそれぞれＨＭＭトレーニング及び分類が実行されな
ければならない。これは図３ではパラメータベクトル
（個体）の斜線の領域によって示されている。次いで、
その他の６個の子孫が評価される。これらの６個の子孫
に対しては最初の１４個の子孫と同様のことが行われ
る。

【００４１】これらの２０個の評価された個体から２個
の最良の個体が新しい世代の親として選択される（選
択）。これらの２個の個体は交叉及び突然変異によって
また２０個の子孫を発生し、これらの２０個の子孫が評
価される。

【００４２】所定の世代数にわたってＨＭＭトレーニン
グパラメータだけが最適化される。次いで、これらのＨ
ＭＭトレーニングパラメータの良好な値が「固定」さ
れ、先行する処理ステップ、すなわちベクトル量子化の
パラメータが最適化される。このやり方が、コードブッ
ク推定、主軸変換の最適化によって継続され、さらに前
処理まで続けられる。次いで再び分類から開始され、分
類パラメータが再びしばらくの間最適化される。

【００４３】各パラメータ群の最適化のための世代数
は、この群におけるパラメータの個数ならびに最適化の
進行に依存して一緒に選択される。最適化の開始時には
例えば３つのパラメータを有する群が３世代にわたって
最適化される。全ての群が一度最適化され、再びＦ_ｋに
到達した後で、これらの全ての群は４世代にわたって最
適化され、その次の回には５世代にわたって最適化され
てゆく。４つのパラメータを有する群は４世代にわたっ
て最適化され、次に５世代にわたって最適化されてゆ
く。

【００４４】さらに、集団（Population）のサイズを群
のパラメータの個数に適合させることも有意義である。
３つのパラメータを有する群の場合には、２０個の子孫
の代わりに約１５個の子孫だけを発生すればよいだろ
う。これに対して、６つのパラメータを有する大きな群
の場合には、約３０個の子孫を発生すればよいだろう。

【００４５】これまで、本発明の実施例ではただテスト
サンプルにおける筆跡認識システムの認識率をパラメー
タ調整の評価尺度として使用してきた。筆跡認識システ
ムは住所読み取りシステムの中の複数の認識方法のうち
の１つでしかないので、さらに住所読み取りシステム全
体の読み取りパフォーマンスを評価尺度として使用する
ことは意味がある。一般的に、個々の認識方法の読み取
りパフォーマンスよりも住所読み取りシステム全体の読
み取りパフォーマンスをもとめることの方がはるかに面
倒である。他方で、パラメータ最適化の目的は住所読み
取りシステム全体の改善である。従って、ときどき住所
読み取りシステム全体の読み取りパフォーマンスをもと
めて、これから最適化における他のやり方に関して又は
新しいパラメータ群の選択に関して、例えば目標とした
読み取りパフォーマンスがすでに達成され終了できるか
どうかの判定を導出することは有意義である。［図面の簡単な説明］

【図１】図１は手書き住所の読み取りのためのフローチ
ャートである。

【図２】図２は筆跡読み取り器の分類の自由パラメータ
の進化的最適化を概略的に示している。

【図３】図３は筆跡読み取り器のＨＭＭトレーニングの
ための自由パラメータの進化的最適化を概略的に示す。

【符号の説明】

１テストサンプル２学習サンプル３前処理４特徴ベクトル５主軸変換行列６主軸変換７コードブック推定８ベクトル量子化９ＨＭＭモデルパラメータ１０分類１１認識率

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁷ 識別記号ＦＩＧ０６Ｎ 3/12 Ｇ０６Ｎ 3/12 (56)参考文献特開平５−165969（ＪＰ，Ａ) 特開平９−128490（ＪＰ，Ａ) 群化の要因に基づく遺伝的アルゴリズムを用いた輪郭線抽出手法，画像電子学会誌，日本，1996年，第25巻第５号，ｐｐ．495−503 画像のベイズ復元への遺伝的アルゴリズムの適用，電子情報通信学会論文誌, 日本，1994年９月，Ｖｏｌ．Ｊ77−Ｄ −ＩＩＮｏ．９，ｐｐ．1768−1777 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06K 9/00 - 9/82 B07C 3/14 G06N 3/00,3/12

Claims

(57)【特許請求の範囲】

【請求項１】パラメータにより制御された少なくとも
２つの処理ステップを有する住所読み取りのための方法
であって、該方法は学習フェーズ及びテストフェーズを
用いて最適化され、それ自体は公知の学習方法によって
学習サンプルに基づいてパラメータは自動的に適応さ
れ、住所読み取りのパフォーマンスはテストサンプルに
基づいて前記学習フェーズからの前記パラメータによっ
てもとめられ、各処理ステップは入力としてそのパラメ
ータの値及び先行する処理ステップの処理されかつ格納
されたデータを受け取り、少なくとも１つの処理ステッ
プは必要不可欠な入力としてサンプル要素を受け取り、
１つの処理ステップは読み取り結果をパフォーマンスと
して発生する、パラメータにより制御された少なくとも
２つの処理ステップを有する住所読み取りのための方法
において、前記学習フェーズにおいて学習サンプルによって自動的
には適応できない全ての自由パラメータにコストを割り
当てるステップ、コスト閾値を定めるステップ、パラメータ値割り当ての既にもとめられた全パフォーマ
ンスを考慮して、それ自体は公知の最適化ストラテジに
従って前記コスト閾値より下にある複数の自由パラメー
タを変化させるステップ、その自由パラメータが変化された最初の処理ステップか
ら開始して、前記学習サンプルに基づいて前記学習フェ
ーズを実行するステップ、そのパラメータが変化された最初の処理ステップから開
始して、前記テストサンプルに基づいて前記テストフェ
ーズを実行し、さらに瞬時のパラメータ値に対する住所
読み取りのパフォーマンスをもとめるステップ、最適化ストラテジに従って、定められた前記コスト閾値
より下にある自由パラメータをさらに変化させ、定めら
れたパフォーマンスが達成されるまで又は定められた数
の学習フェーズ及びテストフェーズが実行されるまで前
記学習フェーズ及び前記テストフェーズを引き続き実行
するステップ、新しいコスト閾値を定め、該コスト閾値より下にある１
つ又は複数の自由パラメータを最適化ストラテジに従っ
て変化させ、定められたパフォーマンスまで又は定めら
れた数の学習フェーズ及びテストフェーズが実行される
までパフォーマンスをもとめることによって前記学習フ
ェーズ及びテストフェーズを実行するステップ、前記コスト閾値を変化させ、住所読み取り全体の定めら
れたパフォーマンスが達成されるまで又は定められた全
コストを上回るまで前述のステップを実施するステッ
プ、適応されたパラメータによって瞬時の住所を読み取るス
テップを特徴とする、パラメータにより制御された少な
くとも２つの処理ステップを有する住所読み取りのため
の方法。
【請求項２】コストは、その自由パラメータが変化す
る最初の処理ステップ以後の予測される計算時間によっ
て決定されることを特徴とする、請求項１記載の方法。
【請求項３】住所は分類法を用いて読み取られ、この
分類法のパフォーマンスは認識率であることを特徴とす
る、請求項１記載の方法。
【請求項４】コスト閾値は最低のパラメータコストか
ら最高のパラメータコストまで及び/又はその逆に変化
されることを特徴とする、請求項１記載の方法。
【請求項５】各自由パラメータはきっちり１つの処理
ステップに割り当てられており、処理ステップのパラメ
ータは同一のコストを有することを特徴とする、請求項
１記載の方法。
【請求項６】同時に同一のコストを有する自由パラメ
ータだけが変化されることを特徴とする、請求項５記載
の方法。
【請求項７】自由パラメータは進化ストラテジに従っ
て変化されることを特徴とする、請求項１記載の方法。
【請求項８】処理ステップに対して又は読み取り方法
全体に対して少なくとも２つの異なるパフォーマンス値
割り当てが発生され、該少なくとも２つの異なるパフォ
ーマンス値割り当ては親として世代の子孫を発生し、こ
れらの子孫のうちの最良のパフォーマンスを有する少な
くとも２つの子孫が選択され、該少なくとも２つの子孫
もまた新しい世代の親として使用され、学習及びテストフェーズの全ステップは、予め新しい親
として選択されたのと同じ数の子孫に対して実行しさえ
すればよく、他の残りの子孫に対しては当該処理ステップ以後にのみ
トレーニングフェーズ及びテストフェーズが実行される
ことを特徴とする、請求項７記載の方法。
【請求項９】決定されたコスト閾値に対する変化にお
いて評価されるパフォーマンスは当該認識方法のパフォ
ーマンスであることを特徴とする、請求項１〜８のうち
の１項記載の方法。
【請求項１０】決定されたコスト閾値に対する変化に
おいて評価されるパフォーマンスは住所読み取り方法全
体のパフォーマンスであることを特徴とする、請求項１
〜９のうちの１項記載の方法。