JP5289566B2 - アウトライン文字をスタイル化ストローク文字に変換する方法 - Google Patents

Description

本発明は、包括的には、フォントを変換することに関し、より詳細には、アウトラインフォントで表されたアウトライン文字をスタイル化ストロークフォント（ＳＳＦ：Ｓｔｙｌｉｚｅｄ Ｓｔｒｏｋｅ Ｆｏｎｔ）で表されたスタイル化ストローク文字に変換することに関する。

例えば移動電話、携帯情報端末、カーナビゲーションシステム、プリンター、カメラ、及び電気機器といったプロセッサ及びメモリの制約があるデバイスが急増し、例えばＦｌａｓｈ（フラッシュ）及びＪａｖａ（ジャバ）といったフォントを含むアプレットのインターネット上でのオンデマンドによる転送が実用化されることによって、既存のフォント表現の欠点が実証されている。

これらのプロセッサ及びメモリの制約によって、スクリプトが多数の文字を含むとき、特定の問題が提起される。大きな高品質フォントセットには、大量のメモリが必要とされ、処理が遅い。表１に示すように、中国語、日本語、及び韓国語（ＣＪＫ：Ｃｈｉｎｅｓｅ，Ｊａｐａｎｅｓｅ，ａｎｄ Ｋｏｒｅａｎ）のスクリプトは、ラテンスクリプトよりもはるかに多くの文字を含む。

図１Ａは、従来の表現的なアウトラインフォントで表された中国語文字を示す。このアウトラインフォントは、閉輪郭を形成する直線分及び曲線分を使用する。アウトラインフォントは、メモリ及びプロセッサの制約があるデバイスでサポートするのが難しい。高品質アウトライン文字をレンダリングするのに使用される従来の方法には、かなりのＣＰＵリソースが必要とされ、これらのフォントのメモリフットプリントは大きい。

ビットマップ表現でも、あまりにも多くのメモリが、メモリの制約があるデバイスに必要とされる。さらに、モノクロビットマップは、アンチエイリアシングされず、ビットマップは、スケーラブルではなく、ビットマップを手作業で調整することは、非常に多くの労力を要する。

メモリ使用量を最適化するには、均一幅ストロークフォントを使用することができる。これらのフォントは、通常、中国語文字においてフォント全体にわたり一般に繰り返される部首又は書記素としても知られているストロークのセットを、文字のあらゆる箇所でその後再利用される単一の単純な形状としてグループ化している。

図１Ｂは、従来の均一幅ストロークフォントで表された中国語文字を示す。従来の均一幅ストロークフォントは、必要とされるメモリが大幅に少ないが（〜２５０ＫＢ）、筆で書かれた豊かな中国語書体のスタイルを反映しておらず、したがって、文化的な受容性に欠けている。

スタイル化ストロークフォント（ＳＳＦ）は、そのストロークが可変の太さ及びスタイリッシュなストローク端部を有する高度化されたストロークベースのフォントである。これについては、「Ａｎ Ｉｍｐｒｏｖｅｄ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ Ｓｔｒｏｋｅ−ｂａｓｅｄ Ｆｏｎｔｓ」（ＳＩＧＧＲＡＰＨ ２００６ Ｃｏｎｆｅｒｅｎｃｅ Ａｂｓｔｒａｃｔｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， Ｅｌｅｎａ Ｊ． Ｊａｋｕｂｉａｋ， Ｒｏｎａｌｄ Ｎ． Ｐｅｒｒｙ， ａｎｄ Ｓａｒａｈ Ｆ． Ｆｒｉｓｋｅｎ）を参照されたい。ＳＳＦは、フォント内の形状の繰り返しを利用するモジュール構造を用い、ＳＳＦが、アウトラインフォントの表現力を、現在の均一幅ストロークフォントに相当するメモリフットプリントと調和させることを可能にしている。

ＳＳＦが、アウトラインフォントに代わる実用的なものになるには、アウトラインフォントによって提供される多様性に適合したＳＳＦの集まりが必要とされる。あいにく、単一のＳＳＦ ＣＪＫフォントを一から作成することは、何人年もの労力を要する可能性がある。その結果、ＣＪＫグリフを従来のアウトライン表現（例えば、ＴｒｕｅＴｙｐｅ（トゥルータイプ）フォント）からＳＳＦに自動的に変換する方法が必要とされている。

ＣＪＫアウトラインフォントをスタイル化ストロークフォント（ＳＳＦ）に変換する有効な方法は、例えばパラメータの調整及び失敗した変換の編集を行うのに最小の人の入力を必要としなければならず、変換の失敗を自動的に検出できなければならない。

その上、変換プロセスは、変換の失敗を訂正する時間が、ＳＳＦを一から作成する時間よりも大幅に少ないほど十分に正確である必要もある。アウトラインフォントをＳＳＦに自動的に変換すること、並びにフォント設計者が不十分に変換されたあらゆる文字を迅速に訂正することを可能にする編集ツール及び診断ツールを提供することが、本発明の目的である。

ＣＪＫフォントを作成し、メモリ要件を削減する従来技術の手法は、コアコンポーネントから文字を作成すること、文字のパラメータ記述を使用すること、形状の繰り返しを利用して既存のアウトラインフォントを圧縮すること、及び字源化された（ｒａｄｉｃａｌｉｚｅｄ）均一幅ストロークフォントを設計することを含む。

すべての中国語文字を記述するのに、約１０個の基本ストロークのコアセットが使用される。これらの基本ストローク群は、多くの文字にわたって繰り返し使用される。その結果、フォント作成をストリームライン化し、メモリ要件を削減する１つの手法は、ストローク又はストローク群の基本セットからフォントを作成することである。しかしながら、この建設的な手法は、空間バランス及び調和を保証する、文字内のストロークのロケーションに起因した重要なスタイルの微妙な点を表す能力に欠けている。これらの微妙な点は、一般的な文化的受容性にとって重要である。

