JPH0877301A

JPH0877301A - 疑似２次元隠れマルコフモデルとｎ最良仮説を用いた劣化グレイスケール文書認識

Info

Publication number: JPH0877301A
Application number: JP7185551A
Authority: JP
Inventors: Shyh-Shiaw Kuo; クオシィ−シアウ; Chinching Yen; イエンチンチン
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1994-07-22
Filing date: 1995-07-21
Publication date: 1996-03-22
Also published as: US5754695A; EP0694862A3; EP0694862A2

Abstract

(57)【要約】（修正有）【目的】グレイスケール画像上の劣化した連結テキス
トの認識方法。【構成】グレイスケール疑似２次元隠れマルコフモデ
ルＨＭＭを用いて、文字やワードなどのテキスト要素を
含む画像を表す。画像に対する観測ベクトルは、グレイ
スケール光学式走査によって生成される。画素の特徴を
表すために、畳込み量子化グレイレベル、画素相対位
置、画素主ストローク方向の３つのコンポーネントが用
いられる。これらは、観測ベクトルとして構成され、こ
のベクトルは、本質的に連続し、各種フォントサイズが
一定であるうえに、各種量子化プロセスでの利用に対し
て融通性がある。このように、バイナリ化による情報落
ちや歪みが除去され、さらに、文書がバイナリの場合に
は（例えばファクス文書）、情報を失うことなく多重レ
ベルにサブサンプリングすることによって画像を圧縮す
ることができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、光学式テキスト認識に
関し、これをさらに詳細に述べると、文書の複製状態が
悪いなどの障害にも関わらず、文字またはワードを認識
するロバスト性に富んだ方法に関する。

【０００２】

【従来の技術】動的プログラミング技法を用いた隠れマ
ルコフモデル（ＨＭＭ）などの確率的モデルは、音声認
識の分野で広く利用されてきた。例えば、Ｊ．Ｗｉｌｐ
ｏｎ、Ｌ．Ｒａｂｉｎｅｒ、Ｃ．ＬｅｅおよびＥ．Ｇｏ
ｌｄｍａｎによる「ＡｕｔｏｍａｔｉｃＲｅｃｏｇｎ
ｉｔｉｏｎｏｆＫｅｙｗｏｒｄｓｉｎＵｎｃｏ
ｎｓｔｒａｉｎｅｄＳｐｅｅｃｈＵｓｉｎｇＨｉ
ｄｄｅｎＭａｒｋｏｖＭｏｄｅｌｓ（隠れマルコフモ
デルを用いた非拘束音声におけるキーボードの自動認
識」（ＩＥＥＥＴｒａｎｓ．Ａｃｏｕｓｔ．Ｓｐｅｅ
ｃｈＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ、１９９０
年１１月号第３８巻１８７０〜１８７８頁）と題する記
事を参照するとよい。また、音声認識に関する多くの問
題とよく似た問題が、光学的文字認識（ＯＣＲ）にも見
られることも、これまでに認められてきた。したがっ
て、確率モデリングと動的プログラミングもこの目的に
使用されてきた。例えば、Ｃ．ＢｏｓｅならびにＳ．Ｋ
ｕｏによる「ＲｅｃｏｇｎｉｔｉｏｎｏｆＤｅｇｒ
ａｄｅｄａｎｄＣｏｎｎｅｃｔｅｄＴｅｘｔＵ
ｓｉｎｇＨｉｄｅｎＭａｒｋｏｖＭｏｄｅｌｓ
（隠れマルコフモデルによる劣化した連結テキストの認
識）」（Ｐｒｏｃ．ｏｆｔｈｅ１１ｔｈＩｎ
ｔ．ＣｏｎｆｏｎＰａｔｔｅｒｎＲｅｃｏｇｎ
ｉｔｉｏｎ、１９９２年）と題する記事（１９９１年１
２月２３日に出願された米国特許０７／８１３，２２５
および１９９２年１１月２４日に出願された米国特許０
７／９８１０２８）を参照。

【０００３】

【発明が解決しようとする課題】最先端技術を用いたＯ
ＣＲのアルゴリズムは、通常、２層式画像（白い背景に
黒の文字）に基づいている。しかし、文書画像が２層式
であるという想定は、大抵の場合、正しくない。という
のは、第１に、現在の光学式スキャナは、グレイスケー
ル出力を行うからであり、第２に、文書の多くは本質的
にグレイレベルであるためである。例えば、印字テキス
トは、グレイレベルまたはカラー画像、あるいは、質感
のある背景に印字されている。さらに、通常、グレイレ
ベルの情報やノイズが収集プロセスの途中で加えられ
る。例えば、このグレイレベルの情報は、スキャナのポ
イントスプレッド機能によって生じるボケ効果によっ
て、あるいは、走査プロセスが劣悪な照度環境で行われ
た場合に、光学式出力に組み込まれる。このように、従
来技術の２値化プロセスがグレイレベル情報を含む文書
で行われた場合に、重大な劣化および／または情報落ち
が発生する可能性がある。テキストの光学的認識は、サ
イズがバラバラな文字や不鮮明な文書、あるいはゆがん
だ文字等の欠陥品の使用が障害になることが多い。した
がって、このような障害にもかかわらず、ロバスト性に
富んだ認識方法の改良が望まれている。

【０００４】

【課題を解決するための手段】ここでは、グレイスケー
ル画像による劣化した連結テキストの認識方法を開示し
ている。また、疑似２次元隠れマルコフモデル（ＰＨＭ
Ｍ）により文字を表している。グレイスケール画像のた
めの観測ベクトルは、グレイスケール光学式走査によっ
て得られる画素マップから作成される。画素の特性を表
すために、畳込み量子化グレイレベルコンポーネント、
画素相対位置コンポーネント、および画素主ストローク
方向コンポーネントの３コンポーネントが使用されてい
る。以上のコンポーネントは、本質的に連続し、各種フ
ォントサイズが一定であり、さらに、各種量子化プロセ
スでの使用に柔軟に対応できる観測ベクトルとして構成
されている。このようにして、２値化プロセスによる情
報落ちや歪みがなくなるうえ、文書が本質的にバイナリ
であるような場合（例えば、ファクス文書）、２層画像
は、情報の損失を伴わずに多重（グレイ）レベルへのサ
ブサンプリングによって圧縮されるので、はるかに短い
時間で圧縮画像を認識することができるようになる。さ
らに、グレイレベルの文書は、性能を犠牲にしなくて
も、バイナリの場合に比べてはるかに低い解像度で走査
ならびに処理される。このため、処理速度が大幅に向上
する。

【０００５】文字は、数多くの超状態を有する（各超状
態は少なくとも１状態を有する）疑似２次元ＨＭＭによ
って表される。好ましい具体例では、このような超状態
は、ワード画像による垂直方向のスライスを表してい
る。レベル構築構造に組み込まれたビタビアルゴリズム
を用いて特定のＰＨＭＭがワード画像の所定部分を表す
確率を計算することによって、ワード画像とＰＨＭＭと
の比較が行われる。予想されるモデルの各表現は、仮説
として概念化される。Ｎ最良仮説探索は、継続時間の制
約と組み合わせて実行される。モデル用のパラメータ
は、複数のルーチンを処理して作成される。Ｎ最良仮説
探索と呼ばれる技法は、上記のすでに開発された方法と
共に有利に利用できる。また、この仮説探索は、Ｎ最良
認識仮説を一つだけでなく複数提供する。さらに、この
ような仮説に後処理機能を課すことによって、認識率は
大幅に改善される。探索プロセスにおいて継続時間の制
約を用いることにより、前述の方法の効果が向上する。
この発明の前記およびそれ以外の諸相は、添付図面と実
施例から明白になるであろう。尚、文章中以下の記述が
採用されていることに注意されたい。

【表１】

【０００６】

【実施例】本発明によって認識されるワード画像は、通
常、ページ上に本文および図から成る大きい面積を占め
る主要部分の一部である。本発明を説明するに当たり、
ページは光学的に走査され、かつ認識対象となるワード
画像が従来のグレイレベルラスタ走査によって生成され
る一連の画素として把握されたものとする。このような
動作を実行する技術には、当業者によく知られているも
のがかなりある。例えば、「Ｐｒｏｃｅｅｄｉｎｇｓ
ｏｆｔｈｅＩＡＰＲＷｏｒｋｓｈｏｐｏｎＳｙ
ｎｔａｃｔｉｃａｎｄＳｔｒｕｃｔｕｒａｌＰａ
ｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ（構文および構造パ
ターン認識に関するＩＡＰＲセミナーの議事録）」（１
９８８年９月、フランス）のＨ．Ｂａｉｒｄによる「Ｇ
ｌｏｂａｌ−ｔｏ−ｌｏｃａｌａｎａｌｙｓｉｓ（全
体的分析から局所的分析）」の記事と、「Ｐｒｏｃｅｅ
ｄｉｎｇｓｏｆｔｈｅ８ｔｈＩｎｔｅｒｎａｔ
ｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＰａｔｔｅ
ｒｎＲｅｃｏｇｎｉｔｉｏｎ（第８回パターン認識国
際会議議事録）」（１９８６年１０月、パリ）のＳ．Ｓ
ｒｉｈａｒｉおよびＧ．Ｚａｃｋによる「Ｄｏｃｕｍｅ
ｎｔＩｍａｇｅＡｎａｌｙｓｉｓ（文書画像分
析）」の記事を参照するとよい。このような既知の文字
に対する画素シーケンスを用いて、文字を表すＨＭＭを
「トレーニング」する。したがって、以下に詳細に説明
するように、未知の文字列に対する画素シーケンスとモ
デルの比較が行われ、モデルがこのような未知の文字列
を表している確率を判断する。

【０００７】図１は、本発明による文字ｈに関する疑似
２次元ＨＭＭの状態図２００を付記した文字ｈの画素マ
ップ１００である。モデルは、画素マップの垂直グレイ
スケールラスタ走査の結果生じる一連の状態を示してい
ることから、「トップダウン、レフトライト」モデルと
いう名称を持っている。また、エルゴート的でない、す
なわち、完全に接続された２次元ネットワークではない
ことから、「疑似」２次元モデルと呼ばれる。

【０００８】状態図２００には、５つの「超状態」２１
０〜２１４が示されている。このような超状態は、それ
ぞれ、画素マップ１００における５つの垂直領域１１０
〜１１４に対応している。ただし、領域１１０〜１１４
のうちの所定の１領域における画素のすべてのカラム
は、いずれも同じ数の画素を有している。各超状態２１
０〜２１４に、画素マップ内の対応する領域のカラムに
可能な各種垂直方向の「状態」が示されている。例え
ば、超状態２１１は、それぞれ領域１１１のローにおけ
る白、黒、白の画素を表す３つの状態２２０〜２２２を
有している。ただし、「白い画素」と「黒い画素」は例
示を行う目的により記載されていることはいうまでもな
い。このような画素は、任意に選択されたグレイレベル
を表すことも可能である。２３０および２３１などの矢
印により、超状態間での遷移が可能であることが示され
ている。２３２のような矢印は、ある一定の超状態から
その状態自身への遷移が可能であることを示している。
同様に、２４０および２４１の矢印によって状態間の遷
移が示されており、２４２の矢印によって同じ状態への
遷移が示されている。状態図２００によって示されるモ
デル構造の別の案は、水平スライスを表した超状態を用
いたモデルである。

【０００９】ある状態から別の状態あるいは同じ状態へ
の遷移が行われる全確率の合計は、１に等しくなくては
ならない。例えば、遷移の確率は、矢印２３０、２３
１、および２３２で示される状態２１０からの各遷移と
対応づけられている。ある状態から別の状態へ遷移する
確率の合計は、画素数で測定された状態の継続時間の逆
数である。したがって、画素マップのラスタ走査におけ
るグレイレベルのセグメントの長さは、対応する遷移確
率によって示されている。つまり、長いセグメントは、
次の状態への遷移確率が低い状態に対応し、短いセグメ
ントは、遷移確率の高い状態に対応している。これと同
じ原理が超状態にも当てはまる。また、ノイズがある
と、特定のグレイレベルを有する画素を観測する確率に
影響する。テキスト要素の観測結果は、この画素に基づ
いている。この種の観測結果は、画素のグレイレベルの
特性に基づいており、他の種類の観測結果は、遷移また
は位置情報などの追加情報を含むことができる。このよ
うな追加情報が含まれている場合、各観測結果は、異な
る複数のコンポーネントを表すベクトル量になることが
ある。このような観測ベクトルの例について以下に説明
する。

