(57)【特許請求の範囲】
【請求項１】
文字列画像から文字パターンをストロークに分解して抽出するストローク抽出装置において、
光学的に走査された文字列画像を入力して記憶する文字列画像記憶部と、前記文字列画像からストローク推定用データを抽出するストローク推定用データ作成部と、前記ストローク推定用データから混合正規分布表現特徴を作成する混合正規分布推定部と、前記混合正規分布表現特徴からストローク情報を出力するストローク抽出部と、を備え、
前記混合正規分布表現特徴として、該混合正規分布における、正規分布の数、及び各正規分布の中心と共分散と混合比とが含まれ、
前記混合正規分布推定部において、前記文字パターンが正規分布の重ね合わせとして表現され、
前記ストローク抽出部において、前記正規分布の重ね合わせにより前記文字パターンのストロークが抽出されることを特徴とするストローク抽出装置。
【請求項２】
前記ストローク推定用データが、前記文字列画像の黒画素の二次元座標値からなることを特徴とする請求項１記載のストローク抽出装置。
【請求項３】
前記ストローク推定用データが、前記文字列画像に距離変換を施した画像の、距離値を頻度に対応させた二次元座標値からなることを特徴とする請求項１記載のストローク抽出装置。
【請求項４】
前記正規分布のパラメータが、ＥＭアルゴリズムを利用して推定されることを特徴とする請求項１乃至３のいずれか一に記載のストローク抽出装置。
【請求項５】
前記正規分布の方向成分と分散成分とが、別々に、ＥＭアルゴリズムを利用して推定されることを特徴とする請求項４記載のストローク抽出装置。
【請求項６】
前記正規分布の分散成分が固定され、方向成分だけがＥＭアルゴリズムを利用して推定されることを特徴とする請求項４記載のストローク抽出装置。
【請求項７】
前記重ね合わせるべき正規分布が、学習によって統計的に求められることを特徴とする請求項１乃至６のいずれか一に記載のストローク抽出装置。
【請求項８】
文字列画像から文字パターンをストロークに分解して抽出するストローク抽出方法において、
光学的に走査された文字列画像を入力して記憶する文字列画像記憶ステップと、前記文字列画像からストローク推定用データを抽出するストローク推定用データ作成ステップと、前記ストローク推定用データから混合正規分布表現特徴を作成する混合正規分布推定ステップと、前記混合正規分布表現特徴からストローク情報を出力するストローク抽出ステップと、を含み、
前記混合正規分布表現特徴として、該混合正規分布における、正規分布の数、及び各正規分布の中心と共分散と混合比とが含まれ、
前記混合正規分布推定ステップにおいて、前記文字パターンを正規分布の重ね合わせとして表現し、
前記ストローク抽出ステップにおいて、前記正規分布の重ね合わせにより前記文字パターンのストロークを抽出することを特徴とするストローク抽出方法。
【請求項９】
前記ストローク推定用データとして、前記文字列画像の黒画素の二次元座標値を用いることを特徴とする請求項８記載のストローク抽出方法。
【請求項１０】
前記ストローク推定用データとして、前記文字列画像に距離変換を施した画像の、距離値を頻度に対応させた二次元座標値を用いることを特徴とする請求項８記載のストローク抽出方法。
【請求項１１】
前記正規分布のパラメータを、ＥＭアルゴリズムを利用して推定することを特徴とする請求項８乃至１０のいずれか一に記載のストローク抽出方法。
【請求項１２】
前記正規分布の方向成分と分散成分とを、別々に、ＥＭアルゴリズムを利用して推定することを特徴とする請求項１１記載のストローク抽出方法。
【請求項１３】
前記正規分布の分散成分を固定して、方向成分だけをＥＭアルゴリズムを利用して推定することを特徴とする請求項１１記載のストローク抽出方法。
【請求項１４】
前記重ね合わせるべき正規分布を、学習によって統計的に求めることを特徴とする請求項８乃至１３のいずれか一に記載のストローク抽出方法。
【請求項１５】
請求項８乃至１４のいずれか一に記載のストローク抽出方法をコンピュータに実行させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、光学的に走査された文字列画像から文字パターンを部分パターンに分解する装置、方法及び記憶媒体に関し、特に、文字をストロークに分解するストローク抽出装置、ストローク抽出方法及びストローク抽出用プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
郵便物や帳票上に記載された文字列を光学的文字読み取り装置(ＯＣＲ)で読み取って文字認識する場合、ストローク抽出はしばしば用いられている。例えば、文字を認識する際の特徴量として、文字パターンを方向成分を持ったストロークに分解して表現することは大変効果的であることが知られており、広く用いられている技術である。
【０００３】
文字を認識する際の特徴として手書き文字からストロークを抽出する技術が、特開昭５７−１９９０７５号公報に提案されている。この技術では、文字切り出し後のパターン領域の各黒画素にその連続方向に対応した方向コードを付ける第一ステップと、この処理後のパターン領域を方向コード毎に別々の方向に走査して各方向コード毎の連結性を調べ、連結した同一方向コードの画素群をストロークとして抽出する第二ステップとからなる。また、第二ステップでは、ストローク同士の交差を監視する処理が行われており、交差したストロークを別々のストロークとして抽出することも可能である。
【０００４】
一方、郵便物や帳票上に記載された文字列を読み取る場合、認識処理に先立って前処理が実施され、この前処理において、１文字を切り出す際の候補となる幾つかの文字切り出し候補が求められる。
【０００５】
従来、このような文字切り出し候補の生成では、文字列画像が与えられたときに、黒画素の連結成分や、文字列の垂直方向に黒画素を投影して求めた投影関数を用いて文字パターンの最小単位を作り、これらの最小単位を幾つか組み合わせることにより文字切り出し候補を生成していた。さらに、文字パターン同士が接触している場合にも、正解を含む文字切り出し候補を生成するために、ストローク抽出が用いられている。
【０００６】
文字切り出し候補生成のためのストローク抽出方式としては、文字列画像をモフォロジー演算を用いて特定の方向を向いた線分に分解し、これらの線分をマージしてストロークを作成し、ストロークを文字切り出しの最小単位として文字切り出し候補を作成する方法が、”石寺他：「ストローク抽出に基づく文字切り出しの一手法」(信学ソ大、Ｄ−３４８、１９９６)”において提案されている。
【０００７】
【発明が解決しようとする課題】
しかし、文字切り出し候補作成のために、これらの技術を利用してストロークを抽出すると、いずれの方法もストロークの方向成分を量子化しているために、図２のように量子化された角度よりも小さな角度変化を伴って二つの直線が接触している場合、二つの直線を分離することが困難である。図２は縦書きされた文字列の一部であり「ノ」と「十」が接触している例である。
【０００８】
また、文字認識のための特徴としてストロークを用いる際にも、ストロークの方向成分の分解能を向上させることは、認識精度を向上させるためにも重要である。つまり、ストローク抽出における課題の一つとしてストロークの方向成分の分解能向上が挙げられる。
【０００９】
また、従来から提案されているストローク抽出方法によると、いずれの方式も黒画素の連結性を前提とした処理であるために、図２のように文字ストロークがかすれている(とぎれている)場合にかすれた箇所が消失してしまったり、方向成分が特定できない問題があった。つまり、ストローク抽出における二つ目の課題として、文字のかすれに頑健なストローク抽出の実現が挙げられる。
【００１０】
さらに、文字線幅の変化への対応に関しても課題であると言える。特開昭５７−１９９０７５号公報の方式では、画素群を特定の方向に走査する処理によって線幅の太い箇所でも方向成分を特定可能であるが、モフォロジー演算を用いた方法によると、図２のように線幅が一つのパターン内で大きく変動する場合に、線幅の細い部分が消失してしまったり、逆に線幅の太い部分でストロークの方向成分を特定できない等の問題がある。
【００１１】
さて、方向成分の分解能を高めることに対しては、例えば、”窪田：「ストローク方向抽出フィルタを用いた手書き数字認識」(信学技報PRMU98-164、１９９８)”において提案されている方式を用いることで、角度方向の分解能向上を得ることが可能である。しかし、本方式によると、方向フィルタはその大きさがあらかじめ決められており、対応可能な線幅がフィルタの大きさを決定した時点で決ってしまうので、多様な線幅への対応が困難である。また、フィルタは局所的な範囲に対してのみ適用されるので、フィルタ周辺に黒画素が密に存在しない箇所においては方向成分が全く特定できないということになり、図２のようにかすれのある箇所において方向を求めることは困難である。
【００１２】
かすれに関しては、”平野他：「外郭ゼロ交差特徴と正準判別分析法による低品質印刷文字認識」(信学技報PRMU98-159、１９９８)”において、ぼかした多値文字パターンのゼロ交差から文字の外郭形状を求め、拡張方向寄与度を求める方法が提案されているが、本手法はストロークを直接求めるのではなく文字の外郭特徴を求める方式であること、また、角度方向の分解能が十分ではないという問題点がある。
【００１３】
以上述べて来たように、従来から知られているストローク抽出方式では、角度方向の高い分解能と、線幅の変動に対する頑健性と、かすれた箇所における方向成分の特定を同時に満たすことは困難である。
【００１４】
本発明は、上記問題点に鑑みてなされたものであって、その主たる目的は、ストロークに対する高い方向成分分解能を持ち、線幅の変動にも柔軟に対応でき、かすれた箇所においても安定してストロークを抽出可能なストロークを抽出装置、ストローク抽出方法及びストローク抽出用プログラムを記録した記録媒体を提供することにある。
【００１５】
【課題を解決するための手段】
上記目的を達成するため、本発明のストローク抽出装置は、文字列画像から文字パターンをストロークに分解して抽出するストローク抽出装置において、光学的に走査された文字列画像を入力して記憶する文字列画像記憶部と、前記文字列画像からストローク推定用データを抽出するストローク推定用データ作成部と、前記ストローク推定用データから混合正規分布表現特徴を作成する混合正規分布推定部と、前記混合正規分布表現特徴からストローク情報を出力するストローク抽出部と、を備え、前記混合正規分布表現特徴として、該混合正規分布における、正規分布の数、及び各正規分布の中心と共分散と混合比とが含まれ、前記混合正規分布推定部において、前記文字パターンが正規分布の重ね合わせとして表現され、前記ストローク抽出部において、前記正規分布の重ね合わせにより前記文字パターンのストロークが抽出されるものである。
【００１６】
本発明においては、前記ストローク推定用データが、前記文字列画像の黒画素の二次元座標値、又は、前記文字列画像に距離変換を施した画像の、距離値を頻度に対応させた二次元座標値からなる構成とすることができる。
【００１８】
また、本発明においては、前記正規分布のパラメータが、ＥＭアルゴリズムを利用して推定されることが好ましい。
【００２０】
また、本発明のストローク抽出方法は、文字列画像から文字パターンをストロークに分解して抽出するストローク抽出方法において、光学的に走査された文字列画像を入力して記憶する文字列画像記憶ステップと、前記文字列画像からストローク推定用データを抽出するストローク推定用データ作成ステップと、前記ストローク推定用データから混合正規分布表現特徴を作成する混合正規分布推定ステップと、前記混合正規分布表現特徴からストローク情報を出力するストローク抽出ステップと、を含み、前記混合正規分布表現特徴として、該混合正規分布における、正規分布の数、及び各正規分布の中心と共分散と混合比とが含まれ、前記混合正規分布推定ステップにおいて、前記文字パターンを正規分布の重ね合わせとして表現し、前記ストローク抽出ステップにおいて、前記正規分布の重ね合わせにより前記文字パターンのストロークを抽出するものである。
【００２２】
また、本発明は、上記ストローク抽出方法をコンピュータに実行させるためのプログラムを記録した記録媒体を含むものである。
【００２３】
このように、本発明は上記構成により、文字パターンを混合正規分布と考え、共分散行列の中に線幅と方向成分を表現し、両者を推定するので線幅の変動にも柔軟に対応でき、ストロークの方向成分に対する高い分解能を持つストローク抽出を行うことができる。また、関数の値が緩やかに減少する性質を持つ関数である正規分布を利用して広い範囲でのデータの規則性を抽出しているため、かすれがある場合にも柔軟に対応が可能になり、安定してストローク抽出を行うことができる。
【００２４】
【発明の実施の形態】
次に、本発明の一実施の形態に係るストローク抽出装置、ストローク抽出方法について図面を参照して詳細に説明する。
【００２５】
図１は、本発明の一実施の形態の構成を示すブロック図である。図１に示す実施の形態は、光学的に走査された文字列画像を入力して記憶する文字列画像記憶部１１と、文字列画像記憶部１１から文字列画像を入力してストローク推定用データを抽出するストローク推定用データ作成部１２と、ストローク推定用データを入力して混合正規分布表現特徴を作成する混合正規分布推定部１３と、混合正規分布表現特徴を入力してストローク情報を出力するストローク抽出部１４とを備えて構成される。
【００２６】
次に、本実施の形態の動作について説明する。文字列画像記憶部１１では、光学的に走査された文字列画像を入力して記憶する。これは、通常のスキャナとメモリーを用いて容易に実現が可能である。
【００２７】
ストローク推定用データ作成部１２では、文字列画像記憶部１１から文字列画像を入力してストローク推定用データを抽出する。ストローク推定用データとしては、いくつかの実現方法が考えられるが、例えば、文字列画像を二次元空間上の点の集合に変換することが考えられる。
【００２８】
例を挙げて説明すれば、図３に示すように４×４の画像パターンが入力されたとすると、一般的な技術においては４×４のマトリクスとして図４のように表現されるが、本発明では図４のマトリクスの(ｉ，ｊ)要素が１である要素のｉとｊの値を用いて、図５のように二次元データが黒画素の個数分だけ集まっている集合であるとして、これをストローク推定用データとすることができる。すなわち、文字認識を行う場合、通常、文字パターンはＮ×Ｍのマトリクスとして扱われ、Ｎ×Ｍ次元の空間の一点として扱われるのが一般的であるが、本発明では、一つの黒画素に対してその二次元座標をストローク推定用データとして与える。したがって、文字パターンは、二次元空間上の点の集合となる。
【００２９】
他の実現方法として、例えば、入力画像にあらかじめ距離変換を施し、その距離値をデータ発生頻度と考えて二次元データを作成し、本方式に入力することも可能である。つまり、元画像の例として図６のようなパターンが与えられたときに、それを距離変換した画像は図７となり、ストローク推定用データとして、図８のようなものを与えることもできる。
【００３０】
混合正規分布推定部１３では、ストローク推定用データを入力して入力文字パターンを混合正規分布として表現し、混合正規分布表現特徴を出力する。混合正規分布特徴とは、混合正規分布における、正規分布の数、各正規分布の持つ中心と共分散と混合比からなる。高い方向成分の分解能を持ち、線幅の変化にも柔軟に対応可能で、かすれにも安定してストロークを抽出するためにはいくつかの方法が考えられるが、本発明では、文字パターンを二次元正規分布の混合モデルと考え、いくつかの正規分布を一つのストロークに対応させる方法が考えられる。
【００３１】
例えば、ストロークを正規分布として近似することを考え、ストローク抽出用データから、二次元の混合正規分布推定手法を用いて、正規分布を抽出することでストロークとすることができる。図９の例で説明するならば、ストローク抽出用データが×印として入力されたときに、これらを二次元の正規分布の重ね合わせとして表現が可能であり(点線で表示)、一つの正規分布を一つのストロークとして抽出することができる。
【００３２】
ここで、文字パターンを二次元正規分布の混合モデルと考える方法の意義と詳細について説明する。文字パターンは、ある二次元の確率分布に従って独立に発生した黒画素の集合として考えることが可能である。このように考えると文字パターンを表現することは、二次元の確率分布を推定する問題として考えることができる。
【００３３】
本来、手書き文字パターンの黒画素は独立に(バラバラに)生起するものではなく、時系列的になんらかのきまりをもって生起すると考える方がより現実に近いが、ＯＣＲでは筆順や筆記方向等、筆記中の時系列状態を観測できないのでこのように考えても差し支えない。例え、一つ一つの黒画素がバラバラに生起したとしても、最終的に人間がそれを見た際には、一つの文字として知覚されることからも、これは差し支えないと言える。他の例で説明すれば、ゴム印等を用いて印を押す場合もインクがどのような順番で紙に染み込むかはよくわからないが、最終的に人間がそれを見た際には、一つの文字として知覚されることからもやはり差し支えないと言える。
【００３４】
さて、一般に、多くの確率分布は混合正規分布によって表現が可能である。今、文字パターンを二次元正規分布の混合モデルであると考えれば、ある局所的な文字線の線幅と方向成分は、二次元正規分布のパラメータである共分散行列の中に自然に表現が可能になる。二次元(２×２)の共分散行列を固有値と固有ベクトルに分解すると、第一固有ベクトルはストロークの方向を、第一固有値はその長さを表し、第二固有ベクトルは線幅方向を、第二固有値は線幅を表すと考えることができるからである。混合正規分布のパラメータはＥＭアルゴリズム(Dempster et al.”Maximum likelihood from incomplete data via the EM algorithm,”J.Roy.ＳＴatist.Soc.B,vol.39,pp.1-38,1977)によってデータから推定できることが知られている。
【００３５】
ここで、本発明において文字パターンを正規分布の重ね合わせと考えることの意義を詳しく述べる。文字パターンを正規分布の重ね合わせと考えると、ストロークは一つ一つの正規分布であると考えることができる。つまり、ストロークを抽出することを、正規分布のパラメータを推定することとして考えることが可能になる。
【００３６】
このように、ストロークを混合正規分布の中のある一つの正規分布であると考えれば、共分散行列の中に線幅の表現が含まれているので、共分散行列を推定することは線幅の推定を含んでいることになる。よって、線幅の変化に追従することが可能になり、線幅の変化や線幅の多様性によらずストロークを抽出可能になる。方向成分についても、共分散行列の第一固有ベクトルが方向成分を表すので、共分散行列を推定することは方向成分の推定を含んでいる。さらに、共分散行列の第一固有ベクトルとして表される方向成分は連続的に定義可能であり、量子化誤差を心配する必要がない十分な方向分解能が得られる。
【００３７】
また、本方式によれば、従来のように黒画素がある方向に連結している長さを計測するのではなく、黒画素の連結性をもともと仮定しないで、黒画素は独立に生起すると仮定して、関数の値が緩やかに減少する性質を持つ関数である正規分布を利用して広い範囲でのデータの規則性を抽出しているために、かすれがある場合にも柔軟に対応が可能になる。
【００３８】
混合正規分布はベクトルχを入力とすると、以下のように定義される。
【００３９】
0004737576.tif 000002
【００４０】
ただし、
0004737576.tif 000003
【００４１】
式（１）のＬは正規分布の数である。一つ一つの正規分布のことを正規分布モデルと呼ぶ。ここで、ｆiはｉ番目の正規分布モデルであり、μiはｉ番目の正規分布モデルの中心を表すベクトル、Σiはｉ番目の正規分布モデルの共分散行列、Ｐｒiはｉ番目の正規分布モデルの混合比であり、ΣiＰｒi＝１を満たす。つまり、式（１）で表される混合正規分布は、Ｌ個の正規分布モデルの重ね合わせによってχを表現しており、各正規分布モデル毎に、中心と共分散と混合比の３つのパラメータを持つことになる。また、ｄは次元数であり、この場合２である。また、ベクトルの右肩の添字Ｔは転置を意味する。さらに｜Σ｜はΣの行列式を表し、行列の右肩の添字−１は、逆行列を意味する。
【００４２】
混合正規分布におけるパラメータ推定には、例えばＥＭアルゴリズムを用いればよい。他にも、例えば”上田他：「混合モデルのための併合分割操作付きＥＭアルゴリズム」(信学論、vol.J82-D-II、No.5、pp930-940、1999)”に記載の方法を用いることもできる。また、併合分割操作付きＥＭアルゴリズムを用いる場合、併合分割基準として、文献(混合モデルのための併合分割操作付きＥＭアルゴリズム)の基準だけでなく、例えば共分散行列の行列式の値が小さい正規分布モデルを中心間距離の最も近い正規分布モデルに併合し、行列式の値の大きい正規分布モデルを分割するような基準を用いることもできる。
【００４３】
また、ＥＭアルゴリズムによってパラメータを推定する際に、混合比Ｐｒiと各正規分布モデルの中心μiは通常のＥＭアルゴリズムによって求めて、共分散行列は回転方向と分散の成分にわけてそれぞれを推定することも考えられる。その場合は、以下の手続きによって推定式を導出すれば、容易に推定が可能である。
【００４４】
まず、共分散行列の逆行列を回転を表す変換を用いて、あらかじめ対角化された形式で表現する。
【００４５】
0004737576.tif 000004
【００４６】
ここで、共分散行列を式（３）のように表現すると、共分散行列をθとλ1、λ2の関数として考えることができるので表記としてΣ(θ,λ1,λ2)という形にしている。以降は、共分散行列の回転方向だけを推定するのでΣ(θ)と表記する。
【００４７】
さて、ＥＭアルゴリズムにおけるＱ関数は、Ｎ個の学習データχk(ｋ＝1,2,…,Ｎ)が与えられたとすると、以下のとおりである。
【００４８】
0004737576.tif 000005
【００４９】
ここで、式（５）の第二項は以下の通りである。
【００５０】
0004737576.tif 000006
【００５１】
ここで、Ｌは正規分布モデルの数、Ｎは与えられたデータの数、ψiはｉ番目の正規分布モデルのパラメータのうち、特に中心と共分散行列を意味する。また、Φはパラメータを推定する前の値であり、Φ′は新たに推定し直したパラメータの値を意味する。学習の最初のステップではΦにはあらかじめ初期値を代入する。この初期値は、混合比の条件と共分散行列の正定値の条件を満たせばランダムな数値でもよい。
【００５２】
パラメータΣの学習に関係する部分は式（５）の第二項である。この項を最大化するには、以下の式でψi′による微分がゼロになるようパラメータを更新すればよい。
【００５３】
0004737576.tif 000007
【００５４】
正規分布の混合モデルでは、ｆｉ(χｋ｜ψｉ′)は、式（２）で表されるので、
0004737576.tif 000008
【００５５】
Σ（θi′）の行列式の値はθi′の変化に対して不変であること、また回転成分だけを推定する場合、∇ψi′は∇θi′と置けばよいことに注意すると以下を得る。
【００５６】
0004737576.tif 000009
【００５７】
ここで、
0004737576.tif 000010
である。
【００５８】
式（１０）を式（９）に代入して、
0004737576.tif 000011
【００５９】
これを式（７）に代入して、
0004737576.tif 000012
よって、この式（１２）を満足するθｉ′を求めることによって解を得る。
【００６０】
いま、
0004737576.tif 000013
とおけるので、以下のように書ける。
【００６１】
0004737576.tif 000014
【００６２】
ゆえに、以下を得る。
【００６３】
0004737576.tif 000015
【００６４】
同様にして、λi１をｉ番目の正規分布モデルの第一固有値として、λi１′で式（８）を微分すると以下を得る。
【００６５】
0004737576.tif 000016
【００６６】
ここで、
0004737576.tif 000017
【００６７】
これを式（７）に代入して
0004737576.tif 000018
よって、λi１′の解を得る。また、第二固有値λi２′の解も同様に求めることができる。
【００６８】
ここまで説明したように、角度方向と分散の成分を別々にわけて学習することによって、例えば、全ての正規分布モデルの広がり成分を固定したままで中心と角度方向だけを推定し、学習を簡略化することで処理速度の向上や局所最適解へ収束してしまう問題の軽減を計ることも可能である。
【００６９】
また、モデル数をどのように選択するかも問題になるが、例えばＡＩＣやＭＤＬのような情報量基準に対して最良な値を与えるようなモデル数を選択することができる。文字パターンは混合正規分布として表現され、この混合正規分布のパラメータである、正規分布モデルの数と、各正規分布モデル毎の、中心と共分散と混合比を混合正規分布表現特徴として出力する。
【００７０】
次に、ストローク抽出部１４では混合正規分布表現特徴から、ストローク情報を構成して出力する。
【００７１】
ストローク情報を構成するには、例えば一つのストロークを一つの正規分布モデルと混合比の掛け算として抽出することができる。図で説明すれば、図９において、入力された文字パターンは、Gaussian1、Gaussian2、Gaussian3、Gaussian4、Gaussian5の五つの正規分布モデルの重ね合わせとして表現されている。ストローク抽出部の出力としてのストローク情報としては、例えばGaussian1からGaussian5までの五つの正規分布モデルをそれぞれ別々のストローク情報として出力することができる。
【００７２】
また、ストローク抽出部の出力としてのストローク情報は、一つの正規分布モデルを一つのストロークに対応させるだけでなく、いくつかの正規分布モデルとその混合比の掛け算の重ね合わせを一つのストロークとして抽出することも可能である。すなわち、別の出力方法として、例えばGaussian1は一つ目のストロークとして出力し、Gaussian2とGaussian5の重ね合わせを二つ目のストロークとして出力し、Gaussian3とGaussian4を三つ目のストロークとして出力することもできる。
【００７３】
いくつかの正規分布モデルの重ね合わせを一つのストロークとして抽出する場合、実現方法としていくつかの方法が考えられる。例えば、任意の正規分布モデルのペアに対して、互いの中心ベクトルと共分散行列を重ね合わせ評価特徴として考える。このとき、中心ベクトルは二次元であり、共分散行列は対称行列ゆえに対角要素二つと非対角要素一つの三つの値を持つので、重ね合わせ評価特徴は１０次元のベクトルになる。この重ね合わせ評価特徴を統計的に評価して、一つのストロークとして出力すべきかどうかを決定することができる。
【００７４】
この際、あらかじめ人間が学習データとして、一つのストロークに統合すべき正規分布モデルのペアから得られた重ね合わせ評価特徴の教師データを１と与え、一つのストロークに統合すべきでない正規分布モデルのペアから得られた重ね合わせ評価特徴の教師データを０と与えてバックプロパゲーションによって学習した多層パーセプトロンの構成をしたニューラルネットを用いて、一つのストロークとして出力すべきかどうかを決定することができる。
【００７５】
このニューラルネットは、例えば三層パーセプトロンを用いることが可能であり、入力層は重ね合わせ評価特徴の次元数と同じ１０個のニューロンを持ち、中間層には５個のニューロン、出力層に１個のニューロンを持つ構造にすることができるし、中間層のニューロンの個数は２個以上から１０００個以下の自由な数に設定することが可能である。また、ニューラルネットではなく、判別分析や重回帰分析等の方法を用いることもできる。
【００７６】
判定の際の具体的手順は、例えば学習済のニューラルネットに重ね合わせ評価特徴を入力し、出力が０．５以上であれば一つのストロークとして出力すべきと判定し、そうでなかった場合には一つのストロークとして出力すべきでないと判定することができる。重回帰分析を用いた場合も同様に判定することが可能である。判別分析の場合は、判別得点を用いて、判別得点があらかじめ定められた閾値以上の場合一つのストロークとして出力すべきと判定し、そうでなかった場合には一つのストロークとして出力すべきでないと判定することができる。
【００７７】
他にも、例えば「特願平０８−１２２３３３号公報、文字切り出し候補発生装置」に記載されている方法を用いることによって容易に実現可能である。
【００７８】
【実施例】
上記した本発明の実施の形態についてさらに詳細に説明すべく、本発明の具体的な実施例の動作を詳細に説明する。
【００７９】
図１０は、本発明のストローク抽出装置に入力された文字パターンの画像の例である。この文字パターンは黒画素数が２２１個である。図１０のような文字パターンが文字列画像記憶部１１から入力され、ストローク推定用データ作成部１２によってストローク推定用データを得る。
【００８０】
その例を図１１に示す。この動作は、入力された文字列画像に通常のラスタースキャンを施し、注目画素が黒画素であったときに、その座標情報を出力すれば良い。混合正規分布推定部１３では、二次元データ集合であるストローク推定用データを入力して、混合正規分布表現特徴を求める。
【００８１】
混合正規分布推定部１３における、一連の動作をフローチャートで説明すれば、図１２のようになる。
【００８２】
フローチャートのＳＴ１１からＳＴ１２までの処理は、モデル数をいくつに設定するかを決定する処理である。ストローク推定用データが入力されると、ＳＴ１１では入力データのデータ数をカウントする。入力画像が図１０の例の場合では、入力されるストローク推定用データ(図１１)のデータ数は２２１個とカウントされる。ＳＴ１２では、正規分布モデルの個数を決定する処理が行われる。この決定処理はＳＴ１１でカウントされたデータ数を、例えば、７０で割った整数を出力することでモデル数を設定することができる。つまり、入力画像が図１０の例の場合では、入力されるストローク推定用データ(図１１)のデータ数２２１を７０で割ると３となり、あまりは１１であるから、この場合モデル数は３個に設定される。
【００８３】
ＳＴ１３ではＳＴ１２で設定されたモデル数を受けて初期値の設定を行う。モデル数を３個と与え、正規分布モデルのパラメータにランダムな初期値を与えた例を図１３に示す。この例のように、各正規分布モデルの共分散行列には単位行列を与えることができる。また、各正規分布モデルの混合比はすべてのモデルに対して一定の値を与えることができる。
【００８４】
ＳＴ１４において、図１１の例に示すストローク推定用データと、図１３の例に示す初期値が与えられて、混合正規分布のパラメータ推定が行われる。混合正規分布のパラメータ推定は、ストローク推定用データに基づいて尤度が最大になるように調整すればよく、通常のＥＭアルゴリズムやＳＭＥＭアルゴリズムを施せば良い。ＳＴ１５ではＳＴ１４で推定されたパラメータを、図１４に示す例のように混合正規分布表現特徴として出力する。図１４の例は、入力された図１０のパターンを三つの正規分布モデルによる混合分布で表現した結果である。この三つの正規分布の二次元空間上の様子を図にしたものが図１５である。
【００８５】
また、ＳＴ１４は通常のＥＭアルゴリズムやＳＭＥＭアルゴリズムではなく、図１６のようなフローチャートによって実現することも可能である。
【００８６】
ＳＴ２１では、各正規分布モデルの共分散行列を式（３）のように表現する。
【００８７】
ＳＴ２２では、通常のＥＭアルゴリズムやＳＭＥＭアルゴリズムと同様に、各正規分布モデルの混合比Ｐｒi′と中心μｉ′を推定する。
【００８８】
次に、ＳＴ２３では共分散式を式（３）の形式で表現したときのθｉ′を推定する。この推定は式（１５）によって求められる。
【００８９】
ＳＴ２４では、共分散式を式（３）の形式で表現したときのλi1′を推定する。この推定は式（１９）によって求められる。
【００９０】
ＳＴ２５からＳＴ２７は、全ての正規分布モデルにおける第二固有値の値を一定にするための処理である。全ての正規分布モデルに対してλi2′を求め、その平均値をλ２とするが、各正規分布モデルのλi2′が初期値と同じ値であった場合λ２は設定されていないとする。もしλ2が設定されていれば処理はＳＴ２８に移るが、λ2が設定されていない場合ＳＴ２６へ移る。
【００９１】
ＳＴ２６では、共分散式を式（３）の形式で表現したときのλi2′を推定する。この推定は式（１９）によって求められる。
【００９２】
ＳＴ２７では、全ての正規分布モデルに対するλｉ２の平均値λ２を求め、各正規分布モデルのλi2′の値をλ２に置き換える。
【００９３】
ＳＴ２８では、Ｐｒｉ′とμi′とθi′とλi1′とλ2′を、それぞれ新たな混合正規分布のパラメータＰｒiとλi１とθiとλi１とλ2に置き換え、対数尤度を求める。
【００９４】
ＳＴ２９では、対数尤度の増加率があらかじめ定められた閾値よりも小さくなった場合に処理が収束したと判断し終了する。そうでない場合は、再びＳＴ２２に戻る。また、図１２のＳＴ１２では、正規分布モデル数の設定の方法は、データ数を７０で割った整数に固定する必要はなく、データ数を２から１０００までの任意の整数で割った整数を与えることもできる。さらに、最適な混合数を決定する際には、例えば複数の正規分布モデル数を設定して、それぞれの正規分布モデル数の場合の混合正規分布を推定すると同時にＡＩＣやＭＤＬ等の情報量基準を求め、最良のＡＩＣやＭＤＬ等の情報量基準を与える正規分布モデル数に決定することも可能である。
【００９５】
図１０の例に対してＭＤＬによって最良な正規分布モデル数を決定すると図１４と図１５に示す例のように正規分布モデル数が３個になる。また、図１０の例に対してＡＩＣによって最良な正規分布モデル数を決定すると正規分布モデル数が４個になる。その際の混合正規分布表現特徴を図１７に、二次元空間上の様子を図１８に示す。
【００９６】
また、図１６のフローチャートのように、λ２を全ての正規分布モデルで同じ値にする方法は、入力された文字列画像の線幅がほぼ一定であった場合に、推定すべきパラメータの数を一つ減らす働きがあり、処理の高速化を可能にする。
【００９７】
ストローク抽出部１４では、ストローク情報を出力する。最終的に出力されるストローク情報の形式としては、ストロークに属する正規分布モデルの個数と、それらの正規分布モデルのパラメータと混合比のセットが、ストロークの数だけ出力される。例えば、一つのストロークを一つの正規分布モデルとして出力する場合、出力結果は図１４の混合正規分布表現特徴が入力されたとき図１９のようになる。
【００９８】
また、出力形式として他の出力形式も考えられる。すなわち、図１４や図１７のような混合正規分布表現特徴が入力された場合、任意の正規分布モデルのペアに対して重ね合わせ評価特徴を統計的に評価して、一つのストロークとして出力すべきと判定された場合にはそれらをストロークとして出力する。図１４の例のような入力に対して、例えばニューラルネットを用いて一つのストロークとして出力すべきかどうかの評価を行ったときに、いずれの正規分布モデルのペアに対してもその出力が０．１以下であり、一つのストロークとして出力すべきと判定された正規分布モデルのペアがなかった場合、出力は図１９と同様な出力となる。
【００９９】
一方、図１７の入力に対して、ニューラルネットを用いて同様な評価を行った場合、２番目と３番目の正規分布モデルのペアでは値が０．９となり、それ以外のペアでは出力が０．１以下であり、２番目と３番目の正規分布モデルのペアでのみが一つのストロークとして出力すべきと判定された場合には、図２０のような出力が得られる。
【０１００】
この処理をフローチャートで説明すると図２１のようになる。ＳＴ３１では、一つの正規分布モデルに着目して、ＳＴ３２において着目正規分布モデルとそれ以外の正規分布モデルを同一ストロークとするべきかどうか判定する。この判定は、統計的な判定によって行うことが可能である。例えば、任意の正規分布モデルのペアに対して、互いの中心ベクトルと共分散行列を重ね合わせ評価特徴として考える。
【０１０１】
このとき、中心ベクトルは二次元であり、共分散行列は対称行列ゆえに対角要素二つと非対角要素一つの三つの値を持つので、重ね合わせ評価特徴は(２＋３)×２モデル分、つまり１０次元のベクトルになる。この重ね合わせ評価特徴を統計的に評価して、一つのストロークとして出力すべきかどうかを決定することができる。
【０１０２】
この際、あらかじめ人間が学習データとして、一つのストロークに統合すべき正規分布モデルのペアから得られた重ね合わせ評価特徴の教師データを１と与え、一つのストロークに統合すべきでない正規分布モデルのペアから得られた重ね合わせ評価特徴の教師データを０と与えて学習したニューラルネットを用いて、一つのストロークとして出力すべきかどうかを決定することができる。また、ニューラルネットではなく、判別分析や重回帰分析等の方法を用いることもできる。この処理を全ての正規分布モデルに対して行い、最終的に同一ストロークとして出力すべきと判定された正規分布モデルは一つのストロークとして出力し、そうでない場合には、一つの正規分布モデルを一つのストロークとして出力する。
【０１０３】
また、ストローク抽出部１３の出力として、混合正規分布の値がある閾値以上になる画素の値を１と置いて画像を出力することもできる。この画像は、かすれパターンが補間された画像として得られることになる。つまり、式（１）の値が例えば０．１1以上ならば、白画素を黒画素に置き換えることによって、かすれを補間することが可能になる。この際、式（１）の値は０．１以上と限定する必要はなく、例えば０から１．０の間で自由に閾値を設定することが可能である。
【０１０４】
なお、上記実施例では、ストローク抽出装置及びストローク抽出方法について記載したが、本発明には上記ストローク抽出方法をコンピュータで実現するためのプログラムを記録した記録媒体も含まれ、ＨＤ、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等の任意の記録媒体を用いて、上記方法をコンピュータで実現することができる。
【０１０５】
【発明の効果】
以上説明したように、本発明のストローク抽出装置によれば、文字パターンを混合正規分布と考え、共分散行列の中に線幅と方向成分を表現し、両者を推定するので線幅の変動にも柔軟に対応でき、ストロークの方向成分に対する高い分解能を持つストローク抽出を行うことができ、関数の値が緩やかに減少する性質を持つ関数である正規分布を利用して広い範囲でのデータの規則性を抽出しているため、かすれがある場合にも柔軟に対応が可能になり、安定してストローク抽出を行うことが可能である。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係るストローク抽出装置の構成を示すブロック図である。
【図２】接触と文字線幅の変動とかすれを伴う文字の例を示す図である。
【図３】入力画像の例を示す図である。
【図４】一般的に用いられるパターン表現の例を示す図である。
【図５】ストローク推定用データの例を示す図である。
【図６】入力画像の例を示す図である。
【図７】距離変換した画像の例を示す図である。
【図８】ストローク推定用データの例を示す図である。
【図９】混合正規分布推定部の動作を説明する図である。
【図１０】本発明の装置に入力される文字パターンの例である。
【図１１】図１０の例に対応したストローク推定用データの例を示す図である。
【図１２】混合正規分布推定部のフローチャートの例を示す図である。
【図１３】混合正規分布推定部で設定された初期値の例を示す図である。
【図１４】図１０の例に対応した三つの正規分布モデルによる混合正規分布表現特徴の例を示す図である。
【図１５】図１０の例に対応した三つの正規分布モデルによる混合正規分布表現特徴の二次元空間上の様子を示す図である。
【図１６】図１２のＳＴ１４の処理に関するフローチャートの例を示す図である。
【図１７】図１０の例に対応した四つの正規分布モデルによる混合正規分布表現特徴の例を示す図である。
【図１８】図１０の例に対応した四つの正規分布モデルによる混合正規分布表現特徴の二次元空間上の様子を示す図である。
【図１９】図１０の例に対応したストローク情報の例を示す図である。
【図２０】図１０の例に対応したストローク情報の例を示す図である。
【図２１】ストローク抽出部のフローチャートの例を示す図である。
【符号の説明】
１１  文字列画像記憶部
１２  ストローク推定用データ作成部
１３  混合正規分布推定部
１４  ストローク抽出部
【図１】
0004737576.tif 000019
【図２】
0004737576.tif 000020
【図３】
0004737576.tif 000021
【図４】
0004737576.tif 000022
【図５】
0004737576.tif 000023
【図６】
0004737576.tif 000024
【図７】
0004737576.tif 000025
【図８】
0004737576.tif 000026
【図９】
0004737576.tif 000027
【図１０】
0004737576.tif 000028
【図１１】
0004737576.tif 000029
【図１２】
0004737576.tif 000030
【図１３】
0004737576.tif 000031
【図１４】
0004737576.tif 000032
【図１５】
0004737576.tif 000033
【図１６】
0004737576.tif 000034
【図１７】
0004737576.tif 000035
【図１８】
0004737576.tif 000036
【図１９】
0004737576.tif 000037
【図２０】
0004737576.tif 000038
【図２１】
0004737576.tif 000039