(57)【要約】【課題】希な複数文字のクラスタに対して品質プロトタイプとしての合成リガチャーを生成することによって、スキャン画像の品質を向上させる方法およびシステムを提供する。【解決手段】スキャン文書内で２つ以上の接触する文字を含むリガチャーを識別する方法であって、前記リガチャーの前記２つ以上の接触する文字が複数のプロトタイプと比較されて２つ以上の合致するプロトタイプを識別する。次いで合成リガチャーが前記２つ以上の合致するプロトタイプに基づいて生成される。【選択図】図１
2007226803.tif 000002
【特許請求の範囲】
【請求項１】
スキャン文書内の２つ以上の接触する文字を含むリガチャーを識別するステップと、
複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別するステップと、
前記２つ以上の合致するプロトタイプに基づいて合成リガチャーを生成するステップとを含む方法。
【請求項２】
前記スキャン文書内の類似のスキャン画像を複数のクラスタにグループ分けするステップと、
前記複数のクラスタのうちの１つのクラスタに対してプロトタイプを生成するステップであって、前記プロトタイプが前記クラスタの類似のスキャン画像を処理することに基づく、前記ステップとをさらに含む請求項１に記載の方法。
【請求項３】
前記クラスタのスキャン画像の属性が知られているキャラクタ・タイプとリガチャー・タイプと比較することに基づいて、キャラクタ・タイプあるいはリガチャー・タイプに従って前記クラスタを分類するステップをさらに含む請求項２に記載の方法。
【請求項４】
前記スキャン文書に関連する光学式文字認識（ＯＣＲ）データを用いて、前記クラスタをタイプ文字あるいはリガチャーとして分類するステップをさらに含む請求項２に記載の方法。
【請求項５】
前記スキャン文書に関連する光学式文字認識（ＯＣＲ）データを用いて、前記プロトタイプをタイプ文字あるいはリガチャーとして分類するステップをさらに含む請求項２に記載の方法。
【請求項６】
前記複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別するステップが、
前記リガチャーの前記２つ以上の接触する文字に対応する２つ以上のタイプ文字を識別するステップと、
識別された２つ以上のタイプ文字を前記複数のプロトタイプの対応するプロトタイプとつき合わせて前記２つ以上の合致するプロトタイプを識別するステップとをさらに含む請求項２に記載の方法。
【請求項７】
それぞれの単一タイプ文字とそれぞれ生成された各合成リガチャーに対応するプロトタイプから合成フォント・ライブラリを生成するステップをさらに含む請求項６に記載の方法。
【請求項８】
前記合成フォント・ライブラリを用いて、前記スキャン文書に対応する新しい画像を生成するステップをさらに含む請求項７に記載の方法。
【請求項９】
前記クラスタの前記類似のスキャン画像を処理して前記プロトタイプを生成するステップが、前記クラスタの前記スキャン画像に関連する１つまたは複数の属性値を平均化するステップをさらに含む請求項２に記載の方法。
【請求項１０】
前記１つまたは複数の属性値が、文字ピクセル値、文字寸法値、リガチャー・ピクセル値、およびリガチャー寸法値のうちの少なくとも１つを含む請求項９に記載の方法。
【請求項１１】
前記クラスタの特定のスキャン画像がリガチャーである場合、かつ前記クラスタのスキャン画像の数が最小閾値を越える場合、前記合成リガチャーを生成するステップが、前記クラスタの前記スキャン画像に関連する１つまたは複数の属性値を平均化するステップをさらに含む請求項１０に記載の方法。
【請求項１２】
前記複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別するステップが、
前記複数のプロトタイプのうちの１つのプロトタイプを前記合成リガチャーの前記２つ以上の文字のうちの第１の文字にオーバーレイさせるステップと、
前記プロトタイプと前記リガチャーの前記第１の文字のそれぞれのピクセルを、ピクセル毎に検査するステップとをさらに含む請求項１に記載の方法。
【請求項１３】
前記オーバレイされたプロトタイプと前記第１の文字との間で共通するピクセルを検査してカウンタｘＰ、ｘＮ、ｙＰ、ｙＮを計算し、かつ垂直と水平安定度インデックスを計算するステップと、
カウンタｘＰ、ｘＮ、ｙＰ、ｙＮ、および垂直と水平安定度インデックスを用いて、前記オーバレイされたプロトタイプの前記合成リガチャー内の配置を決定するステップとによって、
前記第１の文字の配置を計算するステップをさらに含む請求項１２に記載の方法。
【請求項１４】
スキャン文書内の２つ以上の接触する文字からなるリガチャーを識別し、複数のプロトタイプから、前記リガチャーの２つ以上の接触する文字に対応する２つ以上の合致するプロトタイプをつき合わせるクラスタ・モジュールと、
前記２つ以上の合致するプロトタイプから合成リガチャーを生成するプロトタイプ・モジュールとを含むシステム。
【請求項１５】
前記スキャン文書内の類似のスキャン画像を複数のクラスタにグループ分けするクラスタ・モジュールと、
前記複数のクラスタのうちの１つのクラスタに対してプロトタイプを生成するプロトタイプ・モジュールであって、前記プロトタイプが前記クラスタの類似のスキャン画像を処理することに基づくプロトタイプ・モジュールとをさらに含む請求項１４に記載のシステム。
【請求項１６】
前記クラスタ・モジュールが、前記クラスタのスキャン画像の属性を知られているキャラクタ・タイプとリガチャー・タイプとを比較することに基づいて、キャラクタ・タイプあるいはリガチャー・タイプに従って前記類似のスキャン画像のクラスタを分類することになる請求項１５に記載のシステム。
【請求項１７】
前記クラスタ・モジュールが、前記スキャン文書に関連する光学式文字認識（ＯＣＲ）データに基づいて、前記類似のスキャン画像のクラスタをタイプ文字あるいはリガチャーとして分類することになる請求項１５に記載のシステム。
【請求項１８】
前記クラスタ・モジュールが、前記スキャン文書に関連する光学式文字認識（ＯＣＲ）データに基づいて、前記プロトタイプをタイプ文字あるいはリガチャーとして分類することになる請求項１５に記載のシステム。
【請求項１９】
前記複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別する前記プロトタイプ・モジュールが、
前記リガチャーの前記２つ以上の接触する文字に対応する２つ以上のタイプ文字を識別し、
識別された２つ以上のタイプ文字を対応する分類されたプロトタイプとつき合わせて前記２つ以上の合致するプロトタイプを識別するプロトタイプ・モジュールをさらに含む請求項１８に記載のシステム。
【請求項２０】
前記プロトタイプ・モジュールが、それぞれの単一タイプ文字およびそれぞれ生成された合成リガチャーに対応するプロトタイプから合成フォント・ライブラリを生成することになる請求項１９に記載のシステム。
【請求項２１】
前記合成フォント・ライブラリを用いて、前記スキャン文書に対応する新しい画像を生成するページ表示モジュールをさらに含む請求項２０に記載のシステム。
【請求項２２】
前記クラスタの前記類似のスキャン画像を処理して前記プロトタイプを生成する前記プロトタイプ・モジュールが、前記クラスタの前記スキャン画像に関連する１つまたは複数の属性値を平均化することになる請求項１５に記載のシステム。
【請求項２３】
前記１つまたは複数の属性値が、文字ピクセル値、文字寸法値、リガチャー・ピクセル値、リガチャー寸法値のうちの少なくとも１つを含む請求項２２に記載のシステム。
【請求項２４】
前記クラスタの特定のスキャン画像がリガチャーである場合、かつ前記クラスタのスキャン画像の数が閾値を越える場合、前記合成リガチャーを生成する前記プロトタイプ・モジュールが、前記クラスタの前記スキャン画像に関連する１つまたは複数の属性値を平均化することになる請求項２３に記載のシステム。
【請求項２５】
複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別する前記プロトタイプ・モジュールが、
前記複数のプロトタイプのうちの１つのプロトタイプを前記合成リガチャーの２つ以上の文字のうちの第１の文字に、前記第１の文字の１つまたは複数の端に基づく初期配置を用いてオーバーレイし、
前記プロトタイプと前記リガチャーの前記第１の文字のそれぞれのピクセルを、ピクセル毎に検査するプロトタイプ・モジュールをさらに含む請求項１４に記載のシステム。
【請求項２６】
前記合致した文字の最良の配置を計算する前記プロトタイプ・モジュールが、
前記オーバレイされたプロトタイプと前記リガチャーの前記文字との間で共通するピクセルを検査してカウンタｘＰ、ｘＮ、ｙＰ、ｙＮを計算し、かつ垂直と水平安定度インデックスを計算し、
カウンタｘＰ、ｘＮ、ｙＰ、ｙＮ、および垂直と水平安定度インデックスを用いて、前記オーバレイされたプロトタイプの前記合成リガチャー内の配置を決定し、前記配置が前記スキャン文書内の前記リガチャーの元の配置に近似する請求項２５に記載のシステム。
【請求項２７】
機械によって実行されるとき、
スキャン文書内の２つ以上の接触する文字であるリガチャーを識別することと、
複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別することと、
前記２つ以上の合致するプロトタイプに基づいて合成リガチャーを生成することと
を含むオペレーションを前記機械に実施させる命令を実装する有形の機械可読媒体。
【請求項２８】
前記複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別することが、
前記複数のプロトタイプのうちの１つのプロトタイプを前記合成リガチャーの前記２つ以上の文字のうちの第１の文字にオーバーレイすることと、
前記プロトタイプと前記リガチャーの前記第１の文字のそれぞれのピクセルを、ピクセル毎に検査することとをさらに含む請求項２７に記載の有形の機械可読媒体。
【請求項２９】
前記スキャン文書内の類似のスキャン画像を、複数のクラスタにグループ分けすることと、
前記複数のクラスタのうちの１つのクラスタに対してプロトタイプを生成することであって、前記プロトタイプが前記クラスタの前記類似のスキャン画像を処理することに基づくこととをさらに含む請求項２７に記載の有形の機械可読媒体。
【請求項３０】
前記クラスタのスキャン画像の属性を知られているキャラクタ・タイプとリガチャー・タイプとを比較することに基づいて、キャラクタ・タイプあるいはリガチャー・タイプに従って、前記クラスタを分類することをさらに含む請求項２９に記載の有形の機械可読媒体。
【請求項３１】
前記複数のプロトタイプを前記リガチャーの前記２つ以上の接触する文字と比較して２つ以上の合致するプロトタイプを識別することが、
前記リガチャーの前記２つ以上の接触する文字に対応する２つ以上のタイプ文字を識別することと、
識別された２つ以上のタイプ文字を前記複数のプロトタイプの対応するプロトタイプとつき合わせて前記２つ以上の合致するプロトタイプを識別することとをさらに含む請求項２９に記載の有形の機械可読媒体。
【請求項３２】
それぞれの単一タイプ文字とそれぞれ生成された各合成リガチャーに対応するプロトタイプから合成フォント・ライブラリを生成することをさらに含む請求項３１に記載の有形の機械可読媒体。
【請求項３３】
前記合成フォント・ライブラリを用いて、前記スキャン文書に対応する新しい画像を生成することをさらに含む請求項３２に記載の有形の機械可読媒体。
【請求項３４】
スキャン文書内の２つ以上の接触する文字であるリガチャーを識別する手段と、
前記リガチャーの前記２つ以上の接触する文字を複数のプロトタイプとつき合わせて対応する２つ以上の合致するプロトタイプを識別する手段と、
前記２つ以上の合致するプロトタイプから合成リガチャーを生成する手段と
を含むコンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、一実施形態による、希な複数文字(sparse multi-character)のクラスタに対して品質プロトタイプとしての合成リガチャーを生成することによって、スキャン画像の品質を向上させる方法およびシステムに関する。
【背景技術】
【０００２】
現在、スキャンされた文書、すなわちスキャン文書が現代の団体間の通信文のかなりの部分を占めている。しかし、これらスキャン文書の品質には、スキャナの品質、選択したスキャンの解像度、元の文書の品質など様々な要因によって相当な幅がある。スキャン文書の品質があまりにも劣る場合、読むのが困難あるいは不可能なこともある。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
スキャン文書に特定な問題は、２つ以上の接触する文字(touching characters)であるリガチャーの発生である。例えば、「ｆ」はしばしば「ｉ」と接触して「ｆｉ」リガチャーを作り、また２つの「ｆ」が接触して「ｆｆ」リガチャーになる。視覚的により高品質の文書を生成しようと試みて、より視覚的に魅力ある文字を生成するために、スキャン画像に何らかの処理を施すことができる。しかし、一般にはスキャン文書中にリガチャーを描出したスキャン画像が滅多にないことから、より視覚的に魅力あるリガチャーを生成することは難しい。その結果が、視覚的に調和に欠ける魅力のない文書となる。
【課題を解決するための手段】
【０００４】
例示的な一態様によれば、スキャン文書の品質を向上させる方法が提供される。スキャン文書が受け取られ、そのスキャン文書内のリガチャーが識別される。この場合、リガチャーは２つ以上の接触する文字を含む。複数のプロトタイプが、識別されたリガチャーの１つまたは複数の接触する文字と比較され、２つ以上の合致するプロトタイプを識別する。次いで、そのリガチャーに対して、２つ以上の合致するプロトタイプに基づいて、合成リガチャーが生成される。
【０００５】
他の特徴は、添付の図面および以下の詳細な説明から明らかとなろう。
【発明を実施するための最良の形態】
【０００６】
添付の図面の諸図に限定でなく例示のために実施形態が示され、同じ参照番号は同様の要素を示す。
【０００７】
以下の説明では、説明の目的で、本発明の一実施形態の包括的理解を提供するために多数の具体的詳細が示される。しかし、本発明がそうした具体的詳細なしでも実行されてよいことは当業者には明らかであろう。例示的な一実施形態では、グリフがタイプ文字（タイプ・キャラクタ）の一意の特徴的形態あるいは表現である。グリフの真の形態は、その輪郭を正確に定義する１組の式である。タイプ文字（以下、「キャラクタ・タイプ」と代替可能）は、名付けられた、あるいは分類されたグリフ（例えば、文字「ａ」）である。リガチャーは、２つ以上の接触するタイプ文字のグリフである。ブロブ(blob)は、１つまたは複数のグリフのスキャン画像であり、リガチャーのスキャン画像を含んでいる。クラスタはブロブの集合（例えば、類似のブロブ）である。希な複数文字クラスタは、僅かなブロブ（例えば１０またはそれ以下。この閾値は設定可能である）を含むクラスタであり、これはリガチャーに相当している。プロトタイプは、クラスタの理想化された表現である。フォントは、（例えば、共通のタイプフェイス・デザインやサイズ（例えば、１２ポイント、Ｈｅｌｖｅｔｉｃａ  Ｂｏｌｄ）をもつ）タイプ文字の集合である。合成フォントは、スキャンされたグリフから抽出されたフォントである。合成フォントは、未知の「ノーマル」フォントによって生成されてもよく、各クラスタから抽出された分類されたプロトタイプ（例えば、文字「ａ」の理想化された変形形態）を含んでもよい。スキャン画像は、文書撮像デバイス（例えば、スキャナ）によって生成されるデータである。次いでスキャン画像のデータが処理されて、元の文書の視覚的表現を生成するのに使用される。
【０００８】
例示的な一実施形態では、スキャン文書を基にするスキャンしたグリフ画像（ブロブ）の自動分析を用いて合成フォントが抽出され、この合成フォントを用いて、より高品質テキストをもつ元の文書の知覚的に劣化のない複製を生成する。スキャン画像が、ごく稀にしか生じることのないリガチャー（例えば、２つ以上の接触するタイプ文字）である場合でも、元の文書に見られるそのリガチャーの元の間隔と向き(spacing and orientation)をなお失わず、元のリガチャーのより高品質な複製である合成フォントが生成される。この例示的な実施形態では、この自動化された手順によって、例えば、フォトコピー、ファックス、スキャンを何度も繰り返すことによって生じることのある元の文書の歪みに対応できる。
【０００９】
図１は、例示的な一実施形態による、スキャン文書の高品質（例えば、知覚的に劣化のない）バージョンを生成するように構成されたシステム１００を示す構成図である。システム１００は、合成フォント生成器１０２を含み、この合成フォント生成器が、プロトタイプ・モジュール１０４とクラスタ・モジュール１０６を含む。クラスタ・モジュール１０６が、データ記憶デバイス１１０からスキャン文書１０８を受け取る。一実施形態では、スキャン文書１０８は、スキャナ・アプリケーション１１４や任意選択でＯＣＲ（光学式文字認識）アプリケーション１１５によって処理された元の文書１１２から生成される。ＯＣＲアプリケーション１１５は、コンピュータ・ソフトウェアに実装され、スキャナ・アプリケーション１１４によってキャプチャされてよく、タイプされたテキストの画像（例えば、グリフ）を機械で編集可能なテキストに変換する、あるいは文字の画像をそれらを表す標準符号化方式（ＡＳＣＩＩあるいはＵｎｉｃｏｄｅ）に変換するように構成されている。
【００１０】
スキャン文書１０８は、グリフのスキャン画像を表す、ブロブの形式でのデータで構成される。２つ以上の接触する文字から成るグリフ、すなわちリガチャーであるブロブもあってよい。クラスタ・モジュール１０６は、スキャン画像からブロブを抽出し、視覚的に類似のブロブをクラスタにグループ分けする。図２は、ブロブ、クラスタ、プロトタイプの例を示す。クラスタ２０２とクラスタ２０６は各々、ブロブ・セット２０４とブロブ・セット２０８をそれぞれ含む。クラスタ２１０はブロブ２１２を含み、これは２つの接触する文字によって示されるリガチャーである。
【００１１】
一実施形態では、クラスタ・モジュール１０６が、マッチング・アルゴリズム(matching algorithm)１０９を利用して、各ブロブをスキャン文書のその他のブロブと比較して、各クラスタを生成する。マッチング・アルゴリズム１０９は、対のグリフの共通グリッド上でのオーバーレイを含み、両方のグリフが同じ色（例えば、黒）を有する、グリッド・セルの百分比を計算する。リガチャーも同様にしてグループ化されるが、リガチャーの生じる可能性が低いため、クラスタ中にリガチャーが１つ程度と僅かであろう。スキャン文書１０８内のブロブをつき合わせるマッチング・アルゴリズム１０９には多数のアルゴリズムが存在していることは理解されるであろう。どのアルゴリズムを実装するかは、ハードウェアおよび／またはソフトウェアの機能などの要因に基づいた設計上の選択である。
【００１２】
クラスタ・モジュール１０６がクラスタ２０２、２０６、２１０を生成すると、プロトタイプ・モジュール１０４が各クラスタについてプロトタイプ集合１０５を生成する。例えば、クラスタ・モジュール１０６が、それぞれクラスタ２１０、２０２、２０６からのプロトタイプ２１３、２１４、２１６で構成されるプロトタイプ集合１０５を生成する。一実施形態では、プロトタイプ・モジュール１０４が、１つまたは複数の複製アルゴリズム１０３を用いて各クラスタのブロブ（例えば、単一の文字またはリガチャー）を処理して、個々のブロブのどれよりも元のグリフの真の姿のより正確な複製であるプロトタイプを生成する。他の実施形態では、クラスタ内のブロブ数が最小閾値を越える場合、プロトタイプ・モジュール１０４が、１つまたは複数の複製アルゴリズム１０３を用いてクラスタのブロブを処理するだけである。プロトタイプ・モジュール１０４は、単一タイプ文字クラスタやリガチャーのクラスタに対してカウント・オペレーションを実施して、各クラスタ内のタイプ文字とリガチャーの総数を決定する。次いでプロトタイプ・モジュールは、各クラスタの総数が閾値１０７を越える（例えば、一クラスタで５０ブロブ以上）場合、１つまたは複数の複製アルゴリズム１０３を使用して各クラスタを処理して、各プロトタイプを生成する。より高品質なリガチャー（例えば、合成リガチャー２１８）の生成についての詳細は、以下でさらに詳細に論じられる。
【００１３】
様々な実施形態で、最小閾値は設定可能であり、かつ／またはプロトタイプを生成するのにどの選択されたプロトタイプ・アルゴリズムが使用されるかに基づく。例えば、クラスタ内のブロブ数が３０を越える場合、プロトタイプ・モジュール１０４は、そのクラスタの各ブロブ（例えば、クラスタ２０２のブロブ・セット２０４の）を、中心軸と境界位置（例えば、各ブロブの左下角）に合わせてアラインさせるかオーバーレイさせ、プロトタイプを生成するために各ブロブのピクセル毎の比較を実施する。ブロブの半数以上が共通のピクセルをもつ場合、プロトタイプ・モジュール１０４はそのピクセルをプロトタイプに加える。同様の分析が、プロトタイプが完成するまで、クラスタ内のブロブの対応するピクセルすべてに対してなされる。プロトタイプを生成する例示的なアルゴリズムは、最適なブロブ・アラインメントを達成するか、プロトタイプの各ピクセルの黒さが、対応する黒のピクセルをもつグリフの百分比を反映する灰色プロトタイプの生成を達成する部分的なピクセル・シフトの使用を含む。例えば、オーバレイさせた４０のグリフのうち３０がグリッド・セルに黒のピクセルをもつ場合、対応するプロトタイプのピクセルのシェードは７５パーセントの黒さである。
【００１４】
元のグリフの真の形態のより正確な複製であるプロトタイプを生成するアルゴリズムが多数存在してよいことは理解されるであろう。どのアルゴリズムが使用されるかは、ハードウェアおよび／またはソフトウェアの機能などの要因に基づいた設計上の選択である。
【００１５】
図２に戻ると、プロトタイプ・モジュール１０４が、上記で説明したように、クラスタ２０２のブロブ・セット２０４を処理して、ブロブ・セット２０４のブロブの真の形態の高品質な複製であるプロトタイプ２１４（「ｅ」）を生成する。同様にして、プロトタイプ・モジュール１０４は、クラスタ２０６のブロブ・セット２０８を処理して、プロトタイプ２１６を生成する。しかし、クラスタが僅かな数のブロブしか含まない場合、例えばクラスタ２１０のブロブ２１２で表されているような、希な複数文字（例えば、リガチャー）のクラスタの場合、生成されるプロトタイプ２１３は、１つまたは複数のブロブそれ自体（元のリガチャー）とほとんど変わらないノイズのある品質のものとなるので、限られた値をもつことになる。このことは一般にリガチャーに当てはまる。スキャン文書中にリガチャーが生じることがごく稀だからである。
【００１６】
一実施形態では、希な複数文字のリガチャーを克服するために、プロトタイプ・モジュール１０４が、リガチャーの２つ以上のタイプ文字（またはキャラクタ・タイプ、例えば、文字「ｅ」）を識別し合成リガチャー（例えば、合成リガチャー２１８）を生成して、リガチャーで識別されたのと同じタイプ文字に一致する、先に生成されたプロトタイプに基づいて、不適切なプロトタイプ（例えば、プロトタイプ２１３）と取り換える。一実施形態では、プロトタイプ・モジュール１０４が、スキャン文書１０８のＯＣＲデータに基づいて、各プロトタイプを、そのキャラクタ・タイプ（例えば、「ｅ」「ｃ」など）に従って分類する。言い換えると、クラスタ内のブロブ（例えば、ブロブ・セット２０４やブロブ２１２（リガチャー））のタイプ文字は、スキャン文書１０８やスキャナ・アプリケーション１１４によって、各プロトタイプの生成より先に知られ、それにしたがってプロトタイプ・モジュール１０４は各プロトタイプを分類する。例えば、プロトタイプ２１４はタイプ文字「ｅ」に分類され、プロトタイプ２１６はタイプ文字「ｃ」に分類され、プロトタイプ２１３は「ｅｃ」リガチャーに分類される。
【００１７】
他の実施形態では、プロトタイプ・モジュール１０４が、ＯＣＲアプリケーション１１５によって提供されるのと同様のＯＣＲ処理を各プロトタイプに適用して、各プロトタイプのタイプ文字またはリガチャータイプ文字を識別、分類する。同一のタイプ文字に対して複数のクラスタが存在してよいことに留意されたい。例えば、タイプ・スタイル（例えば、太さ(boldness)）、ページの歪み(page skew)、コピー機でのスケーリングなど物理的属性やそれに関連した属性値に基づいて、タイプ文字「ａ」に３つの変形形態があることがある。したがって、「ａ」の各変形形態それぞれが、処理されてタイプ文字「ａ」の各変形形態に対応する３つの一意のプロトタイプを生成する一意のクラスタをもつ。
【００１８】
一実施形態では、リガチャーのタイプ文字が識別された後、プロトタイプ・モジュール１０４が部分的テンプレート・マッチングを使用して、リガチャーで識別された各タイプ文字（例えば、「ｅ」と「ｃ」）を類似のプロトタイプの集合につき合わせる。プロトタイプ・モジュール１０４は、部分的テンプレート・マッチングを使用するとき、リガチャーの各タイプ文字の幾何学的特徴を各プロトタイプの幾何学的特徴と、合致が見つかるまで比較する。例えば、幾何学的特徴は、文字のピクセル値、文字寸法値、リガチャー・ピクセル値、リガチャー寸法値など属性値をもつ文字属性、プロトタイプ属性、リガチャー属性などを含む。合致は、例えばオーバーレイ、あるいはその他のかかる比較アルゴリズムによって決定される。例えば、「ｅｃ」リガチャー（例えば、プロトタイプ２１３）は、左端とベースラインをもち、これらが共に部分的テンプレート・マッチングで、リガチャーの「ｅ」の上にプロトタイプ「ｅ」（例えば、プロトタイプ２１４）の最初の位置を決定する（例えば、プロトタイプとリガチャーの左端やベースラインを揃える）。しかし、これは各「ｅ」のピクセルのほとんどを揃えるに足るだけ正確な配置とならないことがある。例示的な一実施形態では、プロトタイプ・モジュール１０４が、例えば１または２ピクセル垂直および／または水平方向に最初の位置を調整することによって多数の配置を試みてよい。
【００１９】
他の実施形態では、プロトタイプ・モジュール１０４は、（左端とベースラインを用いる）初期配置を使用し、ピクセルをＸＯＲ（排他的ＯＲ）の対称差で検査する。高機能になると、多数の配置を試みるのではなく、初期配置を注意深く検査することで、その後の配置を試すのにどちらの方向にシフトすべきかが示唆される。例えば、プロトタイプ２１４が（リガチャーの）プロトタイプ２１３にオーバレイされる場合、プロトタイプ２１３に相対するプロトタイプ２１４の端が検査されて、正確なアラインメントを達成するにはプロトタイプ２１４の配置をどちらの方向に調整すべきか決定される。プロトタイプ２１４の垂直面の端がプロトタイプ２１３の垂直面の端と完全に揃う場合、このことは申し分のない水平アラインメントを示すことになる。一方、プロトタイプ２１４の垂直面の端がプロトタイプ２１３の垂直面の端より右（左）にある場合、このことはプロトタイプ２１４が左（右）に移動されなければならないことを示している。この一辺の端を検査することによって、カウンタＨ（水平インデックス）は申し分のない水平アラインメントを示すために増分され、カウンタｘＰはプロトタイプ２１４が（プロトタイプ２１３に対して）右に移動されなければならないことを示すために増分され、あるいはカウンタｘＮはプロトタイプ２１４が左に移動されなければならないことを示すために増分される。同様に、カウンタＶ（垂直インデックス）は申し分のない垂直アラインメントを示すために増分され、カウンタｙＰはプロトタイプ２１４が（プロトタイプ２１３に対して）上に移動されなければならないことを示すために増分され、カウンタｙＮはプロトタイプ２１４が下に移動されなければならないことを示すために増分される。次いで、これらのカウンタは、各ブロブの相対する端の他の部分の位置をさらに検査するに当たって調整されてもよい。
【００２０】
他の実施形態では、プロトタイプ２１４が、プロトタイプ２１３に、それぞれの左端とベースラインを用いてオーバレイされ、プロトタイプ２１４のある黒ピクセルがプロトタイプ２１３の白ピクセルの上にある場合、またプロトタイプ２１３の白ピクセルの隣８つを検査して右に２つ黒ピクセルがあるとわかった場合、このことは初期配置が１ピクセル右に移動されなければならないことを示唆していることになる。このようにして、上記で論じたように、カウンタｘＰ、ｘＮ、ｙＰ、ｙＮが計算され、それぞれ水平あるいは垂直方向に１ピクセル移動することを示唆する。また、ある種のピクセル検査は、それ以上の水平または垂直方向への移動が生じないことを示唆する。例えば、プロトタイプ２１４の１列内に０、１、１（オフ、オン、オンを意味する）の３つの連続するピクセルがある場合、そしてプロトタイプ２１３の対応するピクセルも同じである場合、水平カウンタＨ（Ｈインデックス）は増分されて「水平方向を固定する」位置になってよい。
【００２１】
一実施形態では、ＨおよびＶインデックスが以下のように計算される。カウンタＨが初期化されて０になる。プロトタイプ（例えば、プロトタイプ２１４）の水平移行ピクセルは、その左または右のどちらかのピクセルがオフになっている、オンのピクセルである。例えば、プロトタイプ２１４の水平移行ピクセルＰがプロトタイプ２１３の水平ピクセルＰ’の上にある場合、またＰの左のピクセルがＰ’の左のピクセルに一致する場合（例えば、どちらもオン、あるいはどちらもオフ）、なおかつＰの右のピクセルがＰ’の右のピクセルに一致する場合、Ｈは増分される。Ｖインデックスも同様に計算される。
【００２２】
したがって、水平安定度インデックスＨおよび垂直安定度インデックスＶが計算され、このことはｘＰ、ｘＮ、ｙＰ、ｙＮと共に、その後の配置を（あるのであれば）どちらの方向に試すべきかを示唆する。この処理を１、２度繰り返すことで、リガチャー・ブロブが、各プロトタイプに対応する断片にどのように切り分けられてよいかを示唆することができる。次いでプロトタイプの重心が、各断片の重心とアラインされて正確な位置決めが行われる。リガチャーとプロトタイプを比較するアルゴリズムが多数存在してよいことは理解できるであろう。どのアルゴリズムが使用されるかは、ハードウェアおよび／またはソフトウェアの機能などの要因に基づいた設計上の選択である。
【００２３】
上記で論じたように、単一のタイプ文字に対して（複数のクラスタから）複数のプロトタイプがあってよい。その結果、プロトタイプ・モジュール１０４は、各プロトタイプをリガチャーの対応する識別されたタイプ文字と比較する。例えば、（３つの一意のクラスタから）３つのプロトタイプが文字「ｅ」について生成された場合、プロトタイプ・モジュール１０４が、各「ｅ」プロトタイプをリガチャー内で識別された「ｅ」と比較する。次いで３つのプロトタイプのうちでもっとも合致する「ｅ」が選択されて、合成リガチャーの「ｅ」の部分が表される。同様にして、プロトタイプ・モジュール１０４は、部分テンプレート・マッチングを用いてリガチャーの残りのタイプ文字を他のプロトタイプとつき合わせる。
【００２４】
図２に戻ると、合成リガチャー２１８が、例示的な一実施形態に従って、テンプレート・マッチングを用いて合成リガチャーを生成したプロトタイプ・モジュール１０４の結果を示す。上記で論じたように、プロトタイプ・モジュール１０４が、プロトタイプ２１４とプロトタイプ２１６を生成し、それらをそれぞれ「ｅ」と「ｃ」に（例えば、ＯＣＲデータによって）分類する。ブロブ２１２は、プロトタイプ・モジュール１０４によって「ｅｃ」リガチャーと（例えば、ＯＣＲデータによって）識別され、上記で説明したように、テンプレート・マッチングを用いて、同じタイプ文字のプロトタイプをブロブ２１２のリガチャーの対応する文字とつき合わせる。プロトタイプ２１４（「ｅ」）とプロトタイプ２１６（「ｃ」）がもっとも合致していると決定した後、プロトタイプ・モジュール１０４は２つのプロトタイプを合成リガチャー２１８（「ｅｃ」）に組み合わせる。その結果は、スキャン文書１０８内の希な複数文字のリガチャーを基にしているにも関わらず、合成リガチャー２１８のより高品質なリガチャーとなる。
【００２５】
他の実施形態では、部分テンプレート・マッチングが、リガチャーの文字をスキャン文書１０８から抽出した元のブロブ（文字）とつき合わせるプロトタイプ・モジュール１０４を含んでいる。例えば、上記で説明したマッチング・アルゴリズムのいずれかを用いて、ブロブ・セット２０８（「ｃ」）のブロブをブロブ２１２の対応するリガチャーの文字（「ｃ」）とつき合わせる。プロトタイプ・モジュール１０４が、リガチャーの各文字について合致を決定すると、プロトタイプ・モジュール１０４は、クラスタ２０６から生成されたプロトタイプ２１６（「ｃ」）とプロトタイプ２１４（「ｅ」）を用いて、合成リガチャー２１８（「ｅｃ」）を生成する。
【００２６】
合成リガチャー（例えば、合成リガチャー２１８）は、２つ以上の文字を含むが、これは単一の合成フォント要素とも考えられる。他の実施形態では、部分テンプレート・マッチングの後、プロトタイプ・モジュール１０４が、合成リガチャーを２つの個々のつき合わせ用プロトタイプに分け、任意選択で、そのプロトタイプを、元のリガチャー（例えば、ブロブ２１２）の向きおよび／または幾何学的特徴に従ってページ上に設定する。
【００２７】
スキャン文書１０８を描出するプロトタイプや合成リガチャーがすべて生成された後、プロトタイプ・モジュール１０４は、対応する位置データ１１８を伴う合成フォント・ライブラリ１１６を生成する。位置データ１１８は、例えば、絶対ページ座標（例えば、プロトタイプの左下ピクセルといった参照ピクセルの座標）、あるいはプロトタイプの配置に対する前の文字やローカル・ベースラインからの相対座標を含むデータを含む。
【００２８】
一実施形態では、文書表示アプリケーション１２０は、ページ表示モジュール１２２を利用して、合成フォント・ライブラリ１１６のより高品質な文字を用いて、スキャン文書１０８の元の空間的向きとの知覚的な合致を失うことなく、新しい文書を生成する。新しい文書を生成するために、一実施形態によれば、ページ表示モジュール１２２が合成フォント・ライブラリ１１６や位置データ１１８にアクセスし、Ａｄｏｂｅ（登録商標）ＰｏｓｔＳｃｒｉｐｔ、Ｈｅｗｌｅｔｔ−Ｐａｃｋａｒｄ（登録商標）ＰＣＬ（Ｐｒｉｎｔｅｒ  Ｃｏｎｔｒｏｌ  Ｌａｎｇｕａｇｅ）、および  Ｍｉｃｒｏｓｏｆｔ（登録商標）ＸＭＬ  （Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）Ｐａｐｅｒ  Ｓｐｅｃｉｆｉｃａｔｉｏｎなどページ記述言語（ＰＤＬ）を用いて、新しい文書を割り付ける。次いで文書表示アプリケーション１２０は、ＰＤＬを解釈して新しい文書の視覚的表現をユーザ・ディスプレイ（図示せず）上に生成する。
【００２９】
図３Ａは、スキャン文書（例えば、スキャン文書１０８）の一部を表すスキャン画像から成る画像３００を示す。画像３００は、タイプ文字ブロブやリガチャー・ブロブの例を含む。ブロブ３０２はタイプ文字「ｅ」、ブロブ３０４はタイプ文字「ｔ」、ブロブ３０６は２つの接触する「ｆ」から成るリガチャー、ブロブ３０８は接触する「ｅ」と「ｃ」から成るリガチャーである。ブロブの境界を検査することによって、粗悪な画像品質が確認できる。例えば、ブロブ３０８（リガチャー）の境界３１０は、その全般的に粗い境界に加えて、タイプ文字「ｅ」がタイプ文字「ｃ」に接触しているのを示している。
【００３０】
上記で説明したように、例示的な一実施形態では、合成フォント生成器１０２が、各ブロブの幅（例えば、幅３１２）など位置データ１１８をキャプチャする。このデータは、スキャン文書１０８の外観をより正確に再生するために、ページ表示モジュール１２２によって使用される。
【００３１】
図３Ｂは、図３Ａで示したスキャン文書の一部の新しい画像３５０を示す。一実施形態では、文書表示アプリケーション１２０が、プロトタイプ・モジュール１０４によって生成された合成フォント・ライブラリ１１６と位置データ１１８に基づいて新しい画像を生成する。合成フォント３１３、３１４、３１６、３１８は、本明細書で説明するシステムと方法によって生成された、図３Ａに示したブロブに比して品質の向上した合成フォントを表す。例えば、合成フォント３１８の境界３２０は、画像３００の対応するブロブ３０８の境界３１０に対して向上した例を示す。一実施形態では、合成フォント・ライブラリ１１６を生成する際、プロトタイプ・モジュール１０４が、生成されたプロトタイプと合成リガチャーの元の寸法を維持する。例えば、ブロブ３０８の幅３１２が、対応する合成フォント３１８の幅３２２に維持される。また、例示的な一実施形態では、寸法をもつ合成フォントを伴うスキャン文書１０８の元のタイプ文字の位置が複製されて、スキャン文書１０８のそれと視覚的に合致する文書を生成するように、文書表示アプリケーション１２０が、位置データ１１８を用いて各合成フォント（例えば、合成フォント３１８）を新しい画像３５０内に置く。
【００３２】
図４は、例示的な一実施形態による、合成フォント・ライブラリ１１６とブロブ位置データ１１８の生成に基づいてスキャン文書を再構築する方法４００を示す流れ図である。以下で説明する各処理を詳細に述べた特定の例示的な実施形態が、図１、２、３を参照しながら上記で論じられてきたことに留意されたい。
【００３３】
オペレーション４０２に移ると、スキャン文書のページ画像が処理されてブロブを抽出する。ブロブは、オペレーション４０４で、類似性に応じてクラスタにグループ分けされる。オペレーション４０６でクラスタが処理されて、各クラスタに描出されたブロブの真の姿のより高品質な複製であるプロトタイプを生成する。一実施形態では、オペレーション４０８で、各プロトタイプ（例えば、文字やリガチャーの）が、どのタイプ文字（例えばタイプ文字「ｅ」）にそれぞれがマッチするかに応じて分類される。他の実施形態では、もっと早い段階のオペレーション（図示せず）で、プロトタイプが、類似のブロブから成る各クラスタになされた分類に従って分類される。
【００３４】
オペレーション４１０で、プロトタイプが希な複数文字のプロトタイプ（例えば、リガチャー「ｅｃ」）である場合、オペレーション４１２で合成リガチャーが生成される（例えば、図５を参照）。プロトタイプが、希な複数文字のプロトタイプでない場合は、オペレーション４１４で、オペレーション４１２で生成された合成リガチャーと共に、合成フォント・ライブラリ１１６が生成される。合成フォント・ライブラリ１１６は、分類された単一の文字のプロトタイプと合成リガチャーから成る。最後に、オペレーション４１６で、スキャン文書が合成フォント・ライブラリ１１６を用いて再構築されて、元のスキャン文書に知覚的に類似のより高品質な文書を生成する。
【００３５】
図５は、例示的な一実施形態による、合成リガチャーを生成する方法５００を示す流れ図である。以下で説明する各処理を詳細に述べた特定の例示的な実施形態が、図１、２、３を参照しながら上記で論じられてきたことに留意されたい。
【００３６】
オペレーション５０２に移ると、一実施形態では、単一文字のプロトタイプのシーケンスが、生成されたプロトタイプとそのそれぞれの分類（例えば、タイプ文字）に基づいて生成される。他の実施形態では、単一文字のプロトタイプ・シーケンスが、類似のブロブの生成された各クラスタの代表的なブロブに基づいて生成される。
【００３７】
オペレーション５０４で、単一文字のプロトタイプ・シーケンスの要素が、希な複数文字のプロトタイプの対応する部分と比較される。オペレーション５０６で、希な複数文字のプロトタイプのすべての部分が合致している場合、処理が完了し、オペレーション５１２で合成リガチャーが生成される。そうでない場合は、他の単一文字のプロトタイプ・シーケンスを用いて処理が繰り返される。単一文字のプロトタイプ・シーケンスがすべて試されると、オペレーション５０８で決定がなされて、もっとも近い合致を使用して（オペレーション５１０）、オペレーション５１２で合成リガチャーを生成する。
【００３８】
図６は、コンピュータ・システム６００の例示的な形態での機械の図を示しており、この機械において、本明細書で論じる１つまたは複数の手順をこの機械に実施させる命令セットが実行される。他の実施形態では、機械はスタンドアローン・デバイスとして動作するか、あるいは他の機械に接続（ネットワーク化）されてもよい。ネットワークに配置された場合、機械は、サーバ・クライアント・ネットワーク環境でサーバまたはクライアント機械の機能で動作するか、あるいはピア・トゥ・ピア（すなわち分散）ネットワーク環境でピア機械として動作する。機械はパーソナル・コンピュータ（ＰＣ）でも、タブレットＰＣでも、セット・トップ・ボックス（ＳＴＢ）でも、携帯情報端末（ＰＤＡ）でも、携帯電話でも、ウェブ家電でも、ネットワーク・ルータ、交換器、もしくはブリッジでも、あるいはその機械のとる行動を指定する（順次または他のやり方の）命令セットを実行できればどんな機械であってもよい。また、単一の機械だけが示されているが、用語「機械」は、個別で、または合わせて１つの（あるいは複数の）命令セットを実行して本明細書で論じる１つまたは複数の方法を実施する機械のいかなる集合をも含むと受け取られてよい。
【００３９】
例示的なコンピュータ・システム６００は、プロセッサ６０２（例えば、中央演算処理ユニット（ＣＰＵ）、グラフィック処理ユニット（ＧＰＵ）、あるいはその両方）、メインメモリ６０４、スタティックメモリ６０６を含み、これらはバス６０８を介してお互いに通信する。コンピュータ・システム６００はさらに、ビデオ表示ユニット６１０（例えば、液晶ディスプレイ（ＬＣＤ）またはシェード極線管（ＣＲＴ））を含む。コンピュータ・システム６００はまた、英数字入力デバイス６１２（例えば、キーボード）、ユーザ・インターフェース（ＵＩ）ナビゲーション・デバイス６１４（例えば、マウス）、ディスク・ドライブ・ユニット６１６、信号発生デバイス６１８（例えば、スピーカ）、ネットワーク・インターフェース・デバイス６２０を含む。
【００４０】
ディスク・ドライブ・ユニット６１６は機械可読媒体６２２を含み、そこに、本明細書で説明したあらゆる１つまたは複数の手順または関数を実施する、またはそれに利用される１つまたは複数の命令セットやデータ構造（例えば、ソフトウェア６２４）が格納される。ソフトウェア６２４はまた、コンピュータ・システム６００によってそれが実行されている間、完全に、または少なくとも部分的に、メインメモリ６０４および／またはプロセッサ６０２内に常駐してよく、メインメモリ６０４とプロセッサ６０２もまた機械可読媒体を構成する。
【００４１】
ソフトウェア６２４はさらに、ネットワーク６２６を介して、ネットワーク・インターフェース・デバイス６２０によって、数多くのよく知られた転送プロトコル（例えば、ＨＴＴＰ）の任意の１つを利用して、送信または受信される。
【００４２】
例示的な一実施形態で、機械可読媒体６２２が単一の媒体として示されているが、用語「機械可読媒体」は、１つまたは複数の命令セットを格納する単一の媒体または複数の媒体（例えば、集中型または分散型データベース、および／または関連するキャッシュおよびサーバ）を含むと受け取られなければならない。用語「機械可読媒体」はまた、機械によって実行される命令セットを格納、符号化、あるいは携行することが可能であり、本発明のあらゆる１つまたは複数の手順をも機械に実施させる、あるいはかかる命令セットによって利用される、またはそれに関連するデータ構造を格納、符号化、あるいは携行することが可能な任意の有形の媒体を含むと受け取られたい。したがって用語「機械可読媒体」は、ただしそれだけには限らないが、固体メモリ、光学式および磁気媒体、搬送波信号を含むと受け取られたい。
【００４３】
以上、諸実施形態が特定の例を参照しながら説明されてきたが、これらの実施形態に対して、本発明の広範な趣旨および範囲を逸脱することなく様々な修正および変更がなされてよいことは明らかであろう。したがって、本明細書および図面は、限定ではなく説明的な意味において見なされなければならない。
【図面の簡単な説明】
【００４４】
【図１】例示的な一実施形態における、スキャン文書のより高品質で知覚的に劣化のないバージョンを生成するために使用されるシステムを示す図である。
【図２】例示的な一実施形態によるブロブ、クラスタ、プロトタイプの例を示す図である。
【図３】Ａ：例示的な一実施形態による、スキャン文書の一部を描出したスキャン画像を示す図と、Ｂ：例示的な一実施形態に従って生成された、図３Ａに示すスキャン文書の一部の新しい画像の例を示す図である。
【図４】例示的な一実施形態による、合成フォント・ライブラリとブロブ位置データの生成に基づいてスキャン文書を再構築する方法を示す流れ図である。
【図５】例示的な一実施形態による、合成リガチャーを生成する方法を示す流れ図である。
【図６】当該機械に本明細書で論じられる１つまたは複数の手順を実施させる命令セットが実行されるコンピュータ・システムの例示的な形態での機械を示す図である。
【符号の説明】
【００４５】
１００  システム、１０２  合成フォント生成器、１０３  複製アルゴリズム、１０４  プロトタイプ・モジュール、１０５  プロトタイプ集合、１０６  クラスタ・モジュール、１０７  閾値、１０８  スキャン文書、１０９  マッチング・アルゴリズム、１１０  データ記憶デバイス、１１２  元の文書、１１４  スキャナ・アプリケーション、１１５  ＯＣＲアプリケーション、１１６  合成フォント・ライブラリ、１１８  位置データ、１２０  文書表示アプリケーション、１２２  ページ表示モジュール
【図１】
2007226803.tif 000003
【図２】
2007226803.tif 000004
【図３】
2007226803.tif 000005
【図４】
2007226803.tif 000006
【図５】
2007226803.tif 000007
【図６】
2007226803.tif 000008