別の手法は、幾何学的方程式のセットを使用して、ストローク又は文字の部品を数学的に規定する。これらの数学的に設計された文字も、作成時間を最小にし、メモリ要件を削減する可能性を有する。しかしながら、フォント設計者は、バランス及び調和の点から設計を行う専門化した芸術家である。ドナルド・クヌースを引用すると、「数学者にうんざりしてきた芸術家に、６０個のパラメータを有するフォントを書く方法を理解するように頼むことは酷である（…ａｓｋｉｎｇ ａｎ ａｒｔｉｓｔ ｔｏ ｂｅｃｏｍｅ ｅｎｏｕｇｈ ｏｆ ａ ｍａｔｈｅｍａｔｉｃｉａｎ ｔｏ ｕｎｄｅｒｓｔａｎｄ ｈｏｗ ｔｏ ｗｒｉｔｅ ａ ｆｏｎｔ ｗｉｔｈ ６０ ｐａｒａｍｅｔｅｒｓ ｉｓ ｔｏｏ ｍｕｃｈ」（Ｋｎｕｔｈ， １９８６， Ｔｈｅ ＭＥＴＡＦＯＮＴｂｏｏｋ， Ａｄｄｉｔｉｏｎ−Ｗｅｓｌｅｙ）。したがって、アウトラインフォントは、普及し続ける。

アウトライン表現を圧縮する試みによって、約２５％の圧縮が達成されたが、これらの節減ではまだ不十分である。したがって、フォントの製造者は、アウトラインとは対照的に、単純化された中心線によって表され、かつフォント全体を通じてストローク群を再利用する均一幅ストロークフォントを開発してきた。これらのフォントに必要とされるメモリは大幅に少なくなるが（例えば、標準的なＧｕｏｊｉａ Ｂｉａｏｚｈｕｍ（ＧＢ：中国国家標準）２３１２の７，６６３文字を有する簡体字中国語文字セットの場合は２５０ＫＢ）、それらの文字は、過度に単純化されたものであり、ＣＪＫ文字の筆による豊かなスタイルを反映していない。

本発明は、従来のアウトライン文字をスタイル化ストローク文字に自動的に変換する方法を提供する。中国語、日本語、及び韓国語（ＣＪＫ）のフォントのそれぞれは、１２，０００文字よりも多くの文字を含む可能性があるが、このＳＳＦスタイル化ストロークベースの表現は、これらＣＪＫのフォントに特に適している。

従来のアウトラインＣＪＫフォントには、少なくとも３〜１０ＭＢのメモリが必要とされる。本発明の実施の形態による方法では、相当するＳＳＦに、約２５０ＫＢが必要とされる。同様のメモリ削減は、均一幅ストロークフォントを使用して成し遂げることができるが、ＳＳＦは、アウトラインフォントの優れたスタイル特性を保持している。

この自動変換方法は、距離場を使用する。この方法は、一般的な均一幅ストロークフォントでＳＳＦを初期化し、その後、対象となるアウトラインフォントの対応する文字の形状及びスタイルと一致するように、各スタイル化ストローク文字を反復的に修正する。この方法は、距離場を使用して、スタイル化ストローク文字とその対応するアウトライン文字との間の誤差を測定し、各反復について必要とされる修正を決定する。

従来のアウトラインフォントで表された中国語文字である。 従来の均一幅ストロークフォントで表された中国語文字である。 輪郭のはっきりした筆ストロークとして書かれた中国語文字である。 本発明の実施の形態１によるスタイル化ストロークフォントで表された中国語文字である。 本発明の実施の形態１によるスタイル化ストロークである。 本発明の実施の形態１による変換されるアウトラインフォントで表された中国語文字である。 本発明の実施の形態１による閉じた経路による図５Ａの文字である。 図５Ｂの閉じた経路によって暗に含まれる合成形状による図５Ａの文字である。 本発明の実施の形態１による距離場として表された中国語文字である。 本発明の実施の形態１によるアウトライン文字をスタイル化ストローク文字に変換する方法のフロー図である。 アウトラインフォントで表された中国語文字である。 本発明の実施の形態１によるアウトライン文字の閉じた交わらない領域の輪郭を描く閉輪郭で表された図８Ａの中国語文字である。 本発明の実施の形態１による適用された線分化オペレーションを伴う中国語文字である。 本発明の実施の形態１による適用された三角形分割オペレーションを伴う中国語文字である。 本発明の実施の形態１による適用された接合オペレーションを伴う中国語文字である。 本発明の実施の形態１による適用されたマスクオペレーションを伴う中国語文字である。 本発明の実施の形態１による中国語文字の階層的ツリー表現である。 本発明の実施の形態１によるストロークが割り当てられた中国語文字である。 本発明の実施の形態１によるストロークが割り当てられた中国語文字である。 本発明の実施の形態１によるストロークが割り当てられた中国語文字である。 本発明の実施の形態１による図７の方法のステップが適用された中国語文字である。 本発明の実施の形態１による図７の方法のステップが適用された中国語文字である。 本発明の実施の形態１による図７の方法のステップが適用された中国語文字である。 本発明の実施の形態１による図７の方法のステップが適用された中国語文字である。 本発明の実施の形態１による図７の方法のステップが適用された中国語文字である。 本発明の実施の形態１による図７の方法のステップが適用された中国語文字である。 本発明の実施の形態１による末端のセットである。 本発明の実施の形態１による末端がフィットされたストロークである。 本発明の実施の形態１によるＳＳＦ中心線に沿ったサンプル点におけるエネルギー及び力を求める方法の図である。