【００１０】ここに記載する好ましい具体例に使用して
いる疑似２次元隠れマルコフモデルは、文字の継続時間
確率と呼ばれるコンセプトを採用している。文字Ｄ
（ｘ）の継続時間確率は、Ｄ（ｘ）＝Ｐ（ｍ＝ｘ）によ
って得られる。ただし、ｍはカラム単位で指定される。
同様に、超状態Ｄ_s：｛Ｄ_i：Ｏ≦ｉＮｓｕｂＶ；｝
の継続時間確率は、Ｄ_i（ｘ）＝Ｐ（ｍ＝ｘ）として定
義されている。ただし、ｍは、超状態ｉの継続時間であ
り、カラム単位で指定される。状態Ｄｊ／ｓ＝｛Ｄｊ／
１｜Ｏ≦ｉ≦Ｎ^j｝の継続時間は、Ｄｊ／ｉ＝Ｐ（ｍ＝
ｘ）として定義される。ただし、ｍは、超状態ｊ内の状
態ｉの継続時間であり、ｍは、画素単位である。

【００１１】基本的な疑似２次元隠れマルコフモデルを
表すうえで用いられるデータ構造は、以下の要素により
構成されている。超状態数（Ｎ_v）超状態の初期確率（ＩＩ_v）超状態遷移確率（Ａ_v）文字の継続時間確率Ｄ（ｘ）各超状態に対しては、超状態内の状態数（Ｎ_h）状態の初期確率（ＩＩ_h）超状態内の状態遷移確率（Ａ_h）超状態の継続時間確率Ｄ_i（ｘ）超状態内の各状態の観測確率（Ｂ_h）ならびに各状態に対しては、状態の継続時間確率Ｄｊ／ｉ

【００１２】観測ベクトルＯ_xyは、座標（ｘ，ｙ）にお
いて各画素ごとに定義される。観測ベクトルＯ_xyには、
３つのコンポーネントがあり、観測ベクトルの第１コン
ポーネントＯ_subbxy１は、次のように計算される。

【数１】ただし、ｍ_i,jは、（ｉ，ｊ）における画素のグレイレ
ベルであり、ｃ_xyは、図５に示されている３画素核によ
る３つの画素から得られたものとする。この核は、図４
に示すように、画素に重み係数を適用する。すなわち、
図４の核は、画素の配列から構成される全体画像につい
て効果的な畳込みを行っている。畳込みの目的は、ノイ
ズによって発生するグレイレベルの値に対する不規則性
の影響を削減することにある。周囲の画素も、中心部の
画素の特徴評価の一助となっている。その結果得られる
画素のグレイレベルの値（０〜２５５）は、１００レベ
ルに量子化される。

【００１３】Ｏ_xyの第２コンポーネントは、カラム内の
各画素の相対位置である。文書のレイアウト分析を行っ
た後、ベースラインの位置とトップラインおよびベース
ライン間の違いが既知であるものとする（トップライン
５００およびベースライン５０２の定義については、図
５を参照）。第２コンポーネントの実効値は、次の式に
より求められる。第２コンポーネント＝特徴画素からベ
ースライン５０２までの距離（画素単位）／／トップラ
イン５００からベースライン５０２までの距離

【００１４】さらに、５０レベルに量子化される。この
値は、ｇ、ｐ、ｑ等のベースラインより下にある部分に
対しては、当然、マイナスとなる。この特徴は、印字文
字のポイントサイズに関わらず、カラム内の各画素の位
置を示している。このように、前記特徴は、異なるアプ
リケーションにおいて一層ロバスト性が強化される。Ｏ
_xyの第３コンポーネントの値は、画素が存在する主スト
ロークの方向である。全体の画像は、「特許認可」１９
８６年第１９巻ｐ．４１〜４７のＪ．Ｋｉｔｔｌｅｒお
よびＪ．Ｉｌｌｉｎｇｗｏｒｔｈによる「ｍｉｎｉｍｕ
ｍｅｒｒｏｒｔｈｒｅｓｈｏｌｄｉｎｇ（最小誤り
スレッショルド）」にはるかに詳細に述べられているス
レッショルドのプロセスを必要とする。各画素ごとに、
（連続した黒い画素による）ストロークの長さが、０
°、４５°、９０°、１３５°の４方向に計算され、主
ストローク方向として、その画素を通過する最長ストロ
ークが選択される。第５番目の「方向」は、背景画素を
対象としており、方向またはストロークを対象にした定
義は一切ない。このため、Ｏ_xyには、５つの別個のコン
ポーネント値がある。

【００１５】疑似２次元ＨＭＭは、２次元のゆがみを考
慮に入れているため、モデルのロバスト性が大幅に向上
していることから、弾性のテンプレートとして考えるこ
とができる。例えば、ファクシミリによる送信中によく
起きるような垂直のゆがみは、本発明による方法によっ
て調整可能である。疑似２次元２ＨＭＭの状態図におい
て、状態間のトップからボトムへの遷移のみが許可され
（例えば、矢印２４１で示されるように、１状態をスキ
ップすることもあり得る）、超状態間の左から右への遷
移のみが許可される（例えば、矢印２３１で示されるよ
うに、１超状態をスキップすることもあり得る）。上記
の通り、文字が不鮮明の場合、あるいは、異なる文字フ
ォントが使用されている場合は、スキップされた状態が
発生することがある。本発明では、スキップを行う状態
および／または超状態が全く起こり得ないものと想定し
ている。

【００１６】ビタビアルゴリズムは、ある特定のＨＭＭ
が一連の観測に対して一致する確率を計算する際に利用
可能な周知の動的プログラミング法である。このアルゴ
リズムは、例えば、「Ｐｒｏｃｅｅｄｉｎｇｓｏｆ
ｔｈｅＩＥＥＥ（ＩＥＥＥ議事録）」１９８９年２月
号第７７巻ｐｐ．２５７〜２８６に記載されているＬ．
Ｒａｂｉｎｅｒによる「ＡＴｕｔｏｒｉａｌｏｎ
ＨｉｄｄｅｎＭａｒｋｏｖＭｏｄｅｌｓａｎｄ
ＳｅｌｅｃｔｅｄＡｐｐｌｉｃａｔｉｏｎｓｉｎＳ
ｐｅｅｃｈＲｅｃｏｇｎｉｔｉｏｎ（音声認識におけ
る隠れマルコフモデルと選択アプリケーションに関する
論文）」と題する記事に説明されている通り、音声認識
に広く使用されている。また、上記の本願の譲受人に譲
渡された米国特許第０７／８１３，２２５に記載されて
いるように、ビタビアルゴリズムは、テキスト認識にも
使用されてきた。

【００１７】ビタビアルゴリズムによれば、各観測ご
とに、ＨＭＭの各状態における確率δが計算され、その
結果、通常、確率の「トレリス」と呼ばれるＮｘＴ配列
となる。ただし、Ｎは状態数であり、Ｔはシーケンスに
おける観測数とする。シーケンスの最後の観測後のこの
ような最高確率Ｐ＊は、この一連の観測に関しては、Ｈ
ＭＭの「点数」として用いられる。また、モデルにより
最良のパスを判断するための状態シーケンスのトラッキ
ングプロセスは、セグメンテーションとして知られてい
る。複数のアプリケーションに対して、実際の状態シー
ケンスが復元できるようにバックポインタの配列も維持
される。説明を簡単にするため、本書を通じて用いられ
る用語「状態」は、状態および／または超状態を指すも
のとする。すべてのＴ観測が明らかになった後、ＨＭＭ
の最終確率が選択され、次に示す最後の観測後に計算さ
れる最大確率となる。

【数２】ただし、Ｐ＊に関連した最終状態は、以下の通りであ
る。

【数３】通常、このような状態は、状態Ｎである。しかし、最終
観測後の最大観測が状態Ｎ以外の状態と関連している場
合もある。音声処理や文字認識のようなＨＭＭのアプリ
ケーションの中には、最大確率ではなく、ＨＭＭの確率
として最終観測後に状態Ｎについて計算された確率を用
いる場合に選択されるものもある。疑似２次元ＨＭＭに
は、超状態および各超状態内の状態に対し、ビタビアル
ゴリズムが繰り返し用いられる。したがって、このよう
なＰＨＭＭは、真の２次元ではなく、入れ子型１次元モ
デルとして扱われる。

【００１８】図２は、ワード画像の画素マップを本発明
による一連の疑似２次元ＨＭＭと比較するためのプログ
ラムされたコンピュータの動作を示すフローチャートで
あり、図中、超状態は垂直スライスを表している。ステ
ップ３００〜３０７は、メインルーチンを示しており、
このルーチンでは、ビタビアルゴリズムを用いて、ある
特定のカラムの画素が特定の超状態に所属している確率
Ｐ＊から画像のセグメントの最大確率を計算する。メイ
ンルーチンのステップ３０１および３０４は、各々ステ
ップ３１０〜３１８に示すサブルーチンを用い、このサ
ブルーチンでは、各コラムごとに、このような確率Ｐ＊
を計算するための各超状態のビタビアルゴリズムを用い
る。画素マップを形成する観測とＨＭＭの各種パラメー
タが、計算を行うコンピュータの適正なメモリ領域に記
憶されているものとする。

【００１９】メインルーチンの開始時点で、第１カラム
の観測がアドレス指定される（ステップ３００）。その
後、このような観測を用いてサブルーチン（ステップ３
１０〜３１８）が実行される。このようなサブルーチン
の開始と同時に、第１超状態に対するＨＭＭ状態パラメ
ータＮ_v、π_v、Ａ_v、Ｂ_vがアドレス指定され（ステップ
３１０）、さらに現行カラムの第１観測が検索され（ス
テップ３１１）、次式により適正なパラメータπ_vおよ
びＢ_vを用いて、超状態の初期状態確率が計算される。

【数４】ただし、Ｎは状態数に等しく、π_iは初期状態が状態ｉ
である確率に等しく、ｂｉは状態ｉにおける所定の観測
確率に等しく、Ｏ１は実際の初期観測に等しい。現行ロ
ーにおける次の観測が検索され（ステップ３１３）、適
正なパラメータＮ _h、Ａ_h、およびＢ_hと次式を用いて次
の状態確率セットが計算される（ステップ３１４）。

【数５】ただし、Ｔは観測数に等しく、ａ_ijは状態ｉから状態ｊ
への遷移確率に等しい。この等式により、各状態を通過
する最良のパスが創出される。ローにおける最後の観測
（ステップ３１５）後、このようなカラムと現行超状態
の確率Ｐ＊は、カラムの最終状態に対して計算された最
後の確率であり、最終観測（ステップ３１６）後に計算
された最大確率ではない。しかし、Ｐ＊およびｑ_t＊に
ついての等式と共に上に説明した通り、最終観測後に最
終状態について計算された確率は、通常、最大確率とな
る。任意の後処理ステップ（ステップ３１７）が示され
ているが、このステップは、以下に述べるように、本発
明の方法に対する各種の改善に利用可能である。

【００２０】さらに多くの超状態がある場合（ステップ
３１８）、次の超状態の状態パラメータのアドレス指定
が行われ（ステップ３１９）、現行カラムと次の超状態
に対してステップ３１１〜３１８が繰り返される。この
ため、サブルーチンは、現行カラムと各超状態に対して
確率Ｐ＊を返す。ステップ３０１で開始したサブルーチ
ンから出ると、観測Ｏ_xyのこのような返された確率Ｐ＊
を用いて、ＨＭＭ超状態パラメータπ_v、Ｂ_v、および等
式（１）から初期の確率が計算される（ステップ３０
２）。さらに、次のカラムがアドレス指定され（ステッ
プ３０３）、サブルーチンが繰り返され（ステップ３０
４）、等式（３）、適正なＨＭＭパラメータＮ_v、Ａ_v、
Ｂ_v、および観測Ｏ_xyに対してサブルーチンによって返
された確率Ｐ＊を用いて、次の超状態確率セットを計算
することにより、超状態の最良パスを延長する（ステッ
プ３０５）。さらに多くのローがある場合（ステップ３
０６）、次のローに対し、ステップ３０３、３０４、お
よび３０５が繰り返される。最後に、最終ローの後で、
ＨＭＭが比較されているテキスト要素を表す最終尤度点
数が、最終超状態に対して評価された最終確率となる
（ステップ３０７）。さらに、これから説明される改良
を目的とした任意の後処理ステップ（ステップ３０８）
が示されている。上記の方法が、超状態が水平スライス
を表しているＨＭＭにも利用可能なことは、明らかであ
る。そのような場合、「カラム」への参照は、「ロー」
への参照で置き換えることができる。

