JP4085183B2

JP4085183B2 - 遺伝的アルゴリズムによるフォント生成システム

Info

Publication number: JP4085183B2
Application number: JP2002159808A
Authority: JP
Inventors: 村貴利中
Original assignee: 株式会社エヌティーアイ
Priority date: 2002-05-31
Filing date: 2002-05-31
Publication date: 2008-05-14
Anticipated expiration: 2022-05-31
Also published as: JP2004004302A

Description

【０００１】
【発明の属する技術分野】
本発明は、主としてペン等の入力装置から入力された手書き文字を文字フォントデータとして出力する遺伝的アルゴリズムによるフォント生成システムに関するものである。
【０００２】
【従来の技術】
従来、ペン等を用いて手書き文字を入力できる手書きワードプロセッサなどでは、最初は入力された手書き文字を認識して得られる文字コードによる一律の、キーボード入力と同じような定型文字パターンにして印字出力していたが、最近では各個人特有の肉筆感のある署名などの必要性から、手書き文字を入力して各個人特有の筆跡が生かされた手書き文字も出力可能な手書き文字処理装置が多くなっている。
【０００３】
そうした従来の手書き文字処理装置としては、例えば、特開平０５−１４３７６９号に開示されている「手書き文字処理装置」が知られている。
図８はこの従来の手書き文字処理装置の構成図である。ユーザーはペン５２を持ってタブレット５１上に、図９に示すような「Ｔ」という手書き文字を入力すると、手書き文字の筆跡は演算処理部５３のベクトル変換回路５６とパターン認識回路５７へ入力される。
【０００４】
パターン認識回路５７はペン５２の位置データに基づいて入力される文字をパターン展開する。パターン展開された手書き文字パターンにより標準パターン辞書５８をアクセスして、パターンマッチングを図り該当する標準文字パターンを特定して、対応の文字コードを導出する。この導出した文字コードは「Ｔ」を表すもので、文字認識情報記憶部６０にストアされる。
【０００５】
次に、ベクトル変換回路５６では、ペン５２の位置データに基づいて図９に示すような、複数のサンプリング点ａ１〜ａｎ、ｂ１〜ｂｎを得て、手書き文字を構成する各ベクトルの始点、移動量及び終点を算出する。算出したベクトル情報（座標点フォント）は、図１０に示すような形式でベクトル情報記憶部５９にストアされる。ストアされるメモリ内容は、「移動量：ａ１〜ａ２」が座標点ａ１からａ２までの移動量［ΔＸ１、ΔＹ１］として、「移動量：ａ２〜ａ３」が座標点ａ２からａ３までの移動量［ΔＸ２、ΔＹ２］として示しており、「ＡＤ２」はメモリ・アドレスである。
また「始点：ａ１」〜「終点：ａｎ」までがベクトルＡを表し、「始点：ｂ１」〜「終点：ｂ１」はベクトルＢを表している。このようにベクトル変換処理は、手書き入力された文字を点の集まりにして変換記憶している。
【０００６】
次にラスタ描画については、先ず、プリンタ５５は通常印字の場合は、文字認識情報記憶部６０にストアされている文字コードを逐次読出し、欧文書体の場合はａｒｉａｌ、ｔｉｍｅｓなど、漢字書体なら明朝、ゴシックなどのフォントを指定して通常のワープロ用の定型文字パターンに展開して印字を行う。
【０００７】
一方、手書き文字データをそのまま手書き文字のまま印字出力するには、ベクトル情報記憶部５９にストアされている図１０に示すようなベクトル情報（座標点フォント）を読出して、読出したベクトル情報を曲線に変換するための関数（例えば、Ｂ−スプライン曲線関数、ベジェ曲線関数など）を用いて、プログラム処理によりドットの集合で表される曲線に変換する。このようにしてドットの集合で表された曲線のイメージデータはプリンタ５５に与えられ逐次印字出力されるので、手書き文字が微妙な手書き文字の弧を顕著に表示しながら印字される。
【０００８】
このように、図１０に示すベクトル情報（座標点フォント）の各点間の弧をベジェなどの曲線関数により補間生成して、図９に示すような手書き文字を復元するが、通常ワープロの定型パターン文字印字の場合は、ＡＳＣＩＩ、ＪＩＳ漢字コードなどの文字を指定する文字コードをストアしておいて、ａｒｉａｌ、明朝体などのフォントを指定し呼び出して印字を行うのに対して、手書き文字復元の場合は、明朝体などに相当するフォントを、ベクトル情報（座標点フォント）と、その座標点間の弧を補間するスプライン曲線関数やベジェ曲線関数を用いた曲線フォントで表す。従って、以降、本明細書の中で手書き文字フォントは、座標点フォント＋曲線フォント、を示すものとする。
【０００９】
ここで、弧補間用の曲線関数の例としてベジェ曲線関数を上げると、図１１に示すように、一般的なベジェ曲線は、始点Ｐ０、終点Ｐ３、制御点Ｐ１、Ｐ２で構成され、形状を変えずに２つに分割可能で、分割を繰り返し再帰的に適用することで際限なく細分して、最小単位まで細分した直線の集合で近似的にベジェ曲線を復元するものである。
例えば、ｄｍａｘを設定された許容値とし、直線Ｐ０とＰ３の中点Ｑと曲線上の点Ｐとの距離をｄとした場合に、ｄ＜ｄｍａｘ、を分割の判定基準として曲線を分割・細分化する。ｄｍａｘ（フラットネス）が小さい程滑らかな曲線に復元できる。
【００１０】
【発明が解決しようとする課題】
しかしながら、このような従来技術では、手書き文字フォントの演算は、ベジェ曲線関数の演算等を含み文字毎に逐次演算を行っているので、膨大な演算量となりシステム全体として処理速度の劣化を招くという問題があった。
そこで、本発明は、手書きフォントの生成に遺伝的アルゴリズムを導入することによって、システム全体として処理時間を削減して、システムの処理速度の改善を図ると共に、ユーザーによる修正を反映する遺伝的アルゴリズムによるフォント生成システムを提供することを目的としている。
【００１１】
【課題を解決するための手段】
上記目的を達成するため、本発明の遺伝的アルゴリズムによるフォント生成システムは、手書き入力された文字パターンより、手書き文字フォントを生成して手書き文字を出力する文字フォント生成システムにおいて、手書き文字を入力して記憶する入力手段と、前記入力手段により入力される前記手書き文字を文字パターンに変換して出力するパターン変換手段と、前記パターン変換手段により出力される前記文字パターンを認識して該当する文字コードを出力する文字認識手段と、前記入力手段により入力される前記手書き文字を該文字の特徴を含むベクトル情報に変換して出力するベクトル変換手段と、前記ベクトル情報を手書き文字の座標点フォントとして記憶するベクトル情報記憶手段と、前記ベクトル情報記憶手段の座標点フォントを読出し補間曲線関数による曲線フォントを遺伝的アルゴリズムＧＡにより演算生成するＧＡ演算処理手段と、前記ＧＡにより演算生成された曲線フォントを記憶する手書きフォント記憶手段と、を備え、
前記ＧＡ演算処理手段は、前記座標点フォントを入力して前記補間曲線関数をセグメント分割により直線で近似する補間曲線関数処理部と、前記セグメントの係数を個体として複数の個体を含む集団を形成する集団形成部と、前記遺伝的アルゴリズムＧＡの世代数上限、個体数、交叉点、突然変異、評価関数を少なくとも含むパラメータの設定条件を記述した条件設定テーブルと、前記補間曲線関数処理部におけるセグメントの係数を個体とする近似計算に前記条件設定テーブルに設定された前記パラメータを用いてＧＡ演算を行うＧＡ制御部とを有し、予め記憶された標準パターン辞書の標準文字パターンに前記遺伝的アルゴリズムを適用して前記手書き文字フォントを生成することを特徴としている。
また、前記ＧＡ演算処理手段は、ＧＡにより曲線フォントを演算生成する際に、複数の異なる文字パターンを生成して記憶する文字パターン生成部と、生成された複数の異なる文字パターンの中から利用者により選択されて記憶される文字パターン選択部と、を有することを特徴としている。
【００１２】
【発明の実施の形態】
以下、本発明の実施の形態について図を参照して説明する。
図１は、本発明の実施の形態に係る遺伝的アルゴリズムによるフォント生成システムの構成図である。
図２は、図１に示すＧＡ演算処理部の構成図である。
図３は、図２に示すＧＡ演算処理部の処理のフローチャートである。
図４は、図２に示す補間曲線の説明図である。
図５は、図４に示す補間曲線の評価の説明図である。
図６は、図２に示すＧＡ制御部の処理の説明図である。
図７は、図２に示すＧＡ演算処理部で生成する文字パターンの説明図である。
【００１３】
図１において、１はＧＡフォント生成システムで、２はそのＧＡ（遺伝的アルゴリズム）演算処理部であり、遺伝的アルゴリズムによる演算によって手書き文字入力のフオント生成演算を行う。３は生成された曲線フォントを記憶する手書きフォント記憶部、４は明朝体等の定型文字フォント辞書である。
なお、従来技術の図８と同一構成には同一符号を付して重複する説明は省略する。
【００１４】
図２において、２はＧＡ演算処理部、５はベクトル情報記憶部５９から手書き文字のベクトル情報を入力して、ベジェ曲線関数等の補間関数を用いた曲線近似処理を行う補間曲線関数処理部、６はベジェ曲線の分割単位（セグメント）を１個体として複数の個体を含む集団（１フォント曲線）を形成し、複数の集団による集団群（１ストローク）を形成する集団形成部、７は集団形成部６により構成される複数の集団を並列処理するように配置した集団群を示す。８はＧＡ演算処理の世代数上限、個体数、交叉点、突然変異、評価関数、ベジェ曲線関数の閾値ｄｍａｘ等の、パラメータの設定条件等を記述した条件設定テーブル、９は条件設定テーブル８に設定の各パラメータを用いて並列演算によりＧＡ演算処理を行うＧＡ制御部、１０はユーザーによる選択が可能なようにフォント生成過程に設けた文字パターン生成・選択部であり、１１は処理結果（フォント）の出力部である。
【００１５】
つぎにＧＡ演算処理の具体的な処理について説明する。
ＧＡ演算処理部２は、補間曲線関数処理部５によりベクトル情報記憶部５９から図９に示すようなベクトル情報（座標点フォント）を読出し、ベジェ曲線などの曲線関数による補間演算をＧＡ演算によって行い曲線フォントを生成する。
【００１６】
ここで、ベジェ曲線関数とは、図４に示すように、始点Ｐ０、終点Ｐ３、制御点Ｐ１、Ｐ２で定義されるベジェ曲線を、ｆ（ｔ）、（０≦ｔ≦１）というパラメトリック曲線で表現した際の、Ｒ２（０．５）なる点において形状を変えずに２つのベジェ曲線（セグメント）、すなわち（Ｐ０、Ｑ０１、Ｒ１、Ｒ２）と、（Ｒ２、Ｒ３、Ｑ２３、Ｐ３）に分割できる性質を持つ。ここで、
Ｑ０１＝（Ｐ０＋Ｐ１）／２
Ｒ１＝（Ｐ０＋２Ｐ１＋Ｐ２）／４
Ｒ２＝｛Ｐ０＋３（Ｐ１＋Ｐ２）＋Ｐ３｝／４
Ｒ３＝（Ｐ１＋２Ｐ２＋Ｐ３）／４
Ｑ２３＝（Ｐ２＋Ｐ３）／２
である。
【００１７】
このように、ベジェ曲線は分割を繰り返し再帰的に適用することで際限なく細分することができるので、このベジェ曲線の性質がベジェ曲線の描画に利用されている。つまり、描画しようとするベジェ曲線を再帰分割して、分割後の各セグメントが予め設定されている閾値ｄｍａｘより平坦であると判断された時点で分割を止め、この時の各セグメントを始点と終点を結ぶ直線で近似して描画することにより、最小単位に分割した直線群の集合という形で、近似的なベジェ曲線を描画できる。
この場合に各セグメントを平坦と判断する基準は、図５に示すように、ｄをベジェ曲線と直線Ｐ０、Ｐ３との距離の最大値、ｄ１、ｄ２を各制御点Ｐ１、Ｐ２と直線Ｐ０、Ｐ３との距離、フラットネスの閾値をｄｍａｘと定義すると、
ｄ１≧ｄ、ｄ２≧ｄであって、
ｄ１＜ｄｍａｘ（１）
ｄ２＜ｄｍａｘ（２）
の２つの条件が共に満足された場合に平坦と判断して曲線の分割を止め、分割した各セグメントでベジェ曲線を近似する。
【００１８】
以上のベジェ曲線関数を用いて、補間曲線関数処理部５は、図９のようなベクトル情報を読込み、始点ａ１〜次の座標点ａ２間の弧を近似描画するために、ベジェ曲線ａ１〜ａ２を再帰分割する。
この場合にＧＡ制御部９は遺伝的アルゴリズムの前処理として、セグメント毎のｄ１、ｄ２値を個体としてコーディングする。
例えば、今、ｄ１、ｄ２値が、２〜５、６〜９だとすると、以下のように２進コードによってコーディングする。
ｄ１２進コードｄ２２進コード
６「０１１０」２「００１０」
７「０１１１」３「００１１」
８「１０００」４「０１００」
９「１００１」５「０１０１」
この場合の各ビット０，１はそれぞれ遺伝子に対応する。
【００１９】
次に、個体の集合体としての初期集団を、例えば、ａ１〜ａ２、ａ２〜３、…ａｎ−１〜ａｎのように各座標点間の弧として定義する。従って、図９に示すような、ストロークＡはａｎ個の集団によって構成される集団群として表され、並列演算による高速処理が可能な形態に構成される。
【００２０】
ＧＡ演算処理の詳細を、図３に示すＧＡ演算処理のフローチャートを参照して説明する。ここでの処理はＧＡ制御部９が、条件設定テーブル８の設定パラメータを用いて行う並列演算の内容である。
最初に、世代数をカウントアップする（Ｓ１００）。
遺伝的アルゴリズム（ＧＡ）は、
（１）、２進数表現の個体群の初期集団を生成する。
（２）、設定された評価関数により各個体の評価を行う。
（３）、評価に基づいて淘汰、増殖による個体の選択を行う。
（４）、遺伝子を入れ替える交叉を行う。
（５）、遺伝子を変化させる突然変異を行う。
の（１）〜（５）を１ループとする処理を世代と呼び、世代を繰り返し実施することにより最小値に収束させる処理を行うことから、先ず、現在の世代数をカウントして確認する。例えば、ここでの世代数は具体的には、セグメントの分割回数などに相当する。
【００２１】
次に、世代数の上限に達したか？を判断する（Ｓ１０１）。
先に、条件設定テーブル８に世代数上限として世代処理回数を設定してあるので、これを参照して世代数上限に達していれば処理を終了し（Ｓ１０２）、未だ上限に達していなければ、各個体の評価を行う（Ｓ１０３）。
評価処理は個々の個体毎に行われ、条件設定テーブル８に予め設定されている評価関数を用いる。この場合の評価関数は、条件設定テーブル８に設定されている閾値ｄｍａｘを用いた、
ｄ１＜ｄｍａｘ
ｄ２＜ｄｍａｘ
により評価される。
【００２２】
続いて、個体評価を基に選択処理を行う（Ｓ１０４）。
先ず、条件設定テーブル８に設定されている「しきい値」を用いて、個体の淘汰と増殖を行う。「しきい値」は特に限定しないが、例えば、セグメント中のｄ１とｄ２の差が「しきい値」より大きいようなアンバランスなセグメントが出現したら削除して淘汰し、削除した分に残った良いセグメントをコピー（補間により増殖）させる等の選択・淘汰を行う。
【００２３】
次に、個体同士を組にして交叉を行う（Ｓ１０５）。
交叉は条件設定テーブル８に設定されている交叉条件に従って、例えば、個体（親Ａ）の遺伝子と個体（親Ｂ）の遺伝子を入れ替え、第１、第２の個体（子）を生成する。今、親Ａ＝１０１１、親Ｂ＝０１００、として後半の遺伝子同士を入れ替えると、第１の子＝１０００、第２の子＝０１１１と言う交叉となる。
この他に、交叉の方法は、それぞれ前半と後半の遺伝子を入れ替える方法や、一点交叉、他点交叉、等各種の方法がある。
【００２４】
続いて、いくつかの個体の遺伝子を変化させる突然変異の処理を行う（Ｓ１０６）。
突然変異は条件設定テーブル８に設定された、突然変異の起こる確率と条件に従って、例えば、個体「０１００」→「０１１０」、と言うように個体の遺伝子を変化させる。
これら交叉、突然変異などの処理は、例えば、セグメントを分割して行く過程でｄ１、ｄ２の減少率、バランス等をダイナミックに調整することで演算のやり直しを避けたり、分割回数を早めたりして、より最小値への収束を促進するための処理である。
このように、ベジェ曲線の近似処理に、最適化を図って迅速に収束させることができる遺伝的アルゴリズムを導入したことによって、従来の逐次的な近似演算に比較して大幅に処理時間が短縮できる。
【００２５】
こうして、ベジェ曲線が最小直線のセグメントに収束して、弧ａ１〜ａ２のベジェ曲線描画、つまり集団１の曲線フォントが生成されたら、結果出力部１０から出力して、ベクトル情報記憶部５９のベクトル情報とリンクして対応する曲線フオントを手書きフォント記憶部３に記憶する。
同様にして、ａ２〜ａ３…ａｎ−１〜ａｎ、の曲線フォントを手書きフォント記憶部３に記憶する。
ストロークＢについても同様な処理を行う。
こうしたＧＡ演算処理全体としては、各集団は並列処理が行われ、各集団内では図６に示すように、各セグメント（個体）が並列処理され、更に、ストロークＡとストロークＢも並列処理により生成されるので高速処理が可能になる。
【００２６】
文字パターン生成・選択部１０は、フォント生成のための前述したＧＡ演算処理に加えて、ユーザーによる好みなどをフォント生成に反映させるために、ユーザー認知が可能な文字パターンの生成と、生成された文字パターンの選択手段を提供する。
図７は、生成された文字パターンの一例を示しており、縦長、横長、右あがり、右下がり、太った、痩せた、等の変形した様々な文字パターンを生成して、ユーザーに生成した文字パターンを選択させるものである。
このようにして選択された文字パターンの各パラメータは再度ＧＡ処理部で使用され、最終的なフォントにはユーザーの修正内容が反映される。
【００２７】
最後にラスタ描画については、手書き入力を定型印字する場合は、従来と同様に文字認識情報記憶部６０から文字コードを読出し、フォント辞書４で書体フォントを指定して定型印字する。
一方、手書き文字を手書きのまま印字出力する場合は、ベクトル情報記憶部５９と手書きフォント記憶部３のデータを読出しビットマップ展開して印字する。これによって認証用の署名、サイン、肉筆の宛名書、自筆の手紙などが可能になる。
また、文字の拡大・縮小、太字印字、などは手書き文字のサイズが正規化されているので、手書きフォントの曲線関数の定数を可変設定するだけで、特徴のある手書き文字を表示し、印字出力することができる。
その他の文字位置などの制御コードについては従来フォントに準ずる。
【００２８】
ここまでは、手書き文字のフォント生成処理に遺伝的アルゴリズムＧＡを導入する例について説明したが、これ以外に、例えば、パターン認識部５７における手書き文字パターンと、標準パターン辞書の標準文字パターンとのパターンマッチング（パターン照合）処理なども、大量のデータを処理する画像認識演算が必要となるので本発明の遺伝的アルゴリズムの適用は有効である。
【００２９】
【発明の効果】
以上説明したように、本発明によれば、手書き入力された文字パターンより手書き文字フォントを生成して手書き文字を出力する文字フォント生成システムにおいて、入力された手書き文字を記憶・変換した文字パターンを認識して該当する文字コードを出力する文字認識手段と、入力される手書き文字を該文字の特徴を含むベクトル情報に変換して手書き文字の座標点フォントとして記憶するベクトル情報記憶手段と、ベクトル情報記憶手段の座標点フォントを読出しベジェ曲線等の補間曲線関数による曲線フォントを遺伝的アルゴリズムＧＡにより演算生成するＧＡ演算処理手段と、曲線フォントを記憶する手書きフォント記憶手段と、を備えているので、手書き文字フォントの生成演算時間が短縮できてスムースな手書き文字出力が可能になる。
また、ＧＡ演算処理手段は、座標点フォントを入力してベジェ曲線等の補間関数をセグメント分割により直線で近似し、セグメントの係数を個体として複数の個体を含む集団を形成して、遺伝的アルゴリズムＧＡの世代数上限、個体数、交叉点、突然変異、評価関数などのパラメータの設定条件を基に、セグメントの係数を個体とする近似計算によってＧＡ演算を行うので、ＧＡによる最適化処理によってベジェ曲線などの補間関数の収束が迅速に行われ、手書きフォントの生成時間が短縮される。
さらに、ＧＡ演算処理手段は、ＧＡにより曲線フォントを演算生成する際に、複数の異なる文字パターンを生成・記憶すると共に、生成された複数の異なる文字パターンの中から利用者による選択・記憶を可能にしているので、より、ユーザーの好みを反映した手書き文字フォントを作成することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係る遺伝的アルゴリズムによるフォント生成システムの構成図である。
【図２】図１に示すＧＡ演算処理部の構成図である。
【図３】図２に示すＧＡ演算処理部の処理のフローチャートである。
【図４】図２に示す補間曲線の説明図である。
【図５】図４に示す補間曲線の評価の説明図である。
【図６】図２に示すＧＡ制御部の処理の説明図である。
【図７】図２に示すＧＡ演算処理部で生成する文字パターンの説明図である。
【図８】従来の手書き文字処理装置の構成図である。
【図９】図８に示す手書き文字処理装置の座標点フォントの説明図である。
【図１０】図９に示す座標点フォントのメモリ内容を示す図である。
【図１１】図８に示す手書き文字処理装置の補間関数の説明図である。
【符号の説明】
１ＧＡフォント生成システム
２ＧＡ演算処理部
３手書きフォント記憶部
４フオント辞書
５補間曲線関数処理部
６集団形成部
７集団群
８条件設定テーブル
９ＧＡ制御部
１０文字パターン生成・選択部
１１結果出力部