実施の形態１．
本発明は、従来のアウトラインフォントで表された文字（すなわちアウトライン文字）をスタイル化ストロークフォントで表された文字（すなわちスタイル化ストローク文字）に自動的に変換する方法を提供する。

文字構造
図２に示すように、中国語のカリグラフィックストローク（ｃａｌｌｉｇｒａｐｈｉｃ ｓｔｒｏｋｅ）のスタイルは、大きくは、用紙に沿った３段階の筆の移動、すなわち開始２０１、展開２０２、及び終了２０３によって規定される。

図３及び図４に示すように、ＳＳＦストロークの構造は、この筆の移動を反映している。ＳＳＦのストロークの本体３０１は、中心線４０１及び輪郭４０２を含む。中心線４０１は、図２の展開に沿った筆の経路を反映し、輪郭４０２は、展開に沿った筆圧の変化を反映している。ＳＳＦストロークの末端３０２は、筆の先端がページに置かれた時の筆の移動の開始のスタイル化表現及び筆の先端がページから取り去られた時の筆の移動の終了のスタイル化表現である。各中心線及び各末端は、線分及びベジェ曲線の開いた区分的に連続な経路によって表される。輪郭は、単一の二次ベジェ曲線によって表される。この単一の二次ベジェ曲線は、ストロークの中心線からストロークの双方のエッジまでの垂直距離を規定する。

各アウトライン文字は、ＳＳＦ表現に変換される。所与のアウトライン文字について、本発明者の方法は、均一幅ストロークフォントからの対応する文字を使用して、スタイル化ストローク文字を初期化する。この対応する文字は、その後、アウトライン文字と一致するように反復的に修正される。ＳＳＦの中心線４０１は、均一幅ストローク文字の経路を使用して初期化される。ＳＳＦの輪郭４０２は、一定値に初期化され、ＳＳＦのストロークは、末端なしで初期化される。

図５Ａは、図５Ｂに示すような閉じた経路によって表されたアウトライン文字を示し、図５Ｂは、図５Ｃに示すように、その文字における暗に含まれたストロークの合成形状である。このように、アウトライン文字は、実際には、その文字を規定するストロークの合成形状である。スタイル化ストローク文字のストロークは、実際には、アウトライン文字の暗に含まれたストロークと一致するように修正される。

距離場
文字６００について図６に示すように、距離場は、空間における任意の点について、その点から文字の境界までの距離を指定する。通常、外側の点６０１は負であり、内側の点６０２は正であり、アウトライン上の点６０３は０である。

文字の距離場は、空間の任意の点について文字の境界までの距離及び方向を提供するので、距離場は、アウトラインの暗に含まれたストロークと一致するようにＳＳＦストロークを修正するのに特に役立つ。

図１５に示すように、アウトライン文字の対応する暗に含まれたストロークと一致するように、ＳＳＦストロークをどのように修正するのかを決定するために、各ＳＳＦ中心線に沿った規則的間隔のサンプル点１５０１が使用される。サンプル点１５０１における符号付き距離値は、文字エッジ上の最も近い点までの距離だけでなく、サンプル点１５０１がアウトライン文字の内側にあるのか又は外側にあるのかを示し、それによって、アウトライン文字の対応する暗に含まれたストロークの中心線に達するには、ＳＳＦ中心線をどのように移動させるべきかの手がかりを提供する。

アウトライン文字の距離場は、滑らかに変化するので、この手法は、サンプリングロケーション及びサンプリング周波数に対して比較的ロバストである。ＳＳＦストロークが所定の位置になった後、ＳＳＦ中心線は、勾配が０であるアウトライン文字の距離場のエリアに沿って位置している。加えて、ＳＳＦ本体のエッジ及び末端は、アウトライン文字の距離場のゼロレベルの等位面に沿って位置している。

変換方法
図７に示すように、アウトライン文字をスタイル化ストローク文字（すなわちＳＳＦ文字）に変換する方法は、２つの段階７０１〜７０２を有する。第１段階７０１の期間中、スタイル化ストローク文字が初期化され、その後、文字の形状及び構造の情報が、スタイル化ストローク文字及びアウトライン文字の双方について計算される。第２段階７０２の期間中、この形状及び構造の情報が使用されて、スタイル化ストローク文字が、アウトライン文字と一致するように反復的に修正される。

各段階には、３つのステップがある。ステップ１は、アウトライン文字を前処理することであり（７１１）、ステップ２は、スタイル化ストローク文字を初期化及び前処理することであり（７１２）、ステップ３は、ＳＳＦストロークと、アウトライン文字の閉じた交わらない領域との間の対応を識別することであり（７１３）、ステップ４は、アウトライン文字の暗に含まれたストロークと一致するようにＳＳＦストロークを修正することであり（７２１）、ステップ５は、ＳＳＦストロークの端部位置を調整することであり（７２２）、ステップ６は、ＳＳＦのストロークの末端を選択することである（７２３）。

ステップ１−アウトライン文字の前処理
図８Ａに示すような変換されるアウトライン文字は、閉じた交わらない領域の輪郭を描く一連の閉輪郭によって表される。ステップ１は、アウトライン文字の閉じた交わらない領域を識別する。次に、サンプリングされた符号付き距離場が各領域について求められる。各領域は解析され、その領域を規定する輪郭の高密度サンプリングされた線分近似の周知のドロネー（Ｄｅｌａｕｎａｙ）三角形分割を使用してストローク本体及び末端の候補ロケーションが求められる（図９Ａ参照）。

ドロネー三角形分割は、接合三角形（ｊｕｎｃｔｉｏｎ ｔｒｉａｎｇｌｅ）、末端三角形（ｔｅｒｍｉｎａｌ ｔｒｉａｎｇｌｅ）、及びスリーブ三角形（ｓｌｅｅｖｅ ｔｒｉａｎｇｌｅ）の３つのタイプの三角形を含む。これらのタイプは、三角形と線分近似との間で共有されるエッジの個数によって区別される（図９Ｂ参照）。