【００２１】ＨＭＭに用いられる計算の多くは、複合的
な確率の積の計算を含んでいる。大抵の場合、そのよう
な計算は対数形式に変換した方が便利であり好ましい。
このような計算に対数を用いた場合、数値精度に関する
問題を回避するだけでなく、積を和に簡素化し、他方で
未知数を各種モデルと比較して最適モデルを見つけ出す
場合に必要となる相対値の関係を維持する働きをする。

【００２２】パラメータπ、Ａ、およびＢの見積りは、
「ＡＴ＆ＴＴｅｃｈＪ．（ＡＴ＆Ｔ技術ジャーナ
ル）」１９８６年５月号第６５巻ｐｐ．２１〜３６に記
載されているＬ．Ｒａｂｉｎｅｒ、Ｊ．Ｗｉｌｐｏｎ、
およびＢ．Ｊｕａｎｇによる「ＡＳｅｇｍｅｎｔａｌ
Ｋ−ＭｅａｎｓＴｒａｉｎｉｎｇＰｒｏｃｅｄｕ
ｒｅｆｏｒＣｏｎｎｅｃｔｅｄＷｏｒｄＲｅｃ
ｏｇｎｉｔｉｏｎＢａｓｅｄｏｎＷｈｏｌｅＷ
ｏｒｄＲｅｆｅｒｅｎｃｅＰａｔｔｅｒｎｓ（ワー
ド全体参照パターンに基づく連結ワード認識のためのセ
グメント型ｋ平均トレーニング法）」と題する記事に説
明されているセグメント型ｋ平均アルゴリズムを用い
て、疑似２次元ＨＭＭに対して行われる。図３は、疑似
２次元ＨＭＭを生成する手順を示すフローチャートであ
る。まず初めに、モデルの構造、すなわち、超状態およ
び各超状態中の状態の数が決定される（ステップ３５
０）。これは、画素マップを生成するＨＭＭによって表
されるテキスト要素の明確に定義されたサンプルのグレ
イレベル走査を行い、画素マップの各ローにおける遷移
をカウントし、さらに、同数の遷移および似ているが必
ずしも同一でないグレイレベルの画素を有する隣接ロー
をグループ化することによって実行できる。したがっ
て、各グループは超状態に対応し、グループ内のローに
おける遷移数は超状態内の状態数より小さい数に相当す
る。例えば、図１の画素マップ１００について再度説明
すると、領域１１２の２つの隣接カラムには、それぞ
れ、２つの遷移と同数の黒および白の画素があり、３つ
の状態を有する超状態に対応している。領域１１３のカ
ラムにも２つの遷移が含まれているが、領域１１１のカ
ラムと比べて非常に異なった数の黒および白の画素を有
しており、領域１１３のカラムは領域独自の超状態を形
成している。

【００２３】各文字モデルの超状態および状態数は、画
像トポロジによって決定される。まず初めに、画像の初
期ブロックとして原始カラムが使用され、次に、最高相
互相関係数を有する２つの隣接ブロックがグループ化さ
れて、１つの大きいブロックになる。所定数のブロック
だけが残るまで、あるいは、ある一定の相関係数の点数
しきい値に達するまで、上記した同一のグループ化プロ
セスが繰り返される。例えば、最終ブロック数は、文字
トポロジを調べることによって判断可能であり、グルー
プ化プロセスが開始する前に取得できる。このようなカ
ラムの垂直ブロックが形成された後、カラムに対して行
われたのと同じプロセスにより、各垂直ブロックを検査
してブロック内のローをグループ化する。

【００２４】図６は、画像「ｂ」に対する最終的なグル
ープ化（切断）を示している。この図からわかるよう
に、文字「ｂ」は、４つの超状態と各超状態内の状態
３、３、５、３をそれぞれ有するＰＨＭＭにより表すこ
とができる。切断が行われる正確な位置は、この繰り返
しによる相関比較によって自動的に決まる。このこと
は、ノイズやボケを伴うグレイレベル画像に対しては特
に重要であり、これは、手操作により異なる文字やサン
プルに対して意味のある効率的な一貫したセグメンテー
ション（グループ化）を行うことが難しいためである。
各文字ごとに、若干の標本画像に対して上記手順が繰り
返される。セグメンテーションに基づき、対象の文字に
対してＰＨＭＭの初期推定が行われる。ただし、この手
順は、トレーニングプロセスの開始に利用できるＰＨＭ
Ｍの初期推定値が全くない場合にのみ必要とされる。

【００２５】次に、モデルに対するパラメータが初期化
される（ステップ３５１）。これは、前記構造を生成す
る際に用いられるサンプルから派生した上記のパラメー
タを用いて実行できる。モデルの構造が生成され、かつ
パラメータが初期化された後、モデルを「トレーニン
グ」することによって、パラメータの値を推定しなおす
ことができる。トレーニングは、認識されるテキストに
画像が取り入れられることが予想される形式のワード画
像の代表的なサンプル（トークン）を用いて行われる
（ステップ３５２）。各トークンごとに観測シーケンス
（画素マップ）が生成され、さらに、ビタビアルゴリズ
ムを用いて、モデルに関する観測シーケンスのセグメン
テーションを行う（ステップ３５３）。パラメータは、
セグメンテーションの結果によるヒストグラムにしたが
って更新される（ステップ３５４）。例えば、パラメー
タπ_i、ａ_ij、およびｂ_iの更新された推定値は、以下の
通りである。 π_i＝状態Ｓｉから開始するトークンの数／／トークン
の総数ａ_ij＝状態Ｓｉ状態Ｓｊからの遷移数／／状態Ｓ_iから
開始する遷移総数ｂ_i（ｐ）＝状態Ｓ_iにおけるｐの観測数／／観測の総数

【００２６】推定のやり直しを行っている間、ビタビア
ルゴリズムを用いて、モデルに関しては、各トークンご
とに尤度を計算し、トークンに関しては、全トークンに
対するこのような尤度を組み合せて（確率は乗算、対数
確率は加算）、モデルの有効性に関する全体の尤度を提
供する（ステップ３５５）。全トークンが処理された後
（ステップ３５６）、パラメータが収束した場合、すな
わち、このような全体的測度が最大値にほぼ達した場
合、トレーニング手順は完了する（ステップ３５７）。
そうでない場合は、トレーニング手順が繰り返される。
収束を判断する代表的な方法では、継続的な繰り返しを
行うために、ステップ３５５から全体尤度を比較する。
差が小さく、最後の繰り返しの途中でパラメータが大幅
に変化したことを示している場合は、収束が行われたと
みなすことができる。２次元ＨＭＭに対しては、超状態
のパラメータＩＩ_h、Ａ_h、およびＢ_hと超状態における
状態のパラメータＩＩ_v、Ａ_v、およびＢ_vが、すべてこ
の方法によって判断可能である。技術上周知の他の方法
を用いて、ＨＭＭのパラメータを推定することもでき
る。例えば、Ｂａｕｍ−Ｗｅｌｃｈ再推定式および一般
化確率的降下方法などがある。

【００２７】従来のＨＭＭでは、継続時間ｄ_iの間ある
状態を維持する確率（確率密度）が以下の式により表さ
れる指数関数である。

【数６】ただし、ａ_iiは自己遷移確率であり、ａ_ijは次の状態へ
の遷移確率である。しかし、実際の施行においては状態
継続時間の分配により、結果として指数確率密度が得ら
れる可能性が少なくなるため、ＨＭＭにより精巧な状態
継続時間を導入することによって、性能を大幅に改善で
きる。

【００２８】次に説明するのは、継続時間を含む１方法
である。上記のパラメータＩＩ、Ａ、およびＢを用い
て、まず初めに状態へのセグメンテーションが行われ、
次に、最良パスにおける各状態ごとにより適正な確率密
度のパラメータを検索する配列Ψからのバックポインタ
を用いて、セグメンテーションの最中に計算された点数
が後処理ステップで調整される。このような調整例とし
て、各状態に対する自己遷移確率をガウス状態継続時間
確率密度に置き換えることなどが挙げられる。

【００２９】各状態または超状態ｑ_iに対し、このよう
な調整が、次式により実行可能である。

【数７】ただし、括弧で囲まれた最初の項は、指数確率密度を抽
出し、括弧内の第２項はガウス確率密度を挿入し、ａ_ii
は自己遷移確率であり、ｄ（ｉ）は画素数による実際状
態継続時間であり、ｄ₀（ｉ）はその平均であり、σ_iは
状態継続時間の標準偏差である。所定の状態に対するｄ
の値は、状態または超状態での自己遷移数をカウントす
ることにより、配列Ψから判断される。ｄ₀（ｉ）およ
びσ_iの値は、次式により、トレーニング中の各状態ま
たは超状態に対して出すことができる。

【数８】

【数９】ただし、Ｎは、状態ｑ_iになる回数であり、ｄ_i（ｋ）は
ｋの継続時間である。最終確率Ｐ＊が通過するすべての
状態に対する確率の積であることから、今度は、通過す
る各状態の平均および標準偏差を用いて、Ｐ＊に関して
このような調整を繰り返し行うことができる。Ｐ＊が対
数として表される場合、これらの調整を対数形式に変換
し、通過する各状態に対するこのような対数型調整を合
計し、さらに、調整の総計を対数Ｐ＊に加算することに
よって、調整を行うことができる。

【００３０】入れ子型ビタビ探索構造では、ここに記載
されている好ましい具体例により、パス探索プロセスの
一部として、継続時間のペナルティが組み込まれてい
る。継続時間ペナルティを最終確率Ｐ＊に組み込むに
は、次式により、尤度を各ノードにおいてパス方向に更
新しなければならない。ｌｉｋｅ（ｉ，ｋ）＝最大［尤度（ｉ，ｔ−１）＋ａ
（ｉ，ｉ），尤度（ｉ−１，ｔ−１）＋ａ（ｉ−１，
ｉ）＋状態（または超状態，文字）継続時間ペナルテ
ィ］＋ｂ_i（Ｏ_k）ただし、ｂ_i（Ｏ_k）はノードｉ（観測Ｏ_kを生成するた
めに超状態または状態になることがある）の尤度であ
り、尤度（ｉ，ｋ）は最高ノードｉおよびフレーム（ま
たは画素）ｋまで累積されたパス尤度点数であり、継続
時間ペナルティは、継続時間確率のマイナスの対数尺度
である。継続時間確率は、状態、超状態、および文字の
継続時間の長さに関するヒストグラムを計算することに
より、トレーニングを通じて検出される。状態のヒスト
グラムは、画素単位であり、超状態および文字のヒスト
グラムは、カラム単位である。上記の式からお気づきの
通り、継続時間ペナルティは、異なる状態、超状態、ま
たは文字の間で遷移が発生する場合にのみ加えられる。
文字継続時間ペナルティは、任意の文字モデルの最終超
状態から遷移が行われた時点の超状態継続時間ペナルテ
ィの上に加えられる。このように、継続時間ペナルティ
は、後処理としてではなく、順方向探索に組み込まれ
る。この継続時間ペナルティの組み込みにより、文字認
識性能が向上する。また、（後に述べる）Ｎ最良方法と
共に使用された場合、上記組み込みによって、より良い
ワード候補を提供することも可能であり、特に、最良候
補が正しくない場合にこのような用い方が考えられる。
さらに、正しく高水準な後処理（例えば、辞書チェッ
ク）に対し、探索サイズを大幅に縮小できる。

