(57)【特許請求の範囲】
【請求項１】
文字を含む画像を処理する方法であって、
文字セット内で、以下では第１文字と称する該文字セット内の或る文字に対して、最も高い形状類似度を有する１つ以上の文字を探索するステップであり、探索された該１つ以上の文字が前記第１文字の類似文字リストを形成する、ステップと、
前記文字セット内で、前記第１文字の類似文字リスト内の各文字に対して、最も高い形状類似度を有する１つ以上の文字を探索し、前記第１文字の類似文字リスト内の各文字の類似文字リストを形成するステップと、
前記類似文字リスト内で、相互に高い類似度を有する１つ以上の文字を、１つの文字クラスタとして選択するステップと、
を有する方法。
【請求項２】
前記文字セット内で前記第１文字に対して最も高い形状類似度を有する１つ以上の文字を探索するステップは、
前記文字セット内で、前記第１文字の複数の画像サンプルのうちの各画像サンプルに対して、最も高い形状類似度を有する１つ以上の文字を、該画像サンプルの候補文字セットとして探索することで、各々が前記複数の画像サンプルのうちの１つに対応する複数の候補文字セットを形成するステップと、
各文字が前記複数の候補文字セット内に現れる頻度を計算するステップと、
前記複数の候補文字セット内で、最も高い頻度に対応する１つ以上の文字を選択することで、前記第１文字の類似文字リストを形成するステップと
を有する、請求項１に記載の方法。
【請求項３】
前記文字セット内で各画像サンプルに対して最も高い形状類似度を有する１つ以上の文字を探索するステップは、
文字認識エンジンを用いて各画像サンプルを認識して、該画像サンプルの認識結果を取得するステップであり、該認識結果は、該画像サンプルに形状的に類似する１つ以上の文字と、該１つ以上の文字と該画像サンプルとの間での形状類似度の値とを含む、ステップと、
該認識結果内で、最も高い類似度の値に対応する１つ以上の文字を選択するステップと
を有する、請求項２に記載の方法。
【請求項４】
前記複数の候補文字セット内で最も高い頻度に対応する１つ以上の文字を選択するステップは、
前記複数の候補文字セット内で、第１の閾値より高い頻度に対応する１つ以上の文字を選択することで、前記第１文字の類似文字リストを形成するステップ
を有する、請求項２又は３に記載の方法。
【請求項５】
前記文字クラスタの如何なる２つの文字についても、その一方は他方の類似文字リストに含まれる、請求項１又は２に記載の方法。
【請求項６】
各文字が前記複数の候補文字セット内に現れる頻度を計算するステップの前に、
前記第１文字に対して第２の閾値より低い形状類似度を有する文字を、各候補文字セットから除去するステップ
を更に有する請求項２又は３に記載の方法。
【請求項７】
前記第１の閾値は、前記複数の候補文字セット内で２番目に高い頻度に対応する文字の頻度に比例する、請求項４に記載の方法。
【請求項８】
文字を含む画像を処理する装置であって、
文字セット内で、以下では第１文字と称する該文字セット内の或る文字に対して、最も高い形状類似度を有する１つ以上の文字を探索するように構成された初期選択装置であり、探索された該１つ以上の文字が前記第１文字の類似文字リストを形成し、当該初期選択装置は更に、前記文字セット内で、前記第１文字の類似文字リスト内の各文字に対して、最も高い形状類似度を有する１つ以上の文字を探索し、前記第１文字の類似文字リスト内の各文字の類似文字リストを形成するように構成されている、初期選択装置と、
前記類似文字リスト内で、相互に高い類似度を有する１つ以上の文字を、１つの文字クラスタとして選択するように構成されたクラスタ形成装置と、
を有する装置。
【請求項９】
前記初期選択装置は更に、前記文字セット内で前記第１文字に対して最も高い形状類似度を有する１つ以上の文字を探索することを、
前記文字セット内で、前記第１文字の複数の画像サンプルのうちの各画像サンプルに対して、最も高い形状類似度を有する１つ以上の文字を、該画像サンプルの候補文字セットとして探索することで、各々が前記複数の画像サンプルのうちの１つに対応する複数の候補文字セットを形成し、
各文字が前記複数の候補文字セット内に現れる頻度を計算し、且つ
前記複数の候補文字セット内で、最も高い頻度に対応する１つ以上の文字を選択することで、前記第１文字の類似文字リストを形成する、
ことによって行うように構成されている、請求項８に記載の装置。
【請求項１０】
前記初期選択装置は更に、前記文字セット内で各画像サンプルに対して最も高い形状類似度を有する１つ以上の文字を探索することを、
文字認識エンジンを用いて各画像サンプルを認識して、該画像サンプルの認識結果を取得し、ここで、該認識結果は、該画像サンプルに形状的に類似する１つ以上の文字と、該１つ以上の文字と該画像サンプルとの間での形状類似度の値とを含み、且つ
該認識結果内で、最も高い類似度の値に対応する１つ以上の文字を選択する、
ことによって行うように構成されている、請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、文字画像処理の分野に関し、より具体的には文字を含む画像を処理する方法及び装置に関する。
【背景技術】
【０００２】
文字セット内に、互いに似通った文字が多数存在することがある。例えば、漢字文字セットやハングル文字セットには、以下のような類似文字が存在する：
（外１）
0005691953.tif 000002
これら２つの文字群（１）及び（２）は各々、対応する文字セット内の文字クラス（部類）として使用され得る。文字セットは、粗い分類によって複数のクラスに分類されることができ、故に、或る文字を認識するとき、その文字が属するクラスが先ず決定され、その後、その文字がそのクラス内の各文字と比較され得る。これは、文字の認識時間を有意に短縮するので、文字認識の効率を向上させる。故に、このような粗分類は非常に重要である。しかしながら、誤った粗分類によって、文字認識に間違いが生じることがある。
【０００３】
粗分類に適用可能なクラスタリング（集団化）技術が数多く存在している。とりわけ、Ｋ平均（K-means）法は広く使用されている方法である。Ｋ平均法を記載したものとして、非特許文献１を参照することができる。Ｋ平均法においては、先ず、Ｋ個のクラス各々の当初の中心が決定され、各サンプルが、最小距離の原則に基づいて、Ｋ個のクラスのうちの１つに割り当てられ、そして、各クラス内の全てのサンプルの平均値が計算されて該クラスの新たな中心として設定される。これらのステップは、全てのサンプルがＫ個のクラスに分類されるまで反復される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】A.K.Jain、「Data  clustering：50  years  beyond  K-means」、Proceedings  of  the  19th  International  Conference  on  Pattern  Recognition（ICPR）、2008年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
この開示に係る一部の実施形態により、画像又はビデオ内のターゲット（目的物）を検出する方法及び装置が提供される。
【課題を解決するための手段】
【０００６】
ここでは、開示に係る幾つかの態様の基本的な理解を提供するため、この開示の概要を提示する。この概要は、この開示を網羅的に要約するものではなく、また、この開示の主要あるいは重要な要素を特定したり、この開示の範囲を定めたりすることを意図するものではない。この概要の唯一の目的は、後述の詳細な説明への前置きとして、一部の概念を簡略化して提示することである。
【０００７】
この開示に係る一実施形態によれば、或る文字（以下、明瞭さ及び簡潔さのために第１文字と称する）に対して最も高い形状類似度を有する１つ以上の文字が文字セット内で探索され、探索された１つ以上の文字が第１文字の類似文字リストを形成する。そして、第１文字の類似文字リスト内の各文字に対して最も高い形状類似度を有する１つ以上の文字が文字セット内で探索され、第１文字の類似文字リスト内の各文字に関する類似文字リストが形成される。その後、これらの類似文字リスト内で、相互に高い類似度を有する１つ以上の文字が１つの文字クラスタとして選択される。
【図面の簡単な説明】
【０００８】
この開示に係る実施形態の上述及びその他の目的、特徴及び利点は、以下の詳細な説明を図面とともに参照することによって、より十分に理解され得る。図面全体を通して、同一あるいは同様の構成要素は、同一あるいは類似の参照符号によって表される。なお、図面に示される構成要素は、簡略化して描かれたものであり、縮尺通りに描かれたものではない。
【図１】この開示に係る一実施形態に従った、文字を含む画像を処理する方法を概略的に示すフローチャートである。
【図２】特定の一実施形態に従った、或る文字セット内の或る文字に関して類似文字リストを探索する方法を概略的に示すフローチャートである。
【図３】特定の他の一実施形態に従った、或る文字セット内の或る文字に関して類似文字リストを探索する方法を概略的に示すフローチャートである。
【図４】特定の一実施形態に従った、或る文字セット内の或る文字の画像サンプルに関して候補文字セットを探索する方法を概略的に示すフローチャートである。
【図５】特定の他の一実施形態に従った、或る文字セット内の或る文字の画像サンプルに関して候補文字セットを探索する方法を概略的に示すフローチャートである。
【図６】一例に従って作成された文字クラスタを例示する図である。
【図７】この開示に係る一実施形態に従った、文字を含む画像を処理する装置を概略的に示すブロック図である。
【図８】この開示の実施形態又は実施例に従った方法を実現するためのコンピュータの構造を概略的に示すブロック図である。
【発明を実施するための形態】
【０００９】
以下、この開示に係る実施形態を図面に関連付けて説明する。なお、１つの図に示す、あるいは１つの実施形態にて開示する要素及び／又は特徴は、１つ以上のその他の図又は実施形態に示す要素及び／又は特徴と組み合わされ得る。また、明瞭さ及び簡潔さのため、この開示に係る解決策に密接に関連する装置構造及び／又は処理工程のみを図に示すこととし、この開示にあまり関連しない、あるいは技術的に周知の、その他の細部は省略することとする。
【００１０】
言及しておくに、一部のクラスタリング方法（例えば、Ｋ平均クラスタリング法）は、文字セットが分類されることになるクラスタの数（例えば、Ｋの値）を予め定める必要があるが、この数（例えば、Ｋ）を決定する基準を提供していない。また、クラスタリング方法（例えば、Ｋ平均クラスタリング法）で用いられる距離指標は、一般的に、それに続く文字の認識及び処理で使用される類似指標と関係のあるものになっていない。例えば、一部のクラスタリング方法では、各要素に最近接の隣接物を見出すために２つの要素の間のユークリッド距離が用いられるが、続く文字認識又は分類（例えば、修正２次識別関数（quadratic  discriminant  function；ＭＱＤＦ）又はサポートベクターマシン（support  vector  machine；ＳＶＭ）を用いることによる）では一般的に、距離を計算するために複数のクラスの影響が考慮される。従って、これらのクラスタリング方法を用いた粗分類によって得られる各文字クラスに含まれる文字群は、続く文字認識又は分類では、互いに似ていないものとして検討されることがある。
【００１１】
この開示に係る幾つかの実施形態は、上述の欠点のうちの１つ以上を解決するように、文字を含む画像を処理する方法及び装置を提供する。
【００１２】
図１は、この開示に係る一実施形態に従った文字を含む画像を処理する方法を概略的に示すフローチャートであり、この方法により、或る文字セット内の文字群は複数の小型の（コンパクトな）文字クラスタに分類され得る。
【００１３】
図１に示す方法は、ステップ１０３、１０７及び１１１を含み得る。
【００１４】
ステップ１０３にて、文字一式（すなわち、文字セット）内の或る文字（以下、第１文字と称する）に関して、第１文字に対して最も高い形状類似度を有する１つ以上の文字が探索される。斯くして探索された該１つ以上の文字は、第１文字の類似文字リストを形成する。
【００１５】
この開示において、或る１つの文字又はその画像サンプルの他の１つの文字に対する所謂“類似度”は、これら２つの文字間での概観の類似性を意味する。例えば、上述の文字群（１）又は（２）内の複数の文字は形状において相互に類似している。類似度は、如何なる適切な指標によって表されてもよい。例えば、２つの文字間の類似度は、これら２つの文字間の距離（例えば、ユークリッド距離、マハラノビス距離、又はこれらに類するもの）によって表され得る。距離が小さいほど類似度は高く、距離が大きいほど類似度は低い。
【００１６】
第１文字に対して高い形状類似度を有する文字は、如何なる適切な手法を用いて探索されてもよい。例えば、第１文字の１つの画像サンプルを用いて、該画像サンプルに対して高い形状類似度を有する文字セット内の文字が探索されて、第１文字の類似文字として使用され、それにより、第１文字の類似文字リストが形成される。他の一例においては、第１文字の類似文字を探索するために、第１文字の複数の画像サンプルを用いてもよい（この手法に係る特定の例について、図２又は図３を参照して後述する）。
【００１７】
或る１つの画像サンプルに対して高い形状類似度を有する文字は、如何なる適切な手法を用いて探索されてもよい（この手法に係る特定の例については、図４又は図５を参照して後述する）。
【００１８】
一例として、類似文字リスト内の文字の数は、予め定められる必要はない。例えば、類似度の閾値が設定され、この閾値より高い類似度を第１文字に対して有する各文字が、第１文字の類似文字リストの１つの要素として用いられ得る。他の一例として、類似文字リスト内の文字の数（例えば、Ｎ≧１としてＮで表す）は、実際の用途シナリオに従って予め定められてもよく、第１文字の類似文字リストを形成するように、第１文字に対して最も高い類似度を有するＮ個の文字が選択される。
【００１９】
第１文字の類似文字リストを取得した後、ステップ１０７にて、同じ処理が該類似文字リスト内の各文字に対して実行される。すなわち、ステップ１０７では、第１文字の類似文字リスト内の各文字に対して最も高い形状類似度を有する１つ以上の文字が、文字セット内で探索され、第１文字の類似文字リスト内の各文字に関する類似文字リストを形成する。第１文字の類似文字リストは１つ以上の文字を含むので、該リスト内の１つの文字に各々が対応する１つ以上の類似文字リストが得られる。
【００２０】
そして、ステップ１１１にて、これらの類似文字リスト内の文字が更に選択される。すなわち、相互間で高い類似度を有する１つ以上の文字がこれらの類似文字リスト内で選択され、選択された文字群が文字セットの１つの文字クラスタとして使用される。
【００２１】
これらの類似文字リスト内の文字は、文字クラスタ内の文字群のうちの何れの２つに関しても相互間に形状類似度を有することを保証することが可能な如何なる好適な手法を用いて更に選択されてもよい。
【００２２】
一例として、これらの類似文字リスト内の相互に或る閾値以上の類似度を有する文字群が選択され得る。すなわち、形成される文字クラスタ内の文字群のうちの如何なる２つの間の類似度も閾値以上である（この閾値は、実際の用途シナリオに従って決定されることができ、如何なる特定の値にも限定されない）。
【００２３】
他の一例として、これらの類似文字リスト内で相互に形状類似性を有する文字を見出すために、最大クリークに基づくグラフモデルが用いられてもよい。最大クリークに基づくグラフモデルを用いることによって文字クラスタを形成する特定の一例については、図６を参照して後述する。
【００２４】
好適な一例として、文字クラスタ内の如何なる２つの文字に関しても、その一方は他方の類似文字リストに含まれる。
【００２５】
上述の方法により、文字セットは複数の文字クラスタに分類され得る。
【００２６】
図１に示した方法においては、第１文字の類似文字リストを形成した後、第１文字の類似文字リスト内の各文字の類似文字リストが更に探索され、これらの類似文字リスト内の文字が、或る文字クラスタを形成すべく更に選択されている。この方法を用いると、該文字クラスタ内の如何なる２つの文字も相互に高い形状類似度を有することが保証され、それにより、小型であることとクラスタリングの精度とが確保され得る。また、この方法においては、文字クラスタの数が事前設定される必要はなく、すなわち、どれだけの数のクラスタに文字セットが分類されるかを予め定める必要がない。斯くして形成された文字クラスタを用いることにより、続く文字認識及び処理の正確さ及び効率が向上され得る。
【００２７】
最大クリークに基づくグラフモデルを用いる例においては、各文字クラスタ内の文字の数が最大になることを保証することができ、それにより、文字クラスタの数が削減され、ひいては、後続処理の効率化が最大化され得る。
【００２８】
図２は、或る文字セット内の或る文字（例えば、第１文字）の類似文字リストを探索する方法の特定の一実施形態を示している。図２に示す特定の実施形態において、第１文字の類似文字リストを探索する方法は、ステップ１０３−１、１０３−２及び１０３−３を含み得る。ステップ１０３−１にて、第１文字の複数の画像サンプルの各々について、その画像サンプルに対して最も高い形状類似度を有する１つ以上の文字が文字セット内で探索され、探索された１つ以上の文字がその画像サンプルの候補文字セットを形成する。画像サンプルの候補文字セットは如何なる適切な手法を用いて探索されてもよい。そのような手法の幾つかの例については、図４及び図５を参照して後述する。第１文字の上記複数の画像サンプルのうちの１つに各々が対応する複数の候補文字セットが取得され得る。その後、ステップ１０３−２にて、各文字について、これらの候補文字セットに現れる頻度が計算される。そして、ステップ１０３−３にて、最も高い頻度に対応する１つ以上の文字が第１文字の類似文字として選択され、これらの類似文字が第１文字の類似文字リストを形成する。
【００２９】
図３は、或る文字セット内の或る文字（例えば、第１文字）の類似文字リストを探索する特定の他の一実施形態を示している。図３に示す特定の実施形態は、図２の実施形態と似通っている。違いは、図３の方法が更に候補文字セット内の文字を初期に選択するステップを含んでいることにある。具体的には、図３に示す第１文字の類似文字リストを探索する方法は、ステップ３０３−１、３０３−４、３０３−２及び３０３−３を含み得る。ステップ３０３−１はステップ１０３−１と同様であり、その説明はここでは繰り返さない。ステップ３０３−４にて、第１文字に対する形状類似度が閾値より低い１つ以上の文字が、各候補文字セットから除去される。換言すれば、候補文字セット内の各文字の第１文字に対する形状類似度が閾値より低いかが判定され、そうであれば、その文字は除去され、そうでなければ、その文字は留保される。認識され得るように、この閾値は実際の用途シナリオに従って決定されることができ、如何なる特定の値にも限定されるべきではない。そして、ステップ３０３−２にて、残った文字の各々について、候補文字セットに現れる頻度が計算される。最後にステップ３０３−３にて、最も高い頻度に対応する１つ以上の文字が選択されて、第１文字の類似文字リストを形成する。図２に示した方法と比較して図３の方法の計算量は低減され、それによって処理速度が加速される。
【００３０】
図４は、文字セット内で、或る画像サンプル（例えば、第１文字の画像サンプル）に対して高い形状類似度を有する文字を探索することの一例を示している。図４に示す方法は、ステップ１０３−１１及び１０３−１２を含み得る。ステップ１０３−１１にて、該画像サンプルと文字セット内の各文字との間の距離が計算される。この距離は、如何なる特定の例にも限定されるべきでないが例えば「Modified  Quadratic  Discriminant  Functions  and  the  Application  to  Chinese  Character  Recognition」（IEEE  Transactions  on  Pattern  Analysis  and  Machine  Intelligence、第PAMI-9巻、第1号、1987年）に記載された手法又はそれに類するものなど、如何なる適切な手法によって計算されてもよい。画像サンプルと文字との間の距離が小さいほど、それらは相互に一層大きく類似している。ステップ１０３−１２にて、計算された距離の値に基づいて、より小さい距離の値に対応する１つ以上の文字が、その画像サンプルに対して最も高い形状類似度を有する文字として選択される。選択された該１つ以上の文字が、該画像サンプルの候補文字セットを構成する。同一の文字について複数の画像サンプルが存在する場合、各々がそれら画像サンプルのうちの１つに対応する複数の候補文字セットが、図４の方法を用いて探索され得る。
【００３１】
一例として、或る文字と或る画像サンプルとの間の形状類似度は、続く文字認識にて使用されるのと同じ指標によって計算されることができ、その結果、斯くして形成された文字クラスタは、続く文字認識処理に一層良好に適合し、それにより文字認識及び処理の正確さが向上され得る。
【００３２】
図５は、文字セット内で、或る画像サンプル（例えば、第１文字の画像サンプル）に対して高い形状類似度を有する文字を探索することの他の一例を示している。図５に示す方法は、ステップ１０３−１５及び１０３−１６を含み得る。
【００３３】
ステップ１０３−１５にて、画像サンプルを認識するために文字認識エンジンが使用され、該画像サンプルの認識結果が得られる。この認識結果は概して、該画像サンプルに対して最も類似するとして上記エンジンによって認識された1つ以上の文字と、これらの文字の各々と該画像サンプルとの間の類似度の値とを含む。この例において、認識は如何なる適切な認識エンジンによって実行されてもよく、如何なる特定のエンジンにも限定されるべきではない。好適な一例として、続く文字認識の認識エンジンと同じ認識エンジンが使用され得る。同一の認識エンジンは同じ類似度指標を使用するので、こうすることは、続く文字認識及び処理の正確さ及び効率を更に高め得る。
【００３４】
ステップ１０３−１６にて、認識結果に基づいて、最大の類似度の値に対応する１つ以上の文字が、認識エンジンによって取得された文字群の中から選択されて、該画像サンプルの候補文字セットを形成する。同一の文字について複数の画像サンプルが存在する場合、各々がそれら画像サンプルのうちの１つに対応する複数の候補文字セットが、図５の方法を用いて探索され得る。
【００３５】
以下では、ハングル文字セットを複数の文字クラスタに分類する特定の一例を説明する。
【００３６】
簡潔さのため、一例として、文字：
（外２）
0005691953.tif 000003
（図６では、この文字を“ｃｈ１”で表す）を含む１つの文字クラスタを形成する処理のみを説明する。この例において、この文字の複数の画像サンプルが用いられる。
【００３７】
最初に、図５を参照して説明した方法を用いて、各画像サンプルが光学式文字認識（ＯＣＲ）エンジンによって認識され得る。
【００３８】
ＯＣＲエンジンによって取得された各画像サンプルの認識結果は、Ｎ個の候補文字と、これらの文字と該画像サンプルとの間の形状類似度の値とを含み得る。
【００３９】
この例においては、Ｎ＝１０とし、且つ、各候補文字と画像サンプルとの間の形状類似度を表すために、ＯＣＲエンジンによって取得された認識距離が使用されるとする。或る候補文字と画像サンプルとの間の認識距離が長いほど、それらの間の類似度の値は低く、また、認識距離が短いほど、それらの間の類似度の値は高い。
【００４０】
表１は、上記文字：
（外３）
0005691953.tif 000004
の３つの画像サンプルについて、ＯＣＲエンジンによって取得された認識結果を示している。
【００４１】
【表１】
0005691953.tif 000005
この表に示す３つの候補文字セットを取得した後、これらの中の文字群が更に選択される。先ず、各サンプルに対して一層低い形状類似度を有する１つ以上の文字が、該サンプルの候補文字セットから除去され得る。例えば、各候補文字に対応する認識距離が閾値ＴＨより大きいかについて判定が為され、そうであれば、その文字は除去される。この例において、閾値ＴＨは１０００に設定されている。しかしながら、認識されるべきことには、閾値ＴＨは実際の用途シナリオに従って決定され得るものであり、この開示は、この例で採用したこの特定の値に限定されるべきでない。
【００４２】
そして、残った候補文字の各々について、これら３つの候補文字セットに現れる頻度が計算され、頻度閾値（Ｔ＿ｆｒｅｑで表す）より高い頻度に対応する文字が選択されて、上記文字：
（外４）
0005691953.tif 000006
の類似文字リストを形成する。閾値Ｔ＿ｆｒｅｑは実際の用途シナリオに従って決定され得るものであり、如何なる特定の値にも限定されるべきでない。好適な一例として、Ｔ＿ｆｒｅｑは、２番目に高い頻度に対応する文字の頻度に比例するように設定され得る（最高頻度に対応する文字の頻度が使用されないのは、最高頻度を有する文字は通常、第１文字（すなわち、この例において
（外５）
0005691953.tif 000007
）自体であるためである）。例えば、表１において２番目に高い頻度に対応する文字は
（外６）
0005691953.tif 000008
であり、Ｔ＿ｆｒｅｑは表１内にこの文字が現れる頻度の半分として設定され得る。
【００４３】
上述の処理の後、
（外７）
0005691953.tif 000009
を含む文字ｃｈ１の類似文字リストが取得される。
【００４４】
このリスト（３）内の各類似文字に対して同じ処理が実行され、リスト（３）内の全ての類似文字の類似文字リスト：
（外８）
0005691953.tif 000010
が取得される。
【００４５】
これらのリストの長さ（すなわち、各リスト内の文字の数）は互いに等しいわけではない。１つの類似文字リストに含まれる或る文字が他の類似文字リストにおいては排除されていることもある。例えば、
（外９）
0005691953.tif 000011
は、
（外１０）
0005691953.tif 000012
と類似するが、
（外１１）
0005691953.tif 000013
とは類似しない。
【００４６】
その後、最大クリークに基づくグラフモデルを用いることにより、１つの文字クラスタが構成され得る。換言すれば、構成すべき文字クラスタ内の文字群のうちの如何なる２つについても、相互に十分に類似することが要求されるので、そのような文字クラスタを構成することは、上記リストの中で最大クリークを探索することとして単純化され得る。図６は、文字：
（外１２）
0005691953.tif 000014
に関するリスト（３）−（７）に基づいて構築されたグラフモデルを示している。図６のグラフにおいて、各頂点（ｃｈ１−ｃｈ５）は類似文字リスト（３）内の１つの文字に対応している。２つの頂点がエッジ（線分）によって接続されている場合、これら２つの頂点に対応する文字は相互に類似しており、すなわち、これら２つの文字の何れを一方としても、該一方はこれら２つの文字のうちの他方の類似文字リストに含まれている。例えば、ｃｈ２はｃｈ５の類似文字リスト（７）内に存在し、且つｃｈ５はｃｈ２の類似文字リスト（４）内に存在し、故に、対応する２つの頂点は接続されている。図６においては、ｃｈ１、ｃｈ２及びｃｈ５が相互に接続されており、すなわち、これら３つの文字のうちの何れの２つをとり、そのうちの何れの一方をとっても、該一方は該２つのうちの他方の類似文字リストに含まれている。従って、これら３つの文字は１つの文字クラスタを構成することができる。図６のグラフモデルにおいて、相互に類似する頂点のみが接続されているので、２つの文字間の類似度は非対称な指標を用いてもよい。
【００４７】
上述の最大クリークに基づくクラスタ形成方法においては、類似文字リストの内部構造が効率的に利用され、斯くして形成されたクラスタはコンパクトである。この方法を用いることにより、クラスタの数を予め定めることは不要である。この方法の計算処理は単純であり、それにより、処理の効率及び速度が更に向上される。
【００４８】
表２は、図６を参照して説明した方法を適用することなく漢字セット及びハングル文字セットを分類することによって得られる文字クラスの数と、図６の方法を用いて同じセットを分類することによって得られる文字クラスタの数とを示している。
【００４９】
【表２】
0005691953.tif 000015
見て取れるように、図６の方法を用いることによって得られる文字クラスタの数は５３１５から３２７８に削減される。文字クラスタを用いることにより、文字セット内の文字クラスの数が削減され、それにより、続く文字認識処理の速度及び効率が向上される。
【００５０】
表１及びリスト（３）−（７）においては、明瞭化のために、各文字にＵＴＦ−８コードが割り当てられている。認識されるように、実際の用途では、これらの文字はその他の種類のコードによって表されてもよく、この例は本開示をそれに限定するものとして解されるべきでない。
【００５１】
図７は、この開示に係る一実施形態に従った文字を含む画像を処理する装置７００の構成を示す簡略化したブロック図である。装置７００は、上述の実施形態又は例に係る方法を用いて、文字一式（すなわち、文字セット）を複数の文字クラスタに分類し得る。
【００５２】
図７に示す装置７００は、初期選択装置７０２及びクラスタ形成装置７０４を含み得る。
【００５３】
初期選択装置７０２は、或る文字セット内で、該文字セット内の或る文字（第１文字と称する）に対して最も高い形状類似度を有する１つ以上の文字を探索するように構成され、探索された該１つ以上の文字が第１文字の類似文字リストを構成する。そして、初期選択装置７０２は、第１文字の類似文字リスト内の各文字に対して同じ処理を実行する。換言すれば、初期選択装置７０２は更に、該文字セット内で、第１文字の類似文字リスト内の各文字に対して最も高い形状類似度を有する１つ以上の文字を、第１文字の類似文字リスト内の各文字の類似文字リストとして探索するように構成される。
【００５４】
初期選択装置７０２は、或る特定の文字に対して高い形状類似度を有する文字を探索する如何なる適切な手法を用いてもよい。例えば、初期選択装置７０２は、該特定文字の１つの画像サンプルを用い、文字セット内で、該特定文字に対して高い形状類似度を有する文字として、該画像サンプルに対して高い形状類似度を有する文字を探索することで、該特定文字の類似文字リストを形成し得る。他の一例では、初期選択装置７０２は、或る文字の複数の画像サンプルを用いて、該文字の類似文字リストを探索してもよい。特定の例として、初期選択装置７０２は、ここでは説明を繰り返さないが、図２又は図３を参照して説明した方法を用いてもよい。
【００５５】
図２又は３の方法を用いて文字の類似文字リストを探索するとき、初期選択装置７０２は、画像サンプルに対して高い形状類似度を有する文字を探索する如何なる適切な手法を用いてもよい。例えば、初期選択装置７０２は、ここでは説明を繰り返さないが、図４又は図５を参照して説明した手法を使用し得る。
【００５６】
一例として、類似文字リスト内の文字の数は予め定められるのではなく、例えば、或る特定の類似度閾値が設定されて、或る文字（例えば、第１文字）に対して閾値より高い形状類似度を有する文字が、第１文字の類似文字リストの要素として選択され得る。他の一例として、或る文字の類似文字リスト内の文字の数（例えば、Ｎ≧１としてＮで表す）は、実際の用途シナリオに従って予め定められ、第１文字の類似文字リストを形成するように、第１文字に対して最も高い形状類似度を有するＮ個の文字が選択されてもよい。
【００５７】
クラスタ形成装置７０４は、初期選択装置７０２によって出力された複数の類似文字リスト内で、相互に高い類似度を有する１つ以上の文字を１つの文字クラスタとして選択するように構成される。
【００５８】
クラスタ形成装置７０４は、これらの類似文字リスト内で選択を行うために、文字クラスタ内の選択文字のうちの如何なる２つも相互に高い形状類似度を有する限り、如何なる適切な手法を用いてもよい。
【００５９】
一例として、クラスタ形成装置７０４は、これらの類似文字リスト内で、相互に或る特定の閾値以上の類似度を有する文字群、すなわち、文字クラスタ内の文字群のうちの何れの２つの間の類似度も該閾値以上である文字群を選択し得る（この閾値は、実際の用途シナリオに従って決定され得るものであり、如何なる特定の値にも限定されない）。
【００６０】
他の一例として、クラスタ形成装置７０４は、上述の最大クリークに基づくグラフモデル（例えば、図６を参照して説明した手法）を用いて、これらの類似文字リスト内で、相互に高い類似度を有する文字群を選択してもよい。この方法の説明はここでは繰り返さない。
【００６１】
好適な一例として、文字クラスタ内の何れの２つをとっても、その一方は他方の類似文字リストに含まれ得る。
【００６２】
この装置７００を用いて、文字セットは複数の文字クラスタに分類され得る。文字クラスタ内の如何なる２つの文字もそれらの間に高い相似性を有し、それにより、クラスタリングの精度が確保され且つ向上される。また、これらの実施形態においては、文字クラスタの数を予め決定する必要がない。すなわち、どれだけの数のクラスタに文字セットが分類されるかを予め定める必要がない。斯くして形成された文字クラスタを用いることにより、文字の認識及び処理の正確さ及び効率が向上され得る。
【００６３】
理解されるべきことには、上述の実施形態及び例は例示的なものであって、網羅的なものではない。この開示は、上述の特定の実施形態又は例に限定されるものとして見なされるべきでない。
【００６４】
上述の実施形態又は例において、一部の表現（例えば、“第１文字”、“第１の閾値”及び“第２の閾値”）は、“第１”若しくは“第２”又はこれらに類する用語を含んでいる。理解されるべきことには、このような表現は、単に複数の用語を相互に文字通り区別するために使用されているのであって、それらの順序への限定又は何らかのその他の限定として見なされるべきでない。
【００６５】
上述の装置及び方法におけるユニット又はステップは、詳細はここでは省略するが技術的に周知の手法又は手段を用いることにより、ソフトウェア、ハードウェア、ファームウェア、又はこれらの何らかの組み合わせで構成されることができる。
【００６６】
一例として、ソフトウェア又はファームウェアを用いる場合、上述の方法又は装置を実現するためのソフトウェアを構成するプログラムが、記憶媒体又はネットワークから、専用のハードウェア構成を有するコンピュータ（例えば、図８に示すような汎用コンピュータ）にインストールされ得る。コンピュータは、様々なプログラムをインストールされるとき、様々な機能を実行することができる。
【００６７】
図８において、中央処理装置（ＣＰＵ）８０１は、読み出し専用メモリ（ＲＯＭ）８０２に格納されたプログラム、又は記憶装置８０８からランダムアクセスメモリ（ＲＡＭ）８０３にロードされたプログラムに従って様々な種類の処理を実行する。ＲＡＭ８０３はまた、必要に応じて、ＣＰＵ８０１が様々な種類の処理を実行するのに必要なデータを格納する。ＣＰＵ８０１、ＲＯＭ８０２及びＲＡＭ８０３は、バス８０４を介して互いに接続されている。バス８０４は入力／出力インタフェース８０５にも接続している。
【００６８】
入力／出力インタフェース８０５は、キーボードやマウスなどからなる入力装置８０６、陰極線管（ＣＲＴ）若しくは液晶のディスプレイやスピーカなどからなる出力装置８０７、ハードディスクを含む記憶装置８０８、及びモデムやターミナルアダプタなどからなる通信装置８０９に接続している。通信装置８０９は通信処理を実行する。必要に応じて、ドライブ８１０が入力／出力インタフェース８０５に接続される。ドライブ８１０には、例えば、本発明に係るプログラムを格納した記録媒体としてリムーバブルメディア（取り外し可能媒体）８１１がロードされる。必要に応じて、プログラムはリムーバブルメディア８１１から読み出されて記憶ユニット８０８にインストールされる。
【００６９】
上述の一連の処理を実現するためにソフトウェアを用いる場合、該ソフトウェアを構成するプログラムが、例えばインターネットなどのネットワーク又は例えばリムーバブルメディア８１１などの記憶媒体からインストールされ得る。
【００７０】
当業者に理解されるように、記憶媒体は、例えば磁気ディスク（フロッピー（登録商標）ディスクを含む）、光ディスク（コンパクトディスクＲＯＭ（ＣＤ−ＲＯＭ）及びデジタル多用途ディスク（ＤＶＤ）を含む）、光磁気ディスク（ＭＤ（ミニディスク）（登録商標）を含む）、又は半導体メモリなどの、プログラムが記録され且つプログラムをユーザに届けるために配布されるリムーバブルメディア８１１に限定されず、プログラムが記録され且つ装置の本体に前もって搭載されてユーザに届けられる装置の本体又はＲＯＭ８０２若しくは記憶装置８０８に含まれるハードディスクであってもよい。
【００７１】
この開示は更に、実行されたときに実施形態に従った方法を実行することが可能な機械読み取り可能な命令コードを有するプログラムを提供する。
【００７２】
従って、機械読み取り可能命令コードを有するプログラムを担持する記憶媒体も、この開示に含まれる。記憶媒体は、以下に限られないが、フロッピー（登録商標）ディスク、光ディスク、光磁気ディスク、カード式ストレージ、又はメモリスティックなどを含む。
【００７３】
以上の実施形態の説明において、１つの実施形態に関連して説明あるいは示された特徴は、同様あるいは同一のようにして１つ以上のその他の実施形態で使用されてもよいし、その他の実施形態の特徴と組み合わされてもよいし、あるいはその他の実施形態の特徴を置き換えるように使用されてもよい。
【００７４】
ここでは、用語“有する”、“含む”、“持つ”及びこれらの如何なる変形も、非排他的な包含に及ぶものである。故に、要素を列挙する処理、方法、品目又は装置は、必ずしもそれらの要素に限定されず、明示的に列挙されていない要素や、それらの処理、方法、品目又は装置に本来備わる要素などのその他の要素を含み得る。
【００７５】
さらに、この開示において、方法は、ここで説明した順序に従った時系列で実行されるプロセスに限定されるものではなく、その他の時系列で実行されたり、並列あるいは別個に実行されたりすることも可能である。すなわち、上述の実行順序は、方法をその順序に限定するものとして見なされるべきではない。
【００７６】
幾つかの実施形態及び例を説明したが、これらの実施形態及び例は、この開示を単に例示するものであり、この開示を限定するものではない。この開示の範囲を逸脱することなく、様々は変形、改良及び代替が当業者によって行われることが可能である。そのような変形、改良及び代替は、この開示の保護範囲が及ぶものとして見なされるべきである。
【００７７】
以上の説明から分かるように、この開示に係る実施形態は少なくとも以下のソリューションを提供するものである。
（付記１）
文字を含む画像を処理する方法であって、
文字セット内で、以下では第１文字と称する該文字セット内の或る文字に対して、最も高い形状類似度を有する１つ以上の文字を探索するステップであり、探索された該１つ以上の文字が前記第１文字の類似文字リストを形成する、ステップと、
前記文字セット内で、前記第１文字の類似文字リスト内の各文字に対して、最も高い形状類似度を有する１つ以上の文字を探索し、前記第１文字の類似文字リスト内の各文字の類似文字リストを形成するステップと、
前記類似文字リスト内で、相互に高い類似度を有する１つ以上の文字を、１つの文字クラスタとして選択するステップと、
を有する方法。
（付記２）
前記文字セット内で前記第１文字に対して最も高い形状類似度を有する１つ以上の文字を探索するステップは、
前記文字セット内で、前記第１文字の複数の画像サンプルのうちの各画像サンプルに対して、最も高い形状類似度を有する１つ以上の文字を、該画像サンプルの候補文字セットとして探索することで、各々が前記複数の画像サンプルのうちの１つに対応する複数の候補文字セットを形成するステップと、
各文字が前記複数の候補文字セット内に現れる頻度を計算するステップと、
前記複数の候補文字セット内で、最も高い頻度に対応する１つ以上の文字を選択することで、前記第１文字の類似文字リストを形成するステップと
を有する、付記１に記載の方法。
（付記３）
前記文字セット内で各画像サンプルに対して最も高い形状類似度を有する１つ以上の文字を探索するステップは、
文字認識エンジンを用いて各画像サンプルを認識して、該画像サンプルの認識結果を取得するステップであり、該認識結果は、該画像サンプルに形状的に類似する１つ以上の文字と、該１つ以上の文字と該画像サンプルとの間での形状類似度の値とを含む、ステップと、
該認識結果内で、最も高い類似度の値に対応する１つ以上の文字を選択するステップと
を有する、付記２に記載の方法。
（付記４）
前記複数の候補文字セット内で最も高い頻度に対応する１つ以上の文字を選択するステップは、
前記複数の候補文字セット内で、第１の閾値より高い頻度に対応する１つ以上の文字を選択することで、前記第１文字の類似文字リストを形成するステップ
を有する、付記２又は３に記載の方法。
（付記５）
前記文字クラスタの如何なる２つの文字についても、その一方は他方の類似文字リストに含まれる、付記１又は２に記載の方法。
（付記６）
各文字が前記複数の候補文字セット内に現れる頻度を計算するステップの前に、
前記第１文字に対して第２の閾値より低い形状類似度を有する文字を、各候補文字セットから除去するステップ
を更に有する付記２又は３に記載の方法。
（付記７）
前記第１の閾値は、前記複数の候補文字セット内で２番目に高い頻度に対応する文字の頻度に比例する、付記４に記載の方法。
（付記８）
文字を含む画像を処理する装置であって、
文字セット内で、以下では第１文字と称する該文字セット内の或る文字に対して、最も高い形状類似度を有する１つ以上の文字を探索するように構成された初期選択装置であり、探索された該１つ以上の文字が前記第１文字の類似文字リストを形成し、当該初期選択装置は更に、前記文字セット内で、前記第１文字の類似文字リスト内の各文字に対して、最も高い形状類似度を有する１つ以上の文字を探索し、前記第１文字の類似文字リスト内の各文字の類似文字リストを形成するように構成されている、初期選択装置と、
前記類似文字リスト内で、相互に高い類似度を有する１つ以上の文字を、１つの文字クラスタとして選択するように構成されたクラスタ形成装置と、
を有する装置。
（付記９）
前記初期選択装置は更に、前記文字セット内で前記第１文字に対して最も高い形状類似度を有する１つ以上の文字を探索することを、
前記文字セット内で、前記第１文字の複数の画像サンプルのうちの各画像サンプルに対して、最も高い形状類似度を有する１つ以上の文字を、該画像サンプルの候補文字セットとして探索することで、各々が前記複数の画像サンプルのうちの１つに対応する複数の候補文字セットを形成し、
各文字が前記複数の候補文字セット内に現れる頻度を計算し、且つ
前記複数の候補文字セット内で、最も高い頻度に対応する１つ以上の文字を選択することで、前記第１文字の類似文字リストを形成する、
ことによって行うように構成されている、付記８に記載の装置。
（付記１０）
前記初期選択装置は更に、前記文字セット内で各画像サンプルに対して最も高い形状類似度を有する１つ以上の文字を探索することを、
文字認識エンジンを用いて各画像サンプルを認識して、該画像サンプルの認識結果を取得し、ここで、該認識結果は、該画像サンプルに形状的に類似する１つ以上の文字と、該１つ以上の文字と該画像サンプルとの間での形状類似度の値とを含み、且つ
該認識結果内で、最も高い類似度の値に対応する１つ以上の文字を選択する、
ことによって行うように構成されている、付記９に記載の装置。
（付記１１）
前記初期選択装置は更に、前記複数の候補文字セット内で最も高い頻度に対応する１つ以上の文字を選択することを、
前記複数の候補文字セット内で、第１の閾値より高い頻度に対応する１つ以上の文字を選択することで、前記第１文字の類似文字リストを形成する、
ことによって行うように構成されている、付記９又は１０に記載の装置。
（付記１２）
前記文字クラスタの如何なる２つの文字についても、その一方は他方の類似文字リストに含まれる、付記８又は９に記載の装置。
（付記１３）
前記初期選択装置は更に、各文字が前記複数の候補文字セット内に現れる頻度を計算する前に、前記第１文字に対して第２の閾値より低い形状類似度を有する文字を、各候補文字セットから除去するように構成されている、付記９又は１０に記載の装置。
（付記１４）
前記第１の閾値は、前記複数の候補文字セット内で２番目に高い頻度に対応する文字の頻度に比例する、付記１１に記載の装置。
【符号の説明】
【００７８】
７００  文字を含む画像を処理する装置
７０２  初期選択装置
７０４  クラスタ形成装置
８００  コンピュータ
８０１  ＣＰＵ
８０２  ＲＯＭ
８０３  ＲＡＭ
８０４  バス
８０５  入力／出力インタフェース
８０６  入力装置
８０７  出力装置
８０８  記憶装置
８０９  通信装置
８１０  ドライブ
８１１  リムーバブルメディア
【図１】
0005691953.tif 000016
【図２】
0005691953.tif 000017
【図３】
0005691953.tif 000018
【図４】
0005691953.tif 000019
【図５】
0005691953.tif 000020
【図６】
0005691953.tif 000021
【図７】
0005691953.tif 000022
【図８】
0005691953.tif 000023