アウトライン領域の形状は、その領域を規定する暗に含まれたストロークの合成形状であることを思い出されたい（図５Ｃ参照）。したがって、三角形の各タイプは、暗に含まれたストロークの可能な部分に対応する。接合三角形又は末端三角形は、形状の変化を示す。したがって、接合三角形及び末端三角形の外接円は、暗に含まれたストローク間の交点、コーナー、及び接合部、例えばＴ字型接合部について、並びに暗に含まれたストローク端部について、円として表される候補エリアとして使用される（図９Ｃ参照）。スリーブ三角形は、ゆっくりと変化する形状又は一定の形状を示し、単一の暗に含まれたストロークの本体に対応することができる。

この方法は、ドロネー三角形分割の頂点を使用して重み付きマスクを求める（図９Ｄ参照）。マスクの各サンプル点には、そのサンプル点がアウトライン領域の単一の暗に含まれたストロークの本体に位置する尤度が割り当てられる。

マスクは次のように求められる。ドロネー三角形分割の各頂点ｖに、０と１との間の重みが割り当てられる。接合三角形又は末端三角形に属する頂点は、常に０の重みを有する。残りの各頂点ｖは、その法線と、頂点ｖがエッジを共有する各頂点ｕの法線とのドット積に基づく重みｗｅｉｇｈｔ（ｖ）＝１−ｍｉｎ｛Ｎ_ｕ・Ｎ_ｖ｝／２を有する。ここで、Ｎ_ｕ及びＮ_ｖは、頂点ｕ及びｖにおけるアウトライン輪郭の法線であり、Ｎ_ｕ・Ｎ_ｖは、Ｎ_ｕとＮ_ｖとのドット積であり、ｍｉｎ｛Ｎ_ｕ・Ｎ_ｖ｝は、ｖから延びるすべてのエッジｅ＝（ｕ，ｖ）にわたるＮ_ｕ・Ｎ_ｖの最小値である。マスクは、頂点間の重みを補間することによって求められる。

ステップ２−ＳＳＦ文字の初期化及び前処理
スタイル化ストローク文字は、均一幅ストロークフォントからの対応する文字を使用して初期化される。ＳＳＦ中心線は、対応する均一幅ストローク文字の経路を使用して初期化される。ＳＳＦ輪郭は一定値に初期化される。ＳＳＦストローク本体は、末端を有しないように初期化される。コーナーを有する経路は、複数のＳＳＦストローク本体を形成するように区画される。

スタイル化ストローク文字のストロークは、１つ又は複数の重なり合わないストロークセットを形成する。各ストロークセット内のＳＳＦストロークは、ＳＳＦストロークセットのサブセットを規定するのに使用される相互の特定の関係を有する。

ステップ２は、各重なり合わないストロークセットからのＳＳＦストロークを、これらのサブセットの階層ツリーに編成する（図１０参照）。図１０に示すように、ＳＳＦグリフのストロークは、重なり合わない独立したストロークセットに区画することができる。各ストロークセットは、ＳＳＦストローク間の関係を反映したサブセットの階層を構成する。図１０は、描かれたグリフのこのような２つのストロークセットを示している。各階層は、ツリーデータ構造によって表され、リーフノードは、個々のＳＳＦストロークを表し、中間ノードは、ＳＳＦストロークサブセットを表し（当初、同じ経路の一部であったＳＳＦストローク又は互いに交差するＳＳＦストローク若しくはＳＳＦストロークのサブセット）、ルートノードは、ストロークセットのすべてのＳＳＦストロークを表す。

ステップ３−ＳＳＦストロークのセットのアウトライン領域への割り当て
ステップ３は、どのＳＳＦストロークセットが各アウトライン領域に対応するのかを求める（図１１Ａ〜図１１Ｃ参照）。ＳＳＦグリフは変換されて、自身の軸位置合わせされたバウンディングボックスが、対応するアウトライングリフの軸位置合わせされたバウンディングボックスにマッピングされる。アウトライン領域の距離場を使用して、各ＳＳＦストロークセットは、その後、自身の最も近いアウトライン領域に割り当てられる。アウトライン領域がＳＳＦストロークセットに割り当てられない場合、近くのＳＳＦストロークサブセット又はＳＳＦストロークがそのアウトライン領域に再割り当てされる。アウトライン領域に最も近いＳＳＦストロークサブセット又はＳＳＦストローク（ＳＳＦストロークサブセットの一部でない）は、そのアウトライン領域に再割り当てされる。

ステップ３を示すために、一例を図１１Ａ〜図１１Ｃに与えることにする。ステップ３は、各アウトライン領域（ａ〜ｅ）に対応するＳＳＦストロークセットを求める。最初に、各ＳＳＦストロークセット（図１１Ｂ参照）が、該ＳＦストロークセットが最も近いアウトライン領域に割り当てられる（図１１Ａ参照）。アウトライン領域が、割り当てられたＳＳＦストロークセットを有しない場合、例えばアウトライン領域ｅの場合、その領域に最も近いＳＳＦストロークを含むＳＳＦストロークセット、例えばＳＳＦストロークセットｃが、ＳＳＦストロークを有しないアウトライン領域（アウトライン領域ｅ）とＳＳＦストロークセットが最初に割り当てられたアウトライン領域（アウトライン領域ｃ）とに分割される。

ステップ４−ＳＳＦ本体のフィット
ステップ３において、ＳＳＦストロークのセットをアウトライン領域に割り当てると、１つ又は複数のＳＳＦストロークセットが、各アウトライン領域に割り当てられたことになる。各アウトライン領域の形状は、その領域を規定する暗に含まれたストロークの合成形状であることを思い出されたい。