【００３１】後に説明するレベル構築アルゴリズムの終
わりに、最適パスをさかのぼることによって、文字モデ
ルの最良の組み合わせを識別できる。対応するワード
は、アルゴリズムによって認識されるワードである。認
識確度は、後述するＮ最良探索を組み込むことにより、
大幅に改良できる。これに適したグローバルＮ最良仮説
アルゴリズムが、「Ｐｒｏｃ．ＤＡＲＰＡｓｐｅｅｃｈ
ａｎｄＮａｔｕｒａｌＬａｕｎｇｕａｇｅＷｏ
ｒｋｓｈｏｐ（ＤＡＲＰＡ音声および自然言語セミナー
の議事録）」１９９０年６月号ｐｐ．１２〜１９に記載
されているＦ．Ｋ．ＳｏｏｎｇおよびＥ−Ｆ．Ｈｕａｎ
ｇによる「Ａｔｒｅｅ−ｔｒｅｌｌｉｅｓｂａｓｅ
ｄｆａｓｔｓｅａｒｃｈｆｏｒｆｉｎｄｉｎｇ
ｔｈｅｎｂｅｓｔｓｅｎｔｅｎｃｅｈｙｐｏｔ
ｈｅｓｅｓｉｎｃｏｎｔｉｎｕｏｕｓｓｐｅｅｃ
ｈｒｅｃｏｇｎｉｔｉｏｎ（連続音声認識におけるｎ
最良センテンス仮説を検出するための木構造トレリスベ
ースの高速探索）」に説明されており、上記アルゴリズ
ムは、順方向ビタビベースのトレリス探索と逆方向木構
造探索を組み合わせている。ここに開示されている好ま
しい具体例によれば、ＳｏｏｎｇおよびＨｕａｎｇによ
って開示されたアルゴリズムは、次に述べるように強化
され、改良された仮説探索アルゴリズムを提供してい
る。この強化には、順方向探索への継続時間ペナルティ
の組み込みも含まれており、パスマップと順方向パスか
らの継続時間情報を用いて、逆方向探索によるペナルテ
ィ修正を行っている。その結果、後に極めて詳細に述べ
るように、認識性能は大幅に強化されている。

【００３２】以上のように強化されたＮ最良仮説アルゴ
リズムにしたがって、まず初めに入れ子型ビタビ順方向
探索を実行し、次に逆方向探索を行うことにより、Ｎ最
良仮説が得られる。逆方向探索がメインパススタックを
中心に行われ、ここでは、スタックの各項目がトリーの
分岐（パス）であり、パス尤度点数にしたがって、スタ
ックの上から下へランク付けが行われている。バックト
レーシングを行うパスは、当然、終端ノードから開始し
なければならない。全レベルにおける各文字モデルの各
終端ノードごとに、ビタビ探索後に得られた最終累積パ
ス点数にしたがって、１終端ノードのみを含むヌルパス
が構成される。前記パスは、パス点数にしたがって、ラ
ンク順に１本ずつ挿入される。この時点では、パス点数
がビタビ探索での累積尤度点数と依然等しいことを忘れ
てはならない。また、修正は、まだ全く行われていな
い。上記パスは、初期ノードに向かって逆方向に伸展す
る（例えば、右から左へ、フレーム０の方向へ）。パス
が伸びる方向を識別し、かつ逆方向の伸展がまだ完了し
ていないことを示すために、このようなパスには「逆方
向部分パス」という名称が付けられている。この逆方向
部分パスの先端にあるノード、すなわち、左端のノード
を、ここでは「フロントノード」と呼ぶ。フロントノー
ドが初期ノードと等しい場合、パスの逆方向の伸展は
「完了」する。Ｍがスタックサイズであれば、最上位の
Ｍのヌルパスがスタックに入れられた後（他のすべての
パス点数のうち最高のパス点数を有するもの）、初期ス
タックの設定は終了する。

【００３３】図７について説明すると、メインパススタ
ック１０００内の全Ｍパスが処理されるまで次に説明す
るプロセスが繰り返される。このプロセスは、パススタ
ック１０００から最上位パス１０１０を取り除くことか
ら開始する。この最上位パス１０１０は、当面、すべて
のパスの中で最高のパス点数を有しているパスである。
最上位パス１０１０が本パラグラフで説明するプロセス
をすでに経ている場合、最上位パス１０１０をパススタ
ック１０００に戻し、パススタック１０００の次のパス
１０２０を取り出す。最初の非完了パスに対しては、こ
こに説明するプロセス（ブロック１０５０）により、パ
スを２本の別々のパスに分ける。そのうちの第１パス１
０８０は、最良の１アーク（逆方向）延長線を有し、第
２パス１０９０は、予想可能な残りのすべての延長線を
有している。次に、スタック全体がなお分類順を維持す
るように、更新されたパス点数にしたがって、前記２本
の「新規」パスをパススタックに挿入し直す（ブロック
１０６０および１０７０）。この非完了パスが到来パス
をわずか１本しか利用できない場合、パス分割を一切行
わないこともあり得る。アーク延長が一回行われ、延長
されたパスは、パススタックに挿入し直される。

【００３４】図８は、順方向ビタビ探索から得られたパ
スマップのごく一部であり、逆方向木構造探索にも用い
られる。大文字は、超状態ノードを表している。文字列
として配置された場合、完了パスの一部を表すために使
用することもできる。例えば、ＡＢＣＦＧは、図８のパ
ス２の一部を表し、ｆ_x（ｙ）は、ｙユニットを超状態
ｘに長くとどまらせるための継続時間ペナルティを示し
ている。このペナルティは、継続時間確率の対数の負数
である。図８に示すように、逆方向パスの伸びは、初期
ノードＩの方向を向いている終端ノードＴから順次逆方
向のアーク延長を行うことによって実現する。部分的パ
スを逆方向に１回アーク延長を行った場合、継続時間ペ
ナルティが評価し直されて、正確な継続時間に合った状
態が反映される。逆方向木構造探索における１回のアー
ク延長を対象とした基本的メカニズムは、次の通りであ
る。

【００３５】１アーク延長における逆方向部分パス点数
の更新ＰＰＳ（Ｅ）＝ＰＰＳ（Ｆ）−現行の継続時間ペナルテ
ィ＋修正済み継続時間ペナルティ＋ＦからＥまでの延長
を行うための他の更新完了パス点数の更新ＣＰＳ（Ｅ）＆＝＆ＰＰＳ（Ｅ）＋ＦＰＳ（Ｅ）ただし、ＰＰＳ（Ｅ）はフロントノードＥを伴う逆方向
部分パス尤度点数であり、ＣＰＳ（Ｅ）は、Ｅまで更新
された完了パス点数である。ＣＰＳ（Ｅ）の完了パス
は、逆方向部分パスの連結であり、終端ノードＴから
（点数ＰＰＳ（Ｅ）の）ノードＥまでの逆方向連結１ア
ーク延長線と初期ノードＩから（点数ＦＰＳ（Ｅ）の）
Ｅまでの順方向最適パスによって形成されている。順方
向最適パスは、順方向トレリス探索中に記録される。上
記の２本のパスは、ノードＥで結合されている。すなわ
ち、終端ノードから開始した場合、全ＣＰＳ点数は、順
方向ビタビ探索によって得られた最終尤度点数と同じで
ある。パスが逆方向に伸びていくことから、最終的に初
期ノードＩに達するまで、ＣＰＳは、ノードごとに更新
を続ける。ただし、ＣＰＳ（Ｉ）＝ＰＰＳ（Ｉ）であ
る。

【００３６】次に、上に挙げた式の各項について詳細に
説明する。１．現行継続時間ペナルティ（ＤＰ）パスは、現行状態に対して支払われているペナルティの
記録を保持する。ペナルティの計算は、パスがこの状態
にどのくらい長くとどまっていたか、さらに、別の状態
に変化する前にどのくらい長くとどまっているのかとい
う点に基づいて行われる。後者の情報は、順方向探索に
おける各ノードへの最良到来パスの一部として記録され
る。最良到来パスが各ノードごとに異なっていることか
ら、逆方向１アーク延長が行われる度に、このペナルテ
ィは、他のパス情報と共に更新される。図８のパスを、
その一例として考えるとよい。ここでは、順方向段階に
おいてはパスＡＤＥＦＧよりもパスＡＢＣＦＧが選択さ
れることが想定されている。逆方向パスがノードＦに達
したとき、「現行状態」は状態２であり、順方向パスマ
ップにしたがって、Ｆの後にこの状態からの状態遷移が
予想される。したがって、状態２でＧおよびＦ上にとど
まっているためには、ＤＰはｆ₂（２）でなければなら
ない。しかし、パスがノードＣに達したとき、「現行状
態」は状態１となり、今度はＤＰがｆ₁（３）として更
新されなければならない。これは、パスマップにより、
Ｃ、Ｂ、およびＡを通過する横の移動が予想されるため
である。

【００３７】２．修正継続時間ペナルティ（ＣＤＰ）この用語では、順方向の情報と逆方向の情報が組み合わ
されて、各延長線での正しい継続時間ペナルティが決定
させる。このプロセスは、次のように実行される。上記
の通り、順方向段階では、パスＡＤＥＦＧよりもパスＡ
ＢＣＦＧの方が好ましいとされている。このことは、順
方向段階の間、Ｃで累積された尤度点数の方がＥで累積
された点数よりも良い（小さい）（したがって、その時
点でＦがＣを選択）ことを意味している。さらに詳しく
見ていくと、選択時に、パスＡＢＣＦＧはパスＡＤＥＦ
Ｇと比較されないが、代わりに、ＡＢＣＦとＡＤＥＦと
の比較が行われたことが明らかである。元のビタビ構造
によれば、ＦからＧへの最良パスがＦへの最良パスの延
長線でなければならない。しかし、各状態の遷移が行わ
れた時点で継続時間ペナルティが加えられた場合、必ず
しもこの限りではない。順方向パスを行う場合、別の状
態への変化が起きるまで、現行の状態に対して継続時間
がどのくらい長く維持されるかはわからない。このた
め、状態変化の遷移が起きるまで、所定の状態に対する
ペナルティを課すことはない。しかし、順方向状態の遷
移が完了した後は、図８から明らかなように、ＡＢＣＦ
ＧとＡＤＥＦＧに対しては、Ｆ−Ｇを通過するコストが
異なる。このような理由から、ポイントＦへの選択され
た到来パスは、Ｆ−Ｇ後のウィナーを保証していない。
このような事態に対しては、文字認識の改善が全く行わ
れなかった場合、元のワンパスオンリー復号化構造とな
るが、逆方向探索を利用することによってこの事態は改
善される。

【００３８】例えば、逆方向パスがＧからＦに延長する
際に、完了パス点数に加えられる継続時間ペナルティ
は、最良順方向パス継続時間情報、すなわち、状態１の
Ａ−Ｂ−Ｃ（Ｆへの最適順方向パスの点数の一部として
黙示的に）と状態２のＦ−Ｇ（逆方向パスデータのＤＰ
として明示的に記録される）から一部取り入れている。
また、Ｆにおいて１アーク延長を逆方向に行おうとする
場合、Ｆ−Ｃ延長線（パス２）とＦ−Ｅ延長線（パス
１）との比較が必要である。

