(57)【特許請求の範囲】
【請求項１】
文字ストリング画像の中の文字をセグメント化するための方法であって、
ａ）出発ポイント座標の空のリストを生成するステップと、
ｂ）背景と対照を成すピクセルの第１の出発ポイント座標を決定し、出発ポイント座標の前記リストにこの出発ポイント座標を追加するステップと、
ｃ）最大文字幅と、前記最大文字幅に対応する前記文字ストリング画像の部分の特性とに応じた、可能性のある文字幅のリストを生成するステップと、
ｄ）前記第１の出発ポイント座標と、可能性のある文字幅の前記リストの第１の幅とに対応する前記文字ストリング画像の第２の部分を決定するステップと、
ｅ）前記文字ストリング画像の前記第２の部分に対して分類方法を適用して、前記第１の幅についてのエラーの可能性と、候補文字とを提供するステップと、
ｆ）速度と正確さとの間のトレードオフによって決定される第１のしきい値と、エラーの前記可能性を比較するステップと、
ｇ）前記第１の幅に対応するエラーの前記可能性が、前記第１のしきい値の値よりも低い場合に、前記第１の幅に対応する前記文字として前記候補文字を選択するステップと、
ｈ）前記第１の幅に対応するエラーの前記可能性が、第２のしきい値の値よりも低い場合に、次の文字についての出発ポイントを算出するステップと、
ｉ）前記次の文字の前記算出された出発ポイントを出発ポイント座標の前記リストに追加することによって、前記次の文字の前記算出された出発ポイントをメモリに保持するステップと、
ｊ）前記第１のしきい値の値よりも高い第２のしきい値の値とエラーの前記可能性を比較するステップであって、ステップｆ）は、エラーの前記可能性が、前記第２のしきい値の値よりも低い場合にだけ実行される、ステップと
を含み、
ｋ）前記方法は、更に、可能性のある文字幅の前記リストの前記第１の幅に対応するエラーの前記可能性が、前記第１のしきい値の値よりも高い場合に、
１）前記出発ポイント座標に対応し、且つ可能性のある文字幅の前記リストの上の次の幅に対応する前記文字ストリング画像の第２の部分を決定するステップと、
２）前記文字ストリング画像の前記第２の部分に対して分類方法を適用して、この次の幅についてのエラーの可能性と、次の候補文字とを提供するステップと、
３）前記第１のしきい値の値と前記次の幅についてのエラーの前記可能性を比較するステップと、
４）幅に対応するエラーの前記可能性が、前記第１のしきい値の値よりも低くなるまで、或いは、可能性のある文字幅の前記リストの中に含まれるすべての前記幅が処理されてしまうまで、ステップ１）、２）、及び３）を反復するステップと、
５）前記幅に対応するエラーの前記可能性が、前記第１のしきい値の値よりも低い場合に、前記幅に対応する前記文字として前記候補文字を選択するステップと
を含み、
ｌ）出発ポイント座標の前記リストのすべての出発ポイント座標が処理されてしまうまで、ステップｂ）〜ｋ）を反復するステップ
を含む方法。
【請求項２】
幅に対応するエラーの前記可能性が、前記第１のしきい値の値よりも低い場合に、データベースに含まれる文字統計値をアップデートするステップ
をさらに含む、請求項１に記載の方法。
【請求項３】
可能性のある文字幅の前記リストは、最も可能性の高いものから、より可能性の低いものへとソートされ、
前記最も可能性の高い幅は、文字についての推定された最大幅よりも大きくない、最大数の接続された構成部分を含む最も広い幅であるような幅である、請求項１に記載の方法。
【請求項４】
可能性のある文字幅の前記リストのうちの２つのより可能性の低い幅は、平均グローバル幅と、前記平均グローバル幅の２分の１とであり、前記平均グローバル幅は、前記文字ストリング画像の中の第１の文字についての前記文字ストリング画像の高さであり、或いは、前記平均グローバル幅は、前記文字ストリング画像の中の後続の文字についての以前の平均グローバル幅と平均文字幅とに基づいて、算出される、請求項３に記載の方法。
【請求項５】
前記文字ストリング画像は、縦方向の文字ストリング画像であり、すべての幅は、高さである、請求項１に記載の方法。
【請求項６】
成功した反復時に前記平均グローバル幅の値で文字統計データベースをアップデートするステップをさらに含む、請求項４に記載の方法。
【請求項７】
可能性のある文字幅のリストを生成するステップは、与えられたポイント・サイズと、最大の参照文字の幅と、前記参照文字の平均幅と、前記参照文字の間の平均間隔のサイズとについて、前記参照文字を含むデータベースから取り出されるデータに基づいている、請求項１に記載の方法。
【請求項８】
前記データベースは、前記文字の統計値についての推定値をさらに含む、請求項７に記載の方法。
【請求項９】
前記データベースは、成功した反復時にアップデートされる、請求項８に記載の方法。
【請求項１０】
前記最大文字幅は、アジア文字についての最大文字幅である、請求項１に記載の方法。
【請求項１１】
コンピューティング・デバイスに、請求項１に記載の方法を使用することによって、入力画像の中の文字ストリング画像をセグメント化させるための制御ロジックを記憶しているコンピュータ使用可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ライン・セグメント化方法に関し、より詳細には、ＯＣＲシステム内で使用されるライン・セグメント化方法に関する。
【背景技術】
【０００２】
光学式文字認識（ＯＣＲ：Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅｃｏｇｎｉｔｉｏｎ）システムが、知られている。これらのシステムは、紙の文書を検索可能なテキスト文書へと自動的に変換する。ＯＣＲシステムは、一般的に、３つの主要なステップから、すなわち、ライン・セグメント化と、特徴抽出と、文字分類とから構成される。しかし、図１に示されるように、特徴抽出は、多くの場合、文字分類の一部分として提示される。そのようにして、文字ストリングの画像から出発して、知られている光学式文字認識システムは、個別の文字の画像になるようにライン・セグメント化を最初に適用し、その後に、文字分類ステップが実行されて、文字を識別する。文字分類技法は、ここ数年で非常に堅固になっているのに対し、ライン・セグメント化は、とりわけアジア・テキストの場合には、依然としてＯＣＲの決定的に重要なステップのままである。
【０００３】
ライン・セグメント化についての種々のアプローチが、存在している（多くの場合に文字セグメント化とも呼ばれている）。テキスト・ラインを表す画像は、文字画像を構成する個別の部分画像へと分解される。種々の方法を使用して、ラインをセグメント化することができる。知られているライン・セグメント化方法は、個別の文字を分離するやり方として文字間の切断部、又は単語の切断部（ラテン文字に適合される）を検出するものである。これは、例えば、ＷＯ２０１１１２８７７７及びＷＯ２０１１２６７５５に記載される。
【０００４】
例えば、ＷＯ２０１１１４２９７７に記載される、別の知られているライン・セグメント化方法は、文字を分離するラインを識別するために後で処理されるチョップ・ラインを使用している。例えば、ＥＰ０１３８４４５Ｂ１におけるさらに他の方法は、文字の間の一定のピッチを仮定している。
【０００５】
上記で説明されるライン・セグメント化方法は、ダイセクション方法（ｄｉｓｓｅｃｔｉｏｎ  ｍｅｔｈｏｄｓ）として知られている。このタイプの方法は、アジア・テキストと、ラテン・テキストと組み合わされたアジア・テキストとの場合には、あまり効率の良いものではない。その理由は、そのタイプのテキストにおいては、多くの場合に文字の間に明確な切断部又はピッチが存在しておらず、またアジア文字は、単一の接続された構成部分から作られておらず、ほとんどの場合はいくつかの接続された構成部分（例えば、漢字の部首）から作られているためである。
【０００６】
ライン・セグメント化の別のタイプの方法は、特定のアルファベットにおけるクラスにマッチする画像の中の構成部分の認識に基づいている。そのような方法は、しかしながら、長い計算時間を必要とする。
【０００７】
第３のタイプのセグメント化技法は、最初の２つの組合せを使用しており、「オーバーセグメント化」方法として、知られている。画像は、図２に示されるように異なるダイセクション方法を用いて、オーバーセグメント化される。いくつかの妥当と思われるセグメント化の問題解決手法が、同じ、又は異なる文字分類方法によって分析され、次いで最良のセグメント化の問題解決手法が選択される。例えば、アジア文字の場合におけるように、セグメント化が困難になるときには、多数の可能性のあるセグメント化の問題解決手法が評価され、その結果、入力ストリング画像を分析するために非常に長い計算時間がかかる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】ＷＯ２０１１１２８７７７
【特許文献２】ＷＯ２０１１２６７５５
【特許文献３】ＷＯ２０１１１４２９７７
【特許文献４】ＥＰ０１３８４４５Ｂ１
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ラインの高速且つ正確なセグメント化を提供する、文字ストリング画像の中の文字をセグメント化するための方法を提供することが、本発明の目的である。
【課題を解決するための手段】
【００１０】
これらの目的は、第１の独立請求項の技術的特性を示す、文字ストリング画像の中の文字をセグメント化するための方法を用いた本発明に従って達成される。本発明による文字ストリング画像の中の文字をセグメント化する方法は、
ａ）背景と対照を成すピクセルの第１の出発ポイント座標を決定するステップと、
ｂ）最大文字幅と、最大文字幅に対応する文字ストリング画像の部分の特性とに応じた、可能性のある文字幅のリストを生成するステップと、
ｃ）第１の出発ポイント座標と、第１の幅とに対応する文字ストリング画像の第２の部分を決定するステップと、
ｄ）文字ストリング画像の第２の部分に対して分類方法を適用して、第１の幅についてのエラーの可能性（likelihood of error）と、候補文字とを提供するステップと、
ｅ）速度と正確さとの間のトレードオフによって決定される第１のしきい値と、エラーの可能性を比較するステップと、
ｆ）第１の幅に対応するエラーの可能性が、しきい値の値よりも低い場合に、第１の幅に対応する文字として候補文字を選択するステップと
を含んでいる。
この方法の利点は、ライン・セグメント化と、文字分類とが、文字ごとに組み合わされたプロセスにされることである。文字ストリング画像のライン・セグメント化と、文字分類とを実行するステップの必要とされる数が、著しく低減されるので、これは、低減された算出時間の形の大きな利点を生み出す。その結果は、本方法の速度と、正確さとの増大である。
【００１１】
本発明による他の実施例においては、本方法は、第１のしきい値の値よりも高い第２のしきい値の値とエラーの可能性を比較するステップをさらに含んでおり、第１のしきい値の値とエラーの可能性を比較するステップは、エラーの可能性が、第２のしきい値の値よりも低い場合にだけ実行される。
【００１２】
第２のしきい値の値は、肯定的な結果をもたらす機会を有していない候補についての高速なフィルタリングを可能にするという利点を有する。
【００１３】
本発明による別の実施例においては、本方法は、第１の幅に対応するエラーの可能性が、第２のしきい値の値よりも低い場合に、次の文字についての出発ポイントを算出するステップと、次の文字の算出された出発ポイントをメモリに保持するステップとをさらに含む。
【００１４】
本発明による別の実施例においては、本方法は、第１の幅に対応するエラーの可能性が、第１のしきい値の値よりも低い場合に、データベースに含まれる文字統計値をアップデートするステップをさらに含んでいる。
【００１５】
このデータベースは、テキストの中の文字と、参照文字とについての最大サイズと平均サイズとについての情報を含んでいる。これらの値は、可能性のある文字幅のリストの生成における文字の幅を推定するときに、本方法の速度と正確さとを改善するために使用される。
【００１６】
本発明による別の実施例においては、可能性のある文字幅のリストは、最も可能性の高いものから、より可能性の低いものへとソートされ、最も可能性の高い幅は、データベースに記憶される文字についての推定された最大幅よりも大きくない、最大数の接続された構成部分を含む最も広い幅であるような幅である。
【００１７】
本発明による別の実施例においては、可能性のある文字幅のリストのうちの２つのより可能性の低い幅は、平均グローバル幅と、平均グローバル幅の２分の１とであり、平均グローバル幅は、文字ストリング画像の中の第１の文字についての文字ストリング画像の高さであり、また平均グローバル幅は、文字ストリング画像の中の後続の文字についての、データベースに記憶される以前の平均グローバル幅と平均文字幅とに基づいて、算出される。
【００１８】
これの利点は、アジア文字のサイズが、ラテン文字のサイズのおおよそ２倍であるため、平均グローバル幅は、アジア文字を識別するのに対し、平均グローバル幅の２分の１は、ラテン文字を識別し、それゆえに、この手段により、ライン・セグメント化方法を、ラテン文字と、アジア文字と、それらの組合せとに適用できることである。
【００１９】
本発明による別の実施例においては、可能性のある文字幅のリストの以前の幅に対応するエラーの可能性が、第２のしきい値の値よりも高い場合に、本方法は、
ａ）出発ポイント座標に対応し、且つリストの次の幅に対応する文字ストリング画像の第２の部分を決定するステップと、
ｂ）文字ストリング画像の第２の部分に分類方法を適用して、この幅についてのエラーの可能性を提供と、候補文字とを提供するステップと、
ｃ）データベースに記憶されるしきい値の値とエラーの可能性を比較するステップと、
ｄ）この幅に対応するエラーの可能性が、しきい値の値よりも低くなるまで、又は可能性のある文字幅のリストの中に含まれるすべての幅が処理されてしまうまで、ステップａ）と、ステップｂ）と、ステップｃ）とを反復するステップと、
ｅ）幅に対応するエラーの可能性が、第１のしきい値の値よりも低い場合に、幅に対応する文字として文字候補を選択するステップと
をさらに含む。
【００２０】
問題解決手法が見出されていない限り、また問題解決手法が見出されるまで、ライン・セグメント化と、文字分類とが、次々に、組み合わされ、実行される。これは、そのような方法を実行するために必要とされるステップの数を低減させることを可能にしており、また本方法の正確さを改善させもする。
【００２１】
本発明による別の実施例においては、文字ストリング画像は、縦方向の文字ストリング画像であり、すべての幅は、高さである。
【００２２】
アジア文字は、ラインに沿って書かれるが、列に沿って書かれる可能性もある。本方法は、確かにラインだけには限定されず、また文字の幅を高さに変更することだけにより、ラインに簡単に適合される可能性があり、また逆の場合も同様である。
【００２３】
別の実施例においては、本方法は、成功した反復時に平均グローバル幅値で文字統計データベースをアップデートするステップをさらに含んでいる。
【００２４】
本発明による別の実施例においては、可能性のある文字幅のリストを生成するステップは、与えられたポイント・サイズと、最大の参照文字の幅と、参照文字の平均幅と、参照文字の間の平均間隔のサイズとについて、参照文字を含むデータベースから取り出されるデータに基づいている。
【００２５】
本発明の別の実施例においては、データベースは、それらの文字の統計値についての推定値をさらに含んでおり、データベースは、成功した反復のたびにアップデートされる。
【００２６】
本発明の別の実施例においては、最大の文字幅は、アジア文字についての最大文字幅である。
【００２７】
本発明の別の実施例においては、コンピュータ・プログラム製品は、コンピューティング・デバイスに、入力画像の中の文字ストリング画像をセグメント化させるための制御ロジックを記憶しているコンピュータ使用可能媒体を備えており、その制御ロジックは、
ａ）背景と対照を成すピクセルの第１の出発ポイント座標を決定するための第１の制御読取り可能プログラム・コード手段と、
ｂ）最大文字幅と、最大文字幅に対応する文字ストリング画像の部分の特性とに応じた、可能性のある文字幅のリストを生成するための第２の制御読取り可能プログラム・コード手段と、
ｃ）可能性のある文字幅のリストの上の第１の出発ポイント座標と第１の幅とに対応する文字ストリング画像の第２の部分を決定するための第３の制御読取り可能プログラム・コード手段と、
ｄ）文字ストリング画像の第２の部分に対して分類方法を適用して、第１の幅についてのエラーの可能性と、候補文字とを提供するための第４の制御読取り可能プログラム・コード手段と、
ｅ）速度と正確さとの間のトレードオフによって決定される第１のしきい値とエラーの可能性を比較するための第５の制御読取り可能プログラム・コード手段と、
ｆ）第１の幅に対応するエラーの可能性が、しきい値の値よりも低い場合に、第１の幅に対応する文字として候補文字を選択するための第６の制御読取り可能プログラム・コード手段と
を備えている。
【００２８】
本発明は、さらに、以下の説明と、添付の図面とを用いて、明らかにされる。
【図面の簡単な説明】
【００２９】
【図１】先行技術による光学式文字認識プロセスにおける種々のステップを示す図である。
【図２】オーバーセグメント化として知られている最先端技術におけるライン・セグメント化のタイプを示す図である。
【図３】本発明の一実施例によるライン・セグメント化方法を示す図である。
【図４】文字統計データベースを有するライン・セグメント化方法を示す図である。
【発明を実施するための形態】
【００３０】
本発明は、特定の実施例に関して、ある図面を参照して説明されることになるが、本発明は、それに限定されず、特許請求の範囲だけによって限定される。説明される図面は、概略的なものにすぎず、また非限定的である。それらの図面においては、要素のいくつかのサイズは、誇張されることもあり、また例示の目的のために縮尺して描かれてはいない。それらの寸法と、相対的な寸法とは、必ずしも、本発明の実践に合わせた実際の縮小に対応しているとは限らない。
【００３１】
さらに、本説明及び特許請求の範囲における第１の、第２の、及び第３の、などの用語は、類似した要素を区別するために使用され、また必ずしも逐次的順序又は時間的順序を説明するために使用されるとは限らない。それらの用語は、適切な状況の下で交換可能であり、また本発明の実施例は、本明細書において説明又は例示される以外の他の順番でも動作することができる。
【００３２】
さらに、本説明及び特許請求の範囲における最上部、最低部、上の、及び下の、などの用語は、説明の目的のために使用され、必ずしも相対的な位置を説明するために使用されるとは限らない。そのように使用される用語は、適切な状況の下で交換可能であり、また本明細書において説明される本発明の実施例は、本明細書において説明又は例示される以外の他の向きにおいても動作することができる。
【００３３】
さらに、様々な実施例は、「好ましい」と称されるが、本発明の範囲を限定するものとしてではなく、本発明が実装され得る例示的なやり方として解釈されるべきである。
【００３４】
特許請求の範囲において使用される用語「含んでいる／備えている（ｃｏｍｐｒｉｓｉｎｇ）」は、それ以降にリストアップされる要素又はステップだけに限定されるように解釈されるべきではなく、その用語は、他の要素又はステップを除外しない。用語「含んでいる／備えている」は、述べられた特徴、整数、ステップ、又はコンポーネントの存在を言及されるように指定するように解釈される必要があるが、１つ又は複数の他の特徴、整数、ステップ又はコンポーネント、或いはそのグループの存在又は追加を除外することはしない。それゆえに、表現「ＡとＢとを備えているデバイス」の範囲は、コンポーネントＡとＢとだけから構成されるデバイスだけに限定されるべきではなく、本発明に関して言えば、デバイスの列挙されたコンポーネントが、ＡとＢとだけであり、またさらに、請求項は、これらのコンポーネントの均等物を含むように解釈されるべきである。
【００３５】
図３を参照すると、図３は、本発明の一実施例による光学式文字認識（ＯＣＲ）方法の流れ図を示すものである。本方法の入力は、文字ストリング画像１１０である。第１のステップにおいて、ライン・セグメント化１２０が、文字ストリング画像１１０に実行される。分析される文字の可能性のある幅についての予備情報が、算出される。文字の可能性のある幅についてのこの予備情報は、ＯＣＲ方法の速度を改善する、ステップの新しい順番を可能にする。オーバーセグメント化が、依然として使用されるが、必ずしもすべての可能性のある問題解決手法（２１０、２２０、２３０）が、ＯＣＲ方法によって体系的に分析される必要があるとは限らない。可能性のある問題解決手法は、候補文字幅のリストを用いて生成され（３１０）、最も可能性の高いものから、より可能性の低いものへとソートされる。ＯＣＲ方法は、最初に最も可能性の高い見込みのある問題解決手法２１０を分析する。測定エラーに対する条件が満たされる（３２０）場合、文字は分類され（１５０）、その他の可能性のある問題解決手法は、切り捨てられ、次の文字が分析される。測定エラーに対する条件が満たされない（３３０）場合、次の最も可能性の高い可能性のある問題解決手法が分析される（２２０）。このプロセスは、分類に成功した文字がない限り、又はすべての可能性のある問題解決手法が評価されてしまうまで、繰り返し反復される。
【００３６】
本方法は、ここで説明されるように、テキストのラインをセグメント化するために適用される。しかしながら、同じ方法を使用して、アジア・テキストの場合にしばしばそうであるように、テキストの列をセグメント化することができる。
【００３７】
上記で説明したように、最も可能性の高いものから、より可能性の低いものへと発生するように順序付けられる候補文字幅のリストが、文字画像の分析の前に、生成される（３１０）。候補文字幅のこのリストの生成は、本出願において後で説明する。リストは、Ｎ＋２個の候補幅を含んでおり、ここで、最初のＮ個の幅は、切断が、文字を抽出するために文字ストリング画像１１０において実行されるべきでない幅であり、また最後の２つの幅は、切断が、文字ストリング画像１１０において文字を分離させ、また抽出するために実行される必要がある幅である。
【００３８】
出発ポイントは、分析すべき新しい文字画像の位置を規定するｘ座標である。初期の出発ポイントのリストが、アルゴリズムの最初に作成され、ここでは、リストの最初の初期出発ポイントは、画像の左側の第１の黒色ピクセルに対応する。他の所定の出発ポイントは、ラインの端部、又は最も右側のピクセルに対応する。他の出発ポイントが、ＯＣＲプロセス中に、出発ポイントのリストに追加される。本方法は、リストの中に存在するすべての出発ポイントが処理されることを保証する。
【００３９】
文字画像は、接続された構成部分のリストに関連づけられる出発ポイント座標と幅とによって完全に規定される。ラインの高さは、すべての文字について同じである。ＯＣＲプロセスの終わりに、文字が分類される。
【００４０】
可能性のある問題解決手法が作成されると、文字分類方法１４０が、可能性のある問題解決手法に適用されて、文字が、この可能性のある問題解決手法について、分類され得るかどうかを決定する。本発明の一実施例においては、文字分類方法１４０は、ガボール（Gabor）関数に基づいたものである。
【００４１】
文字分類方法１４０は、本発明の一実施例によれば、２つの入力、すなわち、
−  文字ｎの出発ポイント座標ＳＰｎであって、出発ポイント座標は、分析すべき文字の左下の文字の第１のピクセルの（ｘ）座標である、出発ポイント座標ＳＰｎと、
−  文字ｎについての候補文字幅のリストから取られる候補幅ｗｉと
を必要とする。
【００４２】
出力は、文字Ｃｎを計算するために使用されるエラーの可能性Ｐｅｒｒである。エラーの可能性Ｐｅｒｒは、２つのしきい値パラメータ、すなわち、エラーの低い可能性を有するしきい値Ｔｌｅｒｒと、エラーの高い可能性を有するしきい値Ｔｈｅｒｒと比較される。Ｔｌｅｒｒと、Ｔｈｅｒｒとの値は、速度対正確さの要件に応じて、調整することができる。本発明の好ましい一実施例においては、ＴｌｅｒｒとＴｈｅｒｒとの値は、Ｔｌｅｒｒ＝２０％とＴｈｅｒｒ＝９９．９％とに設定される。エラーの低い可能性を有するしきい値Ｔｌｅｒｒは、分類が成功した文字を有する条件を規定する。
【００４３】
本発明の一実施例によるライン・セグメント化方法は、図４に示されるように文字統計データベース４００を使用している。次にそのデータベースの要素をリストアップする。どのようにして要素のうちのそれぞれが使用されるかについてのより詳細な説明が、本出願において、さらに続く。データベースは、
−  メモリに記憶される、アジア文字とラテン文字とについての、また選択されたポイント・サイズについての基準サイズ（高さ及び幅）のライブラリと、
−  メモリに記憶される、選択されたポイント・サイズについてのアジア文字とラテン文字とについての基準最大サイズ、それぞれ、ｗＭａｘ，Ａ，ｒ、及びｗＭａｘ，Ｌ，ｒと、
−  選択されたポイント・サイズについての、アジア・テキストとラテン・テキストとについて同じである基準平均文字間間隔、Ｓｒと、
−  分析されているテキストの中のアジア文字とラテン文字との推定最大幅、それぞれ、ｗＭａｘ，Ａ，ｔ、及びｗＭａｘ，Ｌ，ｔと、
−  分析されているテキストの中のアジア文字とラテン文字とについての平均文字間間隔、ｓｔと、
−  分類済みの文字だけについて算出される、対応する参照文字の幅を表す、アジア文字及びラテン文字ｎの幅のローカル推定値、それぞれＬｎ，Ａ及びＬｎ，Ｌであって、文字ｎの実際の幅と値とを使用して計算される文字のポイント・サイズの測定値である、アジア文字及びラテン文字ｎの幅のローカル推定値、それぞれＬｎ，Ａ及びＬｎ，Ｌと、
−  分類済みの文字だけについて算出される、対応する参照文字の幅を表す、文字の幅のグローバル推定値、Ｇｎと
を含む。Ｇｎの値は、以前に測定されたローカル推定値Ｌｎの移動平均であり、それゆえに、平均文字ポイント・サイズのより正確な測定値である。この値は、間違って分類された文字に対してより許容性があるので、より信頼できるものである。
【００４４】
図４を参照すると、図４は、本発明の一実施例によるライン・セグメント化プロセスの流れ図を示すものである。プロセスは、文字Ｃｎのセグメント化について例示される。文字ＣｎについてのすべてのＮ＋２個の候補文字幅のリスト３１０が生成され、第１の候補文字幅ｗ１が、候補文字幅のリストから取られる。これらの２つの値、ＳＰｎとｗ１とは、ステップ４２０における文字分類方法１４０のための入力４１０である。ステップ４２０の出力は、エラーの可能性Ｐｅｒｒである。
【００４５】
Ｐｅｒｒの値に応じて、２つのオプションが可能である。エラーの可能性Ｐｅｒｒが、エラーの高い可能性を有するエラーについてのしきい値Ｔｈｅｒｒよりも低い（４２１）場合は、文字Ｃｎが、可能性のある問題解決手法である。第１の候補幅ｗ１に対応する文字Ｃｎは、次いで、メモリに保持され、次の文字の出発ポイントが算出され、必要に応じて処理されるように出発ポイントのリストに追加され、すなわち、ＳＰｎ＋１＝ＳＰｎ＋ｗ１＋ｓＡ，ｔとなる（４２５）。さらに、エラーの可能性Ｐｅｒｒがまた、エラーの低い可能性を有するエラーについてのしきい値Ｔｌｅｒｒよりも低い（４２２）場合、文字Ｃｎは、分類が成功したと考えることができ、本説明において後で説明されるように文字統計データベースがアップデートされる（４００）。本方法は、次の出発ポイントＳＰｎ＋１へと移動（４０５）して、現在の出発ポイントＳＰｎについて他の幅を処理することなしに、次の文字Ｃｎ＋１を決定することができる。エラーの可能性Ｐｅｒｒが、エラーの低い可能性を有するエラーについてのしきい値Ｔｌｅｒｒよりも高い（４２３）場合、文字分類方法は、以下で説明されるように、次の候補幅ｉ，ｗｉを用いて実行される（４３０）。
【００４６】
しかしながら、エラーの可能性Ｐｅｒｒが、エラーの高い可能性を有するエラーについてのしきい値Ｔｈｅｒｒよりも高い（４２４）場合には、候補幅１，ｗ１に対応する文字Ｃｎは、メモリに保持されず、新しい出発ポイントは、算出されない。
【００４７】
文字分類方法は、次の候補幅ｉ，ｗｉを用いて実行される（４３０）。この場合にも、Ｐｅｒｒの値に応じて、２つのオプションが存在している。ＰｅｒｒがＴｈｅｒｒよりも低い（４３１）場合、文字Ｃｎは、幅ｗｉとともに記憶され、次の文字の出発ポイントが算出され、必要に応じて処理されるべき出発ポイント（４０５）のリストに追加され、また、ＰｅｒｒがまたＴｌｅｒｒよりも低い（４３２）場合は、文字統計データベースがアップデートされる（４００）。しかしながら、ＰｅｒｒがＴｌｅｒｒ及び／又はＴｈｅｒｒよりも高い（４３５、４３３）場合、文字分類方法は、リストのすべての幅が処理されてしまう（ｉ＝Ｎ）まで、或いは文字の分類が成功する（Ｐｅｒｒ＜Ｔｌｅｒｒ）まで、次の候補幅ｉ＋１，ｗｉ＋１を用いて、実行される。
【００４８】
ｉ＝Ｎ＋１では、同じプロセスが反復されるが、今や幅ｗＮ＋１は、第１の切断が、幅の値ｗＮ＋１＝ｗＭａｘ，Ａ，ｔについて実行されるような幅になっている（４４０）。文字が、ｉ＝Ｎ＋１についてエラーの低い可能性Ｐｅｒｒ＜Ｔｌｅｒｒを用いて分類されていない（４４３又は４４５）場合、そのときにはプロセスは、ｉ＝Ｎ＋２について反復され、ここでｗＮ＋２＝ｗＭａｘ，Ｌ，ｔ（４５０）であり、この場合にも、４５２を伴う４５１や４５３又は４５４を伴う４５１など、異なる経路が可能である。
【００４９】
オーバーセグメント化の必ずしもすべての問題解決手法は分析しないようにするために、文字ｎ（Ｃｎ）についてのすべてのＮ＋２個の候補幅｛ｗｉ｝のリストは、以下のように生成され、すなわち、候補幅は、最も可能性の高いものから、より可能性の低いものへとソートされ、また候補幅の数は、接続された構成部分の数を用いて測定される可能性のある文字の形状に応じて、文字ごとに変化する。観察に基づいて、アジア文字の幅は、そのときにより小さな幅を有する数少ない文字を除いて、ほとんどの文字に共通であると仮定される。本発明の一実施例によれば、最も可能性の高い幅は、より広いアジア文字の推定幅（ｗＭａｘ，Ａ，ｔ）に文字間の推定平均間隔（ｓｔ）を加えたものよりも広くない、接続された構成部分の最大の組を含む幅に対応する。
【００５０】
文字は、非接触形(non-touching)、又は接触形(touching)である可能性がある。非接触形文字は、より高い発生確率を有しており、それゆえに、最初に考慮されるべきである。
【００５１】
非接触形文字では、（切断は必要でなく）、ピクセル単位で算出されるインデックスｉを有する候補幅（ｗｉ）は、最も幅の広いアジア文字（ｗＭａｘ，Ａ，ｔ）よりも小さいｐ（ｐ≧０）個の接続された構成部分の組に文字の間の平均推定間隔（ｓｔ）を加えたものを有するｉ番目の最大の幅となる。幅ｗｉは、ｐ個の接続された構成部分を有しており、幅ｗｉ＋１は、ｐ個又はそれより少ない接続された構成部分を有しており、またｗｉ＋１≦ｗｉとなる。
【００５２】
最も幅の広いアジア文字（ｗＭａｘ，Ａ，ｔ）と、文字の間の推定間隔（ｓｔ）とは、文字統計データベースにおいて評価される。Ｎ個の可能性のある非接触形文字が、存在している。
【００５３】
２つの隣接する文字が、接触形である場合に、切断が実行される必要があり、それらの文字は、文字Ｃｎについての以前の反復（ｎ−１）時にアップデートされた文字統計データベースにおいて見出され得る文字の平均グローバル幅Ｇｎ−１から算出される、最も可能性の高い場所において切断される。インデックスＮ＋１を有する幅ｗＮ＋１は、アジア文字の平均グローバル幅Ｇｎ−１と、平均間隔ｓｔとの合計に対応する。インデックスＮ＋２を有する幅ｗＮ＋２は、ラテン文字の平均幅Ｇｎ−１／２と、平均間隔ｓｔとの合計に対応する。ラテン文字の幅は、アジア文字の幅の２分の１であることが、仮定される。
【００５４】
要約すると、反復ごとに、文字ｎの入力候補幅のリストは、
ｗｉ＝ｐ個の接続された構成部分のｉ番目に大きい組の幅（ｗｉ＝ｗＭａｘ＋ｓｔ，ｉ＝１，．．．，Ｎ；Ｎ≧０）
ｗＮ＋１＝Ｇｎ−１＋ｓｔ、
ｗＮ＋２＝Ｇｎ−１／２＋ｓｔ
によって与えられ、式中で、ｗＭａｘ，Ａ，ｔ、Ｇｎ−１、ｓｔ、ｓｔは、文字が分類された（すなわちＰｅｒｒ＜Ｔｌｅｒｒ）たびにアップデートされる文字統計データベースに由来する値である。
【００５５】
データベースは、参照文字のライン及びライブラリから抽出される文字情報、並びにこれらの文字についての統計値を記憶するデータ構造を含んでいる。単一のデータ構造が、プロセスの最初に作成され、その構造は、そのときには空である。メモリに記憶されるデータ構造は、反復ごとにアップデートされ、またその構造は、グラフに類似している。
【００５６】
データベースのすべてのパラメータは、以下の表、すなわち、
【表１】
0006693887.tif 000002
に要約され、またデータベースの種々のパラメータの評価が、次に説明される。
【００５７】
最大のアジア文字とラテン文字との幅は、
【数１】
0006693887.tif 000003
【数２】
0006693887.tif 000004
のように評価され、ここで、比例比率は、テキストの中の文字のポイント・サイズに対するライブラリの中の文字のポイント・サイズの変換を表している。
【００５８】
同じことが、アジア文字とラテン文字との平均サイズについて行われ、それぞれ、
【数３】
0006693887.tif 000005
【数４】
0006693887.tif 000006
となる。この値は、文字ｎの幅のローカル推定値を表しており、この値をさらに使用して、ステップｎにおいて文字の幅のグローバル推定値を評価する。
【００５９】
ステップｎにおける文字の幅のグローバル推定値Ｇｎは、以下の式、
【数５】
0006693887.tif 000007
を使用して算出され、式中で、Ｇｎ−１は、ステップｎ−１においてアップデートされる文字の平均幅のグローバル推定値であり、Ｌｎは、ステップｎにおける文字の平均サイズのローカル推定値であり、ｎは、本方法の現在のステップのインデックスであり、またＧ０は、ラインの高さである（アジア文字は正方形と仮定される）。この式は、アジア文字とラテン文字とについて有効である。ラテン文字では、幅のグローバル推定値は、アジア文字のグローバル推定値の２分の１であると仮定される。
【００６０】
最後に、同じ比例関係が、テキストの中の文字間間隔ｓｔを推定するために適用され、テキストのポイント・サイズが、参照文字のポイント・サイズとは異なるときには、すなわち、
【数６】
0006693887.tif 000008
となる。
【００６１】
この実施例は、ライン・セグメント化方法の場合を示しているが、本方法は、ラインに限定されない。アジア・テキストはまた、列の中に書かれる可能性もあり、同じ方法が使用されることが可能である。その場合には、文字の幅は、文字の高さに置き換えられる必要があり、また出発ポイント座標は、文字ストリング画像の最上部における文字の第１のピクセルの（ｙ）座標になる。
【図１】
0006693887.tif 000009
【図２】
0006693887.tif 000010
【図３】
0006693887.tif 000011
【図４】
0006693887.tif 000012