ステップ４において、各ＳＳＦストロークセットにおけるストロークの本体が、それらの対応するアウトライン領域の暗に含まれたストロークの本体と一致するように修正される。この方法は、各アウトライン領域及びその対応するストロークを独立に取り扱う。

アウトライン領域に対応するＳＳＦストロークは、最初に、それらのバウンディングボックスの結合体がアウトライン領域のバウンディングボックスと位置合わせされるように変換される。次に、各ＳＳＦストロークは、後述するように、アウトライン領域の距離場を使用して修正されて、その本体が、アウトライン領域の対応する暗に含まれたストロークの本体と一致される。

エネルギー及び力
最終的には、ストローク本体の各ＳＳＦ中心線は、アウトライン文字の対応する暗に含まれたストロークのストローク本体の中心線に位置合わせされる。ＳＳＦ中心線の位置合わせは、アウトライン領域の距離場がＳＳＦ中心線を挟んでどのように変化するのかを反映するエネルギーを使用して定量化される。ＳＳＦ中心線は、このエネルギーを削減するようにＳＳＦ中心線に沿って力を印加して、ＳＳＦ中心線をその対応する暗に含まれたストロークの中心線に接近させることにより反復的に修正される。

図１５に示すように、ＳＳＦ中心線のエネルギーは、ＳＳＦ中心線に沿った等間隔サンプル点１５０１におけるエネルギーの平均である。点ｐにおけるエネルギーは、ｐ並びに２つの点ｐ_ａ及びｐ_ｂにおける距離を使用して計算される。点ｐ_ａ及びｐ_ｂは、ｐにおけるＳＳＦ中心線に垂直な各方向に、小ステップだけｐからオフセットされた点である。すなわち、エネルギーは、Ｅｎｅｒｇｙ_ＣＮＴＲ（ｐ）＝｜Ｄｉｓｔａｎｃｅ（ｐ_ａ）−Ｄｉｓｔａｎｃｅ（ｐ_ｂ）｜＊（Ｃ−Ｄｉｓｔａｎｃｅ（ｐ））となる。ここで、Ｃは、（Ｃ−Ｄｉｓｔａｎｃｅ（ｐ））＞０となるように、Ｄｉｓｔａｎｃｅ（ｐ）の最大値よりも大きな定数である。理想的には、Ｃは、ｐが暗に含まれたストロークの中心線に近いときに（Ｃ−Ｄｉｓｔａｎｃｅ（ｐ））が小さくなるように、アウトライン領域の距離場の最大値に等しい。

アウトライン領域の距離場が、ＳＳＦの中心線を挟んで対称であるとき（｜Ｄｉｓｔａｎｃｅ（ｐ_ａ）−Ｄｉｓｔａｎｃｅ（ｐ_ｂ）｜＝０であるとき）、エネルギーはゼロである。アウトライン領域の距離場が、ＳＳＦ中心線を挟んで対称でないとき、ＳＳＦ中心線がアウトライン領域の暗に含まれた中心線に接近するにつれて、エネルギーは減少する。

ＳＳＦ中心線に沿ったサンプル点における力は、そのエネルギーを削減するようにＳＳＦ中心線を修正するのに使用される。各力は、ＳＳＦ中心線に垂直であり、距離が増加する方向を指している。力の大きさは、サンプル点ｐにおけるＳＳＦ中心線のエネルギーに比例する。すなわち、Ｆ（ｐ）＝Ｎ^＋＊Ｅｎｅｒｇｙ_ＣＮＴＲ（ｐ）＊ＳＴＥＰ＿ＳＩＺＥとなる。ここで、Ｎ^＋は、距離が増加する方向を指すｐにおけるＳＳＦ中心線の法線であり、ＳＴＥＰ＿ＳＩＺＥは、ユーザーによって定義される。

各力は、アウトライン文字を前処理するステップ１において求められたマスクからの関連付けられた重みを有する。この重みは、そのサンプル点が、暗に含まれたアウトラインストロークの本体に対応する領域に位置する尤度を反映している。

ＳＳＦ本体の修正
アウトライン領域に対応するＳＳＦストロークは、階層ツリー構造の順序で反復的に修正される。アウトライン領域に対応するＳＳＦストロークセットは、ツリー構造Ｔに置かれ、ツリー構造Ｔにおいて、各ＳＳＦストロークセットは、Ｔのルートノードの子である（図１０参照）。

最初に、すべてのＳＳＦストローク、すなわち、Ｔのルートノードに含まれるすべてのストロークが、単一のユニットとして修正される。連続した反復と反復との間の中心線エネルギーの変化が小さいとき、各ＳＳＦストロークセット、すなわちＴのルートノードの各子は、独立に修正される。最終的に、各ＳＳＦストローク、すなわちＴの各リーフノードが独立に修正されるまで、図１０の階層を順に下降する。

ＳＳＦ本体が修正される方法は、ＳＳＦ中心線がその対応する暗に含まれたストロークの中心線に接近するにつれて変化する。

最初、アフィン変換が使用されて、ＳＳＦ中心線が粗く成形され位置決めされる。各サンプル点における力は、そのサンプル点の所望のロケーションを規定する。重み付き最小二乗ソルバーが使用されて、現在のノードに含まれるすべてのＳＳＦストロークについて、サンプル点の所望のロケーションからの該サンプル点の二乗距離の合計を最小にするアフィン変換が計算される。アフィン変換は、次に、ＳＳＦ中心線の制御頂点に適用され、それらの位置及び形状が更新される。

アウトライン領域に対応するすべてのＳＳＦストロークが独立に変換され、それらの中心線エネルギーの変化が所定のしきい値よりも小さいとき、この方法は、各ＳＳＦ本体の微調整に進む。