【００３９】図８を検討してみると、修正式を次のよう
に展開できることが明らかである。（ａ）Ｆ−Ｅ延長線の場合：状態遷移が一切発生しな
い。 ●状態２の予測継続時間 −本パスが状態２にどのくらい長くとどまっていたか：
２（Ｇ、Ｆ） −Ｅを通過する場合、状態２にさらにどのくらい長くと
どまるのか：順方向パスから最良パスＡＤＥＦによ
り、２（Ｅ、Ｄ） −状態２における逆方向予測継続時間の合計：２＋２
＝４ −ＣＤＰ（現行知識の最善のもの）：ｆ²（４） ●状態２に対してＦでパスがすでに支払いを行っている
ペナルティ−：初めに優先権を与えられているパス２
によれば、ｆ₂（２）（Ｆ、Ｇにとどまる場合） ●継続時間ペナルティの修正は、以下のように行われな
ければならない。［ＰＰＳ（Ｅ）＝ＰＰＳ（Ｆ）−ｆ₂（２）＋ｆ₂（４）
＋．．．；］ ●更新済ＤＰ：ｆ₂（４）（ｂ）Ｆ−Ｃ延長線の場合：状態遷移が発生。 ●終了したばかりの状態に対する修正。 −順方向パス情報により、パスにおいて現在支払われて
いるペナルティは上記のケース１と同じである（現在ま
でＦでわずか１本のパスしか考慮に入れていないことに
注意）：ｆ₂（２） −パス２が２単位分実際に状態２にとどまった場合のＣ
ＤＰ：ｆ₂（２） ●パスがＣに達した場合、Ｃにおける最良の到来パスに
より状態１に支払われるペナルティ：ｆ₁（３）
（Ｃ、Ｂ、Ａ） ●Ｃに入るための最終継続時間の修正は、以下の通りで
ある。［ＰＰＳ（Ｃ）＝ＰＰＳ（Ｆ）−ｆ₂（２）＋ｆ₂（２）
＋ｆ₁（３）．．．；］ ●更新済ＤＰ：ｆ₁（３）ＣＤＰ情報は、逆方向探索パスによって到着する度に計
算が行われ、ノード内に記憶される。ただし、異なる逆
方向探索パスによって到着した場合、同じノードのＣＤ
Ｐが異なる場合もあり得る。

【００４０】３．他の更新：全確率とも、マイナスの
対数法による。（ａ）Ｆ−Ｅ延長線の場合：［ＰＰＳ（Ｅ）＝ＰＰＳ（Ｆ）＋．．．＋ａ₂₂＋Ｏ
（Ｅ）］ただし、ａ２２＝状態２から状態２までの状態遷移確率Ｏ（Ｅ）＝観測尤度（ｂ）Ｆ−Ｃ延長線の場合：［ＰＰＳ（Ｃ）＝ＰＰＳ（Ｆ）＋．．．＋ａ₁₂＋Ｏ
（Ｃ）］ただし、ａ₁₂＝状態１から状態２までの状態遷移確率最終ＰＰＳ更新のための式は、以下の通りである。（ａ）Ｆ−Ｅ延長線の場合：［ＰＰＳ（Ｅ）＝ＰＰＳ（Ｆ）−ｆ₂（２）＋ｆ₂（４）
＋ａ₂₂＋Ｏ（Ｅ）］（ｂ）Ｆ−Ｃ延長線の場合：［ＰＰＳ（Ｃ）＝ＰＰＳ（Ｆ）−ｆ₂（２）＋ｆ₂（２）
＋ｆ₁（３）＋ａ ₁₂＋Ｏ（Ｃ）］上記の通り、完了パス点数ＣＰＳは、部分逆方向パス点
数（ＰＰＳ）と逆方向ビタビパスで記録された最良逆方
向部分パス点数であるフロントノードへの最良到来パス
の点数（ＦＰＳ）から構成されている。

【００４１】したがって、最終ＣＰＳの式は、以下の通
りである。（ａ）Ｆ−Ｅ延長線の場合：［ＣＰＳ（Ｅ）＝ＰＰＳ（Ｅ）＋ＦＰＳ（Ｅ）］（ｂ）Ｆ−Ｃ延長線の場合：［ＣＰＳ（Ｃ）＝ＰＰＳ（Ｃ）＋ＦＰＳ（Ｃ）］上記プロセスにより、予想可能なあらゆる延長線につい
ての予測ＣＰＳが判断されたことになる（Ｆでは、延長
線がＦ−ＥとＦ−Ｃになる）。さらに、実際の│ーク延
長を行うための最良延長線が選択された。ここでは、補
正後にＣＰＳ（│）＜ＣＰＳ（Ｃ）になると仮定し、延
長線Ｅを選択する。この「実際の」延長は、フロントノ
ードが１アーク逆方向に（この場合、ＦからＥへ）移動
し、予測通りにパス点数を変更した（ＣＰＳ（Ｅ））こ
とを意味している。残りの予想可能なあらゆる延長線
（ここではＦ−Ｃのみ）はそのまま元のパスと共に残さ
れ、したがってフロントノードはＦのままであり、新規
パス点数は残りのうち最良の点数である（この場合、Ｃ
ＰＳ（Ｃ））。図９から明らかなように、初めにフロン
トノードがＦの逆方向部分パスは、２本のパスに分割さ
れる。そのうちの一方は、フロントノードをＥに移動さ
せるための最良の１アーク延長線であり、他方は、同じ
元のフロントノードＦと残りの予想し得るかぎりの延長
線である（次に、両方のパスは、パススタックに挿入し
直される）。

【００４２】文字認識システムの目的のひとつは、高水
準文法または辞書チェックのための最上位Ｎ「ワード」
仮説の検出にあることから、スタック空間が限られてい
る場合は特に、スタック内の２本のパスが同じ「ワー
ド」仮説に至ることはない。ＣＰＳを計算する場合と同
様に、「ワード」仮説は、すでに創出された逆方向パス
をビタビ探索から取得した最適順方向到来パスと連結す
ることにより、追跡することも可能である。全体のスタ
ックは、パスの挿入が行われるときには必ず、重複がな
いかどうか審査される。重複「ワード」を有するすべて
のパスの中で、最良のパスだけが残り、他のすべてのパ
スが取り除かれる。スタックの初めから開始すると、大
抵は、ひとつだけ重複が存在し、比較された後、取り除
かれる。

【００４３】図９のフローチャートに関し、直前のパラ
グラフに述べた手順は、Ｍ＝Ｎ＋５をパススタックサイ
ズとした場合、次のように要約できる。ＩＮＩＴＩＡＬＩＺＥ（ブロック１１０１）；最高Ｍ点
数を有する終端ノードを用いて、パススタックを構成す
る（ブロック１１０３）。すべてのパスが今度はヌルパ
スとなり、１ノードのみが終端ノードとなる。ＬＯＯＰ
を入力し、最良の第１パスを創出する（１１０５）。パ
ススタックの最上部から開始して、第１非完了部分パス
を検出する（ブロック１１０７）。本パスに１を上回る
延長線が予想できる場合、部分パスを２本に分割する。
そのうちの第１パスは、最良の１アーク延長線を有して
おり、第２パスは、残りの１アーク延長線を有してい
る。それ以外の場合は、１アーク延長を行う（ブロック
１１０９）。パススタックが依然ランク順になるよう
に、完了パス点数にしたがってパススタックにパスを挿
入し直す（ブロック１１１１）。スタック内のワード重
複パスを一掃する（ブロック１１１３）。全Ｍパスが
「完了」するまでブロック１１０５にループバックする
（ブロック１１１５）。出力は、最上位のＮ完了パスで
ある（ブロック１１１７）。ブロック１１１９では、任
意の後処理が実行される。

【００４４】以上の技法は、実験的に立証された。実験
では、データベース内のすべての画像が、コンピュータ
によってシミュレートされたワード画像であった。この
ような画像は、パラメータとして標準偏差σｎを有する
ガウス雑音が加えられる鮮明なワード画像をベースとし
た。次に、標準偏差σｎによって指定された２次元ガウ
ス関数により画像の畳込みを行った箇所にボケ処理が行
われた。したがって、パラメータセット（σ_n，σ_n）
は、画像の質が悪化した度合いを指定する。背景および
前景の画素に対するグレイレベルの手段の浮標が制限で
きるように、画像データベースを作成する際にある程度
の正規化処理が行われる。にもかかわらず、グレイレベ
ルの分布には、上記の実験においてかなりの多様性がみ
とめられた。トレーニング処理の初期モデルは、それぞ
れ、パラメータ（５０，０．８）および（２０，０．
２）により、１文字につき２つの画像から構成された。
相関係数法では、前記の通り、一致の各々に対して初期
セグメンテーションを行う。このセグメンテーションに
より、トレーニングと似たような推定手順により各文字
に対する初期モデルが取得可能になる。ｋ平均トレーニ
ング法は、最終収束モデルを得るための大型トレーニン
グセットで動作可能である。

【００４５】トレーニングセットは、初期モデル用のト
レーニングセットと似た様な方法で作成される。ノイズ
およびボケ範囲は、（５０−５９，０．８−０．７）と
なり、１文字につき約１０サンプル用意される。これ
は、明らかに、ダイナミックレンジが非常に狭いトレー
ニングセットである。にもかかわらず、実験結果から明
らかになるように、非常にロバスト性に富んだモデルセ
ットが結果として得られる。本書に記載されている技法
の性能を評価するに当たり、３つのテストセットが使用
された。各セットのサイズは、約２００ワードであり、
１０００以上の文字を有し、長さは２〜１２文字と多様
である。第１セットは、トレーニングセットと同じパラ
メータ範囲で作成される。第２および第３セットは第１
セットと異なるが、それは、ボケやノイズの点および各
セットのワード修正だけでなく、１ワードにおける文字
間のギャップについても言えることであり、トレーニン
グセットやテストセット１では文字間のギャップが元の
１画素幅であるのに対し、０に設定される。その結果、
連結された隣接文字を含む画像が生成される。セット２
のパラメータ範囲は（７０−７９，０．９−１．０）で
あり、セット３は（８０−８９，１．０−１．１）であ
る。比較を行ったアルゴリズムは、バイナリ、グレイレ
ベル、Ｎ最良探索によるグレイレベルであり、いずれも
継続時間に制約がある。

【００４６】認識結果にアクセスするに当たり、あまり
重要でない相違がいくつかある。Ｎ＝１の場合、実験に
より、逆方向探索による継続時間補正の効果が明らかに
みとめられた。したがって、認識されたワードは、継続
時間の補正を伴う逆方向探索が完了した直後に、スタッ
クの最上位から直接出てきたワードである。後処理は一
切行っていない。Ｎ＝１０の場合、辞書チェックが実行
され、スタックの最上位から開始して、上から下の順に
１０候補すべての探索が行われる。ここでは、辞書内で
検出できたワードについての第１仮説が出力される。最
上位の１０候補のいずれも辞書で見つからない場合は、
最上位の１候補が出力として採用される。バイナリ技法
では、グレイレベル技法に代わり、第１コンポーネント
としてしきい値画素値（０または１）の特徴ベクトルを
用いる。採用されるしきい値アルゴリズムは、上記した
通り、特徴ベクトルの第３コンポーネントを抽出する際
に用いられるのと同じアルゴリズムである。残りのベク
トルコンポーネントは、グレイレベル技法と全く同じで
ある。このため、２つの技法は好対照となる。

【００４７】実験の結果は、図１０に示されている。図
１０を検討した結果、以下の点が明らかになった。 ●グレイレベル技法は、トレーニングセットとして同様
に劣化したデータセットに対し、ＯＣＲの性能を２％以
上向上させる働きをする。ワードにノイズが増え不明瞭
になるにつれて、グレイレベル技法がより優れた技法で
あることが明らかになる。 ●Ｎ最良仮説技法は、確度を大幅に改善するだけでな
く、システムのロバスト性も向上するという点で、グレ
イレベルシステムの性能を大幅に押し上げる。 ●Ｎ＝１は、Ｎ最良探索の特殊なケースである。Ｎ＝１
であることから、後処理のための任意仮説はなく、逆方
向探索後に最適出力が１度だけ行われる。この実験の値
から、後処理の要求を受けずに継続時間修正された最良
候補を取得すると、性能が大幅に向上することがわか
る。したがって、上記の強化による性能改善に、逆方向
継続時間修正が非常に重要な役割を果たすことが明らか
である。 ●Ｎ最良仮説技法は、認識の性能を改善させるうえで非
常に能率的であることが立証された。さらに、Ｎ＝１０
にするだけで、認識率とロバスト性に著しい向上がみと
められた。Ｎの値を大きくすれば、一層の改善が期待で
きる。注目したいのは、実験結果により、改善の半分近
くがＮ＝２または３でみとめられたことである。このた
め、能率的には一層の優越性が得られることが確実であ
る。 ●グレイレベル技法により、ほとんどコンピュータの計
算を増やさずに、また、メモリ空間をあまり増加させず
に、大幅な性能の改善が可能になる。メモリ空間は、観
測コンポーネントのひとつに対してのみ増加し、パス探
索に要するメモリ空間に比べ、非常に小さい部分を占め
るにすぎない。コンピュータ計算に関して、ここでは別
のケースを対象に、テーブルルッキング法により観測確
率を検出したところ、レベルが２でも２００でも、レベ
ル数は重大な影響を及ぼさないことが判明した。