Claims

手書き入力された文字パターンより、手書き文字フォントを生成して手書き文字を出力する文字フォント生成システムにおいて、
手書き文字を入力して記憶する入力手段と、
前記入力手段により入力される前記手書き文字を文字パターンに変換して出力するパターン変換手段と、
前記パターン変換手段により出力される前記文字パターンを認識して該当する文字コードを出力する文字認識手段と、
前記入力手段により入力される前記手書き文字を該文字の特徴を含むベクトル情報に変換して出力するベクトル変換手段と、
前記ベクトル情報を手書き文字の座標点フォントとして記憶するベクトル情報記憶手段と、
前記ベクトル情報記憶手段の座標点フォントを読出し補間曲線関数による曲線フォントを遺伝的アルゴリズムＧＡにより演算生成するＧＡ演算処理手段と、
前記ＧＡにより演算生成された曲線フォントを記憶する手書きフォント記憶手段と、を備え、
前記ＧＡ演算処理手段は、
前記座標点フォントを入力して前記補間曲線関数をセグメント分割により直線で近似する補間曲線関数処理部と、前記セグメントの係数を個体として複数の個体を含む集団を形成する集団形成部と、前記遺伝的アルゴリズムＧＡの世代数上限、個体数、交叉点、突然変異、評価関数を少なくとも含むパラメータの設定条件を記述した条件設定テーブルと、前記補間曲線関数処理部におけるセグメントの係数を個体とする近似計算に前記条件設定テーブルに設定された前記パラメータを用いてＧＡ演算を行うＧＡ制御部と、を有し、
予め記憶された標準パターン辞書の標準文字パターンに前記遺伝的アルゴリズムを適用して前記手書き文字フォントを生成することを特徴とする遺伝的アルゴリズムによるフォント生成システム。
前記ＧＡ演算処理手段は、ＧＡにより曲線フォントを演算生成する際に、複数の異なる文字パターンを生成して記憶する文字パターン生成部と、生成された複数の異なる文字パターンの中から利用者により選択されて記憶される文字パターン選択部と、を有することを特徴とする請求項１に記載の遺伝的アルゴリズムによるフォント生成システム。