ＳＳＦ本体の３つの特性、すなわちＳＳＦ中心線の形状、ＳＳＦ本体の長さ、及びＳＳＦ輪郭の形状は、ＳＳＦ本体の形状がその対応する暗に含まれたストロークの本体の形状と一致するように反復的に修正される（図１２Ｄ参照）。

各ＳＳＦ中心線の形状は、距離ベースの曲線フィッティング手順を使用して修正される。上述したように、力が、中心線に沿ったサンプル点のセットについて計算され、アウトライン文字を前処理するステップ１において求められたマスクで重み付けされる。これらのサンプル点の力は、次に、中心線を規定する制御頂点を再位置決めするために組み合わせられて適用され、それによって、中心線の形状が修正される。

詳細には、各制御頂点は、サンプル点の力の重み付き総和の方向に小ステップだけ移動される。重み付き総和の重みは、中心線の各部分を規定する周知のベルンシュタイン多項式の係数に関係付けられる。

例えば、ｐ（ｔ）＝（１−ｔ）^２Ｃ_１＋２ｔ（１−ｔ）Ｃ_２＋ｔ^２Ｃ_３（ここで、ｔ∈［０，１］）によって規定される二次ベジェ曲線に沿ったサンプル点ｐ（ｔ）の重みは、制御頂点Ｃ_１については（１−ｔ）^２であり、制御頂点Ｃ_２については２ｔ（１−ｔ）であり、制御頂点Ｃ_３についてはｔ^２である。

ＳＳＦストローク本体は、ＳＳＦ本体の端部が、該端部が位置する領域にどれだけよくフィットしているのかを判断する一連の述語試験に基づいて長く及び短くされる。

（１）ＳＳＦ本体の端部が、その対応するアウトライン領域の外側に位置している場合、（２）ＳＳＦ本体の端部が、別のＳＳＦ本体の内側に位置している場合、（３）ＳＳＦ中心線の端部が、その対応する暗に含まれた中心線に位置合わせされていない場合、又は（４）ＳＳＦ本体の端部に沿った形状が、暗に含まれたストロークの端部に沿った形状と一致していない場合には、ＳＳＦストロークは短くされる。それ以外の場合には、ストロークは長くされる。

ＳＳＦ本体の形状は、ＳＳＦ中心線に沿ったサンプル点距離に二次ベジェ曲線を、フィットさせるように、重み付き線形最小二乗法を使用して、その輪郭４０２を更新することにより調整される。これらの重みは、サンプル点距離が、サンプル点におけるストローク幅にどれだけよく対応しているのかを反映している。重みは、次のように求められる。

ＳＳＦ中心線４０１が、その対応する暗に含まれたストロークの中心線と完全に位置合わせされているとき、中心にあるサンプル点ｐ、例えば暗に含まれたストロークの交点に対応していない領域におけるそのサンプルの対応する暗に含まれた中心線に位置するサンプル点、における距離Ｄｉｓｔａｎｃｅ（ｐ）は、そのサンプル点におけるストローク幅Ｗｉｄｔｈ（ｐ）を示す。

各サンプル点ｐは、２つの関連付けられたオフセット点ｐ_ａ及びｐ_ｂを有する。点ｐ_ａ及びｐ_ｂは、ｐにおけるＳＳＦ中心線に垂直な各方向にＷｉｄｔｈ（ｐ）だけｐからオフセットされた点である。ｐが中心にあるとき、ｐ_ａ及びｐ_ｂは、アウトライン領域の距離場のゼロレベルの等位面に位置する。これが生じたとき、距離はｐ_ａ及びｐ_ｂにおいて０であり、ｐ_ａ及びｐ_ｂにおける距離場の勾配は、ｐにおける中心線にほぼ垂直である。

ｐ_ａ及びｐ_ｂにおける距離及び勾配を使用して、重みが各サンプル点ｐについて計算される。この重みは、ｐが中心にあるか否かを示す。距離場の勾配と各オフセット点において垂直な対応する中心線との間の差は、そのオフセット点における距離によって拡大縮小される。

ステップ５−ＳＳＦ本体の端部位置の調整
ステップ４において、ＳＳＦ本体をフィットさせる際に、ＳＳＦ本体は、たとえフィットしなかったエリアが、暗に含まれたストロークの本体に対応した可能性があっても、該ＳＳＦ本体がフィットしなかったエリアの外部では収縮せざるを得ない（図１２Ｄ）。例えば、或るＳＳＦ本体は、その端部が２つの暗に含まれたストロークの接合部に対応するエリアに位置していたことから、収縮した可能性がある。

アウトライン文字のトポロジを保存するために、コーナー又は接合部を形成すべきＳＳＦ本体は、明示的に接続され、他のＳＳＦ本体に接続されていないＳＳＦ本体の端部は、末端に対応するアウトライン領域のエリアに位置決めする必要がある（図１２Ｅ）。ＳＳＦ本体の端部位置の接続及び延長は、本明細書では、ＳＳＦ本体の調整と呼ばれる。暗に含まれたストロークの端部、接合部、及びコーナーの候補エリアのセットは、ＳＳＦ本体の端部をどのように接続及び位置決めする（すなわち調整する）のかを示す。

各ＳＳＦ中心線は、そのＳＳＦ中心線の端部が、候補エリアの中心にできるだけ近くなるように、その経路に沿って次の候補エリアに向け順に延長される。ＳＳＦ中心線の延長をいつ停止するのかを判断するのに３つのルールが使用される。

第１に、ＳＳＦ中心線の端部が別のＳＳＦ中心線に遭遇した場合には、該ＳＳＦ中心線の端部の向かい側、例えば、どのＳＳＦストロークによっても覆われていない交差するＳＳＦストロークの向こう側に、アウトライン領域のエリアがある場合にのみ、ＳＳＦ中心線は延長し続けることが可能になる。