【００４８】観測ベクトルでは、わずか１コンポーネン
トが実際にはグレイレベル固有のものである。他のすべ
てのコンポーネントは、バイナリシステムとグレイレベ
ルシステムの両方と同じである。このようなグレイレベ
ルの特徴をさらに加えれば、一層の改善が期待できる。
取得した画像に継続時間ペナルティを加える別の実施態
様は、順方向と逆方向のいずれの探索においても継続時
間を考慮せずに、元の広域Ｎ最良仮説探索を利用すると
いうものである。すべての仮説が検出された後、各仮説
に対する継続時間確率が後処理に組み込まれる。この技
法を用いて行われた実験では、従来のビタビ認識方式で
認識できなかったケースのほとんどは、Ｎが、例えば、
Ｎ＝５０などの非常に大きい値になるまで、大抵の場
合、正しい仮説によってＮ最良探索が行われることはな
い。したがって、仮説探索技法に対するコンピュータ計
算は大幅に増加し、能率も著しく悪化する。仮説探索技
法は、仮説に後処理を行って認識率を高め、かつ正しい
仮説を検出することを目的にしており、これが、前記技
法の利点である。しかし、継続時間ペナルティをまず初
めに順方向ビタビ探索に組み込んでから、次に、逆方向
探索に組み込むことにより、継続時間修正を行って、不
合理なマッチングを伴う仮説を削除することができた。
このようにして、より信憑性の高いワード、すなわち、
よく似た文字数および／またはよく似たトポロジを有す
るワードだけが検出される。このことは、印刷の質が悪
い文書画像を扱う場合は特に重要である。

【００４９】継続時間制約のある疑似２次元ＨＭＭ（１次元）ＨＭＭについての詳細は、参照［３］を参照
する。本書では、図１１のみを用いて、画素ストリング
のモデル作成に１次元ＨＭＭを使用した場合の対応を示
している。図１では、図１１の画素ストリングを２次元
画像に拡張している。その下の状態図は、１次元ＨＭＭ
を「疑似２次元」ＨＭＭに拡張した場合の対応を示して
いる。「疑似」は、完全に接続された２次元ネットワー
クではないという意味で疑似であるが、２次元ワード画
像を表す程度の融通性は有している。大きい楕円形を、
「超状態」と呼ぶ。各超状態は、１次元ＨＭＭである。
「超状態」という名称は、２次元モデルにおいて１次元
モデルの状態のように振る舞うが、１次元モデルの状態
よりもはるかに多くの情報を含んでいるという意味から
きている。文字画像の下の番号順は、観測値として対応
カラムを生成するための可能超状態遷移の順番を表して
いる。すなわち、超状態は、観測ユニットとしてカラム
を生成する。各超状態内では、図１１に示すように、１
次元ＨＭＭの状態が各カラム内の画素に対応している。
すなわち、これらの画素は、状態の観測ユニットであ
る。

【００５０】ＰＨＭＭは、次に説明するパラメータセッ
トにより完全に指定できる。式を明確にするために、こ
こでは、異なるＰＨＭＭが異なる値を有する同一のパラ
メータセットを持つことを条件に、モデル指標を省略す
る。

【００５１】１．Ｎは、モデルの超状態数である。本ア
プリケーションでは、Ｎは、画像のトポロジによって決
まる。例えば、図１では、似たようなカラムをグループ
にまとめることによって、３つの超状態を有するＰＨＭ
Ｍは、文字の特性を充分に示している。

【００５２】２．Ｄは、文字に対する継続時間確率であ
る。ｍが文字の継続時間であるとした場合、以下の式が
成り立つ。Ｄ（ｘ）＝Ｐ（ｍ＝ｘ）ただし、ｍは、カラム単位である。

【００５３】３．Ｄ_s：Ｄ_i０≦ｉ≦Ｎ−１は、超状態の
継続時間確率である。ｍが超状態ｉの継続時間であれ
ば、Ｄ_i（ｘ）＝Ｐ（ｍ＝ｘ）ただし、ｍは、カラム単位である。

【００５４】４．Ａ＝ａ_ij：０≦ｉ≦Ｎ−１；ｉ≦ｊ≦
ｉ＋１は、超状態遷移確率分布である。図１に示すよう
に、超状態遷移は、カラムからカラムへ（この場合、左
から右へ）移動するときに発生する。Ｓ_kがカラムｋの
超状態であるとした場合、ａ_ijは、以下のように定義で
きる。

【数１０】本アプリケーションでは、超状態のスキップは、１つで
も認められていない。すなわち、次の超状態または同じ
超状態への遷移だけが可能である。

【００５５】５．Λ＝｛λ^j：０≦ｉ≦Ｎ−１｝は、各
超状態（楕円形）内の垂直１次元モデルを指定するパラ
メータセットである。ｊ番目の超状態では、λ^jが以下
の要素から成り立っている。 ●Ｎ^jは、超状態ｊ内の１次元ＨＭＭの状態数である。
Ｎと同様に、Ｎ^jは、文字のトポロジによっても決定さ
れる。 ●Ｄｊ／ｉ＝｛Ｄｊ／ｉ０≦ｉ≦Ｎ^j−１｝は、各状態
に対する継続時間確率である。ｍが超状態ｊの状態ｉに
対する継続時間であれば、Ｄｊ／ｉ＝Ｐ（ｍ＝ｘ）であ
る。ただし、ｍは、画素単位である。 ●Ａ^j＝｛ａｊ／ｋｉ：０＜＝ｋ＜＝Ｎｊ−１；ｋ＜＝
ｉ＜＝ｋ＋１”｝超状態ｊの状態ｋがｓｊ／ｋであり、かつ座標（ｘ，
ｙ）の画素の状態がｑ_xyであると定義した場合、以下の
式が成り立つ。

【数１１】 ●Ｂ^j＝｛ｂｊ／１（Ｏ_xy）：０＜＝ｉ＜＋Ｎ^j−１｝
は、超状態ｊの状態ｉにおいて、観測ベクトルとしてＯ
ｘｙを有している観測確率である。すなわち、ｂｊ／１
（Ｏ_xy）＝Ｐ（Ｏ_xy ｑ_xy＝ｓｊ／１）である。ただ
し、Ｏ_xyは、位置（ｘ，ｙ）の画素に対する観測ベクト
ルである。超状態レベルの各モデルにはＢパラメータが
全くないことに注意されたい。その理由は、次の説明に
より明らかになるであろう。

【００５６】特徴の抽出（ｘ，ｙ）に配置された各画素の観測ベクトルＯ_xyには
３つのコンポーネントがある。観測ベクトルの第１コン
ポーネントＯ１／ｘｙは、次のように計算される。

【数１２】ただし、ｍ_i,jは、（ｉ，ｊ）に配置された画素のグレ
イレベルであり、ｃ_xyは、３画素ｘ３画素の核から成
る。この核の重み付けが、図４に示されている。すなわ
ち、この核は、全体画像の畳込みに用いられる。その目
的は、ノイズにより生じたグレイレベル値の不揃いの影
響を減らすことである。つまり、周囲の画素も、中心画
素に対する特徴評価の一助となっている。また、結果と
して得られる（０から２５５までの）画素のグレイレベ
ル値は、１００レベルに量子化される。

【００５７】第２コンポーネントは、カラム内の各画素
の相対位置である。文書のレイアウト分析の後、ベース
ラインの位置とトップラインおよびベースライン間の差
が明らかになるものと想定している（トップラインとベ
ースラインの定義については、図３を参照）。第２コン
ポーネントの実際の値は、次式により求められる。第２コンポーネント＝特徴画素からベースラインまでの
距離（画素単位）／／トップラインからベースラインま
での距離この式により、５０レベルに量子化される。明らかに、
この値は、印字文字のポイントサイズにかかわらず、
ｇ、ｐ、ｑの一部であるカラム内の各画素の位置に対し
て、マイナスになるはずである。このように、前記特徴
は、異なるアプリケーションにおいて、一層ロバスト性
が強化される。

【００５８】第３コンポーネントの値は、画素が存在す
る主ストロークの方向である。本発明では、全体画像に
しきい値を採用している（しきい値アルゴリズムについ
ては、実験条件の箇所で説明している）。各画素ごと
に、０度、４５度、９０度、１３５度の４方向に伸びる
（連続した黒い画素による）ストロークの長さを計算
し、さらに、主ストローク方向としてその画素を通る最
長のストロークを選択する。第５番目の「方向」は、背
景の画素に対するものであり、方向やストロークについ
ては一切の定義がされていない。したがって、このコン
ポーネントは、５つのそれぞれ異なる値を有している。

【００５９】ＰＨＭＭ用入れ子型ビタビアルゴリズムビタビ復号法アルゴリズムの基本構造は、参照［３］お
よび参照［４］などの多くの文献に見ることができる。
図１２は、ＰＨＭＭによるビタビ探索完了後に得られた
他のパスの中の３つのパスを示している。このビタビ探
索は、（Ｎフレーム／カラムを有する）完全ワード画像
と４つの超状態を有するＰＨＭＭの間で実行される。各
パスは、モデルと画像の間の可能性としてあり得る一致
を表している。ｂ_j（Ｏ_i）が、超状態ｊによってカラム
ｉの観測が行われる尤度であり、ａｋｌが、超状態ｋか
ら超状態ｌまでの超状態遷移確率であれば、パスＡの尤
度は、−ｌｏｇ（）法により、以下の式で表される。ｂ₀（Ｏ₀）＋ａ₀₂＋ｂ₂（Ｏ₁）＋ａ₂₂＋ｂ₂（Ｏ₂）＋ａ
₂₃＋ｂ₃（Ｏ₃）＋ａ₃₃＋ｂ₃（Ｏ₄）＋ａ₃₃＋ｂ₃（Ｏ₅）
＋・・・＋ａ₃₃＋ｂ₃（Ｏ_N−１）

【００６０】超状態ｊによりカラムｉを生成する尤度で
あるｂ_j（Ｏ_i）を検出するには、まず初めに、超状態ｊ
内の１次元ＨＭＭとカラムｉの画素との最良の一致を検
出しなければならない。その箇所は、図５の下方部分に
見られるように、状態レベルのビタビ探索が適合する位
置である。このビタビ探索は、第２超状態の１次元ＨＭ
Ｍと第１カラム内の画素との間の別のビタビ探索であ
る。これにより、前記超状態によって（または、前記１
次元ＨＭＭによって）作成された上記カラムの尤度が得
られる。状態レベルビタビ探索の最適パス尤度点数は、
上の式に必要な尤度点数ｂ₂（Ｏ₁）と全く同じである。
したがって、次の式が成り立つ。

【数１３】ただし、Ｍは、１カラム内の画素の総数である。すなわ
ち、超状態レベルのビタビ探索では、ｂ_i（Ｏ_j）を必要
とする度に、入れ子型状態レベルビタビ探索を開始し
て、前記尤度点数を検出する。この理由により、前記技
法を入れ子型ビタビ探索と呼んでいる。

【００６１】注意しなければならないのは、上の式の左
辺のｂ_i（Ｏ^j）と右辺のＢ^j＝｛ｂ^j ⁱ（Ｏ_xy）｝との差
である。前者は、超状態の１次元ＨＭＭによって作成さ
れたカラムの尤度である。前記尤度は、カラムごとに異
なっており、可能な値の数については無限である。後者
は、１状態によって作成された画素の尤度であり、非連
続的観測を行った場合に有限となり、トレーニングによ
り連続的な観測を行えばパラメータ形式になる。このた
め、後者は、モデルパラメータの一部であり、前者は
（少なくとも実際的な意味では）その限りではない。こ
の入れ子型ビタビアルゴリズムは、トレーニングおよび
認識プロセスの極めて重大な部分である。簡潔に言え
ば、ＰＨＭＭ用入れ子型ビタビアルゴリズムは、主要な
１次元ビタビ探索であり、左から右へカラムごとに、ワ
ード画像と複数のモデルの間に見られる最良の一致を検
出する。また、画像の各カラムと各モデルの各超状態と
の間には、別の１次元ビタビ探索が用いられ、上から下
へ画素ごとに、各カラム内の画素と状態との最良の一致
を検出する。この入れ子型構造は、図１２に明確に示さ
れており、図の上部に画像とＰＨＭＭの間の主要ビタビ
探索が示されており、図の下部に１次元探索が適合する
箇所が示されている。ビタビ探索は、最後のフレームが
終わるまで、左から右へ行われる。これにより、ＰＨＭ
Ｍによって生成されている画像の全体的な尤度が得られ
る。

