JP4737576B2 - Stroke extraction device, stroke extraction method, and recording medium recording stroke extraction program - Google Patents
Stroke extraction device, stroke extraction method, and recording medium recording stroke extraction program Download PDFInfo
- Publication number
- JP4737576B2 JP4737576B2 JP2001025794A JP2001025794A JP4737576B2 JP 4737576 B2 JP4737576 B2 JP 4737576B2 JP 2001025794 A JP2001025794 A JP 2001025794A JP 2001025794 A JP2001025794 A JP 2001025794A JP 4737576 B2 JP4737576 B2 JP 4737576B2
- Authority
- JP
- Japan
- Prior art keywords
- stroke
- normal distribution
- character string
- mixed
- string image
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Images
Landscapes
- Character Discrimination (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、光学的に走査された文字列画像から文字パターンを部分パターンに分解する装置、方法及び記憶媒体に関し、特に、文字をストロークに分解するストローク抽出装置、ストローク抽出方法及びストローク抽出用プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
郵便物や帳票上に記載された文字列を光学的文字読み取り装置(ＯＣＲ)で読み取って文字認識する場合、ストローク抽出はしばしば用いられている。例えば、文字を認識する際の特徴量として、文字パターンを方向成分を持ったストロークに分解して表現することは大変効果的であることが知られており、広く用いられている技術である。
【０００３】
文字を認識する際の特徴として手書き文字からストロークを抽出する技術が、特開昭５７−１９９０７５号公報に提案されている。この技術では、文字切り出し後のパターン領域の各黒画素にその連続方向に対応した方向コードを付ける第一ステップと、この処理後のパターン領域を方向コード毎に別々の方向に走査して各方向コード毎の連結性を調べ、連結した同一方向コードの画素群をストロークとして抽出する第二ステップとからなる。また、第二ステップでは、ストローク同士の交差を監視する処理が行われており、交差したストロークを別々のストロークとして抽出することも可能である。
【０００４】
一方、郵便物や帳票上に記載された文字列を読み取る場合、認識処理に先立って前処理が実施され、この前処理において、１文字を切り出す際の候補となる幾つかの文字切り出し候補が求められる。
【０００５】
従来、このような文字切り出し候補の生成では、文字列画像が与えられたときに、黒画素の連結成分や、文字列の垂直方向に黒画素を投影して求めた投影関数を用いて文字パターンの最小単位を作り、これらの最小単位を幾つか組み合わせることにより文字切り出し候補を生成していた。さらに、文字パターン同士が接触している場合にも、正解を含む文字切り出し候補を生成するために、ストローク抽出が用いられている。
【０００６】
文字切り出し候補生成のためのストローク抽出方式としては、文字列画像をモフォロジー演算を用いて特定の方向を向いた線分に分解し、これらの線分をマージしてストロークを作成し、ストロークを文字切り出しの最小単位として文字切り出し候補を作成する方法が、”石寺他：「ストローク抽出に基づく文字切り出しの一手法」(信学ソ大、Ｄ−３４８、１９９６)”において提案されている。
【０００７】
【発明が解決しようとする課題】
しかし、文字切り出し候補作成のために、これらの技術を利用してストロークを抽出すると、いずれの方法もストロークの方向成分を量子化しているために、図２のように量子化された角度よりも小さな角度変化を伴って二つの直線が接触している場合、二つの直線を分離することが困難である。図２は縦書きされた文字列の一部であり「ノ」と「十」が接触している例である。
【０００８】
また、文字認識のための特徴としてストロークを用いる際にも、ストロークの方向成分の分解能を向上させることは、認識精度を向上させるためにも重要である。つまり、ストローク抽出における課題の一つとしてストロークの方向成分の分解能向上が挙げられる。
【０００９】
また、従来から提案されているストローク抽出方法によると、いずれの方式も黒画素の連結性を前提とした処理であるために、図２のように文字ストロークがかすれている(とぎれている)場合にかすれた箇所が消失してしまったり、方向成分が特定できない問題があった。つまり、ストローク抽出における二つ目の課題として、文字のかすれに頑健なストローク抽出の実現が挙げられる。
【００１０】
さらに、文字線幅の変化への対応に関しても課題であると言える。特開昭５７−１９９０７５号公報の方式では、画素群を特定の方向に走査する処理によって線幅の太い箇所でも方向成分を特定可能であるが、モフォロジー演算を用いた方法によると、図２のように線幅が一つのパターン内で大きく変動する場合に、線幅の細い部分が消失してしまったり、逆に線幅の太い部分でストロークの方向成分を特定できない等の問題がある。
【００１１】
さて、方向成分の分解能を高めることに対しては、例えば、”窪田：「ストローク方向抽出フィルタを用いた手書き数字認識」(信学技報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)によってデータから推定できることが知られている。
【００３５】
ここで、本発明において文字パターンを正規分布の重ね合わせと考えることの意義を詳しく述べる。文字パターンを正規分布の重ね合わせと考えると、ストロークは一つ一つの正規分布であると考えることができる。つまり、ストロークを抽出することを、正規分布のパラメータを推定することとして考えることが可能になる。
【００３６】
このように、ストロークを混合正規分布の中のある一つの正規分布であると考えれば、共分散行列の中に線幅の表現が含まれているので、共分散行列を推定することは線幅の推定を含んでいることになる。よって、線幅の変化に追従することが可能になり、線幅の変化や線幅の多様性によらずストロークを抽出可能になる。方向成分についても、共分散行列の第一固有ベクトルが方向成分を表すので、共分散行列を推定することは方向成分の推定を含んでいる。さらに、共分散行列の第一固有ベクトルとして表される方向成分は連続的に定義可能であり、量子化誤差を心配する必要がない十分な方向分解能が得られる。
【００３７】
また、本方式によれば、従来のように黒画素がある方向に連結している長さを計測するのではなく、黒画素の連結性をもともと仮定しないで、黒画素は独立に生起すると仮定して、関数の値が緩やかに減少する性質を持つ関数である正規分布を利用して広い範囲でのデータの規則性を抽出しているために、かすれがある場合にも柔軟に対応が可能になる。
【００３８】
混合正規分布はベクトルχを入力とすると、以下のように定義される。
【００３９】
ただし、
式（１）のＬは正規分布の数である。一つ一つの正規分布のことを正規分布モデルと呼ぶ。ここで、ｆiはｉ番目の正規分布モデルであり、μiはｉ番目の正規分布モデルの中心を表すベクトル、Σiはｉ番目の正規分布モデルの共分散行列、Ｐｒiはｉ番目の正規分布モデルの混合比であり、ΣiＰｒi＝１を満たす。つまり、式（１）で表される混合正規分布は、Ｌ個の正規分布モデルの重ね合わせによってχを表現しており、各正規分布モデル毎に、中心と共分散と混合比の３つのパラメータを持つことになる。また、ｄは次元数であり、この場合２である。また、ベクトルの右肩の添字Ｔは転置を意味する。さらに｜Σ｜はΣの行列式を表し、行列の右肩の添字−１は、逆行列を意味する。
【００４２】
混合正規分布におけるパラメータ推定には、例えばＥＭアルゴリズムを用いればよい。他にも、例えば”上田他：「混合モデルのための併合分割操作付きＥＭアルゴリズム」(信学論、vol.J82-D-II、No.5、pp930-940、1999)”に記載の方法を用いることもできる。また、併合分割操作付きＥＭアルゴリズムを用いる場合、併合分割基準として、文献(混合モデルのための併合分割操作付きＥＭアルゴリズム)の基準だけでなく、例えば共分散行列の行列式の値が小さい正規分布モデルを中心間距離の最も近い正規分布モデルに併合し、行列式の値の大きい正規分布モデルを分割するような基準を用いることもできる。
【００４３】
また、ＥＭアルゴリズムによってパラメータを推定する際に、混合比Ｐｒiと各正規分布モデルの中心μiは通常のＥＭアルゴリズムによって求めて、共分散行列は回転方向と分散の成分にわけてそれぞれを推定することも考えられる。その場合は、以下の手続きによって推定式を導出すれば、容易に推定が可能である。
【００４４】
まず、共分散行列の逆行列を回転を表す変換を用いて、あらかじめ対角化された形式で表現する。
【００４５】
ここで、共分散行列を式（３）のように表現すると、共分散行列をθとλ1、λ2の関数として考えることができるので表記としてΣ(θ,λ1,λ2)という形にしている。以降は、共分散行列の回転方向だけを推定するのでΣ(θ)と表記する。
【００４７】
さて、ＥＭアルゴリズムにおけるＱ関数は、Ｎ個の学習データχk(ｋ＝1,2,…,Ｎ)が与えられたとすると、以下のとおりである。
【００４８】
ここで、式（５）の第二項は以下の通りである。
【００５０】
ここで、Ｌは正規分布モデルの数、Ｎは与えられたデータの数、ψiはｉ番目の正規分布モデルのパラメータのうち、特に中心と共分散行列を意味する。また、Φはパラメータを推定する前の値であり、Φ′は新たに推定し直したパラメータの値を意味する。学習の最初のステップではΦにはあらかじめ初期値を代入する。この初期値は、混合比の条件と共分散行列の正定値の条件を満たせばランダムな数値でもよい。
【００５２】
パラメータΣの学習に関係する部分は式（５）の第二項である。この項を最大化するには、以下の式でψi′による微分がゼロになるようパラメータを更新すればよい。
【００５３】
正規分布の混合モデルでは、ｆｉ(χｋ｜ψｉ′)は、式（２）で表されるので、
Σ（θi′）の行列式の値はθi′の変化に対して不変であること、また回転成分だけを推定する場合、∇ψi′は∇θi′と置けばよいことに注意すると以下を得る。
【００５６】
ここで、
【００５８】
式（１０）を式（９）に代入して、
これを式（７）に代入して、
【００６０】
いま、
【００６１】
ゆえに、以下を得る。
【００６３】
同様にして、λ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以上ならば、白画素を黒画素に置き換えることによって、かすれを補間することが可能になる。この際、式（１）の値は０．１以上と限定する必要はなく、例えば０から１．０の間で自由に閾値を設定することが可能である。
【０１０４】
なお、上記実施例では、ストローク抽出装置及びストローク抽出方法について記載したが、本発明には上記ストローク抽出方法をコンピュータで実現するためのプログラムを記録した記録媒体も含まれ、ＨＤ、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等の任意の記録媒体を用いて、上記方法をコンピュータで実現することができる。
【０１０５】
【発明の効果】
以上説明したように、本発明のストローク抽出装置によれば、文字パターンを混合正規分布と考え、共分散行列の中に線幅と方向成分を表現し、両者を推定するので線幅の変動にも柔軟に対応でき、ストロークの方向成分に対する高い分解能を持つストローク抽出を行うことができ、関数の値が緩やかに減少する性質を持つ関数である正規分布を利用して広い範囲でのデータの規則性を抽出しているため、かすれがある場合にも柔軟に対応が可能になり、安定してストローク抽出を行うことが可能である。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係るストローク抽出装置の構成を示すブロック図である。
【図２】接触と文字線幅の変動とかすれを伴う文字の例を示す図である。
【図３】入力画像の例を示す図である。
【図４】一般的に用いられるパターン表現の例を示す図である。
【図５】ストローク推定用データの例を示す図である。
【図６】入力画像の例を示す図である。
【図７】距離変換した画像の例を示す図である。
【図８】ストローク推定用データの例を示す図である。
【図９】混合正規分布推定部の動作を説明する図である。
【図１０】本発明の装置に入力される文字パターンの例である。
【図１１】図１０の例に対応したストローク推定用データの例を示す図である。
【図１２】混合正規分布推定部のフローチャートの例を示す図である。
【図１３】混合正規分布推定部で設定された初期値の例を示す図である。
【図１４】図１０の例に対応した三つの正規分布モデルによる混合正規分布表現特徴の例を示す図である。
【図１５】図１０の例に対応した三つの正規分布モデルによる混合正規分布表現特徴の二次元空間上の様子を示す図である。
【図１６】図１２のＳＴ１４の処理に関するフローチャートの例を示す図である。
【図１７】図１０の例に対応した四つの正規分布モデルによる混合正規分布表現特徴の例を示す図である。
【図１８】図１０の例に対応した四つの正規分布モデルによる混合正規分布表現特徴の二次元空間上の様子を示す図である。
【図１９】図１０の例に対応したストローク情報の例を示す図である。
【図２０】図１０の例に対応したストローク情報の例を示す図である。
【図２１】ストローク抽出部のフローチャートの例を示す図である。
【符号の説明】
１１ 文字列画像記憶部
１２ ストローク推定用データ作成部
１３ 混合正規分布推定部
１４ ストローク抽出部[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an apparatus, a method, and a storage medium for decomposing a character pattern into partial patterns from an optically scanned character string image, and in particular, a stroke extracting apparatus, a stroke extracting method, and a stroke extracting program for decomposing characters into strokes. The present invention relates to a recording medium on which is recorded.
[0002]
[Prior art]
Stroke extraction is often used in the case of character recognition by reading a character string written on a mail piece or a form with an optical character reader (OCR). For example, as a feature amount for recognizing a character, it is known that it is very effective to decompose a character pattern into strokes having direction components, and this is a widely used technique.
[0003]
Japanese Patent Laid-Open No. 57-199075 proposes a technique for extracting a stroke from a handwritten character as a feature when recognizing a character. In this technique, the first step of attaching a direction code corresponding to the continuous direction to each black pixel of the pattern area after character cut-out, and scanning the pattern area in a different direction for each direction code in each direction The second step of examining the connectivity for each code and extracting the connected pixel group of the same direction code as a stroke. In the second step, a process of monitoring the intersection of strokes is performed, and the intersected strokes can be extracted as separate strokes.
[0004]
On the other hand, when a character string written on a mail piece or a form is read, pre-processing is performed prior to recognition processing. In this pre-processing, several character cut-out candidates that are candidates for cutting out one character are obtained. It is done.
[0005]
Conventionally, in the generation of such a character segmentation candidate, when a character string image is given, a character pattern is obtained using a connected component of black pixels or a projection function obtained by projecting black pixels in the vertical direction of the character string. The character cutout candidate is generated by creating a minimum unit of and combining several of these minimum units. Furthermore, even when character patterns are in contact with each other, stroke extraction is used to generate a character segmentation candidate including a correct answer.
[0006]
As a stroke extraction method for generating character segmentation candidates, a character string image is decomposed into line segments facing a specific direction using a morphological operation, and the strokes are created by merging these line segments. A method of creating a character cutout candidate as a minimum cutout unit is proposed in “Ishidera et al .:“ A Method of Character Cutout Based on Stroke Extraction ”(Shingaku Sodai, D-348, 1996)”.
[0007]
[Problems to be solved by the invention]
However, when a stroke is extracted using these techniques for creating a character extraction candidate, both methods quantize the directional component of the stroke. When two straight lines are in contact with a small angle change, it is difficult to separate the two straight lines. FIG. 2 shows an example in which “no” and “ten” are part of a vertically written character string.
[0008]
Also, when using a stroke as a feature for character recognition, improving the resolution of the stroke direction component is important for improving recognition accuracy. That is, one of the problems in stroke extraction is improving the resolution of stroke direction components.
[0009]
In addition, according to the conventionally proposed stroke extraction method, since each method is processing based on the black pixel connectivity, the character stroke is blurred (disconnected) as shown in FIG. There was a problem that the faint part disappeared or the direction component could not be specified. That is, the second problem in stroke extraction is the realization of stroke extraction that is robust against blurring of characters.
[0010]
Furthermore, it can be said that it is a problem with respect to the change in the character line width. In the method disclosed in Japanese Patent Laid-Open No. 57-199075, the direction component can be specified even at a portion having a large line width by the process of scanning the pixel group in a specific direction. However, according to a method using a morphological operation, FIG. Thus, when the line width largely fluctuates within one pattern, there is a problem that the thin line width portion disappears or the stroke direction component cannot be specified by the thick line width portion.
[0011]
In order to increase the resolution of the direction component, for example, the method proposed in “Kubota:“ Handwritten digit recognition using a stroke direction extraction filter ”(Science Technical Report PRMU 98-164, 1998)” is used. However, according to this method, the size of the directional filter is determined in advance, and the corresponding line width determines the size of the filter. It is difficult to cope with various line widths because it is decided at the time, and the filter is applied only to the local range, so the direction is not used in the area where the black pixels do not exist densely around the filter. This means that the component cannot be specified at all, and it is difficult to obtain the direction at a place with faintness as shown in FIG.
[0012]
As for fading, see “Hirano et al .:“ Low-quality printed character recognition using contour zero-crossing features and canonical discriminant analysis ”” (Science Technical Report PRMU 98-159, 1998) ”. A method has been proposed to determine the outline shape of a character and to determine the degree of expansion direction contribution, but this method is not a method to directly determine the stroke, but a method to determine the outline feature of the character, and sufficient resolution in the angular direction. There is a problem that is not.
[0013]
As described above, with the conventionally known stroke extraction method, it is difficult to satisfy simultaneously high resolution in the angular direction, robustness against fluctuations in line width, and identification of the direction component in a blurred place. is there.
[0014]
The present invention has been made in view of the above problems, and its main purpose is to have a high directional component resolution with respect to the stroke, to flexibly cope with fluctuations in the line width, and to be stable even in a blurred place. An object of the present invention is to provide a stroke extraction device, a stroke extraction method, and a recording medium on which a stroke extraction program is recorded.
[0015]
[Means for Solving the Problems]
In order to achieve the above object, a stroke extracting apparatus of the present invention is a stroke extracting apparatus that extracts a character pattern from a character string image by dividing the character pattern into strokes, and inputs and stores an optically scanned character string image. A sequence image storage unit, a stroke estimation data creation unit that extracts stroke estimation data from the character string image, a mixed normal distribution estimation unit that creates a mixed normal distribution expression feature from the stroke estimation data, and the mixed normal A stroke extraction unit that outputs stroke information from the distribution expression feature.The mixed normal distribution expression feature includes the number of normal distributions in the mixed normal distribution, the center of each normal distribution, the covariance, and the mixing ratio. In the mixed normal distribution estimation unit, the character pattern is normalized. Expressed as a superposition of distributions, the stroke extraction unit extracts the strokes of the character pattern by superimposing the normal distributionsIs.
[0016]
In the present invention, the stroke estimation data is a two-dimensional coordinate value corresponding to the frequency of a two-dimensional coordinate value of a black pixel of the character string image or a distance conversion of the character string image. It can be set as the structure which consists of a coordinate value.
[0018]
In the present invention, it is preferable that the parameter of the normal distribution is estimated using an EM algorithm.
[0020]
The stroke extraction method of the present invention is a stroke extraction method for decomposing and extracting a character pattern from a character string image into strokes, and inputting and storing an optically scanned character string image; A stroke estimation data creation step for extracting stroke estimation data from the character string image; a mixed normal distribution estimation step for creating a mixed normal distribution expression feature from the stroke estimation data; and a stroke from the mixed normal distribution expression feature A stroke extraction step for outputting information.Thus, the mixed normal distribution expression feature includes the number of normal distributions in the mixed normal distribution, the center of each normal distribution, the covariance, and the mixing ratio. In the mixed normal distribution estimation step, the character pattern is Expressed as superposition of normal distribution, and in the stroke extraction step, the stroke of the character pattern is extracted by superposition of the normal distributionIs.
[0022]
The present invention also includes a recording medium on which a program for causing a computer to execute the stroke extraction method is recorded.
[0023]
Thus, the present invention considers the character pattern as a mixed normal distribution, expresses the line width and the direction component in the covariance matrix, and estimates both, so that the present invention can flexibly cope with fluctuations in the line width. In addition, stroke extraction having high resolution with respect to the direction component of the stroke can be performed. In addition, since regularity of data is extracted using a normal distribution, which is a function whose function value gradually decreases, it is possible to flexibly cope with blurring. , Stable stroke extraction can be performed.
[0024]
DETAILED DESCRIPTION OF THE INVENTION
Next, a stroke extraction device and a stroke extraction method according to an embodiment of the present invention will be described in detail with reference to the drawings.
[0025]
FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. The embodiment shown in FIG. 1 includes a character string
[0026]
Next, the operation of the present embodiment will be described. The character string
[0027]
The stroke estimation
[0028]
For example, if a 4 × 4 image pattern is input as shown in FIG. 3, it is expressed as a 4 × 4 matrix in a general technique as shown in FIG. Then, using the values of i and j of the element whose (i, j) element is 1 in the matrix of FIG. 4, it is assumed that the two-dimensional data is collected by the number of black pixels as shown in FIG. This can be used as stroke estimation data. That is, when character recognition is performed, a character pattern is usually handled as an N × M matrix and is generally handled as one point in an N × M dimensional space. However, in the present invention, one black pixel is used. On the other hand, the two-dimensional coordinates are given as stroke estimation data. Therefore, the character pattern is a set of points on the two-dimensional space.
[0029]
As another realization method, for example, it is also possible to perform distance conversion on the input image in advance, create the two-dimensional data by considering the distance value as the data occurrence frequency, and input to the present method. That is, when a pattern as shown in FIG. 6 is given as an example of the original image, an image obtained by distance-converting the pattern is shown in FIG. 7, and the data shown in FIG. 8 can be given as stroke estimation data.
[0030]
The mixed normal
[0031]
For example, considering that the stroke is approximated as a normal distribution, a normal distribution can be extracted from the data for stroke extraction using a two-dimensional mixed normal distribution estimation method to obtain a stroke. In the example of FIG. 9, when stroke extraction data is input as x marks, these can be expressed as a superposition of two-dimensional normal distributions (displayed by dotted lines), and one normal distribution Can be extracted as one stroke.
[0032]
Here, the significance and details of a method of considering a character pattern as a mixed model of a two-dimensional normal distribution will be described. A character pattern can be considered as a set of black pixels generated independently according to a certain two-dimensional probability distribution. In this way, expressing a character pattern can be considered as a problem of estimating a two-dimensional probability distribution.
[0033]
Originally, it is more realistic to think that black pixels of handwritten character patterns do not occur independently (separately) and occur with some kind of chronological order, but in OCR, writing order, writing direction, etc. It is safe to think in this way because the time-series state cannot be observed. For example, even if each black pixel occurs separately, it can be said that it is perceived as a single character when a human finally sees it. In another example, it is not clear how the ink permeates into the paper when the stamp is pressed using a rubber stamp, etc., but when a human finally sees it, one character It can be said that there is no problem because it is perceived as.
[0034]
In general, many probability distributions can be expressed by a mixed normal distribution. Assuming that a character pattern is a mixed model of a two-dimensional normal distribution, the line width and direction component of a local character line can be naturally expressed in the covariance matrix that is a parameter of the two-dimensional normal distribution. It becomes possible. When a two-dimensional (2 × 2) covariance matrix is decomposed into eigenvalues and eigenvectors, the first eigenvector represents the stroke direction, the first eigenvalue represents its length, the second eigenvector represents the line width direction, and the second eigenvalue. This is because can be considered to represent the line width. The parameters of the mixed normal distribution are derived from the data by the EM algorithm (Dempster et al. “Maximum likelihood from incomplete data via the EM algorithm,” J. Roy. Statist. Soc. B, vol. 39, pp. 1-38, 1977). It is known that it can be estimated.
[0035]
Here, the significance of considering a character pattern as a superposition of a normal distribution in the present invention will be described in detail. If the character pattern is considered as a superposition of normal distributions, the stroke can be considered as a single normal distribution. That is, extracting a stroke can be considered as estimating a parameter of a normal distribution.
[0036]
In this way, if the stroke is considered as one normal distribution in the mixed normal distribution, the representation of the line width is included in the covariance matrix. Will include an estimate of. Therefore, it becomes possible to follow the change of the line width, and the stroke can be extracted regardless of the change of the line width and the diversity of the line width. For the direction component as well, since the first eigenvector of the covariance matrix represents the direction component, estimating the covariance matrix includes estimation of the direction component. Furthermore, the direction component represented as the first eigenvector of the covariance matrix can be defined continuously, and sufficient direction resolution can be obtained without having to worry about quantization errors.
[0037]
Also, according to this method, instead of measuring the length of black pixels connected in a certain direction as in the prior art, it is assumed that black pixels occur independently without originally assuming black pixel connectivity. Since the regularity distribution, which is a function with a function value that gradually decreases, is used to extract data regularity over a wide range, it is possible to flexibly cope with blurring. become.
[0038]
The mixed normal distribution is defined as follows when the vector χ is input.
[0039]
However,
L in Equation (1) is the number of normal distributions. Each normal distribution is called a normal distribution model. Where fiIs the i th normal distribution model and μiIs a vector representing the center of the i th normal distribution model, ΣiIs the covariance matrix of the i th normal distribution model, PriIs the mixing ratio of the i th normal distribution model, and ΣiPri= 1 is satisfied. That is, the mixed normal distribution represented by Equation (1) expresses χ by superimposing L normal distribution models, and for each normal distribution model, three parameters of the center, the covariance, and the mixing ratio are used. Will have. D is the number of dimensions, and is 2 in this case. The subscript T on the right shoulder of the vector means transposition. Further, | Σ | represents a determinant of Σ, and the subscript −1 at the right shoulder of the matrix means an inverse matrix.
[0042]
For example, an EM algorithm may be used for parameter estimation in the mixed normal distribution. In addition, for example, the method described in “Ueda et al .:“ EM Algorithm with Merge and Split Operation for Mixed Models ”(Science Theory, vol.J82-D-II, No.5, pp930-940, 1999)” In addition, when using an EM algorithm with a merge partition operation, not only the standard of the literature (EM algorithm with merge partition operation for a mixed model) but also a determinant of a covariance matrix, for example, can be used. A normal distribution model with a small value of can be merged with a normal distribution model with the closest distance between the centers, and a standard that divides the normal distribution model with a large determinant value can also be used.
[0043]
Further, when the parameter is estimated by the EM algorithm, the mixture ratio PriAnd the center μ of each normal distribution modeliIs obtained by a normal EM algorithm, and the covariance matrix may be estimated by dividing into a rotation direction and a variance component. In that case, the estimation can be easily performed by deriving the estimation formula by the following procedure.
[0044]
First, the inverse matrix of the covariance matrix is expressed in a diagonalized form in advance using a transformation representing rotation.
[0045]
Here, when the covariance matrix is expressed as in Expression (3), the covariance matrix is expressed as θ and λ.1, Λ2Can be considered as a function of Σ (θ, λ1, λ2). Henceforth, since only the rotation direction of a covariance matrix is estimated, it describes with (SIGMA) ((theta)).
[0047]
Now, the Q function in the EM algorithm is N pieces of learning data χkIf (k = 1, 2,..., N) is given, it is as follows.
[0048]
Here, the second term of Formula (5) is as follows.
[0050]
Where L is the number of normal distribution models, N is the number of given data, ψiMeans the center and the covariance matrix among the parameters of the i-th normal distribution model. Further, Φ is a value before the parameter is estimated, and Φ ′ means a newly estimated parameter value. In the first step of learning, an initial value is substituted in advance for Φ. This initial value may be a random numerical value as long as the mixing ratio condition and the positive definite condition of the covariance matrix are satisfied.
[0052]
The part related to the learning of the parameter Σ is the second term of Equation (5). To maximize this term, ψiWhat is necessary is just to update a parameter so that the differentiation by ′ becomes zero.
[0053]
For a normally distributed model, fi(χk| Ψi′) Is expressed by equation (2).
Σ (θiThe determinant value of ′) is θiIf it is invariant to changes in ′ and only the rotational component is estimated, ∇ψi′ Is ∇θiNote that we can put ′ to get
[0056]
here,
[0058]
Substituting equation (10) into equation (9),
Substituting this into equation (7),
[0060]
Now
[0061]
So we get:
[0063]
Similarly, λi 1As the first eigenvalue of the i th normal distribution modeli 1Differentiating equation (8) by ′ yields:
[0065]
here,
Substituting this into equation (7)
[0068]
As explained so far, by learning separately the angular direction and variance components, for example, the center component and the angular direction are estimated while keeping the spread components of all normal distribution models fixed, simplifying the learning. It is possible to improve the processing speed and reduce the problem of convergence to the local optimal solution.
[0069]
Further, how to select the number of models is also a problem. For example, it is possible to select the number of models that gives the best value with respect to the information amount standard such as AIC or MDL. The character pattern is expressed as a mixed normal distribution, and the number of normal distribution models, which are parameters of the mixed normal distribution, and the center, covariance, and mixing ratio for each normal distribution model are output as mixed normal distribution expression characteristics.
[0070]
Next, the
[0071]
In order to construct the stroke information, for example, one stroke can be extracted as a product of one normal distribution model and the mixture ratio. If it demonstrates in figure, in FIG. 9, the inputted character pattern is expressed as a superposition of five normal distribution models of Gaussian1, Gaussian2, Gaussian3, Gaussian4, and Gaussian5. As stroke information as the output of the stroke extraction unit, for example, five normal distribution models from Gaussian 1 to Gaussian 5 can be output as separate stroke information.
[0072]
The stroke information as output of the stroke extraction unit not only associates one normal distribution model with one stroke, but also extracts several normal distribution models and their multiplication ratios as one stroke. It is also possible to do. That is, as another output method, for example, Gaussian1 is output as the first stroke, the overlap of Gaussian2 and Gaussian5 is output as the second stroke, and Gaussian3 and Gaussian4 are output as the third stroke. it can.
[0073]
When a superposition of several normal distribution models is extracted as one stroke, several methods can be considered as an implementation method. For example, with respect to an arbitrary pair of normal distribution models, a mutual center vector and a covariance matrix are considered as superposition evaluation features. At this time, the center vector is two-dimensional, and since the covariance matrix is a symmetric matrix, it has three values of two diagonal elements and one non-diagonal element, so the overlay evaluation feature is a 10-dimensional vector. This overlay evaluation feature can be statistically evaluated to determine whether it should be output as a single stroke.
[0074]
In this case, the superimposition evaluation feature teacher data obtained from a pair of normal distribution models to be integrated into one stroke is given as learning data in advance by humans, and a normal distribution model that should not be integrated into one stroke is given. Whether or not to output as one stroke can be determined by using a neural network having a multilayer perceptron learned by backpropagation by giving 0 as superimposition evaluation feature teacher data obtained from the pair.
[0075]
This neural network can use, for example, a three-layer perceptron. The input layer has ten neurons having the same number of dimensions as the overlay evaluation feature, the intermediate layer has five neurons, and the output layer has one. The number of neurons in the intermediate layer can be set to any number between 2 and 1000. In addition, a method such as discriminant analysis or multiple regression analysis can be used instead of the neural network.
[0076]
The specific procedure for the determination is, for example, when an overlay evaluation feature is input to a learned neural network, and if the output is 0.5 or more, it is determined that it should be output as one stroke. Can be determined not to be output as one stroke. The same determination can be made when multiple regression analysis is used. In the case of discriminant analysis, the discriminant score is used to determine that the discriminant score should be output as a single stroke if the discriminant score is equal to or greater than a predetermined threshold, and otherwise it should not be output as a single stroke. Can be determined.
[0077]
In addition, it can be easily realized by using a method described in, for example, “Japanese Patent Application No. 08-122333, Character Extraction Candidate Generation Device”.
[0078]
【Example】
In order to describe the above-described embodiment of the present invention in more detail, the operation of a specific example of the present invention will be described in detail.
[0079]
FIG. 10 is an example of a character pattern image input to the stroke extracting apparatus of the present invention. This character pattern has 221 black pixels. A character pattern as shown in FIG. 10 is input from the character string
[0080]
An example is shown in FIG. In this operation, a normal raster scan is performed on the input character string image, and when the target pixel is a black pixel, the coordinate information may be output. The mixed normal
[0081]
A series of operations in the mixed normal
[0082]
The processes from ST11 to ST12 in the flowchart are processes for determining how many models are set. When the stroke estimation data is input, the number of input data is counted in ST11. In the case of the input image shown in FIG. 10, the number of input stroke estimation data (FIG. 11) is counted as 221. In ST12, a process for determining the number of normal distribution models is performed. In this determination process, the number of models can be set by outputting, for example, an integer obtained by dividing the number of data counted in ST11 by 70. That is, when the input image is the example of FIG. 10, the number of data 221 of the input stroke estimation data (FIG. 11) is divided by 70 to be 3, which is 11, so in this case the number of models is 3 Set to
[0083]
In ST13, the initial value is set in response to the number of models set in ST12. FIG. 13 shows an example in which the number of models is given as three and random initial values are given as parameters of the normal distribution model. As in this example, a unit matrix can be given to the covariance matrix of each normal distribution model. Moreover, the mixture ratio of each normal distribution model can give a constant value with respect to all the models.
[0084]
In ST14, the stroke estimation data shown in the example of FIG. 11 and the initial value shown in the example of FIG. 13 are given, and the parameter of the mixed normal distribution is estimated. The parameter estimation of the mixed normal distribution may be adjusted so as to maximize the likelihood based on the stroke estimation data, and a normal EM algorithm or SMEM algorithm may be applied. In ST15, the parameter estimated in ST14 is output as a mixed normal distribution expression feature as in the example shown in FIG. The example of FIG. 14 is a result of expressing the input pattern of FIG. 10 as a mixed distribution using three normal distribution models. FIG. 15 shows the three normal distributions in a two-dimensional space.
[0085]
Further, ST14 can be realized not by a normal EM algorithm or SMEM algorithm but by a flowchart as shown in FIG.
[0086]
In ST21, the covariance matrix of each normal distribution model is expressed as in Expression (3).
[0087]
In ST22, similar to the normal EM algorithm and SMEM algorithm, the mixture ratio Pr of each normal distribution modeli′ And center μi′ Is estimated.
[0088]
Next, in ST23, θ when the covariance equation is expressed in the form of Equation (3).i′ Is estimated. This estimation is obtained by equation (15).
[0089]
In ST24, λ when the covariance equation is expressed in the form of Equation (3).i1′ Is estimated. This estimation is obtained by equation (19).
[0090]
ST25 to ST27 are processes for making the values of the second eigenvalues constant in all normal distribution models. Λ for all normal distribution modelsi2′ And the average value is λ2Λ of each normal distribution modeli2If ′ is the same value as the initial value, λ2Is not set. If λ2If is set, the process proceeds to ST28, but λ2If is not set, the process proceeds to ST26.
[0091]
In ST26, λ when the covariance equation is expressed in the form of the equation (3).i2′ Is estimated. This estimation is obtained by equation (19).
[0092]
In ST27, λ for all normal distribution modelsi2Mean value λ2For each normal distribution modeli2The value of ′ is λ2Replace with
[0093]
In ST28, Pri′ And μi′ And θi′ And λi1′ And λ2′ For each new mixed normal distribution parameter PriAnd λi 1And θiAnd λi 1And λ2To find the log likelihood.
[0094]
In ST29, it is determined that the process has converged when the increasing rate of the log likelihood becomes smaller than a predetermined threshold value, and the process ends. Otherwise, the process returns to ST22 again. In ST12 of FIG. 12, the method for setting the number of normal distribution models does not need to be fixed to an integer obtained by dividing the number of data by 70, and an integer obtained by dividing the number of data by an arbitrary integer from 2 to 1000 is given. You can also Furthermore, when determining the optimal number of mixtures, for example, a plurality of normal distribution models are set, and the mixed normal distribution in the case of each normal distribution model number is estimated, and at the same time, an information criterion such as AIC or MDL is set. It is also possible to determine and determine the number of normal distribution models that give the best information amount standard such as AIC and MDL.
[0095]
When the best number of normal distribution models is determined by MDL for the example of FIG. 10, the number of normal distribution models is three as in the examples shown in FIGS. Further, when the best number of normal distribution models is determined by AIC in the example of FIG. 10, the number of normal distribution models is four. FIG. 17 shows the mixed normal distribution expression characteristics at that time, and FIG. 18 shows the two-dimensional space.
[0096]
Further, as shown in the flowchart of FIG.2Is the same value for all normal distribution models, and when the line width of the input character string image is almost constant, there is a function to reduce the number of parameters to be estimated by one, which speeds up the processing. Enable.
[0097]
The
[0098]
Also, other output formats can be considered as output formats. That is, when a mixed normal distribution expression feature as shown in FIG. 14 or FIG. 17 is input, the overlay evaluation feature should be statistically evaluated for an arbitrary pair of normal distribution models and output as one stroke. Are determined as strokes. For example, when the input as in the example of FIG. 14 is evaluated as to whether it should be output as one stroke using a neural network, the output is 0. 0 for any pair of normal distribution models. If there is no pair of normal distribution models determined to be output as one stroke, the output is the same as that shown in FIG.
[0099]
On the other hand, when the same evaluation is performed on the input of FIG. 17 using a neural network, the value is 0.9 for the second and third normal distribution model pairs, and the output is 0 for the other pairs. When it is determined that only one pair of the second and third normal distribution models should be output as one stroke, an output as shown in FIG. 20 is obtained.
[0100]
This process is described with reference to a flowchart in FIG. In ST31, paying attention to one normal distribution model, in ST32, it is determined whether or not the target normal distribution model and the other normal distribution models should have the same stroke. This determination can be made by statistical determination. For example, with respect to an arbitrary pair of normal distribution models, a mutual center vector and a covariance matrix are considered as superposition evaluation features.
[0101]
At this time, the center vector is two-dimensional, and since the covariance matrix is a symmetric matrix, it has three values of two diagonal elements and one non-diagonal element, so the overlay evaluation feature is equivalent to (2 + 3) × 2 models, that is, It becomes a 10-dimensional vector. This overlay evaluation feature can be statistically evaluated to determine whether it should be output as a single stroke.
[0102]
In this case, the superimposition evaluation feature teacher data obtained from a pair of normal distribution models to be integrated into one stroke is given as learning data in advance by humans, and a normal distribution model that should not be integrated into one stroke is given. It is possible to determine whether to output as one stroke by using a neural network learned by giving 0 as superimposition evaluation feature teacher data obtained from the pair. In addition, a method such as discriminant analysis or multiple regression analysis can be used instead of the neural network. This process is performed for all normal distribution models, and the normal distribution model that is finally determined to be output as the same stroke is output as one stroke, and if not, one normal distribution model is Output as one stroke.
[0103]
In addition, as an output of the
[0104]
In the above embodiment, the stroke extraction device and the stroke extraction method are described. However, the present invention includes a recording medium on which a program for realizing the stroke extraction method by a computer is recorded, such as HD, CD-ROM, The above method can be realized by a computer using an arbitrary recording medium such as MO or DVD.
[0105]
【The invention's effect】
As described above, according to the stroke extracting device of the present invention, the character pattern is considered as a mixed normal distribution, the line width and the direction component are expressed in the covariance matrix, and both are estimated. Can be used flexibly, can perform stroke extraction with high resolution for the direction component of the stroke, and uses a normal distribution, which is a function that has a property of gradually decreasing the value of the function, to regulate data in a wide range Therefore, it is possible to flexibly cope with blurring, and it is possible to stably extract strokes.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a stroke extracting apparatus according to an embodiment of the present invention.
FIG. 2 is a diagram illustrating an example of a character with contact, fluctuation in character line width, and blurring.
FIG. 3 is a diagram illustrating an example of an input image.
FIG. 4 is a diagram showing an example of a pattern expression generally used.
FIG. 5 is a diagram illustrating an example of stroke estimation data.
FIG. 6 is a diagram illustrating an example of an input image.
FIG. 7 is a diagram illustrating an example of a distance-converted image.
FIG. 8 is a diagram illustrating an example of stroke estimation data.
FIG. 9 is a diagram illustrating the operation of a mixed normal distribution estimation unit.
FIG. 10 is an example of a character pattern input to the apparatus of the present invention.
11 is a diagram illustrating an example of stroke estimation data corresponding to the example of FIG.
FIG. 12 is a diagram illustrating an example of a flowchart of a mixed normal distribution estimation unit.
FIG. 13 is a diagram illustrating an example of initial values set by a mixed normal distribution estimation unit.
14 is a diagram illustrating an example of a mixed normal distribution expression feature using three normal distribution models corresponding to the example of FIG.
15 is a diagram illustrating a state in a two-dimensional space of mixed normal distribution expression features by three normal distribution models corresponding to the example of FIG.
FIG. 16 is a diagram showing an example of a flowchart regarding the processing of ST14 in FIG. 12;
FIG. 17 is a diagram illustrating an example of a mixed normal distribution expression feature based on four normal distribution models corresponding to the example of FIG.
FIG. 18 is a diagram showing a state in a two-dimensional space of mixed normal distribution expression features by four normal distribution models corresponding to the example of FIG.
19 is a diagram illustrating an example of stroke information corresponding to the example of FIG.
20 is a diagram illustrating an example of stroke information corresponding to the example of FIG.
FIG. 21 is a diagram illustrating an example of a flowchart of a stroke extraction unit.
[Explanation of symbols]
11 Character string image storage
12 Stroke estimation data generator
13 Mixed normal distribution estimator
14 Stroke extraction unit
Claims (15)
光学的に走査された文字列画像を入力して記憶する文字列画像記憶部と、前記文字列画像からストローク推定用データを抽出するストローク推定用データ作成部と、前記ストローク推定用データから混合正規分布表現特徴を作成する混合正規分布推定部と、前記混合正規分布表現特徴からストローク情報を出力するストローク抽出部と、を備え、
前記混合正規分布表現特徴として、該混合正規分布における、正規分布の数、及び各正規分布の中心と共分散と混合比とが含まれ、
前記混合正規分布推定部において、前記文字パターンが正規分布の重ね合わせとして表現され、
前記ストローク抽出部において、前記正規分布の重ね合わせにより前記文字パターンのストロークが抽出されることを特徴とするストローク抽出装置。In a stroke extraction device that extracts a character pattern from a character string image into strokes,
A character string image storage unit for inputting and storing an optically scanned character string image, a stroke estimation data creation unit for extracting stroke estimation data from the character string image, and a mixed normal from the stroke estimation data A mixed normal distribution estimation unit that creates a distribution expression feature; and a stroke extraction unit that outputs stroke information from the mixed normal distribution expression feature .
The mixed normal distribution expression features include the number of normal distributions in the mixed normal distribution, and the center, covariance and mixing ratio of each normal distribution,
In the mixed normal distribution estimation unit, the character pattern is expressed as a superposition of normal distributions,
The stroke extracting device, wherein the stroke extracting unit extracts a stroke of the character pattern by superimposing the normal distribution .
光学的に走査された文字列画像を入力して記憶する文字列画像記憶ステップと、前記文字列画像からストローク推定用データを抽出するストローク推定用データ作成ステップと、前記ストローク推定用データから混合正規分布表現特徴を作成する混合正規分布推定ステップと、前記混合正規分布表現特徴からストローク情報を出力するストローク抽出ステップと、を含み、
前記混合正規分布表現特徴として、該混合正規分布における、正規分布の数、及び各正規分布の中心と共分散と混合比とが含まれ、
前記混合正規分布推定ステップにおいて、前記文字パターンを正規分布の重ね合わせとして表現し、
前記ストローク抽出ステップにおいて、前記正規分布の重ね合わせにより前記文字パターンのストロークを抽出することを特徴とするストローク抽出方法。 In a stroke extraction method for extracting a character pattern from a character string image into strokes,
A character string image storing step for inputting and storing the optically scanned character string image, a stroke estimation data creating step for extracting stroke estimation data from the character string image, and a mixed normal from the stroke estimation data A mixed normal distribution estimation step for creating a distribution expression feature, and a stroke extraction step for outputting stroke information from the mixed normal distribution expression feature,
The mixed normal distribution expression features include the number of normal distributions in the mixed normal distribution, and the center, covariance and mixing ratio of each normal distribution,
In the mixed normal distribution estimation step, the character pattern is expressed as a superposition of normal distributions,
In the stroke extracting step, stroke extraction method and extracting the stroke of the character pattern by superposition of the normal distribution.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001025794A JP4737576B2 (en) | 2001-02-01 | 2001-02-01 | Stroke extraction device, stroke extraction method, and recording medium recording stroke extraction program |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001025794A JP4737576B2 (en) | 2001-02-01 | 2001-02-01 | Stroke extraction device, stroke extraction method, and recording medium recording stroke extraction program |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2002230483A JP2002230483A (en) | 2002-08-16 |
| JP4737576B2 true JP4737576B2 (en) | 2011-08-03 |
Family
ID=18890719
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001025794A Expired - Lifetime JP4737576B2 (en) | 2001-02-01 | 2001-02-01 | Stroke extraction device, stroke extraction method, and recording medium recording stroke extraction program |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP4737576B2 (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4483334B2 (en) * | 2004-02-18 | 2010-06-16 | 富士ゼロックス株式会社 | Image processing device |
| JP4571039B2 (en) * | 2005-07-28 | 2010-10-27 | 株式会社リコー | Information processing apparatus, information processing method, and program |
| JP5355769B1 (en) | 2012-11-29 | 2013-11-27 | 株式会社東芝 | Information processing apparatus, information processing method, and program |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2836579B2 (en) * | 1996-04-19 | 1998-12-14 | 日本電気株式会社 | Character segmentation candidate generation device |
| JP2000163395A (en) * | 1998-11-30 | 2000-06-16 | Nippon Telegr & Teleph Corp <Ntt> | Maximum likelihood estimation for mixed model and recording medium where maximum likelihood estimation program for mixed model is recorded |
-
2001
- 2001-02-01 JP JP2001025794A patent/JP4737576B2/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JP2002230483A (en) | 2002-08-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Rebelo et al. | Optical recognition of music symbols: A comparative study | |
| JP2005512201A5 (en) | ||
| JP2010134957A (en) | Pattern recognition method | |
| Chen et al. | Robust text line segmentation for historical manuscript images using color and texture | |
| Zois et al. | Hierarchical dictionary learning and sparse coding for static signature verification | |
| Deore et al. | A survey on offline signature recognition and verification schemes | |
| Elgammal et al. | A graph-based segmentation and feature extraction framework for Arabic text recognition | |
| Saikia et al. | Approaches and issues in offline signature verification system | |
| Riesen et al. | Reducing the dimensionality of dissimilarity space embedding graph kernels | |
| CN120783357A (en) | Chinese ancient book character recognition method and system based on image recognition technology | |
| Arab et al. | 1D-GAN for improving offline handwritten signature verification based on small sets of real samples | |
| Viard-Gaudin et al. | Recognition-directed recovering of temporal information from handwriting images | |
| JP4737576B2 (en) | Stroke extraction device, stroke extraction method, and recording medium recording stroke extraction program | |
| Zhou et al. | UFCNet: Unsupervised network based on Fourier transform and convolutional attention for oracle character recognition | |
| Woodley et al. | Tracking Using Online Feature Selection and a Local Generative Model. | |
| Ferrer et al. | Signature verification using local directional pattern (LDP) | |
| Saon | Cursive word recognition using a random field based hidden Markov model | |
| Assabie et al. | Hmm-based handwritten amharic word recognition with feature concatenation | |
| Ramanathan et al. | Robust feature extraction technique for optical character recognition | |
| Shao et al. | A character image restoration method for unconstrained handwritten Chinese character recognition | |
| Ouadid et al. | Tifinagh Character Recognition: A Survey | |
| Hanif | A Comprehensive Framework for Stroke Trajectory Recovery for Unconstrained Handwritten Documents | |
| van der Maaten et al. | Identifying the real van gogh with brushstroke textons | |
| Rodrigues et al. | Feature extraction using contour projection | |
| Fang et al. | Reduction of feature statistics estimation error for small training sample size in off-line signature verification |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20080111 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20110113 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20110121 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20110314 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20110408 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20110421 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 Ref document number: 4737576 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140513 Year of fee payment: 3 |
|
| EXPY | Cancellation because of completion of term |