第２に、ＳＳＦ本体の端部が、その形状がその対応する暗に含まれたストロークの本体の形状と一致しないエリアに（端部が次の候補エリアに達する前に）遭遇した場合、ＳＳＦ中心線は、その前の位置にリセットされる。

第３に、ＳＳＦ中心線の端部が次の候補エリアを表す円に達したが、その円のエッジまでの該ＳＳＦ中心線の距離が、その前の候補エリアを表す円のエッジまでの距離よりも小さい場合、ＳＳＦ中心線は、その前の位置にリセットされる。

ＳＳＦ中心線が進行を停止した後、他のＳＳＦ中心線を含む候補エリアに位置するＳＳＦ中心線の端部について、接合部及びコーナーを明示的に形成することが必要となり得る。各ＳＳＦ中心線の端部が、順に考慮される。

ＳＳＦ中心線の端部が別のＳＳＦ中心線の一部を含む候補エリアに位置する場合、接合部又はコーナーが形成される。すなわち、（１）ＳＳＦ中心線の端部が、別のＳＳＦ中心線の端部を含む円に位置し、かつそれらの双方のＳＳＦ中心線の一方をさらに延長して接続する必要があるか、又はそれらのＳＳＦ中心線の端部間の距離が双方のＳＳＦ中心線の端部におけるＳＳＦ輪郭のサイズよりも小さい場合には、コーナーが形成され、（２）それ以外の場合には、接合部が形成される。

ステップ６−ＳＳＦ末端の選択
ＳＳＦ末端が、図１３に示す末端のセット１３００から選択される（図１２Ｆ）。末端は、アウトラインフォントのサンプル文字の小さなセットを調べることによってインタラクティブにあらかじめ決定される。各ＳＳＦ末端は、そのＳＳＦ末端をＳＳＦ本体にフィットさせるために、関連付けられたユーザー定義の最大の回転及び拡大縮小が許容されている。ＳＳＦ末端を規定する経路は、アウトライン領域の距離場のゼロレベル等位面に位置するべきである。経路に沿った任意の点ｐにおいてこれが生じたとき、アウトライン領域の距離場の値はｐにおいて０であり、距離場の勾配は、ｐにおいて末端経路に垂直である。

図１４に示すように、セット内の各ＳＳＦ末端をＳＳＦ本体の端部に置き、次にＳＳＦ本体に沿ってそのＳＳＦ末端をスライドさせることを、そのフィットを測定しながら行うことによって、ＳＳＦストロークの最良の末端１４００及びストロークに沿ったその位置が求められる。

ＳＳＦ末端の開口部がＳＳＦ中心線に垂直になり、かつＳＳＦ本体のエッジに位置合わせされるように、ＳＳＦ末端が変換、すなわち平行移動、回転、及び拡大縮小されたときに、ＳＳＦ末端の向き及びサイズは更新される。末端のフィット誤差が、ＳＳＦ末端経路に沿った等間隔サンプル点における距離場及び距離場の勾配を使用して測定される。

この誤差は、ＳＳＦ末端経路に沿ったサンプル点における誤差の平均Ｅｒｒｏｒ_ＴＥＲＭ（ｐ）＝‖Ｎｏｒｍａｌ（ｐ）−Ｇｒａｄｉｅｎｔ（ｐ）‖＊｜Ｄｉｓｔａｎｃｅ（ｐ）｜である。

特定のロケーションにおける最大の拡大縮小又は回転のいずれかを超えるＳＳＦ末端は、そのロケーションについて無視される。ＳＳＦ中心線端部がＳＳＦ末端の外部に延びるロケーションも廃棄される。これによって、ＳＳＦ末端がＳＳＦ本体に沿って遠くスライドしすぎることが防止される。接合部を形成するＳＳＦ本体の端部は、末端を有しない。コーナーを形成するＳＳＦ本体の端部は、より良くフィットする末端を有するＳＳＦストローク端部のＳＳＦ末端のみを使用する。

ステップ１〜６の要約
図１２Ａ〜図１２Ｆは、本発明による方法ステップの要約を示す。図１２Ａは、スタイル化ストローク文字が最初にどのように変換されて、その軸位置合わせされたバウンディングボックスが、アウトライン文字の軸位置合わせされたバウンディングボックスにマッピングされるのかを示している。ＳＳＦストロークセットがアウトライン領域に割り当てられた後（図１２Ｂ）、各アウトライン領域に対応するストロークは、それらのバウンディングボックスの結合体が、アウトライン領域のバウンディングボックスに位置合わせされるように変換される。

アフィン変換が使用されて、ＳＳＦ中心線が、それらの対応する暗に含まれたストロークの中心線と一致するように粗く形成及び位置決めされる（図１２Ｃ）。ＳＳＦストロークとそれらの対応する暗に含まれたストロークとの間の一致を改善するために、ＳＳＦ輪郭が求められ、ＳＳＦストロークの長さが調整され、ＳＳＦ中心線が曲げられる（図１２Ｄ）。ストロークのコーナー、接合部、交点、及び端部の候補エリアのセットを使用して、ＳＳＦ中心線が接続され、又は暗に含まれたストローク末端に対応する領域内に延長される（図１２Ｅ）。末端が、ＳＳＦストロークについて選択される（図１２Ｆ）。

拡張
本発明者の自動変換方法は、多数の拡張及び変化に対応し、（１）輪郭４０２を、単一の二次ベジェ曲線ではなく、線分及びベジェ曲線の区間的に連続な経路として表すことができること、（２）輪郭４０２が、単一の輪郭ではなく左輪郭及び右輪郭から構成することができ、それによって、変換プロセスが目的のアウトライン文字とよりよく一致することが可能になること、（３）数例挙げれば、サンプリングされた距離マップ、適応的にサンプリングされた距離マップ（ＡＤＦ：Ａｄａｐｔｉｖｅｌｙ Ｓａｍｐｌｅｄ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄ）、手順、又はメモリに記憶された距離値のセット等のさまざまな方法で距離場を表すことができること、（４）ＳＳＦストロークを領域と一致させるプロセスを改善するのに二部マッチング方法を使用することができること等に対応する。