【００６２】ＰＨＭＭ用レベル構築アルゴリズム連結文字認識の場合、ワード画像は、すべての文字から
予想可能なＰＨＭＭのあらゆる組み合わせとマッチング
しなければならない。図１３に示すように、ビタビ探索
パスが１レベルを通過した場合、フレームの１セクショ
ンとＨＭＭの間に一致が検出されたことを意味してい
る。図１２に示すように、出口点は、１レベル内のこの
ような一致の可能終了点である。図１３は、図１２を拡
張した図であり、すべての可能文字モデルに対応するた
めさらに１次元加え、最適なモデルの組み合わせを探索
するレベルを構成している。フレーム４におけるモデル
「ａ」の出口点は、フレーム５から上に向かって、レベ
ル２のモデル「ａ」の別の一致に連結されている。この
パスは、フレーム０からフレーム４までの文字「ａ」、
さらに、フレーム５から上の別の「ａ」についての可能
な認識を表している。この間ほとんど常に、各開始点
（例えば、図１３のＳのような、各レベルで見込まれて
いる新規パスの第１ノード）に対し、選択を行う開始点
の直前のフレームおよび直前のレベルで利用可能な出口
点を有するモデルが１以上（１を含まず）存在する。ビ
タビアルゴリズムにより各ノードの到来パスを選択する
規則と同様に、パスを継続する出口を選択する規則につ
いては、以下に述べる通りである。

【００６３】レベルｊ＋１およびフレームｋ＋１のモデ
ルｉの超状態０から開始するパスの場合、最良の出口点
は、レベルｊおよびフレームｋの全モデルの最終超状態
の中で最小累積尤度点数を有していなければならない。
すなわち、まず初めに、どの文字モデルから最適パスが
入ってきたのか検出できる。これが文字モデルｍとすれ
ば、ｍは、次の条件を満たさなければならない。

【数１４】ただし、ｌｉｋｅ（ｓ，ｉ，ｊ，ｋ）は、モデルｉおよ
びレベルｊの超状態におけるフレーム０からフレームｋ
までの累積パス尤度である。この場合、ｓ_mはモデルｍ
の最終超状態であり、Ｍはモデル総数である。また、ｖ
ｉｓｉｔ＝＝１は、このノードに少なくとも１以上のパ
スが到達し、出口ノードとして認められている。新たな
レベルへの拡張を開始するパスは、直前のフレームおよ
び直前のレベルにおいて利用可能なすべての出口を全モ
デルにわたって探している。また、前記パスは、上記出
口を、同じモデルと同じレベルから入ってきたパス、す
なわち、直前のフレームから開始した上記レベルに存在
していたパスと比較しなければならない。そのうちの最
良到来パスは、新規パスの起点として選択される。図１
３を例にとると、レベル１で利用可能な出口が２つあ
る。ひとつはモデル「ａ」にあり、もうひとつはモデル
「ｃ」にあり、いずれもフレーム４にある。前記出口と
レベル２（パスが存在する場合）のモデル「ａ」のフレ
ーム４から入ってきたパスを比較した後、レベル１のモ
デル「ａ」の超状態３の出口が選択されたものとみな
し、レベル２において拡張を開始する。このパスは、フ
レーム０からフレーム４までの「ａ」と、さらに、フレ
ーム５以上の別の「ａ」の認識を可能にする。「ｃ」の
出口が選択された場合、結果は、フレーム０からフレー
ム４までの「ｃ」とフレーム５以上の「ａ」となる。

【００６４】ＰＨＭＭを用いた入れ子型ビタビ探索によ
るアルゴリズムを構成する上記レベルについて要約する
と、以下のようになる。／＊超状態レベルのビタビ探索を開始＊／（ブロック１
４０１）左から右への全カラムにわたるループ（ブロック１４０
３）０から最大レベルへの全レベルにわたるループ（ブロッ
ク１４０５）０から最大モデルへの全モデルにわたるループ（ブロッ
ク１４０７）０からＮまでの全超状態にわたるループ（ブロック１４
０９）現超状態に向かう最良到来パスを検出（ブロック１４１
１）現超状態（１次元モデル）およびカラム間の尤度点数を
検出（ブロック１４１３）／＊状態レベルのビタビ探索を開始＊／（ブロック１４
１５）トップからボトムまでのカラムの全画素にわたるループ
（ブロック１４１７）１次元モデルの全状態にわたるループ（ブロック１４１
９）現超状態に向かう最良到来パスを検出（ブロック１４２
１）現超状態および画素観測間の尤度点数を検出（ブロック
１４２３）適用可能であれば、状態レベルのパス延長線を作成（ブ
ロック１４２５）ループ制御（ブロック１４２７）ループ制御（ブロック１４２９）適用可能であれば、超状態レベルのパス延長線を作成
（ブロック１４３１）ループ制御（ブロック１４３３）ループ制御（ブロック１４３５）ループ制御（ブロック１４３７）ループ制御（ブロック１４３９）

【００６５】ＰＨＭＭへの継続時間ペナルティの組み込
み入れ子型ビタビ探索構造において、パス探索プロセスの
一部として継続時間ペナルティの組み込みを行いたい場
合、次のように、尤度は、各ノードにおいてパスに沿っ
て更新されなければならない。ｌｉｋｅ（ｉ，ｋ）＝最大［ｌｉｋｅ（ｉ，ｔ−１）＋
ａ（ｉ，ｉ），ｌｉｋｅ（ｉ−１，ｔ−１）＋ａ（ｉ−
１，ｉ）＋状態（または超状態，文字）継続時間ペナル
ティ］＋ｂ_i（Ｏ_k）；ただし、ｂ_i（ｂ_Ok）は、ノードｉ（前記の通り、超状
態でも状態でもよい）の尤度であり、ｌｉｋｅ（ｉ，
ｋ）は、ノードｉおよびフレーム（または画素）ｋまで
累積されたパス尤度点数であり、また、継続時間ペナル
ティは、継続時間確率のマイナスの対数尺度である。本
発明のアプリケーションでは、状態、超状態、および文
字の継続時間の長さのヒストグラムを計算することによ
り、トレーニングを通じて継続時間確率を検出する。状
態のヒストグラムは画素単位で、超状態および文字のヒ
ストグラムはカラム単位で計算される。この式からわか
るように、異なる状態、超状態、または文字の間で遷移
が起きる場合に限り、継続時間ペナルティが加えられ
る。文字継続時間ペナルティは、文字モデルの最終超状
態からの遷移が発生するときに、超状態継続時間ペナル
ティの上に加えられる。このようにして、継続時間ペナ
ルティは、後処理としてではなく、順方向探索に組み込
むことができる。実験から、上記の組み込みによって、
認識の性能が大幅に改善されることが明らかである。Ｎ
最良技法では、組み込みによってより最適なワード候補
を提供することもでき、最良候補が正しくない場合は、
特に有効である。さらに、適正な高水準後処理の探索サ
イズを大幅に減少させることも可能である（例えば、辞
書チェック）。

【００６６】バックトレーシング本発明による順方向（左から右へ）ビタビ探索プロセス
では、超状態レベルのいずれのノードにおいても、将来
使用するうえで必要になるすべての情報を記録する。必
要な情報は、トレーニングおよび認識の目的により異な
る場合がある。認識（Ｎ最良探索を伴わない）を目的と
する場合、終端ノードから開始ノードまで逆方向にどの
ように最適パスを追跡するか知っていればよい。パスの
終端ノードは、モデルの最終超状態、すなわち、観測の
最終フレームに位置する。この定義によれば、終端ノー
ドに複数のパスが到来していれば、本構造の全レベルの
全モデルに対して終端ノードは１つである。さらに、全
ノードの累積パス点数を比較し、そのうちの最良のもの
が最適パスの終端ノードになる。開始ノードは、ちょう
どこれと反対側にある。つまり、パスの観測の最初のフ
レームの最初のノード（超状態）である。当然、終端ノ
ードからパスを逆方向に追跡すれば、開始ノードで終了
する。最適パスの終端ノードを検出したと仮定して、こ
の最適パスに沿って逆方向に追跡する場合、現行ノード
の直前のノードがどのようなノードか知っている必要が
ある。つまり、この直前のノードが、どのようなレベル
やモデル、あるいは、超状態に属しているかである。バ
ックトレーシングがトレーニングを目的としている場
合、各モデル、超状態、および状態がどこで開始して終
了するかという点について、正確な画素およびカラム指
標に加え、各状態によって作成される全観測ベクトルに
よって正確に知っていなければならない。これだけで、
本発明によるモデルを更新する際に必要な情報はすべて
得られる。バックトレーシングの主な目的は、超状態レ
ベルにおける最適パスのフレーム単位の回復に加え、超
状態レベルにおける最適パスの各ノード内の状態レベル
における最適パスの画素単位の回復を行うことである。
簡単に言えば、超状態および状態レベルの両方で開始さ
れたビタビ探索の場合、必要な情報を得るために最適パ
スを逆方向に追跡しなければならない。このプロセスに
より必要となる基本的な情報は、現行ノード（超状態ま
たは状態）から最適パスに沿ってひとつ手前のノードま
でのリンク情報である。トレーニングおよび認識を目的
とした上記プロセスで得られた情報の正確な利用法につ
いて、以下に詳しく説明する。レベル構築構造における
前記バックトレーシングをまとめると、次のようになる
（図１５）。／＊最終フレームから、検出された最適パスのバックト
レーシングを開始＊／（ブロック１５０１）ループにより、最良パスから直前カラムのレベル、モデ
ル、超状態を検出（ブロック１５０３）直前カラム内の最適パスのバックトレーシングを開始
（ブロック１５０５）ボトムからトップへの全画素にわたるループ（ブロック
１５０７）最良パスによる直前画素の状態を検出（ブロック１５０
９）ループ制御（ブロック１５１１）ループ制御（ブロック１５１３）

【００６７】トレーニングモデルのトレーニングを行うために、参照［１０］に述
べるようなセグメント型ｋ平均トレーニング法を採用す
る。ブロック図は、図１６に示す通りである。このトレ
ーニング法の長所は、教師なしの手法である点にある。
全体のプロセスを通じて、その目的は、現行モデルを使
用してパスの検出や（超）状態シーケンスセグメンテー
ションを実行し、さらに、セグメンテーション情報を使
用して、モデルのパラメータ推定を行うことである。し
たがって、新たに取得したモデルを用いて、これから再
度セグメンテーションを行う。最終的に一定の基準内に
パラメータセットが収束するまで全体のプロセスが繰り
返され、各文字ごとにＨＭＭが構築される。

【００６８】トレーニングプロセスが開始する前に、初
期ＰＨＭＭを設定させて繰り返しを開始しなければなら
ない。初期ＰＨＭＭは、既存モデルから取得するか、あ
るいは、セグメンテーション方法によって取得する。こ
の概念について、以下に説明する。初期モデルまたは上
記繰り返しが行われているｋ平均プロセス中に更新され
たモデルを取得すると、モデルは、最適パスのバックト
レーシングによる（超）状態シーケンスセグメンテーシ
ョンに使用される。なお入れ子型ビタビ探索により最適
パスの検出を行うが、レベル構築は、この場合、必要で
はない。その理由は、各トレーニング画像に対する「ワ
ード」はどのようなものか正確にわかっているからであ
り、このことは、各レベルの開始時点で出口点の中から
選択を行う必要がないことを意味している。ここでしな
ければならないのは、ワードモデルを形成するために、
ワード内の順序にしたがって、文字モデルを段階的に処
理することだけである。次に、入れ子型ビタビ探索によ
り、このワードモデルとワード画像との間の最良の一致
を検出する。アルゴリズム構造により、入れ子型ビタビ
探索後には、最適パスから、ａ）超状態レベルにおい
て、どこに各超状態および文字の境界（カラム指標によ
る）があるのか、ｂ）状態レベルにおいて、どこに各状
態の境界（画素指標による）があるのか、明らかになる
であろう。この情報は、超状態と状態レベルの両方にお
いて最適パスをバックトレーシングすることによって検
索される。このセグメンテーション情報が取得されれ
ば、各画素が、どのモデルや超状態、あるいは状態に属
しているかを正確に知ることができる。