動作環境
本発明は、多数の汎用又は専用のコンピューティングシステム環境又はコンピューティングシステム構成で動作することができる。本発明と共に使用するのに適した周知のコンピューティングシステム、コンピューティング環境、及び／又はコンピューティング構成の例には、パーソナルコンピューター、サーバーコンピューター、ハンドヘルドデバイス又はラップトップデバイス、マルチプロセッサシステム又はマルチコアシステム、グラフィックス処理ユニット（ＧＰＵ：Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、特定用途向け集積回路（ＡＳＩＣ：Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ：Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）、マイクロコントローラーベースシステム、セットトップボックス、プログラマブル民生用電子機器、ネットワークＰＣ、ミニコンピューター、メインフレームコンピューター、上記システム又はデバイスの任意のものを含む分散コンピューティング環境等が含まれるが、これらに限定されるものではない。

発明の効果
この自動変換方法を、２，５００個のよく使用される語から成る中国政府の教育省のリストの２，４８４個について試験した。この文字のセットは、その文字形状の変化が中国語文字セット全体を代表することから選択されたものである。

試験結果は、変換された文字が７０ｐｐｅｍで目に見える相違を有しておらず、文字の８８％が３０ｐｐｅｍで目に見える相違を有していないことを実証している。変換された文字は、特に小さな点のサイズにおいて目的のアウトライン文字とほぼ同一であり、その結果のフォントは、大幅に小さなメモリフットプリントを有し、例えば、アウトラインフォントの１０分の１である。メモリ要件のこの１桁分の削減はかなり大きい。

各スタイル化ストローク文字の誤差は、そのスタイル化ストローク文字の距離場と、対応するアウトライン文字の距離場との間の二乗差の平均を使用して測定される。この誤差測定によって、十分に変換されていない文字を自動訂正用に識別することが可能になる。

本発明を、好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することが、添付の特許請求の範囲の目的である。

Claims (13)

1. アウトライン文字をスタイル化ストローク文字に変換する、コンピュータによって実行される方法であって、前記方法は、
   前記コンピュータの有する手段が、前記アウトライン文字の領域を識別するステップであって、各領域が閉じて交わっていない、識別するステップと、
   前記コンピュータの有する手段が、各領域について、ストローク本体及び末端の候補ロケーションを求めるステップと、
   前記コンピュータの有する手段が、前記スタイル化ストローク文字の前記ストローク本体を初期化するステップと、
   前記コンピュータの有する手段が、前記ストローク本体を階層的ツリー構造に編成するステップと、
   前記コンピュータの有する手段が、前記階層的ツリー構造の順序で前記ストローク本体を反復的に修正するステップであって、修正されたストローク本体を作成する、修正するステップと、
   前記コンピュータの有する手段が、調整されたストローク本体が前記アウトライン文字と一致するように前記修正されたストローク本体の端部位置を調整するステップと、
   前記コンピュータの有する手段が、前記調整されたストローク本体の前記末端を選択するステップと、
   を含む方法。
2. 各領域は距離場で表され、前記求めるステップは、前記領域を規定する輪郭の高密度サンプリングされた線分近似のドロネー三角形分割を使用する、請求項１に記載の方法。
3. 前記ストローク本体は均一幅を有し、前記ストローク本体の中心線は、対応する均一幅ストローク文字の経路を使用し、コーナーを有する前記経路は区画されて、複数のストローク本体が形成される、請求項２に記載の方法。
4. 前記ストローク本体は、各領域について独立に修正及び調整される、請求項１に記載の方法。
5. 前記コンピュータの有する手段が、各ストローク本体の前記中心線を前記アウトライン文字の対応する暗に含まれたストロークの中心線に位置合わせするステップ、
   をさらに含む、請求項３に記載の方法。
6. 前記位置合わせするステップは、前記領域の前記距離場が各ストローク本体の前記中心線を挟んでどのように変化するのかを反映するエネルギーを使用して定量化される、請求項５に記載の方法。
7. 各ストローク本体の前記中心線は、前記中心線に沿って力を印加して前記エネルギーを削減し、各ストローク本体の前記中心線を前記アウトライン文字の前記対応する暗に含まれたストロークの前記中心線に接近させることにより反復的に修正される、請求項６に記載の方法。
8. 前記エネルギーは、各ストローク本体の前記中心線に沿った等間隔サンプル点における前記エネルギーの平均である、請求項７に記載の方法。
9. 前記エネルギーは、エネルギーの変化が所定のしきい値よりも小さくなるまで削減される、請求項７に記載の方法。
10. 前記位置合わせするステップは、アフィン変換を使用する、請求項５に記載の方法。
11. 各末端は、前記末端の開口部が特定のストローク本体の前記中心線に垂直になり、前記特定のストローク本体のエッジに位置合わせされるように、平行移動、回転、及び拡大縮小される、請求項１に記載の方法。
12. 前記コンピュータの有する手段が、前記アウトライン文字の距離場と前記スタイル化ストローク文字の距離場との間の差を測定するステップであって、変換誤差を識別する、差を測定するステップ、
    をさらに含む、請求項１に記載の方法。
13. 前記調整するステップは、
    前記コンピュータの有する手段が、前記修正されたストローク本体を接続して延長するステップであって、前記アウトライン文字と一致させる、前記修正されたストローク本体を接続して延長するステップ、
    をさらに含む、請求項１に記載の方法。

Images