【００６９】次に、この情報により、画素観測ベクトル
をグループ化する。例えば、各文字ＰＨＭＭに超状態が
５つあり、各超状態に状態が５つある３文字のワードの
場合、このワード画像の全画素観測ベクトルを３ｘ５ｘ
５＝７５のそれぞれ異なるグループに分け、１グループ
には、各文字モデルの各超状態における各状態を割り当
てるようにする。この観測ベクトルは、図１６に示すよ
うに、「ＰＨＭＭＫの情報」データベースにすべて含
まれている。この中に含まれている他の情報は、（超）
状態遷移カウント、文字および（超）状態継続時間レコ
ードである。この手順は、すべてのトレーニング画像
（トークン）がセグメント化されるまで繰り返される。
次に、モデルの新たな集合を得るために、再推定プロセ
スが開始される。パラメータセット（Ｎ、Ａ、Ｂ、Ｄ、
ラムダ）を有するモデルの場合、次のような再推定が可
能である。文字継続時間確率については、以下の通りで
ある。Ｄ（ｎ）＝ｎカラムの継続時間を有する文字のトレーニ
ングトークン数／／文字のトレーニングトークン数超状態レベルパラメータについては、以下の通りであ
る。ａ_kj＝超状態ｋから超状態ｊまでの遷移数／／超状態ｋ
からの全遷移数Ｄ_j（ｎ）＝ｎカラムの継続時間を有する超状態ｊのト
ークン数／／超状態ｊのトークン数超状態ｊにおける１次元ＨＭＭの状態レベルパラメータ
については、以下の通りである。ａｊ／ｋｉ＝状態ｓｊ／ｋからｓｊ／ｌまでの遷移数／
／状態ｓｊ／ｋからの遷移数ｂｊ／ｉｍ（ｐ）＝ｍ番目のベクトルコンポーネントに
観測ｐを有する状態ｓｊ／ｌのベクトル数／／状態ｓｊ
／ｌのベクトル数Ｄｊ／ｌ（ｎ）＝ｎ画素の継続時間を有する状態ｓｊ／
ｌのトークン数／／状態ｓｊ／ｌのトークン数トレーニングループの最終ステップは、繰り返しを止め
るための基準として行われる収束検査である。新規モデ
ルと直前モデルとの間の位置合わせに関する適合性の比
較は、最適パスの尤度を比較して行う。尤度点数の変動
が一定のしきい値を下回れば、最終的な収束が起きたこ
とになる。そうでない場合は、セグメンテーション−推
定ループ全体が繰り返される。この後に続くループのと
きに限り、新規作成されたモデルがセグメンテーション
手順に使用される。

【００７０】ＰＨＭＭの初期推定すでに述べたように、各文字モデルの超状態数および状
態数は、トポロジによって決まる。ここで、図６を例に
とって説明する。実験では、文字のトポロジを検査によ
って決められグループ化プロセスが開始する前に与えら
れた最終ブロック数により、最初の戦略を用いている。
カラムから成るこの垂直ブロックが形成された後、次
に、各垂直ブロックに進み、カラムの場合と同様のプロ
セスによってブロック内のローをグループ化する。図６
は、画像「ｂ」の最終的なグループ化（切断）を示した
ものである。この図から明らかなように、文字「ｂ」
は、各超状態内にそれぞれ３、３、５、３の状態を持つ
４つの超状態を有するＰＨＭＭによって表すことができ
る。切断が行われる正確な位置については、このような
反復した相関関係の比較によって自動的に決められる。
これは、ノイズやボケを伴ったグレイレベル画像に対し
て特に重要である。というのは、異なる文字や標本に対
して意味のある効率的で一貫したセグメンテーション
（グループ化）を手動操作で行うのは難しいからであ
る。各文字ごとに、いくつかの標本画像に対して前記手
順が繰り返される。次に、セグメンテーションに基づ
き、対象となる文字に対してＰＨＭＭの初期推定が行え
る。ただし、この手順が必要とされるのは、トレーニン
グプロセスの開始に利用可能なＰＨＭＭの初期推定値が
全くない場合に限られる。

【００７１】また、識別的なトレーニングを組み込むこ
とにより、性能がさらに向上する。実験で間違って識別
されたワードをチェックしているときに、そのワードの
ほとんどが、いわゆる「コンフュージョンセット」にク
ラスタ化される。

【００７２】すなわち、文字は、似たようなトポロジに
よって他の文字と間違えられ、画像がノイズが多く不鮮
明であった場合には、一層紛らわしいものとなる。例え
ば、セット｛ｅ，ｃ，ｏ｝、セット｛ｌ，ｉ，ｔ｝、ま
たは、「ｃｌ」と間違えられた「ｄ」などがあり、この
ため、Ｎ最良探索を利用して、正しいワードに非常によ
く似たワードを検出する。識別的トレーニングによって
このような競合的文字セットを有するモデルを訓練する
場合、Ｎ最良探索は、認識についての誤り率を大幅に減
少させる。このことは、Ｎ最良仮説技法の結果によって
確認できる。仮説リストで検出されたワードのほとん
ど、すなわち、正しいものと競合する最上位と認められ
たワードは、大抵、コンフュージョンセットからの文字
の組み合わせである。以上をまとめると、疑似２次元マ
ルコフモデルリングと組み合わせたグレイスケールイメ
ージングの利用により、バイナリシステムにおいて、特
に、劣化した連結ワード画像の場合に、大幅な改善がみ
られる。また、システムの一層の改善を図るため、継続
時間制約のあるＮ最良仮説探索が導入されている。この
継続時間制約は、まず初めに、加えられたペナルティと
して順方向ビタビ探索に課された後、次に、順方向パス
で得られたパスマップと組み合わされて、逆方向探索に
より継続時間ペナルティの補正が行われる。実験結果に
より、認識率が大幅に向上し、かつアプリケーションの
変化が著しい場合でもロバスト性に富むというシステム
の優越性が立証された。

【００７３】本発明は、詳細な実施例により、例示およ
び説明がなされた。しかし、本発明の精神に反せず、ま
た本発明の範囲を逸脱しない限り、様々な変更が行える
ことは、当業者にとって明らかであろう。

【発明の効果】【図面の簡単な説明】

【図１】文字の画素マップと疑似２次元ＨＭＭの対応す
る超状態および状態図である。

【図２】ワード画像の画素マップを本発明による疑似２
次元ＨＭＭと比較するためにプログラムされたコンピュ
ータの動作を示すフローチャートである。

【図３】疑似２次元ＨＭＭの生成手順を示すフローチャ
ートである。

【図４】観測ベクトルの作成に用いられる畳込み用の核
の図である。

【図５】説明を行うためのテキスト画像のトップライン
とベースラインを示す図である。

【図６】グレイレベルのテキスト画像に関する状態およ
び超状態の分割を例示した図である。

【図７】３つの異なるテスト用文字セットを対象にここ
で開示されている各種好適な具体例の文字認識率を示す
図である。

【図８】パススタックのデータ構造の流れを示す図であ
る。

【図９】逆方向の木構造探索に関するトポロジを示す図
である。

【図１０】図８のパススタックを処理するための好まし
い方法を示すフローチャートである。

【図１１】１次元ＨＭＭと一連の画素との対応関係を示
す状態シーケンス図である。

【図１２】入れ子型ビタビ探索のパスマップである。

【図１３】入れ子型ビタビ探索を用いるレベル構築アル
ゴリズムによって作成されたデータ構造である。

【図１４】超状態レベルのビタビ探索の手順を示すフロ
ーチャートである。

【図１５】パスをバックトラッキングする手順を示すフ
ローチャートである。

【図１６】各種トレーニング手順を示すフローチャート
である。

【図１７】各種トレーニング手順を示すフローチャート
である。

【図１８】初期モデルの推定に用いられる手順を示すフ
ローチャートである。

【図１９】初期モデルの推定に用いられる手順を示すフ
ローチャートである。

【図２０】初期モデルの推定に用いられる手順を示すフ
ローチャートである。

【図２１】初期モデルの推定に用いられる手順を示すフ
ローチャートである。

【図２２】初期モデルの推定に用いられる手順を示すフ
ローチャートである。

【図２３】初期モデルの推定に用いられる手順を示すフ
ローチャートである。

【図２４】文字認識に用いられる手順を示すフローチャ
ートである。

【図２５】文字認識に用いられる手順を示すフローチャ
ートである。

【図２６】文字認識に用いられる手順を示すフローチャ
ートである。

【図２７】パススタック初期化手順を示すフローチャー
トである。

【図２８】パススタックから第１の非完了パスを取得す
る手順を示すフローチャートである。

【図２９】パス分割手順を示すフローチャートである。

【図３０】可能な逆方向１アーク延長の推定手順を示す
フローチャートである。

【符号の説明】

１００画素マップ１１０〜１１４垂直領域２１０〜２１４超状態

───────────────────────────────────────────────────── フロントページの続き (72)発明者チンチンイエンアメリカ合衆国 07701 ニュージャーシィ，レッドバンク，ヴァージニアテラス 40

Claims

【特許請求の範囲】

【請求項１】各モデルが既知の文字を表している複数
の疑似２次元隠れマルコフモデル（ＰＨＭＭ）を生成す
る段階と、前記文書を走査して、各未知のワード画像ごとにグレイ
レベル画素マップを生成する段階と、各未知のワード画像ごとに、前記未知のワード画像に対する画素マップを既知の文字
のＰＨＭＭと比較して、Ｎ最良仮説探索により、既知の
文字の最適なシーケンスを判断する段階とから成ること
を特徴とするグレイスケール文書に含まれる未知のワー
ド画像を識別する機械的方法。
【請求項２】各前記隠れマルコフモデルが少なくとも
１以上の超状態を有し、各前記超状態が少なくとも１以
上の状態を有していることを特徴とする請求項１に記載
の方法。
【請求項３】隠れマルコフモデルを生成する段階が、
セグメント型ｋ平均トレーニング法を適用し、各既知の
文字を表す複数のトレーニングトークンから前記既知の
文字に対する隠れマルコフモデルのパラメータを推定す
る段階から成ることを特徴とする請求項２に記載の方
法。
【請求項４】前記超状態が、前記隠れマルコフモデル
によって表されたテキスト要素によりほぼ垂直なスライ
スを表しており、かつ、各比較段階が、第１のルーチンにおいて、前記画素マップ内の１カラム
と超状態の各組み合わせに対し、ビタビアルゴリズムを
適用し、前記超状態内の状態により前記カラムに対する
最良パスと前記超状態内の最終状態に対する確率を判断
する段階と、第２のルーチンにおいて、ビタビアルゴリ
ズムと前記第１ルーチンで判断された確率を適用し、前
記超状態による最良パスと最終超状態に対する確率を判
断する段階とから成ることを特徴とする請求項２に記載
の方法。
【請求項５】（ａ）まず初めに、隣接カラムの複数の
対の各々内で相互相関係数を比較して複数のカラムブロ
ックを生成し、（ｂ）次に、複数の隣接カラムブロック
の複数の対の各々内で相互相関係数を比較してさらに大
きいブロックを生成し、かつＮブロック（Ｎは正の非ゼ
ロの整数）が残るまでステップ（ｂ）を循環的に繰り返
すことによって、初期セグメンテーションが行われるこ
とを特徴とするＰＨＭＭの初期推定を実行する方法。
【請求項６】各ブロック内の隣接ローを比較してサブ
ブロックを生成し、超状態の割当てによってブロックの
各々を表し、状態の割当てによってサブブロックの各々
を表し、かつ画素ベクトルに基づくステップを割り当て
る段階を具備する請求項５に記載のＰＨＭＭの初期推定
を実行する方法。